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