Как структура кода раскрывает сложность

Как идентифицировать Big O из кода

Big O скрывается в форме вашего кода. Четыре паттерна охватывают большинство случаев:

Один цикл по N элементам: O(N)

# O(N): один проход по списку
for item in list_of_n_items:
    process(item)

Вложенные циклы, каждый по N элементам: O(N²)

# O(N²): каждый элемент соединён с каждым другим элементом
for item_a in list_of_n_items:
    for item_b in list_of_n_items:
        compare(item_a, item_b)

Поиск в постоянное время: O(1)

Доступ по индексу массива, поиск в таблице хеширования — один шаг независимо от размера.

Разделяй и властвуй (сократить проблему вполовину на каждом шаге): O(log N)

Двоичный поиск: каждая проверка сокращает оставшиеся элементы вполовину.

---

Скрытый O(N²): список внутри цикла

# Это выглядит как O(N), но на самом деле это O(N²)
visited = []
for item in list_of_n_items:
    if item not in visited:   # сканирует весь visited: O(N)
        visited.append(item)  # весь цикл: O(N²)

Строка if item not in visited сканирует каждый элемент visited на каждой итерации. Сканирование списка стоит O(N). Цикл, который работает N раз, каждый раз выполняя O(N) работы: O(N) × O(N) = O(N²).

Этот паттерн появляется в 1000+ проектах с открытым исходным кодом. Исправление занимает один символ: замените visited = [] на visited = set(). Проверка членства в наборе стоит O(1), не O(N). Одно изменение. Те же результаты. В 1000 раз быстрее при N=1000.

Классифицируйте & исправьте этот код

Прочитайте этот код:

result = []
for name in student_names:
    if name not in result:
        result.append(name)

Теория встречает практику

Big O в дикой природе

Big O — это не просто теория. Она отделяет программы, которые заканчиваются за секунды, от программ, которые занимают 17 минут — на точно такую же задачу.

Реальный пример: обнаружение цикла зависимостей в системе сборки.

Когда вы устанавливаете программное обеспечение, ваш компьютер разрешает граф зависимостей: пакет A нужен B, B нужен C, и так далее. Система сборки проверяет этот граф на наличие циклов.

Алгоритм обнаружения цикла O(N²) работает хорошо при N=100 пакетах. При N=50000 пакетов (реальный проект): это занимает 17 минут. Исправление O(N): 10 секунд.

Этот точный дефект существует в GHC (компилятор Haskell), pip (менеджер пакетов Python), Maven (система сборки Java), Cargo (менеджер пакетов Rust), & 1000+ других проектов.

Не потому, что их авторы были небрежны. visited = [] была написана, когда N была малой. Код отвердел. N выросла. Никто не заметил, пока сборка не заняла полчаса.

Big O — это словарь, который позволяет вам назвать то, что произошло — & исправить это.

---

Хотите углубиться? Наш курс unhamming включает полную главу о Big O, MOAD-0001 (реальный дефект O(N²), найденный в 1000+ проектах с открытым исходным кодом), & почему назвать паттерн позволяет вам найти его везде. См. Недостающая глава: сложность алгоритмов.

Предскажите время сборки

Система сборки использует обнаружение цикла O(N²).

Измеренное время сборки:

- N=100 пакетов: 0,01 секунды

- N=1000 пакетов: 1 секунда

Для O(N²): время масштабируется как (N_new / N_old)².

Для O(N): время масштабируется как (N_new / N_old).