сложность сортировки вставками с использованием двусвязного списка?

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

Временная сложность получается O(n^2)? Почему? Если мы рассмотрим вставку для n элементов, то это будет log (1) + log (2) + log (3) + ..... + log (n) - n раз для n элементов, следовательно, сложность должна быть O (nlogn)


sorting linked-list complexity-theory insertion-sort
person Luv    schedule 05.04.2012    source источник
comment
Почему вы думаете, что это log(1) + log(2) + ... + log(n), а не 1 + 2 + ... + n? Пожалуйста, добавьте больше деталей в вопросы, чтобы получить более информативные ответы, которые с большей вероятностью объяснят, в чем заключается ваша ошибка.   -  person amit    schedule 05.04.2012
comment
для вставки с использованием сортировки вставками, если мы используем двусвязный список, тогда вставка элемента занимает время log (k), где k - количество уже отсортированных элементов   -  person Luv    schedule 05.04.2012

Ответы (1)


arrow_upward
2
arrow_downward

Вставка в связанный список занимает время O(n), а не O(lg n), потому что вам нужно перемещаться по структуре ссылок, чтобы найти точку вставки.

person Fred Foo    schedule 05.04.2012