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ⁿ)。这是指数时间，而不是二次时间。

希望这对您有所帮助!