Master(Ana) Teoremi ve Özyinelemeli Algoritma Analizi

Egemen Gulpinar
4 min readMar 8, 2021

--

Ö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.

Özyinelemeli olarak faktöriyel hesap örneği

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.

Özyinelemeli Faktöriyel Algoritması Analizi

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.

Özyinelemeli faktöriyel hesabının karmaşıklık analizi

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.

Master Teoremi

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.

Özyinelemeli Algoritma Örneği ve Parametre Değerleri(1.Kısım)

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.

Master Teorem Örneği 2.Kısım

Peki bu epsilon(ε) değerini nasıl bulacağız, +ε,-ε veya 0 durumunu ne belirler?

epsilon değerinin bulunması(1.Kısım)

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

epsilon değerinin bulunması(2.Kısım)

Şimdi ise Teoremdeki hangi kategoriye girdiğini bulduktan sonra sadece yerine yazmak geriye kalıyor

Master Teorem Örneği 3.Kısım

2.bir örnek daha yaparak konuyu tam anlaşılır kılmak istiyorum. Adımları dikkatli takip edelim.

Master Teorem ve Parametreler(Ör2) 1.Kısım

Özyinelemeli olarak tanımlandırıldı. Değerlerin kontrolleri yapıldı, parametrelerin değerlerini yazdık. Şimdi teoremdeki hangi tanıma uygun bakabiliriz.

Master Teorem ve Parametreler(Ör2) 2.Kısım

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.

Master Teorem ve Parametreler(Ör2) 3.Kısım

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

Free

Distraction-free reading. No ads.

Organize your knowledge with lists and highlights.

Tell your story. Find your audience.

Membership

Read member-only stories

Support writers you read most

Earn money for your writing

Listen to audio narrations

Read offline with the Medium app

--

--

Egemen Gulpinar
Egemen Gulpinar

Written by Egemen Gulpinar

IIS M.Sc. at Bielefeld University Computer Engineer at LIVAD Technologies Inc. AI / Automation / Cloud / Entrepreneurship / R&D

No responses yet

Write a response