algorithm - for循环的复杂度

Question

这是我在网上找到的:

for (i=1; i<=n*n; i++)
    for (j=0; j<i; j++)
        sum++;

执行 sum++ 的确切次数:

Sum{i=1, i=n^2}= (n^2)*((n^2)+1)/2 ∈ Θ(n^4)

报价结束。

虽然我同意这个结果，但在我看来这只考虑了第一个循环，即 i 上的循环，而不是 j 上的循环。换句话说，从数学上讲，我们会得到与代码相同的结果:

for (i=1; i<=n*n; i++)
    sum++;

即，仍然:Sum{i=1, i=n^2}= (n^2)*((n^2)+1)/2 ∈ Θ(n^4) 而这段代码显然是 Θ(n^2)(正好运行 n^2 次)

有人能解释一下我错过了什么吗？

Answer 1

假设在递增值的同时执行了恒定数量的操作 c。