String操作時間の複雑さについて
3699 ワード
面接問題
以下のクラスでは、method 1とmethod 2の時間的複雑さは同じですか?どうして.
私のその時の答えは同じはずだった.彼らの違いを説明する場所が見つからなかったからだ.しかし、面接官がそう聞くのは理由があるに違いありません.私は効率の面から分析しています.例えば、method 1はStringBuilderでやります.後ろのmethod 2がないほうがいいです.その後、面接官は質問を直して、時間の複雑さから考えると言った.私は直接彼に言ったが、私は同じことしか見えない.method 2のほうがいいかもしれない.面接官はあまり満足していないようです.
帰ってきて私はソースコードから見て、頼りにならない感じがして、後でバイトコードで見る分析があるのを見ました.コンパイラがどのように翻訳されているかを見ることができます.実証された結果、私の考えと同じです.バイトコードは次のとおりです.
以下のクラスでは、method 1とmethod 2の時間的複雑さは同じですか?どうして.
public class Test {
public static final int MB = 1024 * 1024;
public static final long TIMES = 500000000L;
public static void main(String[] args) throws InterruptedException {
method1();
method2();
}
// ,method1 new StringBuilder
append, 。 jit 。
public static void method1() {
String s = "";
for (int i = 0; i < 100; i++) {
s += "a";
}
System.out.println(s);
}
public static void method2() {
// //b
StringBuilder sb = new StringBuilder();
for (int i = 0; i < 100; i++) {
sb.append("a");
}
System.out.println(sb.toString());
}
}
私のその時の答えは同じはずだった.彼らの違いを説明する場所が見つからなかったからだ.しかし、面接官がそう聞くのは理由があるに違いありません.私は効率の面から分析しています.例えば、method 1はStringBuilderでやります.後ろのmethod 2がないほうがいいです.その後、面接官は質問を直して、時間の複雑さから考えると言った.私は直接彼に言ったが、私は同じことしか見えない.method 2のほうがいいかもしれない.面接官はあまり満足していないようです.
帰ってきて私はソースコードから見て、頼りにならない感じがして、後でバイトコードで見る分析があるのを見ました.コンパイラがどのように翻訳されているかを見ることができます.実証された結果、私の考えと同じです.バイトコードは次のとおりです.
Compiled from "Test.java"
public class Test extends java.lang.Object{
public static final int MB;
public static final long TIMES;
public Test();
Code:
0: aload_0
1: invokespecial #16; //Method java/lang/Object."<init>":()V
4: return
public static void main(java.lang.String[]) throws java.lang.InterruptedException;
Code:
0: invokestatic #27; //Method method1:()V
3: invokestatic #30; //Method method2:()V
6: return
public static void method1();
Code:
0: ldc #35; //String
2: astore_0
3: iconst_0
4: istore_1
5: goto 31
8: new #37; //class java/lang/StringBuilder
11: dup
12: aload_0
13: invokestatic #39; //Method java/lang/String.valueOf:(Ljava/lang/Object;)Ljava/lang/String;
16: invokespecial #45; //Method java/lang/StringBuilder."<init>":(Ljava/lang/String;)V
19: ldc #48; //String a
21: invokevirtual #50; //Method java/lang/StringBuilder.append:(Ljava/lang/String;)Ljava/lang/StringBuilder;
24: invokevirtual #54; //Method java/lang/StringBuilder.toString:()Ljava/lang/String;
27: astore_0
28: iinc 1, 1
31: iload_1
32: bipush 100
34: if_icmplt 8
37: getstatic #58; //Field java/lang/System.out:Ljava/io/PrintStream;
40: aload_0
41: invokevirtual #64; //Method java/io/PrintStream.println:(Ljava/lang/String;)V
44: return
public static void method2();
Code:
0: new #37; //class java/lang/StringBuilder
3: dup
4: invokespecial #73; //Method java/lang/StringBuilder."<init>":()V
7: astore_0
8: iconst_0
9: istore_1
10: goto 23
13: aload_0
14: ldc #48; //String a
16: invokevirtual #50; //Method java/lang/StringBuilder.append:(Ljava/lang/String;)Ljava/lang/StringBuilder;
19: pop
20: iinc 1, 1
23: iload_1
24: bipush 100
26: if_icmplt 13
29: getstatic #58; //Field java/lang/System.out:Ljava/io/PrintStream;
32: aload_0
33: invokevirtual #54; //Method java/lang/StringBuilder.toString:()Ljava/lang/String;
36: invokevirtual #64; //Method java/io/PrintStream.println:(Ljava/lang/String;)V
39: return
}