Problem mit der Erklärung der einzelnen for-Loop-Laufzeit

8

Ich analysiere einige Laufzeiten verschiedener For-Loops, und wenn ich mehr Wissen bekomme, bin ich neugierig, dieses Problem zu verstehen, das ich noch nicht herausgefunden habe. Ich habe diese Übung mit dem Titel "Wie viele Sterne werden gedruckt":

for (int i = N; i > 1; i = i/2) System.out.println("*");

Die Antworten zur Auswahl sind A: ~log N B: ~N C: ~N log N D: ~0.5N^2

Die Antwort sollte also A sein und ich stimme dem zu, aber auf der anderen Seite. Sagen wir, N = 500was wäre Log Ndann? Es wäre 2.7. Was ist, wenn wir das N=500bei unserer obigen Übung sagen ? Das würde definitiv mehr als 2,7 Sterne drucken? Wie hängt das zusammen?

Weil es Sinn macht zu sagen, wenn die for-Schleife so aussah:

for (int i = 0; i < N; i++)

es würde NSterne drucken .

Ich hoffe, hier eine Erklärung dafür zu finden, vielleicht interpretiere ich all diese Dinge falsch und denke schlecht darüber nach. Danke im Voraus.

algorithms complexity big-o runtime owwyess
quelle
Wie unterscheidet sich das von Ihrer vorherigen Frage? Asymptotische Laufzeit von for-Schleifen
Mücke
Dies hat nichts mit asymptotischen Laufzeiten zu tun.
Owwyess
1
Diese Option ist nur sinnvoll, wenn der Logarithmus zur Basis 2 gemeint ist, nicht der Logarithmus zur Basis 10.
Kilian Foth
3
Welche Basis nehmen Sie an, um Log 500 = 2.7 zu erhalten? und erscheint diese Basis irgendwo in Ihrem Code? Nb Sie sind immer nur ein konstanter Faktor anders mit Protokollen verschiedener Basen
Caleth
2
@Caleth die Logarithmus Basis wird in dem Code angezeigt werden : i = i/2die Basis zwei ist , weil die Schleife durch zwei wiederholte Multiplikation rückwärts fährt.

Antworten:

34

Sie haben das Schlüsselmerkmal der Logarithmusbasis übersehen .

Da iin jeder Iteration durch 2 geteilt wird, ist die Laufzeit mit Basis 2 logarithmisch

log 2 (500) ~ 8,9

Was Sie sehen, ist

log 10 (500) ~ 2,7

(Logarithmus mit Basis 10)

Der Grund, warum die Basis in Laufzeitdiskussionen häufig weggelassen wird (und Ihr Rechner wahrscheinlich keine Schaltfläche für Protokoll 2 hat ), ist, dass aufgrund der Mechanismen der logarithmischen Mathematik eine andere Basis einem konstanten Faktor entspricht und somit ist nicht relevant, wenn Sie ohnehin konstante Faktoren ignorieren. Es kann leicht berechnet werden:

log a (x) = log b (x) / log b (a)

Michael Borgwardt
quelle
Das macht total Sinn, also ist es eigentlich nur mein Mangel an Wissen über Logarithmen. Danke für die einfache und klare Antwort.
Owwyess
Danke @Michael Borgwardt. Jede Chance, die Sie dem obigen Beispiel mit N = 500 geben könnten. Wie kann ich das auf einem Taschenrechner mit nur Log Base 10 berechnen?
Owwyess
2
@owwyess Sie teilen das log10 Ergebnis durch log10 (2)
Ratschenfreak
Entschuldigung, ich hatte mich verwirrt und mit log10 (10) geteilt. Vielen Dank an alle.
Owwyess
2
Der im letzten Absatz erwähnte konstante Faktor beträgt ungefähr 3,322 für Basis 2. Dh Sie benötigen ~ 3,3 Binärziffern für eine Dezimalstelle. Oder wenn Sie lieber eine 33-stellige Binärdatei mit ~ 10 Dezimalstellen haben.
Kapitän Giraffe
8

Zusätzlich zu Michael Borgwardts Antwort sollte das Tilde-Zeichen vor jeder Antwort als "proportional zu" gelesen werden. Wenn Sie also N verdoppeln (z. B. von 500 auf 1000), sehen Sie, dass sich die Laufzeit (oder in diesem Fall die Anzahl der gedruckten Sterne) um einen Faktor erhöht, der gleich (log1000 / log 500) ist. welche unabhängig von welcher Basis Sie verwenden.

Boluc Papuccuoglu
quelle
2
Ich habe Tilde immer als ungefähr und nicht proportional verstanden. Im Wesentlichen ~ist eine Abkürzung für ≅.
Davor Ždralo
1
Proportional zu ist das ∝Symbol nicht ~! Das ~wird verwendet, um Äquivalenzrelationen oder ungefähre Gleichungen anzuzeigen (siehe Wikipedia-Seite über Tilde ).
Bakuriu