Comment résoudre la récurrence.T(n).= T(n-1) + T(n/2) + n?

Question

Je suis conscient que, pour obtenir un temps d'exécution par récurrence la méthode d'arbre, nous avons besoin de dessiner un arbre et trouver:

a) nombre de niveaux dans l'arbre.

Depuis le côté gauche de l'arbre diminue de 1 la taille, donc c'est plus long chemin depuis la racine.Subproblem taille au niveau i est n-i .paramètre n - i = 1 lorsqu'il atteint une taille de 1, on obtient le nombre de niveaux, i = n - 1.

b) le coût par nœud dans l'arbre : cn

c) le Nombre de nœuds au niveau i:C'est là que je suis bloqué.Pas en mesure de trouver des noeuds au niveau i depuis le côté gauche, il diminue de 1, côté droit par moitié.Naturellement, l'arbre est de plus en plus dense vers la gauche.Pas chaque nœud aura deux enfants.

si je peux obtenir une réponse à c, je peux calculer T(n) = coût de niveau 0 + coût de niveau 1 + coût de niveau 2 + ...coût de niveau n-1.si y1 est le nombre de nœuds au niveau 1, y2, au niveau 2, etc...alors
=> T(n) = cn + y1 * cn + y2 * cn + y3 * cn + ....yn-1 * cn pour obtenir prix total.

Quelqu'un peut-il me guider pour l'approche que je prends ?est-il correct ?puis-je prendre une hypothèse que, pour n assez grand, on peut les ignorer, T(n/2), puis procéder ?.

De recherche en ligne qui me confond.Le problème est de 4,4-5 de PLC.

Veuillez voir ici

Cette solution, dit T(n) = O(2^n) et T(n) = omega(n^2) et n'explique pas comment.

Voir aussi ici

Cette solution, dit T(n) = O(n^2).mais contredit avec la solution ci-dessus

Answer 1

Laissez $S(n) = T(n) - 2n - 2$.Vous pouvez vérifier que $S(n) = S(n-1) + S(n/2)$ (en ignorant le fait que $n/2$ n'a pas besoin d'être un nombre entier).Cela montre que l'additif $n$ terme n'est pas faire une grande différence.

Pour les grands $n$, nous avons à peu près $S(n) - S(n-1) \approx S'(n)$, et nous sommes donc amené à résoudre l'équation différentielle $$ S'(n) = S(n/2).$$ Envisager $f(n) = \exp ( frac{1}{2}\log_2^2 n)$.Alors $$ f'(n) = \exp ( frac{1}{2}\log_2^2 n) \cdot \frac{\ln n}{(\ln 4)n}, $$ alors que $$ f(n/2) = \exp( frac{1}{2} (\log_2 n - 1)^2) \approx \exp( frac{1}{2}\log^2 n) \exp(-\log n) = \exp( frac{1}{2} \log^2 n) \cdot \frac{1}{n}.$$ Ceci suggère que, à tout le moins, $\ln S(n) = heta(\log^2 n)$.

D'où vient-il?Vous pouvez penser $S(n)$ (avec une base appropriée cas!) comme le nombre de façons d'aller de $n$ à zéro par l'application de deux opérations:soustraire 1 et diviser par 2."Typique" de cette séquence contiendra environ $\log_2n$ de nombreuses opérations du deuxième type, de $ heta(n)$ opérations au total, conduisant à l'estimation très approximative $\binom{ heta(n)}{\log_2 n}$, qui est aussi de la forme $\exp heta(\log^2 n)$.

---

Envisager de concret pour la suite de définition précise de l' $S(n)$:le cas de base est $S(0) = 1$, et pour $n > 0$, $$ S(n) = S(n-1) + S(\lfloor n/2 floor).$$ C'est la séquence A000123.Knuth, Un presque linéaire de la récidive, a montré que $$ \log_4 S(n) \sim \log_4^2 n, $$ c'est le rapport des deux termes tend vers 1 comme $n o \infty$.L'OEIS entrée contient encore plus de précision asymptotique.

Answer 2

Je suis en désaccord avec le Fibonacci hypnose, mais je ne suis pas à cent pour cent sûr de ma réponse

Vous voyez $ T(n)= T(n-1) +c*n = O(n ^2) $

$ T(n) = T(n/2) + c*n =O(n log n) $

Cependant, u n'a pas obtenir de l'ur T(n) par simple ajout.

Si u remonter d'un niveau dans la récursivité (u peut dessiner un arbre)

T(n) =T(n-2) +T((n-1)/2) +T(n/2-1)+ T(n/4) + [n + (n-1) + (n-1)/2 + (n/2-1) +n/4]

Ceci pour montrer u il n'est également pas juste $ O(n^2) $

J'ai pour l'achever, mais je soupçonne que ce soit $ O (n^2) * log n) $ ou $ O (n^2) * n ^ {log n} ) = O(n^3) $

{Il est un terme n(1+1/2+1/4+..1/n) qui se désintègre dans le journal de n étapes, je dois vérifier à nouveau}