带递减参数的递归函数的时间复杂度分析

给定递归函数 #

int func (int n, int m)
{
    if (n<1)
        return n;
    else if (n<10)
        return func(n-m, m);
    else
        return func(n-1, m);
}

1. 大O表示法结果 #

这个函数的时间复杂度是 O(n)。

2. 复杂度计算过程 #

我们分阶段拆解递归流程：

• 当 n >= 10 时，每次递归调用都会让 n 减1，直到 n 降到9。这个阶段需要执行 n - 9 次递归，次数和n线性相关。
• 当 n < 10 时，每次递归让n减m，直到n < 1。这个阶段的递归次数最多是9次（比如m=1时），属于常数级操作，不会影响整体复杂度的主导项。

把两个阶段合起来看，整个递归的总次数由n >=10阶段的线性操作主导，常数项可以忽略，所以最终时间复杂度是O(n)。

3. 递归复杂度分析的通用规则 #

• 递归树法：把递归调用展开成树状结构，计算每一层的操作次数再求和。适合分支不多的递归，比如这个单分支递归，直接数路径长度即可。
• 主定理：针对形如 T(n) = a*T(n/b) + f(n) 的递归式，直接套用公式判断复杂度。但这个函数不符合主定理的标准形式，无法直接使用。
• 递推关系式法：写出复杂度的递推公式，一步步展开求解。比如这个函数可以写成：
  • 当n >=10时，T(n) = T(n-1) + 1
  • 当1<=n<10时，T(n) = T(n-m) +1（直到n<1）
    展开后能直接看到T(n)和n是线性关系。
• 常数操作忽略原则：递归中如果某阶段的操作次数是固定常数，不管数值多大，都不会影响整体的复杂度阶数，只看主导的增长项。

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