1 00:00:00,000 --> 00:00:00,990 2 00:00:00,990 --> 00:00:02,970 >> [REPRODUCCIÓN DE MÚSICA] 3 00:00:02,970 --> 00:00:10,400 4 00:00:10,400 --> 00:00:12,550 >> DAVID J. MALAN: Este es CS50. 5 00:00:12,550 --> 00:00:14,612 Y este es el comienzo de la tercera semana. 6 00:00:14,612 --> 00:00:16,820 Así que tenemos un montón de emocionantes cosas que cubren la actualidad. 7 00:00:16,820 --> 00:00:20,160 Una gran cantidad de oportunidades para los voluntarios en el escenario. 8 00:00:20,160 --> 00:00:22,780 Y en última instancia, en la actualidad es No se trata de código. 9 00:00:22,780 --> 00:00:24,820 Pero se trata de ideas y se trata de algoritmos, 10 00:00:24,820 --> 00:00:28,420 y de hecho traer de vuelta algunos de las lecciones aprendidas de la semana cero, 11 00:00:28,420 --> 00:00:31,910 en donde recuerdo, nos introducido esta monstruosidad. 12 00:00:31,910 --> 00:00:33,880 Y el endeudamiento inspiración de que, para empezar 13 00:00:33,880 --> 00:00:36,879 para resolver cada vez más sofisticada problemas algorítmicamente. 14 00:00:36,879 --> 00:00:38,420 Pero primero, un par de anuncios. 15 00:00:38,420 --> 00:00:42,020 Así que uno, si usted desea unirse El personal y los compañeros de clase de CS50 en el almuerzo 16 00:00:42,020 --> 00:00:44,670 este viernes, tanto aquí como en Cambridge, y en New Haven, 17 00:00:44,670 --> 00:00:48,060 por favor visite el curso de sitio web, donde una URL se puede encontrar. 18 00:00:48,060 --> 00:00:50,390 Conferencia de este miércoles será no estar aquí en Sanders. 19 00:00:50,390 --> 00:00:53,610 Será sólo en línea, por lo que sintonizar en el sitio web del CS50, 20 00:00:53,610 --> 00:00:55,850 ya sea aquí en Cambridge o New Haven también. 21 00:00:55,850 --> 00:00:58,110 >> Y entonces un problema fijó dos ya está en tus manos. 22 00:00:58,110 --> 00:01:03,067 Si usted no ha buceado en el, sin embargo, permítanme para ofrecer la sugerencia enérgica 23 00:01:03,067 --> 00:01:05,150 que, sobre todo ahora, cuando el problema establece por adelantado, 24 00:01:05,150 --> 00:01:08,669 usted realmente desea comenzar ahora, si no incursionar un poco en el fin de semana o antes 25 00:01:08,669 --> 00:01:10,710 la primera vez que salen a Viernes, porque vas a 26 00:01:10,710 --> 00:01:14,380 encuentran que no son necesariamente cada vez más largos o más desafiante por 27 00:01:14,380 --> 00:01:14,950 se. 28 00:01:14,950 --> 00:01:17,575 Creo que usted encontrará que, en en general, tienden a tener más o menos 29 00:01:17,575 --> 00:01:18,892 alrededor misma cantidad de tiempo. 30 00:01:18,892 --> 00:01:20,850 Pero ciertamente depende en el estudiante, y 31 00:01:20,850 --> 00:01:22,880 depende de la mentalidad con la que te acercas a ella. 32 00:01:22,880 --> 00:01:24,910 Pero invariablemente, vas correr contra alguna pared, 33 00:01:24,910 --> 00:01:26,350 y vas a golpear algunos errores, y no eres más que 34 00:01:26,350 --> 00:01:27,950 no va a ser capaz de superarlo en algún momento. 35 00:01:27,950 --> 00:01:31,380 Y es enormemente valiosa para poder alejarse, volver al día siguiente, 36 00:01:31,380 --> 00:01:35,286 ir a las horas de oficina, mensaje el CS50 Discuta o similar, para conseguir realmente desbloqueado. 37 00:01:35,286 --> 00:01:36,160 Así que tenlo en mente. 38 00:01:36,160 --> 00:01:40,830 Comenzando temprano como sea posible es la mejor cosa que puedes hacer. 39 00:01:40,830 --> 00:01:44,160 Así que aquí es donde empezamos la clase, a lo largo de la semana cero. 40 00:01:44,160 --> 00:01:47,441 Y podemos conseguir un voluntario aquí para ayudarme a encontrar los micrófonos? 41 00:01:47,441 --> 00:01:47,940 OK. 42 00:01:47,940 --> 00:01:48,900 De pie ya. 43 00:01:48,900 --> 00:01:50,080 Vamos arriba. 44 00:01:50,080 --> 00:01:53,707 Supongo que eso es lo que va a trabajar. 45 00:01:53,707 --> 00:01:54,415 ¿Cómo te llamas? 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 Vamos arriba. 49 00:01:57,910 --> 00:01:58,619 Encantada de conocerte. 50 00:01:58,619 --> 00:01:59,910 ALAN ESTRADA: Encantado de conocerte. 51 00:01:59,910 --> 00:02:02,772 DAVID J. MALAN: Y usted estuviera aquí con nosotros en la semana cero, por supuesto. 52 00:02:02,772 --> 00:02:03,028 ALAN ESTRADA: yo. 53 00:02:03,028 --> 00:02:03,160 Yo era. 54 00:02:03,160 --> 00:02:05,868 >> DAVID J. MALAN: Así podría ir adelante y encontrar para nosotros Mike Smith, 55 00:02:05,868 --> 00:02:08,639 ¿tan rapido como puedas? 56 00:02:08,639 --> 00:02:10,639 Tan rapido como puedas. 57 00:02:10,639 --> 00:02:13,756 Literalmente desgarrar el problema en la mitad de lo que necesita. 58 00:02:13,756 --> 00:02:15,130 >> ALAN ESTRADA: Um. 59 00:02:15,130 --> 00:02:17,380 DAVID J. MALAN: Literalmente rasgando el problema en medio. 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 Muy bueno. 64 00:02:23,300 --> 00:02:23,700 >> DAVID J. MALAN: OK. 65 00:02:23,700 --> 00:02:24,200 Bien. 66 00:02:24,200 --> 00:02:24,701 Gracias. 67 00:02:24,701 --> 00:02:25,700 ALAN ESTRADA: Muy buena. 68 00:02:25,700 --> 00:02:26,210 OK. 69 00:02:26,210 --> 00:02:27,610 >> DAVID J. MALAN: Y por lo que ahora, que ha recortado hacia abajo 70 00:02:27,610 --> 00:02:29,320 a la mitad del tamaño del problema. 71 00:02:29,320 --> 00:02:31,267 Ahora, estamos a una cuarta parte. 72 00:02:31,267 --> 00:02:33,475 ¿Usted está prestando atención a de qué lado estamos manteniendo? 73 00:02:33,475 --> 00:02:34,405 >> [Risas] 74 00:02:34,405 --> 00:02:35,970 >> ALAN ESTRADA: Sí, yo think-- 75 00:02:35,970 --> 00:02:37,594 >> DAVID J. MALAN: ¿Qué sección estamos? 76 00:02:37,594 --> 00:02:39,150 ALAN ESTRADA: Mofles, así. 77 00:02:39,150 --> 00:02:39,941 >> DAVID J. MALAN: OK. 78 00:02:39,941 --> 00:02:42,810 Pero Mike Smith va a ser después de Mofles. 79 00:02:42,810 --> 00:02:44,130 Tan-- 80 00:02:44,130 --> 00:02:48,180 >> [Risas] 81 00:02:48,180 --> 00:02:48,742 >> Correcto. 82 00:02:48,742 --> 00:02:50,200 ALAN ESTRADA: ¿Dónde 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: Ahora, estamos en quirúrgico. 86 00:02:54,760 --> 00:02:57,840 Ahora, los médicos. 87 00:02:57,840 --> 00:02:58,340 Ahora-- 88 00:02:58,340 --> 00:02:59,856 >> ALAN ESTRADA: Let's- vamos 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 OK. 92 00:03:01,470 --> 00:03:03,700 Si necesita Real. 93 00:03:03,700 --> 00:03:05,250 Ahora, ¿qué camino es Mike Smith? 94 00:03:05,250 --> 00:03:06,250 >> ALAN ESTRADA: De esta forma. 95 00:03:06,250 --> 00:03:07,333 >> DAVID J. MALAN: Qué manera? 96 00:03:07,333 --> 00:03:08,240 ALAN ESTRADA: Espera. 97 00:03:08,240 --> 00:03:08,790 Derecho M es--? 98 00:03:08,790 --> 00:03:09,110 Empezamos con-- 99 00:03:09,110 --> 00:03:10,090 >> DAVID J. MALAN: Sí. 100 00:03:10,090 --> 00:03:10,650 Están a la izquierda. 101 00:03:10,650 --> 00:03:11,430 Su derecho. 102 00:03:11,430 --> 00:03:11,710 >> ALAN ESTRADA: Sí. 103 00:03:11,710 --> 00:03:13,126 >> DAVID J. MALAN: Así que Mike aquí. 104 00:03:13,126 --> 00:03:13,990 ALAN ESTRADA: ¿Qué? 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 ejemplo, chicos. 108 00:03:18,330 --> 00:03:18,830 Apenado. 109 00:03:18,830 --> 00:03:21,610 DAVID J. MALAN: Esto le enseñará a saltar de su silla. 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 tengo. 113 00:03:23,390 --> 00:03:24,670 Te tengo. 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 Esta es-- Bueno, te tengo. 117 00:03:26,812 --> 00:03:27,520 Smith aquí? 118 00:03:27,520 --> 00:03:28,894 >> DAVID J. MALAN: Smith, gracias. 119 00:03:28,894 --> 00:03:30,535 Así que voy a seguir mirando hacia arriba Smith? 120 00:03:30,535 --> 00:03:30,790 >> ALAN ESTRADA: Oh, sí. 121 00:03:30,790 --> 00:03:31,340 No no no. 122 00:03:31,340 --> 00:03:31,600 Oh no. 123 00:03:31,600 --> 00:03:31,940 Esto es mío. 124 00:03:31,940 --> 00:03:32,580 >> DAVID J. MALAN: Oh, tienes Smith. 125 00:03:32,580 --> 00:03:33,415 OK. 126 00:03:33,415 --> 00:03:34,040 >> ALAN ESTRADA: Sí, Smith consiguió aquí. 127 00:03:34,040 --> 00:03:34,700 Lo siento chicos. 128 00:03:34,700 --> 00:03:35,860 Pensé que Michael-- estabas buscando Michael. 129 00:03:35,860 --> 00:03:36,550 Apenado. 130 00:03:36,550 --> 00:03:37,550 >> DAVID J. MALAN: Está bien. 131 00:03:37,550 --> 00:03:39,950 Muy bien, ahora estamos en Paccini and Sons. 132 00:03:39,950 --> 00:03:41,242 >> ALAN ESTRADA: Paccini e hijos. 133 00:03:41,242 --> 00:03:43,158 DAVID J. MALAN: Sólo usted y yo estamos en esto. 134 00:03:43,158 --> 00:03:44,050 OK. 135 00:03:44,050 --> 00:03:45,130 Encuéntrenos 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 basura. 140 00:03:47,728 --> 00:03:48,644 ALAN ESTRADA: Malo. 141 00:03:48,644 --> 00:03:50,096 Oh. 142 00:03:50,096 --> 00:03:52,480 Esto va a tomar un tiempo. 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: Zapatos. 146 00:03:56,720 --> 00:03:58,080 Estamos en los zapatos. 147 00:03:58,080 --> 00:04:00,210 >> ALAN ESTRADA: Ahora estamos gonna-- 148 00:04:00,210 --> 00:04:01,105 >> DAVID J. MALAN: Niza. 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, esto es genial. 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: Está bien. 155 00:04:09,390 --> 00:04:11,365 >> ALAN ESTRADA: Oh, eso es bueno. 156 00:04:11,365 --> 00:04:14,425 No creo que me voy a tener amigos PSAT después de esto. 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 Um, L, M, N, O, P. 161 00:04:18,668 --> 00:04:19,459 DAVID J. MALAN: OK. 162 00:04:19,459 --> 00:04:21,600 Así que vamos a lágrima esto en medio. 163 00:04:21,600 --> 00:04:22,270 Esta bien. 164 00:04:22,270 --> 00:04:25,606 Esto termina mal de todos modos, porque Mike Smith no estará en las páginas amarillas. 165 00:04:25,606 --> 00:04:26,430 >> ALAN ESTRADA: Aw. 166 00:04:26,430 --> 00:04:27,140 >> DAVID J. MALAN: No, está bien. 167 00:04:27,140 --> 00:04:28,930 Pero vamos a suponer como él está en esta página. 168 00:04:28,930 --> 00:04:33,260 Así que ahora, usted ha recortado el problema abajo de una página, y nos encontramos con Mike Smith. 169 00:04:33,260 --> 00:04:35,180 >> [ANIMA] 170 00:04:35,180 --> 00:04:35,757 171 00:04:35,757 --> 00:04:36,340 Ok, gracias. 172 00:04:36,340 --> 00:04:40,700 173 00:04:40,700 --> 00:04:41,200 OK. 174 00:04:41,200 --> 00:04:43,646 Eso fue extraordinario. 175 00:04:43,646 --> 00:04:45,954 Pero fue aún más rápido de búsqueda lineal, 176 00:04:45,954 --> 00:04:47,870 en el que empezamos a a partir del libro, 177 00:04:47,870 --> 00:04:51,210 y nos movemos nuestra forma de izquierda a derecha, finalmente, en busca de Mike Smith. 178 00:04:51,210 --> 00:04:53,540 Y así, si la guía telefónica tenía tal vez 1.000 páginas, 179 00:04:53,540 --> 00:04:56,300 tal vez habría tomado nos 10 o más páginas lágrimas. 180 00:04:56,300 --> 00:04:59,380 >> Pero es posible que haya aprovechado tocado una suposición 181 00:04:59,380 --> 00:05:03,602 durante todo eso, lo que es decir, que la guía de teléfonos de antemano era qué? 182 00:05:03,602 --> 00:05:04,310 AUDIENCIA: Ordenado. 183 00:05:04,310 --> 00:05:05,000 DAVID J. MALAN: Ha solucionado. 184 00:05:05,000 --> 00:05:05,160 ¿Correcto? 185 00:05:05,160 --> 00:05:07,909 Se ordena alfabéticamente, por lo que todos esos nombres y números 186 00:05:07,909 --> 00:05:11,230 están ordenadas por los Atléticos a la Z, y en orden alfabético en el medio. 187 00:05:11,230 --> 00:05:13,100 Pero hoy en día, nos preguntamos ahora la pregunta, bueno, 188 00:05:13,100 --> 00:05:16,170 ¿cómo Verizon o el teléfono empresa ponerlo en ese estado? 189 00:05:16,170 --> 00:05:19,560 >> Debido a que es una cosa de aprovechar esa suposición, y por lo tanto, 190 00:05:19,560 --> 00:05:22,570 resolver un problema con un algoritmo más eficiente. 191 00:05:22,570 --> 00:05:24,900 Pero en realidad nunca pedido en la semana cero, bueno, 192 00:05:24,900 --> 00:05:27,790 cuanto costo Verizon o alguien más 193 00:05:27,790 --> 00:05:29,620 para conseguir que la libreta de teléfonos en forma ordenada? 194 00:05:29,620 --> 00:05:29,780 >> ¿Correcto? 195 00:05:29,780 --> 00:05:31,529 No importa si mirando hacia arriba Mike Smith 196 00:05:31,529 --> 00:05:35,190 es súper rápido, si usted toma un año para ordenar las páginas inicialmente. 197 00:05:35,190 --> 00:05:35,690 ¿Correcto? 198 00:05:35,690 --> 00:05:38,620 Usted puede ser que también acaba de tamizar a través de un libro de teléfono al azar, 199 00:05:38,620 --> 00:05:40,690 si va a ser súper cara a solucionar el problema. 200 00:05:40,690 --> 00:05:42,350 Así que si podemos tener otro voluntario. 201 00:05:42,350 --> 00:05:46,350 Vamos a echar un vistazo aquí a cómo might-- Vamos up-- cómo 202 00:05:46,350 --> 00:05:48,100 podríamos ir sobre la clasificación de los mismos. 203 00:05:48,100 --> 00:05:51,990 >> Y si Jordan podía realidad únete a nosotros aquí en el escenario. 204 00:05:51,990 --> 00:05:55,100 Vamos para arriba para un momento. 205 00:05:55,100 --> 00:05:56,359 ¿Cómo te llamas? 206 00:05:56,359 --> 00:05:57,150 CAROLINE: Caroline. 207 00:05:57,150 --> 00:05:58,691 DAVID J. MALAN: Caroline, vamos para arriba. 208 00:05:58,691 --> 00:06:02,070 Y se te uniste por mí y Jordania aquí. 209 00:06:02,070 --> 00:06:03,800 Caroline, gracias. 210 00:06:03,800 --> 00:06:04,300 Correcto. 211 00:06:04,300 --> 00:06:08,330 Así que lo que tenemos aquí Caroline tiene 26 libros azules 212 00:06:08,330 --> 00:06:10,747 que FAS utiliza para administrar ciertos exámenes finales. 213 00:06:10,747 --> 00:06:13,330 Estos son cada vez difícil de encontrar, pero lo que hemos hecho con antelación 214 00:06:13,330 --> 00:06:15,800 es que nos hemos puesto el nombre de alguien en la parte frontal de cada uno de estos, 215 00:06:15,800 --> 00:06:18,133 pero nos hemos mantenido simple a continuación, poner los nombres completos. 216 00:06:18,133 --> 00:06:22,720 Así que nos gustaría poner a la persona con el nombre A, C, J, B, hasta el final de la A a la Z, 217 00:06:22,720 --> 00:06:24,090 pero están en orden aleatorio. 218 00:06:24,090 --> 00:06:26,890 Y por lo que si lo haría, hablando de su camino a través de los problemas y se le 219 00:06:26,890 --> 00:06:31,620 hazlo, puede seguir adelante y ordenar estos para nosotros, de la A a la Z. 220 00:06:31,620 --> 00:06:34,070 >> AUDIENCIA: OK, entonces L es como, el medio. 221 00:06:34,070 --> 00:06:35,050 C está comenzando. 222 00:06:35,050 --> 00:06:42,410 B. J antes de L. B, Q. 223 00:06:42,410 --> 00:06:45,140 >> DAVID J. MALAN: Mantenga esa pensado por un segundo. 224 00:06:45,140 --> 00:06:48,910 Porque de lo contrario, esto es sólo interesante para usted, yo, y Jordania. 225 00:06:48,910 --> 00:06:49,724 Allá vamos. 226 00:06:49,724 --> 00:06:50,640 AUDIENCIA: [inaudible]. 227 00:06:50,640 --> 00:06:57,299 R. 228 00:06:57,299 --> 00:06:58,090 DAVID J. MALAN: OK. 229 00:06:58,090 --> 00:06:59,310 ¿Qué estás haciendo? 230 00:06:59,310 --> 00:07:01,730 >> CAROLINE: M se produce después de O. 231 00:07:01,730 --> 00:07:02,564 >> DAVID J. MALAN: OK. 232 00:07:02,564 --> 00:07:03,064 >> CAROLINE: O. 233 00:07:03,064 --> 00:07:04,120 DAVID J. MALAN: O, bueno. 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. Sí. 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. Por lo tanto, Parece que eres making-- seguir adelante. 238 00:07:10,689 --> 00:07:12,730 Parece que estás haciendo una pila grande aquí, 239 00:07:12,730 --> 00:07:13,910 y la clase de una gran pila de allá. 240 00:07:13,910 --> 00:07:16,230 Así que la primera mitad del alfabeto, segunda mitad del alfabeto. 241 00:07:16,230 --> 00:07:16,460 OK. 242 00:07:16,460 --> 00:07:16,960 Bien. 243 00:07:16,960 --> 00:07:19,680 Tipo de dividir el problema en dos. 244 00:07:19,680 --> 00:07:21,771 M, N, X. Sí. 245 00:07:21,771 --> 00:07:22,270 CAROLINE: K. 246 00:07:22,270 --> 00:07:22,980 DAVID J. MALAN: OK. 247 00:07:22,980 --> 00:07:25,070 K. Así que estás tipo de selección uno tras otro, 248 00:07:25,070 --> 00:07:27,620 poniéndolo a la izquierda oa la derecha, o Z va en el suelo. 249 00:07:27,620 --> 00:07:28,012 OK. 250 00:07:28,012 --> 00:07:29,190 >> CAROLINE: Z va en el suelo. 251 00:07:29,190 --> 00:07:29,360 >> DAVID J. MALAN: OK. 252 00:07:29,360 --> 00:07:30,920 Y va en el suelo. 253 00:07:30,920 --> 00:07:31,735 Ahora podemos poner 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 va a la izquierda. 256 00:07:33,700 --> 00:07:36,017 S va bien. 257 00:07:36,017 --> 00:07:37,642 Todo derecho, A va todo el camino de la izquierda. 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: Ahora, bien. 260 00:07:39,873 --> 00:07:43,260 Tenemos A, B, C. W de ir allí. 261 00:07:43,260 --> 00:07:45,566 Muy bien, 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. Bueno. 264 00:07:47,860 --> 00:07:49,160 CAROLINE: En el centro, estoy gonna-- 265 00:07:49,160 --> 00:07:50,000 DAVID J. MALAN: OK. 266 00:07:50,000 --> 00:07:52,375 Así que ahora, vamos a clase de combinar estos diversos montones. 267 00:07:52,375 --> 00:08:00,730 Así la A a C, entonces veo D, y E y F, y G, y H e I. Niza. 268 00:08:00,730 --> 00:08:05,540 J, K. Y luego, esta pila es al revés, pero eso está bien. 269 00:08:05,540 --> 00:08:06,040 Por supuesto. 270 00:08:06,040 --> 00:08:07,240 Podemos cortar algunas esquinas. 271 00:08:07,240 --> 00:08:07,950 OK. 272 00:08:07,950 --> 00:08:10,530 Y entonces tenemos que W, X, Y, Z. 273 00:08:10,530 --> 00:08:11,250 >> CAROLINE: Sí. 274 00:08:11,250 --> 00:08:11,880 >> DAVID J. MALAN: Excelente. 275 00:08:11,880 --> 00:08:14,122 Así que un gran agradecimiento a Caroline para la clasificación de estos. 276 00:08:14,122 --> 00:08:15,030 >> [ANIMA] 277 00:08:15,030 --> 00:08:17,287 >> Gracias. 278 00:08:17,287 --> 00:08:18,120 Muchas gracias. 279 00:08:18,120 --> 00:08:22,910 Así que ahora vamos a considerar por un momento cómo Caroline anduvo haciendo eso, 280 00:08:22,910 --> 00:08:26,040 y qué es exactamente lo que fueron capaces a-- cómo 281 00:08:26,040 --> 00:08:28,409 fueron capaces de resolver ese problema cuando estábamos 282 00:08:28,409 --> 00:08:29,950 dado un montón de entradas aleatorias. 283 00:08:29,950 --> 00:08:31,610 >> Bueno, parece que hay era un poco de un sistema allí? 284 00:08:31,610 --> 00:08:32,110 Correcto. 285 00:08:32,110 --> 00:08:34,495 Así que las cartas anteriores en el alfabeto, ella 286 00:08:34,495 --> 00:08:37,120 era poner a la izquierda, y el últimas cartas en el alfabeto, 287 00:08:37,120 --> 00:08:38,270 que estaba poniendo en la derecha. 288 00:08:38,270 --> 00:08:40,500 Y tan pronto como se enteró algunas cartas proximales, unos 289 00:08:40,500 --> 00:08:43,124 que van uno al lado del otro, pondría los de orden. 290 00:08:43,124 --> 00:08:46,750 Y por lo que de alguna manera tenía estos pequeños montones de entradas ordenadas ocurren. 291 00:08:46,750 --> 00:08:50,540 >> Y eso es muy parecido a lo que la mayoría de nosotros los humanos harían. 292 00:08:50,540 --> 00:08:53,530 Nos tipo de tamizar a través de él, y nos gustaría tipo de disponer de un mecanismo. 293 00:08:53,530 --> 00:08:56,930 Pero podría ser difícil escribir hacia abajo en una fórmula per se. 294 00:08:56,930 --> 00:08:59,010 Se sentía un poco más orgánico que eso. 295 00:08:59,010 --> 00:09:02,560 Así que vamos a ver si podemos ahora atado el problema con menos insumos. 296 00:09:02,560 --> 00:09:05,170 >> En lugar de 26, vamos a hacer algo mucho menos 297 00:09:05,170 --> 00:09:09,890 con sólo decir, siete, detrás estas puertas, por así decirlo. 298 00:09:09,890 --> 00:09:11,300 ¿Hay sólo siete números? 299 00:09:11,300 --> 00:09:15,240 Y si el objetivo ahora en mano es encontrar un valor, 300 00:09:15,240 --> 00:09:17,850 vamos a ver cómo de manera eficiente podemos ir haciendo esto. 301 00:09:17,850 --> 00:09:22,460 Y vamos a ver si podemos ahora empezar a aplicar algunos números, 302 00:09:22,460 --> 00:09:26,310 o algunas fórmulas con las que describen la eficiencia de nuestro directorio telefónico 303 00:09:26,310 --> 00:09:31,060 algoritmo, nuestro algoritmo libro examen, y más en general, la búsqueda de información. 304 00:09:31,060 --> 00:09:34,770 >> Así que para esto, dejarme ir por delante, y en la pantalla táctil por aquí, 305 00:09:34,770 --> 00:09:41,100 poner un navegador web que tiene exactamente estas siete puertas. 306 00:09:41,100 --> 00:09:46,670 Y si pudiéramos conseguir otro voluntarios para venir por aquí, 307 00:09:46,670 --> 00:09:48,480 He puesto estas mismas puertas aquí. 308 00:09:48,480 --> 00:09:49,170 Voluntario rápida. 309 00:09:49,170 --> 00:09:51,130 >> Este uno-- demos van a un más rápido y más rápido ahora. 310 00:09:51,130 --> 00:09:51,600 Baja. 311 00:09:51,600 --> 00:09:52,308 ¿Cómo te llamas? 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 Muy bien, Trevor, vamos hacia abajo. 315 00:09:55,770 --> 00:09:59,212 Así que Trevor se ha ofrecido aquí para hacer un problema similar, pero uno que es 316 00:09:59,212 --> 00:10:02,170 más estrecho en su alcance, y eso va que nos permita tratar de formalizar ahora 317 00:10:02,170 --> 00:10:03,970 el proceso para la clasificación de estos números. 318 00:10:03,970 --> 00:10:05,500 >> Así Trevor, encantado de conocerte. 319 00:10:05,500 --> 00:10:08,720 Así que aquí es una matriz, por lo que hablar, una lista de siete puertas. 320 00:10:08,720 --> 00:10:10,327 Vaya por delante y nos encontrará en el número 50. 321 00:10:10,327 --> 00:10:12,410 Y a continuación, después del hecho, díganos cómo lo encontraste. 322 00:10:12,410 --> 00:10:19,124 323 00:10:19,124 --> 00:10:20,040 En caso de ser-- bien. 324 00:10:20,040 --> 00:10:21,945 Sí, este es el que aquí? 325 00:10:21,945 --> 00:10:24,680 UH oh. 326 00:10:24,680 --> 00:10:25,560 OK. 327 00:10:25,560 --> 00:10:26,680 Hizo clic en esa. 328 00:10:26,680 --> 00:10:28,690 Bien. 329 00:10:28,690 --> 00:10:29,780 >> Y bueno. 330 00:10:29,780 --> 00:10:30,970 Ahora ha hecho clic en ese. 331 00:10:30,970 --> 00:10:34,060 Y te voy a dar el micrófono, de manera que usted lo tiene en un momento. 332 00:10:34,060 --> 00:10:37,000 Siga adelante y haga clic en el al lado que tiene la intención. 333 00:10:37,000 --> 00:10:39,812 Si bueno. 334 00:10:39,812 --> 00:10:41,020 TREVOR: ¿Puedo desmarca una puerta? 335 00:10:41,020 --> 00:10:42,620 DAVID J. MALAN: No, usted no puede desmarque. 336 00:10:42,620 --> 00:10:43,119 TREVOR: OK. 337 00:10:43,119 --> 00:10:43,974 Éste. 338 00:10:43,974 --> 00:10:45,640 DAVID J. MALAN: ¿Dónde quieres ir? 339 00:10:45,640 --> 00:10:46,410 ¿Cúal? 340 00:10:46,410 --> 00:10:47,230 >> TREVOR: Que uno. 341 00:10:47,230 --> 00:10:48,042 >> DAVID J. MALAN: No. 342 00:10:48,042 --> 00:10:48,450 >> TREVOR: OK. 343 00:10:48,450 --> 00:10:48,735 Éste. 344 00:10:48,735 --> 00:10:49,020 >> DAVID J. MALAN: Sí. 345 00:10:49,020 --> 00:10:49,700 Eso era bueno. 346 00:10:49,700 --> 00:10:50,380 Correcto. 347 00:10:50,380 --> 00:10:53,900 Entonces, ¿cuál era su algoritmo o procedimiento para hacer esto, Trevor? 348 00:10:53,900 --> 00:10:56,149 >> TREVOR: Me acaba de pasar por puertas hasta que encontraron un 50. 349 00:10:56,149 --> 00:10:56,940 DAVID J. MALAN: OK. 350 00:10:56,940 --> 00:10:58,150 Excelente algoritmo. 351 00:10:58,150 --> 00:10:59,540 Así que eso está bien. 352 00:10:59,540 --> 00:11:03,120 Porque, de hecho, si revelo lo que es detrás de estas otras dos puertas, lo que 353 00:11:03,120 --> 00:11:06,954 vamos a encontrar aquí es que sólo tenemos entrada aleatoria. 354 00:11:06,954 --> 00:11:08,870 Así que fue realmente como bueno como se puede conseguir. 355 00:11:08,870 --> 00:11:12,509 Y de hecho, tienes mejor que exhaustivamente buscando todo el conjunto, 356 00:11:12,509 --> 00:11:15,300 porque habría sido muy mala suerte si se hubiera golpeado el número 357 00:11:15,300 --> 00:11:16,604 50 en el último lado. 358 00:11:16,604 --> 00:11:18,520 Pero ¿y si en lugar te dio una suposición. 359 00:11:18,520 --> 00:11:20,630 Supongamos que en cierto modo me todos estas puertas de todo, 360 00:11:20,630 --> 00:11:23,500 quedando con la números ordenados en esta ocasión, 361 00:11:23,500 --> 00:11:29,730 pero esta vez es en realidad un diferente-- este tiempo, 362 00:11:29,730 --> 00:11:32,640 en realidad está ordenada para usted. 363 00:11:32,640 --> 00:11:35,380 Y ahora el peligro en la mano es para golpear el número 50. 364 00:11:35,380 --> 00:11:36,090 >> TREVOR: OK. 365 00:11:36,090 --> 00:11:37,670 >> DAVID J. MALAN: ¿Cuál es el algoritmo va a ser? 366 00:11:37,670 --> 00:11:39,628 >> TREVOR: Bueno, si es ordenados, es bien va 367 00:11:39,628 --> 00:11:42,710 a ser-- si mayor a mayor, descendente, va a ser el primero, 368 00:11:42,710 --> 00:11:44,751 o si es todo lo contrario, será la última. 369 00:11:44,751 --> 00:11:48,897 Así que voy a tocar en la puerta, y a continuación, sólo tocar la última puerta. 370 00:11:48,897 --> 00:11:49,980 DAVID J. MALAN: Excelente. 371 00:11:49,980 --> 00:11:50,270 Correcto. 372 00:11:50,270 --> 00:11:51,150 Así que encontramos el número 50. 373 00:11:51,150 --> 00:11:52,970 Así que tan pronto como usted sabía fueron ordenados, nos 374 00:11:52,970 --> 00:11:55,040 fueron capaces de aprovechar esta suposición. 375 00:11:55,040 --> 00:11:57,040 Así que son demasiado parecido el ejemplo guía telefónica. 376 00:11:57,040 --> 00:11:59,540 Tan pronto como usted tiene, incluso con un pequeño problema como este, 377 00:11:59,540 --> 00:12:02,380 sus entradas pre-ordenados, podemos en realidad encontrar el valor discutible 378 00:12:02,380 --> 00:12:03,130 mas eficientemente. 379 00:12:03,130 --> 00:12:05,800 >> Y yo no digo que si era ordenados pequeño a grande o grande a pequeño, 380 00:12:05,800 --> 00:12:08,080 y por lo que era muy razonable para comenzar en un extremo o el otro 381 00:12:08,080 --> 00:12:09,750 encontrar realmente ese valor objetivo. 382 00:12:09,750 --> 00:12:11,400 Así que gracias a Trevor también. 383 00:12:11,400 --> 00:12:13,260 Y voy a propose-- muy bien hecho. 384 00:12:13,260 --> 00:12:16,960 Tenemos un pequeño clip, en realidad, que es uno de nuestros momentos favoritos en CS50, 385 00:12:16,960 --> 00:12:19,700 por el que a veces estas demos no todo vaya según lo planeado. 386 00:12:19,700 --> 00:12:22,050 Y de hecho ahora mismo, detuvo la interfaz equivocada 387 00:12:22,050 --> 00:12:23,508 con la que usar la pantalla táctil. 388 00:12:23,508 --> 00:12:24,660 Así que fue mi culpa no. 389 00:12:24,660 --> 00:12:26,600 >> Así que esto hará para Clip del próximo año como 390 00:12:26,600 --> 00:12:28,570 de por qué estaba haciendo clic en mi propia pantalla. 391 00:12:28,570 --> 00:12:31,390 Pero echemos un vistazo rápido a lo que sucedió el año pasado 392 00:12:31,390 --> 00:12:34,770 con Jay, quien se acercó, y mucho como Trevor aquí, voluntariamente, 393 00:12:34,770 --> 00:12:39,380 y en este breve clip, verás cómo esta misma demostración no hizo bastante 394 00:12:39,380 --> 00:12:41,074 revelar las mismas lecciones aprendidas. 395 00:12:41,074 --> 00:12:41,740 [REPRODUCCIÓN DE VÍDEO] 396 00:12:41,740 --> 00:12:45,360 -Todos Los que quiero que hagas ahora es de encontrar para mí, y para nosotros, 397 00:12:45,360 --> 00:12:51,674 en realidad, el número 50 un paso a la vez. 398 00:12:51,674 --> 00:12:52,450 >> -El Número 50? 399 00:12:52,450 --> 00:12:53,190 >> -El Número 50. 400 00:12:53,190 --> 00:12:55,356 Y usted puede revelar lo que es detrás de cada una de estas puertas 401 00:12:55,356 --> 00:12:58,540 con sólo tocar con un dedo. 402 00:12:58,540 --> 00:13:00,910 Maldición. 403 00:13:00,910 --> 00:13:02,870 >> [Risas] 404 00:13:02,870 --> 00:13:03,806 >> [FIN DE REPRODUCCIÓN] 405 00:13:03,806 --> 00:13:05,430 DAVID J. MALAN: Así que fue muy bien. 406 00:13:05,430 --> 00:13:06,796 Esas fueron las puertas sin clasificar. 407 00:13:06,796 --> 00:13:08,670 Y Jay, por supuesto, encontrado con demasiada rapidez. 408 00:13:08,670 --> 00:13:12,910 Trevor hizo un trabajo mucho mejor en términos de un momento de aprendizaje, 409 00:13:12,910 --> 00:13:15,850 por así decirlo, este año en tomando más tiempo para encontrarlo. 410 00:13:15,850 --> 00:13:17,950 Por supuesto, entonces nos dimos Jay una segunda oportunidad, 411 00:13:17,950 --> 00:13:20,320 por el que nos lo solucionaron las puertas, tal como lo hicimos para Trevor, 412 00:13:20,320 --> 00:13:22,300 y Trevor hizo muy bien esta vez. 413 00:13:22,300 --> 00:13:26,124 Pero Jay hizo un medio tan rápido. 414 00:13:26,124 --> 00:13:26,790 [REPRODUCCIÓN DE VÍDEO] 415 00:13:26,790 --> 00:13:29,650 -El Objetivo ahora es también nosotros encontrar el número 50, 416 00:13:29,650 --> 00:13:33,030 pero hacerlo algorítmicamente, y decirnos cómo va en ello. 417 00:13:33,030 --> 00:13:33,660 >> -OK. 418 00:13:33,660 --> 00:13:35,604 >> -Y Si lo encuentra, se mantiene la película. 419 00:13:35,604 --> 00:13:37,228 Si no lo encuentra, le das la espalda. 420 00:13:37,228 --> 00:13:38,044 >> -Hombre. 421 00:13:38,044 --> 00:13:38,860 >> -¡Oh! 422 00:13:38,860 --> 00:13:40,800 >> - [Inaudible] en Aceptar. 423 00:13:40,800 --> 00:13:46,236 Así que voy a comprobar los extremos primero para determinar si 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 REPRODUCCIÓN] 427 00:13:55,729 --> 00:13:56,520 DAVID J. MALAN: OK. 428 00:13:56,520 --> 00:13:59,760 Así clasificación puertas claramente conduce a una mayor eficiencia. 429 00:13:59,760 --> 00:14:01,680 Y así, dos veces más rápido es lo que quise decir no. 430 00:14:01,680 --> 00:14:03,270 Y así Jay tuvo suerte en ambas ocasiones. 431 00:14:03,270 --> 00:14:06,685 Y también tuvo suerte en ese último año, pedí algunos discos Blu-ray 432 00:14:06,685 --> 00:14:07,560 para dar a conocer realmente. 433 00:14:07,560 --> 00:14:09,768 Lo siento de este año, no tuvo la misma, Trevor. 434 00:14:09,768 --> 00:14:11,540 Pero mejor aún era hace unos años. 435 00:14:11,540 --> 00:14:14,820 Y algunos de ustedes podrían saber esto compañero, Sean, que cuando estaba en el CS50, 436 00:14:14,820 --> 00:14:17,780 fue impugnada con la exacta mismo problema, aunque en SD, 437 00:14:17,780 --> 00:14:19,360 como pronto verás, de vuelta en el día. 438 00:14:19,360 --> 00:14:22,622 Y usted encontrará que no sólo que tome un poco más de Jay, 439 00:14:22,622 --> 00:14:25,580 un poco más de Trevor, fue En realidad esta maravillosa oportunidad 440 00:14:25,580 --> 00:14:29,820 a participar casi todos en el gente a la Price is Right, fomentando 441 00:14:29,820 --> 00:14:31,889 él para encontrar el número que estábamos buscando. 442 00:14:31,889 --> 00:14:32,930 Vamos. echar un vistazo rápido. 443 00:14:32,930 --> 00:14:33,320 >> [REPRODUCCIÓN DE VÍDEO] 444 00:14:33,320 --> 00:14:33,820 >> -OK. 445 00:14:33,820 --> 00:14:36,680 Así que su tarea aquí, Sean, es la siguiente. 446 00:14:36,680 --> 00:14:40,860 He escondido detrás de éstos puertas el número siete. 447 00:14:40,860 --> 00:14:45,120 Pero escondido en alguna de estas puertas así son otros números negativos. 448 00:14:45,120 --> 00:14:47,500 Y su objetivo es pensar de esta fila superior de los números 449 00:14:47,500 --> 00:14:50,390 como se acaba de una matriz, o simplemente secuencia de las hojas de papel 450 00:14:50,390 --> 00:14:51,510 con números detrás de ellos. 451 00:14:51,510 --> 00:14:55,540 Y su objetivo es, sólo con la parte superior variedad aquí, me encontrar el número siete. 452 00:14:55,540 --> 00:14:58,570 Y estamos a continuación, vamos a criticar cómo usted va sobre hacerlo. 453 00:14:58,570 --> 00:14:59,070 -Correcto. 454 00:14:59,070 --> 00:15:00,850 Nos -Buscar el número siete, por favor. 455 00:15:00,850 --> 00:15:10,500 456 00:15:10,500 --> 00:15:11,000 No. 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 >> No es una pregunta con trampa. 462 00:15:25,910 --> 00:15:29,410 463 00:15:29,410 --> 00:15:29,910 Uno. 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 En este punto, su puntuación no es muy bueno, por lo que así podría seguir adelante. 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 >> Continuar. 473 00:15:47,774 --> 00:15:50,690 Francamente, no puedo evitar preguntarme lo que estás siquiera pensar, así que-- 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ólo la fila superior, por lo que usted tiene de tres izquierda. 477 00:15:55,020 --> 00:15:56,200 Así que encontrar siete. 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 Siete. 484 00:16:26,946 --> 00:16:28,780 >> [Aplausos] 485 00:16:28,780 --> 00:16:29,426 >> Correcto. 486 00:16:29,426 --> 00:16:30,360 >> [FIN DE REPRODUCCIÓN] 487 00:16:30,360 --> 00:16:31,840 >> DAVID J. MALAN: Así que pudimos ver a estos durante todo el día. 488 00:16:31,840 --> 00:16:34,090 Y, por supuesto, algunos de demostraciones de este año tal vez 489 00:16:34,090 --> 00:16:36,330 ahora terminar en el próximo vídeo del año también. 490 00:16:36,330 --> 00:16:39,040 Así que ahora vamos a realidad centrarse en los algoritmos 491 00:16:39,040 --> 00:16:42,140 aquí, y ver si no podemos Ahora empezar a formalizar 492 00:16:42,140 --> 00:16:46,650 cómo podemos ir sobre cómo obtener nuestros datos en este estado que está ordenada, 493 00:16:46,650 --> 00:16:50,054 por lo que en última instancia, podemos realidad buscarla en el diccionario de manera más eficiente. 494 00:16:50,054 --> 00:16:52,470 Y a pesar de que vamos utilizar conjuntos de datos bastante pequeños, 495 00:16:52,470 --> 00:16:54,511 como el que ocho números tenemos aquí en el tablero, 496 00:16:54,511 --> 00:16:58,230 en última instancia, podrían aplicar estas mismas ideas 1.000 entradas, un millón de entradas, 497 00:16:58,230 --> 00:17:02,100 4 mil millones de entradas, ya que los algoritmos van a ser fundamentalmente los mismos. 498 00:17:02,100 --> 00:17:05,359 >> Y lo que esta es nuestra última oportunidad para que los voluntarios hoy en día, 499 00:17:05,359 --> 00:17:09,790 pero quizás el más complicado, para lo cual necesitamos ocho voluntarios 500 00:17:09,790 --> 00:17:12,960 para llegar y nos caminar por el proceso de clasificar lo que pronto 501 00:17:12,960 --> 00:17:15,212 estar en estos atriles aquí. 502 00:17:15,212 --> 00:17:16,170 Permítanme comenzar de nuevo aquí. 503 00:17:16,170 --> 00:17:19,692 >> Así que uno en el verde turquoise-- es? 504 00:17:19,692 --> 00:17:21,130 ¿Estás cometiendo? 505 00:17:21,130 --> 00:17:21,630 Dos. 506 00:17:21,630 --> 00:17:23,069 Baja. 507 00:17:23,069 --> 00:17:23,569 OK. 508 00:17:23,569 --> 00:17:24,420 Tres. 509 00:17:24,420 --> 00:17:25,400 Cuatro. 510 00:17:25,400 --> 00:17:27,247 Deje mí-- OK, cinco. 511 00:17:27,247 --> 00:17:28,830 Usted está siendo nominado por su amigo. 512 00:17:28,830 --> 00:17:31,340 Seis, siete y ocho. 513 00:17:31,340 --> 00:17:32,130 Vamos arriba. 514 00:17:32,130 --> 00:17:32,630 Correcto. 515 00:17:32,630 --> 00:17:33,190 Muchas gracias. 516 00:17:33,190 --> 00:17:33,689 Vamos arriba. 517 00:17:33,689 --> 00:17:34,790 Vamos arriba. 518 00:17:34,790 --> 00:17:35,330 >> Correcto. 519 00:17:35,330 --> 00:17:38,890 Así que lo que tenemos aquí-- y esto es uno de los más difíciles, 520 00:17:38,890 --> 00:17:42,390 ya que esto requerirá que el humor mí por un poco de tiempo. 521 00:17:42,390 --> 00:17:43,442 Usted será el número uno. 522 00:17:43,442 --> 00:17:44,150 ¿Cómo te llamas? 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 ¿Cómo te llamas? 527 00:17:46,800 --> 00:17:47,140 >> JOSEPH: Joseph. 528 00:17:47,140 --> 00:17:49,190 >> DAVID J. MALAN: José, usted es el número dos. 529 00:17:49,190 --> 00:17:52,260 >> SERENA: Serena, número tres. 530 00:17:52,260 --> 00:17:53,722 Stefan, el número cuatro. 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 [Inaudible] 534 00:17:58,452 --> 00:17:59,618 DAVID J. MALAN: [inaudible]. 535 00:17:59,618 --> 00:18:00,391 David, el 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 siete. 538 00:18:02,160 --> 00:18:02,850 ¿Y? 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 ocho. 541 00:18:04,470 --> 00:18:04,970 Correcto. 542 00:18:04,970 --> 00:18:06,510 Si could-- gritos. 543 00:18:06,510 --> 00:18:08,820 Si todos ustedes, como su primer desafío, hay 544 00:18:08,820 --> 00:18:10,820 son ocho atriles aquí frente a la audiencia. 545 00:18:10,820 --> 00:18:14,200 Si pudieras poner sus números en estos soportes de música de tal manera 546 00:18:14,200 --> 00:18:16,560 que se alinean con el mismos números en el tablero. 547 00:18:16,560 --> 00:18:19,560 Así que ustedes ven como que por poner los números en esta música 548 00:18:19,560 --> 00:18:21,960 se encuentra aquí. 549 00:18:21,960 --> 00:18:25,980 Excelente hasta el momento. 550 00:18:25,980 --> 00:18:26,600 >> Excelente. 551 00:18:26,600 --> 00:18:26,890 OK. 552 00:18:26,890 --> 00:18:29,556 Así que ahora, vamos a pedir a la pregunta de varias maneras diferentes. 553 00:18:29,556 --> 00:18:31,610 ¿Cómo podemos ir sobre la clasificación esta gente aquí? 554 00:18:31,610 --> 00:18:34,500 Porque teníamos un par de enfoques anterior, por el cual fueron 555 00:18:34,500 --> 00:18:36,360 tipo de toma de dos cubos diferentes. 556 00:18:36,360 --> 00:18:38,842 Y entonces estábamos general recomponer las cosas juntos. 557 00:18:38,842 --> 00:18:41,050 Tan pronto como vimos dos números que pertenecían juntos, 558 00:18:41,050 --> 00:18:41,975 los ponemos juntos. 559 00:18:41,975 --> 00:18:43,350 Dos letras que van de la mano. 560 00:18:43,350 --> 00:18:45,058 >> Pero vamos a ver si nos no puede formalizar este, 561 00:18:45,058 --> 00:18:48,044 para que en última instancia, tenemos algunos pseudo-código se quiere, 562 00:18:48,044 --> 00:18:49,710 con el que puede resolver estos problemas. 563 00:18:49,710 --> 00:18:51,870 Así que ahora, estoy mirando estos números aquí. 564 00:18:51,870 --> 00:18:55,030 Y veo un montón de errores. 565 00:18:55,030 --> 00:18:57,750 En última instancia, quiero uno en el a la izquierda y ocho a la derecha. 566 00:18:57,750 --> 00:19:00,650 >> Y por lo que estoy viendo estos dos, cuatro y dos. 567 00:19:00,650 --> 00:19:02,930 ¿Y cuál es el problema, es obvio? 568 00:19:02,930 --> 00:19:04,261 Sí. 569 00:19:04,261 --> 00:19:04,760 So. 570 00:19:04,760 --> 00:19:07,160 Dos obviamente viene antes cuatro, así que usted sabe lo que? 571 00:19:07,160 --> 00:19:10,210 Permítanme primero tomo un enfoque codiciosos, si se quiere, tanto problema como 572 00:19:10,210 --> 00:19:13,790 establecer uno-- si recuerdan desde el Edición Estándar de de problemas Uno, 573 00:19:13,790 --> 00:19:16,820 donde sólo a nivel local a resolver el problema eso es justo aquí en frente de mí 574 00:19:16,820 --> 00:19:17,690 y ver a dónde me lleva. 575 00:19:17,690 --> 00:19:17,870 >> OK. 576 00:19:17,870 --> 00:19:20,161 Así que dos y cuatro, déjame ir adelante y sólo te intercambiar dos. 577 00:19:20,161 --> 00:19:22,400 Si usted puede mover físicamente ustedes mismos y de su papel, 578 00:19:22,400 --> 00:19:25,040 Parece que he conseguido el listar en mejor estado. 579 00:19:25,040 --> 00:19:26,330 >> Ahora, son buenos. 580 00:19:26,330 --> 00:19:28,480 Voy a seguir adelante, cuatro y seis, se ve bien. 581 00:19:28,480 --> 00:19:29,110 No es un problema. 582 00:19:29,110 --> 00:19:30,440 Seis y ocho, en Aceptar. 583 00:19:30,440 --> 00:19:31,860 Ocho y uno, otro problema. 584 00:19:31,860 --> 00:19:34,750 Porque lo que es cierto eso de las ocho y uno? 585 00:19:34,750 --> 00:19:36,990 Uno viene antes de las ocho, y así ¿qué debemos hacer? 586 00:19:36,990 --> 00:19:38,090 Vamos intercambie estos dos. 587 00:19:38,090 --> 00:19:39,316 Uno y ocho. 588 00:19:39,316 --> 00:19:40,690 Y ahora, voy a seguir adelante. 589 00:19:40,690 --> 00:19:42,030 Yo voy a seguir mirando hacia adelante. 590 00:19:42,030 --> 00:19:42,840 Y vamos a ver qué pasa. 591 00:19:42,840 --> 00:19:44,680 Ocho y tres, de Por supuesto, fuera de orden. 592 00:19:44,680 --> 00:19:45,815 De intercambio Let. 593 00:19:45,815 --> 00:19:46,940 Ocho y siete, por supuesto. 594 00:19:46,940 --> 00:19:47,481 Fuera de servicio. 595 00:19:47,481 --> 00:19:48,280 De intercambio Let. 596 00:19:48,280 --> 00:19:49,940 Ocho y cinco, por supuesto, vamos a swap. 597 00:19:49,940 --> 00:19:50,560 Correcto. 598 00:19:50,560 --> 00:19:51,880 Lista está ordenada. 599 00:19:51,880 --> 00:19:53,060 sí? 600 00:19:53,060 --> 00:19:54,280 >> OK, obviamente no. 601 00:19:54,280 --> 00:19:55,860 Pero es un poco mejor, ¿no? 602 00:19:55,860 --> 00:19:57,270 Debido aviso de lo que pasó. 603 00:19:57,270 --> 00:20:01,749 Cada vez que realiza un intercambio, una más pequeña número de tipo de percolado de esa manera, 604 00:20:01,749 --> 00:20:03,790 y un número más grande percolado de esta manera, o vamos a 605 00:20:03,790 --> 00:20:06,880 comenzar diciendo burbujear a la burbujeó izquierda o hacia la derecha. 606 00:20:06,880 --> 00:20:10,080 >> Ahora, no es suficiente, porque en el mejor de un número podría 607 00:20:10,080 --> 00:20:11,990 han movido un solo lugar hacia adelante, o en el peor, 608 00:20:11,990 --> 00:20:13,880 un número podría tener movido un punto más. 609 00:20:13,880 --> 00:20:16,369 Así que ya sabes lo que, este tipo de funcionado bastante bien hasta ahora. 610 00:20:16,369 --> 00:20:17,410 Déjame intentarlo de nuevo. 611 00:20:17,410 --> 00:20:18,880 Dos y cuatro, que están bien. 612 00:20:18,880 --> 00:20:20,180 Cuatro y seis, que están bien. 613 00:20:20,180 --> 00:20:21,790 Seis y uno, fuera de orden. 614 00:20:21,790 --> 00:20:23,007 Así que vamos a ustedes dos swap. 615 00:20:23,007 --> 00:20:25,840 Y ahora, observe el problema de comenzando a conseguir un poco mejor de nuevo. 616 00:20:25,840 --> 00:20:27,006 Seis y tres, fuera de orden. 617 00:20:27,006 --> 00:20:28,100 Vamos a ustedes dos swap. 618 00:20:28,100 --> 00:20:29,730 Seis y siete, ya está bueno. 619 00:20:29,730 --> 00:20:32,230 Siete y cinco, por supuesto, fuera de orden. 620 00:20:32,230 --> 00:20:33,920 Siete y ocho, en orden. 621 00:20:33,920 --> 00:20:36,470 Y ahora, puede ser que tenga que hacer esto unas cuantas veces más. 622 00:20:36,470 --> 00:20:39,830 Y de hecho, pensar por sí mismos quizás cuántas veces máximo 623 00:20:39,830 --> 00:20:41,330 podría yo tener que caminar de ida y vuelta? 624 00:20:41,330 --> 00:20:42,390 >> Volveremos a eso. 625 00:20:42,390 --> 00:20:43,700 Así que dos y cuatro siguen en Aceptar. 626 00:20:43,700 --> 00:20:44,940 Cuatro y uno, pues no. 627 00:20:44,940 --> 00:20:45,747 Así, intercambio de dejar. 628 00:20:45,747 --> 00:20:47,830 Y de nuevo, observe visualmente uno es tipo de burbujeo 629 00:20:47,830 --> 00:20:49,163 a la izquierda, donde debe estar. 630 00:20:49,163 --> 00:20:50,010 Cuatro y tres de intercambio. 631 00:20:50,010 --> 00:20:51,330 Cuatro y seis. 632 00:20:51,330 --> 00:20:53,100 Seis y cinco años de intercambio. 633 00:20:53,100 --> 00:20:53,959 Seis y siete. 634 00:20:53,959 --> 00:20:55,000 Siete y ocho son buenos. 635 00:20:55,000 --> 00:20:55,500 >> Bien. 636 00:20:55,500 --> 00:20:58,460 Estamos recibiendo aún mejor. 637 00:20:58,460 --> 00:20:59,130 Así que vamos a ver. 638 00:20:59,130 --> 00:21:00,940 Ahora, tenemos dos y uno. 639 00:21:00,940 --> 00:21:02,520 Por supuesto, cambiar. 640 00:21:02,520 --> 00:21:07,520 Dos y tres, tres y cuatro, cuatro y cinco, seis y siete, siete y ocho. 641 00:21:07,520 --> 00:21:08,020 Bien. 642 00:21:08,020 --> 00:21:08,730 ¿Y sabes qué? 643 00:21:08,730 --> 00:21:11,190 Porque hice un cambio allí, déjame hacer un cheque cordura. 644 00:21:11,190 --> 00:21:13,023 Déjame ir todo el camino de nuevo al principio. 645 00:21:13,023 --> 00:21:13,680 OK. 646 00:21:13,680 --> 00:21:14,750 Uno, dos-- yup, ¿ves? 647 00:21:14,750 --> 00:21:15,870 Algo andaba mal. 648 00:21:15,870 --> 00:21:18,420 Tres, cuatro, cinco, seis, siete, ocho. 649 00:21:18,420 --> 00:21:21,920 Y en este último paso, son Se siente cómodo con mi ahora 650 00:21:21,920 --> 00:21:23,830 alegando que se ordena? 651 00:21:23,830 --> 00:21:24,330 OK. 652 00:21:24,330 --> 00:21:25,880 Visualmente, eso es absolutamente cierto. 653 00:21:25,880 --> 00:21:28,410 Pero funcionalmente, lo hizo también acaba de suceder 654 00:21:28,410 --> 00:21:31,870 en ese último pase que le permite para confirmar que esta lista es de hecho 655 00:21:31,870 --> 00:21:32,660 ordenados? 656 00:21:32,660 --> 00:21:34,477 >> ¿Qué hice o no hacer esto último pase? 657 00:21:34,477 --> 00:21:35,810 AUDIENCIA: No hubo cambios. 658 00:21:35,810 --> 00:21:36,120 DAVID J. MALAN: Lo siento? 659 00:21:36,120 --> 00:21:37,070 AUDIENCIA: No hay cambios. 660 00:21:37,070 --> 00:21:38,653 DAVID J. MALAN: No hubo cambios. 661 00:21:38,653 --> 00:21:41,947 Así que sería estúpido de mi parte hacer eso mismo algoritmo de nuevo 662 00:21:41,947 --> 00:21:43,780 si yo no hice ninguna cambia la primera vez. 663 00:21:43,780 --> 00:21:45,160 Y el estado no ha cambiado. 664 00:21:45,160 --> 00:21:47,576 Ciertamente, yo no voy a hacer Cualquier cambio del segundo tiempo. 665 00:21:47,576 --> 00:21:49,820 Y así, es seguro ahora decir, la lista está ordenada. 666 00:21:49,820 --> 00:21:52,069 >> Y, de hecho, esto es ahora algo que vamos a general 667 00:21:52,069 --> 00:21:56,900 llamada de ordenamiento de burbuja, en el que por parejas, corregir errores de nuevo, 668 00:21:56,900 --> 00:22:00,210 y otra vez, y otra vez, y usted seguir adelante hacia atrás y adelante, 669 00:22:00,210 --> 00:22:03,370 y de ida y vuelta, hasta que no hacer este tipo de swaps, y en ese momento 670 00:22:03,370 --> 00:22:07,089 usted puede estar seguro, sí, terminado de fijar todos los errores. 671 00:22:07,089 --> 00:22:08,630 Vamos a restablecer y jugar diferente. 672 00:22:08,630 --> 00:22:11,590 Si ustedes podrían volver a el orden en que fueron hace un momento, 673 00:22:11,590 --> 00:22:13,780 que se veía así. 674 00:22:13,780 --> 00:22:17,640 Ahora, vamos a echar un enfoque un poco más como el libro del examen, 675 00:22:17,640 --> 00:22:21,122 por el que estábamos constantemente la selección de la letra del alfabeto 676 00:22:21,122 --> 00:22:22,830 que tipo de queríamos para hacer frente a la próxima. 677 00:22:22,830 --> 00:22:26,420 Tal vez fue una gran carta, como A, o una letra Z. baja 678 00:22:26,420 --> 00:22:28,170 >> Así que todo el mundo está de vuelta en este orden. 679 00:22:28,170 --> 00:22:29,800 Y ahora déjame hacer esto. 680 00:22:29,800 --> 00:22:34,880 Veamos sé que tengo ocho números aquí. 681 00:22:34,880 --> 00:22:37,410 Voy a seguir adelante y simplemente deliberadamente seleccione 682 00:22:37,410 --> 00:22:38,520 los elementos más pequeños. 683 00:22:38,520 --> 00:22:38,760 ¿Correcto? 684 00:22:38,760 --> 00:22:39,801 Esto parece intuitiva también. 685 00:22:39,801 --> 00:22:42,560 ¿Por qué no me parece el más pequeño elemento, lo puso donde pertenece, 686 00:22:42,560 --> 00:22:45,280 a continuación, obtener el siguiente elemento más pequeño, puesto donde pertenece, y sólo tiene que repetir. 687 00:22:45,280 --> 00:22:46,820 >> Debido a que de manera intuitiva, que debería funcionar también. 688 00:22:46,820 --> 00:22:48,441 Así que cuatro, que es un número muy pequeño. 689 00:22:48,441 --> 00:22:49,940 Voy a recordar de dónde es. 690 00:22:49,940 --> 00:22:50,523 Espera un minuto. 691 00:22:50,523 --> 00:22:51,577 Dos es más pequeño. 692 00:22:51,577 --> 00:22:53,910 Permítanme ahora recuerdo que dos es, y olvidarse de cuatro. 693 00:22:53,910 --> 00:22:55,050 Nos ocuparemos de eso más tarde. 694 00:22:55,050 --> 00:22:56,460 Seis, no me interesa. 695 00:22:56,460 --> 00:22:57,810 Ocho, no estoy interesado. 696 00:22:57,810 --> 00:22:59,780 Uno de ellos es mi nuevo número pequeño. 697 00:22:59,780 --> 00:23:01,470 Así que voy a recordar dónde uno es. 698 00:23:01,470 --> 00:23:02,534 Tres, no le interesa. 699 00:23:02,534 --> 00:23:03,450 Siete, no le interesa. 700 00:23:03,450 --> 00:23:04,530 Cinco, no le interesa. 701 00:23:04,530 --> 00:23:07,390 >> Así que sin caerse la etapa de este año, 702 00:23:07,390 --> 00:23:09,890 Voy a agarrar número uno-- y lo que era tu nombre? 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 Y si usted puede unirse a mí en el principio de la lista, 706 00:23:13,540 --> 00:23:14,870 vamos te desanime a donde perteneces. 707 00:23:14,870 --> 00:23:16,080 Unfortunately-- ¿cómo te llamas? 708 00:23:16,080 --> 00:23:16,650 >> STEFAN: Stefan. 709 00:23:16,650 --> 00:23:18,191 >> DAVID J. MALAN: Stefan se encuentra en el camino. 710 00:23:18,191 --> 00:23:23,490 Así que antes de Stefan resuelve este problema, ¿qué debemos hacer? 711 00:23:23,490 --> 00:23:25,412 ¿Qué hacemos con Stefan? 712 00:23:25,412 --> 00:23:27,269 >> AUDIENCIA: [inaudible]. 713 00:23:27,269 --> 00:23:28,060 DAVID J. MALAN: OK. 714 00:23:28,060 --> 00:23:28,850 Así que podríamos hacer eso. 715 00:23:28,850 --> 00:23:31,730 Podríamos especie de tomar Stefan y su cuatro, y sólo hay que poner en una variable 716 00:23:31,730 --> 00:23:33,530 y aferrarse a ella para una cierta cantidad de tiempo, 717 00:23:33,530 --> 00:23:35,220 haciendo así espacio para el número uno. 718 00:23:35,220 --> 00:23:36,280 Y eso no es malo. 719 00:23:36,280 --> 00:23:39,270 Que podría sugerir, por qué no hacer sólo hay que poner Stefan aquí? 720 00:23:39,270 --> 00:23:41,610 ¿Por qué podría esto violaría un solo de las ideas que empezamos 721 00:23:41,610 --> 00:23:44,830 hablando de la última vez, la semana pasada? 722 00:23:44,830 --> 00:23:45,330 ¿Sí? 723 00:23:45,330 --> 00:23:45,740 >> AUDIENCIA: [inaudible]. 724 00:23:45,740 --> 00:23:46,860 >> DAVID J. MALAN: No hay índice para ello. 725 00:23:46,860 --> 00:23:49,735 Si usted piensa en esto, de hecho, como un matriz, esto es como una cosa negativa, 726 00:23:49,735 --> 00:23:52,900 así que no hay memoria realidad aquí si esta es de hecho una matriz, 727 00:23:52,900 --> 00:23:55,090 como hemos declarado la semana pasada en la conferencia. 728 00:23:55,090 --> 00:23:56,250 Así que no debemos hacer esto. 729 00:23:56,250 --> 00:23:57,340 Podríamos almacenarlo en una variable. 730 00:23:57,340 --> 00:23:57,820 >> O ¿sabes qué? 731 00:23:57,820 --> 00:23:59,153 Oí que alguien sugiera que. 732 00:23:59,153 --> 00:24:01,020 ¿Qué otra cosa podíamos hacer con Stefan? 733 00:24:01,020 --> 00:24:03,770 ¿Por qué no acaba de desalojarlo y lo puso sobre donde estaba el número uno. 734 00:24:03,770 --> 00:24:05,170 Así que si quieres ir allí. 735 00:24:05,170 --> 00:24:07,300 Y de hecho, esta es una bastante buena solución. 736 00:24:07,300 --> 00:24:10,480 Ahora, por un lado, no tengo clase de hecho el problema peor. 737 00:24:10,480 --> 00:24:13,650 Cuatro es ahora más lejos desde donde debe estar. 738 00:24:13,650 --> 00:24:14,900 Debe ser hacia este medio. 739 00:24:14,900 --> 00:24:16,100 >> ¿Pero sabes que? 740 00:24:16,100 --> 00:24:17,630 Eso podría haber sido mala suerte. 741 00:24:17,630 --> 00:24:18,822 Tal vez el número ocho estaba aquí. 742 00:24:18,822 --> 00:24:20,530 Y por eso, tal vez lo haría han tenido suerte, 743 00:24:20,530 --> 00:24:22,460 y empujado de ocho más cerca del final. 744 00:24:22,460 --> 00:24:24,710 Así que al final del día, En cierto modo todos promedia. 745 00:24:24,710 --> 00:24:26,085 No necesitamos que se preocupan por cuatro. 746 00:24:26,085 --> 00:24:29,400 Todo lo que me importa en este momento es seleccionar el elemento más pequeño. 747 00:24:29,400 --> 00:24:32,030 >> Y ahora, ¿qué voy a hacer es olvidarse de número uno 748 00:24:32,030 --> 00:24:35,160 de forma permanente, porque sé que el lista detrás de mí ahora ordenadas. 749 00:24:35,160 --> 00:24:36,720 Así que mi lista era previamente tamaño ocho. 750 00:24:36,720 --> 00:24:37,720 Ahora, es del tamaño de siete. 751 00:24:37,720 --> 00:24:40,340 Así que mi problema es conseguir más pequeño, aunque linealmente. 752 00:24:40,340 --> 00:24:43,022 Así que ahora, voy a seleccionar el actual elemento más pequeño, dos. 753 00:24:43,022 --> 00:24:46,520 Seis, ocho, cuatro, tres, siete, cinco. 754 00:24:46,520 --> 00:24:47,770 Ese fue el elemento más pequeño. 755 00:24:47,770 --> 00:24:49,416 Entonces, ¿qué voy a hacer con-- ¿cuál era su nombre? 756 00:24:49,416 --> 00:24:49,760 >> JOSEPH: Joseph. 757 00:24:49,760 --> 00:24:50,085 >> DAVID J. MALAN: José? 758 00:24:50,085 --> 00:24:52,000 Vamos a dejar a José en su lugar. 759 00:24:52,000 --> 00:24:54,842 Ahora, voy a fingir que estos chicos son-- así, 760 00:24:54,842 --> 00:24:56,550 Sé que estos dos ya están ordenados. 761 00:24:56,550 --> 00:24:58,424 Ahora vamos a centrarnos en la resto de la lista. 762 00:24:58,424 --> 00:25:00,080 Seis es la corriente más pequeña. 763 00:25:00,080 --> 00:25:01,190 Ocho es más grande. 764 00:25:01,190 --> 00:25:02,970 Cuatro es ahora la corriente más pequeña. 765 00:25:02,970 --> 00:25:04,762 Tres es ahora la corriente más pequeña. 766 00:25:04,762 --> 00:25:07,720 Y ahora, voy a seleccionar tres, que es-- ¿cuál es tu nombre? 767 00:25:07,720 --> 00:25:08,190 SERENA: Serena. 768 00:25:08,190 --> 00:25:10,620 DAVID J. MALAN: Serena, si pudieras apoderarse de su número y de intercambio con-- 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 Vamos hacia atrás, y estamos va a cambiar esos dos. 772 00:25:15,220 --> 00:25:17,360 Y ahora, vamos a poner esto en piloto automático. 773 00:25:17,360 --> 00:25:21,589 Voy a ir y dejar a ustedes para seleccionar los siguientes elementos más pequeños. 774 00:25:21,589 --> 00:25:22,380 Dun, dun, dun, dun. 775 00:25:22,380 --> 00:25:24,560 Número cuatro, ¿qué debe hacer? 776 00:25:24,560 --> 00:25:26,261 Excelente. 777 00:25:26,261 --> 00:25:27,760 Ahora, yo voy a hacer otro pase. 778 00:25:27,760 --> 00:25:28,590 Dun, dun, dun, dun. 779 00:25:28,590 --> 00:25:31,465 Veo cinco es el inmediatamente inferior. 780 00:25:31,465 --> 00:25:32,840 Ahora, voy dar otro paso. 781 00:25:32,840 --> 00:25:33,631 Dun, dun, dun, dun. 782 00:25:33,631 --> 00:25:34,880 Seis es el más pequeño. 783 00:25:34,880 --> 00:25:35,520 Bien. 784 00:25:35,520 --> 00:25:36,585 Siete es el más pequeño. 785 00:25:36,585 --> 00:25:37,085 Ningún cambio. 786 00:25:37,085 --> 00:25:38,630 Ocho es el más pequeño. 787 00:25:38,630 --> 00:25:39,170 Hecho. 788 00:25:39,170 --> 00:25:43,900 >> Así que lo que acabamos de hacer de forma iterativa seleccionar un elemento después de la otra 789 00:25:43,900 --> 00:25:47,230 es poner en práctica algo que estamos va a formalizar como ordenación por selección. 790 00:25:47,230 --> 00:25:49,120 Y es tal vez incluso más simple de explicar, 791 00:25:49,120 --> 00:25:51,310 en que, literalmente, todo lo quiero hacer es mantener 792 00:25:51,310 --> 00:25:54,700 que van y vienen a través de la lista la selección, el siguiente elemento más pequeño, 793 00:25:54,700 --> 00:25:55,720 hasta que haya terminado. 794 00:25:55,720 --> 00:25:58,650 >> Por lo que es aún más simple, tal vez intuitivamente, que el pasado. 795 00:25:58,650 --> 00:26:00,020 Probemos última. 796 00:26:00,020 --> 00:26:03,060 Si ustedes podrían restablecer mismos en las siguientes posiciones 797 00:26:03,060 --> 00:26:08,600 por última vez, vamos a ver si no podemos ahora formalizar otro enfoque. 798 00:26:08,600 --> 00:26:12,857 De hecho, lo haría alguien por ahí gustaría proponer 799 00:26:12,857 --> 00:26:14,440 ¿de qué otra podríamos ir haciendo esto? 800 00:26:14,440 --> 00:26:17,439 Sin lanzando palabras de moda o tipo de las respuestas que ya se conocen, 801 00:26:17,439 --> 00:26:19,689 simplemente intuitivamente, ¿qué podíamos hacer? 802 00:26:19,689 --> 00:26:21,635 >> AUDIENCIA: [inaudible]. 803 00:26:21,635 --> 00:26:22,510 DAVID J. MALAN: Sí. 804 00:26:22,510 --> 00:26:24,620 Así que hay algo de gran intuición allí. 805 00:26:24,620 --> 00:26:28,020 Las buenas cosas parecen suceder hasta el momento en ciencias de la computación cuando dividimos 806 00:26:28,020 --> 00:26:30,832 y conquistar el problema de dividir por la mitad y mitad y mitad. 807 00:26:30,832 --> 00:26:32,540 Y así, de hecho, nos podría empezar a hacer eso. 808 00:26:32,540 --> 00:26:35,754 Y de hecho, que va a ser, vamos a ver, una de nuestras mejores soluciones todavía. 809 00:26:35,754 --> 00:26:37,420 Pero volvamos a la que en poco tiempo. 810 00:26:37,420 --> 00:26:40,500 De hecho, vamos a hacer que un poco más tarde esta semana. 811 00:26:40,500 --> 00:26:42,180 ¿Qué más podríamos hacer para solucionar esto? 812 00:26:42,180 --> 00:26:44,647 Así que aquí todo el mundo está en orden aparentemente aleatorio. 813 00:26:44,647 --> 00:26:45,230 ¿Tu sabes que? 814 00:26:45,230 --> 00:26:48,320 En lugar de ir y venir, ida y vuelta, de ida y vuelta 815 00:26:48,320 --> 00:26:50,624 cada vez, esto se siente como Estoy haciendo un montón de pie. 816 00:26:50,624 --> 00:26:52,790 ¿Por qué no acaba de empezar a el principio de la lista, 817 00:26:52,790 --> 00:26:54,960 y sólo hay que poner de cuatro que le corresponde? 818 00:26:54,960 --> 00:26:59,680 Así que permítanme asumo por el momento que mi lista es solamente este primer elemento. 819 00:26:59,680 --> 00:27:04,937 Es de cuatro ordenados en este momento en el tiempo, si todo lo que me importa es todo aquí? 820 00:27:04,937 --> 00:27:06,520 Esta es una especie de trivialmente cierto, ¿no? 821 00:27:06,520 --> 00:27:10,000 Al igual que la lista que contiene un número, y que el número cuatro es, obviamente, ordenadas. 822 00:27:10,000 --> 00:27:13,070 >> Así que permítanme estipulo que esta lista está ordenada. 823 00:27:13,070 --> 00:27:15,090 Pero ahora tengo el resto de esta lista. 824 00:27:15,090 --> 00:27:17,240 Así que ahora, me encuentro con dos. 825 00:27:17,240 --> 00:27:21,690 ¿De dónde viene de dos, obviamente, pertenecer con respecto a cuatro? 826 00:27:21,690 --> 00:27:22,580 Antes de cuatro. 827 00:27:22,580 --> 00:27:23,862 Entonces, ¿qué puedo hacer aquí? 828 00:27:23,862 --> 00:27:24,820 ¿Cuál es tu nombre? Otra vez? 829 00:27:24,820 --> 00:27:25,090 >> JOSEPH: Joseph. 830 00:27:25,090 --> 00:27:26,030 >> DAVID J. MALAN: José, si se pudiera dar un paso atrás 831 00:27:26,030 --> 00:27:27,790 por un momento con su número. 832 00:27:27,790 --> 00:27:31,130 Y ahora lo que debe Stefan hacer aquí? 833 00:27:31,130 --> 00:27:33,720 Vamos a cambiar de puesto Stefan aquí. 834 00:27:33,720 --> 00:27:35,520 Y ahora, vamos a Joseph entrar aquí. 835 00:27:35,520 --> 00:27:39,660 Y ahora, déjame pretendo que todo lo que aquí se ordena. 836 00:27:39,660 --> 00:27:42,474 Por lo tanto, resultado similar, pero una enfoque fundamentalmente diferente. 837 00:27:42,474 --> 00:27:44,140 Ni siquiera he mirado lo que hay ahí abajo. 838 00:27:44,140 --> 00:27:46,310 Sigo teniendo los elementos como se les entregaron a mí, 839 00:27:46,310 --> 00:27:47,240 y tratar con ellos. 840 00:27:47,240 --> 00:27:48,330 >> Así que ahora, veo el número seis. 841 00:27:48,330 --> 00:27:51,110 ¿A dónde pertenece número seis? 842 00:27:51,110 --> 00:27:53,250 Tenemos dos, cuatro, seis. 843 00:27:53,250 --> 00:27:54,800 Exactamente dónde está ahora. 844 00:27:54,800 --> 00:27:57,750 Así que vamos a dejar que por sí sola, y ahora afirmar que esta parte de la lista 845 00:27:57,750 --> 00:27:58,772 ahora está ordenada. 846 00:27:58,772 --> 00:28:01,230 Y así, esto se siente fundamentalmente diferente, ya que sólo soy 847 00:28:01,230 --> 00:28:05,230 moviéndose a través de la lista aquí linealmente, y estoy Nunca doblar la espalda. 848 00:28:05,230 --> 00:28:05,730 Sí. 849 00:28:05,730 --> 00:28:06,230 Correcto. 850 00:28:06,230 --> 00:28:08,190 Así ocho, donde pertenece usted? 851 00:28:08,190 --> 00:28:08,730 Aquí. 852 00:28:08,730 --> 00:28:09,310 Perfecto. 853 00:28:09,310 --> 00:28:10,210 Así que ahora, uno. 854 00:28:10,210 --> 00:28:10,900 UH oh. 855 00:28:10,900 --> 00:28:13,010 Esto se siente como si fuera va a ser caro. 856 00:28:13,010 --> 00:28:15,690 Ahora, en el algoritmo anterior, Yo sólo cambié personas. 857 00:28:15,690 --> 00:28:18,648 Así que yo le ponga todo el camino en al principio, pero luego se trasladó a José. 858 00:28:18,648 --> 00:28:21,450 Pero si me mudo Joseph, ahora lo que va a estar mal? 859 00:28:21,450 --> 00:28:24,250 >> Ahora, tengo una especie de undone-- tengo dado un paso hacia adelante y luego 860 00:28:24,250 --> 00:28:26,300 un paso atrás, porque ahora Joseph estaría fuera de orden. 861 00:28:26,300 --> 00:28:26,830 Así que vamos a hacer esto. 862 00:28:26,830 --> 00:28:29,150 Si usted podría tomar el número uno y un paso atrás por un momento. 863 00:28:29,150 --> 00:28:30,490 ¿Cómo podemos put-- lo era tu nombre? 864 00:28:30,490 --> 00:28:31,130 >> ANNAN: Annan. 865 00:28:31,130 --> 00:28:32,610 >> DAVID J. MALAN: Annan en su lugar? 866 00:28:32,610 --> 00:28:36,091 ¿Qué debe ocurrir con respecto a dos, cuatro, seis y ocho? 867 00:28:36,091 --> 00:28:37,570 Todos ellos necesitan cambiar. 868 00:28:37,570 --> 00:28:42,590 Así que si las ocho le gustaría cambiar primero, luego seis, luego cuatro, luego dos. 869 00:28:42,590 --> 00:28:45,380 Y entonces Annan, si lo gustaría venir aquí, bien. 870 00:28:45,380 --> 00:28:47,760 Pero aquí, acabamos de tipo de pagado un precio 871 00:28:47,760 --> 00:28:49,510 en un punto diferente en el algoritmo. 872 00:28:49,510 --> 00:28:52,550 Mientras que la última vez con la selección especie, e incluso una especie de burbuja, 873 00:28:52,550 --> 00:28:54,700 Estoy caminando hacia atrás y adelante, atrás y adelante, 874 00:28:54,700 --> 00:28:58,360 que sin duda es la suma de en cuanto a tiempo, y, literalmente, paso a paso. 875 00:28:58,360 --> 00:29:00,660 >> La ordenación por inserción, en un primer momento vista, parece que es 876 00:29:00,660 --> 00:29:05,150 súper inteligente, porque yo sólo soy hacer, el progreso gradual lento, 877 00:29:05,150 --> 00:29:07,120 pero yo no voy esta ida y vuelta. 878 00:29:07,120 --> 00:29:09,410 Pero si alguien es de hecho fuera de orden, notificación 879 00:29:09,410 --> 00:29:10,840 todo el trabajo que tenía que hacer. 880 00:29:10,840 --> 00:29:14,750 Tuve que mover la mitad de la lista sólo para hacer espacio para el número uno. 881 00:29:14,750 --> 00:29:16,790 Así que es la misma cantidad de trabajo hasta el momento se 882 00:29:16,790 --> 00:29:18,690 siente, simplemente un tipo diferente de trabajo. 883 00:29:18,690 --> 00:29:19,370 >> Continuemos. 884 00:29:19,370 --> 00:29:22,657 Así que ahora que sabemos que todo el mundo entre uno y ocho son ordenados. 885 00:29:22,657 --> 00:29:23,740 Aquí, no tengo el número tres. 886 00:29:23,740 --> 00:29:25,864 Si te gusta para recoger número tres, un paso atrás una. 887 00:29:25,864 --> 00:29:28,260 ¿Y qué es lo que ustedes necesitan hacer? 888 00:29:28,260 --> 00:29:28,760 Sí. 889 00:29:28,760 --> 00:29:33,070 Así que esa es otra de una, dos, tres pasos. 890 00:29:33,070 --> 00:29:36,010 Tres unidades de tiempo que solo cuestan mí, así que tres ahora puedo encajar. 891 00:29:36,010 --> 00:29:37,460 Finalmente, siete. 892 00:29:37,460 --> 00:29:39,730 >> Vamos a seguir adelante y tener usted toma un paso atrás. 893 00:29:39,730 --> 00:29:42,780 Esto sólo nos va a costar una unidad de tiempo, pero eso está bien. 894 00:29:42,780 --> 00:29:44,170 Y ahora, cinco de ir a ser un poco más caro. 895 00:29:44,170 --> 00:29:45,340 Si desea dar un paso atrás. 896 00:29:45,340 --> 00:29:48,380 Tenemos que pasar ocho, y siete, y seis. 897 00:29:48,380 --> 00:29:50,749 Y entonces todo el mundo está ahora ordenadas. 898 00:29:50,749 --> 00:29:52,290 Así que una gran parte de nuestros voluntarios aquí. 899 00:29:52,290 --> 00:29:53,554 Muchas gracias. 900 00:29:53,554 --> 00:29:56,220 >> [Aplausos] 901 00:29:56,220 --> 00:29:56,860 >> Gracias a todos. 902 00:29:56,860 --> 00:29:57,520 Gracias a todos. 903 00:29:57,520 --> 00:30:02,940 Así que vamos a ver ahora cómo costosa todo eso era. 904 00:30:02,940 --> 00:30:06,210 Vamos a considerar tal vez la más simple de estos, ordenamiento de burbuja. 905 00:30:06,210 --> 00:30:09,950 Y digo más simple, sólo porque se puede resolver con avidez por solo 906 00:30:09,950 --> 00:30:11,660 solucionar el problema por parejas aquí. 907 00:30:11,660 --> 00:30:13,720 Solucionar el problema de pares aquí, una y otra vez 908 00:30:13,720 --> 00:30:17,680 y de nuevo, repitiendo como muchos veces que realmente necesitan. 909 00:30:17,680 --> 00:30:21,050 >> Así resulta que con una especie de burbuja, bueno, 910 00:30:21,050 --> 00:30:25,820 cuántos pasos tengo que asumir la primera pasada de ese algoritmo? 911 00:30:25,820 --> 00:30:30,850 Podría take-- vamos a ver-- uno, dos, tres, cuatro, cinco, seis, siete. 912 00:30:30,850 --> 00:30:32,190 Y hay ocho elementos aquí. 913 00:30:32,190 --> 00:30:35,280 Así que es como n menos pasos de 1 a llegar desde el principio de la lista 914 00:30:35,280 --> 00:30:36,380 hasta el final de la lista. 915 00:30:36,380 --> 00:30:41,350 >> Pero con la selección especie, recuerdo que soy la selección de los elementos de una y otra vez 916 00:30:41,350 --> 00:30:44,590 y otra vez que es más pequeño, Estoy poniendo en su lugar, 917 00:30:44,590 --> 00:30:46,616 pero entonces yo no soy mirando detrás de mí otra vez. 918 00:30:46,616 --> 00:30:49,490 Así que creo que es un poco más clara a continuación, que la primera vez, yo podría 919 00:30:49,490 --> 00:30:52,680 tiene que tomar todo n menos pasos de 1 para encontrar el elemento más pequeño. 920 00:30:52,680 --> 00:30:55,920 Entonces los puse en su lugar, y yo desalojar a todo el que estaba aquí antes. 921 00:30:55,920 --> 00:30:57,500 >> Pero entonces yo no tengo que seguir buscando en este elemento, 922 00:30:57,500 --> 00:30:59,040 porque yo sé que es ya los más pequeños. 923 00:30:59,040 --> 00:31:01,581 Así que ahora, puedo mirar a sólo siete elementos, entonces seis elementos, 924 00:31:01,581 --> 00:31:03,290 a continuación, cinco elementos, luego cuatro elementos. 925 00:31:03,290 --> 00:31:06,900 Y así, matemáticamente, si n es el número de elementos o números 926 00:31:06,900 --> 00:31:11,990 que empezamos con, se puede imaginar que este es el mismo que n menos 1, 927 00:31:11,990 --> 00:31:14,250 más n menos 2 pasos, más n menos 3 pasos, 928 00:31:14,250 --> 00:31:16,780 más n menos 4 pasos, todo el hasta llegar a un solo paso. 929 00:31:16,780 --> 00:31:18,160 Y estoy en mi última persona. 930 00:31:18,160 --> 00:31:20,650 >> Y si usted recuerda que una gran cantidad Estadísticas de libros o libros de matemáticas 931 00:31:20,650 --> 00:31:24,730 tener esas fórmulas en el tapa dura atrás o delante de ellos, 932 00:31:24,730 --> 00:31:27,690 resulta que esta serie puede expresarse más sencillamente 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 Y está bien si eso no es a la vanguardia de su mente. 935 00:31:31,273 --> 00:31:32,420 Pero esto es cierto. 936 00:31:32,420 --> 00:31:34,449 Eso es sólo una manera más sencilla de escribir. 937 00:31:34,449 --> 00:31:36,240 Y entonces si usted piensa de nuevo a la escuela primaria, 938 00:31:36,240 --> 00:31:38,698 cuando acaba de empezar a multiplicar cosas fuera, esto, por supuesto, 939 00:31:38,698 --> 00:31:41,820 es simplemente n al cuadrado menos n dividido por 2. 940 00:31:41,820 --> 00:31:44,772 Lo único que he hecho es ampliar las expresiones allí. 941 00:31:44,772 --> 00:31:46,730 Y así vamos a reescribir esta un poco diferente. 942 00:31:46,730 --> 00:31:49,780 Eso n al cuadrado dividido por 2 menos n / 2. 943 00:31:49,780 --> 00:31:53,270 >> Así que de nuevo, yo soy sólo un poco de la aplicación un poco de aritmética gobierna allí. 944 00:31:53,270 --> 00:31:57,140 Pero note ahora que el mayor plazo En esta expresión, por así decirlo, 945 00:31:57,140 --> 00:31:58,540 es que n al cuadrado. 946 00:31:58,540 --> 00:32:02,910 Así que sí, es n al cuadrado dividido por 2, menos n / 2. 947 00:32:02,910 --> 00:32:05,080 >> Pero, en general, si n es va a ser un gran valor, 948 00:32:05,080 --> 00:32:08,740 Voy a decir que n al cuadrado va a ser el factor dominante. 949 00:32:08,740 --> 00:32:10,490 Es sólo va a ser un contribuyente más grande 950 00:32:10,490 --> 00:32:12,877 con el número de pasos que n / 2. 951 00:32:12,877 --> 00:32:13,960 Entonces, ¿qué quiero decir con esto? 952 00:32:13,960 --> 00:32:16,795 Probemos un ejemplo sencillo, incluso aunque las matemáticas consigue un poco grande. 953 00:32:16,795 --> 00:32:20,210 >> Así que supongamos que tenemos 1 millón de personas en el escenario, o 1 millón de cosas 954 00:32:20,210 --> 00:32:21,320 que queremos ordenar. 955 00:32:21,320 --> 00:32:23,730 Vamos a enchufe de un millón exactamente en esa fórmula 956 00:32:23,730 --> 00:32:27,230 para ver la cantidad de pasos que toma total de para ordenar un millón de elementos usando por ejemplo, 957 00:32:27,230 --> 00:32:28,560 ordenación por selección. 958 00:32:28,560 --> 00:32:30,760 >> Así tendríamos la misma fórmula que antes. 959 00:32:30,760 --> 00:32:34,120 Me conecto un millón, por lo que tengo un millón al cuadrado dividido por 2, 960 00:32:34,120 --> 00:32:35,990 menos de un millón dividido por 2. 961 00:32:35,990 --> 00:32:40,180 Si hago eso matemáticas de antemano aquí, tenemos 500 mil millones 962 00:32:40,180 --> 00:32:47,460 menos 500.000, que nos da 499999500000, 963 00:32:47,460 --> 00:32:49,270 que es bastante maldito grande. 964 00:32:49,270 --> 00:32:54,370 >> De hecho, si se compara ahora 499000000000, 999 millones, 965 00:32:54,370 --> 00:33:01,210 500.000 contra nuestro valor original, 500 mil millones, es tan condenadamente cerca. 966 00:33:01,210 --> 00:33:06,850 ¿Correcto? n al cuadrado dividido por 2 da nosotros-- o más bien, n al cuadrado dividido por 2 967 00:33:06,850 --> 00:33:08,370 nos dio 500 mil millones. 968 00:33:08,370 --> 00:33:13,510 Eso es bastante maldito cerca a 499999500000, 969 00:33:13,510 --> 00:33:17,970 es decir, restando off 500000, o, más generalmente, restando off 970 00:33:17,970 --> 00:33:20,010 n al cuadrado, no es realmente un gran problema. 971 00:33:20,010 --> 00:33:22,490 El n al cuadrado hace que estos números crecen muy rápido. 972 00:33:22,490 --> 00:33:25,790 >> Ahora, esto es importante sólo en la medida como nosotros, como los informáticos, 973 00:33:25,790 --> 00:33:29,350 generalmente no se va a importar mucho sobre los matices de estas fórmulas 974 00:33:29,350 --> 00:33:31,400 y exactamente lo que el respuestas precisas. 975 00:33:31,400 --> 00:33:33,390 Nos preocupamos sólo eso, ¿sabes qué? 976 00:33:33,390 --> 00:33:37,810 Al final del día, esta fórmula es del orden de n al cuadrado. 977 00:33:37,810 --> 00:33:39,350 >> Sí, estamos dividiendo por 2 en ese país. 978 00:33:39,350 --> 00:33:41,360 Sí, estamos restando fuera n menos 2. 979 00:33:41,360 --> 00:33:46,860 Pero al final del día, el término que realmente nos duele y nos cuesta 980 00:33:46,860 --> 00:33:48,995 un montón de pasos es ese término cuadrado. 981 00:33:48,995 --> 00:33:51,370 Y así lo que un científico de la computación se va a hacer en general 982 00:33:51,370 --> 00:33:54,160 es ignorar todos los términos de orden más pequeños, 983 00:33:54,160 --> 00:33:56,900 y basta con ver la que contribuye más al costo. 984 00:33:56,900 --> 00:34:00,530 >> Y esto es bueno, porque podemos ahora hablar en mucho mayor generalidad 985 00:34:00,530 --> 00:34:02,470 sobre algoritmos, y puede compararlos. 986 00:34:02,470 --> 00:34:04,550 Y el hecho de que soy el uso de esta O es deliberado. 987 00:34:04,550 --> 00:34:06,680 Cuando digo que en el orden de, estoy específicamente 988 00:34:06,680 --> 00:34:09,560 se refiere a algo llamado grande O. Y gran O 989 00:34:09,560 --> 00:34:14,090 es una notación que una computadora científico utiliza 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 >> Así que si usted dice que un algoritmo es en gran O de n al cuadrado, 992 00:34:21,150 --> 00:34:23,380 como he propuesto sólo un Hace momento, que los medios 993 00:34:23,380 --> 00:34:27,710 que en términos de su funcionamiento tiempo o su eficiencia, 994 00:34:27,710 --> 00:34:30,090 que se necesita en el orden de n cuadrado pasos. 995 00:34:30,090 --> 00:34:31,420 Tal vez más, tal vez menos. 996 00:34:31,420 --> 00:34:33,435 Pero es del orden de n al cuadrado. 997 00:34:33,435 --> 00:34:34,560 Y ese es el límite superior. 998 00:34:34,560 --> 00:34:36,530 No va a ser más doloroso que eso. 999 00:34:36,530 --> 00:34:40,800 No va a ser n en cubos o 2 a la n, o algo mucho más grande. 1000 00:34:40,800 --> 00:34:43,800 Esta es una cota superior en lo que el costo es. 1001 00:34:43,800 --> 00:34:46,150 Así que teniendo en cuenta que, vamos a considerar sólo algunos ejemplos. 1002 00:34:46,150 --> 00:34:49,820 Y esto es sólo una lista finita tiempos de ejecución de los muy comunes 1003 00:34:49,820 --> 00:34:52,870 para los algoritmos que está destinado a ser ilustrativo de algunas cosas que hemos 1004 00:34:52,870 --> 00:34:53,600 ya se ha visto. 1005 00:34:53,600 --> 00:34:58,060 >> Así, por ejemplo, en el caso de ordenación por selección, lo que estoy diciendo aquí 1006 00:34:58,060 --> 00:35:02,250 es en ejecución que la selección de especie el tiempo es del orden de n al cuadrado. 1007 00:35:02,250 --> 00:35:06,260 En el peor de los casos, voy a tener un montón de números aleatorios aquí. 1008 00:35:06,260 --> 00:35:08,600 Y como vimos matemáticamente, si sigo caminando 1009 00:35:08,600 --> 00:35:11,310 a través de la lista, a través de la lista, seleccionando el inmediatamente inferior 1010 00:35:11,310 --> 00:35:14,410 elemento y otra vez, si yo realidad anote todos los pasos 1011 00:35:14,410 --> 00:35:18,750 Estoy tomando como propuse formulaically antes, es del orden de n al cuadrado 1012 00:35:18,750 --> 00:35:20,370 medidas que estoy tomando. 1013 00:35:20,370 --> 00:35:24,520 >> Y resulta que la burbuja clasificación y ordenación por inserción 1014 00:35:24,520 --> 00:35:27,370 son tan lento en el peor de los casos. 1015 00:35:27,370 --> 00:35:32,040 Consideremos, por ejemplo, la ordenación por inserción, el último algoritmo con el que tratamos, 1016 00:35:32,040 --> 00:35:35,500 que tenían nos fijamos en el elemento, y luego insertarlo donde pertenece. 1017 00:35:35,500 --> 00:35:38,720 Y luego nos fijamos en el siguiente elemento, y se inserta donde pertenece. 1018 00:35:38,720 --> 00:35:40,990 >> Así que considera el mejor escenario posible. 1019 00:35:40,990 --> 00:35:45,590 Supongamos que yo tenía mis voluntarios alinear literalmente así, uno al ocho, 1020 00:35:45,590 --> 00:35:47,440 ya ordenados. 1021 00:35:47,440 --> 00:35:51,300 ¿Cuántos pasos es la ordenación por inserción va a tomar para ordenar a ocho personas, 1022 00:35:51,300 --> 00:35:55,640 si llegan en el escenario buscando de esta manera? 1023 00:35:55,640 --> 00:35:57,410 >> Ocho personas ya ordenados. 1024 00:35:57,410 --> 00:35:58,760 Y uso ordenación por inserción. 1025 00:35:58,760 --> 00:36:02,180 El último de los algoritmos. 1026 00:36:02,180 --> 00:36:03,640 Bueno, vamos a recrear rápido real. 1027 00:36:03,640 --> 00:36:05,504 Así que si me pongo aquí, lo veo. 1028 00:36:05,504 --> 00:36:06,420 ¿Por dónde pertenecen? 1029 00:36:06,420 --> 00:36:07,730 Pertenece aquí. 1030 00:36:07,730 --> 00:36:08,330 Veo dos. 1031 00:36:08,330 --> 00:36:09,660 ¿De dónde viene dos pertenecen? 1032 00:36:09,660 --> 00:36:10,260 Aquí. 1033 00:36:10,260 --> 00:36:10,900 Veo tres. 1034 00:36:10,900 --> 00:36:11,920 ¿De dónde viene tres pertenecen? 1035 00:36:11,920 --> 00:36:12,480 Aquí. 1036 00:36:12,480 --> 00:36:13,100 >> Veo cuatro. 1037 00:36:13,100 --> 00:36:13,600 Aquí. 1038 00:36:13,600 --> 00:36:15,660 Cinco, seis, siete, ocho. 1039 00:36:15,660 --> 00:36:17,320 No hay razón para repetir a mí mismo. 1040 00:36:17,320 --> 00:36:21,260 Y así, el número de pasos es que en términos de n? 1041 00:36:21,260 --> 00:36:23,870 Es del orden de n pasos, ¿verdad? n menos 1. 1042 00:36:23,870 --> 00:36:27,567 Pero tomé una serie lineal de pasos, y ahora he terminado. 1043 00:36:27,567 --> 00:36:28,900 Así que ese es el mejor de los casos, sin embargo. 1044 00:36:28,900 --> 00:36:29,983 ¿Y el peor de los casos? 1045 00:36:29,983 --> 00:36:32,730 Lo que ocho eran de allí, y siete eran allí abajo, 1046 00:36:32,730 --> 00:36:35,840 y uno y dos eran de aquí, por lo que que la lista se invirtiera en verdad? 1047 00:36:35,840 --> 00:36:38,300 >> Bueno, lo que sucede de hecho si este es el número? 1048 00:36:38,300 --> 00:36:41,300 Y vamos a hacer sólo un par de ejemplos. 1049 00:36:41,300 --> 00:36:49,300 ¿Qué pasaría si, de hecho, el número ocho es aquí, y los gritos number--. 1050 00:36:49,300 --> 00:36:52,660 1051 00:36:52,660 --> 00:36:56,430 ¿Y qué si, de hecho, el número ocho es todo el camino hasta aquí, 1052 00:36:56,430 --> 00:36:57,790 y estoy usando la ordenación por inserción? 1053 00:36:57,790 --> 00:36:58,290 >> OK. 1054 00:36:58,290 --> 00:37:00,280 Reclamo en este momento está en su lugar. 1055 00:37:00,280 --> 00:37:03,152 Pero ahora, seven-- ¿dónde van siete años? 1056 00:37:03,152 --> 00:37:04,360 Por supuesto, no hace falta aquí. 1057 00:37:04,360 --> 00:37:06,760 Así que tengo que mover y ocho más de un lugar. 1058 00:37:06,760 --> 00:37:08,554 Ahora seis, ¿hacia dónde va? 1059 00:37:08,554 --> 00:37:09,220 Bueno, está bien. 1060 00:37:09,220 --> 00:37:13,150 Ahora, tengo que mover y ocho más un lugar y siete más de un lugar, 1061 00:37:13,150 --> 00:37:14,440 y luego me dejo caer seis. 1062 00:37:14,440 --> 00:37:16,870 >> Así que la primera vez, el costo mí un paso de arreglar las cosas, 1063 00:37:16,870 --> 00:37:18,570 entonces me costó dos pasos para arreglar las cosas. 1064 00:37:18,570 --> 00:37:20,370 ¿Cuántos pasos es va a tomar para solucionar 1065 00:37:20,370 --> 00:37:22,720 cosas para poner cinco en el lugar correcto? 1066 00:37:22,720 --> 00:37:23,340 Tres. 1067 00:37:23,340 --> 00:37:29,520 Porque ahora tengo que mover uno, dos, tres. 1068 00:37:29,520 --> 00:37:32,430 ¿Cuántos pasos se va a tomar poner cuatro en el lugar correcto? 1069 00:37:32,430 --> 00:37:36,040 4 y 5, además de 6, más 7. 1070 00:37:36,040 --> 00:37:40,260 >> Y lo que es matemáticamente idéntica a lo que hemos descrito para la selección de género. 1071 00:37:40,260 --> 00:37:42,130 Tenemos esta serie eso es sólo el aumento. 1072 00:37:42,130 --> 00:37:45,650 1 más 2 más 3 más 4, o por el contrario, 7 plus 6 1073 00:37:45,650 --> 00:37:52,610 más 5 más 4 añade hoy de efectos a del orden de n al cuadrado. 1074 00:37:52,610 --> 00:37:57,640 >> Así que permítanme estipulo también que ordenamiento de burbuja es también n al cuadrado. 1075 00:37:57,640 --> 00:38:01,340 Porque con ordenamiento de burbuja, cada vez que voy por la lista, 1076 00:38:01,340 --> 00:38:03,100 Estoy tomando más o menos cuántos pasos? 1077 00:38:03,100 --> 00:38:06,260 Cada vez que, literalmente, caminar desde allí hasta allí? 1078 00:38:06,260 --> 00:38:07,960 Alrededor de n pasos. 1079 00:38:07,960 --> 00:38:12,650 Pero ¿cuántas veces puede ocurrir que pasar por la lista? 1080 00:38:12,650 --> 00:38:13,920 >> Bueno, más o menos n tiempo. 1081 00:38:13,920 --> 00:38:15,680 Tal vez n menos 1, pero más o menos n veces. 1082 00:38:15,680 --> 00:38:16,430 Bueno, ¿por qué es eso? 1083 00:38:16,430 --> 00:38:19,560 Bueno, con la burbuja del tipo, si partimos de ordenamiento de burbuja, 1084 00:38:19,560 --> 00:38:23,570 con la lista en la peor posible situación, que de nuevo es completamente 1085 00:38:23,570 --> 00:38:25,550 al revés, lo que va a pasar? 1086 00:38:25,550 --> 00:38:28,830 Voy a través de la lista, y el número de uno pertenece todo el camino por allí. 1087 00:38:28,830 --> 00:38:33,280 >> Pero con la burbuja del tipo, ¿hasta dónde puede uno pasar mi primer pase a través de la lista? 1088 00:38:33,280 --> 00:38:36,620 ¿Cuántos puntos es lo que obtiene más cerca de el lugar correcto? 1089 00:38:36,620 --> 00:38:37,240 Solo uno. 1090 00:38:37,240 --> 00:38:40,281 Así que si usted tipo de razón a través de este, cada vez que a través de este algoritmo, 1091 00:38:40,281 --> 00:38:41,880 Teniendo aproximadamente n pasos de David. 1092 00:38:41,880 --> 00:38:44,940 Pero, ¿cuántos pases a través de la lista es que 1093 00:38:44,940 --> 00:38:49,060 va a tomar para que uno de burbujas a la izquierda donde pertenece? 1094 00:38:49,060 --> 00:38:51,840 >> Él tiene que moverse como, n espacios de esta manera. 1095 00:38:51,840 --> 00:38:57,960 Así que para hacer la clasificación de la lista, Tengo que ir y venir n veces. 1096 00:38:57,960 --> 00:39:01,540 Y cada vez, estoy mirando a n elementos. 1097 00:39:01,540 --> 00:39:05,410 Lo mismo ocurre con las cosas n n veces en del orden de n al cuadrado. 1098 00:39:05,410 --> 00:39:07,220 >> Ahora, vamos a ver de alguna de los cortos que 1099 00:39:07,220 --> 00:39:10,440 se incrustan en el siguiente problema de CS50 establecer, otro enfoque a estos, 1100 00:39:10,440 --> 00:39:13,490 pero por ahora, vamos a considerar otras veces se ejecutan, 1101 00:39:13,490 --> 00:39:16,840 especialmente si los toman de clasificación un poco de tiempo para hundirse en. 1102 00:39:16,840 --> 00:39:21,790 ¿Qué es un algoritmo que hemos visto ya que lleva del orden de n pasos? 1103 00:39:21,790 --> 00:39:27,560 >> ¿Qué se debe tomar una serie lineal de los pasos que hemos visto hasta ahora? 1104 00:39:27,560 --> 00:39:29,350 ¿Que es eso? 1105 00:39:29,350 --> 00:39:30,480 La búsqueda en el directorio telefónico. 1106 00:39:30,480 --> 00:39:31,390 El primer algoritmo. 1107 00:39:31,390 --> 00:39:31,560 ¿Correcto? 1108 00:39:31,560 --> 00:39:33,650 Dónde estamos linealmente la búsqueda de Mike Smith? 1109 00:39:33,650 --> 00:39:34,150 Ciertamente. 1110 00:39:34,150 --> 00:39:37,180 Desde la semana cero, cuando empecé convertir una página a la vez, 1111 00:39:37,180 --> 00:39:40,095 e incluso le dije que era una especie de un algoritmo sensación lineal, 1112 00:39:40,095 --> 00:39:42,720 y tuvimos esa foto en la tablero con la línea roja directa 1113 00:39:42,720 --> 00:39:44,678 y el amarillo recta línea, esos eran de hecho 1114 00:39:44,678 --> 00:39:46,810 algoritmos que son en gran O de n. 1115 00:39:46,810 --> 00:39:50,680 >> Porque para encontrar Mike Smith en un teléfono libro de n páginas, en el peor de los casos, 1116 00:39:50,680 --> 00:39:52,422 me n medidas podría tomar. 1117 00:39:52,422 --> 00:39:53,630 ¿Qué hay de tomar asistencia? 1118 00:39:53,630 --> 00:39:55,790 Uno dos tres CUATRO CINCO SEIS. 1119 00:39:55,790 --> 00:39:59,420 ¿Qué es el tiempo de ejecución de la presente algoritmo para la toma de asistencia? 1120 00:39:59,420 --> 00:40:03,070 O grande de n, ya que en teoría me tienes que apuntar todos en la sala. 1121 00:40:03,070 --> 00:40:05,861 >> Ahora como un aparte, ¿qué pasa con la otra optimización de semana cero? 1122 00:40:05,861 --> 00:40:08,117 Dos, cuatro, seis, ocho, 10, 12. 1123 00:40:08,117 --> 00:40:10,200 Un científico de la computación lo haría darse cuenta, espere un minuto, 1124 00:40:10,200 --> 00:40:12,320 eso es del orden de n dividido por dos pasos. 1125 00:40:12,320 --> 00:40:12,820 ¿Correcto? 1126 00:40:12,820 --> 00:40:14,444 Debido a que estoy haciendo dos personas a la vez. 1127 00:40:14,444 --> 00:40:17,015 Pero vamos a ignorar los términos de orden inferior, 1128 00:40:17,015 --> 00:40:19,140 y nosotros sólo vamos a tirar la divide por 2, 1129 00:40:19,140 --> 00:40:21,830 y decir, gran O de n para que el algoritmo también. 1130 00:40:21,830 --> 00:40:22,760 >> ¿Qué tal este? 1131 00:40:22,760 --> 00:40:26,170 Nos saltaremos sobre algunos de ellos, pero lo que era un algoritmo que era log de n? 1132 00:40:26,170 --> 00:40:29,900 Que tuvo más o menos log n pasos? 1133 00:40:29,900 --> 00:40:30,870 El divide y vencerás. 1134 00:40:30,870 --> 00:40:31,369 Exactamente. 1135 00:40:31,369 --> 00:40:33,900 Al igual que el ejemplo de libro de teléfono en semana cero y el día de hoy, 1136 00:40:33,900 --> 00:40:36,191 donde nos dividimos el problema De nuevo y de nuevo y de nuevo. 1137 00:40:36,191 --> 00:40:39,070 Dibujamos en la pizarra en la semana cero como una línea verde curvado, 1138 00:40:39,070 --> 00:40:41,460 y nos dijo ese día que era un algoritmo logarítmico. 1139 00:40:41,460 --> 00:40:44,970 >> Y de hecho, el número de pasos que lleva a cabo divide y vencerás, 1140 00:40:44,970 --> 00:40:48,610 o búsqueda binaria como vamos a empezar llamándolo, como en la guía telefónica, 1141 00:40:48,610 --> 00:40:50,680 es del orden de registro y pasos. 1142 00:40:50,680 --> 00:40:52,470 Y esto es un poco de un ser extraño. 1143 00:40:52,470 --> 00:40:54,910 >> Lo que da un paso, o más específicamente 1144 00:40:54,910 --> 00:40:56,240 un número constante de pasos? 1145 00:40:56,240 --> 00:40:58,865 Tal vez sea de dos, tal vez es tres, pero un informático solo 1146 00:40:58,865 --> 00:41:01,423 simplifica tan grande O de 1, un número constante de pasos. 1147 00:41:01,423 --> 00:41:04,256 ¿Qué es algo que podría hacer que toma un número constante de pasos? 1148 00:41:04,256 --> 00:41:08,030 1149 00:41:08,030 --> 00:41:10,930 >> ¿Cuál es el tiempo de ejecución de aplaudir? 1150 00:41:10,930 --> 00:41:11,920 Constante de tiempo. 1151 00:41:11,920 --> 00:41:12,420 ¿Correcto? 1152 00:41:12,420 --> 00:41:15,490 Al igual que, ¿cuál es el tiempo de funcionamiento del hacer cualquier cosa que toma sólo una 1153 00:41:15,490 --> 00:41:18,570 operación, como imprimir F Hello World. 1154 00:41:18,570 --> 00:41:24,110 Eso podría decirse que la constante de tiempo, menos que menos caso esquina con la impresión M, 1155 00:41:24,110 --> 00:41:28,260 lo que podría el tiempo de ejecución de impresión F realidad sea? 1156 00:41:28,260 --> 00:41:28,790 ¿Y por qué? 1157 00:41:28,790 --> 00:41:30,550 ¿Qué es la n de medición en ese caso? 1158 00:41:30,550 --> 00:41:32,251 >> AUDIENCIA: [inaudible]. 1159 00:41:32,251 --> 00:41:33,250 DAVID J. MALAN: Exactamente. 1160 00:41:33,250 --> 00:41:34,900 El número de caracteres queremos imprimir. 1161 00:41:34,900 --> 00:41:36,191 Así que es muy sensible al contexto. 1162 00:41:36,191 --> 00:41:39,910 Hoy, nos hemos centrado mucho en las letras y los números aquí en el tablero. 1163 00:41:39,910 --> 00:41:43,540 Pero también podría ser personajes de una cadena real. 1164 00:41:43,540 --> 00:41:46,420 Así que resulta que hay otro medida que comenzará a preocuparse, 1165 00:41:46,420 --> 00:41:48,530 y eso es todo lo contrario de gran O, por decirlo así. 1166 00:41:48,530 --> 00:41:50,120 >> Esa es la notación omega. 1167 00:41:50,120 --> 00:41:53,380 Mientras que gran O significa lo que es, la límite superior de su tiempo de funcionamiento? 1168 00:41:53,380 --> 00:41:55,580 Como máximo, la cantidad de tiempo podría tomar algo? 1169 00:41:55,580 --> 00:41:59,250 Omega-- siento esto sigue llegando up-- es lo contrario de eso, 1170 00:41:59,250 --> 00:42:02,960 mediante el cual se trata de un límite inferior en el cantidad de tiempo que algo podría tomar. 1171 00:42:02,960 --> 00:42:10,480 >> So. por ejemplo, ¿qué es un algoritmo que tome medidas siempre n al cuadrado? 1172 00:42:10,480 --> 00:42:15,600 Bueno, uno de los algoritmos que he visto Hoy en día, de hecho, podría ser que también. 1173 00:42:15,600 --> 00:42:16,720 Selección tipo. 1174 00:42:16,720 --> 00:42:18,270 Selección especie es bastante estúpido. 1175 00:42:18,270 --> 00:42:21,760 Incluso si la siento algorithm--, aun si la matriz ya está ordenado, 1176 00:42:21,760 --> 00:42:24,150 ordenación por selección va a seguir caminando por la lista 1177 00:42:24,150 --> 00:42:28,907 para asegurarse de que cuenta con el más pequeño elemento de una y otra y otra vez. 1178 00:42:28,907 --> 00:42:31,740 Y a pesar de que los seres humanos en el público sepa que, espera un minuto, 1179 00:42:31,740 --> 00:42:33,948 que ya pasó el elemento más pequeño, el ordenador 1180 00:42:33,948 --> 00:42:37,300 no sabe que hasta que se vea todo el camino a través de la lista. 1181 00:42:37,300 --> 00:42:40,240 Del mismo modo, una cota inferior que también puede ser tenido en cuenta 1182 00:42:40,240 --> 00:42:42,000 podría ser el momento lineal. 1183 00:42:42,000 --> 00:42:48,260 >> ¿Cuánto tiempo se tarda en ordenar n elementos en la mejor 1184 00:42:48,260 --> 00:42:52,420 caso usando algo así como una especie de burbuja? 1185 00:42:52,420 --> 00:42:54,280 Supongamos que su lista ya está ordenado. 1186 00:42:54,280 --> 00:42:56,696 Dijimos burbuja especie adquiere del orden de n al cuadrado pasos. 1187 00:42:56,696 --> 00:42:59,640 Pero lo que si ya está ordenada? 1188 00:42:59,640 --> 00:43:02,310 ¿Y si te das cuenta después un paso a través de la matriz 1189 00:43:02,310 --> 00:43:03,540 que usted ha hecho no hay permutas? 1190 00:43:03,540 --> 00:43:05,970 ¿Es necesario seguir haciendo más pases? 1191 00:43:05,970 --> 00:43:06,470 >> No. 1192 00:43:06,470 --> 00:43:10,340 Así que un límite inferior en el ordenamiento de burbuja podría decirse que es lineal. 1193 00:43:10,340 --> 00:43:11,830 Omega de n. 1194 00:43:11,830 --> 00:43:14,450 Y podemos ver otros de estos también. 1195 00:43:14,450 --> 00:43:17,990 Así que vamos a echar un vistazo rápido en apenas una visualización aquí 1196 00:43:17,990 --> 00:43:20,790 para ver cómo éstas se distinguen. 1197 00:43:20,790 --> 00:43:24,592 Voy a ir por aquí a esta página que está disponible en la página web de C50, 1198 00:43:24,592 --> 00:43:27,550 pero va a ser un dolor para conseguir trabajo, ya que utiliza una tecnología llamada 1199 00:43:27,550 --> 00:43:30,560 Los applets de Java, que es un en gran medida sin apoyo en estos días, 1200 00:43:30,560 --> 00:43:32,730 al menos por cromo y algunos otros. 1201 00:43:32,730 --> 00:43:37,070 >> Y déjame ir adelante y acelerar este y explicar lo que está pasando. 1202 00:43:37,070 --> 00:43:40,840 Esta es una demostración de la burbuja especie, el primer algoritmo nos miró. 1203 00:43:40,840 --> 00:43:43,950 Y es una visualización en el que cada de estas barras representa un número. 1204 00:43:43,950 --> 00:43:45,710 Cuanto más grande sea la barra, cuanto mayor sea el número. 1205 00:43:45,710 --> 00:43:47,520 Cuanto menor sea la barra, cuanto menor sea el número. 1206 00:43:47,520 --> 00:43:50,353 ¿Y qué se puede ver visualmente, incluso aunque esto va muy rápido, 1207 00:43:50,353 --> 00:43:53,699 es que la barra roja es como yo, caminando hacia atrás y fijar sucesivamente problemas. 1208 00:43:53,699 --> 00:43:56,740 Se puede ver que los elementos más grandes son de hecho burbujeando hacia la derecha, 1209 00:43:56,740 --> 00:43:59,650 y los elementos más pequeños están burbujeando hacia la izquierda. 1210 00:43:59,650 --> 00:44:01,870 Y aquí, si realmente mirar más de cerca, 1211 00:44:01,870 --> 00:44:04,330 realmente podemos contar el número de comparaciones y swaps 1212 00:44:04,330 --> 00:44:05,350 que se estaban haciendo. 1213 00:44:05,350 --> 00:44:07,360 >> Pero en lugar, echemos un vistazo en el segundo algoritmo 1214 00:44:07,360 --> 00:44:11,240 vimos antes con nuestra voluntarios, selección de ordenar. 1215 00:44:11,240 --> 00:44:13,500 Visualmente, tiene una muy diferente efecto. 1216 00:44:13,500 --> 00:44:16,820 Pero es, de nuevo, muy intuitiva, en que guardemos la selección de la próxima más pequeña 1217 00:44:16,820 --> 00:44:18,660 elemento, y nos dieron un poco de suerte. 1218 00:44:18,660 --> 00:44:20,110 Eso se sintió fundamentalmente más rápido. 1219 00:44:20,110 --> 00:44:22,840 Pero si nos encontramos una y otra vez y otra vez con una gran cantidad de insumos, 1220 00:44:22,840 --> 00:44:26,680 veríamos que es de hecho todavía en gran O de n al cuadrado. 1221 00:44:26,680 --> 00:44:29,920 >> Vamos a hacer un último de un aquí, la ordenación por inserción, 1222 00:44:29,920 --> 00:44:33,180 que fue el tercer algoritmo nos miramos, y el recuerdo 1223 00:44:33,180 --> 00:44:36,700 que éste se ocupa de la elementos, ya que los encuentra, 1224 00:44:36,700 --> 00:44:39,290 Pero entonces quizás turnos las cosas para hacer espacio, 1225 00:44:39,290 --> 00:44:41,660 la inserción de elementos que pertenecen. 1226 00:44:41,660 --> 00:44:45,330 >> Y esto también termina dando la resultado final. Ahora los tres de los 1227 00:44:45,330 --> 00:44:46,490 sentí bastante rápido. 1228 00:44:46,490 --> 00:44:48,740 Y, de hecho, yo los encontré a un ritmo bastante bueno. 1229 00:44:48,740 --> 00:44:52,510 Pero fundamentalmente, son todos bastante horrible, para ser honesto. 1230 00:44:52,510 --> 00:44:56,960 Todos estos algoritmos hasta ahora que se ejecutan en gran O de n al cuadrado 1231 00:44:56,960 --> 00:44:59,270 tomar un poco de tiempo para correr en el final. 1232 00:44:59,270 --> 00:45:01,920 >> Y de hecho, podemos ver y sentir este último 1233 00:45:01,920 --> 00:45:04,090 si me levanto esta tercera y última demostración. 1234 00:45:04,090 --> 00:45:05,840 Esta es otra visualización que va 1235 00:45:05,840 --> 00:45:08,500 para mostrar ordenamiento de burbuja en la izquierda, ordenación por selección en el medio, 1236 00:45:08,500 --> 00:45:13,410 y algo que, como uno de nuestro mano plantea sugirió anteriormente, 1237 00:45:13,410 --> 00:45:15,020 ordenamiento por mezcla a la derecha. 1238 00:45:15,020 --> 00:45:16,937 Un divide y vencerás la estrategia de la derecha. 1239 00:45:16,937 --> 00:45:19,520 Y eso es, de hecho, lo que estamos ir a ver el miércoles. 1240 00:45:19,520 --> 00:45:21,990 Pero el tiempo éstos se ejecute en paralelo vamos. 1241 00:45:21,990 --> 00:45:26,765 Es más o menos el mismo número de elementos, todos funcionando al mismo tiempo. 1242 00:45:26,765 --> 00:45:30,940 1243 00:45:30,940 --> 00:45:34,440 Burbuja especie vs selección especie vs fusión tipo. 1244 00:45:34,440 --> 00:45:36,760 >> Ahora, todos están corriendo en teoría al mismo tiempo. 1245 00:45:36,760 --> 00:45:39,830 La CPU está funcionando a la misma velocidad, pero 1246 00:45:39,830 --> 00:45:44,014 puede sentir lo aburrido que es va muy rápidamente para convertirse, 1247 00:45:44,014 --> 00:45:45,930 y cuán rápido cuando inyectamos un poco de semana 1248 00:45:45,930 --> 00:45:49,330 algoritmos de cero puede que acelerar las cosas. 1249 00:45:49,330 --> 00:45:51,760 >> Y ahora vamos a comparar estos en una última forma. 1250 00:45:51,760 --> 00:45:55,710 Voy a seguir adelante el sitio web del CS50, donde 1251 00:45:55,710 --> 00:45:59,020 tenemos este último eslabón para hoy, donde alguien en Internet 1252 00:45:59,020 --> 00:46:03,960 amablemente armar un vídeo que capta lo diferente clasificación 1253 00:46:03,960 --> 00:46:07,510 algoritmos suenan. 1254 00:46:07,510 --> 00:46:09,577 Esta es la ordenación por inserción. 1255 00:46:09,577 --> 00:46:12,072 >> [SONIDO] 1256 00:46:12,072 --> 00:46:13,070 1257 00:46:13,070 --> 00:46:16,850 >> Por el cual usted está solicitando una frecuencia basado en la altura de la barra de bar. 1258 00:46:16,850 --> 00:46:19,826 Se trata de ordenamiento de burbuja. 1259 00:46:19,826 --> 00:46:21,822 >> [SONIDO Warped] 1260 00:46:21,822 --> 00:46:33,299 1261 00:46:33,299 --> 00:46:45,774 >> Que hasta la próxima es-- venir al lado es-- ordenación por selección, 1262 00:46:45,774 --> 00:46:48,820 donde de nuevo, estamos seleccionando el siguiente elemento más pequeño, 1263 00:46:48,820 --> 00:46:51,820 y podemos ver que cada vez más de izquierda a derecha. 1264 00:46:51,820 --> 00:47:01,120 1265 00:47:01,120 --> 00:47:04,000 >> Combinar especie, por lo que nuestro ganador la fecha de hoy. 1266 00:47:04,000 --> 00:47:09,659 1267 00:47:09,659 --> 00:47:12,450 Observe cómo está dividiendo cosas en [inaudible] media y los cuartos. 1268 00:47:12,450 --> 00:47:17,510 1269 00:47:17,510 --> 00:47:21,660 Tipo Gnome, que no tenemos hablado, y crea visualmente 1270 00:47:21,660 --> 00:47:24,450 y audally un poco de un diferente forma y sonido. 1271 00:47:24,450 --> 00:47:27,060 1272 00:47:27,060 --> 00:47:30,160 El ir y venir, la limpieza de las cosas. 1273 00:47:30,160 --> 00:47:32,230 También puedes ver heapsort en la página web de este tipo. 1274 00:47:32,230 --> 00:47:36,100 1275 00:47:36,100 --> 00:47:36,810 >> Y eso es. 1276 00:47:36,810 --> 00:47:38,210 Nos vemos la próxima vez. 1277 00:47:38,210 --> 00:47:42,647 1278 00:47:42,647 --> 00:47:48,334 >> [Whooshing Y MÚSICA] 1279 00:47:48,334 --> 00:50:24,839