>> [Música tocando]
>> DAVID J. MALAN: Tudo bem.
Então bem-vindo de volta.
Isto é CS50, e é o o final de semana três.
>> Então, lembro nas últimas semanas, estamos gastando um pouco de
tempo em C, em programação, em sintaxe.
E é muito normal, se você ainda estiver lutando com o Conjunto de Problemas 2, para ser
bater sua cabeça contra a parede.
É mensagens de erro enigmáticas para o futuro e os erros que você
não consegue perseguir.
Porque, pode ter certeza, que em apenas um tempo de algumas semanas você vai olhar para trás
coisas como César, e [? V-genair,?] talvez até de crack, e
perceber o quão longe você chegou num curto período de tempo.
Então, se isso serve de consolo, pendurar lá por enquanto.
>> Hoje, porém, começamos a transição para coisas de mais alto nível.
E começamos a dar como certo que Vocês sabem como programar, ou pelo
menos o início de que o nível de conforto.
E vamos começar a considerar como podemos ir sobre a criação de programas mais
eficazmente.
Como podemos ir sobre como otimizar o eficiência dos algoritmos e
geralmente a solução mais problemas interessantes.
E começando a tomar por certo que, se quiséssemos, poderíamos codificar qualquer
dos exemplos que temos em mente.
Então, hoje, nós não tocar o teclado para qualquer forma de código.
Vai ser nível muito mais elevado, e em última instância, sobre a resolução de problemas.
>> Então, para chegar a esse ponto, deixe-me propor que os seguintes sete
retângulos representam sete portas, atrás que são um monte de
números, entre os quais está o número 50.
Deixe-me projetar esta neste tela aqui também.
E propor que precisamos de um voluntário para me ajudar a encontrar um número na frente
a internet aqui para ver.
Vamos para cima, na cor rosa.
Tudo bem.
Qual é o seu nome?
>> JENNIFER: [inaudível]
>> DAVID J. MALAN: Desculpe?
>> JENNIFER: Jennifer.
>> DAVID J. MALAN: Jennifer.
Tudo bem, Jennifer.
Prazer em conhecê lo.
Vamos para cima.
Então, esses aqui são sete portas, eo que Gostaria de fazer para nós aqui,
na frente de todos os seus colegas, é encontrar-nos o número, 50.
Para encontrar um número, você pode espreitar atrás qualquer destas portas simplesmente tocando
em uma das portas, e irá revelar o seu número.
E vamos ver o quão rápido você pode encontrar-nos o número, 50.
>> 15.
16.
50.
Bem feito.
Tudo bem.
Salva de palmas para Jennifer.
>> [Aplausos]
>> Tudo bem.
Então, qual foi a sua estratégia para encontrar o número, a 50?
>> JENNIFER: Hum, eu pensei que talvez se -
[Inaudível]
>> DAVID J. MALAN: Oh.
Dê-lhe um segundo.
Assim foi a sua estratégia para encontrar o número, a 50?
>> JENNIFER: Então, eu só começar no começando a ver que o primeiro número
era, e então eu pensei, talvez se eles estão classificadas, vou continuar
tocando mais alto?
>> DAVID J. MALAN: OK.
E nós parecem ter encontrado que seja esse o caso.
Embora, vamos descascar as camadas apenas um pouco, e você quer ir
frente e revelar as outras portas você poderia ter escolhido?
>> JENNIFER: Oh, querida.
>> DAVID J. MALAN: Ah.
>> JENNIFER: Então eu só tenho sorte.
>> DAVID J. MALAN: Então você teve sorte.
Tudo bem.
Então, não é mau.
Mas isso é um interessante insight, certo?
Se você assumiu, e você conseguiu, na verdade, um pouco de sorte lá.
Mas se do princípio de que os números eram classificadas, você pode ser mais preciso
de como isso influenciado seu comportamento?
>> JENNIFER: Então, se eles foram ordenados, eu pensei que talvez menor para o maior.
>> DAVID J. MALAN: OK.
>> JENNIFER: Ou se isso acabou sendo realmente grande, então maior para o menor.
>> DAVID J. MALAN: OK.
Então maior para o menor, ou menor para o maior.
Mas deixe-me propor, suponha que você tinha obtido de azar, e supor que eles
não foram, de fato, classificado, quantos aquelas portas que você poderia ter tido para espiar
trás em que o pior caso?
>> JENNIFER: Todos eles.
>> David J. MALAN: Todos eles.
Então vamos generalizar que, como n.
Não passa a ser 7, mas vamos mais geralmente dizem que há n portas no
tela aqui.
Assim, no pior caso, você teria que para olhar para trás sete portas, ou n portas.
E assim, este realmente é, é um pouco de sorte hoje, mas é realmente um linear
algoritmo do tipo, mesmo que você eram uma espécie de pular ao redor.
Isso é justo?
>> JENNIFER: Yeah.
>> DAVID J. MALAN: Bem, deixe-me ver se o seu mudanças de estratégia, se eu nos movem
nosso segundo exemplo aqui com 7 portas diferentes.
Os mesmos números, mas esta vez que eles são classificados.
Qual é a sua estratégia aqui vai ser, tentando apagar de sua mente o que
os outros números foram -
>> JENNIFER: OK.
>> DAVID J. MALAN - mais cedo?
>> JENNIFER: Vamos começar com o primeiro.
>> DAVID J. MALAN: Tudo bem.
Comece com o primeiro.
4.
Agora, onde você vai passar, e por quê?
>> JENNIFER: 4 é muito pequeno.
Então, se eles são uma espécie talvez menor a maior, que deveria
ser o dobro, e -.
>> DAVID J. MALAN: OK.
Vamos ver, o que você acha?
>> JENNIFER: Experimente a última.
Nice.
>> DAVID J. MALAN: Muito bem feito.
Tudo bem.
>> [Aplausos]
>> DAVID J. MALAN: OK.
Então, na verdade você está fazendo isso horrivelmente, porque você é
fazê-lo muito bem.
O que nos deixa incapaz de fazer determinados pontos.
Então, vamos tentar reverter aqui.
>> JENNIFER: OK.
>> DAVID J. MALAN: Muito bem feito, no entanto.
Então você começou no início, você viu que ele tinha 4 anos, então você
deslocada para o final.
Mas suponha que você não tem sorte lá, e suponho que 50
estava em outro lugar.
Qual a sua terceira etapa ter sido?
>> JENNIFER: Volte para o começo.
>> DAVID J. MALAN: Volte para o início.
OK, então você teria tocado esta porta, o qual foi de 8.
Tudo bem.
Então, isso não é 50.
Onde é que você olhou ao lado?
>> JENNIFER: Se eu não fiz sabem que classificados.
>> DAVID J. MALAN: Correto.
Bem, se você soubesse foram classificadas -
>> JENNIFER: Ah, sabia, sim.
>> DAVID J. MALAN: - mas você não fez sabe onde 50 foi ainda?
>> JENNIFER: Apenas continuar.
>> DAVID J. MALAN: Tudo bem.
OK.
Continue indo.
OK, para que eu possa trabalhar.
>> JENNIFER: OK.
>> DAVID J. MALAN: Agora, se você está apenas vai continuar, o que é seu
algoritmo que recaem apoiada em.
>> JENNIFER: o linear -.
>> DAVID J. MALAN: É uma espécie de linear.
Mas deixe-me propor, vamos me colocar no local.
Deixe-me atualizar a página.
mesmo número, o mesmo arranjo, mesmas portas.
Mas acho que voltar para aquele primeiro dia em classe quando rasgou um livro de telefone em
metade, mais ou menos, eo que era nossa estratégia lá?
>> JENNIFER: Comece pelo meio.
>> DAVID J. MALAN: OK.
Portanto, comece no meio.
Então, vamos em frente e simular isso.
Comece pelo meio por revelando que porta.
Portanto, o número 16.
Então, o que o cara forte fizeram, que rasgou o livro de telefone pela metade,
para chegar ao próximo palpite?
>> JENNIFER: Vá no semestre.
>> DAVID J. MALAN: E porque para a direita?
>> JENNIFER: Se eles eram uma espécie de menor para o maior, então deve ser 50
nessa extremidade.
>> DAVID J. MALAN: Ótimo.
Totalmente razoável.
Assim como um livro de telefone, você vai para o direita, por oposição à esquerda, mas aqui
é o principal argumento.
Agora você pode jogar fora, ou arrancar, semestre deste problema, deixando-o não
com 7 portas, mas realmente com apenas 3.
Que é cerca de metade da dimensão do problema.
Tudo bem.
Portanto, agora que você teria feito depois que você vai para a direita?
>> JENNIFER: So 16 ainda é muito pequeno, em relação a 50, talvez por isso eu vou tentar,
como, um presente.
>> DAVID J. MALAN: Tudo bem.
42.
Tudo bem, então agora o que é seu instinto dizendo a você?
>> JENNIFER: Eu posso jogar fora isso e, em seguida, apenas -
>> DAVID J. MALAN: OK.
Bom, você pode jogar fora a metade esquerda lá.
>> JENNIFER: - escolher um.
>> DAVID J. MALAN: E a direita.
>> JENNIFER: Yeah.
>> DAVID J. MALAN: Então, mesmo que seja difícil ver talvez, quando há apenas
Sete portas, pensar, agora, a consistência do
algoritmo que você acabou de aplicar.
No caso anterior, o que fez ter sorte, o que foi ótimo.
Mas você fez usar uma heurística, Eu diria.
Você usou uma espécie de seus instintos, e saber ordenado, se é muito
pequena no início, obviamente, temos tem que ir mais para a direita.
Mas, em certo sentido, você tem sorte, porque talvez este foi o número 100,
e talvez 50 foi mais no meio.
Talvez 50 fosse o mesmo por aqui.
>> Mas o que você fez um pouco diferente desta vez foi, você fez a mesma coisa
uma e outra vez.
E eu diria que o que você acabou se, ainda influenciado pelo telefone
livro exemplo, é algo muito mais algorítmica, e muito
menos especial encaixotado.
Muito menos instintivo.
Assim, no final do dia, como seria que descreve a eficácia do
primeiro algoritmo, onde você foi esquerda para a direita, contra o
segundo algoritmo aqui?
>> JENNIFER: Isso deve-se, como, talvez reduzir pela metade o tempo, ou até mais, sim.
>> DAVID J. MALAN: OK, talvez até mais.
Vamos empurrar um pouco mais sobre isso.
O que realmente, se continuar esta lógica, nós definitivamente reduziu pela metade o
tempo de corrida com este segundo algoritmo jogando fora metade do
números, mas o que vamos fazer no próximo iteração, quando Jennifer revelou
o segundo número?
>> Nós para metade o número de portas novamente.
E então o que fizemos após o que, se havia mais portas para brincar?
Gostaríamos de metade deles, e mais uma vez, e de novo, e de novo.
E isso era exatamente como vocês todos pé na primeira semana de
classe, metade do que você sentar-se, metade de você sentar, metade de vocês
sentar-se, até que um solitário alma estava de pé.
E nós dissemos que o tempo de execução isso, o número de passos Bastou
na ordem de quê?
>> COLUNA 1: [inaudível]
>> DAVID J. MALAN: Então log base 2 de n, ou apenas mais simples, faça o login do n.
Portanto, algo logarítmica.
E o gráfico não é uma linha reta que ficou pior e pior, foi
interessante que esta curva não fez ficar tão ruim ao longo do tempo.
Então, vamos segurar essa idéia.
Vamos agradecer a Jennifer.
Muito obrigado por terem vindo em cima.
E, um segundo.
Não há mesa lâmpadas hoje, mas nós tem CS50 bolas de stress.
>> JENNIFER: Yay.
>> DAVID J. MALAN: Tudo bem, aqui.
Obrigado por incorrer o stress aqui.
Tudo bem.
Então, vamos ver se não podemos agora formalizar esta um pouco mais.
Então, novamente, o que nós fizemos foi essencialmente a mesma coisa que nós fizemos
em que a primeira semana.
Mas ao invés de final com apenas um linear algoritmo, que representado
anteriormente como essa linha reta, pelo que, se colocarmos mais uma porta
tela, em seguida, Jennifer teria tiveram que olhar, potencialmente,
por trás de mais uma porta.
Se colocarmos mais duas portas, ela pode ter para olhar para trás mais duas portas.
>> E assim, houve essa linear relação entre o tamanho da
problema em, por exemplo, o eixo x, e a quantidade de tempo que demora a
resolver na y.
Mas a imagem que eu estava aludindo anterior era esta linha verde.
Verde deliberadamente, porque ele só me senti melhor.
Em teoria, o algoritmo, quando fizemos com o livro de telefone, quando fizemos
com vocês contando uns aos outros, e no segundo caso, quando apenas Jennifer
fiz isso aqui em cima, que era uma espécie de fundamentalmente melhor.
Porque não foi apenas duas vezes mais rápido.
Não era até quatro vezes mais rápido.
Foi totalmente dependente do que a tamanho da entrada foi, de quantas
passos que finalmente levou.
>> E assim esta ideia simples que todos nós tomamos adquirido com o livro de telefone,
semelhante pode ser aplicado para algo como isto.
E isso pode ser mais informal conhecida como, como você pode
imaginar, dividir e conquistar.
Não ao contrário do que fizemos, é claro, com o livro de telefone.
>> Mas o pseudocódigo, aviso, foi isso.
Portanto, não vamos fazer isso de novo, mas recordar essa primeira semana, todos nós se levantou
e, em seguida, metade do que você sentou-se, metade dos você sentou-se, metade do que você sentou-se.
Esse algoritmo foi implementado em um pouco de uma forma de trapaça, em que, ele
Não foi apenas uma das me contando, fundamentalmente, de forma mais eficiente.
Nesse caso, eu estava alavancando um recurso secundário.
Mais ou menos, CPUs múltiplo, cérebros, várias pessoas inteligentes no
sala estavam me ajudando a começar a partir de algo linear para algo
logarítmica, de algo vermelho para algo verde.
>> Mas, neste caso, Jennifer sozinho pode fundamentalmente melhorar a
desempenho de seu primeiro algoritmo, mais uma vez, só de pensar um pouco mais.
E agora, quando chega a hora de implementar essas coisas, descobrir
que as linhas de código que você pode escrever como que você pode repeti-los novamente, e
novamente, e novamente, uma espécie de em uma forma de looping.
Porque você não vai ter a luxo, como Jennifer fez num primeiro momento, a
só tem um monte de ifs e dizer: hmm, se este primeiro número é 4,
deixe-me saltar todo o caminho até o fim.
Ooh, se esse número é muito grande, deixe-me passar para trás de forma arbitrária
ao segundo elemento.
Você verá que ele vai ser muito mais difícil de formalizar o que nós, seres humanos
tomar para concedido como muito razoável heurística, mas um computador é apenas
vai fazer o que você diga a ele para fazer.
>> Agora, isso tem muito interessante implicações.
Este gráfico é uma espécie de significado para classificar de sobrecarregar visualmente, mas o aviso prévio, onde
é a reta neste gráfico?
Onde está o gráfico linear que chamamos de n?
Bem, é uma espécie de para o fundo da imagem, certo?
Então, tudo o que fizemos é que tenho a sorte de zoom out para o eixo x eo
eixo-y para tentar obter uma noção do que outros tipos de curvas parecem.
>> E as especificidades da matemática expressões, hoje, não importa para
muito, mas perceber que há uma grande quantidade de algoritmos que são muito piores do que
algo que é linear.
Na verdade, n cubos parece muito ruim.
2 ao n parece muito ruim. n ao quadrado parece muito ruim.
E vamos ver o que alguns desses pode ser, na realidade de hoje.
E log n não se sente tão ruim, mas melhor do que n é o log de base 2 do n.
Mas você sabe, ele teria sido ainda mais surpreendente se Jennifer, ou se,
essa primeira semana, surgiu com algo que é log de registro de n.
>> Portanto, em outras palavras, não há toda essa gama de possíveis soluções para
problemas, mas, mesmo aqui, o aviso o que vai acontecer.
Quando eu diminuir o zoom, qual destas curvas vai provar ser o absoluto
pior os que estão na tela agora?
Então n cubos parece muito ruim no momento.
Mas se diminuir o zoom e ver mais do x e eixo-y, que vai
dominar em última instância?
Então, ele realmente se que 2 a n, e você pode descobrir isso apenas por
ligar em algum cada vez maior números, e você verá que 2 para o
n, de facto, muito mais rapidamente se torna maior.
Se realmente diminuir o zoom, a 2 para o n algoritmo absolutamente uma merda.
Quero dizer que isso vai levar um pouco de tempo para a
computador para agitar completamente.
>> Mas você vai ver ao longo do tempo, especialmente com conjuntos de problemas futuros e até mesmo
projetos finais, é seus dados conjunto se torna grande, certo?
Mesmo na primeira versão do Facebook, como o número de amigos, eo
número de usuários registrados tem grande você pode classificar de telefone-lo e
implementar algo com busca linear, ou uma classificação muito simples
algoritmo, como veremos hoje.
Você tem que começar a pensar mais e mais sobre estes problemas.
E os tipos de problemas locais como Facebook e Google e Microsoft,
e outros, trabalhar é exatamente esses tipo de dados grande tipo de perguntas
cada vez mais nos dias de hoje.
>> Tudo bem.
Assim, o sucesso de Jennifer, em que a segunda algoritmo, francamente, ela fez incrivelmente
bem o primeiro tempo, mas vamos escrevê-lo como sorte, para que
pode fazer neste momento.
No segundo caso, ela alavancado um algoritmo que repetiu novamente e
novamente, mas ela levou para concedido um certa suposição de que nós permitimos
, mas ela explorado algum detalhe o segunda vez que ela não tem o
primeira vez.
Que era o que?
>> Que a lista foi classificada.
Assim, logo que a lista foi resolvido, nós afirmam que Jennifer era capaz de fazer
fundamentalmente melhor.
Sete portas, sim, não é tão interessante, mas acho que estamos 7.000.000 portas.
Sessão de n está indo definitivamente para realizar muito, muito
mais rápido no longo prazo.
Mas ela tinha que ter a portas classificadas para ela.
Agora, eu tomei a liberdade de fazer o que com antecedência na tela do computador
aqui, mas acho que Jennifer tive que fazer isso sozinha?
Suponha-se que as portas em questão dados representados em um banco de dados, ou
amigos registrados para Facebook, ou todas as páginas web na internet que
vários sites pode precisar ao índice ou pesquisa sobre.
>> Suponha que você acabou de ter um conjunto de dados brutos definir e foi deixado para você, ou para
Jennifer fazer isso de triagem?
Que, ao contrário, exige que nós respondemos a questão, bem como, quanto tempo
teria levado Jennifer, ou até mesmo de mim, para ordenar os números com antecedência para
que ela poderia tirar proveito disso?
Certo?
Porque a implicação, é claro, é se ele me leva muito tempo para classificar
os números, quem diabos se importa que você pode encontrar um número como 50 tão rápido,
como no caso de Jennifer, se mais de esmagada a quantidade de tempo total
demorou, classificando as coisas com antecedência?
>> Então, vamos ver se a gente não pode o pintar a imagem aqui.
Eu tenho um monte mais estresse esferas, se isso ajuda
quebrar o gelo aqui.
E se você não se importar, nós precisa de sete voluntários -
on, OK.
Uau.
Então, não tem que gastar em lâmpadas de mesa, ao que parece.
Tudo bem.
Assim como sobre vocês dois na frente.
Que tal vocês dois nas costas.
Então, isso é quatro.
Como sobre você na frente cinco, seis e sete.
Bem ali.
Seu amigo está apontando para fora, de modo a obter o prêmio.
>> Tudo bem.
Vamos para cima.
E por que não tê-lo caras vem aqui.
Vou dar-lhe cada um número.
E vá em frente e organizar-se de forma idêntica ao que está
representado na tela.
>> [Interpondo VOZES]
>> DAVID J. MALAN: Oop, sorry.
Bug.
Tudo bem.
Bem, aqui vamos nós.
Número cinco.
Número seis.
Um, dois, três, quatro, cinco, seis, sete.
Oh, isso é estranho.
>> COLUNA 2: Vou pegar um -.
>> DAVID J. MALAN: Bom negócio.
Tudo bem.
Obrigado por participar.
>> [Aplausos]
>> OK.
Tudo bem.
Portanto, temos quatro, dois, seis, um, três, sete, cinco.
Aperfeiçoar isso temos sete voluntários aqui que são iguais à largura do
matriz que estamos jogando com o anterior.
E eu escolhi sete por razões que será apenas
conveniente um pouco.
E eu vou propor pela primeira vez que nós classificar estes sete voluntários.
Se você gostaria, em primeiro lugar, para dizer Olá embora.
Uma vez que este vai ser um embaraçosas vários minutos.
Apresente-se.
>> GRACE: Oi, eu sou Grace.
Eu sou um estudante de segundo ano em Leverett House.
>> Branson: Hi.
Estou Branson.
Eu sou um calouro na Weld.
>> GABE: Oi.
Estou Gabe.
Eu sou um júnior na Cabot.
>> NEIL: Eu sou Neil.
Eu sou um calouro na Matthews.
>> JASON: Eu sou Jason.
Eu sou um calouro na Greenough.
>> MIKE: Eu sou Mike.
Eu sou um calouro na Grays.
>> JESS: Eu sou Jess.
Eu sou um estudante de segundo ano em Leverett.
>> DAVID J. MALAN: Excelente.
Tudo bem.
Bem, obrigado a todos os nossos voluntários aqui até agora.
E o desafio na mão agora vai ser a de classificar esses caras, mas, em seguida,
vamos ter que pensar um pouco muito sobre como nós realmente eficiente
classificou.
Então, vamos primeiro tentar isso.
Vocês podem ver os números uns dos outros apenas por colocar em torno dos cantos.
Vá em frente e levar alguns segundos, e tipo-vos do menor na
esquerda para a maior à direita.
Ir.
>> OK.
Bom.
Isso foi muito danado rápido.
Agora, alguém aqui, qual foi o algoritmo que esses caras aplicada?
>> COLUNA 1: Pelo menos a maior.
>> DAVID J. MALAN: OK.
Pelo menos a maior é realmente uma espécie de objetivo, mas eu não tenho certeza que é
realmente um algoritmo.
Pelo menos a maior não diz me passo-a-passo o que fazer.
Sim?
>> COLUNA 1: [inaudível]
>> DAVID J. MALAN: OK.
Então, se você vê uma pessoa menor do que seu número, então mover-se para
o direito deles.
Assim que agora está ficando cada vez mais expressivo, mais como um algoritmo, porque você
pode-se dizer, se isso, então aquilo.
Então nós temos algum tipo de construção condicional.
E esses caras pareciam fazer que alguns vezes, porque alguns de vocês mudaram um pouco
de uma distância.
Então, houve presumivelmente algum tipo de looping acontecendo em suas mentes.
>> Mas vamos tentar formalizar isso.
Se vocês pudessem repostas a este arranjo.
Vamos ver se não podemos formalizar esta uma pouco, e, em seguida, fazer a pergunta, apenas
quão eficiente é essa?
Claro que, quando fazemos isso de forma mais lenta, ele vai se sentir tão bem de
um algoritmo, mas vamos ver se podemos colocar os dedos sobre os passos precisos.
>> Então, vocês dois são quatro e dois.
Ou você ordem correta ou incorreta?
Obviamente incorreta.
Então nós trocamos.
Agora estou indo para mover de lado aqui e dizer: 4-6.
Você está correta ou incorreta?
>> GABE: Correto.
>> DAVID J. MALAN: Correto.
Seis e um?
Não..
Troque.
Então, isso é dois swaps.
Seis e três anos?
Não..
Troque.
Seis e sete?
Parece bom.
Sete e cinco?
>> JESS: [inaudível]
>> DAVID J. MALAN: OK, troque.
E classificados.
Tudo bem.
Então, obviamente, não, né?
Então lá estava mais acontecendo.
Mas, na verdade, esses caras, mesmo apenas instintivamente.
continuou se movendo.
Eles não parar, uma vez que eles corrigido um problema.
Assim.
Na verdade, eu vou ter para fazer a mesma coisa.
Eu vou ter a sorte de retroceder para trás para o início deste problema,
ou no início da presente de matriz pessoal, vamos começar a chamá-los.
>> E agora, o que deve o meu algoritmo na segunda passagem será?
>> COLUNA 1: a mesma coisa.
>> DAVID J. MALAN: Mesma coisa.
E isso, eu estou começando a gostar, certo?
Assim que você pode encontrar-se fazendo a mesma coisa uma e outra vez, isso é
tornando-se mais como um algoritmo, instinto e menos humana.
>> Então, agora, aqui vamos nós de novo.
Dois e quatro?
Não.
Quatro e um?
Ah, houve de fato algumas trabalho ainda a ser feito.
Por e três?
Bom.
Quatro e seis?
Seis e cinco?
Seis e sete?
OK, agora, feito.
OK, não.
Eu tenho que voltar.
>> Então, agora, mais uma vez, nós estamos fazendo isso um pouco mais deliberadamente.
E agora, há apenas um cérebro executar este algoritmo.
Uma CPU, se você quiser.
E, francamente, esse é o único recurso vamos ter acesso.
E uma vez que você voltar para um teclado e ter algo como C no nosso
disposição, estamos apenas escrevendo um programa que pode fazer uma coisa de cada vez.
Considerando que, esses caras há um momento, nós alavancado a sua inteligência coletiva
como vocês fizeram na semana zero.
Então, vamos continuar fazendo isso.
>> Dois e um.
Dois e três.
Três e quatro.
Quatro e cinco.
Cinco e seis.
Seis e sete.
Feito?
Então, eu estou, mas deixe-me jogar advogado do diabo.
Eu, o tipo de computador que só fez um passe por esse conjunto de
pessoas, sabe que eu sou feito?
>> COLUNA 1: Não.
>> DAVID J. MALAN: Então por quê?
O que eu tenho que fazer, a fim de concluir decisivamente que estou a fazer?
Provavelmente mais uma passagem.
Certo?
Porque tudo que eu sei de que anterior passe é que eu corrigi um erro.
E isso significa, talvez haja ainda outro erro
que eu preciso corrigir.
Então eu só posso ter certeza de rebobinagem, e em seguida, verificando, 1-2, e dois
três, três e quatro, quatro e cinco, cinco e seis, seis e sete.
OK, agora eu fiz nenhum trabalho.
>> Eu posso certamente me lembro que eu fiz não trabalhar com algo como uma variável,
como um int.
Chamá-lo de swaps, e se swaps é 0 uma vez que eu chegar até aqui, e ele começou a 0, então
Gostaria apenas de ser estúpido para continuar frente e para trás, verificando novamente, e
de novo, e de novo, certo?
Porque você ficar preso em algum espécie de loop infinito.
Assim, logo que há 0 swaps, podemos afirmar que este
algoritmo é realmente completa.
>> Agora, vamos colocar um nome sobre o assunto.
O algoritmo que proponho nós apenas implementado é uma coisa chamada bolha
tipo, conhecida como tal na medida em que os números que são maiores do tipo de
bolha seu caminho até o topo, ou até para o fim da série de números.
Mas quão eficiente foi esse algoritmo?
Quantos passos que eu tenho fisicamente para ter, por exemplo, para classificar estas
sete seres humanos?
>> De quatro a cinco anos?
OK, muitos é em última instância vai ser a resposta.
Mas, mesmo assim, o número específico não é tão interessante.
Vamos generalizar como n.
Então, se eu tivesse n pessoas aqui em cima, e eles foram, de alguma forma, em ordem aleatória no
começando, em que ordem original.
Bem, quantos passos eu tinha para assumir a primeira passagem?
Era um, dois, três, quatro, cinco, seis, e eles são sete pessoas, de modo
que é sete, seis -, de modo que n menos as etapas de uma primeira vez.
>> Agora, quantos passos eu tinha a tomar quando eu rebobinado?
Bem, poderíamos dobrar esse se nós realmente queríamos, mas por agora, estou
só vou dizer, tudo bem, outro n menos 1.
Assim, o n menos um vai ficar irritante para acompanhar, então vamos
apenas arredondar ligeiramente.
Então 2n passos.
Então, 14 etapas, mais ou menos.
>> Quantas vezes eu tomo um passo da próxima vez?
Bem, é 3N.
realmente.
E agora, no pior dos casos, por exemplo, quantas vezes eu teria
ido para trás e para frente, para trás e para frente, executar este algoritmo, trocando
pessoas em cada passagem, mais ou menos?
É realmente n ao quadrado, certo?
>> Porque, na pior das hipóteses, você pode tipo de pensar sobre isso de forma intuitiva,
embora possa demorar um pouco pouco de tempo para afundar-se dentro
No pior dos casos, o que seria isso sete pessoas parecia, em
termos do acordo de seus números?
Completamente para trás, certo?
E só para simular que, qual era o seu nome?
>> MIKE: Mike.
>> DAVID J. MALAN: Mike?
OK, Mike, você pode simplesmente juntar-me ao longo aqui por apenas um segundo?
Na verdade, não.
Desculpe Mike, vamos retroceder.
Qual é o seu nome?
>> NEIL: Neil.
>> DAVID J. MALAN: Neil.
OK, Neil, você vem com me, se você não se importa.
Então eu vou propor, apenas para simplicidade, que Neil está agora no seu
pior caso possível.
Mas lembre-se como eu implementei meu algoritmo.
Eu estou comparando, comparando, comparando, comparando, comparando, oh.
Agora, esses caras estão fora de ordem, assim que eu resolver.
Então vocês trocar.
Mas considere agora, quanto mais distante Neil não tem que ir?
É mais ou menos n.
Você sabe, não é, na verdade, n.
É como se, n menos 1, mas estou ficando irritado manter o controle do pequeno
número, então vamos chamá-lo de n.
>> Então, se Neil move um passo máximo de cada tempo, e para se deslocar Neil um passo,
Eu tenho que fazer esta passagem realmente tedioso e para trás, isto é mais ou menos
Fazendo isto, n passos, um total de n vezes, porque ele vai me levar
que muitos passos para chegar Neil tudo o caminho para onde ele pertence.
Deixai toda a gente se vocês foram todos mis-ordenadas, bem.
>> Então, vamos chamar bubble sort n ao quadrado.
O tempo de execução deste algoritmo, o desempenho deste algoritmo, o
eficiência deste algoritmo, vamos apenas descrever mais
geralmente como n ao quadrado.
Que é bom, porque eu poderia fazer o mesmo exemplo, com oito pessoas, nove
pessoas, um milhão de pessoas, e isso resposta não vai mudar.
>> Então, se vocês não se importaria, vamos redefinir-lo para onde você começou.
E vamos tentar duas outras abordagens e ver se não podemos fazer fundamentalmente
melhor do que este.
Então, desta vez, eu vou propor uma espécie de algoritmo diferente.
Isso foi muito inteligente de nós da última vez, e vocês estavam certos de ter a
instintos certos de apenas uma espécie de troca de pares.
Mas se eu realmente queria abordar esse simplesmente, e meu objetivo é mover-se
todos os números de pequenos desta maneira, e empurrar todos os grandes números que
Assim, por que não posso fazer isso apenas no mais ingênua maneira possível e ver se eu
pode fazer melhor do que aquilo que era um algoritmo bastante complexo?
>> Então vamos ver.
Quatro é um número bastante pequeno, por isso estou vai deixá-lo lá momento.
Ooh, o número dois é ainda melhor.
Então você pode apenas um passo à frente por um momento?
Este é atualmente o meu menor numerado candidato, e eu vou me lembrar
que com, tipo, uma variável.
Mas eu vou manter a verificação.
Existe alguém cuja número é menor?
Seis, não.
Oh, há Neil novamente.
>> Então eu vou empurrá-lo de volta tipo de conceitualmente.
Neil virá para a frente.
E agora, a variável que eu estou usando para acompanhar o que tem o menor
número é atualizado para conter Localização de Neil.
Bem, vamos ver.
Três, sete, cinco.
OK, eu sei que Neil era o menor.
Qual é a coisa mais simples para eu fazer agora?
Eu não vou perder meu tempo por apenas Neil borbulhando um local para a esquerda.
Por que não posso simplesmente colocar Neil onde ele pertence, o que é, naturalmente, onde?
>> Todo o caminho no início.
Então Neil, venha comigo.
E qual era o seu nome?
>> GRACE: Grace.
>> DAVID J. MALAN: Grace.
OK.
Então, Graça, infelizmente, você está tipo de no caminho.
Então, como vamos resolver este problema?
Certo?
Se esta é uma matriz, não há apenas sete localidades.
Lembre-se que, com Rob, nós falamos sobre declarando as idades, e que só tinha um
número finito de idades?
A mesma idéia aqui.
Nós temos apenas um número finito de inteiros.
Graça é uma espécie de em nossa maneira, então como é que vamos resolver?
>> A maneira mais simples é assim, Graça, desculpe.
Você vai ter que passar por cima de lá para que possamos fazer o quarto.
Agora, se você pensar sobre isso, talvez nós apenas piorou o problema.
E talvez nós fizemos, porque o que se Graça estavam no lugar certo?
Mas nós sabemos que ela não é, porque caso contrário, ela teria sido
pé para a frente em vez de Neil neste momento, certo?
Já checou o número para fora.
>> Tudo bem.
Então, agora, Neil está no lugar certo, e Eu posso fazer uma pequena otimização.
Para o próximo minuto, eu vou ignorar Neil todos juntos, de modo a não
desperdice seu tempo, ou acidentalmente trocá-lo para o lugar errado.
Então, agora, como faço para encontrar o próximo elemento que é menor?
Dois.
Isso é um número muito bom, se você quer dar um passo adiante e
Eu vou lembrar de você.
Seis, não é bom.
Quatro, três, sete, cinco, não é bom.
Então deixe-me levá-lo para o seu lugar certo.
E nós só temos sorte desta vez.
>> Agora, eu vou ignorar estes dois caras, e agora fazer mais uma
passar por isso.
Six, que um número muito pequeno.
Vamos em frente.
Oh, desculpe.
Número de Grace é melhor, para pisar para a frente.
Four.
Desculpe, Grace.
Voltar novamente.
O número três é melhor.
Sete.
Cinco.
E agora, qual é o seu nome?
>> JASON: Jason.
>> DAVID J. MALAN: Jason.
Assim Jason é agora o menor elemento eu selecionei.
Onde ele está indo?
Então, onde seis é.
E o seu nome é novo?
>> GABE: Gabe.
>> DAVID J. MALAN: Gabe.
Gabe é o caminho.
Qual é a coisa mais fácil de fazer?
Troque esses dois caras e continuar.
Então, agora vamos ver.
Quem é o menor?
Four.
Deixe-me apenas um tipo de fraude.
Cinco vai ser o menor.
Acho que no próximo, se, você quer pisar para a frente, o que eu tenho a ver com
esses caras, com Gabe?
Troque novamente.
Então, agora, ainda um pouco fora de ordem.
Eu encontrei Gabe para ser o menor, então Eu pop-lo, movê-lo mais caras.
E feito.
>> Assim resposta é a mesma.
O resultado final é o mesmo.
Qual destes dois algoritmos é melhor?
A segunda, eu ouvi.
Por quê?
>> COLUNA 3: é n passos [inaudível].
>> DAVID J. MALAN: É n passos, no máximo.
Interessante.
Assim é que?
Assim como eu encontrar o menor elemento?
Quantos passos que eu tenho que tomar a encontrar o menor elemento?
Eu tinha um olhar todo o caminho no final, certo?
Porque em que o pior caso, o que Neil se foram por aqui?
Então, basta encontrar o menor elemento me n passos, ou n menos 1 leva.
Mas, OK.
Então corrigir Neil.
Lembre-se que, cerca de um minuto atrás.
>> Mas como é que eu encontrar o próximo menor elemento?
É n menos 1, ou n menos 2 realmente, a partir do número de passos.
Então OK.
Então eu fiz n menos 2.
Tudo bem.
Assim que se sente um pouco melhor.
Tudo bem.
Quantos passos da próxima vez encontrar o número três?
Assim, n menos 4.
Então está diminuindo, uma a menos pisar em cada iteração.
Portanto, este não se sentir melhor, certo?
Se a última vez que foi mais ou menos n vezes n, desta vez é menos n 1, mais n menos
2, além de n menos 3, mais n menos 4, ponto, ponto, ponto.
Mas se você se lembra de sua escola livros didáticos, a pequena fraude
folha na parte de trás que tem fórmulas, se você somar essa série de números,
que é o número total de passos será que eu levo aqui?
>> Este é um daqueles, tipo, n menos 1, n vezes, divididos por 2.
Então deixe-me ver se eu posso puxar isso por apenas um momento.
E novamente, eu sou o tipo de arredondamento alguns números apenas para manter nossa vida simples,
mas se bem me lembro, é algo como se Eu n menos uma coisas, então n menos
2, então n menos 3, é mais ou menos algo parecido com isso mais de 2, e se eu
multiplicar isso, é realmente praça n.
Que não está se sentindo muito bem. n n menos mais dois.
>> Mas aqui está a coisa.
Em ciência da computação, quando os problemas começam a ficar interessantes é quando n
fica muito grande.
E quando n fica muito grande, o que de esses valores vai dominar tudo
dos outros?
Ele é o tipo de n ao quadrado, certo?
Sim, dividindo-se por dois é muito bom.
Mas se você está falando de bilhões de pedaços de dados, ou trilhões de
pedaços de dados, ok, então você está duas vezes mais rápido.
Mas quem realmente se importa se esse grande número, Se esse fator é o que recebe
cada vez maior.
E, certamente, faz mais de uma diferença que esse cara.
Assim, mesmo que vocês estão certos, o segundo algoritmo, vamos chamá-lo
seleção de tipo, é, no mundo real, um pouco mais rápido, potencialmente, porque eu sou
tomando cada vez menos passos de cada vez.
>> Realmente não é fundamentalmente mais rápido.
Porque se nós realmente jogar isso para grandes valores de n, no final do
o dia, grande o suficiente para n, ainda é vai sentir-se bastante lento.
Bem, deixe-me tirar uma última passagem por aí.
Isso é o que eu chamaria seleção espécie.
Vocês podem reiniciar-se uma última vez?
E neste último caso, eu vou propor algo
chamado ordenação por inserção.
Ordenação por inserção ser, conceitualmente, um pouco diferente.
>> Ao invés de ir para trás e para a frente e selecionar o menor elemento, eu sou
apenas indo para lidar com cada uma delas caras como eu encontrá-los, e insira
los em seu lugar correto.
Então, eu só vou começar com Graça, e eu vejo que ela é o número quatro.
Onde é que o número quatro pertence?
Eu não comecei nada de triagem, então Grace começa a ficar ali.
E agora eu vou reclamar, se você pudesse dar um passo para a direita, este
minha lista ordenada, essa é minha lista restante indiferenciados.
Então agora eu vou continuar a seguir, e qual é o seu nome?
>> Branson:.
>> DAVID J. MALAN: Branson.
Então Branson é o número dois.
Então, eu vou levá-lo por um momento.
E agora, onde você pertence neste array?
Assim, para o direito de Grace.
Então, novamente, nós somos o tipo de fazer Graça fazer um monte de trabalho aqui.
Onde é que vamos colocá-lo?
Então, nós estamos indo para deslizar-lo para o à esquerda, e inserir Branson lá.
Mas agora eu afirmo que vocês são feitos.
Mas repare, eu não estou usando o espaço extra.
É ainda dois elementos aqui, cinco ali.
Tamanho total do conjunto é de 7, por isso estou não enganar, tudo bem?
>> Portanto, agora temos, com Gabe aqui, o número seis, onde você pertence?
Você teve sorte novamente.
Então, você começa a ficar ali.
Basta dar um leve passo para a direita só para deixar claro que você está classificado.
E agora temos Neil novamente, o número de um, onde você vai?
E agora é o lugar onde nós vamos começar a ver que este algoritmo, que em primeiro
vista, sente-se muito inteligente, assista que está prestes a acontecer.
Se você pudesse avançar.
>> Aonde queremos colocar Neil?
Então, obviamente, aqui, assim como obtemos Neil lá?
Vamos fazer isso passo-a-passo.
Gabe, onde você precisa ir?
Sim, assim que tomar um grande passo, ou duas meias-medidas para tornar
um passo por lá.
Graça, onde você vai?
Bom.
Assim, uma outra etapa.
E, finalmente, Branson?
Outro passo.
E agora podemos colocar Neil no lugar.
>> Então, agora, continuar essa lógica.
Mesmo que não estão mudando Neil mais, e mais, e mais, para colocá-lo
onde ele passa, no pior caso, o próximo número podemos encontrar poderia
ser o número, por exemplo, houve um número zero, então vamos mudar tudo
esses caras.
Suponha-se que há um número negativo um, então temos que mudar
todos esses caras.
Então, nós estamos realmente apenas uma espécie de inversão o problema ao redor, de modo que estamos
transferir a despesa do de modo que o processo de selecção de inserção
processo, de modo que vocês só tinha para movimentar cerca de n menos algo
número de passos.
E esse número de passos é só ir aumentar à medida que eu escolher mais números,
se eu tiver que ficar empurrando vocês para trás, e volta, e volta.
>> Então, a coisa mais triste agora é tudo isso algoritmos são n ao quadrado.
Vamos em frente e, graças a estes caras, e visualizá-las um pouco
diferente.
Muito bem feito.
>> [Aplausos]
>> Tudo bem.
Lá você vai.
Obrigado por -
>> Branson: [inaudível] manter os números.
>> DAVID J. MALAN: Não, você pode manter os números assim.
Tudo bem.
Bem feito.
Tudo bem.
Então vamos ver se não podemos agora resumir mais rapidamente e mais visualmente
exatamente o que aconteceu aqui como se segue.
Eu estou indo para ir em frente e puxe para cima Firefox.
Vamos ligar essa demonstração no site do curso.
Java é um pouco chato para começar a trabalhar em alguns navegadores estes dias.
Então, se você brincar com isso em casa, perceber que você pode precisar usar Firefox
para fazê-lo funcionar.
E o que eu vou fazer com este demonstração é o seguinte.
>> No fundo, eu tenho um monte de opções de menu, incluindo um começo e uma
botão de parar.
Além disso, como um lado, parece haver um bug nesses programas, em que você
não pode realmente ver a partida ou parada botão, a menos que você mantenha Comando ou Alt
mais e zoom in, que curiosamente mostra mais botões.
Portanto, apenas FYI, se você jogar com isso em casa.
Agora eu vou clicar em Iniciar, em apenas um momento, depois de um atraso de especificar,
como, a 200 milésimos de segundo aqui, apenas para que possamos ver o que acontece.
>> Então, eu afirmo que esta é uma visualização do primeiro algoritmo
esses caras fizeram, bubble sort, em que nós trocamos pessoas por pares.
O insight fundamental para essa visualização é que a altura das barras
representa o tamanho do número.
Assim, o mais alto do bar, o Quanto maior o número.
Mais curto da barra, menor o número.
E se você observar, estamos passando por a primeira iteração do algoritmo,
troca de pequenos e grandes números, de modo que o número pequeno vem em primeiro lugar e
o grande número vai para a direita.
>> E assim que chegamos ao final de um array de muitos mais números do que sete, estamos
vai voltar para o início.
E antecipar isso.
Na extrema esquerda, que o rapaz está acontecendo para trocar para o lado, e isto
processo se repete.
Agora essa visualização fica rapidamente chato, então deixe-me ir em frente e parar
, mude o atraso algo muito mais rápido apenas para começar agora, uma sensação de
este algoritmo.
>> Assim, mesmo que eu acelerava-se, este é como atualizar meu processador, comprando
um novo computador.
Eu não mudaram fundamentalmente o meu algoritmo, mas você pode realmente ver mais
claramente do que com os seres humanos, que a grande números estão borbulhando até o topo,
e os números pequenos estão borbulhando para a parte inferior.
E agora essa coisa aqui classificados.
E, como um aparte, nas praças, há apenas algumas escrituração lá para
ajudá-lo a contar quantas comparações, ou quantos swaps têm
realmente foi feito.
>> Bem, vamos tentar uma das os outros que vimos.
Deixe-me clique no bubble sort aqui, e deixe-me escolher, e esta página inteira
é um pouco buggy.
Vamos aceitar o risco e executá-lo novamente.
Lá vamos nós.
Então vamos fazer a seleção tipo.
Eu não sei por que o menu aparece por lá.
Vamos zoom para corrigir isso bug, mudar isso para 50.
Ah, vamos realmente fazer muito mais rápido.
Cinco milissegundos ou menos, e começar.
>> Portanto, esta é a seleção de tipo.
Então, novamente, pensar sobre o que fez com os seres humanos aqui.
Nós fomos através da matriz e selecionados o elemento mais pequeno, novamente,
e de novo, e de novo.
Agora eu afirmo que ainda era muito ruim.
Foi ainda n ao quadrado, mais ou menos, mas foi, no mundo real, um pouco
mais rápido, porque eu estava realmente tomando ligeiramente menos passos de cada vez.
Mas estamos apenas falando o quê?
Talvez 40 ou mais bares aqui?
Não estamos falando de 40 milhões.
Portanto, não é totalmente claro para mim que era de fato um ganho significativo.
>> Deixe-me agora voltar atrás e mudar a nossa terceiro algoritmo, que foi selecionado
ordenação por inserção.
E agora é realmente de buggy, pois o menu realmente não deveria estar lá.
Então, agora vamos rolar para trás até aqui e iniciar este algoritmo.
Whoop, começar e parar.
Assim, este tipo de tem um padrão bastante a ela, em que estamos mais uma vez
inserindo os seres humanos, ou em Neste caso, as barras em
a sua localização apropriada.
E ele já fez antes Eu me virei.
Mas este, também, em teoria, ainda n ao quadrado.
>> Então vamos ver se não podemos resumir estes como segue.
Eu estou indo para ir em frente e apenas para dar nós tipo de uma maneira comum de falar
sobre essas coisas, deixe-me apresentar apenas um pouco de notação aqui.
Você está prestes a ver uma coisa chamada grande Ó, porque é literalmente uma grande
O. e esta é uma forma que um computador cientista ou um matemático ainda usa
para descrever o tempo de execução de um algoritmo.
Quantos passos ele realmente tomar?
>> Agora eu vou me envergonhar com minha letra aqui em apenas um momento.
Mas deixe-me ir em frente e dizer que isso vai ser grande por aqui ó.
E deixe-me apresentar um outro símbolo, um omega capital.
Omega vai ser o oposto, essencialmente, de grande O. Considerando que a grande O
significa, no pior dos casos, a quantidade de tempo pode levar algum algoritmo, em
termos de n, omega vai ser quanto tempo ela poderia
tomar na melhor das hipóteses.
E vamos ver o que se entende por melhor das hipóteses, em apenas um momento.
>> Então, vamos começar algo simples.
Deixe-me começar com uma busca linear.
Portanto, não a classificação.
Vamos chamar essa busca linear.
E agora, fazer um pouco de mesa de fora dessa.
E agora, no caso da pesquisa linear, no pior caso, quantos passos é
ele vai me levar para encontrar uma número de escolha arbitrária?
E há n portas totais ou n números totais.
Pior caso.
Quantos passos eu vou ter que tomar para encontrar o número 50 em uma matriz
de n portas?
E por quê?
Porque ele pode ser tudo o caminho para o fim.
Tanto como Jennifer encontrado, o número 50 foi todo o caminho, por isso,
o pior busca linear caso é grande O de n, vamos dizer.
>> E quanto melhor das hipóteses, se tiver muita sorte?
Só vai dar um passo, ou um número constante de passos.
Então, vamos descrever isso como um.
Então, isso é muito bom.
Agora, o que se fez alguma coisa como busca binária?
Pesquisa de modo binário, no pior caso, levou quanto tempo?
>> [Interpondo VOZES]
>> DAVID J. MALAN: Então, na verdade, eu ouvi em alguns lugares.
Então, é realmente entrar n, mais ou menos, porque, como nós dividimos a lista ao meio
novamente, e novamente, e novamente, somos capazes para encontrar, finalmente, o valor,
se ele está lá, mas há uma pegadinha.
Qual é a suposição de que nós temos que ter concedido para a busca binária?
Tem que ser resolvido.
Não está resolvido, você pode dividir a coisa ao meio de novo e de novo, e você
pode ir para a esquerda, e você pode ir para a direita, e você pode ir para a esquerda e para a direita, mas você é
não vai encontrar o elemento se a lista não está ordenada, porque
você pode perdê-la.
Porque a sua heurística, para ir à esquerda ou para a direita vai ser falho, se é
na verdade, não classificados.
Portanto, há uma espécie de custo oculto para usar algo assim.
>> Agora, vamos para a nossa classificação algoritmos não busca -
oh, realmente vamos entrar em branco.
Busca binária na melhor das hipóteses?
É também um caso só acontece de ser bem no meio da matriz, ou
no meio da lista telefônica.
Agora vamos fazer o bubble sort.
Então, novamente, agora estamos entrando na tipos, e não as pesquisas.
>> No pior dos casos, quantos passos que fizemos reivindicação bubble sort vai levar?
n ao quadrado.
Então eu vou tirar isso.
Ooh, minha letra parece ainda pior quando está previsto que grande.
Tudo bem.
Então isso n ao quadrado.
E, na melhor das hipóteses de bubble sort, quantos passos é que vai tomar?
1, eu ouvi.
>> COLUNA 1: n.
>> DAVID J. MALAN: n, eu ouvi.
>> COLUNA 1: 2.
>> DAVID J. MALAN: 2, eu ouvi.
Ouço 3?
Tudo bem.
Então eu ouvi 1, n, 2, mas vamos escolher para além de pelo menos a primeira dessas
sugestões, 1.
Não é um mau instinto, porque tipo de segue um padrão aqui.
Mas se ele só tem um passo, como no mundo que eu poderia reclamar que a lista
é ordenada, porque se eu estou apenas permitida tomar um passo, quantos elementos
Na verdade, eu poderia verificar para ter certeza?
Bem, só um, o que significa que há n menos um elementos que poderiam estar fora de
ordem, e eu só vou na fé depois olhando para um elemento que o
coisa está classificada.
Então 1 não é correto aqui.
Assim, minimamente, quantos que eu tenho que olhar?
>> [Interpondo VOZES]
>> DAVID J. MALAN: n menos 1, ou realmente, n, porque eu preciso olhar para cada
elemento para certificar-se de que não está fora de ordem.
Mas, novamente, nós vamos resolver de onda nossa mãos em números menores e
supor que, à medida que n se torna grande, eles são desinteressante qualquer maneira.
Então, isso é bubble sort.
E agora, vamos fazer esses dois últimos.
Tipo de seleção, e depois vamos fazer ordenação por inserção.
E então vai explodir sua mente com algo muito
melhor do que todos estes.
Tudo bem.
>> Qual é o pior caso em execução momento da seleção tipo?
>> COLUNA 4: n ao quadrado.
>> DAVID J. MALAN: n quadrado, estou ouvindo.
Mas por que n ao quadrado, intuitivamente?
>> COLUNA 4: Porque nós só fiz isso.
>> DAVID J. MALAN: Porque nós só fiz isso.
OK.
Boa resposta.
Mas, intuitivamente, por que é a seleção tipo n ao quadrado?
O que temos que fazer uma e outra vez?
Tivemos que manter a digitalização através, são você o menor, é o
menor, é o menor.
E concedido, fomos capazes de tomar n passos, então n menos 1, então n menos 2.
Mas se você espécie de adicionar todos aqueles acima, ou levá-la na fé que eu adicionei
-los com antecedência, temos cerca de n quadrado menos alguns números menores.
Então, eu vou ligar para este n ao quadrado.
Mas, com a seleção de tipo no melhor caso, quantos passos é
vai me levar?
>> COLUNA 5: [inaudível]
>> DAVID J. MALAN: É, infelizmente, ainda n ao quadrado, certo?
Porque se eu estou selecionando o menor elemento, e tivemos sete pessoas aqui,
Eu só sei que, quando eu chegar ao muito final, que eu encontrei a menor
número, onde quer ela pode ter sido.
Mas como faço para encontrar o próximo menor número?
Eu tenho que fazer outra passagem.
Assim, no melhor dos casos, o que é o de entrada para a seleção tipo?
É uma lista já espécie, número um, número dois, número três, número quatro.
Mas eu sou um computador.
Eu só posso olhar para um coisa de cada vez.
Eu não posso classificar de dar um passo de volta como um ser humano e dizer:
ooh, isso parece correto.
>> Eu só posso julgar correto em seleção espécie, selecionando o
menor número.
Mas mesmo se eu encontrar o número um em primeiro lugar, se eu não sei mais nada sobre
os outros números, o que eu não faço, tudo o que eu sei que tenho sido entregue uma matriz
ou um conjunto de portas de trás, que são números, a única maneira que eu sei que um
foi a menor?
Se eu chegar até aqui e perceber, caramba, uma era de fato o menor.
>> Mas como faço para, então, determinar que dois é a próxima menor?
Ao fazer a mesma ineficiência uma e outra vez.
Então, finalmente, com a ordenação por inserção, como, na pior das hipóteses,
se dizemos que ele executa?
Ele também é n ao quadrado.
E que tal com o melhor caso?
Vamos deixar isso como um cliffhanger.
Vamos preencher esse vazio da próxima vez, mas primeiro deixe-me propor que
fundamentalmente fazer melhor do que tudo isso, certo?
>> Então, pense por si mesmo que a inserção tipo vai ser.
Bem, isso não era muito dramática, porque eu sou o único
que viu a mudança.
Uau.
OK.
Então aqui nós temos um pouco demonstração diferente.
Se eu aumentar o zoom aqui, você vai ver que em À esquerda temos bubble sort, no
meio temos a seleção de classificação, e em a extrema-direita, nós temos algo que
não olhei ainda chamado merge sort.
Mas considere o que temos sido fazendo aqui, até agora, hoje.
Quando Jennifer veio pela primeira vez em cima do palco, passamos a matriz de números
novamente, e novamente, com busca linear, e temos tempo de execução linear, grande o
de n, por assim dizer.
>> Quando consideramos agora a primeira semana de classe, quando tínhamos dividir e conquistar,
e nós tínhamos o livro de telefone lacrimejamento, e Jennifer, e nós coletivamente
alavancado esse insight fundamental, que era repetir-se uma e outra vez por
alguma forma de jogar fora, jogando fora, jogar fora, metade do problema, ou
Geralmente, dividindo-se um problema no meio, e depois tratando o pedaço menor de
o problema como conceitualmente equivalente para a outra, que de alguma forma fez
fundamentalmente melhor.
Mas com o bubble sort, com a seleção tipo, com ordenação por inserção, temos pode
nenhum desses insights que Jennifer fez.
Nós praticamente só andou para trás e diante de um grupo inteiro de vezes, e nós
coisas mexido um pouco, trocando por esta ordem, talvez
inserir ou selecionar.
Mas no final do dia, eu fiz um monte de andar desajeitado e para trás.
Nós não realmente aproveitar algo inteligente como Jennifer gostou dividindo
e conquistador.
>> Assim tipo fundir, pelo contrário, que não vai ver até a próxima semana, ele vai
para alavancar a idéia chave, dividindo de entrada e, em seguida, reduzir para metade e, em seguida
reduzir para metade, em seguida, reduzir para metade.
E, em cada iteração do loop de que, classificando a metade esquerda e à direita
de metade, em seguida, a metade esquerda da metade esquerda, ea metade direita da esquerda e, em seguida
a metade esquerda da metade direita, e a metade direita da metade direita.
E repetindo uma e outra vez.
>> Então, você vai ver isso visualmente, mas esta é o que nos espera na próxima semana.
E, em geral, quando pensamos um pouco pouco mais difícil em qualquer problema desse tipo.
Nós n ao quadrado do lado esquerdo, n quadrado no meio, e n
log n à direita.
Portanto, não há o suspense real.
Vemo-nos na segunda-feira.
>> [Aplausos]