Komplexitätsklassen auf schnelleren Rechnern

Wenn ein Algorithmus eine Komplexitätsklasse O (LogN) hat und auf einer alten Maschine ein Problem mit N = 10^6 in 1 Sekunde löst. Wie kann ich das N gleich schnell auf einer neuen Maschine 2x schneller berechnen?Komplexitätsklassen auf schnelleren Rechnern

Ich dachte vielleicht könnte ich die Konstante berechnen, die 1/log10^6 sein wird dann verwenden Sie das, um den Rest zu bekommen, aber ich denke nicht, dass das richtig ist. kann mich jemand zu den schritten führen, um das zu lösen?

Danke

Quelle

2016-05-27 Mrfuzzy

Wonach fragen Sie? Fragen Sie, wie Sie einen Algorithmus auf einer schnelleren Maschine gleichzeitig ausführen lassen? Wenn das der Fall ist, ist die Antwort einfach: Machen Sie einfach die doppelte Arbeit an jedem Schritt! –

Dies ist schwierig auf SO, die keine LaTeX unterstützt, aber hier: http://imgur.com/ehTqtKs –

annehmen lassen, dass "Log" bedeutet Logbase 2. In diesem Fall ist "LogN" 20. Dies bedeutet, dass die alte Maschine 20 Operationen in 1 Sekunde ausführen konnte.

Die neue Maschine kann doppelt so viele Operationen ausführen, also 40 Operationen in 1 Sekunde. Und das bedeutet, dass der Wert N ist, den die neue Maschine in 1 Sekunde verarbeiten kann.

Quelle

2016-05-27 03:59:54 user3386109

Alte Maschine: In der Zeit T haben wir O (log N) CPU-Zyklen.

Neue Maschine schneller 2x, so haben wir 0 (2 log N) CPU-Zyklen in der gleichen Zeit T.

O (2 log N) = 0 (log N^2)

so dass wir kann effektiv N^2 Daten in der gleichen Zeit verarbeiten.

Quelle

2016-05-27 04:17:45 Piyg

Komplexitätsklassen auf schnelleren Rechnern

Antwort

Verwandte Themen