Algoritmalarda Big O Notasyonu Nedir?

Merhaba değerli okurlar bu yazımda sizlere Algoritmalarda Big O Notasyonu Nedir? konusundan bahsedeceğim.

Yazılım dünyasında sıkça “Bu kod çok yavaş” veya “Şu algoritma daha hızlı” gibi cümleler duyarız. Peki, bir kodun “hızlı” ya da “yavaş” olduğunu nasıl objektif bir şekilde ölçebiliriz? Benim bilgisayarımda 1 saniyede çalışan bir kod, daha güçlü bir bilgisayarda 0.1 saniyede çalışabilir. O zaman “süre” tek başına iyi bir ölçüt değil, değil mi?

İşte bu noktada Big O Notasyonu devreye giriyor.

Big O, bir algoritmanın ne kadar “verimli” olduğunu anlatan evrensel bir dildir. Ama burada “verimlilik” saniye veya dakika cinsinden ölçülmez. Bunun yerine, algoritmanın başa çıkması gereken veri miktarı (input) arttıkça, yapması gereken işlem sayısının nasıl arttığını ifade eder.

En basit haliyle Big O, şu soruya cevap verir: “Eğer listemdeki eleman sayısını 10 kat artırırsam, algoritmamın çalışma süresi kabaca ne kadar artar?”

Hadi bu gizemli görünen ifadeleri, günlük hayattan örneklerle tek tek ele almaya çalışalım. Algoritmamızdaki “veri miktarına” bundan sonra ’n’ diyeceğiz. Eğer 100 elemanlı bir listemiz varsa, n = 100'dür.

1. O(1) — Sabit Zaman

Bu, hayal edebileceğiniz en verimli durumdur. Anlamı şudur: Veri miktarı (n) ne kadar artarsa artsın, işlem süresi değişmez. Her zaman sabittir.

• Bir kitap yığınınız var. Size “En üstteki kitabı ver” dediğimde, yığında 10 kitap da olsa, 1 milyon kitap da olsa, yapacağınız işlem hep aynıdır: Elinizi uzatıp en üstteki kitabı almak. Tek bir hareket.
• Kod Dünyasında karşılığı ise; Bir listenin ilk elemanını almak.

Hemen Dart koduyla görelim;

int getFirstElement(List<int> list) {
  return list[0]; // Listenin boyutu ne olursa olsun, bu hep 1 adımdır.
}

Listenin 5 elemanı da olsa, 5 milyon elemanı da olsa, bu fonksiyon hep aynı hızda çalışır. İşte bu O(1)’dir.

2. O(n) — Doğrusal Zaman

Bu en yaygın ve anlaşılır durumdur. Veri miktarı (n) ne kadar artarsa, işlem sayısı da aynı oranda (doğrusal olarak) artar.

• Kitap yığınında belirli bir kitabı arıyorsunuz, ama kitapların sırası karışık. Ne yaparsınız? En üstten başlayıp teker teker her kitaba bakarsınız. 10 kitap varsa, en kötü ihtimalle 10 kitaba bakarsınız. 100 kitap varsa, en kötü ihtimalle 100 kitaba bakarsınız. Kitap sayısı 2 katına çıkınca, arama süreniz de kabaca 2 katına çıkar.
• Kod Dünyası: Bir listedeki tüm elemanları ekrana basan basit bir for döngüsü.

void printAllElements(List<int> list) {
  for (int element in list) { // Liste ne kadar uzunsa, döngü o kadar çok çalışır.
    print(element);
  }
}

Liste 10 elemanlıysa döngü 10 kez, 1.000.000 elemanlıysa 1.000.000 kez döner. n arttıkça, işlem sayısı da n kadar artar. İşte bu O(n)’dir.

3. O(n²) — Karesel Zaman

Anlamı şudur: Veri miktarı (n) arttıkça, işlem sayısı onun karesiyle orantılı olarak fırlar. Bu genellikle verimsiz bir durumun işaretidir.

• Bir partidesiniz ve odadaki herkesin birbiriyle el sıkışmasını istiyorsunuz.
• Odada 2 kişi varsa: 1 el sıkışma olur.
• Odada 3 kişi varsa: A, B ile; A, C ile; B, C ile el sıkışır. Toplam 3 el sıkışma.
• Odada 10 kişi varsa: Her bir kişi diğer 9 kişiyle el sıkışacağı için çok daha fazla el sıkışma olur. (Kabaca 10 * 10 = 100 civarı bir işlem)
• Kişi sayısı (n) biraz arttığında, el sıkışma sayısı (n²) patlar! Bu, verimsiz bir tanışma yöntemidir.
• Kod Dünyası: İç içe geçmiş iki for döngüsü, genellikle bu duruma yol açar. Tıpkı makaledeki “Kabarcık Sıralaması” (Bubble Sort) gibi.

void compareEverythingWithEverything(List<int> list) {
  for (int itemA in list) { // Dıştaki döngü 'n' kere döner.
    for (int itemB in list) { // İçteki döngü de her seferinde 'n' kere döner.
      // itemA ve itemB'yi karşılaştır...
    }
  }
}

Eğer liste 10 elemanlıysa (n=10), içteki döngü dıştaki her bir adım için 10 kez çalışır. Toplamda 10 * 10 = 100 işlem yapılır.
Eğer liste 100 elemanlıysa (n=100), toplamda 100 * 100 = 10.000 işlem yapılır.
Liste sadece 10 kat büyüdü ama işlem sayısı 100 kat arttı! İşte bu felaket senaryosu O(n²)’dir ve büyük veri setlerinde kesinlikle kaçınmamız gereken bir durumdur.

O(log n) — Logaritmik Zaman

Bu, “Böl ve Fethet” algoritmalarında (Merge Sort gibi) görülen inanılmaz verimli bir durumdur. Her adımda problemi yarıya indirirsiniz. Tıpkı bir sözlükte kelime aramak gibi. Ortadan açar, aradığınız kelimenin bu yarıda olup olmadığına bakar ve diğer yarısını tamamen elersiniz. 1 milyon kelimelik bir sözlükte bile bir kelimeyi 20–25 adımda bulabilirsiniz. Bu çok hızlıdır!

Özetle, Big O Notasyonu, kodumuzun kaderini öngören sihirli bir kristal küre değil, aksine bize yol gösteren mantıksal bir pusuladır. Bu pusula bize saniyeleri veya milisaniyeleri değil, çok daha değerli bir şeyi gösterir: Ölçeklenebilirliği. Veri setimiz küçükken fark edilmeyen bir O(n²) canavarının, uygulamamız büyüdüğünde nasıl bir performans kabusuna dönüşebileceğini önceden haber verir. Bize, O(1)’in anlık zarafeti ile O(n)’in makul ve öngörülebilir maliyeti arasındaki farkı anlatır.

Peki bu bilgiyi yarın kod yazarken nasıl kullanacaksınız?

Amaç, yazdığınız her satırın Big O’sunu ezberlemek veya her fonksiyona takıntılı bir şekilde analiz yapmak değil, bir sezgi geliştirmektir.

• Artık iç içe bir for döngüsü gördüğünüzde, aklınızın bir köşesinde kırmızı bir ışık yanacak: “Bu liste büyürse ne olur?”
• Bir kullanıcıyı ID’si ile binlerce kişilik bir liste içinden bulmanız gerektiğinde, aklınıza hemen List.firstWhere gibi potansiyel bir O(n) işlemi yerine, anında erişim sağlayan bir Map yapısının (O(1)) gücü gelecek.
• Bir problemi çözerken artık sadece “çalışıyor mu?” diye sormayacak, aynı zamanda “verimli çalışıyor mu?” ve “1 milyon kullanıcıya ulaştığında da çalışacak mı?” sorularını kendinize soracaksınız.

Big O’yu anlamak, sizi sadece kod yazan birinden, yazdığı kodun gelecekteki etkilerini düşünen bir geliştiriciye dönüştürür. Bu, yazdığınız çözümlerin sadece bugünün problemlerini çözmesini değil, aynı zamanda yarının zorluklarına karşı da dayanıklı ve performanslı kalmasını sağlayan bir düşünce biçimidir. Bu pusulayı doğru kullanmak, sizi daha bilinçli, daha öngörülü ve nihayetinde daha iyi bir geliştirici yapacaktır.

Umarım bu yazım ilgilisi ve meraklısı için faydalı olur. Sonraki yazılarda görüşmek üzere…

Github: www.github.com/abdullah017
Linkedin: www.linkedin.com/in/abdullahtas
Stackoverflow: https://stackoverflow.com/users/13807726/abdullah-t

#FREEPALESTINA