Yazan : Şadi Evren ŞEKER

Bilgisayar bilimlerinin en önemli konularından birisi olan algoritma analizinin vazgeçilmez teoremidir. Kısaca özyineli (recurrence) bir problemin çözümü için kullanılır. Üç farklı değerin bulunmasını sağlar. Bunlar sırasıyla

O (büyük O, big-oh) : En kötü durum analizidir (worst case analysis)

(büyük teta, Theta) : Ortalama durum analizi (Average case anlaysis)
(büyük omega) : En iyi durum analizi (Best case analysis)

Olarak sıralanabilir. Bu değerlerin hesaplanabilmesi için ve ana metodun (master method) uygulanabilmesi için öncelikle aşağıdaki şekilde bir denkleme ihtiyaç duyulur.

Burada önemli bir uyarı, ana metodun (master method) her denkleme uygulanamayacağıdır. Sadece yukarıdaki şekilde denklemlere uygulanabilir. Bu denklemde ayrıca , , ve fonksiyonu asimptotik olarak pozitif bir fonksiyon olmalıdır. Ayrıca gösterimi ile ya yada değeri kastedilmektedir. Başlangıç değeri olarak eşitliği birkaç terimde sağlanabilir. Yani denklem ilk terimler için kararsız çalışabilir ve ortalama olarak tek adımda sonuca erişebilir ancak unutulmaması gereken nokta özyineli denklemlerin çözümünde sonsuza giden analizden bahsedilmektedir. Yukarıdaki denklemin ayrıca bir özelliği de parçala ve fethet (divide and conquer) yaklaşımı olmasıdır. Dikkat edilirse problem b parçaya bölünmektedir. Yani her adımda a alt problem olarak tanımlanabilecek terim n/b boyutunda eleman içermektedir. fonkisyonu ise bu bölme ve birleştirme işlemlerinin maliyetini tutmaktadır.

Master Theorem

Yukarıdaki tanıma uygun olarak

, , asimptotik pozitif, ve olarak tanımlanmış bir denklemimiz olsun.

1. öyle bazı , dolayısıyla .
2. , dolayısıyla .
3. öyle bazı , ve şayet öyle bazı vardır ki büyük n tanımlamak yeterlidir, ve sonuçta denilebilir.

Örnekler

• olarak verilmiş olsun. Çözüm için , ,olarak alınır ve olduğu bulunur. Ayrıca , eşitliği ana metoddan yazılabilir. Dolayısıyla (2). Duruma uygun olarak bulunmuş olunur.

• olarak verilmiş olsun. Çözüm için , , olarak alınır ve . olduğu bulunur. Ayrıca eşitliğinden , olduğu bulunur. . eşitliği ana metoddan yazılabilir. Dolayısıyla (1) Duruma uygun olarak bulunmuş olunur.

Birleştirme sıralamasının ana teorem ile karmaşılığının hesaplanması (Mahir Bey’in sorusu üzerine ekliyorum)

Öncelikle birleştirme sıralamasının (Merge sort) özyineli denklemini (recursive equation) yazmaya çalışalım. Bilindiği üzere sıralama algoritmamız üzerinde işlem yaptığı veri yapısını (örneğin bir dizinin (array) ) parçalara bölerek ilerler. Kodu aşağıda verilmiştir:

Yukarıdaki kodun 25. ve 26. satırlarında bölünen iki parça kendi içerisinde sıralanmaktadır. Bu parçalar problemin ikiye bölünmüş alt parçalarıdır.

Bölünen parçalar tek elemanlı olunca birleştirme işlemi başlar. Bu durumu aşağıdaki şekilde formülleyebiliriz:

Yukarıdaki formülde dikkat edileceği üzere eleman sayısının tek olması durumunda sıralama işleminin çalışma süresi 1 olmaktadır. Bunun dışında problem iki ayrı n/2 parçaya bölünmektedir. n değerinin çift sayı olmaması gibi durumlar düşünülecek olursa, bir elemanın ya sağda ya da soldaki kısma dahil olması dolayısıyla parçalardan birisi diğerine göre bir eleman fazla alabilir. Bunun için yukarıdaki denklemde parçalardan birisinin tavan değeri alınırken diğerinin taban değeri alınmıştır.

Sonuç olarak n>1 durumu için iki ayrı parçanın ayrı ayrı hesaplanan özyineli (recursive) denklemlerinin toplamına dn gibi sabit bir değer ilave edilmektedir. Bu değer birleştirme işleminin o anlık maliyetidir.

Yukarıdaki denklemin çözümünü kolaylaştırmak için n = 2^k olarak kabul edelim. Bu durumda denklemi aşağıdaki şekilde açmak mümkün olabilir:

Bu denklemde bölme işlemini yapar ve değerleri toplarsak

Yukarıdaki bu denklemi açarak bir ve iki seviye daha ilerletecek olursak:

Denlemleri elde edilir. Bu denklemlerde dikkat edileceği üzere d2^k değerinin çarpanı açılan seviye ile aynıdır. Dolayısıyla denklemin son haliyle ana teoremi uygulayabiliriz. f(n)=n için n^log_b^a değeriolarak 1 yazılabilir. Bu durumda teoremimizde yazdığı üzere T(n) = Θ ( n log n) olarak fonksiyonun karmaşıklığı bulunmuş olunur.