Четыре простых правила
Чтобы превратить вопрос «сколько шагов делает этот код» в класс Big O, нужны четыре правила:
1. Учитывайте худший случай — считайте наибольшее число шагов, которое может понадобиться коду.
2. Отбрасывайте константы — O(2n) и O(n/2) — это оба O(n).
3. Отбрасывайте младшие члены — O(n + n²) — это O(n²).
4. Разные входные данные — разные буквы — два разных списка дают O(a · b), а не O(n²).
Ниже для каждого правила есть один пример.
Правило 1: учитывайте худший случай
Линейному поиску может повезти: если значение стоит в начале, хватит одного шага. Big O не учитывает везение и описывает худший случай для списка — значение стоит последним или отсутствует, и проверяются все n элементов.
Поэтому линейный поиск — это O(n), хотя часто он завершается раньше. Худший случай — это обещание, которое алгоритм может сдержать всегда.
Лучший и худший случай поиска
Поиск первого слова занимает 1 шаг. Поиск отсутствующего слова занимает все 5. Big O учитывает 5: линейный поиск — это O(n).
Вывод: полная программа на Python
def search(words, target):
steps = 0
for w in words:
steps += 1
if w == target:
break
return steps
words = ["one", "two", "three", "four", "five"]
print('лучший случай ("one"):', search(words, "one"), "шаг")
print('худший случай ("six"):', search(words, "six"), "шагов")
Правило 2: отбрасывайте константы
Цикл, который посещает каждый второй элемент, делает n/2 шагов. Работы вдвое меньше, но форма роста не меняется: входные данные удваиваются — удваиваются и шаги.
Big O учитывает только форму, поэтому O(n/2), O(n) и O(2n) — это один и тот же класс: линейное время.
Вдвое меньше шагов — всё равно O(n)
Цикл перескакивает на 2 и посещает 4 из 8 элементов. Если список удвоится, шаги тоже удвоятся — поэтому n/2 шагов — это всё равно линейный рост, O(n).
Вывод: полная программа на Python
nums = [3, 1, 4, 1, 5, 9, 2, 6]
steps = 0
# Посещаем каждый второй элемент: n/2 шагов.
for i in range(0, len(nums), 2):
print(nums[i], end=" ")
steps += 1
print()
print("элементов:", len(nums), "шагов:", steps)
Правило 3: отбрасывайте младшие члены
Код часто сочетает части с разной стоимостью: простой цикл (n шагов), за которым следуют вложенные циклы (n² шагов). Всего получается n + n².
С ростом n часть n² поглощает всё остальное — при n = 1000 это миллион шагов против тысячи. Big O оставляет только самый быстрорастущий член: O(n + n²) становится O(n²).
n + n² шагов
Для 6 элементов простой цикл добавляет 6 шагов, а вложенные циклы — 36, всего 42. Квадратичный член уже преобладает, и его отрыв только растёт с ростом n.
Вывод: полная программа на Python
nums = [1, 2, 3, 4, 5, 6]
steps = 0
# Один простой цикл: n шагов.
for n in nums:
steps += 1
# Цикл внутри цикла: n * n шагов.
for x in nums:
for y in nums:
steps += 1
print("n =", len(nums))
print("n + n*n =", steps)
Правило 4: разные входные данные — разные буквы
Когда вложенные циклы проходят по двум разным входным данным, число шагов равно a · b — произведению двух длин. Называть это O(n²) было бы ошибкой: входные данные могут сильно различаться по размеру.
Честный класс — O(a · b). Он становится O(n²) только в особом случае, когда оба входа — одни и те же данные.
Два разных списка
3 цвета умножить на 2 животных — это 6 шагов. Сложность — O(a · b): если список животных растёт, а список цветов нет, важно только b.
Вывод: полная программа на Python
colors = ["red", "green", "blue"]
animals = ["cat", "dog"]
steps = 0
for c in colors:
for a in animals:
steps += 1
print("цветов:", len(colors), "животных:", len(animals))
print("шагов:", steps)
Ограничения Big O
Big O — намеренно грубый инструмент, и полезно знать, что он скрывает.
Он видит только худший случай. Алгоритм с пугающим худшим случаем может быть отличным на практике, если этот случай редок. Иногда важен именно средний случай.
Он игнорирует константы. На бумаге 1000 · n и n — один и тот же класс. На небольших входных данных «более медленный» алгоритм O(n²) с очень лёгкими шагами может обогнать «более быстрый» алгоритм O(n) с тяжёлыми шагами.
Используйте Big O, чтобы сравнивать, как алгоритмы масштабируются. Чтобы узнать реальную скорость на реальных данных, делайте замеры.