Алгоритми, які закінчуються вчасно: перевірка складності

Ви напишете функцію, запустите її на тестових даних — і все працює. Потім вона потрапляє в production з 500,000 рядків замість 500 — і request часує. Це трапляється постійно, і майже завжди це проблема складності, прихована в коді, що виглядав розумно в малому масштабі.

Чому ваш ноутбук вам брехав

Алгоритм O(n²), запущений на 100 елементах, виконує 10,000 операцій. Це миттєво на будь-якій машині. Запустіть той же алгоритм на 100,000 елементах — і ви маєте 10 мільярдів операцій, хвилини або години замість мілісекунд. Стрибок від n до n² не здається небезпечним, поки n не стане великим, що саме тому це проходить code review та локальне тестування.

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

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²). Замініть його на set:

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

Тепер це O(n). Пошук у set у середньому 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% часу виконання, це ваша мета. Оптимізація коду, який не є вузьким місцем, тратить ваш час та додає складність без користі.

Типові схеми, що тихо стають повільними

Повторена перевірка належності до list. if x in my_list це O(n) для list, але O(1) у середньому для set або dict. Якщо ви перевіряєте належність всередину циклу, та O(n) перевірка всередину O(n) циклу дає вам O(n²) загалом. Замініть list на set і ви повертаєтеся до O(n).

Конкатенація string всередину циклу. У Python, result += chunk всередину циклу над string це O(n²) у гіршому випадку, тому що string незмінні, і кожна конкатенація копіює все. Використовуйте ''.join(chunks) замість цього — він будує string один раз.

Сортування, коли вам це не потрібно. sorted() це O(n log n). Якщо ви викликаєте його всередину циклу, щоб просто знайти max або min кожної ітерації, використовуйте max()/min() (O(n)) або краще, heap (heapq), якщо вам потрібна біжуча екстремум повторно. heapq.nlargest(k, data) це O(n log k), набагато дешевше за сортування всього list, коли k малий.

Рекурсивні функції без memoization. Наївна рекурсивна Fibonacci це 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 з реального коду, швидко

Порахуйте вкладені цикли над тим же input — це зазвичай ваш показник. Один цикл це O(n). Цикл всередину циклу це O(n²), якщо діапазон внутрішнього циклу не скорочується (як у оптимізованій формі bubble sort, все ще O(n²) у гіршому випадку, але менше порівнянь). Рекурсивні виклики, що розділяють задачу навпіл, як binary search або merge sort, вказують на O(log n) або O(n log n). Рекурсивні виклики, що розгалужуються на кілька викликів на рівні, як наївна Fibonacci, вказують на експоненціальний час — це сильний сигнал, що вам потрібна memoization або ітеративне переписування.

Добра звичка: перед тим, як писати вкладені цикли або рекурсію над user-facing даними, запитайте себе, якою може бути n в production, а не у вашому тестовому файлі. Якщо n може досягти шести цифр, O(n²) рішення потребує другого погляду перед випуском.

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