>> [Glazba svira]
>> David J. Malan: U redu.
Dakle, dobrodošao natrag.
Ovo CS50, a je Kraj tjedna tri.
>> Dakle, sjećam se u proteklih nekoliko tjedana, smo provodili dosta
Vrijeme na C, na programiranju, o sintaksi.
I to je sasvim normalno, ako si još uvijek bori s Problem Set 2, kako bi se
lupanje glavom o zid.
To je zagonetan izgleda poruka o pogrešci i greške koje ste
Ne mogu sasvim loviti.
Zato, budite uvjereni, da je u samo nekoliko tjedana da li ću se osvrnuti na
stvari poput Cezara, i [? V-genair,?] možda čak Crack, a
shvatite koliko daleko ste došli u kratkom vremenskom razdoblju.
Dakle, ako je to neka utjeha, drži se za sada.
>> Danas, međutim, možemo početi tranziciju na višu razinu stvari.
I mi početi uzimati zdravo za gotovo da je ti dečki znaju kako programirati, ili na
Najmanje počeci Ta razina.
A počet ćemo razmisliti o tome kako možemo ići o izradi programa više
učinkovito.
Kako možemo ići o optimizaciji Učinkovitost naših algoritama i
općenito rješavanjem više zanimljivi problemi.
I počinju da uzimaju zdravo za gotovo da je, ako smo htjeli, mogli smo kod do bilo
od primjera imamo na umu.
Tako danas, mi ne dirajte tipkovnicu za bilo koji oblik koda.
To će biti puno viša razina, a u konačnici, o rješavanju problema.
>> Dakle, doći do te točke, neka mi predloži da slijedećih sedam
pravokutnici predstavljaju sedam vrata, iza koja se cijela hrpa
brojeva, među kojima je broj 50.
Dopustite mi da ovo projekt na ovu Zaslon i ovdje.
I predložiti da trebamo dobrovoljca u pomoći mi pronaći broj ispred
Internet ovdje vidjeti.
Dođi gore, u ružičastom.
U redu.
Koje je tvoje ime?
>> JENNIFER: [nečujno]
>> David J. Malan: Žao mi?
>> JENNIFER: Jennifer.
>> David J. Malan: Jennifer.
U redu, Jennifer.
Drago mi je.
Dođi gore.
Dakle, to ovdje su sedam vrata, a što Volio bih da to učiniti za nas ovdje,
pred svim svojim kolegama, se nalaze nam broj, 50.
Kako pronaći broj, možete zaviriti iza bilo koji od ovih vrata jednostavnim dodirom
na jednom od vrata, i to će otkriti svoj broj.
I neka je vidjeti kako brzo ste možete nas naći broj, 50.
>> 15.
16.
50.
Lijepo učinili.
U redu.
Aplauz za Jennifer.
>> [PLJESAK]
>> U redu.
Dakle, ono što je vaša strategija za pronalaženje broja, 50?
>> JENNIFER: Hm, mislio sam da možda ako -
[Nečujno]
>> David J. Malan: Oh.
Daj ga jedan drugi.
Tako je vaša strategija za pronalaženje broja, 50?
>> JENNIFER: Pa sam početi na počinju vidjeti što prvi broj
je, a onda sam pomislio, možda, ako oni su razvrstani, ja ću samo držati
prislušni viši?
>> David J. Malan: OK.
I mi se čini da su našli da je to slučaj.
Iako, neka je guliti natrag slojeve Samo malo, a želite ići
naprijed i otkriti druge vrata mogli ste odabrali?
>> JENNIFER: O, Bože.
>> David J. Malan: Ah.
>> JENNIFER: Tako sam se posrećilo.
>> David J. Malan: Znači li se posrećilo.
U redu.
Dakle, nije loše.
No, to je zanimljiva Uvid, zar ne?
Ako ste pretpostavili, a vi je dobiti, Doista, malo sretan tamo.
Ali ako pretpostavlja da su brojevi bili su razvrstani, može li se preciznije
kako to utječe vaše ponašanje?
>> JENNIFER: Pa, ako su razvrstani, sam Mislio najmanjih do najvećih.
>> David J. Malan: OK.
>> JENNIFER: Ili ako je to zavrsilo se stvarno velik, a zatim po veličini na najmanji.
>> David J. Malan: OK.
Dakle, najveće do najmanje, ili Najmanji do najvećeg.
No, dopustite mi predlažemo, pretpostavimo da je dobivši nesretni, a pretpostavljam da su oni
nisu, u stvari, razvrstani, koliko ta vrata možda ste morali zaviriti
iza u tom najgorem slučaju?
>> JENNIFER: Sve od njih.
>> David J. Malan: Sve od njih.
Tako ćemo generalizirati da kao n.
Tu se dogoditi da bude 7, ali neka se više općenito reći postoji n vrata na
Zaslon ovdje.
Dakle, u najgorem slučaju, da bi se gledati iza sedam vrata, ili n vrata.
I tako ovo je stvarno, to je malo Sreća i danas, ali to je stvarno linearno
Algoritam sorti, iako bili vrsta preskakanja okolo.
Je li to pošteno?
>> JENNIFER: Da.
>> David J. Malan: Pa, da vidim ako je vaš strategija mijenja se ako sam pokrenuti da
Naš drugi primjer ovdje s 7 različitih vrata.
Iste brojeve, ali to Vrijeme su razvrstani.
Koja je vaša strategija ovdje će biti, pokušavaju staviti izvan vašeg uma ono
ostali su brojevi -
>> JENNIFER: OK.
>> David J. Malan: - ranije?
>> JENNIFER: Počnimo sa prvom.
>> David J. Malan: U redu.
Počnite s prvom.
4.
Sada, gdje ćete ići, i zašto?
>> JENNIFER: 4 je stvarno mali.
Dakle, ako oni su vrsta možda i najmanji Najveći se, što bi trebao
se dva puta, i -.
>> David J. Malan: OK.
Da vidimo, što mislite?
>> JENNIFER: Pokušajte zadnji.
Nica.
>> David J. Malan: Vrlo lijepo učinio.
U redu.
>> [PLJESAK]
>> David J. Malan: OK.
Dakle, što zapravo radiš strašno, jer si
to radi jako dobro.
Koji nas ostavlja u stanju napraviti određene točke.
Tako ćemo pokušati vratiti ovdje.
>> JENNIFER: OK.
>> David J. Malan: Vrlo dobro učinili, svejedno.
Tako da je počeo od početka, vidjeli ste da je 4, onda
premještena u kraju.
Ali pretpostavimo da nije posreći postoji, i pretpostavimo 50
bio je negdje drugdje.
Koji vam je treći korak bio?
>> JENNIFER: Vratite se na početak.
>> David J. Malan: Vratite na početak.
U redu, tako da bi ste dotaknu ova vrata, što je 8.
U redu.
Dakle, to nije 50.
Gdje bi ste gledali sljedeće?
>> JENNIFER: Ako nisam znaju oni razvrstani.
>> David J. Malan: Točno.
Pa, ako nisi znao su razvrstani -
>> JENNIFER: Oh, znao, da.
>> David J. Malan: - ali nije znam gdje je još 50?
>> JENNIFER: Samo nastavi.
>> David J. Malan: U redu.
OK.
Imajte ide.
OK, da mogu raditi.
>> JENNIFER: OK.
>> David J. Malan: Sada, ako ste samo će zadržati ide, ono što je vaš
Algoritam devolving podlogom u.
>> JENNIFER: linearno -.
>> David J. Malan: To je vrsta linearne.
No, dopustite mi da predloži, neka ja mu na licu mjesta.
Dopustite mi da osvježite stranicu.
Isti broj, isti raspored, ista vrata.
Ali sjetim tog prvog dana u Klasa kad smo poderao telefonski imenik u
polovice, vrsta, a što je Naša strategija postoji?
>> JENNIFER: Start na sredini.
>> David J. Malan: OK.
Dakle, početi na sredini.
Dakle, idemo naprijed i da simuliraju.
Start na sredini, otkrivajući ta vrata.
Dakle, broj 16.
Pa što bi jak čovjek učinio, koji je poderao telefonskog imenika na pola,
doći do sljedeću pogodak?
>> JENNIFER: Idi u ovom polugodištu.
>> David J. Malan: A zašto udesno?
>> JENNIFER: Ako su najmanja vrsta do najvećih, tada 50 bi trebao biti
u tom kraju.
>> David J. Malan: Dobro.
Totalno razumna.
Dakle, poput telefonskog imenika, idete pravo, za razliku od lijevo, ali ovdje
je ključ takeaway.
Sada možete baciti, ili se otkinuti, polovica tog problema, ostavljajući vas ne
sa 7 vrata, ali stvarno sa samo tri.
Koji je otprilike polovica Veličina problema.
U redu.
Pa sad što bi učinjeno nakon što desno?
>> JENNIFER: Dakle, 16 je još uvijek prilično mali, u odnosu na 50, pa možda ću pokušati,
kao što je, ovaj jedan.
>> David J. Malan: U redu.
42.
U redu, tako da sada Koja je tvoja Instinkt ti govori?
>> JENNIFER: Ja mogu baciti to i onda samo -
>> David J. Malan: OK.
Dobro, možete baciti lijeva polovica postoji.
>> JENNIFER: - pokupiti ovaj jedan.
>> David J. Malan: I u pravu.
>> JENNIFER: Da.
>> David J. Malan: Dakle, iako je teško vidjeti možda, kad postoji samo
7 vrata, razmišljati o tome, sada, konzistentnost
Algoritam samo primjenjivati.
U prethodnom slučaju, jesi posreći, što je super.
Ali jesi koristiti heuristički, Ja bih rekao.
Možete koristiti neku vrstu svoje instinkte, a znajući to riješeno, ako je lijepa
mali na početku, očito, mi smo Moram ići više u desno.
No, u nekom smislu, imaš sreće, jer možda je to bio broj 100,
a možda je 50 više u sredini.
Možda je čak 50 ovamo.
>> No, ono što je malo drugačije ovaj put bio, što nije ista stvar
opet i opet.
I ja bih rekao da je ono što ste upravo je, doduše pod utjecajem telefonu
Knjiga primjer, nešto mnogo više algoritamski, i još mnogo
manje posebna proučavao.
Mnogo manje instinktivno.
Dakle, na kraju dana, kako bi se vam opisati učinkovitost
Prvi algoritam, gdje je otišao slijeva nadesno, u odnosu na
Drugi algoritam ovdje?
>> JENNIFER: Ovo treba, kao što je, možda prepoloviti vrijeme, ili čak i više, da.
>> David J. Malan: OK, možda čak i više.
Idemo gurnuti malo teže na to.
Što je stvarno, ako nastavljamo ovaj Logika, svakako prepolovljena
vrijeme rada s ovom drugom algoritma bacajući daleko polovicu
brojeve, ali ono što smo radili na sljedeći iteracija, kada je Jennifer otkrila
drugi broj?
>> Mi prepolovili broj vrata ponovno.
I onda što smo učinili nakon toga, ako je bilo je više vrata da se igraju s?
Mi bi ih prepoloviti, i opet, i opet, i opet.
A to je baš kao i vama svima stojeći u prvom tjednu
klase, polovica što je sjeo, poluvrijeme od vas sjeo, pola tebi
sjeo, dok se jedan usamljeni Duša je stajao.
A mi je rekao da je vrijeme rada da je broj koraka to je bio
po nalogu što?
>> ZVUČNI 1: [nečujno]
>> David J. Malan: Dakle log baze 2 n, ili jednostavno više jednostavno, prijavite n.
Tako nešto logaritamska.
A graf nije bio ravna crta da je upravo dobio gore i gore, bilo je
Ova zanimljiva krivulja koja nije dobiti tako loše tijekom vremena.
Tako ćemo zadržati na ovoj ideji.
Neka je hvala Jennifer.
Hvala što ste došli na gore.
I, jedna sek.
Nema stolne lampe danas, ali mi nemam CS50 stres loptice.
>> JENNIFER: Jupi.
>> David J. Malan: U redu, ovdje.
Hvala izvrgava Stres se ovdje.
U redu.
Dakle, neka je vidjeti ako ne možemo sada formalizirati to malo više.
Pa opet, ono što smo upravo učinio je u biti ista stvar kao što smo učinili
u tom prvom tjednu.
No, umjesto da kraj sa samo linearno algoritam, koji mi je prikazano
prije što je ovaj ravnoj liniji, pri čemu, ako smo stavili još jednu vrata
Zaslon, a zatim bi se Jennifer su morali gledati, potencijalno,
Iza još jednog vrata.
Ako stavimo još dva vrata, ona može imati gledati iza još dva vrata.
>> I tako, bilo je to linearno odnos između veličine
Problem na, recimo, x-osi, a Vrijeme koje je potrebno da
riješiti na y.
Ali slika sam je aludirajući ranije je to zelena linija.
Zelena namjerno, jer to samo osjećao bolje.
U teoriji, algoritam, kad smo to učinili s telefonskom imeniku, kad smo to učinili
s vama računajući jedni druge, i u drugom slučaju, kada je Jennifer samo
Uspjeli ovdje gore, to je neka vrsta od temelja bolje.
Budući da to nije bila samo dva puta brže.
Nije bilo čak četiri puta brže.
To je u potpunosti ovisi o tome što veličina ulaza je, kako mnogi
korake koji je u konačnici uzeo.
>> I tako ova jednostavna ideja da smo svi uzeo zdravo za gotovo s telefonskom imeniku,
može se isto tako primijeniti za ovako nešto.
A to bi moglo biti više ležerno poznat kao, kao što ste mogli
zamislite, podijeli pa vladaj.
Nije za razliku od onoga što smo učinili, naravno, s telefonskom imeniku.
>> Ali pseudocode, podsjetimo, bio je to.
Dakle, nećemo to učiniti opet, ali sjećam da je prvi tjedan, sve nas je ustao
a onda polovica vas sjeo, polovica da sjedne, polovica vas sjeo.
Taj algoritam je implementiran u bitni za varanje način, da je
nije bio samo jedan od mene brojanje, temelja, učinkovitije.
U tom slučaju, bio sam uložio sekundarni izvor.
Na neki način, više procesora, više mozak, više pametnih ljudi u
Soba su mi pomogli doći na nešto linearno na nešto
logaritamska, od nečega red da nešto zeleno.
>> No, u ovom slučaju, Jennifer sami mogu bitno poboljšati
izvedba njezina prvog algoritma strane, opet, samo razmišljam malo teže.
I sada, kada dođe vrijeme za provedbu te stvari, figuring out
ono linija koda možete pisati kao da ih možete ponoviti i
opet, i opet, vrsta u petlje način.
Zato što ne ideš imati luksuz, kao što je Jennifer u početku,
Samo imaju cijelu hrpu oklijevanja i reći, hmm, ako je ovo prvi broj je 4,
neka mi skočiti sve do kraja.
Ooh, ako taj broj je prevelika, dopustite mi da se presele natrag proizvoljno
na drugi element.
Naći ćete da će to biti puno teže formalizirati ono što mi ljudi
uzeti zdravo za gotovo, kao vrlo razuman heuristika, ali računalo je samo
će učiniti ono što vam reći da to učinite.
>> Sada to ima vrlo zanimljiv implikacije.
Ovaj graf je vrsta značilo svojevrsno preplaviti vizualno, ali obavijest, u kojoj
je ravna crta u ovom grafu?
Gdje je linearni graf koje zovemo n?
Pa, to je vrsta prema dnu ove slike, zar ne?
Dakle, sve što smo učinili je da smo vrsta zumirana se na x-osi i
y-os pokušati dobiti osjećaj za ono što druge vrste krivulja izgledati.
>> I specifičnosti matematička Izrazi danas neće biti važno, tako
mnogo, ali primijetiti da postoji puno algoritama koji su daleko lošiji od
nešto što je linearno.
Doista, n kubu izgleda prilično loše.
2 do n izgleda prilično loše. n na kvadrat izgleda prilično loše.
Pa ćemo vidjeti što neki od onih Možda u stvarnosti danas.
I log n ne osjećam tako loše, ali bolje od n je baza 2 log n.
Ali, znate, to bi bilo još više iznenađujuće ako je Jennifer, ili ako smo mi,
da je prvi tjedan, je došao gore sa nešto što je dnevnik log n.
>> Dakle, drugim riječima, postoji cijela ova Raspon mogućih rješenja
problemima, ali čak i ovdje, obavijest što će se dogoditi.
Kad sam udaljavanje, koja je od ovih krivulja će dokazati da bude apsolutna
Najgore od one na zaslonu sada?
Dakle, n kubu izgleda prilično loše u ovom trenutku.
Ali, ako smo smanjili i vidjeti više x i y-os, tko će
dominiraju u konačnici?
Dakle, to je zapravo ispada da se dvije n, a možete to shvatiti samo
uključivanjem u nekim sve veći brojeva, i vidjet ćete da je 2 do
n, dapače, dobiva veći mnogo brže.
Ako smo stvarno smanjivanje, a dvije se n algoritam apsolutno sranje.
Mislim da će ovo potrajati vrlo malo vremena za
Računalo gubitaka kroz.
>> No, vidjet ćete s vremenom, pogotovo budućih problema seta, pa čak i
Konačni projekti, vaši podatci set dobiva veliki, u redu?
Čak iu prvoj verziji Facebooka, kao i broj prijatelja, a
Broj registriranih korisnika dobio veliki, možete sortirati od telefon, i
provesti nešto s linearnim pretraživanje, ili vrlo jednostavan za sortiranje
algoritam, kao što ćemo vidjeti danas.
Morate početi razmišljati teže i teže o tim problemima.
A vrste problema mjestima kao što su Facebook i Google i Microsoft,
i drugi rade na upravo tih vrsta podataka velikom vrstom pitanja
sve više ovih dana.
>> U redu.
Tako Jennifer uspjeh u tom trenutku Algoritam, iskreno, ona je nevjerojatno
i prvi put, ali neka je napisati što se zove sreća, tako da smo
Možete napraviti ovu točku.
U drugom slučaju, ona je iskoristio algoritam koji je ponovio i opet
opet, ali je uzeo zdravo za gotovo sigurno pretpostavka da smo dopustili
joj, ali ona iskorištava neke pojedinosti Drugi put da ona nije imala
prvi put.
Koji je što?
>> Taj popis je riješeno.
Dakle, čim je popis sortiran, mi Jennifer tvrdi da je u mogućnosti to učiniti
bitno bolje.
7 vrata, da, nije li to zanimljivo, , ali ga pretpostavljam da smo 7 milijuna vrata.
Prijavite n definitivno ide obaviti još mnogo, mnogo
brže u dugoj vožnji.
Ali ona je morala imati Vrata sortirani prema njoj.
Sada sam uzeo slobodu da radi Unaprijed na zaslonu računala
ovdje, ali pretpostavljam da je Jennifer to morao sebe?
Pretpostavimo da su vrata u pitanju zastupljeni podaci u bazi podataka, ili
Prijatelji registrirane za Facebook, ili Bilo koje web stranice na internetu koje
razne web stranice možda ćete morati na indeksu ili tražiti više.
>> Pretpostavimo da ste upravo imali sirovih podataka postavljanje i to je lijevo za vas, ili za
Jennifer to učiniti sortiranje?
To je, naprotiv, zahtijeva da smo odgovor Pitanje, dakle, koliko vremena
bi uzeli Jennifer, ili čak i ja, sortirati one brojeve unaprijed, tako
da bi ona mogla iskoristiti to?
Točno?
Zbog implikacija, naravno, ako to traje mi dosta vremena za sortiranje
brojevi, koji su kritički brine da vas Možete naći broj kao 50 tako brzo,
kao u slučaju Jennifer, ako smo više od svladan količinu ukupnog vremena
to je sortiranje stvari unaprijed?
>> Tako ćemo vidjeti, ako ne možemo bojite sliku ovdje.
Imam cijela hrpa više stresa loptice, ako to pomaže
razbiti led ovdje.
A ako ne bi smetalo, mi potrebno sedam volontera -
na, OK.
Wow.
Dakle, mi ne moramo trošiti na stol svjetiljke, čini se.
U redu.
Dakle, o tome vas dvoje ispred.
Kako vam dva dečki u leđa.
Dakle, to je četvrta.
Kako vam se ispred pet, šest i sedam.
Točno tamo.
Vaš prijatelj vas je istaknuo, tako da ćete dobiti nagradu.
>> U redu.
Dođi gore.
A zašto ne bismo imati što dečki dolaze ovamo.
Ja ću vam dati svaki broj.
I ići naprijed i sami organizirati identično onome što je
prikazan na zaslonu.
>> [Pridodati glasovima]
>> David J. Malan: OOP, ispričavam se.
Bug.
U redu.
Pa, ovdje mi ići.
Broj pet.
Broj šest.
Jedan, dva, tri, četiri, pet, šest, sedam.
Oh, ovo je nezgodno.
>> ZVUČNI 2: Ja ću samo dobiti -.
>> David J. Malan: Dobar posao.
U redu.
Hvala na sudjelovanju.
>> [PLJESAK]
>> OK.
U redu.
Dakle, imamo četiri, dva, šest, jedan, tri, sedam, pet.
Usavršiti tako da imamo sedam volontera ovdje koji su jednaki u širini
Niz koju igramo s ranije.
I sam izabrao sedam razloga koja će biti samo
povoljno u malo.
I ja ću predložiti da se prva Mi smo vrsta tih sedam volontera.
Ako želite, prvo, pozdraviti, iako.
Budući da je ovo će biti nespretan nekoliko minuta.
Predstavite sebe.
>> GRACE: Bok, ja sam Grace.
Ja sam student u Leverett House.
>> BRANSON: Hi.
Ja sam Branson.
Ja sam brucoš na vara.
>> Gabe: Hi.
Ja sam Gabe.
Ja sam junior u Cabot.
>> NEIL: Ja sam Neil.
Ja sam brucoš na Matthews.
>> JASON: Ja sam Jason.
Ja sam brucoš na Greenough.
>> MIKE: Ja sam Mike.
Ja sam brucoš na Grays.
>> JESS: Ja sam Jess.
Ja sam student u Leverett.
>> David J. Malan: Izvrsno.
U redu.
Pa, hvala ti za sve naše Volonteri ovdje do sada.
A izazov pri ruci sada ide se riješiti tih dečki, ali onda
ćemo morati razmišljati malo teško o tome kako učinkovito smo zapravo
ih sortirati.
Dakle, neka prvi probati ovaj.
Vi možete vidjeti jedni druge brojeve samo stavljanjem oko uglova.
Idi naprijed i uzeti nekoliko sekundi, a sortiranje sebe na najmanji na
lijevo najveći na desnoj strani.
Idi.
>> OK.
Dobro.
To je stvarno prokleto brzo.
Sada netko ovdje, ono što je algoritam da ti dečki primijeniti?
>> ZVUČNI 1: barem u najvećoj.
>> David J. Malan: OK.
Najmanje se najveća je stvarno svojevrsni Cilj, ali nisam sigurna da je to
Stvarno algoritam.
Najmanje se najveća ne govori ja korak-po-korak što učiniti.
Da?
>> ZVUČNI 1: [nečujno]
>> David J. Malan: OK.
Dakle, ako vidite osobu manji od vaš broj, a zatim premjestiti na
Pravo na njih.
Tako da sada je sve izraženiji, više kao algoritam, jer
mogu reći, ako je to, onda da.
Tako imamo nekakav uvjetni konstrukt.
A ovi momci se činilo da to malo puta, jer su neki od vas preselili malo
od udaljenosti.
Tako da je vjerojatno neka vrsta petlje događa u njihovim glavama.
>> No, pokušajmo se formalizirati to.
Ako ti dečki mogli vratiti natrag na ovom dogovoru.
Idemo vidjeti ako ne možemo formalizirati to pomalo, a onda postaviti pitanje, samo
koliko je učinkovit je ovo?
Naravno, kada smo to učinili sporije, ona će se osjećati kao dobar
algoritam, ali vidjet ćemo možemo li stavimo prste o konkretnim koracima.
>> Pa vas dvojica su četiri i dva.
Ili ste točan ili netočan kako?
Očito pogrešna.
Tako smo zamijenili.
Sada ću se odmaknuti ovdje i reći, četiri do šest.
Jesu li točna ili netočna?
>> Gabe: Točno.
>> David J. Malan: Točno.
Šest i jedan?
Nope.
Zamijeni.
Dakle, to su dvije zamjene.
Šest i tri?
Nope.
Zamijeni.
Šest do sedam?
Izgleda dobro.
Sedam i pet?
>> JESS: [nečujno]
>> David J. Malan: OK, zamijeniti.
I razvrstani.
U redu.
Dakle, očito ne, zar ne?
Tako da je više događa.
Ali, doista, ovi momci, pa čak i Jednostavno instinktivno.
držati se kreće.
Nisu samo zaustaviti, nakon što ispraviti jedan problem.
Dakle.
Doista, ja ću imati učiniti istu stvar.
Ja ću morati izdvojiti od premotati natrag do početka ovog problema,
ili početak te niz ljudi, počnimo ih zovete.
>> I sad ono što bi moj algoritam na drugom prolazu biti?
>> ZVUČNI 1: Ista stvar.
>> David J. Malan: Ista stvar.
A to, ja počinjem se sviđa, zar ne?
Čim možete pronaći sebe radiš ista stvar opet i opet, to je
sve više kao algoritam, i manje ljudski instinkt.
>> Pa sad, ovdje mi ići opet.
Dvije i četiri?
Ne.
Četiri i jedan?
Ah, bilo je doista neki rade još treba učiniti.
Za te tri?
Dobro.
Četiri i šest?
Šest i pet?
Šest do sedam?
OK, sada, učinio.
OK, nema.
Ja se moram vratiti.
>> Pa sad, opet, mi smo to malo više namjerno.
I sada, postoji samo jedan mozak izvršavanju ovaj algoritam.
Jedan CPU, ako hoćete.
I iskreno, to je jedini resurs ćemo imati pristup.
A kad smo se vratiti na tipkovnici i imaju nešto poput C na našoj
zbrinjavanje, možemo samo pišeš program koji može učiniti jednu stvar u isto vrijeme.
Dok, ovi momci maloprije, mi iskoristio njihov kolektivni brainpower
kao što ste vi učinili u tjednu nulu.
Tako ćemo zadržati to.
>> Dvije i jedna.
Dvije i tri.
Tri i četiri.
Četiri i pet.
Pet i šest.
Šest do sedam.
Gotovo?
Tako sam, ali neka mi igrati vražji odvjetnik.
Da li sam, vrsta računala koji je upravo napravio točno kroz ovaj niz
ljudi, znam da sam učinio?
>> ZVUČNI 1: Broj
>> David J. Malan: Pa zašto?
Ono što bih ja moram napraviti kako bi se zaključuju odlučno da sam učinio?
Vjerojatno još jedan pass.
Točno?
Jer sve što znam iz koje prethodna pass je da sam ispraviti grešku.
A to znači, možda postoji Još uvijek još jedna pogreška
da trebam ispraviti.
Dakle, ja samo mogu biti sigurni od premotavanja, i zatim provjeru jednog do dva, dva i
tri, tri i četiri, četiri i pet, pet i šest, šest i sedam.
OK, sad sam bez posla.
>> Ja sigurno mogu se sjetiti da sam učinio nema raditi nešto poput varijable,
Ljubitelje int.
Nazovite to swaps, a ako je swaps 0 Jednom sam doći ovdje, a započela je na 0, a zatim
Samo bi bilo glupo da ustrajem natrag i naprijed, provjeru opet, i
opet, i opet, zar ne?
Budući da zapnete u nekim vrsta beskonačnu petlju.
Dakle, čim postoji 0 swaps, možemo tvrditi da je ova
Algoritam je doista potpun.
>> Sada, neka je staviti ime na to.
Algoritam koji sam Predlažemo jednostavno proveden je nešto što se zove bubble
sortiranje, poznat i kao takva u smislu da su brojevi koji su veći vrsta
mjehurić svoj put do vrha, odnosno do na kraju niza brojeva.
No, koliko je učinkovit bio ovaj algoritam?
Koliko koraka sam fizički moraju Uzmite, na primjer, za sortiranje tih
Sedam ljudi?
>> Četiri do pet?
OK, previše je u konačnici će biti odgovor.
No, čak i tada, određeni broj nije toliko zanimljiva.
Neka je generalizirati ga kao n.
Dakle, ako sam n ljude ovdje, a oni su, na neki način, u slučajnim redoslijedom u
počinju, u tom izvornom redoslijedu.
Pa, koliko koraka ja imam da se na prvom prolazu?
To je jedan, dva, tri, četiri, pet, šest, a oni su sedam osoba, tako
to je sedam, šest -, tako da je n minus jedan korake prvi put.
>> Sada, koliko koraka ja imam da kad sam premotao?
Pa, mi zapravo mogli udvostručiti da ako smo stvarno željeli, ali za sada, ja sam
Samo ću reći, sve u redu, još n minus 1.
Dakle, n minus 1 će dobiti neugodno za pratiti, pa neka je
Samo zaokružiti nešto.
Dakle 2n koraka.
Dakle 14 koraka, dati ili uzeti.
>> Koliko puta sam se korak sljedeći put?
Pa, to je 3n.
stvarno.
I sada, u najgorem slučaju, za primjerice, koliko puta bi ja imam
otišao natrag i naprijed, natrag i naprijed, izvršavanju ovaj algoritam, zamjene
Ljudi na svaku loptu, otprilike?
To je zapravo n kvadrat, zar ne?
>> Budući da u najgorem slučaju, možete vrsta od razmišljati o tome intuitivno,
iako bi to moglo potrajati malo malo vremena kako bi potonuti u.
U najgorem slučaju, što bi to sedam osoba izgledala, u
uvjeti aranžmana od njihovih brojeva?
Potpuno unatrag, zar ne?
I samo za simulaciju da, ono što je zoveš?
>> MIKE: Mike.
>> David J. Malan: Mike?
OK, Mike, možeš li mi se pridružiti tijekom Ovdje za samo jednu sekundu?
Zapravo, nije.
Žao nam je Mike, idemo natrag.
Koje je vaše ime?
>> NEIL: Neil.
>> David J. Malan: Neil.
OK, Neil, što dolaze s mi, ako ti ne smeta.
Zato ću predložiti, samo za jednostavnost, kako Neil je sada u njegovoj
Najgori mogući slučaj.
Ali sjećam kako sam se provodi moj algoritam.
Ja sam usporedbe, usporedbe, usporedbe, usporedbe, usporedbe, oh.
Sada su ti dečki iz reda, pa sam popraviti.
Dakle, ti dečki zamijeniti.
Ali razmislite, koliko imate dalje Neil ne moraju ići?
To je otprilike n.
Znate, nije zapravo n.
To je kao, n minus 1, ali ja sam uzimajući nerviraju praćenje malo
broj, pa neka je samo nazvati n.
>> Dakle, ako Neil pomiče jedan korak maksimalno svaka vrijeme i za pomicanje Neil jedan korak,
Moram napraviti ovaj uistinu zahtjevan točno naprijed i natrag, to je otprilike
to, n koraka, ukupno n puta, jer će me odvesti
da je mnogo koraka kako bi dobili Neil svima način da tamo gdje pripada.
A kamoli svi drugi, ako ti dečki Svi su mis-naredio kao dobro.
>> Dakle, nazovimo mjehurić kakve n kvadratna.
Trajanje tog algoritma, Performanse ovog algoritma,
Učinkovitost ovog algoritma, samo smo se opisati više
općenito, kao n kvadrat.
Koji je lijepo, jer sam mogao učiniti Isti primjer s osam, devet ljudi
ljudi, milijun ljudi, i to Odgovor se neće promijeniti.
>> Dakle, ako vi ne bi smetalo, neka je vas vratiti na mjesto gdje ste počeli.
I pokušajmo još dva pristupa i vidjeti ako ne možemo napraviti iz temelja
bolje od ovoga.
Dakle, ovaj put, ja ću predložiti različitih vrsta algoritma.
To je vrlo pametno od nas zadnji put, a vi dečki su pravo na
pravo instinkti samo vrsta od zamjene Parne.
Ali ako sam doista želio pristupiti ovom jednostavno, a moj cilj je da se premjestiti
sve od malih brojeva na ovaj način, a gurati sve od velikih brojeva koji
smjer, zašto ne bih to učiniti u većina naivno mogući način i vidjeti ako ja
može učiniti bolje od onoga što je prilično složen algoritam?
>> Pa ćemo vidjeti.
Četiri je prilično mali broj, pa sam će vas ostaviti tamo trenutak.
Ooh, broj dva je još bolje.
Dakle, može li samo korak naprijed na trenutak?
Ovo je trenutno moj najmanji numerirani Kandidat, a ja ću se sjetiti
da s, kao, varijable.
Ali ću držati ček.
Ima li netko čije Broj je manji?
Šest, br.
Oh, ima Neil opet.
>> Tako ću vas gurnuti natrag vrsta konceptualno.
Neil će doći naprijed.
A sada, varijablu da sam koristeći se pratiti tko ima najmanji
broj obnovljen je da sadrži Neil je položaj.
Pa, da vidimo.
Tri, sedam, pet.
OK, znam da je Neil bio najmanji.
Što je najjednostavnije za mene to učiniti sada?
Neću gubiti svoje vrijeme samo mjehurića Neil jedno mjesto ulijevo.
Zašto ne samo staviti Neila gdje je zaposlen, što je, naravno, gdje?
>> Skroz na početku.
Dakle Neila, dolaze sa mnom.
A što je zoveš?
>> GRACE: Grace.
>> David J. Malan: Grace.
OK.
Dakle, Grace, na žalost, ti si vrsta na putu.
Pa kako ćemo riješiti ovaj problem?
Točno?
Ako je ovo polje, postoji samo sedam mjesta.
Podsjetimo da je, s Robom, razgovarali smo o progla dobi, a mi imali samo
konačan broj dobi?
Sve ideja ovdje.
Mi samo imaju ograničen broj Ints.
Grace je vrsta u našim smjer, pa kako smo riješili?
>> Najjednostavniji način je da, Grace, ispričavam se.
Ti ćeš morati ići preko postoje tako da možemo napraviti mjesta.
Sada, ako mislite o tome, možda samo mi je problem pogoršava.
A možda smo mi, zato što ako Grace je na pravom mjestu?
Ali mi znamo da nije, jer je inače, ona bi bila
stoji prema naprijed, umjesto Neil u ovom trenutku, zar ne?
Mi već provjerio njezin broj out.
>> U redu.
Tako sada, Neil je na pravom mjestu, i Ja mogu napraviti blagi optimizacije.
Za sljedeću minutu, ja ću ignorirati Neil svi zajedno, tako da ne
gubiti svoje vrijeme, ili slučajno ga zamijeniti na krivom mjestu.
Tako sada, kako ću pronaći sljedeći element koji je najmanji?
Dvije.
To je prilično dobar broj, ako je želite korak naprijed i
Ja ću vas se sjetiti.
Šest, nije dobro.
Četiri, tri, sedam, pet, nije dobro.
Dakle, dopustite mi da se presele Vaše pravo mjesto.
I samo mi se posrećilo ovaj put.
>> Sada, ja ću ih ignorirati dvojica, a sada napraviti još jedan
prolaze kroz to.
Šest, da je prilično mali broj.
Hajde naprijed.
Oh, ispričavam se.
Grace broj je bolje, tako korak na naprijed.
Četiri.
Žao nam je, Grace.
Idi natrag.
Broj tri je bolje.
Seven.
Pet.
I sad ono zoveš?
>> JASON: Jason.
>> David J. Malan: Jason.
Dakle, Jason je sada najmanji Element sam odabrana.
Kamo ide ići?
Dakle, gdje je šest.
I vaše ime je opet?
>> Gabe: Gabe.
>> David J. Malan: Gabe.
Gabe je na putu.
Što je najjednostavnija stvar za napraviti?
Zamijeni ove dvije dečki i nastaviti.
Pa sad ćemo vidjeti.
Tko je najmanji?
Četiri.
Dopustite mi samo vrsta varati.
Pet će biti najmanja.
Ja vam sljedeći, ako želite korak prema naprijed, što moram učiniti sa
ovi momci, s Gabea?
Zamijeni opet.
Tako sada, još uvijek malo izvan funkcije.
Otkrio sam da se Gabe najmanji, tako Ja ga iskočiti, pomaknite se momci više.
I učinili.
>> Tako da odgovor je isti.
Krajnji rezultat je isti.
Koja od ove dvije algoritama je bolje?
Drugi, čuo sam.
Zašto?
>> ZVUČNI 3: Prošlo n korake [nečujno].
>> David J. Malan: To je n koraka u većini.
Zanimljivi.
Tako je to ipak?
Pa kako mi je bilo najmanji element?
Koliko koraka sam uzeti pronaći najmanji element?
Imao sam izgleda skroz na kraju, zar ne?
Budući da u tom najgorem slučaju, ono što Neil ako su ovamo?
Dakle, samo nalaz najmanji element vodi me n koraka, ili n minus jedan.
Ali, OK.
Dakle riješili Neila.
Zapamtite da, otprilike minutu prije.
>> Ali kako sam pronaći sljedeći najmanji element?
To je n minus 1, odnosno n minus 2 stvarno, od broja koraka.
Pa OK.
Pa sam si n minus dva.
U redu.
Tako da se osjeća malo bolje.
U redu.
Koliko korake sljedeći put pronaći broj tri?
Dakle, n minus 4.
Dakle, to smanjuje, jedan manje korak na svakoj iteraciji.
Dakle, to ne osjećate bolje, zar ne?
Ukoliko zadnji put je to bilo otprilike n puta n, ovaj put je n minus 1, plus minus n
2, te n minus 3 ili n minus 4, točka, točka, točka.
No, ako se sjećaš iz srednje škole udžbenici, malo podvaliti
List na stražnjoj strani koja je formula, ako zbrojite ovaj niz brojeva,
Što je ukupan broj koraka će biti da sam se ovdje?
>> Ovo je jedan od onih koji, kao, n minus 1, n puta, podijeljeno s dva.
Dakle, dopustite mi da vidim mogu povući to se samo na trenutak.
I opet, ja sam vrsta zaokruživanja neke Brojevi samo da bi naš život lakšim,
ali koliko se sjećam, to je nešto kao i ako Ja n minus 1 stvari, a zatim n minus
2, a zatim n minus 3, to je otprilike ovako nešto više od 2, a ako sam
pomnožite ovo, to je zapravo n trgu.
To se ne osjeća baš dobro. n minus n preko 2.
>> Ali ovdje je stvar.
U računalnoj znanosti, kad su problemi početi da biste dobili zanimljiv je kad n
dobiva stvarno velika.
A kada je n dobiva stvarno velika, što je ove vrijednosti će dominirati sve
od drugih?
To je vrsta od n na kvadrat, zar ne?
Da, podijeli s dva je prilično dobra.
Ali ako govorimo o milijardama komada podataka, ili bilijunima
dijelovi podataka, ok, pa ti si dva puta brže.
No, tko je zapravo briga ako tim velikim brojem, ako je taj faktor je ono što dobiva
veći i veći.
I sigurno, to čini više od Razlika od ovog momka.
Dakle, iako ste vi u pravu, Drugi algoritam, mi ćemo ga zvati
Izbor sortiranje, je, u stvarnom svijetu, malo brže potencijalno, jer sam
uzimajući sve manje i manje korake svaki put.
>> To zapravo nije bitno brži.
Jer, ako smo zapravo igrati ovo za velike vrijednosti n, na kraju
dan, za dovoljno veliki n, to je još uvijek ide da se osjećaju prilično sporo.
Pa, neka mi se jedan Posljednji pass na to.
To je ono što bih nazvao Izbor sortiranje.
Možete li sebe resetirati zadnji put?
I u ovom posljednjem slučaju, idem predložiti nešto
naziva unosa vrsta.
Ubacivanje neka vrsta bića, konceptualno, malo drugačiji.
>> Umjesto da ide naprijed i natrag, a odabirom najmanji element, sam
Samo će se nositi sa svakom od tih Dečki kao što sam ih susrećemo, i umetnite
ih u njihovom ispravnom mjestu.
Dakle, samo ću početi s Grace, i ja vidim da je ona broj četiri.
Odakle broj četiri pripadaju?
Ja nisam počeo ništa sortiranja, Grace tako dobiva ostati tamo.
A sada ću tvrditi, ako bi poduzeti korak da je vaše pravo, to
moj razvrstani popis, ovo je moj nerazvrstani preostali popis.
Dakle, sad ću nastaviti sljedeći, i ono zoveš?
>> BRANSON: Branson.
>> David J. Malan: Branson.
Dakle Branson je broj dva.
Dakle, ja ću vas odvesti se na trenutak.
A sada, gdje si ti u tom polju?
Dakle, desno od Milosti.
Pa opet, mi smo vrsta izradu Grace napraviti puno posla ovdje.
Gdje smo vas?
Tako ćemo vas pomaknite se lijevo, i umetnite Branson postoji.
Ali sada tvrdim da ti dečki su učinili.
No, obavijest, ne koristim dodatni prostor.
To je još uvijek 2 elementa Ovdje, 5 ovamo.
Ukupna veličina polja je 7, tako da sam ne vara, u redu?
>> Tako sada imamo, s Gabea ovdje, broj šest, gdje si ti?
Imaš sreću ponovno.
Tako ćete dobiti ostati tamo.
Dovoljno je uzeti lagani korak prema desno samo da bi jasno da ste razvrstani.
I sada imamo Neila opet, broj jedan, gdje idete?
A sada je mjesto gdje ćemo početi vidjeti da ovaj algoritam, iako se na prvi
pogled, osjeća prilično pametna, gledanje što će se dogoditi.
Ako bi korak naprijed.
>> Gdje želimo staviti Neila?
Dakle, očito ovdje, pa kako ćemo dobiti Neila postoji?
Učinimo ovaj korak-po-korak.
Gabe, gdje trebate ići?
Yep, tako da se jedan veliki korak, ili dvije polovice koraci kako bi
jedan korak tamo.
Grace, gdje idete?
Dobro.
Tako je još jedan korak.
I na kraju, Branson?
Još jedan korak.
I sada možemo staviti na mjesto Neila.
>> Pa sad, i dalje tu logiku.
Iako mi se ne prebacuje Neilu više, i više, i više, da ga stavi
gdje ide, u najgorem slučaju, Sljedeći broj ćemo naići mogli
se broj, kažu, bilo je broj nuli, onda ćemo pomaknuti sve
ovi momci.
Pretpostavimo da je broj negativan jedan, onda ćemo morati prebaciti
svi ovi dečki.
Tako smo zapravo samo vrsta flipping Problem oko, kao da smo
prijenos trošak od postupak odabira tako umetanje
proces, tako da vi samo imali premjestiti otprilike n minus nešto
Broj koraka.
I da je broj koraka samo ide povećati kao što sam odabir više brojeva,
ako moram držati guranje momci natrag, i natrag, i natrag.
>> Tako tužno Sada je sve to algoritme su n na kvadrat.
Idemo naprijed, a zahvaljujući tim Dečki, i zamišljati ove malo
drugačije.
Vrlo dobro učinio.
>> [PLJESAK]
>> U redu.
Izvoli.
Hvala -
>> BRANSON: [nečujno] držati brojeve.
>> David J. Malan: Ne, vi svibanj zadržati brojeve, kao dobro.
U redu.
Lijepo učinili.
U redu.
Dakle, neka je vidjeti ako sad ne možemo sumirati brže i više vizualno,
točno što se dogodilo Ovdje su kako slijedi.
Ja ću ići naprijed i povucite prema gore Firefox.
Mi ćemo povezati ovaj prosvjed na stazi stranicama.
Java je malo neugodno da se radi u nekim preglednicima ovih dana.
Dakle, ako ne igraju s tim kod kuće, shvatite da ćete morati koristiti Firefox
da se to radi.
A ono što ću učiniti s ovim Demonstracija je sljedeće.
>> Na dnu, imam cijelu hrpu opcije izbornika, uključujući početak i
stop.
Također, kao na stranu, čini se da postoji bug u ovim programima, pri čemu se
zapravo ne može vidjeti početak ili zaustavljanje Gumb ukoliko ne držite Command ili Alt
plus i zumiranje, koji znatiželjno pokazuje više gumba.
Dakle, samo za Vašu informaciju, ako igrate uz to kod kuće.
Sada ću kliknite Start u samo Trenutak, nakon navođenja kašnjenje,
kao što je, 200 milisekundi ovdje, samo tako da možemo vidjeti što se događa.
>> Dakle, ja tvrdim da je to vizualizacija prvog algoritma
ovi momci su napravili, bubble sortiranje, pri čemu Zamijenili smo ljude pair-mudar.
Ključni uvid na ovu vizualizaciju je da je visina od traka
predstavlja veličinu broja.
Dakle jači bar, veći broj.
Kraći bar, manji broj.
A ako primjetite, idemo kroz prva iteracija ovog algoritma
zamjene velike i male brojeve, tako da je Mali broj je na prvom mjestu, a
Veliki broj ide na desno.
>> I čim smo dobili kraj niza mnogih više od sedam brojeva, mi smo
će se vratiti na početak.
I to predvidjeti.
Na daleko lijevo, da mali dečko ide mijenjati u stranu, a to
proces se ponavlja.
Sada je to vizualizacija brzo dobiva dosadna, pa neka mi ići naprijed i zaustaviti
da, promijenite nešto odgode mnogo brži samo da bi sada, osjećaj za
ovaj algoritam.
>> Dakle, iako sam ga ubrzao, ovo je kao i nadogradnju moje procesor, kupnje
novo računalo.
Nisam iz temelja promijenilo moj algoritam, ali doista može vidjeti više
jasnije nego s ljudima, da je velika brojevi mjehurića do vrha,
a mali broj se mjehurića do dna.
A sada ovo ovdje izdvojiti.
I kao stranu, na trgovima, postoji samo su neka knjigovodstvo tamo
vam pomoći brojati koliko usporedbe, ili koliko imaju swaps
zapravo učinjeno.
>> Pa, pokušajmo jedan od ostali smo vidjeli.
Dopustite mi da kliknete na balon vrste ovdje, a dopustite mi da odaberem, a cijela ova web stranica
je malo lud.
Hajdemo prihvatiti rizik te ga ponovno pokrenuti.
Tamo idemo.
Tako ćemo napraviti odabir vrsta.
Ne znam zašto se izbornik pojavljuje tamo.
Idemo zoom u to popraviti bug, to promijeni do 50 godina.
Ah, neka je zapravo da je puno brže.
Pet milisekundi ili tako, i početi.
>> Dakle, ovo je neka vrsta odabira.
Pa opet, razmišljati o tome što smo učinio s ljudima ovdje.
Prošli smo kroz niz i odabrana najmanji element opet,
i opet, i opet.
Sada sam tvrde da je još uvijek prilično loše.
To je još uvijek n kvadrat, dati ili uzeti, ali to je, u stvarnom svijetu, malo
brže, jer sam doista bio vodeći nešto manje korake svaki put.
No, mi samo pričamo što?
Možda 40 ili tako bar ovdje?
Mi ne govorimo 40 milijuna kuna.
Dakle, to nije potpuno mi je jasno da bio je doista značajan dobitak.
>> Dopustite mi sada vratiti i promijeniti u našim Treći algoritam, koji je odabir
umetanja sortiranje.
I sad je stvarno lud, jer Izbornik stvarno ne bi trebao biti tamo.
Dakle, sada ćemo pomicanje natrag ovdje i početi ovaj algoritam.
Poklič, pokretanje i zaustavljanje.
Dakle, to je jedna vrsta ima lijepu uzorak na njega, pri čemu smo opet
umetanjem ljude, ili u ovaj slučaj, lokali u
njihovo odgovarajuće mjesto.
A to je već učinjeno prije Okrenula sam se.
No, i ova je također, u teoriji, Još uvijek je n kvadrat.
>> Dakle, neka je vidjeti ako ne možemo sumirati to na sljedeći način.
Ja ću ići naprijed i samo dati nas vrsta zajedničkog način govori
o ovim stvarima, neka mi predstaviti Samo malo zapis ovdje.
Vi ste o kako bi vidjeli nešto što se zove big O, jer je doslovce velika
O. I to je način na koji računalo znanstvenik ili matematičar i koristi
opisati vrijeme rada nekog algoritma.
Koliko koraka to zapravo potrajati?
>> Sada ću se ja sramotiti s moj rukopis ovdje u samo trenutak.
No, dopustite mi da ide naprijed i reći da to će biti velika O ovamo.
I neka mi predstaviti jedan drugi simbol, glavni omega.
Omega će biti suprotno, u biti, od velikog O. dok velike O
znači, u najgorem slučaju, koliko vremena Možda su neki algoritam se, u
Uvjeti n, omega će se koliko vremena može ga
se u najboljem slučaju.
A vidjet ćemo što podrazumijevamo pod Najbolji slučaj u samo trenutak.
>> Dakle, krenimo nešto jednostavno.
Dopustite mi da započnem s linearnim pretraživanje.
Dakle, ne sortiranja.
Nazvat ćemo ovo linearno pretraživanje.
I sada, da malo tablici iz ovoga.
I sada, u slučaju linearne pretraživanja, u najgorem slučaju, koliko koraka je
je da će me odvesti pronaći broj proizvoljnog izbora?
I tu je n ukupni vrata ili n ukupni broj.
Najgori slučaj.
Koliko koraka ću morati poduzeti kako bi pronašli broj 50 u niz
od n vrata?
A zašto?
Jer to bi moglo biti sve put preko na kraju.
Toliko poput Jennifer naišao, Broj 50 je bio skroz, tako da u
najgorem slučaju linearno pretraživanje je velika O n, mi ćemo reći.
>> Što o najboljem slučaju, ako se stvarno sretan?
To samo ide uzeti jedan korak, ili stalna broj koraka.
Tako ćemo opisuju to kao jedan.
Dakle, ovo je prilično dobra.
Sad što ako mi je nešto kao binarna?
Dakle, binarna, u najgorem slučaj, uzeo koliko vremena?
>> [Pridodati glasovima]
>> David J. Malan: Pa zapravo, ja ga čuli za par mjesta.
Dakle, to je zapravo log n, više ili manje, jer kao što smo podijeliti na pola popis
opet, i opet, i opet, mi smo u mogućnosti naći, u konačnici, vrijednost,
Ako je tamo, ali postoji kvaka.
Što je pretpostavka da moramo uzeti zdravo za gotovo binarni potrazi?
To mora biti riješeno.
Nije riješeno, možete podijeliti stvar na pola opet i opet, a vi
može ići lijevo, a možete ići desno, a možete ići lijevo i desno, ali ti si
Ne ide pronaći element ako je Popis nije riješeno, jer je
možda ga propustiti.
Zbog svoje heurističkim, za idući lijeva ili desno će biti manjkav, ako je to
istina, nije riješeno.
Tako da postoji neka vrsta skrivenih troškova na korištenje ovako nešto.
>> Sada, idemo u našu sortiranje algoritmi ne traži -
Oh, zapravo, idemo u tom prazninom.
Binary search u najboljem slučaju?
To je također jedna ako se to dogodi samo da bude u samom središtu polja, ili
Sredina u telefonskom imeniku.
Sada ćemo napraviti balon vrsta.
Pa opet, sada ulazimo vrste, a ne na traženje.
>> U najgorem slučaju, koliko koraka smo učinili tvrdnja bubble sortiranje će potrajati?
n kvadrat.
Tako ću se izvući da je.
Ooo, moj rukopis izgleda još gore kad je usmjeren da je veliki.
U redu.
Tako da je n kvadrat.
I u najboljem slučaju bubble sort, koliko koraka će to potrajati?
1, čuo sam.
>> ZVUČNI 1: n.
>> David J. Malan: n, čuo sam.
>> ZVUČNI 1: 2.
>> David J. Malan: 2, čuo sam.
Da čujem 3?
U redu.
Tako sam čuo jednog, n, 2, ali neka je pokupiti osim barem prvi veliki
prijedlozi, 1.
To nije loša instinkt, jer je to vrsta slijedi uzorak ovdje.
No, ako to traje samo jedan korak, kako u Svijet bi ja tvrdim da je popis
je riješeno, jer ako sam se samo smijem uzeti jedan korak, kako su mnogi elementi
mogao sam zapravo da provjerite?
Pa, samo jedan, što znači da je n minus 1 elemenata koji bi mogli biti izvan
bi, a ja samo idem na vjeri nakon gleda na jedan element koji
stvar je riješeno.
Dakle 1 nije točno ovdje.
Dakle, minimalno, koliko je moram pogledati?
>> [Pridodati glasovima]
>> David J. Malan: n minus 1, ili stvarno, n, jer moram gledati na svaku
elementa kako bi bili sigurni da to nije izvan reda.
Ali opet, mi ćemo riješiti naše vala Ruke u manjim brojevima i
Pretpostavljam da je, kao n dobiva veliki, oni su nezanimljivo svejedno.
Dakle, to je neka vrsta balon.
A sada, idemo napraviti ta dva.
Izbor sortirati, a zatim ćemo učinite unosa vrsta.
A onda ćemo puhati umovi s nešto više
bolje od svih ovih.
U redu.
>> Što je najgori slučaj pokrenut vrijeme odabira vrste?
>> ZVUČNI 4: n kvadrat.
>> David J. Malan: n kvadrat, čujem.
Ali zašto n kvadrat, intuitivno?
>> ZVUČNI 4: Budući da smo upravo to učinio.
>> David J. Malan: Jer smo upravo to učinio.
OK.
Dobar odgovor.
Ali intuitivno, zašto je izbor sortiranje n na kvadrat?
Što moramo učiniti opet i opet?
Imali smo zadržati skenirati, su što najmanja, jesi li
Najmanji, ti najmanji.
I gotovo, bili smo u mogućnosti da se n koraka, a zatim n minus 1, a zatim n minus 2.
Ali ako vrsta dodati one sve gore, ili ga odvesti na vjeri koje sam dodao
ih se unaprijed, dobili smo oko n kvadrat minus nekim manjim brojevima.
Pa ću nazvati ovo n na kvadrat.
No, s odabira vrste u najboljem slučaj, koliko koraka je
da će me odvesti?
>> ZVUČNI 5: [nečujno]
>> David J. Malan: To je, nažalost Još uvijek n kvadrat, zar ne?
Jer ako sam odabirom najmanji elementa, a imali smo sedam ljudi ovdje,
Ja samo znam, kad sam doći do vrlo na kraju, da sam pronašao najmanja
broj, gdje god on ili je mogla biti.
Ali kako ću pronaći sljedeći Najmanji broj?
Moram napraviti još točno.
Dakle, u najboljem slučaju, ono što je Ulaz u izbor vrste?
To je već neka vrsta popisa, broj jedan, broj dva, broj tri, broj četiri.
Ali ja sam računalo.
Ja se samo mogu pogledati jedan stvar u isto vrijeme.
Ja se ne mogu razvrstati mjesta uzeti jedan korak vratio kao čovjeka i kažu,
ooo, ovo izgleda točna.
>> Ja samo mogu presuditi u ispravnost Izbor svojevrsni odabirom
Najmanji broj.
No, čak i ako nađem broj jedan prvi, ako ja ne znam ništa drugo o
ostali brojevi, koji sam Ne, sve sam znam da sam predao niz
ili skup vrata iza kojih se brojevi, jedini način znam da je jedan
bio najmanji?
Ako sam se do ovdje i ostvariti, damn, jedna je doista najmanja.
>> Ali kako sam onda odrediti koji dva je sljedeća najmanja?
Na taj isti neučinkovitost opet i opet.
Pa napokon, s ugradnjom vrste, kako se, u najgorem slučaju,
Jesmo li reći to obavlja?
To je previše n kvadrat.
A što je s najboljem slučaju?
Ostavit ćemo to kao Cliffhanger.
Mi ćemo ispuniti taj prazan sljedeći put, ali prvo neka mi predložiti da se
bitno bolje od sve to, u redu?
>> Tako misle za sebe ono umetanja sortiranje će biti.
Pa, to nije bilo vrlo dramatično, jer ja sam samo jedan
da je vidio promjenu.
Wow.
OK.
Dakle, ovdje imamo nešto različite demonstracije.
Ako sam zumirati ovdje, vidjet ćete da se na lijeva imamo mjehurić vrsta, u
Srednji imamo izbor vrsta, a na desni, imamo nešto što
nisu gledali na još zove spajanje vrsta.
No, razmislite o tome što smo bili radiš ovdje do sada još danas.
Kad Jennifer prvi put došao na pozornicu, smo prošli kroz niz brojeva
opet, i opet, s linearno pretraživanje, i dobili smo linearno vrijeme rada, big O
n, da se tako izrazim.
>> Kad smo sada razmotriti prvi tjedan klase, kada smo podijeli pa vladaj,
i imali smo telefonski imenik suzenje, i Jennifer, a mi kolektivno
utjecati na ključna uvid, što je za se ponoviti opet i opet
nekako bacanja, bacanja, bacanja, polovica problema, ili
općenito, dijeljenjem problem na pola, a zatim tretiranje manji dio
Problem su konceptualno odgovara za druge, nekako smo učinili
bitno bolje.
No, s bubble sort, uz izbor sortiranje, s ugradnjom vrste, mi smo svibanj
nema takvih saznanja da je Jennifer učinio.
Mi prilično jednostavno vratio i naprijed cijela hrpa vremena, a mi
praćka stvari malo, zamjene u tom cilju, možda
umetanja ili odabirom.
Ali na kraju dana, ja sam puno od nezgodnom hodanjem.
Mi zapravo nije nešto utjecati pametna kao što je Jennifer poput dijeljenja
i osvajanje.
>> Dakle spojiti neku, za razliku od, koji mi neće vidjeti do sljedećeg tjedna, to se događa
utjecati na ključna ideja dijeljenjem ulaz, a zatim na pola, a zatim
na pola, a zatim prepoloviti.
I na svakoj iteraciji tog petlje, sortiranje lijevu polovicu, kao i pravo
pola, zatim lijevu polovicu lijeve polovice, i desnu polovicu lijeve strane, a zatim
lijeva polovica desne polovice i pravo polovice desne polovice.
I ponavlja opet i opet.
>> Dakle, vidjet ćete ovo vizualno, ali ovo je ono što nas čeka sljedeći tjedan.
I općenito, kada mislimo malo malo teže na bilo takvih problema.
Mi smo n kvadrat na lijevoj strani, n kvadrat u sredini, a n
log n na desnoj strani.
Tako da je tvoj pravi roman u nastavcima.
Vidimo se u ponedjeljak.
>> [PLJESAK]