“Маълумотлар тузилмаси ва алгоритмлар” фанига кириш

Qidiruv algoritmlarining samaradorligi

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