求以下C语言函数的时间复杂度，对O(n²)与O(n³)结论存疑

首先看给出的代码：

void func(int n)
{
    int sum=0;
    for (int i=1;i<=n;i++)
    {
        for (int j=1;j<=i*i;j+=i)
        {
            sum+=i;
        }
    }
}

正确的时间复杂度推导 #

你的分析是正确的，该函数的时间复杂度为O(n²)，推导过程如下：

• 外层循环：i从1到n，共执行n次。
• 内层循环：对于每个固定的i，j的起始值为1，每次步长为i，终止条件是j <= i²。计算迭代次数：
  满足条件的j取值为1, 1+i, 1+2i, ..., 1+(k-1)i，其中最后一项需满足1+(k-1)i <= i²。
  解不等式得：(k-1)i <= i² -1 → k-1 <= i - 1/i，由于k是整数，k-1最大为i-1，因此k=i。即内层循环每次执行i次。
• 总迭代次数为所有内层循环次数之和：1 + 2 + 3 + ... + n = n(n+1)/2，该表达式的最高次项为n²，因此渐近时间复杂度为O(n²)。

Google Bard的错误原因 #

Bard的分析存在核心错误：它错误地认为内层循环的迭代次数是i²次，进而错误推导总次数为n*(1+2+3+…+n)，得出O(n³)的结论。但实际上内层循环的步长是i，而非1，因此迭代次数不是i²，而是i次，总次数是等差数列求和，而非更高阶的计算。

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