Paghahanap ng Linya kumpara sa Binary Search
Nilalaman
- Mga Nilalaman: Pagkakaiba sa pagitan ng Linear Search at Binary Search
- Tsart ng paghahambing
- Binary Search
- Pangunahing Pagkakaiba
- Konklusyon
- Paliwanag ng Video
Ang pagkakaiba sa pagitan ng linear na paghahanap at isang binary paghahanap ay na sa linear na paghahanap ang bawat elemento ay nasuri at inihambing at pagkatapos ay pinagsunod-sunod samantalang sa binary paghahanap ng isang listahan na dapat ay pinagsunod-sunod ay nahahati sa dalawang bahagi at pagkatapos ay pinagsunod-sunod. Ang paghahanap at pagbubukod ay dalawang pangunahing konsepto sa computer programming. Maraming mga algorithm ang ginagamit para sa paghahanap at pagsunud-sunod, ngunit ang dalawang pinaka ginagamit na algorithm para sa paghahanap at pag-uuri ay linear na paghahanap at binary paghahanap.
Ang pagkakaiba sa pagitan ng linear na paghahanap at isang binary paghahanap ay ang pagtatrabaho at kahusayan ng parehong mga algorithm. Ang binary search ay isang mas mahusay na algorithm kumpara sa linear na search algorithm. Ang pag-iiba o oras na kinakailangan upang ihambing ang bawat halaga bago ang pag-uuri ay mas mababa sa binary paghahanap kumpara sa linear na paghahanap.
Ang paghanap sa linear ay isang napaka-kumplikadong algorithm kung nais mong maghanap ng isang numero sa isang listahan, ihambing at umulit kung minsan ang bilang ng mga halaga sa listahan. Isa-isa sa bawat elemento ng listahan ay nakuha at inihambing sa katabing elemento. Ang lahat ng mga elemento ay na-access at suriin at pagkatapos ay matatagpuan ang tamang elemento. Maaaring magkaroon ng pinakamasamang kaso kung ang huling numero sa listahan ay ang bilang na dapat hahanapin. Ang linya ng paghahanap ay ang pamamaraan kung saan ang array ay traversed at ang elemento na hahanapin ay itinatag. Kung pinag-uusapan natin ang tungkol sa kahusayan, ang kahusayan ay ang bilang ng mga beses na dapat tumakbo ang programa upang mahanap ang numero. Kung nahanap natin ang numero na hinahanap natin sa unang posisyon pagkatapos lamang ng isang paghahambing na dapat gawin, at ang mga bagay ay pinagsunod-sunod ngunit kung hindi pagkatapos ay paghahambing ay kailangang gumawa muli at muli, at ang pag-aaksaya ay nasayang. Sa average, ang bilang ng mga paghahambing ay magiging (n + 1/2). At ang pinakamasama-kaso na kahusayan ng pamamaraang ito ay ang O (n) ay nangangahulugan ng pagkakasunud-sunod ng pagpapatupad.
Kung ihahambing sa linear na paghahanap, ang binary paghahanap ay napakahusay. Sa pamamaraang ito, ang array ay nahahati sa dalawang bahagi at sa ganitong paraan ang bilang ng mga paghahambing ay mas mababa kumpara sa binary search. Ang oras ay mas mababa din sa binary search kumpara sa linear na paghahanap. Binary sa paghahanap ng trabaho sa paraan na ang gitnang elemento ng array ay natagpuan at pagkatapos ang gitnang elemento ay inihambing sa isang bahagi ng array. Maaaring may tatlong posibilidad na ang gitnang numero ay maaaring ang bilang na kailangan nating hanapin o ang bilang na mas mababa sa gitnang numero o ang bilang na mas malaki kaysa sa gitna ng gitnang numero. Ang bilang ng mga paghahambing ay pinaka-log (N + 1). Binary Search kumpara sa linear na paghahanap ay isang mahusay na algorithm kapag inihambing sa linear na paghahanap, ngunit ang array ay dapat na pinagsunod-sunod bago gawin ang binary search.
Mga Nilalaman: Pagkakaiba sa pagitan ng Linear Search at Binary Search
- Tsart ng paghahambing
- Binary Search
- Pangunahing Pagkakaiba
- Konklusyon
- Paliwanag ng Video
Tsart ng paghahambing
| Batayan | Paghahanap ng Linya | Binary Search |
| Kahulugan | Linya ng paghahanap ang bawat elemento ay nasuri at inihambing at pagkatapos ay pinagsunod-sunod | Binary paghahanap ng isang listahan na dapat na pinagsunod-sunod ay nahahati sa dalawang bahagi at pagkatapos ay pinagsunod-sunod.
|
| Pagkumplikado ng Oras | Ang pagiging kumplikado ng oras ng linear na paghahanap ay O (N). | Ang pagiging kumplikado ng oras ng binary paghahanap ay O (log 2 N) |
| Uri ng Algorithm | Ang linear na paghahanap ay nakapagpahiwatig. | Binaryong paghahanap ay Hatiin at lupigin. |
| Linya ng code | Sa isang linear na paghahanap, kailangan naming sumulat ng higit pang code. | Sa isang binary paghahanap, kailangan naming sumulat ng mas kaunting code. |
Paghahanap ng Linya
Ang linear na paghahanap ay isang napaka-kumplikadong algorithm kung nais mong maghanap ng isang numero sa isang listahan, ihambing at pag-iintindi ang ilang beses sa bilang ng mga halaga sa listahan. Isa-isa sa bawat elemento ng listahan ay nakuha at inihambing sa katabing elemento. Ang lahat ng mga elemento ay na-access at suriin, at pagkatapos ay matatagpuan ang tamang elemento. Maaaring magkaroon ng pinakamasamang kaso kung ang huling numero sa listahan ay ang bilang na dapat hahanapin. Ang linya ng paghahanap ay ang pamamaraan kung saan ang array ay traversed at ang elemento na hahanapin ay itinatag. Kung pinag-uusapan natin ang tungkol sa kahusayan, ang kahusayan ay ang bilang ng mga beses na dapat tumakbo ang programa upang mahanap ang numero. Kung nahanap natin ang numero na hinahanap natin sa unang posisyon pagkatapos lamang ng isang paghahambing na dapat gawin, at ang mga bagay ay pinagsunod-sunod ngunit kung hindi pagkatapos ay paghahambing ay kailangang gumawa muli at muli, at ang pag-aaksaya ay nasayang. Sa isang average, ang bilang ng mga paghahambing ay magiging (n + 1/2). At ang pinakamasamang kaso ng kahusayan ng pamamaraang ito ay ang O (n) ay kumakatawan sa pagkakasunud-sunod ng pagpapatupad.
Binary Search
Kung ihahambing sa linear na paghahanap, ang binary paghahanap ay napakahusay. Sa pamamaraang ito, ang array ay nahahati sa dalawang bahagi at sa ganitong paraan ang bilang ng mga paghahambing ay mas mababa kumpara sa binary search. Ang oras ay mas mababa din sa binary search kumpara sa linear na paghahanap. Binary sa paghahanap ng trabaho sa paraan na ang gitnang elemento ng array ay matatagpuan at pagkatapos ang gitnang elemento ay inihambing sa isang bahagi ng array.
Maaaring may tatlong posibilidad na ang gitnang numero ay maaaring ang bilang na kailangan nating hanapin o ang bilang na mas mababa sa gitnang numero o ang bilang na mas malaki kaysa sa gitna ng gitnang numero. Ang bilang ng mga paghahambing ay pinaka-log (N + 1). Binary Search kumpara sa linear na paghahanap ay isang mahusay na algorithm kapag inihambing sa linear na paghahanap, ngunit ang array ay dapat na pinagsunod-sunod bago gawin ang binary search.
Pangunahing Pagkakaiba
- Linya ng paghahanap ang bawat elemento ay nasuri at inihambing at pagkatapos ay pinagsunod-sunod samantalang ang Binary paghahanap sa isang listahan na dapat na pinagsunod-sunod ay nahahati sa dalawang bahagi at pagkatapos ay pinagsunod-sunod.
- Ang pagiging kumplikado ng oras ng linear na paghahanap ay 0 (N) samantalang ang pagiging kumplikado ng oras ng binary paghahanap ay O (log2N).
- Ang linear na paghahanap ay iterative samantalang ang Binary search ay Hatiin at lupigin.
- Sa linear na paghahanap, kailangan naming sumulat ng higit pang code samantalang sa binary paghahanap kailangan naming sumulat ng mas kaunting code.
Konklusyon
Sa artikulong ito sa itaas nakita namin ang malinaw na pagkakaiba-iba sa pagitan ng linear na paghahanap at binary paghahanap.
