5-ma’ruza. Tez saralash algoritmi



Download 92 Kb.
bet5/6
Sana05.06.2022
Hajmi92 Kb.
#637363
1   2   3   4   5   6
return 0;
}


5.3.QuickSort algoritmi tahlili.
Massivni „tayanch“ elementiga nisbatan ikki qismga boʻlish jarayoni O(log­2n) vaqtni oladi. Bir xil rekursiya darajasi bajariladigan barcha boʻlinish amallari hajmi doimiy boʻlgan boshlangʻich massivning turli qismlarini qayta ishlagani uchun, har bir rekursiya darajasida jami O (n) amallar ham talab qilinadi. Shuning uchun algoritmning umumiy murakkabligi faqat boʻlinishlar soni, ya’ni rekursiya darajasi bilan belgilanadi. Rekursiyaning darajsi, oʻz navbatida, kirishlarning kombinatsiyasiga va “tayanch element” qanday aniqlanishiga bogʻliq.
Eng yaxshi holat. Eng yaxshi holatda har bir boʻlinish paytida massiv ikkita bir xil (+/- bitta element) qismlarga boʻlinadi, shuning uchun qayta ishlangan ichki massivlarning oʻlchamlari 1 ga yetadigan maksimal rekursiya darajasi log2n boʻladi. Natijada, quicksort tomonidan taqqoslash soni O(nlog2(n)) algoritmining umumiy murakkabligini beradigan   rekursiv ifodasining qiymatiga teng boʻladi.
Oʻrtacha holat. Kirish ma’lumotlarini tasodifiy taqsimlash uchun oʻrtacha murakkablik faqat ehtimollik bilan baholanishi mumkin.
Avvalo shuni ta’kidlash kerakki, aslida, “tayanch” elementi har safar massivni ikkita teng qismga ajratishi shart emas. Masalan, agar har bir bosqichda dastlabki massivning 75% va 25% uzunlikdagi massivlarga boʻlinish boʻlsa, rekursiya darajasi  ga teng boʻladi va O (nlogn) murakkablikni beradi. Umuman olganda, “tayanch” elementning chap va oʻng tomonlari orasidagi har qanday aniq nisbatlar uchun algoritmning murakkabligi bir xil boʻladi, faqat har xil konstantalar mavjud.
Yomon holat. Eng yomon holatda har bir “tayanch” 1 va n-1 oʻlchamdagi ikkita kichik massivni beradi, ya’ni har bir rekursiv chaqiriq uchun kattaroq massiv oldingi vaqtga nisbatan 1 ta qisqa boʻladi. Agar har bir ishlov berilgan elementlarning eng kichigi yoki eng kattasi mos yozuvlar sifatida tanlansa, bu sodir boʻlishi mumkin.
Bunday holda, n-1 “boʻlinish” amallar talab qilinadi va umumiy ishlash muddati   ta operatsiyani tashkil qiladi, ya’ni saralash kvadratik vaqt ichida amalga oshiriladi. Ammo almashtirishlar soni va shunga koʻra ish vaqti uning eng katta kamchiligi emas. Bundan ham yomoni, bu holda algoritmni bajarish paytida rekursiya darajasi n ga yetadi.


Download 92 Kb.

Do'stlaringiz bilan baham:
1   2   3   4   5   6




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