Zeitkomplexität für die babylonische Methode

Wenn man den Wikipedia-Abschnitt für die babylonische Methode ansieht, können wir sehen, dass der relative Fehler bei Schritt k, e _k erfüllt die Gleichung e k & lt; & lt; 2 ^{-f (k)} , wobei f (k) rekursiv wie folgt definiert ist:

f (1) = 2 und f (k + 1) = 2 · f (k) + 1 für n & gt; 1

Nach Induktion gilt f (k) = 3 · 2 - 1

Sei n die Eingabe für unseren Algorithmus, der stoppt, wenn wir sicher sind, dass der Gesamtfehler kleiner ist als eine Konstante m

Der Fehler bei Schritt k, E k erfüllt die Gleichung E k = e k n

Daher wird der Algorithmus beendet, sobald e _{k & lt; m}

Dies tritt auf, wenn 2 ^{f (k)} & gt; n / m, was äquivalent zu f (k) & gt; log ₂ (n / m)

Diese Gleichung ist wahr, wenn 2 ^k-1 & gt; (log ₂ (n / m) - 1) / 3 was wahr ist, wenn k & gt; log ₂ ((log ₂ (n / m) - 1) / 3) + 1

Daher endet der Algorithmus in O (log (log (n / m) +1)) Schritten.

Mit dieser logarithmischen Summenformel können Sie dieses Protokoll anzeigen (log (x) + c)) = O (log (log (x)).

Daher verwendet die babylonische Methode O (log (log (n / m)) Schritte

Ich denke, die Schritte wären O (log2 (Logarithmus zur Basis E0 (m / n)) wobei E0 der Fehler bei der Nulliteration ist, d. h. wenn wir den Startwert wählen m ist Fehler erlaubt in der ANS und n ist die Eingabe in den Algorithmus. Sie können sich hierauf für eine vollständige Erklärung der rekursiven Funktion des Fehlers beziehen: Ссылка