>> [MUSIC SPILLE]
>> DAVID J. MALAN: Dette er CS50.
Og dette er starten på uke tre.
Så vi har fått mange spennende ting å dekke i dag.
Mange muligheter for frivillige opp på scenen.
Og til slutt, er i dag ikke om kode i det hele tatt.
Men det handler om ideer, og det handler om algoritmer,
og faktisk bringe tilbake noe av erfaringene fra uke null,
hvor tilbakekalling, vi introduserte denne uhyrlighet.
Og lån inspirasjon fra det, til å begynne
å løse stadig mer sofistikerte problemer algoritmisk.
Men først et par kunngjøringer.
Så en, hvis du ønsker å delta CS50 ansatte og klassekamerater til lunsj
denne fredagen, både her og i Cambridge, og i New Haven,
vennligst besøk kursets nettside, hvor en URL kan bli funnet.
Forelesning denne onsdagen vil ikke være her i Sanders.
Det vil være online bare, så tune inn på CS50 hjemmeside,
enten her i Cambridge eller New Haven også.
>> Og så problemet satt to- er allerede i hendene.
Hvis du ikke har kastet seg ennå, la meg å tilby den sterkt formulert forslag
det, spesielt nå, som problemet setter forhånd,
du virkelig ønsker å starte nå, hvis ikke prøve seg litt i helgen eller før
når de først går ut på Fredager, fordi du vil
finner ut at de ikke nødvendigvis blir lengre eller mer utfordrende per
SE.
Jeg tror du vil finne at i Generelt har de en tendens til å ta omtrent
rundt samme tid.
Men det sikkert an på student, og det
avhenger av tankegangen som du nærmer deg den.
Men alltid, du kommer å kjøre opp mot noen vegg,
og du kommer til å treffe noen feil, og du er bare
ikke kommer til å være i stand til å komme over det på et tidspunkt.
Og det er enormt verdifullt å kunne å gå bort, komme tilbake neste dag,
gå til kontortid, innlegg på CS50 Diskuter eller lignende, for å faktisk få låst opp.
Så hold det i tankene.
Starter tidligst mulig er det beste du kan gjøre.
Så her er der vi startet klassen, over i uke null.
Og kan vi få en frivillig her for å hjelpe meg å finne mikrofoner?
OK.
Står opp allerede.
Kom opp.
Antar det er hvordan det kommer til å fungere.
Hva er navnet ditt?
ALAN ESTRADA: Alan Estrada.
DAVID J. MALAN: Alan Estrada.
Kom opp.
Hyggelig å møte deg.
ALAN ESTRADA: Hyggelig å møte deg.
DAVID J. MALAN: Og du var her med oss ​​i uke null, selvfølgelig.
ALAN ESTRADA: jeg var.
Jeg var.
>> DAVID J. MALAN: Så kan du gå fremover og finne for oss Mike Smith,
så fort du kan?
Så fort du kan.
Bokstavelig talt rive problemet i halvparten så du må.
>> ALAN ESTRADA: Um.
DAVID J. MALAN: Bokstavelig rive problemet i to.
>> ALAN ESTRADA: Oh.
Mm.
Veldig bra.
>> DAVID J. MALAN: OK.
Good.
Takk.
ALAN ESTRADA: Veldig bra.
OK.
>> DAVID J. MALAN: Og så nå, du har whittled det ned
halvparten av størrelsen av problemet.
Nå er vi ned til en fjerdedel.
Er du betaler oppmerksomhet til hvilken side vi holder?
>> [Ler]
>> ALAN ESTRADA: Ja, think-- jeg
>> DAVID J. MALAN: Hva seksjonen er vi i?
ALAN ESTRADA: Lyddempere, så.
>> DAVID J. MALAN: OK.
Men Mike Smith kommer å være etter lyddempere.
So--
>> [Ler]
>> Greit.
ALAN ESTRADA: Hvor er vi på jakt?
DAVID J. MALAN: Mike Smith.
ALAN ESTRADA: Mike Smith.
DAVID J. MALAN: Nå er vi i kirurgisk.
Nå, leger.
Now--
>> ALAN ESTRADA: Let's- la oss gå med ekte.
Ekte.
>> DAVID J. MALAN: Real.
OK.
Hvis du trenger Real.
Nå, hvilken vei er Mike Smith?
>> ALAN ESTRADA: Denne måten.
>> DAVID J. MALAN: Hvilken vei?
ALAN ESTRADA: Vent.
M er-- rett?
Vi startet with--
>> DAVID J. MALAN: Yeah.
De sitter igjen.
Din rett.
>> ALAN ESTRADA: Yeah.
>> DAVID J. MALAN: Så Mike her inne.
ALAN ESTRADA: Hva?
>> [Ler]
>> Dårlig eksempel, folkens.
Unnskyld.
DAVID J. MALAN: Dette vil lære du til å hoppe ut av stolen.
>> ALAN ESTRADA: Oh.
Oh.
Jeg har deg.
Oh.
Dette er-- OK, jeg har deg.
Smith akkurat her?
>> DAVID J. MALAN: Smith, takk.
Så jeg skal holde utkikk opp Smith?
>> ALAN ESTRADA: Å, ja.
Nei nei nei.
Å nei.
Dette er mitt.
>> DAVID J. MALAN: Åh, du fikk Smith.
OK.
>> ALAN ESTRADA: Ja, jeg fikk Smith akkurat her.
Sorry, folkens.
Jeg trodde Michael-- vi var ute etter Michael.
Unnskyld.
>> DAVID J. MALAN: Det er OK.
Greit, nå er vi inn Paccini and Sons.
>> ALAN ESTRADA: Paccini og sønner.
DAVID J. MALAN: Bare du og jeg er med på dette.
OK.
Finn oss Mike Smith.
Smith.
>> ALAN ESTRADA: Smith.
>> DAVID J. MALAN: Smith.
Vi er i R for søppel.
ALAN ESTRADA: Søppel.
Oh.
Dette kommer til å ta en stund.
>> [Ler]
DAVID J. MALAN: Sko.
Vi er i sko.
>> ALAN ESTRADA: Nå er vi gonna--
>> DAVID J. MALAN: Nice.
ALAN ESTRADA: Which--
[Ler]
Oh, dette er flott.
[Ler]
>> DAVID J. MALAN: Det er OK.
>> ALAN ESTRADA: Åh, dette er bra.
Jeg tror ikke jeg kommer til å har PSAT kompiser etter dette.
DAVID J. MALAN: Good.
Sporting.
ALAN ESTRADA: Sporting.
Um, L, M, N, O, P.
DAVID J. MALAN: OK.
Så la oss rive denne i to.
Det er greit.
Dette ender dårlig uansett, fordi Mike Smith vil ikke være i gule sider.
>> ALAN ESTRADA: Aw.
>> DAVID J. MALAN: Nei, det er OK.
Men la oss late som han er på denne siden.
Så nå har du whittled problemet ned til én side, og vi fant Mike Smith.
>> [Jublende]
Ok takk.
OK.
Det var ekstraordinært.
Men det var fortsatt raskere enn lineær søk,
hvor vi starter på begynnelsen av boken,
og vi flytter vei fra venstre til høyre, til slutt ute etter Mike Smith.
Og så, hvis telefonboken hadde kanskje 1000 sider,
kanskje det ville ha tatt oss 10 eller så siden tårer.
>> Men du har kanskje utnyttes rørte en antagelse
under alt dette, det vil si at telefonboken på forhånd var det?
PUBLIKUM: Sortert.
DAVID J. MALAN: Det er sortert.
Høyre?
Den er sortert alfabetisk, så at alle disse navnene og numrene
sorteres fra A til Z-tallet, og alfabetisk i mellom.
Men i dag, har vi nå spør spørsmålet, vel,
hvordan gjorde Verizon eller telefon Selskapet får det inn i denne tilstanden?
>> Fordi det er en ting å utnytte den antagelse, og dermed
løse et problem med en Algoritmen mer effektivt.
Men vi egentlig aldri spurte i uke null, vel,
hvor mye kostet det Verizon eller noen andre
å få den telefonboken i sortert rekkefølge?
>> Høyre?
Det spiller ingen rolle om se opp Mike Smith
er super rask, hvis det tar deg en år for å sortere sidene i utgangspunktet.
Høyre?
Du kan like godt bare sile gjennom en randomisert telefonboken,
om det kommer til å bli super dyrt å sortere det.
Så hvis vi kan ha en annen frivillig.
La oss ta en titt opp her på hvordan vi might-- kommer på opp-- hvordan
vi kan gå om sortering disse.
>> Og hvis Jordan kunne faktisk bli med oss ​​her oppe på scenen.
Kom opp for bare et øyeblikk.
Hva er navnet ditt?
CAROLINE: Caroline.
DAVID J. MALAN: Caroline, kom opp.
Og du vil være sammen av meg og Jordan her.
Caroline, takk.
Greit.
Så det vi har her for Caroline er 26 blå bøker
at FAS bruker til å administrere visse avsluttende eksamener.
Disse blir vanskelig å finne, men hva vi har gjort på forhånd
er at vi har satt noen navn på forsiden av hver av disse,
men vi har holdt det enkelt ved å deretter sette ut fullt navn.
Så vi ville sette den personen med navnet L, D, J, B, hele veien fra A til Z,
men de er i tilfeldig rekkefølge.
Og så hvis du ville, snakker ditt vei gjennom problemet som deg
gjør det, kan du gå videre og sortere disse for oss, fra A til Z.
>> PUBLIKUM: OK, så L er, i midten.
C begynner.
B. J før L. B, Q.
>> DAVID J. MALAN: Hold denne trodde for ett sekund.
Fordi ellers er dette bare interessant for deg, meg, og Jordan.
Det vi går.
PUBLIKUM: [uhørlig].
R.
DAVID J. MALAN: OK.
Hva driver du med?
>> CAROLINE: M kommer etter O.
>> DAVID J. MALAN: OK.
>> CAROLINE: O.
DAVID J. MALAN: O, Good.
>> CAROLINE: E.
>> DAVID J. MALAN: E, F. Yeah.
>> CAROLINE: T, U, V.
>> DAVID J. MALAN: V, T, U, V. Så det ser ut som du er making-- holde det gående.
Det ser ut som du gjør en stor haug over her,
og slag av en stor haug der borte.
Så første halvdel av alfabetet, andre halvdel av alfabetet.
OK.
Good.
Kind of splitte problem i to.
M, N, X. Yeah.
CAROLINE: K.
DAVID J. MALAN: OK.
K. Så du slags valg dem en etter en,
sette den enten venstre eller høyre, eller Z er det som skjer på gulvet.
OK.
>> CAROLINE: Z kommer på gulvet.
>> DAVID J. MALAN: OK.
Y som skjer på gulvet.
Nå kan vi sette X.
>> CAROLINE: G.
DAVID J. MALAN: G kommer igjen.
S går rett.
Greit, er A går hele veien igjen.
>> CAROLINE: A, B, C, D.
>> DAVID J. MALAN: Nå bra.
Vi har A, B, C, W er det som skjer der nede.
Greit, T.
>> CAROLINE: H, I, J.
DAVID J. MALAN: H, I, J. Good.
CAROLINE: I sentrum, jeg gonna--
DAVID J. MALAN: OK.
Så nå skal vi til slag av flette disse forskjellige hauger.
Så A til C, så ser jeg D, og E og F og G, og H, og I. Nice.
J, K. Og så, er dette haug opp ned, men det er OK.
Sure.
Vi kan kutte noen hjørner.
OK.
Og da trenger vi W, X, Y, Z.
>> CAROLINE: Yeah.
>> DAVID J. MALAN: Excellent.
Så en stor takk til Caroline for sortering disse.
>> [Jublende]
>> Takk.
Tusen takk.
Så nå la oss vurdere et øyeblikk hvordan Caroline gikk om du gjør det,
og hva vi var i stand to-- hvordan vi
var i stand til å løse det problem da vi var bare
gitt en hel haug av tilfeldige innganger.
>> Vel, det ser ut som om det var litt av et system der?
Høyre.
Så de tidligere brevene i alfabetet, hun
var å sette til venstre, og senere bokstaver i alfabetet,
hun var å sette inn riktig.
Og så snart hun funnet noen proksimale bokstaver, ones
som går rett ved siden av hverandre, hun ville sette dem i rekkefølge.
Og så vi slags hadde disse små hauger av sorterte innganger oppstår.
>> Og så det er helt som det de fleste av oss mennesker ville gjøre.
Vi ville liksom sile gjennom det, og vi ville slags har en mekanisme.
Men det kan være vanskelig å skrive det ned i en formel per se.
Det føltes litt mer organisk enn det.
Så la oss se om vi kan nå innbundet problemet med færre innganger.
>> I stedet for 26, la oss gjøre noe langt færre
med bare si, sju, bak disse dørene, så å si.
Er det bare syv tall?
Og hvis målet nå på hånd er å finne en verdi,
la oss se hvor effektivt vi kan gå om du gjør dette.
Og la oss se om vi kan nå begynner å bruke noen tall,
eller noen formler som brukes til å beskrive effektiviteten i vår telefonboken
algoritme, vår eksamen bok algoritme, og mer generelt, å finne informasjon.
>> Så for dette, la meg gå videre, og på berøringsskjermen over her,
sette opp en nettleser som har akkurat disse sju dører.
Og hvis vi kunne få en annen frivillig til å komme på over her,
Jeg har satt de samme dørene over her.
Hurtig frivillig.
>> Denne one-- demoer kommer til en raskere og raskere nå.
Kom ned.
Hva er navnet ditt?
TREVOR: Trevor.
>> DAVID J. MALAN: Trevor?
Greit, Trevor, kom ned.
Så Trevor har meldt seg frivillig her for å gjøre en lignende problem, men en som er
smalere i omfang, og det kommer å tillate oss å prøve å formalisere nå
fremgangsmåten for å sortere disse tallene.
>> Så Trevor, hyggelig å møte deg.
Så her er en matrise, så å snakke, en liste over syv dører.
Gå videre og finne oss nummer 50.
Og så i ettertid, Fortell oss hvordan du fant det.
Skulle be-- all right.
Ja, dette er en her?
UH oh.
OK.
Du klikket den.
Good.
>> Og god.
Nå du klikket den.
Og la meg gi deg mikrofonen, slik at du har det i løpet av et øyeblikk.
Gå videre og klikk på naboen som du har tenkt.
Ja bra.
TREVOR: Kan jeg unclick en dør?
DAVID J. MALAN: Nei, du kan ikke unclick.
TREVOR: OK.
Denne her.
DAVID J. MALAN: Hvor vil du reise?
Hvilken?
>> TREVOR: At man.
>> DAVID J. MALAN: No.
>> TREVOR: OK.
Denne her.
>> DAVID J. MALAN: Ja.
Det var bra.
Greit.
Så hva var din algoritme eller Fremgangsmåten for å gjøre dette, Trevor?
>> TREVOR: Jeg bare gikk gjennom dører før jeg fant en 50.
DAVID J. MALAN: OK.
Utmerket algoritme.
Så det er fint.
Fordi faktisk, hvis jeg avsløre hva som er bak disse to andre dører, hva
vi finner her er at vi har bare tilfeldig innspill.
Så det var faktisk så god som du kan få.
Og faktisk, du fikk bedre enn uttømmende søker hele array,
fordi det ville ha vært veldig uheldig hvis du hadde truffet antall
50 på den aller siste døren.
Men hva om vi i stedet ga deg en forutsetning.
Anta at jeg liksom alle disse dørene rundt,
slik at du har tallene sortert denne gangen,
men denne gangen er det faktisk en different-- denne gangen,
det er faktisk sortert for deg.
Og nå målet på hånden er å treffe nummer 50.
>> TREVOR: OK.
>> DAVID J. MALAN: Hva er algoritmen din kommer til å være?
>> TREVOR: Vel, hvis det er sortert, er det enten kommer
å be-- hvis største til største, synkende, vil det være den første,
eller om det er motsatt, det vil være den siste.
Så jeg vil bare peke på denne døren, og så bare trykk på siste dør.
DAVID J. MALAN: Excellent.
Greit.
Så vi fant nummer 50.
Så så snart du visste de ble sortert, vi
var i stand til å utnytte denne antakelsen.
Så de er for mye som telefonboken eksempel.
Så snart du har, selv med et lite problem som dette,
innganger pre-sortert, kan vi faktisk finne verdien uten tvil
mer effektivt.
>> Og jeg gjorde ikke fortelle deg om det var sortert små til store eller store til små,
og så det var veldig rimelig å starte i den ene ende eller den annen
å faktisk finne at målet verdi.
Så takk til Trevor også.
Og jeg skal propose-- pent gjort.
Vi har et lite klipp, faktisk, at er blant våre favoritt øyeblikk i CS50,
der noen ganger disse demoene ikke helt etter planen.
Og faktisk akkurat nå, jeg trakk opp feil grensesnitt
som å bruke berøringsskjermen.
Så det var min feil der.
>> Så dette vil gjøre for neste års klipp som
hvorfor jeg ble klikke på min egen skjerm.
Men la oss ta en rask titt på hva som skjedde i fjor
med Jay, som kom opp, mye som Trevor her, frivillig,
og i denne korte klipp, vil du se hvordan dette samme demoen ikke helt
avsløre de samme erfaringene.
[VIDEO PLAYBACK]
-Alle Jeg vil du skal gjøre nå er å finne for meg, og for oss,
virkelig, nummer 50 ett skritt av gangen.
>> -Den Nummer 50?
>> -Den Nummer 50.
Og du kan avsløre hva som er bak hver av disse dørene
ganske enkelt ved å berøre den med en finger.
Pokker.
>> [Ler]
>> [END PLAYBACK]
DAVID J. MALAN: Så det gikk veldig bra.
Det var de usorterte dører.
Og Jay, selvfølgelig, fant det alt for fort.
Trevor gjorde en mye bedre jobb i form av en lærevillig øyeblikk,
så å si, i år i tar lengre tid å finne den.
Selvfølgelig, så vi ga Jay en ny sjanse,
hvor vi sortert dørene, akkurat som vi gjorde for Trevor,
og Trevor gjorde super bra denne gangen.
Men Jay gjorde det halvparten så raskt.
[VIDEO PLAYBACK]
-Målet Nå er å også finne oss nummer 50,
men gjør det algoritmisk, og Fortell oss hvordan du går om det.
>> -OK.
>> -Og Hvis du finner den, holde deg filmen.
Hvis du ikke finner det, du gir den tilbake.
>> -Man.
>> -Å!
>> - [Uhørbart] OK.
Så jeg kommer til å sjekke endene først for å finne ut om there's-- Oh.
>> [APPLAUSE]
>> [END PLAYBACK]
DAVID J. MALAN: OK.
Så sortering dører klart fører til større effektivitet.
Og så, dobbelt så raskt er det jeg mente det.
Og så Jay hadde flaks begge ganger.
Og han også hadde flaks i det siste år, jeg bestilte noen Blu-ray-plater
å faktisk gi ut.
Jeg beklager dette året, vi hadde ikke den samme, Trevor.
Men enda bedre var for noen år tilbake.
Og noen av dere kanskje vet dette stipendiat, Sean, som da han var i CS50,
ble utfordret med den nøyaktige samme problem, riktignok i SD,
så vil du snart se, tilbake i dag.
Og du vil finne at ikke bare gjorde han ta litt lenger tid enn Jay,
litt lengre enn Trevor, det var faktisk denne fantastiske muligheten
til å engasjere seg nesten alle i Publikum a la Price is Right, oppmuntre
ham til å finne nummeret vi er ute etter.
La oss. ta en rask titt.
>> [VIDEO PLAYBACK]
>> -OK.
Så din oppgave her, Sean, er følgende.
Jeg har skjult bak disse dører tallet syv.
Men gjemt bort i noen av disse dørene i tillegg er andre negative tall.
Og målet ditt er å tenke av denne øverste raden av tall
som bare en matrise, eller bare Sekvensen av papirbiter
med tall bak dem.
Og målet ditt er, bare ved hjelp av topp utvalg her, finne meg tallet syv.
Og vi så kommer til kritikk hvordan du går om å gjøre det.
-Greit.
-Finn Oss tallet syv, takk.
Nei.
Fem, 19, 13.
>> [Ler]
>> Det er ikke et lurespørsmål.
En.
>> [Ler]
På dette punktet, er poengsummen din ikke veldig bra, så du kan like godt holde det gående.
Tre.
>> [Ler]
>> Fortsett.
Ærlig talt, jeg kan ikke hjelpe, men lurer hva du selv tenker, so--
>> [Ler]
Bare den øverste raden, så du har tre igjen.
Så finn meg syv.
>> [Ler]
17.
Sju.
>> [APPLAUSE]
>> Greit.
>> [END PLAYBACK]
>> DAVID J. MALAN: Så vi kunne se disse hele dagen lang.
Og selvfølgelig, noen av årets demoer kanskje
vil nå ende opp i neste Årets video i tillegg.
Så nå kan vi faktisk fokusere på algoritmer
her, og se om vi ikke kan nå begynne å formal
hvordan vi kan gå om å få våre data inn i denne tilstanden at det er sortert,
slik at til slutt, kan vi faktisk søke det mer effektivt.
Og selv om vi kommer å bruke relativt små datasettene,
som åtte tallene vi har her på bordet,
til slutt de samme ideene kan gjelde 1000 innganger, en million innganger,
4 milliarder innganger, fordi algoritmer kommer til å være fundamentalt det samme.
>> Og så dette er vår siste mulighet for frivillige i dag,
men kanskje den mest involvert en, som trenger vi åtte frivillige
å komme opp og gå oss gjennom Prosessen med å sortere hva som vil snart
være på disse musikk står her.
La meg starte tilbake hit.
>> Så en i turquoise-- grønt er det?
Begår du?
Two.
Kom ned.
OK.
Tre.
Fire.
La me-- OK, fem.
Du blir nominert av din venn.
Seks, sju, og åtte.
Kom opp.
Greit.
Tusen takk.
Kom opp.
>> Greit.
Så det vi har her-- og dette er blant de mer pinlige seg,
siden dette vil kreve at du humor meg for bare en liten bit av gangen.
Du skal være nummer én.
Hva er navnet ditt?
>> ANNAN: Annan.
>> DAVID J. MALAN: Annan.
David.
Hva er navnet ditt?
>> JOSEPH: Joseph.
>> DAVID J. MALAN: Joseph, du er nummer to.
>> SERENA: Serena, nummer tre.
Stefan, nummer fire.
CYNTHIA: Cynthia.
DAVID J. MALAN: Cynthia, nummer fem.
[Uhørbart]
DAVID J. MALAN: [uhørbart].
David, nummer seks.
MATT: Matt.
DAVID J. MALAN: Matt nummer sju.
Og?
>> WAVERLY: Waverly.
>> DAVID J. MALAN: Waverly, nummer åtte.
Greit.
Hvis du could-- whoops.
Hvis dere alle, som din første utfordringen, det
er åtte musikk stands her vendt mot publikum.
Hvis du kunne sette tall på musikk disse står på en slik måte
at de stiller seg opp med samme tallene på tavlen.
Så gjør dere ser sånn etter sette dine tall på disse musikk
står her.
Utmerket så langt.
>> Utmerket.
OK.
Så nå skal vi spørre Spørsmålet i et par forskjellige måter.
Hvordan kan vi gå om sortering disse folkene her oppe?
Fordi vi hadde noen tilnærminger tidligere, der vi var
slags lage to forskjellige skuffer.
Og da vi var generelt piecing ting sammen.
Så snart vi så to tall som hørte sammen,
vi setter dem sammen.
To bokstaver som hører sammen.
>> Men la oss se om vi kan ikke formalisere dette,
slik at vi til slutt har noen pseudo-koden du vil,
som du kan løse disse problemene.
Så nå, jeg ser ut på disse tallene her.
Og jeg ser en hel haug med feil.
Til syvende og sist, jeg vil ha en på venstre og åtte på høyre side.
>> Og så jeg ser på disse to, fire og to.
Og hva er problemet, selvsagt?
Yeah.
So.
To kommer åpenbart før fire, så vet du hva?
La meg først ta en grådig tilnærming, om du vil, mye som problem
satt one-- hvis du husker fra Standard Edition av Problem Set One,
hvor jeg bare lokalt løse problemet det er rett her foran meg
og se hvor det fører meg.
>> OK.
Så to og fire, la meg gå fremover og bare bytte dere to.
Hvis du fysisk kan flytte dere og papir,
Jeg synes å ha fått liste i en bedre tilstand.
>> Nå er de gode.
Jeg kommer til å gå videre, fire og seks, ser bra ut.
Ikke et problem.
Seks og åtte, OK.
Åtte og en, et annet problem.
Fordi det er sant om åtte og en?
En kommer før åtte, og så hva skal vi gjøre?
La oss bytte disse to.
Ett og åtte.
Og nå, jeg kommer til å holde det gående.
Jeg kommer til å holde utkikk fremover.
Og la oss se hva som skjer.
Åtte og tre, av Selvfølgelig, i rekkefølge.
La oss swap.
Åtte og sju, selvfølgelig.
I ustand.
La oss swap.
Åtte og fem, selvfølgelig, la oss swap.
Greit.
Listen er sortert.
ja?
>> OK, selvsagt ikke.
Men det er litt bedre, ikke sant?
Fordi varsel hva som skjedde.
Hver gang vi utført en swap, en mindre antall slags perkoleres på den måten,
og et større antall perkolert denne måten, eller vi vil
begynne å si boblet til venstre eller boblet til høyre.
>> Nå er det ikke nok, fordi i beste fall en rekke makt
har flyttet ett sted fremover, eller i verste fall,
et tall kan ha flyttet ett sted lenger.
Så vet du hva, denne typen av virket ganske bra så langt.
La meg bare prøve det igjen.
To og fire, de er OK.
Fire og seks, de er OK.
Seks og en, ute av drift.
Så la oss bytte dere to.
Og nå, merke problemets begynner å bli litt bedre igjen.
Seks og tre, ute av drift.
La oss bytte dere to.
Seks og sju, du er god.
Syv og fem, selvfølgelig, ute av drift.
Sju og åtte, i rekkefølge.
Og nå, kanskje jeg må gjøre dette noen flere ganger.
Og faktisk, jeg tror for dere selv kanskje hvor mange ganger maksimalt
kanskje jeg må gå frem og tilbake?
>> Vi vil komme tilbake til det.
Så to og fire er fortsatt OK.
Fire og en, nope.
Så, la oss swap.
Og igjen, merke visuelt en er slags boblende
til venstre, der det skal være.
Fire og tre swap.
Fire og seks.
Seks og fem swap.
Seks og syv.
Sju og åtte er gode.
>> Good.
Vi får enda bedre.
Så la oss se.
Nå har vi to og en.
Selvfølgelig bytte.
To og tre, tre og fire, fire og fem, seks og sju, sju og åtte.
Good.
Og vet du hva?
Fordi jeg har gjort én endring der, la meg gjøre én tilregnelighet sjekk.
La meg gå hele veien tilbake til begynnelsen.
OK.
One, two-- yup, se?
Noe var galt.
Tre, fire, fem, seks, sju, åtte.
Og i denne siste pass, er du komfortabel med min nå
hevder det er sortert?
OK.
Visuelt er det helt sant.
Men funksjonelt, hva fikk også bare skje
i det siste innlegget, som lar deg å bekrefte at denne listen er faktisk
sortert?
>> Hva var det jeg gjør eller ikke gjør dette siste innlegget?
PUBLIKUM: Det var ingen endringer.
DAVID J. MALAN: Sorry?
PUBLIKUM: Ingen endringer.
DAVID J. MALAN: Det var ingen endringer.
Så det ville være dumt av meg å gjøre det samme algoritme igjen
hvis jeg ikke gjorde noen forandrer den første gangen.
Og staten har ikke forandret seg.
Sikkert, jeg kommer ikke til å gjøre Eventuelle endringer andre gang.
Og så, er det trygt nå å si, er listen sortert.
>> Og ja, dette er nå noe som vi vil vanligvis
samtale boble sortere, der parvise, du rette feilene igjen,
og igjen, og igjen, og du holde det gående frem og tilbake,
og frem og tilbake, helt til du gjør ingen slike bytteavtaler, noe som medførte at
du kan være trygg på, ja, jeg ferdig med å fikse alle feilene.
La oss arte og prøve en annen tilnærming.
Hvis dere kunne gå tilbake i rekkefølgen du var for et øyeblikk siden,
som så ut som dette.
Nå, la oss ta en tilnærming en Litt mer som eksamen bok,
hvor vi var hele tiden velge bokstav i alfabetet
at vi på en måte ønsket å forholde seg til neste.
Kanskje det var en høy brev, som A, eller en lav bokstaven Z.
>> Slik at alle er tilbake i denne rekkefølgen.
Og nå la meg gjøre dette.
La oss se Jeg vet jeg har åtte tall her.
Jeg kommer til å gå videre og bare bevisst velger
de minste elementene.
Høyre?
Dette virker intuitivt også.
Hvorfor finner jeg ikke den minste element, sette det der det hører hjemme,
deretter få den nest minste element, sette det der det hører hjemme, og bare gjenta.
>> Fordi intuitivt, som skal fungere også.
Så fire, det er en ganske lite antall.
Jeg kommer til å huske hvor dette er.
Vent et minutt.
To er mindre.
La meg nå husker hvor to- er, og glemme fire.
Vi skal ta det senere.
Seks, jeg er ikke interessert.
Åtte, er jeg ikke interessert i.
Det ene er min nye lite antall.
Så jeg kommer til å huske hvor man er.
Tre, ikke interessert.
Seven, ikke interessert.
Five, ikke interessert.
>> Så uten å falle av scenen i år,
Jeg kommer til å ta tak i nummeret one-- og hva var navnet ditt igjen?
>> ANNAN: Annan.
>> DAVID J. MALAN: Annan.
Og om du kunne bli med meg på begynnelsen av listen
la oss sette deg der du hører hjemme.
Unfortunately-- hva heter du?
>> STEFAN: Stefan.
>> DAVID J. MALAN: Stefan er i veien.
Så før Stefan løser dette problem, hva skal vi gjøre?
Hva gjør vi med Stefan?
>> PUBLIKUM: [uhørlig].
DAVID J. MALAN: OK.
Så vi kunne gjøre det.
Vi kunne liksom ta Stefan og hans fire, og bare sette den i en variabel
og holde på den for litt tid,
dermed gjøre plass til nummer én.
Og det er ikke dårlig.
Jeg kunne foreslå, hvorfor gjør ikke vi bare sette Stefan her?
Hvorfor kan dette bryter en av ideene vi startet
snakker om forrige gang, i forrige uke?
Yeah?
>> PUBLIKUM: [uhørlig].
>> DAVID J. MALAN: Det finnes ingen indeks for det.
Hvis du tenker på dette, ja, som en array, er dette som negativt,
så det er ingen hukommelse faktisk her hvis dette er faktisk en matrise,
som vi erklærte i forrige uke i forelesningen.
Så vi bør ikke gjøre dette.
Vi kan lagre den i en variabel.
>> Eller vet du hva?
Jeg hørte noen andre foreslå det.
Hva annet kan vi gjøre med Stefan?
Hvorfor kan ikke vi bare kaste ut ham og sette ham over hvor nummer en var.
Så hvis du ønsker å gå dit.
Og ja, dette er en ganske god løsning.
Nå på den ene siden, har jeg kind av gjort problemet verre.
Fire er nå lenger unna fra der den skal være.
Det bør være mot denne omgangen.
>> Men vet du hva?
Det kunne ha vært uflaks.
Kanskje nummer åtte var her.
Og så, kanskje vi ville har fått heldige,
og presset åtte nærmere slutten.
Så i slutten av dagen, Den slags alle gjennomsnitt ut.
Vi trenger ikke å bry seg om fire.
Alt jeg bryr meg om akkurat nå er velge det minste elementet.
>> Og nå, hva jeg kommer til å gjøre er å glemme nummer én
permanent, fordi jeg vet det liste bak meg er nå sortert.
Så min liste var tidligere størrelse åtte.
Nå er det på størrelse syv.
Så mitt problem er å få mindre enn lineært.
Så nå kommer jeg til å velge nåværende minste element, to.
Seks, åtte, fire, tre, syv, fem.
Det var det minste elementet.
Så hva skal jeg gjøre with-- Hva var navnet ditt igjen?
>> JOSEPH: Joseph.
>> DAVID J. MALAN: Joseph?
Vi kommer til å forlate Joseph på plass.
Nå kommer jeg til å late at disse gutta are-- godt,
Jeg vet at disse to er allerede sortert.
La oss nå fokusere på Resten av listen.
Seks er gjeldende minste.
Åtte er større.
Fire er nå gjeldende minste.
Tre er nå gjeldende minste.
Og så nå, jeg kommer til å velge tre, som er-- hva heter du igjen?
SERENA: Serena.
DAVID J. MALAN: Serena, hvis du kunne grip nummer og swap with--
Kalsang: Kalsang.
DAVID J. MALAN: Kalsang.
Kom tilbake, og vi er kommer til å bytte de to.
Og nå, la oss sette dette på autopilot.
Jeg kommer til å gå, og la den til dere å velge de neste minste elementene.
Dun, dun, dun, dun.
Nummer fire, hva skal du gjøre?
Utmerket.
Nå kommer jeg til å gjøre et annet pass.
Dun, dun, dun, dun.
Jeg ser fem er den nest minste.
Nå skal jeg ta en annen pass.
Dun, dun, dun, dun.
Seks er den minste.
Good.
Seven er den minste.
Ingen endring.
Åtte er den minste.
Ferdig.
>> Så det vi nettopp har gjort ved iterativt valg av ett element etter hverandre
er implementere noe som vi er kommer til å formalisere som utvalget slag.
Og det er kanskje enda enklere å forklare,
i det bokstavelig talt alt du ønsker å gjøre er å bare holde
går frem og tilbake gjennom listen velge, den nest minste element,
til du er ferdig.
>> Så det er enda enklere, kanskje intuitivt, enn sist.
La oss prøve en siste.
Hvis dere kunne tilbakestille dere selv inn i følgende stillinger
en siste gang, la oss se om vi ikke kan nå formalisere en annen tilnærming.
Faktisk, ville noen der ute liker å foreslå
hvordan annet vi kan gå om du gjør dette?
Uten å kaste ut buzzwords eller sort av svarene som allerede er kjent,
bare intuitivt, hva kan vi gjøre?
>> PUBLIKUM: [uhørlig].
DAVID J. MALAN: Yeah.
Så det er noen stor intuisjon der.
Gode ​​ting ser ut til å skje så langt i informatikk når vi deler
og erobre problem med å dele den i to og halvt om halvt.
Og så ja, vi kunne begynne å gjøre det.
Og faktisk, som kommer til å være, vi vil se, en av våre beste løsninger ennå.
Men la oss komme tilbake til det før lenge.
Faktisk skal vi gjøre det litt senere denne uken.
Hva annet kan vi gjøre for å løse dette?
Så alle her er i tilsynelatende tilfeldig rekkefølge.
Vet du hva?
Snarere enn å gå frem og tilbake, frem og tilbake, frem og tilbake
hver gang, føles dette som Jeg gjør mye gåing.
Hvorfor kan jeg ikke bare starte på begynnelsen av listen
og bare sette fire der det hører hjemme?
Så la meg anta for øyeblikket at min liste er bare denne første elementet.
Er fire sortert i dette øyeblikk i tid, hvis alt jeg bryr meg om er alt her?
Dette er liksom trivielt sant, ikke sant?
Som en liste som inneholder en rekke, og som nummer fire er åpenbart sortert.
>> Så la meg bare fastsette at denne listen er sortert.
Men nå har jeg resten av denne listen.
Så nå, jeg møter to.
Hvor gjør to åpenbart hører med hensyn til fire?
Før fire.
Så hva kan jeg gjøre her?
Hva heter du igjen?
>> JOSEPH: Joseph.
>> DAVID J. MALAN: Joseph, Hvis du kunne gå tilbake
for bare et øyeblikk med nummeret ditt.
Og nå hva skal Stefan gjøre her?
La oss skifte Stefan over her.
Og nå, la Joseph komme inn her.
Og nå, la meg hevder at alt her er sortert.
Så, tilsvarende resultat, men fundamentalt forskjellig tilnærming.
Jeg har ikke selv sett hva som er der nede.
Jeg bare fortsette å ta de elementene som de er overlevert til meg,
og håndtere dem.
>> Så nå ser jeg nummer seks.
Hvor kommer nummer seks tilhører?
Vi har to, fire, seks.
Nøyaktig hvor hun er akkurat nå.
Så la oss forlate det alene, og nå hevder at denne del av listen
er nå sortert.
Og så, føles dette fundamentalt annerledes ved at jeg bare
flytte gjennom listen her lineært, og jeg er aldri dobling tilbake.
Ja.
Greit.
Så åtte, hvor hører du?
Akkurat her.
Perfekt.
Så nå, en.
UH oh.
Dette føles som det er kommer til å bli dyrt.
Nå, i den foregående algoritme, Jeg har nettopp byttet folk.
Så jeg kan sette ham hele veien på begynnelsen, men deretter flyttet Joseph.
Men hvis jeg flytter Joseph, nå hva som kommer til å være galt?
>> Nå, jeg har liksom undone-- jeg har tatt ett skritt frem og deretter
ett skritt tilbake, for nå Joseph ville være ute av drift.
Så la oss gjøre dette.
Hvis du kunne ta nummer én og et skritt tilbake for bare et øyeblikk.
Hvordan kan vi put-- hva var navnet ditt igjen?
>> ANNAN: Annan.
>> DAVID J. MALAN: Annan på plass?
Hva som må skje med respekt til to, fire, seks, og åtte?
De trenger alle å skifte.
Så hvis åtte ønsker å skifte først, deretter seks, deretter fire, deretter to.
Og da Annan, hvis du hadde liker å komme inn her, bra.
Men her, vi har bare slags betalt en pris
på et annet punkt i algoritmen.
Mens siste gang med valget sortere, og selv boble sortere,
Jeg går tilbake og frem, frem og tilbake,
som er sikkert legge opp tidsmessig, og bokstavelig talt trinnvis.
>> Sortering ved innsetting, først øyekast ser ut som det er
super smartere, ved at jeg bare gjør langsom, trinnvis utvikling,
men jeg kommer ikke dette frem og tilbake.
Men hvis noen er faktisk ute av drift, varsel
alt arbeidet jeg bare måtte gjøre.
Jeg måtte flytte halvparten av listen bare for å gjøre plass til nummer én.
Så det er det samme beløpet arbeid så langt det
føles, bare en annen type arbeid.
>> La oss fortsette.
Så nå vet vi at alle mellom ett og åtte, sortert.
Her har jeg nummer tre.
Hvis du liker å plukke opp nummer tre, gå tilbake ett.
Og hva gjør dere trenger å gjøre?
Jepp.
Så det er en annen en, to, tre trinn.
Tre enheter av tid som bare koster meg, slik at tre kan nå passe.
Til slutt, syv.
>> La oss gå videre og ha du tar et skritt tilbake.
Dette er bare kommer til å koste oss en enhet av gangen, men det er OK.
Og nå fem kommer til å være litt dyrere.
Hvis du ønsker å gå tilbake.
Vi trenger å flytte åtte, og syv og seks.
Og så alle er nå sortert.
Så en stor hånd til våre frivillige her.
Tusen takk.
>> [APPLAUSE]
>> Tusen takk alle sammen.
Tusen takk alle sammen.
Så la oss se nå bare hvordan kostbar alt som var.
La oss vurdere kanskje den enkleste av disse, boble slag.
Og jeg sier enkleste, bare fordi du kan løse det begjærlig etter bare
fikse den parvise problem her.
Fikse den parvise problem her, igjen og igjen
og igjen, gjenta så mange ganger som du faktisk trenger det.
>> Så det viser seg at med en boble sortere, vel,
hvor mange skritt må jeg ta på første pass av at algoritmen?
Jeg kan take-- la oss see-- en, to, tre, fire, fem, seks, syv.
Og det er åtte elementer her.
Så det er som n minus 1 trinn til komme fra begynnelsen av listen
til enden av listen.
>> Men med utvalg sort, husker at jeg er velge elementene igjen og igjen
og igjen det er minste, Jeg setter det på plass,
men da er jeg ikke ser bak meg igjen.
Så jeg tror det er litt mer klar så det første gang, kanskje jeg
må ta alle n minus 1 trinn for å finne den minste element.
Så jeg satte dem på plass, og jeg kaste ut den som var her tidligere.
>> Men da jeg ikke trenger å holde utkikk på dette elementet,
fordi jeg vet at det er allerede den minste.
Så nå kan jeg se på bare sju elementer, deretter seks elementer,
deretter fem elementer, deretter fire elementer.
Og så matematisk, hvis n er antallet av elementer eller tall
at vi startet med, kan du forestille deg at dette er det samme som N minus 1,
pluss n minus 2 trinn, pluss n minus 3 trinn,
pluss n minus 4 trinn, hele helt ned til bare ett trinn.
Og jeg er på mitt siste person.
>> Og hvis du husker at mye av statistikk bøker eller mattebøker
har disse formler på innbundet rygg eller foran dem,
Det viser seg at denne serien kan uttrykkes enklere
som n ganger n minus 1 over 2.
Og det er fint hvis det er ikke i forkant av tankene dine.
Men dette er faktisk sant.
Det er bare en enklere måte å skrive det.
Og så hvis du tror tilbake til grunnskolen,
når du bare begynne å multiplisere ting ut, dette selvfølgelig,
er bare n squared minus n delt på to.
Alt jeg har gjort er å utvide uttrykkene der.
Og så la oss omskrive dette litt annerledes.
Det er n squared delt på to minus n / 2.
>> Så igjen, jeg bare slags søknad noen regneregler der.
Men merker nå at den største sikt i dette uttrykket, så å si,
er at n squared.
Så ja, det er n squared delt på to, minus n / 2.
>> Men generelt, hvis n er kommer til å være en stor verdi,
Jeg kommer til å hevde at n squared kommer til å være den dominerende faktoren.
Det er bare kommer til å være en større bidragsyter
til antall trinn enn n / 2.
Så hva mener jeg med dette?
La oss prøve et enkelt eksempel, selv men regnestykket blir litt stort.
>> Så antar vi hadde 1 million mennesker på scenen, eller 1 million ting
at vi ønsker å sortere.
La oss plugge en million inn nøyaktig den formelen
for å se hvor mange skritt det tar totalt å sortere en million elementer ved hjelp av si,
utvalg sort.
>> Så vi ville ha den samme formelen som før.
Jeg vil koble en million, slik at jeg får en million kvadrat delt på 2,
minus en million dividert med to.
Hvis jeg gjør det matte på forhånd her har vi 500 milliarder
minus 500.000, noe som gir oss 499999500000,
noe som er ganske utrolig stort.
>> Faktisk, hvis du sammenligner nå 499 000 000 000, 999 millioner kroner,
500.000 mot vår opprinnelige verdien, 500 milliarder, det er så jævla nær.
Høyre? n squared delt på to gir us-- eller rettere sagt, n kvadrert dividert med 2
ga oss 500 milliarder.
Det er ganske utrolig nært til 499 999 500 000,
det vil si å trekke ut 500000, eller mer generelt, å subtrahere off
n squared, egentlig ikke en stor avtale.
N squared gjør disse tallene vokser veldig fort.
>> Nå, dette er viktig bare i den utstrekning som vi, som dataforskere,
er generelt ikke til å bry seg så mye om nyansene i disse formlene
og akkurat hva presise svar er.
Vi bryr oss bare det, vet du hva?
På slutten av dagen, denne formelen er av størrelsesorden av n kvadrat.
>> Ja, vi dividere med to der inne.
Ja, vi trekke ut n minus to.
Men ved slutten av dagen, skal uttrykket som virkelig gjør vondt oss og koster oss
mange av trinnene er at torget sikt.
Og så hva en datamaskin vitenskaps skal generelt gjøre
er ignorere alle de mindre ordens ledd,
og bare se på den som bidrar mest til kostnaden.
>> Og dette er hyggelig, fordi vi kan nå snakke i mye større generalitet
om algoritmer, og kan sammenligne dem.
Og det faktum at jeg er ved hjelp av denne O er bevisst.
Når jeg sier på rekkefølgen av, jeg er spesielt
henvise til noe kalt big O. Og stor O
er en notasjon som en datamaskin forskeren bruker for å beskrive
en øvre grense på noe.
>> Så hvis du sier at en algoritme er i stor O n squared,
som jeg foreslo bare en øyeblikk siden, det betyr
som i form av sin løpe tid eller dens effektivitet,
det tar på ordren n squared trinn.
Kanskje mer, kanskje mindre.
Men det er i størrelsesorden n squared.
Og det er den øvre grensen.
Det kommer ikke til å være mer smertefullt enn det.
Det kommer ikke til å være n cubed, eller to til n, eller noe mye større.
Dette er en øvre grense på hva det koster.
Så gitt at, la oss vurdere bare noen få eksempler.
Og dette er bare en endelig liste av svært vanlige kjører ganger
for algoritmer som er ment å være illustrerende for noen ting vi har
sett allerede.
>> Så for eksempel, i tilfellet utvalg liksom, hva jeg hevder her
er at utvalget slags s løping Klokken er i størrelsesorden n squared.
I verste fall kommer jeg til å ha en hel haug av tilfeldige tall her.
Og som vi så matematisk, hvis jeg fortsette å gå
gjennom listen, via liste, velge den nest minste
element igjen og igjen, hvis jeg faktisk skrive ned alle trinnene
Jeg tar som jeg foreslo formulaically før, er det i størrelsesorden n squared
trinn som jeg tar.
>> Og det viser seg at boblen sortere og innsetting sort
er like treg i verste fall.
Tenk deg for eksempel innsetting sortere, den aller siste algoritmen vi jobbet med,
som hadde oss se på elementet og deretter sette den der den hører hjemme.
Og da vi så på neste element, og satt det der det hører hjemme.
>> Så vurdere best mulig scenario.
Anta at jeg hadde mine frivillige stille opp bokstavelig som dette, en gjennom åtte,
allerede sortert.
Hvor mange skritt er innsetting sort kommer til å ta for å sortere åtte personer,
hvis de kommer på scenen ser ut som dette?
>> Åtte mennesker allerede sortert.
Og jeg innsetting sort.
Det siste av de algoritmer.
Vel, la oss reenact virkelig fort.
Så hvis jeg begynner her, ser jeg en.
Hvor hører en?
Det hører her.
Jeg ser to.
Hvor kommer to hører?
Akkurat her.
Jeg ser tre.
Hvor kommer tre tilhører?
Akkurat her.
>> Jeg ser fire.
Akkurat her.
Fem, seks, sju, åtte.
Det er ingen grunn til å gjenta meg selv.
Og i så fall hvor mange skritt er at når det gjelder n?
Det er i størrelsesorden n trinn, ikke sant? n minus en.
Men jeg tok en lineær rekke trinn, og nå er jeg ferdig.
Så det er den beste saken, skjønt.
Hva om det verste tilfellet?
Hva åtte var der borte, og sju var der nede,
og en og to var over her, så at listen ble virkelig snudd?
>> Vel, hva skjer faktisk hvis dette er nummer?
Og vi vil gjøre bare et par eksempler.
Hva om, ja, nummer åtte er her, og de number-- whoops.
Så hva om faktisk antall åtte er helt over her,
og jeg bruker innsetting slag?
>> OK.
Jeg hevder i øyeblikket det er på plass.
Men nå, seven-- hvor kommer sju gå?
Selvfølgelig går det over her.
Så jeg må flytte åtte over ett sted.
Nå seks, hvor går den?
Vel, greit.
Nå, jeg må flytte åtte løpet et sted, og syv over et sted,
og da jeg plop ned seks.
>> Så den første gang, det koster meg ett skritt å fikse ting,
så det kostet meg to skritt for å fikse ting.
Hvor mange skritt er det kommer til å ta å fikse
ting å sette fem-på rett sted?
Tre.
Fordi nå må jeg flytte en, to, tre.
Hvor mange skritt går det å ta å sette fire i riktig sted?
4 pluss fem pluss seks, pluss 7.
>> Og så det er matematisk identisk hva vi beskrev for valg liksom.
Vi har denne serien det er bare økende.
1 pluss to pluss tre pluss 4, eller omvendt, 7 pluss seks
pluss fem pluss 4 legger opp til dagens formål til i størrelsesorden n squared.
>> Så la meg fastsette for at boble typen er også i n squared.
Fordi med boble sortere, hver gang jeg går gjennom listen,
Jeg tar omtrent hvor mange skritt?
Hver gang jeg bokstavelig talt gå derfra til det?
Omtrent n trinn.
Men hvor mange ganger jeg kan trenger å gå gjennom listen?
>> Vel, omtrent n gang.
Kanskje n minus 1, men omtrent n ganger.
Vel, hvorfor er det?
Vel, med boble sortere, hvis vi starter med boble sortere,
med listen i den verst tenkelige situasjon, som igjen er helt
bakover, hva kommer til å skje?
Jeg går gjennom listen, og antall man tilhører hele veien der borte.
>> Men med boble sortere, gjør hvor langt man flytte på min første pasning gjennom listen?
Hvor mange flekker får han nærmere riktig sted?
Bare én.
Så hvis du slags grunn gjennom dette, hver gang gjennom denne algoritmen,
Davids tar omtrent n trinn.
Men hvor mange passeringer gjennom listen er det
kommer til å ta for en å boble til venstre der det hører hjemme?
>> Han må flytte ut, n mellomrom på denne måten.
Så bare for å gjøre sorteringen av listen, Jeg må gå frem og tilbake n ganger.
Og hver gang jeg er ser på n elementer.
Så gjør n ting n ganger på rekkefølgen av n kvadrat.
>> Nå vil vi se på noen av shorts som
er innebygd i CS50 neste problem satt, en annen tilnærming til disse,
men for nå, la oss bare vurdere noen andre som kjører ganger,
spesielt hvis sorterings de ta litt tid til å synke inn.
Hva er en algoritme vi har sett allerede som tar på rekkefølgen av n trinn?
>> Hva bør ta en lineær rekke trinn som vi har sett så langt?
Hva er det?
Telefonkatalogen søk.
Den første algoritme.
Høyre?
Hvor vi er lineært søker etter Mike Smith?
Faktisk.
Fra uke null, da jeg begynte snu en side av gangen,
og jeg sa selv at det var slags av en lineær følelse algoritme,
og vi hadde det bildet på brettet med den rette røde linjen
og den rette gule linje, de var faktisk
algoritmer som er i stor O av n.
>> Fordi å finne Mike Smith i en telefon bok med n sider, i verste fall,
kan ta meg n trinn.
Hva med å ta oppmøte?
En to tre fire fem seks.
Hva er kjøretiden til dette algoritme for å ta oppmøte?
Big O n, fordi i teorien jeg må peke alle i rommet.
>> Nå som en side, hva med annet optimalisering fra uke null?
To, fire, seks, åtte, ti, tolv.
En datamaskin vitenskapsmann ville realisere, vent litt,
som er i størrelsesorden n dividert med to trinn.
Høyre?
Fordi jeg gjør to personer på en gang.
Men vi kommer til å ignorere de lavere ordens ledd,
og vi skal bare kaste bort dividere med 2,
og bare si, stor O av n for at algoritmen også.
>> Hva med denne?
Vi hopper over noen av disse, men hva var en algoritme som var log n?
Det tok omtrent log n trinn?
Den Splitt og hersk.
Nøyaktig.
Som telefonboken eksempel i uke null og tidligere i dag,
der vi delt problemet igjen og igjen og igjen.
Vi trakk det på tavlen i uken null som en buet grønn linje,
og vi sa at dagen var det en logaritmisk algoritme.
>> Og ja, det antall skritt som tar å utføre splitt og hersk,
eller binære søk som vi skal begynne kalle det, som i telefonboken,
er i størrelsesorden loggen og trinn.
Og dette er litt av en merkelig en.
>> Hva tar ett skritt, eller mer spesifikt
et konstant antall skritt?
Kanskje det er to, kanskje det er tre, men en datamaskin vitenskapsmann bare
forenkler den så stor O for en, noen konstant antall skritt.
Hva er noe du kunne gjøre det tar en konstant antall trinn?
>> Hva er kjøretiden til å klappe?
Konstant tid.
Høyre?
Liker, hva er kjøretiden til gjør noe som tar bare ett
drift, som skriver ut F Hello World.
Det kan sies å være konstant tid, mindre mindre hjørne tilfelle med print F,
hva som kan kjøretiden print F faktisk være?
Og hvorfor?
Hva er n måling i dette tilfelle?
>> PUBLIKUM: [uhørlig].
DAVID J. MALAN: Nettopp.
Antallet tegn vi ønsker å skrive ut.
Så det er svært kontekstavhengig.
I dag har vi hatt fokus mye på bokstaver og tall her på bordet.
Men det kan også være tegn i en faktisk streng.
Så det viser seg at det er en annen tiltak som vil begynne å bry seg om,
og det er det motsatte av stor O, så å si.
>> Det er omega-notasjon.
Mens store O betyr det som er, det øvre grense på kjøretiden?
Maksimalt, hvor mye tid kanskje noe å ta?
Omega-- beklager dette fortsetter å komme opp-- er det motsatte av det,
hvor det er en nedre grense på hvor lenge noe kan ta.
>> So. for eksempel, hva er en algoritme som alltid tar n squared trinn?
Vel, en av de algoritmene vi har sett dag, faktisk kan være at også.
Utvalg slag.
Utvalg sorter er ganske dum.
Selv om algorithm-- beklager, selv Hvis rekken allerede er sortert,
utvalg sort kommer til å Fortsett å gå gjennom listen
å sørge for at den har den minste element igjen og igjen og igjen.
Og selv om du mennesker i Publikum vet det, vent litt,
du allerede passert minste element, datamaskinen
ikke vet at før det ser ut hele veien gjennom listen.
Tilsvarende er en nedre grense som kan også tas i betraktning
kan være lineær tid.
>> Hvor lang tid tar det å sort n elementene i den beste
Ved å bruke noe sånt boble liksom?
Anta at listen er allerede sortert.
Vi sa boble liksom tar på rekkefølgen av n kvadrerte trinn.
Men hva hvis det er allerede sortert?
Hva om du skjønner etter ett pass gjennom rekke
at du har gjort noen bytteavtaler?
Har du behov for å fortsette å lage mer pasninger?
>> Nei.
Så en nedre grense på bubble sort kan sies å være lineær.
Omega av n.
Og vi kan se på andre av disse også.
Så la oss ta en rask titt på bare en visualisering her
for å se hvordan disse skiller seg.
Jeg kommer til å gå ned her i denne side som er tilgjengelig på C50 hjemmeside,
men det vil være smertefullt å få jobbe, siden den bruker en teknologi som kalles
Java-applets, som er en i stor grad støttes disse dager,
minst av Chrome og visse andre.
>> Og la meg gå videre og få fart dette opp og forklare hva som skjer.
Dette er en demonstrasjon av boble sortere, den første algoritmen vi så på.
Og det er en visualisering ved at hver av disse stenger representerer et tall.
Jo større bar, jo større antall.
Jo mindre bar, det mindre tall.
Og hva du kan se visuelt, selv men dette går super fort,
er at den røde linjen er som meg, gå frem og tilbake å fikse problemene.
Du kan se at de større elementene er faktisk bobler opp til høyre,
og de mindre elementene er bobler opp til venstre.
Og her nede, hvis vi faktisk ser nærmere,
vi kan faktisk telle antall sammenligninger og swapper
som ble gjort.
>> Men i stedet, la oss se på den andre algoritmen
vi så på tidligere med vår frivillige, utvalg sorter.
Visuelt, har den en svært forskjellig effekt.
Men det er, igjen, veldig intuitivt, i at vi holder velge den nest minste
element, og vi fikk litt heldig.
Det føltes fundamentalt raskere.
Men hvis vi kjørte dette igjen og igjen og igjen med mange innganger,
vi vil se at det er faktisk fortsatt i stor O n squared.
>> La oss gjøre en siste her, innsetting sortere,
som var den tredje algoritme vi så på, og tilbakekalling
at dette omhandler elementer som den støter på dem,
Men da er det kanskje skift ting over for å gjøre plass,
sette inn elementer der de hører hjemme.
>> Og dette også ender opp med å gi den endelige resultatet. Nå er alle tre av dem
følte meg ganske fort.
Og ja, jeg kjørte dem på en ganske god klipp.
Men fundamentalt, de er alle ganske fryktelig, for å være ærlig.
Alle disse algoritmene hittil at ballen stort O n squared
ta seg en bit av tid til å kjøre til slutt.
>> Og ja, kan vi se og mener at dette til slutt
hvis jeg drar opp denne tredje og siste demo.
Dette er en annen visualisering som kommer
vise boble slag på venstre, utvalg liksom i midten,
og noe, som en av våre hånd hever tidligere foreslått,
flette slag på høyre side.
En splitt og hersk strategi til høyre.
Og det er faktisk det vi er skal se på onsdag.
Men la oss tid disse til å kjøre parallelt.
Det er omtrent det samme antall elementer, alle som kjører på samme tid.
Bubble sort vs utvalg sort vs merge sort.
>> Nå er de alle kjører i teorien på samme tid.
CPU går på samme hastighet, men
kan føle hvor kjedelig dette er svært raskt kommer til å bli,
og hvor fort når vi injisere litt av uken
null algoritmer kan vi fart på sakene.
>> Og nå la oss sammenligne disse i en siste form.
Jeg kommer til å gå videre til CS50 hjemmeside, der
vi har dette siste leddet for i dag, der noen på internett
vennlig sette sammen en video som fanger hva forskjellig sortering
algoritmer høres ut som.
Dette er innsetting sort.
>> [Piper]
>> Hvor du søker en frekvens basert på høyden på bar bar.
Dette er boble slag.
>> [Warped pipelyd]
>> Kommer opp neste er-- kommer opp neste er-- utvalg sortere,
der igjen, vi velger den nest minste element,
og vi kan se det voksende fra venstre til høyre.
>> Flett sort, vår vinneren så langt i dag.
Legg merke til hvordan det er å dele ting inn [uhørbart] halv og kvartalene.
Gnome sort, som vi ikke har snakket om, og skaper visuelt
og audally litt av en annen form og lyd.
Går frem og tilbake, rengjøring ting opp.
Sjekk også ut heapsort på denne fyren hjemmeside.
>> Og det er det.
Vi vil se deg neste gang.
>> [Susende OG MUSIKK]