Java - 创建长度递增的字符串列表的时间复杂度

Question

我有一个关于 Java 中的字符串的非常具体的问题。给定一个字符串，我希望能够创建一个字符串数组，这样每个第 i 个元素都是一个由给定字符串的前 i 个字符组成的字符串。像这样:

public static String[] substrings(String s){
    String[] list = new String[s.length()];
    list[0] = "" + s.charAt(0);
    for (int i = 1; i < s.length(); i++)
        list[i] = list[i-1] + s.charAt(i);
    return list;
}

但我听说将字符串与“+”相加的时间复杂度为 O(n)。这意味着我的方法具有时间复杂度 O(n²)。另一种方法可能是使用 StringBuilder 对象。像这样:

public static String[] substrings(String s){
    String[] list = new String[s.length()];
    StringBuilder sb = new StringBuilder(s.length());
    for (int i = 0; i < s.length(); i++){
        sb.append(s.charAt(i));
        list[i] = sb.toString();
    }
    return list;
}

但我感觉 StringBuilder.toString() 的时间复杂度为 O(n)，这意味着该方法的时间复杂度仍然为 O(n²)。虽然我不确定这一点，所以如果我错了请纠正我。

如果我的看法是对的，有没有一种方法可以在 Java 中构建字符串，并对其所有值进行某种记录，而不需要时间复杂度 O(n²)？

如果没有，有没有办法用另一种编程语言(最好是 C 或 C++)来做到这一点？

感觉就像一台计算机应该能够做到这一点，因为你实际上可以用数字来做到这一点。虽然它确实有更多的字符串内存复杂性，所以如果它不可能，我也不会太惊讶。

Answer 1

查看 OpenJKD，StringBuilder.toString() ( 1 ) 最终调用 new String(char[], offset, count) ( 2 ) ，它调用 Arrays.copyOfRange ( 3 )，它调用 System.arrayCopy。在某种程度上，这将最终在内存中移动 n 个字节；然而，系统通常能够利用 CPU 级 block 复制命令，这比一次复制 n 个字节执行得更快。

我认为这个算法仍然是 n^2，因为您要复制 1，然后 2，然后 3，...，然后 n 个字节。我认为您无法更快地实现目标，因为您必须复制这么多字节才能填充数组。

字符串生成器实现的性能肯定更高，因为在每一步中，它都会将一个字节写入一个数组(其大小已经正确!)，然后将该数组复制到不同的内存位置。