Récurrence avec une fonction de n fois t ()
-
29-09-2020 - |
Question
La méthode principale fonctionne bien sur des problèmes tels que $ t (n)= kt (an) + cn $ , mais cela ne traite pas de problèmes comme $$ t (n)= n ^ {\ frac {1} {3}} t (n ^ {\ frac {2} {3}}) + n ^ 2 $$ Avec le nombre de branches pour chaque partition est une fonction de $ n $ .Je me demande s'il y a une bonne solution à ce genre de problèmes, je n'ai aucune idée de la façon de résoudre ce problème, aucune aide est appréciée!
La solution
Vous pouvez utiliser la méthode la plus élémentaire dans laquelle vous élargissez la récurrence: \ commence {align} T (n) &= n ^ 2 + n ^ {1/3} t (n ^ {2/3}) \\ &= n ^ 2 + n ^ {5/3} + n ^ {5/9} T (n ^ {4/9}) \\ &= n ^ 2 + n ^ {5/3} + n ^ {10/9} + n ^ {19/27} T (n ^ {8/27} ) \\ &=CDOT \ fin {align} Cela suggère que $ t (n)= O (n ^ 2) $ . En effet, essayons de prouver par induction que $ t (n) \ leq cn ^ 2 $ : $$ T (n) \ leq n ^ 2 + n ^ {1/3} \ cdot cn ^ {4/3}= n ^ 2 \ gauche (1 + \ frac {c} {n ^ {1/3}} \ droite), $$ qui sera au plus $ CN ^ 2 $ pour tout $ C> 1 $ et assez grand Classe="Math-Conteneur"> N $ N $ (Selon $ C $ ).
En effet, définissant S (n) $= t (n) - n ^ 2 $ , nous avons $$ S (n)= n ^ {5/3} + n ^ {1/3} s (n ^ {2/3}), $$ et donc le même argument montre que s (n) $= O (n ^ {5/3}) $ et donc $ T (n)= n ^ 2 + o (n ^ {5/3}) $ . De la même manière, nous pouvons obtenir $ t (n)= n ^ 2 + n ^ {5/3} + o (n ^ {10/9}) $ , et ainsi de suite.