>> Speak: Okej, det här är CS50.
Detta är slutet av vecka tre, och om du inte har utnyttjat redan,
vet att det kommer att finnas lunch denna fredag ​​som vanligt, där
du kan njuta av bra samtal och mat på Fire and Ice
med några av CS50: s personal och klasskamrater.
Chef till denna URL här.
>> Nu kanske du minns, eller du kan snart vara bekant med,
dessa saker här, vilket ges ut i slutet
av terminen för många klasser.
Så kallade examen blå böcker, där du skriver dina svar på tentor.
Nu har jag här 26 sådana blå böcker, på var och en av dem
är skrivet ett namn, A till Z. Och ja namnen är så enkelt, A
genom Z. Och en av målen till hands idag
kommer att vara att fortsätta det Vi började på måndagen, vilket inte är
så mycket att titta på koden, men egentligen tittar på idéer och problemlösning.
Ett av de mål och löften om kursen
är att lära dig att tänka mer noggrant, mer metodiskt,
och att lösa problem på ett effektivare sätt.
Och faktiskt, kan vi göra det riktigt utan att ens röra en rad kod.
Så jag har ett par elefanter upp här i dag, orange och blått,
om vi kunde få en volontär, kanske från längre tillbaka än vanligt.
Vad sägs om just där, kom ner.
Målet, som kommer att vara till hjälpa plus administrera denna examen här.
Vad heter du?
>> PUBLIK: Mary Beth.
Speak: Mary Beth, kom upp.
Låt mig få mikrofonen här för dig.
Trevligt att träffas.
>> PUBLIK: Trevligt att träffas.
Speak: Okej, så jag har Här blå böcker A till Z,
och jag ska låtsas att Jag har en av studenterna,
och de kommer i något slumpmässigt vid slutet av en tre timmars tenta blocket,
så de hamna i några semi-slumpmässig ordning så här.
Nu ditt jobb på bara ett ögonblick går att vara-- detta är faktiskt hur de får
slås in vid slutet av klassen, mest troligt.
Ditt jobb nu kommer att bli helt enkelt att sortera dessa blå böcker för oss
från A till Z.
>> PUBLIK: Åh, det här är kommer att ta evigheter.
>> Speak: Och vi kommer att titta på när du gör detta, inget tryck.
PUBLIK: Nej, ingen press eller något.
>> Speak: Och för skojs skull, låt oss sätta upp en timer.
>> PUBLIK: Så mycket roligt, så roligt.
>> Speak: Jag kan hålla mikrofonen för dig.
Okej, vi har just fördubblat hastigheten.
Så under tiden, låt mig ställa vad som är kommer att bli frågan om Mary Beth
är vad gör hon, hur är Hon går om att lösa det här?
Och faktiskt, kanske du inte har någonsin tänkt på något
så enkelt som när du plockar upp 26 böcker som denna,
som har en naturlig beställa dem.
Hur ser processen att du faktiskt använder?
Är det ganska slumpmässigt bara plocka den första du ser
och sätta det på sin plats?
Brukar du först flytta dina händer runt Letar du efter en sedan letar efter B?
Brukar du titta på en par av dem sida vid sida
och bara säga, vänta lite, det här är inte rätt, och sedan byta ordern?
Vi såg redan på måndag att det finns ett antal olika sätt
där vi kan göra detta, och ja som vi i slutet här,
Jag skulle notera kanske vad Mary Beth gör.
Vi har några högar det verkar, en större en, tre mindre.
>> PUBLIK: Jag beställer dem när jag hittar två bokstäver
som jag vet är tillsammans i en sekvens, Jag satte ihop dem så att jag inte
oroa dig hålla spår av en hel rad av böcker.
Det är bara, åh, A är först, Jag har en bunt här.
Speak: Så, nästan som en pusselbitar som
har rätt form för att stämmer med varandra.
PUBLIK: Ganska mycket, ja.
Speak: OK, utmärkt.
Och nu var och en av dessa pålar är förmodligen sorteras?
>> PUBLIKEN: Ja.
>> Speak: Okej, A till Z. Alla höger, grattis, du gjorde det.
Du har ditt val.
Blue?
Okej, tack för det.
Så Mary Beth gjorde föreslå vad hennes inställning var,
men vad är en annan metod hur man skulle gå att sortera dessa saker?
Vad skulle du ha gjort?
Rekordet att slå skulle ha varit en minut och 50-tal sekunder
plus de som jag glömde att räkna.
Vad skulle du ha gjort?
Yeah?
PUBLIK: Ta stapeln.
Börja från början.
Kontrollera dina papper.
Och om den översta en är högre än, kanske, de är,
botten en är högre, sedan byta dem.
>> Speak: OK, så börjar vid toppen och botten,
och sedan arbeta dig inåt så där, byta dem?
OK, så lite liknande i anden att bubbla sortera,
men att välja ytterlighet inte de närliggande par.
Men den korta av det är att det finns säkert en massa olika sätt
vi kan göra detta, och ärligt talat, jag tror att du typ av
antagit ett par metoder, eller hur?
Du gjorde sorts fyra sorterade högar, och sedan effektivt slås ihop dem.
Och det är, förmodar, en annan tekniken helt och hållet.
Du har inte behandla det som en stor hög, du indelade problemet i fyra brigader,
om du vill, och sedan på något sätt fusione dem i slutet.
>> Så låt oss betrakta, i slutändan, hur annat vi kan göra det här.
Vi formalise begreppet bubbla sortera förra gången,
och bubbelsorterings minns var en algoritm som vi visualiserade
med åtta av dina klasskamrater här uppe, till synes slumpmässigt sorteras först.
Och vi beslutade sedan parvis, om två element är ur funktion,
helt enkelt byta dem.
Så fyra och två är uppenbarligen ur funktion,
så dessa två klasskamrater bytte positioner.
Och så upprepade vi med fyra och sex, sedan sex och åtta, på varje iteration,
rör sig åt höger.
>> Så med tanke på åtta personer, hur många parvisa jämförelser gjorde jag när hon gick från
vänster till höger i en sådan iteration?
Hur många jämförelser?
Sju, eller hur?
För om det finns åtta människor, men du har paret
dem och du rör ett hopp till höger,
du kommer inte att ha åtta jämförelser eftersom du kan inte jämföra
ett element mot sig själv, eller det skulle bara vara meningslöst, så du har sju.
, Eller mer generellt, om Vi har n personer, vi
gör n minus ett jämförelser med bubbel slag.
>> Så låt oss tänka nu hur bra eller dålig bubbla sortera faktiskt var, och försök
att ge oss själva ordförråd med vilket till kritik algoritmer som denna,
och snart våra egna.
Så den första passera genom bubbla sortera, första gången
Jag gick från vänster till höger över skede, tog mig n minus ett jämförelser.
Och det kommer att bli min måttenhet, eller hur?
Jag var typ av prat och promenader, något snabbt, något långsam,
så räknar jag antalet sekunder är inte särskilt träffande,
men räkna antalet verksamheter som jag gjorde i måndags,
jämföra två personer, anser att som en trevlig måttenhet.
>> Så n minus 1 steg första gången men vad hände efter det?
Vad är det upp av ett pass genom en i övrigt osorterad lista?
Vad kan du berätta om elementet som var hela vägen dit?
Yeah?
Det var den största elementet, eller hur?
Nummer åtta, även om hon började här, varje gång jag
jämfört henne mot en granne, höll hon
bubblar upp till höger sidan av listan.
Och faktiskt, det är där algoritmen har fått sitt namn.
>> Nu med den logiken, hur många jämförelser behöver jag göra på andra gången
Jag gör det passning från vänster till höger?
n minus 2, eller hur?
Det skulle bara vara slöseri med min tid om jag hålla jämföra åtta mot någon
annat eftersom vi redan vet hon var på rätt plats.
Så det är lite av en optimering, så nästa pass
kommer att bli plus n minus två steg, där n är antalet personer.
Nu kan du typ av extrapolera, och med om du inte är en datorforskare,
hur detta slutar.
Vid slutet av denna algoritm, förmodligen du har bara en jämförelse kvar.
Du måste slags fixera början av listan i fall två
och en är i ordning och bör vara ett och två,
så denna bottnar på plus en slutlig jämförelse.
>> Nu pricken, kort, kort sorts vågor är det händerna på några av de saftigare detaljer,
men låt oss bara gå vidare och förenkla.
Om ni minns från hög skola, ärligt talat, en hel del av er
hade matteböcker som hade en liten fusklapp
på framsidan eller bakstycket som visade dig
vilken serie summationer som detta i slutändan läggas till.
I det allmänna fallet, om du har en variabel som n, och faktiskt den här,
om du tittat på ditt old school matte bok,
skulle du se att det faktiskt lägger upp till denna summa här,
n gånger n minus 1 alla delat med 2.
Så nu vill jag bara föreskriva detta är sant, så på ett språng i tro,
det är vad det här summerar upp till, och vi kunde
bevisa att på ett mer allmänt fall.
Men nu ska vi utöka denna.
Så låt oss multiplicera denna, så det är n kvadrat, minus n, allt delat med 2.
Det är verkligen n kvadrat, delat med 2, minus n över 2,
så det är allt trevligt och intressant.
Men vad händer om vi nu plug-in ett värde?
Anta att jag inte hade åtta människor, men säger en miljon.
Och en miljon bara för att det är ett ganska stort antal,
Låt oss koppla den in och se vad som händer.
Så om jag ansluter en miljon in i den formel Jag kommer att få en miljon kvadrat,
delat med 2, minus en miljoner delat med 2.
Nu vad som kommer att vara lika?
Så 500 miljarder, minus 500.000.
Och om jag faktiskt gör att matte ut, innebär att
att sortera en miljon människor med bubbelsorterings
kan ta mig 499.999.500.000 steg eller jämförelser i slutet,
vi bara extrapolera.
>> Det känns ganska långsam, men uppriktigt sagt mätning av en viss ingång
så här, är inte så talande.
Men ja det antyder att så n blir större och större, denna algoritm
slags känns värre och värre, eller om du verkligen
börjar känna smärtan av att exponentiering, att n kvadrat,
vilket ger upp ganska snabbt.
Och denna detalj är inte förlorat på människor, faktiskt
för några år sedan en viss senator som var kampanjarbete, satte sig ner för en intervju
med Googles Eric Schmidt, CEO på tiden,
och utmanades med en fråga ungefär som vi utforskar i dag.
Låt oss ta en titt.
>> [VIDEOAVSPELNING]
>> -Senator, Du är här på Google, och jag gillar
att tänka på ordförandeskapet som en anställningsintervju.
Nu är det svårt att få ett jobb som president,
och du går igenom stelhet nu.
Det är också svårt att få jobb på Google.
Vi har frågor, och vi fråga våra kandidater frågor,
och den här är från Larry Schwimmer.
Vad-- ni tror att jag är skojar, det är just här.
Vad är det mest effektiva sättet att sortera en miljon 32-bitars heltal?
>> -Well--
>> Jag är ledsen, maybe--
>> Nej, nej, nej.
Jag tror att bubblan sorterings skulle vara fel väg att gå.
>> Kom igen, som berättade det här?
Jag såg inte datorn vetenskap i din bakgrund.
>> -Vi Fick våra spioner där.
>> -OK, Låt oss be en annan intervju fråga.
>> [END VIDEOAVSPELNING]
>> Speak: Så talar om specifika siffror dock,
kommer inte att vara så användbart.
Det är inte ett liv lektion som bubblan sortera, givet en miljon ingångar,
kan ta så många som 500 miljarder steg.
Du kan inte riktigt generalisera alltför effektivt från att
och göra bra designbeslut när man skriver program.
Så låt oss fokusera även på hur vi kan förenkla detta resultat.
>> Så jag har gulmarkerat här resultatet av n kvadrat dividerat med 2,
så en miljon kvadrat dividerad med två, och sedan
Jag har markerat vad det ultimata svaret var
när vi dras bort n delat med 2.
Och påståendet jag ska göra nu är, vem fan bryr sig om du subtraherar bort
lite gamla n över 2 när den första del av denna formel är så mycket större?
Den dominerar den andra sikt n kvadrat delat med 2
är så mycket större, uppenbarligen, såsom n blir stor som en miljon,
det är det verkligen en stor skillnad på slutet av dagen mellan 500.000.000.000
och 499.999.500.000?
Inte riktigt.
Och så vad vi ska gör som datavetare är
ignorera dessa lägre ordningens termer och ta något som detta och verkligen
bara förenkla det till term som kommer spela någon roll.
De större våra datamängder blir, desto större våra databaser får, desto fler webbsidor
Vi måste söka, desto mer vänner du har på Facebook.
>> Som n blir större, vi är verkligen kommer att bry sig om den största
termen i någon sådan analys av våra algoritmer prestanda.
Och jag ska säga, vet du vad, bubbla slag är i storleksordningen big O,
i storleksordningen n kvadrat.
Det är inte precis n kvadrat som vi har sett,
men vem bryr sig egentligen om de mindre termer,
och ärligt talat, som verkligen bryr sig om vi delar med 2?
Det är bara en konstant faktor.
Och är 500 miljarder jämfört med 250 miljard verkligen så stor grej?
Jag kunde bara vänta ett år, Låt min laptop bokstav
få dubbelt så snabbt i hårdvara, och den typen av skillnad
bara försvinner naturligt med tiden.
>> Det vi bryr oss om är uttrycket, den del
av uttrycket som kommer att variera som vår ingång blir större och större.
Och mycket riktigt, i den verkliga världen, det är vad som händer mer och mer
är ingångarna till våra problem och algoritmer blir större.
Så stor o kommer att bli notationen, den asymptotiska notation, att vi bara
använda som datavetare för att beskriva prestanda eller gångtid,
av en algoritm.
Så att vi kan jämföra algoritmer på olika datorer skriftliga
av olika personer, med hjälp av några i grunden liknande metrisk
liksom antalet jämförelser du gör, eller kanske det antal swappar
du gör.
>> Vad vi ska inte räkningen är den tid
som passerar på klockan på väggen normalt.
Vad vi ska inte oroa sig om är hur mycket minne
du använder idag på Minst, men det är
en annan resurs som vi kan mäta.
Vi ska försöka att basera våra analyser om bara de grundläggande funktionerna, de som,
ärligt talat, att du kan se mest visuellt.
Så med något i stil med stort O n kvadrat, jag hävdar att O n kvadrat
är en övre gräns för den så kallade gångtid bubbla slag.
Med andra ord, om du ville påstå att det finns
denna övre gräns för hur många steg en algoritm kan ta,
det kommer att vara i den stora O n kvadrat i detta fall, en övre gräns.
>> Vad händer om jag ändrar i stället för historia att vara inte om bubbla sortera,
men om denna övre gräns.
Kan du komma på en algoritm att vi har tittat på redan
vars övre gräns, maximalt mäta tid eller verksamhet,
skulle sägas vara begränsad av n, en linjär funktion,
inte en kvadratisk en som är böjd?
Vad är en algoritm som alltid tar inte mer
än som n steg, eller 2n steg, eller 3n steg?
Yeah?
>> PUBLIK: Att hitta största antalet i en lista?
>> Speak: Perfect, hitta det största värdet i en lista.
Om jag får en lista över människor till exempel,
var och av vem som innehar ett nummer, vad som är det maximala antalet
steg det ska ta mig, en någorlunda smart person,
att hitta den största personen i listan?
n, eller hur?
Därför att i det värsta fallet, där kanske den största värdet vara?
Höger, hela vägen i slutet.
Så i värsta fall övre gräns, kanske jag
måste gå hela vägen hit och bli som,
åh, här är nummer åtta, eller vad värdet är.
Nu skulle det bara vara dumt om jag höll på, eller hur?
Söker fler och fler element om den sista av dem är borta?
Så säkert är n en övre gräns.
Jag behöver inte ta fler steg än så.
>> Så vad händer om i stället jag föreslog att Det finns algoritmer i världen som
har en gångtid som är avgränsas av stora O i log n, log n?
Där har vi sett det här förut?
Yeah?
>> PUBLIK: I telefonboken problemet?
Speak: Som telefonboken problemet.
Vad var mått på hur mycket tid eller hur många tårar det
tog mig att hitta någon som Mike Smith i telefonboken?
Vi hävdade att det var log n, och även om obekant eller så är det
lite oklar vad en logaritm eller exponent var,
kom bara ihåg att log n i allmänhet hänvisar till processen,
i det här fallet, att dela något i halv igen, och igen,
och igen, och igen, så att den blir allt mindre när du gör det.
>> Så log n avser, säker, i telefonboken exempel
till binär sökning i teorin, när vi hade de virtuella dörrarna på tavlan,
eller när Sean var söker efter något.
Om han hade använt binär sökning, log n skulle vara den övre gränsen för hur mycket
tid det tar.
Men de algoritmer som sprang in logga n antas vilka nyckel detalj?
Att listan sorterades, eller hur?
Din algoritm är fel om din ingång är inte sorterade,
och ändå du använder något liknande binär sökning
eftersom du kan hoppa rätt över elementet
utan att inse att det är faktiskt där.
>> Nu vad kan detta innebära, stort O i en?
Detta betyder inte att din algoritm tar en och endast ett steg,
det betyder bara att det tar en konstant antal steg.
Kanske är det en, kanske är det 10, kanske 1.000,
men det är oberoende av storleken på problemet.
Oavsett hur stor n är, en konstant tid algoritm
alltid tar samma antal steg.
Så vad kan vara en algoritm Vi har pratat om eller bara
intuitivt som kommer till dig att alltid körs i så kallad konstant tid?
Yeah?
>> PUBLIK: Lägg två nummer.
Speak: Lägg två nummer, 2 plus 2 är lika med 4, gjort.
Så det kan fungera, vad annars?
Vad sägs om mer verkliga världen, ja?
>> PUBLIK: Att hitta först på en lista.
Speak: Att hitta den första element i en lista, visst.
Vi har faktiskt pratat om arrayer redan,
hur får man på första element i en array,
oavsett hur länge den array är i C-kod?
Du använder precis som konsolen noll notation, bam, du är där.
Och faktiskt matriser, som en sidoreplik, stöd något allmänt känt
som random access, random access minne, eftersom du kan bokstavligen
hoppa till något ställe.
Vi kan göra detta ännu enklare vi kan spola tillbaka till vecka noll
när vi gjorde Scratch.
Hur lång tid tog det för säger blocket i Scratch att köra?
Bara konstant tid, eller hur?
Säg något, säger någonting, det spelar ingen roll
hur stora Repor världen är, är det alltid kommer att ta lika lång tid
att helt enkelt säga något.
>> Så det är konstant tid, men vad är baksidan?
Om det var över bounds, tänk om vi vill
att beskriva de undre gränser av våra algoritmer gångtid?
Nästan en bästa fall potentiellt, om ni så vill,
om dessa villkor kan gälla för bästa fall, värsta fall genomsnittliga fall mer
allmänhet, men låt oss bara fokusera på undre gränser mer allmänt.
Vad är en algoritm som har en lägre gräns för n steg,
eller 2n steg, eller 3n steg?
Några faktor av n steg, det är dess nedre gräns.
Yeah?
>> PUBLIK: Bubble sort?
>> Speak: Bubble sort tar du minimalt n steg, varför?
Varför det?
Varför skulle det börjar att komma till dig intuitivt, inte ens om det gör bara
än?
Yeah?
>> PUBLIK: [ohörbart].
Speak: Exakt.
I bästa möjliga scenariot bubbla sortera, och en hel del algoritmer,
om jag lämnar er åtta personer som redan är sorterade,
det vore dumt för dig, algoritmen,
att gå fram och tillbaka mer än en gång, eller hur?
Därför att så fort du gå igenom listan en gång,
du bör inse, åh, jag gjorde inget swappar, är den här listan sorteras, utgång.
Men det kommer att ta dig n steg.
>> Och omvänt, vad är en annan sätt att tänka på det?
Bubble sort är en omega, så att säga, av n,
för om man tittar på färre än n element, vad
är den grundläggande frågan där?
Du vet inte om det sorteras, höger.
Vi människor kanske blick på åtta människor och vara som, åh, det sorteras,
det tog mig inte n steg, men det gjorde det.
Dina ögon, även om du snäll i har ett stort synfält,
du tittat på åtta element, du tittat på åtta personer,
det är åtta steg effektivt.
Och bara om jag gå igenom hela Listan gör jag inser, ja, sortering.
Om jag stannar halvvägs tänka, allt rätt, det är ganska sorteras hittills,
vad är oddsen att det inte är sorterade?
Det algoritmer kommer inte att vara korrekt.
Kan vara snabbare, men felaktig.
>> Så nu har vi ett sätt att beskriver en undre gränser,
och hur är det konstant tid?
Vad är en algoritm som har en lägre bunden på sin speltid på en?
1 steg 2 steg, 10 steg, men konstant, oberoende av n,
storleken på den ingående?
Ja, i ryggen.
>> PUBLIK: Printf?
Speak: Vad är det?
PUBLIK: Printf?
Speak: Printf.
OK, visst.
Så det tar ett fast antal steg.
Och jag bör nu-- nu vi pratar om C-kod
och inte Scratch, något liknande säg, med printf,
Vi borde börja få försiktig.
Eftersom printf tar ingång, det är en sträng,
och stråkar har tekniskt längd.
Så om vi nu vill plocka på dig, om du inte har något emot,
tekniskt vi skulle kunna hävda att printf tar en input variabel längd,
och säkert det kan ta mer tid att skriva ut en sträng så här länge,
än så länge.
>> Så vad händer om vi anser bara sortering och sökning exempel?
Hur är det med Mike Smith i telefonen bok, eller binär sökning mer allmänt?
I bästa fall, vad som kan hända?
Jag öppnar telefonboken och, bam, det är Mike Smiths nummer.
Jag kan ringa honom direkt.
>> Tog ett steg, kanske två steg, men ett konstant antal steg
om jag hade tur.
Och ärligt talat, vi såg på Måndag din klasskompis
få ganska tur två gånger i rad.
Och det var faktiskt konstant gången på undre gränser
på algoritmen i fråga för att hitta Antalet 50 bakom de stängda
dörrar.
>> Nu, som en sidoreplik, om du upptäcker att både stora O, den övre gränsen,
och omega, den nedre gränsen, är en i samma, att
är samma formel i parenteser, kan du också
säger, bara för att vara snygga, att något är i theta
av n eller teta av ett annat värde.
Det betyder bara när stora O och omega är samma.
Nu vad om val slag?
Låt oss använda detta nya vokabulär.
I urvalet sortera, vad var vi göra igen, och igen, och igen?
Jag tänkte fram och tillbaka genom listan, letar efter vem?
Det minsta antalet.
>> Så hur många steg, hur många jämförelser jag gjorde
måste göra för att lista ut vem det minsta elementet i listan är den?
n minus 1, eller hur?
För om jag bara börja med den jag är ges och jag börjar jämföra honom eller henne,
då honom eller henne, honom eller henne, honom eller henne, jag
kan bara koppla ihop element tillsammans n minus 1 gånger.
Så val tar sorterings liknande n minus 1 steg första gången.
>> Hur många steg tar det mig till hitta den näst minsta elementet?
n minus 2, eftersom jag är att vara dum Om jag fortsätter att titta på samma personer
igen om jag har redan valt honom eller henne och sätta dem i deras ställe.
Och det tredje steget, n minus 3, då n minus 4.
Vi har sett detta mönster innan, och faktiskt
urval sortera på liknande har en övre gräns
n kvadrat om vi gör upp det summering.
Vad är dess nedre gräns, val slag?
Minimalt, hur mycket tid måste val sorterings tar, som vi definierat det på måndag?
Föreslå två alternativ.
Kanske är det n, som tidigare.
Kanske är det n kvadrat, eftersom det är nu som den övre gränsen.
>> PUBLIK: n kvadrat.
Speak: n kvadrat.
Varför?
>> PUBLIK: Eftersom du har att definiera [ohörbart].
>> Speak: Exakt.
Åtminstone som jag definierat val Sortera det var ganska naivt, fortsätt,
hitta det minsta elementet.
Gå igen, hitta den minsta elementet.
Det finns ingen typ av optimering där som
skulle låta mig avbryta efter bara n eller så steg.
Så ja, val sortera, omega n kvadrat.
>> Hur är insättnings sortera, där jag tog vem jag fick, och sedan jag plopped honom
eller henne på rätt plats?
Sen fortsatte jag att den andra personen, plopped honom eller henne på rätt plats.
Sedan nästa person, plopped honom eller henne på rätt plats.
Lägg märke till att detta är mycket linjär, så att säga.
Jag är en rak linje, jag är inte går fram och tillbaka,
Jag har aldrig ser tillbaka riktigt, men vad som händer när jag sätter honom
eller henne i början av listan som vi gjorde i måndags?
Vad händer?
Yeah?
PUBLIK: [ohörbart].
Speak: Ja, det var fångsten, eller hur?
Du kanske kommer ihåg från dina klasskamrater, om de
gjorde någon rörelse med fötterna, det var en operation.
Så om det var tre personer här och den nya personen tillhörde väg dit,
på en lång etapp så här, visst, han eller hon kan bara gå in i det sista.
Men om vi tänker på ett dator och en matris med minne,
Dessa människor kommer att behöva blanda över
för att göra plats för den personen.
Och så att n minus en shufflings, n minus 2 shufflings, n
minus 3 shufflings är bara typ av händer bakom mig, inte framför mig
som tidigare, i någon mening.
Nu som en sidoreplik, och som du kanske har sett på nätet
om du börjar peta runt om sorterar, det finns så många olika listor
där ute, en del av dem bättre än andra.
Faktum är bogosort en det är ganska kul att se upp.
Bogosort tar en uppsättning av siffror eller säga en kortlek,
slumpmässigt blandar dem, och kontrollerar om de är sorterade.
Och om inte, gör det igen.
Om inte, gör det igen.
Otroligt dumt.
>> Och faktiskt, om du läser gillar den Wikipedia artikeln,
dess smeknamn är dum sort.
Det kommer så småningom att fungera, förhoppningsvis får tillräckligt med tid,
men den mängd av tid kan ta ganska lång tid.
Så om jag kunde, låt oss hastighet saker upp från Mary Beths exempel tidigare,
genom att ha några fler element, men två fler processorer.
Två personer, om du skulle inte ha något emot att gå med mig.
Vad sägs om en hit, och låt oss go-- ingen där borta?
Ingen där borta?
OK.
Du med den svarta skjorta, ja, kom ner.
Okej, vad heter du?
>> PUBLIKEN: Peter.
>> Speak: Vad är det?
>> PUBLIKEN: Peter.
Speak: Peter, David, trevligt att träffas.
Okej, vi har Peter här, om du vill komma på bordet här.
Och vad heter du?
>> PUBLIKEN: Elena.
Speak: Elena.
OK, trevligt att träffas.
Elena träffa Peter.
Peter, Elena.
Och vi behöver Andrew upp här också, tack.
Och din utmaning går vara att sortera en kortlek.
Och om obekanta, däck av kort bör slutligen
sorteras lite något liknande här vi ska göra klubbarna, då
spadarna, då hjärtan och diamanter, från ess som en,
hela vägen upp till kungen.
>> Korten Jag ska ge dig kommer att vara 52 i kvantitet.
Vi ska på samma sätt gång du, på bara ett ögonblick.
Vi ska kasta Andrew upp på skärmen här,
för att titta på när du gör detta.
Och så att allt detta är desto mer synliga,
dessa är de kort jag fick på Amazon.
Så de är redan slumpmässigt sorteras, och vi kommer att tajma dig.
Och vi ska hålla det riktigt den här gången,
så vi kommer att försöka pressa dig för annars kommer detta att få tråkiga
snabbt.
Om du kunde gå vidare för att sortera 52 elementen via något sätt, nu.
>> Och återigen, när vi tittar på dessa killar gör vad, till slut
kommer att producera en uppenbar resultat, tänk på riktigt
hur de var och att göra det, hur du kan beskriva det.
Eftersom igen, dessa är alla processer, algoritmer
som vi tar för givet som en människa.
Men du har antagligen länge haft intuition, långt innan du ens
tänkte på att ta en datavetenskap klass du
kan ha haft på intuition med för att lösa problem som detta.
Men när du känner igen mönstren och börja
att formalisera stegen med vilka du lösa dessa problem,
du kommer att upptäcka att du kan lösa mycket mer intressant och mycket mer komplex
problemen snabbt.
Så någon från publiken, det som är åtminstone en del av algoritmen
att de använder här?
>> PUBLIK: [ohörbart]
Speak: Vad är det?
PUBLIK: Genom kostym.
Speak: Med kostym.
Så först de klustring alla diamanter tillsammans
det verkar, alla av hjärtan ihop det verkar,
och så vidare, utan respekt för de nummer på korten.
Och nu verkar det, till exempel, att sortera dem i antal.
Mycket bra.
>> Okej, så vad som kommer att vara det sista steget då här?
När vi har fyra sorterade kostymer, vad behöver vi göra för att de fyra högarna
i syfte att uppnå en sorterade däck, helt enkelt?
Så vi måste slå ihop dem igen.
>> Så det är en intressant idé som igen, förmodar, är mycket intuitivt och med
om du kanske aldrig har smällde den typen av etikett på den.
Denna grundläggande begreppet dela problemet inte i halv denna tid,
men åtminstone i fyra bitar.
Lösa ganska mycket i grunden identiska problem
i isolering av varandra, och sedan slå ihop resultaten.
Och, utmärkt, gjort.
Okej, en stor rund applåder, om vi kunde.
>> [Applåder]
>> Speak: Jag har ingen aning om vad du kommer göra med dessa, men här har du.
Tack så mycket.
Så låt oss se, två minuter och åtta sekunder,
Om du vill utmana dina vänner.
Vad är det då kommer att vara en ta bort från denna
att vi kan utnyttja mer allmänt?
Tja, tänker tillbaka på denna rad av siffror,
och tänker tillbaka nu till några av de pseudokod vi har skrivit tidigare,
och detta var pseudokod för lösa telefonboken problemet.
Varvid i pseudokod I räknas ett mer metodiskt sätt
att beskriva hur jag gjorde ett mycket intuitivt mänsklig algoritm för att dela upp telefonen
bok i hälften, upprepa, upprepa, upprepa, tills jag hittar någon som Mike Smith,
om han verkligen är i telefonboken.
>> Men jag liksom använt vad jag ska kalla en mycket iterativ metod här,
särskilt meddelande linje 8 och linjen 11.
De vittnar om en iterativ strategi, en looping strategi,
eftersom det är precis beteendet de inducerar.
Dessa linjer både säga gå till linje tre, och du kan typ av
tänker på det i din inre öga som en loop.
Det säger åt dig att gå upp till steg tre och upprepa, igen, och igen,
och igen.
>> Men tänk om vi utnyttja en viktig idé här att vi gjorde inte sista gången,
och förenkla linje 8 och linje 11 och deras grannar
som just detta, i gult.
Det är inte i grunden förkorta pseudokoden så mycket,
men det är i grunden förändra arten av min algoritm.
Vad jag säger nu i steg 7, i steg 10,
är att söka efter Mike på exakt samma sätt,
men bara i den vänstra hälften eller den högra halvan.
>> Så med andra ord, om Jag börjar från steg ett,
plocka upp telefonboken, öppen för mitten i telefonboken, titta på namn,
Om Smith är bland heter, ring Mike, annars
Om Smith är tidigare i boken, steg sju söka efter Mike i vänstra halvan av boken.
Men denna typ av känns som det lämnar mig hängande, eller hur?
I gult, är en undervisning, men hur gör jag
söka efter Mike i det vänstra hälften av telefonboken?
Var ska jag ha en algoritm som jag
kan söka efter någon som Mike Smith?
Tja, det stirrar oss i ansiktet.
Jag kan bokstavligen använda exakt samma program på ett effektivt sätt att gå upp till toppen
åter och åter igång samma kodrader.
>> Så även om det här ska känna som lite av en cyklisk definition
var du svara någons fråga genom att bara sorts fråga
samma fråga igen, som varför, varför, varför?
Verkligheten är att vi har hårt kodat några speciella linjer, steg 4,
vilket är en om, och steg 12, vilket är ett effektivt sätt en annan gren,
eftersom vi har dessa stopgap åtgärder, denna algoritm kommer att upphöra om vi
hitta Mike, eller om vi inte gör det.
Men i steg 7 och 10 nu, vi har vad vi kallar en rekursiv algoritm.
Och rekursion är verkligen en kraftfull idé som är lite sinne bockning i början,
att vi nu kan tillämpas enligt följande.
>> Merge sort blir den sista slag som vi tittar på, åtminstone i klass formellt.
Och det är fundamentalt annorlunda från de tre sista, och definitivt
senaste fyra om vi räknar bogosort.
Här är pseudokod för sammanslagnings slag.
När du är på ingång av n element, så med tanke på en matris av storlek n, om n är mindre än 2,
tillbaka.
Så varför har jag att sanity kontrollera först?
Vad är konsekvenserna om jag lämna dig en array vars längd n är mindre än 2?
Det är redan sorterade, uppenbarligen, eller hur?
Eftersom listan har antingen ett element, som är trivialt
sorteras för att det är det enda som finns.
Eller är det för storlek noll, vilket innebär det finns inget att sortera, så av naturen
den sorteras.
Det finns bara inget fel där.
Så det är vår så kallade referensscenariot.
>> Det är i samma anda vad vi gjorde med Mike.
Om Mike i telefonboken, kalla honom.
Om han inte är där, ge upp.
Det är en så kallad basfallet, för att se denna algoritm i slutet av dagen
stannar under vissa omständigheter.
>> Men här är steg i tro nu, annars, sortera den vänstra halvan av elementen,
sedan sortera rätt hälften av elementen,
och sedan slå samman de sorterade halvorna.
Och här är där det känns som om vi copping ut.
Jag har bett dig att sortera n element, och jag är
ordstäv, OK, gör det genom att sortera vänster och sortera rätt.
Men jag säger en annan sak, och detta
är nyckeln temat verkar i intuition så här långt,
Det är det här tredje steget att slå samman.
Vilket även om det verkar så dum i anden,
som bara samman saker tillsammans, verkar det
att vara ett viktigt steg mot återmontering av två problem som
delades slutligen i hälften.
>> Så slå ihop sortera, låt oss göra detta, om du kommer blidka mig, med ytterligare en demonstration,
bara så att vi har några siffror att arbeta med.
Kan jag byta åtta stressen bollar för åtta personer?
Okej, hur du tre, du fyra i detta avsnitt, fem, sex, och låt oss
gör 7, 8, kom upp.
OK, ja OK.
Minus 8, där går vi, plus 1.
Utmärkt.
Okej Kom fram, låt oss snabbt ge dig siffror.
Nummer två, nummer tre, nummer fyra, nummer fem, sex, sju och åtta.
Jag gjorde åtta rätt den här gången.
>> OK, så sätt igång om du kunde, och Låt oss sortera i original ordning
att vi hade igår som såg så här, om du inte skulle ha något emot.
Och låt oss göra det framför bordet.
Okej, så slå ihop sort.
Det är här det händer att få typ av intressant,
eftersom jag verkar vara att ge mig själv så mycket mindre information i dag.
>> Så slå ihop slags först av allt på ingången av n element,
och är naturligtvis inte mindre än två, det är åtta, så jag har lite mer arbete att göra.
Så nu mentalt vi som en klass är nu i annan gren,
vilket innebär tre steg.
Först måste jag sortera vänstra halvan av elementen.
Så hur gör jag för att göra detta?
Tja, jag ska typ av mentalt dela upp listan här,
du behöver inte fysiskt flytta, och jag är
kommer att fokusera enbart på vänstra halvan av elementen här.
Så hur gör jag för att sortera en lista nu över storlek fyra?
Vad är min algoritm?
Först jag kontrollera är n mindre än två, nej, så jag går vidare till annat blocket igen.
Sortera vänstra halvan av element.
>> Så nu igen, mentalt, och det är där
du måste samla en massa mental historia, om man så vill.
Nu ska jag sortera vänster hälften av den vänstra halvan.
Okej, så nu kallar jag mitt samma merge sorteringsalgoritm är n mindre än två?
Nej, det är två, så jag måste sortera den vänstra halvan, och den högra halvan.
Så här går vi, sortera den vänstra halvan.
Varför inte bara ta ett steg framåt.
Vad heter du?
>> PUBLIKEN: Darren.
>> Speak: Dan.
Dan har klivit fram.
>> PUBLIKEN: Darren.
Speak: Darren, gjort.
Sa du Darren eller Dan?
>> PUBLIKEN: Darren.
>> Speak: Darren.
OK, Darren har klivit framåt och han nu sorteras.
Och det är nästan en inane påstående, eller hur?
Jag vet inte riktigt verkar vara att uppnå något, men låt oss gå vidare.
Låt mig nu sortera rätt halv av elementen.
Vad heter du?
>> PUBLIKEN: Luke.
>> Speak: Luke.
Kom igen, steg framåt.
Klar, har jag sorterat Luke.
Den vänstra halvan är nu sorteras och den högra halvan är nu sorteras,
men återigen, det är ett viktigt steg här.
Vad behöver jag nästa behöver göra?
Slå ihop de sorterade halvorna.
Nu ska vi bara ha alla fram och tillbaka på det sättet,
eftersom jag slags behov del ett utrymme.
Det är nästan som dessa killar är på ett bord,
och jag behöver lite utrymme att flytta runt dem på.
Så jag ska gå samman ni genom att titta
på den vänstra halvan och den högra halvan.
Och som uppenbarligen kommer först, vänstra halvan eller högra halvan?
Så högra halvan, så låt oss gå Luke över här för att Darren ursprungliga ståndpunkt.
Och nu att slå samman sina vänstra halvan i, Darren kommer att röra sig där.
>> Så känns nästan en bubbla sorteringseffekt,
men min grundläggande algoritm, mycket annorlunda den här gången.
Men nu börjar det bli en lite irriterande eftersom du
måste spola tillbaka mentalt där lämnade jag av.
Jag har precis slagits samman de sorterade halvorna, vilket betyder att jag var i min algoritm?
Jag måste sortera den högra halvan, eller hur?
>> Om du spola tillbaka, bokstavligen på videon, du ska
se till att vi kom till denna punkt i Lukas och Darren
genom att sortera vänster hälften av den vänstra halvan.
Sedan vi gick samman de sorterat halvor, vilka
innebär nästa steg är typ det högra halvan av den vänstra halvan.
Okej, så låt oss göra detta snabbare.
Okej, sex, kommer jag att hävda ni nu sorteras, kom fram.
Vad heter du?
>> PUBLIKEN: Adriano.
>> Speak: Adriano.
Adriano nu sorteras.
Och vad heter du?
>> PUBLIKEN: Alex.
>> TALARE: Alex är nu sorteras.
Vänster halv, högra halvan, vad är det sista steget?
Merge.
Ganska trivialt, så jag är kommer att gå samman i sex,
ta ett steg tillbaka, åtta, ta ett steg tillbaka.
Och nu märker att detta är en användbar takeaway, vad
är nu sant om den vänstra halvan av lista, oavsett hur vi började?
Det sorteras.
>> Nu det inte sorteras i den stora tingens ordning,
men den sorteras självständigt av den andra hälften.
Nu vad steget är jag på om jag håller spola tillbaka hur historien började?
Nu måste jag sortera den högra halvan.
Så nu är vi tillbaka på I början av berättelsen,
och låt oss göra detta snabbare.
Så jag kommer att sortera högra halvan av hela listan.
Vad är nästa steg?
Sortera vänstra halvan av den högra halvan.
Sortera vänstra halvan av vänstra halvan av den högra halvan.
Och vad heter du?
>> PUBLIKEN: Omar.
>> Speak: Omar, steg framåt, gjort.
Vänster halva sorteras.
Och vad heter du?
>> PUBLIKEN: Chris.
>> Speak: Chris, ta ett steg framåt, du är nu sorteras.
Vad är den viktigaste steget nu?
Merge.
Så man kommer att gå samman på plats Här, om du kunde ta ett steg tillbaka,
och tre kommer att ta ett steg tillbaka, slå samman.
Så den vänstra halvan av högra halvan, nu sorteras.
Ärligt talat, denna algoritm känns som vi slösar mycket mer tid än tidigare,
men om vi gjorde detta i realtid, vi ska se vad takeaways kommer att bli.
Nu är jag här, rätt hälften av den högra halvan,
Låt mig gå vidare och sortera den vänstra halvan.
Steg framåt, vad heter du?
PUBLIKEN: Ramsey.
TALARE: Ramsey nu sorteras.
Vad heter du?
>> PUBLIKEN: Marina.
>> TALARE: Marina nu sorteras som Tja, om du tar ett steg framåt.
Nyckel steg här nu samman, jag är kommer att plocka från mina två listor,
vänster och höger.
Fem kommer att komma först, och sju kommer att komma härnäst.
Och återigen, detta är avsiktlig.
Det faktum att de tar steg framåt och bakåt
är tänkt att representera att vi inte kan gör denna algoritm på plats som lätt
som bubbla sortera och välja sortera, och insättning sortera där vi bara
hålls byta folk.
Jag behöver bokstavligen en sorts av scratch papper där
att sätta dessa människor medan jag gör en sammanslagning,
och sedan kan jag sätta dem på plats igen.
Och det är nyckeln eftersom jag använder en ny resurs, utrymme, inte bara tid.
>> OK, det här är fantastiskt.
Vänster halva sorteras, högra halvan är sorterade, nu när nyckeln sammanslagning steg.
Hur ska jag slå ihop det här?
Så om du ska följa min vänster hand och höger hand,
Jag kommer att peka min vänstra hand på den vänstra halvan, min högra hand
på den högra halvan, och nu måste jag besluta steg för steg som att gå samman i.
Som uppenbarligen kommer först?
Nummer ett.
Så kom den hit, Här är vår scratch pad.
Så nu nummer ett, och varsel vad jag ska göra med min högra hand,
Jag ska flytta min högra hand en steg över till punkt nummer tre,
och nu måste jag göra samma beslut.
Och faktiskt står rätt i framför Luke här om du kunde,
eftersom detta är vår scratch pad.
Så vem kommer härnäst?
Vi har Lukas med nummer två eller Chris med nummer tre.
Uppenbarligen Luke, antal två, så du kommer hit.
>> Men min vänstra hand nu kommer att ökas för att peka på Darren,
och här är nyckeln ta bort med sammanslagning, kommer jag att fortsätta att göra detta,
självklart, om du snäll av följa logiken.
Men mina händer är aldrig kommer att gå bakåt,
vilket betyder att jag alltid bara flyttar till vänster med min sammanslagning process,
och det kommer att vara nyckeln till att vår analys på bara ett ögonblick.
>> Så nu ska vi avsluta detta snabbt.
Så tre kommer nästa, sedan fyra kommer därnäst,
och nu fem kommer nästa, sedan sex, och sju, och sedan slutligen åtta.
Känns som den långsammaste algoritmen ännu, men inte om vi faktiskt
kör den på samma sorts av klockhastighet, så att
tala, med samma tickande klocka som tidigare.
Varför?
Nåväl, låt oss ta en titta på slutresultatet.
>> Låt oss gå tillbaka hit, låt mig dra upp en demonstration visuellt
av vad vi just gjorde.
Zooma in här, på denna sida här, berättar Firefox
att vi vill köa upp i den här rutan, låt oss
säger bubbla sortera, med vilken Vi är nu väl bekant,
urvals sortera, som är en annan ganska okomplicerad man,
och nu dagens merge sort, som kommer att vara vår climactic slut.
Anledningen till att det tog så mycket längre här med människor och mig verbalt är,
självklart, jag förklarar varje steg.
Men om du bara köra det här, mycket som vi gjorde bubbla sortera och urval
sorterar inte bara visuellt, klocka hur mycket mer effektivt
denna hävstångseffekt division och erövra
kan när den tillämpas på en datamängd som är inte ens storlek åtta, men även mycket,
mycket större.
Jag ger dig samman sortera, sida vid sida med dessa andra algoritmer.
Det här kommer att bli smärtsamt snabbt, och sluttid
är inte särskilt kulminerande, de bara sluta sortering.
Men nyckeln ta bort är att ser hur mycket snabbare samman sorterings
var, om du inte tror att jag är bara typ av jävlas med dig.
Om vi ​​gör det här en sista gång, låt oss ladda om, låt oss gå tillbaka
och välj bubbla sortera, och bara för sparkar,
Låt oss välja insättnings sortera, bara för bra åtgärd.
Och den här gången igen, låt oss välj merge sortera och låt oss
faktiskt köra dessa sida vid sida.
>> Och det är inte i själva verket en lyckträff.
Vad jag har effektivt gjort är jag har indelat min input på mitten, igen,
och igen, och igen.
Och det finns bara så många gånger du kan dela upp din input i halvor, vänster
och höger.
Vad är formeln som vi håller ser som beskriver uppdelningen i hälften
igen, och igen, och igen, och igen?
>> PUBLIK: Logga n.
>> Speak: Log n.
Men sedan finns det en annan viktig åtgärd, denna algoritm är inte log n steg.
Om det bara var log n steg, Vi skulle vara i samma problem
som tidigare där vi inte kan vara att allt är sorterade.
Du måste minimalt titta på n element att vara säker n elementen sorteras,
annars är det ett steg i tro.
>> Så det är minimalt log n steg, men hur är denna nyckel sammanslagning steg
där jag gick samman min vänstra halvan och höger hälften och gick över scenen?
Hur många steg är att gå samman?
Det är n, men jag gjorde inte bara slå ihop den sista tiden.
På var och en av dessa kapslade samtal, på varje av dessa kapslade går samman, jag sorteras fortfarande.
Jag slås samman dessa två killar, då dessa två killar, då dessa två tjejer och så vidare.
>> Så jag gjorde en sammanslagning igen, och igen.
Hur många gånger?
Så varje gång jag delade Listan på mitten, gjorde jag en sammanslagning.
Dela upp listan på mitten, gör en sammanslagning.
Så om man dividerar lista kan göras log n gånger,
och sammanslagningen till slut tar n steg, vad som kan vara nu den övre
bundet på driften tiden för vår algoritm?
n log n.
>> Och faktiskt, det är vad det vi har uppnått här.
Så den känslan som du ser visuellt när dessa tre saker körda sida vid sida
är n squared mot n kvadrat mot n log n.
Som i grunden får vi se, inte bara idag utan även i framtiden,
är mycket, mycket snabbare.
En applåd för dessa killar, Jag kommer att belöna dem med stress bollar.
Låt oss ajournera här i dag, och vi ses på måndag.