Справочник · модуль 17 «Финал»
Сколько шагов (O)
О большое показывает, как растёт число шагов, когда данных больше. У перебора O(n): шагов столько же, сколько элементов. У бинарного поиска O(log n): шагов совсем мало.
Сравнение из жизни
Как цена такси: важно не только сколько стоит, но и как растёт цена с расстоянием.
Пример
def find(items, target):
steps = 0
for i in range(len(items)):
steps = steps + 1
if items[i] == target:
return i, steps
return -1, steps
numbers = [3, 8, 15, 21, 34, 42, 57, 63]
print(find(numbers, 42))
print(find(numbers, 99))Результат
(5, 6) (-1, 8)
Учитель в уроке Вот перебор. Идём по списку и сравниваем каждое число с тем, что ищем. Нашли — вернули место и число шагов. Для сорока двух понадобилось шесть шагов. А числа девяносто девять в списке нет, и пришлось проверить все восемь.
Запомнить
Буква О — как вопрос: насколько дольше уборка, если игрушек вдвое больше? Важно, как растёт работа.
Тема из урока 17.1 «Поиск» курса PythonAZ.