---
title: 'Karmaşıklık Hesaplama Yöntemi'
source: 'https://academia.sh/tr/kurslar/algoritmalar/karmasiklik-hesaplama'
course: Algoritmalar
language: tr
updated: '2026-08-17T18:07:33+00:00'
license: 'CC BY-SA 4.0'
---

# Karmaşıklık Hesaplama Yöntemi

Döngü ve koşul kurallarıyla maliyet sayımı, özyineleme bağıntıları, ana teorem ve amortize çözümleme.

Sınıflar tanındı; sıra bir kod parçasına bakıp hangi sınıfa ait olduğunu belirlemeye
geldi. Bu ders, hesabın kurallarını verir. Kurallar azdır ve birleştirilerek uygulanır.

## Temel Kurallar

**Ardışık bölümler toplanır.** İki bölüm arka arkaya çalışıyorsa maliyetleri toplanır ve
büyük olan baskın kalır: $O(n) + O(n^2) = O(n^2)$.

**Döngü, gövde maliyeti çarpı tur sayısıdır.** Gövdesi sabit olan ve $n$ kez dönen döngü
$O(n)$'dir.

**İç içe döngülerde maliyetler çarpılır.** Her ikisi de $n$ kez dönen iki döngü
$O(n^2)$'dir.

**Koşullu yapılarda en kötü dal alınır.** Güvence en kötü durum üzerinden verilir.

**Sabit sayıda tekrar sabittir.** Kaç kez döndüğü $n$'e bağlı olmayan döngü $O(1)$'dir.

```python
def sayim_ornekleri(n: int) -> dict[str, int]:
    sayac = {"tekli": 0, "icice": 0, "ucgen": 0, "yarilanan": 0}

    for i in range(n):                       # O(n)
        sayac["tekli"] += 1

    for i in range(n):                       # O(n²)
        for j in range(n):
            sayac["icice"] += 1

    for i in range(n):                       # O(n²) — üçgensel ama yine karesel
        for j in range(i):
            sayac["ucgen"] += 1

    i = 1
    while i < n:                             # O(log n)
        sayac["yarilanan"] += 1
        i *= 2

    return sayac


print(sayim_ornekleri(8))
# {'tekli': 8, 'icice': 64, 'ucgen': 28, 'yarilanan': 3}
print(sayim_ornekleri(16))
# {'tekli': 16, 'icice': 256, 'ucgen': 120, 'yarilanan': 4}
```

Girdi ikiye katlandığında sayılar sınıfların beklediği gibi değişir: tekli iki katına,
iç içe dört katına çıkar; yarılanan döngü ise yalnızca bir artar.

Üçgensel döngü dikkat ister. Toplam tur sayısı $n(n-1)/2$'dir; sabit çarpan elendiğinde
$O(n^2)$ kalır. "Yarısı kadar dönüyor" gözlemi sınıfı değiştirmez — yalnızca sabiti
değiştirir.

## Döngü Sınırının Değişimi

Tur sayısı, döngü değişkeninin nasıl ilerlediğine bağlıdır:

| İlerleme | Tur sayısı | Sınıf |
|---|---|---|
| `i += 1` | $n$ | $O(n)$ |
| `i += k` | $n/k$ | $O(n)$ |
| `i *= 2` | $\log_2 n$ | $O(\log n)$ |
| `i = i * i` | $\log \log n$ | $O(\log \log n)$ |
| `i -= 1` (n'den) | $n$ | $O(n)$ |

İkinci satır önemlidir: sabit adımla ilerlemek sınıfı değiştirmez. Çarpımsal ilerleme ise
değiştirir; ikili aramanın logaritmik olmasının kaynağı budur.

## Özyineleme Bağıntıları

Özyinelemeli bir algoritmanın maliyeti, kendi cinsinden yazılır. Bu ifadeye **özyineleme
bağıntısı** denir.

Üç yaygın kalıp:

$$
T(n) = T(n-1) + O(1) \implies T(n) = O(n)
$$

Her adımda problem bir eleman küçülür ve sabit iş yapılır; toplam $n$ adım. Faktöriyel
hesabı bu kalıptadır.

$$
T(n) = T(n/2) + O(1) \implies T(n) = O(\log n)
$$

Her adımda problem yarılanır ve sabit iş yapılır; yarılama sayısı $\log_2 n$'dir. İkili
arama bu kalıptadır.

$$
T(n) = 2\,T(n/2) + O(n) \implies T(n) = O(n \log n)
$$

Problem iki yarıya bölünür, her düzeyde tüm elemanlar işlenir. Birleştirmeli sıralama bu
kalıptadır ve bir sonraki konunun ana örneğidir.

## Özyineleme Ağacı

Bağıntıyı çözmenin sezgisel yolu, çağrıları bir ağaç olarak çizip düzey düzey maliyet
toplamaktır.

$T(n) = 2T(n/2) + n$ bağıntısında:

| Düzey | Çağrı sayısı | Çağrı başına iş | Düzey toplamı |
|---|---|---|---|
| 0 | 1 | $n$ | $n$ |
| 1 | 2 | $n/2$ | $n$ |
| 2 | 4 | $n/4$ | $n$ |
| $k$ | $2^k$ | $n/2^k$ | $n$ |

Her düzeyin toplamı $n$'dir ve düzey sayısı $\log_2 n$'dir; toplam $n \log n$ çıkar.

Aynı yöntem $T(n) = 2T(n/2) + O(1)$ için farklı sonuç verir: düzey toplamları $1, 2, 4,
\dots, n$ biçiminde büyür ve toplam $O(n)$ olur. Yaprak sayısı baskın hâle gelir.

## Ana Teorem

Böl ve yönet bağıntılarının çoğu tek bir kalıba uyar:

$$
T(n) = a\,T(n/b) + f(n)
$$

Burada $a$ alt problem sayısı, $b$ küçülme çarpanı, $f(n)$ bölme ve birleştirme
maliyetidir. Sonuç, $f(n)$ ile $n^{\log_b a}$ karşılaştırılarak belirlenir:

- $f(n)$ küçükse: $T(n) = \Theta(n^{\log_b a})$ — yapraklar baskın.
- İkisi aynı mertebedeyse: $T(n) = \Theta(n^{\log_b a} \log n)$ — tüm düzeyler eşit.
- $f(n)$ büyükse: $T(n) = \Theta(f(n))$ — kök baskın.

Birleştirmeli sıralamada $a = 2$, $b = 2$, $f(n) = n$'dir; $n^{\log_2 2} = n$ olduğundan
ikinci durum geçerlidir ve sonuç $\Theta(n \log n)$ çıkar.

Teoremin tam ifadesi ek koşullar içerir ve her bağıntı bu kalıba uymaz; uymayanlar için
ağaç yöntemi veya doğrudan çözüm kullanılır.

## Amortize Çözümleme

Bazı işlemlerin maliyeti tek tek bakıldığında yanıltıcıdır. Veri Yapıları kursundaki
dinamik dizi buna örnekti: sona ekleme çoğunlukla sabit, ara sıra doğrusaldır.

**Toplam maliyet yöntemi**, $m$ işlemin toplam maliyetini hesaplar ve $m$'e böler.
Dinamik dizide $n$ ekleme için toplam kopyalama $n$'den azdı; ekleme başına amortize
maliyet sabittir.

```python
def toplam_kopyalama(n: int) -> int:
    """n eklemede yapılan toplam kopyalama sayısı (kapasite ikiye katlanarak)."""
    kapasite, uzunluk, kopyalama = 1, 0, 0
    for _ in range(n):
        if uzunluk == kapasite:
            kopyalama += uzunluk           # tüm elemanlar yeni bloğa taşınır
            kapasite *= 2
        uzunluk += 1
    return kopyalama


for n in (16, 1000, 100_000):
    print(n, toplam_kopyalama(n), f"{toplam_kopyalama(n)/n:.2f}")
# 16 15 0.94
# 1000 1023 1.02
# 100000 131071 1.31
```

Ekleme başına ortalama kopyalama sayısı, girdi büyüdükçe küçük bir sabitin çevresinde
kalır; doğrusal büyümez. Amortize sabit maliyet ifadesi tam olarak bunu söyler.

İki yöntem daha vardır. **Muhasebe yöntemi**, her ucuz işleme ileride yapılacak pahalı iş
için bir pay yükler; **potansiyel yöntemi**, yapının "biriken enerjisini" bir fonksiyonla
ifade eder. Üçü de aynı sonucu verir; seçim, ispatın hangisiyle daha kısa yazıldığına
bağlıdır.

## Uygulama Sırası

Bir kod parçasının maliyetini bulmak için izlenen sıra:

1. **Girdi büyüklüğünü tanımla.** $n$ neyi sayıyor?
2. **En iç işlemi bul.** Hangi işlem en sık tekrarlanıyor?
3. **Tur sayılarını çarp.** İç içe yapılarda dıştan içe doğru.
4. **Ardışık bölümleri topla**, büyük terimi al.
5. **Özyineleme varsa bağıntıyı yaz** ve çöz.
6. **Amortize davranış varsa** toplam maliyeti işlem sayısına böl.

Adımlar sırayla uygulandığında, sezgiye başvurmadan sonuç elde edilir.

## Özet

- Ardışık bölümler toplanır, iç içe döngülerde maliyetler çarpılır, koşullarda en kötü
  dal alınır.
- Döngü değişkeninin çarpımsal ilerlemesi tur sayısını logaritmik yapar; sabit adımla
  ilerleme sınıfı değiştirmez.
- Özyinelemeli maliyet bir bağıntıyla yazılır; üç yaygın kalıp doğrusal, logaritmik ve
  doğrusal-logaritmik sonuç verir.
- Özyineleme ağacı, düzey düzey maliyet toplayarak bağıntıyı çözer.
- Ana teorem, böl ve yönet bağıntılarını üç durumda sınıflandırır.
- Amortize çözümleme, bir işlem dizisinin toplam maliyetini işlem sayısına böler.

## Sonraki Adım

Buraya kadar yalnızca zaman ele alındı. Oysa algoritmalar bellek de kullanır ve ikisi
sıklıkla birbirinin yerine geçer: daha çok bellek kullanarak daha hızlı, daha az bellek
kullanarak daha yavaş çalışmak mümkündür. Sonraki ders bu ödünleşimi ve tipik kalıplarını
ele alacak.