[Powered by Google Translate] [Ġimgħa 3, Ikompli] 

[David J. Malan - Università ta 'Harvard] 

[Dan huwa CS50. - CS50.TV] 

Kull dritt. Merħba lura. Dan huwa CS50 u dan huwa l-aħħar ta 'ġimgħa 3. 

Għalhekk għal dawk familjari, sena li għaddiet Harvard nediet dak li jissejjaħ il-Lab Innovazzjoni, jew i-laboratorju, li huwa bini isbaħ madwar l-xmara fuq il-kampus HBS tal- li huwa miftuħ għall-istudenti kulleġġ, studenti GSAs, studenti minn kampus madwar, inkluż fakultà, u huwa post li jingħaqdu flimkien biex jaħdmu fuq affarijiet innovattivi, affarijiet partikolarment intraprenditorjali jekk inti u 0 jew aktar ħbieb qed taħseb li tagħmel xi ħaġa intraprenditorjali jew matul din il-klassi, wara din il-klassi, jew lil hinn. 

Allura waħda mill-affarijiet li jagħmlu fuq terminu J hija dawn il-vjaġġi, waħda minnhom hija li New York, li wieħed minnhom huwa li Silicon Valley. L-ispazju huwa limitat ħafna, iżda huwa opportunità biex togħrok ispallejn ma MBAs u studenti gradwati madwar il-kampus u attwalment jqattgħu ħin f'dawk l-oqsma rispettivi chatting up fetħu, chat up intraprendituri u simili. Allura jekk ikunu interessati, check out dan il-URL hawn. Huwa disponibbli wkoll fuq il-pjastri online. 

Jista aħna jtaffi l-awdjo-dar biss ftit? Jekk inti tixtieq li jingħaqdu magħna għall-ikel din il-ġimgħa, pm 1:15 fil Fire & Silġ, jekk jogħġbok ras hemmhekk. Apologies jekk il-formola hija diġà mimlija mill-ħin li inti naslu s'hemm. Iżda aħna ser tkompli dan onward tradizzjoni. 

Illum aħna tkompli d-diskussjoni livell ogħla ta 'diversi problemi li nistgħu ssolvi, jiffoka ħafna inqas, illum inqas, fuq il-kodiċi u ħafna aktar fuq l-ideat. Allura taħseb lura għal ġimgħa 0 meta aħna Tore ktieb tat-telefon fil-nofs, l-għan tiegħu kien li jagħmel xi ħaġa, ċertament, xi ftit drammatiku imma li jibagħtu l-punt li tiftix ma għandhom ikunu, neċessarjament, kif ovvji ewwel daqqa t'għajn kif inti tista 'taħseb. U sabiex jissolvew problemi b'mod ġenerali mhux bilfors dejjem l-aħjar - L-aktar soluzzjoni ovvja mhux bilfors tkun l-aħjar. Allura kellna dan il-ktieb tat-telefon u, franchement, lkoll f'din il-kamra kienet l-instincts, aktar probabbli, li għandu jibda fl-nofs meta jkunu qed ifittxu Mike Smith u mbagħad mur lemin jew xellug ibbażata fuq kwalunkwe ittra ta 'l-alfabett aħna ġara li jispiċċaw fuq. 

Iżda dik l-idea sempliċi li aħna bnedmin ħadu għall mogħtija għal sakemm verament għandha tibda fuq quddiemnett tal-moħħ tiegħek għaliex il-problemi nikseb ħafna aktar kumpless minn ktieb tat-telefon, dawk l-istess sempliċi, intuwizzjoni brillanti huma liema huma se jħallina naħsdu sabiex isolvu problemi ħafna aktar ikkumplikati u aktar interessanti, fosthom uħud mill-affarijiet nieħdu għall mogħtija diġà f'dawn il-jiem. Biljuni ta 'paġni tal-web hemmhekk, u għadhom Google u Bing u simili huma kapaċi jsibu affarijiet għalina bħal dik. Li mhux jiġri bl-użu ta 'tfittxija lineari, tiftix permezz-paġni kollha web possibbli. Facebook huwa kapaċi jgħidlek li kollha tal-ħbieb tiegħek huma jew ħbieb tal-ħbieb, u li wisq jista 'jsir apparentement fi instant f'dawn il-jiem anki jekk dawn għandhom miljuni ta 'utenti. 

U hekk kif għandna attwalment isolvu problemi fuq skala li finalment se tnaqqas l-ideat ħarisna lejn fl f'ġimgħa 0 u daqsxejn aktar illum. Aħna mhux se terġa 'tesegwixxi dan algoritmu, iżda tfakkar aħna wkoll għamlet fil f'ġimgħa 0 f'dan l-eżerċizzju fejn kellna kulħadd bilwieqfa, jieħdu fuq in-numru 1, u allura kellna kulħadd awto-għadd mill-tqabbil off, li żżid in-numri tiegħek flimkien, allura nofs il-gang poġġa bilqiegħda fuq kull iterazzjoni. Allura aħna marru minn 500 student għal 250 sa 125 u ibqa 'sejjer hekk. Imma kif għidna nhar it-Tnejn, l-idea qawwija hemmhekk kienet li jekk aħna rdoppja l-daqs ta 'dik il-problema u l-gidien mill-Ġustizzja jew Ec 10 daħal lura fil-kamra u ingħaqdet magħna, ukoll, nistgħu probabbilment joqgħod dak il-grupp aggregat kollu mal biss 1 iterazzjoni big aktar tal-linja għaliex biss forsi doppju tad-daqs jew fil-każ daqsxejn aktar mid-doppju tad-daqs Ec 10 ta. U hekk aħna se jkollu jonfoq ftit aktar żmien, iżda aħna ma jkollu jonfoq 400 jew 700 aktar passi. 

Just li żebgħa din l-istampa b'mod li l-ftit inqas astratt, ejja ma jkunu kulħadd stand up. Imma jekk dawk minnkom li għażlu li joqogħdu fil-orkestra tal-lum ma mfakkar wieqfa, ejja ara jekk nistgħu insemmu fost inti li l-persuna tallest hija billi għamlet l-istess tip ta 'algoritmu komparattiv. Mela jekk int seduta fil-orkestra, apologies tiegħi, imma pass 1, stand up; pass 2, par off ma 'xi ħadd fil-qrib miegħek, figura li huwa taller, u joqogħdu bilqegħda jekk inti iqsar. Imbagħad irrepeti. [Studenti murmuring] 

Okay. Okay. Wieħed titħalla wieqfa. X'hemm isem tiegħek? >> Andrew. 

Andrew, inti l-persuna tallest fit-taqsima orkestra illum. 

Prosit. [Applause u cheering] Okay. Jkollhom sedil. Allura sibna Andrew. Imma kemm żmien ser jieħu me, per eżempju, biex isibu Andrew f'din it-taqsima orkestra ta '50 + jew hekk in-nies? I jistgħu ħadu approċċ pjuttost sempliċi u tibda hawn. U jien 2 persuni stand up u I biss jqabbluhom, u mbagħad I say kull min huwa kemmxejn iqsar, "Okay, inti tiltaqa," u jien ser tiftakar li l-persuna taller kien. Imbagħad Nirrepeti, irrepeti, irrepeti, u jien tistrieħ fuq il-persuna tallest sal I issib xi ħadd ftit taller minn dawn, f'liema punt il-persuna kemmxejn iqsar irid imbagħad joqogħdu bilqegħda. Iżda f'dak algoritmu f'din it-taqsima orkestra, jekk ikun hemm n minnkom, kemm passi huwa li algoritmu se jieħu? >> [Student] N. 

Huwa ser jieħu n, id-dritt, minħabba li fl-agħar każ, biex ngħidu hekk, il-persuna tallest hija l-persuna ħafna aħħar li niġi biex biss billi xortih ħażina każwali. Allura fl-agħar każ, il-ħin tmexxija ta 'din l-algorithm hija lineari, huwa n, fejn n huwa n-numru totali ta 'nies fl-ispazju, id-daqs tal-problema. Xi ngħidu dwar dan algoritmu? Il-fatt li intom kollha saqajh u mbagħad għal darb'oħra nofs inti sib stabbiliti, nofs inti sib stabbiliti, nofs inti sib stabbiliti. Kemm passi għandhom li ħadu jekk hemm n minnkom hawn? [Student] N log n. >> Dan ikun agħar. Log n. 

Allura log n, anki jekk inti ma pjuttost tiftakar dak logaritmu hija, għal issa, biss japprezzaw li għandu x'jaqsam b'xi mod li din tnaqqas bin-nofs u tnaqqas bin-nofs u tnaqqas bin-nofs. Ma kellhiex tkun fattur ta '2. Dan jista 'jkun fattur ta' 3. Imma hija din ripetizzjoni ta 'l-istess tip ta' fattur tali li d-daqs tal-problema tibda hawn iżda imbagħad immedjatament tmur hawn, allura hawnhekk, allura hawnhekk, allura hawnhekk. Int mhux qed tieħu gdim żgħar barra mill-problema, int verament tqattiegħ bogħod lejn din bil-kbir waqgħet swoop kull darba. Allura kellna 50 persuna, imbagħad 25, imbagħad 12 ½ jew 13-nies bil-wieqfa, imbagħad 6 ½ u oħrajn sakemm permanenti finalment biss Andrew tħalliet. Allura aħna qed tmur biex sejħa li log ta 'n, u inti tista Ħares din kif ġej. Recall din l-istampa hawn fejn algoritmu lineari huwa bħall-linja ħamra hemm, il-linja isfar kienet l-għadd mill 2s algoritmu li aħna użati għall-istudenti għadd fil-passat, iżda llum il-Grail qaddis se jibqa din il-linja ħadra fejn jekk aħna rduppjat l-għadd ta 'nies fis-sezzjoni orkestra jew biss qal, infern, ejja jkollhom kulħadd fil-kamra kollha bilwieqfa, ma jkunx tali big deal għaliex aħna bejn wieħed u ieħor tirdoppja kif ħafna nies huma stabbiliti hawn, 1 iterazzjoni aktar, mhux problema. 

Imxejna sabet Andrew jew min jiġri li jkun taller minn Andrew fil-mezzanin jew fil-gallarija. Allura din l-idea sempliċi li ħadna tant għall mogħtija fil-ktieb tat-telefon, tirrealizza li hemm postijiet tant differenti li bihom nistgħu japplikaw għaliha. Just biex SLAP xi lingwaġġ - fil-fatt, minflok lingwaġġ 1, let me go għal din l-istampa hawn. Dritt issa tkellimna dwar n u n / 2 u mbagħad log ta 'ln, iżda nistgħu ċertament toħroġ bi, kif aħna se matul il-kors tas-semestru, xorta oħra ta 'formuli matematiċi sabiex jiddeskrivi dan il-kunċett ġenerali ta' running time. Dawn huma barra mill-kuntest għal issa għaliex aħna ser tara qabel twil algoritmi li dawn fil-fatt jirrappreżentaw. 

Iżda l-avviż hawn il-linja n lineari, il-linja dritta, huwa attwalment baxx ħafna tipponta dritt issa. Li tip ta 'illużjoni ottika li aħna biss bidla dak l-assi x tirrappreżenta u l-assi y, u nistgħu nagħmlu punt linja dritta fi kwalunkwe direzzjoni li rridu. Iżda r-raġuni li huwa hekk apparentement fissa issa huwa għaliex għandna bżonn biex tagħmel spazju fuq din il-graff għal żminijiet ħafna aktar kajman running. Għal issa, jafu li hemm xi algoritmi pretty ħżiena fil-ħajja, li wħud minnhom ma tieħu passi n jew, aħjar għadhom, log passi n iżda aktar. Allura fuq mil-linja n hawn fuq l-avviż qiegħ hemm żminijiet n log ta 'ln, u aħna ser tara dak li dan ifisser qabel twil. Fuq din huwa n kwadrat, u aħna ma bbenefikawx xi algoritmi kwadru n għadhom imma aħna waslu biex. U li jistenna tassew ħżiena. Hemm 2 għall-n, xi ħaġa esponenzjali, li jħoss saħansitra agħar. And yet, curiously, allura hemm n kubiku, li jekk int it-tip ta 'ħsieb quddiem, jekk inti tip ta 'tagħmel l-matematika, 2 għall-n attwalment isir ferm straighter, ħafna ogħla milli n up kubiku jekk inti tħares lejn l-assi biżżejjed out. Allura Avviż dritt issa dawn l-assi huma arbitrarjament 2-10 fuq l-assi x. 

U dak ma jfisser? Dan ifisser 2 nies sa 10 nies fil-kamra. Li kollox mezzi x: daqs tal-problema, tkun xi tkun il-kuntest huwa. U l-assi vertikali dritt issa huwa numru ta 'sekonda jew numru ta' passi - xi unità ta 'ħin. Iżda avviż li għamilhom 0 sa 60 u 0-10. Imma jekk aħna tip ta 'zoom out, kif inti tista' fl-Excel jew xi softwer iċċartjar, u immorru sa 200.000, avviż li xi ħaġa bħal 2 sa n se kompletament jisbqu l-ħinijiet kurrenti ta 'n kwadrat, n kubiku, n log n - kollox konna tkellimna dwar s'issa. And yet-qabda huwa meta tibda titkellem dwar affarijiet bħal Facebook fejn ikollok, ħafna ħafna, ħafna nies kollha interkonnessi, għandek n-nies, li kull wieħed minnhom jista 'jkollhom bħala ħafna bħala ħbieb n jekk kulħadd huwa tip ta 'buddy buddy-fid-dinja, ukoll, dan huwa n darbiet n diġà, b'tali mod li l-ħbiberiji n possibbli kwadri, mill-inqas fl-1 direzzjoni, n ħbiberiji possibbli kwadru. Allura li diġà jissuġġerixxi li tiftix graff soċjali Facebook, biex ngħidu hekk, jistgħu jibdew jiġu espressi dawn it-tipi ta 'formuli. 

Aħna ser jiġu lura u tagħmel dan ħafna aktar konkreti, iżda għal issa, l-għan għall-ġimgħat ħafna li jmiss se tkun żgur li ma tmur dwar algoritmi implimentazzjoni jew tal-kodiċi li jispiċċaw teħid ta 'żmien kemm xi ħaġa bħal din. Imma l-ħaġa affaxxinanti dwar ix-xjenza tal-kompjuter jekk inti tkompli fuq f'dan il-qasam tieħu klassijiet bħal CS121, CS124, it-tnejn li huma korsijiet teorija, hija li hemm attwalment xi problemi li jeżistu f'dan dinja li fundamentalment, safejn nafu, ma jistgħux jiġu solvuti aktar malajr mill-agħar ta 'dawn graffs attwalment jissuġġerixxi. Allura hemm ħafna problemi miftuħa f'din id-dinja li jagħmlu ħafna aħjar minn bnedmin ikollhom s'issa. 

Mela ejja nibdew imbagħad ma dan l-eżempju. Rajna taqbida Sean ma 'din camera fuq, wisq awkwardly fuq video. Iżda r-realtà kien meta Sean kienet imqabbda konstatazzjoni fuq bord bħal dan in-numru 7, ifakkar li jien qal li, "Hemm x'imkien wara dawn il-biċċiet tal-karti jew bibien abjad "In-numru 7. Sean, isibuha għalina." U kien wonderfully skomdi għall-għassa għaliex kien verament qed jitħabtu ma 'din il-problema. Iżda r-realtà kienet Sean ma kif ukoll xi ħadd fil-kamra jista 'jkollha jsir. Huwa ħa ftit itwal minn persuna tipiku jista 'jkollhom, iżda huwa preżunt li kien hemm xi trick għal din il-problema, huwa preżunt li kien xi ħaġa nieqsa. U ma jgħinu li mijiet ta 'l-għajnejn kienu li jkollhom isfel fuq lilu. 

Iżda r-realtà kienet jekk il-kontribut għall-problema huwa mazz ta 'numri bl-addoċċ u int qed jintalbu biex isibu 1 in-numru, l-aħjar li tista 'tagħmel huwa tfittxija lineari. Ibda fuq ix-xellug, jimxu lejn il-lemin, jew jibda fil-dritt, jimxu lejn ix-xellug. Retroattivament, aħna tista 'tkun ħsieb, "Sean, għaliex ma inti biss tibda mill-tarf l-ieħor?" Ukoll, 7 setgħet daqstant faċilment kien hawn saltwarjament, iżda I deliberatament tqiegħed lilha hemmhekk minħabba I dehret hu mhux se jibda fl-aħħar. So I tip ta 'manipulati-sitwazzjoni, iżda b'kumbinazzjoni każwali 7 seta' kien kullimkien. Allura jibda mill-aħħar id-dritt seta 'kien aħjar imbagħad, imma dak jekk il-sena li jmiss I jiċċaqalqu 7 x'imkien ieħor? Li mhux soluzzjoni fundamentalment ġdid għall-problema - jibdew mill-1 tarf jew l-oħra - meta int tingħata l-ebda suppożizzjonijiet oħra. Allura Sean bdiet tfittex permezz-numri u qal, "5. Li mhux hawn." Imbagħad huwa mar hawn u raw 19, imbagħad huwa waqfa qasira għal madwar 20 sekondi, allura huwa kien fetaħ dan għal 13, u mbagħad ħareġ ċar li ma jidhirx li hemm tendenza hawn. Ma kienx 1, 2, 3, 4 jew simili. Kien hemm lakuni fil-numri, li ma jgħinu. U wkoll, il-fatt li I użati dawn il-biċċiet irħas ta 'karta biex tkopri up in-numri huwa attwalment intenzjonata, għaliex jekk I jitneħħew dawn biċċiet tal-karti, ħafna minna, Sean inklużi, probabbilment kien glanced tip ta 'makroskopikament fil-blackboard u qal, "Oh, 7 hija ovvjament hemm dritt." Aħna ma kien istantanjament. 

U li jista 'jkun il-mod il-moħħ tal-bniedem xogħlijiet sa ċertu punt, iżda fir-realtà, l-għajnejn tiegħu jew mind kien probabbilment xkumar-numri mill-lemin għax-xellug, xellug għal-lemin, middle fuq barra - xi ħaġa li kien għaddej fiżjoloġikament tali li qisni kien qed jiġri istantanjament, iżda odds huma saħansitra internament kien hemm xi tip ta 'metodoloġija għall-konstatazzjoni 7. U fil-fatt, issa li aħna qed jitkellem dwar arrays u strutturi ta 'data u ġewwa memorja ta 'kompjuter, l-unika ħaġa aħna bnedmin tista' tagħmel hu li tħares lejn postijiet memorja individwali 1 kull darba. 

Allura kull post ieħor tista 'ukoll tkun koperta up ma' wħud biċċa karta għaliex aħna ma tistax tara dan xorta waħda. Nistgħu biss tagħmel 1 ħaġa kull darba. Allura f'dan il-każ, fil-każ Sean, aħna marru hawn u mbagħad aħna marru hawn u allura aħna marru hawn, hawn, hawn, hawn, ltqajna għaqlija sa tmiem u biss tip ta 'skipped dan wieħed arbitrarju u sabet 7 hemmhekk. Dan wieħed ma kienx partikolarment speċjali. Hija wisq kien out of order. Imma hu finalment sabet 7. Imma issa l-takeaway verament hija li l-aħjar li tista 'tagħmel meta jingħata l-ebda informazzjoni għajr numri bl-addoċċ magħżula huwa li tibda mill-xellug jew tibda minn fuq il-lemin. Jew Heck, inti tista saltwarjament jiftħu bibien, imma anki allura dak ma jfisser li jkun każwali? Well, aħna d jkollhom li b'xi mod jifformalizzaw xi jfisser li tibda hawn, imbagħad mur hawn, imbagħad mur hawn. Sean ma kbira, u kien biss gost nara. X'jiġri jekk minflok nagħmlu l-bidla l-problema ftit u żid sal Sean din is-sena, jekk inti se? Would xi ħadd tkun komda ġejjin fuq il-palk u jsolvu problema kemmxejn differenti u li jidhru fuq camera? 

Ejja ħa mmorru lil hinn mill-orkestra għaliex inti guys kienu pjuttost involuti llum diġà. Kif dwar fil roża, fil-kappell? Come fuq l isfel. X'inhu l-isem tiegħek? >> Alex. >> Alex. Okay. Allura Alex se tkun Sean din is-sena u se jidher fil-snin li ġejjin valur ta 'CS50 lectures. Alex, sbieħ li jissodisfaw inti. >> Nizza li jissodisfaw inti wisq. L-isfida fil-idejn għalik huwa li ikollok daqsxejn aktar faċli f'dak jien tghidlek l-istess numri huma hawnhekk, iżda huma issa magħżula. Allura issa għan tiegħek hu li ssib il-numru 7. U fil-fatt, għandna verament jagħmlu dan - it-tip you're ta 'qerq, bħal kompjuter se le, billi tħares lejn dak in-numri kienu mument ilu. Ma 'ġibs dan fil-fatt mhux se jgħinu kollha li ħafna, imma ejja nippretendu li inti ma tafx x'inhu l-array oriġinali. Kulma għandek tkun taf issa huwa li inti għandek firxa ta 'numri magħżula li jista 'jkollhom lakuni bejniethom, u mira tiegħek huwa li jinstabu n-numru 7. Kif inti, bniedem raġonevoli li, imorru jsibu l-għadd 7? 

Mur minn baxxi għal għoljin? Okay. >> Mur baxxi għal għoljin. U ma jitqattax lilhom off. Ejja biss lift up hekk nistgħu jerġgħu jużawhom. Okay, so 1. Stenna. Qabel ma inti żżomm għaddej, li kien 1, kjarament żbaljat. Allura x'inhu għaddej permezz ta 'moħħok li jmiss? X'hemm pass li jmiss tiegħek? Il-li jmiss waħda. Okay. >> Il-li jmiss waħda. Tajba. 3, hekk żbaljata. X'hemm pass li jmiss tiegħek? Żomm għaddejjin. >> Kull dritt. Żomm għaddejjin. 5. Sabiex iżommu għaddejjin, u let me inti idejn dan għal posterità. 7. >>. Eċċellenti Tajjeb ħafna. Misjuba n-numru 7. [Applause] Allura li kienet tajba, imma Sean wisq sabu l numru 7. U jien jargumentaw li int ma verament sfruttati din il-biċċa ta 'informazzjoni addizzjonali, li huwa li dawn in-numri huma magħżula. Allura nistgħu nagħmlu aħjar? Xi suġġerimenti hawn? Yeah, fid-dahar. [Student] search Binarju. >> Għandi l-ebda idea dak li tfittxija binarja hu. 

[Student] Tibda fin-nofs. >> Bidu fin-nofs. Okay. Mela ejja ara jekk nistgħu naslu s'hemm. Mela jekk minflok int told bidu mill-nofs, imorru quddiem u tiftaħ il-bieb tan-nofs. Hemm 8 minnhom, hekk int se jkollhom arbitrarjament jagħżlu l-waħda ftit lejn ix-xellug jew lejn il-lemin. Okay. 7! [Applause] Sbieħ ħafna. Okay, iżda fejn kienu aħna jmorru ma 'dan? Ejja nassumu biss biex jiksru r-rabta li inti kien beda hawn minħabba li ugwalment seta 'ġara ukoll. Aħna biss ġara li tkun taf li 7 kien hemm. Allura dan huwa 13. Mela jekk dawn qed magħżula u aħna kemm bdiet fin-nofs, dak li l-pass li jmiss aħjar ġew? Mur fuq ix-xellug. U hekk hawn jidħol l-eżempju ktieb tat-telefon ġdid. Jekk 13 huwa hawnhekk u nafu l-lista hija magħżula, allura kollha ta 'dawn il-biċċiet tal-karti huma uninteresting lilna issa għaliex aħna diġà jafu li 7 għandu jkun lejn ix-xellug jekk dawn in-numri huma magħżula u sibna 13. 

Allura x'hemm pass li jmiss tiegħek hawn? >> Mur lejn ix-xellug. >> Okay, tajba. Allura jmorru lejn ix-xellug, u - stenna, ħej, ħej, ħej. Li qerq. Allura inti misjuba 7, iżda dak li kien l-algoritmu aħna biss applikati? Ibda fin-nofs. >> Tajba. Allura x'inhu l-estensjoni loġika ta 'dik l-idea istess? Oh, għal ftit dawn. >> Eżattament. >> So I tibda hawn. >> Tajba. Allura issa aħna marru ftit lejn ix-xellug mill-ġdid. Huwa 3. Iżda l-takeaway interessanti issa hija li wieħed do inti ma għandekx għall-kura dwar? Dawn 2. >> Dawn 2. Allura issa dan wieħed jista 'jmur lil hinn, dan wieħed jista' jmur lil hinn. Issa l-problema li kienet ta '8 allura kien 4 Daqs issa huwa daqs 2. Aħna jkollna pretty qrib. Għal darb'oħra, mur l-nofs ta 'dawn l-elementi 2. 

Okay. Allura huwa tip ta 'ħasra li issa aħna qed dejjem se titħalla għaliex aħna qed arrotondament' l isfel. Iżda li l-multa minħabba li issa għandna tarmi dan bogħod u kull ħaġa oħra, jħallu lilna ma 'biss 7. Ejjew nagħtu rawnd ta 'applause. Sibna 7 mill-ġdid. [Applause] Okay. Sure. Tistrieħ fuq għal biss 1 aktar 2. Anki jekk dan it-tip proċess li jmiss ta ħadu ftit itwal minn ħassejna li kieku, franchement, instincts tiegħek l-ewwel kienu l-aħjar, id-dritt? Sibna 7 istantanju. Iżda aħna sabu 7 aktar malajr, l-ebda kwistjoni dak, f'dan l-eżempju kontra dan wieħed għaliex jekk in-numri huma kollha magħżula, ħafna bħall-paġni fil-ktieb tat-telefon, inti tista 'tabilħaqq CHOP nofs il-problema mill-ġdid u għal darb'oħra u għal darb'oħra. U m'humiex daqshekk faċli biex tara dan biss bi 8 numri bħala kuntrarju għal ktieb tat-telefon 1000-paġna fejn inti verament tara dan viżwalment, imma f'dan il-każ hawnhekk meta Sean kien it-tiftix għal 7, kemm passi fil-agħar każ ikun jidher ħadu lilu? >> [Student] 7. 7 fil-agħar każ. Ukoll, fl-agħar każ mhux 7 jekk ikun hemm 8 bibien hawn. Dan kien jieħu lilu 8 passi. 

Mela jekk hemm taċ-bibien n, jista ħadu Sean ftit snin ilu passi n. Issa, fil-każ tiegħek, Alex, peress li dawn in-numri huma magħżula - u nistgħu tip ta 'jiddeduċu dan minn fejn aħna ħadthom ġiet s'issa f'din l-istorja - x'inhu l-ħin tmexxija ta 'l-algoritmu aktar intelliġenti Alex tal-bidu mill-nofs u mbagħad tirrepeti? [Student] 3. >> Allura li għaddej biex tkun 3, bejn wieħed u ieħor, jekk inti tmur 8-4 għal 2 sa 1. Allura 3 passi jew, b'mod aktar ġenerali, li l-log n-ġdid. Kwalunkwe ħin li inti qed tonqos bin-nofs u tnaqqas bin-nofs u tnaqqas bin-nofs u tnaqqas bin-nofs, li l-espressjoni ta 'din l-idea ta' log n. U hekk li kien jieħu inti biss 3 passi, u fil-fatt għamlet ladarba aħna miftuħa l-bibien tnaqqis bin-nofs u tnaqqas bin-nofs, billi dan kien jieħu Sean xi 7 jew 8 passi. Allura nirringrazzjak talli magħna din is-sena. >> Grazzi. Nizza laqgħa inti. Grazzi lil Alex. >> Bl-istess mod. [Applause] 

X'hemm allura l-implikazzjoni reali ta 'dan? Issa immaġina li mhuwiex 8 bibien, li, franchement, lkoll jistgħu jsibu xi ħaġa wara 8 bibien pretty malajr biss billi tiċċarrat-biċċiet tal-karti u jmorru mal instincts tagħna. Imma x'jiġri jekk huwa xi bibien miljun? X'jiġri jekk huwa 4000000000 bibien? Fil-każ ta '4 biljun bibien, int verament se tixtieq li tmur ma algoritmu Alex, l- binarja tfittxija kif aħna ser tibda ssejjaħ dan jew jaqsmu u jirbħu, b'mod aktar ġenerali, fejn inti żżomm tnaqqis bin-nofs u tnaqqas bin-nofs l-problema, għaliex jekk ikollok 4000000000 bibien, kif ħafna drabi tista 'inti CHOP 4 biljun fl-nofs? [Student] 32. >> Huwa fil-fatt 32. Tista 'taħdem dan out fuq biċċa karta jew fir-ras. Inti tmur 4000000000-2000000000 to 1 biljun għal nofs biljun, sa 250 miljun, dot, dot, dot. U jekk inti tagħmel l-matematika, int ser fil-fatt tikseb 32, u li attwalment tirrigwarda xjenza tal-kompjuter għaliex aħna normalment jgħodd poteri ta '2. 2 għall-32 jiġri li jkun ta '4 biljun. Allura hemm ħafna ta 'rilevanza għall-dawn it-tipi ta' poteri ta '2 fix-xjenza tal-kompjuter. 

Imma xi ngħidu dwar 8000000000? Kemm passi huwa li se tieħu jekk ikun hemm 8000000000 bibien? [Student] 33. Allura 33. >> X'jiġri jekk hemm 16000000000 bibien? Kemm passi huwa li se jieħu? [Student] 34. >> 34. Nistgħu tip ta 'jkompli dan nauseam ad. Imma li l-ħaġa qawwija. Inti tista 'tintroduċi biljuni ta' inputs aktar għall-problema tiegħek, iżda, no big deal, inti biss tieħu 1 gidma addizzjonali minnha u b'hekk tagħtina xi ħaġa bħal tfittxija binarja jew jaqsmu u jirbħu, b'mod aktar ġenerali. Imma jien tip ta 'qerq hawn, id-dritt? Fil-każ ta 'algoritmu Alex, hija kellha l-vantaġġ fuq Sean. Kienet taf li dawn in-numri ġew magħżula, iżda Alex ma għandekx sort lilhom lilha nfisha. I bil-quddiem waslet sa l-blackboard u tip ta 'għamel żgur li I ġibdet minnhom kollha barra sabiex magħżul, imbagħad I koperti minnhom bil-karta. Imma kemm ix-xogħol ma dik jieħdu me? Jekk kellna bdew ma 'dawn in-numri f'xi ordni apparentement każwali - f'dan il-każ dawn in-numri sempliċi, 1 sa 8 hawn - kif do we go dwar l-għażla dawn il-valuri? Jekk inti kienu bniedem minħabba dan il-kompitu, liema tip ta 'approċċ intuwittivi se tieħu li issortjar mazz sħiħ ta 'numri? Dawn l-affarijiet kienu stabbiliti bħala biċċiet puzzle. Yeah. 

[Student] nerfa kull numru u jqabbilha għal kull wieħed u jibqgħu għaddejjin lejn ix-xellug. >> Okay, tajba. Sabiex jieħdu kull numru, din titqabbel ma 'dik li jmiss lilha, u mbagħad biss iżommu jimxu tul il-lista, tip ta 'rejiggering affarijiet kif tmur. Allura hawnhekk għandna ċans għal forsi ftit aktar folks biex jinvolvu ruħhom. Do għandna 8 voluntiera aktar li imħabba li toħroġ? Pressjoni ftit inqas peress li int mhux l-uniku wieħed. 1, 2, 3, 4, 5, 6, 7, 8. Come fuq l isfel. You guys huma ser ikunu n-numri 1 sa 8. Ejja naraw jekk aħna ma tistax tagħmel dan issortjar għall Alex ħafna bl-istess mod I ma kien qabel. 1, 2, 3, 4. Jimxi 'l quddiem u jekk inti, linja up fuq il-palk bejn l-istand tal-mużika u lili hawn fl-istess ordni bħall-slide fuq l-iskrin. Uh oh-. Aħna ser naħdmu inti fis-eżempju li jmiss. Oh, stenna, stenna. Here we go. Stenna. L-eżempju li jmiss huwa issa. Hawnhekk inti tmur. Numru 8. Come fuq up. Kull dritt. Sort yourselves skond dan. Żerżaq biss ftit għall-ġenb tal-mużika stand hawn. Allura aħna għandna 4, 2, 6 - tikseb fil hemm, minn hawn, hemm dritt - 3. Yeah. Okay. Inti tmur minn hawn. Le, inti toqgħod hemm. Yeah, hemm dritt. No jien żbaljat. Dritt hemmhekk. Okay, tajba ħafna. Okay. Allura issa ejja sort lilhom fl-ordni dejjem tiżdied. 

Kif nista tmur dwar kif isir dan? L-algoritmu li kien ġie propost mument ilu kien għaliex ma aħna biss iqabbel l-folks li huma tip ta 'ħdejn xulxin u mbagħad tiffissa kwalunkwe żbalji, jiċċaqalqu mix-xellug għal-lemin. Allura hawnhekk għandna 4 u 2, ovvjament out of order. Ejja tpartit inti. Okay. Allura issa jien ser jimxu l-linja. 4 u 6, Nope. [Daħk] 6 u 8, pjuttost tajba. 8 u 1, let me tpartit inti guys. Kull dritt. Allura 8 u 3, tpartit inti guys. 8 u 7, let me tpartit inti guys. 5 u 8, eċċellenti. I jagħtuk lista magħżula. Kull dritt. Allura ma pjuttost. Iżda huwa aħjar għax in-numri akbar - każ fil-punt 8 - jkunu tip ta 'effervexxentement up mill-xellug għal fuq il-lemin. Allura sirt 1 minnhom id-dritt, iżda jħoss bħal dan ma pjuttost issolvi l-problema. 

Allura dak li tipproponi nagħmlu jmiss? >> [Student] Żomm tagħmel dan. >> Aħna tkompli tagħmel dan. U realizzata, għal darb'oħra, aħna waqqafna affarijiet up bi ftit jkollhom l-bnedmin tip ta 'intelliġenti jirranġaw stess ibbażati fuq dak stampa, iżda issa għandna li jkunu ferm iktar metodiku. Aħna rridu nkunu algorithmic dwar dan bħallikieku aħna qed miktub kodiċi - f'dan il-każ pseudocode verbali. So let me biss jippruvaw li għal darb'oħra. Dan ħadmet pjuttost tajjeb. Hija ma issolviha. Iżda meta dubju, biss jippruvaw u erġa 'pprova. Allura 2 u 4, ma jgħinu aktar. 4 u 6. Ah! 6 u 1, ftit aħjar issa. 6 u 3, tajba. 6 u 7, 7 u 5, 7 u 8, tajba. U inti taf, I tista 'probabbilment jinjora 8 issa għaliex huwa fl-aħħar tal-lista. Forsi aħna ma jkollhomx għalfejn tinkwieta dwar xi ħadd li jmorru passat lilu. Imma ejja ara jekk thats suppożizzjoni sikuri. Issa lista hija - kkritikat - mhux magħżula. Ejja nippruvaw dan mill-ġdid. Allura 2 u 4, 4 u 1, 4 u 3. 4 u 6, tajba. 6 u 5, tajba. 6, 7, u 8, tajba. Iżda l-avviż, nista 'biss tieqaf hawn u issa tieqaf hawn issa? [Student] Iva. >> Yeah? X'jiġri jekk wieħed minnkom kien in-numru 9 it-triq kollha hemmhekk? Ikun kienu ġew magħżula. >> Tajba. Ikun kienu ġew magħżula l-ewwel darba madwar. Tajba. Mela ejja jmorru lura mill-ġdid. Aħna kważi hemm. 1 u 2, 2 u 3, 3 u 4, 4 u 5, 5 u 6, 6 u 7, 7 u 8. 

I am isir issa, iżda, għal darb'oħra, jien kompjuter li tista 'biss tagħmel dak li jien qal li tagħmel, u rikollizzjoni biss tiegħi issa hija li I attwalment biss għamlet daqsxejn ta 'xogħol. Xi ħaġa inbidlet hawn. So I ma teknikament ikkonfermat viżwalment jew algorithmically li din il-lista hija tabilħaqq magħżula. Hekk biss għal miżura tajba, biss li jkun anali dwar dan, ejja tagħmel dan iż-żmien 1 aktar. Allura 1 u 2, 2 u 3, 3 u 4. U inti taf liema? Just għal miżura tajba, jien ser iżommu kont fuq naħa tiegħi din id-darba kemm swaps nagħmel biss hekk li jien naf kemm ix-xogħol stajt attwalment isir. 3 u 4, 4 u 5, 5 u 6, 6 u 7, 7 u 8. Ebda swaps. Allura issa nixtieq leġittimament tkun idjota biex jagħmlu dan mill-ġdid għaliex jekk I ma ebda xogħol permezz ta 'dan pass tal-bnedmin, allura b'mod ċar li għaddej biex jerġa 'jiġri jekk l-ebda wieħed minnhom huwa tip ta saltwarjament kontradittorju li jiċċaqalqu minnhom infushom madwar. Allura issa I tista 'twaqqaf. Issa ejja titlob il-kwistjoni, kemm ix-xogħol ma 'dan fil-fatt tieħu me? Kemm passi ma din tieħu? >> N kwadru. Yeah, hekk n kwadru. Fejn tista 'tikseb n kwadrat minn? Int għandek tiċċekkja kull num - Hemm n-numri, u inti għandek tiċċekkja kull numru man-numri n-oħra. Tajba. >> Allura huwa n kwadru. >> Tajba. 

Allura jħoss simili jista 'jkun tajjeb ħafna n kwadrat, id-dritt? M'hemm l-n 'dawn guys, 8 speċifikament f'dan il-każ, imma kull darba I marru permezz ta din il-lista I kien li jqabbel l-ewwel persuna kontra t-tieni, it-tieni kontra l-3 ġdid u għal darb'oħra u għal darb'oħra, u meta sirt l-aħħar, dak li ma nagħmel? I redid dan. Allura jekk aħna tiġġeneralizza din l-ispjegazzjoni, aħna għandna n-nies u jien jagħmlu, ovvjament, 8 passi, n passi, kull darba mmur permezz ta 'dan algoritmu. Imma kif ħafna drabi fil-agħar każ għandi jkollhom jgħaddu din il-lista ta 'nies? [Student] N darbiet. >> Probabbilment n, id-dritt, minħabba li fl-agħar każ, x'hemm probabbilment l-arranġament tal-agħar każ ta 'dawn guys mill-get-go? Jekk dawn qed kompletament maqluba ordni minħabba biss jissoponi mentalment, let's - X'hemm isem tiegħek? >> Bowen. Bowen. Okay. Allura Bowen, come fuq matul hawn għal ftit mument. 

Ejja ngħidu li Bowen kien hawn fil-bidu ta 'l-algoritmu, u ma nafux dak li kulħadd huwa, iżda Bowen hawnhekk, skond din algoritmu - u jekk inti tixtieq li biss stroll miegħi - se bużżieqa up, kif għamel l-ewwel darba madwar, it-triq kollha sa l-aħħar. Iżda jissoponi li l-persuna li jmiss għall Bowen kien in-numru 7. I ikollhom imorru lura u tikseb numru 7, li jfisser I ikollhom imorru-triq kollha lura hawn. Issa I għandhom ikollhom l-istess stroll mal-persuna li tkun numru 7. Imma x'jiġri jekk mbagħad numru 6 kien li jmiss lilu kif ukoll? Imbagħad I għandhom imorru lura u nikseb 6. Għalhekk għal darb'oħra, fuq kull iterazzjoni ta 'dan loop jien tkellem lil kull wieħed mill-poplu n, u I jista 'jkollhom biex jagħmlu n' dawn strolls biex tiżgura jien ġbid l-elementi kollha akbar lura u lura u lura lill-aħħar nett tal-lista. Affarijiet Allura n n darbiet huwa biss darba n n n kwadru jew. 

Allura hawnhekk diġà għandna algoritmu li m'għadux n, li m'għadhiex log n, huwa attwalment agħar minn kull ħaġa li aħna ghamilt qabel. Allura tip Alex tas ltqajna xxurtjati li għamilt kollha tal-ħidma apparentement bil-quddiem għall tagħha, kollha tax-xogħol għoljin, b'tali mod li hi tista 'tgawdi f'dan algoritmu tfittxija binarja, li huwa log ta 'n. Iżda dan huwa konsistenti ma 'tema nhar it-Tnejn. Aħna taw ftit spazju aktar, aħna użati bits aktar, sabiex iħaffu l-running time tagħna. Tant simili hemm dan kompromess bejn żmien u spazju, hemm jista 'wkoll jkun biss kompromessi bejn il-ħin mgħoddi up tip quddiem jkollna affarijiet lesta li tmur u fil-fatt eżekuzzjoni algoritmu simili tfittxija. Ejja nippruvaw ieħor. Jekk inti guys ma mind biss malajr titranġa infuskom biex jaqblu li għal darb'oħra, ejja tipprova xi ħaġa xi ftit differenti fejn mhuwiex daqshekk sempliċi kif biss tiffissa l-iżbalji pairwise, li huwa super intuwittivi. Ejja minflok jkun ftit aktar deliberata u jagħmlu dan. Dan wieħed wisq nipproponi li huwa probabbilment pjuttost intuwittivi. 

Ejja agħżel il-persuna iżgħar mil-lista mill-ġdid u għal darb'oħra. Allura here we go. 4, inti l-persuna iżgħar stajt b'hekk qatt dehret sallum, hekk jien ser mentalment jiftakar li bi ftit tipponta lejn inti għal issa. 2. Ooh! Tinsieh numru 4. I biss sabu l-element ġdid iżgħar f'din il-lista. Jien ser tip ta 'ftakar li. 6, 8. Ooh! 1. Goodbye. Allura issa jien se tiftakar numru 1. Aħna nafu li 1 huwa l-iżgħar, imma jien l-kompjuter. X'jiġri jekk hemm 0? X'jiġri jekk hemm -1? Għandi biex jibqgħu għaddejjin. Allura 3, 7, 5, Nope. Okay. Allura numru 1 kien l-iżgħar. Let me tagħżel int mil-lista - we'll go dan il-mod - u tpoġġi lilek arbitrarju fil-bidu tal-lista. Issa, stenna minuta. I tip ta 'misruqin. Jekk dawn guys jirrappreżentaw mhux lista ta '8 persuni, iżda firxa, 8 biċċiet ta 'memorja kontigwu - do you mind pass lura għal ftit mument? Hemm fil-fatt ebda spazju għal dritt inti hawn. Allura kif nistgħu tagħmel spazju għall - x'hemm isem tiegħek? >> Sammy. >> Sammy. Kif nistgħu tagħmel spazju għal Sammy? 

Nimxu 'l-n li huma qabel lili. Okay. >> Allura nistgħu jimxu l-persuni li huma n quddiemu, hekk jekk inti guys tixtieq li tieħu 1 deliberat, pass drammatika lejn ix-xellug. Huma kollha ma li jopponu ghal, imma aħħar darba I kiteb xi kodiċi, inti ma tistax issolvi tat jiċċaqalqu ħafna affarijiet kollha f'daqqa. Nistgħu nagħmlu dan fil-linja, li jiċċaqalqu kulħadd darba fi żmien. Mela jekk inti guys ma mind pass lura lejn il-lemin, u Sammy, jekk inti tista 'pass lura għaliex hemm għadu ebda kamra ghalik, issa ejja tagħmel dan. Fejn kien Sammy mument ilu? Dritt hemmhekk. Allura hemm lakuna hemmhekk. Allura inti tista 'timxi lejn post Sammy s. Issa persuna li jmiss up u issa persuna li jmiss, issa persuna li jmiss. Issa għandna kamra għal Sammy. Issa, xi ħadd mill-udjenza - li kienet tajba, li kienet korretta, li ħass ftit ħin - x'hemm aktar mgħaġġel? Yeah. [Student] A firxa ġdida? >> X'hemm li? >> [Student] A firxa ġdida? >> Okay, tajba. 

Allura konsistenti ma 'din it-tema ta' ftit kompromessi, għaliex ma I biss tagħmel firxa ġdida  u mbagħad Sammy se jkun għawm fl-ispazju quddiem ta 'dawn in-nies, per eżempju, u nistgħu biss tibda timla firxa ġdida għal kollox. Li wisq tkun taħdem. Imma jien ma interessati fl-infiq aktar spazju illum. X'hemm approċċ ieħor? [Student] Swap. Okay. >> Aħna jista 'biss tpartit dawn guys 2. X'hemm isem tiegħek? Mario. >> Mario. Allura Mario, inti kienu attwalment hawn. Sammy, inti tista 'back up għal ftit mument? Mario kien hawn. Aħna ma jkollhomx spazju għalik aktar, hekk jekk inti ma mind se fejn Sammy hija, aħna ser tpoġġi Sammy hawn, u issa I d jargumentaw li l-operazzjoni iskambji Sammy kien ħafna aktar mgħaġġla. Għamilna 1 tħaddim li tpartit dawn guys, jew forsi 2 li tpartit dawn guys, imma aħna ma tagħmel 1, 2, 3, 4, b'tali mod li jħoss aħjar. Issa, stenna minuta. I tip ta 'għamel l-problema agħar minħabba numru 4 kien tip ta' qrib il-bidu. Issa numru 4 huwa xi ftit aktar mill-qrib għal dan il-għan, imma jien ma verament jafu jew kura dwar dan. Allura dan huwa biss xortih ħażina li numru 4 huwa ftit aktar 'l bogħod mill-post destinat tagħha. Mela ejja issa irrepeti dan algoritmu. 

Biex terġa, sakemm li l-istorja kienet, kollox aħna ma kien walk permezz tal-lista tfittex l-persuna iżgħar nnumerati. Allura issa ejja jagħmlu mill-ġdid. Aħna ma jkollhomx għalfejn tinkwieta dwar Sammy aktar. Nistgħu biss jmorru hawn. Ooh! Numru 2. Li numru pjuttost żgħir. 6, 8, 4, 3, 7, 5. Okay, tajba. U Thankfully, b'kumbinazzjoni, jien ma jkollhom jimxu - >> Willie. Willie għaliex huwa fil-post dritt tiegħu issa. Ejja nagħmlu dan mill-ġdid u jinjora dawn guys 2. 6. Li numru pjuttost żgħir. Ooh! 8 hija definittivament akbar. 4. Ejja niffukaw fuq 4. Ooh! 3 huwa anki aħjar. 7 u 5. Allura dak li nagħmlu issa ma '- >> Roger. >> Roger? Ejja tpartit lilu bin-numru 6. Mela jekk 6 u 3 tixtieq li tpartit, konna issa tip ta gotten xxurtjati li 6 huwa eqreb lejn fejn hija għandha tkun, imma huwa biss koinċidenza hawn. Mela ejja issa mur hawn. 8 huwa numru pjuttost żgħir. Ooh! 4 huwa iżgħar. 6, 7, 5. What do we issa do? Swap. >> >> Eżattament. Allura issa ejja tagħmel dan it-tip ta mgħaġġel. 8, 6, 7, 5. Fejn ma 5 imorru? Tajba. Okay. 6, 7, 8. 6 gets li tissospendi fejn hi. X'hemm isem tiegħek? >> Rosalie. Rosalie gets li tissospendi fejn hi. 7 gets - Ejja naraw. 7, 8. Okay. Allura 7 gets li tissospendi fejn hi. X'hemm isem tiegħek? >> Amna. >> Amna. 

Allura Amna gets li tissospendi fejn hi, u numru 8 huwa diġà fejn issa għandu jkun. Okay, tajba. Iħoss simili aħna qed biss joħolqu x-xogħol għalina hawnhekk, għalkemm. X'hemm finalment l-running time ta 'dan algoritmu? Jekk naħsbu dwar dawn in-nies mhux bħala 8, iżda bħala n? >> Huwa n. Huwa n-passi, imma aħna qed tkun eżaminata kull wieħed ħin. Okay. N imma int iċċekkjar kull wieħed ħin? Okay, iżda jekk huwa n-passi, m'għandux I kienu kapaċi biex issolvi lilek minn biss jmorru 1, 2, 3, 4? Oh! Okay, li differenza kbira. Allura n kwadrat għaliex? X'qed verament jiġri? Hemm nies n f'din il-lista, iżda jsibu l-persuna iżgħar fil-lista fl-agħar każ, kemm passi għandi tieħu? >> N. 

N, id-dritt, minħabba li fl-agħar każ, in-numru 1 huwa it-triq kollha hemmhekk, so I ikollhom imorru nikseb lilu jew lilha. U mbagħad meta I finalment realizzata 1 kien l-iżgħar, allura huwa pjuttost malajr biex tpartit lilhom. Imma issa I għandhom jibdew mill-bidu u jfittxu għal min? Il-persuna li jmiss iżgħar, li huwa 2. Meta fil-każ agħar huwa 2? Oh, Alla tiegħi. Huwa it-triq kollha hawn fuq fl-aħħar. Allura issa stajt biss isir ieħor passi n, ieħor passi n. U jekk konna ltqajna nies n u fl-agħar każ il-persuna iżgħar hija n-passi bogħod, li l-jerġa n-ħinijiet n, u hekk aħna darb'oħra għandna n kwadru. Dan ma tħossok daqshekk tajjeb. U fil-fatt, anki fil-każ aħjar - jissoponi li dawn jibdew off magħżula - kemm passi ma jieħdu għalija li jużaw dan algoritmu biex issolvi dawn in-nies n? N kwadrat. >> Smajt n kwadru. Għaliex n kwadrat? Għaliex inti xorta għandek tiċċekkja kull wieħed ħin. >> Yeah. U inti għandek tpartit lilhom. >> Anki jekk aħna bnedmin huma tip ta 'omniscient fis-sens viżwalment li nistgħu biss tip ta 'tara li dan huwa magħżul, kompjuter ma tkunx dik intelliġenti. Huwa ser tfittex hawn u hawn u hawn, imma jekk dak huwa tfittex huwa l-element iżgħar, inti biss taf li inti tinstab l-element iżgħar minn dak il-punt? Ladarba int fl-aħħar. Iżda f'dak il-punt inti stajt biss sabu l-element bħalissa iżgħar. Inti ma neċessarjament jaf xi ħaġa oħra dwar l-istat tad-dinja. Allura inti għandek tmur għal darb'oħra u għal darb'oħra u għal darb'oħra. 

Allura dan iż-żmien I really do ħarsa mutu għaliex jien iċċekkjar, okay, 2, int l-iżgħar, imma jien ma nafx li b'kollox s'issa. 3, 4, 5, 6, 7, 8. Okay, tajba. 2 kien tabilħaqq l-iżgħar. Issa ejja ssib il-iżgħar li jmiss. Okay. 3, int bħalissa l-iżgħar. Ejja naraw. 4, 5, 6, 7, 8. Okay, ltqajna xxurtjati għal darb'oħra. 3 kien tabilħaqq fil-post it-tajjeb. Imma jien ser iżommu tagħmel dan mill-ġdid u għal darb'oħra u għal darb'oħra. Kif nistgħu nagħmlu dejjem hekk ftit aħjar? Minflok ma jkollhom nies bużżieqa up pairwise minn iżgħar sa l-akbar u minflok tmur quddiem u lura permezz tal-lista għażla tal-persuna imbagħad iżgħar, għaliex ma we minflok daħħal dawn in-nies fi stadju lista ġdida mill-pass? Ejja nippruvaw dan. Issa let me sejħa dan it-tip inserzjoni ħaġa. Allura aħna qegħdin hawn hawn. Numru 1. I do not care about ħaddieħor f'din il-lista. L-għan tiegħi dritt issa huwa li tpoġġi numru 1 fil-bidu ta 'lista magħżula. U jien ser nipproponi peress li jien biss jkollhom 8 biċċiet ta 'memorja, arbitrarjament dritt issa I am il-ħajt bejn lista allegatament mhux magħżul tiegħi, u kulmin huwa lura lili jien ser jitolbu huwa magħżul. Allura issa għandna numru 1. Irrid li daħħal lilu fis lista magħżula tiegħi, hekk jien biss se jimxu ħajt tiegħi hawn fuq, u issa I jitolbu din il-lista huwa magħżul, din il-lista mhux magħżul - mill-inqas safejn naf. Ma nistax nara il-numri f'daqqa. 

Issa I jiġri li jiltaqgħu numru 2. What do I do miegħu? I daħħal inti issa fil-lista magħżula. Imma avviż kif faċli li kien. I biss għandek tfittex. Numru 1 hemm. Oh, ovvjament 2 tmur għall-naħa ta 'numru 1. Issa x'għandi nagħmel bi 3? I daħħal inti fil-lista magħżula. Iżda dan kien super faċli. Dan huwa super faċli, dan huwa super faċli, dan huwa super, super faċli faċli, faċli super. U issa kollox huwa magħżul lura lili, u kemm passi ma din tieħu? [Studenti] N. >> Allura huwa biss n. Aħna ltqajna xxurtjati. Kien biss n għaliex? >> [Student] Minħabba li l-lista ġiet magħżula. Il-lista hija diġà magħżula. Allura aħna ltqajna xxurtjati. Iżda aħna iddisinjat algoritmu dan iż-żmien li ċineg li tip ta 'xortih, li aħjar xenarju, billi ma ħela ta 'ħin bla bżonn. Allura issa għandna dak li aħna ser sejħa xorta bużżieqa fejn in-nies tip ta 'bużżieqa up pairwise. Issa għandna tip ta 'għażla fejn aħna ġewwieni l-persuna iżgħar u għal darb'oħra. U issa għandna tip inserzjoni fejn aħna xorta ta proattiv jpoġġi ż fejn huma jappartjenu f'lista dejjem magħżula. Jekk nistgħu, rawnd ta 'applause għal dawn guys hawn. [Applause] Ejja tieħu 5-minuta break tagħna hawn. U meta niġu lura, aħna se blow kollha ta 'dawn algoritmi barra mill-ilma ma 'xi ħaġa aħjar. Kull dritt. Grazzi ħafna. Tista 'żżomm dawk kif souvenirs. Kull dritt. Aħna lura. 

U biex terġa fast reali, kellna dawn l-approċċi differenti għall-għażla 3, il-punt kollu tagħha kien li jasal sal-punt fejn xi ħadd bħal Alex tista 'tfittex lista ta' numri aktar malajr milli xi ħadd bħal Sean jistgħu. U anki jekk aħna għandna eżempji sempliċi bħal ma 8 numri, inti tista 'faċilment tiġi estrapolata għal 8 paġni web, paġni tal-web 8000000000, jew 800000000 ħbieb fuq Facebook. Allura dawn algoritmi jistgħu ċertament iskala għal dawk it-tipi ta 'valuri, u l-ideat huma finalment l-istess. Sort bużżieqa Allura kien l-ewwel fejn aħna tip ta 'effervexxentement-persuna akbar it-triq kollha lejn il-lemin billi jiġu skambjati nies pairwise. Imbagħad kellna dak li aħna ser sejħa xorta għażla fejn I ftit aktar deliberatament tinżamm tfittex permezz tal-lista, l-għażla l-iżgħar numru ġdid u għal darb'oħra u għal darb'oħra, ir-riżultat loġiku tagħha huwa li l-lista eventwalment magħżula. Imbagħad fit-tielet waħda, I jiddaħħal in-nies fil-post xieraq tagħhom, u għamilna eżempju ħafna artifiċjali f'dik il-lista kienet diġà magħżula, iżda li kien jibgħat il-messaġġ li fil-każ tip inserzjoni, il- inti tista 'tikseb xorti. Jekk in-numri huma diġà magħżula, huwa biss se tieħu inti n passi biex tikkonferma kemm, billi sort għażla int viżjoni mina ftit aktar u inti qatt ma jirrealizzaw li l-lista hija diġà magħżula. Mela ejja ara sort bużżieqa fl-azzjoni hawn. Fl-eżempju li ġej, aħna qed madwar biex tara bars vertikali għoli li jirrappreżentaw numri sabiex inkunu nistgħu sort ta Ħares issortjar jiġri. L-iżgħar il-bar, l-iżgħar in-numru; l-akbar il-bar, l-akbar l-għadd. 

U aħna ser joqogħdu fuq din il-veloċità default. Huwa ser jimxu malajr ftit għal issa, imma aħmar huwa dak li juri 2 bars jiġu mqabbla ġenb ma 'ġenb. U jekk inti watch mill-qrib, dak li jiġri huwa li jekk il-vireg huma out of order, l-iżgħar wieħed gets jiċċaqalqu lejn ix-xellug, il-wieħed akbar lejn il-lemin, u allura inti żżomm avvanz. Allura jekk nagħmlu dan għal darb'oħra u għal darb'oħra, l-avviż li l-vireg iżgħar huma se jżommu inching triqthom lejn ix-xellug u l-vireg akbar huma ser iżommu inching triqthom lejn il-lemin. U fil-fatt, aħna qed jibdew biex tara mudell-triq kollha fuq in-naħa tal-lemin bħad rajna 8 u mbagħad eventwalment 7 tbaqbieq sa l-aħħar ħafna tal-lista tal-bniedem tagħna. Allura dan se malajr ħafna tikseb daqsxejn tedious, so let me twaqqaf dan għal mument. Let me jibdlu l-veloċità li jkunu ferm aktar mgħaġġla. Jien ma jinbidlu l-algoritmu, jien biss tagħmel l-animazzjoni iseħħ aktar malajr. Still bużżieqa tip, algoritmu istess, imma issa tista 'tara ħafna aktar mgħaġġla minn dimostrazzjoni verbali tagħna li l-elementi akbar huma tabilħaqq tbaqbieq sal-quċċata. 

Bħala twarrib, dawn kwadri ftit fil-qiegħ tax-xellug u l-qiegħ dritt huma biss ftit noti ta 'tfakkir dwar kif ħafna paraguni li qed isir. Iżda għal issa, nistgħu niffukaw fuq il-piramida li l-tieħu forma, u hemm din tmur. L-element iżgħar hija fuq ix-xellug, l-akbar fuq il-lemin u kull ħaġa oħra bejniethom. Issa ejja minflok tagħti ħarsa lejn it-tip ta 'għażla. Jien ser jimxi 'l quddiem u hit Stop. Aħna ser tikseb sett każwali ġdid ta 'bars. Sort Għażla, irtirar, tmur permezz tal-lista mill-ġdid u għal darb'oħra u għal darb'oħra, tnittif l-element iżgħar. Allura hawnhekk huwa tip ta 'għażla. Jidher qisu hemm ħidma anqas jiġri issa għaliex aħna mhux qed jitqabblu pairwise imma aħna qed biss tip ta 'cherry picking l-elementi iżgħar minn lemin għax-xellug. Dan ħa ftit żmien, hekk hemm dikotomija diġà. Sempliċiment għax algoritmu huwa qal li jieħdu n ħin kwadrat, bħall-tip bużżieqa u bħall sort għażla, dawn huma verament ħinijiet agħar każ running. Per eżempju, fil-każ ta ', ejja ngħidu, sort għażla, I attwalment am għażla tal-persuna iżgħar u t-tqegħid lilu jew lilha hawn, allura jien tagħmel dan mill-ġdid, imbagħad jien tagħmel dan mill-ġdid, iżda kien hemm ottimizzazzjoni żgħira I tista 'tagħmel. 

Hekk kif mort numru 1 hawn - Sammy f'dak il-każ - dak li għamlet I bżonn tagħmel miegħu wara? >> [Student] Leave lilu. Leave lilu, id-dritt? Xejn. I ma kellhomx bżonn li qatt jitkellem Sammy darb'oħra għaliex jekk kelli għażlet l-element iżgħar u jniżżlu hawn, għaliex iż-żmien l-iskart sejjer sa l-aħħar tal-lista sħiħa tiegħi? Fuq il-iterazzjoni li jmiss let me attwalment jimxu biss numru 2, biss għal numru 3. Allura fir-realtà, I ma kienx qed jagħmlu affarijiet n n darbiet. I kienet tagħmel affarijiet n, allura n - 1 affarijiet, allura n - 2 affarijiet, allura n - 3 affarijiet, allura n - 4, dot, dot, dot. Għandna daqsxejn ta 'serje ġeometrika, li sempliċiment ifisser int żżid up numri progressivament iżgħar. Mhux n + n + n + n, iżda n + 7 + 6 + 5 + 4 + 3 + 2 + 1. U dak li ġeneralment taħdem biex ikun - Jien ser mess up bord tiegħi hawn għal ftit mument - li għaddej biex jaħdmu biex tkun xi ħaġa bħal n (n - 1) / 2 jekk aħna biss tip ta 'ħarsa fuq wara ta' ktieb matematika fejn inti għandek l-folji iqarrqu għall-formuli. Jekk int sempliċement tiżdied xi ħaġa n + n - 1 + n - 2, hija taħdem biex tkun xi ħaġa bħal din. U jekk aħna biss tip ta 'immoltiplika dan out, li l-n kwadrat minus n / 2. I tinżamm qal n kwadrat, għalkemm, u dan għaliex I kien tip ta 'teħid ta' shortcut mentali għaliex fir-realtà, n kwadrat nieqes n diviż bi 2 huwa tabilħaqq in-numru reali ta 'passi li algoritmu bħal tip ta 'għażla se jieħu jekk aħna verament magħduda kollha ta 'dawk il-paraguni u kollha tal-ħidma busy ftit aħna kienu qed jagħmlu. Iżda franchement, ladarba n gets li jkun bħal miljun jew biljun, li l-Heck cares jekk inti qed tagħmel xi biljun nieqes kwadru ta 'biljun diviż bi 2? A biljun kwadru huwa numru kbir. Tista 'tieħu ieħor biljun off ta' dan ma '- n. Mhuwiex tali big deal. Allura l-akbar in-numri jiksbu, l-inqas importanti dawn it-termini ordnati aktar baxxi huma. Who cares jekk inti iddividi 2 jekk inti qed jitkellem dwar quadrillions ta 'numri ta' passi? 

Għalhekk, b'mod ġenerali, xjenzjati tal-kompjuter tendenza li tarmi kollox iżda t-terminu akbar, u aħna biss tip ta 'jissimplifika-dinja u jgħidu li din algorithm ħadet passi madwar n kwadru. Dik hija l-running time ta 'algoriżmu. Allura aħna ser terga 'lura għal din fi ftit mument ma' xi eżempji konkreti, iżda għal issa, dak it-tip ta 'l-motivazzjoni intuwittivi wara biss jissimplifika dinja tagħna u jitkellem dwar it-termini l-aktar importanti, aktar milli jkollna fis kollha dawn il-formuli fancy. Allura li kien tip ta 'għażla, u aħna ltqajna ftit xxurtjati hemmhekk. Ejja nħarsu lejn tip inserzjoni. Let me imorru quddiem u tibda dan wieħed ukoll. Issa avviż il-mudell li qed jiġri huwa xi ftit differenti, u bdejna bil numri bl-addoċċ, imma jekk aħna effettivament jgħoddu l-għadd ta 'passi fl-agħar każ, jekk il-lista bdiet kompletament fl-ordni dritt, aħna biss jieħdu passi n li tirrealizza kemm. 

Iżda jekk il-lista kienu attwalment lura - per eżempju, f'dan il-każ hawnhekk - allura avviż aħna fil-fatt ikollhom jagħmlu xogħol ħafna aktar f'dan il-każ. U għandu tip ta 'jħossu li inti bħal dan wieħed huwa tip ta' xogħol aktar diffiċli biex tikseb dawk l-elementi iżgħar lejn ix-xellug, u dan għaliex aħna ltqajna unlucky. Il-lista ġiet magħżula aċċidentalment fir-reverse. B'kuntrast, ma sort inserzjoni jekk irridu jimitaw dak li għamilna mal-bnedmin tagħna hawnhekk mill-bidu ma 'kulħadd magħżul u mbagħad tibda, huwa algoritmu pjuttost tajba, id-dritt? Huwa diġà, fil-fatt, magħżula. Mela ejja jippruvaw li jitqassar eżattament kemm ħin dawn l-affarijiet qed jieħdu magħna bl-introduzzjoni biss daqsxejn ta 'lingwaġġ jew notazzjoni li l-fatt ferm aktar sempliċi mill-tip fanciness ta jissuġġerixxi. Din ħaġa hawn, dan O kbir fuq l-iskrin, huwa dak xjenzat kompjuter se ġeneralment jużaw biex jiddeskrivi l-ħin agħar każ tmexxija ta 'algoriżmu. 

Għal darb'oħra, billi l-agħar każ, huwa totalment dipendenti mill-kuntest. Dak li jfisser mill-agħar każ totalment tvarja bbażati fuq il-problema li aħna qed jitkellem dwar. Iżda fil-każ ta 'għażla, x'inhu l-agħar xenarju possibbli? Kollox huwa lura għax hija biss iħoss bħal dan ifisser ħafna xogħol għalina. Stajt jotted xi ftit mill-algoritmi li aħna stajt tidher s'issa: Tfittxija lineari, tfittxija binarja bħall mal-ktieb tat-telefon jew il-biċċiet tal-karti, sort sort bużżieqa, sort għażla, u l-inserzjoni mbagħad simili rajna mal-bnedmin tagħna, u mbagħad 1 ohra li l-eventwalment se jissejjaħ jingħaqdu tip. Għalhekk fl-tfittxija lineari fl-agħar każ, kemm passi ma jieħdu biex isibu l-numru 7 jekk ikun hemm bibien n bħall Sean ffaċċjati? >> [Student] N. N. Allura aħna qed tmur biex jiktbu big O ta 'n. Jien biss ser timla xi vojt. Dan huwa biss grilja ta 'matriċi. Iżda fil-każ aħjar ma 'tfittxija lineari, 7 seta' kien fil-bidu nett tal-lista, u Sean jista bdew ifittxu fil-bidu tal-lista. Mela jekk inti qed tuża tfittxija lineari u biss verifika xellug għal-lemin jew forsi lemin għax-xellug - dawn qed ekwivalenti - fil-każ aqwa kif ħafna passi tista 'tfittxija lineari, bħal algoritmu Sean, tieħu? Just 1 pass. 

Allura jien se ngħid li l-notazzjoni omega. Dan huwa biss omega kapital. Omega huwa biss il-mod ta 'tgħid sexy każ l-aħjar running time. Allura fil-każ aħjar il-running time huwa pass wieħed jew numru kostanti ta 'passi - 1 f'dan il-każ - imma fl-agħar każ, big O, huwa attwalment passi n. U dan wieħed hawn, theta, aħna qed attwalment mhux se tħares lejn id-dritt issa. Mhuwiex rilevanti għal dan l-eżempju partikolari. Imma issa ejja ipprova tiftix binarju. Fl-agħar każ ma 'tfittxija binarju, kemm passi huwa se jieħu biex issib in-numru 7 jew kwalunkwe aħna qed tfittex? >> [Student] Log n. Still ser tieħu n log għaliex eżatt bħal Alex ltqajna unlucky meta aħna verament maħduma permezz tal-problema metodiku u hi ma sabx il-numru 7 sakemm il-bieb ħafna aħħar hi ħares lejn, anki jekk, fil-ġustizzja, qabbdet biex armih bibien ċerti tul it-triq, tfittxija binarju fl-agħar każ għandu ħin tmexxija ta 'log n. U għal darb'oħra, li titkellem għal dan diviżjoni u conquering. Imma xi ngħidu dwar fil-każ aħjar? U Alex attwalment esperjenza f'dak il-każ l-aħjar dritt meta hi daħlet up fuq il-palk. Kemm passi ma din tieħu fit-tfittxija binarja? >> [Student] 1. 1, sempliċiment għaliex hija ltqajna xxurtjati. Iżda li l-multa minħabba omega jirreferi għal xenarji każ aħjar, inputs aħjar każ, anki jekk huwa jinsab biss każwali Xorti dumb. 

Issa, dan ukoll aħna qed tmur biex biss tip ta 'vojt leave għal issa. Sort bużżieqa Kif dwar issa? Fl-agħar każ ma sort bużżieqa, kulħadd huwa fl-ordni invers, hekk għandna nagħmlu ħafna ta 'tbaqbieq. Imma kif ħafna passi huwa li se tieħu fl-agħar każ? >> [Student] N kwadru. Dan kien il-n kwadrat, għaliex jekk inti taħseb dwarha, jekk il-lista hija kompletament lura - 8 huwa aktar hawn, 1 huwa minn hawn - bħala ħaġa jibdew bużżieqa, in-numru 8 huwa ser jiċċaqalqu b'dan il-mod, dan il-mod, B'dan il-mod, dan il-mod, iżda fejn huwa n-numru 7 fl-agħar każ? Hawn hi għadha hemmhekk. Allura aħna għandna biex jagħmlu mill-ġdid u għal darb'oħra. U li fejn irridu jiksbu passi n, allura n - 1 passi, allura n - 2 passi. U jekk inti tieħu kelma tiegħi għaliha - li jekk inti-tip ta 'immoltiplika dan jitwettaq, huwa bejn wieħed u ieħor kwadru n fl-aħħar ma 'xi termini oħra li aħna ser biss jinjora għal issa - imbagħad fil-tip bużżieqa agħar każ huwa n kwadrat, jagħtu jew jieħu. Imma x'inhuma l-aħjar każ ma sort bużżieqa? X'inhi l-aħjar xenarju? Kollha tal-numri huma magħżula diġà. U dak kien il-heuristic I użati, il-trick I użati, li tirrealizza li kelli jsir l-ebda xogħol u tista 'għalhekk twaqqaf kmieni? [Student] Iċċekkja darba. >> Iċċekkja darba. Imma dak li kien I tagħmel tul it-triq? I kien iżżomm rekord ta 'kemm tpartit I magħmula. U jien realizzati jekk jien ma jingħaddux ebda swaps fuq swaba tiegħi, imbagħad I ghamilt ebda xogħol. I ċertament ma għandhiex tipprova tagħmel ebda xogħol ġdid, hekk nista 'biss tieqaf. 

Allura fil-każ aħjar ta 'tip bużżieqa meta l-lista hija diġà magħżula, dak would you say in-notazzjoni omega huwa, l-aħjar każ running time? Huwa biss n. Għandna biex jagħmlu xi xogħol, iżda aħna biss għandek tagħmel jiswew 1 stroll ta 'ħidma. U hawnhekk ukoll jien ser tħalli din vojt parti. U issa sort għażla. Sort Għażla kien me tnittif il-persuna iżgħar u għal darb'oħra. U dak ma ngħidu l-running time ta 'li kien? Dan kien n kwadrat fl-agħar każ. U sfortunatament, fl-aħjar każ huwa wkoll n kwadrat minħabba I ma jkollhomx il-tip ta 'dawl omniscient tad-dinja kollha; I biss jafu fuq iterazzjoni sħiħ li stajt tabilħaqq instabu l-persuna iżgħar. Allura l-għażla it-tip tip ta 'sucks f'dan is-sens, iżda l-rasu huwa huwa tip ta 'intuwittivi. Huwa pjuttost faċli għall-kodiċi up għaliex kull ma għandek tagħmel hu li tikteb ftit nested għal-linji, tipikament, li tmur permezz tfittex l-element iżgħar u mbagħad ipoġġu l-element iżgħar fejn jappartjeni fl-aħħar tal-lista. Allura hawnhekk ukoll hemm għaddej li jkun kompromess. L-ammont ta 'ħin li tieħu inti biex jaħsbu u li fil-fatt jiżviluppaw xi ħaġa bil-kitba kodiċi tista 'faċilment jieħdu aktar żmien jekk inti tixtieq a prestazzjoni aħjar algoritmu u aktar malajr. 

Imma jekk int verament biss tip ta 'ħaġa Kodiċi up malajr u maħmuġin u biss tip ta 'tieħu l-idea stupidest possibbli inti tista' taħseb, li jista 'jieħu inti ftit minuti għall-kodiċi, iżda ma' settijiet ta 'data kbar algoritmu tiegħek jista 'jieħu sigħat jiddekorri. U anki jien fl-iskola gradwati se kultant tagħmel dawn il-kompromessi. Ikun 03:00, I kien qed jipprova janalizza xi sett ta 'data kbar ħafna relatat mal-riċerka tas-sigurtà I kienet tagħmel, u kien la jonfqu 5 minuti tweaking programm tiegħi biex tanalizza l-informazzjoni u tmur torqod jew iqattgħu 8 sigħat jkollna dan biss id-dritt hekk hija u tieqaf istantanjament u ma tmur torqod. U għalhekk hemm wisq huwa tip ta 'deċiżjoni konxja. Inqas iżvilupp ħin, aktar irqad. Retrospettivament, I probabbilment ma għandu jinkoraġġixxi li meta l-għan hawnhekk huwa li jottimizzaw kwalità tal-kodiċi, iżda li wisq fid-dinja reali hija ħafna raġonevoli kompromess. Inqas ħin, il-prestazzjoni inqas jew viċi versa. Allura hawnhekk aħna finalment jiksbu opportunità biex jitkellmu dwar theta. Theta notazzjoni hija xi ħaġa xjenzati tal-kompjuter tista 'ġġib up fil-konverżazzjoni meta big O u omega jiġri li jkun l-istess. You say theta biex verament jibgħat il-messaġġ li dan huwa tip ta 'stretta marbuta. Ma jimpurtax jekk l-xenarju hija tajba jew ħażina, huwa n kwadru. Allura huwa biss mhux rilevanti dawn l-istejjer hawn. Sort Inserzjoni hija l-aħħar wieħed ħarisna lejn, fejn I kien biss ddaħħal kulħadd fil-post it-tajjeb. Fil-każ aħjar dak li kien il-ħin tmexxija ta 'tip inserzjoni kif aħna raw dan hawn? [Student] L-aħjar każ? >> L-aħjar każ. 

Kien n għax magħżula kulħadd fil-każ aħjar, u Sammy u l-ebda wieħed inkella verament kellha timxi għal kollox. Huma kienu diġà fis-seħħ id-dritt tagħhom. Allura inserzjoni sort fil-każ aħjar huwa, f'dan il-każ, n. Iżda fl-agħar każ huwa tip ta 'n kwadru. Għaliex? Jekk il-lista tiegħi ta 'bniedem fl-ordni invers, I l-ewwel tibda bil-numru 8 u I daħħal lilu jew lilha fil-pożizzjoni dritt, li huwa dritt hawn. I tip ta 'moviment għall-ġenb. Dawn guys huma mhux magħżula, hu jew hi huwa magħżul. Imma issa I jiġri li ssib li jmiss? >> [Student] 7. 7 fl-agħar każ, għaliex dan huwa fl-ordni invers. 

Allura hawnhekk huwa 7. Fejn ma 7 jappartjenu? Żgur lura lili. Imma issa 7 attwalment tappartjeni mhux immedjatament wara lili iżda wara numru 8, so I għandhom jgħidu, "Skuża me, numru 8, tista 'jekk jogħġbok timxi b'dan il-mod "Biex tagħmel spazju għal 7?" Issa I jiltaqgħu 6. "Oh, skuża me, numru 8 u n-numru 7, inti tista 'timxi biex tagħmel spazju għal 6?" Allura fi kliem ieħor, ma sort inserzjoni, anki jekk jien ma nagħmilx moviment ħafna, il-poplu wara me qed jagħmlu xogħol ħafna aktar, u li ltqajna biex ispiża ħin xi ħadd. Huwa ser jiswew l-ħin tal-kompjuter. Allura fil-każ ta 'tip inserzjoni aħna xorta jsofru. Jekk inti tibda żżid l-għadd totali ta 'passi, aħna jispiċċaw laqtu bejn wieħed u ieħor kwadru n minħabba li dawn guys bżonn tagħmel spazju għall-bniedem li jiddaħħlu lura fis dik il-lista. U hekk f'dan il-każ theta huwa biss mhux applikabbli għall-istorja partikolari fil-idejn. Li kollox sbieħ u tajbin. Aħna dawn il-modi differenti ta '3 jitkellem dwar il-ħin qed taħdem. Imma dak ma dan fil-fatt tfisser f'termini reali jekk aħna fil-fatt jipprovaw kodiċi up algoritmu? 

Let me tipproponi li hemm algoritmu anki aħjar hemmhekk li hi stess għandha xi kompromessi. Aħna ser sejħa hija jingħaqdu sort, u huwa tip ta 'dan algoritmu maġika li biss taħdem aktar malajr b'xi, u huwa daqshekk faċli biex jesprimu, għall-inqas fil pseudocode. L-implimentazzjoni ta 'dan it-tip inkorporazzjoni algoritmu se tkun kif ġej. Meta inti qed tingħata n elementi - numri n, n-nies, ikun x'ikun - 1 hemm l-verifika sanità. Jekk n hija inqas minn 2, jingħaqdu tip biss waqfiet. Hija prospetti, biex ngħidu hekk. Għaliex kieku inti tieqaf jekk n hija inqas minn 2? >> [Rispons istudent inaudible] Dritt. U għal darb'oħra, n mhuwiex in-numru fil-lista, n huwa d-daqs tal-lista. Jekk n hija inqas minn 2, li tfisser lista tiegħek huwa jew 1, fejn int ovvjament magħżula jekk huwa numru 1, jew 0, f'liema każ hemm xejn biex issolvi, għalhekk għandna bżonn dan it-tip ta 'każ bażi. Jekk il-lista hija tant qasir li hemm biss xejn li tagħmel, litteralment ma tagħmel xejn. Ritorn. Inkella sort-nofs tax-xellug ta 'l-elementi, allura sort l-nofs tal-lemin ta' l-elementi, imbagħad jingħaqdu l-nofsijiet 2 magħżula. 

Dan it-tip ta tidher qisha iqarrqu ftit fejn jien inti titlob kif sort elementi u int javżak me, "Sort-nofs tax-xellug, isolvi l-nofs tal-lemin." Jien simili, "Kull dritt. Kif inti sort l-nofs tax-xellug?" "Sort l-nofs tax-xellug tan-nofs tax-xellug, isolvi l-nofs tal-lemin tan-nofs tax-xellug, u mbagħad isir." Inti tip ta 'ċiklikament li jiddefinixxu dak li tfisser li sort, iżda jirriżulta li l-fatt brillanti f'dan il-każ. Mhuwiex verament dan iċ-ċiklu vizzjuż li qatt ma tispiċċa minħabba li ma jintemmx meta? >> [Student] Meta inti tilħaq 1 ħaġa. Meta inti tilħaq 1 ħaġa. Għalhekk anki jekk inti tista 'tibda ma' 8 persuni u jien ngħid, "sort l-nofs tax-xellug ta 'dawn in-nies, dawn in-nies 4, "imbagħad I say," Kif inti sort l-nofs tax-xellug? " "Well, sort-poplu 2 hawn." U allura int simili, "Kull dritt, multa." "Kif inti sort l-nofs tax-xellug ta 'dawk in-nies?" "Just sort din il-persuna 1 hawn." X'hemm-rivelazzjoni brillanti issa? Għandi biex issolvi persuna 1. Magħmul. I ma jkollhom jagħmlu xi xogħol. Imma issa għandi biex issolvi din il-persuna, iżda dawn qed persuna waħda, xejn li jagħmlu. 

Allura l-magic apparentement huwa f'dan tielet pass: jingħaqdu l-nofsijiet magħżula. Sort Allura jingħaqdu jieħu din ħarsa brillanti li jekk inti break problema kbira isfel fis-2 iżgħar, identiku daqs problemi u mbagħad biss tip ta 'kolla-soluzzjonijiet iżgħar flimkien fl-aħħar, Nipproponi li nistgħu nagħmlu ħafna, ħafna aħjar [ħoss tapping] minn kwalunkwe ta 'tip ta' għażla jew tip inserzjoni. Stajt attwalment ġew injorat li għal nofs siegħa, imma jien verament ma nafx x'inhu għaddej barra illum. [Whirring ħoss] [Rires] Mela ejja ara jekk nistgħu naraw dan bi ftit għajnuna mill Bowden tagħna ħabib Rob. Hemm 2 passi kbar fil-proċess ta 'tip jingħaqdu. L-ewwel, kontinwament taqsam il-lista tal-cups fis nofsijiet sakemm għandna mazz ta 'listi mal biss 1 tazza fihom. Tinkwetax jekk lista fiha numru fard u inti ma tistax tagħmel qatgħa perfettament nadif bejniethom. Just pick arbitrarjament li lista biex tinkludi l-tazza żejda pulzieri Mela ejja maqsuma dawn il-listi. Issa għandna 2 listi. Issa għandna 4 listi. Issa għandna 8 listi ma 'tazza waħda f'kull lista. Allura dak li għall-pass 1. Għal pass 2 aħna ripetutament jingħaqdu pari ta 'listi li jużaw l-algoritmu jingħaqdu aħna tgħallimna qabel. Twaħħid 108 u 15 aħna tispiċċa bil-lista 15, 108. Twaħħid 50 u 4 aħna jispiċċaw ma '4, 50. Twaħħid 8 u 42 aħna jispiċċaw bi 8, 42. U qed jingħaqdu 23 u 16 aħna jispiċċaw ma 16, 23. Issa listi kollha tagħna huma ta 'daqs 2. Avviż li kull wieħed mill-listi 4 huwa magħżul, hekk aħna tista 'tibda amalgamazzjoni pari ta' listi ġdid. Twaħħid 15 u 108 u 4 u 50 aħna l-ewwel jieħdu l-4, allura l-15, allura l-50, allura l-108. Twaħħid 8, 42 u 16, 23 aħna l-ewwel jieħu l-8, allura l-16, allura l-23, allura l-42. Allura issa għandna biss 2 listi ta 'daqs 4, li kull wieħed minnhom huwa magħżul. Allura issa aħna jingħaqdu dawn il-listi 2. L-ewwel nieħdu l-4, allura aħna jieħdu l-8, allura aħna jieħdu l-15 u 16 u 23 u 42 u 50 u 108. U aħna qed isir. Issa għandna lista magħżula. 

Rob kien tip ta 'tieħu vantaġġ ta' xi ħaġa li aħna għadhom m'għamlux. Ġie ssuġġerit, imma aħna ma attwalment jagħmlu dan. Huwa kien isir xi ħaġa fiżikament mal-cups li tissuġġerixxi kien infiq xi riżors minbarra żmien. >> [Student]. Ispazju >> Kien ispazju. Il-fatt li huwa kien dan it-tip ta 'bi-livell tabella fejn kellu spazju up here u l-ispazju stabbiliti hawn kien attwalment dan jimplika li hu użu spazjali darbtejn daqs bħala kwalunkwe ta 'algoritmi tagħna s'issa - tip inserzjoni, sort bżieżaq, jew l-għażla sort - iżda kien jitqawwa dan l-ispazju addizzjonali għal tip ta 'affarijiet jimxu quddiem u lura filwaqt li jżommu l-affarijiet fl-ordni. U anki jekk iħoss bħal sirna għal lista magħżula, li qisni hija ħadet ftit żmien. Fir-realtà, dak li Rob kien isir kien eżattament dan algoritmu. Huwa l-ewwel ħa l-problema ta 'n-daqs, maqsuma hija fis-nofs tax-xellug u nofs id-dritt. Li meta huwa mċaqlaq-cups. Imbagħad huwa ripetut il-proċess. Huwa maqsum 4 fi 2 settijiet ta '2 hawn fuq u hawn fuq. Imbagħad huwa ripetut il-proċess u maqsum 2 fis-2 settijiet ta '1 għal kull waħda minn dawn tazzi varji. U li fejn l-opportunità brillanti tqum. F'dak il-punt fl-istorja, Rob kellhom 8 listi ta 'daqs 1, li kollha kienu magħżula diġà. 

Mela allura dak ma hu tipproċedi biex tagħmel? Pairwise huwa ħa din il-lista magħżula u din il-lista magħżula u magħquda minnhom. Imbagħad huwa ħa dan wieħed u magħquda minnhom, allura dan wieħed u magħquda minnhom, allura dan wieħed u magħquda minnhom. U allura dak ma hu tagħmel jmiss? Huwa mbagħad jerġa 'amalgamata l-listi akbar u mbagħad jerġa' amalgamata l-listi akbar. U jekk taħseb dwar dan biss intuwittivament għal issa, dak li kien hu verament tagħmel? Huwa kien diviż il-problema fil nofs, fil nofs, fil nofs, nofs sabiex jiksbu dawn il-listi żgħar super. Imbagħad kien it-tip ta 'kif tgħaqqad, double doppja, double, double. Hekk kien isir darbtejn bħala xogħol kemm aħna stajt tidher s'issa ma 'xi ħaġa li tinvolvi firda u conquer, iżda l-ebda big deal. Xogħol doppju mhuwiex tali big deal. Huwa biss fattur kostanti. U ħafna bħal espressjoni aritmetika tagħna qabel, jien biss se jaqsmu l-fatturi kostanti bħal ħinijiet 2. Who cares? Jekk huwa 2 biljuni darbiet 2, li għadu ħafna ta 'passi. Allura dan il-pass li qed jingħaqdu jidher li jkun l-għarfien ċavetta. Ejja jimxu permezz ta 'dan biss numerikament qabel - Oh, dak ma jitkompla għadu. Ejja jimxu permezz ta 'dan numerikament biss biex effettivament jaraw kif dan jilgħab barra. Dan huwa aktar biss animazzjoni raġel fqir ftit ta. Ejja jipproponi dan. Il-ħin tmexxija ta 'tip jingħaqdu - aħna biss bżonn ta' mod ta 'jitkellem dwar dan. Dan mhux matematika, din hija biss it-tip ta 'mod konċiż li jesprimu nfusna. Allura T tirrappreżenta ħin u n jirrappreżenta dak? >> [Student] Id-daqs tal-- 

[Malan] Id-daqs tal-problema, l-għadd ta 'nies. Allura jien fejn sostniet li l-ħin taħdem biex issolvi n-nies n se jkun ta '0 ammont ta' ħin jekk n hija inqas minn 2, għaliex jekk għandek 1 tazza jew l-ebda tazzi, għandek xejn biex issolvi. Iżda aktar ġenerali, jien ser nipproponi li l-ħin taħdem biex issolvi l-elementi n se tkun il-ħin li tieħu biex issolvi l-nofs tax-xellug kif ukoll il-nofs tal-lemin plus - x'hemm dan addizzjonali + n? >> [Student] sort Merge. [Malan] Huwa fatt li qed jingħaqdu, għaliex jekk ikollok n / 2 elementi hawn u inti għandek n / 2 elementi hawn, kemm ħin ma jieħdu biex jingħaqdu? Eżatt bħal Rob, inti għandek ġewwieni dan wieħed hawn fuq, forsi ġewwieni hawn fuq, ġewwieni hawn fuq, ġewwieni hawn fuq, ġewwieni hawn fuq. Inti għandek tmissx kull wieħed mill-cups darba. U jekk hemm 4 tazzi plus 4 tazzi, li 8 tazzi jew b'mod aktar ġenerali, 8 tazzi n. Allura l-pass li qed jingħaqdu nistgħu jesprimu bħala n- u li litteralment jinvolvi n-numru ta 'drabi Rob fiżikament jintmess wieħed minn dawn tazzi Styrofoam. Mela ejja issa do eżempju arbitrarja. Jekk hemm 16 tazzi, x'inhu l-ħin tmexxija ta 'l-għażla, bl-użu algoritmu Rob s, 16 tazzi? Huwa 2 darbiet l-ammont ta 'ħin li tieħu biex issolvi 8 tazzi għaliex għandna 8 tazzi hawn, 8 tazzi hawn. I do not know kemm żmien li tieħu, hekk aħna qed jiġġeneralizzaw bħala T għall-mument. Min jaf għalxiex? Imma issa I tista 'tip ta' recursively jew ripetutament jistaqsu l-istess kwistjoni. Kif ħafna ħin ma jieħdu biex issolvi 8 tazzi? 8 tazzi jien ser ngħid tieħu l-ammont ta 'ħin li tieħu biex issolvi 4 tazzi plus 4 tazzi, imbagħad jingħaqdu flimkien. Fine. Aħna jkollna fis-ċiklu diġà. Kemm idum ma jieħdu biex issolvi 4 tazzi? Il-ħin li tieħu biex issolvi 4 tazzi huwa 2 tazzi flimkien ma '2 tazzi issortjar flimkien mal-proċess li qed jingħaqdu. Fine. Kemm idum ma jieħdu biex sort 2 tazzi? 2 tazzi huwa l-ammont ta 'ħin li tieħu biex issolvi 1 tazza flimkien mal-ħin li tieħu biex issolvi ieħor tazza flimkien mal-ammont ta 'ħin li tieħu biex jingħaqdu, li huwa biss 2. 

Fine. Aħħar mistoqsija. Kemm idum ma jieħdu biex sort 1 tazza? Hawn hu l-każ ta 'bażi ​​li aħna mbassra aħna'd hit qabel. Il-fatt li dan jieħu ebda xogħol tkun xi tkun biex issolvi l-iżgħar tal-problemi ifisser li issa, it-tip ta 'stil iskola grad, nistgħu biss tmur tibda fejn jitwaħħal dawn in-numri lura pulzieri Aħna issa jkunu jafu liema T ta '1 huwa, so I tista' plagg fil 0 għall T ta '1. Li se tagħti me-risposta għal T-2, li jiena mbagħad tista 'plagg fil sa ogħla. Li se tagħti me T ta '4, li nista' plagg fil sa ogħla. Li se tagħti me T tat-8, li nista 'plagg fil sa ogħla. U jekk I attwalment do li matematika minn fejn jitwaħħal fil dawn it-tweġibiet, I imbagħad nikseb T ta '16 huwa 64. U dak jirrappreżentaw 64 ma? Jekk T huwa 16, yeah, huwa 16 darbiet 4. So I jsostnu issa li l-ħin tmexxija ta 'dan ħaġa imsejħa jingħaqdu sort - u dan se jkun l-fanciest ta 'dawk we stajt tidher s'issa - se jiġu msejħa n log n minħabba kif ħafna drabi tista 'Rob maqsum mazz sħiħ ta' tazzi-nofs? Log n. Huwa l-istess bħall-eżempju ktieb tat-telefon, huwa l-istess bħal l-eżempju awto-għadd. 

Kemm-il darba tista 'taqsam xi ħaġa fil-nofs? Madankollu, hemm dan il-pass li qed jingħaqdu. Inti jista 'jkollok li jaqsam il-kikkri fil nofs mill-ġdid u għal darb'oħra u għal darb'oħra, imma kull darba li int se jkollhom jingħaqdu. U aħna qal qabel li jingħaqdu tazzi n jieħu passi n għaliex ikollok biex ġewwieni out tazza, ġewwieni out tazza, u inti għandek tolqot kull tazza darba, bħad Rob għamlet. Allura jekk aħna qed tagħmel log xi ħaġa n-ħinijiet u aħna qed tagħmel l-affarijiet n fuq kull wieħed minn dawk iterazzjonijiet, kull wieħed minn dawk halvings, għandna n log ħinijiet n. Allura jekk aħna plagg fil-16 f'dan l-eżempju, 16-il darba log ta '16 - ma joqogħdu jinkwetaw dwar għaliex dan huwa l-każ għal issa għaliex stajt ma ġibed l-bażi - iżda log tal-bażi 2 tas-16 huwa ta '4, 16 darbiet 4 huwa 64. Iżda għall-kuntrarju, jekk kellna użati tip bużżieqa jew tip jew inserzjoni għażla it-tip ma '16 numri, dak li l-ħin taħdem kienu kieku n hija 16? Ikun 16 kwadrat, li huwa 256, li anki jekk int ma pjuttost segwew l-matematika, 256 huwa akbar minn 64. Dik hija verament l-takeaway maġika hawn. U jirrealizzaw li jaħdmu permezz ta 'dan fl-eżempji iżgħar kif inti ser fuq pset jagħmilha ferm aktar intuwittivi. Imma dak li verament ifisser f'termini tal-jħossu ta 'dan algoritmu huwa dan: Jekk aħna verament tħares lejn it-tip jingħaqdu hawn - let me pull it up f'dan il-tieqa hawn - dan huwa eżempju kemmxejn differenti li bihom aħna għandna kollha 3 ta 'dawn algoritmi - bużżieqa, għażla, u jingħaqdu - biss ħdejn xulxin. 

Huma kollha bdew bil-bars każwali, u li tajjeb. Ħadd ma għandha vantaġġ fundamentali fuq l-ieħor. Jien ser fil-mument ikklikkja kull wieħed minn dawn animazzjonijiet - Bidu, Bidu, Bidu - malajr kemm nista 'biex, bejn wieħed u ieħor, huma kollha jibdew fl-istess ħin, u ejja jikkunsidraw il-każ agħar tip bużżieqa ta 'running time huwa dak? >> [Student] N kwadru. N kwadrat. Agħar każ tip Għażla running time hu? N kwadrat. U xorta jingħaqdu hija apparentement - anki jekk inti ma pjuttost issegwi l-matematika issa, li ser issir ħafna aktar intuwittivi matul iż-żmien - huwa, aħna jsostnu, n log ħinijiet n. U minħabba log n huwa strettament inqas minn n ladarba għandna numri kbar, n-ħinijiet log n hija iżgħar minn darba n n n kwadrat jew. Allura dak ma jħossu li attwalment jiġi algoritmu aħjar f'termini ta 'running time, n-ħinijiet log n-kuntrarju n kwadrat? Here we go. Ikklikkja, click, ikklikkja. 

Dak hu li jfisser li tuża xi ħaġa simili sort jingħaqdu. Għandna mument. Ejja naraw x'jiġri hawn. [Chuckles] Li l-flus fuq tip bużżieqa? Hija pjuttost jiddependi fuq il-kontribut kultant. Ejja naraw. Come fuq. Hija tħoss bħal hu ilaħħqu. >> [Student] Go, sort bużżieqa! [Studenti murmuring] [Malan] Yeah, yeah. [Studenti murmuring] Go, mur, mur! [Kollha cheering] [applause] Allura issa ma '1-aħħar, demo finali, jekk huwa ftit diffiċli biex nagħlaq moħħ tiegħek madwar l-matematika jew tip ta 'l-viżwalizzazzjoni hemm, inti tista' attwalment tisma 'l-veloċitajiet ta 'algoritmi differenti b'mod differenti. Dan huwa xi ħadd animazzjoni magħmula li attwalment assoċjati ħsejjes mal-proċess ta 'iskambji u l-għoli tal-bars. Kif aħna ser tara hawn, hemm xi algoritmi ftit issortjar aktar hemmhekk li folks ħsibt ta '. Dan ewwel waħda se tkun sort inserzjoni, u dan se jtir permezz u jagħtuk sens li tinstema 'kif jaħdmu dawn algoritmi varji. Hawnhekk huwa tip inserzjoni. [Beeping elettroniku] [Malan] sort bubble. [Mgħaġġla beeping elettroniku] [Malan] sort Għażla. [Mgħaġġla beeping elettroniku] [Malan] sort Merge. [Beeping elettroniku] [Beeping imewwet] [Rires] [Malan] sort Gnome. [Beeping elettroniku] 

Dan huwa CS50. Aħna ser tara inti ġimgħa d-dieħla. [Applause u cheering] 

[CS50.TV]