>> [REPRODUCCIÓN DE MÚSICA]
>> DAVID J. MALAN: Muy bien.
Así que bienvenidos de nuevo.
Esto es CS50, y el IS Al 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 buscando y los errores que
no puedo perseguir.
Porque, puede estar seguro, que en tan sólo un tiempo 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 llegado en un corto período de tiempo.
Así que si te sirve de consuelo, colgar en él por ahora.
>> Hoy, sin embargo, empezamos a transición a las cosas de alto nivel.
Y empezamos a dar por sentado que ustedes saben cómo programar, o por lo
menos los inicios de ese nivel de comodidad.
Y vamos a empezar a considerar cómo podemos ir sobre el diseño de programas más
efectivamente.
¿Cómo podemos ir sobre la optimización de la eficiencia de los algoritmos, y
la solución generalmente más problemas 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 teclado para cualquier tipo de código.
Será nivel mucho más alto, y en última instancia, sobre la resolución de problemas.
>> Así que para llegar a ese punto, permítanme proponer que los siguientes siete
rectángulos representan siete puertas, detrás de que son un montón de
números, entre los cuales es el número 50.
Permítanme proyecto esta en esta Aquí la pantalla también.
Y proponemos que necesitamos un voluntario que ayudarme 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 que Me 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ás cualquiera de estas puertas con un simple toque
en una de las puertas, y se revelará su número.
Y vamos a ver lo rápido que nos 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 para encontrar el número, 50?
>> JENNIFER: Um, pensé que tal vez si -
[Inaudible]
>> DAVID J. MALAN: Oh.
Déle un segundo.
Así fue su estrategia para encontrar el número, 50?
>> JENNIFER: Así que acabo de empezar en el empezando a ver lo que el primer número
estaba, y entonces pensé, tal vez si que están ordenados, que voy a seguir
tocando más arriba?
>> DAVID J. MALAN: OK.
Y parece que hemos encontrado que ese sea el caso.
Aunque, vamos a pelar las capas sólo un poco, y quieres ir
adelante y revelar las otras puertas que 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 interesante visión, ¿no?
Si usted asumió, y lo hizo llegar, de hecho, un poco de suerte allí.
Pero si se supone que las cifras eran ordenados, ¿puedes ser más precisos
cuanto a la forma en que influyó su comportamiento?
>> JENNIFER: Así que si ellos fueron ordenados, me pensé que tal vez menor a mayor.
>> DAVID J. MALAN: OK.
>> JENNIFER: O si esto terminó siendo muy grande, entonces mayor a menor.
>> DAVID J. MALAN: OK.
Así mayor a menor, o menor a mayor.
Pero permítanme proponer, suponga que tiene conseguido de mala suerte, y supongamos que
no eran, de hecho, ordenados, ¿cuántos de esas 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ás en general, dicen que hay n puertas en el
Aquí la pantalla.
Así que en el peor de los casos, usted tendría que para mirar detrás de 7 puertas, o puertas n.
Y por lo que este es en realidad, es un poco de suerte hoy, pero en realidad es una relación lineal
algoritmo de clases, a pesar de que eran una especie de saltar alrededor.
¿Es eso justo?
>> JENNIFER: Si.
>> DAVID J. MALAN: Bueno, déjame ver si su estrategia cambia si nos mueven a
nuestro segundo ejemplo aquí con 7 puertas diferentes.
Los mismos números, pero esto momento 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 empezar con 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ño a 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 esto horriblemente, porque eres
haciendo muy bien.
Lo que nos deja incapaces de hacer que algunos puntos.
Así que vamos a tratar de hacer retroceder aquí.
>> JENNIFER: OK.
>> DAVID J. MALAN: Muy bien hecho, no obstante.
Así que comenzó a principios, viste que era 4, entonces usted
trasladado al final.
Pero supongamos que usted no tenga suerte allí, y suponen el 50
estaba en otro lugar.
Lo que su tercer paso ser?
>> JENNIFER: Ir de nuevo al principio.
>> DAVID J. MALAN: Volver al principio.
Aceptar, por lo que le ha tocado esta 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 hiciera saben lo arreglaron.
>> DAVID J. MALAN: Correcto.
Bueno, si lo has hecho sabes fueron ordenados -
>> JENNIFER: Oh, sabía, sí.
>> DAVID J. MALAN: - Pero no lo hiciste saber 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 eres va 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 mucho me 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 en cuando la clase rompimos una guía telefónica en
medio, más o menos, y lo que era nuestra 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 de revelando 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ño a 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 la derecha 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 la tamaño del problema.
Está bien.
Así que ahora lo que tendría hecho 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 su instinto que le dice?
>> JENNIFER: puedo tirar esto y luego simplemente -
>> DAVID J. MALAN: OK.
Bueno, usted puede tirar la mitad izquierda allí.
>> JENNIFER: - elegir este.
>> DAVID J. MALAN: Y de la derecha.
>> JENNIFER: Si.
>> DAVID J. MALAN: Así que, aunque es difícil para 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 hiciste que tenga suerte, que era genial.
Pero usted ha utilizado un heurístico, Yo diría.
Solías especie de sus instintos, y saber lo resuelto, si es bastante
pequeña al principio, obviamente, tenemos tiene 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 diferente esta vez fue, que hizo lo mismo
una y otra vez.
Y yo diría que lo que acabas de hizo, aunque influido por el teléfono
ejemplo del libro, es algo mucho más algorítmica, y mucho
menos especial funda.
Mucho menos instintivo.
Así que al final del día, ¿cómo usted describe la eficiencia de la
primer algoritmo, donde fuiste izquierda a derecha, frente a la
segundo algoritmo aquí?
>> JENNIFER: Éste debe, al igual que, tal vez reducir 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 esta lógica, definitivamente reducido a la mitad el
tiempo de funcionamiento con este segundo algoritmo por tirar la mitad de la
números, pero ¿qué hicimos en la siguiente iteració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, si habí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 todos de pie en la primera semana de
clase, la mitad de ustedes sentado, medio de ustedes sentados, la mitad de ustedes
sentarse, hasta que un solitario alma estaba de pie.
Y dijimos que el tiempo de ejecución de que, 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 recta que acaba de conseguir en peor, que era
esta curva interesante que no lo hizo conseguir 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 que sí tienen CS50 bolas de la tensión.
>> JENNIFER: Yay.
>> DAVID J. MALAN: Muy bien, aquí.
Gracias por incurrir en el estrés aquí.
Está bien.
Así que veamos si no podemos ahora formalizar este un poco más.
Así que de nuevo, lo que hicimos fue esencialmente lo mismo que hicimos
en que primera semana.
Pero en lugar de terminar con sólo un lineal algoritmo, 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ía han tenido que buscar, potencialmente,
detrás de una puerta más.
Si ponemos dos puertas más, ella podría tener para mirar detrás de dos puertas más.
>> Y así, había un lineal relación entre el tamaño de la
problema en, por ejemplo, el eje x, y la cantidad de tiempo que se necesita para
resolver en la y.
Pero el cuadro que estaba aludiendo a antes era esta línea verde.
Verde deliberadamente, porque se sentía mejor.
En teoría, el algoritmo, cuando lo hicimos con la guía telefónica, cuando lo hicimos
con ustedes contando entre sí, y en el segundo caso, cuando Jennifer sólo
lo hizo aquí, que era una especie de 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 el tamañ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 aplicado a algo como esto.
Y esto podría ser más informal conocida 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 recuerdo esa primera semana, todos nosotros, se puso de pie
y luego la mitad de ustedes se sentó, la mitad de que se sentó, la mitad de ustedes se sentó.
Ese algoritmo se implementa en un poco 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 aprovechamiento un 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 algo lineal a algo
logarítmica, de algo rojo a algo verde.
>> Pero en este caso, solo Jennifer puede mejorar 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áctica estas cosas, averiguar
qué líneas de código se puede escribir como que puede repetir de nuevo, y
otra vez, y otra vez, una especie de en una forma de bucle.
Debido a que usted no va a tener la lujo, 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 mucho más difícil de formalizar lo que los seres humanos
dar por sentado como muy razonable heurística, pero un equipo es sólo
vamos a hacer lo que usted le dice que haga.
>> Ahora bien, esto tiene muy interesante implicaciones.
Esta gráfica es una especie de la intención de una especie de abrumar visualmente, pero cuenta, donde
es la línea recta en esta gráfica?
¿Dónde está la gráfica lineal que llamamos n?
Bueno, es una especie de hacia la parte inferior de esta imagen, ¿verdad?
Así que todo lo que hemos hecho es que hemos tipo de zoom es el eje x y el
eje y para tratar de tener una idea de lo que otros tipos de curvas parecen.
>> Y los detalles de la matemática expresiones hoy no importa lo que
mucho, pero observe que hay una gran cantidad de algoritmos 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 los podría ser en realidad hoy en día.
Y log n no se siente tan mal, pero mejor que n es log base 2 de n.
Pero usted sabe, habría sido aún más sorprendente si Jennifer, o si,
esa primera semana, había llegado con algo que es registro de registro de n.
>> En otras palabras, hay un conjunto gama de posibles soluciones a los
problemas, pero incluso en este caso, el aviso lo que va a suceder.
Cuando hago zoom hacia fuera, ¿cuál de estas curvas va a llegar a ser la absoluta
peor de los que está en la pantalla ahora?
Entonces n cubos ve bastante mal por el momento.
Pero si nos acercamos hacia fuera y ver más de la X y el eje Y, ¿quién va a
dominar en última instancia?
Así que en realidad resulta que 2 a la n, y se puede resolver esto con sólo
enchufando algún cada vez más grande nú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 la n algoritmo es una mierda absoluta.
Quiero decir que esto va a tomar un poco de tiempo para que el
equipo para batir a través.
>> Pero verás con el tiempo, sobre todo con los futuros boletines de problemas e incluso
proyectos fin de carrera, es sus datos conjunto 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ícil y más difícil acerca de estos problemas.
Y los tipos de problemas de lugares como Facebook y Google, y Microsoft,
y otros trabajan en es exactamente estos Datos especie de gran clase de preguntas
cada vez más en estos días.
>> Está bien.
Así que el éxito de Jennifer en ese segundo algoritmo, francamente, lo hizo increíblemente
bien la primera vez, pero vamos a escribirlo como la suerte para que podamos
puede aclarar este punto.
En el segundo caso, se aprovechó de un algoritmo que repite una y otra
de nuevo, pero ella tomó un concedida cierta suposición de que permitiéramos
, pero ella explotó cierto detalle el segunda 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ó, que afirman 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 definitivamente para llevar a cabo mucho, mucho más
más rápido en el largo plazo.
Pero ella tenía que tener la puertas ordenados por ella.
Ahora, me tomé la libertad de hacer eso por adelantado en la pantalla del ordenador
aquí, pero supongo que Jennifer tenía que hacerlo ella misma?
Supongamos que las puertas en cuestión datos representados en una base de datos, o
amigos registrados en Facebook, o ninguna de las páginas web en Internet que
varios sitios web podrían necesitar al índice o buscar de nuevo.
>> Supongamos que usted acaba de tener un datos en bruto establece y se dejó a usted, o para
Jennifer hacer que la clasificación?
Eso, más bien, requiere que respondamos la 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, es si me lleva bastante tiempo para ordenar
los números, ¿quién diablos le importa que puede encontrar un número como 50, de manera rápida,
como en el caso de Jennifer, si tenemos más de abrumado la cantidad de tiempo total
tomó por ordenar las cosas por adelantado?
>> Así que veamos si no podemos el pintar el cuadro aquí.
Tengo un montón entero más estrés bolas, si eso ayuda
romper el hielo aquí.
Y si no te importa, nos necesitará de siete voluntarios -
sucesivamente, en Aceptar.
Wow.
Así que no tenemos que gastar en 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ú delante cinco, 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 que chicos vienen para acá.
Yo te voy a dar a cada uno un número.
Y seguir adelante y organizar a sí mismos idé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 voluntarios aquí, que son iguales en anchura a la
matriz que estamos jugando con el anterior.
Y elegí siete por razones que será igual
conveniente en un poco.
Y voy a proponer primero que clasificamos estos siete voluntarios.
Si desea, en primer lugar, para saludar sin embargo.
Dado que esto va a ser un incó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 nuestros voluntarios aquí hasta ahora.
Y el reto que nos ocupa ahora va siendo para ordenar de estos chicos, pero luego
vamos a tener que pensar un poco tendido sobre la eficiencia con que en realidad
ellos ordenan.
Así que primero vamos a probar esto.
Ustedes pueden ver los números de los otros con sólo colocar alrededor de las esquinas.
Seguir adelante y tomar un par de segundos, y ordenar 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 algoritmo que estos tipos aplicados?
>> ALTAVOZ 1: De menos a más.
>> DAVID J. MALAN: OK.
De menos a más grande es realmente una especie de objetivo, pero no estoy seguro de que es
realmente un algoritmo.
De menos a más no dice me paso a paso lo que debe hacer.
¿Sí?
>> ALTAVOZ 1: [inaudible]
>> DAVID J. MALAN: OK.
Así que si ves a una persona menor de su 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 de constructor condicional.
Y estos chicos parecía hacer que unos pocos veces, porque algunos de ustedes se movieron un poco
de una distancia.
Así que hubo de suponer algún tipo de bucle pasando en sus mentes.
>> Pero vamos a tratar de formalizar eso.
Si ustedes pudieran restablecer de nuevo con esta disposición.
Vamos a ver si no podemos formalizar este un poco, 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 podemos poner 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 lado aquí 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, incluso instintivamente.
mantenerse en movimiento.
No se limitaron a detener, una vez que corregido un problema.
Así.
De hecho, voy a tener para hacer lo mismo.
Voy a tener que rebobinar suerte de volver al principio de este problema,
o el comienzo de esta serie de gente, vamos a empezar llamarlos.
>> Y ahora, ¿qué debería decir a mi algoritmo en 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 haciendo la 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 algunos El 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 esto un poco más de forma deliberada.
Y ahora, sólo hay un cerebro la ejecución de este algoritmo.
Una CPU, si se quiere.
Y, francamente, ese es el único recurso vamos a tener acceso.
¿Y una vez que nos hace volver a un teclado y tener algo como C en nuestra
disposición, que sólo estamos escribiendo un programa que puede hacer una cosa a la vez.
Considerando que, a estos chicos hace un momento, que aprovechado 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 jugar abogado del diablo.
¿Tengo el tipo de ordenador que acaba de hizo 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 de concluir de manera decisiva de que estoy hecho?
Probablemente uno pase más.
¿Cierto?
Porque todo lo que sé de ese anterior pase es que he corregido un error.
Y eso significa, tal vez hay aún otro error
que tengo que corregir.
Así que sólo puedo estar seguro de rebobinado y a 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 no trabajar con algo parecido a una variable,
como un int.
Llámelo swaps, swaps y si es 0, una vez que llegar hasta aquí, y empezó a 0, entonces
Sólo quiero ser estúpido para seguir adelante de ida y vuelta, comprobando de nuevo, y
otra vez, y otra vez, ¿verdad?
Porque te quedas atascado en algún tipo 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 acabamos implementado es algo que se llama la burbuja
tipo, conocido como tal en el sentido de que los números que son más grandes tipo de
burbuja de su camino a la cima, o hasta al final de la matriz de números.
Pero qué tan eficiente fue este algoritmo?
¿Cuántos pasos qué tuve que físicamente Tomemos, 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ífico no es tan interesante.
Vamos a generalizar como n.
Así que si yo tuviera aquí n personas, y ellos eran, más o menos, en un orden aleatorio en la
comenzando, en ese orden original.
Bueno, ¿cuántos pasos tenía yo para 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 n menos uno los pasos de la primera vez.
>> Ahora, ¿cuántos pasos tenía yo a tomar cuando Rebobiné?
Bueno, en realidad podríamos duplicar que si que 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 poner molestos 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 tomo un paso la próxima vez?
Bueno, es 3n.
realmente.
Y ahora, en el peor de los casos, por ejemplo, ¿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 tipo de pensar en esto de manera intuitiva,
a pesar de que puede ser que tome un poco de poco de tiempo a asimilar
En el peor de los casos, lo que haría estos siete personas han visto como, en
términos del acuerdo de 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 sobre aquí 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 con mí, si no te importa.
Así que voy a proponer, sólo por simplicidad, que Neil se encuentra ahora en su
peor de los casos posibles.
Pero recuerdo cómo he implementado mi algoritmo.
Estoy comparando, comparar, comparar, comparar, comparar, oh.
Ahora estos chicos están fuera de orden, así que puedo corregir.
Así que ustedes swap.
Pero consideremos ahora, cuánto más lejos Neil 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 poniendo hacer 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 cada tiempo, y para mover Neil un paso,
Tengo que hacer este paso realmente tedioso de 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 todos el camino a donde pertenece.
Por no hablar de todos los demás si ustedes fueron 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, el el 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 el mismo ejemplo con ocho personas, nueve
personas, un millón de personas, y que respuesta no va a cambiar.
>> Así que si ustedes no me importaría, vamos a que restablezca al punto de partida.
Y vamos a tratar otros dos enfoques y ver si no podemos hacerlo, fundamentalmente,
mejor que esto.
Así que esta vez, voy a proponer un 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 poco de intercambio de parejas.
Pero si realmente quería abordar este simplemente, y mi meta es mover
todos los pequeños números de esta manera, y empujar todos los grandes números que
cierto, ¿por qué no me hago en el la forma más ingenua posible y ver si
puede hacer algo mejor que lo que era un algoritmo bastante complejo?
>> Así que vamos a ver.
Cuatro es un número bastante pequeño, así que estoy voy a dejar ahí momento.
Ooh, el número dos es incluso mejor.
Así que puede que acaba de dar un paso adelante por un momento?
Esta es actualmente mi pequeño numerada candidato, y yo voy a recordar
que con, como, una variable.
Pero yo voy a seguir buscando.
¿Hay alguien cuya número es menor?
Seis, no.
Oh, hay Neil de nuevo.
>> Así que voy a empujar de vuelta tipo de conceptualmente.
Neil vendrá adelante.
Y ahora, la variable que estoy usando para realizar un seguimiento de quién tiene el más pequeño
número se actualiza para contener Ubicació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 simple para que haga ahora?
No voy a perder mi tiempo con sólo burbujeante Neil un lugar a la izquierda.
¿Por qué no acaba de poner Neil donde pertenece, 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, eres un poco en el camino.
Entonces, ¿cómo podemos resolver este problema?
¿Cierto?
Si se trata de una matriz, no hay sólo siete ubicaciones.
Recordemos que, con Rob, hablamos de declarando 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 nuestra manera, así que ¿cómo lo arreglamos?
>> La forma más sencilla es como, Gracia, lo siento.
Vas a tener que ir a través de allí, así que se puede dar cabida.
Ahora, si se piensa en ello, tal vez que acaba de hacer el problema peor.
Y tal vez lo hicimos, porque lo que si La gracia estaba en el lugar correcto?
Pero sabemos que no lo es, porque de lo contrario, habría sido
pie hacia adelante en lugar de Neil en este momento, ¿no?
Ya hemos comprobado su número fuera.
>> Está bien.
Así que ahora, Neil está en el lugar correcto, y Yo puedo hacer una ligera optimización.
Para el próximo minuto, voy a ignorar Neil todos juntos, a fin de no
perder el tiempo, o accidentalmente él cambiar al lugar equivocado.
Así que ahora, ¿cómo puedo encontrar la siguiente elemento que es más pequeño?
Dos.
Eso es un número bastante bueno, si quiere dar un paso adelante y
Yo te recuerdo.
Seis, no es bueno.
Cuatro, tres, siete, cinco, no es bueno.
Así que voy a mover a su lugar correcto.
Y tuvimos suerte esta vez.
>> Ahora, yo voy a hacer caso omiso de estos dos 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ño elemento 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 paso hacia 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 que Le 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 algoritmos es 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 el más pequeño elemento?
¿Cuántos pasos tuve que tomar el encontrar el elemento más pequeño?
Tenía una mirada todo el camino al final, ¿no?
Porque en ese caso peor, ¿qué si Neil estaban aquí?
Así que encontrar el elemento más pequeño me 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 siguiente má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 vez para encontrar el número tres?
Entonces n menos 4.
Así que es decreciente, uno menos paso 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 n menos 4, punto, punto, punto.
Pero si usted recuerda de su escuela secundaria libros de texto, el pequeño truco
hoja en la parte trasera que tiene las fórmulas, si realizar la suma de esta serie de números,
lo que es el número total de pasos vaya a ser que me tomo aquí?
>> Este es uno de los que, como, n menos 1, los tiempos de n, dividido por 2.
Así que déjame ver si puedo sacar esto por un momento.
Y de nuevo, estoy un poco redondeo algunas números sólo para mantener nuestra vida sencilla,
pero por lo que recuerdo, es algo así como si Hago n menos 1 cosas, entonces n menos
2, entonces n menos 3, que es más o menos algo así más de 2, y si
multiplique esto, eso es en 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 problemas empezar a ponerse interesante es cuando n
se pone muy grande.
Y cuando n se hace muy grande, lo que de estos 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 millones de piezas de datos, o miles de millones de
piezas de datos, OK, por lo que usted 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 de una diferencia de este tipo.
Así que a pesar de que ustedes están bien, el segundo algoritmo, lo vamos a llamar
ordenación por selección, es decir, en el mundo real, una poco más rápido en potencia, porque soy
teniendo cada vez menos pasos cada vez.
>> En realidad no es fundamentalmente más rápido.
Porque si en realidad nos jugamos esto para grandes valores de n, al final de
el día, por lo suficientemente grande n, sigue siendo va a sentir bastante lento.
Bueno, déjame tomar una último pase a eso.
Eso es lo que yo llamaría ordenación por selección.
Pueden ustedes restablecer mismos por última vez?
Y en este último caso, voy proponer algo
llamada ordenación por inserción.
Ser la ordenación por inserción, conceptualmente, un poco diferente.
>> En lugar de ir y venir y seleccionar el elemento más pequeño, estoy
sólo va a tratar con cada uno de estos chicos 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 pudiera dar un paso a la derecha, esta
mi lista ordenada, este es mi lista 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 que fuera por un momento.
Y ahora, ¿dónde perteneces en esta serie?
Así que a la derecha de la Gracia.
Así que de nuevo, estamos como hacer La gracia hacer un montón de trabajo aquí.
¿Dónde ponemos usted?
Así que te vamos a deslizar a la a la izquierda, e introduzca Branson allí.
Pero ahora afirmo que ustedes llevan a cabo.
Pero aviso, no estoy usando el espacio extra.
Sigue siendo 2 elementos aquí, 5 aquí.
Tamaño total de la matriz es de 7, así que estoy no copiar, no está bien?
>> Así que ahora tenemos, con Gabe aquí, el número seis, ¿de dónde sois?
Tuviste suerte de nuevo.
Así que usted puede permanecer allí.
Basta con echar un ligero paso hacia la derecha sólo para dejar en claro que está ordenada.
Y ahora tenemos a Neil de nuevo, el número de uno, ¿a dónde vas?
Y ahora es cuando vamos a empezar a ver que este algoritmo, aunque en primera
vista, se siente muy inteligente, reloj lo que va a suceder.
Si pudiera dar un paso adelante.
>> ¿Dónde queremos poner Neil?
Así que, obviamente, aquí, así que ¿cómo Có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 Neil otra, y otra, y otra vez, para ponerlo
a dónde va, en el peor de los casos, la siguiente número, podríamos encontrarnos podría
ser el número, por ejemplo, hubo un número cero, entonces vamos a cambiar todo
estos chicos.
Supongamos que hay un número negativo uno, entonces tenemos que cambiar
todos estos chicos.
Así que estamos realmente sólo un poco de mover de un tirón el problema nada más, de modo que estamos
la transferencia de la costa de la proceso de selección por lo que la inserción
proceso, de tal manera que ustedes acababan de para mover más o menos n menos algo
número de pasos.
Y ese número de pasos sólo se va aumentando a medida que selecciono más números,
si tengo que seguir empujando a ustedes espalda, y la espalda, y la espalda.
>> Así lo triste ahora es todo esto algoritmos se n al cuadrado.
Vamos a seguir adelante y gracias a estos chicos 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 puede mantener los números también.
Está bien.
Muy bien hecho.
Está bien.
Así que vamos a ver si ahora no podemos resumir más rápidamente, y más visualmente,
exactamente lo que acaba de suceder aquí como sigue.
Voy a seguir adelante y tire hacia arriba Firefox.
Nos vincularemos esta manifestación en la página web del curso.
Java es un poco molesto para conseguir trabajo en 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 esta demostración es la siguiente.
>> En la parte inferior, tengo un montón de opciones del menú, incluyendo un inicio y un
botón de parar.
También, en un aparte, parece que hay una bug en estos programas, mediante el cual se
no puede ver realmente el inicio o detener botón a menos que mantenga Comando o Alt
plus y acercar la imagen, que curiosamente te muestra más botones.
Así que lo digo si juegas con esto en casa.
Ahora voy hacer clic en Inicio en tan sólo Actualmente, después de especificar un retraso de,
como 200 milisegundos aquí, sólo para que podamos ver lo que pasa.
>> Así que yo sostengo que esta es una visualización de la primera algoritmo
estos chicos lo hicieron, especie de burbuja, en el que intercambiamos personas por pares.
La idea clave de esta visualización es 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 pasando la primera iteración de este algoritmo,
intercambio de números grandes y pequeños, de manera que el número pequeño viene primero y
el gran número va a la derecha.
>> Y tan pronto como llegamos al final de la matriz de 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 va para intercambiar a un lado, y este
proceso se repite.
Ahora esta visualización se pone rápidamente aburrido, por lo que me dejó ir adelante y dejar de
ella, cambie la demora algo mucho más rápido sólo para ahora, una idea de
este algoritmo.
>> Así que, aunque he aceleró hacia arriba, esto es como actualizar mi procesador, la compra de
un equipo nuevo.
No he cambiado fundamentalmente mi algoritmo, pero de hecho, puede ver más
claramente que con los seres humanos, que el gran números están burbujeando hasta la cima,
y el pequeño número están burbujeando hasta la parte inferior.
¿Y ahora esta cosa aquí ordenada.
Y en un aparte, en las plazas, no hay só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 de los otros que vimos.
Permítanme clic en especie de burbuja aquí, y permitirme elegir, y esta página web entera
es un poco buggy.
Aceptemos el riesgo y 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 eso bug, cambiarlo a 50.
Ah, vamos a hacer realidad que 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 que lo hizo con los humanos hasta aquí.
Fuimos a través de la matriz y seleccionamos el 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 tomando ligeramente 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í que era de hecho una ganancia significativa.
>> Permítanme ahora volver atrás y cambiar a nuestro tercer algoritmo, que era seleccione
ordenación por inserción.
Y ahora está realmente buggy porque el menú 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 bastante a la misma, con lo cual estamos de nuevo
la inserción de los seres humanos, o en este caso, las barras en
su ubicación adecuada.
Y es que ya ha hecho antes Me 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 dar nosotros una especie de una manera común de hablar
acerca de estas cosas, permítanme presentarles sólo un poco de notación aquí.
Estás a punto de ver algo que se llama gran O, ya que es, literalmente, una gran
O. Y esta es una manera de que un ordenador científico o un matemático usos incluso
para describir el tiempo de ejecución de algún algoritmo.
¿Cuántos pasos que realmente necesita?
>> Ahora me voy a avergonzar a mí mismo con mi letra aquí en un momento.
Pero déjame seguir adelante y decir que esto va a ser grande O por aquí.
Y permítanme presentarles a otro sí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 tiempo podría tomar algún algoritmo, en
términos de n, omega va a será la cantidad de tiempo que podría
tomar en el mejor de los casos.
Y veremos lo que entendemos por mejor 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 de mesa 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 una número de elección arbitraria?
Y hay n puertas totales o n números totales.
Peor de los casos.
¿Cuántos pasos voy a tener que tomar para encontrar el número 50 en una serie
de n puertas?
¿Y por qué?
Debido a que puede ser todo el muy por encima en el extremo.
Así que al igual que Jennifer se encontró con el número 50 fue todo el camino, por lo que en
el peor de los casos búsqueda lineal es 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 algo como búsqueda binaria?
Así que la búsqueda binaria, en el peor de los casos caso, 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 de encontrar, en última instancia, el valor,
si está allí, pero hay una trampa.
¿Cuál es la suposición de que tenemos que dar por sentado de búsqueda binaria?
Tiene que ser resuelto.
No es ordenada, se puede dividir la cosa la mitad otra vez y otra vez, y usted
puede ir a la izquierda, y se puede ir a la derecha, y usted puede ir a la izquierda y la derecha, pero usted es
No va a encontrar el elemento si la lista no está ordenada, porque
puede que te pierdas.
Debido a que su heurística, para ir a la izquierda o hacia la derecha va a ser defectuoso si es
de hecho, no ordenados.
Así que hay una especie de costo oculto para el uso de algo como esto.
>> Ahora, vamos a entrar en nuestra clasificación algoritmos 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 ser en 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 el tipo, no las búsquedas.
>> En el peor de los casos, el número de pasos que hicieron burbuja reclamo especie va a tomar?
n al cuadrado.
Así que voy a dibujar eso.
Ooh, mi letra se ve aún peor cuando 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 elegir Además, al menos el primero de los
sugerencias, 1.
No es una mala instinto, porque clase de la siguiente manera un patrón aquí.
Pero si sólo se necesita 1 paso, como en el mundo podría yo afirmar que la lista
está ordenada, porque si sólo se me permite tomar 1 paso, ¿cuántos elementos
pude comprobar realmente estar seguro?
Bueno, sólo 1, que significa que hay n menos 1 elementos que podrían estar fuera de
orden, y yo sólo voy a la fe después de mirando a 1 elemento que el
cosa está ordenada.
Así 1 de no corrige aquí.
Así mínimamente, ¿cuántos Qué tengo que mirar?
>> [VOCES interponiendo]
>> DAVID J. MALAN: n menos 1, o en realidad, n, porque tengo que mirar cada
elemento para asegurarse de que no es fuera de servicio.
Pero una vez más, vamos a clase de agitamos nuestra manos en los números más pequeños y
asumen que, a medida que n se hace grande, son poco 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 a hacer la ordenación por inserción.
Y luego vamos a volar tu mentes con algo mucho
mejor que todos ellos.
Está bien.
>> ¿Cuál es el peor de los casos se ejecuta momento 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ón tipo n al cuadrado?
¿Qué teníamos que hacer una y otra vez?
Tuvimos que mantener la exploración a través, son que 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 n pasos, 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 n cuadrado 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 mejor caso, la cantidad de pasos es
me va a llevar?
>> ALTAVOZ 5: [inaudible]
>> DAVID J. MALAN: Es lamentablemente siendo n al cuadrado, ¿verdad?
Porque si estoy seleccionando los más pequeños elemento, y que teníamos siete personas aquí,
Lo único que sé, una vez que llegue a la misma fin, que he encontrado el más pequeño
número, donde sea que él o ella pudo haber sido.
Pero ¿cómo puedo encontrar la siguiente menor número?
Tengo que hacer otra pasada.
Así que en el mejor de los casos, lo que es lo entrada 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 uno cosa a la vez.
No puedo especie de dar un paso de nuevo como un ser humano y decir:
ooh, esto parece correcto.
>> Sólo puedo juzgar la corrección en ordenació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 que Sé que me han dado una serie
o un conjunto de puertas detrás de las cuales son nú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 que dos es la siguiente más pequeña?
Al hacer la misma ineficiencia una 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 que todo esto, ¿de acuerdo?
>> Así que piense por sí mismo lo inserción especie 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 poco diferente manifestación.
Si hago zoom aquí, verás que en la izquierda tenemos una especie de burbuja, en el
centro tenemos ordenación por selección, y en la extrema derecha, que tienen algo que
no han mirado todavía llamado merge sort.
Pero consideremos lo que hemos sido haciendo 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 de clase, cuando habíamos dividir y conquistar,
y tuvimos el lagrimeo guía telefónica, y Jennifer, y colectivamente
apalancada que idea clave, que debía repetirte 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 equivalente a la otra, de alguna manera hicimos
fundamentalmente mejor.
Pero con la ordenación de burbuja, con la selección especie, con la ordenación por inserción, hemos podrá
hay tales ideas que Jennifer hizo.
Nos prácticamente sólo caminamos de regreso y sucesivamente un montón de veces, y nos
ajustado un poco las cosas, el intercambio de en este orden, tal vez
la inserción o la selección.
Pero al final del día, hice un montón torpe caminar de ida y vuelta.
Nosotros realmente no aprovechamos algo inteligente como Jennifer le gustaba dividiendo
y conquistando.
>> Así fusionar especie, por el contrario, que nos no verá hasta la próxima semana, que va
para aprovechar esa idea clave dividiendo la 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, y la mitad derecha de la mitad derecha.
Y repitiendo una y otra vez.
>> Así verás esto visualmente, pero esta es lo que nos espera la próxima semana.
Y, en general, cuando pensamos un poco poco más difícil en cualquier problema.
N Hemos cuadrado en el lado izquierdo, N cuadrado en el medio, y n
log n a la derecha.
Así que ahí está tu melodrama real.
Nos vemos el lunes.
>> [Aplausos]