Sınavdan önceki son okuma. Hocanın slaytları, Ödev 2 ve 31 Ekim dersinde söyledikleri; log tabanı yazılmamışsa 2.
left <= right), mid = left + (right - left) / 2. Sonuna karmaşıklığı bir satırla yaz.| $n$ | $\log n$ | $n\log n$ | $n^2$ | $2^n$ |
|---|---|---|---|---|
| 16 | 4 | 64 | 256 | 65 536 |
| 1024 | 10 | 10 240 | ≈10⁶ | ≈10³⁰⁸ |
| 10⁶ | ≈20 | ≈2·10⁷ | 10¹² | — |
10⁹ işlem/sn: $n=10^6$ için $n\log n$ ≈ 20 ms, $n^2$ ≈ 17 dakika. Fib(45) özyinelemeli 12.5 s, iteratif < 1 µs.
$O$ = üst sınır ($f\le c\,g$), $\Omega$ = alt sınır ($f\ge c\,g$), $\Theta$ = ikisi birden; hepsi "yeterince büyük $n\ge n_0$ için".
| En iyi | Ort. | En kötü | Bellek | Kararlı | |
|---|---|---|---|---|---|
| Bubble | $n$ | $n^2$ | $n^2$ | 1 | ✓ |
| Selection | $n^2$ | $n^2$ | $n^2$ | 1 | ✗ |
| Insertion | $n$ | $n^2$ | $n^2$ | 1 | ✓ |
| Merge | $n\log n$ | $n\log n$ | $n\log n$ | $n$ | ✓ |
| Quick | $n\log n$ | $n\log n$ | $n^2$ | $\log n$ | ✗ |
| Heap | $n\log n$ | $n\log n$ | $n\log n$ | 1 | ✗ |
| Counting | $n+k$ ($k$ = değer aralığı) | $k$ | ✓ | ||
| Linear search | 1 | $n$ | $n$ | 1 | |
| Binary search | 1 | $\log n$ | $\log n$ | 1 | sıralı dizi şart |
Kime ait (karmaşıklık): $\log n$ → binary search, dengeli BST arama; $n\log n$ → merge, heap, quick (ort.); $n^2$ → bubble, selection, insertion, quick (en kötü); $2^n$ → özyinelemeli Fibonacci.
Kime ait (mucit): Merge sort — John von Neumann (1945); Quick sort — Tony Hoare (1959–61); Heap sort — J. W. J. Williams (1964); Shell sort — Donald Shell (1959); Counting sort — Harold Seward (1954); Radix — Herman Hollerith (1887). Master teoremi — Bentley, Haken, Saxe (1980).
Quick en kötü: sıralı dizi + uç pivot → $T(n)=T(n-1)+n=\Theta(n^2)$. Çare: rastgele / ortanca pivot.
$T(n)=aT(n/b)+f(n)$; $a\ge1$ sabit (aktif alt problem sayısı), $b>1$ sabit (kaça bölüyorum), $f(n)$ asimptotik pozitif (birleştirme maliyeti). Hızlı karar, $f(n)=n^d\log^k n$ için $d$'yi $\log_b a$ ile kıyasla:
Uygulanamaz: $a$ sabit değil ($2^nT(n/2)$), $a<1$ ($0.5T(n/2)$), $f$ negatif, fark yalnızca log ($2T(n/2)+n/\log n$, $k<0$), düzenlilik bozuk ($n(2-\cos n)$), $T(n-1)$ biçimi (Fibonacci: "Master teorem ile çözülemez!!!").
$\epsilon$ nasıl gösterilir (hocanın yolu): önce $\epsilon=0$ gibi düşün, sonra "yeterince küçük bir $\epsilon$ seçebilir miyim?" — $8T(n/2)+n^2$: $n^{3-\epsilon}$, $\epsilon=0.01$ → $n^{2.99}\ge n^2$ ✓.
| Yineleme | Sonuç | Nerede |
|---|---|---|
| $T(n/2)+1$ | $\log n$ (D2) | binary search |
| $2T(n/2)+1$ | $n$ (D1) | böl-fethet max, toplam |
| $2T(n/2)+n$ | $n\log n$ (D2) | merge sort, quick (iyi) |
| $T(n/2)+n$ | $n$ (D3) | |
| $3T(n/2)+n$ | $n^{\log_2 3}\approx n^{1.585}$ (D1) | Karatsuba |
| $4T(n/2)+n$ | $n^2$ (D1) | okul çarpması |
| $7T(n/2)+n^2$ | $n^{\log_2 7}\approx n^{2.807}$ (D1) | Strassen |
| $8T(n/2)+n^2$ | $n^3$ (D1) | slayt örneği |
| $3T(n/4)+n\log n$ | $n\log n$ (D3, $c=\tfrac34$) | slayt örneği |
| $T(n-1)+n$ | $n^2$ (Master yok) | quick (en kötü) |
| $T(n-1)+1$ | $n$ (Master yok) | doğrusal özyineleme |
| $T(n-1)+T(n-2)+1$ | $\Theta(\varphi^n)\le2^n$ (Master yok) | Fibonacci |
Her seviyeyi çiz, maliyetini yanına yaz, seviyeleri topla. $i$. seviye: $a^i$ düğüm, her biri $f(n/b^i)$; $\log_b n$ seviye; $n^{\log_b a}$ yaprak.
Binary search Merge sort n 1·O(1) n 1·n = n n/2 1·O(1) n/2 n/2 2·n/2 = n n/4 1·O(1) n/4 ×4 4·n/4 = n ... ... 1 1·O(1) 1 1 1 … 1 n·1 = n log n seviye → log n log n seviye → n log n
Binary search'te her seviyede tek bir dal aktif (diğer yarı gri): bu yüzden $a=1$.
Örnekler: merge sort, quick sort, binary search, $n$ sayının toplamı, en büyük eleman, üs alma $x^n$ ($T(n/2)+1$), Karatsuba, Strassen.
Özyineleme: taban durum (çıkış) + yineleme bağıntısı. Her özyinelemeli algoritma iteratif yazılabilir; iteratif genelde daha hızlı (fonksiyon çağrısı ve yığıt maliyeti yok). Özyinelemeli Fibonacci'nin hafızası yok, aynı değerleri tekrar tekrar hesaplar.
Ekleme: kökten başla; küçükse sola, büyükse sağa in; boş yere yeni düğümü koy. Arama: aynı yol. Maliyet $O(h)$: dengeli $\log n$, sıralı eklemede çarpık ağaç $n$.
Okuma (dolaşma): Preorder = Kök-Sol-Sağ, Inorder = Sol-Kök-Sağ (BST'de sıralı), Postorder = Sol-Sağ-Kök, Level-order = seviye seviye (kuyruk). Hepsi $\Theta(n)$.
Ekle: 50 30 70 20 40 60 80
50
/ \
30 70
/ \ / \
20 40 60 80
Pre : 50 30 20 40 70 60 80
In : 20 30 40 50 60 70 80
Post: 20 40 30 60 80 70 50
Silme: yaprak → kaldır; tek çocuk → çocuğu yerine bağla; iki çocuk → inorder ardılı (sağ alt ağacın en küçüğü) yerine koy.
Heap (dizi): $i$'nin çocukları $2i+1$, $2i+2$; ekle/çıkar $O(\log n)$, kurma $O(n)$.
def binary_search(a, x): # O(log n)
l, r = 0, len(a) - 1
while l <= r:
m = l + (r - l) // 2
if a[m] == x: return m
if a[m] < x: l = m + 1
else: r = m - 1
return -1
def merge_sort(a): # T(n)=2T(n/2)+n
if len(a) <= 1: return a
m = len(a) // 2
L, R = merge_sort(a[:m]), merge_sort(a[m:])
out, i, j = [], 0, 0
while i < len(L) and j < len(R):
if L[i] <= R[j]: out.append(L[i]); i += 1
else: out.append(R[j]); j += 1
return out + L[i:] + R[j:]
def insertion_sort(a): # O(n^2), sıralıda O(n)
for i in range(1, len(a)):
key, j = a[i], i - 1
while j >= 0 and a[j] > key:
a[j + 1] = a[j]; j -= 1
a[j + 1] = key
return a
def ekle(kok, x): # BST ekleme, O(h)
if kok is None: return Dugum(x)
if x < kok.deger: kok.sol = ekle(kok.sol, x)
elif x > kok.deger: kok.sag = ekle(kok.sag, x)
return kok
def inorder(kok, out): # Sol-Kök-Sağ
if kok:
inorder(kok.sol, out); out.append(kok.deger); inorder(kok.sag, out)
return out