O(n³) — кубічна складність

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

Приклад: множення двох матриць

function matrixMultiplication($matrixA, $matrixB) {
    $rowsA = count($matrixA);
    $colsA = count($matrixA[0]);
    $colsB = count($matrixB[0]);

    $result = [];
    for ($i = 0; $i < $rowsA; $i++) {
        for ($j = 0; $j < $colsB; $j++) {
            $result[$i][$j] = 0;
            for ($k = 0; $k < $colsA; $k++) {
                $result[$i][$j] += $matrixA[$i][$k] * $matrixB[$k][$j];
            }
        }
    }
    return $result;
}

Звучить академічно, але трапляється частіше, ніж здається: в обчисленнях, побудові графів, пошуку комбінацій. Усе, що потребує порівняння трійок даних або тривимірних структур, — кандидати на O(n³).

← Попередня: O(n²) — квадратична складність · Уся серія · Наступна: O(2ⁿ) — експоненціальна складність →

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