Big O: оцениваем скорость алгоритмов

Big O: оцениваем скорость алгоритмов

Ты написал функцию. Она работает. Но насколько она быстрая? И что будет, если данных станет в 100 раз больше?

Big O - это способ описать, как растёт время выполнения при увеличении входных данных.

Два правила, на которых держится вся нотация:

  • Big O - верхняя граница роста. Запись O(n) значит «растёт не быстрее, чем линейно от n»: алгоритм может оказаться и быстрее, но не медленнее этой оценки (с точностью до множителя).
  • Константы и младшие слагаемые отбрасываются. Нас интересует форма роста при больших n, а не точное число операций: 2n и n + 100 - это O(n), а 3n² + 5n - это O(n²), потому что при больших n слагаемое n² всё равно перевешивает.

Кривые Big-O: O(1), O(log n), O(n), O(n log n), O(n²) на одной сетке

ℹ️ O(1) у хеш-таблицы - в среднем, а не всегда

Асимптотику обычно называют одним числом, но у структур с хешированием их два, и разница практическая:

ОперацияВ среднемВ худшем случае
поиск в хеш-таблицеO(1)O(n) - все ключи в одном бакете
вставка в динамический массивO(1) амортизированноO(n) - на перевыделении
поиск в B-tree / отсортированном массивеO(log n)O(log n)

«Амортизированно» - это не «в среднем по входам»: на любой серии из n вставок суммарная цена O(n), поэтому каждая в пересчёте на серию стоит O(1). У хеш-таблицы средний случай вероятностный, а у append амортизация гарантирована для любой серии.

Худший случай у хеш-таблицы - не теоретическая экзотика: он достижим подобранными ключами, и на этом строят атаку hash-flooding. Поэтому языки рандомизируют хеш-функцию: Go выбирает случайный сид для каждой map, Python - для строк и bytes при старте процесса (хеш целых чисел в Python не рандомизирован).

Дальше в курсе O(1) для map будет писаться коротко, но читать это стоит как «в среднем O(1)». Разбор устройства - в уроке про хеш-таблицу изнутри.

Основные сложности

// O(1) - константа. Не зависит от размера данных.
func getFirst(s []int) int {
    return s[0]
}

// O(n) - линейная. Перебираем все элементы.
func contains(s []int, target int) bool {
    for _, v := range s {
        if v == target {
            return true
        }
    }
    return false
}

// O(n²) - квадратичная. Вложенные циклы.
func hasDuplicate(s []int) bool {
    for i := 0; i < len(s); i++ {
        for j := i + 1; j < len(s); j++ {
            if s[i] == s[j] {
                return true
            }
        }
    }
    return false
}

// O(log n) - логарифмическая. Делим пополам на каждом шаге.
func binarySearch(s []int, target int) int {
    lo, hi := 0, len(s)-1
    for lo <= hi {
        mid := (lo + hi) / 2
        switch {
        case s[mid] == target:
            return mid
        case s[mid] < target:
            lo = mid + 1
        default:
            hi = mid - 1
        }
    }
    return -1
}
<?php
declare(strict_types=1);

final class Complexity
{
    /** O(1) - доступ по индексу */
    public function getFirst(array $s): int
    {
        return $s[0];
    }

    /** O(n) - линейный обход. in_array() тоже O(n) */
    public function contains(array $s, int $target): bool
    {
        foreach ($s as $v) {
            if ($v === $target) {
                return true;
            }
        }
        return false;
    }

    /** в среднем O(1) через хеш-таблицу - PHP-массив сам по себе hash map */
    public function containsFast(array $set, int $target): bool
    {
        return isset($set[$target]);
    }

    /** O(n^2) - вложенные циклы */
    public function hasDuplicate(array $s): bool
    {
        $n = count($s);
        for ($i = 0; $i < $n; $i++) {
            for ($j = $i + 1; $j < $n; $j++) {
                if ($s[$i] === $s[$j]) {
                    return true;
                }
            }
        }
        return false;
    }

    /** O(log n) - бинарный поиск (нет native, пишем руками) */
    public function binarySearch(array $s, int $target): int
    {
        $lo = 0;
        $hi = count($s) - 1;
        while ($lo <= $hi) {
            $mid = intdiv($lo + $hi, 2);
            if ($s[$mid] === $target) {
                return $mid;
            }
            if ($s[$mid] < $target) {
                $lo = $mid + 1;
            } else {
                $hi = $mid - 1;
            }
        }
        return -1;
    }
}

В PHP та же классификация работает. Важные нюансы: count() - O(1) (Zend кеширует длину массива), а вот in_array() - O(n). Для проверки наличия за среднее O(1) используй isset($map[$key]), потому что PHP-массив уже хеш-таблица.

# O(1) - константа. Не зависит от размера данных.
# list - динамический массив указателей, доступ по индексу за O(1).
def get_first(s: list[int]) -> int:
    return s[0]


# O(n) - линейная. Перебираем все элементы.
# Оператор `in` для list делает ровно то же самое - линейный обход.
def contains(s: list[int], target: int) -> bool:
    for v in s:
        if v == target:
            return True
    return False


# в среднем O(1) через хеш-таблицу: set и dict - хеш-таблицы
def contains_fast(items: set[int], target: int) -> bool:
    return target in items


# O(n^2) - квадратичная. Вложенные циклы.
def has_duplicate(s: list[int]) -> bool:
    for i in range(len(s)):
        for j in range(i + 1, len(s)):
            if s[i] == s[j]:
                return True
    return False


# O(log n) - логарифмическая. Делим пополам на каждом шаге.
# В stdlib есть готовый bisect.bisect_left, здесь - руками для наглядности.
def binary_search(s: list[int], target: int) -> int:
    lo, hi = 0, len(s) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if s[mid] == target:
            return mid
        if s[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

В PHP нет native sort.Search или slices.BinarySearch - бинарный поиск пишется руками. Зато array_search() есть, но это O(n) (линейный обход).

Таблица сложностей

Сложность10 элементов1000 элементов1 000 000 элементов
O(1)111
O(log n)31020
O(n)101 0001 000 000
O(n log n)3010 00020 000 000
O(n²)1001 000 0001 000 000 000 000

Пространственная сложность

Время - не единственный ресурс. Память тоже стоит денег.

// O(1) по памяти - используем только переменные
func sum(s []int) int {
    total := 0
    for _, v := range s {
        total += v
    }
    return total
}

// O(n) по памяти - создаём новый слайс
func double(s []int) []int {
    result := make([]int, len(s))
    for i, v := range s {
        result[i] = v * 2
    }
    return result
}
<?php
declare(strict_types=1);

final class MemoryComplexity
{
    /** O(1) - только переменные */
    public function sum(array $s): int
    {
        $total = 0;
        foreach ($s as $v) {
            $total += $v;
        }
        return $total;
    }

    /** O(n) - новый массив. array_map тоже O(n) по памяти */
    public function double(array $s): array
    {
        return array_map(static fn (int $v): int => $v * 2, $s);
    }
}
# O(1) по памяти - используем только переменные
# (встроенный sum(s) делает то же самое за O(1) дополнительной памяти)
def total_of(s: list[int]) -> int:
    total = 0
    for v in s:
        total += v
    return total


# O(n) по памяти - создаём новый список
# (генератор (v * 2 for v in s) был бы O(1): элементы считаются лениво)
def double(s: list[int]) -> list[int]:
    return [v * 2 for v in s]

Алгоритм, которому хватает O(1) дополнительной памяти и который меняет данные прямо на месте, без копии, называют in-place (на месте). Пример - разворот слайса обменом элементов с двух концов; противоположный пример - double выше, он строит новый слайс.

PHP-массивы передаются по значению, но Zend применяет copy-on-write: пока не модифицируешь - копии в памяти нет. Это влияет на оценку памяти в реальных бенчмарках.

Как оценивать на глаз

  1. Один цикл по данным → O(n)
  2. Цикл в цикле → O(n²)
  3. Делим пополам на каждом шаге → O(log n) - так работает бинарный поиск и спуск по бинарному дереву
  4. Сортировка → O(n log n) - откуда берётся эта граница и когда её всё-таки обходят, разобрано в уроке про сортировку и бинарный поиск
  5. Обращение по индексу слайса → O(1): адрес элемента вычисляется арифметикой (начало + i * размер элемента). Обращение по ключу map, вставка и delete(m, key) → в среднем O(1) за счёт хеш-таблицы: слот находится по хешу ключа, без перебора
  6. len(s) и cap(s) → O(1): слайс хранит длину и ёмкость прямо в своём заголовке, считать элементы не нужно. То же у len для map, строки и канала

⚠️ Частая ошибка: судить по удачному случаю

contains может найти элемент первым, но сложность мы называем O(n) - потому что в худшем случае придётся проверить все элементы, и планировать надо по нему.

Точная формулировка: Big O описывает рост, а какой именно случай имеется в виду - надо указывать. По умолчанию в этом курсе (и обычно в литературе) речь о худшем случае, но не всегда: хеш-таблица - тот самый пример, где практический смысл имеет средний случай, потому что худший (все ключи в одном бакете) при нормальной хеш-функции не встречается. Поэтому у неё пишут «в среднем O(1)», а не «O(n)» - см. врезку в начале урока.

Проверочный вопрос к любой оценке сложности: про какой случай речь? Если ответа нет, оценка неполная.

Amortized complexity

В Go append обычно O(1), но иногда O(n) - когда слайс расширяется. Дорогие расширения редки, поэтому серия из n вызовов в сумме стоит O(n), а один вызов в пересчёте на серию - O(1). Это и называется амортизированной сложностью (amortized), и это гарантия для любой серии, а не «в среднем по удачным входам» (см. врезку в начале урока). Почему расширение случается редко и как именно растёт capacity - в уроке про устройство слайсов.

s := make([]int, 0)
for i := 0; i < 1000; i++ {
    s = append(s, i) // обычно O(1), иногда O(n)
}
// В сумме: O(n), значит каждый append в пересчёте на серию O(1)
<?php
declare(strict_types=1);

$s = [];
for ($i = 0; $i < 1000; $i++) {
    $s[] = $i; // amortized O(1) - Zend сам расширяет внутренний buffer
}
// count($s) === 1000, общая стоимость O(n)
s: list[int] = []
for i in range(1000):
    s.append(i)  # обычно O(1), иногда O(n) - list перевыделяет массив указателей
# В сумме: O(n), значит каждый append в пересчёте на серию O(1).
# list растёт не вдвое, а примерно на 1/8 (плюс константа) - перевыделений
# больше, чем у Go-слайса, но амортизированная оценка та же.

Реальной capacity у PHP-массива нет (Zend engine скрывает), но логика та же: расширение буфера происходит редко и амортизированно даёт O(1).

Практические выводы

  • O(n²) на 10 000 элементах - уже заметно тормозит
  • O(n log n) на миллионе - нормально
  • Если можешь заменить O(n²) на O(n) с помощью map - делай

Та же арифметика работает не только в коде. Запрос без индекса - это O(n) перебор всей таблицы, а индекс превращает его в O(log n) спуск по дереву. На миллионе строк разница между «мгновенно» и «таймаут» ровно здесь.

Зарегистрируйтесь бесплатно, чтобы пройти квиз, решить задание с автопроверкой, вести прогресс.