|
O‘zbekiston respublikasi oliy ta’lim, fan va innovatsiyalar vazirligi farg‘ona davlat universiteti
|
| bet | 4/12 | | Sana | 21.05.2024 | | Hajmi | 117,25 Kb. | | #248931 |
Bog'liq 1-kurs kurs ishi(2)Hashlashning bosh asoslari:
Hash funksiya: Hashlashda muhim qism hash funksiyasi hisoblanadi. Bu funksiya berilgan ma'lumotlar to'plamidan (masalan, qiymatlar to'plami) ma'lum bir o'zgaruvchiga (masalan, indeks) alohida hash qiymatini generatsiya qiladi. Yaxshi bir hash funksiyasi barcha ma'lumotlar uchun farqli hash qiymatlarni generatsiya qiladi va o'zgaruvchilarni farqiga mos ravishda tarqatadi.
Hash ketma-ketligi (Collision): Hashlashda muammo bo'lgan yoki bir nechta qiymatlar uchun bir xil hash qiymatiga ega bo'lish mumkin. Bu holat hash ketma-ketligi deb ataladi. Hash ketma-ketligi algoritmni samarali ishlashi uchun uni minimalizatsiya qilish kerak.
Hash jadval (Hash table): Hash jadval ma'lumotlarni ma'lum bir hash funksiyasi yordamida indekslash uchun ishlatiladi. Bu, ma'lum bir o'zgaruvchi (masalan, indeks) indekslash va qidirish uchun oson va tezroq foydalaniladi.
Interpolation Search (Interpolatsiya izlash): O'rtacha elementni topish uchun interpolatsiya formulalaridan foydalanish. Agar qidiruvning teskarisi element bilan tezroq ishlaydi. Ammo bu algoritm o'nlik tartibidagi to'plamlarda ishlamaydi.
Interpolatsiya izlash (Interpolation Search) algoritmi, o'lchamli tartiblangan to'plamda (masalan, massivda yoki ro'yxatda) bir qiymatni qidirish uchun ishlatiladi. Bu algoritm bir chiziqli interpolatsiya formulasi yordamida izlashni amalga oshiradi. Bunda, qidirilayotgan qiymatni aniqlash uchun to'plamdagi o'lcham va tartib (masalan, o'rta, katta) hisoblanadi.
Quyidagi tartibda Interpolatsiya izlash algoritmini ifodalash mumkin:
Boshlang'ich to'plamning boshidan boshlab yoki boshlang'ich tartiblangan indeksdan boshlab boshqa tartiblangan indeksni topish.
Qidirilayotgan qiymat va to'plamdagi eng kichik va eng katta qiymatlarni taqqoslash.
Chiziqli interpolatsiya formulasi yordamida qidirilayotgan qiymatning taxminiy indeksini topish.
Taxminiy indeksni tekshirish va qidirilayotgan qiymatga yaqinlik tekshirish.
Agar taxminiy indeksni topilsa, uni qaytarish; aks holda, qidirilayotgan qiymat topilmagan deb bildirish.
Interpolatsiya izlash algoritmi avvalgi qidiruv algoritmlariga nisbatan yuqori taqozlanadi, ammo uning ishchi shartlari mavjud:
To'plamning o'lchami va tartibi bo'yicha ishlaydi.
Qidirilayotgan qiymat va to'plamdagi eng kichik va eng katta qiymatlararo o'rtacha bo'lgan qiymatlar uchun qo'lga kiritiladi.
Interpolatsiya izlashning odatiy tartiblangan to'plamlarda ishlashi eng yaxshi, lekin to'plam tartibidan ko'ra aloqador yechimlarni topish uchun qulay bo'lishi mumkin.
|
| |
