CS50 2013 - Week 3, continued

CS50 2013 - Week 3, continued

>> [REPRODUCCIÓN DE MÚSICA] >> DAVID J. MALAN: Muy bien. Así que bienvenidos de nuevo. Esto es CS50, y el ISAl final de la tercera semana. >> Así que recuerda, en las últimas semanas,hemos pasado un poco de tiempo en C, en la programación, en la sintaxis. Y es muy normal, si usted todavía estáluchando con problemas n 2, para ser golpearse la cabeza contra la pared. Es mensajes de error crípticos buscandoy los errores que no puedo perseguir. Porque, puede estar seguro, que en tan sólo untiempo de algunas semanas que mirar hacia atrás en cosas como César, y [? V-Genair,?]tal vez incluso de grietas y darse cuenta de lo lejos que ha llegadoen un corto período de tiempo. Así que si te sirve de consuelo,colgar en él por ahora. >> Hoy, sin embargo, empezamos a transicióna las cosas de alto nivel. Y empezamos a dar por sentado queustedes saben cómo programar, o por lo menos los inicios deese nivel de comodidad. Y vamos a empezar a considerar cómo podemosir sobre el diseño de programas más efectivamente. ¿Cómo podemos ir sobre la optimización de laeficiencia de los algoritmos, y la solución generalmente másproblemas interesantes. Y comenzando a dar por sentado que,si quisiéramos, podríamos codificar cualquier de los ejemplos que tenemos en mente. Así que hoy, nosotros no tocamos el tecladopara cualquier tipo de código. Será nivel mucho más alto, yen última instancia, sobre la resolución de problemas. >> Así que para llegar a ese punto, permítanme proponerque los siguientes siete rectángulos representan siete puertas, detrás deque son un montón de números, entre los cuales es el número 50. Permítanme proyecto esta en estaAquí la pantalla también. Y proponemos que necesitamos un voluntario queayudarme a encontrar un número delante de el Internet para ver. Vamos arriba, en la rosa. Está bien. ¿Cómo te llamas? >> JENNIFER: [inaudible] >> DAVID J. MALAN: Lo siento? >> JENNIFER: Jennifer. >> DAVID J. MALAN: Jennifer. Muy bien, Jennifer. Gusto en conocerlo. Vamos arriba. Así que estas aquí hay siete puertas, y lo queMe gustaría que usted pueda hacer por nosotros aquí, frente a todos sus compañeros de clase,nosotros es encontrar el número, 50. Para encontrar un número, puede mirar detráscualquiera de estas puertas con un simple toque en una de las puertas, y serevelará su número. Y vamos a ver lo rápido quenos puede encontrar el número, 50. >> 15. 16. 50. Muy bien hecho. Está bien. Ronda de aplausos para Jennifer. >> [Aplausos] >> Está bien. Entonces, ¿cuál fue su estrategia paraencontrar el número, 50? >> JENNIFER: Um, pensé que tal vez si - [Inaudible] >> DAVID J. MALAN: Oh. Déle un segundo. Así fue su estrategia paraencontrar el número, 50? >> JENNIFER: Así que acabo de empezar en elempezando a ver lo que el primer número estaba, y entonces pensé, tal vez sique están ordenados, que voy a seguir tocando más arriba? >> DAVID J. MALAN: OK. Y parece que hemos encontradoque ese sea el caso. Aunque, vamos a pelar las capassólo un poco, y quieres ir adelante y revelar las otras puertasque podría haber elegido? >> JENNIFER: Oh, querido. >> DAVID J. MALAN: Ah. >> JENNIFER: Así que tuve suerte. >> DAVID J. MALAN: ¿Así que tuvo suerte. Está bien. Así que no está mal. Pero eso es una interesantevisión, ¿no? Si usted asumió, y lo hizo llegar,de hecho, un poco de suerte allí. Pero si se supone que las cifras eranordenados, ¿puedes ser más precisos cuanto a la forma en que influyósu comportamiento? >> JENNIFER: Así que si ellos fueron ordenados, mepensé que tal vez menor a mayor. >> DAVID J. MALAN: OK. >> JENNIFER: O si esto terminó siendomuy grande, entonces mayor a menor. >> DAVID J. MALAN: OK. Así mayor a menor, omenor a mayor. Pero permítanme proponer, suponga que tieneconseguido de mala suerte, y supongamos que no eran, de hecho, ordenados, ¿cuántos deesas puertas puede ser que le han tenido que echar un vistazo detrás en que peor de los casos? >> JENNIFER: Todos ellos. >> DAVID J. MALAN: Todos ellos. Así que vamos a generalizar eso como n. Sucede que hay 7, pero a dejar másen general, dicen que hay n puertas en el Aquí la pantalla. Así que en el peor de los casos, usted tendría quepara mirar detrás de 7 puertas, o puertas n. Y por lo que este es en realidad, es un poco desuerte hoy, pero en realidad es una relación lineal algoritmo de clases, a pesar de queeran una especie de saltar alrededor. ¿Es eso justo? >> JENNIFER: Si. >> DAVID J. MALAN: Bueno, déjame ver si suestrategia cambia si nos mueven a nuestro segundo ejemplo aquí con7 puertas diferentes. Los mismos números, pero estomomento en que se ordenan. ¿Cuál es su estrategia de aquí va a ser,tratando de poner fuera de su mente lo que los otros números eran - >> JENNIFER: OK. >> DAVID J. MALAN: - antes? >> JENNIFER: Vamos a empezarcon el primero. >> DAVID J. MALAN: Muy bien. Comience con la primera. 4. Ahora, ¿dónde vas a ir, y por qué? >> JENNIFER: 4 es realmente pequeño. Así que si tienen suerte tal vez más pequeñoa mayor, lo que debería ser el doble que, y -. >> DAVID J. MALAN: OK. Vamos a ver, que te parece? >> JENNIFER: Pruebe la última. Niza. >> DAVID J. MALAN: Muy bien hecho. Está bien. >> [Aplausos] >> DAVID J. MALAN: OK. Así que en realidad estás haciendo estohorriblemente, porque eres haciendo muy bien. Lo que nos deja incapaces dehacer que algunos puntos. Así que vamos a tratar de hacer retroceder aquí. >> JENNIFER: OK. >> DAVID J. MALAN: Muy bienhecho, no obstante. Así que comenzó a principios,viste que era 4, entonces usted trasladado al final. Pero supongamos que usted no tenga suerteallí, y suponen el 50 estaba en otro lugar. Lo que su tercer paso ser? >> JENNIFER: Ir de nuevo al principio. >> DAVID J. MALAN: Volveral principio. Aceptar, por lo que le ha tocadoesta puerta, que tenía 8 años. Está bien. Así que no es 50. ¿Dónde te has mirado al lado? >> JENNIFER: Si no lo hicierasaben lo arreglaron. >> DAVID J. MALAN: Correcto. Bueno, si lo has hecho sabesfueron ordenados - >> JENNIFER: Oh, sabía, sí. >> DAVID J. MALAN: - Pero no lo hicistesaber donde 50 fue todavía? >> JENNIFER: Sigue adelante. >> DAVID J. MALAN: Muy bien. Aceptar. Sigue adelante. Bueno, que puedo trabajar. >> JENNIFER: OK. >> DAVID J. MALAN: Ahora, si eresva a seguir adelante, ¿cuál es su involutivo algoritmo retrocedió hasta. >> JENNIFER: El lineal -. >> DAVID J. MALAN: Es un poco lineal. Pero permítanme proponer, y muchome pongo en el lugar. Déjeme refrescarle la página. mismo número, la misma disposición,mismas puertas. Pero piense de nuevo a ese primer día encuando la clase rompimos una guía telefónica en medio, más o menos, y lo que eranuestra estrategia allí? >> JENNIFER: Comience en el centro. >> DAVID J. MALAN: OK. Así que empieza en el centro. Así que vamos a seguir adelante y simularlo. Comience en el centro derevelando esa puerta. Así que el número 16. Entonces, ¿cuál sería el tipo fuerte haber hecho,que arrancó el libro de teléfono a la mitad, para llegar a la siguiente conjetura? >> JENNIFER: Ir en este medio. >> DAVID J. MALAN: ¿Y por qué a la derecha? >> JENNIFER: Si fueran una especie de pequeñoa más grande, a continuación, 50 debe ser en ese extremo. >> DAVID J. MALAN: Good. Totalmente razonable. Así como un directorio telefónico, usted va a laderecha en oposición a la izquierda, pero aquí es la conclusión clave. Ahora puede tirar, o arrancar,medio de este problema, no dejándote con 7 puertas, pero en realidad con sólo 3. Lo cual es más o menos la mitad de latamaño del problema. Está bien. Así que ahora lo que tendríahecho después de que usted vaya a la derecha? >> JENNIFER: Entonces 16 es todavía muy pequeña,en relación con el 50, así que tal vez voy a intentar, similar, esta. >> DAVID J. MALAN: Muy bien. 42. Muy bien, así que ahora ¿cuál es suinstinto que le dice? >> JENNIFER: puedo tiraresto y luego simplemente - >> DAVID J. MALAN: OK. Bueno, usted puede tirarla mitad izquierda allí. >> JENNIFER: - elegir este. >> DAVID J. MALAN: Y de la derecha. >> JENNIFER: Si. >> DAVID J. MALAN: Así que, aunque es difícilpara ver tal vez, cuando sólo hay 7 puertas, pensar, ahora,la consistencia de la algoritmo que acaba de aplicar. En el caso anterior, lo hicisteque tenga suerte, que era genial. Pero usted ha utilizado un heurístico,Yo diría. Solías especie de sus instintos, ysaber lo resuelto, si es bastante pequeña al principio, obviamente, tenemostiene que ir más a la derecha. Pero, en cierto sentido, tienes suerte,porque tal vez este era el número 100, y tal vez 50 era más en el medio. Tal vez 50 fue aún más de aquí. >> Pero lo que hizo un poco diferenteesta vez fue, que hizo lo mismo una y otra vez. Y yo diría que lo que acabas dehizo, aunque influido por el teléfono ejemplo del libro, es algo muchomás algorítmica, y mucho menos especial funda. Mucho menos instintivo. Así que al final del día, ¿cómousted describe la eficiencia de la primer algoritmo, donde fuisteizquierda a derecha, frente a la segundo algoritmo aquí? >> JENNIFER: Éste debe, al igual que, tal vezreducir a la mitad el tiempo, o incluso más, sí. >> DAVID J. MALAN: OK, tal vez incluso más. Vamos a empujar un poco más duro en eso. Lo que realmente, si seguimos estalógica, definitivamente reducido a la mitad el tiempo de funcionamiento con este segundo algoritmopor tirar la mitad de la números, pero ¿qué hicimos en la siguienteiteración, cuando Jennifer reveló el segundo número? >> Hemos reducido a la mitad el número de puertas de nuevo. Y entonces, ¿qué hicimos después de eso, sihabía más puertas para jugar? Queremos reducir a la mitad, y de nuevo,y otra vez, y otra vez. Y esto era como ustedes todosde pie en la primera semana de clase, la mitad de ustedes sentado, mediode ustedes sentados, la mitad de ustedes sentarse, hasta que un solitarioalma estaba de pie. Y dijimos que el tiempo de ejecución deque, el número de pasos que tomó era en el orden de lo que? >> ALTAVOZ 1: [inaudible] >> DAVID J. MALAN: Entonces ingrese base 2 de n,o simplemente más simplemente, registro de n. Así que algo logarítmica. Y la gráfica no era una línea rectaque acaba de conseguir en peor, que era esta curva interesante que no lo hizoconseguir tan mal con el tiempo. Así que vamos a aferrarse a esta idea. Demos gracias a Jennifer. Muchas gracias por venir en adelante. Y, un segundo. No lámparas de escritorio de hoy, pero quesí tienen CS50 bolas de la tensión. >> JENNIFER: Yay. >> DAVID J. MALAN: Muy bien, aquí. Gracias por incurrir enel estrés aquí. Está bien. Así que veamos si no podemos ahoraformalizar este un poco más. Así que de nuevo, lo que hicimos fueesencialmente lo mismo que hicimos en que primera semana. Pero en lugar de terminar con sólo un linealalgoritmo, que hemos representado previamente como esta línea recta,por lo que, si ponemos una puerta más en la pantalla, a continuación, Jennifer haríahan tenido que buscar, potencialmente, detrás de una puerta más. Si ponemos dos puertas más, ella podría tenerpara mirar detrás de dos puertas más. >> Y así, había un linealrelación entre el tamaño de la problema en, por ejemplo, el eje x, yla cantidad de tiempo que se necesita para resolver en la y. Pero el cuadro que estaba aludiendo aantes era esta línea verde. Verde deliberadamente, porquese sentía mejor. En teoría, el algoritmo, cuando lo hicimoscon la guía telefónica, cuando lo hicimos con ustedes contando entre sí, yen el segundo caso, cuando Jennifer sólo lo hizo aquí, que era una especiede fundamentalmente mejor. Porque no era sólo el doble de rápido. No fue hasta cuatro veces más rápido. Era totalmente dependiente de lo que eltamaño de la entrada era, en cuanto a la cantidad de medidas que en última instancia llevó. >> Y así, esta sencilla idea de que todos nos tomópor sentado con el libro de teléfono, de manera similar puede ser aplicadoa algo como esto. Y esto podría ser más informalconocida como, como puede ser que imaginar, divide y vencerás. No muy diferente de lo que hicimos, por supuesto,con la guía telefónica. >> Pero el pseudocódigo, el recuerdo, era esto. Así que no vamos a hacer esto de nuevo, pero recuerdoesa primera semana, todos nosotros, se puso de pie y luego la mitad de ustedes se sentó, la mitad deque se sentó, la mitad de ustedes se sentó. Ese algoritmo se implementa en unpoco de una forma de engaño, en eso, No era sólo uno de mí contar,fundamentalmente, de manera más eficiente. En ese caso, fui el aprovechamientoun recurso secundario. Más o menos, varias CPU, múltiples cerebros,varias personas inteligentes en el habitación estaban ayudando a conseguir a partir de algolineal a algo logarítmica, de algorojo a algo verde. >> Pero en este caso, solo Jennifer puedemejorar fundamentalmente de la el rendimiento de su primer algoritmo por,una vez más, sólo de pensar un poco más difícil. Y ahora, cuando llega el momento de poner en prácticaestas cosas, averiguar qué líneas de código se puede escribir comoque puede repetir de nuevo, y otra vez, y otra vez, una especie deen una forma de bucle. Debido a que usted no va a tener lalujo, como Jennifer lo hizo en un primer momento, a sólo hay un montón de síes y decir:hmm, si este primer número es 4, déjame saltar todo el camino hasta el final. Ooh, si ese número es demasiado grande,déjame pasar arbitrariamente de nuevo para el segundo elemento. Usted encontrará que esto va a ser muchomás difícil de formalizar lo que los seres humanos dar por sentado como muy razonableheurística, pero un equipo es sólo vamos a hacer lo que usted le dice que haga. >> Ahora bien, esto tiene muy interesanteimplicaciones. Esta gráfica es una especie de la intención de una especie deabrumar visualmente, pero cuenta, donde es la línea recta en esta gráfica? ¿Dónde está la gráfica linealque llamamos n? Bueno, es una especie de hacia la parte inferiorde esta imagen, ¿verdad? Así que todo lo que hemos hecho es que hemos tipo dezoom es el eje x y el eje y para tratar de tener una idea de lo queotros tipos de curvas parecen. >> Y los detalles de la matemáticaexpresiones hoy no importa lo que mucho, pero observe que hay una gran cantidad dealgoritmos que son mucho peor que algo que es lineal. De hecho, n cubos se ve muy mal. 2 a la n se ve muy mal.n al cuadrado se ve muy mal. Y vamos a ver lo que algunos de lospodría ser en realidad hoy en día. Y log n no se siente tan mal, peromejor que n es log base 2 de n. Pero usted sabe, habría sido aúnmás sorprendente si Jennifer, o si, esa primera semana, había llegado conalgo que es registro de registro de n. >> En otras palabras, hay un conjuntogama de posibles soluciones a los problemas, pero incluso en este caso, el avisolo que va a suceder. Cuando hago zoom hacia fuera, ¿cuál de estas curvasva a llegar a ser la absoluta peor de los que está en la pantalla ahora? Entonces n cubos ve bastantemal por el momento. Pero si nos acercamos hacia fuera y ver más de laX y el eje Y, ¿quién va a dominar en última instancia? Así que en realidad resulta que 2 a lan, y se puede resolver esto con sólo enchufando algún cada vez más grandenúmeros y verás que 2 a la n, de hecho, se hace más grande mucho más rápido. Si realmente nos alejamos, a 2 a lan algoritmo es una mierda absoluta. Quiero decir que esto va a tomarun poco de tiempo para que el equipo para batir a través. >> Pero verás con el tiempo, sobre todocon los futuros boletines de problemas e incluso proyectos fin de carrera, es sus datosconjunto se hace grande, ¿de acuerdo? Incluso en la primera versión de Facebook,como el número de amigos, y la número de usuarios registrados consiguió grandes,se puede ordenar de la misma en el teléfono y implementar algo con búsqueda lineal,o una clasificación muy simple algoritmo, como veremos hoy. Tienes que empezar a pensar más difícily más difícil acerca de estos problemas. Y los tipos de problemas de lugares comoFacebook y Google, y Microsoft, y otros trabajan en es exactamente estosDatos especie de gran clase de preguntas cada vez más en estos días. >> Está bien. Así que el éxito de Jennifer en ese segundoalgoritmo, francamente, lo hizo increíblemente bien la primera vez, pero vamos aescribirlo como la suerte para que podamos puede aclarar este punto. En el segundo caso, se aprovechó de unalgoritmo que repite una y otra de nuevo, pero ella tomó un concedidacierta suposición de que permitiéramos , pero ella explotó cierto detalle elsegunda vez que ella no tenía la primera vez. ¿Qué fue qué? >> Que la lista se solucionó. Así que tan pronto como la lista se solucionó, queafirman que Jennifer era capaz de hacer fundamentalmente mejor. 7 puertas, sí, no es tan interesante,pero supongo que Estamos 7000000 puertas. Bitácora de n va definitivamentepara llevar a cabo mucho, mucho más más rápido en el largo plazo. Pero ella tenía que tener lapuertas ordenados por ella. Ahora, me tomé la libertad de hacer esopor adelantado en la pantalla del ordenador aquí, pero supongo que Jennifertenía que hacerlo ella misma? Supongamos que las puertas en cuestióndatos representados en una base de datos, o amigos registrados en Facebook, oninguna de las páginas web en Internet que varios sitios web podrían necesitaral índice o buscar de nuevo. >> Supongamos que usted acaba de tener un datos en brutoestablece y se dejó a usted, o para Jennifer hacer que la clasificación? Eso, más bien, requiere que respondamosla pregunta, bueno, ¿cuánto tiempo habría tomado Jennifer, o incluso yo,para ordenar esos números con anticipación para que podía tomar ventaja de eso? ¿Cierto? Debido a la implicación, desde luego, essi me lleva bastante tiempo para ordenar los números, ¿quién diablos le importa quepuede encontrar un número como 50, de manera rápida, como en el caso de Jennifer, si tenemos más deabrumado la cantidad de tiempo total tomó por ordenar las cosas por adelantado? >> Así que veamos si no podemos elpintar el cuadro aquí. Tengo un montón entero más estrésbolas, si eso ayuda romper el hielo aquí. Y si no te importa, nosnecesitará de siete voluntarios - sucesivamente, en Aceptar. Wow. Así que no tenemos que gastaren lámparas de escritorio, lo que parece. Está bien. Así que ¿qué hay de ustedes dos en el frente. ¿Qué hay de ustedes dos en la espalda. Así que eso es cuatro. ¿Y tú delantecinco, seis y siete. Ahí mismo. De tu amigo que lo llevan a cabo,para que pueda obtener el premio. >> Está bien. Vamos arriba. ¿Y por qué no tenemos quechicos vienen para acá. Yo te voy a dar a cada uno un número. Y seguir adelante y organizar a sí mismosidéntica a lo que es representado en la pantalla. >> [VOCES interponiendo] >> DAVID J. MALAN: Oop, lo siento. Bug. Está bien. Bueno, aquí vamos. El número cinco. El número seis. Uno, dos, tres, cuatro,cinco, de seis, siete. Oh, esto es incómodo. >> ALTAVOZ 2: Voy a buscar a -. >> DAVID J. MALAN: Good deal. Está bien. Gracias por participar. >> [Aplausos] >> Aceptar. Está bien. Así que tenemos cuatro, dos, seis,uno, tres, siete, cinco. Perfect así que tenemos siete voluntariosaquí, que son iguales en anchura a la matriz que estamos jugandocon el anterior. Y elegí siete por razonesque será igual conveniente en un poco. Y voy a proponer primero queclasificamos estos siete voluntarios. Si desea, en primer lugar,para saludar sin embargo. Dado que esto va a ser unincómodas varios minutos. Dar a conocer a ustedes mismos. >> GRACE: Hola, soy la Gracia. Soy un estudiante de segundo año en Leverett House. >> BRANSON: Hi. Estoy Branson. Soy un estudiante de primer año en la soldadura. >> GABE: Hi. Estoy Gabe. Soy un joven en Cabot. >> NEIL: Soy Neil. Soy un estudiante de primer año en Matthews. >> JASON: Soy Jason. Soy un estudiante de primer año en Greenough. >> MIKE: Soy Mike. Soy un estudiante de primer año en Grays. >> JESS: Soy Jess. Soy un estudiante de segundo año en Leverett. >> DAVID J. MALAN: Excelente. Está bien. Bueno, gracias a todos nuestrosvoluntarios aquí hasta ahora. Y el reto que nos ocupa ahora vasiendo para ordenar de estos chicos, pero luego vamos a tener que pensar un pocotendido sobre la eficiencia con que en realidad ellos ordenan. Así que primero vamos a probar esto. Ustedes pueden ver los números de los otroscon sólo colocar alrededor de las esquinas. Seguir adelante y tomar un par de segundos, yordenar los mismos desde el más pequeño en el izquierda a grande a la derecha. Vaya. >> Aceptar. Bueno. Eso fue realmente maldito rápido. Ahora alguien aquí, ¿cuál fue el algoritmoque estos tipos aplicados? >> ALTAVOZ 1: De menos a más. >> DAVID J. MALAN: OK. De menos a más grande es realmente una especie deobjetivo, pero no estoy seguro de que es realmente un algoritmo. De menos a más no diceme paso a paso lo que debe hacer. ¿Sí? >> ALTAVOZ 1: [inaudible] >> DAVID J. MALAN: OK. Así que si ves a una persona menor desu número, a continuación, pasar a la derecha de ellos. Así que ahora es cada vez más expresiva,más como un algoritmo, ya que puede decir, si esto, entonces eso. Así que tenemos algún tipo deconstructor condicional. Y estos chicos parecía hacer que unos pocosveces, porque algunos de ustedes se movieron un poco de una distancia. Así que hubo de suponer algún tipo debucle pasando en sus mentes. >> Pero vamos a tratar de formalizar eso. Si ustedes pudieran restablecer de nuevocon esta disposición. Vamos a ver si no podemos formalizar este unpoco, y luego hacer la pregunta, simplemente qué tan eficiente es esto? Por supuesto, cuando hacemos esto más lentamente,se va a sentir tan bien de un algoritmo, pero vamos a ver si podemosponer los dedos sobre los pasos precisos. >> Así que ustedes dos son cuatro y dos. O usted corrige o el orden incorrecto? Obviamente correctos. Así que intercambiamos. Ahora me voy a mover de ladoaquí y decir, cuatro a seis. ¿Está correcto o incorrecto? >> GABE: Correcto. >> DAVID J. MALAN: Correcto. Seis y uno? Nope. Swap. Así que eso es dos swaps. Seis y tres? Nope. Swap. Seis y siete? Se ve bien. Siete y cinco? >> JESS: [inaudible] >> DAVID J. MALAN: OK, intercambiar. Y ordenados. Está bien. Así que, obviamente, no, ¿verdad? Así que no había más que hacer. Pero, de hecho, estos chicos, inclusoinstintivamente. mantenerse en movimiento. No se limitaron a detener, una vez quecorregido un problema. Así. De hecho, voy a tenerpara hacer lo mismo. Voy a tener que rebobinar suerte de volveral principio de este problema, o el comienzo de esta serie degente, vamos a empezar llamarlos. >> Y ahora, ¿qué debería decir a mi algoritmoen el segundo pase ser? >> ALTAVOZ 1: Es lo mismo. >> DAVID J. MALAN: Es lo mismo. Y esto, me estoy empezando a gustar, ¿verdad? Tan pronto como usted puede encontrarse haciendola misma cosa una y otra vez, eso es cada vez más como un algoritmo,y menos instinto humano. >> Así que ahora, aquí vamos de nuevo. Dos y cuatro? No. Cuatro y uno? Ah, no había de hecho algunosEl trabajo todavía por hacer. A favor y tres? Bueno. Cuatro y seis? Seis y cinco? Seis y siete? Bien, ahora, hecho. Bueno, no. Tengo que volver. >> Así que ahora, una vez más, que estamos haciendo estoun poco más de forma deliberada. Y ahora, sólo hay un cerebrola ejecución de este algoritmo. Una CPU, si se quiere. Y, francamente, ese es el único recursovamos a tener acceso. ¿Y una vez que nos hace volver a un tecladoy tener algo como C en nuestra disposición, que sólo estamos escribiendo un programaque puede hacer una cosa a la vez. Considerando que, a estos chicos hace un momento, queaprovechado su capacidad intelectual colectiva como ustedes hicieron en la semana cero. Así que vamos a seguir haciendo esto. >> Dos y uno. Dos y tres. Tres y cuatro. Cuatro y cinco. Cinco y seis. Seis y siete. Hecho? Así que yo, pero me deja jugarabogado del diablo. ¿Tengo el tipo de ordenador que acaba dehizo un pase a través de esta serie de gente, saben que estoy hecho? >> ALTAVOZ 1: No. >> DAVID J. MALAN: ¿Entonces por qué? ¿Qué tendría que ver con el fin deconcluir de manera decisiva de que estoy hecho? Probablemente uno pase más. ¿Cierto? Porque todo lo que sé de ese anteriorpase es que he corregido un error. Y eso significa, tal vez hayaún otro error que tengo que corregir. Así que sólo puedo estar seguro de rebobinado ya continuación, comprobar, uno a dos, dos y tres, tres y cuatro, cuatro y cinco,cinco y seis, seis y siete. Bien, ahora que hice ningún trabajo. >> Ciertamente, puedo recordar que hice notrabajar con algo parecido a una variable, como un int. Llámelo swaps, swaps y si es 0, una vez quellegar hasta aquí, y empezó a 0, entonces Sólo quiero ser estúpido para seguir adelantede ida y vuelta, comprobando de nuevo, y otra vez, y otra vez, ¿verdad? Porque te quedas atascado en algúntipo de bucle infinito. Así que en cuanto hay 0 swaps,podemos afirmar que esta algoritmo es de hecho completa. >> Ahora, vamos a poner un nombre en esto. El algoritmo que propongo que acabamosimplementado es algo que se llama la burbuja tipo, conocido como tal en el sentido de quelos números que son más grandes tipo de burbuja de su camino a la cima, o hastaal final de la matriz de números. Pero qué tan eficiente fue este algoritmo? ¿Cuántos pasos qué tuve que físicamenteTomemos, por ejemplo, para ordenar estos siete seres humanos? >> Cuatro a cinco? Bien, también muchos es en última instancia,va a ser la respuesta. Pero incluso entonces, el número específicono es tan interesante. Vamos a generalizar como n. Así que si yo tuviera aquí n personas, y elloseran, más o menos, en un orden aleatorio en la comenzando, en ese orden original. Bueno, ¿cuántos pasos tenía yopara tomar en la primera pasada? Fue uno, dos, tres, cuatro, cinco,seis, y son siete personas, por lo eso es siete, seis -, así que eso es nmenos uno los pasos de la primera vez. >> Ahora, ¿cuántos pasos tenía yoa tomar cuando Rebobiné? Bueno, en realidad podríamos duplicar que sique realmente quería, pero por ahora, estoy sólo voy a decir, está bien,otro n menos 1. Así que el n menos 1 se va a ponermolestos para no perder de vista, así que vamos a Justo a la vuelta un poco. Así pasos 2n. Así que 14 pasos, más o menos. >> ¿Cuántas veces me tomoun paso la próxima vez? Bueno, es 3n. realmente. Y ahora, en el peor de los casos, porejemplo, ¿cuántas veces voy a tener ido hacia atrás y adelante, atrás y adelante,la ejecución de este algoritmo, el intercambio personas en cada paso, más o menos? De hecho, es n al cuadrado, ¿verdad? >> Debido a que en el peor de los casos, puede tipode pensar en esto de manera intuitiva, a pesar de que puede ser que tome un poco depoco de tiempo a asimilar En el peor de los casos, lo que haría estossiete personas han visto como, en términos del acuerdode sus números? Completamente al revés, ¿no? Y sólo para simular que,¿cuál era su nombre? >> MIKE: Mike. >> DAVID J. MALAN: Mike? Bien, Mike, ¿puedes venir conmigo sobreaquí sólo por un segundo? En realidad, no. Lo sentimos Mike, vamos a retroceder. ¿Cuál es tu nombre? >> NEIL: Neil. >> DAVID J. MALAN: Neil. Aceptar, Neil, vienes conmí, si no te importa. Así que voy a proponer, sólo porsimplicidad, que Neil se encuentra ahora en su peor de los casos posibles. Pero recuerdo cómo he implementadomi algoritmo. Estoy comparando, comparar, comparar,comparar, comparar, oh. Ahora estos chicos están fuerade orden, así que puedo corregir. Así que ustedes swap. Pero consideremos ahora, cuánto más lejosNeil no tiene por qué ir? Es más o menos n. Ya sabes, no es en realidad n. Es como, n menos 1, pero me estoy poniendohacer el seguimiento molesto de la pequeña número, así que vamos a llamarlo n. >> Así que si Neil da un paso al máximo cadatiempo, y para mover Neil un paso, Tengo que hacer este paso realmente tediosode ida y vuelta, esto es más o menos haciendo esto, n pasos, un total de n veces,porque me va a tomar que muchos pasos para llegar Neil todosel camino a donde pertenece. Por no hablar de todos los demás si ustedesfueron todos mis-ordenó también. >> Así que vamos a llamar a la ordenación de burbuja n al cuadrado. El tiempo de funcionamiento de este algoritmo, elel rendimiento de este algoritmo, la la eficiencia de este algoritmo,nos acaba de describir con mayor generalmente como n al cuadrado. Lo cual es bueno, porque yo podría hacer elmismo ejemplo con ocho personas, nueve personas, un millón de personas, y querespuesta no va a cambiar. >> Así que si ustedes no me importaría, vamos aque restablezca al punto de partida. Y vamos a tratar otros dos enfoques yver si no podemos hacerlo, fundamentalmente, mejor que esto. Así que esta vez, voy a proponerun tipo de algoritmo diferente. Eso fue muy inteligente de nosotros la última vez,y ustedes fueron derecho a que el instintos correctos de sólo un pocode intercambio de parejas. Pero si realmente quería abordar estesimplemente, y mi meta es mover todos los pequeños números de esta manera, yempujar todos los grandes números que cierto, ¿por qué no me hago en ella forma más ingenua posible y ver si puede hacer algo mejor que lo que era unalgoritmo bastante complejo? >> Así que vamos a ver. Cuatro es un número bastante pequeño, así que estoyvoy a dejar ahí momento. Ooh, el número dos es incluso mejor. Así que puede que acaba de dar un paso adelantepor un momento? Esta es actualmente mi pequeño numeradacandidato, y yo voy a recordar que con, como, una variable. Pero yo voy a seguir buscando. ¿Hay alguien cuyanúmero es menor? Seis, no. Oh, hay Neil de nuevo. >> Así que voy a empujar de vueltatipo de conceptualmente. Neil vendrá adelante. Y ahora, la variable que estoy usando pararealizar un seguimiento de quién tiene el más pequeño número se actualiza para contenerUbicación de Neil. Bueno, vamos a ver. Tres, siete, cinco. Ok, sé que Neil era el más pequeño. ¿Cuál es la cosa más simplepara que haga ahora? No voy a perder mi tiempo con sóloburbujeante Neil un lugar a la izquierda. ¿Por qué no acaba de poner Neil dondepertenece, que es, por supuesto, ¿dónde? >> Todo el camino desde el principio. Así que Neil, ven conmigo. ¿Y cuál era tu nombre? >> GRACE: Grace. >> DAVID J. MALAN: Grace. Aceptar. Así también la gracia, por desgracia, eresun poco en el camino. Entonces, ¿cómo podemos resolver este problema? ¿Cierto? Si se trata de una matriz, no haysólo siete ubicaciones. Recordemos que, con Rob, hablamos dedeclarando las edades, y que sólo tenía un número finito de edades? La misma idea aquí. Sólo tenemos un número finito de enteros. La gracia es un poco en nuestramanera, así que ¿cómo lo arreglamos? >> La forma más sencilla es como,Gracia, lo siento. Vas a tener que ir a través deallí, así que se puede dar cabida. Ahora, si se piensa en ello, tal vezque acaba de hacer el problema peor. Y tal vez lo hicimos, porque lo que siLa gracia estaba en el lugar correcto? Pero sabemos que no lo es, porquede lo contrario, habría sido pie hacia adelante en lugar deNeil en este momento, ¿no? Ya hemos comprobado su número fuera. >> Está bien. Así que ahora, Neil está en el lugar correcto, yYo puedo hacer una ligera optimización. Para el próximo minuto, voy a ignorarNeil todos juntos, a fin de no perder el tiempo, o accidentalmenteél cambiar al lugar equivocado. Así que ahora, ¿cómo puedo encontrar la siguienteelemento que es más pequeño? Dos. Eso es un número bastante bueno, siquiere dar un paso adelante y Yo te recuerdo. Seis, no es bueno. Cuatro, tres, siete, cinco, no es bueno. Así que voy a mover asu lugar correcto. Y tuvimos suerte esta vez. >> Ahora, yo voy a hacer caso omiso de estosdos chicos, y ahora lo hacen una más pasar a través de esto. Six, que un número muy pequeño. Vamos hacia adelante. Oh, lo siento. Número de Grace es mejor,por lo que paso en adelante. Cuatro. Lo sentimos, Grace. Volver de nuevo. El número tres es mejor. Siete. Cinco. Y ahora ¿cuál es tu nombre? >> JASON: Jason. >> DAVID J. MALAN: Jason. Así que Jason es ahora el más pequeñoelemento que he seleccionado. ¿A dónde va a ir? Entonces, ¿dónde seis es. Y su nombre es nuevo? >> GABE: Gabe. >> DAVID J. MALAN: Gabe. Gabe está en el camino. ¿Cuál es la cosa más fácil de hacer? Cambie estos dos chicos y continuar. Así que ahora vamos a ver. ¿Quién es el más pequeño? Cuatro. Déjame sólo un poco de trampa. Cinco va a ser el más pequeño. Me parece próximo, si usted quiere dar un pasohacia adelante, ¿qué tengo que ver con estos chicos, con Gabe? Cambie de nuevo. Así que ahora, todavía un poco fuera de lugar. Encontré Gabe para ser el más pequeño, por lo queLe Pop Out, muevo ustedes otra vez. Y hecho. >> Así que la respuesta es la misma. El resultado final es el mismo. ¿Cuál de estos dos algoritmoses mejor? El segundo, oí. ¿Por qué? >> ALTAVOZ 3: Es n pasos [inaudible]. >> DAVID J. MALAN: Es n pasos como máximo. Interesante. Así es que, aunque? Entonces, ¿cómo puedo encontrar elmás pequeño elemento? ¿Cuántos pasos tuve que tomarel encontrar el elemento más pequeño? Tenía una mirada todo el caminoal final, ¿no? Porque en ese caso peor, ¿quési Neil estaban aquí? Así que encontrar el elemento más pequeñome n pasos tomas, o n menos 1. Pero, en Aceptar. Así fijar Neil. Recuerde que, un minuto o así que hace. >> Pero, ¿qué encontré la siguientemás pequeño elemento? Es n menos 1, o n menos 2 realmente,a partir del número de pasos. Así que bien. Así que lo hice n menos 2. Está bien. Así que se siente un poco mejor. Está bien. ¿Cuántos pasos la próxima vezpara encontrar el número tres? Entonces n menos 4. Así que es decreciente, uno menospaso en cada iteración. Así que esto se siente mejor, ¿verdad? Si la última vez fue más o menos n veces n,esta vez se trata de n menos 1, más n menos 2, más n menos 3, más nmenos 4, punto, punto, punto. Pero si usted recuerda de su escuela secundarialibros de texto, el pequeño truco hoja en la parte trasera que tiene las fórmulas, sirealizar la suma de esta serie de números, lo que es el número total de pasosvaya a ser que me tomo aquí? >> Este es uno de los que, como, n menos1, los tiempos de n, dividido por 2. Así que déjame ver si puedo sacaresto por un momento. Y de nuevo, estoy un poco redondeo algunasnúmeros sólo para mantener nuestra vida sencilla, pero por lo que recuerdo, es algo así como siHago n menos 1 cosas, entonces n menos 2, entonces n menos 3, que es más o menosalgo así más de 2, y si multiplique esto, eso esen realidad n cuadrada. Eso no está sintiendo muy bien.n menos n sobre 2. >> Pero aquí está la cosa. En ciencias de la computación, cuando los problemasempezar a ponerse interesante es cuando n se pone muy grande. Y cuando n se hace muy grande, lo que deestos valores se van a dominar toda de los demás? Es una especie de la n al cuadrado, ¿verdad? Sí, dividiendo por 2 es bastante bueno. Pero si usted está hablando de miles de millonesde piezas de datos, o miles de millones de piezas de datos, OK, por lo queusted es el doble de rápido. Pero a quién le importa si ese número grande,si este factor es lo que obtiene más y más grande. Y sin duda, tiene más deuna diferencia de este tipo. Así que a pesar de que ustedes están bien, elsegundo algoritmo, lo vamos a llamar ordenación por selección, es decir, en el mundo real, unapoco más rápido en potencia, porque soy teniendo cada vez menospasos cada vez. >> En realidad no es fundamentalmente más rápido. Porque si en realidad nos jugamos esto paragrandes valores de n, al final de el día, por lo suficientemente grande n, sigue siendova a sentir bastante lento. Bueno, déjame tomar unaúltimo pase a eso. Eso es lo que yo llamaríaordenación por selección. Pueden ustedes restablecer mismospor última vez? Y en este último caso, voyproponer algo llamada ordenación por inserción. Ser la ordenación por inserción, conceptualmente,un poco diferente. >> En lugar de ir y venir yseleccionar el elemento más pequeño, estoy sólo va a tratar con cada uno de estoschicos como yo las encuentre, e inserte ellos en su lugar correcto. Así que sólo voy a empezar con la Gracia,y veo que ella es la número cuatro. ¿Dónde número cuatro pertenecen? Todavía no he empezado la clasificación nada,Así que la gracia llega a quedarse ahí. Y ahora voy a reclamar, si pudieradar un paso a la derecha, esta mi lista ordenada, este es milista restante sin clasificar. Así que ahora voy a proceder a continuación,y ¿cuál es tu nombre? >> BRANSON: Branson. >> DAVID J. MALAN: Branson. Así Branson es el número dos. Así que voy a tener quefuera por un momento. Y ahora, ¿dónde pertenecesen esta serie? Así que a la derecha de la Gracia. Así que de nuevo, estamos como hacerLa gracia hacer un montón de trabajo aquí. ¿Dónde ponemos usted? Así que te vamos a deslizar a laa la izquierda, e introduzca Branson allí. Pero ahora afirmo queustedes llevan a cabo. Pero aviso, no estoy usando el espacio extra. Sigue siendo 2 elementosaquí, 5 aquí. Tamaño total de la matriz es de 7, así que estoyno copiar, no está bien? >> Así que ahora tenemos, con Gabe aquí, elnúmero seis, ¿de dónde sois? Tuviste suerte de nuevo. Así que usted puede permanecer allí. Basta con echar un ligero paso hacia la derechasólo para dejar en claro que está ordenada. Y ahora tenemos a Neil de nuevo, el número deuno, ¿a dónde vas? Y ahora es cuando vamos a empezar a ver queeste algoritmo, aunque en primera vista, se siente muy inteligente, relojlo que va a suceder. Si pudiera dar un paso adelante. >> ¿Dónde queremos poner Neil? Así que, obviamente, aquí, así que ¿cómoCómo conseguimos Neil allí? Vamos a hacer esto paso a paso. Gabe, ¿dónde tiene que ir? Sí, así que tome un gran paso,o dos medias medidas para hacer un paso más allá. Gracia, donde vas? Bueno. Así que otro paso. Y, por último, Branson? Otro paso. Y ahora podemos poner Neil en su lugar. >> Así que ahora, seguir esta lógica. A pesar de que no estamos cambiando Neilotra, y otra, y otra vez, para ponerlo a dónde va, en el peor de los casos, lasiguiente número, podríamos encontrarnos podría ser el número, por ejemplo, hubo un númerocero, entonces vamos a cambiar todo estos chicos. Supongamos que hay un número negativouno, entonces tenemos que cambiar todos estos chicos. Así que estamos realmente sólo un poco de mover de un tirónel problema nada más, de modo que estamos la transferencia de la costa de laproceso de selección por lo que la inserción proceso, de tal manera que ustedes acababan depara mover más o menos n menos algo número de pasos. Y ese número de pasos sólo se vaaumentando a medida que selecciono más números, si tengo que seguir empujando a ustedesespalda, y la espalda, y la espalda. >> Así lo triste ahora es todo estoalgoritmos se n al cuadrado. Vamos a seguir adelante y gracias a estoschicos y visualizar estas un poco de manera diferente. Muy bien hecho. >> [Aplausos] >> Está bien. Ahí lo tienes. Gracias por - >> BRANSON: [inaudible] mantener los números. >> DAVID J. MALAN: No, usted puedemantener los números también. Está bien. Muy bien hecho. Está bien. Así que vamos a ver si ahora no podemos resumirmás rápidamente, y más visualmente, exactamente lo que acaba de sucederaquí como sigue. Voy a seguir adelantey tire hacia arriba Firefox. Nos vincularemos esta manifestaciónen la página web del curso. Java es un poco molesto para conseguir trabajoen algunos navegadores en estos días. Así que si no juegas con esto en casa,da cuenta de que podría tener que usar Firefox para que funcione. ¿Y qué voy a hacer con estademostración es la siguiente. >> En la parte inferior, tengo un montón deopciones del menú, incluyendo un inicio y un botón de parar. También, en un aparte, parece que hay unabug en estos programas, mediante el cual se no puede ver realmente el inicio o detenerbotón a menos que mantenga Comando o Alt plus y acercar la imagen, que curiosamentete muestra más botones. Así que lo digo si juegascon esto en casa. Ahora voy hacer clic en Inicio en tan sóloActualmente, después de especificar un retraso de, como 200 milisegundos aquí, sólopara que podamos ver lo que pasa. >> Así que yo sostengo que esta es una visualizaciónde la primera algoritmo estos chicos lo hicieron, especie de burbuja, en el queintercambiamos personas por pares. La idea clave de esta visualizaciónes que la altura de las barras representa el tamaño del número. Así que la más alta es la barra,mayor sea el número. Shorter la barra, más pequeño es el número. Y si te das cuenta, que estamos pasandola primera iteración de este algoritmo, intercambio de números grandes y pequeños, de manera queel número pequeño viene primero y el gran número va a la derecha. >> Y tan pronto como llegamos al final de la matrizde muchos más números de siete, estamos va a ir de nuevo al principio. Y anticipar esto. En el extremo izquierdo, ese pequeño tipo vapara intercambiar a un lado, y este proceso se repite. Ahora esta visualización se pone rápidamenteaburrido, por lo que me dejó ir adelante y dejar de ella, cambie la demora algo muchomás rápido sólo para ahora, una idea de este algoritmo. >> Así que, aunque he aceleró hacia arriba, esto escomo actualizar mi procesador, la compra de un equipo nuevo. No he cambiado fundamentalmente mialgoritmo, pero de hecho, puede ver más claramente que con los seres humanos, que el grannúmeros están burbujeando hasta la cima, y el pequeño número están burbujeandohasta la parte inferior. ¿Y ahora esta cosa aquí ordenada. Y en un aparte, en las plazas, no haysólo algunas de contabilidad allí para le ayudan a contar la cantidad de comparaciones,o cuántos swaps tener En realidad se ha hecho. >> Bueno, vamos a probar una delos otros que vimos. Permítanme clic en especie de burbuja aquí, ypermitirme elegir, y esta página web entera es un poco buggy. Aceptemos el riesgoy ejecutarlo de nuevo. Eso es. Así que vamos a hacer la selección de clasificación. No sé por qué el menúaparece por allí. Vamos a acercar a arreglar esobug, cambiarlo a 50. Ah, vamos a hacer realidadque mucho más rápido. Cinco milisegundos o menos, y en Inicio. >> Así que esta es la selección de clasificación. Así que de nuevo, pensar en lo quelo hizo con los humanos hasta aquí. Fuimos a través de la matriz y seleccionamosel elemento más pequeño de nuevo, y otra vez, y otra vez. Ahora afirmo que todavía era bastante malo. Seguía siendo n al cuadrado, más o menos,pero fue, en el mundo real, un poco más rápido, porque yo estaba de hecho tomandoligeramente menos pasos cada vez. Pero nosotros sólo estamos hablando, ¿qué? Tal vez 40 o más barras de aquí? No estamos hablando de 40 millones. Así que no es totalmente claro para mí queera de hecho una ganancia significativa. >> Permítanme ahora volver atrás y cambiar a nuestrotercer algoritmo, que era seleccione ordenación por inserción. Y ahora está realmente buggy porque elmenú realmente no debería estar allí. Así que ahora vamos a retroceder hasta aquíy empezar este algoritmo. Whoop, iniciar y detener. Así que éste tipo de tiene un patrón bastantea la misma, con lo cual estamos de nuevo la inserción de los seres humanos, o eneste caso, las barras en su ubicación adecuada. Y es que ya ha hecho antesMe di la vuelta. Pero éste, también, en teoría,todavía está n al cuadrado. >> Así que veamos si no podemos resumiréstos como sigue. Voy a seguir adelante y sólo para darnosotros una especie de una manera común de hablar acerca de estas cosas, permítanme presentarlessólo un poco de notación aquí. Estás a punto de ver algo que se llama granO, ya que es, literalmente, una gran O. Y esta es una manera de que un ordenadorcientífico o un matemático usos incluso para describir el tiempo de ejecuciónde algún algoritmo. ¿Cuántos pasos que realmente necesita? >> Ahora me voy a avergonzar a mí mismo conmi letra aquí en un momento. Pero déjame seguir adelante y decir queesto va a ser grande O por aquí. Y permítanme presentarles a otrosímbolo, un omega mayúscula. Omega va a ser todo lo contrario,en esencia, de la gran O. Considerando que la gran O significa, en el peor de los casos, la cantidad de tiempopodría tomar algún algoritmo, en términos de n, omega va aserá la cantidad de tiempo que podría tomar en el mejor de los casos. Y veremos lo que entendemos pormejor de los casos, en un momento. >> Así que vamos a empezar algo simple. Permítanme comenzar con una búsqueda lineal. Así no clasificación. Llamaremos a esta búsqueda lineal. Y ahora, hacer un poco demesa de salir de esto. Y ahora, en el caso de búsqueda lineal,en el peor de los casos, la cantidad de pasos es que me va a llevar a encontrar unanúmero de elección arbitraria? Y hay n puertas totaleso n números totales. Peor de los casos. ¿Cuántos pasos voy a tener quetomar para encontrar el número 50 en una serie de n puertas? ¿Y por qué? Debido a que puede ser todo elmuy por encima en el extremo. Así que al igual que Jennifer se encontró con elnúmero 50 fue todo el camino, por lo que en el peor de los casos búsqueda lineales gran O de n, vamos a decir. >> ¿Y el mejor de los casos,si usted consigue realmente afortunado? Sólo va a dar un paso,o un número constante de pasos. Así que vamos a describir eso como 1. Así que esto es bastante bueno. Ahora lo que si hemos hecho algocomo búsqueda binaria? Así que la búsqueda binaria, en el peor de los casoscaso, se llevó la cantidad de tiempo? >> [VOCES interponiendo] >> DAVID J. MALAN: Así que en realidad,escuchado en un par de lugares. Así que en realidad es log n, más o menos,porque como se divide la lista en media otra vez, y otra vez, y otra vez, somos capaces deencontrar, en última instancia, el valor, si está allí, pero hay una trampa. ¿Cuál es la suposición de que tenemos quedar por sentado de búsqueda binaria? Tiene que ser resuelto. No es ordenada, se puede dividir la cosala mitad otra vez y otra vez, y usted puede ir a la izquierda, y se puede ir a la derecha, yusted puede ir a la izquierda y la derecha, pero usted es No va a encontrar el elemento sila lista no está ordenada, porque puede que te pierdas. Debido a que su heurística, para ir a la izquierdao hacia la derecha va a ser defectuoso si es de hecho, no ordenados. Así que hay una especie de costo ocultopara el uso de algo como esto. >> Ahora, vamos a entrar en nuestra clasificaciónalgoritmos no busca - oh, realmente vamos a ir en este espacio en blanco. La búsqueda binaria en el mejor de los casos? También es 1 si sólo pasa a seren pleno centro de la matriz, o el medio de la guía telefónica. Ahora vamos a hacer una especie de burbuja. Así que de nuevo, ahora que estamos entrando en eltipo, no las búsquedas. >> En el peor de los casos, el número de pasos que hicieronburbuja reclamo especie va a tomar? n al cuadrado. Así que voy a dibujar eso. Ooh, mi letra se ve aún peorcuando se proyecta tan grande. Está bien. Así que eso es n al cuadrado. ¿Y en el mejor de los casos de ordenación de burbuja,cuántos pasos se va a tomar? 1, lo escuché. >> ALTAVOZ 1: n. >> DAVID J. MALAN: n, he oído. >> ALTAVOZ 1: 2. >> DAVID J. MALAN: 2, escuché. ¿Escucho 3? Está bien. Eso he oído 1, n, 2, pero vamos a elegirAdemás, al menos el primero de los sugerencias, 1. No es una mala instinto, porqueclase de la siguiente manera un patrón aquí. Pero si sólo se necesita 1 paso, como en elmundo podría yo afirmar que la lista está ordenada, porque si sólo se me permitetomar 1 paso, ¿cuántos elementos pude comprobar realmente estar seguro? Bueno, sólo 1, que significa que hay nmenos 1 elementos que podrían estar fuera de orden, y yo sólo voy a la fe después demirando a 1 elemento que el cosa está ordenada. Así 1 de no corrige aquí. Así mínimamente, ¿cuántosQué tengo que mirar? >> [VOCES interponiendo] >> DAVID J. MALAN: n menos 1, o en realidad,n, porque tengo que mirar cada elemento para asegurarse de queno es fuera de servicio. Pero una vez más, vamos a clase de agitamos nuestramanos en los números más pequeños y asumen que, a medida que n se hace grande, sonpoco interesante de todos modos. Así que es una especie de burbuja. Y ahora, vamos a hacer estos dos últimos. Selección de tipo, y luego vamos ahacer la ordenación por inserción. Y luego vamos a volar tumentes con algo mucho mejor que todos ellos. Está bien. >> ¿Cuál es el peor de los casos se ejecutamomento de la selección especie? >> SPEAKER 4: n al cuadrado. >> DAVID J. MALAN: n cuadrado, lo que estoy oyendo. Pero ¿por qué n al cuadrado, intuitivamente? >> ALTAVOZ 4: Debido a que sólo lo hicimos. >> DAVID J. MALAN: Debido a que acabamos de hacer eso. Aceptar. Buena respuesta. Pero intuitivamente, ¿por qué es la seleccióntipo n al cuadrado? ¿Qué teníamos que haceruna y otra vez? Tuvimos que mantener la exploración a través, sonque los más pequeños, ¿es usted el más pequeño, ¿eres tú el más pequeño. Y sentado, hemos sido capaces de tomar npasos, entonces n menos 1, entonces n menos 2. Pero si que tipo de agrega los todo,o llevatelo contigo en la fe de que he añadido ellos de antemano, obtenemos aproximadamente ncuadrado menos algunos números más pequeños. Así que voy a llamar a este n al cuadrado. Pero con ordenación por selección de la mejorcaso, la cantidad de pasos es me va a llevar? >> ALTAVOZ 5: [inaudible] >> DAVID J. MALAN: Es lamentablementesiendo n al cuadrado, ¿verdad? Porque si estoy seleccionando los más pequeñoselemento, y que teníamos siete personas aquí, Lo único que sé, una vez que llegue a la mismafin, que he encontrado el más pequeño número, donde sea que él oella pudo haber sido. Pero ¿cómo puedo encontrar la siguientemenor número? Tengo que hacer otra pasada. Así que en el mejor de los casos, lo que es loentrada a la selección de tipo? Se trata de una especie ya lista, el número uno,número dos, número tres, número cuatro. Pero yo soy un ordenador. Sólo puedo mirar unocosa a la vez. No puedo especie de dar un pasode nuevo como un ser humano y decir: ooh, esto parece correcto. >> Sólo puedo juzgar la corrección enordenación por selección mediante la selección de la número más pequeño. Pero incluso si encuentro el número uno en primer lugar,si yo no sé nada más sobre los demás números, que no lo hago, todo lo queSé que me han dado una serie o un conjunto de puertas detrás de las cuales sonnúmeros, la única manera que sé que uno era la más pequeña? Si consigo todo el camino hasta aquí y me doy cuenta,maldita sea, uno era de hecho el más pequeño. >> Pero ¿cómo puedo entonces determino quedos es la siguiente más pequeña? Al hacer la misma ineficienciauna y otra vez. Así que finalmente, con la ordenación por inserción,cómo, en el peor de los casos, dijimos que realiza? Es demasiado n al cuadrado. ¿Y qué hay con el mejor de los casos? Dejaremos que a medida que un cliffhanger. Vamos a llenar ese espacio en blanco la próxima vez,pero primero déjame propongo que fundamentalmente hacer mejor quetodo esto, ¿de acuerdo? >> Así que piense por sí mismo lo inserciónespecie que va a ser. Bueno, eso no fue muy dramática,porque yo soy el único que vio el cambio. Wow. Aceptar. Así que aquí tenemos un pocodiferente manifestación. Si hago zoom aquí, verás que enla izquierda tenemos una especie de burbuja, en el centro tenemos ordenación por selección, y enla extrema derecha, que tienen algo que no han mirado todavíallamado merge sort. Pero consideremos lo que hemos sidohaciendo aquí hasta el momento actual. Cuando Jennifer llegó por primera vez en el escenario,nos fuimos a través de la matriz de números otra vez, y otra vez, con búsqueda lineal,y tenemos tiempo de funcionamiento lineal, gran O de n, por así decirlo. >> Cuando consideramos ahora la primera semana declase, cuando habíamos dividir y conquistar, y tuvimos el lagrimeo guía telefónica,y Jennifer, y colectivamente apalancada que idea clave, que debíarepetirte una y otra vez por de alguna manera tirar, tirar,tirar, medio del problema, o en general, la división de un problema en un medio,y luego el tratamiento de la pieza más pequeña de el problema como conceptualmente equivalentea la otra, de alguna manera hicimos fundamentalmente mejor. Pero con la ordenación de burbuja, con la selecciónespecie, con la ordenación por inserción, hemos podrá hay tales ideas que Jennifer hizo. Nos prácticamente sólo caminamos de regreso ysucesivamente un montón de veces, y nos ajustado un poco las cosas, el intercambio deen este orden, tal vez la inserción o la selección. Pero al final del día, hice un montóntorpe caminar de ida y vuelta. Nosotros realmente no aprovechamos algointeligente como Jennifer le gustaba dividiendo y conquistando. >> Así fusionar especie, por el contrario, que nosno verá hasta la próxima semana, que va para aprovechar esa idea clave dividiendola entrada y, a continuación, reducir a la mitad, y luego reducir a la mitad, y luego reducir a la mitad. Y en cada iteración del bucle que,la clasificación de la mitad izquierda y la derecha medio, entonces la mitad izquierda de la mitad izquierda,y la mitad derecha de la izquierda, a continuación, la mitad izquierda de la mitad derecha, yla mitad derecha de la mitad derecha. Y repitiendo una y otra vez. >> Así verás esto visualmente, pero estaes lo que nos espera la próxima semana. Y, en general, cuando pensamos un pocopoco más difícil en cualquier problema. N Hemos cuadrado en el lado izquierdo, Ncuadrado en el medio, y n log n a la derecha. Así que ahí está tu melodrama real. Nos vemos el lunes. >> [Aplausos]

Noticias relacionadas