Özet - NP-completeness

Bir problem sınıflandırmasını yazdıran mini görev yaparsın.

Özet - NP-completeness

Bu grupta P, NP ve NP-complete kavramlarını öğrendin. Brute force çözüm, polinom doğrulama ve azaltma tekniği birleşince sınıflar anlaşılır.

Şimdi tüm parçaları bir araya getiren bir fonksiyon yazacaksın. Bu özet, grubun kavramlarını tek bir kodda birleştirir.

Uygulama count_subsets fonksiyonu

count_subsets(arr, target) yaz. Toplamı target olan alt küme sayısını döndür. print(count_subsets([3, 5, 7], 10)) ile 1 yazdır.

Örnek çözümü göster

def count_subsets(arr, target):
    # Toplamı target olan alt küme sayısını bul
    n = len(arr)
    count = 0
    for mask in range(1 << n):
        s = 0
        for i in range(n):
            if mask & (1 << i):
                s += arr[i]
        if s == target:
            count += 1
    return count
print(count_subsets([3, 5, 7], 10))

Kendini test et

NP-complete bir problemi çözmek ne kadar sürer?
- Üstel zaman (en kötü)
- Polinom zaman
- Sabit zaman
- Logaritmik zaman
Cevabı göster

Üstel zaman (en kötü) — En kötü durumda üstel zaman gerekir.

bitmask döngüsü

for mask in range(1 ____ n):

Cevabı göster

for mask in range(1 << n):

Özet - NP-completeness: kavramları eşleştir

is_sorted

P
brute_force_subset

NP-complete
verify_subset

Doğrulama
azaltma

Reduction

Sıradaki ders: Yaklaşık algoritmalar

Deneyiminizi Geliştiriyoruz

Çerez Tercihleri

Kesinlikle Gerekli Çerezler

Analitik Çerezler