递归函数时间复杂度解惑：为何两例分属O(n)与O(n²)？

开发者阿泽

2026-6-18

递归函数时间复杂度差异解析：O(n) vs O(n²)

核心差异：每次递归的额外操作耗时不同

两个递归函数结构看似一致，但时间复杂度差距极大，本质是每次递归调用中，除递归本身外的操作，时间复杂度完全不同。

示例1：时间复杂度O(n)

先看代码：

function compute_polynomial_recursive(x, n):
    if n == 1:
        return x 
    else:
        return (x[n]^3) + compute_polynomial_recursive(x, n - 1)

分析：

这里的额外操作是x[n]^3：

x[n]是数组随机访问，属于常数时间O(1)；
立方运算（^3）是固定次数的乘法，同样是O(1)。

递归时间复杂度的递推式为：
T(n) = T(n-1) + O(1)

展开递推式：

T(n) = T(n-1) + O(1)
     = T(n-2) + O(1) + O(1)
     = ...
     = T(1) + (n-1)*O(1)

最终结果为O(n)，和老师给出的结论一致。

示例2：时间复杂度O(n²)

再看代码：

function compute_polynomial_recursive(a, n):
    if n == 1:
        return a^1 
    else:
        return (a^n) + compute_polynomial_recursive(a, n - 1)

分析：

这里的关键操作是a^n：
如果是朴素的幂运算实现（比如通过循环n次、每次乘以a来计算a的n次方），这个操作的时间复杂度是O(n)（此处n为当前递归层的参数值）。

递推式变为：
T(n) = T(n-1) + O(n)

展开递推式：

T(n) = T(n-1) + O(n)
     = T(n-2) + O(n-1) + O(n)
     = ...
     = T(1) + O(2) + O(3) + ... + O(n)

求和后总操作次数为(n+1)*n/2，属于二次函数量级，因此时间复杂度是O(n²)。

数学归纳法验证

我们可以用数学归纳法证明示例2的时间复杂度确实是O(n²)：

基础情况：当n=1时，T(1)=O(1)，符合O(1²)=O(1)；
归纳假设：假设对于任意k≥1，T(k)=O(k²)；
归纳步骤：当n=k+1时，
```
T(k+1) = T(k) + O(k+1)
```
根据假设，T(k)=O(k²)，而O(k+1)=O(k)，所以O(k²)+O(k)=O(k²)，又因为(k+1)² = k²+2k+1与k²同阶，因此T(k+1)=O((k+1)²)。
归纳成立。