论String操作时间复杂度
面试题以下类中，method1和method2的时间复杂度一样吗？为什么。
Java代码
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());
}
}
我当时的回答是应该一样，因为我实在找不出说明他们不一样的地方。但是面试官这么问肯定有原因的，我只是从效率方面来分析，比如说method1会通过StringBuilder来做，没有后面method2好。后来面试官纠正了提问，说从时间复杂度来考虑。我直接跟他说了，我只能看出是一样的，可能method2会更好些。面试官好像不是很满意。
回来我从源码着手看，感觉不靠谱，后来看到有人分析用字节码来看。可以看到编译器怎么翻译的。经过证实，跟我的想法一样。字节码如下：
Java代码
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
} String 面试 Java stringbuilder --------------------编程问答-------------------- stringBuffer是线程同步，需要同步开销,method1会好一点 --------------------编程问答--------------------
谢谢回答，不过这里我用的是StringBuilder --------------------编程问答-------------------- 效率：
StringBuilder（非线程安全）> StringBuffer(线程安全) > String --------------------编程问答-------------------- 时间复杂度明显都一样，只是String 和StringBuffer实现有所不同
String:
是对象不是原始类型.
为不可变对象,一旦被创建,就不能修改它的值.
对于已经存在的String对象的修改都是重新创建一个新的对象,然后把新的值保存进去.
String 是final类,即不能被继承.
StringBuffer:
是一个可变对象,当对他进行修改的时候不会像String那样重新建立对象
它只能通过构造函数来建立,
StringBuffer sb = new StringBuffer();
note:不能通过付值符号对他进行付值.
sb = "welcome to here!";//error
对象被建立以后,在内存中就会分配内存空间,并初始保存一个null.向StringBuffer
中付值的时候可以通过它的append方法.
sb.append("hello");
字符串连接操作中StringBuffer的效率要比String高:
String str = new String("welcome to ");
str += "here";
的处理步骤实际上是通过建立一个StringBuffer,让侯调用append(),最后
再将StringBuffer toSting();
这样的话String的连接操作就比StringBuffer多出了一些附加操作,当然效率上要打折扣.
并且由于String 对象是不可变对象,每次操作Sting 都会重新建立新的对象来保存新的值.
这样原来的对象就没用了,就要被垃圾回收.这也是要影响性能的.
--------------------编程问答--------------------
是的 我实在弄不明白想考察的知识点是什么 我说了性能方面的 但是boss说想听听时间复杂度方面的。 --------------------编程问答--------------------
说得很好，同时头像很NICE
--------------------编程问答--------------------
你问下那个面试官知道不?有很多面试官故作高深 时间复杂度 他是让你直接说出复杂度表达式吗?
--------------------编程问答--------------------
String的那个其实等于new了100个对象。而StringBuilder中等于new了一个对象。
时间复杂法肯定是一样的。
如果是我我会举这样一个例子，
一个方法输入参数分别为String和StringBuilder
方法内部对这两个对象的值进行修改，方法外的值一个变化，一个不变化。
这就是区别。 --------------------编程问答-------------------- 真心没啥意思，面试官刚大学毕业吗 --------------------编程问答--------------------
不要这么说 心态好了就没事了 再有他很牛逼
--------------------编程问答--------------------
简单明了
--------------------编程问答--------------------
你就问问面试官，这个什么时间复杂度，算不算GC的耗时啊
--------------------编程问答--------------------
也许他想考考你立场是否坚定
--------------------编程问答--------------------
按照我个人理解 String 每次都会new新的对象 重新分配给对象新的内存地址，在堆中
Stringbuffer 就会new一次 地址就那分配了 不会有新的内存地址，少了重新分配的过程
应该是StringBuffer快些。
补充：Java , Java EE
