Основные классы временной сложности алгоритмов
Временные сложности алгоритмов — это способ оценить, как быстро растёт время выполнения кода, когда увеличивается количество данных.
- O(1) — супербыстро (лучшее, что может быть)
- O(log n) — очень быстро (бинарный поиск, деревья)
- O(n) — нормально / быстро (один проход по массиву)
- O(n log n) — средне / довольно быстро (умные сортировки)
- O(n²) — медленно (вложенные циклы, пузырёк)
- O(n³) — очень медленно (тройные циклы)
- O(2ⁿ) — ужасно медленно (перебор подмножеств)
- O(n!) — катастрофически медленно (перестановки, полный перебор)
Примеры:
O(1) — Константная
Алгоритм работает за одинаковое время, независимо от размера входных данных.
Доступ к элементу массива по индексу:
$arr = [10, 20, 30, 40];
echo $arr[2]; // O(1)O(log n) — Логарифмическая
Каждый шаг уменьшает проблему в два раза. Очень быстрый рост.
Бинарный поиск в отсортированном массиве:
function binarySearch($arr, $target) {
$l = 0;
$r = count($arr) - 1;
while ($l <= $r) {
$mid = intdiv($l + $r, 2);
if ($arr[$mid] == $target) return $mid;
if ($arr[$mid] < $target) {
$l = $mid + 1;
} else {
$r = $mid - 1;
}
}
return -1;
}O(n) — Линейная
Время растёт пропорционально количеству элементов. Проходим все элементы один раз.
function linearSearch($arr, $target) {
foreach ($arr as $item) {
if ($item === $target) return true;
}
return false;
}O(n log n) — Линейно-логарифмическая
Чаще всего в «умных» сортировках. Рекурсивная сортировка слиянием.
function mergeSort($arr) {
if (count($arr) <= 1) return $arr;
$mid = intdiv(count($arr), 2);
$left = array_slice($arr, 0, $mid);
$right = array_slice($arr, $mid);
return merge(
mergeSort($left),
mergeSort($right)
);
}
function merge($left, $right) {
$result = [];
while (count($left) && count($right)) {
if ($left[0] < $right[0]) {
$result[] = array_shift($left);
} else {
$result[] = array_shift($right);
}
}
return array_merge($result, $left, $right);
}O(n²) — Квадратичная
Каждый элемент сравнивается с каждым → вложенные циклы.
Пузырьковая сортировка
function bubbleSort($arr) {
$n = count($arr);
for ($i = 0; $i < $n; $i++) {
for ($j = 0; $j < $n - 1; $j++) {
if ($arr[$j] > $arr[$j + 1]) {
[$arr[$j], $arr[$j + 1]] = [$arr[$j + 1], $arr[$j]];
}
}
}
return $arr;
}O(n³) — Кубическая
Три вложенных цикла. Обычное умножение матриц.
function multiplyMatrices($A, $B) {
$n = count($A);
$C = array_fill(0, $n, array_fill(0, $n, 0));
for ($i = 0; $i < $n; $i++) {
for ($j = 0; $j < $n; $j++) {
for ($k = 0; $k < $n; $k++) {
$C[$i][$j] += $A[$i][$k] * $B[$k][$j];
}
}
}
return $C;
}O(2ⁿ) — Экспоненциальная
Количество операций удваивается с каждым n.
Перебор всех подмножеств
function subsets($arr) {
if (!$arr) return [[]];
$first = array_shift($arr);
$rest = subsets($arr);
$withFirst = [];
foreach ($rest as $subset) {
$withFirst[] = array_merge([$first], $subset);
}
return array_merge($rest, $withFirst);
}O(n!) — Факториальная
Самые медленные — все перестановки.
function permutations($arr) {
if (count($arr) <= 1) return [$arr];
$result = [];
foreach ($arr as $i => $val) {
$rest = $arr;
unset($rest[$i]);
$rest = array_values($rest);
foreach (permutations($rest) as $perm) {
$result[] = array_merge([$val], $perm);
}
}
return $result;
}Советы:
Часто правильный выбор структуры данных решает проблему:
- массив — быстрый доступ O(1), но поиск O(n)
- хеш-таблица (в PHP array как map) — поиск O(1)
- дерево — поиск O(log n)
Пример:
если тебе нужно часто искать по ключу → используй ассоциативный массив, а не список.
Избегай вложенных циклов
Каждый вложенный цикл повышает сложность:
- один цикл → O(n)
- два цикла → O(n²)
- три → O(n³)
ПЛОХО: двойной цикл O(n²)
Задача:
У нас есть список пользователей и список заказов.
Для каждого пользователя нужно найти его заказы.
Наивный подход:
$users = [
['id' => 1, 'name' => 'Alex'],
['id' => 2, 'name' => 'John'],
];
$orders = [
['id' => 10, 'user_id' => 1],
['id' => 11, 'user_id' => 2],
['id' => 12, 'user_id' => 1],
];
// ❌ O(n²)
$result = [];
foreach ($users as $user) {
foreach ($orders as $order) {
if ($order['user_id'] === $user['id']) {
$result[$user['id']][] = $order;
}
}
}Почему плохо?
- на 100 пользователей и 10 000 заказов → 1 000 000 сравнений
- каждый новый пользователь = новый полный проход по заказам
ХОРОШО: создаём индекс (мапу) заранее → O(n)
Алгоритм:
- сначала группируем заказы по user_id
- потом просто берём готовые группы
// индексируем заказы O(n)
$ordersByUser = [];
foreach ($orders as $order) {
$ordersByUser[$order['user_id']][] = $order;
}
// Теперь массив выглядит так:
[
1 => [
['id' => 10, 'user_id' => 1],
['id' => 12, 'user_id' => 1],
],
2 => [
['id' => 11, 'user_id' => 2],
]
]
// выбираем для каждого пользователя O(n)
$result = [];
foreach ($users as $user) {
$result[$user['id']] = $ordersByUser[$user['id']] ?? [];
}Что получили?
Было: двойной цикл: O(n * m) = O(n²)
Стало:
✔ один проход для индексации: O(n)
✔ один проход по пользователям: O(n)
Итог: O(n)
Гораздо быстрее, особенно когда данных много.
Используй встроенные функции вместо самописных циклов
PHP-функции (array_map, array_filter, array_unique, sort) написаны на C.
Они почти всегда быстрее, чем твой foreach.
Кэшируй всё, что повторяется
Если функция делает один и тот же дорогой расчёт много раз, кешируй:
$cache = [];
function expensive($value) {
global $cache;
if (isset($cache[$value])) return $cache[$value];
// дорогой рассчет
return $cache[$value] = slowOperation($value);
}Кэш превращает O(n²) → O(n)
Профилируй, а не гадай
Самая частая ошибка — оптимизация “на глаз”.
Используй:
- xhprof
- Blackfire
- Laravel Telescope / Clockwork
Посмотри, где действительно тормозит.
Задавай себе правильный вопрос
При написании кода спрашивай:
«Что произойдёт, если данных будет в 10 раз больше?»
Если есть просадки — ищи, где спрятаны O(n²).