Stringbuilder subSequence方法的时间复杂度

Question

从Java 7开始，字符串子串方法将其大O从O(1)改为O(n)。

StringBuilder subSequence方法的时间复杂度是多少？

Answer 1

在java-11-openjdk中，AbstractStringBuilder.subSequence调用substring...

public CharSequence subSequence(int start, int end) {
    return substring(start, end);
}

..。这与String的同名方法几乎完全相同。

public String substring(int start, int end) {
    checkRangeSIOOBE(start, end, count);
    if (isLatin1()) {
        return StringLatin1.newString(value, start, end - start);
    }
    return StringUTF16.newString(value, start, end - start);
}

..。调用newString，它将(在两种情况下)复制后备数组，因此它也是O(n)。

public static String newString(byte[] val, int index, int len) {
    return new String(Arrays.copyOfRange(val, index, index + len),
                      LATIN1);
}

Answer 2

我不知道你是从哪里找到这些信息的。子串的O(1)到O(n)？

StringBuilder.subSequence(int start, int end)的复杂性与String.substring(int start, int end)大致相同。

StringBuilder.subSequence(int, int)实际上调用了AbstractStringBuilder.substring(int, int)，后者调用public String(char value[], int offset, int count)来创建结果。

String.substring(int start, int end)使用相同的构造函数。

所以所有的方法都有相同的实现。

这项工作在字符串构造器中完成。它使用System.arrayCopy将字符从一个缓冲区复制到另一个缓冲区。因此，它不是为每个字符进行赋值(这将使其成为O(n)，其中n不是输入的长度，而是子字符串的长度)，而是使用高性能系统函数来复制内存块，这比O(n)要好得多。