Master teorem
- Algoritmalar kursu
- Orta seviye
- Ders 67/80
- 4 dk
T(n) = aT(n/b) + f(n) denklemini ve çözümünü öğrenirsin.
Master teorem
Master teorem, T(n) = aT(n/b) + f(n) biçimindeki yinelemeleri çözer. Burada a alt problem sayısı, b bölme oranıdır.
Üç durum verir; her biri farklı karmaşıklık sınıfıdır ve hızlı çözüm sağlar.
Master teorem, böl ve yönet algoritmalarının karmaşıklığını hızlıca hesaplamayı sağlar.
Üç durum
Durum 1: f(n) küçükse T(n) = Θ(n^log_b a). Durum 2: f(n) = Θ(n^log_b a) ise T(n) = Θ(n^log_b a * log n). Durum 3: f(n) büyükse T(n) = Θ(f(n)).
Örnek: T(n) = 2T(n/2) + n, log_2 2 = 1, durum 2, T(n) = Θ(n log n).
Bu durumlar, merge sort gibi algoritmaların Θ(n log n) sonucunu hızlıca verir.
Uygulama Master hesapla
master_log_b_a(a, b) yaz. log_b a değerini döndür. print(master_log_b_a(2, 2)) ile 1.0 yazdır.
Başlangıç kodu
def master_log_b_a(a, b):
# log_b a hesaplaÖrnek çözüm
def master_log_b_a(a, b):
# log_b a hesapla
import math
return math.log(a, b)
print(master_log_b_a(2, 2))Beklenen çıktı
1.0
Soru ve cevaplar
Dersin sorularını cevaplarıyla birlikte inceleyebilirsin. Kendini denemek istersen dersi interaktif olarak çöz.
1 Master teorem: kavramları eşleştir
| Kavram | Anlamı |
|---|---|
a |
Alt problem sayısı |
b |
Bölme oranı |
f(n) |
Birleştirme |
Θ |
Karmaşıklık |
2 T(n) = 2T(n/2) + n yinelemesinin çözümü nedir?
- Θ(n^2)
- Θ(2^n)
- Θ(log n)
- Θ(n log n) Doğru cevap
Açıklama: Θ(n log n).
3 Master denklem
T(n) = aT(n/____) + f(n)T(n) = aT(n/b) + f(n)Açıklama: b doğru.