Java字符串拼接时间复杂度：+=是O(n)还是O(n²)？

在 Java 中，使用 `+=` 拼接两个已知长度的字符串（例如 `str += " world"`），本质上是一次 O(n) 操作，而非多次 O(1) 或 O(n²) 的累积拼接。其背后机制是 JVM 对字面量长度的静态感知，以及底层数组的一次性分配。

在 Java 中，字符串是不可变对象，这意味着每次拼接都会创建一个新的 String 实例。但问题的关键并不在于“是否创建新对象”，而在于拼接操作的次数以及执行方式——这直接决定了时间复杂度是线性增长还是灾难性的平方级增长。

一次拼接：str += s，本质是 O(m + n)，即 O(n)

当执行一次 `str += s`（其中 s 是一个完整的字符串，比如 " world"）时，现代 HotSpot JVM 会执行以下操作：

• 静态获取左侧 str 和右侧 s 的长度（str.length() 和 s.length() 均为 O(1) 操作，因为 String 内部缓存了 count 字段）；
• 一次性分配一个长度为 str.length() + s.length() 的新字符数组；
• 只需两次连续拷贝：先复制 str 的所有字符，再复制 s 的所有字符。总拷贝字符数 = m + n。

// 典型场景：编译器可优化的场景
String str = "hello";
str += " world"; // 等价于 new String("hello world")，底层一次分配，两次拷贝
// 时间复杂度：O(5 + 6) = O(11) → 即 O(m + n)

因此，这属于一次串联（one concatenation），时间复杂度严格为O(m + n)，并非 O(n²)。

循环逐字符拼接：str += s.charAt(i)，是 O(n²)，必须避免

那么，像下面这种逐字符拼接的写法，为什么时间复杂度会飙升？

for (int i = 0; i < s.length(); i++) {
    str += s.charAt(i); // 每次循环都新建一个String实例
}

过程是这样的：

• 第 1 次："hello" + ' ' → 新建长度为 6 的数组，拷贝 6 个字符；
• 第 2 次："hello " + 'w' → 新建长度为 7 的数组，拷贝 7 个字符；
• ……
• 第 k 次：拷贝 (5 + k) 个字符；

累计拷贝量 ≈ Σₖ₌₁ⁿ (m + k) = m·n + n(n+1)/2 = O(mn + n²)。当 m 和 n 同阶时，即为O(n²)。

这里的关键在于，编译器并非“无法预知长度”，而是语义强制了逐轮重建：每次 `+= char`，底层都会调用 `StringBuilder.append(char).toString()`（或类似逻辑），无法在开始前获知最终长度。

编译器能“预知”字面量长度吗？能，而且会充分优化

Java 编译器（javac）和 JVM 对字符串字面量具有完全的可见性：

• " world" 在编译期就已经确定长度为 6；
• str += " world" 会被 JIT 编译器内联为高效路径（例如通过 StringConcatFactory 生成专用字节码）；
• 即使运行时 s 是变量，只要其 length() 能快速获取（String 保证 O(1)），仍然是 O(m+n)。

注意：String x = "hello" 本身是 O(1) —— 字面量在类加载时进入字符串常量池，不涉及字符拷贝。而 x += " world" 虽然创建了新对象，但拷贝总量是线性的，绝非 O(n²)。

正确实践：什么场景用什么方式？

// ✅ 高效写法
StringBuilder sb = new StringBuilder("hello");
sb.append(" world"); // O(6) 拷贝，无中间对象
String result = sb.toString(); // O(1) 创建最终String

结论：str += " world" 是一个一次、且仅一次的 O(n) 字符串拼接操作，绝不是什么“按字符拆解为多个 O(1) 拼接”。其高效性，源于 JVM 对字符串长度的静态认知，以及底层内存的一次性规划——这是现代 Java 字符串实现中的关键优化，也是开发者应当信赖的基础行为。