Алгоритми та структури даних · Middle · Запитання 48 з 75
Скільки підмножин має множина з n елементів і чому це важливо?
- ✓Правильна відповідь: 2ⁿ, тож генерувати всі підмножини - експоненційно
- 2n!, тож генерувати їх усі - факторіально
- 3n², тож генерувати їх усі - квадратично
Пояснення
Кожен елемент або входить, або ні, тож комбінацій 2ⁿ. Пошук із поверненням, що перебирає підмножини, нормальний для n близько 20, але не 50. n! - це кількість перестановок.