为什么这个o(n)的运行时间是这样的？

Question

大家好，在课堂上我们回顾了 Java 的这一点，并被告知要找到运行时。

for(int i=0; i<N; i=i+2){
            for(int j=N; j<N j++){
                for(int k=0; k<N k++){
                    System.out.println(i*j);
                    System.out.println(i);
                }
            }
        }

        for(int k=0; k<100; k++){
        System.out.println(k);
        }

显然这个的运行时间是o(n)，但我不知道为什么。由于 for 循环，这不是 o(n^3) 吗？有什么提示或技巧可以立即告诉我缺少什么运行时吗？

谢谢！

Answer 1

对于给定的代码，您应该具有以下时间复杂度：

T(n) = 1 + N/2 (1 + 2) + 1 + 1 + 1 + 100 (1 + 2) ≈ N/2

这意味着您的整体复杂性是

O(n)

。因为第二个

for

循环（第一个嵌套

for

循环）永远不会执行，由于其条件，您没有

O(n^3)

复杂性。如果第二个

for

循环被写成

for(int j=0; j< N; j++)

，那么你就会有

O(n^3)

的复杂性。