03 MAYIS 2017
PERŞEMBE
16.44
Büyük O Notasyonu (Big O Notation)

Algoritmalar işlenirken aslında en fazla dikkat çekilmesi gereken konulardan biri de Big O'dur. Çünkü oluşturulan bir algoritmanın en kötü durumu gözler önüne alınarak ne kadar işlemden geçeceğini hesaplamak gerekir. Bu durum ise Big O ile hesaplanır.

 

Basit bir düşünce ile başlayalım. Elimizde hiçbir şekilde döngü vs. bulunmayan ve sadece dışarıya "A" çıktısını veren bir fonksiyon düşünün.

void deneme (int x, int y) {
	cout << x << " ve " << y;
}

int main(){
	int a,b;
	cin >> a;
	cin >> b;
	deneme(a,b);
}

Kod yapımızda kullanıcının girdiği iki değeri deneme isimli fonksiyonu gönderiyoruz ve fonksiyonumuzun içerisinde de kullanıcının girdiği sayı değerlerinin arasına ve ekleyerek gösteriyoruz. Peki buradaki çalışma mantığına bakarsak kod değerinin yalnızca 1 kez döngüden geçtiğini gözlemliyoruz. Yani ekrana bir kez x ve y olarak çıktı veriliyor. Bu sebeple bu yapı için O(1) ifadesini kullanabiliyoruz.

Peki işler biraz daha farklı olsaydı;

void deneme (int x, int y) {
	for(int a=0; a<10; a++) {
		cout << a+1 << ") " << x << " ve " << y << endl;
	}
}

int main(){
	int a,b;
	cin >> a;
	cin >> b;
	deneme(a,b);
}

Fonksiyonumuza bir for döngüsü ekleseydik ve bu for döngümüzü de tam 10 kez çalışacak şekilde ayarlasaydık, bu hali ile O(10) olarak ifade edebilirdik.

İşleri biraz daha ileriye götürelim ve kod olarak değil de bir fonksiyon olarak ele alalım.

ÖRNEK

Elimizde şöyle bir fonksiyonumuz olsun;

f(x) = x2 + 2x + 1

Bu fonksiyonumuzun büyüme fonksiyonunun x2 olduğunu (aslında O(x2)) nasıl anlayabiliriz?

ÇÖZÜM

Fonksiyonumuzu matematiksel ifadeler ile açıklamak gerekirse;

x > 1 için; x2+2x+1 <= x2+2x2+x2

O halde: x2+2x+1 <= 4x2

f(x) için O(x2)'dir.

Biraz daha mantıksal olarak bakmak gerekirse;

Elimizdeki fonksiyonun en büyük katsayısının aslında bizim Big O olarak tabir ettiğimiz yapı olduğunu söyleyebiliriz. Diğer tüm değerleri en büyük değere eşitleyerek ilerlediğimiz bu yapımızda sondaki 4 gibi rakamlar ise hiçbir anlam ifade etmemektedir. Çünkü buradaki amaç aslında işlemin en çok ne kadar gerçekleşebileceğini bulabilmektir. Bu sebeple bakıldığında bu işlemin x2'den daha fazla gerçekleşme payı yoktur. Bu da aslında kodlamalardaki en kötü senaryo olayını açıklamaktadır.

Bir başka senaryoyu inceleyelim. Binary Search olayında bahsettiğimiz gibi amaç sıralı bir diziden bir elemanı en çabuk nasıl bulabilirizdir. Bu olayı gerçekleştirirken en kötü senaryo olan en sonda bulma işlemine göz atalım. n elemanlı bir dizide her defasında yarıya indirgeyerek arama yapmaktayız. n/2 - n/4 - n/8 ... Ki bu olay n/n olana kadar sürmekte. Burda farkettiğimiz gibi bölüm 2 sayısının kuvvetlerini kapsamakta..

21 = 2
22 = 4
23 = 8

Bu durumda 2a = n diyebiliriz. Burada logaritma kuralını hatırlayalım;

log2n = a ifadesinin 2a = n olduğunu biliyoruz. O halde bu işlemin kaç adımda gerçekleşeceğini bulabilmek için log2n ifadesine bakmalıyız. O zaman O(log2n) bizim aradığımız cevaptır.

Büyüme Fonksiyonlarında Dikkat Edilmesi Gereken Durum

Herhangi bir fonksiyonun büyüme fonksiyonu tespit edilirken aslında aranan en küçük büyüme fonksiyonudur. Yani eğer f(x) için O(x3) denilebiliyor ise f(x) için aynı zamanda O(x4) ifadesi de kullanılabilir. Çünkü büyüme hızlarına bakıldığında x4 ifadesindeki büyüme hızı x3 ifadesinden daha fazladır. Fakat biz en küçük büyüme fonksiyonunu aradığımız için O(x3) dememiz gerekir.

En Hızlı Fonksiyondan En Yavaş Fonksiyona

1 -> logn -> n -> n.logn -> n2 -> n3 -> 2n -> n!

YORUMLAR 0
Bu konuya henüz kimse yorum yapmadı.
İlk yorumu sen yapmak ister misin?
YORUM BIRAK
Şuanda bu yoruma cevap yazıyorsunuz:
İptal Et