Mathematical Analysis of Recursive Algorithms

Kategori: Algorithm Design and Analysis , 10 Haziran 2020 , JanFranco


Recursive olmayan algoritmaların analizini gördük. Bu bölümde recursive algoritmaların analizini yapacağız. Bir örnekle başlayalım:


Algorithm F(n)

if n = 0 return 1
else return F(n - 1) * n
Bu algoritmaya ilk baktığımızda iki denklem elde ediyoruz:

M(n) = M(n-1) + 1
M(0) = 0

Bu denklemler bize ne anlatıyor? İlk denklemdeki +1, return değerindeki * n işleminden geliyor. Burada bir çarpma işlemi yapılıyor. Bu nedenle bir ekledik. M(0)'da ise yani n = 0 olduğundan sadece 1 değeri return ediliyor. Yani çarpma işlemi yapılmıyor. Bu nedenle M(0) = 0 oluyor. Bir pattern yakalamaya çalışalım:


M(n) = M(n-1) + 1
M(n-1) + 1 = (M(n-2) + 1) + 1
M(n-2) + 2 = (M(n-3) + 1) + 2
...
Pattern'den gördüğümüz gibi;

M(n) = M(n-i) + i

Peki i = n olduğunda;

M(n-n) + n = n

Görüldüğü gibi n değerini elde ettik. Recursive algoritmalardan Tower of Hanoi probemini ele alalım. n kadar disk en altta en büyük disk, en üstte en küçük disk olmak üzere sıralı bir şekilde çubukta dizili. Bu diskleri başka bir çubuğa sıralı bir şekilde koymak istiyoruz. Arada başka bir çubuk da kullanabiliriz. Burada yapılması gereken işlem şu, n-1 kadar diski ikinci çubuğa yerleştir, daha sonra en büyük diski direk üçüncü çubuğa yerleştir. Kalan diskleri ikinci çubuktan sırayla üçüncü çubuğa yerleştir. Bu mantıkla ve temel operasyonun disk taşıma olduğunu varsayarak aşağıdaki denklemleri elde ederiz:

M(n) = M(n-1) + 1 + M(n-1) for n > 1
M(1) = 1

Denklemleri biraz toparlarsak:

M(n) = 2M(n-1) + 1
M(1) = 1

Bir pattern yakalamaya çalışalım:

M(n) = 2M(n-1) + 1
2M(n-1) + 1 = 2(2M(n-2) + 1) + 1 = 2^2M(n-2) + 2 + 1
2^2M(n-2) + 3 = 2^2(2M(n-3)+1) + 3 = 2^3M(n-3) + 2^2 + 2 + 1

Görüldüğü gibi aşağıdaki formülü elde edebiliriz:

M(n) = 2^i M(n-i) + 2^i-1 + 2^i-2 + ... + 2 + 1 = 2^i M(n-i) + 2^i - 1

i = n-1 olduğunda;

M(n) = 2^n-1M(n-(n-1)) + 2^n-1 - 1 = 2^n - 1

Elde ettiğimiz sonuçla birlikte bu algoritmayı O(2^n) sınıfına dahil edebiliriz. Bir önceki bölümdeki BinRec algoritmasını recursive bir biçimde yazalım:


Algorithm BinRec(n)

if n = 1 return 1
else return BinRec([n/2]) + 1
Buradan direk aşağıdaki denklemleri çıkarabiliriz:

A(n) = A([n/2]) + 1
A(1) = 0

Burada her adımda n / 2 işlemi yapıldığında, pattern yakalayabilmek için n = 2^k cinsinden yazmalıyız. Dönüştürelim:

A(2^k) = A(2^k-1) + 1
A(2^0) = 0

Pattern yakalayalım:


A(2^k) = A(2^k-1) + 1
A(2^k-1) + 1 = A(2^k-2) + 1 + 1 = A(2^k-2) + 2
A(2^k-2) + 2 = A(2^k-3) + 3
...
= A(2^k-i) + i
Genel formülü elde ettik ve 2^k değerini girersek;

A(2^k) = A(1) + k = k

Orjinal n değerimize geri dönelim:

n = 2^k
k = log(2)n

Böylece:

A(n) = log(2)n

Demek ki bu algoritmayı O(log n) sınıfına sokabiliriz.


Sonraki Yazı: Brute Force - Selection Sort and Bubble Sort
Yorumlar

Henüz bir yorum bulunmuyor.