Temeller
Kombinatorik temelleri
Permütasyonlar n!, kombinasyonlar, alt kümeler 2ⁿ - küçük n ile görsel.
Soru: 20 eleman için tüm alt kümeleri taramak kaç işlem?
2²⁰ = 1,048,576. İdam edilebilir. Ama 30 eleman için 2³⁰ ≈ 10⁹ ve zaman aşımı garantili. Bu sayfa, n!, 2ⁿ ve C(n,k) arasındaki farkı ve hangi DSA pattern’ine bağlandığını açar.
Sayılarla
| n | 2ⁿ | C(n, n/2) | n! | Yargıç sınırı (≈10⁸) |
|---|---|---|---|---|
| 10 | 1,024 | 252 | 3.6M | yaşar |
| 15 | 32,768 | 6,435 | 1.3T | 2ⁿ yaşar, n! ölür |
| 20 | 1M | 184,756 | 2.4·10¹⁸ | 2ⁿ yaşar, n! imkânsız |
| 25 | 33M | 5.2M | patlar | 2ⁿ zor, C(n,k) yaşar |
| 30 | 1.07B | 155M | patlar | 2ⁿ ölür, C(n,k) zor |
Tek satırda: 2ⁿ n ≤ 20 için yaşanır, n ≥ 30 için ölür. n! n ≥ 15 için zaten imkânsız. C(n, k), k ~n/2 olduğunda 2ⁿ’den ~√(πn/2) kat küçüktür ama yine üstel.
Nereden gelir?
n! (permütasyon)
n elemanın ilkini n yerleştir, ikinciyi n-1, … → n · (n-1) · … · 1 = n!. Tüm permütasyonları taramak (LC 46, 47) bu maliyettir. Backtracking, naif hâli budur; budamayla (pruning) bazı dalları kesmezsen tüm yaprakları gezersin.
2ⁿ (alt küme)
Her eleman dahil veya hariç, iki seçenek → 2 · 2 · … · 2 = 2ⁿ. Tüm alt kümeleri taramak (LC 78, 90) veya subset DP (LC 416, 494) bu maliyettir. n ≤ 20 için bir milyon yaprak gezilebilir; bu yüzden subset DP’de n ≤ 20 kuralı vardır.
C(n, k) (kombinasyon)
n elemandan k tanesini seç: n! / (k! · (n-k)!). Kombinasyon üretimi (LC 39, 77) bu kadar yaprak üretir. k ~n/2 olduğunda maksimumdur ve 2ⁿ / √(πn/2) mertebesinde, yani 2ⁿ’den küçük ama yine üstel.
Tuzak: “C(n, k) polinomiyal, 2ⁿ üstel”
Yanlış. C(n, n/2) üsteldir: C(20,10) = 184,756, C(30,15) = 155M. Sabit k için C(n,k) = O(nᵏ) polinomiyal, ama k n ile birlikte büyürse üstel olur. Bu yüzden “kombinasyon = polinomiyal” genellemesi yanıltıcı; k’nin n’ye bağlılığına bak.
Sıradaki adım
- Büyüme hızları - 2ⁿ ve n!’in diğer sınıflarla karşılaştırması.
- LC 46 Permutations - n! maliyetinin doğduğu yer.
- LC 78 Subsets - 2ⁿ maliyetinin doğduğu yer.
- LC 39 Combination Sum - C(n,k) backtracking.
- LC 416 Partition Equal Subset Sum - subset DP, n ≤ 200 ama 2ⁿ değil.
Alıştırma
Kaydırıcıyı n = 10’a getir. n!, 2ⁿ ve C(n, n/2) değerlerini tahmin et. Şimdin = 15’e geçir: n! kaç kat büyüdü? 2ⁿ kaç kat? Bu, neden backtracking problemlerinde n ≤ 15 sınırlarının var olduğunu somutlaştırır.