algorithm - 使用平滑规则求解递归关系

Question

考虑这个递归关系：x(n) = x(n/2) + n,n > 1和x(1) = 0。现在，这里的反向代换方法会为 的非幂的
值而斗争，所以这里最出名的是使用平滑规则来解决这类问题，当我们使用平滑规则时，我们将在哪里求解(对于n = 值 2) 的幂，我们将得到 的解。 但是，如果我们使用反向代入的方法，这个递推关系就会有解！ 当 n = 1（即当 i = n 时）时，模式 将停止，在这种情况下 ，这是两个不同的答案！n2n = 2^kx(n) = 2n - 1

x(n) = x(n/2) + n = x(n/4) + n/2 + n = x(n/8) + n/4 + n/2 + n = x(n/16) + n/8 + n/4 + n/2 + n = ....

x(n) = x(n/i) + n/(i/2) + n/(i/4) + n/(i/8) + n/(i/16) + ...

x(n) = x(n/n) + n/(n/2) + n/(n/4) + n/(n/8) + n/(n/16) + ... = 1 + 2 + 4 + 8 + 16 + ... = 2^(n+1) - 1

所以请我在这里很困惑，因为在教科书（Anany Levitin 的算法分析与设计简介）中提到我们应该在这里使用平滑规则，但正如你所看到的，我已经通过向后的方法完全解决了它替换方法在这里预计会遇到困难，但没有发生任何事情！

标签： algorithmrecursiondiscrete-mathematicsrecurrence

Answer 1

过渡1 + 2 + 4 + 8 + 16 + ... = 2^(n+1) - 1是错误的。
那是因为左边系列中的元素数量是log n这样的总和2^(log n + 1) - 1，这正是2n - 1。
有log n元素的原因是n/(2^i) = 1（系列的最后一个元素是 1）when i = log n。