O(log n) - Логарифмическая Сложность

Проблема

Линейный поиск (O(n)) честно находит нужный элемент, но на действительно больших данных это дорого: миллион элементов - до миллиона сравнений. При этом сами данные часто уже отсортированы или могут быть организованы так, чтобы этим воспользоваться. Не пользоваться этим порядком и всё равно перебирать элемент за элементом - значит выбрасывать даром информацию, которая уже есть в структуре данных.

Решение

Алгоритм - O(log n), если на каждом шаге он отбрасывает фиксированную долю оставшихся данных (обычно половину) и работает дальше только с тем, что осталось. Узнать такой код можно по признаку: в нём нет прохода по всем элементам, вместо этого - сужение диапазона поиска, обычно с помощью двух границ low/high, которые на каждом шаге сдвигаются друг к другу. Количество таких шагов равно тому, сколько раз можно поделить n пополам, прежде чем останется 1 элемент - это и есть log₂ n.

Как это работает

Формально O(log n) означает: число шагов растёт как логарифм по основанию 2 от n - сколько раз n можно поделить пополам, прежде чем останется 1. Для n = 1 000 000 это log₂ 1 000 000 ≈ 19.9, округляется до 20 шагов. Для линейного поиска на том же массиве в худшем случае потребовался бы 1 000 000 шагов - разница в 50 000 раз, и она только растёт с увеличением данных.

Пропорция особенно хорошо видна на удвоении данных. Если бинарному поиску на n элементах требуется k шагов, то на 2n элементах потребуется всего k + 1 шаг - не вдвое больше, а на единицу больше. Массив вырос в 1000 раз (это примерно 2^10), а число шагов выросло всего на 10.

Ключевое условие для O(log n) - произвольный доступ к середине диапазона за O(1). У массива это arr[mid] - мгновенный доступ по индексу (материал O(1)). У связного списка такого доступа нет, до середины нужно идти по ссылкам от начала - сам «поход к середине» уже стоит O(n), и весь алгоритм перестаёт быть O(log n), даже если логика деления пополам формально сохраняется.

Частая ошибка - искать O(log n) там, где данных с полезным порядком на самом деле нет. Бинарный поиск по неотсортированному массиву не работает вообще: отбрасывание половины опирается на то, что всё слева от mid меньше искомого, а всё справа - больше. Без сортировки это предположение неверно, и алгоритм может пропустить существующий элемент.

Логарифмическая сложность встречается не только в поиске: у сбалансированного бинарного дерева высота дерева - тоже O(log n) от числа узлов, и именно это делает вставку, удаление и поиск в нём быстрыми. Куча (структура, лежащая в основе Heap Sort, уже реализованного в разделе сортировок) по той же причине выполняет sift-up/sift-down за O(log n) - высота кучи растёт логарифмически от числа элементов.

O(log n) обычно не стоит особняком в общей сложности алгоритма - он чаще встречается как множитель. У Merge Sort и Quick Sort (в разделе сортировок) сложность O(n log n): log n уровней разбиения, и на каждом уровне ещё O(n) работы по слиянию или партиционированию - именно так и получается произведение n · log n, а не просто log n.

Нюансы выбора

Поиск в статичных отсортированных данных - справочники, каталоги, любые данные, которые редко меняются, но по которым часто ищут.

Структуры, где порядок нужен постоянно - деревья поиска, кучи, индексы баз данных: там O(log n) не разовый трюк, а свойство самой структуры.

Против O(1) - если нужен только точный поиск по ключу и порядок не важен, хеш-таблица с её O(1) в среднем случае почти всегда быстрее, чем дерево с O(log n).

Как множитель, а не сам по себе - в составе O(n log n) логарифм почти всегда означает разбиение данных на уровни, как в Merge Sort или построении сбалансированного дерева.

Примеры в коде

Индексы в PostgreSQL и MySQL (B-tree) - поиск строки по индексированному полю в таблице из миллионов записей укладывается в единицы уровней дерева, а не в перебор строк.

Java TreeMap/TreeSet и C++ std::map - реализованы поверх сбалансированных деревьев (обычно красно-чёрных), поэтому вставка, удаление и поиск - все O(log n).

git bisect - двоичный поиск по истории коммитов для нахождения того, что сломал сборку: несколько десятков коммитов между известными «хорошим» и «плохим» находятся за считанные шаги.

Heap Sort (в разделе сортировок) - его sift-down на каждом шаге спускается по дереву-куче на один уровень, а глубина кучи - тот самый log n, из-за которого вся сортировка укладывается в O(n log n).

Когда применять

• Когда данные уже отсортированы или будут использоваться для многих повторяющихся поисков - разовая сортировка окупается на каждом следующем запросе.
• Когда нужно не просто найти элемент, а определить его позицию среди отсортированных значений - например, куда вставить новое значение, сохранив порядок.

Примеры из практики

• Бинарные деревья поиска и B-деревья (индексы в базах данных вроде PostgreSQL/MySQL) - каждый уровень дерева отбрасывает часть данных, поиск по индексу идёт за O(log n).
• git bisect - находит коммит, который сломал код, делением диапазона коммитов пополам на каждом шаге, вместо проверки каждого коммита по очереди.