Divide and Conquer (bundan keyin D&C) texnikasi juda ko’p algoritmlar ishlatadigan dizayn patterni bo’lib, uning asosida bitta katta masalani kichik-kichik osonroq masalalarga bo’lish va ularni alohida-alohida yechishni ko’zda tutadi.
Algoritmning ishlash qadamlarini quyidagicha:
- Divide – katta bir masalani kichik-kichik bir xil tipdagi masalalarga bo’lib chiqish
- Conquer – kichik masalalarni yechish. Agar yechim topilsa uni boshqa kichik masalalarga rekursiv yo’l bilan qo’llash.
- Combine – yechimlarni birlashtirish
Divide and Conquer ga misol qilib binary search’ning ishlash prinsipini keltirish mumkin.
Binary search
Bizda tartiblangan array bor:
const arr = [1, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41, 43, 45, 47, 49, 51, 53, 55, 57, 59, 61, 63, 65, 67, 69, 71, 73, 75, 77, 79, 81, 83, 85, 87, 89]
Uning ichidan 75 sonini topishimiz kerak.
Oddiy linear search’da biz sikl ichida array’ning har bir elementini taqqoslab chiqqan bo’lardik. Binary search’da arrayning o’rtasidagi elementni olamiz. Array uzunligi juft bo’lsa birinchi qismning ohirgi elementini olamiz. Bizning array uzunligi 44, demak 21-element bilan 75 ni taqqoslaymiz.
arr[21] = 45, 75 dan kichkina. Demak biz qidirayotgan 75 soni arrayning o’rtadan keyingi qismida.
Array’ni o’rtadan bo’lib, ikkinchi qismini tekshirishni davom ettiramiz.
[…47, 49, 51, 53, 55, 57, 59, 61, 63, 65, 67, 69, 71, 73, 75, 77, 79, 81, 83, 85, 87, 89]
Ushbu qismning o’rtasini topamiz. O’rtasi – arr[10] = 67, 75 dan kichkina. Demak biz qidirayotgan son biz tekshirgan qismning o’rtadan keyingi tarafida.
[…69, 71, 73, 75, 77, 79, 81, 83, 85, 87, 89]
Ushbu qismning o’rtasini topamiz. O’rtasi – arr[5] = 79, 75 dan katta. Demak biz qidirayotgan son biz tekshirgan qismning o’rtadan oldingi tarafida.
[…69, 71, 73, 75, 77]
Ushbu qismning o’rtasini topamiz. O’rtasi – arr[2] = 73, 75 dan kichkina. Demak biz qidirayotgan son biz tekshirgan qismning o’rtadan keyingi tarafida.
[…75,77]
Ushbu qismning o’rtasini topamiz. O’rtasi – arr[0] = 75. Biz qidirayotgan sonimizni topdik.
Yuqoridagi misolda 44 ta elementli array’dan kerakli sonni 5 ta urinishda topdik. Linear search’da esa 75 soni array’ning 36-elementi bo’lgani uchun uni 36-urinishda topgan bo’lardik.
Binary searcha minimal urinish 1, maksimal urinish log N marta bo’ladi. Ya’ni array uzunligi 10 ta bo’lsa binary searchda maksimum 3 ta urinishda X ni topish mumkin. Linear searchda esa maksimum 10 ta urinish bo’lgan bo’lardi. Endi 100,000 elementi bor katta array’ni oladigan bo’lsak:
- Linear searchda max 100,000 urinish
- Binary searchda max 16 urinish!
Har bir urinishni shartli ravishda 1 sekund deb hisoblaganda, linear search 27,78 soatda ishni tugatadi. Binary search 16 sekundda. Demak, ikki algoritmni solishtirganda eng yomon holatda (worst case) binary search 6250 marta tez ishlaydi.
Ko’p holatlarda D&C algoritmi uchun kod yozishda rekursiyadan foydalaniladi. Rekursiya haqida o’zbek tilida ikki ajoyib maqola topganim uchun, rekursiya haqida to’xtalmay, maqolalarni shu yerda bo’lishaman:
Quyida binary search funksiyasini rekursiya va iteratsiya bilan yozishga urinib ko’ramiz.
Rekursiya:
Kod Githubda: https://github.com/Webmaxor/leetcode-solutions/blob/master/algorithms/searches/binary-search-recursion.js
Iteratsiya:
Kod Githubda: https://github.com/Webmaxor/leetcode-solutions/blob/master/algorithms/searches/binary-search.js
* * *
Mavzu bo’yicha savollarni Github’dagi Webmaxor / leetcode-solutions repository’da yozishingiz yoki kodda Reference in new issue ni bosib, qoldirishingiz mumkin.