Anopeng
@Anopeng
Веб-программист, учу фронт и бек

Почему вставка элементов занимает такое время?

Всем привет!
Читаю книгу "Грокаем алгоритмы", в разделе с массивами и списками вышла непонятка. Почему вставка элементов в массив занимает время O(n), а в список O(1)?
Разве в списке, нам не надо сначала дойти до последнего элемента, а потом создать в нем ссылку на новый элемент? Почему константное время?
А в массивах даже предположить не могу, почему O(n).
  • Вопрос задан
  • 228 просмотров
Решения вопроса 4
gbg
@gbg
Любые ответы на любые вопросы
Про список Просто автор хитренький и считает, что задача получения указателя на нужный элемент в списке - это отдельная задача поиска, которая как раз делается за O(n). Ну а со вставкой все просто - она действительно делается за O(1). Тот факт, что на практике зачастую вставка состоит из поиска и собственно вставки хитренький автор замел под ковер. Остерегайтесь хитреньких авторов!

Про массив Нетрудно догадаться™, что при вставке в массив на самое первое место, нужно сдвинуть весь хвост массива на один элемент (чтобы было место, куда вставлять). Вот это сдвигание, по самой пессимистичной (когда вставляем в самое начало) оценке и занимает O(n).
Ответ написан
Alexandroppolus
@Alexandroppolus
кодир
в массивах надо сдвинуть все элементы, которые будут после вставляемого. А в списках подразумевается, что у тебя уже есть ссылка на элемент списка, после которого надо вставить новый элемент
Ответ написан
Rsa97
@Rsa97
Для правильного вопроса надо знать половину ответа
Классический массив - это непрерывная область памяти, заполненная данными в порядке возрастания индексов. Чтобы вставить элемент в массив необходимо перенести часть уже имеющихся элементов, освободив место под вставляемый. При вставке в случайное место матожидание количества переносимых элементов будет n/2, соответственно сложность алгоритма оценивается в O(n). Добавление элемента в конец массива имеет сложность O(1), если нам известен текущий размер и мы не выходим за пределы памяти, выделенной для хранения массива. Если памяти недостаточно, то придётся выделить новый блок, перенести туда весь массив и освободить старый блок памяти. Эта процедура тоже занимает O(n).

Вставка в список зависит от того, есть ли у нас указатель на то место, куда надо вставить новый элемент. Если нет, то сначала необходимо выполнить поиск, который оценивается в O(n). Сама вставка, при этом, не требует перемещения других элементов и всегда выполняется за O(1).
Ответ написан
Комментировать
@res2001
Developer, ex-admin
Потому что, чтоб вставить элемент в массив в произвольное место, надо все остальные элементы сдвинуть на одну позицию.
Для вставки в список вы должны передать операции ссылку на элемент перед которым (или после которого) должен быть вставлен новый элемент. Имея такую ссылку операция происходит за константное количество шагов.
Такая же ситуация и с операцией удаления произвольного элемента.
Ответ написан
Комментировать
Пригласить эксперта
Ответы на вопрос 1
@alexbprofit
Junior SE
Потому что в список, мы можем вставить элемент куда угодно
Ответ написан
Комментировать
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы
10 авг. 2022, в 10:42
100000 руб./за проект
10 авг. 2022, в 10:42
30000 руб./за проект
10 авг. 2022, в 10:40
50000 руб./за проект