Bu ders için video bulunmamaktadır.
Bu derse başlamak veya ilerlemenizi kaydetmek için lütfen giriş yapın veya kayıt olun.
Ders İçeriği
Büyük problemleri küçük alt problemlere bölerek çözen paradigma.
Üç Temel Adım
- Böl (Divide): Problemi daha küçük alt problemlere ayır
- Yönet (Conquer): Alt problemleri özyinelemeli olarak çöz
- Birleştir (Combine): Alt çözümleri birleştirerek ana çözümü elde et
Örnek: Birleştirmeli Sıralama
FONKSİYON MergeSort(dizi)
EĞER (dizi.boyut <= 1) DÖNDÜR dizi
orta = dizi.boyut / 2
sol = MergeSort(dizi[0...orta-1]) // Böl
sag = MergeSort(dizi[orta...son]) // Böl
DÖNDÜR Merge(sol, sag) // Birleştir
SON
Diğer Örnekler
- Hızlı Sıralama: Pivot etrafında böl
- İkili Arama: Arama aralığını yarıya böl
- Strassen Matris Çarpımı: Matrisleri alt matrislere böl
- En Yakın Nokta Çifti: Düzlemi böl
Avantajları
- Paralelleştirilebilir
- Önbellek dostu
- Karmaşık problemleri basitleştirir
- Genellikle verimli algoritmalar üretir
Dezavantajları
- Özyineleme ek yükü
- Yığın taşması riski
- Her problem için uygun değil
Zaman Karmaşıklığı Analizi
Master Theorem kullanılarak analiz edilir:
T(n) = aT(n/b) + f(n)
- a: Alt problem sayısı
- b: Problem boyutu azalma faktörü
- f(n): Bölme ve birleştirme maliyeti