Рецидив с функцией N раз T ()

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 {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 \ левый (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}) $ И так далее.