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

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

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

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

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

// 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-массив уже хеш-таблица.

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

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

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

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

// 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);
    }
}

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

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

Один цикл по данным → O(n)
Цикл в цикле → O(n²)
Делим пополам на каждом шаге → O(log n)
Сортировка → O(n log n)
Обращение по индексу или ключу → O(1)

Big O описывает худший случай. `contains` может найти элемент первым, но мы говорим O(n), потому что в худшем случае проверим все.

Amortized complexity

В Go append обычно O(1), но иногда O(n) - когда слайс расширяется. В среднем это O(1) amortized.

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)

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

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

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