多重循环的时间复杂度（Big O）

Question

    count++;
    count++;
    count++;
    for (int i = 0; i < n; i++)
    {
        for(int j = 0; j < i*i; j++)
        {
            for (int k = 0; k < j; k++)
            {
                count++;
                sum++;
            }
        }
    }
    count++;
    return count;
}

尝试获取此代码的大O时间复杂度。难以理解循环之间的交互方式。运行时，得到n = 25 count = 898960。我已经尝试了从O(n)^5+9到O(n)^5/n的所有可能。

所有其他此问题的示例都没有处理第二个循环中使用了I（I*I）和第三个循环中使用了j的情况。

- Novabomb

---

我认为是 n 的四次方，但我只是粗略估算了一下，没有检查我的工作。 - markspace

n的4次方是390,625，略大于程序输出的一半。这之间有一个很大的差距，让我认为它不是正确的结果。 - Novabomb

根据“for (int i=0; i<n*n; i++)”，应该改为“O(n^2)”而非“O(n)”。循环条件也很重要。 - Pshemo

这个公式可以完美地被O(n^4logn)所限制。我不确定O(n^4)。 - Compass

Answer 1

几乎总是计算循环复杂度的最佳方法是利用sigma符号表示法。

附言：我在公式中不写必要的+1，因为它对大O符号没有影响，也不会影响最大幂次，其值为5。

- Soner from The Ottoman Empire

---

所以我们最终都理解了！我为什么没有用数学符号表示是因为大多数程序员实际上不会理解 :) - Siavas

@Siavas所说的“大多数程序员实际上不理解它”，意味着他们应该学习。 - Soner from The Ottoman Empire

Answer 2

It looks like it is O(n^5).

for (int i = 0; i < n; i++) // 0 to n -> O(n)
    for(int j = 0; j < i*i; j++) // 0 to n * n -> O(n^2) repeated n times -> O(n^3)
        for (int k = 0; k < j; k++) // 0 to n * n -> O (n^2) repeated O(n^3) times -> O(n^5)

在最好的情况下，三个嵌套循环会给你O(n^3)的时间复杂度，但由于第二个循环重复了(n^2)次，这将使它的复杂度成平方，第三个循环也是如此。因此，简单的数学表达式为：(n) * (n * n) * (n * n) = n^5。

最初的回答：在最理想的情况下，三个嵌套循环的时间复杂度为O(n^3)，但由于第二个循环执行了n^2次，它的复杂度和第三个循环一样都被平方了。所以，用数学表达式表示为：(n) * (n * n) * (n * n) = n^5。

- Siavas

---

问题是我无法使其符合输出的“操作”。O ^ 5变成了“9,765,625”，这是898960的10.86倍。也许我的编码在计数方面有误？ - Novabomb

@Novabomb 我是自学的，所以我可能会错，但让我问你一个反问题。你认为 for(int i=1; i<=n; i++) for (int j=1; j<=i; j++){count++;} 的时间复杂度是多少？在第一次迭代中，它将使 count 增加一次，然后两次，依此类推。因此，它的值将是 1+2+3+..+N，即 N*(a1+aN)/2 = N(1+N)/2 = N/2+N^2/2，但我们仍然说它的复杂度是 O(N^2)，因为结果主要取决于 N^2（对于大的 N 值）。如果我理解正确，O(n) 的目的不是为了精确，而是为了向我们展示其曲线的一般“想法”。 - Pshemo

确切地说，@Pshemo，大学里也是这样教的。大O符号可以给出算法的复杂度，但不一定能反映其实际性能。 - Siavas

@pshemo 我曾经学过这个，但期望结果在一定范围内。结果相差如此之大让我自动怀疑自己。最终我是正确的，只是有些怀疑。 - Novabomb