[Daqq tal-mużika] DAVID J. Malan: Dan huwa CS50. U dan huwa l-bidu ta 'tliet ġimgħat. Allura konna ltqajna ħafna ta 'eċċitanti affarijiet li tkopri llum. A lott ta 'opportunitajiet għall- voluntiera up fuq il-palk. U finalment, illum huwa mhux dwar kodiċi livelli kollha. Iżda huwa dwar l-ideat, u huwa dwar algoritmi, u fil-fatt tressaq lura uħud mill l-lezzjonijiet mitgħallma minn żero ġimgħa, fejn recall, aħna introduċew din monstrosity. U l-ispirazzjoni self minn dan, biex tibda biex isolvu dejjem aktar sofistikata problemi algorithmically. Iżda l-ewwel, ftit avviżi. Allura wieħed, jekk inti tixtieq li jissieħbu Persunal CS50 u klassi waqt l-ikla dan il-ġimgħa, kemm hawn u fl Cambridge, u fi New Haven, jekk jogħġbok żur il-kors tal website, fejn URL tista 'tinstab. Lecture dan l-erbgħa se Ma jkun hawn fil Sanders. Dan se jkun online biss, hekk tixgħel fil-website CS50, l jekk hawn fil Cambridge jew New Haven ukoll. U mbagħad problema stabbiliti żewġ hija diġà fil-idejk. Jekk int ma dived fil għadhom, ippermettuli li joffru l-suġġeriment miktuba bil-qawwa li, speċjalment issa, kif il-problema settijiet bil-quddiem, int verament tixtieq li tibda issa, jekk mhux dabble ftit fuq il-weekend jew qabel meta l-ewwel jmorru fuq Ġimgħa, għaliex inti ser issib li dawn mhux qed neċessarjament jitwal jew aktar ta 'sfida għal kull se. Naħseb li inti ser issib li, fi ġenerali, dawn għandhom tendenza li jieħdu bejn wieħed u ieħor madwar istess ammont ta 'ħin. Iżda ċertament jiddependi fuq l-istudent, u jiddependi fuq il-mentalità li magħhom inti approċċ dan. Iżda dejjem, int ser biex tiltaqa 'ma' xi ħajt, u int ser jintlaqtu xi bug, u int biss mhux se tkun kapaċi li nikseb fuqha f'xi punt. U huwa immensament importanti li tkun tista li pass bogħod, jiġu lura l-għada, mur ħinijiet tal-uffiċċju, post fuq CS50 Iddiskuti jew bħalhom, li fil-fatt tikseb mblukkata. Sabiex iżommu dan f'moħħhom. Bidu kmieni kemm jista 'jkun huwa l-aqwa ħaġa li tista 'tagħmel. Allura hawnhekk fejn bdejna il-klassi, fuq żero ġimgħa. U nistgħu jiksbu voluntier hawn biex għinni issib MICs? KOLLOX SEW. Wieqfa diġà. Come fuq up. Raden li l-mod kif huwa sejjer jaħdem. X'hemm isem tiegħek? ALAN Estrada: Alan Estrada. DAVID J. Malan: Alan Estrada. Come fuq up. Għandi pjaċir. ALAN Estrada: Nizza biex jissodisfaw inti. DAVID J. Malan: U inti kienu hawn magħna żero ġimgħa, tal-kors. ALAN Estrada: I kien. I kien. DAVID J. Malan: Allura tista tmur quddiem u jsibu għalina Mike Smith, kif malajr kemm tista '? Malajr kemm tista '. Litteralment dmugħ l-problema fil nofs kif għandek bżonn biex. ALAN Estrada: Um. DAVID J. Malan: Litteralment dmugħ l-problema min-nofs. ALAN Estrada: Oh. Mm. Tajjeb ħafna. DAVID J. Malan: OK. Tajba. Grazzi. ALAN Estrada: Tajjeb ħafna. KOLLOX SEW. DAVID J. Malan: U għalhekk issa, inti stajt fadal l-isfel għal nofs id-daqs tal-problema. Issa, aħna qed isfel sa kwart. Inti tingħata attenzjoni lill liema naħa aħna qed iżżomm? [Laughing] ALAN Estrada: Iva, I think-- DAVID J. Malan: Liema taqsima aħna fil-? ALAN Estrada: mleffi, so. DAVID J. Malan: OK. Iżda Mike Smith huwa għaddej li jkun wara mleffi. So-- [Laughing] Kull dritt. ALAN Estrada: Fejn ninsabu tfittex? DAVID J. Malan: Mike Smith. ALAN Estrada: Mike Smith. DAVID J. Malan: Issa, aħna qed fil kirurġika. Issa, it-tobba. Now-- ALAN Estrada: Let's- ejja jmorru ma reali. Real. DAVID J. Malan: Real. KOLLOX SEW. Jekk għandek bżonn Real. Issa, li mod huwa Mike Smith? ALAN Estrada: Dan il-mod. DAVID J. Malan: Liema mod? ALAN Estrada: Stenna. Dritt M is--? Bdejna with-- DAVID J. Malan: Yeah. Huma qed xellug. Id-dritt tiegħek. ALAN Estrada: Yeah. DAVID J. Malan: hekk Mike fil hawn. ALAN Estrada: What? [Laughing] Bad eżempju, guys. Jiddispjacini. DAVID J. Malan: Dan se jgħallmu inti qabża ta 'siġġu tiegħek. ALAN Estrada: Oh. Oh. Qbadtek. Qbadtek. Oh. Oh. Dan is-- OK, I ltqajna inti. Smith dritt hawn? DAVID J. Malan: Smith, grazie. So I ser iżommu tfittex up Smith? ALAN Estrada: Oh, yeah. No, no, no. Oh, no. Dan huwa minjiera. DAVID J. Malan: Oh, inti ltqajna Smith. KOLLOX SEW. ALAN Estrada: Yeah, I ltqajna Smith dritt hawn. Jiddispjacini, guys. Ħsibt Michael-- we kienu qed ifittxu Michael. Jiddispjacini. DAVID J. Malan: Huwa OK. Kull dritt, issa aħna qed fis Paccini and Sons. ALAN Estrada: Paccini u wliedu. DAVID J. Malan: inti biss u I huma dwar dan. KOLLOX SEW. Sib magħna Mike Smith. Smith. ALAN Estrada: Smith. DAVID J. Malan: Smith. Aħna fl-R għal żibel. ALAN Estrada: Żibel. Oh. Dan se jieħu waqt. [Laughing] DAVID J. Malan: Shoes. Aħna fil-żraben. ALAN Estrada: Issa aħna qed gonna-- DAVID J. Malan: Nizza. ALAN Estrada: Which-- [Laughing] Oh, dan huwa kbir. [Laughing] DAVID J. Malan: Huwa OK. ALAN Estrada: Oh, dan huwa tajjeb. Ma naħsibx li jien ser jkollhom buddies PSAT wara dan. DAVID J. Malan: Tajba. Sporting. ALAN Estrada: Sporting. Um, L, M, N, O, P. DAVID J. Malan: OK. Mela ejja tiċrita dan min-nofs. Orrajt. Dan jispiċċa ħażin xorta waħda, minħabba Mike Smith mhux se jkun fil-yellow pages. ALAN Estrada: Aw. DAVID J. Malan: Le, huwa OK. Imma ejja nippretendu simili hu f'din il-paġna. Allura issa, inti ħadthom fadal il-problema isfel għall-paġna waħda, u sibna Mike Smith. [Cheering] OK, nirringrazzjak. KOLLOX SEW. Dan kien straordinarja. Imma kien għadu aktar mgħaġġel minn tfittxija lineari, fejn nibdew fl- bidu tal-ktieb, u nimxu mod tagħna mix-xellug għal-lemin, eventwalment tfittex Mike Smith. U hekk, jekk il-ktieb tat-telefon kellhom forsi 1,000 paġni, forsi kien jieħu us 10 jew hekk tiċrit paġna. Iżda int tista għenu mimsus assunzjoni matul kollha ta 'dak, li jiġifieri li l-ktieb tat-telefon bil-quddiem kien dak? UDJENZA: Magħżula. DAVID J. Malan: Huwa magħżula. Dritt? Huwa magħżula alfabetikament, hekk li kollha ta 'dawk l-ismijiet u numri huma magħżula mill-l A għall- Z, u alfabetikament bejniethom. Imma llum, aħna issa staqsi il-kwistjoni, ukoll, kif Verizon sar jew it-telefon kumpanija ġġibu fis-istat? Għaliex dan huwa ħaġa waħda li jwieżen din il-preżunzjoni, u għalhekk, issolvi problema ma ' algoritmu b'mod aktar effiċjenti. Imma aħna qatt verament talab żero ġimgħa, ukoll, kemm ma jiswa Verizon jew xi ħadd ieħor li tikseb dak il-ktieb tat-telefon sabiex Issortjat? Dritt? Ma jimpurtax jekk tfittex up Mike Smith huwa super fast, jekk din tieħdok a sena biex issolvi l-paġni fil-bidu. Dritt? Inti tista 'ukoll biss ffiltrati permezz ta 'ktieb tat-telefon randomised, jekk li għaddej biex tkun super għaljin biex sort. Mela jekk jista 'jkollna voluntier ieħor. Ejja tagħti ħarsa up hawn fuq kif aħna might-- jaqgħu fuq up-- kif nistgħu tmur dwar għażla dawn. U jekk Ġordan jistgħu attwalment jingħaqdu magħna up here fuq il-palk. Come fuq up għal ftit mument. X'hemm isem tiegħek? CAROLINE: Caroline. DAVID J. Malan: Caroline, jaqgħu fuq up. U tkun taf tkun magħquda minni u l-Ġordan hawn. Caroline, nirringrazzjak. Kull dritt. Allura dak li għandna hawnhekk għal Caroline huwa 26 kotba blu li FAS juża biex jamministraw ċerti eżamijiet finali. Dawn huma jkollna diffiċli li ssib, imma dak li aħna ghamilt bil-quddiem hija li konna tpoġġi l-isem ta 'xi ħadd fuq quddiem ta 'kull wieħed minn dawn, imma konna żammha sempliċi mill imbagħad tqegħid barra ismijiet sħaħ. Allura aħna se tpoġġi l-persuna bl-isem L, D, J, B, it-triq A sa Z, iżda dawn qed sabiex każwali. U hekk jekk inti, jitkellem tiegħek mod permezz tal-problema kif inti tagħmel dan, inti tista 'tmur quddiem u sort dawn għalina, minn A sa Z. UDJENZA: OK, so L huwa simili,-nofs. C qed jibda. B. J qabel L. B, Q. DAVID J. Malan: Żomm li maħsub għat-tieni waħda. Minħabba xort'oħra, dan huwa biss interessanti għalik, lili, u l-Ġordan. Hemm immorru. UDJENZA: [inaudible]. R. DAVID J. Malan: OK. X'Ser tagħmel? CAROLINE: M jiġi wara O. DAVID J. Malan: OK. CAROLINE: O. DAVID J. Malan: O, Good. CAROLINE: E. DAVID J. Malan: E, F. Yeah. CAROLINE: T, U, V. DAVID J. Malan: V, T, U, V. Għalhekk qisu int making-- jibqgħu għaddejjin. Jidher qisu int tagħmel munzell kbir hawn, u tip ta 'munzell kbir hemmhekk. Allura l-ewwel nofs tas-alfabett, tieni nofs tas-alfabett. KOLLOX SEW. Tajba. Tip ta 'qsim il-problema fi tnejn. M, N, X. Yeah. CAROLINE: K. DAVID J. Malan: OK. K. Allura int it-tip ta 'għażla minnhom wara xulxin, tqegħid jew tax-xellug jew il-lemin, jew tal Z għaddej fuq l-art. KOLLOX SEW. CAROLINE: Z għaddej fuq l-art. DAVID J. Malan: OK. Y huwa għaddej fuq l-art. Issa nistgħu npoġġu X. CAROLINE: G. DAVID J. Malan: l G għaddejjin xellug. S huwa għaddej dritt. Kull dritt, A huwa għaddej it-triq kollha xellug. CAROLINE: A, B, C, D. DAVID J. Malan: Issa, tajba. Imxejna ltqajna A, B, Ċ W għaddej stabbiliti hemmhekk. Dritt kollox, T. CAROLINE: H, I, J. DAVID J. Malan: H, I, J. Tajba. CAROLINE: Fiċ-ċentru, jien gonna-- DAVID J. Malan: OK. Allura issa, aħna qed tmur biex tip ta 'jingħaqdu dawn piles varji. Allura A sa C, imbagħad nara D, u E, u F, u G, u H, u I. Nizza. J, K. U mbagħad, dan pile huwa rasu 'l isfel, iżda li OK. Sure. Aħna tista 'tnaqqas xi kantunieri. KOLLOX SEW. U allura għandna bżonn W, X, Y, Z. CAROLINE: Yeah. DAVID J. Malan: Eċċellenti. Allura big gracias għal Caroline għall-għażla dawn. [Cheering] Grazzi. Grazzi ħafna. Allura issa ejja jikkunsidraw għal mument kif Caroline marru dwar kif isir dan, u dak eżattament aħna kienu kapaċi to-- kif aħna kienu kapaċi ssolvi din meta problema konna biss mogħti mazz sħiħ ta 'inputs każwali. Ukoll, jidher qisu hemm kien daqsxejn ta 'sistema hemmhekk? Dritt. Allura l-ittri preċedenti fl-alfabett, hi kien tqegħid lejn ix-xellug, u l- ittri aktar tard fil-alfabett, hi kien tqegħid fis-lemin. U hekk kif hija sabet xi ittri prossimali, dawk li jmorru dritt ħdejn xulxin, hi tqiegħed dawn fl-ordni. U hekk aħna tip ta 'kellhom dawn żgħir munzelli ta 'inputs magħżula jseħħu. U hekk dan huwa pjuttost bħal dak Ħafna minna bnedmin ser jagħmlu. Nixtiequ tip ta ffiltrati permezz tagħha, u aħna'd tip ta jkollhom mekkaniżmu. Iżda jista 'jkun diffiċli li tikteb l-isfel fil-formula per se. Huwa ħass ftit aktar organiku minn dak. Mela ejja ara jekk nistgħu issa marbut il-problema b'inqas inputs. Minflok ta '26, ejja jagħmel xi ħaġa ferm inqas ma biss jgħidu, seba ', wara dawn il-bibien, biex ngħidu hekk. Hemm biss seba 'numri? U jekk l-għan issa fil idejn huwa li tinstab valur, ejja ara kif effiċjenti nistgħu tmur dwar kif isir dan. U ejja ara jekk nistgħu issa jibdew japplikaw xi numri, jew xi formuli li biex jiddeskrivu l-effiċjenza tal-ktieb tat-telefon tagħna algoritmu, tagħna algoritmu ktieb eżami, u b'mod aktar ġenerali, il-konstatazzjoni informazzjoni. Allura għal dan, let me imorru quddiem u fuq il-touch screen hawn fuq, imqiegħed web browser li għandha eżattament dawn is-seba bibien. U jekk nistgħu jiksbu ieħor voluntier biex jitla fuq minn hawn, Stajt jitqiegħdu dawn l-istess bibien hawn. Quick voluntier. Dan demos one-- tmur għal aktar malajr u aktar malajr issa. Come fuq l isfel. X'hemm isem tiegħek? Trevor: Trevor. DAVID J. Malan: Trevor? Kull dritt, Trevor, jaqgħu fuq l isfel. Allura Trevor offriet hawn biex do problema simili, iżda wieħed li ambitu iktar ristrett, u li għaddej li inessu jipprova jifformalizzaw issa il-proċess għall-għażla dawn in-numri. Allura Trevor, sbieħ li jissodisfaw inti. Allura hawnhekk huwa firxa, biex jitkellmu, lista ta 'seba' bibien. Jimxi 'l quddiem u issibna-numru 50. U mbagħad wara l-fatt, jgħidulna kif inti sabuha. Jekk be-- id-dritt. Yeah, dan huwa l-waħda hawn? Uh-oh. KOLLOX SEW. Inti għafast li wieħed. Tajba. U tajjeb. Issa inti għafast li wieħed. U let me jagħtuk l-mikrofonu, sabiex ikollok fi ftit mument. Jimxi 'l quddiem u kklikkja l- bieb li jmiss li għandek il-ħsieb. Iva, tajjeb. Trevor: Nista unclick bieb? DAVID J. Malan: Le, inti ma tistax unclick. Trevor: OK. Dan wieħed. DAVID J. Malan: Meta inti tixtieq li tmur? Liema? Trevor: Li wieħed. DAVID J. Malan: Le Trevor: OK. Dan wieħed. DAVID J. Malan: Iva. Dan kien tajjeb. Kull dritt. Allura dak li kien algoritmu tiegħek jew proċedura biex isir dan, Trevor? Trevor: I biss marru permezz bibien sakemm sibt 50. DAVID J. Malan: OK. Algoritmu eċċellenti. Allura li l-multa. Minħabba fil-fatt, jekk I jiżvelaw x'hemm wara dawn iż-żewġ bibien oħra, dak aħna ser issib hawnhekk huwa li aħna biss input każwali. Allura li kien effettivament bħala tajba kif int jista 'jkollok. U fil-fatt, inti ltqajna aħjar minn b'mod eżawrjenti tfittex l-firxa sħiħa, għaliex kien ikun verament unlucky jekk inti laqat in-numru 50 fl-aħħar bieb. Imma dak jekk aħna minflok ħadt suppożizzjoni. Ejja ngħidu I sort kollha dawn il-bibien madwar, sabiex ikollok l- numri magħżula din id-darba, iżda din id-darba huwa attwalment a different-- dan iż-żmien, huwa attwalment magħżula għalik. U issa l-għan fil-idejn huwa li tolqot l-għadd 50. Trevor: OK. DAVID J. Malan: X'hemm algoritmu tiegħek se tkun? Trevor: Well, jekk huwa magħżula, huwa jew ser li be-- jekk akbar għall-akbar, dixxendenti, dan ser ikun l-ewwel wieħed, jew jekk huwa l-oppost, se jkun l-aħħar wieħed. So I ser biss vit dan il-bieb, u allura biss tisfrutta l-aħħar bieb. DAVID J. Malan: Eċċellenti. Kull dritt. Allura sibna l-għadd 50. Allura hekk kif inti taf kienu magħżula, aħna kienu kapaċi li jwieżen din il-preżunzjoni. Allura jkunu wisq simili l-eżempju ktieb tat-telefon. Hekk kif ikollok, anke ma problema żgħira bħal dan, inputs tiegħek magħżula minn qabel, nistgħu attwalment sib il-valur forsi b'mod aktar effiċjenti. U jien ma jgħidlek jekk kien magħżula żgħar għall-kbar, jew kbar lill-intrapriżi żgħar, u allura kien raġonevoli ħafna li tibda f'tarf wieħed jew l-oħra li attwalment issib dak il-valur fil-mira. Allura nirringrazzja lil Trevor kif ukoll. U jien ser propose-- nicely jsir. Għandna clip ftit, fil-fatt, li hija fost mumenti favoriti tagħna fil CS50, li biha xi kultant dawn demos ma pjuttost tmur skond il-pjan. U fil-fatt dritt issa, I jinġibed l-interface ħażin li biex jużaw l-touch screen. Allura li kien tort tiegħi hemm. Allura dan se tagħmel għal clip sena d-dieħla kif għaliex I kien tikklikkja fuq l-iskrin tiegħi stess. Imma ejja tagħti ħarsa lejn dak li ġara aħħar sena ma Jay, li ħareġ, ħafna bħal Trevor hawn, volontarju, u f'dan il-clip qasir, tkun taf tara kif din l-istess demo ma pjuttost jiżvelaw l-istess lezzjonijiet meħuda. [Daqq video] -il Nixtieq li tagħmel issa huwa biex isibu għalija, u għalina, tassew, in-numru 50 pass wieħed fi żmien. -Il Numru 50? -Il Numru 50. U inti tista 'tikxef x'hemm wara kull waħda minn dawn il-bibien sempliċiment billi tmiss ma 'saba'. Kkritikat dan. [Laughing] [END Daqq] DAVID J. Malan: Allura li marru tajjeb ħafna. Dawn kienu l-bibien mhux magħżul. U Jay, naturalment, sabuha wisq malajr. Trevor għamlet xogħol aħjar f'termini ta 'mument teachable, biex ngħidu hekk, din is-sena jieħu iktar li jsibuha. Of course, allura aħna taw Jay opportunità oħra, li biha aħna magħżula l-bibien, hekk kif għamilna għal Trevor, u Trevor ma super tajjeb dan iż-żmien. Iżda Jay ma kien nofs malajr. [Daqq video] -Il-Għan issa huwa li wkoll issibna-numru 50, iżda tagħmel dan algorithmically, u jgħidulna kif int ser dwar dan. -KOLLOX SEW. -u Jekk issibha, inti żżomm il-movie. Jekk inti ma jsibuha, inti tagħti lura. -Man. -OH! - [Inaudible] OK. Hekk jien ser jiċċekkja l-truf ewwel biex jiddeterminaw jekk there's-- Oh. [Applause] [END Daqq] DAVID J. Malan: OK. Allura issortjar bibien biċ-ċar iwassal għal aktar effiċjenza. U hekk, darbtejn aktar malajr huwa dak I fisser hemmhekk. U hekk Jay ltqajna xxurtjati kemm żminijiet. U hu wkoll ltqajna xxurtjati f'dak aħħar sena, I ordnat xi diski Blu-ray li attwalment jagħtu. Jien sorry din is-sena, aħna ma kellhomx l-istess, Trevor. Iżda aħjar minn hekk kien ftit snin lura. U xi wħud minnkom tista 'taf dan sħabi, Sean, li meta kien fil CS50, ġiet ikkontestata bl-eżatt istess problema, għalkemm SD, kif tkun taf hekk ara, lura fil-ġurnata. U inti ser issib li mhux biss ma huwa jieħu ftit itwal minn Jay, ftit itwal milli Trevor, kien fil-fatt din l-opportunità mill-isbaħ li jidħlu kważi kulħadd fil- folla a la Prezz huwa Dritt, l-inkoraġġiment lilu biex issib in-numru konna qed ifittxu. Ejja. tagħti ħarsa. [Daqq video] -KOLLOX SEW. Allura kompitu tiegħek hawn, Sean, hija din li ġejja. Għandi moħbija wara dawn bibien in-numru sebgħa. Iżda tucked bogħod f'xi wħud minn dawn il-bibien kif ukoll huma numri negattivi oħra. U l-għan tiegħek huwa li wieħed jaħseb ta 'din il-filliera ta' fuq ta 'numri bħala biss firxa, jew biss sekwenza ta 'biċċiet tal-karti bin-numri warajhom. U l-għan tiegħek huwa, biss tuża l-quċċata firxa hawn, issib lili in-numru sebgħa. U aħna mbagħad se critique kif inti tmur dwar kif isir dan. -kull Dritt. -Sib Us-numru sebgħa, jekk jogħġbok. No Ħames, 19, 13. [Laughing] Mhuwiex kwistjoni trick. One. [Laughing] Wara dan, score tiegħek ma tantx hu tajba, sabiex inti tista 'ukoll jibqgħu għaddejjin. Tlieta. [Laughing] Mur fuq. Franchement, I iżda ma jistax jgħin wonder dak li qed ma jaħsbu dwar, so-- [Laughing] Biss il-filliera ta 'fuq, so inti stajt ltqajna tliet xellug. Allura ssib lili sebgħa. [Laughing] 17. Sebgħa. [Applause] Kull dritt. [END Daqq] DAVID J. Malan: Allura nistgħu watch dawn ġurnata kollha. U ovvjament, xi wħud demos din is-sena forsi issa se jispiċċaw fil jmiss video is-sena ukoll. Allura issa ejja fil-fatt tiffoka fuq l-algoritmi hawn, u ara jekk ma nistgħux issa tibda biex tifformalizza kif nistgħu tmur dwar jkollna data tagħna fis dan l-istat li huwa magħżula, sabiex finalment, nistgħu attwalment tfittxija b'mod aktar effiċjenti. U anki jekk aħna qed tmur tuża settijiet ta 'data pjuttost żgħar, bħall-tmien numri aħna hawn fuq il-bord, jista 'finalment japplikaw dawn l-istess ideat 1,000 inputs, miljun inputs, 4 biljun inputs, minħabba li l-algoritmi ser ikunu fundamentalment l-istess. U għalhekk dan huwa aħħar tagħna opportunità għall-voluntiera llum, imma forsi l-aktar waħda involut, li għalihom hemm bżonn tmien voluntiera biex toħroġ u jimxu lilna permezz tal- proċess ta 'għażla x'se dalwaqt jkun fuq dawn il-mużika stands hawn. Nibda lura hawn. Allura wieħed fil-green turquoise-- huwa? Inti jikkommettu? Tnejn. Come fuq l isfel. KOLLOX SEW. Tlieta. Erbgħa. Ħalli me-- OK, ħamsa. Int jiġi nominat minn ħabib tiegħek. Sitta, seba ', u tmienja. Come fuq up. Kull dritt. Grazzi ħafna. Come fuq up. Come fuq up. Kull dritt. Allura dak li għandna here-- u dan hija fost dawk l-aktar skomdi, peress li dan se jeħtieġ li inti Humer me għal ftit ftit ftit ta 'żmien. Inti għandu jkun in-numru wieħed. X'hemm isem tiegħek? Annan: Annan. DAVID J. Malan: Annan. David. X'hemm isem tiegħek? JOSEPH: Joseph. DAVID J. Malan: Joseph, inti numru tnejn. Serena: Serena, numru tlieta. Stefan, numru erbgħa. Cynthia: Cynthia. DAVID J. Malan: Cynthia, numru b'ħames. [Inaudible] DAVID J. Malan: [inaudible]. David, numru sitta. MATT: Matt. DAVID J. Malan: numru Matt sebgħa. U? WAVERLY: Waverly. DAVID J. Malan: Waverly, numru tmienja. Kull dritt. Jekk inti could-- Whoops. Jekk inti kollha, kif tiegħek ewwel sfida, hemm tmien stands mużika hawn qed tiffaċċja l-udjenza. Jekk inti tista 'tpoġġi numri tiegħek fuq dawn mużika stands b'tali mod li huma bi dritt il istess numri fuq il-bord. Sabiex tagħmel infuskom look like li billi tqegħid numri tiegħek fuq dawn il-mużika stands hawn. Eċċellenti s'issa. Eċċellenti. KOLLOX SEW. Allura issa, aħna qed tmur biex titlob lill- kwistjoni fi ftit modi differenti. Kif nistgħu tmur dwar għażla dawn folks up hawn? Minħabba kellna approċċi ftit qabel, fejn konna tip ta 'teħid żewġ bramel differenti. U allura konna ġeneralment piecing affarijiet flimkien. Hekk kif rajna żewġ numri li jappartjeni flimkien, npoġġux flimkien. Żewġ ittri li jappartjenu flimkien. Imma ejja ara jekk irridu ma jistgħux jifformalizza dan, sabiex inkunu finalment ikollhom xi-kodiċi psewdo inti se, li magħhom inti tista 'ssolvi dawn il-problemi. Allura issa, jien tfittex lejn dawn in-numri hawn. U nara mazz sħiħ ta 'żbalji. Fl-aħħarnett, nixtieq wieħed fuq il- xellug u tmienja fuq il-lemin. U hekk jien tħares lejn dawn iż-żewġ, erba 'u tnejn. U x'inhu l-problema, ovvjament? Yeah. So. Żewġ ovvjament jasal quddiem erba, sabiex inti tkun taf liema? Let me ewwel jieħdu approċċ greedy, jekk inti se, ħafna problema simili sett one-- jekk inti recall mill- Standard Edition tal Problema Set One, fejn I biss lokalment ssolvi l-problema li d-dritt hawn quddiem lili u ara fejn din twassal me. KOLLOX SEW. Allura tnejn u erbgħa, let me go quddiem u biss tpartit inti tnejn. Jekk inti tista fiżikament jiċċaqalqu infuskom u karta tiegħek, I jidhru li gotten l- lista fi stat aħjar. Issa, dawn qed tajba. Jien ser jimxu fuq, erba 'u sitt, jidher tajjeb. Mhux problema. Sitt u tmienja, OK. Tmien u wieħed, problema oħra. Għaliex dak veru madwar tmien u waħda? Wieħed jasal quddiem tmienja, u iva, liema għandu nagħmlu? Ejja tpartit dawn iż-żewġ. Wieħed u tmienja. U issa, jien ser jibqgħu għaddejjin. Jien ser ikompli jfittex l quddiem. U ejja ara dak li jiġri. Tmien u tlieta, ta ' Naturalment, out of order. Ejja tpartit. Tmien u sebgħa, tal-kors. Out of order. Ejja tpartit. Tmien u ħamsa, naturalment, ejja swap. Kull dritt. Lista hija magħżula. iva? OK, ovvjament le. Iżda huwa xi ftit aħjar, right? Minħabba avviż dak li ġara. Kull darba għamilna swap, iżgħar Numru tip ta perkolati il-mod, u numru akbar perkolati B'dan il-mod, jew aħna ser tibda tgħid effervexxentement għall- xellug jew effervexxentement lejn il-lemin. Issa, mhuwiex biżżejjed, għax fl-aħjar numru jista mxew fuq il-post wieħed quddiem, jew fl-agħar, numru jista 'jkollhom mċaqalqa post wieħed ieħor. Allura inti taf liema, dan it-tip ta ħadmu pretty ukoll s'issa. Let me biss tipprova mill-ġdid. Tnejn u erbgħa, dawn qed OK. Erba 'u sitt, dawn qed OK. Sitt xhur u, out of order. Mela ejja tpartit inti tnejn. U issa, avviż-problema tibda tikseb ftit aħjar mill-ġdid. Sitt u tlieta, out of order. Ejja tpartit inti tnejn. Sitt u sebgħa, int tajba. Seba u ħamsa, naturalment, out of order. Seba u tmienja, fl-ordni. U issa, I jista 'jeħtieġ li tagħmel dan ftit aktar drabi. U fil-fatt, naħseb għall yourselves forsi kif ħafna drabi maximally jista I jkollhom jimxu quddiem u lura? Aħna ser terga 'lura għal dan. Allura tnejn u erbgħa għadhom OK. Erba 'u waħda, Nope. Allura, ejja swap. U għal darb'oħra, l-avviż viżwalment wieħed huwa tip ta 'tbaqbieq lejn ix-xellug, meta dan għandu jkun. Erba 'u tliet tpartit. Erba 'u sitt. Sitt u ħames swap. Sitt u sebgħa. Seba u tmienja huma tajbin. Tajba. Aħna jkollna anki aħjar. Mela ejja ara. Issa, għandna żewġ u wieħed. Of course, tpartit. Tnejn u tlieta, tlieta u erba ', erba' u ħames, sitt u seba ', seba' u tmien. Tajba. U inti taf liema? Minħabba I magħmula tibdil wieħed hemm, let me do check sanità wieħed. Let me tmur it-triq lura għall-bidu. KOLLOX SEW. Waħda, two-- Yup, ara? Xi ħaġa kienet żbaljata. Tlieta, erba ', ħames, sitt, seba', tmien. U f'dan l-aħħar pass, huma inti komdu ma issa tiegħi li qal li huwa magħżul? KOLLOX SEW. Viżwalment, dan huwa assolutament veru. Imma funzjonalment, dak ma wkoll jiġri biss F'dan l-aħħar pass li jippermettilek biex jikkonfermaw li din il-lista huwa tabilħaqq magħżula? What did I do jew ma tagħmel dan jgħaddi l-aħħar? UDJENZA: Ma kienx hemm tibdil. DAVID J. Malan: Jiddispjacini? UDJENZA: L-ebda bidla. DAVID J. Malan: Ma kienx hemm tibdil. Hekk ikun stupid ta 'lili li tagħmel dan algoritmu istess mill-ġdid jekk I ma tagħmel l-ebda bidliet l-ewwel darba. U l-istat ma nbidlitx. Żgur, jien mhux ser jagħmlu kwalunkwe bidliet it-tieni darba. U għalhekk, huwa sikur issa ngħid, lista hija magħżula. U fil-fatt, dan issa huwa xi ħaġa li aħna ser ġeneralment sejħa sort bużżieqa, fejn pairwise, inti jikkoreġu żbalji mill-ġdid, u għal darb'oħra, u għal darb'oħra, u inti jibqgħu għaddejjin quddiem u lura, u quddiem u lura, sakemm inti jagħmlu l-ebda swaps bħal dawn, f'liema punt inti tista 'tkun kunfidenti, yeah, I lest li jiffissa l-iżbalji. Ejja reset u jippruvaw approċċ ieħor. Jekk inti guys tista 'tmur lura fil l-ordni li inti kienu eżempju ilu, li dehru qishom dan. Issa, ejja tagħti approċċ ta 'l- ftit aktar bħall-ktieb eżami, li biha konna dejjem għażla tal-ittra tal-alfabett li aħna tip ta 'riedu biex jittrattaw jmiss. Forsi kien ittra għolja, bħal A, jew ittra Z. baxx Allura kulħadd lura f'din l-ordni. U issa let me tagħmel dan. Ejja naraw I know I jkollhom tmien numri hawn. Jien ser jimxi 'l quddiem u biss deliberatament tagħżel l-iżgħar elementi. Dritt? Dan jidher intuwittivi wisq. Għaliex ma nista 'nsib l-iżgħar element, poġġih fejn jappartjeni, mbagħad jiksbu l-element li jmiss iżgħar, tpoġġi fejn hi jappartjeni, u biss jirrepetu. Minħabba intuwittivament, li għandha taħdem wisq. Allura erba, li l-għadd pretty żgħir. Jien ser tiftakar fejn dan ikun. Stenna minuta. Tnejn hija iżgħar. Let me issa tiftakar fejn żewġ huwa, u tinsa dwar erbgħa. Aħna ser jittrattaw dan aktar tard. Sitta, jien ma interessati. Tmienja, jien ma interessati fil. Wieħed huwa numru żgħir ġdida tiegħi. Hekk jien ser tiftakar fejn wieħed hu. Tliet, mhumiex interessati. Seba ', mhumiex interessati. Ħames, mhumiex interessati. Allura mingħajr ma joħorġu barra l-istadju din is-sena, Jien ser grab numru one-- u dak li kien l-isem tiegħek mill-ġdid? Annan: Annan. DAVID J. Malan: Annan. U jekk inti tista 'tingħaqad miegħi fl il-bidu tal-lista, ejja tpoġġi lilek fejn inti jappartjenu. Unfortunately-- x'hemm isem tiegħek? STEFAN: Stefan. DAVID J. Malan: Stefan hija fil-mod. Għalhekk qabel ma Stefan issolvi din problema, x'għandi nagħmlu? X'nagħmlu ma 'Stefan? UDJENZA: [inaudible]. DAVID J. Malan: OK. Allura nistgħu nagħmlu dan. Nistgħu tip ta 'jieħu Stefan u tiegħu erba, u biss jitqiegħed fil-varjabbli u jżommu lill lilha għall xi ammont ta 'żmien, b'hekk tagħmel spazju għal numru wieħed. U li mhux ħażin. I tista 'tissuġġerixxi, għaliex ma aħna biss jitqiegħed Stefan hawn? Għaliex jista din tikser wieħed mill-ideat bdejna jitkellem dwar aħħar darba, l-aħħar ġimgħa? Yeah? UDJENZA: [inaudible]. DAVID J. Malan: M'hemm l-ebda indiċi għal dan. Jekk taħseb ta 'dan, fil-fatt, bħala diodi, din hija bħal wieħed negattiv, b'hekk m'hemm l-ebda memorja attwalment hawn jekk dan huwa verament firxa, bħal aħna ddikjarat ġimgħa li għaddiet fil lecture. Allura aħna ma għandhom jagħmlu dan. Aħna jista 'jaħżen fil varjabbli. Jew inti taf liema? Smajt xi ħadd ieħor jissuġġerixxu dan. X'aktar jista nagħmlu ma 'Stefan? Għaliex ma aħna biss tkeċċi lilu u jniżżlu fuq fejn numru wieħed kien. Mela jekk inti tixtieq li tmur hemmhekk. U fil-fatt, dan huwa Soluzzjoni pjuttost tajba. Issa minn naħa, stajt tip tal għamel il-problema agħar. Erba issa huwa farther bogħod minn meta dan għandu jkun. Għandu jkun lejn Din it-taqsima. Imma inti taf liema? Li seta 'kien xortih ħażina. Forsi numru tmienja kien hawn. U hekk, forsi aħna se gotten xxurtjati, u mbuttati tmienja eqreb lejn l-aħħar. Għalhekk fl-aħħar tal-ġurnata, Huwa tip ta 'medji kollha barra. M'għandniex bżonn għall-kura dwar erbgħa. All I care about dritt issa huwa għażla tal-element iżgħar. U issa, dak li jien ser tagħmel huwa tinsieh numru wieħed b'mod permanenti, għaliex naf l- Lista lura lili issa huwa magħżul. Allura lista tiegħi kien preċedentement daqs tmienja. Issa, huwa ta 'daqs seba'. Allura problema tiegħi huwa jkollna iżgħar, għalkemm lineari. Allura issa, jien ser jagħżlu l- element iżgħar kurrenti, tnejn. Sitt, tmien, erba ', tlieta, seba, ħamsa. Dan kien l-iżgħar element. Allura dak am I se jagħmlu with-- dak li kien l-isem tiegħek mill-ġdid? JOSEPH: Joseph. DAVID J. Malan: Joseph? Aħna ser tħalli Joseph fis-seħħ. Issa, jien ser nippretendu li dawn guys are-- ukoll, Naf li dawn iż-żewġ huma diġà magħżula. Ejja issa jiffokaw fuq l- bqija tal-lista. Sitt huwa l-iżgħar kurrenti. Tmien huwa akbar. Erba issa huwa l-iżgħar kurrenti. Tliet issa huwa l-iżgħar kurrenti. U hekk issa, jien ser tagħżel tlieta, li is-- x'hemm isem tiegħek mill-ġdid? Serena: Serena. DAVID J. Malan: Serena, jekk inti tista grab numru tiegħek u tpartit with-- KALSANG: Kalsang. DAVID J. Malan: Kalsang. Come fuq dahar, u aħna qed ser tpartit dawn iż-żewġ. U issa, ejja tpoġġi dan fuq awtopilota. Jien se jmorru u tħalli f'idejn l inti guys li jagħżlu l-elementi li ġejjin iżgħar. Dun, Dun, Dun, Dun. Numru erbgħa, x'għandek tagħmel? Eċċellenti. Issa, jien ser jagħmlu pass ieħor. Dun, Dun, Dun, Dun. Nara ħamsa huwa l-iżgħar jmiss. Issa, jien ser tieħu pass ieħor. Dun, Dun, Dun, Dun. Sitt huwa l-iżgħar. Tajba. Seba huwa l-iżgħar. L-ebda bidla. Tmien huwa l-iżgħar. Jsir. Allura dak li aħna ħadthom biss isir mill iteratively tagħżel element wieħed wara l-oħra huwa jimplimenta xi ħaġa li aħna qed ser jifformalizzaw mill sort għażla. U huwa forsi anke aktar sempliċi li tispjega, f'dak litteralment kull ma għandek trid tagħmel huwa biss iżommu tmur quddiem u lura permezz tal-lista għażla, l-element li jmiss iżgħar, sakemm inti qed isir. Allura huwa saħansitra aktar sempliċi, forsi intuwittivament, minn aħħar. Ejja nippruvaw aħħar wieħed wieħed. Jekk inti guys tista reset yourselves fil-pożizzjonijiet li ġejjin finali ħin, ejja ara jekk ma nistgħux issa tifformalizza approċċ ieħor. Fil-fatt, kieku xi ħadd hemmhekk tixtieq tipproponi kif inkella nistgħu tmur dwar kif isir dan? Mingħajr tossing out buzzwords jew tip ta 'tweġibiet li huma diġà magħrufa, biss intuwittivament, dak li nistgħu nagħmlu? UDJENZA: [inaudible]. DAVID J. Malan: Yeah. Allura hemm xi intuwizzjoni kbira hemmhekk. Affarijiet tajba jidhru li jiġri s'issa fix-xjenza tal-kompjuter meta aħna jaqsam u jirbħu l-problema ta 'diviżjoni min-nofs u nofs u nofs. U hekk fil-fatt, aħna tista 'tibda tagħmel dan. U fil-fatt, li għaddej biex tkun, aħna ser tara, wieħed mill-aħjar soluzzjonijiet tagħna s'issa. Imma ejja terġa 'lura għal li qabel twil. Fil-fatt, aħna qed tmur biex tagħmel li ftit aktar tard din il-ġimgħa. X'iktar jista nagħmlu biex issolvi din? Allura kulħadd hawnhekk huwa ordni apparentement każwali. Taf xiex? Pjuttost milli jmorru quddiem u lura, quddiem u lura, u lura kull darba, dan iħoss bħal Jien jagħmlu ħafna mixi. Għaliex ma I biss tibda fil il-bidu tal-lista, u biss jitqiegħed erba fejn jappartjeni? So let me tħallas għall-mument li lista tiegħi huwa biss dan l-ewwel element. Huwa erba magħżula f'dan il-mument fil-ħin, jekk kollox I care about huwa kollox hawn? Dan huwa tip ta 'trivially vera, right? Bħall-lista li fiha numru wieħed, u dak in-numru erbgħa hija ovvjament magħżula. So let me biss jistipulaw li din il-lista huwa magħżul. Imma issa għandi l-bqija ta 'din il-lista. Allura issa, I jiltaqgħu tnejn. Fejn ma żewġ ovvjament jappartjenu rigward erba? Qabel erbgħa. Allura x'nista 'nagħmel hawn? X'hemm isem tiegħek mill-ġdid? JOSEPH: Joseph. DAVID J. Malan: Joseph, jekk inti tista 'pass lura għal ftit mument bin-numru tiegħek. U issa dak li għandu Stefan tagħmel hawn? Ejja bidla Stefan hawn. U issa, let Joseph jaqgħu fil hawn. U issa, let me jsostnu li kollox hawnhekk huwa magħżul. Allura, riżultat simili, iżda approċċ fundamentalment differenti. I lanqas biss ħares x'hemm stabbiliti hemmhekk. I biss iżommu tieħu l-elementi kif dawn qed tingħata lill lili, u kif jittrattaw magħhom. Allura issa, nara numru sitta. Fejn ma numru sitta jappartjenu? Għandna żewġ, erba, sitta. Eżattament fejn hi dritt issa. Mela ejja jħallu dak biss, u issa isostnu li din il-parti tal-lista issa huwa magħżul. U għalhekk, dan iħoss fundamentalment differenti li jien biss jiċċaqalqu permezz tal-lista hawn linearment, u jien qatt ma irduppjar lura. Iva. Kull dritt. Allura tmienja, fejn do inti jappartjenu? Dritt hawn. Perfect. Allura issa, wieħed. Uh-oh. Dan iħoss simili huwa se jiġu jiswew ħafna flus. Issa, fil-algoritmu ta 'qabel, I biss biddlu nies. So I tista 'tpoġġi lilu-triq kollha lejn il-bidu, iżda mbagħad għaddiet Joseph. Imma jekk nimxi Joseph, issa dak li għaddej biex tkun ħażina? Issa, stajt tip ta undone-- stajt meħuda pass 'il quddiem u mbagħad pass wieħed lura, minħabba li issa Joseph ikun out of order. Mela ejja tagħmel dan. Jekk inti tista 'tieħu numru wieħed u pass lura għal ftit mument. Kif nistgħu put-- dak kien l-isem tiegħek mill-ġdid? Annan: Annan. DAVID J. Malan: Annan fis-seħħ? Dak li jeħtieġ li jiġri fir-rigward għal żewġ, erba ', sitt, u tmienja? Dawn kollha għandhom bżonn għal bidla. Mela jekk tmienja tixtieq li ċċaqlaq ewwel, imbagħad sitt, imbagħad erba ', imbagħad tnejn. U mbagħad Annan, jekk youd simili li jaqgħu fil hawn, tajba. Iżda hawnhekk, konna biss tip ta ħallas prezz f'punt differenti fil-algoritmu. Billi aħħar darba bl-għażla sort, u anki bubble sort, Jien mixi lura u raba, u lura, li hija ċertament jingħaddu flimkien -time għaqli, u litteralment gradwali. Sort Inserzjoni, fl-ewwel t'għajn, tidher simili huwa super intelliġenti, f'dak jien biss jagħmlu bil-mod, progress inkrimentali, imma jien mhux ser f'dan il quddiem u lura. Imma jekk xi ħadd ikun tabilħaqq out of order, avviż kollha tax-xogħol I biss kellha tagħmel. I kellha timxi nofs tal-lista biss biex tagħmel spazju għal numru wieħed. Allura huwa l-istess ammont xogħol s'issa dan iħoss, biss tip differenti ta 'xogħol. Ejja tkompli. Allura issa nafu li kulħadd bejn wieħed u tmien huma magħżula. Hawnhekk, I jkollhom numru tlieta. Jekk inti tixtieq li pick up numru tlieta, pass lura wieħed. U dak li inti guys bżonn tagħmel? Yep. Allura dak xulxin, tnejn, tlieta passi. Tliet unitajiet ta 'ħin li biss l-ispiża me, sabiex tliet jistgħu issa joqogħdu. Fl-aħħarnett, seba '. Ejja imorru quddiem u jkollhom tieħu pass lura. Dan huwa biss se ispiża us unità waħda ta 'żmien, iżda li OK. U issa, ħames għaddej biex jkun ftit aktar għaljin. Jekk inti tixtieq li pass lura. Jeħtieġ li nimxu tmienja, u seba ', u sitta. U allura kulħadd issa huwa magħżul. Allura idejn big lil voluntiera tagħna hawn. Grazzi ħafna. [Applause] Nirringrazzjakom ilkoll. Nirringrazzjakom ilkoll. Mela ejja ara issa kemm għalja kollha ta 'dak kien. Ejja jikkunsidraw forsi l- aktar sempliċi ta 'dawn, sort bużżieqa. U jien ngħidlek sempliċi, biss minħabba inti tista issolvi dan greedily bi ftit tiffissa l-problema pairwise hawn. Tiffissa l-problema pairwise hawn, għal darb'oħra u għal darb'oħra u għal darb'oħra, tirrepeti daqs darbiet inti fil-fatt bżonn. Għalhekk jirriżulta li bi speċi bużżieqa, ukoll, kemm passi għandi jieħdu fuq l-ewwel pass ta 'din l-algorithm? I jista take-- ejja see-- waħda, tnejn, tlieta, erba ', ħames, sitt, seba'. U hemm tmien elementi hawn. Allura huwa simili n minus 1 passi biex jiksbu mill-bidu tal-lista sa l-aħħar tal-lista. Iżda ma sort għażla, ifakkar li jien għażla tal-elementi mill-ġdid u għal darb'oħra u għal darb'oħra li l-iżgħar, Jien tqegħid fil-post, iżda mbagħad jien ma tfittex lura lili darb'oħra. So I think huwa ftit aktar ċara allura dak l-ewwel darba, I jista għandek tieħu l n minus 1 passi biex isibu l-element iżgħar. Imbagħad I jpoġġuhom fil-post, u I tkeċċi min kien hawn qabel. Imma mbagħad I ma jkollhom iżommu tħares lejn dan l-element, għaliex naf huwa diġà l-iżgħar. Allura issa, I tista 'tħares lejn biss seba elementi, imbagħad sitt elementi, imbagħad ħames elementi, allura erba 'elementi. U għalhekk matematikament, jekk n hija in-numru ta 'elementi jew numri li bdejna ma ', inti tista' timmaġina li dan huwa l-istess bħal n minus 1, plus n minus 2 passi, plus n minus 3 passi, plus n minus 4 passi, l- triq biss pass wieħed. U jien fuq persuna tiegħi aħħar. U jekk inti recall li ħafna tal stats kotba jew kotba matematika jkollhom dawk formuli fuq il- Hardcover dahar jew ta 'quddiemhom, jirriżulta li din is-serje jista 'jiġi espress b'mod aktar sempliċi kif n darbiet n minus 1 minn 2. U huwa multa jekk dan mhux fuq quddiemnett tal-moħħ tiegħek. Iżda dan huwa minnu. Li jinsab biss mod sempliċi ta 'kitba dan. U allura jekk taħseb lura l-iskola grad, meta tkun għadek tibda multiplikazzjoni affarijiet out, dan il-kors, huwa biss n kwadrat minus n diviż bi 2. All I ghamilt hija tespandi l-espressjonijiet hemm. U hekk ejja jikteb dan ftit differenti. Li n kwadrat diviż bi 2 minus n / 2. Għalhekk għal darb'oħra, jien biss tip ta 'applikazzjoni xi aritmetika regoli hemmhekk. Imma avviż issa li t-terminu akbar f'dan espressjoni, biex ngħidu hekk, hija li n kwadrat. Allura iva, huwa n kwadrat maqsum bi 2, nieqes n / 2. Iżda ġeneralment, jekk n hija se tkun valur kbir, Jien ser issostni li n kwadrat se tkun il-fattur dominanti. Huwa biss se tkun kontributur akbar għan-numru ta 'passi minn n / 2. Mela xi do I jfisser minn dan? Ejja nippruvaw eżempju sempliċi, anke għalkemm l-matematika gets big ftit. Allura jissoponi kellna 1 miljun ruħ fuq il-palk, jew 1 miljun affarijiet li aħna rridu li sort. Ejja plug miljun fis eżattament dak formula biex tara kemm passi li tieħu totali biex issolvi miljun elementi jużaw jiġifieri, sort għażla. Allura aħna d jkollhom l-istess formula bħal qabel. I d plug miljun, b'tali mod li niġi miljun kwadrat diviż bi 2, nieqes miljun maqsum bi 2. Jekk nagħmel dan matematika bil-quddiem hawnhekk, għandna 500 biljun nieqes 500,000, li tagħtina 499999500000, li huwa pjuttost darn big. Fil-fatt, jekk inti tqabbel issa 499,000,000,000, 999,000,000, 500000 kontra valur oriġinali tagħna, 500 biljun, huwa hekk kkritikat qrib. Dritt? n kwadrat diviż bi 2 jagħti us-- jew minflok, n kwadrat diviż bi 2 tana 500 biljun. Li pretty darn qrib li 499999500000, li jfisser li tnaqqas off 500,000, jew b'mod iktar ġenerali, jitnaqqas off n kwadrat, mhuwiex verament big deal. Il n kwadrat jagħmel dawn numri jikbru verament mgħaġġel. Issa, dan huwa importanti biss safejn kif aħna, bħala xjenzjati tal-kompjuter, huma ġeneralment mhux ser kura daqstant dwar l-sfumaturi ta 'dawn il-formuli u eżattament dak li l- tweġibiet preċiżi huma. Aħna kura biss, inti taf liema? Fl-aħħar tal-ġurnata, din il-formula hija fuq l-ordni ta 'n kwadrat. Iva, aħna qed diviż bi 2 fil hemmhekk. Iva, aħna qed jitnaqqas off n tnaqqis ta '2. Iżda fl-aħħar tal-ġurnata, it-terminu li verament jolqot lilna u l-ispejjeż us ħafna passi huwa dak it-terminu kwadru. U iva, liema xjenzat kompjuter se ġeneralment jagħmlu huwa jinjora dawk kollha termini ordni iżgħar, u biss ħarsa lejn dak li jikkontribwixxi l-aktar għall-ispiża. U dan huwa sbieħ, għaliex nistgħu issa jitkellmu ġeneralità ferm akbar dwar algoritmi, u jista jqabbluhom. U l-fatt li jien jużaw dan O huwa intenzjonat. Meta I say fuq l-ordni ta, jien speċifikament jirreferu għal xi ħaġa imsejħa O. ​​big U big O huwa notazzjoni li l-kompjuter xjentist juża biex jiddeskrivu 'fuq marbuta fuq xi ħaġa. Mela jekk inti tgħidli li algoriżmu huwa O kbira ta 'n kwadrat, kif I propost biss mument ilu, li l-mezzi li f'termini ta 'tmexxija tagħha time jew l-effiċjenza tiegħu, dan jieħu l-ordni ta n kwadrat passi. Forsi aktar, forsi inqas. Imma hija dwar l-ordni ta 'n kwadrat. U dak l-rbit għoli. Huwa mhux se tkun iktar diffiċli minn dak. Huwa mhux se tkun n kubiku, jew 2 għall-n, jew xi ħaġa ferm ikbar. Dan huwa rbit superjuri fuq kwalunkwe tali kost huwa. Allura peress li, ejja jikkunsidraw biss ftit eżempji. U dan huwa biss lista limitata ħinijiet tmexxija tal komuni ħafna għal algoritmi li kien ifisser li jkun illustrattiva ta 'xi affarijiet Imxejna tidher diġà. Allura per eżempju, fil-każ ta ' sort għażla, dak li jien titlob hawn li għaddej b'mod dik it-tip Għażla ħin huwa fuq l-ordni ta 'n kwadrat. Fl-agħar każ, jien ser ikollhom mazz sħiħ ta 'numri bl-addoċċ hawn. U kif rajna matematikament, jekk I iżommu mixi permezz tal-lista, permezz tal- lista, l-għażla li jmiss iżgħar element ġdid u għal darb'oħra, jekk I attwalment ikteb kollha tal-passi Jien tieħu bħala I propost formulaically qabel, huwa dwar l-ordni ta 'n kwadrat passi li jien jieħdu. U jirriżulta li bużżieqa sort u l-inserzjoni sort huma daqstant bil-mod fl-agħar każ. Ikkunsidra, per eżempju, sort inserzjoni, l-ħafna aħħar algoritmu aħna ttrattati, li kellhom nħarsu lejn l-element, u mbagħad daħlu fejn jappartjeni. U allura aħna ħares lejn l-element li jmiss, u mdaħħla fejn hi jappartjeni. Għalhekk tikkunsidra l-aħjar xenarju possibbli. Ejja ngħidu I kien voluntiera tiegħi line up litteralment bħal dan, wieħed permezz tmienja, diġà magħżula. Kemm passi huwa tip inserzjoni ser jieħu biex issolvi tmien persuni, jekk jaslu fuq il-palk tfittex bħal dan? Tmien persuni li diġà magħżula. U jien jużaw sort inserzjoni. Din l-aħħar ta 'l-algoritmi. Well, ejja jerġgħu jiġu stabbiliti fast reali. Mela jekk jien tibda hawn, I tara wieħed. Fejn korp bħal dan jappartjeni? Jappartjeni dritt hawn. Nara tnejn. Fejn ma tnejn jappartjenu? Dritt hawn. Nara tlieta. Fejn ma tlieta jappartjenu? Dritt hawn. Nara erbgħa. Dritt hawn. Ta 'ħames, sitt, seba', tmien. M'hemm l-ebda raġuni biex jirrepetu myself. U l-passi hekk, kemm huwa li f'termini ta 'n? Huwa dwar l-ordni ta 'n passi, id-dritt? n minus 1. Imma I ħa numru lineari ta 'passi, u issa jien jsir. Allura li l-aħjar każ, għalkemm. Xi ngħidu dwar l-agħar każ? Liema tmien kien hemmhekk, u sebgħa kienu stabbiliti hemm, u wieħed u tnejn kienu hawn fuq, sabiex li l-lista kienu verament maqluba? Ukoll, dak li jiġri fil-fatt jekk dan huwa n-numru? U aħna ser tagħmel biss ftit eżempji. X'jiġri jekk, fil-fatt, in-numru tmienja hija hawnhekk, u l-Whoops number--. Allura dak li jekk, fil-fatt, in-numru tmienja hija it-triq kollha madwar hawn, u jien jużaw sort inserzjoni? KOLLOX SEW. I titlob fil-mument huwa fil-post. Imma issa, seven-- fejn ma seven imorru? Of course, din tmur minn hawn. So I ikollha tiġi spustjata tmien fuq il-post wieħed. Issa sitt, fejn ma tmur? Well, id-dritt. Issa, I għandhom jimxu tmien fuq post, u seba fuq il-post, u mbagħad I plop isfel sitt. Allura l-ewwel darba, l-ispiża me wieħed pass biex jiffissaw affarijiet, allura jiswa me żewġ passi biex tiffissa l-affarijiet. Kemm passi huwa ser jieħdu biex jiffissaw affarijiet li tpoġġi ħamsa fil-post it-tajjeb? Tlieta. Għaliex issa I għandhom jimxu wieħed, tnejn, tlieta. Kemm passi huwa se jieħu li jpoġġi erba 'fil-post dritt? 4 plus 5, flimkien ma '6, plus 7. U dan huwa matematikament identiċi għal dak li aħna deskritt għall tip selezzjoni. Għandna din is-serje li jinsab biss tiżdied. 1 flimkien ma '2 u 3 u 4, jew bil-maqlub, 7 plus 6 plus 5 plus 4 tammonta għal-lum iskopijiet għad dwar l-ordni ta 'n kwadrat. So let me jistipulaw wisq li sort bużżieqa huwa wkoll fl n kwadrat. Minħabba li bl sort bużżieqa, kull darba li mmur permezz tal-lista, Jien tieħu bejn wieħed u ieħor kemm passi? Kull darba I litteralment jimxu minn hemm sa hemmhekk? Madwar passi n. Imma kif ħafna drabi tista I bżonn li jgħaddu mill-lista? Ukoll, bejn wieħed u ieħor n żmien. Forsi n minus 1, iżda madwar żminijiet n. Well, għaliex huwa li? Ukoll, ma sort bużżieqa, jekk nibdew il sort bużżieqa, il-lista fl-agħar possibbli sitwazzjoni, li għal darb'oħra huwa kompletament lura, dak li jiġri? I jgħaddu l-lista, u n-numru wieħed jappartjeni it-triq kollha hemmhekk. Iżda ma sort bużżieqa, kemm ma wieħed jimxu fuq ewwel pass tiegħi permezz tal-lista? Kemm spots ma hu jiksbu eqreb lejn il-post korretta? Just wieħed. Mela jekk inti tip ta raġuni permezz ta 'dan, kull darba li permezz ta 'dan algoritmu, Jieħdu madwar passi n David. Imma kemm jgħaddi permezz tal-lista huwa se jieħdu għal wieħed bużżieqa lejn ix-xellug fejn jappartjeni? Hu ltqajna biex jimxu simili, spazji n b'dan il-mod. Hekk biss li jagħmlu l-għażla tal-lista, I jkollhom jimxu quddiem u lura n darbiet. U kull darba, jien tħares lejn n elementi. So do n affarijiet n darbiet fuq l-ordni ta 'n kwadrat. Issa, aħna ser tara f'xi ta 'l-xorts li huma integrati fil-problema li jmiss CS50 s stabbiliti, approċċ ieħor lejn dawn, iżda għal issa, ejja biss tikkunsidra xi drabi running oħra, speċjalment jekk dawk issortjar jieħdu xi ftit ta 'żmien biex jinżel fil. X'hemm algoritmu Rajna diġà li jieħu fuq l-ordni ta 'passi n? X'għandu tieħu numru lineari ta 'passi li aħna stajt tidher s'issa? Dak X'inhu? It-tfittxija direttorju tat-telefon. L-ewwel algoritmu. Dritt? Fejn aħna qed lineari tiftix għal Mike Smith? Tabilħaqq. Minn żero ġimgħa, meta bdejt tidwir paġna waħda fi żmien, u I anke qal li kien tip ta 'l-algoritmu sensazzjoni lineari, u kellna li istampa fuq il- board mal-linja ħamra dritta u l-isfar dritta line, dawn kienu tabilħaqq algoritmi li huma O kbira ta 'n. Minħabba li ssib Mike Smith fil-telefon ktieb ta 'paġni N, fil-agħar każ, jista 'jieħu me n passi. What dwar it-teħid attendenza? Wieħed, tnejn, tlieta, erba ', ħames, sitt. X'hemm-running time ta 'dan algoritmu għat-teħid attendenza? O Big ta n, għaliex fit-teorija I ikollhom punt kulħadd fil-kamra. Issa bħala twarrib, dak dwar il- ottimizzazzjoni oħra minn żero ġimgħa? Ġimagħtejn, erba, sitta, tmienja, 10, 12. A xjentist kompjuter se realizzata, stenna minuta, li fuq l-ordni ta ' n maqsuma minn żewġ passi. Dritt? Minħabba li qed nagħmel żewġ persuni kull darba. Iżda aħna qed tmur biex jinjoraw dawn it-termini ordni aktar baxxa, u aħna qed biss jmorru tarmi l-iddividi 2, u biss jgħidu, O kbir ta 'n għal din l-algorithm ukoll. Xi ngħidu dwar dan wieħed? Aħna ser skip fuq xi wħud minn dawn, imma dak kien algoritmu li kienet log ta 'n? Li ħa bejn wieħed u ieħor log passi n? Il-firda u conquer. Eżattament. Bħall-eżempju ktieb tat-telefon fil ġimgħa żero u aktar kmieni llum, fejn aħna maqsuma l-problema ġdid u għal darb'oħra u għal darb'oħra. Aħna ġibdet fuq il-bord fil-ġimgħa żero bħala linja ħadra mgħawweġ, u għidna dak il-jum kien algoritmu logaritmika. U fil-fatt, in-numru ta 'passi li jieħu biex iwettqu firda u conquer, jew tfittxija binarja kif aħna ser tibda ssejjaħ dan, bħal fil-ktieb tat-telefon, hija fuq l-ordni ta 'log u passi. U dan huwa daqsxejn ta 'wieħed stramb. Liema jieħu pass wieħed, jew b'mod aktar speċifiku numru kostanti ta 'passi? Forsi huwa tnejn, forsi huwa tlieta, iżda xjenzat kompjuter biss tissemplifika bħala O kbir ta '1, xi numru kostanti ta 'passi. X'hemm xi ħaġa inti tista 'tagħmel dan jieħu numru kostanti ta 'passi? X'hemm-running time ta clapping? Ħin kostanti. Dritt? Bħal, x'inhu l-running time ta tagħmel xi ħaġa li tieħu biss wieħed operazzjoni, bħal print F Hello World. Li jista 'jingħad li jkun żmien kostanti, sakemm anqas każ kantuniera ma print F, Liema jista 'l-running time stampati F 'attwalment jiġi? U għaliex? X'inhu kejl n f'dak il-każ? UDJENZA: [inaudible]. DAVID J. Malan: Eżattament. In-numru ta 'karattri irridu li jistampaw. Allura huwa ħafna għall-kuntest sensittivi. Illum, aħna kont qed jiffukaw ħafna fuq ittri u n-numri hawn fuq il-bord. Iżda jista 'jkun ukoll karattri fi string attwali. Għalhekk jirriżulta li hemm ieħor miżura li ser jibdew jieħdu ħsieb dwar, u dak l-oppost ta O kbar, biex ngħidu hekk. C'est notazzjoni omega. Billi O big ifisser x'inhu, il- ta 'fuq marbutin fil-ħin running tiegħek? Maximally, kemm ħin jista xi ħaġa tieħu? Omega-- sorry dan jżomm ġejjin up-- huwa l-oppost ta 'dak, li biha huwa rbit baxx fuq il- ammont ta 'xi ħaġa żmien tista' tieħu. So. per eżempju, x'hemm algoriżmu li tieħu passi dejjem n kwadri? Ukoll, wieħed mill-algoritmi Rajna illum, fil-fatt, jista 'jkun dak ukoll. Sort għażla. Għażla tip pjuttost stupid. Anki jekk il-sorry algorithm--, anke jekk il-firxa hija diġà magħżula, sort għażla se iżommu mixi permezz tal-lista biex tiżgura li għandha l-iżgħar element ġdid u għal darb'oħra u għal darb'oħra. U anki jekk inti bnedmin fil- udjenza taf li, stenna minuta, inti diġà għadda mit- element iżgħar, il-kompjuter ma jkunx jaf li sakemm jidher it-triq kollha permezz tal-lista. Bl-istess mod, l-inqas limitu li jistgħu jittieħdu wkoll in kunsiderazzjoni jista 'jkun żmien lineari. Kif ħafna ħin ma jieħdu biex Elementi sort n fl-aħjar każ li jużaw xi ħaġa bħal tip bużżieqa? Ejja ngħidu lista tiegħek diġà magħżula. Aħna qal sort bużżieqa jieħu fuq l-ordni ta 'n kwadrat passi. Imma x'jiġri jekk huwa diġà magħżula? X'jiġri jekk inti tirrealizza wara pass wieħed permezz tal-firxa li inti ħadna l-ebda swaps? Do ikollok bżonn li jżommu tagħmel aktar passes? No Allura Lower bound fuq sort bużżieqa jista 'jingħad li hija lineari. Omega ta n. U nistgħu nħarsu lejn oħrajn tagħhom kif ukoll. Mela ejja tagħti ħarsa fi ftit viżwalizzazzjoni hawn biex tara kif dawn jiddistingwu ruħhom. Jien ser jinżlu hawn fis dan paġna li ikunu disponibbli fuq il-websajt C50, il iżda se tkun uġigħ biex jiksbu xogħol, peress li juża teknoloġija msejħa Applets Java, li hija aktar irfid dawn il-ġranet, mill-inqas minn Chrome u biċċiet minnhom. U let me jimxi 'l quddiem u jħaffu dan up u jispjegaw dak li għaddej. Din hija turija ta 'bużżieqa sort, l-ewwel algoritmu ħarisna lejn. U huwa viżwalizzazzjoni f'dak f'kull ta 'dawn il-vireg jirrappreżenta numru. L-ikbar-bar, l-akbar il numru. L-iżgħar bar, l-iżgħar in-numru. U x'tista 'tara viżwalment, anke għalkemm dan se super fast, hija li l-bar aħmar huwa simili me, mixi u lura iffissar problemi. Tista 'tara li l-elementi akbar tabilħaqq tbaqbieq up lejn il-lemin, u l-elementi iżgħar huma tbaqbieq sal-xellug. U 'l isfel hawn, jekk aħna attwalment tħares aktar mill-qrib, nistgħu ngħidu jgħoddu l- numru ta 'tqabbil u tpartit li kienu qed isiru. Iżda minflok, ejja nħarsu fit-tieni algoritmu ħarisna lejn aktar kmieni ma 'tagħna voluntiera, sort għażla. Viżwalment, hija għandha effett differenti ħafna. Imma hija, għal darb'oħra, ħafna intuwittivi, fil li inżommu għażla li jmiss iżgħar element, u aħna ltqajna ftit xxurtjati. Li ħass fundamentalment aktar malajr. Imma jekk irridu dam dan għal darb'oħra u darb'oħra u għal darb'oħra ma 'lottijiet ta' inputs, aħna se tara li huwa tabilħaqq għadu fil O kbira ta 'n kwadrat. Ejja nagħmlu aħħar wieħed wieħed hawn, sort inserzjoni, li kienet it-tielet algoritmu ħarisna lejn, u recall li dan wieħed jittratta l- Elementi għax jiltaqa lilhom, iżda mbagħad forsi xiftijiet affarijiet fuq biex tagħmel spazju, li jdaħħal elementi fejn huma jappartjenu. U dan ukoll jispiċċa tagħti l- riżultat finali. Issa t-tliet dawk ħass pretty fast. U fil-fatt, I dam minnhom fuq clip pretty tajba. Iżda fundamentalment, dawn qed kollha pretty horrible, li tkun onest. Kollha ta 'dawn algoritmi s'issa li run fil O kbira ta 'n kwadrat jieħu pjuttost ftit ta ' żmien jiddekorri fl-aħħar. U fil-fatt, nistgħu naraw u jħossu dan fl-aħħar jekk I pull up din it-tielet u l-aħħar demo. Dan huwa pass ieħor viżwalizzazzjoni li għaddej li juru sort bużżieqa fuq ix-xellug, sort għażla fin-nofs, u xi ħaġa, bħala waħda mill tagħna naħa tqajjem qabel suġġerit, jingħaqdu sort fuq il-lemin. A firda u conquer istrateġija fuq il-lemin. U li, fil-fatt, dak li aħna qed ser tħares lejn l-Erbgħa. Imma ejja ħin dawn sabiex jimxu flimkien. Huwa madwar l-istess numru ta ' elementi, kollha timxi fl-istess ħin. Bubble sort vs għażla sort vs sort jingħaqdu. Issa, dawn qed kollha running fit-teorija fl-istess ħin. Il-CPU tkun għaddejja bil l-istess veloċità, imma int jistgħu jħossu kif boring dan huwa malajr ħafna se ssir, u kemm malajr meta aħna tinjetta daqsxejn tal-ġimgħa algoritmi żero jista aħna veloċità affarijiet up. U issa ejja jqabblu dawn l-aħħar f forma waħda. Jien ser jimxi 'l quddiem għall-websajt CS50, jekk ikun għandna din ir-rabta finali għal-lum, fejn xi ħadd fuq l-internet ġentilment jitqiegħdu flimkien video li jaqbad dak issortjar differenti algoritmi ħoss bħal. Dan huwa tip inserzjoni. [Beeping] Fejn inti qed tapplika frekwenza ibbażata fuq l-għoli tal-bar bar. Dan huwa tip bubble. [Beeping Warped] Coming up jmiss is-- ġejjin up sort għażla is-- jmiss, fejn għal darb'oħra, aħna qed jintgħażlu l-iżgħar element li jmiss, u nistgħu naraw dan jikber mix-xellug għal-lemin. Jingħaqdu sort, rebbieħ tagħna s'issa llum. Avviż kif huwa diviż affarijiet fis [inaudible] nofs u kwartijiet. Sort Gnome, li aħna ma tkellem dwar, u toħloq viżwalment u audally daqsxejn ta ' forma u ħoss differenti. Jmorru lura u 'l quddiem, tindif affarijiet up. Wkoll check out heapsort fuq il-websajt dan Guy. U li hu. Aħna se tara inti ħin li jmiss. [Whooshing U MUSIC]