时间戳

首页 > 解决方案 > 逐字符添加Java字符串的空间复杂度

java - 逐字符添加Java字符串的空间复杂度

问题描述

当通过“加法”循环通过一个字符一个字符地构建一个Java字符串时，可以观察到执行这个操作的时间复杂度很差：它是二次 O(n^2)时间的。但是，我想知道通过循环“逐个添加”字符串的空间复杂度是否也很差。

这是一个程序的最小示例，该程序通过逐字符添加和秒表计时来执行构建字符串。下面显示的结果清楚地显示了二次曲线：

/**Create a String of n 'A's char-by-char.
 * @param n Number of 'A's to be appended
 * @return The finished string
 */
public static String appendString(int n) {
    String str = "";
    // Timed run starts here
    long t = System.currentTimeMillis();
    // String concatenation occurs here
    for (int k = 0; k < n; k++)
        str += "A";
    t = System.currentTimeMillis() - t;
    // Timed run ends
    System.out.printf("%d\t%d\n", n, t);
    return str;
}

虽然我可以得到程序的时间复杂度，但我想知道逐个字符地构建 String的空间复杂度是多少？

首选解决内存管理的详细答案。（我怀疑它也是二次的，因为字符串是不可变的，每次你必须为不断增加的字符串分配新的内存）

注意：这不是C++ 和 Java 中字符串连接复杂度的重复，因为它没有解决空间复杂度。我特别要求进行详细的空间复杂度分析。

标签： javastringcomplexity-theorystring-concatenationspace-complexity

解决方案

您的代码效率很低，因为创建了一个隐式StringBuilder以在循环中添加单个字符。这，

for (int k = 0; k < n; k++)
    str += "A";

相当于类似

for (int k = 0; k < n; k++)
    str = new StringBuilder(str).append("A").toString();

您可以通过使用单个StringBuilder来大大提高空间（和时间）性能（并且您可以显式调整它的大小）。像，

StringBuilder sb = new StringBuilder(n);
for (int k = 0; k < n; k++)
    sb.append("A");
String str = sb.toString();

或者，在 Java 8+ 中，您可以使用生成器并将其限制为n时间并收集它。像，

return Stream.generate(() -> "A").limit(n).collect(Collectors.joining());

推荐阅读