MERT TOPUZ

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.

Elimizde şöyle bir fonksiyonumuz olsun;

f(x) = x² + 2x + 1

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

Fonksiyonumuzu matematiksel ifadeler ile açıklamak gerekirse;

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

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

f(x) için O(x²)'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 x²'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..

2¹ = 2
2² = 4
2³ = 8

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

log₂n = a ifadesinin 2^a = n olduğunu biliyoruz. O halde bu işlemin kaç adımda gerçekleşeceğini bulabilmek için log₂n ifadesine bakmalıyız. O zaman O(log₂n) 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(x³) denilebiliyor ise f(x) için aynı zamanda O(x⁴) ifadesi de kullanılabilir. Çünkü büyüme hızlarına bakıldığında x⁴ ifadesindeki büyüme hızı x³ ifadesinden daha fazladır. Fakat biz en küçük büyüme fonksiyonunu aradığımız için O(x³) dememiz gerekir.

En Hızlı Fonksiyondan En Yavaş Fonksiyona

1 -> logn -> n -> n.logn -> n² -> n³ -> 2ⁿ -> n!