>> [Musikk spilles]
>> DAVID J. MALAN: All right.
Så velkommen tilbake.
Dette er CS50, og det er slutten av uke tre.
>> Så husker i de siste ukene, vi har vært å bruke ganske mye
tid på C, på programmering, på syntaks.
Og det er ganske vanlig, hvis du fremdeles sliter med Problem Set 2, for å være
stanger hodet mot veggen.
Det er kryptisk utseende feilmeldinger og bugs som du
kan ikke helt jage ned.
Fordi, være trygg, at i bare en par ukers tid vil du se tilbake på
ting som Caesar, og [? V-genair,?] kanskje til og med sprekke, og
innse hvor langt du har kommet i en kort periode.
Så hvis det er noen trøst, henge der for nå.
>> I dag, men vi begynner å overgang til ting høyere nivå.
Og vi begynner å ta for gitt at dere vet hvordan man programmerer, eller i
minst begynnelsen av at komfort nivå.
Og vi begynner å tenke på hvordan vi kan gå om å designe programmer mer
effektivt.
Hvordan vi kan gå om å optimalisere effektiviteten av våre algoritmer, og
vanligvis løse mer interessante problemstillinger.
Og begynner å ta for gitt at hvis vi ville, kunne vi kode opp noe
av eksemplene vi har i tankene.
Så i dag har vi ikke tar på tastaturet for en hvilken som helst form for kode.
Det vil være mye høyere nivå, og til slutt, om problemløsning.
>> Så for å komme til det punktet, la meg foreslå at følgende syv
rektangler representerer sju dører, bak som er en hel haug med
tall, blant disse er tallet 50..
La meg projisere dette på denne skjermen her også.
Og foreslå at vi trenger en frivillig til bidra til å finne meg et nummer foran
internett her for å se.
Kom opp i rosa.
OK.
Hva heter du?
>> JENNIFER: [uhørlig]
>> DAVID J. MALAN: Beklager?
>> JENNIFER: Jennifer.
>> DAVID J. MALAN: Jennifer.
Greit, Jennifer.
Hyggelig å treffe deg.
Kom opp.
Så disse her er sju dører, og hva Jeg vil at du skal gjøre for oss her,
foran alle dine klassekamerater, er å finne oss nummeret, 50.
For å finne et nummer, kan du titte bak noen av disse dørene ved å trykke
på en av dørene, og den vil avsløre sin nummer.
Og la oss se hvor raskt du finner oss nummeret, 50.
>> 15.
16.
50.
Pent gjort.
OK.
Applaus for Jennifer.
>> [APPLAUSE]
>> OK.
Så hva var din strategi for finne nummeret, 50?
>> JENNIFER: Um, jeg tenkte kanskje hvis -
[Uhørlig]
>> DAVID J. MALAN: Oh.
Gi det ett sekund.
Så var din strategi for finne nummeret, 50?
>> JENNIFER: Så jeg bare starte på begynner å se hva det første tallet
var, og så tenkte jeg, kanskje hvis de er sortert, vil jeg bare holde
tappe høyere opp?
>> DAVID J. MALAN: OK.
Og vi synes å ha funnet det å være tilfelle.
Selv om, la oss skrelle tilbake lagene bare en liten bit, og du vil gå
videre og avsløre de andre dørene du kunne ha valgt?
>> JENNIFER: Åh, kjære.
>> DAVID J. MALAN: Ah.
>> JENNIFER: Så jeg bare hadde flaks.
>> DAVID J. MALAN: Så du hadde flaks.
OK.
Så ikke ille.
Men det er en interessant innsikt, ikke sant?
Hvis du antok, og du fikk, faktisk litt heldig der.
Men hvis du antok at tallene var sorteres, kan du være mer presis
om hvordan det påvirket din oppførsel?
>> JENNIFER: Så hvis de ble sortert, jeg tenkte kanskje minst til størst.
>> DAVID J. MALAN: OK.
>> JENNIFER: Eller hvis dette endte opp med å bli virkelig stor, så største til minste.
>> DAVID J. MALAN: OK.
Så største til minste, eller minste til største.
Men la meg foreslå si at du hadde fått uheldig, og anta at de
var ikke, faktisk, sortert, hvor mange av disse dørene har du kanskje måtte titte
bak i det verste tilfellet?
>> JENNIFER: Alle av dem.
>> DAVID J. MALAN: Alle av dem.
Så la oss generalisere det som n.
Det skjer for å være 7, men la oss mer generelt si at det er n dører på
skjermen her.
Så i verste fall, ville du ha å se bak syv dører, eller n dører.
Og så dette er virkelig, det er litt av flaks i dag, men det er egentlig en lineær
algoritme slags, selv om du var slags hoppe rundt.
Er det rettferdig?
>> JENNIFER: Yeah.
>> DAVID J. MALAN: Vel, la meg se om strategi endringer hvis jeg flytter oss til
vår andre eksemplet her med 7 ulike dører.
Samme tallene, men dette gang de er sortert.
Hva er din strategi her kommer til å bli, prøver å sette ut av tankene dine hva
de andre tallene var -
>> JENNIFER: OK.
>> DAVID J. MALAN: - tidligere?
>> JENNIFER: La oss starte med den første.
>> DAVID J. MALAN: All right.
Start med den første.
4.
Nå hvor du skal gå, og hvorfor?
>> JENNIFER: 4 er virkelig små.
Så hvis de er liksom kanskje minste til største, bør det
være det dobbelte, og -.
>> DAVID J. MALAN: OK.
La oss se, som du tror?
>> JENNIFER: Prøv den siste.
Nice.
>> DAVID J. MALAN: Veldig pent gjort.
OK.
>> [APPLAUSE]
>> DAVID J. MALAN: OK.
Så du faktisk gjør dette forferdelig, fordi du er
gjør det veldig bra.
Som etterlater oss i stand til å gjøre enkelte punkter.
Så la oss prøve å rulle tilbake hit.
>> JENNIFER: OK.
>> DAVID J. MALAN: Very well gjort, likevel.
Så du startet i begynnelsen, du så at det var fire, så du
flyttet til enden.
Men antar at du ikke får heldig der, og antar 50
var et annet sted.
Hva din tredje trinnet har vært?
>> JENNIFER: Gå tilbake til begynnelsen.
>> DAVID J. MALAN: Gå tilbake til begynnelsen.
OK, så du ville har rørt denne døren, som var åtte.
OK.
Så det er ikke 50.
Hvor ville du ha sett neste?
>> JENNIFER: Hvis jeg ikke vet de sortert.
>> DAVID J. MALAN: Riktig.
Vel, hvis du visste de ble sortert -
>> JENNIFER: Oh, visste, ja.
>> DAVID J. MALAN: - men det gjorde du ikke vet hvor 50 var ennå?
>> JENNIFER: Bare fortsett.
>> DAVID J. MALAN: All right.
OK.
Holde det gående.
OK, at jeg kan jobbe med.
>> JENNIFER: OK.
>> DAVID J. MALAN: Nå, hvis du bare kommer til å holde det gående, hva er din
algoritme devolving støttet inn.
>> JENNIFER: Den lineære -.
>> DAVID J. MALAN: Det er slags lineær.
Men la meg foreslå, la me satt på stedet.
La meg oppdatere siden.
samme nummer, samme arrangement, samme dører.
Men tenk tilbake til den første dagen i klasse når vi rev en telefonbok
halvparten, liksom, og hva som var vår strategi der?
>> JENNIFER: Start på midten.
>> DAVID J. MALAN: OK.
Så starter på midten.
Så la oss gå videre og late som.
Begynn på midten av avslørende at døren.
Så tallet 16.
Så hva ville den sterke fyren har gjort, som rev telefonboken i to,
for å komme til neste gjetning?
>> JENNIFER: Gå i denne omgangen.
>> DAVID J. MALAN: Og hvorfor til høyre?
>> JENNIFER: Hvis de var slags minste til største, så 50 bør være
på at slutten.
>> DAVID J. MALAN: Good.
Helt rimelig.
Så ut som en telefonkatalog, går du til rett i motsetning til venstre, men her
er nøkkelen takeaway.
Du kan nå kaste bort, eller rive av, halvparten av dette problemet, slik at du ikke
med syv dører, men egentlig med tre like.
Som er omtrent halvparten av Størrelsen av problemet.
OK.
Så nå hva du ville ha gjort etter at du går rett?
>> JENNIFER: Så 16 er fortsatt ganske liten, i forhold til 50, så kanskje jeg skal prøve,
som, en dette.
>> DAVID J. MALAN: All right.
42.
Ok, så nå hva er din instinkt som forteller deg?
>> JENNIFER: Jeg kan kaste bort dette og så bare -
>> DAVID J. MALAN: OK.
Bra, kan du kaste bort venstre halvdel der.
>> JENNIFER: - plukke dette.
>> DAVID J. MALAN: Og høyre.
>> JENNIFER: Yeah.
>> DAVID J. MALAN: Så selv om det er vanskelig å se kanskje, når det er bare
7 dører, tenk, nå, konsistensen av
algoritme du bare søkt.
I den forrige saken, gjorde du få heldige, som var stor.
Men det gjorde du bruke en heuristisk, Jeg vil si.
Du brukte slags instinktene dine, og å vite det sortert, hvis det er ganske
små i begynnelsen, selvsagt, har vi må gå mer til høyre.
Men på en måte, fikk du heldig, fordi kanskje dette var nummer 100,
og kanskje 50 var mer i midten.
Kanskje 50 var selv over her.
>> Men hva du gjorde et litt annerledes denne gangen var, gjorde du det samme
igjen og igjen.
Og jeg vil påstå at det du nettopp gitt, enskjønt påvirket av telefonen
bok eksempel, er noe mye mer algoritmisk, og mye
mindre spesiell rettssak.
Mye mindre instinktiv.
Så i slutten av dagen, hvordan ville du beskriver effektiviteten til
første algoritme, hvor du gikk venstre til høyre, kontra
andre algoritmen her?
>> JENNIFER: Det ene burde, som, kanskje halvere tiden, eller enda mer, ja.
>> DAVID J. MALAN: OK, kanskje enda mer.
La oss presse litt hardere på det.
Hva egentlig, hvis vi fortsetter denne logikk, vi definitivt halvert
kjøretid med denne andre algoritmen ved å kaste bort halvparten av
tall, men hva gjorde vi på neste iterasjon, da Jennifer avslørt
det andre tallet?
>> Vi halvert numrene på dørene igjen.
Og hva gjorde vi etter det, hvis det var flere dører for å spille med?
Vi ville halvere dem, og igjen, og igjen og igjen.
Og dette var akkurat som dere alle stå opp på den første uken av
klasse, halvparten av dere sitte ned, halvparten av dere sitte ned, halvparten av dere
sitte ned, helt til en ensom sjel sto.
Og vi sa at kjøretiden det, var antall skritt som tok
på rekkefølgen av hva?
>> SPEAKER 1: [uhørlig]
>> DAVID J. MALAN: Så log base 2 av n, eller bare enklere, logg av n.
Så noe logaritmisk.
Og grafen var ikke en rett linje som bare ble verre og verre, var det
dette interessant kurve som ikke får så dårlig over tid.
Så la oss holde fast på denne ideen.
La oss takke Jennifer.
Takk så mye for å komme videre opp.
Og, en sek.
Ingen bordlamper i dag, men vi har CS50 stress baller.
>> JENNIFER: Yay.
>> DAVID J. MALAN: Greit, her.
Takk for at du pådra stresset opp her.
OK.
Så la oss se om vi ikke kan nå formalisere dette litt mer.
Så igjen, var det vi nettopp gjorde hovedsak det samme som vi gjorde
i den første uken.
Men heller enn å ende med bare en lineær algoritme, som vi avbildet
som tidligere er denne rett linje, der, hvis vi legger enda en dør på
skjermen, da Jennifer ville har måttet se, potensielt,
bak en mer dør.
Hvis vi setter to dører, kan hun ha å se bak to dører.
>> Og så var det denne lineær Forholdet mellom størrelsen på
problemet på, si, x-aksen, og hvor lang tid det tar å
løse på y.
Men bildet jeg hentydet til tidligere var denne grønne linjen.
Grønn bevisst, fordi det bare føltes bedre.
I teorien algoritmen, når vi gjorde det med telefonboken, når vi gjorde det
med dere telle hverandre, og i det andre tilfellet, når Jennifer bare
gjorde det opp her, var det liksom av fundamentalt bedre.
Fordi det var ikke bare dobbelt så fort.
Det var ikke selv fire ganger så fort.
Det var fullstendig avhengig av hva Størrelsen på innspill var, om hvor mange
trinnene det til slutt tok.
>> Og så denne enkle ideen om at vi alle tok for gitt med telefonboken,
På samme måte kan brukes til noe som dette.
Og dette kan være mer tilfeldig kjent som, som du kanskje
forestille seg, splitt og hersk.
Ikke ulikt det vi gjorde, selvfølgelig, med telefonboken.
>> Men pseudokode, husker, var dette.
Så vi vil ikke gjøre dette igjen, men husker den første uken, sto oss alle opp
og deretter halvparten av dere satte seg, halvparten av du satte meg ned, satte halvparten av dere ned.
At algoritmen ble implementert i en litt av en utro måte, ved at det
var ikke bare en av meg å telle, fundamentalt, mer effektivt.
I så fall ble jeg utnytte en sekundær ressurs.
Liksom, flere prosessorer, flere hjerner, flere smarte mennesker i
Rommet var hjelpe meg å få fra noe lineær til noe
logaritmisk, fra noe rød til noe grønt.
>> Men i dette tilfellet, Jennifer alene kan fundamentalt forbedre den
utførelsen av sitt første algoritme ved, igjen, bare tenke litt hardere.
Og nå, når det gjelder tid til å implementere disse tingene, finne ut
hva linjer med kode du kan skrive en slik at du kan gjenta dem igjen, og
igjen og igjen, liksom i en looping mote.
Fordi du ikke kommer til å ha luksus, som Jennifer gjorde i starten, til
bare ha en hel haug med IFS og si: hmm, hvis dette første tallet er 4,
la meg hoppe helt til slutten.
Ooh, hvis det tallet er for stor, la meg flytte vilkårlig tilbake
til det andre elementet.
Du vil finne at det kommer til å være mye vanskeligere å formalisere hva vi mennesker
tar for gitt som svært rimelig heuristikk, men en datamaskin er bare
kommer til å gjøre det du ber den om.
>> Nå har dette veldig interessant implikasjoner.
Denne grafen er liksom ment å sortere av overvelde visuelt, men varsel, der
er den rette linjen i denne grafen?
Hvor er den lineære grafen som vi kaller n?
Vel, det er liksom mot bunnen av dette bildet, ikke sant?
Så alt vi har gjort er at vi har liksom zoomer ut til x-aksen og
y-aksen for å prøve å få en oppfatning av hva andre typer kurver se ut.
>> Og detaljene i den matematiske uttrykk i dag vil ikke saken så
mye, men merker at det er mye algoritmer som er langt verre enn
noe som er lineær.
Faktisk ser n terninger ganske ille.
2 til n ser ganske ille. n squared ser ganske ille.
Og vi får se hva noen av dem kan være i virkeligheten i dag.
Og log n føles ikke så ille, men bedre enn n er log base 2 av n.
Men du vet, ville det ha vært enda mer fantastisk hvis Jennifer, eller hvis vi,
den første uken, hadde kommet opp med noe som er logg over log n.
>> Så med andre ord, det er hele denne utvalg av mulige løsninger på
problemer, men selv her, varsel hva kommer til å skje.
Når jeg zoome ut, hvilke av disse kurvene kommer til å vise seg å være den absolutt
verste av de på skjermen nå?
Så n terninger ser ganske dårlig i øyeblikket.
Men hvis vi zoome ut og se mer av x og y-aksen, som kommer til å
dominerer slutt?
Så det faktisk viser seg at to til n, og du kan finne ut av dette bare ved
plugge i noen stadig større tall, og du vil se at to til
n, faktisk blir større mye raskere.
Hvis vi virkelig zoome ut, en to til n algoritme suger absolutt.
Jeg mener dette kommer til å ta ganske mye tid for
datamaskin til churn gjennom.
>> Men du får se over tid, spesielt med fremtidige oppgavesett og selv
siste prosjekter, er dataene sett blir stor, ok?
Selv i den første versjonen av Facebook, som antall par, og den
antall registrerte brukere fikk store, du kan liksom telefonen det i og
gjennomføre noe med lineær søk, eller en meget enkel sortering
algoritme, som vi ser i dag.
Du må begynne å tenke hardere og vanskeligere om disse problemene.
Og hvilke typer problemer steder som Facebook og Google, og Microsoft,
og andre arbeider på er akkurat disse slags stor data slags spørsmål
stadig i disse dager.
>> OK.
Så Jennifer suksess i den andre algoritme, ærlig, gjorde hun utrolig
Brønnen er den første gangen, men la oss skrive det som flaks slik at vi
kan gjøre dette punktet.
I det andre tilfellet, leveraged hun en algoritme som gjentas igjen og
igjen, men hun tok for gitt en viss antakelse om at vi tillot
henne, men hun utnyttet noen detalj andre gang at hun ikke har
første gang.
Som var det?
>> At listen ble sortert.
Så så snart listen ble sortert, vi hevder at Jennifer var i stand til å gjøre
fundamentalt bedre.
7 dører, ja, er ikke så interessant, men antar at det er vi 7 millioner dører.
Logg av n er definitivt kommer til å utføre mye, mye
raskere i det lange løp.
Men hun måtte ha dører sortert for henne.
Nå tok jeg meg den frihet å gjøre det på forhånd på dataskjermen
her, men antar at Jennifer måtte gjøre det selv?
Anta at dørene aktuelle representert data i en database, eller
venner registrert for Facebook, eller noen nettsider på internett som
ulike nettsteder kan trenge å indeksere eller søk over.
>> Anta at du bare hadde en rådata satt, og det ble overlatt til deg, eller til
Jennifer å gjøre at sorteringen?
Det, snarere krever at vi svarer spørsmålet, vel, hvor mye tid
ville ha tatt Jennifer, eller til og med meg, å sortere disse tallene på forhånd slik
at hun kunne dra nytte av det?
Høyre?
Fordi implikasjon, selvfølgelig, er om det tar meg en stund å sortere
tallene, hvem pokker bryr seg at du kan finne et tall som 50 så fort,
som i Jennifer sak, hvis vi mer enn tatt over den totale mengden av tid
det tok ved å sortere ting på forhånd?
>> Så la oss se om vi kan ikke male bildet her.
Jeg har en hel haug mer stress baller, hvis det hjelper
bryte isen her.
Og hvis du ikke har noe imot det vi trenger syv frivillig -
på, OK.
Wow.
Så vi ikke trenger å bruke på skrivebord lamper, synes det.
OK.
Så hva med deg to foran.
Hva med deg to gutta i ryggen.
Så det er fire.
Hva med deg foran fem, seks og sju.
Akkurat der.
Din venns peker deg ut, slik at du får premien.
>> OK.
Kom opp.
Og hvorfor ikke vi har deg gutta kommer på over her.
Jeg kommer til å gi deg hver et nummer.
Og gå videre og ordne selv identisk til hva som er
avbildet på skjermen.
>> [Interposing STEMMER]
>> DAVID J. MALAN: Oop, beklager.
Bug.
OK.
Vel, her vi går.
Nummer fem.
Nummer seks.
En, to, tre, fire, fem, seks, sju.
Å, dette er vanskelig.
>> SPEAKER 2: Jeg skal bare få en -.
>> DAVID J. MALAN: Good deal.
OK.
Takk for at du deltar.
>> [APPLAUSE]
>> OK.
OK.
Så vi har fire, to, seks, ett, tre, sju, fem.
Perfeksjonere så vi har syv frivillige her som er lik i bredde til
array som vi spiller med tidligere.
Og jeg valgte syv grunner som vil være like
praktisk i en liten bit.
Og jeg kommer til å foreslå første som vi sorterer disse syv frivillige.
Hvis du ønsker, først, for å si hei skjønt.
Siden dette kommer til å bli en klosset flere minutter.
Introdusere dere.
>> GRACE: Hei, jeg er Grace.
Jeg er en sophomore i Leverett House.
>> Branson: Hei.
Jeg er Branson.
Jeg er en førsteårsstudent i Weld.
>> Gabe: Hei.
Jeg er Gabe.
Jeg er en junior i Cabot.
>> NEIL: Jeg er Neil.
Jeg er en førsteårsstudent i Matthews.
>> JASON: Jeg er Jason.
Jeg er en førsteårsstudent i Greenough.
>> MIKE: Jeg er Mike.
Jeg er en førsteårsstudent i Grays.
>> JESS: Jeg er Jess.
Jeg er en sophomore i Leverett.
>> DAVID J. MALAN: Excellent.
OK.
Vel, takk til alle våre frivillige her så langt.
Og utfordringen for hånden nå kommer å være å sortere av disse gutta, men da
vi er nødt til å tenke litt hardt om hvor effektivt vi faktisk
sortert dem.
Så la oss først prøve dette.
Dere kan se hverandres tall bare ved å plassere rundt hjørnene.
Gå videre og ta noen sekunder, og sorter dere fra minste på
igjen til største på høyre side.
Go.
>> OK.
Bra.
Det var virkelig darn fort.
Nå noen her, hva var algoritmen at disse gutta brukt?
>> SPEAKER 1: Minst til størst.
>> DAVID J. MALAN: OK.
Minst til størst er liksom virkelig av objektiv, men jeg er ikke sikker på at det
virkelig en algoritme.
Minst til størst forteller ikke meg steg for steg hva du skal gjøre.
Yeah?
>> SPEAKER 1: [uhørlig]
>> DAVID J. MALAN: OK.
Så hvis du ser en person mindre enn nummeret ditt, og deretter flytte til
til venstre for seg.
Så det er nå får mer uttrykksfulle, mer som en algoritme, fordi du
kan si, hvis dette, da.
Så vi har en slags betinget konstruksjon.
Og disse gutta syntes å gjøre at noen ganger, fordi noen av dere flyttet litt
fra en avstand.
Så det var antagelig en slags looping skjer i deres sinn.
>> Men la oss prøve å formalisere det.
Hvis dere kunne tilbakestille tilbake til denne ordningen.
La oss se om vi ikke kan formalisere dette en bit, og deretter stille spørsmålet, bare
hvor effektiv er dette?
Selvfølgelig, når vi gjør dette saktere, det kommer til å føle seg så godt av
en algoritme, men la oss se om vi kan sette våre fingre på den nøyaktige fremgangsmåten.
>> Så dere to gutta er fire og to.
Eller du riktig eller feil rekkefølge?
Åpenbart feil.
Så vi byttet.
Nå skal jeg flytte på seg her og si, 05:56.
Er du riktig eller gal?
>> Gabe: Riktig.
>> DAVID J. MALAN: Riktig.
Seks og en?
Nope.
Bytte.
Så det er to swapper.
Seks og tre?
Nope.
Bytte.
Seks og sju?
Ser bra ut.
Syv og fem?
>> JESS: [uhørlig]
>> DAVID J. MALAN: OK, bytte.
Og sortert.
OK.
Så åpenbart ikke, ikke sant?
Så det var mer å gå på.
Men, ja, disse gutta, selv bare instinktivt.
holdt flytte.
De hadde ikke bare stoppe, når de korrigert ett problem.
So.
Ja, jeg kommer til å ha å gjøre det samme.
Jeg er nødt til å sortere av spole tilbake til begynnelsen av dette problemet,
eller begynnelsen av denne rekke mennesker, la oss begynne å kalle dem.
>> Og nå hva skal min algoritme i andre omgang være?
>> SPEAKER 1: Samme greia.
>> DAVID J. MALAN: Samme greia.
Og dette, jeg begynner å like, ikke sant?
Så snart du kan finne deg selv gjør det samme igjen og igjen, det er
bli mer lik en algoritme, og mindre menneskelig instinkt.
>> Så nå er vi i gang igjen.
To og fire?
Nei.
Fire og en?
Ah, det var faktisk noen jobber fortsatt må gjøres.
For og tre?
Bra.
Fire og seks?
Seks og fem?
Seks og sju?
OK, nå gjort.
OK, nei.
Jeg må gå tilbake.
>> Så nå, igjen, vi gjør dette litt mer bevisst.
Og nå er det bare én hjerne utførelse av denne algoritmen.
En CPU, hvis du vil.
Og ærlig talt, det er den eneste ressursen vi kommer til å ha tilgang til.
Og når vi går tilbake til et tastatur og har noe sånt som C ved vår
disposisjon, vi bare skriver et program som kan gjøre én ting om gangen.
Mens disse gutta et øyeblikk siden, vi leveraged sin kollektive hjernekraft
som dere gjorde i uke null.
Så la oss fortsette å gjøre dette.
>> To og en.
To og tre.
Tre og fire.
Fire og fem.
Fem og seks.
Seks og sju.
Ferdig?
Så jeg er, men la meg spille djevelens advokat.
Jeg gjør, hva slags datamaskin som bare gjort en pasning gjennom denne rekke
mennesker, vet at jeg er ferdig?
>> SPEAKER 1: Nei.
>> DAVID J. MALAN: Så hvorfor?
Hva ville jeg trenger å gjøre for å konkludere avgjørende at jeg er ferdig?
Sannsynligvis en mer pass.
Høyre?
Fordi alt jeg vet fra det forrige pass er at jeg rettet en feil.
Og det betyr, kanskje det er fortsatt en annen feil
at jeg trenger å korrigere.
Så jeg kan bare være sikker ved å spole tilbake, og deretter sjekke, en til to, to og
tre, tre og fire, fire og fem, fem og seks, seks og sju.
OK, nå har jeg gjorde noe arbeid.
>> Jeg kan sikkert huske at jeg gjorde ingen jobbe med noe som en variabel,
liker en int.
Kall det swapper, og hvis swapper er 0 når jeg komme hit, og det startet på 0, da
Jeg ville bare være dumt å holde det gående frem og tilbake, kontrollerer på nytt, og
igjen, og igjen, ikke sant?
Fordi du sitter fast i noen slags uendelig loop.
Så så snart det er 0 bytteavtaler, Vi kan hevde at dette
algoritmen er faktisk ferdig.
>> Nå, la oss sette et navn på dette.
Algoritmen som jeg foreslår vi bare implementert er noe som heter boble
slag, som er kjent som sådan i den forstand at tallene som er større type
boble sin vei opp til toppen, eller opp til enden av rekken av tall.
Men hvor effektiv var denne algoritmen?
Hvor mange skritt jeg fysisk må ta for eksempel å sortere de
sju mennesker?
>> Fire til fem?
OK, for mange er slutt kommer til å være svaret.
Men selv da, det nøyaktige antall er ikke så interessant.
La oss generalisere det som n.
Så hvis jeg hadde n folk her oppe, og de var, liksom, i tilfeldig rekkefølge på
begynnelse, i den opprinnelige bestillingen.
Vel, hvor mange skritt jeg har å ta på første pass?
Det var en, to, tre, fire, fem, seks, og de er syv personer, så
det er syv, seks -, så det er n minus ett trinn Første gang.
>> Nå, hvor mange skritt jeg har å ta når jeg spoles tilbake?
Vel, kunne vi faktisk dobbelt så høy som hvis vi virkelig ville, men for nå er jeg
bare kommer til å si, all right, en annen n minus en.
Så n minus 1 kommer til å få irriterende å holde styr på, så la oss
bare runde opp litt.
Så 2n trinn.
Så 14 trinn, gi eller ta.
>> Hvor mange ganger har jeg ta et skritt til neste gang?
Vel, det er 3n.
egentlig.
Og nå, i verste fall, for eksempel, hvor mange ganger jeg har
gått frem og tilbake, frem og tilbake, utførelse av denne algoritmen, bytte
folk på hver passering, omtrent?
Det er faktisk n kvadrat, ikke sant?
>> Fordi i verste fall, kan du typen av tenker om dette intuitivt,
selv om det kan ta litt litt tid til å synke inn
I verste fall, hva ville disse syv personer ha sett ut, i
Når det gjelder arrangementet av sine tall?
Helt baklengs, ikke sant?
Og bare for å simulere det, hva var navnet ditt igjen?
>> MIKE: Mike.
>> DAVID J. MALAN: Mike?
OK, Mike, kan du bare bli med meg over her for bare ett sekund?
Nei, faktisk ikke.
Beklager Mike, la oss spole tilbake.
Hva er navnet ditt igjen?
>> NEIL: Neil.
>> DAVID J. MALAN: Neil.
OK, Neil, kommer du med meg, hvis du ikke tankene.
Så jeg kommer til å foreslå, bare for enkelhet, at Neil er nå i sin
verst tenkelige tilfelle.
Men husker hvordan jeg implementert min algoritme.
Jeg sammenlikne, sammenligne, sammenligne, sammenligne, sammenligne, oh.
Nå er disse gutta er ute av orden, så jeg fikse.
Så dere bytte.
Men tenk nå, hvor mye lenger har Neil å gå?
Det er omtrent n.
Du vet, det er faktisk ikke n.
Det er som, n minus en, men jeg får irritert holde styr på den lille
nummer, så la oss bare kalle det n.
>> Så hvis Neil beveger seg ett skritt maksimalt hver tid, og for å bevege Neil ett trinn,
Jeg må gjøre dette veldig kjedelig pass frem og tilbake, er dette omtrent
gjør dette, n trinn, totalt n ganger, fordi det kommer til å ta meg
at mange tiltak for å få Neil alle veien til der han hører hjemme.
Enn si alle andre hvis dere var alle mis-bestilles i tillegg.
>> Så la oss kalle boble sortere n kvadrat.
Kjøretiden til denne algoritmen, den utførelsen av denne algoritmen, den
effektiviteten av denne algoritmen, vi skal bare beskrive mer
generelt som n squared.
Som er fint, fordi jeg kunne gjøre det samme eksempel med åtte personer, ni
mennesker, en million mennesker, og at Svaret er ikke til å forandre seg.
>> Så hvis dere ikke har noe imot, la oss tilbakestiller du til der du startet.
Og la oss prøve to andre tilnærminger og se om vi ikke kan gjøre fundamentalt
bedre enn dette.
Så denne gangen, kommer jeg til å foreslå en slags annen algoritme.
Det var veldig smart av oss sist, og dere hadde rett til å ha
riktige instinkter bare slags å bytte parvis.
Men hvis jeg virkelig ønsket å nærme seg dette enkelt, og mitt mål er å flytte
alle de små tall denne måte, og skyve alle de store tallene at
måte, hvorfor jeg ikke bare gjøre det i mest naiv måte mulig og se om jeg
kan gjøre det bedre enn det som var en ganske kompleks algoritme?
>> Så la oss se.
Fire er et ganske lite antall, så jeg er kommer til å forlate deg dit øyeblikk.
Ooh, er nummer to enda bedre.
Så kan du bare gå fremover for et øyeblikk?
Dette er tiden min minste nummerert kandidat, og jeg kommer til å huske
at med, liker, en variabel.
Men jeg kommer til å fortsette å se.
Er det noen som har antallet er mindre?
Seks, nei.
Oh, det er Neil igjen.
>> Så jeg kommer til å presse deg tilbake slags konseptuelt.
Neil vil komme frem.
Og nå, den variabelen som jeg bruker til holde styr på hvem som har den minste
nummeret er oppdatert til å inneholde Neil beliggenhet.
Vel, la oss se.
Tre, sju, fem.
OK, jeg vet Neil var den minste.
Hva er den enkleste ting for meg å gjøre nå?
Jeg har ikke tenkt å kaste bort tiden min ved å bare boblende Neil ett sted til venstre.
Hvorfor kan jeg ikke bare sette Neil der han hører til, er som selvfølgelig der?
>> Helt på begynnelsen.
Så Neil, bli med meg.
Og hva var navnet ditt igjen?
>> GRACE: Grace.
>> DAVID J. MALAN: Grace.
OK.
Så Grace, dessverre, du er slags i veien.
Så hvordan løser vi dette problemet?
Høyre?
Hvis dette er en matrise, er det bare syv steder.
Husker at, med Rob, vi snakket om erklære aldre, og vi hadde bare en
endelig antall alder?
Samme ideen her.
Vi har kun et begrenset antall ints.
Grace er slags i vår måte, så hvordan vi fikse?
>> Den enkleste måten er like, Grace, beklager.
Du er nødt til å gå over det slik at vi kan få plass.
Nå, hvis du tenker på dette, kanskje vi bare gjort problemet verre.
Og kanskje vi gjorde, fordi hva om Grace var på rett sted?
Men vi vet hun ikke, fordi ellers, ville hun ha vært
står frem i stedet for Neil på denne tiden, ikke sant?
Vi har allerede sjekket nummeret hennes ut.
>> OK.
Så nå, Neil på rett sted, og Jeg kan gjøre en liten optimalisering.
For det neste minuttet, kommer jeg til å ignorere Neil alt sammen, slik at de ikke
kaste bort sin tid, eller ved et uhell bytte ham til feil sted.
Så nå, hvordan kan jeg finne den neste element som er minste?
To.
Det er en ganske god del, hvis du ønsker å stå frem og
Jeg vil huske deg.
Seks, ikke bra.
Fire, tre, sju, fem, ikke bra.
Så la meg flytte deg til din rett sted.
Og vi bare hadde flaks denne gangen.
>> Nå kommer jeg til å ignorere disse to gutter, og nå gjør en mer
passere gjennom dette.
Seks, som en ganske lite antall.
Kom frem.
Oh, beklager.
Grace nummer er bedre, så gå på fremover.
Fire.
Beklager, Grace.
Gå tilbake igjen.
Nummer tre er bedre.
Seven.
Fem.
Og nå hva heter du igjen?
>> JASON: Jason.
>> DAVID J. MALAN: Jason.
Så Jason er nå den minste element jeg har valgt.
Hvor er han kommer til å gå?
Så hvor seks er.
Og navnet ditt er igjen?
>> Gabe: Gabe.
>> DAVID J. MALAN: Gabe.
Gabe er i veien.
Hva er den enkleste tingen å gjøre?
Bytt disse to gutta og fortsette.
Så nå la oss se.
Hvem er den minste?
Fire.
La meg bare slags jukse.
Fem kommer til å være den minste.
Jeg finner neste, hvis du ønsker å gå fremover, hva jeg har å gjøre med
disse gutta, med Gabe?
Bytte igjen.
Så nå, fortsatt litt ute av drift.
Jeg fant Gabe å være den minste, så Jeg pop ham ut, flytt dere over.
Og gjort.
>> Så svar er den samme.
Sluttresultatet er det samme.
Hvilken av disse to algoritmene er bedre?
Den andre, hørte jeg.
Hvorfor?
>> SPEAKER 3: Det er n trinn [uhørlig].
>> DAVID J. MALAN: Det er n trinn på de fleste.
Interessant.
Så er det om?
Så hvordan jeg finner minste elementet?
Hvor mange skritt jeg må ta den finner det minste elementet?
Jeg hadde en ser hele veien i enden, til høyre?
Fordi i det verste tilfellet, hva hvis Neil var over her?
Så bare å finne det minste elementet tar meg n trinn, eller n minus en.
Men, OK.
Så fikse Neil.
Husk at et minutt eller så siden.
>> Men hvordan gjorde jeg finne neste minste elementet?
Det er n 1 minus, eller n minus to egentlig, fra antall trinn.
Så OK.
Så jeg gjorde n minus to.
OK.
Så det føles litt bedre.
OK.
Hvor mange skritt neste gang å finne nummer tre?
Så n minus fire.
Så det er avtagende, en færre tråkke på hver iterasjon.
Så dette føles bedre, ikke sant?
Hvis siste gang var det omtrent n ganger n, denne gangen er det n en minus, pluss n minus
2, pluss n minus tre, pluss n 4 minus, prikk, prikk, prikk.
Men hvis du huske fra videregående skole lærebøker, den lille jukse
ark på baksiden som har formler, hvis du legger opp denne serien av tall,
det som er det totale antall skritt kommer til å være at jeg tar her?
>> Dette er en av dem, som, n minus 1, ganger n, delt på to.
Så la meg se om jeg kan trekke dette opp for bare et øyeblikk.
Og igjen, jeg er litt avrunding noen tall bare for å holde våre liv enkelt,
men som jeg husker, er det noe sånt hvis Jeg gjør n minus en ting, så n minus
2, deretter n minus 3, er det omtrent noe sånt som dette over to, og hvis jeg
multiplisere dette ut, det er faktisk n torget.
Det er ikke følelsen bra. n minus n enn to.
>> Men her er tingen.
I informatikk, når problemene begynner å bli interessant er når n
blir veldig stor.
Og når n blir veldig store, som av disse verdiene kommer til å dominere hele
av de andre?
Det er slags n squared, ikke sant?
Ja, dividere med 2 er ganske bra.
Men hvis du snakker om milliarder biter av data, eller billioner av
biter av data, ok, så du er dobbelt så rask.
Men hvem bryr seg egentlig om det store antall, dersom denne faktoren er det som får
større og større.
Og sikkert, gjør det mer av en forskjell enn denne fyren.
Så selv om dere er rett, andre algoritme, kan vi kalle det
utvalg sortere, er, i den virkelige verden, en litt raskere potensielt, fordi jeg er
ta færre og færre trinn hver gang.
>> Det er egentlig ikke fundamentalt raskere.
Fordi hvis vi faktisk spille ut dette for store verdier av n, i enden av
dagen, for stor nok n, er det fortsatt kommer til å føle seg ganske treg.
Vel, la meg ta ett siste pass på det.
Det er det jeg vil kalle utvalg slag.
Kan dere nullstille dere en siste gang?
Og i dette siste tilfellet, kommer jeg til å foreslå noe
kalt innsetting slag.
Innsetting slags vesen, konseptuelt, litt annerledes.
>> Snarere enn å gå frem og tilbake og velge det minste elementet, jeg
bare kommer til å håndtere hver av disse gutta som jeg møter dem, og sett
dem inn i sin rette plass.
Så jeg skal bare starte med Grace, og jeg ser at hun er nummer fire.
Hvor hører nummer fire?
Jeg har ikke begynt å sortere noe, så Grace får å bo der.
Og nå skal jeg til å kreve, hvis du kunne ta et skritt til høyre, dette
min sortert liste, dette er min usortert gjenværende listen.
Så nå skal jeg fortsette neste, og hva heter du igjen?
>> Branson: Branson.
>> DAVID J. MALAN: Branson.
Så Branson er nummer to.
Så jeg kommer til å ta deg ut for en stund.
Og nå trenger der du hører hjemme i denne matrisen?
Så til høyre for Grace.
Så igjen, er vi på en måte som gjør Grace gjøre mye arbeid her.
Hvor plasserer vi deg?
Så vi kommer til å skyve deg til igjen, og sett Branson der.
Men nå har jeg hevder at dere er ferdig.
Men legg merke til, jeg bruker ikke ekstra plass.
Det er fortsatt to elementer her, fem over her.
Total gitterstørrelse er 7, så jeg er ikke juks, ok?
>> Så nå har vi, med Gabe her, den nummer seks, hvor hører du til?
Du hadde flaks igjen.
Så du får bo der.
Bare ta en liten steg til høyre bare for å gjøre det klart at du er sortert.
Og nå har vi Neil igjen, antall en, hvor går du?
Og er nå der vi vil begynne å se at denne algoritmen, men på første
øyekast, føles ganske smart, se hva som er i ferd med å skje.
Hvis du kunne gå fremover.
>> Hvor ønsker vi å sette Neil?
Så åpenbart her, så hvordan får vi Neil der?
La oss gjøre dette steg for steg.
Gabe, der trenger du å reise?
Jepp, så ta ett stort skritt, eller to halv-skritt for å gjøre
ett skritt der borte.
Grace, hvor du går?
Bra.
Så et annet trinn.
Og til slutt, Branson?
Et annet skritt.
Og nå kan vi sette Neil på plass.
>> Så nå, fortsetter denne logikken.
Selv om vi ikke er skiftende Neil over, og over og over, for å sette ham
hvor han går, i verste fall, neste nummer vi kan støte kunne
være nummer, si, var det en rekke null, så vi kommer til å skifte alle
disse gutta.
Anta at det er et tall, negative en, så vi må skifte
alle disse gutta.
Så vi er egentlig bare slags bla problemet rundt, slik at vi er
overføring bekostning fra utvelgelsesprosessen så innsetting
prosessen, slik at dere bare hadde å flytte omtrent n minus noe
antall trinn.
Og at antall skritt er bare kommer å øke etter hvert som jeg velger flere numre,
hvis jeg må holde dytter dere tilbake, og tilbake, og tilbake.
>> Så det triste er nå alle disse algoritmer er n kvadrat.
La oss gå videre og takket være disse gutter, og visualisere disse litt
annerledes.
Veldig godt gjort.
>> [APPLAUSE]
>> OK.
Der du går.
Takk for -
>> Branson: [uhørlig] holde tallene.
>> DAVID J. MALAN: Nei, det kan du holde tallene i tillegg.
OK.
Pent gjort.
OK.
Så la oss se om vi ikke kan nå oppsummere raskere, og mer visuelt,
nøyaktig hva som skjedde her følger.
Jeg kommer til å gå videre og trekk opp Firefox.
Vi vil knytte denne demonstrasjonen på kurset hjemmeside.
Java er litt irriterende å få jobbe i enkelte nettlesere disse dager.
Så hvis du kan leke med dette hjemme, skjønner du kanskje trenger å bruke Firefox
for å få det til å fungere.
Og hva jeg skal gjøre med dette demonstrasjon er følgende.
>> Nederst har jeg en hel haug med menyvalg, inkludert en start og en
stopp-knappen.
Også, som en side, synes det å være en bug i disse programmene, der du
kan faktisk ikke se starten eller stoppe knappen med mindre du nede Kommando eller Alt
pluss og zoom inn, som merkelig nok viser deg flere knapper.
Så bare så dere vet det hvis du spiller med dette hjemme.
Nå skal jeg til å klikke på Start på bare en øyeblikk, etter å ha angitt en forsinkelse på,
liker, 200 millisekunder her, bare så vi kan se hva som skjer.
>> Så jeg påstå at dette er en visualisering av den første algoritmen
disse gutta gjorde, boble sortere, der vi byttet folk parvis.
Nøkkelen innsikt til denne visualiseringen er at høyden på stengene
representerer størrelsen av nummeret.
Så høyere søylen er, desto større antall.
Kortere baren, mindre tall.
Og hvis du legger merke til, vi går gjennom den første iterasjon av denne algoritmen,
swapping store og små tall, slik at det lave antallet kommer først og
det store antallet går til høyre.
>> Og så snart vi får på slutten av matrise av mange flere tall enn syv, vi
kommer til å gå tilbake til begynnelsen.
Og forutse dette.
Helt til venstre, er at lille fyren kommer å bytte til siden, og dette
prosessen gjentas.
Nå er denne visualiseringen blir raskt kjedelig, så la meg gå videre og stoppe
det, endre forsinkelsen noe mye raskere bare for å få nå, en følelse for
denne algoritmen.
>> Så selv om jeg har sped det opp, er dette som å oppgradere min prosessor, kjøpe
en ny datamaskin.
Jeg har ikke fundamentalt forandret mitt algoritme, men du kan faktisk se mer
tydelig enn med mennesker, at de store tall bobler opp til toppen,
og de små tall bobler ned til bunnen.
Og nå denne tingen her sortert.
Og som en side, i rutene, er det bare noen bokføring der for å
hjelpe deg å telle hvor mange sammenligninger, eller hvor mange swaps har
faktisk blitt gjort.
>> Vel, la oss prøve en av de andre vi så.
La meg klikk på boble sortere her, og la meg velge, og hele denne nettsiden
er litt buggy.
La oss akseptere risikoen og kjøre den på nytt.
Det vi går.
Så la oss gjøre utvalget slag.
Jeg vet ikke hvorfor menyen vises der borte.
La oss zoome inn for å fikse det bug, endre dette til 50 år.
Ah, la oss faktisk gjør så mye raskere.
Fem millisekunder eller så, og Start.
>> Så dette er utvalget slag.
Så igjen, tenke på hva vi gjorde med menneskene her oppe.
Vi gikk gjennom matrisen og valgt det minste elementet igjen,
og igjen og igjen.
Nå har jeg hevder det var fortsatt ganske dårlig.
Det var fortsatt n kvadrat, gi eller ta, men det var i den virkelige verden, litt
raskere, fordi jeg var faktisk å ta litt færre trinn for hver gang.
Men vi bare snakker hva?
Kanskje 40 eller så barer her?
Vi snakker ikke 40 millioner.
Så det er ikke klart helt for meg at var faktisk en betydelig gevinst.
>> La meg nå gå tilbake og endre til vår tredje algoritme, som ble velge
innsetting slag.
Og nå er det virkelig buggy fordi Menyen egentlig ikke burde være der nede.
Så nå skal vi bla tilbake her og starte denne algoritmen.
Whoop, start og stopp.
Så denne typen har en pen mønster til det, der vi er igjen
setter mennesker, eller i dette tilfellet, barene inn
deres passende sted.
Og det er allerede gjort før Jeg snudde meg rundt.
Men dette også, i teorien, er fortsatt n kvadrat.
>> Så la oss se om vi ikke kan oppsummere disse følger.
Jeg kommer til å gå videre og bare for å gi oss liksom en vanlig måte å snakke
om disse tingene, la meg introdusere bare litt av notasjon her.
Du er i ferd med å se noe som kalles big O, fordi det er bokstavelig talt en stor
O. Og dette er en måte som en datamaskin forsker eller en matematiker selv bruker
å beskrive kjøretiden av noen algoritme.
Hvor mange skritt betyr det egentlig ta?
>> Nå skal jeg noe dumt med håndskriften min her i bare et øyeblikk.
Men la meg gå videre og si at dette vil være stor O over her.
Og la meg presentere en annen symbol, en kapital omega.
Omega kommer til å være det motsatte, hovedsak, av stor O. Mens big O
betyr, i verste fall, hvor mye tid kanskje noen algoritme ta i
form av n, er omega skal være hvor mye tid kanskje det
ta i beste fall.
Og vi får se hva vi mener med beste fall på bare et øyeblikk.
>> Så la oss starte noe enkelt.
La meg starte med en lineær søk.
Så ikke sortering.
Vi kaller dette lineære søket.
Og nå, gjøre litt tabell ut av dette.
Og nå, i tilfelle av lineære søk, i verste fall, hvor mange skritt er
det kommer til å ta meg med å finne en antall vilkårlig valg?
Og det er n antall dører eller n totaltall.
Worst case.
Hvor mange skritt jeg nødt til å ta for å finne antall 50 i en matrise
av n dører?
Og hvorfor?
Fordi det kan være alle vei over på enden.
Så mye som Jennifer møtte, den nummer 50 var helt over, så i
verste fall lineær søk er big O n, vil vi si.
>> Hva om beste fall, hvis du får virkelig heldig?
Det er bare kommer til å ta ett skritt, eller et konstant antall skritt.
Så vi vil beskrive det som en.
Så dette er ganske bra.
Hva nå hvis vi gjorde noe liker binære søk?
Så binære søk i verste tilfelle, tok hvor mye tid?
>> [Interposing STEMMER]
>> DAVID J. MALAN: Så egentlig, jeg hørte det på et par steder.
Så det er logger faktisk n, gi eller ta, fordi som vi dele opp listen i to
igjen, og igjen, og igjen, er vi i stand å finne, til slutt, verdien,
hvis den er der, men det er en hake.
Hva er antagelsen om at vi må ta for gitt for binære søk?
Det må være sortert.
Det er ikke sortert, kan du dele ting i to igjen og igjen, og du
kan gå til venstre, og du kan gå rett, og du kan gå til venstre og høyre, men du er
ikke kommer til å finne elementet hvis listen er ikke sortert, fordi
du kan gå glipp av det.
Fordi heuristisk din, for å gå til venstre eller høyre kommer til å være feil hvis det er
faktisk ikke sortert.
Så det er liksom en skjult kostnad å bruke noe sånt som dette.
>> Nå, la oss gå inn sortering vår algoritmer ikke søker -
oh, faktisk la oss gå i denne tomt.
Binære søk i beste fall?
Det er også en hvis det bare skjer for å være i selve midten av matrisen, eller
midt i telefonkatalogen.
Nå la oss gjøre boble slag.
Så igjen, nå er vi inn i sorterer, ikke søk.
>> I verste fall, gjorde hvor mange skritt vi krav boble sortere kommer til å ta?
n squared.
Så jeg kommer til å trekke det.
Ooh, ser håndskriften min enda verre når det er anslått at stort.
OK.
Så det er n kvadrat.
Og i beste fall av boble sortere, hvor mange skritt det kommer til å ta?
1, hørte jeg.
>> SPEAKER 1: n.
>> DAVID J. MALAN: n, hørte jeg.
>> SPEAKER 1: 2.
>> DAVID J. MALAN: 2, hørte jeg.
Hører jeg tre?
OK.
Så jeg har hørt en, n, to, men la oss plukke fra hverandre i det minste den første av disse
forslag, en.
Det er ikke et dårlig instinkt, fordi det slags følger et mønster her.
Men hvis det tar bare ett trinn, hvordan i verden kunne jeg hevde at listen
sorteres, fordi hvis jeg bare lov å ta en trinn, hvor mange deler
kunne jeg faktisk sjekke for å være sikker?
Vel, bare en, noe som betyr at det er n minus 1 elementer som kan være ute av
orden, og jeg skal bare på tro etter ser på en del at
ting blir sortert.
Så en er ikke riktig her.
Så minimalt, hvor mange må jeg se på?
>> [Interposing STEMMER]
>> DAVID J. MALAN: n minus en, eller egentlig, n, fordi jeg trenger å se på hver
element for å sikre at det er ikke ute av drift.
Men igjen, vi vil liksom bølge vår hendene på de mindre tall og
anta at, som n blir stor, er de uinteressant uansett.
Så det er boble slag.
Og nå, la oss gjøre disse to siste.
Utvalg sortere og så får vi gjøre innsetting slag.
Og så vil vi blåse sinn med noe mye
bedre enn alle disse.
OK.
>> Hva er det verste tilfellet kjører tidspunktet for valget slag?
>> SPEAKER 4: n kvadrat.
>> DAVID J. MALAN: n kvadrat, jeg hører.
Men hvorfor n kvadrerte, intuitivt?
>> SPEAKER 4: Fordi vi bare gjorde det.
>> DAVID J. MALAN: Fordi vi bare gjorde det.
OK.
Godt svar.
Men intuitivt, hvorfor er utvalget sortere n kvadrat?
Hva gjorde vi har å gjøre igjen og igjen?
Vi måtte fortsette å søke gjennom, er du den minste, er du den
minste, du er den minste.
Og gitt, var vi i stand til å ta n trinn, deretter n 1 minus, da n minus to.
Men hvis du slags legge dem alle opp, eller ta det på tro at jeg har lagt
dem opp på forhånd, får vi omtrent n squared minus noen mindre tall.
Så jeg kommer til å kalle dette n kvadrat.
Men med valget sortere på best tilfelle, hvor mange skritt er det
kommer til å ta meg?
>> SPEAKER 5: [uhørlig]
>> DAVID J. MALAN: Det er dessverre fortsatt n kvadrat, ikke sant?
Fordi hvis jeg velger den minste element, og vi hadde syv personer her,
Jeg bare vet, når jeg kommer til selve slutt, at jeg har funnet den minste
nummer, uansett hvor han eller hun kan ha vært.
Men hvordan finner jeg den neste minste tallet?
Jeg må gjøre en annen pass.
Så i beste fall, hva er innspill til utvalget slag?
Det er en allerede sortere listen, nummer en, nummer to, for det tredje nummer fire.
Men jeg er en datamaskin.
Jeg kan bare se på en ting om gangen.
Jeg kan ikke liksom ta et skritt tilbake som et menneske og si:
ooh, dette ser riktig.
>> Jeg kan bare avgjøre riktigheten i utvalg sortere ved å velge
minste tallet.
Men selv om jeg finner nummer én første, hvis jeg ikke vet noe annet om
de andre tallene, som jeg ikke gjør det, alt jeg vet at jeg har blitt overlevert en matrise
eller et sett med dører bak som er tall, den eneste måten jeg vet at en
var den minste?
Hvis jeg får hele veien her og realisere, faen, var en faktisk den minste.
>> Men hvordan gjør jeg da bestemme at to er den neste, mindre?
Ved å gjøre det samme ineffektivitet igjen og igjen.
Så til slutt, med innsetting sortere, hvordan, i verste fall,
vi sier det utfører?
Det også er n kvadrat.
Og hva med den beste saken?
Vi vil forlate det som en cliffhanger.
Vi skal fylle ut en blank neste gang, men først la meg foreslå at vi
fundamentalt gjøre det bedre enn alle disse, ok?
>> Så tenk selv hva innsetting sortere kommer til å bli.
Vel, det var ikke veldig dramatisk, fordi jeg er den eneste
som så forandringen.
Wow.
OK.
Så her har vi en noe annen demonstrasjon.
Hvis jeg zoome inn her, vil du se at på venstre vi har boble sorter, i
midten har vi utvalg sortere og på helt til høyre, har vi noe vi
har ikke sett på ennå kalt flette slag.
Men tenk på hva vi har vært gjør her så langt i dag.
Når Jennifer først kom opp på scenen, vi gikk gjennom rekken av tall
igjen og igjen, med lineær søk, og vi fikk lineær kjøretid, big O
av N, så å si.
>> Når vi nå vurdere den første uken av klasse, da vi hadde splitt og hersk,
og vi hadde telefonboken rive, og Jennifer, og vi kollektivt
leveraged at viktig innsikt, som var å gjenta deg selv igjen og igjen av
en eller annen måte å kaste bort, kaste bort, kaster bort halvparten av problemet, eller
generelt, dele et problem i to, og deretter behandle mindre stykke av
problemet som konseptuelt tilsvarende til den annen, vi noe gjorde
fundamentalt bedre.
Men med boble sortere, med utvalg sortere, med innsetting sortere, vi har kanskje
ingen slike innsikt som Jennifer gjorde.
Vi har ganske mye bare gikk frem og frem en hel haug med ganger, og vi
forskjøvet ting litt, bytte i denne rekkefølgen, kanskje
innsetting eller velge.
Men på slutten av dagen, gjorde jeg mye av klosset vandre frem og tilbake.
Vi gjorde egentlig ikke utnytte noe smart som Jennifer gjorde som å dele
og erobre.
>> Så flette sortere, derimot, som vi vil ikke se før neste uke, kommer det til
å utnytte at nøkkelen ideen ved å dele input, og deretter å halvere, og deretter
halvere, og deretter halvere.
Og på hver gjentakelse av den bue, sortering venstre halvdel, og retten
halvparten, deretter den venstre halvdelen av venstre halvdel, og den høyre halvdel av den venstre, deretter
den venstre halvdel av den høyre halvdel, og den høyre halvdelen av den høyre halvdel.
Og gjenta igjen og igjen.
>> Så vil du se dette visuelt, men dette er hva som venter oss neste uke.
Og generelt, når vi tenker litt litt hardere på slike problem.
Vi har n kvadrat på venstre, n kvadrat i midten, og n
logge n til høyre.
Så det er ditt virkelige cliffhanger.
Vi ser deg på mandag.
>> [APPLAUSE]