powered by simpleCommunicator - 2.0.61     © 2026 Programmizd 02
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Форумы / Java [игнор отключен] [закрыт для гостей] / Сложность добавления p элементов в конец ArrayList размера n
4 сообщений из 4, страница 1 из 1
Сложность добавления p элементов в конец ArrayList размера n
    #39103149
redwhite90
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
в тесте встретил вопрос:

авторAdding p elements to the end of an ArrayList (of size n) is

говорят, что правильный ответ O(p)

авторExplanation
Adding an element to the end of an ArrayList is a constant time operation, unless the backing array is full and must be replaced by a larger array. In that case, a new array is constructed, whose length (in Java 8) is 1.5 times the length of the old array. Then all the elements are copied from the old array to the new array.

This longer copy operation is thus amortized over the p element additions.

я чего-то не понял.
Можете разъяснить?
...
Рейтинг: 0 / 0
Сложность добавления p элементов в конец ArrayList размера n
    #39103159
redwhite90
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
или тут имеется ввиду положительный сценарий, что p влезут в текущее capacity и массив не придётся расширять?
...
Рейтинг: 0 / 0
Сложность добавления p элементов в конец ArrayList размера n
    #39103203
Фотография Blazkowicz
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
redwhite90,

Да, потому что в случае нужды ты всегда можешь задать capacity достаточный для большинства сценариев и всё ещё эффективный по памяти.
...
Рейтинг: 0 / 0
Сложность добавления p элементов в конец ArrayList размера n
    #39103243
ivanra
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Строго говоря, сложность при больших p и n равна O((p+n)*log 1.5 (p)), если добавлять по 1 элементу, с автоматическим увеличением размера массива. Это в соответствии с приведенным Explanation.
Но можно предварительно выполнить
Код: java
1.
 a.ensureCapacity(n+p);

, и тогда сложность сводится к O(n+p)
...
Рейтинг: 0 / 0
4 сообщений из 4, страница 1 из 1
Форумы / Java [игнор отключен] [закрыт для гостей] / Сложность добавления p элементов в конец ArrayList размера n
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]