n回の関数t（）の関数による再発

Question

マスターメソッドは、 $ t（n）= kt（a）+ cn $ のような問題にうまく機能しますが、問題は扱いません。 $$ t（n）= n ^ {3}} t（n ^ {\ frac {2} {3}}）+ n ^ 2 $$ 各パーティションのブランチ数は、 $ n $ の関数です。この種の問題に対する良い解決策があるのだろうか、私はこれを解決する方法を理解していない、あらゆる助けが高く評価されています！

Answer 1

再発を展開するより多くの基本的な方法を使用できます。 \ begin {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} ）\\=cdots. \ end {align} これは、 $ t（n）= o（n ^ 2）$ です。確かに、 $ t（n）\ leq cn ^ 2 $ という誘導によって証明しようとしましょう。 $$ t（n）\ LEQ n ^ 2 + n ^ {1/3} \ Cdot Cn ^ {4/3}= n ^ 2 \ left（1 + \ frac {c}}}}}}正しい）、 $$ $ c> 1 $ と十分な大きさのために、これは $ cn ^ 2 $ になります。 class="math-container"> $ n $ （ $ c $ に応じて）。

実際には、 $ s（n）= t（n） - n ^ 2 $ を定義します。 $$ ■（n）= n ^ {5/3} + n ^ {1/3} s（n ^ {2/3}）、 $$ その結果、同じ引数は、 $ s（n）= o（n ^ {5/3}）$ 、spe span class="math-container"であることを示しています$ t（n）= n ^ 2 + o（n ^ {5/3}）$ 。同様に、 $ t（n）= n ^ 2 + n ^ {5/3} + o（n ^ {10/9}）$ など。