[Powered by Google Translate] [Semana 3, continuação] [David J. Malan - Harvard University] [Esta é CS50. - CS50.TV] Tudo bem. Bem-vindo de volta. Este é CS50 e este é o fim da semana 3. Portanto, para aqueles anos, desconhecido última Harvard lançou o que é chamado de Laboratório de Inovação, ou i-laboratório, que é um maravilhoso edifício através do rio no campus da HBS que é aberto a estudantes universitários, estudantes GSAS, estudantes de todo o campus, através de incluindo professores, e é um lugar para se unem para trabalhar em coisas inovadoras, coisas especialmente empresariais se você e 0 ou mais amigos estão pensando em fazer algo empresarial quer durante esta classe, depois de esta classe, ou além. Então, uma das coisas que eles fazem durante a vigência J é essas viagens, uma das quais é a New York, uma das quais é Silicon Valley. O espaço é muito limitado, mas é uma oportunidade de esfregar ombros com MBAs e os alunos de pós-graduação em todo campus e passar mais tempo nas áreas respectivas conversando com startups, conversando com empresários e afins. Então, se interessar, veja este URL aqui. Ele também está disponível nos slides online. Poderíamos baixar o tom do áudio casa um pouco? Se você gostaria de se juntar a nós para o almoço desta sexta-feira, 13:15 em Fire & Ice, por favor, vá lá. Desculpas se o formulário já está preenchido pelo tempo que você chegar lá. Mas vamos continuar esta tradição em diante. Hoje continuamos a discussão maior nível de vários problemas que podemos resolver, focando muito menos, hoje, pelo menos, em código e muito mais sobre idéias. Então, acho que volta à semana 0, quando arrancou um livro de telefone no meio, cujo objetivo era fazer algo, reconhecidamente, um pouco dramática senão enviar o ponto em que a procura não tem de ser, necessariamente, tão óbvio à primeira vista, como se poderia pensar. E resolução de problemas em geral pode não ser necessariamente ser sempre o melhor - A solução mais óbvia pode não ser necessariamente a melhor. Então, nós tivemos este livro de telefone e, francamente, todos nós nesta sala tinha o instinto, mais provável, a começar no meio quando se olha para Mike Smith e depois vá para a esquerda ou para a direita com base em qualquer letra do alfabeto que aconteceu a acabar em. Mas essa idéia simples que nós, humanos, dado como certo por tanto tempo realmente deve começar a vir para a frente de sua mente porque, como os problemas ficam muito mais complexo do que um livro de telefone, esses mesmos simples, idéias brilhantes são o que vai permitir-nos para resolver problemas muito mais complicados e mais interessante, entre eles algumas das coisas que nós tomamos para concedido já nos dias de hoje. Bilhões de páginas da web lá fora, e ainda do Google e Bing e similares são capazes de encontrar coisas para nós assim. Isso não vai acontecer por meio de busca linear, buscando através de todas as páginas possíveis. Facebook é capaz de dizer que todos são seus amigos ou amigos de amigos, e que também pode ser feito aparentemente em um instante estes dias mesmo que eles têm milhões de usuários. E assim como nós realmente resolver os problemas em que a escala vai, finalmente, reduzir às idéias que vimos na semana 0 e um pouco mais hoje. Nós não vamos re-executar este algoritmo, mas lembro que também fiz na semana 0 neste exercício onde tínhamos todos de pé, assumir o número 1, e depois tivemos todos auto-count, emparelhando fora, adicionando seus números, em seguida, metade da turma sentou-se em cada iteração. Portanto, passou de 500 estudantes de 250 a 125 e assim por diante. Mas, como disse na segunda-feira, a idéia poderosa que existe era que se nós dobramos o tamanho desse problema e todas as crianças de Justiça ou Ec 10 voltou para o quarto e se juntou a nós, bem, nós provavelmente poderia contar que todo o grupo agregado com apenas uma iteração mais grande do circuito porque eles apenas talvez o dobro do tamanho ou em 10 de Ec caso um pouco mais do que o dobro do tamanho. E, assim, teria que gastar um pouco mais de tempo, mas não teria de gastar 400 ou 700 passos mais. Só para pintar o quadro de uma forma que é um pouco menos abstrata, não vamos ter todos de pé. Mas se aqueles que escolheu para sentar na orquestra hoje não se importaria em pé, vamos ver se podemos descobrir entre vocês que a pessoa mais alta é fazendo o mesmo tipo de algoritmo comparativa. Então, se você está sentado na orquestra, as minhas desculpas, mas um passo, levantar-se; passo 2, par fora com ninguém por perto de você, descobrir quem é mais alto, e sentar-se, se você é mais curto. Em seguida, repita. [Estudantes murmurando] Okay. Okay. Fica-se de pé. Qual é o seu nome? >> André. André, você é a pessoa mais alta na seção orquestra hoje. Parabéns. [Aplausos e aplausos] Okay. Sente-se. Então, nós encontramos Andrew. Mas por quanto tempo ele teria me levado, por exemplo, para encontrar Andrew nesta seção orquestra de 50 + ou mais pessoas? Eu poderia ter tido uma abordagem bastante simples e começar aqui. E eu tenho duas pessoas se levantarem e eu só compará-los, e então eu digo para quem é um pouco mais curto, "Ok, você sentar-se", e eu vou lembrar de quem era a pessoa mais alta. Então, repito, repetir, repetir, e eu ficar com a pessoa mais alta até encontrar alguém um pouco mais alto do que eles, que no ponto a pessoa tem um pouco mais curto para, em seguida, sentar-se. Mas em que o algoritmo nesta seção orquestra, se há n de você, quantos passos é que o algoritmo vai levar? >> [Aluno] N. Ele vai levar n, direito, porque na pior das hipóteses, por assim dizer, a pessoa mais alta é a última pessoa que eu recebo apenas pela má sorte aleatória. Assim, no pior dos casos, o tempo de execução do algoritmo que é linear, isto é n, onde n é o número total de pessoas no espaço, o tamanho do problema. E sobre esse algoritmo? O fato de você todos se levantaram e novamente metade de você se sentou, metade de você se sentou, metade de você se sentou. Quantos passos deve que ter tomado se há n de vocês aqui? [Estudante] N log n. >> Isso seria pior. Entrar n. Então log n, mesmo se você não consegue lembrar o que é um logaritmo, por agora, apenas apreciar que se relaciona de alguma forma a este reduzir para metade e reduzir para metade e reduzir para metade. Ele não tem que ser um factor de 2. Que poderia ser um factor de 3. Mas é esta repetição do mesmo tipo de elemento de tal forma que a dimensão do problema começa aqui mas logo em seguida vai aqui, então aqui, então aqui, então aqui. Você não está levando pequenas mordidas fora do problema, você está realmente de cortar fora a ele com um grande golpe de cada vez. Então, nós tivemos 50 pessoas, depois 25, depois 12 ½ ou 13 pessoas em pé, então 6 ½ e assim por diante até que, finalmente, de pé apenas Andrew foi deixado. Então, vamos chamar isso de registro de n, e você pode visualizar isso da seguinte forma. Lembre-se esta foto aqui, onde um algoritmo linear é como a linha vermelha lá, a linha amarela foi a contagem pelo algoritmo 2s que usamos para estudantes contagem no passado, mas hoje o Santo Graal vai permanecer esta linha verde onde se duplicou o número de pessoas na seção de orquestra ou apenas disse: inferno, vamos ter todos em toda a sala de pé, não um grande negócio porque aproximadamente o dobro quantas pessoas estão aqui, 1 mais iteração, e não um problema. Descobrimos André ou quem quer que seja mais alto do que Andrew no mezanino ou na varanda. Portanto, esta ideia simples que tomamos tanto para concedido em uma lista telefônica, perceber que existem muitos lugares diferentes em que podemos aplicá-lo. Só para dar um tapa algum jargão - na verdade, ao invés de jargão primeira, deixe-me ir para esta foto aqui. Agora falamos sobre n e n / 2 e efetue de n, mas certamente podemos chegar a, como veremos ao longo do semestre, outro tipo de fórmulas matemáticas para descrever esta noção geral de tempo de execução. Estes são fora de contexto por agora, porque nós vamos ver antes de tempo algoritmos que estes realmente representam. Mas note aqui a linear linha n, a linha reta, é realmente muito baixo apontando agora. Isso é uma espécie de ilusão de ótica em que acabamos de mudar o eixo x representa eo eixo y, e nós podemos fazer um ponto de linha reta em qualquer direção que queremos. Mas a razão que é tão aparentemente apartamento agora é porque nós precisávamos para fazer o quarto neste gráfico por muito mais lento tempos de execução. Por enquanto, sabemos que existem alguns algoritmos muito ruins na vida, alguns dos quais não tomar medidas n ou, melhor ainda, faça o login n passos, mas muito mais. Assim, acima da linha n aqui no aviso de fundo há n log vezes de n, e vamos ver o que isso significa antes de tempo. Acima disso é n ao quadrado, e não vimos quaisquer algoritmos n ao quadrado ainda, mas estamos prestes a. E que se parece muito ruim. Há 2 ao n, algo exponencial, que se sente ainda pior. E, no entanto, curiosamente, então não há n cubos, que se você é uma espécie de pensar à frente, se você gosta de fazer as contas, 2 para o n torna-se realmente muito mais reta, muito mais alto do que n ao cubo se você olhar para os eixos longe o suficiente. Então, observe agora estes eixos são arbitrariamente 2-10 no eixo x. E o que isso significa? Isso significa que duas pessoas a 10 pessoas na sala. Isso é tudo meio x: tamanho do problema, qualquer que seja o contexto é. E um eixo vertical agora é o número de segundos ou número de etapas - alguma unidade de tempo. Mas note que é 0 a 60 e 0 a 10. Mas, se o tipo de zoom, como você pode no Excel ou algum software de gráficos, e vamos para 200.000, perceber que algo como 2 para o n vai dominar completamente os tempos de execução de n ao quadrado, n cubos, n log n - tudo o que já falei sobre até agora. E, no entanto o problema é quando você começa a falar sobre coisas como o Facebook onde você tem muitas, muitas, muitas pessoas todos interligados, você tiver n pessoas, cada um dos quais pode ter quantos amigos n se todo mundo é uma espécie de amigo-amigo no mundo, bem, isso é n vezes n já, portanto, que é n ao quadrado amizades possíveis, pelo menos em um sentido, n quadrados amizades possíveis. Então, que já sugere que a procura gráfico social Facebook, por assim dizer, pode começar a ser expressas nestes tipos de fórmulas. Nós vamos voltar e fazer isso muito mais concreto, mas, por enquanto, o objetivo para as próximas semanas muitos vai ter a certeza de não ir sobre algoritmos de execução ou de código que acabam tendo tempo tanto quanto algo como isto. Mas a coisa fascinante sobre ciência da computação, se você continuar neste campo tendo aulas de como CS121, CS124, ambos são cursos de teoria, é que há realmente alguns problemas que existem neste mundo que, fundamentalmente, tanto quanto sabemos, não pode ser resolvido mais rápido que o pior de estes gráficos realmente sugere. Portanto, há uma série de problemas em aberto neste mundo para fazer muito melhor do que os seres humanos têm, até agora. Então, vamos começar então com este exemplo. Vimos Sean luta com esta câmera, muito sem jeito em vídeo. Mas a realidade era quando Sean foi encarregado de encontrar em uma placa como esta o número 7, lembro que eu disse que, "Não há em algum lugar atrás desses pedaços de papel ou portas brancas "O número 7. Sean, encontrá-lo para nós." E foi maravilhosamente estranho para assistir porque ele estava realmente lutando com este problema. Mas a realidade era Sean fez tão bem quanto qualquer pessoa no quarto poderia ter feito. Ele demorou um pouco mais do que uma pessoa comum pode ter, mas ele assumiu que havia algum truque para este problema, ele assumiu que estava faltando alguma coisa. E não ajuda que centenas de olhos estavam caindo sobre ele. Mas a realidade era se a entrada para o problema é um monte de números aleatórios e você está sendo solicitado para encontrar um número tal, o melhor que você pode fazer é pesquisa linear. Comece à esquerda, mover para a direita, ou começar à direita, mover para a esquerda. Retroativamente, podemos estar pensando: "Sean, por que não você acabou de começar do outro lado?" Bem, 7 poderia ter sido facilmente aqui de forma aleatória, mas eu deliberadamente colocá-lo lá, porque eu percebi que ele não vai começar no final. Então eu meio que manipulou a situação, mas por acaso 7 poderia ter sido em qualquer lugar. Assim, a partir da extremidade direita poderia ter sido melhor, então, mas e se o ano que vem eu mover 7 em outro lugar? Isso não é uma solução fundamentalmente nova para o problema - a partir de um fim ou o outro - quando você está dada há outras hipóteses. Então Sean começou a olhar através dos números e ele disse, "5. Isso não é aqui." Então ele foi aqui e vi 19, então ele parou por cerca de 20 segundos, em seguida, ele abriu isto para 13, e, em seguida, tornou-se evidente que não parece ser um padrão aqui. Não era de 1, 2, 3, 4 ou semelhante. Houve falhas nos números, o que não ajuda. E também, o fato de que eu usei essas peças baratas de papel para cobrir os números na verdade é deliberada, porque se eu removidos todos estes pedaços de papel, a maioria de nós, Sean incluído, provavelmente teria olhou tipo de macroscopicamente na lousa e disse: "Ah, é, obviamente, 7 ali mesmo." Fizemo-lo instantaneamente. E isso pode ser o modo como o cérebro humano funciona, em certa medida, mas, na realidade, os olhos ou mente provavelmente foi deslizando os números da direita para a esquerda, esquerda para a direita, meio para fora - algo estava acontecendo fisiologicamente de tal forma que parecia que estava a acontecer instantaneamente, mas as probabilidades são mesmo internamente havia algum tipo de metodologia para encontrar 7. E, de fato, agora que estamos a falar de matrizes e estruturas de dados e dentro da memória de um computador, a única coisa que nós humanos podemos fazer é olhar para locais de memória individuais 1 de cada vez. Assim, cada outro local poderia muito bem ser coberto com algum pedaço de papel porque não podemos vê-lo de qualquer maneira. Nós só podemos fazer uma coisa de cada vez. Portanto, neste caso, no caso de Sean, fomos aqui e depois fomos aqui e depois fomos aqui, aqui, aqui, aqui, tem esperto até o final e apenas uma espécie de pular esta uma forma arbitrária e encontrou sete lá. Este não foi particularmente especial. Ele também estava fora de ordem. Mas ele finalmente encontrou 7. Mas agora o takeaway realmente é o melhor que você pode fazer quando dada nenhuma informação outro do que os números aleatoriamente ordenados é começar a partir da esquerda ou iniciar a partir da direita. Ou Parreira, você pode aleatoriamente abrir portas, mas, mesmo assim, o que significa ser aleatório? Bem, nós teríamos que de alguma forma formalizar o que significa começar aqui, então aqui, então aqui. Sean foi muito bem, e foi muito divertido de assistir. E se em vez disso, alterar o problema um pouco e trazer Sean deste ano, se você vai? Ninguém seria confortável chegando no palco e resolver um problema um pouco diferente e aparecer na câmera? Vamos além da orquestra porque vocês têm sido bastante envolvido hoje já. Como cerca de rosa, no chapéu? Vamos para baixo. Qual é o seu nome? >> Alex. >> Alex. Okay. Então Alex será Sean deste ano e irá aparecer nos próximos anos no valor de CS50 palestras. Alex, prazer em conhecê-lo. >> Prazer em conhecê-lo também. O desafio na mão para você é que você tem um pouco mais fácil em que eu estou dizendo a você os mesmos números estão aqui, mas eles já estão classificados. Então agora o seu objetivo é encontrar o número 7. E, na verdade, devemos realmente fazer isso - você é o tipo de trapaça, como um computador não iria, olhando o que os números foram um momento atrás. Com giz isso realmente não vai ajudar tanto assim, mas vamos fingir que você não sabe o que é a matriz original. Tudo o que sei agora é que você tem um conjunto de números classificados que pode ter diferenças entre eles, e seu objetivo é encontrar o número 7. Como você, um ser humano razoável ser, vai encontrar o número 7? Vá de alto a baixo? Ok >>. Ir alto a baixo. E não rasgá-los fora. Vamos apenas levantá-los para que possamos reutilizá-los. Ok, então 1. Esperar. Antes de continuar, que foi de 1, claramente errado. Então o que está passando pela sua cabeça agora? Qual é o seu próximo passo? O próximo. Ok >>. O próximo. Bom. 3, de forma incorrecta. Qual é o seu próximo passo? Continue indo. >> Tudo bem. Continue indo. 5. Então continue indo, e deixe-me entregar-lhe isto para a posteridade. 7. Excelente >>. Muito bom. Encontrado o número 7. [Aplausos] Então, o que foi bom, mas Sean também encontrou o número 7. E eu argumentar que você não tenha realmente explorar essa informação adicional, o que é que estes números são classificados. Então, podemos fazer melhor? Todas as sugestões aqui? Sim, na parte de trás. [Aluno] Pesquisa binária. >> Eu não tenho nenhuma idéia do que busca binária é. [Aluno] Comece no meio. >> Comece no meio. Okay. Então, vamos ver se conseguimos chegar lá. Portanto, se em vez você disse início a partir do meio, vá em frente e abrir a porta do meio. Há 8 deles, então você vai ter que escolher arbitrariamente a um ligeiramente para a esquerda ou para a direita. Okay. 7! [Aplausos] Muito bom. Ok, mas onde estávamos indo com isso? Vamos supor apenas para quebrar o laço que você começou aqui porque que igualmente poderia ter acontecido também. Nós só passou a saber que 7 estava lá. Portanto, este é 13. Então, se eles estão classificados e nós apenas começamos no meio, qual seria o movimento ideal próximo ter sido? Vá à esquerda. E aqui vem o exemplo do livro de telefone de novo. Se 13 é aqui e nós sabemos que a lista é ordenada, então todos estes pedaços de papel são desinteressantes para nós agora porque já sabemos que 7 deve estar à esquerda Se esses números forem classificados e encontramos 13. Então, qual é o seu próximo passo aqui? >> Vá para a esquerda. >> Ok, bom. Então, vá para a esquerda, e - espera, hey, hey, hey. Isso é trapaça. Então você encontrou sete, mas o que foi o algoritmo que apenas aplicado? Comece no meio. >> Boa. Então, qual é a extensão lógica de que a mesma idéia? Oh, por apenas estes. >> Exatamente. >> Então eu começar aqui. >> Boa. Então, agora nós fomos um pouco para a esquerda novamente. É 3. Mas o takeaway interessante agora é qual deles você não tem que se preocupar? Estes 2. Estes >> 2. Então, agora este pode ir embora, este pode ir embora. Agora, o problema que foi de 8 em seguida, foi de 4 tamanho agora é o tamanho 2. Estamos ficando muito perto. Mais uma vez, ir para o meio desses dois elementos. Okay. Então é tipo de pena que agora nós estamos sempre indo embora porque estamos arredondamento para baixo. Mas isso é bom, porque agora nós jogar isso fora e tudo mais, deixando-nos com apenas 7. Vamos dar uma salva de palmas. Encontramos 7 novamente. [Aplausos] Okay. Claro. Segurem-se por apenas um segundo mais. Mesmo que esse tipo de processo seguinte demorou um pouco mais do que nós sentimos que seria, francamente, seus primeiros instintos eram os melhores, certo? Encontramos 7 instantaneamente. Mas teríamos encontrado 7 mais rápido, não importa o que, neste exemplo, contra este porque se os números são todos os classificados, assim como as páginas de um livro de telefone, você pode realmente cortar a metade do problema de novo e de novo e de novo. E não é tão fácil de ver isso com apenas oito números em oposição a uma lista telefônica de 1.000 páginas onde você realmente vê-lo visualmente, mas neste caso aqui quando Sean estava à procura de 7, quantos passos no pior caso teria que ter tomado ele? >> [Aluno] 7. 7, no pior caso. Bem, no pior caso, não se há 7 8 portas aqui. Ele teria levado oito etapas. Portanto, se há portas n, ele poderia ter tomado Sean alguns anos atrás n passos. Agora, no seu caso, Alex, dado que estes números são classificados - e podemos inferir tipo de presente, de onde temos sido até agora nesta história - o que é o tempo de execução do algoritmo mais inteligente de Alex de partir ao meio e depois repetir? [Estudante] 3. >> Por isso, vai ser 3, a grosso modo, se você passar de 8 para 4 a 2 a 1. Então 3 etapas ou, mais geralmente, isso é log n novamente. Toda vez que você está reduzir pela metade e reduzir para metade e reduzir para metade e reduzir para metade, que é uma expressão dessa idéia de log n. E assim que teria levado apenas 3 passos, e de fato o fez uma vez que abriu as portas para metade e reduzir para metade, Considerando que este teria tomado Sean cerca de 7 ou 8 passos. Então, obrigado por estarem conosco neste ano. >> Obrigado. Prazer conhecê-lo. Obrigado a Alex. Da mesma forma >>. [Aplausos] Qual é então a implicação real disto? Agora imagine que não é 8 portas, o que, francamente, todos nós poderia encontrar algo 8 portas por trás muito rapidamente apenas por rasgando os pedaços de papel e indo com nossos instintos. Mas o que se é de um milhão de portas? E se for 4000000000 portas? No caso de 4 bilhões de portas, você realmente vai querer ir com o algoritmo de Alex, binária de pesquisa como nós vamos começar a chamar ele ou dividir e conquistar, mais geralmente, onde você guarda reduzir para metade e reduzir para metade o problema, porque se você tem 4000 milhões portas, quantas vezes você pode cortar 4.000 milhões na metade? [Aluno] 32. >> É realmente 32. Você pode resolver isso em um pedaço de papel ou em sua cabeça. Você vai 4.000-2.000 milhões to 1 bilhão para meio bilhão, para 250 milhões, ponto, ponto, ponto. E se você fizer a matemática, você vai realmente obter 32, e que, na verdade, diz respeito à ciência da computação porque geralmente contar em potências de 2. 2 ao 32 passa a ser 4 bilhões. Portanto, há um monte de relevância para estes tipos de potências de 2 em ciência da computação. Mas o que cerca de 8 bilhões? Quantos passos é que vai levar se há 8000 milhões portas? [Aluno] 33. Então >> 33. O que se há 16.000 milhões portas? Quantos passos é que vai levar? [Estudante] 34. >> 34. Poderíamos continuar este tipo de ad nauseam. Mas isso é uma coisa poderosa. Você pode introduzir bilhões de mais insumos para o seu problema, mas não é grande coisa, você tomar apenas uma mordida adicional de fora e, assim, dá-nos algo como busca binária ou dividir e conquistar, mais geral. Mas eu sou o tipo de batota aqui, certo? No caso do algoritmo de Alex, ela teve uma vantagem sobre Sean. Ela sabia que esses números foram classificados, mas Alex não tem que resolver-los sozinha. I antes veio até a lousa e meio que fiz certo que eu desenhei todas elas na ordem de classificação, então cobri-los com papel. Mas como muito trabalho que isso me leva? Se tivéssemos começado com estes números em alguma ordem aparentemente aleatória - neste caso mais simples, estes números de 1 a 8 aqui - como é que vamos classificar esses valores? Se você fosse um ser humano dado esta tarefa, que tipo de abordagem intuitiva você tomaria a ordenação de um monte de números? Essas coisas foram dispostos como peças do puzzle. Sim. [Aluno] Gostaria de ter cada número e compará-lo com cada um e continue indo para a esquerda. >> Ok, bom. Portanto, tome cada número, compará-lo com o próximo a ele, e depois é só manter em movimento ao longo da lista, tipo de rejiggering coisas que você vá. Portanto, temos aqui uma oportunidade para talvez um pouco mais as pessoas a se envolver. Nós temos 8 mais voluntários que gostariam de vir para cima? Um pouco menos de pressão desde que você não é o único. 1, 2, 3, 4, 5, 6, 7, 8. Vamos para baixo. Vocês vão ser os números de 1 a 8. Vamos ver se não podemos fazer essa classificação para Alex muito da mesma forma que eu fiz isso com antecedência. 1, 2, 3, 4. Vá em frente e se você, se alinham no palco entre o suporte de música e eu aqui na mesma ordem em que o diapositivo no ecrã. Uh-oh. Nós vamos trabalhar para que o próximo exemplo. Oh, espere, espere. Aqui vamos nós. Esperar. O exemplo seguinte é agora. Aqui você vai. Número 8. Vamos para cima. Tudo bem. Ordenar-vos de acordo com isso. Deslize um pouco para o lado da música estar aqui. Portanto, temos 4, 2, 6 - chegar lá, aqui, ali mesmo - 3. Sim. Okay. Você vai por aqui. Não, você fica lá. Sim, isso mesmo. Não. Eu estou errado. Bem ali. Ok, muito bom. Okay. Então agora vamos classificá-los em ordem crescente. Como posso fazer sobre isso? O algoritmo que foi proposto há pouco foi por isso que nós não apenas comparar as pessoas que são do tipo ao lado do outro e, em seguida, corrigir os erros, da esquerda para a direita. Portanto, temos aqui 4 e 2, obviamente, fora de ordem. Vamos trocar você. Okay. Então, agora eu vou fazer a fila andar. 4 e 6, nope. [Risos] 6 e 8, muito bom. 8 e 1, deixe-me trocar de vocês. Tudo bem. Então, 8 e 3, troque vocês. 8 e 7, deixe-me trocar de vocês. 5 e 8, excelente. Eu dar-lhe uma lista ordenada. Tudo bem. Portanto, não é bem assim. Mas é melhor porque os números maiores - caso em ponto 8 - ter tipo de borbulhava da esquerda para a direita. Então, eu tenho um direito deles, mas parece que este não chegou a resolver o problema. Então, o que você propõe que fazer a seguir? >> [Aluno] continuar fazendo isso. Nós >> continuar fazendo isso. E perceber, mais uma vez, vamos definir as coisas apenas por ter todos os humanos tipo de inteligência se organizam com base nessa imagem, mas agora temos de ser muito mais metódico. Temos que ser algorítmica sobre isso como se estamos escrevendo código - neste caso pseudocódigo verbal. Então deixe-me tentar novamente. Isso funcionou muito bem. Ele não resolvê-lo. Mas quando se duvidar, tente e tente novamente. Então, 2 e 4, não ajuda mais. 4 e 6. Ah! 6 e 1, um pouco melhor agora. 6 e 3, bom. 6 e 7, 7 e 5, 7 e 8, bom. E você sabe, eu provavelmente pode ignorar 8 agora, porque ele está no final da lista. Talvez a gente não tem que se preocupar com alguém que vai passar por ele. Mas vamos ver se isso é uma suposição segura. Agora lista é - maldito - não classificados. Vamos tentar de novo. Então, 2 e 4, 4 e 1, 4 e 3. 4 e 6, que bom. 6 e 5, bons. 6, 7, e 8, bem. Mas aviso, eu posso parar por aqui agora e parar por aqui agora? [Estudante] Sim. >> Sim? E se um de vocês foi o número 9 por todo o caminho até lá? Teria sido classificados. >> Boa. Teria sido classificados na primeira vez. Bom. Então, vamos voltar novamente. Estamos quase lá. 1 e 2, 2 e 3, 3 e 4, 4 e 5, 5 e 6, 6 e 7, 7 e 8. Eu sou feito agora, mas, novamente, eu sou um computador que só pode fazer o que me mandam fazer, e minha lembrança só agora é que eu realmente só fiz um pouco de trabalho. Alguma coisa mudou aqui. Então eu não tenho tecnicamente confirmada visualmente ou através de algoritmos que esta lista é de fato classificados. Portanto, apenas para uma boa medida, apenas para ser anal sobre isso, vamos fazer desta vez uma mais. Então, 1 e 2, 2 e 3, 3 e 4. E você sabe o que? Só para completar, eu vou manter o controle sobre a minha mão neste momento quantos swaps faço apenas para que eu saiba o quanto o trabalho que eu realmente feito. 3 e 4, 4 e 5, 5 e 6, 6 e 7, 7 e 8. Nenhum dos swaps. Então agora eu seria legitimamente ser um idiota para fazer isso de novo porque se eu não trabalhava com esta passagem dos seres humanos, então é claro que isso vai acontecer de novo se nenhum deles é uma espécie de forma aleatória adversarially movendo-se em torno. Então agora eu posso parar. Agora vamos fazer a pergunta, quanto trabalho é que isso realmente me levar? Quantos passos que levar? N >> quadrado. Sim, por isso n ao quadrado. Quando você começa a partir de n ao quadrado? Você tem que verificar cada num - Há n números, e você tem que verificar cada número com os números de n outros. Bom. >> Então é n ao quadrado. >> Boa. Então ele se sente como ele poderia muito bem ser n ao quadrado, certo? Tem n desses caras, 8, especificamente neste caso, mas cada vez que eu passei por essa lista eu estava comparando o primeiro contra o segundo, o segundo contra o terceiro de novo e de novo e de novo, e quando cheguei ao final, o que foi que eu fiz? I refez-lo. Então, se generalizar esta explicação, temos n pessoas e eu estou fazendo, obviamente, 8 etapas, n passos, cada vez que eu passar por este algoritmo. Mas quantas vezes no pior caso que eu tenho que passar por essa lista de pessoas? [Estudante] N vezes. Provavelmente >> n, direito, porque na pior das hipóteses, o que é provavelmente o arranjo pior caso desses caras a partir do get-go? Se eles estão completamente revertida fim porque apenas supor mentalmente, vamos - Qual é o seu nome? >> Bowen. Bowen. Okay. Então Bowen, vem aqui só por um momento. Suponha-se que foi aqui Bowen, no início do algoritmo, e não sabemos o que todo mundo é, mas aqui Bowen, de acordo com este algoritmo - e se você quiser apenas passear comigo - vai borbulhar, como fez da primeira vez, todo o caminho até o final. Mas suponha que a próxima pessoa a Bowen foi o número 7. Eu tenho que voltar e pegar o número 7, o que significa que eu tenho que ir todo o caminho de volta aqui. Agora eu tenho que ter esse passeio mesmo com a pessoa que é o número 7. Mas e se, em seguida, o número 6 era ao lado dele também? Então eu tenho que voltar e 6. Então, novamente, a cada iteração deste laço que eu estou falando a cada um dos n pessoas, e eu poderia ter de fazer n destes passeios para ter certeza que eu estou puxando todos os grandes elementos de volta e volta e volta para o fim da lista. Coisas que n n vezes é apenas n vezes n ou n ao quadrado. Então, aqui já temos um algoritmo que não está mais n, que não é mais log n, na verdade é pior do que qualquer coisa que já fizemos antes. Então Alex tipo de sorte em que eu fiz todo o trabalho aparentemente frente para ela, todo o trabalho caro, para que ela pudesse desfrutar deste algoritmo de busca binária, que é de n log. Mas isso é consistente com o tema segunda-feira. Nós deu um pouco mais espaço, utilizou-se mais bits, a fim de acelerar o tempo de execução. Tanto como há este trade-off entre tempo e espaço, lá também pode ser apenas trade-offs entre o tempo gasto até espécie frente de fazer as coisas pronto para ir e, na verdade, a execução de um algoritmo como pesquisa. Vamos tentar outro. Se vocês não se importaria apenas rapidamente reorganizar-se para corresponder ao novo, vamos tentar algo um pouco diferente, onde não é tão simples como apenas corrigir todos os erros de pares, que é super intuitivo. Vamos, em vez ser um pouco mais deliberada e fazer isso. Este também eu gostaria de propor é, provavelmente, bastante intuitivo. Vamos selecionar a menor pessoa da lista de novo e de novo. Então, vamos lá. 4, você é a menor pessoa que eu vi até agora, portanto, então eu vou mentalmente lembrar que por apenas apontando para você agora. 2. Ooh! Esqueça número 4. Eu só encontrei o menor elemento novo nesta lista. Eu vou tipo de lembrar disso. 6, 8. Ooh! 1. Tchau. Então agora eu vou me lembrar o número 1. Sabemos que 1 é o menor, mas eu sou o computador. E se há um 0? E se há uma -1? Eu tenho que continuar. Assim, 3, 7, 5, nope. Okay. Assim, o número 1 era o menor. Deixe-me escolher você da lista - nós ir por este caminho - e colocá-lo arbitrariamente no início da lista. Agora, espere um minuto. Eu meio que enganado. Se esses caras não representam uma lista de oito pessoas, mas uma matriz, 8 pedaços de memória contígua - você se importa recuar por um momento? Há, na verdade, não há espaço para você aqui. Então, como vamos dar espaço para - o que é o seu nome? >> Sammy. >> Sammy. Como podemos dar espaço para Sammy? Nós mover os n que estão diante de mim. Ok >>. Assim nós poderíamos mover os n pessoas que estão diante dele, por isso, se vocês querem tomar um passo, deliberada dramática para a esquerda. Eles todos fizeram isso em uníssono, mas a última vez que eu escrevi algum código, você não pode classificar de mover muitas coisas de uma só vez. Poderíamos fazê-lo em um loop, uma vez em movimento todos de uma vez. Então, se vocês não se importaria de recuar para a direita, e Sammy, se você pudesse voltar atrás, porque ainda não há um espaço para você, agora vamos fazer isso. Onde estava Sammy um momento atrás? Bem ali. Portanto, há uma diferença aí. Então você pode mover-se em local de Sammy. Agora a próxima pessoa e agora a próxima pessoa, agora próxima pessoa. Agora nós temos espaço para Sammy. Agora, alguém, do público - o que era bom, que era correto, Senti um pouco demorado - o que é mais rápido? Sim. [Estudante] Uma matriz de novo? >> O que é isso? >> [Estudante] Uma matriz de novo? >> Ok, bom. Assim, de acordo com o tema de apenas trade-offs, por que não queria apenas fazer uma nova matriz  e depois Sammy estará nadando no espaço em frente dessas pessoas, por exemplo, e nós podemos apenas começar a preencher uma nova matriz completamente. Isso também iria trabalhar. Mas eu não estou interessado em gastar mais espaço hoje. O que é outra abordagem? [Aluno] Swap. Ok >>. Nós poderíamos apenas trocar esses dois caras. Qual é o seu nome? Mario. >> Mario. Então Mario, que estava atualmente aqui. Sammy, você pode fazer o backup apenas por um momento? Mario estava aqui. Não temos espaço para mais de você, então se você não se importaria de ir para onde Sammy é, vamos colocar Sammy aqui, e agora eu diria que a operação troca de Sammy era muito mais rápido. Nós fizemos uma operação para trocar esses caras, ou talvez dois a trocar estes caras, mas nós não fizemos 1, 2, 3, 4, de modo que se sente melhor. Agora, espere um minuto. Eu meio que tornou o problema pior, porque o número 4 era uma espécie de perto o início. Agora o número 4 é um pouco mais perto para o efeito, mas eu realmente não sabe nem quer saber disso. Então, este é apenas má sorte que o número 4 é um pouco mais longe de seu lugar destinado. Então, vamos agora repetir este algoritmo. Para recapitular, desde que a história foi, tudo o que fez foi percorrer a lista procurando o menor pessoa numerados. Então agora vamos fazê-lo novamente. Nós não temos que se preocupar com Sammy mais. Nós podemos apenas ir aqui. Ooh! Número 2. Esse é um número muito pequeno. 6, 8, 4, 3, 7, 5. Ok, bom. E, felizmente, por coincidência, eu não tenho para mover - >> Willie. Willie porque ele está em seu lugar agora. Vamos fazer isso de novo e de ignorar esses dois caras. 6. Esse é um número muito pequeno. Ooh! 8 é definitivamente maior. 4. Vamos nos concentrar no 4. Ooh! 3 é melhor ainda. 7 e 5. Então, o que vamos fazer agora com - >> Roger. >> Roger? Vamos trocar-lo com o número 6. Então, se 6 e 3 gostaria de trocar, temos agora chegado tipo de sorte em que 6 é mais perto de onde ela deveria estar, mas é apenas uma coincidência aqui. Então, vamos agora aqui. 8 é um número muito pequeno. Ooh! 4 é menor. 6, 7, 5. O que nós fazemos agora? Trocando. >> >> Exatamente. Então agora vamos fazer esse tipo de rápido. 8, 6, 7, 5. Onde é que 5 ir? Bom. Okay. 6, 7, 8. 6 começa a ficar onde está. Qual é o seu nome? >> Rosalie. Rosalie começa a ficar onde está. 7 chega a - Vamos ver. 7, 8. Okay. Então, 7 começa a ficar onde está. Qual é o seu nome? Amna >>. Amna >>. Então Amna começa a ficar onde está, e número 8 já está onde agora deve ser. Ok, bom. Parece que estamos apenas a criação de trabalho para nós aqui, no entanto. O que é, finalmente, o tempo de execução deste algoritmo? Se pensarmos que essas pessoas não como 8, mas como n? É >> n. É n passos, mas estamos verificando a cada momento. Okay. N, mas você está verificando a cada momento? Ok, mas se for n passos, eu não deveria ter sido capaz de resolver por você só vai 1, 2, 3, 4? Oh! Ok, isso é uma grande diferença. Então n ao quadrado por quê? O que está realmente acontecendo? Há n pessoas na lista, mas para encontrar a menor pessoa na lista no pior caso, quantos passos que eu tenho que tomar? >> N. N, certo, porque no pior caso, o número 1 é todo o caminho até lá, então eu tenho que ir buscá-lo ou ela. E então, quando eu finalmente percebi um era o menor, então é muito rápido para trocá-los. Mas agora eu tenho que começar do início e olhar para quem? A pessoa próximo menor, o que é de 2. Onde, no pior caso é 2? Oh, meu Deus. É tudo até aqui no final. Então agora eu acabei de fazer mais n passos, mais passos n. E se temos n pessoas e, no pior caso, a pessoa é menor n passos de distância, que é novamente n vezes n, e assim temos novamente n ao quadrado. Isso não está se sentindo tão bem. E, de fato, mesmo no melhor dos casos - supor que eles começam classificados - quantos passos são necessários para mim usando este algoritmo para resolver essas pessoas n? N ao quadrado. >> Ouvi n ao quadrado. Por que n ao quadrado? Porque você ainda tem que verificar a cada momento. Sim >>. E você tem que trocá-los. >> Mesmo que nós, seres humanos são uma espécie de onisciente no sentido visualmente que podemos apenas um tipo de ver que este é classificado, um computador que não é inteligente. Ele vai ficar aqui e aqui e aqui, mas se o que ele está procurando é o menor elemento, você só sabe que você encontrou o menor elemento pelo que ponto? Uma vez que você está no fim. Mas em que ponto você só encontrou o menor elemento atualmente. Você não precisa necessariamente saber mais alguma coisa sobre o estado do mundo. Então você tem que ir de novo e de novo e de novo. Então desta vez eu realmente parece idiota, porque eu estou verificando, ok, dois, você é o menor, mas eu não sei o que, no total ainda. 3, 4, 5, 6, 7, 8. Ok, bom. 2 era realmente menor. Agora vamos encontrar o menor seguinte. Okay. 3, você é atualmente o menor. Vamos ver. 4, 5, 6, 7, 8. Ok, teve sorte novamente. 3 era de fato no lugar certo. Mas eu vou continuar fazendo isso de novo e de novo e de novo. Como podemos fazer muito ligeiramente melhor? Em vez de ter bolha pessoas se pairwise do menor para o maior e em vez de ir e vir através da lista de selecionar a pessoa menor, em seguida, por que não, em vez inserir essas pessoas em uma etapa nova lista a passo? Vamos tentar isso. Agora deixe-me chamar este tipo de inserção coisa. Então aqui estamos nós aqui. Número 1. Eu não me importo com ninguém nesta lista. Meu objetivo agora é colocar o número 1 no início de uma lista ordenada. E eu vou propor pois tenho apenas 8 pedaços de memória, arbitrariamente agora eu sou o muro entre minha lista supostamente não classificado, e quem está atrás de mim eu vou reclamar está classificada. Portanto, agora temos o número 1. Quero inserir-lo em minha lista de classificados, então eu só vou mudar a minha parede aqui, e agora eu reclamar esta lista é ordenada, esta lista não estão classificados - pelo menos até onde eu sei. Eu não consigo ver todos os números de uma só vez. Agora acontece que eu encontrar o número 2. O que eu faço com ele? Eu inserir agora para a lista de classificados. Mas observe como foi fácil. Eu só tenho que olhar. O número 1 é ali. Oh, obviamente 2 vai para o lado do número 1. Agora, o que eu faço com 3? Eu insira na lista de classificados. Mas isso foi super fácil. Isso é super fácil, este é super fácil, é super fácil, super fácil, super fácil. E agora tudo é classificada atrás de mim, e quantos passos tinha que tomar? [Estudantes] N. >> Portanto, é apenas o n. Temos sorte. Foi só por isso que n? >> [Aluno] Como a lista foi classificada. A lista já está classificado. Então, tivemos sorte. Mas nós projetamos um algoritmo este tempo que aproveita esse tipo de sorte, que melhor cenário, por não perder tempo desnecessário. Assim, temos agora o que nós vamos chamar os tipos de bolha onde as pessoas espécie de bolha-se em pares. Nós agora temos um tipo de seleção em que arrancar a menor pessoa de novo e de novo. E agora nós temos um tipo de inserção em que tipo de proativamente colocar as pessoas onde elas pertencem em uma lista cada vez classificados. Se pudéssemos, uma salva de palmas para esses caras aqui. [Aplausos] Vamos dar o nosso intervalo de 5 minutos aqui. E quando voltar, vamos explodir todos estes algoritmos para fora da água com algo melhor. Tudo bem. Muito obrigado. Você pode manter as como lembranças. Tudo bem. Estamos de volta. E para recapitular muito rápido, tivemos três dessas abordagens diferentes para classificação, todo o ponto de que era para chegar ao ponto em que alguém como o Alex poderia procurar uma lista de números mais rápido do que alguém como Sean podia. E embora tenhamos esses exemplos simples com 8 números, você poderia extrapolar facilmente a 8 páginas, 8 bilhões de páginas da web, ou 800 milhões de amigos no Facebook. Então, esses algoritmos podem certamente escalar para esses tipos de valores, e as idéias são, em última análise o mesmo. Então espécie de bolha foi o primeiro em que tipo de borbulhava a maior pessoa todo o caminho à direita, trocando as pessoas em pares. Então nós tivemos que chamaremos tipo de seleção, onde eu um pouco mais deliberadamente ficou olhando através da lista, selecionando o menor número de novo e de novo e de novo, o resultado lógico de que é que a lista é finalmente classificados. Em seguida, na terceira, eu inseri as pessoas em seu lugar apropriado, e fizemos um exemplo muito artificial em que a lista já estava classificado, mas que era para enviar a mensagem de que no caso do tipo de inserção, você pode ter sorte. Se os números já estão classificados, só vai te levar n passos para confirmar tanto, enquanto que tipo de seleção que você é a visão de túnel um pouco mais e não se dão conta de que a lista já está classificado. Então vamos ver espécie de bolha em ação aqui. No exemplo a seguir, estamos prestes a ver barras verticais cujas alturas representam números para que possamos classificar de classificação visualize acontecer. Quanto menor for a barra, quanto menor o número, maior a barra, maior o número. E nós vamos jogar a esta velocidade padrão. Ele vai se mover um pouco rápido para agora, mas o vermelho é o que está mostrando 2 barras sendo comparados lado a lado. E se você observar atentamente, o que acontece é que, se os bares estão fora de ordem, o menor, é movido para a esquerda, o maior um para a direita, e então você continuar avançando. Então, se nós fazer isso de novo e de novo, perceber que as menores bares vão continuar avançando seu caminho para a esquerda e os maiores bares vão continuar avançando seu caminho para a direita. E, de fato, nós estamos começando a ver um padrão de todo o caminho no lado direito como vimos 8 e depois, eventualmente, 7 borbulhando até o final da nossa lista de humano. Então, isso vai muito rapidamente um pouco tediosa, então deixe-me parar por um momento. Deixe-me mudar a velocidade para ser muito mais rápido. Eu não vou mudar o algoritmo, eu estou apenas fazendo a animação acontecer mais rápido. Ainda espécie de bolha, mesmo algoritmo, mas agora você pode ver muito mais rápido do que a nossa manifestação verbal que os maiores elementos são de fato borbulhando para cima. Como um aparte, certo estes pequenos quadrados na parte inferior esquerda e fundo são apenas pequenos lembretes quanto ao número de comparações que estão fazendo. Mas, por agora, podemos nos concentrar na pirâmide que está tomando forma, e lá vai ele. O menor elemento é do lado esquerdo, o maior do lado direito, e tudo o mais entre eles. Agora vamos dar uma olhada em vez de tipo de seleção. Eu estou indo para ir em frente e bateu Stop. Nós estamos indo para obter um novo conjunto aleatório de bares. Tipo de seleção, recall, passa a lista de novo e de novo e de novo, arrancando o menor elemento. Então aqui é uma espécie de seleção. Parece que há trabalho de menos acontecendo agora porque não estamos comparando pairwise mas estamos apenas uma espécie de cereja escolher os menores elementos da direita para a esquerda. Que teve muito pouco tempo, então não há uma dicotomia já. Só porque um algoritmo é dito para ter n tempo ao quadrado, como espécie de bolha e como tipo de seleção, esses são realmente vezes pior caso de funcionamento. Por exemplo, no caso de, digamos, uma espécie de seleção, Na verdade, eu estou selecionando a menor pessoa e colocando-lhe aqui, então eu vou fazer isso de novo, então eu estou fazendo isso de novo, mas houve uma otimização leve que eu poderia fazer. Assim que me mudei número 1 aqui - Sammy nesse caso - o que eu preciso fazer com ele depois? >> [Aluno] Deixe-o. Deixá-lo, certo? Nada. Eu não preciso de sempre falar com Sammy novamente, porque se eu tivesse escolhido o menor elemento e colocá-lo aqui, por que perder tempo indo até o final da minha lista inteira? Na próxima iteração, deixe-me realmente se mover apenas para o número 2, apenas para o número 3. Então, na realidade, eu não estava fazendo as coisas n n vezes. Eu estava fazendo coisas n, então n - 1 coisas, então n - 2 coisas, então n - 3 coisas, então n - 4, ponto, ponto, ponto. Nós temos um pouco de uma série geométrica, o que significa apenas você está adicionando-se os números cada vez menores. Não n + n + n + n, mas n + 7 + 6 + 5 + 4 + 3 + 2 + 1. E o que geralmente trabalha-se - Eu vou estragar minha placa aqui apenas por um momento - que vai trabalhar fora para ser algo como n (n - 1) / 2 se apenas um tipo de olhar para a parte de trás de um livro de matemática, onde tem todos os cábulas para as fórmulas. Se você está apenas acrescentando algo n + n - 1 + n - 2, trabalha para ser algo como isto. E se nós só tipo de multiplicar isso, que é n ao quadrado menos n / 2. Eu ficava dizendo n ao quadrado, embora, e isso é porque eu era uma espécie de tomar um atalho mental porque, na realidade, n ao quadrado menos n dividido por dois é de fato o verdadeiro número de passos que um algoritmo como tipo de seleção levaria se realmente contados todas essas comparações e todo o trabalho pouco ocupado estávamos fazendo. Mas, francamente, uma vez que n chega a ser como um milhão ou um bilhão, quem diabos se importa se você está fazendo um bilhão de menos quadrado de um bilhão, dividido por 2? Um bilhão quadrado é um número enorme. Você pode tomar outra bilhões fora dele com - n. Não é um negócio tão grande. Assim, quanto maior os números ficam, os menos importantes estes termos mais baixos ordenados são. Quem se importa se você dividir por dois, se você está falando de quatrilhões de número de passos? Assim, em geral, os cientistas da computação tendem a jogar fora tudo, mas o maior prazo, e nós apenas uma espécie de simplificar o mundo e dizer que que o algoritmo tomou medidas cerca de n ao quadrado. Esse é o tempo de execução de um algoritmo. Então, nós vamos voltar a este em apenas um momento, com alguns exemplos concretos, mas por agora, que é o tipo de motivação intuitiva atrás apenas simplificar o nosso mundo e falar sobre os termos mais importantes, em vez de entrar em todas essas fórmulas extravagantes. Então, que era uma espécie de seleção, e temos um pouco de sorte lá. Vejamos tipo de inserção. Deixe-me ir em frente e começar um presente também. Agora, observe o padrão que está acontecendo é um pouco diferente, e começamos com números aleatórios, mas se realmente contar o número de passos no pior caso, se a lista começou completamente na ordem certa, que só iria tomar n passos para realizar tanto. Mas, se a lista eram realmente para trás - por exemplo, no caso aqui - em seguida, perceber que realmente tem que fazer um trabalho muito mais neste caso. E deve espécie de sensação de que você como este é um tipo de trabalho mais difícil para obter esses elementos menores para a esquerda, e isso é porque temos sorte. A lista foi ordenada acidentalmente em sentido inverso. Por outro lado, com ordenação por inserção se imitar o que fizemos com nossos seres humanos aqui começando com todos classificados e, em seguida, começar, é um algoritmo muito bom, certo? Já está, de fato, classificados. Então, vamos tentar resumir exatamente quanto tempo essas coisas estão nos levando através da introdução de um pouco de jargão ou notação que na verdade é muito mais simples do que o tipo de fanciness sugere. Esta coisa aqui, este O grande na tela, o que é um cientista da computação geralmente usam para descrever o pior caso de tempo de execução de um algoritmo. Mais uma vez, por pior caso, é totalmente dependente do contexto. O que queremos dizer com o pior caso totalmente varia de acordo com o problema que está falando. Mas, no caso de classificação, o que é o pior cenário possível? Tudo é para trás, porque só se sente como que significa um monte de trabalho para nós. Eu anotei alguns dos algoritmos que temos visto até agora: busca linear, busca binária como com o livro de telefone ou os pedaços de papel, em seguida, classificar espécie de bolha, uma espécie de seleção, inserção e como nós vimos com nossos seres humanos, e depois um outro que está indo eventualmente ser chamado merge sort. Assim, em busca linear no pior caso, quantos passos são necessários para encontrar o número 7 se existem portas n como Sean cara? >> [Aluno] N. N. Então, nós estamos indo para escrever O grande de n. Eu só vou para preencher algumas lacunas. Esta é apenas uma grade de espaços em branco. Mas, no melhor dos casos, com busca linear, 7 poderia ter sido logo no início da lista, Sean e pode ter iniciado a olhar para o início da lista. Então, se você está usando a pesquisa linear e apenas verificando esquerda para a direita ou talvez direita para a esquerda - eles são equivalentes - na melhor das hipóteses quantos passos poderia busca linear, como algoritmo de Sean, tomar? Apenas o passo 1. Então, eu vou dizer que é a notação ômega. Este é apenas ômega capital. Omega é apenas a maneira sexy de dizer melhor caso tempo de execução. Assim, no melhor dos casos o tempo de execução é um passo único ou um número constante de passos - 1, neste caso - mas no pior dos casos, grande O, que é, na verdade, n passos. E este aqui, theta, não estamos realmente indo olhar agora. Não é relevante a este exemplo particular. Mas agora vamos tentar de busca binária. No pior dos casos, com busca binária, quantos passos é que vai demorar para encontrar o número 7 ou o que está procurando? >> [Estudante] Log n. Ainda vai levar n log porque apenas como Alex azarão quando realmente trabalhou com o problema metodicamente e ela não encontrar o número 7 até a última porta, olhou para, mesmo que, com justiça, ela chegou a jogar fora de portas certas ao longo do caminho, busca binária no pior caso tem um tempo de execução de log n. E, novamente, que fala a este dividir e conquistar. Mas o que acontece no melhor caso? E Alex experimentou realmente que melhor caso certo quando ela surgiu no palco. Quantos passos se que levar em busca binária? >> [Aluno] 1. 1, só porque ela teve sorte. Mas isso é bom, porque se refere a cenários ômega melhor caso, melhores entradas de caso, mesmo que seja apenas aleatória sorte. Agora, isso também vamos apenas um tipo de licença em branco por enquanto. Que tal agora espécie de bolha? No pior dos casos, com espécie de bolha, todo mundo está em ordem inversa, por isso temos que fazer um monte de borbulhar. Mas quantos passos é que vai levar, no pior caso? >> [Aluno] N ao quadrado. Este foi o n ao quadrado, porque se você pensar sobre isso, se a lista é completamente para trás - 8 é aqui, 1 é aqui - como coisa começar a borbulhar, o número 8 vai se mover dessa forma, dessa maneira, Desta forma, este caminho, mas onde é o número 7 no pior caso? Aqui ela ainda está lá. Então, temos que fazer isso de novo e de novo. E é aí que temos n passos, então n - 1 passos, então n - 2 etapas. E se você tomar minha palavra para ela - que se você tipo de multiplicá-lo para fora, É de certa forma n ao quadrado no final com alguns outros termos que nós vamos simplesmente ignorar por agora - em seguida, na pior espécie de bolha caso é n ao quadrado, mais ou menos. Mas o que sobre o melhor caso com espécie de bolha? Qual é o melhor cenário possível? Todos os números são classificados já. E qual foi a heurística que usei, o truque que eu usei, a perceber que eu tinha feito nenhum trabalho e, portanto, poderia parar mais cedo? [Aluno] Confira uma vez. >> Confira uma vez. Mas o que eu estava fazendo ao longo do caminho? Eu estava mantendo o controle de quantas swaps que eu fiz. E eu percebi que se eu não contei qualquer troca nos meus dedos, então eu tenho feito nenhum trabalho. Eu certamente não deve tentar fazer nenhum trabalho novo, então eu só posso parar. Assim, no melhor dos casos de espécie de bolha quando a lista já está classificado, o que você diria a notação omega é, no melhor dos casos correr do tempo? É só ñ. Temos que fazer algum trabalho, mas só temos de fazer um passeio que vale a pena de trabalho. E aqui também vou deixar esta parte em branco. E agora espécie de seleção. Tipo de seleção tinha me arrancar a menor pessoa de novo e de novo. E o que nós dizemos que o tempo de execução do que foi? Isso foi n ao quadrado no pior caso. E, infelizmente, no melhor dos casos é também n ao quadrado porque eu não tenho o tipo de visão onisciente do mundo inteiro; Eu só sei que em cima de uma iteração completa que eu realmente encontrado a menor pessoa. Então tipo tipo de seleção de suga, nesse sentido, mas a cabeça é que é meio intuitiva. É muito fácil para codificar porque tudo que você tem a fazer é escrever um par de nested loops, tipicamente, que atravessa procurando o menor elemento e, em seguida, coloca o elemento mais pequeno que pertence ao fim da lista. Então, aqui também lá vai ser um trade-off. A quantidade de tempo que você leva para pensar e desenvolver algo realmente escrevendo código poderia muito bem levar mais tempo, se você quer um desempenho melhor e mais rápido algoritmo. Mas se você realmente apenas uma espécie de código algo se rápida e suja e apenas uma espécie de levar a idéia mais estúpida possível que você pode pensar, que pode levar alguns minutos para o código, mas com grandes conjuntos de dados seu algoritmo pode levar horas para ser executado. E mesmo que eu na faculdade, às vezes, fazer essas trocas. Seria 3:00, eu estava tentando analisar alguns muito grande conjunto de dados relacionados à pesquisa de segurança que estava fazendo, e ele foi ou gastar 5 minutos aprimorando o meu programa para analisar os dados e ir dormir ou gastar 8 horas ficando apenas direito para que ele funcione de imediato, e não ir dormir. E assim lá também é uma espécie de uma decisão consciente. Menos tempo de desenvolvimento, mais sono. Em retrospecto, eu provavelmente não deveria incentivar que quando o objetivo aqui é para otimizar a qualidade do código, mas isso também no mundo real é uma muito razoável trade-off. Menos tempo, menos desempenho ou vice-versa. Então, aqui estamos, finalmente, ter a chance de falar sobre teta. Theta notação é algo cientistas da computação pode trazer na conversa O grande quando e ômega acontecer de ser o mesmo. Você diz teta para realmente enviar a mensagem de que este é um tipo de apertado vinculado. Não importa se o cenário é bom ou ruim, é n ao quadrado. Portanto, não é apenas relevante nestas histórias aqui. Tipo de inserção é a última que olhou, onde eu estava apenas de inserir todos no lugar certo. No melhor caso, o que era o tempo de execução da ordenação por inserção, como vimos aqui? [Aluno] caso melhor? O melhor >> caso. Foi N porque no melhor dos casos todos classificados, e Sammy e mais ninguém realmente tinha que se mover. Eles já estavam em seu lugar certo. Então tipo de inserção, no melhor caso, é, neste caso, n. Mas, no pior caso é uma espécie de n ao quadrado. Por quê? Se a minha lista de seres humanos está na ordem inversa, A primeira começa com o número 8 e eu inserir ele ou ela na posição correta, que é aqui mesmo. Eu tipo de movimento para o lado. Esses caras estão sem classificação, que ele ou ela está classificada. Mas agora eu acontecer para encontrar quem vem? >> [Aluno] 7. 7, no pior caso, porque é na ordem inversa. Então aqui é 7. Onde é que sete pertencem? Definitivamente atrás de mim. Mas agora 7 realmente não pertence imediatamente atrás de mim, mas por trás de número 8, então eu tenho que dizer: "Desculpe-me, número 8, por favor você pode mover este caminho "Para dar lugar a 7?" Agora eu encontro 6. "Oh, desculpe-me, número 8 e número 7, você pode se mover para fazer o quarto para 6?" Portanto, em outras palavras, com ordenação por inserção, mesmo que eu não estou fazendo muito movimento, as pessoas atrás de mim estão fazendo um trabalho muito mais, e isso tem que custar tempo alguém. Vai custar o tempo de computador. Assim, no caso da ordenação por inserção ainda sofremos. Se você começar a adicionar-se o número total de passos, acabamos batendo cerca de n ao quadrado porque esses caras precisam dar espaço para o ser humano a ser inserido de volta para essa lista. E assim, neste caso, teta não é apenas aplicável à história particular na mão. Isso é tudo bom e bom. Temos esses três maneiras diferentes de falar sobre o tempo de execução. Mas o que isso realmente significa em termos reais, se nós realmente tentar codificar um algoritmo? Deixe-me propor que há um algoritmo ainda melhor lá fora que em si tem algumas desvantagens. Vamos chamá-lo de merge sort, e é uma espécie de este algoritmo mágico que apenas funciona mais rápido de alguma forma, e é tão fácil de expressar, pelo menos em pseudocódigo. A aplicação deste tipo de intercalação algoritmo vai ser como se segue. Quando você está determinado n elementos - números n, n pessoas, o que for - Primeiro, há um teste de sanidade. Se n é inferior a 2, merge sort simplesmente pára. Ele retorna, por assim dizer. Por que você iria parar se n é menor que 2? >> [Resposta do aluno inaudível] Direito. E mais uma vez, n não é o número da lista, n é o tamanho da lista. Se n for menor do que 2, que significa que a sua lista é, 1, onde você está, obviamente, ordenadas se é um número, ou 0, caso em que não há nada para resolver, por isso precisamos deste tipo de caso base. Se a lista é tão curta que não há nada a fazer, literalmente, não faz nada. Voltar. Caso contrário classificar a metade esquerda dos elementos, em seguida, separar a metade direita dos elementos, em seguida, mesclar as duas metades classificados. Este tipo de fraude parece um pouco pela qual eu estou perguntando como classificar elementos e você está me dizendo, "Classificar a metade esquerda, classificar a metade direita." Eu sou como, "Tudo bem. Como você classifica a metade esquerda?" "Classificar a metade esquerda da meia esquerda, classificar a metade direita da meia esquerda, e então feito." Você é meio ciclicamente definir o que significa classificar, mas acontece que é realmente brilhante neste caso. Não é verdadeiramente este ciclo vicioso que nunca acaba porque não termina quando? >> [Aluno] Quando você chegar a uma coisa. Quando você chegar a uma coisa. Assim, mesmo que você pode começar com 8 pessoas e eu digo, "tipo a metade esquerda dessas pessoas, estes quatro pessoas ", então eu digo:" Como você classifica a metade esquerda? " "Bem, classificar as duas pessoas aqui." E então você é como, "Tudo bem, tudo bem." "Como você classifica a metade esquerda dessas pessoas?" "Só classificar essa pessoa um aqui." Qual é a revelação brilhante agora? Eu tenho que classificar uma pessoa. Concluído. Eu não tenho que fazer qualquer trabalho. Mas agora eu tenho que classificar esta pessoa, mas eles são uma única pessoa, nada a fazer. Assim, a magia, aparentemente, é neste terceiro passo: mesclar as metades classificados. Tipo assim fundir leva essa idéia brilhante que se você quebrar um grande problema para baixo em duas menores, de tamanho idêntico problemas e depois é só tipo de cola as soluções menores juntos no final, Proponho que pode fazer muito, [som tocando] muito melhor do que qualquer tipo de seleção ou tipo de inserção. Eu realmente sido ignorando que por meia hora, mas eu realmente não sei o que está acontecendo fora hoje. [Zumbido] [risos] Então, vamos ver se a gente pode ver isso com uma pequena ajuda do nosso amigo Rob Bowden. Existem dois grandes passos no processo de merge sort. Em primeiro lugar, de forma contínua dividir a lista de copos em metades até que tenhamos um monte de listas com apenas 1 xícara neles. Não se preocupe se uma lista contém um número ímpar e você não pode fazer um corte perfeitamente limpo entre eles. Apenas arbitrariamente escolher qual lista para incluir o copo extra dentro Então vamos dividir essas listas. Agora temos duas listas. Agora temos quatro listas. Agora temos oito listas com um único copo em cada lista. Então é isso para o passo 1. Para a etapa 2 que repetidamente fundir pares de listas usando o algoritmo de junção que aprendemos antes. Mesclando 108 e 15 vamos acabar com a lista de 15, 108. Mesclando 50 e 4 acabamos com 4, 50. Mesclando 8 e 42 nós acabamos com 8, 42. E fusão de 23 e 16 nós acabamos com 16, 23. Agora todas as nossas listas são de tamanho 2. Observe que cada uma das quatro listas é classificada, para que possamos iniciar a fusão de pares de listas novamente. Mesclando 15 e 108 e 4 e 50 que começou a tomar o 4, o 15, em seguida, a 50, em seguida a 108. Mesclando 8, 42 e 16, 23, primeiro tomar a 8, então o 16, em seguida, a 23, em seguida a 42. Portanto, agora temos apenas 2 listas de tamanho 4, cada um dos quais está classificada. Então agora nós mesclar essas duas listas. Primeiro tomamos a 4, então tomamos a 8, então tomamos a 15 e 16 e 23 e 42 e 50 e 108. E estamos a fazer. Temos, agora, uma lista ordenada. Rob era uma espécie de tirar proveito de algo que ainda não o fizeram. Foi sugerido, mas não realmente fazê-lo. Ele estava fazendo algo fisicamente com os copos que sugere ele estava gastando algum recurso além do tempo. >> [Aluno] Espaço. >> Foi espaço. O fato de que ele tinha esse tipo de bi-level mesa onde ele tinha espaço aqui e espaço aqui foi realmente o que significa que ele está usando o espaço duas vezes mais como qualquer um de nossos algoritmos até agora - uma espécie tipo de inserção, espécie de bolha, ou seleção - mas ele estava aproveitando este espaço adicional para o tipo de coisas frente e para trás ao manter as coisas em ordem. E ainda que se sente como chegamos a uma lista ordenada, que parecia que levou um tempo. Na realidade, o que Rob estava fazendo era exatamente este algoritmo. Ele primeiro levou o problema de tamanho n, dividiu-a em meia esquerda e um meia direita. É quando ele se mudou as xícaras. Então ele repetiu o processo. Ele dividiu 4 em 2 conjuntos de 2 aqui e aqui. Então ele repetiu esse processo e dividido em dois 2 jogos de 1 para cada um dos vários copos. E é aí que surge a oportunidade brilhante. Nesse ponto da história, Rob tinha oito listas de tamanho 1, todos os quais já foram classificados. Então o que ele continue a fazer? Pairwise ele tomou esta lista de classificados e esta lista ordenada e fundiu-los. Então ele levou um presente e fundiu-os, em seguida, um presente e fundiu-os, então este e fundiu-los. E então, o que ele fez em seguida? Ele, então, re-fundiu as listas de maiores e, em seguida, re-fundiu as listas maiores. E se você pensar sobre isso apenas intuitivamente, por agora, o que ele estava realmente fazendo? Ele estava dividindo o problema ao meio, ao meio, ao meio, na metade a fim de obter essas listas super pequeno. Então, ele era uma espécie de combinação de dupla, dupla, dupla, dupla. Então, ele estava fazendo duas vezes mais trabalho, como temos visto até agora com qualquer coisa que envolva dividir e conquistar, mas não é grande coisa. Trabalho duas vezes mais não é um negócio tão grande. É apenas um fator constante. E muito parecido com a nossa expressão aritmética antes, eu só vou riscar fatores constantes como vezes 2. Quem se importa? Se for 2 bilhões de vezes 2, que ainda é uma série de etapas. Portanto, este passo fundir parece ser a chave da compreensão. Vamos caminhar por esta apenas numericamente antes - Ah, isso não é para ser continuado ainda. Vamos caminhar por esta numericamente apenas para realmente ver como isso se desenrola. Isto é mais apenas uma animação um pequeno homem pobre. Vamos propor isso. O tempo de execução da ordenação merge - só precisamos de uma maneira de falar sobre isso. Isto não é matemática, esta é apenas uma espécie de uma maneira sucinta de nos expressar. Então T representa o tempo e n representa o que? >> [Estudante] O tamanho da - [Malan] O tamanho do problema, o número de pessoas. Então, eu estou afirmando que o tempo de execução para classificar as pessoas n vai ser 0 quantidade de tempo se n for menor que 2, porque se você tem um copo ou não à vontade, você não tem nada para resolver. Mas em geral, eu vou propor que o tempo de execução para ordenar n elementos vai ser o tempo que leva para classificar a metade da esquerda, mais a metade direita plus - o que é isso adicional + n? >> [Aluno] tipo Merge. [Malan] É realmente fusão, porque se você tem n / 2 elementos aqui e você tem n / 2 elementos aqui, quanto tempo leva para fundi-los? Assim como Rob, você tem que arrancar este aqui, talvez arrancar aqui, arrancar aqui, arranca aqui, arranca aqui. Você tem que tocar cada um dos copos de uma vez. E se há 4 xícaras mais 4 copos, que é de 8 copos ou, mais geralmente, oito copos de n. Assim, o passo de fusão que pode expressar como n, e que envolve, literalmente, o número de vezes Rob fisicamente tocado um daqueles copos de isopor. Então, vamos agora fazer um exemplo arbitrário. Se há 16 xícaras, o que é o tempo de execução de classificação, usando o algoritmo de Rob, 16 copos? É duas vezes a quantidade de tempo que leva para classificar 8 copos porque temos oito copos aqui, oito copos aqui. Eu não sei quanto tempo que leva, por isso estamos generalizando-o como T para o momento. Quem sabe o que é? Mas agora eu posso classificar de forma recursiva ou repetidamente a mesma pergunta. Quanto tempo leva para classificar oito copos? 8 copos que eu vou dizer tem a quantidade de tempo que leva para classificar 4 xícaras mais 4 copos, em seguida, fundi-las em conjunto. Multa. Estamos entrando em um ciclo já. Quanto tempo leva para classificar quatro copos? O tempo que leva para classificar quatro copos é de 2 xícaras mais 2 copos de classificação, mais o processo de fusão. Multa. Quanto tempo leva para classificar dois copos? 2 chávenas é a quantidade de tempo que leva para classificar um copo mais o tempo que leva para classificar um outro copo mais a quantidade de tempo que demora a se fundir, o que é apenas 2. Multa. Última pergunta. Quanto tempo leva para classificar um copo? Aqui é o caso de base que prevíamos que ia bater mais cedo. O fato de que ela não tem trabalho algum para classificar o menor dos problemas significa que agora, uma espécie de estilo de escola, podemos apenas ir começar a ligar estes números para trás dentro Nós sabemos agora que T é de 1, para que eu possa ligar 0 para T de 1. Isso vai me dar a resposta a T de 2, que eu então possa ligar mais para cima. Que vai me dar T de 4, que eu posso ligar mais para cima. Que vai me dar T, de 8, que eu possa ligar mais para cima. E se eu realmente fazer que matemática ligando essas respostas, Eu, então, obter T de 16 é 64. E o que representam 64? Se T é de 16, sim, é 16 vezes 4. Então eu digo agora que o tempo de execução de uma coisa chamada merge sort - e este vai ser o mais badalados de os que temos visto até agora - vai ser chamado de n log n porque quantas vezes pode roubar dividir um monte de copos pela metade? Entrar n. É o mesmo que o exemplo do livro de telefone, é o mesmo que o exemplo de auto-contagem. Quantas vezes você pode dividir algo pela metade? No entanto, há um passo de fusão. Você pode ter que dividir os copos em metade novo e de novo e de novo, mas cada vez que você vai ter que mesclar. E nós dissemos anteriormente que a fusão copos n tem n passos porque você tem que arrancar um copo, arrancar um copo, e você tem que tocar em cada copo uma vez, assim como Rob fez. Então, se estamos fazendo algo log n vezes e nós estamos fazendo n coisas em cada uma dessas iterações, cada uma dessas halvings, temos vezes log n n. Então, se ligar em 16 neste exemplo, 16 vezes log de 16 - não se preocupe porque este é o caso, por agora, porque eu não tenha desenhado a base - mas log de base 2, de 16 a 4, 16 vezes 4 é 64. Mas por outro lado, se tivéssemos utilizado espécie de bolha ou tipo de seleção ou tipo de inserção com 16 números, o que seria o tempo de execução ter sido se n é 16? Seria 16 quadrado, que é de 256, o que, mesmo se você não tiver muito seguido toda a matemática, 256 é maior do que 64. Essa é realmente a takeaway mágica aqui. E perceber que trabalhar com isso em exemplos menores como você vai em um pset torna tudo muito mais intuitivo. Mas o que isso realmente significa em termos de sensação deste algoritmo é o seguinte: Se nós realmente olhar para mesclar tipo aqui - deixe-me puxar para cima nesta janela aqui - este é um exemplo um pouco diferente em que todos nós temos três destes algoritmos - bolha, seleção, e mesclar - apenas lado a lado. Eles têm tudo começou com barras aleatórios, e isso é bom. Ninguém tem uma vantagem fundamental sobre o outro. Eu vou em um momento clique em cada uma dessas animações - Start, Start, Start - tão rápido quanto possível, de modo que, aproximadamente, todos eles começam ao mesmo tempo, e vamos considerar que o pior caso espécie de bolha do tempo de funcionamento é o que? >> [Aluno] N ao quadrado. N ao quadrado. Pior tipo de seleção do tempo de funcionamento é? N ao quadrado. E merge sort, aparentemente, - mesmo se você não chegou a acompanhar toda a matemática agora, ele vai se tornar muito mais intuitivo ao longo do tempo - é, nós reivindicamos, n log n vezes. E porque log n é estritamente menor que n uma vez que temos grandes números, n vezes log n for menor do que n vezes n ou n ao quadrado. Então, o que é a sensação de ser realmente um melhor algoritmo em termos de tempo de execução, n log n vezes em oposição ao n ao quadrado? Aqui vamos nós. Clique, clique, clique. Isso é o que significa usar algo como merge sort. Temos um momento. Vamos ver o que acontece aqui. [Risos] De quem é o dinheiro em espécie de bolha? É, em vez depende da entrada, às vezes. Vamos ver. Vamos. Parece que ele está a aproximar-se. >> [Aluno] Vai, espécie de bolha! [Estudantes murmurando] [Malan] Sim, sim. [Estudantes murmurando] Vai, vai, vai! [Todos torcendo] [aplausos] Então, agora com uma demo, última final, se é um pouco complicado envolver sua mente em torno da matemática ou uma espécie de visualização lá, você pode realmente ouvir as velocidades de algoritmos diferentes de forma diferente. Esta é uma animação feita alguém que realmente soa associados com o processo de permuta e a altura das barras. Como veremos aqui, há alguns algoritmos de ordenação mais lá fora que a gente pensou. Este primeiro vai ser tipo de inserção, e isso vai voar através e dar-lhe um sentido sonoro de como funcionam estes algoritmos diferentes. Aqui é um tipo de inserção. [Bip eletrônico] [Malan] espécie de bolha. [Mais rápido sinal sonoro eletrônico] [Malan] tipo de seleção. [Mais rápido sinal sonoro eletrônico] [Malan] tipo Merge. [Bip eletrônico] [Chamando desacelera] [risos] [Malan] sort Gnome. [Bip eletrônico] Este é CS50. Vamos ver na próxima semana. [Aplausos e aplausos] [CS50.TV]