Asymptotic Notations

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


Bir önceki yazımda da belirttiğim gibi algoritmaların etkinliği büyüme oranı ile ölçülür. Bu değerlerin karşılaştırılması ve ifade edilebilmesi için asymptotik ifadeler kullanılır: Oh, Theta, Omega. Bunları incelemeden önce kullanacağımız bir kaç fonksiyondan bahsedeyim. t(n) dediğimde bu algoritmanın çalışma süresidir, g(n) ise t(n) fonksiyonunu karşılaştıracağımız basit bir fonksiyondur.

Big-Oh(g(n)) yani O(g(n)), g(n)'den düşük veya aynı orandaki tüm fonksiyonları kapsar. Örnek vermek gerekirse:

n € O(n^2), 100n + 5 € O(n^2), 1/2n(n-1) € O(n^2)

Eğer t(n) fonksiyonu O(g(n)) sınıfı içerisinde ise;

t(n) <= cg(n) for all n > n0

Şeklinde bir ifade kullanabiliriz. Örnek yapalım, 100n + 5 € O(n^2) ifadesini kanıtlayalım:

100n + 5
100n + 5 <= 100n + n = 101n
101n <= 101n^2

Burada n0 değeri 5, c değeri 101 oldu. Tanım bize büyük bir aralık veriyor, yani c ve n0 değerlerini seçmekte özgürüz diyebiliriz:

100n + 5
100n + 5 <= 100n + 5n = 105n

Burada c değeri 105, n0 değeri 1 oldu. t(n) € O(g(n)) şeklinde bir varsayımda bulunmuştuk. Bunu grafiksel olarak ifade etmek istersek:



Oh notasyonunu gördük. Farklı durumlarda farklı notasyonları kullanabiliriz. Şimdi de Omega notasyonunu görelim. Eğer t(n) € Theta(g(n)) ise;

t(n) >= cg(n) for all n >= n0

Örnek yapalım ve n^3 € Omega(n^2) olduğunu kanıtlayalım:

n^3 >= n^2 for all n >= 0

Burada c değerini 1, n0 değerini 0 seçtik. Theta notasyonuna bakalım. Eğer t(n) € Theta(g(n)) ise;

c2g(n) <= t(n) <= c1g(n) for all >= n0

Bir örnek yapalım ve 1/2n(n-1) € Theta(n^2) olduğunu kanıtlayalım. İlk olarak sağ taraftan başlayalım:

1/2n(n-1) = 1/2n^2 - 1/2n <= 1/2n^2 (c1 = 1/2)

Sol tarafı da kanıtlayalım:

1/2n(n-1) = 1/2n^2 - 1/2n >= 1/2n^2 - 1/2n1/2n = 1/4n^2 (c2 = 1/4)


Sonraki Yazı: Mathematical Analysis of Nonrecursive Algorithms
Yorumlar

Henüz bir yorum bulunmuyor.