>> [Muziek]
>> Hoogleraar: Oké.
Dit is CS50 en dit is het einde van week drie.
Dus we zijn hier vandaag niet in Sanders Theater, in plaats daarvan in Weidner bibliotheek.
De binnenkant van die is een studio bekend als Hauser Studio,
of zullen we zeggen Studio H, of zal we say-- als je die grap genoten,
het is eigenlijk uit klasgenoot, Mark, online,
die zo veel via Twitter voorgesteld.
Nu wat is cool over dat hier in een studio
is dat ik omringd door deze groene muren, een groen scherm of chromakey,
zo te zeggen, wat betekent dat CS50's productie team, buiten het medeweten van mij
nu, zou kunnen zetten mij het meest overal in de wereld,
in voor-en tegenspoed.
>> Nu wat ons te wachten, probleem stellen twee is in uw handen voor deze week,
maar met een probleem stellen drie komende week,
u zal worden uitgedaagd met de zogenaamde spelletje 15,
een oude partij gunst die je zou herinneren ontvangen
als een kind dat een hele hoop heeft nummers die kan schuiven omhoog, omlaag,
links en rechts, en er is een hiaat binnen de puzzel, waarin u
daadwerkelijk kan schuiven die puzzelstukjes.
Uiteindelijk u deze ontvangen puzzel in sommige semi willekeurige volgorde,
en het doel is om sorteren het, van boven naar beneden,
links naar rechts, van de ene helemaal tot en met 15.
>> Helaas, de implementatie je hebt bij de hand
gaat software gebaseerd, niet fysiek.
Je eigenlijk gaat te hebben om te schrijven code waarmee een student of gebruiker
speel het spel van 15.
En inderdaad, in de hacker editie van het spel van 15,
je zult een uitdaging om uit te voeren, niet alleen het spelen van deze oude school
spel, maar het oplossen ervan, implementeren god mode,
zogezegd, die eigenlijk lost het raadsel van de mens,
door hen te voorzien hint, na hint, hint na.
Zodat meer daarover volgende week.
Maar dat is wat ons te wachten.
>> Voor nu herinneren dat eerder deze week we hadden deze cliffhanger, als je wil,
waarbij het beste wat we aan het doen waren sortering verstandig was een bovengrens van grote o n
kwadraat.
Met andere woorden, bubble sort, selectie sort, insertion sort,
allemaal, terwijl andere in de uitvoering ervan,
overgedragen in een n kwadraat running tijd in het slechtste geval.
En wij over het algemeen aannemen dat het ergste geval is voor het sorteren
is er een die uw input helemaal naar achteren.
En inderdaad, het duurde een paar stappen uitvoering elk van deze algoritmen.
>> Nu aan het einde van de les recall, vergeleken we bubble sort
tegen selectie sorteren tegen een andere dat we geroepen merge soort op het moment,
en ik stel voor dat het nemen van voordeel van een les van week
nul, verdeel en heers.
En een of andere manier het bereiken van een soort logaritmische looptijd uiteindelijk,
in plaats van iets dat is puur kwadratisch.
En het is niet helemaal logaritmische, het is een beetje meer dan dat.
Maar als je te herinneren van de klas, het was veel, veel sneller.
Laten we eens een kijkje nemen op waar we gebleven.
>> Bubble sort versus selectie sort versus merge sort.
Nu zijn ze alle lopende, in theorie tegelijkertijd.
De CPU draait op dezelfde snelheid.
Maar je kunt voelen hoe saai dit zeer snel gaat worden,
en hoe snel, toen we injecteren een beetje van de week nullen algoritmen,
kunnen we sneller dingen.
>> Dus mark soort ziet er geweldig uit.
Hoe kunnen we profiteren van het, met het oog om nummers sneller afstand.
Nou laten we terugdenken een ingrediënt dat we
hadden terug in week nul, die van de op zoek naar iemand in een telefoonboek,
en herinneren eraan dat de pseudocode die wij voorgesteld,
via welke we kunnen vinden iemand als Mike Smith,
keek een beetje zoiets als dit.
>> Neem nu een kijkje in het bijzonder op regel 7 en 8, en 10 en 11,
die deze lus induceren, waarbij we hielden terug naar lijn 3 gaan opnieuw, en opnieuw,
en opnieuw.
Maar het blijkt dat we kunnen bekijken Dit algoritme hier in pseudocode,
een beetje meer holistisch.
In feite, wat ik zoek bij hier op het scherm,
is een algoritme voor het zoeken naar Mike Smith bij sommige set van pagina's.
En inderdaad, we kunnen dit vereenvoudigen algoritme die lijnen 7 en 8,
en 10 en 11 om alleen deze te zeggen, die ik hier in het geel heb gepresenteerd.
Met andere woorden, indien Mike Smith is eerder in het boek,
we hoeven niet te stap te specificeren stap nu hoe om te gaan hem te vinden.
We hoeven niet te specificeren om terug te gaan naar lijn 3,
waarom doen we niet alleen in plaats daarvan, zeggen, meer algemeen,
zoek Mike in de linker helft van het boek.
>> Omgekeerd, als Mike is eigenlijk later in het boek,
waarom doen we niet zomaar citeren unquote zoekopdracht voor Mike in de rechter helft van het boek.
Met andere woorden, waarom gewoon doen we niet soort punter om onszelf te zeggen,
zoek Mike in deze deelverzameling van het boek,
en laat het aan onze bestaande algoritme om ons te vertellen
hoe om te zoeken naar Mike in dat de linker helft van het boek.
Met andere woorden, onze algoritme werkt of het nu
een telefoonboek van deze dikte, van deze dikte of elke dikte dan ook.
Dus we kunnen recursief definieert dit algoritme.
Met andere woorden, de scherm hier, is een algoritme
voor het zoeken naar Mike Smith tussen de bladzijden van een telefoonboek.
Dus in de lijn 7 en 10, laten we gewoon zeggen precies dat.
En ik gebruik deze term een ​​moment geleden, en inderdaad, recursie
is het modewoord voor nu, en het is dit proces
iets cyclisch te doen door een of andere manier met behulp van code die je al hebt,
en opnieuw noemde het, en opnieuw, en opnieuw.
Nu het gaat belangrijk dat we een of andere manier bottom
uit, en doe dat niet oneindig lang.
Zijn we anders gaan inderdaad een oneindige lus.
Maar laten we eens kijken of we dit idee kunnen lenen van een terugkeer, weer iets te doen
en opnieuw en opnieuw, op te lossen het sorteren probleem via merge
sorteren, des te efficiënter.
>> Dus ik geef u soort samenvoegen.
Laten we kijken.
Dus hier is pseudocode, met die we kunnen implementeren sorteren
met behulp van dit algoritme genoemd merge soort.
En het is heel eenvoudig dit.
Op ingang van n elementen, met andere woorden, als je
gegeven n elementen en nummers en letters of wat de ingang,
Als je krijgt n elementen, indien n kleiner is dan 2, gewoon terug.
Rechts?
Want als n kleiner is dan 2, dat betekent dat mijn lijst van elementen
hetzij van maat 0 of 1, en in deze beide triviale zaken
de lijst is al opgelost.
Als er geen lijst, is het opgelost.
En als er een lijst van lengte 1, is het natuurlijk opgelost.
Dus het algoritme alleen moet echt iets interessants te doen,
als we twee of meer elementen aan ons gegeven.
Dus laten we eens kijken naar de magie dan.
Else sorteren de linkerhelft van de elementen, vervolgens sorteren van de rechter helft van de elementen,
Vervolgens fuseren de gesorteerde helften.
En wat voor soort geest buigen hier, is dat ik niet echt
lijken te hebben verteld alles gewoon nog niet, toch?
Alles wat ik heb gezegd is, krijgt een lijst met n elementen, sorteren van de linker helft,
dan is de rechter helft, dan fuseren de gesorteerde helften,
maar waar is de werkelijke geheime saus?
Waar is het algoritme?
Nou, het blijkt dat die twee lijnen eerste soort linkerhelft elementen,
en een soort rechter helft van de elementen, zijn recursieve oproepen, om zo te zeggen.
>> Immers, in dit punt in de tijd, heb ik
een algoritme waarmee afstand een heleboel elementen?
Ja.
Het is hier.
Het is hier op het scherm, en dus ik kan dat dezelfde reeks stappen gebruiken
op de linkerhelft sorteren, als ik kan de rechter helft.
En inderdaad opnieuw en opnieuw.
Dus een of andere manier, en we zullen binnenkort zien, de magie van merge sort
ingebed in die allerlaatste lijn, het samenvoegen van de gesorteerde helften.
En dat lijkt vrij intuïtief.
Je neemt twee helften, en u, een of andere manier, voeg ze samen,
en we zullen dit zien concreet in een moment.
>> Maar dit is een compleet algoritme.
En laten we precies zien waarom.
Nou denk dat we deze zelfde zijn gegeven acht elementen hier op het scherm, een
door middel van acht, maar ze zijn in schijnbaar willekeurige volgorde.
En het doel bij de hand is deze elementen afstand.
Goed hoe kan ik over doet het gebruik van, wederom,
samenvoegen sorteren, volgens deze pseudocode?
En nogmaals, ingrain deze in je geest, voor slechts een moment.
Het eerste geval is vrij triviaal, als het minder dan 2,
gewoon terug, er is geen werk te doen.
Dus eigenlijk is er slechts drie stappen om echt in gedachten te houden.
Opnieuw, en opnieuw, ik ben gaat willen hebben
op de linkerhelft sorteren, sorteren van de rechter helft,
en dan een keer hun twee helften worden gesorteerd,
Ik wil hen samen te voegen in een gesorteerde lijst.
Dus hou dat in gedachten.
>> Dus hier is de oorspronkelijke lijst.
Laten we behandelen dit als een array, zoals we begonnen
in week twee, die een aaneengesloten blok van het geheugen.
In dit geval bevat acht getallen, rug aan rug aan rug.
En laten we nu toepassen merge soort.
Dus ik wil eerst sorteren de linker helft van deze lijst,
en laten we daarom focus op 4, 8, 6 en 2.
>> Nu hoe ga ik over sorteren van een lijst van maat 4?
Nou ik moet nu overwegen sortering links van de linkerhelft.
Nogmaals, laten we terugspoelen voor slechts een moment.
Als de pseudocode is dit, en ik ben gegeven acht elementen,
8 is uiteraard groter dan of gelijk aan 2.
Dus met het eerste geval niet van toepassing.
Dus om acht elementen te sorteren, ik voor het eerst sorteren de linkerhelft van elementen,
dan heb ik afstand de rechter helft, dan samenvoegen I beide gesorteerde helften, elk van afmeting 4.
OK.
>> Maar als je me net hebt verteld, sorteren linkerhelft, die nu van maat 4,
hoe kan ik de linker helft sorteren?
Nou als ik een ingang van de vier elementen,
Ik voor het eerst te sorteren links twee, dan is de juiste twee,
en toen ik ze samen te voegen.
Dus nogmaals, het wordt een beetje van een geest buigen spel hier,
omdat je, soort, moeten onthouden waar je bent in het verhaal,
maar aan het eind van de dag, gegeven een aantal elementen,
je eerst wilt sorteren linkerhelft dan de rechterhelft,
dan voeg ze samen.
Laten we beginnen om precies dat te doen.
Hier is de inbreng van acht elementen.
Nu zijn we op zoek naar de linker helft hier.
Hoe kan ik de afstand vier elementen?
Nou ik voor het eerst afstand de linker helft.
Nu hoe kan ik de linker helft sorteren?
Nou ik heb gekregen twee elementen.
Dus laten sorteren van deze twee elementen.
2 is groter dan of gelijk aan 2, natuurlijk.
Zodat eerste geval niet geldt.
>> Dus ik moet nu naar links te sorteren helft van deze twee elementen.
De linkerhelft, is natuurlijk slechts 4.
Dus hoe kan ik een lijst met één element sorteren?
Welnu, die speciale base case up top, om zo te zeggen, van toepassing.
1 is dan 2, en mijn lijst is inderdaad van grootte 1.
Dus ik gewoon terug.
Ik doe niets.
En inderdaad, kijk naar wat ik heb gedaan, wordt 4 al naargelang.
Zoals ik ben al gedeeltelijk succesvol hier.
>> Nu dat lijkt soort dom conclusie, maar het is waar.
4 is een lijst van grootte 1.
Het is al opgelost.
Dat is de linker helft.
Nu heb ik afstand de rechter helft.
Mijn ingang is een element, 8 evenzo reeds gesorteerd.
Dom, ook, maar nogmaals, dit basisprincipe
zal ons in staat stellen om nu te bouwen op de top van dit succes.
4 naargelang, 8 wordt gesorteerd, nu Wat was dat laatste stap?
Dus de derde en laatste stap, welke keer dat je het sorteren van een lijst, recall,
was de twee helften samen te voegen, links en rechts.
Dus laten we het doen precies dat.
Mijn linkerhelft is natuurlijk 4.
Mijn rechter helft is 8.
>> Dus laten we dit doen.
Eerst Ik ga wijzen wat extra geheugen,
die ik hier vertegenwoordig, als slechts een secundaire array,
Dat is groot genoeg om dit te passen.
Maar je kunt je voorstellen uitbreiding dat de rechthoek de gehele lengte,
als we moeten later meer.
Hoe neem ik 4 en 8, en samenvoegen die twee lijsten van grootte 1 bij elkaar?
Ook hier is vrij eenvoudig.
4 komt eerst, dan komt 8.
Want als ik wil het sorteren linkerhelft dan de rechterhelft,
en dan samen te voegen die twee helften samen, in gesorteerde volgorde,
4 komt eerst, dan komt 8.
>> Dus lijken we te zijn om vooruitgang te boeken, zelfs hoewel ik niet heb gedaan elke eigenlijke werk.
Maar vergeet niet waar we zijn in het verhaal.
We namen oorspronkelijk acht elementen.
We naargelang de linker helft, dat is 4.
Vervolgens gesorteerd we de linkerhelft van de linkerhelft, die 2 was.
En hier gaan we.
We zijn klaar met die stap.
>> Dus als we hebben naargelang de linker helft van de 2, nu zijn we
moet de rechter helft van 2 afstand.
Dus de rechterhelft van 2 is deze twee waarden hier, 6 en 2.
Dus laten we nu eens een ingang van de grootte 2, en sorteren van de linker helft, en dan
de rechter helft, en dan voeg ze samen.
Nou hoe kan ik afstand een lijst van formaat 1, met daarin alleen de nummer 6?
Ik ben al klaar.
Die lijst van maat 1 wordt gesorteerd.
>> Hoe kan ik een andere lijst te sorteren size 1, de zogenaamde rechterhelft.
Nou, het ook, al naargelang.
De nummer 2 is alleen.
Dus nu heb ik twee helften, links en rechts, ik moet ze samen te voegen.
Ik geef mezelf wat extra ruimte.
En zet 2 daar, dan 6 daar, waardoor
sorteren van die lijst, links en rechts, en het samenvoegen van het samen, uiteindelijk.
Dus ik ben in een iets betere vorm.
Ik ben nog niet klaar, omdat duidelijk 4, 8, 2, 6 is niet de definitieve bestelling die ik wil.
Maar ik heb nu twee lijsten van maat 2, dat hebben beide respectievelijk gesorteerd.
Dus nu als je terugspoelen in je geest oog, waar komt die ons verlaten?
Ik ben begonnen met acht elementen, dan heb ik whittled het neer op de linker helft van 4,
dan is de linkerhelft van 2, en vervolgens de rechterhelft van 2,
Ik klaar derhalve sorteren van de linker helft 2, en de rechterhelft van 2,
dus wat is de derde en laatste stap hier?
Ik moet samenvoegen twee lijsten van maat 2.
Dus laten we gaan vooruit.
En op het scherm hier, geven me wat extra geheugen,
hoewel technisch gezien, merken dat ik heb kreeg een heleboel lege ruimte op de top
daar.
Als ik wil vooral zijn efficiënte ruimte wijs,
Ik kon gewoon beginnen met het verplaatsen van de elementen heen en weer, boven en onder.
Maar alleen voor visuele helderheid, Ik ga het beneden te zetten,
om dingen mooi en schoon te houden.
>> Dus ik heb twee lijsten van maat 2.
De eerste lijst heeft 4 en 8.
De tweede lijst heeft 2 en 6.
Laten we samen te voegen die samen in gesorteerde volgorde.
2 uiteraard voorop, dan 4, dan 6, dan 8.
En nu we lijken te krijgen ergens interessant.
Nu heb ik naargelang de helft van de lijst, en toevallig, het is
alle even getallen, maar is inderdaad gewoon een toeval.
En ik nu de linker hebben naargelang helft, zodat het 2, 4, 6 en 8.
Niets is buiten de orde.
Dat voelt als vooruitgang.
>> Nu voelt het alsof ik heb praat nu voor altijd,
dus wat valt nog te bezien of dit algoritme is inderdaad efficiënter.
Maar we gaan door het super methodisch.
Een computer, natuurlijk zou doen als dat.
Dus waar zijn we?
We begonnen met acht elementen.
Ik gesorteerd de linkerhelft van 4.
Ik lijken te worden gedaan met dat.
Nu kan de volgende stap sorteren van de rechter helft van de 4.
En dit deel kunnen we gaan door een beetje
snel, hoewel je bent welkom om terug te spoelen of te pauzeren, gewoon
denken over het op uw eigen tempo, maar wat
We hebben nu een kans om doen precies hetzelfde algoritme op vier
verschillende nummers.
>> Dus laten we doorgaan, en zich richten op de rechter helft, die we hier zijn.
De linkerhelft van deze rechter helft, en nu de
linkerhelft van de linker de helft van die rechter helft,
en hoe kan ik afstand een lijst van formaat 1 bevat alleen de nummer 1?
Het is al gedaan.
Hoe kan ik hetzelfde voor een lijst te doen van grootte 1 met slechts 7?
Het is al gedaan.
Stap drie voor deze helft dan is om deze twee elementen samen te voegen
in een nieuwe lijst van maat 2, 1 en 7.
Lijken niet al te hebben gedaan dat veel interessant werk.
Laten we eens kijken wat er daarna gebeurt.
Ik naargelang de linker helft van de rechterhelft van mijn originele inbreng.
Laten we nu de juiste afstand half, welke 5 en 3 bevat.
Laten we opnieuw kijken naar de linkerzijde half, gesorteerd, rechter helft, gesorteerd,
en het samenvoegen van deze twee samen, in een aantal extra ruimte,
3 komt eerst, dan komt 5.
En nu, we hebben naargelang de linkerhelft van de rechterhelft
van het oorspronkelijke probleem, en de rechterhelft van de rechterhelft
van het oorspronkelijke probleem.
Wat is de derde en laatste stap?
Nou die twee helften samen te voegen.
Dus laat me mezelf nog wat extra ruimte, maar, nogmaals, ik
zou kunnen zijn het gebruik van die extra ruimte boven.
Maar we gaan houden het simpel visueel.
Laat me samenvoegen nu 1, en dan 3, en vervolgens 5 en daarna 7.
Daarbij waardoor ik nu met de rechterhelft van het oorspronkelijke probleem
dat is perfect opgelost.
>> Dus wat blijft?
Ik voel me alsof ik blijf zeggen dat de dezelfde dingen opnieuw, en opnieuw,
maar dat is een afspiegeling is van de feit dat we met behulp van recursie.
Het proces van het gebruik van een algoritme opnieuw, en opnieuw,
op kleinere subsets van het oorspronkelijke probleem.
Dus ik heb nu een linker naargelang de helft van het oorspronkelijke probleem.
Ik heb het recht gesorteerde half van het oorspronkelijke probleem.
Wat is de derde en laatste stap?
Oh, het samenvoegen.
Dus laten we dat doen.
Laten we wijzen een aantal extra geheugen, maar mijn god, we
kan het overal nu zetten.
We hebben zo veel ruimte beschikbaar voor ons, maar we zullen het simpel te houden.
In plaats van terug te gaan en weer met onze oorspronkelijke geheugen,
laten we gewoon doen visueel neer hieronder,
tot het einde van het samenvoegen van de linkerhelft en de rechterhelft.
>> Dus door het samenvoegen, wat moet ik doen?
Ik wil de elementen te nemen om.
Dus kijkt naar de linkerhelft, Ik zie het eerste nummer is 2.
Ik kijk naar de rechter helft, Ik zie het eerste nummer
1 is dus duidelijk welke nummer wil ik rukken uit,
en op de eerste plaats in mijn definitieve lijst?
Natuurlijk 1.
Nu wil ik diezelfde vraag.
Op de linkerhelft, ik heb nog steeds de nummer 2.
Op de rechterhelft, Ik heb het nummer 3.
Die men wil ik kiezen?
Natuurlijk, nummer 2 en Nu merkt de kandidaten
zijn 4 links, 3 rechts.
Laten we, natuurlijk, kiezen uit 3.
Nu de kandidaten zijn 4 op links, 5 rechts.
We natuurlijk kiezen 4.
6 aan de linkerkant, 5 aan de rechterkant.
Wij, natuurlijk, kiezen 5.
6 aan de linkerkant, 7 aan de rechterkant.
We kiezen voor 6, en toen we kiezen 7, en dan kiezen we voor 8.
Voila.
>> Dus een groot aantal woorden later, we deze lijst van acht elementen hebben naargelang
in een lijst van een tot acht, dat is toeneemt met elke stap,
maar hoeveel tijd deed het ons om dat te doen.
Nou ik heb bewust laid dingen uit picturaal
hier, zodat we kunnen soort zien of te genieten van de divisie
in verovering dat er gebeurt.
>> Inderdaad als je kijkt terug op het spoor, Ik heb al deze stippellijnen links
in plaats houders, kunt u, soort, zie, in omgekeerde volgorde,
als je soort terugkijken in geschiedenis nu, mijn oorspronkelijke lijst
is uiteraard van groot 8.
En dan voorheen, ik was maken met twee lijsten van maat 4,
en vervolgens vier lijsten van maat 2, en dan acht lijsten van grootte 1.
>> Dus wat dit doet, soort, herinneren aan?
Nou, inderdaad, een van de algoritmes we hebben
bekeken dusver waar we kloof, en delen, en delen,
houden met de dingen weer, en weer resulteert in deze gedachte.
En dus is er iets logaritmische hier aan de hand.
En het is niet helemaal log van n, maar er is een logaritmische component
met wat we net hebben gedaan.
>> Laten we nu eens kijken hoe dat eigenlijk is.
Dus log n, was weer een geweldige looptijd,
toen we iets dergelijks binary search, zoals we nu noemen,
de verdeel en heers strategie via welke we Mike Smith.
Nu technisch.
Dat is log basis 2 van n, zelfs hoewel in de meeste wiskunde klassen,
10 is meestal de basis die je aanneemt.
Maar informatici bijna altijd denken en spreken in termen van de basis 2,
dus we meestal gewoon log van zeggen n, in plaats van log base 2 van n,
maar ze zijn precies een en hetzelfde in de wereld van computer
wetenschap, en als een terzijde, er is een constante factor
verschil tussen de twee, zodat het moot toch, voor meer formele redenen.
>> Maar voor nu, wat we de zorg is over dit voorbeeld.
Dus laten we niet bewijzen door bijvoorbeeld, maar op z'n minst een voorbeeld van de aantallen
bij de hand als een sanity check, als je wil.
Dus eerder de formule was log base 2 van n, maar wat is aangegeven in dit geval.
Ik had n originele nummers, of 8 originele nummer specifiek.
Nu is het een beetje geweest terwijl, maar ik ben vrij
ervoor dat log basis 2 de waarde 8 is 3,
en inderdaad, wat is er leuk aan is dat 3 dat is precies aantal keren
dat je een lijst kan verdelen met een lengte van 8 opnieuw, en opnieuw,
en weer, totdat je links bent met lijsten van slechts 1 formaat.
Rechts?
8 gaat naar 4, gaat naar 2, gaat naar 1, en dat
afspiegeling is van precies dat foto we hadden net een moment geleden.
Dus een beetje gezond verstand checken waar de logaritme daadwerkelijk betrokken.
>> Dus nu, wat is hier bij betrokken? n.
Zo merken dat elke keer ik deelden de lijst,
zij het in omgekeerde volgorde in de geschiedenis hier, ik was nog steeds n dingen te doen.
Dat samenvoegen stap vereist dat Ik raak ieder van de nummers,
om het glijden de juiste locatie.
Dus hoewel de lengte van deze diagram is van groot log n n of 3,
specifiek, met andere woorden, Ik heb hier drie divisies.
Hoeveel werk heb ik gedaan horizontaal langs deze grafiek elke keer?
>> Nou, ik heb n stappen werken, want als ik heb
kreeg vier elementen en de vier elementen, en ik moet ze samen te voegen.
Ik moet om te gaan door deze vier en deze vier,
uiteindelijk om hen te fuseren back in acht elementen.
Als omgekeerd Ik acht vingers heb hier, dat doe ik niet, en acht
fingers-- sorry-- Als ik heb kreeg vier vingers hier,
wat ik doe, vier vingers hier, wat ik doe,
dan is dat hetzelfde Bijvoorbeeld als voorheen, als ik dat doe
hebben acht vingers al in in totaal, wat ik kan, een soort van, doe.
Ik kan precies doen hier, dan kan ik zeker
samenvoegen van al deze lijsten van maat 1 samen.
Maar ik hebben zeker kijken aan elk element precies één keer.
Zodat de hoogte van dit proces is log n, de breedte van dit proces, zogezegd,
n, dus wat we lijken om, uiteindelijk, is
een looptijd van grootte n keer log n.
>> Met andere woorden, we verdeeld de lijst, log n keer,
maar elke keer dat we dat deden, hadden we aan elk van de elementen te raken
om ze te fuseren allemaal samen, die
werd n stap, dus we hebben n keer log n, of als een computer wetenschapper zou zeggen,
asymptotisch die zou het grote woord
de bovenste beschrijven gebonden op een looptijd,
We lopen in een grote o log n tijd, om zo te zeggen.
>> Nu is dit belangrijk, omdat herinneren wat de looptijden waren
met bel sorteren en selectie sorteren en insertion sort,
en zelfs een paar anderen die er bestaan, n kwadraat was waar we waren.
En je kunt, een soort van, zie deze hier.
Als n kwadraat kennelijk n keer n, maar hier hebben we n keer log n,
en we al kennen van de week nul, dat log n, de logaritmische,
beter is dan iets lineair.
Immers, herinneren aan de foto de rode en gele
en de groene lijnen die we trokken, de groen logaritmische lijn was veel lager.
En daarom, veel beter en sneller dan de rechte gele en rode lijnen,
n maal log n is inderdaad beter dan n maal n of n kwadraat.
>> Dus we lijken te hebben geïdentificeerd een algoritme samenvoegen
soort die in veel loopt snellere tijd, en inderdaad,
dat is waarom, eerder deze week, toen zagen we dat de wedstrijd tussen bubble
sorteren, selectie sorteren en samenvoegen sorteren, samenvoegen soort echt, echt gewonnen.
En inderdaad, we hebben niet eens wachten voor de bubble sort en selectie sorteren
tot finish.
>> Laten we nu eens een ander pas Dit vanuit een iets
Formeel gezien, alleen in geval, dit resoneert beter
dan dat hogere niveau discussie.
Dus hier is het algoritme weer.
Laten we ons afvragen, wat de looptijd
is van deze algoritmen verschillende stappen?
Laten verdeel het in de eerste geval en het tweede geval.
De IF en de andere in het geval als, Als n kleiner is dan 2, gewoon terug.
Voelt als constante tijd.
Het is, een soort van, zoals twee stappen, IF n is minder dan 2, dan terug.
Maar zoals we al zeiden op maandag, constante tijd, of groot o van 1,
kunnen twee stappen, drie stappen, zelfs 1.000 stappen.
Waar het om gaat is dat het een constant aantal stappen.
Dus de gele gemarkeerd pseudocode hier loopt, we noemen het,
constante tijd.
Dus meer formeel en we gaan dit to--
de mate waarin we formaliseren dit recht now-- T van n,
de looptijd van een probleem dat neemt n plussers als input,
evenaart grote o van één, Als n kleiner is dan 2.
Dus het is afhankelijk van dat.
Dus om duidelijk te zijn, als n minder dan 2, hebben we een zeer korte lijst, dan
de looptijd, T n, waarbij n 1 of 0, in dit specifieke geval,
het is gewoon een constante tijd.
Het gaat om één te nemen stap, twee stappen, wat dan ook.
Het is een vast aantal stappen.
>> Zodat de sappige deel moet zeker in het andere geval in de pseudocode.
De ELSE zaak.
Soort linkerhelft van elementen, een soort recht de helft van de elementen, samenvoegen gesorteerde helften.
Hoe lang duurt elk van die stappen te ondernemen?
Nou, als de running tijd om n elementen te sorteren
is, laten we noemen het zeer algemeen, T n,
sorteert links de helft van de elementen
is, een soort van, als zeggen, T n gedeeld door 2,
en op soortgelijke wijze sorteren van de rechterhelft van de elementen is, een soort van, als zeggen,
T n verdeelde 2, en samenvoegen van de gesorteerde helften.
Nou als ik heb wat aantal elementen hier
zoals vier en een getal elementen hier, net als vier,
Ik moet elk van deze vier samenvoegen in, en elk van deze vier in één
na elkaar, zodat Uiteindelijk heb ik acht elementen.
Het voelt alsof dat is grote o n stappen?
Als ik n vingers en elk van hebt ze moet worden samengevoegd in plaats,
dat is als een andere n stappen.
>> Dus inderdaad formulaically, kunnen we dit uit te drukken,
zij het een beetje scarily eerst gezicht, maar het is iets
dat vangt precies die logica.
De looptijd, T n, n IF groter of gelijk aan 2.
In dit geval is het ELSE geval is T n gedeeld door 2, plus T n gedeeld door 2,
plus grote o n, sommige lineaire aantal stappen,
misschien precies n, misschien 2 keer n, maar het is ruwweg, orde van n.
Dus ook dat is hoe we kunnen uitdrukken dit formulaically.
Nu zou je dit niet weten, tenzij je hebt het opgenomen in je geest,
of zoek het op in de rug van een leerboek, dat
misschien een beetje hebben cheat sheet op het einde,
maar dit is inderdaad naar geven ons een grote o n log n,
omdat de herhaling dat u hier ziet op het scherm,
als je eigenlijk deed het uit, met een oneindig aantal voorbeelden,
of je het deed formulaically, zou je zien dat dit, omdat deze formule
zelf recursief met ton n over iets aan de rechterkant,
en t n op links, kan dit in feite tot expressie worden gebracht, uiteindelijk,
zo groot gaan van n log n.
Als er niet van overtuigd, dat is boete voor nu, net
nemen over geloof, dat dat inderdaad, wat dat herhaling leidt tot,
maar dit is gewoon een beetje meer van een wiskundige benadering op zoek
op de looptijd van merge sort gebaseerd op de pseudocode alleen.
>> Laten we nu eens een beetje een beluchter van dat alles,
en een kijkje nemen op een bepaalde voormalige senator, die
ziet er misschien een beetje bekend, die beneden zat met Google's Eric
Schmidt, enige tijd geleden, voor een interview op het podium, in de voorkant van een heleboel
mensen, praten uiteindelijk over een onderwerp, dat is vrij nu bekend.
Laten we kijken.
>> Eric Schmidt: Nu Senator, je bent hier bij Google,
en ik denk aan de voorzitterschap als een sollicitatiegesprek.
Nu is het moeilijk om een ​​baan als president krijgen.
PRESIDENT OBAMA: Recht.
Eric Schmidt: En je bent nu doen [onverstaanbaar].
Het is ook moeilijk om een ​​baan te krijgen bij Google.
PRESIDENT OBAMA: Recht.
>> Eric Schmidt: We hebben vragen, en we vragen onze kandidaten vragen,
en dit is van Larry Schwimmer.
>> PRESIDENT OBAMA: OK.
>> Eric Schmidt: Wat?
Jullie denken dat ik gek?
Het is hier.
Wat is de meest efficiënte manier om sorteren op een miljoen 32 bits gehele getallen?
>> PRESIDENT OBAMA: goed--
Eric Schmidt: Soms, misschien ben ik sorry, maybe--
PRESIDENT OBAMA: Nee, nee, nee, nee, nee, ik think--
Eric Schmidt: Dat is niet het--
PRESIDENT OBAMA: I denk, denk ik dat de zeepbel
soort zou de verkeerde weg te gaan.
Eric Schmidt: Kom op.
Wie heeft hem dit verteld?
OK.
Ik heb niet de computer science on--
>> PRESIDENT OBAMA: We hebben kreeg onze spionnen in.
Hoogleraar: Oké.
Laten we achter ons nu de theoretische wereld van algoritmen
in de asymptotische analyse daarvan, en terug te keren naar een aantal onderwerpen
vanaf week nul en één, en start wat zijwieltjes te verwijderen,
als je wil.
Zodat je echt begrijpt uiteindelijk van de grond af, wat is
gebeurt onder de motorkap, wanneer u schrijven, compileren en uit te voeren programma's.
Herinneren in het bijzonder, dat dit de eerste C-programma keken we naar,
een canoniek, eenvoudig programma van soorten, relatief gezien,
waarin, drukt, Hello World.
En herinner dat ik zei, het proces dat de broncode gaat door
is precies dit.
U neemt uw broncode, passeren het door een compiler, zoals Clang,
en komt uit object code, die kan er zo uitzien, nullen en enen
dat de CPU van de computer, centrale verwerkingseenheid of de hersenen,
uiteindelijk begrijpt.
>> Het blijkt dat dat is een beetje een oversimplificatie,
dat we nu in een positie om elkaar te plagen
om te begrijpen wat er echt geweest gebeurt onder de motorkap
elke keer dat u Clang, of meer algemeen,
elke keer dat u een programma te maken, gebruik maken en CF 50 IDE.
In het bijzonder, dat soort dingen Dit is de eerste gegenereerd,
wanneer u eerst uw programma samenstellen.
Met andere woorden, bij neem uw broncode
en het compileren, wat is de eerste wordt afgegeven door Clang
is iets bekend als assemblage-code.
En in feite, het ziet er precies zo.
>> Ik liep een opdracht bij de command line eerder.
Clang dash hoofdstad s hello.c, en dit creëerde een bestand
voor mij belde hello.s, de binnenkant van die precies waren
deze inhoud, en een beetje boven en iets meer dan,
maar ik heb de sappigste gezet Informatie hier op het scherm.
En als je goed kijkt, zie je minstens een paar vertrouwde trefwoorden.
We hebben de belangrijkste bovenaan.
We hebben in het midden printf.
En we hebben ook hello wereld backslash n aanhalingstekens beneden.
>> En alles wat hier binnen is instructies zeer laag niveau
dat de CPU van de computer begrijpt.
CPU aanwijzingen dat het geheugen bewegen rond, dat de lading strijkers uit het geheugen,
en uiteindelijk, print dingen op het scherm.
Wat gebeurt er als zij na deze vergadering code wordt gegenereerd?
Uiteindelijk, je doet, inderdaad, nog steeds het genereren van object code.
Maar de stappen die echt er aan de hand onder de motorkap
ziet er een beetje meer als dit.
Broncode wordt assemblage-code, die dan object code,
en de operatieve woorden hier zijn dat, wanneer u uw broncode te compileren,
komt uit assemblage-code, en vervolgens wanneer u uw assemblage-code monteren,
buiten komt object code.
>> Nu Clang is super geavanceerde, als een veel compilers,
en het doet al deze stappen samen, en het doet niet noodzakelijkerwijs
uitgang enige intermediaire bestanden die u ook kunt zien.
Het compileert gewoon dingen, die de algemene term die
beschrijft dit hele proces.
Maar als je echt wilt bijzonder zijn, er
veel meer aan de hand daar ook.
>> Maar laten we ook rekening houden nu dat zelfs dat super eenvoudig programma, hello.c,
zogenaamde functie.
Hij riep printf.
Maar ik heb niet schrijven printf, inderdaad, die wordt geleverd met c, bij wijze van spreken.
Het is een functie recall dat is in standaard io.h, verklaarde die
is een header bestand, dat is een onderwerp dat we eigenlijk
duiken in meer diepte duurde niet lang.
Maar een header bestand meestal vergezeld
door een code-bestand, broncode bestand, dus net zoals er bestaat standaard io.h.
>> Enige tijd geleden iemand, of iemands, schreef ook
een bestand met de naam standaard io.c, in die de eigenlijke definities,
of implementaties van printf, en trossen van andere functies,
daadwerkelijk geschreven.
Dus gezien het feit dat, als we rekening houden met hier op de linker, hello.c, dat wanneer
gecompileerd geeft ons hello.s, zelfs indien Clang is niet de moeite te besparen op een plaats
kunnen we het zien, en dat de montage code wordt samengesteld tot hello.o, waarin
is inderdaad de standaardnaam gegeven wanneer u de bron te compileren
code in object code, maar zijn niet helemaal klaar om het nog uit te voeren,
omdat een andere stap moet gebeuren, en heeft
is gebeurd de afgelopen weken, misschien buiten het medeweten van u.
>> Specifiek ergens in CS50 IDE, en dit,
Ook zal een beetje een te zijn oversimplificatie voor een moment,
Er is, of was upon a time, een bestand met de naam standaard io.c,
dat iemand gecompileerd in standaard io.s of het equivalent,
dat iemand vervolgens samengevoegd in standaard io.o,
of het blijkt in een iets ander bestand
formaat dat anders kan hebben file extensie helemaal,
maar in theorie en conceptueel, precies die stappen moest gebeuren in een bepaalde vorm.
Dat wil zeggen, dat nu als ik het schrijven van een programma,
hello.c, die net zegt, hello wereld, en ik gebruik de code van iemand anders
zoals printf, die once upon a was tijd, in een bestand met de naam standaard io.c,
dan een of andere manier moet ik mijn nemen object code, mijn nullen en enen,
en object van die persoon code, of nullen en enen,
en een of andere manier te koppelen samen in een laatste bestand, genaamd hello, dat
heeft alle nullen en degenen van mijn belangrijkste functie,
en alle nullen en degenen voor printf.
>> En inderdaad, dat laatste proces genoemd, het koppelen van uw object code.
Waarvan de uitgang is een uitvoerbaar bestand.
Dus in alle eerlijkheid, op de Uiteindelijk, niets
veranderd sinds één week, wanneer we begon het samenstellen van programma's.
Immers, dit alles is gebeurt onder de motorkap,
maar nu zijn we in een positie waar we kunnen eigenlijk
plagen elkaar deze verschillende stappen.
En inderdaad, eind van de dag, we zijn nog steeds
links nullen en enen, die is eigenlijk een geweldige Segue nu
een ander vermogen van C, die we niet moesten waarschijnlijk hefboomeffect
tot op heden bekend als bitwise operators.
Met andere woorden, tot nu toe, wanneer hebben we behandeld data in C of variabelen in C,
we hebben de dingen gehad, zoals chars en praalwagens en ins
en verlangt en tweepersoonskamers en dergelijke, maar al die ten minste acht bits.
We hebben nog nooit in staat geweest om manipuleren individuele bits,
Zelfs wanneer een individu bit, we weet, kan een 0 en 1 vertegenwoordigen.
Nu blijkt dat in C, u kan toegang krijgen tot de individuele bits,
Als jij de syntaxis, waarmee krijgen op hen.
>> Dus laten we eens een kijkje nemen bij bitwise operators.
Hier dus afgebeeld zijn enkele symbolen die we hebben, een soort van, soort van, eerder gezien.
Ik zie een ampersand, een verticale bar, en enkele anderen ook,
en herinneren eraan dat ampersand ampersand is iets wat we eerder hebben gezien.
De logische operator AND, waar je twee te zamen, of de logische OR
operator, waar u hebben twee verticale balken.
Bitwise operators, die we zullen Zie werken op stukjes individueel,
gewoon gebruik maken van een enkel teken, een enkele verticale balk, het dakje symbool
daarna komt, de kleine tilde, en dan links
beugel links beugel of rechts beugel rechts beugel.
Elk van deze verschillende betekenissen.
>> In feite, laten we eens een kijkje nemen.
Laten we gaan oude school vandaag, en het gebruik een touch screen van weleer,
bekend als een wit bord.
En deze witte boord zal ons in staat stellen
sommige vrij eenvoudige symbolen uit te drukken, of liever een aantal vrij eenvoudige formules,
dat we kunnen dan uiteindelijk leverage, teneinde
om individuele bits binnen een C programma.
Met andere woorden, laten we dit doen.
Laten we het eerste gesprek voor een ogenblik over ampersand,
dat is de bitsgewijze operator.
Met andere woorden, dit een operator die het mogelijk maakt
me naar een linker variabele hebben typisch, en een rechtse variabele,
of een individuele waarde, dat als we EN ze samen, geeft me een eindresultaat.
Dus wat ik bedoel?
Als in een programma, heb je een variabele dat voorraden een van deze waarden,
of laten we het simpel houden, en gewoon schrijf uit nullen en enen individueel,
hier is hoe de ampersand operator werkt.
0 ampersand 0 gaat gelijk 0.
Waarom is dat?
>> Het is vergelijkbaar met Boolean expressies,
dat we tot nu toe hebben besproken.
Als je denkt dat immers de 0 is vals, 0 is vals, onjuist en onwaar
is, zoals we hebben besproken logisch, ook vals.
Dus krijgen we 0 hier ook.
Als je 0 ampersand nemen 1, goed dat, ook,
gaat worden 0, omdat bij dit linker expressie waar of 1 zijn,
het zou moeten waar en waar te zijn.
Maar hier hebben we vals en waar, of 0 en 1.
Nu weer, als we 1 ampersand 0, dat ook zal worden 0,
en als we 1 ampersand 1, eindelijk hebben we een 1 bit.
Dus met andere woorden, we zijn niet te doen iets interessants met deze operator
gewoon nog niet, dit ampersand operator.
Het is de bitsgewijze operator AND.
Maar dit zijn de ingrediënten via welke we kunnen doen
interessante dingen, zoals we snel zullen zien.
>> Laten we nu eens kijken naar alleen de enkelvoudige verticale balk hier aan de rechterkant.
Als ik een 0-bit en ik OR met de bitsgewijze
OR operator, een 0 bit, dat gaat mij 0.
Als ik een 0-bit en OR met een 1-bit, dan ga ik om 1.
En inderdaad, voor duidelijkheid, laat me terug te gaan,
zodat mijn verticale balken zijn niet vergis voor 1's.
Laat me al te herschrijven mijn 1 is een beetje meer
duidelijk, zodat we volgend zien, als ik hebben een 1 of 0, dat gaat een 1 te zijn,
en als ik een 1 of 1 dat, Ook zal een 1 zijn.
Dus je kunt logisch zien dat de OR exploitant gedraagt ​​zich heel anders.
Dit geeft me 0 OF 0 geeft me 0, maar elke andere combinatie geeft me 1.
Zolang ik heb een 1 in de formule, wordt het resultaat zal zijn 1.
>> Anders dan de AND exploitant, de ampersand,
alleen als ik twee 1 in de vergelijking, heb ik eigenlijk een 1 op.
Nu is er een paar andere exploitanten ook.
Een van hen is een beetje meer betrokken.
Dus laat me gaan en te wissen Dit om ruimte vrij te maken.
En laten we eens een kijkje op de dakje symbool, voor slechts een moment.
Dit is typisch een teken dat u kunt typen
op uw toetsenbord bedrijf Shift en dan is een van de nummers boven op uw VS
keyboard.
>> Dus dit is de exclusieve OR operator, exclusieve OR.
Dus we zagen de OR operator.
Dit is de exclusieve operator OR.
Wat is eigenlijk het verschil?
Nou laten we gewoon kijken naar de formule, en gebruik dit als ingrediënten uiteindelijk.
0 0 XOR.
Ik ga zeggen is altijd 0.
Dat is de omschrijving van de XOR.
0 XOR 1 gaat worden 1.
1 XOR 0 gaat worden 1, en 1 XOR 1 gaat worden?
Fout?
Of rechts?
Ik weet het niet.
0.
Nu, wat is hier aan de hand?
Goed na te denken over de De naam van deze operator.
Exclusive OR, teneinde de naam, soort van, al doet vermoeden,
het antwoord is alleen maar om te zijn een 1 als de ingangen zijn exclusief,
exclusief verschillend.
Dus hier de ingangen zijn de hetzelfde, zodat de uitgang 0.
Hier zijn de ingangen van de hetzelfde, zodat de uitgang 0.
Hier zijn de uitgangen verschillend, zij exclusief, en dus is de output 1.
Dus het is zeer vergelijkbaar met En, het is zeer vergelijkbaar zijn,
of liever is vergelijkbaar met OR, maar alleen op een exclusieve wijze.
Dit is niet langer een 1, want we hebben twee 1's,
en niet uitsluitend één van hen.
Prima.
Hoe zit het met de anderen?
Nou, de tilde, ondertussen, is eigenlijk leuk en eenvoudig, gelukkig.
En dit is een unary operator, waardoor
het wordt toegevoerd aan één ingang, één operand, om zo te zeggen.
Niet een linker en een rechter.
Met andere woorden, als je tilde van nemen 0, zal het antwoord het tegenovergestelde.
En als je rekening tilde van 1, de antwoord er het tegenovergestelde zal zijn.
Dus de tilde exploitant een manier van ontkenning van een beetje,
of flipping een beetje uit 0-1 of 1-0.
>> En dat laat ons eindelijk met slechts twee laatste exploitanten,
de zogenaamde linkse shift, en zogenaamde rechter shift operator.
Laten we eens kijken naar hoe die werken.
De linker shift operator, geschreven met twee punthaken als dat,
werkt als volgt.
Indien mijn inbreng of mijn operand, links shift exploitant is gewoon een 1.
En ik dan vertellen dat de computer linker verschuiving die 1, zeggen zeven plaatsen,
het resultaat is alsof ik neem dat 1 en verplaatsen
zeven plaatsen naar de links, en door gebrek,
We gaan ervan uit dat de ruimte aan de rechterkant
zal worden opgevuld met nullen.
Met andere woorden, 1 links verplaatsen 7 gaat om me dat 1, gevolgd door 1, 2, 3,
4, 5, 6, 7 nullen.
Dus in zekere zin, het laat je neem een ​​klein aantal, zoals 1,
en duidelijk maakt het veel veel, veel groter in deze manier
maar we eigenlijk gaan zien slimmer benaderingen voor haar
in plaats daarvan ook,
>> Prima.
Dat is het voor week drie.
Wij zullen u de volgende keer.
Dit was CS50.
>> [Muziek]
>> SPEAKER 1: Hij was bij de snack bar eten van een hete fudge ijscoupe.
Hij had het allemaal over zijn gezicht.
Hij draagt ​​dat chocolade als een baard
Luidspreker 2: Wat doe je?
SPEAKER 3: Hmmm?
Wat?
>> Luidspreker 2: Heb je net double dip?
U doopte het dubbele van de chip.
SPEAKER 3: Neem me niet kwalijk.
Luidspreker 2: U gedoopt de chip, u nam een ​​hap, en je weer gedompeld.
SPEAKER 3:
Luidspreker 2: Dus dat is als het zetten je hele mond in het dip.
Volgende keer dat je een chip te nemen, maar doopt het een keer, en eindig.
>> SPEAKER 3: weet je wat, Dan?
Je doopt de manier waarop u wilt onderdompelen.
Ik zal de manier waarop ik wil dip dip.