Özyinelilerde Ana Teorem (Master Theorem)

Özyinelilerde Ana Teorem (Master Theorem)

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 = 2k 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 d2k değerinin çarpanı açılan seviye ile aynıdır. Dolayısıyla denklemin son haliyle ana teoremi uygulayabiliriz. f(n)=n için nlogba değeriolarak 1 yazılabilir. Bu durumda teoremimizde yazdığı üzere T(n) = Θ ( n log n) olarak fonksiyonun karmaşıklığı bulunmuş olunur.

Ana Teoremde 4. Kural

Gelen soru üzerine, aslında klasik olarak ana teoremde geçmeyen dördüncü kuralı da ekleme ihtiyacı doğmuştur. Yazının altında eklenen sorularda, f(n) fonksiyonunun logaritmik olması durumu verilmiştir. Bu durum klasik 3 duruma girmez. Klasik üç durumda da f(n) fonksiyonunun tam polinom olması beklenir. Oysaki logaritmik bir fonksiyon polinom değildir. Bu durumları içeren ve f(n) fonksiyonunun polilogaritmik olması halini kapsayan özel bir 4. durumu aşağıdaki şekilde tanımlayabiliriz.

Yukarıdaki şekilde bir f(n) fonksiyonu verilmesi durumunda T(n) fonksiyonunun asimptotik üyeliği gösterilmiştir. Burada k>=1 olması gerekliliği bulunur.

Örnek:

şeklinde verilen denklemi ele alalım.

Bu denklemin sonunda bulunan f(n) kısmı, logaritmadır. Bu durumda

Şeklinde değişkenler sıralanabilir. Yani verilen denklemde a=2 ve b = 2 olarak verilmiş, f(n) fonksiyonu ise nlogn olarak verilmiştir.

Bu durumda, sonuç yukarıdaki son satırda gösterildiği gibi logaritma kare olarak ifade edilir.

Gelelim, yazıya bu kısmı eklememize sebep olan soruya.

Bu denklemin sonucu, bir önceki denklemde olduğu gibi

Olarak bulunacaktır. Sebebi ise, denklemde bulunan 6/3 = 2 olması ve dolayısıyla k=1 için verilen ilk T(n) fonksiyonunun ana teoreme konulması sonucunda k+1 = 2 olarak bulunmasıdır.

Daha açık yazacak olursak:

Şeklinde yazılan denklemde değeri, asimptotik bağlantıdan dolayı orijinal denklemimizdeki 2 değeri olarak düşünülebilir. Bu durumda k=1 değeri bir arttırılarak

Sonucunu buluyoruz.

Yorumlar

  1. Reply
    Mahir

    hocam ornek bir programlaam fonksiyonu icin yapabilir misiniz bir tane ?

    mesela
    factryl(x){return x* factryl(x-1);}

    Simdiden tesekkurler

  2. Reply
    Şadi Evren ŞEKER Article Author

    Bilerek mi sordunuz bilmiyorum ancak, özyinelilerde ana teorem (master theorem), özyineli faktöriyel fonksiyonu veya fibonacci fonksiyonu gibi fonksiyonlar için kullanılamaz. Bunun sebebi ilgili fonksiyonların ana teorem ile gösterilebilir birer denkleminin kurulamamasıdır. Ana teorem ( Master Theorem) uygulanabildiği problemler, parçala fethed (divide and conquere) yaklaşımı ile çözülebilen ve problemin üzerinde çalıştığı etki alanını (domain) her defasında parçalara ayıran (ve elbette daha sonra birleştiren) algoritma tipleridir. Faktöriyel fonksiyonu ise ne yazık ki bu şekilde problemi parçalara bölmek gibi bir özyinelemeye sahip değildir.

    Ancak sorunuzu bir kod üzerinden ana teoremin nasıl çalıştığı şeklinde ele alırsak yazının içerisine birazdan birleştirme sıralaması (merge sort) için nasıl kullanabileceğimizi eklemeye çalışırım.

    başarılar

  3. Reply
    Mahir

    Peki hocam bekliyorum. Eger siz bana parcalanabilen bir ornekte anlatabilirseniz, ben neden recursive fonksiyonlarda ve fibonacci fonksiyonunda tanimlayamayacagimizi cok daha iyi anlarim.
    Saygilar

  5. Reply
    Şadi Evren ŞEKER Article Author

    Master teoremin uygulanabilmesi için f(n) kısmının polinom olması gerekir. Yani yukarıdaki 3 durum için de f(n) bir polinom olmalıdır. Sizin sorunuzda ise logaritmik bir f fonksiyonu vermişsniz. Sorunuzda f(n) = n^2. lg(n) şeklinde geçen fonksiyon bir polinom değildir.

    Bu durumda master teoremin üç durumu da uygulanamaz. Ancak master teoremin klasik 3 durumu dışında geçen 4. bir durumu daha vardır. Logaritmik fonksiyonlar için kullanılabilir.
    Bu 4. durumu yukarıda yeni bir başlık altında yayınlayıp sizin sorunuzun çözümünü de ekliyorum.

  6. Reply
    freelancer03

    merhaba hocam.
    bu konuyu anlamaya çalışıyorum. Sorum şöyle T(n)=4T(n/2) + 3n algoritmasının karmaşıklığı nedir diyor. Şimdi a=4, b=2 a/b=2 dir.burda f(n)=3n dir. Eğer f(n)=3n^2 olsaydı, f(n)=n^2=Theta(n^log2^4)eşitiliğini esas alarak 2.duruma göre incelicektim. Soruda fn(3n)oldugundan 1.duruma uygun olarak Theta(n^2) çıkıyor. Fakat şıklarda bunun cevabı Big-oh(n^2) olarak belirtiliyor. Çözümde bir yanlışlık mı var?

  7. Reply
    Şadi Evren ŞEKER Article Author

    sanırım bir karışıklık var. 1. duruma uygun olması halinde çözüm big-oh olarak geçer. Yani ana teoremdeki klasik 3 durum :
    1. big-oh
    2. big-theta
    3. big-sigma

    durumlarından birisidir. Şayet 1. duruma uygunsa zaten otomatik olarak big-oh çıkar. Bunun anlamı da elimizdeki fonksiyonun üst sınırını bulduğumuzdur (upper bound). Diğer bir deyişle big-oh üst sınırı veya en kötü durum analizini (worst case analysis) ifade eder.

  8. Reply
    freelancer03

    people.csail.mit.edu/thies/6.046-web/master.pdf

    linkteki pdf te 16. örnekte 3T (n/3)+ n/2 verilmiş ve bu 4.cu duruma uygunmuş. 4. duruma göre uygun olmasının sebebi f(n) fonksiyonunun divide and conquer yöntemine uygun olmasımıdır?

    18 . örnekte de 4T (n/2)+ n/log n buda 1. yönteme uygun.
    Yukardaki yazıda geçen örnek çözümlerini anladım. Fakat 16. ve 18. örneklerde farklı bir durum sözkonusu. f(n) fonksiyonu kesirli ve farklı değerler olunca farklı durumlarda inceleniyor.
    Kısacası kesirli olan problemlerin hangi duruma uygun olduğunu pek anlayamadım.

  9. Reply
    Şadi Evren ŞEKER Article Author

    ben mi yanlış okuyorum bilmiyorum ama verdiğiniz bağlantıdaki 16. örnek, 2. duruma uygun (case 2) olarak belirtilmiş.

    Çok kabaca anlatacak olursak f(n) fonksiyonunun üstünde altında veya eşit olmasına göre, ilk üç durumdan birisi uygulanır. Logaritmik olması durumundaysa 4. durum uygulanır.

  10. Reply
    freelancer03

    Estagfurullah hocam yanlış okumuyorsunuz. Ben derdimi tam anlatamadım.
    evet pdf te 16. ornek case 2 olarak belirtilmiş. pdf in 1. sayfasında 3 adet master teorem tanımlanmış. pdf de tanımlanan master teoremde, case 2 olarak belitilen durum yukardaki yazıya göre 4. duruma denk düşüyor.
    Teşekkürler. Vaktinizi aldım kusura bakmayın 🙂

  11. Reply
    Şadi Evren ŞEKER Article Author

    şimdi anladım 🙂 4. durum klasik master theorem’de olmayan bir durum. Sizin verdiğiniz bağlantıda, soru çözümleri 4. durum olmaksızın ele alınmış. Yukarıdaki yazıda da belirtmeye çalıştım 4. durum istisnai bir durumdur. Ama ilk üç durumdan 2. durum olarak değerlendirilebilir (theta sonucu verir).

    Tekrar ele alacak olursak, f(n) fonksiyonunun üst veya alt sınırı olmasına göre, aynı sırayla big-oh veya big-omega olur. f(n) fonksiyonuyla eşit hareket ise theta olarak değerlendirilir.

    Bu fonksiyonların çizimlerini ve hareketlerini http://www.bilgisayarkavramlari.com/2010/06/17/karmasiklik-siniflari-complexity-classes/ adresinde açıklamaya çalışmıştım.

  14. Reply
    Barış

    Hocam verilen bir koddan ana denklemi nasıl çıkartabilirim.Yani recurnesi.T(n)=aT(n/2)+f(n) gibi bir fonsiyon bulmam gerekiyor burada a,b ve f(n) degerlerini bulmada zorlanıyorum.Yardımcı olabilirmisiniz?

  15. Reply
    Şadi Evren ŞEKER Article Author

    Güzel bir soruymuş. Verilen bir koddan çıkarmak oldukça detay gerektiren bir iş ama belki sorunuzu biraz kısıtlarsak size yardımcı olacak bir cevap bulabiliriz. Örneğin sorunuzu, verilen bir fonksiyon olarak sınırlasak, ilave olarak fonksiyonu da aşağıdaki şablonda kabul etsek:

    int T ( int n){
  if(koşul)
    return başlangıç //basis
  return g(T( f(n) ) );
}

    bu durumda zaten sorun çözülmüş olur:

    T(n) = g(T(f(n))) şeklinde dönüşüm yapabilirsiniz.

    Örneğin aşağıdaki kodu ele alalım:

    int T ( int n){
  if(n==0)
    return 0;
  return T(n-1) + 1;
}

    Yukarıdaki kod, çok basitçe verilen sayıya kadar olan sayıları toplar. buradaki f ve g fonksiyonları aşağıdaki şekilde yazılabilir:

    f(n) = n-1
    g(n) = n+1

    Dolayısıyla özyineli denklemimiz (recursive equation) aşağıdaki şekildedir:

    T(n) = T(n-1) + 1

    Benzer şekilde bütün kodu analiz edip özyineli denklemlere döndürmek istiyorsanız (veya en azından döndürmeye çalışmak) o zaman yukarıdaki gibi şablonlar oluşturup bu şablonlara uyan yapıları çevirmeyi deneyebilirsiniz. Örneğin bir döngü (loop) da yukarıdaki şekilde çevrilebilir. Ancak bilgisayar bilimlerinde bildiğiniz üzere bütün kodların bu şekilde çevrilmesi imkansızdır.

    Başarılar

  16. Reply
    Barış

    Hocam öncelikle Bilgi verdiğiniz için çok teşekkür ediyorum.

    şu şekilde bir fonk. var

         mın(A,I,R)
      if(I==R) return A(I)
     
      else t1=mın(A,I,(I+R)/2)
           t2=mın(A,(I+R)/2+(1),R)
       İF(t1< =t2) return t1
       else return t2

    şeklinde fonksiyon var.

    Ben burada T(n)= a*T(n/b) + f(n) fonksiyon yapısında

    a:altprogram sayısı
    b:bu alt program ana programın 1/2 si olarak ele aldım

    a=2,b=2 olarak buldum ama f(n) hakkında bir yorum yapamıyorum.

    F(n) i nasıl bulabilirim.

    hocam haftaya sınıvım var bu konularla ilgili örmek olan bi kaynak önerebilir misiniz ?

    Her şey için çok teşekkür ediyorum...

  18. Reply
    muammer

    Hocam merhaba. T(n)= T[n^(1/3)]+1 && T(1)=1 gibi bir soruda nasıl bir yol izleyebiliriz? Karmaşıklığı ne olur? Teşekkürler.(T[n^(1/3)]–> küp kök n.)

Bir cevap yazın

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir