Palestrante: Tudo bem, essa é CS50. Isto é o fim de semana de três, e, se você não tenha aproveitado já, sei que haverá almoço nesta sexta-feira, como de costume, onde você pode desfrutar de uma boa conversa e alimentos em Fire and Ice com alguns dos CS50 de funcionários e colegas. Confronto esta URL aqui. Agora você pode recordar, ou você pode em breve estar familiarizado com, essas coisas aqui, que são dadas no final do semestre para muitas classes. O chamado exame de livros azuis, em que você escrever suas respostas para os exames. Agora eu tenho aqui 26, tais livros azuis, em cada um deles está escrito um nome, de A a Z. E na verdade, os nomes são assim tão simples, A a Z. E uma das as metas em mãos hoje vai ser para continuar o que começamos na segunda-feira, que não é tanto olhar o código, mas realmente olhando para ideias e resolução de problemas. Um dos objetivos e promessas deste curso é ensiná-lo a pensar mais cuidado, mais metodicamente, e para resolver os problemas de forma mais eficiente. E, de fato, nós podemos fazer o que realmente sem sequer tocar uma linha de código. Então, eu tenho um par de elefantes aqui hoje, laranja e azul, se pudéssemos obter um voluntário, talvez de mais para trás do que o habitual. Que tal ali mesmo, vamos lá para baixo. O objetivo do que vai ser a ajudar mais administrar este exame aqui. Qual o seu nome? AUDIÊNCIA: Mary Beth. Palestrante: Mary Beth, vamos lá para cima. Deixe-me pegar o microfone aqui para você. Prazer em conhecê-lo. AUDIÊNCIA: Prazer em conhecê-lo. Palestrante: Tudo bem, então eu tenho aqui livros azul de A a Z, e eu vou fingir que Eu tenho um dos alunos, e eles estão vindo em um tanto aleatoriamente no fim de um bloco de exame três horas, então eles estão acabando em alguns ordem semi-aleatória assim. Agora o seu trabalho em apenas um momento que vai para ser-- este é realmente como eles se entregues no final a classe, o mais provável. Seu trabalho agora vai ser, bastante simplesmente, para classificar esses livros azuis para nós de A a Z. AUDIÊNCIA: Oh, isso é vai levar para sempre. Orador: E vamos assistir como você faz isso, sem pressão. AUDIÊNCIA: Não, nenhuma pressão nem nada. Orador: E para se divertir, vamos colocar um temporizador. AUDIÊNCIA: muito divertido, muito divertido. Palestrante: eu posso segurar o microfone para você. Tudo bem, nós apenas dobrou a nossa velocidade. Então, nesse meio tempo, deixe-me colocar o que há de vai ser a pergunta de Mary Beth é o que ela está fazendo, como está ela vai sobre como resolver isso? E, na verdade, você não pode ter já pensou em algo tão simples como quando você escolhe até 26 livros como este, que tem um talento natural ordenando a eles. Qual é o processo que você realmente usa? É bastante aleatório apenas escolher o primeiro que você vê e colocá-lo em seu lugar? Você primeiro mover suas mãos em torno Procurando um em seguida, olhando para B? Você dar uma olhada em um par deles lado a lado e apenas dizer, espere um minuto, isto Não é certo, e, em seguida, trocar a ordem? Nós já vimos na segunda-feira que há uma série de maneiras em que podemos fazer isso, e na verdade, como estamos perto do final aqui, Eu tomaria nota talvez do que Mary Beth está fazendo. Temos algumas pilhas que parece, um maior, três menores. AUDIÊNCIA: Estou ordenando-lhes quando eu encontrar duas cartas que eu sei que estão juntos em uma seqüência, Eu colocá-los juntos para que eu não tem que se preocupar em manter o controle de uma linha inteira de livros. É apenas, oh, A é o primeiro, Eu tenho essa pilha aqui. Palestrante: Então, quase como de peças de quebra-cabeça que tem a forma certa para combinar-se um com o outro. AUDIÊNCIA: Muito bonito, sim. Palestrante: OK, excelente. E agora cada um destes pilhas é presumivelmente ordenado? AUDIÊNCIA: Yeah. Palestrante: Tudo bem, de A a Z. Todos certo, parabéns, você fez isso. Você tem a sua escolha. Azul? Tudo bem, obrigado por isso. Então Mary Beth se propôs que sua abordagem era, mas o que é uma outra abordagem como você pode ir sobre como classificar essas coisas? O que você teria feito? O recorde de bater teria sido um minuto e 50 segundos ou menos, mais os que eu esqueci de contar. O que você teria feito? Sim? AUDIÊNCIA: Pegue a pilha. Comece desde o início. Verifique os seus papéis. E se o de cima é maior do que, talvez, eles são, o fundo é superior, em seguida, desligá-los. Palestrante: OK, assim que começar na parte superior e na parte inferior, e, em seguida, trabalhar o seu caminho dentro desse jeito, trocando-os? OK, então um pouco semelhante em espírito de bubble sort, mas escolher os extremos não os pares adjacentes. Mas o curto do que é que há certamente um monte de maneiras diferentes nós poderíamos fazer isso, e francamente, acho que tipo de adotou algumas abordagens, certo? Você fez uma espécie de quatro pilhas ordenadas, e então efetivamente fundiu-los juntos. E isso é, ouso dizer, uma outra técnica completamente. Você não tratá-lo como uma grande pilha, você divide o problema em quatro quadriláteros, se você quiser, e depois de alguma forma fundiu-los no final. Então, vamos considerar, em última análise, De que outra forma poderíamos fazer isso. Nós formalizou a noção de bubble sort última vez, e recordação bubble sort foi um algoritmo que visualizamos com oito de seus colegas aqui em cima, aparentemente aleatoriamente classificados em primeiro lugar. E nós, então, decidiu pares, se dois elementos estão fora de ordem, simplesmente trocá-los. Então, quatro e dois são obviamente, fora de ordem, então esses dois colegas trocar de posição. E, então, repetido com quatro e seis, em seguida, seis e oito, em cada iteração, movendo para a direita. Assim, dado oito pessoas, quantos pares comparações que eu fiz durante a caminhada de esquerda para a direita em um tal iteração? Quantas comparações? Sete, certo? Porque se há oito pessoas, mas você tem o par eles e você continuar se movendo um salto para a direita, você não vai ter oito comparações, porque você não pode comparar um elemento contra si, ou que seria basta ser inútil, então você tem sete. Ou, mais geralmente, se temos n pessoas, nós fazer N menos 1 comparações com bubble sort. Então, vamos considerar agora como bom ou ruim bubble sort realmente era, e tentar dar-nos vocabulário com que a algoritmos crítica como esta, e logo a nossa. Então, a primeira passagem através bubble sort, pela primeira vez Eu andei a partir da esquerda para a direita na palco, me n menos 1 comparações tomou. E isso vai ser meu unidade de medida, certo? Eu era uma espécie de falar e caminhar, um tanto rapidamente, um tanto lento, assim contando meu número de segundos não é particularmente revelador, mas a contagem do número de operações que eu fiz na segunda-feira, comparando duas pessoas, que se sente como uma agradável unidade de medida. Então n menos 1 passos pela primeira vez, Mas então o que aconteceu depois disso? Qual é a única cabeça de uma só vez através de uma lista de outra forma não ordenada? O que você pode me dizer sobre o elemento que foi todo o caminho até lá? Sim? Esse foi o maior elemento, certo? O número oito, embora ela começou aqui, toda vez que eu comparado a contra um vizinho, ela manteve borbulhando-se para a direita lado da lista. E, de fato, que é onde o algoritmo recebe o seu nome. Agora por essa lógica, quantas comparações eu vou fazer no segundo tempo Eu faço que passe da esquerda para a direita? n menos 2, certo? Seria apenas perdendo meu tempo se eu manter comparando oito contra alguém mais porque já sabemos ela estava no lugar certo. Então, isso é um pouco de um otimização, de modo que o próximo passo vai ser mais n menos duas etapas, onde n é o número de pessoas. Agora você pode tipo de extrapolar, mesmo se você não é um cientista da computação, como isso termina. No final deste algoritmo, presumivelmente você tem apenas uma comparação esquerda. Você tem que tipo de corrigir o início da lista, no caso de dois e um está fora de ordem e deve ser um e dois, de modo que este encoste na além de uma comparação final. Agora, o ponto, ponto, ponto tipo de ondas é mãos em alguns dos detalhes mais suculentas, mas vamos apenas ir em frente e simplificar. Se você se lembrar de alta escola, francamente, muitos de vocês tinham livros de matemática que tinham uma folha de fraude pouco na capa ou a tampa traseira que mostrei somatórios que séries como Esta última análise, somou. No caso geral, se você tem um variável como n, e de fato este, Se você olhou para sua livro de matemática velha escola, você veria que isso realmente acrescenta-se a esta soma aqui, n vezes n menos 1 tudo dividido por 2. Então, por agora, deixe-me apenas estipular isso é verdade, então em um ato de fé, isso é o que isto resume até, e pudemos provar que, num caso mais geral. Mas agora vamos expandir isso. Então, vamos multiplicar isso, o que é n ao quadrado, menos n, tudo dividido por 2. Isso é realmente n ao quadrado, dividido por 2, menos n mais de 2, de modo que é tudo bom e interessante. Mas o que acontece se nós agora plug-in um valor? Suponha que eu não tinha oito pessoas, mas dizem que um milhão. E um milhão só porque que é um número muito grande, vamos ligar isso e ver o que acontece. Então, se eu ligar um milhão para que a fórmula Eu estou indo para obter um milhão de quadrado, dividido por 2, menos uma milhões, dividido por dois. Agora, o que é que isso vai ser igual? Assim, 500 bilhões, menos 500.000. E se eu realmente fazer que a matemática, isso significa que que a classificação de um milhão pessoas com o tipo de bolha pode me levar 499999500000 etapas ou comparações, no final, nós apenas estamos extrapolando. Que se sente muito lento, mas francamente medição de uma entrada especial assim, não é tão revelador. Mas na verdade, ela sugere que como n torna-se maior e maior, este algoritmo tipo de sente pior e pior, ou você realmente começar a sentir a dor do que exponenciação, que n ao quadrado, que acrescenta-se muito rápido. E esse detalhe não é perdido nas pessoas, na verdade, há alguns anos, um certo senador que foi campanha, sentou-se para uma entrevista com Eric do Google Schmidt, CEO na época, e foi desafiado com uma pergunta assim como nós estamos explorando hoje. Vamos dar uma olhada. [REPRODUÇÃO] Senador, você está aqui no Google, e eu gosto pensar na presidência como uma entrevista de emprego. Agora, é difícil conseguir um trabalho como presidente, e você está passando os rigores agora. Também é difícil conseguir um emprego no Google. Nós temos perguntas, e nós nossas perguntas candidatos, e este é de Larry Schwimmer. O que-- vocês acham que eu sou brincadeira, é aqui mesmo. Qual é a maneira mais eficiente de classificar um milhão de inteiros de 32 bits? -Well-- Estou muito, maybe-- Não, não, não. Eu acho que o bubble sort seria o caminho errado. Vamos, que lhe disse isso? Eu não vi computador ciência em seu fundo. -Temos Nossos espiões lá dentro. -OK, Vamos pedir um diferente pergunta da entrevista. [FIM REPRODUÇÃO DE VÍDEO] Palestrante: Então, falando números específicos, embora Não vai ser tão útil. Não é uma lição de vida que bolha tipo, dado um milhão de entradas, pode levar até 500 bilhões etapas. Você realmente não pode generalizar muito eficazmente desde que e tomar boas decisões de design ao escrever programas. Então, vamos nos concentrar em como embora podemos simplificar este resultado. Então, eu tenho realçado em amarelo aqui o resultado de n quadrado dividido por dois, assim um milhão quadrado dividido por dois, e depois Eu destacou que a resposta final foi uma vez que fora subtraído n dividido por 2. E a alegação de que eu vou fazer agora é, quem diabos se importa se você subtrair off um pouco mais de idade n 2 quando o primeiro parte desta fórmula é muito maior? Ele domina o outro prazo, n quadrado dividido por dois é muito maior, de forma clara, como n se torna grande como um milhões, que há realmente uma grande diferença no No final do dia entre 500 mil milhões e 499.999.500.000? Não é realmente. E então o que vamos fazer o que os cientistas da computação é ignorar esses termos de ordem mais baixa e ter algo parecido com isso e realmente apenas para simplificar a termo que vai importar. Os maiores nossos conjuntos de dados começa, o maior nossas bases de dados começa, mais páginas da web temos que procurar, o mais amigos você tem no Facebook. Como n fica maior, estamos muito vai se preocupar com a maior prazo em qualquer análise de nosso desempenho algoritmos. E eu vou dizer, você sabe o que, bubble sort é da ordem de O grande, na ordem de n ao quadrado. Não é exatamente n quadrado, como vimos, mas quem realmente se importa sobre esses termos menores, e, francamente, que realmente se importa se dividirmos por 2? Isso é apenas um fator constante. E é de 500 bilhões contra 250 bilhões que realmente de um grande negócio? Eu poderia apenas esperar um ano, deixar meu laptop literalmente obter duas vezes mais rápido em hardware, e esse tipo de diferença apenas desaparece naturalmente ao longo do tempo. O que nos interessa é a expressão, a peça da expressão que vai variar como nossa entrada fica maior e maior. E, de fato, no mundo real, isso é o que está acontecendo cada vez mais é as entradas para os nossos problemas e algoritmos estão ficando maiores. Então, ó grande vai ser a notação, a notação assintótica, que acabamos de usar como cientistas da computação para descrever o desempenho, ou o tempo de funcionamento, de um algoritmo. Para que possamos comparar algoritmos em computadores diferentes escritos por pessoas diferentes, usando alguma métrica fundamentalmente semelhantes como o número de comparações que você é fazendo, ou talvez o número de swaps você está fazendo. O que nós não vamos contagem é a quantidade de tempo que passa no relógio tipicamente na parede. O que nós não vamos nos preocupar é sobre a quantidade de memória você está usando hoje em menos importante, embora isso seja outro recurso que pode medir. Nós vamos tentar basear nossas análises em apenas as operações básicas, aquelas, francamente, que você pode ver mais visualmente. Assim, com algo como grande O de n quadrado, eu afirmo que O de n ao quadrado é um limite superior sobre o chamado tempo de funcionamento do bubble sort. Em outras palavras, se queria afirmar que há este limite de quantos as etapas de um algoritmo pode levar, ele vai estar no grande O de n quadrado, neste caso, um limite superior. E se eu não mudar o história a não ser sobre bubble sort, mas sobre o limite superior. Você pode pensar em um algoritmo que nós olhamos já cujo limite superior, máximo medida de tempo ou de operações, seria dito ser limitado por n, de uma função linear, não um quadrática que é curvo? O que é um algoritmo que sempre leva mais do que como n passos, ou 2n passos ou etapas 3n? Sim? AUDIÊNCIA: Encontrar o maior número em uma lista? Palestrante: Perfeito, encontrando o maior número em uma lista. Se eu estou com uma lista de pessoas, por exemplo, cada um que está segurando um número, o que é o número máximo de passos que deve tomar de mim, uma pessoa razoavelmente inteligente, para encontrar o maior pessoa nessa lista? n, certo? Porque, no pior caso, em que talvez o maior valor ser? Certo, todo o caminho no final. Assim, no pior caso limite superior, eu poderia tem que ir todo o caminho até aqui e ser como, oh, aqui está o número oito, ou o que quer que o valor é. Agora seria simplesmente estúpido se eu continuei indo, certo? À procura de mais e mais elementos se o último deles é ali? Assim, certamente, n é um limite superior. Eu não preciso de tomar mais etapas do que isso. Então, o que se em vez propus que existem algoritmos neste mundo que ter um tempo de execução que é delimitada pela grande O de log n, log n? Onde já vimos isso antes? Sim? AUDIÊNCIA: No problema de lista telefônica? Palestrante: Como o problema agenda. Qual foi a medida de quão muito tempo ou quantas lágrimas de TI me levou para encontrar alguém como Mike Smith na lista telefônica? Nós alegou que era log n, e mesmo que desconhecido ou que é um pouco nebuloso o que é um logaritmo ou expoente foi, lembre-se que log n geralmente refere-se ao processo, neste caso, a divisão algo em metade, e novamente, e de novo, e de novo, de tal modo que ele fica cada vez mais pequeno, como você faz isso. Então log de n refere-se, com certeza, a exemplo do livro de telefone, a busca binária, em teoria, quando teve as portas virtuais no conselho, ou quando foi Sean procurando por algo. Se ele tivesse usado a busca binária, log n seria o limite superior da quantidade de tempo que leva. Mas os algoritmos que decorreu em log n assumiu o detalhe chave? Que a lista foi resolvido, certo? Seu algoritmo é errado se sua entrada não é classificada, e ainda assim você estiver usando algo como busca binária porque você pode saltar direito sobre o elemento sem perceber que é de fato lá. Agora, o que isso pode significar, ó grande de um? Isto não significa que o seu algoritmo toma uma e apenas uma etapa, significa apenas que é preciso uma número constante de passos. Talvez seja um, talvez seja 10, talvez seja 1000, mas é independente do o tamanho do problema. Não importa quão grande é n, um algoritmo de tempo constante faz sempre o mesmo número de passos. Então, o que pode ser um algoritmo falamos ou apenas intuitivamente que vem a você que sempre é executado na chamada constante de tempo? Sim? AUDIÊNCIA: Adicionar dois números. Palestrante: Adicionar dois números, 2 mais 2 é igual a 4, feito. Para que possa funcionar, o que mais? Que tal mundo mais real, certo? AUDIÊNCIA: Encontrar o primeira coisa em uma lista. Palestrante: Encontrando-se o primeiro elemento em uma lista, com certeza. Fomos realmente falando sobre matrizes já, como fazê-lo no primeiro elemento de uma matriz, não importa quanto tempo a matriz está em código C? Você acabou de usar como o suporte notação zero, bam, você está lá. E, de fato matrizes, como um aparte, suporte algo geralmente conhecido como de acesso aleatório, de acesso aleatório memória, porque você pode literalmente saltar para qualquer um só lugar. Nós podemos fazer isso ainda mais simples podemos retroceder a semana de zero quando fizemos zero. Quanto tempo demorou para o dizer bloco em risco a executar? Apenas tempo constante, certo? Diga alguma coisa, dizer alguma coisa, não importa como grandes arranhões mundo é, é sempre vai ter a mesma quantidade de tempo simplesmente dizer algo. Então é tempo constante, mas o que é o outro lado? Se isso fosse superior limites, o que se quer para descrever os limites inferiores dos nossos algoritmos de tempo de execução? Quase um melhor caso potencialmente, se quiserem, embora esses termos poderia se aplicar a melhor casos, piores casos, casos de média mais geralmente, mas vamos focar em limites inferiores de forma mais geral. O que é um algoritmo que tem um limite inferior de n passos, ou 2n passos ou etapas 3n? Alguns fator de n passos, que é o seu limite inferior. Sim? AUDIÊNCIA: Bubble sort? Palestrante: Bubble sort leva você minimamente n passos, por quê? Por que é que? Por que que começam a vir até você intuitivamente, mesmo se isso acontecer não apenas ainda? Sim? AUDIÊNCIA: [inaudível]. Palestrante: Exatamente. No melhor cenário possível de bubble sort, e um monte de algoritmos, se eu entregar-lhe oito pessoas que já são classificadas, seria insensato para você, o algoritmo, para ir e voltar mais de uma vez, certo? Porque assim que você caminhar através da lista uma vez, você deve perceber, oh, eu não fiz nenhum swaps, esta lista é ordenada, saia. Mas isso vai levar você n passos. E, inversamente, o que é outra maneira de pensar sobre isso? Bubble sort é um omega, por assim dizer, de n, porque se você olhar para menos de n elementos, o que é a questão fundamental não? Você não sabe se ele está resolvido, certo. Nós os seres humanos possam olhar para oito pessoas e ser como, oh, ele é classificado, que não me n passos tomar, mas ele fez. Seus olhos, mesmo que você tipo de ter um grande campo de visão, você olhou para oito elementos, você olhou para oito pessoas, isso é oito passos de forma eficaz. E só se eu andasse pelo todo lista que eu percebo, sim, classificada. Se eu parar no meio do caminho pensando: tudo direito, é bem resolvido, até agora, quais são as chances que não é ordenado? Isso não os de um algoritmo vai ser correto. Pode ser mais rápido, mas incorreto. Então, agora nós temos uma maneira de descrevendo um limite inferior, E quanto tempo constante? O que é um algoritmo que tem uma menor obrigado em seu tempo de execução de um? 1 passo, dois passos, 10 passos, mas constante, independente de n, o tamanho da entrada? Sim, na parte de trás. AUDIÊNCIA: printf? Palestrante: O que é isso? AUDIÊNCIA: printf? COLUNA: printf. OK, com certeza. Então, é preciso um número fixo de passos. E eu deveria agora-- agora que estamos falando de código C e não arranhar, algo como dizem, com printf, devemos começar a ter cuidado. Porque printf leva entrada, é uma string, e as cordas que tecnicamente tem comprimento. Então, se nós agora quer escolher em você, se você não se importa, tecnicamente poderíamos argumentar que printf toma uma entrada de comprimento variável, e, certamente, isso pode levar mais tempo para imprimir uma seqüência de tanto tempo, do que este tempo. Então, o que se considerarmos apenas o classificação e pesquisa exemplos? E sobre Mike Smith no telefone livro, ou busca binária mais geral? No melhor dos casos, o que pode acontecer? Abro o livro de telefone e, bam, há número de Mike Smith. Posso chamá-lo de imediato. Deu um passo, talvez duas etapas, mas um número constante de etapas se eu tenho sorte. E, francamente, nós vimos em Segunda-feira seu colega de classe ficar bastante sorte duas vezes seguidas. E isso era realmente constante vez em limites inferiores no algoritmo em questão para encontrar o número 50 atrás daqueles fechado portas. Agora, como um aparte, se você descobrir O que tanto grande, o limite superior e omega, o limite inferior, são um na mesma, que é a mesma fórmula em parênteses, você também pode dizer, apenas que ser extravagante, que algo está em theta de n ou teta de algum outro valor. Isso significa apenas que quando grande O e omega são os mesmos. Agora o que acontece com a seleção tipo? Vamos usar esse novo vocabulário. Na seleção de classificação, o que estávamos fazendo de novo, e de novo, e de novo? Eu estava indo para trás e para frente através de da lista, à procura de quem? O menor número. Assim como muitos passos, como muitas comparações fez I tem que fazer, a fim de descobrir quem o menor elemento na lista foi? n menos um, certo? Porque se eu começar com o que eu sou dada e eu começar a comparar a ele ou ela, em seguida, ele ou ela, ele ou ela, ele ou ela, eu só pode emparelhar elementos juntos n menos 1 vezes. Assim, a seleção leva espécie semelhante n menos passos 1 a primeira vez. Quantos passos ele me levar para encontrar o segundo menor elemento? n menos 2, porque eu estou sendo idiota se eu continuar olhando para as mesmas pessoas novamente se eu já o escolheu ou ela e colocá-los em seu lugar. E o terceiro passo, n menos 3, então n menos 4. Vimos este padrão antes, e de facto seleção espécie semelhante tem um limite superior de n ao quadrado, se fizermos o que soma. Qual é o seu limite inferior, a seleção tipo? No mínimo, quanto tempo de seleção deve tipo tomar, como definido na segunda-feira? Propor duas opções. Talvez seja n, como antes. Talvez seja n ao quadrado, como é agora como o limite superior. AUDIÊNCIA: n ao quadrado. Palestrante: n ao quadrado. Por quê? AUDIÊNCIA: Porque você tem definir [inaudível]. Palestrante: Exatamente. Pelo menos enquanto eu definido seleção espécie era muito ingênuo, continue indo, encontrar o menor elemento. Vá mais uma vez, encontrar o menor elemento. Vá mais uma vez, encontrar o menor elemento. Não há nenhum tipo de otimização lá que pode deixar-me abortar depois apenas n ou mais etapas. Assim, de facto, a selecção tipo, omega de n ao quadrado. Que tal tipo de inserção, onde tirei que me foi dado, e então eu estatelou-lo ou ela no lugar certo? Então eu continuei a segunda pessoa, estatelou-lhe no lugar certo. Então, a próxima pessoa, se estatelou ele ou ela no lugar certo. Observe que isso é muito linear, por assim dizer. Eu sou uma linha reta, eu sou não indo e voltando, Eu nunca olhar para trás, realmente, mas o que está acontecendo quando eu inseri-lo ou ela no início do lista como fizemos na segunda-feira? O que está acontecendo? Sim? AUDIÊNCIA: [inaudível]. Palestrante: Sim, isso foi a captura, certo? Você pode se lembrar de seus colegas de classe, se eles estavam fazendo qualquer movimento com seus pés, que era uma operação. Portanto, se havia três pessoas aqui e a nova pessoa pertencia caminho até lá, em uma longa fase como esta, com certeza, ele ou ela poderia apenas ir até o fim. Mas, se estamos pensando em um computador e uma matriz de memória, essas pessoas vão ter para baralhar mais para dar espaço para essa pessoa. E assim que n menos um shufflings, n menos 2 shufflings, n menos 3 shufflings é apenas uma espécie de acontecendo atrás de mim, não na minha frente como antes, em algum sentido. Agora, como um lado, e como você pode ter visto on-line se você começar a bisbilhotar sobre tipos, há tantos diferentes lá fora, alguns deles melhor do que os outros. De facto, é uma bogosort esse é o tipo de diversão para olhar para cima. Bogosort leva um conjunto de números ou dizer um baralho de cartas, embaralha-los aleatoriamente, e verifica se eles estão ordenados. E se não, faz isso de novo. E se não, faz isso de novo. Se não, faz isso de novo. Incrivelmente estúpido. E, de fato, se você ler como o artigo da Wikipedia, seu apelido é meio estúpido. Será eventualmente trabalhar, espero que, com o tempo, mas que a quantidade de tempo pode levar algum tempo. Então, se eu pudesse, vamos acelerar as coisas -se com o exemplo de Mary Beth anteriormente, por ter mais alguns elementos, mas mais dois processadores. Duas pessoas, se você não me importaria de me juntar. Como cerca de 1 por aqui, e vamos vai-- ninguém ali? Ninguém ali? Está bem. Você com o preto camisa, sim, vamos lá para baixo. Tudo bem, qual é o seu nome? AUDIÊNCIA: Peter. Palestrante: O que é isso? AUDIÊNCIA: Peter. Palestrante: Peter, David, prazer em conhecê-lo. Tudo bem, temos Peter aqui, se você quer vir para a mesa por aqui. E qual o seu nome? AUDIÊNCIA: Elena. Palestrante: Elena. OK, prazer em conhecê-lo. Elena atender Peter. Peter, Elena. E precisamos de Andrew aqui também, por favor. E o desafio vai ser para ordenar um baralho de cartas. E se não familiar, deck de cartões deve finalmente ser classificado um pouco algo como este, onde vamos fazer os clubes, em seguida, as espadas, em seguida, os corações e diamantes, de ace como um, todo o caminho até ao rei. As cartas que eu estou indo dar-lhe vão ser 52 em quantidade. Vamos semelhante vez que, em apenas um momento. Vamos jogar Andrew na tela aqui, , de modo a ver como você faz isso. E de modo a que tudo isso é ainda mais visível, Estes são os cartões que recebi na Amazônia. Então, eles já estão aleatoriamente classificado, e nós estamos indo para o tempo que você. E nós vamos mantê-lo real desta vez, então vamos tentar pressioná-lo porque caso contrário isso vai ser entediante rapidamente. Se você pudesse proceder para classificar 52 elementos entre si através de alguns meios, agora. E mais uma vez, como vemos estes caras fazem o que, no final vai produzir um óbvio resultado, pense realmente como eles estão fazendo isso cada, como você pode descrevê-lo. Porque mais uma vez, estas são todos os processos, algoritmos que nós tomamos para concedido como um ser humano. Mas você já deve ter tido por muito tempo intuição, muito antes de você mesmo pensou em tomar um ciência da computação classe você poderia ter tido a intuição com que para resolver problemas como este. Mas uma vez que você reconhece os padrões e começar para formalizar as medidas com as quais você está resolvendo esses problemas, você vai descobrir que você pode resolver muito mais interessante e muito mais complexo problemas rapidamente. Então, alguém da platéia, o que é pelo menos um elemento do algoritmo que eles estão usando aqui? AUDIÊNCIA: [inaudível] Palestrante: O que é isso? AUDIÊNCIA: por exemplo. Palestrante: por exemplo. Então, primeiro eles se aglomeram todos os diamantes juntos Parece que todos os corações juntos que parece, e assim por diante, sem respeito para os números sobre os cartões. E agora eles aparecem, por exemplo, a ser os por número. Muito bom. Tudo bem, então o que vai ser o passo final, então aqui? Uma vez que temos quatro naipes classificadas, o que fazer o que precisamos fazer para as quatro pilhas , a fim de alcançar um classificadas convés, pura e simplesmente? Então, precisamos mesclá-los novamente. Portanto, há uma idéia interessante que novamente, ouso dizer, é muito intuitivo mesmo se você nunca poderia ter esbofeteado esse tipo de rótulo nele. Esta noção fundamental de divisão o problema não em metade deste tempo, mas, pelo menos, em quatro pedaços. Resolvendo praticamente problemas fundamentalmente idênticos isoladamente uns dos outros, e então fundir os resultados. E, excelente, feito. Tudo bem, uma grande rodada de aplausos, se pudéssemos. [Aplausos] Palestrante: Eu não tenho idéia o que você vai ver com isso, mas aqui vai. Muito obrigado. Então vamos ver, dois minutos e oito segundos; se você gostaria de desafiar os seus amigos. O que então vai ser um tirar este que podemos aproveitar de forma mais geral? Bem, acho que volta para esse conjunto de números, e acho que volta agora a alguns dos pseudocódigo nós escrevemos no passado, e este foi o pseudocódigo para resolver o problema da lista telefônica. Nestas circunstâncias, em pseudocódigo I enumerou uma maneira mais metódica de descrever como eu fiz um muito intuitivo algoritmo humano de dividir o telefone livro pela metade, repetir, repetir, repetir, até eu encontrar alguém como Mike Smith, se ele é de fato no livro de telefone. Mas eu meio que usei o que eu vou chamar uma abordagem muito iterativo aqui, em particular aviso linha 8 e linha 11. Essas são evidências de uma iterativo abordagem, uma abordagem looping, porque é exatamente o comportamento que eles induzem. Essas linhas tanto dizer ir para linha de três, e você pode tipo de pensar que, em sua olho da mente como sendo um loop. Ele está dizendo a você para voltar-se para a etapa três e repetir, de novo, e de novo, e novamente. Mas o que se aproveitar uma idéia-chave aqui que nós não pela última vez, e simplificar a linha 8 e linha 11 e seus vizinhos como apenas isso, em amarelo. Não é, fundamentalmente, encurtando pseudocódigo muito, mas está mudando fundamentalmente a natureza do meu algoritmo. O que eu estou dizendo agora no passo 7, na etapa 10, é a busca de Mike da mesma forma exata, mas apenas no lado esquerdo metade ou metade direita. Assim, em outras palavras, se Eu começar a partir de uma etapa, pegar livro de telefone, aberto a meio do livro de telefone, olhar para os nomes, Se Smith está entre O nome de, chamar Mike, o mais Se Smith é anterior no livro, passo sete procurar Mike na metade esquerda do livro. Mas esse tipo de sente como isso está me deixando pendurado, certo? Em amarelo, é uma instrução, mas como faço procurar o Mike no esquerdo metade do livro de telefone? Onde é que eu tenho uma algoritmo com o qual eu pode procurar por alguém como Mike Smith? Bem, isso está nos olhando na cara. Eu posso literalmente usar exatamente o mesmo programa vai efetivamente até o topo novamente e re-execução as mesmas linhas de código. Assim, mesmo que este deve sentir-se como um pouco de uma definição cíclico onde você está respondendo a alguém é Pergunta por apenas uma espécie de perguntar a mesma pergunta novamente, como por que, por que, por quê? A realidade é porque temos codificado um par de linhas especiais, escalão 4, que é um caso, e passo 12, que é efetivamente um outro ramo, porque temos essas medidas paliativas, este algoritmo irá terminar se encontrar Mike, ou se não o fizermos. Mas na etapa 7 e 10 agora, temos o que vamos chamar de um algoritmo recursivo. E recursão é de fato uma idéia poderosa isso é um pouco de mente dobra no início, que agora podemos aplicar a seguinte. Merge sort será o último tipo que olharmos para, pelo menos na classe formalmente. E é fundamentalmente diferente daqueles três últimos, e, certamente, quatro últimos se incluem bogosort. Aqui está o pseudocódigo para merge sort. Quando a entrada de n elementos, então dado uma matriz de tamanho n, se n é inferior a 2, voltar. Então, por que eu tenho que verificação de sanidade em primeiro lugar? Qual é a implicação se eu entregar-lhe uma matriz cujo comprimento n seja inferior a 2? Ele já está classificado, obviamente, não é? Como a lista tem tanto um elemento, o que é trivial classificadas porque é a única coisa que existe. Ou, é de tamanho zero, o que significa não há nada para resolver, por isso, natureza ele é classificado. Apenas há nada de errado lá. Então, esse é o nosso chamado caso base. Isto é semelhante em espírito ao que fizemos com Mike. Se Mike no livro de telefone, ligue para ele. Se ele não estiver lá, desista. É um chamado processo de base, para se certificar este algoritmo, no final do dia vai parar em determinadas circunstâncias. Mas aqui está o salto de fé agora, mais, ordenar a metade esquerda dos elementos, em seguida, classificar o direito metade dos elementos, e em seguida, mesclar as metades classificados. E aqui é onde ele se sente como estamos amarelando. Pedi-lhe para classificar n elementos, e eu sou dizendo: OK, faça isso por classificação a esquerda e para a triagem da direita. Mas eu estou dizendo uma outra coisa, e esta é o tema central parece na intuição, até agora, há esta terceira etapa de fusão. Que embora Parece tão burro em espírito, como apenas mesclar coisas juntos, parece ser um passo fundamental para o remontagem de dois problemas que foram divididos em última instância, pela metade. Então, merge sort, vamos fazer isso, se você humor me, com mais uma demonstração, apenas para que tenhamos alguma números de trabalhar. Posso trocar oito estresse bolas para oito pessoas? Tudo bem, que tal vocês três, vocês quatro nesta seção, cinco, seis, e vamos não 7, 8, vamos para cima. OK, sim OK. Minus 8, lá vamos nós, mais 1. Excelente. Todos vêm a direita em cima, vamos rapidamente lhe dar números. O número dois, número três, número quatro, número cinco, seis, sete, e oito. Eu fiz oito corretamente desta vez. OK, então vá em frente se você pudesse, e vamos classificar na ordem original que tivemos ontem que parecia assim, se você não se importar. E vamos fazê-lo na frente da tabela. Tudo bem, então merge sort. Este é o lugar onde ele vai para chegar bem interessante, porque parece que estou me dando muito menos informação hoje. Assim fundir tipo em primeiro lugar na entrada de n elementos, e é, obviamente, não inferior a dois, é oito, então eu tenho um pouco mais de trabalho para fazer. Então, agora nós mentalmente como uma classe estão agora na outra filial, o que significa que três passos. Primeiro, tenho de resolver o metade esquerda dos elementos. Então como é que eu vou fazer isso? Bem, eu estou indo para o tipo de dividir mentalmente a lista aqui, você não tem que mover fisicamente, e estou vai centrar-se apenas na metade esquerda dos elementos aqui. Então, como eu faço para classificar uma lista agora do tamanho de quatro? Qual é o meu algoritmo? Primeiro eu verifico é n inferior a dois, não, para que eu prossiga para o bloco mais novo. Ordenar deixou metade de elementos. Portanto, agora de novo, mentalmente, e é aí que você tem que acumular um monte de história mental, se você quiser. Agora estou classificando a esquerda a metade do lado esquerdo. Tudo bem, então agora eu chamo o meu mesmo merge algoritmo de classificação, é n inferior a dois? Não, é dois, então eu tenho que classificar a metade da esquerda, e a metade direita. Então, vamos lá, ordenar a metade esquerda. Por que você não apenas dar um passo a frente. Qual o seu nome? AUDIÊNCIA: Darren. Palestrante: Dan. Dan deu um passo a frente. AUDIÊNCIA: Darren. Palestrante: Darren, feito. Você disse Darren ou Dan? AUDIÊNCIA: Darren. Palestrante: Darren. OK, Darren tem intensificado a frente e que é agora classificada. E isso é quase uma reivindicação inane, certo? Eu realmente não parece estar a atingir nada, mas vamos continuar. Agora deixe-me ordenar a direita metade dos elementos. Qual o seu nome? AUDIÊNCIA: Lucas. Palestrante: Lucas. Vamos lá, um passo à frente. Feito, eu classifiquei Lucas. A metade esquerda é agora classificado e a metade da direita é agora classificada, mas, novamente, há um passo-chave aqui. O que eu preciso fazer no próximo? Unir as metades classificados. Agora vamos ter apenas todos trás e para a frente desta maneira, porque eu meio que preciso algum espaço de rascunho. É quase como se estes caras estão sobre uma mesa, e eu preciso de algum espaço para movê-los em. Então eu vou para mesclar vocês olhando na metade esquerda e o da metade direita. E que, obviamente, vem em primeiro lugar, metade esquerda ou metade direita? Então metade direita, então vamos mover Lucas sobre aqui a posição original de Darren. E agora fundir a sua metade esquerda em, Darren vai mover para a direita lá. Então, parece que quase um efeito bubble sort, mas o meu algoritmo fundamental muito diferente desta vez. Mas agora é onde as coisas ficam um pouco chato, porque você tem que rebobinar mentalmente onde foi que eu parei. Acabei fundiu as metades ordenadas, o que significa que eu estou onde no meu algoritmo? Eu tenho que classificar a metade direita, certo? Se você voltar, literalmente no vídeo, você vai ver que chegamos a este ponto de Luke e Darren classificando a esquerda a metade do lado esquerdo. Em seguida, fundiu os metades ordenadas, que significa que o próximo passo é o tipo metade direita da metade esquerda. Tudo bem, então vamos fazer isso mais rapidamente. Tudo bem, seis, eu vou reclamar você está agora resolvido, vamos para a frente. Qual o seu nome? AUDIÊNCIA: Adriano. Palestrante: Adriano. Adriano está agora classificada. E qual o seu nome? AUDIÊNCIA: Alex. Palestrante: Alex está agora classificada. Meia esquerda, meia direita, qual é o passo final? Mesclar. Muito trivial, por isso estou vai fundir em seis, dar um passo atrás, oito, dar um passo atrás. E agora perceber isso é um takeaway útil, o que é agora verdade sobre a metade esquerda da lista, independentemente da forma como começamos? Ele está classificada. Agora ele não está classificada em o grande esquema das coisas, mas ela é ordenada independentemente da outra metade. Agora, o que passo sou eu em se manter rebobinar como a história começou? Agora eu tenho que classificar a metade direita. Portanto, agora estamos no caminho de volta o começo da história, e vamos fazer isso mais rapidamente. Então eu vou para classificar a metade direita da lista inteira. Qual é o próximo passo? Ordena a metade esquerda da metade direita. Ordena a metade esquerda da a metade esquerda da metade direita. E qual o seu nome? AUDIÊNCIA: Omar. Palestrante: Omar, um passo à frente, feito. Metade esquerda está classificada. E qual o seu nome? AUDIÊNCIA: Chris. Palestrante: Chris, dar um passo para a frente, você está agora classificada. Qual é a chave passo agora? Mesclar. Então, um vai se fundir em lugar aqui, se você pudesse dar um passo para trás, e três vai dar um passo atrás, se fundem. Assim, a metade esquerda da metade direita, agora está resolvido. Francamente, este algoritmo se sente como nós estão gastando muito mais tempo do que antes, mas se não fez isso em tempo real, vamos ver o que os delivery vai ser. Agora estou aqui, certo a metade do lado direito, deixe-me ir em frente e resolver a metade esquerda. Passo em frente, o que é o seu nome? AUDIÊNCIA: Ramsey. Palestrante: Ramsey está agora classificada. Qual o seu nome? AUDIÊNCIA: Marina. Palestrante: Marina está agora classificada como Bem, se você der um passo para a frente. Chave passo aqui agora é fundir, eu sou vai arrancar das minhas duas listas, esquerda e direita. Cinco vai vir em primeiro lugar, e sete vai vir em seguida. E, novamente, isso é proposital. O fato de que eles estão levando passos para a frente e para trás é utilizado para representar que não podemos fazer esse algoritmo no lugar com a mesma facilidade como bubble sort, e seleção de tipo, e inserção tipo em que apenas manteve trocando pessoas. Eu literalmente precisa de um tipo de papel de rascunho em que para colocar essas pessoas enquanto eu faço a fusão, e então eu posso colocá-los de volta no lugar. E isso é fundamental, porque eu estou usando um novo recurso, o espaço, não apenas tempo. OK, isso é incrível. Metade esquerda é classificado, a metade direita é , agora que a chave fusão etapa de classificação. Como é que eu vou mesclar essa? Então, se você seguir o meu mão esquerda e mão direita, Eu vou apontar a minha mão esquerda na metade esquerda, a mão direita na metade direita, e agora eu tenho que decidir passo a passo quem se fundir em. Que, obviamente, vem em primeiro lugar? Número um. Então venha para cá, aqui está o nosso bloco de rascunho. Então, agora o número um, e aviso o que vou fazer com a minha mão direita, Vou passar a minha mão direita passar por cima ao ponto número três, e agora eu tenho que fazer a mesma decisão. E, na verdade, ficar bem na frente de Luke aqui se você pudesse, porque este é o nosso bloco de rascunho. Então, quem vem a seguir? Temos Luke com o número dois ou Chris com o número três. Obviamente Luke, número dois, para que você venha aqui. Mas minha mão esquerda agora vai ser incrementado para apontar para Darren, e aqui está a chave tirar com fusão, eu vou continuar fazendo isso, Obviamente, se você tipo de seguir a lógica. Mas minhas mãos nunca são indo para ir para trás, o que significa que eu estou sempre apenas movendo-se para esquerda com o meu processo de fusão, e que vai ser a chave para nossa análise em apenas um momento. Então agora vamos terminar isso rapidamente. Então, três vem a seguir, depois quatro vem a seguir, e agora vem a seguir cinco, depois seis, e sete, e, finalmente, oito. Parece que o algoritmo mais lento ainda, mas não se realmente executá-lo, ao mesmo tipo de velocidade de clock, por assim dizer, com a mesma tique-taque do relógio como antes. Por quê? Bem, Vamos dar uma olhar para o resultado final. Vamos voltar aqui, deixe-me puxe uma demonstração visual do que acabamos de fazer. Aproximar-se aqui, neste página aqui, dizendo Firefox que queremos fila até neste campo, vamos dizer bubble sort, com o qual agora estamos bem familiarizados, tipo de selecção, que é outra bastante um simples, e agora merge sort de hoje, que será o nosso clímax final. A razão que levou muito mais tempo aqui com os seres humanos e me verbalmente é, obviamente, eu estou explicando cada passo. Mas se você simplesmente executar este, muito como fizemos bubble sort e seleção tipo, não só visualmente, relógio o quanto de forma mais eficiente essa alavancagem de divisão e conquista pode ser, quando aplicado a um conjunto de dados que é nem mesmo tamanho oito, mas mesmo muito, muito maior. Eu dou-lhe merge sort, lado a lado com estes outros algoritmos. Isso vai ficar doloroso rapidamente, eo final não é particularmente climático, eles simplesmente acabar ordenados. Mas a chave tirar é que Veja o quanto mais rápido merge sort era, a menos que você acha que eu sou apenas uma espécie de mexer com você. Se fizermos isso uma última vez, Vamos recarregar isso, vamos voltar e escolha bubble sort, e apenas por diversão, Vamos escolher a inserção tipo, apenas para uma boa medida. E desta vez, mais uma vez, vamos escolher merge sort e vamos realmente executar estes lado a lado. E não é, na verdade, um golpe de sorte. O que eu fiz de forma eficaz é que eu tenho repartiram a minha entrada no meio, mais uma vez, e de novo, e de novo. E há apenas tantas vezes você pode dividir sua entrada em metades, esquerda e à direita. Qual é a fórmula que continuo vendo que descreve a divisão em metade de novo, e de novo, e de novo, e de novo? AUDIÊNCIA: Log n. Palestrante: Log n. Mas depois há um outro grande passo, este algoritmo não é log n passos. Se só foram log n passos, estaríamos no mesmo problema como antes, onde não podemos ser Certifique-se que está tudo resolvido. Você tem que olhar minimamente n elementos para ter certeza de n elementos são ordenados, caso contrário, é um salto de fé. Então é log minimamente n passos, mas o que acontece com este passo chave fusão onde eu fundiu minha metade esquerda e direita meio e atravessou o palco? Quantos passos é que se fundir? É n, mas não o fiz apenas mesclar o tempo final. Em cada uma dessas chamadas aninhadas, em cada dessas fusões aninhados, eu ainda classificadas. Eu fundiu esses dois caras, então estes dois caras, então esses dois caras e assim por diante. Então eu fiz a fusão de novo, e de novo. Quantas vezes? Então toda vez que eu dividia o lista pela metade, eu fiz uma mesclagem. Divida a lista ao meio, fazer uma mesclagem. Portanto, se a divisão a lista pode ser feito de log n vezes, e em última análise, a fusão tem n etapas, o que pode ser agora o superior encadernado pela execução tempo do nosso algoritmo? n log n. E, de fato, é o que nós conseguimos aqui. Então, a sensação que você vê quando visualmente essas três coisas correm lado a lado n é quadrado contra n quadrado contra o registro n n. Que fundamentalmente nós vamos ver, Não só, mas hoje em dia, no futuro, é muito mais rápido. Uma salva de palmas para esses caras, Eu vou recompensá-los com bolas de stress. Vamos encerrar aqui hoje, e vamos vê-lo na segunda-feira.