[Muzikavimo] Davidas J. Malan: Gerai. Taigi sveikiname atgal. Tai CS50 ir yra Savaitės trijų pabaiga. Taigi prisiminti per pastaruosius keletą savaičių, mes buvo išleisti gana šiek tiek apie laikas nuo C į programavimą, nuo sintaksės. Ir tai visai normalu, jei jūs vis dar kovoja su problemą, 2, turi būti beldžiasi savo galvą į sieną. Tai paslaptingas atrodantys klaidų pranešimai ir klaidų, kad jūs negali visiškai persekioti žemyn. Nes tikri, kad tik kelių savaičių jums pažvelgti atgal dalykų, pavyzdžiui, Cezaris, ir [? V-genair,?] gal net crack, ir suvokti, kaip toli jūs atėjote per trumpą laiką. Taigi, jei tai paguos, pakabinti ten dabar. Šiandien, nors mes pradėsime perėjimas dalykų aukštesnį lygį. Ir mes pradedame laiko savaime suprantamu dalyku, kad jūs žinote, kaip programa, arba jau ištakas kad komforto lygį. Ir mes pradėsime svarstyti, kaip galime eiti apie projektuojant programas daugiau efektyviai. Kaip mes galime eiti apie optimizavimą efektyvumas mūsų algoritmai ir paprastai problemoms spręsti įdomių problemų. Ir pradeda savaime suprantamu dalyku, kad jei norime, galime koduoti iki bet pavyzdžių mes turime omenyje. Taigi šiandien, mes neturime liesti klaviatūrą bet kodo forma. Tai bus daug aukštesnio lygio, ir galiausiai apie problemų sprendimo. Taigi, norint gauti iki to taško, leiskite man pasiūlyti kad šių septynių stačiakampiai atstovauja septynias duris, už kurie yra visa krūva numerius, tarp kurių yra skaičius 50. Leiskite projektą, tai apie tai ekranas čia taip pat. Ir siūlo, kad mums reikia Pasisiūlykite padėti rasti man priešais skaičių Internetas čia pamatyti. Nagi ", remiantis rausva. Gerai. Koks tavo vardas? JENNIFER: [nesigirdi] Davidas J. Malan: Atsiprašau? JENNIFER: Jennifer. Davidas J. Malan: Jennifer. Visos teisės Jennifer. Malonu jus matyti. Ateik iki. Taigi tai čia yra septynios durys, ir kas Norėčiau jums reikia padaryti, mums čia, prieš visus savo klasiokų, yra mus rasti skaičių, 50. Norėdami rasti skaičių, galite žvilgtelėti už nors iš šių durų, tiesiog paliesdami vieną iš durų, ir jis atskleis jo numerį. Ir pažiūrėkime, kaip greitai jūs Mus rasite skaičių, 50. 15. 16. 50. Gražiai padaryta. Gerai. Audringi plojimai už Jennifer. [Plojimai] Gerai. Taigi, kas buvo jūsų strategija rasti skaičių, 50? JENNIFER: Hm, aš maniau, gal jei - [Nesigirdi] Davidas J. Malan: O. Duok vieną sekundę. Taigi buvo jūsų strategija rasti skaičių, 50? JENNIFER: Taigi aš tiesiog pradėti pradeda rodyti, ką Pirmasis numeris buvo, ir tada aš pagalvojau, gal jei jie rūšiuojami, aš tiesiog laikyti paliesdami aukščiau? Davidas J. Malan: Gerai. Ir mes, atrodo, kad rado kad turi būti atveju. Nors galime žievelės atgal sluoksniai tik šiek tiek, ir jūs norite eiti į priekį ir atskleisti kitas duris Jums galėjo pasirinkti? JENNIFER: O, brangusis. Davidas J. Malan: Ak. JENNIFER: Taigi aš tiesiog pasisekė. Davidas J. Malan: Taigi jūs pasisekė. Gerai. Taigi nėra blogai. Bet tai įdomu įžvalga, tiesa? Jei manoma, ir tu gauti, tiesą sakant, šiek tiek pasisekė ten. Bet jei daroma prielaida, kad numeriai buvo rūšiuojami, galite tiksliau , kaip tai įtakojo Jūsų elgesys? JENNIFER: Taigi, jei jie buvo sutvarkyti, aš maniau gal mažiausio iki didžiausio. Davidas J. Malan: Gerai. JENNIFER: Arba, jei tai galų gale buvo tikrai didelis, tada didžiausiojo iki mažiausiojo. Davidas J. Malan: Gerai. Taigi didžiausiojo iki mažiausiojo, arba mažiausio iki didžiausio. Bet leiskite man pasiūlyti, tarkime, jūs turėjote Dotarłeś nelaimingas, ir manyti, kad jie nebuvo, tiesą sakant, rūšiuojami, kiek šios durys gali jums turėjo žvilgtelėti atsilieka ir pačiu blogiausiu atveju? JENNIFER: Viskas apie juos. Davidas J. Malan: Viskas apie juos. Taigi, galime apibendrinti, kad n. Būna, kad 7, bet tegul daugiau paprastai pasakyti, ten n durelės ekranas čia. Taigi, blogiausiu atveju, jums reikės ieškoti užnugario 7 durimis arba n durys. Ir taip tai tikrai yra, tai tiek Sėkmės šiandien, bet tai tikrai linijinis algoritmas rūšių, net jei buvo rūšies praleidžiant aplink. Ar tai teisinga? JENNIFER: Taip. Davidas J. Malan: Na, leiskite man pamatyti, jei jūsų strategijos pokyčiai, jei aš perkelti mus į Mūsų antrasis pavyzdys čia 7 skirtingų durys. Pačius numerius, tačiau tai laiko jie yra rūšiuojami. Kokia jūsų strategija čia bus, bando įdėti iš savo proto, kas kiti skaičiai buvo - JENNIFER: Gerai. Davidas J. Malan: - anksčiau? JENNIFER: Pradėkime su pirmuoju. Davidas J. Malan: Gerai. Pradėti su pirmąja. 4. Dabar, jei jūs ketinate eiti, ir kodėl? JENNIFER: 4 yra tikrai maža. Taigi, jei jie tarsi galbūt mažiausias iki didžiausio, ji turėtų būti du kartus, ir -. Davidas J. Malan: Gerai. Pažiūrėkime, kuris manote? JENNIFER: Išbandykite naujausia. Nice. Davidas J. Malan: Labai gražiai padaryta. Gerai. [Plojimai] Davidas J. Malan: Gerai. Taigi jūs iš tikrųjų daro tai siaubingai, nes jūs tai daro labai gerai. Kuris palieka mums negali padaryti tam tikrus dalykus. Taigi pabandykime įvirsta čia. JENNIFER: Gerai. Davidas J. Malan: Labai gerai padaryta, vis dėlto. Taigi jums pradėti iš pradžių, Jūs matė, kad tai buvo 4, tada jūs persikėlė į pabaigą. Bet manau, kad tu negali gauti pasisekė ten, ir tarkime 50 buvo kažkur kitur. Kas jūsų Trečias žingsnis buvo? JENNIFER: Grįžti į pradžią. Davidas J. Malan: Grįžti atgal į pradžią. Gerai, kad jūs tai jau palietė šios durys, kuris buvo 8. Gerai. Taigi, tai ne 50. Kur turite pažvelgė toliau? JENNIFER: Jei aš ne žinau, kad jie rūšiuojami. Davidas J. Malan: teisinga. Na, jei jūs žinote, jie rūšiuojami - JENNIFER: O, ar žinote, taip. Davidas J. Malan: - bet tu negali žinoti, kur 50 buvo dar? JENNIFER: Just keep going. Davidas J. Malan: Gerai. Gerai. Keep going. Gerai, kad aš galiu dirbti. JENNIFER: Gerai. Davidas J. Malan: Dabar, jei jūs tiesiog ketina nesustoti, kas yra jūsų algoritmas decentralizuoti remia į. JENNIFER: Linear -. Davidas J. Malan: Tai tipo linijinis. Bet leiskite man pasiūlyti, leiskite man įdėti vietoje. Leiskite man atnaujinti puslapį. tas pats numeris, pats susitarimas, patys durys. Tačiau prisiminkite, kad pirmosios dienos klasė kai mes sudraskė telefono knygą pusė, tarsi, ir tai, kas buvo mūsų strategija yra? JENNIFER: Pradėkite viduryje. Davidas J. Malan: Gerai. Taigi prasideda viduryje. Taigi eikime į priekį ir imituoti, kad. Pradėkite vidurį surengė atskleidžia, kad duris. Taigi skaičius 16. Taigi, ką stiprus vaikinas padarė, kuris sudraskė telefonų knygą per pusę, , kad patektumėte į kitą atspėti? JENNIFER: "Eik šioje pusėje. Davidas J. Malan: Ir kodėl į dešinę? JENNIFER: Jei jie tarsi mažiausias iki didžiausio, tada 50 turėtų būti tuo tikslu. Davidas J. Malan: Geras. Visiškai pagrįsta. Taigi, kaip telefonų knygos, jūs einate į teisę, o ne į kairę, bet čia yra raktas išsinešimui. Dabar jūs galite išmesti arba nuplėšti, pusė šios problemos, paliekant Jums ne su 7 durimis, bet tikrai tik su 3. Kuris yra maždaug pusė dydis problemą. Gerai. Taigi dabar, ką jums reikės padaryta po to, kai eiti tiesiai? JENNIFER: Taigi 16 yra vis dar gana maža, , palyginti su 50, tai gal bandysiu, kaip, šio vieno. Davidas J. Malan: Gerai. 42. Gerai, kad dabar kas yra jūsų instinktas sakau? JENNIFER: galiu mesti toli tai ir tada tik - Davidas J. Malan: Gerai. Geras, galite mesti toli kairę pusę ten. JENNIFER: - pasiimti šį vieną. Davidas J. Malan: Ir teisingai. JENNIFER: Taip. Davidas J. Malan: Taigi, nors sunku pamatyti, galbūt, kai tik 7 durys, pagalvokite apie tai, o dabar, iš nuoseklumas algoritmą tiesiog taikyti. Per praėjusius atveju tu gauti pasisekė, kuris buvo puikus. Bet tu naudoti euristinis, Sakyčiau. Jūs naudojote rūšiuoti savo instinktus ir žinant tai sutvarkyti, jei tai gana maža pradžioje, žinoma, mes turiu eiti daugiau į dešinę. Bet tam tikra prasme, jūs pasisekė, nes gal tai buvo numeris 100, o gal 50 buvo daugiau per vidurį. Gal 50 buvo dar čia. Tačiau tai, ką padarė šiek tiek kitaip šį kartą buvo, tu tą patį vėl ir vėl. Ir aš norėčiau teigti, kad ką tik nebuvo, nors įtakos telefoną knyga, pavyzdžiui, yra kažkas daug daugiau algoritmų, ir daug mažiau ypatinga dėžutę. Daug mažiau instinktyvus. Taigi, dienos pabaigoje, kaip būtų jūs apibūdinti efektyvumą pirmas algoritmas, kur ėjo kairės į dešinę, palyginti su Antrasis algoritmas čia? JENNIFER: Tai vienas turėtų, kaip, galbūt perpus sumažinti laiką, ar net daugiau, taip. Davidas J. Malan: Gerai, gal net daugiau. Leiskite stumti šiek tiek sunkiau, kad. Kas iš tikrųjų, jei mes ir toliau tai logika, mes tikrai perpus veikimo laikas su šio antrojo algoritmo mesti toli pusę numeriai, bet ką mes galime padaryti kitą iteracija, kai Jennifer atskleidė Antrasis numeris? Mes perpus Durų skaičiai dar kartą. Ir tada ką mes darome, po to, jei ten buvo daugiau durys žaisti? Mes norėtume perpus sumažinti juos, ir vėl, ir vėl, ir vėl. Ir tai buvo kaip jus vaikinai visi atsistojus ne pirmą savaitę klasė, pusė iš jūsų sėdi, pusė iš jūsų sėdi, pusė iš jūsų sėdi, kol vienas vienišas siela stovi. Ir mes sakėme, kad veikimo laikas kad žingsnių skaičius užtruko buvo apie kokia tvarka? GARSIAKALBIS 1: [nesigirdi] Davidas J. Malan: Taigi žurnalas bazė 2 n, arba tiesiog daugiau tiesiog, prisijunkite n. Taigi kažkas logaritminė. Ir grafikas nebuvo tiesi linija kad ką tik gavo blogiau ir blogiau, jis buvo Tai įdomu kreivė, kad nebuvo gauti taip blogai laikui bėgant. Taigi, galime eiti į šią idėją. Leiskite padėkoti Jennifer. Labai ačiū, kad atvykote iki. Ir vienas sek. Nėra stalines lempas šiandien, bet mes turiu CS50 streso kamuoliukus. JENNIFER: Šaunu. Davidas J. Malan: Gerai, čia. Dėkojame už patiria stresas čia. Gerai. Taigi pažiūrėkime, jei mes negalime dabar formalizuoti tai šiek tiek daugiau. Taigi dar kartą, ką tik padariau buvo iš esmės tas pats, kaip mes padarėme toje pirmąją savaitę. Tačiau užuot pabaigos tiesiog linijinis algoritmas, kurį mes vaizduojamas anksčiau, nes tai tiesi linija, pagal kurią, jei mes įdėti dar vieną duris ekranas, tada Jennifer būtų turėjo ieškoti, potencialiai Už dar vieną durų. Jei mes įdėti dvi duris, ji gali turėti ieškoti už dvi duris. Ir taip, ten buvo toks linijinis santykiai tarp dydžio problema, tarkim, x ašies ir Kiek laiko užtrunka išspręsti y. Bet vaizdas man buvo užuominos į anksčiau buvo tai žalia linija. Žalioji sąmoningai, kadangi jis tiesiog pajuto geriau. Teoriškai algoritmą, kai mes tai padarėme su telefonų knygoje, kai mes tai padarėme su vaikinai skaičiavimas tarpusavyje, o Antruoju atveju, kai Jennifer tik tai padarė čia, tai buvo tarsi iš esmės geriau. Kadangi tai buvo ne tik du kartus taip greitai. Tai buvo net ne keturis kartus greitai. Tai buvo visiškai priklausoma nuo to, ką dydis įėjimo buvo, kaip, kiek veiksmus, kurių ji galiausiai paėmė. Ir todėl ši paprasta idėja, kad mes visi buvo už suteiktas telefonų knygoje, gali panašiai būti taikomos į kažką panašaus į tai. Ir tai gali būti labiau atsainiai žinomas kaip, nes galbūt įsivaizduoti, skaldyk ir valdyk. Ne kitaip, ką mes padarėme, žinoma, su telefonų knygoje. Bet Pseudocode, išėmimą iš apyvartos, buvo tai. Taigi mes ne tai padaryti ir vėl, bet prisimenu kad pirmą savaitę, mes visi atsistojo ir tada pusė iš jūsų atsisėdo pusė jūs atsisėdo, pusė iš jūsų atsisėdo. Kad algoritmas buvo įgyvendintas tiek oszukiwanie Beje, tai, kad ji buvo ne man tik vienas skaičiavimas esmės, efektyviau. Tokiu atveju, man buvo sverto antrinis šaltinis. Rūšiuoti, daug CPU, daug smegenys, daug protingų žmonių kambarys buvo padėti man gauti nuo kažko linijinis kažką logaritminė, nuo kažko raudona kažką žalia. Tačiau šiuo atveju, Jennifer vien tik esmės patobulinti atlikimas savo pirmąjį algoritmus, vėl, tiesiog galvoju šiek tiek sunkiau. Ir dabar, kai ateina laikas įgyvendinti šie dalykai, suprasti, kas eilučių kodo, galite rašyti, pavyzdžiui kad jūs galite juos pakartoti dar kartą, ir vėl, ir vėl, tarsi į apsisukimo mados. Kadangi jūs nesiruošia turėti prabanga, kaip Jennifer darė pirma, tiesiog visa krūva IF ir pasakyti, Hmm, jei tai pirmas skaičius yra 4, leiskite man pereiti visą kelią iki pabaigos. Ooh, jei šis skaičius yra per didelis, leiskite man perkelti savavališkai atgal į antrąjį elementą sumą. Jūs pamatysite, kad tai bus daug sunkiau formalizuoti, ką mes, žmonės laiko savaime suprantamu dalyku, kaip labai protinga euristika, bet kompiuteris yra tik ketina daryti tai, ką pasakyti, kad tai padaryti. Dabar tai yra labai įdomu pasekmės. Šis grafikas yra tarsi skirtas rūšiuoti sukrėsti vizualiai, bet pastebėkite, kur yra tiesi linija šioje diagramoje? Kur yra linijinis grafikas kurį mes vadiname n? Na, tai tarsi link apačios Šio paveikslėlio, tiesa? Taigi viskas, mes padarėme tai mes tarsi Mastelis dėmesį į x ašies ir y ašis bandyti gauti tai, ką jausmas kitų rūšių kreivių atrodyti. Ir matematinis specifika išraiškos šiandien nesvarbu, kad daug, bet pastebėsite, kad yra daug algoritmai, kurie yra kur kas blogesnė nei kažkas, kad linijinė. Iš tiesų, n kubeliais atrodo gana neblogai. 2 n atrodo gana neblogai. n kvadratu atrodo gana neblogai. Ir mes pamatyti, ką kai kurie iš tų, gali būti iš tikrųjų šiandien. Ir log n nesijaučia taip blogai, bet geriau nei n yra žurnalo bazė 2 n. Bet žinote, tai būtų buvę dar labiau stebina, jei Jennifer ar mes, kad pirmą savaitę, turėjo sugalvoti kažkas, kad žurnalą žurnale n. Taigi, kitaip tariant, visa ši galimas intervalas sprendimų problemų, tačiau net ir čia, pranešimas kas nutiks. Kai aš nutolinti, kuris iš šių kreivių ketina įrodyti, kad absoliuti blogiausia ant ekrano tie dabar? Taigi n kubeliais atrodo gana blogai tuo metu. Bet jei mes padidinti ir pamatyti daugiau x ir y ašis, kas vyksta dominuoja galiausiai? Taigi iš tikrųjų paaiškėja, kad nuo 2 iki n, ir jūs galite suprasti tai tiesiog prijungti kai vis didesnį numeriai ir pamatysite, kad 2 n, tiesą sakant, plečiasi daug greičiau. Jeigu mes tikrai nutolinti nuo 2 iki n algoritmas visiškai sucks. Aš turiu galvoje, tai ketina imtis gana šiek tiek laiko ir kompiuteris bidonas per. Bet jūs pamatysite, laikui bėgant, ypač su ateities problemų rinkinius ir net galutiniai projektai, yra jūsų duomenų rinkinys tampa didelis, gerai? Net pirmoji versija "Facebook", kaip draugų skaičių ir registruojamų vartotojų gavo didelis, galite rūšiuoti telefonu jį ir įgyvendinti kažką su linijiniu paieškos, arba labai paprasta rūšiavimas algoritmas, kaip mes matome šiandien. Jūs turite pradėti galvoti sunkiau ir sunkiau apie šias problemas. Ir problemų vietų tipų, pavyzdžiui, "Facebook" ir "Google" ir "Microsoft", o kiti dirba apie būtent šios tarsi didelis duomenų rūšiuoti klausimų vis šių dienų. Gerai. Taigi Jennifer sėkmės, kad antrasis algoritmas, tiesą sakant, ji padarė nuostabiai gerai pirmas kartas, bet tegul rašyti kaip sėkmės, kad mes galite padaryti šį punktą. Antruoju atveju, ji subalansavo algoritmas, kuris kartojamas vėl ir vėl, bet ji paėmė už suteiktas tikra prielaida, kad leidome ją, bet ji išnaudojama gana išsamiai antras kartas, kai ji neturėjo pirmą kartą. Kuris buvo ką? Kad sąrašas buvo rūšiuojamos. Taigi, kuo greičiau sąrašas buvo rūšiuojami, mes teigia, kad Jennifer galėjo padaryti iš esmės geriau. 7 durys, taip yra ne tai, kad įdomus, bet manau, kad jį mes 7 mln durys. Prisijungti n neabejotinai bus atlikti daug, daug greičiau ilgalaikėje perspektyvoje. Bet ji turėjo būti durys surūšiuoti ja. Dabar, aš paėmė tai, kad laisvės iš anksto kompiuterio ekrane čia, bet manau, kad Jennifer turėjo padaryti, kad sau? Tarkime, kad nagrinėjamos durys atstovauja duomenis į duomenų bazę arba draugai registruoti Facebook, arba visi tinklalapiai internete, kad įvairių svetainių, gali prireikti į indeksą arba ieškokite per. Tarkime, kad jūs tiesiog turėjo neapdorotus duomenis nustatyti ir ji liko su jumis, arba Jennifer padaryti, kad rūšiavimą? Tai veikiau reikalauja, kad mes atsakome klausimas, gerai, kiek laiko būtų imtasi Jennifer, ar net mane, rūšiuoti tuos numerius iš anksto, , kad ji galėtų pasinaudoti, kad? Teisė? Kadangi išvada, žinoma, yra jei reikia man gana ilgai rūšiuoti skaičiai, kas gi rūpinasi, kad jums galite rasti, pavyzdžiui, 50 skaičių taip greitai, kaip Jennifer atveju, jei mes daugiau nei neliko visos laiką, jis paėmė rūšiuoti dalykų iš anksto? Taigi pažiūrėkime, jei mes negalime dažų paveikslėlį čia. Turiu visa krūva daugiau streso rutuliukai, jei tai padeda pralaužti ledus čia. O jei ne tai, mes reikia septynių savanoris - ant, Gerai. Oho. Taigi mes neturime praleisti apie stalines lempas, atrodo. Gerai. Taigi, kaip apie judviejų priekyje. Kaip apie jus du vaikinai atgal. Štai keturi. Kaip apie jus priešais penkių, šešių ir septynių. Štai čia. Jūsų draugo nukreipta jus, taigi, galėsite gauti prizą. Gerai. Ateik iki. Ir kodėl gi ne, mes turime jums vaikinai ateiti čia. Aš norėčiau duoti jums kiekvieną numerį. Ir eiti į priekį ir pasirūpinti patys identiškai, kas vaizduojamas ekrane. [Tarpines BALSAS] Davidas J. Malan: OOP, atsiprašau. Bugas. Gerai. Na, čia mes einame. Skaičius penki. Numeris šeši. Vienas, du, trys, keturi, penkių, šešių, septynių. O, tai yra nepatogu. SPEAKER 2: Aš tiesiog gauti -. Davidas J. Malan: Geras dalykas. Gerai. Dėkojame už dalyvavimą. [Plojimai] Gerai. Gerai. Taigi, mes turime keturis, du, šeši, vienas, trys, septyni, penki. Perfect todėl mes turime septynis savanorių čia kurie yra lygūs plotis masyvas, kad mes žaisti su anksčiau. Ir aš pasirinkau septynių priežasčių kad bus tik patogus truputį. Ir aš ruošiuosi pasiūlyti, pirma, kad mes surūšiuoti šių septynių savanorių. Jei norite, pirma, to say hello nors. Kadangi tai bus nepatogi keletą minučių. Įvesti save. GRACE: Sveiki, aš malonė. Aš į Leverett House antrakursis. BRANSON: Sveiki. Aš Bransonas. Aš į Weld pirmakursis. GABE: Sveiki. Aš Gabe. Aš į Cabot jaunesnysis. Neil: Aš Neilas. Aš Matthews pirmakursis. JASON: Aš Jasonas. Aš į Greenough pirmakursis. MIKE: Aš Mike. Aš Grays pirmakursis. JESS: Aš Jess. Aš į Leverett antrakursis. Davidas J. Malan: Puikiai. Gerai. Na, ačiū visiems mūsų savanoriai čia iki šiol. Ir po ranka iššūkis dabar vyksta būti išspręsti šie vaikinai, bet tada mes ketiname galvoti mažai sunku apie tai, kaip efektyviai mes iš tikrųjų rūšiuoti juos. Taigi tegul pirma pabandykite. Jus vaikinai galite matyti vieni kitų numerius tik pateikdamas aplink kampuose. Eiti į priekį ir per kelias sekundes, ir rūšiuoti patys nuo mažiausios nuo palikta didžiausia dešinėje. Eiti. Gerai. Geras. Tai buvo tikrai adyti greitai. Dabar kažkas čia, kas buvo algoritmas kad šie vaikinai taikomos? GARSIAKALBIS 1: mažiausiai iki didžiausių. Davidas J. Malan: Gerai. Jau Greatest tikrai rūšiuoti tikslas, tačiau aš nesu įsitikinęs, kad tai tikrai algoritmas. Jau didžiausias nepasako man žingsnis po žingsnio, ką daryti. Taip? GARSIAKALBIS 1: [nesigirdi] Davidas J. Malan: Gerai. Taigi, jei matote asmuo mažesnis nei jūsų telefono numeris, tada pereiti prie iš jų teisus. Taigi, tai dabar vis labiau išraiškingas, daugiau kaip algoritmą, nes galiu pasakyti, jei tai, tai. Taigi mes turime kokią nors sąlyga konstruktas. Ir šie vaikinai atrodė, kad tai padaryti kelias kartus, nes kai kurie iš jūsų persikėlė šiek tiek iš tolo. Taigi ten buvo matyt kažkokia iš kilpų vyksta jų protus. Tačiau pabandykime formalizuoti tai. Jei vaikinai galėtų atstatyti atgal šį susitarimą. Leiskite pamatyti, jei mes negalime įteisinti tai truputį, ir tada užduoti klausimą, tiesiog kaip efektyviai tai yra? Žinoma, kai mes tai darome lėčiau, jis ketina jaustis taip gerai algoritmas, bet pažiūrėkime, jei mes galime įdėti mūsų pirštus ant tikslius veiksmus. Taigi jūs du vaikinai yra keturių ir du. Arba jūs teisinga ar neteisinga tvarka? Akivaizdu neteisinga. Taigi mes pavertė. Dabar aš ruošiuosi persikelti žemę čia ir pasakyti, keturių iki šešių. Ar teisinga ar neteisinga? GABE: teisinga. Davidas J. Malan: teisinga. Šeši ir vienas? Nope. Sukeisti. Štai du apsikeitimo sandoriai. Šešių ir trijų? Nope. Sukeisti. Šešių ir septynių? Gerai atrodo. Septyni ir penkių? JESS: [nesigirdi] Davidas J. Malan: Gerai, mainytis. Ir rūšiuojamos. Gerai. Taigi akivaizdu, kad ne, tiesa? Taigi buvo daugiau vyksta. Bet, tiesą sakant, šie vaikinai, net tiesiog instinktyviai. nuolat juda. Jie ne tik sustabdyti, kai jie pataisyti vieną problemą. Taigi. Iš tiesų, aš ruošiuosi daryti tą patį. Aš teks rūšiuoti atsukti atgal į šią problemą pradžioje, arba šio masyvo pradžia žmonės, pradėkime vadindamas juos. Ir dabar kas turėtų mano algoritmas antrame perdavimą būti? GARSIAKALBIS 1: Tas pats dalykas. Davidas J. Malan: Tas pats dalykas. Ir tai, aš pradedu patinka, tiesa? Kaip greitai, kaip jūs galite rasti sau daro tą patį vėl ir vėl, tai tampa daugiau kaip algoritmą, ir mažiau žmogaus instinktas. Taigi dabar, čia mes einame vėl. Dviejų ir keturių? Ne. Keturių ir vienas? Ak, ten buvo iš tiesų, kai dirbti dar reikia nuveikti. Už ir trijų? Geras. Keturių ir šešių? Šešių ir penkių? Šešių ir septynių? Gerai, dabar padaryta. Gerai, Nr. Turiu eiti atgal. Taigi dabar, vėlgi, mes darome tai šiek tiek daugiau sąmoningai. Ir dabar ten tik vienas smegenų vykdant šį algoritmą. Vienas procesorius, jei bus. Ir tiesą sakant, tai vienintelis išteklius, mes ketiname turėti prieigą prie. Ir kai mes grįžti prie klaviatūros ir turėti kažką panašaus į C mūsų šalinimo, mes tik raštu programą kad galima padaryti vieną dalyką vienu metu. Kadangi šie vaikinai metu senumo, mes skolintomis kolektyvinė intelektinių gebėjimų sutelkimas kaip jus vaikinai darė savaitę nulio. Taigi galime laikyti tai daryti. Du vienas. Dviejų ir trijų. Trijų ir keturių. Keturių ir penkių. Penkių ir šešių. Šeši ir septyni. Priimta? Taigi, aš esu, bet leiskite man žaisti velnio advokatas. Ar man, kompiuterio rūšiuoti, kurie tiesiog padarė kerta šio masyvo žmonės, žinau, kad aš padariau? GARSIAKALBIS 1: Ne Davidas J. Malan: Taigi, kodėl? Ką turiu daryti, kad sudaryti ryžtingai, kad aš padariau? Tikriausiai dar vienas smūgis. Teisė? Nes aš žinau, kad iš ankstesnių pass kad aš ištaisyti klaidą. O tai reiškia, gal ten dar viena klaida kad man reikia ištaisyti. Taigi galiu tik būtinai pagal pervyniojimas, ir tada patikrinti, 01:59, du ir trijų, trijų ir keturių, keturių ir penkių, penkių ir šešių, šešių ir septynių. Gerai, dabar aš jokio darbo. Aš tikrai gali prisiminti, kad aš ne dirbti su kažkuo panašaus kintamojo, kaip int. Pavadinkite tai apsikeitimo sandoriai ir, jei sandoriai yra 0, kai aš gauti čia, ir jis pradėjo 0, tada Aš tiesiog kvaila nesustoti pirmyn ir atgal, tikrinimo ir vėl vėl, ir vėl, tiesa? Kadangi jūs įstrigti kai rūšies begalinis ciklas. Taigi, kuo greičiau ten 0 apsikeitimo sandoriai, galima teigti, kad šis algoritmas yra tikrai baigtas. Dabar galime įdėti pavadinimą apie tai. Algoritmas, kuris Siūlau mes tiesiog įgyvendinti yra kažkas vadinamas burbulas rūšiuoti, žinomas kaip pavyzdžiui ta prasme, kad skaičiai yra didesni rūšies burbulas savo kelią į viršų, arba iki į skaičių masyvo pabaigos. Bet kaip efektyvus buvo šis algoritmas? Kiek žingsnių aš fiziškai turi imtis, pavyzdžiui, norite surūšiuoti šių Septyni žmonės? Keturių iki penkių? Gerai, per daug, galiausiai bus atsakymas. Bet net ir tada, konkretus dienų skaičius nėra taip įdomu. Leiskite apibendrinti tai, kaip n. Taigi, jei aš n žmonių čia, ir jie buvo, tarsi, atsitiktine tvarka ne pradžioje, toje pradinės tvarkos. Na, kiek žingsnių aš turėti imtis pirmą perdavimą? Tai buvo vienas, du, trys, keturi, penki, šešių, ir jie septyni žmonės, todėl kad septynių, šešių -, kad tai n minus viena veiksmus pirmą kartą. Dabar, kiek žingsnių aš turėti imtis, kai aš apsukti iš naujo? Na, iš tikrųjų galime padvigubinti, kad jei mes tikrai norėjo, bet dabar, aš tikiu, tiesiog ketinate pasakyti, gerai, dar n atėmus 1. Taigi n atėmus 1 ketinate gauti erzina sekti, todėl galime tik suapvalinti šiek tiek. Taigi 2n veiksmus. Taigi 14 žingsnių, duoti ar priimti. Kiek kartų aš žingsnis kitą kartą? Na, tai 3n. tikrai. Ir dabar, blogiausiu atveju, Pavyzdžiui, kiek kartų aš norėjau dingo ir atgal, pirmyn ir atgal, vykdant šį algoritmą, Swapping žmonių kiekvieną perdavimą, maždaug? Tai iš tikrųjų n kvadratu, tiesa? Nes blogiausiu atveju, galite natūra iš pagalvoti apie tai intuityviai, nors tai gali užtrukti šiek tiek tiek laiko nuskandinti in Blogiausiu atveju, ką jie septyni žmonės atrodė, kad sąlygos susitarimą jų numerius? Visiškai atgal, tiesa? Ir tik imituoti, kad kas buvo tavo vardas? MIKE: Mike. Davidas J. Malan: Mike? Gerai, Mike, galite tiesiog prisijungti prie manęs per čia tik vieną sekundę? Tiesą sakant, ne. Atsiprašome Mike, tegul atgal. Kas tavo vardas? Neil Neil. Davidas J. Malan Neil. Gerai, Neil, galite ateiti su man, jei jūs neprieštaraujate. Taigi, aš ruošiuosi pasiūlyti tik paprastumas, kad Neil dabar jo Blogiausias atvejis. Tačiau prisiminti, kaip aš parašiau mano algoritmas. Aš lyginant, lyginant, lyginant, lyginant, lyginant, oi. Dabar šie vaikinai yra iš iš eilės, todėl aš nustatyti. Taigi vaikinai sukeisti. Tačiau mano, kad dabar, kiek toliau nėra Neil eiti? Tai maždaug n. Jūs žinote, tai nėra faktiškai n. Tai kaip, n atėmus 1, bet aš gaunu Sapīcis sekti mažai skaičius, todėl galime tik jį vadiname n. Taigi, jei Neilas juda vienas žingsnis maksimaliai kiekvienas laiką ir pereiti Neil vieną žingsnį, Aš turiu padaryti tai tikrai nuobodų perdavimą pirmyn ir atgal, tai yra maždaug Tokiu būdu, n žingsnių, iš n kartų iš viso, nes ji ketina imtis man kad daug žingsnių gauti Neilas visi būdas, kur jis priklauso. Jau nekalbant visi kiti, jei jus vaikinai visi buvo neteisingai nurodė taip pat. Taigi galime skambinti burbulas rūšiuoti n kvadratu. Veikimo laikas šį algoritmą, vykdo šią algoritmas, efektyvumas šio algoritmo mes tiesiog aprašyti daugiau paprastai kaip n kvadratu. Kuris yra gražus, nes aš galėtų padaryti tas pats pavyzdys su aštuonių žmonių, devynių žmonių, milijonai žmonių, ir kad Atsakymas yra nesiruošia keisti. Taigi, jei jus vaikinai ne tai, galime naujo jums, kur jums pradėti. Ir pabandykime kitus du metodus ir pamatyti, jei mes negalime padaryti iš esmės geriau nei šis. Taigi šiuo metu, aš pasiūlyti iš įvairių algoritmas rūšiuoti. Tai buvo labai protingas iš mūsų paskutinis kartas, ir vaikinai buvo teisė į teisė instinktai tiesiog rūšies Swapping poromis. Bet jei aš tikrai norėjo imtis šio tiesiog, ir mano tikslas yra perkelti visi mažai numerius šiuo būdu, ir stumti visi didieji numerius, Beje, kodėl ne aš tiesiog padaryti, kad labiausiai naivus būdas įmanoma ir pamatyti, jei aš gali padaryti geriau nei buvo gana sudėtingas algoritmas? Taigi pažiūrėkime. Keturi yra gana nedaug, todėl aš ketina palikti jus ten metu. Ooh, numeris du yra net geriau. Taigi, galite tiesiog žingsnis į priekį metu? Tai šiuo metu mano mažiausias sunumeruoti kandidatas, ir aš ruošiuosi prisiminti kad ten, patinka, kintamasis. Bet aš ruošiuosi nuolat tikrinti. Ar yra asmuo, kurio skaičius yra mažesnis? Šeši, Nr. O, ten Neil dar kartą. Taigi, aš ruošiuosi stumti jus atgal Rūšiuoti konceptualiai. Neil ateis į priekį. Ir dabar, kintamąjį, kad aš naudoju, kad sekti, kas yra mažiausias skaičius atnaujintas, kad turi Neil vieta. Na, pažiūrėkime. Trys, septyni, penki. Gerai, aš žinau, Neil buvo mažiausias. Kas yra paprasčiausias dalykas man dabar daryti? Nesiruošiu gaišti savo laiką tik burbuliuoja Neil vienoje vietoje į kairę. Kodėl ne aš tiesiog įdėti Neil kur jis priklauso, kuris, žinoma, kur? Visi pradžioje būdas. Taigi Neil, ateik pas mane. O kas buvo tavo vardas? GRACE: malonė. Davidas J. Malan: malonė. Gerai. Taigi malonė, deja, jūs rūšies į kelią. Taigi, kaip mes išspręsti šią problemą? Teisė? Jei tai yra masyvas, yra tik septynios vietos. Prisiminkite, kad su Rob, mes kalbėjome apie skelbiantis amžių, ir mes turėjo tik baigtinis skaičius amžius? Pati idėja čia. Mes turime tik baigtinio skaičiaus Ints. Malonė yra tipo mūsų būdas, taip, kaip mes nustatyti? Paprasčiausias būdas yra panašus, Malonė, atsiprašau. Jūs ketinate eiti per ten, mes galime padaryti kambarį. Dabar, jei jūs manote apie tai, gal mes tiesiog padarė problema blogiau. O gal mes padarėme, nes kas, jei Malonė buvo reikiamoje vietoje? Bet mes žinome, ji ne, nes kitaip, ji būtų buvusi stovint į priekį, o ne Neil šiuo metu, tiesa? Mes jau patikrinti jos numerį iš. Gerai. Taigi dabar, Neil reikiamoje vietoje, ir Galiu padaryti šiek tiek optimizavimas. Kitam minutę, aš ignoruoti Neil visi kartu, kad nebūtų gaišti savo laiką, arba atsitiktinai apsikeitimo jį į neteisingą vietą. Taigi dabar, kaip man rasti kitą elementas, kuris yra mažiausias? Du. Tai gana geras numeris, jei jūs norite žingsnis į priekį ir Aš prisimenu tave. Šeši, nieko gero. Keturi, trys, septyni, penki, nieko gero. Taigi leiskite man pereiti jums Jūsų tinkama vieta. Ir mes tiesiog pasisekė šį kartą. Dabar aš ruošiuosi juos ignoruoti du vaikinai, o dabar tai dar vienas pro tai. Šeši, kad gana mažas skaičius. Nagi pirmyn. Oi, atsiprašau. Grace numeris yra geriau, taip žingsnis į priekį. Keturi. Atsiprašome, Grace. Eik ir sugrįžk. Numeris trys yra geresnis. Septyni. Penki. Ir dabar kas tavo vardas? JASON: Jason. Davidas J. Malan: Jason. Taigi Jasonas dabar mažiausias elementas Aš pasirinktas. Kur jis ketina eiti? Taigi, kur yra šešių. Ir jūsų vardas vėl? GABE: Gabe. Davidas J. Malan: Gabe. Gabe tai tokiu būdu. Kas yra lengviausias, ką reikia padaryti? Sukeisti šiuos du vaikinai ir tęsti. Taigi dabar pažiūrėkime. Kas yra mažiausias? Keturi. Leiskite man tiesiog rūšies apgauti. Penkių bus mažiausias. Manau, kitą, jei jūs norite žingsnis į priekį, ką man daryti su šie vaikinai, su Gabe? Sukeisti dar kartą. Taigi dabar, vis dar šiek tiek iš eilės. Radau Gabe būti mažiausias, todėl Aš pop jį, perkelti jus vaikinai daugiau. Ir padaryta. Taigi atsakymas yra tas pats. Galutinis rezultatas yra tas pats. Kuris iš šių dviejų algoritmų kas yra geriau? Antrasis, aš girdėjau. Kodėl? GARSIAKALBIS 3: Tai n žingsnių [nesigirdi]. Davidas J. Malan: Tai n pakopomis labiausiai. Įdomu. Taigi tai yra nors? Taigi, kaip aš rasti mažiausias elementas? Kiek žingsnių aš turi imtis rasti mažiausią elementą? Aš ieškoti visą kelią pabaigoje, tiesa? Nes tokiu blogiausiu atveju, ką jei Neil buvo čia? Taigi, tiesiog rasti mažiausią elementą priima mane n priemonių, arba n ± 1. Bet Gerai. Taigi nustatyti Neil. Nepamirškite, kad per minutę arba tiek atgal. Bet kaip aš rasti kitą mažiausias elementas? Tai n atėmus 1, arba N ± 2 tikrai, iš etapų. Taigi Gerai. Taigi, aš n ± 2. Gerai. Taigi, kad jaučiasi šiek tiek geriau. Gerai. Kiek žingsnių kitą kartą rasti skaičių tris? Taigi n atėmus 4. Taigi jis mažėja, vienas mažiau žingsnis kiekvienos iteracijos. Taigi tai jaustis geriau, tiesa? Jei paskutinį kartą tai buvo maždaug n kartų n šį kartą tai n atėmus 1, plius n atėmus 2, plius n atėmus 3, plius n minus 4, taškas, taškas, taškas. Bet jei jūs prisimenate iš savo aukštosios mokyklos vadovėliai, tiek apgauti lapas gale, kuris turi formules, jei pridėsite šį numerių serijos, Koks bendras pakopų skaičius bus, kad aš čia? Tai yra vienas iš tų, kaip, n atėmus 1 times n, padalintas iš 2. Taigi leiskite man pamatyti, jei aš galiu traukti tai tik akimirką aukštyn. Ir vėl, aš natūra apvalinimo kai numeriai tik išlaikyti mūsų gyvenimas paprastas, bet aš pamenu, tai kažkas panašaus, jei Aš n ± 1 dalykų, tada n atėmus 2, tada n atėmus 3, tai maždaug kažkas panašaus į tai nei 2, o jei aš padauginti šį naudą, tai iš tikrųjų n aikštėje. Tai ne jausmas pernelyg gerai. n atėmus n per 2. Bet čia dalykas. Informatikos, kai problemos pradeda gauti įdomus, kai n bus tikrai didelis. Ir kai n bus tikrai didelis, kuris iš šios vertybės ketina valdyti visą iš kitų? Tai tipo "n kvadratu, tiesa? Taip, dalijant 2 yra gana gera. Bet jei kalbame apie milijardus vienetų duomenų ar trilijonai vienetų duomenis, Gerai, kad jūs dvigubai greičiau. Bet kas tikrai rūpi, jei, kad didelis skaičius, jei šis veiksnys yra tai, ką gauna didesni ir didesni. Ir tikrai, tai daro daugiau nei šis vaikinas skirtumas. Taigi, nors vaikinai teisūs, Antrasis algoritmas, mes jį vadiname pasirinkimas rūšiuoti, yra realiame pasaulyje, tiek greičiau potencialiai nes aš esu atsižvelgiant mažiau ir mažiau veiksmus kiekvieną kartą. Tai tikrai ne iš esmės greičiau. Nes jei mes iš tikrųjų žaisti šį už didelės reikšmės N, pabaigoje per parą, pakankamai didelis n, jis vis dar ketina jaustis gana lėtai. Na, leiskite man vieną paskutinis perdavimas tuo. Štai ką aš vadinčiau pasirinkimas rūšiuoti. Ar jums, vaikinai, iš naujo save vienas paskutinį kartą? Ir pastaruoju atveju, aš ruošiuosi pasiūlyti kažką vadinama įterpimo rūšiuoti. Įtraukiama rūšiuoti yra, konceptualiai šiek tiek kitaip. Užuot vyksta pirmyn ir atgal ir Pasirinkę mažiausią elementą, aš tik ketina kovoti su kiekviena iš šių vaikinai kaip aš susiduria juos ir įdėkite juos į savo teisingą vietą. Taigi, aš tik ketina pradėti malonės, ir matau, kad ji numeris keturi. Kur numeris keturi priklauso? Aš dar nepradėjo rūšiavimo nieko, taip malonė pasireiškia pasilikti teisę ten. Ir dabar aš ruošiuosi reikalauti, jei galėtumėte žengti žingsnį į dešinę, tai mano surūšiuoti sąrašas, tai yra mano Unsorted likę sąrašą. Taigi, dabar aš ruošiuosi pradėti kitą, o kas tavo vardas? BRANSON: Bransonas. Davidas J. Malan: Bransonas. Taigi Bransonas yra numeris du. Taigi, aš ruošiuosi jus už akimirką. Ir dabar, kur Jūs priklausote šiame masyve? Taigi prie malonės teisės. Taigi dar kartą, mes natūra padaryti Malonė padaryti daug darbo čia. Kur mes padėsime jums? Taigi, mes ketiname į skaidrę jums į kairę, ir įdėkite Bransonas ten. Bet dabar galiu reikalauti, kad vaikinai yra padaryta. Tačiau pastebėkite, aš ne naudojant papildomą erdvę. Jis vis dar 2 elementai čia 5 čia. Iš viso masyvo dydis yra 7, todėl aš ne oszukiwanie, viskas gerai? Taigi dabar mes turime, su Gabe čia skaičius šešių, kur Jūs priklausote? Jūs pasisekė dar kartą. Taigi jums likti teisus ten. Tiesiog šiek tiek žingsnį į dešinę tiesiog įsitikinkite, aišku, kad jūs surūšiuoti. Ir dabar mes turime Neil vėl skaičių vienas, kur jūs einate? Ir dabar, kur mes pradėsime matyti, kad Šis algoritmas, nors nuo pirmos žvilgsnio atrodo gana protingas, žiūrėti kas apie atsitikti. Jei galėtumėte žingsnis į priekį. Kur norime įdėti Neil? Taigi akivaizdu, čia, taip, kaip mes gauname Neil ten? Leiskite tai padaryti žingsnis po žingsnio. Gabe, kur jums reikia eiti? Taip, todėl į vieną didelį žingsnį, arba dvi pusės žingsniai padaryti vienas žingsnis ten. Malonė, kur jūs einate? Geras. Taigi dar vienas žingsnis. Ir, pagaliau, Bransonas? Kitas žingsnis. Ir dabar mes galime įdėti Neil į vietą. Taigi dabar, tęsti šią logiką. Nors mes negalime perkelti Neil daugiau, ir daugiau, ir daugiau, įdėti jį kur jis eina, blogiausiu atveju, kitas skaičius, mes galime susidurti galėtų būti skaičius, tarkim, buvo skaičius nulis, tada mes ketiname pereiti visus šie vaikinai. Tarkime, kad yra skaičius, neigiamas vienas, tada mes turime pereiti visi šie vaikinai. Taigi mes tikrai tik natūra prakeiktas problema aplink, pavyzdžiui, kad mes perkeliant išlaidas iš atrankos procesas, todėl įdėjimas procesas, taip, kad jūs, vaikinai tiesiog turėjo perkelti maždaug n atėmus kažką pakopų skaičius. Ir žingsnių skaičius yra tik ketina didinti, kaip aš pasirinkti daugiau numerių, jei aš turiu išlaikyti stumdymas jus vaikinai atgal, ir vėl, ir vėl. Taigi liūdna dabar visi šie algoritmai yra n kvadratu. Eikime į priekį ir dėka jų vaikinai, ir vizualizuoti šiuos šiek tiek skirtingai. Labai gerai padaryta. [Plojimai] Gerai. There you go. Dėkojame už - BRANSON: [nesigirdi] išlaikyti numerius. Davidas J. Malan: Ne, tu gali išlaikyti numerius, taip pat. Gerai. Gražiai padaryta. Gerai. Taigi pažiūrėkime, jei mes negalime dabar apibendrinti greičiau ir labiau vizualiai, ką tik atsitiko čia taip. Aš ruošiuosi eiti į priekį ir atsigriebti Firefox. Susiesime šią demonstraciją nuo kurso tinklalapyje. "Java" yra šiek tiek erzina, kad gauti darbo kai kuriose naršyklėse šių dienų. Taigi, jei jūs žaisti šį namuose, suprasite, jums gali tekti naudoti "Firefox" gauti darbo. Ir ką aš ruošiuosi daryti su šiuo demonstravimas yra taip. Apačioje, turiu visa krūva meniu pasirinktys, įskaitant pradžioje ir išjungimo mygtuką. Be to, kaip panaikinti, atrodo, kad klaidų šiose programose, kai jūs iš tikrųjų negali matyti pradėti arba sustabdyti mygtuką, jei turite arba komandą Alt plius ir padidinti, kuris smalsiai rodo jums daugiau mygtukų. Taigi tiesiog FYI, jei tu žaidi su šia namuose. Dabar aš ruošiuosi spustelėkite Start tik momentas, kai nurodant vėlavimo, kaip, 200 milisekundžių čia, tiesiog todėl mes galime pamatyti, kas atsitiks. Taigi, aš teigti, kad tai yra vizualizacija pirmojo algoritmo šie vaikinai padarė, burbulas rūšiuoti, kuriuo mes pavertė žmones porinių. Pagrindinis įžvalga šios vizualizacijos yra tai, kad iš stulpelių aukščiai atstovauja skaičiaus dydį. Taigi aukštesni baras, didesnis skaičius. Trumpesnis baras, mažesnis skaičius. Ir jei pastebėjote, mes ketiname per pirmoji iteracija šio algoritmo Swapping dideli ir maži numerius, kad nedaug ateina pirmas ir didelis skaičius eina į dešinę. Ir kuo greičiau mes gauname iš masyvo pabaigos daug daugiau skaičių nei septynių, mes ketina grįžti į pradžią. Ir numatyti tai. Dėl toli į kairę, kad mažai vaikinas vyksta apsikeitimo į šoną, ir tai procesas kartojasi. Dabar ši vizualizacija greitai gauna nuobodu, todėl leiskite man eiti į priekį ir sustabdyti tai, pakeiskite uždelsimo kažką daug greičiau tik gauti dabar jaustis Šis algoritmas. Taigi, nors aš pagreitino jį, tai kaip atnaujinti savo procesorių, perkant naujas kompiuteris. Aš iš esmės nepasikeitė mano algoritmas, bet jūs iš tiesų gali pamatyti daugiau aiškiau nei su žmonėmis, kad didelis numeriai burbuliuoja iki viršaus, ir tai yra nedidelis kiekis burbuliuoja į apačią. O dabar tai, ką čia sutvarkyti. Ir kaip žemę, aikštėse, yra tik keletas buhalterijos ten padėti jums suskaičiuoti, kiek palyginimus, ar kiek apsikeitimo sandoriai turi iš tikrųjų buvo padaryta. Na, pabandykime vieną kiti matėme. Leiskite spustelėkite burbulas rūšiuoti čia, ir leiskite man pasirinkti, ir visas šis interneto puslapis yra šiek tiek klaidų. Tegul prisiima riziką ir paleisti jį dar kartą. Čia mes eiti. Taigi darykime atrankos rūšiuoti. Aš nežinau, kodėl meniu pasirodo ten. Leiskite priartinti nustatyti, kad klaida, tai pakeisti iki 50. Ak, tegul iš tikrųjų kad daug greičiau. Penki milisekundžių ar taip, ir pradėti. Taigi tai yra pasirinkimas rūšiuoti. Taigi dar kartą, manau, apie tai, ką mes padarė su žmonių čia. Mes išgyveno masyvo ir pasirinktas mažiausias elementas vėl, ir vėl, ir vėl. Dabar aš teigia, kad vis dar buvo gana blogai. Tai buvo dar n kvadratu, duoti ar priimti, bet tai buvo, realiame pasaulyje, tiek greičiau, nes aš iš tikrųjų atsižvelgiant šiek tiek mažiau veiksmus kiekvieną kartą. Bet mes kalbame tik ką? Gal 40 ar taip barai čia? Mes nekalbame 40 mln. Taigi, tai nėra visiškai aišku, man, kad iš tikrųjų buvo didelis pelnas. Leiskite man dabar grįžti atgal ir pakeisti mūsų Trečiasis algoritmas, kuris buvo pasirinkti įterpimo rūšiuoti. Ir dabar tai tikrai Buggy nes meniu tikrai neturėtų būti ten. Taigi dabar mes pereikite atgal čia ir pradėti šį algoritmą. Rėkauti, paleisti ir sustabdyti. Taigi tai vienos rūšies yra gana modelį jai, kai mes vėl įterpiant žmonėms, arba Šiuo atveju, barai į jų atitinkamą vietą. Ir tai jau padaryta prieš Aš atsisukau. Bet tai viena, taip pat teoriškai vis dar n kvadratu. Taigi pažiūrėkime, jei mes negalime apibendrinti tai taip. Aš ruošiuosi eiti į priekį ir tiesiog duoti mums tarsi paplitęs būdas kalbėti apie šiuos dalykus, leiskite man pristatyti tik žymėjimo tiek čia. Jūs ruošiatės pamatyti kažką vadinama didelis O, nes jis yra tiesiog didelis O. Ir tai yra taip, kad kompiuteris mokslininkas ar matematikas net naudoja apibūdinti važiavimo laikas kai kurių algoritmas. Kiek žingsnių ji iš tikrųjų užtruks? Dabar aš ruošiuosi varžyti save su mano rašysenos čia vos akimirką. Bet leiskite man eiti į priekį ir pasakyti, kad tai bus didelis O čia. Ir leiskite man pristatyti vienas kitas simbolis, kapitalas omega. Omega bus atvirkščiai, vadinasi, iš esmės didelės O. kadangi didelis O reiškia, blogiausiu atveju, kiek laiko gali kai algoritmas, imtis visų būtinų terminai n omega ketina būti, kiek laiko jis galėtų imtis geriausiu atveju. Ir mes pamatyti, ką mes vadiname geriausiu atveju vos akimirką. Taigi, pradėkime ką nors paprasto. Leiskite man pradėti su linijiniu paiešką. Taigi, ne rūšiavimo. Mes vadiname tai linijinis paiešką. Ir dabar, kad mažai lentelė iš šio. Ir dabar, linijinės paieškos atveju blogiausiu atveju, kiek žingsnių yra ji ketina imtis man rasti skaičius savavališko pasirinkimo? Ir yra N Iš viso durys arba N Iš viso numeriai. Blogiausiu atveju. Kiek žingsnių aš teks imtis rasti skaičių 50 masyve iš n durų? Ir kodėl? Kadangi tai gali būti visi būdas per ant pabaigos. Taigi, panašiai kaip Jennifer susidūrė, numeris 50 buvo visą kelią per, todėl Blogiausiu atveju linijinis paieška yra didelis O n, mes pasakyti. Ką apie geriausiu atveju, jei jums tikrai pasisekė? Tai tiesiog ketina imtis dar vieną žingsnį, ar pastovus pakopų skaičius. Taigi mes aprašysime, kad: 1. Taigi, tai yra gana gera. Dabar ką daryti, jei mes padarėme kažką kaip dvejetainis ieškoti? Taigi dvejetainis paieška, blogiausia bylą, paėmė, kiek laiko? [Tarpines BALSAS] Davidas J. Malan: Taigi, iš tikrųjų, aš išgirdo po poros vietose. Taigi tai tikrai log n, duoti ar priimti, nes, kaip mes padalinti sąrašą per pusę vėl, ir vėl, ir vėl, mes galime rasti, galiausiai, vertė, jei jis ten, bet yra laimikis. Kas yra prielaida, kad mes turime imtis už suteiktas naudojant dvejetainį paieškos? Ji turi būti rūšiuojami. Tai nėra rūšiuojamos, galite padalinti dalykas per pusę vėl ir vėl, ir jūs gali eiti į kairę, ir jūs galite eiti į dešinę, ir galite eiti į kairę ir į dešinę, bet jūs nesiruošia rasti elementą, jei sąrašas nėra rūšiuojamos, nes galite praleisti jį. Kadangi jūsų euristini ↩ u, vykstantiems į kairę ar teisė bus klaidingi, jei tai iš tiesų nėra rūšiuojamos. Taigi, čia yra tarsi paslėptų išlaidų naudojant kažką panašaus į tai. Dabar eikime į mūsų rūšiavimo algoritmai neieško - Oh, iš tikrųjų eikime šiuo pavyzdžiu. Dvejetainė paieška geriausiu atveju? Taip pat 1, jei ji tiesiog atsitinka būti ir labai vidutinio masyvo arba iš telefonų knygos viduryje. Dabar darykime burbulas rūšiuoti. Taigi dar kartą, dabar mes patekti rūšių, o ne paieškas. Blogiausiu atveju, kiek žingsnių argi mes reikalavimas burbulas rūšiuoti ketina imtis? n kvadratu. Taigi, aš ruošiuosi padaryti tai. Ooh, mano ranka atrodo dar blogiau kai jis Numatoma, kad didelis. Gerai. Taigi tai n kvadratu. Ir geriausiu atveju burbulas rūšiuoti, kiek žingsnių ji ketina imtis? 1, aš girdėjau. GARSIAKALBIS 1 n. Davidas J. Malan: n išgirdau. GARSIAKALBIS 1: 2. Davidas J. Malan: 2, aš girdėjau. Ar girdžiu 3? Gerai. Taigi, aš girdėjau, 1, n, 2, bet tegul pasirinkti išskyrus mažiausiai pirmojo iš šių pasiūlymai, 1. Tai nėra blogai, instinktas, nes jį tipo taip šabloną čia. Bet jei tai trunka tik 1 žingsnį, kaip į pasaulis galėčiau teigti, kad sąrašas yra rūšiuojamos, nes jei aš leidžiama tik gerti po 1 žingsnį Kiek elementai galėčiau tikrai įsitikinkite? Na, tiesiog 1, kuris reiškia, kad yra n atėmus 1 elementai, kurie gali būti iš kad ir aš tik ketina tikėjimu po žiūri 1 elementas, kuris dalykas rūšiuoti. Taigi, 1 neteisingas, čia. Taigi minimaliai, kiek turiu pažvelgti? [Tarpines BALSAS] Davidas J. Malan: n atėmus 1, ar tikrai, n, nes man reikia pažvelgti į kiekvieną elementas, įsitikinkite, kad tai ne iš eilės. Bet vėl, mes tarsi banga mūsų rankos ties mažesniais skaičiais ir manyti, kad n tampa didelis, jie neįdomu vistiek. Štai burbulas rūšiuoti. Ir dabar, darykime paskutinius du. Atrankos rūšiuoti, ir tada mes padaryti įterpimo rūšiuoti. Ir tada mes bus smūgis protus su kažkuo daug geriau nei visiems. Gerai. Kas yra blogiausias atvejis veikia laikas atrankos rūšiuoti? GARSIAKALBIS 4: n kvadratu. Davidas J. Malan: n aikštė, aš klausos. Bet kodėl n kvadratu, intuityviai? GARSIAKALBIS 4: Kadangi mes tiesiog padarė. Davidas J. Malan: Kadangi mes tiesiog padarė. Gerai. Geras atsakymas. Bet intuityviai, kodėl atrankos rūšiuoti n kvadratu? Ką mes turime padaryti vėl ir vėl? Mes turėjome išlaikyti nuskaitymo, yra Jūs mažiausias, tu mažiausias, tu mažiausias. Ir patenkintas, mes galėjome imtis n žingsniai, tada n minus 1, tada n ± 2. Bet jei jūs rūšies pridėti tie visi, arba priimti jį tikėjimu, kad aš pridėjo juos iš anksto, mes beveik n kvadratu minus kai kurių mažesnių skaičių. Taigi, aš ruošiuosi tai vadiname n kvadratu. Bet su atrankos rūšiuoti geriausias atveju, kiek žingsnių jis ketina imtis domėjosi? GARSIAKALBIS 5 [nesigirdi] Davidas J. Malan: Tai, deja, dar n kvadratu, tiesa? Nes jei aš pasirinkdami mažiausias elementas, ir mes turėjo septynis žmones čia Aš tik žinau, kai aš gauti labai galo, radau mažiausias numeris, kur jis arba ji galėjo būti. Bet kaip man rasti kitą mažiausias skaičius? Turiu daryti kitą leidimą. Taigi, geriausiu atveju, kas yra indėlis į atrankos rūšiuoti? Tai jau tarsi sąrašas, numeris vienas, numeris du, numeris trys, skaičius keturi. Bet aš kompiuterį. Galiu tik pažvelgti į vieną dalykas vienu metu. Aš negaliu rūšiuoti žengti žingsnį atgal kaip žmogus ir sako: ooh, tai atrodo teisinga. Galiu tik priimti sprendimo teisingumas pasirinkimas yra rikiuoti pagal atrankos mažiausias skaičius. Bet net jei manau skaičius iš pradžių, jei aš nežinau nieko daugiau apie kiti skaičiai, kurios aš neturiu, viskas, ką aš žinau, kad aš buvo perduoti masyvą arba Durų rinkinys, už kurios yra numeriai, vienintelis būdas aš žinau, kad vienas buvo mažiausias? Jei gaunu visą kelią čia ir suvokti, Damn, vienas iš tikrųjų buvo mažiausias. Bet kaip man tada nustatyti, kad du yra kitas mažiausias? Tokiu ta pati neveiksmingumo vėl ir vėl. Taigi pagaliau, su įterpimo rūšiuoti, kaip, blogiausiu atveju, Ar mes pasakyti, kad tai atlieka? Jis taip pat yra n kvadratu. Ir kaip apie su geriausiu atveju? Mes palikti, kad kaip Įspūdingos filmą. Mes užpildyti tą tuščią kito karto, bet pirmiausia leiskite man pasiūlyti, kad mes esmės padaryti geriau nei visa tai, gerai? Taigi, manau sau, ką įdėjimas rūšiuoti manimi bus. Na, tai nebuvo labai dramatiška, nes aš tik viena kad pamačiau pakeitimą. Oho. Gerai. Taigi čia mes turime šiek tiek kitoks demonstravimas. Jei aš priartinti čia, pamatysite, kad kairėje turime burbulas rūšiuoti, į vidutinio turime pasirinkimo rūšiuoti, ir kas teisinga, mes turime tai, ką mes turite ne pažvelgė dar vadinamas sujungti rūšiuoti. Tačiau mano, kad tai, ką mes jau čia darai iki šiol šiandien. Kai Jennifer pirmą kartą atėjo į sceną, mes išgyveno skaičių masyvas vėl, ir vėl, su linijine paieškos, ir mes turime tiesinę važiavimo laikas, didelis O n, taip sakant. Kai mes dabar mano pirmą savaitę klasės, kai mes turėjome skaldyk ir valdyk, ir mes Telefonų knyga ašarojimas, ir Jennifer, ir mes kartu pagausėtų, kad raktas įžvalga, kuris buvo kartoti sau vėl ir vėl kažkaip mesti toli, mesti toli, mesti toli pusė problema, ar Apskritai, dalijant per pusę problemą, ir tada gydyti mažesnių gabalas kaip konceptualiai ekvivalentas problema į kitą, mes kažkaip iš esmės geriau. Bet burbulas rūšiuoti, su atranka rūšiuoti, su įterpimo rūšiuoti, mes gali tokios įžvalgos, kad Jennifer padarė. Mes gana daug tik vaikščiojo pirmyn ir atgal visa krūva kartų, ir mes nežymiai dalykų šiek tiek, Swapping tokia tvarka, gal įdėdami arba pasirinkdami. Bet dienos pabaigoje, aš daug nepatogu vaikščioti pirmyn ir atgal. Mes tikrai ne sverto kažkas protingas kaip Jennifer patiko dalijant ir užkariauja. Taigi sujungti rūšiuoti, priešingai, kurį mes nematysite tol, kol kitą savaitę jis ketina sverto, kad esminė idėja dalijant įėjimas, tada perpus, tada perpus, tada perpus. Ir kiekvienam tos linijos iteracija, rūšiavimas yra kairėje pusėje, o dešinėje pusę, tada kairėje pusėje, kairėje pusėje, ir dešinėje pusėje kairėje, tada kairėje pusėje, dešinėje pusėje, ir Dešinė pusė iš dešinės pusės. Ir kartoti vėl ir vėl. Taigi pamatysite tai vizualiai, bet tai yra tai, kas mūsų laukia kitą savaitę. Ir apskritai, kai mes galvojame tiek tiek sunkiau dėl tokio problema. Mes n kvadratu kairėje pusėje, n kvadrato viduryje, ir n log n dešinėje. Taigi, čia yra jūsų tikrasis Įspūdingos filmą. Dar pasimatysime pirmadienį. [Plojimai]