Временная сложность в Java

Question

Для метода add API Java ArrayList говорится:

Операция добавления выполняется с амортизированным постоянным временем, то есть для добавления n элементов требуется время O (n).

Интересноесли это та же временная сложность, линейная, при использовании метода add LinkedList.

Answer 1

Это зависит от того, куда вы добавляете. Например. если в ArrayList вы добавляете его в начало списка, реализация будет вынуждена каждый раз сдвигать все элементы, поэтому добавление n элементов будет выполняться за квадратичное время.

Аналогично для связанного списка, реализация в JDK сохраняет указатель на голову и хвост. Если вы продолжаете прибегать к хвосту или к передней части головы, операция будет выполняться за линейное время для n элементов. Если вы добавляете в другое место, реализация должна будет искать в связанном списке правильное место, что может ухудшить время выполнения. Опять же, это зависит от позиции вставки; вы получите наихудшую временную сложность, если вставите ее в середину списка, поскольку для поиска точки вставки необходимо пройти максимальное количество элементов.

Фактическая сложность зависит от того, является ли ваша позиция вставки постоянной (например, всегда на 10-й позиции), или функцией количества элементов в списке (или какого-либо произвольного поиска по нему). Первый даст вам O (n) с немного худшим постоянным коэффициентом, последний O (n ^ 2).

Answer 2

В большинстве случаев ArrayList превосходит LinkedList в методе add(), поскольку он просто сохраняет указатель на массив и увеличивает счетчик.

Если массив Wooking недостаточно велик, ArrayList увеличивает рабочий массив, выделяя новый и копируя содержимое. Это медленнее, чем добавление нового элемента в LinkedList, но если вы постоянно добавляете элементы, это происходит только O (log (N)) раз.

Когда мы говорим об «амортизируемой» сложности, мы берем среднее время, рассчитанное для некоторого контрольного задания.

Итак, отвечая на ваш вопрос, это не та же сложность: она намного быстрее (хотя все еще O (1)) в большинстве случаев и намного медленнее (O (N)) иногда. Что лучше для вас, лучше проверить с помощью профилировщика.

Answer 3

Если вы имеете в виду метод add(E) (не метод add(int, E)), ответ - да, временная сложность добавления одного элемента в LinkedList постоянна (добавление n элементов требует времени O (n))

Как Мартин Пробст указывает , при разных позициях вы получаете разные сложности, но операция add(E) всегда добавляет элемент к хвосту, что приводит к операции с постоянным (амортизированным) временем