5-mustaqil ishi


Download 316.44 Kb.
bet4/8
Sana21.01.2023
Hajmi316.44 Kb.
#1106159
1   2   3   4   5   6   7   8
Bog'liq
5-mustaqil Dilmurodov.F-1

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.

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


Misol: Ketma-ket qidiruv va Binar qidiruv algoritmlarini solishtirishga misol.(C++ tilida)
Dastur kodi:
#include
using namespace std;
int a[101];
int main(){
int n , l=0 , r=100 , m , count1=0, count2=0;
for(int i=1; i<101; i++){
a[i-1]=i;
}
cout<<"Qidirilayotgan sonni kiriting: ";
cin>>n;
for(int i=0; i<101; i++){
if(a[i]==n) break;
count1++;
}
while(l!=r){
m=(l+r)/2;
if(m==n) break;
else if(m
else r=m-1;
count2++;
}
cout<<"Ketma-ket qidiruv algoritmi yordamida n soni "<
cout<<"Binar qidiruv algoritmi yordamida n soni "<
return 0;
}

Ma’lumotlarni xeshlashtirish.


Download 316.44 Kb.

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




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©fayllar.org 2024
ma'muriyatiga murojaat qiling