Почему сложность времени StringBuilder.append равна O (1) - PullRequest
Новая
       14

Почему сложность времени StringBuilder.append равна O (1)

1 голос
/ 28 июня 2019

По амортизированному анализу мы знаем, что N вставки с методом StringBuilder#append занимают O(N) время. Но здесь я теряюсь. Учтите это, где inputString - это строка ввода от пользователя. 

for (int i = 0; i < N; i++) {
   s.append(inputString); 
   // where s is an empty StringBuilder object at the beginning 
   // and inputString is the string that is taken from the user
}

Должно ли это иметь временную сложность O(inputString.length * N), поскольку append() копирует входную строку в конец StringBuilder N раз? Почему мы считаем, что append() требует O(1) сложности времени, тогда как ее следует рассматривать как O(inputString.length)?

Почти везде, где я проверяю, он считается O(1), таким как https://quora.com/What-is-the-complexity-of-Java-StringBuffer-append, а также В чем сложность этого простого куска кода?

1 Ответ

5 голосов
/ 28 июня 2019

Должно ли это иметь временную сложность O (inputString.length * N), так как append () копирует входную строку в конец StringBuilder N раз?

Да.

Почему мы считаем, что append () требует O (1) временной сложности, тогда как его следует рассматривать как O (inputString.length)?

Это O (1)при добавлении отдельных символов.StringBuilder похож на ArrayList.При добавлении одного элемента стоимость O (1).Добавление строки похоже на вызов addAll () - стоимость пропорциональна длине строки / количеству добавляемых элементов.

Похоже, вы все правильно поняли.Проблема в том, что люди часто небрежно обсуждают производительность Big-O.Это эндемично.

...