Algortim murakkabligini baholash usullari Vaqt bo’yicha murakkabligini baholash

Reja:

1. 
   Algortim murakkabligini baholash usullari
   
2. 
   Vaqt bo’yicha murakkabligini baholash
   
3. 
   Misollarni solishtirish
   

Ma’ruza bayoni

Bu darsimizda sizlar bilan algoritm murakkabligini qanday baholash va bu narsa nima uchun muhimligi haqida to'xtalib o'tamiz. Hamda O-notatsiysa (O(n), O(n^2)) nimani anglatishini ko'rib o'tamiz.

Odatda, dasturlash masalalarini yechishda bir nechta yechim mavjud bo'ladi. Ular bir-biridan ishlash tezligi, xotiradan qancha joy olishi yoki tushunish murakkabligi bilan farqlanadi. Bunda, asosan, ikki xil tushuncha mavjud: algoritmning vaqt bo'yicha murakkabligi va xotira bo'yicha murakkabligi.

Algoritmning vaqt bo'yicha murakkabligi - bu uning ishlash vaqtini unga kiruvchi (input) ma'lumot(lar)ga nisbatan o'zgarishiga aytiladi.

Algoritmning xotira bo'yicha murakkabligi - huddi yuqoridagi kabi, algoritm ishlashi uchun unga kerak bo'lgan xotira hajmini (operativ xotiradan olinadigan joy) kiruvchi (input) ma'lumot(lar)ga nisbatan o'zgarishiga aytiladi.

Dasturiy masalalar yechishda yuqoridagi ikkita omil eng muhimlari sanaladi. Shuning uchun sizning yechimingiz qanday holatdlarda o'rtacha qancha vaqt ishlashi va operativ xotiradan qancha joy egallashini bilish muhim hisoblanadi.

Dasturlash musobaqalarida, asosan, birinchi jihatga ko'proq e'tibor qaratiladi. Lekin aniq vaqt, judayam ko'p omillarga bog'liq: kompyuter qurilmalari, protsessori, operatsion tizim va hokazolarga. Shuning uchun ham bizga faqat uning nazariy jihatdan ishlash vaqtini baholash qiziq. Bunda O() (O - notatsiya)dan foydalaniladi.

O notatsiya ta'rifiga o'tishdan oldin bitta misol keltirib o'tamiz:

N ta elementli massivdan x elementni qidirish kerak bo'lsin. Oddiy yechim, chiziqli qidiruvni ko'ramiz, ya'ni massiv har bir elementni berilgan elementga birma-bir solishtirib ko'ramiz.

for i : 1 to length of A

if A[i] is equal to x

return TRUE

return FALSE

Bunda har bir amal o'zgarmas c vaqt sarflaydi deb hisoblaylik. Biz algoritm murakkabligini hisoblaganda eng yomon holatni hisobga olishimiz kerak. Bu holatda esa x element massivda yo'q holat eng yomon holat hisoblanadi, ya'ni massivning barcha N ta elementi ko'rib chiqilishi kerak. Umumiy holatda, algoritm ishlashi uchun N*c + c (N ta if uchun va bitta return uchun). Algoritm murakkibligini baholaganda konstantalar e'tiborga olinmaydi va bu yuqoridagi algoritm murakkabligini O(N) deb hisoblash mumkin.

Ya'ni kiruvchi massiv hajmi oshib borgan sari algoritmimiz ishlash vaqti ham N ga bog'liq oshib boradi (bu holatda chiziqli nisbatda). Endi ta'riflarga o'tadigan bo'lsak:

O-notatsiya

Ta’rif: Agar shunday konstanta c soni mavjud bo’lsaki, bunda barcha natural n sonlari uchun f(n)≤c*g(n) shart bajarilsa, f funksiya g funksiyadan tez o’smaydi va f(n)≤O(g(n)) ko’rinishida yoziladi.

O-notatsiya yuqori chegarani, ya'ni eng yomon holatni baholash uchun ishlatiladi. Shu sababdan ham dasturlash masalalarini yechishda O-notatsiyadan eng keng foydalaniladi.

Ω-notatsiya (Omega notatsiya)

Ta'rif: Agar shunday konstanta c soni mavjud bo’lsaki, bunda barcha natural n sonlari uchun f(n)≥c*g(n) shart bajarilsa, g funksiya f funksiyadan tez o'smaydi va f(n)≥Ω(g(n)) ko’rinishida yoziladi.

Ω-notatsiya pastki chegarani ifodalashda ishlatiladi.

Θ-notatsiya (Teta notatsiya)

Ta'rif: Agar shunday konstanta c soni mavjud bo’lsaki, bunda barcha natural n sonlari uchun f(n)=c*g(n) shart bajarilsa, f funksiya g funksiya bilan bir xilda o'sadi va f(n)=Θ(g(n)) ko’rinishida yoziladi.

Yanayam soddaroq tushunish uchun quyidagi jadvalni keltiramiz

Bu safar ham shu mavzumizni davom ettirib, algoritm murakkabligini baholashdagi asosiy qoidalar va algoritmik masalalarni yechishda eng ko'p uchraydigan algoritmik assimptotikalarga to'xtalib o'tamiz. (O(n*logn), O(n)) kabi.

Demak, birinchi navbatda algoritm murakkabligini baholashdagi asosiy qoidalar:

•