以替换方法选择常量方法$ t（n）= 5t（n / 4）+ n ^ 2 $

Question

我想到了一个反复关系的解决方案，但我不确定常数应该是什么应该是持续的措施。

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

猜测： $ t（n）= o（n ^ 2）$

p>证明： $ 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}右）+ n ^ 2= 5 ^ 2t \ left（\ frac {n} {4 ^ 2} \右）+ \左（\ frac {5} {16} +1右）n ^ 2= \\= 5 ^ 3t \ left（\ frac {n} {4 ^ 3} \右）+ \左（\左（\ frac {5} {16} \右）^ 2 + \ frac {5} {16} +1 \右）n ^ 2= cdots= \\ = 5 ^ kt \ left（\ frac {n} {4 ^ k}右）+ \左（\ frac {5} {16} \右）^ {k-1} + \ cdots + \ frac{5} {16} +1 \右）n ^ 2 $$ 如果您对 $ t（1）$ 具有一些初始条件，我们假设 $ n= 4 ^ k \ leftrightarrow k=\ log_ {4} n $ ，然后我们获得 $$ t（n）= 5 ^ kt（1）+ n ^ 2 \ frac {16} {11}左（左（\ frac {5} {16} \右）^ {k-1} \右）\在o（n ^ 2）$$