4 min read

Divide and conquer (böl ve yoket) algoritması

Bu yazıda böl ve yoket yaklaşımı ile algoritmalarda performans kazanımını inceliyoruz.
Divide and conquer (böl ve yoket) algoritması

Divide and conquer yani böl ve yoket yöntemi doğru yerde ve doğru şekilde uygulandığında büyük bir performans kazanımı sağlayabilir. Burada böl ve yoket derken kastettiğimiz şey, yapılmak istenen kompleks bir işlemi çok küçük atomik işlemlere bölerek bunları çözmek, ve ardından bu çözümleri birleştirerek asıl sonuca ulaşmaktır.

Böl ve yoket yöntemi hangi durumlarda kullanılır

Böl ve yoket yöntemi her problem tipinde kazançlı değildir. Özellikle sıralı bir veri dizisinde arama yapılıyorsa, böl ve yoket yaklaşımı bu veriyi parçalara bölerek işe başlayacağından daha en başta işlenmeyecek olan kısımları devre dışı bırakarak bu verilerle zaman kaybetmemizi önleyecektir. Binary search bu mantık üzerine çalışır.

Ayrıca küçük sonuçların birleşerek büyük sonuca gittiği sorting(sıralama) gibi işlemlerde de tercih edilebilir. Örneğin Merge sort, quick sort, vb. Yalnız bu küçük sonuçlar tekrarlıyorsa, bu durumda Dinamik Programlama kullanılması daha performanslı olacaktır.

Böl ve yoket yöntemi nasıl çalışır

Bildiğiniz gibi belirli bir özelliğe sahip olan bir veya daha fazla elemanı bulmak için bütün bir diziyi baştan sona taramak, algoritmanın çalışma zamanının lineer yani O(n) olacağı anlamına gelir.

Bunu azaltabilmek ve logaritmik zaman seviyesine düşürebilmek için kullandığımız yöntemi değiştirmemiz, yani her elemanı tek tek taramaktan vazgeçmemiz gerekir.

Eğer veri dizisi önceden sıralanmışsa, bütün verileri tek tek kontrol etmeye gerek yok demektir. Dizinin sıralı oluşu bizi arama işleminde 1-0 önden başlatan bir durumdur. Bunun sebebi sıralı bir dizide aradığınız şeyin yaklaşık olarak hangi bölgede olduğunu tespit etmeniz çok kolaydır. Bu şekilde hızlı bir biçimde aradığınız bölgeye yoğunlaşıp sonuç alırsınız.

Binary search yani ikili arama algoritması uyguladığımızda bütün diziyi taramak yerine diziyi tek elemanlı parçalara bölüp bunlarda arama yaparak, logaritmik zamanda işlemi tamamlamayı başarırız.

Merge sort ve Quick sort algoritmalarında da bir diziyi sıraya koymak için önce tek elemanlı parçalara bölüp, bu parçaları sıralayarak ilerleriz. Sıralanmış olan küçük parçalar recursive olarak birleşerek, sonuçta tek ve bütün olarak sıralanmış haldeki diziyi ortaya çıkarırlar.

Böl ve yoket yaklaşımı ile çözülebilen problemler

  • Sıralama: Merge sort ve Quick sort algoritmaları ile bir array'in elemanları sıraya dizilebilir
  • Eleman arama, eksik veya farklı elemanı bulma: Binary search algoritması ile bir array'de arama yapılabilir
  • En yakındaki verileri bulma: Böl ve yoket yaklaşımı ile bir noktaya en yakın verileri tespit edebiliriz

Kaynaklar

Divide and Conquer Algorithm | Introduction - GeeksforGeeks
A computer science portal for geeks. It contains well written, well thought and well explained computer science and programming articles, quizzes and practice/competitive programming/company interview Questions.
Divide and Conquer - GeeksforGeeks
A computer science portal for geeks. It contains well written, well thought and well explained computer science and programming articles, quizzes and practice/competitive programming/company interview Questions.
Divide & Conquer (D&C) Problems - Techie Delight
Divide and conquer (D&C) is an algorithm design paradigm based on multi-branched recursion. A divide and conquer algorithm works by recursively breaking down a problem into two or more sub-problems of the same or related type, until these become simple enough to be solved directly. The solutions to …
Data Structures - Divide and Conquer - Tutorialspoint
Data Structures - Divide and Conquer - In divide and conquer approach, the problem in hand, is divided into smaller sub-problems and then each problem is solved independently. When we keep on dividin
Binary Search Algorithm | Recursive & Iterative Implementation
Given a sorted array of `n` integers and a target value, determine if the target exists in the array or not in `O(log(n))` time using binary search algorithm in C, Java, and Python. If the target exists in the array, print an index of it.