1 00:00:00,000 --> 00:00:00,488 2 00:00:00,488 --> 00:00:10,800 >> [Speel van musiek] 3 00:00:10,800 --> 00:00:13,500 David Malan: Alle reg. 4 00:00:13,500 --> 00:00:14,670 Alle reg, welkom terug. 5 00:00:14,670 --> 00:00:18,120 So dit is Week 4, die begin daarvan, reeds. 6 00:00:18,120 --> 00:00:21,320 En jy sal die laaste week onthou, ons sit kodeer opsy gesit is vir net 'n bietjie 7 00:00:21,320 --> 00:00:24,240 en ons begin praat 'n bietjie meer hoë-vlak, oor dinge soos 8 00:00:24,240 --> 00:00:28,130 soek-en sorteer, wat al ietwat eenvoudige idees, is 9 00:00:28,130 --> 00:00:31,840 verteenwoordiger van 'n klas van probleme jy sal begin om veral op te los 10 00:00:31,840 --> 00:00:34,820 as jy begin dink oor die finale projekte en interessante oplossings wat jy 11 00:00:34,820 --> 00:00:36,760 mag hê om werklike probleme. 12 00:00:36,760 --> 00:00:39,490 Nou borrel soort was een van die eenvoudigste sulke algoritmes, en dit 13 00:00:39,490 --> 00:00:42,900 gewerk het deur met hierdie klein getalle in 'n lys of in 'n verskeidenheid soort 14 00:00:42,900 --> 00:00:46,530 borrel hul weg op die top, en die groot getalle beweeg om hul pad af te 15 00:00:46,530 --> 00:00:47,930 die einde van die lys. 16 00:00:47,930 --> 00:00:50,650 >> En onthou dat ons kan visualiseer borrel soort 'n bietjie 17 00:00:50,650 --> 00:00:52,310 iets soos hierdie. 18 00:00:52,310 --> 00:00:53,640 So laat my voort te gaan en kliek op 'Begin. 19 00:00:53,640 --> 00:00:55,350 Ek het vooraf gekies borrel soort. 20 00:00:55,350 --> 00:00:58,920 En as jy onthou dat die langer blou lyne stel groot getalle, klein 21 00:00:58,920 --> 00:01:03,300 blou lyne stel klein getalle, soos ons gaan deur dit weer en weer en 22 00:01:03,300 --> 00:01:07,680 weer, vergelyking van twee bars langs elke ander in rooi, ons gaan die te ruil 23 00:01:07,680 --> 00:01:11,010 grootste en die kleinste indien hulle is buite orde. 24 00:01:11,010 --> 00:01:14,150 >> So dit sal gaan en gaan op en gaan op, en jy sal sien dat die groter 25 00:01:14,150 --> 00:01:16,700 elemente maak hul pad na die reg, en die kleiner elemente 26 00:01:16,700 --> 00:01:17,900 maak hul pad na die linkerkant. 27 00:01:17,900 --> 00:01:21,380 Maar ons het begin om te kwantifiseer die doeltreffendheid, die 28 00:01:21,380 --> 00:01:22,970 kwaliteit van hierdie algoritme. 29 00:01:22,970 --> 00:01:25,200 En ons het gesê dat in die ergste geval, hierdie algoritme het 30 00:01:25,200 --> 00:01:27,940 Ongeveer hoeveel stappe? 31 00:01:27,940 --> 00:01:28,980 >> So n vierkant. 32 00:01:28,980 --> 00:01:30,402 En wat was n? 33 00:01:30,402 --> 00:01:31,650 >> GEHOOR: Aantal elemente. 34 00:01:31,650 --> 00:01:32,790 >> David Malan: So n was die aantal elemente. 35 00:01:32,790 --> 00:01:33,730 En so sal ons doen dit dikwels. 36 00:01:33,730 --> 00:01:36,650 Enige tyd wat ons wil om te praat oor die grootte van 'n probleem of die grootte van 'n 37 00:01:36,650 --> 00:01:39,140 insette, of die bedrag van die tyd wat dit neem uitset te produseer, sal ons net 38 00:01:39,140 --> 00:01:41,610 veralgemeen wat die insette is as n. 39 00:01:41,610 --> 00:01:45,970 So terug in Week 0, die aantal bladsye in die telefoon boek was n. 40 00:01:45,970 --> 00:01:47,550 Die aantal studente wat in die kamer was n. 41 00:01:47,550 --> 00:01:49,630 So ook hier, ons volgende dat patroon. 42 00:01:49,630 --> 00:01:52,800 >> Nou n vierkant is nie besonder vinnig, so ons probeer om beter te doen. 43 00:01:52,800 --> 00:01:55,970 En so het ons gekyk na 'n paar ander algoritmes, waaronder 44 00:01:55,970 --> 00:01:57,690 was seleksie soort. 45 00:01:57,690 --> 00:01:59,180 So seleksie soort was 'n bietjie anders. 46 00:01:59,180 --> 00:02:03,130 Dit was amper 'n eenvoudiger, durf ek sê, waardeur ek begin by die begin van die 47 00:02:03,130 --> 00:02:06,740 lys van ons vrywilligers en ek het net weer en weer en weer het deur 48 00:02:06,740 --> 00:02:10,060 die lys, pluk uit die kleinste element op 'n slag en om hom of 49 00:02:10,060 --> 00:02:13,040 haar aan die begin van die lys. 50 00:02:13,040 --> 00:02:16,410 >> Maar hierdie, ook, sodra ons begin om te dink deur middel van die wiskunde en groter 51 00:02:16,410 --> 00:02:19,860 prentjie, gedink oor hoeveel keer Ek is heen en weer en weer terug 52 00:02:19,860 --> 00:02:24,090 en weer, ons het in die ergste geval, seleksie soort ook, was wat? 53 00:02:24,090 --> 00:02:24,960 n vierkant. 54 00:02:24,960 --> 00:02:27,490 Nou in die werklike wêreld, kan dit eintlik effens vinniger. 55 00:02:27,490 --> 00:02:30,620 Omdat weer, het ek nie hoef te hou back tracking nadat ek gesorteer van die 56 00:02:30,620 --> 00:02:31,880 kleinste elemente. 57 00:02:31,880 --> 00:02:35,090 Maar as ons dink oor baie groot n, en As jy soort van doen uit die wiskunde as 58 00:02:35,090 --> 00:02:39,170 Ek het op die raad, met die n geruite minus iets, alles 59 00:02:39,170 --> 00:02:41,850 Behalwe die n vierkant, een keer n regtig groot, nie 60 00:02:41,850 --> 00:02:42,850 regtig soveel saak nie. 61 00:02:42,850 --> 00:02:45,470 So as die rekenaar wetenskaplikes, ons sorteer draai 'n blinde oog na die kleiner 62 00:02:45,470 --> 00:02:49,220 faktore en fokus net op die faktor in 'n uitdrukking wat gaan maak 63 00:02:49,220 --> 00:02:50,330 die grootste verskil maak. 64 00:02:50,330 --> 00:02:52,840 >> Wel, laastens, het ons gekyk by te voeg soort. 65 00:02:52,840 --> 00:02:56,620 En dit was soortgelyk in die gees, maar eerder as om te gaan deur iteratief en 66 00:02:56,620 --> 00:03:01,250 kies die kleinste element een op 'n tyd, ek plaas het die hand dat ek 67 00:03:01,250 --> 00:03:04,070 gehandel is, en ek het besluit, al reg, jy hoort hier. 68 00:03:04,070 --> 00:03:06,160 Daarna het ek verhuis na die volgende element en besluit dat hy of 69 00:03:06,160 --> 00:03:07,470 sy behoort hier. 70 00:03:07,470 --> 00:03:08,810 En dan het ek verhuis oor en oor. 71 00:03:08,810 --> 00:03:11,780 En ek kan nie, langs die pad, skuif hierdie ouens in orde te 72 00:03:11,780 --> 00:03:13,030 om plek te maak vir hulle. 73 00:03:13,030 --> 00:03:16,880 So dit was 'n soort van die geestelike ommekeer van seleksie soort wat ons 74 00:03:16,880 --> 00:03:18,630 genoem voeg soort. 75 00:03:18,630 --> 00:03:20,810 >> So het hierdie onderwerpe te voorkom in die werklike wêreld. 76 00:03:20,810 --> 00:03:23,640 Net 'n paar jaar gelede, toe 'n sekere senator hardloop vir president, 77 00:03:23,640 --> 00:03:27,160 Eric Schmidt, teen die tyd dat die hoof uitvoerende beampte van Google, eintlik die geleentheid gehad 78 00:03:27,160 --> 00:03:28,040 om hom te ondervra. 79 00:03:28,040 --> 00:03:32,010 En ons het gedink ons ​​hierdie YouTube wil deel clip vir jou hier, as ons kon draai 80 00:03:32,010 --> 00:03:32,950 die volume. 81 00:03:32,950 --> 00:03:39,360 >> [Video speel] 82 00:03:39,360 --> 00:03:44,620 >> -Nou, Senator, jy is hier op Google, en ek wil om te dink aan die presidensie 83 00:03:44,620 --> 00:03:46,042 as 'n werksonderhoud. 84 00:03:46,042 --> 00:03:47,770 >> [Gelag] 85 00:03:47,770 --> 00:03:50,800 >> -Nou is dit moeilik om te kry 'n werk as president. 86 00:03:50,800 --> 00:03:52,480 En jy gaan deur middel van die pogings nou. 87 00:03:52,480 --> 00:03:54,330 Dit is ook moeilik om 'n werk by Google te kry. 88 00:03:54,330 --> 00:03:59,610 Ons het vrae en ons vra ons kandidate vrae. 89 00:03:59,610 --> 00:04:02,250 En hierdie een is van Larry Schwimmer. 90 00:04:02,250 --> 00:04:05,325 >> [Gelag] 91 00:04:05,325 --> 00:04:06,400 -Julle dink ek is 'n grap? 92 00:04:06,400 --> 00:04:08,750 Dit is reg hier. 93 00:04:08,750 --> 00:04:12,110 Wat is die mees doeltreffende manier om te sorteer 'n miljoen twee-bit heelgetalle? 94 00:04:12,110 --> 00:04:15,810 >> [Gelag] 95 00:04:15,810 --> 00:04:18,260 >> -Wel, uh - 96 00:04:18,260 --> 00:04:19,029 >> -Ek-is jammer. 97 00:04:19,029 --> 00:04:19,745 Miskien moet ons - 98 00:04:19,745 --> 00:04:21,000 >> -Nee, nee, nee, nee, nee. 99 00:04:21,000 --> 00:04:21,470 >> -Dit is nie 'n - 100 00:04:21,470 --> 00:04:22,185 OK. 101 00:04:22,185 --> 00:04:25,328 >> -Ek dink die borrel soort sou wees op die verkeerde manier om te gaan. 102 00:04:25,328 --> 00:04:26,792 >> [Gelag] 103 00:04:26,792 --> 00:04:28,510 >> [Juig en applous] 104 00:04:28,510 --> 00:04:31,211 >> -Kom op, wat hom dit vertel? 105 00:04:31,211 --> 00:04:32,155 OK. 106 00:04:32,155 --> 00:04:33,350 >> [Einde video-vertoning] 107 00:04:33,350 --> 00:04:35,070 >> David Malan: So daar het jy dit. 108 00:04:35,070 --> 00:04:39,600 So het ons begin om hierdie bedryf te kwantifiseer tye, om so te spreek, met iets 109 00:04:39,600 --> 00:04:43,480 genoem asimptotiese notering, wat net verwys na ons soort van die draai 110 00:04:43,480 --> 00:04:47,420 'n blinde oog op die kleiner faktore en net na die loop van die tyd, 111 00:04:47,420 --> 00:04:51,250 die prestasie van hierdie algoritmes, as n regtig groot met verloop van tyd. 112 00:04:51,250 --> 00:04:55,110 En so het ons 'n groot O. en Big O verteenwoordig iets wat ons gedink 113 00:04:55,110 --> 00:04:57,000 van so 'n bogrens. 114 00:04:57,000 --> 00:04:59,570 En eintlik, Barry, ons kan verlaag as die mikrofoon 'n bietjie? 115 00:04:59,570 --> 00:05:01,040 >> Ons het gedink dat van hierdie is 'n bogrens. 116 00:05:01,040 --> 00:05:04,710 So groot O van n vierkant beteken dat in die ergste geval, iets soos 117 00:05:04,710 --> 00:05:07,780 seleksie soort sou neem n 'vierkante stappe. 118 00:05:07,780 --> 00:05:10,310 Of iets soos voeg soort sou n vierkant stappe. 119 00:05:10,310 --> 00:05:15,150 Nou vir iets soos te voeg soort, wat was die ergste geval? 120 00:05:15,150 --> 00:05:18,200 Gegewe 'n skikking, wat is die ergste moontlike scenario wat jy kan vind 121 00:05:18,200 --> 00:05:20,650 jouself gekonfronteer met? 122 00:05:20,650 --> 00:05:21,860 >> Dit is heeltemal agteruit, reg? 123 00:05:21,860 --> 00:05:24,530 Want as dit is heeltemal agteruit, jy het 'n hele klomp van die werk te doen. 124 00:05:24,530 --> 00:05:26,420 Want as jy heeltemal agtertoe, jy gaan die te vind 125 00:05:26,420 --> 00:05:28,840 grootste element hier, selfs al dit behoort daar. 126 00:05:28,840 --> 00:05:31,140 So jy gaan om te sê, alles reg, by hierdie oomblik in tyd, kan jy hier hoort nie, 127 00:05:31,140 --> 00:05:32,310 sodat jy laat dit alleen. 128 00:05:32,310 --> 00:05:35,425 >> Dan besef jy, o, damn, ek het om te skuif dit effens kleiner element te 129 00:05:35,425 --> 00:05:36,470 links van jou. 130 00:05:36,470 --> 00:05:38,770 Dan moet ek dit weer te doen en weer en weer. 131 00:05:38,770 --> 00:05:41,410 En as ek loop heen en weer, moet jy sou soort van voel die prestasie van 132 00:05:41,410 --> 00:05:45,540 dat algoritme, want voortdurend is ek geskuifel almal anders in die 133 00:05:45,540 --> 00:05:46,510 verskeidenheid plek te maak vir dit. 134 00:05:46,510 --> 00:05:47,750 So wat is die ergste geval. 135 00:05:47,750 --> 00:05:48,570 >> In teenstelling - 136 00:05:48,570 --> 00:05:50,320 en dit was 'n fotonische lewe laaste keer - 137 00:05:50,320 --> 00:05:54,065 Ons het gesê dat voeg soort was 'n omega van wat? 138 00:05:54,065 --> 00:05:57,530 Wat is die beste geval loop tyd van die inplanting soort? 139 00:05:57,530 --> 00:05:58,520 So dit is eintlik n. 140 00:05:58,520 --> 00:06:00,980 Dit was die leë dat ons verlaat op die bord laaste tyd. 141 00:06:00,980 --> 00:06:03,160 >> En dit is omega van n, want hoekom? 142 00:06:03,160 --> 00:06:06,630 Wel, in die beste geval, wat is voeg soort gaan oorhandig word? 143 00:06:06,630 --> 00:06:09,830 Wel, 'n lys wat is heeltemal gesorteer reeds, minimale werk te doen. 144 00:06:09,830 --> 00:06:12,460 Maar wat is netjies oor te voeg soort is dat omdat dit begin hier en 145 00:06:12,460 --> 00:06:15,340 besluit, o, jy is die aantal een, jy behoort hier. 146 00:06:15,340 --> 00:06:16,970 O, wat 'n goeie geluk. 147 00:06:16,970 --> 00:06:17,740 >> Jy is die nommer twee. 148 00:06:17,740 --> 00:06:19,030 Jy kan ook hier hoort nie. 149 00:06:19,030 --> 00:06:21,010 Nommer drie, nog beter, jy hier hoort nie. 150 00:06:21,010 --> 00:06:25,210 Sodra dit raak tot aan die einde van die lys, per inplanting soort se pseudokode 151 00:06:25,210 --> 00:06:28,010 dat ons stap deur mondelings laaste keer, is dit gedoen. 152 00:06:28,010 --> 00:06:32,790 Maar seleksie soort, daarenteen, bly doen wat? 153 00:06:32,790 --> 00:06:35,260 >> Aan die gang gehou deur die lys weer en weer en weer. 154 00:06:35,260 --> 00:06:39,160 Omdat die sleutel insig was daar net sodra jy het al die pad na die 155 00:06:39,160 --> 00:06:42,500 einde van die lys kan jy seker wees dat die element wat jy gekies het, was 156 00:06:42,500 --> 00:06:45,560 inderdaad die oomblik kleinste element. 157 00:06:45,560 --> 00:06:48,920 So hierdie verskillende verstandelike modelle einde up opbrengs van 'n paar baie werklike wêreld 158 00:06:48,920 --> 00:06:53,130 verskille vir ons, sowel as dié teoretiese asimptotiese verskille. 159 00:06:53,130 --> 00:06:56,910 >> So net om te vat, dan, 'n groot O van n vierkantig, het ons gesien dat 'n paar sulke 160 00:06:56,910 --> 00:06:58,350 algoritmes tot dusver. 161 00:06:58,350 --> 00:06:59,580 Big O van n? 162 00:06:59,580 --> 00:07:02,870 Wat is 'n algoritme wat kon word gesê dat groot O van n? 163 00:07:02,870 --> 00:07:06,930 In die ergste geval, dit neem 'n lineêre aantal stappe. 164 00:07:06,930 --> 00:07:07,810 >> OK, lineêre soek. 165 00:07:07,810 --> 00:07:10,470 En in die ergste geval, waar is die element wat jy soek vir wanneer 166 00:07:10,470 --> 00:07:12,950 toepassing van lineêre soek? 167 00:07:12,950 --> 00:07:14,680 >> OK, in die ergste geval, dit is nie eens daar nie. 168 00:07:14,680 --> 00:07:17,000 Of in die tweede ergste geval, is dit al die pad in die einde, wat 169 00:07:17,000 --> 00:07:18,880 plus-of-minus 'n een-stap verskil. 170 00:07:18,880 --> 00:07:21,180 So aan die einde van die dag, Ons kan sê dit is lineêr. 171 00:07:21,180 --> 00:07:23,910 Big O van n sal lineêre soek wees, want in die ergste geval, die 172 00:07:23,910 --> 00:07:26,610 element is nie eens daar of is dit al die pad aan die einde. 173 00:07:26,610 --> 00:07:29,370 >> Wel, 'n groot O van log van n. 174 00:07:29,370 --> 00:07:32,760 Ons het nie gepraat in groot detail oor hierdie, maar ons het dit gesien voor. 175 00:07:32,760 --> 00:07:36,840 Wat loop in die sogenaamde logaritmiese tyd, in die ergste geval? 176 00:07:36,840 --> 00:07:38,500 >> Ja, so binêre soek. 177 00:07:38,500 --> 00:07:42,930 En binêre soek in die ergste geval kan die element iewers in 'n 178 00:07:42,930 --> 00:07:45,640 die middel, of iewers binne-in die skikking. 179 00:07:45,640 --> 00:07:48,040 Maar jy vind dit wanneer jy verdeel die lys in die helfte, in 180 00:07:48,040 --> 00:07:48,940 helfte, in die helfte, in die helfte. 181 00:07:48,940 --> 00:07:50,200 En dan voila, dit is daar. 182 00:07:50,200 --> 00:07:52,500 Of weer, die ergste geval, dit is nie eens daar nie. 183 00:07:52,500 --> 00:07:56,770 Maar jy weet nie dat dit nie daar totdat jy soort van bereik dat die laaste 184 00:07:56,770 --> 00:08:00,470 bottom-die meeste elemente by halveer en halveer en halveer. 185 00:08:00,470 --> 00:08:01,400 >> Big O van 1. 186 00:08:01,400 --> 00:08:03,540 Sodat ons kan groot O van 2, groot O van 3. 187 00:08:03,540 --> 00:08:06,260 Wanneer jy wil net 'n konstante getal, ons het net soort van net vereenvoudig 188 00:08:06,260 --> 00:08:07,280 dat so 'n groot O van 1. 189 00:08:07,280 --> 00:08:10,440 Selfs al as realisties, neem dit 2 of selfs 100 stappe, indien dit is 'n 190 00:08:10,440 --> 00:08:13,680 konstante aantal stappe, ons net sê groot O van 1. 191 00:08:13,680 --> 00:08:15,930 Wat is 'n algoritme wat in 'n groot O van 1? 192 00:08:15,930 --> 00:08:18,350 >> GEHOOR: Dit vind van die lengte van 'n veranderlike. 193 00:08:18,350 --> 00:08:21,090 >> David Malan: Dit vind van die lengte van 'n veranderlike? 194 00:08:21,090 --> 00:08:23,870 >> GEHOOR: Nee, die lengte As dit is reeds uitgesorteer. 195 00:08:23,870 --> 00:08:24,160 >> David Malan: Goed. 196 00:08:24,160 --> 00:08:27,850 OK, so vind die lengte van iets As die lengte van iets, soos 197 00:08:27,850 --> 00:08:30,020 'n skikking, gestoor word in 'n veranderlike. 198 00:08:30,020 --> 00:08:33,380 Want jy kan net lees die veranderlike, of druk die veranderlike, of 199 00:08:33,380 --> 00:08:34,960 net oor die algemeen toegang tot daardie veranderlike. 200 00:08:34,960 --> 00:08:37,299 En siedaar, wat neem konstante tyd. 201 00:08:37,299 --> 00:08:38,909 >> In teenstelling hiermee, dink terug te krap. 202 00:08:38,909 --> 00:08:42,460 Dink terug aan die eerste week van C, bel net printf en druk 203 00:08:42,460 --> 00:08:46,240 iets op die skerm is waarskynlik konstante tyd, want dit neem net 204 00:08:46,240 --> 00:08:50,880 'n aantal van die CPU siklusse aan te toon dat die teks op die skerm. 205 00:08:50,880 --> 00:08:52,720 Of wag - dit doen? 206 00:08:52,720 --> 00:08:56,430 Hoe anders kan ons model prestasie van printf? 207 00:08:56,430 --> 00:09:00,420 Sou iemand wil om te verskil, wat Miskien is dit is nie regtig 'n konstante tyd? 208 00:09:00,420 --> 00:09:03,600 In watter sin kan printf se loop tyd, eintlik die druk van 'n string op 209 00:09:03,600 --> 00:09:05,580 die skerm, iets anders as konstant. 210 00:09:05,580 --> 00:09:07,860 >> GEHOOR: [onhoorbaar]. 211 00:09:07,860 --> 00:09:08,230 >> David Malan: Ja. 212 00:09:08,230 --> 00:09:09,300 So dit hang af van ons perspektief. 213 00:09:09,300 --> 00:09:13,390 As ons dink eintlik van die insette te printf as die string, en 214 00:09:13,390 --> 00:09:16,380 Daarom het ons meet die grootte van daardie insette deur sy lengte - so kom ons noem 215 00:09:16,380 --> 00:09:17,780 dat lengte n so goed - 216 00:09:17,780 --> 00:09:21,990 waarskynlik, is printf self groot O van n want dit gaan jou n stappe te neem 217 00:09:21,990 --> 00:09:24,750 om uit te druk elk van die n karakters, waarskynlik. 218 00:09:24,750 --> 00:09:27,730 Ten minste tot die mate dat ons aanvaar dat miskien is dit die gebruik van 'n for-lus 219 00:09:27,730 --> 00:09:28,560 onder die kap. 220 00:09:28,560 --> 00:09:30,860 >> Maar ons sal moet kyk na wat Kode te verstaan ​​dit beter. 221 00:09:30,860 --> 00:09:33,650 En inderdaad, wanneer jy ouens begin ontleding van jou eie algoritmes, sal jy 222 00:09:33,650 --> 00:09:34,900 letterlik net dat doen. 223 00:09:34,900 --> 00:09:37,765 Soort van oogbal jou kode en dink - alles reg, ek het hierdie lus 224 00:09:37,765 --> 00:09:41,870 hier of ek 'n geneste lusse hier, wat gaan N Dinge n keer te doen, 225 00:09:41,870 --> 00:09:46,050 en jy kan sorteer rede om jou manier deur middel van die kode, selfs al is dit 226 00:09:46,050 --> 00:09:47,980 pseudokode en nie die werklike kode. 227 00:09:47,980 --> 00:09:49,730 >> So, wat oor omega van n vierkant? 228 00:09:49,730 --> 00:09:53,582 Wat was 'n algoritme wat in die beste geval, nog steeds het n vierkantige stappe? 229 00:09:53,582 --> 00:09:54,014 Ja? 230 00:09:54,014 --> 00:09:54,880 >> GEHOOR: [onhoorbaar]. 231 00:09:54,880 --> 00:09:55,900 >> David Malan: So seleksie soort. 232 00:09:55,900 --> 00:09:59,150 Want in daardie probleem werklik verminder aan die feit dat die weer, ek weet nie 233 00:09:59,150 --> 00:10:02,600 Ek het gevind dat die huidige kleinste tot Ek het bewys al die darn elemente. 234 00:10:02,600 --> 00:10:08,050 So omega van, sê, n, ons net vorendag gekom met een. 235 00:10:08,050 --> 00:10:09,300 Invoeging soort. 236 00:10:09,300 --> 00:10:12,370 As die lys gebeur word uitgesorteer reeds, in die beste geval het ons net 237 00:10:12,370 --> 00:10:15,090 Een Pass te maak deur dit, op watter punt ons is seker. 238 00:10:15,090 --> 00:10:17,890 En dan is dit kan gesê word om lineêre, vir seker. 239 00:10:17,890 --> 00:10:20,570 >> Wat van omega van 1? 240 00:10:20,570 --> 00:10:23,790 Wat, in die beste geval is, kan neem 'n konstante aantal stappe? 241 00:10:23,790 --> 00:10:27,220 So lineêre soek, as jy net kry gelukkig en die element wat jy soek 242 00:10:27,220 --> 00:10:31,000 reg aan die begin van die lys, As dit is waar jy die begin van jou 243 00:10:31,000 --> 00:10:33,070 lineêre traversal van die lys. 244 00:10:33,070 --> 00:10:35,180 >> En dit is waar van 'n aantal van die dinge. 245 00:10:35,180 --> 00:10:37,660 Byvoorbeeld, selfs binêre soek is omega van 1. 246 00:10:37,660 --> 00:10:40,310 Omdat wat as jy regtig darn gelukkig en smack-dab in die middel van 247 00:10:40,310 --> 00:10:42,950 jou skikking is die aantal jy soek? 248 00:10:42,950 --> 00:10:45,730 So kan jy gelukkig is daar, as well. 249 00:10:45,730 --> 00:10:49,190 >> Hierdie een, laastens, omega van n log n. 250 00:10:49,190 --> 00:10:52,573 So n log n, ons het nie regtig praat nie, maar - 251 00:10:52,573 --> 00:10:53,300 >> GEHOOR: Merge soort? 252 00:10:53,300 --> 00:10:53,960 >> David Malan: Merge soort. 253 00:10:53,960 --> 00:10:56,920 Dit was die fotonische lewe van verlede tyd, waar ons voorgestel het, en ons het 254 00:10:56,920 --> 00:10:58,600 visueel, dat daar algoritmes. 255 00:10:58,600 --> 00:11:02,470 En voeg soort van net een so 'n algoritme wat is fundamenteel vinniger 256 00:11:02,470 --> 00:11:03,450 as sommige van die ander ouens. 257 00:11:03,450 --> 00:11:07,800 Trouens, saam te smelt kort is nie net in die beste geval n log n, in die ergste 258 00:11:07,800 --> 00:11:09,460 geval n log n. 259 00:11:09,460 --> 00:11:14,540 En wanneer jy hierdie sameloop van omega en 'n groot O synde die dieselfde ding? 260 00:11:14,540 --> 00:11:17,310 Ons kan eintlik beskryf wat as wat is genoem theta, al is dit 'n 261 00:11:17,310 --> 00:11:18,220 bietjie minder algemeen. 262 00:11:18,220 --> 00:11:21,730 Maar dit beteken net die twee grense, in hierdie geval, is dieselfde. 263 00:11:21,730 --> 00:11:25,770 >> So saamsmelt soort, wat beteken dit regtig neer op vir ons? 264 00:11:25,770 --> 00:11:27,000 Wel, onthou die motivering. 265 00:11:27,000 --> 00:11:30,340 Laat my toe om 'n ander animasie wat ons het nie kyk na die laaste keer. 266 00:11:30,340 --> 00:11:33,390 Hierdie een is, dieselfde idee nie, maar dit is 'n bietjie groter. 267 00:11:33,390 --> 00:11:36,160 En ek gaan om voort te gaan en wys eerste - ons voeg soort op 268 00:11:36,160 --> 00:11:39,410 die top links, dan seleksie soort, borrel soort, 'n paar van die ander vorme - 269 00:11:39,410 --> 00:11:42,670 dop en vinnig - dat ons nie gepraat oor, en hoop en voeg soort. 270 00:11:42,670 --> 00:11:47,090 >> So ten minste probeer om jou oë te fokus op die top drie op die linker-en dan 271 00:11:47,090 --> 00:11:49,120 saamsmelt sorteer toe ek op Hierdie groen pyl. 272 00:11:49,120 --> 00:11:51,900 Maar ek sal laat almal van hulle loop, net om te gee jou 'n gevoel van die diversiteit van 273 00:11:51,900 --> 00:11:53,980 algoritmes wat bestaan ​​in die wêreld. 274 00:11:53,980 --> 00:11:56,180 Ek gaan hierdie termyn te laat net vir 'n paar sekondes. 275 00:11:56,180 --> 00:11:59,640 En as jy fokus jou oë - kies 'n algoritme, fokus op dit net vir 'n 276 00:11:59,640 --> 00:12:02,970 sekondes - jy sal begin om te sien patroon wat dit die implementering. 277 00:12:02,970 --> 00:12:04,530 >> Merge soort, kennisgewing, gedoen word. 278 00:12:04,530 --> 00:12:06,430 Hoop sorteer, vinnige soort, dop - 279 00:12:06,430 --> 00:12:09,480 so dit lyk asof ons het die drie ergste algoritmes verlede week. 280 00:12:09,480 --> 00:12:12,960 Maar dit is goed dat ons hier is vandag kyk na saamsmelt soort, wat een van die 281 00:12:12,960 --> 00:12:16,500 die wat makliker is, is om te kyk na, selfs hoewel dit waarskynlik sal buig jou gedagtes 282 00:12:16,500 --> 00:12:17,490 net 'n bietjie. 283 00:12:17,490 --> 00:12:21,130 Hier kan ons sien hoeveel seleksie soort suig. 284 00:12:21,130 --> 00:12:24,600 >> Maar aan die ander kant, is dit regtig maklik om te implementeer. 285 00:12:24,600 --> 00:12:28,160 En dalk ook vir P Stel 3, dit is een van die algoritmes jy verkies om te implementeer 286 00:12:28,160 --> 00:12:28,960 vir die standaard uitgawe. 287 00:12:28,960 --> 00:12:30,970 Heeltemal fyn, heeltemal korrek. 288 00:12:30,970 --> 00:12:35,210 >> Maar weereens, as n groot kry, as jy kies 'n vinniger algoritme te implementeer 289 00:12:35,210 --> 00:12:39,020 wil saamsmelt soort, is die kans in groter en groter insette, jou kode is net 290 00:12:39,020 --> 00:12:39,800 gaan om vinniger te hardloop. 291 00:12:39,800 --> 00:12:41,090 Jou webwerf gaan beter werk. 292 00:12:41,090 --> 00:12:42,650 Jou gebruikers gaan gelukkiger wees. 293 00:12:42,650 --> 00:12:45,280 En so is daar hierdie effekte van die werklikheid te gee 294 00:12:45,280 --> 00:12:47,350 ons 'n paar dieper gedink. 295 00:12:47,350 --> 00:12:49,990 >> So kom ons neem 'n blik op wat saamsmelt soort is eintlik alles oor. 296 00:12:49,990 --> 00:12:52,992 Die cool ding is dat saamsmelt soort is net hierdie. 297 00:12:52,992 --> 00:12:56,300 Dit is, weer, wat ons geroep pseudokode, pseudokode wese 298 00:12:56,300 --> 00:12:57,720 Engels-agtige sintaksis. 299 00:12:57,720 --> 00:12:59,890 En die eenvoud soort van fassinerend. 300 00:12:59,890 --> 00:13:02,840 >> So op die insette van n elemente - sodat beteken net, hier is 'n skikking. 301 00:13:02,840 --> 00:13:04,000 Dit het 'n dinge in dit. 302 00:13:04,000 --> 00:13:05,370 Dit is al wat ons daar is gesê. 303 00:13:05,370 --> 00:13:07,560 >> As n is minder as 2, terug te keer. 304 00:13:07,560 --> 00:13:08,640 So dit is net die triviale geval. 305 00:13:08,640 --> 00:13:12,580 As n is minder as 2, dan natuurlik is dit 1 of 0, in welke geval die ding 306 00:13:12,580 --> 00:13:14,780 is reeds gesorteer of nie bestaan ​​nie, sodat net terug te keer. 307 00:13:14,780 --> 00:13:15,900 Daar is niks om te doen. 308 00:13:15,900 --> 00:13:18,360 So dit is 'n eenvoudige saak te ruk af. 309 00:13:18,360 --> 00:13:20,110 >> Else, het ons drie stappe. 310 00:13:20,110 --> 00:13:23,650 Sorteer die linker helfte van die elemente, soort die reg om die helfte van die elemente, 311 00:13:23,650 --> 00:13:26,650 en dan saam te smelt die gesorteer helftes. 312 00:13:26,650 --> 00:13:29,400 Wat is interessant hier is dat Ek is soort van vaar, reg? 313 00:13:29,400 --> 00:13:32,300 Daar is 'n soort van 'n omsendbrief definisie hierdie algoritme. 314 00:13:32,300 --> 00:13:35,986 In watter sin is hierdie algoritme se definisie omsendbrief? 315 00:13:35,986 --> 00:13:37,850 >> GEHOOR: [onhoorbaar]. 316 00:13:37,850 --> 00:13:41,670 >> David Malan: Ja, my sorteringsalgoritme, twee van sy stappe is "soort 317 00:13:41,670 --> 00:13:44,640 iets "En. sodat lei tot die vraag, nou ja, ek wat ek gaan gebruik 318 00:13:44,640 --> 00:13:46,460 die linker helfte te sorteer en die reg om die helfte? 319 00:13:46,460 --> 00:13:49,600 En die skoonheid hier is dat selfs al weer, dit is die gedagte-buiging 320 00:13:49,600 --> 00:13:54,030 deel potensieel, kan jy gebruik dieselfde algoritme die linker helfte te sorteer. 321 00:13:54,030 --> 00:13:54,700 >> Maar wag 'n minuut. 322 00:13:54,700 --> 00:13:57,070 Wanneer jy aan die uit te sorteer linker helfte, wat is die twee 323 00:13:57,070 --> 00:13:58,240 stappe gaan volgende wees? 324 00:13:58,240 --> 00:14:00,550 Ons sal sorteer die linker helfte van die linker helfte en die reg 325 00:14:00,550 --> 00:14:01,420 helfte van die linker helfte. 326 00:14:01,420 --> 00:14:04,430 Damn, hoe kan ek sorteer die twee helftes of huisvesting, wat nou? 327 00:14:04,430 --> 00:14:05,260 >> Maar dit is OK. 328 00:14:05,260 --> 00:14:07,830 Ons het 'n sorteeralgoritme hier. 329 00:14:07,830 --> 00:14:10,660 En selfs al sou jy bekommerd wees op eerste van hierdie is 'n soort van 'n oneindige 330 00:14:10,660 --> 00:14:12,780 lus, dit is 'n siklus wat nooit gaan eindig - dit gaan 331 00:14:12,780 --> 00:14:15,770 eindig keer wat gebeur? 332 00:14:15,770 --> 00:14:16,970 Sodra n is minder as 2. 333 00:14:16,970 --> 00:14:19,180 Wat uiteindelik gaan gebeur, want as jy hou halveer en 334 00:14:19,180 --> 00:14:23,020 halveer in halveer hierdie helftes, sekerlik uiteindelik sal jy gaan aan die einde 335 00:14:23,020 --> 00:14:25,350 met net 1 of 0 elemente. 336 00:14:25,350 --> 00:14:28,500 By watter punt, hierdie algoritme sê jy klaar is. 337 00:14:28,500 --> 00:14:31,020 >> Dus is die werklike magie in hierdie algoritme blyk te wees in 338 00:14:31,020 --> 00:14:33,470 dat die finale stap, saam te smelt. 339 00:14:33,470 --> 00:14:37,190 Dat eenvoudige idee net samesmelting twee dinge, dit is wat uiteindelik gaan 340 00:14:37,190 --> 00:14:40,920 om voorsiening te maak vir ons 'n verskeidenheid van uit te sorteer, kom ons sê, agt elemente. 341 00:14:40,920 --> 00:14:44,410 So ek het agt meer stres balle hier, agt stukkies papier, en een 342 00:14:44,410 --> 00:14:45,500 Google Glass - 343 00:14:45,500 --> 00:14:46,140 wat ek kry om te hou. 344 00:14:46,140 --> 00:14:46,960 >> [Gelag] 345 00:14:46,960 --> 00:14:48,970 >> David Malan: As ons kon neem agt vrywilligers, en laat ons kyk of ons kan 346 00:14:48,970 --> 00:14:51,430 speel dit uit, so. 347 00:14:51,430 --> 00:14:52,500 Sjoe, OK. 348 00:14:52,500 --> 00:14:53,565 Rekenaarwetenskap is om pret. 349 00:14:53,565 --> 00:14:54,320 Alle regte. 350 00:14:54,320 --> 00:14:57,770 So hoe oor julle drie, grootste hand daar. 351 00:14:57,770 --> 00:14:58,580 Vier in die rug. 352 00:14:58,580 --> 00:15:02,220 En hoe oor ons sal doen wat jy drie in hierdie ry? 353 00:15:02,220 --> 00:15:03,390 En vier in die voorkant. 354 00:15:03,390 --> 00:15:04,920 So jy agt, kom op. 355 00:15:04,920 --> 00:15:12,060 >> [Gelag] 356 00:15:12,060 --> 00:15:13,450 >> David Malan: Ek is eintlik nie seker wat dit is. 357 00:15:13,450 --> 00:15:14,810 Is dit die stres balle? 358 00:15:14,810 --> 00:15:16,510 Die lessenaar lampe? 359 00:15:16,510 --> 00:15:18,650 Die materiaal? 360 00:15:18,650 --> 00:15:19,680 Die internet? 361 00:15:19,680 --> 00:15:20,160 >> OK. 362 00:15:20,160 --> 00:15:21,310 So kom op. 363 00:15:21,310 --> 00:15:22,310 Wie wil - 364 00:15:22,310 --> 00:15:23,570 hou kom. 365 00:15:23,570 --> 00:15:24,240 Kom ons kyk. 366 00:15:24,240 --> 00:15:26,460 En dit sit jy in plek - 367 00:15:26,460 --> 00:15:27,940 jy is in plek een. 368 00:15:27,940 --> 00:15:28,670 Uh-oh, wag 'n minuut. 369 00:15:28,670 --> 00:15:30,760 1, 2, 3, 4, 5, 6, 7 - O, goed. 370 00:15:30,760 --> 00:15:31,310 Alle reg, ons is goed. 371 00:15:31,310 --> 00:15:35,130 Alle reg, sodat almal 'n sitplek, maar nie op die Google Glass. 372 00:15:35,130 --> 00:15:36,475 Laat my toe om te ry hierdie up. 373 00:15:36,475 --> 00:15:37,115 Wat is jou naam? 374 00:15:37,115 --> 00:15:37,440 >> MICHELLE: Michelle. 375 00:15:37,440 --> 00:15:38,090 >> David Malan: Michelle? 376 00:15:38,090 --> 00:15:42,000 Alle reg, jy lyk soos die geek, as dit is OK. 377 00:15:42,000 --> 00:15:44,625 Wel, ek doen ook, dink ek, vir net 'n oomblik. 378 00:15:44,625 --> 00:15:45,875 Alle reg, bystand. 379 00:15:45,875 --> 00:15:48,510 380 00:15:48,510 --> 00:15:50,950 Ons het probeer om vorendag te kom met 'n gebruik geval vir Google Glass, en ons 381 00:15:50,950 --> 00:15:53,750 gedink dit sou pret wees om te doen net wanneer mense op die verhoog is. 382 00:15:53,750 --> 00:15:57,120 Ons sal rekord van die wêreld uit hulle perspektief. 383 00:15:57,120 --> 00:15:58,410 Alle regte. 384 00:15:58,410 --> 00:15:59,830 Nie seker watter Google bedoel is. 385 00:15:59,830 --> 00:16:02,260 Goed, as jy nie omgee nie dra dit vir die volgende ongemaklike minute, 386 00:16:02,260 --> 00:16:03,150 wat jou sal wonderlik wees. 387 00:16:03,150 --> 00:16:08,620 >> Alle reg, so ons het hier 'n verskeidenheid van elemente, en dat skikking, soos per die 388 00:16:08,620 --> 00:16:11,480 stukkies papier in hierdie mense se hande, is tans ongesorteerde. 389 00:16:11,480 --> 00:16:12,050 >> MICHELLE: O, dis so weird. 390 00:16:12,050 --> 00:16:12,810 >> David Malan: Dit is nogal baie random. 391 00:16:12,810 --> 00:16:15,760 En in 'n oomblik, gaan ons om te probeer te implementeer saamsmelt soort saam 392 00:16:15,760 --> 00:16:17,950 en sien dat die sleutel insig is. 393 00:16:17,950 --> 00:16:21,970 En die truuk hier met saamsmelt soort is iets wat ons nie aanvaar nie. 394 00:16:21,970 --> 00:16:24,030 Ons het eintlik 'n paar addisionele ruimte. 395 00:16:24,030 --> 00:16:26,650 So, wat gaan wees veral interessant oor hierdie is dat hierdie 396 00:16:26,650 --> 00:16:29,270 ouens gaan om rond te beweeg 'n bietjie bietjie, want ek gaan om te aanvaar dat 397 00:16:29,270 --> 00:16:31,880 daar is 'n ekstra verskeidenheid van ruimte, sê, reg agter hulle. 398 00:16:31,880 --> 00:16:34,570 >> So as hulle agter hul stoel, dit is die sekondêre skikking. 399 00:16:34,570 --> 00:16:36,960 As hulle hier sit, is dit die primêre skikking. 400 00:16:36,960 --> 00:16:40,170 Maar dit is 'n bron wat ons het nie benut tot dusver met borrel 401 00:16:40,170 --> 00:16:42,040 soort, met seleksie soort, met inplaas van aard. 402 00:16:42,040 --> 00:16:44,600 Onthou verlede week, almal net soort skuifel in plek. 403 00:16:44,600 --> 00:16:46,840 Hulle het nie die gebruik van enige addisionele geheue. 404 00:16:46,840 --> 00:16:49,310 Ons het ruimte vir mense deur beweeg mense rond. 405 00:16:49,310 --> 00:16:50,580 >> So, dit is 'n belangrike insig, ook. 406 00:16:50,580 --> 00:16:53,410 Daar is hierdie trade-off, in die algemeen in rekenaarwetenskap, van hulpbronne. 407 00:16:53,410 --> 00:16:55,800 As jy wil te bespoedig iets soos die tyd, gaan jy 408 00:16:55,800 --> 00:16:56,900 het 'n prys te betaal. 409 00:16:56,900 --> 00:17:00,750 En een van die pryse is baie dikwels ruimte, die bedrag van die geheue of hard 410 00:17:00,750 --> 00:17:01,700 spasie op die hardeskyf wat jy gebruik. 411 00:17:01,700 --> 00:17:03,640 Of, eerlik, die bedrag van programmeerder tyd. 412 00:17:03,640 --> 00:17:06,700 Hoeveel tyd wat dit neem om jou, die menslike, om werklik te implementeer 'n paar meer 413 00:17:06,700 --> 00:17:07,829 ingewikkelde algoritme. 414 00:17:07,829 --> 00:17:09,760 Maar vir vandag, die trade-off 'n tyd en ruimte. 415 00:17:09,760 --> 00:17:11,930 >> So as jy ouens kan net hou jou nommers sodat ons kan sien dat jy 416 00:17:11,930 --> 00:17:15,839 inderdaad ooreenstem met 4, 2, 6, 1, 3, 7, 8. 417 00:17:15,839 --> 00:17:16,599 Uitstekend. 418 00:17:16,599 --> 00:17:19,520 So ek gaan om te probeer om te orkestreer dinge, as jy ouens kan net 419 00:17:19,520 --> 00:17:21,800 volg my lei hier. 420 00:17:21,800 --> 00:17:26,650 >> So ek gaan om te implementeer, die eerste, die eerste stap van die pseudokode, wat 421 00:17:26,650 --> 00:17:29,440 op insette van n elemente, as n minder as 2, dan terug. 422 00:17:29,440 --> 00:17:31,370 Dit is duidelik dat, wat nie van toepassing is, sodat ons beweeg aan. 423 00:17:31,370 --> 00:17:33,340 So sorteer die linker helfte van die elemente. 424 00:17:33,340 --> 00:17:36,220 Dus beteken dit dat ek gaan om te fokus my aandag vir 'n oomblik op hierdie 425 00:17:36,220 --> 00:17:37,310 vier ouens hier. 426 00:17:37,310 --> 00:17:39,774 Alle reg, doen wat ek doen? 427 00:17:39,774 --> 00:17:40,570 >> GEHOOR: sorteer die linker helfte. 428 00:17:40,570 --> 00:17:42,780 >> David Malan: So nou het ek te sorteer die linker helfte van hierdie ouens. 429 00:17:42,780 --> 00:17:45,580 Omdat weer, neem vir jouself die doel is om die linker helfte te sorteer. 430 00:17:45,580 --> 00:17:46,440 Hoe doen jy dit? 431 00:17:46,440 --> 00:17:49,140 Volg net die instruksies, selfs maar ons doen dit weer. 432 00:17:49,140 --> 00:17:50,160 So sorteer die linker helfte. 433 00:17:50,160 --> 00:17:52,030 Nou is ek sorteer hierdie twee ouens. 434 00:17:52,030 --> 00:17:53,563 Wat kom volgende? 435 00:17:53,563 --> 00:17:54,510 >> GEHOOR: sorteer die linker helfte. 436 00:17:54,510 --> 00:17:55,460 >> David Malan: sorteer die linker helfte. 437 00:17:55,460 --> 00:18:00,680 So nou hierdie, die setel hier, is 'n lys van die grootte 1. 438 00:18:00,680 --> 00:18:01,365 En wat is jou naam nou weer? 439 00:18:01,365 --> 00:18:02,390 >> PRINCESS DAISY: Princess Daisy. 440 00:18:02,390 --> 00:18:03,690 >> David Malan: Princess Daisy is hier. 441 00:18:03,690 --> 00:18:07,470 En so het sy reeds gesorteer is, omdat die lys is van die grootte 1. 442 00:18:07,470 --> 00:18:09,490 Wat moet ek nou doen nie? 443 00:18:09,490 --> 00:18:13,680 OK, terug te keer nie, want die lys is van grootte 1, wat minder is as 2. 444 00:18:13,680 --> 00:18:14,320 Dan wat is die volgende stap? 445 00:18:14,320 --> 00:18:17,490 En nou moet jy soort backtracks in jou gedagtes. 446 00:18:17,490 --> 00:18:19,340 >> Sorteer die regter helfte, wat - 447 00:18:19,340 --> 00:18:19,570 Wat is jou naam? 448 00:18:19,570 --> 00:18:20,220 >> LINDA: Linda. 449 00:18:20,220 --> 00:18:20,980 >> David Malan: Linda. 450 00:18:20,980 --> 00:18:23,210 En so wat doen ons nou dat Ons het 'n lys van die grootte 1? 451 00:18:23,210 --> 00:18:24,440 >> GEHOOR: Terug. 452 00:18:24,440 --> 00:18:24,760 >> David Malan: versigtig wees. 453 00:18:24,760 --> 00:18:29,540 Ons keer terug eerste, en nou is die derde stap - en as ek soort van beeld dit deur 454 00:18:29,540 --> 00:18:33,490 die aanvaarding van die twee sitplekke nou, nou is ek het hierdie twee elemente saam te voeg. 455 00:18:33,490 --> 00:18:35,530 So nou ongelukkig die elemente buite werking is. 456 00:18:35,530 --> 00:18:39,920 Maar dit is waar die samesmelting proses begin om dwingende. 457 00:18:39,920 --> 00:18:42,410 >> So as jy ouens kan opstaan ​​vir net 'n oomblik, ek gaan jou nodig het, in 'n 458 00:18:42,410 --> 00:18:44,170 oomblik te stap agter jou stoel. 459 00:18:44,170 --> 00:18:46,480 En as Linda, want 2 is kleiner as 4 is, hoekom dit nie doen nie 460 00:18:46,480 --> 00:18:48,130 jy kom om eerste? 461 00:18:48,130 --> 00:18:48,690 Daar bly. 462 00:18:48,690 --> 00:18:50,520 So Linda, jy kom om die eerste. 463 00:18:50,520 --> 00:18:53,820 >> Nou in werklikheid is dit net 'n skikking Ons kan net beweeg haar in reële tyd 464 00:18:53,820 --> 00:18:55,360 uit hierdie stoel by hierdie plek. 465 00:18:55,360 --> 00:18:57,770 So dink wat het 'n paar konstante aantal stappe 1. 466 00:18:57,770 --> 00:18:58,480 En nou - 467 00:18:58,480 --> 00:19:01,490 maar ons het jou nodig om te sit in die eerste plek hier. 468 00:19:01,490 --> 00:19:03,930 >> En nou as jy kon kom rond, sowel, gaan ons 469 00:19:03,930 --> 00:19:06,300 wees in plek twee. 470 00:19:06,300 --> 00:19:09,120 En selfs al is dit voel soos dit is neem 'n rukkie, wat is nice is nou 471 00:19:09,120 --> 00:19:14,710 dat die linker helfte van die linker helfte is nou gesorteer. 472 00:19:14,710 --> 00:19:18,010 So wat was die volgende stap, as ons nou rewind verder in die storie? 473 00:19:18,010 --> 00:19:18,980 >> GEHOOR: Right helfte. 474 00:19:18,980 --> 00:19:19,900 >> David Malan: sorteer die reg om die helfte. 475 00:19:19,900 --> 00:19:21,320 So julle ouens het dit te doen, as well. 476 00:19:21,320 --> 00:19:23,510 So as jy kan opstaan net vir 'n oomblik? 477 00:19:23,510 --> 00:19:25,192 En wat is jou naam? 478 00:19:25,192 --> 00:19:25,540 >> JESS: Jess. 479 00:19:25,540 --> 00:19:25,870 >> David Malan: Jess. 480 00:19:25,870 --> 00:19:29,720 OK, so Jess is nou die linker helfte van die reg om die helfte. 481 00:19:29,720 --> 00:19:31,400 En so sy is 'n lys van die grootte 1. 482 00:19:31,400 --> 00:19:32,380 Sy is natuurlik gesorteer. 483 00:19:32,380 --> 00:19:33,070 En jou naam nou weer? 484 00:19:33,070 --> 00:19:33,630 >> MICHELLE: Michelle. 485 00:19:33,630 --> 00:19:35,340 >> David Malan: Michelle is natuurlik 'n lys van die grootte 1. 486 00:19:35,340 --> 00:19:36,050 Sy is reeds uitgesorteer. 487 00:19:36,050 --> 00:19:38,690 So nou is die magic gebeur, die samesmelting proses. 488 00:19:38,690 --> 00:19:39,790 So wie gaan eerste kom? 489 00:19:39,790 --> 00:19:41,560 Dit is duidelik dat Michelle. 490 00:19:41,560 --> 00:19:43,280 So as jy kan kom om terug te. 491 00:19:43,280 --> 00:19:47,090 Die ruimte wat ons beskikbaar het nou vir haar is reg agter die stoel hier. 492 00:19:47,090 --> 00:19:51,580 En nou as jy kan terug kom so goed, ons het nou, duidelik te wees, twee 493 00:19:51,580 --> 00:19:53,810 helftes, elk van grootte 2 - 494 00:19:53,810 --> 00:19:57,090 en net vir die uitbeelding se ontwil, as jy kan 'n bietjie van 'n ruimte - 495 00:19:57,090 --> 00:19:59,780 een links half hier, die een reg half hier. 496 00:19:59,780 --> 00:20:01,160 >> Rewind verder in die storie. 497 00:20:01,160 --> 00:20:02,270 Wat stap is volgende? 498 00:20:02,270 --> 00:20:03,030 >> Gehoor deur saam te smelt. 499 00:20:03,030 --> 00:20:04,160 >> David Malan: So nou het ons om saam te smelt. 500 00:20:04,160 --> 00:20:07,490 So OK, so nou, gelukkig, ons net bevry vier stoele. 501 00:20:07,490 --> 00:20:11,480 So het ons twee keer gebruik soveel geheue, maar ons kan flip-uittrek gee tussen 502 00:20:11,480 --> 00:20:12,330 Die twee skikkings. 503 00:20:12,330 --> 00:20:14,190 So watter getal is om eerste te kom? 504 00:20:14,190 --> 00:20:14,850 So Michelle, natuurlik. 505 00:20:14,850 --> 00:20:16,680 So kom rond en neem jou plek hier. 506 00:20:16,680 --> 00:20:19,120 En dan is nommer 2 is natuurlik volgende, so jy hier kom. 507 00:20:19,120 --> 00:20:21,520 Nommer 4, nommer 6. 508 00:20:21,520 --> 00:20:23,390 En weer, selfs al is daar 'n bietjie van die loop betrokke is, 509 00:20:23,390 --> 00:20:26,010 regtig, kan hierdie onmiddellik gebeur nie, deur die beweging van een - 510 00:20:26,010 --> 00:20:26,880 OK, goed gespeel. 511 00:20:26,880 --> 00:20:28,350 >> [Gelag] 512 00:20:28,350 --> 00:20:29,680 >> David Malan: En nou is ons in redelik goeie vorm. 513 00:20:29,680 --> 00:20:34,910 Die linker helfte van die hele insette is nou gesorteer. 514 00:20:34,910 --> 00:20:37,370 Alle reg, sodat hierdie ouens gehad die voordeel van my - 515 00:20:37,370 --> 00:20:40,340 hoe het dit uiteindelik al die meisies op die links en al die seuns van die reg? 516 00:20:40,340 --> 00:20:42,450 >> OK, so ouens "Nou draai. 517 00:20:42,450 --> 00:20:44,680 So ek sal nie loop jy deur hierdie stappe. 518 00:20:44,680 --> 00:20:46,550 Ons sal kyk of ons kan weer aansoek doen dieselfde pseudokode. 519 00:20:46,550 --> 00:20:50,050 As jy wil om voort te gaan en te staan, en julle, laat my gee u die mic. 520 00:20:50,050 --> 00:20:52,990 Sien as jy nie kan herhaal wat Ons het net hier op die 521 00:20:52,990 --> 00:20:53,880 ander einde van die lys. 522 00:20:53,880 --> 00:20:59,530 Wie het dit nodig om eerste te praat, gebaseer op die algoritme? 523 00:20:59,530 --> 00:21:03,210 So verduidelik wat jy doen voordat jy maak 'n voet bewegings. 524 00:21:03,210 --> 00:21:05,930 >> Spreker 1: Alle reg, so sedert Ek is die linker helfte van die 525 00:21:05,930 --> 00:21:07,790 linker helfte, het ek terug. 526 00:21:07,790 --> 00:21:08,730 Reg? 527 00:21:08,730 --> 00:21:09,250 >> David Malan: Goed. 528 00:21:09,250 --> 00:21:10,350 >> Spreker 1: En dan - 529 00:21:10,350 --> 00:21:11,800 >> David Malan: Wie doen die mikrofoon gaan na die volgende? 530 00:21:11,800 --> 00:21:12,920 >> Spreker 1: Volgende nommer. 531 00:21:12,920 --> 00:21:14,720 >> Spreker 2: So ek is die regter helfte van die linker helfte van die 532 00:21:14,720 --> 00:21:17,830 linker helfte, en ek terugkeer. 533 00:21:17,830 --> 00:21:18,050 >> David Malan: Goed. 534 00:21:18,050 --> 00:21:18,550 Jy terugkeer. 535 00:21:18,550 --> 00:21:21,855 So nou wat is die volgende vir julle twee? 536 00:21:21,855 --> 00:21:23,740 >> Spreker 2: Ons wil sien wie is kleiner. 537 00:21:23,740 --> 00:21:24,200 >> David Malan: Presies. 538 00:21:24,200 --> 00:21:24,940 Ons wil hê om saam te smelt. 539 00:21:24,940 --> 00:21:27,590 Die ruimte wat ons gaan gebruik om saam te smelt julle in, selfs al is hulle 540 00:21:27,590 --> 00:21:30,250 natuurlik gesorteer reeds, ons gaan dieselfde algoritme te volg. 541 00:21:30,250 --> 00:21:31,560 So wat gaan in die rug eerste? 542 00:21:31,560 --> 00:21:35,720 So 3, en dan 7. 543 00:21:35,720 --> 00:21:38,570 En nou het die mic gaan om hierdie ouens, OK? 544 00:21:38,570 --> 00:21:43,590 >> SPREKER 3: So ek is die regter helfte van die linker helfte, en my n minder is as 545 00:21:43,590 --> 00:21:45,048 1, so ek gaan net om te slaag - 546 00:21:45,048 --> 00:21:46,380 >> David Malan: Goed. 547 00:21:46,380 --> 00:21:49,450 >> SPREKER 4: Ek is die reg om die helfte van die regter helfte van die reg om die helfte, en ek is 548 00:21:49,450 --> 00:21:51,740 ook een persoon, so ek is gaan om terug te keer. 549 00:21:51,740 --> 00:21:52,990 So nou het ons saam te smelt. 550 00:21:52,990 --> 00:21:55,140 551 00:21:55,140 --> 00:21:56,150 >> SPREKER 3: So gaan ons terug. 552 00:21:56,150 --> 00:21:57,160 >> David Malan: So jy gaan in die rug. 553 00:21:57,160 --> 00:21:59,200 So 5 gaan die eerste, dan 8. 554 00:21:59,200 --> 00:22:01,240 En nou het gehoor, wat is die stap ons nou rewind 555 00:22:01,240 --> 00:22:02,200 terug in ons gedagtes? 556 00:22:02,200 --> 00:22:02,940 >> Gehoor deur saam te smelt. 557 00:22:02,940 --> 00:22:07,270 >> David Malan: Kombineer linker helfte en regs helfte van die oorspronklike linker helfte. 558 00:22:07,270 --> 00:22:08,840 So nou - 559 00:22:08,840 --> 00:22:10,520 en net om dit duidelik maak, 'n bietjie van die ruimte 560 00:22:10,520 --> 00:22:11,690 tussen julle twee ouens. 561 00:22:11,690 --> 00:22:13,800 So nou is dit die twee lyste links en regs. 562 00:22:13,800 --> 00:22:18,320 So hoe ons saam te smelt nou nie julle ouens in die voorste ry sitplekke weer? 563 00:22:18,320 --> 00:22:19,600 >> 3 gaan eerste. 564 00:22:19,600 --> 00:22:20,850 Dan 5, natuurlik. 565 00:22:20,850 --> 00:22:23,110 566 00:22:23,110 --> 00:22:27,330 Dan 7, en nou 8. 567 00:22:27,330 --> 00:22:28,710 OK, en nou is ons? 568 00:22:28,710 --> 00:22:29,650 >> Publiek: nie gedoen nie. 569 00:22:29,650 --> 00:22:32,440 >> David Malan: Nie gedoen nie, want natuurlik, daar is 'n stap in die jaar. 570 00:22:32,440 --> 00:22:35,720 Maar weereens, die rede waarom ek die gebruik van hierdie jargon soos "rewind in jou gedagtes," 571 00:22:35,720 --> 00:22:37,160 dit is omdat dit is regtig wat gebeur. 572 00:22:37,160 --> 00:22:39,610 Ons gaan deur al hierdie stappe maar ons is soort van pousering vir 'n 573 00:22:39,610 --> 00:22:42,480 oomblik, duik dieper in die algoritme, pousering vir 'n oomblik, 574 00:22:42,480 --> 00:22:45,840 duik dieper in die algoritme, en nou het ons te sorteer van rewind in ons 575 00:22:45,840 --> 00:22:49,430 gedagtes en ongedaan te maak al hierdie lae dat ons het soort van op te hou. 576 00:22:49,430 --> 00:22:51,790 >> So nou het ons twee lyste van grootte 4. 577 00:22:51,790 --> 00:22:54,790 As jy ouens kan staan ​​vir oulaas en maak 'n bietjie van die ruimte hier te 578 00:22:54,790 --> 00:22:57,230 duidelik maak dat dit die linker helfte van die oorspronklike, die 579 00:22:57,230 --> 00:22:58,620 regter helfte van die oorspronklike. 580 00:22:58,620 --> 00:23:01,060 Wie is die eerste getal wat ons nodig het om te trek in die rug? 581 00:23:01,060 --> 00:23:01,870 Michelle, natuurlik. 582 00:23:01,870 --> 00:23:03,230 >> So sit ons Michelle hier. 583 00:23:03,230 --> 00:23:05,080 En wie het nommer 2? 584 00:23:05,080 --> 00:23:06,440 Nommer 2 kom op die rug as well. 585 00:23:06,440 --> 00:23:07,800 Nommer 3? 586 00:23:07,800 --> 00:23:08,510 Uitstekend. 587 00:23:08,510 --> 00:23:16,570 Nommer 4, nommer 5, nommer 6, nommer 7, en die getal 8. 588 00:23:16,570 --> 00:23:18,850 >> OK, so dit voel soos 'n baie stappe, vir seker. 589 00:23:18,850 --> 00:23:22,390 Maar laat ons kyk of ons kan dit nie bevestig soort van intuïtief dat hierdie 590 00:23:22,390 --> 00:23:26,190 algoritme fundamenteel, veral as n regtig groot, soos ons gesien het 591 00:23:26,190 --> 00:23:29,170 met die animasies, is fundamenteel vinniger. 592 00:23:29,170 --> 00:23:33,400 So ek beweer hierdie algoritme, in die ergste geval en selfs in die beste geval, 593 00:23:33,400 --> 00:23:36,160 is 'n groot O van n keer log n. 594 00:23:36,160 --> 00:23:39,160 Dit is, daar is 'n aspek van hierdie algoritme wat neem n stappe, maar 595 00:23:39,160 --> 00:23:43,110 daar is 'n ander aspek iewers in dat iterasie, wat herhaling, wat 596 00:23:43,110 --> 00:23:44,410 neem log n stappe. 597 00:23:44,410 --> 00:23:49,154 Kan ons ons vinger op wat daardie twee getalle word verwys na? 598 00:23:49,154 --> 00:23:51,320 Wel, waar - 599 00:23:51,320 --> 00:23:54,160 Waar kom die mikrofoon gaan? 600 00:23:54,160 --> 00:23:58,660 >> Spreker 1: Sou die teken wees n breek ons ​​in twee - 601 00:23:58,660 --> 00:23:59,630 deel deur twee, in wese. 602 00:23:59,630 --> 00:24:00,120 >> David Malan: Presies. 603 00:24:00,120 --> 00:24:03,000 Enige tyd wat ons sien in 'n algoritme dus ver, is daar 'hierdie patroon van 604 00:24:03,000 --> 00:24:04,200 verdeel, verdeel, te verdeel. 605 00:24:04,200 --> 00:24:05,700 En dit is tipies verminder na iets wat 606 00:24:05,700 --> 00:24:07,100 logaritmiese, log basis 2. 607 00:24:07,100 --> 00:24:10,180 Maar dit kan regtig enigiets, maar teken basis 2. 608 00:24:10,180 --> 00:24:11,330 >> Nou wat van die n? 609 00:24:11,330 --> 00:24:14,550 Ek kan sien dat ons soort van verdeel jy ouens - verdeel jou, verdeel jy, 610 00:24:14,550 --> 00:24:15,910 verdeel jy gedeel het. 611 00:24:15,910 --> 00:24:18,760 Waar kom die einde kom? 612 00:24:18,760 --> 00:24:19,810 >> So dit is die samesmelting. 613 00:24:19,810 --> 00:24:20,610 Want daaroor dink. 614 00:24:20,610 --> 00:24:25,420 Wanneer jy voeg agt mense bymekaar, waardeur die helfte van hulle is 'n stel van vier 615 00:24:25,420 --> 00:24:27,770 en die ander helfte is 'n ander stel van vier, hoe kan jy gaan 616 00:24:27,770 --> 00:24:28,820 oor die doen van die samesmelting? 617 00:24:28,820 --> 00:24:30,830 Wel, julle het dit redelik intuïtief. 618 00:24:30,830 --> 00:24:34,140 >> Maar as ek in plaas daarvan het dit 'n bietjie meer metodies, kan ek uitgewys het op 619 00:24:34,140 --> 00:24:38,090 die linker persoon eers met my linkerhand hand, wys na die linker persoon 620 00:24:38,090 --> 00:24:42,080 van dat die helfte met my regterhand, en net daarna het, deur die 621 00:24:42,080 --> 00:24:46,990 lys, wat dui op die kleinste element elke keer, beweeg my vinger oor en 622 00:24:46,990 --> 00:24:48,970 meer as wat nodig is deur die lys. 623 00:24:48,970 --> 00:24:51,890 Maar wat is die sleutel oor hierdie samesmelting proses is ek hierdie pare is vergelyk 624 00:24:51,890 --> 00:24:53,460 van elemente. 625 00:24:53,460 --> 00:24:57,270 Van die regter helfte en van links half, ek het nooit een keer back tracking. 626 00:24:57,270 --> 00:25:00,570 >> So het die samesmelting self neem nie meer as n stappe. 627 00:25:00,570 --> 00:25:03,250 En hoeveel keer het ek om dit te doen samesmelting? 628 00:25:03,250 --> 00:25:07,150 Wel, nie meer as n, en ons het net sien dat met die finale saamsmelt. 629 00:25:07,150 --> 00:25:13,120 En so, as jy iets doen wat neem teken n stappe n keer, of andersom, 630 00:25:13,120 --> 00:25:15,210 dit gaan om te gee ons n keer log n. 631 00:25:15,210 --> 00:25:16,310 >> En hoekom is dit beter? 632 00:25:16,310 --> 00:25:19,600 Wel, as ons reeds weet dat log n is beter as n - reg? 633 00:25:19,600 --> 00:25:22,590 Ons het in binêre soek, die telefoon boek Byvoorbeeld, log n was beslis 634 00:25:22,590 --> 00:25:23,760 beter as lineêre. 635 00:25:23,760 --> 00:25:28,420 Dus beteken dit dat n keer log n is beslis beter as n keer 'n ander 636 00:25:28,420 --> 00:25:30,390 n, AKA n vierkant. 637 00:25:30,390 --> 00:25:32,400 En dit is wat ons uiteindelik voel. 638 00:25:32,400 --> 00:25:34,928 >> So groot applous, indien ons kon nie, want hierdie ouens. 639 00:25:34,928 --> 00:25:38,920 >> [Applous] 640 00:25:38,920 --> 00:25:41,550 >> David Malan, en julle afskeid geskenke - jy mag die getalle, 641 00:25:41,550 --> 00:25:44,010 as jy wil. 642 00:25:44,010 --> 00:25:45,620 En jou afskeidsgeskenk, soos gewoonlik. 643 00:25:45,620 --> 00:25:47,290 O ja, en ons sal jou die beeldmateriaal, Michelle. 644 00:25:47,290 --> 00:25:48,343 Dankie. 645 00:25:48,343 --> 00:25:49,250 Alle regte. 646 00:25:49,250 --> 00:25:50,400 Help jouself om 'n stress bal. 647 00:25:50,400 --> 00:25:54,110 >> En laat my trek, in die tussentyd, ons vriend Rob Bowden aan te bied 648 00:25:54,110 --> 00:25:59,520 ietwat ander perspektief op hierdie, want jy kan dink oor hierdie 649 00:25:59,520 --> 00:26:01,280 stappe gebeur in 'n ietwat ander manier. 650 00:26:01,280 --> 00:26:04,750 Trouens, die set-up vir dit wat Rob is oor om ons te wys aanvaar dat ons 651 00:26:04,750 --> 00:26:09,030 reeds gedoen het die verdeling van die groot lys in agt klein lyste, 652 00:26:09,030 --> 00:26:10,570 elk van grootte 1. 653 00:26:10,570 --> 00:26:13,350 >> So ons is besig om die pseudokode 'n bietjie net om te sorteer van kry by die 654 00:26:13,350 --> 00:26:15,320 kern idee van hoe die samesmelting van werke. 655 00:26:15,320 --> 00:26:17,600 Maar die loop van die tyd wat hy is om te doen, is nog steeds 656 00:26:17,600 --> 00:26:19,110 gaan dieselfde wees. 657 00:26:19,110 --> 00:26:23,540 En weer, die set-up hier is dat hy begin met agt lyste van grootte 1. 658 00:26:23,540 --> 00:26:27,730 So jy het gemis die deel waar hy is eintlik gedoen die puntelys n, log n, log n 659 00:26:27,730 --> 00:26:31,205 verdeling van die insette. 660 00:26:31,205 --> 00:26:32,120 >> [Video speel] 661 00:26:32,120 --> 00:26:33,615 >> -Dit is dit vir stap een. 662 00:26:33,615 --> 00:26:38,270 Vir stap twee, herhaaldelik saamsmelt pare lyste. 663 00:26:38,270 --> 00:26:39,210 >> David Malan: Hm. 664 00:26:39,210 --> 00:26:41,270 Slegs klank kom uit my rekenaar. 665 00:26:41,270 --> 00:26:42,520 Kom ons probeer dit weer. 666 00:26:42,520 --> 00:26:45,330 667 00:26:45,330 --> 00:26:48,310 >> -Net arbitrêr kies wat - Nou het ons vier lyste. 668 00:26:48,310 --> 00:26:51,590 669 00:26:51,590 --> 00:26:52,120 Leer voor. 670 00:26:52,120 --> 00:26:53,040 >> David Malan: Daar gaan ons. 671 00:26:53,040 --> 00:27:00,510 >> -Kombineer 108 en 15, het ons uiteindelik met die lys 15, 108. 672 00:27:00,510 --> 00:27:07,170 Samesmelting 50 en 4, wat ons eindig met 4, 50. 673 00:27:07,170 --> 00:27:12,990 Samesmelting 8 en 42, het ons eindig met 8, 42. 674 00:27:12,990 --> 00:27:19,970 En die samesmelting van 23 en 16, het ons eindig met 16, 23. 675 00:27:19,970 --> 00:27:23,270 >> Nou al ons lyste van grootte 2. 676 00:27:23,270 --> 00:27:26,690 Let daarop dat elk van die vier lyste gesorteer is. 677 00:27:26,690 --> 00:27:29,450 Sodat ons kan begin samesmelting pare lyste weer. 678 00:27:29,450 --> 00:27:38,420 Samesmelting 15 en 108 en 4 en 50, het ons eers die 4, dan is die 15, dan 679 00:27:38,420 --> 00:27:41,500 die 50, dan is die 108. 680 00:27:41,500 --> 00:27:50,610 Samesmelting 8, 42 en 16, 23, het ons vir die eerste maal die 8, dan is die 16, dan is die 23, 681 00:27:50,610 --> 00:27:52,700 dan is die 42. 682 00:27:52,700 --> 00:27:57,600 >> So nou het ons net twee lyste van grootte 4, is elk van wat gesorteer. 683 00:27:57,600 --> 00:28:01,170 So nou het ons saam te smelt die twee lyste. 684 00:28:01,170 --> 00:28:11,835 Eerstens, neem ons die 4, dan neem ons die 8, dan neem ons die 15, dan 16, dan 685 00:28:11,835 --> 00:28:19,456 23, dan 42, dan 50, dan 108. 686 00:28:19,456 --> 00:28:19,872 >> [Einde video-vertoning] 687 00:28:19,872 --> 00:28:23,430 >> David Malan: Weereens, kennisgewing, het hy nooit raak 'n gegewe koppie meer as een keer 688 00:28:23,430 --> 00:28:24,860 na die bevordering van buite dit. 689 00:28:24,860 --> 00:28:26,200 So het hy nog nooit herhaal. 690 00:28:26,200 --> 00:28:29,850 So hy is altyd beweeg aan die kant, en dit is waar ons ons n. 691 00:28:29,850 --> 00:28:33,290 >> Waarom nie laat my trek een animasie dat ons vroeër gesien het, maar hierdie keer 692 00:28:33,290 --> 00:28:35,110 fokus net op saamsmelt soort. 693 00:28:35,110 --> 00:28:38,030 Laat my gaan voort en vergroot op hierdie hier. 694 00:28:38,030 --> 00:28:42,530 Eerste laat my kies 'n ewekansige insette, vergroot dit, en jy kan sorteer sien 695 00:28:42,530 --> 00:28:46,600 wat ons as vanselfsprekend aanvaar het, Vroeër, saam te smelt soort is eintlik doen. 696 00:28:46,600 --> 00:28:50,330 >> So sien dat jy hierdie helftes of hierdie oorde of hierdie agstes van die 697 00:28:50,330 --> 00:28:53,140 probleem wat al van 'n skielike begin 'n goeie vorm te neem. 698 00:28:53,140 --> 00:28:57,070 En dan uiteindelik, wat jy sien by die einde wat bam, 699 00:28:57,070 --> 00:28:58,860 alles saam saamgesmelt. 700 00:28:58,860 --> 00:29:01,690 >> So dit is net drie verskillende neem op dieselfde idee. 701 00:29:01,690 --> 00:29:05,980 Maar die sleutel insig, net soos kloof en verower in die heel eerste klas, 702 00:29:05,980 --> 00:29:10,640 was dat ons besluit het om een ​​of ander manier verdeel die probleem in iets groot, in 703 00:29:10,640 --> 00:29:14,760 iets soort van identiese in gees, maar kleiner en kleiner 704 00:29:14,760 --> 00:29:15,660 en kleiner. 705 00:29:15,660 --> 00:29:18,420 >> Nou 'n ander prettige manier om uit te sorteer dink hieroor, selfs al is dit nie 706 00:29:18,420 --> 00:29:20,520 gaan vir jou dieselfde intuïtief begrip, is 707 00:29:20,520 --> 00:29:21,640 die volgende animasie. 708 00:29:21,640 --> 00:29:25,400 So dit is 'n video iemand saam te stel wat verband hou verskillende 709 00:29:25,400 --> 00:29:29,970 klanke met die verskillende bedrywighede vir voeg soort, vir saamsmelt soort, en 710 00:29:29,970 --> 00:29:31,150 vir 'n paar van die ander. 711 00:29:31,150 --> 00:29:32,330 So in 'n oomblik, ek gaan speel om te tref. 712 00:29:32,330 --> 00:29:33,600 Dit gaan oor 'n minuut lank. 713 00:29:33,600 --> 00:29:37,410 En selfs al is jy kan nog steeds die patrone gebeur, hierdie tyd wat jy kan 714 00:29:37,410 --> 00:29:41,420 ook hoor hoe hierdie algoritmes uitvoering anders en met 715 00:29:41,420 --> 00:29:43,950 ietwat verskillende patrone. 716 00:29:43,950 --> 00:29:45,830 >> Dit is te voeg soort. 717 00:29:45,830 --> 00:29:50,400 >> [Toon SPEEL] 718 00:29:50,400 --> 00:29:52,400 >> David Malan: Dit is weer probeer elke element te voeg 719 00:29:52,400 --> 00:29:52,900 in waar dit hoort. 720 00:29:52,900 --> 00:29:54,628 Dit is borrel soort. 721 00:29:54,628 --> 00:30:10,097 >> [Toon SPEEL] 722 00:30:10,097 --> 00:30:13,630 >> David Malan: En jy kan soort van gevoel hoe relatief min werk dit doen 723 00:30:13,630 --> 00:30:15,834 op elke stap. 724 00:30:15,834 --> 00:30:20,470 Dit is wat die eentonigheid klink. 725 00:30:20,470 --> 00:30:21,472 >> [Toon SPEEL] 726 00:30:21,472 --> 00:30:25,222 >> David Malan: Dit is seleksie soort, waar ons kies die element wat ons wil deur 727 00:30:25,222 --> 00:30:28,845 gaan deur weer en weer en weer en sit dit aan die begin. 728 00:30:28,845 --> 00:30:37,674 >> [Toon SPEEL] 729 00:30:37,674 --> 00:30:43,970 >> David Malan: Dit is saamsmelt soort, wat kan jy regtig begin om te voel. 730 00:30:43,970 --> 00:30:51,810 >> [Toon SPEEL] 731 00:30:51,810 --> 00:30:54,770 >> [Gelag] 732 00:30:54,770 --> 00:30:58,395 >> David Malan: Iets wat genoem gnome soort, wat ons nog nie gekyk het nie. 733 00:30:58,395 --> 00:31:13,630 >> [Toon SPEEL] 734 00:31:13,630 --> 00:31:17,910 >> David Malan: So laat ek sien, nou, afgelei as jy hopelik is deur die 735 00:31:17,910 --> 00:31:21,110 musiek, as ek 'n bietjie kan glip bietjie van wiskunde in hier. 736 00:31:21,110 --> 00:31:24,850 So is daar 'n vierde manier wat ons kan dink oor wat dit beteken om hierdie 737 00:31:24,850 --> 00:31:29,210 funksies om vinniger as kinders wees dat ons nog nooit gesien. 738 00:31:29,210 --> 00:31:32,470 En as jy kom by die kursus uit 'n wiskunde-agtergrond, wat jy 739 00:31:32,470 --> 00:31:36,030 eintlik miskien reeds weet dat jy kan 'n term wat klap op hierdie tegniek - 740 00:31:36,030 --> 00:31:40,400 naamlik rekursie, 'n funksie wat doen 'n beroep op 'n manier self. 741 00:31:40,400 --> 00:31:44,780 >> En weer, onthou dat saamsmelt soort pseudokode was rekursiewe in die sin 742 00:31:44,780 --> 00:31:48,460 dat een van saamsmelt soort se stappe was soort te noem - 743 00:31:48,460 --> 00:31:49,740 dit is, is self. 744 00:31:49,740 --> 00:31:52,480 Maar gelukkig, want ons het roep soort, of saam te smelt soort, 745 00:31:52,480 --> 00:31:55,880 spesifiek, op 'n kleiner en kleiner en kleiner lys, het ons uiteindelik 746 00:31:55,880 --> 00:32:00,005 onderste draaipunt bereik het danksy wat ons bel 'n basis geval, die hard-gekodeerde geval dat 747 00:32:00,005 --> 00:32:04,270 het gesê dat indien die lys is 'n klein, minder as 2 In daardie geval, net dadelik terug te keer. 748 00:32:04,270 --> 00:32:07,550 As ons nie gehad het dat die spesiale geval, die algoritme sou nooit onder uit, 749 00:32:07,550 --> 00:32:11,010 en jy sal wel kry in 'n oneindige lus werklik vir ewig. 750 00:32:11,010 --> 00:32:14,330 >> Maar veronderstel dat ons wou nou sit 'n paar nommers op hierdie, weer, met behulp van n 751 00:32:14,330 --> 00:32:15,660 as die grootte van die insette. 752 00:32:15,660 --> 00:32:18,680 En ek wou jou vra, wat is die totale tyd wat betrokke is in 753 00:32:18,680 --> 00:32:19,800 hardloop saamsmelt soort? 754 00:32:19,800 --> 00:32:22,960 Of meer in die algemeen, wat is die koste van dit in die tyd? 755 00:32:22,960 --> 00:32:24,730 >> Wel, dit is redelik maklik om dit te meet. 756 00:32:24,730 --> 00:32:29,010 As n is minder as 2, die tyd wat betrokke is in sortering n elemente, 757 00:32:29,010 --> 00:32:30,480 waar n 2, is 0. 758 00:32:30,480 --> 00:32:31,410 Omdat ons net terug te keer. 759 00:32:31,410 --> 00:32:32,510 Daar is geen werk wat gedoen moet word. 760 00:32:32,510 --> 00:32:35,660 Nou waarskynlik, miskien is dit 'n stap of twee stappe om uit te vind die bedrag van 761 00:32:35,660 --> 00:32:38,420 werk nie, maar dit is naby genoeg aan 0 wat Ek is net gaan om te sê geen werk is 762 00:32:38,420 --> 00:32:40,940 vereis indien die lys is so klein word oninteressant. 763 00:32:40,940 --> 00:32:42,580 >> Maar hierdie geval is interessant. 764 00:32:42,580 --> 00:32:47,320 Die rekursiewe geval was die tak van die pseudokode wat sê anders, soort 765 00:32:47,320 --> 00:32:52,000 die linker helfte, sorteer die regte helfte, saam te smelt die twee helftes. 766 00:32:52,000 --> 00:32:55,530 Nou hoekom het hierdie uitdrukking stel dat die koste? 767 00:32:55,530 --> 00:32:58,690 Wel, T van n beteken net die tyd n elemente uit te sorteer. 768 00:32:58,690 --> 00:33:03,070 En dan op die regterkant van die gelyk teken is, is die T van n verdeelde 769 00:33:03,070 --> 00:33:06,600 deur 2 verwys na die koste van wat? 770 00:33:06,600 --> 00:33:07,570 Sorteer die linker helfte. 771 00:33:07,570 --> 00:33:10,990 Die ander T van n gedeel deur 2 is vermoedelik verwys na die koste te 772 00:33:10,990 --> 00:33:12,390 sorteer die reg om die helfte. 773 00:33:12,390 --> 00:33:14,590 >> En dan is die plus n? 774 00:33:14,590 --> 00:33:15,420 Is die samesmelting. 775 00:33:15,420 --> 00:33:19,120 Want as jy twee lyste, een van grootte n meer as 2 en 'n ander van grootte n 776 00:33:19,120 --> 00:33:22,580 meer as 2, wat jy hoef te raak in wese elk van die elemente, net soos Rob 777 00:33:22,580 --> 00:33:24,990 aangeraak elk van die koppies, en net Soos ons by elk van die 778 00:33:24,990 --> 00:33:26,310 vrywilligers op die verhoog. 779 00:33:26,310 --> 00:33:28,790 So n is die koste van die samesmelting. 780 00:33:28,790 --> 00:33:31,780 >> Nou ongelukkig, hierdie formule is ook self rekursiewe. 781 00:33:31,780 --> 00:33:36,390 So as die vraag gevra het, vir n ', sê, 16, indien daar is 16 mense op die verhoog 782 00:33:36,390 --> 00:33:40,670 of 16 koppies in die video, hoeveel totale stappe neem dit om hulle te sorteer 783 00:33:40,670 --> 00:33:41,550 met saamsmelt soort? 784 00:33:41,550 --> 00:33:45,790 Dit is eintlik nie 'n duidelike antwoord, want nou het jy te sorteer 785 00:33:45,790 --> 00:33:48,500 rekursief beantwoord hierdie formule. 786 00:33:48,500 --> 00:33:51,190 >> Maar dis OK, want laat my stel dat ons die volgende doen. 787 00:33:51,190 --> 00:33:56,670 Die tyd wat betrokke is 16 mense uit te sorteer of 16 koppies gaan word verteenwoordig 788 00:33:56,670 --> 00:33:58,020 algemeen as T van 16. 789 00:33:58,020 --> 00:34:01,400 Maar dit is gelyk aan, volgens ons vorige formule, 2 keer die bedrag 790 00:34:01,400 --> 00:34:04,780 van die tyd wat dit neem om te sorteer 8 koppies plus 16. 791 00:34:04,780 --> 00:34:08,590 En weer, plus 16 is die tyd om saam te smelt, en die twee keer T van 8 is die 792 00:34:08,590 --> 00:34:10,790 tyd links en regs helfte helfte te sorteer. 793 00:34:10,790 --> 00:34:11,989 >> Maar weereens, dit is nie genoeg nie. 794 00:34:11,989 --> 00:34:13,210 Ons het om te duik in dieper. 795 00:34:13,210 --> 00:34:16,409 Dit beteken dat ons die antwoord vraag, wat is T van 8? 796 00:34:16,409 --> 00:34:19,610 Wel T van 8 is net 2 tye T van 4 plus 8. 797 00:34:19,610 --> 00:34:20,520 Wel, wat is T van 4? 798 00:34:20,520 --> 00:34:23,780 T van 4 is net 2 keer T van 2 plus 4. 799 00:34:23,780 --> 00:34:25,489 Wel, wat is T van 2? 800 00:34:25,489 --> 00:34:29,030 T van 2 is net 2 keer T van 1 en 2. 801 00:34:29,030 --> 00:34:31,940 >> En weer, ons is soort van kry vas in hierdie siklus. 802 00:34:31,940 --> 00:34:34,790 Maar dit is oor te slaan wat sogenaamde basis geval. 803 00:34:34,790 --> 00:34:37,310 Want wat is T van 1, het ons beweer? 804 00:34:37,310 --> 00:34:37,810 0. 805 00:34:37,810 --> 00:34:39,730 So nou uiteindelik, kan ons terug werk. 806 00:34:39,730 --> 00:34:44,290 >> As T van 1 is 0, kan ek nou gaan terug tot een lyn na hierdie man hier, en ek kan 807 00:34:44,290 --> 00:34:46,330 plug in 0 vir T van 1. 808 00:34:46,330 --> 00:34:51,770 So dit beteken dat dit gelyk is aan 2 keer nul, andersins bekend as 0, plus 2. 809 00:34:51,770 --> 00:34:53,739 En so dat die hele uitdrukking is 2. 810 00:34:53,739 --> 00:34:58,740 >> Nou as ek die T van 2, wie se antwoord is 2, prop dit in die middel lyn, T 811 00:34:58,740 --> 00:35:02,740 4, wat gee my 2 keer 2 plus 4, so 8. 812 00:35:02,740 --> 00:35:07,080 As ek dan prop in 8 na die vorige lyn, wat gee my 2 keer 8, 16. 813 00:35:07,080 --> 00:35:12,470 En as ons dan voortgaan om met die 24, en voeg in 16, het ons uiteindelik 'n 814 00:35:12,470 --> 00:35:13,820 waarde van 64. 815 00:35:13,820 --> 00:35:18,480 >> Nou dat in en van die self soort van praat niks aan die n notering, die 816 00:35:18,480 --> 00:35:20,700 Big O, die omega wat ons het gepraat oor. 817 00:35:20,700 --> 00:35:24,890 Maar dit blyk dat die 64 wel 16, die grootte van die insette, 818 00:35:24,890 --> 00:35:27,110 teken basis 2 van 16. 819 00:35:27,110 --> 00:35:30,200 En as dit is 'n bietjie vreemd, net dink terug, en dit sal kom terug 820 00:35:30,200 --> 00:35:30,700 aan jou uiteindelik. 821 00:35:30,700 --> 00:35:33,775 As dit is log basis 2, is dit soos 2 geopper word, te die wat gee jou 16? 822 00:35:33,775 --> 00:35:36,380 O, dit is 4, so dit is 16 keer 4. 823 00:35:36,380 --> 00:35:39,380 >> En weer, dit is nie 'n groot deal as dit is 'n soort van 'n vae herinnering nou. 824 00:35:39,380 --> 00:35:43,720 Maar vir nou, neem oor geloof dat 16 log 16 is 64. 825 00:35:43,720 --> 00:35:46,590 En so ja, met hierdie eenvoudige gesonde verstand kyk, het ons bevestig - 826 00:35:46,590 --> 00:35:48,250 maar nie bewys formeel - 827 00:35:48,250 --> 00:35:52,800 dat die loop van die tyd van saamsmelt soort is inderdaad 'n teken n. 828 00:35:52,800 --> 00:35:53,790 >> So nie sleg nie. 829 00:35:53,790 --> 00:35:57,260 Dit is beslis beter as die algoritmes wat ons tot dusver gesien het, en 830 00:35:57,260 --> 00:36:00,710 dit is, want ons het aged, een, 'n tegniek genoem rekursie. 831 00:36:00,710 --> 00:36:03,880 Maar meer interessant as dit, wat idee van verdeling en verower. 832 00:36:03,880 --> 00:36:07,460 Weereens, werklik week 0 dinge wat Selfs nou is herhalende in 'n 833 00:36:07,460 --> 00:36:08,740 meer dwingende manier. 834 00:36:08,740 --> 00:36:11,750 >> Nou 'n prettige min oefening, as jy het nog nooit dit gedoen - en jy sal waarskynlik 835 00:36:11,750 --> 00:36:14,660 wil nie hê, want soort van normale mense dink nie dit te doen. 836 00:36:14,660 --> 00:36:20,650 Maar as ek gaan na google.com en as Ek wil iets om te leer 837 00:36:20,650 --> 00:36:22,356 rekursie, Tik. 838 00:36:22,356 --> 00:36:25,106 839 00:36:25,106 --> 00:36:29,058 >> [Gelag] 840 00:36:29,058 --> 00:36:32,030 [MEER Gelag] 841 00:36:32,030 --> 00:36:33,385 David Malan: slegte grap stadig versprei. 842 00:36:33,385 --> 00:36:34,450 [Gelag] 843 00:36:34,450 --> 00:36:36,970 David Malan: Slegs in die geval is, is dit daar. 844 00:36:36,970 --> 00:36:38,710 Ek het nie spel dit verkeerd is, en daar is die grap. 845 00:36:38,710 --> 00:36:40,810 Alle regte. 846 00:36:40,810 --> 00:36:42,950 Verduidelik dit aan die mense langs jou as dit het nog nie gekliek net nog nie. 847 00:36:42,950 --> 00:36:47,650 Maar rekursie, meer in die algemeen, verwys om die proses van 'n funksie roep 848 00:36:47,650 --> 00:36:51,430 self, of meer algemeen, die verdeling van 'n probleem in iets wat kan wees 849 00:36:51,430 --> 00:36:56,220 opgelos sporadies deur die oplossing van identiese verteenwoordiger probleme. 850 00:36:56,220 --> 00:36:58,400 >> Wel, laat ons wisselratte vir net 'n oomblik. 851 00:36:58,400 --> 00:37:00,840 Ons wil eindig op sekere cliffhangers, so laat ons begin te stel 852 00:37:00,840 --> 00:37:05,870 die stadium vir 'n paar minute, op 'n baie eenvoudige idee - 853 00:37:05,870 --> 00:37:07,620 dié van die uitruiling van twee elemente, reg? 854 00:37:07,620 --> 00:37:10,040 Al hierdie algoritmes ons het al praat oor die afgelope paar 855 00:37:10,040 --> 00:37:12,420 lesings behels 'n soort van uitruiling. 856 00:37:12,420 --> 00:37:14,630 Vandag is dit gesien word deur hulle kry uit hul stoele en 857 00:37:14,630 --> 00:37:18,570 rond te loop nie, maar in die kode, sou ons neem net 'n element van die een reeks 858 00:37:18,570 --> 00:37:20,370 en plop dit in 'n ander. 859 00:37:20,370 --> 00:37:21,880 >> So, hoe ons te werk gaan om dit te doen? 860 00:37:21,880 --> 00:37:24,850 Wel, laat ek gaan voort en skryf 'n vinnige program hier. 861 00:37:24,850 --> 00:37:31,600 Ek gaan om voort te gaan en te doen dit as die volgende. 862 00:37:31,600 --> 00:37:33,910 Kom ons noem dit - 863 00:37:33,910 --> 00:37:38,070 Wat wil ons doen om hierdie een te noem? 864 00:37:38,070 --> 00:37:38,650 >> Eintlik nie. 865 00:37:38,650 --> 00:37:39,420 Laat my rewind. 866 00:37:39,420 --> 00:37:41,220 Ek wil nie hê om dit te doen fotonische lewe nog. 867 00:37:41,220 --> 00:37:42,270 Dit sal bederf die pret. 868 00:37:42,270 --> 00:37:43,600 Kom ons doen dit eerder. 869 00:37:43,600 --> 00:37:47,430 >> Dink dat ek wil 'n bietjie te skryf program en wat behels nou hierdie 870 00:37:47,430 --> 00:37:48,700 idee van rekursie. 871 00:37:48,700 --> 00:37:50,370 Ek soort van het voor my daar. 872 00:37:50,370 --> 00:37:51,420 Ek gaan die volgende te doen. 873 00:37:51,420 --> 00:38:00,220 >> Eerstens, 'n vinnige sluit van standaard io.h, sowel as 'n sluit van cs50.h. 874 00:38:00,220 --> 00:38:03,200 En dan gaan ek om voort te gaan en verklaar int main leemte 875 00:38:03,200 --> 00:38:04,360 in die gewone manier. 876 00:38:04,360 --> 00:38:07,920 Ek het besef dat ek die lêer Verkeerd benoem, so laat my net voeg 'n C-uitbreiding. hier so 877 00:38:07,920 --> 00:38:09,510 dat ons kan stel dit behoorlik. 878 00:38:09,510 --> 00:38:10,970 Begin hierdie funksie af. 879 00:38:10,970 --> 00:38:13,290 >> En die funksie wat ek wil skryf, heel eenvoudig, is een wat vra die 880 00:38:13,290 --> 00:38:16,210 gebruiker vir 'n aantal en dan voeg tot al die getalle tussen wat 881 00:38:16,210 --> 00:38:19,920 nommer en, sê, 0. 882 00:38:19,920 --> 00:38:22,510 So eerste ek gaan om voort te gaan en verklaar int n. 883 00:38:22,510 --> 00:38:24,760 Toe het ek kopieer die kode wat wat ons gebruik het vir 'n rukkie. 884 00:38:24,760 --> 00:38:26,660 Terwyl iets waar is. 885 00:38:26,660 --> 00:38:28,000 Ek sal terug te kom na wat in 'n oomblik. 886 00:38:28,000 --> 00:38:29,010 >> Wat wil ek doen? 887 00:38:29,010 --> 00:38:33,460 Ek wil om te sê printf positiewe integer asseblief. 888 00:38:33,460 --> 00:38:36,130 En dan gaan ek sê n kry kry int. 889 00:38:36,130 --> 00:38:38,800 So weer, 'n paar boiler-kode dat ons al voorheen gebruik. 890 00:38:38,800 --> 00:38:40,810 En ek gaan om dit te doen terwyl n is minder as 1. 891 00:38:40,810 --> 00:38:44,120 So dit sal verseker dat die gebruiker gee my 'n positiewe heelgetal. 892 00:38:44,120 --> 00:38:45,490 >> En nou gaan ek die volgende te doen. 893 00:38:45,490 --> 00:38:51,020 Ek wil toe te voeg tot al die nommers tussen 1 en en N, of 0 en n, 894 00:38:51,020 --> 00:38:52,570 anders gestel, te kry om die totale bedrag. 895 00:38:52,570 --> 00:38:55,100 So die groot Sigma simbool wat jy kan onthou. 896 00:38:55,100 --> 00:38:59,050 So ek gaan om dit te doen deur die eerste roeping 'n funksie genoem Sigma, 897 00:38:59,050 --> 00:39:06,030 om dit in n, en dan gaan ek sê printf, die antwoord is reg daar. 898 00:39:06,030 --> 00:39:08,180 >> Dus, in kort, ek kry en int van die gebruiker. 899 00:39:08,180 --> 00:39:09,280 Ek verseker dit is positief. 900 00:39:09,280 --> 00:39:12,700 Ek verklaar 'n veranderlike genaamd antwoord tipe int en stoor in dit die terugkeer 901 00:39:12,700 --> 00:39:15,610 waarde van Sigma, verby in n as insette. 902 00:39:15,610 --> 00:39:17,060 En dan het ek druk die antwoord. 903 00:39:17,060 --> 00:39:19,550 >> Ongelukkig, selfs al Sigma klink soos iets wat kan wees in 904 00:39:19,550 --> 00:39:24,040 die math.h lêer, die verklaring, dit is eintlik nie. 905 00:39:24,040 --> 00:39:24,690 So dit is OK. 906 00:39:24,690 --> 00:39:26,170 Ek kan die uitvoering van hierdie myself. 907 00:39:26,170 --> 00:39:29,160 Ek gaan 'n funksie genoem te implementeer Sigma, en dit gaan 'n te neem 908 00:39:29,160 --> 00:39:29,900 parameter - 909 00:39:29,900 --> 00:39:32,100 Kom ons noem dit m, net dus is dit anders. 910 00:39:32,100 --> 00:39:35,910 En dan is hier, ek gaan om te sê, Wel, as m is minder as 1 - dit is 'n 911 00:39:35,910 --> 00:39:38,180 baie oninteressant program. 912 00:39:38,180 --> 00:39:41,700 So ek gaan om voort te gaan en onmiddellik terugkeer 0. 913 00:39:41,700 --> 00:39:45,920 Dit is net nie sin maak om op te tel al die nommers tussen 1 en m as m 914 00:39:45,920 --> 00:39:48,470 self 0 of negatief. 915 00:39:48,470 --> 00:39:50,900 >> En dan gaan ek om voort te gaan en doen dit baie iteratief. 916 00:39:50,900 --> 00:39:53,090 Ek gaan hierdie soort van die ou-skool te doen, en ek gaan om voort te gaan 917 00:39:53,090 --> 00:39:57,150 en sê dat ek gaan verklaar 'n bedrag aan 0 wees nie. 918 00:39:57,150 --> 00:39:59,630 Toe ek gaan te hê 'n lus vir die van int - 919 00:39:59,630 --> 00:40:02,820 en laat my dit doen ons aan te pas verspreiding kode, sodat jy het 'n afskrif 920 00:40:02,820 --> 00:40:07,500 by die huis. Int ek kry 1 op tot Ek is minder as of gelyk aan m. 921 00:40:07,500 --> 00:40:09,430 i plus plus. 922 00:40:09,430 --> 00:40:11,430 En dan binnekant van die for-lus - 923 00:40:11,430 --> 00:40:12,440 Ons is amper daar - 924 00:40:12,440 --> 00:40:15,810 som kry som plus 1. 925 00:40:15,810 --> 00:40:17,670 En dan gaan ek die som om terug te keer. 926 00:40:17,670 --> 00:40:19,420 >> So ek het dit vinnig nogal weliswaar. 927 00:40:19,420 --> 00:40:22,775 Maar weereens, die belangrikste funksie is redelik eenvoudige, gebaseer op kode wat ons het 928 00:40:22,775 --> 00:40:23,190 geskryf dusver. 929 00:40:23,190 --> 00:40:25,610 Gebruik van die dubbele lus om 'n positiewe te kry int van die gebruiker. 930 00:40:25,610 --> 00:40:29,870 Ek het toe gebeur dat int na 'n nuwe funksie sigma genoem, noem dit, weer, n. 931 00:40:29,870 --> 00:40:33,100 En ek slaan die terugkeer waarde, is die antwoord van die swart boks tans 932 00:40:33,100 --> 00:40:35,460 bekend as Sigma, in 'n veranderlike genoem antwoord. 933 00:40:35,460 --> 00:40:36,580 Dan druk ek dit. 934 00:40:36,580 --> 00:40:39,090 >> As ons nou voortgaan om die storie, hoe word Sigma geïmplementeer? 935 00:40:39,090 --> 00:40:40,840 Ek stel voor om te implementeer as volg. 936 00:40:40,840 --> 00:40:43,560 Eerstens, 'n bietjie van die fout kontrole om seker te maak dat die gebruiker nie ' 937 00:40:43,560 --> 00:40:46,480 geknoei met my en verby in 'n paar negatiewe of 0 waarde. 938 00:40:46,480 --> 00:40:49,710 Toe ek verklaar 'n veranderlike genoem som en sit dit aan 0. 939 00:40:49,710 --> 00:40:55,910 >> En nou het ek begin om te beweeg van i gelyk 1 al die pad tot en met m, 940 00:40:55,910 --> 00:41:00,130 want ek wil al die te sluit getalle van een deur m, ingesluit. 941 00:41:00,130 --> 00:41:04,350 En binnekant van die for-lus, het ek net doen som kry wat dit nou is, plus die 942 00:41:04,350 --> 00:41:08,900 waarde van i. 943 00:41:08,900 --> 00:41:10,370 Plus die waarde van i. 944 00:41:10,370 --> 00:41:14,090 >> As 'n eenkant, as jy nie gesien het nie hierdie voor, daar is 'n paar sintaktiese suiker 945 00:41:14,090 --> 00:41:14,870 vir hierdie lyn. 946 00:41:14,870 --> 00:41:21,120 Ek kan herskryf dit as plus gelyk aan i, net om te red myself 'n paar toetsaanslagen 947 00:41:21,120 --> 00:41:22,570 en 'n bietjie koeler te kyk. 948 00:41:22,570 --> 00:41:23,140 Maar dis al. 949 00:41:23,140 --> 00:41:24,660 Dit is funksioneel dieselfde ding. 950 00:41:24,660 --> 00:41:26,710 >> Ongelukkig is hierdie kode se nie van plan om nog saam te stel. 951 00:41:26,710 --> 00:41:31,600 As ek loop maak Sigma 0, hoe is Ek gaan om te skree? 952 00:41:31,600 --> 00:41:33,473 Wat gaan dit nie hou nie? 953 00:41:33,473 --> 00:41:35,740 >> GEHOOR: [onhoorbaar]. 954 00:41:35,740 --> 00:41:37,800 >> David Malan: Ja, ek het nie verklaar die funksie tot bo, reg? 955 00:41:37,800 --> 00:41:40,590 C is 'n soort van dom, in dat dit net doen wat jy vertel om dit te doen, en jy 956 00:41:40,590 --> 00:41:41,880 het om dit te doen in daardie volgorde. 957 00:41:41,880 --> 00:41:45,910 En so as ek getref Tik hier, ek gaan kry 'n waarskuwing oor Sigma implisiete 958 00:41:45,910 --> 00:41:46,860 verklaring. 959 00:41:46,860 --> 00:41:48,120 >> O ja, nie 'n probleem nie. 960 00:41:48,120 --> 00:41:50,370 Ek kan gaan na die top, en ek kan sê, alles reg, wag 'n minuut. 961 00:41:50,370 --> 00:41:54,240 Sigma is 'n funksie wat terugkeer 'n int en verwag om 'n 962 00:41:54,240 --> 00:41:56,620 int as insette, kommapunt. 963 00:41:56,620 --> 00:41:59,550 Of ek kon die hele funksie bogenoemde hoof, maar in die algemeen, ek wil 964 00:41:59,550 --> 00:42:02,260 beveel teen daardie, want dit is lekker om altyd hoof by die top so 965 00:42:02,260 --> 00:42:06,310 jy kan reg duik en weet wat 'n program doen deur die lees van die eerste hoof. 966 00:42:06,310 --> 00:42:07,930 >> So nou laat my duidelik die skerm. 967 00:42:07,930 --> 00:42:09,330 Remake Sigma 0. 968 00:42:09,330 --> 00:42:10,340 Al lyk te sien. 969 00:42:10,340 --> 00:42:11,970 Laat my toe hardloop Sigma 0. 970 00:42:11,970 --> 00:42:12,770 Positiewe inter. 971 00:42:12,770 --> 00:42:15,580 Ek sal dit gee die aantal 3 om te hou dit eenvoudig. 972 00:42:15,580 --> 00:42:18,710 So wat gee my 3 plus 2 plus 1, so 6. 973 00:42:18,710 --> 00:42:20,750 Betree, en ja, ek kry 6. 974 00:42:20,750 --> 00:42:21,820 >> Ek kan iets groter - 975 00:42:21,820 --> 00:42:24,080 50, 12, 75. 976 00:42:24,080 --> 00:42:27,690 Net soos 'n raaklyn, ek gaan om dit te doen iets belaglik soos 'n baie groot 977 00:42:27,690 --> 00:42:30,375 nommer, O, wat eintlik gewerk het - 978 00:42:30,375 --> 00:42:31,600 eh, ek dink nie dit is reg. 979 00:42:31,600 --> 00:42:32,810 Kom ons kyk. 980 00:42:32,810 --> 00:42:34,060 Kom ons regtig gemors met dit. 981 00:42:34,060 --> 00:42:37,150 982 00:42:37,150 --> 00:42:38,400 >> Dit is 'n probleem. 983 00:42:38,400 --> 00:42:43,180 984 00:42:43,180 --> 00:42:44,970 Wat gaan aan? 985 00:42:44,970 --> 00:42:46,050 Die kode is nie so sleg nie. 986 00:42:46,050 --> 00:42:48,470 Dit is nog steeds lineêre. 987 00:42:48,470 --> 00:42:50,810 Fluit is 'n goeie effek, al is. 988 00:42:50,810 --> 00:42:52,060 Wat gaan aan? 989 00:42:52,060 --> 00:42:54,700 990 00:42:54,700 --> 00:42:55,620 >> Nie seker of ek dit hoor. 991 00:42:55,620 --> 00:42:57,620 So dit blyk uit - en Dit is as 'n eenkant. 992 00:42:57,620 --> 00:42:59,400 Dit is nie die kern van die idee van rekursie. 993 00:42:59,400 --> 00:43:02,480 Dit blyk uit, want ek probeer stel so 'n groot aantal, die meeste 994 00:43:02,480 --> 00:43:06,980 waarskynlik dit is wat verkeerd deur C as 'n positiewe getal nie, 995 00:43:06,980 --> 00:43:09,980 maar negatiewe getal. 996 00:43:09,980 --> 00:43:12,690 >> Ons het nie gepraat oor hierdie, maar dit blyk daar is negatiewe getalle 997 00:43:12,690 --> 00:43:14,210 in die wêreld, benewens om positiewe nommers. 998 00:43:14,210 --> 00:43:16,290 En die wyse waarop jy kan verteenwoordig 'n negatiewe getal 999 00:43:16,290 --> 00:43:19,530 wese is, kan jy gebruik maak van een spesiale bietjie aan te dui 1000 00:43:19,530 --> 00:43:20,400 positief oor die negatiewe. 1001 00:43:20,400 --> 00:43:22,950 Dit is 'n bietjie meer kompleks as dit, maar dit is die basiese idee. 1002 00:43:22,950 --> 00:43:26,740 >> So ongelukkig, as C is verwarrend een van daardie stukkies as eintlik beteken, 1003 00:43:26,740 --> 00:43:30,790 O ja, dit is 'n negatiewe getal, my lus hier, byvoorbeeld, is eintlik nooit 1004 00:43:30,790 --> 00:43:31,740 gaan beëindig. 1005 00:43:31,740 --> 00:43:33,850 So as ek was eintlik die druk van iets weer en weer, sou ons 1006 00:43:33,850 --> 00:43:34,650 sien 'n hele klomp. 1007 00:43:34,650 --> 00:43:36,220 Maar weereens, dit is behalwe die punt. 1008 00:43:36,220 --> 00:43:38,590 Dit is regtig net 'n soort intellektuele nuuskierigheid wat ons sal kom 1009 00:43:38,590 --> 00:43:39,550 uiteindelik weer aan. 1010 00:43:39,550 --> 00:43:43,400 Maar vir nou, is dit 'n korrekte implementering as ons aanvaar dat die 1011 00:43:43,400 --> 00:43:45,970 gebruiker sal ints wat pas binne ints. 1012 00:43:45,970 --> 00:43:49,370 >> Maar ek beweer dat hierdie kode, eerlik, kon word soveel meer eenvoudig gedoen. 1013 00:43:49,370 --> 00:43:54,060 As die doel by die hand is 'n aantal te neem soos m en voeg aan al die 1014 00:43:54,060 --> 00:43:59,510 getalle tussen dit en 1, of omgekeerd tussen 1 en dit, ek eis 1015 00:43:59,510 --> 00:44:03,380 dat ek kan leen hierdie idee dat saamsmelt soort het, wat 'n probleem is die neem van 1016 00:44:03,380 --> 00:44:05,660 van hierdie grootte en dit te verdeel in iets kleiner. 1017 00:44:05,660 --> 00:44:09,875 Miskien nie die helfte, maar kleiner, maar verteenwoordigend dieselfde. 1018 00:44:09,875 --> 00:44:12,130 Dieselfde idee, maar 'n kleiner probleem. 1019 00:44:12,130 --> 00:44:15,470 >> So ek is eintlik - laat my red hierdie lêer met 'n ander weergawe nommer. 1020 00:44:15,470 --> 00:44:17,670 Ons sal noem hierdie weergawe 1 in plaas van 0. 1021 00:44:17,670 --> 00:44:20,790 En ek sê dat ek eintlik kan reimplement dit in hierdie soort van 1022 00:44:20,790 --> 00:44:22,160 gedagte-buiging manier. 1023 00:44:22,160 --> 00:44:23,710 >> Ek gaan 'n deel daarvan uit te los. 1024 00:44:23,710 --> 00:44:27,710 Ek gaan om te sê as m is minder as of selfs gelyk aan 0 - 1025 00:44:27,710 --> 00:44:29,280 Ek gaan net 'n bietjie meer anale hierdie tyd 1026 00:44:29,280 --> 00:44:30,520 met my foutkontroles - 1027 00:44:30,520 --> 00:44:33,190 Ek gaan om voort te gaan en 0 terugkeer. 1028 00:44:33,190 --> 00:44:34,490 Dit is arbitrêr. 1029 00:44:34,490 --> 00:44:37,500 Ek is eenvoudig net te besluit of die gebruiker gee my 'n negatiewe getal, is ek 1030 00:44:37,500 --> 00:44:41,490 terugkeer 0, en hulle moet lees die dokumentasie nader. 1031 00:44:41,490 --> 00:44:42,170 >> Else - 1032 00:44:42,170 --> 00:44:44,070 sien wat ek gaan doen. 1033 00:44:44,070 --> 00:44:49,260 Anders gaan ek m plus om terug te keer - 1034 00:44:49,260 --> 00:44:51,010 Wat is Sigma van m? 1035 00:44:51,010 --> 00:44:56,710 Wel, Sigma van m plus m minus 1, plus minus 2 m, plus minus 3 m. 1036 00:44:56,710 --> 00:44:58,030 Ek wil nie al wat uit te skryf. 1037 00:44:58,030 --> 00:44:59,120 Hoekom het ek nie net punt? 1038 00:44:59,120 --> 00:45:05,080 Rekursief noem ek myself met 'n effens kleiner probleem, kommapunt, 1039 00:45:05,080 --> 00:45:06,840 en noem dit 'n dag? 1040 00:45:06,840 --> 00:45:07,040 >> Reg? 1041 00:45:07,040 --> 00:45:10,980 Nou ook hier is, kan jy voel of bekommerd dat dit 'n oneindige lus dat ek 1042 00:45:10,980 --> 00:45:15,450 induserende, waardeur ek die implementering Sigma deur roeping Sigma. 1043 00:45:15,450 --> 00:45:20,342 Maar dit is heeltemal OK, want ek gedink het voor 'n bykomende wat lyne? 1044 00:45:20,342 --> 00:45:22,600 >> GEHOOR: [onhoorbaar]. 1045 00:45:22,600 --> 00:45:25,430 >> David Malan 23 tot 26, wat is my indien toestand. 1046 00:45:25,430 --> 00:45:28,390 Want wat is lekker om oor die aftrek hier, want ek bewaar 1047 00:45:28,390 --> 00:45:31,180 oorhandig Sigma kleiner probleme, kleiner probleme, kleiner - dit is nie 1048 00:45:31,180 --> 00:45:31,870 helfte van die grootte. 1049 00:45:31,870 --> 00:45:34,380 Dit is net 'n baba stap kleiner, maar dis OK. 1050 00:45:34,380 --> 00:45:38,050 Omdat uiteindelik, sal ons werk ons pad af na 1 of 0. 1051 00:45:38,050 --> 00:45:41,630 En wanneer ons getref het 0, Sigma is nie gaan om homself meer te noem. 1052 00:45:41,630 --> 00:45:43,590 Dit gaan dadelik terug te keer 0. 1053 00:45:43,590 --> 00:45:47,960 >> So het die effek, as jy soort van wind hierdie up in jou gedagtes, is m plus by te voeg 1054 00:45:47,960 --> 00:45:52,740 m minus 1, plus minus 2 m, plus m minus 3, plus dot, dot, dot, m minus 1055 00:45:52,740 --> 00:45:57,820 m, en uiteindelik gee jy 0, en die effek is uiteindelik al te voeg 1056 00:45:57,820 --> 00:45:59,070 hierdie dinge saam. 1057 00:45:59,070 --> 00:46:02,380 So ons het nie, met rekursie, die probleem opgelos dat ons 1058 00:46:02,380 --> 00:46:03,470 kon nie los voor. 1059 00:46:03,470 --> 00:46:06,840 Inderdaad, weergawe 0 van hierdie, en elke probleem tot op datum, is opgelos 1060 00:46:06,840 --> 00:46:09,980 met net die gebruik vir sirkelroetes of terwyl sirkelroetes of soortgelyke konstrukte. 1061 00:46:09,980 --> 00:46:13,150 >> Maar rekursie, het ek daresay, gee ons 'n ander manier van dink oor 1062 00:46:13,150 --> 00:46:17,010 probleme, waardeur as ons kan neem om 'n probleem, verdeel dit uit iets 1063 00:46:17,010 --> 00:46:22,340 bietjie groot in iets ietwat kleiner, Ek eis dat ons dit kan oplos 1064 00:46:22,340 --> 00:46:26,040 miskien 'n bietjie meer elegant in terme van die ontwerp, met minder kode, 1065 00:46:26,040 --> 00:46:30,980 en dalk selfs probleme op te los wat sou moeiliker wees, as ons uiteindelik 1066 00:46:30,980 --> 00:46:33,280 sien, die belangrikheid van suiwer iteratief. 1067 00:46:33,280 --> 00:46:35,980 >> Maar die fotonische lewe wat ek gedoen het ons wil verlaat het, was dit. 1068 00:46:35,980 --> 00:46:40,720 Laat my gaan voort en oop 'n lêer van - 1069 00:46:40,720 --> 00:46:44,300 eintlik, laat my gaan en doen dit baie vinnig. 1070 00:46:44,300 --> 00:46:46,875 Laat my gaan voort en stel die volgende. 1071 00:46:46,875 --> 00:46:51,160 1072 00:46:51,160 --> 00:46:54,785 Onder vandag se kode is hierdie lêer hier. 1073 00:46:54,785 --> 00:47:01,090 1074 00:47:01,090 --> 00:47:03,050 Hierdie een hier, noswap. 1075 00:47:03,050 --> 00:47:06,260 >> So, dit is 'n dom bietjie program wat Ek opgesweep dat eise om te doen 1076 00:47:06,260 --> 00:47:06,940 die volgende. 1077 00:47:06,940 --> 00:47:10,140 In die belangrikste, is dit verklaar 'n eerste int genoem x en ken dit 1078 00:47:10,140 --> 00:47:11,100 die waarde van 1. 1079 00:47:11,100 --> 00:47:13,520 Dan is dit verklaar 'n int y en wys dit die waarde 2. 1080 00:47:13,520 --> 00:47:15,310 Dan is dit druk uit wat x en y is. 1081 00:47:15,310 --> 00:47:17,781 Dan sê dit, uitruiling, dot dot dot. 1082 00:47:17,781 --> 00:47:21,670 >> Dan is dit beweer dat hy 'n beroep 'n funksie genoem ruil, verby in x en 1083 00:47:21,670 --> 00:47:24,290 y, die idee van wat is dat hopelik x en y sal terugkom 1084 00:47:24,290 --> 00:47:25,620 anders, die teenoorgestelde. 1085 00:47:25,620 --> 00:47:27,110 Dan is dit eis verruil! 1086 00:47:27,110 --> 00:47:28,420 met 'n uitroepteken. 1087 00:47:28,420 --> 00:47:30,190 Dan is dit druk uit x en y. 1088 00:47:30,190 --> 00:47:33,480 >> Maar dit blyk dat hierdie baie eenvoudige demonstrasie af 1089 00:47:33,480 --> 00:47:35,570 hier is eintlik karretjie. 1090 00:47:35,570 --> 00:47:38,870 Selfs al het ek waarby 'n tydelike veranderlike en tydelik om 'n in 1091 00:47:38,870 --> 00:47:42,010 dit, dan is ek gehou indiensneming n die waarde van b - 1092 00:47:42,010 --> 00:47:45,080 wat voel redelik, want ek het gered van 'n afskrif van 'n in temp. 1093 00:47:45,080 --> 00:47:48,410 Toe het ek werk b op gelyke wat ook al in temp. 1094 00:47:48,410 --> 00:47:51,610 Hierdie soort dop spel van die beweging van 'n in b en b in 'n deur die gebruik van hierdie 1095 00:47:51,610 --> 00:47:54,360 middel-man genoem temp voel heel redelik. 1096 00:47:54,360 --> 00:47:57,270 >> Maar ek beweer dat wanneer ek loop hierdie kode, soos ek nou sal doen - 1097 00:47:57,270 --> 00:47:59,490 Laat my gaan voort en plak dit hier. 1098 00:47:59,490 --> 00:48:01,995 Ek bel die noswap.c. 1099 00:48:01,995 --> 00:48:05,630 En soos die naam aandui, is dit nie gaan na 'n korrekte program wees. 1100 00:48:05,630 --> 00:48:09,460 Maak noswap / geen ruil.. 1101 00:48:09,460 --> 00:48:12,110 x is 1, y is 2, uitruiling, verruil. 1102 00:48:12,110 --> 00:48:14,220 x is 1, y is 2. 1103 00:48:14,220 --> 00:48:16,920 Dit is fundamenteel verkeerd is, selfs hoewel dit lyk perfek 1104 00:48:16,920 --> 00:48:17,730 my redelik. 1105 00:48:17,730 --> 00:48:21,330 En daar is 'n rede, maar ons is nie gaan om die rede om net nog nie openbaar. 1106 00:48:21,330 --> 00:48:24,610 >> Vir nou die tweede fotonische lewe Ek wou om jou te laat is, word 'n 1107 00:48:24,610 --> 00:48:27,120 aankondiging van spesies op coupons. 1108 00:48:27,120 --> 00:48:31,590 Ons innovasie met laat dae hierdie jaar uitgelok het 'n nie-triviale aantal 1109 00:48:31,590 --> 00:48:33,830 van die vrae wat was nie ons bedoeling. 1110 00:48:33,830 --> 00:48:36,590 Die bedoeling van hierdie coupon kodes, waardeur as jy nie deel van die probleem 1111 00:48:36,590 --> 00:48:39,850 stel vroeg, sodoende kry 'n ekstra dag, was regtig om jou te help ouens help 1112 00:48:39,850 --> 00:48:42,420 jouself vroeg begin, soort van deur incentivizing jou. 1113 00:48:42,420 --> 00:48:44,880 Help ons versprei vrag oor kantoorure beter sodat 1114 00:48:44,880 --> 00:48:45,740 dit is soort van wen-wen. 1115 00:48:45,740 --> 00:48:48,860 >> Ongelukkig, ek dink my instruksies het nie, tot op datum, baie duidelik, so 1116 00:48:48,860 --> 00:48:52,230 Ek het teruggegaan hierdie naweek en opgedateer die spec in groter, vetter teks 1117 00:48:52,230 --> 00:48:53,600 verduidelik koeëls soos hierdie. 1118 00:48:53,600 --> 00:48:56,900 En net om dit meer in die openbaar sê, deur verstek, probleem stelle is as gevolg van Donderdag 1119 00:48:56,900 --> 00:48:58,400 teen die middag, volgens die leerplan. 1120 00:48:58,400 --> 00:49:02,030 As jy vroeg begin, afwerking deel van die probleem wat deur Woensdag om 12:00 1121 00:49:02,030 --> 00:49:05,170 PM, die deel wat verband hou met 'n koepon kode, die idee is dat jy kan uit te brei 1122 00:49:05,170 --> 00:49:07,710 jou sperdatum vir die P stel tot Vrydag. 1123 00:49:07,710 --> 00:49:10,890 Dit is bietjie af 'n klein deel van die P stel met betrekking tot wat tipies is die 1124 00:49:10,890 --> 00:49:13,200 groter probleem, en jy koop jouself 'n ekstra dag. 1125 00:49:13,200 --> 00:49:15,190 Weereens, dit kry jy dink oor die probleem stel, kry jy te 1126 00:49:15,190 --> 00:49:16,380 kantoorure gouer. 1127 00:49:16,380 --> 00:49:20,670 Maar die koepon kode probleem is nog steeds vereis word, selfs al is jy nie dien nie. 1128 00:49:20,670 --> 00:49:23,340 >> Maar is meer compellingly hierdie. 1129 00:49:23,340 --> 00:49:26,520 (Verhoog Fluister) En dié mense verlaat vroeg is dit nou eers spyt. 1130 00:49:26,520 --> 00:49:28,620 As die mense op die balkon. 1131 00:49:28,620 --> 00:49:32,510 Ek vra om verskoning by voorbaat aan die mense op die balkon vir die redes wat sal wees 1132 00:49:32,510 --> 00:49:33,920 duidelik in net 'n oomblik. 1133 00:49:33,920 --> 00:49:37,050 >> So ons is bevoorreg om een ​​te hê CS50 se voormalige hoof onderrig metgeselle by 1134 00:49:37,050 --> 00:49:39,302 'n maatskappy genaamd dropbox.com. 1135 00:49:39,302 --> 00:49:45,500 Hulle het baie mildelik geskenk van 'n coupon code hier vir hierdie baie ruimte, 1136 00:49:45,500 --> 00:49:48,180 wat uit die gewoonlik 2 GB. 1137 00:49:48,180 --> 00:49:51,740 So, wat het ek gedink ons ​​sou doen oor hierdie laaste opmerking is nie 'n bietjie van 'n bonus, 1138 00:49:51,740 --> 00:49:55,380 waardeur in net 'n oomblik, sal ons openbaar die wenner en wat 'n koepon 1139 00:49:55,380 --> 00:49:57,980 kode wat jy dan kan gaan na hul webwerf, tik dit in, en voila, kry 'n 1140 00:49:57,980 --> 00:50:01,370 hele klomp meer Dropbox ruimte vir jou apparaat en vir jou persoonlike lêers. 1141 00:50:01,370 --> 00:50:05,690 >> En die eerste, wat graag om deel te neem in hierdie tekening? 1142 00:50:05,690 --> 00:50:09,630 OK, nou wat maak dit selfs meer pret. 1143 00:50:09,630 --> 00:50:14,010 Die persoon wat hierdie 25-GB ontvang coupon kode - dit is verreweg 1144 00:50:14,010 --> 00:50:16,150 meer oortuigend as die laat dae nou, miskien - 1145 00:50:16,150 --> 00:50:20,620 is die een wat op die top van 'n sit stoel kussing onder wat daar is 1146 00:50:20,620 --> 00:50:21,620 dat coupon code. 1147 00:50:21,620 --> 00:50:23,480 Jy kan nou kyk onder jou stoel kussing. 1148 00:50:23,480 --> 00:50:28,710 1149 00:50:28,710 --> 00:50:29,680 >> [Video speel] 1150 00:50:29,680 --> 00:50:31,620 >> -Een, twee, drie. 1151 00:50:31,620 --> 00:50:35,015 >> [Skree] 1152 00:50:35,015 --> 00:50:35,985 >> -Jy kry 'n motor! 1153 00:50:35,985 --> 00:50:36,670 Kry jy 'n kar! 1154 00:50:36,670 --> 00:50:37,970 >> David Malan: Ons sal sien jy op Woensdag. 1155 00:50:37,970 --> 00:50:38,904 >> -Jy kry 'n motor! 1156 00:50:38,904 --> 00:50:39,371 Kry jy 'n kar! 1157 00:50:39,371 --> 00:50:40,305 Kry jy 'n kar! 1158 00:50:40,305 --> 00:50:41,706 Kry jy 'n kar! 1159 00:50:41,706 --> 00:50:43,107 Kry jy 'n kar! 1160 00:50:43,107 --> 00:50:45,530 >> David Malan: balkon mense, kom hier aan die voorkant, 1161 00:50:45,530 --> 00:50:46,866 waar ons ekstras. 1162 00:50:46,866 --> 00:50:50,282 >> -Almal kry 'n motor! 1163 00:50:50,282 --> 00:50:52,234 Almal kry 'n motor! 1164 00:50:52,234 --> 00:50:52,722 >> [Einde video-vertoning] 1165 00:50:52,722 --> 00:50:54,590 >> NARRATOR: By die volgende CS50 - 1166 00:50:54,590 --> 00:51:00,374 >> SPREKER 5: Oh my gosh gosh gosh gosh gosh gosh gosh gosh gosh gosh - 1167 00:51:00,374 --> 00:51:02,106 >> [Ukelele TONEELSTUKKE]