1 00:00:00,000 --> 00:00:11,100 >> [Reproducció de música] 2 00:00:11,100 --> 00:00:11,490 >> DAVID J. Malan: Molt bé. 3 00:00:11,490 --> 00:00:12,170 Així que benvinguda. 4 00:00:12,170 --> 00:00:15,180 Això és CS50 i el és Al final de la tercera setmana. 5 00:00:15,180 --> 00:00:17,770 >> Així que recorda, en les últimes setmanes, hem passat una mica de 6 00:00:17,770 --> 00:00:20,820 vegada en C, en la programació, a la sintaxi. 7 00:00:20,820 --> 00:00:24,680 I és molt normal, si encara lluitant amb Problemes de 2, per ser 8 00:00:24,680 --> 00:00:25,950 colpejar el cap contra la paret. 9 00:00:25,950 --> 00:00:28,310 És missatges d'error críptic d'aspecte i els errors que 10 00:00:28,310 --> 00:00:29,220 no puc perseguir. 11 00:00:29,220 --> 00:00:32,310 Perquè, pot estar segur, que en tan sols un temps d'algunes setmanes de mirar cap enrere en 12 00:00:32,310 --> 00:00:35,930 coses com César, [? V-Genair,?] fins i tot crack, i 13 00:00:35,930 --> 00:00:40,050 compte de fins on ha arribat en un curt període de temps. 14 00:00:40,050 --> 00:00:43,670 Així que si et serveix de consol, s'aguanta per ara. 15 00:00:43,670 --> 00:00:46,610 >> Avui, però, vam començar la transició a les coses d'alt nivell. 16 00:00:46,610 --> 00:00:49,820 I vam començar a donar per fet que Vostès saben com programar, o 17 00:00:49,820 --> 00:00:52,090 menys els començaments de la aquest nivell de comoditat. 18 00:00:52,090 --> 00:00:56,520 I anem a començar a considerar com podem anar sobre el disseny de programes més 19 00:00:56,520 --> 00:00:57,440 efectivament. 20 00:00:57,440 --> 00:01:01,090 Com es pot anar sobre l'optimització de la eficiència dels algoritmes i 21 00:01:01,090 --> 00:01:03,110 generalment la solució més problemes interessants. 22 00:01:03,110 --> 00:01:06,850 I començant a donar per fet que, Si volguéssim, podríem codificar qualsevol 23 00:01:06,850 --> 00:01:08,350 dels exemples que tenim en ment. 24 00:01:08,350 --> 00:01:11,430 Així que avui, no toquem el teclat per a qualsevol tipus de codi. 25 00:01:11,430 --> 00:01:15,150 Serà nivell molt més alt, i en última instància, sobre la resolució de problemes. 26 00:01:15,150 --> 00:01:20,490 >> Així que per arribar a aquest punt, permetin-me proposar que els següents set 27 00:01:20,490 --> 00:01:24,290 rectangles representen set portes, darrere que són un munt de 28 00:01:24,290 --> 00:01:26,340 nombres, entre els quals és el número 50. 29 00:01:26,340 --> 00:01:30,470 Permetin-me en aquest projecte tan pantalla d'aquí també. 30 00:01:30,470 --> 00:01:36,770 I proposem que necessitem un voluntari que ajudar-me a trobar un nombre davant de 31 00:01:36,770 --> 00:01:38,140 l'Internet per veure. 32 00:01:38,140 --> 00:01:40,755 Anem amunt, a la rosa. 33 00:01:40,755 --> 00:01:43,050 Està bé. 34 00:01:43,050 --> 00:01:43,930 Com et dius? 35 00:01:43,930 --> 00:01:44,850 >> JENNIFER: [inaudible] 36 00:01:44,850 --> 00:01:45,170 >> DAVID J. Malan: Com? 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 D'acord, Jennifer. 40 00:01:46,980 --> 00:01:47,630 Gust a conèixer-lo. 41 00:01:47,630 --> 00:01:48,370 Anem amunt. 42 00:01:48,370 --> 00:01:52,430 Així que ets aquí hi ha set portes, i el que M'agradaria que facis per nosaltres aquí, 43 00:01:52,430 --> 00:01:56,560 davant de tots els seus companys de classe, nosaltres es troba el número 50. 44 00:01:56,560 --> 00:02:00,860 Per trobar un nombre, vostè pot mirar darrere qualsevol d'aquestes portes amb un simple toc 45 00:02:00,860 --> 00:02:03,030 en una de les portes, i es revelarà el seu nombre. 46 00:02:03,030 --> 00:02:06,080 I anem a veure la rapidesa amb què ens pot trobar al número 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 Molt ben fet. 54 00:02:17,350 --> 00:02:18,040 Està bé. 55 00:02:18,040 --> 00:02:19,906 Ronda d'aplaudiments per Jennifer. 56 00:02:19,906 --> 00:02:21,530 >> [Aplaudiments] 57 00:02:21,530 --> 00:02:22,320 >> Està bé. 58 00:02:22,320 --> 00:02:25,254 Llavors, quin va ser la seva estratègia per trobar el nombre, 50? 59 00:02:25,254 --> 00:02:27,222 >> JENNIFER: Um, vaig pensar que potser si - 60 00:02:27,222 --> 00:02:27,714 [Inaudible] 61 00:02:27,714 --> 00:02:28,206 >> DAVID J. Malan: Oh. 62 00:02:28,206 --> 00:02:29,630 Doni-li un segon. 63 00:02:29,630 --> 00:02:32,420 Així va ser la seva estratègia per trobar el nombre, 50? 64 00:02:32,420 --> 00:02:34,760 >> JENNIFER: Així que em poso al començant a veure el que el primer número 65 00:02:34,760 --> 00:02:38,590 era, i llavors vaig pensar, potser si que estan ordenats, que seguiré 66 00:02:38,590 --> 00:02:39,970 tocant més amunt? 67 00:02:39,970 --> 00:02:40,140 >> DAVID J. Malan: OK. 68 00:02:40,140 --> 00:02:42,910 I sembla que hem trobat de ser el cas. 69 00:02:42,910 --> 00:02:45,670 Encara que, anem a pelar les capes només una mica, i vol anar 70 00:02:45,670 --> 00:02:47,640 endavant i revelar les altres portes que podria haver triat? 71 00:02:47,640 --> 00:02:50,400 72 00:02:50,400 --> 00:02:51,712 >> JENNIFER: Oh, estimat. 73 00:02:51,712 --> 00:02:53,128 >> DAVID J. Malan: Ah. 74 00:02:53,128 --> 00:02:54,280 >> JENNIFER: Així que vaig tenir sort. 75 00:02:54,280 --> 00:02:55,270 >> DAVID J. Malan: Així que tens sort. 76 00:02:55,270 --> 00:02:55,710 Està bé. 77 00:02:55,710 --> 00:02:56,795 Així que no està malament. 78 00:02:56,795 --> 00:02:58,750 Però això és una interessant idea, oi? 79 00:02:58,750 --> 00:03:01,870 Si vostè va assumir, i ho va fer arribar, de fet, una mica de sort allà. 80 00:03:01,870 --> 00:03:05,350 Però si se suposa que les xifres eren ordenada, pot ser més precís 81 00:03:05,350 --> 00:03:08,750 com a la forma en què influenciats seu comportament? 82 00:03:08,750 --> 00:03:11,715 >> JENNIFER: Així que si que estaven ordenats, em vaig pensar que potser menys a més. 83 00:03:11,715 --> 00:03:11,970 >> DAVID J. Malan: OK. 84 00:03:11,970 --> 00:03:15,260 >> JENNIFER: O si això va acabar sent molt gran, llavors major a menor. 85 00:03:15,260 --> 00:03:15,540 >> DAVID J. Malan: OK. 86 00:03:15,540 --> 00:03:18,170 Així major a menor, o més petit al més gran. 87 00:03:18,170 --> 00:03:21,990 Però permetin-me proposar, suposi que té obtingut de mala sort, i suposem que 88 00:03:21,990 --> 00:03:26,840 no van ser, de fet, ordenats, com molts aquestes portes que podrien haver hagut de mirar 89 00:03:26,840 --> 00:03:28,590 darrere en que pitjor dels casos? 90 00:03:28,590 --> 00:03:29,860 >> JENNIFER: Tots ells. 91 00:03:29,860 --> 00:03:30,420 >> DAVID J. Malan: Tots ells. 92 00:03:30,420 --> 00:03:31,740 Així que anem a generalitzar que com a n. 93 00:03:31,740 --> 00:03:34,790 Passa que hi ha 7, però anem a més generalment diuen que hi ha n portes al 94 00:03:34,790 --> 00:03:35,650 pantalla aquí. 95 00:03:35,650 --> 00:03:40,110 Així que en el pitjor dels casos, vostè hauria de per mirar cap enrere 7 portes, o portes núm. 96 00:03:40,110 --> 00:03:44,140 I pel que això és, que és una mica de sort avui, però en realitat és una relació lineal 97 00:03:44,140 --> 00:03:46,440 algoritme de classes, tot i que eren una cosa que salta voltant. 98 00:03:46,440 --> 00:03:47,080 És això just? 99 00:03:47,080 --> 00:03:47,500 >> JENNIFER: Si. 100 00:03:47,500 --> 00:03:50,000 >> DAVID J. Malan: Bé, deixa veure si el seu canvis d'estratègia si ens moguem 101 00:03:50,000 --> 00:03:52,190 el nostre segon exemple aquí amb 7 portes diferents. 102 00:03:52,190 --> 00:03:55,240 Mateixos números, però això moment en què s'ordenen. 103 00:03:55,240 --> 00:03:58,350 Quina és la seva estratègia d'aquí serà, tractant de posar fora de la seva ment el que 104 00:03:58,350 --> 00:03:59,310 els altres números eren - 105 00:03:59,310 --> 00:03:59,930 >> JENNIFER: OK. 106 00:03:59,930 --> 00:04:02,290 >> DAVID J. Malan: - abans? 107 00:04:02,290 --> 00:04:03,180 >> JENNIFER: Anem a començar amb el primer. 108 00:04:03,180 --> 00:04:03,540 >> DAVID J. Malan: Molt bé. 109 00:04:03,540 --> 00:04:05,190 Comenceu amb la primera. 110 00:04:05,190 --> 00:04:05,960 4. 111 00:04:05,960 --> 00:04:08,810 Ara, a on aniràs, i per què? 112 00:04:08,810 --> 00:04:10,040 >> JENNIFER: 4 és realment petit. 113 00:04:10,040 --> 00:04:12,500 Així que si tenen sort potser més petit a més gran, el que hauria 114 00:04:12,500 --> 00:04:13,290 ser el doble que, i -. 115 00:04:13,290 --> 00:04:13,670 >> DAVID J. Malan: OK. 116 00:04:13,670 --> 00:04:15,990 Anem a veure, que et sembla? 117 00:04:15,990 --> 00:04:19,050 >> JENNIFER: Proveu l'última. 118 00:04:19,050 --> 00:04:19,500 Niça. 119 00:04:19,500 --> 00:04:20,880 >> DAVID J. Malan: Molt ben fet. 120 00:04:20,880 --> 00:04:21,860 Està bé. 121 00:04:21,860 --> 00:04:23,010 >> [Aplaudiments] 122 00:04:23,010 --> 00:04:24,310 >> DAVID J. Malan: OK. 123 00:04:24,310 --> 00:04:26,790 Així que en realitat estàs fent això horrible, perquè ets 124 00:04:26,790 --> 00:04:27,700 fent molt bé. 125 00:04:27,700 --> 00:04:31,150 Què ens deixa incapaços de fer que alguns punts. 126 00:04:31,150 --> 00:04:32,565 Així que anem a tractar de fer retrocedir aquí. 127 00:04:32,565 --> 00:04:34,560 >> JENNIFER: OK. 128 00:04:34,560 --> 00:04:35,980 >> DAVID J. Malan: Molt bé fet, però. 129 00:04:35,980 --> 00:04:39,060 Així que va començar a principis, vas veure que era 4, llavors 130 00:04:39,060 --> 00:04:40,240 mogut fins al final. 131 00:04:40,240 --> 00:04:42,320 Però suposem que no tingui sort allà, i suposo que 50 132 00:04:42,320 --> 00:04:42,890 estava en una altra part. 133 00:04:42,890 --> 00:04:46,190 El que el seu tercer pas ha estat? 134 00:04:46,190 --> 00:04:47,680 >> JENNIFER: Torna al principi. 135 00:04:47,680 --> 00:04:48,320 >> DAVID J. Malan: Tornar al principi. 136 00:04:48,320 --> 00:04:51,320 Acceptar, pel que li ha tocat aquesta porta, que era agost. 137 00:04:51,320 --> 00:04:51,660 Està bé. 138 00:04:51,660 --> 00:04:52,650 Així que això no és 50. 139 00:04:52,650 --> 00:04:55,380 On t'has mirat al costat? 140 00:04:55,380 --> 00:04:56,720 >> JENNIFER: Si no ho fes saben el van arreglar. 141 00:04:56,720 --> 00:04:57,005 >> DAVID J. Malan: Correcte. 142 00:04:57,005 --> 00:04:58,490 Bé, si ho va fer saber van ser ordenats - 143 00:04:58,490 --> 00:04:58,700 >> JENNIFER: Oh, sabia, sí. 144 00:04:58,700 --> 00:05:00,910 >> DAVID J. Malan: - Però no ho vas fer saber que el 50 estava encara? 145 00:05:00,910 --> 00:05:01,785 >> JENNIFER: Segueix endavant. 146 00:05:01,785 --> 00:05:02,130 >> DAVID J. Malan: Molt bé. 147 00:05:02,130 --> 00:05:02,520 D'acord. 148 00:05:02,520 --> 00:05:03,800 Segueix endavant. 149 00:05:03,800 --> 00:05:05,270 Bé, que puc treballar. 150 00:05:05,270 --> 00:05:05,610 >> JENNIFER: OK. 151 00:05:05,610 --> 00:05:07,210 >> DAVID J. Malan: Ara, si ets seguirà endavant, quin és el teu 152 00:05:07,210 --> 00:05:09,680 algoritme que incumbeixen retrocedir fins. 153 00:05:09,680 --> 00:05:10,740 >> JENNIFER: El lineal -. 154 00:05:10,740 --> 00:05:11,820 >> DAVID J. Malan: És una mica lineal. 155 00:05:11,820 --> 00:05:13,480 Però permetin-me proposar, i molt em poso en el lloc. 156 00:05:13,480 --> 00:05:14,900 Deixa que et refresqui la pàgina. 157 00:05:14,900 --> 00:05:17,120 mateix número, mateixa disposició, mateixes portes. 158 00:05:17,120 --> 00:05:21,350 Però pensar en tornar a aquest primer dia en classe quan vam trencar una guia telefònica en 159 00:05:21,350 --> 00:05:25,480 mitjà, més o menys, i el que era nostra estratègia allà? 160 00:05:25,480 --> 00:05:26,450 >> JENNIFER: Comenceu en el centre. 161 00:05:26,450 --> 00:05:26,690 >> DAVID J. Malan: OK. 162 00:05:26,690 --> 00:05:27,610 Així que comença al centre. 163 00:05:27,610 --> 00:05:28,790 Així que seguirem endavant i simular. 164 00:05:28,790 --> 00:05:30,720 Comenceu al centre de revelant aquesta porta. 165 00:05:30,720 --> 00:05:31,660 Així el nombre 16. 166 00:05:31,660 --> 00:05:35,290 Llavors, quin seria l'home fort ha fet, que va arrencar el llibre de telèfon a la meitat, 167 00:05:35,290 --> 00:05:38,450 per arribar a la següent conjectura? 168 00:05:38,450 --> 00:05:39,400 >> JENNIFER: Anar en aquest mitjà. 169 00:05:39,400 --> 00:05:41,700 >> DAVID J. Malan: I per què a la dreta? 170 00:05:41,700 --> 00:05:43,900 >> JENNIFER: Si fossin una mena de petit a més gran, a continuació, 50 ha de ser 171 00:05:43,900 --> 00:05:44,720 en aquest extrem. 172 00:05:44,720 --> 00:05:44,920 >> DAVID J. Malan: Good. 173 00:05:44,920 --> 00:05:45,390 Totalment raonable. 174 00:05:45,390 --> 00:05:48,380 Així com un directori telefònic, vostè va a la dret en oposició a l'esquerra, però aquí 175 00:05:48,380 --> 00:05:49,500 és el punt clau. 176 00:05:49,500 --> 00:05:53,930 Ara pot tirar, o arrencar, mitjà d'aquest problema, no la deixa 177 00:05:53,930 --> 00:05:55,970 amb 7 portes, però en realitat amb només 3. 178 00:05:55,970 --> 00:05:57,870 Que és aproximadament la meitat de la mida del problema. 179 00:05:57,870 --> 00:05:58,350 Està bé. 180 00:05:58,350 --> 00:06:01,890 Així que ara el que hauria realitzat després d'anar a la dreta? 181 00:06:01,890 --> 00:06:05,870 >> JENNIFER: Llavors 16 és encara molt petita, en relació amb el 50, així que potser vaig a tractar, 182 00:06:05,870 --> 00:06:06,700 com, aquest. 183 00:06:06,700 --> 00:06:07,890 >> DAVID J. Malan: Molt bé. 184 00:06:07,890 --> 00:06:08,720 42. 185 00:06:08,720 --> 00:06:10,830 Molt bé, així que ara el que és seu instint que li diu? 186 00:06:10,830 --> 00:06:12,100 >> JENNIFER: Puc llençar això i després simplement - 187 00:06:12,100 --> 00:06:12,360 >> DAVID J. Malan: OK. 188 00:06:12,360 --> 00:06:14,212 Bé, vostè pot tirar la meitat esquerra allà. 189 00:06:14,212 --> 00:06:14,890 >> JENNIFER: - escollir aquest. 190 00:06:14,890 --> 00:06:15,530 >> DAVID J. Malan: I de la dreta. 191 00:06:15,530 --> 00:06:15,760 >> JENNIFER: Si. 192 00:06:15,760 --> 00:06:17,820 >> DAVID J. Malan: Així que, encara que és difícil per veure potser, quan només hi ha 193 00:06:17,820 --> 00:06:21,320 7 portes, pensar, ara, la consistència de la 194 00:06:21,320 --> 00:06:22,620 Algorisme que acaba d'aplicar. 195 00:06:22,620 --> 00:06:24,510 En el cas anterior, que va fer que tingui sort, que era genial. 196 00:06:24,510 --> 00:06:26,540 Però ho vas fer servir una heurística, Diria jo. 197 00:06:26,540 --> 00:06:29,150 Utilitzar espècie dels seus instints, i saber el resolt, si és prou 198 00:06:29,150 --> 00:06:31,600 petita al principi, òbviament, hem ha d'anar més a la dreta. 199 00:06:31,600 --> 00:06:34,990 Però en cert sentit, tens sort, perquè potser aquest va ser el número 100, 200 00:06:34,990 --> 00:06:36,220 i potser 50 era més en el medi. 201 00:06:36,220 --> 00:06:37,910 Potser 50 va ser encara més aquí. 202 00:06:37,910 --> 00:06:40,960 >> Però el que va fer una mica diferent aquesta vegada va ser, que va fer el mateix 203 00:06:40,960 --> 00:06:42,150 una i altra vegada. 204 00:06:42,150 --> 00:06:45,310 I jo diria que el que acabes de va fer, encara que influït pel telèfon 205 00:06:45,310 --> 00:06:48,100 exemple de llibre, és una cosa molt més algorítmica, i molt 206 00:06:48,100 --> 00:06:49,930 menys especial revestit. 207 00:06:49,930 --> 00:06:51,620 Molt menys instintiu. 208 00:06:51,620 --> 00:06:57,160 Així que al final del dia, com que descriu l'eficàcia de la 209 00:06:57,160 --> 00:07:00,530 primer algorisme, en què es esquerra a dreta, enfront de la 210 00:07:00,530 --> 00:07:03,430 segon algorisme aquí? 211 00:07:03,430 --> 00:07:06,460 >> JENNIFER: Aquest ha, igual que, potser reduir a la meitat el temps, o fins i tot més, si. 212 00:07:06,460 --> 00:07:07,320 >> DAVID J. Malan: OK, potser encara més. 213 00:07:07,320 --> 00:07:10,150 Anem a empènyer una mica més en això. 214 00:07:10,150 --> 00:07:13,030 El que, si seguim aquest lògica, que sens dubte redueix a la meitat el 215 00:07:13,030 --> 00:07:15,830 temps de funcionament amb aquest segon algorisme deixant de banda la meitat de la 216 00:07:15,830 --> 00:07:18,470 números, però el que vam fer a la següent iteració, quan Jennifer va revelar 217 00:07:18,470 --> 00:07:20,615 el segon número? 218 00:07:20,615 --> 00:07:22,830 >> Hem reduït a la meitat el nombre de portes. 219 00:07:22,830 --> 00:07:25,270 I llavors què vam fer després d'això, si hi havia més portes per jugar? 220 00:07:25,270 --> 00:07:27,520 Volem reduir a la meitat, i de nou, i una altra, i una altra. 221 00:07:27,520 --> 00:07:30,420 I això era com vosaltres tots de peu a la primera setmana de 222 00:07:30,420 --> 00:07:33,000 classe, la meitat de vostès assegut, mig de vostès asseguts, la meitat de vostès 223 00:07:33,000 --> 00:07:35,440 seure, fins que un solitari ànima estava dempeus. 224 00:07:35,440 --> 00:07:39,050 I vam dir que el temps d'execució de que, el nombre de passos que va prendre era 225 00:07:39,050 --> 00:07:40,430 en l'ordre del que? 226 00:07:40,430 --> 00:07:41,230 >> ALTAVEU 1: [inaudible] 227 00:07:41,230 --> 00:07:43,970 >> DAVID J. Malan: Així logaritme en base 2 de n, o simplement més simplement, iniciar de n. 228 00:07:43,970 --> 00:07:45,060 Així que alguna cosa logarítmica. 229 00:07:45,060 --> 00:07:48,380 I la gràfica no era una línia recta que acaba d'arribar en pitjor, que era 230 00:07:48,380 --> 00:07:52,490 interessant aquesta corba que no ho va fer estar tan malament amb el temps. 231 00:07:52,490 --> 00:07:53,910 Així que anem a aferrar-se a aquesta idea. 232 00:07:53,910 --> 00:07:54,690 Donem gràcies a Jennifer. 233 00:07:54,690 --> 00:07:56,150 Gràcies per venir a endavant. 234 00:07:56,150 --> 00:07:57,400 I, un segon. 235 00:07:57,400 --> 00:08:00,170 236 00:08:00,170 --> 00:08:02,925 No hi ha llums d'escriptori avui, però Què tenen CS50 boles de la tensió. 237 00:08:02,925 --> 00:08:03,420 >> JENNIFER: Yay. 238 00:08:03,420 --> 00:08:04,410 >> DAVID J. Malan: Molt bé, aquí. 239 00:08:04,410 --> 00:08:06,545 Gràcies per incórrer en la tensió aquí. 240 00:08:06,545 --> 00:08:07,350 Està bé. 241 00:08:07,350 --> 00:08:10,620 Així que anem a veure si no podem ara formalitzar aquest una mica més. 242 00:08:10,620 --> 00:08:14,820 Així que de nou, el que vam fer va ser essencialment el mateix que vam fer 243 00:08:14,820 --> 00:08:16,660 en la primera setmana. 244 00:08:16,660 --> 00:08:23,780 Però en comptes d'acabar amb només un lineal algorisme, que és representat 245 00:08:23,780 --> 00:08:27,210 anteriorment com la línia recta, pel que, si col · loquem una porta més a 246 00:08:27,210 --> 00:08:29,610 la pantalla, a continuació, Jennifer faria han hagut de buscar, en potència, 247 00:08:29,610 --> 00:08:30,600 darrere d'una porta més. 248 00:08:30,600 --> 00:08:33,490 Si posem dues portes més, ella podria tenir per mirar darrere de dues portes més. 249 00:08:33,490 --> 00:08:35,990 >> I així, hi havia un lineal relació entre la mida de la 250 00:08:35,990 --> 00:08:39,059 problema en, per exemple, l'eix x, i la quantitat de temps que es necessita per 251 00:08:39,059 --> 00:08:40,440 resoldre a la i. 252 00:08:40,440 --> 00:08:43,330 Però la imatge que s'estava referint a abans era la línia verda. 253 00:08:43,330 --> 00:08:45,970 Verd deliberadament, perquè se sentia millor. 254 00:08:45,970 --> 00:08:49,790 En teoria, l'algorisme, quan ho vam fer amb la guia telefònica, quan ho vam fer 255 00:08:49,790 --> 00:08:52,420 amb vostès comptant entre si, i en el segon cas, quan Jennifer acaba 256 00:08:52,420 --> 00:08:55,250 ho va fer aquí, que era una mena de fonamentalment millor. 257 00:08:55,250 --> 00:08:57,180 A causa que no era només el doble de ràpid. 258 00:08:57,180 --> 00:08:58,870 No va ser fins a quatre vegades més ràpid. 259 00:08:58,870 --> 00:09:03,290 Era totalment dependent del que l' mida de l'entrada era, quant a quants 260 00:09:03,290 --> 00:09:05,220 mesures que en última instància va. 261 00:09:05,220 --> 00:09:08,040 >> I així, aquest simple idea que tot el que vam fer per descomptat amb la guia telefònica, 262 00:09:08,040 --> 00:09:10,200 de manera similar pot ser aplicat a alguna cosa com això. 263 00:09:10,200 --> 00:09:12,380 I això podria ser més informal coneguda com, com pot ser que 264 00:09:12,380 --> 00:09:13,940 imaginar, divideix i venceràs. 265 00:09:13,940 --> 00:09:16,390 No gaire diferent del que vam fer, per descomptat, amb la guia telefònica. 266 00:09:16,390 --> 00:09:18,300 >> Però el pseudocodi, record, era això. 267 00:09:18,300 --> 00:09:21,800 Així que no farem això de nou, però recorda la primera setmana, tots es van posar drets 268 00:09:21,800 --> 00:09:25,140 i després la meitat de vostès es van asseure, la meitat que es va asseure, la meitat de vostès es va asseure. 269 00:09:25,140 --> 00:09:29,280 Això algorisme va ser implementat en un mica d'una manera fer trampa en això, 270 00:09:29,280 --> 00:09:32,870 No va ser només una de les em comptant, fonamentalment, de manera més eficient. 271 00:09:32,870 --> 00:09:35,830 En aquest cas, em Aprofitant un recurs secundari. 272 00:09:35,830 --> 00:09:39,470 Més o menys, diverses CPU, múltiples cervells, moltes persones intel ligents en el 273 00:09:39,470 --> 00:09:42,740 habitació estaven ajudant a aconseguir a partir d'alguna cosa lineal a alguna cosa 274 00:09:42,740 --> 00:09:45,190 logarítmica, d'alguna cosa vermell amb una mica verd. 275 00:09:45,190 --> 00:09:48,650 >> Però en aquest cas, Jennifer solament pot fonamentalment, millorar la 276 00:09:48,650 --> 00:09:52,370 el rendiment del seu primer algorisme per, altra vegada, pensant una mica més difícil. 277 00:09:52,370 --> 00:09:56,650 I ara, quan arriba el moment de posar en pràctica aquestes coses, esbrinar 278 00:09:56,650 --> 00:10:00,670 quines línies de codi es pot escriure com que es pot repetir una vegada més, i 279 00:10:00,670 --> 00:10:03,350 una altra vegada, i una altra, una mena de d'una forma de bucle. 280 00:10:03,350 --> 00:10:06,370 Com que vostè no va a tenir la de luxe, igual que Jennifer va fer al principi, 281 00:10:06,370 --> 00:10:10,460 només hi ha un munt de sís i dir: hmm, si aquest primer número és 4, 282 00:10:10,460 --> 00:10:11,800 m'ho dius a mi saltar tot el camí fins al final. 283 00:10:11,800 --> 00:10:14,180 Oh, si aquest nombre és massa gran, Permetin-me passar arbitràriament de nou 284 00:10:14,180 --> 00:10:15,220 per al segon element. 285 00:10:15,220 --> 00:10:18,210 Trobareu que això serà molt més difícil de formalitzar el que els éssers humans 286 00:10:18,210 --> 00:10:21,270 donar per fet com molt raonable heurística, però un ordinador és només 287 00:10:21,270 --> 00:10:23,260 farem el que vostè li digui que fer. 288 00:10:23,260 --> 00:10:25,280 >> Ara bé, això té molt interessant implicacions. 289 00:10:25,280 --> 00:10:29,950 Aquesta gràfica és una espècie de dir que tipus de saturar visualment, però avís, quan 290 00:10:29,950 --> 00:10:32,230 és la línia recta en el gràfic? 291 00:10:32,230 --> 00:10:35,330 On és la gràfica lineal que anomenem n? 292 00:10:35,330 --> 00:10:37,580 Bé, és una espècie de cap a la part inferior d'aquesta imatge, oi? 293 00:10:37,580 --> 00:10:40,500 Així que tot el que hem fet és que hem mena de ampliada a l'eix x i el 294 00:10:40,500 --> 00:10:44,780 eix per intentar tenir una idea del que altres tipus de corbes semblen. 295 00:10:44,780 --> 00:10:47,760 >> I els detalls de la matemàtica expressions avui no importa el 296 00:10:47,760 --> 00:10:52,440 molt, però noten que hi ha una gran quantitat de algoritmes que són molt pitjors que 297 00:10:52,440 --> 00:10:53,470 cosa que és lineal. 298 00:10:53,470 --> 00:10:55,410 En efecte, n cubs es veu molt malament. 299 00:10:55,410 --> 00:10:58,400 2 a la núm es veu molt malament. n quadrat es veu molt malament. 300 00:10:58,400 --> 00:11:01,630 I anem a veure el que alguns dels podria ser en realitat avui en dia. 301 00:11:01,630 --> 00:11:05,430 I log n no se sent tan malament, però millor que n és log base 2 de n. 302 00:11:05,430 --> 00:11:08,080 Però ja saps, hauria estat encara més sorprenent si Jennifer, o si, 303 00:11:08,080 --> 00:11:12,910 la primera setmana, s'havia arribat amb una cosa que és registre de log de n. 304 00:11:12,910 --> 00:11:15,880 >> En altres paraules, hi ha un conjunt gamma de possibles solucions als 305 00:11:15,880 --> 00:11:18,570 problemes, però fins i tot en aquest cas, l'avís el que va a succeir. 306 00:11:18,570 --> 00:11:22,910 En allunyar la imatge, quina d'aquestes corbes arribarà a ser l'absoluta 307 00:11:22,910 --> 00:11:26,630 pitjor dels que estan a la pantalla ara? 308 00:11:26,630 --> 00:11:28,680 Llavors n cubs es veu molt malament en aquest moment. 309 00:11:28,680 --> 00:11:32,470 Però si allunyar i veure més de la x i l'eix i, qui va a 310 00:11:32,470 --> 00:11:34,550 dominant en última instància? 311 00:11:34,550 --> 00:11:37,120 Per tant, en realitat resulta que 2 a la n, i es pot resoldre això amb només 312 00:11:37,120 --> 00:11:39,990 endollant algun cada vegada més gran números i veureu que 2 a l' 313 00:11:39,990 --> 00:11:42,070 n, de fet, es fa més gran molt més ràpid. 314 00:11:42,070 --> 00:11:45,530 Si realment allunyar la imatge, un 2 a la algoritme n absolutament horrible. 315 00:11:45,530 --> 00:11:48,170 Vull dir que això va a prendre una mica de temps perquè la 316 00:11:48,170 --> 00:11:49,460 equip per batre través. 317 00:11:49,460 --> 00:11:52,500 >> Però veurà amb el temps, especialment amb els futurs butlletins de problemes i fins i tot 318 00:11:52,500 --> 00:11:55,600 projectes fi de carrera, és les seves dades conjunt es fa gran, d'acord? 319 00:11:55,600 --> 00:11:58,300 Fins i tot en la primera versió de Facebook, com el nombre d'amics, i la 320 00:11:58,300 --> 00:12:01,840 nombre d'usuaris registrats té gran, es pot ordenar de telèfon dins i 321 00:12:01,840 --> 00:12:05,530 implementar alguna cosa amb recerca lineal, o una classificació molt simple 322 00:12:05,530 --> 00:12:07,030 algorisme, com veurem avui. 323 00:12:07,030 --> 00:12:09,280 Has de començar a pensar més i més sobre aquests problemes. 324 00:12:09,280 --> 00:12:12,070 I els tipus de problemes de llocs com Facebook i Google, i Microsoft, 325 00:12:12,070 --> 00:12:16,350 i altres treballen és exactament tipus de dades de gran classe de preguntes 326 00:12:16,350 --> 00:12:18,530 cada vegada més en aquests dies. 327 00:12:18,530 --> 00:12:18,900 >> Està bé. 328 00:12:18,900 --> 00:12:23,800 Així que l'èxit de Jennifer en aquest segon algorisme, francament, ho va fer increïblement 329 00:12:23,800 --> 00:12:26,110 bé la primera vegada, però anem a escriure la sort perquè puguem 330 00:12:26,110 --> 00:12:27,000 pot aclarir aquest punt. 331 00:12:27,000 --> 00:12:30,970 En el segon cas, s'ha mobilitzat algoritme que repeteix una i altra 332 00:12:30,970 --> 00:12:34,670 una altra vegada, però ella va donar per fet 1 certa suposició que hem permès 333 00:12:34,670 --> 00:12:39,370 , Però ella explota cert detall el segona vegada que ella no tenia la 334 00:12:39,370 --> 00:12:39,840 primera vegada. 335 00:12:39,840 --> 00:12:41,800 Què va ser què? 336 00:12:41,800 --> 00:12:43,050 >> Això es va solucionar la llista. 337 00:12:43,050 --> 00:12:46,350 Així que tan aviat com s'ordena la llista, afirmen que Jennifer era capaç de fer 338 00:12:46,350 --> 00:12:47,480 fonamentalment millor. 339 00:12:47,480 --> 00:12:51,450 7 portes, si, no és tan interessant, però suposem que estem 7000000 portes. 340 00:12:51,450 --> 00:12:54,080 Bitàcola de n és, sens dubte va per dur a terme molt, molt 341 00:12:54,080 --> 00:12:55,610 més ràpid en el llarg termini. 342 00:12:55,610 --> 00:12:58,880 Però ella havia de tenir la portes ordenats per ella. 343 00:12:58,880 --> 00:13:02,320 Ara, em vaig prendre la llibertat de fer això per avançat en la pantalla de l'ordinador 344 00:13:02,320 --> 00:13:05,160 aquí, però suposo que Jennifer havia de fer ella mateixa? 345 00:13:05,160 --> 00:13:10,120 Suposem que les portes en qüestió dades representades en una base de dades, o 346 00:13:10,120 --> 00:13:14,260 amics registrats a Facebook, o qualsevol de les pàgines web a Internet que 347 00:13:14,260 --> 00:13:16,880 diversos llocs web podrien necessitar l'índex o buscar de nou. 348 00:13:16,880 --> 00:13:20,940 >> Suposem que vostè acaba de tenir una base de dades en brut estableix i es va deixar a vostè, o per 349 00:13:20,940 --> 00:13:23,010 Jennifer fer que la classificació? 350 00:13:23,010 --> 00:13:26,950 Això, més aviat, requereix que responguem la pregunta, bé, quant de temps 351 00:13:26,950 --> 00:13:31,080 hauria pres Jennifer, o fins i tot jo, per ordenar els nombres per endavant per 352 00:13:31,080 --> 00:13:32,680 que podia prendre avantatge d'això? 353 00:13:32,680 --> 00:13:32,880 Cert? 354 00:13:32,880 --> 00:13:36,620 A causa de la implicació, per descomptat, és si em porta bastant temps per ordenar 355 00:13:36,620 --> 00:13:40,800 els números, qui diables li importa que pot trobar un nombre com 50 tan ràpid, 356 00:13:40,800 --> 00:13:44,850 com en el cas de Jennifer, si més d' aclaparat la quantitat de temps total 357 00:13:44,850 --> 00:13:46,920 que va prendre d'ordenar les coses per endavant? 358 00:13:46,920 --> 00:13:49,320 >> Així que anem a veure si no podem l' pintar el quadre aquí. 359 00:13:49,320 --> 00:13:51,370 Tinc un munt més estrès boles, si això ajuda 360 00:13:51,370 --> 00:13:52,270 trencar el gel aquí. 361 00:13:52,270 --> 00:13:55,690 I si no t'importa, ens necessitarà 07:00 voluntaris - 362 00:13:55,690 --> 00:13:57,060 a, OK. 363 00:13:57,060 --> 00:13:57,240 Wow. 364 00:13:57,240 --> 00:13:59,250 Així que no hem de gastar en els llums d'escriptori, el que sembla. 365 00:13:59,250 --> 00:13:59,690 Està bé. 366 00:13:59,690 --> 00:14:01,530 Així que hi ha de vosaltres dos al front. 367 00:14:01,530 --> 00:14:04,160 Què hi ha de vosaltres dos a l'esquena. 368 00:14:04,160 --> 00:14:04,870 Així que això és quatre. 369 00:14:04,870 --> 00:14:09,890 I tu per davant cinc, sis-set. 370 00:14:09,890 --> 00:14:10,320 Aquí mateix. 371 00:14:10,320 --> 00:14:13,260 El teu amic t'està assenyalant, perquè pugui obtenir el premi. 372 00:14:13,260 --> 00:14:13,700 >> Està bé. 373 00:14:13,700 --> 00:14:14,410 Anem amunt. 374 00:14:14,410 --> 00:14:17,120 I per què no hem de nois vénen per aquí. 375 00:14:17,120 --> 00:14:18,960 Jo et vaig a donar a cadascun un nombre. 376 00:14:18,960 --> 00:14:22,150 I seguir endavant i organitzar a si mateixos idèntica al que és 377 00:14:22,150 --> 00:14:25,180 es mostra a la pantalla. 378 00:14:25,180 --> 00:14:26,530 >> [Interrompent VEUS] 379 00:14:26,530 --> 00:14:28,160 >> DAVID J. Malan: OOP, ho sento. 380 00:14:28,160 --> 00:14:30,210 Bug. 381 00:14:30,210 --> 00:14:32,180 Està bé. 382 00:14:32,180 --> 00:14:32,750 Bé, aquí anem. 383 00:14:32,750 --> 00:14:34,180 El número cinc. 384 00:14:34,180 --> 00:14:35,136 El número sis. 385 00:14:35,136 --> 00:14:37,770 Un, dos, tres, quatre, cinc, sis, set. 386 00:14:37,770 --> 00:14:39,410 Oh, això és incòmode. 387 00:14:39,410 --> 00:14:41,210 >> ALTAVEU 2: Vaig a buscar -. 388 00:14:41,210 --> 00:14:41,900 >> DAVID J. Malan: Good deal. 389 00:14:41,900 --> 00:14:43,130 Està bé. 390 00:14:43,130 --> 00:14:44,611 Gràcies per participar. 391 00:14:44,611 --> 00:14:47,200 >> [Aplaudiments] 392 00:14:47,200 --> 00:14:48,580 >> D'acord. 393 00:14:48,580 --> 00:14:48,860 Està bé. 394 00:14:48,860 --> 00:14:51,970 Així que tenim quatre, dos, sis, un, tres, set, cinc. 395 00:14:51,970 --> 00:14:56,010 Perfecciona així que tenim 7 voluntaris aquí, que són iguals en amplada a la 396 00:14:56,010 --> 00:14:57,430 matriu que estem jugant amb l'anterior. 397 00:14:57,430 --> 00:14:59,470 I vaig triar set per raons que serà només 398 00:14:59,470 --> 00:15:00,840 convenient en una mica. 399 00:15:00,840 --> 00:15:04,400 I jo vaig a proposar que la primera que resolguem aquests set voluntaris. 400 00:15:04,400 --> 00:15:06,786 Si ho desitja, en primer lloc, per saludar però. 401 00:15:06,786 --> 00:15:08,970 Atès que això serà un incòmodes diversos minuts. 402 00:15:08,970 --> 00:15:10,370 Presenteu-vos. 403 00:15:10,370 --> 00:15:10,980 >> GRACE: Hola, sóc la Gràcia. 404 00:15:10,980 --> 00:15:14,190 Sóc un estudiant de segon any a Leverett House. 405 00:15:14,190 --> 00:15:14,620 >> BRANSON: Hi. 406 00:15:14,620 --> 00:15:15,620 Estic Branson. 407 00:15:15,620 --> 00:15:16,920 Sóc un estudiant de primer any a la soldadura. 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 Sóc Gabe. 411 00:15:21,040 --> 00:15:22,300 Sóc un jove a Cabot. 412 00:15:22,300 --> 00:15:24,826 413 00:15:24,826 --> 00:15:25,980 >> NEIL: Sóc Neil. 414 00:15:25,980 --> 00:15:29,090 Sóc un estudiant de primer any a Matthews. 415 00:15:29,090 --> 00:15:29,550 >> JASON: Sóc Jason. 416 00:15:29,550 --> 00:15:32,816 Sóc un estudiant de primer any a Greenough. 417 00:15:32,816 --> 00:15:33,700 >> MIKE: Sóc Mike. 418 00:15:33,700 --> 00:15:37,360 Sóc un estudiant de primer any a Grays. 419 00:15:37,360 --> 00:15:37,990 >> JESS: Sóc Jess. 420 00:15:37,990 --> 00:15:40,313 Sóc un estudiant de segon any a Leverett. 421 00:15:40,313 --> 00:15:41,300 >> DAVID J. Malan: Excel · lent. 422 00:15:41,300 --> 00:15:41,850 Està bé. 423 00:15:41,850 --> 00:15:44,190 Bé, gràcies a tots els nostres voluntaris aquí fins ara. 424 00:15:44,190 --> 00:15:47,110 I el desafiament a la mà ara es va estar a la classe d'aquests nois, però després 425 00:15:47,110 --> 00:15:50,250 anem a haver de pensar una mica estès sobre l'eficiència amb que en realitat 426 00:15:50,250 --> 00:15:51,110 ells ordenats. 427 00:15:51,110 --> 00:15:52,580 Així que anem a provar primer això. 428 00:15:52,580 --> 00:15:55,970 Vostès poden veure els números de cadascun amb només posar al voltant de les cantonades. 429 00:15:55,970 --> 00:15:59,380 Seguiu endavant i feu una segons i Ordenar vosaltres mateixos des del més petit al 430 00:15:59,380 --> 00:16:01,240 esquerra a la més gran de la dreta. 431 00:16:01,240 --> 00:16:02,490 Vaya. 432 00:16:02,490 --> 00:16:07,010 433 00:16:07,010 --> 00:16:07,530 >> D'acord. 434 00:16:07,530 --> 00:16:08,030 Bé. 435 00:16:08,030 --> 00:16:09,370 Això va ser realment maleït ràpid. 436 00:16:09,370 --> 00:16:14,040 Ara algú aquí, quin va ser l'algoritme de que aquests tipus aplicats? 437 00:16:14,040 --> 00:16:14,900 >> ALTAVEU 1: De menys a més. 438 00:16:14,900 --> 00:16:15,000 >> DAVID J. Malan: OK. 439 00:16:15,000 --> 00:16:18,070 De menys a més és realment una espècie de objectiu, però no estic segur que és 440 00:16:18,070 --> 00:16:18,890 realment un algorisme. 441 00:16:18,890 --> 00:16:21,810 De menys a més no diu Em pas a pas què fer. 442 00:16:21,810 --> 00:16:22,833 Sí? 443 00:16:22,833 --> 00:16:24,083 >> ALTAVEU 1: [inaudible] 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 Així que si veus una persona menor d' seu nombre, a continuació, passar a 447 00:16:28,920 --> 00:16:29,680 la dreta d'ells. 448 00:16:29,680 --> 00:16:32,800 Així que ara és cada vegada més expressiva, més com un algorisme, ja que 449 00:16:32,800 --> 00:16:35,410 pot dir, si això, llavors això. 450 00:16:35,410 --> 00:16:37,050 Així que tenim algun tipus de constructor condicional. 451 00:16:37,050 --> 00:16:39,700 I aquests nois semblaven fer que uns pocs vegades, a causa que alguns de vostès es va moure una mica 452 00:16:39,700 --> 00:16:40,420 de la distància. 453 00:16:40,420 --> 00:16:43,410 Així que havia presumiblement algun tipus de bucle passant en les seves ments. 454 00:16:43,410 --> 00:16:44,610 >> Però anem a tractar de formalitzar això. 455 00:16:44,610 --> 00:16:47,540 Si vostès poguessin restablir de nou amb aquesta disposició. 456 00:16:47,540 --> 00:16:50,650 Anem a veure si podem formalitzar aquest 1 poc, i després fer la pregunta, simplement 457 00:16:50,650 --> 00:16:51,580 què tan eficient és això? 458 00:16:51,580 --> 00:16:54,220 Per descomptat, quan fem això més lentament, es va a sentir tan bé 459 00:16:54,220 --> 00:16:57,210 un algorisme, però veurem si podem posar els dits en els passos precisos. 460 00:16:57,210 --> 00:16:58,670 >> Així que vostès dos són quatre-dos. 461 00:16:58,670 --> 00:17:01,020 O vostè ordre correcte o incorrecte? 462 00:17:01,020 --> 00:17:01,900 Evidentment falsos. 463 00:17:01,900 --> 00:17:02,710 Així que canviem. 464 00:17:02,710 --> 00:17:05,170 Ara em vaig a moure a un costat aquí i dir, quatre a sis. 465 00:17:05,170 --> 00:17:06,240 Està correcte o incorrecte? 466 00:17:06,240 --> 00:17:06,599 >> GABE: Correcte. 467 00:17:06,599 --> 00:17:07,180 >> DAVID J. Malan: Correcte. 468 00:17:07,180 --> 00:17:08,300 Sis i un? 469 00:17:08,300 --> 00:17:08,609 Nope. 470 00:17:08,609 --> 00:17:09,630 Intercanviar. 471 00:17:09,630 --> 00:17:10,490 Així que per dos swaps. 472 00:17:10,490 --> 00:17:11,710 Sis-tres? 473 00:17:11,710 --> 00:17:11,980 Nope. 474 00:17:11,980 --> 00:17:13,000 Intercanviar. 475 00:17:13,000 --> 00:17:13,930 Sis-set? 476 00:17:13,930 --> 00:17:14,630 Es veu bé. 477 00:17:14,630 --> 00:17:15,396 Set-cinc? 478 00:17:15,396 --> 00:17:16,150 >> JESS: [inaudible] 479 00:17:16,150 --> 00:17:17,089 >> DAVID J. Malan: OK, intercanviar. 480 00:17:17,089 --> 00:17:19,770 I ordenats. 481 00:17:19,770 --> 00:17:19,980 Està bé. 482 00:17:19,980 --> 00:17:21,440 Així que, òbviament, no, oi? 483 00:17:21,440 --> 00:17:22,470 Així que no hi havia més que fer. 484 00:17:22,470 --> 00:17:24,920 Però, de fet, aquests nois, fins i tot instintivament. 485 00:17:24,920 --> 00:17:25,450 seguia avançant. 486 00:17:25,450 --> 00:17:27,710 No es van limitar a parar, un cop corregit un problema. 487 00:17:27,710 --> 00:17:27,839 Així. 488 00:17:27,839 --> 00:17:29,390 De fet, jo vaig a tenir a fer el mateix. 489 00:17:29,390 --> 00:17:32,720 Vaig a haver d'ordenar de rebobinat de nou al principi d'aquest problema, 490 00:17:32,720 --> 00:17:35,630 o el començament d'aquesta sèrie de gent, anem a començar a trucar a ells. 491 00:17:35,630 --> 00:17:38,366 >> I ara, què hauria de dir al meu algorisme en el segon passi de ser? 492 00:17:38,366 --> 00:17:39,220 >> ALTAVEU 1: És el mateix. 493 00:17:39,220 --> 00:17:39,940 >> DAVID J. Malan: És el mateix. 494 00:17:39,940 --> 00:17:41,460 I això, estic començant a agradar, oi? 495 00:17:41,460 --> 00:17:44,720 Tan aviat com vostè pot trobar fent la mateixa cosa una i altra vegada, això és 496 00:17:44,720 --> 00:17:47,890 cada vegada més com un algoritme, i menys instint humà. 497 00:17:47,890 --> 00:17:48,680 >> Així que ara, aquí anem de nou. 498 00:17:48,680 --> 00:17:49,870 Dues-quatre? 499 00:17:49,870 --> 00:17:50,220 No 500 00:17:50,220 --> 00:17:51,050 Quatre i un? 501 00:17:51,050 --> 00:17:53,380 Ah, havia fet algunes treball que queda per fer. 502 00:17:53,380 --> 00:17:53,620 A favor i tres? 503 00:17:53,620 --> 00:17:54,572 Bé. 504 00:17:54,572 --> 00:17:56,000 Quatre-sis? 505 00:17:56,000 --> 00:17:58,380 Sis-cinc? 506 00:17:58,380 --> 00:17:59,470 Sis-set? 507 00:17:59,470 --> 00:18:00,970 Bé, ara, fet. 508 00:18:00,970 --> 00:18:01,550 Bé, no. 509 00:18:01,550 --> 00:18:02,710 He de tornar. 510 00:18:02,710 --> 00:18:05,130 >> Així que ara, un cop més, estem fent això una mica més de forma deliberada. 511 00:18:05,130 --> 00:18:08,700 I ara, no hi ha un sol cervell l'execució d'aquest algorisme. 512 00:18:08,700 --> 00:18:10,290 Una CPU, si es vol. 513 00:18:10,290 --> 00:18:13,090 I, francament, aquest és l'únic recurs tindrem accés. 514 00:18:13,090 --> 00:18:16,280 I una vegada que ens fa tornar a un teclat i tenir una mica com C en la nostra 515 00:18:16,280 --> 00:18:19,600 disposició, només estem escrivint un programa que pot fer una cosa alhora. 516 00:18:19,600 --> 00:18:22,900 Atès que, aquests nois fa un moment, apalancat seva capacitat intel · lectual col · lectiva 517 00:18:22,900 --> 00:18:24,180 com vostès van fer a la setmana zero. 518 00:18:24,180 --> 00:18:24,980 Així que seguirem fent això. 519 00:18:24,980 --> 00:18:26,260 >> Dos i un. 520 00:18:26,260 --> 00:18:26,945 Dues-tres. 521 00:18:26,945 --> 00:18:27,460 Tres-quatre. 522 00:18:27,460 --> 00:18:28,310 Quatre-cinc. 523 00:18:28,310 --> 00:18:28,620 Cinc-sis. 524 00:18:28,620 --> 00:18:30,510 Sis-set. 525 00:18:30,510 --> 00:18:31,880 Fet? 526 00:18:31,880 --> 00:18:34,560 Així que jo, però em deixa jugar advocat del diable. 527 00:18:34,560 --> 00:18:37,950 Tinc el tipus d'equip que acaba de va fer un passi a través d'aquesta sèrie de 528 00:18:37,950 --> 00:18:40,225 gent, saben que he acabat? 529 00:18:40,225 --> 00:18:40,670 >> ALTAVEU 1: No 530 00:18:40,670 --> 00:18:41,050 >> DAVID J. Malan: Per què? 531 00:18:41,050 --> 00:18:46,900 Què he de fer per tal de Concloc amb decisió que he fet? 532 00:18:46,900 --> 00:18:48,230 Probablement un pas més. 533 00:18:48,230 --> 00:18:48,430 Cert? 534 00:18:48,430 --> 00:18:51,760 Perquè tot el que sé d'aquest anterior passi és que he corregit un error. 535 00:18:51,760 --> 00:18:53,920 I això vol dir, tal vegada hagi Encara un altre error 536 00:18:53,920 --> 00:18:54,840 que he de corregir. 537 00:18:54,840 --> 00:18:58,680 Així que només puc estar segur de rebobinat i a continuació, comprovar, un a dos, i 2 538 00:18:58,680 --> 00:19:00,940 3, tres i quatre, quatre i cinc, 05:06, sis i set. 539 00:19:00,940 --> 00:19:02,510 Bé, ara jo no treballo. 540 00:19:02,510 --> 00:19:05,990 >> Certament, puc recordar que vaig fer no treballar amb alguna cosa semblant a una variable, 541 00:19:05,990 --> 00:19:06,975 com un int. 542 00:19:06,975 --> 00:19:12,490 Llámelo swaps, swaps i si és 0, un cop arribar fins aquí, i va començar a 0, llavors 543 00:19:12,490 --> 00:19:15,520 Només vull ser estúpid per seguir endavant d'anada i tornada, comprovant de nou, i 544 00:19:15,520 --> 00:19:16,450 una altra vegada, i una altra, oi? 545 00:19:16,450 --> 00:19:18,450 Perquè et quedes encallat en algun tipus de bucle infinit. 546 00:19:18,450 --> 00:19:21,250 Així que quan hi ha 0 swaps, podem afirmar que aquesta 547 00:19:21,250 --> 00:19:23,810 algorisme és, en efecte complet. 548 00:19:23,810 --> 00:19:25,400 >> Ara, anem a posar un nom a això. 549 00:19:25,400 --> 00:19:28,930 L'algorisme que proposo ens es va implementar una cosa que es diu bombolla 550 00:19:28,930 --> 00:19:32,800 tipus, coneguda com a tal en el sentit que els nombres que són més grans tipus de 551 00:19:32,800 --> 00:19:37,990 bombolla del seu camí al cim, o fins al final de la matriu dels nombres. 552 00:19:37,990 --> 00:19:40,270 Però què tan eficient va ser aquest algorisme? 553 00:19:40,270 --> 00:19:44,600 Quants passos vaig físicament he de Prenguem, per exemple, per ordenar aquests 554 00:19:44,600 --> 00:19:45,850 07:00 éssers humans? 555 00:19:45,850 --> 00:19:48,560 556 00:19:48,560 --> 00:19:49,550 >> Quatre o cinc? 557 00:19:49,550 --> 00:19:51,420 Bé, també molts és en última instància, serà la resposta. 558 00:19:51,420 --> 00:19:54,960 Però fins i tot llavors, el nombre específic no és tan interessant. 559 00:19:54,960 --> 00:19:56,670 Anem a generalitzar com a n. 560 00:19:56,670 --> 00:20:00,520 Així que si jo hagués n la gent aquí, i eren, més o menys, en un ordre aleatori en la 561 00:20:00,520 --> 00:20:02,180 començant, en aquest ordre original. 562 00:20:02,180 --> 00:20:04,910 Bé, quants passos vaig haver prendre el primer pas? 563 00:20:04,910 --> 00:20:09,810 Va ser un, dos, tres, quatre, cinc, 06:00, i són set persones, pel que 564 00:20:09,810 --> 00:20:13,670 això és set, sis -, pel que és n menys un passos que la primera vegada. 565 00:20:13,670 --> 00:20:16,280 >> Ara, quants passos vaig haver prendre quan Rebobine? 566 00:20:16,280 --> 00:20:19,310 Bé, en realitat podria doblar que si que realment volia, però per ara, estic 567 00:20:19,310 --> 00:20:22,300 només vaig a dir, està bé, un altre n almenys 1. 568 00:20:22,300 --> 00:20:25,240 Així que el n almenys 1 es posarà molest per no perdre de vista, així que anem a 569 00:20:25,240 --> 00:20:26,400 a la tornada una mica. 570 00:20:26,400 --> 00:20:27,770 Així 2n passos. 571 00:20:27,770 --> 00:20:29,310 Així que 14 passos, més o menys. 572 00:20:29,310 --> 00:20:31,930 >> Quantes vegades em prenc un pas la propera vegada? 573 00:20:31,930 --> 00:20:33,740 Bé, és 3n. 574 00:20:33,740 --> 00:20:34,510 realitat. 575 00:20:34,510 --> 00:20:37,920 I ara, en el pitjor dels casos, per exemple, quantes vegades hauré 576 00:20:37,920 --> 00:20:41,730 anat cap enrere i endavant, enrere i endavant, l'execució d'aquest algorisme, l'intercanvi 577 00:20:41,730 --> 00:20:44,620 persones en cada pas, més o menys? 578 00:20:44,620 --> 00:20:47,720 579 00:20:47,720 --> 00:20:50,010 De fet, és n al quadrat, oi? 580 00:20:50,010 --> 00:20:53,000 >> A causa que en el pitjor dels casos, pot tipus de pensar en això intuïtivament, 581 00:20:53,000 --> 00:20:54,800 tot i que pot ser que prengui una mica de poc de temps per assimilar 582 00:20:54,800 --> 00:20:57,590 En el pitjor dels casos, el que faria aquestes set persones han vist com, en 583 00:20:57,590 --> 00:21:00,230 termes de l'acord dels seus números? 584 00:21:00,230 --> 00:21:01,460 Completament a l'inrevés, no? 585 00:21:01,460 --> 00:21:02,815 I per simular que, Quin era el seu nom? 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 Bé, Mike, ¿pots venir amb mi sobre aquí només per un segon? 589 00:21:08,100 --> 00:21:08,880 En realitat, no. 590 00:21:08,880 --> 00:21:10,150 Ho sentim Mike, anem a retrocedir. 591 00:21:10,150 --> 00:21:10,910 Quin és el teu nom? 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 Acceptar, Neil, que vénen amb jo, si no m'importa. 595 00:21:13,750 --> 00:21:17,150 Així que vaig a proposar, només per simplicitat, que Neil es troba ara en el seu 596 00:21:17,150 --> 00:21:18,510 pitjor dels casos possibles. 597 00:21:18,510 --> 00:21:20,720 Però recordo com he implementat el meu algorisme. 598 00:21:20,720 --> 00:21:24,530 Estic comparant, comparar, comparar, comparar, comparar, oh. 599 00:21:24,530 --> 00:21:26,640 Ara aquests nois són fora de l'ordre, així que arreglar. 600 00:21:26,640 --> 00:21:27,980 Així que vostès swap. 601 00:21:27,980 --> 00:21:31,630 Però considerem ara, quant més lluny Neil no ha d'anar? 602 00:21:31,630 --> 00:21:32,690 És més o menys n. 603 00:21:32,690 --> 00:21:33,570 Ja saps, no és en realitat n. 604 00:21:33,570 --> 00:21:36,040 És com n menys 1, però m'estic posant molest pista custòdia de la petita 605 00:21:36,040 --> 00:21:37,550 nombre, pel que anem a cridar n. 606 00:21:37,550 --> 00:21:42,860 >> Així que si Neil fa un pas al màxim cada temps, i per moure Neil un pas, 607 00:21:42,860 --> 00:21:46,580 He de fer aquest pas realment tediós anada i tornada, això és més o menys 608 00:21:46,580 --> 00:21:52,080 D'aquesta manera, n passos, un total de n vegades, perquè va a portar 609 00:21:52,080 --> 00:21:55,820 que molts passos per arribar Neil tots el camí a on pertany. 610 00:21:55,820 --> 00:21:58,620 Per no parlar de tots els altres si vostès estaven tots mal ordenat també. 611 00:21:58,620 --> 00:22:01,100 >> Així que anem a trucar a la ordenació de bombolla n al quadrat. 612 00:22:01,100 --> 00:22:04,860 El temps d'execució d'aquest algorisme, el funcionament d'aquest algorisme, la 613 00:22:04,860 --> 00:22:07,120 l'eficiència d'aquest algorisme, ens acaba de descriure amb major 614 00:22:07,120 --> 00:22:08,800 generalment com a n al quadrat. 615 00:22:08,800 --> 00:22:11,650 La qual cosa és bo, perquè jo podria fer el mateix exemple amb vuit persones, nou 616 00:22:11,650 --> 00:22:15,450 persones, un milió de persones, i que resposta no canviarà. 617 00:22:15,450 --> 00:22:18,870 >> Així que si vostès no li importa, anem a de reajustar al punt de sortida. 618 00:22:18,870 --> 00:22:22,510 I tractarem dos enfocaments i si no podem fer-ho fonamentalment 619 00:22:22,510 --> 00:22:23,820 millor que això. 620 00:22:23,820 --> 00:22:27,130 Així que aquesta vegada, vaig a proposar una mena d'algorisme diferent. 621 00:22:27,130 --> 00:22:29,950 Això va ser molt intel · ligent de nosaltres l'última vegada, i vostès tenien raó perquè el 622 00:22:29,950 --> 00:22:32,470 instints correctes de només una mica d'intercanvi de parelles. 623 00:22:32,470 --> 00:22:36,500 Però si realment volia abordar aquest simplement, i la meva meta és moure 624 00:22:36,500 --> 00:22:39,800 tots els petits números d'aquesta manera, i impulsar totes les grans xifres que 625 00:22:39,800 --> 00:22:43,030 Així, per què no acaba de fer això al més ingènua manera possible i veure si 626 00:22:43,030 --> 00:22:45,730 pot fer-ho millor que el que era un bastant complex algoritme? 627 00:22:45,730 --> 00:22:46,620 >> Així que anem a veure. 628 00:22:46,620 --> 00:22:48,940 Quatre és un nombre bastant petit, així que estic sortirà d'allà ara. 629 00:22:48,940 --> 00:22:50,610 Ooh, el número dos és encara millor. 630 00:22:50,610 --> 00:22:52,230 Així es pot simplement fer un pas endavant per un moment? 631 00:22:52,230 --> 00:22:55,670 Aquesta és actualment el meu petit numerat candidat, i jo vaig a recordar 632 00:22:55,670 --> 00:22:57,000 que amb, com, una variable. 633 00:22:57,000 --> 00:22:57,930 Però jo vaig a seguir buscant. 634 00:22:57,930 --> 00:22:59,890 Hi ha algú la nombre és menor? 635 00:22:59,890 --> 00:23:00,460 Sis, no. 636 00:23:00,460 --> 00:23:01,390 Oh, hi ha Neil de nou. 637 00:23:01,390 --> 00:23:04,050 >> Així que vaig a empènyer de nou tipus de vista conceptual. 638 00:23:04,050 --> 00:23:05,120 Neil serà presentat. 639 00:23:05,120 --> 00:23:08,440 I ara, la variable que estic fent servir per realitzar un seguiment de qui té el més petit 640 00:23:08,440 --> 00:23:11,390 nombre s'actualitza per contenir La ubicació de Neil. 641 00:23:11,390 --> 00:23:12,110 Bé, anem a veure. 642 00:23:12,110 --> 00:23:13,960 Tres, set, cinc. 643 00:23:13,960 --> 00:23:15,590 Bé, sé que Neil era el més petit. 644 00:23:15,590 --> 00:23:18,110 Quina és la cosa més simple per a mi fer ara? 645 00:23:18,110 --> 00:23:21,410 Jo no vaig a perdre el meu temps amb només bombolles Neil 1 lloc a l'esquerra. 646 00:23:21,410 --> 00:23:25,350 Per què no acaba de posar Neil on pertany, que és, per descomptat, on? 647 00:23:25,350 --> 00:23:26,160 >> Tot el camí des del principi. 648 00:23:26,160 --> 00:23:27,720 Així que Neil, vine amb mi. 649 00:23:27,720 --> 00:23:28,910 ¿I quin era el seu nom? 650 00:23:28,910 --> 00:23:29,310 >> GRACE: Gràcia. 651 00:23:29,310 --> 00:23:29,710 >> DAVID J. Malan: Gràcia. 652 00:23:29,710 --> 00:23:29,920 D'acord. 653 00:23:29,920 --> 00:23:32,490 Així també la gràcia, per desgràcia, està una mica en el camí. 654 00:23:32,490 --> 00:23:34,290 Llavors, com podem resoldre aquest problema? 655 00:23:34,290 --> 00:23:34,490 Cert? 656 00:23:34,490 --> 00:23:37,500 Si es tracta d'una matriu, no hi ha només set llocs. 657 00:23:37,500 --> 00:23:40,830 Recordem que, amb Rob, parlem de declarant les edats, i que només tenia un 658 00:23:40,830 --> 00:23:41,740 nombre finit d'edats? 659 00:23:41,740 --> 00:23:42,535 La mateixa idea aquí. 660 00:23:42,535 --> 00:23:44,300 Només tenim un nombre finit d'enters. 661 00:23:44,300 --> 00:23:47,590 La gràcia és una mica en la nostra manera, així que com ho arreglem? 662 00:23:47,590 --> 00:23:49,555 >> La forma més senzilla és com, La gràcia, ho sento. 663 00:23:49,555 --> 00:23:51,870 Vas a haver d'anar allà, així que pot donar lloc. 664 00:23:51,870 --> 00:23:55,290 Ara, si es pensa en això, potser que acaba de fer el problema pitjor. 665 00:23:55,290 --> 00:23:58,510 I potser ho vam fer, perquè el que si La gràcia era al lloc correcte? 666 00:23:58,510 --> 00:24:01,730 Però sabem que no ho és, perquè en cas contrari, hauria estat 667 00:24:01,730 --> 00:24:03,980 peu cap endavant en lloc de Neil en aquest moment, no? 668 00:24:03,980 --> 00:24:05,550 Ja hem comprovat el seu nombre fos. 669 00:24:05,550 --> 00:24:05,770 >> Està bé. 670 00:24:05,770 --> 00:24:09,110 Així que ara, Neil està en el lloc correcte, i Jo puc fer una lleugera optimització. 671 00:24:09,110 --> 00:24:11,740 Durant la següent hora, vaig a ignorar Neil tots junts, a fi de no 672 00:24:11,740 --> 00:24:15,280 perdre el temps, o accidentalment li canviï al lloc equivocat. 673 00:24:15,280 --> 00:24:17,805 Així que ara, com puc trobar la següent element que és més petit? 674 00:24:17,805 --> 00:24:18,480 Dos. 675 00:24:18,480 --> 00:24:20,225 Això és un nombre força bo, si vol donar un pas endavant i 676 00:24:20,225 --> 00:24:21,100 Jo et recordaré. 677 00:24:21,100 --> 00:24:21,980 Sis, no és bo. 678 00:24:21,980 --> 00:24:24,820 Quatre, tres, set, cinc, no és bo. 679 00:24:24,820 --> 00:24:26,800 Així que anem a moure a seu lloc correcte. 680 00:24:26,800 --> 00:24:28,470 I vam tenir sort aquesta vegada. 681 00:24:28,470 --> 00:24:31,350 >> Ara, jo faré cas omís d'aquests dos nois, i ara fer una més 682 00:24:31,350 --> 00:24:32,260 passar a través d'això. 683 00:24:32,260 --> 00:24:33,490 Six que un nombre molt petit. 684 00:24:33,490 --> 00:24:34,300 Anem cap endavant. 685 00:24:34,300 --> 00:24:35,220 Oh, ho sento. 686 00:24:35,220 --> 00:24:37,640 Nombre de Grace és millor, per trepitjar cap endavant. 687 00:24:37,640 --> 00:24:38,260 Quatre. 688 00:24:38,260 --> 00:24:39,120 Ho sentim, Grace. 689 00:24:39,120 --> 00:24:39,950 Torna una altra vegada. 690 00:24:39,950 --> 00:24:41,550 El número tres és millor. 691 00:24:41,550 --> 00:24:42,290 Seven. 692 00:24:42,290 --> 00:24:42,720 Cinc. 693 00:24:42,720 --> 00:24:43,550 I ara, ¿quin és el teu nom? 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 Així que Jason és ara el més petit element que he seleccionat. 697 00:24:47,050 --> 00:24:49,160 A on va a anar? 698 00:24:49,160 --> 00:24:50,380 Així què sis és. 699 00:24:50,380 --> 00:24:51,210 I el seu nom és nou? 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 està en el camí. 703 00:24:53,220 --> 00:24:54,640 Quina és la cosa més fàcil de fer? 704 00:24:54,640 --> 00:24:58,390 Canvieu aquests dos nois i continuar. 705 00:24:58,390 --> 00:24:59,020 Així que ara veurem. 706 00:24:59,020 --> 00:25:00,170 Qui és el més petit? 707 00:25:00,170 --> 00:25:01,030 Quatre. 708 00:25:01,030 --> 00:25:01,990 Déjame només una mica de trampa. 709 00:25:01,990 --> 00:25:03,090 Cinc serà el més petit. 710 00:25:03,090 --> 00:25:05,220 Em sembla pròxim, si vostè vol fer un pas cap endavant, què tinc a veure amb 711 00:25:05,220 --> 00:25:06,820 aquests nois, amb Gabe? 712 00:25:06,820 --> 00:25:08,450 Canvia de nou. 713 00:25:08,450 --> 00:25:10,740 Així que ara, encara una mica fora de lloc. 714 00:25:10,740 --> 00:25:14,140 Vaig trobar Gabe sigui el més petit, pel que Ho fan esclatar cap a fora, vostè es mou nois més. 715 00:25:14,140 --> 00:25:15,190 I fet. 716 00:25:15,190 --> 00:25:17,200 >> Així que la resposta és la mateixa. 717 00:25:17,200 --> 00:25:18,600 El resultat final és el mateix. 718 00:25:18,600 --> 00:25:22,730 Quin d'aquests dos algorismes és millor? 719 00:25:22,730 --> 00:25:23,500 El segon, vaig sentir. 720 00:25:23,500 --> 00:25:24,252 Per què? 721 00:25:24,252 --> 00:25:25,900 >> ALTAVEU 3: És N passos [inaudible]. 722 00:25:25,900 --> 00:25:27,600 >> DAVID J. Malan: És n passos com a màxim. 723 00:25:27,600 --> 00:25:28,490 Interessant. 724 00:25:28,490 --> 00:25:30,610 Així és que, encara? 725 00:25:30,610 --> 00:25:33,630 Llavors, com puc trobar la element més petit? 726 00:25:33,630 --> 00:25:37,060 Quants passos vaig haver de prendre en trobar l'element més petit? 727 00:25:37,060 --> 00:25:39,220 Tenia una mirada tot el camí al final, no? 728 00:25:39,220 --> 00:25:41,530 Perquè en aquest cas més desfavorable, el que si Neil estaven per aquí? 729 00:25:41,530 --> 00:25:45,700 Així que trobar l'element més petit em n passos, o núm menys 1 presa. 730 00:25:45,700 --> 00:25:46,100 Però, a D'acord. 731 00:25:46,100 --> 00:25:46,980 Així fixar Neil. 732 00:25:46,980 --> 00:25:48,740 Recordeu que, un minut o així ho fa. 733 00:25:48,740 --> 00:25:51,680 >> Però, com trobar la següent element més petit? 734 00:25:51,680 --> 00:25:54,830 És n menys 1 o n almenys 2 realment, a partir del nombre de passos. 735 00:25:54,830 --> 00:25:55,440 Així que bé. 736 00:25:55,440 --> 00:25:57,390 Així que em vaig N almenys 2. 737 00:25:57,390 --> 00:25:57,600 Està bé. 738 00:25:57,600 --> 00:25:59,130 Així se sent una mica millor. 739 00:25:59,130 --> 00:25:59,730 Està bé. 740 00:25:59,730 --> 00:26:03,270 Quants passos la propera vegada per trobar el número tres? 741 00:26:03,270 --> 00:26:04,420 Per tant n almenys 4. 742 00:26:04,420 --> 00:26:07,670 Així que és decreixent, un menys pas en cada iteració. 743 00:26:07,670 --> 00:26:08,740 Així que això se sent millor, oi? 744 00:26:08,740 --> 00:26:13,450 Si l'última vegada que va ser més o menys n vegades n, aquesta vegada és n menys 1, més n menys 745 00:26:13,450 --> 00:26:16,500 2, més n menys 3, més n menys 4, punt, punt, punt. 746 00:26:16,500 --> 00:26:18,750 Però si vostè recorda de la seva escola secundària llibres de text, la petita trucs 747 00:26:18,750 --> 00:26:24,380 full a la part del darrere que té les fórmules, si realitzar la suma d'aquesta sèrie de nombres, 748 00:26:24,380 --> 00:26:31,280 el que és el nombre total de passos sigui que em prenc aquí? 749 00:26:31,280 --> 00:26:36,580 >> Aquest és un dels, com, n menys 1, n vegades, dividit per 2. 750 00:26:36,580 --> 00:26:39,040 Així que permetin-me veure si puc treure això per un moment. 751 00:26:39,040 --> 00:26:42,230 I de nou, estic una mica d'arrodoniment alguns números només per mantenir la nostra vida simple, 752 00:26:42,230 --> 00:26:47,830 però pel que recordo, és com si Faig n almenys 1 coses, llavors n menys 753 00:26:47,830 --> 00:26:53,570 2, llavors n menys 3, és més o menys una cosa així més de 2, i si 754 00:26:53,570 --> 00:26:55,510 multipliqui això, això és realitat plaça núm. 755 00:26:55,510 --> 00:26:58,940 Que no se sent molt bé. n menys n sobre 2. 756 00:26:58,940 --> 00:27:00,350 >> Però aquí està la cosa. 757 00:27:00,350 --> 00:27:03,720 En ciències de la computació, quan els problemes començar a posar-se interessant és quan n 758 00:27:03,720 --> 00:27:04,700 es posa molt gran. 759 00:27:04,700 --> 00:27:08,110 I quan n es fa molt gran, que d' aquests valors es van a dominar tota 760 00:27:08,110 --> 00:27:09,750 dels altres? 761 00:27:09,750 --> 00:27:10,990 És una mica el n al quadrat, oi? 762 00:27:10,990 --> 00:27:13,340 Sí, dividir per 2 és bastant bo. 763 00:27:13,340 --> 00:27:16,740 Però si vostè està parlant de milers de milions de peces de dades, o trilions de 764 00:27:16,740 --> 00:27:18,700 peces de dades, OK, pel que vostè és el doble de ràpid. 765 00:27:18,700 --> 00:27:22,440 Però a qui li importa si és molt gran el nombre, si aquest factor és el que fa 766 00:27:22,440 --> 00:27:23,040 més i més gran. 767 00:27:23,040 --> 00:27:25,990 I sens dubte, té més de una diferència d'aquest tipus. 768 00:27:25,990 --> 00:27:29,120 Així que tot i que vostès estan bé, el segon algorisme, l'anomenarem 769 00:27:29,120 --> 00:27:32,970 ordenació per selecció, és a dir, en el món real, un poc més ràpid en potència, perquè sóc 770 00:27:32,970 --> 00:27:35,360 tenint cada vegada menys passos cada vegada. 771 00:27:35,360 --> 00:27:37,340 >> En realitat no és fonamentalment més ràpid. 772 00:27:37,340 --> 00:27:41,430 Perquè si en realitat ens juguem això per grans valors de n, al final de 773 00:27:41,430 --> 00:27:44,750 del dia, durant el temps suficient n gran, és encara va a sentir bastant lent. 774 00:27:44,750 --> 00:27:46,770 Bé, deixa prendre una últim pas en això. 775 00:27:46,770 --> 00:27:48,920 Això és el que jo anomenaria ordenació per selecció. 776 00:27:48,920 --> 00:27:51,040 Poden vostès restablir mateixos per última vegada? 777 00:27:51,040 --> 00:27:53,550 I en aquest últim cas, vaig proposar alguna cosa 778 00:27:53,550 --> 00:27:54,970 anomenada ordenació per inserció. 779 00:27:54,970 --> 00:27:57,470 L'ordenació per inserció és, conceptualment, una mica diferent. 780 00:27:57,470 --> 00:28:00,980 >> En lloc d'anar i venir i seleccionar l'element més petit, estic 781 00:28:00,980 --> 00:28:05,030 només anem a tractar cada un d'aquests nois que em trobo, i inserit 782 00:28:05,030 --> 00:28:06,850 ells en el seu lloc correcte. 783 00:28:06,850 --> 00:28:10,160 Així que vaig a començar amb la Gràcia, i veig que ella és el número quatre. 784 00:28:10,160 --> 00:28:11,720 A on pertany el número quatre? 785 00:28:11,720 --> 00:28:14,940 Encara no he començat la classificació res, Així que la gràcia arriba a quedar-s'hi. 786 00:28:14,940 --> 00:28:18,355 I ara vaig a reclamar, si pogués donar un pas a la dreta, aquesta 787 00:28:18,355 --> 00:28:21,650 meva llista ordenada, aquest és el meu llista restant Unsorted. 788 00:28:21,650 --> 00:28:23,260 Així que ara vaig a procedir a continuació, i quin és el teu nom? 789 00:28:23,260 --> 00:28:23,700 >> Branson:. 790 00:28:23,700 --> 00:28:24,150 >> DAVID J. Malan: Branson. 791 00:28:24,150 --> 00:28:25,375 Així Branson és el número dos. 792 00:28:25,375 --> 00:28:27,490 Així que vaig a haver de per un moment. 793 00:28:27,490 --> 00:28:30,940 I ara, ¿a on pertanys en aquesta sèrie? 794 00:28:30,940 --> 00:28:32,360 Així que a la dreta de la Gràcia. 795 00:28:32,360 --> 00:28:35,670 Així que de nou, estem com el La gràcia fer un munt de treball aquí. 796 00:28:35,670 --> 00:28:37,290 A on et posem? 797 00:28:37,290 --> 00:28:40,120 Així que anem per lliscar a la a l'esquerra, i introduïu Branson allà. 798 00:28:40,120 --> 00:28:41,680 Però ara afirmo que vostès fan. 799 00:28:41,680 --> 00:28:43,240 Però cal notar, no vaig a utilitzar l'espai addicional. 800 00:28:43,240 --> 00:28:45,130 Segueix sent 2 elements aquí, maig aquí. 801 00:28:45,130 --> 00:28:47,910 Mida total de la matriu és de 7, així que estic No fer trampa, d'acord? 802 00:28:47,910 --> 00:28:51,950 >> Així que ara tenim, amb Gabe aquí, el número sis, on pertany vostè? 803 00:28:51,950 --> 00:28:52,650 Vas tenir sort de nou. 804 00:28:52,650 --> 00:28:53,820 Així que vostè pot quedar-s'hi. 805 00:28:53,820 --> 00:28:57,210 Només cal fer un lleuger pas a la dreta només per deixar en clar que està ordenada. 806 00:28:57,210 --> 00:29:00,520 I ara tenim a Neil de nou, el nombre de un, ¿a on vas? 807 00:29:00,520 --> 00:29:03,540 I ara és quan anem a començar a veure que aquest algorisme, encara que en la primera 808 00:29:03,540 --> 00:29:05,950 mirada, se sent molt intel · ligent, cura el que està a punt de succeir. 809 00:29:05,950 --> 00:29:07,370 Si pogués fer un pas endavant. 810 00:29:07,370 --> 00:29:09,260 >> On volem posar Neil? 811 00:29:09,260 --> 00:29:11,830 Així que, òbviament, aquí, així que com Com aconseguim Neil allà? 812 00:29:11,830 --> 00:29:12,970 Farem això pas a pas. 813 00:29:12,970 --> 00:29:15,620 Gabe, on ha d'anar? 814 00:29:15,620 --> 00:29:19,590 Sí, a fi de prendre un gran pas, o dues mitges passos per fer 815 00:29:19,590 --> 00:29:20,820 un pas més enllà. 816 00:29:20,820 --> 00:29:21,750 Gràcia, on vas? 817 00:29:21,750 --> 00:29:22,510 Bé. 818 00:29:22,510 --> 00:29:23,500 Així que un altre pas. 819 00:29:23,500 --> 00:29:24,960 I, finalment, Branson? 820 00:29:24,960 --> 00:29:25,460 Un pas més. 821 00:29:25,460 --> 00:29:27,190 I ara podem posar Neil al seu lloc. 822 00:29:27,190 --> 00:29:28,440 >> Així que ara, segueixen aquesta lògica. 823 00:29:28,440 --> 00:29:32,420 Tot i que no estem canviant Neil altra, i una altra, i una altra, per posar- 824 00:29:32,420 --> 00:29:36,420 on va, en el pitjor dels casos, la següent nombre, podríem trobar-nos podria 825 00:29:36,420 --> 00:29:42,220 sigui el nombre, per exemple, hi va haver un nombre zero, llavors canviarem tots 826 00:29:42,220 --> 00:29:42,730 aquests nois. 827 00:29:42,730 --> 00:29:44,950 Suposem que hi ha un nombre negatiu un, llavors hem de canviar 828 00:29:44,950 --> 00:29:46,080 tots aquests nois. 829 00:29:46,080 --> 00:29:48,500 Així que estem realment només una mica de moure d'una tirada el problema de la volta, de manera que estem 830 00:29:48,500 --> 00:29:52,620 la transferència de la costa de l' procés de selecció pel que la inserció 831 00:29:52,620 --> 00:29:56,930 procés, de manera que vostès acabaven de per moure més o menys n almenys alguna cosa 832 00:29:56,930 --> 00:29:57,940 nombre de passos. 833 00:29:57,940 --> 00:30:01,200 I aquest nombre de passos només es va augmentant a mesura que selecciono més números, 834 00:30:01,200 --> 00:30:04,730 si he de seguir empenyent a vostès esquena, i l'esquena, i l'esquena. 835 00:30:04,730 --> 00:30:08,320 >> Així ho trist ara és tot això algoritmes són n al quadrat. 836 00:30:08,320 --> 00:30:10,570 Seguirem endavant i gràcies a ells nois, i visualitzar aquestes una mica 837 00:30:10,570 --> 00:30:11,090 diferent. 838 00:30:11,090 --> 00:30:12,312 Molt ben fet. 839 00:30:12,312 --> 00:30:14,120 >> [Aplaudiments] 840 00:30:14,120 --> 00:30:15,030 >> Està bé. 841 00:30:15,030 --> 00:30:16,280 Aquí el tens. 842 00:30:16,280 --> 00:30:18,390 843 00:30:18,390 --> 00:30:18,470 Gràcies per - 844 00:30:18,470 --> 00:30:19,190 >> Branson: [Inaudible] mantenir els números. 845 00:30:19,190 --> 00:30:21,990 >> DAVID J. Malan: No, vostè pot mantenir els números també. 846 00:30:21,990 --> 00:30:23,440 Està bé. 847 00:30:23,440 --> 00:30:24,100 Molt ben fet. 848 00:30:24,100 --> 00:30:25,300 Està bé. 849 00:30:25,300 --> 00:30:30,510 Així que anem a veure si ara no podem resumir més ràpidament, i més visualment, 850 00:30:30,510 --> 00:30:33,410 exactament el que ha passat aquí com segueix. 851 00:30:33,410 --> 00:30:36,510 852 00:30:36,510 --> 00:30:38,770 Vaig a seguir endavant i tiri cap amunt Firefox. 853 00:30:38,770 --> 00:30:41,310 Ens vinculem aquesta demostració a la pàgina web del curs. 854 00:30:41,310 --> 00:30:43,870 Java és una mica molest per aconseguir feina en alguns navegadors en aquests dies. 855 00:30:43,870 --> 00:30:46,760 Així que si no jugues amb això a casa, s'adona que podria haver de fer servir Firefox 856 00:30:46,760 --> 00:30:47,990 perquè funcioni. 857 00:30:47,990 --> 00:30:50,440 I què faré amb aquesta demostració és la següent. 858 00:30:50,440 --> 00:30:54,875 >> A la part inferior, tinc un munt de opcions del menú, incloent un inici i un 859 00:30:54,875 --> 00:30:55,840 botó d'aturar. 860 00:30:55,840 --> 00:30:59,450 A més, en un apart, sembla que hi ha una error en aquests programes, per la qual cosa 861 00:30:59,450 --> 00:31:03,720 no pot veure realment l'inici o aturar botó llevat que mantingui Comando o Alt 862 00:31:03,720 --> 00:31:06,560 més i zoom in, que curiosament que mostra més botons. 863 00:31:06,560 --> 00:31:09,090 Així que ho dic si jugues amb això a casa. 864 00:31:09,090 --> 00:31:12,870 Ara vaig a fer clic a Inici, en un Actualment, després d'especificar un retard de, 865 00:31:12,870 --> 00:31:16,810 com, a 200 mil · lèsimes de segon aquí, molt perquè puguem veure el que passa. 866 00:31:16,810 --> 00:31:20,180 >> Per això afirmo que es tracta d'una visualització de la primera algorisme 867 00:31:20,180 --> 00:31:23,730 aquests nois han fet, una mena de bombolla, en què intercanviem persones per parells. 868 00:31:23,730 --> 00:31:27,490 La idea clau d'aquesta visualització és que l'altura de les barres 869 00:31:27,490 --> 00:31:30,510 representa la mida del nombre. 870 00:31:30,510 --> 00:31:32,210 Així que la més alta és la barra, més gran sigui el nombre. 871 00:31:32,210 --> 00:31:33,680 Shorter la barra, més petit és el nombre. 872 00:31:33,680 --> 00:31:38,630 I si et dones compte, que estem passant la primera iteració d'aquest algorisme, 873 00:31:38,630 --> 00:31:42,620 intercanvi de nombres grans i petits, de manera que el nombre petit ve primer i 874 00:31:42,620 --> 00:31:44,280 el nombre gran va a la dreta. 875 00:31:44,280 --> 00:31:48,770 >> I tan aviat com arribem al final de la matriu de molts més números de set, estem 876 00:31:48,770 --> 00:31:49,900 va a anar de nou al principi. 877 00:31:49,900 --> 00:31:51,140 I anticipar això. 878 00:31:51,140 --> 00:31:54,860 A l'extrem esquerre, que poc home va per intercanviar a un costat, i aquest 879 00:31:54,860 --> 00:31:56,010 procés es repeteix. 880 00:31:56,010 --> 00:31:59,450 Ara aquesta visualització ràpidament es avorrit, així que seguirem endavant i deixar de 881 00:31:59,450 --> 00:32:04,170 , Canvieu el retard alguna cosa molt més ràpid només per ara, una idea de 882 00:32:04,170 --> 00:32:05,060 aquest algorisme. 883 00:32:05,060 --> 00:32:07,840 >> Així que, encara que he accelerar cap amunt, això és com actualitzar el meu processador, la compra d' 884 00:32:07,840 --> 00:32:08,580 un equip nou. 885 00:32:08,580 --> 00:32:12,980 No he canviat fonamentalment el meu algorisme, però de fet pot veure més 886 00:32:12,980 --> 00:32:16,800 clarament que amb els éssers humans, que el gran números estan sortint al cim, 887 00:32:16,800 --> 00:32:20,900 i els números petits estan sortint cap avall a la part inferior. 888 00:32:20,900 --> 00:32:22,390 I ara aquesta cosa ordenada. 889 00:32:22,390 --> 00:32:25,260 I en un a part, a les places, no hi ha només algunes comptabilitat allà per 890 00:32:25,260 --> 00:32:28,010 l'ajuden a explicar la quantitat de comparacions, o quants swaps tenen 891 00:32:28,010 --> 00:32:28,950 en realitat s'ha fet. 892 00:32:28,950 --> 00:32:30,750 >> Bé, anem a provar una de els altres que vam veure. 893 00:32:30,750 --> 00:32:37,116 Permetin-me clic a mena de bombolla aquí, i permetre triar, i aquesta pàgina web sencera 894 00:32:37,116 --> 00:32:38,936 està lliure d'errors. 895 00:32:38,936 --> 00:32:41,155 Acceptem el risc i lo de nou. 896 00:32:41,155 --> 00:32:44,560 897 00:32:44,560 --> 00:32:45,030 Això és. 898 00:32:45,030 --> 00:32:47,180 Així que farem una mena de selecció. 899 00:32:47,180 --> 00:32:49,140 No sé per què el menú apareix per allà. 900 00:32:49,140 --> 00:32:54,070 Anem a apropar a arreglar això bug, canviar-ho a 50. 901 00:32:54,070 --> 00:32:56,020 Ah, farem realitat que molt més ràpid. 902 00:32:56,020 --> 00:32:59,160 Cinc mil · lisegons o menys, i Start. 903 00:32:59,160 --> 00:33:00,470 >> Així que aquesta és la selecció de gènere. 904 00:33:00,470 --> 00:33:03,070 Així que de nou, pensar en el que va fer amb els éssers humans fins aquí. 905 00:33:03,070 --> 00:33:08,490 Vam anar a través de la matriu i seleccionem l'element més petit de nou, 906 00:33:08,490 --> 00:33:09,250 i una altra, i una altra. 907 00:33:09,250 --> 00:33:11,110 Ara afirmo que encara era bastant dolent. 908 00:33:11,110 --> 00:33:15,010 Seguia n al quadrat, més o menys, però era, en el món real, una mica 909 00:33:15,010 --> 00:33:18,280 més ràpid, perquè estava prenent de fet poc menys passos cada vegada. 910 00:33:18,280 --> 00:33:19,800 Però només estem parlant de què? 911 00:33:19,800 --> 00:33:21,830 Potser 40 o més barres d'aquí? 912 00:33:21,830 --> 00:33:23,200 No estem parlant de 40 milions. 913 00:33:23,200 --> 00:33:27,430 Així que no és totalment clar per a mi que era de fet un guany significativa. 914 00:33:27,430 --> 00:33:32,530 >> Permetin-me ara tornar enrere i canviar al nostre tercer algoritme, el qual va ser seleccionar 915 00:33:32,530 --> 00:33:33,180 ordenació per inserció. 916 00:33:33,180 --> 00:33:36,380 I ara és realment errors perquè el menú realment no hauria d'estar allà. 917 00:33:36,380 --> 00:33:40,840 Així que ara anem a retrocedir aquí i començar aquest algorisme. 918 00:33:40,840 --> 00:33:43,270 Whoop, iniciar i aturar. 919 00:33:43,270 --> 00:33:47,160 Així que aquest tipus de compte amb un model bonic a ella, amb el que estem de nou 920 00:33:47,160 --> 00:33:50,240 la inserció dels éssers humans, o en aquest cas, les barres en 921 00:33:50,240 --> 00:33:52,620 la seva ubicació adequada. 922 00:33:52,620 --> 00:33:55,430 I ja ho ha fet abans Em vaig donar la volta. 923 00:33:55,430 --> 00:33:58,940 Però això, també, en teoria, encara és N quadrat. 924 00:33:58,940 --> 00:34:01,430 >> Així que anem a veure si podem resumir aquests com segueix. 925 00:34:01,430 --> 00:34:04,750 Vaig a seguir endavant i només per donar nosaltres una espècie d'una manera comuna de parlar 926 00:34:04,750 --> 00:34:08,489 sobre aquestes coses, permetin-me presentar només una mica de notació aquí. 927 00:34:08,489 --> 00:34:12,480 Estàs a punt de veure una cosa anomenada gran O, ja que és, literalment, un gran 928 00:34:12,480 --> 00:34:16,320 O. I aquesta és una manera de que un equip científic o un matemàtic, fins i tot utilitza 929 00:34:16,320 --> 00:34:19,230 per descriure el temps d'execució d'algun algoritme. 930 00:34:19,230 --> 00:34:21,400 Quants passos que realment necessita? 931 00:34:21,400 --> 00:34:25,080 >> Ara em vaig a avergonyir a mi mateix amb la meva lletra aquí a un moment. 932 00:34:25,080 --> 00:34:29,020 Però m'ho dius seguir endavant i dir que això va a ser gran O per aquí. 933 00:34:29,020 --> 00:34:33,610 I permetin-me presentar a un altre símbol, un omega capital. 934 00:34:33,610 --> 00:34:37,080 Omega serà l'oposada, en essència, de la gran O. Considerant que la gran O 935 00:34:37,080 --> 00:34:40,790 mitjans, en el pitjor dels casos, la quantitat de temps Podria prendre algun algorisme, en 936 00:34:40,790 --> 00:34:43,480 termes de n, omega va a serà la quantitat de temps que podria 937 00:34:43,480 --> 00:34:45,409 tenir en el millor dels casos. 938 00:34:45,409 --> 00:34:48,090 I veurem el que entenem per millor dels casos, en un moment. 939 00:34:48,090 --> 00:34:49,940 >> Així que anem a començar una cosa simple. 940 00:34:49,940 --> 00:34:54,719 Permetin-me començar amb una recerca lineal. 941 00:34:54,719 --> 00:34:55,679 Per tant no classificació. 942 00:34:55,679 --> 00:34:58,000 Anomenarem a aquesta cerca lineal. 943 00:34:58,000 --> 00:35:01,140 I ara, fer una mica de taula de sortir d'això. 944 00:35:01,140 --> 00:35:06,600 I ara, en el cas de cerca lineal, en el pitjor dels casos, la quantitat de passos és 945 00:35:06,600 --> 00:35:11,770 que em portarà a trobar una nombre d'elecció arbitrària? 946 00:35:11,770 --> 00:35:14,540 I hi ha n portes totals o n el nombre total. 947 00:35:14,540 --> 00:35:15,940 Pitjor dels casos. 948 00:35:15,940 --> 00:35:18,800 Quants passos que vaig a haver de prendre per trobar el número 50 en una sèrie 949 00:35:18,800 --> 00:35:20,830 de n portes? 950 00:35:20,830 --> 00:35:21,410 ¿I per què? 951 00:35:21,410 --> 00:35:23,680 A causa que pot ser tot el camí cap al final. 952 00:35:23,680 --> 00:35:27,120 Així que igual que Jennifer es va trobar amb el nombre 50 va ser tot el camí, pel que en 953 00:35:27,120 --> 00:35:30,760 el pitjor dels casos cerca lineal és gran O de n, direm. 954 00:35:30,760 --> 00:35:33,430 >> I el millor dels casos, si vostè aconsegueix realment afortunat? 955 00:35:33,430 --> 00:35:36,200 No només va a fer un pas, o un nombre constant de passos. 956 00:35:36,200 --> 00:35:37,830 Així que anem a descriure això com 1. 957 00:35:37,830 --> 00:35:39,010 Així que això és bastant bo. 958 00:35:39,010 --> 00:35:41,210 Ara el que si hem fet alguna cosa com a recerca binària? 959 00:35:41,210 --> 00:35:43,860 960 00:35:43,860 --> 00:35:47,846 Cerca binària Així, en el pitjor dels casos cas, es va emportar la quantitat de temps? 961 00:35:47,846 --> 00:35:49,250 >> [Interrompent VEUS] 962 00:35:49,250 --> 00:35:51,310 >> DAVID J. Malan: Així que en realitat, escoltat en un parell de llocs. 963 00:35:51,310 --> 00:35:56,390 Així que en realitat log n, més o menys, perquè com es divideix la llista en mitja 964 00:35:56,390 --> 00:36:00,730 una altra vegada, i una altra, i una altra, som capaços de per trobar, en última instància, el valor, 965 00:36:00,730 --> 00:36:04,750 si hi és, però hi ha una trampa. 966 00:36:04,750 --> 00:36:08,590 Quina és la suposició que hem de donar per fet de cerca binària? 967 00:36:08,590 --> 00:36:09,700 Ha de ser resolt. 968 00:36:09,700 --> 00:36:12,770 No està resolt, es pot dividir la cosa la meitat una altra vegada i una altra, i vostè 969 00:36:12,770 --> 00:36:15,490 pot anar a l'esquerra, i es pot anar a la dreta, i vostè pot anar a l'esquerra i la dreta, però vostè és 970 00:36:15,490 --> 00:36:18,070 No va a trobar l'element si la llista no està ordenada, perquè 971 00:36:18,070 --> 00:36:18,790 potser et perdis. 972 00:36:18,790 --> 00:36:22,120 Com que la seva heurística, per anar a l'esquerra o cap a la dreta serà defectuós si és 973 00:36:22,120 --> 00:36:23,420 de fet no ordenats. 974 00:36:23,420 --> 00:36:26,110 Així que hi ha una mena de cost ocult per a l'ús d'alguna cosa com això. 975 00:36:26,110 --> 00:36:29,250 >> Ara, anirem a la nostra selecció algoritmes no buscar - 976 00:36:29,250 --> 00:36:31,140 oh, realment anirem en aquest espai en blanc. 977 00:36:31,140 --> 00:36:33,190 Cerca binària en el millor dels casos? 978 00:36:33,190 --> 00:36:36,290 També és 1 si només passa a ser en ple centre de la matriu, o 979 00:36:36,290 --> 00:36:37,810 el mitjà de la guia telefònica. 980 00:36:37,810 --> 00:36:39,710 Ara farem una mena de bombolla. 981 00:36:39,710 --> 00:36:42,570 Així que de nou, ara que estem entrant al tipus, no les recerques. 982 00:36:42,570 --> 00:36:47,220 >> En el pitjor dels casos, la quantitat de passos que van fer reclamació mena de bombolla va a prendre? 983 00:36:47,220 --> 00:36:48,410 n al quadrat. 984 00:36:48,410 --> 00:36:49,200 Així que vaig a dibuixar això. 985 00:36:49,200 --> 00:36:51,710 Oh, la meva lletra es veu encara pitjor quan es preveu que tan gran. 986 00:36:51,710 --> 00:36:52,510 Està bé. 987 00:36:52,510 --> 00:36:53,570 Així que això és n al quadrat. 988 00:36:53,570 --> 00:36:59,460 I en el millor dels casos de l'espècie de bombolla, quants passos es va a prendre? 989 00:36:59,460 --> 00:37:00,980 1, ho vaig sentir. 990 00:37:00,980 --> 00:37:01,760 >> ALTAVEU 1: n. 991 00:37:01,760 --> 00:37:03,286 >> DAVID J. Malan: n, vaig escoltar. 992 00:37:03,286 --> 00:37:04,200 >> ALTAVEU 1: 2. 993 00:37:04,200 --> 00:37:05,010 >> DAVID J. Malan: 2, vaig escoltar. 994 00:37:05,010 --> 00:37:06,670 Escolte 3? 995 00:37:06,670 --> 00:37:07,080 Està bé. 996 00:37:07,080 --> 00:37:11,390 Això he sentit 1, n, 2, però anem a recollir a més, almenys, el primer dels 997 00:37:11,390 --> 00:37:12,330 suggeriments, 1. 998 00:37:12,330 --> 00:37:15,370 No és un mal instint, perquè tipus de segueix un patró aquí. 999 00:37:15,370 --> 00:37:19,670 Però si només es necessiten 1 pas, com en el món podria jo afirmar que la llista 1000 00:37:19,670 --> 00:37:22,900 està ordenada, perquè si només es em permet prendre 1 pas, quants elements 1001 00:37:22,900 --> 00:37:25,230 vaig poder comprovar realment estar segur? 1002 00:37:25,230 --> 00:37:28,270 Bé, només 1, el que significa que hi ha n almenys 1 elements que podrien estar fora de 1003 00:37:28,270 --> 00:37:31,310 ordre, i em vaig a la fe després d' mirant que l'element 1 1004 00:37:31,310 --> 00:37:31,850 cosa està ordenada. 1005 00:37:31,850 --> 00:37:33,930 Així que 1 no és correcte aquí. 1006 00:37:33,930 --> 00:37:35,710 Així mínimament, quants Què he de mirar? 1007 00:37:35,710 --> 00:37:36,680 >> [Interrompent VEUS] 1008 00:37:36,680 --> 00:37:40,160 >> DAVID J. Malan: n menys 1, o en realitat, n, perquè he de mirar cada 1009 00:37:40,160 --> 00:37:42,190 joc, assegurant que no és fora de servei. 1010 00:37:42,190 --> 00:37:44,750 Però una vegada més, anem a resoldre d'ona nostre mans en els números més petits i 1011 00:37:44,750 --> 00:37:47,100 suposen que, quan n es fa gran, són sense interès de totes maneres. 1012 00:37:47,100 --> 00:37:48,380 Així que és una mena de bombolla. 1013 00:37:48,380 --> 00:37:49,830 I ara, farem aquestes dues últimes. 1014 00:37:49,830 --> 00:37:53,520 Selecció de tipus i, a continuació anem a fer l'ordenació per inserció. 1015 00:37:53,520 --> 00:37:57,160 I després anem a volar la teva ments amb alguna cosa molt 1016 00:37:57,160 --> 00:37:58,926 millor que tots aquests. 1017 00:37:58,926 --> 00:38:00,410 Està bé. 1018 00:38:00,410 --> 00:38:04,700 >> Quin és el pitjor dels casos s'executa moment de l'ordenació per selecció? 1019 00:38:04,700 --> 00:38:05,680 >> ALTAVEU 4: n al quadrat. 1020 00:38:05,680 --> 00:38:06,710 >> DAVID J. Malan: plaça n, estic escoltant. 1021 00:38:06,710 --> 00:38:09,790 Però per què n al quadrat, intuïtivament? 1022 00:38:09,790 --> 00:38:11,170 >> ALTAVEU 4: Perquè ens vam fer. 1023 00:38:11,170 --> 00:38:12,260 >> DAVID J. Malan: Perquè ens vam fer. 1024 00:38:12,260 --> 00:38:12,550 D'acord. 1025 00:38:12,550 --> 00:38:13,380 Bona resposta. 1026 00:38:13,380 --> 00:38:16,660 Però, intuïtivament, per què és la selecció tipus n al quadrat? 1027 00:38:16,660 --> 00:38:18,980 Què havíem de fer una i altra vegada? 1028 00:38:18,980 --> 00:38:22,570 Vam haver mantenir l'exploració a través, són que els més petits, és vostè el 1029 00:38:22,570 --> 00:38:24,020 més petit, ets el més petit. 1030 00:38:24,020 --> 00:38:27,480 I concedeix, hem estat capaços de prendre n passos, llavors n menys 1, llavors n menys 2. 1031 00:38:27,480 --> 00:38:30,700 Però si que tipus de agrega els tot, o emporta-te'l amb tu en la fe que he afegit 1032 00:38:30,700 --> 00:38:34,810 ells per endavant, tenim més o menys n quadrat menys alguns números més petits. 1033 00:38:34,810 --> 00:38:36,730 Així que vaig a trucar a aquest n al quadrat. 1034 00:38:36,730 --> 00:38:39,530 Però amb l'ordenació per selecció de la millor cas, la quantitat de passos és 1035 00:38:39,530 --> 00:38:40,632 em portarà? 1036 00:38:40,632 --> 00:38:41,840 >> ALTAVEU 5: [inaudible] 1037 00:38:41,840 --> 00:38:44,350 >> DAVID J. Malan: És lamentablement sent n al quadrat, oi? 1038 00:38:44,350 --> 00:38:49,590 Perquè si estic seleccionant els més petits element, i vam tenir set persones aquí, 1039 00:38:49,590 --> 00:38:53,280 L'únic que sé, un cop arribi a la mateixa fi, que he trobat el més petit 1040 00:38:53,280 --> 00:38:55,670 nombre, allà on ella va poder haver estat. 1041 00:38:55,670 --> 00:38:58,820 Però, com puc trobar la següent nombre més petit? 1042 00:38:58,820 --> 00:39:00,160 He de fer una altra passada. 1043 00:39:00,160 --> 00:39:04,810 Així que en el millor dels casos, quin és el d'entrada a la selecció de tipus? 1044 00:39:04,810 --> 00:39:07,830 És una llista ia tipus, número u, número dos, nombre tres, número quatre. 1045 00:39:07,830 --> 00:39:08,600 Però jo sóc un ordinador. 1046 00:39:08,600 --> 00:39:10,190 Només puc mirar 01:00 cosa alhora. 1047 00:39:10,190 --> 00:39:12,465 No puc ordenar de fer un pas nou com un ésser humà i dir: 1048 00:39:12,465 --> 00:39:14,030 ooh, això sembla correcte. 1049 00:39:14,030 --> 00:39:17,580 >> Només puc jutjar la correcció de ordenació per selecció, seleccionant el 1050 00:39:17,580 --> 00:39:18,370 nombre més petit. 1051 00:39:18,370 --> 00:39:21,390 Però fins i tot si trobo el número u en primer lloc, si jo no sé res més sobre 1052 00:39:21,390 --> 00:39:24,460 els altres nombres, que no ho faig, tot el que Sé que m'han donat una sèrie 1053 00:39:24,460 --> 00:39:27,930 o un conjunt de portes de darrere de la qual estan números, l'única manera que sé que un 1054 00:39:27,930 --> 00:39:28,680 era la més petita? 1055 00:39:28,680 --> 00:39:32,440 Si aconsegueixo fins aquí i m'adono, maleïda sigui, un era de fet el més petit. 1056 00:39:32,440 --> 00:39:34,870 >> Però com llavors determinar que dos és el costat més petit? 1057 00:39:34,870 --> 00:39:38,350 En fer la mateixa ineficiència una i altra vegada. 1058 00:39:38,350 --> 00:39:42,210 Així que finalment, amb l'ordenació per inserció, com, en el pitjor dels casos, 1059 00:39:42,210 --> 00:39:44,990 vam dir que realitza? 1060 00:39:44,990 --> 00:39:49,100 Això també és n al quadrat. 1061 00:39:49,100 --> 00:39:53,020 ¿I què hi ha amb el millor dels casos? 1062 00:39:53,020 --> 00:39:56,282 Anem a deixar això com un cliffhanger. 1063 00:39:56,282 --> 00:40:00,090 Ens omplirem que la propera vegada en blanc, però primer m'ho dius proposo que 1064 00:40:00,090 --> 00:40:02,620 fonamentalment fer millor que tot això, d'acord? 1065 00:40:02,620 --> 00:40:05,220 >> Així que pensar per tu mateix el que la inserció tipus serà. 1066 00:40:05,220 --> 00:40:06,910 Bé, això no va ser molt dramàtica, perquè jo sóc l'únic 1067 00:40:06,910 --> 00:40:08,970 que va veure el canvi. 1068 00:40:08,970 --> 00:40:09,620 Wow. 1069 00:40:09,620 --> 00:40:10,420 D'acord. 1070 00:40:10,420 --> 00:40:12,615 Així que aquí tenim una mica diferent demostració. 1071 00:40:12,615 --> 00:40:16,580 Si puc ampliar aquí, veureu que per l'esquerra tenim una mena de bombolla, al 1072 00:40:16,580 --> 00:40:20,740 centre tenim ordenació per selecció, i en l'extrema dreta, que tenim alguna cosa 1073 00:40:20,740 --> 00:40:23,380 no han mirat encara anomenada fusionar espècie. 1074 00:40:23,380 --> 00:40:26,080 Però pensem què hem estat fent aquí fins al moment actual. 1075 00:40:26,080 --> 00:40:29,200 Quan Jennifer va arribar per primera vegada a un escenari, ens vam anar a través de la matriu de nombres 1076 00:40:29,200 --> 00:40:33,750 una altra vegada, i una altra, amb recerca lineal, i tenim temps de funcionament lineal, big O 1077 00:40:33,750 --> 00:40:35,100 de n, per dir-ho. 1078 00:40:35,100 --> 00:40:41,000 >> Quan considerem ara la primera setmana de classe, quan havíem divideix i venceràs, 1079 00:40:41,000 --> 00:40:43,740 i teníem la guia telefònica llagrimeig, i Jennifer, i col · lectivament 1080 00:40:43,740 --> 00:40:47,500 aprofitat aquest coneixement fonamental, que havia repetir-se una vegada i una altra 1081 00:40:47,500 --> 00:40:50,930 d'alguna manera tirar, tirar, llençar, la meitat del problema, o 1082 00:40:50,930 --> 00:40:55,320 en general, la divisió d'un problema en un mitjà, i després el tractament de la peça més petita de 1083 00:40:55,320 --> 00:40:59,630 el problema com conceptualment equivalent a l'altra, que d'alguna manera vam 1084 00:40:59,630 --> 00:41:00,910 fonamentalment millor. 1085 00:41:00,910 --> 00:41:04,720 Però amb l'ordenació de bombolla, amb la selecció espècie, amb l'ordenació per inserció, hem podrà 1086 00:41:04,720 --> 00:41:06,560 hi ha tals idees que Jennifer va fer. 1087 00:41:06,560 --> 00:41:10,220 Ens pràcticament només caminem de tornada i successivament un munt de vegades, i 1088 00:41:10,220 --> 00:41:12,650 coses pessigat una mica, canviant en aquest ordre, potser 1089 00:41:12,650 --> 00:41:13,730 inserir o seleccionar. 1090 00:41:13,730 --> 00:41:16,950 Però al final del dia, vaig fer un munt de caminar maldestre d'anada i tornada. 1091 00:41:16,950 --> 00:41:21,160 Nosaltres realment no aprofitar alguna cosa intel · ligent com Jennifer li agradava dividir 1092 00:41:21,160 --> 00:41:22,040 i la conquesta. 1093 00:41:22,040 --> 00:41:25,620 >> Així fusionar espècie, per contra, el que ens no veurà fins a la setmana, que va 1094 00:41:25,620 --> 00:41:29,540 aprofitar aquesta idea clau dividint l'entrada, i després reduir a la meitat, i després 1095 00:41:29,540 --> 00:41:30,580 reduir a la meitat, i després reduir a la meitat. 1096 00:41:30,580 --> 00:41:34,590 I en cada iteració del bucle que, la classificació de la meitat esquerra i la dreta 1097 00:41:34,590 --> 00:41:38,200 mitjà, llavors la meitat esquerra de la meitat esquerra, i la meitat dreta de l'esquerra, a continuació, 1098 00:41:38,200 --> 00:41:40,990 la meitat esquerra de la part dreta, i la meitat dreta de la meitat dreta. 1099 00:41:40,990 --> 00:41:42,840 I repetint una i altra vegada. 1100 00:41:42,840 --> 00:41:46,170 >> Així veuràs això visualment, però això és el que ens espera la setmana que ve. 1101 00:41:46,170 --> 00:41:49,760 I, en general, quan pensem en un petit mica més difícil de qualsevol problema. 1102 00:41:49,760 --> 00:41:52,435 1103 00:41:52,435 --> 00:41:57,970 Tenim n al quadrat de l'esquerra, n quadrat al mig, i n 1104 00:41:57,970 --> 00:41:59,400 log n a la dreta. 1105 00:41:59,400 --> 00:42:00,590 Així que el seu melodrama real. 1106 00:42:00,590 --> 00:42:02,040 Ens veiem el dilluns. 1107 00:42:02,040 --> 00:42:05,163 >> [Aplaudiments]