n 배의 함수가있는 재발 ()

Question

마스터 방법은 $ t (n)= kt (an) + cn $ 과 같은 문제에 잘 작동하지만 문제는 $$ T (n)= n ^ {\ frac {1} {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 {정렬} 이는 $ 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} {n ^ {1/3}} \ 권리), $$ $ CN ^ 2 $ $ C> 1 $ 및 충분히 큰 $ n $ ( $ c $ 에 따라 다름).

실제로 $ s (n)= t (n) - n ^ 2 $ , 우리는 $$ s (n)= n ^ {5/3} + n ^ {1/3} s (n ^ {2/3}), $$ 그래서 동일한 인수는 $ s (n)= o (n ^ {5/3}) $ 및 $ t (n)= n ^ 2 + o (n ^ {5/3}) $ . 같은 방식으로 $ T (n)= n ^ 2 + n ^ {5/3} + o (n ^ {10/9}) $ 등등.