Tip:
Highlight text to annotate it
X
>> [Musik Spela]
>> DAVID J. MALAN: Okej.
Så välkommen tillbaka.
Detta är CS50, och är I slutet av vecka tre.
>> Så minns under de senaste veckorna, Vi har spenderat en hel del
tid på C, på programmering, på syntax.
Och det är helt normalt, om du fortfarande kämpar med Problem Set 2, för att vara
banka huvudet mot väggen.
Det är kryptiskt utseende felmeddelanden och buggar som du
kan inte riktigt jaga.
Därför, vara säker, att på bara en några veckor kommer du att se tillbaka på
saker som Caesar, och [? V-Genair,?] kanske Crack, och
inse hur långt du har kommit under en kort tidsperiod.
Så om det är någon tröst, hänga där för nu.
>> Men i dag börjar vi att övergången till saker högre nivå.
Och vi börjar ta för givet att ni vet hur man programmerar, eller vid
minst en begynnande att komfort nivå.
Och vi kommer att börja fundera över hur vi kan gå om att utforma programmen mer
effektivt.
Hur vi kan gå om att optimera effektivisera våra algoritmer, och
generellt lösa mer intressanta problem.
Och börjar ta för givet att, om vi ville, vi kunde koda upp någon
av de exempel vi har i åtanke.
Så idag, rör vi inte tangentbordet för någon form av kod.
Det kommer att bli mycket högre nivå, och slutligen, om problemlösning.
>> Så för att komma till den punkten, låt mig föreslå att följande sju
rektanglarna representerar sju dörrar, bakom vilket är en hel ***
siffror, bland vilka är antalet 50.
Låt mig projicera detta på detta Skärmen här också.
Och föreslå att vi behöver en frivillig till hjälpa till att hitta mig ett nummer framför
Internet här för att se.
Kom upp, i rosa.
Okej.
Vad är ditt namn?
>> JENNIFER: [OHÖRBAR]
>> DAVID J. MALAN: Förlåt?
>> JENNIFER: Jennifer.
>> DAVID J. MALAN: Jennifer.
Okej, Jennifer.
Trevligt att träffas.
Kom upp.
Så dessa är här sju dörrar, och vad Jag vill att du ska göra för oss här,
framför allt av dina klasskamrater, är att hitta oss numret, 50.
För att hitta ett nummer, kan du kika in bakom någon av dessa dörrar genom att helt enkelt knacka
på en av dörrarna, och det kommer att avslöja dess nummer.
Och låt oss se hur snabbt du hittar oss numret, 50.
>> 15.
16.
50.
Snyggt gjort.
Okej.
Applåd för Jennifer.
>> [Applåder]
>> Okej.
Så vad var din strategi för hitta numret, 50?
>> JENNIFER: Um, tänkte jag kanske om -
[OHÖRBAR]
>> DAVID J. MALAN: Åh.
Ge det en sekund.
Så var din strategi för hitta numret, 50?
>> JENNIFER: Så jag bara börja på börjar se vad det första numret
var, och då tänkte jag, kanske om de är sorterade, ska jag bara hålla
knacka högre upp?
>> David J. MALAN: OK.
Och vi verkar ha hittat att vara fallet.
Även om, låt oss dra tillbaka skikten bara lite, och du vill gå
framåt och avslöja de andra dörrarna du kunde ha valt?
>> JENNIFER: Åh, kära.
>> DAVID J. MALAN: Ah.
>> JENNIFER: Så jag hade tur.
>> DAVID J. MALAN: Så du hade tur.
Okej.
Så inte illa.
Men det är en intressant insikt, rätt?
Om du antar, och du fick, faktiskt, lite tur där.
Men om du antar att siffrorna var sorteras, kan du vara mer exakt
om hur det påverkade ditt beteende?
>> JENNIFER: Så om de sorteras, jag tänkte minsta till största.
>> David J. MALAN: OK.
>> JENNIFER: Eller om det slutade riktigt stora, då största till den minsta.
>> David J. MALAN: OK.
Så största till den minsta, eller minsta till största.
Men låt mig föreslå, antar att du hade fått otur, och antar att de
var inte, i själva verket, sorteras, hur många av dessa dörrar kanske du har haft att kika
bakom i det värsta fallet?
>> JENNIFER: Alla av dem.
>> DAVID J. MALAN: Alla av dem.
Så låt oss generalisera det som n.
Det råkar vara 7, men låt oss mer generellt säga att det finns n dörrar på
skärmen här.
Så i värsta fall, skulle du ha att titta bakom 7 dörrar eller n dörrar.
Och så det här är egentligen, det är lite av lycka idag, men det är verkligen en linjär
algoritm av slag, även om du var typ av hoppa runt.
Är det rättvist?
>> JENNIFER: Yeah.
>> DAVID J. MALAN: Nåväl, låt mig se om din strategisk förändring om jag flyttar oss till
vår andra exempel här med 7 olika dörrar.
Samma nummer, men detta tid de är sorterade.
Vad är din strategi här kommer att bli, försöker sätta ur ditt sinne vad
de andra siffrorna var -
>> JENNIFER: OK.
>> DAVID J. MALAN: - tidigare?
>> JENNIFER: Låt oss börja med den första.
>> DAVID J. MALAN: Okej.
Börja med den första.
4.
Nu var du ska gå, och varför?
>> JENNIFER: 4 är verkligen liten.
Så om de är sort kanske minsta till störst, bör det
vara dubbelt så, och -.
>> David J. MALAN: OK.
Låt oss se, som du tror?
>> JENNIFER: Pröva den sista.
Trevligt.
>> DAVID J. MALAN: Mycket snyggt gjort.
Okej.
>> [Applåder]
>> David J. MALAN: OK.
Så du faktiskt gör detta fruktansvärt, eftersom du är
gör det mycket bra.
Vilket lämnar oss inte göra vissa punkter.
Så låt oss försöka rulla tillbaka hit.
>> JENNIFER: OK.
>> DAVID J. MALAN: Mycket bra gjort ändå.
Så du började i början, du såg att det var 4, då du
flyttas till slutet.
Men antar att du inte tur det, och antar att 50
var någon annanstans.
Vad din tredje steget har varit?
>> JENNIFER: Gå tillbaka till början.
>> DAVID J. MALAN: Gå tillbaka till början.
OK, så du skulle har rört denna dörr, som var 8.
Okej.
Så det är inte 50.
Var skulle du ha sett nästa?
>> JENNIFER: Om jag inte vet de sorteras.
>> DAVID J. MALAN: Rätt.
Tja, om du visste de sorteras -
>> JENNIFER: Åh, visste, ja.
>> DAVID J. MALAN: - men du gjorde inte vet var 50 var ännu?
>> JENNIFER: Fortsätt bara.
>> DAVID J. MALAN: Okej.
OK.
Keep going.
OK, som jag kan jobba med.
>> JENNIFER: OK.
>> DAVID J. MALAN: Nu, om du bara kommer att fortsätta, vad är din
algoritm som överflyttas backat in.
>> JENNIFER: Den linjära -.
>> DAVID J. MALAN: Det är typ av linjärt.
Men låt mig föreslå, låt mig sätta på plats.
Låt mig uppdatera sidan.
samma nummer, samma arrangemang, Samma dörrar.
Men tänker tillbaka på den första dagen i klassen när vi rev en telefonbok i
hälften, typ av, och vad som var vår strategi där?
>> JENNIFER: Börja på mitten.
>> David J. MALAN: OK.
Så börja i mitten.
Så låt oss gå vidare och simulera det.
Börja i mitten av avslöjar att dörren.
Så antalet 16.
Så vad skulle den starka killen har gjort, som rev telefonboken i hälften,
för att komma till nästa gissning?
>> JENNIFER: Gå in här halvåret.
>> DAVID J. MALAN: Och varför till höger?
>> JENNIFER: Om de var slags minsta till största, så 50 bör vara
vid denna ände.
>> DAVID J. MALAN: Bra.
Helt rimliga.
Så som en telefonbok, går du till rätt i motsats till vänster, men här
är nyckeln take-away.
Du kan nu kasta bort, eller riva av, hälften av detta problem, så att du inte
med 7 dörrar, men egentligen med bara 3.
Vilket är ungefär hälften av problemets storlek.
Okej.
Så nu vad du skulle ha göras efter att du går rätt?
>> JENNIFER: Så 16 är fortfarande ganska liten, förhållande till 50, så kanske jag ska försöka,
liknande, här.
>> DAVID J. MALAN: Okej.
42.
Okej, så nu vad är din instinkt säger dig?
>> JENNIFER: Jag kan kasta bort detta och sedan bara -
>> David J. MALAN: OK.
Bra, kan du kasta bort den vänstra halvan där.
>> JENNIFER: - Välj här.
>> DAVID J. MALAN: Och höger.
>> JENNIFER: Yeah.
>> DAVID J. MALAN: Så även om det är svårt att se kanske, när det bara
7 dörrar, tänka, nu, samstämmigheten i
algoritm kan tillämpas bara.
I det förra fallet, har du tur, som var stor.
Men du gjorde använder en heuristisk, Jag skulle vilja säga.
Du använde sorts dina instinkter, och veta om det sorteras, om det är ganska
litet i början, naturligtvis, har vi fick gå mer åt höger.
Men i någon mening, fick du tur, eftersom kanske detta var antalet 100,
och kanske 50 var mer i mitten.
Kanske 50 var även hit.
>> Men vad du gjorde en lite annorlunda denna gång var, du gjorde samma sak
igen och igen.
Och jag skulle vilja hävda att det du just gjorde, om än påverkad av telefonen
Boken exempel, är något mycket mer algoritmisk, och mycket
mindre speciell kapslade.
Mycket mindre instinktiv.
Så i slutet av dagen, hur skulle du beskriva effektiviteten i
första algoritmen, där du gick vänster till höger, kontra
andra algoritm här?
>> JENNIFER: detta bör man, liksom, kanske halvera tiden, eller ännu mer, ja.
>> DAVID J. MALAN: OK, kanske ännu mer.
Låt oss skjuta lite hårdare på det.
Vad som verkligen, om vi fortsätter detta logik, halverade vi definitivt
gångtid med denna andra algoritmen genom att kasta bort hälften av
siffror, men vad gjorde vi på nästa iteration, när Jennifer avslöjade
det andra talet?
>> Vi halverade antalet dörrar igen.
Och vad gjorde vi efter det, om det fanns fler dörrar att leka med?
Vi skulle halvera dem, och igen, och igen, och igen.
Och det var precis som ni alla står upp på den första veckan i
klass, hälften av er som sitter ner, hälften av er som sitter ner, hälften av er
sitta ner, tills en ensam själ stod.
Och vi sa att gångtiden att var antalet steg det tog
på order av vad?
>> Högtalare 1: [OHÖRBAR]
>> DAVID J. MALAN: Så log bas 2 i N, eller bara helt enkelt, logga n.
Så något logaritmisk.
Och grafen var inte en rak linje som bara blev värre och värre, det var
denna intressanta kurva som inte gjorde det får så dåligt över tid.
Så låt oss hålla fast vid denna idé.
Låt oss tacka Jennifer.
Tack så mycket för kommande vidare upp.
Och, en sek.
Inga skrivbordslampor dag, men vi har CS50 stress bollar.
>> JENNIFER: Yay.
>> DAVID J. MALAN: Okej, här.
Tack för att du ådra stress här uppe.
Okej.
Så låt oss se om vi kan inte nu formalisera detta lite mer.
Så återigen, var vad vi just gjorde i princip samma sak som vi gjorde
i den första veckan.
Men snarare än att avsluta med bara en linjär algoritm, som vi avbildade
tidigare som denna raka linje, varvid, om vi lägger ytterligare en dörr på
skärmen, då Jennifer skulle har haft att se, potentiellt,
bakom ett mer dörr.
Om vi lägger två dörrar, kan hon ha att titta bakom två dörrar.
>> Och så fanns det linjära förhållandet mellan storleken på den
problem på, säg, x-axeln och den tid det tar att
lösa på y.
Men bilden jag syftade på tidigare var detta gröna linjen.
Grön medvetet, eftersom det kändes bara bättre.
I teorin, algoritmen, när vi gjorde det med telefonboken, när vi gjorde det
med er räknar varandra, och i det andra fallet, när Jennifer bara
gjorde upp det här, var det slags av fundamentalt bättre.
För det var inte bara dubbelt så snabb.
Det var inte ens fyra gånger så snabbt.
Det var helt och hållet beroende av vad storleken hos den inmatade var, om hur många
åtgärder den tog ***.
>> Och så denna enkla idé som vi alla tog för givet med telefonboken,
kan på liknande sätt appliceras att något sånt här.
Och detta kan vara mer nonchalant kallas, som ni kanske
föreställa, söndra och härska.
Inte olikt vad vi gjorde, naturligtvis, med telefonboken.
>> Men pseudokoden, minns, var det.
Så vi kommer inte att göra det igen, men minns den första veckan, stod vi alla upp
och sedan hälften av er satte sig ner, hälften av du satt, satt hälften av er ner.
Denna algoritm har genomförts i en lite av en fusk sätt, i det, det
var inte bara en av mig räkna, fundamentalt, mer effektivt.
I så fall, var jag utnyttja en sekundär resurs.
Sortera på, flera processorer, flera hjärnor, flera smarta människor i
Rummet var att hjälpa mig att komma från något linjär till något
logaritmisk, från något röd till något grönt.
>> Men i detta fall, Jennifer ensamt kan grunden förbättra det
fullgöra sitt första algoritmen med, igen, bara tänka lite hårdare.
Och nu, när det blir dags att genomföra dessa saker, räkna ut
vilka rader kod kan du skriva en sådan att du kan upprepa dem igen, och
igen, och igen, typ av i en looping mode.
Eftersom du inte kommer att ha lyx, som Jennifer gjorde i början, för att
bara ha en hel hög med ifs och säga, hmm, om det första numret är 4,
låt mig gå hela vägen till slutet.
Ooh, om detta antal är för stor, Låt mig gå godtyckligt tillbaka
till det andra elementet.
Du kommer att upptäcka att det kommer att bli en hel del svårare att formalisera vad vi människor
tar för givet så mycket rimlig heuristik, men en dator är endast
kommer att göra det du ber den att göra.
>> Nu har mycket intressant konsekvenser.
Denna graf slags tänkt att sortera på överväldiga visuellt, men varsel, där
är den raka linjen i detta diagram?
Var är den linjära grafen som vi kallar n?
Tja, det är typ av mot botten av denna bild, eller hur?
Så allt vi har gjort är att vi har slags utzooming till x-axeln och
y-axeln för att försöka få en känsla för vad andra typer av kurvor ser ut.
>> Och detaljerna i den matematiska uttryck idag inte kommer att fråga så
mycket, men märker att det finns en hel del algoritmer som är långt värre än
något som är linjär.
I själva verket ser n kubik ganska dåligt.
2 till n ser ganska illa. n kvadrat ser ganska illa.
Och vi får se vad några av dem kan vara i verkligheten idag.
Och log n känns inte så illa, men bättre än n är log bas 2 n.
Men du vet, det skulle ha varit ännu mer fantastiskt om Jennifer, eller om vi,
den första veckan, hade kommit med något som är log för logaritmen för n.
>> Så med andra ord, det är denna helhet spektrum av möjliga lösningar på
problem, men även här meddelandet vad som kommer att hända.
När jag zoomar ut, vilket av dessa kurvor kommer att visa sig vara den absoluta
värsta av dem på skärmen nu?
Så n kubik ser ganska dåligt för tillfället.
Men om vi zooma ut och se mer av x och y-axeln, som kommer att
dominera ***ändan?
Så visar det sig faktiskt att två till n, och du kan räkna ut det genom att bara
ansluta vissa allt större siffror, och du ser att 2 till
n, ja, blir större mycket snabbare.
Om vi zoomar verkligen ut, en 2 till n algoritm suger absolut.
Jag menar att detta kommer att ta ganska lite tid för
dator att pressa igenom.
>> Men du kommer att se över tid, särskilt med framtida problem uppsättningar och även
slutliga projekt, är din data set blir stor, okej?
Även i den första versionen av Facebook, som antalet vänner, och
Antalet registrerade användare fick stor, Du kan sortera på telefon det i och
genomföra något med linjär sökning, eller en mycket enkel sortering
algoritm, som vi får se i dag.
Du måste börja tänka hårdare och hårdare om dessa problem.
Och vilka typer av problem platser som Facebook och Google, och Microsoft,
och andra arbetar på är exakt dessa typ av stora uppgifter slags frågor
alltmer dessa dagar.
>> Okej.
Så Jennifer framgång i den andra algoritm, ärligt talat, det gjorde hon otroligt
väl första gången, men låt oss skriva det som tur så att vi
kan göra denna punkt.
I det andra fallet, belånade hon en algoritm som upprepas och
igen, men hon tog för givet en vissa antagandet att vi får
henne, men hon utnyttjade viss detalj andra gången att hon inte hade
första gången.
Vilket var vad?
>> Att listan sorterades.
Så snart listan sorterades, vi hävdar att Jennifer kunde göra
fundamentalt bättre.
7 dörrar, ja, är inte så intressant, men antar att det är vi 7 miljoner dörrar.
Log n kommer definitivt att utföra mycket, mycket
snabbare i det långa loppet.
Men hon var tvungen att ha dörrar sorteras för henne.
Nu tog jag mig friheten att göra det i förväg på datorskärmen
här, men antar att Jennifer tvungen att göra det själv?
Antag att dörrarna i fråga representerade data i en databas, eller
vänner registrerats för Facebook, eller alla webbsidor på internet som
olika webbplatser kan behöva att indexera eller sök över.
>> Anta att du bara hade en rådata in och det var kvar till dig, eller till
Jennifer att göra det sortering?
Det, snarare kräver att vi svarar frågan, ja, hur mycket tid
skulle ha tagit Jennifer, eller ens mig, att sortera dessa siffror i förväg så
att hon kunde dra nytta av det?
Rätt?
Eftersom underförstått, naturligtvis, är om det tar mig ett tag att sortera
numren, vem fan bryr sig om att du kan hitta ett antal som 50 så snabbt,
som i Jennifers fall, om vi mer än överväldigade av mängden av tid
det tog genom att sortera saker i förväg?
>> Så låt oss se om vi kan inte måla bilden här.
Jag har en hel *** mer stress bollar, om det hjälper
bryta isen här.
Och om du inte skulle ha något emot, vi behöver sju volontär -
på, OK.
Wow.
Så vi behöver inte spendera på skrivbordslampor, verkar det.
Okej.
Så vad sägs om er två i fronten.
Hur du två killar i ryggen.
Så det är fyra.
Hur om dig framför fem, sex och sju.
Just där.
Din väns pekar ut dig, så du får priset.
>> Okej.
Kom upp.
Och varför inte vi har dig killar Kom hit.
Jag ska ge dig varje ett nummer.
Och gå vidare och ordna er identiskt med vad som är
avbildas på skärmen.
>> [Inplacering VOICES]
>> DAVID J. MALAN: Oop, sorry.
Bug.
Okej.
Nåväl, nu kör vi.
Nummer fem.
Nummer sex.
Ett, två, tre, fyra, fem, sex, sju.
Åh, detta är pinsamt.
>> Högtalare 2: Jag ska bara få ett -.
>> DAVID J. MALAN: Bra deal.
Okej.
Tack för din medverkan.
>> [Applåder]
>> OK.
Okej.
Så vi har fyra, två, sex, en, tre, sju, fem.
Perfekt så vi har sju frivilliga här som är lika i bredd med
array som vi spelar med tidigare.
Och jag valde sju av skäl som kommer att vara precis
bekvämt i en liten bit.
Och jag kommer att föreslå första att vi sortera dessa sju frivilliga.
Om du vill, först, att säga hej men.
Eftersom detta kommer att bli en obekväma flera minuter.
Presentera er själva.
>> GRACE: Hej, jag är Grace.
Jag är en sophomore i Leverett House.
>> Branson: Hej.
Jag Branson.
Jag är en nybörjare i Weld.
>> GABE: Hej.
Jag är Gabe.
Jag är en junior i Cabot.
>> NEIL: Jag är Neil.
Jag är en nybörjare i Matthews.
>> JASON: Jag är Jason.
Jag är en nybörjare i Greenough.
>> MIKE: Jag är Mike.
Jag är en nybörjare i Grays.
>> JESS: Jag är Jess.
Jag är en sophomore i Leverett.
>> DAVID J. MALAN: Excellent.
Okej.
Tja, tack till alla våra volontärer här hittills.
Och utmaningen till hands nu går vara att sortera dessa killar, men sedan
vi kommer att behöva tänka lite hårt om hur effektivt vi faktiskt
sorterade dem.
Så låt oss först försöka detta.
Ni kan se varandras nummer bara genom att placera runt hörnen.
Gå vidare och ta ett par sekunder, och Sortera er från minsta på
vänster till största på höger.
Go.
>> OK.
Bra.
Det var verkligen darn snabbt.
Nu någon här, vad var algoritmen att dessa killar tillämpas?
>> Högtalare 1: Minsta till största.
>> David J. MALAN: OK.
Minst till störst är sortera riktigt av mål, men jag är inte säker på att det är
verkligen en algoritm.
Minst till störst berättar inte mig steg för steg hur man gör.
Yeah?
>> Högtalare 1: [OHÖRBAR]
>> David J. MALAN: OK.
Så om du ser en person som är mindre än ditt nummer, sedan flytta till
höger om dem.
Så att nu börjar bli mer uttrycksfulla, mer som en algoritm, eftersom du
kan säga, om detta, så att.
Så vi har någon form av villkorlig konstruktion.
Och killarna verkade göra att ett fåtal gånger, eftersom vissa av er flyttat lite
av en sträcka.
Så det var förmodligen någon form av looping händer i deras sinnen.
>> Men låt oss försöka formalisera det.
Om ni skulle kunna återställas till detta arrangemang.
Låt oss se om vi inte kan formalisera detta en bit, och sedan ställa frågan, precis
Hur effektiv är detta?
Naturligtvis, när vi gör denna långsammare, det kommer att kännas så bra för
en algoritm, men låt oss se om vi kan sätta våra fingrar på de exakta stegen.
>> Så ni två killar är fyra och två.
Eller du rätt eller fel beslut?
Självklart felaktig.
Så vi bytte.
Nu ska jag gå åt sidan här och säga fyra till sex.
Är du rätt eller fel?
>> GABE: Korrekt.
>> DAVID J. MALAN: Rätt.
Sex och en?
Nope.
Swap.
Så det är två swappar.
Sex och tre?
Nope.
Swap.
Sex och sju?
Ser bra ut.
Sju och fem?
>> JESS: [OHÖRBAR]
>> DAVID J. MALAN: OK, byta.
Och sorteras.
Okej.
Så uppenbarligen inte, eller hur?
Så det var mer på gång.
Men i själva verket, killarna, även bara instinktivt.
hålls rörliga.
De inte bara sluta, när de korrigerat ett problem.
Så.
Sannerligen, jag kommer att ha att göra samma sak.
Jag kommer att behöva sortera om spola tillbaka till början av detta problem,
eller början av denna samling av människor, låt oss börja ringa dem.
>> Och nu vad ska min algoritm på det andra passet vara?
>> Högtalare 1: Samma sak.
>> DAVID J. MALAN: Samma sak.
Och detta, jag börjar gilla, eller hur?
Så snart du kan hitta dig själv att göra samma sak om och om igen, det är
bli mer lika en algoritm, och mindre mänsklig instinkt.
>> Så nu var det dags igen.
Två och fyra?
Nej.
Fyra och en?
Ah, det fanns faktiskt vissa arbete återstår att göra.
För och tre?
Bra.
Fyra och sex?
Sex och fem?
Sex och sju?
OK, nu gjort.
OK, ingen.
Jag måste gå tillbaka.
>> Så nu, återigen, vi gör detta lite mer medvetet.
Och nu finns det bara en hjärna exekvera denna algoritm.
En processor, om du kommer.
Och ärligt talat, det är den enda resursen vi kommer att ha tillgång till.
Och när vi går tillbaka till ett tangentbord och ha något liknande C på vår
omhändertagande, vi skriver bara ett program som kan göra en sak i taget.
För killarna en stund sedan, vi belånade sin kollektiva intelligens
som ni gjorde i veckan noll.
Så låt oss fortsätta att göra detta.
>> Två och en.
Två och tre.
Tre och fyra.
Fyra och fem.
Fem och sex.
Sex och sju.
Klar?
Så jag är, men låt mig spela djävulens advokat.
Gör jag, den typ av dator som bara gjorde ett pass i denna samling av
människor, vet att jag är klar?
>> Högtalare 1: Nej
>> DAVID J. MALAN: Så varför?
Vad skulle jag behöva göra för att slutsatsen beslutsamt att jag gjort?
Förmodligen ett mer pass.
Rätt?
Eftersom allt jag vet från att tidigare pass är att jag korrigerade ett misstag.
Och det innebär, kanske det finns ännu ett misstag
att jag måste rätta till.
Så jag kan bara vara säker genom att spola tillbaka, och sedan kontrollera, 01:59, två och
tre, tre och fyra, fyra och fem, fem och sex, sex och sju.
OK, nu gjorde jag inget arbete.
>> Jag kan säkert ihåg att jag gjorde något arbeta med något som liknar en variabel,
gillar en int.
Kalla det swappar, och om swappar är 0 när jag komma hit, och det började vid 0, då
Jag skulle bara vara dumt att hålla igång fram och tillbaka, kontroll igen, och
igen, och igen, eller hur?
Eftersom du fastnar i något slags oändlig loop.
Så snart som det finns 0 swappar, Vi kan hävda att detta
algoritm är verkligen klar.
>> Nu, låt oss sätta ett namn på det.
Den algoritm som jag föreslår att vi bara genomföras är något som kallas bubbla
sortera, känd som sådan i den meningen att de nummer som är större typ av
bubbla sig upp till toppen, eller upp till slutet av uppsättningen av siffror.
Men hur effektiv var denna algoritm?
Hur många steg hade jag fysiskt Ta till exempel, för att sortera dessa
sju människor?
>> Fyra till fem?
OK, alltför många är ytterst kommer att vara svaret.
Men även då, det specifika numret är inte så intressant.
Låt oss generalisera det som n.
Så om jag hade n folk här uppe, och de var, liksom, i slumpmässig ordning vid
början, i den ursprungliga ordningen.
Nå, hur många steg jag har att ta på första passet?
Det var en, två, tre, fyra, fem, sex, och de är sju personer, så
att sju är, sex -, så det är n minus ett steg första gången.
>> Nu, hur många steg jag har att ta när jag spolas tillbaka?
Tja, skulle vi fördubbla faktiskt att om Vi ville verkligen, men för nu, är jag
bara kommer att säga, okej, en annan n minus 1.
Så n minus 1 kommer att få irriterande att hålla reda på, så låt oss
bara runda upp något.
Så 2n steg.
Så 14 steg, ge eller ta.
>> Hur många gånger har jag tar ett steg nästa gång?
Tja, det är 3n.
egentligen.
Och nu, i värsta fall, för exempel, hur många gånger jag har
gått fram och tillbaka, fram och tillbaka, exekvera denna algoritm, byta
personer på varje pass, ungefär?
Det är faktiskt n kvadrat, rätt?
>> För i värsta fall, du kan typ av tycker om detta intuitivt,
även om det kan ta lite lite tid att sjunka in
I värsta fall, vad skulle dessa sju personer har sett ut, i
termer av arrangemanget av deras nummer?
Helt bakåt, höger?
Och bara för att simulera det, vad var ditt namn igen?
>> MIKE: Mike.
>> DAVID J. MALAN: Mike?
OK, Mike, kan du gå med bara mig över här bara en sekund?
Nej, faktiskt inte.
Ledsen Mike, låt oss spola tillbaka.
Vad är ditt namn igen?
>> NEIL: Neil.
>> DAVID J. MALAN: Neil.
OK, Neil, kommer du med mig, om ni inte har något emot.
Så jag kommer att föreslå, bara för enkelhet, att Neil är nu i hans
värsta möjliga fall.
Men minns hur jag genomfört min algoritm.
Jag jämför, jämföra, jämföra, jämföra, jämföra, oh.
Nu är killarna ute av ordning, så jag fixa.
Så ni byta.
Men tänk nu, hur mycket längre har Neil åka?
Det är ungefär n.
Du vet, det är faktiskt inte n.
Det är som, n minus 1, men jag får irriterad hålla reda på den lilla
nummer, så låt oss bara kalla det n.
>> Så om Neil flyttar ett steg maximalt varje tid, och att flytta Neil ett steg,
Jag måste göra det här riktigt tråkiga pass fram och tillbaka, är detta ungefär
gör detta, n steg, totalt n gånger, eftersom det kommer att ta mig
att många åtgärder för att få Neil alla vägen till där han hör hemma.
Låt bara alla andra om ni var alla mis-beställda också.
>> Så låt oss kalla bubbla sortera n kvadrat.
Gångtiden för denna algoritm, den utförandet av denna algoritm, den
effektiviteten i denna algoritm, vi ska bara beskriva mer
generellt såsom n squared.
Vilket är trevligt, eftersom jag kunde göra det samma exempel med åtta personer, nio
människor, en miljon människor, och det Svaret kommer inte att förändras.
>> Så om ni inte skulle ha något emot, låt oss återställa dig till där du började.
Och låt oss försöka två andra metoder och se om vi inte kan göra grunden
bättre än så här.
Så den här gången kommer jag att föreslå ett slags annan algoritm.
Det var väldigt smart av oss förra gången, och ni var rätt att ha
rätt instinkter bara typ att byta parvis.
Men om jag ville verkligen att närma sig denna enkelt, och mitt mål är att flytta
alla de små siffrorna på detta sätt, och skjuta alla de stora siffrorna som
Förresten, varför inte jag göra just det i mest naivt sätt och se om jag
kan göra bättre än vad som var en ganska komplex algoritm?
>> Så låt oss se.
Fyra är ett ganska litet antal, så jag är kommer att lämna dig där ögonblicket.
Ooh, är nummer två ännu bättre.
Så kan du bara steg framåt för ett ögonblick?
Detta är för närvarande min minsta numrerade kandidat, och jag kommer att minnas
att med vilja, en variabel.
Men jag kommer att hålla kontroll.
Finns det någon vars Antalet är mindre?
Six, nr.
Åh, det är Neil igen.
>> Så jag kommer att skjuta dig tillbaka slags konceptuellt.
Neil kommer att träda fram.
Och nu, den variabel som jag använder till hålla reda på vem som har den minsta
numret uppdateras för att innehålla Neils läge.
Nåväl, låt oss se.
Tre, sju, fem.
OK, vet jag Neil var den minsta.
Vad är det enklaste sak för mig att göra nu?
Jag tänker inte slösa bort min tid genom att bara bubblande Neil en plats till vänster.
Varför inte jag satte bara Neil där han tillhör, vilket naturligtvis var?
>> Hela vägen från början.
Så Neil, kom med mig.
Och vad var ditt namn igen?
>> GRACE: Grace.
>> DAVID J. MALAN: Grace.
OK.
Så Grace, tyvärr, du är typ av i vägen.
Så hur löser vi detta problem?
Rätt?
Om detta är en array, det finns endast sju platser.
Minns att, med Rob, vi talade om förklara åldrar, och vi hade bara en
ändligt antal åldrar?
Samma idé här.
Vi har bara ett ändligt antal ints.
Grace är typ av i vår sätt, så hur vi fixar?
>> Det enklaste sättet är som, Nåd, sorry.
Du kommer att behöva gå över det så vi kan få plats.
Nu, om du tycker om det här, kanske Vi gjorde bara problemet värre.
Och kanske vi gjorde, eftersom det som om Grace var på rätt ställe?
Men vi vet att hon inte, eftersom annars skulle hon ha varit
stående framåt istället för Neil vid denna tid, eller hur?
Vi har redan kollat hennes nummer ut.
>> Okej.
Så nu är Neil på rätt plats, och Jag kan göra en liten optimering.
För nästa minut, jag kommer att ignorera Neil alla tillsammans, för att inte
slösa sin tid, eller oavsiktligt byta honom till fel ställe.
Så nu, hur jag hitta nästa element som är minsta?
Två.
Det är ett ganska bra antal, om du vill kliva fram och
Jag kommer ihåg dig.
Sex, inte bra.
Fyra, tre, sju, fem, inte bra.
Så låt mig flytta dig till din rätt ställe.
Och vi hade bara tur den här gången.
>> Nu kommer jag att ignorera dessa två killar, och nu gör något mer
passera genom denna.
Sex, att ett ganska litet antal.
Kom fram.
Åh, förlåt.
Graces nummer är bättre, så trampa på framåt.
Fyra.
Tyvärr, Grace.
Gå tillbaka igen.
Nummer tre är bättre.
Seven.
Fem.
Och nu vad heter du nu igen?
>> JASON: Jason.
>> DAVID J. MALAN: Jason.
Så Jason är nu den minsta inslag som jag har valt.
Vart ska han gå?
Så där sex är.
Och ditt namn är nytt?
>> GABE: Gabe.
>> DAVID J. MALAN: Gabe.
Gabe är i vägen.
Vad är det lättaste att göra?
Byt dessa två killar och fortsätta.
Så nu ska vi se.
Vem är den minsta?
Fyra.
Låt mig bara typ av fusk.
Fem kommer att bli det minsta.
Jag hittar nästa, om du vill öka framåt, vad jag har att göra med
dessa killar, med Gabe?
Swap igen.
Så nu, fortfarande något i ordning.
Jag hittade Gabe vara den minsta, så Jag hoppar ut honom, flyttar er över.
Och gjort.
>> Så svaret är detsamma.
Slutresultatet är detsamma.
Vilken av dessa två algoritmer är bättre?
Den andra, hörde jag.
Varför?
>> SPEAKER 3: Det n steg [OHÖRBAR].
>> DAVID J. MALAN: Det är n steg som mest.
Intressant.
Så är det dock?
Så hur har jag hitta den minsta elementet?
Hur många steg jag måste ta den finner det minsta elementet?
Jag hade en ser hela vägen i slutet, eller hur?
För i det värsta fallet, vilken Om Neil var här?
Så bara hitta det minsta elementet tar mig n steg, eller n minus 1.
Men, OK.
Så fixa Neil.
Kom ihåg att, en minut eller så sedan.
>> Men hur gjorde jag hitta nästa minsta elementet?
Det är n minus 1, eller n minus 2 riktigt, från antalet steg.
Så OK.
Så jag gjorde N minus 2.
Okej.
Så det känns lite bättre.
Okej.
Hur många steg nästa gång hitta nummer tre?
Så n minus 4.
Så det minskar, ett färre steg på varje iteration.
Så det här känns bättre, eller hur?
Om förra gången det var ungefär n gånger n, denna gång är det N minus 1, plus N minus
2, plus n minus 3, plus n minus 4, punkt, punkt, punkt.
Men om du minns från din high school läroböcker, den lilla fuska
plåt på baksidan som har formler, om du lägger upp denna serie av siffror,
vad som är det totala antalet steg kommer att vara att jag tar här?
>> Detta är en av dem, gillar, n minus 1, gånger n, delat med 2.
Så låt mig se om jag kan dra upp detta för bara ett ögonblick.
Och återigen, jag slags avrundning vissa siffror bara för att hålla våra liv enkla,
men som jag minns det, det är något som om Jag gör n minus ett ting, då n minus
2, sedan N minus 3, är det ungefär något sådant över 2, och om jag
multiplicera detta ut, det är faktiskt n kvadrat.
Det är inte mår så bra. n minus n över 2.
>> Men här är en sak.
I datavetenskap, när problemen börjar bli intressant är när n
blir riktigt stor.
Och när n blir riktigt stor, vilket av dessa värden kommer att dominera alla
av de andra?
Det är typ av n kvadrat, rätt?
Ja, dividera med 2 är ganska bra.
Men om du pratar om miljarder bitar av data, eller biljoner
bitar av data, ok, så du är dubbelt så snabbt.
Men vem bryr sig egentligen om det stora antal, Om denna faktor är vad som får
större och större.
Och säkert är det mer av en skillnad än den här killen.
Så även om ni har rätt, det andra algoritmen, vi kallar det
selection sort, är, i den verkliga världen, en lite snabbare potentiellt, eftersom jag är
tar färre och färre steg varje gång.
>> Det är egentligen inte i grunden snabbare.
För om vi spelar faktiskt detta för stora värden på N, vid slutet av
dagen, för tillräckligt stora n, det är fortfarande kommer att kännas ganska långsam.
Nåväl, låt mig ta ett sista passet på det.
Det är vad jag skulle kalla selection sort.
Kan ni återställa er en sista gång?
Och i det senare fallet, jag kommer att föreslå något
kallas insättning sort.
Insertion sort är, konceptuellt, lite annorlunda.
>> Hellre än att gå fram och tillbaka och välja det minsta elementet, jag
bara kommer att ta itu med vart och ett av dessa killar som jag möter dem, och sätt
dem i deras rätta plats.
Så jag ska bara börja med Grace, och jag ser att hon är nummer fyra.
Var hör nummer fyra?
Jag har inte börjat sortera någonting, så Grace får stanna där.
Och nu ska jag hävda, om du kunde ta ett steg till höger, här
min sorterad lista, detta är mitt osorterad återstående lista.
Så nu ska jag gå nästa, och vad heter du nu igen?
>> Branson: Branson.
>> DAVID J. MALAN: Branson.
Så Branson är nummer två.
Så jag kommer att ta dig ut för ett ögonblick.
Och nu, där du hör hemma i denna samling?
Så till höger om nåd.
Så återigen, vi slags göra Grace gör en hel del arbete här.
Var placerar vi dig?
Så vi kommer att glida dig till vänster, och sätt Branson där.
Men nu har jag hävdar att ni är klar.
Men varsel, jag använder inte extra utrymme.
Det är fortfarande två element här, 5 hit.
Total array storlek är 7, så jag är inte fusk, okej?
>> Så nu har vi, med Gabe här, nummer sex, där du hör hemma?
Du hade tur igen.
Så du får bo där.
Bara ta en liten steg åt höger bara för att klargöra att du är sorterad.
Och nu har vi Neil igen, antal en, var ska du gå?
Och nu är där vi börjar se att denna algoritm, men den första
anblicken känns ganska smart, titta vad är på väg att hända.
Om du kunde kliva fram.
>> Var vill vi sätta Neil?
Så uppenbarligen här, så hur får vi Neil dit?
Låt oss göra detta steg-för-steg.
Gabe, där behöver du gå?
Japp, så ta ett stort steg, eller två halva steg för att göra
ett steg över det.
Grace, där du går?
Bra.
Så ännu ett steg.
Och slutligen, Branson?
Ett annat steg.
Och nu kan vi sätta Neil på plats.
>> Så nu, fortsätter denna logik.
Även om vi inte är skiftande Neil över och över och över, för att sätta honom
där han går, i värsta fall, den nästa nummer vi kan stöta kunde
vara antalet, säg, det fanns ett antal noll, då vi kommer att flytta alla
dessa killar.
Antag att det finns ett antal, negativ en, då måste vi flytta
alla dessa killar.
Så vi är egentligen bara typ av vändning problemet runt, så att vi är
överföra kostnader från den urvalsprocess så införingen
process, så att ni bara hade att flytta ungefär n minus något
antal steg.
Och att antalet steg kommer bara att öka när jag väljer fler nummer,
om jag måste hålla prejar er tillbaka, och tillbaka, och tillbaka.
>> Så det tråkiga är nu alla dessa algoritmer är n kvadrat.
Låt oss gå vidare och tack vare dessa killar, och visualisera dessa lite
annorlunda.
Mycket bra gjort.
>> [Applåder]
>> Okej.
Där du går.
Tack för -
>> Branson: [OHÖRBAR] hålla tal.
>> DAVID J. MALAN: Nej, du får hålla tal också.
Okej.
Snyggt gjort.
Okej.
Så låt oss se om vi inte kan nu sammanfatta snabbare, och mer visuellt,
exakt vad som hände Här följer.
Jag kommer att gå vidare och dra upp Firefox.
Vi ska länka denna demonstration på kursens hemsida.
Java är lite irriterande att få arbeta i vissa webbläsare dessa dagar.
Så om du vill spela med det här hemma, inser du kanske behöver använda Firefox
att få det att fungera.
Och vad jag ska göra med detta Demonstrationen är följande.
>> Längst ner, har jag en hel drös med menyalternativ, inklusive en start och en
stopp-knappen.
Också, som en parentes, det verkar vara en bugg i dessa program, där du
kan faktiskt inte se starten eller stoppa knappen om du inte håller Kommando eller Alt
plus och zooma in, vilket märkligt visar fler knappar.
Så bara FYI om du spelar med detta hemma.
Nu ska jag klicka på Start på bara ett ögonblick, efter att ha angett en fördröjning,
gillar, 200 millisekunder här, precis så att vi kan se vad som händer.
>> Så jag hävdar att detta är en visualisering av den första algoritmen
killarna gjorde, bubbla sortera, varigenom vi bytte folk parvisa.
Den viktigaste insikten att denna visualisering är att höjden av staplarna
representerar storleken på talet.
Så högre stapel, desto Ju högre siffra.
Kortare baren, lägre tal.
Och om du märker, vi går igenom den första variant av denna algoritm,
byta stora och små siffror, så att det lilla antalet kommer först och
det stora numret går till höger.
>> Och så fort vi får i slutet av arrayen av många fler siffror än sju, vi
kommer att gå tillbaka till början.
Och förutse detta.
Längst till vänster, är den lilla killen går att byta åt sidan, och detta
processen upprepas.
Nu denna visualisering blir snabbt tråkigt, så låt mig gå vidare och sluta
det, ändra fördröjningen något mycket snabbare bara för att få nu, en känsla för
denna algoritm.
>> Så även om jag har sped upp det, är detta som att uppgradera min processor, köpa
en ny dator.
Jag har inte i grunden förändrat mitt algoritm, men du kan faktiskt se mer
tydligare än med människor, att den stora siffror bubblar upp till toppen,
och de små siffrorna bubblar ner till botten.
Och nu denna sak sorteras här.
Och i förbigående, på torgen, det finns bara några bokföring där till
hjälpa dig att räkna hur många jämförelser, eller hur många swappar har
faktiskt gjorts.
>> Nåväl, låt oss prova en av de andra vi såg.
Låt mig klicka på bubblan sort här, och låt mig välja, och hela denna webbsida
är en liten buggy.
Låt oss acceptera risken och köra den igen.
Där vi går.
Så låt oss göra urvalet sortera.
Jag vet inte varför menyn visas där borta.
Låt oss zooma in för att fixa det bugg, ändra detta till 50.
Ah, låt oss faktiskt göra som mycket snabbare.
Fem millisekunder eller så, och Start.
>> Så detta är valet sort.
Så återigen, tänka på vad vi gjorde med människorna här uppe.
Vi gick igenom arrayen och valda det minsta elementet igen,
och igen, och igen.
Nu hävdar jag att var fortfarande ganska dåligt.
Det var fortfarande n kvadrat, ge eller ta, men det var, i den verkliga världen, lite
snabbare, eftersom jag verkligen tar något färre steg varje gång.
Men vi talar bara vad?
Kanske 40 eller så stänger här?
Vi pratar inte 40 miljoner.
Så det är inte klart helt för mig att var verkligen en betydande vinst.
>> Låt mig nu gå tillbaka och ändra till vårt tredje algoritm, som väljer
insättning sort.
Och nu är det verkligen buggig eftersom Menyn egentligen inte borde vara där nere.
Så nu ska vi rulla tillbaka upp hit och starta denna algoritm.
Whoop, starta och stoppa.
Så här en typ av har en ganska mönster till det, vilket vi återigen
sätter människorna, eller i detta fall, barerna i
deras lämplig plats.
Och det är redan gjort innan Jag vände mig om.
Men här också, i teorin, fortfarande n kvadrat.
>> Så låt oss se om vi inte kan sammanfatta dessa enligt följande.
Jag ska gå vidare och bara för att ge oss slags ett gemensamt sätt att tala
om dessa saker, låt mig presentera bara en bit av notation här.
Du är på väg att se något som kallas big O, eftersom det är bokstavligen en stor
O. Och detta är ett sätt att en dator vetenskapsman eller en matematiker ens använder
att beskriva den gångtid av någon algoritm.
Hur många steg tar det egentligen?
>> Nu ska jag skämma ut mig med min handstil här på bara ett ögonblick.
Men låt mig gå vidare och säga att detta kommer att bli stort O hit.
Och låt mig presentera en annan symbol, en huvudstad omega.
Omega kommer att vara det motsatta, huvudsak av stora O. big O
medel, i värsta fall, hur mycket tid kanske någon algoritm tar, i
termer av n, omega tillfalla vara hur mycket tid kan det ge
tar i bästa fall.
Och vi får se vad vi menar med bästa fall på bara ett ögonblick.
>> Så låt oss börja något enkelt.
Låt mig börja med en linjär sökning.
Så inte sortering.
Vi kallar denna linjär sökning.
Och nu, gör lite bord ur detta.
Och nu, i fallet med linjär sökning, i värsta fall, hur många steg är
det kommer att ta mig för att hitta en antal godtyckliga val?
Och det finns n totala dörrar eller n totala antalet.
Worst case.
Hur många steg kommer jag att behöva vidta för att hitta numret 50 i en array
av n dörrar?
Och varför?
Eftersom det kan vara allt sätt över på änden.
Så mycket som Jennifer mötte, den nummer 50 var hela vägen över, så i
värsta fall linjär sökning är stort O n, ska vi säga.
>> Hur är det bästa fallet, om du får verkligen lycklig?
Det kommer bara att ta ett steg, eller ett konstant antal steg.
Så vi ska beskriva det som 1.
Så detta är ganska bra.
Nu tänk om vi gjorde något gillar binär sökning?
Så binär sökning, i värsta fall, tog hur mycket tid?
>> [Inplacering VOICES]
>> DAVID J. MALAN: Så egentligen, jag hörde det på ett par ställen.
Så det logg faktiskt n, ge eller ta, för som vi delar upp listan i hälften
igen, och igen, och igen, vi kan att hitta, slutligen, värde,
om det är det, men det finns en hake.
Vad är antagandet att vi måste tar för givet för binär sökning?
Det måste sorteras.
Det är inte sorterats, kan du dela upp saken i hälften och om igen, och du
kan gå till vänster, och du kan gå rätt, och du kan gå till vänster och höger, men du är
kommer inte att hitta elementet om listan inte är sorterad, eftersom
du kanske missar det.
Eftersom din heuristik, för att gå åt vänster eller höger kommer att vara bristfällig, om det är
faktiskt inte sorteras.
Så det finns en slags dold kostnad till med något sånt här.
>> Nu, låt oss gå in i vår sortering algoritmer söker inte -
Åh, faktiskt Låt oss gå i detta ämne.
Binary sökning i bästa fall?
Det är också en om det bara råkar vara i den mycket mitten av arrayen, eller
mitt i telefonboken.
Nu ska vi göra bubble sort.
Så återigen, nu vi in i sorterar, inte de söker.
>> I värsta fall, hur många steg vi fordran bubbla sortera kommer att ta?
n kvadrat.
Så jag kommer att dra det.
Ooh, ser min handstil ännu värre när det är beräknat att stora.
Okej.
Så det är n kvadrat.
Och i bästa fall av bubbla sortera, hur många steg kommer det att ta?
1, hörde jag.
>> SPEAKER 1: n.
>> DAVID J. MALAN: n, hörde jag.
>> TALARE 1: 2.
>> DAVID J. MALAN: 2, hörde jag.
Hör jag 3?
Okej.
Så jag har hört en, n, 2, men låt oss plocka isär åtminstone den första av dessa
förslag, 1.
Det är inte en dålig instinkt, eftersom det slags följer ett mönster här.
Men om det tar bara 1 steg, hur i världen kunde jag hävda att listan
sorteras, för om jag bara får att ta ett steg, hur många element
kunde jag kolla faktiskt att vara säker?
Tja, bara 1, vilket innebär att det finns n minus ett element som kan vara av
ordning, och jag tänker bara på tron efter tittar på en faktor som
sak sorteras.
Så 1 är inte korrekt här.
Så minimalt, hur många har jag att titta på?
>> [Inplacering VOICES]
>> DAVID J. MALAN: n minus 1, eller egentligen, n, eftersom jag måste titta på varje
inslag för att säkerställa att det är inte i ordning.
Men återigen, vi sorterar av vågen vår händerna på de mindre siffror och
anta att, såsom n blir stora, de är ointressant ändå.
Så det är bubbla sortera.
Och nu, låt oss göra de två sistnämnda.
Urval sortera, och sedan kommer vi göra insättning sort.
Och då kommer vi att blåsa ditt sinnen med något mycket
bättre än alla dessa.
Okej.
>> Vad är det värsta fallet kör tidpunkten för valet sort?
>> Högtalare 4: n kvadrat.
>> DAVID J. MALAN: n square, jag hör.
Men varför n kvadrat, intuitivt?
>> Högtalare 4: Eftersom vi bara gjorde det.
>> DAVID J. MALAN: Eftersom vi bara gjorde det.
OK.
Bra svar.
Men intuitivt, varför är urvalet sortera n kvadrat?
Vad hade vi att göra om och om igen?
Vi var tvungna att hålla skanna igenom, är dig det minsta, du är den
minsta, är du det minsta.
Och beviljats, kunde vi ta n steg, då n minus 1, och sedan n minus 2.
Men om du sorts lägga dem alla upp, eller ta det på tro att jag har lagt
upp dem i förväg, får vi ungefär n kvadrat minus några mindre tal.
Så jag kommer att kalla denna n kvadrat.
Men med val Sortera på bästa fall, hur många steg är det
kommer att ta mig?
>> SPEAKER 5: [OHÖRBAR]
>> DAVID J. MALAN: Det är tyvärr fortfarande n kvadrat, rätt?
För om jag väljer det minsta element, och vi hade sju personer här,
Jag bara vet, när jag får till mycket Därför att jag har hittat den minsta
nummer, oavsett var han eller Hon kan ha varit.
Men hur hittar jag nästa minsta antal?
Jag måste göra ett annat pass.
Så i bästa fall, vad är det ingång till val Sortera?
Det är en redan Sortera listan, nummer ett, nummer två, nummer tre, nummer fyra.
Men jag är en dator.
Jag kan bara titta på en sak i taget.
Jag kan inte sortera om att ta ett steg tillbaka som en människa och säga,
ooh, ser detta korrekt.
>> Jag kan bara döma riktighet i urvalet sortera genom att välja
minsta antalet.
Men även om jag hittar nummer ett första, om jag inte vet något annat om
de andra numren, vilket jag inte gör, allt jag vet att jag har gått i arv en array
eller en uppsättning av dörrar som är bak siffror, det enda sättet jag vet att en
var det minsta?
Om jag får hela vägen här och inser, fan, var en verkligen de minsta.
>> Men hur avgör jag då att två är den näst minsta?
Genom att göra samma ineffektivitet igen och igen.
Så slutligen, med införande sortera, hur, i värsta fall,
vi säger att det fungerar?
Det är för n kvadrat.
Och hur är den bästa fall?
Vi lämnar det som en cliffhanger.
Vi ska fylla i den tomma nästa gång, men låt mig först föreslå att vi
fundamentalt bättre än alla dessa, okej?
>> Så tänk själv vad insättning Sortera kommer att bli.
Tja, var det inte mycket dramatisk, eftersom jag är den enda
som såg förändringen.
Wow.
OK.
Så här har vi en något annan demonstration.
Om jag zooma in här, ser du att på vänster har vi bubbla sortera, i
mitten har vi urvalet sortera och på längst till höger, har vi något vi
har inte tittat på ännu kallas samman sort.
Men fundera över vad vi har varit gör här hittills idag.
När Jennifer först kom upp på scenen, Vi gick igenom matris med tal
igen, och igen, med linjär sökning, och vi fick linjär gångtid, big O
på n, så att säga.
>> När vi betraktar nu den första veckan i klass, när vi hade söndra och härska,
och vi hade telefonboken riva, och Jennifer, och vi kollektivt
belånade att viktiga insikter, som var att upprepa dig om och om igen genom
på något sätt kasta bort, kasta bort, kasta bort, hälften av problemet, eller
allmänhet, dividera ett problem i halv, och sedan behandling av mindre bit av
problemet som begreppsmässigt likvärdiga till den andra, gjorde vi på något sätt
fundamentalt bättre.
Men med bubbla sortera, med val Sortera, med införande sortera, vi har kanske
inga sådana insikter som Jennifer gjorde.
Vi ganska mycket bara gick tillbaka och fram en hel *** gånger, och vi
tweaked saker lite, byta i denna ordning, kanske
infoga eller markera.
Men i slutet av dagen, gjorde jag en hel del av obekväma promenader fram och tillbaka.
Vi gjorde inte riktigt utnyttja något smarta som Jennifer tyckte att dividera
och erövra.
>> Så sammanfoga sortera, däremot, som vi kommer inte se förrän nästa vecka, det kommer
att utnyttja denna nyckel idé genom att dividera ingången, och sedan halvera, och sedan
halvera, och sedan halvera.
Och på varje iteration av denna slinga, sortera den vänstra halvan, och den högra
hälften, sedan den vänstra halvan av vänstra halvan, och den högra halvan av den vänstra, sedan
den vänstra halvan av den högra halvan, och den högra halvan av den högra halvan.
Och upprepa igen och igen.
>> Så du ser det här visuellt, men detta är vad som väntar oss nästa vecka.
Och i allmänhet, när vi tänker lite lite hårdare på sådana problem.
Vi har n kvadrat till vänster, n kvadrat i mitten, och n
log n till höger.
Så det är ditt riktiga cliffhanger.
Vi ses på måndag.
>> [Applåder]