以下函数的时间复杂度是多少

Question

计算时间复杂度：

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^2)，因为外循环运行 n 次，内循环对于每个 i 值大约运行 i 次，这意味着内循环将运行 1+2+3+.. .+n 次，也就是 O(n^2)，但是 Google Bard 说复杂度是 O(n^3)，因为嵌套对时间复杂度有乘法效应，意味着实际的迭代量是

n*(1+2+3+...+n) ，即 O(n^3)

但这怎么可能呢？

Answer 1

您的计算是正确的 - 是

O(n^2)

。内部循环的步长为

i

，因此它将运行 ~

i*i/i

迭代，也为内部循环提供

O(n)

。