关于生成n位二进制字符串递归算法时间复杂度的疑问

你的理解完全正确，下面具体分析两段代码的时间复杂度差异：

一、原代码的时间复杂度分析 #

原代码中，bitStrings(n)在n>1时会两次调用bitStrings(n-1)，这导致每个子问题bitStrings(k)都被重复计算2^(n-k)次，完全没有复用子问题的计算结果。

原书中给出的递归式T(n)=2T(n-1)+d是错误的——这个式子仅适用于子问题被调用一次的场景，而这里子问题被调用了两次，且每次处理的开销并非常数d：

• 每次调用appendAtFront(x, L)需要遍历长度为2^(n-1)的列表L，对每个元素执行字符串拼接操作；
• 两次appendAtFront加上列表拼接的总开销为O(2^n)。

通过递归树分析可以看到，每一层的总计算量都是O(2^{n)，累计n层后，总时间复杂度为**O(n·2}n)**。

二、优化后代码的时间复杂度分析 #

优化后的代码通过将bitStrings(n-1)的结果存入变量A并复用，彻底避免了子问题的重复计算，此时正确的递归式为：
T(n) = T(n-1) + O(2^n)

• T(n-1)是计算一次子问题的开销；
• 两次appendAtFront处理长度为2^{(n-1)的列表`A`，加上列表拼接的总开销为O(2}n)。

展开该递归式可得：
T(n) = T(1) + sum_{k=2}^n O(2^k) = O(2^n)
这完全符合你对优化后代码时间复杂度为O(2^n)的判断。

原代码（存在重复计算） #

def appendAtFront(x, L):
   return [x + element for element in L]

def bitStrings(n):
   if n == 0: return []
   if n == 1: return ["0", "1"]
   else:
     return (appendAtFront("0", bitStrings(n-1)) + appendAtFront("1", bitStrings(n-1)))

print(bitStrings(4))

优化后代码（复用子问题结果） #

def appendAtFront(x, L):
   return [x + element for element in L]

def bitStrings(n):
   if n == 0: return []
   if n == 1: return ["0", "1"]
   else:
     A=bitStrings(n-1)
     return (appendAtFront("0", A) + appendAtFront("1", A))

print(bitStrings(4))

内容的提问来源于stack exchange，提问作者Arun