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

Временная сложность поиска элемента зависит от структуры данных:

• Односвязный список: поиск элемента требует последовательного обхода с начала списка до нужного элемента, так как прямого доступа по индексу нет. В худшем случае нужно пройти весь список — сложность O(n).

• Массив (список в Python): доступ к элементу по индексу происходит за константное время O(1), так как элементы расположены в памяти подряд. Но если нужно найти элемент по значению (без знания индекса), придётся перебрать элементы — O(n).

Пример в Python:

# Поиск по значению в списке
lst = [1, 2, 3, 4, 5]
value = 3
for i in lst:
    if i == value:
        print("Найдено")
        break

Здесь сложность O(n), так как в худшем случае придётся проверить все элементы.

В односвязном списке поиск по значению аналогичен — перебор элементов с начала до конца.