DOUG LLOYD: Kaya sa CS50 natutunan namin tungkol sa isang iba't ibang mga pag-uuri at paghahanap algorithms. At minsan ay maaari itong maging isang maliit na manlilinlang upang panatilihin subaybayan kung ano ang algorithm ang ano. Na namin talagang lamang sinagap na masyadong sa ibabaw, mayroon ding iba't ibang mga paghahanap at pag-uuri algorithm. Kaya sa video na ito ay hahayaan tumagal lamang ng ilang minuto upang subukan at distill bawat algorithm pababa sa core elemento nito upang maaari mong tandaan ang pinaka mahalagang impormasyon tungkol sa kanila at ma-nakapagsasalita ang pagkakaiba, kung kinakailangan. 

Ang una ay ang uri ng pagpili. Ang pangunahing ideya sa likod ng pagpili ng uri ay hanapin ang pinakamaliit unsorted elemento sa isang array at magpalitan ng mga ito gamit ang unang unsorted elemento ng array na. Sabi namin na ang pinakamasama-case magpatakbo ng oras na iyon ay n nakalapat. At kung gusto mong isipin kung bakit, tumagal isang tumingin sa pagpili ng uri ng video. Ang pinakamahusay na-case na tumakbo ng oras ay din n nakalapat. 

Bubble-uuri, ang ideya sa likod na ang isa ay upang magpalitan ng katabi pares. Kaya iyon ang key na tumutulong sa iyo tandaan ang mga pagkakaiba dito. Pinili uri ay, sa ngayon, hanapin ang smallest-- bubble uri ay magpalitan ng mga katabi pares. Swap namin katabi ng mga pares ng mga elemento kung sila ay sira, na epektibong bula ng mas malaking elemento sa kanan, at sa parehong oras din ito ay nagsisimula upang ilipat ang mas maliit na mga elemento sa kaliwa. Ang pinakamasama-case time kaso run ng bubble sort ay n nakalapat. Ang pinakamahusay na-case na tumakbo ng oras ng bubble sort ay n. Dahil sa na sitwasyon hindi namin actually-- Maaaring hindi namin kailangan upang gumawa ng anumang mga swaps sa lahat. Kami lamang magkaroon upang gumawa ng isa pumasa sa lahat ng mga elemento n. 

In-uuri, ang pangunahing ideya dito ay nagbabago. Iyan ang keyword para sa uri pagpapasok. Kami ay pagpunta sa hakbang beses sa pamamagitan ng array mula kaliwa papuntang kanan. At tulad ng ginagawa namin, hindi namin pagpunta sa shift elemento na namin nakita para gumawa nang lugar para sa mas maliit na mga na kailangan upang umangkop sa tabi-tabi bumalik sa na pinagsunod-sunod sa bahaging ito. Kaya bumuo kami ang pinagsunod-sunod array isa sangkap sa isang panahon, sa kaliwa papunta sa kanan, at shift namin ang mga bagay na gumawa ng room. Ang pinakamasama-case tumakbo ang oras ng uri pagpapasok ay n nakalapat. Ang pinakamahusay na-case magpatakbo ng oras ay n. 

Sumanib sort-- keyword dito ay nahati at sumanib. Hatiin namin ang buong array, kung ito ay anim na mga sangkap, walong elemento, 10,000 elements-- hatiin namin ito down sa pamamagitan ng kalahati, sa pamamagitan ng kalahati, sa pamamagitan ng kalahati, hanggang kami ay may sa ilalim ng array ng n isa array elemento. Isang set ng n isa array elemento. Kaya namin na nagsimula sa isa 1000-element array, at makuha namin sa punto kung saan kami ay Mayroon 1,000 array one-element. Pagkatapos namin simulan upang sumanib sa mga sub arrays likod magkasama sa tamang order. Kaya naming gawin dalawang array one-element at lumikha ng isang array two-element. Kumuha kami ng dalawang array two-element at lumikha ng isang array four-element at iba pa at iba pa hanggang hindi namin muli itinayong muli isa n element ng array. 

Ang pinakamasama-case tumakbo ang oras ng sumanib-uuri ay n beses log n. Mayroon kaming n elemento, ngunit ang proseso na ito recombining tumatagal log n hakbang upang makakuha ng i-back sa isang buong array. Ang pinakamahusay na kaso magpatakbo ng oras ay din n log n dahil ang proseso na ito ay hindi tunay pag-aalaga kung ang array ay inayos o hindi na magsimula sa. Ang proseso ay ang parehong, mayroong walang paraan upang short circuit ng mga bagay. Kaya n log n sa pinakamasama kaso, n log n sa pinakamahusay na kaso. 

Usapan natin ang tungkol sa dalawang naghahanap algorithm. Kaya linear paghahanap ay tungkol iterating. Magpatuloy namin sa buong array sabay, mula kaliwa papuntang kanan, sinusubukan mong mahanap ang numero na kami ay naghahanap para sa. Ang oras na patakbuhin pinakamasama-case ay malaking O ng n. Ito ay maaaring tumagal sa amin iterating sa kabuuan ng bawat solong elemento upang mahanap ang elemento kaming naghahanap para sa, alinman sa huling posisyon, o hindi sa lahat. Ngunit hindi pa namin makumpirma na hanggang kami ay tumingin sa lahat ng bagay. m ang pinakamahusay na-case, nakita namin agad. Ang pinakamahusay na-case tumakbo ang oras ng linear paghahanap ay wakas ng 1. 

Sa wakas, nagkaroon binary paghahanap, na kung saan ay nangangailangan ng iba't-ibang mga array. Tandaan na ang isang tunay mahalagang pagsasaalang-alang kapag nagtatrabaho sa binary paghahanap. Ito ay isang paunang kinakailangan upang gamit it-- ang array na kayo ay naghahanap sa pamamagitan ng dapat na pinagsunod-sunod. Kung hindi man, ang keyword ay hatiin at lupigin. Hatiin ang array sa kalahati at puksain ang kalahati ng mga elemento sa bawat oras na ikaw ay magpatuloy sa pamamagitan ng. Dahil dito hatiin at lupigin at paghahati ng mga bagay sa loob ng kalahating diskarte, ang pinakamasama-case na tumakbo ng oras ng binary paghahanap ay mag-log n, na kung saan ay sa kalahatan mas mahusay kaysa sa n linear paghahanap ni. Ang pinakamahusay na-case magpatakbo ng oras ay isa pa rin. 

Maaari naming agad ito ang makahanap unang oras na gumawa kami ng isang dibisyon, ngunit, muli, tandaan na bagaman binary paghahanap ay malaki mas mahusay kaysa sa haba ng paghahanap sa pamamagitan ng kabutihan ng pagiging log n laban n, maaaring kailangan mong pumunta sa pamamagitan ng mga gawa ng paghihiwalay muna ang iyong array, na kung saan ay maaaring gumawa ng hindi gaanong epektibong mga ito depende sa laki ng iterating pinagsunod-sunod. 

Ako Doug Lloyd, ito ay CS50.