Spreker: Alle reg, dit is CS50. Dit is die einde van die week, drie, en as jy nie gebruik reeds weet dat daar sal middagete wees Vrydag soos gewoonlik, waar jy kan 'n goeie gesprek geniet en kos by Vuur en ys met 'n paar van die CS50 se personeel en klasmaats. Kop aan hierdie URL hier. Nou kan jy onthou, of jy kan binnekort bekend wees met, hierdie dinge hier, wat word aan die einde van die semester vir baie klasse. Sogenaamde eksamen blou boeke, waarin jy skryf jou antwoorde op eksamens. Nou het ek hier 26 sulke blou boeke, op elkeen van hulle is geskryf om 'n naam, 'n deur Z. En inderdaad die name is so eenvoudig, 'n deur Z. En een van die doelwitte aan die hand vandag gaan wees om voort te gaan wat ons begin op Maandag, wat nie soveel op soek na kode, maar eintlik op soek na idees en probleemoplossing. Een van die doelwitte en beloftes van hierdie kursus is om jou te leer om meer te dink versigtig, meer metodies, en probleme meer doeltreffend op te los. En inderdaad, kan ons doen wat werklik selfs sonder aanraking van 'n reël van die kode. So ek het 'n paar van die olifante tot vandag hier, oranje en blou, As ons een vrywilliger kry, miskien uit verder terug as gewoonlik. Hoe gaan net daar, kom neer. Die doel van die wat gaan wees om te help plus administreer die eksamen hier. Wat is jou naam? Publiek: Mary Beth. Spreker: Mary Beth, kom op. Laat my die mikrofoon hier vir jou. Nice om jou te ontmoet. Publiek: Nice om jou te ontmoet. Spreker: Alle reg, so ek het hier blou boeke 'n deur Z, en ek gaan om voor te gee Ek het een van die studente, en hulle kom in ietwat lukraak aan die einde van 'n drie-uur eksamen blok, sodat hulle eindig in sommige semi-ewekansige volgorde soos hierdie. Nou jou werk in net 'n oomblik gaan te be-- dit is eintlik hoe hulle kry het aan die einde van die klas, waarskynlik. Jou werk is nou gaan wees, heel eenvoudig, hierdie blou boeke vir ons om te sorteer van 'n deur Z. Publiek: O, dit is vir ewig gaan neem. Spreker: En ons sal sien as jy dit doen, geen druk. Publiek: Nee, geen druk of iets nie. Spreker: En vir die pret, Kom ons stel 'n timer. Publiek: Soveel pret, soveel pret. Spreker: Ek kan die mic hou vir jou. Alle reg, ons het net verdubbel ons spoed. So in die tussentyd, laat my inhou wat is gaan die vraag vir Mary Beth te wees is wat sy doen, hoe sy gaan oor die belangrikheid van hierdie? En in werklikheid is, kan jy nie ' ooit gedink oor iets so eenvoudig soos wanneer jy kies tot 26 boeke soos hierdie, wat 'n natuurlike nie bestel vir hulle. Wat is die proses dat jy eintlik gebruik? Is dit redelik ewekansige net pluk die eerste een wat jy sien en sit dit op sy plek? Moenie eers beweeg jou hande om soek na 'n dan op soek na B? Neem jy 'n blik op 'n paar van hulle langs mekaar en net sê, wag 'n minuut, hierdie nie reg is nie, en dan ruil die einde? Ons het reeds op Maandag dat daar 'n aantal van maniere waarop ons kan dit doen, en inderdaad as ons naby die einde hier Ek sou kennis neem dalk van wat Mary Beth doen. Ons het 'n paar hope lyk dit, 'n groter een, drie kleintjies. Publiek: Ek beveel hulle toe ek vind twee letters dat ek weet is saam in 'n ry, Ek sit hulle saam sodat ek dit nie doen nie hoef te bekommer oor die hou van spoor van 'n hele ry van boeke. Dis net, ag, 'n eerste keer, Ek het hierdie stapel hier. Spreker: So, amper soos 'n legkaart stukke wat het die reg om vorm te ooreenstem met mekaar. Publiek: Pretty much, ja. Spreker: OK, 'n uitstekende. En nou elk van hierdie hope is vermoedelik gesorteer? Publiek: Ja. Spreker: Alle reg, 'n deur Z. Alle reg, baie geluk, jy het dit gedoen. Jy het jou keuse. Blou? Alle reg, dankie vir dit. So Mary Beth het stel wat haar benadering was, Maar wat is 'n ander benadering hoe jy dalk gaan sorteer hierdie dinge? Wat sou jy gedoen het? Die rekord te klop sou gewees het een minuut en 50 sekondes of so, plus die wat ek vergeet het om te tel. Wat sou jy gedoen het? Ja? Publiek: Neem die stapel. Begin van die begin af. Gaan jou vraestelle. En as die boonste een is hoër as, miskien, hulle is, Die onderste een is hoër is, dan skakel hulle. Spreker: OK, so begin aan die bokant en die onderkant, en dan werk jou pad innerlike soos daardie, uitruiling hulle? OK, so 'n bietjie soortgelyk in gees borrel soort, maar die keuse van die uiterstes nie die aangrensende pare. Maar die kort daarvan is dat daar sekerlik 'n klomp van die verskillende maniere ons dit kan doen, en eerlik, ek dink jy soort het 'n paar benaderings, reg? Jy het soort van vier gesorteer gebied, en dan effektief saamgesmelt saam. En dit is, daresay, 'n ander tegniek heeltemal. Jy het nie hanteer dit as 'n groot hoop, om die probleem verdeel in vier quads, as jy wil, en dan een of ander manier saamgevoeg in die einde. So laat ons kyk, uiteindelik, hoe anders ons kan dit doen. Ons geformaliseer die idee van die borrel soort laaste keer, en borrel soort onthou was 'n algoritme wat ons gevisualiseer met agt van jou klasmaats hier, oënskynlik lukraak gesorteer by die eerste. En ons het toe besluit om twee-, indien twee elemente is buite orde, eenvoudig ruil hulle. So vier en twee natuurlik buite orde, sodat die twee klasmaats aangeskakel posisies. En dan moet ons herhaal met vier en ses, dan ses en agt, op elke iterasie, beweeg na regs. So het agt mense, hoeveel paarsgewyse vergelykings het ek gedoen terwyl loop uit links na regs in een so 'n herhaling? Hoeveel vergelykings? Sewe, reg? Want as daar agt mense nie, maar jy het die paar hulle, en jy bly beweeg een hop aan die regterkant, jy gaan nie agt te hê vergelykings, want jy kan nie vergelyk 'n element wat teen homself is, of dit sou net nutteloos, so jy het sewe. Of meer algemeen, as ons n volk, ons doen n minus 1 vergelykings met borrel soort. So laat ons nou kyk hoe goed of slegte borrel soort eintlik was, en probeer onsself te gee woordeskat met wat tot kritiek algoritmes soos hierdie, en gou ons eie. So het die eerste keer deur borrel soort, die eerste keer Ek loop van links na regs oor die stadium, het my n minus 1 vergelykings. En dit gaan wees my eenheid van meet, reg? Ek was soort van praat en loop, ietwat vinnig, ietwat stadig, so toe my nommer van sekondes is veral nie vertel, maar toe die aantal bedrywighede wat ek gedoen het op Maandag, twee mense te vergelyk, wat voel soos 'n mooi eenheid van meet. So n minus 1 stappe die eerste keer, maar dan wat gebeur daarna? Wat is die een onderstebo van 'n pas deur 'n andersins ongesorteerde lys? Wat kan jy my vertel oor die element wat al die pad oor daar? Ja? Dit was die grootste element, reg? Nommer agt, selfs al het sy begin hier, elke keer as ek vergelyking om haar teen 'n buurman, het sy borrel tot aan die regterkant kant van die lys. En inderdaad, dit is waar die algoritme kry sy naam. Nou deur daardie logika, hoeveel vergelykings moet ek op die tweede keer Ek maak dat die slaagsyfer van links na regs? N minus 2, reg? Dit sou net mors my tyd as ek hou vergelyk agt teen iemand anders omdat ons reeds weet Sy was op die regte plek. So dit is 'n bietjie van 'n optimalisering, sodat die volgende slaag gaan wees plus N minus twee stappe, waar n die aantal mense. Nou kan jy soort van ekstrapoleer, selfs As jy nie 'n rekenaar wetenskaplike, hoe dit eindig. Aan die einde van hierdie algoritme, vermoedelik jy het net een vergelyking gelaat. Jy moet soort los die begin van die lys in die geval twee en een is buite orde en moet een en twee, so hierdie Bottoms uit op plus 1 finale vergelyking. Nou is die dot, dot, dot soort van golwe is dit hande op 'n paar van die sappiger besonderhede, maar laat ons net voort te gaan en te vereenvoudig. As jy onthou van 'n hoë skool, eerlik, baie van julle het wiskunde boeke wat moes 'n bietjie oneerlik blad op die voorblad of die agterblad wat gewys het jy wat reeks opsommings soos Dit het uiteindelik bygevoeg tot. In die algemene geval, as jy 'n veranderlike soos n, en inderdaad hierdie een, As jy kyk na jou ou skool wiskunde boek, jy sal sien dat dit eintlik voeg tot hierdie bedrag hier n keer n minus 1 al gedeel deur 2. So vir nou laat my net stipuleer dit waar is, so op 'n sprong van geloof, dit is wat dit neerkom tot, en ons kon bewys dat in 'n meer algemene geval. Maar laat ons nou uit te brei dit uit. So laat vermenigvuldig dit uit, so dit is N vierkantig minus n, al gedeel deur 2. Dit is regtig n vierkant, gedeel deur 2, minus n meer as 2, so dit is al wat mooi en interessant. Maar wat gebeur as ons nou prop-in 'n waarde? Dink ek het nie agt mense nie, maar sê 'n miljoen. En 'n miljoen net omdat dit is 'n mooi groot aantal, laat se prop wat in en kyk wat gebeur. So as ek prop 'n miljoen in die formule Ek gaan 'n miljoen vierkantig gedeel deur 2, minus 'n miljoen, gedeel deur 2. Nou wat is dit gaan gelyk? So 500000000000, minus 500,000. En as ek doen dat wiskunde nie, dit beteken dat sortering 'n miljoen mense met die borrel soort kon neem my 499999500000 stappe of vergelykings in die einde, ons is maar net ekstrapoleer. Dit voel redelik stadig, maar eerlik meet 'n spesifieke insette soos hierdie, is nie al wat vertel. Maar wel dit dui daarop dat as n kry groter en groter, die algoritme soort van voel erger en erger, of jy regtig begin die pyn van daardie te voel magsverheffing, wat n vierkant, wat bydra tot redelik vinnig. En hierdie detail is nie verloor op mense, in werklikheid 'n paar jaar gelede het 'n sekere senator wat veldtog, gaan sit vir 'n onderhoud Google se Eric Schmidt, uitvoerende hoof van die tyd, en is uitgedaag met 'n vraag baie soos ons vandag verken. Kom ons neem 'n blik. [Video speel] -Senator, Jy is hier op Google, en ek wil graag om te dink aan die presidensie as 'n werksonderhoud. Nou, dit is moeilik om te kry 'n werk as president, en jy gaan deur middel van die pogings nou. Dit is ook moeilik om 'n werk te kry by Google. Ons het vrae, en ons vra ons kandidate vrae, en hierdie een is van Larry Schwimmer. What-- julle dink ek is grap, dit is reg hier. Wat is die mees doeltreffende manier om te sorteer 'n miljoen 32-bit heelgetalle? -Well-- I 'm sorry, maybe-- Nee, nee, nee. Ek dink die borrel soort sou die verkeerde manier om te gaan. -Come Op, wat hom hierdie vertel? Ek het nie rekenaar sien wetenskap in jou agtergrond. -We've Het ons spioene in daar. -OK, Laat ons vra 'n ander onderhoud vraag. [Einde video speel] Spreker: So praat spesifieke getalle egter is nie van plan om alles wat nuttig is. Dit is nie 'n lewe les wat borrel soort, gegewe 'n miljoen insette, soveel as 500000000000 stappe te neem. Jy kan regtig nie veralgemeen te doeltreffend uit daardie en maak 'n goeie ontwerp besluite wanneer die skryf van programme. So laat se fokus al hoe ons kan hierdie resultaat vereenvoudig. Daarom het ek in geel uitgelig hier die gevolg van n kwadraat gedeel deur 2, so 'n miljoen vierkant gedeel deur 2, en dan Ek het uitgelig wat die uiteindelike antwoord was Sodra ons afgetrek af N gedeel deur 2. En die eis gaan ek nou maak, is, wat die heck omgee as jy trek af 'n klein ou n meer as 2 toe die eerste deel van hierdie formule is soveel groter? Dit oorheers die ander term, n kwadraat gedeel deur 2 is soveel groter, duidelik, soos N kry groot soos 'n miljoen, dit is daar werklik 'n groot verskil aan die einde van die dag tussen 500000000000 en 499999500000? Nie regtig nie. En ja, wat ons gaan doen as die rekenaar wetenskaplikes is ignoreer die laer orde terme en neem iets soos hierdie en baie net vereenvoudig dit tot die term wat gaan saak maak nie. Die groter ons data stelle kry, hoe groter ons databasis, hoe meer webblaaie ons het, hoe meer om te soek vriende wat jy het op Facebook. As n groter word, ons is baie gaan omgee oor die grootste term in enige sodanige ontleding van ons algoritmes prestasie. En ek gaan om te sê, jy weet wat, borrel soort is aan die orde van die groot O, op die einde van n vierkant. Dit is nie presies n vierkantig soos ons gesien het, maar wat regtig omgee oor die kleiner terme, en eerlik, wat werklik omgee as ons deur 2? Dit is net 'n konstante faktor. En is 500000000000 teenoor 250 miljard regtig so groot van 'n deal? Ek kon net wag 'n jaar, laat my laptop letterlik kry twee keer so vinnig in hardeware, en dat die soort van verskil gaan net weg natuurlike verloop van tyd. Wat ons omgee is die uitdrukking, die deel van die uitdrukking wat gaan verskil as ons insette kry groter en groter. En inderdaad, in die werklike wêreld, dit is wat toenemend gebeur is die insette van ons probleme en algoritmes word al hoe groter. So groot O gaan die notering te wees, die asimptotiese notasie, dat ons net gebruik as die rekenaar wetenskaplikes te beskryf die prestasie of die loop van die tyd, van 'n algoritme. Sodat ons algoritmes kan vergelyk op verskillende rekenaars geskryf deur verskillende mense, deur die gebruik van sommige fundamenteel soortgelyke metrieke soos die aantal vergelykings jy maak, of dalk die aantal swaps jy maak. Wat ons gaan nie telling is die bedrag van die tyd wat verby op die klok op die muur tipies. Wat gaan ons nie te bekommer is oor hoeveel geheue vandag is die gebruik by minste, al is dit 'n ander bron wat ons kan meet. Ons gaan probeer om ons ontleding te baseer op net die basiese operasies, die kinders, eerlik, dat jy die meeste visueel kan sien. So iets soos 'n groot O van n vierkantig, ek beweer dat O van n vierkant 'n bogrens op die sogenaamde loop van die tyd van die borrel soort. Met ander woorde, as jy wou beweer dat daar hierdie boonste limiet op hoeveel stappe om 'n algoritme te neem, dit gaan wees in die groot O van n vierkantig in hierdie geval, 'n bogrens. Wat gebeur as ek plaas verander die storie te wees nie oor borrel soort, maar oor hierdie bogrens. Kan jy dink aan 'n algoritme dat ons het gekyk na al wie se bogrens, maksimum meet van die tyd of bedrywighede, sou gesê word begrens word deur n, 'n lineêre funksie, nie 'n kwadratiese een wat geboë? Wat is 'n algoritme wat vind altyd nie meer as soos n stappe, of 2n stappe, of 3n stappe? Ja? Publiek: Dit vind van die grootste getal in 'n lys? Spreker: Perfect, vind die grootste aantal in 'n lys. As ek 'n lys van mense byvoorbeeld elk van wat hou van 'n nommer, Wat is die maksimum aantal van stappe om dit vir my te neem, 'n redelik slim persoon, die grootste persoon in die lys te kry? n, reg? Want in die ergste geval, waar dalk die grootste waarde wees? Reg, al die pad aan die einde. So in die ergste geval boonste gebind, ek kan het al die pad om te gaan hier en wees soos, O ja, hier is nommer agt, of wat ook al wat waarde is. Nou is dit net dom wees As ek aan die gang gehou het, reg? Op soek na meer en meer elemente As die laaste van hulle is daar? So sekerlik, n 'n bogrens is. Ek het nie nodig om te neem meer stappe as dit. So, wat as plaas ek voorgestel dat daar algoritmes in hierdie wêreld wat 'n loop van die tyd wat begrens deur die groot O van log n, teken n? Waar het ons voorheen gesien het nie? Ja? Publiek: In die telefoon boek probleem? Spreker: Soos die telefoon boek probleem. Wat was die maatstaf van hoe veel tyd of hoeveel trane dit het my iemand soos om uit te vind Mike Smith in die telefoon boek? Ons het beweer dit was log n, en selfs as onbekende of dit dit is 'n bietjie vaag wat 'n logaritme of eksponent was, net onthou dat log N algemeen verwys na die proses, in hierdie geval, verdeel iets weer in die helfte, en weer, en weer, en weer, soos wat dit kry toenemend klein as jy dit doen. So teken van N verwys, seker, na die telefoon boek byvoorbeeld binêre soek in teorie, wanneer ons het die virtuele deure op die raad, of wanneer Sean was soek vir iets. As hy binêre soek gebruik het, teken n die bogrens van hoeveel sou wees tyd wat neem. Maar daardie algoritmes wat gehardloop in log n aanvaar wat die sleutel detail? Dat die lys is gesorteer, reg? Jou algoritme is verkeerd as jou insette is nie gesorteer, en nog wat jy gebruik iets soos binêre soek omdat jy dalk te spring reg oor die element sonder om te besef dit is inderdaad daar. Nou wat kan dit beteken, groot O van die een? Dit beteken nie dat jou algoritme neem een ​​en slegs een stap, dit beteken net dit neem om 'n konstante aantal stappe. Miskien is dit 1, miskien is dit 10, miskien is dit 1000, maar dit is onafhanklik van die omvang van die probleem. Maak nie saak hoe groot n is, 'n konstante tyd algoritme neem altyd dieselfde aantal stappe. So wat kan 'n algoritme wees ons het gepraat oor of net intuïtief wat kom om jou wat altyd loop in die sogenaamde konstante tyd? Ja? GEHOOR: Voeg twee getalle. Spreker: Voeg twee getalle, 2 plus 2 is gelyk aan 4, gedoen. So wat kan werk, wat anders? Hoe gaan meer werklike wêreld, ja? Publiek: Dit vind van die eerste ding wat in 'n lys. Spreker: Dit vind van die eerste element in 'n lys, seker nie. Ons het eintlik gepraat oor skikkings reeds hoe kry jy by die eerste element in 'n skikking, maak nie saak hoe lank die skikking is in C-kode? Jy moet net gebruik soos die bracket nul notasie, bam, jy is daar. En inderdaad skikkings, as 'n eenkant, ondersteuning iets algemeen bekend as ewetoeganklike, ewetoeganklike geheue, want jy kan letterlik spring na enige plek. Ons kan eenvoudig dit doen nog meer Ons kan rewind te week nul toe ons nuuts af. Hoeveel tyd het dit vir die sê blok in Scratch uit te voer? Net konstante tyd, reg? Sê iets, sê iets, beteken dit nie saak nie hoe groot skrape wêreld is, is dit altyd gaan dieselfde hoeveelheid tyd te neem om net iets sê. So dit is konstante, maar wat is die ander kant? As dit was bo grense, wat as ons wil die laer perke te beskryf van ons algoritmes loop van die tyd? Byna 'n beste geval potensieel, as jy wil, al hierdie terme kan aansoek doen om die beste gevalle ergste gevalle, gemiddelde gevalle meer algemeen nie, maar laat ons net fokus op die laer perke meer algemeen. Wat is 'n algoritme wat 'n laer grens van N stappe, of 2n stappe, of 3n stappe? Sommige faktor van N stappe, dit is sy ondergrens. Ja? Publiek: borrel soort? Spreker: borrel soort neem jy minimaal n stappe, hoekom? Hoekom is dit? Hoekom moet dit begin om vir jou te kom intuïtief, selfs al is dit nie net nog? Ja? Publiek: [onhoorbaar]. Spreker: Presies. In die beste moontlike scenario van borrel soort, en 'n baie van algoritmes, As ek vir julle agt mense wat reeds gesorteer, dit sou dom wees vir jou, die algoritme, heen en weer te gaan meer as een keer, reg? Want sodra jy loop deur die lys een keer, jy moet besef, o, ek het geen swaps, is hierdie lys gesorteer, afrit. Maar wat gaan jy n stappe te neem. En omgekeerd, wat is 'n ander manier van dink oor dit? Borrel soort is 'n omega, so te sê, van N, want as jy kyk na minder as N elemente, wat is die fundamentele kwessie is daar? Jy weet nie of dit gesorteer, reg. Ons mense mag blik op agt mense en wees soos, O, dit is gesorteer, dit het nie neem my n stappe, maar dit het. Jou oë, selfs al is jy soort van 'n groot gebied van die visie, jy kyk na agt elemente, jy kyk na agt mense, dit is agt stappe effektief. En net as ek loop deur die hele lys besef ek, ja, gesorteer. As ek stop halfpad dink, al reg, dit is mooi so ver gesorteer, wat is die kans is dit nie gesorteer? Dit algoritmes gaan nie korrek te wees. Dalk vinniger, maar verkeerd. So nou het ons 'n manier om beskrywing van 'n laer perke, En wat van konstante tyd? Wat is 'n algoritme wat 'n laer gebind op sy lopende tyd van die een? 1 stap, 2 stappe, 10 stappe, maar konstant, onafhanklik van N, die grootte van die insette? Ja, in die rug. Publiek: printf? Spreker: Wat is dit? Publiek: printf? Spreker: printf. OK, seker nie. So dit neem 'n vaste aantal stappe. En ek moet nou dat now-- ons praat oor C-kode en nie krap iets soos byvoorbeeld met printf, ons moet begin versigtig te kry. Omdat printf neem nie insette, dit is 'n string, en snare tegnies het lank nie. So as ons nou wil kies op jou, as jy nie omgee nie, tegnies kon ons dat printf argumenteer neem nie 'n veranderlike lengte insette, en sekerlik kan dit neem meer tyd om 'n string te druk hierdie lang, as dit lank. So wat as ons kyk na net die sorteer en soek voorbeelde? Wat van Mike Smith in die telefoon boek, of binêre soek meer in die algemeen? In die beste geval, wat kan gebeur? Ek maak die telefoon boek en bam, daar is Mike Smith se nommer. Ek kan hom bel dadelik. Het 'n stap, miskien twee stappe, maar 'n konstante aantal stappe As ek gelukkig. En eerlik, het ons gesien op Maandag jou klasmaat kry baie gelukkig twee keer in 'n ry. En dit was inderdaad konstante keer in 'n laer perke op die algoritme in die vraag vir die vind van die nommer 50 agter die geslote deure. Nou, as 'n eenkant, as jy ontdek dat beide groot O, die bogrens, en omega, die laer gebind, is een in dieselfde, wat is dieselfde formule in hakies, jy kan ook sê, net om te fancy nie, dat daar iets in theta van N of theta van 'n ander waarde. Dit beteken net wanneer groot O en omega is dieselfde. Nou wat van seleksie soort? Kom ons gebruik hierdie nuwe woordeskat. In seleksie soort, wat ons was doen weer, en weer en weer? Ek is heen en weer gaan deur die lys, op soek na wie? Die kleinste getal. So hoeveel stappe, hoe baie vergelykings het ek moet maak om uit te vind wat die kleinste element in die lys was? N minus 1, reg? Want as ek net begin met die een wat ek gegee en ek begin vergelyk hom of haar, dan moet julle hom of haar, hom of haar, hom of haar, ek kan slegs elemente paar saam n minus 1 keer. So keuring soort soortgelyke N minus 1 stappe die eerste keer. Hoeveel stappe neem dit om my te vind die tweede kleinste element? N minus 2, want ek is die stom As ek bly kyk na die dieselfde mense weer as ek het hom reeds gekies of haar en sit hulle in hul plek. En die derde stap, n minus 3, dan n minus 4. Ons het gesien hoe hierdie patroon voor, en wel seleksie soort soortgelyke 'n bogrens N vierkant as ons dit doen tot dat opsomming. Wat is die ondergrens, seleksie soort? Minimaal, hoeveel tyd moet seleksie soort neem, soos ons dit gedefinieer op Maandag? Stel twee opsies. Miskien is dit n, soos voorheen. Miskien is dit n vierkant, as dit is nou as die bogrens. Publiek: N vierkant. Spreker: N vierkant. Hoekom? Publiek: Omdat jy te definieer [onhoorbaar]. Spreker: Presies. Ten minste as ek gedefinieer seleksie soort dit was 'n bietjie naïef, hou, vind die kleinste element. Gaan weer, vind die kleinste element. Gaan weer, vind die kleinste element. Daar is geen soort optimalisering daar wat dalk laat my staak nadat net n of so stappe. So inderdaad, seleksie soort, omega van N vierkant. Wat van invoeging soort, waar ek het wat ek gegee is, en dan het ek plons hom of haar in die regte plek? Toe voortgegaan ek na die tweede persoon, plons hom of haar in die regte plek. Toe het die volgende persoon, plons hom of haar in die regte plek. Let daarop dat hierdie is baie lineêre, om so te praat. Ek is 'n reguit lyn, ek is nie heen en weer gaan, Ek het nog nooit terug kyk regtig nie, maar wat gebeur wanneer ek plaas hom of haar in die begin van die lys soos ons gedoen het op Maandag? Wat gebeur? Ja? Publiek: [onhoorbaar]. Spreker: Ja, dit was die vangs, reg? Jy kan onthou uit jou klasmaats, indien hulle is om enige beweging met hul voete, dit was 'n operasie. So as daar drie mense hier en die nuwe mens behoort manier daar, op 'n lang fase soos hierdie, seker, hy of sy kan net gaan na die einde. Maar as ons dink oor 'n rekenaar en 'n verskeidenheid van die geheue, hierdie mense gaan te hê om te skuif oor ruimte vir daardie persoon te maak. En sodat n minus 1 shufflings, N minus 2 shufflings, n minus 3 shufflings is net soort van gebeur agter my, nie in die voorkant van my soos voorheen, in 'n sekere sin. Nou as 'n eenkant, en as Jy kan gesien het aanlyn As jy begin skeer rond oor vorme, daar is so baie verskillende kinders daar is, sommige van hulle beter as ander. Inderdaad, bogosort is een dit is soort van pret om te kyk. Bogosort neem 'n stel nommers of sê 'n pak kaarte, lukraak skud hulle, en tjeks as hulle gesorteer. En indien nie, doen dit weer. En indien nie, doen dit weer. Indien nie, doen dit weer. Ongelooflik dom. En inderdaad, as jy lees soos die Wikipedia artikel, sy bynaam is dom soort. Dit sal uiteindelik werk hopelik, gegewe genoeg tyd, maar dat die bedrag van die tyd kon 'n geruime tyd in beslag neem. So as ek kon, laat se spoed dinge uit Mary Beth se voorbeeld vroeër, deur 'n paar elemente, maar twee verwerkers. Twee mense, as jy sal nie omgee om saam met my. Hoe oor 1 hier, en laat se go-- niemand daar? Niemand daar? OK. Jy met die swart hemp, ja, kom neer. Alle reg, wat is jou naam? Publiek: Peter. Spreker: Wat is dit? Publiek: Peter. Spreker: Peter, David, lekker om te ontmoet. Alle reg, ons het Petrus hier, as jy wil kom op die tafel hier. En wat is jou naam? Publiek: Elena. Spreker: Elena. OK, lekker om jou te ontmoet. Elena ontmoet Peter. Peter, Elena. En ons sal moet Andrew hier so goed, asseblief. En jou uitdaging gaan te wees van 'n dek van kaarte te sorteer. En as onbekende, dek kaarte moet uiteindelik word gesorteer 'n bietjie iets soos dit waar ons die klubs sal doen, dan die grawe, die harte en diamante, van kampioen as 'n een, al die pad tot by die koning. Die kaarte wat ek gaan gee jou gaan wees 52 in die hoeveelheid. Ons gaan insgelyks tyd wat jy in net 'n oomblik. Ons gaan Andrew te gooi op die skerm hier so as om te kyk as jy dit doen. En so dat al hierdie is al hoe meer sigbaar, dit is die kaarte wat ek het op Amazon. So hulle is reeds lukraak gesorteer, en ons gaan vir jou tyd. En ons gaan hou dit real hierdie tyd, sodat ons gaan probeer om jou te druk want anders sal kry vervelige vinnig. As jy kan voortgaan 52 te sorteer elemente saam via 'n middel, wat nou. En weer, as ons kyk na hierdie ouens doen wat, in die einde gaan 'n voor die hand liggend te produseer Gevolglik dink regtig hoe hulle mekaar om dit te doen, hoe jy dit beskryf. Omdat weer, dit is alle prosesse, algoritmes wat ons as vanselfsprekend aanvaar as 'n mens. Maar jy het waarskynlik lank het intuïsie, lank voor jy gedink om 'n Rekenaarwetenskap klas wat jy kan die aanvoeling gehad het met wat probleme soos hierdie op te los. Maar sodra jy erken die patrone en begin die stappe wat met die formalisering jy die oplossing van hierdie probleme, jy sal vind dat jy baie kan oplos meer interessant en baie meer kompleks probleme vinnig. So iemand uit die gehoor, wat ten minste een element van die algoritme dat hulle hier is die gebruik van? Publiek: [onhoorbaar] Spreker: Wat is dit? Publiek: Deur pak. Spreker: Deur pak. So eerste hulle die groepering al die diamante saam dit lyk, al die harte saam dit lyk, en so meer, sonder opsigte vir die nommers op die kaarte. En nou het hulle verskyn, byvoorbeeld, word sorteer hulle deur die nommer. Baie goed. Alle reg, so wat gaan wees om die finale stap dan hier? Sodra ons het vier gesorteer pas, wat moet ons die vier stapels te doen om een ​​te bereik gesorteer dek, eenvoudig? Daarom moet ons dit weer saam te smelt. So daar is 'n interessante idee dat weer, daresay, is baie intuïtief selfs As jy dalk nooit geklap het dat die soort van etiket op dit. Hierdie fundamentele idee van die verdeling die probleem nie in die helfte van hierdie tyd, maar ten minste in vier stukke. Oplossing van pretty much fundamenteel dieselfde probleme in isolasie van mekaar, en dan die samesmelting van die resultate. En, 'n uitstekende, gedoen. Alle reg, 'n groot ronde applous, as ons kon. [Applous] Spreker: Ek het nie 'n idee wat jy sal doen met hierdie, maar hier gaan ons. Baie dankie. So laat ons sien, twee minute en agt sekondes As jy wil jou vriende uit te daag. Wat dan gaan 'n weg te neem van hierdie dat ons meer in die algemeen kan benut? Wel, dink terug aan hierdie skikking van getalle, en dink nou terug aan sommige van die pseudokode ons in die verlede geskryf het, en dit was die pseudokode vir die oplossing van die telefoon boek probleem. Waardeur in pseudokode ek vervat 'n meer planmatige manier beskryf hoe ek het 'n baie intuïtief menslike algoritme van die verdeling van die telefoon boek in die helfte, herhaal, herhaal, herhaal, totdat ek iemand soos Mike Smith, As hy wel in die telefoon boek. Maar ek soort van gebruik wat ek sal noem 'n baie iteratiewe benadering hier in die besonder kennis reël 8 en lyn 11. Dit is bewys van 'n iteratiewe benadering, 'n herhaling benadering, want dit is presies die gedrag wat hulle veroorsaak. Diegene lyne sowel sê gaan lyn drie, en jy kan soort dink dat jy in jou geestesoog as 'n lus. Dit is wat jy vertel om terug te gaan na stap drie en herhaal, weer en weer, en weer. Maar wat as ons die invloed van 'n belangrike idee hier dat ons nie die laaste keer, en vereenvoudig reël 8 en lyn 11 en hul bure as net dit, in geel. Dit is nie fundamenteel smeer die pseudokode baie, maar dit is fundamenteel verander die aard van my algoritme. Wat ek nou sê in stap 7, in stap 10, is om te soek vir Mike in presies dieselfde manier, maar net in die linker half of die regter helfte. So met ander woorde, as Ek begin by stap een, haal telefoon boek, oop tot middel van die telefoon boek, kyk na die name, As Smith is onder Naam, bel Mike, anders As Smith is vroeër in 'n boek, stap sewe soek vir Mike in die linker helfte van boek. Maar daardie soort van voel dit laat my hang, reg? In geel, is 'n onderrig, maar hoe doen ek soek vir Mike in die linker helfte van die telefoon boek? Waar Ek het nie 'n algoritme waarmee ek kan soek vir iemand soos Mike Smith? Wel, dit is staar ons in die gesig. Ek kan letterlik gebruik presies dieselfde program effektief gaan na die top weer en weer loop dieselfde reëls van die kode. So selfs al is dit moet voel soos 'n bietjie van 'n sikliese definisie waar jy beantwoord iemand se vraag deur net soort van om te vra dieselfde vraag weer, soos hoekom, hoekom, hoekom? Die werklikheid is, want ons het hard gekodeer 'n paar van die spesiale lyne, stap 4, wat 'n as, en stap 12, wat is effektief 'n ander tak, want ons het die noodhulp maatreëls, hierdie algoritme sal beëindig indien ons vind Mike, of as ons dit nie doen nie. Maar in stap 7 en 10 nou, ons het wat ons sal 'n rekursiewe algoritme noem. En rekursie is inderdaad 'n kragtige idee dit is 'n bietjie verstand buig op die eerste, dat ons kan nou aansoek doen as volg. Merge soort sal die laaste soort wees wat ons kyk na, ten minste in die klas formeel. En dit is fundamenteel verskillende van dié laaste drie, en beslis laaste vier as ons sluit bogosort. Hier is die pseudokode vir merge soort. Wanneer oor die toevoer van n elemente, so gegee 'n verskeidenheid van grootte n, as n minder as 2, terug te keer. So hoekom het ek dat gesonde verstand gaan eerste? Wat is die implikasie as ek vir julle 'n skikking waarvan die lengte n is minder as 2? Dit is reeds gesorteer, natuurlik, reg? Omdat die lys óf een element wat trivially gesorteer, want dit is die enigste ding wat daar is. Of, is dit van die grootte nul, wat beteken daar is niks om te sorteer, so deur die natuur dit gesorteer is. Daar is net niks verkeerd daar. So dit is ons sogenaamde basis geval. Dit is soortgelyk in die gees na wat ons gedoen het met Mike. As Mike's in die telefoon boek, bel hom. As hy nie daar is nie, gee. Dit is 'n sogenaamde basis geval, om seker te maak hierdie algoritme aan die einde van die dag stop in sekere omstandighede. Maar hier is die sprong van die geloof nou, anders, sorteer die linker helfte van die elemente, sorteer dan die reg helfte van die elemente, en dan saam te smelt die gesorteer helftes. En hier is waar dit voel soos ons Copping uit. Ek het jou gevra om te sorteer N elemente, en ek is sê, OK, moenie dit deur sorteer links en sorteer die regte. Maar ek sê een ander ding, en dit is die sleutel tema lyk dit in die intuïsie tot dusver daar is die derde stap van die samesmelting. Watter selfs al is dit lyk so dom in die gees, soos net saamsmelt dinge saam, dit lyk 'n belangrike stap in die rigting van die wees kombinering van twee probleme wat is uiteindelik in die helfte verdeel. So saamsmelt soort, laat ons dit doen, as jy sal humor my, met 'n meer demonstrasie, Net sodat ons het 'n paar getalle te werk. Kan ek ruil agt stres balle vir agt mense? Alle reg, hoe om jou drie, jy vier in hierdie afdeling, vyf, ses, en laat nie 7, 8, kom op. OK, ja OK. Minus 8, daar gaan ons, plus 1. Uitstekend. Alle regte kom, laat se vinnig gee jou nommers. Nommer twee, nommer drie, nommer vier, nommer vyf, ses, sewe, agt. Ek het agt korrek hierdie tyd. OK, so voort te gaan as jy kan, en laat se sorteer in die oorspronklike bevel dat ons gister gehad het wat gelyk soos hierdie, as jy nie sou omgee. En kom ons doen dit in die voorkant van die tafel. Alle reg, sodat saamsmelt soort. Dit is waar dit gaan soort te kry interessante, omdat ek lyk te gee myself so veel minder inligting vandag. So saamsmelt soort in die eerste toevoer van n elemente, en is natuurlik nie minder nie as twee is, is dit agt, so ek het 'n paar meer werk te doen. So nou verstandelik ons ​​as 'n klas is nou in die ander tak, wat beteken drie stappe. Eerstens, ek het die te sorteer linker helfte van die elemente. So, hoe gaan ek oor om dit te doen? Wel, ek gaan soort verstandelik verdeel die lys hier, jy hoef nie te fisies beweeg, en ek is gaan net fokus op die linker helfte van die elemente hier. So, hoe gaan ek te sorteer 'n lys van nou grootte vier? Wat is my algoritme? Eerste Ek is so is n minder as twee nie, so ek gaan na die ander blok weer. Sorteer links helfte van elemente. So nou weer, verstandelik, en dit is waar jy het 'n baie om te val geestelike geskiedenis, as jy wil. Nou is ek sorteer links helfte van die linker helfte. Alle reg, so nou is ek roep my dieselfde merge sorteer algoritme, is N minder as twee? Nee, dit is twee, so ek het om te sorteer die linker helfte en die regter helfte. So hier gaan ons, sorteer die linker helfte. Hoekom doen jy nie net neem 'n stap vorentoe. Wat is jou naam? Publiek: Darren. Spreker: Dan. Dan het na vore getree. Publiek: Darren. Spreker: Darren, gedoen. Het jy sê Darren of Dan? Publiek: Darren. Spreker: Darren. OK, Darren het weereens vorentoe en hy is nou uitgesorteer. En dit is amper 'n ligsinnig eis, reg? Ek het nie regtig lyk nie te wees die bereiking niks nie, maar laat ons voortgaan. Nou kan ek sorteer die regte helfte van die elemente. Wat is jou naam? Publiek: Lukas. Spreker: Lukas. Kom, stap vorentoe. Gedoen het, het ek gesorteer het Lukas. Die linker helfte is nou uitgesorteer en die regter helfte is nou uitgesorteer, maar weer, daar is 'n belangrike stap hier. Wat moet ek volgende doen? Voeg die gesorteer helftes. Nou gaan ons net almal heen en weer op hierdie manier, want ek soort van moet paar vrye ruimte. Dit is amper soos hierdie ouens is op 'n tafel, en ek moet 'n paar kamer om dit te skuif rond op. So ek gaan om saam te smelt julle deur te kyk op die linker helfte en die regter helfte. En wat natuurlik kom eerste, links half-of die regterkant helfte? So reg helfte, so laat beweeg Lukas oor hier te Darren se oorspronklike posisie. En nou is hulle linker helfte om saam te smelt in, Darren gaan reg daar te beweeg. So voel soos byna 'n borrel soort effek, maar my fundamentele algoritme baie verskillende hierdie tyd. Maar nou is waar dinge 'n klein irriterende omdat jy moet geestelik rewind waar het ek laat vaar. Ek het net saamgesmelt het om die gesorteerde helftes, wat beteken ek is waar in my algoritme? Ek het die reg om die helfte te sorteer, reg? As jy rewind, letterlik op die video, sal jy sien dat ons aan hierdie punt van Lukas en Darren deur sorteer links helfte van die linker helfte. Daarna het ons saamgesmelt diegene gesorteer helftes, wat beteken dat die volgende stap is 'n soort van die regter helfte van die linker helfte. Alle reg, so laat doen dit vinniger. Alle reg, ses, ek gaan om te beweer jy is nou uitgesorteer, kom vorentoe. Wat is jou naam? Publiek: Adriano. Spreker: Adriano. Adriano is nou uitgesorteer. En wat is jou naam? Publiek: Alex. Spreker: Alex is nou uitgesorteer. Linker helfte, reg helfte, Wat is die finale stap? Saam te smelt. Redelik triviaal, so ek is gaan om saam te smelt in ses, 'n stap terug, agt, 'n stap terug. En nou sien dit is 'n nuttige afhaal, wat nou waar is oor die linker helfte van die lys, ongeag hoe ons begin het? Dit is gesorteer. Nou is dit nie gesorteer in die groot skema van dinge, maar dit is 'n onafhanklike gesorteer van die ander helfte. Nou wat stap ek op as ek hou omwikkelen hoe die storie begin? Nou het ek die reg om die helfte te sorteer. So nou is ons weg by die die begin van die storie, en laat ons doen dit vinniger. So ek gaan die te sorteer regter helfte van die hele lys. Wat is die volgende stap? Sorteer die linker helfte van die regter helfte. Sorteer die linker helfte van die linker helfte van die regter helfte. En wat is jou naam? Publiek: Omar. Spreker: Omar, stap vorentoe, gedoen. Linker helfte is gesorteer. En wat is jou naam? Publiek: Chris. Spreker: Chris, neem 'n stap vorentoe, jy is nou uitgesorteer. Wat is die belangrike stap nou? Saam te smelt. So 'n mens gaan om saam te smelt in plek hier, as jy kan 'n stap terug te neem, en drie gaan 'n stap terug, saam te smelt. So het die linker helfte van die regter helfte, is nou uitgesorteer. Om eerlik te wees, hierdie algoritme voel soos ons mors manier om meer tyd as voorheen, maar as ons dit gedoen het in reële tyd, sal ons sien wat die wegneemetes gaan wees. Nou hier is ek, reg helfte van die regter helfte, Laat my gaan voort en sorteer die linker helfte. Stap vorentoe, wat is jou naam? Publiek: Ramsey. Spreker: Ramsey is nou uitgesorteer. Wat is jou naam? Publiek: Marina. Spreker: Marina is nou uitgesorteer as Wel, as jy 'n stap vorentoe. Belangrike stap hier is nou saam te smelt, ek is gaan om uit te ruk uit my twee lyste links en regs. Vyf gaan eerste kom, en sewe gaan volgende kom. En weer, dit is doelbewuste. Die feit dat hulle met treë vorentoe en agtertoe is bedoel om voor te stel dat ons nie kan doen hierdie algoritme in plek so maklik as borrel soort, en seleksie soort, en voeg soort waar ons net gehou uitruiling mense. Ek het letterlik 'n soort van nuuts af vraestel waarin hierdie mense te sit Terwyl ek nie die samesmelting, en dan kan ek dit terug in plek gestel. En dit is die sleutel, want ek is met behulp van ' nuwe hulpbron, ruimte, nie net die tyd. OK, dit is amazing. Linker helfte is gesorteer, reg helfte gesorteer nou dat die sleutel samesmelting stap. Hoe gaan ek dit om saam te smelt? So as jy volg my linkerhand en regterhand Ek gaan my linkerhand te wys op die linker helfte, my regterhand op die regte helfte, en nou moet ek besluit stap vir stap wat om saam te smelt in. Wie kom natuurlik eerste? Nommer een. So kom hier, Hier is ons kras pad. So nou nommer een, en 'n kennisgewing wat ek doen met my regterhand Ek gaan my regterhand een te skuif stap oor te wys nommer drie, en nou het ek te maak dieselfde besluit. En eintlik staan ​​reg in voor Lukas hier as jy kan, want dit is ons kras pad. So wat is volgende? Ons het Lukas met nommer twee of Chris met nommer drie. Dit is duidelik dat Lukas, die aantal twee, so jy hier kom. Maar my linkerhand nou gaan word aangevul te wys op Darren, en hier is die sleutel weg te neem met samesmelting, ek gaan om te hou om dit te doen, natuurlik, as jy die soort van volg die logika. Maar my hande is nooit gaan agteruit te gaan, wat beteken ek altyd net beweeg na links met my samesmelting proses, en wat gaan die sleutel te wees ons ontleding in net 'n oomblik. So laat ons nou klaar is met hierdie vinnig. So drie kom volgende, dan vier kom volgende, en nou vyf kom volgende, dan is ses, en sewe, en dan uiteindelik agt. Voel soos die stadigste algoritme nog, maar nie as ons werklik loop dit op dieselfde soort van die klok spoed, so te praat, met dieselfde merk klok as tevore. Hoekom? Wel, Kom ons neem 'n kyk na die eindresultaat. Kom ons gaan terug oor hier, laat my trek 'n demonstrasie visueel van wat ons nou net gedoen het. Inzoomen hier, op hierdie bladsy hier, vertel Firefox dat ons wil tou in hierdie boks, laat sê borrel soort waarmee Ons is nou goed bekend, seleksie soort, wat ook 'n redelik eenvoudig een, en nou vandag se merge soort, wat sal ons klimaks eindig nie. Die rede waarom dit het soveel meer hier met mense en my mondelings is, natuurlik, ek verduidelik elke stap. Maar as jy net voer hierdie, baie soos ons gedoen het borrel soort en keuring soort nie net visueel, kyk net hoeveel meer doeltreffend hierdie benutting van afdeling en verower kan word wanneer dit toegepas word om 'n stel data wat nie eens grootte agt, maar selfs baie, veel groter. Ek gee jou saamsmelt soort, langs kant met hierdie ander algoritmes. Dit gaan pynlik om te kry vinnig, en die einde is nie besonder klimaks, hulle het net beland gesorteer. Maar die sleutel weg te neem is dat Kyk hoe baie vinniger smelt soort was nie, tensy jy dink ek is net soort van die geknoei met jou. As ons dit doen 'n laaste keer, Kom ons laai dit, laat ons terug te gaan en kies borrel soort, en net vir die skop, laat kies inplanting soort, net vir 'n goeie maatreël. En hierdie keer weer, laat kies merge soort en laat eintlik loop hierdie kant van die kant. En dit is nie, in werklikheid, 'n gelukskoot. Wat ek gedoen het, is effektief ek het verdeel my insette in die helfte, weer, en weer en weer. En daar is net so baie keer jy kan verdeel jou insette in die helfte, links en regs. Wat is die formule wat ons hou sien wat beskryf die afdeling in die helfte weer en weer, en weer en weer? GEHOOR: Meld n. Spreker: Teken n. Maar dan is daar een ander belangrike stap, hierdie algoritme nie inteken n stappe. As dit is eers inteken N stappe, ons in die dieselfde probleem sou wees as voor waar ons nie kan seker alles is gesorteer. Jy moet minimaal kyk na n elemente om seker te wees n elemente word gesorteer, anders is dit 'n sprong van geloof. So dit is minimaal log N stappe, maar wat oor hierdie belangrike samesmelting stap waar ek saamgesmelt my linker helfte en regs helfte en loop oor die verhoog? Hoeveel treë is dat om saam te smelt? Dit is n, maar ek het nie net saam te smelt die laaste keer. Op elk van hierdie geneste oproepe, op elke van daardie nes fusies, het ek nog gesorteer. Ek saamgesmelt hierdie twee ouens, dan is hierdie twee ouens, dan is hierdie twee ouens en so meer. So ek het weer en weer saam te smelt. Hoeveel keer? So elke keer as ek verdeel die lys in die helfte, het ek 'n samesmelting. Verdeel die lys in die helfte, doen 'n samesmelting. So as die verdeling van die lys kan gedoen word log n keer, en die samesmelting neem uiteindelik n stappe, wat kan nou die boonste gebind aan die gang tyd van ons algoritme? n log n. En inderdaad, dit is wat Ons het hier behaal. So het die gevoel dat jy sien visueel wanneer hierdie drie dinge loop langs mekaar is n teen n vierkant vierkantig teen n log n. Watter fundamenteel ons sal sien, nie net vandag nie, maar in die toekoms, is baie, baie vinniger. 'N rondte van applous vir hierdie ouens, Ek sal hulle beloon met stress balle. Kom ons verdaag hier vandag, en ons sal jy sien op Maandag.