1 00:00:00,000 --> 00:00:00,990 2 00:00:00,990 --> 00:00:02,970 >> [Música tocando] 3 00:00:02,970 --> 00:00:10,400 4 00:00:10,400 --> 00:00:12,550 >> David J. Malan: Este é CS50. 5 00:00:12,550 --> 00:00:14,612 E este é o inicio da semana tres. 6 00:00:14,612 --> 00:00:16,820 Entón, nós temos unha morea de emocionante cousas para cubrir hoxe. 7 00:00:16,820 --> 00:00:20,160 Unha morea de oportunidades para voluntarios enriba do escenario. 8 00:00:20,160 --> 00:00:22,780 E, finalmente, é hoxe non sobre o código en todo. 9 00:00:22,780 --> 00:00:24,820 Pero é sobre ideas e trátase de algoritmos, 10 00:00:24,820 --> 00:00:28,420 e, de feito, traendo de volta algúns dos as leccións aprendidas a partir da semana cero, 11 00:00:28,420 --> 00:00:31,910 onde recall, nós introduciu esta monstruosidade. 12 00:00:31,910 --> 00:00:33,880 E préstamos inspiración sempre que, para comezar 13 00:00:33,880 --> 00:00:36,879 para resolver cada vez máis sofisticados problemas mediante algoritmos. 14 00:00:36,879 --> 00:00:38,420 Pero, primeiro, un par de anuncios. 15 00:00:38,420 --> 00:00:42,020 Entón un, se quere unirse Funcionarios e compañeiros de CS50 no xantar 16 00:00:42,020 --> 00:00:44,670 este venres, tanto aquí como no Cambridge, e en New Haven, 17 00:00:44,670 --> 00:00:48,060 por favor visita o curso de web, no que un URL se pode atopar. 18 00:00:48,060 --> 00:00:50,390 Charla este mércores non estar aquí en Sanders. 19 00:00:50,390 --> 00:00:53,610 Será en liña, de xeito sintonizar na web da CS50, 20 00:00:53,610 --> 00:00:55,850 aquí en Cambridge ou New Haven tamén. 21 00:00:55,850 --> 00:00:58,110 >> E, a continuación, axustar dous problema xa está nas súas mans. 22 00:00:58,110 --> 00:01:03,067 Se aínda non dicir aínda, permítame para ofrecer a suxestión de palabras fortes 23 00:01:03,067 --> 00:01:05,150 que, sobre todo agora, como o problema define anticipadamente, 24 00:01:05,150 --> 00:01:08,669 realmente quere comezar agora, se non borrifar un pouco a fin de semana ou antes 25 00:01:08,669 --> 00:01:10,710 cando por primeira vez saír Venres, porque vai 26 00:01:10,710 --> 00:01:14,380 descubrir que eles non son necesariamente quedando máis longos ou máis reto por 27 00:01:14,380 --> 00:01:14,950 SE. 28 00:01:14,950 --> 00:01:17,575 Eu creo que vai descubrir que, en xeral, tenden a levar máis ou menos 29 00:01:17,575 --> 00:01:18,892 en torno mesma cantidade de tempo. 30 00:01:18,892 --> 00:01:20,850 Pero é certamente depende no alumno, e 31 00:01:20,850 --> 00:01:22,880 depende da mentalidade co que se achega a el. 32 00:01:22,880 --> 00:01:24,910 Pero, invariablemente, está indo para realizar-se contra algunha parede, 33 00:01:24,910 --> 00:01:26,350 e está indo bater algún erro, e que é só 34 00:01:26,350 --> 00:01:27,950 non vai ser capaz de superar isto nalgún momento. 35 00:01:27,950 --> 00:01:31,380 E é moi valiosa para poder afastarse, volver ao día seguinte, 36 00:01:31,380 --> 00:01:35,286 ir ao horario de oficina, no post CS50 Discutir ou similar, para comezar realmente desbloqueado. 37 00:01:35,286 --> 00:01:36,160 Polo tanto, manter isto presente. 38 00:01:36,160 --> 00:01:40,830 Comezando canto antes é o mellor que podes facer. 39 00:01:40,830 --> 00:01:44,160 Entón, aquí é onde comezan a clase, máis a semana cero. 40 00:01:44,160 --> 00:01:47,441 E podemos obter un voluntario aquí para me axudar a atopar micrófonos? 41 00:01:47,441 --> 00:01:47,940 Aceptar. 42 00:01:47,940 --> 00:01:48,900 Levantando-se xa. 43 00:01:48,900 --> 00:01:50,080 Imos cara arriba. 44 00:01:50,080 --> 00:01:53,707 Creo que é como vai funcionar. 45 00:01:53,707 --> 00:01:54,415 Cal é o teu nome? 46 00:01:54,415 --> 00:01:55,570 ALAN ESTRADA: Alan Estrada. 47 00:01:55,570 --> 00:01:56,778 DAVID J. Malan: Alan Estrada. 48 00:01:56,778 --> 00:01:57,910 Imos cara arriba. 49 00:01:57,910 --> 00:01:58,619 Encantado de coñecerte. 50 00:01:58,619 --> 00:01:59,910 ALAN ESTRADA: Pracer en coñece-lo. 51 00:01:59,910 --> 00:02:02,772 DAVID J. Malan: E estaba aquí coa xente a semana cero, por suposto. 52 00:02:02,772 --> 00:02:03,028 ALAN ESTRADA: eu era. 53 00:02:03,028 --> 00:02:03,160 Eu era. 54 00:02:03,160 --> 00:02:05,868 >> DAVID J. Malan: Entón podería ir adiante e atopar a nós Mike Smith, 55 00:02:05,868 --> 00:02:08,639 tan rápido como pode? 56 00:02:08,639 --> 00:02:10,639 Tan rápido como se poida. 57 00:02:10,639 --> 00:02:13,756 Literalmente rasgando o problema en metade do que precisa. 58 00:02:13,756 --> 00:02:15,130 >> ALAN ESTRADA: Hum. 59 00:02:15,130 --> 00:02:17,380 DAVID J. Malan: Literalmente rasgando o problema á metade. 60 00:02:17,380 --> 00:02:20,210 61 00:02:20,210 --> 00:02:22,083 >> ALAN ESTRADA: Oh. 62 00:02:22,083 --> 00:02:22,583 Mm. 63 00:02:22,583 --> 00:02:23,300 Moi bo. 64 00:02:23,300 --> 00:02:23,700 >> DAVID J. Malan: Aceptar. 65 00:02:23,700 --> 00:02:24,200 Bo. 66 00:02:24,200 --> 00:02:24,701 Grazas. 67 00:02:24,701 --> 00:02:25,700 ALAN ESTRADA: Moi bo. 68 00:02:25,700 --> 00:02:26,210 Aceptar. 69 00:02:26,210 --> 00:02:27,610 >> DAVID J. Malan: E agora, vostede whittled abaixo 70 00:02:27,610 --> 00:02:29,320 a metade do tamaño do problema. 71 00:02:29,320 --> 00:02:31,267 Agora, estamos reducidos a un cuarto. 72 00:02:31,267 --> 00:02:33,475 Está pagando a atención sobre de que lado estamos mantendo? 73 00:02:33,475 --> 00:02:34,405 >> [Risas] 74 00:02:34,405 --> 00:02:35,970 >> ALAN ESTRADA: Si, eu penso-- 75 00:02:35,970 --> 00:02:37,594 >> DAVID J. Malan: Cal sección estamos? 76 00:02:37,594 --> 00:02:39,150 ALAN ESTRADA: silenciosa, entón. 77 00:02:39,150 --> 00:02:39,941 >> DAVID J. Malan: Aceptar. 78 00:02:39,941 --> 00:02:42,810 Pero Mike Smith vai para ser logo silenciosa. 79 00:02:42,810 --> 00:02:44,130 Assim-- 80 00:02:44,130 --> 00:02:48,180 >> [Risas] 81 00:02:48,180 --> 00:02:48,742 >> Todo ben. 82 00:02:48,742 --> 00:02:50,200 ALAN ESTRADA: Onde estamos buscando? 83 00:02:50,200 --> 00:02:52,049 DAVID J. Malan: Mike Smith. 84 00:02:52,049 --> 00:02:53,090 ALAN ESTRADA: Mike Smith. 85 00:02:53,090 --> 00:02:54,760 DAVID J. Malan: Agora estamos en cirúrxico. 86 00:02:54,760 --> 00:02:57,840 Agora, os médicos. 87 00:02:57,840 --> 00:02:58,340 Agora-- 88 00:02:58,340 --> 00:02:59,856 >> ALAN ESTRADA: Let's- imos con real. 89 00:02:59,856 --> 00:03:00,370 Real. 90 00:03:00,370 --> 00:03:00,970 >> DAVID J. Malan: Real. 91 00:03:00,970 --> 00:03:01,470 Aceptar. 92 00:03:01,470 --> 00:03:03,700 Se precisa de Real. 93 00:03:03,700 --> 00:03:05,250 Agora, o camiño que é Mike Smith? 94 00:03:05,250 --> 00:03:06,250 >> ALAN ESTRADA: Desta forma. 95 00:03:06,250 --> 00:03:07,333 >> DAVID J. Malan: Que xeito? 96 00:03:07,333 --> 00:03:08,240 ALAN ESTRADA: Espera. 97 00:03:08,240 --> 00:03:08,790 M é-- non? 98 00:03:08,790 --> 00:03:09,110 Comezamos com-- 99 00:03:09,110 --> 00:03:10,090 >> DAVID J. Malan: Yeah. 100 00:03:10,090 --> 00:03:10,650 Son deixados. 101 00:03:10,650 --> 00:03:11,430 Seu dereito. 102 00:03:11,430 --> 00:03:11,710 >> ALAN ESTRADA: Yeah. 103 00:03:11,710 --> 00:03:13,126 >> DAVID J. Malan: Entón Mike está aquí. 104 00:03:13,126 --> 00:03:13,990 ALAN ESTRADA: O que? 105 00:03:13,990 --> 00:03:14,665 >> [Risas] 106 00:03:14,665 --> 00:03:17,365 107 00:03:17,365 --> 00:03:18,330 >> Mal exemplo, rapaces. 108 00:03:18,330 --> 00:03:18,830 Desculpe. 109 00:03:18,830 --> 00:03:21,610 DAVID J. Malan: Isto vai ensinar saltar para fóra da súa cadeira. 110 00:03:21,610 --> 00:03:22,318 >> ALAN ESTRADA: Oh. 111 00:03:22,318 --> 00:03:22,890 Oh. 112 00:03:22,890 --> 00:03:23,390 Teño ti. 113 00:03:23,390 --> 00:03:24,670 Teño ti. 114 00:03:24,670 --> 00:03:25,170 Oh. 115 00:03:25,170 --> 00:03:25,669 Oh. 116 00:03:25,669 --> 00:03:26,812 Isto é-- OK, eu teño ti. 117 00:03:26,812 --> 00:03:27,520 Smith aquí? 118 00:03:27,520 --> 00:03:28,894 >> DAVID J. Malan: Smith, grazas. 119 00:03:28,894 --> 00:03:30,535 Polo tanto, vou seguir mirando cara arriba Smith? 120 00:03:30,535 --> 00:03:30,790 >> ALAN ESTRADA: Ah, si. 121 00:03:30,790 --> 00:03:31,340 Non, non, non. 122 00:03:31,340 --> 00:03:31,600 Oh, non. 123 00:03:31,600 --> 00:03:31,940 Iso é o meu. 124 00:03:31,940 --> 00:03:32,580 >> DAVID J. Malan: Oh, ten Smith. 125 00:03:32,580 --> 00:03:33,415 Aceptar. 126 00:03:33,415 --> 00:03:34,040 >> ALAN ESTRADA: Si, eu Smith ten aquí. 127 00:03:34,040 --> 00:03:34,700 Sentímolo, persoal. 128 00:03:34,700 --> 00:03:35,860 Eu penso que nós Michael-- Michael busca. 129 00:03:35,860 --> 00:03:36,550 Desculpe. 130 00:03:36,550 --> 00:03:37,550 >> DAVID J. Malan: É Aceptar. 131 00:03:37,550 --> 00:03:39,950 Todo ben, agora estamos en Paccini e Sons. 132 00:03:39,950 --> 00:03:41,242 >> ALAN ESTRADA: Paccini e fillos. 133 00:03:41,242 --> 00:03:43,158 DAVID J. Malan: Só e eu estamos en sobre este asunto. 134 00:03:43,158 --> 00:03:44,050 Aceptar. 135 00:03:44,050 --> 00:03:45,130 Atopar-nos Mike Smith. 136 00:03:45,130 --> 00:03:45,830 Smith. 137 00:03:45,830 --> 00:03:46,310 >> ALAN ESTRADA: Smith. 138 00:03:46,310 --> 00:03:46,750 >> DAVID J. Malan: Smith. 139 00:03:46,750 --> 00:03:47,728 Estamos en R para lixo. 140 00:03:47,728 --> 00:03:48,644 ALAN ESTRADA: Mala. 141 00:03:48,644 --> 00:03:50,096 Oh. 142 00:03:50,096 --> 00:03:52,480 Isto vai levar un pouco. 143 00:03:52,480 --> 00:03:54,340 >> [Risas] 144 00:03:54,340 --> 00:03:55,804 145 00:03:55,804 --> 00:03:56,720 DAVID J. Malan: Shoes. 146 00:03:56,720 --> 00:03:58,080 Estamos en zapatos. 147 00:03:58,080 --> 00:04:00,210 >> ALAN ESTRADA: Agora estamos gonna-- 148 00:04:00,210 --> 00:04:01,105 >> DAVID J. Malan: Nice. 149 00:04:01,105 --> 00:04:01,980 ALAN ESTRADA: Which-- 150 00:04:01,980 --> 00:04:03,620 [Risas] 151 00:04:03,620 --> 00:04:05,440 Oh, iso é gran. 152 00:04:05,440 --> 00:04:06,910 [Risas] 153 00:04:06,910 --> 00:04:08,380 154 00:04:08,380 --> 00:04:09,390 >> DAVID J. Malan: É Aceptar. 155 00:04:09,390 --> 00:04:11,365 >> ALAN ESTRADA: Oh, iso é bo. 156 00:04:11,365 --> 00:04:14,425 Eu non creo que eu vou ter amigos PSAT tras este. 157 00:04:14,425 --> 00:04:15,300 DAVID J. Malan: Good. 158 00:04:15,300 --> 00:04:16,078 Sporting. 159 00:04:16,078 --> 00:04:17,036 ALAN ESTRADA: Sporting. 160 00:04:17,036 --> 00:04:18,668 Hum, L, M, N, O, P. 161 00:04:18,668 --> 00:04:19,459 DAVID J. Malan: Aceptar. 162 00:04:19,459 --> 00:04:21,600 Entón, imos destruír o ao medio. 163 00:04:21,600 --> 00:04:22,270 Está ben. 164 00:04:22,270 --> 00:04:25,606 Iso acaba mal de ningún xeito, porque Mike Smith non será nas páxinas amarelas. 165 00:04:25,606 --> 00:04:26,430 >> ALAN ESTRADA: Aw. 166 00:04:26,430 --> 00:04:27,140 >> DAVID J. Malan: Non, é OK. 167 00:04:27,140 --> 00:04:28,930 Pero imos finxir que está nesta páxina. 168 00:04:28,930 --> 00:04:33,260 Entón, agora, tallou o problema abaixo a unha páxina, e atopamos Mike Smith. 169 00:04:33,260 --> 00:04:35,180 >> [Cheering] 170 00:04:35,180 --> 00:04:35,757 171 00:04:35,757 --> 00:04:36,340 Vale grazas. 172 00:04:36,340 --> 00:04:40,700 173 00:04:40,700 --> 00:04:41,200 Aceptar. 174 00:04:41,200 --> 00:04:43,646 Iso foi extraordinario. 175 00:04:43,646 --> 00:04:45,954 Pero aínda era máis rápido que busca lineal, 176 00:04:45,954 --> 00:04:47,870 en que comezan no inicio do libro, 177 00:04:47,870 --> 00:04:51,210 e pasamos o noso camiño de esquerda a dereita, finalmente, á procura de Mike Smith. 178 00:04:51,210 --> 00:04:53,540 E así, o libro de teléfono tiña quizais 1.000 páxinas, 179 00:04:53,540 --> 00:04:56,300 quizais levaría nos 10 ou máis bágoas páxina. 180 00:04:56,300 --> 00:04:59,380 >> Pero pode que panca tocou unha suposición 181 00:04:59,380 --> 00:05:03,602 durante toda a iso, o que é dicir que o libro de teléfono con antelación o que era? 182 00:05:03,602 --> 00:05:04,310 Audiencia: Ordenado. 183 00:05:04,310 --> 00:05:05,000 DAVID J. Malan: É clasificada. 184 00:05:05,000 --> 00:05:05,160 Non? 185 00:05:05,160 --> 00:05:07,909 É clasificados en orde alfabética, por iso, que todos eses nomes e números 186 00:05:07,909 --> 00:05:11,230 son clasificadas a partir da de un para o Z de, e en orde alfabética no medio. 187 00:05:11,230 --> 00:05:13,100 Pero hoxe, nós agora pedir a cuestión, ben, 188 00:05:13,100 --> 00:05:16,170 como fixo Verizon ou o teléfono empresa obtelo naquel estado? 189 00:05:16,170 --> 00:05:19,560 >> Porque é unha cousa para alavancar esa suposición, e, polo tanto, 190 00:05:19,560 --> 00:05:22,570 resolver un problema con un algoritmo de forma máis eficiente. 191 00:05:22,570 --> 00:05:24,900 Pero nunca realmente pediu a semana cero, así, 192 00:05:24,900 --> 00:05:27,790 canto custou Verizon ou outra persoa 193 00:05:27,790 --> 00:05:29,620 para obter esta lista telefónica na orde de clasificación? 194 00:05:29,620 --> 00:05:29,780 >> Non? 195 00:05:29,780 --> 00:05:31,529 Non importa se mirando cara arriba Mike Smith 196 00:05:31,529 --> 00:05:35,190 é super rápido, se leva un ano para clasificar as páxinas inicialmente. 197 00:05:35,190 --> 00:05:35,690 Non? 198 00:05:35,690 --> 00:05:38,620 Pode moi ben peneirar a través dun libro de teléfono ao azar, 199 00:05:38,620 --> 00:05:40,690 se vai ser super caro para clasificalos lo. 200 00:05:40,690 --> 00:05:42,350 Entón, se podemos ter outro voluntario. 201 00:05:42,350 --> 00:05:46,350 Imos dar un ollo aquí enriba como nós might-- veña up-- como 202 00:05:46,350 --> 00:05:48,100 poderiamos ir sobre a clasificación destes. 203 00:05:48,100 --> 00:05:51,990 >> E se, de feito, podería Jordan unirse a nós aquí enriba do escenario. 204 00:05:51,990 --> 00:05:55,100 Veña-se só por un momento. 205 00:05:55,100 --> 00:05:56,359 Cal é o teu nome? 206 00:05:56,359 --> 00:05:57,150 CAROLINE: Caroline. 207 00:05:57,150 --> 00:05:58,691 DAVID J. Malan: Caroline, imos cara arriba. 208 00:05:58,691 --> 00:06:02,070 E vai ser uniuse por min e Xordán aquí. 209 00:06:02,070 --> 00:06:03,800 Caroline, grazas. 210 00:06:03,800 --> 00:06:04,300 Todo ben. 211 00:06:04,300 --> 00:06:08,330 Entón o que temos aquí para Caroline ten 26 libros azuis 212 00:06:08,330 --> 00:06:10,747 FAS que utiliza para administrar certos exames finais. 213 00:06:10,747 --> 00:06:13,330 Estes están quedando difíciles de atopar, pero o que fixemos con antelación 214 00:06:13,330 --> 00:06:15,800 é que poñemos o nome de alguén na parte de diante de cada unha delas, 215 00:06:15,800 --> 00:06:18,133 pero mantivemos lo simple, a continuación, pór para fóra os nomes completos. 216 00:06:18,133 --> 00:06:22,720 Por iso, sería poñer a persoa co nome G, D, J, B, todo o camiño da a Z, 217 00:06:22,720 --> 00:06:24,090 pero eles están en orde aleatoria. 218 00:06:24,090 --> 00:06:26,890 E por iso, se faría, falando seu camiño a través do problema como 219 00:06:26,890 --> 00:06:31,620 facelo, pode ir adiante e Ordenar estes para nós, da a Z. 220 00:06:31,620 --> 00:06:34,070 >> Audiencia: OK, entón L é como, no medio. 221 00:06:34,070 --> 00:06:35,050 C está comezando. 222 00:06:35,050 --> 00:06:42,410 B. J antes L. B, Q. 223 00:06:42,410 --> 00:06:45,140 >> DAVID J. Malan: Manteña esa penso por un segundo. 224 00:06:45,140 --> 00:06:48,910 Porque doutra forma, esta é só interesante para ti, eu, e Jordan. 225 00:06:48,910 --> 00:06:49,724 Alí imos nós. 226 00:06:49,724 --> 00:06:50,640 Audiencia: [inaudível]. 227 00:06:50,640 --> 00:06:57,299 R. 228 00:06:57,299 --> 00:06:58,090 DAVID J. Malan: Aceptar. 229 00:06:58,090 --> 00:06:59,310 Que estás facendo? 230 00:06:59,310 --> 00:07:01,730 >> CAROLINE: M vén despois O. 231 00:07:01,730 --> 00:07:02,564 >> DAVID J. Malan: Aceptar. 232 00:07:02,564 --> 00:07:03,064 >> CAROLINE: O. 233 00:07:03,064 --> 00:07:04,120 DAVID J. Malan: O, Bo. 234 00:07:04,120 --> 00:07:04,970 >> CAROLINE: E. 235 00:07:04,970 --> 00:07:06,730 >> DAVID J. Malan: E, F. Si. 236 00:07:06,730 --> 00:07:07,620 >> CAROLINE: T, U, V 237 00:07:07,620 --> 00:07:10,689 >> DAVID J. Malan: V, T, U, V. Polo tanto, parece que está making-- continuar. 238 00:07:10,689 --> 00:07:12,730 Parece que está facendo unha gran pila aquí, 239 00:07:12,730 --> 00:07:13,910 e tipo de unha gran pila de alí. 240 00:07:13,910 --> 00:07:16,230 Así, a primeira parte do alfabeto, segunda metade do alfabeto. 241 00:07:16,230 --> 00:07:16,460 Aceptar. 242 00:07:16,460 --> 00:07:16,960 Bo. 243 00:07:16,960 --> 00:07:19,680 Tipo de dividir o problema en dúas partes. 244 00:07:19,680 --> 00:07:21,771 M, N, X. Si. 245 00:07:21,771 --> 00:07:22,270 CAROLINE: K. 246 00:07:22,270 --> 00:07:22,980 DAVID J. Malan: Aceptar. 247 00:07:22,980 --> 00:07:25,070 K. Entón está tipo de selección Los un despois do outro, 248 00:07:25,070 --> 00:07:27,620 poñelas á esquerda ou dereita, ou Z está pasando no chan. 249 00:07:27,620 --> 00:07:28,012 Aceptar. 250 00:07:28,012 --> 00:07:29,190 >> CAROLINE: Z está pasando no chan. 251 00:07:29,190 --> 00:07:29,360 >> DAVID J. Malan: Aceptar. 252 00:07:29,360 --> 00:07:30,920 Y pasa no chan. 253 00:07:30,920 --> 00:07:31,735 Agora podemos poñer X. 254 00:07:31,735 --> 00:07:32,409 >> CAROLINE: G. 255 00:07:32,409 --> 00:07:33,700 DAVID J. Malan: G de ir á esquerda. 256 00:07:33,700 --> 00:07:36,017 S está indo ben. 257 00:07:36,017 --> 00:07:37,642 Todo ben, un vai todo o camiño á esquerda. 258 00:07:37,642 --> 00:07:38,790 >> Caroline: A, B, C, D. 259 00:07:38,790 --> 00:07:39,873 >> DAVID J. Malan: Agora é bo. 260 00:07:39,873 --> 00:07:43,260 Temos A, B, C. W de ir alí en baixo. 261 00:07:43,260 --> 00:07:45,566 Todo ben, T. 262 00:07:45,566 --> 00:07:46,611 >> CAROLINE: H, I, J. 263 00:07:46,611 --> 00:07:47,860 DAVID J. Malan: H, I, J. Boa. 264 00:07:47,860 --> 00:07:49,160 CAROLINE: No centro, estou gonna-- 265 00:07:49,160 --> 00:07:50,000 DAVID J. Malan: Aceptar. 266 00:07:50,000 --> 00:07:52,375 Entón, agora, imos tipo de mesturar estas varias pilas. 267 00:07:52,375 --> 00:08:00,730 Entón, da a C, entón eu vexo D, e E, e F, e G, e H, I e agradable. 268 00:08:00,730 --> 00:08:05,540 J, K. E entón, esa pila é de cabeza para abaixo, pero iso é OK. 269 00:08:05,540 --> 00:08:06,040 Claro. 270 00:08:06,040 --> 00:08:07,240 Podemos cortar algúns cantos. 271 00:08:07,240 --> 00:08:07,950 Aceptar. 272 00:08:07,950 --> 00:08:10,530 E entón necesitamos W, X, Y, Z 273 00:08:10,530 --> 00:08:11,250 >> CAROLINE: Yeah. 274 00:08:11,250 --> 00:08:11,880 >> DAVID J. Malan: Excelente. 275 00:08:11,880 --> 00:08:14,122 Así, un gran grazas a Caroline para clasificar estes. 276 00:08:14,122 --> 00:08:15,030 >> [Cheering] 277 00:08:15,030 --> 00:08:17,287 >> Grazas. 278 00:08:17,287 --> 00:08:18,120 Moitas grazas. 279 00:08:18,120 --> 00:08:22,910 Entón agora imos considerar por un momento como Caroline pasou facendo o que, 280 00:08:22,910 --> 00:08:26,040 e exactamente o que nós foron capaces a-- como nós 281 00:08:26,040 --> 00:08:28,409 foron capaces de resolver este problema cando estabamos só 282 00:08:28,409 --> 00:08:29,950 dado unha chea de entradas aleatorias. 283 00:08:29,950 --> 00:08:31,610 >> Ben, parece que hai foi un pouco de un sistema de alí? 284 00:08:31,610 --> 00:08:32,110 Dereita. 285 00:08:32,110 --> 00:08:34,495 Así, as primeiras cartas no alfabeto, ela 286 00:08:34,495 --> 00:08:37,120 era poñer á esquerda, eo cartas posteriores no alfabeto, 287 00:08:37,120 --> 00:08:38,270 ela estaba poñendo a dereita. 288 00:08:38,270 --> 00:08:40,500 E así que ela atopou algunhas cartas proximais, queridos 289 00:08:40,500 --> 00:08:43,124 que vaia á dereita xunto ao outro, ía poñer-los en orde. 290 00:08:43,124 --> 00:08:46,750 E entón nós medio que estes pequenos pilas de entradas ordenadas produciron. 291 00:08:46,750 --> 00:08:50,540 >> E así que é moi parecido ao que a maioría de nós seres humanos faría. 292 00:08:50,540 --> 00:08:53,530 Queremos especie de peneirar, e nós medio que temos un mecanismo. 293 00:08:53,530 --> 00:08:56,930 Pero pode ser difícil de escribir -o abaixo nunha fórmula de per si. 294 00:08:56,930 --> 00:08:59,010 El Sentín un pouco máis orgánico que iso. 295 00:08:59,010 --> 00:09:02,560 Entón, imos ver se podemos agora conectado O problema co menor número de entradas. 296 00:09:02,560 --> 00:09:05,170 >> No canto de 26, imos facer algo moito menos 297 00:09:05,170 --> 00:09:09,890 con só dicir, sete, atrás estas portas, por así dicir. 298 00:09:09,890 --> 00:09:11,300 Hai só sete números? 299 00:09:11,300 --> 00:09:15,240 E se o obxectivo agora en man é atopar un valor, 300 00:09:15,240 --> 00:09:17,850 imos ver como eficaz podemos facer sobre este asunto. 301 00:09:17,850 --> 00:09:22,460 E imos ver se podemos agora comezar a aplicar algúns números, 302 00:09:22,460 --> 00:09:26,310 ou algunhas fórmulas coas que para describir a eficiencia do noso libro de teléfono 303 00:09:26,310 --> 00:09:31,060 algoritmo, o noso algoritmo libro exame, e de xeito máis xeral, busca de información. 304 00:09:31,060 --> 00:09:34,770 >> Entón, para iso, deixe-me ir adiante, e na pantalla táctil aquí, 305 00:09:34,770 --> 00:09:41,100 poñer un navegador web que ten exactamente eses sete portas. 306 00:09:41,100 --> 00:09:46,670 E se nós puidésemos adquirir outro voluntariamente para vir ata aquí, 307 00:09:46,670 --> 00:09:48,480 Engada esas mesmas portas por aquí. 308 00:09:48,480 --> 00:09:49,170 Voluntario rápido. 309 00:09:49,170 --> 00:09:51,130 >> Este um-- demos van a unha máis rápida e máis rápido agora. 310 00:09:51,130 --> 00:09:51,600 Imos cara a abaixo. 311 00:09:51,600 --> 00:09:52,308 Cal é o teu nome? 312 00:09:52,308 --> 00:09:53,040 Trevor: Trevor. 313 00:09:53,040 --> 00:09:53,998 >> DAVID J. Malan: Trevor? 314 00:09:53,998 --> 00:09:55,770 Todo ben, Trevor, imos alí abaixo. 315 00:09:55,770 --> 00:09:59,212 Entón Trevor ofreceuse aquí para facer un problema semellante, pero un que é 316 00:09:59,212 --> 00:10:02,170 de ámbito máis restrinxido, e que está a suceder para permitir-nos para tentar formalizar agora 317 00:10:02,170 --> 00:10:03,970 o proceso de selección de eses números. 318 00:10:03,970 --> 00:10:05,500 >> Entón Trevor, pracer en coñece-lo. 319 00:10:05,500 --> 00:10:08,720 Entón aquí é unha matriz, por así falar, unha lista de sete portas. 320 00:10:08,720 --> 00:10:10,327 Dalle atopar-nos no número 50. 321 00:10:10,327 --> 00:10:12,410 E, a continuación, despois do feito, di-nos como o atopou. 322 00:10:12,410 --> 00:10:19,124 323 00:10:19,124 --> 00:10:20,040 Debe ser-- todo ben. 324 00:10:20,040 --> 00:10:21,945 Si, este é o único aquí? 325 00:10:21,945 --> 00:10:24,680 Uh-oh. 326 00:10:24,680 --> 00:10:25,560 Aceptar. 327 00:10:25,560 --> 00:10:26,680 Premeu esa. 328 00:10:26,680 --> 00:10:28,690 Bo. 329 00:10:28,690 --> 00:10:29,780 >> E boa. 330 00:10:29,780 --> 00:10:30,970 Agora fai clic esta. 331 00:10:30,970 --> 00:10:34,060 E deixe-me dar-lle o micrófono, de xeito que telo en só un momento. 332 00:10:34,060 --> 00:10:37,000 Dalle prema o xunto que pretende. 333 00:10:37,000 --> 00:10:39,812 Si, é bo. 334 00:10:39,812 --> 00:10:41,020 Trevor: Podo desmarque a porta? 335 00:10:41,020 --> 00:10:42,620 DAVID J. Malan: Non, non pode desmarque. 336 00:10:42,620 --> 00:10:43,119 Trevor: Aceptar. 337 00:10:43,119 --> 00:10:43,974 Este. 338 00:10:43,974 --> 00:10:45,640 DAVID J. Malan: Onde quere ir? 339 00:10:45,640 --> 00:10:46,410 Cal? 340 00:10:46,410 --> 00:10:47,230 >> Trevor: Que un. 341 00:10:47,230 --> 00:10:48,042 >> DAVID J. Malan: Non. 342 00:10:48,042 --> 00:10:48,450 >> Trevor: Aceptar. 343 00:10:48,450 --> 00:10:48,735 Este. 344 00:10:48,735 --> 00:10:49,020 >> DAVID J. Malan: Si. 345 00:10:49,020 --> 00:10:49,700 Isto foi bo. 346 00:10:49,700 --> 00:10:50,380 Todo ben. 347 00:10:50,380 --> 00:10:53,900 Entón, cal foi o seu algoritmo ou procedemento para facelo, Trevor? 348 00:10:53,900 --> 00:10:56,149 >> Trevor: Eu só pasei portas ata que eu atope a 50. 349 00:10:56,149 --> 00:10:56,940 DAVID J. Malan: Aceptar. 350 00:10:56,940 --> 00:10:58,150 Excelente algoritmo. 351 00:10:58,150 --> 00:10:59,540 Entón, iso é bo. 352 00:10:59,540 --> 00:11:03,120 Porque, en realidade, se eu revelar o que é detrás destas dúas outras portas, o que 353 00:11:03,120 --> 00:11:06,954 imos atopar aquí é que só temos entrada aleatoria. 354 00:11:06,954 --> 00:11:08,870 Así, foi realmente como así como se podería obter. 355 00:11:08,870 --> 00:11:12,509 E, de feito, ten mellor que exhaustivamente buscando todo o conxunto, 356 00:11:12,509 --> 00:11:15,300 porque sería realmente azaroso se tivese alcanzado o número 357 00:11:15,300 --> 00:11:16,604 50 no último porto. 358 00:11:16,604 --> 00:11:18,520 Pero o que en vez deulle unha hipótese. 359 00:11:18,520 --> 00:11:20,630 Supoña que classifico todos estas portas ao redor, 360 00:11:20,630 --> 00:11:23,500 de xeito que ten a números clasificados este tempo, 361 00:11:23,500 --> 00:11:29,730 pero esta vez é realmente un diferente-- este tempo, 362 00:11:29,730 --> 00:11:32,640 é realmente clasificadas para ti. 363 00:11:32,640 --> 00:11:35,380 E agora a meta na man é acadar o número de 50. 364 00:11:35,380 --> 00:11:36,090 >> Trevor: Aceptar. 365 00:11:36,090 --> 00:11:37,670 >> DAVID J. Malan: Cal é seu algoritmo vai ser? 366 00:11:37,670 --> 00:11:39,628 >> Trevor: Ben, se é clasificadas, é calquera que vai 367 00:11:39,628 --> 00:11:42,710 para ser-- maior para o maior, descendente, vai ser o primeiro, 368 00:11:42,710 --> 00:11:44,751 ou se é o contrario, será a última. 369 00:11:44,751 --> 00:11:48,897 Entón só vou tocar esta porta, e a continuación, pode tocar a última porta. 370 00:11:48,897 --> 00:11:49,980 DAVID J. Malan: Excelente. 371 00:11:49,980 --> 00:11:50,270 Todo ben. 372 00:11:50,270 --> 00:11:51,150 Así, atopamos o número 50. 373 00:11:51,150 --> 00:11:52,970 Así, logo que soubese eles foron ordenados, nós 374 00:11:52,970 --> 00:11:55,040 foron capaces de aproveitar esta suposición. 375 00:11:55,040 --> 00:11:57,040 Entón, eles están moi parecido a exemplo do libro de teléfono. 376 00:11:57,040 --> 00:11:59,540 Así que ten, mesmo con un pequeno problema como este, 377 00:11:59,540 --> 00:12:02,380 súas entradas pre-clasificados, podemos realmente atopar o valor indiscutibelmente 378 00:12:02,380 --> 00:12:03,130 de forma máis eficiente. 379 00:12:03,130 --> 00:12:05,800 >> E eu non lle dixen que era clasificadas pequeno a grande, ou grande a pequeno, 380 00:12:05,800 --> 00:12:08,080 e por iso era moi razoable para comezar nunha extremidade ou outro 381 00:12:08,080 --> 00:12:09,750 para realmente atopar ese valor obxecto de aprendizaxe. 382 00:12:09,750 --> 00:12:11,400 Por iso, gracias ao Trevor tamén. 383 00:12:11,400 --> 00:12:13,260 E eu vou propose-- ben feito. 384 00:12:13,260 --> 00:12:16,960 Temos un pequeno clip, de feito, que está entre os nosos momentos favoritos en CS50, 385 00:12:16,960 --> 00:12:19,700 polo que, ás veces, estas demostracións non chegan a ir de acordo co plan. 386 00:12:19,700 --> 00:12:22,050 E, de feito agora, eu tirou a interface incorrecta 387 00:12:22,050 --> 00:12:23,508 que utilizar a pantalla táctil. 388 00:12:23,508 --> 00:12:24,660 Así, foi culpa miña alí. 389 00:12:24,660 --> 00:12:26,600 >> Entón, iso vai facer para clip do próximo ano como 390 00:12:26,600 --> 00:12:28,570 a razón pola que eu estaba facendo clic no meu propio pantalla. 391 00:12:28,570 --> 00:12:31,390 Pero imos dar un ollo rápida para o que pasou o ano pasado 392 00:12:31,390 --> 00:12:34,770 con Jay, que xurdiu, moi como Trevor aquí, ofreceu-se, 393 00:12:34,770 --> 00:12:39,380 e neste clip curto, podes ver como esta mesma demostración non fixo moito 394 00:12:39,380 --> 00:12:41,074 revelar as mesmas leccións aprendidas. 395 00:12:41,074 --> 00:12:41,740 [REPRODUCIÓN DE VIDEO] 396 00:12:41,740 --> 00:12:45,360 -Todo Que quero que faga agora para atopar a min, e para nós, 397 00:12:45,360 --> 00:12:51,674 realmente, o número 50 un paso de cada vez. 398 00:12:51,674 --> 00:12:52,450 >> -O Número 50? 399 00:12:52,450 --> 00:12:53,190 >> -O Número 50. 400 00:12:53,190 --> 00:12:55,356 E pode revelar o que é detrás de cada unha destas portas 401 00:12:55,356 --> 00:12:58,540 simplemente por tocar cun dedo. 402 00:12:58,540 --> 00:13:00,910 Droga. 403 00:13:00,910 --> 00:13:02,870 >> [Risas] 404 00:13:02,870 --> 00:13:03,806 >> [FIN DE REPRODUCIÓN] 405 00:13:03,806 --> 00:13:05,430 DAVID J. Malan: Así que foi moi ben. 406 00:13:05,430 --> 00:13:06,796 Estas foron as portas sen clasificar. 407 00:13:06,796 --> 00:13:08,670 E Jay, por suposto, penso todo moi rápido. 408 00:13:08,670 --> 00:13:12,910 Trevor fixo un traballo moito mellor en termos de un momento de aprendizaxe, 409 00:13:12,910 --> 00:13:15,850 por así dicir, este ano, en levando máis tempo para atopalo. 410 00:13:15,850 --> 00:13:17,950 Claro, entón nós demos Jay unha segunda oportunidade, 411 00:13:17,950 --> 00:13:20,320 polo cal nós ordenamos as portas, así como fixemos para o Trevor, 412 00:13:20,320 --> 00:13:22,300 e Trevor fixo super-ben esta vez. 413 00:13:22,300 --> 00:13:26,124 Pero Jay fixo metade tan axiña. 414 00:13:26,124 --> 00:13:26,790 [REPRODUCIÓN DE VIDEO] 415 00:13:26,790 --> 00:13:29,650 -O Obxectivo agora é tamén atopar-nos no número 50, 416 00:13:29,650 --> 00:13:33,030 pero facelo a través de algoritmos, e di-nos como está indo sobre el. 417 00:13:33,030 --> 00:13:33,660 >> -OK. 418 00:13:33,660 --> 00:13:35,604 >> -E Se atopalo, manteña a película. 419 00:13:35,604 --> 00:13:37,228 Se non atopalo, dá-lo de volta. 420 00:13:37,228 --> 00:13:38,044 >> -Man. 421 00:13:38,044 --> 00:13:38,860 >> -Oh! 422 00:13:38,860 --> 00:13:40,800 >> - [Inaudível] Aceptar. 423 00:13:40,800 --> 00:13:46,236 Entón, eu estou indo a comprobar os extremos primeiro para determinar se there's-- Oh. 424 00:13:46,236 --> 00:13:48,646 >> [Aplausos] 425 00:13:48,646 --> 00:13:53,948 426 00:13:53,948 --> 00:13:55,729 >> [FIN DE REPRODUCIÓN] 427 00:13:55,729 --> 00:13:56,520 DAVID J. Malan: Aceptar. 428 00:13:56,520 --> 00:13:59,760 Entón selección portas claramente conduce a unha maior eficiencia. 429 00:13:59,760 --> 00:14:01,680 E así, dúas veces máis rápido é o que eu quería dicir alí. 430 00:14:01,680 --> 00:14:03,270 E así Jay tivo sorte dúas veces. 431 00:14:03,270 --> 00:14:06,685 E tamén tivo sorte naquela última ano, eu pedín algúns discos Blu-ray 432 00:14:06,685 --> 00:14:07,560 para realmente dar para fóra. 433 00:14:07,560 --> 00:14:09,768 Sinto moito este ano, non teñen o mesmo, Trevor. 434 00:14:09,768 --> 00:14:11,540 Pero mellor aínda era hai uns anos. 435 00:14:11,540 --> 00:14:14,820 E algúns de vostedes poden saber iso compañeiro, Sean, que cando estaba na CS50, 436 00:14:14,820 --> 00:14:17,780 foi desafiado coa exacta mesmo problema, aínda que en SD, 437 00:14:17,780 --> 00:14:19,360 como podes ver en breve, de volta ao día. 438 00:14:19,360 --> 00:14:22,622 E vai descubrir que non só el levar un pouco máis do que Jay, 439 00:14:22,622 --> 00:14:25,580 un pouco máis do que Trevor, foi realmente esta oportunidade marabillosa 440 00:14:25,580 --> 00:14:29,820 involucrarse case todos no multitude a la Prezo Correcto, incentivando 441 00:14:29,820 --> 00:14:31,889 Lo a atopar o número que estabamos a buscar. 442 00:14:31,889 --> 00:14:32,930 Imos. dar un ollo rápida. 443 00:14:32,930 --> 00:14:33,320 >> [REPRODUCIÓN DE VIDEO] 444 00:14:33,320 --> 00:14:33,820 >> -OK. 445 00:14:33,820 --> 00:14:36,680 Polo tanto, a súa tarefa aquí, Sean, é o seguinte. 446 00:14:36,680 --> 00:14:40,860 Eu oculto detrás destas portas o número sete. 447 00:14:40,860 --> 00:14:45,120 Pero afastada, nalgunhas desas portas así como outros son números negativos. 448 00:14:45,120 --> 00:14:47,500 E o seu obxectivo é pensar desta liña superior de números 449 00:14:47,500 --> 00:14:50,390 como só unha matriz, ou só secuencia de anacos de papel 450 00:14:50,390 --> 00:14:51,510 con números detrás deles. 451 00:14:51,510 --> 00:14:55,540 E o seu obxectivo é, usando só o principio matriz aquí, atopar-me o número sete. 452 00:14:55,540 --> 00:14:58,570 E nós estamos indo entón para criticar como vai facer sobre iso. 453 00:14:58,570 --> 00:14:59,070 -Todo ben. 454 00:14:59,070 --> 00:15:00,850 -Find-Nos número sete, por favor. 455 00:15:00,850 --> 00:15:10,500 456 00:15:10,500 --> 00:15:11,000 Non. 457 00:15:11,000 --> 00:15:15,050 458 00:15:15,050 --> 00:15:18,550 Cinco, 19, 13. 459 00:15:18,550 --> 00:15:22,240 460 00:15:22,240 --> 00:15:24,770 >> [Risas] 461 00:15:24,770 --> 00:15:25,910 >> Non é unha pregunta capciosa. 462 00:15:25,910 --> 00:15:29,410 463 00:15:29,410 --> 00:15:29,910 Unha. 464 00:15:29,910 --> 00:15:33,218 465 00:15:33,218 --> 00:15:34,695 >> [Risas] 466 00:15:34,695 --> 00:15:37,861 Neste punto, a súa puntuación non é moi bo, entón pode moi ben continuar. 467 00:15:37,861 --> 00:15:40,610 468 00:15:40,610 --> 00:15:41,110 Tres. 469 00:15:41,110 --> 00:15:43,890 470 00:15:43,890 --> 00:15:45,378 >> [Risas] 471 00:15:45,378 --> 00:15:46,370 472 00:15:46,370 --> 00:15:47,774 >> Vai adiante. 473 00:15:47,774 --> 00:15:50,690 Francamente, eu non podo axudar, pero pregunta o que está mesmo a pensar, assim-- 474 00:15:50,690 --> 00:15:51,959 >> [Risas] 475 00:15:51,959 --> 00:15:53,229 476 00:15:53,229 --> 00:15:55,020 Só a liña superior, para ten tres esquerda. 477 00:15:55,020 --> 00:15:56,200 Entón, atopar-me sete. 478 00:15:56,200 --> 00:15:59,700 479 00:15:59,700 --> 00:16:02,167 >> [Risas] 480 00:16:02,167 --> 00:16:14,870 481 00:16:14,870 --> 00:16:15,370 17. 482 00:16:15,370 --> 00:16:25,675 483 00:16:25,675 --> 00:16:26,946 Sete. 484 00:16:26,946 --> 00:16:28,780 >> [Aplausos] 485 00:16:28,780 --> 00:16:29,426 >> Todo ben. 486 00:16:29,426 --> 00:16:30,360 >> [FIN DE REPRODUCIÓN] 487 00:16:30,360 --> 00:16:31,840 >> DAVID J. Malan: para que puidésemos asistir a estes todo o día. 488 00:16:31,840 --> 00:16:34,090 E, por suposto, algúns dos demos deste ano quizais 489 00:16:34,090 --> 00:16:36,330 agora vai acabar o próximo video do ano tamén. 490 00:16:36,330 --> 00:16:39,040 Entón agora imos realmente centrar os algoritmos 491 00:16:39,040 --> 00:16:42,140 aquí, para ver se non podemos agora comezar a formalizar 492 00:16:42,140 --> 00:16:46,650 como podemos ir sobre a obtención dos nosos datos a este estado que está clasificado, 493 00:16:46,650 --> 00:16:50,054 de xeito que, en definitiva, podemos, de feito, buscala de xeito máis eficiente. 494 00:16:50,054 --> 00:16:52,470 E aínda que nós imos usar conxuntos de datos relativamente pequeno, 495 00:16:52,470 --> 00:16:54,511 como a que oito números temos aquí no cadro, 496 00:16:54,511 --> 00:16:58,230 en definitiva, podería aplicar estas mesmas ideas 1.000 entradas, un millón de entradas, 497 00:16:58,230 --> 00:17:02,100 4 millóns de insumos, porque os algoritmos van ser fundamentalmente o mesmo. 498 00:17:02,100 --> 00:17:05,359 >> E así, este é o noso último oportunidade para os voluntarios de hoxe, 499 00:17:05,359 --> 00:17:09,790 pero quizais o máis afectado, para o que necesitamos oito voluntarios 500 00:17:09,790 --> 00:17:12,960 para subir e pé connosco a través do proceso de selección que será en breve 501 00:17:12,960 --> 00:17:15,212 ser sobre estes postos de música aquí. 502 00:17:15,212 --> 00:17:16,170 Déixeme comezar a volver aquí. 503 00:17:16,170 --> 00:17:19,692 >> Entón, un no verde turquoise-- é? 504 00:17:19,692 --> 00:17:21,130 Está cometendo? 505 00:17:21,130 --> 00:17:21,630 Dous. 506 00:17:21,630 --> 00:17:23,069 Imos cara a abaixo. 507 00:17:23,069 --> 00:17:23,569 Aceptar. 508 00:17:23,569 --> 00:17:24,420 Tres. 509 00:17:24,420 --> 00:17:25,400 Four. 510 00:17:25,400 --> 00:17:27,247 Imos me-- OK, cinco. 511 00:17:27,247 --> 00:17:28,830 Está a ser nomeado polo seu amigo. 512 00:17:28,830 --> 00:17:31,340 Seis, sete, e oito. 513 00:17:31,340 --> 00:17:32,130 Imos cara arriba. 514 00:17:32,130 --> 00:17:32,630 Todo ben. 515 00:17:32,630 --> 00:17:33,190 Moitas grazas. 516 00:17:33,190 --> 00:17:33,689 Imos cara arriba. 517 00:17:33,689 --> 00:17:34,790 Imos cara arriba. 518 00:17:34,790 --> 00:17:35,330 >> Todo ben. 519 00:17:35,330 --> 00:17:38,890 Entón o que temos e iso aqui-- está entre os máis torpes, 520 00:17:38,890 --> 00:17:42,390 xa que este vai esixir que humor Miña só un pouco de tempo. 521 00:17:42,390 --> 00:17:43,442 Ten que ser o número un. 522 00:17:43,442 --> 00:17:44,150 Cal é o teu nome? 523 00:17:44,150 --> 00:17:44,610 >> Annan: Annan. 524 00:17:44,610 --> 00:17:45,526 >> DAVID J. Malan: Annan. 525 00:17:45,526 --> 00:17:46,092 David. 526 00:17:46,092 --> 00:17:46,800 Cal é o teu nome? 527 00:17:46,800 --> 00:17:47,140 >> JOSÉ: José. 528 00:17:47,140 --> 00:17:49,190 >> DAVID J. Malan: José, é o número dous. 529 00:17:49,190 --> 00:17:52,260 >> SERENA: Serena, número tres. 530 00:17:52,260 --> 00:17:53,722 Stefan, o número catro. 531 00:17:53,722 --> 00:17:54,430 CYNTHIA: Cynthia. 532 00:17:54,430 --> 00:17:57,548 DAVID J. Malan: Cynthia, número cinco. 533 00:17:57,548 --> 00:17:58,452 [Inaudível] 534 00:17:58,452 --> 00:17:59,618 DAVID J. Malan: [inaudível]. 535 00:17:59,618 --> 00:18:00,391 David, número seis. 536 00:18:00,391 --> 00:18:00,890 Matt: Matt. 537 00:18:00,890 --> 00:18:02,160 DAVID J. Malan: número de Matt sete. 538 00:18:02,160 --> 00:18:02,850 E? 539 00:18:02,850 --> 00:18:03,210 >> WAVERLY: Waverly. 540 00:18:03,210 --> 00:18:04,470 >> DAVID J. Malan: Waverly, número oito. 541 00:18:04,470 --> 00:18:04,970 Todo ben. 542 00:18:04,970 --> 00:18:06,510 Se could-- berros. 543 00:18:06,510 --> 00:18:08,820 Se todo, como o seu primeiro reto, hai 544 00:18:08,820 --> 00:18:10,820 Son oito andeis de música aquí de fronte para o público. 545 00:18:10,820 --> 00:18:14,200 Se puidese poñer o seu número no estes soportes de música de tal xeito 546 00:18:14,200 --> 00:18:16,560 que se aliñan co mesmos números no cadro. 547 00:18:16,560 --> 00:18:19,560 Entón, fai-se ollar como por poñendo os seus números sobre estes música 548 00:18:19,560 --> 00:18:21,960 fica aquí. 549 00:18:21,960 --> 00:18:25,980 Excelente ata agora. 550 00:18:25,980 --> 00:18:26,600 >> Excelente. 551 00:18:26,600 --> 00:18:26,890 Aceptar. 552 00:18:26,890 --> 00:18:29,556 Entón, agora, imos pedir ao cuestión en algunhas formas diferentes. 553 00:18:29,556 --> 00:18:31,610 Como podemos ir sobre como clasificar esas persoas aquí enriba? 554 00:18:31,610 --> 00:18:34,500 Porque tivemos algunhas enfoques anteriormente, en que estabamos 555 00:18:34,500 --> 00:18:36,360 tipo de toma de dous baldes diferentes. 556 00:18:36,360 --> 00:18:38,842 E entón nós xeralmente remendos as cousas xuntos. 557 00:18:38,842 --> 00:18:41,050 Así que viu dous números que pertencía xuntos, 558 00:18:41,050 --> 00:18:41,975 nós poñer-los xuntos. 559 00:18:41,975 --> 00:18:43,350 Dúas cartas que pertencen xuntos. 560 00:18:43,350 --> 00:18:45,058 >> Pero imos ver se nós Non se pode formalizar isto, 561 00:18:45,058 --> 00:18:48,044 para que poidamos finalmente ter algúns pseudo-código que vai, 562 00:18:48,044 --> 00:18:49,710 co cal pode resolver estes problemas. 563 00:18:49,710 --> 00:18:51,870 Entón, agora, eu estou ollando para fóra estas cifras aquí. 564 00:18:51,870 --> 00:18:55,030 E vexo unha morea de erros. 565 00:18:55,030 --> 00:18:57,750 En definitiva, quero un no á esquerda e oito á dereita. 566 00:18:57,750 --> 00:19:00,650 >> E entón eu estou ollando estes dous, catro e dous. 567 00:19:00,650 --> 00:19:02,930 E cal é o problema, obviamente? 568 00:19:02,930 --> 00:19:04,261 Si. 569 00:19:04,261 --> 00:19:04,760 So. 570 00:19:04,760 --> 00:19:07,160 Dous, obviamente, vén antes catro, entón vostede sabe o que? 571 00:19:07,160 --> 00:19:10,210 Déixeme primeiro dar unha visión lambona, se, como moito problema 572 00:19:10,210 --> 00:19:13,790 um-- definir se se lembra do Standard Edition do Conxunto de problemas One, 573 00:19:13,790 --> 00:19:16,820 onde só localmente resolver o problema que está ben aquí na miña fronte 574 00:19:16,820 --> 00:19:17,690 e ver onde me leva. 575 00:19:17,690 --> 00:19:17,870 >> Aceptar. 576 00:19:17,870 --> 00:19:20,161 Entón, dous e catro, deixe-me ir adiante e só intercambiar vostedes dous. 577 00:19:20,161 --> 00:19:22,400 Se pode mover fisicamente vós mesmos eo seu papel, 578 00:19:22,400 --> 00:19:25,040 Eu parezo comezar a incluír nun estado mellor. 579 00:19:25,040 --> 00:19:26,330 >> Agora, son bos. 580 00:19:26,330 --> 00:19:28,480 Vou seguir adiante, catro e seis anos, parece ser bo. 581 00:19:28,480 --> 00:19:29,110 Non é un problema. 582 00:19:29,110 --> 00:19:30,440 Seis e oito, Aceptar. 583 00:19:30,440 --> 00:19:31,860 Oito e un, outro problema. 584 00:19:31,860 --> 00:19:34,750 Porque o que é verdade sobre oito e un? 585 00:19:34,750 --> 00:19:36,990 Un vén antes das oito, e así o que temos que facer? 586 00:19:36,990 --> 00:19:38,090 Imos cambiar estes dous. 587 00:19:38,090 --> 00:19:39,316 Un e oito. 588 00:19:39,316 --> 00:19:40,690 E agora, eu vou continuar. 589 00:19:40,690 --> 00:19:42,030 Vou continuar mirando para adiante. 590 00:19:42,030 --> 00:19:42,840 E veremos que pasa. 591 00:19:42,840 --> 00:19:44,680 Oito e tres, de Por suposto, fóra de orde. 592 00:19:44,680 --> 00:19:45,815 Imos intercambio. 593 00:19:45,815 --> 00:19:46,940 Oito e sete, por suposto. 594 00:19:46,940 --> 00:19:47,481 Fóra de orde. 595 00:19:47,481 --> 00:19:48,280 Imos intercambio. 596 00:19:48,280 --> 00:19:49,940 Oito e cinco, por suposto, imos intercambio. 597 00:19:49,940 --> 00:19:50,560 Todo ben. 598 00:19:50,560 --> 00:19:51,880 Lista é ordenada. 599 00:19:51,880 --> 00:19:53,060 si? 600 00:19:53,060 --> 00:19:54,280 >> OK, obviamente, non. 601 00:19:54,280 --> 00:19:55,860 Pero é un pouco mellor, non? 602 00:19:55,860 --> 00:19:57,270 Porque aviso que pasou. 603 00:19:57,270 --> 00:20:01,749 Cada vez que realizou un intercambio, un menor número tipo de percolado que xeito, 604 00:20:01,749 --> 00:20:03,790 e un número maior percolado deste xeito, ou nós imos 605 00:20:03,790 --> 00:20:06,880 comezar a dicir ao borbulhar cara á esquerda ou cara á dereita borbulhar. 606 00:20:06,880 --> 00:20:10,080 >> Agora, non é suficiente, porque no mellor dos casos un número podería 607 00:20:10,080 --> 00:20:11,990 mover un punto á fronte, ou no peor dos casos, 608 00:20:11,990 --> 00:20:13,880 pode ter un número movido un lugar máis lonxe. 609 00:20:13,880 --> 00:20:16,369 Entón, vostede sabe o que este tipo de funcionar moi ben ata agora. 610 00:20:16,369 --> 00:20:17,410 Déixeme só probalo de novo. 611 00:20:17,410 --> 00:20:18,880 Dous e catro, están OK. 612 00:20:18,880 --> 00:20:20,180 Catro e seis, están OK. 613 00:20:20,180 --> 00:20:21,790 Seis e un, fóra de orde. 614 00:20:21,790 --> 00:20:23,007 Entón, imos cambiar vostedes dous. 615 00:20:23,007 --> 00:20:25,840 E agora, repare o problema de empezando a estar un pouco mellor de novo. 616 00:20:25,840 --> 00:20:27,006 Seis e tres, fóra de orde. 617 00:20:27,006 --> 00:20:28,100 Imos cambiar vostedes dous. 618 00:20:28,100 --> 00:20:29,730 Seis e sete, é bo. 619 00:20:29,730 --> 00:20:32,230 Sete e cinco, por suposto, fóra de orde. 620 00:20:32,230 --> 00:20:33,920 Sete e oito, en orde. 621 00:20:33,920 --> 00:20:36,470 E agora, eu pode que necesite facelo máis algunhas veces. 622 00:20:36,470 --> 00:20:39,830 E, de feito, creo que para vós quizais as veces maxima 623 00:20:39,830 --> 00:20:41,330 pode eu teño que andar para atrás e cara adiante? 624 00:20:41,330 --> 00:20:42,390 >> Nós imos voltar a iso. 625 00:20:42,390 --> 00:20:43,700 Entón, dous e catro aínda están OK. 626 00:20:43,700 --> 00:20:44,940 Catro e un, Nope. 627 00:20:44,940 --> 00:20:45,747 Entón, cambio de deixar. 628 00:20:45,747 --> 00:20:47,830 E, de novo, observar visualmente un é unha especie de borbulhar 629 00:20:47,830 --> 00:20:49,163 á esquerda, onde debería estar. 630 00:20:49,163 --> 00:20:50,010 Catro e tres intercambio. 631 00:20:50,010 --> 00:20:51,330 Catro e seis. 632 00:20:51,330 --> 00:20:53,100 Seis e cinco intercambio. 633 00:20:53,100 --> 00:20:53,959 Seis e sete. 634 00:20:53,959 --> 00:20:55,000 Sete e oito son boas. 635 00:20:55,000 --> 00:20:55,500 >> Bo. 636 00:20:55,500 --> 00:20:58,460 Estamos quedando aínda mellor. 637 00:20:58,460 --> 00:20:59,130 Entón imos ver. 638 00:20:59,130 --> 00:21:00,940 Agora temos dous e un. 639 00:21:00,940 --> 00:21:02,520 Por suposto, cambiar. 640 00:21:02,520 --> 00:21:07,520 Dous e tres, tres e catro, catro e cinco, seis e sete, sete e oito. 641 00:21:07,520 --> 00:21:08,020 Bo. 642 00:21:08,020 --> 00:21:08,730 E vostede sabe o que? 643 00:21:08,730 --> 00:21:11,190 Porque eu fixen un cambio alí, deixe-me facer unha verificación de sanidade. 644 00:21:11,190 --> 00:21:13,023 Deixe-me ir ata o final volver ao principio. 645 00:21:13,023 --> 00:21:13,680 Aceptar. 646 00:21:13,680 --> 00:21:14,750 Un, dois-- si, ver? 647 00:21:14,750 --> 00:21:15,870 Algo estaba mal. 648 00:21:15,870 --> 00:21:18,420 Tres, catro, cinco, seis, sete, oito. 649 00:21:18,420 --> 00:21:21,920 E neste último pase, son Está satisfeito coa miña empresa 650 00:21:21,920 --> 00:21:23,830 alegando que é clasificado? 651 00:21:23,830 --> 00:21:24,330 Aceptar. 652 00:21:24,330 --> 00:21:25,880 Visualmente, iso é absolutamente certo. 653 00:21:25,880 --> 00:21:28,410 Pero funcionalmente, o que que tamén só terá lugar 654 00:21:28,410 --> 00:21:31,870 nese último pase que permite que para confirmar que esta lista é de feito 655 00:21:31,870 --> 00:21:32,660 clasificadas? 656 00:21:32,660 --> 00:21:34,477 >> O que eu fixen ou non facelo último pase? 657 00:21:34,477 --> 00:21:35,810 Audiencia: Non se substituiu nengunha verba. 658 00:21:35,810 --> 00:21:36,120 DAVID J. Malan: Sentímolo? 659 00:21:36,120 --> 00:21:37,070 Audiencia: Sen cambios. 660 00:21:37,070 --> 00:21:38,653 DAVID J. Malan: Non se substituiu nengunha verba. 661 00:21:38,653 --> 00:21:41,947 Polo tanto, sería estúpido da miña parte facelo mesmo algoritmo de novo 662 00:21:41,947 --> 00:21:43,780 se eu non facer calquera modifica a primeira vez. 663 00:21:43,780 --> 00:21:45,160 E o Estado non cambiou. 664 00:21:45,160 --> 00:21:47,576 Certamente, eu non vou facer calquera cambia por segunda vez. 665 00:21:47,576 --> 00:21:49,820 E así, é seguro agora quere dicir, lista é ordenada. 666 00:21:49,820 --> 00:21:52,069 >> E, de feito, este é agora algo que nós imos xeral 667 00:21:52,069 --> 00:21:56,900 chamada bubble sort, no que pares, corrixir erros de novo, 668 00:21:56,900 --> 00:22:00,210 e de novo, e de novo, e manter indo e volvendo, 669 00:22:00,210 --> 00:22:03,370 e adiante e cara atrás, ata que facer ningún destes swaps, en que punto 670 00:22:03,370 --> 00:22:07,089 pode estar seguro, si, eu Terminada a fixación os erros. 671 00:22:07,089 --> 00:22:08,630 Imos axustar e tentar outra visión. 672 00:22:08,630 --> 00:22:11,590 Se vós poderían volver a orde que era un momento atrás, 673 00:22:11,590 --> 00:22:13,780 que mirou como esta. 674 00:22:13,780 --> 00:22:17,640 Agora, imos ter unha visión un pouco máis como o libro exame, 675 00:22:17,640 --> 00:22:21,122 polo cal estabamos sempre seleccionando a letra do alfabeto 676 00:22:21,122 --> 00:22:22,830 que nós medio que quería para xestionar o próximo. 677 00:22:22,830 --> 00:22:26,420 Quizais fose carta alta, como A, ou unha baixa letra Z. 678 00:22:26,420 --> 00:22:28,170 >> Entón, todo o mundo está de volta nesta orde. 679 00:22:28,170 --> 00:22:29,800 E agora déixeme facer. 680 00:22:29,800 --> 00:22:34,880 A ver Sei que teño oito números aquí. 681 00:22:34,880 --> 00:22:37,410 Eu estou indo a ir adiante e só deliberadamente seleccione 682 00:22:37,410 --> 00:22:38,520 os elementos máis pequenos. 683 00:22:38,520 --> 00:22:38,760 Non? 684 00:22:38,760 --> 00:22:39,801 Isto parece moi intuitivo. 685 00:22:39,801 --> 00:22:42,560 Por que non atopar o menor elemento, poñelas onde pertence, 686 00:22:42,560 --> 00:22:45,280 a continuación, obter o seguinte elemento máis pequeno, poña Lo onde pertence, e basta repetir. 687 00:22:45,280 --> 00:22:46,820 >> Porque intuitivamente, que debe funcionar tamén. 688 00:22:46,820 --> 00:22:48,441 Entón, catro, que é un número moi pequeno. 689 00:22:48,441 --> 00:22:49,940 Vou lembrar de onde isto é. 690 00:22:49,940 --> 00:22:50,523 Espera un minuto. 691 00:22:50,523 --> 00:22:51,577 Dous é menor. 692 00:22:51,577 --> 00:22:53,910 Déixame lembrar onde dous é, e esquecer-se sobre catro. 693 00:22:53,910 --> 00:22:55,050 Nós imos tratar con isto máis tarde. 694 00:22:55,050 --> 00:22:56,460 Seis, eu non estou interesado. 695 00:22:56,460 --> 00:22:57,810 Oito, eu non estou interesado. 696 00:22:57,810 --> 00:22:59,780 Un deles é o meu novo número pequeno. 697 00:22:59,780 --> 00:23:01,470 Entón, eu vou lembrar onde está. 698 00:23:01,470 --> 00:23:02,534 Tres, non interesa. 699 00:23:02,534 --> 00:23:03,450 Sete, non interesa. 700 00:23:03,450 --> 00:23:04,530 Cinco, non interesa. 701 00:23:04,530 --> 00:23:07,390 >> Entón, sen caer o escenario este ano, 702 00:23:07,390 --> 00:23:09,890 Vou coller número um-- e cal era o seu nome? 703 00:23:09,890 --> 00:23:10,150 >> Annan: Annan. 704 00:23:10,150 --> 00:23:11,220 >> DAVID J. Malan: Annan. 705 00:23:11,220 --> 00:23:13,540 E se puidese unirse a min na o inicio da lista, 706 00:23:13,540 --> 00:23:14,870 imos poñelas onde pertence. 707 00:23:14,870 --> 00:23:16,080 Unfortunately-- cal é o seu nome? 708 00:23:16,080 --> 00:23:16,650 >> Stefan: Stefan. 709 00:23:16,650 --> 00:23:18,191 >> DAVID J. Malan: Stefan está no camiño. 710 00:23:18,191 --> 00:23:23,490 Polo tanto, antes de Stefan resolve este problema, o que temos que facer? 711 00:23:23,490 --> 00:23:25,412 O que imos facer con Stefan? 712 00:23:25,412 --> 00:23:27,269 >> Audiencia: [inaudível]. 713 00:23:27,269 --> 00:23:28,060 DAVID J. Malan: Aceptar. 714 00:23:28,060 --> 00:23:28,850 Así poderiamos facelo. 715 00:23:28,850 --> 00:23:31,730 Poderiamos tipo de levar Stefan ea súa catro, e basta colocar-lo nunha variable 716 00:23:31,730 --> 00:23:33,530 e seguro-lo para unha certa cantidade de tempo, 717 00:23:33,530 --> 00:23:35,220 tornando así espazo para o número un. 718 00:23:35,220 --> 00:23:36,280 E iso non é malo. 719 00:23:36,280 --> 00:23:39,270 Eu podería suxerir, por que non facer nós só poñer Stefan aquí? 720 00:23:39,270 --> 00:23:41,610 Por que iso pode violar un das ideas que comezaron 721 00:23:41,610 --> 00:23:44,830 falando última vez, a semana pasada? 722 00:23:44,830 --> 00:23:45,330 Si? 723 00:23:45,330 --> 00:23:45,740 >> Audiencia: [inaudível]. 724 00:23:45,740 --> 00:23:46,860 >> DAVID J. Malan: Non hai ningún índice para el. 725 00:23:46,860 --> 00:23:49,735 Se pensas que iso, de feito, como un array, isto é como un negativo, 726 00:23:49,735 --> 00:23:52,900 polo que non hai memoria, en realidade, aquí se este é realmente unha matriz, 727 00:23:52,900 --> 00:23:55,090 como se declarou a semana pasada na conferencia. 728 00:23:55,090 --> 00:23:56,250 Así, non hai que facelo. 729 00:23:56,250 --> 00:23:57,340 Podemos almacena-lo nunha variable. 730 00:23:57,340 --> 00:23:57,820 >> Ou vostede sabe o que? 731 00:23:57,820 --> 00:23:59,153 Escoitei a alguén suxerir iso. 732 00:23:59,153 --> 00:24:01,020 O que máis poderiamos facer Stefan? 733 00:24:01,020 --> 00:24:03,770 Por que non só expulsalo lo e poñelas sobre o lugar onde estaba o número un. 734 00:24:03,770 --> 00:24:05,170 Entón, se quere ir máis alá. 735 00:24:05,170 --> 00:24:07,300 E, de feito, este é un solución moi boa. 736 00:24:07,300 --> 00:24:10,480 Agora, por unha banda, eu teño tipo da empeorou o problema. 737 00:24:10,480 --> 00:24:13,650 Catro é agora máis lonxe de onde debe ser. 738 00:24:13,650 --> 00:24:14,900 Debe ser cara a ese medio. 739 00:24:14,900 --> 00:24:16,100 >> Pero vostede sabe o que? 740 00:24:16,100 --> 00:24:17,630 Isto podería ser mala sorte. 741 00:24:17,630 --> 00:24:18,822 Quizais o número oito foi aquí. 742 00:24:18,822 --> 00:24:20,530 E así, quizais fariamos ter sorte, 743 00:24:20,530 --> 00:24:22,460 e oito empuxada para máis preto do final. 744 00:24:22,460 --> 00:24:24,710 Así, ao final do día, É o tipo de todas as medias para fóra. 745 00:24:24,710 --> 00:24:26,085 Non se preocupe con catro. 746 00:24:26,085 --> 00:24:29,400 Todo o que me importa agora é seleccionando o elemento máis pequeno. 747 00:24:29,400 --> 00:24:32,030 >> E agora, o que eu vou facer é esquecer-se sobre o número un 748 00:24:32,030 --> 00:24:35,160 permanentemente, porque sei o lista detrás de min agora está clasificada. 749 00:24:35,160 --> 00:24:36,720 Así, a miña lista era anteriormente tamaño oito. 750 00:24:36,720 --> 00:24:37,720 Agora, é do tamaño de sete. 751 00:24:37,720 --> 00:24:40,340 Entón, meu problema é conseguir menor, aínda que de forma lineal. 752 00:24:40,340 --> 00:24:43,022 Entón, agora, eu estou indo a seleccionar o actual elemento máis pequeno, dous. 753 00:24:43,022 --> 00:24:46,520 Seis, oito, catro, tres, sete, cinco. 754 00:24:46,520 --> 00:24:47,770 Ese foi o menor elemento. 755 00:24:47,770 --> 00:24:49,416 Entón que é o que eu vou facer com-- o que era o seu nome? 756 00:24:49,416 --> 00:24:49,760 >> JOSÉ: José. 757 00:24:49,760 --> 00:24:50,085 >> DAVID J. Malan: José? 758 00:24:50,085 --> 00:24:52,000 Nós imos deixar Joseph no lugar. 759 00:24:52,000 --> 00:24:54,842 Agora, eu vou finxir que estes faces é-- ben, 760 00:24:54,842 --> 00:24:56,550 Sei que estes dous xa están clasificados. 761 00:24:56,550 --> 00:24:58,424 Imos agora concentrarse na resto da lista. 762 00:24:58,424 --> 00:25:00,080 Seis é a menor corrente. 763 00:25:00,080 --> 00:25:01,190 Oito é maior. 764 00:25:01,190 --> 00:25:02,970 Catro agora a menor corrente. 765 00:25:02,970 --> 00:25:04,762 Tres é agora a menor corrente. 766 00:25:04,762 --> 00:25:07,720 E agora, eu estou indo a seleccionar tres, que é-- o que é o seu nome? 767 00:25:07,720 --> 00:25:08,190 SERENA: Serena. 768 00:25:08,190 --> 00:25:10,620 DAVID J. Malan: Serena, se puidese cara o seu número e intercambio com-- 769 00:25:10,620 --> 00:25:11,550 Kalsang: Kalsang. 770 00:25:11,550 --> 00:25:12,940 DAVID J. Malan: Kalsang. 771 00:25:12,940 --> 00:25:15,220 Imos volver, e estamos vai cambiar os dous. 772 00:25:15,220 --> 00:25:17,360 E agora, imos poñer isto no piloto automático. 773 00:25:17,360 --> 00:25:21,589 Eu estou indo a ir e deixar para vós para seleccionar os menores elementos próximos. 774 00:25:21,589 --> 00:25:22,380 Dun, Dun, Dun, Dun. 775 00:25:22,380 --> 00:25:24,560 Número catro, o que ten que facer? 776 00:25:24,560 --> 00:25:26,261 Excelente. 777 00:25:26,261 --> 00:25:27,760 Agora, eu vou facer outra pasaxe. 778 00:25:27,760 --> 00:25:28,590 Dun, Dun, Dun, Dun. 779 00:25:28,590 --> 00:25:31,465 Vexo cinco é o seguinte menor. 780 00:25:31,465 --> 00:25:32,840 Agora, eu vou tomar outra pasaxe. 781 00:25:32,840 --> 00:25:33,631 Dun, Dun, Dun, Dun. 782 00:25:33,631 --> 00:25:34,880 Seis é o menor. 783 00:25:34,880 --> 00:25:35,520 Bo. 784 00:25:35,520 --> 00:25:36,585 Sete é o menor. 785 00:25:36,585 --> 00:25:37,085 Non se produciron cambios. 786 00:25:37,085 --> 00:25:38,630 Oito é o menor. 787 00:25:38,630 --> 00:25:39,170 Feito. 788 00:25:39,170 --> 00:25:43,900 >> Entón, o que acaba de facer de forma iterativa seleccionando un elemento despois da outra 789 00:25:43,900 --> 00:25:47,230 é aplicar algo que somos vai formalizar como selección de clasificación. 790 00:25:47,230 --> 00:25:49,120 E é posible que aínda sinxelo de explicar, 791 00:25:49,120 --> 00:25:51,310 en que, literalmente, todo o que quero facer é só manter 792 00:25:51,310 --> 00:25:54,700 indo e volvendo pola lista selección, a próxima menor elemento, 793 00:25:54,700 --> 00:25:55,720 ata que estea feito. 794 00:25:55,720 --> 00:25:58,650 >> Por iso, é aínda máis sinxela, quizais intuitivamente, que a última. 795 00:25:58,650 --> 00:26:00,020 Imos tentar un último. 796 00:26:00,020 --> 00:26:03,060 Se vós poderían axustar a si mesmos nas seguintes posicións 797 00:26:03,060 --> 00:26:08,600 unha última vez, imos ver se non podemos agora formalizar outra visión. 798 00:26:08,600 --> 00:26:12,857 De feito, sería alguén aí quere propoñer 799 00:26:12,857 --> 00:26:14,440 de que outra forma poderíamos facer sobre este asunto? 800 00:26:14,440 --> 00:26:17,439 Sen tirar buzzwords ou tipo respostas que xa son coñecidas, 801 00:26:17,439 --> 00:26:19,689 só intuitivamente, o que poderiamos facer? 802 00:26:19,689 --> 00:26:21,635 >> Audiencia: [inaudível]. 803 00:26:21,635 --> 00:26:22,510 DAVID J. Malan: Yeah. 804 00:26:22,510 --> 00:26:24,620 Entón, hai algunha gran intuición alí. 805 00:26:24,620 --> 00:26:28,020 As cousas boas parecen ocorrer ata agora en ciencia da computación cando dividimos 806 00:26:28,020 --> 00:26:30,832 e conquistar o problema de dividir polo medio e medio a medio. 807 00:26:30,832 --> 00:26:32,540 E así, de feito, nós podería comezar a facelo. 808 00:26:32,540 --> 00:26:35,754 E, de feito, que vai ser, imos ver, un dos nosos mellores solucións aínda. 809 00:26:35,754 --> 00:26:37,420 Pero imos volver a iso en pouco tempo. 810 00:26:37,420 --> 00:26:40,500 En realidade, nós imos facer que un pouco máis tarde esta semana. 811 00:26:40,500 --> 00:26:42,180 O que máis podemos facer para solucionar isto? 812 00:26:42,180 --> 00:26:44,647 Entón, todo o mundo aquí está orde aparentemente aleatoria. 813 00:26:44,647 --> 00:26:45,230 Sabes que? 814 00:26:45,230 --> 00:26:48,320 En vez de ir e volver, adiante e cara atrás, e cara atrás 815 00:26:48,320 --> 00:26:50,624 cada vez, este se sente como Eu estou facendo unha morea de pé. 816 00:26:50,624 --> 00:26:52,790 Por que non podo só comezar en o inicio da lista, 817 00:26:52,790 --> 00:26:54,960 e pode poñer catro onde pertence? 818 00:26:54,960 --> 00:26:59,680 Entón deixe-me asumir para o momento que miña lista é só este primeiro elemento. 819 00:26:59,680 --> 00:27:04,937 É catro clasificados neste momento no tempo, se todo o que me importa é todo aquí? 820 00:27:04,937 --> 00:27:06,520 Esta é unha especie de trivialmente verdadeira, non? 821 00:27:06,520 --> 00:27:10,000 Como a lista contén un número, e que é, obviamente, o número catro clasificados. 822 00:27:10,000 --> 00:27:13,070 >> Entón déixeme só estipular que esta lista é ordenada. 823 00:27:13,070 --> 00:27:15,090 Pero agora eu teño o resto da lista. 824 00:27:15,090 --> 00:27:17,240 Entón, agora, eu encontro dous. 825 00:27:17,240 --> 00:27:21,690 Onde fai dous obviamente pertencen en relación a catro? 826 00:27:21,690 --> 00:27:22,580 Antes catro. 827 00:27:22,580 --> 00:27:23,862 Entón, o que podo facer aquí? 828 00:27:23,862 --> 00:27:24,820 Cal é o seu nome? 829 00:27:24,820 --> 00:27:25,090 >> JOSÉ: José. 830 00:27:25,090 --> 00:27:26,030 >> DAVID J. Malan: José, se puidese volver atrás 831 00:27:26,030 --> 00:27:27,790 por só un momento co seu número. 832 00:27:27,790 --> 00:27:31,130 E agora o que debe Stefan facer aquí? 833 00:27:31,130 --> 00:27:33,720 Imos cambiar Stefan aquí. 834 00:27:33,720 --> 00:27:35,520 E agora, imos Joseph entrar aquí. 835 00:27:35,520 --> 00:27:39,660 E agora, deixe-me dicir que todo aquí está clasificada. 836 00:27:39,660 --> 00:27:42,474 Entón, resultado similar, pero un visión fundamentalmente diferente. 837 00:27:42,474 --> 00:27:44,140 Eu nin sequera mirou para o que está alí en baixo. 838 00:27:44,140 --> 00:27:46,310 Eu sigo tendo os elementos como son entregado a min, 839 00:27:46,310 --> 00:27:47,240 e tratar con eles. 840 00:27:47,240 --> 00:27:48,330 >> Entón, agora, eu vexo o número seis. 841 00:27:48,330 --> 00:27:51,110 Onde é que o número seis pertencen? 842 00:27:51,110 --> 00:27:53,250 Temos dous, catro, seis. 843 00:27:53,250 --> 00:27:54,800 Exactamente onde está agora. 844 00:27:54,800 --> 00:27:57,750 Entón, imos deixar isto quedo, e agora afirman que esta parte da lista 845 00:27:57,750 --> 00:27:58,772 agora está clasificada. 846 00:27:58,772 --> 00:28:01,230 E así, este se sente fundamentalmente diferente, xa que eu son só 847 00:28:01,230 --> 00:28:05,230 movéndose a través da lista aquí linearmente, e eu nunca estou dobrando cara atrás. 848 00:28:05,230 --> 00:28:05,730 Si. 849 00:28:05,730 --> 00:28:06,230 Todo ben. 850 00:28:06,230 --> 00:28:08,190 Así, oito, onde pertence? 851 00:28:08,190 --> 00:28:08,730 Ben aquí. 852 00:28:08,730 --> 00:28:09,310 Perfecto. 853 00:28:09,310 --> 00:28:10,210 Entón, agora, un. 854 00:28:10,210 --> 00:28:10,900 Uh-oh. 855 00:28:10,900 --> 00:28:13,010 Isto parece que é vai ser caro. 856 00:28:13,010 --> 00:28:15,690 Agora, no algoritmo anterior, Eu só trocados persoas. 857 00:28:15,690 --> 00:28:18,648 Para que eu poida poñer-lo todo o camiño no en principio, pero despois cambiou Joseph. 858 00:28:18,648 --> 00:28:21,450 Pero se eu pasar Joseph, agora o que vai ser mal? 859 00:28:21,450 --> 00:28:24,250 >> Agora, eu teño a sorte de undone-- teño dado un paso á fronte e, a continuación, 860 00:28:24,250 --> 00:28:26,300 un paso atrás, porque agora Joseph estaría fóra de orde. 861 00:28:26,300 --> 00:28:26,830 Entón, imos facelo. 862 00:28:26,830 --> 00:28:29,150 Se puidese levar o número un e paso atrás por só un momento. 863 00:28:29,150 --> 00:28:30,490 Como podemos put-- o que mesmo o seu nome? 864 00:28:30,490 --> 00:28:31,130 >> Annan: Annan. 865 00:28:31,130 --> 00:28:32,610 >> DAVID J. Malan: Annan no lugar? 866 00:28:32,610 --> 00:28:36,091 O que ten que ocorrer con respecto a dous, catro, seis, oito e? 867 00:28:36,091 --> 00:28:37,570 Todo o que precisan cambiar. 868 00:28:37,570 --> 00:28:42,590 Polo tanto, se oito quere desprazar en primeiro lugar, a continuación, seis, despois catro, despois dous. 869 00:28:42,590 --> 00:28:45,380 E entón Annan, se quere vir aquí, bo. 870 00:28:45,380 --> 00:28:47,760 Pero aquí, temos só tipo de pago un prezo 871 00:28:47,760 --> 00:28:49,510 nun punto diferente no algoritmo. 872 00:28:49,510 --> 00:28:52,550 Considerando última vez coa selección tipo, e mesmo bubble sort, 873 00:28:52,550 --> 00:28:54,700 Eu estou camiñando cara atrás e adiante, para atrás e cara adiante, 874 00:28:54,700 --> 00:28:58,360 que é, certamente, sumando tempo-sabio, e, literalmente, paso a paso. 875 00:28:58,360 --> 00:29:00,660 >> Ordenación por inserción, na primeira vista, parece que é 876 00:29:00,660 --> 00:29:05,150 super-intelixente, en que eu son só facendo lento, o progreso incremental, 877 00:29:05,150 --> 00:29:07,120 pero eu non vou esta fronte e cara atrás. 878 00:29:07,120 --> 00:29:09,410 Pero se alguén é de feito fóra de orde, previo 879 00:29:09,410 --> 00:29:10,840 todo o traballo que eu só tiven que facer. 880 00:29:10,840 --> 00:29:14,750 Tiven que cambiar a metade da lista só para dar espazo para o número un. 881 00:29:14,750 --> 00:29:16,790 Entón é a mesma cantidade de traballo, ata agora, 882 00:29:16,790 --> 00:29:18,690 sente, só un tipo de traballo. 883 00:29:18,690 --> 00:29:19,370 >> Imos continuar. 884 00:29:19,370 --> 00:29:22,657 Polo tanto, agora sabemos que todo o mundo entre un e oito son clasificadas. 885 00:29:22,657 --> 00:29:23,740 Aquí, eu teño o número tres. 886 00:29:23,740 --> 00:29:25,864 Se che gusta de incorporarse número tres, paso atrás un. 887 00:29:25,864 --> 00:29:28,260 E o que vostedes teñen que facer? 888 00:29:28,260 --> 00:29:28,760 Yep. 889 00:29:28,760 --> 00:29:33,070 Entón, iso é outro, dous, tres pasos. 890 00:29:33,070 --> 00:29:36,010 Tres unidades de tempo que custa só me, de xeito que os tres poden agora encaixar. 891 00:29:36,010 --> 00:29:37,460 Finalmente, sete. 892 00:29:37,460 --> 00:29:39,730 >> Imos adiante e ter tomar un paso atrás. 893 00:29:39,730 --> 00:29:42,780 Isto só vai custar unha unidade de tempo, pero iso é OK. 894 00:29:42,780 --> 00:29:44,170 E agora, cinco de ir ser un pouco máis caro. 895 00:29:44,170 --> 00:29:45,340 Se desexa dar un paso atrás. 896 00:29:45,340 --> 00:29:48,380 Necesitamos avanzar oito, e sete, e seis. 897 00:29:48,380 --> 00:29:50,749 E entón todo o mundo está agora clasificada. 898 00:29:50,749 --> 00:29:52,290 Así, unha gran man para os nosos voluntarios aquí. 899 00:29:52,290 --> 00:29:53,554 Moitas grazas. 900 00:29:53,554 --> 00:29:56,220 >> [Aplausos] 901 00:29:56,220 --> 00:29:56,860 >> Grazas a todos. 902 00:29:56,860 --> 00:29:57,520 Grazas a todos. 903 00:29:57,520 --> 00:30:02,940 Entón imos ver agora como caro todo isto era. 904 00:30:02,940 --> 00:30:06,210 Imos considerar, se cadra, o máis simple delas, unha especie de burbulla. 905 00:30:06,210 --> 00:30:09,950 E digo máis simple, só porque pode resolver-lo avidamente por só 906 00:30:09,950 --> 00:30:11,660 resolver o problema de pares aquí. 907 00:30:11,660 --> 00:30:13,720 Resolver o problema de pares aquí, unha e outra vez 908 00:30:13,720 --> 00:30:17,680 e de novo, repetindo como moitos veces como realmente precisa. 909 00:30:17,680 --> 00:30:21,050 >> Así, verifícase que cunha especie de burbulla, así, 910 00:30:21,050 --> 00:30:25,820 cantos pasos teño que asumir a primeira pasaxe dese algoritmo? 911 00:30:25,820 --> 00:30:30,850 Podería take-- imos see-- un, dous, tres, catro, cinco, seis, sete. 912 00:30:30,850 --> 00:30:32,190 E hai oito elementos aquí. 913 00:30:32,190 --> 00:30:35,280 Entón, é como n menos 1 pasos para comeza a partir do inicio da lista 914 00:30:35,280 --> 00:30:36,380 ao final da lista. 915 00:30:36,380 --> 00:30:41,350 >> Pero con selección tipo, lembre que eu son seleccionar os elementos novo e de novo 916 00:30:41,350 --> 00:30:44,590 e, de novo, que é menor, Estou poñendo-o no lugar, 917 00:30:44,590 --> 00:30:46,616 pero entón eu non son mirando atrás de min de novo. 918 00:30:46,616 --> 00:30:49,490 Entón, eu creo que é un pouco máis clara que, a continuación, por primeira vez, que pode 919 00:30:49,490 --> 00:30:52,680 ten que tomar todos os pasos n menos 1 para atopar o elemento máis pequeno. 920 00:30:52,680 --> 00:30:55,920 Entón eu poñer-los no lugar, e eu expulsar quenquera que estivese aquí anteriormente. 921 00:30:55,920 --> 00:30:57,500 >> Pero entón eu non teño que manter a ollar a este elemento, 922 00:30:57,500 --> 00:30:59,040 porque sei que é xa a menor. 923 00:30:59,040 --> 00:31:01,581 Entón, agora, podo ver só sete elementos, a continuación, seis elementos, 924 00:31:01,581 --> 00:31:03,290 a continuación, cinco elementos, a continuación, catro elementos. 925 00:31:03,290 --> 00:31:06,900 E así matematicamente, se n é o número de elementos ou números 926 00:31:06,900 --> 00:31:11,990 que comezou con, pode imaxinar que este é o mesmo que n menos 1, 927 00:31:11,990 --> 00:31:14,250 ademais n menos 2 etapas, n menos 3 etapas, 928 00:31:14,250 --> 00:31:16,780 n menos 4 pasos, todo o forma abaixo a un paso. 929 00:31:16,780 --> 00:31:18,160 E eu estou na miña última persoa. 930 00:31:18,160 --> 00:31:20,650 >> E se se lembra que unha morea Estado de libros ou libros de matemáticas 931 00:31:20,650 --> 00:31:24,730 ter esas fórmulas na capa dura cara atrás ou diante deles, 932 00:31:24,730 --> 00:31:27,690 verifícase que esta serie pode ser expresado de forma máis simple 933 00:31:27,690 --> 00:31:28,857 como n veces n menos 1 sobre 2. 934 00:31:28,857 --> 00:31:31,273 E é bo se isto non é na vangarda da súa mente. 935 00:31:31,273 --> 00:31:32,420 Pero iso é realmente verdade. 936 00:31:32,420 --> 00:31:34,449 Isto é só unha maneira máis sinxela de escribilo. 937 00:31:34,449 --> 00:31:36,240 E entón se pensas de volta á escola, 938 00:31:36,240 --> 00:31:38,698 cando acaba de comezar multiplicando cousas, iso, por suposto, 939 00:31:38,698 --> 00:31:41,820 é só n ao cadrado menos n dividido por dous. 940 00:31:41,820 --> 00:31:44,772 Todo o que eu teño feito é ampliar as expresións alí. 941 00:31:44,772 --> 00:31:46,730 E así imos ter que volver escribir este un pouco diferente. 942 00:31:46,730 --> 00:31:49,780 Isto n ao cadrado dividido por 2 menos n / 2. 943 00:31:49,780 --> 00:31:53,270 >> Entón, de novo, eu son só un tipo de aplicación un pouco de aritmética goberna alí. 944 00:31:53,270 --> 00:31:57,140 Pero teña en conta-se agora que o maior prazo nesta expresión, por así dicir, 945 00:31:57,140 --> 00:31:58,540 é que n ao cadrado. 946 00:31:58,540 --> 00:32:02,910 Entón, si, é n ao cadrado dividido por dous, menos n / 2. 947 00:32:02,910 --> 00:32:05,080 >> Pero, xeralmente, se n é vai ser un valor grande, 948 00:32:05,080 --> 00:32:08,740 Vou alegar que n ao cadrado vai ser o factor dominante. 949 00:32:08,740 --> 00:32:10,490 É só será un contribuínte grande 950 00:32:10,490 --> 00:32:12,877 ao número de pasos que n / 2. 951 00:32:12,877 --> 00:32:13,960 Entón, o que quero dicir con isto? 952 00:32:13,960 --> 00:32:16,795 Imos tentar un exemplo simple, mesmo aínda que a matemática está un pouco grande. 953 00:32:16,795 --> 00:32:20,210 >> Entón, supoña que 1 millón de persoas no escenario, ou 1 millón de cousas 954 00:32:20,210 --> 00:32:21,320 que quere clasificar. 955 00:32:21,320 --> 00:32:23,730 Imos poñer en marcha un millón en exactamente que fórmula 956 00:32:23,730 --> 00:32:27,230 para ver cantos pasos que leva totais para clasificar un millón de elementos usando digamos, 957 00:32:27,230 --> 00:32:28,560 tipo de selección. 958 00:32:28,560 --> 00:32:30,760 >> Entón, nós teriamos a mesma fórmula como antes. 959 00:32:30,760 --> 00:32:34,120 Conectar un millón, para que eu recibín un millón cadrado dividido por 2, 960 00:32:34,120 --> 00:32:35,990 menos dun millón dividido por 2. 961 00:32:35,990 --> 00:32:40,180 Se eu fai iso de matemáticas con antelación aquí temos 500 millóns 962 00:32:40,180 --> 00:32:47,460 menos 500.000, que dános 499999500000, 963 00:32:47,460 --> 00:32:49,270 que é moi danado grande. 964 00:32:49,270 --> 00:32:54,370 >> En realidade, se comparar agora 499.000 millóns, 999 millóns, 965 00:32:54,370 --> 00:33:01,210 500000 contra o noso valor orixinal, 500 millóns, é tan ben preto. 966 00:33:01,210 --> 00:33:06,850 Non? n ao cadrado dividido por 2 dá US-- ou mellor, n ao cadrado dividido por 2 967 00:33:06,850 --> 00:33:08,370 deunos 500 millóns. 968 00:33:08,370 --> 00:33:13,510 Iso é moi danado preto a 499.999.500.000, 969 00:33:13,510 --> 00:33:17,970 o que quere dicir fóra subtraindo 500.000, ou, máis xeralmente, subtraindo fóra 970 00:33:17,970 --> 00:33:20,010 n ao cadrado, non é realmente un gran negocio. 971 00:33:20,010 --> 00:33:22,490 O n ao cadrado fai que estas números crecen moi rápido. 972 00:33:22,490 --> 00:33:25,790 >> Agora, iso só é importante na medida en como nós, como científicos da computación, 973 00:33:25,790 --> 00:33:29,350 son xeralmente non vai importar tanto sobre as pasaxes destas fórmulas 974 00:33:29,350 --> 00:33:31,400 e exactamente o que o respostas precisas son. 975 00:33:31,400 --> 00:33:33,390 Nós nos preocupa só iso, vostede sabe o que? 976 00:33:33,390 --> 00:33:37,810 Ao final do día, esta fórmula é da orde de n ao cadrado. 977 00:33:37,810 --> 00:33:39,350 >> Si, estamos dividindo por dous alí dentro. 978 00:33:39,350 --> 00:33:41,360 Si, estamos subtraindo off n menos 2. 979 00:33:41,360 --> 00:33:46,860 Con todo, ao final do día, o termo que realmente doe e costa connosco 980 00:33:46,860 --> 00:33:48,995 unha serie de etapas que o termo cadrado. 981 00:33:48,995 --> 00:33:51,370 E entón o que un científico da computación vai xeralmente fan 982 00:33:51,370 --> 00:33:54,160 é ignorar todos os Da orde menor, 983 00:33:54,160 --> 00:33:56,900 e basta ollar para o que máis contribúe ao custo. 984 00:33:56,900 --> 00:34:00,530 >> E iso é bo, porque podemos agora falar con máis xeneralidade 985 00:34:00,530 --> 00:34:02,470 sobre algoritmos, e pode comparalos-los. 986 00:34:02,470 --> 00:34:04,550 E o feito de que eu son O utilizando este é deliberada. 987 00:34:04,550 --> 00:34:06,680 Cando digo no fin de, estou especialmente 988 00:34:06,680 --> 00:34:09,560 referíndose a algo chamado gran O. E ó gran 989 00:34:09,560 --> 00:34:14,090 é unha notación que un ordenador científico usa para describir 990 00:34:14,090 --> 00:34:16,710 un límite superior en algo. 991 00:34:16,710 --> 00:34:21,150 >> Entón, se dicir que un algoritmo é en gran O n ao cadrado, 992 00:34:21,150 --> 00:34:23,380 como eu propuxen só un hai pouco, que os medios 993 00:34:23,380 --> 00:34:27,710 que, en termos da súa execución tempo ou a súa eficiencia, 994 00:34:27,710 --> 00:34:30,090 el asume a orde cadrado de n pasos. 995 00:34:30,090 --> 00:34:31,420 Quizais máis, quizais menos. 996 00:34:31,420 --> 00:34:33,435 Pero é da orde de n ao cadrado. 997 00:34:33,435 --> 00:34:34,560 E ese é o límite superior. 998 00:34:34,560 --> 00:34:36,530 Non vai ser máis doloroso do que iso. 999 00:34:36,530 --> 00:34:40,800 Non vai ser n cubos, ou 2 ao n, ou algo moito maior. 1000 00:34:40,800 --> 00:34:43,800 Este é un límite superior en todo o que o custo é. 1001 00:34:43,800 --> 00:34:46,150 Así, dado que, imos Considero só algúns exemplos. 1002 00:34:46,150 --> 00:34:49,820 E esta é só unha lista finita tempos de execución de moi comúns 1003 00:34:49,820 --> 00:34:52,870 para algoritmos que está destinado a ser ilustrativos dalgúns cousas que temos 1004 00:34:52,870 --> 00:34:53,600 visto xa. 1005 00:34:53,600 --> 00:34:58,060 >> Así, por exemplo, no caso de selección tipo, o que eu digo aquí 1006 00:34:58,060 --> 00:35:02,250 se está a executar que a selección de tipo tempo é da orde de n ao cadrado. 1007 00:35:02,250 --> 00:35:06,260 No peor caso, eu vou ter unha morea de números aleatorios aquí. 1008 00:35:06,260 --> 00:35:08,600 E, como vimos matematicamente, se eu continuar camiñando 1009 00:35:08,600 --> 00:35:11,310 por medio da lista, a través do lista, seleccionar o seguinte menor 1010 00:35:11,310 --> 00:35:14,410 elemento novo e de novo, se eu de feito, anota todos os pasos 1011 00:35:14,410 --> 00:35:18,750 Estou tomando como eu propuxen como unha fórmula antes, é da orde de n ao cadrado 1012 00:35:18,750 --> 00:35:20,370 pasos que eu estou tomando. 1013 00:35:20,370 --> 00:35:24,520 >> E parece que burbulla tipo e ordenación por inserción 1014 00:35:24,520 --> 00:35:27,370 son tan lento no peor dos casos. 1015 00:35:27,370 --> 00:35:32,040 Considero, por exemplo, ordenación por inserción, o último algoritmo, tratamos, 1016 00:35:32,040 --> 00:35:35,500 que nos fixo ollar para o elemento, e, a continuación, inserir-lo onde pertence. 1017 00:35:35,500 --> 00:35:38,720 E entón miramos ao seguinte elemento, e inseriu lo onde pertence. 1018 00:35:38,720 --> 00:35:40,990 >> Por iso, considero o mellor escenario posible. 1019 00:35:40,990 --> 00:35:45,590 Supoña que tiña meus voluntarios aliñar literalmente, como este, de un a oito, 1020 00:35:45,590 --> 00:35:47,440 xa ordenados. 1021 00:35:47,440 --> 00:35:51,300 Cantos pasos é a ordenación por inserción vai levar para clasificar oito persoas, 1022 00:35:51,300 --> 00:35:55,640 se chegan no escenario mirando así? 1023 00:35:55,640 --> 00:35:57,410 >> Oito persoas xa ordenados. 1024 00:35:57,410 --> 00:35:58,760 E eu uso a inserción de tipo. 1025 00:35:58,760 --> 00:36:02,180 Ese último dos algoritmos. 1026 00:36:02,180 --> 00:36:03,640 Ben, imos revivir rápido real. 1027 00:36:03,640 --> 00:36:05,504 Entón, se eu comezar, eu vexo un. 1028 00:36:05,504 --> 00:36:06,420 Onde é que se pertencen? 1029 00:36:06,420 --> 00:36:07,730 Pertence aquí. 1030 00:36:07,730 --> 00:36:08,330 Vexo dous. 1031 00:36:08,330 --> 00:36:09,660 Onde é que dous pertencen? 1032 00:36:09,660 --> 00:36:10,260 Ben aquí. 1033 00:36:10,260 --> 00:36:10,900 Vexo tres. 1034 00:36:10,900 --> 00:36:11,920 Onde é que tres pertencen? 1035 00:36:11,920 --> 00:36:12,480 Ben aquí. 1036 00:36:12,480 --> 00:36:13,100 >> Vexo catro. 1037 00:36:13,100 --> 00:36:13,600 Ben aquí. 1038 00:36:13,600 --> 00:36:15,660 Cinco, seis, sete, oito. 1039 00:36:15,660 --> 00:36:17,320 Non hai ningunha razón para me repetir. 1040 00:36:17,320 --> 00:36:21,260 E así, como moitos pasos é que, en termos de n? 1041 00:36:21,260 --> 00:36:23,870 É da orde de n pasos, non? n menos 1. 1042 00:36:23,870 --> 00:36:27,567 Pero eu tomou unha serie lineal de pasos, e agora eu son feito. 1043 00:36:27,567 --> 00:36:28,900 Entón ese é o mellor caso, con todo. 1044 00:36:28,900 --> 00:36:29,983 E sobre o peor caso? 1045 00:36:29,983 --> 00:36:32,730 Que oito estaban alí, e sete estaban alí embaixo, 1046 00:36:32,730 --> 00:36:35,840 e un e dous foron máis aquí, entón que a lista foron verdadeiramente revertido? 1047 00:36:35,840 --> 00:36:38,300 >> Ben, o que pasa realmente se este é o número? 1048 00:36:38,300 --> 00:36:41,300 E nós imos facer só un par de exemplos. 1049 00:36:41,300 --> 00:36:49,300 E se, de feito, o número oito está aquí, e os berros number--. 1050 00:36:49,300 --> 00:36:52,660 1051 00:36:52,660 --> 00:36:56,430 Entón, o que, de feito, o número oito é todo o camiño ata aquí, 1052 00:36:56,430 --> 00:36:57,790 e eu estou usando ordenación por inserción? 1053 00:36:57,790 --> 00:36:58,290 >> Aceptar. 1054 00:36:58,290 --> 00:37:00,280 Eu reivindico no momento que está no lugar. 1055 00:37:00,280 --> 00:37:03,152 Pero agora, seven-- onde é que sete ir? 1056 00:37:03,152 --> 00:37:04,360 Claro, que vai por aquí. 1057 00:37:04,360 --> 00:37:06,760 Entón eu teño que mover oito máis dun lugar. 1058 00:37:06,760 --> 00:37:08,554 Agora seis, onde vai? 1059 00:37:08,554 --> 00:37:09,220 Ben, todo ben. 1060 00:37:09,220 --> 00:37:13,150 Agora, eu teño que cambiar oito máis un lugar, e sete ao longo dun lugar, 1061 00:37:13,150 --> 00:37:14,440 e entón eu plop abaixo seis. 1062 00:37:14,440 --> 00:37:16,870 >> Así, o primeiro tempo, custo me un paso para fixar as cousas, 1063 00:37:16,870 --> 00:37:18,570 entón iso me custou dous pasos para arranxar as cousas. 1064 00:37:18,570 --> 00:37:20,370 Cantos pasos se vai levar para corrixir 1065 00:37:20,370 --> 00:37:22,720 cousas para poñer cinco no lugar seguro? 1066 00:37:22,720 --> 00:37:23,340 Tres. 1067 00:37:23,340 --> 00:37:29,520 Porque agora eu teño que mover un, dous, tres. 1068 00:37:29,520 --> 00:37:32,430 Cantos pasos é que vai tomar para poñer catro no lugar seguro? 1069 00:37:32,430 --> 00:37:36,040 4 plus 5, engade 6, ademais de sete. 1070 00:37:36,040 --> 00:37:40,260 >> E por iso é matematicamente idéntica á o que describimos para a selección de clasificación. 1071 00:37:40,260 --> 00:37:42,130 Temos nesta serie que só está a aumentar. 1072 00:37:42,130 --> 00:37:45,650 1 máis 2 máis 3, 4, ou, inversamente, 7 + 6 1073 00:37:45,650 --> 00:37:52,610 máis 5 4 engádese se para hoxe para fins da orde de n ao cadrado. 1074 00:37:52,610 --> 00:37:57,640 >> Entón deixe-me tamén que estipulan bubble sort é tamén no n ao cadrado. 1075 00:37:57,640 --> 00:38:01,340 Porque con bubble sort, cada xa que eu vaia a lista, 1076 00:38:01,340 --> 00:38:03,100 Estou levando aproximadamente cantos chanzos? 1077 00:38:03,100 --> 00:38:06,260 Cada vez que eu literalmente andar de alí para alí? 1078 00:38:06,260 --> 00:38:07,960 Preto de n pasos. 1079 00:38:07,960 --> 00:38:12,650 Pero cantas veces eu podería que ir a través da lista? 1080 00:38:12,650 --> 00:38:13,920 >> Ben, preto de tempo n. 1081 00:38:13,920 --> 00:38:15,680 Quizais n menos 1, pero preto de n veces. 1082 00:38:15,680 --> 00:38:16,430 Ben, por que isto? 1083 00:38:16,430 --> 00:38:19,560 Ben, con bubble sort, se comezamos con bubble sort, 1084 00:38:19,560 --> 00:38:23,570 coa lista na peor posible situación, que unha vez máis é totalmente 1085 00:38:23,570 --> 00:38:25,550 cara atrás, o que vai pasar? 1086 00:38:25,550 --> 00:38:28,830 Eu percorrer a lista, eo número un pertence todo o camiño ata alí. 1087 00:38:28,830 --> 00:38:33,280 >> Pero con bubble sort, ata que punto é que un mover na miña primeira pasaxe a través da lista? 1088 00:38:33,280 --> 00:38:36,620 Cantos puntos consegue máis próximo ao lugar correcto? 1089 00:38:36,620 --> 00:38:37,240 Só un. 1090 00:38:37,240 --> 00:38:40,281 Entón, se tipo de razón través deste, cada vez a través deste algoritmo, 1091 00:38:40,281 --> 00:38:41,880 Tendo uns n pasos de David. 1092 00:38:41,880 --> 00:38:44,940 Pero cantos pases a lista é 1093 00:38:44,940 --> 00:38:49,060 vai levar a un a burbulla á esquerda, onde pertence? 1094 00:38:49,060 --> 00:38:51,840 >> Ten que moverse como, n espazos deste xeito. 1095 00:38:51,840 --> 00:38:57,960 Entón, só para facer a selección da lista, Teño que andar cara atrás e n veces. 1096 00:38:57,960 --> 00:39:01,540 E cada vez, estou buscando n elementos. 1097 00:39:01,540 --> 00:39:05,410 Entón, facer as cousas n n veces da orde de n ao cadrado. 1098 00:39:05,410 --> 00:39:07,220 >> Agora, imos ver en algúns dos curtas que 1099 00:39:07,220 --> 00:39:10,440 son incorporados no seguinte problema do CS50 definida, outra visión para estes, 1100 00:39:10,440 --> 00:39:13,490 pero por agora, imos considerar só algúns outros tempos de execución, 1101 00:39:13,490 --> 00:39:16,840 especialmente se os selección tomar un pouco de tempo para afundir. 1102 00:39:16,840 --> 00:39:21,790 ¿Que é un algoritmo que vimos xa que leva na orde de n pasos? 1103 00:39:21,790 --> 00:39:27,560 >> O que debe tomar unha serie lineal de pasos que vimos ata agora? 1104 00:39:27,560 --> 00:39:29,350 Que é iso? 1105 00:39:29,350 --> 00:39:30,480 A investigación de directorio de teléfono. 1106 00:39:30,480 --> 00:39:31,390 O primeiro algoritmo. 1107 00:39:31,390 --> 00:39:31,560 Non? 1108 00:39:31,560 --> 00:39:33,650 Onde estamos linearmente buscando Mike Smith? 1109 00:39:33,650 --> 00:39:34,150 De feito. 1110 00:39:34,150 --> 00:39:37,180 A partir da semana cero, cando comece virando unha páxina de cada vez, 1111 00:39:37,180 --> 00:39:40,095 e eu mesmo dixo que era unha especie dun algoritmo sensación lineal, 1112 00:39:40,095 --> 00:39:42,720 e tivemos que imaxe na tarxeta coa liña vermella recta 1113 00:39:42,720 --> 00:39:44,678 eo amarelo en liña recta liña, aqueles eran de feito 1114 00:39:44,678 --> 00:39:46,810 algoritmos que son en gran ó n. 1115 00:39:46,810 --> 00:39:50,680 >> Porque para atopar Mike Smith nun teléfono libro de n páxinas, no peor caso, 1116 00:39:50,680 --> 00:39:52,422 me pode n pasos tomar. 1117 00:39:52,422 --> 00:39:53,630 Que tal incorporarse atención? 1118 00:39:53,630 --> 00:39:55,790 Un, dous, tres, catro, cinco, seis. 1119 00:39:55,790 --> 00:39:59,420 Cal é o tempo de execución deste algoritmo para facer a chamada? 1120 00:39:59,420 --> 00:40:03,070 Big O n, porque, en teoría I ten que apuntar todos na sala. 1121 00:40:03,070 --> 00:40:05,861 >> Agora, como un aparte, que sobre o outra optimización de semana de cero? 1122 00:40:05,861 --> 00:40:08,117 Dous, catro, seis, oito, 10, 12. 1123 00:40:08,117 --> 00:40:10,200 Un científico da computación sería entender, agarde un minuto, 1124 00:40:10,200 --> 00:40:12,320 que é da orde de n dividido por dous pasos. 1125 00:40:12,320 --> 00:40:12,820 Non? 1126 00:40:12,820 --> 00:40:14,444 Porque eu estou facendo dúas persoas de cada vez. 1127 00:40:14,444 --> 00:40:17,015 Pero imos ignorar estes termos de orde máis baixa, 1128 00:40:17,015 --> 00:40:19,140 e nós só estamos indo a xogue fóra a dividir por 2, 1129 00:40:19,140 --> 00:40:21,830 e só dicir, gran O n para ese algoritmo ben. 1130 00:40:21,830 --> 00:40:22,760 >> Que tal un regalo? 1131 00:40:22,760 --> 00:40:26,170 Imos saltar algúns destes, pero o que era un algoritmo que se rexistro de n? 1132 00:40:26,170 --> 00:40:29,900 Isto levou preto de log n pasos? 1133 00:40:29,900 --> 00:40:30,870 O dividir e conquistar. 1134 00:40:30,870 --> 00:40:31,369 Exactamente. 1135 00:40:31,369 --> 00:40:33,900 Como o exemplo do libro de teléfono en semana cero e hoxe cedo, 1136 00:40:33,900 --> 00:40:36,191 onde dividimos o problema de novo e de novo e de novo. 1137 00:40:36,191 --> 00:40:39,070 Nós chamou-o sobre a placa a semana cero como unha liña verde curvado, 1138 00:40:39,070 --> 00:40:41,460 e dixemos que día era un algoritmo logarítmica. 1139 00:40:41,460 --> 00:40:44,970 >> E, de feito, o número de pasos leva a cabo dividir e conquistar, 1140 00:40:44,970 --> 00:40:48,610 ou busca binaria como nós imos comezar chamando-o, como no libro de teléfono, 1141 00:40:48,610 --> 00:40:50,680 é da orde de rexistro e etapas. 1142 00:40:50,680 --> 00:40:52,470 E iso é un pouco de un estraño. 1143 00:40:52,470 --> 00:40:54,910 >> Que leva unha única etapa, ou máis especificamente 1144 00:40:54,910 --> 00:40:56,240 un número constante de pasos? 1145 00:40:56,240 --> 00:40:58,865 Quizais sexa dous, é posible que tres, pero un científico da computación só 1146 00:40:58,865 --> 00:41:01,423 simplifica-lo tan grande O de 1, un número constante de pasos. 1147 00:41:01,423 --> 00:41:04,256 ¿Que é algo que podería facelo ten un número constante de pasos? 1148 00:41:04,256 --> 00:41:08,030 1149 00:41:08,030 --> 00:41:10,930 >> Cal é o tempo de execución de aplaudir? 1150 00:41:10,930 --> 00:41:11,920 Tempo constante. 1151 00:41:11,920 --> 00:41:12,420 Non? 1152 00:41:12,420 --> 00:41:15,490 Como, cal é o tempo de execución de facer algo que leva só un 1153 00:41:15,490 --> 00:41:18,570 operación, como imprimir F Ola Mundo. 1154 00:41:18,570 --> 00:41:24,110 Isto pode ser considerado constante de tempo, a non ser que menos se esquina coa impresión F, 1155 00:41:24,110 --> 00:41:28,260 O que o tempo de execución de impresión F realmente ser? 1156 00:41:28,260 --> 00:41:28,790 E por que? 1157 00:41:28,790 --> 00:41:30,550 ¿Que é de medición n nese caso? 1158 00:41:30,550 --> 00:41:32,251 >> Audiencia: [inaudível]. 1159 00:41:32,251 --> 00:41:33,250 DAVID J. Malan: Exactamente. 1160 00:41:33,250 --> 00:41:34,900 O número de caracteres que desexa imprimir. 1161 00:41:34,900 --> 00:41:36,191 Polo tanto, é moi sensible ao contexto. 1162 00:41:36,191 --> 00:41:39,910 Hoxe, temos que chegou a apostar moito en letras e números aquí no consello. 1163 00:41:39,910 --> 00:41:43,540 Pero tamén pode ser caracteres nunha secuencia real. 1164 00:41:43,540 --> 00:41:46,420 Así, verifícase aí é outra medida que vai comezar a preocuparse, 1165 00:41:46,420 --> 00:41:48,530 e iso é o oposto de gran O, por así dicir. 1166 00:41:48,530 --> 00:41:50,120 >> Isto é notación omega. 1167 00:41:50,120 --> 00:41:53,380 Tendo en conta que gran O significa o que é, o un límite superior ao seu tempo de execución? 1168 00:41:53,380 --> 00:41:55,580 Como máximo, canto tempo pode tomar algo? 1169 00:41:55,580 --> 00:41:59,250 Omega-- Sentímolo este segue vindo up-- é o contrario do que, 1170 00:41:59,250 --> 00:42:02,960 polo que é un límite inferior na cantidade de tempo algo pode tomar. 1171 00:42:02,960 --> 00:42:10,480 >> So. por exemplo, o que é un algoritmo que toma medidas sempre n ao cadrado? 1172 00:42:10,480 --> 00:42:15,600 Ben, un dos algoritmos que vimos Hoxe en día, de feito, pode ser que como ben. 1173 00:42:15,600 --> 00:42:16,720 Tipo de selección. 1174 00:42:16,720 --> 00:42:18,270 Selección tipo é moi estúpido. 1175 00:42:18,270 --> 00:42:21,760 Aínda que o algorithm-- Sentímolo, mesmo a matriz xa está clasificado, 1176 00:42:21,760 --> 00:42:24,150 selección tipo vai manter unha curta andaina a través da lista 1177 00:42:24,150 --> 00:42:28,907 para asegurarse de que ten o menor elemento novo e de novo e de novo. 1178 00:42:28,907 --> 00:42:31,740 E aínda que o ser humano no público sabe diso, agarde un minuto, 1179 00:42:31,740 --> 00:42:33,948 xa pasou o elemento máis pequeno, o ordenador 1180 00:42:33,948 --> 00:42:37,300 non sabe que ata parecer todo o camiño a través da lista. 1181 00:42:37,300 --> 00:42:40,240 Do mesmo xeito, un límite inferior que Tamén pode ser tida en conta 1182 00:42:40,240 --> 00:42:42,000 quizais sexa tempo lineal. 1183 00:42:42,000 --> 00:42:48,260 >> Canto tempo leva a elementos tipo n no mellor 1184 00:42:48,260 --> 00:42:52,420 caso usando algo bubble sort? 1185 00:42:52,420 --> 00:42:54,280 Supoñamos que a súa lista xa está clasificado. 1186 00:42:54,280 --> 00:42:56,696 Dixemos bubble sort asume da orde de n ao cadrado etapas. 1187 00:42:56,696 --> 00:42:59,640 Pero e se xa está clasificado? 1188 00:42:59,640 --> 00:43:02,310 E se entender despois un paso a través da matriz 1189 00:43:02,310 --> 00:43:03,540 que fixo hai swaps? 1190 00:43:03,540 --> 00:43:05,970 Debe seguir facendo máis pases? 1191 00:43:05,970 --> 00:43:06,470 >> Non. 1192 00:43:06,470 --> 00:43:10,340 Así, un límite inferior na bubble sort se pode dicir para ser lineal. 1193 00:43:10,340 --> 00:43:11,830 Omega de n. 1194 00:43:11,830 --> 00:43:14,450 E podemos ollar para outros destes tamén. 1195 00:43:14,450 --> 00:43:17,990 Entón, imos dar un ollo rápida en só unha vista aquí 1196 00:43:17,990 --> 00:43:20,790 para ver como estes se distinguen. 1197 00:43:20,790 --> 00:43:24,592 Eu estou indo a ir para abaixo aquí neste A páxina que está dispoñible na páxina web do C50, 1198 00:43:24,592 --> 00:43:27,550 pero vai ser unha dor de comezar a traballar, xa que utiliza unha tecnoloxía chamada 1199 00:43:27,550 --> 00:43:30,560 Applets Java, que é un en gran parte sen apoio a día de hoxe, 1200 00:43:30,560 --> 00:43:32,730 polo menos por Chrome e certos outros. 1201 00:43:32,730 --> 00:43:37,070 >> E deixe-me ir adiante e acelerar este e explicar o que está pasando. 1202 00:43:37,070 --> 00:43:40,840 Esta é unha demostración de burbulla tipo, o primeiro algoritmo de nós miramos. 1203 00:43:40,840 --> 00:43:43,950 E é a vista na que cada destas barras representa un número. 1204 00:43:43,950 --> 00:43:45,710 Canto máis longa sexa a barra, canto maior sexa o número. 1205 00:43:45,710 --> 00:43:47,520 Canto menor o bar, Canto menor o número. 1206 00:43:47,520 --> 00:43:50,353 E o que se pode ver visualmente, aínda aínda que este vai super rápido, 1207 00:43:50,353 --> 00:43:53,699 é que a barra vermella é como eu, camiñando cara atrás e resolver problemas. 1208 00:43:53,699 --> 00:43:56,740 Podes ver que os elementos máis grandes son, en realidade burbullas para a dereita, 1209 00:43:56,740 --> 00:43:59,650 e os elementos menores está borbulhando á esquerda. 1210 00:43:59,650 --> 00:44:01,870 E aquí, se nós realmente ollar máis de preto, 1211 00:44:01,870 --> 00:44:04,330 podemos realmente contar o número de comparacións e swaps 1212 00:44:04,330 --> 00:44:05,350 que estaban sendo feitos. 1213 00:44:05,350 --> 00:44:07,360 >> Pero en vez diso, imos ollar no segundo algoritmo 1214 00:44:07,360 --> 00:44:11,240 vimos anteriormente co noso voluntarios, selección de clasificación. 1215 00:44:11,240 --> 00:44:13,500 Visualmente, ten un efecto moi diferente. 1216 00:44:13,500 --> 00:44:16,820 Pero é, de novo, moi intuitivo, en que temos que seleccionar o próximo menor 1217 00:44:16,820 --> 00:44:18,660 elemento, e temos un pouco de sorte. 1218 00:44:18,660 --> 00:44:20,110 Iso foi fundamentalmente máis rápido. 1219 00:44:20,110 --> 00:44:22,840 Pero se nós corremos ese novo e de novo e de novo con moitos insumos, 1220 00:44:22,840 --> 00:44:26,680 veriamos que é de feito aínda en gran O n ao cadrado. 1221 00:44:26,680 --> 00:44:29,920 >> Imos facer un último aquí, ordenación por inserción, 1222 00:44:29,920 --> 00:44:33,180 que foi o terceiro algoritmo nós miramos, ea recordo 1223 00:44:33,180 --> 00:44:36,700 que este trata sobre a como elementos que atopa-los, 1224 00:44:36,700 --> 00:44:39,290 Pero, entón, quizais quendas cousas para abrir espazo, 1225 00:44:39,290 --> 00:44:41,660 inserción de elementos a que pertencen. 1226 00:44:41,660 --> 00:44:45,330 >> E iso tamén acaba dando o resultado final. Agora todos os tres dos 1227 00:44:45,330 --> 00:44:46,490 sentín moi rápido. 1228 00:44:46,490 --> 00:44:48,740 E, de feito, eu execute a eles nun bo clip. 1229 00:44:48,740 --> 00:44:52,510 Pero, fundamentalmente, son todos ben horrible, para ser honesto. 1230 00:44:52,510 --> 00:44:56,960 Todos estes algoritmos ata agora que son executados en gran O n ao cadrado 1231 00:44:56,960 --> 00:44:59,270 tomar un pouco de tempo para ser executado ao final. 1232 00:44:59,270 --> 00:45:01,920 >> E, de feito, podemos ver e sinto que este, por último, 1233 00:45:01,920 --> 00:45:04,090 se eu puxar arriba esta terceira e última demostración. 1234 00:45:04,090 --> 00:45:05,840 Este é outro visualización que está a suceder 1235 00:45:05,840 --> 00:45:08,500 para mostrar bubble sort á esquerda, tipo de selección no medio, 1236 00:45:08,500 --> 00:45:13,410 e algo, como un dos nosos man levanta antes suxeriu, 1237 00:45:13,410 --> 00:45:15,020 merge sort á dereita. 1238 00:45:15,020 --> 00:45:16,937 Un dividir e conquistar estratexia da dereita. 1239 00:45:16,937 --> 00:45:19,520 E iso é, en realidade, o que somos indo ollar o mércores. 1240 00:45:19,520 --> 00:45:21,990 Pero o tempo estes funcionen en paralelo imos. 1241 00:45:21,990 --> 00:45:26,765 É máis ou menos o mesmo número de elementos, todo rodando á vez. 1242 00:45:26,765 --> 00:45:30,940 1243 00:45:30,940 --> 00:45:34,440 Bubble sort vs selección tipo vs merge sort. 1244 00:45:34,440 --> 00:45:36,760 >> Agora, eles están todos correndo en teoría, ao mesmo tempo. 1245 00:45:36,760 --> 00:45:39,830 A CPU está en execución en a mesma velocidade, pero 1246 00:45:39,830 --> 00:45:44,014 Pode sentir-se como aburrido que é indo moi rápido para facer, 1247 00:45:44,014 --> 00:45:45,930 e quão rápido cando nós inxectar un pouco de semana 1248 00:45:45,930 --> 00:45:49,330 algoritmos de cero pode que acelerar as cousas. 1249 00:45:49,330 --> 00:45:51,760 >> E agora imos comparar estes nunha última forma. 1250 00:45:51,760 --> 00:45:55,710 Eu estou indo a ir adiante para o sitio web do CS50, onde 1251 00:45:55,710 --> 00:45:59,020 temos este elo final para hoxe, onde alguén en internet 1252 00:45:59,020 --> 00:46:03,960 xentilmente montar un vídeo que capta o que ordenación diferente 1253 00:46:03,960 --> 00:46:07,510 algoritmos soan como. 1254 00:46:07,510 --> 00:46:09,577 Esta é a ordenación por inserción. 1255 00:46:09,577 --> 00:46:12,072 >> [Bipé] 1256 00:46:12,072 --> 00:46:13,070 1257 00:46:13,070 --> 00:46:16,850 >> A través do cal está aplicando unha frecuencia con base na altura da barra de ferramentas. 1258 00:46:16,850 --> 00:46:19,826 Esta é bubble sort. 1259 00:46:19,826 --> 00:46:21,822 >> [Bipé Warped] 1260 00:46:21,822 --> 00:46:33,299 1261 00:46:33,299 --> 00:46:45,774 >> Chegando preto é-- benvida xunto especie selección é--, 1262 00:46:45,774 --> 00:46:48,820 onde unha vez máis, estamos seleccionando o seguinte elemento máis pequeno, 1263 00:46:48,820 --> 00:46:51,820 e podemos velo crecer de esquerda a dereita. 1264 00:46:51,820 --> 00:47:01,120 1265 00:47:01,120 --> 00:47:04,000 >> Merge sort, o noso gañador, ata agora, hoxe. 1266 00:47:04,000 --> 00:47:09,659 1267 00:47:09,659 --> 00:47:12,450 Observe como está dividindo as cousas en [inaudível] a metade e trimestres. 1268 00:47:12,450 --> 00:47:17,510 1269 00:47:17,510 --> 00:47:21,660 Tipo Gnome, que non ten falou, e crea visualmente 1270 00:47:21,660 --> 00:47:24,450 e audally un pouco de forma e son diferente. 1271 00:47:24,450 --> 00:47:27,060 1272 00:47:27,060 --> 00:47:30,160 Indo e volvendo, limpar as cousas. 1273 00:47:30,160 --> 00:47:32,230 Tamén check out heapsort na páxina web do cara. 1274 00:47:32,230 --> 00:47:36,100 1275 00:47:36,100 --> 00:47:36,810 >> E é iso. 1276 00:47:36,810 --> 00:47:38,210 Imos velo a próxima vez. 1277 00:47:38,210 --> 00:47:42,647 1278 00:47:42,647 --> 00:47:48,334 >> [Whooshing E MÚSICA] 1279 00:47:48,334 --> 00:50:24,839