递归 T(n) = 2T(n-1) + 1 给出的递归算法的时间复杂度是多少

Question

我对此完全陌生，所以一步一步来会很有帮助，谢谢。

Answer 1

首先，您可以从 iteration method 开始了解其行为方式。

T(n) = 2T(n-1) + 1 = 
     = 2*(2T(n-2) + 1) + 1 = 4T(n-2) + 3
     = 4(2T(n-3) + 1) + 3 = 8T(n-3) + 7
     = 8*(2T(n-4) + 1) + 7 = 16T(n-4) + 15
     = 16*(2T(n-5) + 1) + 15 = 32T(n-5) + 31

现在，我们了解了行为，我们可以告诉

T(n) = 2^i * T(n-i) + (2^i - 1)

现在，我们需要使用基本子句（问题中没有给出），并提取i=n。例如，如果 T(0) = 0:

T(n) = 2^n * T(0) + (2^n - 1) = 2^n - 1

这是在O(2^n)计算渐近复杂度的时候

注意： 迭代法很好并且易于遵循 - 但它不是正式证明。要正式证明复杂性，您将需要另一个工具，例如归纳法。

递归 T(n) = 2T(n-1) + 1 给出的递归算法的时间复杂度是多少

What is the time complexity of a recursive algorithm given by the recurrence T(n) = 2T(n-1) + 1

big-o

time-complexity