[MUSIK SPELA] 

PROFESSOR: Okej. Detta är CS50 och det är I slutet av vecka tre. Så vi är här i dag, inte i Sanders Teater, i stället i Weidner Library. Inuti vilken är en studio känd som Hauser Studio, eller ska vi säga Studio H, eller skall Vi säga-- om du gillade det skämtet, det är faktiskt från klasskamrat, Mark, på nätet, som föreslog lika mycket via Twitter. Nu vad är hett om att vara här i en studio är att jag är omgiven av dessa gröna väggar, en grön skärm eller chromakey, så att säga, vilket innebär att CS50: s produktion team, okänt för mig just nu, skulle kunna vara att sätta mig mest var som helst i världen, på gott och ont. 

Nu vad som väntar, problem set två är i dina händer den här veckan, men med problem set tre den kommande veckan, Du kommer att utmanas med den så kallade omgång 15, en gammal partyfavör att du kanske minns mottagande som ett barn som har en hel drös av siffror som kan glida uppåt, nedåt, vänster och höger, och det finns ett gap inom pusslet, i vilken du kan faktiskt dra dessa pusselbitar. I slutändan får du här pussel i vissa semi slumpmässig ordning, och målet är att sortera, uppifrån och ned, vänster till höger, från en hela vägen upp genom 15. 

Tyvärr, genomförandet du har till hands kommer att vara mjukvara baserad, inte fysiskt. Du faktiskt kommer att behöva skriva kod som en student eller användare kan spela 15. Och i själva verket i hacker utgåvan av spelet 15, du kommer att bli en utmaning att genomföra, inte bara spela i denna gamla skolan spel, utan snarare att lösa det, genomföra gud läge så att säga, som faktiskt löser pusslet för människan, genom att ge dem tips, efter ledtråd efter ledtråd. Så mer om det nästa vecka. Men det är vad som väntar. 

För nu påminna om att tidigare i veckan Vi hade denna cliffhanger, om man så vill, varvid det bästa vi gjorde sortering klokt var en övre gräns för stora o n kvadrat. Med andra ord, bubbelsortering, val Sortera, insättningssortering, alla av dem, medan olika i genomförandet, decentraliserade in en n kvadrat kör tid i allra värsta fall. Och vi i allmänhet anta att det värsta fallet för sortering är en som ingångarna är helt bakåt. Och faktiskt, det tog en hel del steg att genomföra vart och ett av dessa algoritmer. 

Nu i slutet av klass minns, jämförde vi bubbelsortering mot val Sortera mot en annan som vi kallade merge sort på den tiden, och jag föreslår att det tar Fördelen med en lektion från vecka noll, söndra och härska. Och på något sätt att uppnå någon form av logaritmisk gångtid slutändan i stället för något det är rent kvadratisk. Och det är inte helt logaritmisk, Det är lite mer än så. Men om du minns från klass, det var mycket, mycket snabbare. Låt oss ta en titt på där vi slutade. 

Bubbelsortering kontra urval sortera kontra merge sort. Nu är alla kör i teori, samtidigt. Processorn körs med samma hastighet. Men du kan känna hur tråkigt detta är mycket snabbt kommer att bli, och hur snabbt, när vi injicerar en bit av vecka noll algoritmer, kan vi snabba upp saker och ting. 

Så märke sort ser fantastisk. Hur kan vi utnyttja det, för att sortera siffror snabbare. Nå, låt oss tänka tillbaka en ingrediens som vi hade tillbaka i vecka noll, som söka efter någon i en telefonbok, och påminna om att pseudokod som vi föreslog, via vilken vi kan hitta någon som Mike Smith, såg lite ungefär så här. 

Nu tar en titt i synnerhet vid linje 7 och 8, och 10 och 11, som inducerar den slingan, där vi höll gå tillbaka till linje 3 igen, och igen, och igen. Men det visar sig att vi kan visa denna algoritm, här i pseudokod, lite mer holistiskt. I själva verket, vad jag letar till här på skärmen, är en algoritm för att söka efter Mike Smith bland några uppsättning sidor. Och faktiskt, vi kunde förenkla denna algoritmen i dessa linjer 7 och 8, och 10 och 11 för att bara säga detta, som jag har lagt fram här i gult. Med andra ord, om Mike Smith är tidigare i boken, vi behöver inte ange steg steg nu hur man ska gå hitta honom. Vi behöver inte ange att gå tillbaka till linje 3, varför vi inte bara i stället, säg, mer generellt, söka för Mike i vänstra halvan av boken. 

Omvänt, om Mike är faktiskt senare i boken, varför inte vi bara citera unquote sökning för Mike i den högra halvan av boken. Med andra ord, varför inte vi bara sorts punt till oss och sade: söka för Mike i det här delmängd av boken, och lämna den till vår befintliga algoritm för att berätta hur man söker efter Mike att vänstra halvan av boken. Med andra ord, vår algoritmen fungerar oavsett om det är en telefonbok med denna tjocklek, i detta tjocklek, eller vilken som helst tjocklek som helst. Så vi kan rekursivt definiera denna algoritm. Med andra ord, på den skärm här är en algoritm för att söka efter Mike Smith bland sidorna i en telefonbok. Så i linje 7 och 10, låt oss bara säga just detta. Och jag använder denna term ett ögonblick sedan, och faktiskt, rekursion är modeord för tillfället, och det är denna process att göra något cyklisk av somehow med hjälp av kod som du redan har, och kalla det igen, och igen, och igen. Nu är det kommer att vara viktigt att vi på något sätt botten ut, och inte göra det oändligt lång. Annars ska vi har verkligen en oändlig loop. Men låt oss se om vi kan låna denna idé av en rekursion, gör något igen och om och om igen, för att lösa sorterings problemet via merge sortera, desto mer effektivt. 

Så jag ger dig merge sort. Låt oss ta en titt. Så här är pseudo, med som vi skulle kunna genomföra sortering, att använda denna algoritm som kallas merge sort. Och det är helt enkelt detta. På ingången av n element, Med andra ord, om du är givet n element och siffror och bokstäver eller vad ingången är, om du har gett n element, om n är mindre än 2, bara tillbaka. Höger? Eftersom om n är mindre än 2, som innebär att min lista över element är antingen av storlek 0 eller 1, och i båda dessa triviala fall listan redan sortering. Om det inte finns någon lista, är det sorteras. Och om det finns en lista över längd 1, är det självklart för sortering. Så algoritmen endast behöver verkligen göra något intressant, om vi har två eller flera element ges till oss. Så låt oss titta på den magiska sedan. Else sortera vänstra halvan av elementen, sedan sortera högra halvan av element, sedan sammanfoga de sorterade halvor. Och vad är typ av sinnet böjning här, är att jag inte riktigt tycks ha sagt något ännu, eller hur? Allt jag har sagt är, få en lista över n element, sortera den vänstra halvan, då rätt halv, sedan sammanfoga de sorterade halvor, men var är den verkliga hemliga sås? Var är algoritmen? Jo det visar sig att dessa två linjer först, typ vänstra halvan av element, och sortera högra halvan av element, är rekursiva samtal, så att säga. 

När allt vid denna tidpunkt, måste jag en algoritm med vilken till sortera en massa element? Ja. Det är rätt här. Det är rätt här på skärmen, och så jag kan använda samma uppsättning steg att sortera den vänstra halvan, jag kan den högra halvan. Och faktiskt, igen, och igen. Så på något sätt eller annat, och vi ska snart se detta, magi merge sort är inbäddad i det allra sista linje, sammanslagning av sorterade halvor. Och det verkar ganska intuitiv. Du tar två halvor, och ni, på något sätt, sammanfoga dem tillsammans, och vi får se här konkret i ett ögonblick. 

Men detta är en komplett algoritm. Och låt oss se exakt varför. Väl antar att vi har gett dessa samma åtta element här på skärmen, en till åtta, men de är i till synes slumpmässig ordning. Och målet till hands är att sortera dessa element. Nå hur kan jag gå om göra det genom att använda, återigen, merge sort, enligt denna pseudo? Och återigen, ingrain detta ditt sinne, för bara ett ögonblick. Det första fallet är ganska trivialt, om det är mindre än 2, bara tillbaka, det finns inget arbete som skall utföras. Så egentligen finns det bara tre åtgärder för att verkligen tänka på. Igen, och igen, jag är kommer att vilja ha att sortera den vänstra halvan, sortera den högra halv, och sedan när deras två halvor är sorterade, Jag vill slå samman dem tillsammans in en sorterad lista. Så ha det i åtanke. 

Så här är den ursprungliga listan. Låt oss behandla detta som en array, som vi började i vecka två, som är en sammanhängande block av minne. I detta fall, innehållande åtta siffror, rygg mot rygg mot rygg. Och låt oss nu tillämpa merge sort. Så jag vill först sortera den vänstra halvan av denna lista, och låt oss därför fokusera på 4, 8, 6, och 2. 

Nu hur gör jag om sortering en lista över storlek 4? Jag måste väl nu överväga sortering vänster om den vänstra halv. Återigen, låt oss spola tillbaka för bara ett ögonblick. Om pseudokod är detta, och jag får åtta element, 8 är betydligt större än eller lika med 2. Så med det första fallet inte gäller. Så för att sortera åtta element, jag först sortera vänstra halvan av element, då jag sorterar den högra halvan, sedan slå ihop jag de två sorterade halvor, var och en av storlek 4. OK. 

Men om du bara har berättat för mig, sortera vänstra halvan, som nu av storlek 4, hur gör jag sorterar vänstra halvan? Tja, om jag har en inmatning av fyra delar, Jag sorterar först vänster två, sedan höger två, och då jag slå ihop dem tillsammans. Så återigen blir det en bit av ett sinne böjning spel här, eftersom du, typ av, måste kom ihåg var du är i berättelsen, men i slutet av dagen, med tanke på valfritt antal element, du först vill sortera vänstra halv, sedan höger halv, sedan sammanfoga dem tillsammans. Låt oss börja göra just detta. Här är ingången till åtta element. Nu är vi tittar på den vänstra halvan här. Hur sorterar jag fyra element? Jo jag först sortera vänstra halvan. Nu hur gör jag sorterar vänstra halvan? Jo jag har fått två delar. Så låt oss sortera dessa två element. 2 är större än eller lika med 2, naturligtvis. Så det första fallet inte är tillämpligt. 

Så jag har nu att sortera vänster halv av dessa två element. Den vänstra halv, naturligtvis, är bara fyra. Så hur gör jag sortera en lista med en del? Nåja, det speciella basfallet där uppe, så att säga, är tillämpligt. 1 är mindre än 2, och min Listan är verkligen storlek 1. Så jag återvänder bara. Jag gör ingenting. Och faktiskt, titta på vad jag har gjort, är fyra redan sortering. Som jag är redan delvis framgångsrik här. 

Nu verkar vara lite dum krav, men det är sant. 4 är en lista över storlek 1. Det är redan för sortering. Det är den vänstra halvan. Nu har jag sorterar den högra halvan. Min ingång är ett element, 8 På samma sätt som redan sortering. Dum, också, men återigen, denna grundläggande princip kommer att tillåta oss att nu bygga ovanpå detta framgångsrikt. 4 sorterade, 8 sorteras nu Vad var det sista steget? Så den tredje och sista steget, någon gång du sorterar en lista, återkallelse, var att slå samman de två halvorna, vänster och höger. Så låt oss göra just detta. Min vänstra halvan är, naturligtvis, 4. Min högra halvan är 8. 

Så låt oss göra detta. Först ska jag fördela lite extra minne, att jag företräder här, som bara en sekundär uppsättning, som är tillräckligt stor för att passa detta. Men du kan tänka dig att utvidga rektangeln hela längden, om vi behöver mer senare. Hur tar jag 4 och 8, och sammanfoga dessa två listor med storlek 1 tillsammans? Även här, ganska enkel. 4 kommer först, sedan kommer 8. För om jag vill sortera vänstra halv, sedan höger halv, och sedan slå ihop dessa två halvor tillsammans, i sorterad ordning, 4 kommer först, sedan kommer 8. 

Så vi verkar vara att göra framsteg, även även om jag inte har gjort något egentliga arbetet. Men kom ihåg var vi befinner oss i berättelsen. Vi tog ursprungligen åtta element. Vi sorterade den vänstra halvan, vilket är 4. Sedan vi sorterade den vänstra halvan av den vänstra halvan, vilket var 2. Och nu kör vi. Vi är klar med detta steg. 

Så om vi har sorteras vänstra halvan av två, nu är vi måste sortera den högra halvan av två. Så den högra halvan av 2 dessa två värden här, 6 och 2. Så låt oss nu ta en ingång storlek 2, och sortera den vänstra halvan, och sedan den högra halv, och sedan slås ihop dem. Nå hur gör jag sortera en lista med storlek 1, innehåller bara antalet 6? Jag är redan gjort. Den förteckningen över storleken 1 sorteras. 

Hur sorterar jag en annan lista över storlek 1, den så kallade högra halv. Jo det är också redan sortering. Antalet 2 är ensam. Så nu har jag två halvor, vänster och Okej, jag måste slå samman dem tillsammans. Låt mig ge mig själv lite extra utrymme. Och satte 2 där, då 6 där, och därigenom sortering denna förteckning, vänster och höger, och slå samman det tillsammans, i slutändan. Så jag är i något bättre form. Jag är inte klar, eftersom klart 4, 8, 2, 6 är inte den slutgiltiga beställning som jag vill. Men jag har nu två listor med storlek 2, att har båda, respektive sorterats. Så nu om du spola tillbaka i ditt sinne öga, där kom det lämnar oss? Jag började med åtta element, så jag sållat det ner till den vänstra halvan av 4, sedan den vänstra halvan av två, och sedan den högra halvan av två, Jag slutade därför sortering vänster halv av 2, och den högra halvan av två, så vad är det tredje och sista steget här? Jag måste gå samman två listor med storlek 2. Så låt oss gå vidare. Och på skärmen här, ge mig lite extra minne, men tekniskt, märker att jag har fick en hel del tomt utrymme där uppe där. Om jag vill vara särskilt effektiva ytor klokt, Jag kunde bara börja flytta elementen fram och tillbaka, topp och botten. Men bara för visuell skärpa, Jag kommer att lägga ner nedan, att hålla saker fin och ren. 

Så jag har två listor med storlek 2. Den första listan har 4 och 8. Den andra listan har 2 och 6. Låt oss slå ihop dem tillsammans i sorterad ordning. 2 naturligtvis kommer först, sedan 4, sedan 6, sedan 8. Och nu verkar vi vara att få någonstans intressant. Nu har jag sorterat hälften av lista, och av en tillfällighet, det är alla jämna nummer, men att är faktiskt bara en tillfällighet. Och jag har nu sorteras vänster hälften, så att det är 2, 4, 6, och 8. Ingenting är i ordning. Det känns som pågår. 

Nu känns det som om jag har pratat evigt nu, så vad återstår att se om detta algoritm är faktiskt mer effektiv. Men vi går igenom det super metodiskt. En dator, naturligtvis, skulle göra det så. Så var är vi? Vi började med åtta element. Jag sorterade den vänstra halvan av fyra. Jag verkar vara klar med det. Så nu nästa steg är att sortera den högra halvan av fyra. Och denna del kan vi gå genom lite mer snabbt, även om du är Välkommen att spola tillbaka eller pausa, bara tänka igenom det på din egen takt, men vad vi har nu är en möjlighet att göra exakt samma algoritm på fyra olika nummer. 

Så låt oss gå vidare och fokusera på den högra halvan, som vi är här. Den vänstra halvan av det högra halv, och nu vänstra halv av den vänstra hälften av det högra halvan, och hur jag sortera en lista med storlek 1 innehåller bara antalet 1? Det är redan gjort. Hur gör jag samma sak för en lista storlek 1 innehåller bara 7? Det är redan gjort. Steg tre för Halv sedan är att slå samman dessa två element till en ny förteckning över storlek 2, 1 och 7. Inte tycks ha gjort allt så mycket intressant arbete. Låt oss se vad som händer härnäst. Jag sorterade bara den vänstra halvan av högra halvan av min original- ingång. Nu ska vi sortera rätt hälften, som innehåller 5 och 3. Låt oss återigen titta på vänster halv, sorteras, högra halv, sorteras, och slå ihop dessa två tillsammans, i någon extra utrymme, 3 kommer först, sedan kommer 5. Och så nu har vi sorterat vänstra halvan av den högra halv av det ursprungliga problemet, och den högra halvan av den högra halv av det ursprungliga problemet. Vad är den tredje och sista steg? Jo för att slå samman de två halvorna. Så låt mig få mig lite extra utrymme, men, återigen, jag skulle kunna vara att använda det lediga utrymme där uppe. Men vi kommer att hålla det enkelt visuellt. Låt mig samman i nu 1, och sedan tre och sedan fem, och sedan 7. Därmed lämnar mig nu med högra halvan av det ursprungliga problemet som är perfekt för sortering. 

Så vad återstår? Jag känner att jag håller säger samma saker igen och igen, men det är reflekterande av Att vi använder rekursion. Processen med att använda en algoritm igen, och igen, på mindre delmängder av det ursprungliga problemet. Så jag har nu en vänster sorteras halv av det ursprungliga problemet. Jag har en rätt sorterad halv av det ursprungliga problemet. Vad är det tredje och sista steget? Åh, det är en sammanslagning. Så låt oss göra det. Låt oss anslå några ytterligare minne, men min Gud, vi kunde sätta det någonstans nu. Vi har så mycket utrymme för oss, men vi kommer att hålla det enkelt. Istället för att gå tillbaka och fram med vår ursprungliga minne, låt oss bara göra det visuellt här nere nedan till slut upp en sammanslagning av vänstra halvan och den högra halvan. 

Så genom att slå samman, vad behöver jag göra? Jag vill ta elementen i ordning. Så titta på den vänstra halvan, Jag ser första siffran är 2. Jag tittar på den högra halvan, Jag ser det första numret är en, så självklart som Antalet vill jag rycka ut, och sätts i första rummet i min slutliga listan? Naturligtvis, en. Nu vill jag ställa samma fråga. På den vänstra halvan, jag har fortfarande fick nummer 2. På höger halv, Jag har siffran 3. Som man vill jag välja? Naturligtvis, nummer 2 och Nu märker kandidaterna är 4 till vänster, 3 på höger sida. Låt oss, naturligtvis välja 3. Nu kandidaterna är 4 på vänster, 5 höger. Vi, naturligtvis, välj 4. 6 till vänster, 5 höger. Vi, naturligtvis, välj 5. 6 till vänster, 7 till höger. Vi väljer 6, och då är vi välja 7, och sedan väljer vi åtta. Voila. 

Så ett stort antal ord senare, vi har sorterat denna lista över åtta element i en förteckning över en till åtta, som är ökande med varje steg, men hur mycket tid gjorde det tar oss att göra det. Jo jag har medvetet lagda saker ut pictorially här, så att vi kan typ av se eller uppskatta divisionen i erövrande som har hänt. 

I själva verket om du tittar tillbaka på spåren, Jag har lämnat alla dessa prickade linjer i platshållare, kan du, typ av, se, i omvänd ordning, om du typ av ser tillbaka i historia nu, min ursprungliga listan är naturligtvis storlek 8. Och sedan tidigare, var jag arbetar med två listor med storlek 4, och sedan fyra listor över storlek 2, och sedan åtta listor med storlek 1. 

Så vad gör detta, typ av, påminna dig om? Jo, faktiskt, något av de algoritmer vi ve tittat på hittills där vi klyftan, och dela och dela, hålla med saker igen, och igen, resulterar i denna allmänna idé. Och så det finns något logaritmisk pågår här. Och det är inte riktigt log n, men det finns en logaritmisk komponent vad vi just har gjort. 

Låt oss nu överväga hur det egentligen är. Så log n, återigen var en stor gångtid, när vi gjorde något liknande binär sökning, som vi nu kallar det, klyftan och erövra strategi via vilken vi hittade Mike Smith. Nu tekniskt. Det är log bas 2 av n, även men i de flesta matematiska klasser, 10 är vanligtvis basen att du tar. Men datavetare nästan alltid tänka och tala i termer av basen 2, så vi vanligtvis bara säga logg över n, i stället för log bas 2 av n, men de är exakt en och Samma i världen av datorn vetenskap, och som en sidoreplik, det finns en konstant faktor skillnaden mellan de två, så det är omtvistad ändå, för mer formella skäl. 

Men nu, vad vi bryr om är detta exempel. Så låt oss inte bevisa med gott exempel, men stone använda ett exempel på siffrorna till hands som en sanity check, om ni så vill. Så tidigare formeln var log bas 2 n, men vad är n i detta fall. Jag hade n originalnummer, eller 8 av ursprungliga antalet specifikt. Nu har det gått lite tag, men jag är ganska Se till att log bas 2 av värdet 8 är 3, och faktiskt, vad är trevligt om det är att 3 är exakt det antal gånger att du kan dela upp en lista med längden 8 igen, och igen, och igen, tills du är kvar med listor över bara storlek 1. Höger? 8 går till 4, går till 2, går till ett, och det är reflekterande av just detta bild vi hade bara en stund sedan. Så lite förnuft kontrollera om var logaritmen är faktiskt inblandad. 

Så nu, vad är inblandad här? n. Så märker att varje tid jag dela listan, om än i omvänd ordning i historien här, jag var fortfarande gör n saker. Det sammanslagning steg krävs att Jag rör var och en av numren, För att dra det till dess lämplig plats. Så även om höjden av detta diagram är storlek log n n eller 3, specifikt, med andra ord, Jag gjorde tre divisioner här. Hur mycket arbete gjorde jag horisontellt längs denna tabell varje gång? 

Tja, jag gjorde n stegen arbete, för om jag har fick fyra element och fyra element, och jag måste slå samman dem tillsammans. Jag behöver gå igenom dessa fyra och dessa fyra, i slutändan att slå ihop dem tillbaka in i åtta delar. Om omvänt Jag har åtta fingrar hit, som jag inte, och åtta fingers-- sorry-- Om jag har fick fyra fingrar hit, som jag gör, fyra fingrar hit, som jag gör, då det är samma exempel som förut, om jag gör har åtta fingrar men i Totalt, som jag kan, typ av, gör. Jag kan exakt göra här, då kan jag säkert slå ihop alla dessa listor storlek 1 tillsammans. Men jag har verkligen att se vid varje element exakt en gång. Så höjden av denna process är log n, bredden av denna process, så att säga, är n, så vad vi verkar att ha, i slutändan, är en gångtid av storlek n gånger log n. 

Med andra ord, delade vi listan, log n gånger, men varje gång vi gjorde det, hade vi beröra var och en av elementen för att slå ihop dem alla tillsammans, vilket N steg, så vi har n gånger log n, eller som en datavetare skulle säga, asymptotiskt, vilket skulle vara den stora ord för att beskriva den övre bunden på en gångtid, Vi kör i en stor o av log n tid, så att säga. 

Nu är betydande, eftersom ihåg vad de löpande tiderna var med bubbelsortering och urval sortera och insättningssortering, och även några andra som finns, n kvadrat var där vi var på. Och du kan typ av se det här. Om n kvadrat är uppenbarligen n gånger n, men här har vi n gånger log n, och vi vet redan från vecka noll, att log n, den logaritmiska, är bättre än något linjärt. När allt kommer omkring, minns bilden med den röda och den gula och de gröna linjerna som vi drog, den grön logaritmisk linjen var mycket lägre. Och därför, mycket bättre och snabbare än de raka gula och röda linjer, n gånger log n är verkligen bättre än n gånger n eller n kvadrat. 

Så verkar vi ha identifierat en algoritm merge sortera som körs i mycket snabbare tid, och faktiskt, det är därför, tidigare i veckan, då Vi såg att tävlingen mellan bubbla sort, val av sort, och sammanfoga sort, merge sort verkligen, verkligen vunnit. Och faktiskt, vi inte ens vänta för bubbelsortering och val Sortera att avsluta. 

Nu ska vi ta en annan pass på detta, från en något mer formell perspektiv, precis fall resonans detta bättre än högre diskussionsnivå. Så här är algoritmen igen. Låt oss fråga oss själva, vad gångtid är detta algoritmer olika steg? Låt oss dela upp det i den första fallet och det andra fallet. IF och annat i IF fallet Om n är mindre än 2, bara tillbaka. Känns som konstant tid. Det är, typ av, liksom två steg, Om n är mindre än 2, sedan tillbaka. Men som vi sade på måndagen, konstant tid, eller stora o av 1, kan vara två steg, tre steg, även 1000 steg. Det viktiga är att det är ett konstant antal steg. Så gula markerade pseudo Här körs i, vi kallar det, konstant tid. Så mer formellt, och vi kommer att-- detta kommer att vara i vilken utsträckning vi formalisera denna rätt now-- T n, körtiden för ett problem som tar n things som indata, lika stor o av en, Om n är mindre än 2. Så det är villkorat av att. Så för att vara tydlig, IF n är mindre än 2, har vi en mycket kort lista, sedan drifttid, T från n, där n är 1 eller 0, i detta mycket specifika fall, det bara kommer att vara konstant tid. Det kommer att ta ett steg, två steg, vad som helst. Det är ett fast antal steg. 

Så saftigt delen måste ju vara i det andra fallet i pseudo. Else fallet. Sortera vänstra halvan av element, sortera rätt hälften av element, slå samman sorterade halvor. Hur lång tid tar var och en av dessa åtgärder ta? Tja, om driften tid att sortera n element är, låt oss kalla det mycket generiskt, T av n, sedan sortera vänster halv av elementen är, typ av, som att säga, T n dividerat med 2, och på liknande sätt att sortera den högra halv element är, typ av, som att säga, T n delas 2, och sedan sammanslagning av de sorterade halvor. Tja, om jag har några antal element här, liknande fyra, och något antal av element här, som fyra, och jag måste slå samman var och en av dessa fyra i, och var och en av dessa fyra i en efter den andra, så att i slutändan har jag åtta element. Det känns som det är stor o av n steg? Om jag har n fingrar och var och en av dem måste slås samman på plats, det är som en annan n steg. 

Så faktiskt formulaically, Vi kan uttrycka detta, om än lite läskigt i början blick, men det är något som fångar just denna logik. Gångtiden, T n, om n är större än eller lika med 2. I detta fall, ELSE fallet, T är av n dividerad med två, plus T från N delat med 2, plus stora o n, en del linjär antal steg, kanske exakt n, kanske 2 gånger n, men det är ungefär, ordning n. Så att är också hur vi kan uttrycka detta formulaically. Nu skulle du inte vet detta om du har spelat in det i ditt sinne, eller slå upp det i baksidan av en lärobok, som kanske har lite fusklapp i slutet, men detta är verkligen kommer att ge oss en stor o n log n eftersom återfall som du ser här på skärmen, om du faktiskt gjorde det, med ett oändligt antal exempel, eller om du gjorde det formulaically, skulle du se att detta, eftersom denna formel själv är rekursiv, med t från n över något till höger, och t n vänsterkanten, kan detta faktiskt skall uttryckas, i slutändan, så stor taget om n log n. Om inte övertygad, det är bra för nu, bara ta på tro, att det är, faktiskt, vad som återkommande leder till, men detta är bara lite mer av en matematisk metod att titta vid gångtid merge sort baserat på dess pseudokod ensam. 

Nu ska vi ta en bit av en paus från allt detta, och ta en titt på en vissa tidigare senator, som kanske ser lite bekant, som satte sig ner med Googles Eric Schmidt, för en tid sedan, för en intervju på scenen, framför en hel drös människor, talar slutligen om ett ämne, det är ganska nu bekant. Låt oss ta en titt. 

Eric Schmidt: Nu 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. PRESIDENT OBAMA: Rätt. Eric Schmidt: Och du är kommer att göra [OHÖRBAR] nu. Det är också svårt att få jobb på Google. PRESIDENT OBAMA: Rätt. 

Eric Schmidt: Vi har frågor, och vi ber våra kandidater frågor, och detta är från Larry Schwimmer. 

PRESIDENT OBAMA: OK. 

Eric Schmidt: Vad? Ni tror att jag skojar? Det är rätt här. Vad är det mest effektiva sättet att sortera en miljon 32 bitars heltal? 

PRESIDENT OBAMA: Well-- Eric Schmidt: Ibland kanske jag är ledsen, maybe-- PRESIDENT OBAMA: Nej, nej, nej, nej, nej, jag think-- Eric Schmidt: Det är inte det-- PRESIDENT OBAMA: I tror, ​​jag tror att bubblan sort skulle vara fel väg att gå. Eric Schmidt: Kom igen. Som berättade detta? OK. Jag gjorde inte datavetenskap on-- 

PRESIDENT OBAMA: Vi har fick våra spioner där. PROFESSOR: Okej. Låt oss lämna bakom oss nu teoretisk värld av algoritmer i asymptotiska analys därav, och återgå till vissa ämnen från vecka noll och ett, och start att ta bort några stödhjul, om du vill. Så att du verkligen förstår i slutändan från grunden, vad är pågår under huven, när du skriva, kompilera och exekvera program. Minns i synnerhet att detta var den första C-programmet vi tittat på, en kanonisk, enkelt program av slag, relativt sett, där det skrivs, Hello World. Och minns att jag sa, processen att källkoden går igenom är just detta. Du tar din källkod, passera det genom en kompilator, som Clang, och ut kommer objektkod, att kan se ut så här, nollor och ettor att datorns processor, central behandlingsenhet eller hjärnan, i slutändan förstår. 

Det visar sig att det är en lite av en förenkling, att vi är nu i en ståndpunkt att retas isär att förstå vad som verkligen varit pågår under huven varje gång du kör Klang, eller mer generellt, varje gång du gör ett program, med hjälp av fabrikat och CF 50 IDE. Framför allt sånt detta först genereras, när du först kompilera ditt program. Med andra ord, när man ta din källkod och kompilera den, vad är först matas ut av klang är något som kallas montering kod. Och i själva verket ser det precis som här. 

Jag körde ett kommando på kommandoraden tidigare. Klang streck kapital s hej.c, och detta skapade en fil för mig kallade hello.s, inuti vilken var exakt dessa halter, och lite mer ovan och lite mer nedan, men jag har lagt mediebranschen information här på skärmen. Och om du tittar noga ser du åtminstone ett par bekanta sökord. Vi har huvud upptill. Vi har printf ner i mitten. Och vi har också hallå världen bakstreck n inom citationstecken ner nedan. 

Och allt annat här är instruktionerna mycket låg nivå att datorns processor förstår. CPU instruktioner som rör minne runt, att last strängar från minnet, och i slutändan, print saker på skärmen. Nu vad som händer men efter denna assemblerkod genereras? I slutändan, tror du verkligen, fortfarande genererar objektkod. Men de åtgärder som verkligen har pågått under huven ser lite mer om detta. Källkod blir assemblerkod, som sedan blir objektkod, och de avgörande orden här är att, när du kompilerar källkoden, ut kommer assemblerkod, och sedan när du monterar din assemblerkod, ut kommer objektkod. 

Nu Clang är super sofistikerad, som en hel del kompilatorer, och det gör alla dessa steg tillsammans, och det gör inte nödvändigtvis utgång någon mellanliggande filer som du även kan se. Det sammanställer bara saker, vilket är den allmänna term som beskriver hela denna process. Men om du verkligen vill att vara särskilt, det finns mycket mer händer där liksom. 

Men låt oss också tänka nu att även det super enkelt program, hej.c, kallas en funktion. Det kallas printf. Men jag ville inte skriva printf, ja, som kommer med c, så att säga. Det är en funktion återkallelse som är deklarerats i standard io.h, som är en header-fil, som är ett ämne vi faktiskt dyka in i mer djup snart. Men en header-fil är typiskt åtföljs med en kod fil, källkod fil, så ungefär som det finns standard io.h. 

Någon gång sedan, någon, eller någons, skrev också en fil som heter standard io.c i vilket den faktiska definitioner, eller implementeringar av printf, och klasar av andra funktioner, faktiskt skrivs. Så med tanke på att om vi överväga att ha Här till vänster, hej.c, att när sammanställt, ger oss hello.s, även om Clang inte bry besparing på en plats Vi kan se det, och att assemblerkod blir monteras hello.o, vilket är faktiskt standardnamnet med tanke på när du kompilera källkod koda till objektkod, men är inte helt redo att köra det ännu, eftersom ytterligare ett steg måste ske, och har pågått under de senaste få veckor, kanske okänt för dig. 

Specifikt någonstans i CS50 IDE, och detta, också kommer att vara lite av en förenkling för ett ögonblick, Det finns, eller var på en tid, en fil som heter standard io.c, att någon sammanställs i standard io.s eller motsvarande, att någon sedan monteras till standard io.o, eller det visar sig i en något annorlunda fil format som kan ha en annan fil förlängning helt och hållet, men i teori och begrepps exakt dessa åtgärder måste ske i någon form. Vilket betyder att, som nu när jag skriver ett program, hej.c, som bara säger hej världen, och jag använder någon annans kod som printf, som en gång var på en tid, i en fil som heter standard io.c, sedan på något sätt måste jag ta min objekt kod, mina ettor och nollor, och den personens objekt kod, eller ettor och nollor, och på något sätt koppla ihop dem till en slutlig fil, som heter hello, att har alla nollor och de från min huvudsakliga funktion, och alla nollor och sådana för printf. 

Och faktiskt är det sista process kallas, länka din objektkod. Vars utgång är en körbar fil. Så i rättvisans namn, vid slutet av dagen, ingenting har förändrats sedan vecka ett, när vi började sammanställa program. I själva verket allt detta har varit händer under huven, men nu är vi i en position där vi kan faktiskt retas isär dessa olika steg. Och faktiskt, i slutet av dagen, är vi fortfarande vänster med nollor och ettor, som är faktiskt ett bra segue nu till en annan kapacitet C, som Vi har inte behövt utnyttja troligen hittills känd som bitvisa operatörer. Med andra ord, hittills, när vi har behandlas med data i C eller variabler i C, vi har haft saker som tecken och flyter och ins och längtar och dubblar och liknande, men alla av dessa är åtminstone åtta bitar. Vi har aldrig ännu inte kunnat manipulera enskilda bitar, även om en individuell bit, vi vet, kan representera en 0 och en en. Nu visar det sig att i C, du kan få tillgång till enskilda bitar, om du känner till syntaxen, som man kan komma åt dem. 

Så låt oss ta en titt vid bitvisa operatörer. Så bilden här är några symboler som vi har, typ av, sorts, sett förut. Jag ser ett et-tecken, ett vertikalt bar, och några andra också, och påminna om att et-et-tecken är något vi har sett förut. Den logiska AND, där du har två av dem tillsammans, eller den logiska ELLER operatör, där du har två vertikala streck. Bitvisa operatörer, som vi kan se arbeta på bitar individuellt, bara använda en enda et-tecken, en enda vertikal bar, cirkumflex symbol kommer nästa, den lilla tilde, och sedan vänster fäste vänster fäste, eller höger konsol höger konsol. Var och en av dessa har olika betydelser. 

I själva verket, låt oss ta en titt. Låt oss gå old school idag och användning en pekskärm från förr, känd som en whiteboard. Och detta whiteboard kommer att tillåta oss att uttrycka några ganska enkla symboler, eller snarare några ganska enkla formler, att vi kan sedan slutligen hävstångseffekt, i syfte att få tillgång till enskilda bitar inom ett C-program. Med andra ord, låt oss göra detta. Låt oss först tala för en ögonblick om et-tecken, vilket är bitvis och operatör. Med andra ord är detta en operatör som tillåter mig att ha en vänster variabel typiskt, och en höger variabel, eller ett enskilt värde, att om vi OCH dem tillsammans, ger mig ett slutresultat. Så vad menar jag? Om det i ett program, har du en variabel som lagrar en av dessa värden, eller låt oss hålla det enkelt, och bara skriva ut nollor och ettor individuellt, här är hur et-operatören arbetar. 0 ampersand 0 kommer att motsvara 0. Nu varför är det? 

Det är mycket lik Booleska uttryck, att vi har diskuterat hittills. Om du tror trots allt, 0 är falskt, 0 är falsk, falsk och falskt är, som vi har diskuterat logiskt, också falskt. Så vi får 0 här. Om du tar 0-tecken 1, väl det också, kommer att bli 0, eftersom det för detta vänster för uttryck att vara sant eller ett, det skulle behöva vara sant och sant. Men här har vi falskt och sann, eller 0 och 1. Nu igen, om vi har en et-tecken 0, det också, kommer att vara 0, och om vi har en et-tecken 1, Slutligen har vi en 1 bit. Så med andra ord, vi gör inte något intressant med denna operatör ännu, denna et-operatör. Det är bitvis och operatör. Men dessa är ingredienserna via vilken vi kan göra intressanta saker, som vi snart kommer att se. 

Låt oss nu titta på bara en enda lodrätt streck över här till höger. Om jag har en 0 bit och jag ELLER det med, bitvis OR operatör, en annan 0 bit, som kommer att ge mig 0. Om jag tar en 0 bit och OR det med 1 bit, så jag kommer att få en. Och i själva verket bara för klarhet, låt mig gå tillbaka, så att mina vertikala streck inte förväxlas med 1: or. Låt mig skriva alla min 1 är lite mer tydligt, så att vi nästa ser, om jag har en 1 eller 0, som kommer att vara en 1, och om jag har en 1 eller en som, Även kommer att bli en 1. Så du kan se logiskt att de yttersta randområdena operatör fungerar mycket annorlunda. Detta ger mig 0 ELLER 0 ger mig 0, men varannan kombination ger mig en. Så länge jag har en 1 i formel, är resultatet kommer att bli en. 

Till skillnad från OCH operatör, et-tecknet, bara om jag har två 1: or i ekvation, jag faktiskt få en 1. Nu finns det några andra operatörer samt. En av dem är lite mer engagerade. Så låt mig gå vidare och radera detta för att frigöra utrymme. Och låt oss ta en titt på cirkumflex symbol, för bara ett ögonblick. Detta är typiskt en tecken kan du skriva på tangentbordet innehav Skift och då ett av numren ovanpå din USA tangentbord. 

Så det här är den exklusiva OR operatör, exklusivt ELLER. Så vi såg bara operatorn OR. Detta är den exklusiva OR-opera. Vad är egentligen skillnaden? Nåväl låt oss titta bara på formeln och använda detta som ingredienser i slutändan. 0 XOR 0. Jag kommer att säga är alltid 0. Det är definitionen av XOR. 0 XOR 1 kommer att bli en. 1 XOR 0 kommer att vara 1, och en XOR 1 kommer att bli? Fel? Eller höger? Jag vet inte. 0. Nu vad som händer här? Väl tänka på namn på denna operatör. Exklusiv ELLER, så som den Namn, Typ av, antyder, Svaret kommer bara att bli 1 om ingångarna är exklusiva, uteslutande annorlunda. Så här ingångarna är samma, så utsignalen är 0. Här ingångarna är samma, så utsignalen är 0. Här är utgångarna är annorlunda, de är exklusiva, och så produktionen är ett. Så det är mycket lik OCH det är mycket likt, eller snarare det är mycket lik OR, men endast i ett exklusivt sätt. Denna en inte längre är en 1, eftersom vi har två 1: or, och inte uteslutande, bara en av dem. Okej. Vad händer med de andra? Väl tilde, under tiden, är faktiskt trevligt och enkelt, tack och lov. Och detta är en unär operatör, vilket innebär det appliceras på endast en ingång, en operand, så att säga. Inte en vänster och en höger. Med andra ord, om du tar tilde av 0, kommer svaret vara det motsatta. Och om du tar tilde 1, den svar kommer det att vara det motsatta. Så tilde operatören ett sätt att förneka en bit, eller vända en bit från 0 till ett, eller en till 0. 

Och det lämnar oss slutligen med bara två sista operatörer, den så kallade vänsterskift, och s.k. högerskift operatör. Låt oss ta en titt på hur de arbetet. Den vänstra skift operatör skrivna med två fästvinklar som detta, fungerar på följande sätt. Om min ingång, eller min operand, till vänster skift operatör är helt enkelt en 1. Och jag då tala om för datorn att vänster skift som en, säger sju platser, Resultatet är som om jag ta det ett, och flytta den sju platser över till vänster, och som standard, vi kommer att anta att utrymmet till höger kommer att vara stoppade med nollor. Med andra ord, en vänster skift 7 går att ge mig att 1, följt av 1, 2, 3, 4, 5, 6, 7 nollor. Så på ett sätt, och hjälper dig att ta ett litet antal som 1, och tydligt gör det mycket mycket, mycket större på detta sätt, men vi faktiskt kommer att se mer smarta metoder för det i stället, liksom, 

Okej. Det var allt för vecka tre. Vi kommer att se dig nästa gång. Detta var CS50. 

[MUSIK SPELA] 

TALARE 1: Han var på snack bar äta en hot fudge fruktglass. Han hade hela ansiktet. Han bär den choklad som ett skägg TALARE 2: Vad gör du? TALARE 3: Hmmm? Va? 

TALARE 2: Har du bara double dip? Du doppade dubbla chipet. TALARE 3: Ursäkta mig. TALARE 2: Du doppade chip, du tog en tugga, och du doppade igen. TALARE 3: TALARE 2: Så det är som att sätta hela din mun mitt i dip. Nästa gång du tar ett chip, bara doppa det en gång, och avsluta det. 

TALARE 3: Vet du vad, Dan? Du doppa det sätt som du vill att doppa. Jag ska doppa det sätt som jag vill att doppa.