O(log n) — логарифмічна складність

Це одна з найефективніших складностей, яку тільки можна досягти в реальних задачах з великим обсягом даних.

Уявімо, що в нас є телефонна книга з 1 000 000 імен, і ми шукаємо конкретне. Лінійно довелося б перевірити кожне імʼя, і це зайняло б безліч часу. Але якщо ми будемо розрізати масив навпіл кожного разу, відкидаючи половину, яка нам точно не підходить, — отримаємо двійковий пошук, і результат знайдеться за ~20 кроків. Це й є логарифмічна ефективність.

Такий підхід працює лише з відсортованими даними. І саме це лежить в основі багатьох пошукових і оптимізаційних алгоритмів.

Приклад: двійковий пошук у відсортованому масиві

function binarySearch($array, $target) {
    $left = 0;
    $right = count($array) - 1;

    while ($left <= $right) {
        $middle = floor(($left + $right) / 2);
        if ($array[$middle] === $target) return $middle;

        if ($array[$middle] < $target) {
            $left = $middle + 1;
        } else {
            $right = $middle - 1;
        }
    }
    return -1;
}

Кожний крок зменшує область пошуку вдвічі. І замість мільйона перевірок — лише кілька десятків. Ось чому O(log n) — максимально швидкий.

← Попередня: O(n) — лінійна складність · Уся серія · Наступна: O(n log n) — лінійно-логарифмічна складність →

Вперше опубліковано в Telegram-каналі «Створений щоб помирати» 22.06.2025.