Делим задачу пополам
O(log n) означает логарифмическое время: каждый шаг сокращает остаток работы вдвое. Так как деление пополам уменьшает числа очень быстро, удвоение входных данных добавляет всего один лишний шаг.
Для 16 элементов нужно 4 деления пополам, для 32 элементов — 5, для миллиона — около 20, для миллиарда — около 30. Именно поэтому логарифмические алгоритмы кажутся мгновенными даже на огромных данных.
Классический пример — бинарный поиск, но он работает только на отсортированных данных. Чтобы делить пополам, нужен порядок: иначе не понять, какую половину отбросить.
Цикл с делением пополам
Проще всего увидеть O(log n) на цикле, который делит n на 2, пока не дойдёт до 1. Число повторений — это логарифм n: при n = 16 цикл выполняется 4 раза, потому что 2 · 2 · 2 · 2 = 16.
Делим пополам, пока не останется единица
16 превращается в 8, 4, 2, 1 — четыре шага. Удвоение n до 32 добавило бы всего один шаг.
Вывод: PHP-скрипт
<?php
$n = 16;
$steps = 0;
while ($n > 1) {
$n = intdiv($n, 2);
$steps++;
echo "n теперь $n\n";
}
echo "16 превратилось в 1, шагов: $steps\n";
Бинарный поиск
Бинарный поиск находит значение в отсортированном массиве, каждый раз проверяя средний элемент. Если середина слишком мала, отбрасывается вся левая половина; если слишком велика — правая. Каждая проверка сокращает диапазон поиска вдвое.
Два маркера, $lo и $hi, задают текущий диапазон. Цикл заканчивается, когда значение найдено или диапазон пуст.
В стандартной библиотеке PHP готового бинарного поиска нет. Встроенная функция array_search() находит значение, просматривая массив с начала, — это линейный поиск, O(n). На отсортированных данных написанный вручную бинарный поиск быстрее, и он ещё может сказать, куда попало бы отсутствующее значение.
Бинарный поиск шаг за шагом
В отсортированном массиве из 16 чисел поиск значения 13 требует всего 4 проверок: диапазон сокращается 16 → 8 → 4 → 2 и приводит к индексу 6. Линейному поиску здесь понадобилось бы 7 шагов — а в худшем случае до 16.
Вывод: PHP-скрипт
<?php
$nums = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31];
$target = 13;
$steps = 0;
$lo = 0;
$hi = count($nums) - 1;
while ($lo <= $hi) {
$steps++;
$mid = intdiv($lo + $hi, 2);
if ($nums[$mid] === $target) {
echo "значение $target найдено по индексу $mid, проверок: $steps\n";
break;
}
if ($nums[$mid] < $target) {
$lo = $mid + 1;
} else {
$hi = $mid - 1;
}
}
Бинарный поиск против array_search()
binarySearch() находит 9 по индексу 4. Для отсутствующего значения 10 получаем найдено: false и индекс 5 — место, куда встало бы 10, чтобы массив остался отсортированным. array_search() тоже даёт ответ, но просматривает массив линейно, а для отсутствующего 10 возвращает только false — без позиции.
Вывод: PHP-скрипт
<?php
function binarySearch(array $nums, int $target): array {
$lo = 0;
$hi = count($nums);
while ($lo < $hi) {
$mid = intdiv($lo + $hi, 2);
if ($nums[$mid] < $target) {
$lo = $mid + 1;
} else {
$hi = $mid;
}
}
$found = $lo < count($nums) && $nums[$lo] === $target;
return [$lo, $found];
}
$nums = [1, 3, 5, 7, 9, 11, 13, 15];
[$i, $found] = binarySearch($nums, 9);
echo "binarySearch 9 -> индекс: $i найдено: ", var_export($found, true), "\n";
[$i, $found] = binarySearch($nums, 10);
echo "binarySearch 10 -> индекс: $i найдено: ", var_export($found, true), "\n";
// array_search просматривает массив с начала: это линейный поиск, O(n).
echo "array_search 9 -> ", var_export(array_search(9, $nums, true), true), "\n";
echo "array_search 10 -> ", var_export(array_search(10, $nums, true), true), "\n";
O(n log n): сортировка
O(n log n) находится между линейной и квадратичной сложностью и является сложностью хороших алгоритмов сортировки: данные снова и снова делятся пополам (log n уровней), и на каждом уровне выполняется линейный объём работы (n).
В PHP сортировку редко пишут сами — функция sort() имеет сложность O(n log n). Она принимает массив по ссылке и сортирует его на месте: меняется сам массив, ничего не нужно присваивать обратно. Один раз отсортировать, а затем много раз применять бинарный поиск — распространённый и быстрый подход.
Сортировка массива
sort() упорядочивает 8 чисел на месте примерно за 8 · log 8 = 24 шагов — гораздо меньше, чем 64 шага квадратичной сортировки, и с ростом массива разрыв быстро увеличивается.
Вывод: PHP-скрипт
<?php
$nums = [31, 5, 17, 1, 23, 9, 27, 13];
sort($nums);
echo implode(", ", $nums), "\n";