Java字符串+拼接新对象创建机制与O(N²)复杂度解析

先看你给出的代码：

String str=""; 
char ch='a'; 
for(int i=0;i<n;i++)//n是输入变量 { 
    str=str+ch; 
    ch++; 
}

时间复杂度为O(N²)的原因 #

你误以为对象创建是常数时间，但问题出在字符串拼接时的字符复制操作：

• String是不可变对象，每次执行str + ch，都需要把原str中的所有字符和新的ch字符，复制到一个全新的字符数组（JDK9及以后是byte数组）中，再用这个数组创建新的String对象。
• 第一次循环：复制1个字符（原str为空，加上ch后总长度1）
• 第二次循环：复制2个字符（原str长度1，加上ch后总长度2）
• ...
• 第n次循环：复制n个字符（原str长度n-1，加上ch后总长度n）

总字符复制次数是1+2+...+n = n(n+1)/2，这属于O(N²)级别的操作，远大于循环本身的O(N)次数。

String拼接时的对象创建机制 #

Java编译器会把str + ch这种语法糖转换成以下简化逻辑：

// 每次循环都会执行这段逻辑
StringBuilder sb = new StringBuilder();
sb.append(str);
sb.append(ch);
str = sb.toString();

具体创建流程：

1. 新建一个StringBuilder对象，内部初始化字符数组。
2. 调用append(str)：把原String的字符数组内容，完整复制到StringBuilder的内部数组中。
3. 调用append(ch)：把新字符添加到StringBuilder的数组末尾（若数组容量不足会自动扩容，扩容操作是均摊常数时间，不影响整体复杂度）。
4. 调用toString()：新建一个String对象，把StringBuilder内部的有效字符数组复制一份，作为新String的底层存储。
5. 原String对象失去引用，等待GC回收。

所以每次循环都会创建至少两个新对象：StringBuilder和新的String，而最耗时的是每次复制原字符串所有字符的操作，这才是导致O(N²)复杂度的核心。

如果要优化成O(N)复杂度，只需把StringBuilder提到循环外复用：

StringBuilder sb = new StringBuilder();
char ch='a';
for(int i=0;i<n;i++){
    sb.append(ch);
    ch++;
}
String str = sb.toString();

这样只会执行n次字符追加操作，总操作次数为O(N)。

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