---
title: 'Zaman ve Alan Ödünleşimi'
source: 'https://academia.sh/tr/kurslar/algoritmalar/zaman-ve-alan-odunlesimi'
course: Algoritmalar
language: tr
updated: '2026-08-17T18:07:35+00:00'
license: 'CC BY-SA 4.0'
---

# Zaman ve Alan Ödünleşimi

Alan karmaşıklığı, yerinde çalışma, özyineleme yığıtının maliyeti, anımsama ve önhesaplama kalıpları; ödünleşimin sınırları.

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.

```python
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 nokta**daki ç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.

```python
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ı?

```python
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.