Нотация Big O: временная и пространственная сложность

Что означает Big O

Big O описывает, как растёт объём работы алгоритма при росте размера входных данных n. Она не измеряет секунды. Она отвечает на вопрос: «Если данных станет в десять раз больше, насколько медленнее или прожорливее станет этот код?»

Два правила делают её простой:

• Константы отбрасываются: 2n и n + 100 — это O(n).
• Важен только самый быстрорастущий член: n^2 + n — это O(n^2).

Обычно Big O указывают для худшего случая. Временная сложность считает операции, пространственная — дополнительную память.

Пять сложностей, которые встречаются чаще всего

O(1): константная

Работа не зависит от n.

def first(items):
    return items[0]

prices = {"apple": 3}
prices["apple"]  # поиск в словаре в среднем O(1)

O(log n): логарифмическая

Каждый шаг делит оставшиеся данные пополам. Типичный пример — бинарный поиск в отсортированном списке.

def binary_search(items, target):
    lo, hi = 0, len(items) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if items[mid] == target:
            return mid
        if items[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

O(n): линейная

Один проход по данным.

def total(items):
    s = 0
    for x in items:
        s += x
    return s

O(n log n): линейно-логарифмическая

Цена эффективной универсальной сортировки, например сортировки слиянием или встроенной sorted() во многих языках.

O(n^2): квадратичная

Цикл внутри цикла по тем же данным.

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

Как быстро они растут

Примерное число операций для разных размеров входа:

На десяти элементах быстро всё. На миллионе элементов квадратичный код делает триллион шагов — это разница между мгновенным ответом и запросом, который не завершится.

Как оценить свою функцию

1. Определите n: что растёт? Число пользователей, строк, символов.
2. Простые операции — O(1).
3. Цикл по n умножает тело на n.
4. Вложенные циклы перемножаются: два вложенных цикла по n дают O(n^2).
5. Последовательные блоки складываются, остаётся наибольший: O(n) + O(n^2) = O(n^2).
6. Деление пополам на каждом шаге даёт O(log n).
7. Ищите скрытую стоимость: x in list — O(n), x in set — в среднем O(1); срезы и копирование — O(n).

Классическое улучшение проверки на дубликаты:

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

Время падает с O(n^2) до O(n), но память растёт с O(1) до O(n) из-за множества. Такой обмен времени на память — одно из самых частых решений на практике.

Частые ошибки

• Считать функцию O(n), когда внутри цикла вызывается O(n)-код: это O(n^2).
• Запросы к базе в цикле: N запросов вместо одного часто и есть реальное узкое место веб-приложений.
• Полностью игнорировать константы: при малых n «худший» алгоритм с маленькой константой может оказаться быстрее. Если сомневаетесь — измеряйте.
• Оптимизировать код, который работает с десятью элементами: Big O важна там, где данные растут.