>> [Música tocando]
>> PROFESOR: Todo ben.
Este é CS50 e este é o fin de semana tres.
Entón, nós estamos aquí hoxe, non en Sanders Theater, en vez de Weidner Library.
Dentro dos cales é un estudo coñecido como Hauser Studio,
ou digamos Estudo H, ou debe nós dizer-- se lle gusta que broma,
é, en realidade, a partir de compañeiro, Mark, en liña,
que suxeriu tanto vía Twitter.
Agora, o que é legal sobre estar aquí nun estudo
é que eu estou rodeado por estes do verde paredes, unha pantalla verde ou chromakey,
por así dicir, o que significa que de CS50 equipo de produción, sen saber para min
agora, podería estar poñendo me máis en calquera lugar do mundo,
para mellor ou para peor.
>> Agora, o que temos por diante, conxunto de problemas dous está nas súas mans para esta semana,
pero con xogo de problemas tres da semana que vén,
será desafiado con a chamada de xogo 15,
un favor de partido vello que pode lembrar de recibir
como un neno que ten un grupo enteiro de números que pode desprazar cara arriba, abaixo,
esquerda e dereita, e hai un gap dentro do puzzle, no que
realmente desprazar as pezas de puzzle.
En definitiva, recibe esta puzzle nalgunha orde semi chou,
eo obxectivo é a clasificalos lo de arriba abaixo,
esquerda a dereita, a partir dun todo o camiño ata a 15.
>> Desafortunadamente, a aplicación terá en mans
será software base, non fisicamente.
Está realmente vai ter que escribir código co que un estudante ou usuario pode
xogar o xogo de 15.
E, de feito, en que o hacker edición do xogo de 15,
vai ser un desafío para aplicar, non só o xogo desta vella escola
xogo, mais si a solución diso, a posta en marcha de xeito deus,
por así dicir, que realmente resolve o enigma para o ser humano,
dando-lles información, despois información, despois información.
Entón, máis sobre iso a próxima semana.
Pero iso é o que está por vir.
>> Por agora lembrar que a principios desta semana tivemos este momento de angustia, se quixeren,
polo que o mellor que estabamos facendo selección wise foi un límite superior de grande n
cadrado.
Noutras palabras, bubble sort, tipo de selección, ordenación por inserción,
todos eles, mentres diferente na súa implantación,
converteu nun n ao cadrado que funciona tempo no peor caso.
E nós xeralmente asumen que o peor caso para clasificar
é aquel que os seus inputs son completamente cara atrás.
E, de feito, levou bastante a poucos pasos para aplicar cada un deses algoritmos.
>> Agora ao final da clase recall, nós comparamos bubble sort
contra a especie de selección contra outra que chamamos merge sort na época,
e propoño que está tomando vantaxe de unha lección de semana
cero, dividir e conquistar.
E de algunha maneira alcanzar algún tipo de logarítmica tempo de funcionamento, en definitiva,
en vez de algo iso é puramente cuadrática.
E non é moi logarítmica, é un pouco máis do que iso.
Pero se se lembra de clase, foi moito máis rápido.
Imos dar un ollo onde paramos.
>> Bubble sort contra selección tipo contra merge sort.
Agora están todos correndo, en teoría, ao mesmo tempo.
A CPU está en execución na mesma velocidade.
Pero pode sentir como aburrido iso vai moi rápido para facer,
e quão rápido cando injetamos un pouco de algoritmos de semana de cero,
podemos acelerar as cousas.
>> Así, tipo marca parece incrible.
Como podemos aproveitala lo, a fin para ordenar os números máis rapidamente.
Ben, imos pensar de volta para un ingrediente que
tivo de volta na semana cero, que de buscar alguén nunha lista telefónica,
e recordar que a pseudocódigo que nos propuxemos,
a través do cal podemos atopar alguén como Mike Smith,
parecía un pouco algo así.
>> Agora, bótalle un ollo en particular na liña 7 e 8, e 10 e 11,
que inducen a ese ciclo, polo que mantivemos voltar á liña 3 de novo, e de novo,
e de novo.
Pero resulta que vemos ese algoritmo, aquí en pseudocódigo,
un pouco máis de forma holística.
En realidade, o que estou buscando a aquí na pantalla,
é un algoritmo para a busca de Mike Smith entre algúns conxunto de páxinas.
E, de feito, podemos simplificar esta algoritmo nesas liñas 7 e 8,
e 10 e 11 a só dicir isto, que eu teño presentado aquí en amarelo.
Noutras palabras, se o Mike Smith é o inicio do libro,
nós non precisa especificar paso a paso agora como ir atopalo.
Non temos para especificar voltar á liña 3,
por que nós non só no seu lugar, digamos, máis xeralmente,
buscar Mike no metade esquerda do libro.
>> Por outra banda, se o Mike é de feito, ao final do libro,
por que non podemos só citar investigación unquote para Mike na metade dereita do libro.
Noutras palabras, por que non acabamos tipo de punt para nós mesmos dicindo:
buscar Mike neste subconxunto do libro,
e deixar para o noso existente algoritmo para dicir
como a busca de Mike en que a metade esquerda do libro.
Noutras palabras, o noso algoritmo funciona se é
un libro de teléfono desta espesor, esta espesor, ou calquera espesor que sexa.
Así, podemos de forma recursiva definir este algoritmo.
Noutras palabras, o pantalla aquí, é un algoritmo
para a busca de Mike Smith entre as páxinas dun libro de teléfono.
Así, na liña 7 e 10, imos só dicir exactamente iso.
E eu uso este término nun momento atrás, e de feito, recursão
é a palabra de orde, de momento, e é este proceso
de facer algo por algún cíclica usando o código que xa ten,
e chamando-o de novo, e unha vez máis, e de novo.
Agora vai ser importante que dalgún xeito inferior
para fóra, e non facelo infinitamente longo.
Se non, imos teñen, de feito un loop infinito.
Pero imos ver se podemos prestar esa idea dunha recursão, facendo algo novo
e de novo e de novo, para resolver o problema de ordenación mediante fusión
tipo, tanto máis eficiente.
>> Entón, eu lle merge sort.
Imos dar un ollo.
Entón aquí é pseudocódigo, con que poderiamos aplicar a selección,
usando este algoritmo chamado merge sort.
E é simplemente iso.
Sobre a entrada de n elementos, noutras palabras, se está
dado n elementos e números e cartas ou calquera que sexa a entrada é,
se está dado n elementos, se n sexa inferior a 2, só volver.
Non?
Porque se n é inferior a 2, que significa que a miña lista de elementos
ou é de tamaño 0 ou 1, e en ambos destes casos triviais,
a lista xa está clasificado.
Se non existe unha lista, está clasificado.
E se hai unha lista de lonxitude 1, é obviamente clasificadas.
Así, o algoritmo que só realmente facer algo interesante,
se temos dous ou máis elementos que nos deu.
Entón, imos ollar para a maxia entón.
Logo clasificar a metade esquerda dos elementos, a continuación, clasificar a metade dereita de elementos,
a continuación, mesturar as metades clasificados.
E o que é tipo de mente dobra aquí, é que realmente non
parecen terlle dito nada aínda, non?
Todo o que eu dixen é, dada unha lista de n elementos, ordenar a metade esquerda,
a continuación, a metade dereita, a continuación, mesturar as metades ordenados,
pero onde está o segredo real?
Onde está o algoritmo?
Ben, resulta que estas dúas liñas primeiro, a metade deixou tipo de elementos,
e tipo certo de metade dos elementos, son chamadas recursivas, por así dicir.
>> A pesar de todo, neste punto no tempo, eu teño
un algoritmo coa que a Ordenar unha morea de elementos?
Si.
Está ben aquí.
É aquí mesmo na pantalla, e para que eu poida usar o mesmo conxunto de pasos
para clasificar a metade esquerda, como podo a metade dereita.
E, de feito, unha vez máis, e outra vez.
Entón, de algunha maneira ou doutra, e nós imos en breve ver iso, a maxia de merge sort
incorpórase en que moi definitiva liña, a fusión das metades ordenados.
E iso parece bastante intuitivo.
Colle dúas metades, e ti, dalgún xeito, fondo-las,
e veremos que concretamente en un momento.
>> Pero este é un algoritmo completo.
E imos ver exactamente o por que.
Ben supoñer que estamos dando eses mesmos oito elementos aquí na pantalla, un
a través de oito, pero son en orde aleatoria.
E o obxectivo en cuestión é para clasificar estes elementos.
Ben, como podo ir sobre facelo usando, de novo,
merge sort, segundo este pseudo-código?
E, de novo, incutir iso en súa mente, só por un momento.
O primeiro caso é moi trivial, de ser inferior a 2,
basta volver, non hai traballo por facer.
Entón, realmente hai só tres pasos para realmente ter en conta.
Unha vez máis, e de novo, eu son Vai querer ter
para clasificar a metade esquerda, ordenar a metade dereita,
e, a continuación, xa que a súa dúas metades son clasificadas,
Quero fundídelas nunha lista ordenada.
Polo tanto, manter isto presente.
>> Entón aquí está a lista orixinal.
Imos tratar isto como unha array, coma nós comezamos a
a semana dous, que é un bloque contiguo de memoria.
Neste caso, contendo oito números, back to back to back.
E imos agora aplicar merge sort.
Entón, primeiro quero clasificar a metade esquerda da lista,
e imos, polo tanto, concentrarse en 4, 8, 6, e 2.
>> Agora, como eu vou sobre ordenar unha lista de tamaño 4?
Ben eu teño que considerar agora selección esquerda da metade esquerda.
Unha vez máis, imos retroceder por un momento.
O pseudocódigo é iso, e eu estou determinado oito elementos,
8 é obviamente maior que ou igual a 2.
Así, co primeiro caso non se aplica.
Así, para clasificar oito elementos, eu primeiro ordenar a metade esquerda de elementos,
entón eu ordenar a metade dereita, entón eu mesturar as dúas metades, cada unha das ordenadas tamaño 4.
Aceptar.
>> Pero se acaba de me dicir, ordenar a metade esquerda, que agora é de tamaño 4,
como fago para clasificar a metade esquerda?
Ben, se eu teño unha entrada de catro elementos,
I primeiro clasificar á esquerda dous, entón os dous dereita,
e entón eu fundín-las.
Entón, de novo, pasa a ser un pouco dunha mente dobra xogo aquí,
porque, tipo, ten que Teña en conta que onde está na historia,
pero ao final do día, dada calquera número de elementos,
primeiro quere clasificar a metade esquerda, a continuación, a metade dereita,
logo fundín-las.
Imos comezar a facer exactamente isto.
Aquí é a entrada de oito elementos.
Agora nós estamos mirando para a metade esquerda aquí.
¿Como clasificar catro elementos?
Ben, eu primeiro clasificar a metade esquerda.
Agora como fago para clasificar a metade esquerda?
Ben, eu teño dado dous elementos.
Entón, imos resolver estes dous elementos.
2 é maior que ou igual a 2, por suposto.
Así que o primeiro caso non se aplica.
>> Entón, eu agora teño que clasificar a esquerda metade destes dous elementos.
A metade esquerda, por suposto, está só a 4.
Entón, como fago para clasificar a lista de elemento?
Ben, agora, que se base especial enriba, por así dicir, se aplica.
1 sexa inferior a 2, eo meu lista é realmente de tamaño 1.
Entón, eu só retornar.
Eu non fago nada.
E, de feito, mira o que eu teño feito, catro xa están clasificados.
Como eu xa estou parcialmente exitoso aquí.
>> Agora que parece unha especie de idiota para reclamar, pero é verdade.
4 é unha lista de tamaño 1.
Xa está clasificado.
Isto é a metade esquerda.
Agora eu ordenar a metade dereita.
Miña entrada é un elemento, 8 Do mesmo xeito, xa clasificados.
Estúpido, tamén, pero, de novo, este principio básico
vai permitir-nos construír agora enriba deste correctamente.
4 clasificado, 8 é clasificado, agora Cal foi a última etapa?
Así, o terceiro e último paso, calquera xa que está clasificando unha lista, recall,
era fusionar as dúas metades, á esquerda e á dereita.
Entón, imos facer exactamente isto.
Meu metade esquerda é, por suposto, 4.
Meu metade dereita é 8.
>> Entón, imos facelo.
Primeiro eu vou para reservar algunha memoria adicional,
que eu vou representar aquí, como só unha matriz secundaria,
que é grande abondo para caber iso.
Pero pode imaxinar que se estende rectángulo que toda a lonxitude,
se necesitamos máis tarde.
¿Como facer 4 e 8, e mesturar estas dúas listas de tamaño 1 xuntos?
Aquí, tamén, moi sinxelo.
4 vén primeiro, despois vén 8.
Porque se eu queira clasificar a metade esquerda, a continuación, a metade dereita,
e, a continuación, mesturar estas dúas metades xuntos, na orde de clasificación,
4 vén primeiro, despois vén 8.
>> Entón, parece que estamos a facer avances, aínda aínda que eu non teña feito calquera traballo real.
Pero lembre-se onde estamos na historia.
Nós orixinalmente levou oito elementos.
Separamos a metade esquerda, que é 4.
Entón nós ordenamos a metade esquerda da metade esquerda, que era de 2.
E aquí imos nós.
Somos feitos con ese paso.
>> Entón, se temos clasificados a á esquerda metade 2, agora nós
ten que clasificar a metade dereita de 2.
Así, a metade dereita 2 está estes dous valores aquí, 6 e 2.
Entón, imos agora dar unha entrada de tamaño 2, e ordenar a metade esquerda e logo
a metade dereita, e, a continuación, fundín-las.
Así como fago para clasificar a lista de tamaño 1, que contén só o número 6?
Eu xa estou feito.
Esa lista de tamaño 1 é ordenada.
>> ¿Como clasificar outra lista de tamaño 1, o así chamado metade dereita.
Ben, tamén, xa está clasificado.
O número 2 está só.
Entón agora eu teño dúas metades, esquerda e correcto, eu teño fundín-las.
Deixe-me dar-me un pouco de espazo extra.
E poñer-2 en alí, a continuación, 6 de alí, así
clasificando esa lista, esquerda e dereita, e fundíndose lo xuntos, en última instancia.
Entón, eu estou en algo mellor forma.
Non son feito, porque claramente 4, 8, 2, 6 non é a ordenación final que quero.
Pero agora teño dúas listas de tamaño 2, que ambos teñen, respectivamente, foron clasificadas.
Polo tanto, agora se retroceder na súa mente de ollo, onde é que isto déixanos?
Comecei con oito elementos, entón eu tallou-lo para abaixo para a metade esquerda do 4,
a continuación, a metade esquerda 2, e a continuación, a metade dereita da 2,
Eu rematar, polo tanto, a selección esquerda metade de 2, ea metade dereita de 2,
entón que é o terceiro e último paso aquí?
Teño que fundir-se dúas listas de tamaño 2.
Entón, imos adiante.
E na pantalla aquí, dar- me algunha memoria adicional,
aínda que tecnicamente, repare en que eu teño ten unha morea de espazo en branco encima
alí.
Se eu queira ser especialmente espazo eficiente sabio,
Podería simplemente comezar a mover os elementos e cara atrás, superior e inferior.
Pero só para maior claridade visual, Vou poñer-lo alí en baixo,
para manter as cousas agradable e limpo.
>> Entón eu teño dúas listas de tamaño 2.
A primeira lista ten 4 e 8.
A segunda lista ten 2 e 6.
Imos mesturar os xuntos na orde de clasificación.
2, por suposto, ven en primeiro lugar, a continuación, 4, 6, a continuación, a continuación, 8.
E agora parece que estamos a recibir nalgún lugar interesante.
Agora eu teño a metade clasificadas da lista, e coincidentemente, é
Todos os números pares, pero iso é, en realidade, só unha coincidencia.
E eu agora resolver a esquerda metade, de xeito que é 2, 4, 6, e 8.
Nada está fóra de orde.
Que se sente como progreso.
>> Agora parece que teño falado para sempre agora,
Entón, o que segue a ser visto se iso algoritmo é, en realidade, máis eficiente.
Pero estamos pasando por super metodicamente.
Un ordenador, por suposto, ía facelo así.
Entón, ¿onde estamos?
Comezamos con oito elementos.
Separei a metade esquerda da 4.
Eu parezo ser feito con iso.
Polo tanto, agora o seguinte paso é ordenar a metade dereita 4.
E esta parte podemos ir mediante un pouco máis
rapidamente, aínda que é Benvido a retroceder ou facer unha pausa, só
creo que por el en seu propio ritmo, pero o que
que temos agora é unha oportunidade para facer o mesmo algoritmo exacto en catro
números diferentes.
>> Entón imos adiante, e concentrarse en a metade dereita, que estamos aquí.
A metade esquerda do referido metade dereita, e agora o
metade esquerda da esquerda metade do que a metade dereita,
e como fago para clasificar a lista de tamaño 1 contén o número 1?
Xa está feito.
Cómo fago o mesmo para unha lista de tamaño 1 contendo só 7?
Xa está feito.
Paso tres á metade, a continuación, esta é para mesturar estes dous elementos
nunha nova lista de tamaño 2, 1 e 7.
Non parecen ter feito todo que moito traballo interesante.
Imos ver que pasa a continuación.
Só ordenados a metade esquerda do metade dereita da miña entrada orixinal.
Agora imos clasificar a dereita medio, que contén 3 e 5.
Imos de novo ollar para a esquerda metade, clasificado, metade dereita, clasificado,
e mesturar os dous xuntos, nalgún espazo adicional,
3 vén primeiro, despois vén 5.
E agora temos clasificados a metade esquerda da metade dereita
do problema orixinal, e a metade dereita da metade dereita
do problema orixinal.
¿Que é a terceira e última etapa?
Ben, para mesturar estas dúas metades xuntas.
Entón me deixe ter algún espazo extra, pero, de novo, eu
podería estar usando aquel espazo enriba de reposición.
Pero nós estamos indo a mantê- o simple visual.
Deixe-me agora fúndense en un, e a continuación, 3, 5 e, a continuación, e logo 7.
Así, me deixando agora coa metade dereita do problema orixinal
Isto é perfectamente ordenadas.
>> Entón o que queda?
Eu sinto que eu sigo dicindo a mesmas cousas de novo, e de novo,
pero iso é un reflexo do feito de que estamos a usar recursão.
O proceso de utilización dun algoritmo de novo, e de novo,
en subconxuntos máis pequenos de o problema orixinal.
Entón, agora teño unha esquerda clasificadas metade do problema orixinal.
Eu teño unha media ordenada dereita do problema orixinal.
Cal é a terceira e última etapa?
Oh, está fundindo.
Entón, imos facelo.
Imos reservar algún adicional memoria, pero o meu deus, nós
podería poñer-lo en calquera lugar agora.
Temos moito espazo dispoñible para nós, pero imos mantelo simple.
En vez de ir cara atrás e adiante coa nosa memoria orixinal,
imos facelo visualmente aquí abaixo,
para rematar a fusión metade esquerda e metade dereita.
>> Así, a través da fusión, o que eu teño que facer?
Eu quero ter os elementos en orde.
Entón, ollando para o lado esquerdo, Vexo o primeiro número é 2.
Eu ollo para a metade dereita, Vexo o primeiro número
é 1, entón obviamente que número que quero arrincar,
e poñer en primeiro lugar na miña lista final?
Por suposto, 1.
Agora quero facer a mesma pregunta.
Na metade esquerda, eu teño aínda ten o número 2.
Na metade dereita, Eu teño o número 3.
Cal deles quero escoller?
Por suposto, número 2 E Agora observe os candidatos
4 están á esquerda, á dereita 3.
Imos, por suposto, escoller tres.
Agora, os candidatos son 4 en á esquerda, 5, á dereita.
Nós, por suposto, escoller catro.
6, á esquerda, á dereita 5.
Nós, por suposto, escoller 5.
6 á esquerda, á dereita 7.
Nós escoller seis, e entón nós escoller 7, e, a continuación, nós escoller 8.
Listo.
>> Así, un gran número de palabras máis tarde, resolver esta lista de oito elementos
nunha lista de un a oito, que está aumentando cada paso,
pero canto tempo fixo lévanos a facelo.
Ben, eu teño deliberadamente cousas establecidas pictorially
aquí, para que poidamos tipo de ver ou apreciar a división
na conquista que está pasando.
>> En realidade, se ollar cara atrás na esteira, Eu deixei todas esas liñas pontilhadas
en soportes do lugar, pode, tipo de, vexa, en orde inversa,
se tipo de ollar cara atrás en historia agora, meu lista orixinal
é, por suposto, de tamaño 8.
E, a continuación, anteriormente, eu estaba lidando con dúas listas de tamaño 4,
e, a continuación, catro listas de tamaño 2, e, a continuación, oito listas de tamaño 1.
>> Entón, o que fai iso, tipo de, lembra?
Ben, en realidade, calquera de os algoritmos Nós
mirou, ata agora, onde nós dividir e dividir, e se dividen,
sigo a ter as cousas de novo, e de novo, resulta nesa idea xeral.
E entón hai algo logarítmica suceder aquí.
E non é moi de rexistro n, pero hai un compoñente logarítmica
co que acaba de facer.
>> Agora imos considerar como isto realmente é.
Entón rexistro n, de novo foi un gran tempo de execución,
cando fixemos algo busca binaria, como agora chamalo,
a estratexia de dividir para conquistar vía que atopamos Mike Smith.
Agora tecnicamente.
Isto é log base dous n, mesmo aínda que na maioría das clases de matemáticas,
10 é xeralmente a base que asume.
Pero científicos da computación case sempre pensar e falar en termos de base 2,
así que nós xeralmente só dicir rexistro de N, no canto de rexistro de base 2 de N,
pero son exactamente un eo mentres que no mundo do ordenador
ciencia, e como un aparte, hai un factor constante
diferenza entre os dous, de xeito que é Moot de calquera xeito, por razóns máis formais.
>> Pero, por agora, o que nos importa é sobre este exemplo.
Entón non imos probar por exemplo, pero en menos usar un exemplo dos números
na man como unha comprobación de sanidade, se quere.
Así, a fórmula anteriormente foi rexistro de base 2 de N, pero o que é n neste caso.
Eu tiña números de n orixinais, ou 8 do número orixinal especificamente.
Agora que foi un pouco agora, pero estou moi
Asegúrese de que a base de rexistro 2 do valor 8 é 3,
e, de feito, o que é bo do que é 3 que é exactamente o número de veces
que pode dividir unha lista lonxitude de 8, e de novo,
e outra vez, ata que é deixar con listas de só un tamaño.
Non?
8 vai 4, vai a 2, vai a 1, e iso é
reflexivo que exactamente imaxe, tivemos só un momento atrás.
Entón, un pouco de cordura comprobar de onde o logaritmo é realmente implicados.
>> Entón, agora, o que máis está implicado aquí? n.
Entón, teña en conta que cada xa que dividir a lista,
aínda que na orde inversa da historia aquí, eu estaba facendo as cousas n.
Isto esixe que a fusión etapa Eu toco a cada un dos números,
a fin de deslize- a súa situación axeitada.
Así, aínda que a altura desta diagrama é de tamaño de rexistro n de n ou 3,
En concreto, noutras palabras, Eu fixen tres divisións aquí.
Canto traballo que fixen na horizontal ao longo desta carta de cada vez?
>> Ben, eu fixen n pasos de traballar, porque se eu teño
ten catro elementos e catro elementos, e eu teño fundín-las.
Necesito pasar por estes catro e estes catro,
finalmente, para fundín-los de volta en oito elementos.
Por outra banda eu teño oito dedos aquí, o que eu non fago, e oito
fingers-- sorry-- Se eu teño ten catro dedos aquí,
que fago, catro dedos aquí, o que fago,
entón iso é o mesmo exemplo como antes, se eu fai
ten oito dedos aínda en total, o que podo, tipo, facer.
Podo exactamente facer aquí, entón podo certamente
mesturar todas estas listas de tamaño 1, en conxunto.
Pero eu certamente ten que mirar en cada elemento dunha vez.
Entón, a altura deste proceso é o rexistro N, o ancho do presente proceso, por así dicir,
é n, entón o que parecemos ter, en última instancia, é
unha duración de tamaño n veces rexistro n.
>> Noutras palabras, dividimos lista, log n veces o,
pero cada vez que fixemos iso, tivemos para tocar a cada un dos elementos
a fin de fundín-los todos xuntos, o que
n para paso foi, polo que temos n veces log n, ou como un científico da computación diría,
asintótica, que sería a gran palabra
para describir o superior vinculado nun tempo de execución,
estamos executando nun grande de rexistro n tempo, por así dicir.
>> Agora, iso é significativo, porque recordar que os tempos de execución foron
con bubble sort, e selección tipo e ordenación por inserción,
e mesmo algúns outros que existen, n ao cadrado era onde estabamos.
E pode, tipo, ver este aquí.
Se n ao cadrado é, obviamente, n veces n, pero aquí temos n veces log n,
e xa sabemos desde a semana cero, que log n, a logarítmica,
é mellor que algo lineal.
Ao final, lembrar a imaxe co vermello eo amarelo
e as liñas verdes que sacou, a logarítmica liña verde era moito menor.
E, polo tanto, moito mellor e máis rápido que as liñas amarelas e vermellas en liña recta,
n veces log n é, de feito, mellor que n veces n, ou n ao cadrado.
>> Entón, parece que temos identificou un algoritmo merge
tipo que é executado en moi tempo máis rápido, e de feito,
é por iso que, a principios desta semana, cando vimos que disputa entre burbulla
tipo, especie de selección, e mesturar sort, merge sort realmente, realmente gañou.
E, de feito, non mesmo esperar para bubble sort e selección especie
para rematar.
>> Agora imos dar outra pasaxe para iso, desde un pouco máis
perspectiva formal, só en caso, iso resoa mellor
que maior que o nivel de discusión.
Entón aquí está o algoritmo de novo.
Imos preguntar: o que o tempo de execución
é deste algoritmos varias etapas?
Imos división lo en primeiro caso e no segundo caso.
A SE ea outra persoa no caso IF, Se n é inferior a 2, só volver.
Se sente como tempo constante.
É, tipo, como dous pasos, Se n é inferior a 2, a continuación, volver.
Pero, como dixemos o luns, constante de tempo, ou grande de 1,
pode ser dous, tres pasos pasos, ata 1.000 pasos.
O importante é que é un número constante de pasos.
Así, o amarelo destaque pseudocódigo aquí é executado en, imos chamalo,
constante de tempo.
Entón, máis formalmente, e imos a-- este
será a extensión en que formalizar este dereito agora-- T n,
o tempo de execución dun problema que leva n calquera cousa como entrada,
igualan o o dun, Se n é menor que 2.
Polo tanto, é condicionada a iso.
Entón, para ser claro, se n é inferior a 2, temos unha lista moi curta, entón
o tempo de execución, t n, no que n é 0 ou 1, neste caso moi específico,
el só vai ser de tempo constante.
Vai levar un paso, dous pasos, que sexa.
É un número fixo de etapas.
>> Así, a parte suculenta certamente debe estar en no outro caso no pseudocódigo.
O caso máis.
Ordenar metade esquerda de elementos, tipo certo metade dos elementos, fundir metades ordenados.
Canto tempo dura cada unha destas etapas tomar?
Ben, a carreira tempo para resolver n elementos
é, imos chamalo moi xenericamente, T de N,
a continuación, a selección esquerda metade dos elementos
é, tipo, como dicilo, T n dividido por 2,
e do mesmo xeito clasificando a metade dereita de elementos é, tipo, como dicilo,
T de N 2 dividido e logo fundindo as metades clasificados.
Ben, se eu teño algún número de elementos aquí,
como catro, e algún número de elementos aquí, como catro,
e eu teño que fundir cada un destes catro en, e cada un destes catro, un
despois o outro, de xeito que en definitiva, eu teño oito elementos.
Se sente como que é grande de n pasos?
Se eu teño n dedos e cada un ten que ser incorporado lugar,
que é como máis n pasos.
>> Entón, en realidade, como unha fórmula, podemos expresar isto,
aínda que un pouco assustadoramente en primeiro vista, pero é algo
que capta exactamente esa lóxica.
O tempo de execución, T n, n IF é maior que ou igual a 2.
Neste caso, o caso MÁIS, é T n dividido por dous, ademais de T n dividido por 2,
máis grande de n, algúns lineal número de pasos,
quizais precisamente n, quizais 2 veces n, pero é máis ou menos, a orde de n.
De xeito que, tamén, é como podemos expresar isto como unha fórmula.
Agora non sabería que a menos gravou na súa mente,
ou buscalo no traseira dun libro, que
podería ter un pouco Cabula ao final,
pero que é, de feito, vai ofrécenos un grande n log n,
porque a recorrencia que está a ver aquí na pantalla,
se realmente fixo iso para fóra, con un número infinito de exemplos,
ou fixo iso como unha fórmula, faría ver que esta, porque esta fórmula
en si é recursivo, con t de n sobre algo á dereita,
e t de N ao longo do lado esquerdo, pode de feito, ser expresado, en definitiva,
tan grande para ir de rexistro n n.
Se non está convencido, iso é ben por agora, só
asumir a fe, que é, de feito, o que leva a que a recorrencia,
pero este é só un pouco máis dun visión matemática para ollar
o tempo de execución de merge sort con base só na súa pseudocódigo.
>> Agora imos dar un pouco de respiradoiros de todo isto,
e dar un ollo a un seguro ex senador, que
pode parecer un pouco familiarizado, que sentou-se con Eric de Google
Schmidt, hai algún tempo, para unha entrevista no escenario, diante dun grupo enteiro
de persoas, falando en definitiva, sobre un tema que é moi agora familiar.
Imos dar un ollo.
>> Eric Schmidt: Agora o senador, está aquí en Google,
e eu gusto de pensar no Presidencia como unha entrevista de emprego.
Agora é difícil conseguir un emprego como presidente.
PRESIDENTE OBAMA: Correcto.
Eric Schmidt: E vostede é fará [inaudível] agora.
Tamén é difícil conseguir un emprego en Google.
PRESIDENTE OBAMA: Correcto.
>> Eric Schmidt: Temos preguntas, e pedimos as nosas preguntas candidatos,
e este é de Larry Schwimmer.
>> PRESIDENTE OBAMA: Aceptar.
>> Eric Schmidt: O que?
Vostedes pensan que estou a xogar?
Está ben aquí.
Cal é o xeito máis eficaz de clasificar un millón de 32 bits enteiros?
>> PRESIDENTE OBAMA: bom--
Eric Schmidt: Ás veces, quizais eu sinto moito, maybe--
PRESIDENTE OBAMA: Non, non, non, non, non, eu penso--
Eric Schmidt: Isto non é ele--
PRESIDENTE OBAMA: I creo, eu creo que a burbulla
tipo sería o camiño mal a continuación.
Eric Schmidt: Imos alí.
Quen lle dixo iso?
Aceptar.
Eu non fixen a ciencia da computación on--
>> PRESIDENTE OBAMA: Temos temos os nosos espías dentro.
PROFESOR: Todo ben.
Imos deixar detrás de nós agora o mundo teórica de algoritmos
na análise asintótica do mesmo, e voltar para algúns tópicos
desde a semana cero e un, e de inicio para eliminar algunhas rodinhas,
se quere.
Para que realmente comprender en definitiva, a partir de cero, o que é
pasando baixo o capó, cando escribir, compilar e executar programas.
Teña en conta que, en particular, que este era o primeiro programa C nós miramos,
un programa canónica, simple das sortes, en concepto falando,
en que, imprime, Ola Mundo.
E lembro que eu dixen, o proceso que o código fonte atravesa
é exactamente iso.
Colle o seu código fonte, pasar Lo través dun compilador, como Clang,
e sae código obxecto, que pode parecer como este, ceros e uns
que a CPU do ordenador central unidade de procesamento ou cerebro,
en definitiva, entende.
>> Acontece que isto é unha pouco de unha simplificación,
que estamos agora nun posición de provocar unha separación
para entender o que está realmente foi pasando baixo o capó
cada vez que executa Tinido, ou, máis xeralmente,
cada vez que fai un programa, Fai uso e CF 50 IDE.
En particular, o material como este é xerado primeiro,
cando compilar seu programa.
Noutras palabras, cando levar o seu código fonte
e recompila-lo, o que é primeiro sendo emitido por Clang
é algo coñecido como código de montaxe.
E, de feito, parece exactamente como este.
>> Corre un comando no liña de comandos anterior.
Hello.c Clang de capital trazo s, e iso creou un ficheiro
para min chamados hello.s, no interior dos cales foron exactamente
estes contidos, e un pouco máis arriba e un pouco máis abaixo,
pero eu coloque o juiciest información aquí na pantalla.
E se ollar de preto, podes ver polo menos algunhas palabras clave familiares.
Temos principal na parte superior.
Temos printf abaixo no medio.
E tamén temos Ola mundo barra invertida n entre comiñas continuación.
>> E todo o demais aquí é instrucións de nivel moi baixo
que a CPU do computador entende.
Instrucións da CPU que se moven de memoria arredor, que secuencias de carga de memoria,
e, finalmente, imprimir as cousas na pantalla.
Agora o que pasa aínda despois este código assembly xérase?
En última instancia, fai, de feito, aínda xerar código obxecto.
Pero os pasos que teñen realmente vén acontecendo debaixo do capó
mirar un pouco máis como este.
O código fonte tórnase o código de montaxe, que entón se fai código obxecto,
e as palabras clave aquí é que, cando compilar o código fonte,
vén para fóra do código de montaxe, e, a continuación, cando montar o código da montaxe,
fóra vén código obxecto.
>> Agora Clang é super sofisticado, como unha morea de compiladores,
e fai todas estas etapas xuntos, e fai non necesariamente
saída de calquera intermediario arquivos que vostede mesmo pode ver.
El só compila as cousas, que é o termo xeral que
describe todo este proceso.
Pero se o quere para ser determinado, non hai
moito máis a suceder alí tamén.
>> Pero imos considerar agora que mesmo este programa super sinxelo, hello.c,
chamado dunha función.
Apelou printf.
Pero eu non quería escribir printf, de feito, que vén con c, por así dicir.
É un recall función que é declarou io.h estándar, que
é un ficheiro de cabeceira, que é un tema que imos realmente
mergullo máis fondo antes de tempo.
Pero un ficheiro de cabeceira é tipicamente acompañada
por un ficheiro de código, arquivo de código fonte, así moi parecido existe io.h. estándar
>> Hai algún tempo, alguén, ou de alguén, tamén escribiu
un arquivo chamado io.c estándar, en que a configuración efectivas,
ou implementacións de printf, e acios de outras funcións,
son realmente escrito.
Así, dado que, se considerar ter aquí á esquerda, ola.c, que cando
compilado, dános hello.s, aínda que Clang non se incomoda de aforro nun lugar
podemos velo, e que o código de montaxe fica montada hello.o, que
é, en realidade, o nome predeterminado dado sempre que compilar fonte
código en código obxecto, pero non son completamente listo para executa-lo aínda,
porque un paso ten que pasar, e ten
vén acontecendo nos últimos semanas, quizais sen o seu coñecemento.
>> Especialmente en algún lugar CS50 en IDE, e este,
tamén, vai ser un pouco de un simplificación excesiva por un momento,
non é, ou foi enriba dun tempo, un arquivo chamado io.c estándar,
que alguén compilados io.s estándar ou equivalente,
alguén que, a continuación, montar en io.o estándar,
ou se ve nun arquivo lixeiramente diferente
formato que pode ter un diferente extensión de arquivo completo,
pero, en teoría e conceptualmente, exactamente estes pasos tiña que ocorrer de algunha maneira.
O que significa dicir, que agora cando estou escribindo un programa,
hello.c, que só di: Ola mundo, e eu estou usando o código de outra persoa
como printf, que foi unha vez enriba dun tempo, nun ficheiro chamado io.c estándar,
a continuación, de algunha maneira eu teño que tomar a miña código obxecto, meus ceros e uns,
e obxecto da persoa código, ou ceros e uns,
e dalgunha forma obrigar-los xuntos un arquivo final, chamado Ola, que
ten todos os ceros e os da miña función principal,
e todos os ceros e aqueles para printf.
>> E, de feito, este último proceso é chamada, conectar o seu código obxecto.
A saída dos cales é un ficheiro executábel.
Entón, na xustiza, na final do día, nada
cambiou desde unha semana, cando primeiro comezou a compilar programas.
Efectivamente, todo isto foi pasando baixo o capó,
pero agora estamos nunha posición onde podemos realmente
desmembrar esas varias etapas.
E, de feito, a finais do día, aínda somos
á esquerda con ceros e uns, que é realmente unha boa segue agora
a outra capacidade de C, que nós non tivemos a alavancar máis probable
ata a data, coñecida como operadores bit a bit.
Noutras palabras, ata o momento, en calquera momento temos tratadas con datos variables en C ou C,
tivemos cousas como caracteres e Carrozas e ins
e ansia e dobres e similares, pero todos estes son, polo menos, oito bits.
Temos aínda non foi capaz de manipular bits individuais,
aínda que un bit individual, nós sabe, pode representar un 0 e un 1.
Agora parece que en C, que pode ter acceso a bits individuais,
se sabe a sintaxe, co cal se chegar a eles.
>> Entón, imos dar un ollo en operadores bit a bit.
Entón, retratado aquí están algúns símbolos que temos, tipo de, máis ou menos, visto antes.
Eu vexo un e comercial, vertical bar, e algúns outros tamén,
e recordar que ampersand ampersand é algo que vimos antes.
O operador lóxico AND, onde ten dous deles en conxunto, ou o OU lóxico
operador, onde ten dúas barras verticais.
Operadores bit a bit, o que nós imos vexa operar en anacos individualmente,
non necesitará empregar un único e comercial, un única barra vertical, o símbolo de acento circunflexo
vén a continuación, a pequena til, e despois á esquerda
paréntese esquerdo soporte, ou soporte dereito paréntese dereito.
Cada un deles teñen significados diferentes.
>> De feito, imos dar un ollo.
Imos vella escola hoxe, e uso unha pantalla táctil de outrora,
coñecido como un cadro branco.
E este cadro branco vai permitir
para expresar algúns símbolos moi sinxelo, ou mellor, algúns fórmulas moi sinxelo,
que, a continuación, en definitiva, podemos alavancagem, a fin
para acceder individuo bits dentro dun programa C.
Noutras palabras, imos facelo.
Imos primeiro falar para un momento sobre ampersand,
que é o bit a bit operador AND.
Noutras palabras, esta é un operador que permite
me para ter unha variable á esquerda normalmente, e unha variable da man dereita,
ou un valor individual, que se nos Correo xuntos, me dá un resultado final.
Entón o que quero dicir?
Se nun programa, ten unha variable que almacena un deses valores,
ou imos mantelo simple, e só escriba ceros e uns individualmente,
aquí está como o operador E comercial funciona.
0 0 comercial vai igual a 0.
Agora, por que é isto?
>> É moi semellante ao As expresións booleanas,
que temos discutido ata agora.
Se pensas que despois de todo, o 0 é false, 0 é falso, falso e falso
é, como xa discutir loxicamente, tamén falsa.
Entón, nós temos 0 aquí tamén.
Se tomar 0 e comercial 1, así que, tamén,
será 0, porque para iso expresión da esquerda para ser verdade ou 1,
sería necesario para ser verdade e verdade.
Pero aquí temos false e certa, ou 0 e 1.
Agora, de novo, se temos un E comercial 0, que, tamén, vai ser 0,
e se temos un e comercial 1, finalmente temos un bit 1.
Polo tanto, noutras palabras, non estamos facendo nada interesante con este operador
aínda, este operador comercial.
É o bit a bit operador AND.
Pero estes son os ingredientes a través do cal podemos facer
cousas interesantes, como veremos en breve.
>> Agora imos ollar só o único barra vertical ata aquí, á dereita.
Se eu tivera un bit 0 e I OU-o con, o bit a bit
OU operador, outro bit 0, que me vai dar 0.
Se eu tomar un bit 0 e OU-lo con un bit 1, entón eu estou indo a obter un.
E, de feito, só para claridade, déixeme volver,
de xeito que as miñas barrotes verticais non son confundidos con 1s.
Déixeme reescribir todo meu 1 é un pouco máis
claramente, para que poidamos ver a carón, se eu ter un 1 ou 0, que vai ser un 1,
e se eu tivera un 1 ou 1 que, tamén, será un 1.
Así pode ver que a lóxica OR operador compórtase de xeito moi diferente.
Isto dáme OU 0 0 0 me dá, pero cada outra combinación dáme unha.
Entón, mentres eu tivera un 1 no fórmula, o resultado será unha.
>> En contraste coa E operador, o comercial,
só se eu teño dous números 1 no ecuación, realmente obter un 1.
Agora hai algúns outros operadores tamén.
Un deles é un pouco máis complicado.
Entón deixe-me ir adiante e eliminar esta para liberar algún espazo.
E imos dar un ollo ao símbolo de acento circunflexo, por só un momento.
Este é normalmente un personaxe que podes escribir
no seu teclado e sostendo Shift a continuación, un dos números enriba do seu EUA
teclado.
>> Entón que é o único Operador OU OU exclusivo.
Entón, nós só viu o operador OR.
Este é o OR exclusivo do operador.
O que é realmente a diferenza?
Ben, imos só ollar para a fórmula, e usar isto como ingredientes en última instancia.
0 XOR 0.
Eu vou dicir é sempre 0.
Esa é a definición de XOR.
XOR 0 1 será 1.
1 XOR 0 será 1, e un XOR 1 será?
Mal?
Ou non é?
Eu non sei.
0.
Agora, o que está pasando aquí?
Ben, pense sobre o nome deste operador.
OU exclusivo, para nome, tipo, suxire,
a resposta só será 1 as entradas son exclusivas,
exclusivamente diferente.
Entón, aquí están as entradas do mesma, de xeito que a saída é 0.
Aquí as entradas son o mesma, de xeito que a saída é 0.
Aquí están as saídas son diferentes, son exclusivos, e entón a saída é 1.
Polo tanto, é moi semellante ao E, é moi semellante,
ou mellor, é moi semellante ao OU, pero só de forma exclusiva.
Este non é un 1, porque temos dous de 1,
e non exclusivamente, só un deles.
Todo ben.
E os outros?
Ben o til, mentres, é realmente agradable e simple, por sorte.
E esta é unha unary operador, o que significa
aplicarase só unha entrada, un operando, por así dicir.
Non a un dereito e un dereito.
Noutras palabras, se tomar til de 0, a resposta será o contrario.
E se tomar til de 1, o resposta haberá o contrario.
Así, o operador til é unha forma de negar un pouco,
ou virar un pouco de 0 a 1, ou de 1 a 0.
>> E iso déixanos finalmente con só dous operadores finais,
o chamado desprazamento cara á esquerda, eo o chamado operador de desprazamento cara á dereita.
Imos dar un ollo a como os traballos.
O operador de desprazamento cara á esquerda, por escrito con dous corchetes como esta,
opera deste xeito.
Se a miña entrada, ou a miña operando, á esquerda operador de desprazamento é simplemente un 1.
E eu, a continuación, dicir ao ordenador para desvío á esquerda que unha, digamos sete prazas,
o resultado é como se eu tomar esta 1, e movelo
sete lugares máis á esquerda e, por defecto,
imos supor que o espazo á dereita
será cuberto con ceros.
Noutras palabras, un cambio deixou 7 vai para me dar que 1, seguido por 1, 2, 3,
4, 5, 6, 7 ceros.
Entón, de certa forma, permite que ter un número pequeno como 1,
e facelo moi claramente moi, moi grande, deste xeito,
pero nós estamos indo realmente para ver enfoques máis intelixentes para el
Pola contra, como ben,
>> Todo ben.
É isto por tres semanas.
Imos velo a próxima vez.
Este foi CS50.
>> [Música tocando]
>> COLUMNA 1: Estaba no snack- bar comendo un sundae de chocolate.
Tiña todo sobre o seu rostro.
El está a levar posto que o chocolate como unha barba
COLUMNA 2: O que está facendo?
COLUMNA 3: Hmmm?
Que?
>> COLUMNA 2: Vostede acaba de dobre mergullo?
Vostede dobre mergullou o chip.
COLUMNA 3: Desculpe-me.
COLUMNA 2: Vostede é dicir o chip, vostede deu unha mordida, e mergullou novo.
COLUMNA 3:
COLUMNA 2: Así que é como poñer todo o seu dereito boca no mergullo.
A próxima vez que tomar un chip, só mergullalos lo unha vez, e remata-la.
>> COLUMNA 3: Vostede sabe o que, Dan?
Mergulla a forma que sexa mergullo.
Vou mergullo a forma que eu quero mergullo.