使用反向替换计算算法的复杂度

Question

我的职责是：

int ps (int n) 
{ if (n == 1) return 1; 
 else return (Extra(n) + Ps (n/4) + Ps (n/4)); } 

额外(N)是O(n)

我试图找出这个函数的T(n) =T(N)+2T(n/4)，我用主定理计算了它的复杂性，它是O(n)，但我不知道如何用反替换来求它的复杂性。

Answer 1

首先，你在复杂性方面是错误的。在编写时间复杂性时，您没有提到Extra(n)。那么，T(n) = 2 T(n/4) + n.现在，我认为新的重复复杂性术语很容易通过替换来解决：

T(n) = 2T(n/4) + n = 2 (2 T(n/8) + n/4) + n = 2^2 T(n/8) + n/2 + n =
2^2 (2 T(n/16) + n/8) + n/2 + n = 2^3 T(n/16) + n/4 + n/2 + n

现在，通过数学归纳法，如果我们假设n = 2^k，您可以发现：

T(n) = n + n/2 + n/4 + n/8 + ... + n/2^k = n (1 + 1/2 + 1/4 + ... + 1/2^k) <= 2n

以上分析的最后一部分来自于带因子1/2的和的存在几何级数。因此，T(n)在Theta(n)和O(n)中。