|
Referat mavzu: Saralash algoritmlarining samaradorligi va qiyosiy tahlili. Bajardi: Omonboyev Rashidbek
|
| bet | 4/5 | | Sana | 21.12.2023 | | Hajmi | 17,17 Kb. | | #125752 | | Turi | Referat |
Bog'liq Referat mavzu Saralash algoritmlarining samaradorligi va qiyosi-fayllar.org (2)Oʻrtacha hol tahlili
Xuddi ketma-ket qidirish algoritmidagi kabi tahlilda ikki holatni qaraymiz. Birinchisi maqsad qiymat roʻyxatda aniq mavjud hol va ikkinchisi u umuman yoʻq holat.
Birinchi holda maqsad qiymat uchun mumkin boʻlgan holatlar N ta va ular teng ehtimolli hamda ularning har biri 1/N ga teng. Agar qidirish jarayonini tavsiflovsi binar daraxtni qaraydigan boʻlsak, u holda 1 darajada daraxt ildiz elementidan qidirish uchun bitta solishtirish, ikkinchi darajadagi tugunlar elementlaridan qidirish uchun ikkita solishtirish va uchinchi darajada uchta solishtirish talab qilinadi. Umuman i darajadagi elementlardan qidirish uchun i solishtirish talab qilinadi. i darajada 2i-1 ta tugun mavjud va N=2k-1 da daraxtda k daraja mavjud. Bu shuki, barcha mumkin boʻlgan hollar uchun toʻliq solishtirishlar sonini har qaysi darajadagi solishritirishlarni tugunlar soniga koʻpaymalarini yigʻindisi hisoblab topish mumkin. Natijada oʻrtacha hol tahlili quyidagini beradi:
( uchun)
Endi maqsad qiymat roʻyxatda mavjud boʻlmagan holni qaraymiz. Elementnin mumkin boʻlgan holatlari soni N ga teng, ammo bu holda yana N + 1 maqsad qiymat roʻyxatda yoʻqligi uchun imkoniyatlar bor. Imkoniyatlar soni N + 1 ga teng, ya’ni maqsad qiymat roʻyxatdagi birinchi elementdan kichik, birinchidan katta ikkinchidan kichik, ikkinchidan katta uchinchidan kichik va h.k. maqsad qiymat N elementdan katta boʻlishi mumkin. Har qaysi bu elementlar yoʻqligi hollar к solishtirishda bajariladi. Hammasi boʻlib hisoblashda 2N + 1 imkoniyatlar ishtirok etadi. Nihoyat, hosil qilamiz:
uchun.
Yuqoridagi kabi almashtirishlar quyidagini beradi:
учун.
Oxirgi tenglik element roʻyxatda mavjud boʻlgan holda natijani farqsiz oshiradi. Masalan 2020-1=1 048 575 elementdan iborat roʻyxat uchun birinchi holda 19 ga yaqin natijaga, ikkinchi holda 19.5 ga yaqin natijaga ega boʻlamiz.
4. Qidirish algoritmlarining qiyosiy harakteristikalari
Saralanmagan fayllar va massivlar uchun bir tur qidirish usullari ishlatilsa, saralangan fayl va massivlar uchun boshqa turdagi qidirish algoritmlari ishlatiladi. Quyida ularning ayrimlari bilan tanishamiz:
№
|
Algoritm nomi
|
Qiyinlik bahosi
|
Afzalligi
|
Kamchiligi
|
1.
|
Ketma-ket qidirish
|
O((n-m+1)m)
|
Saralanmagan massivlarda ishlatiladi, oddiy, kichik roʻyxatlarda juda tez
|
Katta roʻyxatlarda sekin ishlaydi
|
2.
|
Ikkilik qidirish
|
O(log n)
|
Katta roʻyxat-larda tez ish-laydi, satrli ma’lumotlar bilan yengil ishlaydi
|
|
3.
|
Interpolotsion qidirish
|
O(log n)
|
Katta roʻyxatlarda tez ishlaydi
|
Murakkab satrli ma’lumotlar bilan qiyin ishlaydi
|
|
| |
