Binary Search
Vaqt murakkabligi nima ekani haqidagi umumiy tushuntirish uchun ushbu sahifaga qarang.
Ikkilik qidiruvning vaqt murakkabligi
Ikkilik qidiruv (Binary Search) allaqachon saralangan massivda o‘rtadagi qiymatni tekshirish orqali maqsadli qiymatni topadi. Agar o‘rtadagi qiymat maqsadli qiymat bo‘lmasa, algoritm chap yoki o‘ng qism massivni tanlaydi va maqsadli qiymat topilguncha qidiruvni davom ettiradi.
Binary Search vaqt murakkabligini topish uchun \(n\) ta qiymatli massivda maqsadli qiymatni topish uchun nechta taqqoslash amali kerakligini ko‘rib chiqaylik.
Eng yaxshi holat — birinchi o‘rtadagi qiymat maqsadli qiymat bilan bir xil bo‘lishi. Bunday bo‘lsa, maqsadli qiymat darhol, atigi bitta taqqoslash bilan topiladi, shuning uchun bu holatda vaqt murakkabligi \(O(1)\) ga teng.
Eng yomon holat — qidiruv sohasini u faqat bitta qiymatdan iborat bo‘lib qolguncha qayta-qayta ikkiga bo‘lishga to‘g‘ri kelishi. Bunday bo‘lganda maqsadli qiymat topiladimi yoki yo‘qmi, bu vaqt murakkabligiga ta’sir qilmaydi.
2 ning darajalari bo‘lgan massiv uzunliklarini ko‘rib chiqaylik: 2, 4, 8, 16, 32, 64 va hokazo.
Faqat bitta qiymat qolishi uchun 2 ni necha marta ikkiga bo‘lish kerak? Faqat bir marta, to‘g‘rimi?
8 ta bo‘lsa-chi? Faqat bitta qiymatga yetib kelish uchun 8 ta qiymatli massivni 3 marta ikkiga bo‘lishimiz kerak.
32 ta qiymatli massivni 5 marta ikkiga bo‘lish kerak.
Ko‘ramizki, \(2=2^1\), \(8=2^3\) va \(32=2^5\). Demak, bitta elementga yetib kelish uchun massivni necha marta bo‘lishimiz kerakligini 2 asosli daraja ko‘rsatkichidan topish mumkin. Bunga boshqacha qarashning yana bir usuli — "shu songa yetish uchun 2 ni o‘ziga necha marta ko‘paytirishim kerak?" deb so‘rash. Matematik jihatdan 2 asosli logarifmdan foydalanishimiz mumkin, shunda \(n\) uzunlikdagi massivni \( \log_{2}(n)\) marta ikkiga bo‘lish mumkinligini aniqlaymiz.
Demak, Binary Search vaqt murakkabligi quyidagiga teng
\[ \underline{\underline{O( \log_{2} n )}} \]
O‘rtacha holatni aniq belgilash unchalik oson emas, ammo biz algoritmning vaqt murakkabligini Big O notatsiyasi yordamida eng yomon holatning yuqori chegarasi sifatida tushunganimiz sababli, o‘rtacha holat unchalik qiziq emas.
Eslatma: Binary Search vaqt murakkabligi \(O( \log_{2}n)\) Linear Search vaqt murakkabligi \(O(n)\) dan ancha tez, ammo Binary Search saralangan massivni talab qilishini, Linear Search esa talab qilmasligini yodda tutish muhim.
Agar ikkilik qidiruvga \(n\) ta qiymatli massivda qiymatni topish uchun qancha vaqt kerakligini chiziqli qidiruv bilan solishtirib chizsak, quyidagi grafikni olamiz:
Binary Search simulyatsiyasi
Simulyatsiyani massivdagi turli miqdordagi qiymatlar \(n\) uchun ishga tushiring va Binary Search maqsadli qiymatni topishi uchun nechta taqqoslash kerakligini ko‘ring:
{{ this.userX }}
Amallar: {{ operations }}
Topilmadi!
Ikkilik qidiruv simulyatsiyalarini ishga tushirganda ko‘rib turganingizdek, massiv katta bo‘lsa va biz izlayotgan qiymat topilmasa ham, qidiruv juda kam taqqoslashni talab qiladi.
W3Schools Pathfinder
Yutuqlaringizni kuzating – bu bepul!