Java中使用“+”运算符连接一个字符时如何创建一个新的字符串对象？

Question

在学习字符串的时候，遇到一段java中字符串拼接的代码片段，推导出的时间复杂度为O(N²)

String str="";
char ch='a';
for(int i=0;i<n;i++)//n is the input variable
{
  str=str+ch;
  ch++;
}

经过进一步调查我发现， “for”循环运行 26 次，每次循环迭代时，下一个字母表都会添加到字符串中，因此，如果由于字符串的不可变性质而每次都创建新对象， 假设创建字符串对象需要恒定时间，时间复杂度为 O(N)，

那么，你能解释一下 java 中新的 String 对象是如何被创建的，这导致了这段代码片段的时间复杂度为 O(N²) 吗？

我正在学习字符串及其连接，并遇到了一个字符串连接的代码片段，其推导的时间复杂度为 O(N²)，但我预计它是 O(N) 假设创建字符串需要恒定的时间。

Answer 1

在学习字符串的时候，遇到一段java中字符串拼接的代码片段，推导出的时间复杂度为O(N2)

是的。

如果由于 sting 的不可变性，每次都会创建新对象，那么时间复杂度将为 O(N)

没有。

假设创建字符串对象需要恒定的时间，

这个假设是错误的。

---

当你写下：

String a = readInput(); // 'abc' is read
String b = readInput(); // 'def' is read

String c = a + b;

最终发生的是

a + b

被编译为对

String.concat

的调用，其工作原理如下：

public static String concat(String a, String b) {
  char[] x = new char[a.length() + b.length()];
  int pos = 0;
  for (int i = 0; i < a.length(); i++) {
    x[pos++] = a.charAt(i);
  }
  for (int i = 0; i < b.length(); i++) {
    x[pos++] = b.charAt(i);
  }
  return String.wrap(x);
}

That 是

O(z)

，其中 z 代表字符串输入长度。你会这样做

n

次，其中 n 代表你要连接的字符串数量。

因此，总操作时间为

O(n*z)

，其中“n”是字符串数量，z 是每个字符串的平均长度。

在讨论大 O 表示法时，人们有一种非常非常讨厌的倾向，就是不解释

n

代表什么。这是一个常见的错误，您应该尽量避免犯。然而，这确实解释了：大多数人们错误地简化了正确的陈述：

Performance characteristic is O(n*z) where n is ... and z is ....

到

Performance characteristic is O(n^2)

。