>> [REPRODUCCIÓN DE MÚSICA]
DAVID MALAN: Muy bien.
Muy bien, bienvenido.
Así que esta es la Semana 4, el comienzo de los mismos, ya.
¿Y te recuerdo que la semana pasada, pusimos codificar un lado por un poco
y empezamos a hablar un poco más de alto nivel, por cosas como
búsqueda y ordenación, que a pesar de las ideas un tanto simples, son
representante de una clase de problemas usted comenzará a resolver todo
a medida que empiezas a pensar en definitiva proyectos y soluciones interesantes le
podría tener problemas del mundo real.
Ahora especie de burbuja fue uno de los más sencillos este tipo de algoritmos, y que
trabajado por tener estos pequeños números en una lista o en un tipo de matriz de
burbuja de su camino a la cima, y ​​el grandes números de mover su camino hasta
Al final de esa lista.
>> Y recordemos que pudimos visualizar ordenamiento de burbuja un poco
algo como esto.
Así que déjame ir adelante y haga clic en Iniciar.
He preseleccionado especie de burbuja.
Y si usted recuerda que el azul más alto líneas representan números grandes, pequeñas
líneas azules representan los números pequeños, como pasamos por esto una y otra vez y
de nuevo, la comparación de dos bares al lado de cada uno otra de color rojo, que vamos a cambiar la
más grande y la más pequeña, si que están fuera de orden.
>> Así que esto va a seguir y seguir y seguir , y usted verá que la mayor
elementos están haciendo su camino a la derecha, y los elementos más pequeños son
hacer su camino a la izquierda.
Pero empezamos a cuantificar la eficiencia, la
calidad de este algoritmo.
Y dijimos que en el peor caso, este algoritmo tomó
más o menos la cantidad de pasos?
>> Así que n al cuadrado.
¿Y qué era n?
>> AUDIENCIA: Número de elementos.
>> DAVID MALAN: Así fue la n número de elementos.
Así que vamos a hacer esto con frecuencia.
Cada vez que queremos hablar sobre el tamaño de un problema o el tamaño de un
entrada, o la cantidad de tiempo que tarda para producir una salida, sólo tendremos que
generalizada lo la entrada es como n.
Así que de vuelta en la semana 0, el número de páginas en la guía telefónica era n.
El número de estudiantes en la habitación era n.
Así que aquí, también, estamos siguiendo ese patrón.
>> Ahora n al cuadrado no es particularmente rápido, por lo que tratamos de hacer mejor.
Así que miramos un par de otros algoritmos, entre los cuales
fueron ordenación por selección.
Así ordenación por selección fue un poco diferente.
Era casi más sencillo, me atrevo a decir, por el que empecé en el inicio de la
Lista de nuestros voluntarios y acabo de nuevo y una y otra vez fue a través de
la lista, arrancarse el más pequeño elemento a la vez y ponerlo o
ella en el principio de la lista.
>> Pero también esto, una vez que comenzó a pensar a través de las matemáticas y más grande
imagen, pensé en cuántas veces Yo iba de ida y vuelta y de vuelta
adelante y hacia atrás, dijimos en el peor de los casos, ordenación por selección también era qué?
n al cuadrado.
Ahora en el mundo real, podría en realidad ser marginalmente más rápido.
Porque de nuevo, yo no tengo que seguir dar marcha atrás una vez que había ordenado la
elementos más pequeños.
Pero si lo pensamos muy grandes de n, y si usted suerte de hacer la matemática como
Lo hice en el tablero, con el n al cuadrado menos algo, todo lo demás
además del N al cuadrado, una vez N se pone muy grande, ¿no
Realmente importa tanto.
Así como los informáticos, que tipo de hacer la vista gorda a la más pequeña
factores y centrarse sólo en el factor de una expresión que se va a hacer
la mayor diferencia.
>> Bueno, por último, buscamos en la ordenación por inserción.
Y esta fue similar en espíritu, pero en lugar de ir a través de forma iterativa y
seleccionar el elemento de uno más pequeño a un tiempo, en vez tomé la mano que me
fue tratado, y decidí, todo derecho, usted pertenece aquí.
Luego pasé al siguiente elemento y decidió que él o
pertenecía aquí.
Y luego me mudé y sigue.
Y yo fuerzas para, en el camino, cambiar estos chicos con el fin de
hacer espacio para ellos.
Así que fue una especie de reversión mentales de ordenación por selección que
llamada ordenación por inserción.
>> Así que estos temas que se produzca en el mundo real.
Hace apenas unos años, cuando un determinado senador fue candidato a la presidencia,
Eric Schmidt, en el momento en que el director general de Google, en realidad tuvo la oportunidad
para entrevistarlo.
Y pensamos que sería buena idea compartir esta YouTube cortar para usted aquí, si pudiéramos subir
el volumen.
>> [REPRODUCCIÓN DE VÍDEO]
>> -Ahora, el senador, estás aquí en Google, y me gusta pensar en la presidencia
como una entrevista de trabajo.
>> [Risas]
>> -Ahora es difícil de conseguir un trabajo como presidente.
Y usted va a través de los rigores ahora.
También es difícil de conseguir un trabajo en Google.
Tenemos preguntas y le pedimos nuestras preguntas de los candidatos.
Y ésta es de Larry Schwimmer.
>> [Risas]
-Ustedes piensan que estoy bromeando?
Está justo aquí.
¿Cuál es la forma más eficiente de ordenar un millón de enteros de dos bits?
>> [Risas]
>> -Bueno, eh -
>> -Lo siento.
Tal vez debería -
>> -No, no, no, no, no.
>> -Eso no es un -
Aceptar.
>> -Creo que el ordenamiento de burbuja haría ser el camino equivocado.
>> [Risas]
>> [Vítores y aplausos]
>> -Vamos, ¿quién le dijo eso?
Aceptar.
>> [VIDEO PLAYBACK FIN]
>> DAVID MALAN: Así que ahí lo tienen.
Así que empezamos a cuantificar estas corriendo veces, por así decirlo, con algo
llamado notación asintótica, que es sólo se refiere a nuestra especie de giro
la vista gorda a los factores más pequeños y sólo mirar el tiempo de funcionamiento,
el rendimiento de estos algoritmos, a medida que n se pone muy grande con el tiempo.
Y por eso hemos introducido gran O. Y gran O representado algo que pensamos
de como un límite superior.
Y en realidad, Barry, ¿podemos bajar que el micrófono un poco?
>> Pensamos que es una cota superior.
Así que gran O de n al cuadrado significa que en el peor de los casos, algo así como
ordenación por selección tomaría n al cuadrado pasos.
O algo así como la ordenación por inserción sería n al cuadrado pasos.
Ahora para algo como la inserción especie, lo que fue el peor de los casos?
Dada una matriz, lo que es lo peor posible escenario que le puede resultar
hecho frente con?
>> Es totalmente al revés, ¿no?
Porque si es totalmente al revés, usted tiene que hacer un montón de trabajo.
Porque si usted es totalmente al revés, usted va a encontrar el
mayor elemento de aquí, aunque pertenece allí.
Así que vas a decir, de acuerdo, en este momento en el tiempo, que es de aquí,
así que lo deje en paz.
>> Entonces te das cuenta, oh, maldita sea, tengo que mover este elemento ligeramente más pequeño a
la izquierda de usted.
Entonces tengo que hacer eso de nuevo y una y otra vez.
Y si caminaba de ida y vuelta, que sería una especie de sentir el desempeño de
que algoritmo, porque constantemente estoy arrastrando los pies a todos los demás en la
matriz para hacer espacio para él.
Así que ese es el peor de los casos.
>> Por el contrario -
y éste era un cliffhanger última vez -
decíamos que la ordenación por inserción era un omega de qué?
¿Cuál es el mejor de los casos en ejecución momento de la ordenación por inserción?
Así que en realidad es n.
Ese fue el espacio en blanco que dejamos en el tablero de la última vez.
>> Y es el omega de n porque ¿por qué?
Pues bien, en el mejor de los casos, lo que es ordenación por inserción va a ser entregado?
Bueno, una lista que está completamente ordenada Ya, un mínimo de trabajo para hacer.
Pero lo que es bueno de ordenación por inserción es que, ya que comienza aquí y
Decide, oh, eres el número uno, ustedes pertenecen aquí.
¡Oh, qué buena fortuna.
>> Usted es el número dos.
También perteneces aquí.
Número tres, mejor aún, perteneces aquí.
Tan pronto como se llega al final de la lista, por la ordenación por inserción es pseudocódigo
que caminamos a través verbalmente la última vez, ya está hecho.
Pero ordenación por selección, por el contrario, mantenido haciendo qué?
>> Siguió su camino a través de la lista una y otra vez y otra vez.
Porque la idea clave que sólo había una vez que has mirado todo el camino a la
final de la lista puede estar seguro que el elemento que ha seleccionado se
de hecho el elemento actualmente más pequeño.
Así que estos diferentes modelos mentales terminan cediendo algunos muy real
diferencias para nosotros, así como ellos asintóticas diferencias teóricas.
>> Así que para recapitular, pues, gran O de n cuadrado, hemos visto unos pocos,
algoritmos hasta ahora.
Gran O del n?
¿Qué es un algoritmo que podría decirse que gran O de n?
En el peor de los casos, se necesita una serie lineal de pasos.
>> Aceptar, búsqueda lineal.
Y en el peor de los casos, ¿dónde está el elemento que está buscando cuando
la aplicación de búsqueda lineal?
>> Aceptar, en el peor de los casos, ni siquiera existe.
O en el segundo peor de los casos, es todo el camino al final, que es
más-o-menos una diferencia de un solo paso.
Así que al final de la día, podemos decir que es lineal.
Big O de n seria búsqueda lineal, porque en el peor de los casos, la
elemento ni siquiera existe o que es todo el camino al final.
>> Bueno, gran O de registro de n.
No hablamos en detalle sobre esto, pero hemos visto esto antes.
¿Qué pasa en la llamada logarítmica tiempo, en el peor de los casos?
>> Sí, por lo que la búsqueda binaria.
Y la búsqueda binaria en el peor de los casos podría tener el elemento en algún lugar
el medio, o en algún lugar dentro de la matriz.
Pero sólo se encuentra una vez que dividir la lista en dos, en
un medio, en un medio, en un medio.
Y luego voila, está ahí.
O, de nuevo, peor de los casos, ni siquiera existe.
Pero usted no sabe que no está allí hasta que se llegue a esa especie de última
abajo hacia la mayoría de los elementos de reducir a la mitad y reducir a la mitad y la reducción a la mitad.
>> Big O de 1.
Así que pudimos gran O de 2, gran O de 3.
Cada vez que quieres es simplemente un número constante, que sólo una especie de sólo simplificamos
que, como gran O de 1.
Aunque si de manera realista, toma 2 o incluso 100 pasos, si se trata de un
número constante de pasos, nos limitamos a decir gran O de 1.
¿Qué es un algoritmo que es en gran O de 1?
>> AUDIENCIA: Encontrar la longitud de una variable.
>> DAVID MALAN: Encontrar el longitud de una variable?
>> AUDIENCIA: No, la longitud si ya está solucionado.
>> DAVID MALAN: Good.
Aceptar, por lo que encontrar la longitud de algo si la longitud de que algo, como
una matriz, se almacena en una variable.
Debido a que sólo se puede leer la variable, o imprimir la variable o
sólo en general acceder a esa variable.
Y voila, eso toma tiempo constante.
>> Por el contrario, piense de nuevo a cero.
Piense de nuevo a la primera semana de C, llamando simplemente printf e impresión
algo en la pantalla es sin duda constante de tiempo, ya que sólo se necesita
cierto número de ciclos de CPU para mostrar que el texto en la pantalla.
O esperar - ¿o sí?
¿Cómo más podríamos modelar el rendimiento de printf?
¿Alguien quisiera estar en desacuerdo, que tal vez no es realmente constante de tiempo?
¿En qué correr el poderío de printf sentido tiempo, en realidad la impresión de una cadena en
la pantalla, sea algo que no sea constante.
>> AUDIENCIA: [inaudible].
>> DAVID MALAN: Si.
Así que depende de nuestra perspectiva.
Si realmente pensamos en la entrada printf como la cadena y
Por lo tanto, medimos el tamaño de ese de entrada por su longitud - así que vamos a llamar
que longitud n, así -
podría decirse que, printf es en sí misma gran O de n porque va a llevarte n pasos
para imprimir cada uno de los N caracteres, más probable.
Al menos en la medida en que suponemos que tal vez se trata de utilizar un bucle for
debajo de la capucha.
>> Pero tendríamos que mirar ese código para entenderlo mejor.
Y, en efecto, una vez que ustedes empezar el análisis de sus propios algoritmos, usted
literalmente hacer precisamente eso.
Una especie de globo ocular de su código y pensar sobre - todo bien, tengo este bucle
aquí o tengo bucles anidados aquí, eso va a hacer las cosas n n veces,
y se puede ordenar de razonar su camino a través del código, incluso si es
pseudocódigo y código no real.
>> ¿Qué pasa con el omega de n al cuadrado?
¿Qué era un algoritmo que, en el mejor caso, todavía tardó n al cuadrado pasos?
¿Sí?
>> AUDIENCIA: [inaudible].
>> DAVID MALAN: Así ordenación por selección.
Porque en ese problema realmente reducida al hecho de que una vez más, no lo sé
He encontrado la corriente más pequeña hasta He comprobado todos los elementos maldito.
Así omega de, por ejemplo, n, que sólo se le ocurrió una.
La ordenación por inserción.
Si la lista pasa a ser ordenados Ya, en el mejor de los casos sólo tenemos
para hacer un pase a través de él, momento en el que estamos seguros.
Y luego de que se puede decir a ser lineal, sin duda.
>> ¿Qué pasa con el omega de 1?
¿Cuál es, en el mejor de los casos, podría tomar un número constante de pasos?
Así que la búsqueda lineal, si usted acaba de tener suerte y el elemento que está buscando
es justo al principio de la lista, si es ahí donde usted está comenzando su
recorrido lineal de esa lista.
>> Y esto es verdad de un número de cosas.
Por ejemplo, incluso binario búsqueda es el omega de 1.
Porque lo que si usted consigue realmente maldito suerte y justo-DAB en el centro de
la matriz es el número que está buscando?
Así que usted puede tener suerte allí, también.
>> Éste, por último, el omega de n log n.
Entonces n log n, no lo hicimos realmente hablar todavía, pero -
>> AUDIENCIA: Combinar tipo?
>> DAVID MALAN: Combinar especie.
Ese fue el drama de suspenso de la última vez, donde nos propusimos, y nos mostramos
visualmente, que hay algoritmos.
Y combinar especie de sólo uno de estos algoritmo que es fundamentalmente más rápido
que algunos de estos otros tipos.
De hecho, fusionar corta es no sólo en el mejor de los casos n log n, en el peor de los casos
caso n log n.
Y cuando usted tiene esta coincidencia de omega y gran O de ser la misma cosa?
De hecho, podemos describir eso como lo que es llamada theta, aunque es un
poco menos común.
Pero eso sólo significa que los dos límites, en este caso, son la misma.
>> Así fusionar especie, lo que hace este realmente se reducen a por nosotros?
Bueno, recordar la motivación.
Déjame sacar otra animación que que no nos fijamos en la última vez.
Éste, misma idea, pero que es un poco más grande.
Y yo voy a seguir adelante y señalar primero - tenemos la ordenación por inserción en
la parte superior izquierda, a continuación, ordenación por selección, ordenamiento de burbuja, un par de otros tipos -
Shell y rápida - que no hemos hablado aproximadamente, y el montón y fusionar especie.
>> Así, al menos, tratar de enfocar sus ojos en los tres primeros de la izquierda y luego
fusionar especie cuando hago clic en esta flecha verde.
Pero voy a dejar que todos ellos corren, sólo para le dará una idea de la diversidad de
algoritmos que existen en el mundo.
Voy a dejar que este plazo por tan sólo unos segundos.
Y si te enfocas tus ojos - elegir una algoritmo, se centran en ella sólo por un
segundo - usted comenzará a ver el patrón que está la aplicación.
>> Combinar clase, aviso, se hace.
Pila de clasificación, ordenación rápida, cáscara -
por lo que parece que presentamos los tres peores algoritmos de semana pasado.
Pero eso es bueno que estamos aquí hoy para mira merge sort, el cual es uno de
los más fáciles es a la vista, incluso aunque probablemente se doblará tu mente
sólo un poco.
Aquí podemos ver hasta qué punto ordenación por selección es una mierda.
>> Pero por el otro lado, es muy fácil de implementar.
Y tal vez para el conjunto P 3, esa es una de las algoritmos que eligió para implementar
para la edición estándar.
Perfectamente bien, perfectamente correcta.
>> Pero una vez más, a medida que n se hace grande, si usted optar por aplicar un algoritmo más rápido
como la combinación de clase, las probabilidades están en mayor y insumos de mayor tamaño, su código es sólo
va a correr más rápido.
Su sitio web va a funcionar mejor.
Los usuarios van a ser más feliz.
Y por eso hay estos efectos de la realidad, dando
nosotros algo más profundo que pensamos.
>> Así que echemos un vistazo a lo que la combinación de especie es realmente todo.
Lo bueno es que la combinación de especie es sólo esto.
Esto es, una vez más, lo que hemos llamado pseudocódigo, ser pseudocódigo
Sintaxis similar al Inglés.
Y la simplicidad es especie de fascinante.
>> Así que en la entrada de n elementos - de manera que Sólo significa, aquí está una matriz.
Tiene n cosas en ella.
Eso es todo lo que estamos diciendo no.
>> Si n es menor que 2, retorno.
Así que eso es sólo el caso trivial.
Si n es menor que 2, entonces obviamente es 1 o 0, en cuyo caso la cosa
ya está ordenada o no existen, así que volver.
No hay nada que hacer.
Así que eso es un caso sencillo de arrancar.
>> Si no, tenemos tres pasos.
Ordene la mitad izquierda de los elementos, más o menos la mitad derecha de los elementos,
y luego fusionar las mitades ordenados.
Lo que es interesante aquí es que Soy una especie de batea, ¿verdad?
Hay una especie de definición circular a este algoritmo.
¿En qué sentido es este algoritmo de circular definición?
>> AUDIENCIA: [inaudible].
>> DAVID MALAN: Sí, mi algoritmo de clasificación, dos de sus pasos son "una especie
algo ". Así que plantea la pregunta, bueno, ¿qué voy a utilizar
para ordenar la mitad izquierda y la mitad derecha?
Y la belleza es que a pesar de que de nuevo, esta es la mente-flexión
desprenderse potencialmente, puede utilizar la misma algoritmo para ordenar la mitad izquierda.
>> Pero espere un minuto.
Cuando te dicen que ordenar la medio izquierdo, ¿cuáles son los dos
pasos va a ser el próximo?
Lo arreglaremos la mitad izquierda de la medio izquierdo y el derecho
la mitad de la mitad izquierda.
Maldita sea, ¿cómo puedo ordenar esos dos mitades o cuartos, ahora?
>> Pero eso está bien.
Tenemos un algoritmo de clasificación aquí.
Y aunque es posible que preocuparse en primero se trata de una especie de infinito
bucle, es un ciclo que nunca es ir al final - que va a
terminar de una vez lo que pasa?
Una vez que n es menor que 2.
Que con el tiempo va a pasar, porque si sigues reducción a la mitad y
reducir a la mitad en reducir a la mitad estas mitades, seguramente finalmente va a terminar
con sólo 1 o 0 elementos.
En ese momento, este algoritmo dice que usted está.
>> Así que la verdadera magia de esta algoritmo parece estar en
ese paso final, la fusión.
Esa simple idea sólo la fusión de dos cosas, eso es lo que en última instancia va
que nos permita ordenar una matriz de, digamos, ocho elementos.
Así que tengo ocho más bolas de la tensión de hasta aquí, ocho trozos de papel, y un
Google Glass -
que tengo la oportunidad de mantener.
>> [Risas]
>> DAVID MALAN: Si pudiéramos tomar ocho voluntarios, y vamos a ver si podemos
jugar a esto, así que.
Wow, OK.
La informática es cada vez divertido.
Está bien.
Así que ¿qué hay de ustedes tres, mayor a mano allí.
Cuatro en la parte posterior.
Y ¿qué tal si voy a hacer usted tres en esta fila?
Y cuatro en la parte delantera.
Así que ocho, vamos arriba.
>> [Risas]
>> DAVID MALAN: En realidad soy no estoy seguro de lo que es.
¿Es que las bolas de estrés?
Lámparas del escritorio?
El material?
El Internet?
>> Aceptar.
Así que ven arriba.
¿Quién quiere -
siguen llegando.
Vamos a ver.
Y esto te pone en el lugar -
usted está en una ubicación.
Uh-oh, espera un minuto.
1, 2, 3, 4, 5, 6, 7 - oh, bien.
Muy bien, estamos bien.
Muy bien, así que cada uno tiene un asiento, pero no en el cristal de Google.
Permítanme hacer cola estos.
¿Cómo te llamas?
>> MICHELLE: Michelle.
>> DAVID MALAN: Michelle?
Muy bien, se llega a parecerse el friki, si eso está bien.
Bueno, yo también, supongo, sólo por un momento.
Muy bien, espera.
Hemos estado tratando de llegar a un caso de uso de Google Glass, y
pensó que sería divertido para hacer esto cuando la gente está en el escenario.
Vamos a grabar el mundo desde su perspectiva.
Está bien.
No, probablemente lo que pretende Google.
Muy bien, si no te importa que llevaba esto durante los próximos minutos torpes,
eso sería maravilloso.
>> Muy bien, así que tenemos aquí una serie de elementos, y esa matriz, como por la
trozos de papel en estas personas ' las manos, se encuentra actualmente sin clasificar.
>> MICHELLE: Oh, eso es tan raro.
>> DAVID MALAN: Es más o menos al azar.
Y en un momento, vamos a tratar implementar merge sort juntos
y ver a dónde idea clave es.
Y el truco aquí con la combinación de tipo es algo que no hemos asumido todavía.
En realidad necesitamos un poco de espacio adicional.
Entonces, ¿qué va a ser particularmente interesante de esto es que estos
chicos van a moverse un poco poco, porque yo voy a asumir que
hay un conjunto adicional de espacio, decir, justo detrás de ellos.
>> Así que si están detrás de su silla, esa es la matriz secundaria.
Si están sentados aquí, eso es la matriz primaria.
Pero este es un recurso que tenemos no aprovechado hasta ahora con la burbuja
especie, con la selección de género, con la ordenación por inserción.
Recordemos la semana pasada, todo el mundo tipo de baraja en su lugar.
No usaron la memoria adicional.
Hicimos habitación para personas con mover a la gente alrededor.
>> Así que esta es una idea clave, también.
Hay un trade-off, en general, en ciencias de la computación, de los recursos.
Si desea acelerar algo como el tiempo, vas a
que tenga que pagar un precio.
Y uno de esos precios es muy a menudo el espacio, la cantidad de memoria o disco
espacio de disco que está utilizando.
O bien, francamente, la cantidad de tiempo del programador.
¿Cuánto tiempo le toma, el ser humano, a aplicar en la práctica algunos más
algoritmo complicado.
Pero por hoy, el trade-off es el tiempo y el espacio.
>> Así que si ustedes pudieran acaba de celebrar su números para que podamos ver que eres
de hecho a juego 4, 2, 6, 1, 3, 7, 8.
Excelente.
Así que voy a tratar de orquestar cosas, si ustedes pueden simplemente
seguir mi ejemplo aquí.
>> Así que me voy a poner en práctica, en primer lugar, la primer paso de la pseudocódigo, que es
en la entrada de n elementos, si n es menos de 2, y luego volver.
Obviamente, eso no lo hace Aplicamos, por lo que seguimos adelante.
Así ordenar la mitad izquierda de los elementos.
Así que eso significa que voy a centrar mi atención por un momento sobre estas
cuatro tipos de aquí.
Muy bien, ¿qué es lo próximo a hacer?
>> AUDIENCIA: Ordene la mitad izquierda.
>> DAVID MALAN: Así que ahora tengo que ordenar La mitad izquierda de estos chicos.
Porque de nuevo, supongamos que usted mismo la objetivo es ordenar la mitad izquierda.
¿Cómo se hace eso?
Sólo tienes que seguir las instrucciones, incluso aunque lo estamos haciendo de nuevo.
Así ordenar la mitad izquierda.
Ahora estoy clasificar estos dos chicos.
¿Qué viene ahora?
>> AUDIENCIA: Ordene la mitad izquierda.
>> DAVID MALAN: Ordene la mitad izquierda.
Así que ahora éstos, este asiento aquí, es una lista de tamaño 1.
¿Y cuál es tu nombre?
>> PRINCESA MARGARITA: Princess Daisy.
>> DAVID MALAN: Princess Daisy está aquí.
Y así que ella ya está ordenado, porque la lista es de tamaño 1.
¿Qué debo hacer al lado?
Aceptar, volverá, porque esa lista es de tamaño 1, que es menor que 2.
Entonces ¿cuál es el siguiente paso?
Y ahora tienes que tipo de dar marcha atrás en su mente.
>> Ordene la mitad derecha, que es -
¿cuál es tu nombre?
>> LINDA: Linda.
>> DAVID MALAN: Linda.
Y así, ¿qué hacemos ahora que tenemos una lista de tamaño de 1?
>> AUDIENCIA: Retorno.
>> DAVID MALAN: Cuidado.
Volvemos primero, y ahora el tercero paso - y si me tipo de representarlo por
que abarca los dos asientos ahora, ahora yo tienen que fusionar estos dos elementos.
Así que ahora, lamentablemente, los elementos están fuera de orden.
Pero ahí es donde el proceso de fusión empieza a ser convincente.
>> Así que si ustedes pudieran ponerse de pie por sólo un momento, voy a necesitar, en un
momento, con el paso detrás de su silla.
Y si Linda, porque es 2 menor que 4, ¿por qué no
vienes por primera vez?
Quédate ahí.
Así que Linda, tú vienes alrededor primero.
>> Ahora, en realidad, si es sólo un arreglo pudiéramos moverla en tiempo real
desde esta silla a este lugar.
Así que imaginen que tuvo alguna constante número de pasos 1.
Y ahora -
pero tenemos que poner en el primer lugar aquí.
>> Y ahora si pudiera entrar en razón, así, vamos a
estar en lugar de dos.
Y a pesar de esto se siente como si fuera tomar un tiempo, lo que es bueno ahora es
que la mitad izquierda de la medio izquierdo está ordenada ahora.
Entonces, ¿cuál era el siguiente paso, si ahora retroceder aún más en la historia?
>> AUDIENCIA: Mitad derecha.
>> DAVID MALAN: Ordene la mitad derecha.
Así que ustedes tienen que hacer esto, también.
Así que si usted puede ponerse de pie por un momento?
¿Y cuál es tu nombre?
>> JESS: Jess.
>> DAVID MALAN: Jess.
OK, así que Jess es ahora la izquierda la mitad de la mitad derecha.
Y por eso ella es una lista de tamaño 1.
Ella obviamente ordenada.
Y tu nombre?
>> MICHELLE: Michelle.
>> DAVID MALAN: Michelle obviamente una lista de tamaño 1.
Ella ya está solucionado.
Así que ahora sucede la magia, el proceso de fusión.
Entonces, ¿quién va a venir primero?
Obviamente Michelle.
Así que si pudieras venir a la vuelta.
El espacio que tenemos disponible para ella ahora es justo detrás de esta silla aquí.
Y ahora si pudiera volver, así, ahora tenemos, para ser claros, dos
mitades, cada una de tamaño 2 -
y simplemente por el amor de la representación, si podría hacer un poco de un espacio -
una mitad izquierda aquí, uno medio aquí.
>> Rebobinar aún más en la historia.
Lo que paso es el siguiente?
>> AUDIENCIA: Combinar.
>> DAVID MALAN: Así que ahora tenemos que fusionar.
Así que bien, así que ahora, gracias a Dios, que nos simplemente liberado cuatro sillas.
Para ello hemos utilizado el doble de memoria, pero podemos dar oscilando entre
las dos matrices.
Así que el número está por venir primero?
Así que Michelle, obviamente.
Así que ven alrededor y tomar su asiento aquí.
Y a continuación, el número 2 es, obviamente, siguiente, por lo que vienen aquí.
Número 4, número 6.
Y de nuevo, a pesar de que hay una poco de caminar involucrados,
Realmente, estos podrían ocurrir al instante, moviendo uno -
Bien, bien jugado.
>> [Risas]
>> DAVID MALAN: Y ahora estamos en muy buena forma.
La mitad izquierda de la entera de entrada ya ha sido solucionado.
Muy bien, por lo que estos chicos tenía la ventaja de mi -
¿cómo se terminan todas las chicas de la a la izquierda y todos los chicos de la derecha?
>> Aceptar, por lo que a su vez chicos ahora.
Así que no voy a caminar a través de estos pasos.
Vamos a ver si somos capaces de volver a aplicar la misma pseudocódigo.
Si quieres seguir adelante y ponerse de pie, y ustedes, te voy a dar el micrófono.
A ver si no se puede replicar lo que acabamos de hacer aquí en la
otro extremo de la lista.
¿Quién tiene que hablar en primer lugar, basado en el algoritmo?
Así que explique lo que está haciendo antes de usted hace cualquier movimiento del pie.
>> ALTAVOZ 1: Muy bien, entonces ya Yo soy la mitad izquierda de la
medio izquierdo, vuelvo.
¿Cierto?
>> DAVID MALAN: Good.
>> ALTAVOZ 1: Y entonces -
>> DAVID MALAN: ¿Quién hace el micro pase a la siguiente?
>> ALTAVOZ 1: número siguiente.
>> ALTAVOZ 2: Así que estoy en la mitad derecha de la mitad izquierda de la
medio izquierdo, y vuelva.
>> DAVID MALAN: Good.
Volverá.
¿Y ahora qué es lo que sigue para ustedes dos?
>> ALTAVOZ 2: Queremos ver quién es el más pequeño.
>> DAVID MALAN: Exactamente.
Queremos combinar.
El espacio que vamos a utilizar para combinar que en, aunque son
obviamente ya ordenados, vamos para seguir el mismo algoritmo.
Entonces, ¿quién va en la espalda por primera vez?
Así 3, y luego 7.
Y ahora el micrófono va a estos chicos, ¿de acuerdo?
>> ALTAVOZ 3: ¿Así que soy la mitad derecha de la medio izquierdo, y mi n es menor que
1, así que sólo voy a pasar -
>> DAVID MALAN: Good.
>> ALTAVOZ 4: Yo soy la mitad derecha de la mitad derecha de la mitad derecha, y estoy
También una persona, así que estoy va a volver.
Así que ahora nos fusionamos.
>> ALTAVOZ 3: Así que volvemos.
>> DAVID MALAN: ¿Así que ir a la parte trasera.
Así 5 va primero, a continuación, 8.
Y ahora la audiencia, que es la paso que tenemos que ahora rebobinar
de nuevo en nuestras mentes?
>> AUDIENCIA: Combinar.
>> DAVID MALAN: La fusión de la mitad izquierda y derecha la mitad de la mitad izquierda originales.
Así que ahora -
y acaba de dejar esto en claro, hacer un poco de espacio
entre ustedes dos.
Así que ahora que es las dos listas, izquierda y derecha.
Entonces, ¿cómo ahora fusionamos ustedes en la primera fila de asientos de nuevo?
>> 3 va primero.
Luego 5, obviamente.
Luego 7, y ahora 8.
Bueno, y ahora que somos?
>> AUDIENCIA: No realizado.
>> DAVID MALAN: No realizado, porque Obviamente, hay un paso restante.
Pero, de nuevo, la razón por la que estoy usando esta la jerga como "rebobinar en su mente,"
es porque eso es realmente lo que está sucediendo.
Estamos pasando por todos estos pasos, pero estamos especie de pausa para una
momento, el buceo profundo en el algoritmo, haciendo una pausa por un momento,
buceo más profundo en el algoritmo, y ahora tenemos que retroceder casi en nuestra
mentes y deshacer todas estas capas que hemos especie de puesta en espera.
>> Así que ahora tenemos dos listas de tamaño 4.
Si ustedes pudieran ponerse de pie una vez más y hacer un poco de espacio para
dejar claro que esta es la izquierda la mitad de la original, la
mitad derecha de la original.
¿Quién es el primer número que tenga que tirar en la parte de atrás?
Michelle, por supuesto.
>> Por eso, pusimos Michelle aquí.
¿Y quién tiene el número 2?
Número 2 viene en la parte posterior también.
Número 3?
Excelente.
Número 4, número 5, número 6, número 7, y el número 8.
>> Bien, así que me sentí como un montón de pasos, seguro.
Pero ahora vamos a ver si no podemos confirmar tipo de intuitivamente que este
algoritmo fundamental, especialmente en lo que n se hace muy grande, como hemos visto
con las animaciones, es fundamentalmente más rápido.
Así que yo reclamo este algoritmo, en el peor de los casos caso e incluso en el mejor de los casos,
es gran O de n veces log n.
Es decir, hay algún aspecto de este algoritmo que toma n pasos, pero
hay otro aspecto en algún lugar esa iteración, que bucle, que
tiene registro de n pasos.
¿Podemos poner nuestro dedo en lo que los dos números se refieren?
Bueno, donde -
¿dónde el micrófono ir?
>> ALTAVOZ 1: ¿El log n ser nosotros romper en dos -
dividiendo por dos, esencialmente.
>> DAVID MALAN: Exactamente.
Cada vez que vemos en cualquier algoritmo de este modo ahora, no ha habido este patrón de
dividir, dividir, dividir.
Y se reduce típicamente a algo que es
logarítmica, log base 2.
Pero podría realmente ser cualquier cosa, pero log base 2.
>> Ahora ¿qué pasa con el n?
Puedo ver que tipo de que dividimos chicos - que haya dividido, dividido ti,
que divide, que dividido.
¿De dónde viene el final viene?
>> Así que es la fusión.
Debido a pensar en ello.
Cuando combina ocho personas juntas, por el que la mitad de ellos son un conjunto de cuatro
y la otra mitad son otra un conjunto de cuatro, ¿cómo ir
de hacer la fusión?
Bueno, ustedes hicieron que bastante intuitiva.
>> Pero si en vez hice un poco más metódicamente, podría haber señalado en
la primera persona de la izquierda con mi izquierda mano, apuntando a la persona más a la izquierda
de ese medio con mi mano derecha, y sólo posteriormente caminó a través de la
lista, señalando el elemento más pequeño cada vez, moviendo el dedo una y
el control como sea necesario en la lista.
Pero lo que es clave sobre esta fusión proceso es que estoy comparando estos pares
de los elementos.
Desde la mitad derecha y de la izquierda medio, estoy dando marcha atrás ni una sola vez.
>> Así la propia fusión está tomando no más de n pasos.
¿Y cuántas veces te tengo hacer que la fusión?
Bueno, no más de n, y acabamos de vio que con la fusión final.
Y por lo que si usted hace algo que toma log n pasos n veces, o viceversa,
que va a darnos n log n veces.
>> ¿Y por qué es esto mejor?
Bueno, si ya sabemos que log n es mejor que n - a la derecha?
Vimos en la búsqueda binaria, la guía de teléfonos ejemplo, log n era definitivamente
mejor que lineal.
Así que eso significa n veces log n es definitivamente mejor que n veces otra
n, AKA n al cuadrado.
Y eso es lo que en última instancia sentimos.
>> Así que gran aplauso, si pudiéramos, para estos chicos.
>> [Aplausos]
>> DAVID MALAN: ¿Y sus regalos de despedida - guardéis los números,
si usted desea.
Y su regalo de despedida, como siempre.
Ah, y le enviaremos el material de archivo, Michelle.
Gracias.
Está bien.
Podrá disfrutar de una bola de la tensión.
>> Y déjame tire hacia arriba, mientras tanto, nuestro amigo Rob Bowden para ofrecer
algo diferente perspectiva sobre esto, ya que se puede pensar en estos
pasos que suceden de forma un tanto diferente manera.
De hecho, la puesta a punto para lo que acerca de Rob para mostrarnos asume que hemos
ha hecho la división de la gran lista en ocho listas pequeñas,
cada uno de tamaño 1.
>> Así que estamos cambiando el pseudocódigo un poco sólo para obtener una especie de en el
idea central de cómo funciona la fusión.
Pero el tiempo de ejecución de lo está a punto de hacer es todavía
va a ser la misma.
Y otra vez, la puesta a punto aquí es que él es comenzado con ocho listas de tamaño 1.
Así que te has perdido la parte donde él es realmente se hace el registro de n, log n, log n
divisoria de la entrada.
>> [REPRODUCCIÓN DE VÍDEO]
>> -Esto es todo por el paso uno.
Para el segundo paso, en varias ocasiones combinar pares de listas.
>> DAVID MALAN: Hm.
Sólo audio está llegando fuera de mi ordenador.
Vamos a intentar de nuevo.
>> -Sólo tiene que elegir de forma arbitraria que - Ahora tenemos cuatro listas.
Aprenda antes.
>> DAVID MALAN: Eso es.
>> -La fusión de 108 y 15, se acaba con la lista de 15, 108.
La fusión de 50 y 4, nos terminar con 4, 50.
La fusión de 8 y 42, que terminar con 8, 42.
Y la fusión de 23 y 16, que terminar con 16, 23.
>> Ahora todas nuestras listas son de tamaño 2.
Observe que cada uno de los cuatro listas se ordenan.
Así que podemos comenzar la fusión pares de listas de nuevo.
La fusión de 15 y 108 y 4 y 50, nos saca primero la 4, la 15, entonces
el 50, entonces el 108.
La fusión de 8, 42 y 16, 23, primero echamos el 8, a continuación, la 16, entonces el 23,
a continuación, la 42.
>> Así que ahora tenemos sólo dos listas de tamaño 4, cada uno de los cuales está ordenada.
Así que ahora nos fusionamos estas dos listas.
En primer lugar, tomamos el 4, luego tomamos el 8, luego tomamos el 15, luego 16, luego
23, a continuación 42, a continuación 50, a continuación, 108.
>> [VIDEO PLAYBACK FIN]
>> DAVID MALAN: De nuevo, aviso, que nunca tocado un vaso dado más de una vez
después de avanzar más allá de ella.
Así que nunca repetir.
Así que siempre se está moviendo hacia un lado, y ahí es donde tenemos nuestro n.
>> ¿Por qué no me deja subo una animación que hemos visto antes, pero esta vez
centrarse sólo en la combinación de tipo.
Déjame ir por delante y el zoom en esto aquí.
Primero permitirme elegir una entrada al azar, magnificar esto, y usted puede ver una especie de
lo que tomamos por sentado, antes, fusionar especie está haciendo realidad.
>> Así cuenta de que usted consigue estas mitades o estos cuartos o en estos octavos de la
problema que, de repente, empezar a tomar buena forma.
Y, por último, que se ve en el final que bam,
todo se fusionaron.
>> Así que estos son sólo tres diferentes toma en la misma idea.
Pero la idea clave, al igual que dividir y vencer en la primera clase,
fue que decidimos dividir de alguna manera el problema en algo grande, en
algo especie de idéntico espíritu, pero más pequeña y más pequeña y más pequeña
y más pequeño.
>> Ahora otra divertida forma de una especie de pensar acerca de estos, a pesar de que no es
va a dar el mismo intuitiva comprensión, es
la siguiente animación.
Así que este es un video que alguien armó la asociada diferente
sonidos con las diversas operaciones para ordenación por inserción, por la combinación de clase y
por un par de los demás.
Así que en un momento, me voy a pegar en Reproducir.
Se trata de un minuto de duración.
Y a pesar de que todavía se puede ver la patrones pasando, esta vez se puede
También escuchar cómo estos algoritmos son realizar de manera diferente y con
algo diferentes patrones.
>> Esta es la ordenación por inserción.
>> [REPRODUCCIÓN DE TONOS]
>> DAVID MALAN: De nuevo está tratando para insertar cada elemento
en donde debe estar.
Se trata de una especie de burbuja.
>> [REPRODUCCIÓN DE TONOS]
>> DAVID MALAN: Y usted puede sentir una especie de lo relativamente poco trabajo que está haciendo
en cada paso.
Esto es lo que suena como el aburrimiento.
>> [REPRODUCCIÓN DE TONOS]
>> DAVID MALAN: Se trata de una especie de selección, donde seleccionamos el elemento que queremos por
pasando una y otra vez y otra vez y ponerlo al principio.
>> [REPRODUCCIÓN DE TONOS]
>> DAVID MALAN: Esto se merge sort, que usted realmente puede comenzar a sentir.
>> [REPRODUCCIÓN DE TONOS]
>> [Risas]
>> DAVID MALAN: Algo llamado gnome especie, que no hemos mirado.
>> [REPRODUCCIÓN DE TONOS]
>> DAVID MALAN: Así que vamos a ver, ahora, distraído mientras espero es por el
música, si puedo meter un poco poco de matemáticas aquí.
Así que hay una cuarta forma de que podamos pensar en lo que significa esto
funciones para ser más rápido que los que hemos visto antes.
Y si vas a venir en el curso de un fondo de matemáticas, que
realmente saben tal vez ya que puede abofetear a un término en esta técnica -
a saber, la recursión, una función que de alguna manera se hace llamar.
>> Y una vez más, recordemos que fusionar especie pseudocódigo era recursivo, en el sentido
que uno de los pasos de combinación de ordenar era llamar especie -
que es, en sí.
Pero, por suerte, porque nos mantenían llamando a ordenar o combinar especie,
específicamente, en una más pequeña y más pequeña y una lista más pequeña, al final
tocado fondo, gracias a lo que llamaremos un caso base, el caso no modificable que
dijo que si la lista es pequeña, menos de 2 en ese caso, simplemente volver inmediatamente.
Si no tuviéramos ese caso especial, el algoritmo haría nunca tocar fondo,
y que sería de hecho entrar en un bucle infinito de verdad para siempre.
>> Pero supongamos que queremos ahora poner algunos números en esta, de nuevo, usando N
como el tamaño de la entrada.
Y yo quería preguntarte, ¿cuál es el tiempo total involucrado en
funcionando fusionar tipo?
O en términos más generales, ¿cuál es el costo de la misma en el tiempo?
>> Bueno, es muy fácil de medir eso.
Si n es menor que 2, el tiempo involucrado en la clasificación de n elementos,
donde n es 2, es 0.
Porque simplemente devolvemos.
No hay trabajo por hacer.
Ahora podría decirse que, tal vez es un paso o dos medidas para averiguar la cantidad de
trabajo, pero es lo suficientemente cerca de 0 que Yo sólo voy a decir que no es el trabajo
requerido si la lista es tan pequeño a ser poco interesante.
>> Pero este caso es interesante.
El caso recursivo fue la rama de el pseudocódigo que dijo otra cosa, una especie
la mitad izquierda, ordenar el derecho medio, combinar las dos mitades.
Ahora ¿por qué esta expresión representar a ese gasto?
Bueno, T de n sólo significa la tiempo para ordenar n elementos.
Y a continuación, en el lado derecho de la signo igual allí, la T de n divide
por 2 se refiere al costo de lo que?
Clasificación de la mitad izquierda.
El otro T de n dividido por 2 es presumiblemente en referencia al coste de
ordenar la mitad derecha.
>> Y entonces el más n?
Es la fusión.
Porque si usted tiene dos listas, una de tamaño n sobre 2 y otra de tamaño n
más de 2, tiene que tocar la esencia cada uno de esos elementos, al igual que Rob
tocado cada una de las copas, y apenas como hemos señalado en cada uno de los
voluntarios en el escenario.
Así que n es el gasto de la fusión.
>> Ahora, por desgracia, esta fórmula También es en sí mismo recursiva.
Así que si la pregunta, si n es, por ejemplo, 16, si hay 16 personas en el escenario
o 16 tazas en el video, el número de total de pasos toma para ordenarlos
con la combinación de clase?
En realidad no es una respuesta obvia, porque ahora usted tiene que ordenar de
recursivamente responder a esta fórmula.
>> Pero está bien, porque permítanme proponer lo que hacemos lo siguiente.
El tiempo necesario para ordenar 16 personas o 16 copas va a ser representado
generalmente como T de 16.
Pero eso es igual, de acuerdo con nuestra fórmula anterior, 2 veces la cantidad
de tiempo que se necesita para ordenar 8 tazas de más 16.
Y de nuevo, más 16 es el momento de unir, y los dos tiempos T de 8 es el
tiempo para ordenar a la mitad izquierda y la mitad derecha.
>> Pero de nuevo, esto no es suficiente.
Tenemos que bucear más profundo.
Esto significa que tenemos que responder a la pregunta, ¿cuál es T de 8?
Bueno T de 8 está a sólo 2 tiempos T de 4 y de 8.
Bueno, ¿cuál es T, de 4?
T, de 4 a solo 2 veces T de 2 más 4.
Bueno, ¿cuál es T de 2?
T de 2 se encuentra a sólo 2 veces T de 1 más 2.
>> Y de nuevo, estamos como llegar atrapado en este ciclo.
Pero está a punto de golpear ese así llamado caso base.
Porque lo que es T, de 1, nos decimos?
0.
Así que ahora, finalmente, podemos trabajar hacia atrás.
>> Si T de 1 es 0, ahora puedo subir un alinear a este tipo de aquí, y no puedo
enchufar 0 para T de 1.
Así que eso significa que es igual a 2 veces cero, conocido de otra manera como 0, más 2.
Y por lo que toda esa expresión es 2.
>> Ahora bien, si me tomo el T de 2, cuya respuesta es 2, conéctelo a la línea media, T
de 4, eso me da 2 veces 2 plus 4, por lo que 8.
Pues si yo conecto a 8 a la anterior line, que me da 2 veces 8, 16.
Y si luego seguimos que con la 24, la adición de 16, por fin tenemos un
valor de 64.
>> Ahora que en sí misma especie de habla nada a la notación n, la
gran O, la omega que hemos estado hablando.
Pero resulta que el 64 es de hecho 16, el tamaño de la entrada,
log base 2 de 16.
Y si esto es un poco extraño, simplemente Piense de nuevo, y se va a volver
que es muy probable.
Si esto es log base 2, es como 2 elevada a la que le da 16?
Oh, eso es 4, por lo que es 16 veces 4.
>> Y de nuevo, no es un gran problema si este es una especie de vago recuerdo ahora.
Pero por ahora, asumir la fe que el 16 de registro 16 es 64.
Y así, de hecho, con este simple cordura comprobar, hemos confirmado -
pero no demostrado formalmente -
que el tiempo de ejecución de merge especie es de hecho n log n.
>> Así que no está mal.
Es definitivamente mejor que el algoritmos que hemos visto hasta ahora, y
es porque hemos aprovechado, uno, una técnica llamada recursión.
Pero más interesante que eso, que noción de dividir y conquistar.
Una vez más, verdaderamente semana 0 cosas que incluso ahora se repite en un
manera más convincente.
>> Ahora un poco de ejercicio divertido, si usted tiene nunca hecho esto - y es probable que
no tendría, pues una especie de normalidad la gente no piensa hacerlo.
Pero si voy a google.com y si Quiero aprender algo acerca de
recursividad, Intro.
>> [Risas]
[Más risas]
DAVID MALAN: Bad broma lentamente extienda.
[Risas]
DAVID MALAN: Por si acaso, que está ahí.
Yo no lo deletree mal, y ahí está la broma.
Está bien.
Explicar a la gente a tu lado si bastante no ha hecho clic en el momento.
Pero recursión, de manera más general, se refiere para el proceso de una llamada función
en sí, o más en general, la división de un problema en algo que puede ser
resuelto por partes resolviendo idéntica problemas de representación.
>> Bueno, vamos a cambiar los engranajes sólo por un momento.
Nos gusta para terminar en ciertos melodramas, así que vamos a empezar a establecer
el escenario, durante varios minutos, en una idea muy simple -
el de intercambio de dos elementos, ¿verdad?
Todos estos algoritmos hemos estado hablando de los últimos dos
conferencias implican algún tipo de intercambio.
Hoy en día se visualizó por ellos conseguir arriba de sus sillas y
caminando por ahí, pero en el código, lo haríamos simplemente tomar un elemento de un array
y plop en otro.
>> Entonces, ¿cómo hacemos para hacer esto?
Bueno, déjame seguir adelante y escribir un programa rápido aquí.
Voy a seguir adelante y hacer esto como la siguiente.
Llamemos a esto -
¿qué queremos llamar este?
>> En realidad, no.
Permítanme rebobinar.
Yo no quiero hacer eso Cliffhanger todavía.
Será estropear la diversión.
Vamos a hacer esto en su lugar.
>> Supongamos que yo quiero escribir un poco programa y que ahora abarca este
idea de recursividad.
Yo como que tengo delante de mí mismo allí.
Voy a hacer lo siguiente.
>> Primero, una rápida incluyen de io.h estándar, así como incluir de cs50.h.
Y luego voy a seguir adelante y declarar void main int
en la forma habitual.
Me di cuenta de que he mal llamado el archivo, por lo que permítanme añadir una. extensión c aquí, así
que podemos compilarlo correctamente.
Inicie esta función.
>> Y la función que quiero escribir, bastante simplemente, es la que pide a la
usuario un número y luego se suma todos los números entre los que
número y, por ejemplo, 0.
Así que primero voy a seguir adelante y declarar int n.
A continuación copio un código que que hemos utilizado durante un tiempo.
Mientras que algo es verdadero.
Voy a volver a eso en un momento.
>> ¿Qué quiero hacer?
Quiero decir printf positivo entero por favor.
Y luego voy a dicen que n se hace llegar int.
Así que de nuevo, un poco de código repetitivo que hemos utilizado antes.
Y yo voy a hacer esto mientras que n es menor que 1.
Así que esto asegurará que el usuario me da un número entero positivo.
>> Y ahora voy a hacer lo siguiente.
Quiero sumar todos los números entre 1 y y n, o 0 y n,
equivalente, para obtener la suma total.
Así el símbolo Sigma grande que se puede recordar.
Así que voy a hacer esto por primera convocatoria una función llamada Sigma,
pasándolo n, y luego me voy a printf decir, la respuesta está ahí.
>> Así que en resumen, lo entiendo y int del usuario.
Me aseguro de que es positivo.
Declaro una respuesta variable llamada de tipo int y almacenar en ella el retorno
valor de sigma, pasando n como entrada.
Y luego imprimo esa respuesta.
>> Desafortunadamente, a pesar de que los sonidos sigma como algo que pudiera estar en
el archivo math.h, su declaración, en realidad no es.
Así que eso está bien.
Puedo aplicar esto a mí mismo.
Voy a implementar una función llamada sigma, y ​​que va a tomar un
parámetro -
vamos a llamarlo m, justo por lo que es diferente.
Y luego aquí, yo voy a decir, bueno, si m es inferior a 1 - esto es un
programa muy interesante.
Así que voy a seguir adelante y volver inmediatamente 0.
Simplemente no tiene sentido sumar todos los números entre 1 y m si m
es en sí mismo 0 o negativo.
>> Y luego voy a seguir adelante y hacer esto muy iterativa.
Voy a hacer este tipo de la vieja escuela, y yo voy a seguir adelante
y decir que voy a declarar una suma a ser 0.
Entonces voy a tener un bucle de int -
y déjame hacer para que coincida con nuestra código de distribución, por lo que tiene una copia
en el hogar. int i Obtiene 1 en un máximo de i es menor que o igual a m.
i plus plus.
Y luego dentro de este ciclo for -
ya casi estamos allí -
suma se suma más 1.
Y luego voy a devolver la suma.
>> Así que hice esto de manera rápida, bastante cierto.
Pero, de nuevo, la función principal es bastante sencillo, basado en el código que hemos
escrito hasta la fecha.
Utiliza el bucle dual para conseguir un resultado positivo int del usuario.
Luego paso que int a una nueva función llamado sigma, llamándolo, de nuevo, n.
Y guardo el valor de retorno, la respuesta Del cuadro negro en la actualidad
conocido como Sigma, en una variable llamada respuesta.
Luego lo imprimo.
>> Si ahora seguimos la historia, cómo se implementa sigma?
Propongo para implementar de la siguiente manera.
En primer lugar, un poco de comprobación de errores para asegurarse de que el usuario no está
jugando conmigo y pasando otros negativos o valor 0.
Entonces me declaro una variable llamada suma y ponerlo a 0.
>> Y ahora empiezo a pasar de iguales i 1 todo el camino hasta e incluyendo m,
porque quiero incluir toda la los números de uno a través de m, inclusive.
Y dentro de este bucle, acabo de hacer suma consigue lo que sea ahora, además de la
valor de i.
Además, el valor de i.
>> Como acotación al margen, si no has visto esta antes, hay un poco de azúcar sintáctico
para esta línea.
Puedo reescribir esto como plus iguala i, sólo para salvarme a mí mismo unas pocas teclas
y mirar un poco más fresco.
Pero eso es todo.
Es funcionalmente lo mismo.
>> Por desgracia, este código es no va a compilar todavía.
Si ejecuto make sigma 0, ¿cómo soy Me va a gritar en?
¿Qué va a le gusta?
>> AUDIENCIA: [inaudible].
>> DAVID MALAN: Sí, yo no declaro parte superior de la función, ¿no?
C es un poco estúpido, ya que sólo Hace lo que usted diga que haga, y usted
hay que hacerlo en ese orden.
Y así, si golpeo Ingrese aquí, yo voy a recibirá una advertencia sobre sigma implícita
declaración.
>> Oh, no es un problema.
Puedo subir a la cima, y ​​puedo por ejemplo, está bien, espera un minuto.
Sigma es una función que devuelve un entero y se espera una
int como entrada, punto y coma.
O podría poner toda la función por encima de principal, pero en general, me gustaría
Recomiendo en contra de eso, porque es agradable tener siempre principal en la parte superior para
usted puede bucear en derecho y saber lo que un El programa de hacer mediante la lectura principal primero.
>> Así que ahora quiero borrar la pantalla.
Remake sigma 0.
Todo parece ir a la salida.
Déjame correr sigma 0.
Entre Positivo.
Voy a darle el número 3 para que sea sencillo.
Así que me debe dar 3 más 2 más 1, por lo que 6.
Entrar, y de hecho me da 6.
>> Puedo hacer algo más grande -
50, 12, 75.
Así como una tangente, yo voy a hacer algo ridículo como una muy grande
número, Oh, que realmente funcionó -
eh, yo no creo que eso sea correcto.
Vamos a ver.
Vamos realmente meterse con él.
>> Eso es un problema.
¿Qué está pasando?
El código no es tan malo.
Todavía es lineal.
Silbar es un buen efecto, sin embargo.
¿Qué está pasando?
>> No estoy seguro si lo escuché.
Así que resulta - y esto es como un aparte.
Este no es el núcleo de la idea de recursividad.
Resulta que, porque yo estoy tratando de representan un número tan grande, la mayoría
probablemente está siendo mal interpretado por C como un número no positiva,
pero el número negativo.
>> No hemos hablado de esto, pero es Resulta que hay números negativos
en el mundo, además de a números positivos.
Y el medio por el cual usted puede representar un número negativo
en esencia, es decir, se utiliza uno poco especial para indicar
positivo en negativo.
Es un poco más complejo que eso, pero esa es la idea básica.
>> Así que, lamentablemente, si C es uno confuso de esos bits como en realidad lo que significa,
oh, este es un número negativo, mi lazo aquí, por ejemplo, es en realidad nunca
va a terminar.
Así que si yo fuera realmente algo de impresión una y otra vez, lo haríamos
ver un montón.
Pero, de nuevo, este es el punto.
Esto es en realidad una especie de curiosidad intelectual que vendremos
de nuevo a la larga.
Pero por ahora, esto es una correcta aplicación si suponemos que el
usuario proporcionará ints que encajan dentro de ints.
>> Pero yo sostengo que este código, francamente, que se podría hacer mucho más sencilla.
Si la meta actual es tomar un número como m y sumar todos los
los números entre éste y 1, o por el contrario entre 1 y que, me dicen
que puedo pedir prestada esta idea de que fusionar ordenar tenido, que estaba teniendo un problema
de este tamaño y dividiéndolo en algo más pequeño.
Quizás no es un medio, pero más pequeño, pero de manera representativa del mismo.
La misma idea, pero un problema menor.
>> Así que estoy realmente - me deja guardar este archivo con un número de versión diferente.
Vamos a llamar a esta versión 1 en lugar de 0.
Y pretender que puedo realmente volver a implementar esto en este tipo de
endiablada manera.
>> Voy a dejar parte de su cuenta.
Voy a decir que si m es menor que o incluso igual a 0 -
Yo sólo voy a ser un poco más anal esta vez
con mi comprobación de errores -
Voy a seguir adelante y devolver 0.
Este es arbitraria.
Estoy simplemente decidiendo si el usuario me da un número negativo, estoy
devolviendo un 0, y que debería haber leído la documentación de más de cerca.
>> Otras ventas -
cuenta de lo que voy a hacer.
Else voy a volver m plus -
lo que es sigma de m?
Bueno, sigma de m + d menos 1, plus minus m 2, más menos 3 m.
Yo no quiero escribir todo eso a cabo.
¿Por qué no acaba de Punt?
Llame recursivamente a mí mismo con un poco más pequeño problema, punto y coma,
y lo llaman un día?
>> ¿Cierto?
Ahora aquí, también, se puede sentir o preocuparse que este es un bucle infinito que estoy
inducir, en el que me estoy poniendo en práctica Sigma llamando Sigma.
Pero eso es perfectamente correcto, porque yo pensado por delante un qué líneas añadidas?
>> AUDIENCIA: [inaudible].
>> DAVID MALAN: 23 a 26, que es mi condición if.
Porque lo bueno de la resta aquí, porque he guardado
entrega sigma problemas más pequeños, más pequeña problemas, más pequeña - no es
la mitad del tamaño.
Es sólo un pequeño paso más pequeño, pero eso está bien.
Debido a que con el tiempo, vamos a trabajar nuestro camino a 1 o 0.
Y una vez que llegamos a 0, sigma no es pasando a llamarse más.
Se va a volver inmediatamente 0.
>> Así que el efecto, si el viento esta especie de en su mente, es añadir m más
m menos 1, más m menos 2, más m menos 3, además de punto, punto, punto, m menos
m, con el tiempo que le da 0, y el efecto es en última instancia, para agregar todos los
estas cosas juntas.
Así que no tenemos, con la recursividad, resuelto el problema que nos
no podría resolver antes.
De hecho, la versión 0 de este, y cada problema hasta la fecha, ha sido solucionable
con sólo usar bucles o mientras bucles o construcciones similares.
>> Pero la recursividad, me atrevo a decir, nos da una manera diferente de pensar sobre
problemas, por lo que si podemos tomar un problema, dividirla de algo
algo grande en algo un tanto más pequeña, afirmo que podemos resolverlo
tal vez un poco más elegante en términos del diseño, con menos código,
y tal vez incluso resolver los problemas que lo haría ser más difícil, ya que finalmente va a
ver, la solución puramente de forma iterativa.
>> Pero el drama de suspenso que lo hice quiere dejar a nosotros en esta era.
Déjenme seguir adelante y abrir un archivo desde -
En realidad, me dejó ir y hacer esto muy rápido.
Déjame ir adelante y propongo el siguiente.
Entre el código de hoy es el archivo aquí.
Este de aquí, noswap.
>> Así que este es un pequeño programa que estúpido Saqué hasta que pretende hacer
el siguiente.
En principal, primero declara una int llamado x y le asigna
el valor de 1.
Entonces se declara un int y y asigna el valor 2.
Luego se imprime lo que x e y es.
Entonces dice: intercambio, punto punto punto.
>> Entonces se dice que está llamando a una función denominada swap, que pasa en x y
y, la idea de que es de esperar que x e y volverá
diferente, lo contrario.
Entonces reclamo cambió!
con un signo de exclamación.
Luego imprime xe y.
>> Pero resulta que esta misma simple demostración abajo
aquí es realmente buggy.
Aunque estoy declarando un temporal variable y poner temporalmente en una
, entonces yo estoy reasignando un valor de b -
que se siente razonable, porque he guardado una copia de un temporal en.
Entonces puedo actualizar b a la igualdad de lo que estaba en temp.
Este tipo de juego de la cáscara de mover un en B y B en una mediante el uso de este
medio-hombre llamado temp siente perfectamente razonable.
>> Pero yo sostengo que cuando ejecuto esta código, ya que voy a hacer ahora -
déjame ir adelante y pegarlo aquí.
Voy a llamar a este noswap.c.
Y como su nombre indica, este no es va a ser un programa correcto.
Hacer noswap. / No swap.
x es 1, y es 2, el intercambio, intercambiado.
x es 1, Y es 2.
Esto es un error fundamental, incluso aunque esto parece perfectamente
razonable para mí.
Y hay una razón, pero no estamos va a revelar la razón por el momento.
>> Por ahora el segundo melodrama que quería a dejar es esto, un
anuncio de tipos de bonos de descuento.
Nuestra innovación con los días finales de este año ha provocado un número no trivial
de preguntas, que era no nuestra intención.
La intención de estos bonos de descuento, por el que si lo haces parte del problema
establecer temprana, consiguiendo así un día adicional, fue realmente para ayudar a ustedes Ayuda
mismo comienzo temprano, más o menos de al incentivar usted.
Nos ayuda a distribuir la carga entre horario de oficina mejor para que
Es una especie de ganar-ganar.
>> Por desgracia, creo que mis instrucciones no han sido, hasta la fecha, muy clara, por lo que
Volví este fin de semana y actualizado la especificación en el más grande, más audaz para el texto
explicar las balas como estos.
Y para decirlo más públicamente, por De forma predeterminada, los boletines de problemas se deben Jueves
al mediodía, por el plan de estudios.
Si comienza temprano, terminando parte de el problema fijado para el miércoles a las 12:00
PM, la parte que se refiere a un cupón Código, la idea es que se puede extender
el plazo para la P fijó hasta el viernes.
Es decir, el bit de una pequeña parte de la P establecido en relación a lo que normalmente es el
mayor problema, y ​​usted compra usted mismo un día extra.
Una vez más, se pone a pensar acerca de el problema planteado, se llega a
las horas de oficina antes.
Pero el problema sigue siendo el código de cupón necesario, incluso si usted no los pongas.
>> Pero lo más convincente es la siguiente.
(ETAPA WHISPER) Y esas personas que salen temprano van a lamentarlo.
Como son las personas en el balcón.
Pido disculpas de antemano a la gente en el balcón por razones que serán
borrar en un momento.
>> Así que tenemos la suerte de tener uno de Ex becarios de enseñanza en la cabeza del CS50
una empresa llamada dropbox.com.
Ellos han donado generosamente un código aquí cupón para este espacio,
que es a partir de la habituales 2 gigabytes.
Así que lo que yo pensaba que íbamos a hacer en este nota final es hacer un poco de un sorteo,
por lo que en un momento, vamos a revelar el ganador y quién tiene un cupón
código que luego se puede ir a su sitio web, escribirlo, y listo, conseguir un
mucho más espacio Dropbox para su aparato y para sus archivos personales.
>> Y en primer lugar, que quiere participar en este dibujo?
Bien, ahora que lo hace aún más divertido.
La persona que recibe este 25 gigabytes código de descuento - que es mucho
más convincente que el difunto día ahora, tal vez -
es el que está sentado en la parte superior de un cojín del asiento por debajo de la cual hay
que el código de cupón.
Ahora puede mirar debajo el cojín del asiento.
>> [REPRODUCCIÓN DE VÍDEO]
>> -Uno, dos, tres.
>> [GRITA]
>> -Usted recibe un coche!
Usted consigue un coche!
>> DAVID MALAN: Veremos que el miércoles.
>> -Usted recibe un coche!
Usted consigue un coche!
>> DAVID MALAN: gente Balcón, vienen aquí abajo en la parte delantera,
donde tenemos extras.
>> -Todo el mundo tiene un coche!
Todo el mundo tiene un coche!
>> [VIDEO PLAYBACK FIN]
>> NARRADOR: En la próxima CS50 -
>> ALTAVOZ 5: Oh, Dios mío Dios mío Dios mío Dios mío caramba caramba caramba caramba caramba caramba -
>> [UKELELE JUEGOS]