>> [Música tocando]
DAVID MALAN: Tudo bem.
Tudo bem, bem-vindo de volta.
Portanto, esta é a Semana 4, o início º, já.
E você vai lembrar que, na semana passada, colocamos código de lado por um pouco
e começamos a conversar um pouco mais de alto nível, sobre coisas como
pesquisa e classificação, que embora ideias são simples, pouco
representativo de uma classe de problemas você vai começar a resolver particularmente
como você começar a pensar em último projetos e soluções interessantes que você
pode ter de problemas do mundo real.
Agora bubble sort é um dos mais simples tais algoritmos, e
Trabalhou por ter estes pequenos números em uma lista ou em um tipo conjunto de
bolha seu caminho até o topo, eo grandes números mover seu caminho até
o fim da lista.
>> E lembrar que pudéssemos visualizar bubble sort um pouco
algo como isto.
Então deixe-me ir em frente e clique em Iniciar.
Eu já pré-selecionado bubble sort.
E se você lembrar que o azul mais alto linhas representam números grandes, pequenas
linhas azuis representam pequenos números, como passamos por isso de novo e de novo e
mais uma vez, comparando duas barras de lado a lado outra em vermelho, vamos trocar o
maior eo menor se eles estão fora de ordem.
>> Então, isso vai continuar e continuar e ir , e você verá que a maior
elementos estão fazendo seu caminho para o direito, e os elementos menores são
fazendo o seu caminho para a esquerda.
Mas começamos a quantificar a eficiência, a
qualidade deste algoritmo.
E nós dissemos que, no pior caso, este algoritmo levou
aproximadamente quantos passos?
>> Então n ao quadrado.
E o que era n?
>> AUDIÊNCIA: Número de elementos.
>> DAVID MALAN: Então n foi o número de elementos.
E assim nós vamos fazer isso muitas vezes.
Toda vez que quero falar sobre o tamanho de um problema ou o tamanho de um
entrada, ou a quantidade de tempo que leva para produzir uma saída, vamos
generalizada o que a entrada é como n.
Então, de volta na Semana 0, o número de páginas na lista telefônica foi n.
O número de estudantes na sala foi n.
Então, aqui, também, que estamos seguindo esse padrão.
>> Agora n ao quadrado não é particularmente rápido, então nós tentamos fazer melhor.
E assim, nós olhamos um par de outros algoritmos, entre os quais
foram seleção espécie.
Assim, a seleção espécie foi um pouco diferente.
Era quase mais simples, ouso dizer, qual I iniciada no começo do
Lista dos nossos voluntários e eu novamente e outra vez passou por
Na lista, arrancar a menor elemento de cada vez e colocá-lo ou
ela no início da lista.
>> Mas isso, também, uma vez que começamos a pensar através da matemática e maior
imagem, pensou em quantas vezes Eu estava indo para trás e para frente e para trás
e para trás, nós dissemos, no pior caso, seleção espécie, também, era o quê?
n ao quadrado.
Agora, no mundo real, ele pode na verdade, ser ligeiramente mais rápido.
Porque mais uma vez, eu não tenho que manter retrocesso, uma vez que eu tinha ordenado a
menores elementos.
Mas se pensarmos muito grande n, e se você tipo de fazer a matemática como
Eu fiz no tabuleiro, com o n ao quadrado menos alguma coisa, tudo o resto
além do n ao quadrado, uma vez que n fica muito grande, não
realmente importa tanto.
Assim como os cientistas da computação, que espécie de fechar os olhos para o menor
fatores e se concentrar apenas no fator de uma expressão que vai fazer
a maior diferença.
>> Bem, finalmente, nós olhamos a ordenação por inserção.
E este foi semelhante em espírito, mas ao invés de passar por iterativa e
selecionar o menor elemento de um tempo, em vez tomou a mão que eu
foi tratado, e eu decidi, tudo certo, você pertence aqui.
Em seguida, mudei-me para o próximo elemento e decidiu que ele ou
ela pertencia aqui.
E então eu segui em frente e continuar.
E eu poderia para, ao longo do caminho, mudar esses caras, a fim de
dar espaço para eles.
Então isso foi uma espécie de inversão mentais de seleção tipo que
chamado ordenação por inserção.
>> Então, esses temas para ocorrer no mundo real.
Apenas alguns anos atrás, quando um determinado senador estava concorrendo à presidência,
Eric Schmidt, no momento em que o CEO da Google, na verdade, tive a oportunidade
entrevistá-lo.
E nós pensamos em compartilhar esse YouTube clipe para você aqui, se pudéssemos transformar-se
o volume.
>> [REPRODUÇÃO]
>> -Agora, o senador, você está aqui no Google, e eu gosto de pensar na presidência
como uma entrevista de emprego.
>> [Risos]
>> -Agora é difícil conseguir um emprego como presidente.
E você está passando os rigores agora.
Também é difícil conseguir um emprego no Google.
Temos perguntas e pedimos Nossos candidatos perguntas.
E este é de Larry Schwimmer.
>> [Risos]
-Vocês pensam que eu estou brincando?
É aqui mesmo.
Qual é a maneira mais eficiente para ordenar um milhão de números inteiros de dois bits?
>> [Risos]
>> -Bem, uh -
>> -Sinto muito.
Talvez devêssemos -
>> -Não, não, não, não, não.
>> -Isso não é uma -
OK.
>> -Eu acho que o bubble sort seria ser o caminho errado.
>> [Risos]
>> [Aclamações e aplausos]
>> -Vamos, que lhe disse isso?
OK.
>> [FIM REPRODUÇÃO DE VÍDEO]
>> DAVID MALAN: Então você tem isso.
Então começamos a quantificar estes execução vezes, por assim dizer, com algo
chamado notação assintótica, que é apenas referindo-se a nossa espécie de transformar
os olhos para esses fatores menores e apenas olhando para o tempo de execução,
o desempenho destes algoritmos, como n fica muito grande ao longo do tempo.
E assim, nós introduzimos grande O. e Big O representava algo que pensávamos
como um limite superior.
E, na verdade, Barry, podemos diminuir que o microfone um pouco?
>> Nós pensamos que isso é um limite superior.
Tão grande S de n significa que, em quadrado pior das hipóteses, algo como
seleção tipo levaria n passos quadrado.
Ou algo parecido com a ordenação por inserção seria n passos quadrado.
Agora, para algo como a inserção tipo, qual foi o pior caso?
Dado um array, que é o pior cenário possível, que você pode encontrar
se depara com?
>> É completamente para trás, certo?
Porque se é completamente para trás, você tem que fazer um monte de trabalho.
Porque se você está completamente para trás, você vai encontrar o
maior elemento aqui, embora pertence lá.
Então você vai dizer, tudo bem, a Neste momento, você pertence aqui,
assim que você deixá-lo sozinho.
>> Então você percebe, oh, droga, eu tenho que mover este elemento ligeiramente menor para
à esquerda de você.
Então eu tenho que fazer isso de novo e de novo e de novo.
E se eu andei para trás e para a frente, você se classificar de sentir o desempenho dos
que o algoritmo, pois constantemente eu sou baralhar todos os outros para baixo na
matriz para fazer o quarto para ele.
Então esse é o pior caso.
>> Por outro lado -
e isso foi um cliffhanger última vez -
dissemos que a ordenação por inserção era um omega de quê?
Qual é o melhor caso running momento da inserção do tipo?
Então, é realmente n.
Esse era o vazio que deixou no quadro da última vez.
>> E é omega de n porque porquê?
Bem, no melhor caso, o que é ordenação por inserção vai ser entregue?
Bem, a lista que está completamente resolvido já, o mínimo de trabalho para fazer.
Mas o que é interessante sobre a ordenação por inserção é que, porque começa aqui e
decide, oh, você é o número um, você pertence aqui.
Oh, o que uma boa fortuna.
>> Você é o número dois.
Você também pertenço aqui.
Número três, melhor ainda, você pertence aqui.
Assim que se chega ao fim da pseudocódigo lista, por inserção de tipo
que atravessou verbalmente última vez, ele é feito.
Mas a seleção tipo, pelo contrário, continuei a fazer o quê?
>> Continuei a lista novo e de novo e de novo.
Porque o conhecimento chave que só havia uma vez que você olhou para todo o caminho para a
final da lista você pode estar certo que o elemento que foi selecionado
de fato o menor elemento atualmente.
Então, esses diferentes modelos mentais final cedendo alguns muito real-world
diferenças para nós, assim como esses diferenças assintóticas teóricas.
>> Então, só para recapitular, então, grande O de n quadrado, temos visto alguns como
algoritmos até agora.
Big O de n?
O que é um algoritmo que poderia ser dito para ser grande O de n?
No pior dos casos, leva uma série linear de passos.
>> OK, pesquisa linear.
E no pior caso, onde está o elemento que você está procurando quando
aplicação de pesquisa linear?
>> OK, no pior caso, não é mesmo lá.
Ou o segundo pior caso, é todo o caminho no final, o que é
mais-ou-menos uma diferença de uma etapa.
Assim, no final do dia, podemos dizer que é linear.
Big O de n seria de busca linear, porque, no pior caso, o
elemento não está lá ou é todo o caminho no final.
>> Bem, O grande de log de n.
Nós não falamos em detalhes sobre isso, mas já vi isso antes.
O que é executado no chamado logarítmica tempo, no pior dos casos?
>> Sim, pesquisa de modo binário.
E busca binária no pior caso pode ter o elemento em algum lugar
no meio, ou em algum lugar no interior da matriz.
Mas você só encontrá-lo uma vez que você dividir a lista pela metade, em
metade, pela metade, pela metade.
E, em seguida, voila, ele está lá.
Ou ainda, pior caso, não é mesmo lá.
Mas você não sabe que ele não está lá até que você espécie de chegar a esse último
baixo para a maioria dos elementos de reduzir para metade e reduzir para metade e reduzir para metade.
>> Big O de 1.
Para que pudéssemos grande O de 2, O grande de 3.
Sempre que você quiser apenas um número constante, nós apenas uma espécie de apenas simplificar
que ó tão grande de uma.
Mesmo que se realisticamente, é preciso 2 ou até 100 passos, se é um
número constante de passos, que acabamos de dizer grande O de 1.
O que é um algoritmo que é em grande O de 1?
>> AUDIÊNCIA: Encontrar o comprimento de uma variável.
>> DAVID MALAN: Encontrar o comprimento de uma variável?
>> AUDIÊNCIA: Não, o comprimento se ele já está classificada.
>> DAVID MALAN: Ótimo.
OK, assim que encontrar o comprimento de algo Se o comprimento de que alguma coisa, como
uma matriz, é armazenada em alguma variável.
Porque você pode apenas ler a variável, ou imprimir a variável, ou
geralmente só acessar essa variável.
E voila, que leva tempo constante.
>> Por outro lado, acho que volta a zero.
Pense na primeira semana de C, chamando apenas printf e impressão
algo na tela é sem dúvida constante de tempo, porque ele só leva
um certo número de ciclos de CPU para mostrar que o texto no ecrã.
Ou esperar - não é?
De que outra forma poderíamos modelar o desempenho do printf?
Será que alguém gostaria de discordar, que talvez não seja o tempo realmente constante?
Em que sentido pode printf está funcionando tempo, na verdade, a impressão de uma corda em
tela, ser algo excepto constante.
>> AUDIÊNCIA: [inaudível].
>> DAVID MALAN: Yeah.
Por isso, depende da nossa perspectiva.
Se nós realmente acho que a entrada para printf como sendo a string, e
portanto, podemos medir o tamanho desse entrada pelo seu comprimento - então vamos chamá
que o comprimento n, bem como -
sem dúvida, printf é a própria grande O de n porque ele vai levá-lo n passos
para imprimir cada um dos n caracteres, provavelmente.
Pelo menos na medida em que assumimos que, talvez, ele está usando um laço for
debaixo do capô.
>> Mas teríamos de olhar para isso Código para entender melhor.
E, de fato, uma vez que vocês começarem analisar seus próprios algoritmos, você vai
literalmente fazer exatamente isso.
Espécie de globo ocular seu código e pensar sobre - tudo bem, eu tenho esse laço
aqui ou eu tenho laços aninhados aqui, que vai fazer n coisas n vezes,
e você pode classificar de razão o seu caminho através do código, mesmo que seja
pseudocódigo e não o código real.
>> Assim que sobre omega de n ao quadrado?
O que era um algoritmo que na melhor caso, ainda levou n passos quadrados?
Sim?
>> AUDIÊNCIA: [inaudível].
>> DAVID MALAN: Então seleção espécie.
Devido a este problema muito reduzida ao fato de que mais uma vez, eu não sei
Eu encontrei o atual menor até Eu chequei todos os elementos danado.
Assim omega de, digamos, n, só veio com um.
Ordenação por inserção.
Se a lista passa a ser classificada já, na melhor das hipóteses, só temos
para fazer uma passagem através dela, no ponto em que temos a certeza.
E, em seguida, que pode ser dito ser linear, com certeza.
>> Que tal omega de 1?
O que, na melhor das hipóteses, pode demorar um número constante de etapas?
Pesquisa de modo linear, se você apenas ter sorte eo elemento que você está procurando
é logo no início da lista, se esse é o lugar onde você está começando seu
linear transversal dessa lista.
>> E isso é verdade de um série de coisas.
Por exemplo, mesmo binário pesquisa é omega de 1.
Porque se você ficar muito danado sorte e smack-dab no meio de
sua matriz é o número você está procurando?
Assim, você pode ter sorte lá, também.
>> Este, por último, omega de n log n.
Então n log n, nós realmente não falar ainda, mas -
>> AUDIÊNCIA: merge sort?
>> DAVID MALAN: merge sort.
Esse foi o gancho da última vez, onde propusemos, e nós mostramos
visualmente, que existem algoritmos.
E uma espécie de apenas um desses fundir algoritmo que é fundamentalmente mais rápido
que alguns desses outros caras.
Na verdade, fundir curto é não só no melhor caso n log n, no pior
caso n log n.
E quando você tem essa coincidência de omega e grandes O ser a mesma coisa?
Na verdade, podemos descrever isso como o que é chamada theta, embora seja um
pouco menos comum.
Mas isso significa apenas que os dois limites, neste caso, são as mesmas.
>> Então, merge sort, o que isso realmente se resumem a para nós?
Bem, lembre-se a motivação.
Deixa-me tirar-se outra animação que nós não olhar pela última vez.
Este, mesma idéia, mas é um pouco maior.
E eu estou indo para ir em frente e apontar primeiro - temos ordenação por inserção em
canto superior esquerdo, em seguida, a seleção de classificação, bubble sort, a par de outros tipos -
shell e rápidos - que não falamos aproximadamente, e heap e merge sort.
>> Assim, pelo menos, tentar focar seus olhos em os três principais da esquerda e depois
merge sort quando eu clico esta seta verde.
Mas eu vou deixar todos eles executados, apenas para dar-lhe um sentido da diversidade de
algoritmos que existem no mundo.
Eu vou deixar esta corrida por apenas alguns segundos.
E se você concentrar seus olhos - escolha um algoritmo, focar-lo por apenas um
segundo - você vai começar a ver o padrão que é de execução.
>> Merge sort, aviso prévio, está feito.
Heap espécie, tipo rápida, shell -
assim parece que introduziu a três piores algoritmos na semana passada.
Mas isso é bom que estamos aqui hoje para olhar para merge sort, que é um dos
o mais fácil é olhar, mesmo embora ele provavelmente irá dobrar sua mente
só um pouquinho.
Aqui podemos ver o quanto seleção espécie é uma merda.
>> Mas, por outro lado, é muito fácil de implementar.
E talvez para P Set 3, que é um dos algoritmos que você escolheu para implementar
para a edição standard.
Perfeitamente bem, perfeitamente correto.
>> Mas, novamente, como n se torna grande, se você optar por implementar um algoritmo mais rápido
como merge sort, as probabilidades são em maior e insumos maiores, o código é apenas
vai correr mais rápido.
Seu site vai funcionar melhor.
Seus usuários estão indo para ser feliz.
E por isso há esses efeitos de realmente dar
nos algum pensamento mais profundo.
>> Então, vamos dar uma olhada no que fundem espécie é realmente tudo.
O legal é que a fusão tipo é só isso.
Isto é, mais uma vez, o que nós chamamos pseudocódigo, ser pseudocódigo
Inglês-como sintaxe.
E a simplicidade é espécie de fascinante.
>> Então, na entrada de n elementos - para que significa apenas que, aqui está um array.
Tem coisas n nele.
Isso é tudo o que estamos dizendo aqui.
>> Se n for menor do que 2, o retorno.
Então, isso é apenas o caso trivial.
Se n for menor do que 2, em seguida, é obviamente 1 ou 0, caso em que a coisa
já está classificado ou inexistente, por isso só voltar.
Não há nada a fazer.
Então, isso é um caso simples de arrancar fora.
>> Caso contrário, nós temos três etapas.
Classificar a metade esquerda dos elementos, tipo a metade direita dos elementos,
e em seguida, mesclar as duas metades ordenadas.
O que é interessante aqui é que Eu sou o tipo de punting, certo?
Há uma espécie de definição circular para esse algoritmo.
Em que sentido é este algoritmo de circular definição?
>> AUDIÊNCIA: [inaudível].
>> DAVID MALAN: Sim, o meu algoritmo de ordenação, dois de seus passos são "espécie
alguma coisa. "E assim que levanta a questão, bem, o que eu vou usar
para classificar a metade esquerda ea metade direita?
E a beleza aqui é que, apesar de mais uma vez, este é o alucinante
parte potencialmente, você pode usar mesmo algoritmo para classificar a metade esquerda.
>> Mas espere um minuto.
Quando você disse para classificar a metade esquerda, quais são os dois
etapas vai ser o próximo?
Vamos resolver a metade esquerda da meia esquerda e à direita
a metade da metade esquerda.
Caramba, como faço para classificar os dois metades, ou em quartos, agora?
>> Mas isso é OK.
Temos um algoritmo de classificação aqui.
E mesmo que você pode se preocupar em pela primeira vez esta é uma espécie de infinito
loop, é um ciclo que nunca vai acabar - ele vai
acabar de uma vez o que acontece?
Uma vez que n é inferior a 2.
Que eventualmente vai acontecer, porque se você continuar e reduzir para metade
reduzir para metade em reduzir para metade dessas metades, com certeza eventualmente, você vai acabar
com apenas 1 ou 0 elementos.
Em que ponto, este algoritmo diz que você está feito.
>> Portanto, a verdadeira magia neste algoritmo parece estar em
esse passo final, a fusão.
Essa idéia simples, apenas fusão de dois coisas, que é o que finalmente vai
que nos permitem classificar uma matriz de, digamos, oito elementos.
Então, eu tenho mais oito bolas de stress up aqui, oito pedaços de papel, e uma
Google Glass -
que eu tenho que manter.
>> [Risos]
>> DAVID MALAN: Se pudéssemos ter oito voluntários, e vamos ver se podemos
jogar isso, então.
Uau, OK.
Ciência da computação está ficando divertido.
Tudo bem.
Então, que tal você três, maior mão lá em cima.
Quatro na parte de trás.
E quanto a nós vamos fazer você três nessa linha?
E quatro na frente.
Então você oito, vamos para cima.
>> [Risos]
>> DAVID MALAN: Na verdade eu sou não sei o que é.
São as bolas de stress?
As lâmpadas de mesa?
O material?
A internet?
>> OK.
Então vamos lá para cima.
Quem gostaria -
continuam aparecendo.
Vamos ver.
E isso coloca você no local -
você está em uma localização.
Uh-oh, espere um minuto.
1, 2, 3, 4, 5, 6, 7 - oh, bom.
Tudo bem, estamos bem.
Tudo bem, então todos têm assento, mas não no vidro do Google.
Deixe-me fazer fila estes acima.
Qual é o seu nome?
>> MICHELLE: Michelle.
>> DAVID MALAN: Michelle?
Tudo bem, você começa a olhar como o geek, se está tudo OK.
Bem, eu também, eu suponho, apenas por um momento.
Tudo bem, espera.
Estamos tentando chegar a um caso de uso para o Google de vidro, e nós
pensei que seria divertido fazer apenas isso quando as pessoas estão no palco.
Vamos gravar o mundo a partir de sua perspectiva.
Tudo bem.
Não provavelmente o Google pretendia.
Tudo bem, se você não me importo de usar isso para os próximos minutos difíceis,
que seria maravilhoso.
>> Tudo bem, então temos aqui um conjunto de elementos, e que a matriz, de acordo com a
pedaços de papel nessas pessoas ' mãos, está atualmente sem classificação.
>> MICHELLE: Oh, isso é tão estranho.
>> DAVID MALAN: É praticamente aleatória.
E, em apenas um momento, vamos tentar para implementar espécie se fundem
e ver onde esse insight chave.
E o truque aqui com merge sort é algo que não assumiram ainda.
Nós realmente precisa de algum espaço adicional.
Então, o que vai ser particularmente interessante sobre isso é que estes
caras vão se movimentar um pouco pouco, porque eu estou indo supor que
há um conjunto extra de espaço, dizer, logo atrás deles.
>> Então, se eles estão por trás de sua cadeira, que é a matriz secundária.
Se eles estão sentados aqui, isso é a matriz primária.
Mas este é um recurso que nós temos não aproveitados, até agora, com bolha
tipo, com a seleção de tipo, com a ordenação por inserção.
Lembre-se, na semana passada, todo mundo tipo de embaralhadas no lugar.
Eles não usam qualquer memória adicional.
Fizemos espaço para as pessoas por movimentação de pessoas ao redor.
>> Portanto, esta é uma visão de chave, também.
Há esse trade-off, em geral, em informática, de recursos.
Se você quiser acelerar algo como o tempo, você vai
tem que pagar um preço.
E um desses preços é muitas vezes espaço, a quantidade de memória ou disco
espaço em disco que você está usando.
Ou, francamente, a quantidade programador de tempo.
Quanto tempo você leva, o ser humano, para realmente implementar um pouco mais
algoritmo complicado.
Mas, por hoje, o trade-off é tempo e espaço.
>> Então, se vocês pudessem apenas segurar o seu números para que possamos ver que você é
de facto correspondente 4, 2, 6, 1, 3, 7, 8.
Excelente.
Então eu vou tentar orquestrar coisas, se vocês podem apenas
seguir minha liderança aqui.
>> Então, eu estou indo para implementar, em primeiro lugar, o primeiro passo do pseudocódigo, que é
na entrada de n elementos, se n for inferior a 2, depois de voltar.
Obviamente, que não faz aplicam-se, por isso, seguir em frente.
Assim classificar a metade esquerda dos elementos.
Então isso significa que eu vou focar a minha atenção por um momento sobre estes
quatro caras aqui.
Tudo bem, o que posso fazer na próxima?
>> AUDIÊNCIA: classificar a metade esquerda.
>> DAVID MALAN: Então agora eu tenho que classificar a metade esquerda desses caras.
Porque mais uma vez, assumir para si a objetivo é classificar a metade esquerda.
Como você faz isso?
Basta seguir as instruções, mesmo que nós estamos fazendo isso de novo.
Assim classificar a metade esquerda.
Agora estou classificando esses dois caras.
O que vem a seguir?
>> AUDIÊNCIA: classificar a metade esquerda.
>> DAVID MALAN: classificar a metade esquerda.
Então, agora estes, este lugar aqui, é uma lista de tamanho 1.
E qual é o seu nome?
>> PRINCESA DAISY: Princesa Daisy.
>> DAVID MALAN: Princesa Daisy está aqui.
E assim ela já está classificado, porque a lista é de tamanho 1.
O que posso fazer na próxima?
OK, voltar, porque essa lista é de tamanho 1, que é inferior a 2.
Então qual é o próximo passo?
E agora você tem que tipo de voltar atrás em sua mente.
>> Classificar a metade direita, o que é -
qual é o seu nome?
>> LINDA: Linda.
>> DAVID MALAN: Linda.
E então, o que fazemos agora que temos uma lista de tamanho 1?
>> AUDIÊNCIA: Return.
>> DAVID MALAN: Cuidado.
Voltamos primeiro, e agora o terceiro etapa - e se eu tipo de representá-lo por
abraçando os dois assentos agora, agora eu tem que juntar estes dois elementos.
Então, agora, infelizmente, os elementos estão fora de ordem.
Mas é aí que o processo de fusão começa a ficar atraente.
>> Então, se vocês poderiam levantar-se para apenas um momento, eu vou precisar de você, em um
momento, para o passo atrás de sua cadeira.
E se Linda, porque é 2 menor do que 4, por que não
você chega perto em primeiro lugar?
Fique aí.
Então, Linda, que você chega perto pela primeira vez.
>> Agora, na realidade, se é apenas uma matriz pudéssemos levá-la em tempo real
a partir desta cadeira a este ponto.
Então, imagine que tomou alguma constante um número de passos.
E agora -
mas precisamos colocá-lo em o primeiro local aqui.
>> E agora, se você pudesse vir por aí, bem, vamos
estar no local dois.
E mesmo que este se sente como se fosse tomando um tempo, o que é bom agora é
que a metade esquerda da metade esquerda agora está classificada.
Então, qual foi o próximo passo, se agora retroceder ainda mais na história?
>> AUDIÊNCIA: A metade direita.
>> DAVID MALAN: classificar a metade direita.
Então, vocês tem que fazer isso, também.
Então, se você pode levantar-se apenas por um momento?
E qual é o seu nome?
>> JESS: Jess.
>> DAVID MALAN: Jess.
OK, então Jess é agora a esquerda metade da metade direita.
E assim ela é uma lista de tamanho 1.
Ela está obviamente classificados.
E o seu nome?
>> MICHELLE: Michelle.
>> DAVID MALAN: Michelle é, obviamente, uma lista de tamanho 1.
Ela já está classificada.
Então, agora a mágica acontece, o processo de fusão.
Então, quem vai vir em primeiro lugar?
Obviamente, a Michelle.
Então, se você poderia vir em torno de volta.
O espaço que temos disponível para ela agora está bem atrás nesta cadeira aqui.
E agora, se você pudesse voltar, bem como, temos agora, para ser claro, dois
metades, cada uma de tamanho 2 -
e apenas por causa da representação, se poderia fazer um pouco de espaço -
um deixou metade aqui, um metade aqui.
>> Retroceder ainda mais na história.
Qual é o próximo passo?
>> AUDIÊNCIA: Mesclar.
>> DAVID MALAN: Portanto, agora temos de mesclar.
Então, OK, então agora, felizmente, nós só liberou quatro cadeiras.
Então, usei o dobro da memória, mas podemos dar flip-flop entre
duas matrizes.
Então, qual é o número que vir primeiro?
Então, Michelle, obviamente.
Então, volta e pegue o seu lugar aqui.
E, em seguida, o número 2 é obviamente Em seguida, assim que você vir aqui.
Número 4, número 6.
E mais uma vez, mesmo que não haja uma pouco de andar envolvido,
realmente, estas poderiam acontecer imediatamente, , movendo uma -
OK, bem jogado.
>> [Risos]
>> DAVID MALAN: E agora estamos em muito boa forma.
A metade esquerda da totalidade entrada já foi resolvido.
Tudo bem, então esses caras tinham a vantagem de a minha -
como foi terminar todas as meninas na à esquerda e todos os meninos do lado direito?
>> OK, então caras "virar agora.
Então eu não vou levá-lo através estes passos.
Vamos ver se podemos reaplicar o mesmo pseudocódigo.
Se você quiser ir em frente e levantar-se, e vocês, deixe-me dar-lhe o microfone.
Veja se você não pode replicar o que que fizemos aqui no
outra extremidade da lista.
Quem precisa falar primeiro, baseado no algoritmo?
Então explique o que você está fazendo antes de de fazer quaisquer movimentos do pé.
>> COLUNA 1: Tudo bem, então desde Eu sou a metade esquerda da
metade esquerda, eu volto.
Certo?
>> DAVID MALAN: Ótimo.
>> COLUNA 1: E então -
>> DAVID MALAN: Quem faz o microfone ir para o próximo?
>> COLUNA 1: número seguinte.
>> COLUNA 2: Então, eu sou a metade direita da metade esquerda do
metade esquerda, e eu voltar.
>> DAVID MALAN: Ótimo.
Você voltar.
Então, agora, qual é a próxima para vocês dois?
>> COLUNA 2: Queremos ver quem é menor.
>> DAVID MALAN: Exatamente.
Queremos fundir.
O espaço que vamos usar para fundir você em, mesmo que sejam
obviamente, já classificado, vamos a seguir o mesmo algoritmo.
Então, quem vai em primeiro?
Então, 3, e, em seguida, 7.
E agora o microfone vai para esses caras, OK?
>> COLUNA 3: Então, eu sou a metade direita do metade esquerda e meu n é inferior a
1, então eu só vou passar -
>> DAVID MALAN: Ótimo.
>> COLUNA 4: Eu sou a metade direita do metade direita do lado direito, e eu sou
também uma pessoa, por isso estou vai voltar.
Então, agora que se fundem.
>> COLUNA 3: Então vamos voltar.
>> DAVID MALAN: Então você vai para a parte de trás.
Então, 5 vai em primeiro lugar, em seguida, 8.
E agora público, que é o passo temos que voltar agora
voltar para em nossas mentes?
>> AUDIÊNCIA: Mesclar.
>> DAVID MALAN: Fusão meia esquerda e direita a metade da metade esquerda inicial.
Então, agora -
e só para deixar isso claro, fazer um pouco de espaço
entre vocês dois.
Portanto, agora que é as duas listas, esquerda e direita.
Então, como vamos agora unir a vocês em a primeira fila de assentos de novo?
>> 3 vai pela primeira vez.
Então, 5, obviamente.
Em seguida, 7, e agora 8.
OK, e agora nós estamos?
>> AUDIÊNCIA: Não feito.
>> DAVID MALAN: Não feito, porque Obviamente, há uma única etapa restante.
Mas, novamente, a razão que eu estou usando esta jargão como "retroceder em sua mente"
é porque isso é realmente o que está acontecendo.
Estamos passando por todas essas etapas, mas nós somos uma espécie de pausa para um
momento, o mergulho mais profundo na algoritmo, parando por um momento,
mergulho mais fundo no algoritmo, e agora temos a sorte de retrocesso em nossa
mentes e desfazer todas essas camadas que temos uma espécie de colocar em espera.
>> Portanto, agora temos duas listas de tamanho 4.
Se vocês pudessem levantar-se uma última vez e fazer um pouco de espaço aqui para
tornar claro que esta é a esquerda metade do original, o
metade direita do original.
Quem é o primeiro número que precisa puxar na parte de trás?
Michelle, é claro.
>> Então nós colocamos Michelle aqui.
E quem tem o número 2?
Número 2 vem na parte de trás também.
Número 3?
Excelente.
Número 4, número 5, número 6, o número 7, e o número 8.
>> OK, por isso parecia muito de passos, com certeza.
Mas agora vamos ver se não podemos confirmar tipo de intuitivamente que este
algoritmo fundamental, especialmente no que n fica muito grande, como já vimos
com as animações, é fundamentalmente mais rápido.
Então, eu reivindico este algoritmo, no pior caso, e mesmo no melhor dos casos,
é grande O de n log n vezes.
Ou seja, há algum aspecto deste algoritmo que leva n passos, mas
há um outro aspecto em algum lugar iteração, que looping, que
leva log n passos.
Podemos colocar o dedo sobre o que os dois números estão se referindo?
Bem, onde -
o microfone pra onde ir?
>> COLUNA 1: Será que o log n ser quebrando-nos em dois -
dividindo por dois, essencialmente.
>> DAVID MALAN: Exatamente.
Toda vez que vemos em qualquer algoritmo, portanto, agora, não tem sido esse padrão de
divisória, dividindo, dividindo.
E é normalmente reduzida a algo que é
logarítmica, base 2 log.
Mas pode realmente ser qualquer coisa, mas log base 2.
>> Agora, o que dizer do n?
Eu posso ver que tipo de dividido você homens - divididos você, divididos você,
divididos você, divididos você.
Onde é que o fim vem?
>> Portanto, é a fusão.
Porque pensar nisso.
Quando você mescla oito pessoas em conjunto, em que metade deles são um conjunto de quatro
e a outra metade é outra conjunto de quatro, como você vai
sobre como fazer a fusão?
Bem, vocês fizeram isso bastante intuitiva.
>> Mas, se em vez fiz um pouco mais metodicamente, eu poderia ter apontado para
a pessoa mais à esquerda pela primeira vez com a minha esquerda mão, apontou para a pessoa mais à esquerda
de que a metade com a minha mão direita, e só posteriormente passou pela
lista, apontando para o menor elemento cada vez, movendo o dedo sobre e
sobre quando necessário ao longo da lista.
Mas o que é importante sobre esta fusão processo é que eu estou comparando esses pares
de elementos.
A partir da metade da direita e da esquerda metade, estou nunca uma vez retrocesso.
>> Assim, o próprio merge está tomando não mais do que n passos.
E quantas vezes eu tive para fazer que a fusão?
Bem, não mais do que n, e nós apenas viu que, com a fusão final.
E por isso, se você faz algo que leva log vezes n passos n, ou vice-versa,
ele vai nos n log n vezes dar.
>> E por que isso é melhor?
Bem, se já sabemos que log n é melhor do que n - certo?
Vimos em busca binária, o livro de telefone exemplo, log n foi definitivamente
melhor do que o linear.
Então isso significa que n log n vezes é definitivamente melhor do que n vezes outro
n, AKA n ao quadrado.
E isso é o que finalmente se sente.
>> Tão grande salva de palmas, se pudéssemos, para esses caras.
>> [Aplausos]
>> DAVID MALAN: E os seus presentes de despedida - você pode manter os números,
se você gostaria.
E o seu presente de despedida, como de costume.
Oh, e nós lhe enviaremos a metragem, Michelle.
Obrigado.
Tudo bem.
Sirva-se de uma bola de stress.
>> E deixe-me puxar para cima, entretanto, nosso amigo Rob Bowden para oferecer
perspectiva um pouco diferente deste, desde que você pode pensar sobre estes
etapas que acontecem em um pouco maneira diferente.
Na verdade, o set-up para o que Rob está prestes para nos mostrar assume que nós temos
feito a divisão do grande lista em oito pequenas listas,
cada um de tamanho 1.
>> Então, nós estamos mudando o pseudocódigo a pouco apenas a sorte de chegar ao
ideia central de como a fusão obras.
Mas o tempo de funcionamento do que ele está prestes a fazer ainda é
vai ser o mesmo.
E, novamente, o set-up aqui é que ele é iniciado com oito listas de tamanho 1.
Então você perdeu a parte onde ele é realmente fez o log n, n log, log n
divisão da entrada.
>> [REPRODUÇÃO]
>> -Isso é tudo por um passo.
Para a segunda etapa, repetidamente pares de listas de mala direta.
>> DAVID MALAN: Hm.
Só áudio está chegando fora do meu computador.
Vamos tentar isso novamente.
>> -Just arbitrariamente escolher qual - agora temos quatro listas.
Saiba antes.
>> DAVID MALAN: Lá vamos nós.
>> Mesclando-108 e 15, terminamos com a lista de 15, 108.
Fundir 50 e 4, temos acabar com 4, 50.
Mesclando 8 e 42, que acabar com 8, 42.
E fusão 23 e 16, nós acabar com 16, 23.
>> Agora todas as nossas listas são de tamanho 2.
Note-se que cada um dos quatro listas é classificado.
Assim, podemos começar a fundir pares de listas novamente.
Mesclando 15 e 108 e 4 e 50, que tire primeiro a 4, depois a 15, em seguida,
a 50, depois a 108.
Mesclando 8, 42 e 16, 23, primeiro tomar a 8, em seguida, a 16, depois a 23,
em seguida, a 42.
>> Portanto, agora temos apenas duas listas de tamanho 4, cada um dos quais é classificado.
Então, agora nós mesclar essas duas listas.
Primeiro, tomamos a 4, depois tomamos o 8, então tomamos o 15, então com 16 anos, em seguida,
23, depois 42, depois 50, depois 108.
>> [FIM REPRODUÇÃO DE VÍDEO]
>> DAVID MALAN: Mais uma vez, o aviso prévio, ele nunca tocado um determinado copo mais do que uma vez
depois de avançar além dela.
Assim, ele nunca repetir.
Então ele está sempre se movendo para o lado, e é aí que temos o nosso n.
>> Por que não deixar me puxar para cima uma animação que vimos anteriormente, mas desta vez
incidindo apenas sobre merge sort.
Deixe-me ir em frente e fazer zoom na nesta aqui.
Primeiro deixe-me escolher uma entrada aleatória, ampliar isso, e você pode classificar de ver
o que nós tomamos para concedido, anteriormente, merge sort está realmente fazendo.
>> Então, observe que você obter essas metades ou estes quartos ou estes oitavos da
problema que, de repente, começar a tomar boa forma.
E então, finalmente, você vê a o fim que bam,
tudo é mesclado juntos.
>> Então, essas são apenas três diferentes assume a mesma ideia.
Mas o insight chave, assim como dividir e conquistar na primeira classe,
foi que decidimos dividir de alguma forma o problema em algo grande, em
algo tipo de idêntico em espírito, mas menores e menores
e menores.
>> Agora uma outra forma divertida de classificar de pensar sobre estes, apesar de que não é
vai dar-lhe o mesmo intuitivo entendimento, é
o seguinte animação.
Portanto, este é um vídeo de alguém juntos que associado diferente
sons com as várias operações para ordenação por inserção, por merge sort, e
por um par de outros.
Então, em um momento, eu vou bater Play.
Trata-se de um minuto de duração.
E mesmo que você ainda pode ver a padrões acontecendo, neste momento você pode
também ouvir como esses algoritmos são realizar de maneira diferente e com
um pouco diferentes padrões.
>> Esta é a ordenação por inserção.
>> [TONS JOGO]
>> DAVID MALAN: Ele novamente está tentando para inserir cada elemento
para onde ela pertence.
Este é bubble sort.
>> [TONS JOGO]
>> DAVID MALAN: E você pode classificar de sensação como relativamente pouco trabalho que está fazendo
em cada passo.
Isto é o tédio parece.
>> [TONS JOGO]
>> DAVID MALAN: Esta é a seleção de tipo, onde se selecionar o elemento que queremos por
passando por uma e outra vez e outra vez e colocá-lo no início.
>> [TONS JOGO]
>> DAVID MALAN: Este é o merge sort, que você pode realmente começar a sentir-se.
>> [TONS JOGO]
>> [Risos]
>> DAVID MALAN: Algo chamado gnome tipo, que não olhei.
>> [TONS JOGO]
>> DAVID MALAN: Então deixe-me ver, agora, distraído como você espera, segundo a
música, se eu posso escorregar um pouco pouco de matemática aqui.
Portanto, há uma quarta forma que pudermos pensar sobre o que significa que estes
funções para ser mais rápido do que os que já vimos antes.
E se você está vindo para o curso de um fundo de matemática, você
realmente sabe, talvez, já que você pode bater um termo sobre esta técnica -
ou seja, a recursividade, uma função que de alguma forma se autodenomina.
>> E mais uma vez, lembrar que merge sort pseudocódigo foi recursivo no sentido
que uma das etapas do merge sort foi chamar espécie -
que é, em si.
Mas, felizmente, porque mantivemos chamando tipo, ou merge sort,
especificamente, numa menor e menor e uma lista menor, eventualmente
ao fundo do poço graças ao que chamaremos um caso base, no caso hard-coded que
disse que se a lista é pequena, menos de 2 Nesse caso, basta retornar imediatamente.
Se não tivéssemos esse caso especial, a algoritmo seria nunca inferior para fora,
e você realmente entrar em um loop infinito verdadeiramente para sempre.
>> Mas suponha que queremos agora colocar alguns números no presente, de novo, utilizando n
medida que o tamanho da entrada.
E eu queria te perguntar, o que é o tempo total envolvido
execução merge sort?
Ou, mais geralmente, o que é o custo do mesmo no tempo?
>> Bem, é muito fácil de medir isso.
Se n for menor do que 2, o tempo envolvido na classificação de n elementos,
onde n é 2, é 0.
Porque nós só retornar.
Não há trabalho a ser feito.
Agora, sem dúvida, talvez seja um passo ou dois passos para descobrir a quantidade de
trabalhar, mas é perto o suficiente para que 0 Eu só vou dizer que não trabalho é
necessário se a lista é tão pequena para ser desinteressante.
>> Mas, neste caso, é interessante.
O caso recursivo foi o ramo de o pseudocódigo que disse outra coisa, tipo
a metade esquerda, classificar o direito metade, unir as duas metades.
Agora, por que esta expressão representar essa despesa?
Bem, T de n significa apenas que o tempo para ordenar n elementos.
E, em seguida, no lado direito da sinal de igual lá, o T de n dividido
por 2 refere-se ao custo de quê?
Classificando a metade esquerda.
O outro T de n dividido por 2 é presumivelmente, referindo-se ao custo de
classificar a metade direita.
>> E então o mais n?
É a fusão.
Porque se você tem duas listas, uma de tamanho n superior a 2 e outra de tamanho n
mais de 2, você tem que tocar essencialmente cada um desses elementos, assim como Rob
tocou cada um dos copos, e apenas como se apontou para cada um dos
voluntários no palco.
Assim, n é à custa de fusão.
>> Agora, infelizmente, esta fórmula é também próprio recursiva.
Assim se fez a pergunta, se n é, digamos, 16, se há 16 pessoas no palco
ou 16 xícaras no vídeo, quantos total de passos que é necessário para classificá-los
com merge sort?
Na verdade não é uma resposta óbvia, porque agora você tem a sorte de
recursivamente responder a esta fórmula.
>> Mas tudo bem, porque deixe-me propor que faça o seguinte.
O tempo envolvido para classificar ou 16 pessoas 16 xícaras vai ser representado
geralmente como T de 16.
Mas o que é igual a, de acordo com o nosso fórmula anterior, duas vezes a quantidade
de tempo que leva para classificar 8 copos mais 16.
E, novamente, mais 16 é o momento de fusão, E as duas vezes T de 8 é o
tempo para resolver metade esquerda e metade direita.
>> Mas, novamente, isso não é suficiente.
Temos que mergulhar mais fundo.
Isso significa que temos de responder à pergunta, o que é T de 8?
Bem T de 8 está apenas a 2 t de 4 vezes mais de 8.
Bem, o que é T de 4?
T de 4 está a apenas 2 vezes T de 2 + 4.
Bem, o que é T de 2?
T de 2 é apenas 2 vezes T de 1 mais 2.
>> E, novamente, nós somos o tipo de conseguir preso neste ciclo.
Mas isso está prestes a bater esse o chamado caso base.
Porque o que é T de 1, não podemos reclamar?
0.
Então, agora, finalmente, podemos trabalhar para trás.
>> Se T 1 é 0, agora posso voltar a subir um alinhar com esse cara aqui, e eu posso
conecte 0 para T de 1.
Então, isso significa que ele é igual a 2 vezes a zero, também conhecido como 0, acrescido de 2.
E, de modo que toda a expressão é 2.
>> Agora, se eu pegar o T de 2, cuja resposta é 2, ligá-lo na linha do meio, T
de 4, que me dá duas vezes 2 + 4, de modo 8.
Ora, se eu ligar 8 a anterior linha, que me dá duas vezes 8, 16.
E se, em seguida, continuar com o que 24, acrescentando em 16 de finalmente obter um
valor de 64.
>> Agora que em si mesmo tipo de fala nada para a notação n, o
O grande, o omega que temos falando.
Mas verifica-se que 64 é de fato 16, o tamanho da entrada,
log base 2, de 16.
E se isso é um pouco estranho, apenas acho que volta, e ele vai voltar
para que você eventualmente.
Se este é o log base 2, é como 2 elevado para o que lhe dá 16?
Oh, isso é 4, por isso é 16 vezes 4.
>> E mais uma vez, não é um grande negócio se este é uma espécie de memória nebulosa agora.
Mas, por enquanto, assumir a fé que 16 log 16 é 64.
E assim, de fato, com esta simples sanidade verificar, temos confirmada -
mas não provou formalmente -
que o tempo de execução de fusão espécie é realmente n log n.
>> Então, não é mau.
É definitivamente melhor do que o algoritmos que temos visto até agora, e
é porque temos alavancado, um, uma técnica chamada de recursão.
Mas o mais interessante do que isso, que noção de dividir e conquistar.
Mais uma vez, verdadeiramente semana 0 coisas que até agora é recorrente em
forma mais convincente.
>> Agora, um pouco de exercício divertido, se você tem nunca fiz isso - e você provavelmente
não teria, porque tipo do normal as pessoas não pensam para fazer isso.
Mas se eu for para google.com e se Eu quero aprender algo sobre
recursão, Enter.
>> [Risos]
[Mais risos]
DAVID MALAN: Bad piada espalhando lentamente.
[Risos]
DAVID MALAN: Apenas no caso, ele está lá.
Eu não soletrar errado, e há a piada.
Tudo bem.
Explique-os pessoas próximas a você se ele não tem muito clicado ainda.
Mas recursão, de modo mais geral, refere-se para o processo de uma função de chamada
si só, ou, mais geralmente, a divisão de um problema em algo que pode ser
resolvidos aos poucos, resolvendo idêntico problemas de representação.
>> Bem, vamos engrenagens de mudança apenas por um momento.
Gostamos de terminar em certos cliffhangers, então vamos começar a definir
a fase, durante vários minutos, em uma idéia muito simples -
que a troca de dois elementos, certo?
Todos esses algoritmos que estivemos falando sobre o último par de
palestras envolvem algum tipo de troca.
Hoje foi visualizado por eles recebendo -se de suas cadeiras e
andando por aí, mas no código, faríamos basta ter um elemento de uma matriz
e plop-lo em outro.
>> Então, como vamos fazer isso?
Bem, deixe-me ir em frente e escrever um programa rápido aqui.
Eu estou indo para ir em frente e fazer isto como a seguir.
Vamos chamar isso -
o que queremos chamar esse?
>> Na verdade, não.
Deixe-me voltar atrás.
Eu não quero fazer isso suspense ainda.
Vai estragar a diversão.
Vamos fazer isso em seu lugar.
>> Suponha que eu quero escrever um pouco programa e que agora abraça este
idéia de recursão.
Eu meio que tenho à frente de mim lá.
Eu vou fazer o seguinte.
>> Primeiro, um rápido incluem padrão de io.h, , bem como uma inclusão de cs50.h.
E então eu estou indo para ir em frente e declarar int void main
da maneira usual.
Eu percebi que eu tenho chamado erroneamente o arquivo, assim deixe-me adicionar uma extensão c. aqui para
que podemos compilá-lo corretamente.
Comece esta função.
>> E a função que eu quero escrever, muito simplesmente, é aquele que faz a
usuário para um número e, em seguida, acrescenta-se todos os números entre esse
número e, por exemplo, 0.
Então, primeiro eu vou seguir em frente e declarar int n.
Então eu copiar um código que nós usamos por um tempo.
Enquanto algo é verdadeiro.
Eu vou voltar a isso em um momento.
>> O que eu quero fazer?
Eu quero dizer printf positivo inteiro por favor.
E então eu vou dizem que n recebe obter int.
Então, novamente, algum código clichê que usei antes.
E eu vou fazer isso enquanto n for menor do que 1.
Assim, isto irá assegurar que o utilizador me dá um número inteiro positivo.
>> E agora eu vou fazer o seguinte.
Quero somar todos os números e entre 1 e n, ou 0 e n,
equivalentemente, para obter a soma total.
Assim, o símbolo grande sigma que você pode se lembrar.
Então, eu vou fazer isso pela primeira convocação uma função chamada sigma,
passá-lo em n, e então eu vou printf dizer, a resposta está logo ali.
>> Assim, em breve, eu recebo e int do usuário.
I garantir que ele é positivo.
Eu declaro uma variável chamada resposta de tipo int e armazenar em que o retorno
valor de sigma, passando n como entrada.
E então eu imprimir essa resposta.
>> Infelizmente, embora sigma soa como algo que pode estar em
o arquivo math.h, sua declaração, isso não é verdade.
Então, isso é OK.
Eu posso implementar isso mesmo.
Vou implementar uma função chamada sigma, e isso vai levar um
parâmetro -
vamos chamá-lo m, apenas por isso é diferente.
E, em seguida, até aqui, eu vou dizer, assim, se m for menor do que 1 - Este é um
programa muito desinteressante.
Então, eu estou indo para ir em frente e imediatamente retornar 0.
Ele simplesmente não faz sentido somar todos os números entre 1 e m se m
0 é ele próprio ou negativo.
>> E então eu estou indo para ir em frente e fazer isso muito iterativa.
Eu vou fazer esse tipo de old-school, e eu estou indo para ir em frente
e dizer que eu vou declarar uma quantia a ser 0.
Então eu vou ter um loop de int -
e deixe-me fazê-lo para coincidir com o nosso Código de distribuição, para que você tenha uma cópia
em casa. int i recebe 1 em até i é inferior ou igual a m.
i plus plus.
E, em seguida, dentro deste loop -
estamos quase lá -
soma fica soma mais 1.
E então eu vou retornar a soma.
>> Então eu fiz isso rapidamente, reconhecidamente bastante.
Mas, novamente, a principal função é muito simples, com base no código temos
escrito até agora.
Utiliza o loop duplo para obter uma positiva int do usuário.
Eu, então, passar essa int para uma nova função chamado sigma, chamando-o, mais uma vez, n.
E eu armazenar o valor de retorno, a resposta da caixa preta atualmente
conhecido como sigma, em uma variável chamada de resposta.
Então eu imprimi-lo.
>> Se agora continuar a história, como é sigma implementado?
Proponho para implementar o seguinte.
Primeiro, um pouco de verificação de erros para se certificar de que o usuário não é
brincando comigo e passando algum valor negativo ou 0.
Então eu declarar uma variável chamada Resumindo e configurá-lo para 0.
>> E agora eu começo a passar de i é igual a 1 todo o caminho até e incluindo m,
porque eu quero incluir todas as números de um a m, inclusive.
E dentro deste loop for, eu só faço soma recebe o que é agora, mais do
valor de i.
Além disso, o valor de i.
>> Como um aparte, se você não vi isso antes, há um pouco de açúcar sintático
para esta linha.
Eu posso reescrever isso como mais iguais i, só para me salvar algumas teclas
e olhar um pouco mais frio.
Mas isso é tudo.
É funcionalmente a mesma coisa.
>> Infelizmente, este código de não vai compilar ainda.
Se eu executar o make sigma 0, como sou I vai ser gritado?
O que ele está indo para não gostar?
>> AUDIÊNCIA: [inaudível].
>> DAVID MALAN: Sim, eu não declarar a função em cima, certo?
C é uma espécie de estúpida, só na medida em que faz o que você diga a ele para fazer, e você
tem que fazer isso nessa ordem.
E então se eu pressione Enter aqui, eu vou receber um aviso sobre sigma implícita
declaração.
>> Oh, não é um problema.
Eu posso ir até o topo, e eu posso dizer, tudo bem, espere um minuto.
Sigma é uma função que retorna um int e espera um
int como entrada, ponto e vírgula.
Ou eu poderia colocar toda a função acima principal, mas em geral, eu
recomendo contra isso, porque é bom ter sempre principal no topo de modo
você pode mergulhar na direita e sabe o que é um programa está fazendo lendo principal pela primeira vez.
>> Então, agora deixe-me limpar a tela.
Remake sigma 0.
Tudo parece check-out.
Deixe-me correr sigma 0.
Entre positiva.
Eu vou dar-lhe o número 3 para mantê-lo simples.
De modo que deve me dar 3 mais 2 mais 1, então 6.
Enter, e na verdade eu fico 6.
>> Eu posso fazer algo maior -
50, 12, 75.
Assim como a tangente, eu vou fazer algo ridículo como realmente um grande
número, Oh, que realmente funcionou -
eh, eu não acho que isso é certo.
Vamos ver.
Vamos realmente mexer com ele.
>> Isso é um problema.
O que está acontecendo?
O código não é tão ruim assim.
Ainda é linear.
Assobiar é um bom efeito, apesar de tudo.
O que está acontecendo?
>> Não tenho certeza se ouvi-lo.
Assim, verifica-se - e isto é como um aparte.
Isto não é essencial para o idéia de recursão.
Acontece que, porque eu estou tentando representam um número tão grande, a maioria
provavelmente ele está sendo mal interpretado por C, tal como um número não positivo,
mas número negativo.
>> Nós não falamos sobre isso, mas Acontece que existem números negativos
no mundo para além a números positivos.
E os meios pelos quais você pode representar um número negativo
essencialmente é, você pode usar um bit especial para indicar
positivo sobre negativo.
É um pouco mais complexo do que isso, mas essa é a idéia básica.
>> Então, infelizmente, se C é confuso uma desses bits como de fato o que significa,
oh, este é um número negativo, o meu laço aqui, por exemplo, é, na verdade nunca
vai terminar.
Então, se eu fosse realmente a impressão de algo novo e de novo, faríamos
ver muita coisa.
Mas, novamente, isso é além do ponto.
Isto é realmente apenas uma espécie de curiosidade intelectual que nós viremos
voltar para eventualmente.
Mas, por agora, esta é a correta implementação se assumirmos que o
usuário irá fornecer ints que se encaixam dentro de ints.
>> Mas eu afirmo que este código, francamente, poderia ser feito muito mais simples.
Se o objetivo em questão é ter um número como m e somar todas as
números entre ele e 1, ou, inversamente entre 1 e ele, eu afirmo
que eu posso pedir essa idéia de que fundem espécie tinha, que estava tomando um problema
deste tamanho e dividindo-o em algo menor.
Talvez nem a metade, mas menor, mas representativamente a mesma.
A mesma idéia, mas um problema menor.
>> Então, eu estou na verdade - deixe-me salve este arquivo com um número de versão diferente.
Vamos chamar esta versão 1 em vez de 0.
E eu afirmo que eu possa realmente reimplementar esta neste tipo de
alucinante caminho.
>> Vou deixar parte dela sozinho.
Eu vou dizer se m é menor que ou mesmo igual a 0 -
Eu só vou ser um pouco desta vez mais anal
com a minha verificação de erros -
Eu estou indo para ir em frente e retornar 0.
Este é arbitrária.
Estou simplesmente decidir se o usuário me dá um número negativo, eu sou
retornando 0, e eles devem ter lido a documentação mais de perto.
>> Else -
perceber o que eu vou fazer.
Mais eu vou voltar m plus -
o que é de sigma m?
Bem, sigma de m mais m menos 1, m menos mais dois, além de menos 3 m.
Eu não quero escrever tudo isso para fora.
Por que eu não apenas punt?
Recursively me chamar com um pouco problema menor, ponto e vírgula,
e chamá-lo um dia?
>> Certo?
Agora, aqui, também, que você pode sentir ou se preocupar que este é um loop infinito que eu sou
induzindo, pelo qual estou implementando sigma chamando sigma.
Mas isso é perfeitamente normal, porque eu pensou em frente uma acrescentou que falas?
>> AUDIÊNCIA: [inaudível].
>> DAVID MALAN: 23 a 26, que é o meu caso condição.
Porque o que é bom sobre o subtração aqui, porque eu mantenho
entregando sigma problemas menores, menor problemas menores - não é
a metade do tamanho.
É apenas um pequeno passo menor, mas isso é OK.
Porque, eventualmente, vamos trabalhar nosso caminho até a 1 ou 0.
E uma vez que nós batemos 0, sigma não é vai chamar-se mais.
Vai retornar imediatamente 0.
>> Assim, o efeito, se este tipo de vento em sua mente, é adicionar mais m
menos 1 m, mais M menos 2, mais M menos 3, além de ponto, ponto, ponto, m menos
m, acabou dando-lhe 0, eo efeito é em última análise, para adicionar todos
essas coisas juntas.
Então, nós não temos, com recursão, resolveu o problema que
não poderia resolver antes.
Com efeito, esta versão de 0, e todo problema até à data, tem sido resolvidas
com apenas usando loops ou enquanto loops ou construções semelhantes.
>> Mas recursão, ouso dizer, dá-nos uma maneira diferente de pensar sobre
problemas, em que se pode tomar um problema, dividi-lo de alguma coisa
um tanto grande para algo um tanto menor, eu afirmo que nós podemos resolvê-lo
talvez um pouco mais elegante em termos do design, com menos código,
e talvez até mesmo resolver problemas que ser mais difícil, à medida que vai finalmente
ver, a solução puramente iterativa.
>> Mas o suspense que eu fiz quero deixar-nos no foi isso.
Deixe-me ir em frente e abrir um arquivo a partir de -
Na verdade, deixe-me ir e fazer isso muito rápido.
Deixe-me ir em frente e propor a seguir.
Entre o código de hoje é este arquivo aqui.
Este aqui, noswap.
>> Portanto, este é um pequeno programa estúpido que Eu chicoteado até que as reivindicações a fazer
a seguir.
Na principal, declara pela primeira vez um int chamado x e atribui a ele
o valor de 1.
Em seguida, ele declara um int y e atribui o valor 2.
Em seguida, ele imprime o que x e y é.
Em seguida, ele diz, troca, dot dot dot.
>> Em seguida, ele afirma ser chamada de uma função chamado swap, passando em x e
y, a idéia de que é que esperamos x e y voltará
diferente, o oposto.
Em seguida, ele trocou reclamar!
com um ponto de exclamação.
Em seguida, ele imprime x e y.
>> Mas acontece que essa mesma demonstração simples para baixo
aqui é realmente buggy.
Mesmo que eu estou declarando uma temporária variável e, temporariamente, colocando um em
, então eu estou reafectação um o valor de b -
que se sente razoável, porque eu tenho salva uma cópia de um de temperatura.
Então eu atualizar b para igual o que estava na temperatura.
Este tipo de jogo shell de mover um em b e b em um usando esta
meio-homem chamado temperatura sente perfeitamente razoável.
>> Mas eu afirmo que quando eu executar este código, como eu vou fazer agora -
deixe-me ir em frente e colá-lo aqui.
Vou chamar esta noswap.c.
E, como o nome sugere, este não é Vai ser um programa correto.
Faça noswap. / No swap.
x é 1, y é 2, troca, trocados.
x é 1, y é 2.
Isto é fundamentalmente errado, mesmo embora isto parece perfeitamente
razoável para mim.
E há uma razão, mas não estamos vai revelar o motivo ainda.
>> Por agora, a segunda suspense que eu queria para deixá-lo com isso é, um
anúncio das sortes sobre os códigos de cupom.
Nossa inovação com dias de atraso este ano tem provocado um número não-trivial
de perguntas, o que foi não a nossa intenção.
A intenção destes códigos de cupom, em que, se você fizer parte do problema
definir cedo, obtendo assim um dia extra, Foi realmente para ajudar vocês ajudam
se começar cedo, tipo de por incentivar você.
Nos ajuda a distribuir a carga em toda o horário de expediente, para que melhor
é uma espécie de ganha-ganha.
>> Infelizmente, acho que as minhas instruções não ter sido, até à data, muito clara, de modo
Voltei esta semana e atualizada a especificação no maior, mais ousado texto para
explicar balas como estas.
E só para dizer isso mais publicamente, por padrão, conjuntos de problemas são devidos quinta-feira
ao meio-dia, conforme o programa.
Se você começar cedo, terminando em parte de o problema de definir até quarta-feira às 12:00
PM, a parte que se relaciona com um cupão código, a idéia é que você pode estender
o prazo para a P definido até sexta-feira.
Ou seja, pouco fora uma pequena parte do P definido em relação ao que normalmente é o
maior problema, e você compra se um dia extra.
Mais uma vez, você fica pensando o conjunto de problemas, faz com que você
o expediente mais cedo.
Mas o problema ainda é o código de cupom obrigados, mesmo se você não enviá-lo.
>> Mas o mais convincente é este.
(Sussurro) E essas pessoas deixando cedo vão se arrepender.
Como são as pessoas na varanda.
Peço desculpas antecipadamente para as pessoas em a varanda, por razões que serão
claro em apenas um momento.
>> Então, temos a sorte de ter um dos Ex-chefe companheiros de ensino do CS50 em
uma empresa chamada dropbox.com.
Eles têm muito generosamente doou um código de cupom aqui para isso muito espaço,
que é a partir do usuais 2 gigabytes.
Então o que eu pensei que iria fazer nesta nota final é fazer um pouco de uma oferta,
pelo qual, em apenas um momento, vamos revelar o vencedor e que tem um cupão
código que você pode, então, ir ao seu site, digite-a, e voila, obter um
muito mais espaço para o seu Dropbox aparelho e para seus arquivos pessoais.
>> E em primeiro lugar, que gostaria de participar neste desenho?
OK, agora que o torna ainda mais divertido.
A pessoa que recebe este 25 gigabytes código do cupom - o que está longe
mais atraente do que o falecido dias de hoje, talvez -
é aquele que está sentado em cima de um assento do banco sob a qual existe
que o código do cupom.
Agora você pode olhar por baixo seu assento.
>> [REPRODUÇÃO]
>> -Um, dois, três.
>> [GRITANDO]
>> -Você ganha um carro!
Você ganha um carro!
>> DAVID MALAN: Veremos você na quarta-feira.
>> -Você ganha um carro!
Você ganha um carro!
>> DAVID MALAN: pessoas Varanda, vêm aqui em baixo para a frente,
onde temos extras.
>> -Todo mundo tem um carro!
Todo mundo fica um carro!
>> [FIM REPRODUÇÃO DE VÍDEO]
>> Narrador: Na próxima CS50 -
>> COLUNA 5: Oh meu Deus caramba caramba caramba caramba caramba caramba caramba caramba caramba -
>> [JOGOS ukelele]