Временная сложность метода подпоследовательности Stringbuilder

Question

Начиная с Java 7, метод подстроки String изменил свой большой O с O (1) на O (n).

Какова временная сложность метода подпоследовательности StringBuilder?

Answer 1

In 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).