代码之家 › 专栏 › 技术社区 › anon

用字符添加Java字符串字符的空间复杂度

space-complexity string-concatenation complexity-theory string java

-2

anon · 技术社区 · 6 年前

当通过一个循环通过“加法”构建一个Java字符串char时,可以观察到 时间复杂性 执行此操作的能力很差:属于二次 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 concatenation complexity in C++ and Java 因为它不能解决 空间复杂性 .我特别想要一份详细的 空间复杂性 分析。

2 回复 | 直到 6 年前

1

Andy Turner 6 年前

它使用二次空间。或者,更确切地说,分配了一个二次空间量,因为循环的每个迭代(至少在JIT不擅长的代码中)都将分配一个新的char数组:

new char[1]
new char[2]
new char[3]
// Etc.

二次时间性能的原因是将字符串复制到这些更大的数组中。

2

Elliott Frisch 6 年前

你的代码效率很低, 因为有一个隐含的 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 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());