Урок 12.0
Два способа добраться до данных различаются по скорости. Про скорость алгоритма
говорят так: сколько шагов он делает в зависимости от размера данных. Это и есть
запись O(...).
numbers = list(range(1000))
print(numbers[500]) # O(1) — сразу по индексу
print(999 in numbers) # O(n) — список просматривается целиком
numbers[500] не зависит от длины списка: список знает, где лежит элемент,
это O(1);999 in numbers идёт по элементам, пока не найдёт: в худшем случае — n шагов,
это O(n);O — не секунды, а рост числа шагов: O(1) на графике — ровная линия,
O(n) — поднимается с размером.Проверка даёт список numbers, индекс index и число target. Напечатайте:
numbers[index];True или False — есть ли target в списке;target встретился впервые — numbers.index(target);-1, если числа нет: numbers.index в этом случае падает, значит проверка нужна
до вызова.В третьей строке видно, сколько шагов пришлось пройти списку: это и есть O(n).
Индекс — это номер в квадратных скобках, элемент берут через [index].
Наличие проверяют словом in: target in numbers даёт True или False.
Где элемент встретился первый раз, подскажет numbers.index(target), но если
элемента нет, он вызовет ошибку — поэтому сначала стоит проверить in.