Lösen von Rezidiven

Question

versuchte die gegebene Rekursion zu lösen, Rekursionsbaum Verwendung T(n) = 3T(n/3) + n/lg n.

In der ersten Ebene (n/3)/(log(n/3)) + (n/3)/(log(n/3)) + (n/3)/(log(n/3)) = n/(log(n/3)).

In der zweiten Ebene stellt sich n/(log(n/9)) erwiesen.

Kann ich die obige Gleichung in Form von n.loglogn

verallgemeinere Dies ist ein allgemeiner Zweifel ich habe, ich brauche einen Einblick zu diesem Thema.

Hinweis: Jede Funktion, die in dieser Funktion Theta(n^k log^k (n)) sein muss, sollte> = 1 sein. Und in diesem Fall k -1 so Master-Theorem kommt nicht in Bild

Answer 1

Es ist wahr, das Master-Theorem gilt nicht.

T (n) = 3T (n/3) + n/logn.

Sei g (n) = T (n)/n.

Dann n g (n) = 3 (n/3) * g (n/3) + n/logn.

So

g (n) = g (n/3) + 1/n log.

Dies gibt g (n) = Summe 1/log n + 1/n log/3 + 1/log n/9 + ...

= Theta (Summe 1/log n + 1/(logn -1) + 1/(log n - 2) + ...) = Theta (Integral 1/x zwischen 1 und logn) = Theta (log n log).

also T (n) = n g (n) = Theta (n log logn.)

Sie ahnen es richtig.

Answer 2

Wenn Sie einen Baum verwenden, um die Frage zu visualisieren, werden Sie sehen, dass die Summe der einzelnen Rang ist:

• Rang 0:

(der gleich bis n/log (n)) - Rang 1:

und so weiter, mit einer allgemeinen Summe n/log(n/(3^i)) für jeden Rang i der aktuelle Rang ist. so, wir alle zusammen bekommen:

wenn wir die Gleichung öffnen erhalten wir:

(ab Ende und rückwärts gehen ..zuerst, wenn i = log (base3) n und dann zurück)

seit Logbase nicht in Theta egal, erhalten wir:

das ist:

die (in Sigma):

, die eine harmonische Reihe ist gleich:

und seit ln mit einer Basis von e log ist, und melden Sie sich Basen keine Rolle in Theta, wir schließlich erhalten:

denen ist gleich:

Also, es ist Theta (n log log n).