Divide and Conqueror Algoritmaları (böl ve fethet algoritmaları)

Algoritma oluşturmada kullanılan en ilginç yaklaşımlardan biri de Divide and Conqueror algoritmalarıdır. Hatta bu algoritma fikrinin dünya yönetiminde bile uygulandığı dedikodusu çıkarılmıştır. Ne kadar gerçektir bilmiyoruz, böldükleri gerçek de, birleştirdiklerini göremedik :)

Her neyse, konumuza giriş yapalım biz. Böl ve fethet algoritması (böl parçala yönet başka bir şey, onu karıştırmayın :) ) temelde problemleri daha küçük parçalara ayırmayı hedefler. Bir problem en küçük parçaya kadar indirgenir. Daha sonra ise bölünmüş olan parçalar belli bir çözüm uygulanarak birleştirilirler. Böylece çözüme ulaşılmış olur. Ana Mantık budur. Şimdi aşağıdaki resme bakın;

divide and conqueror algoritması
Böl ve Yönet Algoritması

Çok karmaşık gibi göründüğüne bakmayın, aslında mantık çok basit, yukarıdan aşağı derinliğe baktığımızda 8 katman var. Bu 8 katmanın 4 tanesi problemleri alt problemlere ayırıyor. Diğer 4 tanesi ise problemlere çözüm uygulayarak birleştiriyor. En sonunda problem çözümü ortaya çıkıyor.

Divide And Conqueror Algoritmasının Kullanıldığı Yerler


  1. Binary Search : Arama işlemi algoritmasıdır. Dizinin ortasındaki değere göre işlem yapar.
  2. Quick Sort: Sıralama işlemi algoritmasıdır. Büyük sayı dizilerinde kullanımı tercih edilir.
  3. Merge Sort: Quick sort gibi bir sıralama algoritmasıdır. Birleştirerek işlem uygular.
Aslında bunlar dışında pek çok yerde uygulanabilir ancak bizler öncelikli olarak bu konular üzerinde bu algoritmanın uygulamasını gerçekleştireceğiz. Kritik nokta, diziyi ikiye bölmektir. Tabii biz hep dizi kullanıyoruz ama linked list gibi yapılar üzerinde de uygulanabilmektedir. Problem çözümünü nlogn süre içerisinde çözmeyi hedeflemektedir. nlogn sayısı, n^2 sayısından daha küçüktür, çünkü logn ifadesi n sayısından küçüktür. Yani bu algoritmaların uygulandığı problemler daha hızlı çözülebilmektedir. Tabii bu her zaman geçerli değil, eldeki veriye hangi algoritmanın uygun olacağını kestirmek size kalmış.

Sıralama Algoritmalarından Merge Sort ve Quick Sort bu mantıkla oluşturulmuştur.

Eğer Merge Sort Sıralama Algoritması konusunu merak ederseniz ilgili makalemizi okuyabilirsiniz. 

Etiketler: ,