Mustaqil ishi Bajardi: Avliyoqulov a qabul qildi: Begimov o mavzu

O(9,1n)=O(n)

O(f*g) = O(f)*O(g) – ikkita funksiya ko’paytmasining murakkabligini baholash ularning murakkabliklari ko’paytmasiga teng, masalan:

O(5n*n) = O(5n)*O(n) = O(n)*O(n) = O(n*n) = O(n²)

O(f/g)=O(f)/O(g) – ikkita funksiyaning bo’linmasining murakkabligi ular murakkabliklarining bo’linmasiga teng, masalan:

O(5n/n) = O(5n)/O(n) = O(n)/O(n) = O(n/n) = O(1)

O(f+g) teng O(f) va O(g) larning dominantiga – funksiyalar summasining murakkabligini baholash, birinchi va ikkinchi qo’shiluvchilarning dominant (hukmron) murakkabligini baholash bilan belgilanadi, masalan:

O(n⁵+n¹⁰) = O(n¹⁰)

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.