Referat mavzu: Saralash algoritmlarining samaradorligi va qiyosiy tahlili. Bajardi: Omonboyev Rashidbek

Eng yomon holat tahlili
Yuqorida koʻrdikki, roʻyxatning qolgan qismlarida barcha oʻtishda ikkining darajalari birga kamayadi. Yana siklning oxirgi iteratsiyasi qolgan qism oʻlchami 1 ga teng boʻlganda bajariladi. Bu esa j=1(ya’ni 2¹-1=1) da bajariladi. Bu shuni ko’rsatadiki, N=2^k-1 da o’tishlar soni k dan oshmaydi. Oxirgi tenglikdan eng yomon holda o’tishlar soni k=log₂(N+1) ga tengligini topamiz.
Tahlilda qidirish jarayoni uchun yechim daraxti ham yordam berishi mumkin. Yechim daraxti tugunlarida mos oʻtishda tekshiriladigan elementlar turadi. Yetti elementdan iborat roʻyxat uchun yechim daraxti 2-rasmda keltirilgan. Umumiy holda daraxt nibatan balanslashtirilgan, ya’ni biz har doim roʻyxat turli qismlarining oʻrtasini tanlaymiz. Shuning tufayli solishtirishlar sonini sanash uchun binar daraxtlar uchun keltirilgan formulalardan foydalanamiz.
Madomiki biz N=2^k-1 deb faraz qilarkanmiz mos keluvchi yechim daraxti doim to’liq bo’ladi. Unda k daraja, ya’ni k=log₂(N+1) bo’ladi. Biz har qaysi darajada bittadan solishtirish bajaryapmiz, shuning uchun solishtirishlar umumiy soni log₂(N+1) dan oshmaydi.

2-rasm. Yetti elementli ro’yxatda qidirish uchun yechim daraxti
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 2ⁱ-1 ta tugun mavjud va N=2^k-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.}