I qism. 3-dars

Algoritm murakkabligini baholash. I qism
"You can't always come up with the optimal solution, but you can usually come up with a better solution" - Barack Obama.
"Siz har doim ham eng yaxshi yechimni topa olmasligingiz mumkin, lekin siz yaxshiroq yechimni topishga qodirsiz" - Barak Obama
I qism. 3-dars
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

Darsimizning ikkinchi qismida algoritm murakkabligini hisoblashdagi asosiy qoidalarni va dasturlash olimpiadalarida eng ko'p uchraydigan murakkabliklarni ko'rib chiqamiz va solishtirib ko'ramiz.
Maqolani foydali deb hisoblasangiz uni do'stlaringizga ham ulashing.