2

我正在阅读一本关于算法问题的流行书籍，并看到了字符串连接的实现，如下所示：

public String joinTheStrings(String[] theStrings){
     String joinedString = "";
     for(String singleString : theStrings){
          joinedString = joinedString + singleString;
     }
     return joinedString;
}

然后作者继续声称此实现是O(n^2)，并且优化将使用 aStringBuffer代替joinedString，他们声称将使用该算法O(n)。但是，我看不到原始算法是如何O(n^2)- 在我看来，对于 N 个单词，将有 N 个操作（将字符串加在一起）。

更新：感谢您的回复。看起来我对作者如何将字符数组的复制（我认为这是一个常数）视为摊销运行时 N 的另一个因素感到困惑？

4

1 回答 1

3

该运算符过去通过将其两个操作数的字符复制到一个带有 size的新字符中+来创建一个新字符，但为此它必须遍历它们的字符。这就是你隐藏的内循环所在的地方。Stringchar[]firstString.length() + secondString.length()

StringBuilder但是，JDK 的最新版本在编译时通过自动将字符串连接转换为'append()操作来优化字符串连接。你说的那本书肯定很老了，现在StringBuffer一般都用不上了，因为是同步的。

无论如何，编译器可能不够聪明，无法在循环之外StringBuilder提取实例化，为每次迭代创建新的字符串构建器，从而降低了其作为性能优化的有用性。所以手写这个不是一个坏主意：

public String joinTheStrings(String[] theStrings) {
     StringBuilder joinedString = new StringBuilder();
     for (String singleString : theStrings)
          joinedString.append(singleString);
     return joinedString.toString();
}
于 2013-08-25T17:25:24.860 回答