>> [Musik spiller]
>> DAVID J. MALAN: Dette er CS50.
Og dette er starten på ugen tre.
Så vi har fået en masse spændende ting til at dække i dag.
En masse af muligheder for frivillige op på scenen.
Og endelig, i dag er ikke om koden på alle.
Men det handler om ideer, og det handler om algoritmer,
og faktisk bringe tilbage nogle af erfaringerne fra uge nul,
hvor tilbagekaldelse, vi indført denne misfoster.
Og låntagning inspiration fra, at starte
at løse stadigt mere sofistikerede problemer algoritmisk.
Men først et par meddelelser.
Så en, hvis du ønsker at deltage CS50 medarbejdere og klassekammerater til frokost
denne fredag, både her og i Cambridge, og i New Haven,
kan du besøge kursets hjemmeside, hvor der kan findes en URL.
Forelæsning denne onsdag vil ikke være her i Sanders.
Det vil være online kun, så tune ind på CS50 hjemmeside,
om her i Cambridge eller New Haven så godt.
>> Og så problem indstille to allerede er i dine hænder.
Hvis du ikke har dykket ind endnu, lad mig at tilbyde den stærkt formuleret forslag
at, især nu, da problemet sætter forvejen,
du virkelig ønsker at starte nu, hvis ikke fuske lidt i weekenden eller før
når de først gå ud på Fredage, fordi du vil
finder, at de er ikke nødvendigvis bliver længere eller mere udfordrende pr
SE.
Jeg tror, ​​du vil finde, at der i Generelt har de en tendens til at tage ca.
omkring samme mængde tid.
Men det helt sikkert afhænger på den studerendes, og det
afhænger af den tankegang som du nærmer dig det.
Men altid, du vil at køre op mod nogle vægge,
og du kommer til at ramme nogle fejl, og du er bare
ikke vil være i stand til at komme over det på et tidspunkt.
Og det er enormt værdifuldt at være i stand til at træde væk, kom tilbage næste dag,
gå til kontortid, indlæg på CS50 Diskuter eller lignende, til rent faktisk at få blokeringen.
Så holder det i tankerne.
Startende tidligst muligt er det bedste, du kan gøre.
Så her er, hvor vi startede klassen over i uge nul.
Og kan vi få en frivillig her for at hjælpe mig med at finde mikrofoner?
OK.
Stående op allerede.
Kom op.
Gæt det er, hvordan det kommer til at fungere.
Hvad er dit navn?
ALAN ESTRADA: Alan Estrada.
DAVID J. MALAN: Alan Estrada.
Kom op.
Dejligt at møde dig.
ALAN ESTRADA: Rart at møde dig.
DAVID J. MALAN: Og du var her med os i uge nul, selvfølgelig.
ALAN ESTRADA: jeg var.
Jeg var.
>> DAVID J. MALAN: Så kan du gå videre og finde for os Mike Smith,
så hurtigt som du kan?
Så hurtigt som du kan.
Bogstaveligt talt rive problemet i halvdelen som du har brug for.
>> ALAN ESTRADA: Um.
DAVID J. MALAN: Bogstaveligt rive problemet i halve.
>> ALAN ESTRADA: Oh.
Mm.
Meget godt.
>> DAVID J. MALAN: OK.
Godt.
Tak.
ALAN ESTRADA: Meget godt.
OK.
>> DAVID J. MALAN: Og så nu, du har skåret det ned
til halvdelen af ​​problemets omfang.
Nu er vi nede på et kvartal.
Er du opmærksom på hvilken side vi holder?
>> [LAUGHING]
>> ALAN ESTRADA: Ja, jeg tror--
>> DAVID J. MALAN: Hvilke afsnit er vi i?
ALAN ESTRADA: lyddæmper, så.
>> DAVID J. MALAN: OK.
Men Mike Smith går at være efter Lyddæmpere.
So--
>> [LAUGHING]
>> Okay.
ALAN ESTRADA: Hvor er vi på udkig?
DAVID J. MALAN: Mike Smith.
ALAN ESTRADA: Mike Smith.
DAVID J. MALAN: Nu er vi i kirurgisk.
Nu læger.
Nu--
>> ALAN ESTRADA: Let's- lad os gå med rigtige.
Real.
>> DAVID J. MALAN: Real.
OK.
Hvis du har brug for Real.
Nu hvilken vej er Mike Smith?
>> ALAN ESTRADA: Denne vej.
>> DAVID J. MALAN: Hvilken vej?
ALAN ESTRADA: Vent.
M is-- ret?
Vi startede med--
>> DAVID J. MALAN: Ja.
De er forladt.
Din højre.
>> ALAN ESTRADA: Ja.
>> DAVID J. MALAN: Så Mike herinde.
ALAN ESTRADA: Hvad?
>> [LAUGHING]
>> Dårligt eksempel, gutter.
Undskyld.
DAVID J. MALAN: Dette vil lære dig til at springe ud af din stol.
>> ALAN ESTRADA: Oh.
Oh.
Jeg har dig.
Oh.
Dette is-- OK, jeg har dig.
Smith lige her?
>> DAVID J. MALAN: Smith, tak.
Så jeg vil holde udkig op Smith?
>> ALAN ESTRADA: Oh, yeah.
Nej Nej Nej.
Åh nej.
Dette er min.
>> DAVID J. MALAN: Åh, du fik Smith.
OK.
>> ALAN ESTRADA: Ja, jeg fik Smith lige her.
Beklager, gutter.
Jeg troede Michael-- vi ledte efter Michael.
Undskyld.
>> DAVID J. MALAN: Det er OK.
Okay, nu er vi ind Paccini and Sons.
>> ALAN ESTRADA: Paccini og sønner.
DAVID J. MALAN: Kun du og jeg er i på dette.
OK.
Find os Mike Smith.
Smith.
>> ALAN ESTRADA: Smith.
>> David J. MALAN: Smith.
Vi er i R for vrøvl.
ALAN ESTRADA: Dårligt.
Oh.
Dette kommer til at tage et stykke tid.
>> [LAUGHING]
DAVID J. MALAN: Sko.
Vi er i sko.
>> ALAN ESTRADA: Nu er vi gonna--
>> DAVID J. MALAN: Nice.
ALAN ESTRADA: Which--
[LAUGHING]
Åh, det er fantastisk.
[LAUGHING]
>> DAVID J. MALAN: Det er OK.
>> ALAN ESTRADA: Åh, det er godt.
Jeg tror ikke, jeg har tænkt mig at har PSAT buddies efter dette.
DAVID J. MALAN: Godt.
Sporting.
ALAN ESTRADA: Sporting.
Um, L, M, N, O, P.
DAVID J. MALAN: OK.
Så lad os rive det i halve.
Det er ok.
Dette ender dårligt alligevel, fordi Mike Smith vil ikke være i de gule sider.
>> ALAN ESTRADA: Aw.
>> DAVID J. MALAN: Nej, det er OK.
Men lad os lade som han er på denne side.
Så nu har du skåret problemet ned til én side, og vi fandt Mike Smith.
>> [Jublende]
Ok tak.
OK.
Det var ekstraordinært.
Men det var stadig hurtigere end lineær søgning,
hvor vi starter på begyndelsen af ​​bogen,
og vi flytter vores vej fra venstre mod højre, sidst på udkig efter Mike Smith.
Og så, hvis telefonbogen havde måske 1.000 sider,
måske det ville have taget os 10 eller deromkring siden tårer.
>> Men du måske har gearede rørt en antagelse
under alt dette, hvilket vil sige at telefonbogen på forhånd var, hvad?
PUBLIKUM: Sorteret.
DAVID J. MALAN: Det er ordnet.
Højre?
Det er sorteret alfabetisk, så at alle disse navne og numre
sorteres fra A'er til Z s, og alfabetisk i mellem.
Men i dag, vi nu spørger spørgsmålet, ja,
hvordan gjorde Verizon eller telefonen Virksomheden får det ind i denne stat?
>> Fordi det er én ting at udnytte dette synspunkt, og derfor
løse et problem med en algoritme mere effektivt.
Men vi har aldrig rigtig spurgte i uge nul, godt,
hvor meget kostede det Verizon eller en anden
at få den telefon bog i sorteret orden?
>> Højre?
Det betyder ikke noget, hvis se op Mike Smith
er super hurtig, hvis det tager dig en år for at sortere siderne i første omgang.
Højre?
Du kan lige så godt bare finkæmme gennem en randomiseret telefonbog,
hvis det vil være super dyrt at sortere det.
Så hvis vi kan få en anden frivillig.
Lad os tage et kig op her på hvordan vi might-- komme på up-- hvordan
vi måske gå om sortering disse.
>> Og hvis Jordan kunne faktisk slutte sig til os heroppe på scenen.
Kom nu op for bare et øjeblik.
Hvad er dit navn?
CAROLINE: Caroline.
DAVID J. MALAN: Caroline, kom op.
Og du vil blive forenet af mig og Jordan her.
Caroline, tak.
Okay.
Så hvad vi har her Caroline er 26 blå bøger
at FAS bruger at administrere visse afsluttende eksamener.
Disse bliver svært at finde, men hvad vi har gjort i forvejen
er, at vi har lagt en persons navn på forsiden af ​​hver af disse,
men vi har holdt det simpelt ved derefter lægge ud fulde navne.
Så vi ville sætte personen med navnet L, D, J, B, hele vejen A til Z,
men de er i tilfældig rækkefølge.
Og så hvis du ville, taler din vej gennem problem som du
gør det, kan du gå videre og sortere disse for os, fra A til Z.
>> PUBLIKUM: OK, så L er ligesom, midten.
C er begyndt.
B. J før L. B, Q.
>> DAVID J. MALAN: Hold, at tænkte et sekund.
Fordi ellers dette kun interessant for dig, mig og Jordan.
Der vi går.
PUBLIKUM: [uhørligt].
R.
DAVID J. MALAN: OK.
Hvad laver du?
>> CAROLINE: M kommer efter O.
>> DAVID J. MALAN: OK.
>> CAROLINE O.
DAVID J. MALAN: O, Good.
>> CAROLINE E.
>> DAVID J. MALAN: E, F. Ja.
>> Caroline: T, U, V.
>> David J. MALAN: V, T, U, V. Så det ser ud som du er making-- holde ud.
Det ser ud som du gør en stor bunke herovre,
og sådan en stor bunke derovre.
Så den første halvdel af alfabetet, anden halvdel af alfabetet.
OK.
Godt.
Slags opdele problemet i to.
M, N, X. Ja.
CAROLINE: K.
DAVID J. MALAN: OK.
K. Så du slags at vælge dem en efter en,
sætte det enten venstre eller højre, eller Z er foregår på gulvet.
OK.
>> CAROLINE: Z der foregår på gulvet.
>> DAVID J. MALAN: OK.
Y går på gulvet.
Nu kan vi sætte X.
>> CAROLINE: G.
DAVID J. MALAN: G kommer forladt.
S går til højre.
Okay, er en gå hele vejen til venstre.
>> Caroline: A, B, C, D.
>> DAVID J. MALAN: Nu, godt.
Vi har A, B, C. W 's går dernede.
Okay, T.
>> Caroline: H, I, J.
DAVID J. MALAN: H, I, J Godt.
CAROLINE: I centrum, jeg gonna--
DAVID J. MALAN: OK.
Så nu, vi vil slags af flette disse forskellige bunker.
Så A til C, så ser jeg D, og E og F og G, og H og I. Nice.
J, K. Og så, denne bunke er på hovedet, men det er OK.
Sikker.
Vi kan skære nogle hjørner.
OK.
Og så har vi brug W, X, Y, Z.
>> CAROLINE: Ja.
>> DAVID J. MALAN: Excellent.
Så en stor tak til Caroline til sortering disse.
>> [Jublende]
>> Tak.
Mange tak.
Så lad os nu overveje et øjeblik hvordan Caroline gik om at gøre det,
og hvad vi var i stand at-- hvordan vi
var i stand til at løse dette problem, når vi var bare
givet en hel masse tilfældige input.
>> Tja, det ligner der var lidt af et system der?
Højre.
Så de tidligere breve i alfabetet, hun
var at sætte til venstre, og senere bogstaver i alfabetet,
hun lagde i den højre.
Og så snart hun fandt nogle proksimale breve, dem
der går lige ved siden af ​​hinanden, hun ville sætte dem i orden.
Og så vi slags havde disse små bunker af sorterede input, der forekommer.
>> Og så det er helt ligesom hvad de fleste af os mennesker ville gøre.
Vi ville slags finkæmme gennem det, og vi ville slags have en mekanisme.
Men det kan være svært at skrive den ned i en formel per se.
Det føltes lidt mere organisk end det.
Så lad os se om vi kan nu bundet problemet med færre indgange.
>> I stedet for 26, lad os gøre noget langt færre
med blot sige, syv, bag disse døre, så at sige.
Er der kun syv numre?
Og hvis målet nu på hånd er at finde en værdi,
lad os se, hvor effektivt vi kan gå om at gøre dette.
Og lad os se om vi kan nu begynde at anvende nogle tal,
eller nogle formler med til at beskrive effektiviteten af ​​vores telefonbog
algoritme, vores prøve bog algoritme, og mere generelt, at finde oplysninger.
>> Så for dette, så lad mig gå videre, og på berøringsskærmen herovre,
udbudt en webbrowser, der har netop disse syv døre.
Og hvis vi kunne få en anden frivilligt til at komme på herovre,
Jeg har lagt de samme døre herovre.
Hurtig frivillig.
>> Denne en-- demoer går til en hurtigere og hurtigere nu.
Kom ned.
Hvad er dit navn?
TREVOR: Trevor.
>> DAVID J. MALAN: Trevor?
Okay, Trevor, kom ned.
Så Trevor har meldt sig frivilligt her gøre et lignende problem, men en, der er
smallere i omfang, og der kommer at tillade os at forsøge at formalisere nu
fremgangsmåden til sortering disse numre.
>> Så Trevor, rart at møde dig.
Så her er et array, så at tale, en liste over syv døre.
Gå videre og finder os nummer 50.
Og så efter den kendsgerning, fortælle os, hvordan du fandt den.
Bør være-- okay.
Ja, det er den her?
Uh-oh.
OK.
Du klikkede at en.
Godt.
>> Og god.
Nu du klikkede at en.
Og lad mig give dig mikrofonen, så du har det på bare et øjeblik.
Gå videre og klik på næste dør, du ønsker.
Ja, godt.
TREVOR: Kan jeg derefter fjerne markeringen en dør?
DAVID J. MALAN: Nej, du kan ikke derefter fjerne markeringen.
TREVOR: OK.
Denne.
DAVID J. MALAN: Hvor skal du hen?
Hvilken en?
>> TREVOR: At man.
>> DAVID J. MALAN: Nej.
>> TREVOR: OK.
Denne.
>> DAVID J. MALAN: Ja.
Det var godt.
Okay.
Hvad var din algoritme eller procedure til at gøre dette, Trevor?
>> TREVOR: Jeg gik bare igennem døre, indtil jeg fandt en 50.
DAVID J. MALAN: OK.
Fremragende algoritme.
Så det er fint.
Fordi i virkeligheden, hvis jeg afslører, hvad der er bag disse to andre døre, hvad
Vi finder her, er, at vi kun har tilfældige input.
Så det var faktisk så god, som du kunne få.
Og i virkeligheden, du fik bedre end udtømmende søgning hele array,
fordi det ville have været rigtig uheldig hvis du havde ramt nummeret
50 i allersidste dør.
Men hvad hvis vi i stedet gav dig en antagelse.
Antag jeg sortere alle disse døre rundt,
så du har den numre sorteres denne gang,
men denne gang er det faktisk a different-- denne gang,
Det er faktisk sorteret for dig.
Og nu målet ved hånden er at ramme nummer 50.
>> TREVOR: OK.
>> DAVID J. MALAN: Hvad er din algoritme kommer til at være?
>> TREVOR: Tja, hvis det er sorteres, er det enten går
at være-- hvis største til den største, faldende, vil det være den første,
eller hvis det er det modsatte, vil det være den sidste.
Så jeg vil bare trykke på denne dør, og så bare trykke på den sidste dør.
DAVID J. MALAN: Excellent.
Okay.
Så vi fandt nummer 50.
Så så snart du vidste de blev sorteret, vi
var i stand til at udnytte denne antagelse.
Så de er for meget som telefonbogen eksempel.
Så snart du har, selv med et lille problem som dette,
dine input pre-sorteret, vi kan faktisk finde værdien velsagtens
mere effektivt.
>> Og jeg har ikke fortælle dig, hvis det var sorteres små til store, eller store til små,
og så det var meget rimelig at starte på den ene ende eller den anden
faktisk finde, at målværdien.
Så tak til Trevor så godt.
Og jeg vil propose-- pænt gjort.
Vi har et lille klip, faktisk, at er blandt vores foretrukne øjeblikke i CS50,
hvorved nogle gange disse demoer ikke helt går efter planen.
Og faktisk lige nu, jeg trukket op den forkerte grænseflade
med til at bruge den berøringsfølsomme skærm.
Så det var min skyld der.
>> Så dette vil gøre for næste års klip som
til hvorfor jeg klikke på min egen skærm.
Men lad os tage et hurtigt kig på, hvad der skete sidste år
med Jay, der kom løbende, meget ligesom Trevor her, meldte,
og i denne korte klip, vil du se hvordan dette samme demo ikke helt
afslører de samme erfaringer.
[VIDEO PLAYBACK]
-Alle Jeg vil have dig til at gøre nu, er at finde for mig, og for os,
virkelig er antallet 50 et skridt ad gangen.
>> -Den Nummer 50?
>> -Den Nummer 50.
Og du kan afsløre, hvad der er bag hver af disse døre
blot ved at røre den med en finger.
For pokker.
>> [LAUGHING]
>> [END AFSPIL]
DAVID J. MALAN: Så gik meget godt.
Det var de usorterede døre.
Og Jay, selvfølgelig, fandt det alt for hurtigt.
Trevor gjorde et meget bedre job i form af en lærenem øjeblik,
så at sige, i år i tager længere tid at finde den.
Selvfølgelig derefter gav vi Jay en ny chance,
hvorved vi sorteret dørene, ligesom vi gjorde for Trevor,
og Trevor gjorde super godt denne gang.
Men Jay gjorde det halvt så hurtigt.
[VIDEO PLAYBACK]
-Den Mål er nu at også finder os nummer 50,
men gør det algoritmisk, og fortælle os, hvordan du kommer over det.
>> -OK.
>> -Og Hvis du finder det, du holder filmen.
Hvis du ikke kan finde det, du give det tilbage.
>> -Man.
>> -OH!
>> - [Uhørligt] OK.
Så jeg har tænkt mig at kontrollere enderne først til, hvis there's-- bestemme Oh.
>> [Applaus]
>> [END AFSPIL]
DAVID J. MALAN: OK.
Så sortering døre klart fører til større effektivitet.
Og ja, dobbelt så hurtigt er, hvad jeg mente der.
Og så Jay fik heldig begge gange.
Og han også fik heldig i den sidste år, jeg bestilte nogle Blu-ray-diske
til rent faktisk at give ud.
Jeg er ked af dette år, vi havde ikke den samme, Trevor.
Men endnu bedre var et par år tilbage.
Og nogle af jer måske kender denne fyr, Sean, som da han var i CS50,
blev udfordret med den nøjagtige samme problem, dog i SD,
som du snart vil se, tilbage i dag.
Og du opdage, at ikke kun gjorde han tage lidt længere tid end Jay,
lidt længere end Trevor, var det faktisk denne vidunderlige mulighed
til at engagere sig næsten alle i crowd a la Price is Right, fremme
ham til at finde nummeret vi søgte.
Lad os. tage et hurtigt kig.
>> [VIDEO PLAYBACK]
>> -OK.
Så din opgave her, Sean, er følgende.
Jeg har skjult bag disse døre nummer syv.
Men gemt væk i nogle af disse døre samt andre negative tal.
Og dit mål er at tænke af denne top talrække
som blot et array, eller bare sekvens af stykker papir
med tal bag dem.
Og dit mål er, kun at bruge toppen matrix her, finde mig det nummer syv.
Og vi derefter gå til kritik hvordan du går om at gøre det.
-Okay.
-Find Os nummer syv, tak.
Nej.
Fem, 19, 13.
>> [LAUGHING]
>> Det er ikke et trick spørgsmål.
One.
>> [LAUGHING]
På dette tidspunkt, din score er ikke meget godt, så du kan lige så godt holde ud.
Tre.
>> [LAUGHING]
>> Fortsæt.
Helt ærligt, kan jeg ikke hjælpe, men spekulerer hvad du selv tænker, so--
>> [LAUGHING]
Kun den øverste række, så du har fået tre venstre.
Så find mig syv.
>> [LAUGHING]
17.
Syv.
>> [Applaus]
>> Okay.
>> [END AFSPIL]
>> DAVID J. MALAN: Så vi kunne se disse hele dagen lang.
Og nogle af selvfølgelig dette års demoer måske
vil nu ende i næste års video så godt.
Så lad os nu faktisk fokusere på de algoritmer
her, og se om vi ikke kan nu begynde at formalisere
hvordan vi kan gå om at få vores data ind i denne tilstand, at det er sorteret,
så i sidste ende, kan vi faktisk søg det mere effektivt.
Og selv om vi skal hen at bruge forholdsvis små datasæt,
ligesom otte numre, vi har her på brættet,
i sidste ende de samme ideer kunne gælde til 1.000 indgange, en million indgange,
4 milliarder indgange, fordi algoritmerne vil være grundlæggende de samme.
>> Og så dette er vores sidste mulighed for frivillige i dag,
men måske den mest involverede en, som vi har brug for otte frivillige
til at komme op og gå os gennem processen med sortering, hvad der snart
være på disse musikken står her.
Lad mig starte tilbage her.
>> Så man i turquoise-- grønne er det?
Er du begår?
To.
Kom ned.
OK.
Tre.
Fire.
Lad mig-- OK, fem.
Du bliver udpeget af din ven.
Seks, syv, og otte.
Kom op.
Okay.
Mange tak.
Kom op.
>> Okay.
Så det, vi har her-- og dette er blandt de mere akavet dem,
da dette vil kræve, at du humor mig for bare en lille smule tid.
Du skal være nummer et.
Hvad er dit navn?
>> ANNAN: Annan.
>> DAVID J. MALAN: Annan.
David.
Hvad er dit navn?
>> 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ørligt]
DAVID J. MALAN: [uhørligt].
David nummer seks.
MAT: Matt.
DAVID J. MALAN: Matt nummer syv.
Og?
>> WAVERLY: Waverly.
>> DAVID J. MALAN: Waverly, nummer otte.
Okay.
Hvis du could-- hovsa.
Hvis du alt, som din første udfordring, der
er otte musik stande her overfor publikum.
Hvis du kunne sætte dine numre på disse musikken står på en sådan måde
at de i linje med samme tal på tavlen.
Så gør jer selv til at ligne, at ved sætte dine numre på disse musik
står her.
Fremragende hidtil.
>> Fremragende.
OK.
Så nu, vi vil bede spørgsmål i et par forskellige måder.
Hvordan kan vi gå om sortering disse folk her?
Fordi vi havde et par tilgange tidligere, hvorved vi var
slags gør to forskellige spande.
Og så var vi generelt patchwork ting sammen.
Så snart vi så to numre som tilhørte sammen,
vi sætter dem sammen.
To bogstaver, der hører sammen.
>> Men lad os se, om vi kan ikke formalisere dette,
således at vi i sidste ende har nogle pseudo-kode, du vil,
som du kan løse disse problemer.
Så nu, jeg kigger ud på disse numre her.
Og jeg ser en hel masse fejl.
I sidste ende, jeg ønsker en på venstre og otte til højre.
>> Og så jeg kigger på disse to, fire og to.
Og hvad er problemet, naturligvis?
Ja.
So.
To naturligvis kommer før fire, så ved du hvad?
Lad mig først tage en grådig tilgang, hvis du vil, meget gerne problem
sæt en-- hvis du husker fra Standard Edition af Problem Set One,
hvor jeg bare lokalt løse problemet det er lige her foran mig
og se, hvor det fører mig.
>> OK.
Så to og fire, lad mig gå videre og bare bytte dig to.
Hvis du fysisk kan bevæge jer selv og dit papir,
Jeg synes at have fået den listen i en bedre tilstand.
>> Nu, de er gode.
Jeg har tænkt mig at komme videre, fire og seks, ser godt ud.
Ikke et problem.
Seks og otte, OK.
Otte en, et andet problem.
For hvad er sandt omkring otte og en?
Man kommer før otte, og så hvad skal vi gøre?
Lad os bytte disse to.
One og otte.
Og nu, jeg har tænkt mig at holde ud.
Jeg har tænkt mig at holde se fremad.
Og lad os se hvad der sker.
Otte og tre, af naturligvis ude af drift.
Lad os bytte.
Otte og syv, selvfølgelig.
Virker ikke.
Lad os bytte.
Otte og fem, selvfølgelig, lad os bytte.
Okay.
Listen er sorteret.
Ja?
>> OK, naturligvis ikke.
Men det er lidt bedre, ikke?
Fordi varsel, hvad der skete.
Hver gang vi udførte en swap, en mindre Antallet slags sivet den måde,
og et større antal nedsives på denne måde, eller vi
begynde at sige boblede til venstre eller boblet til højre.
>> Nu er det ikke nok, fordi i bedste fald en række måske
har flyttet ét sted frem, eller i værste fald,
en række kan have flyttet et sted yderligere.
Så du ved, hvad denne form af fungerede temmelig godt indtil videre.
Lad mig bare prøve det igen.
To og fire, de er OK.
Fire og seks, de er OK.
Seks og en, ude af drift.
Så lad os bytte dig to.
Og nu, mærke problemet er begynder at få lidt bedre igen.
Seks og tre, ude af drift.
Lad os bytte dig to.
Seks og syv, du er god.
Syv og fem naturligvis ude af drift.
Syv og otte, i orden.
Og nu, kan jeg nødt til at gøre dette et par gange mere.
Og i virkeligheden, tror for jer selv måske hvor mange gange maksimalt
jeg måske nødt til at gå frem og tilbage?
>> Vi vil komme tilbage til det.
Så to og fire er stadig OK.
Fire og en, nej.
Så lad os bytte.
Og igen, mærke visuelt en er slags boblende
til venstre, hvor det burde være.
Fire og tre swap.
Fire og seks.
Seks og fem swap.
Seks og syv.
Syv og otte er gode.
>> Godt.
Vi får endnu bedre.
Så lad os se.
Nu har vi to og en.
Selvfølgelig, bytte.
To og tre, tre og fire, fire og fem, seks og syv, syv og otte.
Godt.
Og ved du hvad?
Fordi jeg lavet én ændring der, lad mig gøre én tilregnelighed check.
Lad mig gå hele vejen tilbage til begyndelsen.
OK.
En, to-- yup, se?
Noget var galt.
Tre, fire, fem, seks, syv, otte.
Og i denne sidste aflevering, er dig komfortabel med min nu
hævdede, at det sorteres?
OK.
Visuelt, det er helt rigtigt.
Men funktionelt, hvad gjorde også bare ske
i den sidste aflevering, der giver dig at bekræfte, at denne liste er faktisk
sorteres?
>> Hvad gjorde jeg gøre eller ikke gøre det sidste pass?
PUBLIKUM: Der var ingen ændringer.
DAVID J. MALAN: Beklager?
PUBLIKUM: Ingen ændringer.
DAVID J. MALAN: Der var ingen ændringer.
Så det ville være dumt af mig at gøre det samme algoritme igen
hvis jeg ikke gøre nogen ændrer første gang.
Og staten har ikke ændret sig.
Sikkert, jeg ikke vil gøre foretage ændringer anden gang.
Og så, det er sikkert nu at sige, er listen sorteres.
>> Og ja, det er nu noget, som vi får generelt
opkald boble sortere, hvorved parvis, du rette fejl igen,
og igen og igen, og du holde gå frem og tilbage,
og frem og tilbage, indtil du foretage sådanne swaps, på hvilket tidspunkt
du kan være sikker, yeah, jeg færdig fastsættelse alle de fejltagelser.
Lad os nulstillet og prøve en anden tilgang.
Hvis du fyre kunne gå tilbage i den rækkefølge, du var for et øjeblik siden,
der lignede dette.
Lad os nu tage en tilgang et lidt mere ligesom eksamen bog,
hvorved vi var konstant vælge bogstav i alfabetet
at vi slags ønskede at behandle næste.
Måske var det en høj bogstav, som A, eller en lav brev Z.
>> Så alle er tilbage i denne rækkefølge.
Og lad mig gøre det.
Lad os se, jeg ved, jeg har otte numre her.
Jeg har tænkt mig at gå videre og bare bevidst vælger
de mindste elementer.
Højre?
Dette synes også intuitiv.
Hvorfor kan jeg ikke finde den mindste element, sætte den hvor den hører,
derefter få den næstmindste element, sætte den, hvor det hører hjemme, og bare gentage.
>> Fordi intuitivt, der bør arbejde også.
Så fire, det er en temmelig lille antal.
Jeg har tænkt mig at huske, hvor det er.
Vent et minut.
To er mindre.
Lad mig nu huske, hvor to er, og glemme alt om fire.
Vi vil beskæftige sig med det senere.
Seks, jeg er ikke interesseret.
Otte, jeg er ikke interesseret i.
Den ene er min nye lille antal.
Så jeg har tænkt mig at huske, hvor man er.
Tre, ikke interesseret.
Syv, ikke interesseret.
Fem, ikke interesseret.
>> Så uden at falde ned scenen i år,
Jeg har tænkt mig at få fat i nummer en-- og hvad var dit navn igen?
>> ANNAN: Annan.
>> DAVID J. MALAN: Annan.
Og hvis du kunne slutte sig til mig på begyndelsen af ​​listen,
lad os sætte dig, hvor du hører til.
Unfortunately-- hvad er dit navn?
>> STEFAN: Stefan.
>> DAVID J. MALAN: Stefan er i vejen.
Så før Stefan løser dette problem, hvad skal vi gøre?
Hvad gør vi med Stefan?
>> PUBLIKUM: [uhørligt].
DAVID J. MALAN: OK.
Så vi kunne gøre det.
Vi kunne slags tage Stefan og hans fire, og bare sætte det i en variabel
og holde på det for en vis mængde tid,
hvorved plads til nummer et.
Og det er ikke dårligt.
Jeg kunne foreslå, hvorfor ikke vi bare sætte Stefan her?
Hvorfor kan dette krænke en af de idéer vi startede
taler om sidste gang, i sidste uge?
Ja?
>> PUBLIKUM: [uhørligt].
>> DAVID J. MALAN: Der er ingen indeks for det.
Hvis du tænker på dette, ja, som en array, det er ligesom negativ,
så der er ingen hukommelse faktisk her, hvis dette er faktisk et array,
ligesom vi erklærede i sidste uge i forelæsning.
Så vi skal ikke gøre dette.
Vi kunne gemme det i en variabel.
>> Eller ved du hvad?
Jeg hørte en anden foreslå det.
Hvad andet kunne vi gøre med Stefan?
Hvorfor gør vi ikke bare smide ham og sætte ham over, hvor nummer et var.
Så hvis du ønsker at gå derovre.
Og ja, det er en temmelig god løsning.
Nu på den ene side, har jeg slags af gjort problemet værre.
Fire er nu længere væk hvorfra det skulle være.
Det bør være mod dette halve.
>> Men ved du hvad?
Det kunne have været uheld.
Måske nummer otte var her.
Og så, måske vi ville har fået heldig,
og skubbede otte tættere på slutningen.
Så i slutningen af ​​dagen, Den slags alle gennemsnit ud.
Vi behøver ikke at bekymre sig om fire.
Alt jeg holder lige nu er vælge den mindste element.
>> Og nu, hvad jeg har tænkt mig at gøre, er at glemme alt om nummer et
permanent, fordi jeg ved det Listen bag mig nu sorteres.
Så min liste var tidligere størrelse otte.
Nu er det i størrelse syv.
Så mit problem er at få mindre, end lineært.
Så nu, jeg skal til at vælge det nuværende mindste element, to.
Seks, otte, fire, tre, syv, fem.
Det var det mindste element.
Så hvad skal jeg gøre med-- Hvad var dit navn igen?
>> JOSEPH: Joseph.
>> DAVID J. MALAN: Joseph?
Vi kommer til at forlade Josef på plads.
Nu, jeg har tænkt mig at foregive at disse fyre are-- godt,
Jeg ved, at disse to allerede sorteret.
Lad os nu fokusere på den Resten af ​​listen.
Seks er den nuværende mindste.
Otte er større.
Fire er nu den aktuelle mindste.
Tre er nu den aktuelle mindste.
Og så nu, jeg har tænkt mig at vælge tre, hvem is-- hvad er dit navn igen?
SERENA: Serena.
DAVID J. MALAN: Serena, hvis du kunne Grib dit nummer og swap med--
Kalsang: Kalsang.
DAVID J. MALAN: Kalsang.
Kom tilbage, og vi er kommer til at bytte de to.
Og nu, lad os sætte dette på autopilot.
Jeg har tænkt mig at gå og overlade det til jer at vælge den næste mindste elementer.
Dun, dun, dun, dun.
Nummer fire, hvad skal du gøre?
Fremragende.
Nu, jeg har tænkt mig at gøre en anden bolden.
Dun, dun, dun, dun.
Jeg ser fem er den næstmindste.
Nu, jeg har tænkt mig at tage en anden pass.
Dun, dun, dun, dun.
Seks er den mindste.
Godt.
Syv er den mindste.
Ingen ændring.
Otte er den mindste.
Færdig.
>> Så hvad vi har netop gjort ved iterativt vælge et element efter den anden
er gennemføre noget, som vi er kommer til at formalisere som udvælgelse slags.
Og det er måske endda enklere at forklare,
i det bogstaveligt talt alt, hvad du ønsker at gøre, er bare holde
gå frem og tilbage gennem listen vælge den næstmindste element,
indtil du er færdig.
>> Så det er endnu enklere, måske intuitivt, end sidste.
Lad os prøve en sidste.
Hvis du fyre kunne nulstille jer i følgende positioner
en sidste gang, lad os se om vi ikke kan nu formalisere en anden tilgang.
Faktisk ville en person derude gerne foreslå
hvordan vi ellers kan gå om at gøre dette?
Uden at smide ud buzzwords eller sortering af svar, der allerede er kendt,
bare intuitivt, hvad kunne vi gøre?
>> PUBLIKUM: [uhørligt].
DAVID J. MALAN: Ja.
Så der er nogle store intuition der.
Gode ​​ting synes at ske hidtil i datalogi, når vi deler
og erobre problemet med at opdele det i halve og halvt.
Og så ja, vi kunne begynde at gøre det.
Og i virkeligheden, er det kommer til at være, vil vi se, en af ​​vores bedste løsninger endnu.
Men lad os vende tilbage til det inden længe.
Faktisk vil vi gøre at lidt senere på ugen.
Hvad andet kan vi gøre for at løse dette?
Så alle her er i tilsyneladende tilfældig rækkefølge.
Du ved hvad?
Snarere end at gå frem og tilbage, frem og tilbage, frem og tilbage
hver gang, det føles Jeg gør en masse Walking.
Hvorfor kan jeg ikke bare starte på begyndelsen af ​​listen,
og bare sætte fire hvor det hører hjemme?
Så lad mig antage for det øjeblik, min liste er kun denne første element.
Er fire sorteres på nuværende tidspunkt, hvis alle jeg holder af, er alt her?
Det er en slags trivielt sandt, ikke?
Ligesom den liste, der indeholder ét nummer, og at nummer fire er naturligvis sorteres.
>> Så lad mig bare fastsætte at denne liste er sorteret.
Men nu har jeg resten af ​​denne liste.
Så nu, støder jeg to.
Hvor kommer to tydeligvis hører med hensyn til fire?
Før fire.
Så hvad kan jeg gøre her?
Hvad er dit navn igen?
>> JOSEPH: Joseph.
>> DAVID J. MALAN: Joseph, hvis du kunne gå tilbage
for bare et øjeblik med dit nummer.
Og nu hvad skal Stefan gøre her?
Lad os flytte Stefan herovre.
Og nu, lad Josef komme herind.
Og nu, lad mig påstå, at alt her er sorteret.
Så lignende resultat, men en fundamentalt anderledes tilgang.
Jeg har ikke engang set, hvad der er dernede.
Jeg bare fortsætte med at tage de elementer da de er givet til mig,
og håndtere dem.
>> Så nu ser jeg nummer seks.
Hvor kommer nummer seks tilhører?
Vi har to, fire, seks.
Præcis hvor hun er lige nu.
Så lad os overlade det alene, og nu hævder, at denne del af listen
er nu sorteret.
Og så, det føles fundamentalt anderledes, idet jeg bare
bevæger sig gennem listen her lineært, og jeg aldrig fordobling tilbage.
Ja.
Okay.
Så otte, hvor vil du hører?
Lige her.
Perfekt.
Så nu, en.
Uh-oh.
Dette føles som om det er ville være dyrt.
Nu, i den foregående algoritme, Jeg har lige byttet mennesker.
Så jeg kan sætte ham hele vejen på begyndelsen, men derefter flyttet Joseph.
Men hvis jeg flytter Josef, nu hvad der kommer til at være galt?
>> Nu har jeg slags undone-- jeg har taget et skridt fremad og derefter
et skridt tilbage, for nu Joseph ville være ude af drift.
Så lad os gøre det.
Hvis du kunne tage nummer et og skridt tilbage for et øjeblik.
Hvordan kan vi put-- hvad var dit navn igen?
>> ANNAN: Annan.
>> DAVID J. MALAN: Annan på plads?
Hvad skal der ske med respekt til to, fire, seks, otte og?
De har alle brug for at flytte.
Så hvis otte ønsker at flytte først, derefter seks, derefter fire, derefter to.
Og så Annan, hvis du ville gerne komme herind, god.
Men her, vi har bare slags betalt en pris
på et andet punkt i algoritmen.
Hvorimod sidste gang med udvælgelsen sortere og endda boble sortere,
Jeg går tilbage og frem, frem og tilbage,
der er helt sikkert addere tidsmæssigt, og bogstaveligt trinvis.
>> Indsættelse sortere, først øjekast ser det er
super smartere, idet jeg bare skrider langsomt, trinvise fremskridt,
men jeg har ikke tænkt mig det frem og tilbage.
Men hvis nogen er faktisk ude af drift, varsel
alt det arbejde, jeg havde bare at gøre.
Jeg måtte flytte halvdelen af ​​listen bare for at gøre plads til nummer et.
Så det er det samme beløb af hidtidige arbejde det
føles, bare en anden type arbejde.
>> Lad os fortsætte.
Så nu ved vi, at alle mellem en og otte sorteres.
Her har jeg nummer tre.
Hvis du kan lide at samle op nummer tre, gå tilbage én.
Og hvad gør du fyre nødt til at gøre?
Yep.
Så det er en anden en, to, tre trin.
Tre tidsenheder, der bare koster mig, så at tre kan nu passe.
Endelig syv.
>> Lad os gå videre og have du tager et skridt tilbage.
Dette er kun vil koste os en enhed af tid, men det er OK.
Og nu, fem kommer til at være lidt dyrere.
Hvis du gerne vil til at træde tilbage.
Vi er nødt til at flytte otte, og syv og seks.
Og så alle er nu sorteres.
Så en stor hånd til vores frivillige her.
Mange tak.
>> [Applaus]
>> Tak allesammen.
Tak allesammen.
Så lad os nu se, hvor kostbare alt dette var.
Lad os betragte måske simpleste af disse, bubble slags.
Og jeg siger enkleste, kun fordi du kan løse det grådigt ved blot
løse den parvise problem her.
Løs den parvise problem her, igen og igen
og igen, at gentage så mange gange som du faktisk har brug for.
>> Så det viser sig, at med en boble sortere, godt,
hvor mange skridt skal jeg tage på den første passage af denne algoritme?
Jeg kunne take-- lad os see-- én, to, tre, fire, fem, seks, syv.
Og der er otte elementer her.
Så det er ligesom n minus 1 trin til komme fra begyndelsen af ​​listen
til slutningen af ​​listen.
>> Men med valg Sorter, minde om, at jeg er vælge elementerne igen og igen
og igen, at mindste, Jeg sætte det på plads,
men så er jeg ikke ser bag mig igen.
Så jeg synes det er lidt mere klar da, at det første gang, jeg kunne
nødt til at tage alle n minus 1 trin at finde det mindste element.
Så jeg sætte dem på plads, og jeg forjage hvem var her tidligere.
>> Men så har jeg ikke til holde udkig på dette element,
fordi jeg ved, det er allerede de mindste.
Så nu kan jeg se på bare syv elementer, derefter seks elementer,
derefter fem elementer, derefter fire elementer.
Og så matematisk, hvis n er antallet af elementer eller numre
at vi startede med, kan du forestille dig at dette er det samme som n minus 1,
plus n minus 2 trin, plus n minus 3 trin,
plus n minus 4 trin, hele vejen ned til kun et skridt.
Og jeg er på min sidste person.
>> Og hvis du husker, at en masse af statistik bøger eller matematiske bøger
har disse formler på Indbundet ryggen eller foran dem,
Det viser sig, at denne serie kan udtrykkes mere enkelt
som n gange n minus 1 over 2.
Og det er fint, hvis det ikke er på forkant med dit sind.
Men dette er faktisk sandt.
Det er bare en enklere måde at skrive det.
Og så hvis du tror tilbage til folkeskolen,
når du bare begynde at multiplicere ting ud, dette er naturligvis,
er bare n kvadreret minus n divideres med 2.
Alt, hvad jeg har gjort, er at udvide udtrykkene der.
Og så lad os omskrive dette lidt anderledes.
Der er n kvadreret divideret med 2 minus n / 2.
>> Så igen, jeg er bare lidt for at anvende nogle aritmetiske regler der.
Men bemærke nu, at den største sigt i dette udtryk, så at sige,
er, at n potens.
Så ja, det er n kvadreret divideret med 2, minus n / 2.
>> Men generelt, hvis n er kommer til at være en stor værdi,
Jeg har tænkt mig at påstå, at n kvadreret vil være den dominerende faktor.
Det er bare kommer til at være en større bidragsyder
til antallet af trin end n / 2.
Så hvad mener jeg med det?
Lad os prøve et simpelt eksempel, selv selvom matematik bliver lidt stor.
>> Så formoder, at vi havde 1 million mennesker på scenen, eller 1 million ting
at vi ønsker at sortere.
Lad os sætte en million i netop denne formel
for at se, hvor mange skridt, det tager alt at sortere en million elementer ved hjælp sige,
udvælgelse slags.
>> Så ville vi have den samme formel som før.
Jeg ville sætte en million, så jeg får en million divideret med kvadratet 2,
minus en million divideret med 2.
Hvis jeg gør det math på forhånd her har vi 500 milliarder
minus 500.000, som giver os 499.999.500.000,
som er temmelig darn stor.
>> Faktisk, hvis du sammenligner nu 499 milliarder, 999 millioner,
500.000 mod vores oprindelige værdi, 500 milliarder, det er så forbandet tæt på.
Højre? n kvadreret divideret med 2 giver os-- eller rettere, n kvadreret divideret med 2
gav os 500 mia.
Det er temmelig darn tæt til 499.999.500.000,
hvilket vil sige at fratrække 500.000, eller mere generelt, at fratrække
n kvadreret, egentlig ikke en big deal.
N kvadreret gør disse tal vokser virkelig hurtigt.
>> Nu, dette er kun vigtigt i det omfang som vi, som dataloger,
er generelt ikke til at passe så meget om nuancerne i disse formler
og præcis, hvad den præcise svar er.
Vi pleje kun det, ved du hvad?
Ved slutningen af ​​dagen, denne formel er af størrelsesordenen n potens.
>> Ja, vi dividere med 2 derinde.
Ja, vi fratrække off n minus 2.
Men i slutningen af ​​dagen, udtrykket der virkelig gør ondt os og koster os
en masse af trin er, at firkantede sigt.
Og så hvad datalog vil generelt gøre
er ignorere alle de mindre ordens led,
og bare se på den, der bidrager mest til omkostningerne.
>> Og det er rart, fordi vi kan nu taler i langt større generalitet
om algoritmer, og kan sammenligne dem.
Og det faktum, at jeg er ved hjælp af denne O er bevidst.
Når jeg siger på ordren af, jeg er specielt
henvise til noget kaldet big O. og store O
er en notation, at en computer videnskabsmand bruger til at beskrive
en øvre grænse på noget.
>> Så hvis du siger, at en algoritme er i stort O n kvadreret,
som jeg foreslog bare en øjeblik siden, det betyder
at med hensyn til dets drift tid eller dens effektivitet,
det tager i størrelsesordenen n kvadreret trin.
Måske mere, måske mindre.
Men det er på rækkefølgen af ​​n potens.
Og det er den øvre grænse.
Det kommer ikke til at være mere smertefuld end det.
Det kommer ikke til at være n kubik, eller 2 til n eller noget meget større.
Dette er en øvre grænse på hvad det koster.
Så da, lad os overveje blot et par eksempler.
Og dette er blot en begrænset liste af meget almindelige kører tider
for algoritmer, der er beregnet til at være illustrativ for nogle ting, vi har
set allerede.
>> Så for eksempel i tilfælde af udvælgelse sortere, hvad jeg påstår her
er, at udvælgelsen sortere s kører tid er af størrelsesordenen n potens.
I værste fald, vil jeg have en hel masse tilfældige tal her.
Og som vi så matematisk, hvis jeg fortsætter med at gå
gennem listen, gennem listen, vælge den næstmindste
element igen og igen, hvis jeg faktisk nedskrive alle trinnene
Jeg tager som jeg foreslog formulaically før, er det på rækkefølgen af ​​n kvadreret
skridt, jeg tager.
>> Og det viser sig, at boble sortere og indsættelse sortere
er lige så langsomme i værste fald.
Overvej for eksempel, indsættelse sortere, det allersidste algoritme vi behandlet,
som havde os se på det element, og derefter indsætte det hvor det hører hjemme.
Og så har vi kigget på det næste element, og indsat det, hvor det hører hjemme.
>> Så overveje den bedst mulige scenario.
Antag jeg havde mine frivillige linje op bogstaveligt som dette, en gennem otte,
allerede sorteret.
Hvor mange trin er indsættelse sortere kommer til at tage for at sortere otte personer,
hvis de ankommer på scenen ser sådan ud?
>> Otte mennesker allerede ordnet.
Og jeg bruger indsættelse slags.
Det sidste af de algoritmer.
Nå, lad os reenact virkelig hurtigt.
Så hvis jeg starter her, ser jeg en.
Hvor kan man hører?
Det tilhører lige her.
Jeg ser to.
Hvor kommer to hører?
Lige her.
Jeg ser tre.
Hvor kommer tre tilhører?
Lige her.
>> Jeg ser fire.
Lige her.
Fem, seks, syv, otte.
Der er ingen grund til at gentage mig selv.
Og så, hvor mange skridt er, at i forhold til n?
Det er på rækkefølgen af ​​n trin, højre? n minus 1.
Men jeg tog en lineær nummer trin, og nu er jeg færdig.
Så det er det bedste tilfældet, selv om.
Hvad med det værst tænkelige?
Hvilke otte var derovre, og syv var dernede,
og en og to var herovre, så at listen virkelig var omvendt?
>> Nå, hvad sker der faktisk hvis dette er nummeret?
Og vi vil gøre blot et par eksempler.
Hvad hvis ja, nummer otte er her, og de number-- hovsa.
Så hvad nu hvis, ja, antallet otte er hele vejen over her,
og jeg bruger indsættelse slags?
>> OK.
Jeg hævder i det øjeblik, det er på plads.
Men nu, seven-- hvor kommer syv hen?
Selvfølgelig er det går over her.
Så jeg er nødt til at flytte otte over et sted.
Nu seks, hvor går det gå?
Nå, okay.
Nu har jeg til at flytte otte i løbet af et sted, og syv over et sted,
og så jeg plask ned seks.
>> Så den første gang, det koste mig et skridt til at løse tingene,
så det kostede mig to trin til at løse tingene.
Hvor mange trin er det kommer til at tage for at løse
ting at sætte fem i det rigtige sted?
Tre.
Fordi nu er jeg nødt til at flytte en, to, tre.
Hvor mange trin er det kommer til at tage at sætte fire i det rigtige sted?
4 plus 5 plus 6, plus 7.
>> Og så det er matematisk identisk med hvad vi beskrevet for valg Sorter.
Vi har denne serie der er bare stigende.
1 plus 2 + 3 + 4, eller omvendt, 7 plus 6
plus 5 plus 4 tilføjer op til nutidens formål til på rækkefølgen af ​​n potens.
>> Så lad mig fastsætte også, at boble sortere er også i n potens.
Fordi med boble sortere, hver gang jeg går gennem listen,
Jeg tager nogenlunde hvor mange skridt?
Hver gang jeg bogstaveligt talt gå derfra til der?
Omkring n trin.
Men hvor mange gange jeg måske nødt til at gå gennem listen?
>> Nå, groft n tid.
Måske n minus 1, men groft n gange.
Tja, hvorfor er det?
Nå, med boble sortere, hvis vi starter med boble sortere,
med listen i den værst mulige situation, som igen er helt
baglæns, hvad der kommer til at ske?
Jeg går gennem listen, og nummer man hører hele vejen derovre.
>> Men med boble sortere, hvor langt gør man bevæge sig på min første passage gennem listen?
Hvor mange pletter får han tættere på det rigtige sted?
Bare en.
Så hvis du slags årsag gennem denne, hver gang gennem denne algoritme,
Davids tager ca n trin.
Men hvor mange gennemløb gennem listen er det
vil tage for en at boble til venstre hvor den hører hjemme?
>> Han har fået til at bevæge sig ud, n rum på denne måde.
Så bare for at gøre sorteringen af ​​listen, Jeg er nødt til at gå frem og tilbage n gange.
Og hver gang, jeg er ser på n elementer.
Så gør n ting n gange på rækkefølgen af ​​n potens.
>> Nu vil vi se på nogle af shorts, der
er indlejret i CS50 næste problem sæt, en anden fremgangsmåde på disse,
men for nu, lad os bare overveje nogle andre kører tider,
især hvis sortering dem tage en lille smule tid til at synke i.
Hvad er en algoritme, vi har set allerede der tager i størrelsesordenen n trin?
>> Hvad skal tage en lineær nummer af trin, vi har set indtil videre?
Hvad er det?
Telefonbogen søgning.
Den første algoritme.
Højre?
Hvor vi er lineært søger efter Mike Smith?
Faktisk.
Fra uge nul, da jeg startede dreje én side ad gangen,
og jeg selv sagde, at det var venlig af en lineær følelse algoritme,
og vi havde at billedet på bord med den lige røde linje
og lige gul linje, der faktisk var
algoritmer, der er i store O i n.
>> Fordi at finde Mike Smith i en telefon bog af n sider, i værste fald,
kan tage mig n trin.
Hvad med at tage fremmøde?
En to tre fire fem seks.
Hvad er køretid for denne algoritme til at føre protokol?
Big O i n, for i teorien I nødt til at pege alle i lokalet.
>> Nu som en sidebemærkning, hvad med andet optimering fra uge nul?
To, fire, seks, otte, 10, 12.
En computer videnskabsmand ville indse, vent et minut,
der er på rækkefølgen af n divideret med to trin.
Højre?
Fordi jeg gør to personer ad gangen.
Men vi kommer til at ignorere disse lavere ordens led,
og vi bare gå til smide dividere med 2,
og blot sige, store O i n for denne algoritme samt.
>> Hvad med denne her?
Vi vil springe over nogle af disse, men hvad var en algoritme, der var log n?
Det tog omtrent log n trin?
Den kløft og erobre.
Præcis.
Ligesom telefonbogen eksempel i uge nul og tidligere i dag,
hvor vi delt problemet igen og igen og igen.
Vi trak det i bestyrelsen i uge nul som en buet grøn linje,
og vi sagde, at dag var en logaritmisk algoritme.
>> Og ja, antallet af skridt it tager at udføre del og hersk,
eller binær søgning som vi starter at kalde det, som i telefonbogen,
er af størrelsesordenen log og trin.
Og det er lidt af en underlig en.
>> Hvad tager et skridt, eller mere specifikt
et konstant antal trin?
Måske er det to, måske er det tre, men datalog bare
forenkler det så stor O på 1, nogle konstant antal trin.
Hvad er noget, du kunne gøre det tager et konstant antal trin?
>> Hvad er køretid for at klappe?
Konstant tid.
Højre?
Ligesom, hvad er køretiden for gøre noget, der tager kun én
drift, ligesom udskrive F Hello World.
Det kunne siges at være konstant tid, medmindre mindre hjørne tilfældet med print F,
Hvad kan køretiden af print F faktisk være?
Og hvorfor?
Hvad er n måling i dette tilfælde?
>> PUBLIKUM: [uhørligt].
DAVID J. MALAN: Præcis.
Antallet af tegn Vi ønsker at udskrive.
Så det er meget kontekstafhængig.
I dag har vi haft fokus meget på bogstaver og tal her på brættet.
Men det kan også være tegn i en faktiske strengen.
Så det viser sig der er en anden foranstaltning, der vil begynde at bekymre sig om,
og det er det modsatte af store O, så at sige.
>> Det er omega notation.
Hvorimod store O betyder, hvad der er den øvre grænse på din køretid?
Maksimalt, hvor meget tid måske noget tage?
Omega-- ked dette holder kommer up-- er det modsatte af det,
hvorved det er en nedre grænse på mængde tid noget kan tage.
>> So. for eksempel, hvad er en algoritme der tager altid n firkantede trin?
Tja, en af ​​de algoritmer vi har set dag, i virkeligheden kan være, at så godt.
Udvælgelse slags.
Valg Sorter er temmelig dumt.
Selv om algorithm-- ked, selv Hvis array allerede er sorteret,
valg Sorter kommer til at fortsætter med at gå gennem listen
for at sikre det har den mindste element igen og igen og igen.
Og selvom du mennesker i publikum ved, at vente et øjeblik,
du allerede bestået mindste element, computeren
ikke, at indtil det ser hele vejen gennem listen.
Ligeledes en nedre grænse, at kan også tages i betragtning
kan være lineær tid.
>> Hvor meget tid tager det at Sorter n elementer i den bedste
tilfælde ved hjælp af noget som boble slags?
Antag, at din liste er allerede sorteret.
Vi sagde boble slags tager på rækkefølgen af ​​n kvadreret trin.
Men hvad nu, hvis det er allerede ordnet?
Hvad hvis du er klar efter en passage gennem array
at du har lavet nogen swaps?
Har du brug for at holde gøre flere afleveringer?
>> Nej.
Så en nedre grænse på boble sortere kan siges at være lineær.
Omega af n.
Og vi kan se på andre af disse.
Så lad os tage et hurtigt kig på kun en visualisering her
at se, hvordan disse adskiller sig.
Jeg har tænkt mig at gå ned her i dette side, der er tilgængelig på C50 hjemmeside,
men det vil være en smerte at få arbejde, da den bruger en teknologi kaldet
Java applets, hvilket er en stort set ikke understøttes i disse dage,
i det mindste ved Chrome og visse andre.
>> Og lad mig gå videre og fremskynde denne op og forklare, hvad der foregår.
Dette er en demonstration af boble sortere, den første algoritme vi kiggede på.
Og det er en visualisering, at hvert af disse søjler repræsenterer en række.
Jo større bar, jo større nummeret.
Jo mindre bar, Jo mindre tallet.
Og hvad du kan se visuelt, selv selvom dette foregår super hurtig,
er, at den røde bar er ligesom mig, walking og tilbage fastsættelse problemer.
Du kan se, at de større elementer er faktisk gennemstrømning op til højre,
og de mindre elementer er gennemstrømning op til venstre.
Og hernede, hvis vi faktisk ser nærmere,
Vi kan faktisk tælle Antallet af sammenligninger og swaps
der blev foretaget.
>> Men i stedet, lad os se ved den anden algoritme
vi kiggede på tidligere med vores frivillige, udvælgelse slags.
Visuelt, det har en meget anderledes effekt.
Men det er, igen, meget intuitiv, i at vi holder vælge den næstmindste
element, og vi fik lidt heldig.
Der følte fundamentalt hurtigere.
Men hvis vi kørte dette igen og igen og igen med masser af input,
ville vi se, at det er faktisk stadig i store O n potens.
>> Lad os gøre et sidste her, indsættelse sortere,
som var den tredje algoritme vi kiggede på, og tilbagekaldelse
at denne ene handler om elementer, som det møder dem,
men så er det måske skift over tingene for at gøre plads,
indsætte elementer, hvor de hører til.
>> Og dette også ender med at give endelige resultat. Nu er alle tre af dem
følte temmelig hurtigt.
Og ja, jeg kørte dem på en temmelig god klip.
Men fundamentalt, de er alle temmelig forfærdeligt, at være ærlig.
Alle disse algoritmer hidtil at løb store O i n kvadreret
tage en hel del af tid til at køre i sidste ende.
>> Og ja, kan vi se og føler det endelig
hvis jeg trækker op denne tredje og sidste demo.
Dette er en anden visualisering, der kommer
at vise boble sortere til venstre, valg Sorter i midten,
og noget, som en af ​​vores hånd hæver tidligere foreslået,
mergesort til højre.
En kløft og erobre strategi til højre.
Og det er i virkeligheden, hvad vi er kommer til at se på onsdag.
Men lad os tid disse til at løbe parallelt.
Det er nogenlunde det samme antal elementer, der alle kører på samme tid.
Bubble sortere vs udvælgelse sortere vs mergesort.
>> Nu, de er alle kører i teorien samtidig.
CPU'en kører på samme hastighed, men du
kan føle hvor kedeligt det er meget hurtigt ved at blive,
og hvor hurtigt, når Vi indsprøjte en smule uge
nul algoritmer kan vi fremskynde tingene op.
>> Og lad os nu sammenligne disse i en sidste form.
Jeg har tænkt mig at gå videre til CS50 hjemmeside, hvor
vi har denne sidste led for i dag, hvor en person på internettet
venligt sammensætte en video, indfanger hvad forskellige sortering
algoritmer lyder.
Dette er insertion slags.
>> [Bip]
>> Hvorved du anvender en frekvens baseret på højden af ​​bar bar.
Dette er boble slags.
>> [Skæv bip]
>> Kommer op næste is-- kommer op næste is-- udvælgelse sortere,
hvor igen, vi vælge den næstmindste element,
og vi kan se det voksende fra venstre mod højre.
>> Mergesort, vores vinder hidtil dag.
Læg mærke til, hvordan det er at opdele tingene ind [uhørligt] halvdelen og kvartaler.
Gnome slags, som vi ikke har talte om, og skaber visuelt
og audally lidt af en forskellig form og lyd.
Går frem og tilbage, rengøring tingene op.
Du kan også læse heapsort på denne fyr hjemmeside.
>> Og det er det.
Vi vil se dig næste gang.
>> [Susen OG MUSIK]