[Powered by Google Translate] [Tjedan 3, Nastavak]
>> [David J. Malan - Sveučilište Harvard]
>> [Ovo je CS50. - CS50.TV]
>> U redu. Dobrodošao natrag. Ovo je CS50 i to je kraj tjedna 3.
>> Dakle, za one koji nisu upoznati, prošle godine Harvardu pokrenuo ono što se zove Innovation laboratorij,
ili ja-laboratorij, koji je prekrasan zgrada preko rijeke APK kampusu
koji je otvoren za studente, učenike, studente GSAS iz diljem kampusa,
uključujući profesore, i to je mjesto da se zajedno raditi na inovativnim stvarima,
posebno poduzetničkih stvari
ako i 0 ili više prijatelja misleći da radiš nešto poduzetničke
bilo tijekom ove klase, nakon ove klase, ili izvan nje.
>> Dakle, jedna od stvari koje rade preko J pojma ti izlete,
od kojih je jedan u New Yorku, jedna od kojih je u Silicijskoj dolini.
Prostor je vrlo ograničen, ali to je prilika da se trljati ramenima s mbas
i diplomirani studenti diljem kampusa, a zapravo provesti vrijeme u tim područjima za
razgovor se startupima, pričajući poduzetnicima i slično.
Dakle, ako je zainteresiran, provjeriti ovaj URL ovdje.
To je također dostupan na slajdovima online.
>> Možemo ton dolje kuću audio samo malo?
Ako želite da nam se pridružite za ručak ovaj petak, 13:15 u Fire & Ice, molimo glavu tamo.
Isprike ako oblik već ispunjen u vrijeme kada se tamo.
No, mi ćemo nastaviti ovu tradiciju naprijed.
>> Danas ćemo nastaviti višu razinu rasprave o raznim problemima koje možemo riješiti,
fokusirajući se puno manje, barem danas, na broj i još mnogo toga o idejama.
Dakle, mislim natrag na tjedan 0 kad smo poderali telefonski imenik na pola,
Cilj koji je bio nešto učiniti, doduše, malo dramatična
ali poslati točku da traženje ne mora biti nužno,
kao očigledan na prvi pogled, kao što možda mislite.
A rješavanje problema u cjelini ne mora nužno može uvijek biti najbolji -
Najočitiji rješenje ne mora nužno može biti najbolji.
Dakle, imali smo tu telefonski imenik i, iskreno, sve nas u ovoj sobi imali instinkte,
najvjerojatnije, početi u sredini kada je u potrazi za Mike Smith i onda ići lijevo ili desno
temelji se na bilo slovo abecede mi se dogodilo da se na kraju.
>> Ali to jednostavna ideja da smo mi ljudi uzima zdravo za gotovo tako dugo
stvarno trebali početi dolaziti na čelu svoje pameti
jer kao što su problemi dobiti mnogo složeniji od telefonskog imenika,
one iste jednostavne, sjajne uvidi što će omogućiti nam
riješiti mnogo složeniji i zanimljiviji problema,
među njima neke stvari uzimamo zdravo za gotovo već ovih dana.
Milijarde web stranice vani, i još Google i Bing i kao
su u stanju pronaći stvari za nas kao da.
To se ne događa pomoću linearne pretraživanje, traži kroz sve moguće web stranicama.
Facebook je u mogućnosti da vam reći tko je sve od vaših prijatelja ili prijatelji prijatelja,
i da previše može učiniti naizgled u trenu ovih dana
iako imaju milijune korisnika.
>> I tako kako smo zapravo riješiti probleme na toj skali će u konačnici smanjiti
s idejama smo gledali u tjednu 0 i danas malo više.
Nećemo ponovo izvršiti ovaj algoritam, ali sjećam se također učinili u tjednu 0 Ova vježba
gdje smo svi ustanu, uzeti na broju 1,
i onda smo imali sve self-count po uparivanje off, dodajući svoje brojeve zajedno,
tada polovica bande sjeo na svakom iteracija.
Tako smo išli od 500 studenata na 250-125 i tako dalje.
No, kao što smo rekli u ponedjeljak, moćna ideja postoji
je da, ako smo udvostručili veličinu tog problema
i sva djeca iz pravosuđa ili EC 10 se vratio u sobu i pridružio nam se,
dobro, vjerojatno nije mogao računati da cijeli agregat grupu
sa samo jednom više velikih iteracija petlje jer bi samo možda udvostručiti veličinu
ili u EZ 10 slučaju malo više nego dvostruko u veličini.
I tako ćemo morati potrošiti malo više vremena,
ali mi ne bi trebali potrošiti 400 ili 700 više koraka.
>> Samo slikati ovu sliku na način koji je malo manje apstraktno, nemojmo su svi ustanu.
Ali, ako one od vas koji su odabrali da sjedi u orkestru danas ne bi smetalo stojeći,
neka je vidjeti ako možemo shvatiti među vama koji najviša osoba
obavljajući istu vrstu komparativne algoritma.
Dakle, ako ste sjedi u orkestru, moje isprike, ali korak 1, stand up;
2. korak, par off s kim ste u blizini,
shvatiti tko je jači, i sjesti ako su kraći.
Zatim ponovite.
[Studenti mrmljajući]
>> Ok.
Ok. Jedan je napustio položaj. Koje je vaše ime? >> Andrew.
>> Andrija, ti si najviši osoba u orkestru sekciji danas.
>> Čestitamo. [Pljesak i navijanje] Ok. Imati sjedište. Dakle, našli smo Andriju.
No, koliko dugo će to su me uzeti, na primjer, kako bi pronašli Andriju
u ovom orkestru dijelu 50 + ili tako ljudi?
Mogao sam uzeti prilično jednostavan pristup i početi ovdje.
I ja sam 2 ljudi ustanu i samo sam ih usporediti,
i onda ja kažem da onaj tko je nešto kraća, "Ok, ti ​​sjedni"
i ja ću se sjetiti tko jači osoba bila.
Tada sam, ponavljam, ponavljam, ponavljam, i ja objesiti na najvišim osobi
dok sam naći netko nešto viši od njih, na kojem trenutku
nešto kraći osoba ima onda sjesti.
No, u tom algoritmu u ovom dijelu orkestra, ako postoji n od vas,
koliko koraka je da algoritam će to trajati? >> [Student] N.
>> To će potrajati n, desno, jer u najgorem slučaju, da se tako izrazim,
najviša osoba je vrlo posljednja osoba da ću dobiti samo slučajnim peh.
Dakle, u najgorem slučaju, trajanje tog algoritma je linearno, to je n
gdje je n je ukupan broj ljudi u prostoru, veličina problema.
Što o tom algoritmu?
Činjenica da ste svi ustali i onda opet pola vas sjeo,
pola vas sjeo, pola od vas sjeo.
Koliko koraka treba da su se, ako postoji n od vas ovdje?
[Student] N log n. >> To bi bilo još gore. Prijavite n.
>> Dakle, prijavite n, čak i ako ne sasvim sjetiti što je logaritam,
za sada, samo cijenim da se odnosi na neki način to prepoloviti i prepoloviti i prepoloviti.
To ne mora biti faktor dva. To bi mogla biti čimbenik tri.
No, to je to ponavljanje iste vrste faktora tako da je veličina problem počinje ovdje
ali onda odmah ide ovdje, onda ovdje, onda ovdje, onda ovdje.
Vi ne uzimate male bites iz problema, ste stvarno sjeckanje daleko na njega
s velikim naletu svaki put.
Tako smo imali 50 ljudi, zatim 25, pa 12 ½ ili 13 ljudi stoji,
onda 6 ½ i tako dalje dok napokon samo Andrew je ostao stajati.
Tako ćemo nazvati taj zapisnik n, a možete vizualizirati ovo što slijedi.
Podsjetimo ovu sliku ovdje gdje linearni algoritam je poput crvene linije tamo,
žuta linija bila brojanje prema 2s algoritam koji smo koristili za brojanje studente
u prošlosti, ali danas je sveti gral će ostati ova zelena linija
gdje ako smo udvostručili broj ljudi u orkestru sekciji ili jednostavno rekao,
kvragu, ajmo se svi u cijeloj sobi stand up, a ne kao velika stvar
jer smo otprilike dvostruko koliko su ljudi ovdje dolje,
1 više iteracija, nije problem.
>> Našli smo Andrija ili tko se događa da se jači nego Andrija
u polukatu ili balkona.
Dakle, ove jednostavne ideje da mi je uzeo toliko zdravo za gotovo u telefonskom imeniku,
shvatiti da postoji toliko različitih mjesta u kojem možemo ga primijeniti.
Samo slap neke žargon - Zapravo, nego žargon prvi,
pusti me na ovu sliku ovdje.
Upravo sada smo govorili o n i n / 2, a zatim se prijavite n,
ali svakako može doći do, kako ćemo tijekom semestra,
druga vrsta matematičkih formula opisati ovaj opći pojam o prikazivati ​​vrijeme.
To su iz konteksta za sada, jer ćemo vidjeti zadugo
algoritmi koji to zapravo predstavljaju.
>> Ali primijetite ovdje linearna linija N, ravna crta, je zapravo vrlo niska pokazuje upravo sada.
To je svojevrsna optička varka u koji smo samo promijeniti ono što os x predstavlja
i y osi, a mi možemo napraviti ravne linije točku u bilo kojem smjeru želimo.
No, razlog da je tako naizgled stan sada
je zato što mi je potrebno da bi boravkom na ovom grafu za mnogo sporije trčanje vremena.
Za sada, znam da postoje neke prilično loše algoritmi u životu,
od kojih su neki ne uzimaju n korake ili, još bolje, prijavite n korake, ali više.
Dakle, iznad crte n ovdje na dnu obavijesti tu je n puta log n,
pa ćemo vidjeti što to znači prije dugo.
Iznad da je n kvadratna, a nismo vidjeli nikakve n kvadratnih algoritme, ali još smo uskoro.
I to izgleda jako loše.
Tu je 2 do n, nešto eksponencijalna, koja se osjeća još gore.
Pa ipak, začudo, onda postoji n kubu, koji, ako ste vrsta razmišljanja naprijed,
ako vrsta učiniti math, 2 do n zapravo postaje puno ravniji,
mnogo viši nego n kubu ako pogledate osi dovoljno daleko van.
Dakle primijetiti upravo sada ove osi samovoljno 2 do 10 na x osi.
>> A što to znači?
To znači da dvije ljudi do 10 ljudi u sobi.
To je sve x znači: veličina problema, bez obzira na kontekst.
I vertikalna os upravo sada je broj sekundi ili broj koraka -
neki jedinica vremena.
Ali primijetite da je 0-60 i 0-10.
Ali ako ćemo vrsta zoom out, kao možda u Excelu ili nekom crtati softver,
i idemo do 200.000, primijetiti da nešto poput 2 do n
će u potpunosti preplaviti pokrenute puta od n kvadrata,
n kubu, n log n - sve smo razgovarali o do sada.
A ipak, ulov je kada početi govoriti o stvarima kao što su Facebook
gdje ste mnogo, mnogo, mnogo ljudi svi međusobno povezani,
ste n ljudi, od kojih svaki može imati koliko god n prijatelja
ako svatko je vrsta ortak u svijetu,
dobro, to je n puta n već, tako da je n kvadratnih moguće prijateljstva,
barem u 1 smjeru, n kvadratna mogućih prijateljstava.
Tako da je već sugerira da traži facebook društveni graf, da se tako izrazim,
može početi da se izražava u takvim formulama.
>> Vratit ćemo i učiniti ovo puno konkretniji,
ali za sada, cilj za narednih nekoliko tjedana
će biti sigurni da neće ići o provedbenim algoritama ili kod
da kraj gore uzimajući onoliko vremena kao nešto poput ovoga.
Ali fascinantna stvar o informatici ako nastavi u ovom području
uzimanje nastavu kao CS121, CS124, od kojih su oba teorija tečajevi,
je da zapravo postoje neki problemi koji postoje na ovom svijetu
koje iz temelja, koliko znamo, ne može riješiti bilo brže
od najgore od tih grafova zapravo sugerira.
Dakle, tu je puno otvorenih problema u ovom svijetu da to puno bolje nego ljudi imaju tako daleko.
>> Pa krenimo onda sa ovom primjeru.
Vidjeli smo Sean borbu s tom na kameri, sve previše neprilično na videu.
No, stvarnost je kad Sean je zadatak pronaći na brodu kao što je ovaj broj 7,
Podsjetimo da sam rekao da, "Tu je negdje iza tih komada papira ili bijelih vrata
"Broj 7. Sean ga pronaći za nas."
I to je predivno neugodno gledati
jer je on bio stvarno bore s ovim problemom.
No, stvarnost je Sean činio kao netko u sobi mogao imati učinjeno.
Uzeo je malo duže nego tipična osoba može imati,
ali on pretpostavlja da je bio neki trik za ovaj problem,
on pretpostavlja da je bio nešto nedostaje.
I to nije pomoglo da se stotine oči su imajući dolje na njega.
>> No, stvarnost je da je ulaz na problem je hrpa slučajnih brojeva
a vi ste se pitali kako pronaći jedan takav broj,
Najbolje što možete učiniti je linearno pretraživanje.
Start na lijevoj strani, premjestiti na desno, ili početi na desno, premjestiti na lijevoj strani.
Retroaktivno, mogli bismo biti razmišljanje ", Sean, zašto nisi samo početi s drugog kraja?"
Pa, 7 je mogao samo tako lako je ovdje slučajno,
ali namjerno sam ga stavio tamo jer sam shvatio da se neće početi krajem.
Tako sam nekako manipulira situaciju, ali Slučajnost 7 mogao biti bilo gdje.
Dakle, počevši od desnog kraja možda bilo bolje onda,
ali što ako iduće godine selim 7 drugdje?
To nije temeljno novo rješenje za problem -
počevši od jednog kraja ili druge - kada si dao nema druge pretpostavke.
Dakle, Sean počeo u potrazi kroz brojeva i on je rekao, "5. To nije ovdje."
Tada je otišao ovdje i vidio 19, a zatim je zastao za oko 20 sekundi,
onda je otvorio to za 13, a onda je postalo očito
da ne izgleda kao da se obrazac ovdje.
To nije 1, 2, 3, 4 ili slično. Tu su praznine u brojkama, koje nije pomoglo.
I također, činjenica da sam koristio ove jeftine komada papira da prikrije brojeve
je zapravo namjerno, jer ako sam uklonio sve ove komada papira,
većina nas, Sean uključeni, vjerojatno bi pogledao vrsta makroskopski
na ploči i rekao: "Oh, 7 je očito tamo." Učinili smo to odmah.
>> I to može biti način ljudski mozak funkcionira u određenoj mjeri,
ali u stvarnosti, oči ili um je vjerojatno skimming brojeve s desna na lijevo,
s lijeva na desno, srednji na van - nešto se događa fiziološki
kao da se osjećao kao da se događa odmah,
ali izgledi su čak i interno tamo bila neka vrsta metodologije za pronalaženje 7.
I doista, sad kad govorimo o nizovima i struktura podataka
i memorija unutar računala, jedino mi ljudi mogu učiniti
je pogledati na pojedinim mjestima memorijskih jednom na vrijeme.
>> Dakle, svaki drugi položaj kao što bi i biti pokriven s nekom papiru
jer ne možemo ga vidjeti u svakom slučaju. Mi možemo učiniti samo jedna stvar u isto vrijeme.
Dakle, u ovom slučaju, u Sean slučaju, otišli smo ovdje i onda smo otišli ovdje
i onda smo otišli ovdje, ovdje, ovdje, ovdje, dobio pametan do kraja
i samo vrsta preskočila ovaj jedan samovoljno i pronašao 7 tamo.
Ovo nije bio osobito posebna. To je također bio iz reda.
No, on je konačno pronašao 7.
Ali sada takeaway stvarno je to najbolje što možete učiniti kada je dobio nikakvu informaciju
osim nasumično poredani brojeva je početi s lijeve ili započeti s desne strane.
Ili pakao, da slučajno može otvoriti vrata, ali čak i tada ono što to znači biti slučajan?
Pa, mi bismo se nekako formalizirati što to znači za početak ovdje,
onda ići ovdje, onda ići ovdje. Sean je velik, a to je bio samo zabavno gledati.
Što ako umjesto toga smo promijenili je problem malo i dovesti do ovogodišnjeg Seana, ako hoćeš?
Bi li itko biti udoban dolazi na pozornicu i rješavanju malo drugačiji problem
i koji se pojavljuju na kameru?
>> Idemo dalje orkestra, jer ti dečki su prilično uključeni već danas.
Kako o u ružičasto, u šeširu? Dođite na dolje. Koje je vaše ime? >> Alex. >> Alex. Ok.
Dakle, Alex će biti ovogodišnji Sean i pojavit će se u narednih nekoliko godina
vrijedan CS50 predavanja.
Alex, lijepo da zadovolji vas. >> Drago previše.
Izazov pri ruci za vas je da ste ga malo lakše
u da kažem vam iste brojeve ovdje, ali oni su sada riješeno.
Tako sada vaš cilj je pronaći broj sedam.
A zapravo, mi stvarno treba napraviti ovo - ti si vrste varanja, kao i računalo ne bi,
gleda na ono što su brojevi bili maloprije.
S kredom to zapravo ne ide kako bi se sve to puno,
ali ajmo se pretvarati da ne znate što je izvorni polje je.
Sve što sada znamo je da imate niz sortirani brojeva
koji bi mogli imati praznine između njih, i vaš cilj je pronaći broj sedam.
Kako bi ste, razuman čovjek, ići o pronalaženju broj 7?
>> Idi od niske do visoke? >> Ok. Idi niske do visoke.
I nemojte ih otkinuti. Ajmo ih podignite tako da ih možemo ponovno.
Dobro, 1. Čekaj. Prije nego što dalje, to je bio jedan, jasno krivu.
Dakle, ono što se događa kroz vaš um sljedeći? Što je vaš sljedeći potez?
Sljedeći. >> Ok. Sljedeći. Dobar. 3, tako netočne. Što je vaš sljedeći potez?
Imajte na idući. >> Redu. Imajte na idući. 5.
Dakle, držati na idući, i neka mi ruka ti ovo za buduće naraštaje.
7. >> Izvrsno. Vrlo dobro. Pronađeno broj sedam. [Pljesak]
Dakle, ono što je dobro, ali Sean previše pronašao broj sedam.
I tvrdim da niste stvarno iskoristiti ovaj dodatni dio informacija,
a to je da su ti brojevi sortiraju.
Dakle, možemo učiniti bolje? Bilo koji sugestija ovdje? Da, u leđa.
[Student] Binarni pretraživanje. >> Nemam pojma što binarno pretraživanje je.
>> [Student] Početak u sredini. >> Početak u sredini. Ok. Dakle, neka je vidjeti ako možemo doći.
Dakle, ako umjesto da ste rekli početi od sredine, ići naprijed i otvoriti srednju vrata.
Tu je osam od njih, tako da ćete morati proizvoljno odabrati jedan
malo na lijevo ili na desno. Ok. 7! [Pljesak] Jako lijepo.
Ok, ali gdje su mi ide s tim?
Pretpostavimo samo razbiti kravatu što je počeo ovdje
jer je to jednako moglo dogoditi, kao dobro.
Mi se upravo dogodilo da znaju da je 7 bio tamo. Dakle, ovo je 13.
Dakle, ako su razvrstani i samo smo započeli u sredini,
što bi optimalno sljedeći potez bio?
Idi lijevo. I tako evo primjer telefonskog imenika opet.
Ako 13 je ovdje i znamo popis sortiran,
onda sve od tih komada papira su nezanimljivo za nas sada
jer smo već znali da sedam mora biti lijevo
ako su ti brojevi sortiraju i našli smo 13.
>> Dakle, ono što je vaš sljedeći potez ovdje? >> Idite na lijevoj strani. >> Dobro, dobro.
Dakle, idite na lijevo, i - čekati, hej, hej, hej. To je varanje.
Tako ste pronašli sedam, ali ono što je algoritam mi samo primijeniti?
Počnite u sredini. >> Dobro. Dakle, ono što je logičan nastavak te iste ideje?
Oh, samo to. >> Točno. >> Tako sam početi ovdje. >> Dobro.
Dakle, sada smo otišli malo na lijevo ponovno. To je tri.
No, zanimljivo takeaway sada je što neki to ne morate brinuti o?
Ovo dvoje. >> Ovo dvoje. Dakle, sada to može ići dalje, to se može otići.
Sada je problem da je 8 onda je veličina 4 sada je veličine 2.
Mi smo uzimajući prilično blizak. Opet, idite na sredini tih dvaju elemenata.
>> Ok. Dakle, to je vrsta nesretni da sada smo uvijek ide lijevo, jer smo zaokruživanje dolje.
Ali to je u redu jer se sada bacamo to daleko i sve drugo, ostavljajući nas sa samo sedam.
Idemo dati aplauz. Našli smo 7 opet. [Pljesak] Ok. Naravno.
Objesite na samo 1 više drugi.
Iako da sljedeći proces vrsta je malo duže nego što smo osjetili da bi,
Iskreno, vaši prvi instinkti bili najbolji, zar ne? Našli smo 7 trenutno.
No, mi bi našli sedam brže, bez obzira što u ovom primjeru u odnosu na ovaj jedan
jer ako su brojevi sve su razvrstani, baš kao i na stranicama telefonskog imenika,
što doista može usitniti polovicu problema opet i opet i opet.
A to nije baš tako lako vidjeti ovaj sa samo osam brojeva
za razliku od 1000-stranice telefonskog imenika gdje se stvarno ga vide vizualno,
ali u ovom slučaju ovdje kad Sean je u potrazi za sedam,
koliko koraka u najgorem slučaju bi to ga uzeti? >> [Student] 7.
7 u najgorem slučaju. Pa, u najgorem slučaju ne 7 ako ima osam vrata ovdje.
To bi trebalo mu osam koraka.
>> Dakle, ako postoji n vrata, možda su se Sean prije par godina n korake.
Sada, u vašem slučaju, Alex, s obzirom da su ti brojevi sortiraju -
i možemo vrsta zaključiti ovaj odakle smo bili do sada u ovoj priči -
što je trčanje vrijeme Alex je više inteligentnog algoritma
počevši od sredine, a zatim ponavlja?
[Student] 3. >> Dakle, to će biti 3, ugrubo, ako idete 8-4 2 do 1.
Dakle, tri koraka ili, općenito, da je zapisnik n opet.
Svaki put kad si prepoloviti i prepoloviti i prepoloviti i prepoloviti,
to je izraz tog ideje log n.
I tako da bi uzeli vam samo 3 koraka, i doista je to učinio
kada smo otvorili vrata prepoloviti i prepoloviti,
dok bi to uzeti Sean neke 7 ili 8 koraka.
Dakle, hvala vam za bitak s nama ove godine. >> Hvala. Drago mi je da sastanak.
Hvala Alex. >> Isto. [Pljesak]
>> Što je onda stvarna to implicira?
Sada zamislite da to nije osam vrata, koja je, iskreno, svi mi mogli pronaći nešto
iza osam vrata prilično brzo samo po kidanjem komada papira i ide s našim nagonima.
Ali što ako je milijun vrata? Što ako je 4000000000 vrata?
U slučaju 4000000000 vrata, ste stvarno idući u ištanje to ići s Alex je algoritam,
binarno pretraživanje kako ćemo ga početi zovete ili podijeli pa vladaj, općenito,
gdje držite prepolovi i prepolovi problem,
jer ako imate 4000000000 vrata, koliko puta možete usitniti 4000000000 u poluvremenu?
[Student] 32. >> To je zapravo 32. Možete raditi ovo na komad papira ili u vašoj glavi.
Možete ići 4 milijarde do 2 milijarde to 1 milijardu pola milijarde, na 250 milijuna, točka, točka, točka.
A ako ne iz matematike, idete doista dobiti 32,
i da zapravo odnosi na informatici jer smo obično računati u ovlasti dva.
2 do 32 dogoditi da bude 4000000000.
Dakle, postoji puno važnosti za ove vrste moći dva u računalnoj znanosti.
>> Ali što je 8000000000? Koliko koraka je da će se, ako postoje 8000000000 vrata?
[Student] 33. >> Dakle 33. Što ako postoji 16000000000 vrata? Koliko koraka je da će to trajati?
[Student] 34. >> 34. Mogli bismo vrsta nastaviti ovaj nauseam oglasa. No, to je moćna stvar.
Možete uvesti milijarde više ulaza za vaš problem, ali nije velika stvar,
samo uzmete jedan dodatni zalogaj od njega i tako nam daje nešto poput binarnog pretraživanja
ili podijeli pa vladaj, više općenito.
Ali ja sam vrsta varanje ovdje, zar ne?
U slučaju Alex je algoritam, imala je prednost nad Seanom.
Znala je da su ti brojevi su razvrstani, ali Alex nije imala sortirati ih sama.
Ja se unaprijed došao do ploči i vrsti napravio siguran
da sam nacrtao ih sve u sortiraju bi, onda sam ih prekriven papirom.
No, koliko je posla nije da me odvesti?
Ako smo krenuli s tim brojevima u nekom naizgled nasumičnim redoslijedom -
u ovom slučaju te jednostavniji brojevi, jedan kroz osam ovdje -
kako ćemo ići o razvrstavanju tih vrijednosti?
Ako ste bili čovjek dao ovaj zadatak, kakav intuitivan pristup bi vam se
za sortiranje cijela hrpa brojeva?
Ove stvari su postavljeni kao slagalice. Da.
>> [Student] ja bi se svaki broj i usporedi ga svaki
i zadržati ide na lijevo. >> Dobro, dobro.
Tako se svaki broj, usporedite ga jedan pored nje,
i onda samo držati se kreće zajedno s popisom, vrste rejiggering stvari kao i ti ići.
Dakle, ovdje imamo priliku za možda nekoliko više ljudi da se uključe.
Nemojte mi imamo osam više volontera koji bi rado došli do?
Malo manji pritisak jer niste jedini. 1, 2, 3, 4, 5, 6, 7, 8.
Dođite na dolje. Vi ćete biti brojevi 1 do 8.
Idemo vidjeti ako mi to ne može učiniti sortiranje za Alex mnogo na isti način na koji sam to učinio u unaprijed.
1, 2, 3, 4.
Idi naprijed i ako bi, redati na pozornici između glazbeni stalak i mene ovdje
u istim redoslijedom kao slajd na zaslonu.
Uh-oh.
Mi ćemo vam raditi u sljedećem primjeru. Oh, čekaj, čekaj. Ovdje ćemo ići. Čekaj.
Sljedeći primjer je sada. Ovdje možete ići. Broj 8. Dođi gore.
U redu. Sortiraj sami prema ovome.
Slide samo malo na strani glazbe stajati ovdje.
Dakle, imamo 4, 2, 6 - doći tamo, ovamo, tamo - tri.
Da. Ok. Možete ići ovamo. Ne, ostani tu.
Da, upravo tamo. Ne, ja sam u krivu. Upravo tamo. Dobro, vrlo dobro. Ok.
Dakle, sada ćemo ih sortirati u rastućem redoslijedu.
>> Kako mogu ići o događaj ovaj?
Algoritam koji je predložio trenutak prije bila zašto ne bismo samo usporediti
su ljudi koji su vrsta jedni pored drugih, a zatim popraviti sve greške,
kreće s lijeva na desno.
Dakle, ovdje imamo četiri i dvije, očito iz reda. Ajmo vas zamijeniti. Ok.
Dakle, sada idem za kretanje prema dolje liniju. 4 i 6, nope. [Smijeh]
6 i 8, prilično dobro. 8 i 1, dopustite mi da vam zamijene dečki. U redu.
Dakle 8 i 3, swap vam dečki.
8 i 7, dopustite mi da vam zamijene dečki. 5 i 8, odličan.
Dajem vam sortirani popis.
U redu. Dakle, ne sasvim.
No, to je bolje, jer su veći brojevi - Slučaj u točki 8 -
su vrsta bubbled se s lijeve na desnu.
Tako sam dobio jedan od njih u pravu, ali to se osjeća kao što je ovaj nije sasvim riješiti problem.
>> Pa što bi ti predlažeš mi učiniti sljedeće? >> [Student] Neka to rade. >> Mi zadržati to.
I shvatili, opet, postavili smo stvari koje samo što sve ljude
vrsta inteligentno se dogovoriti na temelju toj slici,
ali sada moramo biti puno više metodičan.
Moramo biti algoritamski o tome kao da smo pisanje koda -
u ovom slučaju verbalnog pseudocode.
Pa neka mi samo pokušati opet. To je radio prilično dobro. To nije ga riješiti.
No, kada je bez sumnje, samo probati i pokušajte ponovno. Dakle, 2 i 4, nije pomoglo više.
4 i 6. Ah! 6 i 1, malo bolje sada.
6 i 3, dobro. 6 i 7, 7 i 5, 7 i 8, dobro.
A znate, ja vjerojatno ne može ignorirati 8 sada, jer on je na kraju popisa.
Možda mi ne morate brinuti o nekome tko ide pored njega.
Ali neka je vidjeti ako to je sigurno pretpostavka.
Sada je popis - prokleto - nije riješeno. Pokušajmo ovo ponovno.
Dakle 2 i 4, 4 i 1, 4 i 3.
4 i 6, dobro. 6 i 5, dobro.
6, 7, i 8, dobro. No, obavijest, mogu samo zaustaviti ovdje i sada zaustaviti ovdje sada?
[Student] Da. >> Da?
Što ako je netko od vas bio broj 9 skroz tamo?
To bi bio razvrstani. >> Dobro. To bi bio razvrstani prvi put okolo.
Dobar. Dakle idemo opet. Skoro smo tamo.
1 i 2, 2 i 3, 3 i 4, 4 i 5, 5 i 6, 6 i 7, 7 i 8.
>> Ja sam učinio, ali sada, opet, ja sam računalo koje mogu učiniti samo ono što sam rekao da ne,
i moja jedina uspomena sada je da sam zapravo samo učinio malo rada.
Nešto promijenilo ovdje.
Dakle, nisam tehnički potvrdio vizualno ili algoritamski da ovaj popis je doista riješeno.
Dakle, samo za dobru mjeru, samo da se analni o tome, hajdemo to učiniti jednom više vremena.
Dakle 1 i 2, 2 i 3, 3 i 4. I znate što?
Samo za dobru mjeru, ja ću pratiti na mojoj ruci ovaj put
koliko swaps sam napraviti samo tako da znam koliko posla sam zapravo učinio.
3 i 4, 4 i 5, 5 i 6, 6 i 7, 7 i 8. Nema zamjene.
Dakle, sada sam legitimno biti idiot da to učinite opet
jer ako sam ne raditi kroz ovaj prolaz ljudi,
onda je jasno da će se to opet dogoditi ako nitko od njih je nekako slučajno
adversarially se kreće oko. Dakle, sada mogu prestati.
Sada ćemo postaviti pitanje, koliko posla je to zapravo me odvesti?
Koliko koraka nije to trajati? >> N kvadrat.
Da, tako n kvadratna. Odakle ti n kvadratna iz?
Morate provjeriti svaki NUM -
Tu je n broj, a vi morate provjeriti svaki broj s drugim n brojeva.
Dobar. >> Dakle, to je n kvadratna. >> Dobro.
>> Dakle, ona se osjeća kao da bi mogao vrlo dobro biti n kvadratna, zar ne?
Tu je n od tih momaka, 8 konkretno u ovom slučaju,
ali svaki put kad sam prošao kroz ovaj popis sam uspoređujući prvu osobu protiv drugi,
drugi protiv treći opet i opet i opet,
i kad sam dobio na kraju, što sam učinio? Ja ga redid.
Dakle, ako smo generalizirati ovo objašnjenje, mi smo n ljudima
i sam što, očito, 8 koraka, n koraka, svaki put sam proći kroz ovaj algoritam.
No, koliko puta u najgorem slučaju moram ići kroz ovaj popis ljudi?
[Student] N puta. >> Vjerojatno n, desno, jer u najgorem slučaju,
što je vjerojatno najgori slučaj aranžman od tih dečki iz get-ići?
Ako ste potpuno obrnut poredak
jer samo pretpostavljam psihički, let's - Koje je vaše ime? >> Bowen.
Bowen. Ok. Dakle Bowen, dolaze ovamo samo na trenutak.
>> Pretpostavimo da je Bowen je ovdje na početku algoritma,
i mi ne znamo što svi drugi, ali ovdje Bowen, prema ovom algoritmu -
a ako želite samo šetati sa mnom - ide na balon up, kao što je učinio prvi put oko,
sve do kraja.
Ali pretpostavimo da je osoba pored Bowen je bio broj 7.
Moram se vratiti i dobiti broj sedam, što znači da moram ići sve na putu natrag ovdje.
Sada moram imati taj isti šetnji s osobom koja je broj 7.
No, što ako onda broj 6 je pokraj njega kao dobro?
Onda moram se vratiti i dobiti šest.
Pa opet, na svakoj iteraciji ove petlje govorim da svaki od n ljudi,
i ja morati napraviti n od tih šetnje kako bi bili sigurni ja se povlačim
sve od najvećih elemenata leđa i natrag i natrag na samom kraju popisa.
Dakle, n stvari n puta je samo n puta n ili n kvadratna.
>> Dakle, ovdje već imamo algoritam koji je više ne n, koje više nisu dnevnik n,
to je zapravo gore nego bilo što smo učinili prije.
Dakle, Alex vrsta posrećilo u to sam učinio sve djelo očito up front za nju,
sve skuplji rad, tako da je mogla uživati ​​u ovom binarnom pretraživanje algoritam,
što je log n.
No, to je u skladu s ponedjeljak na temu.
Dali smo malo više prostora, koristili smo više bitova, kako bi se ubrzao naše vrijeme rada.
Toliko se kao da je to trade-off između vremena i prostora,
Također bi mogla biti samo ustupke između vrijeme provedeno do prednjeg vrstu dobivanje stvari spremni otići
i stvarno izvršenje algoritam kao pretraživanja. Pokušajmo još jednom.
Ako vi ne bi smetalo samo brzo preraspodjela sami odgovarati da opet,
ajmo probati nešto malo drugačiji, gdje je ne sasvim kao jednostavan
kao samo popraviti sve pairwise pogreške, što je super intuitivno.
Hajdemo umjesto toga biti malo više namjerno i to.
Ovo je jedna previše bih predložiti je vjerojatno prilično intuitivno.
>> Ajmo odaberite najmanji osobu s popisa i opet. Dakle, ovdje mi ići.
4, vi ste najmanji čovjek sam tako vidio do sada,
tako da ću psihički sjetiti da je samo pokazujući na tebe za sada.
2. Ooh! Zaboravite broj četiri. Upravo sam pronašao novi najmanji element u ovom popisu.
Idem vrste sjetiti da. 6, 8.
Ooh! 1. Doviđenja. Dakle, sada ću se sjetiti broj jedan.
Mi znamo da je jedan je najmanja, ali sam računalo. Što ako postoji 0?
Što ako postoji -1? Moram zadržati ide.
Dakle 3, 7, 5, nope. Ok. Dakle, broj 1 je najmanji.
Dopustite mi da vas odabrati iz popisa - hrapavi ići na ovaj način -
i staviti proizvoljno na početku popisa.
Sada, pričekajte malo. Nekako prevareni.
Ako ti dečki ne predstavljaju popis osam osoba, ali je polje,
8 komada memorijskog - ti smeta povlači za samo trenutak?
Tu je zapravo nema mjesta za vas ovdje.
Pa kako ćemo napraviti prostor za - ono što je vaše ime? >> Sammy. >> Sammy.
Kako ćemo napraviti prostor za Sammy?
>> Mi premjestiti n koji su prije mene. >> Ok.
Tako smo mogli kretati n ljude koji su prije njega,
pa ako vi želite da se jedan namjerno, dramatičan korak s lijeve strane.
Oni sve učinio da u sklad, ali zadnji put sam pisao neki kod,
ne možete sortirati od presele mnoge stvari odjednom.
Mogli smo to učiniti u petlji, kreće sve u jednom trenutku.
Dakle, ako vi ne bi smetalo odstupi s desne strane,
i Sammy, ako bi korak unatrag jer je još uvijek nema mjesta za tebe,
sad ajmo to učiniti. Gdje je Sammy trenutak prije? Upravo tamo.
Dakle, postoji jaz postoji. Dakle, da bi mogao preseliti u Sammy na licu mjesta.
Sada sljedeća osoba i sada sljedeća osoba, sada sljedeća osoba. Sada imamo prostora za Sammy.
Sada, netko iz publike - što je bilo dobro, da je bio ispravan,
osjećala sam se malo vremena - što je brže? Da.
[Student] Novi niz? >> Što je to? >> [Student] Novi niz? >> Dobro, dobro.
>> Dakle, u skladu s ovom temom samo ustupaka, zašto ne bih jednostavno napraviti novi niz
i onda Sammy će se kupati u prostoru ispred tih ljudi, na primjer,
a mi samo možemo početi punjenje novi niz uopce. To je previše raditi.
Ali ja nisam zainteresiran za trošenje više prostora danas. Što je drugi pristup?
[Student] Zamijeni. >> Ok. Mi smo samo mogli zamijeniti ove dvije dečki. Koje je vaše ime?
Mario. >> Mario. Dakle, Mario, bili ste trenutno ovdje.
Sammy, možete backup samo na trenutak? Mario je bio ovdje.
Nemamo prostora za vas više, pa ako ne bi smetalo ide gdje Sammy je,
ćemo staviti Sammy ovdje, i sada bih tvrditi da je Sammy zamjene operacija bila mnogo brže.
Napravili smo jedan rad zamijeniti ove momke, ili možda dvije da zamijene ove momke,
ali nismo to 1, 2, 3, 4, tako da se osjeća bolje. Sada, pričekajte malo.
Nekako mi je problem pogoršava, jer broj 4 je nekako blizu početka.
Sada broj 4 je malo bliže tom cilju, ali ja ne znam ili briga o tome.
Dakle, ovo je samo loša sreća da je broj četiri je malo dalje od svoje predodređen mjesto.
Dakle, ajmo sad ponoviti ovaj algoritam.
>> Da podsjetimo, dokle god ta priča bila, sve mi je bilo hodati po popisu
u potrazi za najmanjim brojem osoba.
Pa sada neka to učiniti opet. Mi ne moramo brinuti o Sammy više.
Možemo samo ići ovdje. Ooh! Broj 2. To je prilično mali broj.
6, 8, 4, 3, 7, 5. Dobro, dobro.
I srećom, slučajno, ne moram da se presele - >> Willie.
Willie, jer on je u svom pravom mjestu sada.
Ajmo to učiniti opet i ignorirati ove dvije dečki.
6. To je prilično mali broj. Ooh! 8 je definitivno veća.
4. Neka se usredotočiti na četiri. Ooh! 3 je čak i bolje.
7 i 5. Pa što ćemo učiniti sada s - >> Roger. >> Roger?
Idemo ga zamijeniti s brojem šest.
Dakle, ako šest i tri željeli mijenjati,
sada smo vrsta stečen sretan u tom 6 je bliže, gdje bi trebala biti,
ali to je samo slučajnost ovdje. Dakle, ajmo sad ići tamo.
8 je prilično mali broj. Ooh! 4 je manji.
6, 7, 5. Što ćemo sad učiniti? >> Zamijeni. >> Točno.
Dakle, sada idemo napraviti ovu vrstu brže.
8, 6, 7, 5. Odakle 5 ići? Dobar. Ok.
6, 7, 8. 6 dobiva ostati gdje je. Koje je vaše ime? >> Rosalie.
Rosalie dobiva ostati gdje je. 7 dobiva - Idemo vidjeti. 7, 8. Ok.
Dakle, sedam dobiva ostati gdje je. Koje je vaše ime? >> Amna. >> Amna.
>> Dakle, Amna dobiva ostati gdje je, a broj 8 je već gdje on sada treba biti.
Dobro, dobro. Osjeća se kao da smo tek stvara posao za sebe ovdje, ipak.
Što je u konačnici trajanje tog algoritma?
Ako mislimo o tim ljudima ne kao 8 ali kao n? >> To je n.
To je n koraka, ali mi provjeravamo svaki put.
Ok. N, ali ti si provjeri svaki put?
Ok, ali ako to n koraka, ne bih bio u mogućnosti da vam sortirati samo ide 1, 2, 3, 4?
Oh! Ok, to je velika razlika.
Dakle, n četvrtasti zašto? Što se zapravo događa?
Tu je n ljudi u ovom popisu, ali da se naći najmanji osobu na popisu
u najgorem slučaju, koliko koraka moram uzeti? >> N.
>> N, pravo, jer u najgorem slučaju, broj jedan je skroz tamo,
tako da moram ići ga ili nju.
I onda kad sam napokon shvate 1 je najmanji, onda je prilično brzo kako bi ih zamijeniti.
Ali sada moram početi od početka i tražiti tko?
Sljedeći najmanji osoba, što je 2. Gdje u najgorem slučaju je 2?
Oh, moj Bože. To je sve način ovdje na kraju.
Dakle, sada sam upravo učinio još n koraka, još n koraka.
I ako imamo n ljude iu najgorem slučaju najmanji čovjek je n koraka,
to je opet n puta n, pa smo opet n kvadratna.
To se ne osjeća tako dobro.
A u stvari, čak iu najboljem slučaju - Pretpostavljam da počnete razvrstani -
koliko koraka je potrebno za mene koristeći ovaj algoritam za sortiranje tih n ljude?
N kvadrat. >> Čuo sam n kvadratna. Zašto n kvadrat?
Budući da još uvijek imate da provjerite svaki put. >> Da.
I imate kako bi ih zamijeniti. >> Iako mi ljudi su vrsta sveznajući
u smislu vizualno da možemo samo vrsta vidjeti da je to razvrstani,
računalo nije toliko pametan.
To će se pogledati ovdje i ovdje i ovdje,
ali ako je ono što se traži je najmanji element,
vi samo znate da ste pronašli najmanji element po tome što reći? Nakon što ste na kraju.
No, u tom trenutku, da ste samo našli trenutno najmanji element.
Vi ne nužno znati ništa drugo o stanju u svijetu.
Dakle, morate ići opet i opet i opet.
>> Dakle, ovaj put sam stvarno izgleda glupo jer sam provjeru, ok, dvije, ti si najmanji,
ali ne znam da je u ukupno gostiju.
3, 4, 5, 6, 7, 8. Dobro, dobro. 2 je doista najmanji.
Sada ćemo pronaći sljedeći najmanji. Ok.
3, ti si trenutno najmanji. Idemo vidjeti. 4, 5, 6, 7, 8. Ok, posrećilo opet.
3 je doista na pravom mjestu. Ali ja ću zadržati to opet i opet i opet.
Kako možemo učiniti ikada tako nešto bolje?
Umjesto da ljudi balon se pojava udvojenih od najmanjih do najvećih
i umjesto da ide natrag i naprijed kroz popisu se odabire onda najmanji osobu,
zašto ne bismo umjesto umetnuti te ljude u novi popis korak po korak?
Pokušajmo ovo. Sada me zovu ovu vrstu stvar umetanja.
Dakle, ovdje smo ovdje. Broj jedan. Ja ne brinuti se o bilo tko drugi u ovom popisu.
Moj cilj sada je pravo staviti broj jedan na početku sortirane liste.
I ja ću predložiti jer imam samo 8 komade memorije,
samovoljno upravo sada sam zid između moje navodno nerazvrstani popisu,
i svatko tko je iza mene ću tvrditi je riješeno.
Tako sada imamo broj jedan.
Želim ga umetnuti u mom sortirani popisu, tako da sam samo ću premjestiti moj zid ovamo,
i sada tvrdim ovaj popis sortira, ovaj popis je nesortirani - barem koliko ja znam.
Ja ne mogu vidjeti sve brojeve odjednom.
>> Sada sam se dogoditi da naiđete broj dva. Što da radim s njim?
Ja vam umetnuti sada u sortirani popis. Ali primijetite kako je lako.
Imam samo gledati. Broj jedan je tamo. Oh, očito dva odlazi na strani broj 1.
Sada što da radim sa 3? Ja vas umetnuti u sortirani popis. Ali to je bilo super jednostavno.
Ovo je super jednostavno, ovo je super jednostavno, ovo je super jednostavno, super jednostavno, super jednostavno.
I sada je sve razvrstani iza mene, i koliko koraka nije to trajati?
[Studenti] N. >> Dakle, to je samo n. Imali smo sreće.
To je bio samo n zašto? >> [Student] Zato je popis sortiran.
Popis je već riješeno. Dakle, mi se posrećilo.
Ali smo osmislili algoritam ovaj put da harnesses takvu sreću,
koji najbolje scenarij, a ne gubit vrijeme nepotrebno.
Tako sada imamo ono što ćemo nazvati balon vrste
gdje su ljudi vrsta balona do pairwise.
Mi sada imamo izbor vrsta gdje smo iščupati najmanji osobu iznova i iznova.
I sada imamo unosa vrsta gdje smo vrsta proaktivno staviti ljude kojima oni pripadaju
u sve sortirane liste.
Ako smo mogli, aplauz za ove dečke ovdje. [Pljesak]
Uzmimo naš 5-minutni predah ovdje.
A kad smo se vratiti, mi ćemo odsvirati svih tih algoritama iz vode
s nečim boljim. U redu. Hvala vam puno. Možete zadržati one kao suvenire.
U redu. Mi smo natrag.
>> I da podsjetimo jako brzo, imali smo ove tri različite pristupe sortiranje,
cijela točka koja je bila doći do točke gdje netko poput Alexa
mogao tražiti popis brojeva brže nego nekoga poput Seana mogao.
I iako imamo takve jednostavne primjere s osam brojeva,
mogli izvesti lako do 8 web stranica, 8000000000 web stranicama,
ili 800 milijuna prijatelja na Facebooku.
Dakle, ovi algoritmi svakako može skalirati na one vrste vrijednosti,
i ideje su u konačnici isti.
Dakle, balon vrsta je bila prva gdje smo vrsta bubbled do najveće osobu
skroz desno zamjene ljude pojava udvojenih.
Tada smo imali ono što ćemo nazvati odabira vrste gdje sam malo više namjerno
zadržao gledajući kroz popis, odabirom najmanji broj opet i opet i opet,
logična posljedica kojih je da je popis na kraju je riješeno.
Onda je u trećem jednom, ja umetnuta ljude u njihovom odgovarajućem mjestu,
i nismo jako neprirodan primjer, da je popis već sortiran,
ali to je bilo poslati poruku da se u Insertion Poredaj slučaju,
možete dobiti sretan.
Ako su brojevi već su razvrstani, samo će vas odvesti n korake kako bi potvrdili koliko,
dok odabira vrste si malo više tunel vizija
i da nikada ne shvate da je popis već riješeno.
Tako ćemo vidjeti mjehurić vrsta u akciji ovdje.
U sljedećem primjeru, mi smo o tome vidjeti okomite pruge
čije visine predstavljaju brojeve, tako da možemo izdvojiti od zamišljati sortiranje dogoditi.
Manji bar, manji broj, to je veći bar, veći broj.
>> A mi ćemo ga igrati na tu zadanu brzinu.
To se događa da se presele malo brzo, za sada, ali crveno je ono što se pokazuje dva bara
se u usporedbi rame uz rame.
A ako ste gledati usko, što se događa je da ako se barovi su od reda,
manji jedan dobiva preselio na lijevo, veću jednog s desne strane,
i onda držati napreduje.
Dakle, ako smo to učiniti opet i opet, primijetiti da najmanji barovi
će zadržati skroz svoj put do lijeve
i najveći barovi će zadržati skroz svoj put na desnoj strani.
I doista, mi smo početkom vidjeti uzorak skroz na desnoj strani
baš kao što smo vidjeli 8 i onda na kraju sedam bubbling do samom kraju našeg ljudskog liste.
Dakle, to će se vrlo brzo dobiti malo zamorno, pa neka me zaustavi na trenutak.
Dopustite mi da promijenite brzinu da će biti puno brži.
Ja ne mijenja algoritam, ja sam samo izradu animacija dogoditi brže.
Ipak bubble sorta, isti algoritam,
ali sada možete vidjeti mnogo brže nego naše verbalne demonstracije
da je najveći elementi uistinu bubbling do vrha.
>> Kao na stranu, ovi mali trgovi na dnu lijevo i dolje desno
samo su mali podsjetnici što bi koliko usporedbe radite.
Ali za sada, možemo se fokusirati na piramidi da je uzimanje oblik, i tamo to ide.
Najmanji element koji je na lijevoj strani, najvećem na desnoj strani, a sve ostalo između.
Sada ćemo umjesto pogledati odabira vrste.
Ja ću ići naprijed i udario Stop. Mi ćemo dobiti novi slučajni niz barova.
Izbor vrsta, podsjetimo, ide kroz popis opet i opet i opet,
čupanje najmanji element. Dakle, ovdje je izbor vrsta.
To izgleda kao da je manje posla događa sada, jer nismo uspoređujući pairwise
ali mi smo samo sortirati od višnje branje najmanji elemente s desna na lijevo.
To je vrlo malo vremena, tako da je dihotomija već.
Samo zato algoritam je rekao da se n kvadratna vremena, kao mjehurić vrste
i kao što je izbor vrste, one su stvarno najgorem slučaju trčanje puta.
Na primjer, u slučaju, recimo, odabir vrsta,
Ja sam zapravo odabirom najmanji osobu i stavljajući ga ili nju ovdje,
onda ću to opet, onda ću to opet,
ali tu je bio blagi optimizacija sam mogao napraviti.
>> Čim sam se preselio broj jedan ovdje - Sammy u tom slučaju -
ono što sam trebate učiniti s njim nakon toga? >> [Student] Ostavite ga.
Pustite ga, zar ne? Ništa.
Nisam trebate ikada razgovarati Sammy ponovno jer ako sam odabrao najmanji element
i staviti ga ovdje, zašto gubiti vrijeme ide do kraja cijeli moj popis?
Na sljedećoj iteraciji neka mi zapravo kretati samo na broj 2, samo na broju tri.
Dakle, u stvarnosti, nisam radila n stvari n puta.
Radim n stvari, onda n - 1 stvari, onda n - 2 stvari, onda n - 3 stvari,
zatim n - 4, točka, točka, točka.
Imamo malo geometrijskog niza, što samo znači
ste zbrajanjem progresivno manje brojeve.
Ne n + n + n + n, ali n + 7 + 6 + 5 + 4 + 3 + 2 + 1.
A što da uglavnom radi se da se -
Idem nered gore moj brodu ovdje samo na trenutak -
koji će raditi da se nešto poput n (n - 1) / 2
ako smo samo vrsta izgled na leđima matematike knjige, gdje imate sve Šalabahteri
za formule.
Ako ste samo dodao nešto n + n - 1 + n - 2, to radi da se nešto ovako.
A ako mi samo vrsta pomnožite ovo, da je n kvadrat minus n / 2.
Ja stalno ponavljala n kvadratna, ipak, i to je zato što sam bio vrsta uzimanje mentalni prečac
jer u stvarnosti, n kvadrat minus n dijeli dva je doista istina broj koraka
da algoritam poput odabira vrste bi se, ako mi stvarno broje do
sve te usporedbe i sve malo zauzet radom smo radili.
Ali iskreno, jednom n dobiva se kao milijun ili milijardu, koji je pakao brine
ako radite milijarde kvadratnih minus milijardu podijeljenih po dva?
Milijardi kvadratna je ogroman broj.
Možete uzeti drugi milijardi izvan nje s - n. To nije tako velika stvar.
Dakle, veći su brojevi dobili, manje važni ove niže naredio uvjeti.
Koga briga ako podijelite dva ako govorimo o quadrillions prema broju koraka?
>> Dakle, u cjelini, računalni znanstvenici imaju tendenciju da bacaju sve, ali najveći termin,
a mi samo vrsta pojednostaviti svijet i reći da je algoritam
uzeo otprilike n kvadratna korake. To je trčanje vrijeme algoritma.
Dakle, vratit ćemo se na to samo trenutak s nekim konkretnim primjerima,
ali za sada, to je vrsta intuitivnog motivacije iza samo pojednostavljivanja naš svijet
i govori o najvažnijim terminima nego uzimajući u svim tim fantazija formulama.
Tako da je izbor vrsta, a dobili smo malo sreće tamo.
Pogledajmo unosa vrste. Dopustite mi ići naprijed i početi ovaj jedan kao dobro.
Sada primijetite uzorak koji se događa je malo drugačiji,
i počeli smo sa slučajnim brojevima,
ali ako mi zapravo brojati do broja koraka u najgorem slučaju,
ako je popis započeo potpuno u pravom redoslijedu,
možemo samo bi n korake kako bi shvatili koliko.
>> Ali ako popis su zapravo unatrag - na primjer, u ovom slučaju ovdje -
onda primijetite da zapravo morati učiniti puno više posla u ovom slučaju.
I to bi trebalo nekako osjećam da vam se sviđa ova je vrsta radnog teže
da se one manje elemente s lijeve strane, a to je zato što smo nesretni.
Popis je sortiran slučajno u obrnutom smjeru.
Nasuprot tome, s ugradnjom vrste ako mi oponašaju ono što smo učinili s našim ljudima ovdje
počevši sa svima poredani i onda početi, to je prilično dobar algoritam, zar ne?
To je već, u stvari, razvrstani.
Tako ćemo pokušati sažeti točno koliko vremena te stvari uzimaju nam
uvođenjem samo malo žargon ili zapis koji je zapravo puno jednostavnije
od fanciness vrsta sugerira.
To je stvar ovdje, ovaj veliki O na ekranu, što je računalni znanstvenik uglavnom će koristiti
opisati najgorem slučaju trčanje vrijeme algoritma.
>> Opet, po najgorem slučaju, to je potpuno ovisna o kontekstu.
Što mi znači najgorem slučaju potpuno varira ovisno o problemu govorimo o tome.
No, u slučaju razvrstavanja, što je najgori mogući scenarij?
Sve je unatrag, jer to samo osjeća kao da znači puno posla za nas.
Ja sam zapisao nekoliko algoritama koji smo vidjeli do sada:
linearno pretraživanje, binarno pretraživanje kao s telefonskom imeniku ili komadića papira,
zatim balon vrsta, izbor vrsta i umetanje vrsta kao što smo vidjeli s našim ljudima,
i onda jedan drugi koji je na kraju će biti pozvani spojiti vrsta.
Dakle, u linearnom potrage u najgorem slučaju, koliko koraka je potrebno pronaći broj 7
ako postoji n vrata poput Seana suočeni? >> [Student] N.
N. Tako ćemo pisati veliki O od n.
Samo ću ispuniti u nekim praznine. Ovo je samo mreža praznine.
No, u najboljem slučaju s linearnim pretraživanje, 7 možda su na samom početku popisa,
i Sean možda su počeli u potrazi na početku popisa.
Dakle, ako ste koristeći linearnu pretraživanje i samo provjeri s lijeva na desno ili možda s desna na lijevo -
oni su ekvivalent - u najboljem slučaju koliko koraka možda linearno pretraživanje,
kao Sean algoritma, poduzeti? Samo jedan korak.
>> Dakle, ja ću reći da je omega zapis.
Ovo je samo kapital omega.
Omega je samo seksi način govoreći najboljem slučaju prikazivati ​​vrijeme.
Dakle, u najboljem slučaju, trajanje je jedan korak ili konstantna broj koraka -
1 u ovom slučaju - ali u najgorem slučaju, veliki O, to je zapravo n koraka.
A ovaj ovdje, theta, mi zapravo ne ide pogledati upravo sada.
To nije relevantno za ovaj primjer.
Ali sada pokušajmo binarnog pretraživanja.
U najgorem slučaju s binarnom potrazi, koliko koraka se to događa da se pronaći broj 7
ili što god smo u potrazi za? >> [Student] Prijava n.
Ipak ću uzeti log n, jer baš kao i Alex dobio nesretni
kad smo stvarno radili kroz problem metodički
a ona nije našao broj 7 do posljednjeg vrata Gledala,
iako, u pravednosti, ona je dobio baciti određene vrata na putu,
binarno pretraživanje u najgorem slučaju ima trajanje od log n.
I opet, da govori ova dijeljenjem i osvaja.
Ali što u najboljem slučaju?
A Alex je zapravo doživio taj najboljem slučaju u pravu kada je došla na pozornicu.
Koliko koraka je da se u binarnom potrazi? >> [Student] 1.
1, samo zato što se posrećilo.
Ali to je u redu, jer omega odnosi na najboljem slučaju scenarija,
najboljem slučaju ulaza, čak i ako je samo slučajna glupi sreće.
>> Sada, ovo je previše idemo samo vrsta ostavite prazno za sada.
Kako je sada mjehurić vrsta?
U najgorem slučaju s bubble sort, svatko je u obrnutom redoslijedu,
tako da moramo učiniti puno mjehurića.
No, koliko koraka je da će se u najgorem slučaju? >> [Student] N kvadrat.
To je bio n na kvadrat, jer ako mislite o tome,
ako je popis u potpunosti unatrag - 8 je ovdje, jedan je ovdje -
kao stvar početi mjehur, broj 8 je idući u premjestiti na ovaj način, ovaj put,
na taj način, na taj način, ali gdje je broj 7 u najgorem slučaju?
Ovdje je još uvijek tamo. Dakle, moramo to učiniti opet i opet.
A to je gdje smo dobili n koraka, a zatim n - 1 koraka, a zatim n - 2 koraka.
A ako se uzme moju riječ za to - da, ako vrsta umnožiti se,
to grubo je n kvadrat na kraju s nekim drugim uvjetima koje ćemo samo ignorirati za sada -
onda u najgorem slučaju mjehurića kakve je n kvadratna, dati ili uzeti.
No, što o najboljem slučaju s mjehurićima vrste?
Koji je najbolji mogući scenarij? Sve od brojeva su razvrstani već.
A što je heuristička sam koristio, trik sam koristio,
shvatiti da sam učinio nikakav posao te bi stoga mogla zaustaviti rano?
[Student] Ček jednom. >> Ga Provjerite jednom. No, ono što je sam događaj na putu?
Bio sam praćenje koliko swaps sam napravio.
I shvatio sam da nisam broje nikakve zamjene na prstima, onda sam učinio nikakav posao.
Ja sigurno ne bi trebali pokušati raditi nikakva posla opet, tako da sam samo mogu zaustaviti.
>> Dakle, u najboljem slučaju bubble vrste kada je popis već sortiran,
što će vam reći Omega zapis, najbolji slučaj prikazivati ​​vrijeme?
To je samo n. Moramo napraviti neki posao, ali imamo samo učiniti jedan šetati vrijedi rada.
I ovdje ću ostaviti ovaj dio prazan.
I sada izbor vrsta.
Izbor vrsta su me čupanjem najmanji osobu iznova i iznova.
I što smo rekli prikazivati ​​vrijeme to bio?
To je bio n kvadrat u najgorem slučaju.
I, nažalost, u najboljem slučaju to je također n kvadratna
jer nemam svojevrsnu sveznajućeg pogledom na cijeli svijet;
Znam samo na punom iteraciji da sam doista našli najmanji osobu.
Dakle, izbor vrsta vrsta sranje u tom smislu,
ali naopako je da je to vrsta intuitivno.
To je prilično lako kodirati gore, jer sve što morate učiniti je napisati nekoliko ugniježđena za petlje,
obično, koja prolazi kroz potrazi za najmanji element
a zatim stavlja najmanji element gdje pripada na kraju popisa.
Dakle, ni tu će biti trade-off.
Iznos od vremena koje je potrebno da mislite i da se zapravo razviti nešto pisanjem koda
mogao vrlo dobro uzeti više vremena ako želite bolji algoritam i brže performanse.
>> Ali ako doista samo vrsta koda nešto brzo i prljavo
i samo vrsta uzeti najgluplji mogući ideju možete sjetiti,
koja bi mogla odvesti nekoliko minuta koda, ali s velikim skupovima podataka
vaš algoritam bi moglo potrajati satima pokrenuti.
I čak sam u dodiplomskoj školi ponekad bi ove ustupke.
To bi bilo 03:00, bio sam pokušava analizirati neke vrlo veliki skup podataka
odnose na sigurnost istraživanja radim, i to bilo je provesti pet minuta
prilagoditi svoj program za analizu podataka i ići na spavanje
ili provesti osam sati uzimajući ga samo pravo, tako da radi odmah, a ne ići na spavanje.
I tako tamo to je vrsta svjesne odluke.
Manje vrijeme razvoja, više sna.
U retrospektivi, ja vjerojatno ne bi trebalo poticati da
kada je cilj je da se ovdje optimizirati kvalitetu kodeksa,
ali da je u stvarnom svijetu je vrlo razuman kompromis.
Manje vremena, manje performanse ili obrnuto.
Dakle, ovdje smo konačno dobili priliku za razgovor o theta.
Theta zapis je nešto računalni znanstvenici mogu dovesti u razgovoru
kada veliki O i omega dogoditi da bude isti.
Kažeš theta stvarno poslati poruku da je to vrsta čvrsto vezan.
Bez obzira da li je scenarij dobar ili loš, to je n kvadratna.
Dakle, to jednostavno nije relevantno u ovim pričama ovdje.
Ubacivanje vrsta je posljednji smo gledali,
gdje sam bio samo umetanjem svima na pravom mjestu.
U najboljem slučaju ono što je trčanje vrijeme unosa vrste kao što smo vidjeli ovdje?
[Student] najboljem slučaju? >> Najboljem slučaju.
>> To je n, jer u najboljem slučaju svi poredani,
i Sammy i nitko drugi stvarno morao premjestiti na sve.
Oni su već u svoje pravo mjesto.
Dakle umetanja vrsta u najboljem slučaju, u ovom slučaju, n.
No, u najgorem slučaju to je vrsta n kvadratna. Zašto?
Ako moj popis ljudi je u obrnutom redoslijedu,
Prvi put sam početi s brojem 8, a ja mu umetnuti ili ju u pravilnom položaju, što je upravo ovdje.
Nekako mi premjestiti na strani. Ovi momci su nesortirani, on ili ona je riješeno.
Ali sada sam se dogoditi da vam tko sljedeći? >> [Student] 7.
7 u najgorem slučaju, jer je to u obrnutom redoslijedu.
>> Dakle, ovdje je sedam. Odakle 7 pripadaju? Definitivno iza mene.
Ali sada 7 zapravo ne pripada odmah iza mene, ali iza broja 8,
pa moram reći: "Oprosti, broj 8, može li molim vas premjestiti na ovaj način
"Kako bi napravili mjesta za sedam?" Sada sam susret 6.
"Oh, oprostite, broj 8 i broj 7, možete premjestiti kako bi napravili mjesta za šest?"
Dakle, drugim riječima, s ugradnjom vrste, iako ja ne radim puno kretanja,
ljudi iza mene rade puno više posla, te da je dobio koštati netko vrijeme.
To će koštati računalo vrijeme.
Dakle, u slučaju unosa vrsta još uvijek pate.
Ako počnete zbrajanjem ukupnog broja koraka, mi završiti udarajući grubo n kvadratna
jer ti dečki moraju napraviti mjesta za ljudsko biti umetnuta natrag u tom popisu.
I tako, u ovom slučaju theta je samo ne odnosi se na određenu priču pri ruci.
To je sve lijepo i dobro. Imamo ove tri različite načine govore o trajanju.
No, što to zapravo znači u stvarnom smislu, ako smo zapravo pokušati kodirati do algoritam?
>> Dopustite mi predložiti da postoji još bolji algoritam vani
da sama ima neke ustupke.
Mi ćemo ga nazvati spojiti vrsta, a to je vrsta ovog čarobnog algoritma
samo da radi brže nekako, i to je tako lako izraziti, barem u pseudocode.
Provedba ove vrste algoritma spajanja će biti kao što slijedi.
Kada si dao n elemenata - N brojeva, n ljude, bez obzira na - prvi postoji razum ček.
Ako je n manji od 2, spajanje vrsta samo zaustavlja. To vraća, da se tako izrazim.
Zašto bi se zaustaviti ako je n manje od dva? >> [Nečujno učenik odgovor]
Točno. I opet, n nije broj na popisu, n je veličina popisa.
Ako je n manji od 2, to znači da je popis ili 1,
gdje se očito ste razvrstani ako je jedan broj,
ili 0, u kojem slučaju nema ništa za sortiranje,
tako da ćemo morati ovu vrstu baze slučaju.
Ako popis je tako kratko da postoji samo ništa učiniti, doslovno ne rade ništa. Povratak.
Inače sortirati lijevu polovicu elemenata, a zatim sortirati desnu polovicu elemenata,
onda spojiti dvije sortirane polovice.
>> Ova vrsta se čini kao malo varati pri čemu te pitam kako sortirati elemente
i ti si mi reći, "Sortirajte lijevu polovicu, sortirati desnu polovicu."
Ja sam kao, "sve u redu. Kako sortirati lijevu polovine?"
"Sortirajte lijevu polovicu lijeve polovice, sortirati desnu polovicu lijeve polovice, a zatim učinio."
Vi ste vrsta ciklički definiranje što to znači za sortiranje,
ali ispada da je zapravo sjajan u ovom slučaju.
To nije doista to začarani krug koji nikada ne prestaje
jer to ne prestaje kada? >> [Student] Kada dođete do 1 stvar.
Kada dođete do 1 stvar.
Dakle, iako ste mogli početi s osam ljudi, a ja kažem, "Sortirajte lijevu polovicu tih ljudi,
ove četiri osobe ", onda ja kažem," Kako sortirati lijevu polovine? "
"Pa, sortirati 2 ljudi ovdje." A onda ste poput, "U redu, u redu."
"Kako sortirati lijevu polovicu tih ljudi?"
"Samo sortirati ovo jedna osoba ovdje." Što je briljantan otkrivenje sada?
Moram izdvojiti jednog čovjeka. Gotovo. Ja ne moram ništa raditi.
Ali sada moram sortirati tu osobu, ali oni su jedna osoba, ništa učiniti.
>> Dakle, očito je magija u ovom trećem koraku: spajanje sortirane polovice.
Dakle spojiti vrsta traje ovaj sjajan uvid da ako break veliki problem dolje
u dvije manje, identično veličine problema
a zatim samo vrsta ljepila manji rješenja zajedno na kraju,
Ja predlažem da možemo učiniti mnogo, mnogo bolje [kuckanje zvuk]
od bilo kakve odabira ili unosa vrste.
Ja sam zapravo bio ignorirajući da je za pola sata, ali ja stvarno ne znam što se događa
izvan danas. [Whirring zvuk] [smijeh]
Dakle, neka je vidjeti ako možemo vidjeti ovaj uz malu pomoć od našeg prijatelja Rob Bowden.
Postoje dvije velike korake u procesu spajanja vrste.
Prvo, kontinuirano podijeliti popis šalice na polovice
dok imamo hrpu liste sa samo jednom šalicom u njima.
Ne brinite ako popis sadrži neparan broj
i ne možete napraviti savršeno čisti rez između njih.
Samo proizvoljno odabrati koji popis uključiti dodatni šalicu u.
Tako ćemo podijeliti ove liste.
Sada imamo dvije liste.
Sada imamo četiri liste.
Sada imamo osam liste s jednom šalicom u svakom popisu.
Dakle, to je to za 1. koraku.
Za korak dva smo puta spojiti parove popisima pomoću spajanja algoritam smo naučili prije.
Stapanje 108 i 15 smo završili s popisa 15, 108.
Stapanje 50 i 4 smo završili s 4, 50.
Spajanje 8 i 42 smo završili s osam, 42.
A spajanjem 23 i 16 smo završili s 16, 23.
Sada svi naši popisi su veličine dva.
Primijetite da svaka od 4 lista je sortiran,
tako da možemo početi spajanjem parova popisima ponovno.
Stapanje 15 i 108 i 4 i 50 smo prvi uzeti 4, zatim 15,
zatim 50, a zatim 108.
Spajanje 8, 42 i 16, 23 mi prvo uzeti 8, zatim 16,
zatim 23, a zatim 42.
Tako sada imamo samo dvije liste veličine 4, od kojih je svaki razvrstani.
Dakle, sada smo spojiti ove dvije liste.
Prvo smo uzeti 4, onda uzmemo 8, onda mi se 15
i 16 i 23 i 42 i 50 i 108.
I mi smo gotovi. Mi sada imamo sortirani popis.
>> Rob je vrsta iskorištavanjem nešto što još nismo učinili.
To je bio predložen, ali mi nije zapravo to učiniti.
On je radio nešto fizički sa šalicama koja sugerira
on je proveo neko resurs osim vremena. >> [Student] Space. >> To je bio prostor.
Činjenica da je imao ovu vrstu dvorazinskog stola gdje je imao prostora ovdje
i prostor ovdje je zapravo implicira da je on pomoću dvostruko puno prostora
kao i bilo koji od naših algoritama dosad - umetanje vrsta, balon sortiranje ili odabir vrsta -
ali on je uložio ovaj dodatni prostor za takve stvari se preseliti natrag i naprijed
dok je čuvanje stvari u red.
I iako se osjeća kao da smo došli do sortirani popis, da se osjećao kao da je neko vrijeme.
U stvarnosti, ono što je Rob bio događaj bio upravo ovaj algoritam.
On je prvi uzeo problem veličine n, podijeljen u lijevoj polovici i desne polovine.
To je kada je preselio u čaše. Zatim je ponovio taj proces.
On je podijeljen u četiri dva seta dva ovamo i ovamo.
Zatim je ponovio taj proces i podijeliti dva u dva seta jedan za svaki od tih različitih šalica.
A to je gdje je briljantan ukaže prilika.
U tom trenutku u priči, Rob je imao osam popise veličine 1,
svi koji su razvrstani već.
>> Pa što onda je on nastaviti raditi?
Parne uzeo ovu sortirani popis i ovaj sortirani popis te ih spojio.
Zatim je uzeo ovaj jedan, te ih spojio, onda je ovo jedan te ih spojio,
onda je to jedno te ih spojio.
A onda ono što je on učinio sljedeći?
On je tada ponovno spojio veće popise, a zatim ponovno spojio veće popise.
A ako mislite o tome samo intuitivno, za sada, što je on zapravo radi?
On je dijeljenjem problem na pola, na pola, na pola, na pola
kako bi se ove super male liste.
Tada je vrsta kombiniranja dvokrevetna, dupli, dvokrevetna, dupli.
Tako je radio duplo više rada, kao što smo vidjeli dosad
s bilo koje uključuju podijeli pa vladaj, ali nije velika stvar.
Dva puta koliko je rad nije tako velika stvar. To je samo konstantan faktor.
I baš kao i naše aritmetičkog izraza prije, ja samo idem prijeći iz stalne čimbenike
poput puta dva. Koga briga? Ako je 2 milijarde puta dva, to je još uvijek puno koraka.
Dakle, ovo spajanje korak čini se da je ključni uvid.
Idemo prošetati kroz ovo samo brojčano prije - Oh, to je ne biti nastavljen još.
Idemo prošetati kroz ovu numerički samo zapravo vidjeti kako se to igra.
To je uglavnom samo malo jadnog čovjeka animacija.
Hajdemo predložiti ovo.
Trčanje vrijeme spajanja vrste - samo trebamo način govori o tome.
Ovo nije matematika, to je samo vrsta jezgrovit način izražavanja sebe.
Dakle, T predstavlja vrijeme i n predstavlja što? >> [Student] veličina -
>> [Malan] veličina problema, broj ljudi.
Tako sam tvrdeći da trčanje vrijeme za sortiranje n ljudi će biti 0 iznos od vrijeme
ako je n manje od dva, jer ako imate jedan pehar ili nema kupova, nemate ništa za sortiranje.
Ali općenito, ja ću predložiti da trčanje vrijeme za sortiranje n elemenata
će biti vrijeme koje je potrebno za sortiranje lijevu polovina plus Desna polovina
plus - što je to dodatni + n? >> [Student] Spajanje vrsta.
[Malan] To je zapravo spajanje, jer ako imate N / 2 elemenata ovdje
i imate N / 2 elemenata ovdje, koliko vremena je potrebno da ih spojiti?
Baš kao i Rob, morate iščupati ovo ovamo, možda kidati ovamo,
kidati ovamo, kidati ovamo, kidati ovamo.
Morate dodirnuti svaki od šalice jednom.
A ako ima 4 šalice plus četiri šalice, to je 8 šalice
ili, općenitije, 8 n šalice.
Dakle, spajanjem korak možemo izraziti kao n,
i da doslovno uključuje nekoliko puta Rob fizički dotaknuo
jedan od onih stiropor čaše.
Dakle, ajmo sad napraviti proizvoljan primjer.
Ako postoji 16 šalice, što je trčanje vrijeme sortiranja, pomoću Rob je algoritam, 16 šalice?
To je dva puta iznos od vrijeme potrebno za sortiranje 8 šalice
jer imamo 8 šalice ovdje, 8 šalice ovdje.
Ne znam koliko dugo da traje, tako da smo ga generaliziranja kao T za trenutak.
Tko zna što je to?
Ali sada mogu sortirati od rekurzivno ili više puta pitati isto pitanje.
Koliko vremena je potrebno izdvojiti osam šalica?
8 šalice idem reći uzima iznos od vrijeme potrebno za sortiranje 4 šalice plus četiri čaše,
zatim ih spajanja.
Fine. Mi smo ušli u ciklusu već. Koliko dugo je potrebno za sortiranje 4 šalice?
Vrijeme koje je potrebno izdvojiti četiri šalice je 2 šalice plus 2 šalice sortiranje plus spajanjem proces.
Fine. Koliko dugo je potrebno za sortiranje dvije čaše?
2 šalice je iznos od vrijeme potrebno za sortiranje 1 šalicu plus vrijeme koje je potrebno riješiti još jednu šalicu
plus iznos od vrijeme potrebno za spajanje, što je samo dvije.
>> Fine. Zadnje pitanje. Koliko dugo je potrebno za sortiranje 1 šalicu?
Ovdje je osnovni slučaj da smo predviđali da ćemo pogoditi ranije.
Činjenica da je potrebno ne rade uopće sortirati najmanji od problema
znači da je sada, vrsta razreda škole stilu,
možemo ići započeti uključivanjem ove brojeve natrag u.
Mi sada znamo što T 1. je, tako da ja mogu priključiti 0 za T iz jedne.
To će mi dati odgovor na T iz dva, što sam onda možete priključiti u viši.
To će mi dati t 4, što ja mogu priključiti u viši.
To će mi dati t 8, što ja mogu priključiti u viši.
A ako ja zapravo radim na to da matematiku uključivanjem u tim odgovorima,
I onda se T od 16 je 64.
A što predstavlja 64?
Ako je T 16, yeah, to je 16 puta četiri.
Dakle, ja tvrdim da sada prikazivati ​​vrijeme ovu stvar zove spojiti vrsta -
i to će biti fanciest od onih koje smo vidjeli dosad -
će se zvati n log n
jer koliko puta možete Rob podijeliti hrpu šalica u poluvremenu? Prijavite n.
To je isto kao npr. telefonskog imenika, to je isto kao self-prebrojavanja primjer.
>> Koliko puta možete podijeliti nešto na pola?
Međutim, tu je ovo spajanje korak.
Možda ćete morati podijeliti čaše na pola opet i opet i opet,
ali svaki put ćete morati spojiti.
I što smo ranije rekli da spajanjem n šalice traje n koraka
jer morate iščupati šalicu, iskopaj šalicu, a vi morate dotaknuti svaku šalicu jednom,
baš kao i Rob učinio.
Dakle, ako radimo nešto dnevnik n puta i radimo n stvari na svakom od tih iteracija,
svaki od tih halvings, imamo n puta log n.
Dakle, ako smo priključiti 16 u ovom primjeru, 16 puta prijaviti od 16. -
Ne brinite o tome zašto je to slučaj za sada, jer nisam privukao bazu -
ali log bazu 2. 16 je 4, 16 puta 4 je 64.
No, s druge strane, ako smo imali koristi mjehurić vrsta ili odabir sortiranja ili umetanje sortiranje s 16 brojeva,
što bi trajanje bilo, ako je n 16?
To će biti 16 kvadratna, što je 256, što je čak i ako niste sasvim slijedio sve matematiku,
256 je veća od 64. To je stvarno čarobna takeaway ovdje.
I shvatili da rade kroz to u manjim primjerima kao što će na pset
sve to čini puno više intuitivno.
No, što to zapravo znači u smislu dojam ovog algoritma je ovo:
Ako pogledamo spajanja sortiraj ovdje - neka mi ga podići u ovom prozoru ovdje -
ovo je malo drugačiji primjer gdje imamo sve tri od tih algoritama -
balon, izbor, i spajanje - samo rame uz rame.
>> Oni su svi počeli sa slučajnim rešetaka, i to je dobro.
Nitko nema temeljnu prednost nad drugima.
Idem u trenutku kliknite svaki od tih animacije - Start, Start, Start -
kao brz kao što sam ja, tako da, otprilike, svi oni početi u isto vrijeme,
i neka je uzeti u obzir da Bubble Sortiraj je gore slučaj prikazivati ​​vrijeme je ono? >> [Student] N kvadrat.
N kvadrat. IZBOR Poredaj najgori slučaj pokrenut je vrijeme? N kvadrat.
I pisma vrsta je očito - čak i ako nije sasvim slijediti sve matematiku sada,
to će postati mnogo više intuitivno vremenom - je, tvrdimo, n puta log n.
I zato log n je strogo manje od n jednom imamo velike brojeve,
n puta log n je manji od n puta n ili n kvadratna.
Dakle, što je to osjećaj da zapravo biti bolji algoritam u smislu trčanje vremena,
n puta log n za razliku n kvadrata? Ovdje ćemo ići. Klik, klik, klik.
>> To je ono što znači da koriste nešto poput spajanja vrste.
Imamo trenutak. Idemo vidjeti što se ovdje događa.
[Nasmijao] Čiji je novac na bubble vrste?
To već ovisi o ulazu ponekad.
Idemo vidjeti.
Hajde. To se osjeća kao da je sustiže. >> [Student] Idi, mjehurić vrsta!
[Studenti mrmljajući]
[Malan] Da, da.
[Studenti mrmljajući] Idi, idi, idi!
[Svi navijaju] [pljesak]
Dakle, sada sa jednom zadnji, konačni demo, ako je malo lukav da zamotate svoj um oko matematike
ili vrsta vizualizacije tamo, zapravo možete čuti brzine
različitih algoritama drugačije.
Ovo je animacija je netko napravio da zapravo suradnici zvuči
s procesom zamjene i visina od barova.
Kao što ćemo vidjeti ovdje, tu je još nekoliko sortiranje algoritmi vani da su ljudi mislili.
Ovaj prvi će biti umetanje vrsta, a to će letjeti kroz
i vam dati zvučni osjećaj kako su ovi raznih algoritama rada.
Ovdje je umetanje vrsta.
[Elektronička bip]
[Malan] Bubble vrsta.
[Brže elektronički bip]
[Malan] Izbor vrsta.
[Brže elektronički bip]
[Malan] Spajanje vrsta.
[Elektronička bip]
[Bip usporava] [smijeh]
[Malan] Gnome vrsta.
[Elektronička bip]
>> Ovo je CS50. Vidimo se sljedeći tjedan. [Pljesak i navijanje]
>> [CS50.TV]