algorithm - 使用迭代方法解决这种递归关系的步骤是什么？

Question

我对分析算法的时间复杂性相对较新，并且无可救药地陷入了这个问题。

T(n) = 2T(n/2) + Θ(n) ; n>1
T(1) = a

我已经明白使用大师的方法有一个简单的解决方案，但我想知道如何使用迭代方法执行此分析。

标签： algorithmiteration

Answer 1

为简单起见替换theta(n)为n。（要彻底解决这个问题，您必须扩展theta(n)out 的定义以获得该术语的上限和下限，并运行与以下相同的分析 - 在实践中很少看到这样做）。

现在假设这n是 2 的幂：

T(n) = 2T(n/2) + n
     = 4T(n/4) + n + n
     = 8T(n/8) + n + n + n
     = ...
     = 2^kT(n/2^k) + kn

最终，n/2^k 为 1，此时 k 为 log_2(n)。

所以T(n) = nT(1) + log_2(n)*n

这n对 2 的幂有效，但您可以注意到，如果n12 的最大幂小于或等于n，并且n22 的最小幂大于或等于n，那么T(n1) <= T(n) <= T(n2)，您可以结合以下事实：n1 >= n/2,n2 <= 2n以获得所有 n 的 theta(n log n) 边界。

您最常看到的计算或工作与上述相同，但没有说明n必须是 2 的幂，并且完全掩盖了舍入细节。Sedgewick 是一位严格研究这些细节的作者，例如，当他计算在长度为 n 的数组的合并排序中执行的比较的确切数量时。