[Powered by Google Translate] [Semana 3, continuación] [David J. Malan - Harvard University] [Esta es CS50. - CS50.TV] Está bien. Bienvenido de nuevo. Esto es CS50 y este es el fin de semana 3. Así que para aquellos años desconocido, última Harvard lanzó lo que se llama el Laboratorio de Innovación, o i-lab, que es un maravilloso edificio a través del río en el campus de HBS que está abierto a estudiantes universitarios, estudiantes GSAS, estudiantes de todo el campus, a través de incluyendo la facultad, y es un lugar donde se reúnen para trabajar en cosas innovadoras, cosas particularmente empresariales si usted y sus amigos 0 o más personas están pensando en hacer algo emprendedor ya sea durante la clase, después de esta clase, o más allá. Así que una de las cosas que hacen durante el plazo del J es estos viajes, uno de los cuales es a Nueva York, uno de los cuales es a Silicon Valley. El espacio es muy limitado, pero es una oportunidad para codearse con los MBA y estudiantes de postgrado de todo el campus y en realidad pasar tiempo en esos mismos ámbitos conversando con startups, conversando con empresarios y similares. Así que si está interesado, echa un vistazo a esta URL aquí. También está disponible en las diapositivas en línea. Podríamos bajar el tono de audio casa un poco? Si desea unirse a nosotros para el almuerzo de este viernes, 1:15 pm en Fire & Ice, por favor dirigirse allí. Disculpas si el formulario ya lleno para cuando llegues allí. Pero seguiremos adelante esta tradición. Hoy continuamos con la discusión de alto nivel de diversos problemas que se pueden resolver, centrándose mucho menos, al menos hoy, en el código y mucho más en las ideas. Así que piensen en la semana 0, cuando se desgarró un directorio telefónico por la mitad, cuyo objetivo era hacer algo, sin duda, un poco dramático pero para enviar el punto de que la búsqueda no tiene que ser, necesariamente, tan evidente a primera vista se podría pensar. Y la resolución de problemas en general, no necesariamente siempre ser el mejor - La solución más obvia podría no ser necesariamente la mejor. Así que tuvimos este directorio y, francamente, todos nosotros en esta habitación tenía los instintos, Lo más probable es que comience en el centro en la búsqueda de Mike Smith y luego ir a la izquierda oa la derecha sobre la base de lo que las letras del alfabeto nos pasó a terminar en. Pero esa simple idea de que los seres humanos hemos dado por sentado durante tanto tiempo realmente debería empezar a venir a la vanguardia de su mente porque como los problemas de conseguir mucho más compleja que una guía telefónica, esas mismas ideas simples y brillantes son las que nos van a permitir para resolver problemas mucho más complicados y más interesante, entre ellas algunas de las cosas que damos por sentado ya en estos días. Miles de millones de páginas web por ahí, y sin embargo Google y Bing y similares son capaces de encontrar cosas para nosotros de esa manera. Eso no va a suceder mediante una búsqueda lineal, buscando a través de todas las páginas web posibles. Facebook es capaz de decirle que todos sus amigos son o amigos de amigos, y que también se puede hacer en un instante aparentemente estos días a pesar de que cuentan con millones de usuarios. Y entonces, ¿cómo podemos realmente resolver los problemas en esa escala en última instancia, reducir a las ideas que vimos en la semana 0 y un poco más hoy. No vamos a volver a ejecutar este algoritmo, pero recuerda que también hizo en la semana 0 este ejercicio donde nos tenía a todos ponerse de pie, tomar el número 1, y luego tuvimos todo el mundo por cuenta propia emparejamiento, agregando sus números, entonces la mitad de la banda se sentó en cada iteración. Así que pasó de 500 estudiantes a 250 a 125 y así sucesivamente. Pero como dijimos el lunes, la idea poderosa que existe era que si duplicamos el tamaño de ese problema y todos los niños de Justicia o Ec 10 volvió a entrar en la habitación y se unió a nosotros, así, es probable que podía contar con ese grupo agregado total con sólo 1 iteración más grande del circuito, ya que sólo sería tal vez el doble del tamaño o en caso de Ec 10 un poco más del doble del tamaño. Y por lo que tendría que pasar un poco más tiempo, pero no tendríamos que gastar 400 o 700 pasos más. Sólo para pintar este cuadro de manera que es un poco menos abstracta, no vamos a tener a todos de pie. Pero si aquellos que elegimos para sentarse en la orquesta de hoy no le importaría ponerse de pie, vamos a ver si podemos averiguar de vosotros que es la persona más alta haciendo el mismo tipo de algoritmo comparativo. Así que si estás sentado en la orquesta, mis disculpas, pero el paso 1, ponerse de pie; paso 2, se emparejan con alguien cercano que, averiguar quién es más alto, y me siento si son más cortos. Luego repita. [Estudiantes murmurando] Bien. Bien. Uno se queda de pie. ¿Cuál es tu nombre? >> Andrew. Andrew, eres la persona más alta en la sección de orquesta hoy. Felicitaciones. [Aplausos y vítores] Bueno. Toma asiento. Así que nos pareció Andrew. Pero ¿cuánto tiempo me han llevado, por ejemplo, para encontrar Andrew en esta sección orquesta de 50 + o menos a la gente? Yo podría haber tomado un enfoque bastante simple y empiece aquí. Y he 2 personas de pie y yo sólo les compara, y entonces yo les digo que es un poco más corto, "Está bien, te sientas" y yo voy a recordar que la persona más alta era. Entonces repito, repito, repito, y me agarro a la persona más alta hasta que encuentre a alguien un poco más alto que ellos, y en ese momento la persona un poco más corto tiene que sentarse luego hacia abajo. Pero en este algoritmo en esta sección orquesta, si hay n de ustedes, cuántos pasos es que el algoritmo va a tomar? >> [Estudiante] N. Va a tomar n, derecha, porque en el peor de los casos, por así decirlo, la persona más alta es la última persona que llego a sólo mala suerte al azar. Así, en el peor de los casos, el tiempo de ejecución de algoritmo que es lineal, es n, donde n es el número total de personas en el espacio, el tamaño del problema. ¿Qué pasa con este algoritmo? El hecho de que todo se puso de pie y de nuevo la mitad de ustedes se sentó, la mitad de ustedes se sentó, la mitad de ustedes se sentó. ¿Cuántos pasos se han tomado que si hay n de ustedes aquí? [Estudiante] N log n. >> Eso sería peor. Iniciar sesión n. Así log n, aunque no recuerdo bien lo que es un logaritmo, por ahora, sólo apreciar que se relaciona de alguna manera a esta reducción a la mitad y mitad y mitad. No tiene que ser un factor de 2. Podría ser un factor de 3. Pero es esta repetición de la misma clase de factor de tal manera que el tamaño del problema comienza aquí pero inmediatamente va aquí, aquí, aquí, aquí. Usted no está tomando pequeños bocados para salir del problema, en realidad está cortando lejos en lo con un gran golpe cada vez. Así que tuvimos 50 personas, luego 25, luego 12 ½ ó 13 personas de pie, entonces 6 años y medio y así sucesivamente hasta que, finalmente, sólo de pie Andrew se quedó. Así que vamos a llamar a ese registro de n, y se puede visualizar de la siguiente manera. Recordar esta foto aquí donde un algoritmo lineal es como la línea roja allí, la línea amarilla fue el conteo por 2s algoritmo que utilizamos para los estudiantes contar en el pasado, pero hoy en día el santo grial va a seguir siendo la línea verde en la que si duplicamos el número de personas en la sección de orquesta o acaba de decir, infierno, vamos a tener a todos en el cuarto entero de pie, no una cosa muy importante porque aproximadamente el doble de cantidad de personas que están aquí abajo, Una iteración más, y no un problema. Hemos encontrado Andrew o cualquiera que esté más alto que Andrew en el altillo o en el balcón. Así que esta idea simple que nos tomamos tanto por sentado en una guía telefónica, cuenta de que hay tantos lugares diferentes en los que podemos aplicar. Sólo para dar una palmada jerga - de hecho, en lugar de jerga en primer lugar, déjame ir a este cuadro aquí. En este momento hemos hablado de n y n / 2 y luego se desconecta de n, pero sin duda puede llegar a, como veremos a lo largo del semestre, otro tipo de fórmulas matemáticas para describir esta noción general de tiempo de ejecución. Estos son fuera de contexto, por ahora, porque vamos a ver dentro de poco algoritmos que estos en realidad representan. Pero nótese aquí la línea n lineal, la línea recta, es realmente muy bajo apuntando en estos momentos. Eso es una especie de ilusión óptica de que acabamos de cambiar lo que el eje x representa y el eje Y, y podemos hacer un punto de la línea recta en cualquier dirección que desee. Pero la razón de que sea tan aparentemente plana ahora se debe a que necesitábamos para hacer el sitio en este gráfico para mucho más lentos los tiempos de ejecución. Por ahora, sabemos que hay algunos algoritmos muy mal en la vida, algunos de los cuales no se toman medidas n o, mejor aún, iniciar n pasos, pero mucho más. Así que por encima de la línea n aquí, en el anuncio de abajo hay n log n de veces, y vamos a ver lo que esto significa en poco tiempo. Por encima de eso es n al cuadrado, y no hemos visto ningún algoritmo cuadrado n todavía, pero estamos a punto. Y eso se ve muy mal. Hay 2 a la n, algo exponencial, que se siente incluso peor. Y, sin embargo, curiosamente, entonces hay n en cubos, que si estás pensando en el futuro de la especie, si que tipo de hacer los cálculos, 2 a la n en realidad es mucho más recta, mucho más alto que n cubos si nos fijamos en los ejes lo suficientemente lejos. Así notar ahora estos ejes son arbitrariamente 2 a 10 en el eje x. ¿Y qué significa eso? Eso significa que 2 personas a 10 personas en la sala. Por todos los medios x: tamaño del problema, cualquiera que sea el contexto. Y un eje vertical derecho ahora es el número de segundos o número de pasos - alguna unidad de tiempo. Pero nótese que es 0 a 60 y 0 a 10. Pero si que tipo de zoom hacia fuera, como es posible que en Excel u otro software de gráficos, y nos vamos hasta 200.000, note que algo así como 2 a la n va a desbordar por completo los tiempos de funcionamiento de cuadrado n, n cubos, n log n - todo lo que hemos hablado hasta ahora. Sin embargo, el problema es cuando se empieza a hablar de cosas como Facebook donde has muchos, muchas, muchas personas todos interconectados, tiene n personas, cada uno de los cuales puede tener hasta amigos n si todo el mundo es algo muy amigos en el mundo, bueno, eso es n veces n ya, por lo que está n al cuadrado amistades posibles, por lo menos en una dirección, n cuadrados amistades posibles. Así que ya sugiere que la búsqueda gráfica social de Facebook, por así decirlo, puede comenzar a ser expresado en este tipo de fórmulas. Vamos a volver y hacer esto mucho más concreto, pero por ahora, el objetivo de las muchas semanas siguientes va a estar seguro de no ir sobre la aplicación de algoritmos o código que terminan por tomar tanto tiempo como algo parecido a esto. Pero lo fascinante de la informática si continúa en este campo tomar clases como CS121, CS124, ambos de los cuales están los cursos teóricos, es que en realidad hay algunos problemas que existen en este mundo que, fundamentalmente, en la medida que sabemos, no se puede resolver más rápido que el peor de estos gráficos en realidad sugiere. Así que hay un montón de problemas abiertos en este mundo que se puede hacer mucho mejor que los seres humanos tienen hasta el momento. Así que vamos a empezar entonces con este ejemplo. Vimos la lucha de Sean con esta cámara, con demasiada torpeza en el vídeo. Pero la realidad era que Sean estaba encargado de encontrar en una tabla como ésta, la número 7, Recuerdo que me dijo que "no está en alguna parte detrás de estas piezas de papel o puertas blancas "El número 7. Sean, resulta para nosotros." Y fue maravillosamente difícil de ver porque estaba realmente luchando con este problema. Pero la realidad era Sean lo hizo tan bien como cualquiera en la habitación podría haber hecho. Tomó un poco más de lo que una persona normal pueda tener, pero supuso que había algún truco para este problema, supuso que se estaba perdiendo algo. Y no ayudó que cientos de ojos se dirigía hacia él. Pero la realidad era si la entrada al problema es un montón de números aleatorios y se le está pidiendo a encontrar un número tal, lo mejor que puedes hacer es buscar lineal. Comience en la izquierda, mueva hacia la derecha, o comenzar a la derecha, mueva a la izquierda. Retroactivamente, podríamos estar pensando: "Sean, ¿por qué no acabas de empezar desde el otro extremo?" Bien, 7 podría haber sido tan fácilmente aquí al azar, pero deliberadamente puesto ahí porque me di cuenta que no va a empezar por el final. Así que tipo de manipular la situación, pero por casualidad 7 podría haber sido en cualquier lugar. Así que a partir del extremo derecho podría haber sido mejor, entonces, pero ¿y si el año que viene me mudo 7 en otra parte? Eso no es una solución totalmente nuevo para el problema - a partir del 1 extremo o el otro - cuando te dan ninguna suposición otros. Así que Sean comenzó a buscar a través de los números y me dijo: "5. Eso no está aquí." Luego fuimos allí y vi a 19, y luego se detuvo durante unos 20 segundos, Luego se abrió para este 13, y luego se hizo evidente que no parece ser un patrón aquí. No fue 1, 2, 3, 4 o similar. Hay lagunas en los números, que no ayudaron. Y también, el hecho de que he usado estas piezas baratas de papel para cubrir los números en realidad es deliberada, porque si me quita todas estas piezas de papel, la mayoría de nosotros, Sean incluido, probablemente habría una especie de mirada macroscópicamente en el pizarrón y le dijo: "Oh, 7 es obviamente allí mismo". Lo hicimos de inmediato. Y que podría ser la forma en que el cerebro humano funciona en cierta medida, pero en realidad, los ojos o la mente fue probablemente rozando los números de derecha a izquierda, izquierda a derecha, medio en adelante - algo que estaba sucediendo fisiológicamente de tal manera que parecía que estaba sucediendo al instante, pero las probabilidades son incluso internamente que había algún tipo de metodología para la búsqueda 7. Y de hecho, ahora que estamos hablando de arrays y estructuras de datos y dentro de la memoria de un ordenador, lo único que los seres humanos podemos hacer es mirar a posiciones de memoria cada uno a la vez. Así que todas las demás localidades también podría ser cubierto con algún pedazo de papel porque no podemos verlo de todos modos. Sólo podemos hacer una cosa a la vez. Así que en este caso, en el caso de Sean, nos fuimos allí y luego fuimos aquí y luego nos fuimos aquí, aquí, aquí, aquí, tiene listo a finales y sólo un poco de lo saltamos una forma arbitraria y se encontró allí 7. Este no fue particularmente especial. También estaba fuera de orden. Pero finalmente encontró 7. Pero ahora la comida para llevar que realmente es lo mejor que puede hacer cuando se le da ninguna información excepto los números ordenados aleatoriamente es comenzar desde la izquierda o desde la derecha comenzar. O diablos, que al azar puede abrir puertas, pero aun así, ¿qué significa ser al azar? Bueno, tendría que formalizar de alguna manera lo que significa comenzar aquí, a continuación, haz clic aquí, y luego ir aquí. Sean hizo muy bien, y era divertido ver. ¿Y si en vez de eso cambia el problema un poco y traer a Sean de este año, si se quiere? ¿A alguien se sienta cómodo subiendo al escenario y la solución de un problema ligeramente diferente y apareciendo en cámara? Vamos a ir más allá de la orquesta porque ustedes han sido un poco complicado hoy en día ya. ¿Qué tal en rosa, en el sombrero? Vamos hacia abajo. ¿Cuál es su nombre? >> Alex. >> Alex. Bien. Así que Alex será Sean de este año y se publicará en los próximos años valor de CS50 conferencias. Alex, nice to meet you. >> Nice to meet you too. El desafío actual para usted es que usted tiene un poco más fácil en que te estoy diciendo a los mismos números están aquí, pero están ordenados ahora. Así que ahora su objetivo es encontrar el número 7. Y en realidad, deberíamos hacer esto - TU ESTAS tipo de trampa, como un ordenador no lo haría, viendo lo que los números eran hace un momento. Con tiza en realidad esto no va a ayudar a casi nada, pero vamos a suponer que usted no sabe lo que es la matriz original. Todo lo que sabemos ahora es que tiene una matriz de números ordenados que podría tener huecos entre ellos, y su objetivo es encontrar el número 7. ¿Cómo usted, un ser humano razonable ser, va sobre encontrar el número 7? Ir de menor a mayor? >> Okay. Ir de menos a más. Y no se les arrancan. Vamos a levantarlos para que podamos volver a utilizarlos. Bien, así que 1. Espera. Antes de seguir adelante, que fue de 1, claramente errónea. Entonces, ¿qué pasa por tu mente ahora? ¿Cuál es tu próximo paso? La siguiente. >> Okay. La siguiente. Bueno. 3, de modo incorrecto. ¿Cuál es tu próximo paso? Seguir adelante. >> Está bien. Seguir adelante. 5. Así que sigue adelante, y deja que te entregue esto para la posteridad. 7. >> Excelente. Muy bueno. Encontrado el número 7. [Aplauso] Así que eso era bueno, pero Sean también encontró que el número 7. Y yo sostengo que en realidad no ha explotado esta pieza adicional de información, que es que estos números se ordenan. Entonces, ¿podemos hacerlo mejor? Cualquier sugerencia aquí? Sí, en la parte trasera. [Estudiante] Binary búsqueda. >> Tengo ni idea de lo que es la búsqueda binaria. [Estudiante] Comenzar en el centro. Inicio >> en el centro. Bien. Así que vamos a ver si podemos llegar hasta allí. Así que si te dicen en lugar de inicio desde el medio, seguir adelante y abrir la puerta del medio. Hay 8 de ellos, por lo que vamos a tener que elegir arbitrariamente el ligeramente a la izquierda o a la derecha. Bien. 7! [Aplausos] Muy bueno. De acuerdo, pero ¿dónde íbamos con esto? Supongamos sólo para romper el empate que había comenzado aquí ya que igualmente podría haber sucedido así. Nos acaba de pasar a conocer que el 7 estaba allí. Así que esta es 13. Así que si están ordenados y que acaba de comenzar en el medio, ¿cuál sería el próximo movimiento óptimo haber sido? Ir a la izquierda. Y aquí viene el ejemplo de libro de teléfono de nuevo. Si 13 es aquí y sabemos que la lista está ordenada, entonces todas estas piezas de papel son interesantes para nosotros ahora porque ya sabemos que 7 debe estar a la izquierda si estos números están ordenados y encontramos 13. Entonces, ¿cuál es tu próximo movimiento en esta lista? >> Ir a la izquierda. >> Bien, bien. Así que ir a la izquierda, y - ¡agárrense, hey, hey, hey. Eso es trampa. Así que has encontrado 7, pero ¿cuál fue el algoritmo que acaba de aplicar? Comience en el centro. Bueno >>. ¿Cuál es la extensión lógica de esa misma idea? Oh, sólo por éstos. >> Exactamente. >> Así que empiece aquí. Bueno >>. Así que ahora que nos fuimos un poco a la izquierda de nuevo. Son las 3. Pero la comida para llevar interesante ahora es ¿cuál no tiene que preocuparse? Estos 2. Estos >> 2. Así que ahora éste puede desaparecer, esto se puede ir a pie. Ahora el problema que tenía 8 años y luego fue 4 el tamaño actual es talla 2. Nos estamos bastante cerca. Una vez más, ir al centro de estos dos elementos. Bien. Así que es una especie de lamentable que ahora que siempre vamos a la izquierda porque estamos redondeando hacia abajo. Pero eso está bien porque ahora tirar esto y todo lo demás, lo que nos deja con sólo 7. Vamos a darle un aplauso. Hemos encontrado 7 de nuevo. [Aplausos] Bueno. Claro. Espera por sólo 1 segundo más. A pesar de que este tipo de proceso siguiente tomó un poco más de lo que pensaba que sería, Francamente, su primera reacción fue la mejor, ¿verdad? Hemos encontrado 7 instantáneamente. Pero habríamos encontrado 7 más rápido, no importa lo que, en este ejemplo frente a esta porque si los números están ordenados, al igual que las páginas de un libro de teléfono, usted realmente puede cortar la mitad del problema una y otra vez y otra vez. Y no es tan fácil ver esto con tan sólo 8 números a diferencia de una guía telefónica de 1.000 páginas en el que realmente se ve visualmente, pero en este caso aquí cuando Sean estaba buscando a 7, ¿Cuántos pasos en el peor de los casos lo han llevado? >> [Estudiante] 7. 7 en el peor de los casos. Bueno, en el peor de los casos no 7 si hay 8 puertas aquí. Hubiera tardado 8 pasos. Así que si hay puertas n, podría haber tomado Sean un par de años n pasos. Ahora, en su caso, Alex, teniendo en cuenta que estos números se ordenan - y podemos inferir de esta especie a partir de lo que hemos hecho hasta ahora en esta historia - ¿cuál es el tiempo de ejecución del algoritmo más inteligente de Alex de partir de la mitad y luego repetir? [Estudiante] 3. >> Así que va a ser de 3, aproximadamente, si vas 8 a 4 a 2 a 1. Así que 3 pasos o, más en general, eso es log n de nuevo. Cada vez que estés reducir a la mitad y reducir a la mitad y reducir a la mitad y reducir a la mitad, que es una expresión de esta idea de log n. Y para que os lo hubiera tomado tan sólo 3 pasos, y de hecho lo hizo una vez que nos abrió las puertas de reducir a la mitad y reducir a la mitad, mientras que esto habría llevado Sean unos 7 u 8 pasos. Así que gracias por estar con nosotros este año. >> Gracias. Un placer conocerte. ¡Gracias a Alex. >> Lo mismo digo. [Aplauso] ¿Cuál es entonces la implicación real de esto? Ahora imagina que no es 8 puertas, que, francamente, todos nosotros podríamos encontrar algo tras 8 puertas bastante rápidamente con sólo romper los trozos de papel e ir con nuestros instintos. Pero ¿y si es un millón de puertas? ¿Y si es 4 mil millones puertas? En el caso de 4 billones de puertas, que realmente va a querer ir con el algoritmo de Alex, búsqueda binaria como vamos a empezar a llamar a él o dividir y conquistar, más en general, donde guardas reducir a la mitad y reducir a la mitad el problema, porque si usted tiene 4000 millones puertas, ¿cuántas veces se puede cortar 4 mil millones en la mitad? [Estudiante] 32. En realidad >> 32. Puede resolver esto en un pedazo de papel o en la cabeza. Vas 4 mil millones a 2 mil millones to 1 mil millones a quinientos millones, a 250 millones, punto, punto, punto. Y si lo hace la matemáticas, usted va a conseguir en efecto 32, y que en realidad se refiere a la informática ya que por lo general cuentan en potencias de 2. 2 a la 32 pasa a ser 4 millones. Así que hay una gran relevancia a este tipo de potencias de 2 en informática. Pero lo que unos 8 millones de dólares? ¿Cuántos pasos se que va a tomar si hay 8000 millones puertas? [Estudiante] 33. Así >> 33. ¿Y si hay 16 mil millones puertas? ¿Cuántos pasos se que va a tomar? [Estudiante] 34. >> 34. Podríamos continuar con este tipo de saciedad. Pero eso es algo muy poderoso. Puede introducir miles de millones de más entradas a su problema, pero no es gran cosa, usted acaba de tomar un bocado adicional fuera de él y por lo tanto nos da algo así como la búsqueda binaria o dividir y conquistar, de manera más general. Pero yo soy una especie de trampa, ¿verdad? En el caso del algoritmo de Alex, que tenía una ventaja sobre Sean. Ella sabía que estos números fueron ordenados, pero Alex no tiene que ordenar a sí misma. Yo de antemano se acercó a la pizarra y tipo de asegurado que dibujé a todos en forma ordenada, entonces los cubrió con papel. Pero, ¿cuánto trabajo hizo que me llevara? Si hubiéramos empezado con estos números en un orden aparentemente aleatorio - en este caso, estos números más simples, a través de 1 - 8 aquí cómo hacemos para ordenar estos valores? Si usted fuera un hombre dado a esta tarea, ¿qué tipo de enfoque intuitivo que le tomaría para ordenar un montón de números? Estas cosas fueron presentadas como piezas de un rompecabezas. Si. [Estudiante] Quisiera aprovechar cada número y compararlo con cada uno y seguir yendo a la izquierda. >> Bien, bien. Así que toma cada número, compararlo con el de al lado, y luego simplemente seguir moviéndose a lo largo de la lista, tipo de rejiggering cosas sobre la marcha. Así que aquí tenemos una oportunidad para tal vez un poco más a la gente a participar. ¿Tenemos 8 más voluntarios a quienes les encantaría subir? Un poco de presión menor, ya que usted no es el único. 1, 2, 3, 4, 5, 6, 7, 8. Vamos hacia abajo. Ustedes van a ser los números 1 al 8. Vamos a ver si podemos hacer esta clasificación para Alex mucho de la misma manera que lo hice por adelantado. 1, 2, 3, 4. Vaya por delante y si lo haría, línea sobre el escenario entre el atril y yo aquí en el mismo orden que la presentación en la pantalla. Uh-oh. Vamos a trabajar en el siguiente ejemplo. Oh, espera, espera. Aquí vamos. Espera. El siguiente ejemplo es ahora. Aquí tienes. Número 8. Vamos arriba. Está bien. Ordenar ustedes mismos de acuerdo con esto. Deslice un poco a un lado del atril aquí. Así que tenemos 4, 2, 6 - entrar allí, por aquí, justo ahí - 3. Si. Bien. Tú te vas por aquí. No, quédate ahí. Sí, justo ahí. No, yo estoy equivocado. Justo ahí. Bien, muy bien. Bien. Así que ahora vamos a clasificarlos en un orden creciente. ¿Cómo puedo ir haciendo esto? El algoritmo que se propuso hace un momento era por qué no acabamos de comparar las personas que son de tipo uno al lado del otro y luego corregir los errores, moviéndose de izquierda a derecha. Así que aquí tenemos 4 y 2, obviamente, fuera de orden. Vamos a intercambiar. Bien. Así que ahora me voy a mover en la línea. 4 y 6, nope. [Risas] 6 y 8, bastante bueno. 8 y 1, déjame intercambiar chicos. Está bien. Entonces, 8 y 3, intercambiar ustedes. 8 y 7, déjame intercambiar chicos. 5 y 8, excelente. Te doy una lista ordenada. Está bien. Así que no del todo. Pero es mejor porque los números más grandes - Caso en punto 8 - tiene una especie de burbujas por la izquierda, a la derecha. Así que tengo una de ellas correcta, pero se siente como esto no resuelve el problema bastante. Entonces, ¿qué propones que hagamos ahora? >> [Estudiante] Sigue haciéndolo. >> Le sigue haciéndolo. Y darse cuenta, una vez más, nos pusimos las cosas con sólo contar con todos los seres humanos tipo de inteligencia se organizan sobre la base de esa imagen, pero ahora tenemos que ser mucho más metódico. Tenemos que ser algorítmico de ello como si estamos escribiendo código - en este caso pseudocódigo verbal. Así que déjame intentarlo de nuevo. Eso funcionó bastante bien. No resolverlo. Pero cuando lo dude, sólo trato y vuelva a intentarlo. Entonces, 2 y 4, no ayudó más. 4 y 6. ¡Ah! 6 y 1, un poco mejor ahora. 6 y 3, bien. 6 y 7, 7 y 5, 7 y 8, bueno. Y usted sabe, es probable que pueda ignorar 8 ahora porque está al final de la lista. Tal vez no tiene que preocuparse de que alguien va más allá de él. Pero vamos a ver si eso es una suposición segura. Ahora está lista - maldita - Sin ordenar. Vamos a intentarlo de nuevo. Así 2 y 4, 4 y 1, 4 y 3. 4 y 6, bien. 6 y 5, bien. 6, 7, y 8, bueno. Pero note, ¿puedo parar aquí y dejar aquí ahora? [Estudiante] Sí. >> ¿Sí? ¿Qué pasa si uno de ustedes ha sido el número 9 todo el camino hasta allí? Hubiera sido ordenados. Bueno >>. Hubiera sido ordenados a la primera. Bueno. Así que vamos a volver de nuevo. Ya casi llegamos. 1 y 2, 2 y 3, 3 y 4, 4 y 5, 5 y 6, 6 y 7, 7 y 8. Yo estoy haciendo ahora, pero, de nuevo, estoy un equipo que sólo puede hacer lo que me dicen que hacer, y mi único recuerdo ahora es que en realidad acaba de hacer un poco de trabajo. Algo ha cambiado aquí. Así que técnicamente no han confirmado visualmente o mediante algoritmos que esta lista es, en efecto ordenada. Así que, por si acaso, sólo para ser anal sobre esto, vamos a hacer esta vez 1 más. Así 1 y 2, 2 y 3, 3 y 4. ¿Y sabes qué? Sólo por si acaso, voy a hacer un seguimiento de mi mano esta vez cómo muchos swaps hago sólo para que yo sepa la cantidad de trabajo que he hecho en realidad. 3 y 4, 4 y 5, 5 y 6, 6 y 7, 7 y 8. No hay acuerdos de intercambio. Así que ahora me legítimamente ser un idiota para hacer esto de nuevo porque si lo hacía ningún trabajo a través de este paso de los seres humanos, entonces es claro que eso vaya a ocurrir de nuevo si ninguno de ellos es una especie de azar de contradicción se mueve alrededor. Así que ahora me puedo parar. Ahora vamos a hacer la pregunta, ¿cuánto trabajo hizo esto realmente me toma? ¿Cuántos pasos se llevará? >> N al cuadrado. Sí, así que n al cuadrado. ¿De dónde sacas n al cuadrado de? Usted tiene que comprobar cada número - Hay un número n, y usted tiene que comprobar cada número con los números n otros. Bueno. >> Así es n al cuadrado. Bueno >>. Así que se siente como que podría muy bien ser n al cuadrado, ¿no? No ha n de estos chicos, 8 específicamente en este caso, pero cada vez que iba a través de esta lista estaba comparando la primera persona en contra de la segunda, el segundo contra el tercero una y otra vez y otra vez, y cuando llegué a la final, ¿qué debo hacer? Me rehice. Así que si generalizamos esta explicación, tenemos n personas y estoy haciendo, obviamente, 8 pasos, n pasos, cada vez que voy a través de este algoritmo. Pero, ¿cuántas veces en el peor de los casos tengo que ir a través de esta lista de personas? [Estudiante] N veces. Probablemente >> n, a la derecha, porque en el peor de los casos, lo que es probablemente el peor de los casos de acuerdo a estos chicos desde el primer momento? Si están completamente invertida orden porque supongamos mentalmente, let's - ¿Cuál es tu nombre? >> Bowen. Bowen. Bien. Así Bowen, ven aquí sólo por un momento. Supongamos que Bowen era aquí al principio del algoritmo, y no sabemos lo que todos los demás, pero aquí Bowen, de acuerdo con este algoritmo - y si quieres simplemente pasear conmigo - va a burbujear, como lo hizo la primera vez, todo el camino hasta el final. Pero supongamos que la persona al lado de Bowen fue el número 7. Tengo que volver atrás y obtener el número 7, lo que significa que tengo que ir todo el camino hasta aquí. Ahora tengo que tener ese mismo paseo con la persona que es el número 7. Pero ¿y si a continuación, el número 6 estaba junto a él también? Entonces tengo que volver atrás y obtener 6. Así que de nuevo, en cada iteración de este bucle estoy hablando con cada una de las n personas, y voy a tener que hacer n de estos paseos para asegurarme de que estoy tirando todos los elementos más grandes atrás y de atrás y de nuevo hasta el final de la lista. Así las cosas n n veces se encuentra n veces N o N al cuadrado. Así que aquí ya tenemos un algoritmo que ya no es n, que ya no es log n, en realidad es peor que cualquier cosa que hayamos hecho antes. Así que Alex tipo de suerte en que lo hice todo el trabajo por adelantado al parecer para ella, todo el trabajo costoso, así que podía disfrutar en este algoritmo de búsqueda binaria, que es de registro n. Pero esto es consistente con el tema del lunes. Nos dio un poco más de espacio, hemos utilizado más bits, con el fin de acelerar nuestro tiempo de funcionamiento. Tanto como que hay este trade-off entre el tiempo y el espacio, también podría ser justo equilibrio entre el tiempo dedicado a ordenar frente a preparar las cosas para ir y de hecho la ejecución de un algoritmo como búsqueda. Vamos a probar con la otra. Si ustedes no me importaría simplemente reorganizando rápidamente para que coincida con vosotros otra vez, vamos a intentar algo un poco diferente, donde no es tan sencillo como se acaba de arreglar todos los errores por parejas, lo cual es muy intuitiva. En lugar de eso será un poco más deliberado y hacer esto. Este también yo propondría es probablemente bastante intuitivo. Vamos a seleccionar la persona más pequeña de la lista una y otra vez. Así que aquí vamos. 4, usted es la persona más pequeña así que he visto hasta ahora, así que voy a recordar mentalmente que con sólo señala en usted por ahora. 2. Ooh! Olvídate número 4. Acabo de encontrar el elemento más pequeño de nuevo en esta lista. Voy a clase de acuerdo de eso. 6, 8. Ooh! 1. Adiós. Así que ahora voy a recordar el número 1. Sabemos que el 1 es el más pequeño, pero yo soy el ordenador. ¿Qué pasa si hay un 0? ¿Qué pasa si hay un -1? Tengo que seguir adelante. Así 3, 7, 5, nope. Bien. Así que el número 1 era el más pequeño. Permítanme seleccionar de la lista - nos volveremos ir por este camino - y poner arbitrariamente al principio de la lista. Ahora, espera un minuto. Que tipo de trampa. Si estos tipos no representan una lista de 8 personas, sino una matriz, 8 trozos de memoria contigua - ¿Te importaría dar un paso atrás por un momento? Hay realmente no hay espacio para ti aquí. Entonces, ¿cómo hacer espacio para - ¿Cuál es tu nombre? Sammy >>. Sammy >>. ¿Cómo podemos hacer espacio para Sammy? Realizamos movimientos que son los n delante de mí. >> Okay. Así que podemos mover las n personas que están delante de él, así que si ustedes quieren tomar un paso deliberado, dramático hacia la izquierda. Todos ellos hicieron que al unísono, pero la última vez que escribí algo de código, no puede ordenar de mover muchas cosas al mismo tiempo. Podríamos hacerlo en un bucle, una vez en movimiento todo el mundo a la vez. Así que si ustedes no me importaría dar un paso atrás a la derecha, Sammy y, si se puede dar un paso atrás porque todavía no hay sitio para ti, ahora vamos a hacer esto. ¿Dónde estaba Sammy hace un momento? Justo ahí. Así que hay una brecha allí. Por lo que podría trasladarse a punto de Sammy. Ahora, la siguiente persona a persona y ahora viene, ahora siguiente persona. Ahora tenemos espacio para Sammy. Ahora, alguien de la audiencia - que era bueno, que era correcto, me sentí un poco lento - lo que es más rápido? Si. [Estudiante] Una nueva serie? >> ¿Qué es eso? >> [Estudiante] Una nueva serie? >> Bien, bien. Por lo tanto compatible con el presente tema del comercio justo-offs, ¿por qué no simplemente hacer una nueva matriz  Sammy y luego va a nadar en el espacio delante de estas personas, por ejemplo, y sólo podemos comenzar a llenar una nueva matriz por completo. Esto también funcionaría. Pero yo no estoy interesado en gastar más espacio en la actualidad. ¿Qué hay otro enfoque? [Estudiante] Swap. >> Okay. Podríamos intercambiar estos 2 chicos. ¿Cuál es tu nombre? Mario. >> Mario. Así que Mario, que se encuentran actualmente aquí. Sammy, puede realizar copias de seguridad por un momento? Mario estaba aquí. No tenemos espacio para ti nunca más, así que si no te importa ir a donde Sammy está, vamos a poner Sammy aquí, y ahora yo diría que la operación de canje de Sammy era mucho más rápido. Hicimos una operación para cambiar estos chicos, o tal vez 2 para cambiar estos chicos, pero no hacer 1, 2, 3, 4, por lo que se siente mejor. Ahora, espera un minuto. Yo como que agravan el problema porque el número 4 era un poco estrecha al principio. Ahora el número 4 es un poco más a este fin, pero en realidad no sabe ni le importa eso. Así que esto es sólo mala suerte que el número 4 es un poco más lejos de su lugar de destino. Así que vamos a repetir ahora este algoritmo. En resumen, siempre que esa historia era, lo único que hizo fue caminar por la lista en busca de la persona más pequeña contados. Así que ahora vamos a hacerlo de nuevo. No tiene que preocuparse por Sammy más. Sólo podemos ir aquí. Ooh! Número 2. Esa es una cifra bastante pequeña. 6, 8, 4, 3, 7, 5. Bien, bien. Y por suerte, por casualidad, no tienes que mover - >> Willie. Willie porque está en su lugar ahora mismo. Vamos a hacer esto de nuevo y pasar por alto estos dos chicos. 6. Esa es una cifra bastante pequeña. Ooh! 8 es definitivamente más grande. 4. Vamos a centrarnos en 4. Ooh! 3 es aún mejor. 7 y 5. Entonces, ¿qué hacemos ahora con - >> Roger. >> Roger? Vamos a cambiar con el número 6. Así que si 6 y 3 le gustaría cambiar, ahora hemos tenido suerte de clase en el que el 6 está más cerca de donde debería estar, pero es sólo una coincidencia aquí. Así que vamos a ir ahora aquí. 8 es un número bastante pequeño. Ooh! 4 es más pequeño. 6, 7, 5. ¿Qué hacemos ahora? >> Swap. >> Exactamente. Así que ahora vamos a hacer este tipo de rápido. 8, 6, 7, 5. 5 ¿Dónde ir? Bueno. Bien. 6, 7, 8. 6 llega a quedarse donde está. ¿Cuál es tu nombre? >> Rosalie. Rosalie llega a quedarse donde está. 7 llega a - Vamos a ver. 7, 8. Bien. Así que 7 se pone a quedarse donde está. ¿Cuál es tu nombre? Amna >>. Amna >>. Así Amna llega a quedarse donde está, y el número 8 ya está donde debería estar ahora. Bien, bien. Se siente como si estuviéramos sólo la creación de trabajo para nosotros aquí, sin embargo. ¿Qué es en definitiva el tiempo de ejecución de este algoritmo? Si pensamos que estas personas no como 8, pero como n? >> Es n. Es n pasos, pero estamos comprobando cada vez. Bien. N, pero usted está comprobando cada vez? De acuerdo, pero si es n pasos, ¿no debería haber sido capaz de ordenar con sólo ir 1, 2, 3, 4? Oh! Bueno, eso es una gran diferencia. Así que n al cuadrado por qué? ¿Qué está pasando realmente? No hay n personas en esta lista, pero para encontrar la persona más pequeña en la lista en el peor de los casos, ¿cuántos pasos tengo que tomar? N. >> N, a la derecha, porque en el peor de los casos, el número 1 es todo el camino allí, así que tengo que ir por él o ella. Y luego, cuando finalmente se dan cuenta 1 era el más pequeño, entonces es bastante rápido para intercambiarlas. Pero ahora tengo que empezar desde el principio y buscar quién? La persona siguiente más pequeña, que es 2. ¿Dónde en el peor de los casos es de 2? Oh, Dios mío. Es todo el camino hasta aquí al final. Así que ahora que acabo de hacer otro n pasos, otra de n pasos. Y si tenemos n personas y en el peor de los casos la persona más pequeña es n pasos, eso es nuevo n n veces, por lo que de nuevo tenemos n al cuadrado. Esto no se siente tan bien. Y de hecho, incluso en el mejor de los casos - Supongo que parten ordenados - cuántos pasos se necesitan para mí usar este algoritmo para ordenar estas personas n? N al cuadrado. >> Oí n al cuadrado. ¿Por qué n al cuadrado? Debido a que usted todavía tiene que comprobar cada vez. Sí >>. Y hay que cambiarlos. >> A pesar de que nosotros, los humanos son una especie de omnisciencia en el sentido visual que podemos sólo un poco de ver que esto está ordenado, una computadora no es tan inteligente. Va a ver aquí y aquí y aquí, pero si lo que se busca es el elemento más pequeño, sólo se sabe que ha encontrado el elemento más pequeño de lo que punto? Una vez que estamos en el final. Pero en ese momento sólo ha encontrado el elemento más pequeño en la actualidad. No necesariamente saber algo más sobre el estado del mundo. Así que hay que ir una y otra vez y otra vez. Así que esta vez realmente se ven tonto porque estoy comprobando, vale, dos, tú eres la más pequeña, pero no sé que, en total todavía. 3, 4, 5, 6, 7, 8. Bien, bien. 2 era de hecho la más pequeña. Ahora vamos a buscar la inmediata inferior. Bien. 3, que está actualmente el más pequeño. Vamos a ver. 4, 5, 6, 7, 8. Bueno, tuve suerte de nuevo. 3 era de hecho en el lugar correcto. Pero yo voy a seguir haciendo esto una y otra vez y otra vez. ¿Cómo podemos hacer muy ligeramente mejor? En lugar de tener a la gente burbuja pares de menor a mayor para y en vez de ir arriba y abajo por la lista de selección de la persona más pequeña entonces, ¿por qué no en lugar insertar a estas personas en una etapa nueva lista a paso? Vamos a probar esto. Ahora voy a llamar a este tipo de inserción cosa. Así que aquí estamos aquí. Número 1. No me importa nadie más en esta lista. Mi objetivo ahora es poner el número 1 en el comienzo de una lista ordenada. Y yo voy a proponer ya que sólo tienen 8 trozos de memoria, arbitrariamente en estos momentos estoy en la pared entre mi lista supuestamente sin clasificar, y cualquier persona que está detrás de mí que voy a reclamar está ordenada. Así que ahora tenemos el número 1. Le quiero insertar en mi lista ordenada, así que sólo voy a mover mi pared por aquí, y ahora me dicen esta lista está ordenada, que esta lista sin ordenar - por lo menos hasta donde yo sé. No puedo ver todos los números a la vez. Ahora se me ocurre para encontrar el número 2. ¿Qué hago con él? Yo inserta ahora en la lista ordenada. Pero note lo fácil que era. Sólo tengo que mirar. El número 1 está ahí. Oh, obviamente 2 va hacia el lado de número 1. ¿Y ahora qué hago con 3? Te insertar en la lista ordenada. Pero eso fue muy fácil. Esto es muy fácil, es muy fácil, es muy fácil, muy fácil, muy fácil. Y ahora todo se ordena detrás de mí, y la cantidad de pasos que tomó? [Los estudiantes] N. >> por lo que es n. Tuvimos suerte. No fue hasta n ¿por qué? >> [Estudiante] Debido a que la lista fue ordenada. La lista ya está ordenada. Así que tuvimos suerte. Sin embargo, hemos diseñado un algoritmo que aprovecha este momento ese tipo de suerte, que mejor de los casos, por no perder tiempo innecesario. Así que ahora tenemos lo que llamaremos tipo burbuja donde la gente de clase brotan parejas. Ahora tenemos una especie de selección en el que arrancará la persona más pequeña y otra vez. Y ahora tenemos que ordenar la inserción en la que una especie de forma proactiva poner a la gente a la que pertenecen en una lista cada vez más ordenada. Si pudiéramos, un aplauso para estos chicos de aquí. [Aplauso] Vamos a tomar nuestro hijo de 5 minutos de descanso aquí. Y cuando regresemos, vamos a volar todos estos algoritmos fuera del agua con algo mejor. Está bien. Muchas gracias. Usted puede mantener los como recuerdos. Está bien. Estamos de vuelta. Y para resumir muy rápido, tuvimos que estos enfoques diferentes para la clasificación 3, todo el punto de que iba a llegar al punto en el que alguien como Alex podría buscar en una lista de números más rápidos que alguien como Sean pudo. Y aunque tenemos ejemplos tan sencillos con números 8, puede extrapolar fácilmente a 8 páginas, 8 mil millones de páginas web, o 800 millones de amigos en Facebook. Así que estos algoritmos sin duda puede escalar para ese tipo de valores, y las ideas son en definitiva los mismos. Así especie de burbuja fue el primero en que tipo de burbujeaba la persona más grande todo el camino a la derecha mediante el intercambio de personas por parejas. Luego tuvimos lo que llamaremos tipo de selección en el que un poco más deliberadamente no dejaba de mirar a través de la lista, seleccionar el menor número una y otra vez y otra vez, el resultado lógico de las cuales es que la lista está ordenada con el tiempo. Luego, en la tercera, inserté la gente en su lugar apropiado, y hemos hecho un ejemplo muy artificial en que la lista se ordenan ya, pero que iba a enviar el mensaje de que en caso de ordenación por inserción, usted puede tener suerte. Si los números ya están ordenados, que sólo va a tener que n pasos para confirmar tanto, mientras que la ordenación por selección que eres un poco más de visión de túnel y no siempre dan cuenta de que la lista ya está ordenada. Así que vamos a ver la ordenación de burbuja en acción aquí. En el siguiente ejemplo, estamos a punto de ver las barras verticales cuyas alturas representan los números para que podamos ordenar visualice clasificación de suceder. Cuanto menor sea la barra, más pequeño es el número, más grande es la barra, mayor es el número. Y vamos a jugar a esta velocidad predeterminada. Se va a mover un poco rápido por ahora, pero el rojo es lo que está mostrando 2 bares siendo comparación lado a lado. Y si usted mira de cerca, lo que pasa es que si las barras están fuera de servicio, la más pequeña se mueve hacia la izquierda, la más grande a la derecha, y luego seguir avanzando. Así que si hacemos esto una y otra vez, note que los más pequeños bares vamos a seguir avanzando lentamente su camino a la izquierda y los principales bares van a seguir su camino avanza poco a poco hacia la derecha. Y, de hecho, estamos empezando a ver un patrón hasta el final en el lado derecho como vimos 8 y luego 7 eventualmente burbujeando hasta el otro extremo de la lista humana. Así que esto se va a poner muy rápidamente un poco tedioso, así que permítanme dejar esto por un momento. Déjame cambiar la velocidad sea mucho más rápido. No voy a cambiar el algoritmo, sólo estoy haciendo la animación suceder más rápido. Aún burbuja especie, mismo algoritmo, pero ahora se puede ver mucho más rápido que nuestra manifestación verbal que los principales elementos de hecho burbujeando hasta la cima. Como acotación al margen, estos pequeños cuadrados en la parte inferior izquierda e inferior derecha son sólo pequeños recordatorios de cómo muchas comparaciones que haces. Pero por ahora, podemos centrarnos en la pirámide que está tomando forma, y ​​ahí va. El elemento más pequeño está a la izquierda, la más grande a la derecha, y todo lo demás en el medio. Ahora vamos a echar un vistazo en vez de ordenar la selección. Voy a seguir adelante y golpear Stop. Vamos a obtener un nuevo conjunto aleatorio de barras. Tipo de selección, recuperación, pasa a través de la lista una y otra vez y otra vez, arrancarse el elemento más pequeño. Así que aquí es una especie de selección. Parece que hay menos trabajo sucediendo ahora porque no estamos comparando pares pero esto es sólo una especie de cereza recogiendo los elementos más pequeños de derecha a izquierda. Eso llevó muy poco tiempo, así que hay una dicotomía ya. El hecho de que un algoritmo se dice que tomar el tiempo n al cuadrado, como especie de burbuja y como especie de selección, esas son realmente peores momentos de casos de funcionamiento. Por ejemplo, en el caso de, digamos, una especie de selección, De hecho, me estoy seleccionando la persona más pequeña y poner él o ella aquí, entonces lo estoy haciendo de nuevo, entonces lo estoy haciendo de nuevo, pero había una ligera optimización que podría hacer. Tan pronto como me mudé aquí el número 1 - Sammy en este caso - ¿qué tengo que hacer con él después de eso? >> [Estudiante] Déjalo. Déjalo, ¿no? Nada. Yo no necesito hablar nunca de Sammy otra vez, porque si yo hubiera seleccionado el elemento más pequeño y lo puso aquí, ¿por qué perder el tiempo yendo al final de mi lista entera? En la siguiente iteración déjame en realidad se mueven sólo con el número 2, sólo al número 3. Así que en realidad, no estaba haciendo las cosas n n veces. Yo estaba haciendo las cosas n, entonces n - 1 cosas, entonces n - 2 cosas, entonces n - 3 cosas, entonces n - 4, punto, punto, punto. Tenemos un poco de una serie geométrica, lo cual significa va a añadir los números cada vez más pequeños. No n + n + n + n, pero n + 7 + 6 + 5 + 4 + 3 + 2 + 1. Y lo que por lo general resulta ser - Me voy a arruinar mi consejo aquí sólo por un momento - que va a trabajar a ser algo así como n (n - 1) / 2 si tan solo tipo de mirada en la parte posterior de un libro de matemáticas en el que tienen todas las hojas de trucos para las fórmulas. Si acaba de añadir algo n + n - 1 + n - 2, que resulta ser algo como esto. Y si sólo un poco de multiplicar esto, que es n al cuadrado menos n / 2. Nunca dejé de señalar n al cuadrado, sin embargo, y eso es porque yo era una especie de tomar un atajo mental porque en realidad, n cuadrado menos n dividido por 2 es en realidad el verdadero número de pasos que un algoritmo de ordenamiento por selección como tomaría si realmente contaba hasta todas esas comparaciones y todo el trabajo poco ocupados que estábamos haciendo. Pero, francamente, una vez que n llega a ser como un millón o un billón, ¿quién diablos le importa si usted está haciendo un billón menos un cuadrado dividido por 2 mil millones? Mil millones cuadrado es un número enorme. Usted puede tomar otros mil millones fuera de ella con - n. No es una gran cosa. Así que cuanto más grande es obtener los números, los menos importantes estos términos son más bajas ordenadas. A quién le importa si se divide por 2, si estás hablando de miles de billones de números de pasos? Así que en general, los científicos de la computación tienden a tirar todo pero el mayor plazo, y sólo un poco de simplificar el mundo y decir que ese algoritmo tomó medidas aproximadamente n al cuadrado. Ese es el tiempo de ejecución de un algoritmo. Así que vamos a volver a esto en un momento con algunos ejemplos concretos, pero por ahora, que es una especie de la motivación intuitiva detrás sólo simplificar nuestro mundo y hablando de los términos más importantes en lugar de entrar en todas estas fórmulas de fantasía. Así que fue una especie de selección, y nos dieron un poco de suerte allí. Echemos un vistazo a la ordenación por inserción. Déjenme seguir adelante y comenzar éste a su vez. Ahora note el patrón que está pasando es un poco diferente, y comenzamos con números aleatorios, pero si realmente contar el número de pasos en el peor de los casos, si la lista comenzó por completo en el orden correcto, que sólo tomaría n pasos para darse cuenta de lo mismo. Pero si la lista eran realmente hacia atrás - por ejemplo, en este caso aquí - después se da cuenta que en realidad tenemos que hacer mucho más trabajo en este caso. Y hay que tipo de sentir a usted como esta es una especie de trabajar más duro para obtener los elementos más pequeños a la izquierda, y eso es porque tenemos mala suerte. La lista fue ordenada accidentalmente al revés. Por el contrario, con el tipo de inserción si imitamos lo que hicimos con nuestros seres humanos aquí comenzando con todos ordenados y luego empezar, es un algoritmo bastante bien, ¿no? Ya está, de hecho, ordenados. Así que vamos a tratar de resumir exactamente cuánto tiempo estas cosas nos están llevando mediante la introducción de un poco de jerga o anotación que en realidad es mucho más simple que el tipo de fanciness sugiere. Esta cosa aquí, este O grande en la pantalla, es lo que un científico de la computación en general a utilizar para describir el tiempo en el peor caso de ejecución de un algoritmo. Nuevamente, al peor de los casos, es totalmente dependiente del contexto. ¿Qué queremos decir con el peor caso totalmente varía en función del problema que estamos hablando. Pero en el caso de la clasificación, ¿cuál es el peor escenario posible? Todo está al revés, ya que sólo se siente como que significa mucho trabajo para nosotros. Me he apuntado algunos de los algoritmos que hemos visto hasta el momento: búsqueda lineal, la búsqueda binaria como la guía telefónica o los trozos de papel, a continuación, ordenar especie de burbuja, una especie de selección, inserción y como hemos visto con nuestros seres humanos, y luego un otro que está al final va a ser llamado merge sort. Así, en búsqueda lineal en el peor de los casos, ¿cuántos pasos se necesitan para encontrar el número 7 si hay puertas n como Sean cara? >> [Estudiante] N. N. Así que vamos a escribir gran O de n. Yo sólo voy a llenar algunos espacios en blanco. Esto es sólo una red de espacios en blanco. Pero en el mejor de los casos con la búsqueda lineal, 7 podría haber sido en el principio de la lista, Sean y podría haber empezado a buscar en el inicio de la lista. Así que si usted está utilizando una búsqueda lineal y sólo la comprobación de izquierda a derecha o de derecha a izquierda tal vez - son equivalentes - en el mejor de los casos la cantidad de pasos podrían búsqueda lineal, como algoritmo de Sean, tomar? A sólo 1 paso. Así que voy a decir que es la notación omega. Esto es sólo omega capital. Omega es sólo la forma sexy de decir mejor de los casos el tiempo de funcionamiento. Así que en el mejor de los casos el tiempo de ejecución es un solo paso o número constante de pasos - 1 en este caso -, pero en el peor de los casos, oh grande, en realidad es de n pasos. Y este de aquí, theta, estamos en realidad no va a mirar ahora mismo. No es relevante para este ejemplo en particular. Pero ahora vamos a tratar de búsqueda binaria. En el peor de los casos con la búsqueda binario, ¿cuántos pasos le va a tomar para encontrar el número 7 o lo que está buscando? >> [Estudiante] log n. Todavía va a tomar n de registro porque al igual que Alex mala suerte cuando realmente trabajado en el problema metódicamente y ella no encuentra el número 7 hasta la última puerta que miraba, aunque, para ser justos, se puso a tirar algunas puertas en el camino, búsqueda binaria en el peor de los casos tiene una duración de log n. Y de nuevo, que habla de este dividir y conquistar. Pero ¿qué pasa en el mejor de los casos? Y Alex realmente experimentado ese caso mejor derecho cuando subía al escenario. ¿Cuántos pasos se que tomar en la búsqueda binaria? >> [Estudiante] 1. 1, sólo porque ella tuvo suerte. Pero eso está bien porque se refiere a omega mejores casos, las mejores entradas de casos, incluso si es sólo pura suerte al azar. Ahora bien, esto también vamos a sólo un poco de blanco licencia por ahora. ¿Qué tal ahora ordenamiento de burbuja? En el peor de los casos con una especie de burbuja, todo el mundo está en orden inverso, por lo que tenemos que hacer un montón de burbujas. Pero la cantidad de pasos que se van a tomar en el peor de los casos? >> [Estudiante] N al cuadrado. Esta fue la n al cuadrado, ya que si lo piensas bien, si la lista es totalmente al revés - 8 es por aquí, una es por aquí - como cosa comience a burbujear, el número 8 se va a mover de esta manera, de esta manera, Así, de esta manera, pero ¿dónde está el número 7 en el peor de los casos? Aquí está todavía allí. Así que tenemos que hacerlo una y otra vez. Y ahí es donde obtenemos n pasos, entonces n - 1 pasos, entonces n - 2 pasos. Y si usted toma mi palabra para ella - que si lo multiplicamos tipo de salida, Es más o menos cuadrada n al final con algunos otros términos que sólo tendremos que ignoran por ahora - a continuación, en el peor de los casos especie de burbuja es n al cuadrado, más o menos. Pero ¿qué pasa con el mejor de los casos con una especie de burbuja? ¿Cuál es el mejor de los casos? Todos los números se ordenan ya. ¿Y cuál fue la heurística que utiliza, el truco que usé, para darse cuenta de que yo había hecho ningún trabajo y por lo tanto podía dejar antes de tiempo? [Estudiante] Compruébelo usted mismo una vez. >> Compruébelo una vez. Pero, ¿qué estaba haciendo en el camino? Yo estaba un seguimiento de cómo muchos swaps que hice. Y me di cuenta si no he contado alguna swaps en mis dedos, entonces me he hecho ningún trabajo. Desde luego, no debemos tratar de hacer ningún trabajo nuevo, así que puedes parar. Así que en el mejor de los casos de tipo burbuja cuando la lista ya está ordenado, ¿qué diría la notación omega es, el mejor de los casos el tiempo de funcionamiento? Es sólo n. Tenemos que hacer algo de trabajo, pero sólo tenemos que hacer un paseo vale la pena de trabajo. Y aquí también voy a dejar esta parte en blanco. Y ahora ordenamiento por selección. Selección de tipo me había arrancando la persona más pequeña y otra vez. ¿Y qué decimos que el tiempo de ejecución de que fue eso? Fue n al cuadrado en el peor de los casos. Y, por desgracia, en el mejor de los casos también es n al cuadrado porque no tengo el tipo de vista omnisciente de todo el mundo; Lo único que sé sobre una iteración completa que he encontrado de hecho la persona más pequeña. Así que tipo de ordenación por selección chupa en ese sentido, pero lo bueno es que es algo intuitivo. Es bastante fácil de codificar, porque todo lo que tienes que hacer es escribir un par de bucles for anidados, típicamente, que pasa a través de buscando el elemento más pequeño y luego se pone el elemento más pequeño en el que pertenece al final de la lista. Así que también aquí va a haber un trade-off. La cantidad de tiempo que le lleva a pensar y desarrollar algo realmente escribiendo código muy bien podría tomar más tiempo si quieres un mejor desempeño y más rápido algoritmo. Pero si realmente sólo un poco de algo de código para arriba rápido y sucio y sólo un poco de tomar la idea más estúpida posible que se pueda imaginar, que pueden tardar unos minutos en el código, pero con grandes conjuntos de datos el algoritmo puede tardar horas en ejecutarse. Y aunque yo en la universidad a veces hacer estas concesiones. Sería 3am, yo estaba tratando de analizar un conjunto de datos muy grande relacionada con la investigación sobre la seguridad que estaba haciendo, y fue bien pasar 5 minutos ajustar mi programa para analizar los datos e ir a dormir o pasar 8 horas en llegar apenas a la derecha para que se ejecute de inmediato y no ir a dormir. Y por lo que también es una especie de una decisión consciente. Menor tiempo de desarrollo, más horas de sueño. En retrospectiva, probablemente no debería alentar a que cuando el objetivo aquí es para optimizar la calidad del código, sino que también en el mundo real es muy razonable compensación. Menos tiempo, menos rendimiento o viceversa. Así que aquí tenemos por fin la oportunidad de hablar de theta. Theta notación es algo que los informáticos pueden llevar en una conversación O cuando son grandes y omega pasar a ser el mismo. Usted dice theta para enviar el mensaje de que realmente se trata de una especie de apretado atado. No importa si el escenario es bueno o malo, es n al cuadrado. Así que no es sólo relevante en estas historias aquí. La ordenación por inserción es la última vez que miré, donde yo estaba introduciendo a todos en el lugar correcto. En el mejor de los casos lo que era el tiempo de ejecución de la ordenación por inserción como lo vimos aquí? [Estudiante] El mejor de los casos? >> El mejor de los casos. Se N, porque en el mejor de los casos todos ordenados, y Sammy y nadie realmente tenía que moverse en absoluto. Ellos ya estaban en su lugar correcto. Así tipo de inserción en el mejor de los casos es, en este caso, n. Pero en el peor de los casos es una especie de n al cuadrado. ¿Por qué? Si mi lista de los humanos es en orden inverso, La primera vez que inicia con el número 8 y lo inserte o ella en la posición correcta, que está justo aquí. Yo como que se mueven a un lado. Estos chicos no están ordenados, él o ella se ordenan. Pero ahora me ocurre para encontrar que viene? >> [Estudiante] 7. 7 en el peor de los casos, porque es en orden inverso. Así que aquí es 7. ¿Dónde 7 pertenecen? Definitivamente detrás de mí. Pero ahora 7 en realidad no pertenece inmediatamente detrás de mí, pero detrás de la número 8, así que tengo que decir: "Perdón, número 8, ¿podría avanzar en este sentido "Para hacer sitio a 7?" Ahora me encuentro con 6. "Oh, perdón, número 8 y número 7, se puede mover para dar cabida a 6?" En otras palabras, con ordenación por inserción, a pesar de que no estoy haciendo mucho movimiento, la gente detrás de mí están haciendo mucho más trabajo, y eso tiene que costar tiempo a alguien. Va a costar el tiempo en la computadora. Así, en el caso de la ordenación por inserción aún sufrimos. Si usted comienza a sumar el número total de pasos, terminamos golpeando aproximadamente n al cuadrado porque estos chicos tienen que hacer espacio para el ser humano que se inserta de nuevo en la lista. Y así, en este caso theta no es sólo aplicable a la historia particular en cuestión. Eso es todo lo agradable y bueno. Tenemos estas formas diferentes de hablar 3 sobre el tiempo de ejecución. Pero ¿qué significa esto realmente significa en términos reales si realmente tratar de codificar un algoritmo? Permítanme proponer que hay un algoritmo aún mejor por ahí que en sí tiene algunas ventajas y desventajas. Vamos a llamarlo merge sort, y es una especie de este algoritmo mágico que sólo funciona más rápido alguna manera, y es tan fácil de expresar, al menos en pseudocódigo. La implementación de este tipo de combinación algoritmo va a ser como sigue. Cuando te dan n elementos - los números N, n personas, lo que sea - Primero hay una comprobación de validez. Si n es menor que 2, fusionar tipo sólo se detiene. Se vuelve, por así decirlo. ¿Por qué parar si n es menor que 2? >> [Respuesta de los estudiantes inaudible] Derecha. Y de nuevo, n no es el número en la lista, n es el tamaño de la lista. Si n es menor que 2, que significa que su lista es o bien 1, donde usted está, obviamente, según si se trata de un número, o 0, en cuyo caso no hay nada que ordenar, por lo que necesitamos este tipo de caso base. Si la lista es tan corta que sólo hay nada que hacer, literalmente, no hacen nada. Retorno. De lo contrario reordenar la mitad izquierda de los elementos, a continuación, ordenar la mitad derecha de los elementos, luego fusionar las dos mitades ordenadas. Este tipo de parece un poco tramposo el que te estoy preguntando cómo ordenar los elementos y que me estás diciendo, "Ordenar la mitad izquierda, ordenar la mitad derecha". Yo soy como, "Está bien. ¿Cómo ordenar la mitad izquierda?" "Ordenar la mitad izquierda de la mitad izquierda, ordenar la mitad derecha de la mitad izquierda, y luego hacer". Eres amable de cíclicamente definir lo que significa ordenar, pero resulta que en realidad es brillante en este caso. No es verdaderamente este ciclo vicioso que nunca termina porque se acaba cuando? >> [Estudiante] Al llegar a una cosa. Al llegar a una cosa. Así que aunque usted puede comenzar con 8 personas y digo: "Ordenar la mitad izquierda de estas personas, estas 4 personas, "entonces yo digo:" ¿Cómo se puede ordenar la mitad izquierda? " "Bueno, ordenar las 2 personas aquí". Y entonces es como, "Todo bien derecho,." "¿Cómo se clasifica la mitad izquierda de esas personas?" "Sólo una persona resolver esto aquí". ¿Cuál es la revelación brillante ahora? Tengo que ordenar una persona. Hecho. Yo no tengo que hacer ningún trabajo. Pero ahora tengo que ordenar esta persona, pero son una sola persona, no hay nada que hacer. Así que la magia aparentemente es en este tercer paso: combinar las mitades según. Así tipo combinar aprovecha esta brillante idea de que si se rompe un gran problema por en 2 más pequeños, de tamaño idéntico problemas y entonces sólo tipo de pegamento las soluciones más pequeños juntos en el extremo, Propongo que se puede hacer mucho, [golpeteo] mucho mejor que cualquier tipo de selección o la ordenación por inserción. De hecho, he estado ignorando que durante media hora, pero yo realmente no sé lo que está pasando fuera hoy. [Zumbido] [risas] Así que vamos a ver si podemos ver esto con un poco de ayuda de nuestro amigo Rob Bowden. Hay 2 grandes pasos en el proceso de la especie de mezcla. En primer lugar, continuamente dividir la lista de copas en dos mitades hasta que tengamos un montón de listas con sólo 1 taza en ellas. No te preocupes si una lista contiene un número impar y no se puede hacer un corte perfectamente limpio entre ellos. Sólo arbitrariamente escoger cuál desea incluir la taza extra cm Así que vamos a dividir estas listas. Ahora tenemos 2 listas. Ahora tenemos 4 listas. Ahora tenemos 8 listas con una sola taza en cada lista. Así que eso es todo por el paso 1. Para el paso 2 que repetidamente mezcla pares de listas usando el algoritmo de fusión que hemos aprendido antes. La fusión de 108 y 15 nos encontramos con la lista de 15, 108. La fusión de 50 y 4 nos encontramos con 4, 50. La fusión de 8 y 42 nos encontramos con 8, 42. Y la fusión de 23 y 16 nos encontramos con 16, 23. Ahora todas nuestras listas son de tamaño 2. Observe que cada una de las 4 listas está ordenada, para que podamos comenzar la fusión de pares de listas de nuevo. La fusión de 15 y 108 y 4 y 50 que primero tome la 4, a continuación, la 15, a continuación, la 50, entonces el 108. La fusión de 8, 42 y 16, 23, primero tome el 8, el 16, a continuación, la 23, la 42. Así que ahora tenemos sólo 2 listas de tamaño 4, cada uno de los cuales está ordenada. Así que ahora nos fusionamos estas dos listas. En primer lugar tomamos el 4, luego tomamos el 8, luego tomamos el 15 y 16 y 23 y 42 y 50 y 108. Y hemos terminado. Ahora tenemos una lista ordenada. Rob era una especie de aprovechar algo que todavía no hemos hecho. Se sugirió, pero en realidad no lo hacen. Estaba haciendo algo físicamente con las copas que sugiere pasaba algún recurso, además de tiempo. >> [Estudiante] Espacio. >> Era el espacio. El hecho de que él tenía esta especie de bi-nivel de la mesa donde tenía espacio aquí y el espacio aquí abajo en realidad estaba dando a entender que él está usando espacio doble como cualquiera de nuestros algoritmos hasta ahora - sort ordenación por inserción, una especie de burbuja, o de la selección - pero él estaba aprovechando este espacio adicional a la clase de cosas se mueven hacia atrás y adelante mientras que mantener las cosas en orden. Y aunque se siente como llegamos a una lista ordenada, que se sentía como si se tomara un tiempo. En realidad, lo que Rob estaba haciendo era exactamente este algoritmo. Primero tomó el problema de tamaño n, dividido en una mitad izquierda y una mitad derecha. Fue entonces cuando se trasladó de las copas. Luego se repite el proceso. Se divide en 4 2 juegos de 2 aquí y aquí más. Entonces se repite este proceso y se dividieron en 2 grupos de 2 1 para cada uno de los vasos de varios. Y ahí es donde surge la brillante oportunidad. En ese momento de la historia, Rob tenía 8 listas de tamaño 1, todos los cuales fueron ordenados ya. Entonces ¿qué hizo proceder a hacer? Pairwise tomó esta lista ordenada y esta lista ordenada y se fusionó ellos. Luego tomó ésta y las fusionó, entonces éste y las fusionó, entonces éste y ellos se fusionaron. Y entonces ¿qué hizo después? Luego volvió a fusionar las listas más grandes y luego volver a fusionar las listas más grandes. Y si usted piensa acerca de esto sólo intuitivamente, por ahora, ¿qué estaba haciendo en realidad? Fue dividiendo el problema en un medio, en un medio, en un medio, en un medio con el fin de obtener estas listas pequeños supermercados. Entonces él era una especie de combinación de dobles, dobles, dobles de matrimonio,. Así que estaba haciendo el doble de trabajo, como hemos visto hasta ahora con todo lo que implica dividir y conquistar, pero no es gran cosa. Trabajar el doble que no es una gran cosa. Es sólo un factor constante. Y al igual que nuestra expresión aritmética antes, yo sólo voy a tachar factores constantes como los tiempos 2. A quién le importa? Si se trata de 2 mil millones de veces 2, que sigue siendo un montón de pasos. Así que este paso fusión parece ser la idea clave. Vamos a caminar a través de este justo antes de que numéricamente - Oh, eso no quiere continuar todavía. Vamos a caminar a través de este numéricamente sólo para ver realmente cómo funciona este sistema. Esta animación es más que nada un hombre poco pobre. Vamos a proponer esto. El tiempo de ejecución de tipo fusión - sólo tenemos una manera de hablar de esto. Esto no es matemática, esto es sólo un poco de una manera sucinta de expresarnos. Así que T representa el tiempo y n representa qué? >> [Estudiante] El tamaño de la - [Malan] El tamaño del problema, el número de personas. Así que estoy afirmando que el tiempo de ejecución para ordenar n personas va a ser 0 tiempo si n es menor que 2, porque si usted tiene una taza o tazas no, no tienes nada que ordenar. Pero en general, me voy a proponer que el tiempo de ejecución para ordenar n elementos va a ser el tiempo que toma para ordenar la mitad izquierda, más la mitad derecha plus - Qué es adicional + n? >> [Estudiante] tipo de mezcla. [Malan] De hecho, es la fusión, ya que si tiene n / 2 elementos aquí y tienes que n / 2 elementos aquí, ¿cuánto tiempo se necesita para unirlos? Al igual que Rob, tienes que arrancar esta por aquí, tal vez arrancar por aquí, arrancar por aquí, por aquí desplumar, desplumar aquí. Usted tiene que tocar cada una de las copas de una vez. Y si hay 4 tazas 4 tazas más, eso es 8 tazas o, más generalmente, 8 tazas n. Así que el paso de la fusión se puede expresar como n, y que literalmente implica el número de veces Rob tocado físicamente uno de los vasos de espuma de poliestireno. Así que vamos a hacer ahora un ejemplo arbitrario. Si hay 16 tazas, ¿cuál es el tiempo de ejecución de la clasificación, utilizando el algoritmo de Rob, 16 tazas? Es 2 veces la cantidad de tiempo que toma para ordenar 8 tazas porque tenemos 8 tazas de aquí, 8 tazas de aquí. No sé cuánto tiempo que lleva, así que vamos a generalizar como T por el momento. ¿Quién sabe lo que es? Pero ahora puedo ordenar de forma recursiva o varias veces la misma pregunta. ¿Cuánto tiempo se tarda en ordenar 8 tazas? 8 tazas de te voy a decir toma la cantidad de tiempo que se necesita para ordenar 4 tazas más tazas 4, a continuación, los combina juntos. Bien. Estamos entrando en un ciclo ya. ¿Cuánto tiempo se tarda en ordenar 4 tazas? El tiempo que toma para ordenar 4 tazas es 2 tazas más tazas 2 sorting más el proceso de fusión. Bien. ¿Cuánto tiempo se tarda en resolver dos tazas? 2 tazas es la cantidad de tiempo que se necesita para ordenar 1 taza más el tiempo que toma para ordenar otra taza más la cantidad de tiempo que tarda en fundirse, que es sólo 2. Bien. Última pregunta. ¿Cuánto tiempo se tarda en resolver una taza? Este es el caso base que predijimos que había tocado antes. El hecho de que no toma ningún trabajo en absoluto para ordenar el más pequeño de los problemas significa que ahora, una especie de estilo de la escuela primaria, podemos ir comenzar a tapar estos números hacia adentro Ahora sabemos lo que T es de 1, por lo que se puede conectar en 0 para T de 1. Eso me dará la respuesta a la T de 2, que luego puede conectar más arriba. Eso me dará T de 4, que puedo conectar más arriba. Eso me dará T de 8, el cual puedo conectar más arriba. Y si realmente hacen que las matemáticas mediante la conexión de estas respuestas, Entonces consigo T de 16 es 64. ¿Y qué hace 64 representan? Si T es 16, si, es 16 veces 4. Así que me dicen ahora que el tiempo de duración de esta cosa llamada merge sort - y esto va a ser el más lujoso de los que hemos visto hasta ahora - Se va a llamar n log n porque ¿cuántas veces puede Rob dividir un montón de copas por la mitad? Iniciar sesión n. Es el mismo que el ejemplo de libro de teléfono, que es el mismo que el ejemplo de auto-escrutinio. ¿Cuántas veces se puede dividir algo por la mitad? Sin embargo, hay un paso fusión. Puede que tenga que dividir las copas en la mitad otra vez y otra vez y otra vez, pero cada vez que vamos a tener que fusionarse. Y hemos dicho que la fusión tazas n tiene n pasos porque hay que arrancar una taza, arrebatar la copa, y tiene que tocar cada taza una vez, al igual que Rob hizo. Así que si estamos haciendo algo log n veces y estamos haciendo las cosas n en cada una de esas iteraciones, cada uno de esos halvings, tenemos n log n veces. Así que si enchufar en 16 en este ejemplo, 16 horas de registro de 16 - no te preocupes acerca de por qué este es el caso por ahora porque no he llegado a la base - pero log de base 2 de 16 es 4, 16 veces 4 es 64. Pero por el contrario, si se hubiera utilizado especie de burbuja o tipo de selección o tipo de inserción con 16 números, lo que el tiempo de ejecución hubiera sido si n es 16? Sería 16 al cuadrado, que es de 256, lo que incluso si usted no ha seguido completamente todas las matemáticas, 256 es mayor que 64. Eso es realmente la comida para llevar mágico aquí. Y darse cuenta de que a través de este trabajo en pequeños ejemplos de lo que quieras en un conjunto de procesadores hace que sea mucho más intuitivo. Pero lo que realmente significa en términos de la sensación de este algoritmo es la siguiente: Si realmente se ven en especie de mezcla aquí - me deja arrancar en esta ventana aquí - este es un ejemplo ligeramente diferente en que podamos tener todos los 3 de estos algoritmos - burbuja, selección y combinación - simplemente uno junto al otro. Todos ellos han comenzado con barras al azar, y eso es bueno. No se tiene una ventaja fundamental sobre el otro. Voy a hacer clic en un momento en cada una de estas animaciones - Start, Start, Start - tan rápido como pueda para que, a grandes rasgos, todos comienzan al mismo tiempo, y vamos a considerar que peor caso ordenamiento de burbuja de tiempo en marcha es lo que? >> [Estudiante] N al cuadrado. N al cuadrado. Peor de los casos especie de Selección tiempo de funcionamiento es? N al cuadrado. Y especie de combinación es aparentemente - incluso si usted no acababa de seguir todas las matemáticas ahora, que va a ser mucho más intuitivo a través del tiempo - es, decimos, n log n veces. Y como log n es estrictamente menor que n una vez que tengamos los números grandes, n veces log n es menor que n veces n o n al cuadrado. Entonces, ¿qué se siente al ser en realidad un algoritmo mejor en términos de tiempo de ejecución, n log n veces en lugar de cuadrado n? Aquí vamos. Clic, clic, clic. Eso es lo que significa usar algo como especie de mezcla. Tenemos un momento. Vamos a ver lo que pasa aquí. [Risas] ¿De quién es el dinero en especie de burbuja? Más bien depende de la entrada de vez en cuando. Vamos a ver. Vamos. Se siente como si estuviera poniendo al día. >> [Estudiante] Vaya, una especie de burbujas! [Estudiantes murmurando] [Malan] Sí, sí. [Los estudiantes murmuraban] Vaya, vaya, vaya! [Todos aplausos] [aplausos] Así que ahora con una demostración última, final, si es un poco difícil para envolver su mente alrededor de las matemáticas o una especie de visualización allí, se puede oír las velocidades de diferentes algoritmos de manera diferente. Se trata de una animación hecha a alguien que en realidad suena asociados con el proceso de intercambio y la altura de las barras. Como vamos a ver aquí, hay unos cuantos algoritmos de ordenación por ahí que la gente ha pensado. Este primero va a ser una especie de inserción, y esto va a volar a través de y le dará una sensación audible de cómo funcionan estos algoritmos diferentes. Aquí está la ordenación por inserción. [Pitido electrónico] [Malan] ordenamiento de burbuja. [Rápido pitido electrónico] [Malan] tipo de selección. [Rápido pitido electrónico] [Malan] tipo de mezcla. [Pitido electrónico] [Pitido ralentiza] [risas] [Malan] sort Gnome. [Pitido electrónico] Esto es CS50. Nos vemos la semana que viene. [Aplausos y vítores] [CS50.TV]