[Speel van musiek] 

PROFESSOR: Alle reg. Dit is CS50, en dit is die einde van die week drie. So ons is hier vandag nie in Sanders Teater, plaas in Weidner Biblioteek. Binnekant van wat is 'n ateljee bekend as Hauser Studio, of sal ons sê Studio H, of moet ons say-- as jy dit grap geniet, dit is eintlik van klasmaat, Mark, online, wat soveel via Twitter voorgestel. Nou wat is koel oor hier is in 'n ateljee is dat ek omring deur hierdie groen mure, 'n groen skerm of chromakey, om so te praat, wat beteken dat CS50 se produksie span, buite my nou, kan wees om my die meeste enige plek in die wêreld, vir 'n beter of vir slegter. 

Nou wat voorlê, probleem stel twee is in jou hande vir hierdie week, maar met die probleem sit drie hierdie komende week, sal jy uitgedaag word met die sogenaamde game van 15, 'n ou partytjie guns wat u sal onthou ontvang as 'n kind wat 'n hele klomp het getalle wat kan gly op, af, links en regs, en daar is een gaping binne die legkaart, waarin jy eintlik kan gly diegene stukke van die legkaart. Uiteindelik jy dit ontvang legkaart in sommige semi ewekansige volgorde, en die doel is om sorteer dit, bo na onder, links na regs, van die een al die pad deur 15. 

Ongelukkig is die implementering jy het in die hand gaan wees sagteware gebaseer is, nie fisies. Jy eintlik gaan hê om te skryf kode met wat 'n student of gebruiker kan speel die spel van die 15. En in die feit, in die hacker uitgawe van spel van 15, jy sal 'n uitdaging om te implementeer, nie net die speel van hierdie ou skool spel nie, maar eerder die oplossing dit, implementering god af, om so te praat, wat eintlik los die legkaart vir die mens, deur hulle te voorsien met 'n wenk, ná wenk, ná wenk. Sodat meer op dat die volgende week. Maar dit is wat voorlê. 

Vir nou onthou dat vroeër hierdie week ons het hierdie fotonische lewe, as jy wil, waardeur die beste wat ons besig was om te sorteer wyse was 'n bogrens van die groot o van n kwadraat. Met ander woorde, borrelsortering, seleksie soort, voeg soort, almal van hulle, terwyl verskillende in die implementering daarvan, afgewentel in 'n N kwadraat hardloop keer in die heel ergste geval. En ons in die algemeen aanvaar dat die heel ergste geval vir sortering is die een wat jou insette is heeltemal agteruit. En inderdaad, dit het 'n hele paar stappe te implementeer elkeen van daardie algoritmes. 

En aan die einde van die klas Onthou, ons vergelyk borrelsortering teen seleksie soort teen mekaar dat ons geroep merge soort op die oomblik, en ek stel voor dat dit neem voordeel van 'n les uit week nul, verdeel en oorwin. En een of ander manier 'n soort van die bereiking van logaritmiese looptyd uiteindelik in plaas van iets dit is suiwer kwadratiese. En dit is nie heeltemal logaritmiese, dit is 'n bietjie meer as dit. Maar as jy onthou uit die klas, dit was baie, baie vinniger. Kom ons neem 'n blik op waar ons opgehou het. 

Borrel soort versus seleksie sorteer versus merge soort. Nou is hulle almal hardloop, in teorie, op dieselfde tyd. Die SVE loop teen dieselfde spoed. Maar jy kan voel hoe vervelig dit is baie vinnig gaan word, en net hoe vinnig, wanneer ons spuit 'n bietjie van die week se zero algoritmes, kan ons vinniger dinge op. 

So merk soort lyk amazing. Hoe kan ons dit hefboom, ten einde om getalle vinniger te sorteer. Wel, laat ons terugdink om 'n bestanddeel wat ons het terug in week nul, dié van soek vir iemand in 'n telefoon boek, en onthou dat die pseudokode dat ons voorgestel via wat ons kan vind iemand soos Mike Smith, kyk 'n bietjie iets soos hierdie. 

Nou neem 'n blik in die besonder op reël 7 en 8, en 10 en 11, wat daardie lus veroorsaak, waardeur ons gehou terug na lyn 3 gaan weer en weer, en weer. Maar dit blyk dat ons kan sien hierdie algoritme, hier in pseudokode, 'n bietjie meer holisties. In werklikheid, wat ek soek om hier op die skerm, is 'n algoritme vir die soek vir Mike Smith onder sommige stel bladsye. En inderdaad, kan ons dit vereenvoudig algoritme in die lyne 7 en 8, en 10 en 11 tot net dit te sê, wat ek hier in geel het aangebied. Met ander woorde, as Mike Smith is vroeër in die boek, Ons hoef nie te stap spesifiseer stap nou hoe om te gaan hom kry. Ons hoef nie te spesifiseer om terug te gaan na lyn 3, hoekom doen ons nie net plaas, sê, meer algemeen, soek Mike in die links helfte van die boek. 

Omgekeerd, indien Mike is eintlik later in die boek, Daarom het ons nie net te haal unquote search vir Mike in die regter helfte van die boek. Met ander woorde, hoekom doen net ons nie soort liewer onsself sê, soek Mike in hierdie subset van die boek, en laat dit aan ons bestaande algoritme om ons te vertel hoe om te soek vir Mike in wat links die helfte van die boek. Met ander woorde, ons algoritme werk of dit nou 'n telefoon boek van hierdie dikte, van hierdie dikte, of enige dikte hoegenaamd nie. Sodat ons kan rekursief definieer hierdie algoritme. Met ander woorde, die skerm hier, is 'n algoritme vir die soek vir Mike Smith onder die bladsye van 'n telefoon boek. So in reël 7 en 10, laat net sê presies dit. En ek gebruik die term 'n oomblik gelede, en inderdaad, rekursie is die modewoord vir nou, en dit is hierdie proses van iets sikliese doen deur een of ander manier die gebruik van kode wat jy reeds het, en weer 'n beroep nie, en weer en weer. Nou gaan dit belangrik wees dat ons een of ander manier onder uit en dit nie doen nie oneindig lank. Is anders gaan ons het inderdaad 'n oneindige lus. Maar laat ons kyk of ons hierdie idee kan leen van 'n rekursie, weer iets doen en weer en weer, op te los die sortering probleem via merge soort, al hoe meer doeltreffend. 

So ek gee jou soort saam te smelt. Kom ons neem 'n blik. So hier is pseudokode, met wat ons kan implementeer sorteer, die gebruik van hierdie algoritme genoem merge soort. En dit is eenvoudig hierdie. Op insette van n elemente, Met ander woorde, as jy gegee N elemente en getalle en letters of wat ook al die insette is, as jy gegee N elemente, indien N is minder as 2, net terug te keer. Reg? Want as N is minder as 2, wat beteken dat my lys van elemente is een van die grootte 0 of 1, en in beide van die triviale gevalle die lys is reeds gesorteer. As daar geen lys, is dit gesorteer. En as daar is 'n lys van die lengte 1, is dit natuurlik gesorteer. So die algoritme moet net regtig iets interessant te doen, As ons twee of meer elemente wat aan ons gegee. So laat ons kyk na die magie dan. Anders sorteer die linker helfte van die elemente, dan sorteer die regter helfte van elemente, dan saam te smelt die gesorteer helftes. En wat is soort van gedagte buig hier, is dat ek nie regtig lyk om jou gesê het niks net nog nie, reg? Al wat ek gesê het is, 'n lys van N elemente, sorteer die linker helfte, dan die regter helfte, dan saamsmelt die gesorteer helftes, maar waar is die werklike geheime kruie? Waar is die algoritme? Wel dit blyk dat die twee lyne eerste, sorteer gelaat helfte van elemente, en sorteer regter helfte van elemente, is rekursiewe oproepe, om so te praat. 

Na alles, op hierdie punt in die tyd, het ek 'n algoritme waarmee sorteer n hele klomp van elemente? Ja. Dit is reg hier. Dit is reg hier op die skerm, en sodat ek kan dieselfde stel stappe gebruik aan die linkerkant half sorteer, as ek kan die regter helfte. En inderdaad, weer en weer. So een of ander manier, en ons sal gou sien dit, die magie van merge soort ingebed in daardie finale lyn, die samesmelting van die gesorteerde helftes. En dit lyk redelik intuïtief. Jy neem twee helftes, en jy, een of ander manier, saam te smelt hulle saam, en ons sal sien konkreet in 'n oomblik. 

Maar dit is 'n volledige algoritme. En laat ons sien presies hoekom. Wel dink dat ons hierdie selfde is gegee agt elemente hier op die skerm, die een deur agt, maar hulle is in skynbaar ewekansige volgorde. En die doel aan die hand is om hierdie elemente te sorteer. Wel, hoe kan ek gaan om dit te doen deur gebruik te maak, weer, saamsmelt soort, soos per die pseudokode? En weer, ingeworteld dit in jou gedagtes, want net 'n oomblik. Die eerste geval is redelik triviale, as dit is minder as 2, net terug, daar is geen werk wat gedoen moet word. So regtig daar is net drie stappe om werklik in gedagte te hou. Weer en weer, ek is gaan wil hê aan die linkerkant half sorteer, sorteer die regter helfte, en dan weer hul twee helftes is gesorteer, Ek wil vir hulle saam te smelt in een gesorteerde lys. So hou dit in gedagte. 

So hier is die oorspronklike lys. Kom ons hanteer dit as 'n skikking, as ons begin om in week twee, wat is 'n aangrensende blok van die geheue. In hierdie geval, met agt getalle, rug aan rug aan rug. En laat ons nou aansoek merge soort. So ek wil eers te sorteer die linker helfte van hierdie lys, en laat ons dus fokus op 4, 8, 6, en 2. 

Nou hoe gaan ek te werk sorteer 'n lys van die grootte 4? Wel, ek het nou oorweeg sorteer die linkerkant van die linker helfte. Weereens, laat ons rewind vir net 'n oomblik. As die pseudokode is dit, en ek het agt elemente, 8 is natuurlik groter as of gelyk aan 2. So met die eerste geval is nie van toepassing. So agt elemente te sorteer, ek eerste sorteer die linker helfte van die elemente dan het ek sorteer die regter helfte, dan smelt ek Die twee helftes gesorteer, elke grootte 4. OK. 

Maar as jy my net vertel het, sorteer die linkerhelfte, wat nou van die grootte 4, hoe kan ek die linkerkant half sorteer? Wel, as ek 'n insette van vier elemente, Ek het eers sorteer links twee, dan is die regte twee en dan het ek hulle saam te smelt. So weer, raak dit 'n bietjie van 'n gedagte buig spel hier, omdat jy, soort, moet onthou waar jy is in die storie, maar aan die einde van die dag, gegee 'n aantal van die elemente, jy eers wil die sorteer linkerhelfte, dan die regter helfte, dan saam te smelt hulle saam. Kom ons begin om presies dit te doen. Hier is die insette van agt elemente. Nou is ons op soek na die linker helfte hier. Hoe sorteer ek vier elemente? Wel, ek eerste sorteer links helfte. Nou hoe kan ek die linkerkant half sorteer? Wel, ek het gegee is twee elemente. So laat sorteer hierdie twee elemente. 2 groter as of gelyk aan 2, natuurlik. Sodat eerste geval nie van toepassing nie. 

So ek het nou aan die linkerkant sorteer helfte van hierdie twee elemente. Die linker helfte, natuurlik, is net 4. So hoe kan ek 'n lys van 'n element te sorteer? Wel nou, wat spesiale basis geval up top, om so te praat, is van toepassing. 1 is minder as 2, en my lys is inderdaad grootte 1. So het ek net terug te keer. Ek het nie iets te doen. En inderdaad, kyk wat ek het gedoen het, is reeds 4 gesorteer. Soos ek is reeds gedeeltelik suksesvol hier. 

Nou wat blyk soort van dom te eis nie, maar dit is waar. 4 is 'n lys van die grootte 1. Dit is reeds gesorteer. Dit is die linker helfte. Nou het ek sorteer die regter helfte. My insette is een element, 8 Net so, reeds gesorteer. Dom ook, maar weer, hierdie basiese beginsel gaan ons toelaat om nou te bou op die top van dit suksesvol. 4 gesorteer, 8 gesorteer nou wat was die laaste stap? So het die derde en finale stap, enige tyd wat jy 'n lys te sorteer, onthou, was om die twee helftes saam te smelt, links en regs. So kom ons doen presies dit. My linker helfte is, natuurlik, 4. My reg helfte is 8. 

So laat dit doen. Eerste gaan ek ken 'n paar ekstra geheue, dat ek sal hier verteenwoordig, as net 'n sekondêre skikking, dit is groot genoeg om hierdie te pas. Maar jy kan dink uitbreiding dat reghoek die hele lengte, as ons moet meer later. Hoe kan ek dit neem 4 en 8, en voeg daardie twee lyste van grootte 1 saam? Ook hier eenvoudig. 4 kom eerste, dan kom 8. Want as ek wil die sorteer linkerhelfte, dan die regter helfte, en dan saam te smelt die twee helftes saam in gesorteerde volgorde, 4 kom eerste, dan kom 8. 

So lyk ons ​​maak vordering, selfs al het ek nie gedoen het nie enige werklike werk. Maar onthou waar ons is in die storie. Ons het oorspronklik agt elemente. Ons gesorteer links helfte, wat is 4. Dan gesorteer ons die linker helfte van die linker helfte, wat 2 was. En hier gaan ons. Ons klaar met daardie stap. 

So as ons gesorteer die gelaat helfte van 2, nou is ons het die reg om die helfte van 2 sorteer. So het die regter helfte van 2 is hierdie twee waardes hier, 6 en 2. So laat neem nou 'n inset van grootte 2, en sorteer die linker helfte, en dan die regter helfte, en dan voeg hulle saam. Goed hoe sorteer ek 'n lys van die grootte 1, wat net die nommer 6? Ek is reeds gedoen. Dat die lys van die grootte 1 gesorteer. 

Hoe kan ek 'n lys van sorteer grootte 1, die sogenaamde reg helfte. Wel dit ook reeds gesorteer. Die nommer 2 is alleen. So nou het ek twee helftes, links en reg, ek moet hulle saam te smelt. Kom ek gee myself 'n paar ekstra ruimte. En sit 2 in daar, dan 6 daar, en sodoende sorteer die lys, links en regs, en die samesmelting saam, uiteindelik. So ek is in 'n effens beter vorm. Ek is nie gedoen nie, want duidelik 4, 8, 2, 6 is nie die finale bestel wat ek wil. Maar ek het nou twee lyste van grootte 2, wat albei, onderskeidelik, is gesorteer. So nou as jy rewind in jou gedagtes se oog was, waar het dit ons? Ek het begin met agt elemente, dan sal ek Uiteindelik is dit af na die linker helfte van 4, dan is die linker helfte van 2, en dan is die regter helfte van 2, Ek klaar dus sorteer links helfte van 2, en die regter helfte van 2, so wat is die derde en laaste stap hier? Ek het om saam te smelt twee lyste van grootte 2. So laat ons gaan voort. En op die skerm hier, gee my 'n paar ekstra geheue, al tegnies, sien dat Ek het het 'n hele klomp van die leë ruimte op die top daar is. As ek wil veral wees doeltreffende ruimte wys, Ek kon net begin beweeg die elemente heen en weer, bo en onder. Maar net vir visuele helderheid, Ek gaan dit hier neer te sit, om dinge mooi en skoon te hou. 

So ek het twee lyste van grootte 2. Die eerste lys het 4 en 8. Die tweede lys het 2 en 6. Kom ons saamsmelt diegene saam in gesorteerde volgorde. 2, natuurlik, kom eerste, dan 4, dan 6, dan 8. En nou lyk ons ​​te wees om iewers interessant. Nou het ek gesorteer helfte van die lys, en toevallig, dit is al die ewe getalle nie, maar dat is inderdaad net 'n toeval. En ek nou links het gesorteer helfte, sodat dit is 2, 4, 6 en 8. Niks is buite orde. Dit voel soos die gang. 

Nou is dit voel soos ek het praat nou vir ewig, so wat is nog te sien of dit algoritme is inderdaad meer doeltreffend. Maar ons gaan deur middel van dit super metodies. 'N rekenaar, natuurlik, sou dit doen soos dit. So waar is ons? Ons het begin met agt elemente. Ek gesorteer links helfte van 4. Dit lyk asof ek gedoen word met dit. So nou is die volgende stap is om sorteer die regter helfte van 4. En hierdie deel ons kan gaan deur 'n bietjie meer vinnig, maar jy is welkom om rewind of breek, net dink deur dit op jou eie pas, maar wat ons het nou 'n geleentheid om doen presies dieselfde algoritme op vier verskillende getalle. 

So laat ons gaan voort, en fokus op die regter helfte, wat ons hier is. Die linker helfte van daardie reg helfte, en nou is die linkerhelfte van die linker helfte van daardie reg helfte, en hoe kan ek sorteer 'n lys van die grootte 1 met net die nommer 1? Dit is reeds gedoen. Hoe kan ek dieselfde vir 'n lys te doen grootte 1 bevat net 7? Dit is reeds gedoen. Stap drie vir hierdie half dan is om hierdie twee elemente saam te voeg in 'n nuwe lys van grootte 2, 1 en 7. Lyk nie al gedoen het dat baie interessante werk. Kom ons kyk wat gebeur volgende. Ek het net gesorteer links die helfte van die regter helfte van my oorspronklike insette. Nou laat sorteer die regte helfte, wat 5 en 3 bevat. Kom ons kyk weer na die links helfte, gesorteer, reg helfte, gesorteer, en voeg die twee saam, in 'n paar ekstra ruimte, 3 kom eerste, dan kom 5. En so nou het ons die gesorteer links helfte van die regter helfte van die oorspronklike probleem, en die regter helfte van die regter helfte van die oorspronklike probleem. Wat is die derde en finale stap? Wel om die twee helftes saam te smelt. So laat ek myself kry 'n paar ekstra ruimte, maar, weer, ek kan wees dat die gebruik van vrye ruimte op die top. Maar ons gaan hou dit eenvoudig visueel. Laat my saamsmelt nou 1, en dan 3, en dan 5, en dan 7. Daardeur laat my nou met die regter helfte van die oorspronklike probleem dit is perfek gesorteer. 

So, wat bly? Ek voel soos ek sê hou die dieselfde dinge weer en weer, maar dit is 'n weerspieëling van die feit dat ons gebruik rekursie. Die proses van die gebruik van 'n algoritme weer en weer, op kleiner onderafdelings van die oorspronklike probleem. So ek nou 'n links gesorteer die helfte van die oorspronklike probleem. Ek het 'n reg gesorteer helfte van die oorspronklike probleem. Wat is die derde en laaste stap? O, dit is die samesmelting. So laat dit te doen. Kom ons wys 'n paar ekstra geheue, maar my God, ons kan dit oral nou sit. Ons het so baie ruimte beskikbaar aan ons, maar ons sal dit eenvoudig te hou. In plaas van om terug te gaan en saam met ons oorspronklike geheue, laat ons net dit doen visueel af hier onder, om te voltooi die samesmelting van die linkerhelfte en die regter helfte. 

So deur die samesmelting, wat moet ek doen? Ek wil die elemente in orde. So kyk na die linker helfte, Ek sien die eerste getal is 2. Ek kyk na die regter helfte, Ek sien die eerste getal is 1, so natuurlik wat aantal wil ek uitpluk, en eerste in my finale lys? Natuurlik, 1. Nou wil ek dieselfde vraag vra. Op die linker helfte, ek het nog steeds die nommer 2. Op die regte helfte, Ek het die nommer 3. Watter een wil ek kies? Natuurlik, nommer 2 En Let nou op die kandidate 4 aan die linkerkant, 3 aan die regterkant. Kom ons, natuurlik, kies 3. Nou is die kandidate op 4 links, 5 aan die regterkant. Ons, natuurlik, kies 4. 6 aan die linkerkant, 5 aan die regterkant. Ons, natuurlik, kies 5. 6 aan die linkerkant, 7 aan die regterkant. Ons kies 6, en dan sal ons kies 7, en dan kies ons 8. Voila. 

So 'n groot aantal woorde later, het ons hierdie lys van agt elemente gesorteer in 'n lys van die een deur agt, dit is die verhoging met elke stap, maar hoeveel tyd het dit ons neem om dit te doen. Wel, ek het doelbewus gelê dinge uit picturaal hier, sodat ons kan soort van sien of waardeer die afdeling verower wat alreeds gebeur. 

Inderdaad as jy terug kyk op die nasleep, Ek het al hierdie stippellyne gelaat in houers plek, jy kan, soort, sien, in omgekeerde volgorde, as jy soort van terug kyk in geskiedenis nou, my oorspronklike lys is, natuurlik, grootte 8. En dan voorheen, was ek met twee lyste van grootte 4, en dan vier lyste van grootte 2, en dan agt lyste van grootte 1. 

So, wat dit doen, soort, herinner u aan? Wel, wel, enige van die algoritmes ons het gekyk dusver waar ons verdeel, en verdeel, en verdeel, hou met dinge weer en weer lei tot hierdie algemene idee. En dus is daar iets logaritmiese hier aangaan nie. En dit is nie heeltemal log van n, maar daar is 'n logaritmiese komponent wat ons net gedoen het. 

Nou laat ons kyk hoe dit eintlik is. So teken van n, was weer 'n groot loop van tyd, wanneer ons het iets soos binêre soek, soos ons nou noem, die Verdeel en oorwin strategie via wat ons gevind Mike Smith. Nou tegnies. Dit is log basis 2 van n, selfs maar in die meeste wiskunde klasse, 10 is gewoonlik die basis dat jy aanvaar. Maar die rekenaar wetenskaplikes byna altyd dink en praat in terme van die basis 2, sodat ons oor die algemeen net log van sê n, in plaas van log basis 2 van n, maar hulle is presies een en die dieselfde in die wêreld van die rekenaar wetenskap, en as 'n eenkant, daar is 'n konstante faktor verskil tussen die twee, so dit is akademiese vraag in elk geval, vir meer formele redes. 

Maar vir nou, wat ons omgee oor is hierdie voorbeeld. So laat ons nie te bewys deur byvoorbeeld nie, maar op minste gebruik 'n voorbeeld van die getalle aan die hand as 'n gesonde verstand tjek, as jy wil. So voorheen die formule was log basis 2 van n, maar wat is n in hierdie geval. Ek het n oorspronklike nommers, of 8 van oorspronklike getal spesifiek. Nou is dit 'n bietjie was rukkie, maar ek is redelik seker dat log basis 2 van die waarde 8 is 3, en inderdaad, wat is lekker oor wat wat 3 is presies die aantal kere dat jy 'n lys kan verdeel lengte van 8 weer en weer, en weer totdat jy links is met lyste van net 1 grote. Reg? 8 gaan 4, gaan na 2, gaan na 1, en dit is weerspieël presies dit prentjie wat ons het net 'n oomblik gelede. So 'n bietjie gesonde verstand gaan oor waar die logaritme is eintlik betrokke is. 

So nou, wat anders is hier betrokke? n. So sien dat elke tyd wat ek verdeel die lys, al is dit in omgekeerde volgorde in die geskiedenis hier, ek is nog steeds n dinge doen. Dit samesmelting stap vereis dat Ek raak elke een van die getalle, ten einde dit te skuif in sy toepaslike plek. So selfs al is die hoogte van hierdie diagram is van die grootte log N van N of 3, spesifiek, met ander woorde, Ek het hier drie afdelings. Hoeveel werk het ek gedoen horisontaal langs hierdie grafiek elke keer? 

Wel, ek het n stappe van werk, want as ek het het vier elemente en vier elemente, en ek nodig het om hulle saam te smelt. Ek nodig het om te gaan deur hierdie vier en hierdie vier, uiteindelik tot hulle saamsmelt terug in agt elemente. As omgekeerd ek agt vingers het hier, wat ek nie doen nie, en agt fingers-- sorry-- as ek het vier vingers hier, wat ek doen, vier vingers hier, wat ek doen, dan is dit dieselfde byvoorbeeld as voorheen, as ek dit doen het agt vingers al in totaal, wat ek kan, soort, te doen. Ek kan presies doen hier, Dan kan ek beslis saamsmelt al hierdie lyste grootte 1 saam. Maar ek het beslis te kyk by elke element presies een keer. So het die hoogte van hierdie proses is log n, die breedte van hierdie proses, om so te praat, is N, so wat ons lyk om uiteindelik is 'n lopende tyd van grootte n keer inteken n. 

Met ander woorde, ons verdeel die lys, log N tye, maar elke keer het ons dit gedoen het, het ons aan elkeen van die elemente raak ten einde hulle saamsmelt almal saam, wat is N stap, so ons het n keer inteken n, of as 'n rekenaar wetenskaplike sou sê, asimptoties, wat sou die groot woord na die boonste beskryf gebind op 'n lopende tyd ons hardloop in 'n groot o log N tyd, so te praat. 

Nou is dit belangrik, want onthou wat die loop tye was met borrelsortering, en seleksie soort, en voeg soort, en selfs 'n paar ander wat bestaan, N kwadraat was waar ons was op. En jy kan, soort, kyk hierdie hier. As n vierkant is natuurlik n keer N, maar hier het ons n keer inteken n, en ons weet reeds van week nul, dat log n, die logaritmiese, is beter as iets lineêre. Na alles, onthou die prentjie met die rooi en die geel en die groen lyne wat ons het, is die groen logaritmiese lyn was baie laer. En dus baie beter en vinniger as die reguit geel en rooi lyne, N tye aanteken N is inderdaad 'n beter as n keer n, of n vierkant. 

So lyk ons ​​het geïdentifiseer n algoritme merge soort wat in baie loop vinniger tyd, en inderdaad, dit is hoekom, het vroeër hierdie week, toe het ons gesien dat kompetisie tussen borrel soort, seleksie soort, en voeg sorteer saamsmelt soort regtig, regtig gewen het. En inderdaad, ons het nie eens wag vir borrelsortering en seleksie soort om klaar te maak. 

Nou laat neem een ​​ander pass na hierdie, van 'n effens meer formele perspektief, net in geval, dit resoneer beter as dit 'n hoër vlak bespreking. So hier is die algoritme weer. Kom ons vra onsself, wat die loop van die tyd is van hierdie algoritmes verskillende stappe? Kom ons verdeel dit in die eerste geval en die tweede geval. Die IF en die anders in die geval as, INDIEN N is minder as 2, net terug te keer. Voel soos konstante tyd. Dit is, soort, soos twee stappe, INDIEN N is minder as 2, dan terug. Maar soos ons sê op Maandag, konstante tyd, of 'n groot o van 1, kan twee stappe, drie stappe, selfs 1000 stappe. Wat belangrik is, is dat dit 'n konstante aantal stappe. So die geel uitgelig pseudokode hier loop in, ons sal dit noem, konstante tyd. Sodat meer formeel en ons gaan aan- hierdie sal die mate waarin ons formaliseer hierdie reg now-- T van n, die loop van die tyd van 'n probleem wat neem N Iets as insette, gelyk groot o een, INDIEN N is minder as 2. So dit is op voorwaarde dat. So duidelik, as n minder as 2, ons het 'n baie kort lys, dan die loop van die tyd, T van n, waar n 1 of 0, in hierdie baie spesifieke geval, dit is net gaan om te konstante tyd. Dit gaan om een ​​te neem stap, twee stappe, wat ook al. Dit is 'n vaste aantal stappe. 

So het die sappige deel sekerlik in die ander geval in die pseudokode. Die NÓG geval. Sorteer links helfte van elemente, sorteer reg helfte van elemente, saamsmelt gesorteerde helftes. Hoe lank elk van dié stappe te neem? Wel, as die bestuur tyd om n elemente te sorteer is, kom ons noem dit baie generies, T van n, dan sorteer die linker helfte van die elemente is, soort, soos om te sê, T van N gedeel deur 2, en insgelyks sorteer die regter helfte elemente is, soort, soos om te sê, T van N verdeel 2, en dan die samesmelting van die gesorteer helftes. Wel, as ek het 'n paar aantal elemente hier soos vier en 'n paar nommer elemente hier, soos vier en ek het aan elk van hierdie vier saamsmelt in, en elk van hierdie vier in een na die ander, sodat Ek het uiteindelik agt elemente. Dit voel soos dit is 'n groot o van n stappe? As ek n vingers en elk van het hulle moet saamgevoeg word in plek is, dit is soos 'n ander n stappe. 

So inderdaad formulaically, kan ons dit uit te druk, hoewel 'n bietjie op die eerste scarily oogopslag, maar dit is iets wat vang presies dit logika. Die loop van die tyd, T van n, as n groter as of gelyk aan 2. In hierdie geval, die NÓG geval, is T van N gedeel deur 2, plus T van N gedeel deur 2, plus groot o van N, sommige lineêre aantal stappe, Miskien presies n, miskien 2 keer N, maar dit is 'n harde orde van n. Sodat, ook, is hoe ons kan druk hierdie formulaically. Nou wil jy dit nie weet nie, tensy jy dit aangeteken in jou gedagtes, of kyk dit in die rug van 'n handboek, wat dalk 'n bietjie te hê oneerlik vel aan die einde, maar dit is inderdaad gaan gee ons 'n groot o van n log n, omdat die herhaling wat jy hier sien op die skerm, as jy eintlik het dit uit met 'n oneindige aantal voorbeelde, of jy dit gedoen het formulaically, sou jy sien dat dit, want hierdie formule self is rekursiewe, met t van N oor iets aan die regterkant, en t van N oor aan die linkerkant, kan dit eintlik uitgedruk, uiteindelik, so groot gaan van N log n. Indien nie oortuig nie, dis boete vir nou, net op die geloof, sodat dit is, inderdaad, wat dit herhaling lei tot, maar dit is net 'n bietjie meer van 'n wiskundige benadering tot soek by die loop tyd van merge soort gebaseer op sy pseudokode alleen. 

Nou laat ons neem 'n bietjie van 'n blaaskans van alles, en neem 'n blik op 'n sekere voormalige senator wat kan kyk 'n bietjie bekend, wat gaan sit het met Google se Eric Schmidt, 'n geruime tyd gelede, vir 'n onderhoud op die verhoog, in die voorkant van 'n hele klomp mense, praat uiteindelik oor 'n onderwerp, dis nogal nou reeds bekende. Kom ons neem 'n blik. 

ERIC SCHMIDT: Nou Senator, jy hier is op Google, en ek wil om te dink van die presidentskap as 'n werksonderhoud. Nou is dit moeilik om 'n werk te kry as president. President Obama: Right. ERIC SCHMIDT: En jy is nou gaan doen [onhoorbaar]. Dit is ook moeilik om 'n werk te kry by Google. President Obama: Right. 

ERIC SCHMIDT: Ons het vrae, en ons vra ons kandidate vrae, en hierdie een is van Larry Schwimmer. 

President Obama: OK. 

ERIC SCHMIDT: Wat? Julle dink ek grap? Dit is reg hier. Wat is die mees doeltreffende manier om sorteer 'n miljoen 32 bit heelgetalle? 

President Obama: Well-- ERIC SCHMIDT: Soms miskien is ek jammer, maybe-- President Obama: Nee, nee, nee, nee, nee, ek think-- ERIC SCHMIDT: Dit is nie it-- President Obama: Ek dink, ek dink die borrel soort sou die verkeerde manier om te gaan. ERIC SCHMIDT: Kom op. Wat hom dit vertel het? OK. Ek het nie die rekenaarwetenskap on-- 

President Obama: Ons het het ons spioene in daar. PROFESSOR: Alle reg. Kom ons laat ons nou die agter teoretiese wêreld van algoritmes in die asimptotiese analise daarvan, en terug te keer na 'n paar onderwerpe van week nul en een, en begin om 'n paar opleiding wiele te verwyder, as jy wil. Sodat jy werklik verstaan uiteindelik van die grond af, wat is gaan op onder die kap, wanneer jy skryf, saamstel, en uit te voer programme. Onthou in die besonder, dat dit die eerste C-program het ons gekyk na, 'n kanoniese, eenvoudige program van spesies, relatief gesproke, waarin, dit druk, Hello World. En onthou dat ek gesê het, die proses dat bronkode gaan deur is presies hierdie. Jy neem jou bronkode, slaag dit deur 'n samesteller, soos klang, en kom uit voorwerp kode, wat kan lyk soos hierdie, nulle en ene dat die verwerker, sentrale verwerking van eenheid of brein, uiteindelik verstaan. 

Dit blyk dat dit is 'n bietjie van 'n oorvereenvoudiging, dat ons nou in 'n posisie om uitmekaar te terg om te verstaan ​​wat regtig gaan op onder die kap elke keer as jy hardloop Klang, of meer algemeen, elke keer as jy 'n program te maak, gebruik van Maak en CF 50 IDE. In die besonder, dinge soos dit is die eerste keer gegenereer word, wanneer jy eers jou program saam te stel. Met ander woorde, wanneer jy neem jou bronkode en stel dit wat is die eerste word outputted deur klang is iets wat bekend staan ​​as die gemeente-kode. En in die feit, dit lyk presies soos hierdie. 

Ek hardloop 'n opdrag aan die command line vroeër. Klang Dash kapitaal s hello.c, en dit het 'n lêer vir my geroep hello.s, binnekant van wat presies was hierdie inhoud, en 'n bietjie meer bo en 'n bietjie meer hieronder maar ek het die sappigste sit inligting wat hier op die skerm. En as jy mooi kyk, sal jy sien ten minste 'n paar bekende sleutelwoorde. Ons het groot op top. Ons het in die middel printf. En ons het ook hello world backslash N in aanhalingstekens down hieronder. 

En alles anders in hier is instruksies baie lae vlak dat die verwerker verstaan. CPU instruksies wat geheue beweeg rond, dat die vrag snare van die geheue, en uiteindelik, druk dinge op die skerm. Nou wat gebeur nadat hulle hierdie vergadering kode gegenereer? Uiteindelik, jy doen, inderdaad, steeds genereer voorwerp kode. Maar die stappe wat regtig is aan die gang onder die enjinkap kyk 'n bietjie meer soos hierdie. Bronkode word vergadering kode, wat dan voorwerp kode, en die operatiewe woord hier is dat wanneer jy jou bronkode te stel, kom uit die gemeente-kode, en dan wanneer jy jou gemeente-kode vergader, kom uit voorwerp kode. 

Nou klang is super gesofistikeerde, soos 'n baie opstellers, en dit nie al hierdie stappe bymekaar, en dit nie noodwendig uitset enige intermediêre lêers wat jy kan selfs sien. Dit stel net dinge, wat is die algemene term wat beskryf hierdie hele proses. Maar as jy regtig wil besonder te wees, daar is 'n baie meer gaan daar as well. 

Maar laat ons dit ook oorweeg nou dat selfs dat super eenvoudige program, hello.c, genoem 'n funksie. Dit is dan printf. Maar ek het nie skryf printf, inderdaad, wat kom met c, om so te praat. Dit is 'n funksie herroep wat in die standaard io.h, verklaar wat is 'n kop-lêer, wat is 'n onderwerp sal ons eintlik duik in meer diepte voor lank. Maar 'n kop lêer tipies vergesel deur 'n kode lêer, bronkode lêer, sodat baie soos daar bestaan ​​standaard io.h. 

Rukkie gelede het iemand, of iemand ook geskryf 'n lêer genaamd standaard io.c, in wat die werklike definisies, of die implementering van printf, en trosse van ander funksies, is eintlik geskryf. So gegee dat, as ons kyk na wat hier aan die linkerkant, hello.c, dat wanneer saamgestel, gee ons hello.s, selfs al Klang nie besparing pla in 'n plek ons kan dit sien, en dat die gemeente-kode kry vergader in hello.o, wat is inderdaad die standaard naam gegee wanneer jy bron stel kode in voorwerp-kode nie, maar is nie heeltemal gereed om dit nog te voer, omdat 'n ander stap het om te gebeur, en het gebeur het vir die afgelope paar weke, miskien unbeknownst aan jou. 

Spesifiek iewers in CS50 IDE, en dit, Ook sal 'n bietjie van 'n wees oorvereenvoudiging vir 'n oomblik, daar is, of was op 'n tyd, 'n lêer genaamd standaard io.c, dat iemand saamgestel in standaard io.s of die ekwivalent, dat iemand dan vergader in standaard io.o, of dit blyk in 'n effens verskillende lêer formaat wat 'n ander kan hê lêer uitbreiding geheel en al, maar in die teorie en konseptueel, presies daardie stappe moes gebeur in 'n vorm. Wat is om te sê, wat nou wanneer ek skryf 'n program, hello.c, wat net sê, hello wêreld, en ek die gebruik van kode iemand anders se soos printf, wat eens op 'n was tyd, in 'n lêer met die naam standaard io.c, dan een of ander manier het ek my neem voorwerp kode, my nulle en ene, en voorwerp daardie persoon se kode, of nulle en ene, en een of ander manier hulle mekaar skakel in een finale lêer, genaamd hello, wat het al die nulle en kinders van my hoof funksie, en al die nulle en een vir printf. 

En inderdaad, wat verlede proses is genoem, koppel jou voorwerp kode. Die opbrengs van wat is 'n uitvoerbare lêer. So in regverdigheid, by die einde van die dag, niks het verander sedert week een, wanneer ons eers begin die opstel van programme. Inderdaad, al hierdie is gebeur onder die enjinkap, maar nou is ons in 'n posisie waar ons kan eintlik terg uitmekaar hierdie verskillende stappe. En inderdaad, aan die einde van die dag, ons is nog steeds links met nulle en ene, wat is eintlik 'n groot segue nou na 'n ander moontlikheid van C, wat ons het nie moes waarskynlik hefboom tot op datum, bekend as bis operateurs. Met ander woorde, tot dusver, enige tyd het ons hanteer data in C of veranderlikes in C, ons het dinge gehad soos karakters en dryf en ins en verlang en dubbelspel en dies meer, maar Al wat is minstens agt stukkies. Ons het nog nooit in staat was om manipuleer individuele stukkies, selfs al 'n individu bietjie, ons weet, kan 'n 0 en 'n 1 verteenwoordig. Nou is dit blyk dat in C, jy kan kry toegang tot individuele stukkies, As jy weet wat die sintaksis, waarmee te kry op hulle. 

So laat ons 'n blik by bis operateurs. Hier so uitgebeeld is 'n paar simbole wat ons het, soort van, soort van, gesien nie. Ek sien 'n ampersand, 'n vertikale bar, en 'n paar ander ook, en onthou dat ampersand ampersand is iets wat ons voorheen gesien het. Die logiese EN operateur, waar jy twee van hulle saam, of die logiese OF operateur, waar jy het twee vertikale bars. Bis-operateurs, wat ons sal sien werk op stukkies individueel, net gebruik om 'n enkele ampersand, 'n enkele vertikale bar, die kappie simbool kom die volgende, die klein tilde, en dan links bracket gelaat bracket, of reg bracket reg bracket. Elkeen van hierdie verskillende betekenisse. 

In werklikheid, laat ons neem 'n blik. Kom ons gaan ou skool vandag, en gebruik 'n touch screen van weleer, bekend as 'n wit bord. En dit wit bord gaan ons toelaat sommige redelik eenvoudige simbole uit te druk, of liewer 'n paar redelik eenvoudige formules, dat ons kan dan uiteindelik hefboom, ten einde om toegang tot die individuele stukkies binne 'n C program. Met ander woorde, laat ons dit doen. Kom ons praat vir 'n eerste oomblik oor ampersand, wat is die bis EN operateur. Met ander woorde, dit is 'n operateur wat toelaat my 'n linker veranderlike het Tipies, en 'n regter veranderlike, of 'n individu waarde dat as ons EN hulle saam, gee my 'n finale uitslag. So, wat ek bedoel? As in 'n program, jy het 'n veranderlike wat winkels een van hierdie waardes, of laat ons hou dit eenvoudig, en net skryf nulle en ene individueel, Hier is hoe die ampersand operateur werk. 0 0 ampersand gaan gelyk 0. Nou hoekom is dit? 

Dit is baie soortgelyk aan Boole uitdrukkings, dat ons tot dusver bespreek het. As jy dink na alles, die 0 is valse, 0 is vals, vals en onwaar is, soos ons bespreek het logies, ook onwaar. So kry ons 0 hier. As jy 0 ampersand neem 1, goed dat ook gaan wees 0, want vir hierdie linkerkantse uitdrukking waar of 1 wees, dit nodig sou wees om die ware en waar te wees. Maar hier het ons valse en waar is, of 0 en 1. Nou weer, as ons het 1 ampersand 0, wat ook gaan wees 0, en as ons 1 ampersand 1, uiteindelik het ons 'n 1 bietjie. So met ander woorde, is ons nie te doen iets interessant met hierdie operateur net nog, hierdie ampersand operateur. Dit is die bis EN operateur. Maar dit is die bestanddele via wat kan ons doen interessante dinge, soos ons binnekort sal sien. 

Nou laat ons kyk na net die enkele vertikale bar hier aan die regterkant. As ek 'n bietjie en ek 0 OF dit met die bis OF operateur, 'n ander 0 bietjie, wat gaan om te gee my 0. As ek 'n bietjie en 0 OF dit met 'n 1 bietjie, dan gaan ek om 1 te kry. En in die feit, net vir duidelikheid, laat my terug te gaan, sodat my vertikale bars nie verwar 1 se. Laat my al herskryf my 1 is 'n bietjie meer duidelik, so dat ons volgende sien, as ek het 'n 1 OF 0, wat gaan 'n 1 te wees, en as ek 'n 1 OF 1 dat Ook gaan 'n 1 te wees. Sodat jy kan logies sien dat die OR operateur optree baie anders. Dit gee my 0 OF 0 gee my 0, maar elke ander kombinasie gee my 1. So lank as wat ek een in die 1 formule, is die resultaat gaan wees 1. 

In teenstelling met die EN operateur, die ampersand, net as ek het twee 1 in die vergelyking, ek kry eintlik 'n 1 uit. Nou is daar ''n paar ander operateurs sowel. Een van hulle is 'n bietjie meer betrokke. So laat my gaan voort en vee hierdie om gratis 'n paar ruimte. En laat ons 'n blik op die kappie simbool, vir net 'n oomblik. Dit is gewoonlik 'n karakter wat jy kan tik op jou sleutelbord hou die Shift en dan een van die getalle bo jou Amerikaanse sleutelbord. 

So, dit is die eksklusiewe OF operateur, eksklusiewe OF. So sien ons net die OR operateur. Dit is die uitsluitlike of operateur. Wat is eintlik die verskil? Wel, laat ons net kyk na die formule, en gebruik dit as bestanddele uiteindelik. 0 0 XOR. Ek gaan om te sê is altyd 0. Dit is die definisie van XOR. 0 XOR 1 gaan wees 1. 1 XOR 0 gaan wees 1, en 1 XOR 1 gaan wees? Verkeerd? Of reg? Ek weet nie. 0. Nou wat gaan hier aan? Wel dink oor die naam van hierdie operateur. Eksklusiewe OF, so as die naam, soort van, dui, die antwoord is net gaan wees 'n 1 as die insette is eksklusiewe, uitsluitlik anders. So hier is die insette is die dieselfde, so die produksie is 0. Hier is die insette is die dieselfde, so die produksie is 0. Hier is die uitgange is anders, hulle is eksklusief, en so die produksie is 1. So dit is baie soortgelyk aan En, dit is baie soortgelyk, of eerder dit is baie soortgelyk aan OF, maar slegs in 'n eksklusiewe manier. Hierdie een is nie meer 'n 1, want ons het twee 1 se en nie uitsluitlik nie, maar net een van hulle. Alles reg. Wat van die ander? Wel, die tilde, intussen, is eintlik mooi en eenvoudige, gelukkig. En dit is 'n unêre operateur, wat beteken dit toegepas word om net een insette, een operand, om so te praat. Nie om 'n links en regs. Met ander woorde, as jy tilde neem 0, sal die antwoord die teenoorgestelde. En as jy tilde van 1, die antwoord daar die teenoorgestelde wees. So die tilde operateur is 'n manier om die ontkenning van 'n bietjie, of daarby 'n bietjie uit 0-1 of 1-0. 

En dat ons uiteindelik verlaat met net twee finale operateurs, die sogenaamde links verskuiwing en die sogenaamde reg verskuiwing operateur. Kom ons neem 'n blik op hoe die werk. Links verskuiwing operateur, geskryf met twee hoek tussen hakies soos dit, bedryf as volg. As my insette, of my operand, aan die linkerkant verskuiwing operateur is eenvoudig 'n 1. En ek vertel dan die rekenaar links verskuiwing wat 1, sê sewe plekke, die resultaat is asof ek neem dat 1, en beweeg dit sewe plekke oor die links, en by verstek, ons gaan om te aanvaar dat die ruimte om die regte gaan word opgestopte met nulle. Met ander woorde, 1 links verskuiwing 7 gaan gee my dat 1, gevolg deur 1, 2, 3, 4, 5, 6, 7 nulle. So op 'n manier, dit laat jou neem 'n klein aantal soos 1, en maak dit baie duidelik baie, baie groter op hierdie manier, maar ons is eintlik gaan om te sien meer slim benaderings want dit plaas, asook, 

Alles reg. Dit is dit vir week drie. Ons sal jy sien die volgende keer. Dit was CS50. 

[Speel van musiek] 

Spreker 1: Hy was by die snack bar eet 'n warm fudge sundae. Hy het dit alles oor sy gesig. Hy dra dat sjokolade soos 'n baard Spreker 2: Wat doen jy? SPREKER 3: Hmmm? Wat? 

Spreker 2: Het jy net dubbel dip? Jy gedoop dubbel die chip. SPREKER 3: Verskoon my. Spreker 2: Jy steek die chip, jy het 'n byt, en jy weer gedoop. SPREKER 3: Spreker 2: So dit is soos om jou hele mond reg in die dip. Volgende keer as jy 'n chip te neem, net steek dit een keer, en eindig dit. 

SPREKER 3: Jy weet wat, Dan? Jy steek die pad wat jy wil om te duik. Ek sal die pad wat ek wil om te duik steek.