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 21-1=1) da bajariladi. Bu shuni ko’rsatadiki, N=2k-1 da o’tishlar soni k dan oshmaydi. Oxirgi tenglikdan eng yomon holda o’tishlar soni k=log2(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=2k-1 deb faraz qilarkanmiz mos keluvchi yechim daraxti doim to’liq bo’ladi. Unda k daraja, ya’ni k=log2(N+1) bo’ladi. Biz har qaysi darajada bittadan solishtirish bajaryapmiz, shuning uchun solishtirishlar umumiy soni log2(N+1) dan oshmaydi.
Yetti elementli ro’yxatda qidirish uchun yechim daraxti
E’TIBORINGIZ UCHUN RAHMAT!
Do'stlaringiz bilan baham: |
