1 00:00:00,000 --> 00:00:11,100 >> [Speel van musiek] 2 00:00:11,100 --> 00:00:11,490 >> David J. MALAN: Alle reg. 3 00:00:11,490 --> 00:00:12,170 So terug te verwelkom. 4 00:00:12,170 --> 00:00:15,180 Dit is CS50, en die is die einde van die week, drie. 5 00:00:15,180 --> 00:00:17,770 >> So onthou in die afgelope paar weke, het ons spandeer nogal 'n bietjie van 6 00:00:17,770 --> 00:00:20,820 tyd op C, op ontwikkeling, op sintaksis. 7 00:00:20,820 --> 00:00:24,680 En dit is heel normaal, as jy nog sukkel met die probleem Stel 2, te wees 8 00:00:24,680 --> 00:00:25,950 gebons jou kop teen die muur. 9 00:00:25,950 --> 00:00:28,310 Dit is kripties-looking fout boodskappe en foute wat jy 10 00:00:28,310 --> 00:00:29,220 kan nie heeltemal jaag. 11 00:00:29,220 --> 00:00:32,310 Omdat, gerus wees, wat in net 'n paar weke sal jy terugkyk op 12 00:00:32,310 --> 00:00:35,930 dinge soos Caesar, en [? V-genair,?] miskien selfs kraak, en 13 00:00:35,930 --> 00:00:40,050 besef net hoe ver het jy gekom in 'n kort tydperk van die tyd. 14 00:00:40,050 --> 00:00:43,670 So as dit enige troos, hang in daar vir nou. 15 00:00:43,670 --> 00:00:46,610 >> Vandag, egter, is ons begin met die oorgang om dinge hoër vlak. 16 00:00:46,610 --> 00:00:49,820 En ons begin om te neem as vanselfsprekend aanvaar dat julle weet hoe om die program, of by 17 00:00:49,820 --> 00:00:52,090 minste die begin van die dat comfort vlak. 18 00:00:52,090 --> 00:00:56,520 En ons sal begin om te dink oor hoe ons kan gaan oor die ontwerp van programme meer 19 00:00:56,520 --> 00:00:57,440 effektief. 20 00:00:57,440 --> 00:01:01,090 Hoe kan ons gaan oor die optimalisering van die doeltreffendheid van ons algoritmes, en 21 00:01:01,090 --> 00:01:03,110 algemeen oplossing meer interessante probleme. 22 00:01:03,110 --> 00:01:06,850 En begin om te neem as vanselfsprekend aanvaar dat, As ons wou, kon ons ook kode op enige 23 00:01:06,850 --> 00:01:08,350 van die voorbeelde wat ons in gedagte het. 24 00:01:08,350 --> 00:01:11,430 So vandag, het ons nie raak die klawerbord vir enige vorm van kode. 25 00:01:11,430 --> 00:01:15,150 Dit sal veel hoër vlak wees, en uiteindelik oor probleemoplossing. 26 00:01:15,150 --> 00:01:20,490 >> So te kry om daardie punt, laat my stel dat die volgende sewe 27 00:01:20,490 --> 00:01:24,290 reghoeke uit sewe deure, agter wat is 'n hele klomp van die 28 00:01:24,290 --> 00:01:26,340 nommers, waaronder die nommer 50. 29 00:01:26,340 --> 00:01:30,470 Laat my by hierdie projek op hierdie skerm hier so goed. 30 00:01:30,470 --> 00:01:36,770 En stel voor dat ons nodig het om 'n vrywilliger te help om my 'n nommer in die voorkant van 31 00:01:36,770 --> 00:01:38,140 die internet hier om te sien. 32 00:01:38,140 --> 00:01:40,755 Kom op, in die pienk. 33 00:01:40,755 --> 00:01:43,050 Alle regte. 34 00:01:43,050 --> 00:01:43,930 Wat is jou naam? 35 00:01:43,930 --> 00:01:44,850 >> JENNIFER: [onhoorbaar] 36 00:01:44,850 --> 00:01:45,170 >> David J. Malan Jammer? 37 00:01:45,170 --> 00:01:45,860 >> JENNIFER: Jennifer. 38 00:01:45,860 --> 00:01:46,390 >> David J. MALAN: Jennifer. 39 00:01:46,390 --> 00:01:46,980 Alle reg, Jennifer. 40 00:01:46,980 --> 00:01:47,630 Nice om jou te ontmoet. 41 00:01:47,630 --> 00:01:48,370 Kom up. 42 00:01:48,370 --> 00:01:52,430 So het hierdie hier is sewe deure, en wat Ek wil graag om te doen vir ons hier, 43 00:01:52,430 --> 00:01:56,560 in die voorkant van al jou klasmaats, word vind ons die getal, 50. 44 00:01:56,560 --> 00:02:00,860 'N nommer te vind, kan jy loer agter enige van hierdie deure deur eenvoudig 45 00:02:00,860 --> 00:02:03,030 op een van die deure, en dit sal openbaar sy nommer. 46 00:02:03,030 --> 00:02:06,080 En laat ons sien hoe vinnig jy vind ons die getal, 50. 47 00:02:06,080 --> 00:02:09,979 48 00:02:09,979 --> 00:02:11,229 >> 15. 49 00:02:11,229 --> 00:02:13,110 50 00:02:13,110 --> 00:02:14,360 16. 51 00:02:14,360 --> 00:02:16,270 52 00:02:16,270 --> 00:02:16,530 50. 53 00:02:16,530 --> 00:02:17,350 Mooi gedoen. 54 00:02:17,350 --> 00:02:18,040 Alle regte. 55 00:02:18,040 --> 00:02:19,906 Rondte van applous vir Jennifer. 56 00:02:19,906 --> 00:02:21,530 >> [Applous] 57 00:02:21,530 --> 00:02:22,320 >> Alle regte. 58 00:02:22,320 --> 00:02:25,254 So, wat was jou strategie vir vind die getal, 50? 59 00:02:25,254 --> 00:02:27,222 >> JENNIFER: Um, ek het gedink miskien is indien - 60 00:02:27,222 --> 00:02:27,714 [Onhoorbaar] 61 00:02:27,714 --> 00:02:28,206 >> David J. Malan Oh. 62 00:02:28,206 --> 00:02:29,630 Gee dit 'n sekonde. 63 00:02:29,630 --> 00:02:32,420 So was jou strategie vir vind die getal, 50? 64 00:02:32,420 --> 00:02:34,760 >> JENNIFER: So het ek net begin by die begin om te sien wat die eerste getal 65 00:02:34,760 --> 00:02:38,590 was, en dan het ek gedink, miskien as hulle is gesorteer, ek sal net hou 66 00:02:38,590 --> 00:02:39,970 afluister hoër op? 67 00:02:39,970 --> 00:02:40,140 >> David J. MALAN: OK. 68 00:02:40,140 --> 00:02:42,910 En ons lyk gevind wat die geval te wees. 69 00:02:42,910 --> 00:02:45,670 Alhoewel, laat ons terug skil die lae net 'n bietjie, en jy wil om te gaan 70 00:02:45,670 --> 00:02:47,640 voor en onthul die ander deure jy kon gekies het? 71 00:02:47,640 --> 00:02:50,400 72 00:02:50,400 --> 00:02:51,712 >> JENNIFER: O, liewe. 73 00:02:51,712 --> 00:02:53,128 >> David J. MALAN: Ag. 74 00:02:53,128 --> 00:02:54,280 >> JENNIFER: So het ek net gelukkig. 75 00:02:54,280 --> 00:02:55,270 >> David J. MALAN: So jy het gelukkig nie. 76 00:02:55,270 --> 00:02:55,710 Alle regte. 77 00:02:55,710 --> 00:02:56,795 So nie sleg nie. 78 00:02:56,795 --> 00:02:58,750 Maar dit is 'n interessante insig, reg? 79 00:02:58,750 --> 00:03:01,870 As jy aanvaar, en jy het kry, Inderdaad, 'n bietjie geluk is daar. 80 00:03:01,870 --> 00:03:05,350 Maar as jy aanvaar dat die getalle was gesorteer, kan jy meer presies te wees 81 00:03:05,350 --> 00:03:08,750 oor hoe dit beïnvloed jou gedrag? 82 00:03:08,750 --> 00:03:11,715 >> JENNIFER: So as hulle is gesorteer, ek gedink miskien is die kleinste tot die grootste. 83 00:03:11,715 --> 00:03:11,970 >> David J. MALAN: OK. 84 00:03:11,970 --> 00:03:15,260 >> JENNIFER: Of as dit beland baie groot, dan is die grootste tot die kleinste. 85 00:03:15,260 --> 00:03:15,540 >> David J. MALAN: OK. 86 00:03:15,540 --> 00:03:18,170 So die grootste tot die kleinste, of kleinste tot die grootste. 87 00:03:18,170 --> 00:03:21,990 Maar laat my stel, veronderstel jy het gekry het ongelukkig, en dink dat hulle 88 00:03:21,990 --> 00:03:26,840 is nie, in werklikheid, gesorteer, hoeveel van die deure kan jy gehad het om te blik 89 00:03:26,840 --> 00:03:28,590 agter in die ergste geval? 90 00:03:28,590 --> 00:03:29,860 >> JENNIFER: Almal van hulle. 91 00:03:29,860 --> 00:03:30,420 >> David J. MALAN: Almal van hulle. 92 00:03:30,420 --> 00:03:31,740 So laat se veralgemeen dat as n. 93 00:03:31,740 --> 00:03:34,790 Daar gebeur te wees 7, maar laat ons meer algemeen sê daar is 'n deure op die 94 00:03:34,790 --> 00:03:35,650 skerm hier. 95 00:03:35,650 --> 00:03:40,110 So in die ergste geval, sou jy om te kyk agter 7 deure, of N deure. 96 00:03:40,110 --> 00:03:44,140 En so is dit regtig nie, dit is 'n bietjie van ' geluk van vandag, maar dit is regtig 'n lineêre 97 00:03:44,140 --> 00:03:46,440 algoritme van die spesies, selfs al is jy was soort van spring rond. 98 00:03:46,440 --> 00:03:47,080 Is dit regverdig? 99 00:03:47,080 --> 00:03:47,500 >> JENNIFER: Ja. 100 00:03:47,500 --> 00:03:50,000 >> David J. MALAN: Wel, laat ek sien of jou strategie verander as ek beweeg om ons te 101 00:03:50,000 --> 00:03:52,190 ons tweede voorbeeld hier met 7 verskillende deure. 102 00:03:52,190 --> 00:03:55,240 Dieselfde getalle nie, maar dit tyd wat hulle is gesorteer. 103 00:03:55,240 --> 00:03:58,350 Wat is jou strategie hier gaan wees, probeer om uit jou gees wat 104 00:03:58,350 --> 00:03:59,310 die ander getalle is - 105 00:03:59,310 --> 00:03:59,930 >> JENNIFER: OK. 106 00:03:59,930 --> 00:04:02,290 >> David J. Malan - vroeër? 107 00:04:02,290 --> 00:04:03,180 >> JENNIFER: Kom ons begin met die eerste een. 108 00:04:03,180 --> 00:04:03,540 >> David J. MALAN: Alle reg. 109 00:04:03,540 --> 00:04:05,190 Begin met die eerste een. 110 00:04:05,190 --> 00:04:05,960 4. 111 00:04:05,960 --> 00:04:08,810 Nou waar jy gaan om te gaan, en hoekom? 112 00:04:08,810 --> 00:04:10,040 >> JENNIFER: 4 is baie klein. 113 00:04:10,040 --> 00:04:12,500 So as hulle is soort miskien kleinste tot die grootste, moet dit 114 00:04:12,500 --> 00:04:13,290 twee keer nie, en -. 115 00:04:13,290 --> 00:04:13,670 >> David J. MALAN: OK. 116 00:04:13,670 --> 00:04:15,990 Kom ons kyk, wat dink jy? 117 00:04:15,990 --> 00:04:19,050 >> JENNIFER: Probeer die laaste een. 118 00:04:19,050 --> 00:04:19,500 Nice. 119 00:04:19,500 --> 00:04:20,880 >> David J. MALAN: Baie mooi gedoen. 120 00:04:20,880 --> 00:04:21,860 Alle regte. 121 00:04:21,860 --> 00:04:23,010 >> [Applous] 122 00:04:23,010 --> 00:04:24,310 >> David J. MALAN: OK. 123 00:04:24,310 --> 00:04:26,790 So jy is eintlik om dit te doen verskriklik, omdat jy 124 00:04:26,790 --> 00:04:27,700 doen dit baie goed. 125 00:04:27,700 --> 00:04:31,150 Wat laat ons nie in staat is om te maak sekere punte. 126 00:04:31,150 --> 00:04:32,565 So laat ons probeer om terug te rol hier. 127 00:04:32,565 --> 00:04:34,560 >> JENNIFER: OK. 128 00:04:34,560 --> 00:04:35,980 >> David J. MALAN: Baie goed gedoen het, nietemin. 129 00:04:35,980 --> 00:04:39,060 So jy begin by die begin, jy sien dat dit was 4, dan is jy 130 00:04:39,060 --> 00:04:40,240 verskuif na die einde. 131 00:04:40,240 --> 00:04:42,320 Maar dink jy nie kry gelukkig daar is, en veronderstel 50 132 00:04:42,320 --> 00:04:42,890 was iewers anders. 133 00:04:42,890 --> 00:04:46,190 Wat jou derde stap gewees het? 134 00:04:46,190 --> 00:04:47,680 >> JENNIFER: Gaan terug na die begin. 135 00:04:47,680 --> 00:04:48,320 >> David J. MALAN: Gaan terug aan die begin. 136 00:04:48,320 --> 00:04:51,320 OK, so jy sal aangeraak het hierdie deur, wat was 8. 137 00:04:51,320 --> 00:04:51,660 Alle regte. 138 00:04:51,660 --> 00:04:52,650 So dit is nie 50. 139 00:04:52,650 --> 00:04:55,380 Waar sou jy gelyk het volgende? 140 00:04:55,380 --> 00:04:56,720 >> JENNIFER: As ek gedoen het nie Weet hulle gesorteer. 141 00:04:56,720 --> 00:04:57,005 >> David J. MALAN: Korrekte. 142 00:04:57,005 --> 00:04:58,490 Wel, as jy nie weet hulle is gesorteer - 143 00:04:58,490 --> 00:04:58,700 >> JENNIFER: Ag, geweet het, ja. 144 00:04:58,700 --> 00:05:00,910 >> David J. Malan - maar julle het nie weet waar 50 was nie? 145 00:05:00,910 --> 00:05:01,785 >> JENNIFER: Slegs te gaan. 146 00:05:01,785 --> 00:05:02,130 >> David J. MALAN: Alle reg. 147 00:05:02,130 --> 00:05:02,520 OK. 148 00:05:02,520 --> 00:05:03,800 Gaan hou. 149 00:05:03,800 --> 00:05:05,270 OK, wat ek kan werk. 150 00:05:05,270 --> 00:05:05,610 >> JENNIFER: OK. 151 00:05:05,610 --> 00:05:07,210 >> David J. MALAN: Nou, as jy net gaan om voort te gaan, wat is jou 152 00:05:07,210 --> 00:05:09,680 algoritme wentel ondersteun in. 153 00:05:09,680 --> 00:05:10,740 >> JENNIFER: Die lineêre -. 154 00:05:10,740 --> 00:05:11,820 >> David J. MALAN: Dit is 'n soort van lineêre. 155 00:05:11,820 --> 00:05:13,480 Maar laat my stel, laat my sit op die plek. 156 00:05:13,480 --> 00:05:14,900 Laat my verfris die bladsy. 157 00:05:14,900 --> 00:05:17,120 dieselfde nommer, dieselfde reëling, dieselfde deure. 158 00:05:17,120 --> 00:05:21,350 Maar dink terug aan daardie eerste dag in klas toe ons skeur 'n telefoon boek in 159 00:05:21,350 --> 00:05:25,480 helfte, soort van, en wat was ons strategie is daar? 160 00:05:25,480 --> 00:05:26,450 >> JENNIFER: Begin by die middel. 161 00:05:26,450 --> 00:05:26,690 >> David J. MALAN: OK. 162 00:05:26,690 --> 00:05:27,610 So begin by die middel. 163 00:05:27,610 --> 00:05:28,790 So laat ons gaan voort en boots dit. 164 00:05:28,790 --> 00:05:30,720 Begin by die middel deur die onthulling dat die deure. 165 00:05:30,720 --> 00:05:31,660 So het die nommer 16. 166 00:05:31,660 --> 00:05:35,290 So, wat sou die sterk man gedoen het nie, wat die telefoon boek skeur in die helfte, 167 00:05:35,290 --> 00:05:38,450 te kry om die volgende raaiskoot? 168 00:05:38,450 --> 00:05:39,400 >> JENNIFER: Gaan in hierdie helfte. 169 00:05:39,400 --> 00:05:41,700 >> David J. MALAN: En hoekom die reg? 170 00:05:41,700 --> 00:05:43,900 >> JENNIFER: As hulle soort van kleinste tot die grootste, dan is 50 moet wees 171 00:05:43,900 --> 00:05:44,720 aan die einde. 172 00:05:44,720 --> 00:05:44,920 >> David J. MALAN: Goed. 173 00:05:44,920 --> 00:05:45,390 Heeltemal redelike. 174 00:05:45,390 --> 00:05:48,380 Dus, net soos 'n telefoon boek, gaan jy na die reg in teenstelling met die linker, maar hier 175 00:05:48,380 --> 00:05:49,500 is die sleutel afhaal. 176 00:05:49,500 --> 00:05:53,930 Jy kan nou weggooi, of skeur af, helfte van hierdie probleem, sodat jy nie 177 00:05:53,930 --> 00:05:55,970 met 7 deure, maar eintlik met net 3. 178 00:05:55,970 --> 00:05:57,870 Dit is ongeveer die helfte van die omvang van die probleem. 179 00:05:57,870 --> 00:05:58,350 Alle regte. 180 00:05:58,350 --> 00:06:01,890 So nou wat jy wil hê gedoen nadat jy gaan reg? 181 00:06:01,890 --> 00:06:05,870 >> JENNIFER: So 16 is nog redelik klein, relatief tot 50, so miskien sal ek probeer, 182 00:06:05,870 --> 00:06:06,700 soos hierdie een. 183 00:06:06,700 --> 00:06:07,890 >> David J. MALAN: Alle reg. 184 00:06:07,890 --> 00:06:08,720 42. 185 00:06:08,720 --> 00:06:10,830 Alle reg, so nou wat is jou instink wat jy vertel? 186 00:06:10,830 --> 00:06:12,100 >> JENNIFER: Ek kan weggooi hierdie en dan net - 187 00:06:12,100 --> 00:06:12,360 >> David J. MALAN: OK. 188 00:06:12,360 --> 00:06:14,212 Goed is, kan jy weggooi die linker helfte was daar. 189 00:06:14,212 --> 00:06:14,890 >> JENNIFER: - kies hierdie een. 190 00:06:14,890 --> 00:06:15,530 >> David J. MALAN: En die reg. 191 00:06:15,530 --> 00:06:15,760 >> JENNIFER: Ja. 192 00:06:15,760 --> 00:06:17,820 >> David J. MALAN: So selfs al is dit moeilik miskien sien, wanneer daar net 193 00:06:17,820 --> 00:06:21,320 7 deure, dink, nou, die konsekwentheid van die 194 00:06:21,320 --> 00:06:22,620 algoritme jy net toegepas word. 195 00:06:22,620 --> 00:06:24,510 In die vorige geval, jy het gelukkig is, wat so groot was. 196 00:06:24,510 --> 00:06:26,540 Maar jy het gebruik 'n heuristiese, Ek sou sê. 197 00:06:26,540 --> 00:06:29,150 Jy gebruik soort van jou instink, en wetende dat dit gesorteer is, as dit is mooi 198 00:06:29,150 --> 00:06:31,600 klein aan die begin, natuurlik, ons het het meer om te gaan na die regterkant. 199 00:06:31,600 --> 00:06:34,990 Maar in 'n sekere sin, jy het gelukkig, want miskien was dit die getal 100, 200 00:06:34,990 --> 00:06:36,220 en miskien 50 was meer in die middel. 201 00:06:36,220 --> 00:06:37,910 Miskien 50 was nog hier. 202 00:06:37,910 --> 00:06:40,960 >> Maar wat jy het 'n bietjie anders hierdie tyd was, julle het dieselfde ding 203 00:06:40,960 --> 00:06:42,150 weer en weer. 204 00:06:42,150 --> 00:06:45,310 En ek sou argumenteer dat dit wat jy net het, al is dit beïnvloed deur die telefoon 205 00:06:45,310 --> 00:06:48,100 boek byvoorbeeld, is iets veel meer algoritmiese, en nog baie 206 00:06:48,100 --> 00:06:49,930 minder spesiale cased. 207 00:06:49,930 --> 00:06:51,620 Veel minder instinktief. 208 00:06:51,620 --> 00:06:57,160 So in die einde van die dag, hoe sou jy beskryf die doeltreffendheid van die 209 00:06:57,160 --> 00:07:00,530 eerste algoritme, waar jy gegaan het links na regs, teenoor die 210 00:07:00,530 --> 00:07:03,430 tweede algoritme hier? 211 00:07:03,430 --> 00:07:06,460 >> JENNIFER: Dit moet 'n mens, soos, miskien helfte van die tyd, of selfs meer, ja. 212 00:07:06,460 --> 00:07:07,320 >> David J. MALAN: OK, miskien selfs meer. 213 00:07:07,320 --> 00:07:10,150 Kom ons druk 'n bietjie harder op daardie. 214 00:07:10,150 --> 00:07:13,030 Wat regtig, as ons voortgaan om hierdie logika, het ons beslis gehalveer die 215 00:07:13,030 --> 00:07:15,830 tyd met hierdie tweede algoritme deur gooi weg die helfte van die 216 00:07:15,830 --> 00:07:18,470 getalle nie, maar wat het ons op die volgende iterasie, wanneer Jennifer geopenbaar 217 00:07:18,470 --> 00:07:20,615 die tweede getal? 218 00:07:20,615 --> 00:07:22,830 >> Ons gehalveer die nommers van die deure weer. 219 00:07:22,830 --> 00:07:25,270 En dan wat het ons te doen na dat indien was daar meer deure te speel met? 220 00:07:25,270 --> 00:07:27,520 Ons wil halveer hulle, en weer, en weer en weer. 221 00:07:27,520 --> 00:07:30,420 En dit was net soos julle almal staan ​​by die eerste week van 222 00:07:30,420 --> 00:07:33,000 klas, die helfte van julle sit, half van julle sit, die helfte van u 223 00:07:33,000 --> 00:07:35,440 sit, totdat een eensame siel gestaan. 224 00:07:35,440 --> 00:07:39,050 En ons het gesê dat die loop van die tyd van dat die aantal stappe wat dit geneem het was 225 00:07:39,050 --> 00:07:40,430 op die einde van wat? 226 00:07:40,430 --> 00:07:41,230 >> Spreker 1: [onhoorbaar] 227 00:07:41,230 --> 00:07:43,970 >> David J. MALAN: So log basis 2 van n, of net meer eenvoudig, teken van n. 228 00:07:43,970 --> 00:07:45,060 So iets logaritmiese. 229 00:07:45,060 --> 00:07:48,380 En die grafiek was nie 'n reguit lyn wat net erger en erger, was dit 230 00:07:48,380 --> 00:07:52,490 hierdie interessante kurwe wat nie kry so sleg met verloop van tyd. 231 00:07:52,490 --> 00:07:53,910 So laat ons vashou aan hierdie idee. 232 00:07:53,910 --> 00:07:54,690 Kom ons dank Jennifer. 233 00:07:54,690 --> 00:07:56,150 Baie dankie vir die kom op up. 234 00:07:56,150 --> 00:07:57,400 En een sek. 235 00:07:57,400 --> 00:08:00,170 236 00:08:00,170 --> 00:08:02,925 Geen lessenaar lampe vandag, maar ons hoef CS50 stres balle. 237 00:08:02,925 --> 00:08:03,420 >> JENNIFER: Yay. 238 00:08:03,420 --> 00:08:04,410 >> David J. MALAN: Alle reg, hier. 239 00:08:04,410 --> 00:08:06,545 Dankie vir die aangaan die spanning hier. 240 00:08:06,545 --> 00:08:07,350 Alle regte. 241 00:08:07,350 --> 00:08:10,620 So laat ons kyk of ons kan nie nou formalisering van hierdie 'n bietjie meer. 242 00:08:10,620 --> 00:08:14,820 So weer, wat ons nou net gedoen het, was basies dieselfde ding as wat ons gedoen het 243 00:08:14,820 --> 00:08:16,660 in die eerste week. 244 00:08:16,660 --> 00:08:23,780 Maar eerder as die einde met net 'n lineêre algoritme, wat ons uitgebeeld 245 00:08:23,780 --> 00:08:27,210 voorheen as dit reguit lyn, waardeur, as ons sit nog een deur op 246 00:08:27,210 --> 00:08:29,610 die skerm, dan Jennifer sou gehad het om te kyk, potensieel, 247 00:08:29,610 --> 00:08:30,600 agter een deur. 248 00:08:30,600 --> 00:08:33,490 As ons nog twee deure, kan sy ' om te kyk agter twee deure. 249 00:08:33,490 --> 00:08:35,990 >> En so, was daar hierdie lineêre verhouding tussen die grootte van die 250 00:08:35,990 --> 00:08:39,059 probleem op, sê, die x-as, en die bedrag van die tyd wat dit neem om te 251 00:08:39,059 --> 00:08:40,440 los op die y. 252 00:08:40,440 --> 00:08:43,330 Maar die prentjie wat ek het verwys na vroeër was dit groen lyn. 253 00:08:43,330 --> 00:08:45,970 Groen doelbewus, omdat dit net beter gevoel. 254 00:08:45,970 --> 00:08:49,790 In teorie, die algoritme, toe ons dit gedoen het met die telefoon boek, wanneer ons dit gedoen het 255 00:08:49,790 --> 00:08:52,420 met julle tel mekaar, en in die tweede geval is, wanneer Jennifer net 256 00:08:52,420 --> 00:08:55,250 het dit hier, dit was soort fundamenteel beter. 257 00:08:55,250 --> 00:08:57,180 Want dit was nie net twee keer so vinnig. 258 00:08:57,180 --> 00:08:58,870 Dit was nie eens vier keer so vinnig. 259 00:08:58,870 --> 00:09:03,290 Dit was heeltemal afhanklik van wat die grootte van die insette was, oor hoeveel 260 00:09:03,290 --> 00:09:05,220 stappe om dit uiteindelik het. 261 00:09:05,220 --> 00:09:08,040 >> En so het hierdie eenvoudige idee dat ons almal het vanselfsprekend met die telefoon boek, 262 00:09:08,040 --> 00:09:10,200 Net so kan toegepas word om iets soos hierdie. 263 00:09:10,200 --> 00:09:12,380 En dit mag dalk meer ligtelik bekend as, as jy dalk 264 00:09:12,380 --> 00:09:13,940 dink, verdeel en oorwin. 265 00:09:13,940 --> 00:09:16,390 Nie in teenstelling met wat ons gedoen het, natuurlik, met die telefoon boek. 266 00:09:16,390 --> 00:09:18,300 >> Maar die pseudokode, onthou, was dit. 267 00:09:18,300 --> 00:09:21,800 So ons sal nie weer doen nie, maar onthou dat die eerste week, almal van ons het opgestaan 268 00:09:21,800 --> 00:09:25,140 en dan die helfte van julle sit, die helfte van jy sit die helfte van julle gaan sit. 269 00:09:25,140 --> 00:09:29,280 Dit algoritme is geïmplementeer in 'n bietjie van 'n kullery manier, in die sin dat dit 270 00:09:29,280 --> 00:09:32,870 net een van my is nie die tel, fundamenteel, meer doeltreffend. 271 00:09:32,870 --> 00:09:35,830 In daardie geval, ek was gebruik te maak 'n sekondêre bron. 272 00:09:35,830 --> 00:09:39,470 Soort, verskeie CPUs, verskeie brein, verskeie slim mense in die 273 00:09:39,470 --> 00:09:42,740 kamer was om my te help kry van iets lineêre na iets 274 00:09:42,740 --> 00:09:45,190 logaritmiese, van iets rooi na iets groen. 275 00:09:45,190 --> 00:09:48,650 >> Maar in hierdie geval, Jennifer alleen kan fundamenteel verbeter op die 276 00:09:48,650 --> 00:09:52,370 prestasie van haar eerste algoritme deur, weer, dink net 'n bietjie moeiliker. 277 00:09:52,370 --> 00:09:56,650 En nou, wanneer dit tyd is om te implementeer hierdie dinge, uitzoeken 278 00:09:56,650 --> 00:10:00,670 watter reëls van die kode wat jy kan skryf soos dat jy kan dit weer doen, en 279 00:10:00,670 --> 00:10:03,350 weer en weer, soort in 'n herhaling mode. 280 00:10:03,350 --> 00:10:06,370 Omdat jy nie gaan die te hê luukse, soos Jennifer het op die eerste, te 281 00:10:06,370 --> 00:10:10,460 net nog 'n hele klomp van die ifs en sê: hmm, as die eerste getal 4, 282 00:10:10,460 --> 00:10:11,800 laat my spring al die pad na die einde. 283 00:10:11,800 --> 00:10:14,180 Oe, as dat die getal is te groot, laat my arbitrêr terug te beweeg 284 00:10:14,180 --> 00:10:15,220 na die tweede element. 285 00:10:15,220 --> 00:10:18,210 Jy sal vind dat dit gaan 'n baie wees harder te formaliseer wat ons mense 286 00:10:18,210 --> 00:10:21,270 vanselfsprekend aanvaar as 'n baie redelike heuristiek nie, maar 'n rekenaar is slegs 287 00:10:21,270 --> 00:10:23,260 gaan om te doen wat dit wat jy vertel om te doen. 288 00:10:23,260 --> 00:10:25,280 >> Nou is dit het 'n baie interessante implikasies. 289 00:10:25,280 --> 00:10:29,950 Hierdie grafiek is 'n soort van bedoel om te sorteer oorweldig visueel, maar kennisgewing, waar 290 00:10:29,950 --> 00:10:32,230 is die reguit lyn in die grafiek? 291 00:10:32,230 --> 00:10:35,330 Waar is die lineêre grafiek wat ons noem n? 292 00:10:35,330 --> 00:10:37,580 Wel, dit is soort van die rigting van die onderkant van hierdie prentjie, reg? 293 00:10:37,580 --> 00:10:40,500 So al wat ons gedoen het, is ons het soort van ingezoomd uit na die x-as en die 294 00:10:40,500 --> 00:10:44,780 y-as om te probeer om 'n gevoel van wat om te kry ander vorme van boë lyk. 295 00:10:44,780 --> 00:10:47,760 >> En die besonderhede van die wiskundige uitdrukkings vandag sal nie so saak nie 296 00:10:47,760 --> 00:10:52,440 veel nie, maar sien dat daar is 'n baie algoritmes wat veel erger as 297 00:10:52,440 --> 00:10:53,470 iets wat lineêr. 298 00:10:53,470 --> 00:10:55,410 Inderdaad, in blokkies gesny n lyk baie sleg. 299 00:10:55,410 --> 00:10:58,400 2 na die n lyk baie sleg. n vierkant lyk baie sleg. 300 00:10:58,400 --> 00:11:01,630 En ons sal sien wat sommige van dié kan wees in werklikheid vandag. 301 00:11:01,630 --> 00:11:05,430 En log n voel nie so sleg nie, maar beter as n 'log basis 2 van n. 302 00:11:05,430 --> 00:11:08,080 Maar jy weet, sou dit selfs gewees het meer amazing as Jennifer, of as ons, 303 00:11:08,080 --> 00:11:12,910 dat die eerste week, het gekom met iets wat log van log van n. 304 00:11:12,910 --> 00:11:15,880 >> So met ander woorde, daar is hierdie hele reeks moontlike oplossings te 305 00:11:15,880 --> 00:11:18,570 probleme, maar selfs hier, kennisgewing wat gaan gebeur nie. 306 00:11:18,570 --> 00:11:22,910 Toe ek vergroot nie, na watter van hierdie krommes gaan blyk te wees die absolute 307 00:11:22,910 --> 00:11:26,630 ergste van die mense wat op die skerm nou? 308 00:11:26,630 --> 00:11:28,680 So n blokkies lyk mooi sleg op die oomblik nie. 309 00:11:28,680 --> 00:11:32,470 Maar as ons zoom uit en sien meer van die x-en y-as, wat gaan 310 00:11:32,470 --> 00:11:34,550 oorheers uiteindelik? 311 00:11:34,550 --> 00:11:37,120 So dit blyk eintlik dat 2 tot die n, en jy kan dit uit figuur net deur 312 00:11:37,120 --> 00:11:39,990 steek in sommige toenemend groot nommers, en jy sal sien dat 2 van die 313 00:11:39,990 --> 00:11:42,070 n, wel, kry groter veel vinniger. 314 00:11:42,070 --> 00:11:45,530 As ons regtig vergroot nie, na 'n 2 aan die n algoritme suig absoluut. 315 00:11:45,530 --> 00:11:48,170 Ek bedoel dit gaan neem nogal 'n bietjie van die tyd vir die 316 00:11:48,170 --> 00:11:49,460 rekenaar te kansellasies deur. 317 00:11:49,460 --> 00:11:52,500 >> Maar jy sal sien met verloop van tyd, veral met toekomstige probleem stelle en selfs 318 00:11:52,500 --> 00:11:55,600 finale projekte, is jou data stel kry groot, alles reg? 319 00:11:55,600 --> 00:11:58,300 Selfs in die eerste weergawe van Facebook, as die aantal vriende, en die 320 00:11:58,300 --> 00:12:01,840 aantal geregistreerde gebruikers het 'n groot, jy kan sorteer van die telefoon in en 321 00:12:01,840 --> 00:12:05,530 implementeer iets met lineêre soek, of 'n baie eenvoudige sortering 322 00:12:05,530 --> 00:12:07,030 algoritme, as ons vandag sien. 323 00:12:07,030 --> 00:12:09,280 Jy het om te begin dink harder en harder oor hierdie probleme. 324 00:12:09,280 --> 00:12:12,070 En die aard van die probleme plekke soos Facebook, en Google en Microsoft, 325 00:12:12,070 --> 00:12:16,350 en ander werk op juis hierdie soort van groot data soort van vrae 326 00:12:16,350 --> 00:12:18,530 toenemend hierdie dae. 327 00:12:18,530 --> 00:12:18,900 >> Alle regte. 328 00:12:18,900 --> 00:12:23,800 So Jennifer se sukses in die tweede algoritme, eerlik, sy het ongelooflik 329 00:12:23,800 --> 00:12:26,110 goed die eerste keer nie, maar laat se skryf dit soos geluk, sodat ons 330 00:12:26,110 --> 00:12:27,000 kan maak hierdie punt. 331 00:12:27,000 --> 00:12:30,970 In die tweede geval is, het sy 'n aged algoritme wat herhaal weer en 332 00:12:30,970 --> 00:12:34,670 weer, maar sy het vir toegestaan ​​'n sekere aanname dat ons toegelaat 333 00:12:34,670 --> 00:12:39,370 haar, maar sy uitgebuit 'n paar besonderhede oor die tweede keer dat sy nie die 334 00:12:39,370 --> 00:12:39,840 eerste keer. 335 00:12:39,840 --> 00:12:41,800 Wat was wat? 336 00:12:41,800 --> 00:12:43,050 >> Dat die lys is gesorteer. 337 00:12:43,050 --> 00:12:46,350 So gou as die lys gesorteer is ons beweer dat Jennifer was in staat om te doen 338 00:12:46,350 --> 00:12:47,480 fundamenteel beter. 339 00:12:47,480 --> 00:12:51,450 7 deure, ja, is dit nie interessant, maar dink dit is ons 7 miljoen deure. 340 00:12:51,450 --> 00:12:54,080 Teken van n gaan beslis baie, baie uit te voer 341 00:12:54,080 --> 00:12:55,610 vinniger in die lang termyn. 342 00:12:55,610 --> 00:12:58,880 Maar sy het die te hê deure gesorteer vir haar. 343 00:12:58,880 --> 00:13:02,320 Nou, ek het die vryheid om dit te doen vooraf op die rekenaar skerm 344 00:13:02,320 --> 00:13:05,160 hier, maar veronderstel dat Jennifer gehad het om te doen wat haarself? 345 00:13:05,160 --> 00:13:10,120 Veronderstel dat die deure in vraag verteenwoordig data in 'n databasis, of 346 00:13:10,120 --> 00:13:14,260 Vriende geregistreer vir Facebook, of enige webblaaie op die internet wat 347 00:13:14,260 --> 00:13:16,880 verskeie webwerwe dalk nodig na die indeks of soek oor. 348 00:13:16,880 --> 00:13:20,940 >> Veronderstel dat jy net 'n rou data stel en dit is links na jou toe, of na 349 00:13:20,940 --> 00:13:23,010 Jennifer dat sortering te doen? 350 00:13:23,010 --> 00:13:26,950 Dit, eerder, vereis dat ons antwoord Die vraag, wel, hoeveel tyd 351 00:13:26,950 --> 00:13:31,080 sou geneem het Jennifer, of selfs my hierdie syfers te sorteer in advance so 352 00:13:31,080 --> 00:13:32,680 dat sy kan neem voordeel van dit? 353 00:13:32,680 --> 00:13:32,880 Reg? 354 00:13:32,880 --> 00:13:36,620 Omdat die implikasie is natuurlik Indien dit my nogal 'n rukkie om te sorteer 355 00:13:36,620 --> 00:13:40,800 die nommers, wat die heck sorg dat jy kan 'n aantal soos 50 so vinnig vind, 356 00:13:40,800 --> 00:13:44,850 as in Jennifer se geval, as ons meer as oorweldig die bedrag van die totale tyd 357 00:13:44,850 --> 00:13:46,920 dit het deur sorteer dinge in advance? 358 00:13:46,920 --> 00:13:49,320 >> So kom ons kyk of ons nie die verf die prentjie hier. 359 00:13:49,320 --> 00:13:51,370 Ek het 'n hele klomp meer stres balle, as dit sal help 360 00:13:51,370 --> 00:13:52,270 breek die ys hier. 361 00:13:52,270 --> 00:13:55,690 En as jy nie omgee nie, ons het sewe vrywilliger - 362 00:13:55,690 --> 00:13:57,060 op, OK. 363 00:13:57,060 --> 00:13:57,240 Sjoe. 364 00:13:57,240 --> 00:13:59,250 Sodat ons nie hoef te spandeer op die lessenaar lampe, dit lyk. 365 00:13:59,250 --> 00:13:59,690 Alle regte. 366 00:13:59,690 --> 00:14:01,530 So hoe om jou twee in die voorkant. 367 00:14:01,530 --> 00:14:04,160 Hoe gaan jy twee ouens in die rug. 368 00:14:04,160 --> 00:14:04,870 So dit is vier. 369 00:14:04,870 --> 00:14:09,890 Hoe gaan jy in die voorkant vyf, ses en sewe. 370 00:14:09,890 --> 00:14:10,320 Reg daar. 371 00:14:10,320 --> 00:14:13,260 Jou vriend se wys jou uit, sodat jy die prys. 372 00:14:13,260 --> 00:14:13,700 >> Alle regte. 373 00:14:13,700 --> 00:14:14,410 Kom up. 374 00:14:14,410 --> 00:14:17,120 En waarom ons nie hê jy ouens kom hier. 375 00:14:17,120 --> 00:14:18,960 Ek gaan om te gee jy elke 'n nommer. 376 00:14:18,960 --> 00:14:22,150 En voort te gaan en reël self identies aan wat is 377 00:14:22,150 --> 00:14:25,180 uitgebeeld op die skerm. 378 00:14:25,180 --> 00:14:26,530 >> [INTERPOSING Voices] 379 00:14:26,530 --> 00:14:28,160 >> David J. MALAN: Oop, jammer. 380 00:14:28,160 --> 00:14:30,210 Fout. 381 00:14:30,210 --> 00:14:32,180 Alle regte. 382 00:14:32,180 --> 00:14:32,750 Wel, hier gaan ons. 383 00:14:32,750 --> 00:14:34,180 Nommer vyf. 384 00:14:34,180 --> 00:14:35,136 Nommer ses. 385 00:14:35,136 --> 00:14:37,770 Een, twee, drie, vier, vyf, ses, sewe. 386 00:14:37,770 --> 00:14:39,410 O, dit is moeilik. 387 00:14:39,410 --> 00:14:41,210 >> Spreker 2: Ek sal net 'n -. 388 00:14:41,210 --> 00:14:41,900 >> David J. Malan Goeie deal. 389 00:14:41,900 --> 00:14:43,130 Alle regte. 390 00:14:43,130 --> 00:14:44,611 Dankie vir jou deelname. 391 00:14:44,611 --> 00:14:47,200 >> [Applous] 392 00:14:47,200 --> 00:14:48,580 >> OK. 393 00:14:48,580 --> 00:14:48,860 Alle regte. 394 00:14:48,860 --> 00:14:51,970 So het ons vier, twee, ses, een, drie, sewe, vyf. 395 00:14:51,970 --> 00:14:56,010 Vervolmaak sodat ons sewe vrywilligers hier wat gelyk is in breedte aan die 396 00:14:56,010 --> 00:14:57,430 skikking wat ons speel met die vroeër. 397 00:14:57,430 --> 00:14:59,470 En ek het sewe vir redes wat sal net 398 00:14:59,470 --> 00:15:00,840 gerieflik in 'n bietjie. 399 00:15:00,840 --> 00:15:04,400 En ek gaan na die eerste stel voor dat ons sorteer hierdie sewe vrywilligers. 400 00:15:04,400 --> 00:15:06,786 As jy wil, in die eerste, hallo te sê al is. 401 00:15:06,786 --> 00:15:08,970 Aangesien dit gaan wees om 'n ongemaklike paar minute. 402 00:15:08,970 --> 00:15:10,370 Stel julself. 403 00:15:10,370 --> 00:15:10,980 >> GRACE: Hi, ek is Grace. 404 00:15:10,980 --> 00:15:14,190 Ek is 'n stage in Leverett House. 405 00:15:14,190 --> 00:15:14,620 >> BRANSON: Hi. 406 00:15:14,620 --> 00:15:15,620 Ek is Branson. 407 00:15:15,620 --> 00:15:16,920 Ek is 'n groentjie in sweis. 408 00:15:16,920 --> 00:15:19,755 409 00:15:19,755 --> 00:15:20,230 >> GABE: Hi. 410 00:15:20,230 --> 00:15:21,040 Ek is Gabe. 411 00:15:21,040 --> 00:15:22,300 Ek is 'n junior in Cabot. 412 00:15:22,300 --> 00:15:24,826 413 00:15:24,826 --> 00:15:25,980 >> NEIL: Ek is Neil. 414 00:15:25,980 --> 00:15:29,090 Ek is 'n groentjie in Matthews. 415 00:15:29,090 --> 00:15:29,550 >> JASON: Ek is Jason. 416 00:15:29,550 --> 00:15:32,816 Ek is 'n groentjie in Greenough. 417 00:15:32,816 --> 00:15:33,700 >> Mike: Ek is Mike. 418 00:15:33,700 --> 00:15:37,360 Ek is 'n groentjie in Grays. 419 00:15:37,360 --> 00:15:37,990 >> JESS: Ek is Jess. 420 00:15:37,990 --> 00:15:40,313 Ek is 'n stage in Leverett. 421 00:15:40,313 --> 00:15:41,300 >> David J. MALAN: Uitstekende. 422 00:15:41,300 --> 00:15:41,850 Alle regte. 423 00:15:41,850 --> 00:15:44,190 Wel, dankie aan al ons vrywilligers hier tot dusver. 424 00:15:44,190 --> 00:15:47,110 En die uitdaging aan hand gaan om te sorteer van hierdie ouens, maar dan 425 00:15:47,110 --> 00:15:50,250 Ons gaan 'n bietjie te dink hard oor hoe doeltreffend ons eintlik 426 00:15:50,250 --> 00:15:51,110 ingedeel. 427 00:15:51,110 --> 00:15:52,580 So laat ons eers probeer om hierdie. 428 00:15:52,580 --> 00:15:55,970 Julle kan mekaar se nommers net deur die plasing om die hoeke. 429 00:15:55,970 --> 00:15:59,380 Gaan voort en neem 'n paar sekondes, en soort self van die kleinste op die 430 00:15:59,380 --> 00:16:01,240 links na grootste op die regterkant. 431 00:16:01,240 --> 00:16:02,490 Gaan. 432 00:16:02,490 --> 00:16:07,010 433 00:16:07,010 --> 00:16:07,530 >> OK. 434 00:16:07,530 --> 00:16:08,030 Goed. 435 00:16:08,030 --> 00:16:09,370 Dit was regtig darn vinnig. 436 00:16:09,370 --> 00:16:14,040 Nou kan iemand hier, wat was die algoritme dat hierdie ouens toegepas? 437 00:16:14,040 --> 00:16:14,900 >> Spreker 1: minste tot die meeste. 438 00:16:14,900 --> 00:16:15,000 >> David J. MALAN: OK. 439 00:16:15,000 --> 00:16:18,070 Minste tot die meeste is regtig sorteer van die doel, maar ek is nie seker dit is 440 00:16:18,070 --> 00:16:18,890 regtig 'n algoritme. 441 00:16:18,890 --> 00:16:21,810 Minste tot die meeste nie vertel my stap-vir-stap wat om te doen. 442 00:16:21,810 --> 00:16:22,833 Ja? 443 00:16:22,833 --> 00:16:24,083 >> Spreker 1: [onhoorbaar] 444 00:16:24,083 --> 00:16:26,010 445 00:16:26,010 --> 00:16:26,280 >> David J. MALAN: OK. 446 00:16:26,280 --> 00:16:28,920 So as jy sien 'n persoon kleiner as jou nommer, dan skuif na 447 00:16:28,920 --> 00:16:29,680 die reg van hulle. 448 00:16:29,680 --> 00:16:32,800 So dit is nou om meer uitdrukkingsvolle meer soos 'n algoritme, omdat jy 449 00:16:32,800 --> 00:16:35,410 kan sê, as dit, dan is dit. 450 00:16:35,410 --> 00:16:37,050 So het ons 'n soort voorwaardelike bou. 451 00:16:37,050 --> 00:16:39,700 En hierdie ouens was dat 'n paar om te doen keer, want sommige van julle het 'n bietjie 452 00:16:39,700 --> 00:16:40,420 van 'n afstand. 453 00:16:40,420 --> 00:16:43,410 En daar was vermoedelik 'n soort van herhaling gaan aan in hul gedagtes. 454 00:16:43,410 --> 00:16:44,610 >> Maar laat ons probeer om daardie te formaliseer. 455 00:16:44,610 --> 00:16:47,540 As jy ouens kan weer terug hierdie reëling. 456 00:16:47,540 --> 00:16:50,650 Kom ons kyk of ons kan dit nie 'n formalisering bietjie, en dan vra die vraag, net 457 00:16:50,650 --> 00:16:51,580 hoe doeltreffend is dit? 458 00:16:51,580 --> 00:16:54,220 Natuurlik, wanneer ons dit doen, meer stadig, dit gaan voel so goed van 459 00:16:54,220 --> 00:16:57,210 'n algoritme, maar laat ons kyk of ons kan sit ons vingers op die presiese stappe. 460 00:16:57,210 --> 00:16:58,670 >> So julle twee ouens is vier en twee. 461 00:16:58,670 --> 00:17:01,020 Of jy reg of verkeerd om? 462 00:17:01,020 --> 00:17:01,900 Ooglopend verkeerd is. 463 00:17:01,900 --> 00:17:02,710 So het ons verruil. 464 00:17:02,710 --> 00:17:05,170 Nou gaan ek opsy te skuif hier en sê: 05:56. 465 00:17:05,170 --> 00:17:06,240 Is jy reg of verkeerd? 466 00:17:06,240 --> 00:17:06,599 >> GABE: Korrekte. 467 00:17:06,599 --> 00:17:07,180 >> David J. MALAN: Korrekte. 468 00:17:07,180 --> 00:17:08,300 Ses en een? 469 00:17:08,300 --> 00:17:08,609 Nee. 470 00:17:08,609 --> 00:17:09,630 Ruil. 471 00:17:09,630 --> 00:17:10,490 So dit is twee swaps. 472 00:17:10,490 --> 00:17:11,710 Ses en drie? 473 00:17:11,710 --> 00:17:11,980 Nee. 474 00:17:11,980 --> 00:17:13,000 Ruil. 475 00:17:13,000 --> 00:17:13,930 Ses en sewe? 476 00:17:13,930 --> 00:17:14,630 Lyk goed. 477 00:17:14,630 --> 00:17:15,396 Sewe en vyf? 478 00:17:15,396 --> 00:17:16,150 >> JESS: [onhoorbaar] 479 00:17:16,150 --> 00:17:17,089 >> David J. MALAN: OK, ruil. 480 00:17:17,089 --> 00:17:19,770 En gesorteer. 481 00:17:19,770 --> 00:17:19,980 Alle regte. 482 00:17:19,980 --> 00:17:21,440 So natuurlik nie, reg? 483 00:17:21,440 --> 00:17:22,470 So daar is meer aan die gang. 484 00:17:22,470 --> 00:17:24,920 Maar, inderdaad, hierdie ouens, selfs net instinktief. 485 00:17:24,920 --> 00:17:25,450 gehou beweeg. 486 00:17:25,450 --> 00:17:27,710 Hulle het net nie ophou nie, wanneer hulle reggestel een probleem. 487 00:17:27,710 --> 00:17:27,839 So. 488 00:17:27,839 --> 00:17:29,390 Trouens, ek gaan te hê dieselfde ding te doen. 489 00:17:29,390 --> 00:17:32,720 Ek gaan om te sorteer van rewind terug aan die begin van hierdie probleem, 490 00:17:32,720 --> 00:17:35,630 of die begin van hierdie reeks mense, laat ons begin bel hulle. 491 00:17:35,630 --> 00:17:38,366 >> En nou Wat moet my algoritme op die tweede pas wees? 492 00:17:38,366 --> 00:17:39,220 >> Spreker 1: Dieselfde ding. 493 00:17:39,220 --> 00:17:39,940 >> David J. MALAN: Dieselfde ding. 494 00:17:39,940 --> 00:17:41,460 En dit, ek begin te hou, reg? 495 00:17:41,460 --> 00:17:44,720 So gou as wat jy kan vind jouself doen dieselfde ding weer en weer, dit is 496 00:17:44,720 --> 00:17:47,890 meer soos 'n algoritme, en minder menslike instink. 497 00:17:47,890 --> 00:17:48,680 >> So nou, hier gaan ons weer. 498 00:17:48,680 --> 00:17:49,870 Twee en vier? 499 00:17:49,870 --> 00:17:50,220 No 500 00:17:50,220 --> 00:17:51,050 Vier en een? 501 00:17:51,050 --> 00:17:53,380 Ag, was daar wel 'n paar werk nog gedoen moet word. 502 00:17:53,380 --> 00:17:53,620 Vir drie en? 503 00:17:53,620 --> 00:17:54,572 Goed. 504 00:17:54,572 --> 00:17:56,000 Vier en ses? 505 00:17:56,000 --> 00:17:58,380 Ses en vyf? 506 00:17:58,380 --> 00:17:59,470 Ses en sewe? 507 00:17:59,470 --> 00:18:00,970 OK, nou, gedoen. 508 00:18:00,970 --> 00:18:01,550 OK, no. 509 00:18:01,550 --> 00:18:02,710 Ek het om terug te gaan. 510 00:18:02,710 --> 00:18:05,130 >> So nou, weer, is ons om dit te doen 'n bietjie meer doelbewus. 511 00:18:05,130 --> 00:18:08,700 En nou, is daar net een brein uitvoering van hierdie algoritme. 512 00:18:08,700 --> 00:18:10,290 Een CPU, as jy wil. 513 00:18:10,290 --> 00:18:13,090 En eerlik, dit is die enigste bron ons gaan om toegang te hê. 514 00:18:13,090 --> 00:18:16,280 En sodra ons terug gaan nie na 'n klavier en het iets soos C by ons 515 00:18:16,280 --> 00:18:19,600 beskikking, kan ons slegs die skryf van 'n program wat een ding doen op 'n tyd. 516 00:18:19,600 --> 00:18:22,900 Terwyl, hierdie ouens 'n oomblik gelede, het ons aged hul kollektiewe breinkrag 517 00:18:22,900 --> 00:18:24,180 soos jy ouens het in week nul. 518 00:18:24,180 --> 00:18:24,980 So laat ons hou om dit te doen. 519 00:18:24,980 --> 00:18:26,260 >> Twee en 'n mens. 520 00:18:26,260 --> 00:18:26,945 Twee en drie. 521 00:18:26,945 --> 00:18:27,460 Drie en vier. 522 00:18:27,460 --> 00:18:28,310 Vier en vyf. 523 00:18:28,310 --> 00:18:28,620 Vyf en ses. 524 00:18:28,620 --> 00:18:30,510 Ses en sewe. 525 00:18:30,510 --> 00:18:31,880 Gedoen? 526 00:18:31,880 --> 00:18:34,560 So ek is nie, maar laat my speel duiwel se advokaat. 527 00:18:34,560 --> 00:18:37,950 Doen ek, die soort van die rekenaar wat net het 'n slaagsyfer deur middel van hierdie reeks 528 00:18:37,950 --> 00:18:40,225 mense, weet dat ek gedoen het? 529 00:18:40,225 --> 00:18:40,670 >> Spreker 1: No 530 00:18:40,670 --> 00:18:41,050 >> David J. MALAN: So hoekom? 531 00:18:41,050 --> 00:18:46,900 Wat sou ek het om te doen ten einde te sluit beslissend dat ek gedoen? 532 00:18:46,900 --> 00:18:48,230 Waarskynlik een meer slaag. 533 00:18:48,230 --> 00:18:48,430 Reg? 534 00:18:48,430 --> 00:18:51,760 Want al wat ek weet van dat die vorige slaag, is dat ek 'n fout reggestel. 535 00:18:51,760 --> 00:18:53,920 En dit beteken, miskien is daar ' nog 'n fout 536 00:18:53,920 --> 00:18:54,840 wat ek nodig het om te herstel. 537 00:18:54,840 --> 00:18:58,680 So ek kan net seker wees deur omwikkelen, en dan nagaan, 1-2, twee-en- 538 00:18:58,680 --> 00:19:00,940 drie, drie en vier, vier en vyf, vyf en ses, ses en sewe. 539 00:19:00,940 --> 00:19:02,510 OK, nou het ek geen werk. 540 00:19:02,510 --> 00:19:05,990 >> Ek kan beslis onthou wat ek gedoen het nie werk met iets soos 'n veranderlike, 541 00:19:05,990 --> 00:19:06,975 graag 'n int. 542 00:19:06,975 --> 00:19:12,490 Noem dit swaps, en as swaps is 0 keer ek kry hier, en dit begin by 0, dan 543 00:19:12,490 --> 00:19:15,520 Ek wil net dom wees om aan te hou heen en weer, seker die weer, en 544 00:19:15,520 --> 00:19:16,450 weer en weer, reg? 545 00:19:16,450 --> 00:19:18,450 Omdat jy vassit in sommige soort van oneindige lus. 546 00:19:18,450 --> 00:19:21,250 So gou as daar is 0 swaps, ons kan beweer dat dit 547 00:19:21,250 --> 00:19:23,810 algoritme is inderdaad voltooi. 548 00:19:23,810 --> 00:19:25,400 >> Nou, laat ons 'n naam op hierdie punt. 549 00:19:25,400 --> 00:19:28,930 Die algoritme wat ek stel voor ons net geïmplementeer is iets genoem borrel 550 00:19:28,930 --> 00:19:32,800 soort, wat bekend staan ​​as sodanig in die sin dat die nommers wat groter soort 551 00:19:32,800 --> 00:19:37,990 borrel hul pad na die top, of tot aan die einde van die skikking van getalle. 552 00:19:37,990 --> 00:19:40,270 Maar hoe doeltreffend was hierdie algoritme? 553 00:19:40,270 --> 00:19:44,600 Hoeveel treë Ek het fisies in 'n neem, byvoorbeeld, om dit te sorteer 554 00:19:44,600 --> 00:19:45,850 sewe mense? 555 00:19:45,850 --> 00:19:48,560 556 00:19:48,560 --> 00:19:49,550 >> Vier tot vyf? 557 00:19:49,550 --> 00:19:51,420 OK, te veel is uiteindelik gaan die antwoord wees. 558 00:19:51,420 --> 00:19:54,960 Maar selfs dan, die spesifieke getal is nie so interessant. 559 00:19:54,960 --> 00:19:56,670 Kom ons veralgemeen dit as 'n. 560 00:19:56,670 --> 00:20:00,520 So as ek het n 'mense hier, en hulle was, soort van, in enige volgorde op die 561 00:20:00,520 --> 00:20:02,180 begin, in die oorspronklike bestelling. 562 00:20:02,180 --> 00:20:04,910 Wel, hoeveel stappe wat ek het te neem op die eerste slaag? 563 00:20:04,910 --> 00:20:09,810 Dit was een, twee, drie, vier, vyf, ses, en hulle is sewe mense, so 564 00:20:09,810 --> 00:20:13,670 Dit is sewe, ses -, so dit is n minus een stappe die eerste keer. 565 00:20:13,670 --> 00:20:16,280 >> Nou, hoeveel stappe wat ek het om te neem wanneer ek terug gespoeld? 566 00:20:16,280 --> 00:20:19,310 Wel, ons kan eintlik verdubbel dat indien Ons wou eintlik om nie, maar vir nou, is ek 567 00:20:19,310 --> 00:20:22,300 net gaan om te sê, alles reg, nog n minus 1. 568 00:20:22,300 --> 00:20:25,240 So die n minus 1 gaan kry irriterende tred te hou, so laat 569 00:20:25,240 --> 00:20:26,400 net om effens. 570 00:20:26,400 --> 00:20:27,770 So 2n stappe. 571 00:20:27,770 --> 00:20:29,310 So 14 stappe, gee of neem. 572 00:20:29,310 --> 00:20:31,930 >> Hoeveel keer het ek 'n stap om die volgende keer? 573 00:20:31,930 --> 00:20:33,740 Wel, dit is 3n. 574 00:20:33,740 --> 00:20:34,510 regtig. 575 00:20:34,510 --> 00:20:37,920 En nou, in die ergste geval, vir Byvoorbeeld, hoeveel keer het ek 576 00:20:37,920 --> 00:20:41,730 gegaan heen en weer, heen en weer, uitvoering van hierdie algoritme uitruiling 577 00:20:41,730 --> 00:20:44,620 mense op elke slaag, rofweg? 578 00:20:44,620 --> 00:20:47,720 579 00:20:47,720 --> 00:20:50,010 Dit is eintlik n 'vierkantig, reg? 580 00:20:50,010 --> 00:20:53,000 >> Want in die ergste geval, jy kan soort van dink oor hierdie intuïtief, 581 00:20:53,000 --> 00:20:54,800 selfs al is dit dalk 'n bietjie n bietjie van die tyd om te sink in 582 00:20:54,800 --> 00:20:57,590 In die ergste geval, wat sou hierdie sewe mense is gelyk, in 583 00:20:57,590 --> 00:21:00,230 terme van die ooreenkoms van hul getalle? 584 00:21:00,230 --> 00:21:01,460 Heeltemal agtertoe, reg? 585 00:21:01,460 --> 00:21:02,815 En net dat na te boots, wat was jou naam nou weer? 586 00:21:02,815 --> 00:21:03,360 >> Mike: Mike. 587 00:21:03,360 --> 00:21:03,640 >> David J. MALAN: Mike? 588 00:21:03,640 --> 00:21:08,100 OK, Mike, jy kan net saam met my oor hier vir net een sekonde? 589 00:21:08,100 --> 00:21:08,880 Eintlik nie. 590 00:21:08,880 --> 00:21:10,150 Jammer Mike, laat se rewind. 591 00:21:10,150 --> 00:21:10,910 Wat is jou naam nou weer? 592 00:21:10,910 --> 00:21:11,180 >> NEIL: Neil. 593 00:21:11,180 --> 00:21:11,640 >> David J. MALAN: Neil. 594 00:21:11,640 --> 00:21:13,750 OK, Neil, kom jy met my, as jy nie omgee nie. 595 00:21:13,750 --> 00:21:17,150 So ek gaan voor te stel, net vir eenvoud, wat Neil is nou in sy 596 00:21:17,150 --> 00:21:18,510 ergste moontlike geval. 597 00:21:18,510 --> 00:21:20,720 Maar onthou hoe ek geïmplementeer my algoritme. 598 00:21:20,720 --> 00:21:24,530 Ek vergelyk, vergelyk, vergelyk, vergelyk, vergelyk, o. 599 00:21:24,530 --> 00:21:26,640 Nou hierdie ouens is uit van orde, so ek los. 600 00:21:26,640 --> 00:21:27,980 So julle ouens ruil. 601 00:21:27,980 --> 00:21:31,630 Maar nou kyk, hoeveel verder nie Neil het om te gaan? 602 00:21:31,630 --> 00:21:32,690 Dit is min of meer n. 603 00:21:32,690 --> 00:21:33,570 Jy weet, is dit nie eintlik n. 604 00:21:33,570 --> 00:21:36,040 Dit is soos, n minus 1, maar ek kry vererg hou van die klein 605 00:21:36,040 --> 00:21:37,550 nommer, so laat ons noem dit net n. 606 00:21:37,550 --> 00:21:42,860 >> So as Neil beweeg 'n stap maksimaal elke tyd, en Neil n stap te beweeg, 607 00:21:42,860 --> 00:21:46,580 Ek het dit regtig vervelige pas te maak heen en weer, dit is ongeveer 608 00:21:46,580 --> 00:21:52,080 om dit te doen, n werk, 'n totaal van n keer, want dit gaan om my te neem 609 00:21:52,080 --> 00:21:55,820 dat baie stappe Neil almal te kry die pad na waar hy hoort. 610 00:21:55,820 --> 00:21:58,620 Laat staan ​​almal anders as jy ouens is almal mis-bestel as well. 611 00:21:58,620 --> 00:22:01,100 >> So kom ons noem borrel soort n vierkant. 612 00:22:01,100 --> 00:22:04,860 Die loop van die tyd van hierdie algoritme, die uitvoering van hierdie algoritme, die 613 00:22:04,860 --> 00:22:07,120 doeltreffendheid van hierdie algoritme ons sal net beskryf meer 614 00:22:07,120 --> 00:22:08,800 algemeen as n vierkant. 615 00:22:08,800 --> 00:22:11,650 Wat is lekker, want ek kon doen om die dieselfde voorbeeld met agt mense, nege 616 00:22:11,650 --> 00:22:15,450 mense, 'n miljoen mense, en dat antwoord is nie van plan te verander. 617 00:22:15,450 --> 00:22:18,870 >> So as jy ouens sal nie omgee, laat herstel jy na die plek waar jy begin het. 618 00:22:18,870 --> 00:22:22,510 En laat ons probeer om twee ander benaderings en kyk of ons kan dit nie doen nie fundamenteel 619 00:22:22,510 --> 00:22:23,820 beter as dit. 620 00:22:23,820 --> 00:22:27,130 So hierdie tyd, ek gaan voor te stel 'n soort van verskillende algoritme. 621 00:22:27,130 --> 00:22:29,950 Dit was baie slim van ons laaste tyd, en julle ouens was reg om die 622 00:22:29,950 --> 00:22:32,470 reg instink van net 'n soort van die uitruiling van paarsgewyse. 623 00:22:32,470 --> 00:22:36,500 Maar as ek regtig wou dit te benader eenvoudig, en my doel is om te beweeg 624 00:22:36,500 --> 00:22:39,800 al die klein getalle op hierdie manier, en druk al die groot getalle wat 625 00:22:39,800 --> 00:22:43,030 manier, hoekom nie ek doen net wat in die mees naïewe manier moontlik en kyk of ek 626 00:22:43,030 --> 00:22:45,730 beter kan doen as wat 'n redelik komplekse algoritme? 627 00:22:45,730 --> 00:22:46,620 >> So laat ons sien. 628 00:22:46,620 --> 00:22:48,940 Vier is 'n mooi klein aantal, so ek is gaan jy om daar te verlaat oomblik. 629 00:22:48,940 --> 00:22:50,610 Oe, nommer twee is nog beter. 630 00:22:50,610 --> 00:22:52,230 So kan jy net vorentoe te stap vir 'n oomblik? 631 00:22:52,230 --> 00:22:55,670 Dit is tans my kleinste getel kandidaat, en ek gaan om te onthou 632 00:22:55,670 --> 00:22:57,000 wat nie, soos 'n veranderlike. 633 00:22:57,000 --> 00:22:57,930 Maar Ek gaan om te hou keur. 634 00:22:57,930 --> 00:22:59,890 Is daar iemand wie se getal is kleiner? 635 00:22:59,890 --> 00:23:00,460 Ses, no. 636 00:23:00,460 --> 00:23:01,390 O ja, daar is Neil weer. 637 00:23:01,390 --> 00:23:04,050 >> So ek gaan om jou te stoot terug soort van konseptueel. 638 00:23:04,050 --> 00:23:05,120 Neil na vore sal kom. 639 00:23:05,120 --> 00:23:08,440 En nou, die veranderlike wat ek gebruik om te hou van wat die kleinste het 640 00:23:08,440 --> 00:23:11,390 getal word opgedateer te bevat Neil se plek. 641 00:23:11,390 --> 00:23:12,110 Wel, laat ons sien. 642 00:23:12,110 --> 00:23:13,960 Drie, sewe, vyf. 643 00:23:13,960 --> 00:23:15,590 OK, ek weet Neil was die kleinste. 644 00:23:15,590 --> 00:23:18,110 Wat is die eenvoudigste ding vir my nou te doen? 645 00:23:18,110 --> 00:23:21,410 Ek gaan nie my tyd te mors deur net borrel Neil een plek na links. 646 00:23:21,410 --> 00:23:25,350 Hoekom kan ek nie net sit Neil waar hy behoort, wat natuurlik waar? 647 00:23:25,350 --> 00:23:26,160 >> Al die pad aan die begin. 648 00:23:26,160 --> 00:23:27,720 So Neil, kom saam met my. 649 00:23:27,720 --> 00:23:28,910 En wat was jou naam nou weer? 650 00:23:28,910 --> 00:23:29,310 >> GRACE: Grace. 651 00:23:29,310 --> 00:23:29,710 >> David J. Malan Grace. 652 00:23:29,710 --> 00:23:29,920 OK. 653 00:23:29,920 --> 00:23:32,490 So Grace, ongelukkig, is jy soort in die pad. 654 00:23:32,490 --> 00:23:34,290 So hoe los ons die probleem? 655 00:23:34,290 --> 00:23:34,490 Reg? 656 00:23:34,490 --> 00:23:37,500 As dit is 'n skikking, is daar net sewe plekke. 657 00:23:37,500 --> 00:23:40,830 Onthou dat, met Rob, het ons gepraat oor verklaar ouderdomme, en ons het net 'n 658 00:23:40,830 --> 00:23:41,740 beperkte aantal ouderdomme? 659 00:23:41,740 --> 00:23:42,535 Dieselfde idee hier. 660 00:23:42,535 --> 00:23:44,300 Ons het net 'n beperkte aantal ints. 661 00:23:44,300 --> 00:23:47,590 Grace is 'n soort van in ons manier, so hoe ons dit regmaak? 662 00:23:47,590 --> 00:23:49,555 >> Die eenvoudigste manier is soos, Genade, jammer. 663 00:23:49,555 --> 00:23:51,870 Jy gaan hê om oor te gaan daar sodat ons kan vertrek. 664 00:23:51,870 --> 00:23:55,290 Nou, as jy dink oor hierdie, miskien Ons het net het die probleem vererger. 665 00:23:55,290 --> 00:23:58,510 En dalk het ons gedoen het nie, want wat as Grace was op die regte plek? 666 00:23:58,510 --> 00:24:01,730 Maar ons weet sy is nie, want Anders sou sy gewees het 667 00:24:01,730 --> 00:24:03,980 staan ​​vorentoe in plaas van Neil in hierdie tyd, reg? 668 00:24:03,980 --> 00:24:05,550 Ons het reeds nagegaan haar nommer. 669 00:24:05,550 --> 00:24:05,770 >> Alle regte. 670 00:24:05,770 --> 00:24:09,110 So nou, Neil is op die regte plek, en Ek kan dit doen 'n effense optimalisering. 671 00:24:09,110 --> 00:24:11,740 Vir die volgende minuut, ek gaan om te ignoreer Neil almal saam, sodat dit nie te 672 00:24:11,740 --> 00:24:15,280 mors sy tyd, of per ongeluk ruil hom na die verkeerde plek. 673 00:24:15,280 --> 00:24:17,805 So nou, hoe kan ek kry die volgende element wat is die kleinste? 674 00:24:17,805 --> 00:24:18,480 Twee. 675 00:24:18,480 --> 00:24:20,225 Dit is 'n goeie, indien jy wil om vorentoe te stap en 676 00:24:20,225 --> 00:24:21,100 Ek sal aan julle dink. 677 00:24:21,100 --> 00:24:21,980 Ses, nie goed nie. 678 00:24:21,980 --> 00:24:24,820 Vier, drie, sewe, vyf, nie goed nie. 679 00:24:24,820 --> 00:24:26,800 So laat my beweeg om jou te jou regte plek. 680 00:24:26,800 --> 00:24:28,470 En ons het net gelukkig hierdie tyd. 681 00:24:28,470 --> 00:24:31,350 >> Nou, ek gaan om dit te ignoreer twee ouens, en nou nog een 682 00:24:31,350 --> 00:24:32,260 slaag deur middel van hierdie. 683 00:24:32,260 --> 00:24:33,490 Ses, wat 'n mooi klein aantal. 684 00:24:33,490 --> 00:24:34,300 Kom vorentoe. 685 00:24:34,300 --> 00:24:35,220 O, jammer. 686 00:24:35,220 --> 00:24:37,640 Grace se nommer is beter, so stap op vorentoe. 687 00:24:37,640 --> 00:24:38,260 Vier. 688 00:24:38,260 --> 00:24:39,120 Jammer, Grace. 689 00:24:39,120 --> 00:24:39,950 Gaan weer terug. 690 00:24:39,950 --> 00:24:41,550 Nommer drie is beter. 691 00:24:41,550 --> 00:24:42,290 Sewe. 692 00:24:42,290 --> 00:24:42,720 Vyf. 693 00:24:42,720 --> 00:24:43,550 Maar nou, wat is jou naam nou weer? 694 00:24:43,550 --> 00:24:44,000 >> JASON: Jason. 695 00:24:44,000 --> 00:24:44,420 >> David J. MALAN: Jason. 696 00:24:44,420 --> 00:24:47,050 So Jason is nou die kleinste element Ek het gekies. 697 00:24:47,050 --> 00:24:49,160 Waar is hy gaan om te gaan? 698 00:24:49,160 --> 00:24:50,380 So waar ses is. 699 00:24:50,380 --> 00:24:51,210 En jou naam nou weer? 700 00:24:51,210 --> 00:24:51,710 >> GABE: Gabe. 701 00:24:51,710 --> 00:24:52,340 >> David J. MALAN: Gabe. 702 00:24:52,340 --> 00:24:53,220 Gabe is in die pad. 703 00:24:53,220 --> 00:24:54,640 Wat is die maklikste ding om te doen? 704 00:24:54,640 --> 00:24:58,390 Ruil die twee ouens en gaan voort. 705 00:24:58,390 --> 00:24:59,020 So laat ons nou sien. 706 00:24:59,020 --> 00:25:00,170 Wie is die kleinste? 707 00:25:00,170 --> 00:25:01,030 Vier. 708 00:25:01,030 --> 00:25:01,990 Laat my net 'n soort oneerlik. 709 00:25:01,990 --> 00:25:03,090 Vyf gaan wees om die kleinste. 710 00:25:03,090 --> 00:25:05,220 Ek soek die volgende, indien jy wil om te stap vorentoe, wat ek te doen het met 711 00:25:05,220 --> 00:25:06,820 hierdie ouens, met Gabe? 712 00:25:06,820 --> 00:25:08,450 Ruil weer. 713 00:25:08,450 --> 00:25:10,740 So nou, steeds effens buite orde. 714 00:25:10,740 --> 00:25:14,140 Ek het gevind Gabe tot die kleinste, so Ek pop hom uit, beweeg julle oor. 715 00:25:14,140 --> 00:25:15,190 En gedoen het. 716 00:25:15,190 --> 00:25:17,200 >> So antwoord is dieselfde. 717 00:25:17,200 --> 00:25:18,600 Die eindresultaat is dieselfde. 718 00:25:18,600 --> 00:25:22,730 Watter van hierdie twee algoritmes is beter? 719 00:25:22,730 --> 00:25:23,500 Die tweede een, het ek gehoor. 720 00:25:23,500 --> 00:25:24,252 Hoekom? 721 00:25:24,252 --> 00:25:25,900 >> SPREKER 3: Dit is n stappe [onhoorbaar]. 722 00:25:25,900 --> 00:25:27,600 >> David J. MALAN: Dis n stappe op die meeste. 723 00:25:27,600 --> 00:25:28,490 Interessant. 724 00:25:28,490 --> 00:25:30,610 So is dit al? 725 00:25:30,610 --> 00:25:33,630 So hoe het ek die kleinste element? 726 00:25:33,630 --> 00:25:37,060 Hoeveel stappe het ek het om te neem die vind van die kleinste element? 727 00:25:37,060 --> 00:25:39,220 Ek het 'n kyk al die pad aan die einde, reg? 728 00:25:39,220 --> 00:25:41,530 Want in die ergste geval, wat As Neil was hier? 729 00:25:41,530 --> 00:25:45,700 So net die vind van die kleinste element neem my n stappe, of n minus 1. 730 00:25:45,700 --> 00:25:46,100 Maar, OK. 731 00:25:46,100 --> 00:25:46,980 So los Neil. 732 00:25:46,980 --> 00:25:48,740 Onthou dat 'n minuut of wat gelede. 733 00:25:48,740 --> 00:25:51,680 >> Maar hoe het ek die volgende kleinste element? 734 00:25:51,680 --> 00:25:54,830 Dit is 'n minus 1, of n minus 2 werklik, van die aantal stappe. 735 00:25:54,830 --> 00:25:55,440 So OK. 736 00:25:55,440 --> 00:25:57,390 So ek het n 'minus 2. 737 00:25:57,390 --> 00:25:57,600 Alle regte. 738 00:25:57,600 --> 00:25:59,130 So wat voel 'n bietjie beter. 739 00:25:59,130 --> 00:25:59,730 Alle regte. 740 00:25:59,730 --> 00:26:03,270 Hoeveel treë die volgende keer nommer drie te vind? 741 00:26:03,270 --> 00:26:04,420 So n minus 4. 742 00:26:04,420 --> 00:26:07,670 So dit afneem, een minder stap op elke iterasie. 743 00:26:07,670 --> 00:26:08,740 So dit beteken beter voel, reg? 744 00:26:08,740 --> 00:26:13,450 As laaste tyd was dit ongeveer n keer n, hierdie keer is dit n minus 1, plus n minus 745 00:26:13,450 --> 00:26:16,500 2, plus n minus 3, plus n minus 4, dot, dot, dot. 746 00:26:16,500 --> 00:26:18,750 Maar as jy onthou van jou hoërskool handboeke, die klein oneerlik 747 00:26:18,750 --> 00:26:24,380 vel aan die agterkant wat formules, indien jy optel hierdie reeks van getalle, 748 00:26:24,380 --> 00:26:31,280 Wat is die totale aantal stappe gaan wees dat ek hier op te neem? 749 00:26:31,280 --> 00:26:36,580 >> Dit is een van daardie, soos, n minus 1 keer n, gedeel deur 2. 750 00:26:36,580 --> 00:26:39,040 So laat my sien as ek kan trek hierdie vir net 'n oomblik. 751 00:26:39,040 --> 00:26:42,230 En weer, ek is soort van afronding sommige getalle net om ons lewe eenvoudige, 752 00:26:42,230 --> 00:26:47,830 maar as ek reg onthou, is dit iets soos as Ek doen n minus 1 dinge, dan is n minus 753 00:26:47,830 --> 00:26:53,570 2, dan is n minus 3, dit is ongeveer iets soos hierdie meer as 2, en as ek 754 00:26:53,570 --> 00:26:55,510 vermenigvuldig dit uit, dis eintlik n vierkant. 755 00:26:55,510 --> 00:26:58,940 Dit is nie te goed voel. n minus n meer as 2. 756 00:26:58,940 --> 00:27:00,350 >> Maar hier is die ding. 757 00:27:00,350 --> 00:27:03,720 In rekenaar wetenskap, wanneer die probleme begin om te kry interessant is, is wanneer n 758 00:27:03,720 --> 00:27:04,700 regtig groot. 759 00:27:04,700 --> 00:27:08,110 En toe n regtig groot, wat van hierdie waardes gaan al te domineer 760 00:27:08,110 --> 00:27:09,750 van die ander? 761 00:27:09,750 --> 00:27:10,990 Dit is soort van die n vierkant, reg? 762 00:27:10,990 --> 00:27:13,340 Ja, deel deur 2 is redelik goed. 763 00:27:13,340 --> 00:27:16,740 Maar as jy praat oor die miljarde stukke van data, of triljoene 764 00:27:16,740 --> 00:27:18,700 stukke van data, OK, so jy is twee keer so vinnig. 765 00:27:18,700 --> 00:27:22,440 Maar wat regtig omgee as dat 'n groot aantal, As hierdie faktor is wat kry 766 00:27:22,440 --> 00:27:23,040 groter en groter. 767 00:27:23,040 --> 00:27:25,990 En seker maak dit meer van 'n verskil as hierdie man. 768 00:27:25,990 --> 00:27:29,120 So selfs al is jy ouens is reg, die tweede algoritme, sal ons noem dit 769 00:27:29,120 --> 00:27:32,970 seleksie soort, is, in die werklike wêreld, 'n bietjie vinniger potensieel, omdat ek 770 00:27:32,970 --> 00:27:35,360 neem minder en minder stappe elke keer. 771 00:27:35,360 --> 00:27:37,340 >> Dit is nie regtig fundamenteel vinniger. 772 00:27:37,340 --> 00:27:41,430 Want as ons eintlik speel hierdie uit vir groot waardes van n, aan die einde van 773 00:27:41,430 --> 00:27:44,750 die dag, vir groot genoeg N, dit is nog steeds gaan voel redelik stadig. 774 00:27:44,750 --> 00:27:46,770 Wel, laat my toe om een laaste pass op daardie. 775 00:27:46,770 --> 00:27:48,920 Dit is wat ek sou noem seleksie soort. 776 00:27:48,920 --> 00:27:51,040 Kan julle weer julle 'n laaste keer? 777 00:27:51,040 --> 00:27:53,550 En in die laaste geval, ek gaan iets voor te stel 778 00:27:53,550 --> 00:27:54,970 genoem voeg soort. 779 00:27:54,970 --> 00:27:57,470 Invoeging soort wese, konseptueel, 'n bietjie anders. 780 00:27:57,470 --> 00:28:00,980 >> Eerder as om heen en weer en kies die kleinste element, ek is 781 00:28:00,980 --> 00:28:05,030 net gaan om te gaan met elkeen van hierdie ouens soos ek hulle teëkom, en voeg 782 00:28:05,030 --> 00:28:06,850 hulle in hul korrekte plek. 783 00:28:06,850 --> 00:28:10,160 So ek is net gaan om te begin met Grace, en ek sien dat sy is nommer vier. 784 00:28:10,160 --> 00:28:11,720 Waar kom nommer vier behoort? 785 00:28:11,720 --> 00:28:14,940 Ek het nog nie begin sorteer enigiets, so ook die genade kry om net daar te bly. 786 00:28:14,940 --> 00:28:18,355 En nou gaan ek te eis, as jy kon neem 'n stap na regs, hierdie 787 00:28:18,355 --> 00:28:21,650 my gesorteer lys, dit is my ongesorteerde oorblywende lys. 788 00:28:21,650 --> 00:28:23,260 So nou is ek volgende gaan voort, En wat is jou naam nou weer? 789 00:28:23,260 --> 00:28:23,700 >> BRANSON: Branson. 790 00:28:23,700 --> 00:28:24,150 >> David J. MALAN: Branson. 791 00:28:24,150 --> 00:28:25,375 So Branson is nommer twee. 792 00:28:25,375 --> 00:28:27,490 So ek gaan om jou te neem uit vir 'n oomblik. 793 00:28:27,490 --> 00:28:30,940 En nou, waar jy behoort in hierdie reeks? 794 00:28:30,940 --> 00:28:32,360 So aan die regterkant van die genade. 795 00:28:32,360 --> 00:28:35,670 So weer, ons is soort van die maak van Grace doen 'n baie werk hier. 796 00:28:35,670 --> 00:28:37,290 Waar sit ons u? 797 00:28:37,290 --> 00:28:40,120 So ons gaan om jou te skuif na die links, en voeg Branson daar. 798 00:28:40,120 --> 00:28:41,680 Maar nou het ek beweer dat Julle is gedoen. 799 00:28:41,680 --> 00:28:43,240 Maar kennis, ek is nie die gebruik van ekstra ruimte. 800 00:28:43,240 --> 00:28:45,130 Dit is nog steeds 2 elemente hier, 5 hier. 801 00:28:45,130 --> 00:28:47,910 Totale verskeidenheid grootte is 7, so ek is nie verneuk, alles reg? 802 00:28:47,910 --> 00:28:51,950 >> So nou het ons, met Gabe hier, die nommer ses, waar val jy? 803 00:28:51,950 --> 00:28:52,650 Jy het gelukkig weer. 804 00:28:52,650 --> 00:28:53,820 So jy net daar bly. 805 00:28:53,820 --> 00:28:57,210 Net 'n effense stap na regs net om duidelik te maak dat jy gesorteer. 806 00:28:57,210 --> 00:29:00,520 En nou het ons Neil weer, die aantal een, waar jy gaan? 807 00:29:00,520 --> 00:29:03,540 En nou is waar ons sal begin om te sien dat hierdie algoritme, al op die eerste 808 00:29:03,540 --> 00:29:05,950 oogopslag, voel redelik slim, kyk Wat is die punt om te gebeur nie. 809 00:29:05,950 --> 00:29:07,370 As jy kon stap vorentoe. 810 00:29:07,370 --> 00:29:09,260 >> Waar wil ons Neil te sit? 811 00:29:09,260 --> 00:29:11,830 So natuurlik hier nie, so hoe kry ons Neil daar? 812 00:29:11,830 --> 00:29:12,970 Kom ons doen dit stap-vir-stap. 813 00:29:12,970 --> 00:29:15,620 Gabe, waar jy nodig het om te gaan? 814 00:29:15,620 --> 00:29:19,590 Yep, so neem 'n groot stap, of twee half-stappe te maak 815 00:29:19,590 --> 00:29:20,820 een stap daar. 816 00:29:20,820 --> 00:29:21,750 Grace, waar jy gaan? 817 00:29:21,750 --> 00:29:22,510 Goed. 818 00:29:22,510 --> 00:29:23,500 So 'n stap. 819 00:29:23,500 --> 00:29:24,960 En uiteindelik, Branson? 820 00:29:24,960 --> 00:29:25,460 Nog 'n stap. 821 00:29:25,460 --> 00:29:27,190 En nou kan ons sit Neil in plek. 822 00:29:27,190 --> 00:29:28,440 >> So nou, hierdie logika. 823 00:29:28,440 --> 00:29:32,420 Selfs al is ons nie verskuif Neil oor en oor en oor hom te sit 824 00:29:32,420 --> 00:29:36,420 waar hy gaan, in die ergste geval, die volgende getal ons mag teëkom kon 825 00:29:36,420 --> 00:29:42,220 die aantal, sê, was daar 'n aantal nul is, dan gaan ons almal om te skuif 826 00:29:42,220 --> 00:29:42,730 hierdie ouens. 827 00:29:42,730 --> 00:29:44,950 Veronderstel dat daar is 'n aantal, negatiewe een, dan het ons om te skuif 828 00:29:44,950 --> 00:29:46,080 al hierdie ouens. 829 00:29:46,080 --> 00:29:48,500 So ons is regtig net 'n soort van daarby die probleem om, soos wat ons is 830 00:29:48,500 --> 00:29:52,620 die oordrag van die koste van die keuringsproses so te voeg 831 00:29:52,620 --> 00:29:56,930 proses, soos wat julle het net rofweg n minus iets om te beweeg 832 00:29:56,930 --> 00:29:57,940 aantal stappe. 833 00:29:57,940 --> 00:30:01,200 En dat die getal van die stappe is slegs gaan te verhoog as ek kies meer getalle, 834 00:30:01,200 --> 00:30:04,730 As ek het om te hou stoot julle ouens terug, en weer, en weer terug. 835 00:30:04,730 --> 00:30:08,320 >> So het die hartseer ding is nou al hierdie algoritmes is n 'kwadraat. 836 00:30:08,320 --> 00:30:10,570 Kom ons gaan voort en te danke aan hierdie ouens, en sien hierdie 'n bietjie 837 00:30:10,570 --> 00:30:11,090 anders. 838 00:30:11,090 --> 00:30:12,312 Baie goed gedoen. 839 00:30:12,312 --> 00:30:14,120 >> [Applous] 840 00:30:14,120 --> 00:30:15,030 >> Alle regte. 841 00:30:15,030 --> 00:30:16,280 Daar gaan jy. 842 00:30:16,280 --> 00:30:18,390 843 00:30:18,390 --> 00:30:18,470 Dankie vir die - 844 00:30:18,470 --> 00:30:19,190 >> BRANSON: [onhoorbaar] hou die nommers. 845 00:30:19,190 --> 00:30:21,990 >> David J. MALAN: Nee, jy mag hou die getalle so goed. 846 00:30:21,990 --> 00:30:23,440 Alle regte. 847 00:30:23,440 --> 00:30:24,100 Mooi gedoen. 848 00:30:24,100 --> 00:30:25,300 Alle regte. 849 00:30:25,300 --> 00:30:30,510 So laat ons kyk of ons kan nou nie 'n opsomming vinniger en meer visueel, 850 00:30:30,510 --> 00:30:33,410 presies wat nou net gebeur hier soos volg. 851 00:30:33,410 --> 00:30:36,510 852 00:30:36,510 --> 00:30:38,770 Ek gaan om voort te gaan en trek Firefox. 853 00:30:38,770 --> 00:30:41,310 Ons sal verbind hierdie demonstrasie op die kursus se webblad. 854 00:30:41,310 --> 00:30:43,870 Java is 'n bietjie lastig om te werk in sommige blaaiers hierdie dae. 855 00:30:43,870 --> 00:30:46,760 So as jy speel met dit by die huis, besef jy dalk nodig Firefox te gebruik 856 00:30:46,760 --> 00:30:47,990 te kry om dit te werk. 857 00:30:47,990 --> 00:30:50,440 En wat gaan ek doen met hierdie demonstrasie is die volgende. 858 00:30:50,440 --> 00:30:54,875 >> Aan die onderkant, ek het 'n hele klomp van die opsies, insluitend 'n begin en 'n 859 00:30:54,875 --> 00:30:55,840 stop knoppie. 860 00:30:55,840 --> 00:30:59,450 Ook, as 'n eenkant, daar blyk te wees 'n fout in hierdie programme, waardeur jy 861 00:30:59,450 --> 00:31:03,720 kan nie eintlik sien die begin of stop knoppie tensy jy bevel of Alt 862 00:31:03,720 --> 00:31:06,560 plus en zoom in, wat vreemd wys jou meer knoppies. 863 00:31:06,560 --> 00:31:09,090 Dus net FYI as jy speel met hierdie by die huis. 864 00:31:09,090 --> 00:31:12,870 Nou gaan ek begin om te klik in net 'n oomblik na spesifiseer 'n vertraging van, 865 00:31:12,870 --> 00:31:16,810 soos, 200 millisekondes hier, net sodat ons kan sien wat gebeur. 866 00:31:16,810 --> 00:31:20,180 >> So ek beweer dat dit 'n visualisering van die eerste algoritme 867 00:31:20,180 --> 00:31:23,730 hierdie ouens het, borrel soort, waardeur Ons verruil mense paarsgewyse. 868 00:31:23,730 --> 00:31:27,490 Die sleutel insig van hierdie visualisering is dat die hoogte van die bars 869 00:31:27,490 --> 00:31:30,510 verteenwoordig die grootte van die getal. 870 00:31:30,510 --> 00:31:32,210 So die langer die bar, die Hoe groter die nommer. 871 00:31:32,210 --> 00:31:33,680 Korter die bar, kleiner die nommer. 872 00:31:33,680 --> 00:31:38,630 En as jy sien, gaan ons deur die eerste iterasie van hierdie algoritme 873 00:31:38,630 --> 00:31:42,620 uitruiling groot en klein getalle, sodat die klein getal kom eerste en 874 00:31:42,620 --> 00:31:44,280 die groot aantal gaan aan die regterkant. 875 00:31:44,280 --> 00:31:48,770 >> En so gou as wat ons kry aan die einde van verskeidenheid van baie meer as sewe nommers, ons is 876 00:31:48,770 --> 00:31:49,900 gaan om terug te gaan na die begin. 877 00:31:49,900 --> 00:31:51,140 En verwag dit. 878 00:31:51,140 --> 00:31:54,860 Op die ver links, is dat die outjie gaan om te wissel na die kant, en hierdie 879 00:31:54,860 --> 00:31:56,010 proses herhaal. 880 00:31:56,010 --> 00:31:59,450 Nou is hierdie visualisering kry vinnig vervelig, so laat my voort te gaan en te stop 881 00:31:59,450 --> 00:32:04,170 dit verander die vertraging iets veel vinniger net om nou te kry, 'n gevoel vir 882 00:32:04,170 --> 00:32:05,060 hierdie algoritme. 883 00:32:05,060 --> 00:32:07,840 >> So selfs al het ek het dit versnel, is dit soos die opgradering van my verwerker, koop 884 00:32:07,840 --> 00:32:08,580 'n nuwe rekenaar. 885 00:32:08,580 --> 00:32:12,980 Ek het fundamenteel nie verander nie my algoritme, maar jy kan wel sien meer 886 00:32:12,980 --> 00:32:16,800 duidelik as met die mens, dat die groot getalle borrel tot die top, 887 00:32:16,800 --> 00:32:20,900 en die klein getalle borrelende af na die bodem. 888 00:32:20,900 --> 00:32:22,390 En nou hierdie ding hier gesorteer. 889 00:32:22,390 --> 00:32:25,260 En as 'n eenkant, in die blokkies, is daar net 'n paar boekhouding daar te 890 00:32:25,260 --> 00:32:28,010 help tel hoeveel vergelykings, of hoeveel swaps het 891 00:32:28,010 --> 00:32:28,950 eintlik gedoen is. 892 00:32:28,950 --> 00:32:30,750 >> Wel, laat ons probeer om een ​​van die ander wat ons gesien het. 893 00:32:30,750 --> 00:32:37,116 Laat my op borrel soort hier, en laat my kies, en hierdie hele webblad 894 00:32:37,116 --> 00:32:38,936 is 'n bietjie karretjie. 895 00:32:38,936 --> 00:32:41,155 Kom ons aanvaar die risiko en dit loop weer. 896 00:32:41,155 --> 00:32:44,560 897 00:32:44,560 --> 00:32:45,030 Daar gaan ons. 898 00:32:45,030 --> 00:32:47,180 So laat ons doen seleksie soort. 899 00:32:47,180 --> 00:32:49,140 Ek weet nie hoekom die spyskaart verskyn daar. 900 00:32:49,140 --> 00:32:54,070 Kom ons zoom in wat op te los fout, dit verander na 50. 901 00:32:54,070 --> 00:32:56,020 Ag, laat ons werklik te doen wat baie vinniger. 902 00:32:56,020 --> 00:32:59,160 Vyf millisekondes of so, en begin nie. 903 00:32:59,160 --> 00:33:00,470 >> So dit is seleksie soort. 904 00:33:00,470 --> 00:33:03,070 So weer, dink oor wat ons gedoen het met die mense hier. 905 00:33:03,070 --> 00:33:08,490 Ons het deur die skikking en gekies die kleinste element weer 906 00:33:08,490 --> 00:33:09,250 en weer en weer. 907 00:33:09,250 --> 00:33:11,110 Nou moet ek sê dat nog baie sleg. 908 00:33:11,110 --> 00:33:15,010 Dit is nog steeds n 'vierkantig, gee of neem, maar dit was, in die werklike wêreld, 'n bietjie 909 00:33:15,010 --> 00:33:18,280 vinniger, want ek was inderdaad neem effens minder stappe elke keer. 910 00:33:18,280 --> 00:33:19,800 Maar ons is net praat wat? 911 00:33:19,800 --> 00:33:21,830 Miskien 40 of so bars hier? 912 00:33:21,830 --> 00:33:23,200 Ons praat nie 40 miljoen. 913 00:33:23,200 --> 00:33:27,430 So dit is nie heeltemal duidelik vir my dat was inderdaad 'n beduidende wins. 914 00:33:27,430 --> 00:33:32,530 >> Laat my trek, en verander ons derde algoritme, wat kies 915 00:33:32,530 --> 00:33:33,180 voeg soort. 916 00:33:33,180 --> 00:33:36,380 En nou is dit regtig karretjie omdat die spyskaart moet regtig nie daar. 917 00:33:36,380 --> 00:33:40,840 So nou gaan ons terug hier blaai en begin hierdie algoritme. 918 00:33:40,840 --> 00:33:43,270 Woep, begin en stop. 919 00:33:43,270 --> 00:33:47,160 So hierdie een soort het 'n mooi patroon om dit, waardeur ons weer 920 00:33:47,160 --> 00:33:50,240 invoeging van die mens, of in hierdie geval, die bars in 921 00:33:50,240 --> 00:33:52,620 hulle toepaslike plek. 922 00:33:52,620 --> 00:33:55,430 En dit is reeds gedoen voordat Ek het omgedraai. 923 00:33:55,430 --> 00:33:58,940 Maar hierdie een ook, in teorie, is nog steeds n 'kwadraat. 924 00:33:58,940 --> 00:34:01,430 >> So laat ons kyk of ons nie kan vat hierdie soos volg. 925 00:34:01,430 --> 00:34:04,750 Ek gaan om voort te gaan en net te gee ons soort van 'n gemeenskaplike manier van praat 926 00:34:04,750 --> 00:34:08,489 oor hierdie dinge, laat my voer net 'n bietjie van die notering hier. 927 00:34:08,489 --> 00:34:12,480 Jy oor om te sien iets genoem groot O, want dit is letterlik 'n groot 928 00:34:12,480 --> 00:34:16,320 O. En dit is 'n manier dat 'n rekenaar wetenskaplike of 'n wiskundige selfs gebruik 929 00:34:16,320 --> 00:34:19,230 die loop van die tyd om te beskryf van 'n paar algoritme. 930 00:34:19,230 --> 00:34:21,400 Hoeveel treë dit eintlik neem? 931 00:34:21,400 --> 00:34:25,080 >> Nou gaan ek myself verleentheid te stel met my handskrif hier in net 'n oomblik. 932 00:34:25,080 --> 00:34:29,020 Maar laat my gaan voort en sê dat dit sal groot O hier. 933 00:34:29,020 --> 00:34:33,610 En laat my voer een ander simbool, 'n kapitale omega. 934 00:34:33,610 --> 00:34:37,080 Omega gaan na die teenoorgestelde wees, wese, van die groot O. AANGESIEN groot O 935 00:34:37,080 --> 00:34:40,790 beteken, in die ergste geval, hoeveel tyd dalk 'n algoritme neem, in 936 00:34:40,790 --> 00:34:43,480 terme van n, is omega gaan wees hoeveel tyd kan dit 937 00:34:43,480 --> 00:34:45,409 neem in die beste geval. 938 00:34:45,409 --> 00:34:48,090 En ons sal sien wat ons bedoel met beste geval in net 'n oomblik. 939 00:34:48,090 --> 00:34:49,940 >> So laat ons begin iets eenvoudig. 940 00:34:49,940 --> 00:34:54,719 Laat my begin met 'n lineêre soek. 941 00:34:54,719 --> 00:34:55,679 So nie te sorteer. 942 00:34:55,679 --> 00:34:58,000 Ons sal noem dit lineêre soek. 943 00:34:58,000 --> 00:35:01,140 En nou, 'n bietjie tafel uit hierdie. 944 00:35:01,140 --> 00:35:06,600 En nou, in die geval van lineêre soek, In die ergste geval, hoeveel stappe is 945 00:35:06,600 --> 00:35:11,770 dit gaan my 'n te vind aantal arbitrêre keuse? 946 00:35:11,770 --> 00:35:14,540 En daar is 'n totale deure of n totale getalle. 947 00:35:14,540 --> 00:35:15,940 Ergste geval. 948 00:35:15,940 --> 00:35:18,800 Hoeveel treë ek gaan hê om te neem die getal 50 te vind in 'n verskeidenheid 949 00:35:18,800 --> 00:35:20,830 van n deure? 950 00:35:20,830 --> 00:35:21,410 En hoekom? 951 00:35:21,410 --> 00:35:23,680 Want dit kan wees om al die manier oor na die einde. 952 00:35:23,680 --> 00:35:27,120 So baie soos Jennifer ondervind, die nommer 50 was al die pad, so in 953 00:35:27,120 --> 00:35:30,760 die ergste geval lineêre soek is 'n groot O van n, sal ons sê. 954 00:35:30,760 --> 00:35:33,430 >> Wat van die beste geval, As jy regtig gelukkig? 955 00:35:33,430 --> 00:35:36,200 Dit is net gaan 'n stap te neem, of 'n konstante aantal stappe. 956 00:35:36,200 --> 00:35:37,830 So sal ons beskryf dat as 1. 957 00:35:37,830 --> 00:35:39,010 So, dit is redelik goed. 958 00:35:39,010 --> 00:35:41,210 Nou wat as ons het iets hou binêre soek? 959 00:35:41,210 --> 00:35:43,860 960 00:35:43,860 --> 00:35:47,846 So binêre soek, in die ergste geval het hoeveel tyd? 961 00:35:47,846 --> 00:35:49,250 >> [INTERPOSING Voices] 962 00:35:49,250 --> 00:35:51,310 >> David J. MALAN: So eintlik, ek hoor dit in 'n paar plekke. 963 00:35:51,310 --> 00:35:56,390 So dit is eintlik meld n, gee of neem, want as deel ons die lys in die helfte 964 00:35:56,390 --> 00:36:00,730 weer en weer en weer, ons is in staat om om uit te vind, uiteindelik, die waarde, 965 00:36:00,730 --> 00:36:04,750 As dit is daar, maar daar is 'n vangs. 966 00:36:04,750 --> 00:36:08,590 Wat is die veronderstelling dat ons moet vanselfsprekend aanvaar vir binêre soek? 967 00:36:08,590 --> 00:36:09,700 Dit moet uitgesorteer. 968 00:36:09,700 --> 00:36:12,770 Dit is nie uitgesorteer is, kan jy verdeel die ding in die helfte weer en weer, en jy 969 00:36:12,770 --> 00:36:15,490 kan gaan verlaat, en jy kan reg gaan, en jy kan gaan links en regs, maar jy 970 00:36:15,490 --> 00:36:18,070 gaan nie die element as om uit te vind Die lys is nie gesorteer, want 971 00:36:18,070 --> 00:36:18,790 jy mag misloop nie. 972 00:36:18,790 --> 00:36:22,120 Omdat jou heuristiese, want na links of regs gaan word gebrekkig as dit 973 00:36:22,120 --> 00:36:23,420 inderdaad nie gesorteer. 974 00:36:23,420 --> 00:36:26,110 So daar is soort van 'n versteekte koste om die gebruik van iets soos hierdie. 975 00:36:26,110 --> 00:36:29,250 >> Nou, laat ons gaan in ons sortering algoritmes soek nie - 976 00:36:29,250 --> 00:36:31,140 Ag, eintlik laat ons gaan in hierdie leeg. 977 00:36:31,140 --> 00:36:33,190 Binêre soek in die beste geval? 978 00:36:33,190 --> 00:36:36,290 Dit is ook 1 as dit net gebeur om te wees in die baie middel van die skikking, of 979 00:36:36,290 --> 00:36:37,810 die middel van die telefoon boek. 980 00:36:37,810 --> 00:36:39,710 Nou kom ons doen borrel soort. 981 00:36:39,710 --> 00:36:42,570 So weer, nou is ons die aanvang van die soorte, nie die navrae. 982 00:36:42,570 --> 00:36:47,220 >> In die ergste geval, hoeveel stappe gedoen het wat ons eis borrel soort gaan neem? 983 00:36:47,220 --> 00:36:48,410 n vierkant. 984 00:36:48,410 --> 00:36:49,200 So ek gaan dit te trek. 985 00:36:49,200 --> 00:36:51,710 Ooh, my handskrif lyk nog erger wanneer dit geprojekteer dat groot. 986 00:36:51,710 --> 00:36:52,510 Alle regte. 987 00:36:52,510 --> 00:36:53,570 Sodat se N-kwadraat. 988 00:36:53,570 --> 00:36:59,460 En in die beste geval van borrel soort, hoeveel stappe gaan dit neem? 989 00:36:59,460 --> 00:37:00,980 1, het ek gehoor. 990 00:37:00,980 --> 00:37:01,760 >> Spreker 1: n. 991 00:37:01,760 --> 00:37:03,286 >> David J. MALAN: n, hoor ek. 992 00:37:03,286 --> 00:37:04,200 >> Spreker 1: 2. 993 00:37:04,200 --> 00:37:05,010 >> David J. MALAN: 2, hoor ek. 994 00:37:05,010 --> 00:37:06,670 Hoor ek 3? 995 00:37:06,670 --> 00:37:07,080 Alle regte. 996 00:37:07,080 --> 00:37:11,390 So ek het gehoor 1, n, 2, maar laat haal uitmekaar ten minste die eerste van daardie 997 00:37:11,390 --> 00:37:12,330 voorstelle, 1. 998 00:37:12,330 --> 00:37:15,370 Dit is nie 'n slegte instink, want dit soort volg 'n patroon hier. 999 00:37:15,370 --> 00:37:19,670 Maar as dit neem net 1 stap, hoe om in die wêreld kan ek sê dat die lys 1000 00:37:19,670 --> 00:37:22,900 gesorteer is, want as ek net toegelaat 1 stap, hoeveel elemente te neem 1001 00:37:22,900 --> 00:37:25,230 Ek kon eintlik gaan om seker te wees? 1002 00:37:25,230 --> 00:37:28,270 Wel, net 1, wat beteken daar is 'n minus 1 elemente wat kan wees uit 1003 00:37:28,270 --> 00:37:31,310 orde, en ek gaan net op geloof na op soek na 1 element wat die 1004 00:37:31,310 --> 00:37:31,850 ding is gesorteer. 1005 00:37:31,850 --> 00:37:33,930 So 1 is nie hier los. 1006 00:37:33,930 --> 00:37:35,710 So minimaal, hoeveel het ek om te sien? 1007 00:37:35,710 --> 00:37:36,680 >> [INTERPOSING Voices] 1008 00:37:36,680 --> 00:37:40,160 >> David J. Malan n minus 1, of werklik, n, want ek nodig het om te kyk na elke 1009 00:37:40,160 --> 00:37:42,190 element om seker te maak dat dit is nie buite orde. 1010 00:37:42,190 --> 00:37:44,750 Maar weereens, sal ons die soort van golf ons hande op die kleiner getalle en 1011 00:37:44,750 --> 00:37:47,100 aanvaar dat, as n groot kry, hulle is oninteressant in elk geval. 1012 00:37:47,100 --> 00:37:48,380 So dit is borrel soort. 1013 00:37:48,380 --> 00:37:49,830 En nou, laat ons doen hierdie laaste twee. 1014 00:37:49,830 --> 00:37:53,520 Seleksie soort, en dan sal ons doen voeg soort. 1015 00:37:53,520 --> 00:37:57,160 En dan sal ons blaas jou gedagtes met iets veel 1016 00:37:57,160 --> 00:37:58,926 beter as al hierdie. 1017 00:37:58,926 --> 00:38:00,410 Alle regte. 1018 00:38:00,410 --> 00:38:04,700 >> Wat is die ergste geval loop tyd van seleksie soort? 1019 00:38:04,700 --> 00:38:05,680 >> SPREKER 4: n vierkant. 1020 00:38:05,680 --> 00:38:06,710 >> David J. Malan n vierkant, ek hoor. 1021 00:38:06,710 --> 00:38:09,790 Maar hoekom n vierkant, intuïtief? 1022 00:38:09,790 --> 00:38:11,170 >> SPREKER 4: Omdat ons net dit gedoen het. 1023 00:38:11,170 --> 00:38:12,260 >> David J. MALAN: Omdat ons net dit gedoen het. 1024 00:38:12,260 --> 00:38:12,550 OK. 1025 00:38:12,550 --> 00:38:13,380 Goeie antwoord. 1026 00:38:13,380 --> 00:38:16,660 Maar intuïtief, is die rede waarom seleksie sorteer n vierkant? 1027 00:38:16,660 --> 00:38:18,980 Wat het ons te doen het weer en weer? 1028 00:38:18,980 --> 00:38:22,570 Ons het om te hou die skandering deur, is jy die kleinste, is jy die 1029 00:38:22,570 --> 00:38:24,020 kleinste, is jy die kleinste. 1030 00:38:24,020 --> 00:38:27,480 En toegestaan ​​is, het ons in staat was om n te neem stappe te doen, dan is n minus 1, dan is n minus 2. 1031 00:38:27,480 --> 00:38:30,700 Maar as jy soort voeg diegene wat al op, of neem dit op die geloof wat ek het bygevoeg 1032 00:38:30,700 --> 00:38:34,810 hulle in advance, kry ons ongeveer n vierkante minus 'n paar kleiner getalle. 1033 00:38:34,810 --> 00:38:36,730 So ek gaan om te noem dit 'n vierkant. 1034 00:38:36,730 --> 00:38:39,530 Maar met die seleksie soort in die beste geval, hoeveel stappe is dit 1035 00:38:39,530 --> 00:38:40,632 gaan om my te neem? 1036 00:38:40,632 --> 00:38:41,840 >> SPREKER 5: [onhoorbaar] 1037 00:38:41,840 --> 00:38:44,350 >> David J. MALAN: Dis ongelukkig nog steeds n vierkant, reg? 1038 00:38:44,350 --> 00:38:49,590 Want as ek die kies van die kleinste element, en ons het sewe mense hier, 1039 00:38:49,590 --> 00:38:53,280 Ek weet net, wanneer ek na die heel einde, wat ek gevind het die kleinste 1040 00:38:53,280 --> 00:38:55,670 nommer, waar hy of sy mag gewees het. 1041 00:38:55,670 --> 00:38:58,820 Maar hoe kry ek die volgende kleinste getal? 1042 00:38:58,820 --> 00:39:00,160 Ek het 'n ander pas om te doen. 1043 00:39:00,160 --> 00:39:04,810 So in die beste geval, wat is die insette te seleksie soort? 1044 00:39:04,810 --> 00:39:07,830 Dit is 'n reeds soort lys, nommer een, nommer twee, nommer drie, nommer vier. 1045 00:39:07,830 --> 00:39:08,600 Maar ek is 'n rekenaar. 1046 00:39:08,600 --> 00:39:10,190 Ek kan net kyk na een ding op 'n slag. 1047 00:39:10,190 --> 00:39:12,465 Ek kan nie uitsorteer van 'n stap terug soos 'n mens en sê: 1048 00:39:12,465 --> 00:39:14,030 ooh, dit lyk reg. 1049 00:39:14,030 --> 00:39:17,580 >> Ek kan net beoordeel korrektheid in seleksie soort deur die kies van die 1050 00:39:17,580 --> 00:39:18,370 kleinste getal. 1051 00:39:18,370 --> 00:39:21,390 Maar selfs as ek 'n nommer een eerste, As ek weet nie iets anders oor 1052 00:39:21,390 --> 00:39:24,460 die ander getalle, wat ek doen nie, al wat ek weet dat ek 'n skikking ingehandig 1053 00:39:24,460 --> 00:39:27,930 of 'n stel van die deure agter wat getalle, is die enigste manier wat ek weet dat 'n mens 1054 00:39:27,930 --> 00:39:28,680 was die kleinste? 1055 00:39:28,680 --> 00:39:32,440 As ek al die pad hier en besef, Damn, een was inderdaad die kleinste. 1056 00:39:32,440 --> 00:39:34,870 >> Maar hoe bepaal ek dan dat twee is die volgende kleinste? 1057 00:39:34,870 --> 00:39:38,350 Deur dit te doen dieselfde ondoeltreffendheid weer en weer. 1058 00:39:38,350 --> 00:39:42,210 So uiteindelik, met inplaas soort, hoe, in die ergste geval, 1059 00:39:42,210 --> 00:39:44,990 het, sê ons dit doen? 1060 00:39:44,990 --> 00:39:49,100 Dit het ook 'n 'kwadraat. 1061 00:39:49,100 --> 00:39:53,020 En hoe oor met die beste geval? 1062 00:39:53,020 --> 00:39:56,282 Ons sal laat dit as 'n fotonische lewe. 1063 00:39:56,282 --> 00:40:00,090 Ons sal vul dat leë volgende keer, maar laat my eers voor dat ons 1064 00:40:00,090 --> 00:40:02,620 fundamenteel beter doen as al hierdie, al reg? 1065 00:40:02,620 --> 00:40:05,220 >> So dink vir jouself wat inplanting soort gaan wees. 1066 00:40:05,220 --> 00:40:06,910 Wel, dit was nie baie dramatiese, want ek is die enigste een 1067 00:40:06,910 --> 00:40:08,970 wat het die verandering. 1068 00:40:08,970 --> 00:40:09,620 Sjoe. 1069 00:40:09,620 --> 00:40:10,420 OK. 1070 00:40:10,420 --> 00:40:12,615 So hier het ons 'n ietwat verskillende demonstrasie. 1071 00:40:12,615 --> 00:40:16,580 As ek zoom in hier, sal jy sien dat op die linker ons borrel soort, in die 1072 00:40:16,580 --> 00:40:20,740 Midde ons seleksie soort, en op die heel regs, ons het iets wat ons 1073 00:40:20,740 --> 00:40:23,380 het nie gekyk na nog genoem saamsmelt soort. 1074 00:40:23,380 --> 00:40:26,080 Maar kyk wat ons het al hier tot dusver vandag. 1075 00:40:26,080 --> 00:40:29,200 Wanneer Jennifer eerste keer op die verhoog, ons het in die skikking van getalle 1076 00:40:29,200 --> 00:40:33,750 weer en weer, met lineêre soek, en ons het lineêre loop van die tyd, 'n groot O 1077 00:40:33,750 --> 00:40:35,100 van N, om so te spreek. 1078 00:40:35,100 --> 00:40:41,000 >> As ons nou kyk na die eerste week van klas, toe ons verdeel en heers, 1079 00:40:41,000 --> 00:40:43,740 en ons het die telefoon boek skeur, en Jennifer, en ons gesamentlik 1080 00:40:43,740 --> 00:40:47,500 aged dat die sleutel insig, wat was om te herhaal jouself weer en weer deur 1081 00:40:47,500 --> 00:40:50,930 een of ander manier weg te gooi, gooi weg, weg te gooi, die helfte van die probleem, of 1082 00:40:50,930 --> 00:40:55,320 oor die algemeen, die verdeling van 'n probleem in die helfte, en dan die behandeling van die kleiner stuk 1083 00:40:55,320 --> 00:40:59,630 die probleem as konseptueel ekwivalent aan die ander kant, het ons een of ander manier het 1084 00:40:59,630 --> 00:41:00,910 fundamenteel beter. 1085 00:41:00,910 --> 00:41:04,720 Maar met borrel soort, met seleksie soort, met inplaas soort, het ons kan 1086 00:41:04,720 --> 00:41:06,560 geen sodanige insigte wat Jennifer het. 1087 00:41:06,560 --> 00:41:10,220 Ons pretty much net gestap terug en weer 'n hele klomp van die tye, en ons 1088 00:41:10,220 --> 00:41:12,650 tweaked dinge 'n bietjie, uitruiling in hierdie volgorde, miskien 1089 00:41:12,650 --> 00:41:13,730 voeg of te kies. 1090 00:41:13,730 --> 00:41:16,950 Maar aan die einde van die dag, ek het 'n baie ongemaklike loop heen en weer. 1091 00:41:16,950 --> 00:41:21,160 Ons het nie regtig iets hefboom smart soos Jennifer het, soos die verdeling 1092 00:41:21,160 --> 00:41:22,040 en verower. 1093 00:41:22,040 --> 00:41:25,620 >> So saamsmelt soort, daarenteen, wat ons sal sien nie tot volgende week, gaan dit 1094 00:41:25,620 --> 00:41:29,540 om die invloed wat die sleutel idee deur die verdeling die insette, en dan te halveer, en dan 1095 00:41:29,540 --> 00:41:30,580 halveer, en dan te halveer. 1096 00:41:30,580 --> 00:41:34,590 En op elke iterasie van die lus, sorteer die linker helfte, en die reg 1097 00:41:34,590 --> 00:41:38,200 helfte, dan is die linker helfte van die linker helfte, en die reg om die helfte van die links, dan 1098 00:41:38,200 --> 00:41:40,990 die linker helfte van die reg om die helfte, en die reg om die helfte van die reg om die helfte. 1099 00:41:40,990 --> 00:41:42,840 En herhaal weer en weer. 1100 00:41:42,840 --> 00:41:46,170 >> So, sien jy hierdie visueel, maar dit is wat op ons wag volgende week. 1101 00:41:46,170 --> 00:41:49,760 En in die algemeen, wanneer ons dink 'n bietjie bietjie harder op enige sodanige probleem. 1102 00:41:49,760 --> 00:41:52,435 1103 00:41:52,435 --> 00:41:57,970 Ons het n 'vierkantig aan die linkerkant, n vierkantig in die middel, en n 1104 00:41:57,970 --> 00:41:59,400 teken N op die regterkant. 1105 00:41:59,400 --> 00:42:00,590 So daar is jou regte fotonische lewe. 1106 00:42:00,590 --> 00:42:02,040 Ons sal sien dat jy op Maandag. 1107 00:42:02,040 --> 00:42:05,163 >> [Applous]