java - 3个嵌套循环的运行时间

Question

我很困惑这个算法的运行时间是 O(n^2) 还是 O(n^3)。该程序如下所示:

int count=0;

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

System.out.print("count: " + count);

我使用了 n=7 的例子。这给了我 35 的结果(计数)。我知道i和j循环一起有高斯和的运行时间，就是1+2+3...n=O(n^2)。我试图通过一些计算来计算出所有 3 个循环的完整运行时间。 我使用了给出的高斯和公式:

我发现做高斯求和并将它们相加得到了正确的结果。(从 i=2 到 i=n-1)公式 I必须是:

如何删除求和符号并获得常规“公式”？

感谢您的宝贵时间!

Answer 1

From Wikipedia ，强调我的:

Big O notation is a mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity.

考虑当 n 接近无穷大时会发生什么:您正在对 n - 2 个元素求和。随着 n 接近无穷大，-2 将变成无用的小项，因此您可以忽略*它并乘以 n。

(* 你没有正确地忽略它，但存在一个常量 k 这样你的外循环/求和将运行少于 kn 次，这意味着它仍然属于 O(n)。)

按照类似的逻辑，您求和的表达式属于 O(n²)，因为尽管有 i，您求和的项将严格小于kn² 表示 k 的某个常数值。 i 可能在 2 和 n - 1 之间变化，但这对 (n - i)((n - i) + 1) 没有任何影响/2 随着 n 接近无穷大的趋势；对于 k 的某个常数值，它仍然增长小于 kn²，因此该函数仍在 O(n²) 中。

因为您要对O(n²) 阶的O(n) 值求和，所以您的函数在O(n³) 整体。