bilan bajarilishini ta’minlang. Bunda sikl bir va bir necha marta bajariladi va hisoblashning turli
tarmoqlari bo‘ylab o‘tadi. 1.4 va 1.5-masalalardagi algoritmlar qanchalik samarali? Bu savolga
Har bitta masala uchun uning yechilishini maqbul vaqti to‘g‘risida gapirish mumkin.
Ba’zi masalalar uchun bu sindirish bir necha ulushidan, boshqa masalalar uchun minutlar va
soatlarni tashkil qiladi. Ko‘pincha bitta masalani turli xil algoritmlar yordamida yechish mumkin
va uning ba’zilari maqbul vaqt ichida natija bersa, ba’zilari natija bermaydi. Bunday vaqtlarda
algoritmning to‘g‘ri tanlanishi hal qiluvchi hisoblanadi. Odatda, masala yechishni shunday
dasturlaydilarki, uning yordamida masalaning istalgan mumkin bo‘lgan holatlarini yechish
mumkin bo‘lsin. Masalan: masalaning “berilgan son oddiy hisoblanadimi?”, aniq sonli
masalalar: “997 soni oddiy sonmi?”, “2007 soni oddiy sonmi?” va shu kabilar. Holatlar aniq
kiruvchi ma’lumotlar bilan aniqlanadi. Ular esa, odatda, qandaydir parametrli sondagi raqamlar
miqdori, massivdagi elementlar miqdori va shu kabilar bilan xarakterlanadi. Bu parametr natural
qiymatlarga ega va masala holatlarining o‘lchami deyiladi. Odatda masala holatlarining o‘lchami
bo‘lib kiruvchi ma’lumotlarning ko‘rinishi taqdim qiligan bitlar soni hisoblanadi. Biroq kiruvchi
ma’lumotlar qiymatlar ketma-ketligini tashkil qiluvchi masalalarda bitlar soni emas ketma-ketlik
uzunligi o‘lcham hisoblanadi. Skalyar tipdagi (o‘zlashtirish, taqqoslash, qo‘shish, ko‘paytirish va
shu kabilar) qiymatlar ustidagi operatsiyalarni elementar harakatni bajarish davomiyligi uchun
operatsiyalariga va harakatning o‘ziga bog‘liq emas deb taxmin qilamiz. U holda dasturning shu
vaqti bajaruvchi elementar harakatlar soniga to‘g‘ri proporsional ya’ni harakatlar miqdori bilan
o‘lchanadi. Algoritm murakkabligi tushunchasida bosh rolni elementar harakatlar soni o‘z
o‘zidan o‘ynamaydi, balki masala xollaring o‘lchami oshganida uning o‘sish harakteri o‘ynaydi.
Bu tasdiqni aniqlashtiramiz.
Biror A – masala yechishning algoritmi bo‘lsin. Ushbu algoritm bo‘yicha masala hollari
yechilganida qandaydir miqdorda elementar harakatlar bajariladi. Holatlarning mumkin bo‘lgan
har bir n o‘lchamiga ushbu o‘lchamdagi ko‘rinishlar uchun eng katta elementar harakatlar
miqdorini moslashtiramiz. Bu miqdorni F
A
(n) bilan belgilaymiz.
Algoritm yordamida n o‘lchamli hollarni yechishda elementar harakatlarning eng katta miqdori
kabi aniqlangan F
A
(n) funksiya A algoritmning murakkabligi deyiladi.
Deyarli barcha real masalalar yechimlarining algoritmlar murakkabligi kamayadigan
funksiya hisoblanadi. Real algoritmlar uchun F
A
(n) funksiyaning analitik ifodasi, odatda,
mumkin emas va kerak emas. Amaliy qiymat n ga nisbatan F
A
(n) o‘sish tartibiga ega. U oddiy
analitik qiymatga ega bo‘lgan boshqa funksiya yordamida beriladi va F
A
(n) uchun baho
hisoblanadi.
Agar musbat C
2
va natural m sonlar mavjud bo‘lsa, ular uchun F(n)≥C
2
G(n) n>m ga bo‘lsa,
G(n) funksiya F(n) funksiya uchun ustidan baho deyiladi. Funksiyalar orasidagi ushbu
bog‘lanish “0” belgisi yordamida belgilanadi: F(n)=0(G(n)). “0(….)” yozuv “0… dan katta” deb
o‘qiladi. Agar musbat c
1
va m natural sonlar mavjud bo‘lsa, ular uchun n>m ga c
1
G(n)
bo‘lsa, G(n) funksiya F(n) funksiya uchun pastdan baho deyiladi. Funksiyalar orasidagi ushbu
bog‘lanish “ Ω(omega)” belgisi bilan belgilanadi: F(n) = Ω (G(n)). Agar musbat aniq c
1
, c
2
va n
natural m sonlar mavjud bo‘lsa, ular uchun n>m ga c
1
G(n)
2
G(n) bo‘lsa, G(n) funksiya,
F(n) funksiya uchun baho deyiladi, yoki F(n) funksiya G(n) tartibning funksiyasi hisoblanadi.
Funksiyalar orasidagi ushbu bog‘lanish “θ (teta)” belgisi orqali belgilanadi: F(n)= θ (G(n)).
Ba’zan bunday ta’riflardan foydalanadilar.
Agar lim F(n)/G(n)= C, bu yerda 0
funksiyasi deyiladi. Bu ta’rif F(n) = θ (G(n)) ga o‘xshash ekanligiga n larda G(n) dan kichik
tartib funksiyasi deyiladi. Bunday munosabat 0(kichik) bilan belgilanadi: F(n)=o(G(n)).
Real algoritmlarning murakkabligini baholash uchun logorifmik, darajali va ko‘rsatmali
funksiyalar hamda ularning yig‘indisi, ko‘paytmalari yetarli. Ularning barchasi monoton
o‘suvchi va oddiy ifodalanadilar. Masalan:n>2 da 0,5n
2
2
bo‘lgani uchun n(n-1)=0(n
2
).
Analogik tarzda n
3
+100n
2
=θ(n
3
)=o(n
3,1
)=o(2
n
), 100 logn+10000= θ(logn)= θ(lg)=o(n) ekanligiga
ishonish murakkab emas. Xohlagan musbat c doimiy o(1) va θ(1) baholarga egaligi o‘z-o‘zidan
ayon. Algoritmlar murakkabligining baholarini hisoblash uchun odatda quyidagicha ta’riflari
keltirilgan ikki qoida ishlatiladi.
