O(n!) — факторіальна складність

Це — вершина обчислювального кошмару. Факторіальна складність означає, що кількість операцій зростає як добуток усіх цілих чисел до n. Для n = 10 — це вже 3 628 800 варіантів. І так, усе це треба обробити.

10! = 10 × 9 × 8 × 7 × 6 × 5 × 4 × 3 × 2 × 1 = 3 628 800

Приклад: генерація всіх можливих перестановок елементів

function permutations(array $items): array {
    if (count($items) <= 1) return [$items];

    $result = [];
    foreach ($items as $key => $item) {
        $remaining = $items;
        unset($remaining[$key]);
        foreach (permutations(array_values($remaining)) as $perm) {
            $result[] = array_merge([$item], $perm);
        }
    }
    return $result;
}

Цей код генерує всі можливі перестановки елементів масиву. І якщо їх 8 — то вже 40 320 варіантів. Це може виглядати невинно, поки не впаде прод у Black Friday.

На цьому серія завершується.

← Попередня: O(2ⁿ) — експоненціальна складність · Уся серія

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