示例 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最好?
示例 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最好?
要找到最好的代码,最好编译它并使用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
最后,由于进行的操作较少,后者的实现似乎比前者更好。
我不是这方面的专家,所以如果有人可以编辑/执行更好的分析,请随意。我写了这个答案,因为它不适合单个评论。
两个循环只是相同的。没有最好的。但是如果N
value 很大,那么N*N
value 会溢出,你需要回到两个 for 循环。因此,您可以根据自己的N
价值使用它。
当你说得最好时,在编程意义上,有两种定义方式,在内存和性能方面(通常是迭代)。
就内存而言,第二个是最好的,因为只使用了 2 个变量(i 和 n)。除此之外,每次迭代只发生一次变量分配(i++ => i = i+1)。而在第一个 i++ 和 j++ 中,每次迭代都会发生两次分配操作。由于在高处理操作中重新分配变量也需要相当多的时间,所以第二个是最好的。
在迭代方面,两者是相同的。