J'essaie de résoudre la récursion donnée, à l'aide de l'arbre de récursion, dans le premier niveau dans le deuxième niveau, il s'avère être Puis-je généraliser l'équation ci-dessus sous la forme de C'est un doute général que j'ai, j'ai besoin d'une perspicacité à ce sujet.
note:
Toute fonction qui doit être t (n) = 3t (n / 3) + n / lg n.
(n / 3) / (N / 3)) + (n / 3) / (log (n / 3)) + (n / 3) / (log (nd / 3)) = N / (journal (n / 3)) .
n / (log (n / 9)) .
n.loglogn
theta (n ^ k log ^ k (n)) dans cette fonction k devrait> = 1. Et dans ce cas k est -1 tel que le théorème principal ne vient pas dans la photo
3 Réponses :
C'est vrai, le théorème principal ne s'applique pas.
t (n) = 3t (n / 3) + n / logn.
let g (n) = t (n) / n.
alors n g (n) = 3 (n / 3) * g (n / 3) + n / logn.
Ainsi
g (n) = g (n / 3) + 1 / journal n.
Ceci donne g (n) = somme 1 / journal n + 1 / journal n / 3 + 1 / journal n / 9 + ...
= theta (somme 1 / logn + 1 / (logn -1) + 1 / (journal n - 2) + ...) = thêta (intégré 1 / x entre 1 et logn) = thêta (journal de journal n ).
Ainsi, t (n) = n g (n) = theta (n logn de journal.)
Vous l'avez bien deviné.
On dirait qu'il y a une erreur juste à l'étape entre l'endroit où vous introduisez g (n) = t (n) / n et le n * g (n) = ... partie; n / logn n'a jamais marché jusqu'à n ^ 2 / logn
Je suis un peu faible dans le calcul, pouvez-vous s'il vous plaît expliquer-moi comment avez-vous reçu de la somme 1 / logn + 1 / (logn-1) + 1 / (logn-2) + ... pour intégrer 1 / x entre 1 et logn. Je peux comprendre que vous réécrivez la somme de la limite infinie comme une intégrale mais que je ne comprends pas comment.
Si vous utilisez un arbre pour visualiser la question, vous verrez que la somme de chaque rang est la suivante:
(qui est égal à n / journal (n)) - Classe 1:
et ainsi de suite, avec une somme générale de Si nous ouvrons l'équation, nous obtenons:
(à partir de la fin et descendant à l'envers. Premièrement, lorsque je = journal (base3) n puis en arrière)
Depuis la base de journal n'a pas d'importance dans Theta, nous obtenons:
qui est:
qui est (en sigma):
qui est une série harmonique égale à:
Et puisque LN est en train de loger avec une base de E et que les bases de journal ne comptent pas dans Theta, nous obtenons enfin:
qui est égal à:
Alors, c'est thêta (n journal journal n). n / journal (n / (3 ^ i)) pour chaque rang, je suis le rang actuel. Alors, tous ensemble, nous obtenons:
J'ai réellement corrigé vos liens avant de les ouvrir et maintenant un peu regretter: p. Il suffit de coller les mathématiques dans des extraits de code - il est plus lisible de toute façon.
Pour toute personne, déterminer la manière dont la série harmonique est approximativement à la lecture de la caisse de la caisse lien
t (n) = 3t (⌊3⌋) + 2nlogn avec condition de base 1 lorsque n <= 1
Par méthode de substitution:
Vous recherchez la solution (forme fermée) ou pour trouver la complexité de calcul?