Алгоритмы, которые завершаются вовремя: проверка сложности

Вы написали функцию, запустили её на тестовых данных — всё работает. Потом она попадает на production данные — 500 000 строк вместо 500 — и запрос зависает. Это происходит постоянно, и почти всегда это проблема сложности, скрывающаяся в коде, который выглядел нормально для малых объёмов.

Почему ваш ноутбук вас обманул

Алгоритм O(n²), работающий на 100 элементах, выполняет 10 000 операций. Это мгновенно на любой машине. Запустите тот же алгоритм на 100 000 элементах — получите 10 миллиардов операций, минуты или часы вместо миллисекунд. Прыжок от n к n² не кажется опасным, пока n мал, что и объясняет, почему это проходит код-ревью и локальное тестирование.

Классический пример: проверка дубликатов вложенным циклом.

def has_duplicates(items):
    for i in range(len(items)):
        for j in range(i + 1, len(items)):
            if items[i] == items[j]:
                return True
    return False

Это O(n²). Замените на множество:

def has_duplicates(items):
    seen = set()
    for item in items:
        if item in seen:
            return True
        seen.add(item)
    return False

Теперь это O(n). Поиск в множестве в среднем O(1), поэтому функция масштабируется линейно, а не квадратично. На 10 000 элементах это разница между примерно 100 миллионами сравнений и 10 000.

Измеряйте перед оптимизацией

Не угадывайте. Используйте timeit для микробенчмарков:

import timeit
timeit.timeit(lambda: has_duplicates(list(range(5000))), number=10)

Для больших функций профилируйте с помощью cProfile:

python -m cProfile -s cumulative myscript.py

Смотрите на столбец cumtime. Если одна функция занимает 90% времени выполнения — это ваша цель. Оптимизация кода, который не является узким местом, тратит ваше время и добавляет сложность без выигрыша.

Типичные паттерны, которые незаметно становятся медленными

Повторяющиеся проверки принадлежности к списку. if x in my_list это O(n) для списка, но O(1) в среднем для множества или словаря. Если вы проверяете принадлежность внутри цикла, то O(n) проверка внутри O(n) цикла даёт вам O(n²) в целом. Замените список на множество — и вы вернётесь к O(n).

Конкатенация строк в цикле. В Python result += chunk внутри цикла по строкам это O(n²) в худшем случае, потому что строки неизменяемы и каждая конкатенация копирует всё. Используйте ''.join(chunks) вместо этого — это строит строку один раз.

Сортировка, когда она не нужна. sorted() это O(n log n). Если вы вызываете её внутри цикла только чтобы найти максимум или минимум на каждой итерации, используйте max()/min() (O(n)) или лучше, кучу (heapq), если вам нужно текущее экстремальное значение повторно. heapq.nlargest(k, data) это O(n log k), намного дешевле, чем сортировка всего списка, когда k мал.

Рекурсивные функции без мемоизации. Наивная рекурсивная последовательность Фибоначчи это O(2ⁿ), потому что она пересчитывает одни и те же подзадачи снова и снова. Добавьте functools.lru_cache и она упадёт до O(n):

from functools import lru_cache

@lru_cache(maxsize=None)
def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

Быстро читать Big O в реальном коде

Считайте вложенные циклы по одному и тому же входу — это обычно ваш показатель степени. Один цикл это O(n). Цикл внутри цикла это O(n²), если только диапазон внутреннего цикла не сужается (как в оптимизированной форме сортировки пузырьком, всё ещё O(n²) в худшем случае, но меньше сравнений). Рекурсивные вызовы, которые разбивают задачу пополам, как в двоичном поиске или сортировке слиянием, указывают на O(log n) или O(n log n). Рекурсивные вызовы, которые ветвятся на несколько вызовов за уровень, как наивная последовательность Фибоначчи, указывают на экспоненциальное время — сильный сигнал о том, что вам нужна мемоизация или переписывание в итеративный вид.

Хороший привычка: перед тем как писать вложенные циклы или рекурсию по пользовательским данным, спросите себя, какой может быть n в production, а не в вашем тестовом файле. Если n может достичь сотен тысяч, решение O(n²) нужно проверить перед развёртыванием.

Дополнительно о анализе сложности, алгоритмах сортировки и инструментах профилирования смотрите в разделах Python и Computer Science на Korra Studio.