- Bir kod parçasının işlemlerini sayıp büyüme sınıfını bulmak
- O, Ω ve Θ gösterimlerinin biçimsel tanımlarını uygulamak
- Özyinelemeli bir algoritmanın çalışma süresini ana teoremle tahmin etmek
Leyla çevrim içi bir kütüphane için arama özelliği yazdı: 1000 kitapta anında yanıt veriyor. Bir yıl sonra katalogda 10 milyon kitap var ve aynı özellik dakikalarca “düşünüyor”. Bilgisayar yavaşlamadı; algoritmanın çalışma süresi verinin boyutuyla çok hızlı büyüyor. Bu derste bu büyümeyi ölçmeyi ve önceden tahmin etmeyi öğreneceğiz.
İşlemleri saymak
Saniyeler makineye, dile ve arka plandaki işlemlere bağlıdır; bu yüzden bir algoritmayı saniyeyle değil, temel işlem sayısıyla değerlendiririz: karşılaştırma, atama, aritmetik işlem, dizi elemanına erişim. Bu sayı, girdi boyutu n'nin bir fonksiyonudur ve genellikle en kötü durum için hesaplanır; kullanıcıya verebileceğimiz garanti budur.
Bir fonksiyonda dış döngü i = 0 … n − 1, iç döngü j = i + 1 … n − 1 üzerinde döner; iç gövdede bir çarpma vardır (a[i] * a[j]). Gövde kaç kez çalışır ve bu hangi büyüme sınıfıdır?
Çözümü gösterÇözümü gizle
Toplam: (n − 1) + (n − 2) + … + 1 + 0 = n(n − 1)/2.
n = 1000 için bu 499.500 çarpmadır.
n(n − 1)/2 = 0,5n² − 0,5n; düşük dereceli terimi ve sabiti atarız → Θ(n²), karesel bir algoritma.
- ngirdi boyutu (eleman sayısı)
Gauss toplamı: “her eleman diğer her elemanla bir kez” türündeki iç içe döngülerin işlem sayısı.
Asimptotik gösterimler: O, Ω, Θ
f(n) = O(g(n)) yazımı, yeterince büyük n için f(n) fonksiyonunun g(n)'nin sabit bir katıyla yukarıdan sınırlandığı anlamına gelir: f, g'den daha hızlı büyümez. Ω alt sınırı, Θ ise ikisini birlikte, yani tam büyüme hızını verir.
- f(n)algoritmanın işlem sayısı
- g(n)karşılaştırma fonksiyonu (n, n², n log n …)
- cpozitif bir sabit
- n₀eşitsizliğin sağlandığı başlangıç boyutu
Ω alt sınırdır; Θ hem üst hem alt sınırdır (iki sabit arasında “sıkışma”).
f(n) = 3n² + 5n + 2 veriliyor. c ve n₀ sabitlerini göstererek f(n) = Θ(n²) olduğunu ispatla.
Çözümü gösterÇözümü gizle
3n² + 5n + 2 ≤ 3n² + 5n² + 2n² = 10n² → c = 10, n₀ = 1; demek ki f = O(n²).
Alt sınır: n ≥ 1 için 5n + 2 > 0, dolayısıyla 3n² + 5n + 2 ≥ 3n² → c = 3; demek ki f = Ω(n²).
İkisi birlikte: 3n² ≤ f(n) ≤ 10n² → f(n) = Θ(n²).
Yaygın karmaşıklık sınıfları
| Sınıf | Adı | Tipik algoritma | n = 10 | n = 1000 |
|---|---|---|---|---|
| O(1) | sabit | dizide indeksle erişim | 1 | 1 |
| O(log n) | logaritmik | ikili arama | ≈ 3 | ≈ 10 |
| O(n) | doğrusal | doğrusal arama, en büyüğü bulma | 10 | 10³ |
| O(n log n) | doğrusal-logaritmik | birleştirmeli sıralama | ≈ 33 | ≈ 10⁴ |
| O(n²) | karesel | kabarcık sıralaması, tüm çiftleri denemek | 100 | 10⁶ |
| O(2ⁿ) | üstel | tüm alt kümeleri denemek | 1024 | ≈ 10³⁰¹ |
| O(n!) | faktöriyel | tüm permütasyonları denemek | 3.628.800 | ≈ 10²⁵⁶⁷ |
def binary_steps(n):
steps, lo, hi = 0, 0, n - 1
while lo <= hi:
mid = (lo + hi) // 2
steps += 1
lo = mid + 1
return steps
def pair_steps(n):
count = 0
for i in range(n):
for j in range(i + 1, n):
count += 1
return count
print('n', 'log', 'linear', 'pairs')
for n in [10, 100, 1000, 2000]:
print(n, binary_steps(n), n, pair_steps(n))▸ Beklenen çıktı
n log linear pairs 10 4 10 45 100 7 100 4950 1000 10 1000 499500 2000 11 2000 1999000
| Karmaşıklık | ≈ 1 saniyede işlenebilen en büyük n |
|---|---|
| O(n) | ≈ 10⁸ |
| O(n log n) | ≈ 5 · 10⁶ |
| O(n²) | ≈ 10⁴ |
| O(n³) | ≈ 450 |
| O(2ⁿ) | ≈ 26 |
| O(n!) | ≈ 11 |
Yineleme bağıntıları ve ana teorem
Özyinelemeli bir algoritmanın çalışma süresi de özyinelemeli yazılır. İkili arama yarılardan birinde devam eder: T(n) = T(n/2) + c. Birleştirmeli sıralama diziyi iki yarıya böler, her yarıyı sıralar ve doğrusal sürede birleştirir: T(n) = 2T(n/2) + cn. Böyle bir denkleme yineleme bağıntısı denir.
- T(n)n elemanlı girdide çalışma süresi
- 2T(n/2)2T(n/2)iki yarının özyinelemeli işlenmesi
- cnbölme ve birleştirme işi (doğrusal)
Özyineleme ağacı: k. düzeyde n/2ᵏ boyutlu 2ᵏ alt problem vardır; düzeyin toplam işi 2ᵏ · c · n/2ᵏ = cn olur. log₂ n düzey olduğundan toplam cn · log₂ n'dir.
- aözyinelemeli çağrı sayısı (a ≥ 1)
- bboyutun kaç kat küçüldüğü (b > 1)
- dbölme ve birleştirme işinin üssü (d ≥ 0)
Ana teorem (sadeleştirilmiş biçim): a ile bᵈ'yi karşılaştır. a < bᵈ → Θ(nᵈ); a = bᵈ → Θ(nᵈ · log n); a > bᵈ → Θ(nᵖ), burada p = log a / log b.
Sezgi şudur: a/bᵈ oranı, özyineleme ağacında bir düzeyden sonrakine işin nasıl değiştiğini gösterir. a < bᵈ iken iş aşağıya doğru azalır ve kökteki nᵈ baskın olur; a = bᵈ iken log n düzeyin hepsi eşit iş yapar; a > bᵈ iken iş artar ve yapraklar (nᵖ tane) belirleyici olur.
Çöz:
a) T(n) = 2T(n/2) + n
b) T(n) = T(n/2) + 1
c) T(n) = 8T(n/2) + n²
d) T(n) = 2T(n/2) + n²
Çözümü gösterÇözümü gizle
b) a = 1, b = 2, d = 0: bᵈ = 1 = a → Θ(n⁰ · log n) = Θ(log n) (ikili arama).
c) a = 8, b = 2, d = 2: bᵈ = 4 < 8 → Θ(nᵖ), p = log₂ 8 = 3 → Θ(n³) (saf özyinelemeli matris çarpımı).
d) a = 2, b = 2, d = 2: bᵈ = 4 > 2 → Θ(n²); kökteki iş baskındır.
import math
def T(n):
if n == 1:
return 1
return 2 * T(n // 2) + n
for k in [2, 4, 8, 16, 20]:
n = 2 ** k
print(n, T(n), n * k + n, round(T(n) / (n * math.log2(n)), 3))▸ Beklenen çıktı
4 12 12 1.5 16 80 80 1.25 256 2304 2304 1.125 65536 1114112 1114112 1.062 1048576 22020096 22020096 1.05
Önemli noktalar
- Algoritmalar saniyeyle değil, n'ye bağlı temel işlem sayısıyla, genellikle en kötü durumda değerlendirilir.
- O üst sınır, Ω alt sınır, Θ tam büyüme hızıdır; sabitler ve küçük terimler atılır.
- Sınıfların sırası: 1 < log n < n < n log n < n² < 2ⁿ < n!.
- Ardışık bloklar toplanır, iç içe döngüler çarpılır, yarıya bölme log n verir.
- T(n) = aT(n/b) + Θ(nᵈ) için a ile bᵈ karşılaştırılır; T(n) = 2T(n/2) + n → Θ(n log n).
Kendini test et
10 soru. Her doğru cevap XP kazandırır.