我真的很困惑如何简化这个递推关系:c(n) = c(n/2) + n^2。
所以我首先得到:
c(n/2) = c(n/4) + n^2 所以 c(n) = c(n/4) + n^2 + n^2 c(n) = c(n/4) + 2n^2
c(n/4) = c(n/8) + n^2 所以 c(n) = c(n/8) + 3n^2
不过我确实注意到了一种模式:
2 乘以 "n^2"前面的任何系数的幂给出 n 结束的分母。
我不确定这是否有帮助。
我只是不明白如何简化这个递归关系，然后找到它的 theta 符号。
编辑:实际上我只是再次计算出来，我得到了 c(n) = c(n/n) + n^2*lgn。
我认为这是正确的，但我不确定。另外，我如何找到它的 theta 符号？它只是 theta(n^2lgn) 吗？
最佳答案
首先，在放置c(n/2) 在 lhs 上。
即
c(n/2) = c(n/4) + (n/2)^2
您的直觉是正确的，因为它是问题中非常重要的部分。在我们达到 1 之前，您可以将 n 除以 2 多少次？
我们以8为例
8/2 = 4
4/2 = 2
2/2 = 1
你看到它是 3，结果是 log(8)
为了证明 theta 符号，查看 master theorem 可能会有所帮助.这是证明递归关系复杂性的非常有用的工具。
利用主定理案例3，我们可以看到
a = 1
b = 2
logb(a) = 0
c = 2
n^2 = Omega(n^2)
k = 9/10
(n/2)^2 < k*n^2
c(n) = Theta(n^2)
为什么答案是 Theta(n^2) 的直觉是你有 n^2 + (n^2)/4 + (n^2)/16 + ... + (n^2)/2^(2n)，这不会给我们 logn n^2，而是越来越多更小的n^2
关于math - 简化递推关系 c(n) = c(n/2) + n^2，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/22674053/