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

Question

Среднее и наихудшее время выполнения вставки и поиска в отсортированном одно- и двусвязном списке составляет O (1) и O (n).Одинаковы ли сложности времени выполнения в лучшем случае?

Другими словами, в лучшем случае, имеет ли отсортированный однократно и двусвязный список время O (1) для вставки и время O (n) для поиска?

Answer 1

Думайте об этом так:

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

Вставка после определенного элемента одинакова в лучшем случае: вы вставляете после определенного элемента, который снова не зависит от длины списка, поэтому это O(1).

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