Böl ve yönet: Bağımsız alt problemler | DSA

← BlogDATA STRUCTURES / ALGORITHMSPython örnek paketi ↓

Divide-and-conquer problemi küçültür, alt problemleri çözer ve sonuçları birleştirir. Merge sort'ta birleştirme işin merkezidir; quicksort'ta partition önden yapılır. Binary search tek alt problem izleyen decrease-and-conquer örneği olarak ayrıca sınıflanabilir.

Closest-pair iki boyutta noktaları x ile böler, iki yarının minimum distance'ını bulur, strip'te sınırlı komşulara bakar. Strip noktaları her seviyede tekrar sıralanırsa O(n log²n) çıkabilir; y sırasını merge ile korumak O(n log n) analizini sağlar. Geometrik packing ispatı olmadan “yalnız yedi nokta bak” ezberi eksiktir.

Alt problemler örtüşüyorsa aynı işleri tekrar çözmek DP ihtiyacını gösterir. Paralel çalıştırılabilir olması bedava hızlanma değildir: work toplam işlem, span en uzun bağımlılık zinciridir; bellek ve scheduling overhead ayrıca vardır. Tüm recursion'ları divide-and-conquer diye etiketlemek problemi anlamayı kolaylaştırmaz.

Adım adım iz sürme

Sum([1,2,3,4]) iki yarı sonucu3 ve7'+'’yi toplar. Alt problemler bağımsızdır; ama Python slicing kopya maliyeti ekler.

Maliyet ve varsayımlar

İndeks tabanlı recursive sum Θ(n) work ve Θ(log n) stack; paralel ideal span Θ(log n).

Çalıştırılabilir örnek

Python 3 ile çalıştır. Assert küçük bir örneği denetler; genel doğruluk ispatı değildir. Bazı ileri örnekler özellikle küçük model veya referans oracle'dır; tam üretim uygulaması değildir.

Python 3

def range_sum(a, lo, hi):
    if lo == hi: return 0
    if hi-lo == 1: return a[lo]
    mid=(lo+hi)//2
    return range_sum(a,lo,mid)+range_sum(a,mid,hi)
assert range_sum([1,2,3,4],0,4) == 10

KAVRADIĞINI KONTROL ET

Sıra sende

Fib recursion neden gereksiz tekrar yapar?

Çözümün mantığını göster

Alt problemler bağımsız değil örtüşür: fib(n−2) birçok dalda tekrar oluşur. Memoization aynı state'i bir kez çözer.

Bir adım ileri

Örneği değiştirmeden önce girdi sözleşmesini ve invariantı yaz.
Uygun olan boş, sınır, tekrar ve adversarial girdileri ekle. Basit bir oracle ile karşılaştır.
Belirtilen modelde maliyeti çıkar; farklı girdi büyüklüklerini ölç ve farkları gerekçelendir.

Temel kaynaklar ve ders notları

Bu eğitimde özgün anlatım kullanıldı; aşağıdaki kaynaklar ispatlar ve ileri okumalar sunar. Bağlantılar daha geniş ders modülünü kapsayabilir.

MIT 6.046J · Design and Analysis ↗Jeff Erickson · Algorithms ↗

İlerlemeden önce alıştırmayı çöz.

RasimAtaberkŞahin