Algorytmy i struktury danych · Middle · Pytanie 48 z 75
Ile podzbiorów ma zbiór n elementów i dlaczego to ważne?
- ✓Poprawna odpowiedź: 2ⁿ, więc generowanie wszystkich podzbiorów jest wykładnicze
- 2n!, więc generowanie ich wszystkich jest silniowe
- 3n², więc generowanie ich wszystkich jest kwadratowe
Wyjaśnienie
Każdy element jest w podzbiorze albo nie, co daje 2ⁿ kombinacji. Backtracking wyliczający podzbiory jest w porządku dla n około 20, ale nie 50. n! to liczba permutacji.