使用重复展开计算递归
Calculate the recurrence use repeated unfolding
我正在尝试计算 T (n) = 2 T (n/2) + n (log n)^2。
按照我得到的步骤：
=2^kT(n/2^k)+ nlog2 (n/2^(k-1))+ nlog2 (n/2^(k-2))+…+ n(log (n/2))^2 + n (log2 n)^2
当 n=2^k 我得到：
但是我不知道如何简化求和公式并得到 Θ() 符号。
任何人都可以帮忙吗？非常感谢
如果你看过Master theorem，你会发现你问的问题实际上是Master Theorem的2nd情况（参考上面的link ).
因此，这里 a=2、b=2 和 f(n) = 0[n^(c_crit)(log n)^k] 其中 k=2 和 c 称为 c_crit = log a to base b = 1.
所以，根据大师定理，T(n) = 0[(n^c_crit)(log k)^(k+1)] = 0[n(log n)^3]
我觉得你的总结不太正确。让我们re-derive吧：
... m 次迭代后。假设停止条件是 n = 1（不失一般性）：
... 我们使用了两个对数规则。如您所见，总和实际上超过了 "free indices" 而不是日志本身。使用以下整数幂和：
...我们得到：
要计算 Θ 符号，最高阶项是：
我正在尝试计算 T (n) = 2 T (n/2) + n (log n)^2。 按照我得到的步骤：
=2^kT(n/2^k)+ nlog2 (n/2^(k-1))+ nlog2 (n/2^(k-2))+…+ n(log (n/2))^2 + n (log2 n)^2
当 n=2^k 我得到：
但是我不知道如何简化求和公式并得到 Θ() 符号。 任何人都可以帮忙吗？非常感谢
如果你看过Master theorem，你会发现你问的问题实际上是Master Theorem的2nd情况（参考上面的link ).
因此，这里 a=2、b=2 和 f(n) = 0[n^(c_crit)(log n)^k] 其中 k=2 和 c 称为 c_crit = log a to base b = 1.
所以，根据大师定理，T(n) = 0[(n^c_crit)(log k)^(k+1)] = 0[n(log n)^3]
我觉得你的总结不太正确。让我们re-derive吧：
... m 次迭代后。假设停止条件是 n = 1（不失一般性）：
... 我们使用了两个对数规则。如您所见，总和实际上超过了 "free indices" 而不是日志本身。使用以下整数幂和：
...我们得到：
要计算 Θ 符号，最高阶项是：