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

Question

[Anonymous Penguin]

Всем привет!
Читаю книгу "Грокаем алгоритмы", в разделе с массивами и списками вышла непонятка. Почему вставка элементов в массив занимает время O(n), а в список O(1)?
Разве в списке, нам не надо сначала дойти до последнего элемента, а потом создать в нем ссылку на новый элемент? Почему константное время?
А в массивах даже предположить не могу, почему O(n).

Answer 1

[Армянское Радио]

Про список Просто автор хитренький и считает, что задача получения указателя на нужный элемент в списке - это отдельная задача поиска, которая как раз делается за O(n). Ну а со вставкой все просто - она действительно делается за O(1). Тот факт, что на практике зачастую вставка состоит из поиска и собственно вставки хитренький автор замел под ковер. Остерегайтесь хитреньких авторов!

Про массив Нетрудно догадаться™, что при вставке в массив на самое первое место, нужно сдвинуть весь хвост массива на один элемент (чтобы было место, куда вставлять). Вот это сдвигание, по самой пессимистичной (когда вставляем в самое начало) оценке и занимает O(n).

Comments

[Anonymous Penguin]

Спасибо, буду остерегаться хитреньких авторов :D

[res2001]

вставка состоит из поиска и собственно вставки

Верно. Но часто, опорный элемент уже известен из предыдущих этапов работы программы.

При вставке в массив, кстати, то же ни кто не отменяет поиск опорного элемента и этот поиск то же в общем случае будет выполняться за O(n).
В таком случае если объединить операции поиска и вставки в одну, то для обоих контейнеров эта операция будет выполняться за O(n).
По моему, разделение этих задач вполне обоснованно.

[Армянское Радио]

res2001, оно обоснованно, когда книжку читает программист со стажем, который в состоянии понять, откуда ветер дует и что творится в голове у автора. (С другой стороны, нафига ему тогда книжка, разве что в качестве беллетристики).

Неопытный же читатель оказывается в рекурсивном тупике - чтобы понять книгу по алгоритмам, нужно понимать алгоритмы. Выходом было бы аккуратное объяснение что к чему с явным указанием мотивов автора.

[Alexandroppolus]

Получение индекса в массиве тоже может занять куда более O(n), если например по каждому элементу делается сложная проверка. Так что нет никакого смысла в оценку операции вставки добавлять ещё и поиск.

[Армянское Радио]

Alexandroppolus, о, нашелся человек, который не понимает O-нотацию. Даже если проверка на каждый элемент занимает час, оценка времени будет O(n).

[Anonymous Penguin]

Армянское Радио, тогда почему эту книгу многие рекомендуют? Раз автор не в состоянии нормально объяснить

[res2001]

Anonymous Penguin, "Грокаем алгоритмы" книга для начинающих, дает довольно поверхностный "облегченный" взгляд на проблему. Именно в таком разрезе ее и рекомендуют - чтоб без лишних заморочек быстренько въехать в тему на среднем уровне. Когда потребуется более серьезное понимание, то, скорее всего, понадобится другая литература.

Просто сравните объем. "Грокаем" - ~300 страниц, а например тот же Кормен ~1200. Я уж молчу про Кнута :-)
Думаю это не просто так.

[Армянское Радио]

Anonymous Penguin,

-популярность книги не всегда означает высокое качество. Например, она понравилась какой-то пачке профессионалов (по тому что для них она является беллетристикой и приятным чтением, а алгоритмы они изучали в другом месте), которые начали ее советовать на всех углах.

-то что автору не удалось что-то объяснить лично вам не означает, что автор плохой для всех читателей - он плохой персонально для вас (строго говоря, для такого утверждения нужно накопить историю взаимного непонимания). К счастью, на свете есть другие авторы.

Профессионалы обычно являются плохими (если не сказать больше) учителями (ровно как и учителя являются плохими профессионалами), потому что эти люди занимаются разной деятельностью и имеют разные цели.

Как минимум, профессионал использует все свои знания в комплексе, а учитель скован педагогическим процессом и должен выдавать знания дозированно - иначе ученик треснет (что с вами и произошло в данном случае)

[Alexandroppolus]

Армянское Радио,

Даже если проверка на каждый элемент занимает час, оценка времени будет O(n).

ок, допустим требуется найти в массиве чисел arr индекс i такого элемента, что someFunc(arr[j], arr[i]) === true, для всех j < i. Попробуй сделать за O(N), понимающий ты наш.

[Армянское Радио]

Alexandroppolus, это уже не задача поиска в массиве (У которой есть вполне конкретное определение - нужно перебирать элементы и для каждого делать проверку), а ваше изобретение, притянутое за уши в поддержку вашей версии.

В реальности же есть операция преобразования индекса в указатель. Для массивов это делается за O(1), для списков за O(n).

Ключевым для автора вопроса является то, что автор книги посчитал время вставки в список как O(1) исходя из предположения, что указатель уже есть в распоряжении программиста. Если же у программиста есть только индекс элемента (что на практике встречается довольно часто), к сложности добавляется вполне конкретный процесс поиска указателя на элемент с нужным индексом, который делается за O(n)

Вы же зачем-то к сложности конкретной операции вставки пытаетесь притянуть часть прикладного алгоритма, что методологически неверно.

[Alexandroppolus]

Армянское Радио,

это уже не задача поиска в массиве (У которой есть вполне конкретное определение - нужно перебирать элементы и для каждого делать проверку),

ну так проверка элемента вполне может включать в себя работу с тем же массивом. O(1) на элемент - это частный случай.

В реальности же есть операция преобразования индекса в указатель.

в реальности эта операция есть, только если задача стоит "воткнуть элемент на K-ю позицию". Это частный случай. И в вопросе пользователя такого не было.

[Армянское Радио]

Alexandroppolus,

ну так проверка элемента вполне может включать в себя работу с тем же массивом. O(1) на элемент - это частный случай.

Откройте уже для себя учебник Кнута про сортировку и поиск и разберитесь, что называется поиском элемента в массиве. Под проверкой элемента там понимается вполне конкретная операция со сложностью O(1), в противном случае, вся постороенная теория оценок сложности алгоритмов развалится.

то частный случай. И в вопросе пользователя такого не было.

если внимательно прочитать вопрос, он весь сделан в предположении, что вставка происходит в конец контейнера. Что является наихудшим случаем для связного списка (если мы не храним указатель на хвост), и почти всегда является наилучшим случаем для массива {отсюда и недоумение, почему вставка в массив занимает так много - при вставке в хвост массива обычно достаточно просто впихнуть элемент, а про случай исчерпания памяти автор вопроса не подумал}

Собственно, их этого предположения и развилось дальнейшее непонимание и возник этот пост.

[Alexandroppolus]

что называется поиском элемента в массиве

В общем виде - поиск такого элемента, который соответствует некоторому предикату.
например, плюсовый std::find_if - это ведь поиск, разве нет?
Операция (предикат) может быть любая, а не только O(1).
И непонятно, с чего вдруг это должно разваливать теорию оценок. Если проверка элемента занимает O(f(N)), то поиск в массиве займет O(N * f(N)). В чем проблема-то?

[Армянское Радио]

Alexandroppolus, Как именно придуманные вами случаи и усложнения относятся к вопросу, который задан автором? У автора (и у меня в ответе) под поиском понимается поиск хвоста списка, который ищется за O(n).

И непонятно, с чего вдруг это должно разваливать теорию оценок.

Потому что вся теория того, как работает поиск, (и не только в массиве, а например, в карте) дается для случая, что предикат проверяется за O(1). Для более сложного предиката теорию нужно будет разрабатывать заново, потому что O(N * f(N)) - это некое новшество, которое непонятно как оценивать.

Answer 2

[Alexandroppolus]

в массивах надо сдвинуть все элементы, которые будут после вставляемого. А в списках подразумевается, что у тебя уже есть ссылка на элемент списка, после которого надо вставить новый элемент

Comments

[Anonymous Penguin]

Спасибо :D

Answer 3

[Rsa97]

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

Вставка в список зависит от того, есть ли у нас указатель на то место, куда надо вставить новый элемент. Если нет, то сначала необходимо выполнить поиск, который оценивается в O(n). Сама вставка, при этом, не требует перемещения других элементов и всегда выполняется за O(1).

Answer 4

[res2001]

Потому что, чтоб вставить элемент в массив в произвольное место, надо все остальные элементы сдвинуть на одну позицию.
Для вставки в список вы должны передать операции ссылку на элемент перед которым (или после которого) должен быть вставлен новый элемент. Имея такую ссылку операция происходит за константное количество шагов.
Такая же ситуация и с операцией удаления произвольного элемента.

Answer 5

[alexbprofit]

Потому что в список, мы можем вставить элемент куда угодно