[REPRODUCCIÓN DE MÚSICA] DAVID J. MALAN: Este es CS50. Y este es el comienzo de la tercera semana. Así que tenemos un montón de emocionantes cosas que cubren la actualidad. Una gran cantidad de oportunidades para los voluntarios en el escenario. Y en última instancia, en la actualidad es No se trata de código. Pero se trata de ideas y se trata de algoritmos, y de hecho traer de vuelta algunos de las lecciones aprendidas de la semana cero, en donde recuerdo, nos introducido esta monstruosidad. Y el endeudamiento inspiración de que, para empezar para resolver cada vez más sofisticada problemas algorítmicamente. Pero primero, un par de anuncios. Así que uno, si usted desea unirse El personal y los compañeros de clase de CS50 en el almuerzo este viernes, tanto aquí como en Cambridge, y en New Haven, por favor visite el curso de sitio web, donde una URL se puede encontrar. Conferencia de este miércoles será no estar aquí en Sanders. Será sólo en línea, por lo que sintonizar en el sitio web del CS50, ya sea aquí en Cambridge o New Haven también. Y entonces un problema fijó dos ya está en tus manos. Si usted no ha buceado en el, sin embargo, permítanme para ofrecer la sugerencia enérgica que, sobre todo ahora, cuando el problema establece por adelantado, usted realmente desea comenzar ahora, si no incursionar un poco en el fin de semana o antes la primera vez que salen a Viernes, porque vas a encuentran que no son necesariamente cada vez más largos o más desafiante por se. Creo que usted encontrará que, en en general, tienden a tener más o menos alrededor misma cantidad de tiempo. Pero ciertamente depende en el estudiante, y depende de la mentalidad con la que te acercas a ella. Pero invariablemente, vas correr contra alguna pared, y vas a golpear algunos errores, y no eres más que no va a ser capaz de superarlo en algún momento. Y es enormemente valiosa para poder alejarse, volver al día siguiente, ir a las horas de oficina, mensaje el CS50 Discuta o similar, para conseguir realmente desbloqueado. Así que tenlo en mente. Comenzando temprano como sea posible es la mejor cosa que puedes hacer. Así que aquí es donde empezamos la clase, a lo largo de la semana cero. Y podemos conseguir un voluntario aquí para ayudarme a encontrar los micrófonos? OK. De pie ya. Vamos arriba. Supongo que eso es lo que va a trabajar. ¿Cómo te llamas? ALAN ESTRADA: Alan Estrada. DAVID J. MALAN: Alan Estrada. Vamos arriba. Encantada de conocerte. ALAN ESTRADA: Encantado de conocerte. DAVID J. MALAN: Y usted estuviera aquí con nosotros en la semana cero, por supuesto. ALAN ESTRADA: yo. Yo era. DAVID J. MALAN: Así podría ir adelante y encontrar para nosotros Mike Smith, ¿tan rapido como puedas? Tan rapido como puedas. Literalmente desgarrar el problema en la mitad de lo que necesita. ALAN ESTRADA: Um. DAVID J. MALAN: Literalmente rasgando el problema en medio. ALAN ESTRADA: Oh. Mm. Muy bueno. DAVID J. MALAN: OK. Bien. Gracias. ALAN ESTRADA: Muy buena. OK. DAVID J. MALAN: Y por lo que ahora, que ha recortado hacia abajo a la mitad del tamaño del problema. Ahora, estamos a una cuarta parte. ¿Usted está prestando atención a de qué lado estamos manteniendo? [Risas] ALAN ESTRADA: Sí, yo think-- DAVID J. MALAN: ¿Qué sección estamos? ALAN ESTRADA: Mofles, así. DAVID J. MALAN: OK. Pero Mike Smith va a ser después de Mofles. Tan-- [Risas] Correcto. ALAN ESTRADA: ¿Dónde estamos buscando? DAVID J. MALAN: Mike Smith. ALAN ESTRADA: Mike Smith. DAVID J. MALAN: Ahora, estamos en quirúrgico. Ahora, los médicos. Ahora-- ALAN ESTRADA: Let's- vamos con real. Real. DAVID J. MALAN: Real. OK. Si necesita Real. Ahora, ¿qué camino es Mike Smith? ALAN ESTRADA: De esta forma. DAVID J. MALAN: Qué manera? ALAN ESTRADA: Espera. Derecho M es--? Empezamos con-- DAVID J. MALAN: Sí. Están a la izquierda. Su derecho. ALAN ESTRADA: Sí. DAVID J. MALAN: Así que Mike aquí. ALAN ESTRADA: ¿Qué? [Risas] Mal ejemplo, chicos. Apenado. DAVID J. MALAN: Esto le enseñará a saltar de su silla. ALAN ESTRADA: Oh. Oh. Te tengo. Te tengo. Oh. Oh. Esta es-- Bueno, te tengo. Smith aquí? DAVID J. MALAN: Smith, gracias. Así que voy a seguir mirando hacia arriba Smith? ALAN ESTRADA: Oh, sí. No no no. Oh no. Esto es mío. DAVID J. MALAN: Oh, tienes Smith. OK. ALAN ESTRADA: Sí, Smith consiguió aquí. Lo siento chicos. Pensé que Michael-- estabas buscando Michael. Apenado. DAVID J. MALAN: Está bien. Muy bien, ahora estamos en Paccini and Sons. ALAN ESTRADA: Paccini e hijos. DAVID J. MALAN: Sólo usted y yo estamos en esto. OK. Encuéntrenos Mike Smith. Smith. ALAN ESTRADA: Smith. DAVID J. MALAN: Smith. Estamos en R para basura. ALAN ESTRADA: Malo. Oh. Esto va a tomar un tiempo. [Risas] DAVID J. MALAN: Zapatos. Estamos en los zapatos. ALAN ESTRADA: Ahora estamos gonna-- DAVID J. MALAN: Niza. ALAN ESTRADA: Which-- [Risas] Oh, esto es genial. [Risas] DAVID J. MALAN: Está bien. ALAN ESTRADA: Oh, eso es bueno. No creo que me voy a tener amigos PSAT después de esto. DAVID J. MALAN: Good. Sporting. ALAN ESTRADA: Sporting. Um, L, M, N, O, P. DAVID J. MALAN: OK. Así que vamos a lágrima esto en medio. Esta bien. Esto termina mal de todos modos, porque Mike Smith no estará en las páginas amarillas. ALAN ESTRADA: Aw. DAVID J. MALAN: No, está bien. Pero vamos a suponer como él está en esta página. Así que ahora, usted ha recortado el problema abajo de una página, y nos encontramos con Mike Smith. [ANIMA] Ok, gracias. OK. Eso fue extraordinario. Pero fue aún más rápido de búsqueda lineal, en el que empezamos a a partir del libro, y nos movemos nuestra forma de izquierda a derecha, finalmente, en busca de Mike Smith. Y así, si la guía telefónica tenía tal vez 1.000 páginas, tal vez habría tomado nos 10 o más páginas lágrimas. Pero es posible que haya aprovechado tocado una suposición durante todo eso, lo que es decir, que la guía de teléfonos de antemano era qué? AUDIENCIA: Ordenado. DAVID J. MALAN: Ha solucionado. ¿Correcto? Se ordena alfabéticamente, por lo que todos esos nombres y números están ordenadas por los Atléticos a la Z, y en orden alfabético en el medio. Pero hoy en día, nos preguntamos ahora la pregunta, bueno, ¿cómo Verizon o el teléfono empresa ponerlo en ese estado? Debido a que es una cosa de aprovechar esa suposición, y por lo tanto, resolver un problema con un algoritmo más eficiente. Pero en realidad nunca pedido en la semana cero, bueno, cuanto costo Verizon o alguien más para conseguir que la libreta de teléfonos en forma ordenada? ¿Correcto? No importa si mirando hacia arriba Mike Smith es súper rápido, si usted toma un año para ordenar las páginas inicialmente. ¿Correcto? Usted puede ser que también acaba de tamizar a través de un libro de teléfono al azar, si va a ser súper cara a solucionar el problema. Así que si podemos tener otro voluntario. Vamos a echar un vistazo aquí a cómo might-- Vamos up-- cómo podríamos ir sobre la clasificación de los mismos. Y si Jordan podía realidad únete a nosotros aquí en el escenario. Vamos para arriba para un momento. ¿Cómo te llamas? CAROLINE: Caroline. DAVID J. MALAN: Caroline, vamos para arriba. Y se te uniste por mí y Jordania aquí. Caroline, gracias. Correcto. Así que lo que tenemos aquí Caroline tiene 26 libros azules que FAS utiliza para administrar ciertos exámenes finales. Estos son cada vez difícil de encontrar, pero lo que hemos hecho con antelación es que nos hemos puesto el nombre de alguien en la parte frontal de cada uno de estos, pero nos hemos mantenido simple a continuación, poner los nombres completos. Así que nos gustaría poner a la persona con el nombre A, C, J, B, hasta el final de la A a la Z, pero están en orden aleatorio. Y por lo que si lo haría, hablando de su camino a través de los problemas y se le hazlo, puede seguir adelante y ordenar estos para nosotros, de la A a la Z. AUDIENCIA: OK, entonces L es como, el medio. C está comenzando. B. J antes de L. B, Q. DAVID J. MALAN: Mantenga esa pensado por un segundo. Porque de lo contrario, esto es sólo interesante para usted, yo, y Jordania. Allá vamos. AUDIENCIA: [inaudible]. R. DAVID J. MALAN: OK. ¿Qué estás haciendo? CAROLINE: M se produce después de O. DAVID J. MALAN: OK. CAROLINE: O. DAVID J. MALAN: O, bueno. CAROLINE: E. DAVID J. MALAN: E, F. Sí. CAROLINE: T, U, V. DAVID J. MALAN: V, T, U, V. Por lo tanto, Parece que eres making-- seguir adelante. Parece que estás haciendo una pila grande aquí, y la clase de una gran pila de allá. Así que la primera mitad del alfabeto, segunda mitad del alfabeto. OK. Bien. Tipo de dividir el problema en dos. M, N, X. Sí. CAROLINE: K. DAVID J. MALAN: OK. K. Así que estás tipo de selección uno tras otro, poniéndolo a la izquierda oa la derecha, o Z va en el suelo. OK. CAROLINE: Z va en el suelo. DAVID J. MALAN: OK. Y va en el suelo. Ahora podemos poner X. CAROLINE: G. DAVID J. MALAN: G va a la izquierda. S va bien. Todo derecho, A va todo el camino de la izquierda. CAROLINE: A, B, C, D. DAVID J. MALAN: Ahora, bien. Tenemos A, B, C. W de ir allí. Muy bien, T. CAROLINE: H, I, J. DAVID J. MALAN: H, I, J. Bueno. CAROLINE: En el centro, estoy gonna-- DAVID J. MALAN: OK. Así que ahora, vamos a clase de combinar estos diversos montones. Así la A a C, entonces veo D, y E y F, y G, y H e I. Niza. J, K. Y luego, esta pila es al revés, pero eso está bien. Por supuesto. Podemos cortar algunas esquinas. OK. Y entonces tenemos que W, X, Y, Z. CAROLINE: Sí. DAVID J. MALAN: Excelente. Así que un gran agradecimiento a Caroline para la clasificación de estos. [ANIMA] Gracias. Muchas gracias. Así que ahora vamos a considerar por un momento cómo Caroline anduvo haciendo eso, y qué es exactamente lo que fueron capaces a-- cómo fueron capaces de resolver ese problema cuando estábamos dado un montón de entradas aleatorias. Bueno, parece que hay era un poco de un sistema allí? Correcto. Así que las cartas anteriores en el alfabeto, ella era poner a la izquierda, y el últimas cartas en el alfabeto, que estaba poniendo en la derecha. Y tan pronto como se enteró algunas cartas proximales, unos que van uno al lado del otro, pondría los de orden. Y por lo que de alguna manera tenía estos pequeños montones de entradas ordenadas ocurren. Y eso es muy parecido a lo que la mayoría de nosotros los humanos harían. Nos tipo de tamizar a través de él, y nos gustaría tipo de disponer de un mecanismo. Pero podría ser difícil escribir hacia abajo en una fórmula per se. Se sentía un poco más orgánico que eso. Así que vamos a ver si podemos ahora atado el problema con menos insumos. En lugar de 26, vamos a hacer algo mucho menos con sólo decir, siete, detrás estas puertas, por así decirlo. ¿Hay sólo siete números? Y si el objetivo ahora en mano es encontrar un valor, vamos a ver cómo de manera eficiente podemos ir haciendo esto. Y vamos a ver si podemos ahora empezar a aplicar algunos números, o algunas fórmulas con las que describen la eficiencia de nuestro directorio telefónico algoritmo, nuestro algoritmo libro examen, y más en general, la búsqueda de información. Así que para esto, dejarme ir por delante, y en la pantalla táctil por aquí, poner un navegador web que tiene exactamente estas siete puertas. Y si pudiéramos conseguir otro voluntarios para venir por aquí, He puesto estas mismas puertas aquí. Voluntario rápida. Este uno-- demos van a un más rápido y más rápido ahora. Baja. ¿Cómo te llamas? TREVOR: Trevor. DAVID J. MALAN: Trevor? Muy bien, Trevor, vamos hacia abajo. Así que Trevor se ha ofrecido aquí para hacer un problema similar, pero uno que es más estrecho en su alcance, y eso va que nos permita tratar de formalizar ahora el proceso para la clasificación de estos números. Así Trevor, encantado de conocerte. Así que aquí es una matriz, por lo que hablar, una lista de siete puertas. Vaya por delante y nos encontrará en el número 50. Y a continuación, después del hecho, díganos cómo lo encontraste. En caso de ser-- bien. Sí, este es el que aquí? UH oh. OK. Hizo clic en esa. Bien. Y bueno. Ahora ha hecho clic en ese. Y te voy a dar el micrófono, de manera que usted lo tiene en un momento. Siga adelante y haga clic en el al lado que tiene la intención. Si bueno. TREVOR: ¿Puedo desmarca una puerta? DAVID J. MALAN: No, usted no puede desmarque. TREVOR: OK. Éste. DAVID J. MALAN: ¿Dónde quieres ir? ¿Cúal? TREVOR: Que uno. DAVID J. MALAN: No. TREVOR: OK. Éste. DAVID J. MALAN: Sí. Eso era bueno. Correcto. Entonces, ¿cuál era su algoritmo o procedimiento para hacer esto, Trevor? TREVOR: Me acaba de pasar por puertas hasta que encontraron un 50. DAVID J. MALAN: OK. Excelente algoritmo. Así que eso está bien. Porque, de hecho, si revelo lo que es detrás de estas otras dos puertas, lo que vamos a encontrar aquí es que sólo tenemos entrada aleatoria. Así que fue realmente como bueno como se puede conseguir. Y de hecho, tienes mejor que exhaustivamente buscando todo el conjunto, porque habría sido muy mala suerte si se hubiera golpeado el número 50 en el último lado. Pero ¿y si en lugar te dio una suposición. Supongamos que en cierto modo me todos estas puertas de todo, quedando con la números ordenados en esta ocasión, pero esta vez es en realidad un diferente-- este tiempo, en realidad está ordenada para usted. Y ahora el peligro en la mano es para golpear el número 50. TREVOR: OK. DAVID J. MALAN: ¿Cuál es el algoritmo va a ser? TREVOR: Bueno, si es ordenados, es bien va a ser-- si mayor a mayor, descendente, va a ser el primero, o si es todo lo contrario, será la última. Así que voy a tocar en la puerta, y a continuación, sólo tocar la última puerta. DAVID J. MALAN: Excelente. Correcto. Así que encontramos el número 50. Así que tan pronto como usted sabía fueron ordenados, nos fueron capaces de aprovechar esta suposición. Así que son demasiado parecido el ejemplo guía telefónica. Tan pronto como usted tiene, incluso con un pequeño problema como este, sus entradas pre-ordenados, podemos en realidad encontrar el valor discutible mas eficientemente. Y yo no digo que si era ordenados pequeño a grande o grande a pequeño, y por lo que era muy razonable para comenzar en un extremo o el otro encontrar realmente ese valor objetivo. Así que gracias a Trevor también. Y voy a propose-- muy bien hecho. Tenemos un pequeño clip, en realidad, que es uno de nuestros momentos favoritos en CS50, por el que a veces estas demos no todo vaya según lo planeado. Y de hecho ahora mismo, detuvo la interfaz equivocada con la que usar la pantalla táctil. Así que fue mi culpa no. Así que esto hará para Clip del próximo año como de por qué estaba haciendo clic en mi propia pantalla. Pero echemos un vistazo rápido a lo que sucedió el año pasado con Jay, quien se acercó, y mucho como Trevor aquí, voluntariamente, y en este breve clip, verás cómo esta misma demostración no hizo bastante revelar las mismas lecciones aprendidas. [REPRODUCCIÓN DE VÍDEO] -Todos Los que quiero que hagas ahora es de encontrar para mí, y para nosotros, en realidad, el número 50 un paso a la vez. -El Número 50? -El Número 50. Y usted puede revelar lo que es detrás de cada una de estas puertas con sólo tocar con un dedo. Maldición. [Risas] [FIN DE REPRODUCCIÓN] DAVID J. MALAN: Así que fue muy bien. Esas fueron las puertas sin clasificar. Y Jay, por supuesto, encontrado con demasiada rapidez. Trevor hizo un trabajo mucho mejor en términos de un momento de aprendizaje, por así decirlo, este año en tomando más tiempo para encontrarlo. Por supuesto, entonces nos dimos Jay una segunda oportunidad, por el que nos lo solucionaron las puertas, tal como lo hicimos para Trevor, y Trevor hizo muy bien esta vez. Pero Jay hizo un medio tan rápido. [REPRODUCCIÓN DE VÍDEO] -El Objetivo ahora es también nosotros encontrar el número 50, pero hacerlo algorítmicamente, y decirnos cómo va en ello. -OK. -Y Si lo encuentra, se mantiene la película. Si no lo encuentra, le das la espalda. -Hombre. -¡Oh! - [Inaudible] en Aceptar. Así que voy a comprobar los extremos primero para determinar si there's-- Oh. [Aplausos] [FIN DE REPRODUCCIÓN] DAVID J. MALAN: OK. Así clasificación puertas claramente conduce a una mayor eficiencia. Y así, dos veces más rápido es lo que quise decir no. Y así Jay tuvo suerte en ambas ocasiones. Y también tuvo suerte en ese último año, pedí algunos discos Blu-ray para dar a conocer realmente. Lo siento de este año, no tuvo la misma, Trevor. Pero mejor aún era hace unos años. Y algunos de ustedes podrían saber esto compañero, Sean, que cuando estaba en el CS50, fue impugnada con la exacta mismo problema, aunque en SD, como pronto verás, de vuelta en el día. Y usted encontrará que no sólo que tome un poco más de Jay, un poco más de Trevor, fue En realidad esta maravillosa oportunidad a participar casi todos en el gente a la Price is Right, fomentando él para encontrar el número que estábamos buscando. Vamos. echar un vistazo rápido. [REPRODUCCIÓN DE VÍDEO] -OK. Así que su tarea aquí, Sean, es la siguiente. He escondido detrás de éstos puertas el número siete. Pero escondido en alguna de estas puertas así son otros números negativos. Y su objetivo es pensar de esta fila superior de los números como se acaba de una matriz, o simplemente secuencia de las hojas de papel con números detrás de ellos. Y su objetivo es, sólo con la parte superior variedad aquí, me encontrar el número siete. Y estamos a continuación, vamos a criticar cómo usted va sobre hacerlo. -Correcto. Nos -Buscar el número siete, por favor. No. Cinco, 19, 13. [Risas] No es una pregunta con trampa. Uno. [Risas] En este punto, su puntuación no es muy bueno, por lo que así podría seguir adelante. Tres. [Risas] Continuar. Francamente, no puedo evitar preguntarme lo que estás siquiera pensar, así que-- [Risas] Sólo la fila superior, por lo que usted tiene de tres izquierda. Así que encontrar siete. [Risas] 17. Siete. [Aplausos] Correcto. [FIN DE REPRODUCCIÓN] DAVID J. MALAN: Así que pudimos ver a estos durante todo el día. Y, por supuesto, algunos de demostraciones de este año tal vez ahora terminar en el próximo vídeo del año también. Así que ahora vamos a realidad centrarse en los algoritmos aquí, y ver si no podemos Ahora empezar a formalizar cómo podemos ir sobre cómo obtener nuestros datos en este estado que está ordenada, por lo que en última instancia, podemos realidad buscarla en el diccionario de manera más eficiente. Y a pesar de que vamos utilizar conjuntos de datos bastante pequeños, como el que ocho números tenemos aquí en el tablero, en última instancia, podrían aplicar estas mismas ideas 1.000 entradas, un millón de entradas, 4 mil millones de entradas, ya que los algoritmos van a ser fundamentalmente los mismos. Y lo que esta es nuestra última oportunidad para que los voluntarios hoy en día, pero quizás el más complicado, para lo cual necesitamos ocho voluntarios para llegar y nos caminar por el proceso de clasificar lo que pronto estar en estos atriles aquí. Permítanme comenzar de nuevo aquí. Así que uno en el verde turquoise-- es? ¿Estás cometiendo? Dos. Baja. OK. Tres. Cuatro. Deje mí-- OK, cinco. Usted está siendo nominado por su amigo. Seis, siete y ocho. Vamos arriba. Correcto. Muchas gracias. Vamos arriba. Vamos arriba. Correcto. Así que lo que tenemos aquí-- y esto es uno de los más difíciles, ya que esto requerirá que el humor mí por un poco de tiempo. Usted será el número uno. ¿Cómo te llamas? ANNAN: Annan. DAVID J. MALAN: Annan. David. ¿Cómo te llamas? JOSEPH: Joseph. DAVID J. MALAN: José, usted es el número dos. SERENA: Serena, número tres. Stefan, el número cuatro. CYNTHIA: Cynthia. DAVID J. MALAN: Cynthia, número cinco. [Inaudible] DAVID J. MALAN: [inaudible]. David, el número seis. MATT: Matt. DAVID J. MALAN: Número de Matt siete. ¿Y? WAVERLY: Waverly. DAVID J. MALAN: Waverly, número ocho. Correcto. Si could-- gritos. Si todos ustedes, como su primer desafío, hay son ocho atriles aquí frente a la audiencia. Si pudieras poner sus números en estos soportes de música de tal manera que se alinean con el mismos números en el tablero. Así que ustedes ven como que por poner los números en esta música se encuentra aquí. Excelente hasta el momento. Excelente. OK. Así que ahora, vamos a pedir a la pregunta de varias maneras diferentes. ¿Cómo podemos ir sobre la clasificación esta gente aquí? Porque teníamos un par de enfoques anterior, por el cual fueron tipo de toma de dos cubos diferentes. Y entonces estábamos general recomponer las cosas juntos. Tan pronto como vimos dos números que pertenecían juntos, los ponemos juntos. Dos letras que van de la mano. Pero vamos a ver si nos no puede formalizar este, para que en última instancia, tenemos algunos pseudo-código se quiere, con el que puede resolver estos problemas. Así que ahora, estoy mirando estos números aquí. Y veo un montón de errores. En última instancia, quiero uno en el a la izquierda y ocho a la derecha. Y por lo que estoy viendo estos dos, cuatro y dos. ¿Y cuál es el problema, es obvio? Sí. So. Dos obviamente viene antes cuatro, así que usted sabe lo que? Permítanme primero tomo un enfoque codiciosos, si se quiere, tanto problema como establecer uno-- si recuerdan desde el Edición Estándar de de problemas Uno, donde sólo a nivel local a resolver el problema eso es justo aquí en frente de mí y ver a dónde me lleva. OK. Así que dos y cuatro, déjame ir adelante y sólo te intercambiar dos. Si usted puede mover físicamente ustedes mismos y de su papel, Parece que he conseguido el listar en mejor estado. Ahora, son buenos. Voy a seguir adelante, cuatro y seis, se ve bien. No es un problema. Seis y ocho, en Aceptar. Ocho y uno, otro problema. Porque lo que es cierto eso de las ocho y uno? Uno viene antes de las ocho, y así ¿qué debemos hacer? Vamos intercambie estos dos. Uno y ocho. Y ahora, voy a seguir adelante. Yo voy a seguir mirando hacia adelante. Y vamos a ver qué pasa. Ocho y tres, de Por supuesto, fuera de orden. De intercambio Let. Ocho y siete, por supuesto. Fuera de servicio. De intercambio Let. Ocho y cinco, por supuesto, vamos a swap. Correcto. Lista está ordenada. sí? OK, obviamente no. Pero es un poco mejor, ¿no? Debido aviso de lo que pasó. Cada vez que realiza un intercambio, una más pequeña número de tipo de percolado de esa manera, y un número más grande percolado de esta manera, o vamos a comenzar diciendo burbujear a la burbujeó izquierda o hacia la derecha. Ahora, no es suficiente, porque en el mejor de un número podría han movido un solo lugar hacia adelante, o en el peor, un número podría tener movido un punto más. Así que ya sabes lo que, este tipo de funcionado bastante bien hasta ahora. Déjame intentarlo de nuevo. Dos y cuatro, que están bien. Cuatro y seis, que están bien. Seis y uno, fuera de orden. Así que vamos a ustedes dos swap. Y ahora, observe el problema de comenzando a conseguir un poco mejor de nuevo. Seis y tres, fuera de orden. Vamos a ustedes dos swap. Seis y siete, ya está bueno. Siete y cinco, por supuesto, fuera de orden. Siete y ocho, en orden. Y ahora, puede ser que tenga que hacer esto unas cuantas veces más. Y de hecho, pensar por sí mismos quizás cuántas veces máximo podría yo tener que caminar de ida y vuelta? Volveremos a eso. Así que dos y cuatro siguen en Aceptar. Cuatro y uno, pues no. Así, intercambio de dejar. Y de nuevo, observe visualmente uno es tipo de burbujeo a la izquierda, donde debe estar. Cuatro y tres de intercambio. Cuatro y seis. Seis y cinco años de intercambio. Seis y siete. Siete y ocho son buenos. Bien. Estamos recibiendo aún mejor. Así que vamos a ver. Ahora, tenemos dos y uno. Por supuesto, cambiar. Dos y tres, tres y cuatro, cuatro y cinco, seis y siete, siete y ocho. Bien. ¿Y sabes qué? Porque hice un cambio allí, déjame hacer un cheque cordura. Déjame ir todo el camino de nuevo al principio. OK. Uno, dos-- yup, ¿ves? Algo andaba mal. Tres, cuatro, cinco, seis, siete, ocho. Y en este último paso, son Se siente cómodo con mi ahora alegando que se ordena? OK. Visualmente, eso es absolutamente cierto. Pero funcionalmente, lo hizo también acaba de suceder en ese último pase que le permite para confirmar que esta lista es de hecho ordenados? ¿Qué hice o no hacer esto último pase? AUDIENCIA: No hubo cambios. DAVID J. MALAN: Lo siento? AUDIENCIA: No hay cambios. DAVID J. MALAN: No hubo cambios. Así que sería estúpido de mi parte hacer eso mismo algoritmo de nuevo si yo no hice ninguna cambia la primera vez. Y el estado no ha cambiado. Ciertamente, yo no voy a hacer Cualquier cambio del segundo tiempo. Y así, es seguro ahora decir, la lista está ordenada. Y, de hecho, esto es ahora algo que vamos a general llamada de ordenamiento de burbuja, en el que por parejas, corregir errores de nuevo, y otra vez, y otra vez, y usted seguir adelante hacia atrás y adelante, y de ida y vuelta, hasta que no hacer este tipo de swaps, y en ese momento usted puede estar seguro, sí, terminado de fijar todos los errores. Vamos a restablecer y jugar diferente. Si ustedes podrían volver a el orden en que fueron hace un momento, que se veía así. Ahora, vamos a echar un enfoque un poco más como el libro del examen, por el que estábamos constantemente la selección de la letra del alfabeto que tipo de queríamos para hacer frente a la próxima. Tal vez fue una gran carta, como A, o una letra Z. baja Así que todo el mundo está de vuelta en este orden. Y ahora déjame hacer esto. Veamos sé que tengo ocho números aquí. Voy a seguir adelante y simplemente deliberadamente seleccione los elementos más pequeños. ¿Correcto? Esto parece intuitiva también. ¿Por qué no me parece el más pequeño elemento, lo puso donde pertenece, a continuación, obtener el siguiente elemento más pequeño, puesto donde pertenece, y sólo tiene que repetir. Debido a que de manera intuitiva, que debería funcionar también. Así que cuatro, que es un número muy pequeño. Voy a recordar de dónde es. Espera un minuto. Dos es más pequeño. Permítanme ahora recuerdo que dos es, y olvidarse de cuatro. Nos ocuparemos de eso más tarde. Seis, no me interesa. Ocho, no estoy interesado. Uno de ellos es mi nuevo número pequeño. Así que voy a recordar dónde uno es. Tres, no le interesa. Siete, no le interesa. Cinco, no le interesa. Así que sin caerse la etapa de este año, Voy a agarrar número uno-- y lo que era tu nombre? ANNAN: Annan. DAVID J. MALAN: Annan. Y si usted puede unirse a mí en el principio de la lista, vamos te desanime a donde perteneces. Unfortunately-- ¿cómo te llamas? STEFAN: Stefan. DAVID J. MALAN: Stefan se encuentra en el camino. Así que antes de Stefan resuelve este problema, ¿qué debemos hacer? ¿Qué hacemos con Stefan? AUDIENCIA: [inaudible]. DAVID J. MALAN: OK. Así que podríamos hacer eso. Podríamos especie de tomar Stefan y su cuatro, y sólo hay que poner en una variable y aferrarse a ella para una cierta cantidad de tiempo, haciendo así espacio para el número uno. Y eso no es malo. Que podría sugerir, por qué no hacer sólo hay que poner Stefan aquí? ¿Por qué podría esto violaría un solo de las ideas que empezamos hablando de la última vez, la semana pasada? ¿Sí? AUDIENCIA: [inaudible]. DAVID J. MALAN: No hay índice para ello. Si usted piensa en esto, de hecho, como un matriz, esto es como una cosa negativa, así que no hay memoria realidad aquí si esta es de hecho una matriz, como hemos declarado la semana pasada en la conferencia. Así que no debemos hacer esto. Podríamos almacenarlo en una variable. O ¿sabes qué? Oí que alguien sugiera que. ¿Qué otra cosa podíamos hacer con Stefan? ¿Por qué no acaba de desalojarlo y lo puso sobre donde estaba el número uno. Así que si quieres ir allí. Y de hecho, esta es una bastante buena solución. Ahora, por un lado, no tengo clase de hecho el problema peor. Cuatro es ahora más lejos desde donde debe estar. Debe ser hacia este medio. ¿Pero sabes que? Eso podría haber sido mala suerte. Tal vez el número ocho estaba aquí. Y por eso, tal vez lo haría han tenido suerte, y empujado de ocho más cerca del final. Así que al final del día, En cierto modo todos promedia. No necesitamos que se preocupan por cuatro. Todo lo que me importa en este momento es seleccionar el elemento más pequeño. Y ahora, ¿qué voy a hacer es olvidarse de número uno de forma permanente, porque sé que el lista detrás de mí ahora ordenadas. Así que mi lista era previamente tamaño ocho. Ahora, es del tamaño de siete. Así que mi problema es conseguir más pequeño, aunque linealmente. Así que ahora, voy a seleccionar el actual elemento más pequeño, dos. Seis, ocho, cuatro, tres, siete, cinco. Ese fue el elemento más pequeño. Entonces, ¿qué voy a hacer con-- ¿cuál era su nombre? JOSEPH: Joseph. DAVID J. MALAN: José? Vamos a dejar a José en su lugar. Ahora, voy a fingir que estos chicos son-- así, Sé que estos dos ya están ordenados. Ahora vamos a centrarnos en la resto de la lista. Seis es la corriente más pequeña. Ocho es más grande. Cuatro es ahora la corriente más pequeña. Tres es ahora la corriente más pequeña. Y ahora, voy a seleccionar tres, que es-- ¿cuál es tu nombre? SERENA: Serena. DAVID J. MALAN: Serena, si pudieras apoderarse de su número y de intercambio con-- Kalsang: Kalsang. DAVID J. MALAN: Kalsang. Vamos hacia atrás, y estamos va a cambiar esos dos. Y ahora, vamos a poner esto en piloto automático. Voy a ir y dejar a ustedes para seleccionar los siguientes elementos más pequeños. Dun, dun, dun, dun. Número cuatro, ¿qué debe hacer? Excelente. Ahora, yo voy a hacer otro pase. Dun, dun, dun, dun. Veo cinco es el inmediatamente inferior. Ahora, voy dar otro paso. Dun, dun, dun, dun. Seis es el más pequeño. Bien. Siete es el más pequeño. Ningún cambio. Ocho es el más pequeño. Hecho. Así que lo que acabamos de hacer de forma iterativa seleccionar un elemento después de la otra es poner en práctica algo que estamos va a formalizar como ordenación por selección. Y es tal vez incluso más simple de explicar, en que, literalmente, todo lo quiero hacer es mantener que van y vienen a través de la lista la selección, el siguiente elemento más pequeño, hasta que haya terminado. Por lo que es aún más simple, tal vez intuitivamente, que el pasado. Probemos última. Si ustedes podrían restablecer mismos en las siguientes posiciones por última vez, vamos a ver si no podemos ahora formalizar otro enfoque. De hecho, lo haría alguien por ahí gustaría proponer ¿de qué otra podríamos ir haciendo esto? Sin lanzando palabras de moda o tipo de las respuestas que ya se conocen, simplemente intuitivamente, ¿qué podíamos hacer? AUDIENCIA: [inaudible]. DAVID J. MALAN: Sí. Así que hay algo de gran intuición allí. Las buenas cosas parecen suceder hasta el momento en ciencias de la computación cuando dividimos y conquistar el problema de dividir por la mitad y mitad y mitad. Y así, de hecho, nos podría empezar a hacer eso. Y de hecho, que va a ser, vamos a ver, una de nuestras mejores soluciones todavía. Pero volvamos a la que en poco tiempo. De hecho, vamos a hacer que un poco más tarde esta semana. ¿Qué más podríamos hacer para solucionar esto? Así que aquí todo el mundo está en orden aparentemente aleatorio. ¿Tu sabes que? En lugar de ir y venir, ida y vuelta, de ida y vuelta cada vez, esto se siente como Estoy haciendo un montón de pie. ¿Por qué no acaba de empezar a el principio de la lista, y sólo hay que poner de cuatro que le corresponde? Así que permítanme asumo por el momento que mi lista es solamente este primer elemento. Es de cuatro ordenados en este momento en el tiempo, si todo lo que me importa es todo aquí? Esta es una especie de trivialmente cierto, ¿no? Al igual que la lista que contiene un número, y que el número cuatro es, obviamente, ordenadas. Así que permítanme estipulo que esta lista está ordenada. Pero ahora tengo el resto de esta lista. Así que ahora, me encuentro con dos. ¿De dónde viene de dos, obviamente, pertenecer con respecto a cuatro? Antes de cuatro. Entonces, ¿qué puedo hacer aquí? ¿Cuál es tu nombre? Otra vez? JOSEPH: Joseph. DAVID J. MALAN: José, si se pudiera dar un paso atrás por un momento con su número. Y ahora lo que debe Stefan hacer aquí? Vamos a cambiar de puesto Stefan aquí. Y ahora, vamos a Joseph entrar aquí. Y ahora, déjame pretendo que todo lo que aquí se ordena. Por lo tanto, resultado similar, pero una enfoque fundamentalmente diferente. Ni siquiera he mirado lo que hay ahí abajo. Sigo teniendo los elementos como se les entregaron a mí, y tratar con ellos. Así que ahora, veo el número seis. ¿A dónde pertenece número seis? Tenemos dos, cuatro, seis. Exactamente dónde está ahora. Así que vamos a dejar que por sí sola, y ahora afirmar que esta parte de la lista ahora está ordenada. Y así, esto se siente fundamentalmente diferente, ya que sólo soy moviéndose a través de la lista aquí linealmente, y estoy Nunca doblar la espalda. Sí. Correcto. Así ocho, donde pertenece usted? Aquí. Perfecto. Así que ahora, uno. UH oh. Esto se siente como si fuera va a ser caro. Ahora, en el algoritmo anterior, Yo sólo cambié personas. Así que yo le ponga todo el camino en al principio, pero luego se trasladó a José. Pero si me mudo Joseph, ahora lo que va a estar mal? Ahora, tengo una especie de undone-- tengo dado un paso hacia adelante y luego un paso atrás, porque ahora Joseph estaría fuera de orden. Así que vamos a hacer esto. Si usted podría tomar el número uno y un paso atrás por un momento. ¿Cómo podemos put-- lo era tu nombre? ANNAN: Annan. DAVID J. MALAN: Annan en su lugar? ¿Qué debe ocurrir con respecto a dos, cuatro, seis y ocho? Todos ellos necesitan cambiar. Así que si las ocho le gustaría cambiar primero, luego seis, luego cuatro, luego dos. Y entonces Annan, si lo gustaría venir aquí, bien. Pero aquí, acabamos de tipo de pagado un precio en un punto diferente en el algoritmo. Mientras que la última vez con la selección especie, e incluso una especie de burbuja, Estoy caminando hacia atrás y adelante, atrás y adelante, que sin duda es la suma de en cuanto a tiempo, y, literalmente, paso a paso. La ordenación por inserción, en un primer momento vista, parece que es súper inteligente, porque yo sólo soy hacer, el progreso gradual lento, pero yo no voy esta ida y vuelta. Pero si alguien es de hecho fuera de orden, notificación todo el trabajo que tenía que hacer. Tuve que mover la mitad de la lista sólo para hacer espacio para el número uno. Así que es la misma cantidad de trabajo hasta el momento se siente, simplemente un tipo diferente de trabajo. Continuemos. Así que ahora que sabemos que todo el mundo entre uno y ocho son ordenados. Aquí, no tengo el número tres. Si te gusta para recoger número tres, un paso atrás una. ¿Y qué es lo que ustedes necesitan hacer? Sí. Así que esa es otra de una, dos, tres pasos. Tres unidades de tiempo que solo cuestan mí, así que tres ahora puedo encajar. Finalmente, siete. Vamos a seguir adelante y tener usted toma un paso atrás. Esto sólo nos va a costar una unidad de tiempo, pero eso está bien. Y ahora, cinco de ir a ser un poco más caro. Si desea dar un paso atrás. Tenemos que pasar ocho, y siete, y seis. Y entonces todo el mundo está ahora ordenadas. Así que una gran parte de nuestros voluntarios aquí. Muchas gracias. [Aplausos] Gracias a todos. Gracias a todos. Así que vamos a ver ahora cómo costosa todo eso era. Vamos a considerar tal vez la más simple de estos, ordenamiento de burbuja. Y digo más simple, sólo porque se puede resolver con avidez por solo solucionar el problema por parejas aquí. Solucionar el problema de pares aquí, una y otra vez y de nuevo, repitiendo como muchos veces que realmente necesitan. Así resulta que con una especie de burbuja, bueno, cuántos pasos tengo que asumir la primera pasada de ese algoritmo? Podría take-- vamos a ver-- uno, dos, tres, cuatro, cinco, seis, siete. Y hay ocho elementos aquí. Así que es como n menos pasos de 1 a llegar desde el principio de la lista hasta el final de la lista. Pero con la selección especie, recuerdo que soy la selección de los elementos de una y otra vez y otra vez que es más pequeño, Estoy poniendo en su lugar, pero entonces yo no soy mirando detrás de mí otra vez. Así que creo que es un poco más clara a continuación, que la primera vez, yo podría tiene que tomar todo n menos pasos de 1 para encontrar el elemento más pequeño. Entonces los puse en su lugar, y yo desalojar a todo el que estaba aquí antes. Pero entonces yo no tengo que seguir buscando en este elemento, porque yo sé que es ya los más pequeños. Así que ahora, puedo mirar a sólo siete elementos, entonces seis elementos, a continuación, cinco elementos, luego cuatro elementos. Y así, matemáticamente, si n es el número de elementos o números que empezamos con, se puede imaginar que este es el mismo que n menos 1, más n menos 2 pasos, más n menos 3 pasos, más n menos 4 pasos, todo el hasta llegar a un solo paso. Y estoy en mi última persona. Y si usted recuerda que una gran cantidad Estadísticas de libros o libros de matemáticas tener esas fórmulas en el tapa dura atrás o delante de ellos, resulta que esta serie puede expresarse más sencillamente como n veces n menos 1 sobre 2. Y está bien si eso no es a la vanguardia de su mente. Pero esto es cierto. Eso es sólo una manera más sencilla de escribir. Y entonces si usted piensa de nuevo a la escuela primaria, cuando acaba de empezar a multiplicar cosas fuera, esto, por supuesto, es simplemente n al cuadrado menos n dividido por 2. Lo único que he hecho es ampliar las expresiones allí. Y así vamos a reescribir esta un poco diferente. Eso n al cuadrado dividido por 2 menos n / 2. Así que de nuevo, yo soy sólo un poco de la aplicación un poco de aritmética gobierna allí. Pero note ahora que el mayor plazo En esta expresión, por así decirlo, es que n al cuadrado. Así que sí, es n al cuadrado dividido por 2, menos n / 2. Pero, en general, si n es va a ser un gran valor, Voy a decir que n al cuadrado va a ser el factor dominante. Es sólo va a ser un contribuyente más grande con el número de pasos que n / 2. Entonces, ¿qué quiero decir con esto? Probemos un ejemplo sencillo, incluso aunque las matemáticas consigue un poco grande. Así que supongamos que tenemos 1 millón de personas en el escenario, o 1 millón de cosas que queremos ordenar. Vamos a enchufe de un millón exactamente en esa fórmula para ver la cantidad de pasos que toma total de para ordenar un millón de elementos usando por ejemplo, ordenación por selección. Así tendríamos la misma fórmula que antes. Me conecto un millón, por lo que tengo un millón al cuadrado dividido por 2, menos de un millón dividido por 2. Si hago eso matemáticas de antemano aquí, tenemos 500 mil millones menos 500.000, que nos da 499999500000, que es bastante maldito grande. De hecho, si se compara ahora 499000000000, 999 millones, 500.000 contra nuestro valor original, 500 mil millones, es tan condenadamente cerca. ¿Correcto? n al cuadrado dividido por 2 da nosotros-- o más bien, n al cuadrado dividido por 2 nos dio 500 mil millones. Eso es bastante maldito cerca a 499999500000, es decir, restando off 500000, o, más generalmente, restando off n al cuadrado, no es realmente un gran problema. El n al cuadrado hace que estos números crecen muy rápido. Ahora, esto es importante sólo en la medida como nosotros, como los informáticos, generalmente no se va a importar mucho sobre los matices de estas fórmulas y exactamente lo que el respuestas precisas. Nos preocupamos sólo eso, ¿sabes qué? Al final del día, esta fórmula es del orden de n al cuadrado. Sí, estamos dividiendo por 2 en ese país. Sí, estamos restando fuera n menos 2. Pero al final del día, el término que realmente nos duele y nos cuesta un montón de pasos es ese término cuadrado. Y así lo que un científico de la computación se va a hacer en general es ignorar todos los términos de orden más pequeños, y basta con ver la que contribuye más al costo. Y esto es bueno, porque podemos ahora hablar en mucho mayor generalidad sobre algoritmos, y puede compararlos. Y el hecho de que soy el uso de esta O es deliberado. Cuando digo que en el orden de, estoy específicamente se refiere a algo llamado grande O. Y gran O es una notación que una computadora científico utiliza para describir un límite superior en algo. Así que si usted dice que un algoritmo es en gran O de n al cuadrado, como he propuesto sólo un Hace momento, que los medios que en términos de su funcionamiento tiempo o su eficiencia, que se necesita en el orden de n cuadrado pasos. Tal vez más, tal vez menos. Pero es del orden de n al cuadrado. Y ese es el límite superior. No va a ser más doloroso que eso. No va a ser n en cubos o 2 a la n, o algo mucho más grande. Esta es una cota superior en lo que el costo es. Así que teniendo en cuenta que, vamos a considerar sólo algunos ejemplos. Y esto es sólo una lista finita tiempos de ejecución de los muy comunes para los algoritmos que está destinado a ser ilustrativo de algunas cosas que hemos ya se ha visto. Así, por ejemplo, en el caso de ordenación por selección, lo que estoy diciendo aquí es en ejecución que la selección de especie el tiempo es del orden de n al cuadrado. En el peor de los casos, voy a tener un montón de números aleatorios aquí. Y como vimos matemáticamente, si sigo caminando a través de la lista, a través de la lista, seleccionando el inmediatamente inferior elemento y otra vez, si yo realidad anote todos los pasos Estoy tomando como propuse formulaically antes, es del orden de n al cuadrado medidas que estoy tomando. Y resulta que la burbuja clasificación y ordenación por inserción son tan lento en el peor de los casos. Consideremos, por ejemplo, la ordenación por inserción, el último algoritmo con el que tratamos, que tenían nos fijamos en el elemento, y luego insertarlo donde pertenece. Y luego nos fijamos en el siguiente elemento, y se inserta donde pertenece. Así que considera el mejor escenario posible. Supongamos que yo tenía mis voluntarios alinear literalmente así, uno al ocho, ya ordenados. ¿Cuántos pasos es la ordenación por inserción va a tomar para ordenar a ocho personas, si llegan en el escenario buscando de esta manera? Ocho personas ya ordenados. Y uso ordenación por inserción. El último de los algoritmos. Bueno, vamos a recrear rápido real. Así que si me pongo aquí, lo veo. ¿Por dónde pertenecen? Pertenece aquí. Veo dos. ¿De dónde viene dos pertenecen? Aquí. Veo tres. ¿De dónde viene tres pertenecen? Aquí. Veo cuatro. Aquí. Cinco, seis, siete, ocho. No hay razón para repetir a mí mismo. Y así, el número de pasos es que en términos de n? Es del orden de n pasos, ¿verdad? n menos 1. Pero tomé una serie lineal de pasos, y ahora he terminado. Así que ese es el mejor de los casos, sin embargo. ¿Y el peor de los casos? Lo que ocho eran de allí, y siete eran allí abajo, y uno y dos eran de aquí, por lo que que la lista se invirtiera en verdad? Bueno, lo que sucede de hecho si este es el número? Y vamos a hacer sólo un par de ejemplos. ¿Qué pasaría si, de hecho, el número ocho es aquí, y los gritos number--. ¿Y qué si, de hecho, el número ocho es todo el camino hasta aquí, y estoy usando la ordenación por inserción? OK. Reclamo en este momento está en su lugar. Pero ahora, seven-- ¿dónde van siete años? Por supuesto, no hace falta aquí. Así que tengo que mover y ocho más de un lugar. Ahora seis, ¿hacia dónde va? Bueno, está bien. Ahora, tengo que mover y ocho más un lugar y siete más de un lugar, y luego me dejo caer seis. Así que la primera vez, el costo mí un paso de arreglar las cosas, entonces me costó dos pasos para arreglar las cosas. ¿Cuántos pasos es va a tomar para solucionar cosas para poner cinco en el lugar correcto? Tres. Porque ahora tengo que mover uno, dos, tres. ¿Cuántos pasos se va a tomar poner cuatro en el lugar correcto? 4 y 5, además de 6, más 7. Y lo que es matemáticamente idéntica a lo que hemos descrito para la selección de género. Tenemos esta serie eso es sólo el aumento. 1 más 2 más 3 más 4, o por el contrario, 7 plus 6 más 5 más 4 añade hoy de efectos a del orden de n al cuadrado. Así que permítanme estipulo también que ordenamiento de burbuja es también n al cuadrado. Porque con ordenamiento de burbuja, cada vez que voy por la lista, Estoy tomando más o menos cuántos pasos? Cada vez que, literalmente, caminar desde allí hasta allí? Alrededor de n pasos. Pero ¿cuántas veces puede ocurrir que pasar por la lista? Bueno, más o menos n tiempo. Tal vez n menos 1, pero más o menos n veces. Bueno, ¿por qué es eso? Bueno, con la burbuja del tipo, si partimos de ordenamiento de burbuja, con la lista en la peor posible situación, que de nuevo es completamente al revés, lo que va a pasar? Voy a través de la lista, y el número de uno pertenece todo el camino por allí. Pero con la burbuja del tipo, ¿hasta dónde puede uno pasar mi primer pase a través de la lista? ¿Cuántos puntos es lo que obtiene más cerca de el lugar correcto? Solo uno. Así que si usted tipo de razón a través de este, cada vez que a través de este algoritmo, Teniendo aproximadamente n pasos de David. Pero, ¿cuántos pases a través de la lista es que va a tomar para que uno de burbujas a la izquierda donde pertenece? Él tiene que moverse como, n espacios de esta manera. Así que para hacer la clasificación de la lista, Tengo que ir y venir n veces. Y cada vez, estoy mirando a n elementos. Lo mismo ocurre con las cosas n n veces en del orden de n al cuadrado. Ahora, vamos a ver de alguna de los cortos que se incrustan en el siguiente problema de CS50 establecer, otro enfoque a estos, pero por ahora, vamos a considerar otras veces se ejecutan, especialmente si los toman de clasificación un poco de tiempo para hundirse en. ¿Qué es un algoritmo que hemos visto ya que lleva del orden de n pasos? ¿Qué se debe tomar una serie lineal de los pasos que hemos visto hasta ahora? ¿Que es eso? La búsqueda en el directorio telefónico. El primer algoritmo. ¿Correcto? Dónde estamos linealmente la búsqueda de Mike Smith? Ciertamente. Desde la semana cero, cuando empecé convertir una página a la vez, e incluso le dije que era una especie de un algoritmo sensación lineal, y tuvimos esa foto en la tablero con la línea roja directa y el amarillo recta línea, esos eran de hecho algoritmos que son en gran O de n. Porque para encontrar Mike Smith en un teléfono libro de n páginas, en el peor de los casos, me n medidas podría tomar. ¿Qué hay de tomar asistencia? Uno dos tres CUATRO CINCO SEIS. ¿Qué es el tiempo de ejecución de la presente algoritmo para la toma de asistencia? O grande de n, ya que en teoría me tienes que apuntar todos en la sala. Ahora como un aparte, ¿qué pasa con la otra optimización de semana cero? Dos, cuatro, seis, ocho, 10, 12. Un científico de la computación lo haría darse cuenta, espere un minuto, eso es del orden de n dividido por dos pasos. ¿Correcto? Debido a que estoy haciendo dos personas a la vez. Pero vamos a ignorar los términos de orden inferior, y nosotros sólo vamos a tirar la divide por 2, y decir, gran O de n para que el algoritmo también. ¿Qué tal este? Nos saltaremos sobre algunos de ellos, pero lo que era un algoritmo que era log de n? Que tuvo más o menos log n pasos? El divide y vencerás. Exactamente. Al igual que el ejemplo de libro de teléfono en semana cero y el día de hoy, donde nos dividimos el problema De nuevo y de nuevo y de nuevo. Dibujamos en la pizarra en la semana cero como una línea verde curvado, y nos dijo ese día que era un algoritmo logarítmico. Y de hecho, el número de pasos que lleva a cabo divide y vencerás, o búsqueda binaria como vamos a empezar llamándolo, como en la guía telefónica, es del orden de registro y pasos. Y esto es un poco de un ser extraño. Lo que da un paso, o más específicamente un número constante de pasos? Tal vez sea de dos, tal vez es tres, pero un informático solo simplifica tan grande O de 1, un número constante de pasos. ¿Qué es algo que podría hacer que toma un número constante de pasos? ¿Cuál es el tiempo de ejecución de aplaudir? Constante de tiempo. ¿Correcto? Al igual que, ¿cuál es el tiempo de funcionamiento del hacer cualquier cosa que toma sólo una operación, como imprimir F Hello World. Eso podría decirse que la constante de tiempo, menos que menos caso esquina con la impresión M, lo que podría el tiempo de ejecución de impresión F realidad sea? ¿Y por qué? ¿Qué es la n de medición en ese caso? AUDIENCIA: [inaudible]. DAVID J. MALAN: Exactamente. El número de caracteres queremos imprimir. Así que es muy sensible al contexto. Hoy, nos hemos centrado mucho en las letras y los números aquí en el tablero. Pero también podría ser personajes de una cadena real. Así que resulta que hay otro medida que comenzará a preocuparse, y eso es todo lo contrario de gran O, por decirlo así. Esa es la notación omega. Mientras que gran O significa lo que es, la límite superior de su tiempo de funcionamiento? Como máximo, la cantidad de tiempo podría tomar algo? Omega-- siento esto sigue llegando up-- es lo contrario de eso, mediante el cual se trata de un límite inferior en el cantidad de tiempo que algo podría tomar. So. por ejemplo, ¿qué es un algoritmo que tome medidas siempre n al cuadrado? Bueno, uno de los algoritmos que he visto Hoy en día, de hecho, podría ser que también. Selección tipo. Selección especie es bastante estúpido. Incluso si la siento algorithm--, aun si la matriz ya está ordenado, ordenación por selección va a seguir caminando por la lista para asegurarse de que cuenta con el más pequeño elemento de una y otra y otra vez. Y a pesar de que los seres humanos en el público sepa que, espera un minuto, que ya pasó el elemento más pequeño, el ordenador no sabe que hasta que se vea todo el camino a través de la lista. Del mismo modo, una cota inferior que también puede ser tenido en cuenta podría ser el momento lineal. ¿Cuánto tiempo se tarda en ordenar n elementos en la mejor caso usando algo así como una especie de burbuja? Supongamos que su lista ya está ordenado. Dijimos burbuja especie adquiere del orden de n al cuadrado pasos. Pero lo que si ya está ordenada? ¿Y si te das cuenta después un paso a través de la matriz que usted ha hecho no hay permutas? ¿Es necesario seguir haciendo más pases? No. Así que un límite inferior en el ordenamiento de burbuja podría decirse que es lineal. Omega de n. Y podemos ver otros de estos también. Así que vamos a echar un vistazo rápido en apenas una visualización aquí para ver cómo éstas se distinguen. Voy a ir por aquí a esta página que está disponible en la página web de C50, pero va a ser un dolor para conseguir trabajo, ya que utiliza una tecnología llamada Los applets de Java, que es un en gran medida sin apoyo en estos días, al menos por cromo y algunos otros. Y déjame ir adelante y acelerar este y explicar lo que está pasando. Esta es una demostración de la burbuja especie, el primer algoritmo nos miró. Y es una visualización en el que cada de estas barras representa un número. Cuanto más grande sea la barra, cuanto mayor sea el número. Cuanto menor sea la barra, cuanto menor sea el número. ¿Y qué se puede ver visualmente, incluso aunque esto va muy rápido, es que la barra roja es como yo, caminando hacia atrás y fijar sucesivamente problemas. Se puede ver que los elementos más grandes son de hecho burbujeando hacia la derecha, y los elementos más pequeños están burbujeando hacia la izquierda. Y aquí, si realmente mirar más de cerca, realmente podemos contar el número de comparaciones y swaps que se estaban haciendo. Pero en lugar, echemos un vistazo en el segundo algoritmo vimos antes con nuestra voluntarios, selección de ordenar. Visualmente, tiene una muy diferente efecto. Pero es, de nuevo, muy intuitiva, en que guardemos la selección de la próxima más pequeña elemento, y nos dieron un poco de suerte. Eso se sintió fundamentalmente más rápido. Pero si nos encontramos una y otra vez y otra vez con una gran cantidad de insumos, veríamos que es de hecho todavía en gran O de n al cuadrado. Vamos a hacer un último de un aquí, la ordenación por inserción, que fue el tercer algoritmo nos miramos, y el recuerdo que éste se ocupa de la elementos, ya que los encuentra, Pero entonces quizás turnos las cosas para hacer espacio, la inserción de elementos que pertenecen. Y esto también termina dando la resultado final. Ahora los tres de los sentí bastante rápido. Y, de hecho, yo los encontré a un ritmo bastante bueno. Pero fundamentalmente, son todos bastante horrible, para ser honesto. Todos estos algoritmos hasta ahora que se ejecutan en gran O de n al cuadrado tomar un poco de tiempo para correr en el final. Y de hecho, podemos ver y sentir este último si me levanto esta tercera y última demostración. Esta es otra visualización que va para mostrar ordenamiento de burbuja en la izquierda, ordenación por selección en el medio, y algo que, como uno de nuestro mano plantea sugirió anteriormente, ordenamiento por mezcla a la derecha. Un divide y vencerás la estrategia de la derecha. Y eso es, de hecho, lo que estamos ir a ver el miércoles. Pero el tiempo éstos se ejecute en paralelo vamos. Es más o menos el mismo número de elementos, todos funcionando al mismo tiempo. Burbuja especie vs selección especie vs fusión tipo. Ahora, todos están corriendo en teoría al mismo tiempo. La CPU está funcionando a la misma velocidad, pero puede sentir lo aburrido que es va muy rápidamente para convertirse, y cuán rápido cuando inyectamos un poco de semana algoritmos de cero puede que acelerar las cosas. Y ahora vamos a comparar estos en una última forma. Voy a seguir adelante el sitio web del CS50, donde tenemos este último eslabón para hoy, donde alguien en Internet amablemente armar un vídeo que capta lo diferente clasificación algoritmos suenan. Esta es la ordenación por inserción. [SONIDO] Por el cual usted está solicitando una frecuencia basado en la altura de la barra de bar. Se trata de ordenamiento de burbuja. [SONIDO Warped] Que hasta la próxima es-- venir al lado es-- ordenación por selección, donde de nuevo, estamos seleccionando el siguiente elemento más pequeño, y podemos ver que cada vez más de izquierda a derecha. Combinar especie, por lo que nuestro ganador la fecha de hoy. Observe cómo está dividiendo cosas en [inaudible] media y los cuartos. Tipo Gnome, que no tenemos hablado, y crea visualmente y audally un poco de un diferente forma y sonido. El ir y venir, la limpieza de las cosas. También puedes ver heapsort en la página web de este tipo. Y eso es. Nos vemos la próxima vez. [Whooshing Y MÚSICA]