ALTAVOZ: Muy bien, esto es CS50. Este es el final de la tercera semana, y si usted no ha tomado ventaja ya, saben que habrá almuerzo este viernes, como de costumbre, donde se puede disfrutar de una buena conversación y la comida en Fire and Ice con algunos de CS50 de el personal y los compañeros de clase. Dirígete a esta URL aquí. 

Ahora usted puede recordar, o usted pronto puede estar familiarizado con, estas cosas aquí, que se dan al final del semestre para muchas clases. Libros azules El llamado examen, en el que usted escribe sus respuestas a los exámenes. Ahora tengo aquí 26 de tal libros azules, sobre cada uno de ellos se escribe un nombre, de la A a la Z. Y de hecho, los nombres son tan simples, A a la Z. Y uno de los objetivos en la mano hoy va a ser la de continuar lo empezamos el lunes, lo que no es tanto mirar el código, pero en realidad mirando ideas y la resolución de problemas. Una de las metas y promesas de este curso es que le enseñe a pensar más con cuidado, más metódicamente, y para resolver problemas de manera más eficiente. Y, de hecho, podemos hacer que realmente sin siquiera tocar una línea de código. Así que tengo un par de elefantes hasta hoy, naranja y azul, si pudiéramos conseguir un voluntario, tal vez desde más atrás de lo habitual. ¿Qué hay ahí, vamos hacia abajo. El objetivo de la cual va a ser a ayudar además administrar este examen aquí. Cuál es tu nombre? 

AUDIENCIA: Mary Beth. ALTAVOZ: Mary Beth, vamos arriba. A ver si el micrófono aquí para usted. Encantada de conocerte. 

AUDIENCIA: Mucho gusto. ALTAVOZ: Muy bien, así que tengo aquí los libros azules de la A a la Z, y yo voy a pretender que Tengo uno de los estudiantes, y que van a venir en un tanto al azar al final de un bloque de examen de tres horas por lo que están terminando de alguna Para semi-aleatorio como éste. Ahora su trabajo en un momento va a ser-- esto es en realidad la forma en que obtienen convertido en al final de la clase, más probable. Su trabajo ahora va a ser, bastante simplemente, para ordenar estos libros azules para nosotros de la A a la Z. 

AUDIENCIA: Oh, esto es va a tener para siempre. 

ALTAVOZ: Y vamos a ver al hacer esto, no hay presión. AUDIENCIA: No, no hay presión ni nada. 

ALTAVOZ: Y para la diversión, vamos a poner un temporizador. 

AUDIENCIA: Muy divertido, muy divertido. 

ALTAVOZ: Puedo sostener el micrófono para usted. Muy bien, acabamos duplicó nuestra velocidad. Así que mientras tanto, permítanme plantear lo que es va a ser la pregunta para Mary Beth es lo que está haciendo, cómo es ella va sobre solucionar esto? Y, de hecho, puede que no tenga Ha pensado alguna vez acerca de algo tan simple como cuando usted escoge hasta 26 libros como éste, que no tienen un producto natural ordenando a ellos. ¿Cuál es el proceso de que en realidad se utiliza? Es bastante aleatorio sólo escoger el primero que se ve y ponerlo en su lugar? ¿Es primera vez que mueve sus manos alrededor de en busca de una continuación en busca de B? ¿Es usted echa un vistazo a una par de ellos al lado del otro y decir, espera un minuto, este no está bien, y luego intercambiar el orden? Vimos ya el lunes de que hay un número de maneras en el que podemos hacer esto, y de hecho, como nos acercamos al final aquí, Yo tomaría nota quizás de lo que Mary Beth está haciendo. Tenemos unos montones al parecer, un uno más grande, tres más pequeñas. 

AUDIENCIA: yo les estoy ordenando cuando me encuentro con dos cartas que sé que están juntos en una secuencia, Los pongo juntos para que no lo hago tener que preocuparse de mantener pista de toda una fila de libros. Es sólo que, oh, A es primero, Tengo esta pila aquí. ALTAVOZ: Entonces, casi como piezas de un rompecabezas que tener la forma derecho a coincidir entre sí. AUDIENCIA: Más o menos, sí. ALTAVOZ: OK, excelente. Y ahora cada uno de estos pilas se ordenan presumiblemente? 

AUDIENCIA: Si. 

ALTAVOZ: Muy bien, de la A a la Z. Todos bien, felicidades, lo hicieron. Usted tiene su opción. Azul? Muy bien, gracias por eso. Así que Mary Beth se proponía lo que su enfoque era, pero lo que es otro enfoque de cómo podría ir sobre clasificación de estas cosas? ¿Qué habría hecho usted? El récord a batir habría sido un minuto y 50 segundos más o menos, además de los que más me olvidé de contar. ¿Qué habría hecho usted? ¿Sí? AUDIENCIA: Tome la pila. Comience desde el principio. Revise sus papeles. Y si el superior es mayor que, tal vez, que son, el inferior es más alto, entonces cámbielos. 

ALTAVOZ: OK, así que comenzar en la parte superior y la parte inferior, y luego su forma de trabajo hacia el interior de esa manera, el canje de ellos? OK, así que un poco parecido en espíritu al ordenamiento de burbuja, pero la elección de los extremos no los pares adyacentes. Sin embargo, el corto de él es que no sin duda un montón de diferentes maneras podríamos hacer esto, y Francamente, yo creo que tipo de adoptado un par de aproximaciones, ¿verdad? Usted ha hecho una especie de cuatro montones ordenados, y luego fusionado con eficacia. Y eso es, diría, otra técnica por completo. Usted no lo trata como una gran pila, que haya dividido el problema en cuatro quads, si se quiere, y entonces de alguna manera las fusionó en el final. 

Así que vamos a considerar, en última instancia, cómo más podemos hacer esto. Formalizamos la noción de ordenamiento de burbuja última vez, y ordenamiento de burbuja revocatorio era una algoritmo que visualizamos con ocho de sus compañeros de clase hasta aquí, aparentemente ordenados al azar al principio. Y entonces decidimos por parejas, si dos elementos están fuera de servicio, simplemente intercambiar. Así cuatro y dos son evidente su total improcedencia, por lo que estos dos compañeros de clase y cambió de posición. Y luego repetimos con cuatro y seis, a continuación, seis y ocho, en cada iteración, moviéndose hacia la derecha. 

Así que dado ocho personas, ¿cuántas parejas comparaciones Qué hice mientras caminaba desde izquierda a derecha en uno de tales iteración? ¿Cuántas comparaciones? Siete, ¿verdad? Porque si hay ocho personas, pero que tienen la pareja ellos y que se mantienen en movimiento un salto a la derecha, usted no va a tener ocho comparaciones porque no se puede comparar un elemento contra sí misma, o que lo haría sólo inútil, por lo que tiene siete. O, más generalmente, si tenemos n personas, que hacer N menos 1 comparaciones con ordenamiento de burbuja. 

Así que vamos a considerar ahora lo bueno o mal ordenamiento de burbuja en realidad era, y tratar para darnos vocabulario con que a los algoritmos de crítica como esta, y pronto nuestro propio. Así que el primer paso a través ordenamiento de burbuja, la primera vez Caminé de izquierda a derecha en la etapa, me n menos 1 comparaciones tomó. Y eso va a ser mi unidad de medida, ¿no? Yo estaba un poco hablando y paseando, algo rápido, algo lento, así que contando mi número de segundos no está particularmente revelador, pero contando el número de operaciones que hice el lunes, la comparación de dos personas, que se siente como una buena unidad de medida. 

Así n menos 1 pasos la primera vez, pero entonces, ¿qué pasó después? ¿Cuál es la ventaja de una sola pasada a través de una lista de otro modo sin clasificar? ¿Qué puedes decirme sobre el elemento que fue todo el camino por allí? ¿Sí? Ese fue el elemento más importante, ¿verdad? El número ocho, a pesar de que comenzado aquí, cada vez que su comparación contra un vecino, mantuvo burbujeando hacia la derecha lado de la lista. Y, en efecto, que es donde el algoritmo obtiene su nombre. 

Ahora por esa lógica, el número de comparaciones Necesito que hago en el segundo tiempo Hago que pase de izquierda a derecha? n menos 2, ¿verdad? Sería simplemente estar desperdiciando mi tiempo si mantener comparando ocho en contra de alguien más porque ya sabemos ella estaba en el lugar correcto. Así que eso es un poco de una optimización, por lo que el siguiente paso va a ser más n menos dos pasos, donde n es el número de personas. Ahora usted puede tipo de extrapolar, incluso si no eres un experto en informática, cómo esto termina. Al final de este algoritmo, presumiblemente usted tiene sólo una comparación izquierda. Usted tiene que fijar el tipo de a partir de la lista en caso de que dos y uno son fuera de servicio y debe ser uno y dos, por lo que este toque fondo en más 1 comparación final. 

Ahora el punto, punto, punto tipo de ondas es manos de algunos de los detalles más jugosos, pero vamos a seguir adelante y simplificar. Si usted recuerda de alta escuela, francamente, muchos de ustedes tenido libros de matemáticas que tenían una hoja de trucos poco en la portada o la contraportada que mostraba sumas lo de la serie como esta última instancia, añadió haciendo. En el caso general, si tiene un variable como la n, y de hecho éste, si uno mira a su libro de matemáticas de la vieja escuela, verías que esta realidad se suma a esta suma aquí, n veces n menos 1 todo dividido por 2. Así que por ahora permítanme estipulo esto es cierto, por lo que en un acto de fe, eso es lo que esto resume hasta, y pudimos demostrar que en un caso más general. Pero ahora vamos a ampliar esto. Así que vamos a multiplicar esto, así que eso es n al cuadrado, menos n, todo dividido por 2. Eso es realmente n al cuadrado, dividido por 2, menos n sobre 2, así que eso es todo lo agradable e interesante. Pero, ¿qué pasa si nos ahora plug-in de un valor? Supongamos que yo no tenía ocho personas, pero dicen que un millón. Y un millón sólo porque que es un número bastante grande, vamos a conectar que en y ver qué pasa. Así que si conecto un millón en esa fórmula Voy a conseguir un millón de cuadrado, dividido por 2, menos una millones, dividido entre 2. Ahora ¿qué es eso va a ser igual? Así que 500 mil millones, menos de 500.000. Y si hago realmente que las matemáticas, significa que que la clasificación de un millón de las personas con el ordenamiento de burbuja me podría tomar 499999500000 pasos o comparaciones en el final, sólo estamos extrapolando. 

Eso se siente bastante lento, pero, francamente, medición de una entrada particular, así, no es todo lo que elocuente. Pero de hecho, sí sugiere que a medida que n se hace más grande y más grande, este algoritmo tipo de se siente peor y peor, o que realmente empezar a sentir el dolor de esa exponenciación, que n al cuadrado, que añade bastante rápido. Y este detalle no es perdido en las personas, de hecho, Hace algunos años un cierto senador que era campaña, se sentó para una entrevista con Eric de Google Schmidt, CEO de la época, y fue puesta en duda con una pregunta al igual que estamos explorando hoy. Vamos a echar un vistazo. 

[REPRODUCCIÓN DE VÍDEO] 

-Senador, Estás aquí en Google, y me gusta pensar en la presidencia como una entrevista de trabajo. Ahora, es difícil conseguir un trabajo como presidente, y usted va a través de los rigores ahora. También es difícil de conseguir un trabajo en Google. Tenemos preguntas, y nos pedir a nuestras preguntas de los candidatos, y éste es de Larry Schwimmer. Que-- que ustedes piensan que soy es broma, está justo aquí. ¿Cuál es la forma más eficiente de ordenar un millón de enteros de 32 bits? 

-Well-- 

-Lo Siento, tal vez-- 

No, no, no. Creo que el ordenamiento de burbuja sería el camino equivocado. 

Vamos, que le dijo eso? No vi ordenador la ciencia en su fondo. 

-Tenemos Nuestros espías en allí. 

-OK, Vamos a pedir una diferente pregunta de la entrevista. 

[FIN REPRODUCCIÓN DE VÍDEO] 

ALTAVOZ: Así que hablando de números específicos aunque, no va a ser tan útil. No es una lección de vida que la burbuja especie, dado un millón de entradas, podría tomar hasta 500 mil millones pasos. Realmente no se puede generalizar demasiado eficazmente a partir de ese y tomar buenas decisiones de diseño al escribir programas. Así que vamos a centrarnos aunque sobre cómo podemos simplificar este resultado. 

Así que he resaltado en amarillo aquí el resultado de n al cuadrado dividida por 2, por lo que un millones cuadrado dividido por 2, y luego He destacado lo la respuesta final fue una vez que restamos off n dividido por 2. Y la afirmación de que voy a hacer ahora es, quién diablos le importa si se resta de un poco más de 2 n edad cuando la primera parte de esta fórmula es mucho más grande? Domina el otro plazo, n al cuadrado dividido por 2 es mucho más grande, con claridad, como n se hace grande como un millón, esto es realmente una gran diferencia en el final de la día entre 500 mil millones y 499 999 500 000? En realidad no. Y así lo vamos a hacer como científicos de la computación es ignorar los términos de orden inferior y tomar algo como esto y realmente sólo simplificar al término que se va a importar. Los más grandes de nuestros conjuntos de datos consiguen, más grande nuestras bases de datos reciben, más páginas web tenemos que buscar, más amigos que tienen en Facebook. 

Como n se hace más grande, estamos muy va a preocuparse por el más grande plazo en cualquier tipo de análisis de nuestro desempeño algoritmos. Y yo voy a decir, sabes qué, ordenamiento de burbuja está en el orden de la gran O, del orden de n al cuadrado. No es exactamente n al cuadrado, como hemos visto, pero a quién le importa sobre los plazos más pequeños, y, francamente, que realmente le importa si dividimos por 2? Eso es sólo un factor constante. Y es de 500 mil millones contra 250 millones realmente tan grande de un acuerdo? Yo sólo podía esperar un año, dejar que mi laptop literalmente obtener el doble de rápido en el hardware, y ese tipo de diferencia simplemente desaparece de forma natural con el tiempo. 

Lo que nos importa es la expresión, la parte de la expresión que va a variar como nuestra entrada se hace más grande y más grande. Y de hecho, en el mundo real, eso es lo que está pasando cada vez más es las entradas a nuestros problemas y algoritmos son cada vez más grande. Tan grande O va a ser la notación, la notación asintótica, que acabamos de utilizar como científicos de la computación para describir el rendimiento, o el tiempo de ejecución, de un algoritmo. Así que podemos comparar algoritmos en equipos diferentes escritos por diferentes personas, utilizando alguna métrica fundamentalmente similar como el número de comparaciones que eres hacer, o tal vez el número de swaps usted está haciendo. 

Lo que no vamos a recuento es la cantidad de tiempo que pasa en el reloj en la pared normalmente. Lo que no vamos a preocuparnos acerca es la cantidad de memoria está utilizando hoy en menos, aunque eso es otro recurso que podríamos medir. Vamos a tratar de basar nuestro análisis sólo en las operaciones básicas, los que, francamente, que se puede ver más visualmente. Así que con algo así como gran O de n cuadrado, afirmo que O de n al cuadrado es un límite superior en la llamada momento de la burbuja de tipo corriente. En otras palabras, si usted quería decir que hay este límite superior de la cantidad de los pasos de un algoritmo puede tomar, que va a estar en el gran O de n cuadrado en este caso, un límite superior. 

¿Qué pasa si en vez cambio el historia sea no se trata de una especie de burbuja, pero sobre este límite superior. ¿Puedes pensar en un algoritmo que hemos visto en ya cuyo límite superior, máximo medir el tiempo o las operaciones, se dice que está acotada por n, una función lineal, no una cuadrática que es curvo? ¿Qué es un algoritmo que Siempre toma no más que como n pasos, o Pasos 2n, 3n o pasos? ¿Sí? 

AUDIENCIA: Encontrar el mayor número en una lista? 

ALTAVOZ: Perfect, la búsqueda de el mayor número en una lista. Si me dan una lista de personas, por ejemplo, cada uno de que es la celebración de una serie, ¿cuál es el número máximo de medidas que debería llevarme, una persona razonablemente inteligente, encontrar a la persona más grande en esa lista? n, ¿verdad? Debido a que en el peor de los casos, donde podría ser el mayor valor? Cierto, todo el camino al final. Así que en el peor de los casos límite superior, que podría tener que ir todo el camino aquí y ser como, oh, aquí está el número ocho, o lo que sea que el valor es. Ahora sólo sería estúpido si lo seguía haciendo, ¿verdad? ¿Estás buscando más y más elementos si el último de ellos es de allí? Así que sin duda, n es un límite superior. Yo no necesito tomar más pasos que eso. 

Entonces, ¿qué si en vez propuse que existen algoritmos en este mundo que tienen un tiempo de ejecución que es delimitada por gran O de log n, log n? ¿Dónde hemos visto esto antes? ¿Sí? 

AUDIENCIA: En el problema de guía telefónica? ALTAVOZ: Al igual que el problema de la guía telefónica. ¿Cuál fue la medida de la mucho tiempo o cuántas lágrimas de TI me llevó a encontrar a alguien como Mike Smith en la guía telefónica? Nos decía que era log n, y incluso si desconocido o que es un poco nebulosa qué logaritmo o exponente fue, sólo recuerda que log n generalmente se refiere al proceso, en este caso, de dividir algo en la mitad otra vez, y otra vez, y otra vez, y otra vez, de manera que obtiene cada vez más pequeña a medida que hace eso. 

Así que ingrese de n se refiere, claro, al ejemplo de guía telefónica, para búsqueda binaria en teoría, cuando tenía las puertas virtuales en el tablero, o cuando Sean era buscando algo. Si se hubiera utilizado de búsqueda binaria, log n sería el límite superior de la cantidad tiempo que toma. Pero esos algoritmos que corrían en log n asumido lo detalle clave? Que la lista se solucionó, ¿verdad? Su algoritmo es malo si su entrada no está ordenada, y sin embargo está utilizando algo así como búsqueda binaria ya que podría saltar derecho sobre el elemento sin darse cuenta de que es de hecho allí. 

Ahora, ¿qué podría significar esto, gran O de uno? Esto no quiere decir que su algoritmo tiene una y sólo una etapa, sólo significa que se necesita un número constante de pasos. Tal vez sea 1, tal vez es 10, tal vez es 1000, pero es independiente de el tamaño del problema. No importa qué tan grande es n, un algoritmo de constante de tiempo siempre tiene el mismo número de pasos. Entonces, ¿qué podría ser un algoritmo hemos hablado o simplemente intuitivamente que viene a usted que siempre se ejecuta en la llamada constante de tiempo? ¿Sí? 

AUDIENCIA: Añadir dos números. ALTAVOZ: Añadir dos números, 2 más 2 es igual a 4, hecho. Así que podría funcionar, ¿qué más? ¿Qué tal mundo más real, ¿no? 

AUDIENCIA: Encontrar el a primera hora de la lista. ALTAVOZ: Encontrar a la primera elemento en una lista, seguro. En realidad hemos estado hablando acerca de las matrices ya, ¿Cómo se llega a la primer elemento de una matriz, no importa cuánto tiempo la array es en código C? Usted sólo tiene que utilizar como el soporte notación cero, bam, estás allí. Y de hecho, matrices, como un aparte, apoyo algo generalmente conocido como acceso aleatorio, de acceso aleatorio memoria, porque usted puede literalmente saltar a cualquier lugar. Podemos hacer esto aún más simple podemos rebobinar hasta la semana cero cuando hicimos los arañazos. ¿Cuánto tiempo se necesita para que la dicen bloque en Scratch para ejecutar? Sólo la constante de tiempo, ¿verdad? Di algo, di algo, no importa cómo grandes rasguños mundo es, siempre es va a tomar la misma cantidad de tiempo decir simplemente algo. 

Así que esa es la constante de tiempo, pero ¿cuál es la otra cara? Si eso era superior límites, lo que si queremos para describir los límites inferiores de nuestros algoritmos de tiempo de ejecución? Casi un mejor caso potencialmente, si se quiere, aunque estos términos pueden aplicarse a mejor casos, los peores casos, los casos promedio más en general, pero vamos a concentrarnos en cotas inferiores en términos más generales. ¿Qué es un algoritmo que tiene una cota inferior de n pasos, o pasos 2n, 3n o pasos? Algunos de factor de n pasos, ese es su límite inferior. ¿Sí? 

AUDIENCIA: ordenamiento de burbuja? 

ALTAVOZ: ordenamiento de burbuja toma que mínimamente n pasos, ¿por qué? Porqué es eso? ¿Por qué ese comienzo para ir a vosotros intuitivamente, incluso si lo hace, no sólo todavía? ¿Sí? 

AUDIENCIA: [inaudible]. ALTAVOZ: Exactamente. En el mejor escenario posible de ordenamiento de burbuja, y una gran cantidad de algoritmos, si te entrego ocho personas que ya están ordenados, sería absurdo para usted, el algoritmo, para ir hacia atrás y adelante más de una vez, ¿no? Porque tan pronto como se caminar a través de la lista una vez, usted debe darse cuenta, oh, no hice ningún swaps, esta lista está ordenada, salida. Pero eso va a tomar usted n pasos. 

Y a la inversa, lo que es otra forma de pensar al respecto? Ordenamiento de burbuja es un omega, por así decirlo, de n, porque si nos fijamos en menos de n elementos, lo que es la cuestión fundamental que hay? No sabes si es ordenada, correcta. Nosotros los humanos podrían vistazo a las ocho personas y ser como, oh, está ordenada, que no me n medidas tomó, pero lo hicieron. Sus ojos, a pesar de que tipo de tener un gran campo de visión, miraste ocho elementos, miraste a ocho personas, eso es ocho pasos con eficacia. Y sólo si camino a través de todo lista ¿Me doy cuenta, sí, ordenados. Si me detengo a mitad de camino de pensar, todo derecho, que es bastante ordenadas hasta el momento, ¿cuáles son las probabilidades de que no está ordenada? Eso no va a haber algoritmos correctos. Podría ser más rápido, pero incorrecta. 

Así que ahora tenemos una manera de describiendo una menor grada, y ¿qué pasa con la constante de tiempo? ¿Qué es un algoritmo que tiene un menor con destino en su tiempo de ejecución de uno? 1 etapa, 2 etapas, 10 pasos, pero constante, independiente de n, el tamaño de la entrada? Sí, en la parte trasera. 

AUDIENCIA: Printf? ALTAVOZ: ¿Qué es eso? AUDIENCIA: Printf? ALTAVOZ: Printf. Bueno, seguro. Así que se necesita un número fijo de pasos. Y debería ahora-- ahora que estamos hablando de código C y no Scratch, algo como por ejemplo, con printf, deberíamos empezar a tener cuidado. Debido printf embargo, toma de entrada, que es una cadena, y las cuerdas no tienen técnicamente longitud. Así que si ahora queremos recoger en ti, si no te importa, técnicamente podríamos argumentar que printf no tener una entrada de longitud variable, y seguramente puede ser que tome más tiempo para imprimir una cadena de este largo, de este largo. 

¿Y qué si tenemos en cuenta sólo el clasificación y búsqueda ejemplos? ¿Qué pasa con Mike Smith en el teléfono libro, o de búsqueda binaria más general? En el mejor de los casos, lo que podría suceder? Abro la guía telefónica y, bam, hay número de Mike Smith. Yo le puedo llamar de inmediato. 

Tomó un paso, tal vez dos pasos, pero un número constante de pasos si tuve suerte. Y, francamente, que vimos en Lunes a su compañera de clase conseguir bastante suerte dos veces seguidas. Y eso fue hecho constante vez en unos bajos límites en el algoritmo en cuestión para encontrar el número 50 detrás de las cerradas puertas. 

Ahora, como un aparte, si descubre que tanto la gran O, el límite superior, y el omega, el límite inferior, son uno en el mismo, que es la misma fórmula en paréntesis, también puede decir, sólo para ser de lujo, que hay algo en zeta de n theta o de algún otro valor. Eso sólo significa que cuando grande O y omega son los mismos. Ahora ¿qué pasa con la selección especie? Vamos a utilizar este nuevo vocabulario. En la selección de clasificación, lo que eran haciendo de nuevo, y otra vez, y otra vez? Yo iba hacia atrás y adelante a través de la lista, en busca de quién? El número más pequeño. 

Entonces, ¿cómo muchos pasos, cómo muchas comparaciones hicieron I tener que hacer con el fin de averiguar quién el elemento más pequeño de la lista era? n menos 1, ¿no? Porque si acabo de empezar con el que estoy dado y yo le pongo a comparar, entonces él o ella, le o ella, él o ella, sólo puede emparejar elementos juntos n menos 1 veces. Así selección tiene especie de manera similar n menos 1 pasos la primera vez. 

¿Cuántos pasos que me lleve a encontrar el segundo elemento más pequeño? n menos 2, porque estoy siendo tonto si sigo mirando las mismas personas de nuevo si he ya lo seleccionado o ella y los puso en su lugar. Y el tercer paso, n menos 3, entonces n menos 4. Hemos visto este patrón antes, y de hecho Selección de tipo similar tiene un límite superior de n al cuadrado si hacemos esa suma. ¿Cuál es su límite inferior, la selección especie? Como mínimo, la cantidad de tiempo de selección debe ordenar tomar, como lo definimos el lunes? Proponer dos opciones. Tal vez sea n, como antes. A lo mejor es n al cuadrado, ya que es ahora como el límite superior. 

AUDIENCIA: n al cuadrado. ALTAVOZ: n al cuadrado. ¿Por qué? 

AUDIENCIA: Debido a que tiene para definir [inaudible]. 

ALTAVOZ: Exactamente. Al menos en lo definí ordenamiento por selección era bastante ingenua, seguir adelante, encontrar el elemento más pequeño. Ir de nuevo, encontrar el elemento más pequeño. Ir de nuevo, encontrar el elemento más pequeño. No hay ninguna clase de optimización de ahí que podría dejarme abortar después sólo n o menos pasos. Así que de hecho, la selección tipo, omega de n al cuadrado. 

¿Qué pasa con la ordenación por inserción, donde tomé que me dieron, y entonces yo le dejé o ella en el lugar correcto? Entonces procedí a la segunda persona, él o ella se dejó caer en el lugar correcto. Entonces la siguiente persona, se dejó él o ella en el lugar correcto. Tenga en cuenta que esto es muy lineales, por así decirlo. Soy una línea recta, estoy no ir y venir, Nunca mirar hacia atrás en realidad, pero lo que está sucediendo cuando lo introduzco o ella en el comienzo de la lista como lo hicimos el lunes? Lo que está sucediendo? ¿Sí? AUDIENCIA: [inaudible]. ALTAVOZ: Sí, eso fue la captura, ¿verdad? Usted puede recordar de sus compañeros de clase, si estaban haciendo ningún movimiento con sus pies, que era una operación. Así que si había tres personas aquí y la nueva persona pertenecía hasta allá, en una larga etapa como esta, claro, o ella sólo podía ir hasta el final. Pero si estamos pensando en un ordenador y una matriz de la memoria, estas personas van a tener que barajar más para dar cabida a esa persona. Y para que n menos 1 shufflings, n menos 2 shufflings, n menos 3 shufflings es sólo un poco de pasando detrás de mí, no en frente de mí como antes, en algún sentido. Ahora como un aparte, y como que podría haber visto en línea si usted comienza a hurgar sobre tipo, hay tan muchos diversos por ahí, algunos de ellos mejor que otros. De hecho, es uno bogosort eso es bastante divertido para mirar hacia arriba. Bogosort toma un conjunto de números o decir una baraja de cartas, las baraja al azar, y comprueba si están ordenados. Y si no, lo hace de nuevo. Y si no, lo hace de nuevo. Si no, lo hace de nuevo. Increíblemente estúpido. 

Y de hecho, si usted lee al igual que el artículo de Wikipedia, su apodo es estúpida especie. Con el tiempo va a funcionar, con suerte, dado el tiempo suficiente, pero esa cantidad de tiempo podría tomar bastante tiempo. Así que si yo pudiera, vamos a acelerar las cosas desde el ejemplo de Mary Beth antes, por tener algunos elementos más, sino dos procesadores más. Dos personas, si no le importaría acompañarme. ¿Qué hay de 1 por aquí, y vamos a vaya-- nadie allí? Nadie de allí? Okay. Usted con el negro camisa, sí, vamos hacia abajo. Muy bien, ¿cuál es tu nombre? 

AUDIENCIA: Peter. 

ALTAVOZ: ¿Qué es eso? 

AUDIENCIA: Peter. ALTAVOZ: Pedro, David, encantado de conocerte. Muy bien, tenemos Peter aquí, si quieren venir a la mesa aquí. ¿Y cuál es tu nombre? 

AUDIENCIA: Elena. ALTAVOZ: Elena. Bueno, encantado de conocerte. Elena cumple con Peter. Peter, Elena. Y necesitaremos Andrew aquí también, por favor. Y su reto va ser para ordenar una baraja de cartas. Y si no familiar, cubierta de tarjetas debe en última instancia, ordenarse un poco algo como esto donde haremos los clubes, a continuación, las espadas, a continuación, los corazones y diamantes, desde ace como uno, todo el camino hasta el rey. 

Las tarjetas que voy a darle van a ser 52 en cantidad. Vamos a similar vez que, en un momento. Vamos a lanzar Andrew en la pantalla aquí, con el fin de ver como hacer esto. Y para que todo esto es tanto más visible, estas son las cartas que recibí en Amazon. Así que ya son al azar solucionaron, y que vamos a medir el tiempo que usted. Y vamos a vivir en la realidad de este tiempo, así que vamos a tratar de presionarte porque de lo contrario esto será tedioso rápidamente. Si se pudiera proceder a ordenar 52 elementos juntos a través de algunos medios, ahora. 

Y de nuevo, cuando vemos estos chicos hacen lo que, al final se va a producir una evidente resultado, piensa realmente cómo lo están haciendo cada uno que, cómo podría describirlo. Porque de nuevo, estos son todos los procesos, algoritmos que nosotros damos por sentado como un ser humano. Pero usted ha tenido probablemente mucho intuición, mucho antes de que incluso pensado en tomar un clase de informática que podría haber tenido la intuición con que para resolver problemas como éste. Pero una vez que reconocen los patrones y comenzar para formalizar los pasos con los que usted está la solución de estos problemas, usted encontrará que usted puede solucionar mucho más interesante y mucho más complejo problemas rápidamente. Así que alguien del público, lo que es al menos un elemento del algoritmo que están usando aquí? 

AUDIENCIA: [inaudible] ALTAVOZ: ¿Qué es eso? AUDIENCIA: Por ejemplo. ALTAVOZ: Por ejemplo. Así que primero que se están agrupando todos los diamantes juntos al parecer, todo el corazones juntos lo que parece, y así sucesivamente, sin respeto para los números de las tarjetas. Y ahora aparecen, por ejemplo, ser ordenándolos por número. Muy buena. 

Muy bien, así que lo que va a ser el paso final, entonces aquí? Una vez que tenemos cuatro palos ordenados, lo que Por qué tenemos que hacer para las cuatro pilas con el fin de lograr uno cubierta ordenados, simplemente? Así que tenemos que combina otra vez. 

Así que hay una idea interesante que de nuevo, diría, es muy intuitivo incluso si usted nunca podría haber abofeteado ese tipo de etiqueta. Esta noción fundamental de la división el problema no en la mitad de este tiempo, pero al menos en cuatro piezas. Resolver casi problemas fundamentalmente idénticos en el aislamiento de uno al otro, y luego combinar los resultados. Y, excelente, hecho. Muy bien, una gran ronda de aplausos, si pudiéramos. 

[Aplausos] 

ALTAVOZ: No tengo ni idea de lo que va a hacer con ellos, pero aquí tienes. Muchas gracias. Así que vamos a ver, a dos minutos y ocho segundos, de si desea desafiar a tus amigos. Entonces, ¿qué va a ser una toma de distancia de esta que podemos aprovechar de forma más general? Bueno, piense de nuevo a este conjunto de números, y pensar de nuevo ahora a algunas de las pseudocódigo que hemos escrito en el pasado, y este fue el pseudocódigo para resolver el problema de la guía telefónica. Por lo cual en pseudocódigo I enumerado una manera más metódica de describir la forma en que hice un muy intuitivo algoritmo humana de dividir el teléfono libro por la mitad, repetir, repetir, repetir, hasta que encuentre a alguien como Mike Smith, si es hecho en la guía telefónica. 

Pero que tipo de utilicé lo que yo llamo un enfoque muy iterativo aquí, en particular notificación línea 8 y la línea 11. Esos son evidencia de un proceso iterativo enfoque, un enfoque de bucle, porque eso es exactamente el comportamiento que inducen. Esas líneas de ambos dicen ir a línea de tres, y usted puede tipo de pensar que en su el ojo de la mente como un bucle. Le está diciendo a volver a subir al paso tres y repetir, una y otra vez, y otra vez. 

Pero ¿y si aprovechamos una idea clave aquí que hicimos no la última vez, y simplificar la línea 8 y línea 11 y sus vecinos como acaba esto, en amarillo. No es fundamentalmente acortar el pseudocódigo mucho, pero está cambiando fundamentalmente la naturaleza de mi algoritmo. Lo que ahora estoy diciendo en el paso 7, en el paso 10, es la búsqueda de Mike de la misma manera exacta, pero sólo en la izquierda la mitad o la mitad derecha. 

Así, en otras palabras, si Empiezo desde el paso uno, recoger la guía telefónica, abierto a medio de guía telefónica, mirar nombres, si se encuentra entre Smith nombre de, llame a Mike, lo demás si Smith es anterior en el libro, paso siete buscar Mike en la mitad izquierda del libro. Pero ese tipo de se siente como me está dejando colgar, ¿verdad? En amarillo, es un instrucción, pero ¿cómo puedo buscar Mike en la izquierda la mitad de la guía telefónica? ¿Dónde tengo un algoritmo con el que puede buscar a alguien como Mike Smith? Bueno, nos está mirando a la cara. Literalmente, puedo usar la misma exacta programa va efectivamente a la cima de nuevo y volver a correr las mismas líneas de código. 

Así que, aunque este debe sentirse como un poco de una definición cíclica donde usted está respondiendo a alguien es pregunta por sólo una especie de pedir la misma pregunta de nuevo, como por qué, por qué, por qué? La realidad es porque hemos codificamos un par de líneas especiales, el paso 4, que es un si, y el paso 12, el cual es efectivamente otra rama, porque tenemos esas medidas provisionales, este algoritmo terminará si encontrar Mike, o si no lo hacemos. Pero en el paso 7 y 10 ahora, tenemos lo que llamaremos un algoritmo recursivo. Y recursividad es de hecho una idea poderosa eso es un poco alucinante al principio, que ahora podemos aplicar la siguiente manera. 

Combinar tipo será el último tipo que miramos, al menos en la clase formal. Y es fundamentalmente diferente de los últimos tres, y ciertamente últimos cuatro si incluimos bogosort. Aquí está el pseudocódigo para merge sort. Cuando en la entrada de n elementos, por lo que dada una matriz de tamaño n, si n es menor que 2, regresar. Entonces, ¿por qué tengo que cordura comprobar primero? ¿Cuál es la implicación de que si te entrego una matriz cuya longitud n es menor que 2? Ya está ordenada, obviamente, ¿no? Debido a que la lista tiene ya sea un elemento, que es trivialmente ordenada porque es lo único que hay. O, es de tamaño cero, lo que significa no hay nada que arreglar, así que por la naturaleza que está ordenada. No hay nada mal allí. Así que ese es nuestro llamado caso base. 

Que es similar en espíritu a lo que hicimos con Mike. Si Mike en la guía telefónica, le llaman. Si él no está allí, darse por vencido. Es un caso base de la llamada, para asegurarse este algoritmo al final del día se detendrá en ciertas circunstancias. 

Pero aquí está el salto de fe ahora, otra cosa, ordenar la mitad izquierda de los elementos, a continuación, ordenar el derecho medio de los elementos, y luego fusionar las mitades ordenados. Y aquí es donde se siente como que estamos copping cabo. Te he pedido para ordenar n elementos, y estoy diciendo, bien, no es por la clasificación la izquierda y la clasificación de la derecha. Lo que digo es una otra cosa, y esto es el tema clave parece en la intuición hasta ahora, hay esta tercera etapa de la fusión. Qué aunque parece tan tonto en espíritu, como acaba de fusionar cosas juntos, parece ser un paso clave hacia la montaje de dos problemas que se dividieron en última instancia por la mitad. 

Así fusionar tipo, vamos a hacer esto, si me humor mí, con una manifestación más, sólo para que tengamos un poco de números para trabajar con. ¿Puedo intercambiar ocho estrés bolas para ocho personas? Muy bien, ¿y tú tres, cuatro en esta sección, cinco, seis, y vamos a do 7, 8, vamos arriba. Aceptar, sí Aceptar. Minus 8, allí vamos, más 1. Excelente. Todo viene derecho hacia arriba, vamos a rápidamente le dará números. El número dos, número tres, número cuatro, número cinco, seis, siete y ocho. Hice ocho correctamente esta vez. 

OK, así que adelante si se pudiera, y vamos a ordenar en el orden original que tuvimos ayer que parecía así, si no te importa. Y vamos a hacerlo delante de la mesa. Muy bien, así que fusionar especie. Aquí es donde se va para conseguir una especie de interesante, porque me parece que estoy dando a mí mismo mucho menos información hoy en día. 

Así fusionar tipo primero de todo en la entrada de n elementos, y es, obviamente, no menos de dos, es ocho, así que tienen un poco más de trabajo que hacer. Así que ahora estamos mentalmente como una clase están ahora en la rama else, lo que significa tres pasos. En primer lugar, tengo que ordenar la mitad izquierda de los elementos. Entonces, ¿cómo hago para hacer esto? Bueno, voy a clase de mentalmente dividir la lista aquí, usted no tiene que mover físicamente, y estoy vamos a centrar sólo en la mitad izquierda de los elementos aquí. Entonces, ¿cómo hago para ordenar una lista ahora del tamaño de cuatro? ¿Cuál es mi algoritmo? Primero compruebo es n menos de dos, no, así que me dedico al bloque distinto. Ordenar a la izquierda de la mitad de los elementos. 

Así que ahora de nuevo, mentalmente, y aquí es donde debes acumular una gran cantidad de historia mental, si se quiere. Ahora estoy ordenando el izquierdo la mitad de la mitad izquierda. Muy bien, así que ahora llamo a mi misma combinación algoritmo de ordenación, es n menos de dos? No, es de dos, así que tengo que ordenar la mitad izquierda y la mitad derecha. Así que aquí vamos, ordenar la mitad izquierda. ¿Por qué no acaba de dar un paso hacia adelante. Cuál es tu nombre? 

AUDIENCIA: Darren. 

ALTAVOZ: Dan. Dan ha dado un paso adelante. 

AUDIENCIA: Darren. ALTAVOZ: Darren, hecho. ¿Dijo Darren o Dan? 

AUDIENCIA: Darren. 

ALTAVOZ: Darren. Aceptar, Darren ha intensificado hacia adelante y ahora está solucionado. Y esto es casi una afirmación estúpida, ¿verdad? Realmente no parece estar logrando nada, pero vamos a proceder. Ahora voy a ordenar la derecha medio de los elementos. Cuál es tu nombre? 

AUDIENCIA: Lucas. 

ALTAVOZ: Lucas. Vamos, un paso adelante. Hecho, he clasificado Lucas. La mitad izquierda está clasificado y la mitad derecha está ordenada, pero de nuevo, hay un paso clave aquí. ¿Qué tengo que hacer la próxima? Combinar las mitades ordenados. Ahora vamos a tener sólo todos atrás y hacia adelante de esta manera, porque Yo como que necesito algo de espacio cero. Es casi como éstos chicos están en una mesa, y necesito un poco de espacio para moverlos en. Así que voy a fusionar ustedes por mirar en la mitad izquierda y la mitad derecha. Y que, obviamente, es lo primero, la mitad izquierda o la mitad derecha? Así que la mitad derecha, por lo que vamos a pasar a Luke aquí a la posición original de Darren. Y ahora fusionar su mitad izquierda en, Darren va a mover a la derecha allí. 

Así que se siente como casi un efecto burbuja especie, pero mi algoritmo fundamental, muy diferente esta vez. Pero ahora es donde las cosas se ponen un poco molesto porque usted tener que rebobinar mentalmente dónde dejé fuera. Acabo fundí las mitades ordenadas, lo que significa que estoy en mi algoritmo? Tengo que ordenar la mitad derecha, ¿no? 

Si rebobina, literalmente en el vídeo, podrás vemos que llegamos a este punto de Luke y Darren por la clasificación de la izquierda la mitad de la mitad izquierda. Entonces nos fusionamos los mitades ordenadas, que significa que el siguiente paso es ordenar la mitad derecha de la mitad izquierda. Muy bien, así que vamos a hacer esto más rápidamente. Muy bien, seis, voy a reclamar que ahora se ordenan, vamos hacia adelante. Cuál es tu nombre? 

AUDIENCIA: Adriano. 

ALTAVOZ: Adriano. Adriano está solucionado. ¿Y cuál es tu nombre? 

AUDIENCIA: Alex. 

ALTAVOZ: Alex está ahora ordenadas. Medio izquierdo, medio derecho, ¿cuál es el paso final? Combinar. Pretty trivial, así que estoy va a fusionar en seis, dar un paso atrás, ocho, dar un paso atrás. Y ahora note que esto es una comida para llevar útil, lo que ahora es verdad sobre la mitad izquierda de la lista, independientemente de cómo empezamos? Se está ordenada. 

Ahora que no está ordenada en el gran esquema de las cosas, pero está ordenada de forma independiente de la otra mitad. Ahora lo que paso soy yo en si sigo rebobinado de cómo comenzó la historia? Ahora tengo que ordenar la mitad derecha. Así que ahora estamos en el camino de regreso el principio de la historia, y vamos a hacer esto con mayor rapidez. Así que voy a ordenar la mitad derecha de toda la lista. ¿Cuál es el siguiente paso? Ordenar la mitad izquierda de la mitad derecha. Ordenar la mitad izquierda de la mitad izquierda de la mitad derecha. ¿Y cuál es tu nombre? 

AUDIENCIA: Omar. 

ALTAVOZ: Omar, un paso al frente, hecho. La mitad izquierda está ordenada. ¿Y cuál es tu nombre? 

AUDIENCIA: Chris. 

ALTAVOZ: Chris, dar un paso hacia adelante, que ahora está ordenada. ¿Cuál es el paso clave ahora? Combinar. Así que uno va a fusionar en su lugar aquí, si pudiera dar un paso atrás, y tres va a dar un paso atrás, se funden. Así que la mitad izquierda de la mitad derecha, ahora está solucionado. Francamente, este algoritmo se siente como que están perdiendo mucho más tiempo que antes, pero si lo hiciéramos esto en tiempo real, vamos a ver lo que los robos de balón va a ser. Ahora aquí estoy, ¿no la mitad de la mitad derecha, déjame ir adelante y ordenar la mitad izquierda. Paso adelante, ¿cómo te llamas? AUDIENCIA: Ramsey. ALTAVOZ: Ramsey está solucionado. Cuál es tu nombre? 

AUDIENCIA: Marina. 

ALTAVOZ: Marina está clasificado como así, si usted toma un paso hacia adelante. Paso clave es ahora fusionar, estoy va a arrancar de mis dos listas, izquierda y derecha. Cinco va a ser lo primero, y siete va a ser el próximo. Y de nuevo, esto es deliberado. El hecho de que están tomando pasos hacia adelante y hacia atrás tiene la intención de representar que no podemos hacer este algoritmo en su lugar con la misma facilidad como especie de burbuja, y la selección de tipo, y tipo de inserción en el que sólo guardado intercambiando personas. Yo, literalmente, necesito una especie de papel borrador en el que para poner a estas personas mientras hago la fusión, y entonces puedo volver a ponerlos en su lugar. Y eso es clave porque estoy usando un nuevo recurso, el espacio, no sólo tiempo. 

OK, esto es increíble. La mitad izquierda está ordenada, la mitad derecha es paso ordenado, ahora que la fusión de tecla. ¿Cómo voy a fusionar esto? Así que si usted sigue mi la mano izquierda y la mano derecha, Voy a señalar mi mano izquierda en la mitad izquierda, la mano derecha en la mitad derecha, y ahora tengo que decidir paso a paso a quién se funden en. Que obviamente es lo primero? Número uno. Así que ven aquí, aquí está nuestro bloc de notas. Así que ahora el número uno, y el aviso lo que voy a hacer con mi mano derecha, Voy a mover mi mano derecha una pasar por encima al punto número tres, y ahora tengo que hacer la misma decisión. Y en realidad de pie justo en delante de Lucas aquí si pudiera, porque este es nuestro bloc de notas. Entonces, ¿quién sigue? Tenemos Lucas con el número dos o Chris número tres. Obviamente Lucas, número dos, por lo que vienen aquí. 

Pero mi mano izquierda ahora va a se incrementa para apuntar a Darren, y aquí está la clave de llevar con la fusión, que voy a seguir haciendo esto, Obviamente, si usted amable de seguir la lógica. Pero mis manos nunca son va a ir hacia atrás, lo que significa que sólo alguna vez voy a mudar a la izquierda con mi proceso de fusión, y eso va a ser clave para nuestro análisis en un momento. 

Así que ahora vamos a terminar esto rápidamente. Así que tres viene a continuación, luego cuatro viene a continuación, y ahora cinco viene a continuación, y luego seis, y siete, y, finalmente, ocho. Se siente como el algoritmo más lento sin embargo, pero no si en realidad ejecutarlo en el mismo tipo de velocidad de reloj, por lo que hablar, con el mismo tic-tac del reloj como antes. ¿Por qué? Bueno, echemos un mirar en el resultado final. 

Volvamos aquí, déjame tire hacia arriba una demostración visual de lo que acabamos de hacer. Acercar aquí, en esta página aquí, diciendo Firefox que queremos hacer cola en esta caja, vamos a decir especie de burbuja, con la que ahora estamos bien familiarizados, ordenación por selección, que es otra uno bastante sencillo, y ahora de hoy merge sort, el cual será nuestro final culminante. La razón por la que tomó mucho más tiempo aquí con los seres humanos y me verbalmente es, Obviamente, estoy explicando cada paso. Pero si simplemente ejecuta este, mucho como lo hicimos especie de burbuja y selección especie no sólo visualmente, reloj cuánto más eficiente Este apalancamiento de división y conquista puede ser cuando se aplica a un conjunto de datos que está ni siquiera tamaño de ocho, pero incluso mucho, mucho más grande. Doy combinar especie, uno al lado del lado con estos otros algoritmos. Esto se va a poner dolorosa rápidamente, y el final no es particularmente culminante, que sólo terminan ordenados. Pero la clave para llevar es que mirar cuánto más rápido fusionar especie era, a menos que pienses que soy sólo un poco de jugar con usted. Si hacemos esto por última vez, Vamos a recargar esto, volvamos y elegir especie de burbuja, y sólo por diversión, vamos a elegir la inserción especie, sólo por si acaso. Y esta vez de nuevo, vamos a elija Fusión de clase y vamos a de hecho ejecutar estos lado a lado. 

Y no es, de hecho, un golpe de suerte. Lo que he hecho es efectivamente tengo dividido mi entrada a la mitad, de nuevo, y otra vez, y otra vez. Y sólo hay tantas veces que puedas dividir su entrada en mitades, izquierda y la derecha. ¿Cuál es la fórmula que nos seguimos viendo que describe la división por la mitad otra vez, y otra, y otra, y otra vez? 

AUDIENCIA: log n. 

ALTAVOZ: Inicie sesión n. Pero luego hay otro paso clave, este algoritmo no es log n pasos. Si sólo se log n pasos, estaríamos en el mismo problema como antes, donde no podemos estar Seguro que todo está ordenado. Hay que mirar mínimamente en n elementos para asegurarse de n elementos se ordenan, de lo contrario es un acto de fe. 

Por lo que es registro mínimamente n pasos, pero ¿qué pasa con este paso clave fusión donde combiné mi mitad izquierda y derecha medio y caminó por el escenario? ¿Cuántos pasos es que fusionar? Es n, pero no lo hice solo fusionar el tiempo final. En cada una de esas llamadas anidadas, en cada de esas fusiones anidados, yo todavía lo solucionaron. Combiné estos dos chicos, a continuación, estos dos chicos, entonces estos dos chicos y así sucesivamente. 

Así que me di la fusión de nuevo, y otra vez. ¿Cuántas veces? Así que cada vez que divide la lista a la mitad, me hizo una fusión. Divida la lista por la mitad, hacer una fusión. Así que si dividiendo la lista se puede hacer log n veces, y la fusión en última instancia lleva a n pasos, lo que podría ser ahora la parte superior con destino en el funcionamiento tiempo de nuestro algoritmo? n log n. 

Y de hecho, eso es lo que que hemos logrado aquí. Así que la sensación que se ve visualmente cuando esas tres cosas corren lado a lado está n al cuadrado contra n cuadrado contra n log n. Qué fundamentalmente vamos a ver, no sólo hoy sino en el futuro, es mucho, mucho más rápido. Un aplauso para estos chicos, Voy a recompensarlos con bolas de estrés. Vamos a levantar la sesión aquí hoy, y nos vemos el lunes.