Master(Ana) Teoremi ve Özyinelemeli Algoritma Analizi
Özyinelemeli Algoritmalar Nedir ?
Özyinelemeli algoritmalar, kendi kendini çağıran, bir döngü içine girmeksizin iterasyona devam edebilen yapılardır. Büyük kolaylıklar sağlayıp karmaşıklık oranlarını düşürmekte kullanılabilir. Ufak bir hatırlatma için örnek yapalım.
Faktöriyel Hesabını for döngüsü içerisinde de yapabilirdik. Ancak bu bize daha maliyetli olacaktı. Bunun yerine özyinelemeli olarak yapıyoruz. Karmaşıklığı daha düşük ve çalışması daha hızlı (Bu örnek için geçerli). Her problemde kullanılmasa da algoritma dünyasındaki yeri çok büyüktür.
Yukarıdaki örneğin nasıl çalıştığına bir göz atalım.
sonuç olarak, 5*4*3*2*1 işlemleri icra ediyor. Ve koşul ifadesinden n değeri 0 olana kadar devam ediyoruz. 0 olduğu zamanda ise, tekrar fonksiyon çağrımı yapmadan return ediyoruz.
Peki bu algoritma anlaşıldı, ancak nasıl karmaşıklığını hesaplayacağız? Diyorsanız aşağıda işlemlere başlıyorum.
T(n) = T(n-1) + 1 ifadesi, yukarıdaki sorumuzda bulunan F(n-1)*n değerini temsil etmekte. T(n-1) ifadesi xxx adet çarpma işlemi F(n-1) ifadesini, +1 değeri ise çarpmak için*n ifadesini temsil eder.
Bununla beraber, sadece yerine koyma metodu dışında farklı çözüm yollarıda mevcuttur. Bunlardan biri de, (gerekli şartlar sağlandığı takdirde) Master Teoremi’dir.
Master Teoremi Özyinelemeli Fonksiyon(recursive function)’un asimtotik karmaşıklığını bulmak için kullanılan bir yöntemdir.
Bu teoremi ve beraberinde getirdiği formüller kafanızı karıştırmasın. Adım adım ilerleyip açıklayacağım.
T(N) = aT(n/b) +f(n)
a = kaç parçaya bölündüğü
T(n/b) = her parçanın boyutu
f(n) = her adımın maliyeti
Öncelikle ε(epsilon) değerine göre 3 adet durum mevcuttur diyebiliriz. Bu değerin + ε ,-ε, veya eşit olmasını bulacağız.
Çözüm adımları
- Bir algoritmanın master teorem ile çözülmesi için, bunun özyinelemeli(recursive) denklem olarak çevirilmesi gereklidir.
- Devamında Master Teorem’deki gerekli şartlar sağlandığı kontrol edilmeli.
- Son olarak sağlanan şarta göre eşitliklere bakılıp sonuç bulunur.
Örnek ile Genel Bir Bakış
→ T(n) = T(n/2) + O(1)
olarak soru verilsin ve bunun master teorem ile çözülüp çözülmeyeceğini, çözülürse nasıl bir yol izleyeceğiz bundan bahsedelim.
Değerleri tanımlayıp a,b ve f(n) değerlerini bulduk. Devamında kontrollerimize başlayalım;
Bizim sorumuzdaki f(n) değerimiz bildiğiniz üzere O(1)’di. Aşağıda buna dikkat edelim.
Peki bu epsilon(ε) değerini nasıl bulacağız, +ε,-ε veya 0 durumunu ne belirler?
karşılaştırılması yapılır. Şayet aralarında fark var ise, f(n) değerine eşitlemeye çalışırız. Örneğin kendi hesaplamamız n³ çıktı ve f(n) = n², bu eşitliği sağlamak için -ε değerini yazarız(ε = 1 olursa 3–1 = 2 ve n² icra edilir). Bu sayede eşitlik sağlanmış olur.
ε değerinin hangisi olacağını bulduktan sonra, ilgili teorem türünü seçebiliriz
Şimdi ise Teoremdeki hangi kategoriye girdiğini bulduktan sonra sadece yerine yazmak geriye kalıyor
2.bir örnek daha yaparak konuyu tam anlaşılır kılmak istiyorum. Adımları dikkatli takip edelim.
Özyinelemeli olarak tanımlandırıldı. Değerlerin kontrolleri yapıldı, parametrelerin değerlerini yazdık. Şimdi teoremdeki hangi tanıma uygun bakabiliriz.
1.Kuralın geçerliliği olduğunu tespit ettik. Şimdi ise sonucumuz, 1.Kuralın bize sunmuş olduğu karmaşıklık tanımında.
Basit, olabildiğince sade tutarak özyinelemeli fonksiyonların karmaşıklığını ve master teoremiyle nasıl çözülebileceği konusunda bilmeyenler için hazırladığım makalenin sonuna geldik. Eğer 3.kuralın örneklerini ve nasıl kullanıldığına dair çözüm istenirse ilerleyen haftalarda bu konu üzerine de bir makale yayınlarım.
Ek Kaynaklar:
[1]. Algoritmalar — Robert Sedgewick | Kevin Wayne
[2].Doç. Dr. Şadi Evren Şeker | Bilgisayarkavramlari.com
