Reja: Qidirish algoritmlari va ularni baholash Ketma-ket qidirish algoritmi Ikkilik daraxt boʻyicha qidirish Qidirish algoritmlarining qiyosiy harakteristikalari Xulosa Foydalanilgan adabiyotlar va saytlar Qidirish algoritmlari va ularni

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.}