[Speel van musiek] DAVID J. MALAN: Dit is CS50. En dit is die begin van die week drie. So het ons 'n baie opwindende gekry dinge te dek vandag. 'N baie geleenthede vir vrywilligers op die verhoog. En uiteindelik, vandag is nie oor-kode at all. Maar dit gaan oor idees, en dit gaan oor algoritmes, en eintlik terug te bring 'n paar van die lesse wat geleer is uit week nul, waarin onthou, ons het hierdie gedrog. En lenings inspirasie dat, om te begin om op te los al hoe meer gesofistikeerd probleme algoritmies. Maar eers 'n paar aankondigings. So een, as jy wil om aan te sluit Personeel en klasmaats CS50 se middagete hierdie Vrydag, beide hier en in Cambridge, en in New Haven, besoek die kursus se webwerf, waar 'n URL gevind kan word. Lesing hierdie Woensdag sal hier nie in Sanders. Dit sal slegs aanlyn wees, so tune in op die webwerf CS50 se of hier in Cambridge of New Haven as well. En dan die probleem sit twee is reeds in jou hande. As jy nog nie geduik in nog, laat my die sterk bewoorde voorstel bied dat, veral nou, as die probleem stel vooraf, jy regtig wil nou begin, indien nie ploeteraars 'n bietjie oor die naweek of voor wanneer hulle die eerste uit te gaan op Vrydae, want jy vind dat hulle is nie noodwendig kry langer of meer uitdagend per se. Ek dink jy sal vind dat, in die algemeen, hulle is geneig om te neem ongeveer rondom dieselfde hoeveelheid tyd. Maar dit is beslis hang op die student, en dit hang af van die ingesteldheid waarmee jy dit benader. Maar sonder uitsondering, jy gaan om te hardloop teen 'n paar muur en jy gaan om te tref sommige fout, en jy is net gaan nie in staat wees om kry oor dit op 'n sekere punt. En dit is uiters waardevolle staat te wees om om te stap weg, kom die volgende dag terug, gaan na kantoorure, post op CS50 Bespreek of die wil, om werklik geblok. So hou dit in gedagte. Begin vroegste as moontlik is die beste ding wat jy kan doen. So hier is waar ons begin die klas, oor in week nul. En ons kan kry 'n vrywilliger hier om my te help mie vind? OK. Staan reeds. Kom up. Dink dit is hoe dit gaan werk. Wat is jou naam? ALAN ESTRADA: Alan Estrada. DAVID J. MALAN: Alan Estrada. Kom up. Bly te kenne. ALAN ESTRADA: Nice om jou te ontmoet. DAVID J. MALAN: En jy was hier met ons in week nul, natuurlik. ALAN ESTRADA: ek was. Ek was. DAVID J. MALAN: So kon jy gaan voort en vind vir ons Mike Smith, so vinnig as wat jy kan? So vinnig as wat jy kan. Letterlik skeur die probleem in die helfte as wat jy nodig het om te. ALAN ESTRADA: Um. DAVID J. MALAN: Letterlik skeur die probleem in die helfte. ALAN ESTRADA: Oh. Mm. Baie goed. DAVID J. MALAN: OK. Goed. Dankie. ALAN ESTRADA: Baie goed. OK. DAVID J. MALAN: En so nou, jy dit Uiteindelik af om die helfte van die grootte van die probleem. Nou, ons is af na 'n kwartaal. Is jy aandag te gee aan watter kant ons hou? [ROOIBORSDUIFIE] ALAN ESTRADA: Ja, ek think-- DAVID J. MALAN: Wat artikel is ons in? ALAN ESTRADA: sluiers so. DAVID J. MALAN: OK. Maar Mike Smith gaan te wees ná Klanke Dempers. So-- [ROOIBORSDUIFIE] Alles reg. ALAN ESTRADA: Waarheen is ons op soek na? DAVID J. MALAN: Mike Smith. ALAN ESTRADA: Mike Smith. DAVID J. MALAN: Nou, ons is in die chirurgiese. Nou, dokters. Now-- ALAN ESTRADA: Let's- laat ons gaan met die werklike. Real. DAVID J. MALAN: Real. OK. As jy nodig het Real. Nou, wat manier is Mike Smith? ALAN ESTRADA: Hierdie manier. DAVID J. MALAN: Watter manier? ALAN ESTRADA: wag. M is-- reg? Ons het begin with-- DAVID J. MALAN: Ja. Hulle is gelaat. Jou reg. ALAN ESTRADA: Ja. DAVID J. MALAN: So Mike se hier. ALAN ESTRADA: Wat? [ROOIBORSDUIFIE] Slegte voorbeeld, ouens. Jammer. DAVID J. MALAN: Dit sal leer jy spring uit jou stoel. ALAN ESTRADA: Oh. Oh. Ek het jou. Ek het jou. Oh. Oh. Dit is-- OK, ek het jou. Smith reg hier? DAVID J. MALAN: Smith, dankie. So ek sal aanhou opkyk Smith? ALAN ESTRADA: O, ja. Nee, nee, nee. Ag nee. Dit is myne. DAVID J. MALAN: Ag, jy het Smith. OK. ALAN ESTRADA: Ja, ek het Smith hier. Jammer, ouens. Ek het gedink ons ​​Michael-- soek Michael. Jammer. DAVID J. MALAN: Dis OK. Alle reg, nou is ons in Paccini en Seuns. ALAN ESTRADA: Paccini en seuns. DAVID J. MALAN: Net jy en ek is op hierdie. OK. Vind ons Mike Smith. Smith. ALAN ESTRADA: Smith. DAVID J. MALAN: Smith. Ons is in R vir rommel. ALAN ESTRADA: Vullis. Oh. Dit gaan 'n rukkie neem. [ROOIBORSDUIFIE] DAVID J. MALAN: Shoes. Ons is in die skoene. ALAN ESTRADA: Nou is ons gonna-- DAVID J. MALAN: Nice. ALAN ESTRADA: Which-- [ROOIBORSDUIFIE] O, dit is 'n groot. [ROOIBORSDUIFIE] DAVID J. MALAN: Dis OK. ALAN ESTRADA: O, dit is goed. Ek dink nie ek gaan het PSAT buddies daarna. DAVID J. MALAN: Goed. Sport. ALAN ESTRADA: Sporting. Um, L, M, N, O, P. DAVID J. MALAN: OK. So laat skeur dit in die helfte. Dit is OK. Dit eindig swak in elk geval, want Mike Smith sal nie in die geel bladsye. ALAN ESTRADA: Aw. DAVID J. MALAN: Nee, dit is OK. Maar laat ons voorgee soos hy is op hierdie bladsy. So nou, het jy die probleem Uiteindelik af tot een bladsy, en ons het Mike Smith. [Juig] OK dankie. OK. Dit was iets besonders. Maar dit was nog vinniger as lineêre soek, waarin ons begin by die begin van die boek, en ons beweeg ons weg van links na regs, uiteindelik op soek na Mike Smith. En so, as die telefoon boek het miskien 1000 bladsye, Miskien is dit sou geneem het ons 10 of so bladsy trane. Maar jy kan aged aangeraak 'n aanname tydens alles, wat is om te sê dat die telefoon boek vooruit was wat? GEHOOR: Gesorteer. DAVID J. MALAN: Dit is gesorteer. Reg? Dit is alfabeties gesorteer, so dat al die name en nommers word gesorteer van die A tot die Z se en alfabeties tussen in. Maar vandag, nou vra ons Die vraag is goed, hoe het Verizon of die telefoon maatskappy kry dit in die staat? Want dit is een ding om te hefboom dat die aanname, en daarom, 'n probleem met 'n los algoritme meer doeltreffend. Maar ons het nooit regtig gevra week nul, goed, hoeveel dit gekos het Verizon of iemand anders dat die telefoon boek in gesorteerde volgorde te kry? Reg? Dit maak nie saak of kyk Mike Smith is super vinnig as wat dit neem jou 'n jaar tot die bladsye aanvanklik sorteer. Reg? Jy kan net sowel sif deur 'n ewekansige telefoon boek, As dit gaan super wees duur om dit te sorteer. So as ons 'n ander vrywilligers kan hê. Kom ons neem 'n blik op hier by hoe ons might-- kom up-- hoe ons kan gaan sorteer hierdie. En as die Jordaan kon eintlik saam met ons hier op die verhoog. Kom vir net 'n oomblik. Wat is jou naam? CAROLINE: Caroline. DAVID J. MALAN: Caroline, kom op op. En jy sal by deur my en Jordan hier. Caroline, baie dankie. Alles reg. So wat ons hier vir Caroline is 26 blou boeke dat FAS gebruik om te administreer sekere eindeksamen. Dit is om hard te vind, maar wat ons gedoen het in advance is dat ons iemand se naam gesit het op die voorkant van elk van hierdie, maar ons het dit eenvoudig deur gehou dan om uit volle name. So wil ons die persoon sit met die naam L, D, J, B, al die pad deur middel van 'n Z, maar hulle is in enige volgorde. En so as jy wil, praat jou pad deur die probleem as jy doen dit, kan jy gaan voort en sorteer vir ons, van A tot Z. GEHOOR: OK, so L is soos die middel. C begin. B. J voordat L. B, Q. DAVID J. MALAN: Hou dit gedink vir 'n sekonde. Want anders is dit net interessant om jou, my, en die Jordaan. Daar gaan ons. GEHOOR: [onhoorbaar]. R. DAVID J. MALAN: OK. Wat doen jy? CAROLINE: M kom nadat O. DAVID J. MALAN: OK. CAROLINE: O. DAVID J. MALAN: O, Good. CAROLINE: E. DAVID J. MALAN: E, F. Ja. CAROLINE: T, U, V DAVID J. MALAN: V, T, U, V. So dit lyk soos jy making-- die gang te hou. Dit lyk soos jy maak 'n groot hoop hier, en soort van 'n groot hoop daar. So het die eerste helfte van die alfabet, tweede helfte van die alfabet. OK. Goed. Soort splitsing van die probleem in twee. M, N, X. Ja. CAROLINE: K. DAVID J. MALAN: OK. K. So jy soort van te kies hulle die een na die ander, om dit óf links of regs, of Z se gaan op die vloer. OK. CAROLINE: Z gaan op die vloer. DAVID J. MALAN: OK. Y gaan op die vloer. Nou kan ons X. sit CAROLINE: G. DAVID J. MALAN: G gaan verlaat. S gaan reg. Alle reg, A gaan al die pad verlaat het. CAROLINE: A, B, C, D. DAVID J. MALAN: Nou, goed. Ons het 'n het, B, C. W se daar gaan sit. Alle reg, T. CAROLINE: H, I, J. DAVID J. MALAN: H, I, J. Good. CAROLINE: In die sentrum, ek gonna-- DAVID J. MALAN: OK. So nou gaan ons soort van saamsmelt hierdie verskillende planke. So 'n deur C, dan sien ek D, en E en F en G, en H, en I. Nice. J, K. En dan, hierdie hoop is onderstebo, maar dit is OK. Seker nie. Ons kan sny 'n paar hoeke. OK. En dan moet ons W, X, Y, Z CAROLINE: Ja. DAVID J. MALAN: Uitstekende. So 'n groot dankie aan Caroline vir sortering hierdie. [Juig] Dankie. Baie dankie. So nou laat ons kyk vir 'n oomblik hoe Caroline het oor dit te doen, en wat presies ons kon aan- hoe ons in staat was om op te los wat probleem wanneer ons was net kry 'n hele klomp van die ewekansige insette. Wel, dit lyk asof daar was 'n bietjie van 'n stelsel daar? Reg. So het die vroeëre briewe in die alfabet, sy was om aan die linkerkant, en die later letters in die alfabet, Sy was besig om in die regte. En sodra sy gevind sommige proksimale briewe, kinders wat gaan reg langs mekaar, sy sou diegene in orde te bring. En so het ons soort het hierdie klein hope gesorteerde insette voorkom. En so dit is nogal soos wat die meeste van ons mense sou doen. Ons wil soort van sif deur dit, en ons wil soort het 'n meganisme. Maar dit kan moeilik wees om te skryf dit in 'n formule per se. Dit het gevoel 'n bietjie meer organiese as dit. So laat ons kyk of ons kan nou gebind die probleem met minder insette. In plaas van 26, laat iets veel minder te doen met net sê, sewe, agter hierdie deure, om so te praat. Is daar net sewe getalle? En indien die doel nou op hand is om 'n waarde te vind, Kom ons kyk hoe doeltreffend ons kan gaan om dit te doen. En laat ons kyk of ons kan nou begin om 'n paar nommers toe te pas, of 'n formules waarmee beskryf die doeltreffendheid van ons telefoon boek algoritme, ons eksamen boek algoritme, en meer algemeen, die vind van inligting. So vir hierdie, laat my gaan voort, en op die touch screen hier, sit 'n webblaaier wat juis hierdie sewe deure. En as ons kon een ander te kry vrywilligers om op te kom hier, Ek het hierdie selfde deure sit hier. Vinnige vrywilliger. Dit one-- demos gaan om 'n vinniger en vinniger nou. Kom af. Wat is jou naam? TREVOR: Trevor. DAVID J. MALAN: Trevor? Alle reg, Trevor, kom op sit. So Trevor het hier aangebied om doen 'n soortgelyke probleem, maar een wat nouer in omvang, en dit gaan sodat ons probeer om nou te formaliseer die proses vir die sorteer hierdie getalle. So Trevor, lekker om jou te ontmoet. So hier is 'n skikking, om so te praat, 'n lys van sewe deure. Gaan voort en vind ons die nommer 50. En dan na die feit, vertel ons hoe jy dit gevind het. Moet be-- alles reg. Ja, dit is die een hier? Uh Oh. OK. Jy het gekliek dat een. Goed. En goed. Nou het jy gekliek dat een. En laat my gee u die mikrofoon, sodat jy dit in net 'n oomblik. Gaan voort en klik op die langsaan wat jy van plan. Ja, goed. TREVOR: Kan ek unclick 'n deur? DAVID J. MALAN: Nee, jy kan nie unclick. TREVOR: OK. Hierdie een. DAVID J. MALAN: Waar wil jy gaan? Watter een? TREVOR: Daardie een. DAVID J. MALAN: No. TREVOR: OK. Hierdie een. DAVID J. MALAN: Ja. Dit was goed. Alles reg. So wat was jou algoritme of prosedure vir die doen dit, Trevor? TREVOR: Ek het net deur deure totdat ek het 'n 50. DAVID J. MALAN: OK. Uitstekende algoritme. So is dit goed. Want in werklikheid, as ek openbaar wat is agter hierdie twee ander deure, wat ons sal hier vind, is dat ons het net ewekansige insette. So dit was eintlik as goed soos jy kan kry. En in die feit, jy beter as het uitvoerig soek die hele skikking, want dit is werklik sou gewees ongelukkig as jy die aantal getref het 50 op die laaste deur. Maar wat as ons plaas het jy 'n aanname. Veronderstel ek soort al hierdie deure rond, sodat jy die getalle gesorteer hierdie tyd, maar hierdie keer is dit eintlik 'n different-- hierdie tyd, dit is eintlik gesorteer vir jou. En nou het die doel aan die hand is om die nommer 50 getref. TREVOR: OK. DAVID J. MALAN: Wat is jou algoritme gaan wees? TREVOR: Wel, as dit is gesorteer, dit is óf gaan om be-- as grootste tot die grootste, neerdaal, sal dit die eerste een te wees, of as dit die teenoorgestelde, dit sal die laaste een wees. So ek sal net tap die deur, en dan net tap die laaste deur. DAVID J. MALAN: Uitstekende. Alles reg. So het ons die nommer 50. So gou as jy geweet het hulle gesorteer ons in staat was om hierdie aanname te hefboom. So hulle is te veel soos die telefoon boek voorbeeld. Sodra jy het, selfs met 'n klein probleem soos hierdie, u insette pre-gesorteer, kan ons die waarde eintlik vind waarskynlik meer doeltreffend. En ek het jou as dit nie was vertel gesorteer klein tot groot, of groot na klein, en so is dit baie redelik was om te begin aan die een kant of die ander om werklik te vind dat die teiken waarde. So dankie aan Trevor as well. En ek sal propose-- mooi gedoen. Ons het 'n bietjie uit, eintlik, is onder ons gunsteling oomblikke in CS50, waardeur soms hierdie demos nie heeltemal volgens plan. En inderdaad nou, ek trek die verkeerde koppelvlak waarmee die touch screen te gebruik. So dit was my skuld is daar. So sal dit vir volgende jaar se clip as waarom ek kliek op my eie skerm. Maar laat ons neem 'n vinnige blik na wat verlede jaar gebeur het met Jay, wat gekom het, baie soos Trevor hier, vrywillig, en in hierdie kort clip, sal jy sien hoe dit dieselfde demo het nie heeltemal openbaar dieselfde lesse geleer. [Video speel] -Alle Ek wil hê jy moet doen is nou om uit te vind vir my, en vir ons, regtig, die nommer 50 een stap op 'n tyd. -Die Nommer 50? -Die Nommer 50. En jy kan openbaar wat is Agter elkeen van hierdie deure eenvoudig deur te raak met 'n vinger. Vervloek Dit. [ROOIBORSDUIFIE] [Einde afspeel] DAVID J. MALAN: So wat baie goed gegaan. Dit was die ongesorteerde deure. En Jay, natuurlik, gevind dat dit al te vinnig. Trevor het 'n veel beter werk in terme van 'n leerbare oomblik, om so te praat, het hierdie jaar in neem langer om dit te vind. Natuurlik, dan het ons Jay 'n tweede kans, waardeur ons gesorteer die deure, net soos ons gedoen het vir Trevor, en Trevor het super goed hierdie tyd. Maar Jay het dit half so vinnig. [Video speel] -Die Doel is nou om ook vind ons die nommer 50, maar doen dit algoritmies en vertel ons hoe jy gaan oor dit. -OK. -en As jy dit vind, hou jou die film. As jy dit nie vind nie, is dit gee jou terug. -Man. -OH! - [Onhoorbaar] OK. So ek gaan die einde gaan eerste as there's-- te bepaal Oh. [Applous] [Einde afspeel] DAVID J. MALAN: OK. So sorteer deure duidelik lei tot groter doeltreffendheid. En so, twee keer so vinnig is wat ek daar bedoel. En so Jay het gelukkig albei kere. En hy het ook gelukkig in daardie laaste jaar bestel ek 'n paar Blu-ray skywe om werklik uit te gee. Ek is jammer hierdie jaar het ons nie dieselfde nie, Trevor. Maar nog beter was 'n paar jaar terug. En sommige van julle dalk weet mede, Sean, wat toe hy in CS50 was, uitgedaag met die presiese dieselfde probleem, al is dit in SD, as jy gou sal sien, terug in die dag. En jy sal vind dat dit nie net gedoen Hy neem 'n bietjie langer as Jay, 'n bietjie langer as Trevor, was dit eintlik hierdie wonderlike geleentheid byna almal in die betrokke skare 'n la prys is reg, moedig hom na die getal wat ons soek is te vind. Kom ons. neem 'n vinnige blik. [Video speel] -OK. So jou taak hier Sean, is die volgende. Ek het agter hierdie verborge deure die nommer sewe. Maar weggesteek in sommige van hierdie deure sowel ander negatiewe getalle. En jou doel is om te dink van hierdie boonste ry getalle as net 'n skikking, of net volgorde van stukkies papier met nommers agter hulle. En jou doel is nie, net die gebruik van die top array hier, vind my die nommer sewe. En ons is dan gaan kritiseer hoe gaan jy oor om dit te doen. -Alles reg. -Find Ons die getal sewe, asseblief. Geen. Vyf, 19, 13. [ROOIBORSDUIFIE] Dit is nie 'n truuk vraag. Een. [ROOIBORSDUIFIE] Op hierdie punt, jou telling is nie baie goeie, sodat jy kan net so goed gaan hou. Drie. [ROOIBORSDUIFIE] Gaan aan. Eerlik, kan ek nie help om te wonder wat jy selfs dink oor, so-- [ROOIBORSDUIFIE] Slegs die boonste ry, so jy het drie linkerkant. So vind my sewe. [ROOIBORSDUIFIE] 17. Sewe. [Applous] Alles reg. [Einde afspeel] DAVID J. MALAN: sodat ons kan kyk na hierdie hele dag lank. En natuurlik, 'n paar van demos vanjaar se miskien nou sal beland in die volgende video jaar se as well. So nou, laat ons eintlik fokus op die algoritmes hier, en kyk of ons nie kan nie nou begin om te formaliseer hoe ons kan gaan om ons data in hierdie toestand dat dit gesorteer, sodat uiteindelik kan ons eintlik soek dit meer doeltreffend. En selfs al is ons gaan redelik klein data stelle gebruik, soos die agt nommers ons hier op die bord, uiteindelik dieselfde idees kon aansoek doen 1000 insette, 'n miljoen insette, 4000000000 insette, omdat die algoritmes gaan fundamenteel dieselfde wees nie. En so is dit ons laaste geleentheid vir vrywilligers vandag Maar miskien is die mees betrokke een waarvoor ons moet agt vrywilligers om te kom en loop ons deur die proses van sorteer wat binnekort wees oor hierdie musiek staan ​​hier. Laat my hier begin terug. So een in die turquoise-- groen is dit? Pleeg jy? Twee. Kom af. OK. Drie. Vier. Laat me-- OK, vyf. Jy deur jou vriend genomineer. Ses, sewe, agt. Kom up. Alles reg. Baie dankie. Kom up. Kom up. Alles reg. So wat ons het en dit here-- is onder die meer ongemaklike kinders, aangesien dit sal vereis dat jy humor my net 'n bietjie van die tyd. Jy sal nommer een. Wat is jou naam? Annan: Annan. DAVID J. MALAN: Annan. David. Wat is jou naam? JOSEPH: Josef. DAVID J. MALAN: Joseph, jy is nommer twee. SERENA: Serena, nommer drie. Stefan, nommer vier. CYNTHIA: Cynthia. DAVID J. MALAN: Cynthia, nommer vyf. [Onhoorbaar] DAVID J. MALAN: [onhoorbaar]. David, nommer ses. MATT: Matt. DAVID J. MALAN: Matt se nommer sewe. En? WAVERLY: Waverly. DAVID J. MALAN: Waverly, nommer agt. Alles reg. As jy could-- Oeps. As jy alles, as jou eerste uitdaging is, is daar agt musiek erwe hier in die gesig staar die gehoor. As jy jou nommers op kan sit hierdie musiek staan ​​in so 'n manier dat hulle in lyn met die dieselfde nommers op die bord. So maak julle lyk wat deur om jou nommers op hierdie musiek staan ​​hier. Uitstekende so ver. Uitstekend. OK. So nou gaan ons na die vra vraag in 'n paar verskillende maniere. Hoe kan ons gaan sorteer hierdie mense hier? Want ons het 'n paar benaderings vroeër, waardeur ons soort maak twee verskillende emmers. En dan algemeen was ons piece dinge saam. Sodra ons sien twee getalle wat behoort saam ons hulle saam. Twee briewe wat saam hoort. Maar laat ons kyk of ons kan dit nie formaliseer, sodat ons uiteindelik sommige pseudo-kode wat jy wil, met wat jy kan hierdie probleme op te los. So nou, ek kyk uit by die volgende nommers hier. En ek sien 'n hele klomp van die foute. Uiteindelik, ek wil een op die links en agt aan die regterkant. En so het ek is op soek na hierdie twee, vier en twee. En wat is die probleem, natuurlik? Ja. Doen. Twee natuurlik kom voor vier, so jy weet wat? Laat my toe om eers te neem 'n gulsige benadering, as jy wil, baie soos die probleem stel one-- as jy onthou uit die Standard Edition van Probleem Stel One, waar ek net plaaslik die probleem op te los dit is reg hier in die voorkant van my en sien waar dit lei my. OK. So twee en vier, laat my gaan voor en net te ruil julle twee. As jy fisies kan beweeg julle en jou papier, Dit lyk asof ek gekry het die lys in 'n beter toestand. Nou, hulle is goed. Ek gaan om aan te beweeg, vier tot ses, lyk goed. Geen probleem. Ses en agt, OK. Agt en een, 'n ander probleem. Want wat is waar sowat agt en een? Een kom voor agt, en so wat moet ons doen? Kom ons ruil die twee. Een en twintig. En nou, ek gaan om voort te gaan. Ek gaan hou om vorentoe te kyk. En laat ons sien wat gebeur. Agt en drie van Natuurlik, buite orde. Kom ons ruil. Agt en sewe, natuurlik. Buite werking. Kom ons ruil. Agt en vyf, natuurlik, laat swap. Alles reg. Lys is gesorteer. ja? OK, natuurlik nie. Maar dit is 'n bietjie beter, reg? Omdat kennisgewing wat gebeur het. Elke keer opgevoer ons 'n ruil, 'n kleiner aantal soort percolaatwater dat die pad, en 'n groter aantal percolaatwater hierdie manier, of ons sal begin sê geborrel om die links of geborrel na regs. Nou, dit is nie genoeg nie, want op sy beste 'n aantal mag een plek verskuif het vorentoe, of op die ergste, 'n aantal dalk verskuif een plek verder. Sodat jy weet wat hierdie soort gewerk redelik goed so ver. Kom ek probeer dit net weer. Twee en vier, hulle is OK. Vier tot ses, hulle is OK. Ses-en-een buite orde. So laat ruil julle twee. En nou, kennis van die probleem se begin om beter weer 'n klein kry. Ses en drie, buite orde. Kom ons ruil julle twee. Ses en sewe, jy is goed. Sewe en vyf, natuurlik, buite orde. Sewe en agt, in orde is. En nou, kan ek nodig het om doen dit 'n paar keer. En in die feit, dink vir julle dalk hoeveel keer maksimaal dalk moet ek heen en weer loop? Ons sal terug kom. So twee en vier is nog OK. Vier-en-een nope. So, laat ons ruil. En weer, sien visueel een is 'n soort van borrelende aan die linkerkant, waar dit moet wees. Vier en drie swap. Vier tot ses. Ses en vyf ruil. Ses en sewe. Sewe en agt is goed. Goed. Ons kry nog beter. So laat ons sien. Nou, ons het twee en 'n. Natuurlik, te ruil. Twee en drie, drie en vier, vier en vyf, ses en sewe, sewe en agt. Goed. En jy weet wat? Want ek het een verandering daar, laat my nie een gesonde verstand tjek. Laat my gaan al die pad terug na die begin. OK. Een, two-- yup, sien? Iets is verkeerd. Drie, vier, vyf, ses, sewe, agt. En in hierdie laaste aangee, is jy is gemaklik met my nou beweer dat dit gesorteer? OK. Visueel, dit is absoluut waar. Maar funksioneel, wat het ook net gebeur in daardie laaste aangee dat jy kan om te bevestig dat hierdie lys is inderdaad gesorteer? Wat het ek gedoen of hierdie laaste aangee nie? GEHOOR: Daar was geen veranderings. DAVID J. MALAN: Jammer? GEHOOR: Geen veranderinge. DAVID J. MALAN: Daar was geen veranderings. So sou dit dom van my wees doen dieselfde algoritme weer as ek nie het nie verander die eerste keer. En die staat het nie verander nie. Sekerlik, ek is nie van plan om te maak enige veranderinge vir die tweede keer. En so, dit is veilig nou om te sê, is lys gesorteer. En inderdaad, dit is nou iets wat ons sal oor die algemeen oproep borrel soort, waardeur paarsgewyse, jy foute weer reg te stel, en weer, en weer, en jy hou heen en weer gaan, en heen en weer, totdat jy maak geen sodanige swaps, op watter punt kan jy seker wees, ja, ek klaar vaststelling al die foute. Kom ons stel en probeer 'n ander benadering. As jy ouens kan gaan terug in die volgorde wat jy was 'n oomblik gelede wat lyk soos hierdie. Nou, laat ons neem 'n benadering 'n bietjie meer soos die eksamen boek, waardeur ons voortdurend was kies die letter van die alfabet dat ons soort wou om te gaan met die volgende. Miskien was dit 'n hoë brief soos A, of 'n lae letter Z. Sodat almal terug in hierdie volgorde. En nou, laat my dit doen. Kom ons kyk ek weet ek het agt nommers hier. Ek gaan om voort te gaan en net doelbewus kies die kleinste elemente. Reg? Dit lyk te intuïtief. Hoekom het ek nie die kleinste vind element, sit dit waar dit hoort, dan kry die volgende kleinste element, sit dit waar dit hoort, en net herhaal. Omdat intuïtief, Dit sou te werk. So vier, dis 'n mooi klein aantal. Ek gaan om te onthou waar dit is. Wag 'n minuut. Twee kleiner is. Laat my nou onthou waar twee is, en vergeet van vier. Ons sal later hanteer nie. Ses, Ek is nie geïnteresseerd. Agt, ek is nie geïnteresseerd in. Een is my nuwe klein aantal. So ek gaan om te onthou waar die een is. Drie, nie belang nie. Sewe, nie belang nie. Vyf, nie belang nie. So sonder om te val af die stadium van hierdie jaar, Ek gaan getal gryp one-- en wat was jou naam nou weer? Annan: Annan. DAVID J. MALAN: Annan. En as jy kan aansluit by my die begin van die lys, laat sit jy waar jy hoort. Unfortunately-- wat is jou naam? STEFAN: Stefan. DAVID J. MALAN: Stefan is in die pad. Dus voor Stefan los hierdie probleem, wat moet ons doen? Wat doen ons met Stefan? GEHOOR: [onhoorbaar]. DAVID J. MALAN: OK. Sodat ons kan dit doen. Ons kon soort van te neem Stefan en sy vier, en net sit dit in 'n veranderlike en hou op om dit vir 'n bedrag van die tyd, waardeur ruimte vir nommer een. En dit is nie sleg nie. Ek kon raai, waarom nie ons net sit Stefan hier? Hoekom kan dit skend een van die idees wat ons begin praat oor die laaste keer, het verlede week? Ja? GEHOOR: [onhoorbaar]. DAVID J. MALAN: Daar is geen indeks vir dit. As jy dink van hierdie inderdaad as 'n skikking, dit is soos negatiewe een, so daar is geen geheue eintlik hier as dit is inderdaad 'n skikking, soos wat ons verklaar het verlede week in lesing. So moet ons dit nie doen nie. Ons kan dit stoor in 'n veranderlike. Of jy weet wat? Ek het gehoor iemand anders voor te stel nie. Wat anders kon ons doen met Stefan? Hoekom het ons nie net vir hom uitsit en hom oor waar nommer een was. So as jy wil oor daarheen te gaan. En inderdaad, dit is 'n mooi goeie oplossing. Nou aan die een kant, ek het soort van die probleem gemaak erger. Vier is nou verder weg van waar dit moet wees. Dit moet na hierdie helfte. Maar weet jy wat? Dit kan slegte geluk gewees het. Miskien nommer agt was hier. En so nie, miskien sou ons gekry het gelukkig, en gestoot agt nader aan die einde. So in die einde van die dag, dit soort van alle gemiddeldes uit. Ons het nie nodig om sowat vier omgee. Al wat ek omgee nou is kies die kleinste element. En nou, wat ek gaan doen is vergeet nommer een permanent, want ek weet die lys agter my is nou gesorteer. So my lys was voorheen grootte agt. Nou, dit is die grootte sewe. So my probleem is om kleiner, hoewel lineêr. So nou, ek gaan na die kies huidige kleinste element, twee. Ses agt, vier, drie, sewe, vyf. Dit was die kleinste element. So, wat ek gaan doen with-- wat was jou naam nou weer? JOSEPH: Josef. DAVID J. MALAN: Joseph? Ons gaan aan Josef in plek te verlaat. Nou, ek gaan voorgee dat hierdie ouens are-- goed, Ek weet dat hierdie twee is reeds gesorteer. Kom nou fokus op die res van die lys. Ses is die huidige kleinste. Agt is groter. Vier is nou die huidige kleinste. Drie is nou die huidige kleinste. En so nou gaan ek drie te kies, wat is-- wat is jou naam nou weer? SERENA: Serena. DAVID J. MALAN: Serena, as jy kon gryp jou nommer en ruil with-- KALSANG: Kalsang. DAVID J. MALAN: Kalsang. Kom terug, en ons is gaan ruil die twee. En nou, laat ons hierdie op auto pilot. Ek gaan om te gaan en laat dit aan julle ouens na die volgende kleinste elemente te kies. Dun, vaal, vaal, vaal. Nommer vier, wat moet jy doen? Uitstekend. Nou, ek gaan na 'n ander laat verbygaan. Dun, vaal, vaal, vaal. Ek sien vyf is die volgende kleinste. Nou, ek gaan neem 'n ander pass. Dun, vaal, vaal, vaal. Ses is die kleinste. Goed. Sewe is die kleinste. Geen verandering. Agt is die kleinste. Gedoen. So wat ons het net gedoen word deur iteratief kies een element na die ander is implementeer iets wat ons is gaan formaliseer as seleksie soort. En dit is dalk selfs makliker om te verduidelik, in wat letterlik alles wat jy wil doen, is net bly gaan heen en weer deur die lys kies, die volgende kleinste element, totdat jy klaar is. Dus is dit nog makliker, miskien intuïtief, as verlede. Kom ons probeer 'n laaste een. As jy ouens julle kan herstel in die volgende posisies 'n laaste tyd, laat ons kyk of ons kan nie nou formaliseer een ander benadering. In werklikheid, sou iemand daar graag voor hoe anders ons kan gaan om dit te doen? Sonder die gooi uit buzzwords of soort antwoorde wat reeds bekend is, net intuïtief, wat kan ons doen? GEHOOR: [onhoorbaar]. DAVID J. MALAN: Ja. So is daar 'n paar groot intuïsie daar. Goeie dinge lyk tot dusver gebeur in rekenaarwetenskap wanneer ons verdeel en oorwin die probleem van die verdeling dit in die helfte en 'n half en half. En so ja, ons kan begin om dit te doen. En in die feit dat gaan wees, sal ons sien, een van ons beste oplossings nie. Maar laat ons terug na wat kom kort voor lank. Trouens, ons gaan om dit te doen dat 'n bietjie later in die week. Wat anders kan ons doen om hierdie op te los? Sodat almal hier is in skynbaar ewekansige volgorde. Jy weet wat? Eerder as heen en weer, heen en weer, heen en weer elke keer, dit voel soos Ek is besig met 'n baie van die loop. Hoekom moet ek nie net begin die begin van die lys, en net sit vier waar dit hoort? So laat my aanvaar vir die oomblik wat my lys is slegs die eerste element. Is vier gesorteer op hierdie oomblik in tyd, As ek omgee is alles hier? Dit is 'n soort van trivially waar, reg? Soos die lys met 'n nommer, en dat die getal vier is natuurlik gesorteer. So laat my net stipuleer dat hierdie lys is gesorteer. Maar nou het ek die res van hierdie lys. So nou, ek teëkom twee. Waar kom twee natuurlik hoort met betrekking tot vier? Voordat vier. So wat kan ek hier doen? Wat is weer jou naam? JOSEPH: Josef. DAVID J. MALAN: Joseph, as jy kon terug stap vir 'n oomblik met jou nommer. En nou, wat moet Stefan hier doen? Kom ons skuif Stefan hier. En nou, laat Josef hier kom. En nou, laat my daarop aanspraak maak dat alles hier gesorteer. So, soortgelyke resultaat, maar 'n fundamenteel ander benadering. Ek het nie eens gekyk wat daar sit. Ek hou net die neem van die elemente as hulle aan my oorhandig, en dit te hanteer. So nou, ek sien nommer ses. Waar kom nommer ses behoort? Ons het twee, vier, ses. Presies waar sy is nou. So laat ons dit alleen, en nou beweer dat hierdie deel van die lys is nou gesorteer. En so, dit voel fundamenteel anders in dat ek net beweeg deur die lys hier lineêr, en ek het nooit die verdubbeling terug. Ja. Alles reg. So agt, waar val jy? Net hier. Volmaak. So nou, een. Uh Oh. Dit voel soos dit is gaan duur te wees. Nou, in die vorige algoritme, Ek het net omgeruil mense. Sodat ek hom al die pad sit op die begin, maar dan verskuif Josef. Maar as ek Joseph beweeg, nou wat gaan verkeerd wees? Nou, ek het soort van undone-- Ek het geneem 'n stap vorentoe en dan een tree terug, want nou Joseph sou wees buite orde. So laat dit doen. As jy nommer een kan neem en stap terug vir 'n oomblik. Hoe kan ons put-- wat was jou naam nou weer? Annan: Annan. DAVID J. MALAN: Annan in plek? Wat moet gebeur met respek twee, vier, ses en agt? Hulle moet almal om te skuif. So as agt wil skuif eerste, dan ses, dan vier, dan twee. En dan Annan, as jy wil graag hier in te kom, goed. Maar hier het ons net soort 'n prys betaal op 'n ander punt in die algoritme. AANGESIEN laaste tyd saam met seleksie soort, en selfs borrel soort, Ek is terug loop en weer, heen en weer, wat beslis die toevoeging van tyd-wyse, en letterlik stapsgewyse. Invoeging soort, op die eerste oogopslag, lyk soos dit is super slimmer, in dat ek net maak stadige, inkrementele vordering, maar ek gaan nie hierdie heen en weer. Maar as iemand wel buite orde, kennisgewing al die werk wat ek moes net om te doen. Ek het die helfte van die lys te beweeg net om plek te maak vir nommer een te maak. So dit is dieselfde bedrag werk tot dusver is dit voel, net 'n ander soort werk. Laat ons voortgaan. So nou weet ons dat almal tussen een en agt gesorteer. Hier, ek het nommer drie. As jy wil om af te haal nommer drie, stap terug een. En wat doen julle moet doen? Yep. So dit is 'n ander een, twee, drie stappe. Drie eenhede van die tyd wat net kos my, so dat drie kan nou pas. Ten slotte, sewe. Kom ons gaan voort en het jy 'n stap terug te neem. Dit gaan net om ons kos een eenheid van tyd, maar dit is OK. En nou, vyf se gaan 'n bietjie duurder. As jy wil om terug te stap. Ons moet beweeg agt, en sewe en ses. En dan almal is nou gesorteer. So 'n groot hand om ons vrywilligers hier. Baie dankie. [Applous] Dankie almal. Dankie almal. So laat ons sien nou net hoe duur al wat. Kom ons kyk miskien die eenvoudigste, borrel soort. En ek sê eenvoudigste, net omdat jy kan dit gulsig op te los deur net los die paarsgewyse probleem hier. Los die probleem paarsgewyse hier, weer en weer en weer herhaal soveel keer as wat jy werklik nodig het om. So dit blyk dat met 'n borrel soort, goed, hoeveel stappe moet ek om oor te neem die eerste pass van daardie algoritme? Ek kan take-- laat see-- een twee, drie, vier, vyf, ses, sewe. En daar is hier agt elemente. So dit is soos n minus 1 stappe kry van die begin van die lys tot die einde van die lys. Maar met seleksie soort, onthou dat ek die elemente kies weer en weer en weer dit is die kleinste, Ek is dit in die plek, maar dan is ek nie soek agter my weer. So ek dink dit is 'n bietjie meer duidelik dan dat die eerste keer, kan ek het al n minus 1 stappe die kleinste element te vind. Dan sit ek hulle in plek is, en ek uitsit wie was hier voorheen. Maar dan het ek nie om hou op soek na hierdie element, want ek weet dit is reeds die kleinste. So nou kan ek kyk na net sewe elemente, dan ses elemente, dan vyf elemente, dan vier elemente. En so wiskundig as n die aantal elemente of nommers dat ons begin met, kan jy jou voorstel dat dit is dieselfde as N minus 1, plus minus n 2 stappe, plus minus 3 N stappe, plus N minus 4 stappe, al die pad af na net een stap. En ek is op my laaste persoon. En as jy onthou dat 'n baie van stats boeke of wiskunde boeke het die formules soos op die hardcover rug of voor hulle dit blyk dat hierdie reeks meer eenvoudig uitgedruk as n keer n minus 1 oor 2. En dit is goed as dit is nie aan die voorpunt van jou gedagtes. Maar dit is inderdaad waar. Dit is net 'n eenvoudiger manier om dit te skryf. En dan as jy dink terug na graad skool, wanneer jy net begin vermenigvuldig dinge uit, hierdie natuurlik is net n vierkant minus N gedeel deur 2. Al wat ek gedoen het, is uit te brei die uitdrukkings daar. En so laat herskryf hierdie 'n bietjie anders. Dit is n kwadraat gedeel deur 2 minus N / 2. So weer, ek is net soort van toepassing sommige rekenkundige reëls daar. Maar let nou dat die grootste termyn in hierdie uitdrukking, om so te praat, is dat n vierkant. So ja, dit is n kwadraat gedeel deur 2, minus N / 2. Maar oor die algemeen, as n gaan 'n groot waarde wees, Ek gaan om te beweer dat n kwadraat gaan die dominante faktor wees. Dit is net gaan wees 'n groter bydrae om die aantal stappe as N / 2. So, wat ek bedoel? Kom ons probeer 'n eenvoudige voorbeeld, selfs al die wiskunde kry 'n bietjie groot. So dink ons ​​het as 1 miljoen mense op die verhoog, of 1000000 dinge wat ons wil om te sorteer. Kom ons prop 'n miljoen in presies daardie formule om te sien hoe baie stappe wat dit neem totale om 'n miljoen elemente te sorteer met behulp sê, seleksie soort. So wil ons dieselfde formule as tevore. Ek wil aansluit 'n miljoen, sodat ek 'n miljoen kwadraat gedeel deur 2, minus 'n miljoen gedeel deur 2. As ek dit doen wiskunde in advance hier, ons het 500.000.000.000 minus 500,000, wat gee ons 499999500000, wat is pretty darn groot. In werklikheid, as jy nou vergelyk 499.000.000.000 999 miljoen 500000 teen ons oorspronklike waarde, 500.000.000.000, dit is so damn naby. Reg? N kwadraat gedeel deur 2 gee us-- of liewer, n kwadraat gedeel deur 2 het ons 500000000000. Dit is pretty darn naby om 499999500000, wat is om te sê trek af 500,000, of meer algemeen, aftrekking af N kwadraat, nie regtig nie 'n groot deal. Die N kwadraat maak hierdie getalle groei baie vinnig. Nou, dit is net belangrik vir sover as ons as die rekenaar wetenskaplikes, is oor die algemeen gaan nie soveel sorg oor die nuanses van hierdie formules en presies wat die presiese antwoorde is. Ons gee net dit nie, jy weet wat? Aan die einde van die dag, van hierdie formule is op die einde van n vierkant. Ja, ons is deel deur 2 daar in. Ja, ons trek af N minus 2. Maar aan die einde van die dag, die term wat ons werklik seer en kos ons 'n baie stappe is dat vierkante termyn. En ja, wat 'n rekenaar wetenskaplike gaan oor die algemeen doen is ignoreer al daardie kleiner orde terme, en kyk net na die een wat dra die meeste tot die koste. En dit is mooi, want ons kan nou praat in veel groter omvang oor algoritmes, en kan vergelyk. En die feit dat ek die gebruik van hierdie O is doelbewuste. Wanneer ek sê op die einde van, ek is spesifiek verwys na iets genoem groot O. en Big O is 'n notasie wat 'n rekenaar wetenskaplike gebruik om te beskryf 'n bogrens op iets. So as jy sê dat 'n algoritme is in groot O van n vierkant, as ek net 'n voorgestelde oomblik gelede, wat beteken dat wat in terme van sy hardloop tyd of sy doeltreffendheid, dit neem op die einde van N kwadraat stappe. Miskien meer, miskien minder. Maar dit is op die einde van N kwadraat. En dit is die bogrens. Dit gaan nie om te wees meer pynlik as dit. Dit gaan nie n blokkies te wees, of 2 om die N, of iets baie groter. Dit is 'n bogrens op wat dit ook al is die koste. So gegee dat, laat oorweeg net 'n paar voorbeelde. En dit is net 'n beperkte lys van baie algemene hardloop tye vir algoritmes wat bedoel is om te wees tekenend van 'n paar dinge wat ons het reeds gesien. So byvoorbeeld, in die geval van seleksie soort, wat ek hier beweer loop dat seleksie soort se die tyd is op die einde van N kwadraat. In die ergste geval, ek gaan hê 'n hele klomp van die ewekansige getalle hier. En soos ons wiskundig gesien het, as ek aanhou loop deur die lys, deur die lys, kies die volgende kleinste weer en weer element, as ek eintlik skryf al van die stappe Ek neem as ek voorgestel formulaically voor, dit is op die einde van N kwadraat stappe wat ek neem. En dit blyk dat borrel sorteer en voeg soort is net so stadig in die ergste geval. Oorweeg, byvoorbeeld, voeg soort, die heel laaste algoritme ons hanteer, wat het ons kyk na die element, en plaas dit dan waar dit hoort. En dan het ons gekyk na die volgende element, en plaas dit waar dit hoort. So kyk na die beste moontlike scenario. Dink ek het my vrywilligers line-up hierdie letterlik soos een deur agt, reeds gesorteer. Hoeveel stappe is invoeging soort gaan neem om agt mense te sorteer, as hulle kom op die verhoog soek soos hierdie? Agt mense is reeds gesorteer. En ek gebruik invoeging soort. Dat dit die laaste van die algoritmes. Wel, laat ons reenact ware vinnig. So as ek hier begin, ek sien een. Waar 'n mens behoort? Dit behoort hier. Ek sien twee. Waar kom twee hoort? Net hier. Ek sien drie. Waar kom drie hoort? Net hier. Ek sien vier. Net hier. Vyf, ses, sewe, agt. Daar is geen rede om myself te herhaal. En so, hoeveel stappe is dat in terme van n? Dit is op die einde van N stappe, reg? N minus 1. Maar ek het 'n liniêre getal stappe, en nou is ek gedaan. So wat is die beste geval, al is. Wat van die ergste geval? Wat agt oor was daar, en sewe was daar, en een en twee was hier, so dat die lys werklik is omgekeer? Wel, wat gebeur inderdaad As dit is die getal? En ons sal net 'n paar voorbeelde te doen. Wat as, wel, die nommer agt is hier, en die number-- Oeps. So, wat as, wel, die aantal agt is al die pad hier, en ek gebruik invoeging soort? OK. Ek eis op die oomblik is dit in plek is. Maar nou, seven-- waar kom sewe gaan? Natuurlik, dit gaan oor hier. So ek het om te beweeg agt oor een plek. Nou ses, waar gaan dit? Wel, alles reg. Nou, ek het om te beweeg agt oor 'n plek, en sewe oor 'n plek, en dan plop ek down ses. So het die eerste keer, dit kos my 'n stap om dinge reg te stel, dan is dit my kos twee stappe om dinge reg te stel. Hoeveel stappe is dit gaan neem om op te los dinge om vyf in die regte plek te sit? Drie. Want nou moet ek beweeg een, twee, drie. Hoeveel stappe gaan dit neem vier op die regte plek te sit? 4 plus 5, plus 6, plus 7. En so is dit wiskundig identies aan wat ons beskryf vir keuring soort. Ons het hierdie reeks dit is net toeneem. 1 plus 2 plus 3 plus 4, of omgekeerd, 7 plus 6 plus 5 plus 4 voeg vir vandag is doeleindes op die einde van N kwadraat. So laat my ook dat stipuleer borrel soort is ook in n vierkant. Want met borrelsortering, elk keer as ek gaan deur die lys, Ek neem ongeveer hoeveel stappe? Elke keer as ek letterlik loop van daar na daar? Sowat N stappe. Maar hoeveel keer mag ek nodig om te gaan deur die lys? Wel, ongeveer N tyd. Miskien N minus 1, maar rofweg n keer. Wel, hoekom is dit? Wel, met borrel soort, as Ons begin met borrelsortering, met die lys in die ergste moontlike situasie, wat weer heeltemal agtertoe, wat gaan gebeur? Ek gaan deur die lys, en die aantal een behoort al die pad daar. Maar met borrelsortering, hoe ver 'n mens beweeg op my eers deur die lys? Hoeveel kolle kry hy nader aan die regte plek? Net een. So as jy soort rede deur hierdie, elke keer deur hierdie algoritme, David se neem ongeveer N stappe. Maar hoeveel passe deur die lys is dit gaan neem vir een tot borrel aan die linkerkant waar dit hoort? Hy het om te beweeg soos, N spasies op hierdie manier. So net om die sortering doen van die lys, Ek het om heen en weer loop n keer. En elke keer, ek is op soek na n elemente. So doen dinge N N tye op die orde van N kwadraat. Nou, sal ons sien in sommige van die kortbroek wat ingebed in CS50 se volgende probleem stel, 'n ander benadering na hierdie, maar vir nou, laat ons net oorweeg 'n ander loop tye, veral as die sortering kinders te neem 'n bietjie van die tyd om te sink in. Wat is 'n algoritme ons het reeds gesien wat neem op die einde van n stappe? Wat moet 'n lineêre getal neem stappe wat ons tot dusver gesien het? Wat is dit? Die telefoongids soek. Die eerste algoritme. Reg? Waar ons lineêr soek vir Mike Smith? Inderdaad. Van week nul, toe ek begin draai een bladsy op 'n tyd, en ek het selfs gesê dat dit was soort van 'n lineêre gevoel algoritme, en ons het die foto op die raad met die reguit rooi lyn en die reguit geel lyn, diegene inderdaad was algoritmes wat in groot O van n. Want om Mike Smith in 'n telefoon boek van N bladsye, in die ergste geval, dalk my N stappe te neem. Wat oor die neem van bywoning? Een, twee, drie, vier, vyf, ses. Wat is die loop van die tyd van hierdie algoritme vir die neem van bywoning? Big O van n, want in teorie Ek moet almal in die kamer wys. Nou as 'n eenkant, wat oor die ander optimization vanaf week nul? Twee, vier, ses, agt, 10, 12. 'N Rekenaar wetenskaplike sou besef, wag 'n minuut, dit is op die einde van N gedeel deur twee stappe. Reg? Omdat ek doen twee mense op 'n slag. Maar ons gaan om te ignoreer diegene laer orde terme, en ons is net gaan om te gooi die kloof weg deur 2, en net sê, 'n groot O van n vir daardie algoritme as well. Wat van dié een? Ons sal slaan oor sommige van hierdie, maar wat was 'n algoritme wat log van N is? Dit het ongeveer meld N stappe? Die Verdeel en oorwin. Presies. Soos die telefoon boek voorbeeld in week nul en vroeër vandag, waar ons verdeel die probleem weer en weer en weer. Ons het dit op die bord in week zero as 'n geboë groen lyn, en ons het daardie dag was dit 'n logaritmiese algoritme. En inderdaad, die aantal stappe dit neem om te verdeel en oorwin voer, of binêre soek soos ons sal begin noem dit, soos in die telefoon boek, is op die einde van die log en stappe. En dit is 'n bietjie van 'n vreemde een. Wat neem 'n stap, of meer spesifiek 'n konstante aantal stappe? Miskien is dit twee, miskien is dit drie, maar 'n rekenaar wetenskaplike net vereenvoudig dit so groot O van 1, sommige konstante aantal stappe. Wat is iets wat jy kan doen nie neem 'n konstante aantal stappe? Wat is die loop tyd van klap? Konstante tyd. Reg? Soos, wat is die loop van die tyd enigiets wat net 'n mens doen operasie, soos druk F Hello World. Dit kan gesê word dat konstante tyd, tensy minder hoek geval met die druk F, Wat kan die loop van die tyd druk F eintlik? En waarom? Wat is n meting in daardie geval? GEHOOR: [onhoorbaar]. DAVID J. MALAN: Presies. Die aantal karakters Ons wil druk. So dit is baie konteks-sensitiewe. Vandag, het ons fokus op 'n baie letters en nommers hier op die bord. Maar dit kan ook wees karakters in 'n werklike string. So dit blyk daar is 'n ander maatreël wat sal begin omgee oor, en dit is die teenoorgestelde van die groot O, om so te praat. Dit is omega notasie. AANGESIEN groot O beteken wat is, die bogrens op jou loop tyd? Maksimaal, hoeveel tyd dalk iets te neem? Omega-- jammer dit hou kom up-- is die teenoorgestelde van wat, waardeur dit is 'n ondergrens op die bedrag van die tyd iets kon neem. Doen. Byvoorbeeld, wat is 'n algoritme wat neem altyd n vierkant stappe? Wel, een van die algoritmes wat ons gesien het vandag, in werklikheid, kan wees dat sowel. Seleksie soort. Seleksie soort is redelik dom. Selfs as die algorithm-- jammer, selfs As die skikking reeds gesorteer, seleksie soort gaan hou loop deur die lys om seker te maak dit het die kleinste element weer en weer en weer. En selfs al is julle mense in die gehoor weet dat, wag 'n minuut, jy reeds verby die kleinste element, die rekenaar weet nie dat totdat dit lyk al die pad deur die lys. Net so, 'n laer gebind dat kan ook in ag geneem word kan lineêre tyd. Hoeveel tyd neem dit om sorteer N elemente in die beste geval met behulp van iets soos borrel soort? Veronderstel jou lys is reeds gesorteer. Ons het gesê borrelsortering neem op die orde van N kwadraat stappe. Maar wat as dit is reeds gesorteer? Wat as jy besef na een keer deur die skikking dat jy nie swaps gemaak het? Het jy nodig om te hou om meer passe? Geen. So 'n laer gebind borrelsortering kan gesê lineêre te wees. Omega van n. En ons kan kyk na ander van hierdie so goed. So laat ons neem 'n vinnige blik op net 'n visualisering hier om te sien hoe hierdie self te onderskei. Ek gaan hier af gaan in hierdie bladsy wat beskikbaar is op die webwerf C50 se maar dit sal 'n pyn te werk te kry, aangesien dit gebruik 'n tegnologie genaamd Java applets, wat is 'n grootliks nie ondersteun hierdie dae, ten minste deur Chrome en sekere ander. En laat my gaan voort en versnel hierdie en verduidelik wat aangaan. Dit is 'n demonstrasie van die borrel soort, die eerste algoritme het ons gekyk na. En dit is 'n visualisering in dat elke van hierdie bars verteenwoordig 'n nommer. Hoe groter die bar, hoe groter die nommer. Die kleiner die bar, hoe kleiner die nommer. En wat jy kan visueel te sien, selfs hoewel dit gaan super vinnig, is dat die rooi bar is soos ek, loop heen en weer die oplos van probleme. Jy kan sien dat die groter elemente is inderdaad borrelende tot die regte, en die kleiner elemente is borrel tot aan die linkerkant. En af hier, as ons eintlik lyk nader, kan ons eintlik tel aantal vergelykings en swaps wat gemaak word. Maar in plaas daarvan, laat ons kyk by die tweede algoritme ons gekyk na vroeër met ons vrywilligers, seleksie soort. Visueel, dit het 'n baie ander effek. Maar dit is, weer, baie intuïtief, in dat ons hou die kies van die volgende kleinste element, en ons het 'n bietjie geluk. Dit het gevoel fundamenteel vinniger. Maar as ons hardloop hierdie weer en weer en weer met baie van die insette, sou ons sien dat dit inderdaad steeds in groot O van n vierkant. Kom ons doen 'n laaste een hier, voeg soort, wat die derde algoritme was ons gekyk na, en onthou dat hierdie een handel oor die elemente soos hulle ontmoetings, maar dan is dit dalk skofte dinge oor om plek te maak, invoeging elemente waar hulle hoort. En dit te eindig wat die finale uitslag. Nou al drie van dié gevoel redelik vinnig. En inderdaad, ek het hulle op 'n redelik goeie clip. Maar fundamenteel, hulle is almal mooi verskriklik, om eerlik te wees. Al hierdie algoritmes dusver wat loop in groot O van n kwadraat neem nogal 'n bietjie van ' tyd om te hardloop in die einde. En inderdaad, kan ons sien en voel dit laastens as ek trek die derde en finale demo. Dit is 'n ander visualisering wat gaan borrel soort wys aan die linkerkant, seleksie soort in die middel, en iets soos een van ons hand verhoog vroeër voorgestel, saamsmelt soort aan die regterkant. A Verdeel en oorwin strategie aan die regterkant. En dit is, in werklikheid, wat ons is gaan om te kyk na Woensdag. Maar laat ons tyd hierdie om te hardloop in parallel. Dit is min of meer dieselfde aantal elemente, al loop op dieselfde tyd. Borrel soort vs seleksie sorteer vs merge soort. Nou, hulle is almal hardloop in teorie op dieselfde tyd. Die SVE loop op 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 spoed dinge op. En nou, laat ons vergelyk dit in 'n laaste vorm. Ek gaan om voort te gaan webwerf CS50, waar ons het hierdie laaste skakel vir vandag, waar iemand op die internet vriendelik saam 'n video wat vang wat verskillende sorteer algoritmes klink soos. Dit is invoeging soort. [Piep] Waardeur jy aansoek doen 'n frekwensie gebaseer op die hoogte van die bar bar. Dit is borrelsortering. [Warped piep] Kom volgende is-- kom langs is-- seleksie soort, waar weer, ons kies die volgende kleinste element, en ons kan dit sien groei van links na regs. Merge soort, ons wenner dusver vandag. Let op hoe dit verdeel dinge in [onhoorbaar] helfte en kwarte. Gnome soort, wat ons het nie gepraat het, en visueel skep en audally 'n bietjie van 'n verskillende vorm en klank. Gaan heen en weer, skoonmaak dinge op. Kyk ook uit heapsort op die webwerf se man. En dit is dit. Ons sal jy sien die volgende keer. [Whooshing EN MUSIEK]