Master Theorem

Master metodi quyidagi ko'rinishdagi rekurrent munosabatlarni yechish formulasi hisoblanadi:

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

Bu yerda:

• n = kiruvchi ma'lumotlar hajmi
• a = rekursiyadagi quyi muammolar soni
• n/b = har bir quyi muammoning hajmi. Barcha quyi muammolar bir xil hajmga ega deb hisoblanadi.
• f(n) = rekursiv chaqiruvdan tashqarida bajarilgan ishlar xarajati, bu muammoni bo'lish xarajati va yechimlarni birlashtirish xarajatini o'z ichiga oladi.

Bu yerda a ≥ 1 va b > 1 o'zgarmas sonlar (konstantalar) bo'lib, f(n) asimptotik musbat funksiyadir.

Asimptotik musbat funksiya shuni anglatadiki, yetarlicha katta n qiymatlari uchun bizda f(n) > 0 bo'ladi.

Master teoremasi rekurrent munosabatlarning (bo'lib tashla va hukmronlik qil algoritmlarining) vaqt murakkabligini oddiy va tezkor usulda hisoblashda qo'llaniladi.

Master teoremasi

Agar a ≥ 1 va b > 1 o'zgarmaslar bo'lsa hamda f(n) asimptotik musbat funksiya bo'lsa, rekursiv munosabatning vaqt murakkabligi quyidagicha aniqlanadi:

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

Bu yerda T(n) quyidagi asimptotik chegaralarga ega:

1. Agar f(n) = O(n^(log_b a - ε)) bo'lsa, u holda T(n) = Θ(n^(log_b a)).
2. Agar f(n) = Θ(n^(log_b a)) bo'lsa, u holda T(n) = Θ(n^(log_b a) * log n).
3. Agar f(n) = Ω(n^(log_b a + ε)) bo'lsa, u holda T(n) = Θ(f(n)).

Bu yerda ε > 0 o'zgarmas sondir.

Yuqoridagi har bir shart quyidagicha izohlanadi:

1. Agar har bir bosqichdagi quyi muammolarni yechish xarajati ma'lum bir koeffitsiyentga ortib borsa, f(n) ning qiymati n^(log_b a) ga nisbatan ko'phad darajasida kichikroq bo'ladi. Shunday qilib, vaqt murakkabligi oxirgi darajaning xarajati, ya'ni n^(log_b a) bilan belgilanadi.
2. Agar har bir bosqichdagi quyi muammoni yechish xarajati deyarli teng bo'lsa, u holda f(n) qiymati n^(log_b a) bo'ladi. Shunday qilib, vaqt murakkabligi f(n) ning umumiy bosqichlar soniga ko'paytirilganiga teng bo'ladi, ya'ni n^(log_b a) * log n.
3. Agar har bir bosqichdagi quyi muammolarni yechish xarajati ma'lum bir koeffitsiyentga kamayib borsa, f(n) ning qiymati n^(log_b a) ga nisbatan ko'phad darajasida kattaroq bo'ladi. Shunday qilib, vaqt murakkabligi f(n) xarajati bilan belgilanadi.

Master teoremasi bo'yicha yechilgan misol

T(n) = 3T(n/2) + n²

Bu yerda:

• a = 3
• n/b = n/2
• f(n) = n²
• log_b a = log₂ 3 ≈ 1.58 < 2, ya'ni f(n) > n^(log_b a + ε) (bu yerda ε o'zgarmas son).

Bu yerda 3-holat qo'llaniladi.

Shuning uchun:

T(n) = f(n) = Θ(n²)

Master teoremasining cheklovlari

Master teoremasidan quyidagi hollarda foydalanib bo'lmaydi:

• T(n) monoton bo'lmasa. Masalan, T(n) = sin n
• f(n) ko'phad (polinomial) bo'lmasa. Masalan, f(n) = 2ⁿ
• a o'zgarmas (konstanta) bo'lmasa. Masalan, a = 2ⁿ
• a < 1 bo'lsa