Samarqand davlat universiteti raqamli texnologiyalar fakulteti



Download 145,25 Kb.
bet10/11
Sana31.12.2021
Hajmi145,25 Kb.
#266110
1   2   3   4   5   6   7   8   9   10   11
Bog'liq
1-laboratoriya mashg'uloti

4-misol. Ichki sikllarni o'z ichiga olgan yanada murakkab algoritmlarni baholashning misoli sifatida ikkitasini ko'rib chiqamiz.

Masalaning sharti. a1, a2, ..., an butun sonlar qatori berilgan. Massiv tarkibiy qismlarini kamaymaydigan tartibda joylashtiring.

Birinchi algoritm massiv elementlarni tanlash usuli yordamida saralash.
Uning mohiyati quyidagicha. Butun massivda minimal element qidiriladi va birinchi o'ringa qo'yiladi, massivning qolgan qismida minimal qidiriladi va ikkinchi o'ringa qo'yiladi va hokazo, massivning oxirgi elementi ko'rib chiqilmaguncha bu ish davom ettiriladi. Ushbu algoritmdan odamlar kundalik hayotda foydalanadilar. Bu algoritm ancha "yomon", ya'ni samarasiz ko'rinadi. Keling, ushbu algoritmni batafsil ko'rib chiqaylik:


  1. for(int i=0; i

{

  1. min1=A[i]; n-1

  2. k=i; n-1

  3. for(int j=i+1; j2+n-2)/2

  4. if(min1>A[j]){ (n2-n)/2

  5. min1=A[j]; 0 dan (n2-n)/2 gacha

  6. k=j; 0 dan (n2-n)/2 gacha

  7. }

  8. A[k]=A[i]; n-1

  9. A[i]=min1; n-1

  10. }

4-operatorning quyidagicha olinadi. Ushbu sikl sarlavhasi har bir i uchun bajariladi va i = 1 uchun n marta, i = 2 uchun n - 1 marta va hokazo, i = n - 2 - 3 marta, i = n -1 2 marta bajariladi. Ya'ni, bizda a1, a2, ..., am arifmetik progressiyasi bor, ularning yig'indisi




sm =

(a1

+ am ) m




2

Bu yerda m = n-1, a1 = n, an-1 = 2 va yig'indisi (n + 2) (n-1) / 2 = (n2 + n-2) / 2.
5-operatorning bahosi xuddi shu tarzda olinadi, shunchaki unutmang for siklining asosiy qismihar doim tanasiga qaraganda yana bir marta bajariladi. Bu yerda m = n-1, a1 = n-1, an-1 = 1 va yig'indisi .

5- va 6-operatorlarning baholariga kelsak, biz bunga oldinroq duch kelganmiz.

Kiritilgan ma'lumotlarga qarab, ushbu operatorlar boshqacha marta bajarilishi mumkin. "Yaxshi" ma'lumotlar uchun (massiv allaqachon saralangan qilingan), bu operatorlar hech qachon bajarilmaydi. "Yomon" ma'lumotlar uchun ushbu operatorlar har bir tekshirishda min>a[j] bajariladi. Algoritmlarni saralash uchun "yomon" ma'lumotlar teskari tartibda saralangan massivdir.

Shunday qilib, saralash algoritmi uchun eng yaxshi ball n2 + 5n-5, eng yomon ko'rsatkich esa 2n2+4n-5. Yomonmi yoki yaxshimi? Hozircha faqat massiv allaqachon saralangan bo’lsa, algoritm ko'p vaqt sarflashini sezishingiz mumkin. Bu ushbu algoritmning aniq kamchiliklaridir.




Download 145,25 Kb.

Do'stlaringiz bilan baham:
1   2   3   4   5   6   7   8   9   10   11




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©hozir.org 2024
ma'muriyatiga murojaat qiling

kiriting | ro'yxatdan o'tish
    Bosh sahifa
юртда тантана
Боғда битган
Бугун юртда
Эшитганлар жилманглар
Эшитмадим деманглар
битган бодомлар
Yangiariq tumani
qitish marakazi
Raqamli texnologiyalar
ilishida muhokamadan
tasdiqqa tavsiya
tavsiya etilgan
iqtisodiyot kafedrasi
steiermarkischen landesregierung
asarlaringizni yuboring
o'zingizning asarlaringizni
Iltimos faqat
faqat o'zingizning
steierm rkischen
landesregierung fachabteilung
rkischen landesregierung
hamshira loyihasi
loyihasi mavsum
faolyatining oqibatlari
asosiy adabiyotlar
fakulteti ahborot
ahborot havfsizligi
havfsizligi kafedrasi
fanidan bo’yicha
fakulteti iqtisodiyot
boshqaruv fakulteti
chiqarishda boshqaruv
ishlab chiqarishda
iqtisodiyot fakultet
multiservis tarmoqlari
fanidan asosiy
Uzbek fanidan
mavzulari potok
asosidagi multiservis
'aliyyil a'ziym
billahil 'aliyyil
illaa billahil
quvvata illaa
falah' deganida
Kompyuter savodxonligi
bo’yicha mustaqil
'alal falah'
Hayya 'alal
'alas soloh
Hayya 'alas
mavsum boyicha


yuklab olish