Bir xil me‟yorda oʻlchash kriteriyasi boʻyicha sigʻimning murakkabligi. Bu yerda hamma narsa oddiy. Oʻzgaruvchilar sonini hisoblashingiz kerak. Agar topshiriq massivlardan foydalansa, massivdagi har bir yacheyka oʻzgaruvchi hisoblanadi. Oʻzgaruvchilar soni kirish kattaligiga bogʻliq boʻlmaganligi sababli, murakkablik O (1) boʻladi.
Logarifmik oʻlchash kriteriyasi ega boʻlgan sigʻimning murakkabligi. Bunday holda, siz xotira yacheykasida boʻlishi mumkin boʻlgan maksimal qiymatni hisobga olishingiz kerak. Agar qiymat aniqlanmagan boʻlsa (masalan, operand boʻlganda), u holda chegaraviy qiymati bor deb hisoblanadi.
Ushbu masalada qiymati n (i) dan oshmaydigan va n (result) qiymatidan oshmaydigan oʻzgaruvchi mavjud. Shunday qilib, ga teng.
2-misol. Massiv elementlari yigʻindisi. Bir oʻlchovli massivning barcha elementlari qiymatlari yigʻindisini hisoblaydigan quyidagi algoritm bor deylik:
23
(1) S=0;
(2) for(int i=0; i
(3) S=S+A[i];
Algoritmni bitta satrda bitta operator boʻladigan tarzda yozish kerak. Bundan tashqari, har bir bajarilgan operator yonida, ushbu operatorning necha marta bajarilishini koʻrsatadigan kirish ma‘lumotlarining oʻlchamiga bogʻliq boʻlgan ifoda yozishingiz kerak. Ushbu baholash ozmi-koʻpmi aniqroq boʻlishi mumkin, asosiysi siz uni xuddi shu tarzda bajarishingiz kerak. Masalan, har bir bayonot bir mavhum vaqt birligida bajarilgan deb taxmin qilishingiz mumkin. Yoki har bir operatorning bajarilishini elementar amallar ketma-ketligiga ajrating: xotiradan oʻqing, xotiraga yozing, arifmetik amalni bajaring.
Birinchi yondashuvda biz quyidagi taxminlarni olamiz. Birinchi ifoda bir marta bajariladi va u kiritilgan ma‘lumotlarning oʻlchamiga bogʻliq emas. Ikkinchi operatorning bajarilish soni kiritilgan ma‘lumotlarning oʻlchamiga bogʻliq (xususan, n – massivning uzunligiga). Ushbu holatda bu n + 1 (for siklining boshi uning tanasidan bir marta koʻproq bajarilishini unutmang). Shunga koʻra uchinchi operator n mavhum vaqt birligida bajariladi. Shunday qilib, bizda:
Do'stlaringiz bilan baham: |
