algorithm - 具有恒定组合时间的递归算法的时间界限

Question

假设我有一个递归算法，它将输入分成 2 个大小为 n-1 的输入并递归求解它们。它在一个恒定的时间内组合结果，比如 c。

所以为此制定一个方程，

T(n) = 2T(n-1) + c

为了找到这个的复杂性，我使用了递归树的方法。由于输入在每一步都被分成 2，因此每一步节点的数量都会得到平方，而由于只有一个元素被消除，每一级将只从列表中丢失一个元素。

所以我认为这个问题的复杂度应该是Θ(n ² )

我在这个思考过程中是否正确。如果没有，我做错了什么？

谢谢你。

Answer 1

每个步骤的节点数不会平方。相反，它在每个级别都翻倍。例如，节点数

• 问题大小 n：1
• 问题大小 n - 1: 2
• 问题大小 n - 2: 4
• 问题大小 n - 3: 8
• 问题大小 n - 4: 16
• ...
• 问题大小 n - i: 2 ⁱ

结果，递归树中的节点总数将为 1 + 2 + 4 + 8 + ... + 2 ⁿ = 2 ⁿ⁺¹ - 1。因此，完成的工作将是 c2 ⁿ⁺¹ - c ，即 Θ(2 ⁿ )。这是指数时间，而不是二次时间。

希望这可以帮助！

Answer 2

复杂性实际上是指数级的：Omega(2^n).

让我们用数学归纳法来证明它。为简单起见 - 假设c=1

Claim: T(n) >= 2^n
Base: T(0) = 1 (Let's take it as assumption)
Assume the claim is true for each k<n and using it let's prove:
T(n) = 2*T(n-1) + 1 >= 2*2^(n-1) + 1 = 2^n + 1 > 2^n

现在，总结一下，让我们展示它也是O(2^n)，我们将得出结论Theta(2^n)：

Claim: T(n) <= 2*2^n - 1
Base: T(0) = 1 = 2 -1 
Assume the claim is true for each k<n and using it let's prove:
T(n) = 2*T(n-1) + 1 <= 2 * (2*2^(n-1) -1 ) + 1 = 2*2^n -2 + 1 = 2*2^n -1 

如您所见，我们实际上得到了准确2*2^n-1的结果（在上面的证明中，<= 可以很容易地替换为 =），这符合 @templatetypedef 所示的内容

Answer 3

从 T(n+1)=2T(n)+c 我们有：

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

这会产生 Θ(2^n) 复杂度。