[Música tocando] David J. MALAN: Este é CS50. E este é o início da semana três. Então, nós temos um monte de emocionante coisas para cobrir hoje. Um monte de oportunidades para voluntários em cima do palco. E, finalmente, é hoje não sobre o código em tudo. Mas é sobre ideias e trata-se de algoritmos, e, na verdade, trazendo de volta alguns dos as lições aprendidas a partir da semana zero, onde recall, nós introduziu esta monstruosidade. E empréstimos inspiração desde que, para iniciar para resolver cada vez mais sofisticados problemas através de algoritmos. Mas, primeiro, um par de anúncios. Então um, se você gostaria de se juntar Funcionários e colegas de CS50 no almoço nesta sexta-feira, tanto aqui como no Cambridge, e em New Haven, visite por favor o curso de site, em que um URL pode ser encontrado. Palestra esta quarta-feira não estar aqui em Sanders. Vai ser on-line, de modo sintonizar no site da CS50, se aqui em Cambridge ou New Haven também. E, em seguida, ajustou dois problema já está em suas mãos. Se você ainda não mergulhou ainda, permita-me para oferecer a sugestão de palavras fortes que, especialmente agora, como o problema define antecipadamente, você realmente quer começar agora, se não borrifar um pouco no fim de semana ou antes quando pela primeira vez sair em Sextas-feiras, porque você vai descobrir que eles não são necessariamente ficando mais longos ou mais desafiador por SE. Eu acho que você vai descobrir que, em geral, eles tendem a levar mais ou menos em torno mesma quantidade de tempo. Mas é certamente depende no aluno, e depende da mentalidade com o qual você se aproxima dele. Mas, invariavelmente, você está indo para executar-se contra alguma parede, e você está indo bater algum bug, e você é apenas não vai ser capaz de superar isso em algum momento. E é muito valiosa para ser capaz se afastar, voltar no dia seguinte, ir para o horário de expediente, no pós CS50 Discutir ou similar, para começar realmente desbloqueado. Portanto, manter isso em mente. Começando mais cedo possível é a melhor coisa que você pode fazer. Então, aqui é onde nós começamos a classe, mais na semana zero. E podemos obter um voluntário aqui para me ajudar a encontrar microfones? ESTÁ BEM. Levantando-se já. Vamos lá para cima. Acho que é como ele vai funcionar. Qual o seu nome? ALAN ESTRADA: Alan Estrada. DAVID J. MALAN: Alan Estrada. Vamos lá para cima. Bom te conhecer. ALAN ESTRADA: Prazer em conhecê-lo. DAVID J. MALAN: E você estava aqui com a gente na semana zero, é claro. ALAN ESTRADA: eu era. Eu era. DAVID J. MALAN: Então você poderia ir em frente e encontrar para nós Mike Smith, tão rápido quanto você pode? Tão rápido quanto você puder. Literalmente rasgando o problema em metade do que você precisa. ALAN ESTRADA: Hum. DAVID J. MALAN: Literalmente rasgando o problema pela metade. ALAN ESTRADA: Oh. Mm. Muito bem. DAVID J. MALAN: OK. Boa. Obrigado. ALAN ESTRADA: Muito bom. ESTÁ BEM. DAVID J. MALAN: E agora, você whittled para baixo a metade do tamanho do problema. Agora, estamos reduzidos a um quarto. Você está pagando a atenção para de que lado estamos mantendo? [RINDO] ALAN ESTRADA: Sim, eu penso-- DAVID J. MALAN: Qual seção estamos? ALAN ESTRADA: Silenciosos, então. DAVID J. MALAN: OK. Mas Mike Smith vai para ser depois Silenciosos. Assim-- [RINDO] Tudo certo. ALAN ESTRADA: Onde estamos procurando? DAVID J. MALAN: Mike Smith. ALAN ESTRADA: Mike Smith. DAVID J. MALAN: Agora, estamos em cirúrgico. Agora, os médicos. Agora-- ALAN ESTRADA: Let's- vamos com real. Real. DAVID J. MALAN: Real. ESTÁ BEM. Se você precisar de Real. Agora, o caminho que é Mike Smith? ALAN ESTRADA: Desta forma. DAVID J. MALAN: Que maneira? ALAN ESTRADA: Espere. M é-- certo? Começamos com-- DAVID J. MALAN: Yeah. Eles são deixados. Seu direito. ALAN ESTRADA: Yeah. DAVID J. MALAN: Então Mike está aqui. ALAN ESTRADA: O quê? [RINDO] Mau exemplo, rapazes. Desculpe. DAVID J. MALAN: Isto vai ensinar você pular para fora de sua cadeira. ALAN ESTRADA: Oh. Oh. Entendi. Entendi. Oh. Oh. Isso é-- OK, eu tenho você. Smith aqui? DAVID J. MALAN: Smith, obrigado. Portanto, vou continuar olhando para cima Smith? ALAN ESTRADA: Ah, sim. Não não não. Ah não. Isto é meu. DAVID J. MALAN: Oh, você tem Smith. ESTÁ BEM. ALAN ESTRADA: Sim, eu Smith tem aqui. Desculpe, rapazes. Eu pensei que nós Michael-- Michael estava procurando. Desculpe. DAVID J. MALAN: É OK. Tudo bem, agora estamos em Paccini e Sons. ALAN ESTRADA: Paccini e filhos. DAVID J. MALAN: Só você e eu estamos em sobre este assunto. ESTÁ BEM. Encontre-nos Mike Smith. Smith. ALAN ESTRADA: Smith. DAVID J. MALAN: Smith. Estamos em R para lixo. ALAN ESTRADA: Péssima. Oh. Isso vai demorar um pouco. [RINDO] DAVID J. MALAN: Shoes. Estamos em sapatos. ALAN ESTRADA: Agora estamos gonna-- DAVID J. MALAN: Nice. ALAN ESTRADA: Which-- [RINDO] Oh, isso é ótimo. [RINDO] DAVID J. MALAN: É OK. ALAN ESTRADA: Oh, isso é bom. Eu não acho que eu vou ter amigos PSAT após este. DAVID J. MALAN: Good. Sporting. ALAN ESTRADA: Sporting. Hum, L, M, N, O, P. DAVID J. MALAN: OK. Então, vamos destruir o ao meio. Está certo. Isso acaba mal de qualquer maneira, porque Mike Smith não será nas páginas amarelas. ALAN ESTRADA: Aw. DAVID J. MALAN: Não, é OK. Mas vamos fingir que ele está nesta página. Então, agora, você talhou o problema para baixo a uma página, e encontramos Mike Smith. [CHEERING] Tudo bem, obrigado. ESTÁ BEM. Isso foi extraordinário. Mas ainda era mais rápido que busca linear, em que nós começamos no início do livro, e passamos o nosso caminho da esquerda para a direita, eventualmente, à procura de Mike Smith. E assim, se o livro de telefone tinha talvez 1.000 páginas, talvez teria levado nos 10 ou mais lágrimas página. Mas você pode ter alavancado tocou uma suposição durante toda a isso, o que é dizer que o livro de telefone com antecedência o que era? AUDIÊNCIA: Ordenado. DAVID J. MALAN: É classificada. Certo? É classificados em ordem alfabética, por isso, que todos esses nomes e números são classificadas a partir da de um para o Z de, e em ordem alfabética no meio. Mas hoje, nós agora pedir a questão, bem, como fez Verizon ou o telefone empresa obtê-lo naquele estado? Porque é uma coisa para alavancar essa suposição, e, portanto, resolver um problema com um algoritmo de forma mais eficiente. Mas nós nunca realmente pediu na semana zero, bem, quanto isso custou Verizon ou outra pessoa para obter essa lista telefônica na ordem de classificação? Certo? Não importa se olhando para cima Mike Smith é super rápido, se você leva um ano para classificar as páginas inicialmente. Certo? Você pode muito bem peneirar através de um livro de telefone ao acaso, se ele vai ser super caro para classificá-lo. Então, se nós podemos ter outro voluntário. Vamos dar uma olhada aqui em cima como nós might-- venha up-- como poderíamos ir sobre a classificação destes. E se, na verdade, poderia Jordan se juntar a nós aqui em cima no palco. Venha-se apenas por um momento. Qual o seu nome? CAROLINE: Caroline. DAVID J. MALAN: Caroline, vamos lá para cima. E você vai ser se juntou por mim e Jordão aqui. Caroline, obrigado. Tudo certo. Então o que temos aqui para Caroline tem 26 livros azuis FAS que utiliza para administrar certos exames finais. Estes estão ficando difíceis de encontrar, mas o que temos feito com antecedência é que nós colocamos o nome de alguém na parte da frente de cada uma delas, mas mantivemos-lo simples, em seguida, colocar para fora os nomes completos. Por isso, seria colocar a pessoa com o nome G, D, J, B, todo o caminho de A a Z, mas eles estão em ordem aleatória. E por isso, se você faria, falando seu caminho através do problema como você fazê-lo, você pode ir em frente e classificar estes para nós, de A a Z. AUDIÊNCIA: OK, então L é como, no meio. C está começando. B. J antes L. B, Q. DAVID J. MALAN: Mantenha essa pensou por um segundo. Porque de outra forma, esta é apenas interessante para você, eu, e Jordan. Aí vamos nós. AUDIÊNCIA: [inaudível]. R. DAVID J. MALAN: OK. O que você está fazendo? CAROLINE: M vem depois O. DAVID J. MALAN: OK. CAROLINE: O. DAVID J. MALAN: O, Bom. CAROLINE: E. DAVID J. MALAN: E, F. Sim. CAROLINE: T, U, V DAVID J. MALAN: V, T, U, V. Portanto, parece que você está making-- continuar. Parece que você está fazendo uma grande pilha aqui, e tipo de uma grande pilha de lá. Assim, a primeira metade do alfabeto, segunda metade do alfabeto. ESTÁ BEM. Boa. Tipo de dividir o problema em duas partes. M, N, X. Sim. CAROLINE: K. DAVID J. MALAN: OK. K. Então você está tipo de seleção -los um após o outro, colocá-lo para a esquerda ou direita, ou Z está acontecendo no chão. ESTÁ BEM. CAROLINE: Z está acontecendo no chão. DAVID J. MALAN: OK. Y está acontecendo no chão. Agora podemos colocar X. CAROLINE: G. DAVID J. MALAN: G de ir à esquerda. S está indo bem. Tudo bem, um está indo todo o caminho à esquerda. Caroline: A, B, C, D. DAVID J. MALAN: Agora, é bom. Temos A, B, C. W de ir lá em baixo. Tudo bem, T. CAROLINE: H, I, J. DAVID J. MALAN: H, I, J. Boa. CAROLINE: No centro, eu estou gonna-- DAVID J. MALAN: OK. Então, agora, vamos tipo de mesclar essas várias pilhas. Então, de A a C, então eu vejo D, e E, e F, e G, e H, I e agradável. J, K. E então, essa pilha é de cabeça para baixo, mas isso é OK. Certo. Podemos cortar alguns cantos. ESTÁ BEM. E então nós precisamos W, X, Y, Z. CAROLINE: Yeah. DAVID J. MALAN: Excelente. Assim, um grande obrigado a Caroline para classificar estes. [CHEERING] Obrigado. Muito obrigado. Então agora vamos considerar por um momento como Caroline passou fazendo o que, e exatamente o que nós foram capazes a-- como nós foram capazes de resolver esse problema quando estávamos apenas dado um monte de entradas aleatórias. Bem, parece que há foi um pouco de um sistema de lá? Certo. Assim, as primeiras cartas no alfabeto, ela era colocar à esquerda, eo cartas posteriores no alfabeto, ela estava colocando para a direita. E assim que ela encontrou algumas cartas proximais, queridos que vá para a direita ao lado do outro, ela iria colocá-los em ordem. E então nós meio que tinha estes pequenos pilhas de entradas ordenadas ocorrendo. E assim que é bastante parecido com o que a maioria de nós seres humanos faria. Gostaríamos espécie de peneirar, e nós meio que temos um mecanismo. Mas pode ser difícil de escrever -o para baixo em uma fórmula de per si. Ele Senti um pouco mais orgânico do que isso. Então, vamos ver se podemos agora ligado O problema com o menor número de entradas. Em vez de 26, vamos fazer algo muito menos com apenas dizer, sete, atrás estas portas, por assim dizer. Há apenas sete números? E se o objetivo agora em mão é encontrar um valor, vamos ver o quão eficiente nós podemos fazer sobre este assunto. E vamos ver se podemos agora começar a aplicar alguns números, ou algumas fórmulas com as quais para descrever a eficiência do nosso livro de telefone algoritmo, nosso algoritmo livro exame, e de modo mais geral, busca de informações. Então, para isso, deixe-me ir em frente, e na tela de toque aqui, colocar um navegador web que tem exatamente esses sete portas. E se nós pudéssemos adquirir um outro voluntariar para vir até aqui, Eu coloquei essas mesmas portas por aqui. Voluntário rápido. Este um-- demos vão a uma mais rápida e mais rápido agora. Vamos lá para baixo. Qual o seu nome? TREVOR: Trevor. DAVID J. MALAN: Trevor? Tudo bem, Trevor, vamos lá para baixo. Então Trevor se ofereceu aqui para fazer um problema semelhante, mas um que é de âmbito mais restrito, e que está acontecendo para permitir-nos para tentar formalizar agora o processo de triagem de esses números. Então Trevor, prazer em conhecê-lo. Então aqui é uma matriz, por assim falar, uma lista de sete portas. Vá em frente e encontrar-nos no número 50. E, em seguida, após o fato, diga-nos como você o encontrou. Deve ser-- tudo bem. Sim, este é o único aqui? Uh oh. ESTÁ BEM. Você clicou essa. Boa. E bom. Agora você clicou essa. E deixe-me dar-lhe o microfone, de modo que você tê-lo em apenas um momento. Vá em frente e clique no ao lado que você pretende. Sim bom. TREVOR: Posso desmarque a porta? DAVID J. MALAN: Não, você não pode desmarque. TREVOR: OK. Este. DAVID J. MALAN: Onde você quer ir? Qual? TREVOR: Que um. DAVID J. MALAN: Não. TREVOR: OK. Este. DAVID J. MALAN: Sim. Isso foi bom. Tudo certo. Então, qual foi o seu algoritmo ou procedimento para fazer isso, Trevor? TREVOR: Eu só passei portas até que eu encontrei a 50. DAVID J. MALAN: OK. Excelente algoritmo. Então, isso é bom. Porque, na verdade, se eu revelar o que é por trás dessas duas outras portas, o que vamos encontrar aqui é que só temos entrada aleatória. Então isso foi realmente como bem como se poderia obter. E, na verdade, você tem melhor do que exaustivamente buscando todo o conjunto, porque ele teria sido realmente azarado se tivesse atingido o número 50 no último porta. Mas o que se em vez deu-lhe uma hipótese. Suponha que eu classifico todos estas portas ao redor, de modo que você tem a números classificados este tempo, mas desta vez é realmente um diferente-- este tempo, ele é realmente classificadas para você. E agora a meta na mão é atingir o número de 50. TREVOR: OK. DAVID J. MALAN: Qual é seu algoritmo vai ser? TREVOR: Bem, se é classificadas, é qualquer um que vai para ser-- se maior para o maior, descendente, vai ser o primeiro, ou se é o contrário, será a última. Então só vou tocar esta porta, e em seguida, basta tocar a última porta. DAVID J. MALAN: Excelente. Tudo certo. Assim, encontramos o número 50. Assim, logo que você soubesse eles foram ordenados, nós foram capazes de aproveitar essa suposição. Então, eles estão muito parecido a exemplo do livro de telefone. Assim que você tem, mesmo com um pequeno problema como este, suas entradas pré-classificados, nós podemos realmente encontrar o valor indiscutivelmente mais eficientemente. E eu não lhe disse se era classificadas pequeno a grande, ou grande a pequeno, e por isso era muito razoável para começar em uma extremidade ou outro para realmente encontrar esse valor-alvo. Por isso, agradeço ao Trevor também. E eu vou propose-- bem feito. Temos um pequeno clip, na verdade, que está entre os nossos momentos favoritos em CS50, pelo que, por vezes, estas demonstrações não chegam a ir de acordo com o plano. E, de fato agora, eu puxou a interface errada com que usar a tela sensível ao toque. Então isso foi culpa minha lá. Então, isso vai fazer para clipe do próximo ano como a razão pela qual eu estava clicando no meu próprio ecrã. Mas vamos dar uma olhada rápida para o que aconteceu no ano passado com Jay, que surgiu, muito como Trevor aqui, ofereceu-se, e neste clipe curto, você verá como esta mesma demonstração não fez muito revelar as mesmas lições aprendidas. [REPRODUÇÃO DE VÍDEO] -Tudo Que eu quero que você faça agora é para encontrar para mim, e para nós, realmente, o número 50 um passo de cada vez. -O Número 50? -O Número 50. E você pode revelar o que é por trás de cada uma destas portas simplesmente por tocar com um dedo. Caramba. [RINDO] [FIM DE REPRODUÇÃO] DAVID J. MALAN: Assim que correu muito bem. Essas foram as portas não triados. E Jay, é claro, achei tudo muito rapidamente. Trevor fez um trabalho muito melhor em termos de um momento de aprendizado, por assim dizer, este ano, em levando mais tempo para encontrá-lo. É claro, então nós demos Jay uma segunda chance, pelo qual nós ordenamos as portas, assim como fizemos para o Trevor, e Trevor fez super-bem desta vez. Mas Jay fez metade tão rapidamente. [REPRODUÇÃO DE VÍDEO] -O Objetivo agora é também encontrar-nos no número 50, mas fazê-lo através de algoritmos, e diga-nos como você está indo sobre ele. -ESTÁ BEM. -E Se você encontrá-lo, mantenha o filme. Se você não encontrá-lo, você dá-lo de volta. -Cara. -Oh! - [Inaudível] OK. Então, eu estou indo para verificar as extremidades primeiro para determinar se there's-- Oh. [Aplausos] [FIM DE REPRODUÇÃO] DAVID J. MALAN: OK. Então triagem portas claramente conduz a uma maior eficiência. E assim, duas vezes mais rápido é o que eu quis dizer lá. E assim Jay teve sorte duas vezes. E ele também teve sorte naquela última ano, eu pedi alguns discos Blu-ray para realmente dar para fora. Sinto muito este ano, não têm o mesmo, Trevor. Mas melhor ainda era alguns anos atrás. E alguns de vocês podem saber isso companheiro, Sean, que quando ele estava na CS50, foi desafiado com a exata mesmo problema, embora em SD, como você verá em breve, de volta ao dia. E você vai descobrir que não só ele demorar um pouco mais do que Jay, um pouco mais do que Trevor, foi realmente esta oportunidade maravilhosa se envolver quase todos no multidão a la Preço Certo, incentivando -lo a encontrar o número que estávamos procurando. Vamos. dar uma olhada rápida. [REPRODUÇÃO DE VÍDEO] -ESTÁ BEM. Portanto, sua tarefa aqui, Sean, é o seguinte. Eu ter escondido por trás dessas portas o número sete. Mas afastada, em algumas dessas portas bem como outros são números negativos. E seu objetivo é pensar desta linha superior de números como apenas uma matriz, ou apenas sequência de pedaços de papel com números por trás deles. E seu objetivo é, usando apenas o topo matriz aqui, encontrar-me o número sete. E nós estamos indo então para criticar como você vai fazer sobre isso. -Tudo certo. -Find-Nos o número sete, por favor. Não. Cinco, 19, 13. [RINDO] Não é uma pergunta capciosa. Uma. [RINDO] Neste ponto, sua pontuação não é muito bom, então você pode muito bem continuar. Três. [RINDO] Continue. Francamente, eu não posso ajudar, mas pergunto o que você está mesmo pensando, assim-- [RINDO] Apenas a linha superior, de modo você tem três esquerda. Então, encontrar-me sete. [RINDO] 17. Sete. [Aplausos] Tudo certo. [FIM DE REPRODUÇÃO] DAVID J. MALAN: para que pudéssemos assistir a esses todo o dia. E, claro, alguns dos demos deste ano talvez agora vai acabar no próximo vídeo do ano também. Então agora vamos realmente focar os algoritmos aqui, e ver se nós não podemos agora começar a formalizar como podemos ir sobre a obtenção de nossos dados a este estado que está classificado, de modo que, em última análise, podemos, na verdade, procurá-la de modo mais eficiente. E mesmo que nós vamos usar conjuntos de dados relativamente pequeno, como a que oito números temos aqui no quadro, em última análise, poderia aplicar essas mesmas idéias 1.000 entradas, um milhão de entradas, 4 bilhões de insumos, porque os algoritmos vão ser fundamentalmente o mesmo. E assim, este é o nosso último oportunidade para os voluntários de hoje, mas talvez o mais envolvido, para o qual precisamos oito voluntários para subir e pé-nos através do processo de triagem que será em breve ser sobre estes stands de música aqui. Deixe-me começar a voltar aqui. Então, um no verde turquoise-- é? Você está cometendo? Dois. Vamos lá para baixo. ESTÁ BEM. Três. Four. Vamos me-- OK, cinco. Você está sendo nomeado por seu amigo. Seis, sete, e oito. Vamos lá para cima. Tudo certo. Muito obrigada. Vamos lá para cima. Vamos lá para cima. Tudo certo. Então o que temos e isso aqui-- está entre os mais desajeitados, uma vez que este vai exigir que você humor Minha apenas um pouco de tempo. Você deve ser o número um. Qual o seu nome? ANNAN: Annan. DAVID J. MALAN: Annan. David. Qual o seu nome? JOSÉ: José. DAVID J. MALAN: Joseph, você é o número dois. SERENA: Serena, número três. Stefan, o número quatro. CYNTHIA: Cynthia. DAVID J. MALAN: Cynthia, número cinco. [Inaudível] DAVID J. MALAN: [inaudível]. David, número seis. MATT: Matt. DAVID J. MALAN: número de Matt sete. E? WAVERLY: Waverly. DAVID J. MALAN: Waverly, número oito. Tudo certo. Se você could-- gritos. Se você tudo, como seu primeiro desafio, há São oito estantes de música aqui de frente para a platéia. Se você pudesse colocar seus números no estes suportes de música de tal maneira que eles se alinham com o mesmos números no quadro. Então, faça-se olhar como que por colocando os seus números sobre estes música fica aqui. Excelente até agora. Excelente. ESTÁ BEM. Então, agora, vamos pedir ao questão em algumas maneiras diferentes. Como podemos ir sobre como classificar essas pessoas aqui em cima? Porque nós tivemos algumas abordagens anteriormente, em que estávamos tipo de tomada de dois baldes diferentes. E então nós geralmente remendar as coisas juntos. Assim que viu dois números que pertencia juntos, nós colocá-los juntos. Duas cartas que pertencem juntos. Mas vamos ver se nós Não é possível formalizar isso, para que possamos, finalmente, ter alguns pseudo-código que você vai, com o qual você pode resolver estes problemas. Então, agora, eu estou olhando para fora esses números aqui. E eu vejo um monte de erros. Em última análise, eu quero um no à esquerda e oito à direita. E então eu estou olhando estes dois, quatro e dois. E qual é o problema, obviamente? Sim. Assim. Dois, obviamente, vem antes quatro, então você sabe o quê? Deixe-me primeiro dar uma abordagem gulosa, se você, como muito problema um-- definir se você se lembra do Standard Edition do Conjunto de Problemas One, onde eu apenas localmente resolver o problema que está bem aqui na minha frente e ver onde ele me leva. ESTÁ BEM. Então, dois e quatro, deixe-me ir em frente e apenas trocar vocês dois. Se você pode mover fisicamente vocês mesmos e seu papel, Eu pareço ter começado a listar em um estado melhor. Agora, eles são bons. Eu vou seguir em frente, quatro e seis anos, parece ser bom. Não é um problema. Seis e oito, OK. Oito e um, um outro problema. Porque o que é verdade sobre oito e um? Um vem antes das oito, e assim o que devemos fazer? Vamos trocar esses dois. Um e oito. E agora, eu vou continuar. Eu vou continuar olhando para frente. E vamos ver o que acontece. Oito e três, de Claro, fora de ordem. Vamos swap. Oito e sete, é claro. Fora de ordem. Vamos swap. Oito e cinco, é claro, vamos swap. Tudo certo. Lista é ordenada. sim? OK, obviamente, não. Mas é um pouco melhor, certo? Porque aviso que aconteceu. Cada vez que realizou um swap, um menor número tipo de percolado que maneira, e um número maior percolado desta forma, ou nós vamos começar a dizer ao borbulhar para a esquerda ou para a direita borbulhar. Agora, não é suficiente, porque na melhor das hipóteses um número poderia ter movido um ponto para a frente, ou na pior das hipóteses, pode ter um número movido um local mais longe. Então, você sabe o quê, este tipo de funcionou muito bem até agora. Deixe-me apenas experimentá-lo novamente. Dois e quatro, eles estão OK. Quatro e seis, eles estão OK. Seis e um, fora de ordem. Então, vamos trocar vocês dois. E agora, repare o problema de começando a ficar um pouco melhor novamente. Seis e três, fora de ordem. Vamos trocar vocês dois. Seis e sete, você é bom. Sete e cinco, é claro, fora de ordem. Sete e oito, em ordem. E agora, eu talvez seja necessário fazer isso mais algumas vezes. E, na verdade, acho que para vós talvez quantas vezes maximamente pode eu tenho que andar para trás e para frente? Nós vamos voltar a isso. Então, dois e quatro ainda estão OK. Quatro e um, Nope. Então, troca de deixar. E, novamente, observar visualmente um é uma espécie de borbulhar para a esquerda, onde deveria estar. Quatro e três swap. Quatro e seis. Seis e cinco swap. Seis e sete. Sete e oito são boas. Boa. Estamos ficando ainda melhor. Então vamos ver. Agora, temos dois e um. Claro, trocar. Dois e três, três e quatro, quatro e cinco, seis e sete, sete e oito. Boa. E você sabe o quê? Porque eu fiz uma mudança lá, deixe-me fazer uma verificação de sanidade. Deixe-me ir até o fim voltar para o início. ESTÁ BEM. Um, dois-- sim, ver? Algo estava errado. Três, quatro, cinco, seis, sete, oito. E neste último passe, são Você está satisfeito com a minha empresa alegando que ele é classificado? ESTÁ BEM. Visualmente, isso é absolutamente verdadeiro. Mas funcionalmente, o que que também só acontecerá nesse último passe que permite que você para confirmar que esta lista é de fato classificadas? O que eu fiz ou não fazer isso último passe? AUDIÊNCIA: Não houve alterações. DAVID J. MALAN: Desculpe? AUDIÊNCIA: Sem alterações. DAVID J. MALAN: Não houve alterações. Portanto, seria estúpido da minha parte fazer isso mesmo algoritmo novamente se eu não fazer qualquer altera a primeira vez. E o Estado não mudou. Certamente, eu não vou fazer qualquer muda pela segunda vez. E assim, é seguro agora quer dizer, lista é ordenada. E, de fato, este é agora algo que nós vamos geral chamada bubble sort, em que pares, você corrigir erros novamente, e de novo, e de novo, e você manter indo e voltando, e frente e para trás, até que você fazer nenhum desses swaps, em que ponto você pode ter certeza, sim, eu Terminada a fixação todos os erros. Vamos redefinir e tentar outra abordagem. Se vocês poderiam voltar para a ordem que você era um momento atrás, que olhou como esta. Agora, vamos ter uma abordagem um pouco mais como o livro exame, pelo qual estávamos constantemente seleccionando a letra do alfabeto que nós meio que queria para lidar com o próximo. Talvez fosse uma carta alta, como A, ou uma baixa letra Z. Então, todo mundo está de volta nesta ordem. E agora deixe-me fazer isso. Vamos ver Eu sei que tenho oito números aqui. Eu estou indo para ir em frente e apenas deliberadamente selecione os elementos mais pequenos. Certo? Isso parece muito intuitivo. Por que eu não encontrar o menor elemento, colocá-lo onde ele pertence, em seguida, obter o próximo elemento mais pequeno, coloque -lo onde ele pertence, e basta repetir. Porque intuitivamente, que deve funcionar também. Então, quatro, que é um número bastante pequeno. Eu vou lembrar de onde isso é. Espere um minuto. Dois é menor. Deixa-me lembrar onde dois é, e esquecer-se sobre quatro. Nós vamos lidar com isso mais tarde. Seis, eu não estou interessado. Oito, eu não estou interessado. Um deles é o meu novo número pequeno. Então, eu vou me lembrar onde você estiver. Três, não está interessado. Sete, não está interessado. Cinco, não está interessado. Então, sem cair o palco este ano, Vou agarrar número um-- e qual era o seu nome? ANNAN: Annan. DAVID J. MALAN: Annan. E se você pudesse se juntar a mim no o início da lista, vamos colocá-lo onde você pertence. Unfortunately-- qual é o seu nome? STEFAN: Stefan. DAVID J. MALAN: Stefan está no caminho. Portanto, antes de Stefan resolve este problema, o que devemos fazer? O que vamos fazer com Stefan? AUDIÊNCIA: [inaudível]. DAVID J. MALAN: OK. Assim nós poderíamos fazer isso. Poderíamos tipo de levar Stefan e sua quatro, e basta colocá-lo em uma variável e segurá-lo para uma certa quantidade de tempo, tornando assim espaço para o número um. E isso não é ruim. Eu poderia sugerir, por que não fazer nós apenas colocar Stefan aqui? Por que isso pode violar um das ideias que começaram falando última vez, na semana passada? Sim? AUDIÊNCIA: [inaudível]. DAVID J. MALAN: Não há nenhum índice para ele. Se você acha que isso, de fato, como um array, isto é como um negativo, por isso não há memória, na verdade, aqui se este é realmente uma matriz, como se declarou na semana passada na conferência. Assim, não devemos fazer isso. Podemos armazená-lo em uma variável. Ou você sabe o quê? Eu ouvi alguém sugerir isso. O que mais poderíamos fazer com Stefan? Por que nós não apenas expulsá-lo e colocá-lo sobre o lugar onde estava o número um. Então, se você quer ir para lá. E, de fato, este é um solução muito boa. Agora, por um lado, eu tenho tipo da piorou o problema. Quatro é agora mais longe de onde ele deve ser. Ele deve ser em direção a esse meio. Mas você sabe o quê? Isso poderia ter sido má sorte. Talvez o número oito foi aqui. E assim, talvez faríamos ter tido sorte, e oito empurrada para mais perto do fim. Assim, no final do dia, É o tipo de todas as médias para fora. Nós não precisa se preocupar com quatro. Tudo que me importa agora é seleccionando o elemento mais pequeno. E agora, o que eu vou fazer é esquecer-se sobre o número um permanentemente, porque eu sei o lista atrás de mim agora está classificada. Assim, a minha lista era anteriormente tamanho oito. Agora, é do tamanho de sete. Então, meu problema é conseguir menor, embora de forma linear. Então, agora, eu estou indo para selecionar o atual elemento mais pequeno, dois. Seis, oito, quatro, três, sete, cinco. Esse foi o menor elemento. Então o que é que eu vou fazer com-- o que era o seu nome? JOSÉ: José. DAVID J. MALAN: Joseph? Nós vamos deixar Joseph no lugar. Agora, eu vou fingir que esses caras é-- bem, Eu sei que estes dois já estão classificados. Vamos agora concentrar-se na restante da lista. Seis é a menor corrente. Oito é maior. Quatro é agora a menor corrente. Três é agora a menor corrente. E agora, eu estou indo para selecionar três, que é-- o que é seu nome? SERENA: Serena. DAVID J. MALAN: Serena, se pudesse pegue o seu número e swap com-- Kalsang: Kalsang. DAVID J. MALAN: Kalsang. Vamos voltar, e estamos vai trocar os dois. E agora, vamos colocar isso no piloto automático. Eu estou indo para ir e deixá-lo para vocês para selecionar os menores elementos próximos. Dun, dun, dun, dun. Número quatro, o que você deve fazer? Excelente. Agora, eu vou fazer uma outra passagem. Dun, dun, dun, dun. Vejo cinco é o próximo menor. Agora, eu vou tomar outra passagem. Dun, dun, dun, dun. Seis é o menor. Boa. Sete é o menor. Sem mudança. Oito é o menor. Feito. Então, o que acabou de fazer por forma iterativa seleccionando um elemento após a outra é implementar algo que nós somos vai formalizar como selecção de classificação. E é talvez ainda simples de explicar, em que, literalmente, tudo o que você quero fazer é apenas manter indo e voltando pela lista seleção, a próxima menor elemento, até que você esteja feito. Por isso, é ainda mais simples, talvez intuitivamente, que a última. Vamos tentar um último. Se vocês poderiam redefinir a si mesmos nas seguintes posições uma última vez, vamos ver se nós não podemos agora formalizar uma outra abordagem. Na verdade, seria alguém lá fora, gostaria de propor de que outra forma poderíamos fazer sobre este assunto? Sem jogar fora buzzwords ou tipo de respostas que já são conhecidas, apenas intuitivamente, o que poderíamos fazer? AUDIÊNCIA: [inaudível]. DAVID J. MALAN: Yeah. Então, há alguma grande intuição lá. As coisas boas parecem acontecer até agora em ciência da computação quando dividimos e conquistar o problema de dividir ao meio e meio a meio. E assim, de fato, nós poderia começar a fazer isso. E, de fato, que vai ser, vamos ver, um dos nossos melhores soluções ainda. Mas vamos voltar a isso em pouco tempo. Na verdade, nós vamos fazer que um pouco mais tarde esta semana. O que mais podemos fazer para resolver isso? Então, todo mundo aqui está em ordem aparentemente aleatória. Você sabe o que? Ao invés de ir e voltar, frente e para trás, e para trás cada vez, este se sente como Eu estou fazendo um monte de pé. Por que não posso apenas começar em o início da lista, e basta colocar quatro onde ele pertence? Então deixe-me assumir para o momento que minha lista é apenas este primeiro elemento. É quatro classificados neste momento no tempo, se tudo o que me importa é tudo aqui? Esta é uma espécie de trivialmente verdadeira, certo? Como a lista contendo um número, e que é, obviamente, o número quatro classificados. Então deixe-me apenas estipular que esta lista é ordenada. Mas agora eu tenho o resto desta lista. Então, agora, eu encontro dois. Onde faz dois, obviamente, pertencem em relação a quatro? Antes quatro. Então, o que eu posso fazer aqui? Qual é o seu nome? JOSÉ: José. DAVID J. MALAN: Joseph, se você pudesse voltar atrás por apenas um momento com o seu número. E agora o que deve Stefan fazer aqui? Vamos mudar Stefan aqui. E agora, vamos Joseph entrar aqui. E agora, deixe-me afirmar que tudo aqui está classificada. Então, resultado semelhante, mas um abordagem fundamentalmente diferente. Eu nem sequer olhou para o que está lá em baixo. Eu continuo tendo os elementos como eles são entregue a mim, e lidar com eles. Então, agora, eu vejo o número seis. Onde é que o número seis pertencem? Temos dois, quatro, seis. Exatamente onde ela está agora. Então, vamos deixar isso quieto, e agora afirmam que esta parte da lista agora está classificada. E assim, este se sente fundamentalmente diferente, já que eu sou apenas movendo-se através da lista aqui linearmente, e eu nunca estou dobrando para trás. Sim. Tudo certo. Assim, oito, onde você pertence? Aqui mesmo. Perfeito. Então, agora, um. Uh oh. Isto parece que é vai ser caro. Agora, no algoritmo anterior, Eu apenas trocados pessoas. Para que eu possa colocá-lo todo o caminho no no início, mas depois mudou Joseph. Mas se eu passar Joseph, agora o que vai ser errado? Agora, eu tenho a sorte de undone-- tenho dado um passo para a frente e, em seguida, um passo para trás, porque agora Joseph estaria fora de ordem. Então, vamos fazer isso. Se você pudesse levar o número um e passo para trás por apenas um momento. Como podemos put-- o que mesmo o seu nome? ANNAN: Annan. DAVID J. MALAN: Annan no lugar? O que precisa acontecer com respeito a dois, quatro, seis, oito e? Tudo que eles precisam mudar. Portanto, se oito gostaria de deslocar em primeiro lugar, em seguida, seis, depois quatro, depois dois. E então Annan, se você gostaria de vir aqui, bom. Mas aqui, nós temos apenas tipo de pago um preço num ponto diferente no algoritmo. Considerando última vez com a seleção tipo, e até mesmo bubble sort, Eu estou andando para trás e frente, para trás e para frente, que é, certamente, somando tempo-sábio, e, literalmente, passo a passo. Ordenação por inserção, na primeira vista, parece que é super-inteligente, em que eu sou apenas tornando lento, o progresso incremental, mas eu não vou esta frente e para trás. Mas se alguém é de fato fora de ordem, aviso todo o trabalho que eu apenas tive que fazer. Eu tive que mudar metade da lista apenas para dar espaço para o número um. Então é a mesma quantidade de trabalho, até agora, ele sente, apenas um tipo diferente de trabalho. Vamos continuar. Portanto, agora sabemos que toda a gente entre um e oito são classificadas. Aqui, eu tenho o número três. Se você gosta de pegar número três, passo para trás um. E o que vocês precisam fazer? Sim. Então, isso é um outro, dois, três passos. Três unidades de tempo que custam apenas me, de modo que os três podem agora encaixar. Finalmente, sete. Vamos em frente e ter você tomar um passo para trás. Isso só vai nos custar uma unidade de tempo, mas isso é OK. E agora, cinco de ir para ser um pouco mais caro. Se você gostaria de dar um passo atrás. Precisamos avançar oito, e sete, e seis. E então todo mundo está agora classificada. Assim, uma grande mão para os nossos voluntários aqui. Muito obrigada. [Aplausos] Obrigado a todos. Obrigado a todos. Então vamos ver agora o quão caro tudo isso era. Vamos considerar, talvez, o mais simples delas, uma espécie de bolha. E digo mais simples, só porque você pode resolvê-lo avidamente por apenas resolver o problema de pares aqui. Corrigir o problema de pares aqui, uma e outra vez e novamente, repetindo como muitos vezes como você realmente precisa. Assim, verifica-se que com uma espécie de bolha, bem, quantos passos eu tenho que assumir a primeira passagem desse algoritmo? Eu poderia take-- vamos see-- um, dois, três, quatro, cinco, seis, sete. E há oito elementos aqui. Então, é como n menos 1 passos para começa a partir do início da lista para o fim da lista. Mas com seleção tipo, lembre-se que eu sou selecionar os elementos novo e de novo e, novamente, que é menor, Estou colocando-o no lugar, mas então eu não sou olhando atrás de mim novamente. Então, eu acho que é um pouco mais clara que, em seguida, pela primeira vez, que pode tem que tomar todos os passos n menos 1 para encontrar o elemento mais pequeno. Então eu colocá-los no lugar, e eu expulsar quem quer que estivesse aqui anteriormente. Mas então eu não tenho que manter a olhar para este elemento, porque eu sei que é já a menor. Então, agora, eu posso olhar para apenas sete elementos, em seguida, seis elementos, em seguida, cinco elementos, em seguida, quatro elementos. E assim matematicamente, se n é o número de elementos ou números que começou com, você pode imaginar que este é o mesmo que n menos 1, além n menos 2 etapas, n menos mais 3 etapas, n menos mais 4 passos, tudo o maneira para baixo a apenas um passo. E eu estou em minha última pessoa. E se você se lembra que um monte Status de livros ou livros de matemática ter essas fórmulas na capa dura para trás ou frente deles, verifica-se que esta série pode ser expresso de forma mais simples como n vezes n menos 1 sobre 2. E é bom se isso não é na vanguarda da sua mente. Mas isso é realmente verdade. Isso é apenas uma maneira mais simples de escrevê-lo. E então se você acha de volta à escola, quando você acabou de começar multiplicando coisas, isso, claro, é apenas n ao quadrado menos n dividido por dois. Tudo o que eu tenho feito é expandir as expressões lá. E assim vamos reescrever este um pouco diferente. Isso n ao quadrado dividido por 2 menos n / 2. Então, novamente, eu sou apenas um tipo de aplicação um pouco de aritmética governa lá. Mas note-se agora que o maior prazo nesta expressão, por assim dizer, é que n ao quadrado. Então, sim, é n ao quadrado dividido por dois, menos n / 2. Mas, geralmente, se n for vai ser um valor grande, Eu vou alegar que n ao quadrado vai ser o fator dominante. É só vai ser um contribuinte maior para o número de passos do que n / 2. Então, o que quero dizer com isto? Vamos tentar um exemplo simples, mesmo embora a matemática fica um pouco grande. Então, suponha que tinha 1 milhão de pessoas no palco, ou 1 milhão de coisas que deseja classificar. Vamos ligar um milhão em exatamente que fórmula para ver quantos passos que leva totais para classificar um milhão de elementos usando digamos, tipo de seleção. Então, nós teríamos a mesma fórmula como antes. Eu ligar um milhão, para que eu recebo um milhão quadrado dividido por 2, menos de um milhão dividido por 2. Se eu fizer isso de matemática com antecedência aqui, temos 500 bilhões menos 500.000, que nos dá 499999500000, que é muito danado grande. Na verdade, se você comparar agora 499.000 milhões, 999 milhões, 500000 contra o nosso valor original, 500 bilhões, é tão bem perto. Certo? n ao quadrado dividido por 2 dá US-- ou melhor, n ao quadrado dividido por 2 nos deu 500 bilhões. Isso é muito danado perto a 499.999.500.000, o que quer dizer fora subtraindo 500.000, ou, mais geralmente, subtraindo fora n ao quadrado, não é realmente um grande negócio. O n ao quadrado faz com que essas números crescem muito rápido. Agora, isso só é importante na medida em como nós, como cientistas da computação, são geralmente não vai se importar tanto sobre as nuances dessas fórmulas e exatamente o que o respostas precisas são. Nós nos preocupamos só isso, você sabe o quê? No final do dia, esta fórmula é da ordem de n ao quadrado. Sim, nós estamos dividindo por dois lá dentro. Sim, nós estamos subtraindo off n menos 2. Contudo, no final do dia, o termo que realmente nos dói e custa-nos uma série de etapas é que o termo quadrado. E então o que um cientista da computação vai geralmente fazem é ignorar todos aqueles Da ordem menor, e basta olhar para o que mais contribui para o custo. E isso é bom, porque podemos agora falar com muito mais generalidade sobre algoritmos, e pode compará-los. E o fato de que eu sou O utilizando este é deliberada. Quando eu digo no fim de, estou especificamente referindo-se a algo chamado grande O. E ó grande é uma notação que um computador cientista usa para descrever um limite superior em alguma coisa. Então, se você dizer que um algoritmo é em grande O de n ao quadrado, como eu propus apenas um há pouco, que os meios que, em termos da sua execução tempo ou a sua eficiência, ele assume a ordem quadrado de n passos. Talvez mais, talvez menos. Mas é da ordem de n ao quadrado. E esse é o limite superior. Não vai ser mais doloroso do que isso. Não vai ser n cubos, ou 2 ao n, ou algo muito maior. Este é um limite superior em tudo o que o custo é. Assim, dado que, vamos Considere apenas alguns exemplos. E esta é apenas uma lista finita tempos de execução de muito comuns para algoritmos que está destinado a ser ilustrativos de alguns coisas que temos visto já. Assim, por exemplo, no caso de seleção tipo, o que eu estou dizendo aqui está em execução que a seleção de tipo tempo é da ordem de n ao quadrado. No pior caso, eu vou ter um monte de números aleatórios aqui. E, como vimos matematicamente, se eu continuar caminhando por meio da lista, através do lista, selecionar o próximo menor elemento novo e de novo, se eu na verdade, anote todas as etapas Estou tomando como eu propus como uma fórmula antes, é da ordem de n ao quadrado etapas que eu estou tomando. E verifica-se que bolha tipo e ordenação por inserção são tão lento no pior dos casos. Considere, por exemplo, ordenação por inserção, o último algoritmo, tratámos, que nos fez olhar para o elemento, e, em seguida, inseri-lo onde ele pertence. E então olhamos para o próximo elemento, e inseriu-lo onde ele pertence. Por isso, considero o melhor cenário possível. Suponha que eu tinha meus voluntários alinhar literalmente, como este, de um a oito, já ordenados. Quantos passos é a ordenação por inserção vai levar para classificar oito pessoas, se eles chegam no palco olhando assim? Oito pessoas já ordenados. E eu uso a inserção de tipo. Esse último dos algoritmos. Bem, vamos reviver rápido real. Então, se eu começar aqui, eu vejo um. Onde é que se pertencem? Ele pertence aqui. Eu vejo dois. Onde é que dois pertencem? Aqui mesmo. Eu vejo três. Onde é que três pertencem? Aqui mesmo. Eu vejo quatro. Aqui mesmo. Cinco, seis, sete, oito. Não há nenhuma razão para me repetir. E assim, como muitos passos é que, em termos de n? É da ordem de n passos, certo? n menos 1. Mas eu tomou uma série linear de passos, e agora eu sou feito. Então esse é o melhor caso, no entanto. E sobre o pior caso? O que oito estavam lá, e sete estavam lá embaixo, e um e dois foram mais aqui, então que a lista foram verdadeiramente revertido? Bem, o que acontece de fato se este é o número? E nós vamos fazer apenas um par de exemplos. E se, na verdade, o número oito está aqui, e os gritos number--. Então, o que se, de fato, o número oito é todo o caminho até aqui, e eu estou usando ordenação por inserção? ESTÁ BEM. Eu reivindico no momento que está no lugar. Mas agora, seven-- onde é que sete ir? Claro, ele vai por aqui. Então eu tenho que mover oito mais de um lugar. Agora seis, onde ela vai? Bem, tudo bem. Agora, eu tenho que mudar oito mais um lugar, e sete ao longo de um lugar, e então eu plop para baixo seis. Assim, o primeiro tempo, custo me um passo para consertar as coisas, então isso me custou dois passos para consertar as coisas. Quantos passos é vai demorar para corrigir coisas para colocar cinco no lugar certo? Três. Porque agora eu tenho que mover um, dois, três. Quantos passos é que vai tomar para colocar quatro no lugar certo? 4 plus 5, acrescido de 6, além de sete. E por isso é matematicamente idêntica à o que descrevemos para a seleção de classificação. Nós temos nesta série que está apenas a aumentar. 1 mais 2 mais 3, mais 4, ou, inversamente, 7 + 6 mais 5 mais 4 acrescenta-se para hoje para fins da ordem de n ao quadrado. Então deixe-me também que estipulam bubble sort é também no n ao quadrado. Porque com bubble sort, cada vez que eu vá até a lista, Estou levando aproximadamente quantos degraus? Cada vez que eu literalmente andar de lá para lá? Cerca de n passos. Mas quantas vezes eu poderia precisa ir através da lista? Bem, cerca de tempo n. Talvez n menos 1, mas cerca de n vezes. Bem, por que isso? Bem, com bubble sort, se começamos com bubble sort, com a lista na pior possível situação, que mais uma vez é completamente para trás, o que vai acontecer? Eu percorrer a lista, eo número um pertence todo o caminho até lá. Mas com bubble sort, até que ponto é que um movimentar na minha primeira passagem através da lista? Quantos pontos ele consegue mais próximo do local correto? Apenas um. Então, se você tipo de razão através deste, cada vez através deste algoritmo, Tendo cerca de n passos de David. Mas quantos passes a lista é vai levar para um a bolha à esquerda, onde ele pertence? Ele tem que se mover como, n espaços desta forma. Então, só para fazer a triagem da lista, Eu tenho que andar para trás e n vezes. E cada vez, estou olhando para n elementos. Então, fazer as coisas n n vezes em da ordem de n ao quadrado. Agora, vamos ver em alguns dos curtas que são incorporados no próximo problema do CS50 definida, uma outra abordagem para estes, mas por agora, vamos considerar apenas alguns outros tempos de execução, especialmente se os triagem tomar um pouco de tempo para afundar. O que é um algoritmo que vimos já que leva na ordem de n passos? O que deve tomar uma série linear de passos que temos visto até agora? O que é isso? A pesquisa de diretório de telefone. O primeiro algoritmo. Certo? Onde estamos linearmente à procura de Mike Smith? De fato. A partir da semana zero, quando eu comecei virando uma página de cada vez, e eu mesmo disse que era uma espécie de um algoritmo sensação linear, e tivemos que imagem na placa com a linha vermelha reta eo amarelo em linha reta linha, aqueles eram de fato algoritmos que são em grande ó de n. Porque para encontrar Mike Smith em um telefone livro de n páginas, no pior caso, pode me n passos tomar. Que tal pegar atendimento? Um dois três quatro cinco seis. Qual é o tempo de execução deste algoritmo para fazer a chamada? Big O de n, porque, em teoria I tem que apontar todos na sala. Agora, como um aparte, que sobre o outra otimização de semana de zero? Dois, quatro, seis, oito, 10, 12. Um cientista da computação seria perceber, espere um minuto, que é da ordem de n dividido por dois passos. Certo? Porque eu estou fazendo duas pessoas de cada vez. Mas vamos ignorar esses termos de ordem mais baixa, e nós apenas estamos indo para jogue fora a dividir por 2, e apenas dizer, grande O de n para esse algoritmo bem. Que tal este? Vamos pular alguns destes, mas o que era um algoritmo que foi log de n? Isso levou cerca de log n passos? O dividir e conquistar. Exatamente. Como o exemplo do livro de telefone em semana zero e hoje cedo, onde dividimos o problema de novo e de novo e de novo. Nós chamou-o sobre a placa na semana zero como uma linha verde curvado, e dissemos que dia era um algoritmo logarítmica. E, de fato, o número de passos leva para realizar dividir e conquistar, ou busca binária como nós vamos começar chamando-o, como no livro de telefone, é da ordem de registo e etapas. E isso é um pouco de um estranho. O que leva uma única etapa, ou mais especificamente um número constante de passos? Talvez seja dois, talvez seja três, mas um cientista da computação apenas simplifica-lo tão grande O de 1, um número constante de passos. O que é algo que você poderia fazer isso tem um número constante de passos? Qual é o tempo de execução de bater palmas? Tempo constante. Certo? Como, qual é o tempo de execução de fazer qualquer coisa que leva apenas um operação, como imprimir F Olá Mundo. Isso pode ser considerado constante de tempo, a menos que menos caso esquina com a impressão F, O que o tempo de execução de impressão F realmente ser? E porque? O que é de medição n nesse caso? AUDIÊNCIA: [inaudível]. DAVID J. MALAN: Exatamente. O número de caracteres que pretende imprimir. Portanto, é muito sensível ao contexto. Hoje, temos vindo a apostar muito em letras e números aqui no conselho. Mas também pode ser caracteres em uma seqüência real. Assim, verifica-lá fora é outra medida que vai começar a se preocupar, e isso é o oposto de grande O, por assim dizer. Isso é notação omega. Considerando que grande O significa o que é, o um limite superior ao seu tempo de execução? No máximo, quanto tempo pode tomar alguma coisa? Omega-- desculpe este continua vindo up-- é o oposto do que, pelo que é um limite inferior na quantidade de tempo algo pode tomar. Assim. por exemplo, o que é um algoritmo que toma medidas sempre n ao quadrado? Bem, um dos algoritmos que temos visto Hoje em dia, na verdade, pode ser que como bem. Tipo de seleção. Seleção tipo é muito estúpido. Mesmo que o algorithm-- desculpe, mesmo se a matriz já está classificado, seleção tipo vai manter uma curta caminhada através da lista para se certificar de que tem o menor elemento novo e de novo e de novo. E mesmo que você os seres humanos no público sabe disso, espere um minuto, você já passou o elemento mais pequeno, o computador não sabe que até que parece todo o caminho através da lista. Do mesmo modo, um limite inferior que também pode ser tida em conta talvez seja tempo linear. Quanto tempo leva para elementos tipo n no melhor caso usando algo como bubble sort? Suponha que a sua lista já está classificado. Dissemos bubble sort assume da ordem de n ao quadrado etapas. Mas e se ele já está classificado? E se você perceber depois uma passagem através da matriz que você fez há swaps? Você precisa continuar a fazer mais passes? Não. Assim, um limite inferior na bubble sort pode ser dito para ser linear. Omega de n. E podemos olhar para outros de estes também. Então, vamos dar uma olhada rápida em apenas uma visualização aqui para ver como estes se distinguem. Eu estou indo para ir para baixo aqui neste A página que está disponível no site do C50, mas vai ser uma dor de começar a trabalhar, uma vez que utiliza uma tecnologia chamada Applets Java, que é um em grande parte sem apoio nos dias de hoje, pelo menos por Chrome e certos outros. E deixe-me ir em frente e acelerar este e explicar o que está acontecendo. Esta é uma demonstração de bolha tipo, o primeiro algoritmo de nós olhamos. E é uma visualização em que cada destas barras representa um número. Quanto maior for a barra, quanto maior o número. Quanto menor o bar, Quanto menor o número. E o que você pode ver visualmente, mesmo embora este está indo super rápido, é que a barra vermelha é como eu, andando para trás e corrigir problemas. Você pode ver que os elementos maiores são, na verdade borbulhando para a direita, e os elementos menores está borbulhando para a esquerda. E aqui, se nós realmente olhar mais de perto, nós podemos realmente contar o número de comparações e swaps que estavam sendo feitos. Mas em vez disso, vamos olhar no segundo algoritmo vimos anteriormente com o nosso voluntários, selecção de classificação. Visualmente, tem um efeito muito diferente. Mas é, de novo, muito intuitivo, em que mantemos selecionar o próximo menor elemento, e temos um pouco de sorte. Isso foi fundamentalmente mais rápido. Mas se nós corremos esse novo e de novo e novamente com muitos insumos, veríamos que ele é de fato ainda em grande O de n ao quadrado. Vamos fazer um último aqui, ordenação por inserção, que foi o terceiro algoritmo nós olhamos, ea recordação que este lida com a como elementos que ele encontra-los, Mas, então, talvez turnos coisas para abrir espaço, inserção de elementos a que pertencem. E isso também acaba dando o resultado final. Agora todos os três daqueles senti muito rápido. E, de fato, eu corri-los em um bom clip. Mas, fundamentalmente, eles são todos bem horrível, para ser honesto. Todos estes algoritmos até agora que são executados em grande O de n ao quadrado tomar um pouco de tempo para ser executado no final. E, de fato, podemos ver e sinto que este, por último, se eu puxar para cima esta terceira e última demonstração. Este é outro visualização que está acontecendo para mostrar bubble sort à esquerda, tipo de seleção no meio, e alguma coisa, como um de nossos mão levanta mais cedo sugeriu, merge sort à direita. Um dividir e conquistar estratégia à direita. E isso é, na verdade, o que nós somos indo olhar na quarta-feira. Mas o tempo estes funcionem em paralelo vamos. É mais ou menos o mesmo número de elementos, todos rodando ao mesmo tempo. Bubble sort vs seleção tipo vs merge sort. Agora, eles estão todos correndo em teoria, ao mesmo tempo. A CPU está sendo executado em a mesma velocidade, mas você pode sentir-se como chato isso é indo muito rapidamente para se tornar, e quão rápido quando nós injetar um pouco de semana algoritmos do zero pode que acelerar as coisas. E agora vamos comparar estes em uma última forma. Eu estou indo para ir em frente para o site do CS50, onde temos este elo final para hoje, onde alguém na internet gentilmente montar um vídeo que capta o que ordenação diferente algoritmos soam como. Esta é a ordenação por inserção. [BIPE] Através do qual você está aplicando uma frequência com base na altura da barra de barra. Esta é bubble sort. [BIPE Warped] Chegando próximo é-- vindo ao lado espécie seleção é--, onde mais uma vez, estamos selecionando o próximo elemento mais pequeno, e podemos vê-lo crescer da esquerda para a direita. Merge sort, o nosso vencedor, até agora, hoje. Observe como ele está dividindo as coisas em [inaudível] a metade e trimestres. Tipo Gnome, que não tem falou, e cria visualmente e audally um pouco de forma e som diferente. Indo e voltando, limpar as coisas. Também check out heapsort no site do cara. E é isso. Vamos vê-lo na próxima vez. [Whooshing E MÚSICA]