Bu eğitimde böl ve yönet algoritmasının nasıl çalıştığını öğreneceksiniz. Yinelemeli bir problemi çözmek için böl ve yönet yaklaşımını diğer yaklaşımlarla da karşılaştıracağız.
Bir bölme ve ele geçir algoritması tarafından daha büyük problemi çözmenin bir stratejidir
- problemi daha küçük alt problemlere bölmek
- alt problemleri çözmek ve
- İstenilen çıktıyı elde etmek için bunları birleştirmek.
Böl ve yönet algoritmasını kullanmak için özyineleme kullanılır. Farklı programlama dillerinde yineleme hakkında bilgi edinin:
- Java'da özyineleme
- Python'da Özyineleme
- C ++ 'da özyineleme
Böl ve Fethet Algoritmaları Nasıl Çalışır?
İşte ilgili adımlar:
- Böl : Verilen problemi özyineleme kullanarak alt problemlere bölün.
- Fethedin : Daha küçük alt problemleri özyinelemeli olarak çözün. Alt problem yeterince küçükse, doğrudan çözün.
- Birleştir: Asıl sorunu çözmek için özyinelemeli sürecin parçası olan alt problemlerin çözümlerini birleştirin.
Bu kavramı bir örnek yardımıyla anlayalım.
Burada, böl ve yönet yaklaşımını (yani, birleştirme sıralaması) kullanarak bir diziyi sıralayacağız.
- Verilen dizi şöyle olsun:
Birleştirme sıralaması için dizi - Böl ikiye dizi.
Diziyi iki alt parçaya
bölün Yine, her bir alt bölümü, tek tek öğeler elde edene kadar yinelemeli olarak iki yarıya bölün.
Diziyi daha küçük alt bölümlere ayırın - Şimdi, tek tek öğeleri sıralı bir şekilde birleştirin. Burada, fethedin ve birleştirin adımları yan yana ilerler.
Alt bölümleri birleştirin
Zaman Karmaşıklığı
Böl ve yönet algoritmasının karmaşıklığı, ana teoremi kullanarak hesaplanır.
T (n) = aT (n / b) + f (n), burada, n = girişin boyutu a = özyinelemedeki alt problemlerin sayısı n / b = her alt problemin boyutu. Tüm alt problemlerin aynı boyutta olduğu varsayılır. f (n) = problemi bölme maliyetini ve çözümleri birleştirme maliyetini içeren yinelemeli aramanın dışında yapılan işin maliyeti
Özyinelemeli bir problemin zaman karmaşıklığını bulmak için bir örnek alalım.
Birleştirme sıralaması için denklem şu şekilde yazılabilir:
T (n) = aT (n / b) + f (n) = 2T (n / 2) + O (n) Burada, a = 2 (her seferinde bir problem 2 alt probleme bölünür) n / b = n / 2 (her alt problemin boyutu girdinin yarısıdır) f (n) = problemi bölmek ve alt problemleri birleştirmek için geçen süre T (n / 2) = O (n log n) (Bunu anlamak için, lütfen bakınız ana teorem.) Şimdi, T (n) = 2T (n log n) + O (n) ≈ O (n log n)
Divide and Conquer Vs Dynamic yaklaşımı
Böl ve yönet yaklaşımı bir problemi daha küçük alt problemlere böler; bu alt problemler özyinelemeli olarak daha da çözülür. Her alt problemin sonucu ileride başvurmak üzere saklanmaz, oysa dinamik bir yaklaşımda her bir alt problemin sonucu ileride başvurmak üzere saklanır.
Aynı alt problem birden çok kez çözülmediğinde böl ve yönet yaklaşımını kullanın. Bir alt problemin sonucu gelecekte birden çok kez kullanılacaksa dinamik yaklaşımı kullanın.
Bunu bir örnekle anlayalım. Fibonacci serisini bulmaya çalıştığımızı varsayalım. Sonra,
Böl ve Yönet yaklaşımı:
fib (n) Eğer n <2 ise, 1 Else döndür, f (n - 1) + f (n -2) döndür
Dinamik yaklaşım:
mem = () fib (n) Mem'de n ise: mem (n) aksi takdirde, n <2 ise, f = 1 ise, f = f (n - 1) + f (n -2) mem (n) = f dönüş f
Dinamik bir yaklaşımda mem, her alt problemin sonucunu depolar.
Böl ve Fethet Algoritmasının Avantajları
- Naif yöntemi kullanarak iki matrisin çarpımının karmaşıklığı O (n 3 ) iken böl ve yönet yaklaşımını kullanmak (yani Strassen'in matris çarpımı) O (n 2.8074 ) 'tür. Bu yaklaşım aynı zamanda Hanoi Kulesi gibi diğer sorunları da basitleştirir.
- Bu yaklaşım, çoklu işlem sistemleri için uygundur.
- Bellek önbelleklerinden verimli bir şekilde yararlanır.
Böl ve Fethet Uygulamaları
- Ikili arama
- Sıralamayı Birleştir
- Hızlı sıralama
- Strassen'in Matrix çarpımı
- Karatsuba Algoritması
