带两个for循环的递归算法时间复杂度分析

你需要计算时间复杂度的C语言实现代码如下：

int fonksiyon(int n) 
{
    if (n < 2)
    {
        return 1;
    }
    else
    {
        int a = 0;
        for (int i = 0; i <= n; i++)
        {
            a = a + fonksiyon(n / 2);
        }
        for (int i = 0; i <= n; i++)
        {
            for (int j = 0; j <= n; j++)
            {
                a = a + 1;
            }
        }
        return a;
    }
}

你提到想用主定理求解，但顾虑两个for循环结构的影响——这里先明确：基础版主定理无法直接套用在这段代码上。基础主定理仅支持形如T(n) = aT(n/b) + f(n)（其中a、b为大于0的常数）的递推关系，而这段代码第一个for循环会产生n+1次递归调用，子问题个数随输入规模n线性增长，不满足基础主定理的常数a要求。

这段代码的时间复杂度为 2^{Θ((log n)²)}（等价写法为n^{Θ(log n)}），属于准多项式复杂度，增长速度快于任意固定阶的多项式复杂度，慢于指数复杂度。

• 第一步：写出准确的递推关系
  渐近分析中可以忽略循环边界的+1常数项（i从0到n共n+1次循环，和n次循环的渐近阶完全一致），所有常数时间操作统一记为O(1)，可得递推式：

  递归边界：当n < 2时，T(n) = O(1)，直接返回结果，无额外开销
  递归递推：当n ≥ 2时，T(n) = n·T(n/2) + Θ(n²)
  递推式两项分别对应代码的两部分开销：

  • n·T(n/2)：第一个for循环共执行n轮，每轮调用1次参数为n/2的递归函数，总递归开销为n倍的子问题时间（代码无记忆化缓存，每次调用都会独立执行）
  • Θ(n²)：第二个双层for循环共执行n²轮常数级加法操作，非递归开销为平方级
• 第二步：逐层展开递推式找规律
  从顶层开始逐层代入子问题的递推关系：
  1. 顶层（问题规模n）：T(n) = n·T(n/2) + n²
  2. 第一层子问题（规模n/2）：代入T(n/2) = (n/2)·T(n/4) + (n/2)²，可得 T(n) = n·(n/2)·T(n/4) + n²/2 + n²
  3. 第二层子问题（规模n/4）：代入T(n/4) = (n/4)·T(n/8) + (n/4)²，可得 T(n) = n·(n/2)·(n/4)·T(n/8) + n²/4 + n²/2 + n²
     以此类推，当递归到第k层时，子问题规模为n/2^k < 2，满足递归终止条件，此时k = ⌊log₂n⌋，T(n/2^k) = O(1)。
• 第三步：分别计算两部分总开销
  1. 非递归部分（所有层的双层循环开销）：总和为n² + n²/2 + n²/4 + ... + n²/2^{k-1}，这是公比为1/2的等比数列，求和结果恒小于2n²，量级为Θ(n²)。
  2. 递归终止部分：递归项的系数是各层子问题调用次数的乘积，即n * (n/2) * (n/4) * ... * (n/2^{k-1}) = n^k / 2^{{0+1+2+...+(k-1)}。代入k=log₂n、n=2}k化简，可得这部分的量级为2^{(k² +k)/2} = 2^{Θ((log n)²)}。
• 第四步：确定主导项
  对比两部分开销的增长速度：2^{Θ((log n)²)}的增长速度远快于多项式级的Θ(n²)，是整个算法时间开销的主导项，因此最终时间复杂度由递归部分决定。

如果熟悉推广版本的主定理（支持子问题个数为规模函数的形式），也可以通过推广版主定理直接得到一致结果，但对不熟悉变种主定理的场景，直接展开递推式找规律的方法容错率更高。

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