具有恒定组合时间的递归算法的时间限制

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 ^{n + 1} - 1.因此,完成的工作将为c2 ^{n + 1} - c ,即Θ(2 ⁿ).这是指数时间,而不是二次时间.

希望这可以帮助!