[Daqq tal-mużika] DAVID J. Malan: Kull dritt. Allura merħba lura. Dan huwa CS50, u l huwa l-aħħar ta 'tliet ġimgħat. Allura mfakkra fl-aħħar ġimgħat, aħna kont qed infiq pjuttost ftit ta ' ħin fuq C, dwar l-ipprogrammar, fuq sintassi. U huwa pjuttost normali, jekk int xorta tissara mal-problema Set 2, li jkun banging ras tiegħek kontra l-ħajt. Huwa messaġġi ta 'żball cryptic li tħares u bugs li inti ma tistax pjuttost chase isfel. Minħabba, mistrieħ assigurat, li fi ftit żmien ftit ġimgħat int ser tħares lura fuq affarijiet simili Caesar, u [? V-genair,?] forsi anki jixxaqqaq, u jirrealizzaw kemm inti ħadthom ġejjin fil-perjodu qasir ta 'żmien. Allura jekk dan huwa xi konsolazzjoni, hang fil hemm għal issa. Illum, għalkemm, aħna jibdew transizzjoni għal affarijiet livell ogħla. U aħna jibdew jieħdu għal mogħtija li inti guys taf kif program, jew inqas il-bidu ta ' dak il-livell kumdità. U aħna ser tibda biex jikkunsidraw kif nistgħu tmur dwar tfassil ta 'programmi aktar b'mod effettiv. Kif nistgħu tmur dwar ottimizzat l- effiċjenza ta 'algoritmi tagħna, u ġeneralment soluzzjoni aktar problemi interessanti. U jibdew jieħdu għal mogħtija li, jekk ridna li, nistgħu kodiċi up xi mill-eżempji li għandna fil-moħħ. Allura llum, aħna ma tmissx il-keyboard għal kwalunkwe forma ta 'kodiċi. Huwa ser jiġi livell ħafna ogħla, u finalment, dwar soluzzjoni tal-problemi. Allura biex tikseb dak il-punt, let me tipproponi li l-seba ġej rettangoli jirrappreżentaw seba bibien, wara li huma mazz sħiħ ta ' numri, li fosthom huwa n-numru 50. Let me proġett dan fuq dan screen hawnhekk ukoll. U jipproponu li għandna bżonn voluntier biex tgħin sabiex tinstab me numru quddiem l-internet hawn biex tara. Come on up, fil-roża. Kull dritt. X'hemm isem tiegħek? JENNIFER: [inaudible] DAVID J. Malan: Jiddispjacini? JENNIFER: Jennifer. DAVID J. Malan: Jennifer. Kull dritt, Jennifer. Nizza li jissodisfaw inti. Come fuq up. Allura dawn hawn huma seba 'bibien, u liema Nixtieq li tagħmel għalina hawnhekk, quddiem ta 'kollha ta' klassi tiegħek, huwa issibna-numru, 50. Biex issib numru, inti tista Peek wara xi wieħed minn dawn il-bibien billi sempliċiment ttektek fuq waħda mill-bibien, u se jiżvelaw in-numru tiegħu. U ejja ara kif malajr inti tista 'issibna in-numru, 50. 15. 16. 50. Nicely jsir. Kull dritt. Round ta 'applause għall Jennifer. [Applause] Kull dritt. Allura dak li kien l-istrateġija tiegħek għall konstatazzjoni tal-numru, 50? JENNIFER: Um, ħsibt forsi jekk - [Inaudible] DAVID J. Malan: Oh. Agħti tieni waħda. Hekk kien istrateġija tiegħek għall konstatazzjoni tal-numru, 50? JENNIFER: So I biss tibda fl- bidu biex tara dak li l-ewwel numru kien, u mbagħad ħsibt, forsi jekk dawn qed magħżula, jien ser biss iżommu tapping ogħla up? DAVID J. Malan: OK. U aħna jidhru li sabu dan ikun il-każ. Għalkemm, ejja qaxxar il-saffi biss ftit, u inti tixtieq li tmur quddiem u jiżvelaw l-bibien oħra inti tista għażilt? JENNIFER: Oh, għeżież. DAVID J. Malan: Ah. JENNIFER: So I biss ltqajna xxurtjati. DAVID J. Malan: Allura inti ltqajna xxurtjati. Kull dritt. Allura mhux ħażin. Imma thats interessanti għarfien, id-dritt? Jekk inti preżunt, u għamilt tikseb, tabilħaqq, daqsxejn xxurtjati hemmhekk. Imma jekk inti jassumi li n-numri kienu magħżula, inti tista 'tkun aktar preċiża dwar kif dik influwenzati imġieba tiegħek? JENNIFER: Mela jekk kienu magħżula, I ħsibt forsi iżgħar sa l-akbar. DAVID J. Malan: OK. JENNIFER: Jew jekk dan spiċċa biex tkun verament kbir, allura akbar għall-iżgħar. DAVID J. Malan: OK. Allura akbar biex iżgħar, jew iżgħar sa l-akbar. Iżda let me tipproponi, ejja ngħidu li inti kellhom gotten unlucky, u jissoponi li ma kinux, fil-fatt, magħżula, kemm ta ' dawk bibien jistgħu kellek Peek lura f'dak agħar każ? JENNIFER: Kollha kemm huma. DAVID J. Malan: Kollha kemm huma. Mela ejja tiġġeneralizza li bħala n. Jiġri li jkun hemm 7, imma ejja aktar ġeneralment jgħidu hemm bibien n fuq il- iskrin hawn. Allura fl-agħar każ, inti jkollok tfittex wara 7 bibien, jew bibien n. U hekk dan huwa verament, huwa daqsxejn ta ' Xorti llum, iżda huwa verament lineari algoritmu ta 'tipi, anki jekk inti kienu tip ta taqbeż is-site madwar. Huwa li ġust? JENNIFER: Yeah. DAVID J. Malan: Well, let me ara jekk tiegħek bidliet istrateġija jekk I twassalna lejn tieni eżempju tagħna hawn 7 bibien differenti. Numri istess, iżda dan darba li huma magħżula. X'hemm istrateġija tiegħek hawn se tkun, jippruvaw joħolqu minn moħħok dak in-numri l-oħra kienu - JENNIFER: OK. DAVID J. Malan: - qabel? JENNIFER: Nibdew l-ewwel waħda. DAVID J. Malan: Kull dritt. Jibda bl-ewwel wieħed. 4. Issa fejn inti se jmorru, u għaliex? JENNIFER: 4 huwa verament żgħir. Mela jekk dawn qed sort forsi iżgħar biex akbar, għandu jkun id-doppju dak, u -. DAVID J. Malan: OK. Ejja naraw, li taħseb? JENNIFER: Ipprova l-aħħar wieħed. Nizza. DAVID J. Malan: Ħafna nicely jsir. Kull dritt. [Applause] DAVID J. Malan: OK. Allura int fil-fatt tagħmel dan horribly, għax int tagħmel dan tajjeb ħafna. Li tħalli us kapaċi jagħmlu ċerti punti. Mela ejja jippruvaw li roll lura hawn. JENNIFER: OK. DAVID J. Malan: Tajjeb ħafna jsir, madankollu. Allura bdejt fil-bidu, inti raw li kien 4, allura inti tmexxa għall-aħħar. Imma ejja ngħidu li inti ma tikseb xxurtjati hemm, u jissoponi 50 kien x'imkien ieħor. What tielet pass tiegħek kienu? JENNIFER: Mur lura għall-bidu. DAVID J. Malan: Mur lura għall-bidu. OK, sabiex inti stajt mimsus dan il-bieb, li kienet ta '8. Kull dritt. Allura li mhux 50. Fejn kieku inti ħarsu jmiss? JENNIFER: Jekk jien ma jafu li magħżula. DAVID J. Malan: Korretta. Ukoll, jekk inti ma taf kienu magħżula - JENNIFER: Oh, ma taf, yeah. DAVID J. Malan: - imma inti ma taf fejn 50 kien għadhom? JENNIFER: Just iżommu għaddejjin. DAVID J. Malan: Kull dritt. OK. Jibqgħu għaddejjin. OK, li I jistgħu jaħdmu ma '. JENNIFER: OK. DAVID J. Malan: Issa, jekk int biss ser jibqgħu għaddejjin, x'hemm tiegħek algoritmu jiddevolvu appoġġjati fil. JENNIFER: Il lineari -. DAVID J. Malan: Huwa tip ta 'lineari. Iżda let me tipproponi, let me jitqiegħdu fuq il-post. Let me jġedded il-paġna. istess numru, l-istess arranġament, istess bibien. Iżda naħseb lura għal dak l-ewwel jum klassi meta aħna Tore ktieb tat-telefon fil- nofs, tip ta ', u dak li kien istrateġija tagħna hemm? JENNIFER: Ibda fl-nofs. DAVID J. Malan: OK. Allura tibda fil-nofs. Mela ejja imorru quddiem u jissimulaw dak. Ibda fl-nofs minn tiżvela dak il-bieb. Allura n-numru 16. Allura dak li l-Guy qawwija għamlu, li Tore-ktieb tat-telefon fil nofs, biex jiksbu l-raden jmiss? JENNIFER: Mur Din it-taqsima. DAVID J. Malan: U għaliex għad-dritt? JENNIFER: Jekk dawn kienu tip ta 'iżgħar għall-akbar, allura 50 għandu jkun fi dak il-għan. DAVID J. Malan: Tajba. Totalment raġonevoli. Allura bħal ktieb tat-telefon, inti tmur għall- dritt kif oppost għad-xellug, iżda hawnhekk hija l-muftieħ takeaway. Inti tista 'issa armih, jew tiċrita off, nofs ta 'din il-problema, jħalli inti ma ma '7 bibien, imma verament biss ma 3. Liema hija bejn wieħed u ieħor nofs il- daqs tal-problema. Kull dritt. Allura issa dak li inti jkollok jsir wara li inti tmur id-dritt? JENNIFER: Allura 16 għadu pjuttost żgħir, relattiv għal 50, hekk forsi I ser nippruvaw, simili, dan wieħed. DAVID J. Malan: Kull dritt. 42. Kull dritt, hekk issa x'hemm tiegħek istint tghidlek? JENNIFER: I tista tarmi l bogħod dan u mbagħad biss - DAVID J. Malan: OK. Tajba, inti tista tarmi l bogħod in-nofs xellugi hemmhekk. JENNIFER: - pick dan wieħed. DAVID J. Malan: U d-dritt. JENNIFER: Yeah. DAVID J. Malan: Allura anke jekk huwa diffiċli biex tara forsi, meta jkun hemm biss 7 bibien, jaħsbu dwar, issa, il-konsistenza tal- Algoritmu inti biss applikati. Fil-każ preċedenti, għamilt tikseb xxurtjati, li kien kbir. Imma inti ma tuża heuristic, Jien ngħid. Inti użati tip ta 'instincts tiegħek, u jkunu jafu magħżula, jekk huwa pretty żgħir fil-bidu, ovvjament, konna ltqajna biex tmur aktar lejn il-lemin. Iżda f'xi sens, inti ltqajna xxurtjati, għaliex forsi dan kien in-numru 100, u forsi 50 kien aktar fin-nofs. Forsi 50 kien saħansitra hawn fuq. Imma dak li għamilt ftit differenti din id-darba kien, għamilt l-istess ħaġa ġdid u għal darb'oħra. U nixtieq jargumentaw li dak li inti biss ma, għalkemm influwenzati mill-telefon eżempju ktieb, hija xi ħaġa ferm aktar algorithmic, u ħafna inqas speċjali b'għata. Ħafna inqas istintiv. Għalhekk fl-aħħar tal-ġurnata, kif kieku tiddeskrivi l-effiċjenza ta 'l- ewwel algoritmu, fejn inti marru xellug għal-lemin, kontra l- tieni algoritmu hawn? JENNIFER: Dan wieħed għandu, bħal, forsi tnaqqas iż, jew saħansitra aktar, yeah. DAVID J. Malan: OK, forsi anke aktar. Ejja timbotta ftit diffiċli fuq dan. Dak li verament, jekk inkomplu din loġika, aħna definittivament bin-nofs l- running time ma 'din it-tieni algoritmu billi jitfa bogħod nofs il- numri, imma dak li ma nagħmlu fuq il-li jmiss iterazzjoni, meta Jennifer żvelat it-tieni numru? Aħna bin-nofs in-numri ta 'bibien mill-ġdid. U allura dak li ma nagħmlu wara li, jekk kien hemm bibien aktar biex jilagħbu ma? Nixtiequ jonqos bin-nofs minnhom, u għal darb'oħra, u għal darb'oħra, u għal darb'oħra. U dan kien biss bħal inti guys kollha wieqfa fl-ewwel ġimgħa ta ' klassi, nofs inti bilqiegħda, nofs tal inti bilqiegħda, nofs inti bilqiegħda, sakemm wieħed isolati ruħ kien bil-wieqfa. U aħna qal li l-ħin tmexxija ta ' li, l-għadd ta 'passi li ħa kienet fuq l-ordni ta 'xiex? SPEAKER 1: [inaudible] DAVID J. Malan: Allura log bażi 2 ta 'n, jew biss aktar sempliċi, log ta 'n. Allura xi ħaġa logaritmika. U l-grafika ma kienx linja dritta li biss marret għall-agħar u agħar, kien din il-kurva interessanti li ma tikseb daqshekk ħżiena matul iż-żmien. Mela ejja iżommu lill din l-idea. Ejja nirringrazzja Jennifer. Grazzi tant għall ġejjin fuq up. U, wieħed taqs. Ebda bozoz mejda llum, imma aħna do jkollhom CS50 blalen istress. JENNIFER: Yay. DAVID J. Malan: Kull dritt, hawn. Grazzi għall jeħel l-istress up here. Kull dritt. Mela ejja ara jekk nistgħu mhux issa jifformalizza din daqsxejn aktar. Għalhekk għal darb'oħra, dak li aħna biss ma kien essenzjalment l-istess ħaġa bħat għamilna f'dan l-ewwel ġimgħa. Iżda pjuttost milli tmiem biss bi lineari algoritmu, li aħna jidhru qabel bħala din il-linja dritta, fejn, jekk npoġġux wieħed bieb aktar fuq l-iskrin, allura Jennifer kieku kellhom ħarsa, potenzjalment, wara bieb wieħed aktar. Jekk nistaqsu żewġ bibien aktar, hi jista 'jkollhom tfittex wara żewġ bibien aktar. U hekk, kien hemm dan lineari relazzjoni bejn id-daqs tal- problema, ngħidu aħna, l-assi x, u l-ammont ta 'ħin li tieħu biex isolvu fuq il-y. Iżda l-istampa I kien jalludi għal qabel kienet din il-linja ħadra. Green deliberatament, minħabba huwa biss ħassew aħjar. Fit-teorija, l-algoritmu, meta aħna ma kien mal-ktieb tat-telefon, meta aħna ma kien miegħek guys għadd xulxin, u fit-tieni każ, meta Jennifer biss ma kien up hawn, kien sort tal fundamentalment aħjar. Minħabba li ma kienx biss darbtejn aktar malajr. Lanqas ma kien erba 'darbiet malajr. Kien kompletament dipendenti fuq dak il- daqs tal-input kien, dwar kemm passi li finalment ħa. U hekk din l-idea sempliċi li aħna kollha ħa għall mogħtija mal-ktieb tat-telefon, jistgħu bl-istess mod jiġu applikati għal xi ħaġa bħal din. U dan jista 'jkun aktar każwali magħrufa bħala, kif inti tista ' jimmaġina, jaqsam u jirbħu. B'differenza ma dak li għamilna, naturalment, mal-ktieb tat-telefon. Iżda l-pseudocode, recall, kien dan. Allura aħna mhux se tagħmel dan mill-ġdid, iżda tfakkar li l-ewwel ġimgħa, lkoll saqajh u mbagħad nofs tal inti sib stabbiliti, nofs inti sib stabbiliti, nofs inti sib stabbiliti. Din l-algorithm ġiet implimentata daqsxejn ta 'mod qerq, peress li, hija kienx biss waħda mill me għadd, fundamentalment, b'mod aktar effiċjenti. F'dak il-każ, I kien jitqawwa riżorsa sekondarja. Sort ta ', CPUs multipli, imħuħ multipli, nies intelliġenti multipli fil- kamra ġew tgħin me tikseb minn xi ħaġa lineari għal xi ħaġa logaritmika, minn xi ħaġa aħmar għal aħdar xi ħaġa. Iżda f'dan il-każ, Jennifer weħidha ma fundamentalment jtejbu fuq l- prestazzjoni ta 'l-ewwel algoritmu tagħha minn, għal darb'oħra, biss ħsieb ftit diffiċli. U issa, meta niġu żmien biex jimplimentaw dawn l-affarijiet, jidhru liema linji tal-kodiċi tista 'tikteb bħal li inti tista 'tirrepeti lilhom mill-ġdid, u għal darb'oħra, u għal darb'oħra, tip ta ' b'mod looping. Minħabba int mhux se jkollhom l- lussu, bħal Jennifer ma fl-ewwel, biex biss ikollhom mazz sħiħ ta 'IFs u jgħidu, hmm, jekk din l-ewwel numru huwa 4, let me jaqbżu it-triq kollha sa l-aħħar. Ooh, jekk dak in-numru huwa kbir wisq, let me jimxu arbitrarju lura għat-tieni element. Inti ser issib li huwa għaddej li jkun hemm ħafna aktar diffiċli biex tifformalizza dak aħna bnedmin jieħdu għal mogħtija bħala raġonevoli ħafna heuristics, iżda l-kompjuter huwa biss se tagħmel dak li inti tgħid li tagħmel. Issa dan għandu interessanti ħafna implikazzjonijiet. Din il-graff hija tip ta maħsub biex isolvi ta jisbqu viżwalment, imma avviż, fejn hija l-linja dritta f'dan graff? Fejn hi l-graff lineari li nitolbu n? Ukoll, huwa tip ta 'lejn il-qiegħ ta 'din l-istampa, id-dritt? Allura kollha għandna ghamilt hija konna tip ta ' żżomjati out għall-assi-x u il- assi-y biex nipprova nikseb sens ta 'dak tipi oħra ta 'kurvi look like. U l-ispeċifiċitajiet ta 'l-matematiċi espressjonijiet illum mhux se kwistjoni hekk ħafna, iżda avviż li hemm ħafna ta ' algoritmi li huma ħafna agħar minn xi ħaġa li lineari. Tabilħaqq, n kubiku jistenna pretty bad. 2 għall-n jistenna pretty bad. n kwadrat jistenna pretty bad. U aħna ser tara dak li xi wħud minn dawk jista 'jkun fir-realtà llum. U log n ma jħossx bħala ħżiena, iżda aħjar minn n huwa log bażi 2 ta 'n. Imma inti taf, kien ikun saħansitra aktar aqwa jekk Jennifer, jew jekk aħna, li l-ewwel ġimgħa, kienet toħroġ bi xi ħaġa li log log ta 'n. Allura fi kliem ieħor, hemm dan kollu firxa ta 'soluzzjonijiet possibbli għall- problemi, iżda anke hawn, l-avviż x'inhu jiġri. Meta I zoom out, liema minn dawn kurvi se jirriżultaw li huma l assoluta agħar ta 'dawk fuq l-iskrin issa? Allura n kubiku jistenna pretty gravi fil-mument. Imma jekk irridu zoom out u ara aktar tal- x u il-y-axis, li għaddej biex jiddominaw finalment? Għalhekk fil-fatt jirriżulta li 2 għall- n, u inti tista 'figura dan biss billi fejn jitwaħħal f'xi kbir dejjem jiżdied numri, u tkun taf tara li 2 għall- n, tabilħaqq, tkompli tikber ħafna aktar mgħaġġla. Jekk aħna verament zoom out, a 2 għall- n algoritmu assolutament sucks. I tfisser dan se jieħu pjuttost ftit ta 'żmien għall- kompjuter biex lenbija permezz. Imma int ser tara matul iż-żmien, speċjalment ma 'settijiet problema futuri u anke proġetti finali, hija data tiegħek sett gets kbira, id-dritt? Anke fl-ewwel verżjoni ta 'Facebook, bħala n-numru ta 'ħbieb, u l- numru ta 'utenti reġistrati ltqajna kbar, inti tista sort ta 'telefon fil u timplimenta xi ħaġa ma 'search lineari, jew għażla sempliċi ħafna algoritmu, kif Ser naraw illum. Int għandek tibda taħseb aktar diffiċli u aktar diffiċli dwar dawn il-problemi. U t-tipi ta 'problemi postijiet bħal Facebook, u Google, u Microsoft, u oħrajn jaħdmu fuq huwa eżattament dawn tip ta 'big tip data ta' mistoqsijiet dejjem dawn il-jiem. Kull dritt. Allura suċċess Jennifer f'dan it-tieni algoritmu, franchement, hija għamlet amazingly ukoll l-ewwel darba, iżda ejja tiktibha kif Xorti sabiex inkunu tista 'tagħmel dan il-punt. Fit-tieni każ, hija leveraged l algoritmu li ripetuta mill-ġdid u għal darb'oħra, iżda hi ħa jingħataw ċerti suppożizzjoni li aħna permess tagħha, iżda hi sfruttata xi dettall l- tieni darba li hi ma kellhiex l- ewwel darba. Liema kien dak? Li l-lista ġiet magħżula. Allura hekk kif il-lista ġiet magħżula, aħna jsostnu li Jennifer kienet f'pożizzjoni li tagħmel fundamentalment aħjar. 7 bibien, iva, mhijiex dik interessanti, iżda jissoponi li aħna qed 7000000 bibien. Log ta 'n huwa definittivament se biex iwettqu ħafna, ħafna aktar mgħaġġel fit-tul. Iżda hija kellha li jkollhom l- bibien magħżula għall tagħha. Issa, I ħa l-libertà li jagħmlu dan bil-quddiem fuq l-iskrin tal-kompjuter hawn, iżda jissoponi li Jennifer kellha tagħmel dan lilha nfisha? Ejja ngħidu li l-bibien in kwistjoni data rappreżentati f 'database, jew ħbieb rreġistrati għal Facebook, jew xi paġni web fuq l-internet li diversi websites jistgħu jeħtieġu biex indiċi jew tfittxija fuq. Ejja ngħidu li inti biss kellhom data mhux ipproċessata stabbiliti u kien f'idejn lilek, jew li Jennifer biex tagħmel dan issortjar? Li, aktar, teħtieġ li aħna risposta il-kwistjoni, ukoll, kemm ħin kienx jieħu Jennifer, jew saħansitra me, biex issolvi dawn in-numri bil-quddiem sabiex li hi tista 'tieħu vantaġġ ta' dak? Dritt? Minħabba li l-implikazzjoni, naturalment, huwa jekk tieħu me pjuttost filwaqt li sort in-numri, li l-Heck cares li inti tista 'ssib numru simili 50 daqstant b'mod mgħaġġel, bħal fil-każ Jennifer, jekk aħna aktar minn megħlub l-ammont ta 'ħin totali hija ħadet bl-għażil affarijiet bil-quddiem? Mela ejja ara jekk aħna ma tista 'l- żebgħa l-istampa hawn. I jkollhom mazz sħiħ aktar stress blalen, jekk li tgħin jkisser is-silġ hawn. U jekk inti ma mind, aħna bżonn seba voluntier - fuq, OK. Ara naqra. Allura aħna ma jkollu jonfoq fuq lampi desk, jidher. Kull dritt. Allura kif dwarek tnejn quddiem. Kif dwarek żewġ guys fid-dahar. Allura dak erbgħa. Kif dwarek quddiem ħames, sitt u seba '. Hemm dritt. Ħabib tiegħek tipponta out, sabiex tikseb l-premju. Kull dritt. Come fuq up. U għaliex ma we jkollhom inti guys jaqgħu fuq matul hawn. Jien ser jagħtuk kull numru. U jimxi 'l quddiem u jirranġa yourselves identiku għal dak jidhru fuq l-iskrin. [INTERPOSING VUĊI] DAVID J. Malan: OOP, sorry. Bug. Kull dritt. Well, here we go. Numru b'ħames. Numru sitta. Wieħed, tnejn, tlieta, erba, ħames, sitt, seba '. Oh, dan huwa skomda. SPEAKER 2: I taf biss jiksbu -. DAVID J. Malan: jittrattaw Tajba. Kull dritt. Grazzi għall-parteċipazzjoni. [Applause] OK. Kull dritt. Allura aħna għandna erba ', tnejn, sitta, waħda, tlieta, seba ', ħames. Perfetta hekk aħna f'seba 'voluntiera hawn li huma ugwali fil-wisa 'l- array li aħna qed jilagħbu mal-ewwel. U jien għażlet seba għal raġunijiet li se jkun biss konvenjenti fi ftit. U jien ser tipproponi ewwel li aħna issolvi dawn f'seba 'voluntiera. Jekk inti tixtieq, minn naħa, li jgħidu bonjour għalkemm. Peress li din se tkun skomdi diversi minuti. Introduċi yourselves. GRACE: Hi, jien Grace. Jien sophomore fil Leverett House. BRANSON: Hi. Jien Branson. Jien freshman fil Weld. Gabe: Hi. Jien Gabe. Jien junior fil Cabot. NEIL: Jien Neil. Jien freshman fil Matthews. JASON: Jien Jason. Jien freshman fil Greenough. MIKE: Jien Mike. Jien freshman fil Grays. JESS: Jien Jess. Jien sophomore fl Leverett. DAVID J. Malan: Eċċellenti. Kull dritt. Ukoll, grazzi għall kollha ta 'tagħna voluntiera hawn s'issa. U l-isfida fil-idejn issa huwa għaddej li jkun biex issolvi ta 'dawn guys, iżda mbagħad aħna qed tmur biex ikollhom biex jaħsbu ftit hard dwar kif effiċjenti nistgħu attwalment magħżula minnhom. Mela ejja ewwel tipprova dan. You guys tista 'tara n-numri ta' xulxin biss mill-tqegħid madwar il-kantunieri. Jimxi 'l quddiem u tieħu ftit sekondi, u sort yourselves mill-iżgħar fuq l- xellug għal akbar fuq il-lemin. Mur. OK. Tajba. Dan kien verament darn fast. Issa xi ħadd hawnhekk, dak li kien l-algoritmu li dawn guys applikati? SPEAKER 1: Inqas għall-akbar. DAVID J. Malan: OK. Inqas sal akbar huwa verament sort ta 'l- għan, iżda M'inix ċert li l- verament algoritmu. Inqas sal akbar ma tgħid me pass pass x'għandek tagħmel. Yeah? SPEAKER 1: [inaudible] DAVID J. Malan: OK. Mela jekk inti tara persuna iżgħar minn numru tiegħek, mbagħad jimxu għal id-dritt minnhom. Allura thats issa jkollna aktar espressiva, aktar bħal algoritmu, għaliex inti jista 'jgħid, jekk dan, allura dik. Allura aħna għandna xi tip ta ' tibni kondizzjonali. U dawn guys deher li tagħmel dan ftit drabi, minħabba li xi wħud minnkom mċaqalqa daqsxejn ta 'distanza. Allura kien hemm preżumibbilment xi tip ta ' looping għaddej fl-imħuħ tagħhom. Imma ejja jippruvaw li jifformalizzaw dan. Jekk inti guys tista reset lura għal dan l-arranġament. Ejja naraw jekk aħna ma tistax jifformalizza din l- bit, u mbagħad titlob il-kwistjoni, biss kif effiċjenti huwa dan? Of course, meta nagħmlu dan aktar bil-mod, li għaddej biex jħossu bħala tajba ta ' algoritmu, imma ejja ara jekk nistgħu jitqiegħdu idejna fuq il-passi preċiżi. Allura inti żewġ guys huma erba 'u tnejn. Jew inti ordni eżatta jew żbaljata? Ovvjament żbaljata. Allura aħna biddlu. Issa jien ser jiċċaqalqu aside hawn u jgħidu, 4-6. Inti eżatta jew żbaljata? Gabe: Korretta. DAVID J. Malan: Korretta. Sitta u wieħed? Nope. Tpartit. Allura dak żewġ tpartit. Sitta u tlieta? Nope. Tpartit. Sitta u seba? Jidher tajjeb. Seba u ħames? JESS: [inaudible] DAVID J. Malan: OK, tpartit. U magħżula. Kull dritt. Allura ovvjament le, id-dritt? Allura kien hemm aktar għaddej. Iżda, fil-fatt, dawn guys, anke biss istintivament. miżmuma miexja. Huma ma tieqaf biss, ladarba korretta problema waħda. So. Tabilħaqq, jien ser ikollhom jagħmlu l-istess ħaġa. Jien ser ikollhom biex isolvi ta kontrina lura għall-bidu ta 'din il-problema, jew il-bidu ta 'din firxa ta' nies, ejja tibda sejħa minnhom. U issa dak li għandu algoritmu tiegħi fit-tieni pass ikun? SPEAKER 1: L-istess ħaġa. DAVID J. Malan: L-istess ħaġa. U dan, jien jibdew biex simili, right? Hekk kif inti tista 'ssib ruħek jagħmlu l-istess ħaġa mill-ġdid u għal darb'oħra, li l- isiru aktar simili algoritmu, u istint inqas bniedem. Allura issa, here we go darb'oħra. Żewġ u erba? No Erba 'u waħda? Ah, kien hemm tabilħaqq xi xogħol xi jsir. Għal u tliet? Tajba. Erba 'u sitt? Sitta u ħames? Sitta u seba? OK, issa, isir. OK, l-ebda. I ikollhom imorru lura. Allura issa, għal darb'oħra, aħna qed tagħmel dan ftit aktar deliberatament. U issa, hemm waħda biss tal-moħħ eżekuzzjoni din algoritmu. CPU waħda, jekk inti se. U franchement, dak l-uniku riżors aħna qed tmur biex ikollhom aċċess għall. U ladarba aħna ma jmorru lura għal tastiera u jkollhom xi ħaġa simili C lejn tagħna rimi, aħna qed biss kitba ta 'programm li tista 'tagħmel ħaġa waħda f'ħin wieħed. Billi, dawn guys mument ilu, aħna leveraged intelliġenza kollettiva tagħhom bħal inti guys għamlet fil-ġimgħa żero. Mela ejja iżommu tagħmel dan. Tnejn u wieħed. Tnejn u tlieta. Tlieta u erbgħa. Erba 'u ħames. Ħames u sitt. Sitt snin u seba '. Magħmula? So I am, iżda let me play avukat devil. Do I, il-tip tal-kompjuter li sempliċiment għamlet pass permezz ta 'dan firxa ta' nies, jafu li jien jsir? SPEAKER 1: Le DAVID J. Malan: Allura għaliex? X'għandu nagħmel biex jikkonkludi deċiżiv li jiena jsir? Probabbilment wieħed pass aktar. Dritt? Minħabba li kull naf minn dak preċedenti pass huwa li jien korrett żball. U dan ifisser, forsi hemm xorta żball ieħor li għandi bżonn biex jikkoreġu. So I jista 'jkun żgur biss mill rewinding, u allura iċċekkjar, 1-2, tnejn u tlieta, tlieta u erba ', erba' u ħames, ħames u sitt, sitt u seba '. OK, issa I ma ebda xogħol. I jista 'ċertament ftakar li għamilt ebda jaħdmu ma 'xi ħaġa bħal varjabbli, bħal int. Sejħa hija swaps, u jekk tpartit huwa 0 darba I nikseb hawn, u dan beda fil-0, imbagħad I se jkun biss stupid li jibqgħu għaddejjin quddiem u lura, il-verifika mill-ġdid, u għal darb'oħra, u għal darb'oħra, id-dritt? Għaliex inti jeħlu f'xi tip ta 'loop infinita. Allura hekk kif hemm 0 tpartit, nistgħu jsostnu li dan algoritmu huwa tabilħaqq kompluta. Issa, ejja tpoġġi isem fuq dan. L-algoritmu li nipproponi aħna biss implimentat huwa xi ħaġa imsejħa bużżieqa sort, magħrufa bħala tali fis-sens li -numri li huma xorta akbar ta ' bużżieqa mod tagħhom sal-quċċata, jew sa l-aħħar tal-firxa ta 'numri. Imma kif effiċjenti kien dan algoritmu? Kemm passi ħafna ma I fiżikament jkollhom jieħdu, per eżempju, biex issolvi dawn seba bnedmin? Erba 'sa ħames? OK, wisq hija finalment se tkun ir-risposta. Iżda anke dakinhar, in-numru speċifiku ma jkunx hekk interessanti. Ejja tiġġeneralizza bħala n. Mela jekk jien kienu n-nies up hawn, u dawn kienu, tip ta ', sabiex każwali fil- bidu, f'dik l-ordni oriġinali. Well, kemm passi ma I jkollhom li jieħu fuq l-ewwel pass? Kien wieħed, tnejn, tlieta, erba ', ħames, sitta, u dawn qed seba 'persuni, hekk li l-seba ', sitt -, b'tali mod li n nieqes waħda passi l-ewwel darba. Issa, kemm passi ma I jkollhom li jieħdu meta I rewound? Well, nistgħu attwalment doppju li jekk aħna verament riedu, iżda għal issa, jien biss se ngħid, id-dritt, n ieħor minus 1. Allura l-n minus 1 hija se tikseb annoying biex iżommu kont ta ', hekk ejja biss madwar up ftit. Allura 2n passi. Allura 14 passi, jagħtu jew jieħu. Kemm-il darba ma nieħu pass l-ħin li jmiss? Ukoll, huwa 3n. verament. U issa, fl-agħar każ, eżempju, kif ħafna drabi irrid marret quddiem u lura, u lura, eżekuzzjoni din algoritmu, jagħmlu skambju ta ' nies fuq kull pass, bejn wieħed u ieħor? Huwa fil-fatt n kwadrat, right? Minħabba fl-agħar każ, inti tista 'tip ta 'jaħsbu dwar dan intuwittivament, anki jekk jista 'jieħu ftit ftit ta 'żmien biex jinżel pulzieri Fl-agħar każ, liema kieku dawn seba 'persuni ħarsu simili, fil termini tal-arranġament ta 'numri tagħhom? Kompletament lura, id-dritt? U biss biex jissimulaw li, dak kien l-isem tiegħek mill-ġdid? MIKE: Mike. DAVID J. Malan: Mike? OK, Mike, inti biss tista jissieħbu miegħi fuq hawn għal waħda biss tieni? Attwalment, l-ebda. Jiddispjacini Mike, ejja kontrina. X'hemm isem tiegħek mill-ġdid? Neil Neil. DAVID J. Malan: Neil. OK, Neil, inti taqa 'bi me, jekk inti ma mind. Hekk jien ser tipproponi, biss għal sempliċità, li Neil issa hija fil tiegħu agħar każ possibbli. Imma jitfakkar kif I implimentati algoritmu tiegħi. Jien jqabbel, li jqabbel, li jqabbel, jitqabblu, li jqabbel, oh. Issa dawn guys huma barra ta 'ordni, so I jiffissaw. Allura inti guys tpartit. Iżda jikkunsidraw issa, kemm farther ma Neil jkollhom imorru? Huwa madwar n. You know, mhuwiex attwalment n. Huwa simili, n minus 1, imma jien jkollna imdejqa iżżomm rekord ta 'l-ftit numru, hekk ejja biss sejħa hija n. Mela jekk Neil jiċċaqlaq pass wieħed maximally kull żmien, u biex jimxu Neil pass wieħed, I jkollhom jagħmlu dan il-pass verament tedious quddiem u lura, dan huwa bejn wieħed u ieħor tagħmel dan, n passi, total ta 'n darbiet, minħabba li għaddej biex jieħdu me li ħafna passi biex tikseb Neil kollha l-mod biex fejn hu jappartjeni. Aħseb u ara kulħadd jekk inti guys kienu kollha mis-ordnati kif ukoll. Mela ejja sejħa bubble n sort kwadru. Il-running time ta 'dan algoritmu, il- prestazzjoni ta 'dan algoritmu, il- effiċjenza ta 'dan algoritmu, aħna għandu biss jiddeskrivu aktar ġeneralment bħala n kwadrat. Li huwa sbieħ, minħabba I tista 'tagħmel l- istess eżempju bi tmien persuni, disa nies, miljun ruħ, u li tweġiba mhux se jibdlu. Hekk jekk inti guys ma mind, ejja reset inti fejn bdejt. U ejja tipprova żewġ approċċi l-oħra u ara jekk aħna ma tistax tagħmel fundamentalment aħjar minn hekk. Allura dan iż-żmien, jien ser tipproponi tip ta 'algoritmu differenti. Dan kien ħafna għaqlija minna aħħar darba, u inti guys kienu dritt li jkollhom l- instincts dritt ta 'biss tip ta 'iskambji pairwise. Imma jekk jien verament riedu approċċ dan sempliċi, u l-għan tiegħi huwa li jiċċaqalqu kollha tal-numri ftit il-mod, u imbotta kollha tan-numri kbar li mod, għaliex ma I biss tagħmel dan fil- aktar naive mod possibbli u ara jekk I tista 'tagħmel aħjar minn dak li kien a pjuttost algoritmu kumpless? Mela ejja ara. Erba huwa numru pjuttost żgħir, hekk jien ser tħallik hemm mument. Ooh, numru tnejn huwa anki aħjar. Allura tista 'biss pass' il quddiem għal mument? Dan huwa attwalment numru iżgħar tiegħi kandidat, u jien ser tiftakar li ma, bħal, varjabbli. Imma jien ser żżomm kontroll. Hemm xi ħadd li in-numru huwa iżgħar? Sitta, l-ebda. Oh, hemm Neil ġdid. Hekk jien ser push inti lura tip ta 'kunċettwalment. Neil se tressaq. U issa, il-varjabbli li jien jużaw biex jżommu rekord ta 'min għandu l-iżgħar numru hija aġġornata biex tinkludi Post Neil. Well, ejja ara. Tliet, seba ', ħames. OK, I know Neil kien l-iżgħar. X'hemm-ħaġa sempliċi għalija li tagħmel issa? Jien ma jmur l-iskart ħin tiegħi bi ftit tbaqbieq Neil wieħed spot lejn ix-xellug. Għaliex ma I biss jitqiegħed Neil fejn hu jappartjeni, li naturalment huwa fejn? It-triq kollha fil-bidu. Allura Neil, come miegħi. U dak kien l-isem tiegħek mill-ġdid? GRACE: Grace. DAVID J. Malan: Grace. OK. Allura Grace, sfortunatament, int tip ta 'fil-mod. Allura kif nistgħu issolvi din il-problema? Dritt? Jekk dan huwa firxa, hemm biss seba 'postijiet. Ifakkar li, bil Rob, tkellimna dwar tiddikjara etajiet, u aħna biss kellhom numru finit ta 'etajiet? Istess idea hawn. Aħna biss numru finit ta 'ints. Grace huwa tip ta fil tagħna mod, hekk kif nistgħu jiffissaw? L-eħfef mod huwa simili, Grace, sorry. Int ser ikollok tmur fuq hemm hekk nistgħu nagħmlu kamra. Issa, jekk taħseb dwar dan, forsi aħna biss għamel il-problema agħar. U forsi għamilna, għaliex dak li jekk Grace kienu fil-post it-tajjeb? Imma nafu hi li ma, għaliex mod ieħor, kienet tkun wieqfa quddiem minflok Neil f'dan iż-żmien, id-dritt? Aħna diġà ċċekkjati numru tagħha out. Kull dritt. Allura issa, Neil fil-post it-tajjeb, u I tista 'tagħmel ottimizzazzjoni żgħira. Għall-minuta li jmiss, jien ser jinjora Neil kollha flimkien, sabiex ma jaħlux ħin tiegħu, jew aċċidentalment tpartit lilu għall-post żbaljat. Allura issa, kif nista 'nsib li jmiss element li l-iżgħar? Tnejn. Li numru pjuttost tajba, jekk inti tixtieq li pass 'il quddiem u I ser ftakar li inti. Sitta, l-ebda tajba. Erba, tlieta, seba ', ħames, mhux tajba. So let me jimxu inti post dritt tiegħek. U aħna biss ltqajna xxurtjati dan iż-żmien. Issa, jien ser jinjora dawn żewġ guys, u issa jagħmlu waħda aktar jgħaddu dan. Sitta, li numru żgħir pretty. Come fuq quddiem. Oh, sorry. Numru Grace huwa aħjar, hekk pass fuq quddiem. Erbgħa. Jiddispjacini, Grace. Mur lura. Numru tlieta huwa aħjar. Seven. Ħamsa. U issa dak l-isem tiegħek mill-ġdid? JASON: Jason. DAVID J. Malan: Jason. Allura Jason issa huwa l-iżgħar element stajt magħżula. Fejn huwa hu se jmorru? Għalhekk, fejn huwa sitta. U l-isem tiegħek hija għal darb'oħra? Gabe: Gabe. DAVID J. Malan: Gabe. Gabe huwa fil-mod. X'hemm-eħfef ħaġa li tagħmel? Tpartit dawn iż-żewġ guys u tkompli. Allura issa ejja ara. Min hu l-iżgħar? Erbgħa. Let me biss tip ta 'iqarrqu. Ta 'ħames se tkun l-iżgħar. I isibu li jmiss, jekk, inti tixtieq li pass quddiem, x'għandi nagħmel għandhom x'jaqsmu ma ' dawn guys, bl Gabe? Tpartit mill-ġdid. Allura issa, għadu ftit out of order. I sabet Gabe l-iżgħar, so I pop lilu out, inti timxi guys fuq. U jsir. Allura tweġiba hija l-istess. Ir-riżultat aħħari huwa l-istess. Liema minn dawn iż-żewġ algoritmi hija aħjar? It-tieni waħda, I jinstemgħu. Għaliex? SPEAKER 3: Huwa n-passi [inaudible]. DAVID J. Malan: Huwa passi n-iktar tard. Interessanti. Allura huwa għalkemm? Allura kif ma nsib l- element iżgħar? Kemm passi ħafna ma I għandhom jieħdu isibu l-iżgħar element? I kellhom ħarsa-triq kollha fl-aħħar, id-dritt? Għaliex f'dak agħar każ, liema jekk Neil kienu aktar hawn? Hekk biss konstatazzjoni tal-iżgħar element jieħu me n passi, jew minus 1 n. Iżda, OK. Allura jiffissaw Neil. Ftakar li, minuta jew hekk ilu. Imma kif ma nsib li jmiss element iżgħar? Huwa n minus 1, jew n minus 2 tassew, min-numru ta 'passi. Allura OK. So I ma n minus 2. Kull dritt. Allura li jħoss ftit aħjar. Kull dritt. Kemm passi l-ħin li jmiss issib numru tlieta? Allura n minus 4. Allura huwa jonqos, wieħed inqas pass fuq kull iterazzjoni. Allura dan ma tħossok aħjar, id-dritt? Jekk l-aħħar darba kien madwar n ħinijiet n, din id-darba n minus 1, plus minus n 2, plus minus n 3, plus n minus 4, dot, dot, dot. Imma jekk inti recall mill-iskola għolja tiegħek kotba, l-iqarrqu ftit sheet fid-dahar li għandu formuli, jekk inti żid up din is-serje ta 'numri, liema huwa l-għadd totali ta 'passi se tkun li nieħu hawn? Din hija waħda minn dawk, simili, n minus 1, il-ħinijiet n, diviż 2. So let me ara jekk I jistgħu jiġbdu dan up għal ftit mument. U għal darb'oħra, jien tip ta 'arrotondament f'xi numri biss biex iżommu sempliċi ħajja tagħna, iżda bħala I recall, huwa xi ħaġa simili jekk I do n minus 1-affarijiet, allura n minus 2, allura n minus 3, huwa bejn wieħed u ieħor xi ħaġa bħal din aktar minn 2, u jekk I immoltiplika dan out, li attwalment n kwadru. Li ma tħossok wisq tajbin. n minus n aktar minn 2. Iżda hawn l-ħaġa. Fix-xjenza tal-kompjuter, meta l-problemi tibda tikseb interessanti huwa meta n gets verament kbir. U meta n gets verament kbira, li ta ' dawn il-valuri se jiddominaw kollha mill-oħrajn? Huwa tip ta 'n kwadrat, right? Iva, jiġi diviż bi 2 hija pjuttost tajba. Imma jekk inti qed jitkellem dwar biljuni ta 'biċċiet ta' data, jew triljuni ta ' biċċiet ta 'data, Ok, sabiex int darbtejn aktar malajr. Imma li verament jimpurtah jekk dak in-numru kbir, jekk dan il-fattur huwa dak gets akbar u akbar. U żgur, jagħmel aktar ta ' differenza minn dan Guy. Allura anke jekk inti guys huma dritt, il- tieni algoritmu, aħna ser sejħa hija sort għażla, hija, fid-dinja reali, a bit malajr potenzjalment, minħabba I am tieħu anqas u anqas passi kull darba. Mhuwiex verament fundamentalment aktar malajr. Għaliex jekk aħna fil-fatt play dan out għal valuri kbar ta 'n, fl-aħħar ta' il-jum, għal n kbir biżżejjed, huwa għadu se jħossu pretty bil-mod. Well, let me tieħu waħda jgħaddi l-aħħar f'dak. Dan huwa dak I call sort għażla. Tista guys reset yourselves aħħar darba? U f'dan il-aħħar każ, jien ser li tipproponi xi ħaġa imsejħa sort inserzjoni. Sort Inserzjoni tkun, kunċettwalment, daqsxejn differenti. Pjuttost milli jmorru quddiem u lura u għażla tal-iżgħar element, jien biss jmorru biex jittrattaw ma 'kull wieħed minn dawn guys kif I jiltaqgħu magħhom, u daħħal minnhom fil-post korretta tagħhom. Hekk jien biss ser tibda bil Grace, u nara li hi numru erbgħa. Fejn ma numru erbgħa jappartjenu? I ma bdew issortjar xejn, hekk Grace gets li tissospendi hemm dritt. U issa jien ser jitolbu, jekk inti tista ' tieħu pass għal-lemin tiegħek, dan lista magħżula tiegħi, dan huwa tiegħi lista li jifdal mhux magħżul. Allura issa jien ser tipproċedi jmiss, u dak l-isem tiegħek mill-ġdid? BRANSON: Branson. DAVID J. Malan: Branson. Allura Branson huwa numru żewġ. Hekk jien ser tieħu inti out għal mument. U issa, fejn do inti jappartjenu f'dan firxa? Allura għad-dritt ta Grace. Għalhekk għal darb'oħra, aħna qed tip ta 'teħid Grace jagħmlu ħafna xogħol hawnhekk. Fejn nistgħu tpoġġi lilek? Allura aħna qed tmur biex slide inti l- xellug, u daħħal Branson hemmhekk. Imma issa I jsostnu li inti guys qed isir. Imma avviż, jien ma jużaw spazju żejjed. Huwa għadu 2 elementi hawn, 5 hawn fuq. Daqs l-array totali huwa 7, hekk jien mhux qerq, id-dritt? Allura issa għandna, ma Gabe hawn, il- numru sitta, fejn do inti jappartjenu? You ltqajna xxurtjati darb'oħra. Allura ikollok li tissospendi hemm dritt. Just tieħu pass żgħir lejn il-lemin biss biex jagħmilha ċara li int magħżula. U issa għandna Neil darb'oħra, numru wieħed, fejn ma tmur? U issa huwa fejn aħna ser tibda tara li dan algoritmu, għalkemm fuq l-ewwel daqqa t'għajn, iħoss pretty intelliġenti, watch x'hemm sejjer iseħħ. Jekk inti tista 'pass' il quddiem. Fejn irridu li tqiegħed Neil? Allura ovvjament hawnhekk, hekk kif nilħqu Neil hemmhekk? Ejja nagħmlu dan il-pass-pass. Gabe, fejn għandek bżonn biex tmur? Yep, sabiex jieħdu pass wieħed kbir, jew żewġ nofs passi biex jagħmlu pass wieħed hemmhekk. Grace, fejn inti tmur? Tajba. Allura pass ieħor. U fl-aħħarnett, Branson? Pass ieħor. U issa nistgħu npoġġu Neil fis-seħħ. Allura issa, ikomplu din il-loġika. Anki jekk aħna mhux ċaqliq Neil fuq, u aktar, u aktar, li jniżżlu fejn imur, fl-agħar każ, il- numru li jmiss nistgħu jiltaqgħu jistgħu jkun in-numru, ngħidu aħna, kien hemm numru żero, allura aħna qed tmur li ċċaqlaq kollha dawn guys. Ejja ngħidu li hemm numru, negattiv waħda, allura għandna għall-bidla kollha ta 'dawn guys. Allura aħna qed verament biss tip ta 'flipping il-problema madwar, bħal li aħna qed jittrasferixxi l-ispiża mill- proċess ta 'għażla sabiex l-inserzjoni proċess, b'tali mod li inti guys biss kellhom jimxu madwar n minus xi ħaġa numru ta 'passi. U dak in-numru ta 'passi huwa biss se jiżdied hekk kif I jagħżlu numri aktar, jekk I għandhom iżommu shoving inti guys lura, u lura, u lura. Allura l-ħaġa diqa hija issa kollha ta 'dawn algoritmi huma n kwadru. Ejja imorru quddiem u grazzi għal dawn guys, u Ħares dawn daqsxejn differenti. Ħafna isir ukoll. [Applause] Kull dritt. Hemm inti tmur. Grazzi għall - BRANSON: [inaudible] jżomm in-numri. DAVID J. Malan: Le, inti tista ' iżommu n-numri kif ukoll. Kull dritt. Nicely jsir. Kull dritt. Mela ejja ara jekk ma nkunux nistgħu issa tqassar aktar malajr, u aktar viżwalment, eżattament dak li ġara biss hawn kif ġej. Jien ser jimxi 'l quddiem u iġbed up Firefox. Aħna ser jorbot dan dimostrazzjoni fuq il-websajt il-kors tal. Java huwa daqsxejn tedjanti biex tikseb xogħol f'xi browsers dawn il-jiem. Mela jekk inti play ma 'dan fid-dar, tirrealizza jista 'jkollok bżonn biex jużaw Firefox biex tiksbu tax-xogħol. U dak li jien ser tagħmel ma 'dan dimostrazzjoni huma dawn li ġejjin. Fil-qiegħ, I jkollhom mazz sħiħ ta ' għażliet menu, inkluż bidu u stop buttuna. Wkoll, bħala twarrib, jidher li jkun bug f'dawn il-programmi, fejn inti ma tistax attwalment ara l-bidu jew tieqaf buttuna sakemm inti żżomm Kmand jew Alt plus u zoom fi, li curiously jurik buttuni aktar. Hekk biss FYI jekk inti play ma 'dan fid-dar. Issa jien ser ikklikkja Start fi ftit mument, wara li jispeċifikaw dewmien ta ', simili, 200 millisekondi hawn, just hekk nistgħu naraw x'jiġri. So I jsostnu li dan huwa viżwalizzazzjoni ta 'l-ewwel algoritmu dawn guys ma, sort bubble, fejn aħna biddlu nies par għaqli. L-għarfien ċavetta għal din viżwalizzazzjoni huwa li l-għoli tal-bars tirrappreżenta d-daqs tan-numru. Allura l-taller l-bar, il- akbar in-numru. Iqsar l-bar, iżgħar in-numru. U jekk tinnota, aħna qed tmur permezz l-ewwel iterazzjoni ta 'dan algoritmu, iskambji numri kbar u żgħar, sabiex in-numru żgħir jiġi l-ewwel u in-numru kbir imur lejn il-lemin. U hekk kif aħna jiksbu l-aħħar ta 'firxa ta 'ħafna aktar minn seba' numri, aħna qed se jmorru lura għall-bidu. U jantiċipaw dan. Fuq ix-xellug, li Guy ftit għaddej tpartit għall-ġenb, u dan jirrepeti proċess. Issa dan viżwalizzazzjoni malajr gets boring, so let me imorru quddiem u stop dan, jibdlu l-ħaġa wisq dewmien aktar mgħaġġel biss li tikseb issa, jħossu għal dan algoritmu. Allura anke jekk stajt titħaffef it up, dan huwa bħal titjib proċessur tiegħi, ix-xiri kompjuter ġdid. I ma nbidlux fundamentalment tiegħi algoritmu, imma int tista 'tabilħaqq tara aktar ċar milli mal-bnedmin, li l-big in-numri huma tbaqbieq sal-quċċata, u n-numri żgħar huma tbaqbieq sal-qiegħ. U issa dan il-ħaġa hawn magħżula. U bħala twarrib, fil-pjazez, hemm biss ftit bookkeeping hemm biex jgħinu inti għadd kemm paraguni, jew kif ħafna swaps għandhom attwalment sar. Well, ejja ipprova wieħed ta ' l-oħrajn rajna. Let me ikklikkja fuq tip bużżieqa hawn, u let me jagħżlu, u din il-paġna web kollu huwa Buggy ftit. Ejja taċċetta r-riskju u run mill-ġdid. Hemm immorru. Mela ejja jagħmlu sort għażla. I do not know għaliex il-menu jidher hemmhekk. Ejja zoom fl biex jiffissaw dak bug, tbiddel dan sa 50. Ah, ejja fil-fatt jagħmlu li ħafna aktar mgħaġġla. Ħames millisekondi jew hekk, u tibda. Allura dan huwa tip għażla. Għalhekk għal darb'oħra, jaħsbu dwar dak li aħna għamlet mal-bnedmin up hawn. Aħna marru permezz tal-firxa u magħżula l-iżgħar element ġdid, u għal darb'oħra, u għal darb'oħra. Now I jsostnu li kien għadu pretty bad. Kien għadu n kwadrat, jagħtu jew jieħu, imma kien, fid-dinja reali, daqsxejn aktar malajr, minħabba I kien tabilħaqq tieħu kemmxejn inqas passi kull darba. Iżda aħna qed jitkellem biss dak? Forsi 40 jew hekk bars hawn? Aħna ma jitkellem 40 miljun. Allura mhuwiex totalment ċar għalija li kienet tabilħaqq żieda sinjifikanti. Let me issa jmorru lura u l-bidla għal tagħna tielet algoritmu, li kien tagħżel sort inserzjoni. U issa huwa verament Buggy minħabba li l- menu verament ma għandu jkun hemm isfel. Allura issa aħna ser iscroll back up here u tibda dan algoritmu. Konvulżjonijiet, startjar u waqfien. Allura dan it-tip wieħed ta ikollu mudell pretty lilha, fejn aħna napprovaw qed jiddaħħlu l-bnedmin, jew F'dan il-każ, il-bars fis post xieraq tagħhom. U huwa diġà sar qabel I daru madwar. Iżda dan wieħed, wisq, fit-teorija, għadu n kwadru. Mela ejja ara jekk ma nkunux nistgħu tqassar dawn kif ġej. Jien ser imorru quddiem u biss biex tagħti us tip ta 'mod komuni ta' titkellem dwar dawn l-affarijiet, let me jintroduċu biss daqsxejn ta 'notazzjoni hawn. Int ser tara xi ħaġa imsejħa big O, minħabba li huwa litteralment a big O. U dan huwa mod li l-kompjuter xjentist jew matematiku anke juża biex jiddeskrivu l-running time ta 'xi algoritmu. Kif passi ħafna ma attwalment jieħdu? Issa jien ser jimbarazza myself ma ' kalligrafija tiegħi hawn fi ftit mument. Iżda let me imorru quddiem u jgħidu li dan se jkun kbir O hawn fuq. U let me jintroduċu waħda oħra simbolu, a omega kapital. Omega se tkun l-oppost, essenzjalment, ta 'big O. Billi big O mezzi, fl-agħar każ, kemm ħin jista xi algoritmu jieħu, fir- f'termini ta 'n, omega se jkun kemm ħin jista 'dan tieħu fil-każ aħjar. U aħna ser tara dak li jfisser minn aħjar każ fi ftit mument. Mela ejja nibdew xi ħaġa sempliċi. Nibda ma 'tfittxija lineari. Allura mhux issortjar. Aħna ser sejħa dan tfittxija lineari. U issa, jagħmlu ftit tabella barra ta 'dan. U issa, fil-każ tat-tfittxija lineari, fl-agħar każ, kemm passi huwa Huwa ser jieħu me biex isibu numru ta 'għażla arbitrarja? U hemm bibien totali n jew n-numri totali. L-agħar każ. Kemm passi ħafna jien ser ikollhom jieħdu biex issib in-numru 50 fil-firxa ta 'bibien n? U għaliex? Minħabba li jista 'jkun l- mod fuq fuq l-aħħar. Tant simili Jennifer ltaqgħu magħhom, l- numru 50 kienet it-triq kollha madwar, hekk l-agħar każ tfittxija lineari huwa big O ta 'n, aħna ser ngħidu. Xi ngħidu dwar l-aħjar każ, jekk ikollok verament xxurtjati? Huwa biss ser jieħdu pass wieħed, jew numru ta 'passi kostanti. Allura aħna ser jiddeskrivu li bħala 1. Allura dan huwa pjuttost tajba. Issa dak li jekk aħna ma xi ħaġa bħal tfittxija binarja? Tfittxija Allura binarju, fl-agħar każ, ħa kemm ħin? [INTERPOSING VUĊI] DAVID J. Malan: So attwalment, I smajtu fi postijiet koppja. Allura huwa attwalment log n, jagħtu jew jieħu, għaliex kif aħna jaqsam il-lista fil nofs għal darb'oħra, u għal darb'oħra, u għal darb'oħra, aħna qed kapaċi biex isibu, finalment, il-valur, jekk huwa hemmhekk, iżda hemm qabda. X'hemm-suppożizzjoni li rridu jieħdu għal mogħtija għat-tiftix binarju? Għandu jiġi magħżul. Mhuwiex magħżula, inti tista 'taqsam il-ħaġa fil nofs mill-ġdid u għal darb'oħra, u għandek tista 'tmur xellug, u inti tista' tmur dritt, u inti tista 'tmur xellug u lemin, imma int mhux ser isibu l-element jekk il-lista mhix magħżula, minħabba inti tista 'titlef dan. Minħabba heuristic tiegħek, biex imur xellug jew dritt se tkun difettuż jekk huwa tabilħaqq jkunux magħżula. Allura hemm tip ta 'spiża moħbija għall-użu xi ħaġa bħal din. Issa, ejja jmorru fil issortjar tagħna algoritmi ma jistgħux tiftix - oh, fil-fatt ejja imorru f'dan vojt. Tfittxija Binarju fl-aħjar każ? Huwa wkoll 1 jekk hija biss jiġri li jkun fin-nofs ħafna mill-firxa, jew -nofs tal-ktieb tat-telefon. Issa ejja jagħmlu sort bubble. Għalhekk għal darb'oħra, issa aħna qed jidħlu fil- xorta, mhux il-tfittxijiet. Fl-agħar każ, kemm-passi ma we talba bubble sort għaddej biex tieħu? n kwadrat. Hekk jien ser tiġbed dan. Ooh, kalligrafija tiegħi jistenna saħansitra agħar meta huwa proġettat li big. Kull dritt. Allura thats n kwadru. U fl-aħjar każ ta 'tip bużżieqa, kemm passi huwa se tieħu? 1, I jinstemgħu. SPEAKER 1: n. DAVID J. Malan: n, I jinstemgħu. SPEAKER 1: 2. DAVID J. Malan: 2, smajt. Do Nisma 3? Kull dritt. So I widnejna 1, n, 2, imma ejja pick apparti mill-inqas l-ewwel ta 'dawk suġġerimenti, 1. Mhuwiex istint ħażin, għaliex tip ta 'ssegwi mudell hawn. Iżda jekk hija tieħu biss 1 pass, kif fid- dinja jista I jsostnu li l-lista huwa magħżul, għaliex jekk jien permess biss li tieħu pass 1, kemm elementi jista I attwalment jivverifika sabiex ikun żgur? Well, just 1, li jfisser li hemm n minus 1 elementi li jistgħu jkunu wkoll ta ' ordni, u jien biss jmorru fuq il-fidi wara tħares lejn 1 element li l- Ħaġa huwa magħżul. Allura 1 mhuwiex korrett hawnhekk. Allura minimament, kemm għandi tħares lejn? [INTERPOSING VUĊI] DAVID J. Malan: n minus 1, jew verament, n, minħabba I bżonn tħares lejn kull element biex tiżgura li mhuwiex out of order. Iżda għal darb'oħra, aħna ser issolvi ta 'mewġa tagħna idejn fil-numri iżgħar u jassumi li, bħala n gets kbar, dawn qed uninteresting xorta waħda. Allura dak it-tip bubble. U issa, ejja tagħmel dawn l-aħħar tnejn. Sort għażla, u mbagħad aħna ser jagħmlu sort inserzjoni. U allura aħna se blow tiegħek imħuħ ma 'xi ħaġa ferm aħjar minn kollha ta 'dawn. Kull dritt. X'inhu l-agħar każ running ħin ta 'tip-għażla? SPEAKER 4: n kwadru. DAVID J. Malan: n kwadru, jien seduta. Iżda għaliex n kwadrat, intuwittivament? SPEAKER 4: Għaliex aħna biss ma kien. DAVID J. Malan: Għaliex aħna biss ma kien. OK. Tweġiba tajba. Iżda intuwittivament, għaliex hija għażla sort n kwadrat? What did għandna nagħmlu ġdid u għal darb'oħra? Kellna biex iżommu scanning permezz, huma inti l-iżgħar, inti l- iżgħar, inti l-iżgħar. U mogħtija, konna kapaċi jieħdu n passi, allura n nieqes 1, allura n minus 2. Imma jekk inti-tip ta 'żżid dawk kollha up, jew teħodha fuq il-fidi li stajt miżjud lilhom minn qabel, irridu jiksbu madwar n kwadrat minus xi numri iżgħar. Hekk jien ser sejħa dan n kwadru. Iżda ma sort għażla fl-aħjar każ, kemm passi huwa ser tieħu me? SPEAKER 5: [inaudible] DAVID J. Malan: Huwa sfortunatament xorta n kwadrat, right? Għaliex jekk jien jintgħażlu l-iżgħar element, u kellna seba 'persuni hawn, I biss jafu, ladarba I jiksbu l-ħafna għan, li stajt sabu l-iżgħar numru, kull fejn hu jew hi setgħu kienu. Imma kif nista 'nsib li jmiss iżgħar numru? I għandek tagħmel pass ieħor. Allura fl-aħjar każ, liema huwa l- input li sort għażla? Huwa ta 'lista tip diġà, numru wieħed, numru tnejn, numru tlieta, numru erbgħa. Imma jien kompjuter. I tista 'tħares biss lejn wieħed ħaġa fi żmien. I ma tistax issolvi ta jittieħed pass lura bħal bniedem u jgħidu, ooh, dan jistenna korretta. I tista 'biss tiddeċiedi korrettezza fl sort għażla billi tagħżel il- iżgħar numru. Iżda anke jekk nsib numru wieħed ewwel, jekk jien ma nafx xi ħaġa oħra dwar n-numri l-oħra, li jien ma, I kollha jafu li stajt ġiet mogħtija array jew sett ta 'bibien wara li huma numri, l-uniku mod Naf li wieħed kien l-iżgħar? Jekk niġi-triq kollha hawn u jirrealizzaw, kkritikat, wieħed kien tabilħaqq l-iżgħar. Imma kif nista mbagħad tiddetermina li tnejn huwa l-iżgħar li jmiss? Billi tagħmel l-istess ineffiċjenza ġdid u għal darb'oħra. Allura finalment, ma sort inserzjoni, kif, fl-agħar każ, ma ngħidu li jwettaq? Huwa wisq huwa n kwadru. U kif madwar bl-aħjar każ? Aħna ser tħalli li bħala cliffhanger. Aħna ser timla dak iż-żmien li jmiss vojta, imma l-ewwel let me tipproponi li aħna fundamentalment do aħjar minn kollha ta 'dawn, id-dritt? Allura taħseb għalik innifsek dak inserzjoni sort għaddej biex tkun. Ukoll, li ma kienx drammatiku ħafna, għaliex jien l-unika waħda li raw il-bidla. Ara naqra. OK. Allura hawnhekk għandna kemmxejn dimostrazzjoni differenti. Jekk I zoom fil hawn, tkun taf tara li fuq ix-xellug għandna sort bużżieqa, fil- nofs għandna sort għażla, u fuq -lemin, għandna xi ħaġa li aħna ma jkunux ħarsu lejn għadhom imsejħa jingħaqdu tip. Iżda jikkunsidraw dak li aħna kont qed tagħmel hawn s'issa illum. Meta Jennifer ewwel daħal up fuq il-palk, aħna marru permezz tal-firxa ta 'numri għal darb'oħra, u għal darb'oħra, bil-tfittxija lineari, u aħna ltqajna running time lineari, big O ta 'n, biex ngħidu hekk. Meta aħna issa tikkunsidra l-ewwel ġimgħa ta ' klassi, meta kellna jaqsam u jirbħu, u kellna l-ktieb tat-telefon dmugħ, u Jennifer, u aħna kollettivament leveraged li ħarsa ewlenin, li kellha jirrepetu yourself darb'oħra u għal darb'oħra mill b'xi tarmi, jitfg bogħod, tarmi, nofs il-problema, jew ġeneralment, jiġi diviż problema fil nofs, u mbagħad wieħed jittratta l-biċċa iżgħar ta ' il-problema bħala kunċettwalment ekwivalenti għall-ieħor, aħna b'xi mod ma fundamentalment aħjar. Iżda ma sort bużżieqa, bl-għażla sort, ma sort inserzjoni, konna jista ebda għarfien bħal dak Jennifer għamlet. Aħna pretty ħafna biss mixi lura u raba mazz sħiħ ta 'drabi, u aħna affarijiet tweaked ftit, jagħmlu skambju ta ' f'din l-ordni, forsi jinserixxi jew għażla. Iżda fl-aħħar tal-ġurnata, Jien għamilt ħafna ta 'mixi skomdi u lura. Aħna ma verament lieva xi ħaġa smart bħal Jennifer ma tixtieq tiddividi u conquering. Allura jingħaqdu sort, b'kuntrast, li aħna mhux se tara sal-ġimgħa d-dieħla, li għaddej biex ingranaġġ li idea ewlenija billi tiddividi l-input, u mbagħad tnaqqis bin-nofs, u mbagħad tnaqqis bin-nofs, u mbagħad tnaqqis bin-nofs. U fuq kull iterazzjoni ta 'dak loop, issortjar in-nofs xellugi, u d-dritt nofs, allura l-nofs tax-xellug ta 'nofs tax-xellug, u l-nofs tal-lemin ta 'fuq ix-xellug, imbagħad in-nofs xellugi tal-nofs tal-lemin, u il-nofs tal-lemin ta 'l-nofs tal-lemin. U jirrepeti ġdid u għal darb'oħra. Sabiex tkun taf tara dan viżwalment, iżda dan huwa dak li jistenna minna ġimgħa d-dieħla. U b'mod ġenerali, meta naħsbu ftit daqsxejn aktar diffiċli fuq kull problema simili. Aħna n-kwadrat fuq ix-xellug n kwadrat fin-nofs, u n log n fuq il-lemin. Allura hemm cliffhanger reali tiegħek. Aħna ser tara inti nhar it-Tnejn. [Applause]