Asymptotische Komplexität von T (n) = T (n-1) + 1 / n [geschlossen]

Man kann leicht sehen (oder formal mit Induktion bewiesen), dass T (n) die Summe von 1 / k für die Werte von k von 1 bis n ist. Dies ist die harmonische Zahl , H _n = 1 + 1/2 + 1/3 + ... + 1 / n.

Asymptotisch wachsen die harmonischen Zahlen in der Größenordnung von log (n). Dies liegt daran, dass die Summe nahe dem Wert des Integrals von 1 / x von 1 bis n ist, was gleich dem natürlichen Logarithmus von n ist. Tatsächlich ist Hn = ln (n) + γ + 0 (1 / n), wobei γ eine Konstante ist. Daraus kann man leicht zeigen, dass T (n) = Θ (log (n)).

Für weitere Details:

Mit H(N) = 1 + 1/2 + 1/3 + ... + 1/N

Die Funktion x :-> 1/x ist eine fallende Funktion also:

Wir summieren von 1 to N den linken Teil und für den rechten Teil berechnen wir aus 2 to N und wir fügen 1 hinzu, wir erhalten:

Dann berechnen wir die linken und rechten Teile: ln(N+1) <= H(N) <= 1 + ln(N)

Das bedeutet H(N)/ln(N) -> 1 daher H(N)=Θ(log(N))

(aus Ссылка )