嵌套循环上界时间复杂度是否为O(n²)及对应函数计算问题

核心结论 #

• 该代码的时间复杂度确实为O(n²)
• 你猜测的n!·n+C的时间复杂度函数完全错误，该逻辑不存在阶乘相关的运算特征

推导过程 #

我们直接统计核心操作count++的总执行次数即可得到精确的时间复杂度函数：

1. 外层循环的i取值依次为n、n-1、n-2……1，共执行n轮
2. 每轮外层循环中，内层循环j从当前i的取值遍历到1，执行次数等于当前i的值
   总执行次数就是首项为1、末项为n的等差数列求和：

n + (n-1) + (n-2) + ... + 1 = n(n+1)/2 = 0.5n² + 0.5n
根据大O上界的定义，忽略低次项和常数系数后，时间复杂度为O(n²)。

误区说明 #

阶乘n!对应连续正整数的乘积逻辑，只有当内层循环的执行次数随外层迭代呈现倍增、或者存在累乘类操作时才有可能出现阶乘级复杂度。这段代码的内层循环只是随外层迭代逐次减少1次执行次数，全程都是求和逻辑，完全没有阶乘的运算特征，因此不会出现阶乘相关的复杂度项。

对应代码 #

for(int i=n;i>0;i--)
{
 for(int j=i;j>=1;j--)
  {
     count++;
  }
}

内容的提问来源于stack exchange，提问作者Syed Zainullah Qazi