Цикл внутри цикла
O(n²) означает квадратичное время: объём работы растёт как квадрат размера входных данных. В два раза больше элементов — в четыре раза больше шагов. В десять раз больше элементов — в сто раз больше шагов.
Характерная форма в коде — цикл внутри цикла, причём оба проходят по одним и тем же данным. Внешний цикл выполняется n раз, и для каждого его шага внутренний цикл снова выполняется n раз: n · n шагов.
Для небольших массивов квадратичная сложность вполне приемлема. Для 100 000 элементов это уже 10 миллиардов шагов — именно на этом программы начинают «зависать».
Все пары
Самая прямая задача на O(n²): соединить каждый элемент с каждым. 4 буквы дают 4 · 4 = 16 пар; 100 букв дали бы 10 000.
Построение всех пар
Внешний цикл выбирает $x, внутренний соединяет его с каждым $y. 4 элемента дают 16 пар — квадрат размера входных данных.
Вывод: PHP-скрипт
<?php
$letters = ["a", "b", "c", "d"];
$pairs = 0;
foreach ($letters as $x) {
foreach ($letters as $y) {
echo $x . $y, " ";
$pairs++;
}
echo "\n";
}
echo count($letters), " элемента образовали ", $pairs, " пар\n";
Пузырьковая сортировка
Пузырьковая сортировка — классический квадратичный алгоритм: он многократно проходит по массиву и меняет местами соседние элементы, стоящие в неверном порядке. Большие значения «всплывают» к концу, по одному за проход.
Из-за двух вложенных циклов он выполняет примерно n²/2 сравнений. На нём отлично учиться — и плохо им пользоваться: встроенная в PHP функция sort() делает то же самое за O(n log n).
Сортировка двумя вложенными циклами
Сортировка 5 элементов требует 4 + 3 + 2 + 1 = 10 сравнений. Для 1 000 элементов их было бы около полумиллиона — тогда как сортировке с O(n log n) нужно около десяти тысяч.
Вывод: PHP-скрипт
<?php
$nums = [5, 3, 8, 1, 4];
$comparisons = 0;
$n = count($nums);
for ($i = 0; $i < $n - 1; $i++) {
for ($j = 0; $j < $n - 1 - $i; $j++) {
$comparisons++;
if ($nums[$j] > $nums[$j + 1]) {
[$nums[$j], $nums[$j + 1]] = [$nums[$j + 1], $nums[$j]];
}
}
}
echo "отсортировано: ", implode(", ", $nums), "\n";
echo "сравнений: ", $comparisons, "\n";
Поиск дубликатов медленным способом
Проверка каждого элемента со всеми элементами, идущими после него, — ещё один шаблон вложенных циклов: сравнение всех пар для поиска дубликата.
Это работает, но сложность равна O(n²). Страница «Пространственная сложность» в этой группе показывает стандартный приём, который делает такой поиск линейным: запоминать уже встреченные значения в ассоциативном массиве.
Поиск дубликата двумя циклами
Каждый элемент сравнивается со всеми последующими. Пара одинаковых значений 1 находится после 7 проверок; в худшем случае — когда дубликатов нет вовсе — выполняются все 15 проверок пар.
Вывод: PHP-скрипт
<?php
$nums = [3, 1, 4, 1, 5, 9];
$checks = 0;
$n = count($nums);
for ($i = 0; $i < $n; $i++) {
for ($j = $i + 1; $j < $n; $j++) {
$checks++;
if ($nums[$i] === $nums[$j]) {
echo "дубликат: ", $nums[$i], " после ", $checks, " проверок\n";
}
}
}