Vaqt murakkabligi
Eng yaxshi: O(1)
O'rtacha: O(log log n)
Eng yomon: O(n)
Interpolatsion qidiruv — bir tekis taqsimlangan tartiblangan ma’lumotlar uchun Binary Search algoritmining takomillashtirilgan turi. U doimo massivning o‘rtasiga o‘tish o‘rniga, qidirilayotgan qiymatga asoslanib elementning taxminiy o‘rnini aniqlaydi.
Ishlash tartibi:
1. Pozitsiyani hisoblaydi: pos = low + ((target - arr[low]) × (high - low)) / (arr[high] - arr[low])
2. Agar arr[pos] qidirilayotgan qiymatga teng bo‘lsa, pos ni qaytaradi
3. Agar arr[pos] < target bo‘lsa, massivning o‘ng qismidan qidiradi
4. Agar arr[pos] > target bo‘lsa, massivning chap qismidan qidiradi
Vaqt murakkabligi:
Eng yaxshi: O(1)
O‘rtacha: O(log log n) — bir tekis taqsimotda
Eng yomon: O(n) — notekis taqsimotda
Xotira murakkabligi: O(1)
Xususiyatlari:
- Tartiblangan massivni talab qiladi
- Bir tekis taqsimlangan ma’lumotlar uchun eng samarali
- Notekis taqsimotda samaradorligi O(n) gacha pasayishi mumkin
Ma’lumotlar bir tekis taqsimlangan bo‘lsa, interpolatsion qidiruv Binary Search algoritmidan ancha tez ishlashi mumkin, chunki u qidirilayotgan elementning qayerda joylashganini aniqroq taxmin qiladi.
O'xshash algoritmlar
Ko'p beriladigan savollar
- Interpolatsion qidiruv (Interpolation Search) nima?
- Interpolatsion qidiruv — bir tekis taqsimlangan tartiblangan ma’lumotlar uchun Binary Search algoritmining takomillashtirilgan turi. U doimo massivning o‘rtasiga o‘tish o‘rniga, qidirilayotgan qiymatga asoslanib elementning taxminiy o‘rnini aniqlaydi.
- Interpolatsion qidiruv (Interpolation Search) murakkabligi qanday?
- Vaqt (o'rtacha): O(log log n) — bir tekis taqsimotda · Xotira: O(1)
- Ushbu Interpolatsion qidiruv (Interpolation Search) vizualizatori kimlar uchun?
- Interpolatsion qidiruv (Interpolation Search) vizualizatsiyasi "Qidirish" kategoriyasida o'rta darajadagi o'rganuvchilar uchun mo'ljallangan. Talabalar, texnik suhbatlarga tayyorgarlik va amaliy takrorlash uchun foydali.
- Interpolatsion qidiruv (Interpolation Search) ga o'xshash qanday algoritmlar bor?
- Shu kategoriyada (Qidirish) quyidagilarni ko'rishingiz mumkin: Binary Search, Linear Search, Jump Search. Har biri interaktiv vizualizatsiyaga ega.