Сложность алгоритмов (Big O)

Сложность алгоритмов — почему один код работает за секунду, а другой за час

Два разработчика решают одну задачу — проверить, есть ли дубликаты в массиве. Первый пишет два вложенных цикла, второй использует set. На 100 элементах оба работают мгновенно. На 10 миллионах — первый код работает минуты, второй — доли секунды. Разница не в железе, не в языке — в алгоритме.

Сложность алгоритмов — это умение оценить, как быстро растёт время работы кода при увеличении входных данных. Это must-have навык по трём причинам: • Производственный код. Когда твой pipeline обрабатывает миллионы записей, разница между O(n) и O(n²) — это разница между «работает» и «упал по таймауту». • Собеседования. «Какая сложность у этого кода? Как ускорить?» — звучит на каждом техническом интервью. • Выбор структуры данных. list vs set vs dict — выбор определяет производительность всего приложения.

Большая картина: Big O — язык для описания скорости роста

Big O — это нотация, которая описывает верхнюю границу роста количества операций при увеличении размера входных данных n. Она отвечает на вопрос: «Если я удвою данные, во сколько раз замедлится код?»

Аналогия: ты переезжаешь и считаешь количество рейсов на грузовике. Если у тебя 10 коробок и грузовик вмещает 10 — один рейс. 20 коробок — два рейса. Количество рейсов растёт линейно с числом коробок: O(n). Но если бы ты каждую коробку сравнивал с каждой другой (чтобы ничего не потерять) — это уже n×n сравнений, квадратичный рост: O(n²).

O(1) — константная: «не зависит от размера»

Время выполнения одинаково при 10 элементах и при 10 миллионах. Ты точно знаешь, где лежит нужное — никакого поиска.

# Доступ по индексу в массиве — O(1)
nums = [10, 20, 30, 40, 50]
first = nums[0]            # один шаг, независимо от длины

# Поиск по ключу в словаре — O(1)
user = {"name": "Аня", "age": 25}
name = user["name"]        # хеш-таблица → прямой доступ

# Добавление в конец списка — O(1) амортизированная
nums.append(60)            # обычно одна операция

# Проверка элемента в set — O(1)
seen = {1, 2, 3}
is_there = 2 in seen       # хеш → мгновенно

O(log n) — логарифмическая: «делим пополам на каждом шаге»

На каждом шаге отбрасываем половину данных. Миллиард элементов → всего ~30 шагов. Это магия логарифма: log₂(1 000 000 000) ≈ 30.

Аналогия: ищешь слово в бумажном словаре. Открываешь посередине — нужное слово левее или правее? Отбрасываешь половину, повторяешь. Три-четыре раза — и нашёл.

# Бинарный поиск — O(log n)
def binary_search(arr: list[int], target: int) -> int:
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1       # отбрасываем левую половину
        else:
            right = mid - 1      # отбрасываем правую половину
    return -1

# 1_000_000 элементов → максимум 20 шагов
# 1_000_000_000 элементов → максимум 30 шагов

O(n) — линейная: «один проход по всем данным»

Проходим по каждому элементу ровно один раз. Удвоили данные — удвоилось время. Самый честный и понятный рост.

# Поиск максимума — O(n)
def find_max(nums: list[int]) -> int:
    result = nums[0]
    for x in nums:              # один проход
        if x > result:
            result = x
    return result

# sum(), max(), min(), any(), all() — всё O(n)
# «x in list» — тоже O(n): перебирает до нахождения или до конца

O(n log n) — линейно-логарифмическая: «хорошая сортировка»

Это нижняя граница для сортировки сравнением — быстрее не получится (доказано математически). Данные рекурсивно делятся на части (log n уровней), на каждом уровне обрабатываются все n элементов.

# sorted() и list.sort() — O(n log n), алгоритм Timsort
nums = [5, 2, 8, 1, 9, 3]
sorted_nums = sorted(nums)     # новый список
nums.sort()                     # in-place, тот же O(n log n)

# heapq.nlargest(k, nums) — O(n log k), полезно когда k << n
import heapq
top3 = heapq.nlargest(3, nums)  # O(n log 3) ≈ O(n)

O(n²) — квадратичная: «каждый с каждым»

Два вложенных цикла по одним данным. Удвоил n — время выросло в 4 раза. На n = 10 000 уже заметно тормозит, на n = 100 000 — можно не дождаться.

Аналогия: на вечеринке каждый гость здоровается с каждым другим. 10 гостей — 45 рукопожатий. 100 — уже 4 950. 1 000 — почти полмиллиона.

# Проверка всех пар — O(n²)
def has_pair_with_sum(nums: list[int], target: int) -> bool:
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):   # вложенный цикл
            if nums[i] + nums[j] == target:
                return True
    return False

# Пузырьковая сортировка — тоже O(n²)
# Поэтому на практике используют Timsort — O(n log n)

Масштаб разницы на числах

Сложность встроенных операций Python

Знать сложность встроенных структур данных — must have. Главное правило: dict и set построены на хеш-таблице → поиск O(1). list — это массив → поиск O(n). Выбор структуры данных определяет производительность.

list (динамический массив)

• l[i] — доступ по индексу → O(1)
• l.append(x) — добавить в конец → O(1) амортизированная
• l.pop() — удалить последний → O(1)
• x in l — проверка наличия → O(n) — перебирает весь список!
• l.insert(0, x) — вставить в начало → O(n) — сдвигает все элементы
• l.pop(0) — удалить первый → O(n) — сдвигает все элементы
• l.sort() — сортировка → O(n log n) — Timsort
• len(l) — длина → O(1) — хранится как атрибут

dict (хеш-таблица)

• d[key], d.get(key) — чтение → O(1)
• d[key] = value — запись → O(1)
• key in d — проверка ключа → O(1)
• del d[key] — удаление → O(1)
• for k in d — перебор → O(n)

set (хеш-множество)

• s.add(x) — добавить → O(1)
• x in s — проверка наличия → O(1) — вот почему set быстрее list для поиска
• s.remove(x) — удалить → O(1)
• s1 & s2 — пересечение → O(min(len(s1), len(s2)))
• s1 | s2 — объединение → O(len(s1) + len(s2))

Пространственная сложность: сколько памяти жрёт алгоритм

Big O описывает не только время, но и дополнительную память. На собесе часто спрашивают оба показателя. Вопрос: «Сколько лишней памяти (помимо входных данных) потребляет алгоритм?»

# O(1) по памяти — работаем с парой переменных
def find_max(nums: list[int]) -> int:
    result = nums[0]
    for x in nums:
        result = max(result, x)
    return result               # доп. память: одна переменная result

# O(n) по памяти — создаём новую структуру размером n
def get_unique(nums: list[int]) -> set[int]:
    seen = set()                # в худшем случае все n элементов уникальны
    for x in nums:
        seen.add(x)
    return seen                 # доп. память: set размером до n

• Два указателя — O(1) по памяти (только пара индексов)
• Хеш-таблица (set/dict для поиска) — O(n) по памяти
• Рекурсия глубиной n — O(n) по памяти (стек вызовов)
• Сортировка in-place (list.sort()) — O(1) доп. памяти, sorted() — O(n)

Типичный трейдофф: время ↔ память. Хочешь быстрый поиск — заплати O(n) памяти за хеш-таблицу. Хочешь экономить память — готовься к O(n) времени на линейный поиск.

Как оценивать сложность: пошаговый алгоритм

Четыре шага, которые работают в 90% случаев:

Шаг 1. Считай циклы

Один цикл по n → O(n). Два вложенных цикла по n → O(n²). Цикл с делением пополам (while n > 0: n //= 2) → O(log n). Цикл от 1 до n, внутри цикл от 1 до n → O(n²).

Шаг 2. Учитывай операции внутри цикла

# Ловушка! Выглядит как O(n), но на деле O(n²)
data = [1, 2, 3, ..., n]
blacklist = [10, 20, 30, ..., m]        # m ≈ n

for x in data:                           # O(n) итераций
    if x in blacklist:                   # O(m) на каждую проверку!
        print(f"{x} в чёрном списке")
# Итого: O(n × m) ≈ O(n²)

# Фикс: превратить blacklist в set
blacklist_set = set(blacklist)           # O(m) один раз
for x in data:                           # O(n) итераций
    if x in blacklist_set:               # O(1) на проверку
        print(f"{x} в чёрном списке")
# Итого: O(n + m) ≈ O(n)

Шаг 3. Рекурсия — рисуй дерево вызовов

Для рекурсии считай количество вызовов. Каждый вызов порождает два новых → дерево удваивается → O(2ⁿ). Каждый вызов порождает один вызов на n−1 → линейная цепочка → O(n). Каждый вызов делит данные пополам → O(log n).

# O(2^n) — каждый вызов порождает ДВА
def fib_naive(n: int) -> int:
    if n <= 1:
        return n
    return fib_naive(n - 1) + fib_naive(n - 2)
# fib_naive(40) — уже тормозит (>1 млрд вызовов)

# O(n) — мемоизация: каждое значение считается ОДИН раз
from functools import lru_cache

@lru_cache(maxsize=None)
def fib_memo(n: int) -> int:
    if n <= 1:
        return n
    return fib_memo(n - 1) + fib_memo(n - 2)
# fib_memo(1000) — мгновенно

Шаг 4. Амортизированная сложность

Некоторые операции «обычно быстрые, но иногда медленные». list.append() — почти всегда O(1), но когда массив заполнен, Python выделяет новый блок памяти побольше и копирует всё: O(n). Однако такое происходит всё реже и реже. Если усреднить по всем вызовам — получится O(1) амортизированная.

Аналогия: ты копишь монеты в копилку. Бросил монету — 1 секунда. Когда копилка полна, покупаешь новую вдвое больше и пересыпаешь — это долго. Но на следующие тысячи бросков одна «дорогая» операция размазывается, и в среднем каждый бросок — O(1).

Оптимизация: три приёма, которые решают 80% задач

На собеседованиях часто дают «наивное» решение O(n²) и просят ускорить до O(n) или O(n log n). Вот три основных паттерна.

Приём 1. Замена list на set/dict — убиваем вложенный поиск

# Задача: найти два числа, дающие в сумме target (Two Sum)

# Наивно — O(n²): перебираем все пары
def two_sum_slow(nums: list[int], target: int) -> list[int]:
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] + nums[j] == target:
                return [i, j]
    return []

# Через dict — O(n): запоминаем виденные числа
def two_sum_fast(nums: list[int], target: int) -> list[int]:
    seen = {}                              # число → индекс
    for i, x in enumerate(nums):
        complement = target - x
        if complement in seen:             # O(1)
            return [seen[complement], i]
        seen[x] = i
    return []

Принцип: вместо перебора всех пар «запоминай то, что уже видел». Dict или set превращают вложенный поиск O(n) в O(1).

Приём 2. Два указателя — работает на отсортированных данных

# Пара с нужной суммой в ОТСОРТИРОВАННОМ массиве — O(n)
def two_sum_sorted(nums: list[int], target: int) -> list[int]:
    left, right = 0, len(nums) - 1
    while left < right:
        s = nums[left] + nums[right]
        if s == target:
            return [left, right]
        elif s < target:
            left += 1          # сумма мала → двигаем левый вправо
        else:
            right -= 1         # сумма велика → двигаем правый влево
    return []

# Каждый элемент посещается максимум один раз → O(n)

Принцип: один указатель в начале, другой в конце. Сужаем диапазон, опираясь на свойство упорядоченности. Работает для задач на пары, палиндромы, слияние.

Приём 3. Скользящее окно — подмассив с условием

# Максимальная сумма подмассива длины k — O(n)
def max_subarray_sum(nums: list[int], k: int) -> int:
    window_sum = sum(nums[:k])             # начальное окно
    best = window_sum
    for i in range(k, len(nums)):
        window_sum += nums[i] - nums[i - k]  # добавляем новый, убираем старый
        best = max(best, window_sum)
    return best

# Наивный подход: для каждой позиции считать sum(nums[i:i+k]) → O(n × k)
# Скользящее окно: O(n), потому что каждый элемент добавляется и удаляется один раз

Принцип: вместо пересчёта суммы/состояния «с нуля» на каждом шаге — сдвигаем окно, добавляя один элемент справа и убирая один слева. Фиксированный размер окна → O(n). Переменный размер (expand/shrink) → тоже O(n), если каждый элемент добавляется и удаляется максимум один раз.

🎯 На собеседовании

Собираем всё вместе

Сложность алгоритмов — это не абстрактная математика, а практический инструмент. O(1) → O(log n) → O(n) → O(n log n) → O(n²) — пять классов, которые покрывают 95% реальных задач. Ключевое: смотри не только на циклы, но и на операции внутри них. x in list внутри цикла — тихий убийца производительности.

Если запомнить одну вещь: замена list на set/dict для поиска — самая частая оптимизация, которая превращает O(n²) в O(n). А три паттерна — хеш-таблица, два указателя, скользящее окно — решают подавляющее большинство задач на оптимизацию.

Дальше: SQL и Python продвинутый — где сложность алгоритмов применяется на практике каждый день.