>> [REPRODUCCIÓN DE MÚSICA]
>> PROFESOR: Muy bien.
Esto es CS50 y esto es Al final de la tercera semana.
Así que estamos aquí hoy, no en Sanders Teatro, en lugar de Weidner Biblioteca.
En el interior de los cuales es un estudio conocido como Hauser de estudio,
o mejor dicho Estudio H, o irán que decir-- si te gustó la broma,
en realidad es de compañero, Mark, en línea,
quien sugirió tanto a través de Twitter.
Ahora lo bueno de estar aquí en un estudio
es que estoy rodeado de estos de verde paredes, una pantalla verde o chromakey,
por así decirlo, lo que significa que CS50 de equipo de producción, sin yo saberlo
en este momento, podría ser poner más me cualquier parte del mundo,
Para bien o para mal.
>> Ahora lo que se avecina, establece problema dos es en sus manos para esta semana,
pero con el problema de establecer de tres esta semana que viene,
serás retado con el llamado juego de 15,
un viejo partido a favor de que se puede recordar que recibe
como un niño que tiene un montón de números que se pueden deslizar hacia arriba, abajo,
izquierda y derecha, y hay una brecha dentro del rompecabezas, en el que
puede deslizarse en realidad esas piezas del rompecabezas.
En última instancia recibe este rompecabezas en algún orden semi aleatoria,
y el objetivo es ordenarla, de arriba abajo,
izquierda a derecha, de un todo el camino a través de 15.
>> Desafortunadamente, la implementación tendrás a la mano
va a ser el software basado, no físicamente.
Usted está en realidad va a tener que escribir código con el que un estudiante o usuario lata
jugar el juego de los 15.
Y de hecho, en el hacker edición del juego de 15,
usted será un desafío para poner en práctica, no sólo el juego de esta vieja escuela
juego, sino más bien la resolución de ello, la aplicación de modo de dios,
por así decirlo, que de hecho resuelve el rompecabezas para el ser humano,
poniendo a su pista, después de pista, después toque.
Así que más en que la próxima semana.
Pero eso es lo que nos espera.
>> Por ahora recordar que a principios de esta semana hemos tenido este melodrama, si se quiere,
por lo que el mejor que estábamos haciendo la clasificación sabia era una cota superior de grande o de n
al cuadrado.
En otras palabras, ordenamiento de burbuja, ordenación por selección, ordenación por inserción,
todos ellos, mientras diferente en su aplicación,
degenerado en un cuadrado n corriendo tiempo en el peor de los casos.
Y por lo general, suponemos que el peor de los casos para la clasificación
es uno que sus entradas son completamente al revés.
Y, de hecho, le tomó unos cuantos pasos para poner en práctica cada uno de los algoritmos.
>> Ahora en el final de la clase revocatorio, comparamos ordenamiento de burbuja
contra la ordenación por selección contra otro que llamamos de combinación de clase en el momento,
y yo propongo que está tomando ventaja de una lección de la semana
cero, divide y vencerás.
Y de alguna manera lograr algún tipo de logarítmica tiempo de funcionamiento en última instancia,
en lugar de algo eso es puramente cuadrática.
Y no es bastante logarítmica, que es un poco más que eso.
Pero si usted recuerda de la clase, era mucho, mucho más rápido.
Echemos un vistazo a donde lo dejamos.
>> Burbuja tipo contra la selección tipo de combinación frente especie.
Ahora están todos corriendo, en teoría, al mismo tiempo.
La CPU está funcionando a la misma velocidad.
Pero se puede sentir lo aburrido esto va muy rápidamente para convertirse,
y la rapidez, cuando inyectamos un poco de algoritmos semana de cero,
podemos acelerar las cosas.
>> Así especie marca se ve increíble.
¿Cómo podemos aprovechar que, con el fin para ordenar los números más rápidamente.
Bueno vamos a pensar en volver a un ingrediente que
tenía de vuelta en semanas cero, el de buscando a alguien en una guía telefónica,
y recordar que el pseudocódigo que propusimos,
a través del cual podemos encontrar alguien como Mike Smith,
parecía un poco algo como esto.
>> Ahora echa un vistazo en particular, en la línea 7 y 8, y 10 y 11,
que inducen ese bucle, en el que mantuvimos que se remonta a la línea 3 de nuevo, y otra vez,
y otra vez.
Pero resulta que podemos ver este algoritmo, aquí en pseudocódigo,
un poco más de manera integral.
De hecho, lo que estoy buscando por lo que aquí en la pantalla,
es un algoritmo para la búsqueda de Mike Smith, entre un conjunto de páginas.
Y de hecho, podríamos simplificar este algoritmo en esas líneas 7 y 8,
y 10 y 11 a sólo decir esto, que he presentado aquí en amarillo.
En otras palabras, si Mike Smith es anterior en el libro,
no necesitamos especificar paso a paso ahora cómo ir a buscarlo.
No tenemos que especificar para volver a la línea 3,
¿Por qué no simplemente en su lugar, por ejemplo, más en general,
buscar Mike en el media izquierda del libro.
>> A la inversa, si Mike es en realidad más adelante en el libro,
¿por qué no acabamos de citar búsqueda fin de la cita Mike en la mitad derecha del libro.
En otras palabras, ¿por qué no lo hacemos sólo especie de batea a nosotros mismos diciendo:
buscar Mike en este subconjunto del libro,
y dejar que nuestros actuales algoritmo que nos diga
cómo buscar Mike en que la mitad izquierda del libro.
En otras palabras, nuestra algoritmo funciona ya sea
una libreta de teléfonos de este espesor, de esta espesor, o cualquier espesor que sea.
Así que lo que podamos de forma recursiva definir este algoritmo.
En otras palabras, en el pantalla de aquí, es un algoritmo
para la búsqueda de Mike Smith entre las páginas de un libro de teléfono.
Así, en la línea 7 y 10, vamos a a decir exactamente eso.
Y utilizo este término un momento Hace, y de hecho, la recursión
es la palabra de moda, por ahora, y es este proceso
de hacer algo cíclico de alguna manera utilizando el código que ya tiene,
y decir que es nuevo, y otra vez, y otra vez.
Ahora que va a ser importante que de alguna manera inferior
fuera, y no hagas eso infinitamente largo.
De lo contrario, vamos a tienen de hecho un bucle infinito.
Pero vamos a ver si podemos pedir prestada esta idea de un recursividad, hacer algo nuevo
y una y otra vez, para resolver el problema de clasificación a través de combinación
Ordena, toda la manera más eficiente.
>> Así que le doy combinar tipo.
Echemos un vistazo.
Así que aquí es pseudocódigo, con que podríamos aplicar la clasificación,
el uso de este algoritmo llamado fusión tipo.
Y es simplemente esto.
En la entrada de n elementos, en otras palabras, si usted es
dada n elementos y números y cartas o lo que la entrada es,
si te dan n elementos, si n es menor que 2, simplemente volver.
¿Correcto?
Porque si n es menor que 2, que significa que mi lista de elementos
es cualquiera de tamaño 0 o 1, y en ambos casos triviales,
la lista ya está ordenado.
Si no hay una lista, es ordenada.
Y si hay una lista de longitud 1, es obviamente ordenado.
Así que el algoritmo sólo necesita realmente hacer algo interesante,
si tenemos dos o más elementos dados a nosotros.
Así que echemos un vistazo a la magia entonces.
Else ordenar la mitad izquierda de los elementos, a continuación, ordenar la mitad derecha de los elementos,
luego fusionar las mitades ordenados.
Y lo que es clase de mente flexión aquí, es que realmente no me
parecen que han dicho nada todavía, ¿verdad?
Todo lo que he dicho es, dada una lista de n elementos, ordenar la mitad izquierda,
entonces la mitad derecha, a continuación, fusionar las mitades ordenados,
pero ¿dónde está el ingrediente secreto real?
¿Dónde está el algoritmo?
Pues resulta que esas dos líneas primero, ordenar la izquierda de la mitad de los elementos,
y tipo adecuado medio de elementos, son llamadas recursivas, por así decirlo.
>> Después de todo, en este punto en el tiempo, ¿tengo
un algoritmo con el cual ordenar un montón de elementos?
Sí.
Es justo aquí.
Es aquí en la pantalla, y así que puedo usar ese mismo conjunto de medidas
para ordenar la mitad izquierda, como puedo la mitad derecha.
Y, en efecto, de nuevo, una y otra vez.
Así que de alguna manera u otra, y que pronto ver esto, la magia de la combinación de tipo
está incrustado en ese mismo definitiva línea, la fusión de las mitades ordenadas.
Y eso parece bastante intuitivo.
Usted toma dos mitades, y tú, de alguna manera, unirlos,
y vamos a ver esto concretamente en un momento.
>> Pero este es un algoritmo completo.
Y vamos a ver exactamente por qué.
Bueno supongamos que nos dan estos mismos ocho elementos aquí en la pantalla, uno
a través de ocho, pero son con el fin aparentemente al azar.
Y el objetivo que nos ocupa es para ordenar estos elementos.
Bueno, ¿cómo puedo ir sobre hacerlo utilizando, de nuevo,
ordenamiento por mezcla, según este pseudocódigo?
Y de nuevo, arraigar esto en su mente, sólo por un momento.
El primer caso es bastante trivial, si es menos de 2,
simplemente volver, no hay trabajo por hacer.
Así que en realidad hay sólo tres medidas para mantener muy en cuenta.
Una vez más, y otra vez, estoy va a querer tener
para ordenar la mitad izquierda, ordenar la mitad derecha,
y luego una vez su dos mitades están ordenados,
Quiero unirlos en una lista ordenada.
Así que tenlo en mente.
>> Así que aquí está la lista original.
Vamos a tratar esto como una matriz, como empezamos a
en la segunda semana, que es un bloque contiguo de memoria.
En este caso, que contiene ocho números, espalda con espalda con espalda.
Y ahora vamos a aplicar fusión tipo.
Así que primero quiero ordenar la mitad izquierda de esta lista,
y dejar de, por lo tanto, centrarse en 4, 8, 6, y 2.
>> Ahora, ¿cómo hago para ordenar una lista de tamaño de 4?
Bueno tengo que considerar ahora la clasificación de la izquierda de la mitad izquierda.
Una vez más, vamos a retroceder por un momento.
Si el pseudocódigo es esto, y me dan ocho elementos,
8 es obviamente mayor que o igual a 2.
Así que con el primer caso no se aplica.
Así que para clasificar ocho elementos, yo primero ordenar la mitad izquierda de elementos,
entonces puedo ordenar la mitad derecha, luego me fusiono las dos mitades ordenadas, cada una del tamaño de 4.
OK.
>> Pero si lo que me has dicho, ordenar la mitad izquierda, que ahora es de tamaño 4,
¿Cómo puedo ordenar el medio queda?
Bueno, si tengo una de entrada de cuatro elementos,
Yo primero ordenar la izquierda dos, y luego los dos a la derecha,
y luego unirlos.
Así que de nuevo, se vuelve un poco de una mente de flexión juego aquí,
porque, clase de, que recordar dónde usted está en la historia,
pero al final del día, dado cualquier número de elementos,
que primero desea ordenar la medio izquierdo, luego la mitad derecha,
luego unirlos.
Vamos a empezar a hacer exactamente eso.
Aquí está la entrada de ocho elementos.
Ahora estamos viendo la mitad izquierda aquí.
¿Cómo puedo ordenar cuatro elementos?
Bueno, yo primero ordenar el medio izquierdo.
Ahora, ¿cómo puedo ordenar el medio queda?
Bueno me han dado dos elementos.
Así que vamos a ordenar estos dos elementos.
2 es mayor o igual a 2, por supuesto.
Así que el primer caso no se aplica.
>> Así que ahora tengo que ordenar la izquierda medio de estos dos elementos.
La mitad izquierda, por supuesto, está a sólo 4.
Entonces, ¿cómo puedo ordenar una lista de un elemento?
Ahora bien, ese caso base especial en lo alto, por así decirlo, se aplica.
1 es menor que 2, y mi lista es precisamente de tamaño 1.
Así que me vuelvo.
Yo no hago nada.
Y de hecho, mira lo que tengo hecho, 4 ya está ordenado.
Al igual que ya estoy parcialmente exitoso aquí.
>> Ahora que parece un poco estúpido a reclamar, pero es cierto.
4 es una lista de tamaño 1.
Ya está solucionado.
Eso es la mitad izquierda.
Ahora puedo ordenar la mitad derecha.
Mi entrada es un elemento, 8 Del mismo modo, ya ordenados.
Estúpido, también, pero de nuevo, este principio básico
va a permitir que construyamos ahora en la parte superior de este éxito.
4 ordenados, 8 se ordena, ahora ¿cuál fue el último paso?
Así que el tercer y último paso, cualquier tiempo estás ordenar una lista, el recuerdo,
era fusionar las dos mitades, la izquierda y la derecha.
Así que vamos a hacer exactamente eso.
Mi media izquierda es, por supuesto, 4.
Mi mitad derecha es 8.
>> Así que vamos a hacer esto.
En primer lugar voy a asignar algo de memoria adicional,
que voy a represento aquí, como se acaba de una matriz secundaria,
eso es lo suficientemente grande para esto.
Pero se puede imaginar que se extiende ese rectángulo toda la longitud,
si necesitamos más tarde.
¿Cómo tomo 4 y 8, y se fusionan esas dos listas de tamaño 1 en conjunto?
Aquí, también, bastante simple.
4 viene primero, luego viene 8.
Porque si quiero ordenar la medio izquierdo, luego la mitad derecha,
y luego fusionar esas dos mitades juntos, en forma ordenada,
4 viene primero, luego viene 8.
>> Así que parece que estamos haciendo progresos, incluso aunque no he hecho ningún trabajo real.
Pero recuerda dónde estamos en la historia.
Originalmente llevamos ocho elementos.
Clasificamos la mitad izquierda, que es 4.
Entonces nos lo solucionaron la mitad izquierda de la mitad izquierda, que era 2.
Y aquí vamos.
Hemos terminado con ese paso.
>> Así que si hemos solucionaron el media de 2 fuimos, ahora nosotros
tiene que ordenar la mitad derecha de 2.
Así que la mitad derecha de 2 es estos dos valores aquí, 6 y 2.
Así que vamos a tomar ahora una entrada de tamaño 2, y ordenar la mitad izquierda, y luego
la mitad derecha, y luego unirlos.
Bueno, ¿cómo puedo ordenar una lista de tamaño 1, que contiene sólo el número 6?
Yo ya he terminado.
Se ordena esa lista de tamaño 1.
>> ¿Cómo puedo ordenar otra lista de tamaño 1, la denominada media derecha.
Bueno, también, ya está solucionado.
El número 2 es el único.
Así que ahora tengo dos mitades, izquierda y bien, tengo que unirlos.
Permítanme doy un poco de espacio extra.
Y poner 2 en allí, a continuación, 6 de allí, de ese modo
ordenar la lista, izquierda y derecha, y la fusión juntos, en última instancia.
Así que estoy en un poco mejor forma.
No he terminado, porque es evidente 4, 8, 2, 6 no es el ordenamiento final que quiero.
Pero ahora tengo dos listas de tamaño 2, que haber dos, respectivamente, sido ordenados.
Así que ahora si se rebobina en su mente de ojo, ¿dónde nos deja eso?
Empecé con ocho elementos, entonces yo recortado hacia abajo a la mitad izquierda de 4,
a continuación, la mitad izquierda de 2, y entonces la mitad derecha de 2,
Terminé, por lo tanto, la clasificación de la izquierda media de 2, y la mitad derecha de 2,
¿cuál es el tercer y último paso aquí?
Tengo que fusionar dos listas de tamaño 2.
Así que vamos a seguir adelante.
Y en la pantalla aquí, dar me algo de memoria adicional,
aunque técnicamente, noto que tengo tiene un montón de espacio en blanco encima de la tapa
Ya está.
Si quiero ser especialmente espacio eficiente sabio,
Yo sólo podía empezar a mover los elementos adelante y atrás, arriba y abajo.
Pero sólo por la claridad visual, Voy a ponerlo abajo,
para mantener las cosas agradables y limpias.
>> Así que tengo dos listas de tamaño 2.
La primera lista tiene 4 y 8.
La segunda lista tiene 2 y 6.
Vamos a fusionar los juntos en forma ordenada.
2, por supuesto, es lo primero, luego 4, luego 6, entonces 8.
Y ahora parece que estamos consiguiendo en algún lugar interesante.
Medio Ahora he ordenada de la lista, y casualmente, es
todos los números pares, pero eso es, de hecho, sólo una coincidencia.
Y ahora he ordenado la izquierda medio, por lo que es 2, 4, 6 y 8.
Nada está fuera de orden.
Que se siente como el progreso.
>> Ahora se siente como si hubiera estado hablando siempre ahora,
así que lo que queda por ver si esto algoritmo es, de hecho, más eficiente.
Pero vamos a través super metódicamente.
Un ordenador, por supuesto, lo haría así.
Entonces, ¿dónde estamos?
Empezamos con ocho elementos.
Me clasifiqué la mitad izquierda de 4.
Me parece que hacer con eso.
Así que ahora el siguiente paso es ordenar la mitad derecha de 4.
Y esta parte podemos ir a través de un poco más de
rápidamente, aunque usted es bienvenidos a rebobinar o pausar, justo
pensar a través de él en su propio ritmo, pero lo
que tenemos ahora es una oportunidad para hacer lo mismo algoritmo exacto de las cuatro
números diferentes.
>> Así que vamos a seguir adelante, y se centran en la mitad derecha, lo que estamos aquí.
La mitad izquierda de ese medio derecho, y ahora el
mitad izquierda de la izquierda la mitad de esa mitad derecha,
y cómo puedo ordenar una lista de tamaño 1 que contiene sólo el número 1?
Ya está hecho.
¿Cómo puedo hacer lo mismo para una lista de tamaño 1 que contiene sólo 7?
Ya está hecho.
El tercer paso de este medio a continuación, es fusionar estos dos elementos
en una nueva lista de tamaño 2, 1 y 7.
No parecen haber hecho todo que mucho trabajo interesante.
Vamos a ver qué sucede después.
Acabo solucionaron la mitad izquierda de la mitad derecha de mi entrada original.
Ahora vamos a ordenar la derecha medio, que contiene 5 y 3.
Vamos a volver a ver a la izquierda medio, ordenados, medio derecho, ordenados,
y fusionar los dos juntos, en un poco de espacio adicional,
3 viene primero, luego viene 5.
Y ahora, hemos clasificado el media izquierda de la mitad derecha
del problema original, y la mitad derecha de la mitad derecha
del problema original.
¿Cuál es la tercera y última etapa?
Bueno para fusionar esas dos mitades.
Así que déjame a mí mismo un poco espacio extra, pero, de nuevo,
podría ser el uso de ese espacio hasta repuesto superior.
Pero nosotros vamos a seguir simple visualmente.
Permítanme ahora se funden en 1, y a continuación, 3, 5 y, a continuación, y luego 7.
De esta manera dejándome ahora con la mitad derecha del problema original
Eso es perfectamente ordenados.
>> Entonces, ¿qué queda?
Siento que sigo diciendo que el mismas cosas una y otra vez,
pero eso es un reflejo de la hecho de que estamos utilizando recursividad.
El proceso de usar una algoritmo de nuevo, y de nuevo,
en subconjuntos más pequeños de el problema original.
Así que ahora tenemos una izquierda ordenados medio del problema original.
Tengo un medio ordenado derecho del problema original.
¿Cuál es la tercera y última etapa?
Oh, es la fusión.
Así que vamos a hacer eso.
Vamos a asignar algunos adicionales memoria, pero mi Dios, nos
podría poner en cualquier lugar ahora.
Tenemos mucho espacio disponible para nosotros, pero vamos a mantener las cosas simples.
En vez de ir hacia atrás y adelante con nuestra memoria original,
vamos hazlo visualmente por aquí abajo,
para terminar la fusión de la mitad izquierda y la mitad derecha.
>> Así que mediante la fusión, ¿qué tengo que hacer?
Quiero aprovechar los elementos en orden.
Así que mirando a la mitad izquierda, Veo el primer número es 2.
Miro a la mitad derecha, Veo el primer número
es 1, así que obviamente que número Qué quiero arrancar,
y poner primero en mi lista final?
Por supuesto, 1.
Ahora quiero hacer esa misma pregunta.
En la mitad izquierda, tengo todavía tiene el número 2.
En la mitad derecha, Tengo el número 3.
¿Cuál debo quiero elegir?
Por supuesto, el número 2 Y Ahora notar los candidatos
son 4 a la izquierda, 3 a la derecha.
Vamos, por supuesto, elegir 3.
Ahora los candidatos son 4 en la izquierda, 5 a la derecha.
Nosotros, por supuesto, elegimos 4.
6 a la izquierda, 5 a la derecha.
Nosotros, por supuesto, elegimos 5.
6 a la izquierda, 7 a la derecha.
Elegimos 6, y luego elegir 7, y luego elegimos 8.
Voila.
>> Así que un gran número de palabras más tarde, han clasificado esta lista de ocho elementos
en una lista de uno a ocho, eso está aumentando con cada paso,
pero cuánto tiempo lo hizo que nos lleva a hacer eso.
Bueno, yo he deliberadamente cosas establecidas ilustrado
aquí, así que podemos tipo de ver o apreciar la división
en la conquista que está ocurriendo.
>> De hecho, si uno mira hacia atrás en el velorio, He dejado todas estas líneas de puntos
en marcadores de posición, usted puede, clase de, vea, en orden inverso,
si usted especie de mirar hacia atrás en la historia ahora, mi lista original
es, por supuesto, de tamaño 8.
Y a continuación, previamente, estaba se trata de dos listas de tamaño 4,
y luego cuatro listas de tamaño 2, y luego ocho listas de tamaño 1.
>> Entonces, ¿qué hace esto, clase de, recordarle?
Bueno, de hecho, cualquiera de los algoritmos que hemos
mirado hasta el momento en el que dividir y dividir y dividir,
seguir teniendo las cosas de nuevo, y Nuevamente, los resultados en esta idea general.
Y así hay algo logarítmica pasando aquí.
Y no es bastante registro de n, pero hay un componente logarítmica
a lo que acabamos de hacer.
>> Ahora vamos a considerar la forma en que realmente es.
Así que ingrese de n, de nuevo fue un gran tiempo de funcionamiento,
cuando hicimos algo parecido búsqueda binaria, ya que ahora llamamos,
la estrategia de divide y vencerás a través del cual nos encontramos Mike Smith.
Ahora técnicamente.
Eso es log base 2 de n, incluso aunque en la mayoría de las clases de matemáticas,
10 es por lo general la base de que usted asume.
Pero científicos de la computación casi siempre pensar y hablar en términos de base 2,
así que en general, sólo decimos registro de n, en lugar de logaritmo en base 2 de n,
pero son exactamente una y la mismo en el mundo del ordenador
ciencia, y como un aparte, hay un factor constante
diferencia entre los dos, por lo que es discutible de todos modos, por razones más formales.
>> Pero por ahora, lo que nos importa acerca es este ejemplo.
Así que vamos a no prueba con el ejemplo, pero al menos usar un ejemplo de los números
a la mano como una comprobación de validez, si se quiere.
Así que con anterioridad la fórmula era la base de registro 2 de n, pero lo que es n en este caso.
Tuve n números originales, o 8 del número original específicamente.
Ahora que ha sido un poco tiempo, pero estoy bastante
Seguro que log base 2 del valor 8 es 3,
y de hecho, lo que es bueno de esto es que el 3 es exactamente el número de veces
que se puede dividir una lista de longitud 8 otra vez, y otra vez,
y otra vez, hasta que uno se queda con listas de apenas el tamaño 1.
¿Correcto?
8 va a 4, pasa a 2, pasa a 1, y eso es
refleja exactamente eso imagen que teníamos hace un momento.
Así que un poco de cordura comprobar de dónde el logaritmo está realmente involucrado.
>> Así que ahora, ¿qué más está involucrado aquí? n.
Así notar que cada tiempo yo nos dividimos la lista,
aunque en orden inverso en la historia aquí, todavía estaba haciendo n cosas.
Ese paso fusión requería que Toco cada uno de los números,
con el fin de deslizarse en su ubicación adecuada.
Así que, aunque la altura de esta diagrama es del tamaño del registro n de n o 3,
específicamente, en otras palabras, Hice tres divisiones aquí.
¿Cuánto trabajo hice horizontalmente a lo largo de este gráfico cada vez?
>> Bueno, lo hice n pasos de trabajar, porque si tengo
tiene cuatro elementos y cuatro elementos, y necesito unirlos.
Tengo que ir a través de estos cuatro y estos cuatro,
en última instancia, para fundirlas de nuevo en ocho elementos.
Si por el contrario tengo ocho dedos por aquí, que no lo hago, y de ocho
fingers-- sorry-- Si tengo tiene cuatro dedos por aquí,
que voy a hacer, cuatro dedos aquí, que yo hago,
entonces eso es la misma ejemplo, como antes, si lo hago
tiene ocho dedos aunque en total, que puedo clase de, hacer,.
Exactamente lo que puedo hacer aquí, entonces yo sabe
fusionar todas estas listas de tamaño 1 juntos.
Pero sin duda tengo que mirar en cada elemento de exactamente una vez.
Por lo tanto la altura de este proceso es log n, la anchura de este proceso, por así decirlo,
es N, así que lo que parece tener, en última instancia, es
una duración de tamaño n veces log n.
>> En otras palabras, hemos dividido la lista, registro n veces,
pero cada vez que lo hicimos, tuvimos tocar cada uno de los elementos
con el fin de fusionarlos todos juntos, que
fue n paso, por lo que tenemos n veces log n, o como un científico de la computación diría,
asintóticamente, que sería la palabra grande
para describir la parte superior con destino en un tiempo de funcionamiento,
nos estamos quedando en una gran o de log n tiempo, por así decirlo.
>> Ahora bien, esto es importante, porque recuerdan lo que fueron los tiempos de funcionamiento
con la burbuja de género, y la selección ordenar y ordenación por inserción,
e incluso algunos otros que existen, n al cuadrado era donde estábamos.
Y usted puede, un poco, ver esto aquí.
Si n al cuadrado es obviamente n veces n, pero aquí tenemos n veces log n,
y ya sabemos por semana cero, que log n, la logarítmica,
es mejor que algo lineal.
Después de todo, recordar la imagen con el rojo y el amarillo
y las líneas verdes que Drew, el línea logarítmica verde era mucho menor.
Y por lo tanto, mucho mejor y más rápido que las líneas amarillas y rojas rectas,
n veces log n es, de hecho, mejor de n veces n o n al cuadrado.
>> Así que parece que tenemos identificado una combinación de algoritmo
especie que se ejecuta en mucho tiempo más rápido, y de hecho,
por eso, a principios de esta semana, cuando vimos que contienda entre burbujas
Ordena, ordenación por selección, y fusionar Ordena, ordenamiento por mezcla muy, muy ganado.
Y, en efecto, que ni siquiera esperar de ordenamiento de burbuja y ordenación por selección
acabar.
>> Ahora vamos a tomar otro paso en este, desde un poco más
punto de vista formal, por si caso, esto resuena mejor
que el alto nivel de discusión.
Así que aquí está el algoritmo de nuevo.
Preguntémonos, lo que el tiempo de ejecución
es de este algoritmos diferentes pasos?
Vamos a dividir en la primera caso y el segundo caso.
El IF y ELSE En el caso SI, Si N es menor que 2, simplemente volver.
Se siente como constante de tiempo.
Es, algo así, como dos pasos, Si n es inferior a 2, y luego volver.
Pero como hemos dicho el lunes constante de tiempo, o del o de 1,
pueden ser dos pasos, tres pasos, incluso 1.000 pasos.
Lo que importa es que es un número constante de pasos.
Así que el amarillo resaltado pseudocódigo aquí se ejecuta en, lo vamos a llamar,
constante de tiempo.
Así que de manera más formal, y vamos a-- este
será el grado en que nos formalizar este derecho ahora-- T de n,
el tiempo de ejecución de un problema que toma n tantos como entrada,
es igual a grande o de uno, Si N es menor que 2.
Así que es condicionado a eso.
Así que para ser claros, si n es menor que 2, tenemos una lista muy corta, a continuación,
el tiempo de ejecución, T de n, donde n es 1 o 0, en este caso muy específico,
es sólo va a ser la constante de tiempo.
Se va a tomar uno paso, dos pasos, lo que sea.
Es un número fijo de pasos.
>> Así que la parte jugosa seguramente debe estar en el otro caso en el pseudocódigo.
El caso ELSE.
Ordenar mitad izquierda de los elementos, tipo adecuado medio de elementos, combinar mitades ordenadas.
¿Cuánto tiempo dura cada uno de esos pasos tomar?
Bueno, si el funcionamiento tiempo para ordenar n elementos
Es decir, vamos a llamarlo muy genéricamente, T de n,
a continuación, la clasificación de la izquierda medio de los elementos
es decir, una especie de, como decir, T de n dividido por 2,
y del mismo modo la clasificación de la mitad derecha de elementos es, algo así, como diciendo:
T de n divide 2, y luego la fusión de las mitades ordenados.
Bueno, si tengo alguna número de elementos aquí,
como cuatro, y un número de elementos que aquí, al igual que cuatro,
y tengo que combinar cada uno de estos cuatro en, y cada una de estas cuatro en, uno
después de la otra, de modo que en última instancia, tengo ocho elementos.
Se siente como que es grande o de n pasos?
Si tengo n dedos y cada una de ellos tiene que ser fusionado en su lugar,
eso es como otro n pasos.
>> Así que de hecho formulaically, podemos expresar esto,
aunque un poco asustadizo al principio vista, pero es algo
que captura exactamente esa lógica.
El tiempo de ejecución, T de n, si n es mayor que o igual a 2.
En este caso, el caso ELSE, es T de n dividido por 2, además de T de N dividido por 2,
más grande o de n, algunos número de pasos lineal,
tal vez exactamente n, tal vez 2 veces n, pero es más o menos, el orden de n.
Así que, también, es la forma en que puede expresar esta formulaically.
Ahora no vas a saber esto a menos que ha grabado en su mente,
o búsquelo en la lomo de un libro de texto, que
podría tener un poco hoja de trucos al final,
pero esto es, de hecho, va a nos dan una gran o de n log n,
porque la recurrencia que que estamos viendo aquí en la pantalla,
si realmente lo hizo a cabo, con un número infinito de ejemplos,
o lo hiciste formulaically, lo haría ver que esto, porque esta fórmula
sí mismo es recursivo, con t de n por algo a la derecha,
y t de n por la izquierda, esto puede en realidad ser expresada, en última instancia,
tan grande de lado n log n.
Si no está convencido, eso es bien por ahora, sólo
toma en la fe, que es, de hecho, lo que conduce a la recurrencia,
pero esto es sólo un poco más de un enfoque matemático a la búsqueda
en el momento de ejecución de la fusión especie basado en su pseudocódigo solo.
>> Ahora vamos a echar un poco de un respiro de todo eso,
y echar un vistazo a una cierta ex senador, quien
podría parecer un poco familiar, quien se sentó con Eric de Google
Schmidt, hace algún tiempo, para una entrevista en el escenario, delante de un montón
de las personas, hablar en última instancia acerca de un tema, que es bastante ya familiar.
Echemos un vistazo.
>> Eric Schmidt: Ahora el senador, usted está aquí en Google,
y me gusta pensar en el presidencia como una entrevista de trabajo.
Ahora es difícil conseguir un trabajo como presidente.
PRESIDENTE OBAMA: Correcto.
Eric Schmidt: Y tú eres va a hacer [inaudible] ahora.
También es difícil de conseguir un trabajo en Google.
PRESIDENTE OBAMA: Correcto.
>> Eric Schmidt: Tenemos preguntas, y le pedimos a nuestras preguntas de los candidatos,
y éste es de Larry Schwimmer.
>> PRESIDENTE OBAMA: OK.
>> Eric Schmidt: ¿Qué?
Ustedes piensan que estoy bromeando?
Es justo aquí.
¿Cuál es la forma más eficiente de ordenar un millón 32 bits enteros?
>> PRESIDENTE OBAMA: Bueno--
Eric Schmidt: En ocasiones, tal vez me siento, maybe--
PRESIDENTE OBAMA: No, no, no, no, no, yo think--
Eric Schmidt: Eso no es it--
PRESIDENTE OBAMA: I pensar, creo que la burbuja
tipo sería el camino equivocado.
Eric Schmidt: Vamos.
¿Quién le dijo eso?
OK.
Yo no hice la informática en--
>> PRESIDENTE OBAMA: Tenemos dieron nuestros espías en ese país.
PROFESOR: Muy bien.
Vamos a dejar detrás de nosotros ahora mundo teórico de algoritmos
en el análisis asintótico de los mismos, y volver a algunos temas
desde la semana cero y uno, e inicio para eliminar algunas ruedas de entrenamiento,
si se quiere.
Así que usted realmente entiende en última instancia, a partir de cero, lo que es
pasando por debajo de la campana, cuando escribir, compilar y ejecutar programas.
Recordemos, en particular, que se trataba de el primer programa en C mirábamos,
un programa canónica, simple de tipo, en términos relativos,
en donde, imprime, Hello World.
Y recuerdo que le dije, el proceso que el código fuente pasa a través de
es exactamente esto.
Usted toma su código fuente, pasa a través de un compilador, como Clang,
y fuera viene código objeto, que podría tener este aspecto, ceros y unos
que la CPU de la computadora, el centro unidad de procesamiento o el cerebro,
en última instancia, entiende.
>> Resulta que esa es una poco de una simplificación excesiva,
que ahora estamos en un posición de separar
para entender lo que realmente ha sido pasando por debajo de la campana
cada vez que se ejecuta Clang, o más generalmente,
cada vez que realice un programa, utilizando Marca y CF 50 IDE.
En particular, cosas por el estilo este se genera primero,
la primera vez que compila el programa.
En otras palabras, cuando se llevar a su código fuente
y compilarlo, ¿qué es primero siendo enviada por Clang
es algo conocido como código ensamblador.
Y, de hecho, se ve exactamente como este.
>> Corrí un comando en el línea de comandos anterior.
Hola.c Clang capitales tablero s, y esto crea un archivo
para mí llamados hello.s, dentro de los cuales eran exactamente
estos contenidos, y un poco más arriba y un poco más abajo,
pero me he puesto la más jugosa información aquí, en la pantalla.
Y si te fijas bien, verás al menos un par de palabras clave familiares.
Tenemos principal en la parte superior.
Hemos printf en el centro.
Y también tenemos hola mundo barra invertida n entre comillas abajo abajo.
>> Y todo lo demás aquí es muy instrucciones de bajo nivel
que la CPU de la computadora entiende.
Instrucciones de CPU que se mueven de memoria alrededor, que las cadenas de carga de la memoria,
y en última instancia, de impresión cosas en la pantalla.
Ahora lo que sucede aunque después se genera el código de montaje?
En última instancia, lo hace, de hecho, Todavía generar código objeto.
Pero los pasos que tienen realmente estado sucediendo debajo de la campana
mirar un poco de la misma familia.
El código fuente se convierte en código ensamblador, que luego se convierte en código objeto,
y las palabras clave aquí es que, al compilar el código fuente,
cabo viene código ensamblador, y después al colocar su código en ensamblador,
cabo viene código objeto.
>> Ahora Clang es super sofisticado, como muchos de los compiladores,
y lo hace de todos estos pasos juntos, y no necesariamente
salida de cualquier intermedio archivos que aún se pueden ver.
Simplemente compila las cosas, que es el término general que
describe todo este proceso.
Pero si realmente quieres para ser concreto, no hay
mucho más que hacer allí también.
>> Pero también vamos a considerar ahora que incluso ese programa super simple, hello.c,
llamado una función.
Pidió printf.
Pero yo no escribí printf, de hecho, que viene con c, por así decirlo.
Es un recordatorio de que la función es declarada en io.h estándar, que
es un archivo de cabecera, que es un tema que va en realidad
sumergirse en mayor profundidad en poco tiempo.
Sin embargo, un archivo de cabecera es normalmente acompañados
por un archivo de código, archivo de código fuente, por lo al igual que existe io.h. estándar
>> Hace algún tiempo, alguien, o de alguien, también escribió
un archivo llamado io.c norma, en que las definiciones reales,
o implementaciones de printf, y racimos de otras funciones,
son en realidad escrito.
Así que teniendo en cuenta que, si tenemos en cuenta que tiene aquí a la izquierda, hello.c, que cuando
compilado, nos da hello.s, incluso si Clang no molesta ahorro en un lugar
podemos verlo, y que el código de montaje obtiene ensamblado en hello.o, que
es, de hecho, el nombre por defecto dado cada vez que se compila la fuente
codificar en código objeto, pero no son listo para ejecutarlo sin embargo,
porque otro paso tiene que suceder, y tiene
venido sucediendo en los últimos semana, quizá sin saberlo tú.
>> Específicamente en alguna parte en CS50 IDE, y esto,
también, será un poco de un simplificación excesiva por un momento,
hay, o fue en otro tiempo, un archivo llamado io.c estándar,
que alguien compilado en io.s estándar o el equivalente,
que alguien ensambla entonces en io.o estándar,
o resulta en una ligeramente diferente archivo
formato que puede tener un diferente extensión de archivo por completo,
pero en teoría y conceptualmente, exactamente esos pasos tuvieron que pasar en alguna forma.
Es decir, que ahora cuando estoy escribiendo un programa,
hello.c, que apenas dice, hola mundo, y estoy usando el código de otra persona
como printf, que era una vez un tiempo, en un archivo llamado io.c estándar,
entonces de alguna manera tengo que llevar a mi código objeto, mis ceros y unos,
y el objeto de esa persona código, o ceros y unos,
y de alguna manera enlazar juntos en un archivo final, llamada hola, que
tiene todos los ceros y los de mi función principal,
y todos los ceros y los de printf.
>> Y, en efecto, que el pasado proceso es llamada, la vinculación de su código objeto.
La salida de los cuales es un archivo ejecutable.
Así que para ser justos, en el final del día, nada
ha cambiado desde la semana uno, cuando primero comenzó compilar programas.
De hecho, todo esto ha sido pasando por debajo de la capucha,
pero ahora estamos en una posición donde podamos realmente
desmenuzar estos varios pasos.
Y, de hecho, al final del día, todavía estamos
izquierda con ceros y unos, que es en realidad un gran segue ahora
a otra capacidad de C, que nosotros no hemos tenido que aprovechar más probable
hasta la fecha, conocida como operadores bit a bit.
En otras palabras, hasta el momento, en cualquier momento nos hemos tratado con datos en C o variables en C,
hemos tenido cosas como caracteres y carrozas y complementos
y anhela y dobles y similares, pero todos esos son al menos ocho bits.
Hemos embargo nunca sido capaces de manipular bits individuales,
a pesar de que un bit individual, nos saben, puede representar un 0 y un 1.
Ahora resulta que en C, puede obtener acceso a los bits individuales,
si conoce la sintaxis, con la que para llegar a ellos.
>> Así que vamos a echar un vistazo a operadores bit a bit.
Así fotografiados aquí hay algunos símbolos que hemos, clase de, clase de, visto antes.
Veo una y comercial, vertical bar, y algunos otros también,
y recordar que signo ampersand es algo que hemos visto antes.
El operador lógico AND, donde tienes dos de ellos juntos, o la lógica OR
operador, en la que tener dos barras verticales.
Operadores bit a bit, que vamos a ver operar en bits de forma individual,
sólo tiene que utilizar un solo signo, un barra vertical única, el símbolo de intercalación
que viene a continuación, la pequeña tilde y, luego a la izquierda
soporte dejó soporte o corchete derecho escuadra derecha.
Cada uno de ellos tienen diferentes significados.
>> De hecho, vamos a echar un vistazo.
Vamos a la vieja escuela de hoy, y el uso una pantalla táctil de antaño,
conocido como un tablero blanco.
Y este tablero blanco nos va a permitir
para expresar algunos símbolos bastante simples, o más bien algunas fórmulas bastante simples,
que podemos entonces en última instancia, apalancamiento, con el fin
acceder a la persona bits dentro de un programa C.
En otras palabras, vamos a hacer esto.
Primero hablemos de momento en signo,
que es el operador AND.
En otras palabras, esto es un operador que permite
que yo tenga una variable de la izquierda Típicamente, y una variable de la derecha,
o un valor individual, que si Y juntos, me da un resultado final.
Entonces, ¿qué puedo decir?
Si en un programa, que tiene una variable que almacena uno de estos valores,
o vamos a mantenerlo simple, y justo escriba ceros y unos de forma individual,
así es como funciona el operador de signo.
0 0 Y comercial va a ser igual a 0.
Ahora ¿por qué es eso?
>> Es muy similar a Expresiones booleanas,
que hemos discutido hasta ahora.
Si usted piensa que después de todo, el 0 es falsa, 0 es falsa, falsa y falso
es, como hemos discutido lógicamente, también falsa.
Así obtenemos 0 aquí también.
Si usted toma 0 ampersand 1, así que, también,
va a ser 0, porque para esto la expresión de la izquierda para ser verdad o 1,
que tendría que ser verdadero y cierto.
Pero aquí tenemos falsa y verdadero, o 0 y 1.
Ahora, de nuevo, si tenemos 1 ampersand 0, eso también va a ser 0,
y si tenemos 1 ampersand 1, finalmente tenemos un 1 bit.
En otras palabras, no estamos haciendo algo interesante con este operador
por el momento, este operador signo.
Es el operador AND.
Pero estos son los ingredientes a través del cual podemos hacer
cosas interesantes, como pronto veremos.
>> Ahora vamos a ver sólo la única barra vertical por aquí a la derecha.
Si tengo un bit 0 y yo O con el bit a bit
Operador OR, otro bit 0, eso va a darme 0.
Si tomo un bit 0 y O con un bit 1, a continuación, voy a conseguir 1.
Y, de hecho, sólo por claridad, me dejó ir hacia atrás,
de modo que mis barras verticales no se confunden con 1 de.
Permítanme reescribir todos mi 1 es un poco más
claramente, de modo que nos vemos la próxima, si han un 1 o 0, eso va a ser un 1,
y si tengo un 1 O 1 que, también, va a ser un 1.
Así se puede ver, lógicamente, que la O operador se comporta de manera muy diferente.
Esto me da 0 O 0 0 me da, pero cualquier otra combinación me da 1.
Siempre y cuando tengo un 1 en el fórmula, el resultado va a ser 1.
>> En contraste con la Y operador, el signo,
sólo si tengo dos de 1 en la ecuación, puedo realmente conseguir un 1.
Ahora hay algunos otros operadores también.
Uno de ellos es un poco más complicado.
Así que déjame ir adelante y borrar esto para liberar algo de espacio.
Y vamos a echar un vistazo a la símbolo de intercalación, por un momento.
Esto es típicamente un carácter que se pueda escribir
en su celebración de teclado Mayús y entonces uno de los números encima de la de EE.UU.
teclado.
>> Así que esta es la exclusiva Operador OR, OR exclusiva.
Así que acabamos de ver el operador OR.
Este es el exclusivo operador OR.
¿Qué es realmente la diferencia?
Bueno vamos a ver en la fórmula, y utilizar esto como ingredientes en última instancia.
0 0 XOR.
Voy a decir es siempre 0.
Esa es la definición de XOR.
0 XOR 1 va a ser 1.
1 XOR 0 va a ser 1, y 1 XOR 1 va a ser?
¿Equivocado?
¿O derecha?
No lo sé.
0.
Ahora, ¿qué está pasando aquí?
Bueno pensar en el nombre de este operador.
Exclusiva O, por lo que el nombre, tipo de, sugiere,
la respuesta sólo va a ser un 1 si las entradas son exclusivos,
exclusivamente diferente.
Así que aquí las entradas son los mismo, por lo que la salida es 0.
Aquí las entradas son la mismo, por lo que la salida es 0.
Aquí están las salidas son diferentes, son exclusivos, por lo que la salida es 1.
Así que es muy similar a la Y, es muy similar,
o mejor dicho, que es muy similar a la O, pero sólo de manera exclusiva.
Éste ya no es un 1, porque tenemos dos de 1,
y no exclusivamente, sólo uno de ellos.
Correcto.
¿Qué pasa con los demás?
Bueno, la tilde, por su parte, es realmente agradable y sencilla, gracias a Dios.
Y este es un unario operador, lo que significa
que se aplica a una sola entrada, un operando, por así decirlo.
No a una izquierda y una derecha.
En otras palabras, si usted toma tilde de 0, la respuesta será la opuesta.
Y si se toma tilde de 1, el respuesta allí será el opuesto.
Así que el operador tilde es una forma de negar un poco,
o voltear un poco de 0 a 1, o de 1 a 0.
>> Y eso nos deja finalmente con sólo dos operadores finales,
El llamado desviación a la izquierda, y la el llamado operador de desplazamiento a la derecha.
Echemos un vistazo a cómo los trabajos.
El operador de desplazamiento a la izquierda, por escrito con dos escuadras por el estilo,
funciona como sigue.
Si mi entrada, o mi operando, a la izquierda operador de desplazamiento es, sencillamente, un 1.
Y entonces digo que la computadora desviación a la izquierda que 1, dicen siete lugares,
el resultado es como si tomar ese 1, y moverlo
siete lugares más a la izquierda, y por defecto,
vamos a suponer que el espacio a la derecha
va a ser rellenado con ceros.
En otras palabras, 1 izquierda turno 7 va que me diera que 1, seguido de 1, 2, 3,
4, 5, 6, 7 ceros.
Así que en cierto modo, le permite tomar un número pequeño como 1,
y claramente que sea mucho mucho, mucho más grande de esta manera,
pero en realidad estamos yendo a ver enfoques más inteligentes para que
en su lugar, así,
>> Correcto.
Eso es todo para la semana tres.
Nos vemos la próxima vez.
Este fue CS50.
>> [REPRODUCCIÓN DE MÚSICA]
>> ALTAVOZ 1: Estaba en la merienda bar comiendo un helado con chocolate caliente.
Lo tenía todo en su rostro.
Lleva que el chocolate como una barba
ALTAVOZ 2: ¿Qué estás haciendo?
ALTAVOZ 3: Hmmm?
¿Qué?
>> ALTAVOZ 2: ¿Acabas de doble inmersión?
Hace doble sumergido el chip.
ALTAVOZ 3: Perdone.
ALTAVOZ 2: Usted sumergido el chip, que tomó un bocado, y sumergido de nuevo.
ALTAVOZ 3:
ALTAVOZ 2: Así que eso es como poner a su derecha la boca entera en el dip.
La próxima vez que usted toma un chip, simplemente sumergir una vez, y acabar con ella.
>> ALTAVOZ 3: ¿Sabes qué, Dan?
Usted sumerge la forma en que desea que echar mano.
Voy a mojar la manera que yo quiero que echar mano.