[Powered by Google Translate] [Linggo 3, ipinagpatuloy] 

[David J. Malan - Harvard University] 

[Ito ay CS50. - CS50.TV] 

Ayos lang. Maligayang pagbabalik. Ito ay CS50 at ito ay ang katapusan ng linggo 3. 

Kaya para sa mga pamilyar, huling taon Harvard Inilunsad kung ano ang tinatawag Innovation Lab, o i-lab, kung saan ay isang magandang gusali sa kabuuan ng ilog sa HBS ng campus na bukas sa mga mag-aaral sa kolehiyo, GSAS mga mag-aaral, ang mga mag-aaral mula sa lahat sa buong campus, kabilang ang mga guro, at ito ay isang lugar tipon upang gumana sa mga makabagong bagay, lalo na pangnegosyo bagay kung ikaw at 0 o higit pang mga kaibigan ay pag-iisip ng paggawa ng isang bagay pangnegosyo alinman sa panahon ng klase, pagkatapos ng klase, o higit pa. 

Kaya isa sa ang mga bagay na ginagawa nila sa ibabaw J termino ay mga biyahe na ito, isa na kung saan ay sa New York, na kung saan ay sa Silicon Valley. Space ay napaka-limitado, ngunit ito ay isang pagkakataon upang kuskusin ang mga balikat na may MBAs at graduate na mga mag-aaral sa buong campus at aktwal na magpalipas ng oras sa mga kanya-kanyang lugar pakikipag-chat up ng mga startup, pakikipag-chat up ng mga negosyante at ang gusto. Kaya kung interesado, i-check ang URL na ito dito. Ito ay magagamit din sa mga slide online. 

Ma namin tone down ang bahay audio lang ng kaunti? Kung nais mong upang sumali sa amin para sa tanghalian ito Biyernes, 1:15 p.m. sa Sunog at Yelo, mangyaring magtungo doon. Paumanhin kung ang form na napuno ng oras kang makakuha ng may. Subalit patuloy kaming tradisyon pasulong na ito. 

Ngayon patuloy namin ang mas mataas na antas ng talakayan ng iba't-ibang mga problema na maaari naming malutas, tumutuon higit na mas mababa, ngayon ng hindi bababa sa, sa code at marami pang iba sa mga ideya. Kaya sa tingin bumalik sa linggo 0 kapag torus namin ng phone book sa kalahati, ang layunin ng kung saan ay upang gawin ang isang bagay, tinatanggap na, kaunti dramatic ngunit upang ipadala ang punto na paghahanap ay hindi upang maging, kinakailangan, halata sa unang sulyap bilang maaari mong isipin. At problema na paglutas sa pangkalahatan ay maaaring hindi kinakailangang palaging ang pinakamahusay na - Ang pinaka-halata na solusyon ay maaaring hindi kinakailangang maging ang pinakamahusay na. Kaya nagkaroon kami phone book na ito at, lantaran, ang lahat ng sa amin sa kuwartong ito may instincts, malamang, upang magsimula sa gitna kapag naghahanap para sa Mike Smith at pagkatapos ay pumunta sa kaliwa o kanan batay sa anumang titik ng alpabeto namin ang nangyari sa magtapos sa. 

Ngunit na simpleng ideya na namin ang mga tao na kinuha para sa ipinagkaloob para sa kaya mahaba talagang dapat magsimula sa forefront ng iyong isip dahil ang bilang ng mga problema makakuha ng mas mas kumplikado kaysa sa isang libro ng telepono, mga parehong simple, makikinang na pananaw kung ano ay upang payagan sa amin upang malutas ang mga problema na mas kumplikadong at mas kawili-wili, kasama ng mga ito ang ilan sa mga bagay na lubos naming para sa ipinagkaloob na mga araw na ito. Bilyon-bilyong mga pahina ng web out doon, at pa Google at Bing at ang mga tulad upang mahanap ang mga bagay para sa amin tulad na. Na hindi nangyayari sa pamamagitan ng paggamit ng isang linear paghahanap, paghahanap sa pamamagitan ng lahat ng posibleng mga pahina ng web. Facebook ay sabihin sa iyo na ang lahat ng iyong mga kaibigan ay o mga kaibigan ng mga kaibigan, at masyadong maaaring gawin tila sa isang instant na mga araw na ito kahit na mayroon silang mga milyon-milyong ng mga gumagamit. 

At kaya kung paano namin aktwal na malutas ang mga problema sa na scale ay huli bawasan sa mga ideya na namin ay tumingin sa sa linggo 0 at ng kaunti pang ngayon. Hindi namin muling isakatuparan ang algorithm na ito, ngunit isipin ang ginawa din namin sa linggo 0 pagsasanay na ito kung saan ay namin ang lahat tumayo, sa numero 1, at pagkatapos ay nagkaroon kami lahat ng pagbilang sa sarili sa pamamagitan ng pagpapares off, ang pagdaragdag ng iyong mga numero, kalahati ng gang nakaupo sa bawat pag-ulit. Kaya namin nagpunta mula sa 500 mga mag-aaral sa 250-125 at iba pa. Ngunit tulad ng sinabi namin sa Monday, ang makapangyarihang ideya may ay na kung Dinoble namin ang laki ng problema na at ang lahat ng mga bata mula sa Katarungan o EC 10 dumating pabalik sa kuwarto at sumali sa amin, na rin, maaari naming marahil ang bilang na buong pinagsama-samang grupo sa pamamagitan lamang ng 1 pang malaki-ulit ng loop dahil sila lamang siguro double ang laki o sa EC 10 kaso ng kaunti pa kaysa sa double ang laki. At ito ay namin sa gastos ng kaunti mas maraming oras, ngunit hindi namin ay upang gastusin ang 400 o 700 higit pang mga hakbang. 

Lamang upang ipinta ang larawan na ito sa isang paraan na ang isang maliit na mas mababa abstract, sabihin hindi na ang lahat tumayo. Ngunit kung ang mga mo na pinili upang umupo sa orkestra ngayon ay hindi tututol nakatayo up, sabihin makita kung maaari naming malaman kung kabilang ka na ang pinakamataas na tao ay sa pamamagitan ng paggawa ng parehong uri ng pahambing na algorithm. Kaya kung nag-sitting sa orkestra, ang aking mga pasensiya, ngunit ang hakbang 1, tumayo; hakbang 2, pares sa sinuman na malapit sa iyo, malaman na taller, at umupo kung ikaw ay mas maikli. Ulitin. [Mag-aaral murmuring] 

Okay. Okay. Isa hinayaang katayuan. Ano ang iyong pangalan? >> Andrew. 

Andrew, ikaw ay ang pinakamataas na tao sa seksyon ng orkestra ngayon. 

Binabati kita. [Palakpakan at pagpalakpak] Okay. Magkaroon ng isang upuan. Kaya nakita namin Andrew. Subalit kung gaano katagal ito kinuha sa akin, halimbawa, upang makahanap ng Andrew sa seksyon ng orkestra ng 50 + o kaya tao? Ko kinuha isang medyo simpleng diskarte at simulan dito. At ako 2 tao tumayo at ko lang paghambingin ang mga ito, at pagkatapos ay sinasabi ko sa sinumang ay bahagyang mas maikli, "Okay, umupo ka pababa," at ako pagpunta sa tandaan na taller tao. Pagkatapos ko ulitin, ulitin, ulitin, at mag-hang ko sa ang pinakamataas na tao hanggang sa mahanap ko ay may bahagyang taller kaysa sa kanila, sa puntong ang bahagyang mas maikli tao ay pagkatapos ay umupo. Ngunit sa na algorithm sa seksyon na ito ng orkestra, kung may n mo, kung gaano karaming mga hakbang na algorithm pagpunta sa tumagal? >> [Mag-aaral] N. 

Ito ay pagpunta sa n, kanan, dahil sa ang pinakamasama kaso, kaya na magsalita, ang pinakamataas na tao ay ang huling tao na nakukuha ko sa pamamagitan ng random alat. Kaya sa ang pinakamasama kaso, ang tumatakbo oras ng algorithm na linear, n, kung saan ang n ay ang kabuuang bilang ng mga tao sa espasyo, ang laki ng problema. Paano ang tungkol sa algorithm? Ang katotohanan na mo ang lahat ng nakatayo up at pagkatapos ay muli kalahati ng sa iyo nakaupo, nakaupo pababa ang kalahati ng sa iyo, ang kalahati ng nakaupo. Gaano karaming mga hakbang ang dapat na kinuha kung may n mo dito? [Mag-aaral] N log n. >> Iyon ay magiging mas masahol pa. Mag-log n. 

Kaya mag-log n, kahit na hindi mo pa masyadong matandaan kung ano ang logarithm ng, sa ngayon, Pinahahalagahan na ito ay nauugnay sa paanuman ito paghati at paghati at paghati. Ito ay hindi isang kadahilanan ng 2. Ito ay maaaring maging isang kadahilanan ng 3. Ngunit ang pag-uulit ng parehong uri ng mga kadahilanan tulad na ang laki ng problema ng mga pagsisimula dito ngunit pagkatapos agad pupunta dito, pagkatapos dito, pagkatapos dito, pagkatapos dito. Hindi ka pagkuha ng maliit na kagat ng problema, talagang ka pagpuputol layo ito sa isang malaking nahulog mabilis na sumalakay sa bawat oras. Kaya nagkaroon kami 50 tao, pagkatapos 25, pagkatapos ay 12 ½ o 13 tao nakatayo, 6 ½ at iba pa hanggang sa wakas lamang Andrew ay pakaliwa standing. Kaya kami ay pagpunta sa tumawag na log ng n, at maaari kang maisalarawan ito tulad ng sumusunod. Maalala muli ang larawan dito kung saan ang isang linear na algorithm ay tulad ng pulang linya doon, ang dilaw na linya ay ang pagbilang ng 2s algorithm na ginamit namin para sa pagbibilang ng mga mag-aaral sa nakaraan, ngunit ngayon ang banal na Kopita upang manatili ito berdeng linya kung saan kung Dinoble namin ang bilang ng mga tao sa seksyon ng orkestra o sinabi, impiyerno, sabihin lahat ng tao sa buong room tumayo, hindi isang malaking deal dahil namin halos double kung gaano karaming mga tao ang pababa dito, 1 pang-ulit, hindi isang problema. 

Aming natagpuan Andrew o ng sinumang mangyayari upang maging taller kaysa sa Andrew sa mezzanine o sa balkonahe. Kaya ito simpleng ideya na kinuha namin kaya magkano para sa ipinagkaloob sa isang libro ng telepono, mapagtanto na may maraming iba't ibang mga lugar kung saan maaari naming mag-aplay ang mga ito. Lamang sa sampal unang ilang magulong pag-uusap - aktwal na, sa halip na magulong pag-uusap, hayaan mo akong pumunta sa ang larawang ito dito. Sa ngayon usapan natin ang tungkol sa n at n / 2 at pagkatapos ay mag-log ng n, ngunit maaari naming tiyak na darating sa, bilang ay namin sa kabuuan ng semestre, iba pang uri ng mga mathematical formula upang ilarawan ang pangkalahatang paniwala ng tumatakbo oras. Mga ito ay out ng konteksto sa ngayon dahil gagamitin namin ang bago mahaba algorithm na mga aktwal na kumakatawan sa. 

Ngunit mapansin dito linear n linya, tuwid na linya, ay talagang napakababa na tumuturo sa ngayon. Na ang uri ng isang optical ilusyon na namin baguhin lamang kung ano ang x axis kumakatawan at ang y axis, at maaari naming gumawa ng isang tuwid na linya punto sa anumang direksyon na gusto namin. Ngunit ang dahilan na ito kaya tila flat ngayon ay dahil kailangan namin upang gumawa ng room sa graph na ito para sa magkano ang mas mabagal na mga panahon ng pagtakbo. Sa ngayon, alam na may ilang mga medyo masamang algorithm sa buhay, ang ilan sa hindi tumagal ng n hakbang, o mas mahusay pa, mag-log n hakbang ngunit higit pa. Kaya sa itaas ng linya n dito sa ibaba paunawa n beses log ng n, at kami na makita kung ano ito ay nangangahulugan bago mahaba. Sa itaas na n squared, at hindi namin nakita ang anumang n squared algorithm ngunit hindi namin tungkol sa. At na mukhang ganap na hindi maayos. May 2 sa n, isang bagay pagpaparami, na nararamdaman kahit na mas masahol pa. At pa, pausisa, pagkatapos may n nakakubo, na kung ikaw ay ang uri ng iniisip magpatuloy, kung uri ng gawin ang matematika, 2 sa n aktwal na nagiging mas straighter, mas mataas kaysa sa n nakakubo kung titingnan mo ang mga axes malayo sapat ang. Kaya mapapansin ngayon mga axes ay mang 2 sa 10 sa axis x. 

At kung ano ang na ibig sabihin nito? Iyon ay nangangahulugang ang 2 tao sa 10 tao sa kuwarto. Na ang lahat ng x ay nangangahulugan: laki ng problema, anumang konteksto ay. At vertical axis ngayon ang bilang ng mga segundo o bilang ng mga hakbang - ilang yunit ng oras. Ngunit mapansin na 0 hanggang 60 at 0 hanggang 10. Ngunit kung namin uri ng zoom out, tulad ng kapangyarihan sa Excel o ilang charting software, at kami ng hanggang sa 200,000, mapapansin na may isang bagay tulad ng 2 sa n ay pagpunta sa ganap na mapuspos ang panahon ng pagtakbo ng n squared, nakakubo n, n log n - lahat ng namin ang uusapang tungkol sa gayon malayo. At pa catch ay kapag nagsimula ka ng pakikipag-usap tungkol sa mga bagay tulad ng Facebook kung saan ka maraming, maraming, maraming mga tao na lahat ng interconnected, mo na n ng mga tao, bawat isa sa kanino ay maaaring magkaroon ng maraming mga bilang n kaibigan kung ang lahat ay uri ng pare sa mundo, mahusay na n beses n na, kaya na n squared posibleng pagkakaibigan, ng hindi bababa sa 1 direksyon, n squared posibleng pagkakaibigan. Kaya na nagmumungkahi na naghahanap ng social graph ng Facebook, kaya na magsalita, maaaring magsimula na ipinahayag sa mga ganitong uri ng mga formula. 

Susubukan naming bumalik at gawin itong mas kongkreto, ngunit sa ngayon, ang mga layunin para sa susunod na maraming linggo ay upang matiyak na hindi pumunta tungkol sa pagpapatupad ng mga algorithm o code na nagtatapos up ng paglalaan ng mas maraming oras bilang isang bagay tulad nito. Ngunit ang kamangha-manghang bagay tungkol sa computer science kung magpapatuloy ka sa field na ito pagkuha ng mga klase tulad ng CS121, CS124, pareho ng mga kurso sa teorya, na may aktwal na ilang mga problema na umiiral sa mundong ito na sa panimula, kasing layo ng alam namin, hindi maaaring malutas ang anumang mas mabilis kaysa sa pinakamasama sa mga graph na aktwal na nagmumungkahi. Kaya may maraming ng mga bukas na mga problema sa mundong ito upang gawin mas mas mahusay kaysa sa mga tao ay may sa gayon malayo. 

Kaya ipaalam sa magsimula sa halimbawang ito. Nakakita kami Sean pakikibaka na ito sa camera, ang lahat ng masyadong awkwardly sa video. Ngunit katotohanan ay kapag Sean ay tasked sa paghanap sa isang board tulad ito ang numero 7, isipin ang na sinabi ko na, "May isang lugar sa likod ng mga piraso ng papel o puting pinto "Ang bilang 7. Sean, hanapin ito para sa amin." At ito ay kamangha-mangha mahirap upang panoorin dahil talagang siya ay struggling na may ganitong problema. Ngunit katotohanan ay Sean ginawa pati na rin ang sinuman sa kuwarto ay maaaring magkaroon ng tapos. Kinuha niya ang kaunti na kaysa sa isang tipikal na tao ay maaaring magkaroon ng, ngunit ipinapalagay na siya na may ilang nanlilinlang sa problemang ito, siya ipinapalagay na siya ay nawawala ng isang bagay. At hindi ito makatulong na daan-daang mga mata ay nadadala sa kanya. 

Ngunit katotohanan ay kung ang input sa problema ng grupo ng mga random na numero at ikaw ay hiniling upang mahanap ang 1 tulad bilang, ang pinakamahusay na maaari mong gawin ay linear paghahanap. Magsimula sa kaliwa, ilipat sa kanan, o magsimula sa kanan, ilipat sa kaliwa. Retroactive, maaari naming pag-iisip, "Sean, bakit hindi mo lamang magsimula mula sa kabilang dulo?" Well, 7 maaaring tulad ng madaling naging dito random, ngunit sadyang ako ilagay ito doon dahil naisip ko hindi siya pagpunta sa magsimula sa dulo. Kaya ko uri ng manipulahin ang sitwasyon, ngunit sa pamamagitan ng random na pagkakataon 7 maaaring saanman. Kaya simula mula sa kanang dulo maaaring mas mahusay na pagkatapos, ngunit kung ano ang kung ang mga susunod na taon ilipat ko 7 sa ibang lugar? Na hindi sa panimula bagong solusyon sa problema - nagsisimula mula sa 1 pagtatapos o ang iba pang mga - kapag ikaw ay ibinigay na walang iba pang mga pagpapalagay. Kaya Sean nagsimula naghahanap sa pamamagitan ng numero at sinabi niya, "5. Iyon ay hindi dito." Pagkatapos siya nagpunta dito at nakita 19, pagkatapos siya naka-pause para sa mga 20 segundo, pagkatapos ay binuksan niya ito para sa 13, at pagkatapos nito ay naging maliwanag na may ay hindi mukhang isang pattern dito. Ito ay hindi 1, 2, 3, 4 o ang tulad ng. May mga gaps sa mga numero, na hindi nakatulong. At masyadong, ang katotohanan na ginamit ko ang mga murang mga piraso ng papel upang masakop ang ang mga numero aktwal na sinadya, dahil kung inalis ko ang lahat ng mga piraso ng papel, karamihan sa atin, Sean kasama, marahil ay na glanced uri ng macroscopically sa pisara at sinabing, "Oh, 7 ay malinaw naman doon." Ginawa namin ito agad. 

At na maaaring ang paraan gumagana ang utak ng tao sa ilang mga lawak, ngunit sa katotohanan, ang kanyang mga mata o isip ay marahil skimming ang mga numero mula sa karapatan sa kaliwa, sa kaliwa sa kanan, gitna sa ang - ay isang bagay na nangyayari sa physiologically tulad na ito nadama tulad ng ito ay nangyayari agad, ngunit logro ay kahit na panloob na may ilang mga uri ng pamamaraan sa paghahanap ng 7. At sa katunayan, ngayon na kami ay pakikipag-usap tungkol sa array at data istraktura at memory sa loob ng isang computer, ang tanging bagay na namin mga tao ay maaaring gawin ay tingnan ang mga indibidwal na lokasyon sa memorya 1 sa isang pagkakataon. 

Kaya ang bawat iba pang lokasyon ay maaaring pati na rin ay sakop na may ilang piraso ng papel dahil hindi namin makita ang anumang paraan. Maaari lamang kami gawin ang 1 bagay sa isang pagkakataon. Kaya sa kasong ito, sa kaso ng Sean ng, kami nagpunta dito at pagkatapos namin nagpunta dito at pagkatapos namin nagpunta dito, dito, dito, dito, nakuha ko matalino sa katapusan at uri ng nilaktawan ang isang ito mang at natagpuan 7 doon. Ito ay hindi partikular na espesyal. Masyadong ito ay sira. Ngunit siya sa wakas nahanap na 7. Ngunit ngayon takeaway talaga na ang pinakamahusay na maaari mong gawin kapag bibigyan ng walang impormasyon maliban sa random na pinagsunod-sunod numero ay upang simulan mula sa kaliwa o magsimula mula sa kanan. O ano ba, maaari mong random buksan ang pinto, ngunit kahit na pagkatapos kung ano ang ibig sabihin na random? Well, gusto namin upang gawing pormal sa paanuman kung ano ang ibig sabihin nito upang simulan dito, pagkatapos ay pumunta dito, pagkatapos ay pumunta dito. Sean ginawa dakilang, at ito ay lamang masaya upang panoorin. Paano kung sa halip naming baguhin ang problema ng kaunti at dalhin Sean sa taong ito, kung kalooban mo? Gusto sinuman maging komportable paparating na sa stage at sa paglutas ng isang problema na bahagyang naiiba at lumilitaw sa camera? 

Natin pumunta higit sa orkestra dahil ikaw guys ay lubos na kasangkot ngayon na. Paano tungkol sa pink, sa sumbrero? Halika sa down na. Ano ang iyong pangalan? >> Alex. >> Alex. Okay. Kaya Alex ay Sean sa taong ito at ay lilitaw sa susunod na ilang mga taon halaga ng CS50 aralin. Alex, Masaya akong makilala kayo. >> Masaya akong makilala kayo masyadong. Ang hamon sa kamay para sa iyo na mayroon kang ang bit madali na ako na nagsasabi sa iyo ang parehong numero dito, ngunit sila ngayon ay pinagsunod-sunod. Kaya ngayon ang iyong layunin ay upang mahanap ang numero 7. At aktwal na, dapat naming makuha ito - you're uri ng pagdaraya, tulad ng isang computer gagawin hindi, sa pamamagitan ng pagtingin sa kung ano ang mga numero ay ng ilang sandali ang nakalipas. Gamit ang yeso ito ay hindi aktwal na pagpunta upang matulungan ang lahat na mga magkano, ngunit sabihin magpanggap na hindi mo alam kung ano ang orihinal na array ay. Ang alam mo ngayon ay na mayroon kang isang array ng mga pinagsunod-sunod na mga numero na maaaring magkaroon ng mga gaps sa pagitan ng mga ito, at ang iyong layunin ay upang mahanap ang numero 7. Paano mo ire, ng makatuwirang tao, pumunta tungkol sa paghahanap ang bilang 7? 

Pumunta mula sa mababa sa mataas na? >> Okay. Pumunta sa mababa sa mataas na. At hindi pilasin ito. Sabihin lang iangat ang mga ito upang maaari naming muling gamitin ang mga ito. Okay, sa gayon 1. Maghintay. Bago patuloy mong pagpunta, na 1, malinaw na mali. Kaya kung ano ang nangyayari sa pamamagitan ng iyong isip sa tabi? Ano ang iyong susunod na ilipat? Ang susunod na isa. >> Okay. Ang susunod na isa. Mabuti. 3, kaya hindi tama. Ano ang iyong susunod na ilipat? Manatiling dumalo. >> Lahat ng karapatan. Manatiling dumalo. 5. Kaya panatilihin ang dumalo, at ipaalam sa akin na ibigay mo ito para sa salinlahi sa hinaharap. 7. >> Mahusay. Napakabuti. Nakahanap ng ang bilang 7. [Palakpakan] Kaya na ay mabuti, ngunit Sean masyadong natagpuan ang numero 7. At magtalo ko na hindi mo talaga pinagsamantalahan ito karagdagang piraso ng impormasyon, kung saan ay na ang mga bilang na ito ay pinagsunod-sunod. Upang maaari naming gawin mas mahusay? Anumang mga mungkahi dito? Oo, sa likod. [Mag-aaral] binary paghahanap. >> Wala akong palagay kung ano ang binary paghahanap. 

[Mag-aaral] Magsimula sa gitna. >> Magsimula sa gitna. Okay. Kaya sabihin makita kung maaari naming makakuha ng may. Kaya kung sa halip ka Sinabi ng pagsisimula mula sa gitna, sige at buksan ang gitnang pinto. Mayroong 8 sa kanila, kaya ka mang pumili sa isa bahagyang sa kaliwa o sa kanan. Okay. 7! [Palakpakan] Tunay na magaling. Okay, ngunit kung saan ay namin pagpunta na ito? Sabihin ipagpalagay lamang sa basagin ang kurbatang mo ay nagsimula dito dahil na pantay maaaring nangyari pati na rin. Nangyari lang namin malaman na 7 ay naroon. Kaya ito ay 13. Kaya kung sila ay pinagsunod-sunod at lang namin na nagsimula sa gitna, kung ano ang pinakamainam na susunod na ilipat ay? Pumunta sa kaliwa. At kaya dito ay muli ang halimbawa ng aklat ng telepono. Kung 13 dito at alam namin ang listahan ay pinagsunod-sunod, pagkatapos ang lahat ng mga piraso ng papel ay hindi kawili-wili sa amin ngayon dahil alam namin na na 7 ay dapat na sa kaliwa kung ang mga numero ay pinagsunod-sunod at nakita namin 13. 

Kaya kung ano ang iyong susunod na ilipat dito? >> Pumunta sa kaliwa. >> Okay, mabuti. Kaya pumunta sa kaliwa, at - maghintay, hey, hey, hey. Na Pandaraya. Kaya mo nahanap na 7, ngunit kung ano ang algorithm na inilapat lang namin? Magsimula sa gitna. >> Mahusay. Kaya kung ano ang lohikal na extension ng na parehong ideya? Oh, para lamang sa mga. >> Mismong. >> Kaya sisimulan ko dito. >> Mahusay. Kaya ngayon namin nagpunta bahagyang sa kaliwa muli. Ito ay 3. Ngunit ngayon ang kawili-wiling takeaway ay na gawin ang isa hindi mo pakialam tungkol sa? Mga 2. >> Mga 2. Kaya ngayon ito ay maaaring pumunta ang layo, ang isang ito ay maaaring pumunta ang layo. Ngayon ang problema na 8 pagkatapos ay laki 4 ngayon laki 2. Kami ay nakakakuha ng medyo malapit. Muli, pumunta sa gitna ng mga 2 elemento. 

Okay. Kaya ito uri ng kapus-palad na ngayon laging kami ay pagpunta sa kaliwa dahil hindi namin rounding pababa. Ngunit iyon lamang ang fine dahil na namin ngayon magtapon ito ang layo at lahat ng iba pa, na nag-iiwan sa amin sa pamamagitan lamang ng 7. Natin bigyan ng isang ikot ng papuri. Natagpuan namin 7 muli. [Palakpakan] Okay. Sigurado. Ibaba sa para sa lamang 1 pang pangalawang. Kahit na ang susunod na uri ng proseso ng kinuha ng kaunti na kaysa sa nadama namin gagawin ito, lantaran, ang iyong unang instincts ay ang pinakamahusay na, i-right? Natagpuan namin 7 agad. Ngunit nais naming natagpuan 7 mas mabilis, kahit na ano, sa halimbawang ito kumpara sa isang ito dahil kung ang mga numero ay pinagsunod-sunod lahat, tulad ng mga pahina sa isang libro ng telepono, Maaari mo katunayan pagpura-pirasuhin ang kalahati ng problema ang muli at muli at muli. At hindi pa madali upang makita ito may 8 numero lamang kumpara sa 1,000 mga pahina ng libro ng telepono kung saan mo ba talagang makita ang mga ito nang biswal, ngunit sa kasong ito dito kapag Sean ay naghahanap para sa 7, kung gaano karaming mga hakbang sa pinakamalala kaso ay kinuha sa kanya? >> [Mag-aaral] 7. 7 sa pinakamalala kaso. Well, sa ang pinakamasama kaso hindi 7 kung may 8 pinto dito. Kinuha kanya 8 hakbang. 

Kaya kung may n pintuan, maaaring ito kinuha Sean ng ilang taon na ang nakakaraan n hakbang. Ngayon, sa iyong kaso, Alex, ibinigay na ang mga bilang na ito ay pinagsunod-sunod - at maaari naming uri ng magpakilala ito mula sa kung saan kami sa gayon ay malayo sa kuwentong ito - ano ang oras ng paggana ng mas intelligent na algorithm Alex ng simula sa gitna at pagkatapos ay paulit-ulit na? [Mag-aaral] 3. >> Kaya pagpunta sa 3, halos, kung pumunta ka 8-4 sa 2 sa 1. Kaya 3 hakbang o, mas pangkalahatang paraan, na ang log n muli. Anumang oras na naka paghati at paghati at paghati at paghati, na ang isang pagpapahayag ng ito ideya ng log n. At kaya na kinuha mo lamang ang 3 hakbang, at sa katunayan ito ginawa sabay-sabay namin binuksan ang pinto paghati at paghati, kung saan ito ay kinuha Sean ilang 7 o 8 hakbang. Kaya salamat sa iyo para sa pagiging sa amin sa taong ito. >> Salamat. Nice meeting mo. Salamat sa Alex. >> Gayundin. [Palakpakan] 

Ano ang pagkatapos ay ang tunay na implikasyon ng ito? Ngayon isipin na hindi 8 pintuan, kung saan, lantaran, ang lahat ng sa atin ay maaaring makahanap ng isang bagay sa likod ng 8 pinto medyo mabilis sa pamamagitan lamang ng pansiwang ang mga piraso ng papel at pagpunta sa aming mga instincts. Ngunit ano kung ito ay isang milyong mga pinto? Ano kung ito ay 4 bilyong pinto? Sa kaso ng 4 bilyong pintuan, ikaw talaga ay pagpunta sa nais upang pumunta sa Alex ng algorithm, binary paghahanap bilang namin simulan ang pagtawag ito o hatiin at lupigin, mas pangkalahatang, kung saan patuloy mong paghati at paghati ang problema, dahil kung mayroon kang 4 bilyong mga pintuan, kung gaano karaming beses maaari mong pagpura-pirasuhin 4 bilyong sa kalahati? [Mag-aaral] 32. >> Ito ang aktwal na 32. Maaari kang gumawa ito sa isang piraso ng papel o sa iyong ulo. Pumunta ka 4 bilyong sa 2 bilyong sa 1 bilyong sa kalahating bilyon, sa 250 milyon, tuldok, tuldok, tuldok. At kung gagawin mo ang matematika, ka pagpunta sa katunayan makakuha ng 32, at na aktwal na nauugnay sa computer science dahil karaniwang namin mabibilang sa kapangyarihan ng 2. 2 sa 32 ay mangyayari na 4 bilyong. Kaya may maraming ng kaugnayan sa mga ganitong uri ng kapangyarihan ng 2 sa computer science. 

Ngunit ano ang tungkol sa 8 bilyong? Gaano karaming mga hakbang ay na pagpunta sa tumagal kung may 8 bilyong pinto? [Mag-aaral] 33. >> Kaya 33. Paano kung may 16 bilyong pinto? Gaano karaming mga hakbang ay na pagpunta sa tumagal? [Mag-aaral] 34. >> 34. Kami maaaring uri ng magpatuloy ito hanggang sa pagkainis. Ngunit na ang isang malakas na bagay. Maaari kang ipakilala ang mga bilyun-bilyong ng higit pang mga input sa iyong problema ngunit, walang sang-ayon, mo lang 1 karagdagang kagat nito at samakatuwid ay nagbibigay sa amin ng isang bagay tulad ng binary paghahanap o hatiin at lupigin, mas pangkalahatan. Ngunit ako uri ng Pandaraya dito, i-right? Sa kaso ng Alex ng algorithm, siya ay isang kalamangan sa Sean. Alam niya na ang mga numerong ito ay pinagsunod-sunod, ngunit Alex ay hindi upang pag-uri-uriin ang mga ito sarili. Ako nang maaga ay dumating hanggang sa pisara at uri ng natiyak na iginuhit ko ang lahat ng ito sa pinagsunod-sunod pagkakasunod-sunod, pagkatapos ko sakop ito sa papel. Ngunit kung magkano ang trabaho ay na dalhin ako? Kung tayo ay nagsimula sa mga numerong ito sa ilang tila random na pagkakasunod-sunod - sa kasong ito mga simple numero, 1 hanggang 8 dito - kung paano namin pumunta tungkol sa pag-uuri-uri ng mga halaga? Kung ikaw ay isang tao na binigyan ng gawaing ito, kung anong uri ng intuitive diskarte ang nais mong gawin sa pag-uuri-uri ng isang buong grupo ng mga numero? Ang mga bagay na ito ay inilatag bilang piraso ng puzzle. Oo. 

[Mag-aaral] Gusto ko tumagal ng bawat numero at ihambing ang mga ito sa bawat isa at patuloy na pagpunta sa kaliwa. >> Okay, mabuti. Kaya tumagal ng bawat numero, ihambing ito sa isa sa tabi nito, at pagkatapos lamang panatilihin ang paglipat sa kahabaan ng listahan ng uri ng rejiggering ng mga bagay bilang kang pumunta. Kaya dito mayroon kaming isang pagkakataon para sa mga marahil ng ilang higit pang mga tao upang makakuha ng kasangkot. Ba namin 8 higit pang mga boluntaryo na ibigin upang makabuo? Ang isang maliit na mas mababa presyon dahil sa iyo na hindi lamang ang. 1, 2, 3, 4, 5, 6, 7, 8. Halika sa down na. Mong guys na ang mga numero 1 hanggang 8. Natin makita kung hindi namin gawin ito pag-uuri para sa Alex karamihan sa parehong paraan na ginawa ko ito nang maaga. 1, 2, 3, 4. Sige at kung gagawin mo, linya sa entablado sa pagitan ng musika stand at sa akin dito sa parehong pagkakasunud-sunod bilang ng slide sa screen. Uh-oh. Makikipagtulungan kami sa susunod na halimbawa. Oh, maghintay, maghintay. Narito kami. Maghintay. Ang susunod na halimbawa ay sa ngayon. Dito ka pumunta. Numero 8. Halika sa up. Ayos lang. -Uri-uriin ang sarili ayon sa. Slide ang ng kaunti lamang sa bahagi ng musika tumayo dito. Kaya mayroon kaming 4, 2, 6 - makakuha ng doon, sa paglipas dito, doon - 3. Oo. Okay. Pumunta ka sa paglipas dito. Hindi, manatili doon. Oo, doon. No ako mali. Doon. Okay, napakabuti. Okay. Kaya ngayon sabihin-uri-uriin ang mga ito sa isang pagtaas ng order. 

Paano ko pumunta tungkol sa paggawa nito? Ang algorithm na iminungkahi ng ilang sandali ang nakalipas ay bakit hindi lang namin ihambing ang mga tao na uri ng sa tabi ng bawat isa at pagkatapos ay ayusin ang anumang mga pagkakamali, paglipat mula kaliwa hanggang kanang. Kaya dito mayroon kaming 4 at 2, malinaw naman sira. Sabihin mong magpalit. Okay. Kaya ako ngayon upang ilipat ang linya. 4 at 6, nope. [Tawa] 6 at 8, medyo magandang. 8 at 1, ipaalam sa akin mong magpalit guys. Ayos lang. Kaya ng 8 at 3, mong magpalit guys. 8 at 7, ipaalam sa akin mong magpalit guys. 5 at 8, mahusay. Ako magbibigay sa iyo ng isang pinagsunod-sunod na listahan. Ayos lang. Kaya hindi pa. Ngunit ito ay mas mahusay dahil ang mas malaking mga numero - kaso sa point 8 - na uri ng bubbled mula sa kaliwa sa kanan. Kaya Nakatanggap ako 1 sa kanila karapatan, ngunit ito nararamdaman tulad ng ito ay hindi pa malutas ang problema. 

Kaya kung ano ang gusto mong ipanukala ang ginagawa namin susunod? >> [Mag-aaral] Panatilihin gawin ito. >> Naming patuloy na gawin ito. At Napagtanto, muli, kami ng mga bagay sa pamamagitan ng lamang pagkakaroon ng lahat ng mga tao uri ng intelligently magsagawa ang kanilang mga sarili batay sa na larawan, ngunit ngayon ay mayroon kaming mas sistema. Mayroon kaming algorithmic tungkol dito na parang kami ay sumusulat code - sa kasong ito pandiwang pseudocode. Kaya ipaalam sa akin lamang subukan na muli. Na nagtrabaho medyo na rin. Hindi ito malutas ito. Ngunit kapag pagdudahan ito, lamang na subukan at subukan muli. Kaya sa 2 at 4, hindi makakatulong ito. 4 at 6. Ah! 6 at 1, bahagyang mas mahusay na ngayon. 6 at 3, ang mahusay. 6 at 7, 7 at 5, 7 at 8, mabuti. At alam mo, ang maaari kong marahil huwag pansinin 8 ngayon dahil siya sa dulo ng listahan. Siguro hindi kami mag-alala tungkol sa isang tao na pagpunta nakaraang kanya. Ngunit sabihin makita kung na ang isang ligtas na palagay. Ngayon ang listahan - mapahamak - hindi pinagsunod-sunod. Natin subukan ito muli. Kaya 2 at 4, 4 at 1, 4 at 3. 4 at 6, mabuti. 6 at 5, mabuti. 6, 7, at 8, mabuti. Ngunit paunawa, maaari ko lang hihinto dito ngayon at hihinto dito ngayon? [Mag-aaral] Oo. >> Oo? Paano kung isa sa inyo ay ang bilang 9 lahat ng paraan doon? Nito ay pinagsunod-sunod. >> Mahusay. Na-pinagsunod-sunod sa unang pagkakataon sa paligid. Mabuti. Kaya sabihin bumalik muli. Humihingi kami ng halos doon. 1 at 2, 2 at 3, 3 at 4, 4 at 5, 5 at 6, 6 at 7, 7 at 8. 

Tapos ako na ngayon ngunit, muli, ako computer na maaari lamang gawin kung ano ang ako nasabihan na gawin, at ang aking lamang gunita ngayon ay na aktwal na ako lang ang isang bit ng trabaho. Isang bagay ay nagbago dito. Kaya hindi ko na technically nakumpirma biswal o algorithm na ang listahan na ito ay sa katunayan pinagsunod-sunod. Kaya para sa mabuting panukala, lamang anal tungkol sa, sabihin gawin ito 1 pang oras. Kaya 1 at 2, 2 at 3, 3 at 4. At alam mo kung ano? Para lamang sa magandang sukatan, ako pagpunta sa subaybayan sa aking kamay sa oras na ito kung gaano karaming mga swaps gumawa ko lang kaya na alam ko kung gaano kahalaga gumagana ang aktwal na nagawa ko na. 3 at 4, 4 at 5, 5 at 6, 6 at 7, 7 at 8. Walang swaps. Kaya ngayon Gusto ko lehitimong isang gagong tao upang gawin ito muli dahil kung ginawa ko walang trabaho sa pamamagitan ng ito pass ng mga tao, pagkatapos ay malinaw na pagpunta sa mangyari muli kung wala sa kanila ang uri ng random adversarially paglipat sa kanilang sarili sa paligid. Kaya ngayon maaari kong itigil. Ngayon sabihin tanungin ang tanong, kung magkano ang trabaho ay ito aktwal na dalhin ako? Gaano karaming mga hakbang na? >> N squared. Oo, kaya n squared. Saan mo makukuha n squared mula? Mayroon kang suriin ang bawat num - May n numero, at mayroon kang suriin ang bawat numero sa iba pang mga numero ng n. Mabuti. >> Kaya ito n squared. >> Mahusay. 

Kaya ito nararamdaman tulad ng ito nang mahusay n squared, i-right? Mayroong n sa mga guys, 8 partikular sa kasong ito, ngunit sa bawat oras na pinuntahan ko sa pamamagitan ng listahang ito na ako ay paghahambing ng unang tao laban sa segundo, ang ikalawang laban sa ikatlong muli at muli at muli, at kapag Nakatanggap ako sa dulo, kung ano ang gagawin ko? Redid ko ito. Kaya kung namin ng tuntuning panlahat ang paliwanag na ito, namin n tao at ako paggawa, malinaw naman, 8 hakbang, n hakbang, sa bawat oras na pumunta ko sa pamamagitan ng algorithm. Ngunit kung gaano karaming beses sa pinakamalala kaso ko upang pumunta sa pamamagitan ng listahan ng mga tao? [Mag-aaral] N beses. >> Marahil n, kanan, dahil sa ang pinakamasama kaso, kung ano ang marahil ang pinakamasama arrangement kaso ng mga guys mula sa makakuha-pumunta? Kung ganap na sila ay reverse ang pagkakasunod-sunod dahil lamang ipagpalagay itak, let's - Ano ang iyong pangalan? >> Bowen. Bowen. Okay. Kaya Bowen, ay sa higit dito para sa sandali lamang. 

Ipagpalagay na ang Bowen dito sa simula ng algorithm, at hindi namin alam kung ano ang iba ay, ngunit Bowen dito, ayon sa algorithm na ito - at kung gusto mo lang maglakad sa akin - ay pagpunta sa bubble up, tulad ng ginawa niya sa unang pagkakataon sa paligid, ang lahat ng mga paraan sa dulo. Ngunit ipagpalagay na ang mga tao sa tabi Bowen ay ang bilang 7. Mayroon akong upang bumalik at kumuha ng numero 7, na nangangahulugan na mayroon akong pumunta ang lahat ng mga paraan pabalik dito. Ngayon ay mayroon akong na magkaroon na parehong paglalakad sa mga tao na bilang 7. Ngunit ano kung ang bilang 6 ay susunod sa kanya pati na rin? Pagkatapos Mayroon akong upang bumalik at makakuha ng 6. Kaya muli, sa bawat pag-ulit ng loop na ito ako ng pakikipag-usap sa bawat isa ng n tao, at maaari ba akong magkaroon upang gumawa ng n sa mga strolls upang matiyak ako kumukuha lahat ng pinakamalaking elemento bumalik at bumalik at bumalik sa pinakadulo ng listahan. Kaya n bagay n beses lamang n beses n o n squared. 

Kaya dito na mayroon kami ng isang algorithm na hindi na n, na hindi na log n, ito ay aktwal na mas masahol pa kaysa sa anumang ginawa namin bago. Kaya Alex uri ng nakuha masuwerteng na ginawa ko ang lahat ng trabaho na tila hanggang harap para sa kanyang, lahat ng mahal trabaho, sa gayon na maaaring siya mga bisita sa ito binary search algorithm, na log ng n. Ngunit ito ay pare-pareho sa Lunes ng tema. Ibinigay namin ng kaunti ng mas maraming espasyo, ginamit namin sa higit pang mga bit, upang mapabilis ang aming tumatakbo oras. Kaya tulad ng ito kalakalan-off sa pagitan ng oras at espasyo, maaaring may din lamang kalakalan-offs sa pagitan ng oras na ginugol front uri ng pagkuha ng mga bagay handa upang pumunta at aktwal na execute ng isang algorithm tulad ng paghahanap. Natin subukan ang isa pa. Kung ikaw guys ay hindi tututol lang mabilis rearranging sarili upang tumugma na muli, ipaalam sa subukan ang isang bagay na bahagyang naiiba sa kung saan ito ay hindi pa na simple bilang lang ayusin ang lahat ng mga pairwise pagkakamali, na super intuitive. Natin sa halip ng kaunti pa sinadya at gawin ito. Ito masyadong Gusto ko ipanukala ay maaaring medyo madaling maunawaan. 

Natin piliin ang pinakamaliit na tao mula sa listahan sa muli at muli. Kaya dito namin pumunta. 4, ikaw ay ang pinakamaliit na tao sa gayon Nakita ko na sa ngayon, kaya ako pagpunta sa itak tandaan na sa pamamagitan lamang ng pagturo sa sa ngayon. 2. Ooh! Kalimutan ang tungkol sa numero 4. Ko lang nahanap na ang bagong pinakamaliit na elemento sa listahang ito. Ako pagpunta sa uri ng tandaan na. 6, 8. Ooh! 1. Paalam na po. Kaya ngayon ako pagpunta upang matandaan ang numero 1. Alam namin na 1 ay ang pinakamaliit, ngunit ako sa computer. Paano kung ang isang 0? Paano kung may -1? Mayroon akong upang panatilihin ang pagpunta. Kaya 3, 7, 5, nope. Okay. Kaya ang numero 1 ay ang pinakamaliit. Hayaan akong pumili mula sa listahan - we'll pumunta sa ganitong paraan - at ilagay mo mang sa simula ng listahan. Ngayon, maghintay ng isang minuto. Ako uri ng ginulangan. Kung ang mga guys na ito ay kumakatawan hindi isang listahan ng 8 tao ngunit isang array, 8 chunks ng magkadikit memory - tututol ba kayo stepping pabalik para sa sandali lamang? Mayroon talagang walang puwang para sa iyo karapatan dito. Kaya kung paano namin gumawa ng puwang para sa - kung ano ang iyong pangalan? >> Sammy. >> Sammy. Paano namin gumawa ng espasyo para sa Sammy? 

Ilipat namin n na bago sa akin. >> Okay. Kaya maaari naming ilipat ang n mga taong bago sa kanya, kaya kung guys gusto 1 sinadya, dramatic hakbang sa kaliwa. Ang lahat ng mga ito ay ginawa na sa pagkakaisa, ngunit huling beses ko sinulat ni ilang code, hindi ka maaaring ayusin ng ilipat ang maraming bagay nang sabay-sabay. Kami maaaring gawin ito sa isang loop, paglipat ng lahat nang isang beses sa isang oras. Kaya kung ikaw guys ay hindi tututol stepping pabalik sa kanan, at Sammy, kung maaari mong hakbang pabalik dahil mayroon pa rin walang room para sa iyo, ngayon sabihin gawin ito. Kung saan ay Sammy ng ilang sandali ang nakalipas? Doon. Kaya may agwat doon. Kaya maaari mong ilipat sa Sammy ng lugar. Ngayon susunod na tao at ngayon susunod na tao, susunod na tao na ngayon. Ngayon kami ay may kuwarto para sa Sammy. Ngayon, isang tao mula sa madla - na ay mabuti, na tama, nadama ito ng kaunti matagal - kung ano ang mas mabilis? Oo. [Mag-aaral] Ang isang bagong array? >> Ano iyan? >> [Mag-aaral] Ang isang bagong array? >> Okay, mabuti. 

Kaya pare-pareho sa ang tema na ito ng kalakalan-offs, bakit hindi ko lang gumawa ng isang bagong array  at pagkatapos Sammy ay swimming sa puwang sa harap ng mga taong ito, halimbawa, at maaari naming lamang simulan ang pagpuno ng isang bagong array kabuuan. Na masyadong ay gumagana. Ngunit hindi ako interesado sa paggastos mas maraming espasyo ngayon. Ano ang isa pang diskarte? [Mag-aaral] Swap. >> Okay. Ma lang namin magpalitan ng mga 2 guys. Ano ang iyong pangalan? Mario. >> Mario. Kaya Mario, ikaw ay kasalukuyang dito. Sammy, maaari mong i-back up para sa isang sandali lamang? Mario ay dito. Wala kaming kuwarto para sa iyo na ito, kaya kung hindi mo nais isipan ng pagpunta sa kung saan Sammy ay, maglalagay kami ng Sammy dito, at ngayon Gusto ko magtaltalan na ang pagpapalit operasyon Sammy ay mas mabilis. Ginawa namin 1 pagpapatakbo sa swap ang mga guys na ito, o marahil 2 upang magpalitan ng mga guys, ngunit hindi namin ginawa 1, 2, 3, 4, kaya na pakiramdam ng mas mahusay. Ngayon, maghintay ng isang minuto. Ko uri ng ginawa ang problema mas masahol pa dahil ang numero 4 ay uri ng malapit sa simula. Ngayon numero 4 ay isang maliit na mas malapit sa katapusang ito, ngunit hindi ko talaga alam o pakialam tungkol sa. Kaya ito ay malas na numero 4 ay isang maliit na mas malayo ang layo mula sa nakaukol lugar. Kaya natin ngayon ulitin ito algorithm. 

Upang paglalagom, hangga't kuwento na, lahat kami ay ay maglakad sa pamamagitan ng listahan naghahanap para sa pinakamaliit na bilang tao. Kaya ngayon sabihin gawin ito muli. Hindi namin kailangang mag-alala tungkol Sammy. Maaari naming pumunta lamang dito. Ooh! Numero 2. Iyon ay isang magandang maliit na bilang. 6, 8, 4, 3, 7, 5. Okay, mabuti. At thankfully, sa pamamagitan ng pagkakataon, hindi ko upang ilipat - >> Willie. Willie dahil siya sa kanyang tamang lugar ngayon. Natin gawin ito muli at huwag pansinin ang mga ito ng 2 guys. 6. Iyon ay isang magandang maliit na bilang. Ooh! 8 ay tiyak na mas malaki. 4. Hayaan ang tumutok sa 4. Ooh! 3 ay mas mahusay. 7 at 5. Kaya ano ang gagawin namin ngayon na may - >> Roger. >> Roger? Natin swap sa kanya na may numerong 6. Kaya kung 6 at 3 gusto mong magpalit, na namin ngayon ang uri ng nakuha masuwerteng sa na 6 ay mas malapit sa kung saan dapat siya, ngunit ito lang pagkakatulad dito. Kaya natin ngayon pumunta dito. 8 ay isang magandang maliit na bilang. Ooh! 4 ay mas maliit. 6, 7, 5. Ano ang gagawin namin ngayon gawin? >> Swap. >> Mismong. Kaya ngayon sabihin gawin ito uri ng mas mabilis na. 8, 6, 7, 5. Saan kinukuha ng 5 pumunta? Mabuti. Okay. 6, 7, 8. Ay nakakakuha ng 6 upang manatili kung saan siya ay. Ano ang iyong pangalan? >> Rosalie. Ay nakakakuha ng Rosalie upang manatili kung saan siya ay. 7 ay nakakakuha - natin makita. 7, 8. Okay. Kaya 7 ay nakakakuha upang manatili kung saan siya ay. Ano ang iyong pangalan? >> Amna. >> Amna. 

Kaya ay nakakakuha ng Amna upang manatili kung saan siya ay, at bilang 8 ay kung saan siya ngayon ay dapat na. Okay, mabuti. Nararamdaman tulad lang namin ang paglikha ng trabaho para sa ating sarili dito, bagaman. Ano ang huli ang tumatakbo oras ng algorithm na ito? Kung sa tingin namin tungkol sa mga taong hindi bilang 8 ngunit bilang n? >> Ito n. Ito n ang mga hakbang, ngunit Sinusuri namin ang bawat solong oras. Okay. N ngunit ka check bawat solong oras? Okay, ngunit kung ito n hakbang, hindi ko dapat ay upang pag-uri-uriin sa pamamagitan ng pagpunta lamang 1, 2, 3, 4? Oh! Okay, na ang isang malaking pagkakaiba. Kaya nakalapat n kung bakit? Kung ano talaga ang nangyayari? Mayroong n mga tao sa listahan na ito, ngunit upang mahanap ang pinakamaliit na tao sa listahan sa ang pinakamasama kaso, kung gaano karaming mga hakbang ko na kumuha? >> N. 

H, kanan, dahil sa ang pinakamasama kaso, numero 1 ang lahat ng mga paraan doon, kaya mayroon akong pumunta makakuha ng kanya. At pagkatapos ay kapag ako ay nag-wakas Napagtanto 1 ay ang pinakamaliit na, pagkatapos ito ay medyo mabilis magpalit ang mga ito. Ngunit ngayon mayroon akong upang simulan mula sa simula at hanapin na? Ang susunod na pinakamaliit na tao, na kung saan ay 2. Saan sa pinakamalala kaso ay 2? Oh, aking Diyos. Ang lahat ng mga paraan sa paglipas dito sa dulo. Kaya ngayon lang nagawa ko ang isa pang n hakbang, isa pang n hakbang. At kung kami nakakuha ng mga tao n at sa pinakamalala kaso ang pinakamaliit na tao ay n hakbang lamang ang layo, na muli n beses n, at kaya na namin muli ang N squared. Ito ay hindi pakiramdam kaya magandang. At sa katunayan, kahit na sa pinakamahusay na kaso - ipagpalagay na simulan nila off pinagsunod-sunod - kung gaano karaming mga hakbang aabutin para sa akin gamit ang algorithm upang pag-uri-uriin ang mga ito n mga tao? N nakalapat. >> Narinig ko n squared. Bakit n nakalapat? Dahil mayroon ka pa ring upang suriin ang bawat solong oras. >> Oo. At mayroon kang magpalit ang mga ito. >> Kahit na namin tao uri ng marunong ng lahat ng bagay sa kamalayan visual na aming makakaya lamang uri ng makita na ito ay pinagsunod-sunod, computer ng ay hindi na smart. Ito ay upang tumingin dito at dito at dito, ngunit kung ang kung ano ang hinahanap ay ang pinakamaliit na elemento, alam mo lamang na iyong natagpuan ang pinakamaliit na elemento sa pamamagitan ng kung ano ang punto? Sa sandaling ikaw ay sa dulo. Ngunit sa puntong iyon lamang natagpuan ang kasalukuyang pinakamaliit na elemento. Hindi mo kinakailangang malaman ang anumang bagay tungkol sa estado ng mundo. Kaya mayroon kang muli at muli at muli. 

Kaya oras na ito ko talagang gawin tumingin pipi dahil Lalabas na ako, okay, 2, ikaw na ang pinakamaliit na, ngunit hindi ko alam na sa kabuuan. 3, 4, 5, 6, 7, 8. Okay, mabuti. 2 ay sa katunayan ang pinakamaliit. Ngayon sabihin mahanap ang susunod na pinakamaliit. Okay. 3, ikaw ay kasalukuyang pinakamaliit. Natin makita. 4, 5, 6, 7, 8. Okay, nakuha ko masuwerteng muli. 3 ay katunayan sa tamang lugar. Ngunit ako pagpunta sa patuloy na ginagawa ito muli at muli at muli. Paano maaari naming gawin kailanman kaya bahagyang mas mahusay? Sa halip ng pagkakaroon ng tao bubble up pairwise mula sa pinakamaliit sa pinakamalaking at sa halip ng pagpunta pabalik-balik sa pamamagitan ng listahan ng pagpili pagkatapos pinakamaliit tao, bakit hindi namin halip magpasok ng mga taong ito sa isang bagong listahan hakbang sa pamamagitan ng hakbang? Hayaan ang subukan ito. Ngayon hayaan mo akong tawagan ito-uri-uriin ang pagpapasok ng bagay. Kaya dito ay namin dito. Numero 1. Wala akong pakialam tungkol sa sinuman sa listahang ito. Aking layunin ngayon ay ilagay ang numero 1 sa simula ng isang pinagsunod-sunod na listahan. At ako pagpunta sa ipanukala dahil lamang ako may 8 chunks ng memorya, mang ngayon Ako ang pader sa pagitan ng aking parang unsorted listahan, at sinuman na ay sa likod sa akin ako pagpunta upang i-claim ay pinagsunod-sunod. Kaya ngayon mayroon kaming numero 1. Gusto ko upang ipasok sa kanya sa aking listahan ng pinagsunod-sunod, kaya ako pagpunta sa ilipat ang aking pader sa dito, at ngayon inaangkin ko ang listahan na ito ay pinagsunod-sunod, ang listahan na ito ay unsorted - hindi bababa sa ngayon alam ko. Hindi ko makita ang lahat ng mga numero nang sabay-sabay. 

Ngayon ko mangyari sa nakatagpo ang numero 2. Ano ang gagawin ko sa kanya? Ko isingit ka na ngayon sa ang pinagsunod-sunod na listahan. Ngunit mapansin kung gaano kadali na. Ko na lang ay upang tumingin. Numero 1 doon. Oh, malinaw naman 2 napupunta sa gilid ng numero 1. Ngayon ano ang gagawin ko na may 3? Ko isingit sa ang pinagsunod-sunod na listahan. Ngunit iyon ay napakadaling. Ito ay napakadaling, ito ay napakadaling, ito ay napakadaling, sobrang madali, napakadaling. At ngayon ang lahat pinagsunod-sunod sa likod sa akin, at kung gaano karaming mga hakbang na tumagal? [Mag-aaral] N. >> Kaya lamang ito n. Namin nakuha masuwerteng. Lamang n kung bakit? >> [Mag-aaral] Dahil listahan ay pinagsunod-sunod. Ang listahan pinagsunod-sunod. Kaya namin nakuha masuwerteng. Subalit dinisenyo namin ang isang algorithm oras na ito na harnesses na uri ng swerte, na pinakamahusay na sitwasyon kaso, sa pamamagitan ng hindi pag-aaksaya ng hindi kinakailangang oras. Kaya namin ngayon kung ano kami tatawag ng mga uri ng bubble kung saan ang mga tao ay uri ng bubble up pairwise. Na kami ngayon ng pagpili-uri-uriin kung saan namin kumalbit sa pinakamaliliit na tao muli at muli. At ngayon namin ang pagpapasok ng-uri-uriin kung saan namin uri ng maagap na inilagay ang mga tao kung saan nabibilang sila sa isang nagiging pinagsunod-sunod sa listahan. Kung magagawa namin, isang ikot ng papuri para sa mga guys dito. [Palakpakan] Natin ang aming 5-minutong break na dito. At kapag dumating namin pabalik, namin pumutok ang lahat ng mga algorithm ng tubig may isang bagay na mas mahusay. Ayos lang. Maraming salamat. Maaari mong panatilihin ang mga bilang souvenir. Ayos lang. Kami ay bumalik. 

At sa paglalagom ng real mabilis, nagkaroon kami ng mga 3 iba't ibang mga diskarte sa pag-uuri, ang buong punto ng kung saan ay upang makakuha ng sa point kung saan ang isang tao tulad ng Alex maghanap ng isang listahan ng mga numero ng mas mabilis kaysa sa isang tao tulad ng Sean maaari. At kahit na mayroon kaming tulad simpleng halimbawa na may 8 numero, maaari mong intindihin mula sa data madali sa 8 mga pahina ng web, 8 bilyong mga web page, o 800 milyong mga kaibigan sa Facebook. Kaya mga algorithm ay maaaring tiyak na masukat sa mga uri ng mga halaga, at ang mga ideya sa huli ang parehong. Kaya bubble-uuri ay ang unang kung saan namin uri ng bubbled ang pinakamalaking tao ang lahat ng mga paraan upang ang karapatan sa pamamagitan ng pagpapalit ng mga tao pairwise. Pagkatapos namin ay kung ano ang makikita namin call na-uri-uriin ng pagpili kung saan ako ng kaunti pa sadyang iningatan hinahanap sa listahan, piliin ang pinakamaliit na bilang muli at muli at muli, lohikal na resulta ng kung saan ay na ang listahan ay pinagsunod-sunod kalaunan. Pagkatapos sa ikatlong isa, ipinasok ko ang mga tao sa kanilang mga naaangkop na lugar, at ginawa namin contrived halimbawa sa na listahan ay pinagsunod-sunod, ngunit ay upang ipadala ang mensahe na sa kaso ng pagpapasok ng-uuri, maaari kang makakuha ng masuwerteng. Kung ang mga numero ay na pinagsunod-sunod, lamang ito ay magdadala sa iyo n hakbang upang kumpirmahin bilang magkano, samantalang ang pagpili-uuri na sa iyo ng kaunti pa tunnel vision at hindi mo kailanman mapagtanto na ang listahan na pinagsunod-sunod. Kaya sabihin makita ang bubble na uri sa pagkilos dito. Sa mga sumusunod na halimbawa, hindi namin tungkol sa upang makita ang mga vertical na bar na ang taas ay kumakatawan numero upang maaari naming ayusin ng Ilarawan sa isip na pag-uuri-uri mangyayari. Sa mas maliit na bar, ang mas maliit ang numero, mas malaki ang bar, mas malaki ang bilang. 

At kami na i-play ang mga ito sa default na bilis. Ito upang ilipat ang isang maliit na mabilis sa ngayon, ngunit pula ay kung ano ang pagpapakita ng 2 bar na kumpara tabi-tabi. At kung panoorin mo nang maigi, ano ang mangyayari kung ang mga bar ay sira, ang mas maliit ay makakakuha ng inilipat sa kaliwa, ang mas malaking isa sa kanan, at pagkatapos mong panatilihin ang pagsulong. Kaya kung gagawin namin ito muli at muli, mapapansin na ang pinakamaliit na bar pagpunta sa panatilihing inching ang kanilang mga paraan sa kaliwa at ang pinakamalaking bar upang panatilihing inching ang kanilang mga paraan sa kanan. At sa katunayan, kami ay simula upang makita ang isang pattern ang lahat ng mga paraan sa kanang bahagi lamang tulad ng nakita natin 8 at pagkatapos 7 kalaunan bulubok hanggang sa dulong dulo ng aming mga listahan sa tao. Kaya ito ay pagpunta sa masyadong mabilis na makakuha ng bit ng nakakapagod, kaya ipaalam sa akin itigil ito para sa isang sandali. Hayaan akong baguhin ang bilis sa mas mabilis. Hindi ako sa pagbabago sa algorithm, lang ako sa paggawa ng animation ang mangyayari mas mabilis. Pa rin bubble-uuri, parehong algorithm, ngunit ngayon maaari mong makita ang mas mabilis kaysa sa aming pandiwang demonstration na ang pinakamalaking elemento ay sa katunayan bulubok sa itaas. 

Bilang isang bukod, ang mga maliit na mga parisukat sa kaliwa ng ibaba at kanang ibaba ay kaunti lamang paalala sa kung gaano karaming mga paghahambing na ginagawa mo. Ngunit sa ngayon, maaari naming tumuon sa pyramid na pagkuha ng hugis, at may ito napupunta. Ang pinakamaliit na elemento ay sa kaliwa, ang pinakamalaking sa kanan, at lahat ng iba pa sa pagitan. Ngayon ipaalam sa halip ng pagtingin sa pagpili-uuri. Ako pagpunta upang magpatuloy at pindutin ang Stop. Kami ay pagpunta upang makakuha ng isang bagong random na hanay ng mga bar. Ang Pinili-uuri, manariwa sa diwa, napupunta sa pamamagitan ng listahan muli at muli at muli, plucking sa pinakamaliliit na elemento. Kaya narito ang pagpili-uuri. Mukhang may mas mababa na nangyayari ngayon dahil hindi namin naghahambing ng pairwise ngunit kami ay ayusin ng seresa pagpili ang pinakamaliit na elemento mula sa kanan papuntang kaliwa. Na tumagal ng napakaliit na oras, kaya ang isang paghihiwalay sa dalawang bahagi na. Dahil lang sa isang algorithm ay sinabi sa n squared oras, tulad ng bubble-uuri at tulad ng pagpili-uuri, mga talagang pinakamasama kaso panahon ng pagtakbo. Halimbawa, sa kaso ng, sabihin nating, pagpili-uuri, Aktwal ko ako ang pagpili sa pinakamaliliit na tao at paglalagay ng kanya dito, ako ginagawa itong muli, pagkatapos ay ako ginagawa itong muli, ngunit nagkaroon ng bahagyang pag-optimize maaari kong gawin. 

Sa lalong madaling inilipat ko ang numero 1 dito - Sammy sa kasong iyon - kung ano ang kailangan kong gawin sa kanya noon? >> [Mag-aaral] Iwanang kanya. Iwanang kanya, kanan? Walang. Hindi ko kailangan upang kailanman na makipag-usap sa Sammy muli dahil kung ako ay napili na ang pinakamaliit na elemento at ilagay sa kanya dito, kung bakit ang basura oras ng pagpunta sa dulo ng aking buong listahan? Sa susunod na pag-ulit na ipaalam sa akin aktwal na ilipat lamang sa bilang 2, lamang sa numero 3. Kaya sa katotohanan, hindi ako paggawa ng mga n bagay n beses. Ako ay ginagawa n bagay, pagkatapos n - 1 bagay, pagkatapos n - 2 bagay, pagkatapos n - 3 bagay, pagkatapos n - 4, tuldok, tuldok, tuldok. Mayroon kaming isang bit ng isang geometric na serye, na lamang ay nangangahulugan nagdadagdag ka ng progressively mas maliit na numero. Hindi n + n + n + n ngunit n + 7 + 6 + 5 + 4 + 3 + 2 + 1. At kung ano na pangkalahatang gumagana upang maging - Ako pagpunta sa gulo up ang aking board dito para sa sandali lamang - na upang gumana sa isang bagay tulad ng n (n - 1) / 2 kung lamang namin uri ng hitsura sa likod ng isang aklat ng matematika na kung saan mayroon kang lahat ng mga impostor sheet para sa formula. Kung nagdaragdag ka ng isang bagay na lamang n + n - 1 + n - 2, ito gumagana sa isang bagay tulad nito. At kung lamang namin uri ng multiply ito, na n squared minus n / 2. Sinasabi ko iningatan n squared, bagaman, at na dahil ako ay uri ng pagkuha ng kaisipan shortcut dahil sa katotohanan, n squared minus n na hinati sa pamamagitan ng 2 sa katunayan ang tunay na bilang ng mga hakbang na ang isang algorithm tulad ng pagpili-uuri ay kung binibilang talaga namin hanggang lahat ng mga paghahambing at lahat ng maliit na abala na namin ginagawa. Subalit lantaran, sabay-sabay n nakakakuha ng tulad ng isang milyon o bilyong, na ang nagmamalasakit ng ano ba kung gumagawa ka ng isang bilyong squared minus isang bilyong na hinati sa pamamagitan ng 2? Isang bilyong squared ay isang malaking numero. Maaari mong gawin ang isa pang bilyon-off nito sa - n. Ito ay hindi isang malaking deal. Kaya ang mas malaking mga numero na nakukuha, hindi gaanong mahalaga ang mga mas mababa na nakaayos na mga tuntunin. Sino ang nagmamalasakit kung hatiin mo ng 2 kung ikaw ay pakikipag-usap tungkol sa mga quadrillions ng bilang ng mga hakbang? 

Kaya sa pangkalahatan, computer siyentipiko ay may posibilidad upang itapon ang lahat ngunit ang pinakamalaking termino, at lamang namin uri ng pasimplehin ang mundo at sabihin na algorithm kinuha halos n squared hakbang. Na ang oras ng paggana ng isang algorithm. Kaya magpapadala kami bumalik na ito sa sandali lamang na may ilang mga kongkreto halimbawa, ngunit sa ngayon, na uri ng intuitive pagganyak sa likod lamang pagpapasimple ng ating mundo at pakikipag-usap tungkol sa pinakamahalagang mga tuntunin kaysa sa pagkuha sa lahat ng mga fancy na mga formula. Kaya na pagpili ng uri, at nakuha namin ng kaunti masuwerteng doon. Tingnan natin sa pagpapasok ng-uuri. Hayaan akong sige at simulan ang isang ito pati na rin. Ngayon mapansin ang pattern na nangyayari ng kaunti ibang, at hindi na namin na nagsimula sa mga random na numero, ngunit kung namin ang aktwal na bilang ng ang bilang ng mga hakbang sa pinakamasama kaso, kung ang listahan sa nagsimula sa tamang pagkakasunod-sunod, nais lamang namin tumagal ng n hakbang upang mapagtanto bilang magkano. 

Ngunit kung ang listahan ay aktwal na paurong - halimbawa, sa kasong ito dito - pagkatapos mapansin namin aktwal na gawin ng maraming pang trabaho sa kasong ito. At dapat ito uri ng pakiramdam sa iyo tulad ng isang ito ay uri ng nagtatrabaho mahirap upang makakuha ng mga mas maliit na mga elemento sa kaliwa, at na dahil kapus-palad namin nakuha. Listahan ay pinagsunod-sunod aksidente sa reverse. Sa pamamagitan ng kaibahan, ang may pagpapasok ng-uri-uriin kung gayahin namin kung ano ang ginawa namin sa aming mga kawani na tao dito sa pamamagitan ng pagsisimula sa lahat pinagsunod-sunod at pagkatapos ay simulan, ito ay isang medyo magandang algorithm, i-right? Na ito, sa katunayan, pinagsunod-sunod. Kaya sabihin subukan upang ipahayag sa ilang pananalita eksakto kung gaano karaming oras ang mga bagay na ito ay pagsasaayos sa amin sa pamamagitan ng nagpapakilala lamang ng kaunti ng magulong pag-uusap o pagtatanda na ang aktwal na mas simple sa ang fanciness uri ng nagmumungkahi. Ito bagay dito, ang malaking O sa screen, ay kung ano ang isang computer siyentipiko ay pangkalahatan gamitin upang ilarawan ang pinakamasama kaso tumatakbo oras ng isang algorithm. 

Muli, sa pamamagitan ng pinakamasama kaso, ito ay lubos na konteksto-nakasalalay. Ano ang ibig sabihin namin sa pamamagitan ng pinakamasama kaso ay lubos na nag-iiba-iba batay sa problema na pinag-uusapan natin ang tungkol sa. Ngunit sa kaso ng pag-uuri, kung ano ang pinakamasama posibleng sitwasyon? Lahat ay paurong dahil ito nararamdaman tulad na ay nangangahulugan ng maraming trabaho para sa amin. Ko na jotted down na ng ilang ng algorithm na nasaksihan namin sa gayon malayo: linear paghahanap, binary paghahanap tulad ng sa phone book o ang mga piraso ng papel, pagkatapos-uuri-uuri ng bubble, pagpili ng uri, at pagpapasok ng tulad ng nakita natin sa aming mga kawani na tao, at pagkatapos ng 1 iba na kalaunan pagpunta sa tinatawag na sumanib-uuri. Kaya sa linear na paghahanap sa pinakamasama kaso, kung gaano karaming mga hakbang ang gawin upang mahanap ang numero 7 kung may n pinto tulad Sean mukha? >> [Mag-aaral] N. N. Kaya namin ay pagpunta upang isulat ang malaking O ng n. Lamang ako pagpunta sa punan ang ilang mga blangko. Ito ay isang grid ng mga blangko. Ngunit sa pinakamahusay na kaso sa linear paghahanap, 7 maaaring sa simula ng listahan, at Sean maaaring makapagsimula ng pagtingin sa simula ng listahan. Kaya kung gumagamit ka ng linear paghahanap at lang check pakaliwa sa kanan o maaaring karapatan sa kaliwa - hindi nila katumbas - sa ang pinakamahusay na kaso kung gaano karaming mga hakbang na maaari linear paghahanap, tulad ng Sean ng algorithm,? Lang 1 hakbang. 

Kaya ako pagpunta upang sabihin na ang wakas pagtatanda. Ito ay lamang kabisera wakas. Omega ay ang sexy paraan ng pagsabi pinakamahusay na kaso tumatakbo oras. Kaya sa ang pinakamahusay na kaso ang oras ay isang solong hakbang o pare-pareho ang bilang ng mga hakbang - 1 sa kasong ito - ngunit sa ang pinakamasama kaso, malaking O, ito ay aktwal na n hakbang. At ito ang isa dito, theta, aktwal na kami ay hindi upang tumingin sa ngayon. Ito ay hindi nauugnay sa partikular na halimbawa na ito. Ngunit ngayon sabihin subukan ang binary paghahanap. Sa pinakamalala kaso sa binary paghahanap, kung gaano karaming mga hakbang ay pagpunta sa gawin upang mahanap ang numero 7 o anumang kaming naghahanap para sa? >> [Mag-aaral] Mag-log n. Pa rin pagpunta sa n log dahil tulad lamang ng Alex nakuha kapus-palad kapag namin talagang nagtrabaho sa pamamagitan ng problema methodically at hindi niya mahanap ang numero ng 7 hanggang sa huling pinto siya ay tumingin sa, kahit na, sa pagkamakatarungan, nakuha niya upang itapon ang ilang mga pinto sa kahabaan ng paraan, binary paghahanap sa pinakamalala kaso ay tumatakbo ang oras ng log n. At muli, na nagsasalita sa paghahati at mapanakop. Ngunit ano ang tungkol sa ang pinakamahusay na kaso? At aktwal na naranasan Alex na pinakamahusay na kaso kapag dumating siya sa entablado. Gaano karaming mga hakbang na sa binary paghahanap? >> [Mag-aaral] 1. 1, dahil lamang niya nakuha masuwerteng. Ngunit iyon lamang ang fine dahil wakas ay tumutukoy sa mga pinakamahusay na sitwasyon kaso, pinakamahusay na input ng kaso, kahit na ito ay lamang random pipi swerte. 

Ngayon, ito masyadong kami ay pagpunta sa lamang ang uri ng bakasyon blangko sa ngayon. Bubble-uuri Paano tungkol sa ngayon? Sa pinakamalala kaso sa bubble-uuri, ang lahat ay sa reverse pagkakasunud-sunod, kaya mayroon kaming gawin ng maraming bulubok. Ngunit kung gaano karaming mga hakbang ay pagpunta sa sa ang pinakamasama kaso? >> [Mag-aaral] N squared. Ito ang n squared, dahil kung sa tingin mo tungkol dito, kung ang listahan ay ganap na paurong - 8 ay higit sa dito, 1 ay higit sa dito - bilang bagay magsimula sa bubble, ang bilang 8 ay pagpunta sa ilipat ang paraan na ito, sa ganitong paraan, ganitong paraan, ang paraan na ito, ngunit kung saan ay ang bilang 7 sa pinakamalala kaso? Narito siya ay pa rin doon. Kaya mayroon kaming gawin itong muli at muli. At na kung saan nakukuha namin n hakbang, pagkatapos n - 1 hakbang, pagkatapos n - 2 hakbang. At kung ang aking salita para dito - na kung ang uri ng multiply ito, halos ito n squared sa dulo na may ilang mga iba pang mga term na balewalain lang namin sa ngayon - sa pinakamalala kaso bubble-uuri n squared, bigyan o tumagal. Ngunit ano ang tungkol sa mga pinakamahusay na kaso sa bubble-uuri? Ano ang pinakamahusay na kaso sitwasyon? Ang lahat ng mga numero ay na pinagsunod-sunod. At kung ano ang hyuristiko ginamit ko, nanlilinlang na ginamit ko, upang mapagtanto na ako ay tapos ng trabaho walang at maaaring samakatuwid ihinto ang maagang? [Mag-aaral] Suriin ito sabay-sabay. >> Suriin ang mga ito nang sabay-sabay. Ngunit ano ang ako ginagawa sa kahabaan ng paraan? Ako ay pinapanatili track kung gaano karaming mga swaps ginawa ko. At natanto ko na kung hindi ko binibilang ng anumang mga swaps sa aking mga daliri, at pagkatapos ay tapos ko na na ang trabaho na walang. Hindi ko tiyak dapat subukang gawin walang trabaho muli, sa gayon ay maaari ko lang itigil. 

Kaya sa pinakamahusay na kaso ng bubble-uuri kapag ang listahan ay pinagsunod-sunod, kung ano ang nais mong sabihin sa wakas pagtatanda ay, ang pinakamahusay na kaso tumatakbo oras? Lamang ito n. Naming gawin ang ilang mga trabaho, ngunit lamang namin na gawin ang 1 lakad halaga ng trabaho. At dito masyadong ako pagpunta sa iwanan blangko ang bahaging ito. At ngayon pagpili-uuri. Ang Pinili-uuri ay sa akin plucking ang pinakamaliit na tao muli at muli. At kung ano ang sinasabi namin ang oras na? Na ay n nakalapat sa pinakamalala kaso. At sa kasamaang-palad, sa ang pinakamahusay na kaso din ito n squared dahil hindi ako ang uri ng marunong ng lahat ng bagay na tanawin ng buong mundo; Alam ko lamang kapag ang isang buong-ulit na katunayan na nahanap ko sa pinakamaliliit na tao. Kaya pagpili-uuri uri ng sucks sa na kahulugan, ngunit nakabaligtad ito uri ng intuitive. Ito ay medyo madali sa code up dahil ang lahat ng kailangan mong gawin ay magsulat ng dalawang nested para sa loop, karaniwan, na napupunta sa pamamagitan ng naghahanap para sa pinakamaliit na elemento at pagkatapos ay naglalagay ang pinakamaliit na elemento kung saan ito ay kabilang sa dulo ng listahan. Kaya dito masyadong mayroong ng trade-off. Ang halaga ng oras na aabutin mong mag-isip at sa aktwal na bumuo ng isang bagay sa pamamagitan ng pagsusulat ng code maaaring mahusay na gumawa ng mas maraming oras kung nais mo ng isang mas mahusay na algorithm at mas mabilis na pagganap. 

Ngunit kung ikaw ay talagang lamang uri ng code ng isang bagay up mabilis at marumi at uri ng stupidest posibleng ideya maaari mong isipin ng, na maaaring tumagal ng ilang minuto sa code, ngunit sa malaking hanay ng data ang iyong algorithm ay maaaring tumagal ng oras upang tumakbo. At kahit ako sa graduate paaralan ay minsan mga kalakalan-offs. Ito ay 3:00, ako ay sinusubukan upang pag-aralan ang ilang malaking hanay ng data may kinalaman sa seguridad pananaliksik na ako ay ginagawa, at alinman ito ay gastos ng 5 minuto pag-aayos ng aking programa upang pag-aralan ang data at matulog o gumastos ng 8 oras pagkuha ito lamang karapatan upang ito tumatakbo agad at hindi matulog. At sa gayon walang masyadong uri ng isang nakakamalay desisyon. Mas mababa ang pag-unlad ng oras, karagdagang pagtulog. Sa paggunita, marahil ko ay hindi dapat hinihikayat na kapag ang layunin dito ay upang i-optimize ang kalidad ng code, ngunit na masyadong sa tunay na mundo ay isang makatwirang kalakalan-off. Mas kaunting oras, mas pagganap o vice versa. Kaya dito namin sa wakas makakuha ng isang pagkakataon upang makipag-usap tungkol sa theta. Theta notation ay isang bagay na siyentipiko computer ay maaaring dalhin sa pag-uusap kapag malaki O at wakas mangyayari ang parehong. Sabihin mong theta sa talagang ipadala ang mensahe na ito ay uri ng isang masikip sumunod. Hindi mahalaga kung ang sitwasyon ay mabuti o hindi magandang, ito n squared. Kaya lang hindi may-katuturan sa mga kuwento sa dito. Insertion-uuri ay ang huling itinuturing namin ang, kung saan lang ako ay pagpasok ng lahat sa tamang lugar. Sa ang pinakamahusay na kaso kung ano ang tumatakbo oras ng pag-uuri ng pagpapasok ng bilang nakita namin ito dito? [Mag-aaral] Ang pinakamahusay na kaso? >> Ang pinakamahusay na kaso. 

Ito ay n dahil sa ang pinakamahusay na kaso lahat pinagsunod-sunod, at Sammy at walang ibang talagang ay upang ilipat sa lahat. Sila ay na sa kanilang mga tamang lugar. Kaya pagpapasok ng uri sa ang pinakamahusay na kaso, sa kasong ito, n. Ngunit sa pinakamalala kaso uri ng n squared. Bakit? Kung ang aking listahan ng mga tao sa reverse pagkakasunud-sunod, Simulan ko muna ang bilang 8 at isingit ko sa kanya sa tamang posisyon, na dito mismo. Uri ako ng paglipat sa gilid. Mga guys ay unsorted, siya ay pinagsunod-sunod. Ngunit ngayon ko mangyari upang mahanap kung sino ang susunod? >> [Mag-aaral] 7. 7 sa pinakamalala kaso dahil ito sa reverse pagkakasunud-sunod. 

Kaya dito ay 7. Kung saan nabibilang ang 7? Talagang sa likod sa akin. Ngunit ngayon 7 aktwal na nabibilang hindi agad sa likod sa akin ngunit sa likod ng numero 8, kaya kong sabihin, "Mawalang galang na, bilang 8, maaari mong ilipat ang paraan "Upang gumawa ng room para sa 7?" Ngayon ko nakatagpo ng 6. "Oh, patawarin ninyo ako, bilang 8 at numero 7, maaari mong ilipat ang upang gumawa ng room para sa 6?" Kaya sa ibang salita, may pagpapasok ng-uri-uriin, kahit hindi ako paggawa ng magkano ang kilusan, ang mga tao sa likod ng akin ang ginagawa ng maraming pang trabaho, at na nakuha sa halaga ng oras ng isang tao. Ito ay pagpunta sa gastos sa computer ng oras. Kaya sa kaso ng pagpapasok ng-uuri magdusa pa rin namin. Kung sinimulan mo ang pagdaragdag ng hanggang ang kabuuang bilang ng mga hakbang, magtapos namin pagpindot nang halos n squared dahil ang mga guys kailangan upang gumawa ng room para sa mga tao na ipinasok pabalik sa listahan na. At iba pa sa kasong ito theta lamang ang hindi naaangkop sa partikular na kuwento sa kamay. Na ang lahat ng maganda at mahusay na. Mayroon kaming mga 3 iba't ibang mga paraan ng pakikipag-usap tungkol sa ang oras. Ngunit ano ito aktwal na ibig sabihin sa tunay na mga term kung namin ang aktwal na subukan sa code ng isang algorithm? 

Hayaan akong magpanukala na may isang mas mahusay na algorithm out doon na mismo ay may ilang mga trade-offs. Kami ay pagpunta sa tumawag ito sumanib-uuri, at uri ng kahima-himala algorithm na ito na lang Mas mabilis na gumagana sa paanuman, at kaya madaling upang ipahayag, ng hindi bababa sa pseudocode. Ang pagpapatupad ng ganitong uri ng pagsasama ng algorithm na tulad ng sumusunod. Kapag binibigyan ka n elemento - n numero, n tao, anumang - unang may katinuan check. Kung ang n ay mas mababa sa 2, pagsamahin-uuri lamang hinto. Ito nagbabalik, kaya na magsalita. Bakit gusto mong itigil kung n ay mas mababa sa 2? >> [Hindi marinig na mag-aaral tugon] Kanan. At muli, n ay hindi ang bilang sa listahan, n ang laki ng listahan. Kung ang n ay mas mababa sa 2, na ay nangangahulugan na ang iyong listahan ay alinman sa 1, kung saan malinaw naman ay pinagsunod-sunod kung 1 numero, o 0, kung saan walang kinalaman upang ayusin, kaya kailangan namin ang ganitong uri ng kaso ng base. Kung ang listahan ay kaya maikli na may walang kinalaman sa, literal hindi gawin. Bumalik. Kung hindi man ayusin ang kaliwang kalahati ng mga elemento, pagkatapos ay ayusin ang kanang kalahati ng mga elemento, pagkatapos ay sumanib sa 2 pinagsunod-sunod na mga halves. 

Ang ganitong uri ng tila tulad ng isang maliit na impostor kung saan ako humihiling sa iyo kung paano upang pag-uri-uriin ang mga elemento at ikaw ay nagsasabi sa akin, "Pagbukud-bukurin kaliwang kalahati,-uri-uriin ang kanang kalahati." Ako tulad ng, "Ang lahat ng mga karapatan. Paano mo ayusin ang kaliwang kalahati?" "Pagbukud-bukurin ang kaliwang kalahati ng kaliwang kalahati, ayusin ang kanang kalahati ng kaliwang kalahati, at pagkatapos ay tapos na." Ikaw ang uri ng cyclically pagtukoy kung ano ang ibig sabihin nito ay upang ayusin, ngunit ito lumiliko na aktwal makikinang na sa kasong ito. Ito ay hindi tunay na ito mabisyo ikot ng hindi nagtatapos dahil ito ay magtapos kapag? >> [Mag-aaral] Kapag naabot mo ang 1 bagay. Kapag naabot mo na ang 1 bagay. Kaya kahit na maaari mong magsimula sa 8 tao at sinasabi ko, "Pagbukud-bukurin ang kaliwang kalahati ng mga taong ito, ang 4 na tao, "pagkatapos ay sinasabi ko," Paano mo ayusin ang kaliwang kalahati? " "Well, ayusin ang 2 tao dito." At pagkatapos ikaw ay tulad ng, "Ang lahat ng mga karapatan, fine." "Paano mo ayusin ang kaliwang kalahati ng mga tao?" "Lamang-uri-uriin ang 1 tao dito." Ano ang makikinang na paghahayag ngayon? Mayroon akong upang pag-uri-uriin ang 1 tao. Tapos na. Hindi ko na gawin ang anumang trabaho. Ngunit ngayon mayroon akong upang pag-uri-uriin ang taong ito, ngunit hindi sila ng isang tao, walang kinalaman sa. 

Kaya magic tila sa ikatlong hakbang: sumanib ang pinagsunod-sunod na mga halves. Kaya sumanib-uuri tumatagal ito makikinang na pananaw na kung masira ang isang malaking problema pababa sa 2 mas maliit, identically-sized na mga problema at pagkatapos lamang uri ng pangola sa mas maliit na mga solusyon kasama sa pagtatapos, Ko ipanukala na maaari naming gawin mas, mas mas mahusay na [pagtapik sa tunog] kaysa sa anumang ng pagpili-uuri o-uuri ng pagpapasok ng. Tunay ko na pagbalewala sa na para sa kalahating oras, ngunit hindi ko talagang malaman kung ano ang nangyayari sa sa labas ngayon. [Whirring sound] [tawa] Kaya sabihin makita kung maaari naming makita ito na may kaunting tulong mula sa aming mga kaibigan sa Rob Bowden. May 2 malaking hakbang sa proseso ng pagsasama-uuri. Una, patuloy na hatiin ang listahan ng mga tasa sa halves hanggang kami ay may isang bungkos ng mga listahan na may 1 tasa sa kanila. Huwag mag-alala kung ang isang listahan ay naglalaman ng isang kakaibang numero at hindi ka maaaring gumawa ng isang perpektong malinis na hiwa sa pagitan ng mga ito. Lang mang pick kung aling listahan upang isama ang dagdag na tasa. Kaya sabihin hatiin ang mga listahang ito. Ngayon ay mayroon kaming 2 listahan. Ngayon ay mayroon kaming 4 na listahan. Ngayon kami ay may 8 mga listahan na may isang tasa sa bawat listahan. Kaya na ito para sa hakbang 1. Hakbang 2 paulit-ulit kaming magsama ng mga pares ng mga listahan gamit ang sumanib algorithm na namin natutunan bago. Pagsasama sa 108 at 15 namin magtapos sa listahan sa 15, 108. Pinagsasama ang 50 at 4 magtapos namin na may 4, 50. Pagsasama sa 8 at 42 namin magtapos may 8, 42. At pinagsasama ng 23 at 16 namin magtapos na may 16, 23. Ngayon ang lahat ng aming mga listahan ng laki 2. Pansinin na ang bawat isa sa 4 na listahan ay pinagsunod-sunod, upang maaari naming simulan ang pinagsasama ng mga pares ng mga listahan muli. Pagsasama sa 15 at 108 at 4 at 50 muna namin ang 4, pagkatapos ang 15, pagkatapos ang 50, pagkatapos ay ang 108. Pagsasama sa 8, 42 at 16, 23 muna namin ang 8, pagkatapos ang 16, pagkatapos ang 23, pagkatapos ay ang 42. Kaya ngayon mayroon kaming may 2 listahan ng mga laki 4, ang bawat isa ay pinagsunod-sunod. Kaya ngayon bumaybay namin mga 2 listahan. Una naming 4, pagkatapos namin ang 8, pagkatapos namin ang 15 at 16 at 23 at 42 at 50 at 108. At tapos na kami. Namin ngayon ay may pinagsunod-sunod listahan. 

Rob uri ng sinasamantala ng isang bagay na hindi pa kami tapos. Ito ay iminungkahing, ngunit hindi namin aktwal na gawin ito. Siya ay paggawa ng isang bagay pisikal na may tasa na nagmumungkahi siya ay paggastos ng ilang mga mapagkukunan na bukod sa oras. >> [Mag-aaral] Space. >> Ito ay space. Ang katotohanan na siya ay may ganitong uri ng Silahis-antas na talahanayan kung saan nagkaroon siya ng espasyo dito at space pababa dito ay aktwal na nagpapahiwatig na siya ay gumagamit ng dalawang beses ng mas maraming espasyo ang anuman sa aming mga algorithm sa gayon ngayon - pagpapasok ng-uri-uriin, bubble uri, o pagpili-uuri - ngunit siya ay pagdaragdag ito ng dagdag na espasyo sa uri ng mga bagay sa ilipat papunta at pabalik habang pinapanatili ang mga bagay upang. At kahit na ito nararamdaman tulad ng nakuha namin sa isang pinagsunod-sunod na listahan, na nadama tulad ng ito kinuha ng isang habang. Sa katotohanan, ano Rob ay ginagawa ay eksakto ang algorithm na ito. Siya unang kinuha ang problema ng laki n, hinati ito sa isang kaliwang kalahati at kanang kalahati. Kapag inilipat siya sa tasa. Pagkatapos siya paulit-ulit na proseso. Hinati niya ang 4 sa 2 set ng 2 sa dito at sa paglipas dito. Pagkatapos siya paulit-ulit na proseso at hinati 2 sa 2 set ng 1 para sa bawat isa ng mga iba't-ibang tasa. At na kung saan ang makikinang na pagkakataon arises. Sa puntong iyon sa kuwento, Rob ay nagkaroon ng 8 mga listahan ng mga laki 1, ang lahat ng mga ito ay na pinagsunod-sunod. 

Kaya pagkatapos kung ano ay siya magpatuloy na gawin? Ang Pairwise kinuha niya ito pinagsunod-sunod na listahan at ito pinagsunod-sunod na listahan at Pinagsama sa kanila. Pagkatapos ay kinuha niya ang isang ito at Pinagsama sa kanila, ang isang ito at Pinagsama sa kanila, pagkatapos ng isang ito at Pinagsama sa kanila. At pagkatapos ay kung ano ang ginawa niya sa tabi? Siya pagkatapos ay muling-Pinagsama ang mas malaking mga listahan at pagkatapos ay muling Pinagsama ang mas malaking listahan. At kung sa tingin mo tungkol dito lamang intuitively sa ngayon, kung ano ang siya talaga ginagawa? Siya ng paghati ng problema sa kalahati, sa kalahati, sa kalahati, sa kalahati upang makakuha ng mga sobrang maliit na listahan. Pagkatapos siya ay uri ng pagsasama-sama ng double, double, double, double. Kaya siya ay ginagawa nang dalawang beses ng maraming trabaho namin ang iyong nakita sa gayon malayo sa anumang kinasasangkutan hatiin at lupigin, ngunit hindi sang-ayon. Dalawang beses ng mas maraming trabaho ay hindi isang malaking deal. Ito ay patuloy na kadahilanan. At tulad ng aming pang-aritmetika expression bago, lamang ako upang i-cross ang mga pare-pareho ang mga kadahilanan tulad ng beses 2. Sino ang nagmamalasakit? Kung ito ay 2 bilyong beses 2, na pa rin ng maraming ng mga hakbang. Kaya pinagsasama ang mga hakbang na ito ay tila ang key na pananaw. Natin maglakad sa pamamagitan ng ayon sa bilang bago - Oh, na hindi na nagpatuloy pa. Lakad natin sa pamamagitan ng ayon sa bilang lamang sa aktwal na makita kung paano ito nagpe-play ang. Ito ay karamihan lang animation ng kaunti mahinang tao. Natin ipanukala ito. Ang tumatakbo ang oras ng pagsasama-uuri - kailangan lang namin ng isang paraan ng pakikipag-usap tungkol sa. Na ito ay hindi matematika; ito lamang ang uri ng isang maikli at malinaw na paraan ng pagpapahayag ng ating sarili. Kaya T kumakatawan oras at n kumakatawan sa kung ano? >> [Mag-aaral] Ang laki ng - 

[Malan] Ang laki ng problema, ang bilang ng mga tao. Kaya ako na nagke-claim na ang oras upang pag-uri-uriin ang mga tao n 0 halaga ng oras kung ang n ay mas mababa sa 2, dahil kung mayroon kang 1 tasa o walang tasa, mayroon kang walang kinalaman upang ayusin. Ngunit mas pangkalahatan, ako pagpunta sa ipanukala na ang oras upang pag-uri-uriin ang mga n elemento ay ang oras na kinakailangan upang pag-uri-uriin ang kaliwang kalahati kasama ang karapatan na kalahati plus - kung ano ang karagdagang + n? >> [Mag-aaral] magsamang bumaybay-uuri. [Malan] aktwal Ito ay pinagsasama, dahil kung mayroon kang n / 2 elemento dito at mayroon kang n / 2 elemento dito, kung gaano karaming oras ang gawin upang pagsamahin ang mga ito? Tulad lamang ng Rob, mayroon kang kumalbit ang isang ito sa paglipas dito, maaaring kumalbit sa paglipas dito, kumalbit sa paglipas dito, kumalbit sa paglipas dito, kumalbit sa paglipas dito. Mong pindutin ang bawat isa ng tasa sabay-sabay. At kung may 4 tasa plus 4 tasa, na 8 tasa o, mas pangkalahatan, 8 n tasa. Kaya pinagsasama ang mga hakbang na maaari naming ipahayag ang bilang n, at na literal na nagsasangkot ang dami ng beses na Rob pisikal hinawakan isa ng mga Styrofoam tasa. Kaya natin ngayon isang arbitrary na halimbawa. Kung may 16 tasa, kung ano ang oras ng pag-uuri-uri, gamit ang Rob algorithm, 16 tasa? 2 beses ang halaga ng oras na aabutin upang pag-uri-uriin ang 8 tasa dahil mayroon kaming 8 tasa dito, 8 tasa dito. Hindi ko alam kung gaano katagal na tumatagal, kaya kami ay generalizing ito bilang T para sa ngayon. Sino ang nakakaalam kung ano ito ay? Ngunit ngayon ang maaari kong pag-uri-uriin recursively o paulit-ulit na tanungin ang parehong tanong. Gaano karaming oras ang aabutin upang pag-uri-uriin ang 8 tasa? 8 tasa ako sasabihin tumatagal ang halaga ng oras na aabutin upang pag-uri-uriin ang 4 tasa plus 4 tasa, pagkatapos ay pinagsasama ang mga iyon nang magkakasama. Fine. Kami ay nakakakuha sa isang ikot ng na. Gaano katagal aabutin upang pag-uri-uriin ang 4 tasa? Ang oras na aabutin upang pag-uri-uriin ang 4 tasa 2 tasa plus 2 tasa pag-uuri-uri kasama ang pinagsasama ang proseso. Fine. Gaano katagal aabutin upang pag-uri-uriin ang 2 tasa? 2 tasa ay ang halaga ng oras na aabutin upang pag-uri-uriin ang 1 tasa kasama ang oras na kinakailangan upang pag-uri-uriin ang isa pang tasa pati na rin ang halaga ng oras na aabutin upang sumanib, na kung saan ay may 2. 

Fine. Huling tanong. Gaano katagal aabutin upang pag-uri-uriin ang 1 tasa? Narito ang pangunahing kaso na hinulaang namin gusto namin pindutin mas maaga. Ang katotohanan na ito ay tumatagal ng walang trabaho anumang upang pag-uri-uriin ang pinakamaliit ng problema nangangahulugan na ngayon, uri ng mababang paaralan estilo, maaari naming pumunta lamang magsimulang i-plug ang mga numerong ito muli. Namin ngayon malaman kung ano ang T na 1, kaya ko plug sa 0 para sa T na 1. Na ay magbibigay sa akin ang kasagutan sa T ng 2, kung saan pagkatapos ko maaaring plug sa mas mataas na up. Na ako ay magbibigay sa T ng 4, na ko plug sa mas mataas na up. Na ako ay magbibigay sa T na 8, na maaari kong plug sa mas mataas na up. At kung gawin ko aktwal na matematika sa pamamagitan ng pag-i-plug sa mga sagot, Pagkatapos kong makakuha ng T ng 16 ay 64. At kung ano ang 64 kumatawan? Kung ang T ay 16, oo, 16 beses 4. Kaya inaangkin ko ngayon na ang oras na ito bagay na tinatawag na sumanib-uuri - at ito ay ang fanciest ng mga nasaksihan namin sa gayon malayo - na tinatawag n log n dahil kung gaano karaming beses ang maaari Rob hatiin ang maramihang mga tasa sa kalahati? Mag-log n. Ang parehong bilang halimbawa ng phone book, ang parehong bilang self-nadaragdagan halimbawa. 

Kung gaano karaming beses ang maaari mong hatiin ang isang bagay sa kalahati? Gayunpaman, mayroong pinagsasama ang mga hakbang na ito. Maaaring mayroon ka upang hatiin ang mga tasa sa kalahati muli at muli at muli, ngunit sa bawat oras na ikaw ay pagpunta sa may upang sumanib. At sinabi namin nang mas maaga na pinagsasama ang tasa n tumatagal n hakbang dahil mayroon kang upang kumalbit isang tasa, kumalbit isang tasa, at mayroon kang pindutin bawat tasa nang isang beses, tulad ng Rob ginawa. Kaya kung ang ginagawa namin ang log n beses sa isang bagay at ginagawa namin n mga bagay sa bawat isa sa mga iterations, ang bawat isa ay ng mga halvings, mayroon kaming n beses log n. Kaya kung plug namin sa 16 sa halimbawang ito, ang 16 beses mag-log ng 16 - huwag mag-alala tungkol sa kung bakit ito ang kaso para sa ngayon dahil hindi ko na iginuhit base - ngunit ang log ng base 2 ng 16 4, 16 beses 4 64. Ngunit sa pamamagitan ng kaibahan, kung kami ay ginagamit bubble-uuri o pagpili-uuri o-uuri ng pagpapasok ng may 16 mga numero, kung ano ang ang oras ay kung n ay 16? Magiging 16 squared, na kung saan ay 256, na kahit na kung hindi mo pa lubos na sinusundan ng lahat ng matematika, 256 ay mas malaki kaysa sa 64. Na talaga kahima-himala takeaway dito. At mapagtanto na nagtatrabaho sa pamamagitan ng ito sa mas maliit na mga halimbawa ay mo sa isang pset gumagawa ng lahat ng ito mas intuitive. Ngunit ano na talaga ay nangangahulugan sa mga tuntunin ng ang pakiramdam ng algorithm na ito ay ito: Kung namin ang aktwal na tumitingin sa pagsasama-uuri dito - ipaalam sa akin hilahin ang mga ito sa window na ito dito - ito ay isang bahagyang kakaibang halimbawa kung saan mayroon kaming ang lahat ng 3 ng mga algorithm - bubble, pagpili, at sumanib - tabi-tabi. 

Lahat ng mga ito makapagsimula sa random na mga bar, at na mahusay. Walang isa ay may isang pangunahing bentahe sa ibabaw ng iba pang mga. Pupunta ako sa sa isang sandali mag-click sa bawat isa sa mga animation - Simulan, Start, Start - bilang mabilis hangga't maaari kong upang, halos, sila lahat ng simula sa parehong oras, at sabihin isaalang-alang na mas masahol pa kaso bubble-uuri tumatakbo oras ang? >> [Mag-aaral] N squared. N nakalapat. Ay ang pinakamasama kaso-uri-uriin ang Pinili tumatakbo ang oras? N nakalapat. At sumanib-uuri ay tila - kahit na hindi mo ay medyo sundin ang lahat ng matematika ngayon, itong maging higit na mas magaling sa paglipas ng panahon - ay, inaangkin namin, n beses log n. At dahil log n ay mahigpit na mas mababa kaysa sa n sa sandaling kami ay may malaking numero, n beses log n ay mas maliit kaysa sa n beses n o n squared. Kaya kung ano ang pakiramdam sa aktwal na maging isang mas mahusay na algorithm sa mga tuntunin ng tumatakbo ang oras, n beses log n kumpara sa n squared? Narito kami. I-click, click, i-click ang. 

Kung ano ang ibig sabihin nito ay upang gamitin ang isang bagay tulad ng pagsasama-uuri. Mayroon kami ng ilang sandali. Natin makita kung ano ang mangyayari dito. [Chuckles] Kaninong pera sa bubble-uuri? Ito kaysa depende sa input minsan. Natin makita. Halika sa. Nararamdaman tulad siya ng pansing up. >> [Mag-aaral] Pumunta, bubble-uuri! [Mag-aaral murmuring] [Malan] Oo, oo. [Mag-aaral murmuring] Pumunta, pumunta, pumunta! [Lahat ng pagpalakpak] [palakpakan] Kaya ngayon may 1 huling, panghuling demo, kung ito ay isang maliit na nakakalito sa I-wrap ang iyong isip sa paligid ng matematika o uri ng visualization doon, maaari mong aktwal na marinig ang bilis ng iba't ibang mga algorithm naiiba. Ito ay isang tao ang isang animation na ginawa na aktwal na iniuugnay ng tunog ang proseso ng pagpapalit at ang taas ng bar. Dahil kakailanganin namin makikita dito, may ilang higit pang mga pag-uuri algorithm out doon na ang mga tao na naisip ng. Ang unang isa ay pagpunta sa pagpapasok ng-uri-uriin, at ito ay lumipad sa at magbibigay sa iyo ng isang naririnig na pakiramdam ng kung paano ang mga iba't-ibang mga algorithm ng trabaho. Narito ang pagpapasok ng-uuri. [Electronic beeping] [Malan] Bubble-uuri. [Mas mabilis electronic na beeping] [Malan] Pinili-uuri. [Mas mabilis electronic na beeping] [Malan] magsamang bumaybay-uuri. [Electronic beeping] [Beeping slows] [tawa] [Malan] Gnome-uuri. [Electronic beeping] 

Ito ay CS50. Gagamitin namin ang susunod na linggo. [Palakpakan at pagpalakpak] 

[CS50.TV]