Благодаря амортизированному анализу мы знаем, что вставки 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-complexit ... fer-append как Какова сложность этого простого фрагмента кода?
Подробнее здесь:
https://stackoverflow.com/questions/567 ... xity-is-o1
Мобильная версия