1 00:00:00,000 --> 00:00:11,270 2 00:00:11,270 --> 00:00:14,910 >> Spreker: Alle reg, dit is CS50. 3 00:00:14,910 --> 00:00:19,020 Dit is die einde van die week, drie, en as jy nie gebruik reeds 4 00:00:19,020 --> 00:00:21,790 weet dat daar sal middagete wees Vrydag soos gewoonlik, waar 5 00:00:21,790 --> 00:00:25,430 jy kan 'n goeie gesprek geniet en kos by Vuur en ys 6 00:00:25,430 --> 00:00:27,980 met 'n paar van die CS50 se personeel en klasmaats. 7 00:00:27,980 --> 00:00:30,170 Kop aan hierdie URL hier. 8 00:00:30,170 --> 00:00:33,420 >> Nou kan jy onthou, of jy kan binnekort bekend wees met, 9 00:00:33,420 --> 00:00:35,970 hierdie dinge hier, wat word aan die einde 10 00:00:35,970 --> 00:00:37,850 van die semester vir baie klasse. 11 00:00:37,850 --> 00:00:40,870 Sogenaamde eksamen blou boeke, waarin jy skryf jou antwoorde op eksamens. 12 00:00:40,870 --> 00:00:44,240 Nou het ek hier 26 sulke blou boeke, op elkeen van hulle 13 00:00:44,240 --> 00:00:47,580 is geskryf om 'n naam, 'n deur Z. En inderdaad die name is so eenvoudig, 'n 14 00:00:47,580 --> 00:00:50,490 deur Z. En een van die doelwitte aan die hand vandag 15 00:00:50,490 --> 00:00:53,910 gaan wees om voort te gaan wat ons begin op Maandag, wat nie 16 00:00:53,910 --> 00:00:57,830 soveel op soek na kode, maar eintlik op soek na idees en probleemoplossing. 17 00:00:57,830 --> 00:01:00,170 Een van die doelwitte en beloftes van hierdie kursus 18 00:01:00,170 --> 00:01:02,985 is om jou te leer om meer te dink versigtig, meer metodies, 19 00:01:02,985 --> 00:01:05,400 en probleme meer doeltreffend op te los. 20 00:01:05,400 --> 00:01:09,526 En inderdaad, kan ons doen wat werklik selfs sonder aanraking van 'n reël van die kode. 21 00:01:09,526 --> 00:01:12,150 So ek het 'n paar van die olifante tot vandag hier, oranje en blou, 22 00:01:12,150 --> 00:01:15,780 As ons een vrywilliger kry, miskien uit verder terug as gewoonlik. 23 00:01:15,780 --> 00:01:18,070 Hoe gaan net daar, kom neer. 24 00:01:18,070 --> 00:01:24,180 Die doel van die wat gaan wees om te help plus administreer die eksamen hier. 25 00:01:24,180 --> 00:01:24,935 Wat is jou naam? 26 00:01:24,935 --> 00:01:25,768 >> Publiek: Mary Beth. 27 00:01:25,768 --> 00:01:27,560 Spreker: Mary Beth, kom op. 28 00:01:27,560 --> 00:01:29,560 Laat my die mikrofoon hier vir jou. 29 00:01:29,560 --> 00:01:32,172 30 00:01:32,172 --> 00:01:32,880 Nice om jou te ontmoet. 31 00:01:32,880 --> 00:01:34,005 >> Publiek: Nice om jou te ontmoet. 32 00:01:34,005 --> 00:01:36,790 Spreker: Alle reg, so ek het hier blou boeke 'n deur Z, 33 00:01:36,790 --> 00:01:41,680 en ek gaan om voor te gee Ek het een van die studente, 34 00:01:41,680 --> 00:01:45,770 en hulle kom in ietwat lukraak aan die einde van 'n drie-uur eksamen blok, 35 00:01:45,770 --> 00:01:49,400 sodat hulle eindig in sommige semi-ewekansige volgorde soos hierdie. 36 00:01:49,400 --> 00:01:54,510 Nou jou werk in net 'n oomblik gaan te be-- dit is eintlik hoe hulle kry 37 00:01:54,510 --> 00:01:56,820 het aan die einde van die klas, waarskynlik. 38 00:01:56,820 --> 00:02:01,120 Jou werk is nou gaan wees, heel eenvoudig, hierdie blou boeke vir ons om te sorteer 39 00:02:01,120 --> 00:02:05,220 van 'n deur Z. 40 00:02:05,220 --> 00:02:08,400 >> Publiek: O, dit is vir ewig gaan neem. 41 00:02:08,400 --> 00:02:13,747 >> Spreker: En ons sal sien as jy dit doen, geen druk. 42 00:02:13,747 --> 00:02:15,330 Publiek: Nee, geen druk of iets nie. 43 00:02:15,330 --> 00:02:19,230 44 00:02:19,230 --> 00:02:23,570 >> Spreker: En vir die pret, Kom ons stel 'n timer. 45 00:02:23,570 --> 00:02:26,680 46 00:02:26,680 --> 00:02:28,700 >> Publiek: Soveel pret, soveel pret. 47 00:02:28,700 --> 00:02:36,741 48 00:02:36,741 --> 00:02:38,574 >> Spreker: Ek kan die mic hou vir jou. 49 00:02:38,574 --> 00:02:40,240 Alle reg, ons het net verdubbel ons spoed. 50 00:02:40,240 --> 00:02:44,190 51 00:02:44,190 --> 00:02:49,060 So in die tussentyd, laat my inhou wat is gaan die vraag vir Mary Beth te wees 52 00:02:49,060 --> 00:02:51,540 is wat sy doen, hoe sy gaan oor die belangrikheid van hierdie? 53 00:02:51,540 --> 00:02:54,040 En in werklikheid is, kan jy nie ' ooit gedink oor iets 54 00:02:54,040 --> 00:02:57,440 so eenvoudig soos wanneer jy kies tot 26 boeke soos hierdie, 55 00:02:57,440 --> 00:02:59,350 wat 'n natuurlike nie bestel vir hulle. 56 00:02:59,350 --> 00:03:01,335 Wat is die proses dat jy eintlik gebruik? 57 00:03:01,335 --> 00:03:03,770 Is dit redelik ewekansige net pluk die eerste een wat jy sien 58 00:03:03,770 --> 00:03:05,250 en sit dit op sy plek? 59 00:03:05,250 --> 00:03:09,680 Moenie eers beweeg jou hande om soek na 'n dan op soek na B? 60 00:03:09,680 --> 00:03:11,722 Neem jy 'n blik op 'n paar van hulle langs mekaar 61 00:03:11,722 --> 00:03:14,680 en net sê, wag 'n minuut, hierdie nie reg is nie, en dan ruil die einde? 62 00:03:14,680 --> 00:03:16,960 Ons het reeds op Maandag dat daar 'n aantal van maniere 63 00:03:16,960 --> 00:03:22,140 waarop ons kan dit doen, en inderdaad as ons naby die einde hier 64 00:03:22,140 --> 00:03:26,360 Ek sou kennis neem dalk van wat Mary Beth doen. 65 00:03:26,360 --> 00:03:30,040 Ons het 'n paar hope lyk dit, 'n groter een, drie kleintjies. 66 00:03:30,040 --> 00:03:33,790 67 00:03:33,790 --> 00:03:36,415 >> Publiek: Ek beveel hulle toe ek vind twee letters 68 00:03:36,415 --> 00:03:39,540 dat ek weet is saam in 'n ry, Ek sit hulle saam sodat ek dit nie doen nie 69 00:03:39,540 --> 00:03:42,915 hoef te bekommer oor die hou van spoor van 'n hele ry van boeke. 70 00:03:42,915 --> 00:03:45,706 Dis net, ag, 'n eerste keer, Ek het hierdie stapel hier. 71 00:03:45,706 --> 00:03:47,580 Spreker: So, amper soos 'n legkaart stukke wat 72 00:03:47,580 --> 00:03:49,860 het die reg om vorm te ooreenstem met mekaar. 73 00:03:49,860 --> 00:03:51,026 Publiek: Pretty much, ja. 74 00:03:51,026 --> 00:03:55,320 Spreker: OK, 'n uitstekende. 75 00:03:55,320 --> 00:03:59,850 En nou elk van hierdie hope is vermoedelik gesorteer? 76 00:03:59,850 --> 00:04:00,990 >> Publiek: Ja. 77 00:04:00,990 --> 00:04:09,900 >> Spreker: Alle reg, 'n deur Z. Alle reg, baie geluk, jy het dit gedoen. 78 00:04:09,900 --> 00:04:11,461 Jy het jou keuse. 79 00:04:11,461 --> 00:04:11,960 Blou? 80 00:04:11,960 --> 00:04:13,530 Alle reg, dankie vir dit. 81 00:04:13,530 --> 00:04:16,679 So Mary Beth het stel wat haar benadering was, 82 00:04:16,679 --> 00:04:19,720 Maar wat is 'n ander benadering hoe jy dalk gaan sorteer hierdie dinge? 83 00:04:19,720 --> 00:04:21,130 Wat sou jy gedoen het? 84 00:04:21,130 --> 00:04:24,060 Die rekord te klop sou gewees het een minuut en 50 sekondes of so, 85 00:04:24,060 --> 00:04:26,039 plus die wat ek vergeet het om te tel. 86 00:04:26,039 --> 00:04:27,080 Wat sou jy gedoen het? 87 00:04:27,080 --> 00:04:27,579 Ja? 88 00:04:27,579 --> 00:04:28,735 Publiek: Neem die stapel. 89 00:04:28,735 --> 00:04:29,776 Begin van die begin af. 90 00:04:29,776 --> 00:04:32,284 Gaan jou vraestelle. 91 00:04:32,284 --> 00:04:36,586 En as die boonste een is hoër as, miskien, hulle is, 92 00:04:36,586 --> 00:04:38,980 Die onderste een is hoër is, dan skakel hulle. 93 00:04:38,980 --> 00:04:41,300 >> Spreker: OK, so begin aan die bokant en die onderkant, 94 00:04:41,300 --> 00:04:43,716 en dan werk jou pad innerlike soos daardie, uitruiling hulle? 95 00:04:43,716 --> 00:04:46,580 OK, so 'n bietjie soortgelyk in gees borrel soort, 96 00:04:46,580 --> 00:04:49,160 maar die keuse van die uiterstes nie die aangrensende pare. 97 00:04:49,160 --> 00:04:52,080 Maar die kort daarvan is dat daar sekerlik 'n klomp van die verskillende maniere 98 00:04:52,080 --> 00:04:54,210 ons dit kan doen, en eerlik, ek dink jy soort 99 00:04:54,210 --> 00:04:55,700 het 'n paar benaderings, reg? 100 00:04:55,700 --> 00:05:00,567 Jy het soort van vier gesorteer gebied, en dan effektief saamgesmelt saam. 101 00:05:00,567 --> 00:05:02,650 En dit is, daresay, 'n ander tegniek heeltemal. 102 00:05:02,650 --> 00:05:06,950 Jy het nie hanteer dit as 'n groot hoop, om die probleem verdeel in vier quads, 103 00:05:06,950 --> 00:05:09,820 as jy wil, en dan een of ander manier saamgevoeg in die einde. 104 00:05:09,820 --> 00:05:13,410 >> So laat ons kyk, uiteindelik, hoe anders ons kan dit doen. 105 00:05:13,410 --> 00:05:15,860 Ons geformaliseer die idee van die borrel soort laaste keer, 106 00:05:15,860 --> 00:05:18,780 en borrel soort onthou was 'n algoritme wat ons gevisualiseer 107 00:05:18,780 --> 00:05:22,640 met agt van jou klasmaats hier, oënskynlik lukraak gesorteer by die eerste. 108 00:05:22,640 --> 00:05:26,110 En ons het toe besluit om twee-, indien twee elemente is buite orde, 109 00:05:26,110 --> 00:05:26,950 eenvoudig ruil hulle. 110 00:05:26,950 --> 00:05:28,930 So vier en twee natuurlik buite orde, 111 00:05:28,930 --> 00:05:31,080 sodat die twee klasmaats aangeskakel posisies. 112 00:05:31,080 --> 00:05:35,390 En dan moet ons herhaal met vier en ses, dan ses en agt, op elke iterasie, 113 00:05:35,390 --> 00:05:36,980 beweeg na regs. 114 00:05:36,980 --> 00:05:42,590 >> So het agt mense, hoeveel paarsgewyse vergelykings het ek gedoen terwyl loop uit 115 00:05:42,590 --> 00:05:45,220 links na regs in een so 'n herhaling? 116 00:05:45,220 --> 00:05:48,410 Hoeveel vergelykings? 117 00:05:48,410 --> 00:05:49,197 Sewe, reg? 118 00:05:49,197 --> 00:05:51,405 Want as daar agt mense nie, maar jy het die paar 119 00:05:51,405 --> 00:05:53,880 hulle, en jy bly beweeg een hop aan die regterkant, 120 00:05:53,880 --> 00:05:56,060 jy gaan nie agt te hê vergelykings, want jy kan nie vergelyk 121 00:05:56,060 --> 00:05:59,226 'n element wat teen homself is, of dit sou net nutteloos, so jy het sewe. 122 00:05:59,226 --> 00:06:01,290 Of meer algemeen, as ons n volk, ons 123 00:06:01,290 --> 00:06:04,300 doen n minus 1 vergelykings met borrel soort. 124 00:06:04,300 --> 00:06:08,150 >> So laat ons nou kyk hoe goed of slegte borrel soort eintlik was, en probeer 125 00:06:08,150 --> 00:06:13,570 onsself te gee woordeskat met wat tot kritiek algoritmes soos hierdie, 126 00:06:13,570 --> 00:06:14,430 en gou ons eie. 127 00:06:14,430 --> 00:06:16,970 So het die eerste keer deur borrel soort, die eerste keer 128 00:06:16,970 --> 00:06:20,909 Ek loop van links na regs oor die stadium, het my n minus 1 vergelykings. 129 00:06:20,909 --> 00:06:22,950 En dit gaan wees my eenheid van meet, reg? 130 00:06:22,950 --> 00:06:26,170 Ek was soort van praat en loop, ietwat vinnig, ietwat stadig, 131 00:06:26,170 --> 00:06:29,300 so toe my nommer van sekondes is veral nie vertel, 132 00:06:29,300 --> 00:06:32,260 maar toe die aantal bedrywighede wat ek gedoen het op Maandag, 133 00:06:32,260 --> 00:06:35,900 twee mense te vergelyk, wat voel soos 'n mooi eenheid van meet. 134 00:06:35,900 --> 00:06:40,980 >> So n minus 1 stappe die eerste keer, maar dan wat gebeur daarna? 135 00:06:40,980 --> 00:06:46,610 Wat is die een onderstebo van 'n pas deur 'n andersins ongesorteerde lys? 136 00:06:46,610 --> 00:06:49,840 Wat kan jy my vertel oor die element wat al die pad oor daar? 137 00:06:49,840 --> 00:06:51,300 Ja? 138 00:06:51,300 --> 00:06:52,870 Dit was die grootste element, reg? 139 00:06:52,870 --> 00:06:55,710 Nommer agt, selfs al het sy begin hier, elke keer as ek 140 00:06:55,710 --> 00:06:57,860 vergelyking om haar teen 'n buurman, het sy 141 00:06:57,860 --> 00:07:00,480 borrel tot aan die regterkant kant van die lys. 142 00:07:00,480 --> 00:07:02,710 En inderdaad, dit is waar die algoritme kry sy naam. 143 00:07:02,710 --> 00:07:07,630 >> Nou deur daardie logika, hoeveel vergelykings moet ek op die tweede keer 144 00:07:07,630 --> 00:07:09,800 Ek maak dat die slaagsyfer van links na regs? 145 00:07:09,800 --> 00:07:10,730 N minus 2, reg? 146 00:07:10,730 --> 00:07:14,297 Dit sou net mors my tyd as ek hou vergelyk agt teen iemand 147 00:07:14,297 --> 00:07:16,630 anders omdat ons reeds weet Sy was op die regte plek. 148 00:07:16,630 --> 00:07:19,760 So dit is 'n bietjie van 'n optimalisering, sodat die volgende slaag 149 00:07:19,760 --> 00:07:23,899 gaan wees plus N minus twee stappe, waar n die aantal mense. 150 00:07:23,899 --> 00:07:26,940 Nou kan jy soort van ekstrapoleer, selfs As jy nie 'n rekenaar wetenskaplike, 151 00:07:26,940 --> 00:07:27,680 hoe dit eindig. 152 00:07:27,680 --> 00:07:31,259 Aan die einde van hierdie algoritme, vermoedelik jy het net een vergelyking gelaat. 153 00:07:31,259 --> 00:07:33,800 Jy moet soort los die begin van die lys in die geval twee 154 00:07:33,800 --> 00:07:36,540 en een is buite orde en moet een en twee, 155 00:07:36,540 --> 00:07:40,330 so hierdie Bottoms uit op plus 1 finale vergelyking. 156 00:07:40,330 --> 00:07:44,500 >> Nou is die dot, dot, dot soort van golwe is dit hande op 'n paar van die sappiger besonderhede, 157 00:07:44,500 --> 00:07:46,452 maar laat ons net voort te gaan en te vereenvoudig. 158 00:07:46,452 --> 00:07:48,660 As jy onthou van 'n hoë skool, eerlik, baie van julle 159 00:07:48,660 --> 00:07:50,340 het wiskunde boeke wat moes 'n bietjie oneerlik blad 160 00:07:50,340 --> 00:07:52,550 op die voorblad of die agterblad wat gewys het jy 161 00:07:52,550 --> 00:07:56,400 wat reeks opsommings soos Dit het uiteindelik bygevoeg tot. 162 00:07:56,400 --> 00:07:59,600 In die algemene geval, as jy 'n veranderlike soos n, en inderdaad hierdie een, 163 00:07:59,600 --> 00:08:01,634 As jy kyk na jou ou skool wiskunde boek, 164 00:08:01,634 --> 00:08:04,050 jy sal sien dat dit eintlik voeg tot hierdie bedrag hier 165 00:08:04,050 --> 00:08:07,970 n keer n minus 1 al gedeel deur 2. 166 00:08:07,970 --> 00:08:11,172 So vir nou laat my net stipuleer dit waar is, so op 'n sprong van geloof, 167 00:08:11,172 --> 00:08:12,880 dit is wat dit neerkom tot, en ons kon 168 00:08:12,880 --> 00:08:14,341 bewys dat in 'n meer algemene geval. 169 00:08:14,341 --> 00:08:15,590 Maar laat ons nou uit te brei dit uit. 170 00:08:15,590 --> 00:08:19,920 So laat vermenigvuldig dit uit, so dit is N vierkantig minus n, al gedeel deur 2. 171 00:08:19,920 --> 00:08:23,200 Dit is regtig n vierkant, gedeel deur 2, minus n meer as 2, 172 00:08:23,200 --> 00:08:25,010 so dit is al wat mooi en interessant. 173 00:08:25,010 --> 00:08:27,060 Maar wat gebeur as ons nou prop-in 'n waarde? 174 00:08:27,060 --> 00:08:29,724 Dink ek het nie agt mense nie, maar sê 'n miljoen. 175 00:08:29,724 --> 00:08:31,890 En 'n miljoen net omdat dit is 'n mooi groot aantal, 176 00:08:31,890 --> 00:08:34,039 laat se prop wat in en kyk wat gebeur. 177 00:08:34,039 --> 00:08:39,039 So as ek prop 'n miljoen in die formule Ek gaan 'n miljoen vierkantig 178 00:08:39,039 --> 00:08:42,868 gedeel deur 2, minus 'n miljoen, gedeel deur 2. 179 00:08:42,868 --> 00:08:44,159 Nou wat is dit gaan gelyk? 180 00:08:44,159 --> 00:08:47,354 So 500000000000, minus 500,000. 181 00:08:47,354 --> 00:08:49,270 En as ek doen dat wiskunde nie, dit beteken 182 00:08:49,270 --> 00:08:53,920 dat sortering 'n miljoen mense met die borrel soort 183 00:08:53,920 --> 00:09:01,800 kon neem my 499999500000 stappe of vergelykings in die einde, 184 00:09:01,800 --> 00:09:02,900 ons is maar net ekstrapoleer. 185 00:09:02,900 --> 00:09:06,860 >> Dit voel redelik stadig, maar eerlik meet 'n spesifieke insette 186 00:09:06,860 --> 00:09:09,160 soos hierdie, is nie al wat vertel. 187 00:09:09,160 --> 00:09:14,050 Maar wel dit dui daarop dat as n kry groter en groter, die algoritme 188 00:09:14,050 --> 00:09:16,280 soort van voel erger en erger, of jy regtig 189 00:09:16,280 --> 00:09:20,450 begin die pyn van daardie te voel magsverheffing, wat n vierkant, 190 00:09:20,450 --> 00:09:21,770 wat bydra tot redelik vinnig. 191 00:09:21,770 --> 00:09:25,340 En hierdie detail is nie verloor op mense, in werklikheid 192 00:09:25,340 --> 00:09:29,640 'n paar jaar gelede het 'n sekere senator wat veldtog, gaan sit vir 'n onderhoud 193 00:09:29,640 --> 00:09:32,180 Google se Eric Schmidt, uitvoerende hoof van die tyd, 194 00:09:32,180 --> 00:09:36,380 en is uitgedaag met 'n vraag baie soos ons vandag verken. 195 00:09:36,380 --> 00:09:38,468 Kom ons neem 'n blik. 196 00:09:38,468 --> 00:09:45,280 >> [Video speel] 197 00:09:45,280 --> 00:09:48,560 >> -Senator, Jy is hier op Google, en ek wil graag 198 00:09:48,560 --> 00:09:53,382 om te dink aan die presidensie as 'n werksonderhoud. 199 00:09:53,382 --> 00:09:56,434 Nou, dit is moeilik om te kry 'n werk as president, 200 00:09:56,434 --> 00:09:58,100 en jy gaan deur middel van die pogings nou. 201 00:09:58,100 --> 00:10:01,860 Dit is ook moeilik om 'n werk te kry by Google. 202 00:10:01,860 --> 00:10:05,490 Ons het vrae, en ons vra ons kandidate vrae, 203 00:10:05,490 --> 00:10:09,770 en hierdie een is van Larry Schwimmer. 204 00:10:09,770 --> 00:10:14,760 What-- julle dink ek is grap, dit is reg hier. 205 00:10:14,760 --> 00:10:17,930 Wat is die mees doeltreffende manier om te sorteer 'n miljoen 32-bit heelgetalle? 206 00:10:17,930 --> 00:10:21,800 207 00:10:21,800 --> 00:10:24,350 >> -Well-- 208 00:10:24,350 --> 00:10:25,200 >> I 'm sorry, maybe-- 209 00:10:25,200 --> 00:10:27,400 >> Nee, nee, nee. 210 00:10:27,400 --> 00:10:30,700 Ek dink die borrel soort sou die verkeerde manier om te gaan. 211 00:10:30,700 --> 00:10:34,165 212 00:10:34,165 --> 00:10:38,180 >> -Come Op, wat hom hierdie vertel? 213 00:10:38,180 --> 00:10:40,590 Ek het nie rekenaar sien wetenskap in jou agtergrond. 214 00:10:40,590 --> 00:10:42,130 >> -We've Het ons spioene in daar. 215 00:10:42,130 --> 00:10:44,930 216 00:10:44,930 --> 00:10:48,444 >> -OK, Laat ons vra 'n ander onderhoud vraag. 217 00:10:48,444 --> 00:10:49,300 >> [Einde video speel] 218 00:10:49,300 --> 00:10:52,290 >> Spreker: So praat spesifieke getalle egter 219 00:10:52,290 --> 00:10:53,890 is nie van plan om alles wat nuttig is. 220 00:10:53,890 --> 00:10:56,810 Dit is nie 'n lewe les wat borrel soort, gegewe 'n miljoen insette, 221 00:10:56,810 --> 00:10:58,590 soveel as 500000000000 stappe te neem. 222 00:10:58,590 --> 00:11:01,120 Jy kan regtig nie veralgemeen te doeltreffend uit daardie 223 00:11:01,120 --> 00:11:03,560 en maak 'n goeie ontwerp besluite wanneer die skryf van programme. 224 00:11:03,560 --> 00:11:07,070 So laat se fokus al hoe ons kan hierdie resultaat vereenvoudig. 225 00:11:07,070 --> 00:11:11,780 >> Daarom het ek in geel uitgelig hier die gevolg van n kwadraat gedeel deur 2, 226 00:11:11,780 --> 00:11:14,330 so 'n miljoen vierkant gedeel deur 2, en dan 227 00:11:14,330 --> 00:11:16,710 Ek het uitgelig wat die uiteindelike antwoord was 228 00:11:16,710 --> 00:11:20,180 Sodra ons afgetrek af N gedeel deur 2. 229 00:11:20,180 --> 00:11:24,850 En die eis gaan ek nou maak, is, wat die heck omgee as jy trek af 230 00:11:24,850 --> 00:11:30,060 'n klein ou n meer as 2 toe die eerste deel van hierdie formule is soveel groter? 231 00:11:30,060 --> 00:11:33,910 Dit oorheers die ander term, n kwadraat gedeel deur 2 232 00:11:33,910 --> 00:11:37,510 is soveel groter, duidelik, soos N kry groot soos 'n miljoen, 233 00:11:37,510 --> 00:11:41,450 dit is daar werklik 'n groot verskil aan die einde van die dag tussen 500000000000 234 00:11:41,450 --> 00:11:45,730 en 499999500000? 235 00:11:45,730 --> 00:11:46,349 Nie regtig nie. 236 00:11:46,349 --> 00:11:48,640 En ja, wat ons gaan doen as die rekenaar wetenskaplikes is 237 00:11:48,640 --> 00:11:53,270 ignoreer die laer orde terme en neem iets soos hierdie en baie 238 00:11:53,270 --> 00:11:56,050 net vereenvoudig dit tot die term wat gaan saak maak nie. 239 00:11:56,050 --> 00:12:00,315 Die groter ons data stelle kry, hoe groter ons databasis, hoe meer webblaaie 240 00:12:00,315 --> 00:12:02,690 ons het, hoe meer om te soek vriende wat jy het op Facebook. 241 00:12:02,690 --> 00:12:07,340 >> As n groter word, ons is baie gaan omgee oor die grootste 242 00:12:07,340 --> 00:12:11,560 term in enige sodanige ontleding van ons algoritmes prestasie. 243 00:12:11,560 --> 00:12:16,230 En ek gaan om te sê, jy weet wat, borrel soort is aan die orde van die groot O, 244 00:12:16,230 --> 00:12:18,060 op die einde van n vierkant. 245 00:12:18,060 --> 00:12:20,090 Dit is nie presies n vierkantig soos ons gesien het, 246 00:12:20,090 --> 00:12:22,060 maar wat regtig omgee oor die kleiner terme, 247 00:12:22,060 --> 00:12:24,390 en eerlik, wat werklik omgee as ons deur 2? 248 00:12:24,390 --> 00:12:25,870 Dit is net 'n konstante faktor. 249 00:12:25,870 --> 00:12:29,480 En is 500000000000 teenoor 250 miljard regtig so groot van 'n deal? 250 00:12:29,480 --> 00:12:32,190 Ek kon net wag 'n jaar, laat my laptop letterlik 251 00:12:32,190 --> 00:12:34,810 kry twee keer so vinnig in hardeware, en dat die soort van verskil 252 00:12:34,810 --> 00:12:36,650 gaan net weg natuurlike verloop van tyd. 253 00:12:36,650 --> 00:12:39,300 >> Wat ons omgee is die uitdrukking, die deel 254 00:12:39,300 --> 00:12:42,489 van die uitdrukking wat gaan verskil as ons insette kry groter en groter. 255 00:12:42,489 --> 00:12:45,280 En inderdaad, in die werklike wêreld, dit is wat toenemend gebeur 256 00:12:45,280 --> 00:12:48,330 is die insette van ons probleme en algoritmes word al hoe groter. 257 00:12:48,330 --> 00:12:53,470 So groot O gaan die notering te wees, die asimptotiese notasie, dat ons net 258 00:12:53,470 --> 00:12:57,160 gebruik as die rekenaar wetenskaplikes te beskryf die prestasie of die loop van die tyd, 259 00:12:57,160 --> 00:12:58,130 van 'n algoritme. 260 00:12:58,130 --> 00:13:00,800 Sodat ons algoritmes kan vergelyk op verskillende rekenaars geskryf 261 00:13:00,800 --> 00:13:04,170 deur verskillende mense, deur die gebruik van sommige fundamenteel soortgelyke metrieke 262 00:13:04,170 --> 00:13:07,557 soos die aantal vergelykings jy maak, of dalk die aantal swaps 263 00:13:07,557 --> 00:13:08,140 jy maak. 264 00:13:08,140 --> 00:13:11,910 >> Wat ons gaan nie telling is die bedrag van die tyd 265 00:13:11,910 --> 00:13:13,981 wat verby op die klok op die muur tipies. 266 00:13:13,981 --> 00:13:16,230 Wat gaan ons nie te bekommer is oor hoeveel geheue 267 00:13:16,230 --> 00:13:17,820 vandag is die gebruik by minste, al is dit 268 00:13:17,820 --> 00:13:19,370 'n ander bron wat ons kan meet. 269 00:13:19,370 --> 00:13:23,610 Ons gaan probeer om ons ontleding te baseer op net die basiese operasies, die kinders, 270 00:13:23,610 --> 00:13:25,930 eerlik, dat jy die meeste visueel kan sien. 271 00:13:25,930 --> 00:13:30,700 So iets soos 'n groot O van n vierkantig, ek beweer dat O van n vierkant 272 00:13:30,700 --> 00:13:35,820 'n bogrens op die sogenaamde loop van die tyd van die borrel soort. 273 00:13:35,820 --> 00:13:38,820 Met ander woorde, as jy wou beweer dat daar 274 00:13:38,820 --> 00:13:41,370 hierdie boonste limiet op hoeveel stappe om 'n algoritme te neem, 275 00:13:41,370 --> 00:13:46,240 dit gaan wees in die groot O van n vierkantig in hierdie geval, 'n bogrens. 276 00:13:46,240 --> 00:13:49,710 >> Wat gebeur as ek plaas verander die storie te wees nie oor borrel soort, 277 00:13:49,710 --> 00:13:50,910 maar oor hierdie bogrens. 278 00:13:50,910 --> 00:13:54,030 Kan jy dink aan 'n algoritme dat ons het gekyk na al 279 00:13:54,030 --> 00:13:59,530 wie se bogrens, maksimum meet van die tyd of bedrywighede, 280 00:13:59,530 --> 00:14:04,300 sou gesê word begrens word deur n, 'n lineêre funksie, 281 00:14:04,300 --> 00:14:07,260 nie 'n kwadratiese een wat geboë? 282 00:14:07,260 --> 00:14:10,780 Wat is 'n algoritme wat vind altyd nie meer 283 00:14:10,780 --> 00:14:12,860 as soos n stappe, of 2n stappe, of 3n stappe? 284 00:14:12,860 --> 00:14:13,360 Ja? 285 00:14:13,360 --> 00:14:15,030 >> Publiek: Dit vind van die grootste getal in 'n lys? 286 00:14:15,030 --> 00:14:16,930 >> Spreker: Perfect, vind die grootste aantal in 'n lys. 287 00:14:16,930 --> 00:14:18,940 As ek 'n lys van mense byvoorbeeld 288 00:14:18,940 --> 00:14:21,440 elk van wat hou van 'n nommer, Wat is die maksimum aantal 289 00:14:21,440 --> 00:14:23,770 van stappe om dit vir my te neem, 'n redelik slim persoon, 290 00:14:23,770 --> 00:14:27,530 die grootste persoon in die lys te kry? 291 00:14:27,530 --> 00:14:28,100 n, reg? 292 00:14:28,100 --> 00:14:31,320 Want in die ergste geval, waar dalk die grootste waarde wees? 293 00:14:31,320 --> 00:14:32,700 Reg, al die pad aan die einde. 294 00:14:32,700 --> 00:14:34,575 So in die ergste geval boonste gebind, ek kan 295 00:14:34,575 --> 00:14:36,450 het al die pad om te gaan hier en wees soos, 296 00:14:36,450 --> 00:14:39,170 O ja, hier is nommer agt, of wat ook al wat waarde is. 297 00:14:39,170 --> 00:14:41,330 Nou is dit net dom wees As ek aan die gang gehou het, reg? 298 00:14:41,330 --> 00:14:43,840 Op soek na meer en meer elemente As die laaste van hulle is daar? 299 00:14:43,840 --> 00:14:45,340 So sekerlik, n 'n bogrens is. 300 00:14:45,340 --> 00:14:47,420 Ek het nie nodig om te neem meer stappe as dit. 301 00:14:47,420 --> 00:14:51,580 >> So, wat as plaas ek voorgestel dat daar algoritmes in hierdie wêreld wat 302 00:14:51,580 --> 00:14:57,750 'n loop van die tyd wat begrens deur die groot O van log n, teken n? 303 00:14:57,750 --> 00:15:00,390 Waar het ons voorheen gesien het nie? 304 00:15:00,390 --> 00:15:00,890 Ja? 305 00:15:00,890 --> 00:15:03,309 >> Publiek: In die telefoon boek probleem? 306 00:15:03,309 --> 00:15:04,850 Spreker: Soos die telefoon boek probleem. 307 00:15:04,850 --> 00:15:07,754 Wat was die maatstaf van hoe veel tyd of hoeveel trane dit 308 00:15:07,754 --> 00:15:10,170 het my iemand soos om uit te vind Mike Smith in die telefoon boek? 309 00:15:10,170 --> 00:15:13,212 Ons het beweer dit was log n, en selfs as onbekende of dit dit is 310 00:15:13,212 --> 00:15:15,170 'n bietjie vaag wat 'n logaritme of eksponent was, 311 00:15:15,170 --> 00:15:17,650 net onthou dat log N algemeen verwys na die proses, 312 00:15:17,650 --> 00:15:20,790 in hierdie geval, verdeel iets weer in die helfte, en weer, 313 00:15:20,790 --> 00:15:25,790 en weer, en weer, soos wat dit kry toenemend klein as jy dit doen. 314 00:15:25,790 --> 00:15:28,470 >> So teken van N verwys, seker, na die telefoon boek byvoorbeeld 315 00:15:28,470 --> 00:15:32,662 binêre soek in teorie, wanneer ons het die virtuele deure op die raad, 316 00:15:32,662 --> 00:15:34,370 of wanneer Sean was soek vir iets. 317 00:15:34,370 --> 00:15:37,374 As hy binêre soek gebruik het, teken n die bogrens van hoeveel sou wees 318 00:15:37,374 --> 00:15:38,040 tyd wat neem. 319 00:15:38,040 --> 00:15:44,027 Maar daardie algoritmes wat gehardloop in log n aanvaar wat die sleutel detail? 320 00:15:44,027 --> 00:15:45,360 Dat die lys is gesorteer, reg? 321 00:15:45,360 --> 00:15:47,789 Jou algoritme is verkeerd as jou insette is nie gesorteer, 322 00:15:47,789 --> 00:15:49,830 en nog wat jy gebruik iets soos binêre soek 323 00:15:49,830 --> 00:15:51,704 omdat jy dalk te spring reg oor die element 324 00:15:51,704 --> 00:15:53,600 sonder om te besef dit is inderdaad daar. 325 00:15:53,600 --> 00:15:55,600 >> Nou wat kan dit beteken, groot O van die een? 326 00:15:55,600 --> 00:15:59,117 Dit beteken nie dat jou algoritme neem een ​​en slegs een stap, 327 00:15:59,117 --> 00:16:01,200 dit beteken net dit neem om 'n konstante aantal stappe. 328 00:16:01,200 --> 00:16:04,060 Miskien is dit 1, miskien is dit 10, miskien is dit 1000, 329 00:16:04,060 --> 00:16:07,750 maar dit is onafhanklik van die omvang van die probleem. 330 00:16:07,750 --> 00:16:10,850 Maak nie saak hoe groot n is, 'n konstante tyd algoritme 331 00:16:10,850 --> 00:16:12,747 neem altyd dieselfde aantal stappe. 332 00:16:12,747 --> 00:16:15,080 So wat kan 'n algoritme wees ons het gepraat oor of net 333 00:16:15,080 --> 00:16:20,418 intuïtief wat kom om jou wat altyd loop in die sogenaamde konstante tyd? 334 00:16:20,418 --> 00:16:20,918 Ja? 335 00:16:20,918 --> 00:16:22,001 >> GEHOOR: Voeg twee getalle. 336 00:16:22,001 --> 00:16:25,320 Spreker: Voeg twee getalle, 2 plus 2 is gelyk aan 4, gedoen. 337 00:16:25,320 --> 00:16:27,227 So wat kan werk, wat anders? 338 00:16:27,227 --> 00:16:28,560 Hoe gaan meer werklike wêreld, ja? 339 00:16:28,560 --> 00:16:30,686 >> Publiek: Dit vind van die eerste ding wat in 'n lys. 340 00:16:30,686 --> 00:16:32,810 Spreker: Dit vind van die eerste element in 'n lys, seker nie. 341 00:16:32,810 --> 00:16:34,540 Ons het eintlik gepraat oor skikkings reeds 342 00:16:34,540 --> 00:16:36,540 hoe kry jy by die eerste element in 'n skikking, 343 00:16:36,540 --> 00:16:40,465 maak nie saak hoe lank die skikking is in C-kode? 344 00:16:40,465 --> 00:16:43,090 Jy moet net gebruik soos die bracket nul notasie, bam, jy is daar. 345 00:16:43,090 --> 00:16:46,120 En inderdaad skikkings, as 'n eenkant, ondersteuning iets algemeen bekend 346 00:16:46,120 --> 00:16:49,240 as ewetoeganklike, ewetoeganklike geheue, want jy kan letterlik 347 00:16:49,240 --> 00:16:50,284 spring na enige plek. 348 00:16:50,284 --> 00:16:52,700 Ons kan eenvoudig dit doen nog meer Ons kan rewind te week nul 349 00:16:52,700 --> 00:16:53,900 toe ons nuuts af. 350 00:16:53,900 --> 00:16:59,707 Hoeveel tyd het dit vir die sê blok in Scratch uit te voer? 351 00:16:59,707 --> 00:17:00,790 Net konstante tyd, reg? 352 00:17:00,790 --> 00:17:03,960 Sê iets, sê iets, beteken dit nie saak nie 353 00:17:03,960 --> 00:17:07,359 hoe groot skrape wêreld is, is dit altyd gaan dieselfde hoeveelheid tyd te neem 354 00:17:07,359 --> 00:17:08,490 om net iets sê. 355 00:17:08,490 --> 00:17:11,089 >> So dit is konstante, maar wat is die ander kant? 356 00:17:11,089 --> 00:17:13,030 As dit was bo grense, wat as ons wil 357 00:17:13,030 --> 00:17:17,089 die laer perke te beskryf van ons algoritmes loop van die tyd? 358 00:17:17,089 --> 00:17:19,852 Byna 'n beste geval potensieel, as jy wil, 359 00:17:19,852 --> 00:17:23,060 al hierdie terme kan aansoek doen om die beste gevalle ergste gevalle, gemiddelde gevalle meer 360 00:17:23,060 --> 00:17:26,359 algemeen nie, maar laat ons net fokus op die laer perke meer algemeen. 361 00:17:26,359 --> 00:17:31,920 Wat is 'n algoritme wat 'n laer grens van N stappe, 362 00:17:31,920 --> 00:17:33,350 of 2n stappe, of 3n stappe? 363 00:17:33,350 --> 00:17:36,241 Sommige faktor van N stappe, dit is sy ondergrens. 364 00:17:36,241 --> 00:17:36,740 Ja? 365 00:17:36,740 --> 00:17:37,910 >> Publiek: borrel soort? 366 00:17:37,910 --> 00:17:41,610 >> Spreker: borrel soort neem jy minimaal n stappe, hoekom? 367 00:17:41,610 --> 00:17:42,279 Hoekom is dit? 368 00:17:42,279 --> 00:17:45,320 Hoekom moet dit begin om vir jou te kom intuïtief, selfs al is dit nie net 369 00:17:45,320 --> 00:17:46,530 nog? 370 00:17:46,530 --> 00:17:47,030 Ja? 371 00:17:47,030 --> 00:17:47,990 >> Publiek: [onhoorbaar]. 372 00:17:47,990 --> 00:17:51,652 373 00:17:51,652 --> 00:17:52,360 Spreker: Presies. 374 00:17:52,360 --> 00:17:55,810 In die beste moontlike scenario van borrel soort, en 'n baie van algoritmes, 375 00:17:55,810 --> 00:17:58,769 As ek vir julle agt mense wat reeds gesorteer, 376 00:17:58,769 --> 00:18:00,560 dit sou dom wees vir jou, die algoritme, 377 00:18:00,560 --> 00:18:02,202 heen en weer te gaan meer as een keer, reg? 378 00:18:02,202 --> 00:18:04,285 Want sodra jy loop deur die lys een keer, 379 00:18:04,285 --> 00:18:08,090 jy moet besef, o, ek het geen swaps, is hierdie lys gesorteer, afrit. 380 00:18:08,090 --> 00:18:09,700 Maar wat gaan jy n stappe te neem. 381 00:18:09,700 --> 00:18:12,033 >> En omgekeerd, wat is 'n ander manier van dink oor dit? 382 00:18:12,033 --> 00:18:15,240 Borrel soort is 'n omega, so te sê, van N, 383 00:18:15,240 --> 00:18:19,050 want as jy kyk na minder as N elemente, wat 384 00:18:19,050 --> 00:18:23,009 is die fundamentele kwessie is daar? 385 00:18:23,009 --> 00:18:24,550 Jy weet nie of dit gesorteer, reg. 386 00:18:24,550 --> 00:18:26,800 Ons mense mag blik op agt mense en wees soos, O, dit is gesorteer, 387 00:18:26,800 --> 00:18:28,430 dit het nie neem my n stappe, maar dit het. 388 00:18:28,430 --> 00:18:30,810 Jou oë, selfs al is jy soort van 'n groot gebied van die visie, 389 00:18:30,810 --> 00:18:33,184 jy kyk na agt elemente, jy kyk na agt mense, 390 00:18:33,184 --> 00:18:34,610 dit is agt stappe effektief. 391 00:18:34,610 --> 00:18:38,612 En net as ek loop deur die hele lys besef ek, ja, gesorteer. 392 00:18:38,612 --> 00:18:41,320 As ek stop halfpad dink, al reg, dit is mooi so ver gesorteer, 393 00:18:41,320 --> 00:18:42,520 wat is die kans is dit nie gesorteer? 394 00:18:42,520 --> 00:18:44,186 Dit algoritmes gaan nie korrek te wees. 395 00:18:44,186 --> 00:18:46,250 Dalk vinniger, maar verkeerd. 396 00:18:46,250 --> 00:18:48,500 >> So nou het ons 'n manier om beskrywing van 'n laer perke, 397 00:18:48,500 --> 00:18:49,710 En wat van konstante tyd? 398 00:18:49,710 --> 00:18:54,565 Wat is 'n algoritme wat 'n laer gebind op sy lopende tyd van die een? 399 00:18:54,565 --> 00:18:58,350 1 stap, 2 stappe, 10 stappe, maar konstant, onafhanklik van N, 400 00:18:58,350 --> 00:18:59,310 die grootte van die insette? 401 00:18:59,310 --> 00:19:03,930 402 00:19:03,930 --> 00:19:04,600 Ja, in die rug. 403 00:19:04,600 --> 00:19:05,309 >> Publiek: printf? 404 00:19:05,309 --> 00:19:06,183 Spreker: Wat is dit? 405 00:19:06,183 --> 00:19:07,184 Publiek: printf? 406 00:19:07,184 --> 00:19:07,850 Spreker: printf. 407 00:19:07,850 --> 00:19:08,400 OK, seker nie. 408 00:19:08,400 --> 00:19:10,720 So dit neem 'n vaste aantal stappe. 409 00:19:10,720 --> 00:19:13,170 En ek moet nou dat now-- ons praat oor C-kode 410 00:19:13,170 --> 00:19:16,040 en nie krap iets soos byvoorbeeld met printf, 411 00:19:16,040 --> 00:19:17,710 ons moet begin versigtig te kry. 412 00:19:17,710 --> 00:19:21,090 Omdat printf neem nie insette, dit is 'n string, 413 00:19:21,090 --> 00:19:23,220 en snare tegnies het lank nie. 414 00:19:23,220 --> 00:19:25,530 So as ons nou wil kies op jou, as jy nie omgee nie, 415 00:19:25,530 --> 00:19:29,430 tegnies kon ons dat printf argumenteer neem nie 'n veranderlike lengte insette, 416 00:19:29,430 --> 00:19:32,270 en sekerlik kan dit neem meer tyd om 'n string te druk hierdie lang, 417 00:19:32,270 --> 00:19:33,560 as dit lank. 418 00:19:33,560 --> 00:19:36,570 >> So wat as ons kyk na net die sorteer en soek voorbeelde? 419 00:19:36,570 --> 00:19:40,450 Wat van Mike Smith in die telefoon boek, of binêre soek meer in die algemeen? 420 00:19:40,450 --> 00:19:42,220 In die beste geval, wat kan gebeur? 421 00:19:42,220 --> 00:19:45,577 Ek maak die telefoon boek en bam, daar is Mike Smith se nommer. 422 00:19:45,577 --> 00:19:46,660 Ek kan hom bel dadelik. 423 00:19:46,660 --> 00:19:49,390 >> Het 'n stap, miskien twee stappe, maar 'n konstante aantal stappe 424 00:19:49,390 --> 00:19:50,230 As ek gelukkig. 425 00:19:50,230 --> 00:19:52,570 En eerlik, het ons gesien op Maandag jou klasmaat 426 00:19:52,570 --> 00:19:54,710 kry baie gelukkig twee keer in 'n ry. 427 00:19:54,710 --> 00:19:57,050 En dit was inderdaad konstante keer in 'n laer perke 428 00:19:57,050 --> 00:20:01,280 op die algoritme in die vraag vir die vind van die nommer 50 agter die geslote 429 00:20:01,280 --> 00:20:01,830 deure. 430 00:20:01,830 --> 00:20:06,400 >> Nou, as 'n eenkant, as jy ontdek dat beide groot O, die bogrens, 431 00:20:06,400 --> 00:20:09,310 en omega, die laer gebind, is een in dieselfde, wat 432 00:20:09,310 --> 00:20:11,830 is dieselfde formule in hakies, jy kan ook 433 00:20:11,830 --> 00:20:15,170 sê, net om te fancy nie, dat daar iets in theta 434 00:20:15,170 --> 00:20:18,270 van N of theta van 'n ander waarde. 435 00:20:18,270 --> 00:20:20,661 Dit beteken net wanneer groot O en omega is dieselfde. 436 00:20:20,661 --> 00:20:21,910 Nou wat van seleksie soort? 437 00:20:21,910 --> 00:20:23,400 Kom ons gebruik hierdie nuwe woordeskat. 438 00:20:23,400 --> 00:20:27,407 In seleksie soort, wat ons was doen weer, en weer en weer? 439 00:20:27,407 --> 00:20:29,990 Ek is heen en weer gaan deur die lys, op soek na wie? 440 00:20:29,990 --> 00:20:33,260 441 00:20:33,260 --> 00:20:34,730 Die kleinste getal. 442 00:20:34,730 --> 00:20:37,560 >> So hoeveel stappe, hoe baie vergelykings het ek 443 00:20:37,560 --> 00:20:43,250 moet maak om uit te vind wat die kleinste element in die lys was? 444 00:20:43,250 --> 00:20:44,437 N minus 1, reg? 445 00:20:44,437 --> 00:20:47,770 Want as ek net begin met die een wat ek gegee en ek begin vergelyk hom of haar, 446 00:20:47,770 --> 00:20:49,519 dan moet julle hom of haar, hom of haar, hom of haar, ek 447 00:20:49,519 --> 00:20:52,010 kan slegs elemente paar saam n minus 1 keer. 448 00:20:52,010 --> 00:20:55,630 So keuring soort soortgelyke N minus 1 stappe die eerste keer. 449 00:20:55,630 --> 00:20:59,540 >> Hoeveel stappe neem dit om my te vind die tweede kleinste element? 450 00:20:59,540 --> 00:21:02,920 N minus 2, want ek is die stom As ek bly kyk na die dieselfde mense 451 00:21:02,920 --> 00:21:06,280 weer as ek het hom reeds gekies of haar en sit hulle in hul plek. 452 00:21:06,280 --> 00:21:09,270 En die derde stap, n minus 3, dan n minus 4. 453 00:21:09,270 --> 00:21:11,020 Ons het gesien hoe hierdie patroon voor, en wel 454 00:21:11,020 --> 00:21:13,460 seleksie soort soortgelyke 'n bogrens 455 00:21:13,460 --> 00:21:16,210 N vierkant as ons dit doen tot dat opsomming. 456 00:21:16,210 --> 00:21:19,790 Wat is die ondergrens, seleksie soort? 457 00:21:19,790 --> 00:21:25,350 Minimaal, hoeveel tyd moet seleksie soort neem, soos ons dit gedefinieer op Maandag? 458 00:21:25,350 --> 00:21:29,370 459 00:21:29,370 --> 00:21:30,490 Stel twee opsies. 460 00:21:30,490 --> 00:21:32,360 Miskien is dit n, soos voorheen. 461 00:21:32,360 --> 00:21:35,040 Miskien is dit n vierkant, as dit is nou as die bogrens. 462 00:21:35,040 --> 00:21:35,874 >> Publiek: N vierkant. 463 00:21:35,874 --> 00:21:36,664 Spreker: N vierkant. 464 00:21:36,664 --> 00:21:37,368 Hoekom? 465 00:21:37,368 --> 00:21:40,060 >> Publiek: Omdat jy te definieer [onhoorbaar]. 466 00:21:40,060 --> 00:21:41,510 >> Spreker: Presies. 467 00:21:41,510 --> 00:21:45,077 Ten minste as ek gedefinieer seleksie soort dit was 'n bietjie naïef, hou, 468 00:21:45,077 --> 00:21:46,160 vind die kleinste element. 469 00:21:46,160 --> 00:21:47,770 Gaan weer, vind die kleinste element. 470 00:21:47,770 --> 00:21:49,490 Gaan weer, vind die kleinste element. 471 00:21:49,490 --> 00:21:51,700 Daar is geen soort optimalisering daar wat 472 00:21:51,700 --> 00:21:54,350 dalk laat my staak nadat net n of so stappe. 473 00:21:54,350 --> 00:21:57,080 So inderdaad, seleksie soort, omega van N vierkant. 474 00:21:57,080 --> 00:22:00,667 >> Wat van invoeging soort, waar ek het wat ek gegee is, en dan het ek plons hom 475 00:22:00,667 --> 00:22:01,750 of haar in die regte plek? 476 00:22:01,750 --> 00:22:04,958 Toe voortgegaan ek na die tweede persoon, plons hom of haar in die regte plek. 477 00:22:04,958 --> 00:22:07,910 Toe het die volgende persoon, plons hom of haar in die regte plek. 478 00:22:07,910 --> 00:22:10,537 Let daarop dat hierdie is baie lineêre, om so te praat. 479 00:22:10,537 --> 00:22:12,620 Ek is 'n reguit lyn, ek is nie heen en weer gaan, 480 00:22:12,620 --> 00:22:16,080 Ek het nog nooit terug kyk regtig nie, maar wat gebeur wanneer ek plaas hom 481 00:22:16,080 --> 00:22:20,302 of haar in die begin van die lys soos ons gedoen het op Maandag? 482 00:22:20,302 --> 00:22:21,010 Wat gebeur? 483 00:22:21,010 --> 00:22:21,510 Ja? 484 00:22:21,510 --> 00:22:23,122 Publiek: [onhoorbaar]. 485 00:22:23,122 --> 00:22:24,830 Spreker: Ja, dit was die vangs, reg? 486 00:22:24,830 --> 00:22:26,746 Jy kan onthou uit jou klasmaats, indien hulle 487 00:22:26,746 --> 00:22:29,670 is om enige beweging met hul voete, dit was 'n operasie. 488 00:22:29,670 --> 00:22:33,610 So as daar drie mense hier en die nuwe mens behoort manier daar, 489 00:22:33,610 --> 00:22:37,360 op 'n lang fase soos hierdie, seker, hy of sy kan net gaan na die einde. 490 00:22:37,360 --> 00:22:40,074 Maar as ons dink oor 'n rekenaar en 'n verskeidenheid van die geheue, 491 00:22:40,074 --> 00:22:41,990 hierdie mense gaan te hê om te skuif oor 492 00:22:41,990 --> 00:22:43,260 ruimte vir daardie persoon te maak. 493 00:22:43,260 --> 00:22:46,930 En sodat n minus 1 shufflings, N minus 2 shufflings, n 494 00:22:46,930 --> 00:22:50,660 minus 3 shufflings is net soort van gebeur agter my, nie in die voorkant van my 495 00:22:50,660 --> 00:22:52,710 soos voorheen, in 'n sekere sin. 499 00:22:52,557 --> 00:22:54,640 Nou as 'n eenkant, en as Jy kan gesien het aanlyn 500 00:22:54,640 --> 00:22:57,699 As jy begin skeer rond oor vorme, daar is so baie verskillende kinders 501 00:22:57,699 --> 00:22:59,490 daar is, sommige van hulle beter as ander. 502 00:22:59,490 --> 00:23:02,200 Inderdaad, bogosort is een dit is soort van pret om te kyk. 503 00:23:02,200 --> 00:23:06,650 Bogosort neem 'n stel nommers of sê 'n pak kaarte, 504 00:23:06,650 --> 00:23:09,870 lukraak skud hulle, en tjeks as hulle gesorteer. 505 00:23:09,870 --> 00:23:12,130 En indien nie, doen dit weer. 506 00:23:12,130 --> 00:23:14,140 En indien nie, doen dit weer. 507 00:23:14,140 --> 00:23:15,440 Indien nie, doen dit weer. 508 00:23:15,440 --> 00:23:17,060 Ongelooflik dom. 509 00:23:17,060 --> 00:23:19,520 >> En inderdaad, as jy lees soos die Wikipedia artikel, 510 00:23:19,520 --> 00:23:21,200 sy bynaam is dom soort. 511 00:23:21,200 --> 00:23:25,180 Dit sal uiteindelik werk hopelik, gegewe genoeg tyd, 512 00:23:25,180 --> 00:23:28,240 maar dat die bedrag van die tyd kon 'n geruime tyd in beslag neem. 513 00:23:28,240 --> 00:23:31,650 So as ek kon, laat se spoed dinge uit Mary Beth se voorbeeld vroeër, 514 00:23:31,650 --> 00:23:35,150 deur 'n paar elemente, maar twee verwerkers. 515 00:23:35,150 --> 00:23:37,100 Twee mense, as jy sal nie omgee om saam met my. 516 00:23:37,100 --> 00:23:40,972 Hoe oor 1 hier, en laat se go-- niemand daar? 517 00:23:40,972 --> 00:23:41,722 Niemand daar? 518 00:23:41,722 --> 00:23:42,221 OK. 519 00:23:42,221 --> 00:23:44,190 Jy met die swart hemp, ja, kom neer. 520 00:23:44,190 --> 00:23:45,000 Alle reg, wat is jou naam? 521 00:23:45,000 --> 00:23:45,720 >> Publiek: Peter. 522 00:23:45,720 --> 00:23:46,100 >> Spreker: Wat is dit? 523 00:23:46,100 --> 00:23:46,766 >> Publiek: Peter. 524 00:23:46,766 --> 00:23:49,450 Spreker: Peter, David, lekker om te ontmoet. 525 00:23:49,450 --> 00:23:53,670 Alle reg, ons het Petrus hier, as jy wil kom op die tafel hier. 526 00:23:53,670 --> 00:23:54,550 En wat is jou naam? 527 00:23:54,550 --> 00:23:55,216 >> Publiek: Elena. 528 00:23:55,216 --> 00:23:55,970 Spreker: Elena. 529 00:23:55,970 --> 00:23:57,030 OK, lekker om jou te ontmoet. 530 00:23:57,030 --> 00:23:58,060 Elena ontmoet Peter. 531 00:23:58,060 --> 00:23:59,170 Peter, Elena. 532 00:23:59,170 --> 00:24:02,290 En ons sal moet Andrew hier so goed, asseblief. 533 00:24:02,290 --> 00:24:06,107 En jou uitdaging gaan te wees van 'n dek van kaarte te sorteer. 534 00:24:06,107 --> 00:24:08,190 En as onbekende, dek kaarte moet uiteindelik 535 00:24:08,190 --> 00:24:11,064 word gesorteer 'n bietjie iets soos dit waar ons die klubs sal doen, dan 536 00:24:11,064 --> 00:24:13,660 die grawe, die harte en diamante, van kampioen as 'n een, 537 00:24:13,660 --> 00:24:15,570 al die pad tot by die koning. 538 00:24:15,570 --> 00:24:20,890 >> Die kaarte wat ek gaan gee jou gaan wees 52 in die hoeveelheid. 539 00:24:20,890 --> 00:24:23,160 Ons gaan insgelyks tyd wat jy in net 'n oomblik. 540 00:24:23,160 --> 00:24:26,410 Ons gaan Andrew te gooi op die skerm hier 541 00:24:26,410 --> 00:24:28,170 so as om te kyk as jy dit doen. 542 00:24:28,170 --> 00:24:31,070 En so dat al hierdie is al hoe meer sigbaar, 543 00:24:31,070 --> 00:24:33,490 dit is die kaarte wat ek het op Amazon. 544 00:24:33,490 --> 00:24:42,861 So hulle is reeds lukraak gesorteer, en ons gaan vir jou tyd. 545 00:24:42,861 --> 00:24:44,610 En ons gaan hou dit real hierdie tyd, 546 00:24:44,610 --> 00:24:47,820 sodat ons gaan probeer om jou te druk want anders sal kry vervelige 547 00:24:47,820 --> 00:24:48,460 vinnig. 548 00:24:48,460 --> 00:24:53,860 As jy kan voortgaan 52 te sorteer elemente saam via 'n middel, wat nou. 549 00:24:53,860 --> 00:25:04,710 550 00:25:04,710 --> 00:25:07,180 >> En weer, as ons kyk na hierdie ouens doen wat, in die einde 551 00:25:07,180 --> 00:25:10,200 gaan 'n voor die hand liggend te produseer Gevolglik dink regtig 552 00:25:10,200 --> 00:25:12,962 hoe hulle mekaar om dit te doen, hoe jy dit beskryf. 553 00:25:12,962 --> 00:25:15,045 Omdat weer, dit is alle prosesse, algoritmes 554 00:25:15,045 --> 00:25:17,090 wat ons as vanselfsprekend aanvaar as 'n mens. 555 00:25:17,090 --> 00:25:22,349 Maar jy het waarskynlik lank het intuïsie, lank voor jy 556 00:25:22,349 --> 00:25:24,390 gedink om 'n Rekenaarwetenskap klas wat jy 557 00:25:24,390 --> 00:25:27,223 kan die aanvoeling gehad het met wat probleme soos hierdie op te los. 558 00:25:27,223 --> 00:25:29,560 Maar sodra jy erken die patrone en begin 559 00:25:29,560 --> 00:25:32,407 die stappe wat met die formalisering jy die oplossing van hierdie probleme, 560 00:25:32,407 --> 00:25:35,490 jy sal vind dat jy baie kan oplos meer interessant en baie meer kompleks 561 00:25:35,490 --> 00:25:39,190 probleme vinnig. 562 00:25:39,190 --> 00:25:42,351 So iemand uit die gehoor, wat ten minste een element van die algoritme 563 00:25:42,351 --> 00:25:43,350 dat hulle hier is die gebruik van? 564 00:25:43,350 --> 00:25:44,275 >> Publiek: [onhoorbaar] 565 00:25:44,275 --> 00:25:45,150 Spreker: Wat is dit? 566 00:25:45,150 --> 00:25:47,062 Publiek: Deur pak. 567 00:25:47,062 --> 00:25:47,770 Spreker: Deur pak. 568 00:25:47,770 --> 00:25:50,630 So eerste hulle die groepering al die diamante saam 569 00:25:50,630 --> 00:25:52,560 dit lyk, al die harte saam dit lyk, 570 00:25:52,560 --> 00:25:56,520 en so meer, sonder opsigte vir die nommers op die kaarte. 571 00:25:56,520 --> 00:26:00,900 En nou het hulle verskyn, byvoorbeeld, word sorteer hulle deur die nommer. 572 00:26:00,900 --> 00:26:06,870 573 00:26:06,870 --> 00:26:08,910 Baie goed. 574 00:26:08,910 --> 00:26:12,370 >> Alle reg, so wat gaan wees om die finale stap dan hier? 575 00:26:12,370 --> 00:26:16,950 Sodra ons het vier gesorteer pas, wat moet ons die vier stapels te doen 576 00:26:16,950 --> 00:26:20,059 om een ​​te bereik gesorteer dek, eenvoudig? 577 00:26:20,059 --> 00:26:21,350 Daarom moet ons dit weer saam te smelt. 578 00:26:21,350 --> 00:26:25,160 >> So daar is 'n interessante idee dat weer, daresay, is baie intuïtief selfs 579 00:26:25,160 --> 00:26:28,140 As jy dalk nooit geklap het dat die soort van etiket op dit. 580 00:26:28,140 --> 00:26:31,900 Hierdie fundamentele idee van die verdeling die probleem nie in die helfte van hierdie tyd, 581 00:26:31,900 --> 00:26:33,410 maar ten minste in vier stukke. 582 00:26:33,410 --> 00:26:36,810 Oplossing van pretty much fundamenteel dieselfde probleme 583 00:26:36,810 --> 00:26:40,480 in isolasie van mekaar, en dan die samesmelting van die resultate. 584 00:26:40,480 --> 00:26:46,940 585 00:26:46,940 --> 00:26:50,140 En, 'n uitstekende, gedoen. 586 00:26:50,140 --> 00:26:52,140 Alle reg, 'n groot ronde applous, as ons kon. 587 00:26:52,140 --> 00:26:56,480 >> [Applous] 588 00:26:56,480 --> 00:26:59,740 >> Spreker: Ek het nie 'n idee wat jy sal doen met hierdie, maar hier gaan ons. 589 00:26:59,740 --> 00:27:01,690 Baie dankie. 590 00:27:01,690 --> 00:27:04,660 So laat ons sien, twee minute en agt sekondes 591 00:27:04,660 --> 00:27:07,490 As jy wil jou vriende uit te daag. 592 00:27:07,490 --> 00:27:12,160 Wat dan gaan 'n weg te neem van hierdie 593 00:27:12,160 --> 00:27:13,830 dat ons meer in die algemeen kan benut? 594 00:27:13,830 --> 00:27:16,080 Wel, dink terug aan hierdie skikking van getalle, 595 00:27:16,080 --> 00:27:19,060 en dink nou terug aan sommige van die pseudokode ons in die verlede geskryf het, 596 00:27:19,060 --> 00:27:22,080 en dit was die pseudokode vir die oplossing van die telefoon boek probleem. 597 00:27:22,080 --> 00:27:25,150 Waardeur in pseudokode ek vervat 'n meer planmatige manier 598 00:27:25,150 --> 00:27:28,400 beskryf hoe ek het 'n baie intuïtief menslike algoritme van die verdeling van die telefoon 599 00:27:28,400 --> 00:27:31,650 boek in die helfte, herhaal, herhaal, herhaal, totdat ek iemand soos Mike Smith, 600 00:27:31,650 --> 00:27:33,790 As hy wel in die telefoon boek. 601 00:27:33,790 --> 00:27:37,610 >> Maar ek soort van gebruik wat ek sal noem 'n baie iteratiewe benadering hier 602 00:27:37,610 --> 00:27:42,160 in die besonder kennis reël 8 en lyn 11. 603 00:27:42,160 --> 00:27:46,750 Dit is bewys van 'n iteratiewe benadering, 'n herhaling benadering, 604 00:27:46,750 --> 00:27:49,040 want dit is presies die gedrag wat hulle veroorsaak. 605 00:27:49,040 --> 00:27:52,910 Diegene lyne sowel sê gaan lyn drie, en jy kan soort 606 00:27:52,910 --> 00:27:55,140 dink dat jy in jou geestesoog as 'n lus. 607 00:27:55,140 --> 00:27:59,080 Dit is wat jy vertel om terug te gaan na stap drie en herhaal, weer en weer, 608 00:27:59,080 --> 00:28:00,010 en weer. 609 00:28:00,010 --> 00:28:04,410 >> Maar wat as ons die invloed van 'n belangrike idee hier dat ons nie die laaste keer, 610 00:28:04,410 --> 00:28:10,280 en vereenvoudig reël 8 en lyn 11 en hul bure 611 00:28:10,280 --> 00:28:12,840 as net dit, in geel. 612 00:28:12,840 --> 00:28:16,480 Dit is nie fundamenteel smeer die pseudokode baie, 613 00:28:16,480 --> 00:28:20,530 maar dit is fundamenteel verander die aard van my algoritme. 614 00:28:20,530 --> 00:28:24,220 Wat ek nou sê in stap 7, in stap 10, 615 00:28:24,220 --> 00:28:29,140 is om te soek vir Mike in presies dieselfde manier, 616 00:28:29,140 --> 00:28:31,580 maar net in die linker half of die regter helfte. 617 00:28:31,580 --> 00:28:33,420 >> So met ander woorde, as Ek begin by stap een, 618 00:28:33,420 --> 00:28:36,150 haal telefoon boek, oop tot middel van die telefoon boek, kyk na die name, 619 00:28:36,150 --> 00:28:39,010 As Smith is onder Naam, bel Mike, anders 620 00:28:39,010 --> 00:28:44,340 As Smith is vroeër in 'n boek, stap sewe soek vir Mike in die linker helfte van boek. 621 00:28:44,340 --> 00:28:47,130 Maar daardie soort van voel dit laat my hang, reg? 622 00:28:47,130 --> 00:28:49,240 In geel, is 'n onderrig, maar hoe doen ek 623 00:28:49,240 --> 00:28:51,870 soek vir Mike in die linker helfte van die telefoon boek? 624 00:28:51,870 --> 00:28:54,210 Waar Ek het nie 'n algoritme waarmee ek 625 00:28:54,210 --> 00:28:57,100 kan soek vir iemand soos Mike Smith? 626 00:28:57,100 --> 00:28:58,980 Wel, dit is staar ons in die gesig. 627 00:28:58,980 --> 00:29:03,090 Ek kan letterlik gebruik presies dieselfde program effektief gaan na die top 628 00:29:03,090 --> 00:29:06,490 weer en weer loop dieselfde reëls van die kode. 629 00:29:06,490 --> 00:29:10,610 >> So selfs al is dit moet voel soos 'n bietjie van 'n sikliese definisie 630 00:29:10,610 --> 00:29:13,480 waar jy beantwoord iemand se vraag deur net soort van om te vra 631 00:29:13,480 --> 00:29:15,990 dieselfde vraag weer, soos hoekom, hoekom, hoekom? 632 00:29:15,990 --> 00:29:21,580 Die werklikheid is, want ons het hard gekodeer 'n paar van die spesiale lyne, stap 4, 633 00:29:21,580 --> 00:29:25,320 wat 'n as, en stap 12, wat is effektief 'n ander tak, 634 00:29:25,320 --> 00:29:30,120 want ons het die noodhulp maatreëls, hierdie algoritme sal beëindig indien ons 635 00:29:30,120 --> 00:29:32,050 vind Mike, of as ons dit nie doen nie. 636 00:29:32,050 --> 00:29:36,810 Maar in stap 7 en 10 nou, ons het wat ons sal 'n rekursiewe algoritme noem. 637 00:29:36,810 --> 00:29:40,420 En rekursie is inderdaad 'n kragtige idee dit is 'n bietjie verstand buig op die eerste, 638 00:29:40,420 --> 00:29:42,500 dat ons kan nou aansoek doen as volg. 639 00:29:42,500 --> 00:29:46,600 >> Merge soort sal die laaste soort wees wat ons kyk na, ten minste in die klas formeel. 640 00:29:46,600 --> 00:29:50,040 En dit is fundamenteel verskillende van dié laaste drie, en beslis 641 00:29:50,040 --> 00:29:52,140 laaste vier as ons sluit bogosort. 642 00:29:52,140 --> 00:29:54,810 Hier is die pseudokode vir merge soort. 643 00:29:54,810 --> 00:30:00,170 Wanneer oor die toevoer van n elemente, so gegee 'n verskeidenheid van grootte n, as n minder as 2, 644 00:30:00,170 --> 00:30:01,040 terug te keer. 645 00:30:01,040 --> 00:30:03,610 So hoekom het ek dat gesonde verstand gaan eerste? 646 00:30:03,610 --> 00:30:09,477 Wat is die implikasie as ek vir julle 'n skikking waarvan die lengte n is minder as 2? 647 00:30:09,477 --> 00:30:11,060 Dit is reeds gesorteer, natuurlik, reg? 648 00:30:11,060 --> 00:30:13,640 Omdat die lys óf een element wat trivially 649 00:30:13,640 --> 00:30:15,180 gesorteer, want dit is die enigste ding wat daar is. 650 00:30:15,180 --> 00:30:18,138 Of, is dit van die grootte nul, wat beteken daar is niks om te sorteer, so deur die natuur 651 00:30:18,138 --> 00:30:18,720 dit gesorteer is. 652 00:30:18,720 --> 00:30:20,410 Daar is net niks verkeerd daar. 653 00:30:20,410 --> 00:30:22,310 So dit is ons sogenaamde basis geval. 654 00:30:22,310 --> 00:30:24,440 >> Dit is soortgelyk in die gees na wat ons gedoen het met Mike. 655 00:30:24,440 --> 00:30:26,023 As Mike's in die telefoon boek, bel hom. 656 00:30:26,023 --> 00:30:27,740 As hy nie daar is nie, gee. 657 00:30:27,740 --> 00:30:31,240 Dit is 'n sogenaamde basis geval, om seker te maak hierdie algoritme aan die einde van die dag 658 00:30:31,240 --> 00:30:33,540 stop in sekere omstandighede. 659 00:30:33,540 --> 00:30:37,890 >> Maar hier is die sprong van die geloof nou, anders, sorteer die linker helfte van die elemente, 660 00:30:37,890 --> 00:30:39,740 sorteer dan die reg helfte van die elemente, 661 00:30:39,740 --> 00:30:41,189 en dan saam te smelt die gesorteer helftes. 662 00:30:41,189 --> 00:30:43,230 En hier is waar dit voel soos ons Copping uit. 663 00:30:43,230 --> 00:30:46,900 Ek het jou gevra om te sorteer N elemente, en ek is 664 00:30:46,900 --> 00:30:50,712 sê, OK, moenie dit deur sorteer links en sorteer die regte. 665 00:30:50,712 --> 00:30:52,420 Maar ek sê een ander ding, en dit 666 00:30:52,420 --> 00:30:55,530 is die sleutel tema lyk dit in die intuïsie tot dusver 667 00:30:55,530 --> 00:30:57,380 daar is die derde stap van die samesmelting. 668 00:30:57,380 --> 00:31:00,430 Watter selfs al is dit lyk so dom in die gees, 669 00:31:00,430 --> 00:31:02,320 soos net saamsmelt dinge saam, dit lyk 670 00:31:02,320 --> 00:31:05,380 'n belangrike stap in die rigting van die wees kombinering van twee probleme wat 671 00:31:05,380 --> 00:31:07,330 is uiteindelik in die helfte verdeel. 672 00:31:07,330 --> 00:31:12,090 >> So saamsmelt soort, laat ons dit doen, as jy sal humor my, met 'n meer demonstrasie, 673 00:31:12,090 --> 00:31:14,730 Net sodat ons het 'n paar getalle te werk. 674 00:31:14,730 --> 00:31:19,470 Kan ek ruil agt stres balle vir agt mense? 675 00:31:19,470 --> 00:31:29,320 Alle reg, hoe om jou drie, jy vier in hierdie afdeling, vyf, ses, en laat 676 00:31:29,320 --> 00:31:30,720 nie 7, 8, kom op. 677 00:31:30,720 --> 00:31:35,120 678 00:31:35,120 --> 00:31:36,520 OK, ja OK. 679 00:31:36,520 --> 00:31:38,640 Minus 8, daar gaan ons, plus 1. 680 00:31:38,640 --> 00:31:39,150 Uitstekend. 681 00:31:39,150 --> 00:31:42,000 Alle regte kom, laat se vinnig gee jou nommers. 682 00:31:42,000 --> 00:31:50,800 Nommer twee, nommer drie, nommer vier, nommer vyf, ses, sewe, agt. 683 00:31:50,800 --> 00:31:52,140 Ek het agt korrek hierdie tyd. 684 00:31:52,140 --> 00:31:56,390 >> OK, so voort te gaan as jy kan, en laat se sorteer in die oorspronklike bevel 685 00:31:56,390 --> 00:31:59,810 dat ons gister gehad het wat gelyk soos hierdie, as jy nie sou omgee. 686 00:31:59,810 --> 00:32:03,620 En kom ons doen dit in die voorkant van die tafel. 687 00:32:03,620 --> 00:32:06,510 Alle reg, sodat saamsmelt soort. 688 00:32:06,510 --> 00:32:08,820 Dit is waar dit gaan soort te kry interessante, 689 00:32:08,820 --> 00:32:12,800 omdat ek lyk te gee myself so veel minder inligting vandag. 690 00:32:12,800 --> 00:32:15,149 >> So saamsmelt soort in die eerste toevoer van n elemente, 691 00:32:15,149 --> 00:32:18,440 en is natuurlik nie minder nie as twee is, is dit agt, so ek het 'n paar meer werk te doen. 692 00:32:18,440 --> 00:32:21,140 So nou verstandelik ons ​​as 'n klas is nou in die ander tak, 693 00:32:21,140 --> 00:32:22,540 wat beteken drie stappe. 694 00:32:22,540 --> 00:32:25,017 Eerstens, ek het die te sorteer linker helfte van die elemente. 695 00:32:25,017 --> 00:32:26,350 So, hoe gaan ek oor om dit te doen? 696 00:32:26,350 --> 00:32:28,950 Wel, ek gaan soort verstandelik verdeel die lys hier, 697 00:32:28,950 --> 00:32:30,700 jy hoef nie te fisies beweeg, en ek is 698 00:32:30,700 --> 00:32:33,180 gaan net fokus op die linker helfte van die elemente hier. 699 00:32:33,180 --> 00:32:36,770 So, hoe gaan ek te sorteer 'n lys van nou grootte vier? 700 00:32:36,770 --> 00:32:38,730 Wat is my algoritme? 701 00:32:38,730 --> 00:32:42,580 Eerste Ek is so is n minder as twee nie, so ek gaan na die ander blok weer. 702 00:32:42,580 --> 00:32:43,900 Sorteer links helfte van elemente. 703 00:32:43,900 --> 00:32:45,608 >> So nou weer, verstandelik, en dit is waar 704 00:32:45,608 --> 00:32:49,550 jy het 'n baie om te val geestelike geskiedenis, as jy wil. 705 00:32:49,550 --> 00:32:51,940 Nou is ek sorteer links helfte van die linker helfte. 706 00:32:51,940 --> 00:32:57,000 Alle reg, so nou is ek roep my dieselfde merge sorteer algoritme, is N minder as twee? 707 00:32:57,000 --> 00:33:00,590 Nee, dit is twee, so ek het om te sorteer die linker helfte en die regter helfte. 708 00:33:00,590 --> 00:33:02,042 So hier gaan ons, sorteer die linker helfte. 709 00:33:02,042 --> 00:33:03,750 Hoekom doen jy nie net neem 'n stap vorentoe. 710 00:33:03,750 --> 00:33:04,415 Wat is jou naam? 711 00:33:04,415 --> 00:33:04,860 >> Publiek: Darren. 712 00:33:04,860 --> 00:33:05,260 >> Spreker: Dan. 713 00:33:05,260 --> 00:33:06,040 Dan het na vore getree. 714 00:33:06,040 --> 00:33:06,748 >> Publiek: Darren. 715 00:33:06,748 --> 00:33:09,000 Spreker: Darren, gedoen. 716 00:33:09,000 --> 00:33:10,090 Het jy sê Darren of Dan? 717 00:33:10,090 --> 00:33:10,550 >> Publiek: Darren. 718 00:33:10,550 --> 00:33:11,216 >> Spreker: Darren. 719 00:33:11,216 --> 00:33:14,422 OK, Darren het weereens vorentoe en hy is nou uitgesorteer. 720 00:33:14,422 --> 00:33:16,130 En dit is amper 'n ligsinnig eis, reg? 721 00:33:16,130 --> 00:33:18,862 Ek het nie regtig lyk nie te wees die bereiking niks nie, maar laat ons voortgaan. 722 00:33:18,862 --> 00:33:20,820 Nou kan ek sorteer die regte helfte van die elemente. 723 00:33:20,820 --> 00:33:21,200 Wat is jou naam? 724 00:33:21,200 --> 00:33:21,690 >> Publiek: Lukas. 725 00:33:21,690 --> 00:33:22,273 >> Spreker: Lukas. 726 00:33:22,273 --> 00:33:23,400 Kom, stap vorentoe. 727 00:33:23,400 --> 00:33:25,640 Gedoen het, het ek gesorteer het Lukas. 728 00:33:25,640 --> 00:33:28,570 Die linker helfte is nou uitgesorteer en die regter helfte is nou uitgesorteer, 729 00:33:28,570 --> 00:33:30,770 maar weer, daar is 'n belangrike stap hier. 730 00:33:30,770 --> 00:33:32,940 Wat moet ek volgende doen? 731 00:33:32,940 --> 00:33:33,941 Voeg die gesorteer helftes. 732 00:33:33,941 --> 00:33:36,648 Nou gaan ons net almal heen en weer op hierdie manier, 733 00:33:36,648 --> 00:33:38,620 want ek soort van moet paar vrye ruimte. 734 00:33:38,620 --> 00:33:40,411 Dit is amper soos hierdie ouens is op 'n tafel, 735 00:33:40,411 --> 00:33:42,460 en ek moet 'n paar kamer om dit te skuif rond op. 736 00:33:42,460 --> 00:33:44,170 So ek gaan om saam te smelt julle deur te kyk 737 00:33:44,170 --> 00:33:45,960 op die linker helfte en die regter helfte. 738 00:33:45,960 --> 00:33:48,740 En wat natuurlik kom eerste, links half-of die regterkant helfte? 739 00:33:48,740 --> 00:33:52,710 So reg helfte, so laat beweeg Lukas oor hier te Darren se oorspronklike posisie. 740 00:33:52,710 --> 00:33:57,640 En nou is hulle linker helfte om saam te smelt in, Darren gaan reg daar te beweeg. 741 00:33:57,640 --> 00:33:59,750 >> So voel soos byna 'n borrel soort effek, 742 00:33:59,750 --> 00:34:02,482 maar my fundamentele algoritme baie verskillende hierdie tyd. 743 00:34:02,482 --> 00:34:04,815 Maar nou is waar dinge 'n klein irriterende omdat jy 744 00:34:04,815 --> 00:34:06,810 moet geestelik rewind waar het ek laat vaar. 745 00:34:06,810 --> 00:34:09,893 Ek het net saamgesmelt het om die gesorteerde helftes, wat beteken ek is waar in my algoritme? 746 00:34:09,893 --> 00:34:12,229 747 00:34:12,229 --> 00:34:13,770 Ek het die reg om die helfte te sorteer, reg? 748 00:34:13,770 --> 00:34:15,910 >> As jy rewind, letterlik op die video, sal jy 749 00:34:15,910 --> 00:34:18,339 sien dat ons aan hierdie punt van Lukas en Darren 750 00:34:18,339 --> 00:34:21,370 deur sorteer links helfte van die linker helfte. 751 00:34:21,370 --> 00:34:23,430 Daarna het ons saamgesmelt diegene gesorteer helftes, wat 752 00:34:23,430 --> 00:34:27,941 beteken dat die volgende stap is 'n soort van die regter helfte van die linker helfte. 753 00:34:27,941 --> 00:34:29,649 Alle reg, so laat doen dit vinniger. 754 00:34:29,649 --> 00:34:33,282 Alle reg, ses, ek gaan om te beweer jy is nou uitgesorteer, kom vorentoe. 755 00:34:33,282 --> 00:34:33,990 Wat is jou naam? 756 00:34:33,990 --> 00:34:34,589 >> Publiek: Adriano. 757 00:34:34,589 --> 00:34:35,200 >> Spreker: Adriano. 758 00:34:35,200 --> 00:34:36,010 Adriano is nou uitgesorteer. 759 00:34:36,010 --> 00:34:36,450 En wat is jou naam? 760 00:34:36,450 --> 00:34:37,080 >> Publiek: Alex. 761 00:34:37,080 --> 00:34:38,379 >> Spreker: Alex is nou uitgesorteer. 762 00:34:38,379 --> 00:34:40,750 Linker helfte, reg helfte, Wat is die finale stap? 763 00:34:40,750 --> 00:34:41,250 Saam te smelt. 764 00:34:41,250 --> 00:34:44,310 Redelik triviaal, so ek is gaan om saam te smelt in ses, 765 00:34:44,310 --> 00:34:46,930 'n stap terug, agt, 'n stap terug. 766 00:34:46,930 --> 00:34:49,530 En nou sien dit is 'n nuttige afhaal, wat 767 00:34:49,530 --> 00:34:53,930 nou waar is oor die linker helfte van die lys, ongeag hoe ons begin het? 768 00:34:53,930 --> 00:34:55,090 Dit is gesorteer. 769 00:34:55,090 --> 00:34:57,750 >> Nou is dit nie gesorteer in die groot skema van dinge, 770 00:34:57,750 --> 00:35:00,250 maar dit is 'n onafhanklike gesorteer van die ander helfte. 771 00:35:00,250 --> 00:35:04,100 Nou wat stap ek op as ek hou omwikkelen hoe die storie begin? 772 00:35:04,100 --> 00:35:05,680 Nou het ek die reg om die helfte te sorteer. 773 00:35:05,680 --> 00:35:07,630 So nou is ons weg by die die begin van die storie, 774 00:35:07,630 --> 00:35:08,921 en laat ons doen dit vinniger. 775 00:35:08,921 --> 00:35:11,320 So ek gaan die te sorteer regter helfte van die hele lys. 776 00:35:11,320 --> 00:35:13,060 Wat is die volgende stap? 777 00:35:13,060 --> 00:35:15,840 Sorteer die linker helfte van die regter helfte. 778 00:35:15,840 --> 00:35:18,715 Sorteer die linker helfte van die linker helfte van die regter helfte. 779 00:35:18,715 --> 00:35:19,590 En wat is jou naam? 780 00:35:19,590 --> 00:35:20,230 >> Publiek: Omar. 781 00:35:20,230 --> 00:35:21,970 >> Spreker: Omar, stap vorentoe, gedoen. 782 00:35:21,970 --> 00:35:22,860 Linker helfte is gesorteer. 783 00:35:22,860 --> 00:35:23,330 En wat is jou naam? 784 00:35:23,330 --> 00:35:23,820 >> Publiek: Chris. 785 00:35:23,820 --> 00:35:25,620 >> Spreker: Chris, neem 'n stap vorentoe, jy is nou uitgesorteer. 786 00:35:25,620 --> 00:35:27,010 Wat is die belangrike stap nou? 787 00:35:27,010 --> 00:35:27,510 Saam te smelt. 788 00:35:27,510 --> 00:35:30,509 So 'n mens gaan om saam te smelt in plek hier, as jy kan 'n stap terug te neem, 789 00:35:30,509 --> 00:35:32,930 en drie gaan 'n stap terug, saam te smelt. 790 00:35:32,930 --> 00:35:38,080 So het die linker helfte van die regter helfte, is nou uitgesorteer. 791 00:35:38,080 --> 00:35:41,747 Om eerlik te wees, hierdie algoritme voel soos ons mors manier om meer tyd as voorheen, 792 00:35:41,747 --> 00:35:44,830 maar as ons dit gedoen het in reële tyd, sal ons sien wat die wegneemetes gaan wees. 793 00:35:44,830 --> 00:35:47,970 Nou hier is ek, reg helfte van die regter helfte, 794 00:35:47,970 --> 00:35:50,170 Laat my gaan voort en sorteer die linker helfte. 795 00:35:50,170 --> 00:35:51,482 Stap vorentoe, wat is jou naam? 796 00:35:51,482 --> 00:35:52,190 Publiek: Ramsey. 797 00:35:52,190 --> 00:35:53,210 Spreker: Ramsey is nou uitgesorteer. 798 00:35:53,210 --> 00:35:53,570 Wat is jou naam? 799 00:35:53,570 --> 00:35:54,200 >> Publiek: Marina. 800 00:35:54,200 --> 00:35:57,033 >> Spreker: Marina is nou uitgesorteer as Wel, as jy 'n stap vorentoe. 801 00:35:57,033 --> 00:36:00,690 Belangrike stap hier is nou saam te smelt, ek is gaan om uit te ruk uit my twee lyste 802 00:36:00,690 --> 00:36:01,720 links en regs. 803 00:36:01,720 --> 00:36:05,150 Vyf gaan eerste kom, en sewe gaan volgende kom. 804 00:36:05,150 --> 00:36:06,410 En weer, dit is doelbewuste. 805 00:36:06,410 --> 00:36:08,535 Die feit dat hulle met treë vorentoe en agtertoe 806 00:36:08,535 --> 00:36:12,997 is bedoel om voor te stel dat ons nie kan doen hierdie algoritme in plek so maklik 807 00:36:12,997 --> 00:36:15,830 as borrel soort, en seleksie soort, en voeg soort waar ons net 808 00:36:15,830 --> 00:36:16,960 gehou uitruiling mense. 809 00:36:16,960 --> 00:36:19,940 Ek het letterlik 'n soort van nuuts af vraestel waarin 810 00:36:19,940 --> 00:36:21,827 hierdie mense te sit Terwyl ek nie die samesmelting, 811 00:36:21,827 --> 00:36:23,410 en dan kan ek dit terug in plek gestel. 812 00:36:23,410 --> 00:36:27,260 En dit is die sleutel, want ek is met behulp van ' nuwe hulpbron, ruimte, nie net die tyd. 813 00:36:27,260 --> 00:36:28,270 >> OK, dit is amazing. 814 00:36:28,270 --> 00:36:32,050 Linker helfte is gesorteer, reg helfte gesorteer nou dat die sleutel samesmelting stap. 815 00:36:32,050 --> 00:36:33,450 Hoe gaan ek dit om saam te smelt? 816 00:36:33,450 --> 00:36:35,470 So as jy volg my linkerhand en regterhand 817 00:36:35,470 --> 00:36:38,930 Ek gaan my linkerhand te wys op die linker helfte, my regterhand 818 00:36:38,930 --> 00:36:42,680 op die regte helfte, en nou moet ek besluit stap vir stap wat om saam te smelt in. 819 00:36:42,680 --> 00:36:44,650 Wie kom natuurlik eerste? 820 00:36:44,650 --> 00:36:45,150 Nommer een. 821 00:36:45,150 --> 00:36:47,327 So kom hier, Hier is ons kras pad. 822 00:36:47,327 --> 00:36:49,910 So nou nommer een, en 'n kennisgewing wat ek doen met my regterhand 823 00:36:49,910 --> 00:36:54,152 Ek gaan my regterhand een te skuif stap oor te wys nommer drie, 824 00:36:54,152 --> 00:36:55,860 en nou het ek te maak dieselfde besluit. 825 00:36:55,860 --> 00:36:58,387 En eintlik staan ​​reg in voor Lukas hier as jy kan, 826 00:36:58,387 --> 00:36:59,720 want dit is ons kras pad. 827 00:36:59,720 --> 00:37:00,610 So wat is volgende? 828 00:37:00,610 --> 00:37:05,000 Ons het Lukas met nommer twee of Chris met nommer drie. 829 00:37:05,000 --> 00:37:07,460 Dit is duidelik dat Lukas, die aantal twee, so jy hier kom. 830 00:37:07,460 --> 00:37:11,270 >> Maar my linkerhand nou gaan word aangevul te wys op Darren, 831 00:37:11,270 --> 00:37:15,160 en hier is die sleutel weg te neem met samesmelting, ek gaan om te hou om dit te doen, 832 00:37:15,160 --> 00:37:17,340 natuurlik, as jy die soort van volg die logika. 833 00:37:17,340 --> 00:37:19,670 Maar my hande is nooit gaan agteruit te gaan, 834 00:37:19,670 --> 00:37:23,861 wat beteken ek altyd net beweeg na links met my samesmelting proses, 835 00:37:23,861 --> 00:37:26,360 en wat gaan die sleutel te wees ons ontleding in net 'n oomblik. 836 00:37:26,360 --> 00:37:27,859 >> So laat ons nou klaar is met hierdie vinnig. 837 00:37:27,859 --> 00:37:31,650 So drie kom volgende, dan vier kom volgende, 838 00:37:31,650 --> 00:37:38,750 en nou vyf kom volgende, dan is ses, en sewe, en dan uiteindelik agt. 839 00:37:38,750 --> 00:37:42,960 Voel soos die stadigste algoritme nog, maar nie as ons werklik 840 00:37:42,960 --> 00:37:45,510 loop dit op dieselfde soort van die klok spoed, so te 841 00:37:45,510 --> 00:37:48,106 praat, met dieselfde merk klok as tevore. 842 00:37:48,106 --> 00:37:48,605 Hoekom? 843 00:37:48,605 --> 00:37:51,100 Wel, Kom ons neem 'n kyk na die eindresultaat. 844 00:37:51,100 --> 00:37:56,990 >> Kom ons gaan terug oor hier, laat my trek 'n demonstrasie visueel 845 00:37:56,990 --> 00:37:59,030 van wat ons nou net gedoen het. 846 00:37:59,030 --> 00:38:06,110 Inzoomen hier, op hierdie bladsy hier, vertel Firefox 847 00:38:06,110 --> 00:38:08,200 dat ons wil tou in hierdie boks, laat 848 00:38:08,200 --> 00:38:11,260 sê borrel soort waarmee Ons is nou goed bekend, 849 00:38:11,260 --> 00:38:14,130 seleksie soort, wat ook 'n redelik eenvoudig een, 850 00:38:14,130 --> 00:38:18,250 en nou vandag se merge soort, wat sal ons klimaks eindig nie. 851 00:38:18,250 --> 00:38:21,530 Die rede waarom dit het soveel meer hier met mense en my mondelings is, 852 00:38:21,530 --> 00:38:23,480 natuurlik, ek verduidelik elke stap. 853 00:38:23,480 --> 00:38:26,920 Maar as jy net voer hierdie, baie soos ons gedoen het borrel soort en keuring 854 00:38:26,920 --> 00:38:30,890 soort nie net visueel, kyk net hoeveel meer doeltreffend 855 00:38:30,890 --> 00:38:33,330 hierdie benutting van afdeling en verower 856 00:38:33,330 --> 00:38:39,150 kan word wanneer dit toegepas word om 'n stel data wat nie eens grootte agt, maar selfs baie, 857 00:38:39,150 --> 00:38:39,970 veel groter. 858 00:38:39,970 --> 00:38:44,585 Ek gee jou saamsmelt soort, langs kant met hierdie ander algoritmes. 859 00:38:44,585 --> 00:38:56,364 860 00:38:56,364 --> 00:38:58,530 Dit gaan pynlik om te kry vinnig, en die einde 861 00:38:58,530 --> 00:39:00,890 is nie besonder klimaks, hulle het net beland gesorteer. 862 00:39:00,890 --> 00:39:05,280 Maar die sleutel weg te neem is dat Kyk hoe baie vinniger smelt soort 863 00:39:05,280 --> 00:39:08,110 was nie, tensy jy dink ek is net soort van die geknoei met jou. 864 00:39:08,110 --> 00:39:13,100 As ons dit doen 'n laaste keer, Kom ons laai dit, laat ons terug te gaan 865 00:39:13,100 --> 00:39:14,960 en kies borrel soort, en net vir die skop, 866 00:39:14,960 --> 00:39:17,330 laat kies inplanting soort, net vir 'n goeie maatreël. 867 00:39:17,330 --> 00:39:20,020 En hierdie keer weer, laat kies merge soort en laat 868 00:39:20,020 --> 00:39:21,595 eintlik loop hierdie kant van die kant. 869 00:39:21,595 --> 00:39:24,140 870 00:39:24,140 --> 00:39:26,930 >> En dit is nie, in werklikheid, 'n gelukskoot. 871 00:39:26,930 --> 00:39:31,140 Wat ek gedoen het, is effektief ek het verdeel my insette in die helfte, weer, 872 00:39:31,140 --> 00:39:32,240 en weer en weer. 873 00:39:32,240 --> 00:39:35,590 En daar is net so baie keer jy kan verdeel jou insette in die helfte, links 874 00:39:35,590 --> 00:39:36,240 en regs. 875 00:39:36,240 --> 00:39:39,425 Wat is die formule wat ons hou sien wat beskryf die afdeling in die helfte 876 00:39:39,425 --> 00:39:41,050 weer en weer, en weer en weer? 877 00:39:41,050 --> 00:39:41,890 >> GEHOOR: Meld n. 878 00:39:41,890 --> 00:39:42,760 >> Spreker: Teken n. 879 00:39:42,760 --> 00:39:46,300 Maar dan is daar een ander belangrike stap, hierdie algoritme nie inteken n stappe. 880 00:39:46,300 --> 00:39:48,992 As dit is eers inteken N stappe, ons in die dieselfde probleem sou wees 881 00:39:48,992 --> 00:39:51,200 as voor waar ons nie kan seker alles is gesorteer. 882 00:39:51,200 --> 00:39:54,480 Jy moet minimaal kyk na n elemente om seker te wees n elemente word gesorteer, 883 00:39:54,480 --> 00:39:55,950 anders is dit 'n sprong van geloof. 884 00:39:55,950 --> 00:39:59,810 >> So dit is minimaal log N stappe, maar wat oor hierdie belangrike samesmelting stap 885 00:39:59,810 --> 00:40:04,370 waar ek saamgesmelt my linker helfte en regs helfte en loop oor die verhoog? 886 00:40:04,370 --> 00:40:06,980 Hoeveel treë is dat om saam te smelt? 887 00:40:06,980 --> 00:40:10,150 Dit is n, maar ek het nie net saam te smelt die laaste keer. 888 00:40:10,150 --> 00:40:15,089 Op elk van hierdie geneste oproepe, op elke van daardie nes fusies, het ek nog gesorteer. 889 00:40:15,089 --> 00:40:18,380 Ek saamgesmelt hierdie twee ouens, dan is hierdie twee ouens, dan is hierdie twee ouens en so meer. 890 00:40:18,380 --> 00:40:19,955 >> So ek het weer en weer saam te smelt. 891 00:40:19,955 --> 00:40:20,580 Hoeveel keer? 892 00:40:20,580 --> 00:40:23,510 So elke keer as ek verdeel die lys in die helfte, het ek 'n samesmelting. 893 00:40:23,510 --> 00:40:25,460 Verdeel die lys in die helfte, doen 'n samesmelting. 894 00:40:25,460 --> 00:40:28,570 So as die verdeling van die lys kan gedoen word log n keer, 895 00:40:28,570 --> 00:40:33,880 en die samesmelting neem uiteindelik n stappe, wat kan nou die boonste 896 00:40:33,880 --> 00:40:37,000 gebind aan die gang tyd van ons algoritme? 897 00:40:37,000 --> 00:40:37,980 n log n. 898 00:40:37,980 --> 00:40:40,560 >> En inderdaad, dit is wat Ons het hier behaal. 899 00:40:40,560 --> 00:40:44,650 So het die gevoel dat jy sien visueel wanneer hierdie drie dinge loop langs mekaar 900 00:40:44,650 --> 00:40:47,930 is n teen n vierkant vierkantig teen n log n. 901 00:40:47,930 --> 00:40:51,010 Watter fundamenteel ons sal sien, nie net vandag nie, maar in die toekoms, 902 00:40:51,010 --> 00:40:52,760 is baie, baie vinniger. 903 00:40:52,760 --> 00:40:56,010 'N rondte van applous vir hierdie ouens, Ek sal hulle beloon met stress balle. 904 00:40:56,010 --> 00:41:00,260 Kom ons verdaag hier vandag, en ons sal jy sien op Maandag. 905 00:41:00,260 --> 00:41:02,255