[Muzika] 

DAVID J. Malan: Kjo është CS50. Dhe kjo është fillimi i javës së tretë. Pra, ne kemi marrë një shumë të emocionuese gjëra për të mbuluar sot. Një shumë e mundësive për vullnetarë deri në skenë. Dhe në fund të fundit, sot është jo në lidhje me kodin fare. Por kjo është në lidhje me idetë, dhe kjo është në lidhje me algoritme, dhe në fakt duke sjellë përsëri disa prej mësimet e nxjerra nga javë zero, ku kujtojnë, ne futur këtë gjë të shëmtuar. Dhe huamarrja frymëzim nga ajo, për të filluar për të zgjidhur gjithnjë e më të sofistikuara Problemet algoritmikisht. Por së pari, një çift i njoftimeve. Pra, një, në qoftë se ju do të donte për t'u bashkuar Stafi dhe Shokët e klasës CS50-së në drekë kjo e premte, si këtu dhe në Cambridge, dhe në New Haven, ju lutem vizitoni Sigurisht së Faqja e internetit, ku një URL mund të gjenden. Leksion këtë të mërkurë do të të mos jetë këtu në Sanders. Ajo do të jetë vetëm online, kështu që akorduar në në faqen e internetit CS50 e, nëse këtu në Kembrixh ose New Haven si. 

Dhe pastaj problemi vendosur dy tashmë është në duart tuaja. Nëse ju nuk e keni hodh në krahun ende, më lejoni për të ofruar sugjerimin fjalë të ashpra se, sidomos tani, si problemi përcakton paraprakisht, ju me të vërtetë duan të fillojnë tani, në qoftë se nuk njom pak në fundjavë ose para kur ata së pari të shkojnë jashtë në Premteve, sepse ju do të të gjeni se ata nuk janë domosdoshmërisht duke marrë më të gjatë ose më të vështirë për se. Unë mendoj se ju do të gjeni se, në përgjithësi, ata kanë tendencë për të marrë afërsisht rreth të njëjtën sasi kohe. Por kjo sigurisht varet për nxënësit, dhe atë varet nga mendim me të cilat ju qasje atë. Por pa ndryshim, ju do të jeni për të drejtuar kundër një mur, dhe ju jeni duke shkuar për të goditur disa bug, dhe ju jeni vetëm nuk do të jetë në gjendje të të marrë përsipër atë në një pikë. Dhe kjo është jashtëzakonisht e vlefshme për të të jetë në gjendje për të hap larg, kthehen të nesërmen, shkoni në orarit të punës, postoni në CS50 Diskutoni apo si, që në fakt të marrë zhbllokuar. Pra, mbani në mend. Duke filluar hershme të jetë e mundur është gjëja më e mirë që ju mund të bëni. Kështu që këtu është ku kemi filluar klasa, mbi në javë zero. Dhe mund të marrim një vullnetar këtu për të ndihmuar mua të gjej mics? NE RREGULL. Këmbë tashmë. Eja up. Mendoj se është se si ajo do të punojë. Si e ke emrin? ALAN ESTRADA: Alan Estrada. DAVID J. Malan: Alan Estrada. Eja up. Gëzohem që u njohëm. ALAN ESTRADA: Gëzohem që u njohëm. DAVID J. Malan: Dhe ju ishit këtu me ne në javën zero, natyrisht. ALAN ESTRADA: Unë kam qenë. Isha. 

DAVID J. Malan: Pra, mund të shkoni përpara dhe për të gjetur për ne Mike Smith, aq shpejt si ju mund? Sa më shpejtë që mundeni. Fjalë për fjalë marramendës problemin në gjysmën e si ju duhet të. 

ALAN ESTRADA: Um. DAVID J. Malan: Fjalë për fjalë marramendës problemin në gjysmë. 

ALAN ESTRADA: Oh. Mm. Shume mire. 

DAVID J. Malan: OK. Të mirë. Faleminderit. ALAN ESTRADA: Shumë mirë. NE RREGULL. 

DAVID J. Malan: Dhe kështu tani, ju keni whittled atë poshtë në gjysmën e madhësisë së problemit. Tani, ne jemi deri në një të katërtën. A jeni duke i kushtuar vëmendje të cilën anë ne jemi duke e mbajtur? 

[Duke qeshur] 

ALAN ESTRADA: Po, unë think-- 

DAVID J. Malan: Cilat seksion jemi në? ALAN ESTRADA: Mufflers, kështu. 

DAVID J. Malan: OK. Por, Mike Smith po shkon të jetë pas Mufflers. Kështu që-- 

[Duke qeshur] 

Në rregull. ALAN ESTRADA: Ku jemi duke kërkuar? DAVID J. Malan: Mike Smith. ALAN ESTRADA: Mike Smith. DAVID J. Malan: Tani, ne jemi në kirurgjikale. Tani, mjekët. Now-- 

ALAN ESTRADA: Let's- le të shkojë me të vërtetë. Real. 

DAVID J. Malan: Real. NE RREGULL. Nëse keni nevojë të vërtetë. Tani, cila rrugë është Mike Smith? 

ALAN ESTRADA: Në këtë mënyrë. 

DAVID J. Malan: Cila mënyrë? ALAN ESTRADA: Prit. E drejtë M is--? Ne kemi filluar with-- 

DAVID J. Malan: Po. Ata janë lënë. E drejta juaj. 

ALAN ESTRADA: Po. 

DAVID J. Malan: Pra, Mike s në këtu. ALAN ESTRADA: Çfarë? 

[Duke qeshur] 

Shembulli i keq, djema. Më vjen keq. DAVID J. Malan: Kjo do të mësojmë ju të brishtë nga karrige tuaj. 

ALAN ESTRADA: Oh. Oh. I kam ju. I kam ju. Oh. Oh. Kjo is-- OK, unë kam ty. Smith drejtë këtu? 

DAVID J. Malan: Smith, faleminderit. Kështu që unë do të mbaj shikuar deri Smith? 

ALAN ESTRADA: Oh, po. Jo jo jo. Oh, jo. Kjo është e imja. 

DAVID J. Malan: Oh, ju mori Smith. NE RREGULL. 

ALAN ESTRADA: Po, unë mori Smith drejtë këtu. Më vjen keq, djema. Mendova Michael-- ne ishin në kërkim për Michael. Më vjen keq. 

DAVID J. Malan: Është në rregull. Në rregull, tani ne jemi në Paccini dhe fëmijësh. 

ALAN ESTRADA: Paccini dhe bijtë. DAVID J. Malan: Vetëm ju dhe unë jemi në në këtë. NE RREGULL. Na gjeni Mike Smith. Smith. 

ALAN ESTRADA: Smith. 

DAVID J. Malan: Smith. Ne jemi në R për mbeturina. ALAN ESTRADA: Shumë keq. Oh. Kjo do të marrë një kohë. 

[Duke qeshur] DAVID J. Malan: Këpucë. Ne jemi në këpucë. 

ALAN ESTRADA: Tani ne jemi gonna-- 

DAVID J. Malan: Bukur. ALAN ESTRADA: Which-- [Duke qeshur] Oh, kjo është e madhe. [Duke qeshur] 

DAVID J. Malan: Është në rregull. 

ALAN ESTRADA: Oh, kjo është e mirë. Unë nuk mendoj se unë jam duke shkuar për të kanë miqtë PSAT pas kësaj. DAVID J. Malan: Mirë. Sporting. ALAN ESTRADA: Sporting. Um, L, M, N, O, P. DAVID J. Malan: OK. Pra, le të gris këtë në gjysmë. Eshte mire. Kjo përfundon keq gjithsesi, sepse Mike Smith nuk do të jetë në faqet e verdhë. 

ALAN ESTRADA: Aw. 

DAVID J. Malan: Jo, kjo është në rregull. Por le të pretendojë si ai është në këtë faqe. Deri tani, ju keni whittled problemin poshtë në një faqe, dhe gjetëm Mike Smith. 

[Brohorisnin] Ne rregull faleminderit. NE RREGULL. Kjo ishte e jashtëzakonshme. Por ai ishte ende më i shpejtë se kërko lineare, ku ne të fillojë në nivel fillim të librit, dhe ne shkojmë rrugën tonë nga e majta në të djathtë, përfundimisht duke kërkuar për Mike Smith. Dhe kështu, në qoftë se libri telefonit kishte ndoshta 1.000 faqe, ndoshta kjo do të kishte marrë ne 10 apo më shumë lot faqe. 

Por ju mund të keni leveraged prekur një supozim gjatë gjithë se, që do të thotë se libri telefoni paraprakisht ishte ajo? Audienca: Renditur. DAVID J. Malan: Është e renditura. E drejtë? Është renditura alfabetikisht, kështu se të gjithë ata emra dhe numra janë të renditura nga A-së të Z-së, dhe sipas rendit alfabetik në mes. Por sot, ne tani pyesim pyetja, mirë, sa e bëri Verizon ose telefon kompani të marrë atë në atë shtet? 

Sepse kjo është një gjë për të levave që supozim, dhe për këtë arsye, të zgjidhur një problem me një algorithm më efikase. Por ne kurrë nuk të vërtetë pyetur në javë zero, mirë, sa e bëri atë kosto Verizon apo dikush tjetër për të marrë atë libër telefonit në mënyrë renditura? 

E drejtë? Nuk ka rëndësi nëse shikuar deri Mike Smith është e super të shpejtë, në qoftë se ajo ju merr një vit për të zgjidhur faqet fillimisht. E drejtë? Si edhe ju mund vetëm të analizoj përmes një libër telefoni randomized, në qoftë se ajo do të jetë super shtrenjtë për të zgjidhur atë. Pra, nëse ne mund të kemi një tjetër vullnetar. Le të marrin një vështrim lart këtu në se si ne might-- ardhur në up-- si ne mund të shkoni në lidhje me klasifikim këto. 

Dhe në qoftë se Jordani mund të vërtetë të bashkohen me ne këtu në skenë. Eja për vetëm një moment. Si e ke emrin? CAROLINE: Caroline. DAVID J. Malan: Caroline, eja lart. Dhe ju do të bashkohen nga unë dhe Jordani këtu. Caroline, faleminderit. Në rregull. Pra, ajo që ne kemi këtu për Caroline është 26 libra blu që FAS përdor për të administruar Provimet caktuara përfundimtar. Këto janë duke u vështirë për të gjetur, por ajo që ne kemi bërë më parë është se ne kemi vënë emrin e dikujt në pjesën e përparme të secilit prej këtyre, por ne kemi mbajtur atë të thjeshtë nga pastaj vënë nga emrat e plotë. Pra, ne do të vënë personin me emrin L, D, J, B, të gjithë mënyrë A nëpër Z, por ata janë në mënyrë të rastit. Dhe kështu që në qoftë se ju do, duke folur tuaj rrugën përmes problem si ju bëni atë, ju mund të shkoni përpara dhe lloj këto për ne, nga A në Z. 

Audienca: OK, kështu që L është si, e mesme. C ka filluar. B. J para L. B, Q. 

DAVID J. Malan: Hold se mendoi për një sekondë. Sepse përndryshe, kjo është vetëm interesante për ju, mua, dhe Jordani. Atje shkojmë. Audienca: [padëgjueshme]. R. DAVID J. Malan: OK. Çfarë po bën? 

CAROLINE: M vjen pas O. 

DAVID J. Malan: OK. 

CAROLINE: O. DAVID J. Malan: O, mirë. 

CAROLINE: E. 

DAVID J. Malan: E, F. Po. 

CAROLINE: T, U, V. 

DAVID J. Malan: V, T, U, V. kështu që ajo duket sikur ju jeni making-- mbajë. Ajo duket sikur ju jeni duke e bërë një grumbull i madh gjatë këtu, dhe lloj i një grumbull i madh mbi atje. Pra, gjysma e parë e alfabetit, gjysma e dytë e alfabetit. NE RREGULL. Të mirë. Lloji i ndarjes problemin në dy. M, N, X. Po. CAROLINE: K. DAVID J. Malan: OK. K. Pra, ju jeni lloj i zgjedhur ata njëri pas tjetrit, duke e vënë atë ose majtas ose djathtas, ose Z po ndodh në dysheme. NE RREGULL. 

CAROLINE: Z po ndodh në dysheme. 

DAVID J. Malan: OK. Y po ndodh në dysheme. Tani ne mund të vënë X. 

CAROLINE: G. DAVID J. Malan: G do largua. S po shkon drejtë. Të gjithë të drejtë, A po shkon gjatë gjithë rrugës majtë. 

CAROLINE: A, B, C, D. 

DAVID J. Malan: Tani, mirë. Ne kemi marrë A, B, C. W-së shkuar atje poshtë. Të gjithë të drejtë, T. 

CAROLINE: H, I, J. DAVID J. Malan: H, I, J. mirë. CAROLINE: Në qendër, unë jam gonna-- DAVID J. Malan: OK. Deri tani, ne jemi duke shkuar për të llojit të bashkojë të këtyre shtyllave të ndryshme. Pra, një anë C, atëherë unë shoh D, dhe E, dhe F, dhe G, dhe H dhe I. Nisë. J, K. Dhe pastaj, kjo është grumbull me kokë poshtë, por kjo është në rregull. I sigurt. Ne mund të prerë disa qoshet. NE RREGULL. Dhe pastaj ne kemi nevojë W, X, Y, Z. 

CAROLINE: Po. 

DAVID J. Malan: Excellent. Pra, një i madh ju falënderoj për Caroline për klasifikim këto. 

[Brohorisnin] 

Faleminderit. Faleminderit shumë. Pra, tani le të shqyrtojmë për një moment si Caroline përshkoi vendin duke bërë atë, dhe çfarë saktësisht ne ishin në gjendje to-- si ne ishin në gjendje për të zgjidhur atë Problemi kur ishim vetëm dhënë një bandë e tërë e inputeve të rastit. 

E pra, ajo duket sikur ka ishte pak e një sistemi atje? E drejtë. Pra, letrat e mëparshme në alfabetin, ajo ishte vënë në të majtë, dhe letra Më vonë në alfabetin, ajo ishte vënë në të djathtë. Dhe sa më shpejt që ajo gjeti disa letra proksimalen, ato të që shkojnë drejtë pranë njëri-tjetrit, ajo do të vënë ato në mënyrë. Dhe kështu që ne lloj i pasur këto të vogla grumbujt e inputeve të renditura ndodhin. 

Dhe kështu kjo është mjaft si ajo Shumica prej nesh do të bëjë njerëzit. Ne do lloj analizoj përmes saj, dhe ne do lloj të ketë një mekanizëm. Por ajo mund të jetë e vështirë për të shkruar ajo poshtë në një formulë në vetvete. Ajo ndjeu një pak më shumë se kaq organik. Pra, le të shohim nëse ne mund tani lidhur problemi me më pak inpute. 

Në vend të 26, le të të bëjë diçka shumë më pak me të them vetëm, shtatë, prapa këto dyer, kështu që të flasin. A ka vetëm shtatë numra? Dhe në qoftë se qëllimi tani në dorë është për të gjetur një vlerë, le të shohim se si në mënyrë efikase ne mund të shkojë për të bërë këtë. Dhe le të shohim nëse ne mund tani fillojnë të aplikojnë disa numra, ose disa formula me të cilin për të përshkruar efikasiteti i librit tonë të telefonit algorithm, tona algorithm libër provim, dhe më në përgjithësi, gjetjen e informacionit. 

Pra për këtë, më lejoni të shkoj përpara, dhe në ekran touch gjatë këtu, vënë një shfletues web që ka pikërisht këto shtatë dyer. Dhe në qoftë se ne mund të marrë një tjetër vullnetarë për të ardhur në këtu, Unë e kam vënë këto dyer të njëjta mbi këtu. Vullnetar të shpejtë. 

Ky popull one-- janë duke shkuar për një të shpejtë dhe më të shpejtë tani. Eja poshtë. Si e ke emrin? Trevor: Trevor. 

DAVID J. Malan: Trevor? Të gjithë të drejtë, Trevor, vijnë më poshtë. Pra, Trevor ka vullnetarë këtu për të bëjë një problem të ngjashëm, por ai që është ngushtë në fushëveprimin, dhe kjo po ndodh të na lejojë që të përpiqen për të zyrtarizuar tani procesi për klasifikim këto numra. 

Pra Trevor, nice to meet you. Kështu që këtu është një grup, në mënyrë që të flasin, një listë të shtatë dyerve. Shkoni përpara dhe të na gjeni numrin 50. Dhe pastaj pas faktit, na tregoni se si keni gjetur atë. Duhet be-- të gjithë të drejtë. Po, kjo është ajo këtu? Uh-oh. NE RREGULL. Ju klikuar se një. Të mirë. 

Dhe të mirë. Tani ju klikuar se një. Dhe më lejoni t'ju jap mikrofonin, në mënyrë që ju të keni atë në një moment të vetëm. Shkoni përpara dhe klikoni në vendin fqinj që keni ndërmend. Po, mirë. Trevor: A mund të unclick një derë? DAVID J. Malan: Jo, ju nuk mund të unclick. Trevor: OK. Këtë. DAVID J. Malan: Ku doni të shkoni? Cila? 

Trevor: Se një. 

DAVID J. Malan: Jo. 

Trevor: OK. Këtë. 

DAVID J. Malan: Po. Kjo ishte e mirë. Në rregull. Pra, çfarë ishte algoritmi tuaj ose Procedura për të bërë këtë, Trevor? 

Trevor: Unë vetëm shkoi nëpër Dyert deri sa kam gjetur një 50. DAVID J. Malan: OK. Algorithm shkëlqyer. Pra, kjo është në rregull. Sepse në fakt, në qoftë se unë të zbulojë se çfarë është pas këtyre dy dyer të tjera, çfarë ne do të gjeni këtu është se ne kemi vetëm të dhëna të rastit. Kështu që ishte në të vërtetë si i mirë sa ju mund të merrni. Dhe në fakt, ju mori më të mirë se shteruese në kërkim të gjithë array, sepse kjo do të kishte qenë me të vërtetë pafat në qoftë se ju kishte goditur numrin 50 tek dera e fundit. Por, çfarë nëse ne vend ju dha një supozim. Mendoj unë lloj të gjithë Këto dyer rreth, kështu që ju keni Numrat e renditura në këtë kohë, por këtë herë është e vërtetë një different-- këtë herë, është e renditura në fakt për ju. Dhe tani qëllimi në dorë është për të goditur numrin 50. 

Trevor: OK. 

DAVID J. Malan: Çfarë është do të jetë algorithm juaj? 

Trevor: E pra, në qoftë se është të renditura, është ose do për be-- nëse e madhe për të më e madhe, zbritëse, ajo do të jetë i pari, ose në qoftë se është e kundërta, ajo do të jetë e fundit. Kështu që unë do të caktojë vetëm këtë derë, dhe pastaj vetëm trokitje e lehtë derën e fundit. DAVID J. Malan: Excellent. Në rregull. Pra, ne kemi gjetur numrin 50. Pra, sa më shpejt që ju e dinte ata ishin të renditura, ne ishin në gjendje të levave këtë supozim. Pra, ata janë shumë si shembulli librin e telefonit. Sa më shpejt që ju keni, madje edhe me një problem të vogël si kjo, inputet e tu para-renditura, ne mund të në fakt të gjetur vlerën ndoshta në mënyrë më efikase. 

Dhe unë nuk ju them në qoftë se ajo ishte renditura vogla në të mëdha, ose të mëdha në të vogla, dhe kështu që ishte shumë e arsyeshme për të filluar në një nga skajet ose tjetër që në fakt gjetur këtë vlerë të synuar. Pra, falënderoj për Trevor si. Dhe unë do të propose-- bërë mirë. Ne kemi një klip të vogël, në të vërtetë, se është ndër momentet favorite tona në CS50, ku ndonjëherë këto popull mos fare shkojnë sipas planit. Dhe me të vërtetë tani, unë u tërhoq deri interface gabuar me të cilin do të përdorni ekranin me prekje. Kështu që ishte faji im aty. 

Pra, kjo do të bëjë për clip vitin e ardhshëm si pse unë kam qenë duke klikuar në ekranin tim. Por le të marrin një vështrim të shpejtë se çfarë ka ndodhur vitin e kaluar me Jay, i cili erdhi, shumë si Trevor këtu, vullnetarë, dhe në këtë klip të shkurtër, ju do të shihni si kjo e njëjta demo nuk bëri mjaft zbulojnë të njëjtat mësimet e nxjerra. [VIDEO rishikim] -Të Gjitha unë dua që ju të bëni tani është për të gjetur për mua, dhe për ne, me të vërtetë, numri 50 një hap në një kohë. 

-Numri 50? 

-Numri 50. Dhe ju mund të zbulojë se çfarë është pas secili prej këtyre dyerve thjesht duke prekur atë me një gisht. Mallkuar atë. 

[Duke qeshur] 

[END rishikim] DAVID J. Malan: Pra, që shkoi shumë mirë. Ata ishin dyert Unsorted. Dhe Jay, sigurisht, gjeti atë të gjithë shumë shpejt. Trevor bëri një punë shumë të mirë në kushtet e një moment i aftë për shkollë, mënyrë që të flasin, këtë vit në duke marrë më të gjatë për të gjetur atë. Sigurisht, atëherë ne i dhamë Jay një shans të dytë, ku ne renditura dyert, ashtu siç bëmë për Trevor, dhe Trevor e bëri super të mirë këtë herë. Por Jay bëri atë gjysmë sa më shpejt. [VIDEO rishikim] -The Tani qëllimi është edhe na gjeni numrin 50, por të bëjë atë algoritmikisht, dhe na tregoni se si ju do të jeni në lidhje me të. 

-NE RREGULL. 

-Dhe Në qoftë se ju të gjeni atë, ju mbani filmin. Nëse ju nuk e gjeni atë, ju jepni atë përsëri. 

-Man. 

-Oh! 

- [E padëgjueshme] OK. Kështu që unë jam duke shkuar për të kontrolluar përfundon së pari për të përcaktuar nëse there's-- Oh. 

[Duartrokitje] 

[END rishikim] DAVID J. Malan: OK. Pra, sorting dyert në mënyrë të qartë çon në efikasitet më të madh. Dhe kështu, dy herë më shpejt është ajo që unë do të thotë atje. Dhe kështu Jay mori me fat dy herë. Dhe ai gjithashtu mori me fat në atë të fundit vit, unë urdhëroi disa disqe Blu-ray që në fakt japin. Më vjen keq të këtij viti, ne nuk kanë të njëjtë, Trevor. Por më mirë akoma ishte disa vjet mbrapa. Dhe disa prej jush mund të dini këtë shokët, Sean, i cili kur ai ishte në CS50, u sfidua me saktë njëjtin problem, megjithëse në SD, si ju së shpejti do të shihni, mbrapa në ditë. Dhe ju do të gjeni se jo vetëm që ai të marrë pak më shumë se Jay, pak më shumë se Trevor, ajo ishte në fakt kjo mundësi e mrekullueshme për t'u angazhuar pothuajse të gjithë në Turma a la Çmimi është e drejta, duke inkurajuar atë për të gjetur numrin e ne po e kërkojmë. Le. të marrë një sy të shpejtë. 

[VIDEO rishikim] 

-NE RREGULL. Kështu që detyra juaj këtu, Sean, është në vijim. Unë kam fshehur prapa këto Dyert numri shtatë. Por tucked larg në disa prej këtyre dyerve si dhe një numër të tjera negative. Dhe qëllimi juaj është për të menduar i këtij rreshtin e lartë të numrave si vetëm një grup, apo vetëm Sekuenca e copa letre me numra pas tyre. Dhe qëllimi juaj është vetëm duke përdorur të lartë array këtu, të gjetur me numrin shtatë. Dhe ne jemi duke shkuar për të kritikuar më pas si ju shkoni për të bërë atë. -Në rregull. Na -Find numrin shtatë, ju lutem. Jo. Pesë, 19, 13. 

[Duke qeshur] 

Kjo nuk është një pyetje mashtrim. Një. 

[Duke qeshur] Në këtë pikë, rezultati juaj nuk është shumë e e mirë, kështu që ju mund edhe të do të mbajë. Tre. 

[Duke qeshur] 

Vazhdo. Sinqerisht, unë nuk mund të ndihmojnë por pyes veten çfarë jeni duke menduar për, so-- 

[Duke qeshur] Vetëm në radhën e lartë, kështu që ju keni marrë tre majtë. Pra, gjeni mua shtatë. 

[Duke qeshur] 17. Shtatë. 

[Duartrokitje] 

Në rregull. 

[END rishikim] 

DAVID J. Malan: Pra, ne mund të shikojnë këto gjatë gjithë ditës. Dhe sigurisht, disa prej popull këtij viti ndoshta tani do të përfundojë deri në të ardhshëm Video viti si. Pra, tani le të vërtetë të përqëndrohet në algoritme këtu, dhe të shohim nëse ne nuk mund të tani të fillojë të formalizuar se si ne mund të shkoni në lidhje me marrjen e të dhënave tonë në këtë gjendje që është e renditura, në mënyrë që në fund të fundit, ne mund të vërtetë kërko atë në mënyrë më efikase. Dhe, edhe pse ne jemi duke shkuar të përdorin të dhënat grupe mjaft të vogla, si tetë numrat ne kemi këtu në bord, në fund të fundit këto ide të njëjta mund të aplikohet në 1.000 inputeve, një milion inputeve, 4 miliardë inputeve, sepse algoritme do të jetë në thelb e njëjtë. 

Dhe kështu kjo është e fundit ynë mundësi për vullnetarët sot, por ndoshta më e përfshirë, për të cilat ne kemi nevojë për tetë vullnetarë për të dalë dhe të na ecin nëpër Procesi i ndarjes se çfarë do të së shpejti të jetë në këto muzikën qëndron këtu. Më lejoni të filloj përsëri këtu. 

Pra, një në të gjelbër turquoise-- është ajo? A jeni kryerjen? Dy. Eja poshtë. NE RREGULL. Tre. Katër. Le me-- OK, pesë. Ju jeni duke u nominuar nga miku juaj. Gjashtë, shtatë, tetë. Eja up. Në rregull. Shume faleminderit. Eja up. Eja up. 

Në rregull. Pra, ajo që ne kemi here-- dhe kjo është ndër ato më të vështirë, pasi kjo do të kërkojë që të humorit mua për vetëm një grimë të vogël të kohës. Ju do të jetë numër një. Si e ke emrin? 

Anan: Anan. 

DAVID J. Malan: Anan. David. Si e ke emrin? 

Joseph: Joseph. 

DAVID J. Malan: Joseph, ju jeni numri dy. 

Serena: Serena, numri tre. Stefan, numri katër. CYNTHIA: Cynthia. DAVID J. Malan: Cynthia, numri pesë. [Padëgjueshme] DAVID J. Malan: [padëgjueshme]. David, numri gjashtë. MATT: Matt. DAVID J. Malan: Numri i Matt shtatë. Dhe? 

WAVERLY: Waverly. 

DAVID J. Malan: Waverly, numri tetë. Në rregull. Nëse ju could-- uh. Në qoftë se ju të gjithë, siç tuaj Sfida e parë, atje janë tetë qëndron muzikë këtu përballet me audiencën. Në qoftë se ju mund të vënë numrat tuaj mbi këto muzikë qëndron në një mënyrë të tillë që ata të vijë deri me Numrat e njëjta në bord. Pra, bëni të duken si se nga vënë numrat tuaj në këto muzikën qëndron këtu. Të shkëlqyer deri tani. 

Shkëlqyer. NE RREGULL. Deri tani, ne jemi duke shkuar për të pyesni pyetje në disa mënyra të ndryshme. Si mund të shkoni në lidhje me sorting këto folks këtu? Sepse kemi pasur një qasje pak më parë, ku ne ishim lloj i bërë dy kova të ndryshme. Dhe pastaj ne kemi qenë në përgjithësi piecing gjëra së bashku. Sapo pamë dy numrat që i përkiste së bashku, ne kemi vënë ata së bashku. Dy letra që i përkasin së bashku. 

Por le të shohim nëse ne nuk mund të formalizojë këtë, në mënyrë që në fund të fundit ne kemi disa pseudo-kod ju do, me të cilat ju mund të zgjidhin këto probleme. Deri tani, unë jam duke kërkuar jashtë në këto numra këtu. Dhe unë shoh një bandë e tërë e gabimeve. Në fund të fundit, unë dua një të tillë në majtë dhe të tetë në të djathtë. 

Dhe kështu që unë jam duke kërkuar në këta të dy, katër dhe dy. Dhe çfarë është problemi, natyrisht? Po. Kështu që. Dy padyshim vjen para katër, kështu që ju e dini se çfarë? Më lejoni së pari të marrë një qasje babëzitur, në qoftë se ju do të, problemi shumë si vendosur one-- nëse ju kujtohet nga Standard Edition i problemit Set One, ku unë vetëm në vend të zgjidhur problemin kjo është e drejtë këtu para meje dhe të shohim se ku ajo të çon mua. 

NE RREGULL. Pra, dy dhe katër, më lejoni të shkoj përpara dhe vetëm shkëmbim të dy. Në qoftë se ju mund të lëvizin fizikisht veten dhe letër tuaj, Unë duket se kanë marrë lista në një gjendje më të mirë. 

Tani, ata janë të mirë. Unë jam duke shkuar për të shkuar përpara, katër dhe gjashtë, duket e mirë. Nuk është problem. Gjashtë dhe tetë, OK. Tetë dhe një, një tjetër problem. Sepse ajo që është e vërtetë në lidhje me tetë dhe një? Vjen para se të tetë, dhe kështu çfarë duhet të bëjmë? Le të bie në ujdi këto dy. Një dhe tetë. Dhe tani, unë jam duke shkuar për të do të mbajë. Unë jam duke shkuar për të mbajtur në kërkim përpara. Dhe le të shohim se çfarë ndodh. Tetë dhe tre, të Sigurisht, nga e rendit. Le të swap. Tetë dhe shtatë, natyrisht. Jashte perdorimit. Le të swap. Tetë dhe pesë, natyrisht, le shkëmbim. Në rregull. Lista është e renditura. po? 

OK, natyrisht jo. Por kjo është një pak më të mirë, e drejtë? Sepse njoftim çfarë ka ndodhur. Çdo herë kemi kryer një shkëmbim, një më të vogël Numri lloj i percolated në këtë mënyrë, dhe një numër i madh percolated këtë mënyrë, ose ne do të fillojnë duke thënë bubbled të majtas ose bubbled në të djathtë. 

Tani, kjo nuk është e mjaftueshme, sepse në të mirë të një numër i fuqisë kanë lëvizur një vend përpara, ose në më të keq, një numër mund të ketë lëvizur një vend edhe më tej. Pra, ju e dini se çfarë, ky lloj i ka punuar mjaft mirë deri tani. Më lejoni vetëm të provoni përsëri. Dy dhe katër, ata janë në rregull. Katër dhe gjashtë, ata janë në rregull. Gjashtë dhe një, nga e rendit. Pra, le të bie në ujdi të dy. Dhe tani, vini re problemi-së duke filluar për të marrë një pak më të mirë përsëri. Gjashtë dhe tre, nga e rendit. Le të bie në ujdi të dy. Gjashtë dhe shtatë, ju jeni të mirë. Shtatë dhe pesë, natyrisht, jashtë funksionit. Shtatë dhe tetë, në rregull. Dhe tani, unë mund të kenë nevojë për të bëni këtë disa herë më shumë. Dhe në fakt, mendoj për veten tuaj ndoshta sa herë maksimalisht mund të më duhet të ecin mbrapa dhe me radhë? 

Ne do të kthehen në atë. Pra, dy dhe katër janë ende në rregull. Katër dhe një, Jo. Pra, le të swap. Dhe përsëri, vini re vizualisht një është lloj i bubbling në të majtë, ku ajo duhet të jetë. Katër dhe tre shkëmbim. Katër dhe gjashtë. Gjashtë dhe pesë shkëmbim. Gjashtë dhe shtatë. Shtatë dhe tetë janë të mira. 

Të mirë. Ne jemi duke marrë edhe më të mirë. Pra, le të shohim. Tani, ne kemi dy dhe një. Sigurisht, të bie në ujdi. Dy dhe tre, tre dhe katër, katër dhe pesë, gjashtë dhe shtatë, shtatë dhe tetë. Të mirë. Dhe ju e dini se çfarë? Sepse unë bëra një ndryshim atje, më lejoni të bëj një kontroll mendje e shëndoshë. Më lejoni të shkoni të gjithë rrugën përsëri në fillim. NE RREGULL. Një, two-- Yup, e shihni? Diçka ishte e gabuar. Tre, katër, pesë, gjashtë, shtatë, tetë. Dhe në këtë kalim të fundit, janë ju rehat me tani tim duke pretenduar se ai është renditur? NE RREGULL. Vizualisht, kjo është absolutisht e vërtetë. Por funksionalisht, çfarë ka gjithashtu ndodhë vetëm në atë të kalojë e fundit që ju lejon për të konfirmuar se kjo listë është me të vërtetë të renditura? 

Çfarë ka të bëj apo jo të bëjë këtë abone të fundit? Audienca: Nuk ka pasur ndryshime. DAVID J. Malan: Na vjen keq? Audienca: Nuk ka pasur ndryshime. DAVID J. Malan: Nuk ka pasur ndryshime. Pra, kjo do të jetë budalla për mua për të të bëjë të njëjtin algoritmi përsëri në qoftë se unë nuk e ka bërë asnjë ndryshon për herë të parë. Dhe shteti nuk ka ndryshuar. Sigurisht, unë nuk jam duke shkuar për të bërë Çdo ndryshim për herë të dytë. Dhe kështu, është e sigurt tani për të thënë, lista është renditur. 

Dhe në të vërtetë, kjo është tani diçka që ne do të në përgjithësi thirrje lloj flluskë, ku pairwise, ju korrigjuar gabimet përsëri, dhe përsëri, dhe përsëri, dhe ju do të mbajë mbrapa dhe me radhë, dhe mbrapa dhe me radhë, derisa ju të bëjë asnjë këmbime të tilla, në të cilën pikë ju mund të jeni i sigurt, po, përfundoi fiksimin e të gjitha gabimet. Le të rivendosur dhe të provoj diçka tjetër. Në qoftë se ju djema mund të kthehem në rendi keni qenë një moment më parë, që dukej si kjo. Tani, le të marrin një qasje të një pak më shumë si librin e provimit, ku ne kemi qenë vazhdimisht zgjedhjen letrën e alfabetit që ne lloj i dashur për t'u marrë me të ardhshëm. Ndoshta kjo ishte një letër e lartë, si A, ose një letër Z. ulët 

Kështu që të gjithë është kthyer në këtë mënyrë. Dhe tani më lejoni të bëj këtë. Le të shohim se Unë e di unë kam tetë numra këtu. Unë jam duke shkuar për të shkuar përpara dhe vetëm qëllimisht zgjidhni elementet më të vogla. E drejtë? Kjo duket intuitive shumë. Pse nuk mund të gjej më të vogël element, e vënë atë ku i takon, pastaj të marrë elementin tjetër më të vogël, vendos ajo aty ku i takon, dhe vetëm përsërisin. 

Sepse intuitive, që duhet të punojnë shumë. Pra katër, që është një numër shumë i vogël. Unë jam duke shkuar për të kujtuar se ku është kjo. Prit një minutë. Dy është më i vogël. Më lejoni tani të mbani mend se ku dy është, dhe të harrojmë për katër. Ne do të merremi me këtë më vonë. Gjashtë, unë nuk jam i interesuar. Tetë, unë nuk jam i interesuar në. Njëra është numri im i ri i vogël. Kështu që unë jam duke shkuar për të kujtuar ku është. Tre, nuk janë të interesuar. Shtatë, nuk janë të interesuar. Pesë, nuk janë të interesuar. 

Pra, pa u pakësuar faza të këtij viti, Unë jam duke shkuar për të rrëmbyer numrin one-- dhe ajo që ishte emri juaj përsëri? 

Anan: Anan. 

DAVID J. Malan: Anan. Dhe në qoftë se ju mund të bashkohet me mua në fillimi i listës, le të ju vë ku ju i përkisni. Unfortunately-- çfarë është emri juaj? 

STEFAN: Stefan. 

DAVID J. Malan: Stefan është në rrugë të drejtë. Pra, para se të Stefan zgjidh këtë problem, çfarë duhet të bëjmë? Çfarë bëjmë ne me Stefan? 

Audienca: [padëgjueshme]. DAVID J. Malan: OK. Pra, ne mund të bëjmë atë. Ne mund të lloj të Stefan dhe tij katër, dhe vetëm vënë atë në një variabël dhe të mbajë në të atë për disa sasinë e kohës, duke e bërë vend për numrin një. Dhe kjo nuk është e keqe. Unë mund të sugjeroj, pse nuk e bëjmë ne vetëm vënë Stefan këtu? Pse mund të shkelë një kjo e ideve kemi filluar duke folur për herë të fundit, javën e kaluar? Po? 

Audienca: [padëgjueshme]. 

DAVID J. Malan: Nuk ka indeks për të. Nëse ju mendoni për këtë, me të vërtetë, si një grup, kjo është si një negativ, kështu që nuk ka asnjë kujtim fakt këtu nëse kjo është me të vërtetë një grup, si kemi deklaruar javën e kaluar në leksion. Pra, ne nuk duhet ta bëjë këtë. Ne mund të ruani atë në një variabël. 

Apo ju e dini se çfarë? Kam dëgjuar dikush tjetër sugjerojnë atë. Çfarë tjetër mund të bëjmë me Stefan? Pse nuk kemi vetëm të dëbojë atë dhe vënë atë mbi ku numër një ishte. Pra, nëse ju doni të shkoni atje. Dhe në të vërtetë, kjo është një zgjidhje shumë e mirë. Tani në njërën anë, unë kam lloj e bëri problemin edhe më keq. Katër tani është më larg larg nga ku ajo duhet të jetë. Ajo duhet të jetë në drejtim të këtij gjysmë. 

Por ju e dini se çfarë? Kjo mund të ketë qenë fat i keq. Ndoshta numri tetë ishte këtu. Dhe kështu, ndoshta ne do kanë marrë me fat, dhe shtyrë tetë më afër deri në fund. Pra, në fund të ditës, Kjo lloj e të gjitha mesataret jashtë. Ne nuk duhet të kujdesen për katër. Të gjitha unë intereson tani është zgjedhjen elementin më të vogël. 

Dhe tani, ajo që unë jam duke shkuar për bëni është të harrojmë për numrin një përgjithmonë, sepse unë e di Lista prapa meje është renditur tani. Pra lista ime ishte më parë madhësia e tetë. Tani, është e madhësisë shtatë. Pra, problemi im po më i vogël, megjithëse në mënyrë lineare. Deri tani, unë jam duke shkuar për të zgjedhur element i tanishëm më i vogël, dy. Gjashtë, tetë, katër, tre, shtatë, pesë. Kjo ishte elementi më i vogël. Pra, çfarë jam unë do të bëj with-- çfarë ishte emri juaj përsëri? 

Joseph: Joseph. 

DAVID J. Malan: Joseph? Ne jemi duke shkuar për të lënë Jozefin në vend. Tani, unë jam duke shkuar për të pretendojë se këta njerëz are-- mirë, Unë e di se këto dy janë të renditura tashmë. Le tani të përqëndrohet në Pjesa tjetër e listës. Gjashtë është aktual më i vogël. Tetë është më e madhe. Katër tani është aktuale vogël. Tre tani është aktuale vogël. Dhe kështu që tani, unë jam duke shkuar për të zgjedhur tre, kush is-- çfarë është emri juaj përsëri? Serena: Serena. DAVID J. Malan: Serena, në qoftë se ju mund të kap numrin tuaj dhe swap with-- KALSANG: Kalsang. DAVID J. Malan: Kalsang. Come on mbrapa, dhe ne jemi do të bie në ujdi ata dy. Dhe tani, le të vënë këtë në autopilot. Unë jam duke shkuar për të shkuar dhe të lënë atë për ju djema për të zgjedhur elementët e ardhshme më të vogla. Dun, Dun, murmë, dun. Numri katër, çfarë duhet të bëni? Shkëlqyer. Tani, unë jam duke shkuar për të bërë një abone. Dun, Dun, murmë, dun. Unë shoh pesë është tjetër vogël. Tani, unë jam duke shkuar për të marrë një tjetër abone. Dun, Dun, murmë, dun. Gjashtë është më i vogël. Të mirë. Shtatë është më i vogël. Nuk ka ndryshim. Tetë është më i vogël. Done. 

Pra, ajo që ne kemi bërë vetëm nga iteratively një element të zgjedhur pas tjetrit është të zbatojë diçka që ne jemi duke shkuar për të formalizuar si përzgjedhës lloj. Dhe kjo është ndoshta edhe thjeshtë për të shpjeguar, në që fjalë për fjalë të gjithë ju doni të bëni është vetëm i mbajnë duke shkuar mbrapa dhe me radhë nëpër lista zgjedhjen, elementi tjetër i vogël, derisa ju jeni bërë. 

Pra, kjo është edhe më të thjeshta, ndoshta intuitive, se fundit. Le të provoni një e fundit. Në qoftë se ju djema mund të rivendosur veten në pozitat vijuese një kohë e fundit, le të shohim nëse ne nuk mund të tani formalizojë një qasje tjetër. Në fakt, do dikush atje doja të propozojë si tjetër ne mund të shkojë për të bërë këtë? Pa hedhur nga buzzwords apo lloj e përgjigjeve që janë të njohur tashmë, vetëm intuitive, çfarë mund të bëjmë? 

Audienca: [padëgjueshme]. DAVID J. Malan: Po. Pra, ka disa intuitë të madh atje. Gjërat e mira duket të ndodhë deri tani në shkenca kompjuterike, kur ne të ndarë dhe të pushtuar problemin e ndarjes atë në gjysmë dhe gjysmë dhe gjysmë. Dhe kështu me të vërtetë, ne mund të fillojë për të bërë këtë. Dhe në fakt, kjo do të jetë, ne do të shih, një nga zgjidhjet tona më të mira ende. Por le të kthehemi në atë para se të gjatë. Në fakt, ne jemi duke shkuar për të bërë se pak më vonë gjatë kësaj jave. Çfarë tjetër mund të bëjmë për të zgjidhur këtë? Kështu që të gjithë këtu është në mënyrë në dukje të rastit. E di çfarë? Në vend se të shkuar mbrapa dhe me radhë, mbrapa dhe me radhë, mbrapa dhe me radhë çdo herë, kjo ndjehet si Unë jam duke bërë një shumë të ecin. Pse nuk mund vetëm të fillojë në fillimi i listës, dhe vetëm vënë katër ku i takon? Pra më lejoni të supozojmë për momentin se lista ime është vetëm ky element i parë. Është katër të renditura në këtë moment në kohë, në qoftë se të gjitha që më intereson është gjithçka këtu? Kjo është lloj i trivially e vërtetë, e drejtë? Ashtu si listë që përmban një numër, dhe se numri katër është e renditura qartë. 

Pra, më lejoni vetëm të parashikojë se kjo listë është renditur. Por tani unë kam pjesën tjetër të kësaj liste. Deri tani, unë hasni dy. Ku ka dy padyshim përkasin në lidhje me katër? Para katër. Pra, çfarë mund të bëj këtu? Cili është emri juaj përsëri? 

Joseph: Joseph. 

DAVID J. Malan: Joseph, nëse ju mund të hap prapa për vetëm një moment me numrin tuaj. Dhe tani çfarë duhet të bëjë Stefan këtu? Le të zhvendoset Stefan mbi këtu. Dhe tani, le të Jozefi vijë këtu. Dhe tani, më lejoni të pohojnë se çdo gjë këtu është e renditura. Pra, rezultat i ngjashëm, por një qasje krejtësisht të ndryshme. Unë nuk kam shikuar edhe ajo që është atje poshtë. Unë vetëm i mbajnë duke marrë elementet si ata janë dorëzuar për mua, dhe të merren me ta. 

Deri tani, unë shoh numrin gjashtë. Ku ka numër gjashtë përket? Ne kemi dy, katër, gjashtë. Pikërisht aty ku ajo është e drejtë tani. Pra, le të lënë që vetëm, dhe tani pretendimit se kjo pjesë e lista është renditur tani. Dhe kështu, kjo ndihet krejtësisht i ndryshëm në atë që unë jam vetëm lëviz nëpër lista këtu lineare, dhe unë kurrë nuk jam duke e dyfishuar prapa. Po. Në rregull. Pra tetë, ku ju takon? Mu ketu. Përsosur. Deri tani, një. Uh-oh. Kjo ndjehet si ajo është do të jetë i shtrenjtë. Tani, në algorithm e mëparshëm, Unë vetëm swapped njerëzit. Kështu që unë mund të vënë atë të gjithë rrugën në fillimi, por pastaj u zhvendos Jozefin. Por në qoftë se unë të lëvizur Jozefi, tani çfarë do të jetë i gabuar? 

Tani, unë kam lloj undone-- kam ndërmarrë një hap përpara dhe pastaj një hap prapa, sepse tani Jozefi do të jetë jashtë funksionit. Pra, le ta bëjmë këtë. Nëse ju mund të marrë një numër dhe hap prapa për vetëm një moment. Si mund të put-- çfarë ishte emri juaj përsëri? 

Anan: Anan. 

DAVID J. Malan: Annan në vend? Çfarë duhet të ndodhë me respekt për të dy, katër, gjashtë dhe tetë? Ata të gjithë duhet të zhvendoset. Pra, nëse tetë do të donte për të zhvendosur së pari, pastaj gjashtë, pastaj katër, pastaj dy. Dhe pastaj Anan, në qoftë se ju do të si për të ardhur këtu, mirë. Por këtu, ne kemi vetëm lloj i pagoi një çmim në një pikë të ndryshme në algoritmin. Ndërsa herën e fundit me zgjedhjen lloj, dhe madje flluskë lloj, Unë jam duke ecur mbrapa dhe radhë, mbrapa dhe me radhë, e cila është sigurisht duke shtuar deri kohë-i mençur, dhe fjalë për fjalë hap pas hapi. 

Futje lloj, në fillim shikim, duket sikur është super të zgjuar, në atë që unë jam vetëm duke bërë përparim të ngadalshëm, rritje, por unë nuk jam duke shkuar ky mbrapa dhe me radhë. Por në qoftë se dikush është me të vërtetë nga e rendit, njoftimi të gjithë punën Unë vetëm kishte për të bërë. Unë kisha për të lëvizur gjysmën e listës vetëm për të bërë vend për numrin një. Pra, kjo është shuma e njëjtë e punës deri më tani atë ndihet, vetëm një lloj tjetër të punës. 

Le të vazhdojnë. Pra, tani ne e dimë se të gjithë ndërmjet një dhe tetë janë të renditura. Këtu, unë kam numrin tre. Nëse ju pëlqen të marr numri tre, hap prapa një të tillë. Dhe çfarë mendoni ju djema duhet të bëni? Yep. Pra, kjo është një tjetër një, dy, tre hapa. Tre njësi të kohës që vetëm kushtojnë mua, kështu që tre tani mund të përshtatet. Së fundi, shtatë. 

Le të shkojnë përpara dhe të ketë ju të marrë një hap prapa. Kjo është vetëm do të na kushtojë një njësi e kohës, por kjo është në rregull. Dhe tani, pesë-së do të të jetë pak më të shtrenjtë. Nëse ju dëshironi të hap prapa. Ne kemi nevojë për të lëvizur tetë, dhe shtatë, dhe gjashtë. Dhe pastaj të gjithë po zgjidhet tani. Pra, një dorë e madhe për vullnetarët tanë këtu. Shume faleminderit. 

[Duartrokitje] 

Ju faleminderit të gjithëve. Ju faleminderit të gjithëve. Pra, le të shohim tani se sa kushtueshme të gjithë se ishte. Le të konsiderojmë ndoshta thjeshtë nga këto, lloj flluskë. Dhe unë them thjeshtë, vetëm për shkak ju mund të zgjidhin atë me lakmi nga vetëm zgjidhur problemin pairwise këtu. Zgjidhur problemin pairwise këtu, përsëri dhe përsëri dhe përsëri, duke përsëritur si shumë herë të ju në të vërtetë nevojë për të. 

Pra, rezulton se me një lloj flluskë, mirë, sa hapa nuk kam për të të marrë në kalojë e parë e këtij algoritmi? Unë mund të take-- le see-- një, dy, tre, katër, pesë, gjashtë, shtatë. Dhe nuk ka tetë elemente këtu. Pra, kjo është si n minus 1 hapa për merrni nga fillimi i listës në fund të lista. 

Por me përzgjedhjes lloj, kujtojnë se unë jam zgjedhjen elementet përsëri dhe përsëri dhe një herë se është i vogël, Unë jam vënë atë në vend, por pastaj unë nuk jam në kërkim pas meje përsëri. Kështu që unë mendoj se është pak më i qartë pastaj se herë të parë, unë mund duhet të marrin të gjitha n minus 1 hapa për të gjetur elementin më të vogël. Pastaj kam vënë ato në vend, dhe unë dëbojë kush ishte këtu më parë. 

Por atëherë unë nuk duhet të mbajtur në kërkim në këtë element, sepse unë e di se është tashmë më të vogël. Deri tani, unë mund të shikoni në vetëm shtatë elemente, atëherë gjashtë elemente, pastaj pesë elemente, pastaj katër elemente. Dhe kështu matematikisht, nëse n është numri i elementeve ose numra se kemi filluar me, ju mund të imagjinoni se kjo është e njëjtë si n minus 1, plus n minus 2 hapa, plus n minus 3 hapa, plus n minus 4 hapa, të gjithë Mënyra poshtë për të vetëm një hap. Dhe unë jam në personin tim të fundit. 

Dhe në qoftë se ju kujtohet se një shumë i stats librave apo libra të matematikës kanë këto formula në Hardcover prapa ose para tyre, rezulton se këtë seri mund të shprehet më thjesht si kohët n n minus 1 mbi 2. Dhe kjo është në rregull në qoftë se kjo nuk është e në ballë e mendjen tuaj. Por kjo është me të vërtetë e vërtetë. Kjo është vetëm një mënyrë e thjeshtë e shkruar atë. Dhe pastaj në qoftë se ju mendoni se përsëri në klasën e shkollës, kur ju sapo filloni shumëzuar gjërat, kjo natyrisht, është vetëm katror n minus n ndarë nga 2. Të gjitha unë kam bërë është të zgjerohet shprehjet atje. Dhe kështu që le të rishkruaj këtë pak ndryshe. Kjo është n katrore e ndarë nga 2 minus n / 2. 

Pra, përsëri, unë jam vetëm lloji i aplikimit disa aritmetikë rregullat atje. Por vini re tani se termi më i madh në këtë shprehje, kështu që të flasin, n është se katror. Pra, po, kjo është n katror e ndarë nga 2, minus n / 2. 

Por në përgjithësi, në qoftë se është n do të jetë një vlerë e madhe, Unë do të thonë se n katror do të jetë faktori dominant. Është vetëm do të jetë një kontribues i madh me numrin e hapave sesa n / 2. Pra, çfarë dua të them me këtë? Le të provoni një shembull të thjeshtë, madje edhe pse matematikë merr një i madh pak. 

Pra, mendoj që ne kishim 1 milion njerëz në skenë, apo 1 milion gjëra se ne duam për të zgjidhur. Le të plug një milion në pikërisht këtë formulë për të parë se sa hapa ajo merr gjithsej për të zgjidhur një milion elemente të përdorur të themi, lloj përzgjedhje. 

Pra, ne do të kemi të njëjtën formulë si më parë. Unë do të plug një milion, kështu që unë të marrë një milion katrore ndarë nga 2, minus një milion e ndarë nga 2. Nëse unë bëj atë matematikë më parë këtu, ne kemi 500 miliardë minus 500,000, e cila na jep 499999500000, i cili është goxha i mallkuar i madh. 

Në fakt, në qoftë se ju krahasoni tani 499000000000, 999000000, 500,000 kundër vlerës tonë origjinal, 500 miliardë, kjo është aq damn afër. E drejtë? n katrore e ndarë nga 2 jep us-- ose më mirë, n katrore ndarë nga 2 na dhanë 500 miliardë. Kjo është goxha i mallkuar afër në 499,999,500,000, që do të thotë zbritur off 500,000, ose më në përgjithësi, zbritur off n katror, ​​jo të vërtetë një punë e madhe. N katror bën këto Numrat rriten me të vërtetë i shpejtë. 

Tani, kjo është e rëndësishme vetëm për aq si ne, si shkencëtarët kompjuterike, në përgjithësi nuk do të kujdesen aq shumë për nuancat e këtyre formulave dhe pikërisht ajo që përgjigje të sakta janë. Kemi kujdes vetëm se, ju e dini se çfarë? Në fund të ditës, kjo formulë është në mënyrë të n katror. 

Po, ne jemi duke e ndarë nga 2 në atje. Po, ne jemi duke zbritur off n minus 2. Por në fund të ditës, termi që me të vërtetë na lëndon dhe na kushton shumë hapa është se termi katrore. Dhe kështu që ajo që një shkencëtar kompjuteri do të në përgjithësi të bëjë po injorojnë të gjithë ata Termat vogla rendit, dhe vetëm shikoni në atë që kontribuon më me koston. 

Dhe kjo është e bukur, sepse ne mund të tani flasim në parim i përgjithshëm shumë më të madh në lidhje me algoritme, dhe mund të krahasohen ato. Dhe fakti që unë jam duke përdorur këtë O është e qëllimshme. Kur them në mënyrë e, unë jam në mënyrë specifike duke iu referuar diçka quajtur O. e madhe dhe e madhe o është një simbol që një kompjuter shkencëtar përdor për të përshkruar një kufi i sipërm për diçka. 

Pra, nëse ju them se një algoritëm është në O madhe të n katror, si unë propozuar vetëm një moment më parë, që do të thotë se në aspektin e drejtimin e saj herë ose efikasiteti i tij, ajo merr në mënyrë e n katror hapa. Ndoshta më shumë, ndoshta më pak. Por kjo është në mënyrë të n katror. Dhe kjo është kufi i sipërm. Kjo nuk do të jetë më e dhimbshme se kaq. Kjo nuk do të jetë n cubed, ose 2 me n, apo diçka shumë më të madhe. Ky është një kufi i sipërm për çfarëdo që kostoja është. Pra duke pasur parasysh se, le të konsiderojnë vetëm disa shembuj. Dhe kjo është vetëm një listë të fundme herë e shumë të zakonshme running për algoritme që është menduar të jetë ilustrues i disa gjëra që ne kemi parë tashmë. 

Kështu për shembull, në rastin e Zgjedhja lloj, çfarë unë jam duke pretenduar këtu po kalon ky lloj përzgjedhës Ora është në mënyrë të n katror. Në rastin më të keq, unë jam do të ketë një bandë e tërë e numrave të rastit këtu. Dhe siç e pamë matematikisht, në qoftë se unë mbaj duke ecur nëpër lista, përmes Lista, zgjedhjen e ardhshme të vogël element përsëri dhe përsëri, në qoftë se unë në fakt shkruani të gjitha hapat Unë jam duke marrë si kam propozuar formulaically para, kjo është me urdhër të n katror Hapat që unë jam duke marrë. 

Dhe kjo rezulton se flluskë lloj dhe futje lloj janë po aq të ngadalshëm në rastin më të keq. Mendoni, për shembull, futje lloj, shumë të fundit algorithm kemi trajtuar me të, e cila kishte të shikojmë në elementin, dhe pastaj futur atë ku i takon. Dhe pastaj kemi shikuar në elementin e ardhshëm, dhe futur atë ku i takon. 

Kështu që e konsiderojnë skenarin më të mirë të mundshme. Mendoj unë kisha vullnetarët e mia të vijë deri fjalë për fjalë si kjo, një anë të tetë, tashmë të renditura. Sa hapa është futje lloj do të marrë për të zgjidhur tetë persona, në qoftë se ata të arrijnë në skenë në kërkim si kjo? 

Tetë persona tashmë të renditura. Dhe unë e përdorin futje lloj. Kjo e fundit e algoritme. E pra, le të reenact agjërimin e vërtetë. Pra, nëse unë të fillojë këtu, unë shoh një të tillë. Ku ka një përket? Ajo i takon të drejtë këtu. Unë shoh dy. Ku ka dy takon? Mu ketu. Unë shoh tre. Ku ka tre takon? Mu ketu. 

Unë po shoh katër. Mu ketu. Pesë, gjashtë, shtatë, tetë. Nuk ka asnjë arsye për të përsëritur veten. Dhe kështu, sa shumë hapa është se në drejtim të n? Kjo është në mënyrë të n hapa, e drejtë? n minus 1. Por mora një numër lineare e hapa, dhe tani unë jam bërë. Pra, kjo është rasti më i mirë, edhe pse. Po në lidhje me rastin më të keq? Çfarë tetë ishin atje, dhe shtatë ishin poshtë atje, dhe një dhe dy ishin mbi këtu, kështu që se lista u ndryshuan me të vërtetë? 

E pra, çfarë ndodh në të vërtetë në qoftë se ky është numri? Dhe ne do të bëjmë vetëm disa shembuj. Çfarë nëse, vërtet, numri tetë është këtu, dhe uh number--. Pra, çfarë nëse, në të vërtetë, numri i tetë është gjatë gjithë rrugës gjatë këtu, dhe unë jam duke përdorur futje lloj? 

NE RREGULL. Unë pretendojnë në këtë moment kjo është në vend. Por tani, seven-- ku ka shtatë shkoni? Sigurisht, ajo shkon mbi këtu. Pra, unë kam për të lëvizur tetë mbi një vend. Tani gjashtë, ku do të shkojë? E pra, të gjithë të drejtë. Tani, unë kam për të lëvizur mbi tetë një vend, dhe shtatë më shumë se një vend, dhe pastaj unë pllum poshtë gjashtë. 

Pra, për herë të parë, ajo kosto mua një hap për të rregulluar gjërat, atëherë ajo të kushtojë më dy hapa për të rregulluar gjërat. Sa hapa është ajo do të marrë për të rregulluar gjëra për të vënë pesë në vendin e duhur? Tre. Sepse tani më duhet të lëvizur një, dy, tre. Sa hapa është ajo do të marrë për të vënë katër në vendin e duhur? 4 plus 5, plus 6, plus 7. 

Dhe kështu që është matematikisht identike me ajo që ne e përshkroi për përzgjedhjes lloj. Ne kemi këtë seri kjo është vetëm në rritje. 1 plus 2 plus 3 plus 4, ose anasjelltas, 7 plus 6 plus 5 plus 4 shton për sotëm si qëllim të në mënyrë të n katror. 

Pra më lejoni të përcaktojnë gjithashtu se flluskë lloj është edhe në n katror. Sepse me lloj flluskë, çdo herë që unë shkoj nëpër lista, Unë jam duke marrë afërsisht sa hapa? Çdo herë që unë fjalë për fjalë këmbë nga aty deri atje? Afërsisht hapa n. Por sa herë fuqinë unë nevojë për të shkuar nëpër lista? 

E pra, afërsisht n herë. Ndoshta n minus 1, por afërsisht herë n. E pra, pse është kjo? E pra, me flluskë lloji, nëse ne fillojmë me flluskë lloji, me listën në më të keqen e mundshme situatë, e cila përsëri është plotësisht prapa, çfarë do të ndodhë? Unë shkoj nëpër lista, dhe numri një i takon të gjithë rrugën atje. 

Por me flluskë lloji, sa larg nuk e lëvizin mbi kalojë tim të parë përmes listës? Sa spote e bën ai të marrë më afër në vendin e duhur? Vetem nje. Pra, nëse ju lloj arsye përmes kësaj, çdo herë përmes këtij algoritmi, Duke marrë afërsisht Hapat e Davidit n. Por sa kalon nëpër lista është ajo do të marrë për një të flluskë në të majtë, ku i takon? 

Ai e mori për të lëvizur si, Hapësirat n në këtë mënyrë. Pra, vetëm për të bërë klasifikim i listës, Unë duhet të ecin mbrapa dhe me radhë herë n. Dhe çdo herë, unë jam duke kërkuar në n elemente. Pra, bëni gjëra n n herë në rendi i n katror. 

Tani, ne do të shohim në disa e pantallona të shkurtra që janë të ngulitura në problemin e ardhshëm CS50 e vendosur, një tjetër qasje në këto, por tani për tani, le të vetëm të marrin në konsideratë disa herë të tjera running, veçanërisht nëse ato klasifikim marrin pak kohë për të zhytet në. Çfarë është një algoritmi që ne kemi parë tashmë që merr në mënyrë të hapave n? 

Çfarë duhet të marrë një numër lineare i hapave që kemi parë deri më tani? Cfare eshte kjo? Kërkimi Lista telefonit. Algorithm e parë. E drejtë? Ku ne jemi linear kërkim për Mike Smith? Ne te vertete. Nga java zero, kur kam filluar duke e kthyer një faqe në një kohë, dhe unë madje tha se ajo ishte lloj nga një ndjenjë lineare algorithm, dhe ne kishim këtë foto në Bordi me vijë të drejtë e kuqe dhe të verdhë drejt line, ato ishin me të vërtetë algoritme që janë në O madh të n. 

Sepse për të gjetur Mike Smith në një telefon Libri i faqeve n, në rastin më të keq, mund të marrë mua n hapa. Po në lidhje me marrjen frekuentimin? Një dy tre Katër Pesë Gjashtë. Çfarë është koha drejtimin e kësaj algorithm për të marrë frekuentimin? Big O i n, sepse në teori unë duhet të theksoj gjithë në dhomë. 

Tani si një mënjanë, çka në lidhje me optimization të tjera nga java zero? Dy, katër, gjashtë, tetë, 10, 12. Një shkencëtar kompjuteri do realizuar, prit një minutë, që është në rendin e n ndarë nga dy hapa. E drejtë? Sepse unë jam duke bërë dy njerëz në një kohë. Por ne jemi duke shkuar për të injorojë këto terma më të ulëta rendit, dhe ne jemi vetëm duke shkuar për të hedhin larg ndarjen me 2, dhe vetëm thonë, O i madh i n për këtë algorithm, si dhe. 

Po në lidhje me këtë? Ne do të kaloni mbi disa nga këto, por ajo që ishte një algoritmi që ishte log n? Që mori afërsisht hyni hapa n? Ndarja dhe sundo. Pikërisht. Ashtu si shembull librin e telefonit në Javën zero dhe më herët sot, ku kemi ndarë problemin përsëri dhe përsëri dhe përsëri. Ne tërhoqi atë në bord në javë zero si një linjë të lakuar të gjelbër, dhe kemi thënë atë ditë ishte një algoritmi logaritmike. 

Dhe me të vërtetë, numri i hapat që merr për të kryer ndarjen dhe të pushtuar, ose kërko binar si ne do të fillojmë duke e quajtur atë, si në librin e telefonit, është në rendin e log dhe hapat. Dhe kjo është pak e një të pazakontë. 

Çfarë merr një hap, ose më saktë një numër i vazhdueshëm i hapave? Ndoshta kjo është dy, ndoshta kjo është tre, por një shkencëtar kompjuteri vetëm thjeshton atë si O e madhe e 1, disa numër konstant prej hapave. Çfarë është diçka që ju mund të bëni atë merr një numër të vazhdueshëm të hapave? 

Çfarë është koha drejtimin e duartrokitje? Kohë konstante. E drejtë? Si, çfarë është koha drejtimin e bërë ndonjë gjë që merr vetëm një operacion, si të shtypura F Hello World. Kjo mund të thuhet të jetë kohë konstante, nëse rast më pak nga këndi me të shtypura F, çfarë mund të kohën running e shtypura F jetë në fakt? Dhe pse? Çfarë është n matëse në këtë rast? 

Audienca: [padëgjueshme]. DAVID J. Malan: Pikërisht. Numri i karaktereve ne duam të shtypura. Pra, kjo është shumë e context-sensitive. Sot, ne kemi qenë duke u përqëndruar shumë në shkronja dhe numra këtu në bord. Por ajo mund të jetë edhe karaktere në një varg aktuale. Pra, ajo rezulton atje është një tjetër masë që do të fillojë të kujdeseni për, dhe kjo është e kundërta O i madh, kështu që të flasin. 

Kjo është simbol omega. Ndërsa O i madh do të thotë se çfarë së, sipërme të detyruar në kohën tuaj running? Maksimalisht, sa kohë mund të marrë diçka? Omega-- keq kjo mban të vijnë up-- është e kundërta e kësaj, ku kjo është një më të ulët i lidhur nga Sasinë e kohës që diçka mund të marrë. 

Kështu që. për shembull, çfarë është një algoritmi që merr hapa gjithmonë ne katror n? E pra, një nga algoritme kemi parë sot, në fakt, mund të jetë se si. Përzgjedhja lloj. Përzgjedhja lloj është goxha budalla. Edhe nëse algorithm-- keq, madje edhe nëse array është renditur tashmë, Zgjedhja lloj do të mbajtur ecur nëpër lista për t'u siguruar se e ka më të vogël element përsëri dhe përsëri dhe përsëri. Dhe, edhe pse ju njerëzit i në Audienca e di se, prit një minutë, ju tashmë e kaluar Elementi më i vogël, kompjuteri nuk e di se deri sa ajo duket të gjithë rrugën nëpër lista. Në mënyrë të ngjashme, një ulët i detyruar që gjithashtu mund të merren parasysh mund të jetë koha lineare. 

Sa kohë nuk është marrë për Elementet lloj n në të mirë rast duke përdorur diçka si flluskë lloj? Supozoni se lista juaj është renditur tashmë. Ne i thamë flluskë lloj merr rendi i n katror hapa. Por, çfarë nëse ajo është renditur tashmë? Çfarë nëse ti e kupton pas një të kalojë nëpër rrjet që ju keni bërë asnjë këmbime? A ju duhet të mbani të bërë më shumë kalon? 

Jo. Pra, një i lidhur në flluskë lloji më i ulët mund të thuhet të jetë linear. Omega e n. Dhe ne mund të shohim në të tjerët e tyre si edhe. Pra, le të marrin një vështrim të shpejtë në vetëm një vizualizimi këtu për të parë se si këto dallojnë veten e tyre. Unë jam duke shkuar për të shkuar poshtë këtu në këtë faqe që është në dispozicion në faqen e internetit C50-së, por ajo do të jetë një dhimbje për të marrë të punës, pasi që ai përdor një teknologji të quajtur Java applets, e cila është një kryesisht pambështetur këto ditë, të paktën nga Chrome dhe disa të tjerë. 

Dhe më lejoni të shkoj përpara dhe të shpejtuar këtë dhe të shpjegojë se çfarë po ndodh. Ky është demonstrim i flluskë lloj, algorithm parë kemi shikuar. Dhe kjo është një vizualizimi në që çdo nga këto bare përfaqëson një numër. Sa më i madh bar, aq më i madh numri. Sa më e vogël bar, aq më i vogël numri. Dhe çfarë ju mund të shihni me sy, madje edhe edhe pse kjo po ndodh super të shpejtë, është se bar i kuq është si unë, duke ecur mbrapa dhe me radhë fiksimin e problemeve. Ju mund të shihni se elementet më të mëdha janë me të vërtetë bubbling deri në të djathtë, dhe elementet më të vogla janë bubbling deri në të majtë. Dhe këtu poshtë, në qoftë se ne në fakt shohim më nga afër, ne fakt mund të llogarisë Numri i krahasimeve dhe këmbime se janë duke u bërë. 

Por në vend, le të shohim ne algoritmin e dytë kemi shikuar më herët me tonë vullnetarë, përzgjedhja lloji. Vizualisht, ajo ka një efekt shumë të ndryshme. Por kjo është, përsëri, shumë intuitiv, në që ne të zbatojmë zgjedhjen e ardhshme të vogël element, dhe kemi marrë një pak fat. Se ndjerë rrënjësisht të shpejtë. Por nëse ne u këtë përsëri dhe përsëri dhe përsëri me shumë inputeve, ne do të shohim se kjo është me të vërtetë ende në O madh të n katror. 

Le të bëjmë një një të fundit këtu, futje lloj, e cila ishte algoritmi i tretë ne shikuar në, dhe risjell se kjo ka të bëjë me elemente si ajo ballafaqohet me to, por pastaj ajo ndoshta ndërrime gjëra mbi të bëjë vend, futur elemente ku ata i përkasin. 

Dhe kjo edhe përfundon duke i dhënë Rezultati përfundimtar. Tani të tre të atyre ndjerë shumë shpejt. Dhe me të vërtetë, unë u zhvillua ato në një clip mjaft të mirë. Por në thelb, ata janë të gjithë goxha e tmerrshme, të jetë i sinqertë. Të gjitha këto algoritme deri tani që të kandidojë në O madh të n katror të marrë mjaft e kohë për të kandiduar në fund. 

Dhe me të vërtetë, ne mund të shohim dhe të ndjehen kjo së fundi në qoftë se unë tërheq lart këtë demo tretë dhe të fundit. Ky është një tjetër vizualizimi që po ndodh për të treguar flluskë lloj në të majtë, lloj përzgjedhje në mes, dhe diçka, si një nga tonë dore ngre sugjeruar më herët, bashkojë lloj në të djathtë. Një ndarje dhe sundo strategji në të djathtë. Dhe kjo është, në fakt, ajo që ne jemi do të shikojmë në të mërkurën. Por le të kohës këto për të kandiduar në mënyrë paralele. Kjo është afërsisht i njëjtë numri i të elementë, të gjithë drejtimin në të njëjtën kohë. Bubble lloj vs përzgjedhjes lloj vs merge lloji. 

Tani, ata janë të gjithë duke teorikisht në të njëjtën kohë. CPU është në drejtimin të njëjtën shpejtësi, por ju mund të ndjehen si i mërzitshëm ky është shumë shpejt do të bëhet, dhe se sa shpejt kur ne injektuar një grimë e javës Algoritme ZERO-së mund ne të shpejtojë gjërat. 

Dhe tani le të krahasojmë këto në një formë fundit. Unë jam duke shkuar për të shkuar përpara në faqen e internetit CS50, ku ne kemi këtë link përfundimtare për sot, ku dikush në internet mirësi të vënë së bashku një video që kap Çfarë klasifikim të ndryshëm algoritme të tingëllojë si. Kjo është lloj futje. 

[Beeping] 

Ku ju jeni duke aplikuar një frekuencë bazuar në lartësinë e bar bar. Kjo është flluskë lloj. 

[Deformuar beeping] 

Vjen deri ardhshme is-- vjen up tjetër lloj is-- përzgjedhjes, ku përsëri, ne jemi duke zgjedhur element tjetër i vogël, dhe ne mund të shohim atë në rritje nga e majta në të djathtë. 

Merge lloj, fitues ynë deri më tani sot. Vini re se si është e ndarë gjërat në [padëgjueshme] gjysmë dhe lagjet. Lloj gnome, të cilat ne nuk kemi biseduar rreth, dhe krijon vizualisht dhe audally një grimë e një formë të ndryshme dhe të shëndoshë. Kthim prapa dhe me radhë, pastrimin gjërat. Gjithashtu shikoni heapsort në faqen e internetit këtë djalë. 

Dhe kjo është ajo. Ne do të ju shohim herën tjetër. 

[Whooshing DHE MUZIKA]