Le calcul de la Relation de Récurrence T(n)=T(n-1)+logn
Nous pouvons résoudre la relation de récurrence à travers la répétition de substitution:
T(n)=T(n-1)+logn
J'ai commencé la substitution et le suivant.
T(n)=T(n-2)+log(n)+log(n-1)
Par le logarithme du produit de la règle, log(mn)=logm+logn,
T(n)=T(n-2)+log[n*(n-1)]
De la poursuite de cette, je reçois
T(n)=T(n-k)+log[n*(n-1)*...*(n-k)]
Nous savons que le cas de base est T(1), de sorte que n-1=k -> k=n+1, et la substitution de ce nous obtenons
T(n)=T(1)+log[n*(n-1)*...*1]
Clairement n*(n-1)*...*1 = n! donc,
T(n)=T(1)+log(n!)
Je ne sais pas comment le résoudre-delà de ce point. La réponse est tout simplement O(log(n!))? J'ai lu d'autres explications en disant que c'est Θ(nlogn) et donc il en résulte que O(nlogn) et Ω(nlogn) sont les limites inférieures et supérieures respectivement.
Θ(log(n!)) = Θ (n log n)
Le
k est le nombre maximum d'étapes pour cette récursivité.
reformulée. vous dire k=n? 😉
La façon dont mon professeur (et quelques autres explications en ligne) ont été de le faire est d'utiliser k pour représenter un générique de "maximum" de substitution.
Le
k dans cette dernière deux équations est juste de crier " hé, ce que l'enfer je suis en train de faire ici, si les autres conditions sont indépendantes l'une de moi?? Qui ne regarde pas à droite...k est le nombre maximum d'étapes pour cette récursivité.
reformulée. vous dire k=n? 😉
La façon dont mon professeur (et quelques autres explications en ligne) ont été de le faire est d'utiliser k pour représenter un générique de "maximum" de substitution.
OriginalL'auteur Jay | 2014-03-24
Vous devez vous connecter pour publier un commentaire.
Ceci développe à log (n!). Vous pouvez voir car
La réponse exacte dépend de ce que T(0) est, mais c'est Θ(log n!) pour toute constante fixe la valeur de T(0).
Une note à l'aide de Stirling rapprochement, Θ(log n!) = Θ(n log n). Qui pourrait vous aider à porter ce retour à l'existant, la complexité des classes.
Espérons que cette aide!
OriginalL'auteur templatetypedef
La formule de Stirling n'est pas nécessaire pour obtenir la grande-Theta lié. Il est O(n log n), car c'est une somme de n termes chacun, au plus log n. C'est Omega(n log n), car c'est une somme d'au moins n/2 termes chacune au moins log (n/2) = log n - 1.
OriginalL'auteur David Eisenstat
Oui, c'est une récurrence linéaire du premier ordre. Il peut être résolu exactement. Si la valeur initiale est de $T(1) = 0$, on a $T(n) = \log n!$. Vous pouvez approximative de $\log n!$ (voir La formule de Stirling):
$$
\ln n! = n \ln n - n + \frac{1}{2} \ln \pí n + O(\ln n)
$$
[LaTeX ici!!]
OriginalL'auteur vonbrand