[Daqq tal-mużika] DAVID Malan: Kull dritt. Kull dritt, welcome lura. Allura dan huwa Ġimgħa 4, il-bidu tiegħu, diġà. U inti ser tfakkar li l-aħħar ġimgħa, npoġġux kodiċi riservati għall biss ftit u bdejna nitkellmu ftit aktar ta 'livell għoli, dwar affarijiet bħal tiftix u għażla, li għalkemm ideat pjuttost sempliċi, huma rappreżentant ta 'klassi ta' problemi inti se tibda biex isolvu partikolarment kif inti tibda taħseb dwar finali proġetti u soluzzjonijiet interessanti inti jista 'jkollok problemi tad-dinja reali. Issa tip bużżieqa kienet waħda mill-aktar sempliċi bħal algoritmi, u maħduma billi dawn in-numri żgħar f'lista jew fil-firxa tip ta ' bużżieqa mod tagħhom sal-quċċata, u l- numri kbar jimxu mod tagħhom sa l-aħħar ta 'dik il-lista. U tfakkar li nistgħu Ħares bubble sort ftit xi ħaġa bħal din. So let me go quddiem u kklikkja Bidu. Stajt magħżula minn qabel sort bubble. U jekk inti recall li l-blu taller linji jirrappreżentaw numri kbar, żgħar linji blu jirrappreżentaw numri żgħar, kif aħna jgħaddu din darb'oħra u għal darb'oħra u għal darb'oħra, li jqabbel żewġ bars wieħed ħdejn l- oħra bl-aħmar, aħna qed tmur biex tpartit l- akbar u l-iżgħar jekk huma out of order. Allura dan se jmorru fuq u jmorru fuq u jmorru fuq, u tkun taf tara li l-akbar Elementi qed jagħmlu triqthom lejn il- dritt, u l-elementi iżgħar huma jagħmlu mod tagħhom lejn ix-xellug. Iżda aħna bdew jikkwantifikaw l-effiċjenza, l- kwalità ta 'dan algoritmu. U aħna qal li fl-agħar każ, dan algoritmu ħa bejn wieħed u ieħor kemm-passi? Allura n kwadru. U dak li kien n? UDJENZA: Numru ta 'elementi. DAVID Malan: Allura n kienet l- numru ta 'elementi. U hekk aħna ser jagħmlu dan ta 'spiss. Kwalunkwe ħin rridu nitkellmu dwar id-daqs ta 'problema jew id-daqs ta' input, jew l-ammont ta 'ħin li tieħu biex jipprovdi produzzjoni, aħna ser biss tkun xi tkun ġeneralizzata l-input huwa kif n. Allura lura fil-Ġimgħa 0, paġni l-għadd fil-ktieb tat-telefon kien n. In-numru ta 'studenti fil-kamra kienet n. Allura hawnhekk, wisq, aħna qed wara dak il-mudell. Issa n kwadrat mhuwiex partikolarment fast, hekk aħna ppruvaw li naħdmu aħjar. U hekk aħna ħares lejn koppja ta ' algoritmi oħra, fosthom kienu sort għażla. Allura sort għażla kienet ftit differenti. Kien kważi sempliċi, I DARE ngħid, fejn I bdiet fil-bidu tal- lista ta 'voluntiera tagħna u I biss darb'oħra u għal darb'oħra u għal darb'oħra marru permezz il-lista, tnittif l-iżgħar element fi żmien u jniżżlu jew tagħha fil-bidu tal-lista. Iżda dan, wisq, ladarba aħna bdew jaħsbu permezz tal-matematika u akbar stampa, ħsibt dwar kif ħafna drabi I kien għaddej quddiem u lura u lura u lura, għidna fl-agħar każ, sort għażla, wisq, kien dak? n kwadrat. Issa fid-dinja reali, dan jista 'jkun fil-fatt tkun marġinalment aktar mgħaġġel. Minħabba darb'oħra, I ma għandhomx iżommu treġġigħ lura darba I kien magħżula l- elementi iżgħar. Imma jekk naħsbu dwar n kbir ħafna, u jekk inti tagħmel tip ta 'l-matematika bħala Jien għamilt fuq il-bord, bl-kwadrat n xi ħaġa minus, kollox minbarra n kwadrat, ladarba n gets verament kbir, ma verament kwistjoni kemm. Sabiex xjenzjati tal-kompjuter, aħna sort ta ' jagħlqu għajnejhom għall-iżgħar fatturi u tiffoka biss fuq il-fattur fil- espressjoni li għaddej biex jagħmlu l-akbar differenza. Ukoll, fl-aħħar, ħarisna fil sort inserzjoni. U dan kien simili fl-ispirtu, imma pjuttost milli jgħaddu iteratively u jagħżlu l-iżgħar element wieħed fi time, I minflok ħa l-idejn li I ġiet ittrattata, u I iddeċieda, kollha dritt, inti jappartjenu hawn. Imbagħad mort fuq l-element li jmiss u ddeċieda li hu jew hi ikkontrollata hawn. U mbagħad I mċaqalqa fuq u fuq. U jien jista lill, tul it-triq, shift dawn guys sabiex tagħmel spazju għalihom. Allura li kien tip ta 'l-inverżjoni mentali ta 'tip għażla li aħna imsejħa sort inserzjoni. Allura dawn is-suġġetti li jseħħu fid-dinja reali. Just ftit snin ilu, meta ċertu senatur kien għaddej għall-president, Eric Schmidt, fil-mument l-CEO ta ' Google, fil-fatt kellhom l-opportunità għal intervista lilu. U ħsibna aħna'd jaqsmu din YouTube clip għalik hawn, jekk nistgħu dawran up il-volum. [Daqq video] -Issa, Senatur, int hawn fuq Google, u I simili biex jaħsbu tal-presidenza bħala intervista tax-xogħol. [Daħk] -Issa huwa diffiċli biex jiksbu xogħol bħala president. U int għaddejjin l-ħruxija issa. Huwa wkoll diffiċli li jsibu xogħol fil-Google. Għandna mistoqsijiet u aħna nitolbu mistoqsijiet lill-kandidati tagħna. U dan huwa wieħed mill Larry Schwimmer. [Daħk] You guys think-jien kidding? Huwa dritt hawn. X'inhu l-aktar mod effiċjenti biex sort miljun interi żewġ-bit? [Daħk] Well, uh - I'm sorry-. Forsi għandna - -No, no, no, no, no. -Li mhux - OK. -I think it-tip bużżieqa jkun il-mod żbaljat biex imorru. [Daħk] [Cheering U applause] -Come on, li qallu dan? OK. [Daqq video END] DAVID Malan: Allura hemm ikollok. Allura bdejna biex tikkwantifika dawn running drabi, biex ngħidu hekk, ma 'xi ħaġa imsejħa notazzjoni asintotiku, li hija biss li jirreferu għall tip tagħna ta 'tidwir għajnejhom għal dawk il-fatturi iżgħar u biss tħares lejn l-running time, l-prestazzjoni ta 'dawn algoritmi, bħala n gets verament kbir matul iż-żmien. U hekk aħna introdotti big O. U big O xi ħaġa rappreżentati li ħsibna ta bħala bound fuq. U fil-fatt, Barry, nistgħu ibaxxu mill-mic ftit? Ħsibna ta 'dan huwa marbut fuq. O daqshekk kbira ta 'n mezzi kwadrati li l-agħar każ, xi ħaġa bħal sort għażla se jieħu n passi kwadrati. Jew xi ħaġa bħal sort inserzjoni kieku passi kwadrati n. Issa għal xi ħaġa bħal inserzjoni sort, dak li kien l-agħar każ? Minħabba l-firxa, x'inhu l-agħar xenarju possibbli li inti tista 'ssib yourself jiffaċċjaw? Huwa kompletament lura, id-dritt? Għaliex jekk huwa kompletament lura, għandek tagħmel lott kollu ta 'xogħol. Għaliex jekk int kompletament lura, int ser issib il- element akbar hawnhekk, anki jekk jappartjeni stabbiliti hemmhekk. Allura int ser ngħid, id-dritt, fil- dan il-mument fil-ħin, inti jagħmlu parti minn hawn, sabiex inti jitilqu minnu biss. Imbagħad inti tirrealizza, oh, kkritikat, I jkollhom jimxu dan l-element kemmxejn iżgħar biex ix-xellug tal inti. Imbagħad I għandek tagħmel dan mill-ġdid u għal darb'oħra u għal darb'oħra. U jekk I mixi u lura, inti se sort tal jħossu l-prestazzjoni ta ' din l-algorithm minħabba kontinwament am I jsir ċaqliq kulħadd fid- array biex tagħmel spazju għal dan. Allura dak l-agħar każ. B'kuntrast - u dan kien cliffhanger aħħar darba - għidna li sort inserzjoni kien omega 'dak? X'hemm-running-aħjar każ ħin ta 'tip inserzjoni? Allura huwa attwalment n. Dan kien il-vojt li aħna xellug fuq il-bord aħħar darba. U huwa omega 'n għaliex għaliex? Ukoll, fl-aqwa każ, x'hemm sort inserzjoni se jingħataw? Well, lista thats kompletament magħżula diġà, xogħol minimu li tagħmel. Imma x'hemm pulita dwar sort inserzjoni hija li minħabba dan tibda hawn u jiddeċiedi, oh, inti huma n-numru waħda, inti jappartjenu hawn. Oh, dak fortuna tajba. Int l-għadd tnejn. You jagħmlu parti minn hawn. Numru tlieta, anki aħjar, inti jappartjenu hawn. Hekk kif jiġrilha l-aħħar tal- pseudocode lista, għal kull sort inserzjoni tal li aħna mixi permezz verbalment aħħar darba, dan isir. Iżda sort għażla, għall-kuntrarju, tinżamm tagħmel dak? Jinżammu għaddejjin permezz tal-lista ġdid u għal darb'oħra u għal darb'oħra. Minħabba l-għarfien ewlieni kien hemm biss ladarba inti stajt ħares-triq kollha lejn l- aħħar tal-lista tista 'tkun ċerta li l-element inti magħżula kienet tabilħaqq l-iżgħar bħalissa element. Allura dawn differenti mentali mudelli aħħar up jipproduċi xi ħafna reali tad-dinja differenzi għalina, kif ukoll dawn differenzi asintotika teoretiċi. Hekk biss biex terġa, imbagħad, big O ta 'n kwadrat, Rajna bħal ftit algoritmi s'issa. Big O ta 'n? X'hemm algoritmu li jistgħu jingħad li big O ta n? Fl-agħar każ, hija tieħu numru lineari ta 'passi. OK, tfittxija lineari. U fl-agħar każ, fejn huwa l- element li qed tfittex għal meta applikazzjoni tfittxija lineari? OK, fl-agħar każ, huwa lanqas hemm. Jew bit-tieni l-agħar każ, huwa it-triq kollha fl-aħħar, li hija plus-or-minus differenza pass wieħed. Għalhekk fl-aħħar tal-ġurnata, nistgħu ngħidu huwa lineari. Big O ta 'n ikun tfittxija lineari, minħabba fl-agħar każ, il- element mhux anki hemmhekk jew huwa it-triq kollha fl-aħħar. Ukoll, big O ta 'log ta' n. Aħna ma jitkellem fid-dettall kbir dwar dan, iżda Rajna dan qabel. Liema jibda fl-hekk imsejħa logaritmika żmien, fl-agħar każ? Yeah, search hekk binarja. U tfittxija binarja fl-agħar każ jista 'jkollhom l-element x'imkien -nofs, jew x'imkien ġewwa l-firxa. Imma inti biss jsibuha ladarba inti jaqsam il-lista fil nofs, fil- nofs, fil nofs, fil nofs. U mbagħad voila, huwa hemmhekk. Jew darb'oħra, agħar każ, huwa lanqas hemm. Imma inti ma taf li mhuwiex hemm sakemm inti tip ta 'jilħqu dak l-aħħar bottom-elementi l-aktar minn tnaqqis bin-nofs u tnaqqis bin-nofs u tnaqqas bin-nofs. Big O ta '1. Allura nistgħu big O ta '2, big O ta '3. Ghaċ inti tixtieq biss numru kostanti, aħna biss tip ta 'ftit jissimplifikaw li bħala big O ta '1. Anki jekk jekk realistikament, hija tieħu 2 jew saħansitra 100 passi, jekk huwa numru kostanti ta 'passi, aħna biss jgħidu O kbir ta '1. X'hemm algoritmu li l- fil big O ta '1? UDJENZA: Tfittxija-tul ta 'varjabbli. DAVID Malan: Sib l- tul ta 'varjabbli? UDJENZA: Le, it-tul jekk huwa diġà magħżula. DAVID Malan: Tajba. OK, sabiex tinstab it-tul ta 'xi ħaġa jekk it-tul ta 'li xi ħaġa, bħal firxa, hija maħżuna f'xi varjabbli. Għaliex inti tista 'biss taqra l-varjabbli, jew jistampaw il-varjabbli, jew biss ġeneralment aċċess dak il-varjabbli. U voila, li jieħu ż-żmien kostanti. B'kuntrast, think lura li tobrox. Think lura għall-ewwel ġimgħa ta 'C, ssejjaħ biss printf u l-istampar xi ħaġa fuq l-iskrin huwa probabbilment ħin kostanti, minħabba li biss tieħu xi numru ta 'ċikli CPU biex juru dak it-test fuq l-iskrin. Jew stenna - ma? Kif inkella tista we mudell l- prestazzjoni ta 'printf? Kieku xi ħadd tixtieq li ma jaqblux, li forsi mhuwiex żmien tassew kostanti? F'liema sens jista printf-ġirja żmien, fil-fatt istampar string fuq l-iskrin, tkun xi ħaġa minbarra kostanti. UDJENZA: [inaudible]. DAVID Malan: Yeah. Għalhekk jiddependi fuq il-perspettiva tagħna. Jekk għandna attwalment think tal-input li printf bħala l-sekwenza, u għalhekk aħna jitkejjel id-daqs ta 'dak input skond it-tul tagħha - so ejja sejħa li tul un kif ukoll - forsi, printf innifsu O kbira ta 'n minħabba li għaddej biex tieħu inti n passi li jistampa kull wieħed minn dawn n karattri, aktar probabbli. Mill-inqas sal-punt li aħna nassumu li forsi huwa għall-użu ta 'loop taħt il-barnuża. Imma rridu naraw li tħares lejn dak kodiċi jifhmu aħjar. U fil-fatt, ladarba inti guys tibda analiżi algoritmi tiegħek, inti ser litteralment tagħmel dan. Sort ta boċċa kodiċi tiegħek u think dwar - id-dritt, I jkollhom din loop hawn jew għandi loops nested hawn, li għaddej biex tagħmel affarijiet n b'n drabi, u inti tista sort tar-raġuni tiegħek mod permezz tal-kodiċi, anki jekk huwa pseudocode u mhux il-kodiċi attwali. Allura dak dwar omega 'n kwadru? Dak li kien algoritmu li fl-aħjar każ, xorta ħa n passi kwadrati? Yeah? UDJENZA: [inaudible]. DAVID Malan: Allura sort għażla. Għaliex f'dak il-problema verament imnaqqsa l-fatt li għal darb'oħra, jien ma nafx Stajt sabu l-iżgħar kurrenti tagħhom sakemm Stajt ċċekkjati l-elementi kollha darn. Allura omega ', ngħidu aħna, n, aħna biss ħarāet bil wieħed. Sort Inserzjoni. Jekk il-lista jiġri li jiġu magħżula diġà, fl-aħjar każ aħna biss għandhom jagħmlu pass wieħed permezz tagħha, f'liema punt aħna qed żgur. U allura li jista 'jingħad biex tkun lineari, għall-żgur. What about omega-1? X'inhuma, fl-aħjar każ, jista 'jieħu numru kostanti ta 'passi? Tfittxija Għalhekk lineari, jekk inti biss tikseb xxurtjati u l-element li qed tfittex huwa dritt fil-bidu tal-lista, jekk dan huwa fejn int tibda tiegħek lineari traversal ta dik il-lista. U dan huwa minnu ta ' numru ta 'affarijiet. Per eżempju, anke binarju tfittxija hija omega ta '1. Għaliex dak li jekk ikollok verament darn xortik tajba u smack dab-fin-nofs ta ' firxa tiegħek huwa n-numru qed tfittex? Allura inti tista 'tikseb xortik tajba hemmhekk, kif ukoll. Dan wieħed, fl-aħħarnett, omega 'n log n. Allura n log n, aħna ma verament jitkellmu dwar għada, iżda - UDJENZA: Jingħaqdu sort? DAVID Malan: sort Merge. Dan kien l-aħħar darba cliffhanger ta, fejn aħna propost, u aħna wera viżwalment, li hemm algoritmi. U jingħaqdu tip ta 'waħda biss bħal algoritmu li huwa fundamentalment aktar mgħaġġel minn xi wħud minn dawn guys oħra. Fil-fatt, jingħaqdu qasir mhux biss fil- aħjar każ n n log, fl-agħar n log n każ. U meta jkollok dan koinċidenza ta ' omega u big O huma l-istess ħaġa? Aħna fil-fatt jistgħu jiddeskrivu li bħala x'hemm imsejħa theta, għalkemm huwa ftit inqas komuni. Iżda dan ifisser biss l-żewġ limiti, f'dan il-każ, huma l-istess. Allura jingħaqdu sort, dan xi verament jsarrafx biss fl għalina? Ukoll, mfakkra l-motivazzjoni. Let me pull up animazzjoni ieħor li aħna ma nħarsu lejn l-aħħar darba. Dan wieħed, l-istess idea, iżda huwa ftit akbar. U jien ser imorru quddiem u tfakkar ewwel - għandna sort inserzjoni fuq fuq ix-xellug ta 'fuq, imbagħad sort għażla, sort bużżieqa, koppja ta 'tipi oħra - qoxra u malajr - li aħna ma tkellmu dwar, u borġ u jingħaqdu tip. Allura mill-inqas tipprova li tiffoka għajnejn tiegħek fuq l-ewwel tliet fuq ix-xellug u mbagħad jingħaqdu sort meta I ikklikkja dan vleġġa ħadra. Imma jien ser let kull wieħed minnhom run, biss biex jagħtuk sens tad-diversità ta ' algoritmi li jeżistu fid-dinja. Jien ser let din ir-run għal ftit ftit sekondi. U jekk inti tiffoka għajnejn tiegħek - pick algoritmu, tiffoka fuq dan għal ftit sekondi - inti ser tibda tara l- mudell li huwa ta 'implimentazzjoni. Jingħaqdu sort, avviż, isir. Sort borġ, sort malajr, qoxra - hekk jidher aħna introdotti t-tliet agħar algoritmi aħħar ġimgħa. Iżda li tajjeb li aħna qed hawn illum biex tħares lejn sort jingħaqdu, li hija waħda ta ' dawk eħfef huwa li tħares lejn, anke għalkemm hija probabbilment se liwja moħħok biss ftit. Hawnhekk nistgħu naraw biss kemm sort għażla sucks. Iżda fuq in-naħa flip, huwa verament faċli biex jiġi implimentat. U forsi għal P Set 3, li wieħed mill- algoritmi għażilt biex jimplimentaw għall-edizzjoni standard. Perfettament multa, perfettament korretta. Iżda għal darb'oħra, bħala n gets kbira, jekk inti jagħżlu li jimplimentaw l-algoritmu aktar malajr simili jingħaqdu sort, odds huma akbar u inputs akbar, il-kodiċi tiegħek hija biss ser jimxu aktar mgħaġġel. Your website għaddej biex jaħdmu aħjar. Utenti tiegħek ser ikunu kuntenti. U għalhekk hemm dawn l-effetti li attwalment jagħti us xi fond maħsub. Mela ejja tagħti ħarsa lejn dak li jingħaqdu sort huwa attwalment madwar kollha. Il-ħaġa jibred hija li jingħaqdu sort huwa biss dan. Dan huwa, għal darb'oħra, dak li konna imsejħa pseudocode, being pseudocode Sintassi Ingliż simili. U l-sempliċità hija tip ta 'affaxxinanti. Allura fuq input ta 'elementi n - sabiex ifisser biss, hawn firxa. Huwa ltqajna affarijiet n fiha. Li kollox aħna qed tgħid hemmhekk. Jekk n huwa inqas minn 2, ritorn. Allura dan huwa biss il-każ trivjali. Jekk n huwa inqas minn 2, allura ovvjament huwa 1 jew 0, f'liema każ il-ħaġa huwa diġà magħżula jew kważi ma jeżistix, hekk biss ritorn. M'hemm xejn li jagħmlu. Allura dak każ sempliċi ġewwieni off. Else, għandna tliet passi. Sort in-nofs xellugi tal-elementi, sort il-nofs tal-lemin ta 'l-elementi, u mbagħad jingħaqdu l-nofsijiet magħżula. X'hemm interessanti hawnhekk huwa li Jien tip ta 'punting, right? Hemm tip ta 'definizzjoni ċirkolari għal dan algoritmu. F'liema sens huwa dan l-algoritmu ċirkolari definizzjoni? UDJENZA: [inaudible]. DAVID Malan: Yeah, algoritmu issortjar tiegħi, tnejn mill-passi tiegħu huma "sort xi ħaġa. "U hekk li iqajjem il- kwistjoni, ukoll, dak li jien ser tuża biex issolvi l-nofs tax-xellug u l-half-dritt? U l-sbuħija hawnhekk hija li anke jekk għal darb'oħra, dan huwa l-mind-liwi parti potenzjalment, tista 'tuża istess algoritmu biex isolvi l-nofs tax-xellug. Imma stenna minuta. Meta inti qed told biex isolvi l- nofs tax-xellug, liema huma ż-żewġ passi se tkun li jmiss? Aħna ser issolvi in-nofs xellugi tal- nofs tax-xellug u d-dritt nofs in-nofs xellugi. Indanna, kif nista sort dawk iż-żewġ nofsijiet jew kwarti,, issa? Imma dak li OK. Għandna algoritmu issortjar hawn. U anki jekk inti tista 'ninkwetaw ewwel dan huwa tip ta 'infinita loop, huwa ċiklu li qatt ma ser jispiċċaw - huwa ser tispiċċa ladarba x'jiġri? Ladarba n huwa inqas minn 2. Li eventwalment se jiġri, għaliex jekk inti żżomm tnaqqis bin-nofs u tnaqqis bin-nofs fl naqset bin-nofs f'dawn nofsijiet, żgur eventwalment int ser jispiċċaw up bil biss 1 jew 0 elementi. F'liema punt, dan algoritmu tgħid li inti qed isir. Allura l-magic reali f'dan algoritmu jidher li jkun dak il-pass finali, li qed jingħaqdu. Li l-idea sempliċi biss jingħaqdu żewġ affarijiet, dan huwa dak li finalment għaddej biex inessu biex issolvi firxa ta ', ejja ngħidu, tmien elementi. So I jkollhom tmien blalen istress aktar up hawn, tmien biċċiet tal-karti, u wieħed Google ħġieġ - li nasal biex iżommu. [Daħk] DAVID Malan: Jekk aħna nkunu nistgħu nieħdu tmien voluntiera, u ejja ara jekk nistgħu jilagħbu din out, so. Ara naqra, OK. Computer xjenza huwa jkollna gost. Kull dritt. Allura kif dwarek tlieta, idejn akbar up hemm. Erba fid-dahar. U kif madwar aħna ser nagħmlu għalik tliet f'dan ringiela? U erba 'fil-front. Allura inti tmienja, come fuq up. [Daħk] DAVID Malan: Jien attwalment mhux ċert dak li hu. Huwa l-blalen istress? Il-lampi desk? Il-materjal? L-internet? OK. Allura ġejjin fuq up. Min jixtieq - iżommu ġejjin up. Ejja ara. U dan tpoġġik post - int f'post wieħed. Uh-oh, stenna minuta. 1, 2, 3, 4, 5, 6, 7 - oh, tajba. Kull dritt, aħna qed tajba. Kull dritt, sabiex kulħadd ikollu sede, iżda mhux fuq il-Google Glass. Let me kju dawn il-up. X'hemm isem tiegħek? Michelle: Michelle. DAVID Malan: Michelle? Kull dritt, ikollok lill-dehra l-geek, jekk dan huwa OK. Well, I do wisq, I suppose, għal ftit mument. Kull dritt, standby. Imxejna ġiet tipprova toħroġ bi użu każ għall Google ħġieġ, u aħna ħsibt li jkun gost li biss tagħmel dan meta n-nies huma onstage. Aħna se jirreġistraw id-dinja mill-perspettiva tagħhom. Kull dritt. Mhux probabbilment dak Google maħsub. Kull dritt, jekk inti ma mind liebes dan għall-minuti skomdi li ġejjin, li tkun isbaħ. Kull dritt, hekk aħna hawn firxa ta ' elementi, u li array, bħala kull l- biċċiet tal-karti f'dawn folks " idejn, bħalissa jintbagħtu f'volumi kbar. Michelle: Oh, li hekk stramb. DAVID Malan: Huwa pretty ħafna każwali. U fi ftit mument, aħna qed tmur biex tipprova biex jimplimentaw jingħaqdu sort flimkien u ara fejn dik ewlenija hija ħarsa. U l-trick hawnhekk ma sort jingħaqdu huwa xi ħaġa li aħna ma jassumi s'issa. Għandna attwalment bżonn xi spazju addizzjonali. Allura dak li għaddej biex tkun partikolarment interessanti dwar dan hija li dawn guys huma ser jiċċaqalqu madwar ftit bit, għaliex jien ser jassumi li hemm firxa żejda ta 'spazju, ngħidu, id-dritt warajhom. Mela jekk dawn qed wara president tagħhom, dak l-firxa sekondarja. Jekk dawn qed bilqiegħda hawn, li l- l-array primarja. Iżda din hija riżorsa li għandna jkunux ingranati s'issa ma bużżieqa sort, ma sort għażla, ma sort inserzjoni. Recall aħħar ġimgħa, kulħadd biss tip ta 'shuffled fis-seħħ. Huma ma tuża kwalunkwe memorja addizzjonali. Għamilna kamra għal nies minn jiċċaqalqu nies madwar. Allura dan huwa ħarsa ewlieni, wisq. Hemm dan il-kompromess, b'mod ġenerali xjenza tal-kompjuter, ta 'riżorsi. Jekk inti tixtieq li tħaffef xi ħaġa bħal ħin, int ser jkollhom iħallsu prezz. U waħda minn dawk il-prezzijiet ħafna drabi hija ispazju, l-ammont tal-memorja jew hard disk ispazju li inti qed tuża. Or, franchement, l-ammont ta 'żmien programmer. Kemm ħin li tieħu inti, il-bniedem, li fil-fatt jimplimentaw ftit aktar algoritmu kkumplikata. Iżda għal-lum, il-kompromess huwa żmien u l-ispazju. Hekk jekk inti guys tista 'biss istiva up tiegħek numri hekk nistgħu naraw li int tabilħaqq tqabbil 4, 2, 6, 1, 3, 7, 8. Eċċellenti. Hekk jien ser tipprova orchestrate affarijiet, jekk inti guys tista 'sempliċement segwiex tiegħi hawn. So I am ser jimplimentaw, l-ewwel, il- ewwel pass tal-pseudocode, li huwa fuq l-input ta 'elementi n, jekk n hija inqas minn 2, mbagħad jirritornaw. Ovvjament, li ma japplikaw, hekk aħna jimxu fuq. Allura sort in-nofs xellugi tal-elementi. Allura dan ifisser li jien ser tiffoka tiegħi attenzjoni għal ftit mument fuq dawn erba guys hawn. Kull dritt, x'għandi nagħmel jmiss do? UDJENZA: Sort in-nofs xellugi. DAVID Malan: Allura issa għandi biex issolvi in-nofs xellugi ta 'dawn guys. Minħabba darb'oħra, jassumi lilek innifsek il- għan huwa biex issolvi l-nofs tax-xellug. Kif inti tagħmel dan? Just segwi l-istruzzjonijiet, anke jekk aħna qed tagħmel dan mill-ġdid. Allura sort in-nofs xellugi. Issa jien issortjar dawn iż-żewġ guys. Dak li jiġi jmiss? UDJENZA: Sort in-nofs xellugi. DAVID Malan: sort in-nofs xellugi. Allura issa dawn, dan is-sit hawn, hija lista ta 'daqs 1. U x'hemm isem tiegħek mill-ġdid? PRINCESS DAISY: Princess Daisy. DAVID Malan: Princess Daisy huwa hawnhekk. U hekk hi huwa diġà magħżula, minħabba il-lista hija ta 'daqs 1. What do I do jmiss? OK, lura, għaliex din il-lista ta ' daqs 1, li hija inqas minn 2. Imbagħad x'inhu l-pass li jmiss? U issa għandek tip ta ' wieħed imur lura fil moħħok. Tip li l-nofs tal-lemin, li tkun - dak l-isem tiegħek? LINDA: Linda. DAVID Malan: Linda. U hekk dak li nagħmlu issa li għandna lista ta 'daqs 1? UDJENZA: Ritorn. DAVID Malan: Bir-reqqa. Nerġgħu lura ewwel, u issa t-tielet pass - u jekk I tip ta 'juru dan billi tħaddan iż-żewġ sedili issa, issa I għandek jingħaqdu dawn iż-żewġ elementi. Allura issa sfortunatament, l-elementi huma out of order. Iżda li meta l-proċess li qed jingħaqdu tibda tikseb konvinċenti. Hekk jekk inti guys tista 'toqgħod up għal ftit mument, jien ser bżonn inti, fil- mument, li pass wara president tiegħek. U jekk Linda, għaliex 2 huwa iżgħar minn 4, għaliex ma inti come madwar l-ewwel? Jibqgħu hemm. Allura Linda, inti come madwar l-ewwel. Issa fir-realtà jekk huwa biss firxa nistgħu biss jiċċaqalqu tagħha fil-ħin reali minn dan il-presidenza għal dan il-post. Allura immaġina li ħa xi kostanti numru ta 'passi 1. U issa - imma għandna bżonn li tpoġġi lilek l-ewwel post hawn. U issa jekk inti tista come madwar, kif ukoll, aħna qed tmur biex tkun post tnejn. U anki jekk dan iħoss simili huwa tieħu filwaqt, x'hemm sbieħ issa huwa li l-nofs tax-xellug tal- nofs tax-xellug huwa issa magħżula. Allura dak li kien l-pass li jmiss, jekk aħna issa Rewind aktar fl-istorja? UDJENZA: nofs Dritt. DAVID Malan: sort l-nofs tal-lemin. Allura inti guys għandek tagħmel dan, ukoll. Hekk jekk inti tista 'stand up għal ftit mument? U x'hemm isem tiegħek? JESS: Jess. DAVID Malan: Jess. OK, hekk Jess issa huwa ix-xellug nofs il-nofs tal-lemin. U hekk hi lista ta 'daqs 1. Hi ovvjament magħżula. U l-isem tiegħek mill-ġdid? Michelle: Michelle. DAVID Malan: Michelle hija ovvjament lista ta 'daqs 1. Hi diġà magħżula. Allura issa l-magic jiġri, il-proċess li qed jingħaqdu. Hekk li għaddej biex jasal l-ewwel? Ovvjament Michelle. Hekk jekk inti tista come madwar lura. L-ispazju li għandna disponibbli għall tagħha issa huwa dritt wara dan il-presidenza hawn. U issa jekk inti tista 'terga' lura kif ukoll, issa għandna, tkun ċara, żewġ nofsijiet, b'kull wieħed daqs 2 - u biss għall-finijiet rappreżentazzjoni tal, jekk inti tista 'tagħmel xi ftit ta' spazju - waħda xellug nofs hawn, waħda nofs tal-lemin hawn. Rewind aktar fl-istorja. X'inhu pass huwa li jmiss? UDJENZA: Jingħaqdu. DAVID Malan: Allura issa għandna biex jingħaqdu. Allura OK, hekk issa, Thankfully, aħna biss jinħelsu erba siġġijiet. Allura aħna ħadthom użati darbtejn kemm memorja, iżda nistgħu nagħtu flip-flopping bejn iż-żewġ arrays. Allura liema numru huwa li jasal l-ewwel? Allura Michelle, ovvjament. Allura ġejjin madwar u jieħdu sedil tiegħek hawn. U allura numru 2 hija ovvjament jmiss, sabiex inti jiġu hawn. Numru 4, numru 6. U għal darb'oħra, anki jekk hemm Ftit ftit ta 'mixi involuti, verament, dawn jista 'jiġri istantanjament, billi jiċċaqilqu waħda - OK, ukoll rwol. [Daħk] DAVID Malan: U issa aħna qed fil-forma pjuttost tajba. In-nofs xellugi tal-kollu input issa ġiet magħżula. Kull dritt, hekk dawn guys kellhom l-vantaġġ ta 'tiegħi - kif ma kien jispiċċaw l-bniet fuq il- xellug u l-subien fuq il-lemin? OK, hekk guys "dawran issa. So I mhux se jimxu miegħek permezz dawn il-passi. Ser naraw jekk nistgħu terġa 'tapplika l-istess pseudocode. Jekk inti tixtieq li tmur quddiem u stand up, u inti guys, let me jagħtuk l-mic. Ara jekk inti ma tistax tirreplika dak aħna biss ma hawn fuq l- tarf l-ieħor tal-lista. Li jeħtieġ li jitkellem l-ewwel, ibbażata fuq l-algoritmu? Allura jispjegaw dak li qed tagħmel qabel ma tagħmel xi movimenti sieq. SPEAKER 1: Kull dritt, hekk peress li I am in-nofs xellugi tal- nofs tax-xellug, I-ritorn. Dritt? DAVID Malan: Tajba. SPEAKER 1: U mbagħad - DAVID Malan: Min jagħmel l-mic mur jmiss? SPEAKER 1: numru jmiss. SPEAKER 2: Hekk jien il-nofs tal-lemin tal-nofs tax-xellug tal- nofs tax-xellug, u I-ritorn. DAVID Malan: Tajba. Inti tirritorna. Allura issa x'inhu l-up li jmiss għalik tnejn? SPEAKER 2: Irridu tara li l-iżgħar. DAVID Malan: Eżattament. Aħna rridu li jingħaqdu. L-ispazju aħna qed tmur biex jużaw biex jingħaqdu inti fis, anki jekk dawn qed ovvjament diġà magħżula, aħna qed tmur biex isegwu l-istess algoritmu. Hekk li tmur lura l-ewwel? Allura 3, u mbagħad 7. U issa l-mic tmur għal dawn guys, OK? SPEAKER 3: Hekk jien il-nofs tal-lemin ta 'l- nofs tax-xellug, u n tiegħi huwa inqas minn 1, hekk jien biss se jgħaddu - DAVID Malan: Tajba. SPEAKER 4: Jien l-nofs tal-lemin ta 'l- nofs tal-lemin ta 'l-nofs tal-lemin, u jien wkoll persuna waħda, hekk jien ser jirritornaw. Allura issa aħna jingħaqdu. SPEAKER 3: Allura immorru lura. DAVID Malan: Allura inti tmur fil-dahar. Allura 5 tmur l-ewwel, imbagħad 8. U issa udjenza, li hija l- pass irridu issa Rewind lura fl-imħuħ tagħna? UDJENZA: Jingħaqdu. DAVID Malan: twaħħid nofs tax-xellug u tal-lemin nofs in-nofs xellugi oriġinali. Allura issa - u biss biex dan ikun ċar, jagħmlu ftit ta 'spazju bejn żewġ guys inti. Allura issa li l-żewġ listi, xellug u lemin. Allura kif nistgħu issa jingħaqdu inti guys fis l-filliera ta 'quddiem tas-sedili mill-ġdid? 3 tmur l-ewwel. Imbagħad 5, ovvjament. Imbagħad 7, u issa 8. OK, u issa ninsabu? UDJENZA: Ma sarx. DAVID Malan: Ma sarx, għaliex ovvjament, hemm pass wieħed fadal. Iżda għal darb'oħra, ir-raġuni jien jużaw dan jargon bħal "Rewind fil moħħok," huwa minħabba li tassew dak li qed jiġri. Aħna ser kollha permezz ta 'dawn il-passi, iżda aħna qed tip ta 'espressjonijiet fit għal mument, aktar profonda għadis fil- algoritmu, jieqaf għal mument, għadis fond fil-algoritmu, u issa għandna biex issolvi ta kontrina fil tagħna imħuħ u jneħħu kollha ta 'dawn saffi li konna tip ta 'posposti. Allura issa għandna żewġ listi ta 'daqs 4. Jekk inti guys tista 'toqgħod up-aħħar darba u jagħmlu daqsxejn ta 'spazju hawn biex jagħmluha ċara li dan huwa ix-xellug nofs il-oriġinali, l- nofs tal-lemin ta 'l-oriġinali. Min hu l-ewwel numru li aħna bżonn biex jiġbdu fil-dahar? Michelle, tal-kors. Allura aħna tpoġġi Michelle hawn. U li għandu numru 2? Numru 2 jixgħel lura ukoll. Numru 3? Eċċellenti. Numru 4, numru 5, numru 6, numru 7, u n-numru 8. OK, hekk qisni ħafna ta 'passi, għall-żgur. Imma issa ejja ara jekk aħna ma tista 'tikkonferma tip ta 'intuwittivament li dan algoritmu fundamentalment, partikolarment fir- n gets verament kbir, kif aħna stajt tidher mal-animazzjonijiet, huwa fundamentalment aktar malajr. So I titlob dan algoritmu, fl-agħar każ u anki fl-aħjar każ, huwa kbir O ta 'n darbiet log n. Dan huwa, hemm xi aspett ta 'dan algoritmu li tieħu passi n, iżda hemm aspett ieħor x'imkien li iterazzjoni, li looping, li jieħu passi log n. Nistgħu iqiegħed subgħajh tagħna fuq dak dawk żewġ numri huma jirreferu għall? Well, meta - where'd l mic imorru? SPEAKER 1: Would il-log n tkun tkissir us up f'żewġ - billi tiddividi żewġ, essenzjalment. DAVID Malan: Eżattament. Kwalunkwe ħin li naraw fi kwalunkwe algoritmu b'hekk S'issa, hemm kien dan il-mudell ta ' diviżjoni, diviżjoni, diviżjoni. U huwa tipikament mnaqqsa għal xi ħaġa li logaritmika, log bażi 2. Iżda tista 'verament tkun xejn, imma bażi 2 log. Issa dak dwar il-n? I jista 'jara li aħna tip ta maqsum inti guys - maqsum inti, maqsuma int, maqsum inti, maqsuma int. Fejn ma l-aħħar jiġu minn? Allura huwa l-amalgamazzjoni. Minħabba taħseb dwarha. Meta inti jingħaqdu tmien persuni flimkien, fejn nofshom huma sett ta 'erba' u nofs l-ieħor huma ieħor sett ta 'erba, kif taħseb li tmur dwar kif isir l-amalgamazzjoni? Ukoll, inti guys ma kien pjuttost intuwittivament. Imma jekk jien minflok ma kien ftit aktar metodiku, I jista 'jkollhom mfakkar fil il-persuna fuq ix-xellug ewwel mal xellug tiegħi idejn, mfakkar fil-persuna fuq ix-xellug ta 'dik in-nofs mal-lemin tiegħi, u biss sussegwentement mixi permezz tal- lista, li tipponta lejn l-iżgħar element kull darba, li jiċċaqalqu finger tiegħi fuq u fuq kif meħtieġ matul l-lista. Imma x'hemm importanti dwar dan li qed jingħaqdu proċess huwa jien jqabbel dawn pari ta 'elementi. Mill-nofs tal-lemin u mix-xellug nofs, jien qatt darba treġġigħ lura. Allura l-inkorporazzjoni innifsu qed tieħu mhux aktar minn n passi. U kif ħafna drabi ma I jkollhom biex tagħmel dan jingħaqdu? Ukoll, mhux aktar minn n, u aħna biss raw li ma 'l-inkorporazzjoni finali. U hekk jekk inti tagħmel xi ħaġa li jieħu log n passi n darbiet, jew viċe versa, li għaddej biex tagħtina n ħinijiet log n. U għaliex huwa dan aħjar? Ukoll, jekk aħna diġà jafu li log n huwa aħjar minn n - id-dritt? Rajna fit-tfittxija binarja, il-ktieb tat-telefon eżempju, log n kien definittivament aħjar minn lineari. Allura dan ifisser n ħinijiet log n hija definittivament aħjar minn n darbiet ieħor n, AKA n kwadrat. U dan huwa dak li aħna finalment jħossu. Round daqshekk kbira ta 'applause, jekk nistgħu, għal dawn guys. [Applause] DAVID Malan: U rigali firda tiegħek - inti tista 'żżomm in-numri, jekk inti tixtieq. U rigal firda tiegħek, bħas-soltu. Oh, u ahna nibaghtulek l-footage, Michelle. Grazzi. Kull dritt. Tgħin lilek innifsek għal ballun stress. U let me pull up, fil-frattemp, ħabib tagħna Rob Bowden li joffru perspettiva kemmxejn differenti fuq dan, peress li inti tista 'taħseb dwar dawn passi jiġri fil kemmxejn b'mod differenti. Fil-fatt, l-set-up għal dak Rob huwa madwar li juruna tassumi li konna diġà għamlu l up diviżjoni tal- lista big fi tmien listi żgħar, kull daqs 1. Allura aħna qed jinbidlu l-pseudocode a ftit biss biex issolvi tat jiksbu fil- idea qalba ta 'kif l-amalgamazzjoni xogħlijiet. Iżda l-ħin tmexxija ta 'dak hu waslu biex jagħmlu għadu ser ikunu l-istess. U għal darb'oħra, l-set-up hawnhekk huwa li hu bdew ma 'tmien listi ta' daqs 1. Allura inti ħadthom qbiżt l-parti fejn hu attwalment isir il-log n, log n, log n diviżjoni tal-input. [Daqq video] -Li huwa għal pass wieħed. Għal pass tnejn, ripetutament jingħaqdu pari ta 'listi. DAVID Malan: Hm. Biss awdjo huwa li ġejjin minn kompjuter tiegħi. Ejja nippruvaw dan mill-ġdid. Just arbitrarju pick - issa għandna erba 'listi. Tgħallem qabel. DAVID Malan: Hemm immorru. Twaħħid-108 u 15, aħna jispiċċaw up mal-lista 15, 108. Twaħħid 50 u 4, aħna tispiċċa bil 4, 50. Twaħħid 8 u 42, aħna jispiċċaw bi 8, 42. U l-amalgamazzjoni 23 u 16, aħna tispiċċa bil 16, 23. Issa listi kollha tagħna huma ta 'daqs 2. Avviż li kull tal- erba 'listi huwa magħżul. Allura aħna tista 'tibda qed jingħaqdu pari ta 'listi darb'oħra. Twaħħid 15 u 108 u 4 u 50, aħna ewwel jieħdu l-4, allura l-15, imbagħad l-50, allura l-108. Twaħħid 8, 42 u 16, 23, aħna l-ewwel tieħu l-8, allura l-16, allura l-23, allura l-42. Allura issa għandna biss żewġ listi ta 'daqs 4, li kull wieħed minnhom huwa magħżul. Allura issa aħna jingħaqdu dawn iż-żewġ listi. L-ewwel, aħna jieħdu l-4, allura aħna jieħdu l- 8, allura nieħdu l-15, imbagħad 16, imbagħad 23, imbagħad 42, imbagħad 50, imbagħad 108. [Daqq video END] DAVID Malan: Għal darb'oħra, avviż, hu qatt ma mimsus tazza jingħataw żmien aktar minn wieħed wara avvanz lil hinn minnha. Hekk hu qatt ma tirrepeti. Hekk hu dejjem li jiċċaqalqu lejn il-ġenb, u li fejn sirna n tagħna. Għaliex ma let me pull up animazzjoni wieħed li rajna qabel, iżda din id-darba jiffoka biss fuq it-tip jingħaqdu. Let me imorru quddiem u zoom fil dwar dan hawn. Ewwel let me jagħżlu input każwali, tagħmel dan aktar evidenti, u inti tista sort ta 'tara dak li aħna ħa għall mogħtija, qabel, jingħaqdu tip huwa attwalment tagħmel. Allura avviż li inti tikseb dawn nofsijiet jew dawn kwarti jew dawn tmienja tal- problema li kollha f'daqqa jibdew jieħdu forma tajba. U mbagħad finalment, inti tara fuq l-aħħar ħafna li bam, kollox huwa magħquda flimkien. Allura dawn huma biss tlieta differenti jieħu fuq l-istess idea. Iżda l-għarfien ewlieni, bħad qasma u conquer fl-ewwel klassi, kienet li aħna iddeċieda li b'xi mod jaqsam il-problema fis xi ħaġa kbira, fis sort xi ħaġa ta identiċi fl-ispirtu, iżda iżgħar u iżgħar u iżgħar. Issa gost mod ieħor biex issolvi tar jaħsbu dwar dawn, anki jekk mhuwiex ser jagħtuk l-istess intuwittivi fehim, huwa l-animazzjoni wara. Allura dan huwa xi ħadd video jitqiegħdu flimkien li assoċjati differenti ħsejjes bl-operazzjonijiet varji għall sort inserzjoni, per sort jingħaqdu, u għal ftit oħrajn. Allura fil-mument, jien ser hit Play. Huwa madwar minuta twil. U anki jekk inti xorta tista 'tara l- mudelli jiġri, din id-darba inti tista ' wkoll jisimgħu kif dawn algoritmi huma jwettqu b'mod differenti u ma ' mudelli kemmxejn differenti. Dan huwa tip inserzjoni. [Tones KUNDIZZJONIJIET] DAVID Malan: Huwa darb'oħra qed jipprova li daħħal kull element fis fejn jappartjeni. Dan huwa tip bubble. [Tones KUNDIZZJONIJIET] DAVID Malan: U inti tista sort ta 'jħossu kif relattivament ftit xogħol li huwa qed jagħmel fuq kull pass. Dan huwa dak tediousness ħsejjes simili. [Tones KUNDIZZJONIJIET] DAVID Malan: Dan huwa tip ta 'għażla, fejn aħna tagħżel l-element li rridu mill għaddejjin mill-ġdid u għal darb'oħra u għal darb'oħra u t-tqegħid fil-bidu. [Tones KUNDIZZJONIJIET] DAVID Malan: Dan huwa jingħaqdu sort, li inti tista 'verament tibda tħossok. [Tones KUNDIZZJONIJIET] [Daħk] DAVID Malan: Xi ħaġa imsejħa gnome sort, li aħna ma ħares lejn. [Tones KUNDIZZJONIJIET] DAVID Malan: So let me tara, issa, distratt kif inti nisperaw li bil- mużika, jekk I jistgħu jiżolqu ftit daqsxejn ta 'matematika fil hawn. Allura hemm raba mod li nistgħu jaħsbu dwar xi jfisser li dawn funzjonijiet li jitwettqu aktar malajr minn dawk li konna rajna qabel. U jekk int ġejjin fil-kors minn sfond matematika, inti tassew taf forsi diġà li inti jistgħu SLAP terminu fuq din it-teknika - jiġifieri recursion, funzjoni li b'xi mod jitlob huwa stess. U għal darb'oħra, ifakkar li sort jingħaqdu pseudocode kien jirrikorri fis-sens li wieħed mill-passi jingħaqdu sort ta kien li jsejħu sort - jiġifieri, innifsu. Iżda Thankfully, għaliex aħna tinżamm sejħa sort, jew jingħaqdu sort, speċifikament, fuq iżgħar u l-lista iżgħar, aħna eventwalment qiegħ barra grazzi għall dak li aħna ser sejħa base case, il-każ hard-kodifikati li qal jekk il-lista huwa żgħir, inqas minn 2 f'dak il-każ, biss jirritorna immedjatament. Jekk aħna ma kellhiex il-każ speċjali, il- algoritmu kieku qatt qiegħ barra, u inti tabilħaqq jsibu rwieħhom loop infinita verament dejjem. Iżda jissoponi li ridna li issa tqiegħed xi numri fuq dan, għal darb'oħra, bl-użu n id-daqs tal-input. U jien ridt li jgħidlek, x'hemm il-ħin totali involut running sort jingħaqdu? Jew b'mod iktar ġenerali, x'hemm l-ispiża ta 'dan fil-ħin? Ukoll huwa pjuttost faċli tkejjel dak. Jekk n huwa inqas minn 2, iż-żmien involut fl-għażla elementi n, fejn n hija 2, hija 0. Għaliex aħna biss ritorn. M'hemm l-ebda xogħol li għandu jsir. Issa forsi, forsi huwa pass wieħed jew tnejn passi biex insemmu l-ammont ta ' xogħol, iżda huwa qrib biżżejjed għal 0 dik Jien biss se ngħid ebda xogħol hija meħtieġ jekk il-lista hija tant żgħira li jiġu uninteresting. Iżda f'dan il-każ huwa interessanti. Il-każ rikursivi kien il-fergħa ta ' l pseudocode dak imsemmi inkella, sort in-nofs xellugi, issolvi d-dritt nofs, tgħaqqad iż-żewġ nofsijiet. Issa għaliex din l-espressjoni jirrappreżenta dak spiża? Ukoll, T ta 'n ifisser biss l- ħin biex issolvi l-elementi n. U mbagħad fuq il-lemin tal- ugwali sinjal hemm, it-T ta 'n maqsuma minn 2 hija tirreferi għall-ispiża ta 'dak? Sortjar in-nofs xellugi. It-T-oħra ta 'n diviż bi 2 huwa preżumibbilment jirreferu għall-ispiża biex isolvi l-nofs tal-lemin. U allura l-n plus? Huwa l-amalgamazzjoni. Għaliex jekk għandek żewġ listi, wieħed ta ' n daqs matul 2 u ieħor ta 'qies n aktar minn 2, inti għandek essenzjalment tmissx kull wieħed minn dawk l-elementi, bħal Rob mimsus kull wieħed mill-cups, u biss kif aħna osservat f'kull tal- voluntiera fuq il-palk. Allura n hija l-ispiża ta 'għaqda. Issa sfortunatament, din il-formula huwa wkoll innifsu rikursiv. Mela jekk staqsa l-mistoqsija, jekk n hija, ngħidu aħna, 16, jekk hemm 16-il persuna fuq il-palk jew 16 tazzi fil-video, kemm total passi ma jieħdu biex sort lilhom ma sort jingħaqdu? Huwa fil-fatt mhux risposta ovvja, għaliex issa inti għandek sort ta ' recursively twieġeb din il-formula. Imma dak li OK, għaliex let me tipproponi li aħna tagħmel dan li ġej. Il-ħin involuti biex issolvi 16-il persuna jew 16 cups se tkun rappreżentata ġeneralment bħala T-16. Iżda li jkun daqs, skond tagħna formula preċedenti, 2 darbiet l-ammont ta 'ħin li tieħu biex issolvi 8 tazzi plus 16. U għal darb'oħra, plus 16 huwa l-ħin li jingħaqdu, u l-żewġ ħinijiet T tat-8 hija l- ħin biex issolvi nofs tax-xellug u dritt nofs. Iżda għal darb'oħra, dan mhux biżżejjed. Irridu adsa aktar profonda. Dan ifisser li għandna nirrispondu l- kwistjoni, dak li huwa T tat-8? Ukoll T tat-8 huwa biss 2 żminijiet T tal-4 plus 8. Well, x'hemm T tal-4? T ta '4 huwa biss 2 darbiet T tat-2 plus 4. Well, x'hemm T tat-2? T tat-2 huwa biss 2 darbiet T ta '1 plus 2. U għal darb'oħra, aħna qed tip ta 'jkollna staġnati f'dan iċ-ċiklu. Iżda huwa dwar li tolqot dak hekk imsejħa każ bażi. Għaliex x'hemm T ta '1, aħna ma titlob? 0. Allura issa finalment, nistgħu naħdmu lura. Jekk T-1 0 huwa, I issa tista 'tmur lura up wieħed linja li dan Guy hawn, u nista ' plug in 0 għall T-1. Allura dan ifisser li huwa ugwali 2 darbiet żero, inkella magħruf bħala 0, plus 2. U hekk dik l-espressjoni kollu huwa 2. Issa jekk I jieħdu l-T ta '2, li tweġiba huwa 2, plagg fil-linja tan-nofs, T ta '4, li tagħti me 2 darbiet 2 plus 4, hekk 8. Jekk I imbagħad plagg fil 8 mas-sena linja, li tagħti me 2 darbiet 8, 16. U jekk aħna mbagħad tkompli li bl- 24, u żżid f'16, aħna finalment jiksbu valur ta '64. Issa li fih innifsu tip ta 'jitkellem xejn man-notazzjoni n, il- big O, il-omega li konna kien jitkellem dwar. Iżda jirriżulta li 64 huwa tabilħaqq 16, id-daqs tal-input, log bażi 2 tas-16. U jekk dan huwa ftit familjari, biss jaħsbu lura, u dan ser terga 'lura lilek eventwalment. Jekk dan huwa bażi log 2, huwa simili 2 jitgħollew sal-dak jagħtik 16? Oh, li 4, dan huwa 16-il darba 4. U għal darb'oħra, mhuwiex big deal jekk dan huwa tip ta 'memorja imċajpra issa. Iżda għal issa, jieħdu fuq il-fidi li 16 log 16 huwa 64. U għalhekk fil-fatt, ma 'dan sanità sempliċi jivverifikaw, konna ikkonfermata - iżda mhux ippruvat formalment - li l-ħin ta 'tmexxija jingħaqdu sort huwa tabilħaqq n log n. Allura mhux ħażin. Huwa definittivament aħjar mill- algoritmi Rajna s'issa, u huwa għaliex aħna ħadthom leveraged, wieħed, ta 'teknika msejħa recursion. Iżda aktar interessanti minn dak li kunċett ta 'diviżjoni u conquering. Għal darb'oħra, verament ġimgħa 0 għalf li anke issa qed terġa 'sseħħ fil- b'mod aktar konvinċenti. Issa eżerċizzju ftit gost, jekk inti stajt qatt ma għamlu dan - u inti probabilment ma jkollhomx, minħabba tip ta 'normal nies ma naħsibx li jagħmlu dan. Imma jekk immur għal google.com u jekk I tixtieq titgħallem xi ħaġa dwar recursion, Ikteb. [Daħk] [Daħk AKTAR] DAVID Malan: Bad Joke bil-mod tixrid. [Daħk] DAVID Malan: Biss fil-każ, huwa hemmhekk. I ma jespliċitaw hija żbaljata, u hemm l-ċajta. Kull dritt. Jispjegaw lill-poplu li jmiss lilek jekk għadu ma pjuttost għafast għadha biss. Iżda recursion, b'mod aktar ġenerali, jirreferi għall-proċess ta 'funzjoni sejħa innifsu, jew b'mod iktar ġenerali, li jiddividu l- problema f'xi ħaġa li tista 'tkun solvuti frammentat mill-soluzzjoni identika problemi rappreżentattivi. Ukoll, ejja gerijiet bidla għal ftit mument. Aħna nixtiequ li jintemm fit ċerti cliffhangers, Mela ejja nibdew biex jistabbilixxu l-istadju, għal diversi minuti, fuq idea sempliċi ħafna - dik ta 'iskambji żewġ elementi, id-dritt? Kollha ta 'dawn algoritmi aħna kont qed jitkellem dwar l-aħħar ftit lectures jinvolvu xi tip ta 'iskambji. Illum kien viżwalizzata minnhom jkollna up barra ta 'siġġijiet tagħhom u madwar mixi, imma fil-kodiċi, nixtiequ ħu element minn firxa waħda u plop fis ieħor. Allura kif do we go dwar kif isir dan? Well, let me imorru quddiem u jiktbu programm quick hawn. Jien ser jimxi 'l quddiem u jagħmlu dan kif ġej. Ejja sejħa dan - dak li rridu sejħa dan wieħed? Attwalment, l-ebda. Let me kontrina. Ma rridx li tagħmel dan cliffhanger s'issa. Hija se jħassru l-gost. Ejja nagħmlu dan minflok. Ejja ngħidu li nixtieq li jiktbu ftit programm u li issa tħaddan din idea ta 'recursion. I tip ta 'ltqajna qabel myself hemmhekk. Jien ser jagħmlu dan li ġej. L-ewwel, a quick jinkludu ta 'standard io.h, kif ukoll jinkludu ta cs50.h. U allura jien ser jimxi 'l quddiem u tiddikjara null prinċipali int bil-mod normali. I realizzati I ve misnamed-fajl, hekk let me żid ftit. estensjoni c hawn hekk li nistgħu jikkompilaw kif suppost. Tibda din il-funzjoni off. U l-funzjoni I jridu jiktbu, pjuttost sempliċiment, huwa wieħed li jitlob lill- utent għal numru u mbagħad iżid up il-numri bejn li numru u, jgħidu, 0. Allura l-ewwel jien ser jimxi 'l quddiem u tiddikjara n int. Imbagħad I kopja xi kodiċi li konna użati għal waqt. Filwaqt xi ħaġa huwa veru. I ser jiġu lura għal dak fil-mument. What do I trid tagħmel? Irrid ngħid printf pożittiv numru sħiħ jekk jogħġbok. U allura jien ser jgħidu n gets tikseb int. Għalhekk għal darb'oħra, xi kodiċi boilerplate li konna użati qabel. U jien se tagħmel dan filwaqt li n huwa inqas minn 1. Allura dan se jiżgura li l-utent tagħti me numru sħiħ pożittiv. U issa jien ser jagħmlu dan li ġej. I trid iżżid up kollha tan-numri bejn 1 u un, jew 0 u n- ekwivalenti, biex tikseb is-somma totali. Allura l-simbolu sigma big li inti tista 'recall. Hekk jien ser tagħmel dan billi l-ewwel sejħa funzjoni msejħa sigma, jgħaddiha fl n, u mbagħad jien ser jgħidu printf, it-tweġiba hija hemm dritt. Għalhekk fil-qosor, I jiksbu u int mill-utent. I jiżgura huwa pożittiv. Niddikjara a imsejjaħ tweġiba varjabbli ta ' int tip u maħżen fiha r-ritorn valur tal sigma, tgħaddi fis n bħala input. U mbagħad I jistampa din ir-risposta. Sfortunatament, anke jekk sigma ħsejjes bħal xi ħaġa li jista 'jkun fil- il-fajl math.h, dikjarazzjoni tiegħu, huwa attwalment mhux. Allura dak OK. I tista 'timplimenta dan myself. Jien ser timplimenta funzjoni msejħa sigma, u li għaddej biex tieħu parametru - ejja biss sejħa hija m, biss dan huwa differenti. U mbagħad up hawn, jien ser ngħid, ukoll, jekk m ikun inqas minn 1 - dan huwa Programm ħafna uninteresting. Hekk jien ser jimxi 'l quddiem u immedjatament jirritorna 0. Hija biss ma jagħmilx sens li jammontaw kollha in-numri bejn 1 u m jekk m hija nnifisha 0 jew negattiv. U allura jien ser jimxi 'l quddiem u tagħmel dan ħafna iteratively. Jien ser jagħmlu dan it-tip ta 'qodma l-iskola, u jien ser jimxi 'l quddiem u jgħidu li jien ser tiddikjara somma li tkun 0. Imbagħad jien ser ikollhom a għal loop ta int - u let me tagħmel dan biex jaqblu tagħna kodiċi ta 'distribuzzjoni, hekk ikollok kopja fid-dar. i int gets 1 fuq sa i huwa inqas minn jew ugwali għal m. i plus plus. U allura ġewwa ta 'dan għall loop - aħna qed kważi hemm - somma gets somma plus 1. U allura jien ser jirritorna l-ammont. So I ma 'dan malajr, pjuttost ċertament. Iżda għal darb'oħra, il-funzjoni ewlenija pjuttost sempliċi, ibbażat fuq kodiċi konna miktub s'issa. Juża l-linja doppja biex tikseb pożittiv int mill-utent. I imbagħad jgħaddu li int għal funzjoni ġdida imsejħa sigma, ssejjaħ dan, għal darb'oħra, n. U jien jaħżnu l-valur tar-ritorn, ir-risposta mill-kaxxa s-sewda bħalissa magħrufa bħala sigma, fil-varjabbli imsejħa risposta. Imbagħad I jistampaw. Jekk aħna issa tkompli l-istorja, kif hija sigma implimentat? Nipproponi li jimplimentaw kif ġej. L-ewwel, xi ftit ta 'żball ta' verifika biex tiżgura li l-utent mhux messing miegħi u li jgħaddi fl xi valur negattiv jew 0. Imbagħad I tiddikjara varjabbli imsejjaħ somma u tistabbilixxi li 0. U issa nibda biex jiċċaqalqu minn i ugwali 1 it-triq kollha sa u inkluż m, għaliex nixtieq li tinkludi l- numri minn wieħed sa m, inklużi. U ġewwa ta 'dan għal loop, I biss ma somma gets kwalunkwe huwa issa, flimkien mal- valur ta 'i. Flimkien mal-valur ta 'i. Bħala twarrib, jekk inti stajt ma bbenefikawx dan qabel, hemm xi zokkor sintattika għal din il-linja. I jistgħu jikteb dan bħala plus daqs i, biss biex jiffrankaw myself ftit keystrokes u biex tfittex cooler daqsxejn. Imma li kollox. Huwa funzjonalment l-istess ħaġa. Sfortunatament, dan il-kodiċi tal- mhux se jikkumpilaw s'issa. Jekk I run jagħmlu sigma 0, kif am I se tikseb għajjat ​​fil? X'hemm Huwa ser ma simili? UDJENZA: [inaudible]. DAVID Malan: Yeah, I ma ddikjarawx il-funzjoni top up, right? C huwa tip ta stupid, fis-sens li biss ma dak li inti tgħid li tagħmel, u inti għandek tagħmel dan f'dik l-ordni. U hekk jekk I hit Ikteb hawn, jien ser tikseb twissija dwar sigma impliċitu dikjarazzjoni. Oh, mhux problema. I tista 'tmur sal-quċċata, u nista' jiġifieri, id-dritt, stenna minuta. Sigma hija funzjoni li prospetti l int u jistenna int bħala input, b'waqfa u virgola. Jew I tista 'tpoġġi l-funzjoni sħiħa hawn fuq ewlenija, iżda b'mod ġenerali, I d jirrakkomanda kontra li, għaliex dan huwa sbieħ li dejjem ikollhom prinċipali fil-quċċata hekk inti tista 'adsa dritt u jafu liema programm qed jagħmel mill-qari prinċipali ewwel. Allura issa let me ċar l-iskrin. Remake sigma 0. Kollha jidher li check out. Let me run sigma 0. Inter pożittiv. I ser tagħtiha l-għadd 3 li jżommha sempliċi. Allura li għandha tagħti me 3 plus 2 plus 1, hekk 6. Ikteb, u tabilħaqq niġi 6. I tista 'tagħmel xi ħaġa akbar - 50, 12, 75. Just bħala tanġent, jien ser tagħmel xi ħaġa redikoli bħal verament kbir numru, Oh, li attwalment jinħadmu - eh, ma naħsibx li d-dritt. Ejja ara. Ejja verament mess miegħu. Li l-problema. X'qed jiġri? Il-kodiċi m'huwiex ħażin. Huwa għadu lineari. Whistling huwa effett tajjeb, għalkemm. X'qed jiġri? Mhux żgur jekk I smajt dan. Għalhekk jirriżulta li - u dan huwa bħala aside. Dan mhux qalba għall- idea ta 'recursion. Jirriżulta, għaliex jien jippruvaw jirrappreżentaw numru kbir bħal dan, l-aktar probabbli huwa qed interpretat ħażin billi C bħala numru pożittiv mhux, iżda numru negattiv. Aħna ma tkellmu dwar dan, iżda jinstabx hemm għadd negattivi fid-dinja flimkien għal numri pożittivi. U l-mezzi li permezz tagħhom tista jirrappreżentaw numru negattiv essenzjalment hija, tuża waħda bit speċjali biex jindikaw pożittiv fuq negattiv. Huwa ftit aktar kumplessi minn dan, iżda li l-idea bażika. Allura sfortunatament, jekk C hija konfuża wieħed ta 'dawk bits bħala fatt li jfisser, oh, dan huwa numru negattiv, loop tiegħi hawn, per eżempju, huwa fatt qatt ma ser tintemm. Mela jekk jien kienu attwalment istampar xi ħaġa ġdid u għal darb'oħra, aħna se tara lott kollu. Iżda għal darb'oħra, dan huwa minbarra l-punt. Dan huwa verament ftit tip ta ' kurżità intellettwali li aħna ser jidħlu lura biex eventwalment. Iżda għal issa, dan huwa korrett implimentazzjoni jekk nassumu li l- utent se jipprovdi ints li jaqblu fi ħdan ints. Imma I jsostnu li dan il-kodiċi, franchement, jista 'jsir tant aktar sempliċi. Jekk l-għan fil-idejn huwa li jieħu numru bħal mu żid up kollha tal- numri bejn dan u 1, jew bil-maqlub bejn l-1 u, nitlob li nista 'jissellef din l-idea li jingħaqdu sort kellha, li kien qed jieħu problema ta 'dan id-daqs u jaqsmuh fis xi ħaġa iżgħar. Forsi mhux nofs, iżda iżgħar, iżda rappreżentattiv-istess. Istess idea, iżda problema iżgħar. Hekk jien attwalment - let me jiffrankaw dan il-fajl ma 'numru verżjoni differenti. Aħna ser sejħa din il-verżjoni 1 minflok 0. U jien jsostnu li I jistgħu attwalment reimplement dan f'dan it-tip ta ' mind-liwi mod. Jien ser jitilqu parti minnha biss. Jien se ngħid jekk m ikun inqas minn jew saħansitra ugwali għal 0 - Jien biss se tkun ftit aktar anali dan iż-żmien mal-verifika żball tiegħi - Jien ser imorru quddiem u lura 0. Dan huwa arbitrarju. I am biss sempliċement jiddeċiedu jekk l-utent tagħti me numru negattiv, jien jirritornaw 0, u għandhom qrajt id-dokumentazzjoni aktar mill-qrib. Else - Avviż dak li jien ser tagħmel. Else I am ser jirritorna m plus - dak li huwa sigma ta 'm? Ukoll, sigma ta 'm plus minus 1 m, plus minus m 2, plus minus 3 m. Ma rridx li tikteb kollha ta 'dak out. Għaliex ma I biss żi punt? Recursively sejħa myself ma 'ftit problema iżgħar, semicolon, u sejħa hija ta 'kuljum? Dritt? Issa hawnhekk, wisq, inti tista 'tħossok jew jinkwetaw li dan huwa loop infinita li jien jinduċu, fejn I am implimentazzjoni sigma billi ċċempel sigma. Imma dak li perfettament OK, minħabba I ħasbu quddiem l miżjuda li linji? UDJENZA: [inaudible]. DAVID Malan: 23 sa 26, li huwa jekk il-kundizzjoni tiegħi. Għaliex x'hemm sbieħ dwar il- tnaqqis hawn, għaliex I iżommu għoti problemi sigma iżgħar, iżgħar problemi, iżgħar - mhuwiex nofs id-daqs. Huwa biss pass tarbija iżgħar, iżda li OK. Minħabba eventwalment, aħna ser jaħdmu mod tagħna sa 1 jew 0. U ladarba aħna hit 0, sigma mhux ser sejħa nnifisha aktar. Huwa ser jirritorna minnufih 0. Allura l-effett, jekk inti tip ta 'riħ din up f'moħħu tiegħek, huwa li żżid m plus m minus 1, plus minus m 2, plus minus m 3, plus dot, dot, dot, m minus m, eventwalment giving you 0, u l- effett huwa finalment li jkunu miżjuda l dawn l-affarijiet flimkien. Allura aħna ma, ma recursion, solvuta l-problema li għandna ma setgħetx issolvi qabel. Tabilħaqq, verżjoni 0 ta 'dan, u kull problema sal-lum, kien solvable ma biss bl-użu ta 'linji jew waqt ħoloq jew constructs simili. Imma recursion, I daresay, jagħtina mod differenti ta 'ħsieb dwar problemi, fejn jekk aħna tista 'tieħu problema, jaqsamha minn xi ħaġa kemmxejn kbir fis xi ħaġa kemmxejn iżgħar, I jsostnu li nistgħu issolviha forsi ftit aktar elegantly f'termini tad-disinn, b'inqas kodiċi, u forsi anki isolvu problemi aktar dak li jkun jkun aktar diffiċli, kif aħna ser eventwalment tara, soluzzjoni purament iteratively. Iżda l-cliffhanger li għamilt nirtira us fuq kien dan. Let me imorru quddiem u tiftaħ up fajl mill - attwalment, let me go u tagħmel dan malajr reali. Let me imorru quddiem u tipproponi dan li ġej. Fost kodiċi lum hija dan il-fajl hawn. Dan wieħed hawn, noswap. Allura dan huwa programm ftit stupid li I bit-tarjola up li t-talbiet li tagħmel dan li ġej. Fil prinċipali, l-ewwel jiddikjara int imsejħa x u tassenja dan il-valur ta '1. Imbagħad tiddikjara y int u tassenja dan il-valur 2. Imbagħad tistampa dak xuy huwa. Imbagħad jgħid, iskambji, dot dot dot. Imbagħad hija tallega li ssejjaħ funzjoni imsejħa tpartit, li jgħaddi fil x u y, l-idea ta 'liema huwa li nisperaw xuy se terga 'lura differenti, l-oppost. Imbagħad titlob skambjat! ma 'punt exclamation. Imbagħad tistampa xuy. Iżda jirriżulta li din ħafna dimostrazzjoni sempliċi isfel hawnhekk huwa attwalment buggy. Anke jekk jien tiddikjara temporanju varjabbli u temporanjament tqegħid fis dan, allura jien jassenjaw mill-ġdid a l-valur ta 'b - li jħoss raġonevoli, għaliex stajt salvati kopja ta 'temperatura fil-. Imbagħad I taġġorna b lill ugwali kwalunkwe kien fl temperatura. Din it-tip ta 'logħba qoxra ta' ċaqliq ta ' fis bu b ġo billi jużaw dan middle-raġel imsejjaħ temp iħoss perfettament raġonevoli. Imma I jsostnu li meta I run dan kodiċi, kif jien ser tagħmel issa - let me imorru quddiem u paste fil hawn. I ser sejħa dan noswap.c. U kif tissuġġerixxi l-isem, dan mhuwiex se jkun programm korretta. Jagħmlu noswap. / Le swap. x hija l-1, y huwa 2, iskambji, biddlu. x hija l-1, y huwa 2. Dan huwa fundamentalment żbaljat, anke għalkemm dan jidher perfettament raġonevoli lili. U hemm raġuni, iżda aħna mhux qed se jiżvelaw ir-raġuni għadha biss. Għal issa-tieni cliffhanger ridt li tħallik ma huwa dan, tħabbira ta 'tip fuq kodiċijiet kupun. Innovazzjoni tagħna mal-jiem tard din is-sena pprovoka numru mhux trivjali ta 'mistoqsijiet, li kienet Mhijiex l-intenzjoni tagħna. L-intenzjoni ta 'dawn il-kodiċijiet kupun, fejn jekk inti tagħmel parti mill-problema stabbiliti kmieni, u b'hekk jkollna b'jum żejjed, kien verament biex jgħinuk guys jgħinu yourself jibdew kmieni, sort ta 'mill Jingħata inċentiv inti. Jgħinna jiddistribwixxu tagħbija madwar ħinijiet tal-uffiċċju aħjar sabiex huwa tip ta 'win-win. Sfortunatament, I think istruzzjonijiet tiegħi ma ġewx, sa llum, ċar ħafna, hekk I marru lura dan il-weekend u aġġornati l-spec fil akbar, aktar kuraġġuża test li jispjegaw balal bħal dawn. U biss biex jgħidu li aktar pubblikament, bi inadempjenza, settijiet problema huma dovuti il-Ħamis f'nofsinhar, per-sillabu. Jekk tibda kmieni, irfinar parti l-problema stabbilita sal-Erbgħa at 12:00 PM, il-parti li tirrigwarda kupun kodiċi, l-idea hija li inti tista 'testendi iskadenza tiegħek għall- P stabbilit sal-Ġimgħa. Dan huwa, daqsxejn off parti żgħira tal-P stabbiliti relattiv għal dak li tipikament huwa l- problema akbar, u tixtri yourself b'jum żejjed. Għal darb'oħra, jiġrilha inti taħseb dwar il-problema sett, gets inti ħinijiet tal-uffiċċju qabel. Iżda l-problema kodiċi tal-kupun għadu meħtieġa, anki jekk inti ma tissottomettih. Iżda aktar compellingly hija din. (Whisper STAGE) U dawk folks li jħallu kmieni huma gonna jiddispjaċina minnu. Kif huma l-folks fuq il-gallarija. I ruhna bil-quddiem lill-folks fuq il-gallarija għal raġunijiet li se jkunu ċar fil-ftit mument. Allura aħna fortunati li jkollhom waħda ta ' Ex fellows tagħlim ras CS50 fiż kumpanija msejħa dropbox.com. Huma ħafna ġenerożament donat kodiċi tal-kupun hawn għal dan l-ispazju ħafna, li jkun sa mill- soltu 2 gigabytes. Allura dak li ħsibt aħna se nagħmlu dwar dan Nota finali hija tagħmel daqsxejn ta 'giveaway, fejn fi ftit mument, aħna se jiżvelaw ir-rebbieħ u li jkollha kupun kodiċi li inti tista 'imbagħad mur tagħhom website, tip fil, u voila, jiksbu lott kollu aktar spazju Dropbox għall tiegħek apparat u għall-fajls personali tiegħek. U l-ewwel, li jixtiequ jipparteċipaw f'dan tpinġija? OK, issa li jagħmilha saħansitra aktar gost. Il-persuna li tirċievi dan 25-gigabyte kodiċi tal-kupun - li hija ferm aktar konvinċenti mill-tard ġranet issa, forsi - huwa dak li hu bilqiegħda fuq quċċata ta ' kuxxin tas-sedil li taħtu hemm li kodiċi tal-kupun. Inti issa tista 'tfittex taħt kuxxin tas-sedil tiegħek. [Daqq video] -One, tnejn, tlieta. [Screaming] -Inti tikseb karozza! Ikollok karozza! DAVID Malan: Aħna se tara inti l-Erbgħa. -Inti tikseb karozza! Ikollok karozza! Ikollok karozza! Ikollok karozza! Ikollok karozza! DAVID Malan: folks Gallarija, come stabbiliti hawn il-quddiem, fejn għandna ekstras. Kulħadd gets-karozza! Kulħadd gets karozza! [Daqq video END] Narrator: Fil-CS50 jmiss - SPEAKER 5: Oh gosh tiegħi gosh gosh gosh gosh gosh gosh gosh gosh gosh - [Jilgħab UKELELE]