Böl ve Yönet
Böl ve yönet, bir problemi aynı türden daha küçük alt problemlere ayırarak, bunları özyinelemeli olarak çözerek ve çözümlerini orijinal problemin bir çözümü halinde birleştirerek çözen bir algoritma tasarım paradigmasıdır.
Tanım
Bir böl ve yönet algoritması, bir problemi, alt problemler doğrudan çözülebilecek kadar basit hale gelene kadar aynı veya ilişkili türden iki veya daha fazla alt probleme özyinelemeli olarak böler, ardından orijinal problemin cevabını üretmek için alt problem çözümlerini birleştirir.
Kapsam
Bu konu, böl ve yönet algoritmalarının üç adımlı yapısını (böl, yönet, birleştir), mergesort, quicksort, ikili arama ve hızlı tam sayı ile matris çarpımı gibi tipik örnekleri ve çalışma sürelerinin özyineleme tabanlı analizini kapsamaktadır. Ana teorem ve bu tür algoritmaları analiz etmek için kullanılan özyineleme çözme teknikleriyle yakından ilişkilidir.
Temel sorular
- Alt problemlerin bağımsız ve aynı biçimde olması için bir problem nasıl ayrıştırılır?
- Birleştirme adımında hangi işler yapılır ve bu, toplam maliyeti nasıl etkiler?
- Asimptotik çalışma sürelerini elde etmek için ortaya çıkan özyinelemeler nasıl çözülür?
- Böl ve yönet, doğrudan yinelemeli bir yaklaşımdan ne zaman daha iyi performans gösterir?
Anahtar kavramlar
- böl, yönet, birleştir
- özyineleme bağıntıları
- ana teorem
- mergesort
- quicksort
- binary search
- Karatsuba multiplication
- Strassen's matrix multiplication
Temel kuramlar
- Özyinelemeler için ana teorem
- Ana teorem, T(n) = aT(n/b) + f(n) biçimindeki böl ve yönet özyinelemeleri için, özyinelemeli alt problemlerin maliyetini birleştirme maliyeti f(n) ile karşılaştırarak kapalı formda asimptotik çözümler sunmaktadır.
- Ayrıştırma yoluyla subkuadratik çarpma
- İşlenenleri özyinelemeli olarak bölmek ve özyinelemeli çarpma sayısını azaltmak (Karatsuba çarpımı ve Strassen'ın matris çarpımında olduğu gibi), saf kuadratik ve kübik yöntemlerden asimptotik olarak daha hızlı algoritmalar sağlamaktadır.
Klinik önem
Böl ve yönet, en yaygın kullanılan algoritmaların çoğunun temelini oluşturmaktadır: standart kütüphanelerde verimli sıralama (mergesort, quicksort), arama rutinlerinde ikili arama, sinyal ve görüntü işlemede Hızlı Fourier Dönüşümü ve kriptografi ile keyfi hassasiyetli aritmetikte kullanılan hızlı çarpma.
Tarihçe
Mergesort'un John von Neumann'a (1945) atfedildiği bilinmektedir. C. A. R. Hoare, quicksort'u 1962'de yayımlamıştır. Karatsuba'nın 1960'taki subkuadratik çarpımı ve Strassen'ın 1969'daki matris çarpımı algoritması, özyinelemeli ayrıştırmanın klasik sınırları aşabileceğini göstererek, böl ve yöneti temel bir paradigma olarak yerleştirmeye yardımcı olmuştur.
Öne çıkan isimler
- C. A. R. Hoare
- John von Neumann
- Anatoly Karatsuba
- Volker Strassen
İlgili konular
Temel eserler
- hoare1962
- cormen2009
Sıkça sorulan sorular
- Mergesort neden O(n log n) karmaşıklığa sahiptir?
- Mergesort, diziyi iki yarıya böler (log n özyineleme seviyesi) ve her seviyede tüm elemanlar üzerinde doğrusal zamanda birleştirme yapar, bu da T(n) = 2T(n/2) + O(n) özyinelemesini verir; ana teorem bunu O(n log n) olarak çözmektedir.
- Quicksort'un açık bir birleştirme adımı olmamasına rağmen bir böl ve yönet algoritması mıdır?
- Evet. Quicksort, ana işini bir pivot etrafında bölme yaparak bölme adımında gerçekleştirir; iki bölüm özyinelemeli olarak sıralandığında, birleştirme işine gerek kalmaz. Paradigma, çabanın büyük kısmının üç aşamadan herhangi birine düşmesine izin vermektedir.