[Nagpe-play ng musika] 

David J. MALAN: Lahat ng karapatan. Kaya maligayang pagdating pabalik. Ito ay CS50, at ang ay ang katapusan ng linggo tatlong. 

Kaya isipin ang sa nakalipas na ilang linggo, kami gumagastos pa ng kaunting oras sa C, sa programming, sa syntax. At ito ay lubos na normal, kung hindi mo pa rin struggling na may Problema Set 2, na maging banging iyong ulo laban sa mga pader. Ito ay misteriyoso-mukhang error na mensahe at mga bug sa iyo na Hindi maaaring medyo Chase down. Dahil, magpahinga panatag, na sa loob lamang ng ilang linggo 'oras makakakita ka tumingin pabalik sa mga bagay tulad ng Caesar, at [? V-genair,?] siguro ay maging lamat, at Napagtanto lang gaano kalayo mo na dumating sa isang maikling panahon. Kaya kung iyon ang anumang aliw, hang sa doon sa ngayon. 

Ngayon, bagaman, magsisimula kami sa transition sa mga bagay na mas mataas na antas. At simulan namin upang mang-ahas na ka guys malaman kung paano i-program, o sa hindi bababa ang Beginnings ng kaginhawahan na antas. At magsisimula kami upang isaalang-alang kung paano aming makakaya pumunta tungkol sa pagdisenyo ng mga programa nang higit pa mabisa. Paano namin pumunta tungkol sa pag-optimize ang kahusayan ng aming mga algorithm, at pangkalahatan paglutas nang higit pa kagiliw-giliw na mga problema. At nagsisimula na kumuha para sa ipinagkaloob na, kung gusto naming, maaari naming code up anumang ng mga halimbawa sa kami ay may sa isip. Kaya ngayon, hindi kami pindutin ang keyboard para sa anumang paraan ng code. Ito ay mas mataas na antas, at sa huli, tungkol sa problema-tuos. 

Kaya upang makakuha ng sa puntong iyon, hayaan mo akong magpanukala na ang mga sumusunod na pitong parihaba para kumatawan sa pitong pintuan, sa likod ng na kung saan ay ang maramihang mga mga numero, bukod sa kung saan ay ang numero 50. Hayaan akong proyekto na ito sa ito screen dito pati na rin. At ipanukala na kailangan namin ng isang volunteer sa makatulong sa akin mahanap ang isang numero sa harap ng ang internet dito upang makita. Halika sa up, nakahubad. Ayos lang. Ano ang inyong pangalan? 

Jennifer: [hindi marinig] 

David J. MALAN: Paumanhin? 

Jennifer: Jennifer. 

David J. MALAN: Jennifer. Ang lahat ng mga karapatan, Jennifer. Masaya akong makilala kayo. Halika sa up. Kaya ang mga narito ang pitong pintuan, at kung ano Gusto ko ng mong gawin para sa amin dito, sa harap ng lahat ng iyong mga kamag-aral, ay hanapin sa amin ang numero, 50. Upang mahanap ang isang numero, maaari mong pagsilip sa likod alinman sa mga pinto sa pamamagitan ng simpleng pag-tap sa isa sa mga pinto, at ito ibubunyag nito bilang. At sabihin makita kung gaano ka kabilis ay makakahanap sa amin ang numero, 50. 

15. 16. 50. Maayos na Natapos. Ayos lang. Yugto ng papuri para sa Jennifer. 

[Palakpakan] 

Ayos lang. Kaya kung ano ang iyong diskarte para sa paghahanap ng mga numero, 50? 

Jennifer: Um, naisip ko na baka kung - [Hindi marinig] 

David J. MALAN: Oh. Bigyan ito ng isang segundo. Kaya ay ang iyong diskarte para sa paghahanap ng mga numero, 50? 

Jennifer: Kaya ko lang magsisimula sa simula upang makita kung ano ang unang numero noon, at pagkatapos ay naisip ko na, siguro kung sila ay pinagsunod-sunod, kukunin ko na lang panatilihing pagtapik sa mas mataas na up? 

David J. MALAN: OK. At tila namin upang Nakakita na maging ang kaso. Bagaman, sabihin mag-alis ng balat pabalik ang mga layer lamang ng isang maliit na bit, at nais mong pumunta Magpatuloy at ilantad ang iba pang mga pinto maaaring napili mo? 

Jennifer: Oh, mahal. 

David J. MALAN: Ah. 

Jennifer: So Nakakuha ako masuwerteng. 

David J. MALAN: Kaya ba kayong masuwerteng. Ayos lang. Kaya hindi masama. Ngunit iyon lamang ang isang kawili-wiling pananaw, tama? Kung hindi tunay, at ginawa mo makuha, sa katunayan, isang bit masuwerteng doon. Ngunit kung ikaw ay ipinapalagay na ang mga numero ay pinagsunod-sunod, maaari kang maging mas tumpak bilang sa kung paano naiimpluwensyahan na ang iyong pag-uugali? 

Jennifer: Kaya kung sila ay pinagsunod-sunod, ako Naisip siguro pinakamaliit na pinakamalaking. 

David J. MALAN: OK. 

Jennifer: O kung ito napunta sa pagiging talaga malaki, pagkatapos ay pinakamalaking sa pinakamaliit. 

David J. MALAN: OK. Kaya pinakamalaking sa pinakamaliit, o pinakamaliit na pinakamalaking. Ngunit ipaalam sa akin imungkahi, ipagpalagay na mayroon kang nakuha kapus-palad, at ipagpalagay na sila ay hindi, sa katunayan, pinagsunod-sunod, kung gaano karaming ng mga pinto ay maaaring nagkaroon ka na pagsilip sa likod na sa pinakamasama kaso? 

Jennifer: Ang lahat ng mga ito. 

David J. MALAN: Ang lahat ng mga ito. Kaya sabihin ng tuntuning panlahat na bilang n. May mangyayari sa maging 7, ngunit sabihin pa sa pangkalahatan ay sinasabi doon ni n mga pinto sa screen dito. Kaya sa ang pinakamasama kaso, magkakaroon ka ng upang tumingin sa likod ng 7 mga pinto, o pintuan n. At kaya ito ay talagang, ito ay isang bit ng swerte ngayon, ngunit ito ay talagang isang linear algorithm ng uri, kahit na na- ay mga uri ng laktaw sa paligid. Ay patas na? 

Jennifer: Oo. 

David J. MALAN: Well, hayaan mo akong makita kung ang iyong diskarte sa pagbabago kung ilipat ko sa amin sa ang aming ikalawang halimbawa dito sa 7 iba't ibang mga pinto. Parehong numero, ngunit ito oras na sila ay pinagsunod-sunod. Ano ang iyong diskarte dito pagpunta sa maging, sinusubukan upang ilagay ang out sa iyong isip kung ano ang iba pang mga numero ay - 

Jennifer: OK. 

David J. MALAN: - mas maaga? 

Jennifer: Sabihin simulan sa unang isa. 

David J. MALAN: Lahat ng karapatan. Magsimula sa ang unang isa. 4. Ngayon saan ka pupunta upang pumunta, at bakit? 

Jennifer: 4 ay talagang maliit. Kaya kung ang mga ito ay pag-uuri siguro pinakamaliliit sa pinakamalaking, dapat ito maging dalawang beses na, at -. 

David J. MALAN: OK. Tayo'y makita, na sa palagay mo? 

Jennifer: Subukan ang huli. Nice. 

David J. MALAN: Bihirang mabuti tapos na. Ayos lang. 

[Palakpakan] 

David J. MALAN: OK. Kaya talaga ginagawa mo ito horribly, dahil ikaw ay ginagawa ito nang mahusay. Na nag-iiwan sa amin magawang gumawa ng ilang mga puntos. So sabihin subukan upang ibalik dito. 

Jennifer: OK. 

David J. MALAN: Bihirang na rin tapos na, gayunman. Kaya Sinimulan mo sa simula, Nakita mo na ito ay 4 na, pagkatapos mong inilipat na sa dulo. Ngunit ipagpalagay na hindi mo makakuha ng masuwerteng doon, at ipagpalagay 50 ay sa ibang lugar. Ano ang iyong third step na naging? 

Jennifer: Bumalik sa simula. 

David J. MALAN: Bumalik sa simula. OK, kaya gusto mo na hinawakan ito pinto, na kung saan ay 8. Ayos lang. Kaya hindi iyon 50. Saan mo na tumingin sa tabi? 

Jennifer: Kung ako ay hindi malaman nila pinagsunod-sunod. 

David J. MALAN: Tama. Well, kung ginawa mo alam sila ay pinagsunod-sunod - 

Jennifer: Oh, alam, oo. 

David J. MALAN: - ngunit ikaw ay hindi alam kung saan 50 noon pa? 

Jennifer: lamang panatilihin ang pagpunta. 

David J. MALAN: Lahat ng karapatan. OK. Panatilihin ang pagpunta. OK, na maaari kong magamit. 

Jennifer: OK. 

David J. MALAN: Ngayon, kung hindi ka lang pagpunta sa panatilihin ang pagpunta, kung ano ang iyong algorithm devolving back in. 

Jennifer: Ang linear -. 

David J. MALAN: Ito ay uri ng linear. Ngunit ipaalam sa akin imungkahi, sabihin ako ilagay sa puwesto. Hayaan akong i-refresh ang pahina. parehong numero, parehong pag-aayos, parehong mga pinto. Ngunit sa tingin bumalik sa na unang araw sa kapag klase namin torus isang telepono libro sa kalahati, uri ng, at kung ano ang noon ay ang aming diskarte doon? 

Jennifer: Magsimula sa gitna. 

David J. MALAN: OK. Kaya magsisimula sa gitna. Kaya sabihin sige at gayahin na. Magsimula sa gitna ng ibinubunyag na pinto. Kaya ang bilang 16. Kaya kung ano ang gusto ng malakas na tao nagawa na, sino torus ang phone book sa kalahati, upang makakuha ng sa susunod na hula? 

Jennifer: Pumunta sa kalahati. 

David J. MALAN: At bakit sa kanan? 

Jennifer: Kung sila ay mga uri ng mga pinakamaliliit sa pinakamalaking, pagkatapos ay 50 ay dapat na na sa dulo. 

David J. MALAN: Mahusay. Lubos makatwirang. Kaya tulad ng isang libro ng telepono, kang pumunta sa karapatan bilang kabaligtaran sa kaliwa, ngunit dito ay ang susi takeaway. Ikaw ngayon ay maaaring itapon, o pilasin, kalahati ng ang problemang ito, iiwan sa iyo hindi may 7 mga pinto, ngunit talagang may lamang 3. Alin ang halos kalahati ng laki ng problema. Ayos lang. Kaya ngayon kung ano ang mayroon ka tapos pagkatapos pumunta ka tama? 

Jennifer: So 16 pa rin ang medyo maliit, kung ihahambing sa 50, kaya siguro kailangan kong subukan, tulad ng, ang isang ito. 

David J. MALAN: Lahat ng karapatan. 42. Ang lahat ng mga karapatan, kaya ngayon kung ano ang iyong likas na hilig na nagsasabi sa iyo? 

Jennifer: Maaari ko bang itapon ito at pagkatapos lamang - 

David J. MALAN: OK. Mahusay, maaari mong ibasura sa kaliwang kalahati doon. 

Jennifer: - pumili ng isang ito. 

David J. MALAN: At sa kanan. 

Jennifer: Oo. 

David J. MALAN: Kaya kahit mahirap upang makita ang di kaya, kapag mayroon lamang 7 mga pinto, isipin ang tungkol, ngayon, ang pagkakapare-pareho ng mga algorithm mo lamang inilapat. Sa nakaraang mga kaso, ng ginawa mo makakuha ng masuwerteng, na noon ay mahusay. Pero ginawa mo gamitin ang isang hyuristiko, Gusto ko sabihin. Ikaw ginamit uri ng iyong instincts, at pag-alam ito pinagsunod-sunod, kung ito ay medyo maliit sa simula, malinaw naman, na namin Nakakuha upang pumunta nang higit pa sa kanan. Ngunit sa ilang mga kahulugan, nakukuha mo masuwerteng, dahil marahil ito ay ang numero 100, at siguro 50 noon pa sa gitna. Siguro 50 ay kahit na sa paglipas dito. 

Ngunit ano ang ginawa mo ng kaunti naiiba oras na ito noon, ginawa mo ang parehong bagay muli at muli. At Gusto ko magtaltalan na kung ano ang iyong lamang ay, kahit na naimpluwensyahan ng mga telepono aklat halimbawa, ay isang bagay magkano higit pang mga algorithmic, at magkano mas espesyal cased. Karamihan mas mababa katutubo. Kaya sa katapusan ng araw, paano gagawin ilarawan mo ang husay ng unang algorithm, kung saan ka nagpunta pakaliwa sa kanan, kumpara sa pangalawang algorithm dito? 

Jennifer: ang isa na ito ay dapat, tulad ng, siguro maghati ng oras, o kahit na higit pa, oo. 

David J. MALAN: OK, marahil kahit na higit pa. Sabihin itulak ng kaunti mahirap sa na. Ano talaga, kung patuloy namin ito logic, kami siguradong halved ang tumatakbo ang oras na ito na may pangalawang algorithm sa pamamagitan ng itsa kalahati ng mga numero, ngunit kung ano ang ginagawa namin sa susunod pag-ulit, kapag Jennifer nagsiwalat ang pangalawang numero? 

Halved namin ang mga numero ng mga pinto muli. At pagkatapos ay kung ano ang ginagawa namin matapos na, kung ang mayroong higit pang mga pinto upang i-play na may? Gusto naming maghati sa kanila, at muli, at muli, at muli. At ito ay katulad lamang ng sa iyo ang lahat ng mga guys nakatayo hanggang sa unang linggo ng klase, kalahati ng sa iyo sitting down, kalahati ng pag-upo ka pababa, kalahati ng sa iyo sitting down, hanggang sa kaisa-isa isa kaluluwa ay nakatayo. At sinabi namin na ang oras ng paggana ng na, ang bilang ng mga hakbang na ito ay kinuha sa pagkakasunud-sunod ng kung ano? 

Tagapagsalita 1: [hindi marinig] 

David J. MALAN: So log base 2 ng n, o lamang nang higit pa lamang, mag-log ng n. Kaya isang bagay logarithmic. At ang graph ay hindi isang tuwid na linya na Naging mas masahol at mas masahol pa, ito ay ito kawili-wiling curve na hindi makakuha kaya masamang sa paglipas ng panahon. Kaya sabihin kumapit sa ideyang ito. Sabihin salamat Jennifer. Salamat magkano kaya para sa darating up. At, isa seg. Walang desk lamp ngayon, ngunit hindi namin kailangang CS50 bola stress. 

Jennifer: Yay. 

David J. MALAN: Ang lahat ng karapatan, dito. Salamat sa iyo para sa incurring ang pagkapagod up dito. Ayos lang. Kaya sabihin makita kung maaari naming hindi na ngayon gawing pormal ito nang kaunti pa. Kaya muli, ano pa lang namin ginawa noon ay mahalagang parehong bagay tulad ng ginawa namin na sa unang linggo. Ngunit sa halip na sa katapusan sa pamamagitan lamang ng isang linear algorithm, na aming itinatanghal dati ito bilang tuwid na linya, kung saan, kung inilalagay namin ang isa pang pinto sa ang screen, at pagkatapos ay Jennifer gagawin nagkaroon upang tumingin, potensyal, sa likod ng isa pang pinto. Kung inilalagay namin ang dalawang higit pang mga pinto, baka siya ay may upang tumingin sa likod ng dalawang higit pang mga pinto. 

At kaya, nagkaroon ito linear relasyon sa pagitan ng mga sukat ng problema sa, sabihin nating, ang x-axis, at ang halaga ng oras na aabutin upang lumutas sa y. Ngunit ang larawan ko ay alluding sa mas maaga ay ang berdeng linya. Green kusa, dahil ito lamang nadama mas mahusay. Sa teorya, ang algorithm, kapag ginawa namin ito sa aklat ng telepono, kapag ginawa namin ito sa iyo guys pagbibilang ng bawat isa, at sa pangalawang pagkakataon, kapag Jennifer lamang ginawa ito up dito, ito ay pag-uuri sa panimula ng mas mahusay. Dahil ito ay hindi lamang dalawang beses nang mas mabilis. Ito ay hindi kahit na apat na beses na mas mabilis. Iyon ay ganap na nakasalalay sa kung ano ang laki ng input ay, bilang sa kung gaano karaming hakbang ito kinuha sa huli. 

At kaya ito simpleng ideya na namin ang lahat ng kinuha para sa ipinagkaloob sa aklat ng telepono, Maaari katulad mailapat sa isang bagay na katulad nito. At ito ay maaaring maging mas casually na kilala bilang, pati na kapangyarihan sa iyo isipin, hatiin at lupigin. Hindi hindi tulad ng kung ano ang ginawa namin, siyempre, may mga phone book. 

Ngunit ang pseudocode, isipin ang, ay ito. Kaya hindi namin gawin ito muli, ngunit isipin ang na unang linggo, ang lahat ng sa amin nakatayo up at pagkatapos ay kalahati ng umupo ka down, kalahati ng umupo ka pababa, kalahati ng umupo ka pababa. Iyon algorithm ay ipinatupad sa isang bit ng isang paraan pagdaraya, sa na, ito ay hindi lamang isa sa akin pagbibilang, sa panimula, mas mahusay. Sa kasong iyon, ako ay pagdaragdag isang pangalawang mapagkukunan. Pagsunud-sunurin ng, ang maramihang mga CPUs, maraming talino, maraming matalinong tao sa room ay pagtulong sa akin makakuha ng isang bagay mula sa linear sa isang bagay logarithmic, mula sa isang bagay pula sa isang bagay na berde. 

Ngunit sa kasong ito, Jennifer nag-iisa maaari sa panimula mapabuti ang oras ng pagganap ng kanyang mga unang algorithm sa pamamagitan ng, muli, pag-iisip lamang ng kaunti mas mahirap. At ngayon, pagdating ng panahon upang ipatupad mga bagay na ito, ang pag-uunawa kung ano ang mga linya ng code na maaari mong isulat ang naturang na maaari mong ulitin muli ang mga ito, at muli, at muli, isang uri ng sa isang looping fashion. Dahil hindi ka pagpunta sa may luxury, tulad ng ginawa Jennifer nang una, upang lamang magkaroon ang maramihang mga ifs at sabihing, Hmm, kung ang unang numero ay 4, hayaan mo akong tumalon lahat ng mga paraan sa dulo. Ooh, kung ang numero na ay masyadong malaki, hayaan mo akong ilipat mang bumalik sa pangalawang elemento. Makikita mo ang na ito ay pagpunta sa maging ng maraming mas mahirap upang gawing pormal kung ano ang aming mga kawani na tao mang-ahas bilang napaka-makatwirang heuristics, ngunit computer ng isang ay lamang pagpunta sa gawin kung ano sabihin mo ito upang gawin. 

Ngayon na ito ay may napaka-interesante implikasyon. Ang graph na ito ay isang uri ng sinadya upang pagsunud-sunurin ng mapuspos biswal, ngunit paunawa, kung saan ay ang tuwid na linya sa graph na ito? Saan ang linear graph na tinatawag naming n? Well, ito ay isang uri ng patungo sa ibaba ng ang larawang ito, tama? Kaya lahat kami ay tapos na namin ang uri ng naka-zoom out sa x-axis at ang y-axis upang subukan upang makakuha ng ideya ng kung ano ang iba pang mga uri ng mga curves hitsura. 

At ang mga pagtutukoy ng mathematical expression ngayon ay hindi mahalaga kaya magkano, ngunit napansin na mayroong ng maraming algorithm na malayo mas masahol pa kaysa sa isang bagay na linear. Sa katunayan, n nakakubo medyo mukhang masama. 2 sa n mukhang medyo masama. n squared medyo mukhang masama. At kami makita kung ano ang ilan sa mga ay maaaring maging sa katotohanan ngayon. At log n ay hindi pakiramdam bilang masama, ngunit mas mahusay kaysa sa n ay log base 2 ng n. Pero alam mo, mas naging kahit na higit pang mga kamangha-manghang kung Jennifer, o kung kami, na unang linggo, ay makabuo ng mga isang bagay na pag-log ng log ng n. 

Kaya sa ibang salita, may kabuuan na ito hanay ng mga posibleng solusyon sa mga problema, ngunit kahit na dito, notice kung ano ang nangyayari sa mangyari. Kapag ako mag-zoom out, kung alin sa mga curves ay pagpunta sa patunayan na maging ganap pinakamasama ng ang mga nasa screen ngayon? Kaya n nakakubo mukhang maganda masama sa sandaling ito. Ngunit kung kami mag-zoom out at makita ang higit pa sa mga x at y-axis, kung sino ang pagpunta sa mangibabaw sa huli? Kaya ito talaga lumiliko out na 2 sa n, at maaari mong malaman ito out lamang sa pamamagitan ng i-plug sa ilang nagiging malaki numero, at makikita mo na ang 2 sa n, sa katunayan, ay nakakakuha ng mas malaki mas mabilis. Kung kami talaga mag-zoom out, isang 2 sa n algorithm talagang sucks. Ibig kong sabihin na ito ay pagpunta sa tumagal pa ng kaunting oras para sa computer upang magbati sa pamamagitan ng. 

Ngunit makikita mo sa paglipas ng panahon, lalo na may hinaharap na mga hanay ng problema at kahit na huling proyekto, ay ang iyong data hanay ay makakakuha ng malaki, ang lahat ng karapatan? Kahit na sa unang bersyon ng Facebook, bilang ang bilang ng mga kaibigan, at ang bilang ng mga nakarehistrong user Naging malaking, Maaari mong pagsunud-sunurin ng telepono ito sa at ipatupad ang isang bagay na may linear paghahanap, o isang napaka-simpleng pag-uuri algorithm, bilang namin makita ngayon. Mayroon kang upang simulan ang pag-iisip mas mahirap at mahirap tungkol sa mga problemang ito. At ang mga uri ng mga problema sa mga lugar tulad ng Facebook, at Google, at Microsoft, at iba pa gumagana sa ay eksaktong mga uri ng malaking data uri ng mga katanungan nagiging mga araw na ito. 

Ayos lang. Kaya Jennifer ng tagumpay sa na pangalawang algorithm, lantaran, siya ay ginawa amazingly na rin sa unang pagkakataon, ngunit sabihin isulat ito bilang swerte kaya na namin maaaring gumawa ng puntong ito. Sa pangalawang kaso, siya ay isang magagamit algorithm na paulit-ulit na muli at muli, ngunit siya ay kinuha para sa ipinagkaloob ng ilang mga palagay na namin pinapayagan kanya, ngunit siya ay pinagsamantalahan ang ilang detalye ang pangalawang pagkakataon na hindi niya kinailangang mga unang pagkakataon. Aling ay kung ano? 

Iyon ang listahan ay pinagsunod-sunod. Kaya sa lalong madaling ang listahan ay pinagsunod-sunod, namin i-claim na Jennifer nagawang gawin sa panimula mas mahusay. 7 mga pinto, oo, ay hindi na kawili-wili, ngunit ipagpalagay na ito kami ay 7,000,000 pintuan. Log ng n ay siguradong pagpunta upang isagawa magkano, magkano mas mabilis sa katagalan. Subalit siya ay nagkaroon na magkaroon ng pintuan pinagsunod-sunod para sa kanya. Ngayon, ako kinuha ang kalayaan ng paggawa na nang maaga sa computer screen dito, ngunit ipagpalagay na Jennifer nagkaroon na gawin na kanyang sarili? Ipagpalagay na ang mga pinto na pinag-uusapan kinakatawan ng data sa isang database, o kaibigan nakarehistro para sa Facebook, o anumang web page sa internet na iba't-ibang mga website ay maaaring kailangan sa index ng paghahanap o sa ibabaw. 

Ipagpalagay na ikaw lamang ay nagkaroon ng isang raw data itakda at ito ay iniwan sa iyo, o sa Jennifer na gawin na pag-uuri? Iyon, sa halip, ay nangangailangan na sagutin namin ang pinag-uusapan, well, kung magkano ang oras sana ay kinuha Jennifer, o kahit sa akin, upang pagbukud-bukurin ang mga numero nang maaga kaya na siya ay maaaring samantalahin ng mga iyon? I-right? Dahil ang implikasyon, siyempre, ay kung ito ay tumatagal ng lubos sa akin ng isang habang upang pagsunud-sunurin ang mga numero, na ano ba ang nagmamalasakit ka na Maaari makahanap ng isang numero tulad ng 50 kaya mabilis, bilang sa Jennifer ng kaso, kung kami ng higit pa mapuspos ng halaga ng kabuuang oras ito kinuha sa pamamagitan ng pagbubukod-bukod ng mga bagay nang maaga? 

Kaya sabihin makita kung hindi namin magagawa ang pintura ang larawan dito. Mayroon akong isang buong bungkos pa ng stress bola, kung na tumutulong sa basagin ang yelo dito. At kung hindi mo nais tututol, namin kailangan pitong volunteer - on, OK. Wow. Kaya hindi namin kailangang gumastos sa desk lamp, tila. Ayos lang. Kaya kung paano tungkol sa iyo dalawa sa harap. Paano tungkol sa iyo dalawang guys sa likod. Kaya iyon ang apat. Paano tungkol sa iyo sa harap lima, anim at pito. I-right doon. Ang iyong kaibigan ay pagturo out ka, kaya mo makuha ang premyo. 

Ayos lang. Halika sa up. At bakit hindi na mayroon kami sa iyo guys dumating sa paglipas dito. Pupunta ako sa magbibigay sa iyo ng bawat isang numero. At sige at mag-ayos inyong sarili identically sa kung ano ang itinatanghal sa screen. 

[INTERPOSING tinig] 

David J. MALAN: Oop, paumanhin. Bug. Ayos lang. Well, dito namin pumunta. Numero ng limang. Numero ng anim. Ang isa, dalawa, tatlo, apat, lima, anim, pitong. Oh, ito ay hindi akma. 

Tagapagsalita 2: kukunin ko na lang makakuha ng -. 

David J. MALAN: Magandang deal. Ayos lang. Salamat sa iyong pakikilahok. 

[Palakpakan] 

OK. Ayos lang. Kaya mayroon kaming apat, dalawa, anim, isa, tatlo, pitong, lima. Maperpekto kaya kami ay may pitong mga boluntaryo sino dito ay pantay-pantay sa lapad sa array na aming paglalaro may mga mas maaga. At ako pinili mo para sa pitong mga dahilan na magiging lamang maginhawa sa ilang sandali. At ako pagpunta sa imungkahi unang na namin ang uri-uriin ang mga pitong mga boluntaryo. Kung gusto mo, una, upang kamustahin bagaman. Dahil ito ay magiging isang nakahihiya ilang minuto. Ipakilala inyong sarili. 

Grace: Hi, Ako Grace. Ako ay isang sopomor sa Leverett House. 

Branson: Hi. Ako Branson. Ako ay isang primer anyo sa Weld. 

Gabe: Hi. Ako Gabe. Ako ay isang junior sa Cabot. 

Neil: Ako Neil. Ako ay isang primer anyo sa Matthews. 

Jason: Ako Jason. Ako ay isang primer anyo sa Greenough. 

Mike: Ako Mike. Ako ay isang primer anyo sa Grays. 

Tanikala: Ako Jess. Ako ay isang sopomor sa Leverett. 

David J. MALAN: Mahusay. Ayos lang. Well, salamat sa lahat ng aming boluntaryo dito kaya sa ngayon. At ang mga hamon sa kamay ngayon ay pagpunta upang maging upang ayusin ng mga guys, ngunit pagkatapos ay kami ay pagpunta sa mag-isip ng kaunti mahirap tungkol sa kung paano mahusay na namin talaga pinagsunod-sunod ang mga ito. Kaya sabihin muna subukan ito. Ka guys ay maaaring makita ng bawat isa mga numero lamang sa pamamagitan ng paglalagay sa paligid ang mga sulok. Sige at tumagal ng ilang segundo, at sort inyong sarili mula sa pinakamaliliit sa ang natitira upang pinakamalaking sa kanan. Pumunta. 

OK. Magandang. Iyon ay talagang darn mabilis. Ngayon isang tao dito, kung ano ang algorithm ang na mga guys inilapat? 

Tagapagsalita 1: bababa sa pinakadakilang. 

David J. MALAN: OK. Hindi bababa sa pinakadakilang talaga-uri-uriin ng layunin, ngunit hindi ako sigurado na talaga isang algorithm. Hindi bababa sa pinakamahusay na hindi sabihin sa akin mga step-by-hakbang kung ano ang gagawin. Oo? 

Tagapagsalita 1: [hindi marinig] 

David J. MALAN: OK. Kaya kung makikita mo ang isang tao na mas maliit sa ang iyong numero, pagkatapos ay lumipat sa ang karapatan ng mga ito. Kaya na ngayon sa pagkuha ng mas makahulugan, higit na katulad ng isang algorithm, dahil ikaw Maaaring sabihin, kung ito, pagkatapos na. Kaya kami ay may ilang mga uri ng bumuo ng mga kondisyon. At ang mga guys tila upang gawin iyon ng ilang beses, dahil ang ilan sa iyo inilipat ng kaunti ng isang distansya. Kaya nagkaroon siguro ng ilang mga uri ng looping nagaganap sa kanilang mga isip. 

Ngunit sabihin subukan upang gawing pormal na. Kung ka guys ay maaaring i-reset pabalik sa pag-aayos na ito. Tayo'y makita kung hindi namin maaaring gawing pormal ang isang bit, at pagkatapos ay tanungin ang tanong, lamang kung paano mahusay na ito? Siyempre, kapag ginagawa namin ito nang mas mabagal, ito ay pagpunta sa pakiramdam bilang mabuting ng isang algorithm, ngunit sabihin makita kung ang aming makakaya ilagay ang aming mga daliri sa ang tumpak na mga hakbang. 

Kaya kang dalawang guys ay apat at dalawang. O kaya mo tama o mali ang pagkakasunod-sunod? Malinaw na hindi tama. Kaya namin swapped. Ngayon ako pagpunta sa magtabi dito at sabihing, 05:56. Sigurado ka tama o mali? 

Gabe: Tama. 

David J. MALAN: Tama. Anim at isa? Nope. Pagpalitin. Kaya iyon ang dalawang swaps. Anim na at tatlong? Nope. Pagpalitin. Anim at pito? Mukhang magandang. Pitong at limang? 

Tanikala: [hindi marinig] 

David J. MALAN: OK, swap. At pinagsunod-sunod. Ayos lang. Kaya malinaw naman hindi, tama? Kaya doon ay mas pagpunta sa. Ngunit, sa katunayan, ang mga guys, kahit na lamang nang katutubo. iningatan gumagalaw. Hindi nila lamang tumigil, sa sandaling sila naitama isa problema. Kaya. Sa katunayan, pupuntahan ko mayroon upang gawin ang parehong bagay. Pupunta ako sa may upang ayusin ng rewind pabalik sa simula ng ang problemang ito, o simula ng array na ito ng mga tao, sabihin simulan ang pagtawag sa kanila. 

At ngayon kung ano ang dapat ang aking mga algorithm sa ikalawang pass maging? 

Tagapagsalita 1: Parehong bagay. 

David J. MALAN: Parehong bagay. At ito, ako simula upang gustuhin, tama? Sa lalong madaling maaari mong mahanap ang iyong sarili paggawa ang parehong bagay muli at muli, na pagiging higit na katulad ng isang algorithm, at mas pantao likas na hilig. 

Kaya ngayon, dito namin pumunta muli. Dalawang at apat? Hindi. Apat at isa? Ah, nagkaroon nga ng ilang gumana pa rin na ma-tapos na. Para at tatlong? Magandang. Apat at anim? Anim at limang? Anim at pito? OK, ngayon, tapos na. OK, hindi. Mayroon akong upang bumalik. 

Kaya ngayon, muli, ginagawa namin ito ang kaunti pa sadya. At ngayon, mayroong isa lamang sa utak e-execute ito algorithm. One CPU, kung kalooban mo. At lantaran, na ang tanging mapagkukunan kami ay pagpunta sa may access sa. At sabay-sabay kami bumalik sa isang keyboard at magkaroon ng isang bagay tulad ng C sa aming pagtatapon, tanging sumusulat kami ng isang programa na maaaring gawin ang isang bagay sa isang pagkakataon. Sapagkat, ang mga guys ng ilang sandali ang nakalipas, namin magagamit ang kanilang kolektibong brainpower tulad mo guys ginawa sa linggo zero. Kaya sabihin panatilihin ang paggawa na ito. 

Dalawang at isa. Dalawa at tatlong. Tatlong at apat. Apat at lima. Limang at anim. Anim at pito. Tapos na? Kaya ako, ngunit hayaan mo akong maglaro satanas ng tagapagtaguyod. Gagawin ko, ang uri ng mga computer na kung sino lamang ginawa ng pass sa pamamagitan ng hanay ng mga mga tao, alam na ako tapos? 

Tagapagsalita 1: Hindi. 

David J. MALAN: Kaya bakit? Ano ang gusto kong gawin upang pagtibayin tiyak na ako ay tapos na? Malamang isa pang pass. I-right? Dahil ang lahat ng mga kakilala ko na mula sa nakaraang pass ay na naitama ko isang pagkakamali. At na paraan, siguro mayroong pa rin ng isa pang pagkakamali na kailangan ko upang itama. Kaya ko lamang maging sigurado sa pamamagitan ng rewinding, at pagkatapos ng pagsusuri, 01:59, at dalawang tatlo, tatlo at apat, apat at limang, limang at anim, anim at pito. OK, ngayon ko ginawang walang trabaho. 

Maaari ba akong tiyak na tandaan na ang ginawa kong walang gumana sa isang bagay tulad ng isang variable, gusto ang isang int. Tumawag ito swaps, at kung swaps ay 0 beses ko makarating dito, at ito nagsimula sa 0, pagkatapos ay Gusto ko lang maging bobo upang panatilihing pagpunta pabalik-balik, muling suriin, at muli, at muli, tama? Dahil hindi ka makaalis sa ilang mga uri ng walang-katapusang loop. Kaya sa lalong madaling mayroong 0 swaps, Maaari naming i-claim na ito algorithm ay talagang kumpleto. 

Ngayon, sabihin maglagay ng pangalan sa mga ito. Ang algorithm na ipanukala ko pa lang namin ipinatupad ay isang bagay na tinatawag na bubble -uri-uriin, na kilala bilang tulad sa kamalayan na ang mga numero na mas malaki uri ng bubble kanilang mga paraan up sa tuktok, o hanggang sa dulo ng hanay ng mga numero. Ngunit paano mahusay noon ay algorithm na ito? Gaano karaming mga hakbang na ito ang nakuha ko pisikal na kailangang magtagal, halimbawa, upang ayusin ang mga pitong kawani na tao? 

Apat sa limang? OK, masyadong maraming ay sa huli pagpunta sa maging ang kasagutan. Ngunit kahit na pagkatapos, ang tiyak na bilang Hindi kaya kawili-wiling. Sabihin ng tuntuning panlahat ito bilang n. Kaya kung ako ay n mga tao dito, at sila ay, uri ng, sa random na pagkakasunod-sunod sa simula, sa orihinal na order. Well, kung gaano karaming mga hakbang na ito ay mayroon akong gumawa sa unang pass? Iyon ay isa, dalawa, tatlo, apat, lima, anim, at ang mga ito ay pitong mga tao, kaya na pitong, anim -, kaya na n minus isa hakbang sa unang pagkakataon. 

Ngayon, kung gaano karaming mga hakbang na ito ay mayroon akong gumawa kapag rewound ko? Well, maaari namin talagang i-double na kung namin talagang gusto, ngunit sa ngayon, ako lamang ng pagpunta sa sabihin, ang lahat ng karapatan, isa pa n minus 1. Kaya ang minus n 1 ay pagpunta upang makakuha ng nakakainis upang subaybayan, kaya sabihin lamang paglilikom bahagyang. Kaya 2n hakbang. Kaya 14 mga hakbang, bigyan o kumuha. 

Gaano karaming beses ang nakuha ko tumagal isang hakbang sa susunod na pagkakataon? Well, ito ay 3n. talaga. At ngayon, sa pinakamasama kaso, para sa Halimbawa, kung gaano karaming beses Gusto ko mayroon nawala na pabalik-balik, pabalik-balik, e-execute ito algorithm, pagpapalit mga tao sa bawat pass, halos? Talaga Ito ay n squared, tama? 

Dahil sa ang pinakamasama kaso, maaari mong uri ng isipin ang tungkol ito intuitively, kahit na maaaring tumagal ng kaunti kaunting oras upang malugi in Sa pinakamasama kaso, ano ang gagawin mga pitong tao ang mukhang, sa mga tuntunin ng pag-aayos ng kanilang mga numero? Ganap na paurong, tama? At lamang upang gayahin na, ano ang iyong pangalan muli? 

Mike: Mike. 

David J. MALAN: Mike? OK, Mike, maaari ka lamang sumali sa akin sa paglipas ng dito lamang para sa isang segundo? Talaga, hindi. Paumanhin Mike, sabihin rewind. Ano ang inyong pangalan muli? 

Neil: Neil. 

David J. MALAN: Neil. OK, Neil, pumunta ka sa sa akin, kung hindi tututol kayo. Kaya ako ng pagpunta sa imungkahi, para lamang sa simple, na Neil ay nasa kanyang pinakamasama posibleng sitwasyon. Ngunit isipin ang kung paano naipatupad ko ang aking mga algorithm. Ako paghahambing, paghahambing, paghahambing, paghahambing, paghahambing, oh. Ngayon ang mga guys ay out ng order, kaya ko aayusin. Kaya mo guys swap. Subalit isaalang-alang ngayon, kung magkano ang higit na malayo Neil ay may upang pumunta? Halos Ito ay n. Alam mo, ito ay hindi talaga n. Ito ay tulad, n minus 1, ngunit ako nakakakuha nayayamot pagpapanatiling track ng kaunti numero, kaya sabihin lang tawagan n ito. 

Kaya kung Neil gumagalaw isang hakbang maximally bawat oras, at upang ilipat Neil isang hakbang, Mayroon akong upang gumawa ito talagang nakakapagod pass pabalik-balik, ito ay tinatayang ginagawa ito, n hakbang na ito, sa kabuuan ng n beses, dahil ito ay pagpunta sa tumagal sa akin na maraming mga hakbang na ito upang makakuha ng lahat ng Neil ang daan sa kung saan siya nabibilang. Hayaang mag-isa ang iba kung ikaw guys lahat ay di-nakaayos pati na rin. 

Kaya sabihin tumawag bubble sort n squared. Ang oras ng paggana ng algorithm na ito, ang pagganap ng algorithm, ang kahusayan ng algorithm na ito, tayo lamang ilarawan nang higit pa sa pangkalahatan bilang n nakalapat. Alin ang magaling, dahil maaari kong gawin ang parehong halimbawa na may walong mga tao, siyam mga tao, isang milyong mga tao, at na sagot ay hindi pagpunta upang baguhin. 

Kaya't kung ikaw guys ay hindi tututol, sabihin i-reset mo sa kung saan ka magsimula. At sabihin subukan ang dalawang iba pang mga approach na at makita kung hindi namin maaaring gawin sa panimula mas mahusay kaysa sa na ito. Kaya oras na ito, pupuntahan ko ipanukala isang uri ng iba't ibang mga algorithm. Iyon ay napaka-matalino sa atin huling oras, at ka guys ay karapatan na mayroon ang karapatan instincts lamang ng uri pagpapalit ng pairwise. Ngunit kung ako talagang gusto lapitan ito lamang, at ang aking layunin ay upang ilipat lahat ng maliit na mga numero ng paraang ito, at itulak ang lahat ng mga malaking mga numero na paraan, bakit hindi ko na lang gawin iyon sa pinaka-walang muwang paraan posible at makita kung ako maaaring gawin mas mahusay kaysa sa kung ano ay isang medyo complex algorithm? 

Kaya natin makita. Apat ay isang medyo maliit na bilang, kaya ako pagpunta sa umalis ka doon sandali. Ooh, dalawang numero ay mas mahusay. Kaya maaari mo lamang humakband para sa isang sandali? Ito ang aking kasalukuyang pinakamaliit na numerong kandidato, at pupuntahan ko matandaan na may, gusto, sa isang variable. Ngunit ako pagpunta sa panatilihin ang pagsuri. Mayroon bang isang tao na ang numero ay mas maliit? Anim, hindi. Oh, mayroong Neil muli. 

Kaya ako ng pagpunta sa itulak ka pabalik uri ng conceptually. Neil ay darating pasulong. At ngayon, ang mga variable na gumagamit ako sa subaybayan kung sino ang may mga pinakamaliliit numero ay na-update upang maglaman ng Neil ng lokasyon. Well, sabihin makita. Tatlong, pitong, lima. OK, alam ko Neil ay ang pinakamaliit na. Ano ang pinakasimpleng bagay para sa akin upang gawin ngayon? Hindi ako pagpunta sa sayangin ang aking oras sa pamamagitan lamang bulubok Neil isa puwesto sa kaliwa. Bakit hindi ko lang ilagay Neil kung saan siya Nabibilang, na siyempre saan? 

Ang lahat ng mga paraan sa simula. Kaya Neil, sumama kayo sa akin. At kung ano ang iyong pangalan muli? 

Grace: Grace. 

David J. MALAN: Grace. OK. So Grace, sa kasamaang-palad, ikaw ay uri ng sa paraan. Kaya paano namin malutas ang problemang ito? I-right? Kung ito ay isang array, mayroong lamang pitong mga lokasyon. Isipin ang na, may Rob, usapan natin ang tungkol sa deklarasyon ng edad, at lamang namin ay nagkaroon ng isang may hangganan bilang ng edad? Parehong ideya dito. Kami lamang magkaroon ng isang tiyak na bilang ng mga ints. Grace ay uri ng sa aming paraan, kaya paano namin ayusin? 

Ang pinakamadaling paraan ay tulad, Grace, paumanhin. Ikaw ay pagpunta sa may upang pumunta sa ibabaw doon upang maaari naming gumawa ng room. Ngayon, kung sa tingin mo tungkol sa mga ito, siguro lang namin ginawa ang problema mas masahol pa. At siguro ginawa namin, dahil kung ano Grace ay nasa tamang lugar? Ngunit alam namin siya hindi, dahil kung hindi man, gusto siya naging nakatayo forward sa halip ng Neil sa oras na ito, tama? Kami ay naka-check ang kanyang numero out. 

Ayos lang. Kaya ngayon, Neil ay nasa tamang lugar, at Ang maaari kong gawin ang isang bahagyang pag-optimize. Para sa susunod na minuto, pupuntahan ko huwag pansinin Neil lahat ng sama-sama, sa gayon ay hindi mag-aaksaya ng kanyang oras, o aksidenteng swap sa kanya sa maling lugar. Kaya ngayon, paano ko mahanap ang susunod na elemento na pinakamaliit? Dalawang. Iyan ay isang medyo magandang numero, kung Gusto mo sa hakbang pasulong at Kukunin ko tandaan mo. Anim, walang mabuti. Apat, tatlo, pitong, lima, walang mabuti. Kaya hayaan mo akong ilipat sa iyo upang ang iyong mga tamang lugar. At kami Naging masuwerteng oras na ito. 

Ngayon, pupuntahan ko na balewalain ang mga dalawang guys, at ngayon ay gawin ang isa pa dumaan na ito. Anim na, na ang isang medyo maliit na bilang. Halika sa pasulong. Oh, paumanhin. Grace ng numero ay mas mahusay, kaya hakbang sa forward. Apat. Paumanhin, Grace. Bumalik muli. Numero ng tatlong ay mas mahusay. Pitong. Limang. At ngayon kung ano ang iyong pangalan muli? 

Jason: Jason. 

David J. MALAN: Jason. Kaya Jason na ngayon ang pinakamaliit na elemento aking napili. Kung saan siya ay pagpunta sa pumunta? Kaya kung saan ay anim. At ang iyong pangalan ay muli? 

Gabe: Gabe. 

David J. MALAN: Gabe. Gabe ay sa paraan. Ano ang pinakamadaling bagay na gawin? Pagpalitin ang dalawang guys at magpatuloy. Kaya ngayon sabihin makita. Sino ang pinakamaliit? Apat. Hayaan akong lamang uri ng impostor. Limang ay pagpunta sa maging sa pinakamaliliit na. Tingin ko susunod, kung, gusto mo sa hakbang pasulong, ano ang dapat kong gawin sa mga mga guys, may Gabe? Pagpalitin muli. Kaya ngayon, pa rin bahagyang out ng order. May nakita akong Gabe upang maging sa pinakamaliliit na, kaya Ako magpa-pop out sa kanya, ilipat mo guys sa ibabaw. At tapos na. 

Kaya sagot ay pareho. Ang katapusan ng resulta ay pareho. Alin sa mga ito ang dalawang mga algorithm ang mas mainam? Ang ikalawang isa, Narinig ko. Bakit? 

Tagapagsalita 3: Ito ay n hakbang [hindi marinig]. 

David J. MALAN: Ito'y n hakbang sa karamihan. Kawili-wili. Kaya ito ay bagaman? Kaya kung paano ang nakuha ko mahanap ang pinakamaliliit na elemento? Gaano karaming mga hakbang na ito ay mayroon akong gumawa ang mahanap ang pinakamaliit na elemento? Ako ay isang tumingin sa lahat ng paraan sa dulo, tama? Dahil sa na ang pinakamasama kaso, kung ano kung Neil ay higit sa dito? Kaya lamang ang paghahanap ng mga na ang pinakamaliit na elemento tumatagal sa akin n hakbang na ito, o minus n 1. Ngunit, OK. Kaya ayusin Neil. Tandaan na, isang minuto o kaya ang nakalipas. 

Ngunit kung paano ang nakuha ko mahanap ang susunod na pinakamaliliit na elemento? Ito'y n minus 1, o minus n 2 talaga, mula sa bilang ng mga hakbang na ito. Kaya OK. Kaya ako nag-n minus 2. Ayos lang. Kaya na pakiramdam ng isang maliit na mas mahusay. Ayos lang. Gaano karaming mga hakbang sa susunod na oras upang mahanap ang numero ng tatlong? Kaya n minus 4. Kaya ito ay mababawasan, isa mas kaunti hakbang sa bawat pag-ulit. Kaya ito ay mas mahusay na pakiramdam, tama? Kung ang huling beses na iyon ay halos n beses n, oras na ito ito ay n minus 1, plus n minus 2, plus n minus 3, plus n minus 4, tuldok, tuldok, tuldok. Ngunit kung isipin ang mo mula sa iyong mga mataas na paaralan aklat-aralin, ang maliit na manlilinlang sheet sa likod na may mga formula, kung ikaw magdagdag ng hanggang na ito serye ng mga numero, ano ay ang kabuuang bilang ng mga hakbang pagpunta upang maging na tumagal ako dito? 

Ito ay isa sa mga iyon, i, n minus 1, n beses, na hinati sa 2. Kaya hayaan mo akong makita kung maaari kong hilahin ito up para lamang ng ilang sandali. At muli, ako uri ng ilang mga rounding mga numero lamang upang panatilihin ang aming mga buhay simple, ngunit bilang ko maalala muli, ito ay isang bagay tulad ng kung Gagawin ko n minus 1 bagay, pagkatapos n minus 2, pagkatapos n minus 3, ito ay humigit-kumulang isang bagay na tulad nito sa paglipas ng 2, at kung ako multiply ito out, na talaga n square. Na hindi pakiramdam masyadong mabuti. n minus n sa 2. 

Ngunit narito ang bagay. Sa computer science, kapag ang mga problema simulan upang makakuha ng kawili-wiling ay kapag n ay makakakuha ng talagang malaki. At kapag n nakakakuha talaga malaki, kung alin sa ang mga halagang ito ay pagpunta sa mangibabaw ang lahat ng ng iba? Ito ay uri ng mga n squared, tama? Oo, sa pamamagitan ng paghati 2 ay medyo mabuti. Ngunit kung ikaw ay pakikipag-usap tungkol sa bilyon-bilyong ng mga piraso ng data, o trillions ng mga piraso ng data, OK, kaya ikaw ay dalawang beses nang mas mabilis. Ngunit sino ba talagang nagmamalasakit kung malaki na numero, kung factor na ito ay kung ano ang nakukuha ng mas malaki at mas malaki. At tiyak, ito ay ginagawang higit pa sa isang pagkakaiba kaysa ito tao. Kaya kahit na na guys ay tama, ang pangalawang algorithm, aming tawagan ito pagpili ng uri, ay, sa tunay na mundo, isang bit mas mabilis na potensyal na, dahil ako ay pagkuha ng mas kaunting at mas kaunting hakbang sa bawat oras. 

Ito ay hindi tunay na sa panimula mas mabilis. Dahil kung namin talagang i-play ito out para sa malaking halaga ng n, sa dulo ng ang araw, para malaki sapat n, pa rin ito pagpunta sa pakiramdam medyo mabagal. Well, hayaan mo akong kumuha ng isa huling pass sa na. Iyon ay kung ano ang gusto kong tumawag pagpili-uri. Maaari mong i-reset ang guys inyong sarili isa huling oras? At sa huling pagkakataon, pupuntahan ko upang ipanukala ang isang bagay tinatawag na pagpapasok sort. Insertion sort pagiging, conceptually, medyo naiiba. 

Kaysa sa pagpunta papunta at pabalik at pagpili sa pinakamaliliit na elemento, ako lamang ng pagpunta sa makitungo sa bawat isa sa mga guys bilang ko makaharap ang mga ito, at ipasok ang mga ito sa kanilang wastong lugar. Kaya lang ako sa pagpunta sa magsimula sa Grace, at nakikita ko na siya bilang apat. Saan kinukuha bilang apat nabibilang? Hindi ko pa sinimulan ng pagbubukod-bukod ng anumang bagay, kaya Grace ay nakakakuha upang manatili doon. At ngayon ako pagpunta sa i-claim, kung magagawa mong kumuha ng isang hakbang sa iyong mga karapatan, ito aking listahan pinagsunod-sunod, ito ay ang aking unsorted natitirang listahan. Kaya ngayon ako pagpunta sa magpatuloy sa tabi, at kung ano ang iyong pangalan muli? 

Branson: Branson. 

David J. MALAN: Branson. Kaya Branson ay dalawang numero. Kaya ako ng pagpunta sa magdadala sa iyo out para sa isang sandali. At ngayon, saan ka nabibilang sa array na ito? Kaya sa kanan ng Grace. Kaya muli, kami uri ng paggawa Grace gawin ng maraming trabaho dito. Saan namin ilalagay mo? Kaya kami ay pagpunta sa slide ka sa pakaliwa, at ipasok Branson doon. Ngunit ngayon inaangkin ko na ka guys ay tapos na. Ngunit notice, hindi ko ginagamit ng dagdag na espasyo. Ito ay pa rin ang 2 elemento dito, 5 paglipas dito. Kabuuang sukat ng array ay 7, kaya ako hindi Pandaraya, ang lahat ng karapatan? 

Kaya ngayon mayroon kami, may Gabe dito, ang anim na numero, kung saan ka nabibilang? Nakakuha ka masuwerteng muli. Kaya mo makakuha upang manatili doon. Lang tumagal ng bahagyang hakbang sa kanan lamang upang gumawa ng malinaw na kayo ay pinagsunod-sunod. At ngayon, mayroon kaming Neil muli, numero isa, saan ka pumunta? At ngayon ay kung saan magsisimula kaming upang makita na algorithm na ito, bagaman sa unang sulyap, palagay ng medyo matalino, panoorin kung ano ang tungkol sa nangyari. Kung maaari mong humakbang pasulong. 

Saan nagpupunta ang mga nais naming ilagay Neil? Kaya malinaw naman dito, kaya paano huwag naming kumuha Neil doon? Tayo'y gawin ito hakbang-hakbang. Gabe, kung saan kailangan mong pumunta? Yep, kaya tumagal ng isang malaking hakbang, o dalawang half-hakbang na ito upang gumawa ng mga isang hakbang sa paglipas ng doon. Grace, kung saan ka pumunta? Magandang. Kaya isa pang hakbang. At sa wakas, Branson? Isa pang hakbang. At ngayon maaari naming ilagay Neil sa lugar. 

Kaya ngayon, patuloy na ito logic. Kahit na hindi kami paglilipat Neil sa ibabaw, at sa paglipas ng, at mahigit sa, upang ilagay sa kanya kung saan siya napupunta, sa pinakamasama kaso, ang susunod na bilang maaari naming makatagpo ng dati maging ang bilang, sabihin nating, nagkaroon ng isang numero zero, pagkatapos kami ay pagpunta sa shift ang lahat ng mga guys. Ipagpalagay na may isang numero, mga negatibong isa, pagkatapos kami ay may sa shift lahat ng mga guys. Kaya kami ay talagang lamang uri ng flipping ang problema sa paligid, tulad na kami ay paglilipat ng mga gastos mula sa pagpili proseso kaya ang pagpapasok proseso, tulad mo na guys lang nagkaroon upang ilipat ang halos n minus isang bagay bilang ng mga hakbang. At na bilang ng mga hakbang ay lamang ng pagpunta upang madagdagan ang bilang piliin ko pa numero, kung mayroon akong upang panatilihin shoving mo guys pabalik, at bumalik, at likod. 

Kaya ang malungkot bagay ay ngayon ang lahat ng mga algorithm ay n squared. Sabihin sige at salamat sa mga guys, at isalarawan ang mga ito ng kaunti magkaiba. Tunay na magaling. 

[Palakpakan] 

Ayos lang. May pumunta ka. Salamat sa - 

Branson: [hindi marinig] panatilihin ang mga numero. 

David J. MALAN: Hindi, maaari kang panatilihin ang mga numero ng pati na rin. Ayos lang. Maayos na Natapos. Ayos lang. Kaya sabihin makita kung hindi namin ngayon ay maaaring sabihin sa maikling pangungusap mas mabilis, at mas biswal, eksakto kung ano ang nangyari lamang dito tulad ng sumusunod. Pupunta ako sa sige at makuha ang Firefox. Ili-link namin ito demonstration sa website ng kurso ni. Java ay isang bit nakakainis upang nagtatrabaho sa ilang mga browser mga araw na ito. Kaya't kung ikaw ay may-play ito sa bahay, Napagtanto maaaring kailanganin mong gamitin ang Firefox upang makakuha ng mga ito gumagana. At kung ano ako ng pagpunta sa gawin sa mga ito demonstration ay ang sumusunod. 

Sa ibaba, mayroon akong isang buong grupo ng mga menu ng mga pagpipilian, kabilang ang isang panimula at isang itigil na pindutan. Gayundin, bilang isang tabi, tila na maging isang bug sa mga programang ito, kung saan mo Hindi maaaring aktwal na makita ang panimula o itigil pindutan maliban kung hawak mo ang Command o Alt plus at mag-zoom in, na pausisa Ipinapakita sa iyo ng higit pang mga pindutan. Kaya lamang Para sa Iyong Impormasyon kung i-play mo may mga ito sa bahay. Ngayon ako pagpunta sa i-click ang Start sa loob lamang ng sandali, pagkatapos ng pagtukoy ng isang pagka-antala ng, gaya, 200 millisecond dito, lamang upang maaari naming makita kung ano ang mangyayari. 

Kaya inaangkin ko na ito ay isang visualization sa mga unang algorithm mga guys ginawa, bubble sort, kung saan kami swapped mga tao pares-matalino. Ang key na pananaw upang ito visualization ay ang taas ng mga bar Kinakatawan ang laki ng mga numero. Kaya ang taller ang bar, ang Mas malaking numero. Mas maikli ang bar, mas maliit sa bilang. At kung napansin mo, kami ay pagpunta sa pamamagitan ng ang unang pag-ulit ng mga algorithm na ito, pagpapalit malaki at maliit na mga numero, upang ang maliit na bilang ang mauna at ang malaking bilang napupunta sa kanan. 

At sa lalong madaling makuha namin ang dulo ng array ng maraming higit pa kaysa sa mga numero ng pitong, kami ay pagpunta upang bumalik sa simula. At umasa na ito. Sa malayong kaliwa, maliit na tao ang nangyayari upang magpalitan sa gilid, at ito umuulit proseso. Ngayon visualization ito ay makakakuha ng mabilis pagbubutas, kaya ipaalam sa akin sige at itigil ito, baguhin ang mga pagkaantala sa isang bagay magkano mas mabilis lang upang makakuha ng ngayon, masubukan algorithm na ito. 

Kaya kahit na ko na sped up ito, ito ay tulad ng pag-upgrade ang aking processor, pagbili isang bagong computer. Hindi ko pa sa panimula nagbago ng aking algorithm, ngunit maaari mo talagang makakita ng higit pang malinaw kaysa sa mga kawani na tao, na ang malaki mga numero ay bulubok up sa tuktok, at ang maliit na mga numero ay bulubok pababa sa ilalim. At ngayon bagay na ito dito pinagsunod-sunod. At bilang isang bukod, sa mga parisukat, mayroong ilan lang Bookkeeping doon sa makatulong sa iyo na bilangin kung gaano karaming mga paghahambing, o kung gaano karaming mga mayroon swaps talaga ang nagawa. 

Well, sabihin subukan ang isa sa ang iba pa naming nakita. Hayaan akong mag-click sa bubble sort dito, at hayaan mo akong pumili, at ang buong web page ay isang maliit na maraming surot. Sabihin tanggapin ang mga panganib at patakbuhin itong muli. Nagkaroon kami pumunta. Kaya natin gawin seleksyon-uri. Hindi ko alam kung bakit ang menu Lumilitaw banda roon. Tayo'y mag-zoom in upang maayos na bug, baguhin ito sa 50. Ah, sabihin talagang gawin na mas mabilis. Limang millisecond o kaya, at Start. 

Kaya ito ay seleksyon-uri. Kaya muli, isipin ang tungkol sa kung ano ang aming ginawa gamit ang mga kawani na tao up dito. Nagpunta kami sa pamamagitan ng array at napili ang pinakamaliit na elemento muli, at muli, at muli. Ngayon i-claim ko na noon ay pa rin medyo masama. Pa rin Ito ay n squared, bigyan o kumuha, ngunit ito ay, sa tunay na mundo, isang bit mas mabilis, dahil nga ako ay pagkuha bahagyang mas kaunting mga hakbang na ito sa bawat oras. Ngunit lamang ang pinag-uusapan natin kung ano? Siguro 40 o kaya bar dito? Hindi pinag-uusapan natin 40,000,000. Kaya ito ay hindi talagang i-clear sa akin na ay sa katunayan ng isang makabuluhang pakinabang. 

Hayaan akong ngayon bumalik at baguhin sa aming ikatlong algorithm, na kung saan ay piliin pagpapasok ng pag-uuri. At ngayon talaga dahil maraming surot ang menu talagang hindi dapat pababa doon. Kaya ngayon kami mag-scroll back up dito at simulan ang algorithm. Sigaw, magsimula at huminto. Kaya ito isang uri ng mga may kaakit-akit pattern upang ito, kung saan hindi namin muli pagpapasok ng mga tao, o sa kasong ito, ang mga bar sa kanilang mga naaangkop na lokasyon. At nang tapos na ito bago Ako naka-paligid. Ngunit ang isang ito, masyadong, sa teorya, ay pa rin n squared. 

Kaya sabihin makita kung hindi namin sabihin sa maikling pangungusap ang mga tulad ng mga sumusunod. Pupuntahan ko sige lang at bigyan amin ang uri ng isang pangkaraniwang paraan ng pakikipag-usap tungkol sa mga bagay na ito, hayaan mo akong ipakilala lamang ng kaunti ng pagtatanda dito. Ikaw ay tungkol sa upang makita ang isang bagay na tinatawag na malaki O, sapagkat ito ay literal isang malaking O. At ito ay isang paraan na ang isang computer siyentipiko o isang dalubhasa sa matematika kahit na gumagamit ng upang ilarawan ang oras ng ilang mga algorithm. Ilang hakbang na ang ibig talagang tumagal? 

Ngayon Pupunta ako sa sarili ko mapahiya sa ang aking sulat-kamay dito sa loob lamang ng ilang sandali. Ngunit ipaalam sa akin sige at sabihin na ito ang magiging malaking O paglipas dito. At hayaan mo akong ipakilala ang isa pang simbolo, isang kabisera wakas. Omega ay magiging mga tapat, talaga, ng malaking O. Sapagkat malaki O ibig sabihin, sa pinakamasama kaso, kung magkano ang oras algorithm ay maaaring tumagal ng ilang mga, sa mga tuntunin ng n, wakas ay pagpunta sa maging gaano karaming oras maaari itong kumuha sa ang pinakamahusay na kaso. At kami makita kung ano ang ibig sabihin namin sa pamamagitan ng pinakamahusay na kaso sa loob lamang ng ilang sandali. 

Kaya natin simulan ang isang bagay na simple. Hayaan akong magsimula sa isang linear paghahanap. Kaya hindi pag-uuri. Susubukan naming itawag sa linear paghahanap. At ngayon, gumawa ng isang maliit na talahanayan out ng ito. At ngayon, sa kaso ng mga linear na paghahanap, sa pinakamasama kaso, kung ilang mga hakbang ay ito pagpunta sa tumagal sa akin upang makahanap ng isang bilang ng mga arbitrary choice? At mayroong n kabuuang mga mga pinto o n kabuuang numero. Pinakamahina ang kaso. Gaano karaming mga hakbang na ito ako pagpunta upang magkaroon ng upang gawin upang mahanap ang numero ng 50 sa isang array ng n mga pinto? At kung bakit? Dahil maaari itong maging ang lahat ng mga paraan sa ibabaw papunta sa dulo. Kaya halos tulad Jennifer nakatagpo, ang numero 50 ay ang lahat ng mga paraan sa paglipas, kaya in ang pinakamasama kaso linear na sa paghahanap ay malaki mga O ng n, makakakita namin sasabihin. 

Paano ang tungkol sa mga pinakamahusay na kaso, kung makakuha ka talagang mapalad? Lamang Ito ay pagpunta sa tumagal ng isang hakbang, o isang pare-pareho ang bilang ng mga hakbang. Kaya namin ilarawan na bilang 1. So na ito ay medyo magandang. Ngayon ano kung namin ginawang isang bagay i binary paghahanap? Kaya binary paghahanap, sa pinakamalala kaso, kinuha kung magkano ang oras? 

[INTERPOSING tinig] 

David J. MALAN: Kaya talaga, ako narinig ito sa isang lugar na ilang. Kaya talaga ito ay mag-log n, bigyan o kumuha, dahil bilang hinati namin ang listahan sa kalahati muli, at muli, at muli, nagpapaumanhin kami magagawang upang mahanap, sa huli, ang halaga, kung ito doon, pero may catch a. Ano ang palagay na kami ay may sa mang-ahas para sa binary paghahanap? Mayroon na pinagsunod-sunod. Hindi Ito ay naka pinagbukud-bukod, maaari mong hatiin ang bagay na sa kalahati muli at muli, at ikaw Maaari pumunta sa kaliwa, at maaari kang pumunta karapatan, at Maaari kang pumunta kaliwa at kanan, ngunit ikaw ay hindi pagpunta upang mahanap ang mga elemento kung listahan ay hindi pinagsunod-sunod, dahil baka makaligtaan ito. Sapagkat ang iyong mga hyuristiko, para pagpunta kaliwa o pakanan ay ng pagpunta sa mai-flawed kung ito ay sa katunayan hindi pinagsunod-sunod. Kaya mayroong isang uri ng isang nakatagong gastos sa paggamit ng isang bagay na katulad nito. 

Ngayon, sabihin pumunta sa aming pag-uuri algorithm hindi naghahanap - oh, talaga natin pumunta sa blangko. Binary paghahanap sa pinakamahusay na kaso? Ito ay din 1 kung ito lamang ang mangyayari sa maging sa pinakadulo gitna ng array, o sa gitna ng aklat telepono. Ngayon ipaalam sa ni gawin bubble-uri-uriin. Kaya muli, na namin ngayon ng pagpasok ng uri, hindi ang mga paghahanap. 

Sa pinakamasama kaso, kung gaano karaming mga hakbang na kami claim na bubble sort pupuntahan tumagal? n nakalapat. Kaya pupuntahan ko upang gumuhit na. Ooh, ang aking sulat-kamay hitsura kahit na mas masahol pa kapag ito ay inaasahang na malaki. Ayos lang. Kaya na n squared. At sa pinakamahusay na kaso ng bubble sort, kung gaano karaming mga hakbang na ito ng pagpunta sa tumagal? 1, Narinig ko. 

Tagapagsalita 1: n. 

David J. MALAN: n, Narinig ko. 

Tagapagsalita 1: 2. 

David J. MALAN: 2, Narinig ko. Huwag akong marinig 3? Ayos lang. Kaya ko nalaman 1 n, 2, ngunit sabihin pick bukod ng hindi bababa sa ang unang ng mga mga mungkahi, 1. Ito ay hindi isang masamang likas na hilig, sapagkat ito uri ng sumusunod sa isang pattern dito. Ngunit kung ito lamang ay tumatagal ng 1 hakbang, kung paano sa mundo kaya kong i-claim na ang listahan ay pinagsunod-sunod, dahil kung lamang ako pinapayagan gumawa ng 1 hakbang, kung gaano karaming mga elemento maaari ko talagang tingnan upang matiyak? Well, may 1, na nangangahulugan na n minus 1 elemento na maaaring maging out sa pagkakasunud-sunod, at lang ako sa ng pagpunta sa pananampalataya pagkatapos ng pagtingin sa 1 elemento na ang bagay ay pinagsunod-sunod. So 1 ay hindi itama dito. Kaya Nagnais ng pinakamababang, kung gaano karaming ang mayroon ako upang tumingin sa? 

[INTERPOSING tinig] 

David J. MALAN: n minus 1, o talagang, n, dahil kailangan kong tumingin sa bawat elemento upang matiyak na hindi ito out ng order. Ngunit muli, kailangan namin pagsunud-sunurin ng wave aming mga kamay sa mas maliit na mga numero at ipinapalagay na, bilang n nakukuha ng malaki, ang mga ito ay hindi kawili-wili pa rin. Kaya na bubble sort. At ngayon, sabihin gawin ang mga nakaraang dalawang. Pinili uri, at pagkatapos ay bibigyan namin ng gawin insertion sort. At pagkatapos kami ay pumutok ang iyong isip may bagay magkano mas mahusay kaysa sa lahat ng mga ito. Ayos lang. 

Ano ang pinakamasamang sitwasyon tumatakbo oras ng pagpili-uri? 

Tagapagsalita 4: n squared. 

David J. MALAN: n square, ako pagdinig. Ngunit bakit n nakalapat, intuitively? 

Tagapagsalita 4: Dahil lang namin ginawa ito. 

David J. MALAN: Dahil lang namin ginawa ito. OK. Magandang sagot. Ngunit intuitively, bakit ang seleksyon sort n squared? Ano ang mayroon kami na gawin muli at muli? Kinailangan naming panatilihin ang pag-scan sa pamamagitan ng, mga mo na ang pinakamaliit na, ikaw ang pinakamaliliit na, ikaw ang pinakamaliit. At ipinagkaloob, nagawa naming gumawa ng n hakbang, pagkatapos n minus 1, pagkatapos n minus 2. Ngunit kung ikaw uri ng magdagdag ng mga lahat up, o dalhin ito sa paniniwala na ang Idinagdag ko na up ang mga ito sa advance, makakuha ng mga namin humigit-kumulang n squared minus ang ilang mga mas maliit na mga numero ng. Kaya pupuntahan ko tawagan n ito squared. Ngunit sa pagpili-uri sa ang pinakamahusay na kaso, kung gaano karaming mga hakbang na ito pagpunta sa tumagal sa akin? 

Tagapagsalita 5: [hindi marinig] 

David J. MALAN: Ito ay sa kasamaang-palad pa rin n squared, tama? Dahil kung ako ang pagpili sa mga pinakamaliliit elemento, at nagkaroon kami ng pitong mga tao dito, Ko lang alam, sa sandaling nakuha ko sa pinakadulo end, na aking nakita na ang pinakamaliit na numero, nasaan man siya o maaaring siya ay naging. Ngunit paano ko mahanap ang susunod na pinakamaliliit number? Mayroon akong gawin ang isa pang pass. Kaya't sa pinakamahusay na kaso, kung ano ang input upang seleksyon-uri? Ito ay isang mayroon listahan-uri-uriin, ang bilang na ng isa, bilang dalawang, ang bilang na tatlo, bilang apat. Ngunit Ako ay isang computer. Maaari lamang akong tumingin sa isa bagay sa isang pagkakataon. Hindi ako makapag-sort ng tumagal ng isang hakbang bumalik tulad ng isang tao at sabihing, ooh, ito mukhang tama. 

Maaari lamang akong dinggin kawastuhan sa pagpili-uri sa pamamagitan ng pagpili ng pinakamaliliit na numero. Ngunit kahit na mahanap ko ang numero ng isa muna, kung hindi ko alam kung anumang bagay tungkol sa ang iba pang mga numero, na gagawin ko hindi, lahat ko malaman na ang ko na ang nai-ipinasa array isang o isang hanay ng mga pinto sa likod na kung saan ay mga numero, ang tanging paraan na alam ko na ang isa ay ang pinakamaliit? Kung nakukuha ko lahat ng paraan dito at nauunawaan, sumpain, ang isa ay sa katunayan na ang pinakamaliit na. 

Ngunit paano ko nang tukuyin na dalawa ang susunod na pinakamaliit? Sa pamamagitan ng paggawa ng parehong kawalang-kaya muli at muli. Kaya sa wakas, na may pagpapasok ng uri, paano, sa pinakamasama kaso, ang sabihin namin ito ay gumaganap? Ito masyadong ay n squared. At kung paano tungkol sa ang pinakamahusay na kaso? Susubukan naming umalis na bilang isang cliffhanger. Susubukan naming fill in na blangko ang susunod na oras, ngunit unang hayaan mo akong magpanukala na namin sa panimula gawin mas mahusay kaysa sa lahat ng mga ito, ang lahat ng karapatan? 

Kaya sa tingin para sa iyong sarili kung ano ang pagpapasok ng -uri-uriin ang nangyayari upang maging. Well, na noon ay hindi masyadong dramatic, dahil ako ang isa lamang na nakita ang pagbabago. Wow. OK. Kaya dito kami ay may isang medyo ibang pagpapakita. Kung ako mag-zoom in dito, makikita mo na sa sa kaliwa mayroon kaming bubble sort, sa gitna mayroon kaming seleksyon uri, at sa dulong kanan, mayroon kaming isang bagay namin hindi Tiningnan pa tinatawag na pagsamahin ang pag-uuri. Subalit isaalang-alang kung ano ang aming nakapunta paggawa dito kaya malayo ngayon. Kapag Jennifer unang dumating up sa entablado, kami nagpunta sa pamamagitan ng array ng mga numero muli, at muli, na may linear paghahanap, at kami nakakuha linear tumatakbo oras, malaki O ng n, kaya na magsalita. 

Kapag kami ngayon isaalang-alang ang unang linggo ng klase, kapag kami ay hatiin at lupigin, at kami ang phone book pansiwang, at Jennifer, at kami sama-sama magagamit na key pananaw, na noon ay sa ulitin ang iyong sarili muli at muli sa pamamagitan ng sa paano pa man ibinabato ang layo ng, ibinabato ang layo ng, itsa, kalahati ng mga problema, o Sa pangkalahatan, paghahati ng problema sa kalahati, at pagkatapos ay pagpapagamot ng mga mas maliit na piraso ng ang problema bilang conceptually katumbas upang ang iba pang mga, namin sa paanuman ginawa sa panimula mas mahusay. Ngunit na may bubble-uri-uriin, na may mga seleksyon uri, na may pagpapasok ng uri, kami nag maaari walang ganoong mga pananaw na Jennifer ginawa. Kami medyo magkano lamang lumakad pabalik at nakalahad isang buo magsikisikan ng beses na, at namin tweaked bagay Medyo, pagpapalit sa ayos na ito, siguro pagpasok o pagpili. Ngunit sa pagtatapos ng araw, ako ginawa ng maraming isang ng nakahihiya walking papunta at pabalik. Kami ay hindi talaga pakikinabangan ang isang bagay matalino tulad ng Jennifer ginawa tulad ng paghahati at mapanakop. 

Kaya pagsamahin ang uri, sa pamamagitan ng kaibahan, na aming hindi makikita hanggang sa susunod na linggo, ito ay pagpunta upang masulit na key ideya sa pamamagitan ng paghati ang input, at pagkatapos ay paghati, at pagkatapos ay paghati, at pagkatapos ay paghati. At sa bawat pag-ulit ng na loop, pag-uuri sa kaliwa kalahati, at ang karapatan kalahati, at pagkatapos ay sa kaliwa kalahati ng kaliwang kalahati, at ang kanang kalahati ng kaliwa, at pagkatapos ay sa kaliwang kalahati ng kanang kalahati, at ang karapatan kalahati ng kanang kalahati. At paulit-ulit na muli at muli. 

So makikita mo ang biswal, ngunit ito ay kung ano ang naghihintay sa amin sa susunod na linggo. At sa pangkalahatan, kapag sa tingin namin ang kaunti bit na mas mahirap sa anumang naturang problema. Kami n squared sa kaliwa, n squared sa gitna, at n mag-log n sa kanan. Kaya mayroong iyong tunay na cliffhanger. Gagamitin namin ang nakikita mo sa Lunes. 

[Palakpakan]