使用平滑规则求解递归关系
Solving a recurrence relation using Smoothness Rule
考虑这个递归关系：x(n) = x(n/2) + n，对于 n > 1 和 x(1) = 0。
现在这里反向替换的方法将争取 n 的值而不是 2 的幂，所以这里最著名的是使用平滑规则来解决这类问题，当我们使用平滑规则，我们将求解 n = 2^k（对于 n = 2 的值的幂），我们将得到 x(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) + ...
这将在 n = 1 时停止（即当 i = n 时），在这种情况下
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 的算法分析和设计导论）中提到我们应该在这里使用平滑规则，但是正如你所看到的，我已经通过向后的方法完全解决了它替代方法预计在这里会遇到困难但什么也没有发生！
转换 1 + 2 + 4 + 8 + 16 + ... = 2^(n+1) - 1 为假。
那是因为左边数列的元素个数是log n所以和是2^(log n + 1) - 1，正好是2n - 1.
有 log n 个元素的原因是当 i = log n.
时 n/(2^i) = 1 （系列的最后一个元素是 1）
考虑这个递归关系：x(n) = x(n/2) + n，对于 n > 1 和 x(1) = 0。
现在这里反向替换的方法将争取 n 的值而不是 2 的幂，所以这里最著名的是使用平滑规则来解决这类问题，当我们使用平滑规则，我们将求解 n = 2^k（对于 n = 2 的值的幂），我们将得到 x(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) + ...
这将在 n = 1 时停止（即当 i = n 时），在这种情况下
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 的算法分析和设计导论）中提到我们应该在这里使用平滑规则，但是正如你所看到的，我已经通过向后的方法完全解决了它替代方法预计在这里会遇到困难但什么也没有发生！
转换 1 + 2 + 4 + 8 + 16 + ... = 2^(n+1) - 1 为假。
那是因为左边数列的元素个数是log n所以和是2^(log n + 1) - 1，正好是2n - 1.
有 log n 个元素的原因是当 i = log n.
n/(2^i) = 1 （系列的最后一个元素是 1）