Какова сложность вставки в отсортированный список ссылок в формате big-O?

Question

Какова сложность вставки в отсортированный список ссылок в формате big-O? Допустим, у меня есть 5 элементов, и какова сложность, чтобы вставить все из них.

Большое спасибо

Answer 1

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

1) Вы должны найти правильное место в списке. Это линейный поиск. О (п)

2) Вставить очень просто: создайте новый узел, установите указатели на предыдущий и следующий узлы. O (1)

В этом случае O (n) перевешивает O (1), поэтому это O (n).

Количество элементов на самом деле не относится к big-O, поскольку все они основаны на порядках.

Answer 2

Во-первых, я бы рекомендовал прочитать статью в Википедии о Связанных списках , особенно (небольшую) часть о ускорении поиска.

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

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