代替方法の最後のステップの定数を選択する$ t（n）= 5t（n / 4）+ n ^ 2 $

Question

私は再発関係の解決策を考え出したが、最後のステップを保持するための定数が何であるべきかわからない。

$ t（n）= 5t（n / 4）+ n ^ 2 $

推測： $ t（n）= O（n ^ 2）$

証明： $ t（n）\ leq cn ^ 2 $

故障

$ t（n）\ Leq 5（C（n / 4）^ 2）+ n ^ 2 $

$=（5/16）cn ^ 2 + n ^ 2 $

$ \ leq cn ^ 2 $

最後のステップを保持するために、Cの値がどのようなものであるべきかわからない（5/16）。私の推測はC>= 1になり、それが保持するかどうかはかなりわからない。

Answer 1

あなたの定数 $ c $ を満たす必要がある $$ \ frac {5} {16} C n ^ 2 + N ^ 2 \ LEQ C N ^ 2、$$ あれは、 $$ \ frac {5} {16} C + 1 \ LEQ C。$$ うまくいけば、この不等式が満たされる定数 $ c $ のセットを決定できます。

Answer 2

$$ t（n）= 5t \ left（\ frac {n} {4} \ right）+ n ^ 2= 5 ^ 2t \ left（\ frac {n{4 ^ 2} \ right）+ \ left（\ frac {5} {16} +1 \ right）n ^ 2= \\= 5 ^ 3T \ left（\ frac {n} {4 ^ 3} \右）+ \ left（\ left）{16} \ righ {5} {5} {5} {16} + 1 \ right）n ^ 2=cdots= \\ = 5 ^ kt \ left（\ frac {n} {4 ^ k} \ right）+ \ left（\ left \ frac {5} {16} \ right）^ {K-1} + \ cdots + \ frac{5} {16} + 1 \ right）n ^ 2 $$ $ t（1）$ の初期条件がある場合は、 $ n= 4 ^ k \ LeftrightArrow k=\ log_ {4} n $ 、それから我々は取得します $$ t（n）= 5 ^ kt（1）+ n ^ 2 \ frac {16} {11} \左（1- \ left（\ frac {5} {16\ right）^ {k-1} \ right）\ in（n ^ 2）$$