DAA - Böl ve Fethet
Çoğu algoritma, belirli bir sorunu özyinelemeli olarak alt problemlerle ilgilenerek çözmek için doğası gereği özyinelidir.
İçinde divide and conquer approachbir problem daha küçük problemlere bölünür, daha sonra daha küçük problemler bağımsız olarak çözülür ve son olarak daha küçük problemlerin çözümleri büyük problem için bir çözüm olarak birleştirilir.
Böl ve yönet algoritmalarının genel olarak üç bölümü vardır -
Divide the problem aynı sorunun daha küçük örnekleri olan bir dizi alt soruna.
Conquer the sub-problemsbunları özyinelemeli olarak çözerek. Yeterince küçüklerse, alt problemleri temel durumlar olarak çözün.
Combine the solutions alt problemlere orijinal problemin çözümüne.
Böl ve Fethet Yaklaşımının artıları ve eksileri
Böl ve yönet yaklaşımı, alt problemler bağımsız olduğundan paralelliği destekler. Dolayısıyla bu teknik kullanılarak tasarlanan bir algoritma, çok işlemcili sistemde veya aynı anda farklı makinelerde çalışabilir.
Bu yaklaşımda, algoritmaların çoğu özyineleme kullanılarak tasarlanmıştır, dolayısıyla bellek yönetimi çok yüksektir. Özyinelemeli işlev yığını için, işlev durumunun depolanması gerektiğinde kullanılır.
Böl ve Fethet Yaklaşımının Uygulanması
Böl ve yönet yaklaşımı kullanılarak çözülen bazı problemler aşağıdadır.
- Bir sayı dizisinin maksimum ve minimumunu bulma
- Strassen'in matris çarpımı
- Sıralamayı birleştir
- Ikili arama