Big O: оцениваем скорость алгоритмов
Big O: оцениваем скорость алгоритмов
Ты написал функцию. Она работает. Но насколько она быстрая? И что будет, если данных станет в 100 раз больше?
Big O - это способ описать, как растёт время выполнения при увеличении входных данных.
Два правила, на которых держится вся нотация:
- Big O - верхняя граница роста. Запись O(n) значит «растёт не быстрее, чем линейно от n»: алгоритм может оказаться и быстрее, но не медленнее этой оценки (с точностью до множителя).
- Константы и младшие слагаемые отбрасываются. Нас интересует форма роста при больших n, а не точное число операций: 2n и n + 100 - это O(n), а 3n² + 5n - это O(n²), потому что при больших n слагаемое 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) | 1 | 1 | 1 |
| O(log n) | 3 | 10 | 20 |
| O(n) | 10 | 1 000 | 1 000 000 |
| O(n log n) | 30 | 10 000 | 20 000 000 |
| O(n²) | 100 | 1 000 000 | 1 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: пока не модифицируешь - копии в памяти нет. Это влияет на оценку памяти в реальных бенчмарках.
Как оценивать на глаз
- Один цикл по данным → O(n)
- Цикл в цикле → O(n²)
- Делим пополам на каждом шаге → O(log n) - так работает бинарный поиск и спуск по бинарному дереву
- Сортировка → O(n log n) - откуда берётся эта граница и когда её всё-таки обходят, разобрано в уроке про сортировку и бинарный поиск
- Обращение по индексу слайса → O(1): адрес элемента вычисляется арифметикой (начало + i * размер элемента). Обращение по ключу map, вставка и
delete(m, key)→ в среднем O(1) за счёт хеш-таблицы: слот находится по хешу ключа, без перебора 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) спуск по дереву. На миллионе строк разница между «мгновенно» и «таймаут» ровно здесь.