Wiem, że iterowanie wszystkich podzbiorów zestawu n jest koszmarem wydajności i zajmie O (2 ^ n) czasu.

Co powiesz na iterowanie wszystkich podzbiorów wielkości k (dla (0 <= k <= n))? Czy to koszmar występów? Wiem, że są (n, k) = n! / k! (n - k)! możliwości. Wiem, że jeśli k jest bardzo blisko 0 lub bardzo blisko n, jest to mała liczba.

Jaki jest najgorszy przypadek w kategoriach n i k? Czy istnieje prostszy sposób powiedzenia tego poza O (n! / K! (N - k)!)? Czy jest to asymptotycznie mniejsze niż O (n!) Lub takie samo?