Algoritmlarda Divide and Conquer texnikasi

Divide and Conquer (bundan keyin D&C) texnikasi juda köp algoritmlar işlatadigan dizayn patterni bölib, uning asosida bitta katta masalani kiçik-kiçik osonroq masalalarga böliş va ularni alohida-alohida yeçişni közda tutadi.
Algoritmning işlaş qadamlarini quyidagiça:
- Divide - katta bir masalani kiçik-kiçik bir xil tipdagi masalalarga bölib çiqiş
- Conquer - kiçik masalalarni yeçiş. Agar yeçim topilsa uni boşqa kiçik masalalarga rekursiv yöl bilan qöllaş.
- Combine - yeçimlarni birlaştiriş
Divide and Conquer ga misol qilib binary search'ning işlaş prinsipini keltiriş 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 içidan 75 sonini topişimiz kerak.
Oddiy linear search'da biz sikl içida array'ning har bir elementini taqqoslab çiqqan bölardik. Binary search'da arrayning örtasidagi elementni olamiz. Array uzunligi juft bölsa birinçi qismning ohirgi elementini olamiz. Bizning array uzunligi 44, demak 21-element bilan 75 ni taqqoslaymiz.
arr[21] = 45, 75 dan kiçkina. Demak biz qidirayotgan 75 soni arrayning örtadan keyingi qismida.
Array'ni örtadan bölib, ikkinçi qismini tekşirişni davom ettiramiz.
[...47, 49, 51, 53, 55, 57, 59, 61, 63, 65, 67, 69, 71, 73, 75, 77, 79, 81, 83, 85, 87, 89]
Uşbu qismning örtasini topamiz. Örtasi - arr[10] = 67, 75 dan kiçkina. Demak biz qidirayotgan son biz tekşirgan qismning örtadan keyingi tarafida.
[...69, 71, 73, 75, 77, 79, 81, 83, 85, 87, 89]
Uşbu qismning örtasini topamiz. Örtasi - arr[5] = 79, 75 dan katta. Demak biz qidirayotgan son biz tekşirgan qismning örtadan oldingi tarafida.
[...69, 71, 73, 75, 77]
Uşbu qismning örtasini topamiz. Örtasi - arr[2] = 73, 75 dan kiçkina. Demak biz qidirayotgan son biz tekşirgan qismning örtadan keyingi tarafida.
[...75,77]
Uşbu qismning örtasini topamiz. Örtasi - arr[0] = 75. Biz qidirayotgan sonimizni topdik.
Yuqoridagi misolda 44 ta elementli array'dan kerakli sonni 5 ta urinişda topdik. Linear search'da esa 75 soni array'ning 36-elementi bölgani uçun uni 36-urinişda topgan bölardik.
Binary searça minimal uriniş 1, maksimal uriniş log N marta böladi. Ya’ni array uzunligi 10 ta bölsa binary searchda maksimum 3 ta urinişda X ni topiş mumkin. Linear searchda esa maksimum 10 ta uriniş bölgan bölardi. Endi 100,000 elementi bor katta array'ni oladigan bölsak:
- Linear searchda max 100,000 uriniş
- Binary searchda max 16 uriniş!
Har bir urinişni şartli ravişda 1 sekund deb hisoblaganda, linear search 27,78 soatda işni tugatadi. Binary search 16 sekundda. Demak, ikki algoritmni soliştirganda eng yomon holatda (worst case) binary search 6250 marta tez işlaydi.
Köp holatlarda D&C algoritmi uçun kod yozişda rekursiyadan foydalaniladi. Rekursiya haqida özbek tilida ikki ajoyib maqola topganim uçun, rekursiya haqida töxtalmay, maqolalarni şu yerda bölişaman:
Quyida binary search funksiyasini rekursiya va iteratsiya bilan yozişga urinib kö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 böyiça savollarni Github’dagi Webmaxor / leetcode-solutions repository’da yozişingiz yoki kodda **Reference in new issue **ni bosib, qoldirişingiz mumkin.