Recidiva con una funzione di n volte t ()

Question

Il metodo principale funziona bene su problemi come $ t (n)= kt (AN) + cn $ , ma non gestisce problemi come $$ t (n)= n ^ {\ frac {1} {3}} t (n ^ {\ frac {2} {3}}) + n ^ 2 $$ Con il numero di rami per ogni partizione è una funzione di $ N $ .Mi chiedo se c'è una buona soluzione a questo tipo di problemi, non ho idea di come risolvere questo, qualsiasi aiuto è apprezzato!

Answer 1

È possibile utilizzare il metodo più elementare in cui si espande la recidiva: \ Begin {Align} T (n) &= n ^ 2 + n ^ {1/3} t (n ^ {2/3}) \\ &= n ^ 2 + n ^ {5/3} + n ^ {5/3} + n ^ {5/9} T (n ^ {4/9}) \\ &= n ^ 2 + n ^ {5/3} + n ^ {10/9} + n ^ {10/9} + n ^ {19/9} + n ^ {19/27} t (n ^ {8/27} ) \\ &=cdots \ end {allinea} Questo suggerisce che $ t (n)= o (n ^ 2) $ . In effetti, cerchiamo di dimostrare di induzione che $ t (n) \ leq cn ^ 2 $ : $$ T (n) \ leq n ^ 2 + n ^ {1/3} \ cdot cn ^ {4/3}= n ^ 2 \ sinistra (1 + \ frac {c} {n ^ {1/3}} \ giusto), $$ che sarà al massimo $ cn ^ 2 $ per qualsiasi classe $ c> 1 $ e abbastanza grande $ N $ (a seconda della classe $ c $ ).

Infatti, definendo $ s (n)= t (n) - n ^ 2 $ , abbiamo $$ S (n)= n ^ {5/3} + n ^ {1/3} s (n ^ {2/3}), $$ e quindi lo stesso argomento mostra che $ s (n)= o (n ^ {5/3}) $ e così $ T (n)= n ^ 2 + o (n ^ {5/3}) $ . Allo stesso modo, possiamo ottenere $ t (n)= n ^ 2 + n ^ {5/3} + o (n ^ {10/9}) $ , e così via.