|
Qidiruv algoritmlarining samaradorligi
|
| bet | 3/3 | | Sana | 16.11.2022 | | Hajmi | 0.82 Mb. | | #30636 |
Bog'liq MA\'LUMOTLAR QIDIRUV USULLARI-4 xudo xoxlasa tushadi99%, 3-labarotoriya ishi Saralash usul va algoritmlarini tadqiq qilis, cmd buyruqlari, Incremental model nima, 1matematik, word sAM 1 savol, Документ Microsoft Word (4), Ma\'ruzalar (2), ЛАБОРАТОРНАЯ РАБОТА N1, Dasturlash 2, Ariza, Qalandarova Gulshoda, 1648631455, 1650692784, 1651669892 (2) - Ma’lumki, qidiruvning maqsadi - quyidagi jarayonlarni bajarilishidan iborat:
- topilgan yozuvni o‘qish.
- qidirilayotgan yozuv topilmasa, uni jadvalga qo‘yish.
- topilgan yozuvni o‘chirish.
- Qidiruv algoritmlarining samaradorlik mezonlari:
- kalitlarni taqqoslashlar soni;
- dasturning ishlab chiqishga ketgan vaqt;
- talab qilinadigan xotira xajmi.
- Qidiruv algoritmlari ishlab chiqilayotganida, asosan, ko‘proq, jadvaldagi kalitlarni taqqoslashlar soniga e’tibor qaratiladi.
- Faraz qilaylik, ketma-ket qidiruv algoritmida taqqoslashlar soni -M, indeksli ketma-ket qidiruvda esa - S bo‘lsin. U holda:
- Massivda ketma-ket qidiruvning samaradorligi quyidagicha bo‘ladi, O(n):
- M =1 n, Mo‘rtacha = (n + 1)/2.
Eslatma: Ma’lumotlar jadvali massiv yoki bog‘lamli ro‘yxat ko‘rinishida bo‘ladi. - Eslatma: Ma’lumotlar jadvali massiv yoki bog‘lamli ro‘yxat ko‘rinishida bo‘ladi.
- Eslatma: Massiv va bog‘langan ro‘yxatda kerakli elementni bor yoki yo‘qligini aniqlash samaradorligi bir xil, ammo topilgan elementni o‘chirish yoki bunday element jadvalda bo‘lmasa, uni jadvalga qo‘yish talab qilingan bo‘lsa, u holda qidiruvni amalga oshirish ro‘yxatda samaraliroq bo‘ladi.
- Indeksli ketma-ket qidiruv samaradorligi
- Faraz qilaylik, kalitlar teng extimolli bilan tekis taqsimlangan, u holda samaradorlikni quyidagicha hisoblash mumkin:
- S = (m+1)/2 + (p+1)/2 = (n/p+1)/2 + (p+1)/2 = n/2p+p/2+1, bu erda: m – indeks o‘lchovi; m = n / p; p – qadam o‘lchovi.
- dS/dp=(d/dp) (n/2p+p/2+1)= - n / 2 p2 + 1/2 = 0 p2=n popt=
- Demak, indeksli ketma-ket qidiruvni samaradorligi tartibi bo‘ladi.
- 1. Qidiruv deganda nima tushiniladi?
- 2. Qidiruvning vazifasi nimadan iborat?
- 3. Qidiruvning maqsadi nimadan iborat?
- 4. Chiziqli qidiruvning g‘oyasini tushuntirib bering?
- 5. Indeksli ketma-ket qidiruv tushunchasi?
- 6.Binar qidiruv nima?
|
| |
