Big O Notasyonu Nedir?

Big O notasyonu nedir?

Big O notasyonu, bir algoritmanın veri miktarı arttıkça ne kadar yavaşladığını anlatan bir gösterimdir. Saniye cinsinden süre vermez, çünkü süre bilgisayara göre değişir. Bunun yerine büyüme biçimini anlatır: veri iki katına çıkınca iş de iki katına mı çıkıyor, yoksa dört katına mı?

Nasıl okunur?

Gösterimdeki n, girdinin boyutunu ifade eder. En sık karşılaşılan sınıflar şunlardır:

Gösterim	Adı	Örnek
O(1)	Sabit	Dizide belirli sıradaki elemana erişmek
O(log n)	Logaritmik	Sıralı listede ikili arama
O(n)	Doğrusal	Listede tek tek arama
O(n log n)	Doğrusal logaritmik	Birleştirmeli sıralama
O(n²)	Karesel	Kabarcık sıralaması

Big O genellikle en kötü durumu anlatır. Sabit çarpanlar ve küçük terimler göz ardı edilir; 3n + 5 adım süren bir işlem O(n) olarak yazılır.

Somut bir karşılaştırma

10.000 kişilik bir öğrenci listesinde iki farklı yöntem düşünün. O(n) bir algoritma kabaca 10.000 adım atar. O(n²) bir algoritma ise 100 milyon adıma ulaşır. Liste 100.000 kişiye çıktığında ilki 100.000 adıma, ikincisi 10 milyar adıma çıkar. Bu yüzden büyük veride algoritmanın sınıfı, donanımın hızından çok daha belirleyicidir.

Pratikte nasıl kullanılır?

Kodunuzu okurken iç içe döngüler arayın. Bir listeyi dolaşan döngünün içinde aynı listeyi tekrar dolaşan ikinci bir döngü varsa, büyük olasılıkla O(n²) bir yapı vardır. Bu konunun ayrıntıları zaman karmaşıklığı maddesinde ele alınır. Yazılım mülakatlarında hemen her algoritma sorusunun ardından "bunun Big O değeri nedir?" diye sorulduğunu da hesaba katın.