Özyinelemeli karmaşıklık: yineleme bağıntıları

10. haftada özyinelemeli metot yazdık. Şimdi soru şu: bu metotlar ne kadar hızlı? Döngüde tur sayısını sayıyorduk. Özyinelemede ise metodun süresi kendi süresine bağlıdır: factorial(n)’in süresi factorial(n - 1)’in süresi artı biraz iş. Bunu bir yineleme bağıntısı (recurrence relation) olarak yazar, sonra çözeriz. Sınavda iki adım istenir: koddan bağıntıyı çıkar, bağıntıdan Big-O’yu bul. Bu sayfadaki on bağıntıyı tanırsan soruların çoğunu ezbere çözersin.

Altın kurallar:

1. T(n) = (kaç çağrı) · T(her çağrının boyutu) + (çağrı dışında yapılan iş).
2. n − 1 ile küçülen özyineleme doğrusal derinliktedir; n / 2 ile küçülen logaritmik.
3. İki çağrı + n − 1 = üstel. İki çağrı + n / 2 = doğrusal ya da n log n.
4. Özyineleme ağacında: seviye sayısı × seviye başına iş.

Koddan bağıntıya

Üç soruyu sor: taban durumda ne kadar iş var? Kaç özyinelemeli çağrı var ve her biri hangi boyutla? Çağrıların dışında ne kadar iş var?

Sabit iş (c) Big-O’yu etkilemez; çoğu zaman 1 yazılır.

Yöntem 1: açılım (unrolling)

Bağıntıyı kendi içine birkaç kez yerleştir, deseni gör, taban duruma kadar götür.

$T(n) = T(n-1) + n$, $T(1) = 1$

T(n) = T(n-1) + n
     = T(n-2) + (n-1) + n
     = T(n-3) + (n-2) + (n-1) + n
     ...
     = T(1) + 2 + 3 + ... + n
     = 1 + 2 + ... + n = n(n+1)/2   → O(n²)

$T(n) = T(n/2) + 1$, $T(1) = 1$

T(n) = T(n/2) + 1
     = T(n/4) + 2
     = T(n/8) + 3
     ...
     = T(n/2^k) + k      n/2^k = 1 olduğunda k = log2 n
     = 1 + log2 n        → O(log n)

$T(n) = 2T(n-1) + 1$, $T(0) = 0$

T(n) = 2T(n-1) + 1
     = 4T(n-2) + 2 + 1
     = 8T(n-3) + 4 + 2 + 1
     ...
     = 2^n T(0) + (2^(n-1) + ... + 2 + 1)
     = 2^n - 1           → O(2^n)

Programın doğrudan hesapladığı değerler (n iki katına çıkarken oranlar parantezde):

T(n-1)+1: T(10)=10 T(1000)=1000 (x100.00) T(2000)=2000 (x2.00) T(4000)=4000 (x2.00)
T(n-1)+n: T(10)=55 T(1000)=500500 (x9100.00) T(2000)=2001000 (x4.00) T(4000)=8002000 (x4.00)
T(n/2)+1: T(16)=5 T(1024)=11 (x2.20) T(2048)=12 (x1.09) T(1048576)=21 (x1.75)
2T(n-1)+1: T(5)=31 T(10)=1023 (x33.00) T(20)=1048575 (x1025.00) T(21)=2097151 (x2.00)

Son satırda dikkat: n sadece 1 artınca (20 → 21) değer iki katına çıkıyor. Üstel büyüme bu.

Yöntem 2: özyineleme ağacı (recursion tree)

Her düğüm bir çağrının kendi işini gösterir; toplam süre bütün düğümlerin toplamıdır.

$T(n) = 2T(n/2) + n$

seviye 0:                 n                         toplam n
seviye 1:          n/2          n/2                 toplam n
seviye 2:      n/4    n/4    n/4    n/4             toplam n
   ...
seviye log n:  1  1  1  1  ...  1   (n yaprak)      toplam n

Seviye sayısı $\log_2 n + 1$, her seviyede n iş: $T(n) = n\log_2 n + n$. n = 8 için 8 · 3 + 8 = 32, n = 1024 için 11 264. Program aynısını buldu:

2T(n/2)+n: T(8)=32 T(1024)=11264 (x352.00) T(2048)=24576 (x2.18) T(4096)=53248 (x2.17)

$T(n) = T(n/2) + n$ ağacı tek dallıdır: n, n/2, n/4, … Toplam $n(1 + \frac12 + \frac14 + \dots) < 2n$. Kökteki iş baskın: O(n).

$T(n) = 2T(n/2) + 1$ ağacında seviye başına iş 1, 2, 4, …, n. Toplam $2n - 1$. Yapraklar baskın: O(n).

İPUCU · Ağaçta kim baskın? Seviye başına iş aşağı doğru azalıyorsa kök baskındır (cevap kökteki iş). Sabitse seviye sayısıyla çarp (log n çarpanı). Artıyorsa yapraklar baskındır (cevap yaprak sayısı). Master teoremi bunun formül halidir.

Yöntem 3: master teoremi

$T(n) = a\,T(n/b) + n^d$ biçimindeki bağıntılar için ($a \ge 1$, $b > 1$). $k = \log_b a$ hesapla ve d ile karşılaştır:

Programla kontrol (n iki katına çıkınca beklenen oran: n için x2, n² için x4, n³ için x8):

4T(n/2)+n: T(1024)=2096128 T(2048)=8386560 (x4.00) T(4096)=33550336 (x4.00)
T(n/2)+n: T(1024)=2047 T(2048)=4095 (x2.00) T(4096)=8191 (x2.00)
2T(n/2)+1: T(1024)=2047 T(2048)=4095 (x2.00) T(4096)=8191 (x2.00)
8T(n/2)+n^2: T(256)=33488896 T(512)=268173312 (x8.01) T(1024)=2146435072 (x8.00)
2T(n/2)+n^2: T(1024)=2096128 T(2048)=8386560 (x4.00) T(4096)=33550336 (x4.00)

TUZAK · Master teoremi n − 1’e uygulanmaz. $T(n) = T(n-1) + n$ ya da $2T(n-1) + 1$ biçiminde bölme yok, çıkarma var. Bunları açılımla çöz.

Gerçek kodda sayım

Bağıntılar soyut kalmasın diye gerçek özyinelemeli kodlarda işlem saydık:

static void halfLoop(int n) {           // T(n) = T(n/2) + n
    if (n <= 1) return;
    for (int i = 0; i < n; i++) ops++;
    halfLoop(n / 2);
}

static void twoCalls(int n) {           // T(n) = 2T(n-1) + 1
    ops++;
    if (n == 0) return;
    twoCalls(n - 1);
    twoCalls(n - 1);
}

static void splitLoop(int lo, int hi) { // T(n) = 2T(n/2) + n
    if (hi - lo < 1) return;
    for (int i = lo; i <= hi; i++) ops++;
    int mid = (lo + hi) / 2;
    splitLoop(lo, mid);
    splitLoop(mid + 1, hi);
}

halfLoop n=1024 ops=2046  halfLoop n=2048 ops=4094  halfLoop n=4096 ops=8190  
bsearch(miss) n=1024 calls=11  bsearch(miss) n=2048 calls=12  bsearch(miss) n=1048576 calls=21  
twoCalls n=3 calls=15  twoCalls n=10 calls=2047  twoCalls n=11 calls=4095  twoCalls n=12 calls=8191  
splitLoop n=1024 ops=10240  splitLoop n=2048 ops=22528  splitLoop n=4096 ops=49152  
loopThenOne n=10 ops=55  loopThenOne n=1000 ops=500500  loopThenOne n=2000 ops=2001000  

splitLoop için 1024 · 10 = 10 240: tam olarak n log₂ n. loopThenOne (n’lik döngü + f(n − 1)) için n(n+1)/2.

Bellek karmaşıklığı

Özyinelemenin gizli bir maliyeti var: her açık çağrı bir yığın çerçevesi tutar. Ek bellek, en derin çağrı zincirinin uzunluğu kadardır.

Naif fib’de çağrı sayısı üstel ama aynı anda açık olan çağrı sayısı en fazla n’dir: bir dal bitmeden diğerine geçilmez.

Sık yapılan hatalar

static void f(int n) {
    if (n == 0) return;
    f(n - 1);
    f(n - 1);
}

static void h(int n) {
    if (n <= 1) return;
    for (int i = 0; i < n; i++)
        count++;
    h(n / 2);
}

seviye 0:            n                      = n
seviye 1:       n/2     n/2                 = n
seviye 2:    n/4 n/4  n/4 n/4               = n
...
seviye k:  2^k parça, her biri n/2^k        = n
son seviye: n tane T(1)                     = n