Блог

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

В моих классах алгоритмов и структур данных мы изучали, как реализовать список с двойной связью. Преподаватели предоставили код и таблицу с временной сложностью каждой функции. Таблица с временной сложностью функций.

Pior Caso означает наихудший случай, Melhor Caso означает наилучший случай, Caso Esperado означает средний случай

Итак, я сомневаюсь, почему временная сложность поиска в лучшем случае O (1), а не O (n), учителя говорят, что я не могу сказать, что лучший случай для n = 1, но они также говорят, что лучший случай — это когда элемент, который мы ищем, является первым. Что они подразумевают под этим??? Может кто-нибудь объяснить мне, как рассчитать наилучшую, наихудшую и среднюю временную сложность алгоритмов?

вот код для поиска:

алгоритм поиска

Представьте, что у вас есть следующий двусвязный список чисел:

 1 <-> 5 <-> 3 <-> 9 <-> 8 <-> 10
  

Если бы вы искали число 1 , начинающееся слева, вы бы сразу его нашли. Это O(1) операция, потому что все, что вам нужно было сделать, это коснуться первого элемента (слева). С другой стороны, если вы искали номер 10 и были настолько неудачны, что также начали слева, тогда вам пришлось бы касаться каждого элемента в связанном списке, всех N из них (в данном случае 6). Это была бы O(N) операция.

В общем, для поиска элемента в несортированном связанном списке потребуются N / 2 операции, то есть вам нужно в среднем выполнить поиск по половине элементов. Это также O(N) операция в общем случае.