Zaman ve Alan Ödünleşimi

Buraya kadar tek bir kaynak sayıldı: işlem sayısı. Oysa algoritmalar bellek de tüketir ve iki kaynak sıklıkla birbirinin yerine geçer. Daha çok bellek kullanarak daha az işlem yapmak, ya da tersi, çoğu problemde mümkündür.

Bu ders, ikinci ekseni tanımlar ve aralarındaki değiş tokuşun kalıplarını gösterir.

Alan Karmaşıklığı

Alan karmaşıklığı, girdi büyüklüğüne göre kullanılan bellek miktarının büyüme hızıdır. Zaman karmaşıklığıyla aynı gösterimler kullanılır.

İki ayrı büyüklük vardır ve karıştırılmaları yaygın bir hatadır:

Toplam alan, girdi dahil kullanılan tüm bellektir. $n$ elemanlık bir dizi üzerinde çalışan her algoritma en az $O(n)$ toplam alan kullanır.

Ek alan (auxiliary space), girdi dışında ayrılan bellektir. Karşılaştırmalarda anlamlı olan budur; çünkü girdiyi tutmak zaten zorunludur.

Ek alanı sabit olan algoritmalara yerinde (in-place) denir. Diziyi ters çeviren şu işlev yerindedir: kaç eleman olursa olsun üç değişkenden fazlasını kullanmaz.

def ters_cevir_yerinde(dizi: list[int]) -> None:
    """Diziyi yerinde ters çevirir. Ek alan: O(1)."""
    sol, sag = 0, len(dizi) - 1
    while sol < sag:
        dizi[sol], dizi[sag] = dizi[sag], dizi[sol]
        sol += 1
        sag -= 1


def ters_cevir_kopyali(dizi: list[int]) -> list[int]:
    """Yeni dizi üretir. Ek alan: O(n)."""
    return [dizi[i] for i in range(len(dizi) - 1, -1, -1)]


d = [1, 2, 3, 4, 5]
ters_cevir_yerinde(d)
print(d)                          # [5, 4, 3, 2, 1]
print(ters_cevir_kopyali([1, 2, 3, 4, 5]))    # [5, 4, 3, 2, 1]

İkisi de $O(n)$ zamanlıdır; ayrıldıkları eksen alandır. Seçim, çağıranın özgün diziye ihtiyacı olup olmamasına ve belleğin ne kadar kısıtlı olduğuna bağlıdır.

Özyineleme Yığıtı Alan Tüketir

Özyinelemeli bir çözümde açıkça dizi ayrılmasa bile bellek kullanılır: her bekleyen çağrı, Programlama Temelleri kursunda tanıtılan çağrı yığıtında bir çerçeve tutar.

Alan maliyeti, en derin noktadaki çağrı sayısıdır — toplam çağrı sayısı değil.

Yapı	En büyük derinlik	Ek alan
Doğrusal özyineleme ($n$ adım)	$n$	$O(n)$
İkiye bölen özyineleme	$\log n$	$O(\log n)$
Kuyruk özyinelemesi (döngüye çevrilmişse)	$1$	$O(1)$

Ayrım pratik sonuç doğurur: milyon elemanlık bir dizide doğrusal derinlikli bir özyineleme, çalışma zamanının yığıt sınırını aşar. Aynı algoritmanın döngülü yazımı sınıra takılmaz.

Klasik Ödünleşim Kalıpları

Belleği zamana çevirmenin birkaç yerleşik yolu vardır.

Anımsama (memoization). Hesaplanan sonuçlar saklanır, tekrar istendiğinde yeniden hesaplanmaz. Zaman düşer, alan artar.

Önhesaplama. Sonuçlar sorgu gelmeden önce bir tabloya yazılır. Sorgu maliyeti sabite iner, tablo alanı ödenir.

Dizinleme. Veri Yapıları kursundaki karma tablosu ve ağaçlar, ek yapı karşılığında arama maliyetini düşürür.

Sıkıştırma. Ters yön: alan azalır, kodlama-çözme işlemi zamanı artırır.

Anımsamanın etkisi, aynı hesabı iki kez yapan bir özyinelemede en açık görülür.

def fib_saf(n: int, sayac: list[int]) -> int:
    sayac[0] += 1
    if n < 2:
        return n
    return fib_saf(n - 1, sayac) + fib_saf(n - 2, sayac)


def fib_tablolu(n: int, sayac: list[int], tablo: dict[int, int]) -> int:
    sayac[0] += 1
    if n < 2:
        return n
    if n not in tablo:
        tablo[n] = fib_tablolu(n - 1, sayac, tablo) + fib_tablolu(n - 2, sayac, tablo)
    return tablo[n]


for n in (10, 20, 30):
    a, b = [0], [0]
    print(n, fib_saf(n, a), a[0], fib_tablolu(n, b, {}), b[0])

# 10 55 177 55 19
# 20 6765 21891 6765 39
# 30 832040 2692537 832040 59

Çağrı sayısı üstelden doğrusala iner: otuz için iki buçuk milyon çağrı yerine elli dokuz. Ödenen bedel, $n$ girdilik bir sözlüktür — yani $O(n)$ ek alan.

Aynı Problem, İki Denge Noktası

Ödünleşim, tek bir problem üzerinde iki çözüm yazılarak somutlaşır. Problem: bir dizide toplamı verilen hedefe eşit olan iki eleman var mı?

def iki_toplam_karma(dizi: list[int], hedef: int) -> tuple[int, int] | None:
    """Zaman O(n), ek alan O(n)."""
    gorulen: dict[int, int] = {}
    for i, deger in enumerate(dizi):
        if hedef - deger in gorulen:
            return gorulen[hedef - deger], i
        gorulen[deger] = i
    return None


def iki_toplam_iki_uc(dizi: list[int], hedef: int) -> tuple[int, int] | None:
    """Sıralı dizi üzerinde zaman O(n), ek alan O(1)."""
    sol, sag = 0, len(dizi) - 1
    while sol < sag:
        toplam = dizi[sol] + dizi[sag]
        if toplam == hedef:
            return sol, sag
        if toplam < hedef:
            sol += 1
        else:
            sag -= 1
    return None


print(iki_toplam_karma([8, 3, 11, 5, 2], 13))        # (0, 3)  — 8 + 5
print(iki_toplam_iki_uc([2, 3, 5, 8, 11], 13))       # (0, 4)
print(iki_toplam_karma([8, 3, 11, 5, 2], 100))       # None

Birinci çözüm sırasız dizide tek geçişte çalışır ama $n$ girdilik bir sözlük tutar. İkincisi hiç ek alan kullanmaz, karşılığında dizinin sıralı olmasını ister; sıralama maliyeti eklenirse toplam $O(n \log n)$ olur.

Seçim, “hangisi daha iyi” sorusunun yanıtı değildir; hangi kaynağın kısıtlı olduğuna bağlıdır. Bellek boldu ve tek sorgu yapılacaksa birincisi; bellek darsa veya dizi zaten sıralıysa ikincisi.

Ödünleşim Her Zaman Geçerli Değil

İki uyarı, ödünleşimi mekanik bir kural saymayı engeller.

Daha az alan bazen daha hızlıdır. Bilgisayarlar Nasıl Çalışır kursundaki bellek hiyerarşisi nedeniyle, küçük ve bitişik bir yapı önbelleğe sığar ve dağınık büyük bir yapıdan hızlı çalışabilir. Alan azaltmak burada zamanı da azaltır.

Bazı iyileştirmeler her iki eksende de kazandırır. Karesel bir algoritmayı doğrusal-logaritmiğe indiren bir fikir, çoğu zaman ek alan da istemez. Ödünleşim, algoritma sabit tutulduğunda geçerlidir; daha iyi bir algoritma bulunduğunda değil.

Bu nedenle sıralama, önce algoritmanın kendisini iyileştirmeye bakmak, ödünleşime ancak sonra başvurmaktır.

Karar Ölçütü

Uygulamada seçim üç soruyla yapılır:

1. Hangi kaynak kısıtlı? Gömülü bir sistemde bellek, toplu işlemede zaman.
2. Sonuç kaç kez kullanılacak? Tek kullanımlık hesapta önhesaplama zarardır; çok sorguluda kendini öder.
3. Girdi ne kadar büyüyecek? Alan doğrusal artıyorsa, girdi belli bir noktadan sonra belleğe sığmaz ve çözüm geçersizleşir.

Üçüncü soru sıklıkla atlanır: zaman aşımı bir gecikmedir, bellek aşımı ise çalışmanın tamamen durmasıdır.

Özet

• Alan karmaşıklığı, bellek kullanımının girdiye göre büyüme hızıdır; toplam alan ile ek alan ayrı büyüklüklerdir.
• Ek alanı sabit olan algoritmalara yerinde denir.
• Özyineleme, en derin noktadaki çağrı sayısı kadar yığıt alanı tüketir.
• Anımsama, önhesaplama ve dizinleme belleği zamana çevirir; sıkıştırma ters yönde çalışır.
• Aynı problemin farklı denge noktalarındaki çözümleri, kısıtlı kaynağa göre seçilir.
• Ödünleşim algoritma sabitken geçerlidir; daha iyi bir algoritma her iki eksende de kazandırabilir.

Sonraki Adım

Çözümleme araçları tamamlandı: maliyet tanımlandı, gösterimle ifade edildi, hesaplandı ve iki eksene ayrıldı. Sonraki konu bu araçları ilk kez ciddi bir algoritma ailesine uygulayacak — arama ve sıralama. Aynı problemin yarım düzine çözümü, tam da bu ölçütlerle karşılaştırılacak.