字符串拼接时间复杂度对比：单次+=与循环拼接是否同阶？

针对你提出的两种拼接方式，直接给出结论：append1的时间复杂度是O(n²)，append2是O(m+n)（m为原字符串长度，n为待拼接字符串长度），二者完全不同。

一、append1的时间复杂度解析 #

在append1的循环中，每次执行str += s.charAt(i)时，由于Java的String是不可变对象，每次拼接都会创建一个新的String实例：

• 第一次循环：将长度为5的"hello"与1个字符拼接，需要复制5+1=6个字符；
• 第二次循环：将长度为6的新字符串与下一个字符拼接，需要复制6+1=7个字符；
• ……
• 第k次循环（k为s的长度）：复制5+k个字符。

总复制次数是等差数列求和，最终时间复杂度为O(n²)（n为s的长度），这正是多次拆分拼接带来的高复杂度。

二、append2的时间复杂度解析 #

对于单个str += s操作，Java编译器会自动进行优化，将其转换为使用StringBuilder的高效拼接，等价代码如下：

void append2(String s) {
    String str = "hello";
    StringBuilder sb = new StringBuilder(str);
    sb.append(s);
    str = sb.toString();
}

StringBuilder在执行append时，会先计算总长度（原字符串长度 + s的长度），一次性分配足够的字符数组空间，然后将原字符串和s的字符一次性复制到新数组中。整个过程仅需两次线性复制，总时间复杂度为O(m+n)，属于一次完整的拼接操作，不会逐个字符拆分拼接。

三、关于你额外疑问的解答 #

1. 为什么String x = "hello"是O(n)，而x += " world"不同？

   • String x = "hello"是直接创建单个String对象，JVM仅需将字面量的字符数组复制到String的内部数组，时间复杂度为O(n)（n为字符串长度）。
   • x += " world"是两个已有字符串的拼接，编译器优化后是一次线性时间的操作（O(m+n)），和直接创建字面量的场景逻辑不同，但依然是线性复杂度，而非O(n²)。

2. str += " world"应被视为一次还是多次拼接？
   这是一次拼接。编译器会将单个+=操作优化为一次性合并两个字符串的逻辑，只有当+=出现在循环中且编译器无法识别优化时，才会变成多次拼接导致O(n²)复杂度。

内容的提问来源于stack exchange，提问作者Zerenity