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

但是，无论如何，从性能的角度来看，使用StringBuilder更好。

我在 toString() 时观察到这种情况。我观察到使用 + 运算符构建字符串比使用 StringBuilder 花费更多时间。所以说的和做的一切——即使时间复杂度相似，使用 StringBuilder 总是更好。

Answer 2

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

我认为这个算法仍然是 n^2，因为你要复制 1，然后是 2，然后是 3，...，然后是 n 个字节。我不认为你可以更快地完成你的目标，因为你必须复制这么多字节来填充数组。

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

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

Java - Time complexity of creating lists of strings of increasing length

string

algorithm

complexity-theory

list