[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]