|
Qidirish usullari samaradorligi va optimallashtirish
|
| bet | 3/8 | | Sana | 07.10.2024 | | Hajmi | 0,63 Mb. | | #273963 |
Bog'liq Raqamli texnologiyalar vazirligi muhammad al-xorazmiy nomidagi t Qidirish usullari samaradorligi va optimallashtirish.
Ketma-ket qidiruvni samaradorligi. Ixtiyoriy qidiruvning samaradorligi jadvaldagi ma’lumotlarning kalitlari bilan solishtirish soni – S bilan baxolanishi mumkin. Agar taqqoslashlar (solishtirish) soni qancha kichik bo’lsa, qidiruv algoritmi samaradorligi shuncha yaxshi bo’ladi.
Massivda ketma-ket qidiruvning samaradorligi quyidagicha bo’ladi:
C = 1 n, C = (n + 1)/2.
Umuman olganda ro’yxatda xam samaradorlik yuqoridagi kabi bo’ladi. Garchi massivda xam bog’langan ro’yxatda xam qidiruv samaradorligi bir xil bo’lsada, ma’lumotlarni massiv va ro’yxat ko’rinishda tasvirlashning o’ziga xos kamchilik va afzalliklari mavjud. Qidiruvning maqsadi - quyidagi jarayonlarni bajarilishidan iborat:
Topilgan yozuvni o’qish.
Qidirilayotgan yozuv topilmasa, uni jadvalga qo’yish.
Topilgan yozuvni o’chirish.
Birinchi jarayon (qidiruvning o’zi) massiv uchun ham ro’yxat uchun ham bir xil bo’ladi. Ikkinchi va uchinchi jarayonda esa qidiruv ro’yxatli tuzilmada samaraliqroq bo’ladi (sababi massivda elementlarn siljitish lozim).
Agar k massivda elementlarni siljitishlar soni bo’lsa, u xolda k = (n + 1)/2
bo’ladi.
Saralash tushunchasi va uning vazifasi.
Saralash – bu berilgan to’plam elementlarini biror bir tartibda joylashtirish jarayonidir. Saralashni maqsadi tartiblangan to’plamda kerakli elementni topishni osonlashtirishdan iborat. Saralash dasturlarni translyasiya qilinayotganda, ma’lumotlar majmuasini tashqi xotirada tashkil qilinayotganda, kutubxonalar, kataloglar, ma’lumotlar bazasi yaratilayotganda tadbiq qilinadi. Ma’lumki, saralashning turli hil algoritmlari mavjud. Sababi, bitta masalani saralash uchun juda ko’plab turli hil algoritmlardan foydalanish mumkin. Berilgan masalani hal qilishda ba’zilari mukammal bo’lishi mumkin. Shuning uchun saralash masalasida algoritmlarni qiyosiy tahlilini o’tkazish zarurati paydo bo’ladi.
|
| |
