Big O: Algoritmaların Büyüme Hızını Anlatan Gösterim

Big O notasyonu nedir?

Big O notasyonu, bir algoritmanın çalışma süresinin ya da bellek kullanımının girdi büyüdükçe hangi hızla arttığını anlatan gösterimdir. Sabit saniyeleri değil, büyüme eğrisinin şeklini ifade eder. Girdinin büyüklüğü n ile gösterilir; O(n) bir algoritmanın süresinin girdiyle doğru orantılı arttığı anlamına gelir.

Notasyonun gücü, algoritmaları bilgisayardan ve programlama dilinden bağımsız karşılaştırabilmesidir. Bir algoritma hızlı bir makinede çalışsa da yavaş bir makinede çalışsa da, girdi çok büyüdüğünde büyüme eğrisi belirleyici olur. Bu yüzden algoritma karmaşıklığı ve zaman karmaşıklığı ifadeleri sıklıkla Big O ile birlikte anılır.

Yaygın karmaşıklık sınıfları

En sık karşılaşılan sınıflar, en hızlıdan en yavaşa doğru şöyledir:

• O(1), sabit zaman: girdi büyüse de iş aynı kalır. Bir dizideki elemana indeksle erişmek ya da karma tabloda ortalama durumda anahtar aramak.
• O(log n), logaritmik: her adımda problemin yarıya indiği durum. Sıralı listede ikili arama.
• O(n), doğrusal: her elemana bir kez bakılır. Sırasız listede arama.
• O(n log n): etkin sıralama algoritmalarının tipik maliyeti, örneğin birleştirme sıralaması.
• O(n²), karesel: iç içe döngüler. Basit sıralama yöntemleri ve tüm çiftleri karşılaştıran işlemler.
• Üstel ve faktöriyel büyüme: her yeni elemanda işin katlandığı durumlar, örneğin tüm alt kümeleri ya da tüm sıralamaları denemek. Küçük girdilerin ötesinde pratik değildir.

Bu sıralamayı bilmek, bir algoritmanın büyük veride ölçeklenip ölçeklenmeyeceğini hızlıca tahmin etmeye yarar.

Big O nasıl hesaplanır?

Hesap, kodun adımlarına bakarak yapılır:

• Girdiyle büyüyen döngüleri ve özyinelemeli çağrıları belirleyin. Girdiye bağlı olmayan işlemler sabit kabul edilir.
• Ardışık bloklar toplanır, iç içe döngüler çarpılır. Bir döngü içinde başka bir döngü varsa maliyet çarpımdır.
• Sabit çarpanlar atılır: işi katlayan bir sabit çarpan eklenirse karmaşıklık yine O(n) kalır.
• Düşük dereceli terimler atılır: n kare artı n ifadesi, büyük n için n kare ile aynı büyüklükte davranır, bu yüzden O(n²) yazılır.
• Hangi durumu anlattığınızı belirleyin: en kötü durum, ortalama durum ya da en elverişli durum. Başka bilgi verilmediyse genellikle en kötü durum kastedilir.

Bellek karmaşıklığı da aynı yöntemle çıkarılır, ancak bu kez algoritmanın girdiye bağlı olarak ayırdığı ek alan sayılır.

Küçük bir örnek: listelerde ortak eleman bulmak

Örneğin bir çift liste verilmiş ve ortak elemanlar isteniyor. İlk çözüm, birinci listedeki her eleman için ikinci listeyi baştan sona taramaktır. İç içe döngüler olduğundan maliyet O(n²) olur; listeler büyüdükçe süre karesel biçimde artar.

İkinci çözümde birinci listenin elemanları önce bir kümeye (karma tabloya) yazılır. Sonra ikinci listedeki her eleman için kümede arama yapılır. Kümede arama ortalama durumda O(1) olduğundan toplam maliyet O(n) olur. Karşılığında ek bir küme tutulduğu için bellek kullanımı artar. Bu, zaman ve bellek arasındaki tipik değiş tokuştur: hızı artırmak için bellek harcanır.

Big O ile ilişkili kavramlar

Zaman karmaşıklığı işlem adımlarının sayısındaki büyümeyi, uzay (bellek) karmaşıklığı ise ek bellek ihtiyacındaki büyümeyi ifade eder. İkisi birbirini tamamlar ve sıklıkla biri iyileştirilirken diğeri kötüleşir.

Big O üst sınırı anlatır. Alt sınır için Omega, hem alt hem üst sınırın aynı olduğu sıkı sınır için Theta gösterimi vardır. Günlük konuşmada ve mülakatlarda genellikle Big O kullanılır. Amortize analiz ise nadir pahalı işlemlerin çok sayıdaki ucuz işleme yayılmasıyla ortalama maliyeti hesaplar; dinamik dizilerin büyümesi buna örnektir.

Veri yapıları, karmaşıklık kararlarının zeminidir. Aynı işlem, seçilen yapıya göre farklı maliyet taşır: dizi, bağlı liste, karma tablo ve ağaç yapılarında arama, ekleme ve silme maliyetleri farklıdır. Bu yüzden Big O, algoritma ve veri yapıları konularıyla birlikte öğrenilir.

Sık yapılan hatalar ve Mindset bağlamı

Sık yapılan hatalar: • Big O'yu gerçek çalışma süresi sanmak. O(n) bir algoritma, küçük girdilerde sabit çarpanı yüksek olduğu için O(n²) olandan yavaş çalışabilir. • Girdinin ne olduğunu net tanımlamamak. Birden çok listeyle çalışan bir algoritmada karmaşıklık tek n ile değil, her listenin büyüklüğüyle ifade edilmelidir. • Gizli maliyetleri atlamak: dizgi birleştirme, dilimleme ya da kopyalama işlemleri döngü içinde sanıldığından pahalı olabilir. • Yalnızca elverişli durumu düşünmek; sorun en kötü durumda ortaya çıkar. • Erken optimizasyon: küçük ve sabit boyutlu veride karmaşıklığı düşürmek için kodu zorlaştırmak.

Mindset kataloğunda bu konu farklı eğitimlerde işlenir. Veri Yapıları ve Algoritmalar eğitimi karmaşıklık analizi ve temel yapılar, yığın, kuyruk ve karma tablolar, ağaç yapıları, sıralama ve arama algoritmaları, çizge algoritmaları, dinamik programlama başlıklarını içerir. Teknik Mülakat ve Algoritma Hazırlığı eğitimi ise karmaşıklık analizi ve yaklaşım, temel veri yapıları ve kullanım kararı, problem çözüm kalıpları, mülakat simülasyonu başlıklarını kapsar.