Big-O Karmaşıklığı Kod Örnekleriyle Nasıl Hesaplanır?

Big-O karmaşıklığı, girdi boyutu büyüdükçe bir algoritmanın çalışma adımı ve ek bellek ihtiyacının nasıl ölçeklendiğini ifade eder. Kodun belirli bir bilgisayarda tam olarak kaç saniyede çalışacağını söylemez; farklı girdiler büyüdüğünde algoritmanın davranışını karşılaştırmayı sağlar.

Bir kod parçasını analiz ederken önce girdinin boyutunu n ile temsil eder, ardından işlemlerin veya ek veri yapılarının n arttıkça nasıl değiştiğine bakarız. Aşağıdaki örnekler, Big-O mantığını öğrenmek için kullanılan temel kalıplardır; tüm algoritmaları kapsayan bir liste değildir.

Big-O karmaşıklığı neyi ölçer?

Bir algoritmanın karmaşıklığı genellikle iki açıdan incelenir: zaman karmaşıklığı ve bellek karmaşıklığı.

• Zaman karmaşıklığı: Girdi büyüdükçe algoritmanın gerçekleştirdiği temel işlemlerin nasıl arttığını gösterir.
• Bellek karmaşıklığı: Algoritmanın çalışırken ihtiyaç duyduğu ek alanın girdi boyutuna göre nasıl değiştiğini gösterir.

Örneğin bir listedeki eleman sayısını n kabul edelim. Bir algoritma listedeki her elemanı bir kez kontrol ediyorsa işlem sayısı yaklaşık olarak n ile birlikte büyür. Liste iki katına çıktığında yapılacak kontroller de yaklaşık iki katına çıkar. Bu davranış O(n) ile ifade edilir.

Big-O gösteriminde sabit katsayılar ve düşük dereceli terimler genellikle göz ardı edilir. Bunun nedeni, girdi çok büyüdüğünde algoritmanın genel davranışını asıl belirleyen terimin baskın hâle gelmesidir.

• 3n + 5 ifadesinde baskın terim n olduğu için karmaşıklık O(n) kabul edilir.
• n² + n ifadesinde n büyüdükçe n² daha etkili olduğu için karmaşıklık O(n²) olur.

Buradaki gösterim, belirli bir bilgisayardaki kesin süreyi veya kesin işlem sayısını vermez. Örneğin iki farklı O(n) algoritmasından biri pratikte diğerinden daha hızlı olabilir. Big-O daha çok büyüme eğrisini, yani girdi genişledikçe maliyetin hangi hızla arttığını anlatır.

O(1), O(n), O(log n), O(n log n) ve O(n²) nasıl ayırt edilir?

O(1): Sabit zamanlı işlem

def first_item(items):
    return items[0]

1. İşlem sayısı: Listenin uzunluğu ne olursa olsun tek bir indeksteki elemana erişilir.

2. n ile ilişki: Liste 10 veya 10 milyon elemanlı olsa da yapılan temel işlem sayısı yaklaşık olarak değişmez.

3. Sonuç: Zaman karmaşıklığı O(1)’dir. Yeni bir veri yapısı oluşturulmadığı için ek bellek karmaşıklığı da O(1)’dir.

O(n): Tüm girdiyi bir kez dolaşma

def total(items):
    result = 0
    for item in items:
        result += item
    return result

1. İşlem sayısı: Döngü, listedeki her eleman için bir kez çalışır.

2. n ile ilişki: Liste n elemanlıysa yaklaşık n toplama işlemi yapılır.

3. Sonuç: Zaman karmaşıklığı O(n)’dir. Yalnızca result ve item gibi sabit sayıda değişken kullanıldığı için ek bellek karmaşıklığı O(1)’dir.

O(log n): Arama alanını her adımda küçültme

def binary_search(items, target):
    left, right = 0, len(items) - 1

    while left <= right:
        middle = (left + right) // 2

        if items[middle] == target:
            return middle
        if items[middle] < target:
            left = middle + 1
        else:
            right = middle - 1

    return -1

Bu yöntem, sıralı bir listede arama alanını her turda yaklaşık yarıya indirir.

1. İşlem sayısı: Her döngüde listenin tamamı değil, kalan arama alanının yarısı incelenir.

2. n ile ilişki: Alanın yarıya inmesi için gereken tur sayısı yaklaşık log₂ n kadardır.

3. Sonuç: Zaman karmaşıklığı O(log n)’dir. Ek bir liste veya veri yapısı oluşturulmadığından ek bellek karmaşıklığı O(1)’dir.

O(n log n): n düzeyindeki işlemi log n aşamayla birleştirme

def sort_items(items):
    if len(items) <= 1:
        return items

    middle = len(items) // 2
    left = sort_items(items[:middle])
    right = sort_items(items[middle:])

    return merge(left, right)

Bu, böl-ve-yönet yaklaşımını kullanan sıralama algoritmalarının sadeleştirilmiş biçimidir. Liste parçalara ayrılır, alt parçalar sıralanır ve sonuçlar birleştirilir.

1. İşlem sayısı: Her seviyede elemanların işlenmesi toplamda yaklaşık n düzeyindedir.

2. n ile ilişki: Listeyi ikiye bölme işlemi yaklaşık log n seviye sürer. Her seviyedeki n düzeyindeki çalışma bu seviyelerle birleşir.

3. Sonuç: Zaman karmaşıklığı O(n log n)’dir. Bu örnekte parçalar oluşturulduğu için ek bellek kullanımı uygulamaya bağlıdır; tipik bir birleştirmeli sıralama uygulamasında ek bellek O(n) olabilir.

O(n²): İki iç içe döngü

def compare_all(items):
    for first in items:
        for second in items:
            print(first, second)

1. İşlem sayısı: Dış döngü n kez, iç döngü de her dış döngü adımında n kez çalışır.

2. n ile ilişki: Toplam işlem sayısı yaklaşık n × n = n² olur.

3. Sonuç: Zaman karmaşıklığı O(n²)’dir. Yeni bir veri yapısı oluşturulmadığı için ek bellek karmaşıklığı O(1)’dir.

Ardışık işlemler toplanır, iç içe döngüler çarpılır

Bir kodda işlemler art arda çalışıyorsa karmaşıklıklar toplanır; ancak Big-O gösteriminde büyümeyi belirleyen en baskın terim bırakılır. Örneğin O(n) + O(n) + O(1) işlemi, sabitleri ve küçük terimleri göz ardı ettiğimizde O(n) olur. Döngüler birbirinin içine yerleşmişse durum değişir: dış döngünün tekrar sayısı ile iç döngünün tekrar sayısı çarpılır.

toplam = 0

for sayi in liste:
    toplam += sayi

maksimum = liste[0]

for sayi in liste:
    if sayi > maksimum:
        maksimum = sayi

İlk döngü listeyi bir kez dolaşır ve O(n) zamanda çalışır. İkinci döngü de listeyi bir kez dolaştığı için yine O(n) maliyetindedir. Başlangıçta yapılan atama ise O(1) kabul edilir. Sonuç O(n) + O(n) + O(1) = O(n), yani O(n) olur. İki ayrı döngü bulunması, kodu otomatik olarak O(n²) yapmaz.

Karşılaştırma için aşağıdaki iki yapıyı inceleyelim:

# Tek döngü: hedefi arama
for sayi in liste:
    if sayi == hedef:
        bulundu = True
        break

# İç içe iki döngü: tüm çiftleri karşılaştırma
for i in range(len(liste)):
    for j in range(len(liste)):
        karsilastir(liste[i], liste[j])

Buradaki temel karar çerçevesi şudur: Her elemanı bir kez işlemek, toplamı hesaplamak veya maksimumu bulmak gibi işlemler genellikle doğrusal büyür. Her elemanı diğer tüm elemanlarla eşleştirmek ise her yeni eleman için yeniden karşılaştırmalar yaptığı için karesel büyür. Bu nedenle bir listenin toplamını ve maksimumunu arka arkaya hesaplayan çözüm, toplamda iki geçiş yapsa da O(n) kalır; tüm çiftleri karşılaştıran çözüm ise O(n²) olur.

Koşullar, erken çıkış ve en kötü durum nasıl analiz edilir?

if/else bloklarındaki dallar art arda değil, alternatif olarak çalışır. Bu nedenle iki dalın maliyetlerini toplamak yerine genellikle daha maliyetli dal dikkate alınır:

if kosul:
    sonuc = sabit_islem()       # O(1)
else:
    sonuc = listeyi_dolaş()     # O(n)

Koşul doğru olduğunda işlem O(1), yanlış olduğunda O(n) sürer. Her iki dal aynı çalışmada yürütülmediği için genel üst sınır O(n) kabul edilir.

Erken çıkış, en iyi ve en kötü durum arasındaki farkı açıkça gösterir:

for sayi in liste:
    if sayi == hedef:
        return True

return False

Hedef ilk elemandaysa döngü hemen biter ve en iyi durum O(1) olur. Hedef listenin ortalarında bulunabilir veya hiç bulunmayabilir; bu durumlarda kaç elemanın inceleneceği veri dağılımına bağlıdır. Hedefin son elemanda olması ya da hiç bulunmaması, en fazla elemanın kontrol edildiği en kötü durumu oluşturur: O(n). Ortalama durum için sabit bir oran varsaymak doğru değildir; sonuç, hedeflerin ve verilerin nasıl dağıldığına göre değişir.

Önce sıralayıp sonra aramak da benzer biçimde toplam maliyetle değerlendirilmelidir. Sıralama maliyeti, ardından yapılan arama maliyetine eklenir. Yalnızca bir kez arama yapılacaksa sıralama için harcanan ek süre gereksiz olabilir. Çok sayıda arama yapılacaksa başlangıçtaki sıralama maliyeti, sonraki aramaları hızlandırdığı için daha anlamlı hâle gelebilir. Karar verirken yalnızca aramanın değil, tüm işlem akışının büyüme hızına bakmalısın.

Bu ayrımlar, algoritmik düşünmenin temel parçalarındandır. AP Computer Science Principles sınav hazırlığı için çalışırken Big-O’nun resmî kapsamını ayrıca kontrol etmek önemlidir: College Board’un güncel ders açıklamasında algoritmik verimlilik kavramı yer alsa da formel Big-O analizi ve matematiksel formüller sınav kapsamı dışında belirtilmektedir.

Bellek karmaşıklığı: Ek veri yapıları ve liste kopyaları

Big-O analizi yalnızca algoritmanın ne kadar sürede çalıştığını değil, çalışırken girdinin dışında ne kadar ek bellek kullandığını da inceler. Bu ölçüme genellikle ek bellek karmaşıklığı veya yardımcı alan karmaşıklığı denir. Orijinal girdi çoğu analizde zaten mevcut kabul edilir; bu nedenle kendisi ek bellek olarak sayılmaz. Ancak girdinin kopyasını oluşturursan, bu kopya analizde hesaba katılır.

Örneğin aşağıdaki döngü, listenin elemanlarını toplarken yalnızca birkaç değişken kullanır:

def toplam(liste):
    sonuc = 0

    for sayi in liste:
        sonuc += sayi

    return sonuc

Döngü listedeki her elemanı bir kez ziyaret ettiği için zaman maliyeti n elemanlı bir listede doğrudan artar. Buna karşılık sonuc ve sayi gibi değişkenlerin sayısı, listenin uzunluğu arttıkça artmaz. Bu nedenle ek bellek kullanımı sabittir.

Beklenen sonuç:
Zaman karmaşıklığı: O(n)
Ek bellek karmaşıklığı: O(1)

Şimdi aynı işlemi yeni bir liste oluşturarak yapalım:

def pozitifleri_ayir(liste):
    pozitifler = []

    for sayi in liste:
        if sayi > 0:
            pozitifler.append(sayi)

    return pozitifler

Bu çözümde döngü yine tüm girdiyi dolaşır. Fakat pozitif elemanlar için yeni bir liste oluşturulur. En kötü durumda listedeki n elemanın tamamı pozitif olabilir. Böyle bir durumda pozitifler listesi de n eleman içerir.

Beklenen sonuç:
Zaman karmaşıklığı: O(n)
Ek bellek karmaşıklığı: O(n)

Buradaki önemli ayrım şudur: Girdi listesinin kendisi ek bellek değildir; algoritmanın oluşturduğu pozitifler listesi ek bellektir. Sonuç listesindeki elemanların sayısı girdinin uzunluğuyla birlikte büyüdüğü için bellek karmaşıklığı O(n) olur.

Listeyi değiştirmek ile listeyi kopyalamak aynı şey değildir

Bir listenin mevcut yapısını değiştirmek ile yeni bir liste üretmek, bellek analizi açısından farklı sonuçlar doğurabilir. Örneğin:

def sifirlari_sil(liste):
    i = 0

    while i < len(liste):
        if liste[i] == 0:
            liste.pop(i)
        else:
            i += 1

    return liste

Bu örnekte fonksiyon, kendisine verilen liste üzerinde çalışır ve ayrıca elemanları saklamak için ikinci bir sonuç listesi oluşturmaz. Kullanılan değişkenlerin sayısı sabit olduğu için ek bellek, kullanılan işlemlerin ayrıntılarına bağlı özel durumlar göz ardı edildiğinde O(1) olarak ifade edilir. Zaman maliyeti ise kullanılan liste işlemlerine ve elemanların konumlarına göre değişebilir; bu nedenle bellek sonucunu zaman sonucundan ayrı değerlendirmek gerekir.

Buna karşılık aşağıdaki ifade yeni bir liste üretir:

def listeyi_kopyala(liste):
    kopya = liste[:]
    return kopya

liste[:] ifadesi, listedeki elemanları içeren yeni bir liste oluşturur. Girdi n elemanlıysa bu yeni yapının saklanması için n ile orantılı ek alan gerekir.

Beklenen sonuç:
Zaman karmaşıklığı: O(n)
Ek bellek karmaşıklığı: O(n)

Bu nedenle kodu okurken “kaç liste var?” sorusu tek başına yeterli değildir. Yeni listenin boyutunun girdiden bağımsız mı, yoksa n ile birlikte mi büyüdüğünü de kontrol etmelisin. Birkaç sabit boyutlu değişken kullanmak O(1) ek bellek anlamına gelirken, her elemanı yeni bir yapıda saklamak çoğu zaman O(n) ek bellek anlamına gelir.

Zaman ve bellek karmaşıklıklarının aynı olması zorunlu değildir. Örneğin bir listedeki en büyük değeri bulmak için listeyi tek kez dolaşabilirsin:

def en_buyuk(liste):
    en_buyuk_deger = liste[0]

    for sayi in liste:
        if sayi > en_buyuk_deger:
            en_buyuk_deger = sayi

    return en_buyuk_deger

Bu algoritma her elemanı inceleyebilir, fakat yalnızca mevcut en büyük değeri saklar.

Beklenen sonuç:
Zaman karmaşıklığı: O(n)
Ek bellek karmaşıklığı: O(1)

Aynı girdiyi başka bir listeye kopyalayıp işlem yapmak da zaman açısından yine O(n) olabilir; ancak kopya nedeniyle ek bellek O(n) olur. Bu fark, özellikle büyük verilerle çalışırken algoritma seçimini etkileyebilir.

Her kod parçasında uygulanabilecek beş aşamalı analiz kontrol listesi

Bir algoritmayı analiz ederken her defasında ezberlenmiş kalıplara başvurmak yerine aşağıdaki beş soruyu sırayla yanıtlayabilirsin. Bu yöntem, özellikle iç içe döngüler, liste kopyaları ve birden fazla işlem içeren kodlarda daha tutarlı sonuç verir.

Kontrol listesini kısa biçimde şöyle uygulayabilirsin:

1. Girdiyi ve n değerini tanımla.
2. Algoritmanın temel işlemini belirle.
3. Döngülerin ve çağrıların kaç kez tekrarlandığını hesapla.
4. Ardışık işlemleri topla, iç içe işlemleri çarp.
5. Uygun durumu seç, sonucu sadeleştir ve zaman ile ek belleği ayrı belirt.

Aynı problemde çözüm seçimi nasıl yapılır?

Bir değeri listede aradığını düşünelim. Veri sıralı değilse tek bir sorgu için doğrusal tarama çoğu zaman doğrudan bir çözümdür: Elemanları sırayla kontrol edersin ve eşleşmeyi bulduğunda durabilirsin. En kötü durumda zaman maliyeti O(n), ek bellek maliyeti ise O(1) olabilir.

Veri sıralıysa ve arama koşulları uygunsa aralık her adımda küçültülerek logaritmik bir yaklaşım kullanılabilir. Bu yöntemde arama alanı yarıya indirildiği için sorgu başına maliyet O(log n) düzeyine düşebilir. Ancak bu sonuca ulaşmak için verinin sıralı olması gibi bir ön koşul vardır.

Çok sayıda sorgu yapılacaksa yalnızca tek sorgunun maliyetine bakmak yeterli değildir. Önce veriyi sıralamanın veya bir yardımcı yapı oluşturmanın maliyeti ile daha sonraki sorgu başına maliyeti birlikte değerlendirilmelidir. Örneğin ön işlem O(n log n) sürse bile binlerce sorguda sorgu maliyetinin azalması toplam süreyi iyileştirebilir.

Bu çerçeve kesin bir “en iyi algoritma” iddiası taşımaz. Veri düzeni, sorgu sayısı, ek bellek sınırı ve erken çıkış olasılığı birlikte düşünülmelidir. Big-O bilgisi, tek başına karar veren bir kural değil; farklı seçeneklerin bedelini görünür hâle getiren bir analiz aracıdır. Kendi algoritmik düşünme seviyeni görmek istersen algoritmik düşünme bilgi testini çözerek hangi konularda daha fazla pratik yapabileceğini belirleyebilirsin.

Sık Sorulan Sorular

Big-O analizinde sabit katsayılar neden dikkate alınmaz?

Big-O, girdinin boyutu büyüdüğünde algoritmanın büyüme davranışını gösterir. 3n ile n aynı doğrusal büyüme sınıfındadır; bu nedenle sabit katsayılar sadeleştirilerek O(n) yazılır. Gerçek çalışma süresinde sabitlerin etkisi olabilir, ancak temel ölçeklenme karşılaştırmasında baskın olan büyüme derecesidir.

İki ardışık döngü her zaman O(n²) mi olur?

Hayır. İki döngü art arda çalışıyor ve her biri n kez dönüyorsa toplam maliyet O(n) + O(n) = O(n) olur. O(n²) sonucu genellikle bir döngünün diğerinin içinde bulunduğu ve iki tekrar sayısının çarpıldığı durumlarda ortaya çıkar.

Erken çıkış kullanan bir döngünün Big-O karmaşıklığı nasıl yazılır?

Analiz hangi durumu hedefliyorsa ona göre yazılır. Aranan eleman ilk sıradaysa en iyi durum O(1) olabilir. Eleman listenin sonunda bulunuyorsa veya hiç bulunmuyorsa en kötü durum genellikle O(n) olur. Genel değerlendirmelerde, aksi belirtilmedikçe en kötü durum özellikle önemlidir.

Zaman karmaşıklığı ile bellek karmaşıklığı arasındaki fark nedir?

Zaman karmaşıklığı, algoritmanın temel işlemleri kaç kez yaptığını; bellek karmaşıklığı ise çalışırken girdinin dışında ne kadar alan kullandığını ölçer. Bir algoritma listeyi yalnızca bir kez dolaşıp O(n) zamanda çalışabilir ve O(1) ek bellek kullanabilir. Yeni bir sonuç listesi oluşturursa zaman yine O(n) kalırken ek bellek O(n) olabilir.

Big-O analizinde amaç yalnızca bir gösterim yazmak değil, algoritmanın veri büyüdüğünde nasıl davranacağını önceden görebilmektir. Zamanı ve ek belleği birlikte değerlendirdiğinde daha bilinçli, ölçülebilir ve sürdürülebilir çözümler tasarlayabilirsin.