1 00:00:00,000 --> 00:00:11,100 >> [REPRODUCCIÓN DE MÚSICA] 2 00:00:11,100 --> 00:00:11,490 >> DAVID J. MALAN: Muy bien. 3 00:00:11,490 --> 00:00:12,170 Así que bienvenidos de nuevo. 4 00:00:12,170 --> 00:00:15,180 Esto es CS50, y el IS Al final de la tercera semana. 5 00:00:15,180 --> 00:00:17,770 >> Así que recuerda, en las últimas semanas, hemos pasado un poco de 6 00:00:17,770 --> 00:00:20,820 tiempo en C, en la programación, en la sintaxis. 7 00:00:20,820 --> 00:00:24,680 Y es muy normal, si usted todavía está luchando con problemas n 2, para ser 8 00:00:24,680 --> 00:00:25,950 golpearse la cabeza contra la pared. 9 00:00:25,950 --> 00:00:28,310 Es mensajes de error crípticos buscando y los errores que 10 00:00:28,310 --> 00:00:29,220 no puedo perseguir. 11 00:00:29,220 --> 00:00:32,310 Porque, puede estar seguro, que en tan sólo un tiempo de algunas semanas que mirar hacia atrás en 12 00:00:32,310 --> 00:00:35,930 cosas como César, y [? V-Genair,?] tal vez incluso de grietas y 13 00:00:35,930 --> 00:00:40,050 darse cuenta de lo lejos que ha llegado en un corto período de tiempo. 14 00:00:40,050 --> 00:00:43,670 Así que si te sirve de consuelo, colgar en él por ahora. 15 00:00:43,670 --> 00:00:46,610 >> Hoy, sin embargo, empezamos a transición a las cosas de alto nivel. 16 00:00:46,610 --> 00:00:49,820 Y empezamos a dar por sentado que ustedes saben cómo programar, o por lo 17 00:00:49,820 --> 00:00:52,090 menos los inicios de ese nivel de comodidad. 18 00:00:52,090 --> 00:00:56,520 Y vamos a empezar a considerar cómo podemos ir sobre el diseño de programas más 19 00:00:56,520 --> 00:00:57,440 efectivamente. 20 00:00:57,440 --> 00:01:01,090 ¿Cómo podemos ir sobre la optimización de la eficiencia de los algoritmos, y 21 00:01:01,090 --> 00:01:03,110 la solución generalmente más problemas interesantes. 22 00:01:03,110 --> 00:01:06,850 Y comenzando a dar por sentado que, si quisiéramos, podríamos codificar cualquier 23 00:01:06,850 --> 00:01:08,350 de los ejemplos que tenemos en mente. 24 00:01:08,350 --> 00:01:11,430 Así que hoy, nosotros no tocamos el teclado para cualquier tipo de código. 25 00:01:11,430 --> 00:01:15,150 Será nivel mucho más alto, y en última instancia, sobre la resolución de problemas. 26 00:01:15,150 --> 00:01:20,490 >> Así que para llegar a ese punto, permítanme proponer que los siguientes siete 27 00:01:20,490 --> 00:01:24,290 rectángulos representan siete puertas, detrás de que son un montón de 28 00:01:24,290 --> 00:01:26,340 números, entre los cuales es el número 50. 29 00:01:26,340 --> 00:01:30,470 Permítanme proyecto esta en esta Aquí la pantalla también. 30 00:01:30,470 --> 00:01:36,770 Y proponemos que necesitamos un voluntario que ayudarme a encontrar un número delante de 31 00:01:36,770 --> 00:01:38,140 el Internet para ver. 32 00:01:38,140 --> 00:01:40,755 Vamos arriba, en la rosa. 33 00:01:40,755 --> 00:01:43,050 Está bien. 34 00:01:43,050 --> 00:01:43,930 ¿Cómo te llamas? 35 00:01:43,930 --> 00:01:44,850 >> JENNIFER: [inaudible] 36 00:01:44,850 --> 00:01:45,170 >> DAVID J. MALAN: Lo siento? 37 00:01:45,170 --> 00:01:45,860 >> JENNIFER: Jennifer. 38 00:01:45,860 --> 00:01:46,390 >> DAVID J. MALAN: Jennifer. 39 00:01:46,390 --> 00:01:46,980 Muy bien, Jennifer. 40 00:01:46,980 --> 00:01:47,630 Gusto en conocerlo. 41 00:01:47,630 --> 00:01:48,370 Vamos arriba. 42 00:01:48,370 --> 00:01:52,430 Así que estas aquí hay siete puertas, y lo que Me gustaría que usted pueda hacer por nosotros aquí, 43 00:01:52,430 --> 00:01:56,560 frente a todos sus compañeros de clase, nosotros es encontrar el número, 50. 44 00:01:56,560 --> 00:02:00,860 Para encontrar un número, puede mirar detrás cualquiera de estas puertas con un simple toque 45 00:02:00,860 --> 00:02:03,030 en una de las puertas, y se revelará su número. 46 00:02:03,030 --> 00:02:06,080 Y vamos a ver lo rápido que nos puede encontrar el número, 50. 47 00:02:06,080 --> 00:02:09,979 48 00:02:09,979 --> 00:02:11,229 >> 15. 49 00:02:11,229 --> 00:02:13,110 50 00:02:13,110 --> 00:02:14,360 16. 51 00:02:14,360 --> 00:02:16,270 52 00:02:16,270 --> 00:02:16,530 50. 53 00:02:16,530 --> 00:02:17,350 Muy bien hecho. 54 00:02:17,350 --> 00:02:18,040 Está bien. 55 00:02:18,040 --> 00:02:19,906 Ronda de aplausos para Jennifer. 56 00:02:19,906 --> 00:02:21,530 >> [Aplausos] 57 00:02:21,530 --> 00:02:22,320 >> Está bien. 58 00:02:22,320 --> 00:02:25,254 Entonces, ¿cuál fue su estrategia para encontrar el número, 50? 59 00:02:25,254 --> 00:02:27,222 >> JENNIFER: Um, pensé que tal vez si - 60 00:02:27,222 --> 00:02:27,714 [Inaudible] 61 00:02:27,714 --> 00:02:28,206 >> DAVID J. MALAN: Oh. 62 00:02:28,206 --> 00:02:29,630 Déle un segundo. 63 00:02:29,630 --> 00:02:32,420 Así fue su estrategia para encontrar el número, 50? 64 00:02:32,420 --> 00:02:34,760 >> JENNIFER: Así que acabo de empezar en el empezando a ver lo que el primer número 65 00:02:34,760 --> 00:02:38,590 estaba, y entonces pensé, tal vez si que están ordenados, que voy a seguir 66 00:02:38,590 --> 00:02:39,970 tocando más arriba? 67 00:02:39,970 --> 00:02:40,140 >> DAVID J. MALAN: OK. 68 00:02:40,140 --> 00:02:42,910 Y parece que hemos encontrado que ese sea el caso. 69 00:02:42,910 --> 00:02:45,670 Aunque, vamos a pelar las capas sólo un poco, y quieres ir 70 00:02:45,670 --> 00:02:47,640 adelante y revelar las otras puertas que podría haber elegido? 71 00:02:47,640 --> 00:02:50,400 72 00:02:50,400 --> 00:02:51,712 >> JENNIFER: Oh, querido. 73 00:02:51,712 --> 00:02:53,128 >> DAVID J. MALAN: Ah. 74 00:02:53,128 --> 00:02:54,280 >> JENNIFER: Así que tuve suerte. 75 00:02:54,280 --> 00:02:55,270 >> DAVID J. MALAN: ¿Así que tuvo suerte. 76 00:02:55,270 --> 00:02:55,710 Está bien. 77 00:02:55,710 --> 00:02:56,795 Así que no está mal. 78 00:02:56,795 --> 00:02:58,750 Pero eso es una interesante visión, ¿no? 79 00:02:58,750 --> 00:03:01,870 Si usted asumió, y lo hizo llegar, de hecho, un poco de suerte allí. 80 00:03:01,870 --> 00:03:05,350 Pero si se supone que las cifras eran ordenados, ¿puedes ser más precisos 81 00:03:05,350 --> 00:03:08,750 cuanto a la forma en que influyó su comportamiento? 82 00:03:08,750 --> 00:03:11,715 >> JENNIFER: Así que si ellos fueron ordenados, me pensé que tal vez menor a mayor. 83 00:03:11,715 --> 00:03:11,970 >> DAVID J. MALAN: OK. 84 00:03:11,970 --> 00:03:15,260 >> JENNIFER: O si esto terminó siendo muy grande, entonces mayor a menor. 85 00:03:15,260 --> 00:03:15,540 >> DAVID J. MALAN: OK. 86 00:03:15,540 --> 00:03:18,170 Así mayor a menor, o menor a mayor. 87 00:03:18,170 --> 00:03:21,990 Pero permítanme proponer, suponga que tiene conseguido de mala suerte, y supongamos que 88 00:03:21,990 --> 00:03:26,840 no eran, de hecho, ordenados, ¿cuántos de esas puertas puede ser que le han tenido que echar un vistazo 89 00:03:26,840 --> 00:03:28,590 detrás en que peor de los casos? 90 00:03:28,590 --> 00:03:29,860 >> JENNIFER: Todos ellos. 91 00:03:29,860 --> 00:03:30,420 >> DAVID J. MALAN: Todos ellos. 92 00:03:30,420 --> 00:03:31,740 Así que vamos a generalizar eso como n. 93 00:03:31,740 --> 00:03:34,790 Sucede que hay 7, pero a dejar más en general, dicen que hay n puertas en el 94 00:03:34,790 --> 00:03:35,650 Aquí la pantalla. 95 00:03:35,650 --> 00:03:40,110 Así que en el peor de los casos, usted tendría que para mirar detrás de 7 puertas, o puertas n. 96 00:03:40,110 --> 00:03:44,140 Y por lo que este es en realidad, es un poco de suerte hoy, pero en realidad es una relación lineal 97 00:03:44,140 --> 00:03:46,440 algoritmo de clases, a pesar de que eran una especie de saltar alrededor. 98 00:03:46,440 --> 00:03:47,080 ¿Es eso justo? 99 00:03:47,080 --> 00:03:47,500 >> JENNIFER: Si. 100 00:03:47,500 --> 00:03:50,000 >> DAVID J. MALAN: Bueno, déjame ver si su estrategia cambia si nos mueven a 101 00:03:50,000 --> 00:03:52,190 nuestro segundo ejemplo aquí con 7 puertas diferentes. 102 00:03:52,190 --> 00:03:55,240 Los mismos números, pero esto momento en que se ordenan. 103 00:03:55,240 --> 00:03:58,350 ¿Cuál es su estrategia de aquí va a ser, tratando de poner fuera de su mente lo que 104 00:03:58,350 --> 00:03:59,310 los otros números eran - 105 00:03:59,310 --> 00:03:59,930 >> JENNIFER: OK. 106 00:03:59,930 --> 00:04:02,290 >> DAVID J. MALAN: - antes? 107 00:04:02,290 --> 00:04:03,180 >> JENNIFER: Vamos a empezar con el primero. 108 00:04:03,180 --> 00:04:03,540 >> DAVID J. MALAN: Muy bien. 109 00:04:03,540 --> 00:04:05,190 Comience con la primera. 110 00:04:05,190 --> 00:04:05,960 4. 111 00:04:05,960 --> 00:04:08,810 Ahora, ¿dónde vas a ir, y por qué? 112 00:04:08,810 --> 00:04:10,040 >> JENNIFER: 4 es realmente pequeño. 113 00:04:10,040 --> 00:04:12,500 Así que si tienen suerte tal vez más pequeño a mayor, lo que debería 114 00:04:12,500 --> 00:04:13,290 ser el doble que, y -. 115 00:04:13,290 --> 00:04:13,670 >> DAVID J. MALAN: OK. 116 00:04:13,670 --> 00:04:15,990 Vamos a ver, que te parece? 117 00:04:15,990 --> 00:04:19,050 >> JENNIFER: Pruebe la última. 118 00:04:19,050 --> 00:04:19,500 Niza. 119 00:04:19,500 --> 00:04:20,880 >> DAVID J. MALAN: Muy bien hecho. 120 00:04:20,880 --> 00:04:21,860 Está bien. 121 00:04:21,860 --> 00:04:23,010 >> [Aplausos] 122 00:04:23,010 --> 00:04:24,310 >> DAVID J. MALAN: OK. 123 00:04:24,310 --> 00:04:26,790 Así que en realidad estás haciendo esto horriblemente, porque eres 124 00:04:26,790 --> 00:04:27,700 haciendo muy bien. 125 00:04:27,700 --> 00:04:31,150 Lo que nos deja incapaces de hacer que algunos puntos. 126 00:04:31,150 --> 00:04:32,565 Así que vamos a tratar de hacer retroceder aquí. 127 00:04:32,565 --> 00:04:34,560 >> JENNIFER: OK. 128 00:04:34,560 --> 00:04:35,980 >> DAVID J. MALAN: Muy bien hecho, no obstante. 129 00:04:35,980 --> 00:04:39,060 Así que comenzó a principios, viste que era 4, entonces usted 130 00:04:39,060 --> 00:04:40,240 trasladado al final. 131 00:04:40,240 --> 00:04:42,320 Pero supongamos que usted no tenga suerte allí, y suponen el 50 132 00:04:42,320 --> 00:04:42,890 estaba en otro lugar. 133 00:04:42,890 --> 00:04:46,190 Lo que su tercer paso ser? 134 00:04:46,190 --> 00:04:47,680 >> JENNIFER: Ir de nuevo al principio. 135 00:04:47,680 --> 00:04:48,320 >> DAVID J. MALAN: Volver al principio. 136 00:04:48,320 --> 00:04:51,320 Aceptar, por lo que le ha tocado esta puerta, que tenía 8 años. 137 00:04:51,320 --> 00:04:51,660 Está bien. 138 00:04:51,660 --> 00:04:52,650 Así que no es 50. 139 00:04:52,650 --> 00:04:55,380 ¿Dónde te has mirado al lado? 140 00:04:55,380 --> 00:04:56,720 >> JENNIFER: Si no lo hiciera saben lo arreglaron. 141 00:04:56,720 --> 00:04:57,005 >> DAVID J. MALAN: Correcto. 142 00:04:57,005 --> 00:04:58,490 Bueno, si lo has hecho sabes fueron ordenados - 143 00:04:58,490 --> 00:04:58,700 >> JENNIFER: Oh, sabía, sí. 144 00:04:58,700 --> 00:05:00,910 >> DAVID J. MALAN: - Pero no lo hiciste saber donde 50 fue todavía? 145 00:05:00,910 --> 00:05:01,785 >> JENNIFER: Sigue adelante. 146 00:05:01,785 --> 00:05:02,130 >> DAVID J. MALAN: Muy bien. 147 00:05:02,130 --> 00:05:02,520 Aceptar. 148 00:05:02,520 --> 00:05:03,800 Sigue adelante. 149 00:05:03,800 --> 00:05:05,270 Bueno, que puedo trabajar. 150 00:05:05,270 --> 00:05:05,610 >> JENNIFER: OK. 151 00:05:05,610 --> 00:05:07,210 >> DAVID J. MALAN: Ahora, si eres va a seguir adelante, ¿cuál es su 152 00:05:07,210 --> 00:05:09,680 involutivo algoritmo retrocedió hasta. 153 00:05:09,680 --> 00:05:10,740 >> JENNIFER: El lineal -. 154 00:05:10,740 --> 00:05:11,820 >> DAVID J. MALAN: Es un poco lineal. 155 00:05:11,820 --> 00:05:13,480 Pero permítanme proponer, y mucho me pongo en el lugar. 156 00:05:13,480 --> 00:05:14,900 Déjeme refrescarle la página. 157 00:05:14,900 --> 00:05:17,120 mismo número, la misma disposición, mismas puertas. 158 00:05:17,120 --> 00:05:21,350 Pero piense de nuevo a ese primer día en cuando la clase rompimos una guía telefónica en 159 00:05:21,350 --> 00:05:25,480 medio, más o menos, y lo que era nuestra estrategia allí? 160 00:05:25,480 --> 00:05:26,450 >> JENNIFER: Comience en el centro. 161 00:05:26,450 --> 00:05:26,690 >> DAVID J. MALAN: OK. 162 00:05:26,690 --> 00:05:27,610 Así que empieza en el centro. 163 00:05:27,610 --> 00:05:28,790 Así que vamos a seguir adelante y simularlo. 164 00:05:28,790 --> 00:05:30,720 Comience en el centro de revelando esa puerta. 165 00:05:30,720 --> 00:05:31,660 Así que el número 16. 166 00:05:31,660 --> 00:05:35,290 Entonces, ¿cuál sería el tipo fuerte haber hecho, que arrancó el libro de teléfono a la mitad, 167 00:05:35,290 --> 00:05:38,450 para llegar a la siguiente conjetura? 168 00:05:38,450 --> 00:05:39,400 >> JENNIFER: Ir en este medio. 169 00:05:39,400 --> 00:05:41,700 >> DAVID J. MALAN: ¿Y por qué a la derecha? 170 00:05:41,700 --> 00:05:43,900 >> JENNIFER: Si fueran una especie de pequeño a más grande, a continuación, 50 debe ser 171 00:05:43,900 --> 00:05:44,720 en ese extremo. 172 00:05:44,720 --> 00:05:44,920 >> DAVID J. MALAN: Good. 173 00:05:44,920 --> 00:05:45,390 Totalmente razonable. 174 00:05:45,390 --> 00:05:48,380 Así como un directorio telefónico, usted va a la derecha en oposición a la izquierda, pero aquí 175 00:05:48,380 --> 00:05:49,500 es la conclusión clave. 176 00:05:49,500 --> 00:05:53,930 Ahora puede tirar, o arrancar, medio de este problema, no dejándote 177 00:05:53,930 --> 00:05:55,970 con 7 puertas, pero en realidad con sólo 3. 178 00:05:55,970 --> 00:05:57,870 Lo cual es más o menos la mitad de la tamaño del problema. 179 00:05:57,870 --> 00:05:58,350 Está bien. 180 00:05:58,350 --> 00:06:01,890 Así que ahora lo que tendría hecho después de que usted vaya a la derecha? 181 00:06:01,890 --> 00:06:05,870 >> JENNIFER: Entonces 16 es todavía muy pequeña, en relación con el 50, así que tal vez voy a intentar, 182 00:06:05,870 --> 00:06:06,700 similar, esta. 183 00:06:06,700 --> 00:06:07,890 >> DAVID J. MALAN: Muy bien. 184 00:06:07,890 --> 00:06:08,720 42. 185 00:06:08,720 --> 00:06:10,830 Muy bien, así que ahora ¿cuál es su instinto que le dice? 186 00:06:10,830 --> 00:06:12,100 >> JENNIFER: puedo tirar esto y luego simplemente - 187 00:06:12,100 --> 00:06:12,360 >> DAVID J. MALAN: OK. 188 00:06:12,360 --> 00:06:14,212 Bueno, usted puede tirar la mitad izquierda allí. 189 00:06:14,212 --> 00:06:14,890 >> JENNIFER: - elegir este. 190 00:06:14,890 --> 00:06:15,530 >> DAVID J. MALAN: Y de la derecha. 191 00:06:15,530 --> 00:06:15,760 >> JENNIFER: Si. 192 00:06:15,760 --> 00:06:17,820 >> DAVID J. MALAN: Así que, aunque es difícil para ver tal vez, cuando sólo hay 193 00:06:17,820 --> 00:06:21,320 7 puertas, pensar, ahora, la consistencia de la 194 00:06:21,320 --> 00:06:22,620 algoritmo que acaba de aplicar. 195 00:06:22,620 --> 00:06:24,510 En el caso anterior, lo hiciste que tenga suerte, que era genial. 196 00:06:24,510 --> 00:06:26,540 Pero usted ha utilizado un heurístico, Yo diría. 197 00:06:26,540 --> 00:06:29,150 Solías especie de sus instintos, y saber lo resuelto, si es bastante 198 00:06:29,150 --> 00:06:31,600 pequeña al principio, obviamente, tenemos tiene que ir más a la derecha. 199 00:06:31,600 --> 00:06:34,990 Pero, en cierto sentido, tienes suerte, porque tal vez este era el número 100, 200 00:06:34,990 --> 00:06:36,220 y tal vez 50 era más en el medio. 201 00:06:36,220 --> 00:06:37,910 Tal vez 50 fue aún más de aquí. 202 00:06:37,910 --> 00:06:40,960 >> Pero lo que hizo un poco diferente esta vez fue, que hizo lo mismo 203 00:06:40,960 --> 00:06:42,150 una y otra vez. 204 00:06:42,150 --> 00:06:45,310 Y yo diría que lo que acabas de hizo, aunque influido por el teléfono 205 00:06:45,310 --> 00:06:48,100 ejemplo del libro, es algo mucho más algorítmica, y mucho 206 00:06:48,100 --> 00:06:49,930 menos especial funda. 207 00:06:49,930 --> 00:06:51,620 Mucho menos instintivo. 208 00:06:51,620 --> 00:06:57,160 Así que al final del día, ¿cómo usted describe la eficiencia de la 209 00:06:57,160 --> 00:07:00,530 primer algoritmo, donde fuiste izquierda a derecha, frente a la 210 00:07:00,530 --> 00:07:03,430 segundo algoritmo aquí? 211 00:07:03,430 --> 00:07:06,460 >> JENNIFER: Éste debe, al igual que, tal vez reducir a la mitad el tiempo, o incluso más, sí. 212 00:07:06,460 --> 00:07:07,320 >> DAVID J. MALAN: OK, tal vez incluso más. 213 00:07:07,320 --> 00:07:10,150 Vamos a empujar un poco más duro en eso. 214 00:07:10,150 --> 00:07:13,030 Lo que realmente, si seguimos esta lógica, definitivamente reducido a la mitad el 215 00:07:13,030 --> 00:07:15,830 tiempo de funcionamiento con este segundo algoritmo por tirar la mitad de la 216 00:07:15,830 --> 00:07:18,470 números, pero ¿qué hicimos en la siguiente iteración, cuando Jennifer reveló 217 00:07:18,470 --> 00:07:20,615 el segundo número? 218 00:07:20,615 --> 00:07:22,830 >> Hemos reducido a la mitad el número de puertas de nuevo. 219 00:07:22,830 --> 00:07:25,270 Y entonces, ¿qué hicimos después de eso, si había más puertas para jugar? 220 00:07:25,270 --> 00:07:27,520 Queremos reducir a la mitad, y de nuevo, y otra vez, y otra vez. 221 00:07:27,520 --> 00:07:30,420 Y esto era como ustedes todos de pie en la primera semana de 222 00:07:30,420 --> 00:07:33,000 clase, la mitad de ustedes sentado, medio de ustedes sentados, la mitad de ustedes 223 00:07:33,000 --> 00:07:35,440 sentarse, hasta que un solitario alma estaba de pie. 224 00:07:35,440 --> 00:07:39,050 Y dijimos que el tiempo de ejecución de que, el número de pasos que tomó era 225 00:07:39,050 --> 00:07:40,430 en el orden de lo que? 226 00:07:40,430 --> 00:07:41,230 >> ALTAVOZ 1: [inaudible] 227 00:07:41,230 --> 00:07:43,970 >> DAVID J. MALAN: Entonces ingrese base 2 de n, o simplemente más simplemente, registro de n. 228 00:07:43,970 --> 00:07:45,060 Así que algo logarítmica. 229 00:07:45,060 --> 00:07:48,380 Y la gráfica no era una línea recta que acaba de conseguir en peor, que era 230 00:07:48,380 --> 00:07:52,490 esta curva interesante que no lo hizo conseguir tan mal con el tiempo. 231 00:07:52,490 --> 00:07:53,910 Así que vamos a aferrarse a esta idea. 232 00:07:53,910 --> 00:07:54,690 Demos gracias a Jennifer. 233 00:07:54,690 --> 00:07:56,150 Muchas gracias por venir en adelante. 234 00:07:56,150 --> 00:07:57,400 Y, un segundo. 235 00:07:57,400 --> 00:08:00,170 236 00:08:00,170 --> 00:08:02,925 No lámparas de escritorio de hoy, pero que sí tienen CS50 bolas de la tensión. 237 00:08:02,925 --> 00:08:03,420 >> JENNIFER: Yay. 238 00:08:03,420 --> 00:08:04,410 >> DAVID J. MALAN: Muy bien, aquí. 239 00:08:04,410 --> 00:08:06,545 Gracias por incurrir en el estrés aquí. 240 00:08:06,545 --> 00:08:07,350 Está bien. 241 00:08:07,350 --> 00:08:10,620 Así que veamos si no podemos ahora formalizar este un poco más. 242 00:08:10,620 --> 00:08:14,820 Así que de nuevo, lo que hicimos fue esencialmente lo mismo que hicimos 243 00:08:14,820 --> 00:08:16,660 en que primera semana. 244 00:08:16,660 --> 00:08:23,780 Pero en lugar de terminar con sólo un lineal algoritmo, que hemos representado 245 00:08:23,780 --> 00:08:27,210 previamente como esta línea recta, por lo que, si ponemos una puerta más en 246 00:08:27,210 --> 00:08:29,610 la pantalla, a continuación, Jennifer haría han tenido que buscar, potencialmente, 247 00:08:29,610 --> 00:08:30,600 detrás de una puerta más. 248 00:08:30,600 --> 00:08:33,490 Si ponemos dos puertas más, ella podría tener para mirar detrás de dos puertas más. 249 00:08:33,490 --> 00:08:35,990 >> Y así, había un lineal relación entre el tamaño de la 250 00:08:35,990 --> 00:08:39,059 problema en, por ejemplo, el eje x, y la cantidad de tiempo que se necesita para 251 00:08:39,059 --> 00:08:40,440 resolver en la y. 252 00:08:40,440 --> 00:08:43,330 Pero el cuadro que estaba aludiendo a antes era esta línea verde. 253 00:08:43,330 --> 00:08:45,970 Verde deliberadamente, porque se sentía mejor. 254 00:08:45,970 --> 00:08:49,790 En teoría, el algoritmo, cuando lo hicimos con la guía telefónica, cuando lo hicimos 255 00:08:49,790 --> 00:08:52,420 con ustedes contando entre sí, y en el segundo caso, cuando Jennifer sólo 256 00:08:52,420 --> 00:08:55,250 lo hizo aquí, que era una especie de fundamentalmente mejor. 257 00:08:55,250 --> 00:08:57,180 Porque no era sólo el doble de rápido. 258 00:08:57,180 --> 00:08:58,870 No fue hasta cuatro veces más rápido. 259 00:08:58,870 --> 00:09:03,290 Era totalmente dependiente de lo que el tamaño de la entrada era, en cuanto a la cantidad de 260 00:09:03,290 --> 00:09:05,220 medidas que en última instancia llevó. 261 00:09:05,220 --> 00:09:08,040 >> Y así, esta sencilla idea de que todos nos tomó por sentado con el libro de teléfono, 262 00:09:08,040 --> 00:09:10,200 de manera similar puede ser aplicado a algo como esto. 263 00:09:10,200 --> 00:09:12,380 Y esto podría ser más informal conocida como, como puede ser que 264 00:09:12,380 --> 00:09:13,940 imaginar, divide y vencerás. 265 00:09:13,940 --> 00:09:16,390 No muy diferente de lo que hicimos, por supuesto, con la guía telefónica. 266 00:09:16,390 --> 00:09:18,300 >> Pero el pseudocódigo, el recuerdo, era esto. 267 00:09:18,300 --> 00:09:21,800 Así que no vamos a hacer esto de nuevo, pero recuerdo esa primera semana, todos nosotros, se puso de pie 268 00:09:21,800 --> 00:09:25,140 y luego la mitad de ustedes se sentó, la mitad de que se sentó, la mitad de ustedes se sentó. 269 00:09:25,140 --> 00:09:29,280 Ese algoritmo se implementa en un poco de una forma de engaño, en eso, 270 00:09:29,280 --> 00:09:32,870 No era sólo uno de mí contar, fundamentalmente, de manera más eficiente. 271 00:09:32,870 --> 00:09:35,830 En ese caso, fui el aprovechamiento un recurso secundario. 272 00:09:35,830 --> 00:09:39,470 Más o menos, varias CPU, múltiples cerebros, varias personas inteligentes en el 273 00:09:39,470 --> 00:09:42,740 habitación estaban ayudando a conseguir a partir de algo lineal a algo 274 00:09:42,740 --> 00:09:45,190 logarítmica, de algo rojo a algo verde. 275 00:09:45,190 --> 00:09:48,650 >> Pero en este caso, solo Jennifer puede mejorar fundamentalmente de la 276 00:09:48,650 --> 00:09:52,370 el rendimiento de su primer algoritmo por, una vez más, sólo de pensar un poco más difícil. 277 00:09:52,370 --> 00:09:56,650 Y ahora, cuando llega el momento de poner en práctica estas cosas, averiguar 278 00:09:56,650 --> 00:10:00,670 qué líneas de código se puede escribir como que puede repetir de nuevo, y 279 00:10:00,670 --> 00:10:03,350 otra vez, y otra vez, una especie de en una forma de bucle. 280 00:10:03,350 --> 00:10:06,370 Debido a que usted no va a tener la lujo, como Jennifer lo hizo en un primer momento, a 281 00:10:06,370 --> 00:10:10,460 sólo hay un montón de síes y decir: hmm, si este primer número es 4, 282 00:10:10,460 --> 00:10:11,800 déjame saltar todo el camino hasta el final. 283 00:10:11,800 --> 00:10:14,180 Ooh, si ese número es demasiado grande, déjame pasar arbitrariamente de nuevo 284 00:10:14,180 --> 00:10:15,220 para el segundo elemento. 285 00:10:15,220 --> 00:10:18,210 Usted encontrará que esto va a ser mucho más difícil de formalizar lo que los seres humanos 286 00:10:18,210 --> 00:10:21,270 dar por sentado como muy razonable heurística, pero un equipo es sólo 287 00:10:21,270 --> 00:10:23,260 vamos a hacer lo que usted le dice que haga. 288 00:10:23,260 --> 00:10:25,280 >> Ahora bien, esto tiene muy interesante implicaciones. 289 00:10:25,280 --> 00:10:29,950 Esta gráfica es una especie de la intención de una especie de abrumar visualmente, pero cuenta, donde 290 00:10:29,950 --> 00:10:32,230 es la línea recta en esta gráfica? 291 00:10:32,230 --> 00:10:35,330 ¿Dónde está la gráfica lineal que llamamos n? 292 00:10:35,330 --> 00:10:37,580 Bueno, es una especie de hacia la parte inferior de esta imagen, ¿verdad? 293 00:10:37,580 --> 00:10:40,500 Así que todo lo que hemos hecho es que hemos tipo de zoom es el eje x y el 294 00:10:40,500 --> 00:10:44,780 eje y para tratar de tener una idea de lo que otros tipos de curvas parecen. 295 00:10:44,780 --> 00:10:47,760 >> Y los detalles de la matemática expresiones hoy no importa lo que 296 00:10:47,760 --> 00:10:52,440 mucho, pero observe que hay una gran cantidad de algoritmos que son mucho peor que 297 00:10:52,440 --> 00:10:53,470 algo que es lineal. 298 00:10:53,470 --> 00:10:55,410 De hecho, n cubos se ve muy mal. 299 00:10:55,410 --> 00:10:58,400 2 a la n se ve muy mal. n al cuadrado se ve muy mal. 300 00:10:58,400 --> 00:11:01,630 Y vamos a ver lo que algunos de los podría ser en realidad hoy en día. 301 00:11:01,630 --> 00:11:05,430 Y log n no se siente tan mal, pero mejor que n es log base 2 de n. 302 00:11:05,430 --> 00:11:08,080 Pero usted sabe, habría sido aún más sorprendente si Jennifer, o si, 303 00:11:08,080 --> 00:11:12,910 esa primera semana, había llegado con algo que es registro de registro de n. 304 00:11:12,910 --> 00:11:15,880 >> En otras palabras, hay un conjunto gama de posibles soluciones a los 305 00:11:15,880 --> 00:11:18,570 problemas, pero incluso en este caso, el aviso lo que va a suceder. 306 00:11:18,570 --> 00:11:22,910 Cuando hago zoom hacia fuera, ¿cuál de estas curvas va a llegar a ser la absoluta 307 00:11:22,910 --> 00:11:26,630 peor de los que está en la pantalla ahora? 308 00:11:26,630 --> 00:11:28,680 Entonces n cubos ve bastante mal por el momento. 309 00:11:28,680 --> 00:11:32,470 Pero si nos acercamos hacia fuera y ver más de la X y el eje Y, ¿quién va a 310 00:11:32,470 --> 00:11:34,550 dominar en última instancia? 311 00:11:34,550 --> 00:11:37,120 Así que en realidad resulta que 2 a la n, y se puede resolver esto con sólo 312 00:11:37,120 --> 00:11:39,990 enchufando algún cada vez más grande números y verás que 2 a la 313 00:11:39,990 --> 00:11:42,070 n, de hecho, se hace más grande mucho más rápido. 314 00:11:42,070 --> 00:11:45,530 Si realmente nos alejamos, a 2 a la n algoritmo es una mierda absoluta. 315 00:11:45,530 --> 00:11:48,170 Quiero decir que esto va a tomar un poco de tiempo para que el 316 00:11:48,170 --> 00:11:49,460 equipo para batir a través. 317 00:11:49,460 --> 00:11:52,500 >> Pero verás con el tiempo, sobre todo con los futuros boletines de problemas e incluso 318 00:11:52,500 --> 00:11:55,600 proyectos fin de carrera, es sus datos conjunto se hace grande, ¿de acuerdo? 319 00:11:55,600 --> 00:11:58,300 Incluso en la primera versión de Facebook, como el número de amigos, y la 320 00:11:58,300 --> 00:12:01,840 número de usuarios registrados consiguió grandes, se puede ordenar de la misma en el teléfono y 321 00:12:01,840 --> 00:12:05,530 implementar algo con búsqueda lineal, o una clasificación muy simple 322 00:12:05,530 --> 00:12:07,030 algoritmo, como veremos hoy. 323 00:12:07,030 --> 00:12:09,280 Tienes que empezar a pensar más difícil y más difícil acerca de estos problemas. 324 00:12:09,280 --> 00:12:12,070 Y los tipos de problemas de lugares como Facebook y Google, y Microsoft, 325 00:12:12,070 --> 00:12:16,350 y otros trabajan en es exactamente estos Datos especie de gran clase de preguntas 326 00:12:16,350 --> 00:12:18,530 cada vez más en estos días. 327 00:12:18,530 --> 00:12:18,900 >> Está bien. 328 00:12:18,900 --> 00:12:23,800 Así que el éxito de Jennifer en ese segundo algoritmo, francamente, lo hizo increíblemente 329 00:12:23,800 --> 00:12:26,110 bien la primera vez, pero vamos a escribirlo como la suerte para que podamos 330 00:12:26,110 --> 00:12:27,000 puede aclarar este punto. 331 00:12:27,000 --> 00:12:30,970 En el segundo caso, se aprovechó de un algoritmo que repite una y otra 332 00:12:30,970 --> 00:12:34,670 de nuevo, pero ella tomó un concedida cierta suposición de que permitiéramos 333 00:12:34,670 --> 00:12:39,370 , pero ella explotó cierto detalle el segunda vez que ella no tenía la 334 00:12:39,370 --> 00:12:39,840 primera vez. 335 00:12:39,840 --> 00:12:41,800 ¿Qué fue qué? 336 00:12:41,800 --> 00:12:43,050 >> Que la lista se solucionó. 337 00:12:43,050 --> 00:12:46,350 Así que tan pronto como la lista se solucionó, que afirman que Jennifer era capaz de hacer 338 00:12:46,350 --> 00:12:47,480 fundamentalmente mejor. 339 00:12:47,480 --> 00:12:51,450 7 puertas, sí, no es tan interesante, pero supongo que Estamos 7000000 puertas. 340 00:12:51,450 --> 00:12:54,080 Bitácora de n va definitivamente para llevar a cabo mucho, mucho más 341 00:12:54,080 --> 00:12:55,610 más rápido en el largo plazo. 342 00:12:55,610 --> 00:12:58,880 Pero ella tenía que tener la puertas ordenados por ella. 343 00:12:58,880 --> 00:13:02,320 Ahora, me tomé la libertad de hacer eso por adelantado en la pantalla del ordenador 344 00:13:02,320 --> 00:13:05,160 aquí, pero supongo que Jennifer tenía que hacerlo ella misma? 345 00:13:05,160 --> 00:13:10,120 Supongamos que las puertas en cuestión datos representados en una base de datos, o 346 00:13:10,120 --> 00:13:14,260 amigos registrados en Facebook, o ninguna de las páginas web en Internet que 347 00:13:14,260 --> 00:13:16,880 varios sitios web podrían necesitar al índice o buscar de nuevo. 348 00:13:16,880 --> 00:13:20,940 >> Supongamos que usted acaba de tener un datos en bruto establece y se dejó a usted, o para 349 00:13:20,940 --> 00:13:23,010 Jennifer hacer que la clasificación? 350 00:13:23,010 --> 00:13:26,950 Eso, más bien, requiere que respondamos la pregunta, bueno, ¿cuánto tiempo 351 00:13:26,950 --> 00:13:31,080 habría tomado Jennifer, o incluso yo, para ordenar esos números con anticipación para 352 00:13:31,080 --> 00:13:32,680 que podía tomar ventaja de eso? 353 00:13:32,680 --> 00:13:32,880 ¿Cierto? 354 00:13:32,880 --> 00:13:36,620 Debido a la implicación, desde luego, es si me lleva bastante tiempo para ordenar 355 00:13:36,620 --> 00:13:40,800 los números, ¿quién diablos le importa que puede encontrar un número como 50, de manera rápida, 356 00:13:40,800 --> 00:13:44,850 como en el caso de Jennifer, si tenemos más de abrumado la cantidad de tiempo total 357 00:13:44,850 --> 00:13:46,920 tomó por ordenar las cosas por adelantado? 358 00:13:46,920 --> 00:13:49,320 >> Así que veamos si no podemos el pintar el cuadro aquí. 359 00:13:49,320 --> 00:13:51,370 Tengo un montón entero más estrés bolas, si eso ayuda 360 00:13:51,370 --> 00:13:52,270 romper el hielo aquí. 361 00:13:52,270 --> 00:13:55,690 Y si no te importa, nos necesitará de siete voluntarios - 362 00:13:55,690 --> 00:13:57,060 sucesivamente, en Aceptar. 363 00:13:57,060 --> 00:13:57,240 Wow. 364 00:13:57,240 --> 00:13:59,250 Así que no tenemos que gastar en lámparas de escritorio, lo que parece. 365 00:13:59,250 --> 00:13:59,690 Está bien. 366 00:13:59,690 --> 00:14:01,530 Así que ¿qué hay de ustedes dos en el frente. 367 00:14:01,530 --> 00:14:04,160 ¿Qué hay de ustedes dos en la espalda. 368 00:14:04,160 --> 00:14:04,870 Así que eso es cuatro. 369 00:14:04,870 --> 00:14:09,890 ¿Y tú delante cinco, seis y siete. 370 00:14:09,890 --> 00:14:10,320 Ahí mismo. 371 00:14:10,320 --> 00:14:13,260 De tu amigo que lo llevan a cabo, para que pueda obtener el premio. 372 00:14:13,260 --> 00:14:13,700 >> Está bien. 373 00:14:13,700 --> 00:14:14,410 Vamos arriba. 374 00:14:14,410 --> 00:14:17,120 ¿Y por qué no tenemos que chicos vienen para acá. 375 00:14:17,120 --> 00:14:18,960 Yo te voy a dar a cada uno un número. 376 00:14:18,960 --> 00:14:22,150 Y seguir adelante y organizar a sí mismos idéntica a lo que es 377 00:14:22,150 --> 00:14:25,180 representado en la pantalla. 378 00:14:25,180 --> 00:14:26,530 >> [VOCES interponiendo] 379 00:14:26,530 --> 00:14:28,160 >> DAVID J. MALAN: Oop, lo siento. 380 00:14:28,160 --> 00:14:30,210 Bug. 381 00:14:30,210 --> 00:14:32,180 Está bien. 382 00:14:32,180 --> 00:14:32,750 Bueno, aquí vamos. 383 00:14:32,750 --> 00:14:34,180 El número cinco. 384 00:14:34,180 --> 00:14:35,136 El número seis. 385 00:14:35,136 --> 00:14:37,770 Uno, dos, tres, cuatro, cinco, de seis, siete. 386 00:14:37,770 --> 00:14:39,410 Oh, esto es incómodo. 387 00:14:39,410 --> 00:14:41,210 >> ALTAVOZ 2: Voy a buscar a -. 388 00:14:41,210 --> 00:14:41,900 >> DAVID J. MALAN: Good deal. 389 00:14:41,900 --> 00:14:43,130 Está bien. 390 00:14:43,130 --> 00:14:44,611 Gracias por participar. 391 00:14:44,611 --> 00:14:47,200 >> [Aplausos] 392 00:14:47,200 --> 00:14:48,580 >> Aceptar. 393 00:14:48,580 --> 00:14:48,860 Está bien. 394 00:14:48,860 --> 00:14:51,970 Así que tenemos cuatro, dos, seis, uno, tres, siete, cinco. 395 00:14:51,970 --> 00:14:56,010 Perfect así que tenemos siete voluntarios aquí, que son iguales en anchura a la 396 00:14:56,010 --> 00:14:57,430 matriz que estamos jugando con el anterior. 397 00:14:57,430 --> 00:14:59,470 Y elegí siete por razones que será igual 398 00:14:59,470 --> 00:15:00,840 conveniente en un poco. 399 00:15:00,840 --> 00:15:04,400 Y voy a proponer primero que clasificamos estos siete voluntarios. 400 00:15:04,400 --> 00:15:06,786 Si desea, en primer lugar, para saludar sin embargo. 401 00:15:06,786 --> 00:15:08,970 Dado que esto va a ser un incómodas varios minutos. 402 00:15:08,970 --> 00:15:10,370 Dar a conocer a ustedes mismos. 403 00:15:10,370 --> 00:15:10,980 >> GRACE: Hola, soy la Gracia. 404 00:15:10,980 --> 00:15:14,190 Soy un estudiante de segundo año en Leverett House. 405 00:15:14,190 --> 00:15:14,620 >> BRANSON: Hi. 406 00:15:14,620 --> 00:15:15,620 Estoy Branson. 407 00:15:15,620 --> 00:15:16,920 Soy un estudiante de primer año en la soldadura. 408 00:15:16,920 --> 00:15:19,755 409 00:15:19,755 --> 00:15:20,230 >> GABE: Hi. 410 00:15:20,230 --> 00:15:21,040 Estoy Gabe. 411 00:15:21,040 --> 00:15:22,300 Soy un joven en Cabot. 412 00:15:22,300 --> 00:15:24,826 413 00:15:24,826 --> 00:15:25,980 >> NEIL: Soy Neil. 414 00:15:25,980 --> 00:15:29,090 Soy un estudiante de primer año en Matthews. 415 00:15:29,090 --> 00:15:29,550 >> JASON: Soy Jason. 416 00:15:29,550 --> 00:15:32,816 Soy un estudiante de primer año en Greenough. 417 00:15:32,816 --> 00:15:33,700 >> MIKE: Soy Mike. 418 00:15:33,700 --> 00:15:37,360 Soy un estudiante de primer año en Grays. 419 00:15:37,360 --> 00:15:37,990 >> JESS: Soy Jess. 420 00:15:37,990 --> 00:15:40,313 Soy un estudiante de segundo año en Leverett. 421 00:15:40,313 --> 00:15:41,300 >> DAVID J. MALAN: Excelente. 422 00:15:41,300 --> 00:15:41,850 Está bien. 423 00:15:41,850 --> 00:15:44,190 Bueno, gracias a todos nuestros voluntarios aquí hasta ahora. 424 00:15:44,190 --> 00:15:47,110 Y el reto que nos ocupa ahora va siendo para ordenar de estos chicos, pero luego 425 00:15:47,110 --> 00:15:50,250 vamos a tener que pensar un poco tendido sobre la eficiencia con que en realidad 426 00:15:50,250 --> 00:15:51,110 ellos ordenan. 427 00:15:51,110 --> 00:15:52,580 Así que primero vamos a probar esto. 428 00:15:52,580 --> 00:15:55,970 Ustedes pueden ver los números de los otros con sólo colocar alrededor de las esquinas. 429 00:15:55,970 --> 00:15:59,380 Seguir adelante y tomar un par de segundos, y ordenar los mismos desde el más pequeño en el 430 00:15:59,380 --> 00:16:01,240 izquierda a grande a la derecha. 431 00:16:01,240 --> 00:16:02,490 Vaya. 432 00:16:02,490 --> 00:16:07,010 433 00:16:07,010 --> 00:16:07,530 >> Aceptar. 434 00:16:07,530 --> 00:16:08,030 Bueno. 435 00:16:08,030 --> 00:16:09,370 Eso fue realmente maldito rápido. 436 00:16:09,370 --> 00:16:14,040 Ahora alguien aquí, ¿cuál fue el algoritmo que estos tipos aplicados? 437 00:16:14,040 --> 00:16:14,900 >> ALTAVOZ 1: De menos a más. 438 00:16:14,900 --> 00:16:15,000 >> DAVID J. MALAN: OK. 439 00:16:15,000 --> 00:16:18,070 De menos a más grande es realmente una especie de objetivo, pero no estoy seguro de que es 440 00:16:18,070 --> 00:16:18,890 realmente un algoritmo. 441 00:16:18,890 --> 00:16:21,810 De menos a más no dice me paso a paso lo que debe hacer. 442 00:16:21,810 --> 00:16:22,833 ¿Sí? 443 00:16:22,833 --> 00:16:24,083 >> ALTAVOZ 1: [inaudible] 444 00:16:24,083 --> 00:16:26,010 445 00:16:26,010 --> 00:16:26,280 >> DAVID J. MALAN: OK. 446 00:16:26,280 --> 00:16:28,920 Así que si ves a una persona menor de su número, a continuación, pasar a 447 00:16:28,920 --> 00:16:29,680 la derecha de ellos. 448 00:16:29,680 --> 00:16:32,800 Así que ahora es cada vez más expresiva, más como un algoritmo, ya que 449 00:16:32,800 --> 00:16:35,410 puede decir, si esto, entonces eso. 450 00:16:35,410 --> 00:16:37,050 Así que tenemos algún tipo de constructor condicional. 451 00:16:37,050 --> 00:16:39,700 Y estos chicos parecía hacer que unos pocos veces, porque algunos de ustedes se movieron un poco 452 00:16:39,700 --> 00:16:40,420 de una distancia. 453 00:16:40,420 --> 00:16:43,410 Así que hubo de suponer algún tipo de bucle pasando en sus mentes. 454 00:16:43,410 --> 00:16:44,610 >> Pero vamos a tratar de formalizar eso. 455 00:16:44,610 --> 00:16:47,540 Si ustedes pudieran restablecer de nuevo con esta disposición. 456 00:16:47,540 --> 00:16:50,650 Vamos a ver si no podemos formalizar este un poco, y luego hacer la pregunta, simplemente 457 00:16:50,650 --> 00:16:51,580 qué tan eficiente es esto? 458 00:16:51,580 --> 00:16:54,220 Por supuesto, cuando hacemos esto más lentamente, se va a sentir tan bien de 459 00:16:54,220 --> 00:16:57,210 un algoritmo, pero vamos a ver si podemos poner los dedos sobre los pasos precisos. 460 00:16:57,210 --> 00:16:58,670 >> Así que ustedes dos son cuatro y dos. 461 00:16:58,670 --> 00:17:01,020 O usted corrige o el orden incorrecto? 462 00:17:01,020 --> 00:17:01,900 Obviamente correctos. 463 00:17:01,900 --> 00:17:02,710 Así que intercambiamos. 464 00:17:02,710 --> 00:17:05,170 Ahora me voy a mover de lado aquí y decir, cuatro a seis. 465 00:17:05,170 --> 00:17:06,240 ¿Está correcto o incorrecto? 466 00:17:06,240 --> 00:17:06,599 >> GABE: Correcto. 467 00:17:06,599 --> 00:17:07,180 >> DAVID J. MALAN: Correcto. 468 00:17:07,180 --> 00:17:08,300 Seis y uno? 469 00:17:08,300 --> 00:17:08,609 Nope. 470 00:17:08,609 --> 00:17:09,630 Swap. 471 00:17:09,630 --> 00:17:10,490 Así que eso es dos swaps. 472 00:17:10,490 --> 00:17:11,710 Seis y tres? 473 00:17:11,710 --> 00:17:11,980 Nope. 474 00:17:11,980 --> 00:17:13,000 Swap. 475 00:17:13,000 --> 00:17:13,930 Seis y siete? 476 00:17:13,930 --> 00:17:14,630 Se ve bien. 477 00:17:14,630 --> 00:17:15,396 Siete y cinco? 478 00:17:15,396 --> 00:17:16,150 >> JESS: [inaudible] 479 00:17:16,150 --> 00:17:17,089 >> DAVID J. MALAN: OK, intercambiar. 480 00:17:17,089 --> 00:17:19,770 Y ordenados. 481 00:17:19,770 --> 00:17:19,980 Está bien. 482 00:17:19,980 --> 00:17:21,440 Así que, obviamente, no, ¿verdad? 483 00:17:21,440 --> 00:17:22,470 Así que no había más que hacer. 484 00:17:22,470 --> 00:17:24,920 Pero, de hecho, estos chicos, incluso instintivamente. 485 00:17:24,920 --> 00:17:25,450 mantenerse en movimiento. 486 00:17:25,450 --> 00:17:27,710 No se limitaron a detener, una vez que corregido un problema. 487 00:17:27,710 --> 00:17:27,839 Así. 488 00:17:27,839 --> 00:17:29,390 De hecho, voy a tener para hacer lo mismo. 489 00:17:29,390 --> 00:17:32,720 Voy a tener que rebobinar suerte de volver al principio de este problema, 490 00:17:32,720 --> 00:17:35,630 o el comienzo de esta serie de gente, vamos a empezar llamarlos. 491 00:17:35,630 --> 00:17:38,366 >> Y ahora, ¿qué debería decir a mi algoritmo en el segundo pase ser? 492 00:17:38,366 --> 00:17:39,220 >> ALTAVOZ 1: Es lo mismo. 493 00:17:39,220 --> 00:17:39,940 >> DAVID J. MALAN: Es lo mismo. 494 00:17:39,940 --> 00:17:41,460 Y esto, me estoy empezando a gustar, ¿verdad? 495 00:17:41,460 --> 00:17:44,720 Tan pronto como usted puede encontrarse haciendo la misma cosa una y otra vez, eso es 496 00:17:44,720 --> 00:17:47,890 cada vez más como un algoritmo, y menos instinto humano. 497 00:17:47,890 --> 00:17:48,680 >> Así que ahora, aquí vamos de nuevo. 498 00:17:48,680 --> 00:17:49,870 Dos y cuatro? 499 00:17:49,870 --> 00:17:50,220 No. 500 00:17:50,220 --> 00:17:51,050 Cuatro y uno? 501 00:17:51,050 --> 00:17:53,380 Ah, no había de hecho algunos El trabajo todavía por hacer. 502 00:17:53,380 --> 00:17:53,620 A favor y tres? 503 00:17:53,620 --> 00:17:54,572 Bueno. 504 00:17:54,572 --> 00:17:56,000 Cuatro y seis? 505 00:17:56,000 --> 00:17:58,380 Seis y cinco? 506 00:17:58,380 --> 00:17:59,470 Seis y siete? 507 00:17:59,470 --> 00:18:00,970 Bien, ahora, hecho. 508 00:18:00,970 --> 00:18:01,550 Bueno, no. 509 00:18:01,550 --> 00:18:02,710 Tengo que volver. 510 00:18:02,710 --> 00:18:05,130 >> Así que ahora, una vez más, que estamos haciendo esto un poco más de forma deliberada. 511 00:18:05,130 --> 00:18:08,700 Y ahora, sólo hay un cerebro la ejecución de este algoritmo. 512 00:18:08,700 --> 00:18:10,290 Una CPU, si se quiere. 513 00:18:10,290 --> 00:18:13,090 Y, francamente, ese es el único recurso vamos a tener acceso. 514 00:18:13,090 --> 00:18:16,280 ¿Y una vez que nos hace volver a un teclado y tener algo como C en nuestra 515 00:18:16,280 --> 00:18:19,600 disposición, que sólo estamos escribiendo un programa que puede hacer una cosa a la vez. 516 00:18:19,600 --> 00:18:22,900 Considerando que, a estos chicos hace un momento, que aprovechado su capacidad intelectual colectiva 517 00:18:22,900 --> 00:18:24,180 como ustedes hicieron en la semana cero. 518 00:18:24,180 --> 00:18:24,980 Así que vamos a seguir haciendo esto. 519 00:18:24,980 --> 00:18:26,260 >> Dos y uno. 520 00:18:26,260 --> 00:18:26,945 Dos y tres. 521 00:18:26,945 --> 00:18:27,460 Tres y cuatro. 522 00:18:27,460 --> 00:18:28,310 Cuatro y cinco. 523 00:18:28,310 --> 00:18:28,620 Cinco y seis. 524 00:18:28,620 --> 00:18:30,510 Seis y siete. 525 00:18:30,510 --> 00:18:31,880 Hecho? 526 00:18:31,880 --> 00:18:34,560 Así que yo, pero me deja jugar abogado del diablo. 527 00:18:34,560 --> 00:18:37,950 ¿Tengo el tipo de ordenador que acaba de hizo un pase a través de esta serie de 528 00:18:37,950 --> 00:18:40,225 gente, saben que estoy hecho? 529 00:18:40,225 --> 00:18:40,670 >> ALTAVOZ 1: No. 530 00:18:40,670 --> 00:18:41,050 >> DAVID J. MALAN: ¿Entonces por qué? 531 00:18:41,050 --> 00:18:46,900 ¿Qué tendría que ver con el fin de concluir de manera decisiva de que estoy hecho? 532 00:18:46,900 --> 00:18:48,230 Probablemente uno pase más. 533 00:18:48,230 --> 00:18:48,430 ¿Cierto? 534 00:18:48,430 --> 00:18:51,760 Porque todo lo que sé de ese anterior pase es que he corregido un error. 535 00:18:51,760 --> 00:18:53,920 Y eso significa, tal vez hay aún otro error 536 00:18:53,920 --> 00:18:54,840 que tengo que corregir. 537 00:18:54,840 --> 00:18:58,680 Así que sólo puedo estar seguro de rebobinado y a continuación, comprobar, uno a dos, dos y 538 00:18:58,680 --> 00:19:00,940 tres, tres y cuatro, cuatro y cinco, cinco y seis, seis y siete. 539 00:19:00,940 --> 00:19:02,510 Bien, ahora que hice ningún trabajo. 540 00:19:02,510 --> 00:19:05,990 >> Ciertamente, puedo recordar que hice no trabajar con algo parecido a una variable, 541 00:19:05,990 --> 00:19:06,975 como un int. 542 00:19:06,975 --> 00:19:12,490 Llámelo swaps, swaps y si es 0, una vez que llegar hasta aquí, y empezó a 0, entonces 543 00:19:12,490 --> 00:19:15,520 Sólo quiero ser estúpido para seguir adelante de ida y vuelta, comprobando de nuevo, y 544 00:19:15,520 --> 00:19:16,450 otra vez, y otra vez, ¿verdad? 545 00:19:16,450 --> 00:19:18,450 Porque te quedas atascado en algún tipo de bucle infinito. 546 00:19:18,450 --> 00:19:21,250 Así que en cuanto hay 0 swaps, podemos afirmar que esta 547 00:19:21,250 --> 00:19:23,810 algoritmo es de hecho completa. 548 00:19:23,810 --> 00:19:25,400 >> Ahora, vamos a poner un nombre en esto. 549 00:19:25,400 --> 00:19:28,930 El algoritmo que propongo que acabamos implementado es algo que se llama la burbuja 550 00:19:28,930 --> 00:19:32,800 tipo, conocido como tal en el sentido de que los números que son más grandes tipo de 551 00:19:32,800 --> 00:19:37,990 burbuja de su camino a la cima, o hasta al final de la matriz de números. 552 00:19:37,990 --> 00:19:40,270 Pero qué tan eficiente fue este algoritmo? 553 00:19:40,270 --> 00:19:44,600 ¿Cuántos pasos qué tuve que físicamente Tomemos, por ejemplo, para ordenar estos 554 00:19:44,600 --> 00:19:45,850 siete seres humanos? 555 00:19:45,850 --> 00:19:48,560 556 00:19:48,560 --> 00:19:49,550 >> Cuatro a cinco? 557 00:19:49,550 --> 00:19:51,420 Bien, también muchos es en última instancia, va a ser la respuesta. 558 00:19:51,420 --> 00:19:54,960 Pero incluso entonces, el número específico no es tan interesante. 559 00:19:54,960 --> 00:19:56,670 Vamos a generalizar como n. 560 00:19:56,670 --> 00:20:00,520 Así que si yo tuviera aquí n personas, y ellos eran, más o menos, en un orden aleatorio en la 561 00:20:00,520 --> 00:20:02,180 comenzando, en ese orden original. 562 00:20:02,180 --> 00:20:04,910 Bueno, ¿cuántos pasos tenía yo para tomar en la primera pasada? 563 00:20:04,910 --> 00:20:09,810 Fue uno, dos, tres, cuatro, cinco, seis, y son siete personas, por lo 564 00:20:09,810 --> 00:20:13,670 eso es siete, seis -, así que eso es n menos uno los pasos de la primera vez. 565 00:20:13,670 --> 00:20:16,280 >> Ahora, ¿cuántos pasos tenía yo a tomar cuando Rebobiné? 566 00:20:16,280 --> 00:20:19,310 Bueno, en realidad podríamos duplicar que si que realmente quería, pero por ahora, estoy 567 00:20:19,310 --> 00:20:22,300 sólo voy a decir, está bien, otro n menos 1. 568 00:20:22,300 --> 00:20:25,240 Así que el n menos 1 se va a poner molestos para no perder de vista, así que vamos a 569 00:20:25,240 --> 00:20:26,400 Justo a la vuelta un poco. 570 00:20:26,400 --> 00:20:27,770 Así pasos 2n. 571 00:20:27,770 --> 00:20:29,310 Así que 14 pasos, más o menos. 572 00:20:29,310 --> 00:20:31,930 >> ¿Cuántas veces me tomo un paso la próxima vez? 573 00:20:31,930 --> 00:20:33,740 Bueno, es 3n. 574 00:20:33,740 --> 00:20:34,510 realmente. 575 00:20:34,510 --> 00:20:37,920 Y ahora, en el peor de los casos, por ejemplo, ¿cuántas veces voy a tener 576 00:20:37,920 --> 00:20:41,730 ido hacia atrás y adelante, atrás y adelante, la ejecución de este algoritmo, el intercambio 577 00:20:41,730 --> 00:20:44,620 personas en cada paso, más o menos? 578 00:20:44,620 --> 00:20:47,720 579 00:20:47,720 --> 00:20:50,010 De hecho, es n al cuadrado, ¿verdad? 580 00:20:50,010 --> 00:20:53,000 >> Debido a que en el peor de los casos, puede tipo de pensar en esto de manera intuitiva, 581 00:20:53,000 --> 00:20:54,800 a pesar de que puede ser que tome un poco de poco de tiempo a asimilar 582 00:20:54,800 --> 00:20:57,590 En el peor de los casos, lo que haría estos siete personas han visto como, en 583 00:20:57,590 --> 00:21:00,230 términos del acuerdo de sus números? 584 00:21:00,230 --> 00:21:01,460 Completamente al revés, ¿no? 585 00:21:01,460 --> 00:21:02,815 Y sólo para simular que, ¿cuál era su nombre? 586 00:21:02,815 --> 00:21:03,360 >> MIKE: Mike. 587 00:21:03,360 --> 00:21:03,640 >> DAVID J. MALAN: Mike? 588 00:21:03,640 --> 00:21:08,100 Bien, Mike, ¿puedes venir conmigo sobre aquí sólo por un segundo? 589 00:21:08,100 --> 00:21:08,880 En realidad, no. 590 00:21:08,880 --> 00:21:10,150 Lo sentimos Mike, vamos a retroceder. 591 00:21:10,150 --> 00:21:10,910 ¿Cuál es tu nombre? 592 00:21:10,910 --> 00:21:11,180 >> NEIL: Neil. 593 00:21:11,180 --> 00:21:11,640 >> DAVID J. MALAN: Neil. 594 00:21:11,640 --> 00:21:13,750 Aceptar, Neil, vienes con mí, si no te importa. 595 00:21:13,750 --> 00:21:17,150 Así que voy a proponer, sólo por simplicidad, que Neil se encuentra ahora en su 596 00:21:17,150 --> 00:21:18,510 peor de los casos posibles. 597 00:21:18,510 --> 00:21:20,720 Pero recuerdo cómo he implementado mi algoritmo. 598 00:21:20,720 --> 00:21:24,530 Estoy comparando, comparar, comparar, comparar, comparar, oh. 599 00:21:24,530 --> 00:21:26,640 Ahora estos chicos están fuera de orden, así que puedo corregir. 600 00:21:26,640 --> 00:21:27,980 Así que ustedes swap. 601 00:21:27,980 --> 00:21:31,630 Pero consideremos ahora, cuánto más lejos Neil no tiene por qué ir? 602 00:21:31,630 --> 00:21:32,690 Es más o menos n. 603 00:21:32,690 --> 00:21:33,570 Ya sabes, no es en realidad n. 604 00:21:33,570 --> 00:21:36,040 Es como, n menos 1, pero me estoy poniendo hacer el seguimiento molesto de la pequeña 605 00:21:36,040 --> 00:21:37,550 número, así que vamos a llamarlo n. 606 00:21:37,550 --> 00:21:42,860 >> Así que si Neil da un paso al máximo cada tiempo, y para mover Neil un paso, 607 00:21:42,860 --> 00:21:46,580 Tengo que hacer este paso realmente tedioso de ida y vuelta, esto es más o menos 608 00:21:46,580 --> 00:21:52,080 haciendo esto, n pasos, un total de n veces, porque me va a tomar 609 00:21:52,080 --> 00:21:55,820 que muchos pasos para llegar Neil todos el camino a donde pertenece. 610 00:21:55,820 --> 00:21:58,620 Por no hablar de todos los demás si ustedes fueron todos mis-ordenó también. 611 00:21:58,620 --> 00:22:01,100 >> Así que vamos a llamar a la ordenación de burbuja n al cuadrado. 612 00:22:01,100 --> 00:22:04,860 El tiempo de funcionamiento de este algoritmo, el el rendimiento de este algoritmo, la 613 00:22:04,860 --> 00:22:07,120 la eficiencia de este algoritmo, nos acaba de describir con mayor 614 00:22:07,120 --> 00:22:08,800 generalmente como n al cuadrado. 615 00:22:08,800 --> 00:22:11,650 Lo cual es bueno, porque yo podría hacer el mismo ejemplo con ocho personas, nueve 616 00:22:11,650 --> 00:22:15,450 personas, un millón de personas, y que respuesta no va a cambiar. 617 00:22:15,450 --> 00:22:18,870 >> Así que si ustedes no me importaría, vamos a que restablezca al punto de partida. 618 00:22:18,870 --> 00:22:22,510 Y vamos a tratar otros dos enfoques y ver si no podemos hacerlo, fundamentalmente, 619 00:22:22,510 --> 00:22:23,820 mejor que esto. 620 00:22:23,820 --> 00:22:27,130 Así que esta vez, voy a proponer un tipo de algoritmo diferente. 621 00:22:27,130 --> 00:22:29,950 Eso fue muy inteligente de nosotros la última vez, y ustedes fueron derecho a que el 622 00:22:29,950 --> 00:22:32,470 instintos correctos de sólo un poco de intercambio de parejas. 623 00:22:32,470 --> 00:22:36,500 Pero si realmente quería abordar este simplemente, y mi meta es mover 624 00:22:36,500 --> 00:22:39,800 todos los pequeños números de esta manera, y empujar todos los grandes números que 625 00:22:39,800 --> 00:22:43,030 cierto, ¿por qué no me hago en el la forma más ingenua posible y ver si 626 00:22:43,030 --> 00:22:45,730 puede hacer algo mejor que lo que era un algoritmo bastante complejo? 627 00:22:45,730 --> 00:22:46,620 >> Así que vamos a ver. 628 00:22:46,620 --> 00:22:48,940 Cuatro es un número bastante pequeño, así que estoy voy a dejar ahí momento. 629 00:22:48,940 --> 00:22:50,610 Ooh, el número dos es incluso mejor. 630 00:22:50,610 --> 00:22:52,230 Así que puede que acaba de dar un paso adelante por un momento? 631 00:22:52,230 --> 00:22:55,670 Esta es actualmente mi pequeño numerada candidato, y yo voy a recordar 632 00:22:55,670 --> 00:22:57,000 que con, como, una variable. 633 00:22:57,000 --> 00:22:57,930 Pero yo voy a seguir buscando. 634 00:22:57,930 --> 00:22:59,890 ¿Hay alguien cuya número es menor? 635 00:22:59,890 --> 00:23:00,460 Seis, no. 636 00:23:00,460 --> 00:23:01,390 Oh, hay Neil de nuevo. 637 00:23:01,390 --> 00:23:04,050 >> Así que voy a empujar de vuelta tipo de conceptualmente. 638 00:23:04,050 --> 00:23:05,120 Neil vendrá adelante. 639 00:23:05,120 --> 00:23:08,440 Y ahora, la variable que estoy usando para realizar un seguimiento de quién tiene el más pequeño 640 00:23:08,440 --> 00:23:11,390 número se actualiza para contener Ubicación de Neil. 641 00:23:11,390 --> 00:23:12,110 Bueno, vamos a ver. 642 00:23:12,110 --> 00:23:13,960 Tres, siete, cinco. 643 00:23:13,960 --> 00:23:15,590 Ok, sé que Neil era el más pequeño. 644 00:23:15,590 --> 00:23:18,110 ¿Cuál es la cosa más simple para que haga ahora? 645 00:23:18,110 --> 00:23:21,410 No voy a perder mi tiempo con sólo burbujeante Neil un lugar a la izquierda. 646 00:23:21,410 --> 00:23:25,350 ¿Por qué no acaba de poner Neil donde pertenece, que es, por supuesto, ¿dónde? 647 00:23:25,350 --> 00:23:26,160 >> Todo el camino desde el principio. 648 00:23:26,160 --> 00:23:27,720 Así que Neil, ven conmigo. 649 00:23:27,720 --> 00:23:28,910 ¿Y cuál era tu nombre? 650 00:23:28,910 --> 00:23:29,310 >> GRACE: Grace. 651 00:23:29,310 --> 00:23:29,710 >> DAVID J. MALAN: Grace. 652 00:23:29,710 --> 00:23:29,920 Aceptar. 653 00:23:29,920 --> 00:23:32,490 Así también la gracia, por desgracia, eres un poco en el camino. 654 00:23:32,490 --> 00:23:34,290 Entonces, ¿cómo podemos resolver este problema? 655 00:23:34,290 --> 00:23:34,490 ¿Cierto? 656 00:23:34,490 --> 00:23:37,500 Si se trata de una matriz, no hay sólo siete ubicaciones. 657 00:23:37,500 --> 00:23:40,830 Recordemos que, con Rob, hablamos de declarando las edades, y que sólo tenía un 658 00:23:40,830 --> 00:23:41,740 número finito de edades? 659 00:23:41,740 --> 00:23:42,535 La misma idea aquí. 660 00:23:42,535 --> 00:23:44,300 Sólo tenemos un número finito de enteros. 661 00:23:44,300 --> 00:23:47,590 La gracia es un poco en nuestra manera, así que ¿cómo lo arreglamos? 662 00:23:47,590 --> 00:23:49,555 >> La forma más sencilla es como, Gracia, lo siento. 663 00:23:49,555 --> 00:23:51,870 Vas a tener que ir a través de allí, así que se puede dar cabida. 664 00:23:51,870 --> 00:23:55,290 Ahora, si se piensa en ello, tal vez que acaba de hacer el problema peor. 665 00:23:55,290 --> 00:23:58,510 Y tal vez lo hicimos, porque lo que si La gracia estaba en el lugar correcto? 666 00:23:58,510 --> 00:24:01,730 Pero sabemos que no lo es, porque de lo contrario, habría sido 667 00:24:01,730 --> 00:24:03,980 pie hacia adelante en lugar de Neil en este momento, ¿no? 668 00:24:03,980 --> 00:24:05,550 Ya hemos comprobado su número fuera. 669 00:24:05,550 --> 00:24:05,770 >> Está bien. 670 00:24:05,770 --> 00:24:09,110 Así que ahora, Neil está en el lugar correcto, y Yo puedo hacer una ligera optimización. 671 00:24:09,110 --> 00:24:11,740 Para el próximo minuto, voy a ignorar Neil todos juntos, a fin de no 672 00:24:11,740 --> 00:24:15,280 perder el tiempo, o accidentalmente él cambiar al lugar equivocado. 673 00:24:15,280 --> 00:24:17,805 Así que ahora, ¿cómo puedo encontrar la siguiente elemento que es más pequeño? 674 00:24:17,805 --> 00:24:18,480 Dos. 675 00:24:18,480 --> 00:24:20,225 Eso es un número bastante bueno, si quiere dar un paso adelante y 676 00:24:20,225 --> 00:24:21,100 Yo te recuerdo. 677 00:24:21,100 --> 00:24:21,980 Seis, no es bueno. 678 00:24:21,980 --> 00:24:24,820 Cuatro, tres, siete, cinco, no es bueno. 679 00:24:24,820 --> 00:24:26,800 Así que voy a mover a su lugar correcto. 680 00:24:26,800 --> 00:24:28,470 Y tuvimos suerte esta vez. 681 00:24:28,470 --> 00:24:31,350 >> Ahora, yo voy a hacer caso omiso de estos dos chicos, y ahora lo hacen una más 682 00:24:31,350 --> 00:24:32,260 pasar a través de esto. 683 00:24:32,260 --> 00:24:33,490 Six, que un número muy pequeño. 684 00:24:33,490 --> 00:24:34,300 Vamos hacia adelante. 685 00:24:34,300 --> 00:24:35,220 Oh, lo siento. 686 00:24:35,220 --> 00:24:37,640 Número de Grace es mejor, por lo que paso en adelante. 687 00:24:37,640 --> 00:24:38,260 Cuatro. 688 00:24:38,260 --> 00:24:39,120 Lo sentimos, Grace. 689 00:24:39,120 --> 00:24:39,950 Volver de nuevo. 690 00:24:39,950 --> 00:24:41,550 El número tres es mejor. 691 00:24:41,550 --> 00:24:42,290 Siete. 692 00:24:42,290 --> 00:24:42,720 Cinco. 693 00:24:42,720 --> 00:24:43,550 Y ahora ¿cuál es tu nombre? 694 00:24:43,550 --> 00:24:44,000 >> JASON: Jason. 695 00:24:44,000 --> 00:24:44,420 >> DAVID J. MALAN: Jason. 696 00:24:44,420 --> 00:24:47,050 Así que Jason es ahora el más pequeño elemento que he seleccionado. 697 00:24:47,050 --> 00:24:49,160 ¿A dónde va a ir? 698 00:24:49,160 --> 00:24:50,380 Entonces, ¿dónde seis es. 699 00:24:50,380 --> 00:24:51,210 Y su nombre es nuevo? 700 00:24:51,210 --> 00:24:51,710 >> GABE: Gabe. 701 00:24:51,710 --> 00:24:52,340 >> DAVID J. MALAN: Gabe. 702 00:24:52,340 --> 00:24:53,220 Gabe está en el camino. 703 00:24:53,220 --> 00:24:54,640 ¿Cuál es la cosa más fácil de hacer? 704 00:24:54,640 --> 00:24:58,390 Cambie estos dos chicos y continuar. 705 00:24:58,390 --> 00:24:59,020 Así que ahora vamos a ver. 706 00:24:59,020 --> 00:25:00,170 ¿Quién es el más pequeño? 707 00:25:00,170 --> 00:25:01,030 Cuatro. 708 00:25:01,030 --> 00:25:01,990 Déjame sólo un poco de trampa. 709 00:25:01,990 --> 00:25:03,090 Cinco va a ser el más pequeño. 710 00:25:03,090 --> 00:25:05,220 Me parece próximo, si usted quiere dar un paso hacia adelante, ¿qué tengo que ver con 711 00:25:05,220 --> 00:25:06,820 estos chicos, con Gabe? 712 00:25:06,820 --> 00:25:08,450 Cambie de nuevo. 713 00:25:08,450 --> 00:25:10,740 Así que ahora, todavía un poco fuera de lugar. 714 00:25:10,740 --> 00:25:14,140 Encontré Gabe para ser el más pequeño, por lo que Le Pop Out, muevo ustedes otra vez. 715 00:25:14,140 --> 00:25:15,190 Y hecho. 716 00:25:15,190 --> 00:25:17,200 >> Así que la respuesta es la misma. 717 00:25:17,200 --> 00:25:18,600 El resultado final es el mismo. 718 00:25:18,600 --> 00:25:22,730 ¿Cuál de estos dos algoritmos es mejor? 719 00:25:22,730 --> 00:25:23,500 El segundo, oí. 720 00:25:23,500 --> 00:25:24,252 ¿Por qué? 721 00:25:24,252 --> 00:25:25,900 >> ALTAVOZ 3: Es n pasos [inaudible]. 722 00:25:25,900 --> 00:25:27,600 >> DAVID J. MALAN: Es n pasos como máximo. 723 00:25:27,600 --> 00:25:28,490 Interesante. 724 00:25:28,490 --> 00:25:30,610 Así es que, aunque? 725 00:25:30,610 --> 00:25:33,630 Entonces, ¿cómo puedo encontrar el más pequeño elemento? 726 00:25:33,630 --> 00:25:37,060 ¿Cuántos pasos tuve que tomar el encontrar el elemento más pequeño? 727 00:25:37,060 --> 00:25:39,220 Tenía una mirada todo el camino al final, ¿no? 728 00:25:39,220 --> 00:25:41,530 Porque en ese caso peor, ¿qué si Neil estaban aquí? 729 00:25:41,530 --> 00:25:45,700 Así que encontrar el elemento más pequeño me n pasos tomas, o n menos 1. 730 00:25:45,700 --> 00:25:46,100 Pero, en Aceptar. 731 00:25:46,100 --> 00:25:46,980 Así fijar Neil. 732 00:25:46,980 --> 00:25:48,740 Recuerde que, un minuto o así que hace. 733 00:25:48,740 --> 00:25:51,680 >> Pero, ¿qué encontré la siguiente más pequeño elemento? 734 00:25:51,680 --> 00:25:54,830 Es n menos 1, o n menos 2 realmente, a partir del número de pasos. 735 00:25:54,830 --> 00:25:55,440 Así que bien. 736 00:25:55,440 --> 00:25:57,390 Así que lo hice n menos 2. 737 00:25:57,390 --> 00:25:57,600 Está bien. 738 00:25:57,600 --> 00:25:59,130 Así que se siente un poco mejor. 739 00:25:59,130 --> 00:25:59,730 Está bien. 740 00:25:59,730 --> 00:26:03,270 ¿Cuántos pasos la próxima vez para encontrar el número tres? 741 00:26:03,270 --> 00:26:04,420 Entonces n menos 4. 742 00:26:04,420 --> 00:26:07,670 Así que es decreciente, uno menos paso en cada iteración. 743 00:26:07,670 --> 00:26:08,740 Así que esto se siente mejor, ¿verdad? 744 00:26:08,740 --> 00:26:13,450 Si la última vez fue más o menos n veces n, esta vez se trata de n menos 1, más n menos 745 00:26:13,450 --> 00:26:16,500 2, más n menos 3, más n menos 4, punto, punto, punto. 746 00:26:16,500 --> 00:26:18,750 Pero si usted recuerda de su escuela secundaria libros de texto, el pequeño truco 747 00:26:18,750 --> 00:26:24,380 hoja en la parte trasera que tiene las fórmulas, si realizar la suma de esta serie de números, 748 00:26:24,380 --> 00:26:31,280 lo que es el número total de pasos vaya a ser que me tomo aquí? 749 00:26:31,280 --> 00:26:36,580 >> Este es uno de los que, como, n menos 1, los tiempos de n, dividido por 2. 750 00:26:36,580 --> 00:26:39,040 Así que déjame ver si puedo sacar esto por un momento. 751 00:26:39,040 --> 00:26:42,230 Y de nuevo, estoy un poco redondeo algunas números sólo para mantener nuestra vida sencilla, 752 00:26:42,230 --> 00:26:47,830 pero por lo que recuerdo, es algo así como si Hago n menos 1 cosas, entonces n menos 753 00:26:47,830 --> 00:26:53,570 2, entonces n menos 3, que es más o menos algo así más de 2, y si 754 00:26:53,570 --> 00:26:55,510 multiplique esto, eso es en realidad n cuadrada. 755 00:26:55,510 --> 00:26:58,940 Eso no está sintiendo muy bien. n menos n sobre 2. 756 00:26:58,940 --> 00:27:00,350 >> Pero aquí está la cosa. 757 00:27:00,350 --> 00:27:03,720 En ciencias de la computación, cuando los problemas empezar a ponerse interesante es cuando n 758 00:27:03,720 --> 00:27:04,700 se pone muy grande. 759 00:27:04,700 --> 00:27:08,110 Y cuando n se hace muy grande, lo que de estos valores se van a dominar toda 760 00:27:08,110 --> 00:27:09,750 de los demás? 761 00:27:09,750 --> 00:27:10,990 Es una especie de la n al cuadrado, ¿verdad? 762 00:27:10,990 --> 00:27:13,340 Sí, dividiendo por 2 es bastante bueno. 763 00:27:13,340 --> 00:27:16,740 Pero si usted está hablando de miles de millones de piezas de datos, o miles de millones de 764 00:27:16,740 --> 00:27:18,700 piezas de datos, OK, por lo que usted es el doble de rápido. 765 00:27:18,700 --> 00:27:22,440 Pero a quién le importa si ese número grande, si este factor es lo que obtiene 766 00:27:22,440 --> 00:27:23,040 más y más grande. 767 00:27:23,040 --> 00:27:25,990 Y sin duda, tiene más de una diferencia de este tipo. 768 00:27:25,990 --> 00:27:29,120 Así que a pesar de que ustedes están bien, el segundo algoritmo, lo vamos a llamar 769 00:27:29,120 --> 00:27:32,970 ordenación por selección, es decir, en el mundo real, una poco más rápido en potencia, porque soy 770 00:27:32,970 --> 00:27:35,360 teniendo cada vez menos pasos cada vez. 771 00:27:35,360 --> 00:27:37,340 >> En realidad no es fundamentalmente más rápido. 772 00:27:37,340 --> 00:27:41,430 Porque si en realidad nos jugamos esto para grandes valores de n, al final de 773 00:27:41,430 --> 00:27:44,750 el día, por lo suficientemente grande n, sigue siendo va a sentir bastante lento. 774 00:27:44,750 --> 00:27:46,770 Bueno, déjame tomar una último pase a eso. 775 00:27:46,770 --> 00:27:48,920 Eso es lo que yo llamaría ordenación por selección. 776 00:27:48,920 --> 00:27:51,040 Pueden ustedes restablecer mismos por última vez? 777 00:27:51,040 --> 00:27:53,550 Y en este último caso, voy proponer algo 778 00:27:53,550 --> 00:27:54,970 llamada ordenación por inserción. 779 00:27:54,970 --> 00:27:57,470 Ser la ordenación por inserción, conceptualmente, un poco diferente. 780 00:27:57,470 --> 00:28:00,980 >> En lugar de ir y venir y seleccionar el elemento más pequeño, estoy 781 00:28:00,980 --> 00:28:05,030 sólo va a tratar con cada uno de estos chicos como yo las encuentre, e inserte 782 00:28:05,030 --> 00:28:06,850 ellos en su lugar correcto. 783 00:28:06,850 --> 00:28:10,160 Así que sólo voy a empezar con la Gracia, y veo que ella es la número cuatro. 784 00:28:10,160 --> 00:28:11,720 ¿Dónde número cuatro pertenecen? 785 00:28:11,720 --> 00:28:14,940 Todavía no he empezado la clasificación nada, Así que la gracia llega a quedarse ahí. 786 00:28:14,940 --> 00:28:18,355 Y ahora voy a reclamar, si pudiera dar un paso a la derecha, esta 787 00:28:18,355 --> 00:28:21,650 mi lista ordenada, este es mi lista restante sin clasificar. 788 00:28:21,650 --> 00:28:23,260 Así que ahora voy a proceder a continuación, y ¿cuál es tu nombre? 789 00:28:23,260 --> 00:28:23,700 >> BRANSON: Branson. 790 00:28:23,700 --> 00:28:24,150 >> DAVID J. MALAN: Branson. 791 00:28:24,150 --> 00:28:25,375 Así Branson es el número dos. 792 00:28:25,375 --> 00:28:27,490 Así que voy a tener que fuera por un momento. 793 00:28:27,490 --> 00:28:30,940 Y ahora, ¿dónde perteneces en esta serie? 794 00:28:30,940 --> 00:28:32,360 Así que a la derecha de la Gracia. 795 00:28:32,360 --> 00:28:35,670 Así que de nuevo, estamos como hacer La gracia hacer un montón de trabajo aquí. 796 00:28:35,670 --> 00:28:37,290 ¿Dónde ponemos usted? 797 00:28:37,290 --> 00:28:40,120 Así que te vamos a deslizar a la a la izquierda, e introduzca Branson allí. 798 00:28:40,120 --> 00:28:41,680 Pero ahora afirmo que ustedes llevan a cabo. 799 00:28:41,680 --> 00:28:43,240 Pero aviso, no estoy usando el espacio extra. 800 00:28:43,240 --> 00:28:45,130 Sigue siendo 2 elementos aquí, 5 aquí. 801 00:28:45,130 --> 00:28:47,910 Tamaño total de la matriz es de 7, así que estoy no copiar, no está bien? 802 00:28:47,910 --> 00:28:51,950 >> Así que ahora tenemos, con Gabe aquí, el número seis, ¿de dónde sois? 803 00:28:51,950 --> 00:28:52,650 Tuviste suerte de nuevo. 804 00:28:52,650 --> 00:28:53,820 Así que usted puede permanecer allí. 805 00:28:53,820 --> 00:28:57,210 Basta con echar un ligero paso hacia la derecha sólo para dejar en claro que está ordenada. 806 00:28:57,210 --> 00:29:00,520 Y ahora tenemos a Neil de nuevo, el número de uno, ¿a dónde vas? 807 00:29:00,520 --> 00:29:03,540 Y ahora es cuando vamos a empezar a ver que este algoritmo, aunque en primera 808 00:29:03,540 --> 00:29:05,950 vista, se siente muy inteligente, reloj lo que va a suceder. 809 00:29:05,950 --> 00:29:07,370 Si pudiera dar un paso adelante. 810 00:29:07,370 --> 00:29:09,260 >> ¿Dónde queremos poner Neil? 811 00:29:09,260 --> 00:29:11,830 Así que, obviamente, aquí, así que ¿cómo Cómo conseguimos Neil allí? 812 00:29:11,830 --> 00:29:12,970 Vamos a hacer esto paso a paso. 813 00:29:12,970 --> 00:29:15,620 Gabe, ¿dónde tiene que ir? 814 00:29:15,620 --> 00:29:19,590 Sí, así que tome un gran paso, o dos medias medidas para hacer 815 00:29:19,590 --> 00:29:20,820 un paso más allá. 816 00:29:20,820 --> 00:29:21,750 Gracia, donde vas? 817 00:29:21,750 --> 00:29:22,510 Bueno. 818 00:29:22,510 --> 00:29:23,500 Así que otro paso. 819 00:29:23,500 --> 00:29:24,960 Y, por último, Branson? 820 00:29:24,960 --> 00:29:25,460 Otro paso. 821 00:29:25,460 --> 00:29:27,190 Y ahora podemos poner Neil en su lugar. 822 00:29:27,190 --> 00:29:28,440 >> Así que ahora, seguir esta lógica. 823 00:29:28,440 --> 00:29:32,420 A pesar de que no estamos cambiando Neil otra, y otra, y otra vez, para ponerlo 824 00:29:32,420 --> 00:29:36,420 a dónde va, en el peor de los casos, la siguiente número, podríamos encontrarnos podría 825 00:29:36,420 --> 00:29:42,220 ser el número, por ejemplo, hubo un número cero, entonces vamos a cambiar todo 826 00:29:42,220 --> 00:29:42,730 estos chicos. 827 00:29:42,730 --> 00:29:44,950 Supongamos que hay un número negativo uno, entonces tenemos que cambiar 828 00:29:44,950 --> 00:29:46,080 todos estos chicos. 829 00:29:46,080 --> 00:29:48,500 Así que estamos realmente sólo un poco de mover de un tirón el problema nada más, de modo que estamos 830 00:29:48,500 --> 00:29:52,620 la transferencia de la costa de la proceso de selección por lo que la inserción 831 00:29:52,620 --> 00:29:56,930 proceso, de tal manera que ustedes acababan de para mover más o menos n menos algo 832 00:29:56,930 --> 00:29:57,940 número de pasos. 833 00:29:57,940 --> 00:30:01,200 Y ese número de pasos sólo se va aumentando a medida que selecciono más números, 834 00:30:01,200 --> 00:30:04,730 si tengo que seguir empujando a ustedes espalda, y la espalda, y la espalda. 835 00:30:04,730 --> 00:30:08,320 >> Así lo triste ahora es todo esto algoritmos se n al cuadrado. 836 00:30:08,320 --> 00:30:10,570 Vamos a seguir adelante y gracias a estos chicos y visualizar estas un poco 837 00:30:10,570 --> 00:30:11,090 de manera diferente. 838 00:30:11,090 --> 00:30:12,312 Muy bien hecho. 839 00:30:12,312 --> 00:30:14,120 >> [Aplausos] 840 00:30:14,120 --> 00:30:15,030 >> Está bien. 841 00:30:15,030 --> 00:30:16,280 Ahí lo tienes. 842 00:30:16,280 --> 00:30:18,390 843 00:30:18,390 --> 00:30:18,470 Gracias por - 844 00:30:18,470 --> 00:30:19,190 >> BRANSON: [inaudible] mantener los números. 845 00:30:19,190 --> 00:30:21,990 >> DAVID J. MALAN: No, usted puede mantener los números también. 846 00:30:21,990 --> 00:30:23,440 Está bien. 847 00:30:23,440 --> 00:30:24,100 Muy bien hecho. 848 00:30:24,100 --> 00:30:25,300 Está bien. 849 00:30:25,300 --> 00:30:30,510 Así que vamos a ver si ahora no podemos resumir más rápidamente, y más visualmente, 850 00:30:30,510 --> 00:30:33,410 exactamente lo que acaba de suceder aquí como sigue. 851 00:30:33,410 --> 00:30:36,510 852 00:30:36,510 --> 00:30:38,770 Voy a seguir adelante y tire hacia arriba Firefox. 853 00:30:38,770 --> 00:30:41,310 Nos vincularemos esta manifestación en la página web del curso. 854 00:30:41,310 --> 00:30:43,870 Java es un poco molesto para conseguir trabajo en algunos navegadores en estos días. 855 00:30:43,870 --> 00:30:46,760 Así que si no juegas con esto en casa, da cuenta de que podría tener que usar Firefox 856 00:30:46,760 --> 00:30:47,990 para que funcione. 857 00:30:47,990 --> 00:30:50,440 ¿Y qué voy a hacer con esta demostración es la siguiente. 858 00:30:50,440 --> 00:30:54,875 >> En la parte inferior, tengo un montón de opciones del menú, incluyendo un inicio y un 859 00:30:54,875 --> 00:30:55,840 botón de parar. 860 00:30:55,840 --> 00:30:59,450 También, en un aparte, parece que hay una bug en estos programas, mediante el cual se 861 00:30:59,450 --> 00:31:03,720 no puede ver realmente el inicio o detener botón a menos que mantenga Comando o Alt 862 00:31:03,720 --> 00:31:06,560 plus y acercar la imagen, que curiosamente te muestra más botones. 863 00:31:06,560 --> 00:31:09,090 Así que lo digo si juegas con esto en casa. 864 00:31:09,090 --> 00:31:12,870 Ahora voy hacer clic en Inicio en tan sólo Actualmente, después de especificar un retraso de, 865 00:31:12,870 --> 00:31:16,810 como 200 milisegundos aquí, sólo para que podamos ver lo que pasa. 866 00:31:16,810 --> 00:31:20,180 >> Así que yo sostengo que esta es una visualización de la primera algoritmo 867 00:31:20,180 --> 00:31:23,730 estos chicos lo hicieron, especie de burbuja, en el que intercambiamos personas por pares. 868 00:31:23,730 --> 00:31:27,490 La idea clave de esta visualización es que la altura de las barras 869 00:31:27,490 --> 00:31:30,510 representa el tamaño del número. 870 00:31:30,510 --> 00:31:32,210 Así que la más alta es la barra, mayor sea el número. 871 00:31:32,210 --> 00:31:33,680 Shorter la barra, más pequeño es el número. 872 00:31:33,680 --> 00:31:38,630 Y si te das cuenta, que estamos pasando la primera iteración de este algoritmo, 873 00:31:38,630 --> 00:31:42,620 intercambio de números grandes y pequeños, de manera que el número pequeño viene primero y 874 00:31:42,620 --> 00:31:44,280 el gran número va a la derecha. 875 00:31:44,280 --> 00:31:48,770 >> Y tan pronto como llegamos al final de la matriz de muchos más números de siete, estamos 876 00:31:48,770 --> 00:31:49,900 va a ir de nuevo al principio. 877 00:31:49,900 --> 00:31:51,140 Y anticipar esto. 878 00:31:51,140 --> 00:31:54,860 En el extremo izquierdo, ese pequeño tipo va para intercambiar a un lado, y este 879 00:31:54,860 --> 00:31:56,010 proceso se repite. 880 00:31:56,010 --> 00:31:59,450 Ahora esta visualización se pone rápidamente aburrido, por lo que me dejó ir adelante y dejar de 881 00:31:59,450 --> 00:32:04,170 ella, cambie la demora algo mucho más rápido sólo para ahora, una idea de 882 00:32:04,170 --> 00:32:05,060 este algoritmo. 883 00:32:05,060 --> 00:32:07,840 >> Así que, aunque he aceleró hacia arriba, esto es como actualizar mi procesador, la compra de 884 00:32:07,840 --> 00:32:08,580 un equipo nuevo. 885 00:32:08,580 --> 00:32:12,980 No he cambiado fundamentalmente mi algoritmo, pero de hecho, puede ver más 886 00:32:12,980 --> 00:32:16,800 claramente que con los seres humanos, que el gran números están burbujeando hasta la cima, 887 00:32:16,800 --> 00:32:20,900 y el pequeño número están burbujeando hasta la parte inferior. 888 00:32:20,900 --> 00:32:22,390 ¿Y ahora esta cosa aquí ordenada. 889 00:32:22,390 --> 00:32:25,260 Y en un aparte, en las plazas, no hay sólo algunas de contabilidad allí para 890 00:32:25,260 --> 00:32:28,010 le ayudan a contar la cantidad de comparaciones, o cuántos swaps tener 891 00:32:28,010 --> 00:32:28,950 En realidad se ha hecho. 892 00:32:28,950 --> 00:32:30,750 >> Bueno, vamos a probar una de los otros que vimos. 893 00:32:30,750 --> 00:32:37,116 Permítanme clic en especie de burbuja aquí, y permitirme elegir, y esta página web entera 894 00:32:37,116 --> 00:32:38,936 es un poco buggy. 895 00:32:38,936 --> 00:32:41,155 Aceptemos el riesgo y ejecutarlo de nuevo. 896 00:32:41,155 --> 00:32:44,560 897 00:32:44,560 --> 00:32:45,030 Eso es. 898 00:32:45,030 --> 00:32:47,180 Así que vamos a hacer la selección de clasificación. 899 00:32:47,180 --> 00:32:49,140 No sé por qué el menú aparece por allí. 900 00:32:49,140 --> 00:32:54,070 Vamos a acercar a arreglar eso bug, cambiarlo a 50. 901 00:32:54,070 --> 00:32:56,020 Ah, vamos a hacer realidad que mucho más rápido. 902 00:32:56,020 --> 00:32:59,160 Cinco milisegundos o menos, y en Inicio. 903 00:32:59,160 --> 00:33:00,470 >> Así que esta es la selección de clasificación. 904 00:33:00,470 --> 00:33:03,070 Así que de nuevo, pensar en lo que lo hizo con los humanos hasta aquí. 905 00:33:03,070 --> 00:33:08,490 Fuimos a través de la matriz y seleccionamos el elemento más pequeño de nuevo, 906 00:33:08,490 --> 00:33:09,250 y otra vez, y otra vez. 907 00:33:09,250 --> 00:33:11,110 Ahora afirmo que todavía era bastante malo. 908 00:33:11,110 --> 00:33:15,010 Seguía siendo n al cuadrado, más o menos, pero fue, en el mundo real, un poco 909 00:33:15,010 --> 00:33:18,280 más rápido, porque yo estaba de hecho tomando ligeramente menos pasos cada vez. 910 00:33:18,280 --> 00:33:19,800 Pero nosotros sólo estamos hablando, ¿qué? 911 00:33:19,800 --> 00:33:21,830 Tal vez 40 o más barras de aquí? 912 00:33:21,830 --> 00:33:23,200 No estamos hablando de 40 millones. 913 00:33:23,200 --> 00:33:27,430 Así que no es totalmente claro para mí que era de hecho una ganancia significativa. 914 00:33:27,430 --> 00:33:32,530 >> Permítanme ahora volver atrás y cambiar a nuestro tercer algoritmo, que era seleccione 915 00:33:32,530 --> 00:33:33,180 ordenación por inserción. 916 00:33:33,180 --> 00:33:36,380 Y ahora está realmente buggy porque el menú realmente no debería estar allí. 917 00:33:36,380 --> 00:33:40,840 Así que ahora vamos a retroceder hasta aquí y empezar este algoritmo. 918 00:33:40,840 --> 00:33:43,270 Whoop, iniciar y detener. 919 00:33:43,270 --> 00:33:47,160 Así que éste tipo de tiene un patrón bastante a la misma, con lo cual estamos de nuevo 920 00:33:47,160 --> 00:33:50,240 la inserción de los seres humanos, o en este caso, las barras en 921 00:33:50,240 --> 00:33:52,620 su ubicación adecuada. 922 00:33:52,620 --> 00:33:55,430 Y es que ya ha hecho antes Me di la vuelta. 923 00:33:55,430 --> 00:33:58,940 Pero éste, también, en teoría, todavía está n al cuadrado. 924 00:33:58,940 --> 00:34:01,430 >> Así que veamos si no podemos resumir éstos como sigue. 925 00:34:01,430 --> 00:34:04,750 Voy a seguir adelante y sólo para dar nosotros una especie de una manera común de hablar 926 00:34:04,750 --> 00:34:08,489 acerca de estas cosas, permítanme presentarles sólo un poco de notación aquí. 927 00:34:08,489 --> 00:34:12,480 Estás a punto de ver algo que se llama gran O, ya que es, literalmente, una gran 928 00:34:12,480 --> 00:34:16,320 O. Y esta es una manera de que un ordenador científico o un matemático usos incluso 929 00:34:16,320 --> 00:34:19,230 para describir el tiempo de ejecución de algún algoritmo. 930 00:34:19,230 --> 00:34:21,400 ¿Cuántos pasos que realmente necesita? 931 00:34:21,400 --> 00:34:25,080 >> Ahora me voy a avergonzar a mí mismo con mi letra aquí en un momento. 932 00:34:25,080 --> 00:34:29,020 Pero déjame seguir adelante y decir que esto va a ser grande O por aquí. 933 00:34:29,020 --> 00:34:33,610 Y permítanme presentarles a otro símbolo, un omega mayúscula. 934 00:34:33,610 --> 00:34:37,080 Omega va a ser todo lo contrario, en esencia, de la gran O. Considerando que la gran O 935 00:34:37,080 --> 00:34:40,790 significa, en el peor de los casos, la cantidad de tiempo podría tomar algún algoritmo, en 936 00:34:40,790 --> 00:34:43,480 términos de n, omega va a será la cantidad de tiempo que podría 937 00:34:43,480 --> 00:34:45,409 tomar en el mejor de los casos. 938 00:34:45,409 --> 00:34:48,090 Y veremos lo que entendemos por mejor de los casos, en un momento. 939 00:34:48,090 --> 00:34:49,940 >> Así que vamos a empezar algo simple. 940 00:34:49,940 --> 00:34:54,719 Permítanme comenzar con una búsqueda lineal. 941 00:34:54,719 --> 00:34:55,679 Así no clasificación. 942 00:34:55,679 --> 00:34:58,000 Llamaremos a esta búsqueda lineal. 943 00:34:58,000 --> 00:35:01,140 Y ahora, hacer un poco de mesa de salir de esto. 944 00:35:01,140 --> 00:35:06,600 Y ahora, en el caso de búsqueda lineal, en el peor de los casos, la cantidad de pasos es 945 00:35:06,600 --> 00:35:11,770 que me va a llevar a encontrar una número de elección arbitraria? 946 00:35:11,770 --> 00:35:14,540 Y hay n puertas totales o n números totales. 947 00:35:14,540 --> 00:35:15,940 Peor de los casos. 948 00:35:15,940 --> 00:35:18,800 ¿Cuántos pasos voy a tener que tomar para encontrar el número 50 en una serie 949 00:35:18,800 --> 00:35:20,830 de n puertas? 950 00:35:20,830 --> 00:35:21,410 ¿Y por qué? 951 00:35:21,410 --> 00:35:23,680 Debido a que puede ser todo el muy por encima en el extremo. 952 00:35:23,680 --> 00:35:27,120 Así que al igual que Jennifer se encontró con el número 50 fue todo el camino, por lo que en 953 00:35:27,120 --> 00:35:30,760 el peor de los casos búsqueda lineal es gran O de n, vamos a decir. 954 00:35:30,760 --> 00:35:33,430 >> ¿Y el mejor de los casos, si usted consigue realmente afortunado? 955 00:35:33,430 --> 00:35:36,200 Sólo va a dar un paso, o un número constante de pasos. 956 00:35:36,200 --> 00:35:37,830 Así que vamos a describir eso como 1. 957 00:35:37,830 --> 00:35:39,010 Así que esto es bastante bueno. 958 00:35:39,010 --> 00:35:41,210 Ahora lo que si hemos hecho algo como búsqueda binaria? 959 00:35:41,210 --> 00:35:43,860 960 00:35:43,860 --> 00:35:47,846 Así que la búsqueda binaria, en el peor de los casos caso, se llevó la cantidad de tiempo? 961 00:35:47,846 --> 00:35:49,250 >> [VOCES interponiendo] 962 00:35:49,250 --> 00:35:51,310 >> DAVID J. MALAN: Así que en realidad, escuchado en un par de lugares. 963 00:35:51,310 --> 00:35:56,390 Así que en realidad es log n, más o menos, porque como se divide la lista en media 964 00:35:56,390 --> 00:36:00,730 otra vez, y otra vez, y otra vez, somos capaces de encontrar, en última instancia, el valor, 965 00:36:00,730 --> 00:36:04,750 si está allí, pero hay una trampa. 966 00:36:04,750 --> 00:36:08,590 ¿Cuál es la suposición de que tenemos que dar por sentado de búsqueda binaria? 967 00:36:08,590 --> 00:36:09,700 Tiene que ser resuelto. 968 00:36:09,700 --> 00:36:12,770 No es ordenada, se puede dividir la cosa la mitad otra vez y otra vez, y usted 969 00:36:12,770 --> 00:36:15,490 puede ir a la izquierda, y se puede ir a la derecha, y usted puede ir a la izquierda y la derecha, pero usted es 970 00:36:15,490 --> 00:36:18,070 No va a encontrar el elemento si la lista no está ordenada, porque 971 00:36:18,070 --> 00:36:18,790 puede que te pierdas. 972 00:36:18,790 --> 00:36:22,120 Debido a que su heurística, para ir a la izquierda o hacia la derecha va a ser defectuoso si es 973 00:36:22,120 --> 00:36:23,420 de hecho, no ordenados. 974 00:36:23,420 --> 00:36:26,110 Así que hay una especie de costo oculto para el uso de algo como esto. 975 00:36:26,110 --> 00:36:29,250 >> Ahora, vamos a entrar en nuestra clasificación algoritmos no busca - 976 00:36:29,250 --> 00:36:31,140 oh, realmente vamos a ir en este espacio en blanco. 977 00:36:31,140 --> 00:36:33,190 La búsqueda binaria en el mejor de los casos? 978 00:36:33,190 --> 00:36:36,290 También es 1 si sólo pasa a ser en pleno centro de la matriz, o 979 00:36:36,290 --> 00:36:37,810 el medio de la guía telefónica. 980 00:36:37,810 --> 00:36:39,710 Ahora vamos a hacer una especie de burbuja. 981 00:36:39,710 --> 00:36:42,570 Así que de nuevo, ahora que estamos entrando en el tipo, no las búsquedas. 982 00:36:42,570 --> 00:36:47,220 >> En el peor de los casos, el número de pasos que hicieron burbuja reclamo especie va a tomar? 983 00:36:47,220 --> 00:36:48,410 n al cuadrado. 984 00:36:48,410 --> 00:36:49,200 Así que voy a dibujar eso. 985 00:36:49,200 --> 00:36:51,710 Ooh, mi letra se ve aún peor cuando se proyecta tan grande. 986 00:36:51,710 --> 00:36:52,510 Está bien. 987 00:36:52,510 --> 00:36:53,570 Así que eso es n al cuadrado. 988 00:36:53,570 --> 00:36:59,460 ¿Y en el mejor de los casos de ordenación de burbuja, cuántos pasos se va a tomar? 989 00:36:59,460 --> 00:37:00,980 1, lo escuché. 990 00:37:00,980 --> 00:37:01,760 >> ALTAVOZ 1: n. 991 00:37:01,760 --> 00:37:03,286 >> DAVID J. MALAN: n, he oído. 992 00:37:03,286 --> 00:37:04,200 >> ALTAVOZ 1: 2. 993 00:37:04,200 --> 00:37:05,010 >> DAVID J. MALAN: 2, escuché. 994 00:37:05,010 --> 00:37:06,670 ¿Escucho 3? 995 00:37:06,670 --> 00:37:07,080 Está bien. 996 00:37:07,080 --> 00:37:11,390 Eso he oído 1, n, 2, pero vamos a elegir Además, al menos el primero de los 997 00:37:11,390 --> 00:37:12,330 sugerencias, 1. 998 00:37:12,330 --> 00:37:15,370 No es una mala instinto, porque clase de la siguiente manera un patrón aquí. 999 00:37:15,370 --> 00:37:19,670 Pero si sólo se necesita 1 paso, como en el mundo podría yo afirmar que la lista 1000 00:37:19,670 --> 00:37:22,900 está ordenada, porque si sólo se me permite tomar 1 paso, ¿cuántos elementos 1001 00:37:22,900 --> 00:37:25,230 pude comprobar realmente estar seguro? 1002 00:37:25,230 --> 00:37:28,270 Bueno, sólo 1, que significa que hay n menos 1 elementos que podrían estar fuera de 1003 00:37:28,270 --> 00:37:31,310 orden, y yo sólo voy a la fe después de mirando a 1 elemento que el 1004 00:37:31,310 --> 00:37:31,850 cosa está ordenada. 1005 00:37:31,850 --> 00:37:33,930 Así 1 de no corrige aquí. 1006 00:37:33,930 --> 00:37:35,710 Así mínimamente, ¿cuántos Qué tengo que mirar? 1007 00:37:35,710 --> 00:37:36,680 >> [VOCES interponiendo] 1008 00:37:36,680 --> 00:37:40,160 >> DAVID J. MALAN: n menos 1, o en realidad, n, porque tengo que mirar cada 1009 00:37:40,160 --> 00:37:42,190 elemento para asegurarse de que no es fuera de servicio. 1010 00:37:42,190 --> 00:37:44,750 Pero una vez más, vamos a clase de agitamos nuestra manos en los números más pequeños y 1011 00:37:44,750 --> 00:37:47,100 asumen que, a medida que n se hace grande, son poco interesante de todos modos. 1012 00:37:47,100 --> 00:37:48,380 Así que es una especie de burbuja. 1013 00:37:48,380 --> 00:37:49,830 Y ahora, vamos a hacer estos dos últimos. 1014 00:37:49,830 --> 00:37:53,520 Selección de tipo, y luego vamos a hacer la ordenación por inserción. 1015 00:37:53,520 --> 00:37:57,160 Y luego vamos a volar tu mentes con algo mucho 1016 00:37:57,160 --> 00:37:58,926 mejor que todos ellos. 1017 00:37:58,926 --> 00:38:00,410 Está bien. 1018 00:38:00,410 --> 00:38:04,700 >> ¿Cuál es el peor de los casos se ejecuta momento de la selección especie? 1019 00:38:04,700 --> 00:38:05,680 >> SPEAKER 4: n al cuadrado. 1020 00:38:05,680 --> 00:38:06,710 >> DAVID J. MALAN: n cuadrado, lo que estoy oyendo. 1021 00:38:06,710 --> 00:38:09,790 Pero ¿por qué n al cuadrado, intuitivamente? 1022 00:38:09,790 --> 00:38:11,170 >> ALTAVOZ 4: Debido a que sólo lo hicimos. 1023 00:38:11,170 --> 00:38:12,260 >> DAVID J. MALAN: Debido a que acabamos de hacer eso. 1024 00:38:12,260 --> 00:38:12,550 Aceptar. 1025 00:38:12,550 --> 00:38:13,380 Buena respuesta. 1026 00:38:13,380 --> 00:38:16,660 Pero intuitivamente, ¿por qué es la selección tipo n al cuadrado? 1027 00:38:16,660 --> 00:38:18,980 ¿Qué teníamos que hacer una y otra vez? 1028 00:38:18,980 --> 00:38:22,570 Tuvimos que mantener la exploración a través, son que los más pequeños, ¿es usted el 1029 00:38:22,570 --> 00:38:24,020 más pequeño, ¿eres tú el más pequeño. 1030 00:38:24,020 --> 00:38:27,480 Y sentado, hemos sido capaces de tomar n pasos, entonces n menos 1, entonces n menos 2. 1031 00:38:27,480 --> 00:38:30,700 Pero si que tipo de agrega los todo, o llevatelo contigo en la fe de que he añadido 1032 00:38:30,700 --> 00:38:34,810 ellos de antemano, obtenemos aproximadamente n cuadrado menos algunos números más pequeños. 1033 00:38:34,810 --> 00:38:36,730 Así que voy a llamar a este n al cuadrado. 1034 00:38:36,730 --> 00:38:39,530 Pero con ordenación por selección de la mejor caso, la cantidad de pasos es 1035 00:38:39,530 --> 00:38:40,632 me va a llevar? 1036 00:38:40,632 --> 00:38:41,840 >> ALTAVOZ 5: [inaudible] 1037 00:38:41,840 --> 00:38:44,350 >> DAVID J. MALAN: Es lamentablemente siendo n al cuadrado, ¿verdad? 1038 00:38:44,350 --> 00:38:49,590 Porque si estoy seleccionando los más pequeños elemento, y que teníamos siete personas aquí, 1039 00:38:49,590 --> 00:38:53,280 Lo único que sé, una vez que llegue a la misma fin, que he encontrado el más pequeño 1040 00:38:53,280 --> 00:38:55,670 número, donde sea que él o ella pudo haber sido. 1041 00:38:55,670 --> 00:38:58,820 Pero ¿cómo puedo encontrar la siguiente menor número? 1042 00:38:58,820 --> 00:39:00,160 Tengo que hacer otra pasada. 1043 00:39:00,160 --> 00:39:04,810 Así que en el mejor de los casos, lo que es lo entrada a la selección de tipo? 1044 00:39:04,810 --> 00:39:07,830 Se trata de una especie ya lista, el número uno, número dos, número tres, número cuatro. 1045 00:39:07,830 --> 00:39:08,600 Pero yo soy un ordenador. 1046 00:39:08,600 --> 00:39:10,190 Sólo puedo mirar uno cosa a la vez. 1047 00:39:10,190 --> 00:39:12,465 No puedo especie de dar un paso de nuevo como un ser humano y decir: 1048 00:39:12,465 --> 00:39:14,030 ooh, esto parece correcto. 1049 00:39:14,030 --> 00:39:17,580 >> Sólo puedo juzgar la corrección en ordenación por selección mediante la selección de la 1050 00:39:17,580 --> 00:39:18,370 número más pequeño. 1051 00:39:18,370 --> 00:39:21,390 Pero incluso si encuentro el número uno en primer lugar, si yo no sé nada más sobre 1052 00:39:21,390 --> 00:39:24,460 los demás números, que no lo hago, todo lo que Sé que me han dado una serie 1053 00:39:24,460 --> 00:39:27,930 o un conjunto de puertas detrás de las cuales son números, la única manera que sé que uno 1054 00:39:27,930 --> 00:39:28,680 era la más pequeña? 1055 00:39:28,680 --> 00:39:32,440 Si consigo todo el camino hasta aquí y me doy cuenta, maldita sea, uno era de hecho el más pequeño. 1056 00:39:32,440 --> 00:39:34,870 >> Pero ¿cómo puedo entonces determino que dos es la siguiente más pequeña? 1057 00:39:34,870 --> 00:39:38,350 Al hacer la misma ineficiencia una y otra vez. 1058 00:39:38,350 --> 00:39:42,210 Así que finalmente, con la ordenación por inserción, cómo, en el peor de los casos, 1059 00:39:42,210 --> 00:39:44,990 dijimos que realiza? 1060 00:39:44,990 --> 00:39:49,100 Es demasiado n al cuadrado. 1061 00:39:49,100 --> 00:39:53,020 ¿Y qué hay con el mejor de los casos? 1062 00:39:53,020 --> 00:39:56,282 Dejaremos que a medida que un cliffhanger. 1063 00:39:56,282 --> 00:40:00,090 Vamos a llenar ese espacio en blanco la próxima vez, pero primero déjame propongo que 1064 00:40:00,090 --> 00:40:02,620 fundamentalmente hacer mejor que todo esto, ¿de acuerdo? 1065 00:40:02,620 --> 00:40:05,220 >> Así que piense por sí mismo lo inserción especie que va a ser. 1066 00:40:05,220 --> 00:40:06,910 Bueno, eso no fue muy dramática, porque yo soy el único 1067 00:40:06,910 --> 00:40:08,970 que vio el cambio. 1068 00:40:08,970 --> 00:40:09,620 Wow. 1069 00:40:09,620 --> 00:40:10,420 Aceptar. 1070 00:40:10,420 --> 00:40:12,615 Así que aquí tenemos un poco diferente manifestación. 1071 00:40:12,615 --> 00:40:16,580 Si hago zoom aquí, verás que en la izquierda tenemos una especie de burbuja, en el 1072 00:40:16,580 --> 00:40:20,740 centro tenemos ordenación por selección, y en la extrema derecha, que tienen algo que 1073 00:40:20,740 --> 00:40:23,380 no han mirado todavía llamado merge sort. 1074 00:40:23,380 --> 00:40:26,080 Pero consideremos lo que hemos sido haciendo aquí hasta el momento actual. 1075 00:40:26,080 --> 00:40:29,200 Cuando Jennifer llegó por primera vez en el escenario, nos fuimos a través de la matriz de números 1076 00:40:29,200 --> 00:40:33,750 otra vez, y otra vez, con búsqueda lineal, y tenemos tiempo de funcionamiento lineal, gran O 1077 00:40:33,750 --> 00:40:35,100 de n, por así decirlo. 1078 00:40:35,100 --> 00:40:41,000 >> Cuando consideramos ahora la primera semana de clase, cuando habíamos dividir y conquistar, 1079 00:40:41,000 --> 00:40:43,740 y tuvimos el lagrimeo guía telefónica, y Jennifer, y colectivamente 1080 00:40:43,740 --> 00:40:47,500 apalancada que idea clave, que debía repetirte una y otra vez por 1081 00:40:47,500 --> 00:40:50,930 de alguna manera tirar, tirar, tirar, medio del problema, o 1082 00:40:50,930 --> 00:40:55,320 en general, la división de un problema en un medio, y luego el tratamiento de la pieza más pequeña de 1083 00:40:55,320 --> 00:40:59,630 el problema como conceptualmente equivalente a la otra, de alguna manera hicimos 1084 00:40:59,630 --> 00:41:00,910 fundamentalmente mejor. 1085 00:41:00,910 --> 00:41:04,720 Pero con la ordenación de burbuja, con la selección especie, con la ordenación por inserción, hemos podrá 1086 00:41:04,720 --> 00:41:06,560 hay tales ideas que Jennifer hizo. 1087 00:41:06,560 --> 00:41:10,220 Nos prácticamente sólo caminamos de regreso y sucesivamente un montón de veces, y nos 1088 00:41:10,220 --> 00:41:12,650 ajustado un poco las cosas, el intercambio de en este orden, tal vez 1089 00:41:12,650 --> 00:41:13,730 la inserción o la selección. 1090 00:41:13,730 --> 00:41:16,950 Pero al final del día, hice un montón torpe caminar de ida y vuelta. 1091 00:41:16,950 --> 00:41:21,160 Nosotros realmente no aprovechamos algo inteligente como Jennifer le gustaba dividiendo 1092 00:41:21,160 --> 00:41:22,040 y conquistando. 1093 00:41:22,040 --> 00:41:25,620 >> Así fusionar especie, por el contrario, que nos no verá hasta la próxima semana, que va 1094 00:41:25,620 --> 00:41:29,540 para aprovechar esa idea clave dividiendo la entrada y, a continuación, reducir a la mitad, y luego 1095 00:41:29,540 --> 00:41:30,580 reducir a la mitad, y luego reducir a la mitad. 1096 00:41:30,580 --> 00:41:34,590 Y en cada iteración del bucle que, la clasificación de la mitad izquierda y la derecha 1097 00:41:34,590 --> 00:41:38,200 medio, entonces la mitad izquierda de la mitad izquierda, y la mitad derecha de la izquierda, a continuación, 1098 00:41:38,200 --> 00:41:40,990 la mitad izquierda de la mitad derecha, y la mitad derecha de la mitad derecha. 1099 00:41:40,990 --> 00:41:42,840 Y repitiendo una y otra vez. 1100 00:41:42,840 --> 00:41:46,170 >> Así verás esto visualmente, pero esta es lo que nos espera la próxima semana. 1101 00:41:46,170 --> 00:41:49,760 Y, en general, cuando pensamos un poco poco más difícil en cualquier problema. 1102 00:41:49,760 --> 00:41:52,435 1103 00:41:52,435 --> 00:41:57,970 N Hemos cuadrado en el lado izquierdo, N cuadrado en el medio, y n 1104 00:41:57,970 --> 00:41:59,400 log n a la derecha. 1105 00:41:59,400 --> 00:42:00,590 Así que ahí está tu melodrama real. 1106 00:42:00,590 --> 00:42:02,040 Nos vemos el lunes. 1107 00:42:02,040 --> 00:42:05,163 >> [Aplausos]