Özyinelemeli (Rekürsif) Algoritma Analiz Teknikleri ve Örnekler

Özyinelemeli (recursive) algoritmayı analiz etmek, küçük parçaları oluşturan iş miktarını hesaplamayı ve tüm probleme çözüm getiren hesaplamayı gerektirir.

Özyinelemeli algoritma analizi, diğer algoritma analizlerinden farklıdır. Bunun temel nedeni, programın çalışma süresinin sadece yapılan işlemlere değil aynı zamanda programın kendi çalışma süresinin bir fonksiyonuna da bağlı olmasıdır.

Özyineli Algoritmaların Zaman Etkinliği Analizinin Genel Planı :

1. Girdi büyüklüğünü gösteren parametrelerin belirlenmesi
2. Algoritmanın temel işleminin belirlenmesi
3. Girdi büyüklüğüne bağımlı olarak temel işlemin kaz kez gerçekleştiğinin bulunması (Aynı büyüklükteki girdiler için farklı sayıda gerçekleşiyorsa en kötü, en iyi, ortalama durum incelemeleri)
4. Temel işlemin kaç kez gerçekleştiğinin bir özyineleme ilişkisiyle gösterilmesi
5. Özyinelemenin çözülmesi ve büyüme derecesinin araştırılması

Özyinelemeli (Recursive) algoritmaların çalışma sürelerinin analizi

• Recursive algoritmaların çalışma süreleri recurrence ifadelerle tanımlanır
• Bir recurrence ifade küçük giriş değerleri için bir fonksiyon tanımlar

Recurrence ifadelerin çözümü :

• Böl ve Yönet (divide- conquer)

· Tekrarlı substitution metodu

• Recursion-trees

• Master metod

Böl ve Yönet (Divide- Conquer) :

Büyük problemleri parçalara ayırarak çözer. Sonra her bir parçaya algoritmayı uygular. Bilinen en genel algoritma dizayn tekniğidir. Böl ve yönet algoritma planı:

1. Problem aynı tipte alt problemlere bölünür.

2. Alt problemler çözülür.

3. Eğer gerekliyse alt problemler birleştirilir. Diyagram olarak:

Örn: n sayı toplama problemi

a0,…,a n−1

Eğer n>1 ise problemi 2’ye böleriz. İlki[n/2] toplamı hesaplama diğeri [n/2] toplamı hesaplama

Bu iki toplamın her birini aynı metodu kullanarak hesaplamak için:

Böl- yönet paralel hesaplama için uygundur. Çünkü her process bir alt problemi çözebilir.

Tipik olarak böl yönet algoritmaları n boyutu b alt boyuta böler. Yani n/b alt boyut oluşur. A alt elemandan oluşur. Çalışma zamanı T(n) aynı zaman n b’nin bir kuvvetidir.

T(n)=a.T(n/b)+f(n)

Çünkü b her zaman 2’nin üssü şeklindedir. F(n) n boyutlu bir örneği bölmek ve ya birleştirmek için harcanan zaman için hesaplanan fonksiyondur. (a=b=2 ise f(n)=1)

T(n) a ve b sabit değerlerine ve f(n) fonksiyonunun büyümesine bağlıdır.

Tekrarlı Substitution Metodu

• Merge sort algoritmasının çalışma süresi (bazı b değerleri için n — 2b olduğunu varsayalım).

işlem akışı:

• Substitute

• Expand

• Substitute

• Expand

Sonuçlar incelenir (Observe) ve Ah substitution’ dan sonra ifadenin nasıl devam ettiği bulunur.

Merge sort için daha kesin çalışma süresi bulma (bazı b değerleri için n — 2 b alınırsa).

Recursion Tree :

• Recursion tree görsel olarak iterasyonların çalışmasını gösterir.
• Recurrence ifadeler için asymtotic çözüm tahmininde iyi bir yoldur.

Master Metodu :

Aşağıdaki yapıdaki recurrence ifadelerin çözümü için kullanılır.

T(n) aT(n/b) + f(n)

• a 2 1 ve b » 1, ve f pozitif.

• Rn) bir algoritmanın çalışma süresidir.

• n” boyutunda a tane alt problem recursive olarak çözülür ve herbiri 7(n/b) süresindedir

• (n) problemin bölünmesi ve sonuçların birleştirilmesi için geçen süredir. Merge-sort için T (n) 2T(n/2) + 8(n) yazılabilir.

Verilen bir recurrence ifade için T(n) aT(n/ b) + f (n)

Fibonacci Örneği :

public int fibonacci(int sayi) {

if ( ( sayi == 0 ) || ( sayi == 1 )

return sayi;

else

return fibonacci( sayi — 1 ) + fibonacci( sayi — 2 );

}

Hanoi Kulleleri Örneği :

Bu puzzle’de farklı boyutlarda n diske sahibiz. Bunlar 3 çubuktan herhangi birine geçirilebilir. Önce disklerin hepsi küçükten büyüğe ilk çubukda bulunur. Hedef bunları eğer gerekliyse ikinciyi kullanarak üçüncüye taşımak. Bir seferde bir disk oynatabiliriz. Küçüğün üzerine büyük yerleştirmek mümkün değildir.

Faktöriyel Örneği :