For Döngüsünün Zaman Karmaşıklığı Nasıl Bulunur? Adım Adım Analiz

For döngüsünün zaman karmaşıklığını bulmak için kodu iki soruya ayırırsın: döngü kaç tur atıyor ve her turda yapılan iş girdiyle büyüyor mu? Tur sayısı ile turdaki işin maliyetini çarparsın, çıkan ifadeyi sabit çarpanları atarak sadeleştirirsin. İç içe döngülerde iç döngünün tur sayısı dış döngüdeki değişkene bağlıysa toplam maliyet de buna göre değişir. Düşünme sırasının özeti şudur: "Önce döngünün kaç tur attığını, sonra her turda yapılan işin değişip değişmediğini belirle."

Önce tur sayısı, sonra turdaki iş: temel düşünme sırası

Toplam maliyeti tur sayısı x turdaki iş mantığıyla kurarsın. Döngü n tur atıyor ve her turda tek bir toplama yapılıyorsa toplam iş yaklaşık n x 1 olur. Sonra sabit çarpanları ve küçük terimleri atıp sonucu O gösteriminde yazarsın. O gösterimini burada yeniden tanımlamayacağım; kısaca girdi büyüdükçe işin büyüme biçimini anlatır. Ölçtüğün saniye değil, saydığın adım sayısıdır. Aynı karmaşıklığa sahip iki kod, gerçek çalışma süresinde birbirinden farklı olabilir.

Bu bir ilkedir, her koda otomatik uygulanan tek bir formül değildir. Tur sayısı bazen n, bazen n/2, bazen çok daha azdır. Turdaki iş de bazen sabittir, bazen dış döngüdeki değişkene bağlıdır. Bu yüzden her kodu ayrıca okuyup iki soruyu baştan sormak gerekir.

Aşağıdaki bölümlerde beş durumu bu sırayla inceleyeceğiz: sabit artışlı tek döngü, değişkeni ikiye katlayan döngü, iç içe döngü, sabit tur sayılı iç döngü ve koşulla erken biten döngü.

Sabit artışlı tek döngü ve değişkeni ikiye katlayan döngü

İlk örnek en yalın hâliyle bir toplama döngüsü:

toplam = 0
for i in range(n):
    toplam += i

Tur sayısı n, turdaki iş tek bir toplama olduğu için sabit. Toplam maliyet n x 1 olur ve sonuç O(n) çıkar.

Adımı değiştirelim:

toplam = 0
for i in range(0, n, 2):
    toplam += i

Adım sabit olsa da tur sayısı n değil, yaklaşık n/2'dir. Turdaki iş yine sabittir, dolayısıyla maliyet yaklaşık n/2 olur. O gösteriminde sabit çarpan düştüğü için sonuç yine O(n) kalır. Adımı 2 yerine 5 yapsan da aynı sonuca ulaşırsın: n'e bağlı doğrusal büyüme değişmez.

Üçüncü örnekte değişken her turda iki katına çıkıyor. Python'un for range yapısı değeri ikiye katlayamadığı için aynı düşünme sırasını while ile uyguluyoruz:

n = 8
i = 1
tur = 0
while i < n:
    i *= 2
    tur += 1
print(tur)

Beklenen çıktı: 3. Turlar başlarken i sırasıyla 1, 2 ve 4 değerini alır; i 8 olunca koşul bozulur ve döngü biter. Turdaki iş sabittir, yani her turda tek bir çarpma ve tek bir sayaç artışı yapılır.

Tur sayısına gelince: i her turda iki katına çıktığı için n değerine log2(n) mertebesinde turda ulaşır. n = 8 için log2(8) = 3 olduğundan sayaç 3 gösterir. n = 16 yaptığında tur sayısı yalnızca 4'e çıkar; girdi iki katına çıkarken tur sayısı bir artar. Sonuç O(log n) olur.

İç içe döngü ve sabit tur sayılı iç döngü aynı sonucu vermez

İç içe iki for görünce otomatik olarak "n kare" demek kısayol gibi durur, ama güvenilir değildir. Karar veren şey iç döngünün kaç tur attığıdır. Aşağıdaki iki kodun görünüşü benzer, sonuçları farklıdır.

n = 1000
sayac = 0
for i in range(n):
    for j in range(n):
        sayac += 1
print(sayac)

Dış döngü n tur atar. İç döngü her turda yine n tur atar. Toplam tekrar n x n olur ve çıktı 1000000 çıkar. Karmaşıklık O(n^2) olur.

n = 1000
sayac = 0
for i in range(n):
    for j in range(5):
        sayac += 1
print(sayac)

Dış döngü yine n tur atar, ama iç döngü her turda sabit 5 tur atar. Toplam tekrar 5n olur ve çıktı 5000 çıkar. Sabit çarpan karmaşıklığı değiştirmez, sonuç O(n) olur.

Aradaki fark tek bir soruyla anlaşılır: iç döngünün tur sayısı n'ye bağlı mı? İlkinde bağlıdır, ikincisinde bağlı değildir.

İç döngü dış döngüye bağlıysa

İç döngü range(i) olursa her turdaki tur sayısı değişir. Dış döngü i = 0, 1, 2, ..., n-1 değerlerini alır. Toplam tur sayısı 0 + 1 + 2 + ... + (n-1) = n(n-1)/2 olur. Bu ifade açıldığında en büyük terim n^2/2 olduğundan sonuç yine O(n^2) çıkar.

Üç örnekte de tur sayıları tek tek yazıldı. "İç içe döngü her zaman n^2'dir" ya da "iç içe döngü her zaman yavaştır" gibi kestirmelere güvenme. Her seviyenin kaç tur attığını yaz, sonra çarp ya da topla.

Koşulla erken biten döngüde en iyi ve en kötü durum

Döngü break ile erken çıkabiliyorsa tur sayısı girdiye göre değişir. Doğrusal arama bunun klasik örneğidir. Aşağıdaki kod karşılaştırma sayısını da sayıyor:

def ara(liste, hedef):
    karsilastirma = 0
    for eleman in liste:
        karsilastirma += 1
        if eleman == hedef:
            break
    return karsilastirma

sayilar = [4, 8, 15, 16, 23, 42]
print(ara(sayilar, 4))
print(ara(sayilar, 99))

Beklenen çıktı:

1
6

Aranan değer ilk elemansa döngü 1 turda biter. Bu en iyi durumdur ve karmaşıklık O(1) olur. Değer en sondaysa ya da listede hiç yoksa döngü listenin tamamını gezer, yani n tur atar. Bu en kötü durumdur ve karmaşıklık O(n) olur.

Bu yüzden karmaşıklık sorusu "hangi girdi için?" sorusuyla birlikte sorulmalıdır. Aynı kod bir girdide O(1), başka bir girdide O(n) olabilir. Sınavda hangisinin istendiğini soru metninden oku. Soruda durum belirtilmişse onu kullan. Belirtilmemişse en kötü durumun mu, en iyi durumun mu istendiğini sorunun ifadesinden çıkar; emin olmadığın yerde iki durumu da yazman en güvenli yoldur.

Burada ortalama durum ayrıntısına girmiyoruz. Önemli olan, break görünce döngünün tam tur atacağını varsaymamak ve girdiye göre iki ucu ayrı ayrı yazmaktır.

Üç Örnekte Aynı Kontrol Listesi: Tur Say, İşi Tart, Birleştir, Sadeleştir

Başta verdiğimiz düşünme sırasını dört adımlık bir kontrol listesine çevirebilirsin. Aşağıdaki sıra bir yöntem önerisidir; her yeni kodda adımları tek tek sorgulaman gerekir.

1. Tur sayısını bul. Döngü değişkeni nereden başlıyor, nasıl değişiyor, ne zaman duruyor?
2. Turdaki işin sabit olup olmadığına bak. Gövde her turda aynı miktarda iş mi yapıyor, yoksa iş n'ye göre mi büyüyor?
3. Döngüleri birleştir. İç içe döngülerde tur sayılarını çarp (ya da iç döngünün tur sayısı dış değişkene bağlıysa turlara göre topla). Ardışık döngülerde sonuçları topla.
4. Sonucu sadeleştir. Sabit çarpanları ve büyümede baskın olmayan terimleri at.

Listeyi daha önce incelediğimiz üç örneğe sırayla uygulayalım:

• Tek döngü (for i in range(n), gövdede tek toplama): n tur × her turda sabit iş = n × 1 = n. Sonuç O(n).
• İç içe döngü (iki döngü de range(n)): dış döngü n tur, her turda iç döngü n tur. n × n = n^2. Sonuç O(n^2).
• İkiye katlayan döngü (while i < n ve gövdede i *= 2): değişken her turda ikiye katlandığı için tur sayısı yaklaşık log n, turdaki iş sabit. log n × 1 = log n. Sonuç O(log n).

Üçüncü adımın ardışık durumunu küçük bir kodla görelim:

def iki_dongu(n):
    for i in range(n):
        print(i)
    for j in range(n):
        print(j)

iki_dongu(3)

Çıktı, 0 1 2 0 1 2 şeklinde alt alta altı satırdır. Birinci döngü n, ikincisi n tur atar; ardışık oldukları için toplanır: n + n = 2n. Dördüncü adımda sabit çarpan atılır ve O(2n) ifadesi O(n) olur. Bu adımda yalnız büyüme biçimi tutulur; O gösteriminin genel tanımı için önceki bölümlere dönebilirsin.

Listeyi ezberlemek yerine farklı kodlarda uygulamak daha öğreticidir. Kod okuma pratiğini dilden bağımsız sorularla sınamak istersen Algoritmik Düşünme Testi iyi bir deneme alanı olabilir.

Sık Yapılan Hatalar: Sabit mi Değişken mi ve Sabit Çarpanlar

Kod okurken en çok şu dört noktada yanlış sonuca varılır.

Hata 1: İç döngünün tur sayısını yanlış okumak

İç döngünün neye bağlı olduğuna dikkat et:

• range(5): tur sayısı sabit. İç döngü toplam işi yalnızca 5 ile çarpar, sonuç dış döngüye göre O(n).
• range(n): tur sayısı n'ye bağlı. Dış döngüyle çarpılır, sonuç O(n^2).
• range(i): tur sayısı dış değişkene bağlı. Turlar 0, 1, 2, ... n-1 diye gider; toplamları yaklaşık n^2/2 eder, sonuç yine O(n^2).

Hata 2: Sabit çarpanı yanlış yorumlamak

O(2n) ve O(n/2) için O(n) yazılır. Ancak bu, iki kodun gerçek çalışma süresinin aynı olduğu anlamına gelmez. Karmaşıklık, girdi büyüdükçe işin nasıl büyüdüğünü anlatır; saniye cinsinden süre garantisi vermez.

Hata 3: Ardışık ve iç içe yapıyı karıştırmak

Alt alta duran döngüler toplanır, biri diğerinin içinde duruyorsa çarpılır. İki ardışık n turluk döngüye O(n^2) demek ya da iç içe iki döngüye O(2n) demek sık görülen bir karışıklıktır. Girinti hizasına bakmak çoğu zaman yeterli ipucunu verir.

Hata 4: Gövdedeki tek satırı sabit maliyetli sanmak

Tek satırlık bir işlem her zaman sabit maliyetli değildir. Listede in sorgusu ya da dilimleme (liste[1:]) varsa turdaki iş artık listenin uzunluğuna göre büyür. Bu durumda kontrol listesinin ikinci adımına dönüp işi yeniden tartman gerekir.

def ortaklari_bul(a, b):
    ortak = []
    for x in a:
        if x in b:
            ortak.append(x)
    return ortak

print(ortaklari_bul([1, 2, 3], [2, 3, 4]))

Çıktı [2, 3] olur. a ve b listelerinin ikisi de n elemanlıysa dış döngü n tur atar. x in b ise listeyi baştan taramak zorunda kalabilir ve en kötü durumda n karşılaştırma yapar. n × n işlem gerektiği için bu kod O(n^2) olabilir. Gövde tek satır olsa bile işin sabit olmadığına dikkat et.

Bu tür kalıpları farklı seviyelerde denemek için ücretsiz bilgi testleri merkezindeki testlerden yararlanabilirsin; kod okuma alışkanlığını ölçmenin pratik bir yoludur.

Sık Sorulan Sorular

Döngünün içinde 'in' operatörü ya da başka bir liste işlemi kullanılırsa karmaşıklık değişir mi?

Evet, değişebilir. Listede in sorgusu, dilimleme ve kopyalama gibi işlemler listenin uzunluğuna göre büyüyen iş yapar. Böyle bir işlem n turluk bir döngünün gövdesindeyse toplam iş n × n olabilir. Gövdedeki her işlemin maliyetini ayrı ayrı değerlendirmek gerekir.

While döngüsünün zaman karmaşıklığı da aynı düşünme sırasıyla mı bulunur?

Evet, sıra aynıdır: önce kaç tur attığını, sonra turdaki işin sabit olup olmadığını belirlersin. While'da tur sayısını bulmak için döngü değişkeninin başlangıç değerine, her turdaki değişimine (toplama mı, çarpma mı) ve durma koşuluna bakarsın. i += 1 ile ilerleyen döngü yaklaşık n tur, i *= 2 ile ilerleyen döngü yaklaşık log n tur atar.

Zaman karmaşıklığı ile gerçek çalışma süresi aynı şey midir?

Hayır. Zaman karmaşıklığı, girdi büyüdükçe işlem sayısının hangi biçimde arttığını anlatır. Gerçek süre ise bilgisayara, programlama diline, yorumlayıcıya ve işlemlerin ayrıntısına bağlıdır. Sabit çarpanlar O gösteriminde atılsa da süreyi etkileyebilir; bu yüzden karmaşıklık süre için bir garanti değil, büyüme biçimi için bir ölçüdür.

Bir döngüyle karşılaştığında önce tur sayısını, ardından turdaki işi sorgulama alışkanlığı, kodu çalıştırmadan da fikir yürütmeni sağlar. Kontrol listesini farklı kodlar üzerinde tekrar tekrar uyguladıkça adımlar kendiliğinden oturur.