1 00:00:00,000 --> 00:00:11,270 2 00:00:11,270 --> 00:00:14,910 >> ALTAVEU: Molt bé, això és CS50. 3 00:00:14,910 --> 00:00:19,020 Aquest és el final de la tercera setmana, i si no ha pres avantatge ja, 4 00:00:19,020 --> 00:00:21,790 saben que hi haurà dinar aquest divendres, com de costum, on 5 00:00:21,790 --> 00:00:25,430 es pot gaudir d'una bona conversa i el menjar en Fire and Ice 6 00:00:25,430 --> 00:00:27,980 amb alguns CS50 d' el personal i els companys de classe. 7 00:00:27,980 --> 00:00:30,170 Dirigeix-te a aquest URL aquí. 8 00:00:30,170 --> 00:00:33,420 >> Ara vostè pot recordar, o vostè aviat pot estar familiaritzat amb, 9 00:00:33,420 --> 00:00:35,970 aquestes coses aquí, que es donen al final 10 00:00:35,970 --> 00:00:37,850 del semestre per a moltes classes. 11 00:00:37,850 --> 00:00:40,870 Llibres blaus L'anomenat examen, en el qual vostè escriu les seves respostes als exàmens. 12 00:00:40,870 --> 00:00:44,240 Ara tinc aquí 26 de tal llibres blaus, sobre cadascun d'ells 13 00:00:44,240 --> 00:00:47,580 s'escriu un nom, de l'A a la Z. I de fet, els noms són tan simples, A 14 00:00:47,580 --> 00:00:50,490 a la Z. I un els objectius a la mà avui 15 00:00:50,490 --> 00:00:53,910 serà la de continuar el comencem el dilluns, el que no és 16 00:00:53,910 --> 00:00:57,830 tant mirar el codi, però en realitat mirant idees i la resolució de problemes. 17 00:00:57,830 --> 00:01:00,170 Una de les metes i promeses d'aquest curs 18 00:01:00,170 --> 00:01:02,985 és que li ensenyi a pensar més amb cura, més metòdicament, 19 00:01:02,985 --> 00:01:05,400 i per resoldre problemes de manera més eficient. 20 00:01:05,400 --> 00:01:09,526 I, de fet, podem fer que realment sense si més no tocar una línia de codi. 21 00:01:09,526 --> 00:01:12,150 Així que tinc un parell d'elefants fins avui, taronja i blau, 22 00:01:12,150 --> 00:01:15,780 si poguéssim aconseguir un voluntari, potser des de més enrere del que és habitual. 23 00:01:15,780 --> 00:01:18,070 Què hi ha aquí, anem cap avall. 24 00:01:18,070 --> 00:01:24,180 L'objectiu de la qual serà a ajudar a més administrar aquest examen aquí. 25 00:01:24,180 --> 00:01:24,935 Quin és el teu nom? 26 00:01:24,935 --> 00:01:25,768 >> AUDIÈNCIA: Mary Beth. 27 00:01:25,768 --> 00:01:27,560 ALTAVEU: Mary Beth, anem a dalt. 28 00:01:27,560 --> 00:01:29,560 A veure si el micròfon aquí per a vostè. 29 00:01:29,560 --> 00:01:32,172 30 00:01:32,172 --> 00:01:32,880 Encantada de conèixer-te. 31 00:01:32,880 --> 00:01:34,005 >> AUDIÈNCIA: Molt gust. 32 00:01:34,005 --> 00:01:36,790 ALTAVEU: Molt bé, així que tinc aquí els llibres blaus de l'A a la Z, 33 00:01:36,790 --> 00:01:41,680 i jo vaig a pretendre que Tinc un dels estudiants, 34 00:01:41,680 --> 00:01:45,770 i que vindran en un tant a l'atzar al final d'un bloc d'examen de tres hores 35 00:01:45,770 --> 00:01:49,400 pel que estan acabant d'alguna Per semi-aleatori com aquest. 36 00:01:49,400 --> 00:01:54,510 Ara el seu treball en un moment va a ser-- això és en realitat la forma en que obtenen 37 00:01:54,510 --> 00:01:56,820 convertit en al final d' la classe, més probable. 38 00:01:56,820 --> 00:02:01,120 El seu treball ara serà, bastant simplement, per ordenar aquests llibres blaus per a nosaltres 39 00:02:01,120 --> 00:02:05,220 de l'A a la Z. 40 00:02:05,220 --> 00:02:08,400 >> AUDIÈNCIA: Oh, això és tindrà per sempre. 41 00:02:08,400 --> 00:02:13,747 >> ALTAVEU: I veurem en fer això, no hi ha pressió. 42 00:02:13,747 --> 00:02:15,330 AUDIÈNCIA: No, no hi ha pressió ni res. 43 00:02:15,330 --> 00:02:19,230 44 00:02:19,230 --> 00:02:23,570 >> ALTAVEU: I per a la diversió, posarem un temporitzador. 45 00:02:23,570 --> 00:02:26,680 46 00:02:26,680 --> 00:02:28,700 >> AUDIÈNCIA: Molt divertit, molt divertit. 47 00:02:28,700 --> 00:02:36,741 48 00:02:36,741 --> 00:02:38,574 >> ALTAVEU: Puc sostenir el micròfon per a vostè. 49 00:02:38,574 --> 00:02:40,240 Molt bé, acabem duplicar la nostra velocitat. 50 00:02:40,240 --> 00:02:44,190 51 00:02:44,190 --> 00:02:49,060 Així que mentre tant, permetin-me plantejar el que és serà la pregunta per Mary Beth 52 00:02:49,060 --> 00:02:51,540 és el que està fent, com és ella va sobre solucionar això? 53 00:02:51,540 --> 00:02:54,040 I, de fet, pot ser que no tingui Ha pensat alguna vegada sobre alguna cosa 54 00:02:54,040 --> 00:02:57,440 tan simple com quan vostè tria fins a 26 llibres com aquest, 55 00:02:57,440 --> 00:02:59,350 que no tenen un producte natural ordenant a ells. 56 00:02:59,350 --> 00:03:01,335 Quin és el procés de que en realitat s'utilitza? 57 00:03:01,335 --> 00:03:03,770 És bastant aleatori només escollir el primer que es veu 58 00:03:03,770 --> 00:03:05,250 i posar-lo en el seu lloc? 59 00:03:05,250 --> 00:03:09,680 És primera vegada que mou les seves mans al voltant de a la recerca d'una continuació a la recerca de B? 60 00:03:09,680 --> 00:03:11,722 És vostè fes un cop d'ull a una parell al costat de l'altre 61 00:03:11,722 --> 00:03:14,680 i dir, espera un minut, aquest no està bé, i després intercanviar l'ordre? 62 00:03:14,680 --> 00:03:16,960 Vam veure ja el dilluns que hi ha un nombre de maneres 63 00:03:16,960 --> 00:03:22,140 en el qual podem fer això, i de fet, com ens acostem al final aquí, 64 00:03:22,140 --> 00:03:26,360 Jo prendria nota potser del que Mary Beth està fent. 65 00:03:26,360 --> 00:03:30,040 Tenim uns munts que sembla, un un més gran, tres més petites. 66 00:03:30,040 --> 00:03:33,790 67 00:03:33,790 --> 00:03:36,415 >> AUDIÈNCIA: jo els estic ordenant quan em trobo amb dues cartes 68 00:03:36,415 --> 00:03:39,540 que sé que estan junts en una seqüència, Els poso junts perquè no ho faig 69 00:03:39,540 --> 00:03:42,915 haver de preocupar de mantenir pista de tota una fila de llibres. 70 00:03:42,915 --> 00:03:45,706 És només que, oh, A és primer, Tinc aquesta pila aquí. 71 00:03:45,706 --> 00:03:47,580 ALTAVEU: Llavors, gairebé com peces d'un trencaclosques que 72 00:03:47,580 --> 00:03:49,860 tenir la forma dret a coincidir entre si. 73 00:03:49,860 --> 00:03:51,026 AUDIÈNCIA: Més o menys, sí. 74 00:03:51,026 --> 00:03:55,320 ALTAVEU: OK, excel.lent. 75 00:03:55,320 --> 00:03:59,850 I ara cada un d'aquests piles s'ordenen presumiblement? 76 00:03:59,850 --> 00:04:00,990 >> AUDIÈNCIA: Si. 77 00:04:00,990 --> 00:04:09,900 >> ALTAVEU: Molt bé, de l'A a la Z. Tots bé, felicitats, ho van fer. 78 00:04:09,900 --> 00:04:11,461 Vostè té la seva opció. 79 00:04:11,461 --> 00:04:11,960 Blau? 80 00:04:11,960 --> 00:04:13,530 Molt bé, gràcies per això. 81 00:04:13,530 --> 00:04:16,679 Així que Mary Beth es proposava el que el seu enfocament era, 82 00:04:16,679 --> 00:04:19,720 però el que és un altre enfocament de com podria anar sobre classificació d'aquestes coses? 83 00:04:19,720 --> 00:04:21,130 Què hauria fet vostè? 84 00:04:21,130 --> 00:04:24,060 El rècord a batre hauria estat un minut i 50 segons més o menys, 85 00:04:24,060 --> 00:04:26,039 a més dels que més em vaig oblidar d'explicar. 86 00:04:26,039 --> 00:04:27,080 Què hauria fet vostè? 87 00:04:27,080 --> 00:04:27,579 Sí? 88 00:04:27,579 --> 00:04:28,735 AUDIÈNCIA: Prengui la pila. 89 00:04:28,735 --> 00:04:29,776 Comenceu des del principi. 90 00:04:29,776 --> 00:04:32,284 Reviseu els seus papers. 91 00:04:32,284 --> 00:04:36,586 I si el superior és més gran que, tal vegada, que són, 92 00:04:36,586 --> 00:04:38,980 l'inferior és més alt, llavors canviï'ls. 93 00:04:38,980 --> 00:04:41,300 >> ALTAVEU: OK, així que començar a la part superior i la part inferior, 94 00:04:41,300 --> 00:04:43,716 i després la seva forma de treball cap a l'interior d'aquesta manera, el canvi d'ells? 95 00:04:43,716 --> 00:04:46,580 OK, així que una mica semblant en esperit l'ordenament de bombolla, 96 00:04:46,580 --> 00:04:49,160 però l'elecció dels extrems no els parells adjacents. 97 00:04:49,160 --> 00:04:52,080 No obstant això, el curt d'ell és que no sens dubte un munt de diferents maneres 98 00:04:52,080 --> 00:04:54,210 podríem fer això, i Francament, jo crec que tipus de 99 00:04:54,210 --> 00:04:55,700 adoptat un parell d'aproximacions, oi? 100 00:04:55,700 --> 00:05:00,567 Vostè ha fet una mena de quatre munts ordenats, i després fusionat amb eficàcia. 101 00:05:00,567 --> 00:05:02,650 I això és, diria, una altra tècnica per complet. 102 00:05:02,650 --> 00:05:06,950 No ho tracta com una gran pila, que s'hagi dividit el problema en quatre quads, 103 00:05:06,950 --> 00:05:09,820 si es vol, i llavors d'alguna manera les va fusionar al final. 104 00:05:09,820 --> 00:05:13,410 >> Així que anem a considerar, en última instància, com més podem fer això. 105 00:05:13,410 --> 00:05:15,860 Formalitzem la noció d'ordenament de bombolla última vegada, 106 00:05:15,860 --> 00:05:18,780 i ordenament de bombolla revocatori era una algorisme que visualitzem 107 00:05:18,780 --> 00:05:22,640 amb vuit dels seus companys de classe fins aquí, aparentment ordenats a l'atzar al principi. 108 00:05:22,640 --> 00:05:26,110 I llavors vam decidir per parelles, si dos elements estan fora de servei, 109 00:05:26,110 --> 00:05:26,950 simplement intercanviar. 110 00:05:26,950 --> 00:05:28,930 Així quatre i dos són evident la seva total improcedència, 111 00:05:28,930 --> 00:05:31,080 per la qual cosa aquests dos companys de classe i va canviar de posició. 112 00:05:31,080 --> 00:05:35,390 I després repetim amb quatre-sis, a continuació, sis-vuit, en cada iteració, 113 00:05:35,390 --> 00:05:36,980 movent-se cap a la dreta. 114 00:05:36,980 --> 00:05:42,590 >> Així que donat a vuit persones, quantes parelles comparacions Què vaig fer mentre caminava des 115 00:05:42,590 --> 00:05:45,220 esquerra a dreta en un d'aquests iteració? 116 00:05:45,220 --> 00:05:48,410 Quantes comparacions? 117 00:05:48,410 --> 00:05:49,197 Set, oi? 118 00:05:49,197 --> 00:05:51,405 Perquè si hi ha vuit persones, però que tenen la parella 119 00:05:51,405 --> 00:05:53,880 ells i que es mantenen en moviment un salt a la dreta, 120 00:05:53,880 --> 00:05:56,060 no va a tenir vuit comparacions perquè no es pot comparar 121 00:05:56,060 --> 00:05:59,226 un element contra si mateixa, o que ho faria només inútil, pel que té set. 122 00:05:59,226 --> 00:06:01,290 O, més generalment, si tenim n persones, que 123 00:06:01,290 --> 00:06:04,300 fer N almenys 1 comparacions amb ordenament de bombolla. 124 00:06:04,300 --> 00:06:08,150 >> Així que anem a considerar ara el bo o mal ordenament de bombolla en realitat era, i tractar 125 00:06:08,150 --> 00:06:13,570 per donar-nos vocabulari amb que als algoritmes de crítica com aquesta, 126 00:06:13,570 --> 00:06:14,430 i aviat el nostre propi. 127 00:06:14,430 --> 00:06:16,970 Així que el primer pas a través ordenament de bombolla, la primera vegada 128 00:06:16,970 --> 00:06:20,909 Vaig caminar d'esquerra a dreta a la etapa, em n almenys 1 comparacions prendre. 129 00:06:20,909 --> 00:06:22,950 I això serà la meva unitat de mesura, no? 130 00:06:22,950 --> 00:06:26,170 Jo estava una mica parlant i passejant, alguna cosa ràpid, una mica lent, 131 00:06:26,170 --> 00:06:29,300 així que comptant el meu número de segons no està particularment revelador, 132 00:06:29,300 --> 00:06:32,260 però comptant el nombre de operacions que vaig fer el dilluns, 133 00:06:32,260 --> 00:06:35,900 la comparació de dues persones, que se sent com una bona unitat de mesura. 134 00:06:35,900 --> 00:06:40,980 >> Així n almenys 1 passos la primera vegada, però llavors, ¿què va passar després? 135 00:06:40,980 --> 00:06:46,610 Quina és l'avantatge d'una sola passada a través d'una llista d'una altra manera sense classificar? 136 00:06:46,610 --> 00:06:49,840 Què pots dir-me sobre l'element que va ser tot el camí per allà? 137 00:06:49,840 --> 00:06:51,300 Sí? 138 00:06:51,300 --> 00:06:52,870 Aquest va ser l'element més important, oi? 139 00:06:52,870 --> 00:06:55,710 El número vuit, tot i que començat aquí, cada vegada que 140 00:06:55,710 --> 00:06:57,860 seva comparació contra un veí, va mantenir 141 00:06:57,860 --> 00:07:00,480 bombollejant cap a la dreta costat de la llista. 142 00:07:00,480 --> 00:07:02,710 I, en efecte, que és on l'algorisme obté el seu nom. 143 00:07:02,710 --> 00:07:07,630 >> Ara per aquesta lògica, el nombre de comparacions Necessito que faig en el segon temps 144 00:07:07,630 --> 00:07:09,800 Faig que passi d'esquerra a dreta? 145 00:07:09,800 --> 00:07:10,730 n menys 2, oi? 146 00:07:10,730 --> 00:07:14,297 Seria simplement estar desaprofitant meu temps si mantenir comparant vuit en contra d'algú 147 00:07:14,297 --> 00:07:16,630 més perquè ja sabem ella era al lloc correcte. 148 00:07:16,630 --> 00:07:19,760 Així que això és una mica d'una optimització, de manera que el següent pas 149 00:07:19,760 --> 00:07:23,899 serà més n menys dos passos, on n és el nombre de persones. 150 00:07:23,899 --> 00:07:26,940 Ara vostè pot tipus d'extrapolar, fins i tot si no ets un expert en informàtica, 151 00:07:26,940 --> 00:07:27,680 com això acaba. 152 00:07:27,680 --> 00:07:31,259 Al final d'aquest algorisme, presumiblement vostè té només una comparació esquerra. 153 00:07:31,259 --> 00:07:33,800 Vostè ha de fixar el tipus de a partir de la llista en cas que dos 154 00:07:33,800 --> 00:07:36,540 i un són fora de servei i ha de ser un i dos, 155 00:07:36,540 --> 00:07:40,330 pel que aquest toqui fons en més 1 comparació final. 156 00:07:40,330 --> 00:07:44,500 >> Ara el punt, punt, punt tipus d'ones és mans d'alguns dels detalls més sucosos, 157 00:07:44,500 --> 00:07:46,452 però seguirem endavant i simplificar. 158 00:07:46,452 --> 00:07:48,660 Si vostè recorda d'alta escola, francament, molts de vostès 159 00:07:48,660 --> 00:07:50,340 tingut llibres de matemàtiques que tenien un full de trucs poc 160 00:07:50,340 --> 00:07:52,550 a la portada o la contraportada que mostrava 161 00:07:52,550 --> 00:07:56,400 sumes això de la sèrie com aquesta última instància, va afegir fent. 162 00:07:56,400 --> 00:07:59,600 En el cas general, si té un variable com la n, i de fet aquest, 163 00:07:59,600 --> 00:08:01,634 si un mira al seu llibre de matemàtiques de la vella escola, 164 00:08:01,634 --> 00:08:04,050 veuries que aquesta realitat se suma a aquesta suma aquí, 165 00:08:04,050 --> 00:08:07,970 n vegades n almenys 1 tot dividit per 2. 166 00:08:07,970 --> 00:08:11,172 Així que per ara permeteu-me estipulo això és cert, pel que en un acte de fe, 167 00:08:11,172 --> 00:08:12,880 això és el que això resumeix fins, i vam poder 168 00:08:12,880 --> 00:08:14,341 demostrar que en un cas més general. 169 00:08:14,341 --> 00:08:15,590 Però ara anem a ampliar això. 170 00:08:15,590 --> 00:08:19,920 Així que anem a multiplicar això, així que això és n al quadrat, menys n, tot dividit per 2. 171 00:08:19,920 --> 00:08:23,200 Això és realment n al quadrat, dividit per 2, menys n sobre 2, 172 00:08:23,200 --> 00:08:25,010 així que això és tot el agradable i interessant. 173 00:08:25,010 --> 00:08:27,060 Però, què passa si ens ara plug-in d'un valor? 174 00:08:27,060 --> 00:08:29,724 Suposem que jo no tenia vuit persones, però diuen que un milió. 175 00:08:29,724 --> 00:08:31,890 I un milió només perquè que és un nombre bastant gran, 176 00:08:31,890 --> 00:08:34,039 anem a connectar que en i veure què passa. 177 00:08:34,039 --> 00:08:39,039 Així que si connecto un milió en aquesta fórmula Vaig a aconseguir un milió de quadrat, 178 00:08:39,039 --> 00:08:42,868 dividit per 2, almenys una milions, dividit entre 2. 179 00:08:42,868 --> 00:08:44,159 Ara ¿què és això serà igual? 180 00:08:44,159 --> 00:08:47,354 Així quals 500 mil milions, menys de 500.000. 181 00:08:47,354 --> 00:08:49,270 I si faig realment que les matemàtiques, vol dir que 182 00:08:49,270 --> 00:08:53,920 que la classificació d'un milió de les persones amb l'ordenament de bombolla 183 00:08:53,920 --> 00:09:01,800 em podria prendre 499999500000 passos o comparacions en el final, 184 00:09:01,800 --> 00:09:02,900 només estem extrapolant. 185 00:09:02,900 --> 00:09:06,860 >> Això se sent bastant lent, però, francament, mesurament d'una entrada particular, 186 00:09:06,860 --> 00:09:09,160 així, no és tot el que eloqüent. 187 00:09:09,160 --> 00:09:14,050 Però de fet, sí suggereix que a mesura que n es fa més gran i més gran, aquest algorisme 188 00:09:14,050 --> 00:09:16,280 tipus de se sent pitjor i pitjor, o que realment 189 00:09:16,280 --> 00:09:20,450 començar a sentir el dolor d'aquesta exponenciació, que n al quadrat, 190 00:09:20,450 --> 00:09:21,770 que afegeix bastant ràpid. 191 00:09:21,770 --> 00:09:25,340 I aquest detall no és perdut en les persones, de fet, 192 00:09:25,340 --> 00:09:29,640 Fa alguns anys un cert senador que era campanya, es va asseure per a una entrevista 193 00:09:29,640 --> 00:09:32,180 amb Eric de Google Schmidt, CEO de l'època, 194 00:09:32,180 --> 00:09:36,380 i va ser posada en dubte amb una pregunta igual que estem explorant avui. 195 00:09:36,380 --> 00:09:38,468 Anem a fer una ullada. 196 00:09:38,468 --> 00:09:45,280 >> [REPRODUCCIÓ DE VÍDEO] 197 00:09:45,280 --> 00:09:48,560 >> -Senador, Ets aquí a Google, i m'agrada 198 00:09:48,560 --> 00:09:53,382 pensar en la presidència com una entrevista de treball. 199 00:09:53,382 --> 00:09:56,434 Ara, és difícil aconseguir un treball com a president, 200 00:09:56,434 --> 00:09:58,100 i vostè va a través dels rigors ara. 201 00:09:58,100 --> 00:10:01,860 També és difícil d'aconseguir una feina a Google. 202 00:10:01,860 --> 00:10:05,490 Tenim preguntes, i ens demanar a les nostres preguntes dels candidats, 203 00:10:05,490 --> 00:10:09,770 i aquest és de Larry Schwimmer. 204 00:10:09,770 --> 00:10:14,760 Què-- que vostès pensen que sóc és broma, està just aquí. 205 00:10:14,760 --> 00:10:17,930 Quina és la forma més eficient de ordenar un milió d'enters de 32 bits? 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 >> -Ho Sento, tal vegada-- 209 00:10:25,200 --> 00:10:27,400 >> No, no, no. 210 00:10:27,400 --> 00:10:30,700 Crec que l'ordenament de bombolla seria el camí equivocat. 211 00:10:30,700 --> 00:10:34,165 212 00:10:34,165 --> 00:10:38,180 >> Anem, que li va dir això? 213 00:10:38,180 --> 00:10:40,590 No vaig veure ordinador la ciència en el seu fons. 214 00:10:40,590 --> 00:10:42,130 >> -Tenim Nostres espies en allà. 215 00:10:42,130 --> 00:10:44,930 216 00:10:44,930 --> 00:10:48,444 >> -ok, Anem a demanar una diferent pregunta de l'entrevista. 217 00:10:48,444 --> 00:10:49,300 >> [FI REPRODUCCIÓ DE VÍDEO] 218 00:10:49,300 --> 00:10:52,290 >> ALTAVEU: Així que parlant de nombres específics tot i que, 219 00:10:52,290 --> 00:10:53,890 no serà tan útil. 220 00:10:53,890 --> 00:10:56,810 No és una lliçó de vida que la bombolla espècie, donat un milió d'entrades, 221 00:10:56,810 --> 00:10:58,590 podria prendre fins a 500.000.000.000 passos. 222 00:10:58,590 --> 00:11:01,120 Realment no es pot generalitzar massa eficaçment a partir d'aquest 223 00:11:01,120 --> 00:11:03,560 i prendre bones decisions de disseny en escriure programes. 224 00:11:03,560 --> 00:11:07,070 Així que anem a centrar-nos encara sobre com podem simplificar aquest resultat. 225 00:11:07,070 --> 00:11:11,780 >> Així que he ressaltat en groc aquí el resultat de n al quadrat dividida per 2, 226 00:11:11,780 --> 00:11:14,330 per la qual cosa 1.000.000 quadrat dividit per 2, i després 227 00:11:14,330 --> 00:11:16,710 He destacat el la resposta final va ser 228 00:11:16,710 --> 00:11:20,180 una vegada que restem off n dividit per 2. 229 00:11:20,180 --> 00:11:24,850 I l'afirmació que faré ara és, qui diables li importa si es resta de 230 00:11:24,850 --> 00:11:30,060 una mica més de 2 n edat quan la primera part d'aquesta fórmula és molt més gran? 231 00:11:30,060 --> 00:11:33,910 Domina l'altre termini, n al quadrat dividit per 2 232 00:11:33,910 --> 00:11:37,510 és molt més gran, amb claredat, com n es fa gran com un milió, 233 00:11:37,510 --> 00:11:41,450 això és realment una gran diferència en al final de la dia entre 500.000.000.000 234 00:11:41,450 --> 00:11:45,730 i 499.999.500.000? 235 00:11:45,730 --> 00:11:46,349 En realitat no. 236 00:11:46,349 --> 00:11:48,640 I així ho anem a fer com científics de la computació és 237 00:11:48,640 --> 00:11:53,270 ignorar els termes d'ordre inferior i prendre alguna cosa com això i realment 238 00:11:53,270 --> 00:11:56,050 només simplificar l' terme que es va a importar. 239 00:11:56,050 --> 00:12:00,315 Els més grans de les nostres conjunts de dades aconsegueixen, més gran les nostres bases de dades reben, més pàgines web 240 00:12:00,315 --> 00:12:02,690 hem de buscar, més amics que tenen a Facebook. 241 00:12:02,690 --> 00:12:07,340 >> Com n es fa més gran, estem molt va a preocupar-se pel més gran 242 00:12:07,340 --> 00:12:11,560 termini en qualsevol tipus d'anàlisi de nostre acompliment algoritmes. 243 00:12:11,560 --> 00:12:16,230 I jo vaig a dir, saps què, ordenament de bombolla està en l'ordre de la gran O, 244 00:12:16,230 --> 00:12:18,060 de l'ordre de n al quadrat. 245 00:12:18,060 --> 00:12:20,090 No és exactament n al quadrat, com hem vist, 246 00:12:20,090 --> 00:12:22,060 però a qui li importa sobre els terminis més petits, 247 00:12:22,060 --> 00:12:24,390 i, francament, que realment li importa si dividim per 2? 248 00:12:24,390 --> 00:12:25,870 Això és només un factor constant. 249 00:12:25,870 --> 00:12:29,480 I és de 500 mil milions contra 250 milions realment tan gran d'un acord? 250 00:12:29,480 --> 00:12:32,190 Jo només podia esperar un any, deixar que el meu portàtil literalment 251 00:12:32,190 --> 00:12:34,810 obtenir el doble de ràpid en el maquinari, i aquest tipus de diferència 252 00:12:34,810 --> 00:12:36,650 simplement desapareix de forma natural amb el temps. 253 00:12:36,650 --> 00:12:39,300 >> El que ens importa és l'expressió, la part 254 00:12:39,300 --> 00:12:42,489 de l'expressió que variarà com la nostra entrada es fa més gran i més gran. 255 00:12:42,489 --> 00:12:45,280 I de fet, en el món real, això és el que està passant cada vegada més 256 00:12:45,280 --> 00:12:48,330 és les entrades als nostres problemes i algoritmes són cada vegada més gran. 257 00:12:48,330 --> 00:12:53,470 Tan gran O serà la notació, la notació asimptòtica, que acabem de 258 00:12:53,470 --> 00:12:57,160 utilitzar com a científics de la computació per descriure el rendiment, o el temps d'execució, 259 00:12:57,160 --> 00:12:58,130 d'un algorisme. 260 00:12:58,130 --> 00:13:00,800 Així que podem comparar algorismes en equips diferents escrits 261 00:13:00,800 --> 00:13:04,170 per diferents persones, utilitzant alguna mètrica fonamentalment similar 262 00:13:04,170 --> 00:13:07,557 com el nombre de comparacions que ets fer, o potser el nombre de swaps 263 00:13:07,557 --> 00:13:08,140 vostè està fent. 264 00:13:08,140 --> 00:13:11,910 >> El que no anem a recompte és la quantitat de temps 265 00:13:11,910 --> 00:13:13,981 que passa al rellotge a la paret normalment. 266 00:13:13,981 --> 00:13:16,230 El que no anem a preocupar sobre és la quantitat de memòria 267 00:13:16,230 --> 00:13:17,820 està utilitzant avui menys, encara que això és 268 00:13:17,820 --> 00:13:19,370 altre recurs que podríem mesurar. 269 00:13:19,370 --> 00:13:23,610 Anem a tractar de basar la nostra anàlisi només en les operacions bàsiques, els que, 270 00:13:23,610 --> 00:13:25,930 francament, que es pot veure més visualment. 271 00:13:25,930 --> 00:13:30,700 Així que amb una mena de gran O de n quadrat, afirmo que O de n al quadrat 272 00:13:30,700 --> 00:13:35,820 és un límit superior en l'anomenada moment de la bombolla de tipus corrent. 273 00:13:35,820 --> 00:13:38,820 En altres paraules, si vostè volia dir que hi ha 274 00:13:38,820 --> 00:13:41,370 aquest límit superior de la quantitat de els passos d'un algorisme pot prendre, 275 00:13:41,370 --> 00:13:46,240 que estarà en el gran O de n quadrat en aquest cas, un límit superior. 276 00:13:46,240 --> 00:13:49,710 >> Què passa si en comptes canvi el història sigui no es tracta d'una espècie de bombolla, 277 00:13:49,710 --> 00:13:50,910 però aquest límit superior. 278 00:13:50,910 --> 00:13:54,030 Pots pensar en un algoritme que hem vist en ia 279 00:13:54,030 --> 00:13:59,530 el límit superior, màxim mesurar el temps o les operacions, 280 00:13:59,530 --> 00:14:04,300 es diu que està fitada per n, una funció lineal, 281 00:14:04,300 --> 00:14:07,260 no una quadràtica que és corb? 282 00:14:07,260 --> 00:14:10,780 Què és un algorisme que Sempre presa no més 283 00:14:10,780 --> 00:14:12,860 que com n passos, o Passos 2n, 3n o passos? 284 00:14:12,860 --> 00:14:13,360 Sí? 285 00:14:13,360 --> 00:14:15,030 >> AUDIÈNCIA: Trobar el major nombre en una llista? 286 00:14:15,030 --> 00:14:16,930 >> ALTAVEU: Perfect, la recerca de el major nombre en una llista. 287 00:14:16,930 --> 00:14:18,940 Si em donen una llista de persones, per exemple, 288 00:14:18,940 --> 00:14:21,440 cada un que és la celebració d'una sèrie, ¿Quin és el nombre màxim 289 00:14:21,440 --> 00:14:23,770 de mesures que hauria portar, una persona raonablement intel · ligent, 290 00:14:23,770 --> 00:14:27,530 trobar la persona més gran en aquesta llista? 291 00:14:27,530 --> 00:14:28,100 n, oi? 292 00:14:28,100 --> 00:14:31,320 Com que en el pitjor dels casos, on podria ser el major valor? 293 00:14:31,320 --> 00:14:32,700 És cert, tot el camí al final. 294 00:14:32,700 --> 00:14:34,575 Així que en el pitjor dels casos límit superior, que podria 295 00:14:34,575 --> 00:14:36,450 haver d'anar tot el camí aquí i ser com, 296 00:14:36,450 --> 00:14:39,170 oh, aquí hi ha el número vuit, o el que sigui que el valor és. 297 00:14:39,170 --> 00:14:41,330 Ara només seria estúpid si ho seguia fent, oi? 298 00:14:41,330 --> 00:14:43,840 Estàs buscant més i més elements si l'últim d'ells és d'allà? 299 00:14:43,840 --> 00:14:45,340 Així que sens dubte, n és un límit superior. 300 00:14:45,340 --> 00:14:47,420 Jo no necessito prendre més passos que això. 301 00:14:47,420 --> 00:14:51,580 >> Llavors, què si en comptes vaig proposar que existeixen algorismes en aquest món que 302 00:14:51,580 --> 00:14:57,750 tenen un temps d'execució que és delimitada per gran O de log n, log n? 303 00:14:57,750 --> 00:15:00,390 On hem vist això abans? 304 00:15:00,390 --> 00:15:00,890 Sí? 305 00:15:00,890 --> 00:15:03,309 >> AUDIÈNCIA: Al problema de guia telefònica? 306 00:15:03,309 --> 00:15:04,850 ALTAVEU: Igual que el problema de la guia telefònica. 307 00:15:04,850 --> 00:15:07,754 Quina va ser la mesura de la molt temps o quantes llàgrimes de TI 308 00:15:07,754 --> 00:15:10,170 em va portar a trobar algú com Mike Smith a la guia telefònica? 309 00:15:10,170 --> 00:15:13,212 Ens deia que era log n, i fins i tot si desconegut o que és 310 00:15:13,212 --> 00:15:15,170 una mica nebulosa què logaritme o exponent va ser, 311 00:15:15,170 --> 00:15:17,650 només recorda que log n generalment es refereix al procés, 312 00:15:17,650 --> 00:15:20,790 en aquest cas, de dividir alguna cosa a la meitat una altra vegada, i una altra, 313 00:15:20,790 --> 00:15:25,790 i una altra, i una altra, de manera que obté cada vegada més petita a mesura que fa això. 314 00:15:25,790 --> 00:15:28,470 >> Així que ingressi de n es refereix, és clar, l'exemple de guia telefònica, 315 00:15:28,470 --> 00:15:32,662 per a recerca binària en teoria, quan tenia les portes virtuals en el tauler, 316 00:15:32,662 --> 00:15:34,370 o quan Siguin era buscant alguna cosa. 317 00:15:34,370 --> 00:15:37,374 Si s'hagués utilitzat de recerca binària, log n seria el límit superior de la quantitat 318 00:15:37,374 --> 00:15:38,040 temps que pren. 319 00:15:38,040 --> 00:15:44,027 Però aquests algoritmes que corrien a log n assumit el detall clau? 320 00:15:44,027 --> 00:15:45,360 Que la llista es va solucionar, oi? 321 00:15:45,360 --> 00:15:47,789 El seu algorisme és dolent si seva entrada no està ordenada, 322 00:15:47,789 --> 00:15:49,830 i no obstant això està utilitzant una mena de recerca binària 323 00:15:49,830 --> 00:15:51,704 ja que podria saltar dret sobre l'element 324 00:15:51,704 --> 00:15:53,600 sense adonar-se que és de fet allà. 325 00:15:53,600 --> 00:15:55,600 >> Ara, què podria significar això, gran O d'un? 326 00:15:55,600 --> 00:15:59,117 Això no vol dir que el seu algorisme té una i només una etapa, 327 00:15:59,117 --> 00:16:01,200 només significa que es necessita un nombre constant de passos. 328 00:16:01,200 --> 00:16:04,060 Potser sigui 1, potser és 10, potser és 1000, 329 00:16:04,060 --> 00:16:07,750 però és independent de la mida del problema. 330 00:16:07,750 --> 00:16:10,850 No importa què tan gran és n, un algorisme de constant de temps 331 00:16:10,850 --> 00:16:12,747 sempre té el mateix nombre de passos. 332 00:16:12,747 --> 00:16:15,080 Llavors, què podria ser un algorisme hem parlat o simplement 333 00:16:15,080 --> 00:16:20,418 intuïtivament que ve a vostè que sempre s'executa en l'anomenada constant de temps? 334 00:16:20,418 --> 00:16:20,918 Sí? 335 00:16:20,918 --> 00:16:22,001 >> AUDIÈNCIA: Afegeix dos nombres. 336 00:16:22,001 --> 00:16:25,320 ALTAVEU: Afegeix dos nombres, 2 més 2 és igual a 4, fet. 337 00:16:25,320 --> 00:16:27,227 Així que podria funcionar, què més? 338 00:16:27,227 --> 00:16:28,560 Què tal món més real, no? 339 00:16:28,560 --> 00:16:30,686 >> AUDIÈNCIA: Trobar el a primera hora de la llista. 340 00:16:30,686 --> 00:16:32,810 ALTAVEU: Trobar a la primera element en una llista, segur. 341 00:16:32,810 --> 00:16:34,540 En realitat hem estat parlant sobre les matrius ja, 342 00:16:34,540 --> 00:16:36,540 Com s'arriba a la primer element d'una matriu, 343 00:16:36,540 --> 00:16:40,465 no importa quant de temps la array és en codi C? 344 00:16:40,465 --> 00:16:43,090 Vostè només ha d'utilitzar com el suport notació zero, bam, ets allà. 345 00:16:43,090 --> 00:16:46,120 I de fet, matrius, com un part, suport cosa generalment conegut 346 00:16:46,120 --> 00:16:49,240 com accés aleatori, d'accés aleatori memòria, perquè vostè pot literalment 347 00:16:49,240 --> 00:16:50,284 saltar a qualsevol lloc. 348 00:16:50,284 --> 00:16:52,700 Podem fer això encara més simple podem rebobinar fins a la setmana zero 349 00:16:52,700 --> 00:16:53,900 quan vam fer les ratllades. 350 00:16:53,900 --> 00:16:59,707 Quant de temps es necessita perquè la diuen bloc en Scratch per executar? 351 00:16:59,707 --> 00:17:00,790 Només la constant de temps, oi? 352 00:17:00,790 --> 00:17:03,960 Parla, di alguna cosa, no importa 353 00:17:03,960 --> 00:17:07,359 com grans rascades món és, sempre és va a prendre la mateixa quantitat de temps 354 00:17:07,359 --> 00:17:08,490 dir simplement alguna cosa. 355 00:17:08,490 --> 00:17:11,089 >> Així que aquesta és la constant de temps, però quina és l'altra cara? 356 00:17:11,089 --> 00:17:13,030 Si això era superior límits, el que si volem 357 00:17:13,030 --> 00:17:17,089 per descriure els límits inferiors dels nostres algorismes de temps d'execució? 358 00:17:17,089 --> 00:17:19,852 Gairebé un millor cas potencialment, si es vol, 359 00:17:19,852 --> 00:17:23,060 encara que aquests termes poden aplicar-se a millor casos, els pitjors casos, els casos mitjana més 360 00:17:23,060 --> 00:17:26,359 en general, però ens concentrarem en cotes inferiors en termes més generals. 361 00:17:26,359 --> 00:17:31,920 Què és un algorisme que té una cota inferior de n passos, 362 00:17:31,920 --> 00:17:33,350 o passos 2n, 3n o passos? 363 00:17:33,350 --> 00:17:36,241 Alguns factor de n passos, aquest és el seu límit inferior. 364 00:17:36,241 --> 00:17:36,740 Sí? 365 00:17:36,740 --> 00:17:37,910 >> AUDIÈNCIA: ordenament de bombolla? 366 00:17:37,910 --> 00:17:41,610 >> ALTAVEU: ordenament de bombolla presa que mínimament n passos, per què? 367 00:17:41,610 --> 00:17:42,279 Perquè és això? 368 00:17:42,279 --> 00:17:45,320 Per què aquest començament per anar a vosaltres intuïtivament, fins i tot si ho fa, no només 369 00:17:45,320 --> 00:17:46,530 encara? 370 00:17:46,530 --> 00:17:47,030 Sí? 371 00:17:47,030 --> 00:17:47,990 >> AUDIÈNCIA: [inaudible]. 372 00:17:47,990 --> 00:17:51,652 373 00:17:51,652 --> 00:17:52,360 ALTAVEU: Exactament. 374 00:17:52,360 --> 00:17:55,810 En el millor escenari possible de ordenament de bombolla, i una gran quantitat d'algorismes, 375 00:17:55,810 --> 00:17:58,769 si et lliuro a vuit persones que ja estan ordenats, 376 00:17:58,769 --> 00:18:00,560 seria absurd per a vostè, l'algorisme, 377 00:18:00,560 --> 00:18:02,202 per anar cap enrere i endavant més d'una vegada, no? 378 00:18:02,202 --> 00:18:04,285 Perquè tan aviat com es caminar a través de la llista una vegada, 379 00:18:04,285 --> 00:18:08,090 vostè ha de donar compte, oh, no vaig fer cap swaps, aquesta llista està ordenada, sortida. 380 00:18:08,090 --> 00:18:09,700 Però això va a prendre vostè n passos. 381 00:18:09,700 --> 00:18:12,033 >> I al revés, el que és una altra forma de pensar sobre això? 382 00:18:12,033 --> 00:18:15,240 Ordenament de bombolla és un omega, per així dir-ho, de n, 383 00:18:15,240 --> 00:18:19,050 perquè si ens fixem en menys de n elements, el que 384 00:18:19,050 --> 00:18:23,009 és la qüestió fonamental que hi ha? 385 00:18:23,009 --> 00:18:24,550 No saps si és ordenada, correcta. 386 00:18:24,550 --> 00:18:26,800 Nosaltres els humans podrien ullada a les vuit persones i ser com, oh, està ordenada, 387 00:18:26,800 --> 00:18:28,430 que no em n mesures prendre, però ho van fer. 388 00:18:28,430 --> 00:18:30,810 Els seus ulls, tot i que tipus de tenir un gran camp de visió, 389 00:18:30,810 --> 00:18:33,184 vas mirar vuit elements, vas mirar a vuit persones, 390 00:18:33,184 --> 00:18:34,610 això és vuit passos amb eficàcia. 391 00:18:34,610 --> 00:18:38,612 I només si camí a través de tot llista ¿M'adono, sí, ordenats. 392 00:18:38,612 --> 00:18:41,320 Si m'aturo a meitat de camí de pensar, tot dret, que és bastant ordenades fins al moment, 393 00:18:41,320 --> 00:18:42,520 ¿Quines són les probabilitats que no està ordenada? 394 00:18:42,520 --> 00:18:44,186 Això no hi haurà algorismes correctes. 395 00:18:44,186 --> 00:18:46,250 Podria ser més ràpid, però incorrecta. 396 00:18:46,250 --> 00:18:48,500 >> Així que ara tenim una manera de descrivint una menor grau, 397 00:18:48,500 --> 00:18:49,710 i què passa amb la constant de temps? 398 00:18:49,710 --> 00:18:54,565 Què és un algorisme que té un menor amb destinació en el seu temps d'execució d'un? 399 00:18:54,565 --> 00:18:58,350 1 etapa, 2 etapes, 10 passos, però constant, independent de n, 400 00:18:58,350 --> 00:18:59,310 la mida de l'entrada? 401 00:18:59,310 --> 00:19:03,930 402 00:19:03,930 --> 00:19:04,600 Sí, a la part posterior. 403 00:19:04,600 --> 00:19:05,309 >> AUDIÈNCIA: printf? 404 00:19:05,309 --> 00:19:06,183 ALTAVEU: Què és això? 405 00:19:06,183 --> 00:19:07,184 AUDIÈNCIA: printf? 406 00:19:07,184 --> 00:19:07,850 ALTAVEU: printf. 407 00:19:07,850 --> 00:19:08,400 Bé, segur. 408 00:19:08,400 --> 00:19:10,720 Així que es necessita un nombre fix de passos. 409 00:19:10,720 --> 00:19:13,170 I hauria ara-- ara que estem parlant de codi C 410 00:19:13,170 --> 00:19:16,040 i no Scratch, cosa com per exemple, amb printf, 411 00:19:16,040 --> 00:19:17,710 hauríem de començar a anar amb compte. 412 00:19:17,710 --> 00:19:21,090 A causa printf això, pren d'entrada, que és una cadena, 413 00:19:21,090 --> 00:19:23,220 i les cordes no tenen tècnicament longitud. 414 00:19:23,220 --> 00:19:25,530 Així que si ara volem recollir en tu, si no t'importa, 415 00:19:25,530 --> 00:19:29,430 tècnicament podríem argumentar que printf no tenir una entrada de longitud variable, 416 00:19:29,430 --> 00:19:32,270 i segurament pot ser que prengui més temps per imprimir una cadena d'aquest llarg, 417 00:19:32,270 --> 00:19:33,560 d'aquest llarg. 418 00:19:33,560 --> 00:19:36,570 >> I què si tenim en compte només el classificació i recerca exemples? 419 00:19:36,570 --> 00:19:40,450 Què passa amb Mike Smith al telèfon llibre, o de recerca binària més general? 420 00:19:40,450 --> 00:19:42,220 En el millor dels casos, el que podria succeir? 421 00:19:42,220 --> 00:19:45,577 Obro la guia telefònica i, bam, hi ha nombre de Mike Smith. 422 00:19:45,577 --> 00:19:46,660 Jo li puc dir immediatament. 423 00:19:46,660 --> 00:19:49,390 >> Va prendre un pas, potser dos passos, però un nombre constant de passos 424 00:19:49,390 --> 00:19:50,230 si vaig tenir sort. 425 00:19:50,230 --> 00:19:52,570 I, francament, que vam veure en Dilluns a la seva companya de classe 426 00:19:52,570 --> 00:19:54,710 aconseguir bastant sort dues vegades seguides. 427 00:19:54,710 --> 00:19:57,050 I això va ser fet constant vegada en uns baixos límits 428 00:19:57,050 --> 00:20:01,280 en l'algorisme en qüestió per trobar el nombre 50 darrere de les tancades 429 00:20:01,280 --> 00:20:01,830 portes. 430 00:20:01,830 --> 00:20:06,400 >> Ara, com un a part, si descobreix que tant la gran O, el límit superior, 431 00:20:06,400 --> 00:20:09,310 i l'omega, el límit inferior, són un en el mateix, que 432 00:20:09,310 --> 00:20:11,830 és la mateixa fórmula en parèntesi, també pot 433 00:20:11,830 --> 00:20:15,170 dir, només per ser de luxe, que hi ha alguna cosa en zeta 434 00:20:15,170 --> 00:20:18,270 de n theta o d'algun altre valor. 435 00:20:18,270 --> 00:20:20,661 Això només significa que quan gran O i omega són els mateixos. 436 00:20:20,661 --> 00:20:21,910 Ara què passa amb la selecció espècie? 437 00:20:21,910 --> 00:20:23,400 Anem a utilitzar aquest nou vocabulari. 438 00:20:23,400 --> 00:20:27,407 En la selecció de classificació, que eren fent de nou, i una altra, i una altra? 439 00:20:27,407 --> 00:20:29,990 Jo anava cap enrere i endavant a través de la llista, a la recerca de qui? 440 00:20:29,990 --> 00:20:33,260 441 00:20:33,260 --> 00:20:34,730 El nombre més petit. 442 00:20:34,730 --> 00:20:37,560 >> Llavors, com molts passos, com moltes comparacions van fer I 443 00:20:37,560 --> 00:20:43,250 haver de fer per tal d'esbrinar qui l'element més petit de la llista era? 444 00:20:43,250 --> 00:20:44,437 n menys 1, no? 445 00:20:44,437 --> 00:20:47,770 Perquè si acabo de començar amb el qual estic donat i jo li poso a comparar, 446 00:20:47,770 --> 00:20:49,519 llavors ell o ella, li o ella, ell o ella, 447 00:20:49,519 --> 00:20:52,010 només pot aparellar elements junts n almenys 1 vegades. 448 00:20:52,010 --> 00:20:55,630 Així selecció té espècie de manera similar n almenys 1 passos la primera vegada. 449 00:20:55,630 --> 00:20:59,540 >> Quants passos que em porti a trobar el segon element més petit? 450 00:20:59,540 --> 00:21:02,920 n menys 2, perquè estic sent ximple si segueixo mirant les mateixes persones 451 00:21:02,920 --> 00:21:06,280 de nou si he ja ho seleccionat o ella i els va posar en el seu lloc. 452 00:21:06,280 --> 00:21:09,270 I el tercer pas, n mínim 3, llavors n almenys 4. 453 00:21:09,270 --> 00:21:11,020 Hem vist aquest patró abans, i de fet 454 00:21:11,020 --> 00:21:13,460 Selecció de tipus similar té un límit superior 455 00:21:13,460 --> 00:21:16,210 de n al quadrat si fem aquesta suma. 456 00:21:16,210 --> 00:21:19,790 Quin és el seu límit inferior, la selecció espècie? 457 00:21:19,790 --> 00:21:25,350 Com a mínim, la quantitat de temps de selecció ha de ordenar prendre, com el definim dilluns? 458 00:21:25,350 --> 00:21:29,370 459 00:21:29,370 --> 00:21:30,490 Proposar dues opcions. 460 00:21:30,490 --> 00:21:32,360 Potser és n, com abans. 461 00:21:32,360 --> 00:21:35,040 Potser és n al quadrat, ja que és ara com el límit superior. 462 00:21:35,040 --> 00:21:35,874 >> AUDIÈNCIA: n al quadrat. 463 00:21:35,874 --> 00:21:36,664 ALTAVEU: n al quadrat. 464 00:21:36,664 --> 00:21:37,368 Per què? 465 00:21:37,368 --> 00:21:40,060 >> AUDIÈNCIA: Com que té per definir [inaudible]. 466 00:21:40,060 --> 00:21:41,510 >> ALTAVEU: Exactament. 467 00:21:41,510 --> 00:21:45,077 Almenys pel vaig definir ordenament per selecció era bastant ingènua, seguir endavant, 468 00:21:45,077 --> 00:21:46,160 trobar l'element més petit. 469 00:21:46,160 --> 00:21:47,770 Anar de nou, trobar l'element més petit. 470 00:21:47,770 --> 00:21:49,490 Anar de nou, trobar l'element més petit. 471 00:21:49,490 --> 00:21:51,700 No hi ha cap mena de optimització motiu 472 00:21:51,700 --> 00:21:54,350 podria deixar-me avortar després només n o menys passos. 473 00:21:54,350 --> 00:21:57,080 Així que de fet, la selecció tipus, omega de n al quadrat. 474 00:21:57,080 --> 00:22:00,667 >> Què passa amb l'ordenació per inserció, on vaig prendre que em van donar, i llavors jo li vaig deixar 475 00:22:00,667 --> 00:22:01,750 o ella en el lloc correcte? 476 00:22:01,750 --> 00:22:04,958 Llavors vaig procedir a la segona persona, ell o ella es va deixar caure al lloc correcte. 477 00:22:04,958 --> 00:22:07,910 Llavors la següent persona, es va deixar ell o ella en el lloc correcte. 478 00:22:07,910 --> 00:22:10,537 Tingueu en compte que això és molt lineals, per així dir-ho. 479 00:22:10,537 --> 00:22:12,620 Sóc una línia recta, estic no anar i venir, 480 00:22:12,620 --> 00:22:16,080 Mai mirar cap enrere en realitat, però el que està succeint quan ho introdueixo 481 00:22:16,080 --> 00:22:20,302 o ella en el començament de la llista com ho vam fer dilluns? 482 00:22:20,302 --> 00:22:21,010 El que està succeint? 483 00:22:21,010 --> 00:22:21,510 Sí? 484 00:22:21,510 --> 00:22:23,122 AUDIÈNCIA: [inaudible]. 485 00:22:23,122 --> 00:22:24,830 ALTAVEU: Sí, això va ser la captura, oi? 486 00:22:24,830 --> 00:22:26,746 Vostè pot recordar de seus companys de classe, si 487 00:22:26,746 --> 00:22:29,670 estaven fent cap moviment amb seus peus, que era una operació. 488 00:22:29,670 --> 00:22:33,610 Així que si hi havia tres persones aquí i la nova persona pertanyia fins allà, 489 00:22:33,610 --> 00:22:37,360 en una llarga etapa com aquesta, és clar, o ella només podia anar fins al final. 490 00:22:37,360 --> 00:22:40,074 Però si estem pensant en un ordinador i una matriu de la memòria, 491 00:22:40,074 --> 00:22:41,990 aquestes persones van a haver de remenar més 492 00:22:41,990 --> 00:22:43,260 per donar cabuda a aquesta persona. 493 00:22:43,260 --> 00:22:46,930 I perquè n almenys 1 shufflings, n almenys 2 shufflings, n 494 00:22:46,930 --> 00:22:50,660 almenys 3 shufflings és només una mica de passant darrere de mi, no al davant de mi 495 00:22:50,660 --> 00:22:52,710 com abans, en algun sentit. 499 00:22:52,557 --> 00:22:54,640 Ara com un part, i com que podria haver vist en línia 500 00:22:54,640 --> 00:22:57,699 si vostè comença a furgar sobre tipus, hi ha tan molts diversos 501 00:22:57,699 --> 00:22:59,490 per aquí, alguns d'ells millor que altres. 502 00:22:59,490 --> 00:23:02,200 De fet, és un Bogosort això és bastant divertit per mirar cap amunt. 503 00:23:02,200 --> 00:23:06,650 Bogosort pren un conjunt de números o dir una baralla de cartes, 504 00:23:06,650 --> 00:23:09,870 les baralla a l'atzar, i comprova si estan ordenats. 505 00:23:09,870 --> 00:23:12,130 I si no, ho fa de nou. 506 00:23:12,130 --> 00:23:14,140 I si no, ho fa de nou. 507 00:23:14,140 --> 00:23:15,440 Si no, ho fa de nou. 508 00:23:15,440 --> 00:23:17,060 Increïblement estúpid. 509 00:23:17,060 --> 00:23:19,520 >> I de fet, si vostè llegeix igual que l'article de Wikipedia, 510 00:23:19,520 --> 00:23:21,200 el seu sobrenom és estúpida espècie. 511 00:23:21,200 --> 00:23:25,180 Amb el temps funcionarà, amb sort, donat el temps suficient, 512 00:23:25,180 --> 00:23:28,240 però aquesta quantitat de temps podria arribar a alentir. 513 00:23:28,240 --> 00:23:31,650 Així que si jo pogués, anem a accelerar les coses des de l'exemple de Mary Beth abans, 514 00:23:31,650 --> 00:23:35,150 per tenir alguns elements més, sinó dos processadors més. 515 00:23:35,150 --> 00:23:37,100 Dues persones, si no li importaria acompanyar-me. 516 00:23:37,100 --> 00:23:40,972 Què hi ha de 1 per aquí, i anem a vaya-- ningú allà? 517 00:23:40,972 --> 00:23:41,722 Ningú d'allà? 518 00:23:41,722 --> 00:23:42,221 Okay. 519 00:23:42,221 --> 00:23:44,190 Vostè amb el negre camisa, sí, anem cap avall. 520 00:23:44,190 --> 00:23:45,000 Molt bé, quin és el teu nom? 521 00:23:45,000 --> 00:23:45,720 >> AUDIÈNCIA: Peter. 522 00:23:45,720 --> 00:23:46,100 >> ALTAVEU: Què és això? 523 00:23:46,100 --> 00:23:46,766 >> AUDIÈNCIA: Peter. 524 00:23:46,766 --> 00:23:49,450 ALTAVEU: Pedro, David, encantat de conèixer-te. 525 00:23:49,450 --> 00:23:53,670 Molt bé, tenim Peter aquí, si volen venir a la taula aquí. 526 00:23:53,670 --> 00:23:54,550 I quin és el teu nom? 527 00:23:54,550 --> 00:23:55,216 >> AUDIÈNCIA: Elena. 528 00:23:55,216 --> 00:23:55,970 ALTAVEU: Elena. 529 00:23:55,970 --> 00:23:57,030 Bé, encantat de conèixer-te. 530 00:23:57,030 --> 00:23:58,060 Elena compleix amb Peter. 531 00:23:58,060 --> 00:23:59,170 Peter, Elena. 532 00:23:59,170 --> 00:24:02,290 I necessitarem Andrew aquí també, si us plau. 533 00:24:02,290 --> 00:24:06,107 I el seu repte va ser per ordenar una baralla de cartes. 534 00:24:06,107 --> 00:24:08,190 I si no familiar, coberta de targetes deu en última instància, 535 00:24:08,190 --> 00:24:11,064 ordenar una mica alguna cosa com això on farem els clubs, a continuació, 536 00:24:11,064 --> 00:24:13,660 les espases, a continuació, els cors i diamants, des ace com un, 537 00:24:13,660 --> 00:24:15,570 tot el camí fins al rei. 538 00:24:15,570 --> 00:24:20,890 >> Les targetes que vaig a donar-li seran 52 en quantitat. 539 00:24:20,890 --> 00:24:23,160 Anem a similar vegada que, en un moment. 540 00:24:23,160 --> 00:24:26,410 Anem a llançar Andrew a la pantalla aquí, 541 00:24:26,410 --> 00:24:28,170 per tal de veure com fer això. 542 00:24:28,170 --> 00:24:31,070 I perquè tot això és tant més visible, 543 00:24:31,070 --> 00:24:33,490 aquestes són les cartes que vaig rebre a Amazon. 544 00:24:33,490 --> 00:24:42,861 Així que ja són a l'atzar solucionar, i que anem a mesurar el temps que vostè. 545 00:24:42,861 --> 00:24:44,610 I anem a viure en la realitat d'aquest temps, 546 00:24:44,610 --> 00:24:47,820 així que tractarem de pressionar perquè si no això serà tediós 547 00:24:47,820 --> 00:24:48,460 ràpidament. 548 00:24:48,460 --> 00:24:53,860 Si es pogués procedir a ordenar 52 elements junts a través d'alguns mitjans, ara. 549 00:24:53,860 --> 00:25:04,710 550 00:25:04,710 --> 00:25:07,180 >> I de nou, quan veiem aquests nois fan el que, al final 551 00:25:07,180 --> 00:25:10,200 es produirà una evident resultat, pensa realment 552 00:25:10,200 --> 00:25:12,962 com ho estan fent cada un que, com podria descriure-ho. 553 00:25:12,962 --> 00:25:15,045 Perquè de nou, aquests són tots els processos, algoritmes 554 00:25:15,045 --> 00:25:17,090 que nosaltres donem per fet com un ésser humà. 555 00:25:17,090 --> 00:25:22,349 Però vostè ha tingut probablement molt intuïció, molt abans que fins i tot 556 00:25:22,349 --> 00:25:24,390 pensat en prendre un classe d'informàtica que 557 00:25:24,390 --> 00:25:27,223 podria haver tingut la intuïció amb que per resoldre problemes com aquest. 558 00:25:27,223 --> 00:25:29,560 Però una vegada que reconeixen els patrons i començar 559 00:25:29,560 --> 00:25:32,407 per formalitzar els passos amb els quals vostè està la solució d'aquests problemes, 560 00:25:32,407 --> 00:25:35,490 trobareu que vostè pot solucionar molt més interessant i molt més complex 561 00:25:35,490 --> 00:25:39,190 problemes ràpidament. 562 00:25:39,190 --> 00:25:42,351 Així que algú del públic, el que és almenys un element de l'algoritme 563 00:25:42,351 --> 00:25:43,350 que estan fent servir aquí? 564 00:25:43,350 --> 00:25:44,275 >> AUDIÈNCIA: [inaudible] 565 00:25:44,275 --> 00:25:45,150 ALTAVEU: Què és això? 566 00:25:45,150 --> 00:25:47,062 AUDIÈNCIA: Per exemple. 567 00:25:47,062 --> 00:25:47,770 ALTAVEU: Per exemple. 568 00:25:47,770 --> 00:25:50,630 Així que primer que s'estan agrupant tots els diamants junts 569 00:25:50,630 --> 00:25:52,560 pel que sembla, tot el cors junts el que sembla, 570 00:25:52,560 --> 00:25:56,520 i així successivament, sense respecte per als números de les targetes. 571 00:25:56,520 --> 00:26:00,900 I ara apareixen, per exemple, ser ordenant-los per nombre. 572 00:26:00,900 --> 00:26:06,870 573 00:26:06,870 --> 00:26:08,910 Molt bona. 574 00:26:08,910 --> 00:26:12,370 >> Molt bé, així que el que va a ser el pas final, llavors aquí? 575 00:26:12,370 --> 00:26:16,950 Un cop tenim quatre pals ordenats, el que Per què hem de fer per a les quatre piles 576 00:26:16,950 --> 00:26:20,059 amb la finalitat d'aconseguir-ne un coberta ordenats, simplement? 577 00:26:20,059 --> 00:26:21,350 Així que hem de combina una altra vegada. 578 00:26:21,350 --> 00:26:25,160 >> Així que hi ha una idea interessant que de nou, diria, és molt intuïtiu fins i tot 579 00:26:25,160 --> 00:26:28,140 si vostè mai podria haver bufetejat aquest tipus d'etiqueta. 580 00:26:28,140 --> 00:26:31,900 Aquesta noció fonamental de la divisió el problema no a la meitat d'aquest temps, 581 00:26:31,900 --> 00:26:33,410 però almenys en quatre peces. 582 00:26:33,410 --> 00:26:36,810 Resoldre gairebé problemes fonamentalment idèntics 583 00:26:36,810 --> 00:26:40,480 en l'aïllament d'un a l'altre, i després combinar els resultats. 584 00:26:40,480 --> 00:26:46,940 585 00:26:46,940 --> 00:26:50,140 I, excel · lent, fet. 586 00:26:50,140 --> 00:26:52,140 Molt bé, una gran ronda d'aplaudiments, si poguéssim. 587 00:26:52,140 --> 00:26:56,480 >> [Aplaudiments] 588 00:26:56,480 --> 00:26:59,740 >> ALTAVEU: No tinc ni idea del que va a fer amb ells, però aquí tens. 589 00:26:59,740 --> 00:27:01,690 Moltes gràcies. 590 00:27:01,690 --> 00:27:04,660 Així que anem a veure, a dos minuts i vuit segons, de 591 00:27:04,660 --> 00:27:07,490 si vol desafiar als teus amics. 592 00:27:07,490 --> 00:27:12,160 Llavors, què va a ser una presa de distància d'aquesta 593 00:27:12,160 --> 00:27:13,830 que podem aprofitar de forma més general? 594 00:27:13,830 --> 00:27:16,080 Bé, pensi de nou a aquest conjunt de nombres, 595 00:27:16,080 --> 00:27:19,060 i pensar de nou ara a algunes de les pseudocodi que hem escrit en el passat, 596 00:27:19,060 --> 00:27:22,080 i aquest va ser el pseudocodi per resoldre el problema de la guia telefònica. 597 00:27:22,080 --> 00:27:25,150 Per la qual cosa en pseudocodi I enumerat una manera més metòdica 598 00:27:25,150 --> 00:27:28,400 de descriure la forma en què vaig fer un molt intuïtiu algorisme humana de dividir el telèfon 599 00:27:28,400 --> 00:27:31,650 llibre per la meitat, repetir, repetir, repetir, fins que trobi algú com Mike Smith, 600 00:27:31,650 --> 00:27:33,790 si és fet a la guia telefònica. 601 00:27:33,790 --> 00:27:37,610 >> Però quin tipus de vaig utilitzar el que jo anomeno un enfocament molt iteratiu aquí, 602 00:27:37,610 --> 00:27:42,160 en particular notificació línia 8 i la línia 11. 603 00:27:42,160 --> 00:27:46,750 Aquests són evidència d'un procés iteratiu enfocament, un enfocament de bucle, 604 00:27:46,750 --> 00:27:49,040 perquè això és exactament el comportament que indueixen. 605 00:27:49,040 --> 00:27:52,910 Aquestes línies de tots dos diuen anar a línia de tres, i vostè pot tipus de 606 00:27:52,910 --> 00:27:55,140 pensar que en el seu l'ull de la ment com un bucle. 607 00:27:55,140 --> 00:27:59,080 Li està dient a tornar a pujar al pas 3 i repetir, una i altra vegada, 608 00:27:59,080 --> 00:28:00,010 i una altra vegada. 609 00:28:00,010 --> 00:28:04,410 >> Però i si aprofitem una idea clau aquí que vam fer no l'última vegada, 610 00:28:04,410 --> 00:28:10,280 i simplificar la línia 8 i línia 11 i els seus veïns 611 00:28:10,280 --> 00:28:12,840 com acaba això, en groc. 612 00:28:12,840 --> 00:28:16,480 No és fonamentalment escurçar el pseudocodi molt, 613 00:28:16,480 --> 00:28:20,530 però està canviant fonamentalment la naturalesa del meu algorisme. 614 00:28:20,530 --> 00:28:24,220 El que ara estic dient en el pas 7, al pas 10, 615 00:28:24,220 --> 00:28:29,140 és la recerca de Mike de la mateixa manera exacta, 616 00:28:29,140 --> 00:28:31,580 però només en l'esquerra la meitat o la meitat dreta. 617 00:28:31,580 --> 00:28:33,420 >> Així, en altres paraules, si Començo des del pas un, 618 00:28:33,420 --> 00:28:36,150 recollir la guia telefònica, obert a mig de guia telefònica, mirar noms, 619 00:28:36,150 --> 00:28:39,010 si es troba entre Smith nom d', truqueu a Mike, la resta 620 00:28:39,010 --> 00:28:44,340 si Smith és anterior al llibre, pas 7 buscar Mike en la meitat esquerra del llibre. 621 00:28:44,340 --> 00:28:47,130 Però aquest tipus de se sent com m'està deixant penjar, oi? 622 00:28:47,130 --> 00:28:49,240 En groc, és un instrucció, però com puc 623 00:28:49,240 --> 00:28:51,870 buscar Mike a l'esquerra la meitat de la guia telefònica? 624 00:28:51,870 --> 00:28:54,210 On tinc un algorisme amb el qual 625 00:28:54,210 --> 00:28:57,100 pot buscar a algú com Mike Smith? 626 00:28:57,100 --> 00:28:58,980 Bé, ens està mirant a la cara. 627 00:28:58,980 --> 00:29:03,090 Literalment, puc utilitzar la mateixa exacta programa va efectivament al cim 628 00:29:03,090 --> 00:29:06,490 de nou i tornar a córrer les mateixes línies de codi. 629 00:29:06,490 --> 00:29:10,610 >> Així que, tot i que aquest ha de sentir com una mica d'una definició cíclica 630 00:29:10,610 --> 00:29:13,480 on vostè està responent a algú és pregunta per només una espècie de demanar 631 00:29:13,480 --> 00:29:15,990 la mateixa pregunta de nou, com per què, per què, per què? 632 00:29:15,990 --> 00:29:21,580 La realitat és perquè hem codifiquem un parell de línies especials, el pas 4, 633 00:29:21,580 --> 00:29:25,320 que és un si, i el pas 12, el qual és efectivament una altra branca, 634 00:29:25,320 --> 00:29:30,120 perquè tenim aquestes mesures provisionals, aquest algorisme acabarà si 635 00:29:30,120 --> 00:29:32,050 trobar Mike, o si no ho fem. 636 00:29:32,050 --> 00:29:36,810 Però en el pas 7 i 10 ara, tenim el que anomenarem un algorisme recursiu. 637 00:29:36,810 --> 00:29:40,420 I recursivitat és de fet una idea poderosa això és una mica lucinant al principi, 638 00:29:40,420 --> 00:29:42,500 que ara podem aplicar la següent manera. 639 00:29:42,500 --> 00:29:46,600 >> Combinar tipus serà l'últim tipus que mirem, almenys en la classe formal. 640 00:29:46,600 --> 00:29:50,040 I és fonamentalment diferent dels últims tres, i certament 641 00:29:50,040 --> 00:29:52,140 últims quatre si incloem Bogosort. 642 00:29:52,140 --> 00:29:54,810 Aquí està el pseudocodi per merge sort. 643 00:29:54,810 --> 00:30:00,170 Quan en l'entrada de n elements, de manera que donada una matriu de grandària n, si n és menor que 2, 644 00:30:00,170 --> 00:30:01,040 tornar. 645 00:30:01,040 --> 00:30:03,610 Llavors, ¿per què he de seny comprovar primer? 646 00:30:03,610 --> 00:30:09,477 Quina és la implicació que si et lliuro una matriu la longitud n és menor que 2? 647 00:30:09,477 --> 00:30:11,060 Ja està ordenada, òbviament, no? 648 00:30:11,060 --> 00:30:13,640 Com que la llista té ja sigui un element, que és trivialment 649 00:30:13,640 --> 00:30:15,180 ordenada perquè és l'únic que hi ha. 650 00:30:15,180 --> 00:30:18,138 O, és de mida zero, el que significa no hi ha res arreglar, així que per la naturalesa 651 00:30:18,138 --> 00:30:18,720 que està ordenada. 652 00:30:18,720 --> 00:30:20,410 No hi ha res malament allà. 653 00:30:20,410 --> 00:30:22,310 Així que aquest és el nostre anomenat cas base. 654 00:30:22,310 --> 00:30:24,440 >> Que és similar en esperit al que vam fer amb Mike. 655 00:30:24,440 --> 00:30:26,023 Si Mike en la guia telefònica, li diuen. 656 00:30:26,023 --> 00:30:27,740 Si ell no hi és, donar-se per vençut. 657 00:30:27,740 --> 00:30:31,240 És un cas base de l'anomenada, per assegurar aquest algorisme al final del dia 658 00:30:31,240 --> 00:30:33,540 s'aturarà en certes circumstàncies. 659 00:30:33,540 --> 00:30:37,890 >> Però aquí hi ha el salt de fe ara, una altra cosa, ordenar la meitat esquerra dels elements, 660 00:30:37,890 --> 00:30:39,740 a continuació, ordenar el dret mitjà dels elements, 661 00:30:39,740 --> 00:30:41,189 i després fusionar les meitats ordenats. 662 00:30:41,189 --> 00:30:43,230 I aquí és on se sent com que estem Copping terme. 663 00:30:43,230 --> 00:30:46,900 T'he demanat per ordenar n elements, i estic 664 00:30:46,900 --> 00:30:50,712 dient, bé, no és per la classificació l'esquerra i la classificació de la dreta. 665 00:30:50,712 --> 00:30:52,420 El que dic és una una altra cosa, i això 666 00:30:52,420 --> 00:30:55,530 és el tema clau sembla en la intuïció fins ara, 667 00:30:55,530 --> 00:30:57,380 hi ha aquesta tercera etapa de la fusió. 668 00:30:57,380 --> 00:31:00,430 Què encara sembla tan ximple en esperit, 669 00:31:00,430 --> 00:31:02,320 com acaba de fusionar coses junts, sembla 670 00:31:02,320 --> 00:31:05,380 ser un pas clau cap a la muntatge de dos problemes que 671 00:31:05,380 --> 00:31:07,330 es van dividir en última instància per la meitat. 672 00:31:07,330 --> 00:31:12,090 >> Així fusionar tipus, farem això, si em humor mi, amb una manifestació més, 673 00:31:12,090 --> 00:31:14,730 només perquè tinguem una mica de números per treballar amb. 674 00:31:14,730 --> 00:31:19,470 Puc intercanviar 08:00 estrès boles per a vuit persones? 675 00:31:19,470 --> 00:31:29,320 Molt bé, i tu tres, quatre en aquesta secció, cinc, sis, i anem a 676 00:31:29,320 --> 00:31:30,720 do 7, 8, anem a dalt. 677 00:31:30,720 --> 00:31:35,120 678 00:31:35,120 --> 00:31:36,520 Acceptar, sí acord. 679 00:31:36,520 --> 00:31:38,640 Minus 8, allà anem, més 1. 680 00:31:38,640 --> 00:31:39,150 Excel · lent. 681 00:31:39,150 --> 00:31:42,000 Tot ve dret cap amunt, anem a ràpidament li donarà nombres. 682 00:31:42,000 --> 00:31:50,800 El número dos, número tres, número quatre, nombre cinc, sis, set-vuit. 683 00:31:50,800 --> 00:31:52,140 Vaig 08:00 correctament aquesta vegada. 684 00:31:52,140 --> 00:31:56,390 >> OK, així que endavant si es pogués, i anem a ordenar en l'ordre original 685 00:31:56,390 --> 00:31:59,810 que vam tenir ahir que semblava així, si no t'importa. 686 00:31:59,810 --> 00:32:03,620 I anem a fer-ho davant de la taula. 687 00:32:03,620 --> 00:32:06,510 Molt bé, així que fusionar espècie. 688 00:32:06,510 --> 00:32:08,820 Aquí és on es va per aconseguir una espècie d'interessant, 689 00:32:08,820 --> 00:32:12,800 perquè em sembla que estic donant a mi mateix molt menys informació avui en dia. 690 00:32:12,800 --> 00:32:15,149 >> Així fusionar tipus primer de tot a l'entrada de n elements, 691 00:32:15,149 --> 00:32:18,440 i és, òbviament, no menys de dos, és 8, així que tenen una mica més de feina a fer. 692 00:32:18,440 --> 00:32:21,140 Així que ara estem mentalment com una classe estan ara en la branca else, 693 00:32:21,140 --> 00:32:22,540 el que significa tres passos. 694 00:32:22,540 --> 00:32:25,017 En primer lloc, he de ordenar la meitat esquerra dels elements. 695 00:32:25,017 --> 00:32:26,350 Llavors, com faig per fer això? 696 00:32:26,350 --> 00:32:28,950 Bé, vaig a classe de mentalment dividir la llista aquí, 697 00:32:28,950 --> 00:32:30,700 vostè no ha de moure físicament, i estic 698 00:32:30,700 --> 00:32:33,180 centrarem només en la meitat esquerra dels elements aquí. 699 00:32:33,180 --> 00:32:36,770 Llavors, com faig per ordenar una llista ara de la mida de quatre? 700 00:32:36,770 --> 00:32:38,730 Quin és el meu algorisme? 701 00:32:38,730 --> 00:32:42,580 Primer comprovo és n menys de dos, no, així que em dedico al bloc diferent. 702 00:32:42,580 --> 00:32:43,900 Ordenar a l'esquerra de la meitat dels elements. 703 00:32:43,900 --> 00:32:45,608 >> Així que ara de nou, mentalment, i aquí és on 704 00:32:45,608 --> 00:32:49,550 has acumular una gran quantitat de història mental, si es vol. 705 00:32:49,550 --> 00:32:51,940 Ara estic ordenant l'esquerre la meitat de la meitat esquerra. 706 00:32:51,940 --> 00:32:57,000 Molt bé, així que ara dic a mi mateixa combinació algoritme d'ordenació, és n menys de dos? 707 00:32:57,000 --> 00:33:00,590 No, és de dos, així que he de ordenar la meitat esquerra i la meitat dreta. 708 00:33:00,590 --> 00:33:02,042 Així que aquí anem, ordenar la meitat esquerra. 709 00:33:02,042 --> 00:33:03,750 Per què no acaba de fer un pas cap endavant. 710 00:33:03,750 --> 00:33:04,415 Quin és el teu nom? 711 00:33:04,415 --> 00:33:04,860 >> AUDIÈNCIA: Darren. 712 00:33:04,860 --> 00:33:05,260 >> ALTAVEU: Dan. 713 00:33:05,260 --> 00:33:06,040 Dan ha fet un pas endavant. 714 00:33:06,040 --> 00:33:06,748 >> AUDIÈNCIA: Darren. 715 00:33:06,748 --> 00:33:09,000 ALTAVEU: Darren, fet. 716 00:33:09,000 --> 00:33:10,090 ¿Va dir Darren o Dan? 717 00:33:10,090 --> 00:33:10,550 >> AUDIÈNCIA: Darren. 718 00:33:10,550 --> 00:33:11,216 >> ALTAVEU: Darren. 719 00:33:11,216 --> 00:33:14,422 Acceptar, Darren ha intensificat cap endavant i ara està solucionat. 720 00:33:14,422 --> 00:33:16,130 I això és gairebé una afirmació estúpida, oi? 721 00:33:16,130 --> 00:33:18,862 Realment no sembla estar assolint res, però anem a procedir. 722 00:33:18,862 --> 00:33:20,820 Ara vaig a ordenar la dreta mitjà dels elements. 723 00:33:20,820 --> 00:33:21,200 Quin és el teu nom? 724 00:33:21,200 --> 00:33:21,690 >> AUDIÈNCIA: Lucas. 725 00:33:21,690 --> 00:33:22,273 >> ALTAVEU: Lucas. 726 00:33:22,273 --> 00:33:23,400 Anem, un pas endavant. 727 00:33:23,400 --> 00:33:25,640 Fet, he classificat Lucas. 728 00:33:25,640 --> 00:33:28,570 La meitat esquerra està classificat i la meitat dreta està ordenada, 729 00:33:28,570 --> 00:33:30,770 però de nou, hi ha un pas clau aquí. 730 00:33:30,770 --> 00:33:32,940 Què he de fer la propera? 731 00:33:32,940 --> 00:33:33,941 Combinar les meitats ordenats. 732 00:33:33,941 --> 00:33:36,648 Ara tindrem només tots enrere i cap endavant d'aquesta manera, 733 00:33:36,648 --> 00:33:38,620 perquè Jo com que necessito una mica d'espai zero. 734 00:33:38,620 --> 00:33:40,411 És gairebé com aquests nois estan en una taula, 735 00:33:40,411 --> 00:33:42,460 i necessito una mica d'espai per moure'ls a. 736 00:33:42,460 --> 00:33:44,170 Així que vaig a fusionar vostès per mirar 737 00:33:44,170 --> 00:33:45,960 en la meitat esquerra i la meitat dreta. 738 00:33:45,960 --> 00:33:48,740 I que, òbviament, és el primer, la meitat esquerra o la meitat dreta? 739 00:33:48,740 --> 00:33:52,710 Així que la meitat dreta, per la qual cosa anem a passar a Luke aquí a la posició original de Darren. 740 00:33:52,710 --> 00:33:57,640 I ara fusionar la seva meitat esquerra a, Darren va a moure a la dreta allà. 741 00:33:57,640 --> 00:33:59,750 >> Així que se sent com gairebé un efecte bombolla espècie, 742 00:33:59,750 --> 00:34:02,482 però el meu algorisme fonamental, molt diferent aquesta vegada. 743 00:34:02,482 --> 00:34:04,815 Però ara és on les coses es posen una mica molest perquè vostè 744 00:34:04,815 --> 00:34:06,810 haver de rebobinar mentalment on vaig deixar fora. 745 00:34:06,810 --> 00:34:09,893 Acabo vaig fondre les meitats ordenades, el que significa que estic en el meu algorisme? 746 00:34:09,893 --> 00:34:12,229 747 00:34:12,229 --> 00:34:13,770 He d'ordenar la meitat dreta, no? 748 00:34:13,770 --> 00:34:15,910 >> Si rebobina, literalment al vídeo, podràs 749 00:34:15,910 --> 00:34:18,339 veiem que arribem a aquest punt de Luke i Darren 750 00:34:18,339 --> 00:34:21,370 per la classificació de l'esquerra la meitat de la meitat esquerra. 751 00:34:21,370 --> 00:34:23,430 Llavors ens fusionem els meitats ordenades, que 752 00:34:23,430 --> 00:34:27,941 significa que el següent pas és ordenar la meitat dreta de la meitat esquerra. 753 00:34:27,941 --> 00:34:29,649 Molt bé, així que anem a fer això més ràpidament. 754 00:34:29,649 --> 00:34:33,282 Molt bé, sis, vaig a reclamar que ara s'ordenen, anem cap endavant. 755 00:34:33,282 --> 00:34:33,990 Quin és el teu nom? 756 00:34:33,990 --> 00:34:34,589 >> AUDIÈNCIA: Adriano. 757 00:34:34,589 --> 00:34:35,200 >> ALTAVEU: Adriano. 758 00:34:35,200 --> 00:34:36,010 Adriano està solucionat. 759 00:34:36,010 --> 00:34:36,450 I quin és el teu nom? 760 00:34:36,450 --> 00:34:37,080 >> AUDIÈNCIA: Alex. 761 00:34:37,080 --> 00:34:38,379 >> ALTAVEU: Alex està ara ordenades. 762 00:34:38,379 --> 00:34:40,750 Medi esquerre, mig dret, ¿Quin és el pas final? 763 00:34:40,750 --> 00:34:41,250 Combinar. 764 00:34:41,250 --> 00:34:44,310 Pretty trivial, així que estic va a fusionar en sis, 765 00:34:44,310 --> 00:34:46,930 fer un pas enrere, 8, fer un pas enrere. 766 00:34:46,930 --> 00:34:49,530 I ara noti que això és un dinar per emportar útil, el que 767 00:34:49,530 --> 00:34:53,930 ara és veritat sobre la meitat esquerra de la llista, independentment de com comencem? 768 00:34:53,930 --> 00:34:55,090 S'està ordenada. 769 00:34:55,090 --> 00:34:57,750 >> Ara que no està ordenada en el gran esquema de les coses, 770 00:34:57,750 --> 00:35:00,250 però està ordenada de forma independent de l'altra meitat. 771 00:35:00,250 --> 00:35:04,100 Ara el que pas sóc jo en si segueixo rebobinat de com va començar la història? 772 00:35:04,100 --> 00:35:05,680 Ara he de ordenar la meitat dreta. 773 00:35:05,680 --> 00:35:07,630 Així que ara estem en el camí de tornada el principi de la història, 774 00:35:07,630 --> 00:35:08,921 i farem això amb més rapidesa. 775 00:35:08,921 --> 00:35:11,320 Així que vaig a ordenar la meitat dreta de tota la llista. 776 00:35:11,320 --> 00:35:13,060 Quin és el següent pas? 777 00:35:13,060 --> 00:35:15,840 Ordenar la meitat esquerra de la meitat dreta. 778 00:35:15,840 --> 00:35:18,715 Ordenar la meitat esquerra de la meitat esquerra de la meitat dreta. 779 00:35:18,715 --> 00:35:19,590 I quin és el teu nom? 780 00:35:19,590 --> 00:35:20,230 >> AUDIÈNCIA: Omar. 781 00:35:20,230 --> 00:35:21,970 >> ALTAVEU: Omar, un pas endavant, fet. 782 00:35:21,970 --> 00:35:22,860 La meitat esquerra està ordenada. 783 00:35:22,860 --> 00:35:23,330 I quin és el teu nom? 784 00:35:23,330 --> 00:35:23,820 >> AUDIÈNCIA: Chris. 785 00:35:23,820 --> 00:35:25,620 >> ALTAVEU: Chris, fer un pas cap endavant, que ara està ordenada. 786 00:35:25,620 --> 00:35:27,010 Quin és el pas clau ara? 787 00:35:27,010 --> 00:35:27,510 Combinar. 788 00:35:27,510 --> 00:35:30,509 Així que un va a fusionar en el seu lloc aquí, si pogués fer un pas enrere, 789 00:35:30,509 --> 00:35:32,930 -tres va a fer un pas enrere, es fonen. 790 00:35:32,930 --> 00:35:38,080 Així que la meitat esquerra de la meitat dreta, ara està solucionat. 791 00:35:38,080 --> 00:35:41,747 Francament, aquest algorisme se sent com que estan perdent molt més temps que abans, 792 00:35:41,747 --> 00:35:44,830 però si ho féssim això en temps real, anem a veure el que els robatoris de pilota serà. 793 00:35:44,830 --> 00:35:47,970 Ara aquí estic, no la meitat de la meitat dreta, 794 00:35:47,970 --> 00:35:50,170 m'ho dius a mi anar endavant i ordenar la meitat esquerra. 795 00:35:50,170 --> 00:35:51,482 Pas endavant, com et dius? 796 00:35:51,482 --> 00:35:52,190 AUDIÈNCIA: Ramsey. 797 00:35:52,190 --> 00:35:53,210 ALTAVEU: Ramsey està solucionat. 798 00:35:53,210 --> 00:35:53,570 Quin és el teu nom? 799 00:35:53,570 --> 00:35:54,200 >> AUDIÈNCIA: Marina. 800 00:35:54,200 --> 00:35:57,033 >> ALTAVEU: Marina està classificat com així, si vostè pren un pas cap endavant. 801 00:35:57,033 --> 00:36:00,690 Pas clau és ara fusionar, estic va a arrencar de les meves dues llistes, 802 00:36:00,690 --> 00:36:01,720 esquerra i dreta. 803 00:36:01,720 --> 00:36:05,150 Cinc serà el primer, -set serà el pròxim. 804 00:36:05,150 --> 00:36:06,410 I de nou, això és deliberat. 805 00:36:06,410 --> 00:36:08,535 El fet que estan prenent passos cap endavant i cap enrere 806 00:36:08,535 --> 00:36:12,997 té la intenció de representar que no podem fer aquest algorisme en el seu lloc amb la mateixa facilitat 807 00:36:12,997 --> 00:36:15,830 com a espècie de bombolla, i la selecció de tipus, i tipus d'inserció en el qual només 808 00:36:15,830 --> 00:36:16,960 guardat intercanviant persones. 809 00:36:16,960 --> 00:36:19,940 Jo, literalment, necessito una espècie de paper esborrany en el qual 810 00:36:19,940 --> 00:36:21,827 per posar a aquestes persones mentre faig la fusió, 811 00:36:21,827 --> 00:36:23,410 i llavors puc tornar a posar al seu lloc. 812 00:36:23,410 --> 00:36:27,260 I això és clau perquè estic utilitzant un nou recurs, l'espai, no només temps. 813 00:36:27,260 --> 00:36:28,270 >> OK, això és increïble. 814 00:36:28,270 --> 00:36:32,050 La meitat esquerra està ordenada, la meitat dreta és pas ordenat, ara que la fusió de tecla. 815 00:36:32,050 --> 00:36:33,450 Com vaig a fusionar això? 816 00:36:33,450 --> 00:36:35,470 Així que si vostè segueix el meu la mà esquerra i la mà dreta, 817 00:36:35,470 --> 00:36:38,930 Vaig a assenyalar la meva mà esquerra en la meitat esquerra, la mà dreta 818 00:36:38,930 --> 00:36:42,680 en la meitat dreta, i ara he de decidir pas a pas a qui es fonen en. 819 00:36:42,680 --> 00:36:44,650 Que òbviament és el primer? 820 00:36:44,650 --> 00:36:45,150 Número u. 821 00:36:45,150 --> 00:36:47,327 Així que vine aquí, aquí està el nostre bloc de notes. 822 00:36:47,327 --> 00:36:49,910 Així que ara el número u, i l'avís el que faré amb la meva mà dreta, 823 00:36:49,910 --> 00:36:54,152 Vaig a moure la meva mà dreta una passar per sobre al punt número tres, 824 00:36:54,152 --> 00:36:55,860 i ara he de fer la mateixa decisió. 825 00:36:55,860 --> 00:36:58,387 I en realitat de peu just a davant de Lucas aquí si pogués, 826 00:36:58,387 --> 00:36:59,720 perquè aquest és el nostre bloc de notes. 827 00:36:59,720 --> 00:37:00,610 Llavors, qui segueix? 828 00:37:00,610 --> 00:37:05,000 Tenim Lucas amb el número dos o Chris nombre tres. 829 00:37:05,000 --> 00:37:07,460 Òbviament Lucas, nombre dos, pel que vénen aquí. 830 00:37:07,460 --> 00:37:11,270 >> Però la meva mà esquerra ara va a s'incrementa per apuntar a Darren, 831 00:37:11,270 --> 00:37:15,160 i aquí hi ha la clau de portar amb la fusió, que seguiré fent això, 832 00:37:15,160 --> 00:37:17,340 Òbviament, si vostè amable de seguir la lògica. 833 00:37:17,340 --> 00:37:19,670 Però les meves mans mai no són anirà cap enrere, 834 00:37:19,670 --> 00:37:23,861 el que significa que només alguna vegada vaig a mudar a l'esquerra amb el meu procés de fusió, 835 00:37:23,861 --> 00:37:26,360 i això serà clau per la nostra anàlisi en un moment. 836 00:37:26,360 --> 00:37:27,859 >> Així que ara anem a acabar això ràpidament. 837 00:37:27,859 --> 00:37:31,650 Així que 3 ve a continuació, després quatre ve a continuació, 838 00:37:31,650 --> 00:37:38,750 i ara cinc ve a continuació, i després sis, i 7, i, finalment, vuit. 839 00:37:38,750 --> 00:37:42,960 Se sent com l'algorisme més lent però, però no si en realitat 840 00:37:42,960 --> 00:37:45,510 executar en el mateix tipus de velocitat de rellotge, de manera que 841 00:37:45,510 --> 00:37:48,106 parlar, amb el mateix tic-tac del rellotge com abans. 842 00:37:48,106 --> 00:37:48,605 Per què? 843 00:37:48,605 --> 00:37:51,100 Bé, donem una mirar al resultat final. 844 00:37:51,100 --> 00:37:56,990 >> Tornem aquí, deixa tiri cap amunt una demostració visual 845 00:37:56,990 --> 00:37:59,030 del que acabem de fer. 846 00:37:59,030 --> 00:38:06,110 Apropar aquí, en aquesta pàgina aquí, dient Firefox 847 00:38:06,110 --> 00:38:08,200 que volem fer cua en aquesta caixa, anem a 848 00:38:08,200 --> 00:38:11,260 dir espècie de bombolla, amb la qual ara estem ben familiaritzats, 849 00:38:11,260 --> 00:38:14,130 ordenació per selecció, que és una altra un bastant senzill, 850 00:38:14,130 --> 00:38:18,250 i ara d'avui merge sort, el qual serà el nostre final culminant. 851 00:38:18,250 --> 00:38:21,530 La raó per la qual va prendre molt més temps aquí amb els éssers humans i em verbalment és, 852 00:38:21,530 --> 00:38:23,480 Òbviament, estic explicant cada pas. 853 00:38:23,480 --> 00:38:26,920 Però si simplement executa aquest, molt com ho vam fer espècie de bombolla i selecció 854 00:38:26,920 --> 00:38:30,890 espècie no només visualment, rellotge quant més eficient 855 00:38:30,890 --> 00:38:33,330 Aquest palanquejament divisió i conquesta 856 00:38:33,330 --> 00:38:39,150 pot ser quan s'aplica a un conjunt de dades que està ni tan sols mida de vuit, però fins i tot molt, 857 00:38:39,150 --> 00:38:39,970 molt més gran. 858 00:38:39,970 --> 00:38:44,585 Dono combinar espècie, un al costat de l' costat amb aquests altres algoritmes. 859 00:38:44,585 --> 00:38:56,364 860 00:38:56,364 --> 00:38:58,530 Això es posarà dolorosa ràpidament, i el final 861 00:38:58,530 --> 00:39:00,890 no és particularment culminant, que només acaben ordenats. 862 00:39:00,890 --> 00:39:05,280 Però la clau per dur és que mirar com més ràpid fusionar espècie 863 00:39:05,280 --> 00:39:08,110 era, llevat que pensis que sóc només una mica de jugar amb vostè. 864 00:39:08,110 --> 00:39:13,100 Si fem això per última vegada, Anem a recarregar això, tornem 865 00:39:13,100 --> 00:39:14,960 i triar espècie de bombolla, i només per diversió, 866 00:39:14,960 --> 00:39:17,330 anem a triar la inserció espècie, només per si de cas. 867 00:39:17,330 --> 00:39:20,020 I aquesta vegada de nou, anem a triï Fusió de classe i anem a 868 00:39:20,020 --> 00:39:21,595 de fet executar aquests costat a costat. 869 00:39:21,595 --> 00:39:24,140 870 00:39:24,140 --> 00:39:26,930 >> I no és, de fet, un cop de sort. 871 00:39:26,930 --> 00:39:31,140 El que he fet és efectivament tinc dividit la meva entrada a la meitat, de nou, 872 00:39:31,140 --> 00:39:32,240 i una altra, i una altra. 873 00:39:32,240 --> 00:39:35,590 I només hi ha tantes vegades que puguis dividir la seva entrada en meitats, esquerra 874 00:39:35,590 --> 00:39:36,240 i la dreta. 875 00:39:36,240 --> 00:39:39,425 Quina és la fórmula que ens seguim veient que descriu la divisió per la meitat 876 00:39:39,425 --> 00:39:41,050 una altra vegada, i una altra, i una altra, i una altra vegada? 877 00:39:41,050 --> 00:39:41,890 >> AUDIÈNCIA: log n. 878 00:39:41,890 --> 00:39:42,760 >> ALTAVEU: Inicieu sessió n. 879 00:39:42,760 --> 00:39:46,300 Però després hi ha un altre pas clau, aquest algorisme no és log n passos. 880 00:39:46,300 --> 00:39:48,992 Si només es log n passos, estaríem en el mateix problema 881 00:39:48,992 --> 00:39:51,200 com abans, on no podem estar Segur que tot està ordenat. 882 00:39:51,200 --> 00:39:54,480 Cal mirar mínimament en n elements per assegurar-se n elements s'ordenen, 883 00:39:54,480 --> 00:39:55,950 en cas contrari és un acte de fe. 884 00:39:55,950 --> 00:39:59,810 >> Pel que és registre mínimament n passos, però ¿Què passa amb aquest pas clau fusió 885 00:39:59,810 --> 00:40:04,370 on vaig combinar la meva meitat esquerra i dreta mitjà i va caminar per l'escenari? 886 00:40:04,370 --> 00:40:06,980 Quants passos és de fusionar? 887 00:40:06,980 --> 00:40:10,150 És n, però no ho vaig fer només fusionar el temps final. 888 00:40:10,150 --> 00:40:15,089 En cadascuna d'aquestes trucades niades, en cada d'aquestes fusions niats, jo encara ho van solucionar. 889 00:40:15,089 --> 00:40:18,380 Combinar aquests dos nois, a continuació, aquests dos nois, llavors aquests dos nois i així successivament. 890 00:40:18,380 --> 00:40:19,955 >> Així que em vaig donar la fusió de nou, i una altra. 891 00:40:19,955 --> 00:40:20,580 Quantes vegades? 892 00:40:20,580 --> 00:40:23,510 Així que cada vegada que divideix la llista a la meitat, em va fer una fusió. 893 00:40:23,510 --> 00:40:25,460 Dividiu la llista per la meitat, fer una fusió. 894 00:40:25,460 --> 00:40:28,570 Així que si dividint la llista es pot fer log n vegades, 895 00:40:28,570 --> 00:40:33,880 i la fusió en última instància porta a n passos, el que podria ser ara la part superior 896 00:40:33,880 --> 00:40:37,000 amb destinació en el funcionament temps del nostre algorisme? 897 00:40:37,000 --> 00:40:37,980 n log n. 898 00:40:37,980 --> 00:40:40,560 >> I de fet, això és el que que hem aconseguit aquí. 899 00:40:40,560 --> 00:40:44,650 Així que la sensació que es veu visualment quan aquestes tres coses corren costat a costat 900 00:40:44,650 --> 00:40:47,930 està n al quadrat contra n quadrat contra n log n. 901 00:40:47,930 --> 00:40:51,010 Què fonamentalment veurem, no només avui sinó en el futur, 902 00:40:51,010 --> 00:40:52,760 és molt, molt més ràpid. 903 00:40:52,760 --> 00:40:56,010 Un aplaudiment per a aquests nois, Vaig a recompensar amb boles d'estrès. 904 00:40:56,010 --> 00:41:00,260 Anem a aixecar la sessió aquí avui, i ens veiem dilluns. 905 00:41:00,260 --> 00:41:02,255