递归式T(n)=2T(n)的时间复杂度求解及相关疑问咨询

嘿，这个递归式确实有点反直觉——毕竟我们平时接触的递归都是把问题拆得越来越小，比如 $T(n)=2T(n/2)+n$ 这类，而这个居然完全不缩小问题规模！咱们一步一步来拆解它。

首先，先试着展开这个递归式，看看规律：

• 第1次展开：$T(n) = 2T(n) = 2 \times 2T(n) = 2^2T(n)$
• 第2次展开：$T(n) = 2^2T(n) = 2^3T(n)$
• ...
• 第k次展开：$T(n) = 2^k T(n)$

你会发现，不管展开多少次，式子右边始终带着 $T(n)$，根本没有向终止条件靠近的迹象。这时候我们得结合递归的终止条件来分析：

情况1：没有明确的终止条件 #

如果这个递归式没有任何终止条件（也就是对于所有n，都遵循 $T(n)=2T(n)$），那它会无限递归下去——每一次调用都会触发新的调用，永远不会返回结果。这种情况下，时间复杂度就是无限大，或者说没有有效的时间复杂度定义，因为程序会一直运行直到栈溢出或者系统资源耗尽。

情况2：存在特殊终止条件 #

假设我们给它加一个终止条件，比如当 $n = c$（某个固定常数，比如n=1）时，$T(c) = C$（常数时间）。但问题在于，原递归式是针对所有 $n \neq c$ 的情况吗？如果输入的n不等于c，那递归还是会无限调用自己，因为每次调用的参数都是n，永远触达不到终止条件。只有当输入恰好是c时，才会在常数时间内返回，这种极端情况没有普遍意义。

举个实际代码的例子，如果你写出这样的函数：

def compute_T(n):
    if n == 1:
        return 1
    return 2 * compute_T(n)

当你传入n=2时，函数会一直调用compute_T(2)，直到栈溢出报错，根本不会停止。

总结 #

这个递归式的核心问题是没有缩小问题规模的逻辑——常规递归通过分解子问题来减少计算量、触发终止条件，但它每次调用的问题规模和原问题完全一致，所以除非输入恰好命中终止条件，否则程序永远无法终止，时间复杂度也就不存在有效的有限值。

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