Komplexitätsklassen auf schnelleren Rechnern

Question

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?

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

Answer 1

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.

Answer 2

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.