Четыре простых правила
Чтобы превратить «сколько шагов делает этот код» в класс Big O, нужны четыре правила:
1. Оставляем худший случай — считаем наибольшее число шагов, которое код может потребовать.
2. Отбрасываем константы — O(2n) и O(n/2) — это оба O(n).
3. Отбрасываем младшие слагаемые — O(n + n²) — это O(n²).
4. Разным входным данным — разные буквы — два разных массива дают O(a · b), а не O(n²).
Для каждого правила ниже есть один пример.
Правило 1: оставляем худший случай
Линейному поиску может повезти: если значение стоит в начале, достаточно одного шага. Big O не учитывает везение и описывает худший случай для массива — значение стоит последним или его нет вовсе, и проверяются все n элементов.
Поэтому линейный поиск — это O(n), хотя часто он заканчивается раньше. Худший случай — то обещание, которое алгоритм может выполнить всегда.
Лучший и худший случай поиска
Поиск первого слова занимает 1 шаг. Поиск отсутствующего слова занимает все 5. Big O оставляет 5: линейный поиск — это O(n).
Вывод: PHP-скрипт
<?php
function search(array $words, string $target): int {
$steps = 0;
foreach ($words as $w) {
$steps++;
if ($w === $target) {
break;
}
}
return $steps;
}
$words = ["one", "two", "three", "four", "five"];
echo 'лучший случай ("one"): ', search($words, "one"), " шаг\n";
echo 'худший случай ("six"): ', search($words, "six"), " шагов\n";
Правило 2: отбрасываем константы
Цикл, который посещает каждый второй элемент, делает n/2 шагов. Работы вдвое меньше — но форма роста не меняется: удвоив вход, удваиваем и число шагов.
Big O оставляет только форму, поэтому O(n/2), O(n) и O(2n) — это один и тот же класс: линейный.
Вдвое меньше шагов — всё равно O(n)
Цикл шагает через 2 и посещает 4 из 8 элементов. Если массив станет вдвое больше, число шагов тоже удвоится — значит n/2 шагов — это по-прежнему линейный рост, O(n).
Вывод: PHP-скрипт
<?php
$nums = [3, 1, 4, 1, 5, 9, 2, 6];
$steps = 0;
// Посещаем каждый второй элемент: n/2 шагов.
for ($i = 0; $i < count($nums); $i += 2) {
echo $nums[$i], " ";
$steps++;
}
echo "\n";
echo "элементов: ", count($nums), " шагов: ", $steps, "\n";
Правило 3: отбрасываем младшие слагаемые
Код часто смешивает части с разной стоимостью: простой цикл (n шагов), за которым идут вложенные циклы (n² шагов). Всего получается n + n².
С ростом n часть n² поглощает остальное — при n = 1000 это миллион шагов против тысячи. Big O оставляет только самое быстро растущее слагаемое: O(n + n²) превращается в O(n²).
n + n² шагов
Для 6 элементов простой цикл добавляет 6 шагов, а вложенные циклы — 36; всего 42. Квадратичное слагаемое уже доминирует, и его перевес только растёт вместе с n.
Вывод: PHP-скрипт
<?php
$nums = [1, 2, 3, 4, 5, 6];
$steps = 0;
// Один простой цикл: n шагов.
foreach ($nums as $x) {
$steps++;
}
// Цикл внутри цикла: n * n шагов.
foreach ($nums as $x) {
foreach ($nums as $y) {
$steps++;
}
}
echo "n = ", count($nums), "\n";
echo "n + n*n = ", $steps, "\n";
Правило 4: разные входные данные — разные буквы
Когда вложенные циклы проходят по двум разным входным данным, число шагов равно a · b — произведению двух длин. Называть это O(n²) было бы неверно: размеры входных данных могут сильно различаться.
Честный класс — O(a · b). Он становится O(n²) только в особом случае, когда оба входа — это один и тот же набор данных.
Два разных массива
3 цвета, умноженные на 2 животных, дают 6 шагов. Сложность — O(a · b): если массив животных растёт, а массив цветов нет, важно только b.
Вывод: PHP-скрипт
<?php
$colors = ["red", "green", "blue"];
$animals = ["cat", "dog"];
$steps = 0;
foreach ($colors as $c) {
foreach ($animals as $a) {
$steps++;
}
}
echo "цветов: ", count($colors), " животных: ", count($animals), "\n";
echo "шагов: ", $steps, "\n";
Ограничения Big O
Big O намеренно является грубым инструментом, и стоит знать, что он скрывает.
Он видит только худший случай. Алгоритм с пугающим худшим случаем может быть отличным на практике, если этот случай редок. Иногда важен средний случай.
Он игнорирует константы. На бумаге 1000 · n и n — это один класс. Для небольших входных данных «медленный» алгоритм O(n²) с крошечными шагами может обогнать «быстрый» O(n) с тяжёлыми шагами.
Используйте Big O, чтобы сравнивать, как алгоритмы масштабируются. Для настоящей скорости на настоящих данных — измеряйте.