[Musik spiller] 

PROFESSOR: Okay. Dette er CS50, og det er i slutningen af ​​ugen tre. Så vi er her i dag, ikke i Sanders Teater, i stedet i Weidner Bibliotek. Inderside er et studie kendt som Hauser Studio, eller skal vi sige Studio H, eller skal vi say-- hvis du har nydt at joke, det er faktisk fra klassekammerat, Mark, online, der foreslog så meget via Twitter. Nu, hvad er cool om være her i et studie er, at jeg er omgivet af disse grønne vægge, en grøn skærm eller chromakey, så at sige, hvilket betyder, at CS50 s produktion team, ukendt for mig lige nu, kunne være at sætte mig mest overalt i verden, for bedre eller værre. 

Nu, hvad der ligger forude, problem sæt to er i dine hænder for denne uge, men med problemet sæt tre i den kommende uge, vil du blive udfordret med den såkaldte omgang 15, en gammel part favor, at du måske huske at modtage som et barn, der har en hel flok af numre, som kan glide op, ned, venstre og højre, og der er én hul inden puslespillet, hvori du kan faktisk skubbe disse puslespilsbrikker. I sidste ende du modtager denne puslespil i nogle semi tilfældig rækkefølge, og målet er at sortere det, top til bund, venstre til højre, fra en hele vejen op gennem 15. 

Desværre, gennemførelse vil du have ved hånden vil være software baseret, ikke fysisk. Du faktisk nødt til at skrive kode med som en studerende eller bruger dåse spille spillet på 15. Og i virkeligheden, i hacker udgave af spillet på 15, vil du være en udfordring at gennemføre, ikke bare at spille i denne gamle skole spil, men snarere løsningen af det, gennemføre gud tilstand, så at sige, der rent faktisk løser puslespillet for den humane, ved at give dem tip, efter tip, efter tip. Så mere om det i næste uge. Men det er, hvad der ligger forude. 

For nu huske, at tidligere i denne uge vi havde denne cliffhanger, hvis du vil, hvorved det bedste, vi gjorde sortering klogt var en øvre grænse for store o n potens. Med andre ord, boble sortere, udvælgelse sortere, indsættelse sortere, dem alle, selvom de er forskellige i deres gennemførelse, overdrages til en n kvadreret kører tid i værste fald. Og vi generelt antager, at det værste tilfælde til sortering er en, der dine input er helt bagud. Og ja, det tog et par skridt at gennemføre hver af disse algoritmer. 

Nu i slutningen af ​​klassen tilbagekaldelse, vi sammenlignet boble sortere mod valg Sorter mod en anden at vi kaldte mergesort dengang, og jeg foreslår, at det tager fordel af en lektion fra uge nul, dividere og erobre. Og en eller anden måde at opnå en form for logaritmisk køretid sidste ende, i stedet for noget det er rent kvadratisk. Og det er ikke helt logaritmisk, det er lidt mere end det. Men hvis du husker fra klassen, Det var meget, meget hurtigere. Lad os tage et kig på, hvor vi slap. 

Bubble sortere versus udvælgelse sortere versus mergesort. Nu er de alle kører i teori, på samme tid. CPU kører ved samme hastighed. Men du kan føle, hvordan kedelige dette er meget hurtigt ved at blive, og hvor hurtigt, når vi injicere lidt af uge nul algoritmer, kan vi fremskynde tingene op. 

Så mark slags ser fantastisk. Hvordan kan vi udnytte det, for at sortere tal hurtigere. Jamen så lad os tænke tilbage en ingrediens, som vi havde igen i uge nul, nemlig søger efter en person i en telefonbog, og minde om, at pseudokode, som vi foreslog, via hvilken vi kan finde en som Mike Smith, kiggede lidt noget som dette. 

Nu tage et kig i særdeleshed på linje 7 og 8, og 10 og 11, som inducerer, at loop, hvorved vi holdt gå tilbage til linje 3 igen og igen, og igen. Men det viser sig, at vi kan se denne algoritme, her i pseudokode, lidt mere holistisk. Faktisk hvad jeg søger på her på skærmen, er en algoritme til at søge efter Mike Smith blandt nogle sæt sider. Og ja, kunne vi forenkle denne algoritme i disse linjer 7 og 8, og 10 og 11 til blot sige dette, som jeg har præsenteret her i gult. Med andre ord, hvis Mike Smith er tidligere i bogen, Vi behøver ikke at angive trin for skridt nu, hvordan at gå finde ham. Vi behøver ikke at angive at gå tilbage til linje 3, hvorfor vi ikke bare stedet, sige, mere generelt, søge efter Mike i venstre halvdel af bogen. 

Omvendt, hvis Mike er faktisk senere i bogen, hvorfor vi ikke bare citere citat slut søgning til Mike i højre halvdel af bogen. Med andre ord, hvorfor vi ikke bare slags punt til os selv at sige, søge efter Mike i denne delmængde af bogen, og overlade det til vores eksisterende algoritme til at fortælle os hvordan du søger efter Mike i at venstre halvdel af bogen. Med andre ord, vores algoritme fungerer uanset om det er en telefonbog af denne tykkelse, af denne tykkelse eller nogen som helst tykkelse. Så vi kan rekursivt definerer denne algoritme. Med andre ord, om skærmen her, er en algoritme til at søge efter Mike Smith blandt siderne i en telefonbog. Så på linje 7 og 10, lad os bare sige præcis det. Og jeg bruger dette udtryk et øjeblik siden, og faktisk, rekursion er buzzword for nu, og det er denne proces for at gøre noget cyklisk ved en eller anden måde bruge kode, som du allerede har, og kalder det igen, og igen og igen. Nu det vil være vigtigt at vi på en måde bunden ud, og ikke gør det uendelig lang. Ellers vil vi har faktisk en uendelig løkke. Men lad os se, om vi kan låne denne idé af en rekursion, at gøre noget igen og igen og igen, at løse den sortering problemet via merge Sorter, desto mere effektivt. 

Så jeg giver dig mergesort. Lad os tage et kig. Så her er pseudokode, med som vi kunne gennemføre sortering, ved hjælp af denne algoritme kaldes mergesort. Og det er ganske enkelt dette. På input af n elementer, med andre ord, hvis du er givet n elementer og tal, og breve eller hvad input er, hvis du er givet n elementer, hvis n er mindre end 2, blot tilbage. Højre? For hvis n er mindre end 2, at betyder, at min liste over elementer enten størrelse 0 eller 1, og i begge disse trivielle tilfælde, listen er allerede sorteret. Hvis der ikke er nogen liste, er det ordnet. Og hvis der er en liste over længde 1, er det naturligvis sorteres. Så algoritmen kun behøver at virkelig gøre noget interessant, hvis vi har to eller flere elementer givet til os. Så lad os se på det magiske dengang. Else sortere den venstre halvdel af elementerne, derefter sortere højre halvdel af elementer, derefter flette de sorterede halvdele. Og hvad er form for sindet bøjning her, er, at jeg ikke rigtig synes at have fortalt dig noget endnu, ikke? Alt, hvad jeg har sagt er, givet en liste over n elementer, sortere den venstre halvdel, derefter den højre halvdel, derefter fusionere de sorterede halvdele, men hvor er den egentlige hemmelige sauce? Hvor er den algoritme? Jamen det viser sig, at de to linjer første, sortere venstre halvdel af elementer, og sortering højre halvdel af elementer, er rekursive kald, så at sige. 

Efter alt, på dette tidspunkt, har jeg en algoritme med at sortere en hel masse elementer? Ja. Det er lige her. Det er lige her på skærmen, og så jeg kan bruge den samme sæt af trin at sortere venstre halvdel, som jeg kan højre halvdel. Og ja, igen og igen. Så en eller anden måde, og vi vil snart se dette, den magiske af mergesort er indlejret i det meget endelige linje, sammenlægning af de sorterede halvdele. Og det forekommer temmelig intuitiv. Du tager to halvdele, og du, en eller anden måde, flette dem sammen, og vi vil se denne konkret i et øjeblik. 

Men dette er en komplet algoritme. Og lad os se præcis hvorfor. Nå antage, at vi er givet disse samme otte elementer her på skærmen, en gennem otte, men de er i tilsyneladende tilfældig rækkefølge. Og målet ved hånden er at sortere disse elementer. Godt, hvordan kan jeg gå om gør det ved hjælp igen, mergesort, som pr denne pseudokode? Og igen, ingrain dette i dit sind, for bare et øjeblik. Det første tilfælde er temmelig trivielt, hvis det er mindre end 2, bare tilbage, er der ingen arbejde der skal gøres. Så virkelig er der bare tre skridt til virkelig huske. Igen og igen, jeg er vil ønsker at have at sortere venstre halvdel, sortere højre halvdel, og derefter en gang deres to halvdele er sorteret, Jeg vil flette dem sammen i en sorteret liste. Så holder det i tankerne. 

Så her er den oprindelige liste. Lad os behandle dette som et array, som vi begyndte at i uge to, som er en sammenhængende blok hukommelse. I dette tilfælde indeholder otte numre, ryg mod ryg mod ryg. Og lad os nu anvende mergesort. Så jeg først vil sortere den venstre halvdel af denne liste, og lad os derfor fokusere på 4, 8, 6 og 2. 

Nu hvordan kan jeg gå om sortering en liste over størrelse 4? Jeg må godt nu overveje sortering venstre for den venstre halvdel. Igen, lad os spole tilbage for et øjeblik. Hvis pseudokode er det, og jeg fik otte elementer, 8 er klart større end eller lig med 2. Så med det første tilfælde ikke finder anvendelse. Så for at sortere otte elementer, jeg først sortere den venstre halvdel af elementer, så jeg sortere den højre halvdel, så jeg flette de to sorterede halvdele, hver med størrelsen 4. OK. 

Men hvis du lige har fortalt mig, sortere venstre halvdel, som nu er i størrelse 4, hvordan kan jeg sortere venstre halvleg? Tja, hvis jeg har en input af fire elementer, Jeg først sortere venstre to, så den højre to, og så vil jeg flette dem sammen. Så igen, bliver det en smule af et sind bøjning spil her, fordi du, slags, er nødt til at huske, hvor du er i historien, men i slutningen af ​​dagen, givet nogen række elementer, du først ønsker at sortere venstre halvdel, derefter den højre halvdel, derefter flette dem sammen. Lad os begynde at gøre netop dette. Her er input af otte elementer. Nu er vi kigger på den venstre halvdel her. Hvordan kan jeg sortere fire elementer? Jamen jeg først sortere venstre halvdel. Nu hvordan kan jeg sortere venstre halvleg? Jamen jeg har fået to elementer. Så lad os sortere disse to elementer. 2 er større end eller svarende til 2, selvfølgelig. Så det første tilfælde ikke finder anvendelse. 

Så nu har jeg til at sortere venstre halvdelen af ​​disse to elementer. Den venstre halvdel, selvfølgelig, er kun 4. Så hvordan får jeg sorterer en liste med et element? Nå nu, at særlige base case op toppen, så at sige, finder anvendelse. 1 er mindre end 2, og min Listen er faktisk størrelse 1. Så jeg bare vende tilbage. Jeg kan ikke gøre noget. Og ja, se på, hvad jeg har gjort, er 4 allerede sorteret. Ligesom jeg er allerede delvis succes her. 

Nu, synes slags dum at kræve, men det er sandt. 4 er en liste over størrelse 1. Det er allerede ordnet. Det er den venstre halvdel. Nu jeg sortere højre halvdel. Mit input er et element, 8 Ligeledes allerede sorteret. Dum, også, men igen, dette grundlæggende princip kommer til at give os mulighed for nu at bygge øverst på denne succes. 4 sorteret, 8 sorteres, nu hvad var det sidste skridt? Så det tredje og sidste trin, som helst gang du sortere en liste, tilbagekaldelse, var at fusionere de to halvdele, venstre og højre. Så lad os gøre netop dette. Min venstre halvdel er selvfølgelig, 4. Min højre halvdel er 8. 

Så lad os gøre det. Først vil jeg tildele nogle ekstra hukommelse, at jeg vil repræsentere her, som blot en sekundær matrix, der er stor nok til at passe dette. Men du kan forestille dig at udvide dette rektangel hele længden, hvis vi har brug for mere senere. Hvordan tager jeg 4 og 8, og flette disse to lister med størrelse 1 sammen? Også her temmelig simpel. 4 kommer først, så kommer 8. Fordi hvis jeg ønsker at sortere venstre halvdel, derefter den højre halvdel, og derefter fusionere de to halvdele sammen i sorteret orden, 4 kommer først, så kommer 8. 

Så vi synes at gøre fremskridt, selv selvom jeg ikke har gjort noget egentlige arbejde. Men huske, hvor vi er i historien. Vi oprindeligt tog otte elementer. Vi sorteret den venstre halvdel, hvilket er 4. Derefter sorteres vi venstre halvdel af den venstre halvdel, som var 2. Og her går vi. Vi er færdig med dette skridt. 

Så hvis vi har ordnet det venstre halvdel af 2, nu er vi nødt til at sortere højre halvdel af 2. Så højre halvdel af 2 disse to værdier her, 6 og 2. Så lad os nu tage et input af størrelse 2, og sortere den venstre halvdel, og derefter den højre halvdel, og derefter flette dem sammen. Godt, hvordan kan jeg sorterer en liste over størrelse 1, indeholder kun nummer 6? Jeg er allerede gjort. Denne liste over størrelse 1 sorteres. 

Hvordan kan jeg sortere en anden liste over størrelse 1, den såkaldte højre halvdel. Godt det også allerede er sorteret. Det nummer 2 er alene. Så nu har jeg to halvdele, venstre og ret, jeg har brug for at flette dem sammen. Lad mig give mig nogle ekstra plads. Og sætte 2 derinde, derefter 6 derinde, hvorved sortering denne liste, venstre og højre, og sammenlægning det sammen, i sidste ende. Så jeg er i lidt bedre form. Jeg er ikke færdig, fordi klart 4, 8, 2, 6 er ikke den endelige bestilling, som jeg ønsker. Men jeg har nu to lister med størrelse 2, at har begge henholdsvis blevet sorteret. Så nu, hvis du spole tilbage i dit sind s øjet, hvor har der forlader os? Jeg startede med otte elementer, så jeg skåret det ned til den venstre halvdel af 4, derefter den venstre halvdel af 2, og derefter den højre halvdel af 2, Jeg er færdig, derfor, sortering venstre halvdelen af ​​2 og den højre halvdel af 2, så hvad er den tredje og sidste trin her? Jeg er nødt til at smelte sammen to lister med størrelse 2. Så lad os gå videre. Og på skærmen her, giver mig nogle ekstra hukommelse, dog teknisk set, mærke til, at jeg har fik en hel masse tom plads op øverst der. Hvis jeg ønsker at være særligt effektiv plads klogt, Jeg kunne bare begynde at bevæge elementerne frem og tilbage, top og bund. Men bare for visuel klarhed, Jeg har tænkt mig at sætte den ned under, at holde tingene pæn og ren. 

Så jeg har fået to lister med størrelse 2. Den første liste har 4 og 8. Den anden liste har 2 og 6. Lad os flette dem sammen i sorteret orden. 2 naturligvis kommer først, derefter 4 og derefter 6, derefter 8. Og nu synes vi at være at få et sted interessant. Nu har jeg ordnet halvdelen af liste, og tilfældigvis er det alle de lige numre, men er, ja, bare en tilfældighed. Og jeg har nu sorteres venstre halvdelen, således at det er 2, 4, 6 og 8. Intet er ude af drift. Der føles som fremskridt. 

Nu føles det som jeg har talt evigt nu, så hvad er stadig uvist, om dette algoritme er faktisk mere effektiv. Men vi går igennem det super metodisk. En computer, naturligvis, ville gøre det sådan. Så hvor er vi? Vi startede med otte elementer. Jeg sorteret den venstre halvdel af 4. Jeg synes at ske med det. Så nu det næste skridt er at sortere højre halvdel af 4. Og denne del, vi kan gå gennem lidt mere hurtigt, selvom du er velkommen til at spole tilbage eller pause, bare tænke igennem det på dit eget tempo, men hvad Vi har nu en mulighed for at gøre nøjagtig samme algoritme på fire forskellige numre. 

Så lad os gå videre og fokusere på den højre halvdel, som vi er her. Den venstre halvdel af denne højre halvdel, og nu venstre halvdel af den venstre halvdelen af ​​denne højre halvdel, og hvordan kan jeg sorterer en liste over størrelse 1 kun indeholder nummer 1? Det er allerede gjort. Hvordan gør jeg det samme for en liste størrelse 1 indeholdende kun 7? Det er allerede gjort. Trin tre for denne halve derefter er at fusionere disse to elementer i en ny liste over størrelsen 2, 1 og 7. Synes ikke at have gjort alt at meget interessant arbejde. Lad os se, hvad der sker næste. Jeg har lige ordnet den venstre halvdel af højre halvdel af min oprindelige indgang. Lad os nu sortere ret halvdelen, der indeholder 5 og 3. Lad os igen se på venstre halvdelen, sorteret, højre halvdel, sorteret, og flette de to sammen, ind i nogle ekstra plads, 3 kommer først, så kommer 5. Og så nu, har vi sorteret de venstre halvdel af den højre halvdel af det oprindelige problem, og den højre halvdel af den højre halvdel af det oprindelige problem. Hvad er den tredje og sidste trin? Nå at fusionere de to halvdele sammen. Så lad mig få mig nogle ekstra plads, men igen, I kunne være ved hjælp af denne overskydende plads op øverst. Men vi kommer til at holde det nemt visuelt. Lad mig fusionere i nu 1, og derefter 3 og derefter 5, og derefter 7. Derved forlader mig nu med højre halvdel af det oprindelige problem der er perfekt ordnet. 

Så hvad der er tilbage? Jeg føler, at jeg holder siger samme ting igen og igen, men det er reflekterende af faktum, at vi bruger rekursion. Processen med at bruge en algoritme igen og igen, på mindre delmængder af det oprindelige problem. Så jeg har nu en venstre sorteres halvdelen af ​​det oprindelige problem. Jeg har ret sorterede halvdel af det oprindelige problem. Hvad er den tredje og sidste skridt? Åh, det er fletning. Så lad os gøre det. Lad os afsætte nogle ekstra hukommelse, men min Gud, vi kunne sætte det overalt nu. Vi har så meget plads til rådighed for os, men vi vil holde det enkelt. I stedet for at gå tilbage og frem med vores oprindelige hukommelse, lad os bare gøre det visuelt hernede nedenfor, at slutte op sammenlægning af venstre halvdel og højre halvdel. 

Så ved at fusionere, hvad skal jeg gøre? Jeg ønsker at tage de elementer i orden. Så ser på den venstre halvdel, Jeg ser det første tal er 2. Jeg ser på den højre halvdel, Jeg ser det første nummer er 1, så selvfølgelig som nummer ønsker jeg at plukke ud, og sætte først i min endelige liste? Selvfølgelig 1. Nu vil jeg bede om, at samme spørgsmål. På venstre halvdel, jeg har stadig fik nummer 2. På den højre halvdel, Jeg har fået nummer 3. Hvilken en skal jeg vælge? Selvfølgelig nummer 2 og nu mærke til de kandidater, er 4 til venstre, 3 til højre. Lad os naturligvis vælge 3. Nu kandidaterne er 4 på venstre, 5 til højre. Vi naturligvis vælge 4. 6 til venstre, 5 til højre. Vi naturligvis vælge 5. 6 til venstre, 7 til højre. Vi vælger 6, og så er vi vælge 7, og vælg derefter vi 8. Voila. 

Er således et stort antal ord senere, vi har sorteret denne liste over otte elementer i en liste med en gennem otte, der er stigende med hvert trin, men hvor meget tid gjorde det tage os at gøre det. Jamen jeg har med vilje lagte ting ud billedligt her, så vi kan slags se eller værdsætter division i erobre, der er blevet sker. 

Faktisk, hvis man ser tilbage på kølvandet, Jeg har efterladt alle disse stiplede linjer i pladsholdere, kan du, slags, se i omvendt rækkefølge, hvis du slags se tilbage i historie nu, min oprindelige liste er naturligvis af størrelsen 8. Og så tidligere, var jeg beskæftiger sig med to lister med størrelse 4, og derefter fire lister over størrelse 2, og derefter otte lister over størrelse 1. 

Så hvad gør dette, slags, minde dig om? Nå, ja, nogen af de algoritmer, vi har så på hidtil hvor vi kløft, og dividere, og dividere, holde have tingene igen, og igen, resulterer i denne generelle idé. Og så er der noget logaritmisk foregår her. Og det er ikke helt log over n, men der er en logaritmisk komponent til det, vi lige har gjort. 

Lad os nu overveje, hvordan der rent faktisk er. Så log n, igen var en stor køretid, når vi gjorde noget lignende binær søgning, som vi nu kalder det, kløften og erobre strategi via som vi fandt Mike Smith. Nu teknisk. Det er totalslogaritmen 2 n, selv men i de fleste matematiske klasser, 10 er normalt i bunden, som du antager. Men dataloger næsten altid tænker og taler om bunden 2, så vi generelt bare sige log over n, i stedet for log basis 2 af n, men de er nøjagtigt én og samme i verden af ​​computeren videnskab, og som en sidebemærkning, der er en konstant faktor Forskellen mellem de to, så det er omstridt alligevel, for mere formelle grunde. 

Men for nu, hvad vi bekymrer om, er dette eksempel. Så lad os ikke bevise ved eksempel, men på det mindste bruge et eksempel på tallene ved hånden som en tilregnelighed check, hvis du vil. Så tidligere formlen var totalslogaritmen 2 af n, men hvad der er n i dette tilfælde. Jeg havde n originale numre, eller 8 af oprindelige antal specifikt. Nu er det blevet lidt stykke tid, men jeg er temmelig sikker på, at bunden 2 log af værdien 8 er 3, og ja, hvad er rart om der er at 3 er nøjagtigt det antal gange at du kan opdele en liste af længde 8 igen og igen, og igen, indtil du er tilbage med lister over bare størrelse 1. Højre? 8 går til 4, går til 2, går til 1, og det er reflekterende af netop dette billede, vi havde bare et øjeblik siden. Så lidt fornuft tjek på, hvor logaritmen er faktisk involveret. 

Så nu, hvad der ellers er involveret her? n. Så mærke til, at hver tid jeg opdele listen, omend i omvendt rækkefølge i historien her, var jeg stadig gør n ting. Det fusionerende trin krævede, at Jeg rører hver et af de numre, for at skubbe den ind dens passende placering. Så selvom højden af ​​denne diagrammet er af størrelsen log n af n eller 3, specifikt, med andre ord, Jeg gjorde tre divisioner her. Hvor meget arbejde gjorde jeg vandret langs dette skema hver gang? 

Nå, jeg gjorde n trin arbejde, fordi hvis jeg har fik fire elementer og fire elementer, og jeg har brug for at flette dem sammen. Jeg har brug for at gå gennem disse fire og disse fire, i sidste ende til at flette dem tilbage til otte elementer. Hvis omvendt I got otte fingre herovre, hvilket jeg ikke gør, og otte fingers-- sorry-- Hvis jeg har fik fire fingre herovre, som jeg gør, fire fingre herovre, som jeg gør, så det er det samme eksempel som før, hvis jeg gør har otte fingre men i alt, som jeg kan, slags, gør. Jeg kan netop gøre her, så jeg kan helt sikkert flette alle disse lister størrelse 1 sammen. Men jeg bestemt nødt til at se på hvert element præcis én gang. Så højden af ​​denne proces er log n, bredden af ​​denne proces, så at sige, er n, så hvad vi synes at have, i sidste ende, er en køretid på størrelse n gange log n. 

Med andre ord, vi delt listen, log n gange, men hver gang vi gjorde det, vi havde at røre hver enkelt af elementerne for at flette dem alle sammen, hvilket var n skridt, så vi har n gange log n, eller som en datalog ville sige, asymptotisk, som ville være stort ord at beskrive den øvre bundet på en køretid, vi kører i en stor o af log n tid, så at sige. 

Nu er dette er signifikant, fordi huske, hvad de kører tider var med boble sortere, og udvælgelse sortere og indsættelse sortere, og endda et par andre, der findes, n kvadreret var, hvor vi var på. Og du kan, slags, se denne her. Hvis n kvadreret er naturligvis n gange n, men her har vi n gange log n, og vi ved allerede fra uge nul, det log n, den logaritmiske, er bedre end noget lineær. Efter alt, husker billedet med det røde og det gule og de grønne linjer, som vi drog, den grøn logaritmisk linje var meget lavere. Og derfor meget bedre og hurtigere end de lige gule og røde linjer, n gange log n er faktisk bedre end n gange n, eller n potens. 

Så vi synes at have identificeret en algoritme merge slags, der kører i meget hurtigste tid, og faktisk, det er derfor, tidligere i denne uge, da vi så, at konkurrencen mellem boble sortering, udvælgelse sortere, og flette sortere, mergesort virkelig, virkelig vundet. Og ja, vi ikke engang vente til boble sortere og udvælgelse sortere at færdiggøre. 

Lad os nu tage en anden pass på dette, fra en lidt mere formelle perspektiv, bare i tilfælde, det genlyd bedre end højere diskussion niveau. Så her er algoritmen igen. Lad os spørge os selv, hvad køretiden er af denne algoritmer forskellige trin? Lad os opdele det i den første sagen og det andet tilfælde. IF og andet i IF tilfælde Hvis n er mindre end 2, blot tilbage. Føles som konstant tid. Det er, sådan, som to trin, Hvis n er mindre end 2, derefter vende tilbage. Men som vi sagde i mandags, konstant tid, eller store o på 1, kan være to trin, tre trin, selv 1.000 trin. Det afgørende er, at det er et konstant antal trin. Så den gule fremhævet pseudokode her kører i, vi vil kalde det, konstant tid. Så mere formelt, og vi vil at-- dette vil være i hvilket omfang vi formalisere denne ret nu-- T n, køretiden for et problem der tager n somethings som input, lig stor o af en, Hvis n er mindre end 2. Så det er betinget af det. Så for at være klar, hvis n er mindre end 2, har vi en meget kort liste, så køretiden, T n, hvor n er 1 eller 0, i denne meget specifikke tilfælde, det bare at gå at være konstant tid. Det kommer til at tage en trin, to skridt, uanset hvad. Det er et fast antal trin. 

Så den saftige del må da være i det andet tilfælde i pseudokode. ELSE sag. Sorter venstre halvdel af elementer, sortere højre halvdelen af ​​elementer, flette sorterede halvdele. Hvor lang tid tager hver af disse trin tage? Tja, hvis driften tid til at sortere n elementer er, lad os kalde det meget generisk, T n, derefter sortering venstre halvdelen af ​​elementerne er, sådan, som at sige, T n divideret med 2, og tilsvarende sortering højre halvdel elementer er, sådan, som at sige, T n delt 2, og derefter sammenlægning de sorterede halvdele. Tja, hvis jeg har fået nogle antal elementer her, ligesom fire, og et tal elementer her, ligesom fire, og jeg er nødt til at fusionere hver af disse fire i, og hver af disse fire i én efter den anden, således at i sidste ende har jeg otte elementer. Det føles som det er stort o af n trin? Hvis jeg har fået n fingre og hver af dem skal flettes på plads, det er ligesom en anden n trin. 

Så ja formulaically, Vi kan udtrykke dette, omend lidt skræmmende ved første øjekast, men det er noget der fanger netop denne logik. Køretiden, T n, hvis n er større end eller lig med 2. I dette tilfælde ELSE tilfælde er T n divideret med 2, plus T N divideret med 2, plus store o af n, nogle lineær antal trin, måske præcis n, måske 2 gange n, men det er groft, orden n. Så det også, er, hvordan vi kan udtrykke denne formulaically. Nu vil du ikke vide dette, medmindre du har optaget det i dit sind, eller slå det op i bagsiden af ​​en lærebog, at kunne have lidt snyde ark i slutningen, men dette er faktisk kommer til at give os en stor o af n log n, fordi gentagelse, der du ser her på skærmen, hvis du rent faktisk gjorde det ud, med et uendeligt antal eksempler, eller du gjorde det formulaically, ville du se, at dette, fordi denne formel selv er rekursiv, med t n over noget til højre, og t for nanoteknologi over til venstre, kan dette faktisk udtrykkes, i sidste ende, så store go af n log n. Hvis ikke overbevist, det er bøde for nu, bare tage på tro, at det er, ja, hvad det gentagelse fører til, men det er bare lidt mere af en matematiske tilgang til at kigge på køretiden for mergesort baseret på dens pseudokode alene. 

Lad os nu tage lidt af en pause fra alt dette, og tage et kig på en visse tidligere senator, der ser måske lidt bekendt, der sad ned med Googles Eric Schmidt, for nogen tid siden, til et interview på scenen, foran en hel flok af mennesker, taler i sidste ende om et emne, der er temmelig nu velkendte. Lad os tage et kig. 

Eric Schmidt: Nu senator, du er her hos Google, og jeg kan lide at tænke på formandskab som en jobsamtale. Nu er det svært at få et job som præsident. Præsident Obama: Right. Eric Schmidt: Og du er vil gøre [uhørligt] nu. Det er også svært at få et job hos Google. Præsident Obama: Right. 

Eric Schmidt: Vi har spørgsmål, og vi beder vores kandidater spørgsmål, og denne er fra Larry Schwimmer. 

Præsident Obama: OK. 

Eric Schmidt: Hvad? Du fyre tror jeg kidding? Det er lige her. Hvad er den mest effektive måde at sortere en million 32 bit heltal? 

Præsident Obama: Well-- Eric Schmidt: Nogle gange, måske er jeg ked af, maybe-- Præsident Obama: Nej, nej, nej, nej, nej, jeg tror-- Eric Schmidt: Det er ikke det-- Præsident Obama: Jeg tror, ​​jeg tror, ​​boblen sortering ville være den forkerte vej at gå. Eric Schmidt: Kom nu. Hvem fortalte ham det? OK. Jeg gjorde ikke datalogi on-- 

Præsident Obama: Vi har fik vores spioner derinde. PROFESSOR: Okay. Lad os efterlade os nu teoretiske verden af ​​algoritmer i asymptotiske analyse deraf, og vende tilbage til nogle emner fra uge nul og én, og starte at fjerne nogle uddannelse hjul, hvis du vil. Så du virkelig forstår i sidste ende fra jorden op, hvad er foregår under kølerhjelmen, når du skrive, kompilere, og udføre programmer. Husk især, at dette var det første C-program vi kiggede på, en kanonisk, simpelt program slags, relativt set, hvor, udskriver, Hello World. Og husker, at jeg sagde, at processen denne kildekode går gennem er netop dette. Du tager din kildekode, pass det gennem en compiler, ligesom Dunk, og ud kommer objektkode, at kunne se sådan ud, nuller og ettaller at computerens CPU, centrale behandlingsenhed eller hjerne, i sidste ende forstår. 

Det viser sig, at der er en lidt af en oversimplificering, at vi er nu i en position til at drille hinanden at forstå, hvad der virkelig har været foregår under emhætten hver gang du kører Klang, eller mere generelt, hver gang du laver et program, hjælp Foretag og CF 50 IDE. Især ting som dette genereres først, når du først kompilere dit program. Med andre ord, når man tage din kildekode og kompilere det, hvad er først blive udsendt ved Dunk er noget kendt som samling kode. Og i virkeligheden er det ser ud præcis som dette. 

Jeg løb en kommando ved kommandolinjen tidligere. Klang Dash kapital s hello.c, og dette skabte en fil for mig kaldte hello.s, inden i hvilken var nøjagtigt disse indhold og lidt mere ovenfor og lidt mere nedenfor, men jeg har lagt den juiciest information her på skærmen. Og hvis man ser nøje, vil du se mindst et par velkendte søgeord. Vi har vigtigste øverst. Vi har printf ned i midten. Og vi har også goddag verden backslash n i anførselstegn ned nedenfor. 

Og alt andet i her er instruktioner meget lavt niveau at computerens CPU forstår. CPU instruktioner, der bevæger hukommelse omkring, at belastning strenge fra hukommelsen, og i sidste ende, udskrive ting på skærmen. Nu, hvad der sker, selvom efter denne forsamling kode er genereret? I sidste ende, du gør, ja, stadig generere objektkode. Men de skridt, der har virkelig stået på under hætten se lidt mere som denne. Kildekode bliver forsamling kode, som så bliver objektkode, og de operative ord her er at, når du kompilere din kildekode, ud kommer forsamling kode, og derefter når du samler din samling kode, ud kommer objektkode. 

Nu Dunk er super sofistikeret, som en masse compilere, og det gør alle disse trin sammen, og det gør ikke nødvendigvis output nogen mellemliggende filer, som du selv kan se. Det bare samler ting, som er den generelle betegnelse, beskriver hele denne proces. Men hvis du virkelig ønsker at være særlig, der er meget mere foregår der. 

Men lad os også overveje nu, at selv at super simpelt program, hello.c, kaldes en funktion. Det opfordrede printf. Men jeg skrev ikke printf, ja, der kommer med C, så at sige. Det er en funktion, tilbagekaldelse, der er erklæret i standard io.h, som er en header fil, som er et emne, vi vil faktisk dykke mere i dybden inden længe. Men en header fil er typisk ledsaget ved en kode-fil, kildekode-fil, så meget gerne der findes standard io.h. 

Engang siden, nogen, eller læserens, skrev også en fil kaldet standard io.c, i som den faktiske definitioner, eller implementeringer af printf, og klaser af andre funktioner, er faktisk skrevet. Så givet, at hvis vi overveje at have her til venstre, hello.c, at når kompileret, giver os hello.s, selv om Dunk ikke generer besparelse på et sted vi kan se det, og det samling kode bliver samlet i hello.o, som er faktisk standardnavnet givet, når du kompilere kilde kode til objektkode, men er ikke helt klar til at udføre det endnu, fordi endnu et skridt skal ske, og har været tilfældet i de sidste par uger, måske ukendt for dig. 

Specielt et sted i CS50 IDE, og dette, vil også være lidt af en oversimplificering for et øjeblik, der er, eller var på et tidspunkt, en fil kaldet standard io.c, at nogen samlet i standard io.s eller tilsvarende, at nogen derefter samles i standard io.o, eller det viser sig i en lidt anderledes fil format, der kan have en anden fil forlængelse helt, men i teori og begrebsmæssigt, præcis disse skridt skulle ske i en eller anden form. Hvilket vil sige, at nu når jeg skriver et program, hello.c, der bare siger, hej verden, og jeg bruger en andens kode ligesom printf, som engang var på en tid, i en fil kaldet standard io.c, så en eller anden måde jeg nødt til at tage min objektkode, mine nuller og ettaller, og at personens objekt kode, eller nuller og ettaller, og på en måde linke dem sammen i en sidste fil, kaldet goddag, at har alle de nuller og dem fra min vigtigste funktion, og alle de nuller og dem for printf. 

Og ja, det sidste proces er kaldes, der forbinder dit objekt kode. Hvis udgang er en eksekverbar fil. Så i retfærdighed, på slutningen af ​​dagen, intet har ændret sig siden uge en, når vi begyndte kompilering programmer. Faktisk har alt dette været sker under kølerhjelmen, men nu er vi i en position hvor vi kan faktisk drille hinanden disse forskellige trin. Og ja, i slutningen af dagen, vi er stadig venstre med nuller og ettaller, som er faktisk en stor segue nu til en anden evne C, der vi har ikke haft til at udnytte sandsynligvis til dato, kendt som bitvise operatører. Med andre ord, hidtil, når som helst vi har behandlet data i C eller variabler i C, vi har haft ting som chars og flåd og ins og længes og doubler og lignende, men alle disse er mindst otte bits. Vi har endnu aldrig været i stand til manipulere individuelle bits, selv om en individuel bit, vi ved, kan udgøre en 0 og en 1. Nu viser det sig, at i C, du kan få adgang til individuelle bits, hvis du kender syntaksen, med til at få ram på dem. 

Så lad os tage et kig ved bitvise operatører. Så afbilledet her er et par symboler, vi har, sådan, en slags, set før. Jeg ser en ét-tegn, en lodret bar, og nogle andre samt, og minde om, at tegnet tegnet er noget, vi har set før. Den logiske og operatør, hvor du har to af dem sammen, eller logisk OR operatør, hvor du har to lodrette stænger. Bitvise operatører, som vi vil se operere på bits individuelt, bare bruge en enkelt ét-tegn, et enkelt lodret bar, indsætningstegn symbol kommer næste, den lille tilde, og derefter til venstre beslag venstre konsol eller højre beslag til højre beslag. Hver af disse har forskellige betydninger. 

Faktisk, lad os tage et kig. Lad os gå gamle skole i dag, og brug en touch skærm fra gårsdagens, kendt som et hvidt bord. Og denne hvide bord kommer til at give os at udtrykke nogle temmelig simple symboler, eller rettere nogle temmelig simple formler, at vi kan så i sidste ende gearing, med henblik på at få adgang til de enkelte bits inden for et C-program. Med andre ord, lad os gøre det. Lad os først tale om en øjeblik om tegnet, som er den bitvise OG operatør. Med andre ord er dette en operatør, der giver mulighed mig at have en venstre variabel typisk, og en højre variabel, eller en individuel værdi, at hvis vi OG dem sammen, giver mig et endeligt resultat. Så hvad gør jeg mener? Hvis der i et program, har du en variabel der lagrer en af ​​disse værdier, eller lad os holde det simpelt, og bare skrive nuller og ettaller individuelt, her er hvordan det tegnet operatør fungerer. 0 0 tegnet vil lig med 0. Nu hvorfor er det? 

Det er meget lig Booleske udtryk, at vi har diskuteret hidtil. Hvis du tror trods alt 0 er falsk, 0 er falsk, falsk og falsk er, som vi har diskuteret logisk, også er falsk. Så vi får 0 her. Hvis du tager 0-tegn 1, Det er også, kommer til at være 0, da denne venstre udtryk til at være sandt eller 1, det vil være nødvendigt at være sandt og rigtigt. Men her har vi falske og sandt, eller 0 og 1. Nu igen, hvis vi har en ét-tegn 0, at også kommer til at være 0, og hvis vi har en ampersand 1, endelig har vi en 1 bit. Så med andre ord, vi ikke gør noget interessant med denne operator lige nu, denne tegnet operatør. Det er den bitvise OG operatør. Men disse er ingredienserne via hvilken vi kan gøre interessante ting, som vi snart vil se. 

Lad os nu se på det helt enkelt lodret streg over her til højre. Hvis jeg har en 0 bit og jeg Eller det med, den bitvise ELLER operatør, en anden 0 bit, der kommer til at give mig 0. Hvis jeg tager en 0 bit og OR det med en 1 bit, så jeg har tænkt mig at få 1. Og i virkeligheden, bare for klarhed, lad mig gå tilbage, så mine lodrette stænger ikke forveksles med 1 s. Lad mig omskrive alle min 1 er lidt mere klart, således at vi næste se, om jeg har en 1 eller 0, der kommer til at være en 1, og hvis jeg har en 1 eller 1, der, Også vil være en 1. Så du kan se logisk, at OR operatør opfører sig meget forskelligt. Det giver mig 0 eller 0 giver mig 0, men hver anden kombination giver mig 1. Så længe jeg har en 1 i formel, bliver resultatet kommer til at være 1. 

I modsætning til AND operatøren, tegnet, kun hvis jeg har to 1'er i ligning, jeg faktisk få en 1 ud. Nu er der et par andre operatører så godt. En af dem er lidt mere involveret. Så lad mig gå videre og slette dette for at frigøre noget plads. Og lad os tage et kig på den indskudsmærke symbol, for bare et øjeblik. Dette er typisk en tegn, du kan skrive på dit tastatur beholdning Shift og derefter et af numrene oven din amerikanske tastatur. 

Så dette er den eksklusive ELLER operatør, eksklusive OR. Så vi har lige set operatoren OR. Dette er den eksklusive OR operatøren. Hvad er egentlig forskellen? Jamen så lad os bare se på formlen, og bruge denne som ingredienser i sidste ende. 0 XOR 0. Jeg har tænkt mig at sige, er altid 0. Det er definitionen af ​​XOR. 0 XOR 1 vil være 1. 1 XOR 0 vil være 1, og 1 XOR 1 kommer til at være? Forkert? Eller højre? Jeg ved ikke. 0. Nu, hvad der foregår her? Nå tænke på navn på denne operatør. Eksklusiv OR, så som navn, type, antyder, svaret er kun vil være en 1, hvis input er eksklusive, udelukkende anderledes. Så her indgangene er samme, så produktionen er 0. Her indgangene er samme, så produktionen er 0. Her er de udgange er forskellige, de er eksklusive, og så produktionen er 1. Så det er meget lig Og det er meget ens, eller det er snarere meget lig OR, men kun i en eksklusiv måde. Dette er ikke længere en 1, fordi vi har to 1 s, og ikke udelukkende, kun et af dem. Okay. Hvad med de andre? Nå tilde, i mellemtiden, er faktisk nice og enkel, heldigvis. Og det er en unary operatør, hvilket betyder det er anvendt kun én indgang, én operand, så at sige. Ikke at en venstre og en højre. Med andre ord, hvis du tager tilde af 0, vil svaret være det modsatte. Og hvis du tager tilde på 1, det Svaret vil der være det modsatte. Så den tilde operatør en måde at bevirke en smule, eller spejlvende lidt fra Fra 0 til 1, eller 1 til 0. 

Og det efterlader os endelig med blot to endelige operatører, den såkaldte venstre skift, og såkaldte ret-operatør. Lad os tage et kig på, hvordan de arbejder. Den venstre skift operatør, skriftlig med to vinkelbeslag som dette, fungerer som følger. Hvis min input, eller min operand, til venstre skift operatør er ganske enkelt en 1. Og jeg så fortælle computeren til venstre skift at 1, siger syv pladser, resultatet er, som om jeg tage, at 1, og flytte det syv pladser over til venstre, og som standard, vi kommer til at antage, at plads til højre vil være polstret med nuller. Med andre ord, 1 venstre skift 7 går at give mig, at 1, efterfulgt af 1, 2, 3, 4, 5, 6, 7 nuller. Så på en måde, det giver dig mulighed for at tage et lille antal som 1, og klart gøre det meget meget, meget større på denne måde, men vi faktisk kommer til at se mere kloge metoder til det stedet, samt, 

Okay. Det er det for uge tre. Vi vil se dig næste gang. Det var CS50. 

[Musik spiller] 

SPEAKER 1: Han var på snack bar spise en varm sludder sundae. Han havde det hele hans ansigt. Han er iført at chokolade som en skæg SPEAKER 2: Hvad laver du? SPEAKER 3: Hmmm? Hvad? 

SPEAKER 2: Har du lige double dip? Du dobbelt dyppet chippen. SPEAKER 3: Undskyld mig. SPEAKER 2: Du dyppet chippen, du tog en bid, og du dyppet igen. SPEAKER 3: SPEAKER 2: Så det er ligesom at sætte Hele din mund lige i dip. Næste gang du tager en chip, bare dyppe den én gang, og afslutte det. 

SPEAKER 3: Ved du hvad, Dan? Du dyppe den måde, du ønsker at dyppe. Jeg vil dyppe den måde, at jeg ønsker at dyppe.