java - (n^2) 的大 O 表示法

Question

示例 1

for (int i = 0; i < n; i++) {
  for (int j = 0; j < n; j++) {
        System.out.println(count++);
   }
}

示例 2

for (int i = 0; i < n * n; i++) {            
     System.out.println(count++);
} 

这两个例子都给了我一个大 O (n^2)。但是哪个ans最好？

Answer 1

要找到最好的代码，最好编译它并使用javap -c ClassName.class来查看这两种方法生成的字节码。我foo对前者使用方法，bar对后者使用方法。

public static void foo(int n) {
    int count = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            System.out.println(count++);
        }
    }
}

public static void bar(int n) {
    int count = 0;
    for (int i = 0; i < n * n; i++) {
        System.out.println(count++);
    }
}

这些是结果：

public static void foo(int);
    Code:
       0: iconst_0      
       1: istore_1      
       2: iconst_0      
       3: istore_2      
       4: iload_2       
       5: iload_0       
       6: if_icmpge     38
       9: iconst_0      
      10: istore_3      
      11: iload_3       
      12: iload_0       
      13: if_icmpge     32
      16: getstatic     #2       // Field java/lang/System.out:Ljava/io/PrintStream;
      19: iload_1       
      20: iinc          1, 1
      23: invokevirtual #3       // Method java/io/PrintStream.println:(I)V
      26: iinc          3, 1
      29: goto          11
      32: iinc          2, 1
      35: goto          4
      38: return        

public static void bar(int);
    Code:
       0: iconst_0      
       1: istore_1      
       2: iconst_0      
       3: istore_2      
       4: iload_2       
       5: iload_0       
       6: iload_0       
       7: imul          
       8: if_icmpge     27
      11: getstatic     #2       // Field java/lang/System.out:Ljava/io/PrintStream;
      14: iload_1       
      15: iinc          1, 1
      18: invokevirtual #3       // Method java/io/PrintStream.println:(I)V
      21: iinc          2, 1
      24: goto          4
      27: return        

最后，由于进行的操作较少，后者的实现似乎比前者更好。

我不是这方面的专家，所以如果有人可以编辑/执行更好的分析，请随意。我写了这个答案，因为它不适合单个评论。

Answer 2

两个循环只是相同的。没有最好的。但是如果Nvalue 很大，那么N*Nvalue 会溢出，你需要回到两个 for 循环。因此，您可以根据自己的N价值使用它。

Answer 3

当你说得最好时，在编程意义上，有两种定义方式，在内存和性能方面（通常是迭代）。

就内存而言，第二个是最好的，因为只使用了 2 个变量（i 和 n）。除此之外，每次迭代只发生一次变量分配（i++ => i = i+1）。而在第一个 i++ 和 j++ 中，每次迭代都会发生两次分配操作。由于在高处理操作中重新分配变量也需要相当多的时间，所以第二个是最好的。

在迭代方面，两者是相同的。