|
Samarqand davlat universiteti o. R. Yusupov, I. Q. Ximmatov, E. Sh. EshonqulovBog'liq ALGORITMLAR VA MA‟LUMOTLAR STRUKTURALARI return 0;
}
Berilgan masalaning kirish kattaligi n ekanligini aniqlash oson.
Qadamlar soni (n - 1). Shunday qilib, bir xil me‘yorda oʻlchash
kriteriyasi uchun vaqt murakkabligi O(n) dir.
Logarifmik oʻlchash kriteriyasi
bilan vaqt murakkabligi. Shu
nuqtada, baholanishi kerak boʻlgan amallarni ajratib koʻrsatish kerak.
Birinchidan, bu
taqqoslash
amallari. Ikkinchidan, oʻzgaruvchi
qiymatiga ta‘sir qiluvchi amallar (qoʻshish, koʻpaytirish, boʻlish,
ayirish). Oʻzlashtirish (ta‘minlash) amali hisobga olinmaydi, chunki ular
bir zumda amalga oshiriladi deb taxmin qilinadi.
Shunday qilib, ushbu masala uchta amal ajratilgan:
1)
i-qadamda
ni olamiz. Qadamlar soni
ta
boʻlgani uchun ushbu amalning murakkabligi
ga
tengdir.
2)
i++; i-qadamda
ni olamiz.
22
Ushbu holatda, quyidagicha yigʻindi hosil boʻladi:
∑
3)
result *=i; i-qadamda
( )
ni olamiz.
Ushbu holatda, quyidagi yigʻindi hosil boʻladi:
∑
( )
(∏
)
Agar biz barcha olingan qiymatlarni yigʻsak va n ning oʻsishi bilan
asta
sekin
oʻsadigan
atamalarni
bekor
qilsak,
(∏
)
biz yakuniy ifodasini olamiz.
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:
|
| |
