Algoritma Tasarımı ve Analizi I (Algorithm Design and Analysis I)

Algoritma Seçme Kriterleri

1. Doğruluk

2. Yapılan İş Miktarı

3. Kullanılan Hafıza

4. Basitlik ve Açıklık

Asimptotik Notasyon (Asymptotic Notation)
Uygulamalarda iki fonksiyon boyutlarını karşılaştırmak için kullanılır. Gösterimler tanımlayan fonksiyon ve işlevleri belirlenmiş kümesi arasında farklı oran büyüme ilişkileri açıklar.

Big Theta Q Notasyonu

Q(g(n)) = {

f(n) :  $ pozitif değer c₁, c₂, ve n_0, öyle ki "n ³  n₀,

0 £ c₁g(n) £  f(n) £ c₂g(n)

}

f(n) Î Q (g(n))

f(n) = Q (g(n))

Egzersiz:

n²/2-2n=Q(n²) c1, c2 ve n0 değerlerini nedir?

0 £ c₁n² £  n²/2-2n £ c₂n²     "n ³  n₀,

0 değerini sağladığı için dikkate alınmaz. Eşitsizliğin her tarafı n²’ ye bölünür.

c₁ £  1/2-2/n £ c₂

lim 1/2-2/n = 1/2  fonksiyon sonsuza gittiğinde üst sınır yani c2 1/2  olacaktır.

 ^n®¥

f(n) fonksiyonunu alttan sınırlandırmak için n değerine şartları sağlayan değerler verilir.

n	1/2-2/n	c1
1	-3/2	Nonpositive
2	-1/2	Nonpositive
3	-1/6	Nonpositive
4	0	Nonpositive
5	1/10	1/10

 

Big O Notasyonu

O(g(n)) = {

f(n) : $ pozitif değer c ve n_0, öyle ki "n ³  n₀,

0 £  f(n) £ cg(n)

}

f(n) = Q (g(n)) →  f(n) = O(g(n))

Q (g(n))  Ì  O(g(n))

Egzersiz:

2n²=O(n³) c ve n0 değerlerini nedir?

0 £  f(n) £ cg(n)

0 £  2n² £ cn³

0 değerini sağladığı için dikkate alınmaz. Eşitsizliğin her tarafı n²’ ye bölünür.

2/n £ c

n	2/n	c
3	0.6	Nonpositive
2	1	2

Big Omega W Notasyonu

W (g(n)) = {

f(n) : $ pozitif değer c ve n_0, öyle ki "n ³  n₀,

0 £ cg(n) £ f(n)

}

f(n) = Q (g(n)) →  f(n) = W (g(n))

Q (g(n))  Ì  W (g(n))

Egzersiz:

sqrt(n)= W(logn) c ve n0 değerlerini nedir?

0 £ cg(n) £ f(n)        "n ³  n₀,

0 £ clogn £        

0 değerini sağladığı için dikkate alınmaz.

n	sqrt(n) / logn	c
1	undefined	undefined
2	1.4142	1

Teorem: 

g(n) ve f(n) iki fonksiyon olsun.

f(n) = Q(g(n))

f(n) = O(g(n)) and f(n) = W(g(n))

Q(g(n)) = O(g(n)) ∩ W(g(n))

Çalışma Zamanları

O(f(n)) worst-case çalışma zamanı  → O(f(n)) her girişin çalışma zamanına bağlı

Q (f(n)) worst-case çalışma zamanı  → Q (f(n)) her girişin çalışma zamanına bağlı

Insertion Sort algortiması ile sıralama en kötü durumda Q(n²) ya da O(n²)'dir. Herhangi bir sıralama algoritması sıralama W(n)'dir, Aslında her gelen öğenin sırasına bağlıdır.  Merge Sort ile sıralama en kötü durumda Q(nlogn)'dir. 

Little o Notasyonu

o(g(n)) = {

f(n): " c > 0, $ n₀ > 0 öyle ki " n ³  n₀,

 0 £  f(n) < cg(n)

}

lim [f(n) / g(n)] = 0

^n®¥

g (n), f(n) için bir üst sınırdır.

Little omega w Notasyonu

w(g(n)) = {

f(n): " c > 0, $ n₀ > 0 öyle ki " n ³  n₀,

0 £ cg(n) <  f(n)

}

lim [f(n) / g(n)] = ¥.

 ^n®¥

g (n), f (n) için bir alt sınırdır.

Fonksiyonlarının Karşılaştırılması

 f « g  »  a « b olmak üzere:

f (n) = O(g(n))  »  a  £   b

f (n) = W (g(n)) »  a  ³  b

f (n) = Q (g(n)) »  a  =  b

f (n) = o(g(n))  »  a  <  b

f (n) = w(g(n)) »  a  >  b

Fonksiyon Limitleri

lim [f(n) / g(n)] = 0 → f(n) Î o(g(n))

^n®¥

lim [f(n) / g(n)] < ¥ → f(n) Î O(g(n))

^n®¥

0 < lim [f(n) / g(n)] < ¥ → f(n) Î Q(g(n))

^n®¥

0 < lim [f(n) / g(n)] → f(n) Î W(g(n))

^n®¥

lim [f(n) / g(n)] = ¥ → f(n) Î w(g(n))

^n®¥

lim [f(n) / g(n)] undefined

^n®¥

Notasyon Özellikleri

Geçişlilik Özelliği

f(n) = Q (g(n)) & g(n) = Q (h(n)) → f(n) = Q (h(n))

f(n) = O(g(n)) & g(n) = O(h(n)) → f(n) = O(h(n))

f(n) = W (g(n)) & g(n) = W (h(n)) → f(n) = W (h(n))

f(n) = o (g(n)) & g(n) = o (h(n)) → f(n) = o (h(n))

f(n) = w(g(n)) & g(n) = w(h(n)) → f(n) = w(h(n))

Dönüşümlülük Özelliği

f(n) = Q (f(n))

f(n) = O(f(n))

f(n)  = W (f(n))

Simetri Özelliği

f(n) = Q (g(n))  →  g(n) = Q (f(n))

Tamamlama Özelliği

f(n) = O(g(n))  →   g(n) = W (f(n))

f(n) =  o(g(n)) →  g(n) = w((f(n))

Bir sonraki yazımda görüşmek üzere...