Master teorem

T(n) = aT(n/b) + f(n) denklemini ve çözümünü öğrenirsin.

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.

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.

Örnek çözümü göster

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))

Master denklem

T(n) = aT(n/____) + f(n)

Cevabı göster

T(n) = aT(n/b) + f(n)