1 00:00:00,000 --> 00:00:11,270 2 00:00:11,270 --> 00:00:14,910 >> ALTAVOZ: Muy bien, esto es CS50. 3 00:00:14,910 --> 00:00:19,020 Este es el final de la tercera semana, y si usted no ha tomado ventaja ya, 4 00:00:19,020 --> 00:00:21,790 saben que habrá almuerzo este viernes, como de costumbre, donde 5 00:00:21,790 --> 00:00:25,430 se puede disfrutar de una buena conversación y la comida en Fire and Ice 6 00:00:25,430 --> 00:00:27,980 con algunos de CS50 de el personal y los compañeros de clase. 7 00:00:27,980 --> 00:00:30,170 Dirígete a esta URL aquí. 8 00:00:30,170 --> 00:00:33,420 >> Ahora usted puede recordar, o usted pronto puede estar familiarizado con, 9 00:00:33,420 --> 00:00:35,970 estas cosas aquí, que se dan al final 10 00:00:35,970 --> 00:00:37,850 del semestre para muchas clases. 11 00:00:37,850 --> 00:00:40,870 Libros azules El llamado examen, en el que usted escribe sus respuestas a los exámenes. 12 00:00:40,870 --> 00:00:44,240 Ahora tengo aquí 26 de tal libros azules, sobre cada uno de ellos 13 00:00:44,240 --> 00:00:47,580 se escribe un nombre, de la A a la Z. Y de hecho, los nombres son tan simples, A 14 00:00:47,580 --> 00:00:50,490 a la Z. Y uno de los objetivos en la mano hoy 15 00:00:50,490 --> 00:00:53,910 va a ser la de continuar lo empezamos el lunes, lo que no es 16 00:00:53,910 --> 00:00:57,830 tanto mirar el código, pero en realidad mirando ideas y la resolución de problemas. 17 00:00:57,830 --> 00:01:00,170 Una de las metas y promesas de este curso 18 00:01:00,170 --> 00:01:02,985 es que le enseñe a pensar más con cuidado, más metódicamente, 19 00:01:02,985 --> 00:01:05,400 y para resolver problemas de manera más eficiente. 20 00:01:05,400 --> 00:01:09,526 Y, de hecho, podemos hacer que realmente sin siquiera tocar una línea de código. 21 00:01:09,526 --> 00:01:12,150 Así que tengo un par de elefantes hasta hoy, naranja y azul, 22 00:01:12,150 --> 00:01:15,780 si pudiéramos conseguir un voluntario, tal vez desde más atrás de lo habitual. 23 00:01:15,780 --> 00:01:18,070 ¿Qué hay ahí, vamos hacia abajo. 24 00:01:18,070 --> 00:01:24,180 El objetivo de la cual va a ser a ayudar además administrar este examen aquí. 25 00:01:24,180 --> 00:01:24,935 Cuál es tu nombre? 26 00:01:24,935 --> 00:01:25,768 >> AUDIENCIA: Mary Beth. 27 00:01:25,768 --> 00:01:27,560 ALTAVOZ: Mary Beth, vamos arriba. 28 00:01:27,560 --> 00:01:29,560 A ver si el micrófono aquí para usted. 29 00:01:29,560 --> 00:01:32,172 30 00:01:32,172 --> 00:01:32,880 Encantada de conocerte. 31 00:01:32,880 --> 00:01:34,005 >> AUDIENCIA: Mucho gusto. 32 00:01:34,005 --> 00:01:36,790 ALTAVOZ: Muy bien, así que tengo aquí los libros azules de la A a la Z, 33 00:01:36,790 --> 00:01:41,680 y yo voy a pretender que Tengo uno de los estudiantes, 34 00:01:41,680 --> 00:01:45,770 y que van a venir en un tanto al azar al final de un bloque de examen de tres horas 35 00:01:45,770 --> 00:01:49,400 por lo que están terminando de alguna Para semi-aleatorio como éste. 36 00:01:49,400 --> 00:01:54,510 Ahora su trabajo en un momento va a ser-- esto es en realidad la forma en que obtienen 37 00:01:54,510 --> 00:01:56,820 convertido en al final de la clase, más probable. 38 00:01:56,820 --> 00:02:01,120 Su trabajo ahora va a ser, bastante simplemente, para ordenar estos libros azules para nosotros 39 00:02:01,120 --> 00:02:05,220 de la A a la Z. 40 00:02:05,220 --> 00:02:08,400 >> AUDIENCIA: Oh, esto es va a tener para siempre. 41 00:02:08,400 --> 00:02:13,747 >> ALTAVOZ: Y vamos a ver al hacer esto, no hay presión. 42 00:02:13,747 --> 00:02:15,330 AUDIENCIA: No, no hay presión ni nada. 43 00:02:15,330 --> 00:02:19,230 44 00:02:19,230 --> 00:02:23,570 >> ALTAVOZ: Y para la diversión, vamos a poner un temporizador. 45 00:02:23,570 --> 00:02:26,680 46 00:02:26,680 --> 00:02:28,700 >> AUDIENCIA: Muy divertido, muy divertido. 47 00:02:28,700 --> 00:02:36,741 48 00:02:36,741 --> 00:02:38,574 >> ALTAVOZ: Puedo sostener el micrófono para usted. 49 00:02:38,574 --> 00:02:40,240 Muy bien, acabamos duplicó nuestra velocidad. 50 00:02:40,240 --> 00:02:44,190 51 00:02:44,190 --> 00:02:49,060 Así que mientras tanto, permítanme plantear lo que es va a ser la pregunta para Mary Beth 52 00:02:49,060 --> 00:02:51,540 es lo que está haciendo, cómo es ella va sobre solucionar esto? 53 00:02:51,540 --> 00:02:54,040 Y, de hecho, puede que no tenga Ha pensado alguna vez acerca de algo 54 00:02:54,040 --> 00:02:57,440 tan simple como cuando usted escoge hasta 26 libros como éste, 55 00:02:57,440 --> 00:02:59,350 que no tienen un producto natural ordenando a ellos. 56 00:02:59,350 --> 00:03:01,335 ¿Cuál es el proceso de que en realidad se utiliza? 57 00:03:01,335 --> 00:03:03,770 Es bastante aleatorio sólo escoger el primero que se ve 58 00:03:03,770 --> 00:03:05,250 y ponerlo en su lugar? 59 00:03:05,250 --> 00:03:09,680 ¿Es primera vez que mueve sus manos alrededor de en busca de una continuación en busca de B? 60 00:03:09,680 --> 00:03:11,722 ¿Es usted echa un vistazo a una par de ellos al lado del otro 61 00:03:11,722 --> 00:03:14,680 y decir, espera un minuto, este no está bien, y luego intercambiar el orden? 62 00:03:14,680 --> 00:03:16,960 Vimos ya el lunes de que hay un número de maneras 63 00:03:16,960 --> 00:03:22,140 en el que podemos hacer esto, y de hecho, como nos acercamos al final aquí, 64 00:03:22,140 --> 00:03:26,360 Yo tomaría nota quizás de lo que Mary Beth está haciendo. 65 00:03:26,360 --> 00:03:30,040 Tenemos unos montones al parecer, un uno más grande, tres más pequeñas. 66 00:03:30,040 --> 00:03:33,790 67 00:03:33,790 --> 00:03:36,415 >> AUDIENCIA: yo les estoy ordenando cuando me encuentro con dos cartas 68 00:03:36,415 --> 00:03:39,540 que sé que están juntos en una secuencia, Los pongo juntos para que no lo hago 69 00:03:39,540 --> 00:03:42,915 tener que preocuparse de mantener pista de toda una fila de libros. 70 00:03:42,915 --> 00:03:45,706 Es sólo que, oh, A es primero, Tengo esta pila aquí. 71 00:03:45,706 --> 00:03:47,580 ALTAVOZ: Entonces, casi como piezas de un rompecabezas que 72 00:03:47,580 --> 00:03:49,860 tener la forma derecho a coincidir entre sí. 73 00:03:49,860 --> 00:03:51,026 AUDIENCIA: Más o menos, sí. 74 00:03:51,026 --> 00:03:55,320 ALTAVOZ: OK, excelente. 75 00:03:55,320 --> 00:03:59,850 Y ahora cada uno de estos pilas se ordenan presumiblemente? 76 00:03:59,850 --> 00:04:00,990 >> AUDIENCIA: Si. 77 00:04:00,990 --> 00:04:09,900 >> ALTAVOZ: Muy bien, de la A a la Z. Todos bien, felicidades, lo hicieron. 78 00:04:09,900 --> 00:04:11,461 Usted tiene su opción. 79 00:04:11,461 --> 00:04:11,960 Azul? 80 00:04:11,960 --> 00:04:13,530 Muy bien, gracias por eso. 81 00:04:13,530 --> 00:04:16,679 Así que Mary Beth se proponía lo que su enfoque era, 82 00:04:16,679 --> 00:04:19,720 pero lo que es otro enfoque de cómo podría ir sobre clasificación de estas cosas? 83 00:04:19,720 --> 00:04:21,130 ¿Qué habría hecho usted? 84 00:04:21,130 --> 00:04:24,060 El récord a batir habría sido un minuto y 50 segundos más o menos, 85 00:04:24,060 --> 00:04:26,039 además de los que más me olvidé de contar. 86 00:04:26,039 --> 00:04:27,080 ¿Qué habría hecho usted? 87 00:04:27,080 --> 00:04:27,579 ¿Sí? 88 00:04:27,579 --> 00:04:28,735 AUDIENCIA: Tome la pila. 89 00:04:28,735 --> 00:04:29,776 Comience desde el principio. 90 00:04:29,776 --> 00:04:32,284 Revise sus papeles. 91 00:04:32,284 --> 00:04:36,586 Y si el superior es mayor que, tal vez, que son, 92 00:04:36,586 --> 00:04:38,980 el inferior es más alto, entonces cámbielos. 93 00:04:38,980 --> 00:04:41,300 >> ALTAVOZ: OK, así que comenzar en la parte superior y la parte inferior, 94 00:04:41,300 --> 00:04:43,716 y luego su forma de trabajo hacia el interior de esa manera, el canje de ellos? 95 00:04:43,716 --> 00:04:46,580 OK, así que un poco parecido en espíritu al ordenamiento de burbuja, 96 00:04:46,580 --> 00:04:49,160 pero la elección de los extremos no los pares adyacentes. 97 00:04:49,160 --> 00:04:52,080 Sin embargo, el corto de él es que no sin duda un montón de diferentes maneras 98 00:04:52,080 --> 00:04:54,210 podríamos hacer esto, y Francamente, yo creo que tipo de 99 00:04:54,210 --> 00:04:55,700 adoptado un par de aproximaciones, ¿verdad? 100 00:04:55,700 --> 00:05:00,567 Usted ha hecho una especie de cuatro montones ordenados, y luego fusionado con eficacia. 101 00:05:00,567 --> 00:05:02,650 Y eso es, diría, otra técnica por completo. 102 00:05:02,650 --> 00:05:06,950 Usted no lo trata como una gran pila, que haya dividido el problema en cuatro quads, 103 00:05:06,950 --> 00:05:09,820 si se quiere, y entonces de alguna manera las fusionó en el final. 104 00:05:09,820 --> 00:05:13,410 >> Así que vamos a considerar, en última instancia, cómo más podemos hacer esto. 105 00:05:13,410 --> 00:05:15,860 Formalizamos la noción de ordenamiento de burbuja última vez, 106 00:05:15,860 --> 00:05:18,780 y ordenamiento de burbuja revocatorio era una algoritmo que visualizamos 107 00:05:18,780 --> 00:05:22,640 con ocho de sus compañeros de clase hasta aquí, aparentemente ordenados al azar al principio. 108 00:05:22,640 --> 00:05:26,110 Y entonces decidimos por parejas, si dos elementos están fuera de servicio, 109 00:05:26,110 --> 00:05:26,950 simplemente intercambiar. 110 00:05:26,950 --> 00:05:28,930 Así cuatro y dos son evidente su total improcedencia, 111 00:05:28,930 --> 00:05:31,080 por lo que estos dos compañeros de clase y cambió de posición. 112 00:05:31,080 --> 00:05:35,390 Y luego repetimos con cuatro y seis, a continuación, seis y ocho, en cada iteración, 113 00:05:35,390 --> 00:05:36,980 moviéndose hacia la derecha. 114 00:05:36,980 --> 00:05:42,590 >> Así que dado ocho personas, ¿cuántas parejas comparaciones Qué hice mientras caminaba desde 115 00:05:42,590 --> 00:05:45,220 izquierda a derecha en uno de tales iteración? 116 00:05:45,220 --> 00:05:48,410 ¿Cuántas comparaciones? 117 00:05:48,410 --> 00:05:49,197 Siete, ¿verdad? 118 00:05:49,197 --> 00:05:51,405 Porque si hay ocho personas, pero que tienen la pareja 119 00:05:51,405 --> 00:05:53,880 ellos y que se mantienen en movimiento un salto a la derecha, 120 00:05:53,880 --> 00:05:56,060 usted no va a tener ocho comparaciones porque no se puede comparar 121 00:05:56,060 --> 00:05:59,226 un elemento contra sí misma, o que lo haría sólo inútil, por lo que tiene siete. 122 00:05:59,226 --> 00:06:01,290 O, más generalmente, si tenemos n personas, que 123 00:06:01,290 --> 00:06:04,300 hacer N menos 1 comparaciones con ordenamiento de burbuja. 124 00:06:04,300 --> 00:06:08,150 >> Así que vamos a considerar ahora lo bueno o mal ordenamiento de burbuja en realidad era, y tratar 125 00:06:08,150 --> 00:06:13,570 para darnos vocabulario con que a los algoritmos de crítica como esta, 126 00:06:13,570 --> 00:06:14,430 y pronto nuestro propio. 127 00:06:14,430 --> 00:06:16,970 Así que el primer paso a través ordenamiento de burbuja, la primera vez 128 00:06:16,970 --> 00:06:20,909 Caminé de izquierda a derecha en la etapa, me n menos 1 comparaciones tomó. 129 00:06:20,909 --> 00:06:22,950 Y eso va a ser mi unidad de medida, ¿no? 130 00:06:22,950 --> 00:06:26,170 Yo estaba un poco hablando y paseando, algo rápido, algo lento, 131 00:06:26,170 --> 00:06:29,300 así que contando mi número de segundos no está particularmente revelador, 132 00:06:29,300 --> 00:06:32,260 pero contando el número de operaciones que hice el lunes, 133 00:06:32,260 --> 00:06:35,900 la comparación de dos personas, que se siente como una buena unidad de medida. 134 00:06:35,900 --> 00:06:40,980 >> Así n menos 1 pasos la primera vez, pero entonces, ¿qué pasó después? 135 00:06:40,980 --> 00:06:46,610 ¿Cuál es la ventaja de una sola pasada a través de una lista de otro modo sin clasificar? 136 00:06:46,610 --> 00:06:49,840 ¿Qué puedes decirme sobre el elemento que fue todo el camino por allí? 137 00:06:49,840 --> 00:06:51,300 ¿Sí? 138 00:06:51,300 --> 00:06:52,870 Ese fue el elemento más importante, ¿verdad? 139 00:06:52,870 --> 00:06:55,710 El número ocho, a pesar de que comenzado aquí, cada vez que 140 00:06:55,710 --> 00:06:57,860 su comparación contra un vecino, mantuvo 141 00:06:57,860 --> 00:07:00,480 burbujeando hacia la derecha lado de la lista. 142 00:07:00,480 --> 00:07:02,710 Y, en efecto, que es donde el algoritmo obtiene su nombre. 143 00:07:02,710 --> 00:07:07,630 >> Ahora por esa lógica, el número de comparaciones Necesito que hago en el segundo tiempo 144 00:07:07,630 --> 00:07:09,800 Hago que pase de izquierda a derecha? 145 00:07:09,800 --> 00:07:10,730 n menos 2, ¿verdad? 146 00:07:10,730 --> 00:07:14,297 Sería simplemente estar desperdiciando mi tiempo si mantener comparando ocho en contra de alguien 147 00:07:14,297 --> 00:07:16,630 más porque ya sabemos ella estaba en el lugar correcto. 148 00:07:16,630 --> 00:07:19,760 Así que eso es un poco de una optimización, por lo que el siguiente paso 149 00:07:19,760 --> 00:07:23,899 va a ser más n menos dos pasos, donde n es el número de personas. 150 00:07:23,899 --> 00:07:26,940 Ahora usted puede tipo de extrapolar, incluso si no eres un experto en informática, 151 00:07:26,940 --> 00:07:27,680 cómo esto termina. 152 00:07:27,680 --> 00:07:31,259 Al final de este algoritmo, presumiblemente usted tiene sólo una comparación izquierda. 153 00:07:31,259 --> 00:07:33,800 Usted tiene que fijar el tipo de a partir de la lista en caso de que dos 154 00:07:33,800 --> 00:07:36,540 y uno son fuera de servicio y debe ser uno y dos, 155 00:07:36,540 --> 00:07:40,330 por lo que este toque fondo en más 1 comparación final. 156 00:07:40,330 --> 00:07:44,500 >> Ahora el punto, punto, punto tipo de ondas es manos de algunos de los detalles más jugosos, 157 00:07:44,500 --> 00:07:46,452 pero vamos a seguir adelante y simplificar. 158 00:07:46,452 --> 00:07:48,660 Si usted recuerda de alta escuela, francamente, muchos de ustedes 159 00:07:48,660 --> 00:07:50,340 tenido libros de matemáticas que tenían una hoja de trucos poco 160 00:07:50,340 --> 00:07:52,550 en la portada o la contraportada que mostraba 161 00:07:52,550 --> 00:07:56,400 sumas lo de la serie como esta última instancia, añadió haciendo. 162 00:07:56,400 --> 00:07:59,600 En el caso general, si tiene un variable como la n, y de hecho éste, 163 00:07:59,600 --> 00:08:01,634 si uno mira a su libro de matemáticas de la vieja escuela, 164 00:08:01,634 --> 00:08:04,050 verías que esta realidad se suma a esta suma aquí, 165 00:08:04,050 --> 00:08:07,970 n veces n menos 1 todo dividido por 2. 166 00:08:07,970 --> 00:08:11,172 Así que por ahora permítanme estipulo esto es cierto, por lo que en un acto de fe, 167 00:08:11,172 --> 00:08:12,880 eso es lo que esto resume hasta, y pudimos 168 00:08:12,880 --> 00:08:14,341 demostrar que en un caso más general. 169 00:08:14,341 --> 00:08:15,590 Pero ahora vamos a ampliar esto. 170 00:08:15,590 --> 00:08:19,920 Así que vamos a multiplicar esto, así que eso es n al cuadrado, menos n, todo dividido por 2. 171 00:08:19,920 --> 00:08:23,200 Eso es realmente n al cuadrado, dividido por 2, menos n sobre 2, 172 00:08:23,200 --> 00:08:25,010 así que eso es todo lo agradable e interesante. 173 00:08:25,010 --> 00:08:27,060 Pero, ¿qué pasa si nos ahora plug-in de un valor? 174 00:08:27,060 --> 00:08:29,724 Supongamos que yo no tenía ocho personas, pero dicen que un millón. 175 00:08:29,724 --> 00:08:31,890 Y un millón sólo porque que es un número bastante grande, 176 00:08:31,890 --> 00:08:34,039 vamos a conectar que en y ver qué pasa. 177 00:08:34,039 --> 00:08:39,039 Así que si conecto un millón en esa fórmula Voy a conseguir un millón de cuadrado, 178 00:08:39,039 --> 00:08:42,868 dividido por 2, menos una millones, dividido entre 2. 179 00:08:42,868 --> 00:08:44,159 Ahora ¿qué es eso va a ser igual? 180 00:08:44,159 --> 00:08:47,354 Así que 500 mil millones, menos de 500.000. 181 00:08:47,354 --> 00:08:49,270 Y si hago realmente que las matemáticas, significa que 182 00:08:49,270 --> 00:08:53,920 que la clasificación de un millón de las personas con el ordenamiento de burbuja 183 00:08:53,920 --> 00:09:01,800 me podría tomar 499999500000 pasos o comparaciones en el final, 184 00:09:01,800 --> 00:09:02,900 sólo estamos extrapolando. 185 00:09:02,900 --> 00:09:06,860 >> Eso se siente bastante lento, pero, francamente, medición de una entrada particular, 186 00:09:06,860 --> 00:09:09,160 así, no es todo lo que elocuente. 187 00:09:09,160 --> 00:09:14,050 Pero de hecho, sí sugiere que a medida que n se hace más grande y más grande, este algoritmo 188 00:09:14,050 --> 00:09:16,280 tipo de se siente peor y peor, o que realmente 189 00:09:16,280 --> 00:09:20,450 empezar a sentir el dolor de esa exponenciación, que n al cuadrado, 190 00:09:20,450 --> 00:09:21,770 que añade bastante rápido. 191 00:09:21,770 --> 00:09:25,340 Y este detalle no es perdido en las personas, de hecho, 192 00:09:25,340 --> 00:09:29,640 Hace algunos años un cierto senador que era campaña, se sentó para una entrevista 193 00:09:29,640 --> 00:09:32,180 con Eric de Google Schmidt, CEO de la época, 194 00:09:32,180 --> 00:09:36,380 y fue puesta en duda con una pregunta al igual que estamos explorando hoy. 195 00:09:36,380 --> 00:09:38,468 Vamos a echar un vistazo. 196 00:09:38,468 --> 00:09:45,280 >> [REPRODUCCIÓN DE VÍDEO] 197 00:09:45,280 --> 00:09:48,560 >> -Senador, Estás aquí en Google, y me gusta 198 00:09:48,560 --> 00:09:53,382 pensar en la presidencia como una entrevista de trabajo. 199 00:09:53,382 --> 00:09:56,434 Ahora, es difícil conseguir un trabajo como presidente, 200 00:09:56,434 --> 00:09:58,100 y usted va a través de los rigores ahora. 201 00:09:58,100 --> 00:10:01,860 También es difícil de conseguir un trabajo en Google. 202 00:10:01,860 --> 00:10:05,490 Tenemos preguntas, y nos pedir a nuestras preguntas de los candidatos, 203 00:10:05,490 --> 00:10:09,770 y éste es de Larry Schwimmer. 204 00:10:09,770 --> 00:10:14,760 Que-- que ustedes piensan que soy es broma, está justo aquí. 205 00:10:14,760 --> 00:10:17,930 ¿Cuál es la forma más eficiente de ordenar un millón de enteros de 32 bits? 206 00:10:17,930 --> 00:10:21,800 207 00:10:21,800 --> 00:10:24,350 >> -Well-- 208 00:10:24,350 --> 00:10:25,200 >> -Lo Siento, tal vez-- 209 00:10:25,200 --> 00:10:27,400 >> No, no, no. 210 00:10:27,400 --> 00:10:30,700 Creo que el ordenamiento de burbuja sería el camino equivocado. 211 00:10:30,700 --> 00:10:34,165 212 00:10:34,165 --> 00:10:38,180 >> Vamos, que le dijo eso? 213 00:10:38,180 --> 00:10:40,590 No vi ordenador la ciencia en su fondo. 214 00:10:40,590 --> 00:10:42,130 >> -Tenemos Nuestros espías en allí. 215 00:10:42,130 --> 00:10:44,930 216 00:10:44,930 --> 00:10:48,444 >> -OK, Vamos a pedir una diferente pregunta de la entrevista. 217 00:10:48,444 --> 00:10:49,300 >> [FIN REPRODUCCIÓN DE VÍDEO] 218 00:10:49,300 --> 00:10:52,290 >> ALTAVOZ: Así que hablando de números específicos aunque, 219 00:10:52,290 --> 00:10:53,890 no va a ser tan útil. 220 00:10:53,890 --> 00:10:56,810 No es una lección de vida que la burbuja especie, dado un millón de entradas, 221 00:10:56,810 --> 00:10:58,590 podría tomar hasta 500 mil millones pasos. 222 00:10:58,590 --> 00:11:01,120 Realmente no se puede generalizar demasiado eficazmente a partir de ese 223 00:11:01,120 --> 00:11:03,560 y tomar buenas decisiones de diseño al escribir programas. 224 00:11:03,560 --> 00:11:07,070 Así que vamos a centrarnos aunque sobre cómo podemos simplificar este resultado. 225 00:11:07,070 --> 00:11:11,780 >> Así que he resaltado en amarillo aquí el resultado de n al cuadrado dividida por 2, 226 00:11:11,780 --> 00:11:14,330 por lo que un millones cuadrado dividido por 2, y luego 227 00:11:14,330 --> 00:11:16,710 He destacado lo la respuesta final fue 228 00:11:16,710 --> 00:11:20,180 una vez que restamos off n dividido por 2. 229 00:11:20,180 --> 00:11:24,850 Y la afirmación de que voy a hacer ahora es, quién diablos le importa si se resta de 230 00:11:24,850 --> 00:11:30,060 un poco más de 2 n edad cuando la primera parte de esta fórmula es mucho más grande? 231 00:11:30,060 --> 00:11:33,910 Domina el otro plazo, n al cuadrado dividido por 2 232 00:11:33,910 --> 00:11:37,510 es mucho más grande, con claridad, como n se hace grande como un millón, 233 00:11:37,510 --> 00:11:41,450 esto es realmente una gran diferencia en el final de la día entre 500 mil millones 234 00:11:41,450 --> 00:11:45,730 y 499 999 500 000? 235 00:11:45,730 --> 00:11:46,349 En realidad no. 236 00:11:46,349 --> 00:11:48,640 Y así lo vamos a hacer como científicos de la computación es 237 00:11:48,640 --> 00:11:53,270 ignorar los términos de orden inferior y tomar algo como esto y realmente 238 00:11:53,270 --> 00:11:56,050 sólo simplificar al término que se va a importar. 239 00:11:56,050 --> 00:12:00,315 Los más grandes de nuestros conjuntos de datos consiguen, más grande nuestras bases de datos reciben, más páginas web 240 00:12:00,315 --> 00:12:02,690 tenemos que buscar, más amigos que tienen en Facebook. 241 00:12:02,690 --> 00:12:07,340 >> Como n se hace más grande, estamos muy va a preocuparse por el más grande 242 00:12:07,340 --> 00:12:11,560 plazo en cualquier tipo de análisis de nuestro desempeño algoritmos. 243 00:12:11,560 --> 00:12:16,230 Y yo voy a decir, sabes qué, ordenamiento de burbuja está en el orden de la gran O, 244 00:12:16,230 --> 00:12:18,060 del orden de n al cuadrado. 245 00:12:18,060 --> 00:12:20,090 No es exactamente n al cuadrado, como hemos visto, 246 00:12:20,090 --> 00:12:22,060 pero a quién le importa sobre los plazos más pequeños, 247 00:12:22,060 --> 00:12:24,390 y, francamente, que realmente le importa si dividimos por 2? 248 00:12:24,390 --> 00:12:25,870 Eso es sólo un factor constante. 249 00:12:25,870 --> 00:12:29,480 Y es de 500 mil millones contra 250 millones realmente tan grande de un acuerdo? 250 00:12:29,480 --> 00:12:32,190 Yo sólo podía esperar un año, dejar que mi laptop literalmente 251 00:12:32,190 --> 00:12:34,810 obtener el doble de rápido en el hardware, y ese tipo de diferencia 252 00:12:34,810 --> 00:12:36,650 simplemente desaparece de forma natural con el tiempo. 253 00:12:36,650 --> 00:12:39,300 >> Lo que nos importa es la expresión, la parte 254 00:12:39,300 --> 00:12:42,489 de la expresión que va a variar como nuestra entrada se hace más grande y más grande. 255 00:12:42,489 --> 00:12:45,280 Y de hecho, en el mundo real, eso es lo que está pasando cada vez más 256 00:12:45,280 --> 00:12:48,330 es las entradas a nuestros problemas y algoritmos son cada vez más grande. 257 00:12:48,330 --> 00:12:53,470 Tan grande O va a ser la notación, la notación asintótica, que acabamos de 258 00:12:53,470 --> 00:12:57,160 utilizar como científicos de la computación para describir el rendimiento, o el tiempo de ejecución, 259 00:12:57,160 --> 00:12:58,130 de un algoritmo. 260 00:12:58,130 --> 00:13:00,800 Así que podemos comparar algoritmos en equipos diferentes escritos 261 00:13:00,800 --> 00:13:04,170 por diferentes personas, utilizando alguna métrica fundamentalmente similar 262 00:13:04,170 --> 00:13:07,557 como el número de comparaciones que eres hacer, o tal vez el número de swaps 263 00:13:07,557 --> 00:13:08,140 usted está haciendo. 264 00:13:08,140 --> 00:13:11,910 >> Lo que no vamos a recuento es la cantidad de tiempo 265 00:13:11,910 --> 00:13:13,981 que pasa en el reloj en la pared normalmente. 266 00:13:13,981 --> 00:13:16,230 Lo que no vamos a preocuparnos acerca es la cantidad de memoria 267 00:13:16,230 --> 00:13:17,820 está utilizando hoy en menos, aunque eso es 268 00:13:17,820 --> 00:13:19,370 otro recurso que podríamos medir. 269 00:13:19,370 --> 00:13:23,610 Vamos a tratar de basar nuestro análisis sólo en las operaciones básicas, los que, 270 00:13:23,610 --> 00:13:25,930 francamente, que se puede ver más visualmente. 271 00:13:25,930 --> 00:13:30,700 Así que con algo así como gran O de n cuadrado, afirmo que O de n al cuadrado 272 00:13:30,700 --> 00:13:35,820 es un límite superior en la llamada momento de la burbuja de tipo corriente. 273 00:13:35,820 --> 00:13:38,820 En otras palabras, si usted quería decir que hay 274 00:13:38,820 --> 00:13:41,370 este límite superior de la cantidad de los pasos de un algoritmo puede tomar, 275 00:13:41,370 --> 00:13:46,240 que va a estar en el gran O de n cuadrado en este caso, un límite superior. 276 00:13:46,240 --> 00:13:49,710 >> ¿Qué pasa si en vez cambio el historia sea no se trata de una especie de burbuja, 277 00:13:49,710 --> 00:13:50,910 pero sobre este límite superior. 278 00:13:50,910 --> 00:13:54,030 ¿Puedes pensar en un algoritmo que hemos visto en ya 279 00:13:54,030 --> 00:13:59,530 cuyo límite superior, máximo medir el tiempo o las operaciones, 280 00:13:59,530 --> 00:14:04,300 se dice que está acotada por n, una función lineal, 281 00:14:04,300 --> 00:14:07,260 no una cuadrática que es curvo? 282 00:14:07,260 --> 00:14:10,780 ¿Qué es un algoritmo que Siempre toma no más 283 00:14:10,780 --> 00:14:12,860 que como n pasos, o Pasos 2n, 3n o pasos? 284 00:14:12,860 --> 00:14:13,360 ¿Sí? 285 00:14:13,360 --> 00:14:15,030 >> AUDIENCIA: Encontrar el mayor número en una lista? 286 00:14:15,030 --> 00:14:16,930 >> ALTAVOZ: Perfect, la búsqueda de el mayor número en una lista. 287 00:14:16,930 --> 00:14:18,940 Si me dan una lista de personas, por ejemplo, 288 00:14:18,940 --> 00:14:21,440 cada uno de que es la celebración de una serie, ¿cuál es el número máximo 289 00:14:21,440 --> 00:14:23,770 de medidas que debería llevarme, una persona razonablemente inteligente, 290 00:14:23,770 --> 00:14:27,530 encontrar a la persona más grande en esa lista? 291 00:14:27,530 --> 00:14:28,100 n, ¿verdad? 292 00:14:28,100 --> 00:14:31,320 Debido a que en el peor de los casos, donde podría ser el mayor valor? 293 00:14:31,320 --> 00:14:32,700 Cierto, todo el camino al final. 294 00:14:32,700 --> 00:14:34,575 Así que en el peor de los casos límite superior, que podría 295 00:14:34,575 --> 00:14:36,450 tener que ir todo el camino aquí y ser como, 296 00:14:36,450 --> 00:14:39,170 oh, aquí está el número ocho, o lo que sea que el valor es. 297 00:14:39,170 --> 00:14:41,330 Ahora sólo sería estúpido si lo seguía haciendo, ¿verdad? 298 00:14:41,330 --> 00:14:43,840 ¿Estás buscando más y más elementos si el último de ellos es de allí? 299 00:14:43,840 --> 00:14:45,340 Así que sin duda, n es un límite superior. 300 00:14:45,340 --> 00:14:47,420 Yo no necesito tomar más pasos que eso. 301 00:14:47,420 --> 00:14:51,580 >> Entonces, ¿qué si en vez propuse que existen algoritmos en este mundo que 302 00:14:51,580 --> 00:14:57,750 tienen un tiempo de ejecución que es delimitada por gran O de log n, log n? 303 00:14:57,750 --> 00:15:00,390 ¿Dónde hemos visto esto antes? 304 00:15:00,390 --> 00:15:00,890 ¿Sí? 305 00:15:00,890 --> 00:15:03,309 >> AUDIENCIA: En el problema de guía telefónica? 306 00:15:03,309 --> 00:15:04,850 ALTAVOZ: Al igual que el problema de la guía telefónica. 307 00:15:04,850 --> 00:15:07,754 ¿Cuál fue la medida de la mucho tiempo o cuántas lágrimas de TI 308 00:15:07,754 --> 00:15:10,170 me llevó a encontrar a alguien como Mike Smith en la guía telefónica? 309 00:15:10,170 --> 00:15:13,212 Nos decía que era log n, y incluso si desconocido o que es 310 00:15:13,212 --> 00:15:15,170 un poco nebulosa qué logaritmo o exponente fue, 311 00:15:15,170 --> 00:15:17,650 sólo recuerda que log n generalmente se refiere al proceso, 312 00:15:17,650 --> 00:15:20,790 en este caso, de dividir algo en la mitad otra vez, y otra vez, 313 00:15:20,790 --> 00:15:25,790 y otra vez, y otra vez, de manera que obtiene cada vez más pequeña a medida que hace eso. 314 00:15:25,790 --> 00:15:28,470 >> Así que ingrese de n se refiere, claro, al ejemplo de guía telefónica, 315 00:15:28,470 --> 00:15:32,662 para búsqueda binaria en teoría, cuando tenía las puertas virtuales en el tablero, 316 00:15:32,662 --> 00:15:34,370 o cuando Sean era buscando algo. 317 00:15:34,370 --> 00:15:37,374 Si se hubiera utilizado de búsqueda binaria, log n sería el límite superior de la cantidad 318 00:15:37,374 --> 00:15:38,040 tiempo que toma. 319 00:15:38,040 --> 00:15:44,027 Pero esos algoritmos que corrían en log n asumido lo detalle clave? 320 00:15:44,027 --> 00:15:45,360 Que la lista se solucionó, ¿verdad? 321 00:15:45,360 --> 00:15:47,789 Su algoritmo es malo si su entrada no está ordenada, 322 00:15:47,789 --> 00:15:49,830 y sin embargo está utilizando algo así como búsqueda binaria 323 00:15:49,830 --> 00:15:51,704 ya que podría saltar derecho sobre el elemento 324 00:15:51,704 --> 00:15:53,600 sin darse cuenta de que es de hecho allí. 325 00:15:53,600 --> 00:15:55,600 >> Ahora, ¿qué podría significar esto, gran O de uno? 326 00:15:55,600 --> 00:15:59,117 Esto no quiere decir que su algoritmo tiene una y sólo una etapa, 327 00:15:59,117 --> 00:16:01,200 sólo significa que se necesita un número constante de pasos. 328 00:16:01,200 --> 00:16:04,060 Tal vez sea 1, tal vez es 10, tal vez es 1000, 329 00:16:04,060 --> 00:16:07,750 pero es independiente de el tamaño del problema. 330 00:16:07,750 --> 00:16:10,850 No importa qué tan grande es n, un algoritmo de constante de tiempo 331 00:16:10,850 --> 00:16:12,747 siempre tiene el mismo número de pasos. 332 00:16:12,747 --> 00:16:15,080 Entonces, ¿qué podría ser un algoritmo hemos hablado o simplemente 333 00:16:15,080 --> 00:16:20,418 intuitivamente que viene a usted que siempre se ejecuta en la llamada constante de tiempo? 334 00:16:20,418 --> 00:16:20,918 ¿Sí? 335 00:16:20,918 --> 00:16:22,001 >> AUDIENCIA: Añadir dos números. 336 00:16:22,001 --> 00:16:25,320 ALTAVOZ: Añadir dos números, 2 más 2 es igual a 4, hecho. 337 00:16:25,320 --> 00:16:27,227 Así que podría funcionar, ¿qué más? 338 00:16:27,227 --> 00:16:28,560 ¿Qué tal mundo más real, ¿no? 339 00:16:28,560 --> 00:16:30,686 >> AUDIENCIA: Encontrar el a primera hora de la lista. 340 00:16:30,686 --> 00:16:32,810 ALTAVOZ: Encontrar a la primera elemento en una lista, seguro. 341 00:16:32,810 --> 00:16:34,540 En realidad hemos estado hablando acerca de las matrices ya, 342 00:16:34,540 --> 00:16:36,540 ¿Cómo se llega a la primer elemento de una matriz, 343 00:16:36,540 --> 00:16:40,465 no importa cuánto tiempo la array es en código C? 344 00:16:40,465 --> 00:16:43,090 Usted sólo tiene que utilizar como el soporte notación cero, bam, estás allí. 345 00:16:43,090 --> 00:16:46,120 Y de hecho, matrices, como un aparte, apoyo algo generalmente conocido 346 00:16:46,120 --> 00:16:49,240 como acceso aleatorio, de acceso aleatorio memoria, porque usted puede literalmente 347 00:16:49,240 --> 00:16:50,284 saltar a cualquier lugar. 348 00:16:50,284 --> 00:16:52,700 Podemos hacer esto aún más simple podemos rebobinar hasta la semana cero 349 00:16:52,700 --> 00:16:53,900 cuando hicimos los arañazos. 350 00:16:53,900 --> 00:16:59,707 ¿Cuánto tiempo se necesita para que la dicen bloque en Scratch para ejecutar? 351 00:16:59,707 --> 00:17:00,790 Sólo la constante de tiempo, ¿verdad? 352 00:17:00,790 --> 00:17:03,960 Di algo, di algo, no importa 353 00:17:03,960 --> 00:17:07,359 cómo grandes rasguños mundo es, siempre es va a tomar la misma cantidad de tiempo 354 00:17:07,359 --> 00:17:08,490 decir simplemente algo. 355 00:17:08,490 --> 00:17:11,089 >> Así que esa es la constante de tiempo, pero ¿cuál es la otra cara? 356 00:17:11,089 --> 00:17:13,030 Si eso era superior límites, lo que si queremos 357 00:17:13,030 --> 00:17:17,089 para describir los límites inferiores de nuestros algoritmos de tiempo de ejecución? 358 00:17:17,089 --> 00:17:19,852 Casi un mejor caso potencialmente, si se quiere, 359 00:17:19,852 --> 00:17:23,060 aunque estos términos pueden aplicarse a mejor casos, los peores casos, los casos promedio más 360 00:17:23,060 --> 00:17:26,359 en general, pero vamos a concentrarnos en cotas inferiores en términos más generales. 361 00:17:26,359 --> 00:17:31,920 ¿Qué es un algoritmo que tiene una cota inferior de n pasos, 362 00:17:31,920 --> 00:17:33,350 o pasos 2n, 3n o pasos? 363 00:17:33,350 --> 00:17:36,241 Algunos de factor de n pasos, ese es su límite inferior. 364 00:17:36,241 --> 00:17:36,740 ¿Sí? 365 00:17:36,740 --> 00:17:37,910 >> AUDIENCIA: ordenamiento de burbuja? 366 00:17:37,910 --> 00:17:41,610 >> ALTAVOZ: ordenamiento de burbuja toma que mínimamente n pasos, ¿por qué? 367 00:17:41,610 --> 00:17:42,279 Porqué es eso? 368 00:17:42,279 --> 00:17:45,320 ¿Por qué ese comienzo para ir a vosotros intuitivamente, incluso si lo hace, no sólo 369 00:17:45,320 --> 00:17:46,530 todavía? 370 00:17:46,530 --> 00:17:47,030 ¿Sí? 371 00:17:47,030 --> 00:17:47,990 >> AUDIENCIA: [inaudible]. 372 00:17:47,990 --> 00:17:51,652 373 00:17:51,652 --> 00:17:52,360 ALTAVOZ: Exactamente. 374 00:17:52,360 --> 00:17:55,810 En el mejor escenario posible de ordenamiento de burbuja, y una gran cantidad de algoritmos, 375 00:17:55,810 --> 00:17:58,769 si te entrego ocho personas que ya están ordenados, 376 00:17:58,769 --> 00:18:00,560 sería absurdo para usted, el algoritmo, 377 00:18:00,560 --> 00:18:02,202 para ir hacia atrás y adelante más de una vez, ¿no? 378 00:18:02,202 --> 00:18:04,285 Porque tan pronto como se caminar a través de la lista una vez, 379 00:18:04,285 --> 00:18:08,090 usted debe darse cuenta, oh, no hice ningún swaps, esta lista está ordenada, salida. 380 00:18:08,090 --> 00:18:09,700 Pero eso va a tomar usted n pasos. 381 00:18:09,700 --> 00:18:12,033 >> Y a la inversa, lo que es otra forma de pensar al respecto? 382 00:18:12,033 --> 00:18:15,240 Ordenamiento de burbuja es un omega, por así decirlo, de n, 383 00:18:15,240 --> 00:18:19,050 porque si nos fijamos en menos de n elementos, lo que 384 00:18:19,050 --> 00:18:23,009 es la cuestión fundamental que hay? 385 00:18:23,009 --> 00:18:24,550 No sabes si es ordenada, correcta. 386 00:18:24,550 --> 00:18:26,800 Nosotros los humanos podrían vistazo a las ocho personas y ser como, oh, está ordenada, 387 00:18:26,800 --> 00:18:28,430 que no me n medidas tomó, pero lo hicieron. 388 00:18:28,430 --> 00:18:30,810 Sus ojos, a pesar de que tipo de tener un gran campo de visión, 389 00:18:30,810 --> 00:18:33,184 miraste ocho elementos, miraste a ocho personas, 390 00:18:33,184 --> 00:18:34,610 eso es ocho pasos con eficacia. 391 00:18:34,610 --> 00:18:38,612 Y sólo si camino a través de todo lista ¿Me doy cuenta, sí, ordenados. 392 00:18:38,612 --> 00:18:41,320 Si me detengo a mitad de camino de pensar, todo derecho, que es bastante ordenadas hasta el momento, 393 00:18:41,320 --> 00:18:42,520 ¿cuáles son las probabilidades de que no está ordenada? 394 00:18:42,520 --> 00:18:44,186 Eso no va a haber algoritmos correctos. 395 00:18:44,186 --> 00:18:46,250 Podría ser más rápido, pero incorrecta. 396 00:18:46,250 --> 00:18:48,500 >> Así que ahora tenemos una manera de describiendo una menor grada, 397 00:18:48,500 --> 00:18:49,710 y ¿qué pasa con la constante de tiempo? 398 00:18:49,710 --> 00:18:54,565 ¿Qué es un algoritmo que tiene un menor con destino en su tiempo de ejecución de uno? 399 00:18:54,565 --> 00:18:58,350 1 etapa, 2 etapas, 10 pasos, pero constante, independiente de n, 400 00:18:58,350 --> 00:18:59,310 el tamaño de la entrada? 401 00:18:59,310 --> 00:19:03,930 402 00:19:03,930 --> 00:19:04,600 Sí, en la parte trasera. 403 00:19:04,600 --> 00:19:05,309 >> AUDIENCIA: Printf? 404 00:19:05,309 --> 00:19:06,183 ALTAVOZ: ¿Qué es eso? 405 00:19:06,183 --> 00:19:07,184 AUDIENCIA: Printf? 406 00:19:07,184 --> 00:19:07,850 ALTAVOZ: Printf. 407 00:19:07,850 --> 00:19:08,400 Bueno, seguro. 408 00:19:08,400 --> 00:19:10,720 Así que se necesita un número fijo de pasos. 409 00:19:10,720 --> 00:19:13,170 Y debería ahora-- ahora que estamos hablando de código C 410 00:19:13,170 --> 00:19:16,040 y no Scratch, algo como por ejemplo, con printf, 411 00:19:16,040 --> 00:19:17,710 deberíamos empezar a tener cuidado. 412 00:19:17,710 --> 00:19:21,090 Debido printf embargo, toma de entrada, que es una cadena, 413 00:19:21,090 --> 00:19:23,220 y las cuerdas no tienen técnicamente longitud. 414 00:19:23,220 --> 00:19:25,530 Así que si ahora queremos recoger en ti, si no te importa, 415 00:19:25,530 --> 00:19:29,430 técnicamente podríamos argumentar que printf no tener una entrada de longitud variable, 416 00:19:29,430 --> 00:19:32,270 y seguramente puede ser que tome más tiempo para imprimir una cadena de este largo, 417 00:19:32,270 --> 00:19:33,560 de este largo. 418 00:19:33,560 --> 00:19:36,570 >> ¿Y qué si tenemos en cuenta sólo el clasificación y búsqueda ejemplos? 419 00:19:36,570 --> 00:19:40,450 ¿Qué pasa con Mike Smith en el teléfono libro, o de búsqueda binaria más general? 420 00:19:40,450 --> 00:19:42,220 En el mejor de los casos, lo que podría suceder? 421 00:19:42,220 --> 00:19:45,577 Abro la guía telefónica y, bam, hay número de Mike Smith. 422 00:19:45,577 --> 00:19:46,660 Yo le puedo llamar de inmediato. 423 00:19:46,660 --> 00:19:49,390 >> Tomó un paso, tal vez dos pasos, pero un número constante de pasos 424 00:19:49,390 --> 00:19:50,230 si tuve suerte. 425 00:19:50,230 --> 00:19:52,570 Y, francamente, que vimos en Lunes a su compañera de clase 426 00:19:52,570 --> 00:19:54,710 conseguir bastante suerte dos veces seguidas. 427 00:19:54,710 --> 00:19:57,050 Y eso fue hecho constante vez en unos bajos límites 428 00:19:57,050 --> 00:20:01,280 en el algoritmo en cuestión para encontrar el número 50 detrás de las cerradas 429 00:20:01,280 --> 00:20:01,830 puertas. 430 00:20:01,830 --> 00:20:06,400 >> Ahora, como un aparte, si descubre que tanto la gran O, el límite superior, 431 00:20:06,400 --> 00:20:09,310 y el omega, el límite inferior, son uno en el mismo, que 432 00:20:09,310 --> 00:20:11,830 es la misma fórmula en paréntesis, también puede 433 00:20:11,830 --> 00:20:15,170 decir, sólo para ser de lujo, que hay algo en zeta 434 00:20:15,170 --> 00:20:18,270 de n theta o de algún otro valor. 435 00:20:18,270 --> 00:20:20,661 Eso sólo significa que cuando grande O y omega son los mismos. 436 00:20:20,661 --> 00:20:21,910 Ahora ¿qué pasa con la selección especie? 437 00:20:21,910 --> 00:20:23,400 Vamos a utilizar este nuevo vocabulario. 438 00:20:23,400 --> 00:20:27,407 En la selección de clasificación, lo que eran haciendo de nuevo, y otra vez, y otra vez? 439 00:20:27,407 --> 00:20:29,990 Yo iba hacia atrás y adelante a través de la lista, en busca de quién? 440 00:20:29,990 --> 00:20:33,260 441 00:20:33,260 --> 00:20:34,730 El número más pequeño. 442 00:20:34,730 --> 00:20:37,560 >> Entonces, ¿cómo muchos pasos, cómo muchas comparaciones hicieron I 443 00:20:37,560 --> 00:20:43,250 tener que hacer con el fin de averiguar quién el elemento más pequeño de la lista era? 444 00:20:43,250 --> 00:20:44,437 n menos 1, ¿no? 445 00:20:44,437 --> 00:20:47,770 Porque si acabo de empezar con el que estoy dado y yo le pongo a comparar, 446 00:20:47,770 --> 00:20:49,519 entonces él o ella, le o ella, él o ella, 447 00:20:49,519 --> 00:20:52,010 sólo puede emparejar elementos juntos n menos 1 veces. 448 00:20:52,010 --> 00:20:55,630 Así selección tiene especie de manera similar n menos 1 pasos la primera vez. 449 00:20:55,630 --> 00:20:59,540 >> ¿Cuántos pasos que me lleve a encontrar el segundo elemento más pequeño? 450 00:20:59,540 --> 00:21:02,920 n menos 2, porque estoy siendo tonto si sigo mirando las mismas personas 451 00:21:02,920 --> 00:21:06,280 de nuevo si he ya lo seleccionado o ella y los puso en su lugar. 452 00:21:06,280 --> 00:21:09,270 Y el tercer paso, n menos 3, entonces n menos 4. 453 00:21:09,270 --> 00:21:11,020 Hemos visto este patrón antes, y de hecho 454 00:21:11,020 --> 00:21:13,460 Selección de tipo similar tiene un límite superior 455 00:21:13,460 --> 00:21:16,210 de n al cuadrado si hacemos esa suma. 456 00:21:16,210 --> 00:21:19,790 ¿Cuál es su límite inferior, la selección especie? 457 00:21:19,790 --> 00:21:25,350 Como mínimo, la cantidad de tiempo de selección debe ordenar tomar, como lo definimos el lunes? 458 00:21:25,350 --> 00:21:29,370 459 00:21:29,370 --> 00:21:30,490 Proponer dos opciones. 460 00:21:30,490 --> 00:21:32,360 Tal vez sea n, como antes. 461 00:21:32,360 --> 00:21:35,040 A lo mejor es n al cuadrado, ya que es ahora como el límite superior. 462 00:21:35,040 --> 00:21:35,874 >> AUDIENCIA: n al cuadrado. 463 00:21:35,874 --> 00:21:36,664 ALTAVOZ: n al cuadrado. 464 00:21:36,664 --> 00:21:37,368 ¿Por qué? 465 00:21:37,368 --> 00:21:40,060 >> AUDIENCIA: Debido a que tiene para definir [inaudible]. 466 00:21:40,060 --> 00:21:41,510 >> ALTAVOZ: Exactamente. 467 00:21:41,510 --> 00:21:45,077 Al menos en lo definí ordenamiento por selección era bastante ingenua, seguir adelante, 468 00:21:45,077 --> 00:21:46,160 encontrar el elemento más pequeño. 469 00:21:46,160 --> 00:21:47,770 Ir de nuevo, encontrar el elemento más pequeño. 470 00:21:47,770 --> 00:21:49,490 Ir de nuevo, encontrar el elemento más pequeño. 471 00:21:49,490 --> 00:21:51,700 No hay ninguna clase de optimización de ahí que 472 00:21:51,700 --> 00:21:54,350 podría dejarme abortar después sólo n o menos pasos. 473 00:21:54,350 --> 00:21:57,080 Así que de hecho, la selección tipo, omega de n al cuadrado. 474 00:21:57,080 --> 00:22:00,667 >> ¿Qué pasa con la ordenación por inserción, donde tomé que me dieron, y entonces yo le dejé 475 00:22:00,667 --> 00:22:01,750 o ella en el lugar correcto? 476 00:22:01,750 --> 00:22:04,958 Entonces procedí a la segunda persona, él o ella se dejó caer en el lugar correcto. 477 00:22:04,958 --> 00:22:07,910 Entonces la siguiente persona, se dejó él o ella en el lugar correcto. 478 00:22:07,910 --> 00:22:10,537 Tenga en cuenta que esto es muy lineales, por así decirlo. 479 00:22:10,537 --> 00:22:12,620 Soy una línea recta, estoy no ir y venir, 480 00:22:12,620 --> 00:22:16,080 Nunca mirar hacia atrás en realidad, pero lo que está sucediendo cuando lo introduzco 481 00:22:16,080 --> 00:22:20,302 o ella en el comienzo de la lista como lo hicimos el lunes? 482 00:22:20,302 --> 00:22:21,010 Lo que está sucediendo? 483 00:22:21,010 --> 00:22:21,510 ¿Sí? 484 00:22:21,510 --> 00:22:23,122 AUDIENCIA: [inaudible]. 485 00:22:23,122 --> 00:22:24,830 ALTAVOZ: Sí, eso fue la captura, ¿verdad? 486 00:22:24,830 --> 00:22:26,746 Usted puede recordar de sus compañeros de clase, si 487 00:22:26,746 --> 00:22:29,670 estaban haciendo ningún movimiento con sus pies, que era una operación. 488 00:22:29,670 --> 00:22:33,610 Así que si había tres personas aquí y la nueva persona pertenecía hasta allá, 489 00:22:33,610 --> 00:22:37,360 en una larga etapa como esta, claro, o ella sólo podía ir hasta el final. 490 00:22:37,360 --> 00:22:40,074 Pero si estamos pensando en un ordenador y una matriz de la memoria, 491 00:22:40,074 --> 00:22:41,990 estas personas van a tener que barajar más 492 00:22:41,990 --> 00:22:43,260 para dar cabida a esa persona. 493 00:22:43,260 --> 00:22:46,930 Y para que n menos 1 shufflings, n menos 2 shufflings, n 494 00:22:46,930 --> 00:22:50,660 menos 3 shufflings es sólo un poco de pasando detrás de mí, no en frente de mí 495 00:22:50,660 --> 00:22:52,710 como antes, en algún sentido. 499 00:22:52,557 --> 00:22:54,640 Ahora como un aparte, y como que podría haber visto en línea 500 00:22:54,640 --> 00:22:57,699 si usted comienza a hurgar sobre tipo, hay tan muchos diversos 501 00:22:57,699 --> 00:22:59,490 por ahí, algunos de ellos mejor que otros. 502 00:22:59,490 --> 00:23:02,200 De hecho, es uno bogosort eso es bastante divertido para mirar hacia arriba. 503 00:23:02,200 --> 00:23:06,650 Bogosort toma un conjunto de números o decir una baraja de cartas, 504 00:23:06,650 --> 00:23:09,870 las baraja al azar, y comprueba si están ordenados. 505 00:23:09,870 --> 00:23:12,130 Y si no, lo hace de nuevo. 506 00:23:12,130 --> 00:23:14,140 Y si no, lo hace de nuevo. 507 00:23:14,140 --> 00:23:15,440 Si no, lo hace de nuevo. 508 00:23:15,440 --> 00:23:17,060 Increíblemente estúpido. 509 00:23:17,060 --> 00:23:19,520 >> Y de hecho, si usted lee al igual que el artículo de Wikipedia, 510 00:23:19,520 --> 00:23:21,200 su apodo es estúpida especie. 511 00:23:21,200 --> 00:23:25,180 Con el tiempo va a funcionar, con suerte, dado el tiempo suficiente, 512 00:23:25,180 --> 00:23:28,240 pero esa cantidad de tiempo podría tomar bastante tiempo. 513 00:23:28,240 --> 00:23:31,650 Así que si yo pudiera, vamos a acelerar las cosas desde el ejemplo de Mary Beth antes, 514 00:23:31,650 --> 00:23:35,150 por tener algunos elementos más, sino dos procesadores más. 515 00:23:35,150 --> 00:23:37,100 Dos personas, si no le importaría acompañarme. 516 00:23:37,100 --> 00:23:40,972 ¿Qué hay de 1 por aquí, y vamos a vaya-- nadie allí? 517 00:23:40,972 --> 00:23:41,722 Nadie de allí? 518 00:23:41,722 --> 00:23:42,221 Okay. 519 00:23:42,221 --> 00:23:44,190 Usted con el negro camisa, sí, vamos hacia abajo. 520 00:23:44,190 --> 00:23:45,000 Muy bien, ¿cuál es tu nombre? 521 00:23:45,000 --> 00:23:45,720 >> AUDIENCIA: Peter. 522 00:23:45,720 --> 00:23:46,100 >> ALTAVOZ: ¿Qué es eso? 523 00:23:46,100 --> 00:23:46,766 >> AUDIENCIA: Peter. 524 00:23:46,766 --> 00:23:49,450 ALTAVOZ: Pedro, David, encantado de conocerte. 525 00:23:49,450 --> 00:23:53,670 Muy bien, tenemos Peter aquí, si quieren venir a la mesa aquí. 526 00:23:53,670 --> 00:23:54,550 ¿Y cuál es tu nombre? 527 00:23:54,550 --> 00:23:55,216 >> AUDIENCIA: Elena. 528 00:23:55,216 --> 00:23:55,970 ALTAVOZ: Elena. 529 00:23:55,970 --> 00:23:57,030 Bueno, encantado de conocerte. 530 00:23:57,030 --> 00:23:58,060 Elena cumple con Peter. 531 00:23:58,060 --> 00:23:59,170 Peter, Elena. 532 00:23:59,170 --> 00:24:02,290 Y necesitaremos Andrew aquí también, por favor. 533 00:24:02,290 --> 00:24:06,107 Y su reto va ser para ordenar una baraja de cartas. 534 00:24:06,107 --> 00:24:08,190 Y si no familiar, cubierta de tarjetas debe en última instancia, 535 00:24:08,190 --> 00:24:11,064 ordenarse un poco algo como esto donde haremos los clubes, a continuación, 536 00:24:11,064 --> 00:24:13,660 las espadas, a continuación, los corazones y diamantes, desde ace como uno, 537 00:24:13,660 --> 00:24:15,570 todo el camino hasta el rey. 538 00:24:15,570 --> 00:24:20,890 >> Las tarjetas que voy a darle van a ser 52 en cantidad. 539 00:24:20,890 --> 00:24:23,160 Vamos a similar vez que, en un momento. 540 00:24:23,160 --> 00:24:26,410 Vamos a lanzar Andrew en la pantalla aquí, 541 00:24:26,410 --> 00:24:28,170 con el fin de ver como hacer esto. 542 00:24:28,170 --> 00:24:31,070 Y para que todo esto es tanto más visible, 543 00:24:31,070 --> 00:24:33,490 estas son las cartas que recibí en Amazon. 544 00:24:33,490 --> 00:24:42,861 Así que ya son al azar solucionaron, y que vamos a medir el tiempo que usted. 545 00:24:42,861 --> 00:24:44,610 Y vamos a vivir en la realidad de este tiempo, 546 00:24:44,610 --> 00:24:47,820 así que vamos a tratar de presionarte porque de lo contrario esto será tedioso 547 00:24:47,820 --> 00:24:48,460 rápidamente. 548 00:24:48,460 --> 00:24:53,860 Si se pudiera proceder a ordenar 52 elementos juntos a través de algunos medios, ahora. 549 00:24:53,860 --> 00:25:04,710 550 00:25:04,710 --> 00:25:07,180 >> Y de nuevo, cuando vemos estos chicos hacen lo que, al final 551 00:25:07,180 --> 00:25:10,200 se va a producir una evidente resultado, piensa realmente 552 00:25:10,200 --> 00:25:12,962 cómo lo están haciendo cada uno que, cómo podría describirlo. 553 00:25:12,962 --> 00:25:15,045 Porque de nuevo, estos son todos los procesos, algoritmos 554 00:25:15,045 --> 00:25:17,090 que nosotros damos por sentado como un ser humano. 555 00:25:17,090 --> 00:25:22,349 Pero usted ha tenido probablemente mucho intuición, mucho antes de que incluso 556 00:25:22,349 --> 00:25:24,390 pensado en tomar un clase de informática que 557 00:25:24,390 --> 00:25:27,223 podría haber tenido la intuición con que para resolver problemas como éste. 558 00:25:27,223 --> 00:25:29,560 Pero una vez que reconocen los patrones y comenzar 559 00:25:29,560 --> 00:25:32,407 para formalizar los pasos con los que usted está la solución de estos problemas, 560 00:25:32,407 --> 00:25:35,490 usted encontrará que usted puede solucionar mucho más interesante y mucho más complejo 561 00:25:35,490 --> 00:25:39,190 problemas rápidamente. 562 00:25:39,190 --> 00:25:42,351 Así que alguien del público, lo que es al menos un elemento del algoritmo 563 00:25:42,351 --> 00:25:43,350 que están usando aquí? 564 00:25:43,350 --> 00:25:44,275 >> AUDIENCIA: [inaudible] 565 00:25:44,275 --> 00:25:45,150 ALTAVOZ: ¿Qué es eso? 566 00:25:45,150 --> 00:25:47,062 AUDIENCIA: Por ejemplo. 567 00:25:47,062 --> 00:25:47,770 ALTAVOZ: Por ejemplo. 568 00:25:47,770 --> 00:25:50,630 Así que primero que se están agrupando todos los diamantes juntos 569 00:25:50,630 --> 00:25:52,560 al parecer, todo el corazones juntos lo que parece, 570 00:25:52,560 --> 00:25:56,520 y así sucesivamente, sin respeto para los números de las tarjetas. 571 00:25:56,520 --> 00:26:00,900 Y ahora aparecen, por ejemplo, ser ordenándolos por número. 572 00:26:00,900 --> 00:26:06,870 573 00:26:06,870 --> 00:26:08,910 Muy buena. 574 00:26:08,910 --> 00:26:12,370 >> Muy bien, así que lo que va a ser el paso final, entonces aquí? 575 00:26:12,370 --> 00:26:16,950 Una vez que tenemos cuatro palos ordenados, lo que Por qué tenemos que hacer para las cuatro pilas 576 00:26:16,950 --> 00:26:20,059 con el fin de lograr uno cubierta ordenados, simplemente? 577 00:26:20,059 --> 00:26:21,350 Así que tenemos que combina otra vez. 578 00:26:21,350 --> 00:26:25,160 >> Así que hay una idea interesante que de nuevo, diría, es muy intuitivo incluso 579 00:26:25,160 --> 00:26:28,140 si usted nunca podría haber abofeteado ese tipo de etiqueta. 580 00:26:28,140 --> 00:26:31,900 Esta noción fundamental de la división el problema no en la mitad de este tiempo, 581 00:26:31,900 --> 00:26:33,410 pero al menos en cuatro piezas. 582 00:26:33,410 --> 00:26:36,810 Resolver casi problemas fundamentalmente idénticos 583 00:26:36,810 --> 00:26:40,480 en el aislamiento de uno al otro, y luego combinar los resultados. 584 00:26:40,480 --> 00:26:46,940 585 00:26:46,940 --> 00:26:50,140 Y, excelente, hecho. 586 00:26:50,140 --> 00:26:52,140 Muy bien, una gran ronda de aplausos, si pudiéramos. 587 00:26:52,140 --> 00:26:56,480 >> [Aplausos] 588 00:26:56,480 --> 00:26:59,740 >> ALTAVOZ: No tengo ni idea de lo que va a hacer con ellos, pero aquí tienes. 589 00:26:59,740 --> 00:27:01,690 Muchas gracias. 590 00:27:01,690 --> 00:27:04,660 Así que vamos a ver, a dos minutos y ocho segundos, de 591 00:27:04,660 --> 00:27:07,490 si desea desafiar a tus amigos. 592 00:27:07,490 --> 00:27:12,160 Entonces, ¿qué va a ser una toma de distancia de esta 593 00:27:12,160 --> 00:27:13,830 que podemos aprovechar de forma más general? 594 00:27:13,830 --> 00:27:16,080 Bueno, piense de nuevo a este conjunto de números, 595 00:27:16,080 --> 00:27:19,060 y pensar de nuevo ahora a algunas de las pseudocódigo que hemos escrito en el pasado, 596 00:27:19,060 --> 00:27:22,080 y este fue el pseudocódigo para resolver el problema de la guía telefónica. 597 00:27:22,080 --> 00:27:25,150 Por lo cual en pseudocódigo I enumerado una manera más metódica 598 00:27:25,150 --> 00:27:28,400 de describir la forma en que hice un muy intuitivo algoritmo humana de dividir el teléfono 599 00:27:28,400 --> 00:27:31,650 libro por la mitad, repetir, repetir, repetir, hasta que encuentre a alguien como Mike Smith, 600 00:27:31,650 --> 00:27:33,790 si es hecho en la guía telefónica. 601 00:27:33,790 --> 00:27:37,610 >> Pero que tipo de utilicé lo que yo llamo un enfoque muy iterativo aquí, 602 00:27:37,610 --> 00:27:42,160 en particular notificación línea 8 y la línea 11. 603 00:27:42,160 --> 00:27:46,750 Esos son evidencia de un proceso iterativo enfoque, un enfoque de bucle, 604 00:27:46,750 --> 00:27:49,040 porque eso es exactamente el comportamiento que inducen. 605 00:27:49,040 --> 00:27:52,910 Esas líneas de ambos dicen ir a línea de tres, y usted puede tipo de 606 00:27:52,910 --> 00:27:55,140 pensar que en su el ojo de la mente como un bucle. 607 00:27:55,140 --> 00:27:59,080 Le está diciendo a volver a subir al paso tres y repetir, una y otra vez, 608 00:27:59,080 --> 00:28:00,010 y otra vez. 609 00:28:00,010 --> 00:28:04,410 >> Pero ¿y si aprovechamos una idea clave aquí que hicimos no la última vez, 610 00:28:04,410 --> 00:28:10,280 y simplificar la línea 8 y línea 11 y sus vecinos 611 00:28:10,280 --> 00:28:12,840 como acaba esto, en amarillo. 612 00:28:12,840 --> 00:28:16,480 No es fundamentalmente acortar el pseudocódigo mucho, 613 00:28:16,480 --> 00:28:20,530 pero está cambiando fundamentalmente la naturaleza de mi algoritmo. 614 00:28:20,530 --> 00:28:24,220 Lo que ahora estoy diciendo en el paso 7, en el paso 10, 615 00:28:24,220 --> 00:28:29,140 es la búsqueda de Mike de la misma manera exacta, 616 00:28:29,140 --> 00:28:31,580 pero sólo en la izquierda la mitad o la mitad derecha. 617 00:28:31,580 --> 00:28:33,420 >> Así, en otras palabras, si Empiezo desde el paso uno, 618 00:28:33,420 --> 00:28:36,150 recoger la guía telefónica, abierto a medio de guía telefónica, mirar nombres, 619 00:28:36,150 --> 00:28:39,010 si se encuentra entre Smith nombre de, llame a Mike, lo demás 620 00:28:39,010 --> 00:28:44,340 si Smith es anterior en el libro, paso siete buscar Mike en la mitad izquierda del libro. 621 00:28:44,340 --> 00:28:47,130 Pero ese tipo de se siente como me está dejando colgar, ¿verdad? 622 00:28:47,130 --> 00:28:49,240 En amarillo, es un instrucción, pero ¿cómo puedo 623 00:28:49,240 --> 00:28:51,870 buscar Mike en la izquierda la mitad de la guía telefónica? 624 00:28:51,870 --> 00:28:54,210 ¿Dónde tengo un algoritmo con el que 625 00:28:54,210 --> 00:28:57,100 puede buscar a alguien como Mike Smith? 626 00:28:57,100 --> 00:28:58,980 Bueno, nos está mirando a la cara. 627 00:28:58,980 --> 00:29:03,090 Literalmente, puedo usar la misma exacta programa va efectivamente a la cima 628 00:29:03,090 --> 00:29:06,490 de nuevo y volver a correr las mismas líneas de código. 629 00:29:06,490 --> 00:29:10,610 >> Así que, aunque este debe sentirse como un poco de una definición cíclica 630 00:29:10,610 --> 00:29:13,480 donde usted está respondiendo a alguien es pregunta por sólo una especie de pedir 631 00:29:13,480 --> 00:29:15,990 la misma pregunta de nuevo, como por qué, por qué, por qué? 632 00:29:15,990 --> 00:29:21,580 La realidad es porque hemos codificamos un par de líneas especiales, el paso 4, 633 00:29:21,580 --> 00:29:25,320 que es un si, y el paso 12, el cual es efectivamente otra rama, 634 00:29:25,320 --> 00:29:30,120 porque tenemos esas medidas provisionales, este algoritmo terminará si 635 00:29:30,120 --> 00:29:32,050 encontrar Mike, o si no lo hacemos. 636 00:29:32,050 --> 00:29:36,810 Pero en el paso 7 y 10 ahora, tenemos lo que llamaremos un algoritmo recursivo. 637 00:29:36,810 --> 00:29:40,420 Y recursividad es de hecho una idea poderosa eso es un poco alucinante al principio, 638 00:29:40,420 --> 00:29:42,500 que ahora podemos aplicar la siguiente manera. 639 00:29:42,500 --> 00:29:46,600 >> Combinar tipo será el último tipo que miramos, al menos en la clase formal. 640 00:29:46,600 --> 00:29:50,040 Y es fundamentalmente diferente de los últimos tres, y ciertamente 641 00:29:50,040 --> 00:29:52,140 últimos cuatro si incluimos bogosort. 642 00:29:52,140 --> 00:29:54,810 Aquí está el pseudocódigo para merge sort. 643 00:29:54,810 --> 00:30:00,170 Cuando en la entrada de n elementos, por lo que dada una matriz de tamaño n, si n es menor que 2, 644 00:30:00,170 --> 00:30:01,040 regresar. 645 00:30:01,040 --> 00:30:03,610 Entonces, ¿por qué tengo que cordura comprobar primero? 646 00:30:03,610 --> 00:30:09,477 ¿Cuál es la implicación de que si te entrego una matriz cuya longitud n es menor que 2? 647 00:30:09,477 --> 00:30:11,060 Ya está ordenada, obviamente, ¿no? 648 00:30:11,060 --> 00:30:13,640 Debido a que la lista tiene ya sea un elemento, que es trivialmente 649 00:30:13,640 --> 00:30:15,180 ordenada porque es lo único que hay. 650 00:30:15,180 --> 00:30:18,138 O, es de tamaño cero, lo que significa no hay nada que arreglar, así que por la naturaleza 651 00:30:18,138 --> 00:30:18,720 que está ordenada. 652 00:30:18,720 --> 00:30:20,410 No hay nada mal allí. 653 00:30:20,410 --> 00:30:22,310 Así que ese es nuestro llamado caso base. 654 00:30:22,310 --> 00:30:24,440 >> Que es similar en espíritu a lo que hicimos con Mike. 655 00:30:24,440 --> 00:30:26,023 Si Mike en la guía telefónica, le llaman. 656 00:30:26,023 --> 00:30:27,740 Si él no está allí, darse por vencido. 657 00:30:27,740 --> 00:30:31,240 Es un caso base de la llamada, para asegurarse este algoritmo al final del día 658 00:30:31,240 --> 00:30:33,540 se detendrá en ciertas circunstancias. 659 00:30:33,540 --> 00:30:37,890 >> Pero aquí está el salto de fe ahora, otra cosa, ordenar la mitad izquierda de los elementos, 660 00:30:37,890 --> 00:30:39,740 a continuación, ordenar el derecho medio de los elementos, 661 00:30:39,740 --> 00:30:41,189 y luego fusionar las mitades ordenados. 662 00:30:41,189 --> 00:30:43,230 Y aquí es donde se siente como que estamos copping cabo. 663 00:30:43,230 --> 00:30:46,900 Te he pedido para ordenar n elementos, y estoy 664 00:30:46,900 --> 00:30:50,712 diciendo, bien, no es por la clasificación la izquierda y la clasificación de la derecha. 665 00:30:50,712 --> 00:30:52,420 Lo que digo es una otra cosa, y esto 666 00:30:52,420 --> 00:30:55,530 es el tema clave parece en la intuición hasta ahora, 667 00:30:55,530 --> 00:30:57,380 hay esta tercera etapa de la fusión. 668 00:30:57,380 --> 00:31:00,430 Qué aunque parece tan tonto en espíritu, 669 00:31:00,430 --> 00:31:02,320 como acaba de fusionar cosas juntos, parece 670 00:31:02,320 --> 00:31:05,380 ser un paso clave hacia la montaje de dos problemas que 671 00:31:05,380 --> 00:31:07,330 se dividieron en última instancia por la mitad. 672 00:31:07,330 --> 00:31:12,090 >> Así fusionar tipo, vamos a hacer esto, si me humor mí, con una manifestación más, 673 00:31:12,090 --> 00:31:14,730 sólo para que tengamos un poco de números para trabajar con. 674 00:31:14,730 --> 00:31:19,470 ¿Puedo intercambiar ocho estrés bolas para ocho personas? 675 00:31:19,470 --> 00:31:29,320 Muy bien, ¿y tú tres, cuatro en esta sección, cinco, seis, y vamos a 676 00:31:29,320 --> 00:31:30,720 do 7, 8, vamos arriba. 677 00:31:30,720 --> 00:31:35,120 678 00:31:35,120 --> 00:31:36,520 Aceptar, sí Aceptar. 679 00:31:36,520 --> 00:31:38,640 Minus 8, allí vamos, más 1. 680 00:31:38,640 --> 00:31:39,150 Excelente. 681 00:31:39,150 --> 00:31:42,000 Todo viene derecho hacia arriba, vamos a rápidamente le dará números. 682 00:31:42,000 --> 00:31:50,800 El número dos, número tres, número cuatro, número cinco, seis, siete y ocho. 683 00:31:50,800 --> 00:31:52,140 Hice ocho correctamente esta vez. 684 00:31:52,140 --> 00:31:56,390 >> OK, así que adelante si se pudiera, y vamos a ordenar en el orden original 685 00:31:56,390 --> 00:31:59,810 que tuvimos ayer que parecía así, si no te importa. 686 00:31:59,810 --> 00:32:03,620 Y vamos a hacerlo delante de la mesa. 687 00:32:03,620 --> 00:32:06,510 Muy bien, así que fusionar especie. 688 00:32:06,510 --> 00:32:08,820 Aquí es donde se va para conseguir una especie de interesante, 689 00:32:08,820 --> 00:32:12,800 porque me parece que estoy dando a mí mismo mucho menos información hoy en día. 690 00:32:12,800 --> 00:32:15,149 >> Así fusionar tipo primero de todo en la entrada de n elementos, 691 00:32:15,149 --> 00:32:18,440 y es, obviamente, no menos de dos, es ocho, así que tienen un poco más de trabajo que hacer. 692 00:32:18,440 --> 00:32:21,140 Así que ahora estamos mentalmente como una clase están ahora en la rama else, 693 00:32:21,140 --> 00:32:22,540 lo que significa tres pasos. 694 00:32:22,540 --> 00:32:25,017 En primer lugar, tengo que ordenar la mitad izquierda de los elementos. 695 00:32:25,017 --> 00:32:26,350 Entonces, ¿cómo hago para hacer esto? 696 00:32:26,350 --> 00:32:28,950 Bueno, voy a clase de mentalmente dividir la lista aquí, 697 00:32:28,950 --> 00:32:30,700 usted no tiene que mover físicamente, y estoy 698 00:32:30,700 --> 00:32:33,180 vamos a centrar sólo en la mitad izquierda de los elementos aquí. 699 00:32:33,180 --> 00:32:36,770 Entonces, ¿cómo hago para ordenar una lista ahora del tamaño de cuatro? 700 00:32:36,770 --> 00:32:38,730 ¿Cuál es mi algoritmo? 701 00:32:38,730 --> 00:32:42,580 Primero compruebo es n menos de dos, no, así que me dedico al bloque distinto. 702 00:32:42,580 --> 00:32:43,900 Ordenar a la izquierda de la mitad de los elementos. 703 00:32:43,900 --> 00:32:45,608 >> Así que ahora de nuevo, mentalmente, y aquí es donde 704 00:32:45,608 --> 00:32:49,550 debes acumular una gran cantidad de historia mental, si se quiere. 705 00:32:49,550 --> 00:32:51,940 Ahora estoy ordenando el izquierdo la mitad de la mitad izquierda. 706 00:32:51,940 --> 00:32:57,000 Muy bien, así que ahora llamo a mi misma combinación algoritmo de ordenación, es n menos de dos? 707 00:32:57,000 --> 00:33:00,590 No, es de dos, así que tengo que ordenar la mitad izquierda y la mitad derecha. 708 00:33:00,590 --> 00:33:02,042 Así que aquí vamos, ordenar la mitad izquierda. 709 00:33:02,042 --> 00:33:03,750 ¿Por qué no acaba de dar un paso hacia adelante. 710 00:33:03,750 --> 00:33:04,415 Cuál es tu nombre? 711 00:33:04,415 --> 00:33:04,860 >> AUDIENCIA: Darren. 712 00:33:04,860 --> 00:33:05,260 >> ALTAVOZ: Dan. 713 00:33:05,260 --> 00:33:06,040 Dan ha dado un paso adelante. 714 00:33:06,040 --> 00:33:06,748 >> AUDIENCIA: Darren. 715 00:33:06,748 --> 00:33:09,000 ALTAVOZ: Darren, hecho. 716 00:33:09,000 --> 00:33:10,090 ¿Dijo Darren o Dan? 717 00:33:10,090 --> 00:33:10,550 >> AUDIENCIA: Darren. 718 00:33:10,550 --> 00:33:11,216 >> ALTAVOZ: Darren. 719 00:33:11,216 --> 00:33:14,422 Aceptar, Darren ha intensificado hacia adelante y ahora está solucionado. 720 00:33:14,422 --> 00:33:16,130 Y esto es casi una afirmación estúpida, ¿verdad? 721 00:33:16,130 --> 00:33:18,862 Realmente no parece estar logrando nada, pero vamos a proceder. 722 00:33:18,862 --> 00:33:20,820 Ahora voy a ordenar la derecha medio de los elementos. 723 00:33:20,820 --> 00:33:21,200 Cuál es tu nombre? 724 00:33:21,200 --> 00:33:21,690 >> AUDIENCIA: Lucas. 725 00:33:21,690 --> 00:33:22,273 >> ALTAVOZ: Lucas. 726 00:33:22,273 --> 00:33:23,400 Vamos, un paso adelante. 727 00:33:23,400 --> 00:33:25,640 Hecho, he clasificado Lucas. 728 00:33:25,640 --> 00:33:28,570 La mitad izquierda está clasificado y la mitad derecha está ordenada, 729 00:33:28,570 --> 00:33:30,770 pero de nuevo, hay un paso clave aquí. 730 00:33:30,770 --> 00:33:32,940 ¿Qué tengo que hacer la próxima? 731 00:33:32,940 --> 00:33:33,941 Combinar las mitades ordenados. 732 00:33:33,941 --> 00:33:36,648 Ahora vamos a tener sólo todos atrás y hacia adelante de esta manera, 733 00:33:36,648 --> 00:33:38,620 porque Yo como que necesito algo de espacio cero. 734 00:33:38,620 --> 00:33:40,411 Es casi como éstos chicos están en una mesa, 735 00:33:40,411 --> 00:33:42,460 y necesito un poco de espacio para moverlos en. 736 00:33:42,460 --> 00:33:44,170 Así que voy a fusionar ustedes por mirar 737 00:33:44,170 --> 00:33:45,960 en la mitad izquierda y la mitad derecha. 738 00:33:45,960 --> 00:33:48,740 Y que, obviamente, es lo primero, la mitad izquierda o la mitad derecha? 739 00:33:48,740 --> 00:33:52,710 Así que la mitad derecha, por lo que vamos a pasar a Luke aquí a la posición original de Darren. 740 00:33:52,710 --> 00:33:57,640 Y ahora fusionar su mitad izquierda en, Darren va a mover a la derecha allí. 741 00:33:57,640 --> 00:33:59,750 >> Así que se siente como casi un efecto burbuja especie, 742 00:33:59,750 --> 00:34:02,482 pero mi algoritmo fundamental, muy diferente esta vez. 743 00:34:02,482 --> 00:34:04,815 Pero ahora es donde las cosas se ponen un poco molesto porque usted 744 00:34:04,815 --> 00:34:06,810 tener que rebobinar mentalmente dónde dejé fuera. 745 00:34:06,810 --> 00:34:09,893 Acabo fundí las mitades ordenadas, lo que significa que estoy en mi algoritmo? 746 00:34:09,893 --> 00:34:12,229 747 00:34:12,229 --> 00:34:13,770 Tengo que ordenar la mitad derecha, ¿no? 748 00:34:13,770 --> 00:34:15,910 >> Si rebobina, literalmente en el vídeo, podrás 749 00:34:15,910 --> 00:34:18,339 vemos que llegamos a este punto de Luke y Darren 750 00:34:18,339 --> 00:34:21,370 por la clasificación de la izquierda la mitad de la mitad izquierda. 751 00:34:21,370 --> 00:34:23,430 Entonces nos fusionamos los mitades ordenadas, que 752 00:34:23,430 --> 00:34:27,941 significa que el siguiente paso es ordenar la mitad derecha de la mitad izquierda. 753 00:34:27,941 --> 00:34:29,649 Muy bien, así que vamos a hacer esto más rápidamente. 754 00:34:29,649 --> 00:34:33,282 Muy bien, seis, voy a reclamar que ahora se ordenan, vamos hacia adelante. 755 00:34:33,282 --> 00:34:33,990 Cuál es tu nombre? 756 00:34:33,990 --> 00:34:34,589 >> AUDIENCIA: Adriano. 757 00:34:34,589 --> 00:34:35,200 >> ALTAVOZ: Adriano. 758 00:34:35,200 --> 00:34:36,010 Adriano está solucionado. 759 00:34:36,010 --> 00:34:36,450 ¿Y cuál es tu nombre? 760 00:34:36,450 --> 00:34:37,080 >> AUDIENCIA: Alex. 761 00:34:37,080 --> 00:34:38,379 >> ALTAVOZ: Alex está ahora ordenadas. 762 00:34:38,379 --> 00:34:40,750 Medio izquierdo, medio derecho, ¿cuál es el paso final? 763 00:34:40,750 --> 00:34:41,250 Combinar. 764 00:34:41,250 --> 00:34:44,310 Pretty trivial, así que estoy va a fusionar en seis, 765 00:34:44,310 --> 00:34:46,930 dar un paso atrás, ocho, dar un paso atrás. 766 00:34:46,930 --> 00:34:49,530 Y ahora note que esto es una comida para llevar útil, lo que 767 00:34:49,530 --> 00:34:53,930 ahora es verdad sobre la mitad izquierda de la lista, independientemente de cómo empezamos? 768 00:34:53,930 --> 00:34:55,090 Se está ordenada. 769 00:34:55,090 --> 00:34:57,750 >> Ahora que no está ordenada en el gran esquema de las cosas, 770 00:34:57,750 --> 00:35:00,250 pero está ordenada de forma independiente de la otra mitad. 771 00:35:00,250 --> 00:35:04,100 Ahora lo que paso soy yo en si sigo rebobinado de cómo comenzó la historia? 772 00:35:04,100 --> 00:35:05,680 Ahora tengo que ordenar la mitad derecha. 773 00:35:05,680 --> 00:35:07,630 Así que ahora estamos en el camino de regreso el principio de la historia, 774 00:35:07,630 --> 00:35:08,921 y vamos a hacer esto con mayor rapidez. 775 00:35:08,921 --> 00:35:11,320 Así que voy a ordenar la mitad derecha de toda la lista. 776 00:35:11,320 --> 00:35:13,060 ¿Cuál es el siguiente paso? 777 00:35:13,060 --> 00:35:15,840 Ordenar la mitad izquierda de la mitad derecha. 778 00:35:15,840 --> 00:35:18,715 Ordenar la mitad izquierda de la mitad izquierda de la mitad derecha. 779 00:35:18,715 --> 00:35:19,590 ¿Y cuál es tu nombre? 780 00:35:19,590 --> 00:35:20,230 >> AUDIENCIA: Omar. 781 00:35:20,230 --> 00:35:21,970 >> ALTAVOZ: Omar, un paso al frente, hecho. 782 00:35:21,970 --> 00:35:22,860 La mitad izquierda está ordenada. 783 00:35:22,860 --> 00:35:23,330 ¿Y cuál es tu nombre? 784 00:35:23,330 --> 00:35:23,820 >> AUDIENCIA: Chris. 785 00:35:23,820 --> 00:35:25,620 >> ALTAVOZ: Chris, dar un paso hacia adelante, que ahora está ordenada. 786 00:35:25,620 --> 00:35:27,010 ¿Cuál es el paso clave ahora? 787 00:35:27,010 --> 00:35:27,510 Combinar. 788 00:35:27,510 --> 00:35:30,509 Así que uno va a fusionar en su lugar aquí, si pudiera dar un paso atrás, 789 00:35:30,509 --> 00:35:32,930 y tres va a dar un paso atrás, se funden. 790 00:35:32,930 --> 00:35:38,080 Así que la mitad izquierda de la mitad derecha, ahora está solucionado. 791 00:35:38,080 --> 00:35:41,747 Francamente, este algoritmo se siente como que están perdiendo mucho más tiempo que antes, 792 00:35:41,747 --> 00:35:44,830 pero si lo hiciéramos esto en tiempo real, vamos a ver lo que los robos de balón va a ser. 793 00:35:44,830 --> 00:35:47,970 Ahora aquí estoy, ¿no la mitad de la mitad derecha, 794 00:35:47,970 --> 00:35:50,170 déjame ir adelante y ordenar la mitad izquierda. 795 00:35:50,170 --> 00:35:51,482 Paso adelante, ¿cómo te llamas? 796 00:35:51,482 --> 00:35:52,190 AUDIENCIA: Ramsey. 797 00:35:52,190 --> 00:35:53,210 ALTAVOZ: Ramsey está solucionado. 798 00:35:53,210 --> 00:35:53,570 Cuál es tu nombre? 799 00:35:53,570 --> 00:35:54,200 >> AUDIENCIA: Marina. 800 00:35:54,200 --> 00:35:57,033 >> ALTAVOZ: Marina está clasificado como así, si usted toma un paso hacia adelante. 801 00:35:57,033 --> 00:36:00,690 Paso clave es ahora fusionar, estoy va a arrancar de mis dos listas, 802 00:36:00,690 --> 00:36:01,720 izquierda y derecha. 803 00:36:01,720 --> 00:36:05,150 Cinco va a ser lo primero, y siete va a ser el próximo. 804 00:36:05,150 --> 00:36:06,410 Y de nuevo, esto es deliberado. 805 00:36:06,410 --> 00:36:08,535 El hecho de que están tomando pasos hacia adelante y hacia atrás 806 00:36:08,535 --> 00:36:12,997 tiene la intención de representar que no podemos hacer este algoritmo en su lugar con la misma facilidad 807 00:36:12,997 --> 00:36:15,830 como especie de burbuja, y la selección de tipo, y tipo de inserción en el que sólo 808 00:36:15,830 --> 00:36:16,960 guardado intercambiando personas. 809 00:36:16,960 --> 00:36:19,940 Yo, literalmente, necesito una especie de papel borrador en el que 810 00:36:19,940 --> 00:36:21,827 para poner a estas personas mientras hago la fusión, 811 00:36:21,827 --> 00:36:23,410 y entonces puedo volver a ponerlos en su lugar. 812 00:36:23,410 --> 00:36:27,260 Y eso es clave porque estoy usando un nuevo recurso, el espacio, no sólo tiempo. 813 00:36:27,260 --> 00:36:28,270 >> OK, esto es increíble. 814 00:36:28,270 --> 00:36:32,050 La mitad izquierda está ordenada, la mitad derecha es paso ordenado, ahora que la fusión de tecla. 815 00:36:32,050 --> 00:36:33,450 ¿Cómo voy a fusionar esto? 816 00:36:33,450 --> 00:36:35,470 Así que si usted sigue mi la mano izquierda y la mano derecha, 817 00:36:35,470 --> 00:36:38,930 Voy a señalar mi mano izquierda en la mitad izquierda, la mano derecha 818 00:36:38,930 --> 00:36:42,680 en la mitad derecha, y ahora tengo que decidir paso a paso a quién se funden en. 819 00:36:42,680 --> 00:36:44,650 Que obviamente es lo primero? 820 00:36:44,650 --> 00:36:45,150 Número uno. 821 00:36:45,150 --> 00:36:47,327 Así que ven aquí, aquí está nuestro bloc de notas. 822 00:36:47,327 --> 00:36:49,910 Así que ahora el número uno, y el aviso lo que voy a hacer con mi mano derecha, 823 00:36:49,910 --> 00:36:54,152 Voy a mover mi mano derecha una pasar por encima al punto número tres, 824 00:36:54,152 --> 00:36:55,860 y ahora tengo que hacer la misma decisión. 825 00:36:55,860 --> 00:36:58,387 Y en realidad de pie justo en delante de Lucas aquí si pudiera, 826 00:36:58,387 --> 00:36:59,720 porque este es nuestro bloc de notas. 827 00:36:59,720 --> 00:37:00,610 Entonces, ¿quién sigue? 828 00:37:00,610 --> 00:37:05,000 Tenemos Lucas con el número dos o Chris número tres. 829 00:37:05,000 --> 00:37:07,460 Obviamente Lucas, número dos, por lo que vienen aquí. 830 00:37:07,460 --> 00:37:11,270 >> Pero mi mano izquierda ahora va a se incrementa para apuntar a Darren, 831 00:37:11,270 --> 00:37:15,160 y aquí está la clave de llevar con la fusión, que voy a seguir haciendo esto, 832 00:37:15,160 --> 00:37:17,340 Obviamente, si usted amable de seguir la lógica. 833 00:37:17,340 --> 00:37:19,670 Pero mis manos nunca son va a ir hacia atrás, 834 00:37:19,670 --> 00:37:23,861 lo que significa que sólo alguna vez voy a mudar a la izquierda con mi proceso de fusión, 835 00:37:23,861 --> 00:37:26,360 y eso va a ser clave para nuestro análisis en un momento. 836 00:37:26,360 --> 00:37:27,859 >> Así que ahora vamos a terminar esto rápidamente. 837 00:37:27,859 --> 00:37:31,650 Así que tres viene a continuación, luego cuatro viene a continuación, 838 00:37:31,650 --> 00:37:38,750 y ahora cinco viene a continuación, y luego seis, y siete, y, finalmente, ocho. 839 00:37:38,750 --> 00:37:42,960 Se siente como el algoritmo más lento sin embargo, pero no si en realidad 840 00:37:42,960 --> 00:37:45,510 ejecutarlo en el mismo tipo de velocidad de reloj, por lo que 841 00:37:45,510 --> 00:37:48,106 hablar, con el mismo tic-tac del reloj como antes. 842 00:37:48,106 --> 00:37:48,605 ¿Por qué? 843 00:37:48,605 --> 00:37:51,100 Bueno, echemos un mirar en el resultado final. 844 00:37:51,100 --> 00:37:56,990 >> Volvamos aquí, déjame tire hacia arriba una demostración visual 845 00:37:56,990 --> 00:37:59,030 de lo que acabamos de hacer. 846 00:37:59,030 --> 00:38:06,110 Acercar aquí, en esta página aquí, diciendo Firefox 847 00:38:06,110 --> 00:38:08,200 que queremos hacer cola en esta caja, vamos a 848 00:38:08,200 --> 00:38:11,260 decir especie de burbuja, con la que ahora estamos bien familiarizados, 849 00:38:11,260 --> 00:38:14,130 ordenación por selección, que es otra uno bastante sencillo, 850 00:38:14,130 --> 00:38:18,250 y ahora de hoy merge sort, el cual será nuestro final culminante. 851 00:38:18,250 --> 00:38:21,530 La razón por la que tomó mucho más tiempo aquí con los seres humanos y me verbalmente es, 852 00:38:21,530 --> 00:38:23,480 Obviamente, estoy explicando cada paso. 853 00:38:23,480 --> 00:38:26,920 Pero si simplemente ejecuta este, mucho como lo hicimos especie de burbuja y selección 854 00:38:26,920 --> 00:38:30,890 especie no sólo visualmente, reloj cuánto más eficiente 855 00:38:30,890 --> 00:38:33,330 Este apalancamiento de división y conquista 856 00:38:33,330 --> 00:38:39,150 puede ser cuando se aplica a un conjunto de datos que está ni siquiera tamaño de ocho, pero incluso mucho, 857 00:38:39,150 --> 00:38:39,970 mucho más grande. 858 00:38:39,970 --> 00:38:44,585 Doy combinar especie, uno al lado del lado con estos otros algoritmos. 859 00:38:44,585 --> 00:38:56,364 860 00:38:56,364 --> 00:38:58,530 Esto se va a poner dolorosa rápidamente, y el final 861 00:38:58,530 --> 00:39:00,890 no es particularmente culminante, que sólo terminan ordenados. 862 00:39:00,890 --> 00:39:05,280 Pero la clave para llevar es que mirar cuánto más rápido fusionar especie 863 00:39:05,280 --> 00:39:08,110 era, a menos que pienses que soy sólo un poco de jugar con usted. 864 00:39:08,110 --> 00:39:13,100 Si hacemos esto por última vez, Vamos a recargar esto, volvamos 865 00:39:13,100 --> 00:39:14,960 y elegir especie de burbuja, y sólo por diversión, 866 00:39:14,960 --> 00:39:17,330 vamos a elegir la inserción especie, sólo por si acaso. 867 00:39:17,330 --> 00:39:20,020 Y esta vez de nuevo, vamos a elija Fusión de clase y vamos a 868 00:39:20,020 --> 00:39:21,595 de hecho ejecutar estos lado a lado. 869 00:39:21,595 --> 00:39:24,140 870 00:39:24,140 --> 00:39:26,930 >> Y no es, de hecho, un golpe de suerte. 871 00:39:26,930 --> 00:39:31,140 Lo que he hecho es efectivamente tengo dividido mi entrada a la mitad, de nuevo, 872 00:39:31,140 --> 00:39:32,240 y otra vez, y otra vez. 873 00:39:32,240 --> 00:39:35,590 Y sólo hay tantas veces que puedas dividir su entrada en mitades, izquierda 874 00:39:35,590 --> 00:39:36,240 y la derecha. 875 00:39:36,240 --> 00:39:39,425 ¿Cuál es la fórmula que nos seguimos viendo que describe la división por la mitad 876 00:39:39,425 --> 00:39:41,050 otra vez, y otra, y otra, y otra vez? 877 00:39:41,050 --> 00:39:41,890 >> AUDIENCIA: log n. 878 00:39:41,890 --> 00:39:42,760 >> ALTAVOZ: Inicie sesión n. 879 00:39:42,760 --> 00:39:46,300 Pero luego hay otro paso clave, este algoritmo no es log n pasos. 880 00:39:46,300 --> 00:39:48,992 Si sólo se log n pasos, estaríamos en el mismo problema 881 00:39:48,992 --> 00:39:51,200 como antes, donde no podemos estar Seguro que todo está ordenado. 882 00:39:51,200 --> 00:39:54,480 Hay que mirar mínimamente en n elementos para asegurarse de n elementos se ordenan, 883 00:39:54,480 --> 00:39:55,950 de lo contrario es un acto de fe. 884 00:39:55,950 --> 00:39:59,810 >> Por lo que es registro mínimamente n pasos, pero ¿qué pasa con este paso clave fusión 885 00:39:59,810 --> 00:40:04,370 donde combiné mi mitad izquierda y derecha medio y caminó por el escenario? 886 00:40:04,370 --> 00:40:06,980 ¿Cuántos pasos es que fusionar? 887 00:40:06,980 --> 00:40:10,150 Es n, pero no lo hice solo fusionar el tiempo final. 888 00:40:10,150 --> 00:40:15,089 En cada una de esas llamadas anidadas, en cada de esas fusiones anidados, yo todavía lo solucionaron. 889 00:40:15,089 --> 00:40:18,380 Combiné estos dos chicos, a continuación, estos dos chicos, entonces estos dos chicos y así sucesivamente. 890 00:40:18,380 --> 00:40:19,955 >> Así que me di la fusión de nuevo, y otra vez. 891 00:40:19,955 --> 00:40:20,580 ¿Cuántas veces? 892 00:40:20,580 --> 00:40:23,510 Así que cada vez que divide la lista a la mitad, me hizo una fusión. 893 00:40:23,510 --> 00:40:25,460 Divida la lista por la mitad, hacer una fusión. 894 00:40:25,460 --> 00:40:28,570 Así que si dividiendo la lista se puede hacer log n veces, 895 00:40:28,570 --> 00:40:33,880 y la fusión en última instancia lleva a n pasos, lo que podría ser ahora la parte superior 896 00:40:33,880 --> 00:40:37,000 con destino en el funcionamiento tiempo de nuestro algoritmo? 897 00:40:37,000 --> 00:40:37,980 n log n. 898 00:40:37,980 --> 00:40:40,560 >> Y de hecho, eso es lo que que hemos logrado aquí. 899 00:40:40,560 --> 00:40:44,650 Así que la sensación que se ve visualmente cuando esas tres cosas corren lado a lado 900 00:40:44,650 --> 00:40:47,930 está n al cuadrado contra n cuadrado contra n log n. 901 00:40:47,930 --> 00:40:51,010 Qué fundamentalmente vamos a ver, no sólo hoy sino en el futuro, 902 00:40:51,010 --> 00:40:52,760 es mucho, mucho más rápido. 903 00:40:52,760 --> 00:40:56,010 Un aplauso para estos chicos, Voy a recompensarlos con bolas de estrés. 904 00:40:56,010 --> 00:41:00,260 Vamos a levantar la sesión aquí hoy, y nos vemos el lunes. 905 00:41:00,260 --> 00:41:02,255