Lösen von Rezidiven
-
19-09-2019 - |
Frage
Am versuchen, die gegebenen 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 heraus, n/(log(n/9))
zu sein.
Kann ich die obige Gleichung in Form von n.loglogn
verallgemeinern
Dies ist ein allgemeiner Zweifel ich habe, ich brauche einen Einblick zu diesem Thema.
Hinweis:
Jede Funktion, die in dieser Funktion k wird Theta(n^k log^k (n))
muss sollte> = 1. Und in diesem Fall k -1 so Master-Theorem nicht in zu Bild kommt
Lösung
Es ist wahr, die Master-Theorem gilt nicht.
T (n) = 3T (n / 3) + n / logn.
Es 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 ergibt g (n) = Summe 1 / log n + 1 / log n / 3 + 1 / log n / 9 + ...
= Theta (Summe 1 / log n + 1 / (log n -1) + 1 / (log n - 2) + ...) = Theta (Integral 1 / x zwischen 1 und log n) = Theta (log log n ).
So T (n) = n g (n) = Theta (n log logn).
Sie ahnen es richtig.
Andere Tipps
Wenn Sie einen Baum verwenden, um die Frage zu visualisieren, werden Sie sehen, dass die Summe der einzelnen Rang ist:
- rank 0:
(die n / log gleich (n)) - Rang 1:
und so weiter, mit einer allgemeinen Summe n/log(n/(3^i))
für jeden Rang, wobei i der aktuelle Rang. so, wir alle zusammen bekommen:
Wenn wir die Gleichung öffnen wir bekommen:
(ab Ende und rückwärts .. zuerst, wenn i = log (base3) n und dann zurück)
da Logbase in Theta egal ist, erhalten wir:
das ist:
, die (in Sigma) ist:
, die eine harmonische Reihe ist gleich:
und da ln log mit einer Basis von e ist, und log Basen keine Rolle in Theta, wir schließlich erhalten:
, die gleich:
Es ist also Theta (n log log n).