← O(log n) — логарифмічна складність
docs: English JsonRpcBundle docs, REST and MCP Bundle sections, package cards
uk/articles/from-tg/series/algorithm-complexity/o-log-n.md
новий файл +36
−0
1
+
# O(log n) — логарифмічна складність
2
+
3
+
Це одна з найефективніших складностей, яку тільки можна досягти в реальних задачах з великим обсягом даних.
4
+
5
+
Уявімо, що в нас є телефонна книга з 1 000 000 імен, і ми шукаємо конкретне. Лінійно довелося б перевірити кожне імʼя, і це зайняло б безліч часу. Але якщо ми будемо розрізати масив навпіл кожного разу, відкидаючи половину, яка нам точно не підходить, — отримаємо двійковий пошук, і результат знайдеться за ~20 кроків. Це й є логарифмічна ефективність.
6
+
7
+
Такий підхід працює лише з відсортованими даними. І саме це лежить в основі багатьох пошукових і оптимізаційних алгоритмів.
8
+
9
+
## Приклад: двійковий пошук у відсортованому масиві
10
+
11
+
```php
12
+
function binarySearch($array, $target) {
13
+
$left = 0;
14
+
$right = count($array) - 1;
15
+
16
+
while ($left <= $right) {
17
+
$middle = floor(($left + $right) / 2);
18
+
if ($array[$middle] === $target) return $middle;
19
+
20
+
if ($array[$middle] < $target) {
21
+
$left = $middle + 1;
22
+
} else {
23
+
$right = $middle - 1;
24
+
}
25
+
}
26
+
return -1;
27
+
}
28
+
```
29
+
30
+
Кожний крок зменшує область пошуку вдвічі. І замість мільйона перевірок — лише кілька десятків. Ось чому O(log n) — максимально швидкий.
31
+
32
+
← [Попередня: O(n) — лінійна складність](/articles/from-tg/series/algorithm-complexity/o-n) · [Уся серія](/articles/from-tg/series/algorithm-complexity) · [Наступна: O(n log n) — лінійно-логарифмічна складність →](/articles/from-tg/series/algorithm-complexity/o-n-log-n)
33
+
34
+
---
35
+
36
+
*Вперше опубліковано в Telegram-каналі [«Створений щоб помирати»](https://t.me/php_while_true/31) 22.06.2025.*