← Все уроки

Урок 12.0

Сложность: O(1) и O(n)

▶ Теория

Два способа добраться до данных различаются по скорости. Про скорость алгоритма говорят так: сколько шагов он делает в зависимости от размера данных. Это и есть запись O(...).

numbers = list(range(1000))

print(numbers[500])     # O(1) — сразу по индексу
print(999 in numbers)   # O(n) — список просматривается целиком

Проверка даёт список numbers, индекс index и число target. Напечатайте:

  1. элемент по индексу — numbers[index];
  2. True или False — есть ли target в списке;
  3. где target встретился впервые — numbers.index(target);
  4. -1, если числа нет: numbers.index в этом случае падает, значит проверка нужна до вызова.

В третьей строке видно, сколько шагов пришлось пройти списку: это и есть O(n).

Подсказка

Индекс — это номер в квадратных скобках, элемент берут через [index].

Наличие проверяют словом in: target in numbers даёт True или False. Где элемент встретился первый раз, подскажет numbers.index(target), но если элемента нет, он вызовет ошибку — поэтому сначала стоит проверить in.