Tagapagsalita: Lahat ng karapatan, ito ay CS50. Ito ang katapusan ng linggo tatlong, at kung hindi mo kinuha bentahe na, malaman na magkakaroon ng tanghalian Biyernes ito gaya ng dati, kung saan Maaari mong tangkilikin ang mahusay na pag-uusap at pagkain sa Sunog at Yelo kasama ang ilan sa CS50 ni kawani at mga kamag-aral. Magtungo sa URL na ito dito. Ngayon maaari mong isipin ang, o sa iyo Maaaring madaling ma-kilala sa, mga bagay na ito dito, na ay binibigyan out sa dulo ng semestre para sa maraming mga klase. Kaya-tinatawag na pagsusulit asul na mga libro, kung saan mong isulat ang iyong mga sagot sa mga pagsusulit. Ngayon Mayroon akong dito 26 tulad asul na mga aklat, sa bawat isa sa kanila nakasulat ang isang pangalan, A sa pamamagitan Z. At sa katunayan ang pangalan ay na simple, A sa pamamagitan ng Z. At isa sa ang mga layunin sa kamay ngayon ay magiging upang magpatuloy kung ano namin na nagsimula sa Monday, kung saan ay hindi kaya magkano ng pagtingin sa code, ngunit talagang pagtingin sa mga ideya at mga problema paglutas. Isa sa mga layunin at mga pangako ng kursong ito ay upang magturo sa iyo mag-isip nang higit pa Maingat, mas methodically, at upang malutas ang mga problema nang mas mabisa. At sa katunayan, maaari naming gawin na talaga nang walang kahit pagpindot sa isang linya ng code. Kaya ba akong magkaroon ng isang pares ng mga elepante up dito ngayon, orange at asul, kung maaari naming makakuha ng isang volunteer, siguro mas malayo mula sa likod kaysa sa karaniwan. Paano ang tungkol doon, dumating pababa. Ang layunin ng kung saan ay magiging sa tulungan plus pangasiwaan ang eksaminasyong ito dito. Ano ang inyong pangalan? Madla: Mary Beth. Tagapagsalita: Mary Beth, dumating sa up. Hayaan akong makuha ang mikropono dito para sa iyo. Nice upang matugunan mo. Madla: Nice upang matugunan mo. Tagapagsalita: Lahat ng karapatan, kaya Mayroon akong dito asul Ang isang libro sa pamamagitan ng Z, at pupuntahan ko upang magpanggap na Mayroon akong isa sa mga mag-aaral, at sila nagmumula sa medyo random sa dulo ng isang tatlong oras na bloke pagsusulit, kaya sila ay nagtatapos up sa ilang mga semi-random na pagkakasunod-sunod na katulad nito. Ngayon ang iyong trabaho sa isang sandali lamang ay pagpunta upang be-- ito ay talagang kung paano sila makakuha ng Naka-in sa dulo ng ang klase, pinaka-malamang. Ang iyong trabaho ngayon ay magiging, medyo lamang, upang ayusin ang mga asul na mga libro para sa amin mula sa A sa pamamagitan Z. Madla: Oh, ito ay pagpunta sa tumagal magpakailanman. Tagapagsalita: At magkakaroon kami panoorin ginawa mo na ito, walang presyon. Madla: Hindi, walang presyon o kahit ano. Tagapagsalita: At para masaya, ni maglagay ng isang timer ipaalam. Madla: Kaya magkano masaya, kaya magkano masaya. Tagapagsalita: Maaari ko bang hawakan ang mic para sa iyo. Ang lahat ng mga karapatan, na lamang Dinoble namin ang aming bilis. Kaya sa Pansamantala, hayaan mo akong magpose kayo kung ano ang pagpunta sa maging ang tanong para sa Mary Beth ay kung ano ang ginagawa niya, paano ay siya ng pagpunta tungkol sa paglutas ng mga ito? At sa katunayan, hindi mo maaaring mayroon kailanman naisip tungkol sa isang bagay kaya simpleng bilang kapag kinuha mo hanggang 26 mga aklat na tulad nito, na kung saan ay walang natural ng pag-order sa kanila. Ano ang proseso na iyong aktwal na gamitin? Ito ba ay medyo random na lamang pagpili ang unang isa na nakikita mo at paglalagay nito sa lugar nito? Huwag mong ilipat muna ang iyong mga kamay sa paligid naghahanap ng isang pagkatapos ay naghahanap para sa B? Umiinom ba ng isang pagtingin sa isang pares ng mga ito tabi-tabi at sabihin lamang, maghintay ng isang minuto, ito hindi tama, at pagkatapos magpalit ng order? Nakita namin na sa Lunes na mayroong isang bilang ng mga paraan kung saan maaari naming gawin ito, at sa katunayan bilang namin na malapit sa dulo dito, Gusto ko itala marahil ng kung ano ang Mary Beth ang ginagawa. Mayroon kaming ilang mga piles ito ay tila, isang mas malaking isa, tatlong mas maliit na mga bago. Madla: ako pag-order ng mga ito kapag nakahanap ako ng dalawang titik na kong malaman ay magkasama sa isang pagkakasunud-sunod, Ilagay ko ang mga ito nang sama-sama upang ang gagawin ko hindi kailangang mag-alala tungkol sa pagpapanatiling track ng isang buong hilera ng libro. Ito ay lamang, oh, A ay una, Mayroon akong na ito stack dito. Tagapagsalita: Kaya, halos tulad ng isang palaisipan piraso na ay may karapatan sa hugis tutugma sa isa't isa. Madla: Pretty magkano, Oo. Tagapagsalita: OK, mahusay. At ngayon bawat isa sa mga piles ay baka pinagsunod-sunod? Madla: Oo. Tagapagsalita: Lahat ng karapatan, A sa pamamagitan Z. Lahat karapatan, binabati kita, ginawa mo ito. Mayroon kang ang iyong pinili. Blue? Ang lahat ng mga karapatan, salamat sa iyo para sa na. Kaya Mary Beth ay ipanukala kung ano ang kanyang diskarte ay, ngunit kung ano ay isa pang diskarte kung paano mo Baka pumunta tungkol sa pagbubukod-bukod ng mga bagay na ito? Ano ang gusto mo pa? Ang tala upang talunin ang maaaring naging isang minuto at 50 o kaya mga segundo, kasama ang mga bago Nakalimutan ko ang upang mabilang. Ano ang gusto mo pa? Oo? Madla: Dumaan sa stack. Simulan mula sa simula. Suriin ang iyong mga papeles. At kung ang isa tuktok ay mas mataas kaysa, marahil, ang mga ito, ang isa ay ibaba mas mataas, pagkatapos ay lumipat sa kanila. Tagapagsalita: OK, kaya simula sa itaas at sa ibaba, at pagkatapos ay gumagana ang iyong paraan paloob tulad na, pagpapalit ang mga ito? OK, kaya ng kaunti katulad sa espiritu sa bubble-uuri, ngunit pagpili ng extremes hindi ang katabing mga pares. Subalit ang maikling ng ito ay mayroong tiyak ng grupo ng mga iba't-ibang paraan maaari naming gawin ito, at tapat, sa tingin ko sa iyo uri ng pinagtibay ng ilang approach na ito, tama? Nagsagawa ka ng isang uri ng apat na pinagsunod-sunod piles, at pagkatapos ay epektibo Pinagsama-sama ang mga ito. At iyon ang, daresay, isa pang diskarteng ito nang sama-sama. Hindi mo ituturing ito bilang isa malaki pile, hinati mo ang problema sa apat na quads, kung gagawin mo, at pagkatapos ay kahit papaano Pinag-isa ang mga ito sa dulo. Kaya Isaalang-alang natin, sa huli ipaalam, paano pa namin maaaring gawin ito. Formalized namin ang paniwala ng bubble-uuri huling oras, at bubble uri pagpapabalik ng algorithm na namin makita may walong ng iyong mga kaklase up dito, tila random na pinagsunod-sunod sa unang. At pagkatapos ay nagpasya kaming pairwise, kung ang dalawang mga elemento ay sira, magpalit lang ang mga ito. Kaya apat at dalawa malinaw naman out sa pagkakasunud-sunod, kaya dalawang kaklase mga nakalipat posisyon. At pagkatapos ay paulit-ulit namin na may apat at anim, pagkatapos ng anim at walong, sa bawat iteration, paglipat sa kanan. Kaya ibinigay na walong tao, kung gaano karaming mga pairwise paghahambing ginawa ko habang naglalakad mula sa ang natitira upang karapatan sa isa tulad iteration? Gaano karaming mga paghahambing? Pitong, tama? Dahil kung mayroong walong mga tao ngunit mayroon ka ng mga pares ang mga ito at mong mapanatili ang paglipat isa Hop sa kanan, Hindi ka pagpunta sa may walong paghahambing dahil hindi mo maaaring ihambing isang elemento laban sa sarili nito, o gagawin ito maging pointless lamang, kaya mayroon kang pitong. O mas pangkalahatang paraan, kung mayroon kaming n tao, namin gawin n minus 1 paghahambing may bubble-uuri. Kaya Isaalang-alang natin ngayon kung paano mahusay na ipaalam o masamang bubble uri talaga noon, at subukan upang bigyan ang ating mga sarili na may bokabularyo kung saan pumupuna algorithm na tulad nito, at sa lalong madaling panahon ang aming mga sarili. Kaya ang unang pass sa pamamagitan ng uri ng bubble, sa unang pagkakataon Lumakad ako mula kaliwa hanggang kanang sa buong yugto, kinuha sa akin n minus 1 paghahambing. At na pupuntahan maging ang aking yunit ng pagsukat, tama? Uri ng ako ay pakikipag-usap at strolling, medyo mabilis, medyo mabagal, kaya pagbibilang aking bilang ng mga segundo ay hindi partikular na nagsasabi, ngunit pagbibilang ang bilang ng mga mga operasyon na ginawa ko sa Monday, paghahambing ng dalawang tao, na sa palagay tulad ng isang masarap na unit ng pagsukat. Kaya n minus 1 hakbang sa unang pagkakataon, ngunit pagkatapos ay kung ano ang nangyari pagkatapos na? Ano ang isang bentahe ng isa pass sa pamamagitan ng isang kung hindi man ay unsorted listahan? Ano ang maaari mong sabihin sa akin ang tungkol sa mga elemento na naging ang lahat ng mga paraan na iyon? Oo? Iyon ay ang pinakamalaking elemento, tama? Numero ng walong, kahit na siya Nagsimula dito, sa tuwing ako kumpara laban sa kanya isang kapit-bahay, siya ay pinananatiling bubbling up sa kanan bahagi ng listahan. At sa katunayan, iyon ang kung saan ang algorithm ay makakakuha ng pangalan nito. Ngayon na sa pamamagitan ng logic, kung gaano karaming mga paghahambing kailangan gumawa ako sa ikalawang oras Gumawa ko na pass mula kaliwa hanggang kanang? n minus 2, i-right? Ito ay lamang ma-aksaya ang aking oras kung ako panatilihin ng paghahambing ng walong laban sa isang tao iba dahil alam namin siya ay nasa tamang lugar. Kaya na ang isang bit ng isang pag-optimize, kaya ang susunod na pass ay magiging plus n minus dalawang hakbang, kung saan n ay ang bilang ng mga tao. Ngayon ay maaari mong uri ng extrapolate, kahit kung ikaw ay hindi isang computer siyentipiko, paano nagtatapos ito. Sa dulo ng algorithm na ito, baka mayroon ka lamang isang paghahambing na natitira. Mayroon kang sa uri ng maayos ang simula ng listahan sa kasong dalawang at isa ay sira at dapat ay isa at dalawa, kaya ito bottoms out sa plus 1 panghuling paghahambing. Ngayon ang tuldok, tuldok, tuldok uri ng mga wave ito mga kamay sa ilan sa mga juicier mga detalye, ngunit hayaan pumunta ni lamang magpatuloy at pasimplehin. Kung isipin ang mo mula sa mataas paaralan, tapat, ng maraming mo Nagkaroon matematika mga aklat na nagkaroon ng medyo cheat sheet sa harap na pabalat o ang likurang pabalat na ipinakita sa iyo ano serye summations tulad ng ito sa huli idinagdag hanggang sa. Sa pangkalahatan kaso, kung mayroon kang isang variable tulad n, at sa katunayan ang isang ito, kung tiningnan mo ang iyong matematika aklat lumang paaralan, Gusto mong makita na ito talaga nagdadagdag ng hanggang sa halagang ito dito, n beses n minus 1 lahat ng hinati sa 2. Kaya para sa ngayon hayaan stipulate sa akin lamang ito ay totoo, kaya sa isang hakbang ng pananampalataya, na kung ano ito sums hanggang sa, at maaari naming patunayan na sa isang mas pangkalahatang mga kaso. Ngunit ng palawakin ito out na ngayon hayaan. Kaya ni-multiply ito out ipaalam, kaya na n nakalapat, minus n, ang lahat ng hinati sa 2. Iyon ay talagang n nakalapat, hinati sa 2, minus n paglipas ng 2, nang sa gayon ang lahat ay maganda at kawili-wiling. Ngunit ano ang mangyayari kung namin ngayon plug-in ng isang halaga? Ipagpalagay Hindi ko kinailangang walong mga tao, ngunit sinasabi ng isang milyon. At isang milyon dahil lang ito ay isang medyo malaking bilang, plug sa na at tingnan kung ano ang mangyayari ipaalam. Kaya kung plug ako ng isang milyon sa na formula Pupunta ako upang makakuha ng isang milyong nakalapat, hinati sa 2, na binawasan ng isang milyon, na hinati sa 2. Ngayon kung ano ang na pagpunta sa kasing-halaga? Kaya 500000000000, na binawasan ng 500,000. At kung ako aktwal na gawin na matematika out, paraan na na pag-uuri ng isang milyong mga taong may bubble-uuri Maaaring umabot sa akin 499999500000 hakbang o mga paghahambing sa dulo, lamang kami extrapolating. Na sa palagay medyo mabagal, ngunit tapat pagsukat ng isang partikular na pag-input tulad nito, ay hindi lahat na nagsasabi na iyon. Ngunit sa katunayan ito magmungkahi na ang bilang n ay makakakuha ng mas malaki at mas malaki, ito algorithm uri ng pakiramdam ng mas masahol pa at mas masahol pa, o mo ba talagang simulan sa pakiramdam ang sakit ng na exponentiation, na n nakalapat, na medyo mabilis nagdadagdag up. At detalye na ito ay hindi Nawala sa mga tao, sa katunayan ilang taon na ang nakakaraan ng isang tiyak na Senador na naging campaigning, SA down para sa isang pakikipanayam may Eric Google Schmidt, CEO sa oras, at ay hinamon sa isang tanong halos tulad kami ng paggalugad ngayon. Tingnan natin ang isang hitsura. [VIDEO pag-playback] -Senator, Handa ka dito sa Google, at gusto ko mag-isip ng pagkapangulo bilang isang interbyu sa trabaho. Ngayon, mahirap upang makakuha ng ng trabaho bilang president, at tapos ka ng pagpunta sa pamamagitan ng mga kahirapan ngayon. Mahirap din upang makakuha ng trabaho sa Google. Mayroon kaming mga tanong, at kami hilingin sa aming mga tanong kandidato, at ang isang ito ay mula sa Larry Schwimmer. What-- mo guys tingin ko Nagagalak kidding, ito ay dito mismo. Ano ang pinaka-mahusay na paraan upang pagbukud-bukurin isang milyong 32-bit integer? -Well-- -I'm Ng paumanhin, maybe-- -No, Walang, hindi. Sa tingin ko ang bubble-uuri ay magiging sa maling paraan upang pumunta. -Come Sa, na sinabi sa kanya na ito? Hindi ko nakita ng computer agham sa iyong background. Nakakuha -We've aming spies sa doon. -OK, Na magtanong sa isang iba't ibang hayaan tanong interbiyu. [END VIDEO pag-playback] Tagapagsalita: Kaya pinag-uusapan tungkol sa tukoy na mga numero bagaman, Hindi pupunta na maging lahat na kapaki-pakinabang. Hindi ito isang aralin buhay na bubble uri, bibigyan ng milyon input, maaaring tumagal ng maraming bilang 500,000,000,000 hakbang. Hindi mo maaaring talagang tuntuning panlahat Masyadong epektibo mula sa na at gumawa ng mabuting pasya sa disenyo kapag sumusulat ng mga programa. Kaya sabihin tumuon bagaman sa kung paano maaari naming gawing simple ang resultang ito. Kaya nai-highlight ko sa dilaw dito ang resulta ng n nakalapat na hinati sa 2, kaya isang milyong nakalapat hinati sa 2, at pagkatapos ay Nai-highlight ko kung ano ang ang tunay na sagot ay sa sandaling subtracted namin off n na hinati sa 2. At ang claim Pupunta ako sa gumawa ngayon ay, sino ang heck na pinahahalagahan mo kung ibawas off isang maliit na gulang n sa 2 kapag ang unang bahagi ng formula na ito ay kaya magkano ang mas malaki? Dominates nito ang iba pang mga na termino, n nakalapat na hinati sa 2 ay kaya magkano ang mas malaki, malinaw, bilang n ay makakakuha ng malaking tulad ng isang milyon, na mayroong talagang isang malaking pagkakaiba sa ang pagtatapos ng araw sa pagitan ng 500000000000 at 499999500000? Hindi talaga. At kaya kung ano ang namin ang pagpunta sa gawin bilang mga siyentipiko computer ay huwag pansinin ang mga mas mababang mga tuntunin ng order at kumuha ng isang bagay na tulad nito at talaga gawing simple lamang ito sa taning na pupuntahan mahalaga. Ang mas malaki ang aming hanay ng data makakuha ng, ang mas malaking aming database makakuha ng, ang higit pang mga pahina ng web mayroon kaming upang maghanap, ang higit pa mga kaibigan na mayroon ka sa Facebook. Bilang n nakakakuha ng mas malaki, hindi namin talaga pagpunta sa nagmamalasakit sa pinakamalaking termino sa anumang naturang pag-aaral ng ang aming mga algorithm pagganap. At pupuntahan ko sabihin, alam mo kung ano ang, bubble uri ay sa pagkakasunud-sunod ng malaking O, sa pagkakasunud-sunod ng n nakalapat. Ito ay hindi eksakto n nakalapat bilang nasaksihan namin, ngunit sino ba talagang pinahahalagahan tungkol sa mga mas maliit na mga termino, at tapat, na talagang pinahahalagahan ng kung hinati namin sa pamamagitan ng 2? Ito lamang ay isang pare-pareho factor. At 500000000000 kumpara sa 250 bilyon talaga na malaki ng isang deal? Maaari ko lang maghintay ng isang taon, hayaan ang aking laptop na literal makakuha ng dalawang beses nang mas mabilis sa hardware, at na uri ng mga pagkakaiba natural lang napupunta ang layo sa paglipas ng panahon. Ano pinapahalagahan namin tungkol ay ang expression, ang bahagi ng mga expression na pupuntahan mag-iba bilang aming input ay nakakakuha ng mas malaki at mas malalaking. At sa katunayan, sa tunay na mundo, na kung ano ang nangyayari lalong ay ang input sa aming mga problema at algorithm ay nakakakuha ng mas malaki. Kaya malaki O ay magiging ang pagtatanda, ang asymptotic pagtatanda, na namin lamang gamitin bilang mga siyentipiko computer upang ilarawan ang pagganap, o mga oras sa pagtakbo, ng isang algorithm. Upang maaari naming ihambing ang mga algorithm sa iba't ibang mga computer nakasulat sa pamamagitan ng iba't ibang mga tao, sa pamamagitan ng paggamit ilang fundamentally katulad na sukatan tulad ng bilang ng mga paghahambing ikaw ay paggawa, o marahil ang bilang ng mga swaps nagsasagawa ka ng. Ano ang hindi namin pagpunta sa count ay ang halaga ng oras na pumasa sa orasan sa pader karaniwang. Ano ang hindi namin pagpunta sa mag-alala tungkol ay kung magkano ang memorya gumagamit ka ngayon sa hindi bababa sa, bagaman na isa pang mapagkukunan na maaari naming sukatin. Kami ay pagpunta sa subukan upang ibabase ang aming pagsusuri sa lamang ang pangunahing mga pagpapatakbo, ang mga taong, tapat, na maaari mong makita ang pinaka-biswal. Kaya may isang bagay tulad ng malaking O ng n nakalapat, inaangkin ko na O ng n nakalapat ay isang pang-itaas bound sa tinatawag na oras ng paggana ng bubble-uuri. Sa ibang salita, kung ikaw Nais upang i-claim na mayroong ito mataas na limitasyon sa kung gaano karaming hakbang ay maaaring tumagal ng isang algorithm, itong ibang mapupuntahan na nasa malaking O ng n nakalapat sa kasong ito, isang pang-itaas nakatali. Paano kung ako sa halip baguhin ang kuwento na hindi tungkol sa bubble-uuri, ngunit tungkol sa itaas na hangganan. Maaari mong isipin ang isang algorithm na Tiningnan namin sa na na kung saan ang itaas na hangganan, maximum sukatin ng oras o mga pagpapatakbo, ay nagsabi na bounded sa pamamagitan ng n, isang linear function, hindi isang isa quadratic na Kurbadong? Ano ang isang algorithm na laging tumatagal ng hindi hihigit kaysa tulad ng n hakbang, o 2n mga hakbang, o mga hakbang 3n? Oo? Madla: Paghahanap ng mga pinakamalaking bilang sa isang listahan? Tagapagsalita: Ganap, paghahanap ang pinakamalaking bilang sa isang listahan. Kapag ako ay bibigyan ng isang listahan ng mga mga tao halimbawa, bawat isa sa kung sino ang humahawak ng isang numero, kung ano ang maximum na bilang ng hakbang na dapat itong tumagal sa akin, isang makatwirang matalinong tao, upang mahanap ang pinakamalaking tao sa listahang iyon? n, tama? Dahil sa ang pinakamasama kaso, kung saan ang ay maaaring ang pinakamalaking halaga? Mag-right, ang lahat ng mga paraan sa dulo. Kaya sa mga pinakamasama kaso upper bound, maaari ko kailangang pumunta lahat ng mga paraan sa paglipas dito at dapat tulad ng, oh, narito ang numero ng walong, o kahit anong halaga na hindi. Ngayon magiging hangal lamang kung iningatan ko pagpunta, i-right? Naghahanap ng higit pa at higit pang mga elemento kung ang huli sa kanila ay banda roon? Kaya tiyak, n ay isang pang-itaas nakatali. Hindi ko na kailangang gumawa ng higit pang hakbang kaysa iyon. Kaya kung ano kung sa halip ipinanukalang ko na may mga algorithm sa mundo na magkaroon ng oras tumatakbo na bounded sa pamamagitan ng malaking O ng log n, mag-log n? Saan nakita namin na ito bago? Oo? Madla: Sa problema phone book? Tagapagsalita: Tulad ng problema phone book. Ano ang sukatan ng kung gaano karaming oras o kung gaano karaming mga luha ito kinuha sa akin upang mahanap ang isang tao tulad ng Mike Smith sa aklat ng telepono? Inaangkin namin na ito ay log n, at kahit na hindi pamilyar o ito ito ay medyo hazy kung ano ang isang logarithm o exponent ay, tandaan lamang na ang log n sa pangkalahatan ay tumutukoy sa proseso, sa kasong ito, ng paghahati damit na yari sa kalahati muli, at muli, at muli, at muli, tulad na ito ay makakakuha ng mas maliit na tulad ng iyong ginagawa iyon. Kaya mag-log ng n tumutukoy, sigurado, sa halimbawa sa aklat ng telepono, sa binary paghahanap sa teorya, kung kailan namin Nagkaroon ng virtual na mga pinto sa board, o kapag Sean noon ay na naghahanap ng isang bagay. Kung gumamit siya ng binary paghahanap, mag-log n ay magiging sa itaas na hangganan sa kung magkano oras na tumatagal. Ngunit ang mga algorithm na ang bumangga sa Mag-log n ipinapalagay kung ano ang detalye ng key? Na ang listahan ay pinagsunod-sunod, i-right? Ang iyong algorithm ay mali kung iyong input ay hindi pinagsunod-sunod, at pa gumagamit ka ng isang bagay tulad ng binary paghahanap dahil maaari kang tumalon karapatan sa ibabaw ng elemento nang hindi napagtatanto ito ay sa katunayan doon. Ngayon kung ano ang maaaring sabihin nito, malaki O ng isa? Hindi ito nangangahulugan na ang iyong algorithm tumatagal ng isa at isa lamang hakbang, Nangangahulugan ito lamang tumatagal ng isang pare-pareho ang bilang ng mga hakbang. Siguro ito ay 1, marahil ito ay 10, marahil ito ay 1,000, ngunit ito ay hiwalay sa ang laki ng problema. Hindi mahalaga kung gaano kalaki n ay, isang pare-pareho ang oras algorithm laging tumatagal ang parehong bilang ng mga hakbang. Kaya kung ano ang maaaring maging isang algorithm nai-usapan natin ang tungkol sa o lamang intuitively na pagdating sa iyo na palaging tumatakbo sa tinatawag na pare-pareho ang oras? Oo? Madla: Magdagdag ng dalawang numero. Tagapagsalita: Magdagdag ng dalawang mga numero, 2 plus 2 ay katumbas ng 4, tapos na. Kaya na maaaring gumana, ano pa? Paano ang tungkol sa higit pang mga tunay na mundo, Oo? Madla: Paghahanap ng mga unang bagay sa isang listahan. Tagapagsalita: Paghahanap ng mga unang sangkap sa isang listahan, siguraduhin. Namin ang aktwal na pakikipag-usap tungkol sa array na, paano mo makukuha sa unang elemento sa isang array, hindi mahalaga kung gaano katagal ang array ay nasa C code? Gamitin mo lang tulad ng bracket zero pagtatanda, Bam, nandoon ka. At sa katunayan array, bilang isang bukod, suporta ng isang bagay na sa pangkalahatan ay kilala bilang random access, random access memorya, dahil maaari ka nang literal tumalon sa anumang isang lugar. Maaari naming gawin ito kahit na higit pa lamang maaari naming rewind sa linggo zero kapag ginawa namin sa simula. Magkano oras ay tumagal para sa sabihin block sa simula upang maisagawa? Pare-pareho lang ng oras, tama? Sabihing isang bagay, sabihin natin isang bagay, hindi mahalaga kung gaano kalaki ang mga gasgas mundo ay, ito ay palaging pagpunta sa gawin ang parehong dami ng oras upang sabihin lamang ng isang bagay. Kaya na pare-pareho ang oras, ngunit ano ang flip side? Kung na-itaas hangganan, paano kung gusto naming upang ilarawan ang mas mababang mga hangganan ng aming mga algorithm sa pagtakbo ang oras? Halos isang pinakamahusay na kaso potensyal na, kung gagawin mo, bagaman ang mga terminong ito maaaring ilapat sa mga pinakamahusay na kaso, pinakamasama kaso, average na mga kaso nang higit pa Sa pangkalahatan, ngunit hayaan ang pagtuon ni lamang sa mas mababang hangganan sa mas pangkalahatang paraan. Ano ang isang algorithm na iyon ay mayroon isang mas mababang bound ng n hakbang, o 2n mga hakbang, o mga hakbang 3n? Ang ilang mga salik ng n hakbang, na mas mababa ang hangganan. Oo? Madla: Bubble-uri-uriin? Tagapagsalita: Bubble-uri-uriin tumatagal Nagnais mo n hakbang na ito, bakit? Bakit na? Bakit dapat na pagsisimula darating sa iyo intuitively, kahit na ito ay hindi lamang pa? Oo? Madla: [INAUDIBLE]. Tagapagsalita: Mismong. Sa pinakamahusay na posibleng mga sitwasyon ng uri ng bubble, at maraming mga algorithm, kung ipasa ko sa inyo walong tao na na pinagsunod-sunod, magiging hangal para sa iyo, ang algorithm, upang bumalik-balik higit sa isang beses, tama? Dahil sa lalong madaling mo maglakad sa pamamagitan ng mga listahan nang isang beses, dapat mong mapagtanto, oh, ginawa ko walang swaps, list na ito ay pinagsunod-sunod, lumabas. Ngunit na pupuntahan magdadala sa iyo n hakbang. At kabaligtaran, kung ano ang isa pang paraan ng pag-iisip tungkol dito? Bubble-uri-uriin ay isang wakas, kaya upang makipag-usap, ng n, dahil kung tiningnan mo ang mas kaunti sa n elemento, kung ano ay ang pangunahing mga isyu doon? Hindi mo alam kung ito ay pinagsunod-sunod, i-right. Mga tao namin na maaaring sulyap sa walong mga tao at maging tulad ng, oh, ito ay pinagsunod-sunod, na hindi dalhin ako n hakbang na ito, ngunit ito ginawa. Ang iyong mga mata, kahit na na-uri ng may malaking field ng paningin, ikaw ay tumingin sa walong mga elemento, ikaw ay tumingin sa walong mga tao, na walong hakbang na ito nang epektibo. At lamang kung lumakad ako sa pamamagitan ng buong listahan gawin Napag-alaman kong, oo, pinagsunod-sunod. Kung ihihinto ko kalahatian pag-iisip, ang lahat karapatan, kaakit-akit na ito ay pinagsunod-sunod sa ngayon, kung ano ang mga logro hindi ito pinagsunod-sunod? Na algorithm hindi magiging tama. Maaaring maging mas mabilis, ngunit hindi tama. Kaya ngayon ay mayroon kaming isang paraan ng na naglalarawan ng isang mas mababang hangganan, at kung ano ang tungkol sa pare-pareho ang oras? Ano ang isang algorithm na may mas mababang nakatali sa running time nito sa isa? 1 na hakbang, 2 hakbang, 10 mga hakbang, pero pare-pareho, independiyenteng ng n, ang laki ng input? Oo, sa likod. Madla: Printf? Tagapagsalita: Ano iyon? Madla: Printf? Tagapagsalita: Printf. OK, sigurado. Kaya gumugugol ito ng nakapirming bilang ng mga hakbang. At ang dapat kong now-- ngayon na kami ay pakikipag-usap tungkol sa C code at hindi sa simula, isang bagay tulad ng sabihin nating, na may printf, dapat namin simulan upang makakuha ng maingat. Dahil printf aabutin input, ito ay isang string, at mga string ay technically mayroon haba. Kaya kung nais namin ngayon upang pumili sa iyo, kung ikaw ay hindi bale na gawin, technically na maaari kaming argue na printf aabutin ng isang variable na haba ng pag-input, at tiyak na maaaring tumagal ito nang higit pa oras upang i-print ang isang string na ito ang haba, kaysa ito mahaba. Kaya kung ano kung isinasaalang-alang namin lamang ang pag-uuri at paghahanap ng mga halimbawa? Paano ang tungkol sa Mike Smith sa telepono aklat, o binary paghahanap sa mas pangkalahatang? Sa pinakamahusay na kaso, kung ano ang maaaring mangyari? Buksan ko ang phone book at, Bam, mayroong Mike Smith numero. Maaari ko sa kanya tumawag agad-agad. Kinuha isang hakbang, siguro dalawang hakbang, ngunit isang pare-pareho ang bilang ng mga hakbang kung Nakatanggap ako masuwerteng. At tapat, nakita namin sa Lunes iyong kaklase makakuha ng masyadong masuwerteng dalawang beses sa isang hilera. At iyon ay sa katunayan pare-pareho oras sa isang mas mababang hangganan sa algorithm na pinag-uusapan para sa paghahanap ng ang bilang 50 sa likod ng mga sarado pintuan. Ngayon, bilang isang bukod, kung matuklasan mo na parehong malaki O, sa itaas na hangganan, at wakas, ang mas mababang nakatali, ay isa sa parehong, na ay ang parehong formula sa panaklong, maaari ring mo sabihin, upang maging fancy lamang, na may isang bagay ay nasa theta ng n o theta ng ilang iba pang mga halaga. Iyon ay nangangahulugan lamang kapag malaki Oh at wakas ay pareho. Kung ano ang tungkol sa uri seleksyon ngayon? Gumamit ng bagong bokabularyo Hayaan. Sa uri seleksyon, ano ang mga namin paggawa muli, at muli, at muli? Ako ay pagpunta pabalik-balik sa pamamagitan ng sa listahan, naghahanap ng kanino? Ang pinakamaliit na numero. Kaya kung gaano karaming mga hakbang na ito, kung paano maraming mga paghahambing ng ginawa ko mayroon upang gawing upang malaman kung sino ang pinakamaliit na elemento sa listahan ay? n minus 1, tama? Dahil kung magsimulang lang ako sa isa ako given at ako magsisimulang paghahambing sa kanya, pagkatapos ay sa kanya, siya o ang kanyang, kanya, ako Maaari lamang ipares ang mga elemento magkasama n minus 1 beses. Kaya uri kaparehong tumatagal seleksyon n minus 1 hakbang sa unang pagkakataon. Ilang hakbang na ito ay tumagal sa akin upang hanapin ang pangalawang pinakamaliliit na elemento? n minus 2, dahil ako sa pagiging pipi kung ako patuloy na pagtingin sa parehong mga tao muli kung ang napili na ako sa kanya o ang kanyang at ilagay ang mga ito sa kanilang lugar. At ang ikatlong hakbang, n minus 3, pagkatapos n minus 4. Nakakita kami ang pattern na ito bago, at sa katunayan pagpili ng uri kaparehong May isang pang-itaas nakatali ng n nakalapat kung gagawin up namin na kabuuan. Ano ang kanyang mas mababang nakatali, uri seleksyon? Nagnais, kung magkano ang seleksyon kailangang oras uri tumagal, gaya ng nilinaw namin ito sa Lunes? Ipanukala dalawang pagpipilian. Siguro ito ay n, tulad ng dati. Siguro ito n nakalapat, pati na ito na ngayon ang bilang sa itaas na hangganan. Madla: n nakalapat. Tagapagsalita: n nakalapat. Bakit? Madla: Dahil mayroon kang upang tukuyin ang [INAUDIBLE]. Tagapagsalita: Mismong. Hindi bababa sa gaya ng nilinaw ko maisasa-ayos seleksyon ito ay medyo walang muwang, panatilihin ang pagpunta, hanapin ang pinakamaliit na elemento. Pumunta muli, hanapin ang pinakamaliit na elemento. Pumunta muli, hanapin ang pinakamaliit na elemento. Walang uri ng sa pag-optimize sa doon na maaaring ipaalam sa akin i-abort matapos hakbang lamang n o kaya. Kaya nga, seleksyon -uri-uriin, wakas ng n nakalapat. Paano ang tungkol sa uri ng pagpapasok ng, kung saan kinuha ko na ako ay ibinigay, at pagkatapos ay plopped ko sa kanya o ang kanyang sa tamang lugar? Pagkatapos ay nagpatuloy ako sa ikalawang tao, plopped kanya sa tamang lugar. Pagkatapos ng susunod na tao, plopped sa kanya sa tamang lugar. Pansinin na ito ay napaka linear, kaya upang makipag-usap. Ako ay isang tuwid na linya, ako hindi pagpunta pabalik-balik, Hindi pa ko naghahanap bumalik talaga ito, ngunit kung ano ang nangyayari kapag ipasok ko sa kanya o ang kanyang sa simula ng ang listahan tulad ng ginawa namin sa Lunes? Anong nangyayari? Oo? Madla: [INAUDIBLE]. Tagapagsalita: Oo, na ay ang catch, tama? Maaari mong isipin ang mula sa ang iyong mga kamag-aral, kung ang mga ito ay ang pagsasagawa ng anumang pagkilos sa ang kanilang mga paa, na noon ay isang operasyon. Kaya kung mayroong tatlong mga tao dito at ang bagong tao aari paraan banda roon, sa isang mahabang yugto tulad nito, sigurado, siya o maaaring siya pumunta lamang sa dulo napaka. Ngunit kung pinag-iisipan mo kami tungkol sa isang computer at isang array ng memorya, ang mga taong ito ay pumunta sa upang i-shuffle sa ibabaw para gumawa nang lugar para sa taong iyon. At nang sa gayon ay n minus 1 shufflings, n minus 2 shufflings, n minus 3 shufflings lamang ang uri ng nangyayari sa likod ng akin, hindi sa harap ng akin tulad ng dati, sa ilang mga kahulugan. Ngayon bilang isang bukod, at bilang maaaring nakakita ka online kung nagsimula ka ng poking sa paligid tungkol sa mga uri, mayroong kaya maraming iba't ibang mga bago Nariyan lang, ang ilan sa kanila mas mahusay kaysa sa iba. Sa katunayan, bogosort ay isa na uri ng masaya upang tumingin hanggang. Bogosort tumatagal ng isang hanay ng mga numero o sinasabi ng isang deck ng mga baraha, random shuffles sa kanila, at mga tseke kung ang mga ito ay pinagsunod-sunod. At kung hindi, ginagawa itong muli. At kung hindi, ginagawa itong muli. Kung hindi, ginagawa itong muli. Hindi kapani-paniwalang hangal. At sa katunayan, kung basahin mo tulad ng mga artikulo sa Wikipedia, palayaw nito ay hangal uri. Ito ay malaon gumana, sana ay, na ibinigay ng sapat na panahon, ngunit na dami ng oras Maaaring magtagal pa masyadong ilang panahon. Kaya kung kaya kong, sabihin bilis bagay up mula sa halimbawa ni Maria Beth ng mas maaga, sa pamamagitan ng pagkakaroon ng ilang higit pang mga elemento, ngunit dalawang higit pang mga processors. Dalawang mga tao, kung ikaw hindi bale na sumali sa akin. Paano ang tungkol sa 1 sa ibabaw dito, at go-- ni walang sinuman banda roon ipaalam? Walang isa na iyon? OK. Ikaw na may itim shirt, oo, dumating pababa. Ang lahat ng mga karapatan, kung ano ang iyong pangalan? Madla: Peter. Tagapagsalita: Ano iyon? Madla: Peter. Tagapagsalita: Pedro, David, mabait sa matugunan mo. Ang lahat ng mga karapatan, mayroon kaming Peter dito, kung ikaw nais na dumating sa talahanayan sa paglipas dito. At kung ano ang iyong pangalan? Madla: Elena. Tagapagsalita: Elena. OK, mabait sa matugunan mo. Elena matugunan Peter. Peter, Elena. At kailangan nating Andrew up dito pati na rin, pakiusap. At ang iyong mga hamon ay pagpunta upang maging upang pagbukud-bukurin ang isang deck ng mga baraha. At kung hindi pamilyar, deck ng mga baraha dapat sa huli ay pinagsunod-sunod ng kaunti ng isang bagay tulad ng na ito kung saan kami na ang mga club, pagkatapos ay ang spades, pagkatapos ay ang puso at diamante, mula sa ACE bilang isa, ang lahat ng mga paraan ng hanggang sa hari. Ang mga kard Pupunta ako sa magbibigay sa iyo ng ay magiging 52 sa dami. Kami ay pagpunta sa kaparehong oras ka, sa sandali lamang. Kami ay pagpunta sa magtapon ng Andrew hanggang sa screen dito, kaya bilang upang panoorin bilang gawin mo ito. At upang ang lahat ng ito ay ang lahat ng mga mas nakikita, ang mga ito ay ang mga card Nakatanggap ako sa Amazon. Kaya ang mga ito ay mayroon nang sapalaran pinagsunod-sunod, at kami ay pagpunta sa minsan sa iyo. At kami ay pagpunta sa panatilihin itong real time na ito, kaya kami ay pagpunta upang subukang i-presyon ka dahil kung hindi man ito ay makakakuha nakakainip mabilis. Kung maaari kang magpatuloy upang pagbukud-bukurin 52 mga elemento nang magkasama sa pamamagitan ng ilang mga paraan, na ngayon. At muli, habang pinapanood namin ang mga guys kung ano, gawin sa dulo Mawawala na upang makabuo ng isang halata resulta, isipin ang tungkol talaga kung paano sila bawat paggawa nito, kung paano maaari mong ilarawan ito. Dahil muli, ang mga ito ay lahat ng mga proseso, mga algorithm na lubos naming para sa ipinagkaloob bilang isang tao. Ngunit mo na marahil ay nagkaroon mahaba Swersey, katagal bago mo kahit na naisip tungkol sa pagkuha ng isang computer science klase mo Maaaring nagkaroon ang Swersey na may na lutasin ang mga problema tulad nito. Ngunit sa sandaling makilala ka ang mga pattern at simulan upang gawing pormal ang mga hakbang kung saan naka-solve ang mga problemang ito, makikita mo na maaari mong malutas magkano higit pa kawili-wili at marami pang iba complex mga problema nang mabilis. Kaya ang isang tao mula sa madla, kung ano ang hindi bababa sa isang elemento ng algorithm na ginagamit nila dito? Madla: [INAUDIBLE] Tagapagsalita: Ano iyon? Madla: Sa pamamagitan ng suit. Tagapagsalita: Sa pamamagitan ng suit. Kaya unang ay clustering sila ang lahat ng mga diamante magkasama ito ay tila, ang lahat ng mga puso-sama ito ay tila, at iba pa, nang walang paggalang para sa mga numero sa mga baraha. At ngayon lumilitaw ang mga ito, halimbawa, na pag-uuri ang mga ito sa pamamagitan ng numero. Napakabuti. Ang lahat ng mga karapatan, kaya kung ano ang nangyayari sa maging ang huling hakbang pagkatapos dito? Sa sandaling mayroon kami ng apat na pinagsunod-sunod paghahabla, kung ano ang kailangan naming gawin sa apat na piles upang makamit isa pinagsunod-sunod deck, medyo simple? Kaya kailangan namin upang sumanib muli ang mga ito. Kaya mayroong isang kawili-wiling ideya na ang muli, daresay, ay napaka madaling maunawaan kahit na kung maaari mong hindi kailanman na-slapped na uri ng label na ito. Ang mga pangunahing paniwala ng paghahati ang problema wala sa kalahati oras na ito, ngunit hindi bababa sa apat na piraso. Paglutas halos fundamentally magkatulad na mga problema sa paghihiwalay ng bawat isa, at pagkatapos ay pinagsasama ang mga resulta. At, mahusay na, tapos na. Ang lahat ng mga karapatan, isang malaking bilog ng applause, kung magagawa namin. [APPLAUSE] Tagapagsalita: wala akong mga ideya kung ano ikaw gawin sa mga ito, ngunit dito mo pumunta. Salamat sa iyo kaya magkano. Kaya hayaan makita, ang dalawang minuto at walong segundo, kung nais mong hamunin ang iyong mga kaibigan. Ano pagkatapos ay pagpunta sa maging isang tumagal ang layo mula sa na ito na maaari naming magamit sa mas pangkalahatang? Well, sa tingin pabalik sa ito array ng mga numero, at sa tingin bumalik ngayon sa ilan sa mga pseudocode na naisulat namin sa nakaraan, at ito ay ang pseudocode para sa paglutas sa problema phone book. Kung saan sa pseudocode ko enumerated isang mas sistema paraan ng na naglalarawan kung paano ko ginawang isang napaka-intuitive algorithm ng pag-divide ng telepono ng tao aklat sa kalahati, ulitin, ulitin, ulitin, hanggang sa mahanap ako ng isang tao tulad ng Mike Smith, kung siya ay sa katunayan sa aklat telepono. Ngunit uri ng ko ginamit kung ano Tatawag ako isang napaka-iterative diskarte dito, sa partikular na notice sa linya 8 at 11 linya. Iyon ang mga ebidensiya ng isang iterative diskarteng ito, ang diskarteng looping, dahil iyon mismo ang pag-uugali nila humimok. Yaong parehong linya sabihin pumunta sa tatlong linya, at maaari mong uri ng isipin na iyon sa iyong mata isip bilang sa pagiging isang loop. Ay nagsasabi sa iyo ito upang bumalik up sa hakbang tatlong at ulitin, muli, at muli, at muli. Ngunit paano kung makakuha kami ng isang key ideya dito na ginawa namin hindi sa huling pagkakataon, at padaliin ang 8 linya at line 11 at ang kanilang mga kapitbahay bilang lamang ito, sa kulay dilaw. Ito ay hindi fundamentally ang pagpapaikli ang pseudocode Sobra, ngunit fundamentally ito pagbabago ang likas na katangian ng aking mga algorithm. Ano ngayon ang gagawin ko sinasabi sa hakbang 7, sa hakbang 10, ay upang maghanap para sa Mike sa eksaktong magkatulad na paraan, ngunit lamang sa kaliwang kalahati o ang karapatan sa kalahati. Kaya sa ibang salita, kung Sisimulan ko mula sa unang hakbang, kunin phone book, bukas sa gitna ng phone book, tumingin sa mga pangalan, kung Smith ay kabilang sa pangalan, tawagan Mike, iba pa kung Smith ay mas maaga sa libro, magbasa-pitong maghanap para sa Mike sa kaliwang kalahati ng libro. Ngunit na uri ng pakiramdam ng tulad ng ito ay nag-iiwan sa akin nakikipag-hang, tama? Sa dilaw, ay isang pagtuturo, ngunit kung paano gagawin ko maghanap para sa Mike sa kaliwang kalahati ng phone book? Saan Mayroon akong isang algorithm na kung saan ako maaaring maghanap para sa isang tao tulad ng Mike Smith? Well, ito ay staring sa amin sa mukha. Maaari ko literal gamitin ang eksaktong parehong programa epektibo ng pagpunta hanggang sa tuktok tumakbo muling muli at ang parehong linya ng code. Kaya kahit na ito ay dapat na sa tingin tulad ng isang bit ng isang paikot-ikot kahulugan kung saan ka ng pagsagot ng isang tao ang tanong sa pamamagitan lamang uri ng pagtatanong muli ng parehong tanong, tulad ng kung bakit, bakit, bakit? Ang katotohanan ay dahil mahirap na namin ang naka-code isang pares ng mga espesyal na mga linya, na hakbang 4, kung saan ay isang kung, at hakbang 12, na ay epektibo ng isa pang sangay, dahil mayroon kaming mga stopgap mga panukala, algorithm na ito ay magwawakas kung namin hanapin Mike, o kung hindi namin. Ngunit sa hakbang 7 at 10 ngayon, mayroon kaming kung ano ang makikita namin tumawag sa isang recursive algorithm. At recursion ay sa katunayan isang malakas na ideya na ang isang ilan isip bending sa una, maaari naming ngayong mag-apply tulad ng sumusunod. Pagsamahin ang uri-uriin ang magiging huling uri na tinitingnan namin ang, hindi bababa sa klase pormal. At ito ay fundamentally iba't ibang mula sa mga huling tatlong, at tiyak huling apat na kung isama namin bogosort. Narito ang pseudocode para sa uri merge. Kapag sa input ng n elemento, kaya ibinigay isang hanay ng mga sukat n, kung n ay mas mababa sa 2, bumalik. Kaya bakit mayroon akong na katinuan suriin muna? Ano ang implikasyon kung ipasa ko sa iyo isang array na kung saan ang haba n Mababa sa 2? Na-pinagsunod-sunod, malinaw naman, tama? Dahil ang listahan ng alinman sa may ang isang elemento, na kung saan ay trivially pinagsunod-sunod dahil ito ay ang tanging bagay doon. O kaya naman, ito ay ang laki ng zero na nangangahulugang walang upang pagbukud-bukurin ang, kaya sa pamamagitan ng kalikasan ito ay pinagsunod-sunod. Mayroong walang lamang mali doon. Kaya na aming tinatawag na base kaso. Iyon ay katulad sa espiritu sa kung ano ang ginawa namin gamit ang Mike. Kung ni Mike sa aklat ng telepono, tumawag sa kanya. Kung siya ay hindi doon, ibigay up. Ito ay isang tinatawag na base kaso, upang matiyak ito algorithm sa pagtatapos ng araw Hihinto sa ilang mga pangyayari. Ngunit narito ang hakbang ng pananampalataya ngayon, iba pa, -uri-uriin ang kaliwang kalahati ng mga elemento, pagkatapos ay i-uri-uriin ang karapatan kalahati ng mga elemento, at pagkatapos ay pagsamahin ang pinagsunod-sunod halves. At narito ang kung saan ito nararamdaman tulad kami copping out. Tinanong ko ang upang pagbukud-bukurin sa iyo n elemento, at ako na nagsasabi, OK, huwag ito sa pamamagitan ng pag-uuri sa kaliwa at sa pag-aayos sa kanan. Ngunit ako ay sinasabi ng isang iba pang mga bagay, at ito ay ang susi tema ito ay tila sa Swersey kaya sa ngayon, mayroong ito ikatlong hakbang ng pagbubuklod. Aling kahit na ito Mukhang kaya pipi sa espiritu, tulad ng sumanib lamang bagay magkasama, tila upang maging isang mahalagang hakbang patungo sa reassembly ng dalawang mga problema na ay hinati sa huli sa kalahati. Kaya sumanib-uri-uriin, ni gawin ito ipaalam, kung ikaw ay katatawanan sa akin, may isa pang demonstration, kaya lang na mayroon kaming ilang mga mga numero upang gumana sa. Maaari ba akong makipagpalitan ng walong ang stress bola para sa walong tao? Ang lahat ng mga karapatan, kung paano tungkol sa iyo tatlong, mo apat sa seksiyong ito, limang, anim, at sabihin huwag 7, 8, dumating sa up. OK, Oo OK. Minus 8, doon pumunta kami, plus 1. Mahusay. Lahat ng karapatan ay sa up, sabihin mabilis na magbibigay sa iyo ng mga numero. Numero ng dalawang, numero ng tatlong, numero ng apat, numero ng limang, anim, pitong, at walong. Ginawa ko nang tama ang walong oras na ito. OK, kaya sige kung magagawa mo, at ni-uri-uriin sa orihinal na pagkakasunud-sunod hayaan na nagkaroon kami kahapon kung saan ay tumingin tulad nito, kung hindi mo nais na bale. At gawin ni ito sa harap ng table ipaalam. Ang lahat ng mga karapatan, kaya pagsamahin-uri-uriin. Ito ay kung saan ito ang nangyayari upang makakuha ng mga uri ng kawili-wili, dahil mukhang ako na nagbibigay sa aking sarili kaya higit na mas mababa impormasyon ngayon. Kaya sumanib-uri-uriin una sa lahat sa input ng n elemento, at ito ay malinaw naman hindi kukulangin sa dalawang, ito ay walo, kaya bang makakuha ng ilang pang trabaho na gawin. Kaya ngayon itak namin bilang isang klase na ngayon sa ibang sangay, na nangangahulugan tatlong hakbang. Una, mayroon akong upang ayusin ang kaliwang kalahati ng mga elemento. Kaya paano ko pumunta tungkol sa paggawa na ito? Well, ako ako pagpunta sa uri ng itak hatiin ang listahan dito, hindi mo kailangang i- pisikal na ilipat, at ako pagpunta upang tumutok lamang sa mga kaliwang kalahati ng mga elemento dito. Kaya paano ko pumunta ako tungkol sa pag-uuri isang listahan ngayon ng apat na laki? Ano ang aking algorithm? Una kong suriin ay n mas mababa kaysa sa dalawang, hindi, kaya magpatuloy ko muli sa ibang block. Pagsunud-sunurin ayon kaliwa kalahati ng mga elemento. Kaya ngayon muli, itak, at ito ay kung saan Mayroon kang nakakaipon ng maraming sakit sa kasaysayan, kung gagawin mo. Ngayon ako sa pag-aayos sa kaliwa kalahati ng kaliwang kalahati. Ang lahat ng mga karapatan, kaya ngayon Tinatawag kong aking parehong pagsanib pag-uuri algorithm, ay n mas mababa sa dalawang? Hindi, ito ay dalawang, kaya Mayroon akong upang ayusin kaliwang kalahati, at ang kanang kalahati. Kaya dito pumunta kami, uri-uriin ang natitira kalahati. Bakit hindi mo pa lamang tumagal ng isang hakbang pasulong. Ano ang inyong pangalan? Madla: Darren. Tagapagsalita: Dan. Dan ay stepped pasulong. Madla: Darren. Tagapagsalita: Darren, tapos na. Sabihin mo ba Darren o Dan? Madla: Darren. Tagapagsalita: Darren. OK, Darren ay stepped pasulong at siya ay pinagsunod-sunod ngayon. At ito ay halos isang inane claim, tama? Huwag tila ko talagang i-pagkamit ng magpatuloy anumang bagay, ngunit hayaan. Ngayon ipaalam sa akin-uri-uriin ang karapatan kalahati ng mga elemento. Ano ang inyong pangalan? Madla: Luke. Tagapagsalita: Luke. Halika sa, magbasa-forward. Tapos, na-pinagsunod-sunod ko Lucas. Ang kaliwang kalahati ay pinagsunod-sunod ngayon at ang karapatan kalahati ay pinagsunod-sunod ngayon, ngunit muli, mayroong isang mahalagang hakbang dito. Ano ang susunod na kailangan kong gawin? Pagsamahin ang pinagsunod-sunod halves. Ngayon kami ay pagpunta sa may lamang lahat nang pabalik-balik sa ganitong paraan, dahil ko uri ng kailangan ilang espasyo sa simula. Ito ay halos tulad ng mga ito guys ay nasa isang mesa, at kailangan ko ang ilang mga kuwarto upang ilipat ang mga ito sa paligid sa. Kaya ako pupunta upang sumanib mo guys sa pamamagitan ng pagtingin sa kaliwang kalahati at ang kanang kalahati. At malinaw naman kung sino ang mauuna, iniwan kalahati o pakanan kalahati? Kaya kanang kalahati, kaya ni Lucas ilipat sa paglipas ng ipaalam dito sa orihinal na posisyon Darren iyon. At ngayon upang pagsamahin ang kanilang kaliwang kalahati in, Darren pupuntahan ilipat mula doon. Kaya pakiramdam ng tulad ng halos ang isang bubble ng uri ng epekto, ngunit ang aking pangunahing mga algorithm, napaka iba't ibang mga oras na ito. Ngunit ngayon kung saan ang mga bagay makakuha ng isang maliit na nakakainis na dahil ikaw mag-rewind itak kung saan nag-iwan ako off. Lamang ako ng Pinagsama ang Pinagbukud-bukod halves, na nangangahulugan na ako kung saan sa aking mga algorithm? Mayroon akong upang pagbukud-bukurin ang karapatan kalahati, tama? Kung rewind, literal sa video, ipapakita sa iyo makita na Nakakuha kami upang ito punto ni Lucas at Darren sa pamamagitan ng pag-uuri sa kaliwa kalahati ng kaliwang kalahati. Pagkatapos Pinagsama namin ang mga Pinagbukud-bukod halves, na ay nangangahulugan na ang susunod na hakbang ay isang uri ng kanang kalahati ng kaliwang kalahati. Ang lahat ng mga karapatan, kaya sabihin gawin ito nang mas mabilis. Ang lahat ng mga karapatan, anim, pupuntahan ko upang i-claim ikaw ay pinagsunod-sunod ngayon, dumating sa pasulong. Ano ang inyong pangalan? Madla: Adriano. Tagapagsalita: Adriano. Adriano ay pinagsunod-sunod ngayon. At kung ano ang iyong pangalan? Madla: Alex. Tagapagsalita: Alex ay pinagsunod-sunod ngayon. Kaliwa kalahati, i-right kalahati, ano ang huling hakbang? Pagsamahin. Pretty trivia, kaya ako pagpunta upang sumanib sa anim, tumagal ng isang hakbang pabalik, walo, kumuha nang isang hakbang pabalik. At ngayon mapansin na ito ay isang kapaki-pakinabang takeaway, kung ano ngayon ay totoo tungkol sa kaliwang kalahati ng listahan, kanikanilang mga kung paano namin nagsimula? Ito ay pinagsunod-sunod. Ngayon hindi ito pinagsunod-sunod sa ang malaking scheme ng mga bagay, ngunit ito ay pinagsunod-sunod nang nakapag-iisa ng iba pang kalahati. Ngayon kung ano ang hakbang na ako sa kung panatilihing ako rewinding kung paano nagsimula ang kuwento? Ngayon Mayroon akong upang pagbukud-bukurin ang karapatan kalahati. Kaya ngayon kami ay paraan pabalik sa simula ng kuwento, at sabihin gawin ito nang higit pa mabilis. Kaya ako pagpunta sa uri-uriin ang kanang kalahati ng buong listahan. Ano ang susunod na hakbang? -Uri-uriin ang natitira sa kalahati ng mga karapatan kalahati. -Uri-uriin ang natitira kalahati ng kaliwang kalahati ng kanang kalahati. At kung ano ang iyong pangalan? Madla: Omar. Tagapagsalita: Omar, magbasa-forward, tapos na. Kaliwa kalahati ay pinagsunod-sunod. At kung ano ang iyong pangalan? Madla: Chris. Tagapagsalita: Chris, kumuha nang isang hakbang pasulong, ikaw ay pinagsunod-sunod ngayon. Ano ang mga pangunahing hakbang ngayon? Pagsamahin. Kaya isa ay pagpunta upang sumanib sa lugar dito, kung maaari kang kumuha ng isang hakbang pabalik, at tatlong ay pagpunta sa tumagal ng isang hakbang pabalik, pagsamahin. Kaya sa kaliwang kalahati ng kanang kalahati, ay pinagsunod-sunod ngayon. Tapat, pakiramdam ng algorithm na ito tulad ng namin ay aksaya paraan ng higit pang oras kaysa sa dati, ngunit kung ginawa namin ito sa real time, ipapakita namin tingnan kung ano ang takeaways pagpunta sa maging. Ngayon dito Ako, i-right kalahati ng kanang kalahati, hayaan mo akong sige at ayusin ang kaliwang kalahati. Hakbang pasulong, kung ano ang iyong pangalan? Madla: Ramsey. Tagapagsalita: Ramsey ay pinagsunod-sunod ngayon. Ano ang inyong pangalan? Madla: Marina. Tagapagsalita: Marina ay pinagsunod-sunod na ngayon bilang well, kung gagawin mo ng isang hakbang pasulong. Key hakbang dito ay sumanib ngayon, ako pagpunta sa pluck mula sa aking dalawang mga listahan, pakaliwa at pakanan. Limang ay pagpunta sa first come, at pitong ay pagpunta sa darating sa susunod. At muli, ito ay sinadya. Ang katotohanan na ito ay naka-pagkuha hakbang pasulong at pabalik Nakalaan lamang ito upang kumatawan na hindi namin maaari gawin algorithm na ito sa lugar na kasing-dali bilang uri ng bubble, at uri seleksyon, at uri ng pagpapasok ng kung saan kami lamang pinananatiling pagpapalit ng mga tao. Literal na kailangan ko ng isang sort ng scratch papel kung saan upang ilagay ang mga tao habang gagawin ko ang pagsasama, at pagkatapos ay maaari kong ilagay ang mga ito pabalik sa lugar. At iyon ang key dahil ako ako gamit ang isang bagong mapagkukunan, espasyo, hindi lamang oras. OK, ito ay kamangha-manghang. Kaliwa kalahati ay pinagsunod-sunod, i-right kalahati ay Pinagbukud-bukod, ngayon na key pinagsasama ang mga hakbang na ito. Paano ako pagpunta upang sumanib ito? Kaya kung makikita mo sundin ang aking pakaliwa kamay at kanang kamay, Pupunta ako upang ituro ang aking kaliwang kamay sa kaliwang kalahati, ang aking kanang kamay sa kanang kalahati, at ngayon Kailangan ko bang magpasya sunud-sunod kung kanino upang sumanib sa. Sino malinaw naman ang mauna? Numero ng isa. Kaya dumating sa paglipas dito, narito ang aming mga scratch pad. Kaya ngayon numero ng isa, at abiso kung ano ang makikita ko sa pamamagitan ng aking kanang kamay, Pupunta ako sa ilipat ang aking kanang kamay isa basa sa ibabaw upang ituro ang numero ng tatlong, at ngayon may kong gumawa ang parehong desisyon. At talagang tumayo karapatan sa harap ng Lucas dito kung magagawa mo, dahil ito ay ang aming mga scratch pad. Kaya sino ay susunod? Mayroon kaming Lucas na may numero ng dalawang o Chris na may numero ng tatlong. Malinaw Lucas, numero dalawa, kaya napunta ka dito. Ngunit ang aking kaliwang ngayon ay pagpunta sa ay incremented upang tumuro sa Darren, at narito ang key tumagal ang layo sa pagbubuklod, ako ako pagpunta sa panatilihin ang paggawa nito, malinaw naman, kung ikaw uri ng sundin ang logic. Ngunit ang aking mga kamay ay hindi kailanman pagpunta sa pumunta paurong, na ang ibig sabihin ay nakakaapekto lamang ako sa paglipat sa ang natitira sa aking proseso ng pagsasama, at na ang nangyayari upang maging susi sa aming pag-aaral sa isang sandali lamang. Kaya ng tapusin ito up mabilis na ngayon hayaan. Kaya tatlong ay susunod, pagkatapos ng apat na nanggagaling sa tabi, at ngayon ay limang susunod, pagkatapos ay i-anim, at pitong, at pagkatapos ay sa wakas ay alas-otso. Pakiramdam ng tulad ng pinakamabagal na algorithm pa, ngunit hindi namin kung talagang patakbuhin ito sa parehong uri bilis ng orasan, kaya upang makipag-usap, na may parehong ticking orasan tulad ng dati. Bakit? Well, Sabihin maglaan ng tumingin sa dulo ng resulta. Sabihin bumalik sa paglipas dito, ipaalam sa akin hilahin up sa isang demonstration biswal ng kung ano ang ginawa namin lamang. Ang pag-zoom in dito, sa na ito pahina dito, na nagsasabi sa Firefox na nais naming mag-lilinya hanggang sa kahong ito, sabihin sabihin bubble-uri-uriin, kung saan Ikinalulungkot namin ngayon na rin pamilyar, uri pinili, na kung saan ay isa pang medyo prangka isa, at ngayon uri pagsanib ngayon, na Magiging aming climactic nagtatapos. Ang dahilan kung bakit ito kinuha kaya mas matagal dito sa mga kawani na tao at ako ay pasalita, malinaw naman, ako ko na nagpapaliwanag sa bawat hakbang. Ngunit kung execute mo lang ito, magkano tulad ng ginawa namin bubble-uri-uriin at seleksyon uri hindi lamang biswal, sa panonood paano lamang magkano ang mas mahusay ito sinusulit ng dibisyon at conquering Pwedeng kapag inilapat sa isang hanay ng data na Hindi kahit na laki ng walong, ngunit kahit magkano, magkano ang mas malaking. Bigyan ko bang pagsamahin mo uri, tabi- gilid sa iba pang mga algorithm. Ito ay pagpunta upang makakuha ng masakit mabilis, at ang nagtatapos ay hindi partikular na climactic, tapusin lang nila up pinagsunod-sunod. Ngunit ang susi tumagal ang layo ay na hitsura kung magkano ang mas mabilis na bumaybay-uri ay, maliban kung sa tingin mo ako lamang uri ng panggugulo sa iyo. Kung gagawin namin ito ng isang huling oras, Hinahayaan ni-reload ito, sabihin bumalik at pumili ng bubble uri, at para lamang sa mga kicks, hayaan pumili ng pagpapasok -uri-uriin, para lamang sa mabuting panukala. At oras na ito muli, sabihin pumili ng uri merge at sabihin talaga tumakbo ang mga magkatabi. At ito ay hindi, sa katunayan, isang fluke. Ano mabisang ko nagawa mo na ay na hindi ko na hinati ang aking input sa kalahati, muli, at muli, at muli. At mayroon lamang kaya maraming beses na maaari kang hatiin ang iyong input sa halves, pakaliwa at kanan. Ano ang formula na panatilihin namin ang nakakakita na naglalarawan ng dibisyon sa kalahati muli, at muli, at muli, at muli? Madla: Mag-log n. Tagapagsalita: Mag-log n. Ngunit pagkatapos ay mayroong isang iba pang mga pangunahing hakbang, algorithm na ito ay hindi mag-log n hakbang. Kung ito ay mag-log lamang n hakbang na ito, Gusto naming maging sa parehong problema tulad ng dati kung saan hindi namin maaaring maging Tiyaking ang lahat ng pinagsunod-sunod. Kailangan mong Nagnais tumingin sa n elemento upang makatiyak n mga elemento ay pinagsunod-sunod, kung hindi man ito ay isang hakbang ng pananampalataya. Kaya Nagnais log n hakbang na ito, ngunit kung ano ang tungkol sa mga pangunahing hakbang pagsasama kung saan ako naka-merge ang aking kaliwang kalahati at kanang mga kalahati at lumakad sa buong yugto? Ilang hakbang na ito ay na upang sumanib? Ito'y n, ngunit ko ginawa hindi lamang pagsamahin ang panghuling oras. Sa bawat isa sa mga nested mga tawag, sa bawat ng mga nested merges, pinagsunod-sunod pa rin ako. Pinagsama ko ang dalawang guys, pagkatapos ay ang dalawang guys, pagkatapos ay ang dalawang guys at iba pa. Kaya ako nag pinagsasama muli, at muli. Gaano karaming beses? Kaya sa tuwing ko na hinati-hati ang listahan sa kalahati, ginawa ko ang isang pag-merge. Hatiin ang listahan sa kalahati, gawin ang isang pag-merge. Kaya kung paghati sa listahan Maaaring magawa ng log n beses, at ang pagsasama sa huli ay tumatagal ng n hakbang na ito, kung ano ang maaaring maging itaas na ngayon nakatali sa pagtakbo oras ng aming algorithm? n log n. At sa katunayan, iyon ang na nakamit namin dito. Kaya ang pakiramdam na nakikita mo kapag biswal mga tatlong bagay bahagi tumakbo sa pamamagitan ng gilid ay nakalapat n laban n nakalapat laban sa n log n. Aling fundamentally ipapakita namin makita, hindi lamang ngayon ngunit sa hinaharap, ay mas, mas mabilis. Ang isang round ng applause para sa mga guys, Ako ay gantimpalaan ang mga ito ang stress bola. Ni adjourn dito ngayon Hayaan, at aalisin namin ang nakikita mo sa Lunes.