>> [MUSIK SPELA]
>> DAVID J. MALAN: Detta är CS50.
Och detta är början på veckan tre.
Så vi har en hel del spännande saker att täcka idag.
En hel del möjligheter för volontärer upp på scenen.
Och i slutändan, är idag inte om kod alls.
Men det handlar om idéer, och det handlar om algoritmer,
och faktiskt få tillbaka en del av de lärdomar som dragits från vecka noll,
vari minns, vi infört denna monster.
Och upplåning inspiration från detta, för att starta
att lösa allt mer sofistikerade problem algoritmiskt.
Men först, ett par meddelanden.
Så en, om du vill gå CS50 personal och klasskamrater vid lunch
denna fredag, både här och i Cambridge, och i New Haven,
besök kursens webbplats där en URL kan hittas.
Föreläsning denna onsdag kommer inte vara här i Sanders.
Det blir bara på nätet, så lyssna på CS50: s hemsida,
om här i Cambridge eller New Haven som också.
>> Och sedan problem ställa in två är redan i dina händer.
Om du inte har dykt ännu, låt mig att erbjuda skarpt förslag
att, särskilt nu, som problemet sätter förväg,
du verkligen vill börja nu, om inte dabble lite på helgen eller före
när de först gå ut på Fredagar eftersom du kommer
tycker att de är inte nödvändigtvis blir längre eller mer utmanande per
SE.
Jag tror att du kommer att upptäcka att, i Generellt tenderar de att ta ungefär
ungefär samma tid.
Men det verkligen beror på eleven, och det
beror på tänke med vilken du närmar dig det.
Men alltid, du kommer att köra upp mot några väggen,
och du kommer att träffa vissa programfel, och du är bara
inte kommer att kunna komma över det någon gång.
Och det är oerhört värdefullt att kunna att steg bort, kom tillbaka nästa dag,
gå till kontorstid, inlägg på CS50 Diskutera eller liknande, för att faktiskt få hävs.
Så ha det i åtanke.
Starta tidigast som möjligt är det bästa du kan göra.
Så här är där vi började klassen, över i vecka noll.
Och kan vi få en volontär här för att hjälpa mig att hitta mikrofoner?
OK.
Stående upp redan.
Kom upp.
Antar att det är hur det kommer att fungera.
Vad heter du?
ALAN ESTRADA: Alan Estrada.
DAVID J. MALAN: Alan Estrada.
Kom upp.
Trevligt att träffas.
ALAN ESTRADA: Trevligt att träffas.
DAVID J. MALAN: Och du var här med oss ​​i vecka noll, naturligtvis.
ALAN ESTRADA: Jag var.
Jag var.
>> DAVID J. MALAN: Så kan du gå framåt och hitta för oss Mike Smith,
så fort du kan?
Så fort du kan.
Bokstavligen riva problemet i hälften så du behöver.
>> ALAN ESTRADA: Um.
DAVID J. MALAN: Bokstavligen riva problemet i halv.
>> ALAN ESTRADA: Oh.
Mm.
Väldigt bra.
>> David J. MALAN: OK.
God.
Tack.
ALAN ESTRADA: Mycket bra.
OK.
>> DAVID J. MALAN: Och så nu, du har skurit ner
till halv storlek av problemet.
Nu är vi ner till en fjärdedel.
Är du uppmärksamma vilken sida vi håller?
>> [Skrattar]
>> ALAN ESTRADA: Ja, jag think--
>> DAVID J. MALAN: Vilka avsnitt är vi i?
ALAN ESTRADA: Ljuddämpare, så.
>> David J. MALAN: OK.
Men Mike Smith går vara efter Ljuddämpare.
So--
>> [Skrattar]
>> Okej.
ALAN ESTRADA: Vart är vi ser?
DAVID J. MALAN: Mike Smith.
ALAN ESTRADA: Mike Smith.
DAVID J. MALAN: Nu, vi är i kirurgiskt.
Nu, läkare.
Now--
>> ALAN ESTRADA: Let's- låt oss gå med riktiga.
Real.
>> DAVID J. MALAN: Real.
OK.
Om du behöver Real.
Nu är vilken väg Mike Smith?
>> ALAN ESTRADA: Detta sätt.
>> DAVID J. MALAN: Vilken väg?
ALAN ESTRADA: Vänta.
M är-- rätt?
Vi började with--
>> DAVID J. MALAN: Ja.
De är kvar.
Du har rätt.
>> ALAN ESTRADA: Ja.
>> DAVID J. MALAN: Så Mike här.
ALAN ESTRADA: Vad?
>> [Skrattar]
>> Dåligt exempel, killar.
Förlåt.
DAVID J. MALAN: Detta kommer att lära du att hoppa ur stolen.
>> ALAN ESTRADA: Oh.
Oh.
Jag fick dig.
Oh.
Detta är-- OK, jag har dig.
Smith just här?
>> DAVID J. MALAN: Smith, tack.
Så jag ska fortsätta leta upp Smith?
>> ALAN ESTRADA: Oh, ja.
Nej nej nej.
Å nej.
Den här är min.
>> DAVID J. MALAN: Åh, du fick Smith.
OK.
>> ALAN ESTRADA: Ja, jag fick Smith här.
Ledsen, killar.
Jag trodde Michael-- vi letade efter Michael.
Förlåt.
>> DAVID J. MALAN: Det är OK.
Okej, nu är vi in Paccini and Sons.
>> ALAN ESTRADA: Paccini och söner.
DAVID J. MALAN: Bara du och jag är på den här.
OK.
Hitta hit Mike Smith.
Smith.
>> ALAN ESTRADA: Smith.
>> DAVID J. MALAN: Smith.
Vi är i forskning för sopor.
ALAN ESTRADA: Skräp.
Oh.
Detta kommer att ta ett tag.
>> [Skrattar]
DAVID J. MALAN: Skor.
Vi är i skor.
>> ALAN ESTRADA: Nu är vi gonna--
>> DAVID J. MALAN: Nice.
ALAN ESTRADA: Which--
[Skrattar]
Åh, det här är bra.
[Skrattar]
>> DAVID J. MALAN: Det är OK.
>> ALAN ESTRADA: Åh, det är bra.
Jag tror inte att jag kommer att har PSAT kompisar efter detta.
DAVID J. MALAN: Good.
Sporting.
ALAN ESTRADA: Sporting.
Um, L, M, N, O, P.
David J. MALAN: OK.
Så låt oss riva det i hälften.
Det är ok.
Detta avslutar dåligt ändå, eftersom Mike Smith kommer inte att vara i gula sidorna.
>> ALAN ESTRADA: Aw.
>> DAVID J. MALAN: Nej, det är OK.
Men låt oss låtsas som han är på denna sida.
Så nu har du skurit problemet ner till en sida, och vi hittade Mike Smith.
>> [GLÄDJANDE]
Okej tack så mycket.
OK.
Det var extra.
Men det var fortfarande snabbare än linjär sökning,
där vi börjar på början av boken,
och vi flyttar vår väg från vänster till höger, småningom letar efter Mike Smith.
Och så, om telefonboken hade kanske 1.000 sidor,
Kanske skulle det ha tagit oss 10-tal sidan tårar.
>> Men du kanske har belånade rörde ett antagande
under allt detta, det vill säga att telefonboken i förväg var vad?
PUBLIK: Sorterade.
DAVID J. MALAN: Det sortering.
Höger?
Det är sorterade i bokstavsordning, så att alla dessa namn och nummer
sorteras från A: s till Z: s, och i bokstavsordning i mellan.
Men i dag, vi ber nu frågan, ja,
Hur gjorde Verizon eller telefon företag få in detta tillstånd?
>> Eftersom det är en sak att utnyttja detta antagande, och därför,
lösa ett problem med en algoritm mer effektivt.
Men vi aldrig riktigt frågade vecka noll, ja,
hur mycket kostade det Verizon eller någon annan
att få det telefonboken i sorterad ordning?
>> Höger?
Det spelar ingen roll om tittar upp Mike Smith
är supersnabb, om det tar en år för att sortera sidorna först.
Höger?
Du kan lika gärna sålla genom en randomiserad telefonbok,
om det kommer att bli super dyrt att sortera det.
Så om vi kan ha en annan volontär.
Låt oss ta en titta upp här på hur vi might-- komma på up-- hur
vi kan gå till väga sortering dessa.
>> Och om Jordanien kunde faktiskt ansluta sig till oss här uppe på scenen.
Kom upp för bara ett ögonblick.
Vad heter du?
CAROLINE: Caroline.
DAVID J. MALAN: Caroline, kom upp.
Och du kommer att få sällskap av mig och Jordanien här.
Caroline, tack.
Okej.
Så vad vi har för här Caroline är 26 blå böcker
att FAS använder för att administrera vissa slutprov.
Dessa blir svårt att hitta, men vad vi har gjort i förväg
är att vi har lagt någons namn på framsidan av var och en av dessa,
men vi har hållit det enkelt genom sedan sätta ut fullständiga namn.
Så vi skulle sätta den person med namnet L, M, J, B, hela vägen A till Z,
men de är i slumpmässig ordning.
Och så om du skulle prata din igenom problem som du
gör det, kan du gå vidare och sortera dessa för oss, från A till Ö
>> Målgrupp: OK, så L är som i mitten.
C börjar.
B. J före L. B, Q.
>> DAVID J. MALAN: Håll att funderade en sekund.
För annars är bara detta intressant för dig, mig och Jordanien.
Det går vi.
PUBLIK: [OHÖRBAR].
R.
David J. MALAN: OK.
Vad gör du?
>> CAROLINE: M kommer efter O.
>> David J. MALAN: OK.
>> CAROLINE: O.
DAVID J. MALAN: O, bra.
>> CAROLINE: E.
>> David J. MALAN: E, F. Ja.
>> CAROLINE: T, U, V.
>> David J. MALAN: V, T, U, V. Så det ser ut som du är making-- hålla igång.
Det ser ut som du gör en stor hög hit,
och slag av en stor hög därborta.
Så den första halvan av alfabetet, andra halv av alfabetet.
OK.
God.
Typ av att dela upp problemet i två.
M, N, X. Yeah.
CAROLINE: K.
David J. MALAN: OK.
K. Så du är typ att välja dem en efter en,
sätta det antingen vänster eller höger, eller Z är det som händer på golvet.
OK.
>> CAROLINE: Z kommer på golvet.
>> David J. MALAN: OK.
Y går på golvet.
Nu kan vi sätta X.
>> CAROLINE: G.
DAVID J. MALAN: G gå vänster.
S går rätt.
Okej, är A går hela vägen till vänster.
>> CAROLINE: A, B, C, D.
>> DAVID J. MALAN: Nu, bra.
Vi har A, B, C. W: s går där nere.
Okej, T.
>> CAROLINE: H, I, J.
DAVID J. MALAN: H, I, J Bra.
CAROLINE: I centrum, jag gonna--
David J. MALAN: OK.
Så nu ska vi slag av samman dessa olika högar.
Så A till C, då ser jag D, och E och F, och G och H, och I. Nice.
J, K. Och sedan, är denna hög upp och ner, men det är OK.
Visst.
Vi kan klippa vissa hörn.
OK.
Och då behöver vi W, X, Y, Z.
>> CAROLINE: Ja.
>> DAVID J. MALAN: Excellent.
Så ett stort tack till Caroline för sortering av dessa.
>> [GLÄDJANDE]
>> Tack.
Tack så mycket.
Så nu ska vi överväga för ett ögonblick hur Caroline gick om att göra det,
och exakt vad vi kunde att-- hur vi
kunde lösa det problem när vi var bara
med tanke på en hel massa slumpmässiga ingångar.
>> Det ser ut som det var lite av ett system där?
Höger.
Så de tidigare breven i alfabetet, hon
var att sätta åt vänster, och senare bokstäver i alfabetet,
Hon satte in höger.
Och så snart hon hittade vissa proximala bokstäver, ettor
som går bredvid varandra, hon skulle sätta dem i ordning.
Och så vi hade typ av dessa små högar av sorterade ingångar inträffar.
>> Och så det är ganska precis vad de flesta av oss människor skulle göra.
Vi skulle sorts sålla bland det, och vi skulle slags ha en mekanism.
Men det kan vara svårt att skriva ner i en formel i och för sig.
Det kändes lite mer organiskt än så.
Så låt oss se om vi kan nu bundet problemet med färre ingångar.
>> I stället för 26, låt oss göra något betydligt färre
med bara säga, sju, bakom dessa dörrar, så att säga.
Finns det bara sju siffror?
Och om målet nu hand är att finna ett värde,
låt oss se hur effektivt vi kan gå om att göra detta.
Och låt oss se om vi kan nu börja tillämpa några siffror,
eller vissa formler som att beskriva effektiviteten i vår telefonbok
algoritm, vår examen bok algoritm och mer allmänt, att hitta information.
>> Så för detta, låt mig gå vidare och på pekskärmen över här,
sätta upp en webbläsare som har just dessa sju dörrar.
Och om vi kunde få en annan volontär att komma på hit,
Jag har lagt samma dörrar hit.
Snabb volontär.
>> Denna en-- demos går till en snabbare och snabbare nu.
Kom ner.
Vad heter du?
TREVOR: Trevor.
>> David J. MALAN: Trevor?
Okej, Trevor, kom ner.
Så Trevor har frivilligt för att göra ett liknande problem, men en som är
mindre omfattning, och det kommer att tillåta oss att försöka formalisera nu
processen för att sortera dessa nummer.
>> Så Trevor, trevligt att träffas.
Så här är en array, så att tala, en förteckning över sju dörrar.
Gå vidare och hitta oss numret 50.
Och sedan i efterhand, berätta för oss hur du hittade det.
Bör be-- okej.
Ja, det här är en här?
Hoppsan.
OK.
Du klickade att en.
God.
>> Och bra.
Nu kan du klickade den.
Och låt mig ge dig mikrofonen, så att du har det på bara ett ögonblick.
Gå vidare och klicka på intill som du tänker.
Ja bra.
TREVOR: Kan jag avmarkerar en dörr?
DAVID J. MALAN: Nej, du kan inte avmarkerar.
TREVOR: OK.
Den här.
DAVID J. MALAN: Vart vill du åka?
Vilken?
>> TREVOR: Att en.
>> DAVID J. MALAN: Nej
>> TREVOR: OK.
Den här.
>> DAVID J. MALAN: Ja.
Det var bra.
Okej.
Så vad var din algoritm eller förfarande för att göra detta, Trevor?
>> TREVOR: Jag bara gick igenom dörrar tills jag hittade en 50.
David J. MALAN: OK.
Utmärkt algoritm.
Så det är bra.
För i själva verket om jag avslöjar vad som är bakom dessa två dörrar, vad
vi hittar här är att Vi har bara slumpmässigt ingång.
Så det var faktiskt så bra som du kan få.
Och i själva verket har du bättre än uttömmande söka hela uppsättningen,
eftersom det skulle ha varit riktigt otur om du hade träffat nummer
50 i allra sista dörren.
Men vad händer om vi istället gav dig ett antagande.
Antar att jag sorterar alla dessa dörrar runt,
så att du har siffror sorteras den här gången,
men den här gången är det faktiskt en different-- den här gången,
det är faktiskt sorterats för dig.
Och nu målet till hands är att slå numret 50.
>> TREVOR: OK.
>> DAVID J. MALAN: Vad är din algoritm kommer att bli?
>> TREVOR: Tja, om det är sorteras, är det antingen gå
att be-- om störst till största, fallande, det blir den första,
eller om det är tvärtom, det kommer att bli den sista.
Så jag ska bara tryck på den här dörren, och sedan bara trycka på den sista dörren.
DAVID J. MALAN: Excellent.
Okej.
Så fann vi nummer 50.
Så snart som du visste de var sorteras, vi
kunde utnyttja detta antagande.
Så de är för mycket som telefonboken exempel.
Så snart du har, även med ett litet problem som detta,
ingångarna försorterade, vi kan faktiskt hitta värdet utan tvekan
mer effektivt.
>> Och jag ville inte berätta om det var sorterade små till stora eller stora till små,
och så det var mycket rimliga att starta vid en eller den andra änden
att faktiskt tycker att målvärdet.
Så tack till Trevor också.
Och jag ska propose-- snyggt gjort.
Vi har en liten klämma, faktiskt, att är bland våra favoritögonblick i CS50,
varigenom ibland dessa demos inte riktigt går enligt plan.
Och faktiskt just nu, jag drog upp fel gränssnitt
som man kan använda pekskärmen.
Så det var mitt fel där.
>> Så det här kommer att leda till nästa års klipp som
varför jag var att klicka på min egen skärm.
Men låt oss ta en snabb titt på vad som hände förra året
med Jay, som kom upp, mycket som Trevor här, frivilligt,
och i denna korta klipp ser du hur samma demo inte helt
avslöjar samma lärdomar.
[VIDEOAVSPELNING]
-Alla Jag vill att du ska göra nu är att hitta för mig, och för oss,
verkligen, antalet 50 ett steg i taget.
>> -Den Nummer 50?
>> -Den Nummer 50.
Och du kan avslöja vad som är bakom vart och ett av dessa dörrar
helt enkelt genom att trycka på den med ett finger.
Jäklar.
>> [Skrattar]
>> [END SPELA]
DAVID J. MALAN: Så det gick väldigt bra.
De var de osorterade dörrar.
Och Jay, naturligtvis, tyckte att det var alltför snabbt.
Trevor gjorde ett mycket bättre jobb i termer av en teachable ögonblick,
så att säga, i år i tar längre tid att hitta den.
Naturligtvis, så vi gav Jay en andra chans,
där vi sorterade dörrarna, precis som vi gjorde för Trevor,
och Trevor gjorde super bra den här gången.
Men Jay gjorde det hälften så snabbt.
[VIDEOAVSPELNING]
-Den Målet är nu att även hitta oss numret 50,
men gör det algoritm, och berätta hur du går om det.
>> -OK.
>> -Och Om du tycker det, hålla dig filmen.
Om du inte hittar det du ge det tillbaka.
>> -Man.
>> -oh!
>> - [OHÖRBAR] OK.
Så jag kommer att kontrollera ändarna först för att avgöra om there's-- Oh.
>> [Applåder]
>> [END SPELA]
David J. MALAN: OK.
Så sorterings dörrar klart leder till ökad effektivitet.
Och så, dubbelt så snabbt är vad jag menade det.
Och så Jay hade tur båda gångerna.
Och han också hade tur i den sista år, jag beställde vissa Blu-ray-skivor
att faktiskt ge ut.
Jag är ledsen i år, vi hade inte samma, Trevor.
Men ännu bättre var ett par år tillbaka.
Och några av er kanske vet detta karl, Sean, som när han var i CS50,
utmanades med den exakta Samma problem, om än i SD,
eftersom du snart se, tillbaka i dag.
Och du kommer att upptäcka att inte bara gjorde han ta lite längre tid än Jay,
lite längre än Trevor, var det faktiskt denna underbara möjlighet
att engagera sig nästan alla i Publiken a la priset är rätt, att uppmuntra
honom att hitta numret vi sökte.
Låt oss. ta en snabb titt.
>> [VIDEOAVSPELNING]
>> -OK.
Så din uppgift här, Sean, är följande.
Jag har gömt bakom dessa dörrar nummer sju.
Men undanstoppad i en del av dessa dörrar liksom är andra negativa tal.
Och ditt mål är att tänka av denna översta raden av siffror
som bara en array, eller bara sekvens av bitar av papper
med siffror bakom dem.
Och ditt mål är, bara med hjälp toppen array här, hitta mig nummer sju.
Och vi sedan kommer att kritisera hur du går om att göra det.
-Okej.
-Hitta Oss nummer sju, tack.
Nej.
Fem, 19, 13.
>> [Skrattar]
>> Det är inte en kuggfråga.
En.
>> [Skrattar]
Vid denna punkt, är din poäng inte mycket bra, så du kan lika gärna fortsätta.
Tre.
>> [Skrattar]
>> Fortsätt.
Ärligt talat, jag kan inte låta bli att undra vad du ens tänka på, so--
>> [Skrattar]
Endast den översta raden, så du har tre kvar.
Så hitta mig sju.
>> [Skrattar]
17.
Sju.
>> [Applåder]
>> Okej.
>> [END SPELA]
>> DAVID J. MALAN: Så vi kunde titta på dem hela dagen lång.
Och naturligtvis, en del av årets demos kanske
kommer nu att hamna i nästa Årets video också.
Så nu ska vi faktiskt fokusera på de algoritmer
här, och se om vi kan inte Nu börjar formalisera
hur vi kan gå om att få våra data i detta tillstånd att det är sorteras,
så som i slutändan, vi kan faktiskt sök det mer effektivt.
Och även om vi ska att använda ganska små datamängder,
som åtta siffror vi har här på bordet,
i slutändan samma idéer skulle kunna tillämpas till 1.000 ingångar, en miljon ingångar,
4 miljarder ingångar, eftersom algoritmerna kommer att vara i grunden densamma.
>> Och så detta är vår sista möjlighet för volontärer i dag,
men kanske den mest engagerade en, som vi behöver åtta frivilliga
att komma upp och gå oss genom processen att sortera vad som kommer snart
vara på dessa notställ här.
Låt mig börja tillbaka hit.
>> Så en i turquoise-- grönt är det?
Är du begår?
Två.
Kom ner.
OK.
Tre.
Fyra.
Låt mig-- OK, fem.
Du är nominerad av din vän.
Sex, sju och åtta.
Kom upp.
Okej.
Tack så mycket.
Kom upp.
>> Okej.
Så vad vi har här-- och detta är bland de mer besvärliga sådana,
eftersom detta kommer att kräva att du humor mig bara lite tid.
Du ska vara nummer ett.
Vad heter du?
>> ANNAN: Annan.
>> DAVID J. MALAN: Annan.
David.
Vad heter du?
>> JOSEPH: Joseph.
>> DAVID J. MALAN: Joseph, du är nummer två.
>> Serena: Serena, nummer tre.
Stefan, nummer fyra.
CYNTHIA: Cynthia.
DAVID J. MALAN: Cynthia, nummer fem.
[OHÖRBAR]
David J. MALAN: [OHÖRBAR].
David, nummer sex.
MATT: Matt.
DAVID J. MALAN: Matt nummer sju.
Och?
>> WAVERLY: Waverly.
>> DAVID J. MALAN: Waverly, nummer åtta.
Okej.
Om du could-- hoppsan.
Om du allt, som din första utmaningen, det
är åtta notställ här inför publiken.
Om du kan sätta dina siffror på dessa notställ på ett sådant sätt
att de ställer upp med samma siffror på tavlan.
Så gör er ser ut att genom sätta dina nummer på dessa musik
står här.
Utmärkt hittills.
>> Utmärkt.
OK.
Så nu ska vi be fråga i ett par olika sätt.
Hur kan vi gå om sortering dessa folks här?
Eftersom vi hade några metoder tidigare, där vi var
typ av att göra två olika skopor.
Och sedan var vi i allmänhet aktualiserat saker tillsammans.
Så snart vi såg två siffror som tillhörde tillsammans,
vi sätta ihop dem.
Två bokstäver som hör ihop.
>> Men låt oss se om vi kan inte formalisera detta,
så att vi i slutändan har vissa pseudo-kod du vill,
med vilken du kan lösa dessa problem.
Så nu, jag tittar ut på dessa siffror här.
Och jag ser en massa misstag.
I slutändan, jag vill ha en på vänster och åtta på höger sida.
>> Och så jag tittar på dessa två, fyra och två.
Och vad är problemet, naturligtvis?
Yeah.
So.
Två uppenbarligen kommer före fyra, så att du vet vad?
Låt mig först ta en girig strategi om ni så vill, likt problem
ställa en-- om du minns från Standard Edition Problem Set One,
där jag bara lokalt lösa problemet det är just här framför mig
och se vart det leder mig.
>> OK.
Så två och fyra, låt mig gå framåt och bara byta ni två.
Om du fysiskt kan flytta er och dina papper,
Jag verkar ha fått lista i ett bättre tillstånd.
>> Nu, de är bra.
Jag kommer att gå vidare, fyra och sex, ser bra ut.
Inget problem.
Sex och åtta, OK.
Åtta och en, ett annat problem.
För vad är sant om åtta och en?
Man kommer före åtta, och så vad ska vi göra?
Låt oss byta dessa två.
En och åtta.
Och nu kommer jag att fortsätta.
Jag kommer att hålla blicken riktad framåt.
Och låt oss se vad som händer.
Åtta och tre, Naturligtvis i ordning.
Låt oss swap.
Åtta och sju, naturligtvis.
Trasig.
Låt oss swap.
Åtta och fem, naturligtvis, låt oss byta.
Okej.
Listan sorteras.
ja?
>> OK, uppenbarligen inte.
Men det är lite bättre, eller hur?
Eftersom meddelande vad som hände.
Varje gång vi utförde en swap, en mindre Antalet slags trängt det sättet,
och ett större antal trängt detta sätt, eller vi ska
börja säga bubblade till vänster eller bubblade till höger.
>> Nu är det inte tillräckligt, eftersom i bästa fall ett antal kanske
har flyttat en fläck framåt, eller i värsta fall,
ett antal kan ha flyttas en fläck ytterligare.
Så du vet vad denna typ av fungerat ganska bra hittills.
Låt mig bara prova igen.
Två och fyra, de är OK.
Fyra och sex, de är OK.
Sex och en, i ordning.
Så låt oss byta er två.
Och nu märker problemets börjar bli lite bättre igen.
Sex och tre, i ordning.
Låt oss byta er två.
Sex och sju, du är bra.
Sju och fem, naturligtvis, i ordning.
Sju och åtta, i ordning.
Och nu kan jag behöva gör detta några gånger.
Och i själva verket tänka själva kanske hur många gånger maximalt
jag kanske måste gå fram och tillbaka?
>> Vi ska återkomma till det.
Så två och fyra är fortfarande OK.
Fyra och en, nix.
Så, låt oss byta.
Och återigen, märker visuellt en är typ av bubblande
till vänster, där det ska vara.
Fyra och tre swap.
Fyra och sex.
Sex och fem swap.
Sex och sju.
Sju och åtta är goda.
>> God.
Vi får ännu bättre.
Så låt oss se.
Nu har vi två och en.
Naturligtvis, byta.
Två och tre, tre och fyra, fyra och fem, sex och sju, sju och åtta.
God.
Och vet du vad?
Eftersom jag gjorde en förändring där, Låt mig göra en sanity check.
Låt mig gå hela vägen tillbaka till början.
OK.
En, two-- Japp, se?
Något var fel.
Tre, fyra, fem, sex, sju, åtta.
Och i denna sista passet, är dig bekväm med min nu
hävdar det sorteras?
OK.
Visuellt är det helt sant.
Men funktionellt, vad gjorde också bara händer
i det sista passet som låter dig bekräfta att denna lista är verkligen
sorterat?
>> Vad har jag gjort eller inte göra det sista passet?
PUBLIK: Det fanns inga förändringar.
DAVID J. MALAN: Förlåt?
PUBLIK: Inga ändringar.
DAVID J. MALAN: Det fanns inga förändringar.
Så det skulle vara dumt av mig att gör samma algoritm igen
om jag inte göra någon ändrar första gången.
Och staten har inte förändrats.
Visst, jag kommer inte att göra någon ändrar andra gången.
Och så är det säkert nu att säga, är listan sorteras.
>> Och faktiskt, är detta nu något som vi ska i allmänhet
samtalsbubbelsortering, varvid parvis, du korrigera misstag igen,
och igen, och igen, och du hålla gå fram och tillbaka,
och fram och tillbaka, tills du gör inga sådana swappar, vid vilken tidpunkt
du kan vara säker på, ja, jag korrigerat alla misstag.
Låt oss återställa och prova en annan strategi.
Om ni kunde gå tillbaka till den ordning du var för en stund sedan,
som såg ut så här.
Nu ska vi ta en strategi a lite mer som testet bok,
där vi var ständigt välja bokstav i alfabetet
att vi typ av ville att ta itu med nästa.
Kanske var det en hög brev, som A, eller en låg bokstaven Z.
>> Så alla är tillbaka i denna ordning.
Och nu vill jag göra det här.
Låt oss se Jag vet att jag har åtta siffror här.
Jag kommer att gå vidare och bara medvetet väljer
de minsta delarna.
Höger?
Detta verkar för intuitiv.
Varför jag inte det minsta element, sätta det där det hör hemma,
sedan få nästa minsta element, sätta det där det hör hemma, och bara upprepa.
>> Eftersom intuitivt, som bör fungera också.
Så fyra, det är ett ganska litet antal.
Jag kommer att komma ihåg när det är.
Vänta en minut.
Två är mindre.
Låt mig nu ihåg var två är, och glömma fyra.
Vi tar hand om det senare.
Sex, jag är inte intresserad.
Åtta, jag är inte intresserad av.
En är mitt nya litet antal.
Så jag kommer att komma ihåg var man är.
Tre, inte intresserad.
Sju, inte intresserad.
Fem, inte intresserad.
>> Så utan att falla av scenen i år,
Jag kommer att ta antal en-- och vad var ditt namn igen?
>> ANNAN: Annan.
>> DAVID J. MALAN: Annan.
Och om du kunde gå med mig på början av listan,
Låt oss sätta dig där du hör hemma.
Unfortunately-- vad heter du?
>> STEFAN: Stefan.
>> DAVID J. MALAN: Stefan är i vägen.
Så innan Stefan löser detta problem, vad ska vi göra?
Vad gör vi med Stefan?
>> PUBLIK: [OHÖRBAR].
David J. MALAN: OK.
Så vi kunde göra det.
Vi kunde sorts ta Stefan och hans fyra, och bara lägga den i en variabel
och hålla fast vid det för viss tid,
vilket gör utrymme för nummer ett.
Och det är inte dåligt.
Jag skulle kunna föreslå, varför inte vi bara sätta Stefan här?
Varför kan detta strida mot ett av de idéer vi började
talar om förra gången, förra veckan?
Yeah?
>> PUBLIK: [OHÖRBAR].
>> DAVID J. MALAN: Det finns inget index för det.
Om du tänker på detta, faktiskt, som en array, är detta som negativt,
så det finns inget minne faktiskt här om detta verkligen är en array,
som vi förklarade förra veckan i föreläsningen.
Så vi ska inte göra det.
Vi kan förvara den i en variabel.
>> Eller vet du vad?
Jag hörde någon annan föreslå det.
Vad kan vi göra med Stefan?
Varför inte vi bara vräka honom och satte honom där nummer ett var.
Så om du vill gå dit.
Och faktiskt, är detta en ganska bra lösning.
Nu å ena sidan, jag har typ av gjort problemet värre.
Fyra är nu längre bort varifrån det ska vara.
Det bör vara mot mitten.
>> Men vet du vad?
Det kunde ha varit otur.
Kanske nummer åtta var här.
Och så kanske vi skulle har fått tur,
och sköt åtta närmare slutet.
Så i slutet av dagen, det slags alla jämnar ut.
Vi behöver inte bry sig om fyra.
Allt jag bryr mig om just nu är välja det minsta elementet.
>> Och nu, vad jag ska göra är att glömma nummer ett
permanent, eftersom jag vet att Listan bakom mig nu sorteras.
Så min lista var tidigare storlek åtta.
Nu är det storlek sju.
Så mitt problem är att få mindre, om än linjärt.
Så nu kommer jag att välja nuvarande minsta elementet, två.
Sex, åtta, fyra, tre, sju, fem.
Det var det minsta elementet.
Så vad jag ska göra with-- Vad var ditt namn igen?
>> JOSEPH: Joseph.
>> DAVID J. MALAN: Joseph?
Vi kommer att lämna Josef på plats.
Nu, jag ska låtsas att dessa killar är-- väl,
Jag vet att dessa två är redan sortering.
Låt oss nu fokusera på resten av listan.
Sex är den nuvarande minsta.
Åtta är större.
Fyra är nu aktuell minsta.
Tre är nu den nuvarande minsta.
Och så nu kommer jag att välja tre, som är-- vad heter du igen?
Serena: Serena.
DAVID J. MALAN: Serena, om du kunde ta ditt nummer och swap with--
Kalsang: kalsang.
David J. MALAN: kalsang.
Kom tillbaka, och vi är kommer att byta dem två.
Och nu, låt oss sätta detta på autopilot.
Jag ska gå och lämna det till er killar att välja nästa minsta beståndsdel.
Dun, dun, dun, dun.
Nummer fyra, vad ska du göra?
Utmärkt.
Nu, jag kommer att göra en annan passera.
Dun, dun, dun, dun.
Jag ser fem är den näst minsta.
Nu ska jag ta en annan pass.
Dun, dun, dun, dun.
Sex är den minsta.
God.
Sju är den minsta.
Ingen förändring.
Åtta är den minsta.
Klar.
>> Så vad vi har just gjort av iterativt välja en del efter den andra
är att genomföra något som vi är kommer att formalisera som val slag.
Och det är kanske till och med enklare att förklara,
att bokstavligen allt du vill göra är att bara hålla
gå fram och tillbaka i listan val, nästa minsta elementet,
tills du är klar.
>> Så det är ännu enklare, kanske intuitivt, än sist.
Låt oss försöka en sista.
Om ni kunde återställa er i följande positioner
en sista gång, låt oss se om vi kan inte nu formalisera ett annat tillvägagångssätt.
I själva verket skulle någon ute vilja föreslå
hur annat vi kan gå om att göra detta?
Utan gungade ut slagord eller sortera svar som redan är kända,
bara intuitivt, vad kan vi göra?
>> PUBLIK: [OHÖRBAR].
DAVID J. MALAN: Ja.
Så det finns några bra intuition där.
Bra saker tycks hända hittills i datavetenskap när vi delar
och erövra problemet att dela det i hälften och hälften och hälften.
Och så faktiskt, vi kunde börja göra det.
Och faktiskt, det kommer att bli, vi kommer se, en av våra bästa lösningarna ännu.
Men låt oss återkomma till detta inom kort.
I själva verket kommer vi att göra det lite senare i veckan.
Vad kan vi göra för att lösa det här?
Så alla här är i synes slumpmässig ordning.
Du vet vad?
Hellre än att gå fram och tillbaka, fram och tillbaka, fram och tillbaka
varje gång, känns detta som Jag gör en hel del promenader.
Varför jag inte bara börja på början av listan,
och bara sätta fyra där den hör hemma?
Så låt mig för ett ögonblick anta att min lista är endast denna första elementet.
Är fyra sorteras vid denna tidpunkt, om allt jag bryr mig om är allt här?
Detta är en slags trivialt sant, eller hur?
Liksom förteckning ett nummer, och som nummer fyra är uppenbarligen för sortering.
>> Så låt mig bara föreskriva att denna förteckning sortering.
Men nu har jag resten av denna lista.
Så nu, jag möter två.
Var gör två uppenbarligen hör ihop med avseende på fyra?
Före fyra.
Så vad kan jag göra här?
Vad heter du igen?
>> JOSEPH: Joseph.
>> DAVID J. MALAN: Joseph, om du kunde steg tillbaka
för bara en stund med ditt nummer.
Och nu vad ska Stefan göra här?
Låt oss flytta Stefan hit.
Och nu, låt Joseph komma hit.
Och nu, låt mig hävdar att allt här sorteras.
Så, liknande resultat, men en fundamentalt annorlunda tillvägagångssätt.
Jag har inte ens tittat vad som finns där nere.
Jag håller bara ta elementen eftersom de är överlämnades till mig,
och ta itu med dem.
>> Så nu ser jag nummer sex.
Varifrån kommer nummer sex hör?
Vi har två, fyra, sex.
Exakt var hon är just nu.
Så låt oss lämna det ensam, och nu hävdar att denna del av listan
Nu sorteras.
Och så känns det i grunden annorlunda eftersom jag bara
rör sig genom listan här linjärt, och jag aldrig fördubbling tillbaka.
Ja.
Okej.
Så åtta, där ni hör hemma?
Precis här.
Perfekt.
Så nu en.
Hoppsan.
Det känns som det är kommer att bli dyrt.
Nu, i den tidigare algoritmen, Jag bytte folk.
Så jag skulle sätta honom hela vägen början, men sedan flyttade Joseph.
Men om jag flyttar Joseph, nu vad som kommer att vara fel?
>> Nu, jag har typ av undone-- jag har tagit ett steg framåt och sedan
ett steg tillbaka, för nu Joseph skulle vara i ordning.
Så låt oss göra detta.
Om du kunde ta nummer ett och ett steg tillbaka för ett ögonblick.
Hur kan vi put-- vad var ditt namn igen?
>> ANNAN: Annan.
>> DAVID J. MALAN: Annan på plats?
Vad behöver hända med respekt till två, fyra, sex och åtta?
De behöver alla att skifta.
Så om åtta vill flytta först, sedan sex, sedan fyra, sedan två.
Och sedan Annan, om du skulle vilja komma in här, bra.
Men här, vi har bara sorts betalat ett pris
vid en annan punkt i algoritmen.
Medan förra gången med val sortera och även bubbelsortering,
Jag går tillbaka och framåt, fram och tillbaka,
vilket säkerligen är att lägga upp tidsmässigt, och bokstavligen stegvis.
>> Insättningssortering, först anblicken ser ut som det är
super smartare, eftersom jag bara går långsamt, små förbättringar,
men jag tänker inte detta fram och tillbaka.
Men om någon är verkligen out of order, meddelande
allt arbete jag var bara tvungen att göra.
Jag var tvungen att flytta hälften av listan bara för att göra plats för nummer ett.
Så det är samma belopp arbete hittills det
känns, bara en annan typ av arbete.
>> Låt oss fortsätta.
Så nu vet vi att alla mellan en och åtta sorteras.
Här har jag nummer tre.
Om du gillar att plocka upp nummer tre, ett steg tillbaka ett.
Och vad gör ni behöver göra?
Japp.
Så det är en annan, två, tre steg.
Tre tidsenheter som bara kostar mig, så att tre kan nu passa.
Slutligen sju.
>> Låt oss gå vidare och ha du tar ett steg tillbaka.
Detta kommer bara att kosta oss en tidsenhet, men det är OK.
Och nu, fem kommer att vara lite dyrare.
Om du vill ta ett steg tillbaka.
Vi måste gå åtta, och sju och sex.
Och då alla nu sorteras.
Så en stor hand till våra volontärer här.
Tack så mycket.
>> [Applåder]
>> Tack alla ni.
Tack alla ni.
Så låt oss se nu hur kostsam allt detta var.
Låt oss betrakta kanske enklaste av dessa, bubbelsortering.
Och jag säger enklaste, bara för att Du kan lösa det girigt genom att bara
åtgärda den parvisa problem här.
Fäst den parvisa problemet här, igen och igen
och igen, upprepa så många gånger som du faktiskt behöver.
>> Så visar det sig att med en bubbelsortering, bra,
hur många steg måste jag ta på det första passet av den algoritm?
Jag kanske take-- låt oss see-- en, två, tre, fyra, fem, sex, sju.
Och det finns åtta element här.
Så det är som n minus 1 steg till får från början av listan
till slutet av listan.
>> Men med val sort, minns att jag är välja de element och om igen
och återigen det är minsta, Jag sätter den på plats,
men då är jag inte titta bakom mig igen.
Så jag tycker det är lite mer tydlig då den första gången, kanske jag
måste vidta alla n minus 1 steg att hitta det minsta elementet.
Då ska jag sätta dem på plats, och jag vräka vem var här tidigare.
>> Men då jag inte behöver hålla tittar på detta element,
eftersom jag vet att det är redan den minsta.
Så nu kan jag titta på bara sju element, sedan sex element,
sedan fem elementen, sedan fyra element.
Och så matematiskt, om n är antalet element eller siffror
att vi började med, kan ni tänka er att detta är samma som n minus 1,
plus n minus 2 steg, plus n minus 3 steg,
plus n minus 4 steg, alla ända ner till bara ett steg.
Och jag är på min sista personen.
>> Och om ni minns att en hel del av statistik böcker eller matematiska böcker
har dessa formler på inbundna tillbaka eller framför dem,
det visar sig att denna serie kan uttryckas enklare
som n gånger n minus 1 över 2.
Och det är bra om det inte i spetsen för ditt sinne.
Men det är sant.
Det är bara ett enklare sätt att skriva det.
Och sedan om du tror tillbaka till skolan,
när du bara börja multiplicera saker, detta naturligtvis,
bara n kvadrat minus n dividerat med två.
Allt jag har gjort är att expandera uttrycken där.
Och så låt oss skriva detta lite annorlunda.
Det är n kvadrat delat med 2 minus n / 2.
>> Så återigen, jag är bara slags tillämpa vissa aritmetiska regler där.
Men märker nu att den största termen i detta uttryck, så att säga,
är att n i kvadrat.
Så ja, det är n kvadrat dividerat med två, minus n / 2.
>> Men generellt, om n är kommer att bli en stor värde,
Jag kommer att hävda att n kvadrat kommer att vara den dominerande faktorn.
Det är bara kommer att bli en större bidragsgivare
till det antal steg än n / 2.
Så vad menar jag med det?
Låt oss försöka ett enkelt exempel, även men matten blir lite stor.
>> Så antar att vi hade 1 miljon människor på scen, eller 1 miljon saker
att vi vill sortera.
Låt oss ansluta en miljon i just den formeln
för att se hur många steg det tar totalt att sortera en miljon element med hjälp av säg,
urval slag.
>> Så skulle vi ha samma formel som tidigare.
Jag skulle koppla en miljon, så att jag får en miljon kvadrat delat med 2,
minus en miljon dividerat med två.
Om jag gör det matte i förväg Här har vi 500 miljarder
minus 500 tusen, som ger oss 499.999.500.000,
som är ganska stor.
>> I själva verket, om man jämför nu 499 miljarder, 999 miljoner,
500000 mot vår ursprungliga värde, 500 miljarder, det är så jävla nära.
Höger? n kvadrat dividerat med 2 ger oss-- eller snarare n kvadrat delat med 2
gav oss 500 miljarder.
Det är ganska nära till 499.999.500.000,
det vill säga att subtrahera bort 500.000, eller mer generellt, subtrahera bort
n kvadrat, egentligen inte en big deal.
N kvadrat gör dessa siffror växer riktigt snabbt.
>> Nu är det bara viktigt i den mån som vi, som datavetare,
i allmänhet inte kommer att bry sig så mycket om nyanserna i dessa formler
och exakt vad den exakta svar är.
Vi bryr oss bara det, vet du vad?
Vid slutet av dagen, denna formel är i storleksordningen av n kvadrat.
>> Ja, vi dividera med 2 där.
Ja, vi subtrahera bort n minus 2.
Men i slutet av dagen, termen som verkligen skadar oss och kostar oss
en hel del steg är att fyrkantig sikt.
Och så vad datavetare kommer att i allmänhet göra
är ignorera alla de mindre ordningens termer,
och bara titta på det som bidrar mest till kostnaden.
>> Och det är trevligt, eftersom vi kan nu tala mycket större allmän
om algoritmer, och kan jämföra dem.
Och det faktum att jag är med hjälp av denna O är avsiktligt.
När jag säger i storleksordningen av, jag är specifikt
med hänvisning till något kallade stora O. Och stora O
är en uppgift om att en dator forskare använder för att beskriva
en övre gräns på något.
>> Så om ni säger att en algoritm är i stort O n kvadrat,
som jag föreslog bara en stund sedan, innebär att
att när det gäller sin löpning tid eller dess effektivitet,
Det tar i storleksordningen av n kvadrat steg.
Kanske mer, kanske mindre.
Men det är i storleksordningen n kvadrat.
Och det är den övre gränsen.
Det kommer inte att vara mer smärtsamt än så.
Det kommer inte att vara n kubik, eller 2 till n, eller något mycket större.
Detta är en övre gräns på vad det kostar.
Så med tanke på att, låt oss överväga några exempel.
Och detta är bara en ändlig lista mycket vanliga drifttider
för algoritmer som är tänkt att vara illustrerar några saker vi har
sett redan.
>> Så till exempel, i fallet med val Sortera, vad jag påstår här
är att valet sortera vicepresident tiden är i storleksordningen n i kvadrat.
I värsta fall kommer jag att ha en hel massa slumptal här.
Och som vi såg matematiskt, om jag hålla walking
genom listan genom listan, välja nästa minsta
elementet och om igen, om jag faktiskt skriva ner alla steg
Jag tar som jag föreslog formulaically innan det är i storleksordningen n kvadrat
steg som jag tar.
>> Och det visar sig att bubblan sortera och insättningssortering
är lika långsamt i värsta fall.
Betänk till exempel, insättningssortering, den allra sista algoritm vi behandlat,
som hade oss titta på elementet, och sedan infoga det där det hör hemma.
Och sedan vi tittat på nästa element, och satt in den där det hör hemma.
>> Så överväga bästa möjliga scenario.
Anta att jag hade mina frivilliga ställer upp bokstavligen som detta, ett till åtta,
redan sortering.
Hur många steg är insättningssortering kommer att ta att sortera åtta personer,
om de anländer på scen ser ut så här?
>> Åtta människor redan sortering.
Och jag använder insättningssortering.
Det sista av algoritmer.
Nåväl, låt oss reenact riktigt snabbt.
Så om jag börjar här, jag ser en.
Var ska man tillhör?
Det tillhör just här.
Jag ser två.
Vart tar två hör?
Precis här.
Jag ser tre.
Vart tar tre tillhör?
Precis här.
>> Jag ser fyra.
Precis här.
Fem, sex, sju, åtta.
Det finns ingen anledning att upprepa mig.
Och i så fall hur många steg är att när det gäller n?
Det är i storleksordningen n steg, eller hur? N minus 1.
Men jag tog ett linjärt antal steg, och nu är jag klar.
Så det är bästa fall, dock.
Hur är det värsta fall?
Vilka åtta var borta, och sju var nere,
och ett och två var över här, så att listan verkligen var omvänd?
>> Tja, vad händer faktiskt om detta är numret?
Och vi kommer att göra bara ett par exempel.
Tänk om, ja, nummer åtta är här, och de number-- hoppsan.
Så vad händer om, ja, antalet åtta är hela vägen hit,
och jag använder insättningssortering?
>> OK.
Jag hävdar just nu är det på plats.
Men nu, seven-- vart tar sju gå?
Naturligtvis går det över här.
Så jag måste flytta åtta över en plats.
Nu sex, vart tar det vägen?
Tja, okej.
Nu måste jag flytta åtta över en plats, och sju över en plats,
och sedan jag plopp ner sex.
>> Så första gången det kostar mig en steg för att fixa saker,
då det kostade mig två steg för att fixa saker.
Hur många steg är det kommer att vidta för att åtgärda
saker att sätta fem på rätt plats?
Tre.
För nu har jag flytta en, två, tre.
Hur många steg kommer det att ta att sätta fyra på rätt plats?
4 plus 5, plus 6, plus 7.
>> Och så det är matematiskt identisk med vad vi beskrivits för val slag.
Vi har denna serie det är bara ökar.
1 plus 2 plus 3 plus 4, eller omvänt, 7 plus 6
plus 5 plus 4 lägger upp för dagens ändamål till i storleksordningen n kvadrat.
>> Så låt mig föreskriver också att bubbelsortering är också i n kvadrat.
Eftersom med bubbelsortering, varje gång jag går igenom listan,
Jag tar ungefär hur många steg?
Varje gång jag bokstavligen promenad därifrån till det?
Ungefär n steg.
Men hur många gånger kanske jag måste gå igenom listan?
>> Tja, ungefär n tid.
Kanske n minus 1, men ungefär n gånger.
Tja, varför är det?
Tja, med bubbelsortering, om vi börjar med bubbelsortering,
med listan i värsta möjliga situation, som återigen är helt
bakåt, vad som kommer att hända?
Jag går igenom listan och antal man tillhör hela vägen dit.
>> Men med bubbelsortering, gör hur långt man gå på min första passagen genom listan?
Hur många platser skulle bli han närmare till rätt ställe?
Bara en.
Så om du typ av anledning genom denna, varje gång genom denna algoritm,
Davids tar ungefär n steg.
Men hur många pass genom listan är det
kommer att ta en bubbla till vänster där det hör hemma?
>> Han har att röra sig som, n utrymmen på detta sätt.
Så bara för att göra sorteringen av listan, Jag måste gå fram och tillbaka n gånger.
Och varje gång jag är tittar på n element.
Så gör n saker n gånger i storleksordningen n i kvadrat.
>> Nu får vi se i vissa av shorts som
är inbäddade i CS50 nästa problem set, ett annat tillvägagångssätt på dessa,
men för nu, låt oss bara betrakta några andra drifttider,
särskilt om sorterings som tar lite tid att sjunka in.
Vad är en algoritm som vi har sett redan som tar i storleksordningen n steg?
>> Vad ska ta ett linjärt antal steg som vi har sett så här långt?
Vad är det?
Telefonen katalogsökning.
Den första algoritmen.
Höger?
Där vi är linjärt söka efter Mike Smith?
Verkligen.
Från vecka noll, när jag började vrida en sida i taget,
och jag sa till och med att det var typ av en linjär känsla algoritm
och vi hade att bilden på kartong med raka röda linjen
och den raka gul linje, de som faktiskt var
algoritmer som är i stort O n.
>> Eftersom att hitta Mike Smith i en telefon bok n sidor, i värsta fall,
kan ta mig n steg.
Vad sägs om att ta närvaro?
Ett två tre Fyra Fem Sex.
Vad är körtiden för denna algoritm för att ta närvaro?
Big O n, eftersom i teorin jag måste peka alla i rummet.
>> Nu som en sidoreplik, hur är det andra optimering från vecka noll?
Två, fyra, sex, åtta, 10, 12.
En datavetare skulle inse, vänta en minut,
som är i storleksordningen n dividerat med två steg.
Höger?
Eftersom jag gör två personer åt gången.
Men vi ska ignorera de lägre ordningens termer,
och vi kommer bara att kasta bort klyftan med 2,
och bara säga, stort O n för den algoritm som också.
>> Vad sägs om den här?
Vi ska hoppa över några av dessa, men vad var en algoritm som var loggen av n?
Det tog ungefär log n steg?
Den söndra och härska.
Exakt.
Liksom telefonboken exemplet i vecka noll och tidigare i dag,
där vi delat problemet igen och igen och igen.
Vi drog det på tavlan i veckan noll som en böjd grön linje,
och vi sade att dagen var det en logaritmisk algoritm.
>> Och faktiskt, antalet steg det tar att utföra söndra och härska,
eller binär sökning som vi börjar kalla det, som i telefonboken,
är i storleksordningen av log och steg.
Och detta är lite av en konstig en.
>> Vad tar ett steg, eller mer specifikt
ett konstant antal steg?
Kanske är det två, kanske det är tre, men datavetare bara
förenklas så stor O 1, någon konstant antal steg.
Vad är något du kunde göra det tar ett konstant antal steg?
>> Vad är körtiden för klappar?
Konstant tid.
Höger?
Liksom, vad är gångtid göra något som tar bara en
drift, liksom ut F Hello World.
Det kan sägas vara konstant tid, såvida mindre hörn fallet med tryck F,
Vad kan körtiden utskrifts F faktiskt vara?
Och varför?
Vad är n mätning i så fall?
>> PUBLIK: [OHÖRBAR].
DAVID J. MALAN: Exakt.
Antalet tecken Vi vill skriva ut.
Så det är väldigt sammanhangsberoende.
Idag har vi fokuserat mycket på bokstäver och siffror här på tavlan.
Men det kan också vara tecken i en faktisk sträng.
Så det visar sig att det finns en annan åtgärd som kommer att börja bry sig om,
och det är motsatsen av stora O, så att säga.
>> Det är omega notation.
Medan stora O menar vad är det övre gräns på din gångtid?
Maximalt, hur mycket tid kanske något att ta?
Omega-- ledsen detta håller kommer up-- är motsatsen till det,
varigenom det är en nedre gräns på tid något kan ta.
>> So. till exempel, vad är en algoritm som tar alltid n kvadrat steg?
Tja, en av de algoritmer vi har sett idag, i själva verket kan vara det också.
Urval slag.
Val sort är ganska dumt.
Även om algorithm-- ledsen, även Om arrayen är redan sorterade,
val Sortera kommer att fortsätta att gå igenom listan
att se till att den har den minsta elementet igen och igen och igen.
Och även om du människor i Publiken vet att vänta en minut,
du redan passerat minsta elementet, varvid datorn
vet inte att tills det ser hela vägen igenom listan.
På liknande sätt, en lägre gräns som kan också beaktas
kan vara linjär tid.
>> Hur lång tid tar det att sort n element i bästa
fall genom att använda något som bubbelsortering?
Anta att din lista är redan sortering.
Vi sade bubbelsortering tar på ordningen n kvadrat steg.
Men vad händer om det redan sorteras?
Vad händer om du inser efter en passage genom matrisen
att du har gjort några swappar?
Behöver du fortsätta att göra mer passerar?
>> Nej.
Så en lägre gräns för bubbelsortering kan sägas vara linjär.
Omega n.
Och vi kan titta på andra av dessa också.
Så låt oss ta en snabb titt på bara en visualisering här
att se hur dessa utmärker sig.
Jag kommer att gå här nere i detta sida som är tillgänglig på C50: s hemsida,
men det kommer att bli jobbigt att få arbeta, eftersom den använder en teknik som kallas
Java applets, vilket är en till stor del stöds dessa dagar,
åtminstone genom Chrome och vissa andra.
>> Och låt mig gå vidare och påskynda detta upp och förklara vad som händer.
Detta är en demonstration av bubbla sortera, den första algoritmen som vi tittat på.
Och det är en visualisering av att varje av dessa stänger representerar ett tal.
Ju större baren, desto större numret.
Ju mindre baren, desto mindre antal.
Och vad du kan se visuellt, även även om detta går supersnabbt,
är att den röda stapeln är som jag, promenader och tillbaka åtgärda problem.
Du kan se att de större elementen är sannerligen bubblar upp till höger,
och de mindre elementen bubblar upp till vänster.
Och här nere, om vi faktiskt titta närmare,
vi kan faktiskt räkna antal jämförelser och swappar
som görs.
>> Men i stället, låt oss titta vid den andra algoritmen
vi tittat på tidigare med vår volontärer, val Sortera.
Visuellt har en helt annan effekt.
Men det är, återigen, mycket intuitivt, i att vi fortsätter att välja nästa mindre
element, och vi fick en lite tur.
Det kändes fundamentalt snabbare.
Men om vi sprang det igen och igen och igen med massor av insatsvaror,
skulle vi se att det är verkligen fortfarande i stor O n kvadrat.
>> Låt oss göra en sista här, insättningssortering,
vilket var den tredje algoritmen vi tittat på, och återkallelse
att detta en behandlar element som möter dem,
Men då kanske skift över saker att göra plats,
infoga element där de hör hemma.
>> Och även detta slutar ge slutresultatet. Nu alla tre av dem
kände ganska snabbt.
Och faktiskt, sprang jag dem på en ganska bra klipp.
Men i grund och botten, de är alla ganska hemskt, att vara ärlig.
Alla dessa algoritmer hittills som körs i stora O n kvadrat
ta en hel del tid att köra i slutet.
>> Och faktiskt, kan vi se och anser att detta slutligen
om jag drar upp denna tredje och sista demo.
Detta är en annan visualisering som händer
att visa bubbelsortering till vänster, val Sortera i mitten,
och något, som en av våra handen lyfter tidigare föreslagits,
merge sort till höger.
En söndra och härska strategi till höger.
Och det är i själva verket vad vi är kommer att titta på onsdagen.
Men låt oss tid dessa att löpa parallellt.
Det är ungefär lika många element, alla kör på samma gång.
Bubbelsortering vs val sortera vs merge sort.
>> Nu, de är alla kör i teorin samtidigt.
Processorn körs på samma hastighet, men du
kan känna hur tråkigt det är mycket snabbt kommer att bli,
och hur snabbt när vi injicerar lite vecka
noll algoritmer kan vi påskynda saker.
>> Och nu ska vi jämföra dessa i ett sista formen.
Jag kommer att gå vidare till CS50 hemsida, där
Vi har denna sista länken för idag, där någon på internet
vänligen sätta ihop en video som fångar vad olika sortering
algoritmer låter som.
Detta är insättningssortering.
>> [Pipande]
>> Där du applicera en frekvens baserat på höjden av bar bar.
Detta är bubbelsortering.
>> [Warped pipande]
>> Kommer upp nästa är-- kommande upp nästa är-- val sortera,
där återigen, vi väljer nästa minsta elementet,
och vi kan se det växa från vänster till höger.
>> Merge sort, vår vinnare hittills i dag.
Lägg märke till hur det dela saker i [OHÖRBAR] halv och kvartal.
Gnome sort, som vi inte har talade om, och skapar visuellt
och audally lite av en olika form och ljud.
Gå fram och tillbaka, städa upp saker.
Läs också heapsort På den här killen hemsida.
>> Och det är allt.
Vi kommer att se dig nästa gång.
>> [Whooshing OCH MUSIK]