[Powered by Google Translate] [Teden 3, Nadaljevanje] 

[David J. Malan - Harvard University] 

[To je CS50. - CS50.TV] 

V redu. Dobrodošel nazaj. To je CS50 in to je konec tedna 3. 

Torej za tiste, ki ne poznajo, lani začel Harvard, kar se imenuje Innovation Lab, ali i-laboratorij, ki je čudovita stavba čez reko na univerzi v HBS ki je odprt za študente, dijake, študente GSA iz vsega kampusu, vključno s fakultete, in to je kraj, da pridejo skupaj za delo na inovativne stvari, zlasti podjetniške stvari če in 0 ali več prijatelji razmišljate o tem kaj podjetniške niti v tem razredu, po tem razredu, ali pa še dlje. 

Torej ena od stvari, ki jih storijo v obdobju J je ta izlet, od katerih je ena v New York, od katerih je Silicijevi dolini. Vesolje je zelo omejena, vendar je možnost, da Masiranje ramena z MBA in podiplomski študenti po kampusu in dejansko preživeti nekaj časa na teh področjih, za katera klepetali do novih podjetij, klepet podjetniki in podobno. Torej, če zanima, si oglejte ta URL. Prav tako je na voljo na spletnih diapozitivih. 

Bi lahko omilijo hišno zvok samo malo? Če bi radi, da se nam pridružite na kosilo v petek, 13:15, v Fire & Ice, prosim glavo tam. Opravičilo, če je obrazec že napolnjena do takrat, ko prideš tja. Ampak bomo nadaljevali tradicijo naprej. 

Danes smo še višjo raven razprave o različnih problemih, ki jih lahko reši, osredotoča veliko manj, danes vsaj na kodo in še veliko več o idejah. Torej menite nazaj na teden, 0, ko smo trgali telefonski imenik na pol, Cilj je bil, da narediš nekaj, priznam, malo dramatična ampak za pošiljanje opozoril, da iskanje nima, da je nujno, kot je očitno na prvi pogled, kot si morda mislite. In reševanje težav na splošno ne bi nujno vedno najboljša - Najbolj očitna rešitev ne bi nujno najboljši. Tako smo imeli ta imenik in, odkrito rečeno, vsi v tej sobi je imel instinkt, najbolj verjetno, da bi začeli v sredini, ko iščejo Mike Smith in nato šel v levo ali desno temelji na katerem koli črko zgodilo, da smo končali na. 

Ampak to preprosto idejo, da smo ljudje za samoumevno, dokler Res bi se morala začeti prihajajo v ospredje svojega uma ker so težave, dobili veliko bolj zapleten, kot telefonski imenik, te iste preproste, briljantno vpogled so tisto, kar se dogaja, da se nam za reševanje bolj zapletenih in bolj zanimivo težave, med njimi nekatere stvari, ki jih jemljemo za samoumevno že v teh dneh. Milijarde spletnih strani tam, pa vendar Google in Bing in podobno so sposobni najti stvari za nas tako. To se ne dogaja z linearno iskanje, iskanje po vseh možnih spletnih straneh. Facebook je lahko povedal, kdo vse so prijatelji ali prijatelji prijateljev, in da se lahko tudi na videz se opravi v trenutku te dni čeprav imajo na milijone uporabnikov. 

In tako se, kako smo dejansko reševanje težav na tem merilu bo na koncu zmanjšalo zamislim smo pogledal v tednu 0 in malo več danes. Ne bomo ponovno izvedli ta algoritem, pa opozarjajo tudi storil v tednu 0 Ta vaja , kjer smo vsi vstali, da na številko 1, in potem bomo imeli vse, samo-count, ki jih seznanjanje off, dodajanje številk skupaj, kot polovica banda sedel na vsaki ponovitvi. Torej smo šli od 500 študentov v 250-125 in tako naprej. Toda, kot smo rekli v ponedeljek, močan ideja ni je bil, da če bomo podvojili velikost tega problema in vsi otroci iz skupnosti ali ES 10 se je vrnil v sobo in se nam je pridružil, No, lahko bi verjetno računajo, da se celotno skupino sestavljenega samo z 1 veliko več ponovitev zanke, saj bi se le morda dvojno velikost ali ES 10 je pri malo več kot dvakrat večja od velikosti. In tako bi morali porabiti malo več časa, vendar pa ne bi bilo treba porabiti 400 ali 700 več korakov. 

Samo za barvanje to sliko na način, ki je malo manj abstraktno, naj ne bi vsi vstali. Ampak, če tisti, ki ste se odločili, da bi sedel v orkestru danes ne bi motilo stoje, pa poglejmo, če lahko ugotovimo, med vami, ki najvišja oseba s tem enako vrsto primerjalnih algoritem. Torej, če si sedel v orkestru, moje opravičilo, vendar korak 1, stand up; 2. korak, par off s kom si v bližini, ugotoviti, kdo je višji, in se usedi, če so krajši. Nato ponovite. [Učenci godrnjajo] 

Ok. Ok. Eden od njih je zapustil položaj. Kako ti je ime? >> Andrew. 

Andrew, ste najvišja oseba v oddelku orkestra danes. 

Čestitamo. [Ploskanje in navijanje] Ok. Imajo sedež. Tako smo ugotovili, Andrew. Ampak kako dolgo bi me upoštevati, na primer, da je bil Andrew V tem orkestru oddelku 50 + ali tako ljudi? Lahko bi vzel dokaj preprost pristop in začeli tukaj. In sem 2 ljudi je vstal in sem jih primerjajo, in potem sem rekel, da kdor je nekoliko krajša, "Ok, sedite," in bom, da se spomnimo, kdo je višja je bila oseba. Potem pa ponavljam, ponavljam, ponavljam, jaz pa visijo na najvišjem osebe dokler ne najdem nekoga, nekoliko višji od njih, na kateri točki nekoliko krajša oseba je nato sedel. Vendar je v tem algoritmu v tem oddelku orkester, če obstaja n od tebe, koliko korakov je, da algoritem bo trajalo? >> [Študent] N. 

To se dogaja, da se n, prav, saj v najslabšem primeru, če se tako izrazim, najvišja oseba, ki je zadnja oseba, ki sem dobil, da samo z naključnim nesrečo. Torej, v najslabšem primeru, je čas delovanja tega algoritem linearna, to je n pri čemer je n skupno število ljudi v prostoru, velikost problema. Kaj je to algoritem? Dejstvo, da ste vsi vstali in potem spet pol ti sedel, polovica vas sedel, pol ti sedel. Koliko korakov, da bi morali sprejeti, če obstaja n izmed vas? [Študent] N log n. >> To bi bilo še slabše. Prijavite n. 

Tako se prijavite n, tudi če se ne spomnite, kaj je logaritem, za zdaj samo hvaležni, da gre nekako na to prepolovitev in prepolovitev in prepolovili. Ni nujno, da je faktor 2. To je lahko faktor 3. Ampak to je to ponavljanje iste vrste faktor, tako da je velikost problema se začne tukaj potem pa takoj gre tukaj, potem je tukaj, potem je tukaj, potem tukaj. Nisi majhnimi ugrizi iz problema, ste res sekanje stran na njej z veliko potezo vsakič. Tako smo imeli 50 ljudi, nato 25, nato 12 ½ ali 13 ljudi, stoji, nato 6 ½ in tako naprej, dokler na koncu je ostal samo Andrew položaju. Torej bomo za klic, da je dnevnik n, in si lahko predstavljate tako, kot sledi. Spomnimo to sliko tukaj, kjer linearni algoritem je kot rdečo črto tam, rumena linija je štetje z algoritmom 2s, ki smo jo uporabili za štetje študente v preteklosti, danes pa sveti gral bo ostala ta zelena črta če, če bomo podvojili število ljudi v orkestru oddelku ali pa je dejal, hudiča, imejmo vse v celotnem prostoru stand up, ni tako velik posel ker smo podvojila, koliko ljudi je tukaj, 1 več ponovitev, ni problem. 

Ugotovili smo, Andrew ali tisti, ki se zgodi, da bo višji od Andreja V medetaži ali na balkonu. Torej, to preprosto idejo, da se je toliko za odobrene v telefonskem imeniku, zavedati, da obstaja toliko različnih krajev, kjer ga lahko uporabljajo. Samo, da slap nekaj žargonu - pravzaprav namesto žargonu prvič, pustite me, da te slike tukaj. Zdaj smo se pogovarjali o n in n / 2 in se prijavite n, vendar se gotovo lahko prišli do, kot bomo tekom semestra, druga vrsta matematičnih formul za opis tega splošnega pojma časa vožnje. To so izven konteksta, za zdaj, ker bomo videli kmalu algoritmi, ki jih dejansko predstavljajo. 

Opazil sem linearna linija n je premica, je pravzaprav zelo nizka kaže zdaj. To je neke vrste optično iluzijo, da smo samo v spremeniti tisto, kar os x predstavlja in os y, in lahko naredimo ravno črto točko v katerokoli smer želimo. A razlog, da je tako na videz ravno zdaj zato, ker smo potrebovali, da naredite prostor na grafu za veliko počasneje teče čas. Za zdaj vemo, da je nekaj zelo slabih algoritmi v življenju, nekateri, ki ne sprejmejo ukrepov n ali, še bolje, da se prijavite n ukrepe, vendar več. Torej nad črto n tu na dnu obvestila obstaja n-krat log n, in bomo videli, kaj to pomeni, prej ali slej. Predvsem, da je n kvadrat, in še nismo videli nobenega n kvadrat algoritme, vendar pa smo kmalu. In to zgleda res slabo. Tukaj je 2 do n, kar eksponentno, ki se počuti še slabše. In vendar, zanimivo, potem je n kubikov, ki bi, če ste nekako mislijo za naprej, če vrste math od 2 do n dejansko postane precej naravnost, precej višje od n kubikov, če pogledaš na osi dovolj daleč ven. Torej, opazil zdaj te osi je samovoljno 2-10 na x osi. 

In kaj to pomeni? To pomeni, da ljudje 2 do 10 ljudi v sobi. To je vse, kar pomeni x: velikost problema, ne glede na kontekst. In navpične osi zdaj je število sekund ali številu korakov - nekateri enota časa. Toda opazil, da je 0-60 in 0-10. Ampak, če bomo vrsta zoom out, kot si morda v Excelu ali kakem Charting programske opreme, in gremo do 200.000, opazil, da nekaj takega kot 2 do n bo povsem preplavijo tekočih čase n kvadrat, n kubikov, n log n - vse, kar smo govorili doslej. In še ulov je, ko začnete govoriti o stvareh, kot so Facebook kje ste mnogo, mnogo, mnogo ljudi, med seboj povezane, ste n ljudi, lahko vsak od njih pa ima toliko kot prijatelja n če so vsi nekako kolega-kolega na svetu, no, to je že n-krat n, da je n kvadrat možne prijateljstva, vsaj v 1 smer, n kvadratnih možnih prijateljstva. Tako, da že kaže, da išče socialni graf Facebook, če se tako izrazim, Lahko začnete, izražena v teh vrstah formul. 

Vrnili se bomo in to veliko bolj konkreten, ampak za zdaj je cilj v naslednjih nekaj tednih se dogaja, da se prepričajte, da ne bo šel o izvajanju algoritmov ali kode V ta namen se ob toliko časa, kot nekaj takega. Ampak zanimivo pri računalništvu, če boste še naprej na tem področju ob razrede, kot CS121 CS124,, ki sta teorija tečaji, je, da so dejansko nekaj problemov, ki obstajajo na tem svetu da je bistveno, kolikor vemo, ni mogoče rešiti hitreje kot najslabši od teh grafov dejansko kaže. Torej je veliko odprtih vprašanj na tem svetu, naj storijo veliko bolje kot ljudje, imajo doslej. 

Torej začnimo s tem pa na primer. Videli smo, Sean spopad s tem na kamero, vse preveč nerodno na video. Ampak dejstvo pa je bilo, ko je bil Sean nalogo pri iskanju na krovu, kot je ta številka 7, spomnim, da sem rekel, da "je nekje v ozadju teh kosov papirja ali bele vrata "Številka 7 Sean. Našli za nas." In bilo je čudovito nerodno gledati ker je bil res borila s tem problemom. Toda realnost je Sean naredil kot kdorkoli v sobi, bi lahko storili. On je malo več kot tipičen oseba lahko imela, vendar je domneval, da je bilo nekaj trik, da bi ta problem, je domneval, da mu nekaj manjka. In to ni pomagalo, da je na stotine oči so bile ob določitvi nanj. 

Ampak dejstvo pa je, če je vhodni problema je kup naključnih števil in ste se morali najti takšno številko 1, Največ kar lahko naredite, je linearna iskanje. Začnite na levi strani, nato v desno, ali začeti na desni, premakni v levo. Nazaj, bi morali razmišljati, "Sean, zakaj nisi začeti z drugega konca?" No lahko, 7 so prav tako lahko bil tu naključno, vendar sem namenoma dal tam, ker sem mislil, da ne bo začel konec. Tako nekako manipulira stanje, vendar pa ga Naključje 7, so lahko kjerkoli že. Tako se začne na desnem koncu bi lahko bilo bolje, potem, kaj pa, če v naslednjem letu sem premakniti 7 drugje? To ni popolnoma novo rešitev problema - začenši z 1 ali drugega konca - ko ste saj nima drugih predpostavk. Torej, Sean začeli iskati skozi številke in reče: "5. To ni tukaj." Šel sem in videl 19, nato pa je obstal za približno 20 sekund, Nato je odprl to za 13, nato pa je postalo jasno, da se ne zdi, da je vzorec tukaj. Ni bilo 1, 2, 3, 4 ali podobno. Ni bilo razlike v številu, ki ne pomagajo. In tudi dejstvo, da sem te poceni koščkov papirja, da bi prikrili številke je pravzaprav namerno, ker če sem odstranil vse te koščke papirja, večina od nas, Sean vključene, bi verjetno pogledal nekako mikroskopom na tablo in rekel: »Oh, 7 je očitno tam." Uspelo nam je takoj. 

In morda, da je način, kako se človeški možgani delujejo do neke mere, ampak v resnici, oči ali um je bil verjetno posnemanje številke od desne proti levi, od leve proti desni, srednji ven - nekaj, kar se je dogajalo fiziološko tako, da se mu je zdelo, kot da je v trenutku dogaja, vendar so možnosti, čeprav je bilo interno nekakšen metodologije za ugotavljanje 7. In res, zdaj, ko govorimo o poljih in podatkovnih struktur in spomin notranjosti računalnika, lahko edina stvar, ki smo jo tudi ljudje je pogled na posameznih lokacijah pomnilnika 1 naenkrat. 

Tako lahko vsak drugi lokaciji, kot tudi pokriti z nekaj listek ker ne moremo videti nekako. To lahko storimo samo 1 stvar naenkrat. Torej v tem primeru, v primeru, Sean, smo šli tu in potem smo šli tu in potem smo šli tukaj, tukaj, tukaj, tukaj, sem pameten, do konca leta in kar nekako preskočil tole samovoljno in ugotovil, 7 tam. Ta ni bil posebno posebnega. Tudi ta je bil v okvari. Vendar pa je končno našel 7. Ampak zdaj je takeaway res je, da je največ, kar lahko storite, ko noben podatek razen naključno razvrščeni številk je, da začnete z leve ali začnite z desne. Ali vraga, lahko naključno odprl vrata, vendar je tudi kaj potem to pomeni, da je naključno? No, jaz se moramo nekako formalizirati, kaj to pomeni, da sem začel, potem pa tukaj, potem kliknite tukaj. Sean naredil veliko, in to je samo zabavno gledati. Kaj pa, če namesto tega smo spremenili je problem malo in bruhati letošnji Seana, če bo? Bi kdo lahko udobno prihaja na oder in reševanje nekoliko drugačen problem in se pojavljajo na kamero? 

Pojdimo po orkestru, ker ste vi bili zelo vpleteni že danes. Kaj pa v roza, v klobuku? Pridi dol. Kako ti je ime? >> Alex. >> Alex. Ok. Tako bo Alex bo letošnji Sean in bodo v naslednjih nekaj letih vredno CS50 predavanj. Alex, lepo da sva se spoznala. >> Me veseli preveč. Izziv pri roki za vas je, da imate to nekoliko lažje v tem, da vam govorim enake številke so tu, vendar so zdaj razvrščeni. Torej, zdaj vaš cilj je najti številke 7. In dejansko bi morali res to - Ti si vrste varanje, kot računalnik ne bi, ga je videti, kaj je bilo število trenutek nazaj. S kredo to dejansko ne bo pomagalo vse to veliko, ampak kaj je pretvarjal, da ne veš, kaj je izvirna matrika je. Vse, kar vem zdaj, je, da imate niz številk, razvrščenih da bi lahko razlike med njimi, in vaš cilj je najti številke 7. Kako bi vi, razumen človek, iti o iskanju številko 7? 

Pojdi od nizkih do visokih? >> Redu. Pojdi nizka do visoka. In jih ne odtrgate. Naj jih samo dvigne, da bomo lahko znova uporabi. V redu, torej 1. Počakaj. Preden nadaljujem, da je 1, očitno napačna. Torej, kaj se dogaja po glavi potem? Kaj je vaš naslednji korak? Naslednji 1. >> Redu. Naslednji 1. Dobro. 3, tako napačna. Kaj je vaš naslednji korak? Naprej dogaja. >> Redu. Naprej dogaja. 5. Torej naprej dogaja, in mi izročil to za zanamce. 7. >> Odlično. Zelo dobro. Najdeno številko 7. [Aplavz] Tako, da je bila dobra, ampak tudi Sean našli številko 7. In menim, da niste res izkoristiti to dodatno informacijo, to je, da so razporejene te številke. Tako smo lahko še boljši? Vse predloge tukaj? Ja, nazaj. [Študent] Binary iskanje. >> Jaz nimam pojma, kaj je binarno iskanje. 

[Študent] Začnite na sredini. >> Začnite na sredini. Ok. Da vidimo, če lahko pridemo tja. Torej, če bi namesto vas povedali začetek od sredine, pojdi naprej in odprla vrata na sredini. Tukaj je 8 od njih, tako da boste morali izbrati tisto, samovoljno rahlo v levo ali v desno. Ok. 7! [Aplavz] Zelo lepo. V redu, ampak ko smo se dogaja s tem? Recimo samo, da bi prekinil vez si je tukaj začelo saj bi to lahko enako zgodilo tudi. Samo da veste, da se je zgodilo 7 je bil tam. Torej, to je 13. Torej, če si jih sortirati in smo šele začeli v sredini, kakšna bi bila najboljša naslednja poteza bila? Pojdi levo. In tukaj pride na primer telefonski imenik znova. Če 13 je tukaj in vemo, da je seznam urejen, Nato vse te koščke papirja, so nezanimive za nas zdaj saj že vemo, da mora biti 7 na levo če so te številke razporejene in smo ugotovili 13. 

Torej, kaj je vaš naslednji korak tukaj? >> Pojdi v levo. >> Dobro, dobro. Torej pojdi na levo, in - počakajte, hej, hej, hej. To je goljufanje. Torej si našel 7, ampak kaj je algoritem sva se uporablja? Začnite na sredini. Dobro >>. Torej, kaj je logično nadaljevanje te iste ideje? Oh, samo to. >> Točno tako. >> Tako sem začel tukaj. Dobro >>. Torej, zdaj smo šli malo na levo znova. To je 3. Vendar je zanimivo takeaway zdaj Kateri vam ni treba skrbeti? Ti 2. Te >> 2. Torej, zdaj je to ena lahko oditi, lahko ta izgine. Sedaj je problem, da je bila 8 je bila velikost 4 je zdaj velikost 2. Dobili smo zelo blizu. Še enkrat, pojdite na sredini teh 2 elementov. 

Ok. Torej, to je nekako žalostno, da sedaj smo vedno tekoč zapustil, ker smo zaokroževanje navzdol. Ampak to je v redu, ker zdaj smo vrgli stran to in vse drugo, nam je zapustil le 7. Naj dajo aplavz. Našli smo 7 znova. [Aplavz] Ok. Seveda. Drži se za samo še 1 sekundo. Čeprav ta proces Naslednja vrsta je trajalo malo dlje, kot smo menili, da bi, odkrito povedano, vaš prvi instinkt je najboljši, kajne? Našli smo 7 trenutku. Vendar bi Ugotovili smo 7 hitrejši, ne glede na to, kaj je v tem primeru v primerjavi s tem 1 ker če so številke Vse je že urejeno, tako kot strani v telefonskem imeniku, lahko dejansko sesekljajte polovico problema spet in spet in spet. In to ni čisto tako enostavno, da bi se to v samo 8 številk za razliko od 1.000 strani imenika, kjer ste res videli vidno, vendar v tem primeru, ko Sean tukaj iskal 7, koliko korakov v najslabšem primeru bi ga odpeljala? >> [Študent] 7. 7 v najslabšem primeru. No, v najslabšem primeru pa 7, če obstaja 8 vrata tukaj. To bi mu vzeti 8 korakov. 

Torej, če je n vrata, je morda treba Seana pred nekaj leti n korake. Zdaj, v vašem primeru, Alex, glede na to, da so razporejene te številke - in bomo lahko te vrste sklepajo, od koder smo bili doslej v tej zgodbi - kaj teče čas bolj inteligenten algoritem Alex od začnite na sredini in nato ponavlja? [Študent] 3. >> Tako se dogaja, da je 3, v grobem, če greš 8-4 na 2 do 1. Torej, 3 korakih ali, bolj splošno, da je log n znova. Vsak čas si prepolovitev in prepolovitev in prepolovitev in prepolovili, To je izraz te ideje log n. In tako, da so se ti samo 3 korake in sicer je to storila ko smo odprli vrata prepolovitev in prepolovili, ker bi to bilo nekaj Sean 7 ali 8 korakov. Torej, hvala, ker ste z nami v tem letu. >> Hvala. Veselilo. Hvala Alex. Podobno >>. [Aplavz] 

Kaj pa pravi posledice tega? Zdaj pa si predstavljajte, da to ni 8 vrati, ki, odkrito povedano, bi vsi našli nekaj 8 zadaj vrata zelo hitro, tako da bi raztrgal na koščke papirja in se dogaja z našimi instinkti. Kaj pa, če je to milijon vrata? Kaj, če je 4000000000 vrata? V primeru 4000000000 vrat, si zares želiš iti z algoritmom Alex, dvojiška iskalna kot bomo začeli kliče ali deli in vladaj, bolj na splošno, če boste obdržali prepolovitev in prepolovitev problem, ker če imate 4000000000 vrata, kolikokrat lahko sesekljamo 4000000000 na pol? [Študent] 32. >> Pravzaprav je 32. Delate lahko to izvajajo na papirju ali v tvoji glavi. Greš 4000000000-2000000000 to 1 milijardo pol milijarde evrov, na 250 milijonov evrov, pika, pika, pika. In če vam ven matematike, da boš res dobil 32, in da se dejansko nanaša na računalniške znanosti, saj smo ponavadi šteje v pristojnosti 2. 2 do 32 se zgodi, da bo 4 milijarde EUR. Torej je veliko pomena za te vrste pooblastil 2 v računalništvu. 

Toda kaj okoli 8 milijard? Koliko korakov je, da bo trajalo, če obstajajo 8000000000 vrata? [Študent] 33. Torej >> 33. Kaj pa, če je 16000000000 vrata? Koliko korakov je, da bo trajalo? [34] študent. >> 34. Lahko bi nekako nadaljevanje tega oglasa nauseam. Ampak to je močna stvar. Lahko uvedejo milijarde več vhodov na vašo težavo, vendar ni nič takega, si vzemite 1 dodaten grižljaj od njega, zato nam kaj podobnega binarno iskanje ali deli in vladaj, bolj na splošno. Ampak jaz sem malo goljufali, kajne? V primeru algoritma Alex je imela prednost pred Seana. Vedela je, da so bile razporejene te številke, vendar pa Alex ni bilo treba razvrstiti jih sama. I pred prišel k tabli in vrste poskrbel Narisal sem, da jih vse v razvrščeni redu, potem pa sem jih prekrit s papirjem. Ampak koliko dela si, da me vzameš? Če bi se začelo s temi številkami v neki navidezno naključnem vrstnem redu - v tem primeru ti enostavnejši številke od 1 do 8, tu - kako bomo šli o razvrščanju teh vrednot? Če bi bili človeški saj to nalogo, kakšen pristop bi intuitivno vzameš sortirajo cel kup številk? Te stvari so bile, kot je določeno koščke. Ja. 

[Študent] jaz bi vsako številko in ga primerjajte z vsako od in nadaljuj na levi strani. >> Dobro, dobro. Tako se vsako številko, jo primerjati z eno poleg nje, in potem samo premikati po seznamu, vrste rejiggering stvari, kot si. Torej, tukaj imamo priložnost za morda nekaj več ljudi, da se vključijo. Ali imamo 8 več prostovoljcev, ki bi radi, da pridejo gor? Malo manj pritiska, saj nisi edini. 1, 2, 3, 4, 5, 6, 7, 8. Pridi dol. Fantje se bodo številke od 1 do 8. Poglejmo, če tega ne more storiti za sortiranje Alex na zelo podoben način sem to storil vnaprej. 1, 2, 3, 4. Pojdi naprej in če bi, line up na odru med glasbeno stojalo in jaz tukaj v istem vrstnem redu kot diapozitiv na zaslonu. Uh-oh. Vas bomo delati v naslednjem primeru. Oh, čakaj, čakaj. Pa gremo. Počakaj. Naslednji primer je zdaj. Tukaj imaš. Število 8. Pridi gor. V redu. Razvrsti sami v skladu s tem. Potisnite samo malo na stran glasbe stojim tukaj. Torej imamo 4, 2, 6 - noter, tukaj, tukaj - 3. Ja. Ok. Ti pojdi tja. Ne, ostani tam. Ja, prav tam. Ne motim. Prav tam. Dobro, zelo dobro. Ok. Torej, zdaj pa jih razvrstite v naraščajočem vrstnem redu. 

Kako naj grem o tem? Algoritem, ki je bil predlagan pred nekaj trenutki je, zakaj ne bi preprosto primerjavo so ljudje, ki so nekako drug poleg drugega in nato popraviti vse napake, premika od leve proti desni. Torej, tukaj imamo 4 in 2, ki je očitno v okvari. Naj te zamenjati. Ok. Torej, zdaj bom za premikanje po vrsti. 4 in 6, nope. [Smeh] 6 in 8, kar dober. 8 in 1, dovolite mi, swap vas. V redu. Torej, 8 in 3, swap fantje. 8 in 7, dovolite mi, swap vas. 5 in 8, odlično. Dam razvrščen seznam. V redu. Torej ne povsem. Vendar je bolje, ker je večji številke - primerov v točki 8 - so nekako vrela iz leve na desno. Tako sem dobil 1 izmed njih v redu, vendar je občutek ta ni povsem rešila problem. 

Torej, kaj bi predlagali bomo naredili sedaj? >> [Študent] Naj to počne. Še naprej >> počne. In spoznali, spet smo postavili stvari, ki jih le ob vse ljudi nekako pametno se uredijo na podlagi te slike, zdaj pa moramo biti veliko bolj metodično. Moramo biti algoritemsko o tem, kot da smo pisanje kode - v tem primeru besedni psevdokod. Zato mi dovolite, da poskusite znova. To je delal zelo dobro. Ni ga rešiti. Ampak, ko dvomim, samo poskusite in poskusite znova. Torej, 2 in 4, ni več pomagati. 4 in 6. Ah! 6 in 1, kar je nekoliko bolje. 6 in 3, dobro. 6 in 7, 7 in 5, 7 in 8, dobro. In veste, sem lahko verjetno prezreti 8 sedaj, ker je na koncu seznama. Mogoče mi ne bo treba skrbeti nekdo mimo njega. Toda poglejmo, če je to varno predpostavko. Zdaj je seznam - prekleto - ni urejen. Poskusimo še enkrat. Torej, 2 in 4, 4 in 1, 4 in 3. 4 in 6 dobro. 6 in 5, dobro. 6, 7 in 8, dobro. Ampak obvestilo, sem lahko samo ustavi tukaj in zdaj ustaviti tu? [Študent] Da. >> Ja? Kaj pa, če je kdo od vas že številka 9 pa vse tja? To bi bilo urejeno. Dobro >>. To bi bilo prvič razporejene okoli. Dobro. Torej greva nazaj. Skoraj smo že tam. 1 in 2, 2 in 3, 3 in 4, 4 in 5, 5 in 6, 6 in 7, 7 in 8. 

Zdaj sem naredil, vendar pa se mi računalnik, ki lahko samo to, kar sem rekel, da ne, in moj edini spomin sedaj je, da sem v bistvu le naredil nekaj dela. Nekaj ​​se je spremenilo tukaj. Torej nisem tehnično potrdili vizualno ali algoritmično, da je ta seznam dejansko razporejene. Torej samo za dober ukrep, tako da je analni o tem, kaj je to storiti 1 več časa. Torej 1 in 2, 2 in 3, 3 in 4. In veste kaj? Samo za dober ukrep, bom spremljate na moji roki tokrat koliko zamenjave sem ti samo zato, da vem, koliko dela sem dejansko naredil. 3 in 4, 4 in 5, 5 in 6, 6 in 7, 7 in 8. Brez zamenjave. Torej, zdaj bi legitimno idiot, da to storijo še enkrat ker če sem ne dela prek tega prelaza na človeka, potem je jasno, da se bo to spet zgodilo, če nobena od njih je nekako naključno adversarially se gibljejo. Sedaj lahko neham. Zdaj pa vprašati, koliko dela je to dejansko me je vzel? Koliko korakov pa to trajalo? N >> kvadrat. Ja, tako n kvadrat. Kje ste dobili n kvadrat iz? Moraš preveriti vsako cilindrov - Tu je n število, in boste morali preveriti vsako številko z drugimi n številk. Dobro. >> Torej je n kvadrat. Dobro >>. 

Tako se zdi, kot bi to bilo zelo dobro n kvadrat, kajne? Tam je n od teh fantov, 8, posebej v tem primeru, ampak vsakič, ko sem šel skozi ta seznam, sem primerjavo prvo osebo, proti drugi, drugega proti tretji spet in spet in spet, in ko sem prišel do konca, kaj sem naredil? Sem ga uredil. Torej, če se sploh to razlago, imamo n ljudi in delam, seveda, 8 korakov, n korakih, vsakič, ko grem skozi ta algoritem. Toda koliko krat v najslabšem primeru moram iti skozi ta seznam ljudi? [Študent] N-krat. Verjetno >> n, prav, saj v najslabšem primeru, kar je verjetno najslabši primer razporeditev teh fantov od zaslužiti-go? Če jih popolnoma obrnil vrstni red Verjetno zato, ker samo mentalno, let's - Kako ti je ime? >> Bowen. Bowen. Ok. Torej Bowen, pridi sem za trenutek. 

Recimo, da je Bowen je tukaj na začetku algoritma, in ne vem, kaj vsi ostali, ampak Bowen tukaj, glede na to algoritem - in če želite samo sprehod z mano - se bo do balona, ​​kot je to storil prvič okoli, vse do konca. Recimo, da je oseba, ki poleg Bowen je bila številka 7. Moram iti nazaj in dobil številko 7, kar pomeni, moram iti vso pot nazaj. Zdaj moram imeti to isto sprehod z osebo, ki je številka 7. Toda kaj, če pa je bila številka 6 zraven njega, pa tudi? Potem sem moral iti nazaj in dobil 6. Torej, še enkrat, na vsaki ponovitvi te zanke govorim za vsakega od n ljudi, in bi mi morali n teh sprehodih, da poskrbite, da sem vleče vsi elementi največjih nazaj in nazaj in nazaj do samega konca seznama. Torej n stvari n-krat je le n-krat n ali n kvadrat. 

Torej, tukaj že imamo algoritem, ki je ni več n, ki je ni več log n, je dejansko slabše kot karkoli smo že naredili prej. Torej, Alex nekako imam srečo, da sem naredil vse delo očitno spredaj za njo, vse drago delo, tako da lahko ona uživa v tem binarnega iskalnega algoritma, ki je log n. Ampak to je v skladu s temo v ponedeljek. Dali smo malo več prostora, smo uporabili več bitov, da bi pospešila svoj delovni čas. Toliko kot da je ta kompromis med časom in prostorom, obstaja tudi samo se kompromisi med porabljen čas do sprednje vrste so stvari pripravljene, da gredo in dejansko izvedbo algoritma, kot so iskanje. Poskusimo še enega. Če vidva ne bi motilo, samo hitro preurejanjem sami, da bi ustrezala ponovno poskusimo nekaj malce drugačen, če to ni tako preprosto kot le popraviti vse napake, parno, ki je zelo intuitiven. Naj se namesto tega malo bolj premišljeno in to. Ta Tudi jaz bi predlagal, je verjetno precej intuitivna. 

Naj izberite najmanjšo osebo s seznama znova in znova. Torej, gremo. 4, ste najmanjša oseba, ki sem torej videl doslej, Tako bom duševno zapomniti, da jih samo kaže na vas za zdaj. 2. Oh! Pozabite številko 4. Pravkar sem ugotovila, da je nov najmanjši element na tem seznamu. Grem na vrsto zapomniti. 6, 8. Oh! 1. Nasvidenje. Torej, zdaj bom zapomniti številko 1. Vemo, da 1 je najmanjši, ampak sem računalnik. Kaj pa, če je 0? Kaj pa, če je -1? Moram naprej. Torej, 3, 7, 5, nope. Ok. Torej, številka 1 je najmanjša. Naj vas izberite iz seznama - Bomo iti po tej poti - in si dal samovoljno na začetku seznama. Počakaj malo. Nekako sem goljufal. Če ti fantje sestavljati seznam 8 oseb, ampak z matriko, 8 kosi strnjenega pomnilnika - Imate kaj proti korak nazaj za trenutek? Tam je dejansko ni prostora za vas tukaj. Torej, kako bomo naredili prostor - Kako ti je ime? >> Sammy. >> Sammy. Kako naredimo prostor za Sammyja? 

Gremo na n, ki so pred mano. >> Redu. Tako smo lahko premikate n ljudi, ki so pred njim, tako da, če vi želite, da 1 namerno, dramatičen korak v levo. Vsi so naredili, da je v sozvočju, ampak nazadnje, ko sem napisal nekaj kode, ne moreš nekako premakniti veliko stvari naenkrat. Lahko bi to naredil v zanko, ki se gibljejo vse enkrat naenkrat. Torej, če vi ne bi motilo, korak nazaj na desno, in Sammy, če bi lahko korak nazaj, saj je še vedno ni prostora za vas, zdaj pa to. Kje je Sammy pred nekaj trenutki? Prav tam. Torej je razlika obstaja. Torej si lahko premaknete v mestu Sammy. Zdaj naslednja oseba in zdaj naslednjo osebo, ki je zdaj naslednja oseba. Zdaj imamo prostor za Sammyja. Sedaj, nekdo iz občinstva - to je bilo dobro, da je bila pravilna, se mu je zdelo malo časa - kaj hitreje? Ja. [Študent] nov niz? >> Kaj je to? >> [Študent] nov niz? >> Dobro, dobro. 

Torej, v skladu s to temo le s kompromisi, zakaj ne bi sem narediti nov niz  in potem bo Sammy je kopanje v prostoru pred temi ljudmi, na primer, in bomo lahko šele začetek polnjenja nov niz v celoti. To bi bilo preveč dela. Ampak me ne zanima porabi več prostora danes. Kaj je drugačen pristop? [Študent] menjavo. >> Redu. Lahko bi samo zamenjali teh 2 guys. Kako ti je ime? Mario. >> Mario. Torej Mario, da si zdaj tu. Sammy, lahko nazaj gor za trenutek? Mario je bil tukaj. Nimamo prostora za tabo, tako da če ne bi imel nič proti, če bo Sammy je, bomo napisali Sammy tukaj in zdaj bi lahko dejali, da je bila menjava delovanje Sammy je veliko hitreje. To smo storili, da bi zamenjali 1 delovanje te ljudi, ali pa 2, da bi zamenjali te fante, vendar nismo naredili 1, 2, 3, 4, tako da se počuti bolje. Počakaj malo. Nekako je problem slabše, ker številka 4 je nekako blizu začetka. Sedaj številka 4 je malo bližje, da v ta namen, vendar nisem vedela, ali zanima. Torej, to je samo slaba sreča, da je številka 4 je malce dlje od svojega namenjeno mesto. Torej, kaj je zdaj to ponovi algoritem. 

Če povzamem, dokler ta zgodba je bila vse, kar si je sprehod skozi seznam išče najmanjše oštevilčeno osebe. Torej, zdaj gremo še enkrat. Mi ne bo treba skrbeti, Sammy več. Lahko samo pojdi tukaj. Oh! Številka 2. To je zelo majhno število. 6, 8, 4, 3, 7, 5. Dobro, dobro. In na srečo, naključje, mi ni treba premakniti - >> Willie. Willie, ker je v svojem pravem mestu zdaj. Naredimo to še enkrat in prezreti teh 2 guys. 6. To je zelo majhno število. Oh! 8 je zagotovo večja. 4. Osredotočimo se na 4. Oh! 3 je še boljši. 7 in 5. Torej, kaj bova zdaj s - >> Roger. >> Roger? Naj ga zamenjali s številko 6. Torej, če 6 in 3 bi radi zamenjali, smo zdaj nekako prišel srečen v tem 6 je bližje, če bi bila tam, ampak to je samo naključje tukaj. Torej, kaj je zdaj kliknite tukaj. 8 je zelo majhno število. Oh! 4 je manjša. 6, 7, 5. Kaj bomo pa zdaj? >> Menjavo. >> Točno tako. Torej, zdaj naredimo to vrsto hitreje. 8, 6, 7, 5. Kje 5 iti? Dobro. Ok. 6, 7, 8. 6 dobi, da ostanejo tam, kjer je. Kako ti je ime? >> Rosalie. Rosalie dobi prenočiti, kje je. 7 gets - Pa poglejmo. 7, 8. Ok. Torej 7 postane prenočiti, kje je. Kako ti je ime? >> Amna. >> Amna. 

Torej Amna dobi prenočiti, kje je, in številka 8 je že, če bi moral biti zdaj. Dobro, dobro. Počutim se, kot da smo samo ustvariti delo za nas tukaj, čeprav. Kaj je končno čas delovanja tega algoritma? Če mislimo, da o teh ljudeh ne kot 8, vendar kot n? >> To je n. To je n ukrepe, vendar smo kontrolo vsak čas. Ok. N a ste preverjanje vsak čas? V redu, če pa je n ukrepe, ne bi mi bilo, da vas lahko razvrstite po pravkar dogaja 1, 2, 3, 4? Oh! Ok, to je velika razlika. Torej n kvadrat, zakaj? Kaj se v resnici dogaja? Tukaj je n ljudi na tem seznamu, vendar da bi našli najmanjšo osebo na seznamu V najslabšem primeru, koliko korakov moram sprejeti? N. >> 

N, prav, saj v najslabšem primeru, številka 1 je vso pot tja, tako da sem moral iti ponj ali ona. In potem, ko sem končno spoznali 1 je bil najmanjši, potem je zelo hitro, da jih swap. Ampak zdaj moram začeti od začetka in si za koga? Naslednji Najmanjše oseba, ki je 2. Če je v najslabšem primeru znaša 2? Oh, moj bog. To je vse tako sem na koncu. Torej, zdaj sem pravkar naredil še n korake, še n korakih. In če imamo n ljudi in v najslabšem primeru najmanjša oseba n korakov, To je še n-krat n, in tako smo spet bili n kvadrat. To se ne počuti dobro. In v resnici, tudi v najboljšem primeru - Predvidevam, da začnete razporejene - koliko korakov je potrebnih, da sem z uporabo tega algoritem za razvrščanje teh n ljudi? N kvadrat. >> Slišal sem n kvadrat. Zakaj n kvadrat? Ker imate še vedno preveriti vsak čas. >> Ja. In jih morate zamenjati. >> Čeprav smo ljudje nekako vsemogočni v smislu, vizualno, da bomo lahko kar nekako vidim, da je urejen tako, Računalnik ni tako pameten. To se dogaja, da si tukaj in tukaj in tukaj, če pa kaj je iskal je najmanjši element, ste samo vem, da ste našli najmanjši element, do katerega bistvo? Ko ste na koncu. Toda na tej točki ste našli le trenutno najmanjši element. Saj ni nujno, veš kaj o stanju sveta. Torej boste morali spet in spet in spet. 

Torej, tokrat sem res videti neumno, ker sem kontrolo, ok, 2, si je najmanjša, ampak jaz ne vem, da v celoti še ni. 3, 4, 5, 6, 7, 8. Dobro, dobro. 2 je res najmanjši. Zdaj pa je bil naslednji najmanjši. Ok. 3, ste trenutno najmanjši. Pa poglejmo. 4, 5, 6, 7, 8. Ok, imaš srečo še enkrat. 3 je bil res na pravem mestu. Vendar bom vztrajati početje to znova in znova in znova. Kako lahko to storimo vedno tako malo bolje? Namesto da bi ljudje mehurček gor Pairwise od najmanjšega do največjega in namesto da bi šel naprej in nazaj po seznamu izberete ta pa najmanjši osebo, Zakaj ne bi namesto vstaviti te ljudi v nov korak za korakom seznama? Poskusimo tole. Zdaj pa me poklical te vrste stvar vstavljanja. Torej, tukaj smo tukaj. Številka 1. Ne skrbi nikomur na tem seznamu. Moj cilj sedaj je, da se številka 1 na začetku razvrščeni seznama. In jaz bom predlagala, ker imam samo 8 kose pomnilnika, samovoljno zdaj sem zid med mojimi naj nesortiranih seznamu in je razvrščen vsakdo, ki je za sabo bom trdijo. Torej, zdaj imamo številko 1. Želim, da ga vstavite v mojem razvrščenih seznam, tako da bom samo, da se premaknete svoj zid tukaj, zdaj pa trdijo, ta seznam je urejen, je ta seznam nerazvrščeno - vsaj kolikor jaz vem. Ne vidim vse številke naenkrat. 

Zdaj sem se zgodi, da naletijo na številne 2. Kaj naj naredim z njim? Sem ti vstavite zdaj na seznamu razvrščeni. Toda opazil, kako enostavno je to. Sem moral pogledati. Številka 1 je tam. Oh, seveda 2 gre na strani številka 1. No, kaj naj naredim s 3? Sem ti vstavite v seznamu razvrščeni. Ampak to je bilo super enostavno. To je super enostavno, je to super lahka, to je super enostavno, super enostavno, super enostavno. In zdaj je vse razporejene za mano, in koliko korakov se je to trajalo? [Študenti] >> N. Torej je le n. Imeli smo srečo. Bilo je le n zakaj? >> [Študent] Ker je bil razvrščen seznam. Seznam je že urejeno. Torej imamo srečo. Ampak smo zasnovali algoritem, ki ta čas, da ramenskimi toliko sreče, da je najboljši scenarij, ki ga ne bi izgubljali časa po nepotrebnem. Tako imamo zdaj, kaj bomo poklicali mehurček vrste kjer se ljudje nekako balona do parne. Zdaj imamo izbiro vrste, kjer smo Istrgnuti najmanjšo osebo, znova in znova. In zdaj imamo nekakšno vstavljanja, kjer smo nekako proaktivno, da ljudi, kamor sodijo v vse bolj razvrščenih seznama. Če bi lahko, aplavz za te fante tukaj. [Aplavz] Vzemimo našo 5-minutni odmor tukaj. In ko se vrnemo, bomo razstrelili vse te algoritmov iz vode nekaj boljšega. V redu. Najlepša hvala. Lahko da so kot spominke. V redu. Mi smo nazaj. 

In če povzamem zelo hitro, smo te 3 različne pristope za sortiranje, bistvo, ki naj bi prišli do točke, ko nekdo kot Alex lahko poiščete seznam številk hitreje kot nekoga, kot je Sean lahko. In čeprav imamo tako preproste primere z 8 številk, bi lahko ekstrapolirajo z lahkoto do 8 spletnih strani, 8 milijard spletnih strani, ali 800000000 prijatelji na Facebooku. Tako lahko ti algoritmi zagotovo lestvico za tiste vrste vrednosti, in ideje so na koncu isti. Tako nekako mehurček je bil prvi, kjer smo nekako vrela največji osebo vse do pravice z zamenjavo ljudi Pairwise. Potem smo imeli kaj bomo poklicali izbiro vrste, kjer sem malo bolj premišljeno hranijo išče po seznamu, izberite najmanjše število znova in znova in znova, logična posledica je, da je seznam na koncu razvrščeni. Potem pa v tretjo, sem vstavil ljudi v njihovem ustreznem mestu in smo zelo izmišljene primer v tem, da je bil seznam že urejen, ampak to je bilo, da pošljete sporočilo, da je v primeru vstavljanja sortiraj je, lahko posreči. Če so številke že razporejene, to je samo še, da vas n korakov za potrditev toliko, ker neke izbire, da si malo bolj predor vizijo in ti nikoli ne zavedaš, da je ta seznam že urejeno. Torej, da vidimo neke mehurčke v akciji tukaj. V tem primeru, bomo kmalu videli navpične črte katerih višina predstavljajo številk, tako da bomo lahko nekako vizualiziramo sortiranje zgodilo. Manjša kot je bar, tem manjše je število, večja kot je bar, večja številka. 

In ga bomo igrali na tej privzeti hitrosti. To se dogaja, da se premaknete malo hitro za zdaj, vendar je rdeča, kaj se kaže tudi 2 bara se v primerjavi drug ob drugem. In če gledate pozorno, kaj se zgodi, je, da če so palice v okvari, se manjši gets preselila na levo, širšo 1 na desni, in potem naprej napreduje. Torej, če to počnemo znova in znova, da vidite, da je najmanjša palice se dogaja, da inching svojo pot na levo in največji palice dogaja, da inching svojo pot na desni. In res, smo začeli videti vzorcu, vso pot na desni strani tako kot smo videli, 8 in nato sčasoma 7 vpihavanjem do skrajnem koncu našega seznama ljudi. Torej, to se dogaja zelo hitro dobili malo dolgočasno, zato naj ustavi za trenutek. Naj spremembo hitrosti, da se veliko hitreje. Jaz ne spreminja algoritem, jaz sem samo izdelavo animacije zgodi hitreje. Še vedno bubble sort, enak algoritem, zdaj pa si lahko ogledate veliko hitreje kot naši ustno predstavitev da se največje elementi so dejansko vpihavanjem do vrha. 

Naj omenim, da so ti mali kvadratki na spodnjem levem in desnem spodnjem je le malo opomnike o tem, koliko primerjave delate. Ampak za zdaj, bomo lahko osredotočili na piramido, ki je dobiva obliko, in tam gre. Najmanjši element je na levi, največji na desni, in vse ostalo vmes. Zdaj pa namesto tega si oglejte vrste selekcijo. Grem, da gredo naprej in zadeti Stop. Bomo dobili nov naključni komplet palic. Izbor vrste, odpoklic, gre skozi seznam spet in spet in spet, skubljenje od najmanjšega elementa. Torej, tukaj je izbor sort. Videti je, da je manj dela, se dogaja zdaj, ker ne bomo primerjali parne vendar smo nekako cherry picking najmanjše elemente iz desne na levo. To je zelo malo časa, tako da je že dihotomija. Samo zato, ker algoritem je dejal, da n kvadrat časa, kot so vrsta mehurček in kot neke izbire tistih, ki so res najslabši teče čas. Na primer, v primeru, recimo, izbira vrste, Pravzaprav sem izberete najmanjšo osebo in dajanje mu tukaj potem to počnem še enkrat, potem pa to počnem še enkrat, vendar pa je prišlo do manjšega optimizacija Jaz bi lahko. 

Takoj, ko sem se preselil sem številka 1 - Sammy v tem primeru - Kaj pa moram storiti z njim potem? >> [Študent] Pustite ga. Pusti ga, kajne? Nič. Nisem je treba vedno govoriti Sammy še enkrat, ker če sem izbral najmanjši element in ga postavil tu, zakaj bi izgubljal čas bo konec mojega celotnega seznama? Na naslednji iteraciji mi dejansko premakniti samo za številko 2, samo številko 3. Torej, v resnici pa sem bil ne delam stvari, n n-krat. Opravljal sem n stvari, potem je n - 1 stvari, potem n - 2 stvari, potem n - 3 stvari, potem n - 4, pika, pika, pika. Imamo malo geometrijskem zaporedju, ki samo pomeni, dodajate postopoma do manjših številk. Ne n + n + n + n vendar n + 7 + 6 + 5 + 4 + 3 + 2 + 1. In kaj, da na splošno deluje se je, da - Grem pokvariti mojega sveta sem za trenutek - da se bo izšlo, da bi bilo kaj takega n (n - 1) / 2 če smo le nekakšen pogled na zadnji matematični knjigi, kjer imate vse Goljufaš listi Za formul. Če ste pravkar dodal nekaj n + n - 1 + n - 2, to tovarna jasno, da je nekaj takega. In če smo le nekako množijo iz tega, da je n kvadrat minus n / 2. Obdržal sem rekel n kvadrat, čeprav, in da je zato, ker sem bil nekako ob mentalno bližnjico ker v resnici, n kvadrat minus n deljeno z 2 je dejansko res, število korakov da algoritem kot neke izbire da če res šteje navzgor vse te primerjave, in vse malo zaseden delu smo bili početje. Ampak odkrito povedano, ko n dobi biti kot milijon ali milijarde, ki skrbi za vraga če delaš milijardo kvadrat minus milijard deljeno s 2? Milijarde kvadrat je ogromna številka. Lahko še eno milijardo off to z - n. To ni nič takega. Torej večji številke dobijo, manj pomembni so ti pogoji so nižje naročiti. Koga briga, če delimo z 2, če govorimo o quadrillions števila korakov? 

Torej na splošno, računalniški znanstveniki pogosto mečejo vse, ampak največji izraz, in smo kar nekako poenostaviti svet in rekel, da algoritem je približno n kvadrat korake. To je čas vožnje od algoritma. Torej bomo prišli nazaj na to čez nekaj trenutkov z nekaterimi konkretnimi primeri, vendar za zdaj, to je nekako intuitivno motivacije za tako poenostavlja naš svet in govori o najpomembnejših izrazov, ne pa dobili v vseh teh fancy formul. Tako, da je bil izbor sort in imamo malo sreče tam. Oglejmo si uredi po vstavitvi. Naj gredo naprej in začnemo 1, kot tudi. Zdaj opazite vzorec, ki se dogaja, je malo drugačna, in smo začeli s naključnih števil, če pa smo dejansko prešteti število korakov, v najslabšem primeru, Če je seznam začel povsem v pravem vrstnem redu, želimo le n ukrepe za uresničitev toliko. 

Ampak, če so bili dejansko nazaj seznam - na primer, v tem primeru - potem opazil, smo dejansko narediti veliko več dela v tej zadevi. Prav tako bi moral nekako občutek, da vam je všeč tale je malo težje delo , da bi dobili tiste manjše elemente na levi, in da je zato, ker smo dobili nesrečen. Seznam je bil pomotoma razvrščeni v obratnem vrstnem redu. V nasprotju z neke vstavljanja, če posnema, kar smo naredili z našimi ljudmi tukaj da se začne s razvrščene vse in nato začne, to je zelo dober algoritem, kajne? To je že v bistvu urejeno. Torej, kaj je poskušal povzeti, koliko časa te stvari jemljejo nam z uvedbo le nekaj žargona ali notacijo, ki je dejansko veliko enostavnejši kot fanciness nekako kaže. Ta stvar tukaj, ta velik O na zaslonu, kaj se bo računalniški znanstvenik splošno uporabo opisati najhujšo teče sodni čas algoritma. 

Še enkrat, po najslabšem primeru, to je popolnoma odvisno od konteksta. Kaj mislimo s najslabšem primeru popolnoma razlikuje glede na problem, govorimo o tem. Toda v primeru, sortiranja, kar je najslabši možen scenarij? Vse je nazaj, ker je samo občutek, kot da pomeni veliko dela za nas. Sem jotted dol nekaj algoritmov, ki smo jih videli doslej: linearno iskanje, binarno iskanje kot pri telefonskem imeniku ali koščke papirja, potem nekako bubble sort, izbira sort, in vključitev, kot smo lahko videli pri naših ljudeh, in nato še 1, ki je na koncu bo, da se imenuje zlivanjem. Torej, v linearnem iskanje v najslabšem primeru, koliko korakov je potrebnih, da bi našli številko 7 če je n vrata, s katerimi se srečujejo, kot so Sean? >> [Študent] N. N. Torej bomo napisali veliko Õ n. Grem, da izpolnite v nekaterih prazne. To je le mreža presledki. Toda v najboljšem primeru z linearnim iskanju lahko, 7 je bilo na samem začetku seznama, in bi lahko Sean začeli iskati na začetku seznama. Torej, če ste z uporabo linearne iskanje in samo preverjanje leve proti desni ali pa od desne proti levi - oni so enakovredne - v najboljšem primeru koliko korakov bi lahko linearno iskanje, kot algoritem Sean je, da? Samo 1 korak. 

Tako bom rekel, da je omega zapis. To je samo kapital omega. Omega je le seksi način rekel najboljšem primeru teče čas. Torej v najboljšem primeru teče čas je sam korak ali stalno število korakov - 1 v tem primeru - ampak v najslabšem primeru, veliki O, je dejansko n korakov. In tale tukaj, theta, mi pravzaprav ne gre iskati v tem trenutku. To ni pomembno za to posebno primer. Ampak zdaj poskusiva binarno iskanje. V najslabšem primeru z binarno iskanje, koliko korakov je bo trajalo, da bi našli številko 7 ali karkoli že iščemo? >> [Študent] Prijavi n. Še vedno se dogaja, da se log n, ker tako kot Alex dobil sreče ko smo res delali skozi problem metodično in ona ni našel številko 7 do zadnjega vratih je gledala, čeprav je v pravičnosti, je prišla do mečejo nekatere vrata na tej poti, binarno iskanje v najslabšem primeru ima zaporedno čas log n. In še enkrat, da se govori, da je to tako in osvajanje. Toda kaj je v najboljšem primeru? In Alex je dejansko prišlo, da je najboljši primer prav, ko je prišla na oder. Koliko korakov, da bi si v binarnem iskanju? >> [Študent] 1. 1, samo zato, ker je dobila srečo. Ampak to je v redu, ker se nanaša na omega najboljših scenarijev, Najboljši vnosi primeru, tudi če je samo naključna sreča. 

No, tudi to bomo le nekakšno slepo dopusta za zdaj. Kaj pa zdaj bubble sort? V najslabšem primeru z neke mehurčkov, vsi so v obratnem vrstnem redu, zato moramo storiti veliko mehurčki. Toda koliko korakov je, da bo trajalo v najslabšem primeru? >> [Študent] N kvadrat. To je n kvadrat, ker če mislite o tem, Če je seznam povsem nazaj - 8 je tukaj, 1 je tukaj - kot stvar začne mehurček, številka 8 se bo premaknil v to smer, na ta način, Na ta način, na ta način, ampak, če je številka 7 v najslabšem primeru? Tukaj je še vedno tam. Zato moramo to storiti znova in znova. In to je, če dobimo n korakih, potem n - 1 korakih, potem n - 2 korakih. In če se sprejme mojo besedo za to - da če jo pomnožimo nekako ven, to je približno n kvadrat na koncu še z nekaterimi drugimi pogoji, ki jih bomo samo za zdaj ne upoštevajo - nato pa v najslabšem primeru vrste mehurčkov n kvadrat, gor ali dol. Kaj pa najboljšem primeru z neke mehurček? Kaj je najboljši scenarij? Vse številke so že razporejene. In kaj je metodični sem, trik sem uporabil, zavedati, da sem storil nobenega dela in zato prenehati zgodaj? [Študent] Check it enkrat. Poglej >> enkrat. Ampak, kaj sem počel na poti? Bil sem sledenja, koliko zamenjav sem naredila. In spoznal sem, če sem ne štejemo nobenih zamenjav na prstih, potem pa sem naredil brez dela. Jaz zagotovo ne bi poskusil narediti nobenega dela spet, tako da sem lahko samo ustaviti. 

Torej v najboljšem primeru neke mehurčke, ko je seznam že urejen, kaj bi rekli oznako omega je najboljši primer teče čas? To je samo n. Moramo narediti nekaj dela, vendar smo le morali narediti v vrednosti 1 sprehod z dela. In tudi tu se bom, da zapustimo to del prazno. In zdaj izbor sort. Izbor vrste me je skubljenje najmanjšo osebo znova in znova. In kaj smo rekli teče čas je bil to? To je n kvadrat v najslabšem primeru. In na žalost, v najboljšem primeru se je tudi n kvadrat ker nimam neke vrste vsevednega Ob vsem svetu; Vem samo na popolno ponovitev, da sem res našel najmanjšo osebo. Torej, izbira neke vrste zanič v tem smislu, ampak glavo je, da je nekako intuitivno. To je zelo enostavno za kodiranje gor, ker vse, kar morate storiti, je napisati nekaj ugnezdena za zank, Značilno je, da gre skozi iščejo najmanjšega elementa in potem postavlja najmanjši element, kamor spada na koncu seznama. Torej tudi tukaj se bo kompromis. Čas, ki je potreben, da misliš, da se dejansko razvijajo in kaj je s pisanjem kode lahko zelo dobro vzame več časa, če želite boljše in hitrejše delovanje algoritma. 

Ampak, če ste res tako kot nekaj kode za hitro in umazano in kar nekako prevzeti neumna možno predstavo si lahko zamislite, ki bi lahko peljal nekaj minut kodo, vendar z velikih zbirk podatkov vaš algoritem lahko traja ure teči. In bi tudi jaz v šoli včasih te kompromise. To bi bilo 03:00, sem poskušal analizirati nekaj zelo velik nabor podatkov nanašajo na varnostne raziskave sem delal in je bil preživijo 5 minut poteg svoj program za analizo podatkov in zaspi ali preživijo 8 ur, da bi jo ravno prav, tako da deluje takoj in ne zaspi. In tako je tudi bilo nekako zavestne odločitve. Manj razvojni čas, več spanja. Če pogledam nazaj, se verjetno ne bi smela spodbujati, da ko je cilj tukaj je za višjo raven kakovosti kodeksa, ampak da tudi v realnem svetu je zelo razumen kompromis. Manj časa, manj zmogljivost ali obratno. Torej, tukaj smo končno dobili priložnost za pogovor o theta. Theta zapis je nekaj, računalniški znanstveniki lahko prinese v pogovoru ko veliki O in omega zgodi, da bo enako. Pravite, theta, da bo res poslali sporočilo, da je to nekako tesno povezani. Ne glede na to, ali je scenarij, dobro ali slabo, je to n kvadrat. Torej, to preprosto ni pomembno v teh zgodbah tukaj. Vstavitev vrsta je zadnja nas je zanimalo, kjer sem bil samo vstavljanje v vse na pravem mestu. V najboljšem primeru, kakšen je bil teče čas vstavitve vrste, kot smo ga videli tukaj? [Študent] najboljšem primeru? >> Najboljšem primeru. 

To je zato, ker n v najboljšem primeru vsak urejen, in Sammy in nihče drug Res je, da se premaknete na vse. Bili so že na svojem pravem mestu. Tako nekako vključitev v najboljšem primeru je v tem primeru n. Toda v najslabšem primeru pa nekako n kvadrat. Zakaj? Če moj seznam ljudi, je v obratnem vrstnem redu, Najprej sem začela s številko 8, ki sem ga vstavite ali jo v pravilnem položaju, kar je tukaj. Nekako sem prehod na strani. Ti fantje so nesortirani, on ali ona je urejeno. Ampak zdaj sem se zgodi, da ugotovite, kdo potem? >> [Študent] 7. 7 v najslabšem primeru, ker je to v obratnem vrstnem redu. 

Torej, tukaj je 7. Kje 7 pripada? Zagotovo je za mano. Ampak zdaj 7 dejansko pripada ne takoj za mano, ampak za številko 8, tako da sem moral reči: "Oprosti, številka 8, lahko prosim premaknite na ta način "Da bi naredili prostor za 7?" Zdaj sem srečati 6. "Oh, oprostite, številka 8 in številko 7, se lahko premaknete, da naredite prostor za 6?" Torej, z drugimi besedami, z neke vstavljanja, čeprav ne delam veliko gibanja, ljudi za menoj delaš veliko več dela in da ima nekoga stalo časa. To bo stalo računalnik časa. Torej, v primeru vrste vstavitve še vedno trpijo. Če začnete sešteva skupno število korakov, smo na koncu hitting grobo n kvadrat ker so ti ljudje morali narediti prostor za človeka, ki se vstavi nazaj v ta seznam. In tako se je v tem primeru theta je samo ne uporablja za posamezne zgodbe v roki. To je vse lepo in prav. Imamo teh 3 različne načine govorimo o času delovanja. Toda kaj to pravzaprav pomeni realno, če bi dejansko poskušali kodo gor algoritem? 

Naj predlagajo, da obstaja še boljši algoritem tam da sama nekaj kompromisov. Mi bomo imenovali z zlivanjem, in to je nekako to čarobno algoritma da tako deluje hitreje nekako, in to je tako preprosto, da izrazijo, vsaj v Psevdokoda. Izvajanje te vrste algoritmov za združevanje se bo, kot sledi. Ko ste glede n elementov - N, N številk ljudi, ne glede na - prva se je duševno zdravje ček. Če je n manj kot 2, združi nekako samo ustavi. Se vrne, če se tako izrazim. Zakaj bi se ustavil, če je n manj kot 2? >> [Neslišno študentski odziv] Prav. In spet, n ni število na seznamu, n je velikost seznama. Če je n manjši od 2, kar pomeni, da vaš seznam je bodisi 1, če ste seveda razporejene če je številka 1, ali 0, v tem primeru ni nič rešiti, zato moramo te vrste primerjavi z osnovnim. Če je seznam tako kratek, da obstaja samo nič storiti, dobesedno ne naredi ničesar. Vrni se. Sicer razvrstiti v levi polovici elementov, nato pa razvrstiti na desni polovici elementov, spojite 2 razvrščeni polovic. 

Ta vrsta izgleda kot majhen goljufija, s katerim vas prosim, kako razvrstiti elemente in ti si mi povedal, "Razvrščanje v levi polovici, razvrstiti na desni polovici." Jaz pa: "Vse je v redu. Kako razvrstiti levo polovico?" "Razvrščanje v levi polovici levi polovici, razvrstiti na desni polovici levi polovici, nato pa storil." Ti si nekako ciklično opredelitvi, kaj to pomeni za razvrščanje, vendar se izkaže, da je pravzaprav odlična v tej zadevi. To ni res, da ta začarani krog se nikoli ne konča ker ne konča, ko? >> [Študent] Ko dosežete 1 stvar. Ko pridete do 1 stvar. Torej, čeprav lahko začnete z 8 ljudi in rečem, "Razvrščanje levo polovico teh ljudi, Ti ljudje 4 ", potem rečem," Kako rešiti levo polovico? " "No, nekako od 2 ljudi tukaj." In potem si kot: "V redu, v redu." "Kako rešiti levo polovico teh ljudi?" "Samo to razvrstite 1 oseba tukaj." Kaj je sijajno odkritje zdaj? Moram razvrstiti 1 osebo. Končano. Nimam nobene poklicne dejavnosti. Ampak zdaj moram rešiti to osebo, vendar pa si samska oseba, nič. 

Torej magija očitno je v tem tretjem koraku: združiti razvrščeni polovic. Tako nekako združiti jemlje to briljantno vpogled, da če si zlomil velik problem navzdol 2 v manjše, enako velike težave in potem samo neke vrste lepilo manjše rešitve skupaj na koncu, Predlagam, da lahko naredimo še veliko, veliko bolje [prisluškovanje zvok] kakor koli vrste ali vstavitve izbor vrste. Sem bila dejansko ne upošteva, da se za pol ure, ampak jaz res ne vem, kaj se dogaja zunaj danes. [Whirring zvok] [smeh] Da vidimo, če lahko to vidimo z majhno pomočjo našega prijatelja Rob Bowden. Obstajata 2 velik korak v procesu vrste spajanja. Prvič, ves čas po delih seznam skodelic na polovici dokler ne bomo imeli kup seznamov s samo 1 skodelico v njih. Ne skrbite, če seznam vsebuje liho število in ne moreš narediti popolnoma čisti rez med njimi. Samo samovoljno izbirati, katere seznam vključiti dodatno skodelico noter Torej, kaj je razdeljen teh seznamov. Zdaj imamo 2 seznamov. Zdaj imamo 4 seznamov. Zdaj imamo 8 sezname z eno skodelico na vsakega seznama. Tako da je za 1. koraku. Za korak 2 smo ponovno združitev para seznamov s pomočjo algoritma za spajanje smo se naučili prej. Združitev 108 in 15 končamo s seznama 15, 108. Združitev 50 in 4 končamo s 4, 50. Združitev 8 in 42 smo na koncu z 8, 42. In združuje 23 in 16 smo na koncu z 16, 23. Zdaj so vsi naši seznami velikosti 2. Obvestilo, da je razvrščena vsaka od 4 seznamov, tako da lahko začnemo združuje parov seznamov znova. Združitev 15 in 108 ter 4 in 50 smo najprej vzeti 4, nato 15, nato 50, nato 108. Združitev 8, 42 in 16, 23 moramo najprej sprejeti 8, nato 16, nato 23, nato 42. Torej, zdaj imamo samo 2 seznamov velikosti 4, so razvrščeni od katerih vsaka. Zdaj smo združiti teh 2 seznamov. Najprej vzamemo 4, nato pa vzamemo 8, nato pa vzamemo 15 in 16 ter 23 in 42 ter 50 in 108. In končamo. Zdaj imamo urejen seznam. 

Rob je nekako izkoristiti nekaj, kar še nismo opravili. Predlagano je bilo, ampak mi dejansko ni naredil. On je bil početje nekaj fizično z bonboni, da predlaga je bil porabi nekaj sredstev poleg časa. >> [Študent] vesolje. >> To je bil prostor. Dejstvo, da je imel tovrstne bi na ravni mizi, kjer je imel prostor tukaj in prostor tukaj je dejansko kar pomeni, da je z uporabo dvakrat toliko prostora kot kateri koli od naših algoritmov doslej - vstavljanje sortiranje, bubble sort, ali izbira sort - vendar je bil to vplivno dodaten prostor na vrsto premakniti stvari naprej in nazaj pri čemer pa stvari v red. In čeprav se zdi, kot da imamo na seznamu razvrščene, da so se počutili, kot da se je nekaj časa. V resnici je šlo Rob je bil ravno ta algoritem. Sprva je problem velikosti n, ga razdelimo na levi polovici in desni pol. To je, ko se je preselil v skodelice. Potem je ponovil ta proces. On je razdeljena na 4 2 2 sklopov sem in tja. Potem je ponovil ta proces in razdeljen v 2 sklopa 2 1 za vsako od teh različnih lončkov. In to je, če briljantno pojavi priložnost. Na tej točki v zgodbo, Rob je 8 seznamov velikosti 1, vsi, ki so že bili razvrščeni. 

Torej, kaj ti je nadaljevati narediti? Pairwise vzel ta urejen seznam in to urejen seznam in jih združiti. Nato je vzel tole in jih združiti, potem je to eno in jih združila, potem je to ena in jih združiti. In potem, kaj je naredil potem? Nato je ponovno združil večje liste in nato ponovno združila večje liste. In če misliš o tem samo intuitivno, za zdaj, kaj je res počne? Bil je tako, da se težave na pol na pol, na pol, na pol , da bi dobili te super majhne seznamov. Potem je bil nekako združuje dvojno, dvo-, dvo-, dvojno. Tako je bil dvakrat delal toliko dela, kot smo videli doslej z vsem, kar vključuje deli in vladaj, vendar nič posebnega. Dvakrat toliko, da delo ni nič takega. To je samo stalno prisotna. In podobno kot naš aritmetični izraz prej, bom samo za prehod iz stalne dejavnike kot vedno 2. Koga briga? Če je 2-krat v milijardah 2, ki je še vedno veliko korakov. Torej ta korak združitev zdi, da je ključni vpogled. Sprehodimo se skozi to samo številčno prej - Oh, to je, da se ne še nadaljevala. Sprehodimo se skozi to samo številčno da bi dejansko videli, kako ta igra ven. To je večinoma le malo ubogega človeka animacije. Naj bo predlagala to. Čas teče vrsta spajanje - moramo samo način govori o tem. To ni matematika, to je le neke vrste kratkega način izražanja sebe. Torej T predstavlja čas in n predstavlja kaj? >> [Študent] Velikost od - 

[Malan] Obseg tega problema se je število ljudi. Torej sem trdil, da teče čas, da uredite n ljudi se bo 0 količina časa če je n manj kot 2, ker če imate 1 skodelico ali brez skodelice, nimaš nič za razvrščanje. Ampak na splošno, bom predlagal, da teče čas, da uredite n elementov se bo čas, potreben za razvrščanje v levi polovici plus desno polovico plus - kaj je to dodaten + n? >> [Študent] zlivanjem. [Malan] To je pravzaprav združitev, ker če imate n / 2 elementi tukaj in imate N / 2 elemente tukaj, koliko časa traja, da se ju združi? Tako kot Rob, morate oskubil tole tukaj, morda drobovja tukaj, Prebirati sem, drobovja sem, drobovja tukaj. Moraš se dotakniti vsakega od skodelic enkrat. In če obstaja 4 skodelice plus 4 skodelice, to je 8 skodelice ali, bolj splošno, 8 n skodelice. Tako lahko združujejo korak, ki ga predstavljajo kot n, in ki dobesedno pomeni, kolikokrat Rob fizično dotaknil ena od teh skodelic stiropora. Torej, kaj je zdaj to samovoljno primer. Če je 16 skodelic, kaj je čas delovanja razvrščanja, uporabljajo algoritem Rob je, 16 skodelic? To je 2-krat koliko časa traja, da razvrstite 8 skodelic saj imamo 8 skodelic tukaj, 8 skodelice tukaj. Ne vem, kako dolgo traja, da, tako da smo ga posploševati kot T za trenutek. Kdo ve, kaj je to? Ampak zdaj sem lahko nekako rekurzivno ali večkrat vprašati isto vprašanje. Koliko časa traja, da se razvrstite 8 skodelice? 8 skodelic sem hotel reči, meni časa, ki je potreben, da razvrstite 4 skodelice plus 4 skodelice, Nato jih združiti skupaj. Prav. Gremo v krogu že. Kako dolgo traja, da razvrstite 4 skodelice? Čas, ki je potreben, da razvrstite 4 skodelice je 2 skodelice plus 2 skodelice sortiranje plus združitve procesa. Prav. Kako dolgo traja, da razvrstite 2 skodelice? 2 skodelici je količina časa, ki je potreben, da razvrstite 1 skodelico plus čas, ki je potreben, da razvrstite eno skodelico plus količina časa, ki je potreben, da se združijo, ki je le 2. 

Prav. Zadnje vprašanje. Kako dolgo traja, da razvrstite 1 skodelico? Tu je osnova drži, da smo napovedali, da bomo zadeli prej. Dejstvo, da se ne dela nikakor rešiti najmanjših težav pomeni, da je zdaj nekako razred slogu šole, moremo iti začeti priklopom te številke nazaj noter Zdaj vemo, kaj T 1 je, da bom lahko priključite 0 za t 1. To mi bo dal odgovor na T 2, ki lahko nato priključite v višje. To mi bo dal T 4, kar sem lahko priključite na višje. To mi bo dal t 8, kar sem lahko priključite na višje. In če sem dejansko naredil, da izračunate s priklopom na teh odgovorov, Nato sem dobil T od 16 je 64 let. In kaj pomeni 64? Če je T 16, ja, to je 16-krat 4. Zato trdim, da je sedaj čas delovanja to stvar imenovano zlivanjem - in to se dogaja, da je fanciest od tistih, ki smo jih videli doslej - se dogaja, da se imenuje n log n ker lahko, kolikokrat Rob deljiva cel kup skodelic na pol? Prijavite n. To je isto, kot na primer imenika, je to isto, kot samo štetje npr. 

Kolikokrat lahko razdeli nekaj na pol? Vendar pa je ta združitev korak. Morda boste morali razdeliti na pol skodelice znova in znova in znova, ampak vsakič, ko boste morali združiti. In smo že povedali, da je združitev n skodelice meni n ukrepe ker moraš Istrgnuti skodelico, Istrgnuti skodelico in imate na dotik vsako skodelico enkrat, tako kot Rob storil. Torej, če delamo nekaj Dnevnik n-krat in delamo n stvari na vsakem od teh iteracij, vsako od teh halvings, imamo n-krat log n. Torej, če priključite 16 V tem primeru je 16-krat prijavite od 16 - Ne skrbite o tem, zakaj je temu tako, ker za zdaj še nisem pripraviti podlago - ampak dnevnik osnove 2, 16 je 4, 16 krat 4 je 64 let. Ampak po drugi strani, če bi smo mehurček vrste ali izbiro sort uredi ali vstavljanjem s 16 številkami, kaj bi bilo, če teče čas n 16? To bi bilo 16 kvadratov, kar je 256, ki tudi če ni povsem sledil vse matematike, 256 je večji od 64 let. To je res čarobna hrana za s seboj tukaj. In zavedati, da delajo preko tega v manjših primerov, ko se bo na pset Zato je toliko bolj intuitivno. Toda kaj to v resnici pomeni v smislu občutek tega algoritma je: Če smo dejansko pogledamo vrste spajanja - Naj ga povlecite v to okno tukaj - To je nekoliko drugačen primer, s katerim smo vsi 3 teh algoritmov - mehurček, izbire in združitev - le drug ob drugem. 

Vsi so začeli z naključnimi palice, in to je dobro. Nihče ni bistveno prednost pred drugimi. Grem v trenutku, kliknite vsako od teh animacij - Start Start, Start - kakor hitro sem lahko, tako da, v grobem, da vse skupaj začelo ob istem času, in kaj menijo, da je mehurček razvrstite v primeru hujše časa vožnje je kaj? >> [Študent] N kvadrat. N kvadrat. Izbirne razvrstite v najslabšem primeru teče čas je? N kvadrat. In zlivanjem je očitno - tudi če ni povsem upoštevati vse math zdaj, da bomo postali veliko bolj intuitivno skozi čas - je trdimo, n log n-krat. In ker log n je strogo manjši od n, ko imamo velike številke, n log n-krat manjša od časov N ali n kvadrat. Torej, kaj je občutek, da pravzaprav bolje algoritem glede časa vožnje, n log n-krat v primerjavi z n kvadrat? Pa gremo. Kliknite, kliknite, kliknite. 

To pomeni, da uporabite nekaj podobnega vrste spajanja. Imamo trenutek. Pa poglejmo, kaj se dogaja tukaj. [Smeh] Čigav je denar od vrste mehurček? Prej je odvisno od vhoda včasih. Pa poglejmo. Daj no. Zdi se, kot da se dohiteva. >> [Študent] Pojdi, mehurček vrste! [Učenci godrnjajo] [Malan] Ja, ja. [Učenci godrnjajo] Gremo, gremo, gremo! [Vsi navijajo] [aplavz] Torej, zdaj z 1 zadnji, končni demo, če je to precej zapleteno zaviti vaš um okoli matematiki ali vrsta vizualizacije tam, lahko dejansko slišati hitrosti različnih algoritmov drugače. To je animacija nekdo, ki dejansko zveni sodelavci s procesom zamenjavam in višine palic. Kot bomo videli tu, tam je še nekaj algoritmov tam, da so ljudje mislil. Ta prva se bo vstavljanje sortiranje in to bo letel skozi in vam zvočni občutek, kako te različne delo algoritmov. Tukaj je vstavljanje vrste. [Elektronske piskanje] [Malan] bubble sort. [Hitrejši elektronsko piskanje] [Malan] Izbira vrste. [Hitrejši elektronsko piskanje] [Malan] zlivanjem. [Elektronske piskanje] [Piskanje upočasni] [smeh] [Malan] Gnome sort. [Elektronske piskanje] 

To je CS50. Vidimo se naslednji teden. [Ploskanje in navijanje] 

[CS50.TV]