Sikllarni analiz qilish

U qanday ishlaydi?
Master usuli asosan takrorlanish daraxti usulidan olingan. Agar T(n) = aT(n/b) + f(n) ning takrorlanish daraxtini chizsak, ildizda bajarilgan ish f(n) va barcha barglarda bajarilgan ish T(n^c) ekanligini ko‘ramiz. Bu Log_b^a. Va takrorlanish daraxtining balandligi Log_bⁿ

Takroriy daraxt usulida biz jami bajarilgan ishlarni hisoblaymiz. Agar barglarda bajarilgan ish ko'pnomli bo'lsa, barglar dominant qism bo'lib, bizning natijamiz barglarda bajarilgan ishlarga aylanadi (1-holat). Agar barglar va ildizda bajarilgan ish asimptotik jihatdan bir xil bo'lsa, unda bizning natijamiz balandlikning istalgan darajada bajarilgan ishiga ko'paytiriladi (2-holat). Agar ildizda bajarilgan ish asimptotik ko'proq bo'lsa, natijamiz ildizda bajarilgan ishga aylanadi (3-holat).

Vaqt murakkabligi Master Method yordamida baholanishi mumkin bo'lgan ba'zi standart algoritmlarga misollar:
Birlashtirish saralash: T(n) = 2T(n/2) + ʘ(n). U 2 holatda tushadi, chunki c1 va Log_b^a ham 1 ga teng. Demak, yechim ʘ(n Logn) bo‘ladi.


Ikkilik qidiruv: T(n) = T(n/2) + ʘ(1). U 2-holatga ham tushadi, chunki c 0, Log_b^a ham 0. Demak, yechim ʘ(Logn) ga teng.

Eslatmalar:

1) T(n) = aT(n/b) + f(n) ko’rinishdagi takrorlanishni Asosiy teorema yordamida yechish shart emas. Berilgan uchta holatda ular orasida ba'zi bo'shliqlar mavjud. Masalan, T(n) = 2T(n/2) + n/Logn takrorlanishini asosiy usul yordamida yechish mumkin emas.

2) f(n) = ʘ(n^c Log^k_n) uchun kengaytirilishi mumkin

Agar ba'zi bir doimiy k >= 0 va c = Log_b^a uchun f(n) = ʘ(n^c Log^k_n) bo'lsa, T(n) = ʘ(n^c Log^k+1_n) bo'ladi.