← O(n²) — квадратична складність
docs: English JsonRpcBundle docs, REST and MCP Bundle sections, package cards
uk/articles/from-tg/series/algorithm-complexity/o-n2.md
новий файл +35
−0
1
+
# O(n²) — квадратична складність
2
+
3
+
Це вже повільно. Алгоритми з O(n²) мають вкладені цикли, і час виконання зростає квадратично відносно розміру вхідних даних.
4
+
5
+
## Приклад: сортування бульбашкою (Bubble Sort)
6
+
7
+
```php
8
+
function bubbleSort($array) {
9
+
$n = count($array);
10
+
for ($i = 0; $i < $n - 1; $i++) {
11
+
for ($j = 0; $j < $n - $i - 1; $j++) {
12
+
if ($array[$j] > $array[$j + 1]) {
13
+
$temp = $array[$j];
14
+
$array[$j] = $array[$j + 1];
15
+
$array[$j + 1] = $temp;
16
+
}
17
+
}
18
+
}
19
+
return $array;
20
+
}
21
+
```
22
+
23
+
Кожен елемент перевіряється з кожним — от і квадратична складність. Якщо масив має 1000 елементів — буде до мільйона операцій.
24
+
25
+
:::warning
26
+
Будь-який вкладений цикл — тривожний дзвіночок. У реальному коді O(n²) трапляється при порівнянні всіх з усіма: наприклад, фільтрація перетинів, дублікати, агрегації без індексів.
27
+
:::
28
+
29
+
Часом уникнути O(n²) не вийде, але щойно бачите подвійний цикл — варто хоча б запитати себе: а чи немає кращого способу?
30
+
31
+
← [Попередня: O(n log n) — лінійно-логарифмічна складність](/articles/from-tg/series/algorithm-complexity/o-n-log-n) · [Уся серія](/articles/from-tg/series/algorithm-complexity) · [Наступна: O(n³) — кубічна складність →](/articles/from-tg/series/algorithm-complexity/o-n3)
32
+
33
+
---
34
+
35
+
*Вперше опубліковано в Telegram-каналі [«Створений щоб помирати»](https://t.me/php_while_true/42) 24.06.2025.*