Big O 嵌套 for 循环问题

Question

 public static void main(String[] args) {
        int count = 0;
        int n = 20;
        for (int i = 0; i < n; i++) {
            for (int j = i; j > 0; j--) {
                count++;
            }
        }
        System.out.println(count);
    }

以上是一个简单的嵌套 for 循环的代码，我和我的同事对它的大 O 有疑问。

正如我所见，每个 for 循环都是 o(n)，而 o(n)*o(n) 使 o(n^2)。然而，由于第二个 for 循环从第一个循环开始 i 并且不执行例如 J 为 0 时的第一个循环，因此存在问题。我认为这不会影响它作为两组第一个循环的数据 n-i 和第二个循环的 j-i 仍在遍历。任何清晰度将不胜感激。

Answer 1

任何时候你有两个嵌套循环，你必须假设绝对最坏的情况（即循环执行 n 次）。所以这里的大 O 表示法是 O(n^2).

Answer 2

外循环将运行正好 n 次，而内循环取决于 i 的值。但基本上，它正在执行 0, 1, ..., n-1 循环，总共 (0 + n-1) * (n) / 2 = (n^2 - n) / 2 即 O(n^2)

Answer 3

外层循环运行n次。对于外层循环的每次迭代，内层循环运行不同的次数，先是0，然后是1, 2, ...n-1, n, which = Summation from 0 to n = n(n+1)/ 2 ~= n^2/2 即 O(n^2)

见http://en.wikipedia.org/wiki/1_%2B_2_%2B_3_%2B_4_%2B_%E2%8B%AF

Big O 嵌套 for 循环问题

Big O Nested for Loop issue

java

big-o