Algoritma & Veri Yapıları

Big O gösterimi: algoritma karmaşıklığını pratik örneklerle anlamak

Editör 6 saat önce · 0 görüntülenme

Big O gösterimi, bir algoritmanın girdi büyüdükçe ne kadar yavaşladığını (ya da ne kadar bellek kullandığını) anlatmanın standart yoludur. Teknik mülakatların vazgeçilmezidir ama asıl önemi günlük kodda doğru tercihi yapmaktır.

Temel fikir

Big O kesin süreyi değil, büyüme hızını ölçer. 10 elemanlı listede her algoritma hızlıdır; fark 1 milyon elemanda ortaya çıkar. Sabit çarpanlar ve küçük terimler yok sayılır: 3n + 5 işlem yapan bir algoritma O(n)'dir.

En sık karşılaşılan karmaşıklıklar

Gösterim	Adı	Örnek
O(1)	Sabit	Dizide indeksle erişim, hash tablosunda arama
O(log n)	Logaritmik	Sıralı dizide ikili arama
O(n)	Doğrusal	Listede tek tek arama
O(n log n)		İyi sıralama algoritmaları (merge sort)
O(n²)	Karesel	İç içe iki döngü
O(2ⁿ)	Üstel	Tüm alt kümeleri denemek

1 milyon eleman için kabaca: O(log n) ≈ 20 adım, O(n) = 1 milyon, O(n²) = 1 trilyon adım.

Günlük koddan bir örnek

Bir listede tekrar eden eleman var mı diye bakmak:

# O(n²): her elemanı diğer hepsiyle karşılaştırır
def tekrar_var_mi(liste):
    for i in range(len(liste)):
        for j in range(i + 1, len(liste)):
            if liste[i] == liste[j]:
                return True
    return False

# O(n): küme (set) ile tek geçiş
def tekrar_var_mi_hizli(liste):
    gorulen = set()
    for x in liste:
        if x in gorulen:
            return True
        gorulen.add(x)
    return False

İkinci sürüm biraz ek bellek harcar ama büyük listelerde binlerce kat hızlıdır. Bu, sık karşılaşılan bir zaman–bellek takasıdır.

Gizli maliyetler

Python'da x in liste O(n)'dir, x in kume ortalama O(1)'dir. Döngü içinde listede arama yapmak fark etmeden O(n²) üretir.
Döngü içinde veritabanı sorgusu atmak (N+1 sorgu sorunu) da aynı mantıkla uygulamayı yavaşlatır.
Dizinin başına eleman eklemek çoğu dilde O(n)'dir çünkü tüm elemanlar kayar.

Karmaşıklığı hesaplamak için pratik kurallar

Ardışık adımlar toplanır, en büyüğü kalır: O(n) + O(n²) = O(n²).
İç içe döngüler çarpılır.
Her adımda problemi yarıya indiren yapı (ikili arama gibi) O(log n)'dir.

Nasıl çalışmalı?

Temel veri yapılarının (dizi, bağlı liste, hash tablosu, yığın, kuyruk, ağaç, heap) işlem maliyetlerini bilmek çoğu soruyu çözmeye yeter. Pratik için LeetCode, HackerRank ya da Codeforces gibi sitelerde kolay sorulardan başlayıp her çözümün karmaşıklığını kendin yazmaya çalış.

Bir kodun karmaşıklığını hesaplayamadıysan kodu bu konuya ekleyip sorabilirsin.

#algoritma #big-o #veri-yapilari