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

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)=T(n)+2 T(n/4) 并且我已经使用主定理计算了它的复杂度上） 但我不知道如何使用反向替换来找到它的复杂性

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).

中