|
Samarqand davlat universiteti o. R. Yusupov, I. Q. Ximmatov, E. Sh. EshonqulovBog'liq ALGORITMLAR VA MA‟LUMOTLAR STRUKTURALARI (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:
S=0; (1)
for(int i=0; i
S=S+A[i]; (n)
Barcha operatorlarning algoritmlar murakkabligi yigʻindisini
hisoblash natijasida 2n + 2 murakkablikni olish mumkin.
Algoritmlarni
baholashda
koʻpincha
quyidagi
funksiyalar
qoʻllaniladi:
, n,
,
,
,
,
,
.
koʻrinishida baholangan algoritmlar, har qanday sababga koʻra, juda tez
algoritmlar deb nomlanadi. Bunday algoritmlar unchalik koʻp emas.
Aslida, adabiyotda odatda O
bahoga ega boʻlgan faqat bitta
algoritm zikr qilinadi - bu ikkilik qidiruv algoritmi. Buni keyinroq koʻrib
chiqamiz.
va
deb baholangan algoritmlar
|
| |
