O(n²) — квадратична складність

Це вже повільно. Алгоритми з O(n²) мають вкладені цикли, і час виконання зростає квадратично відносно розміру вхідних даних.

Приклад: сортування бульбашкою (Bubble Sort)

function bubbleSort($array) {
    $n = count($array);
    for ($i = 0; $i < $n - 1; $i++) {
        for ($j = 0; $j < $n - $i - 1; $j++) {
            if ($array[$j] > $array[$j + 1]) {
                $temp = $array[$j];
                $array[$j] = $array[$j + 1];
                $array[$j + 1] = $temp;
            }
        }
    }
    return $array;
}

Кожен елемент перевіряється з кожним — от і квадратична складність. Якщо масив має 1000 елементів — буде до мільйона операцій.

Часом уникнути O(n²) не вийде, але щойно бачите подвійний цикл — варто хоча б запитати себе: а чи немає кращого способу?

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

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