DAVID MALAN: Tudo bem. Estamos de volta. Portanto, neste segmento sobre a programação que Pensei que faria é uma mistura de coisas. Um, fazer um pouco de algo prático, embora com uma forma mais lúdica environment-- programação um que é demonstrativo de exatamente os tipos de idéias temos vindo a falar, mas um pouco mais formalmente. Dois, olhar para alguns dos as formas mais técnicas que um programador seria realmente resolver problemas como o problema procura que olhou antes e também uma mais fundamentalmente problema interessante de classificação. 

Nós só assumiu desde o ir buscar que esse livro de telefone foi resolvido, mas que por si só é realmente uma espécie de problema difícil com muitas maneiras diferentes resolvê-lo. Então, vamos usá-los como uma classe de problemas representante das coisas que pode ser resolvido de um modo geral. E então vamos falar sobre com algum detalhe o que são chamados de dados structures-- formas mais extravagantes como listas ligadas e tabelas de hash e árvores que um programador seria realmente usar e, geralmente, utilizar em um quadro branco para pintar uma imagem do que ele ou ela vislumbra para a implementação algum pedaço de software. 

Então vamos fazer o hands-on primeira parte. Então, basta sujar as mãos com um ambiente chamada scratch.mit.edu. Esta é uma ferramenta que usamos na nossa classe de graduação. Mesmo que ele é projetado para as idades de 12 e acima, podemos usá-lo para o up parte desse um pouco já que é um bom, divertido forma gráfica da aprendizagem um pouco sobre programação. Então cabeça para que URL, onde você deve ver uma página como esta, e vá em frente e clique Junte-se a zero no canto superior direito e escolher um nome de usuário e uma senha e, finalmente, obter-se um scratch.mit.edu account--. Pensei em usar isso como uma primeira oportunidade para mostrar isso. A questão foi levantada durante a pausa sobre o código realmente se parece. E nós estávamos falando durante a pausa de cerca de C, em particular um particular-- menor nível em uma linguagem mais antiga. E eu apenas fiz uma rápida Google busca para encontrar o código C para pesquisa binária, o algoritmo que nós usado para procurar o livro de telefone mais cedo. Neste exemplo particular, é claro, não procurar um livro de telefone. Ele só procura um monte de números na memória do computador. Mas se você gostaria de obter apenas um Visual sentido do que uma programação real linguagem parece, parece um pouco algo como isto. Portanto, é cerca de 20-plus, 30 ou mais linhas de código, mas a conversa que estavam tendo durante as férias era sobre como isso realmente se transformou em zeros e uns e se você não pode simplesmente reverter essa processar e ir de zeros e uns voltar ao código. 

Infelizmente, o processo de é tão transformadora que é muito mais fácil dizer do que fazer. Fui em frente e realmente se transformou esse programa, Binary Search, em zeros e uns por meio de um O programa chamado compilador que eu acontecer de ter aqui bem no meu Mac. E se você olhar para a tela aqui, concentrando-se especificamente nesses seis colunas do meio somente, você verá apenas zeros e uns. E esses são os zeros e uns que compor exatamente esse programa de pesquisa. 

E assim cada pedaço de cinco bits, cada byte de zeros e uns aqui, representam algumas instruções tipicamente dentro de um computador. E, na verdade, se você já ouviu o slogan de marketing "Intel inside" - que, é claro, significa apenas que você tem um CPU Intel ou o cérebro dentro do computador. E o que significa ser um CPU é que você tem um conjunto de instruções, por assim dizer. 

Cada CPU no mundo, muitos dos -los feito pela Intel nos dias de hoje, compreende um finito número de instruções. E essas instruções são tão baixo nível como adicionar esses dois números juntos, multiplicar esses dois números juntos, mover este pedaço de dados a partir daqui para aqui na memória, salvar esta informações daqui até aqui na memória, e assim por forth-- muito, muito baixo nível, detalhes quase eletrônicos. Mas com os matemático operações acoplado com o que discutimos anteriormente, a representação dos dados como zeros e uns, pode você construir tudo que um computador pode fazer hoje, seja é textual, gráfica, musical, ou então. 

Então isso é muito fácil de obter perdido nas ervas daninhas de forma rápida. E há um monte de desafios sintáticas em que se tornar o mais simples, estúpido de erros de digitação nenhum do programa funcionará qualquer. E assim, em vez de usar um linguagem como C, esta manhã, Eu pensei que seria mais divertido para realmente fazer algo mais visual, que enquanto projetado para crianças é, na verdade, uma manifestação perfeita de uma programação real language-- só acontece de usar imagens em vez de texto para representar essas idéias. 

Então, quando você de fato tem um conta no scratch.mit.edu, clique no botão Criar no canto superior esquerdo do site. E você deve ver um ambiente como o que eu estou prestes a ver em minha tela Aqui. E nós vamos gastar um pouco pouco de tempo a jogar aqui. Vamos ver se nós não podemos todos resolver alguns problemas em conjunto da seguinte maneira. 

Então, o que você verá dentro deste environment-- e realmente apenas deixar me uma pausa. Será que alguém não está aqui? Não aqui? ESTÁ BEM. Então, deixe-me salientar alguns características desse ambiente. 

Então, na parte superior esquerda da tela, nós tem palco do zero, por assim dizer. Zero não é apenas o nome desta linguagem de programação; é também o nome do gato que você vê por padrão, não em laranja. Ele está em um estágio, de modo tanto como eu descrevi a tartaruga anteriormente como estar em um rectangular ambiente quadro branco. mundo deste gato está totalmente confinada para esse retângulo em cima lá. 

Enquanto isso, do lado direito lado aqui, é apenas uma área de roteiros, um lousa em branco se você quiser. Este é o lugar onde nós estamos indo para escrever nossos programas em apenas um momento. E os blocos de construção que deve usado para gravar essa program-- o quebra-cabeça pedaços, se você will-- são aqueles aqui no meio, e eles estão categorizados pela funcionalidade. Assim, por exemplo, eu estou indo para ir em frente e demonstram, pelo menos, um destes. Eu estou indo para ir em frente e clique a categoria de controle em cima. 

Portanto, estas são as categorias em cima. Vou clique na categoria de Controle. Em vez disso, eu vou clique nos eventos categoria, a primeira um em cima. E se você gostaria de acompanhar, mesmo como fazer isso, você está muito bem-vindo para. Eu estou indo para clicar e arrastar esse primeiro, "quando a bandeira verde clicado." E então eu vou deixá-la apenas aproximadamente no topo das minhas folhas em branco. 

E o que é agradável sobre risco é que esta parte do enigma, quando interligado com outro quebra-cabeça peças, vai fazer literalmente o que essas peças do puzzle dizer que fazer. Assim, por exemplo, Scratch é certo agora no meio de seu mundo. Eu estou indo para ir em frente e escolher Agora, vamos dizer, a categoria Movimento, se você gostaria de fazer o same-- categoria Motion. E agora notem eu tenho um todo monte de peças do puzzle aqui que, novamente, tipo de fazer o que eles dizem. E eu estou indo para ir em frente e arrastar e soltar o bloco movimento bem aqui. 

E note que, assim que você começa perto da parte inferior da "bandeira verde clicado "botão, o aviso prévio como uma linha branca aparece, como se fosse quase magnética, ele quer ir para lá. Apenas deixe ir, e ele se encaixará em conjunto e as formas irá corresponder. E agora você pode, talvez, quase adivinhar onde estamos indo com isso. 

Se você olhar para o estágio zero por aqui e olhar para o topo, você verá uma luz vermelha, um pare o sinal, e uma bandeira verde. E eu estou indo para ir em frente e assistir os meus screen-- por apenas um momento, se pudesse. Vou clique no bandeira verde agora, e moveu-se o que parece ser 10 passos ou 10 pixels, 10 pontos, na tela. 

E assim não excitante, mas deixe-me propor sem sequer ensinando isso, basta usando o próprio seu próprio let intuition-- -me propor que você descobrir como fazer scratch pé direito para fora do palco. Tê-lo abrir caminho para o lado direito a tela, todo o caminho para a direita. Deixe-me dar-lhe um momento ou mais para lutar com isso. Você pode querer dar uma olhada em outras categorias de blocos. Tudo certo. Então, só para recapitular, quando temos a bandeira verde clicado aqui e mover 10 passos é a única instrução, cada vez que eu clique na bandeira verde, o que está acontecendo? Bem, isso está executando o meu programa. Então, eu poderia fazer isso talvez 10 vezes manualmente, mas este se sente um pouco pouco hackish, por assim dizer, em que eu realmente não estou resolvendo o problema. Eu só estou tentando novamente e de novo e de novo e de novo até eu meio que acidentalmente alcançar a directiva que se propõe atingir mais cedo. 

Mas nós sabemos de nossa pseudocódigo anterior de que há esta noção em programação de looping, fazendo algo novo e de novo. E então eu vi que um monte de você alcançou peça o quebra-cabeça? Repita até. Para que pudéssemos fazer algo como repetir até. E o que você repetir até que exatamente? 

ESTÁ BEM. E deixe-me ir com um que é um pouco mais simples para apenas um momento. Deixe-me ir em frente e fazer isso. Observe que, como você pode ter descoberto sob controle, existe este bloco de repetição, que Não parece que ele é tão grande. Não há muito espaço no entre essas duas linhas amarelas. Mas, como alguns de vocês podem ter notado, se você arrastar e soltar, notar como cresce para preencher a forma. 

E você ainda pode empinar mais. Ele só vai continuar a crescer, se você arrastar e pairar sobre ele. E eu não sei o que é melhor aqui, então vamos me, pelo menos, repetir cinco vezes, por exemplo, e depois voltar para o palco e clique na bandeira verde. E agora percebe que não é bem lá. 

Agora alguns de vocês proposto, Victoria fez, repita 10 vezes. E que geralmente faz levá-lo todo o caminho, Mas não seria haver uma mais robusta maneira do que arbitrariamente descobrir quantos movimentos para fazer? O que poderia ser um bloco melhor do que repetir 10 vezes ser? 

Sim, então porque não fazer algo para sempre? E agora deixe-me mover esta parte do enigma lá dentro e livrar-se de um presente. Agora note, não importa onde Raspadinha começa, ele vai para a borda. E felizmente MIT, que faz scratch, apenas garante que ele nunca desaparece completamente. Você pode sempre agarrar sua cauda. 

E apenas intuitivamente, por que ele continua se movendo? O que está acontecendo aqui? Ele parece ter parado, mas em seguida, se eu pegar e arrastar ele continua querendo ir para lá. Por que é que? Verdadeiramente, um computador é, literalmente, vai fazer o que você diga a ele para fazer. Então, se você disse isso antes fazer o coisa seguinte para sempre, mover 10 passos, ele vai continuar e vai até que eu bati o sinal vermelho e parar o programa completamente. 

Assim, mesmo se você não fez fazer isso, como eu poderia fazer mover mais rápido do risco do outro lado da tela? Mais passos, certo? Então, em vez de fazer 10 de cada vez, por quê nós não vá em frente e mudar isso a-- o que você propose-- 50? Então agora eu vou clique no verde bandeira, e, na verdade, ele vai muito rápido. 

E isso, claro, é apenas uma manifestação de animação. O que é animação? É apenas mostrando-lhe a um ser humano grupo inteiro de imagens fixas, realmente, muito, muito rápido. E por isso, se nós estamos apenas dizendo -lo a se mover mais passos, nós apenas estamos tendo o efeito ser mudança onde ele está na tela toda a unidade mais rapidamente por de tempo. 

Agora, o próximo desafio que propus era tê-lo saltar para fora da borda. E sem saber o quebra-cabeça peças exist-- porque é fina se você não chegar ao etapa do que challenge-- você quer fazer intuitivamente? Como poderíamos tê-lo saltar para trás e diante, entre a esquerda e direita? 

Sim. Então, precisamos de algum tipo da condição, e nós parecem ter condicionais, por assim falar, sob a categoria de controle. Qual destes blocos nós provavelmente quer? Sim, talvez "se, então." Então, observe que, entre os blocos amarelo temos aqui, não é este "se" ou este "if, else" bloco que vai nos permitem tomar uma decisão para fazer isso ou para fazer isso. E você ainda pode inserí-las para fazer várias coisas. Ou se você não tenha ido ainda aqui, vá em frente para a categoria Sensing e- vamos ver se ele está aqui. 

Então, o bloco pode ser útil aqui para detectar se ele está fora do palco? Sim, notar que alguns desses blocos pode ser parametrizada, por assim dizer. Eles podem ser tipo de personalização, não ao contrário do HTML ontem com atributos, onde esses atributos tipo de personalizar o comportamento de uma etiqueta. Da mesma forma aqui, posso agarrar esta comovente bloco e mudança e fazer a pergunta, você está tocando o mouse ponteiro como o cursor ou você está tocando a borda? 

Então deixe-me entrar e fazer isso. Eu estou indo para afastar por um momento. Deixe-me agarrar esta parte do enigma aqui, este enigma isso, e eu vou Desordem -los por apenas um momento. Eu estou indo para mover este, alterar esta a beira tocar, e eu vou fazer isso de movimento. Então, aqui estão alguns ingredientes. Eu acho que eu tenho tudo o que quero. 

Será que alguém gostaria de propor como eu pode conectar estes talvez de cima para baixo a fim de resolver o problema de ter Zero direita para a esquerda para a direita para mover esquerda para a direita para a esquerda, cada um tempo apenas saltar fora da parede? O que eu quero fazer? Qual bloco deve me conectar à "Flag quando verde clicou pela primeira vez"? 

OK, então vamos começar com o "para sempre". O que vai dentro em seguida? Alguém. OK, mova etapas. Tudo certo. Então o que? Então a se. E note, mesmo que pareça imprensados ​​junto com força, ela só vai crescer para preencher. Ele vai apenas no salto, onde eu quero. 

E o que eu pus entre if e então? Provavelmente "se tocar borda." E observem, novamente, é muito grande para ele, mas ele vai crescer para preencher. E, em seguida, virar 15 graus? Quantos graus? Sim, então 180 girará me a toda a volta. Então vamos ver se eu tenho esse direito. Deixe-me afastar. 

Deixe-me arrastar zero para cima. Então, ele é um pouco distorcida agora, mas isso é bom. Como posso repor-lo facilmente? Eu estou indo para enganar um pouco. Então, eu estou adicionando outro bloco, só para ficar claro. Eu quero que ele aponta 90 graus à direita por padrão, então eu só vou dizer a ele para fazer isso por meio de programação. E aqui vamos nós. Nós parecemos ter feito isso. É um pouco estranho, porque ele está andando de cabeça para baixo. Vamos chamar esse um bug. Isso é um erro. Um bug é um erro em um programa, um erro lógico que eu, o ser humano, feito. Por que ele está indo de cabeça para baixo? Será que MIT estragar ou eu? 

Sim, quero dizer, não é MIT falha. Eles me deram uma parte do enigma que diz que transformar alguns número de graus. E por sugestão de Victoria, Eu estou girando 180 graus, que é a intuição certa. Mas transformar 180 graus literalmente significa virar 180 graus, e isso não é realmente o que eu quero, aparentemente. Porque pelo menos ele está em este mundo bidimensional, de modo decisivo que realmente está acontecendo para virar de cabeça para baixo. 

I provavelmente vai querer usar o bloco em vez disso, com base no que você vê aqui? Como podemos corrigir isso? É, por isso, poderia apontar no sentido oposto. E, na verdade, mesmo que seja não vai ser suficiente, porque só pode código rígido a apontar para a esquerda ou para a direita. 

Você sabe o que poderíamos fazer? Parece que temos um bloco de conveniência aqui. Se eu aumentar o zoom, ver algo que gostamos aqui? Portanto, parece que o MIT tem uma abstração construída aqui. Este bloco parece ser equivalente para que outros blocos, plural? 

Este bloco parece ser equivalente a todo este trio de blocos que temos aqui. Então não é que eu posso simplificar a minha programa por se livrar de tudo isso e basta colocar isso aqui. E agora ele ainda é um pouco carrinho, e isso é bom para agora. Vamos deixar que seja. Mas meu programa é ainda mais simples, e isso, também, seria representativa de um objetivo em programming-- é idealmente fazer o seu código como simples, tão compacto quanto possível, enquanto continuam a ser tão legível possível. Você não quer fazê-lo de modo sucinto que é difícil de entender. 

Mas observe que eu substituído três blocos com um, e isso é, sem dúvida, uma coisa boa. Eu abstraída a noção de verificar se você está na borda com apenas um bloco. Agora podemos nos divertir com isso, na verdade. Isso não acrescentar muito valor intelectual, mas valor lúdico. Eu estou indo para ir em frente e pegar este som aqui. Então deixe-me ir em frente, e deixe-me parar o programa por um momento. Vou gravar o seguinte, permitindo o acesso ao meu microfone. 

Aqui vamos nós. Ouch. Vamos tentar isso novamente. Aqui vamos nós. OK, eu gravei a coisa errada. Aqui vamos nós. Ouch. Ouch. Tudo certo. Agora eu preciso para se livrar dessa. Tudo certo. 

Então agora eu tenho um gravação de apenas "ouch". Então agora eu estou indo para ir em frente e chamar isso de "ai". Eu estou indo para voltar para meus scripts, e agora aviso há este bloco que se chama reproduzir o som "miau" ou reproduzir o som "ai". Eu estou indo para arrastar isso, e onde devo colocar isso para efeito cômico? É, por isso agora é uma espécie de carrinho, porque agora este block-- observe como esse "se na borda, salto "é uma espécie de auto-contido. Então eu preciso consertar isso. Deixe-me ir em frente e fazer isso. Deixe-me se livrar dessa e voltar para a nossa original, mais deliberada funcionalidade. Então, "se tocar borda, em seguida," Eu quero a girar, como Victoria proposto, 180 graus. E eu quero jogar o som "ouch" lá? 

Sim, notar que é fora esse bloco amarelo. Então, isso também seria uma bug, mas tenho notado isso. Então eu vou arrastá-lo até aqui, e aviso agora é dentro do "se". Assim, o "se" é esse tipo de como blot braço-like que só vai fazer o que está dentro dela. Então agora se eu diminuir o zoom em o risco de annoying-- 

COMPUTADOR: Ai, ai, ai. 

DAVID MALAN: E só vai durar para sempre. Agora é só para acelerar as coisas aqui, deixe-me ir em frente e abrir-se, vamos dizer-- deixe-me ir para algum do meu próprio material de classe. E deixe-me abrir, vamos dizer, este um feito por um dos nossos companheiros de ensino um par de anos atrás. Então, alguns de vocês podem recordar este jogo de outros tempos, e é realmente notável. Mesmo que nós fizemos o mais simples de programas de agora, vamos considerar o que isso realmente parece. Deixe-me bateu jogar. 

Então, neste jogo, temos um rã, e utilizando a seta keys-- ele toma passos maiores do que eu recorde-- Eu tenho controle sobre esse sapo. E o objetivo é atravessar a movimentada estrada sem correr para os carros. E vamos see-- se eu ir até aqui, eu tem que esperar por um registro para rolar. Isto parece um bug. Este é um tipo de bug. Tudo certo. Eu estou neste aqui, lá, e então você continua indo até você obter todas as rãs para os lírios. Agora, isso pode parecer tanto mais complexa, mas vamos tentar quebrar este para baixo mentalmente e verbalmente em seus blocos componentes. Então, há provavelmente um quebra-cabeça peça que nós não vimos ainda mas que está respondendo aos comandos das teclas, a coisas que eu bati no teclado. 

Então, há provavelmente algum tipo de bloco que diz, se a chave é igual a acima, em seguida, fazer algo com Scratch-- talvez movê-lo 10 etapas desta forma. Se tecla para baixo é pressionado, mover 10 passos Desta forma, ou para a esquerda, mover 10 passos Desta forma, 10 passos que. Virei claramente o gato em um sapo. Então, isso é apenas onde o traje, como chamadas de raspadinhas ele-- nós acabou de importar uma imagem do sapo. 

Mas o que mais está acontecendo? Que outras linhas de código, o que as outras peças do puzzle fez Blake, o nosso ensino do companheiro, utilizar neste programa, aparentemente? O que está fazendo tudo move-- o que de programação construir? 

Movimento, de modo que o sure-- mover o bloco, com certeza. E o que é que o bloco movimento Dentro, mais provável? Sim, algum tipo de loop, talvez um sempre bloquear, talvez uma repetição block-- repetir até que o bloco. E é isso que está a fazer os registros e os lírios e tudo mais movimento vai e volta. É só acontecendo sem parar. 

Por que alguns dos carros movendo mais rápido do que os outros? O que é diferente sobre esses programas? Sim, provavelmente alguns deles estão a tomar mais passos de uma só vez e alguns deles menos etapas de uma só vez. E o efeito visual é rápido contra lento. 

O que você acha que aconteceu? Quando eu tenho o meu sapo todo o caminho do outro lado da rua e do rio na almofada de lírio, algo digno de nota aconteceu. O que aconteceu assim que eu fiz isso? Parou. Aquele sapo parou, e Eu tenho uma segunda rã. Então, o construto deve ser usado lá, o recurso? 

É, por isso há algum tipo de "Se" condicionar-se lá, também. E acontece out-- não vimos isto-- mas há outros blocos em que há pode dizer que, se você está tocando outra coisa na tela, se você está tocando a almofada de lírio ", então". E, em seguida, que é quando nós fazer a segunda rã aparecer. Assim, mesmo que este jogo é certamente muito antigo, embora à primeira vista há tanta coisa acontecendo Blake on-- e não chicotear isto em dois minutos, provavelmente levou vários horas para criar este jogo com base em sua memória ou vídeos da versão de passado dele. Mas todas estas pequenas coisas indo na tela de forma isolada resumem-se a estes muito simples movimentos constructs-- ou declarações como já discutimos, loops e condições, e é sobre isso. Há algumas outras características extravagantes. Alguns deles são puramente estética ou acústico, como os sons Eu só jogou com. Mas para a maior parte, você tem nesta língua, risco, todos da fundamental blocos de construção que você têm em C, Java, JavaScript, PHP, Ruby, Python, e qualquer número de outras línguas. Qualquer dúvida sobre zero? Tudo certo. Portanto, não vamos mergulhar mais fundo para zero, que você é bem-vindo neste fim de semana, especialmente se você tem filhos ou sobrinhos e sobrinhas e tal, apresentá-los a zero. É realmente um maravilhosamente lúdica ambiente, com, como os seus autores, tetos muito altos. Mesmo que começou com muito detalhes de baixo nível, você pode realmente fazer um pouco com ele, e este é talvez uma demonstração de exatamente isso. 

Mas vamos agora fazer a transição para um pouco mais problemas sofisticados, se quiserem, conhecida como "busca" e "Triagem", de modo mais geral. Tivemos este livro de telefone earlier-- aqui está outra apenas para discussion-- que fomos capazes de pesquisa de forma mais eficiente porque de um pressuposto significativo. E só para ficar claro, o que suposição era eu fazendo ao pesquisar através deste livro de telefone? Que Mike Smith estava em o livro de telefone, embora eu seria capaz de lidar o cenário sem ele lá se eu simplesmente parou prematuramente. O livro é alfabética. E isso é muito generoso suposição, porque isso significa someone-- Eu sou do tipo de corte de um canto, como eu sou mais rápido porque alguém outros fizeram um monte de trabalho duro para mim. 

Mas e se o telefone livro foram não separados? Talvez Verizon tenho preguiça, só jogou nomes e números de todos lá dentro talvez na ordem em que eles assinou o serviço de telefone. E quanto tempo leva-me para encontrar alguém como Mike Smith? 1.000 páginas de telefone book-- quantas páginas que eu tenho que olhar através? 

Todos eles. Você é tipo de fora da sorte. Você literalmente tem que olhar para todos os página se o livro de telefone é apenas ordenados aleatoriamente. Você pode ter sorte e encontrar Mike na primeira página, porque ele foi o primeiro cliente para solicitar o serviço de telefone. Mas ele pode ter sido a última também. 

Então ordem aleatória não é bom. Então, suponha que temos para ordenar a livro de telefone ou nos dados gerais tipo que nos foi dado. Como podemos fazer isso? 

Bem, deixe-me tentar um exemplo simples aqui. Deixe-me ir em frente e atirar uma alguns números no quadro. Suponha que os números que temos são, digamos, quatro, dois, um e três. E, Ben, classificar esses números para nós. 

Tudo bem. Como você fez isso? Tudo certo. Então comece com a menor valor e o mais alto, e isso é realmente boa intuição. E perceber que nós os seres humanos são realmente muito bom em resolver problemas assim, pelo menos, quando os dados é relativamente pequena. Assim que você começa a ter centenas de números, milhares de números, milhões de números, Ben provavelmente Não poderia fazê-lo assim tão rápido, assumindo que havia lacunas nos números. Muito fácil de contar até um milhão Caso contrário, basta demorado. 

Assim, o algoritmo soa como Ben usado agora Foi busca pelo menor número. Assim, mesmo que nós, humanos, pode levar em um monte de informações visuais, um computador é, na verdade um pouco mais limitada. O computador só pode olhar para um byte de cada vez ou talvez quatro bytes de cada vez-- nos dias de hoje talvez 8 bytes de cada vez-- mas um número muito pequeno de bytes num determinado momento. 

Então, uma vez que nós realmente temos quatro valores separados aqui-- e você pode pensar em Ben como tendo antolhos se fosse um computador, tais que ele não pode ver qualquer outra coisa de um número em uma vez-- por isso, geralmente irá assumir, como em Inglês, vamos ler da direita para a esquerda. Assim, o primeiro número Ben provavelmente parecia em seguida, foi de quatro e muito rapidamente percebi que é um muito grande number-- deixe-me continuar a procurar. 

Há dois. Espere um minuto. Dois é menor do que quatro. Eu vou lembrar. Dois é agora o menor. Agora um-- que é ainda melhor. Isso é ainda menor. Vou esquecer dois e lembre-se um agora. 

E ele poderia parar de olhar? Bem, ele poderia baseadas nesta informação, mas ele seria melhor pesquisa o resto da lista. Porque o que se for zero estavam na lista? E se negativo alguém fosse na lista? Ele só sabe que a sua resposta é correto se ele é exaustivamente verifiquei a lista inteira. Então olhamos para o resto deste. Three-- que era um desperdício de tempo. Demos azar, mas eu estava Ainda correta de fazê-lo. E então agora ele presumivelmente seleccionado o número mais pequeno e basta colocá-lo no início da lista, como eu vou fazer aqui. Agora, o que você fez depois, embora você não pensar nisso quase a este ponto? Repita o processo, de modo algum tipo de loop. Há uma ideia familiar. Então aqui é quatro. Isso é atualmente o menor. Isso é um candidato. Não mais. Agora que eu vi dois. Esse é o próximo elemento mais pequeno. Three-- que não é menor, então, agora Ben pode arrancar os dois. 

E agora nós repita o processo, e de curso de três é puxado para fora em seguida. Repita o processo. Quatro é puxado para fora. E agora estamos fora dos números, assim que a lista deve ser ordenada. 

E, de fato, este é um algoritmo formal. Um cientista da computação seria chamam isso de "tipo de seleção," A idéia é tipo um listar iteratively-- novamente e novamente e novamente selecionando o menor número. E o que é agradável sobre ele é isso é tão danado intuitiva. É tão simples. E você pode repetir o mesmo operação novamente e novamente. É simples. 

Neste caso, foi rápido, mas quanto tempo faz exame realmente? Vamos fazê-lo parecer e sentir um pouco mais tedioso. Então, um, dois, três, quatro, cinco, seis, sete, oito, nove, 10, 11, 12, 13, 14, 15, 16-- número arbitrário. Eu só queria mais isso tempo do que apenas a quatro. Então, se eu tenho um todo monte de números agora---lo não importa mesmo o que é-- Vamos pensar sobre o que este algoritmo é realmente como. 

Suponha que há números lá. Mais uma vez, não importa o que eles são, mas eles são aleatórios. Estou aplicando o algoritmo de Ben. Eu preciso selecionar o menor número. O que eu faço? E eu vou fisicamente fazê-lo desta vez para representá-lo. Olhando, olhando, olhando, olhando, olhando. Só na hora que eu chegar a o fim da lista pode Eu percebo a menor número era dois neste momento. Não está na lista. Então, eu coloquei dois. 

O que devo fazer em seguida? Olhando, olhando, olhando, olhando. Agora eu encontrei o número sete, porque há falhas nestes Números de mas apenas arbitrária. Tudo certo. Então agora eu posso colocar para baixo sete. Olhando olhando, olhando. 

Agora eu estou supondo, claro, que não faz Ben tem RAM extra, extra memória, porque, obviamente, Estou olhando para o mesmo número. Certamente eu poderia ter lembrado todos esses números, e isso é absolutamente verdadeiro. Mas se Ben lembra tudo dos números que viu, ele não tem feito realmente progressos fundamentais porque ele já tem a capacidade de pesquisar através dos números na mesa. Lembrando todas as O números não ajudam, porque ele pode ainda como um computador só olhar para, já dissemos, um número de uma vez. Portanto, não há nenhum tipo de fraude lá que você pode aproveitar. 

Então, na realidade, como eu continuar pesquisando a lista, Eu literalmente só tem que continuar frente e para trás através dele, arrancando a próxima menor número. E como você pode tipo de inferir dos meus movimentos parvos, isso só fica muito tedioso muito rapidamente, e eu parecem estar indo para trás e frente, para trás e para a frente um pouco. Agora, para ser justo, eu não tenho que ir bem como, bem, vamos see-- para ser justo, Eu não tenho que caminhar bastante como muitos passos de cada vez. Uma vez que, é claro, como I selecionar números da lista, a lista restante está ficando mais curto. 

E assim vamos pensar sobre quantos passos eu estou realmente traipsing através de cada vez. Na primeira situação tivemos 16 números, e assim por maximally-- vamos apenas fazer isso por um discussion-- Eu tive que olhar através de 16 números para encontrar a menor. Mas uma vez eu arrancado o menor número, como tempo durou a lista restante, é claro? Apenas 15. Então, quantos números fez Ben ou eu tenho olhar através da segunda vez? 15, só para ir e encontrar o menor. Mas agora, é claro, a lista é, também, menor do que era antes. Então, como muitos passos fez I tem que tomar a próxima vez? 14 e depois 13 e depois 12, além de ponto, ponto, ponto, até que eu estou à esquerda com apenas um. Portanto, agora um cientista da computação seria perguntar, bem, o que faz que todos iguais? Na verdade, é igual a algum concreto número que certamente poderíamos fazer aritmeticamente, mas queremos falar sobre a eficiência de algoritmos um pouco mais como uma fórmula, independente de quanto tempo a lista é. 

E assim que você sabe o quê? Este é 16, mas como eu disse antes, vamos chamar o tamanho do problema n, onde n é um número. Talvez seja 16, talvez seja três, talvez seja um milhão. Eu não sei. Eu não me importo. O que eu realmente quero é uma fórmula que eu puder usar para comparar este algoritmo contra outros algoritmos que alguém pode reclamar são melhores ou piores. 

Assim, ao que parece, e só eu sei que isto da escola primária, que isso realmente funciona para o mesmo coisa que n mais de n mais um sobre dois. E isso acontece para igualar, de Naturalmente, n ao quadrado mais n mais de dois. Então, se eu queria uma fórmula por quantos passos estavam envolvidos em olhar para todos desses números novo e de novo e de novo e de novo, eu diria é n ao quadrado mais n mais de dois. Mas você sabe o que? Isso só parece confuso. Eu realmente quero um sentido geral das coisas. E você pode se lembrar de ensino médio que não é a noção de termo de maior ordem. Qual destes termos, a n quadrado, a N, ou a meia, tem o maior impacto ao longo do tempo? O maior n recebe, que destes assuntos mais? 

Em outras palavras, se eu ligar em um milhão, n ao quadrado vai ser mais provável o fator dominante, Uma vez que um milhão de vezes em si é muito maior do que mais um adicional milhões. Então você sabe o quê? Este é um tal danado grande número se você quadrado de um número. Isso realmente não importa. Nós só vamos cruz que fora e esquecê-la. E assim um cientista da computação diria que a eficiência deste algoritmo é da ordem de n ao quadrado Quero dizer realmente uma aproximação. É uma espécie de cerca de n ao quadrado. Ao longo do tempo, a maior e maior n recebe, este é uma boa estimativa para o que o a eficiência ou a falta de eficiência deste algoritmo é realmente. E eu derivar que, é claro, de realmente fazer a matemática. Mas agora eu só estou acenando minhas mãos, porque eu só quer um sentido geral deste algoritmo. 

Então, usando a mesma lógica, entretanto, vamos considerar outro algoritmo já olhou at-- busca linear. Quando eu estava procurando para o telefone book-- não classificando-o, procurando através do telefone book-- mantivemos dizendo que era 1.000 passos, ou 500 passos. Mas vamos generalizar isso. Se há n páginas o livro de telefone, o que é o tempo de execução ou o eficiência da pesquisa linear? É da ordem de quantos passos para encontrar Mike Smith usando a pesquisa linear, o primeiro algoritmo, ou mesmo o segundo? 

No pior dos casos, o Mike é no final do livro. Então, se o livro de telefone tem 1.000 páginas, dissemos última vez, no pior caso, isso pode levar mais ou menos como muitas páginas para encontrar Mike? Como 1000. É um limite superior. É uma pior situação possível. Mas, novamente, nós estamos nos movendo para longe a partir de números como 1.000 agora. É apenas n. 

Então, qual é a conclusão lógica? Encontrar Mike em um telefone livro que tem n páginas pode levar, no pior caso, quantos passos na ordem de n? E, de fato um computador cientista diria que o tempo de execução, ou o o desempenho ou a eficiência ou ineficiência, de um algoritmo como uma pesquisa linear está na ordem de n. E podemos aplicar o mesmo lógica de atravessar algo fora como eu fiz com o segundo algoritmo que tivemos com o livro de telefone, onde fomos duas páginas de cada vez. 

Então 1.000 página do livro de telefone pode nos levar 500 páginas voltas, mais um se dobrar um pouco para trás. Portanto, se um livro de telefone tem n páginas, mas nós estamos fazendo duas páginas por vez, que é aproximadamente o que? N ao longo de dois, de modo que é como n mais de dois. Mas eu fiz o pedido de um há pouco que n ao longo dois-- isso é meio o mesmo que apenas n. É apenas um fator constante, cientistas da computação diria. Vamos apenas focar as variáveis, realmente-- os maiores variáveis ​​na equação. 

pesquisa de modo linear, seja feito um página de cada vez ou duas páginas por vez, é uma espécie de fundamentalmente o mesmo. Ainda é da ordem de n. Mas eu reivindicado com a minha foto anterior que o terceiro algoritmo não foi linear. Não era uma linha reta. Foi que linha curva, e o fórmula algébrica havia o que? Log de n-- tão log base dois de n. E não temos de ir para muito muitos detalhes sobre logaritmos de hoje, mas a maioria dos cientistas da computação não iria mesmo dizer-lhe qual é a base. Porque é tudo apenas fatores constantes, por assim dizer, apenas pequenas diferenças numéricas. E assim esta seria uma muito comum caminho para computador particular formais cientistas uma placa ou programadores em um quadro branco na verdade, argumentando que algoritmo que usariam ou que a eficiência de seu algoritmo é. 

E isso não é necessariamente algo você discute em qualquer grande detalhe, mas um bom programador é alguém que tem uma base sólida, formal. Ele é capaz de falar com -lo neste tipo de forma e realmente fazer argumentos qualitativos como a razão pela qual um algoritmo ou um pedaço de software é superior, de alguma forma para outra. Porque você poderia certamente basta executar o programa de uma pessoa e contar o número de segundos é preciso para classificar alguns números, e você pode executar alguns O programa de outra pessoa e contar o número de segundos que leva. Mas esta é uma forma mais geral, que você pode usar para analisar algoritmos, se quiserem, apenas de papel ou apenas verbalmente. Sem mesmo executá-lo, sem mesmo tentando entradas de amostra, você pode apenas raciocinar com ele. E assim, com a contratação de um desenvolvedor ou se tendo-lhe espécie de discutir com você porque seu algoritmo, seu segredo molho para pesquisar bilhões de páginas da web para o seu empresa é melhor, estes são os tipos de argumentos que deveria idealmente ser capaz de fazer. Ou, pelo menos, estes são os tipos de coisas que viria em discussão, na menos em uma discussão muito formal. Tudo certo. Então Ben propôs algo chamado de seleção de classificação. Mas eu vou propor que há outras maneiras de fazer isso, também. O que eu não gosto muito sobre o algoritmo de Ben é que ele continuou andando, ou tendo-me andar, e para trás e de trás e para frente e para trás e para frente. E se em vez eu fosse fazer algo como esses números aqui e eu fosse apenas para lidar com cada número por sua vez, como eu estou dado? 

Em outras palavras, é aqui minha lista de números. Quatro, um, três, dois. E eu vou fazer o seguinte. Eu estou indo para inserir os números onde eles pertencem, em vez do que selecionando-os um de cada vez. Em outras palavras, aqui é o número quatro. 

Aqui está a minha lista original. E eu vou manter essencialmente uma nova lista aqui. Portanto, esta é a lista de idade. Esta é a nova lista. Eu vejo o número quatro em primeiro lugar. Minha nova lista é inicialmente vazio, por isso é o caso trivialmente que quatro está agora a lista variada. Estou apenas tomando o número que eu sou dado, e eu estou colocando isso na minha nova lista. 

É esta nova lista ordenada? Sim. É estúpido porque há apenas um elemento, mas é absolutamente classificadas. Não há nada fora do lugar. É mais interessante, este algoritmo, quando eu passar para a próxima etapa. 

Agora eu tenho um. Assim, uma, é claro, pertence ao início ou no fim desta nova lista? O início. Então eu tenho que fazer algum trabalho agora. Fui tomar alguns liberdades com o meu marcador por apenas desenhar coisas onde eu quero que eles, mas isso não é realmente preciso em um computador. Um computador, como se sabe, tem RAM, ou memória de acesso aleatório, e isso é um byte e outro byte e outro byte. E se você tem um gigabyte de RAM, você tem um bilhão de bytes, mas eles estão fisicamente em um único local. Você não pode simplesmente mover coisas ao redor desenhando-a no tabuleiro onde quiser. Então, se a minha nova lista tem quatro locais na memória, Infelizmente a quatro é já no lugar errado. 

Assim, para inserir o número um Eu não posso simplesmente desenhá-lo aqui. Este local de memória não existe. Isso seria fazer batota, e eu tenho sido batota pictoricamente por alguns minutos Aqui. Então, realmente, se eu quiser colocar um aqui, Eu tenho que copiar temporariamente os quatro e depois colocar um lá. 

Isso é bom, isso é correto, que é tecnicamente possível, mas percebe que é um trabalho extra. Eu não basta colocar o número no lugar. A primeira vez que teve que mover uma número, em seguida, colocá-lo no lugar, então eu meio que duplicou a minha quantidade de trabalho. Portanto, manter isso em mente. 

Mas agora estou feito com este elemento. Agora eu quero pegar o número três. Onde, é claro, ele pertence? Entre. Eu não pode enganar mais e só colocá-lo lá, porque, novamente, essa memória é em locais físicos. Então eu tenho que copiar os quatro e colocar os três aqui. Não é um grande negócio. É apenas uma etapa extra novamente-- sente muito barato. 

Mas agora eu passo para os dois. Os dois, é claro, pertence aqui. Agora você começa a ver como o trabalho pode acumular. Agora o que eu tenho que fazer? Sim, eu tenho que mover a quatro, Eu, então, tem que copiar os três, e agora eu posso inserir os dois. E a captura com este algoritmo, curiosamente, se que suponha que temos uma forma mais extrema caso em que ele é, digamos oito, sete, seis, cinco, quatro, três, dois, um. Isto é, em muitos contextos, o pior cenário, porque o danado é, literalmente, para trás. 

Realmente não afeta o algoritmo de Ben, porque na selecção de Ben tipo que ele vai continuar indo e voltando pela lista. E porque ele estava sempre à procura através de toda a lista restante, Não importa em que os elementos são. Mas, neste caso, com a minha inserção approach-- vamos tentar isso. 

Então, um, dois, três, quatro, cinco, seis, sete, oito. Um dois três quatro, cinco, seis, sete, oito. Vou tomar a oito, e onde posso colocá-lo? Bem, no início da minha lista, porque esta nova lista é ordenada. E eu atravessá-la fora. 

Onde devo colocar o sete? Danado. Ele precisa ir lá, então Eu tenho que fazer alguma cópia. E agora a sete vai aqui. Agora eu passar para o seis. Agora é ainda mais trabalho. 

Oito tem que ir aqui. Sete tem de ir aqui. Agora, a seis pode ir aqui. Agora eu agarrar a cinco. Agora, a oito tem que ir aqui, sete tem que ir aqui, seis tem que ir aqui, e agora os cinco e repita. E eu estou muito bem movendo-o constantemente. 

Assim, no final, este algorithm-- nós vamos chamá-lo de inserção sort-- realmente tem um monte de trabalho, também. É apenas diferente tipo de trabalho de Ben. O trabalho de Ben tinha-me ir e para trás todo o tempo, selecionar o próximo menor elemento novamente e novamente. Por isso, foi este tipo muito visual do trabalho. 

Este outro algoritmo que ainda é correct-- ele vai começar o trabalho done-- apenas muda a quantidade de trabalho. Parece que inicialmente você está poupança, porque você está apenas lidar com cada elemento na frente sem andar todo o caminho através da lista como Ben era. Mas o problema é, especialmente nestes casos louco onde tudo está para trás, você é apenas um tipo de adiando o trabalho duro até que você tem que corrigir seus erros. 

E por isso, se você pode imaginar este oito e sete anos e seis e cinco e depois de quatro e três e dois movendo seu caminho através da lista, temos apenas mudou o tipo de trabalho que estamos fazendo. Em vez de fazê-lo no início da minha iteração, Eu estou fazendo isso apenas na fim de cada iteração. Assim, verifica-se que este algoritmo, também, geralmente chamado de ordenação por inserção, é também da ordem de n ao quadrado. É realmente não é melhor, não é melhor em tudo. 

No entanto, há uma terceira abordagem Gostaria de encorajar-nos a considerar, que é esta. Então suponho minha lista, por simplicidade mais uma vez, é de quatro, um, três, dois-- apenas quatro números. Ben teve boa intuição, boa intuição humana antes, pelo que fixa o conjunto listar eventually-- tipo de inserção. I persuadiu-nos junto. Mas vamos considerar o maneira mais simples de corrigir esta lista. 

Esta lista não está ordenada. Por quê? Em Inglês, explicar por que Na verdade não é classificada. O que significa a não ser ordenados? 

ESTUDANTE: Não é sequencial. 

DAVID MALAN: Não sequencial. Me dê um exemplo. 

ALUNO: Coloque-as em ordem. 

DAVID MALAN: OK. Dê-me um exemplo mais específico. 

ALUNO: ordem crescente. DAVID MALAN: Ordem não ascendente. Ser mais preciso. Eu não sei o que você quer dizer com ascendente. O que está errado? 

ALUNO: O menor da números não está no primeiro espaço. 

DAVID MALAN: menor número de não no primeiro espaço. Seja mais específico. Eu estou começando a pegar. Nós estamos contando, mas o que está fora de ordem aqui? 

ALUNO: seqüência numérica. DAVID MALAN: seqüência numérica. tipo de todos de manutenção isso aqui-- nível muito elevado. Apenas literalmente me dizer o que é errado como uma força de cinco anos de idade. 

ALUNO: Mais um. 

DAVID MALAN: O que é isso? 

ALUNO: Mais um. 

DAVID MALAN: O que quer dizer mais um? Dê-me uma pessoa diferente de cinco anos de idade. O que há de errado, mãe? O que está errado, pai? O que quer dizer isso não é ordenada? 

ALUNO: Não é o lugar certo. 

DAVID MALAN: Qual é não no lugar certo? 

ALUNO: Four. DAVID MALAN: OK, bom. Então, quatro não é onde deveria estar. Em particular, é esse direito? Quatro e um, o primeiro dois números que vejo. Isto está certo? Não, eles estão fora de ordem, certo? Na verdade, acho que agora sobre um computador, também. Ele pode apenas olhar para talvez um, talvez duas coisas ao once-- e, na verdade, apenas uma coisa de cada vez, mas pode, pelo menos olhar para uma coisa, então o próxima coisa bem próximo a ela. 

Então são estes em ordem? Claro que não. Então você sabe o quê? Por que não tomamos bebê passos corrigir esse problema em vez de fazer estes fantasia algoritmos, como Ben, onde Ele é uma espécie de corrigi-lo por looping através da lista em vez de fazer o que eu fiz, onde Eu meio que fixa-lo como nós vamos? Vamos apenas literalmente quebrar a noção de ordem numérica order--, chamá-lo de tudo o que você want-- para estas comparações de pares. 

Quatro e um. É esta a ordem correta? Então vamos corrigir isso. Um e quatro, e em seguida vamos apenas copiar isso. Tudo bem, bom. Fixei um e quatro. Três e dois? Não. Deixe minhas palavras coincidir com os meus dedos. Quatro e três? 

Não é em ordem, então eu vou para fazer um, três, quatro, dois. Tudo bem. Agora, quatro e dois? Precisamos corrigir isso, também. Então, um, dois, três, quatro. Então, é classificada? Não, mas é o mais perto de ordenados? 

É, porque nós corrigido este erro, nós corrigido este erro, e nós corrigido este erro. Por isso, fixa três erros, sem dúvida. Ainda realmente não parece ordenada, mas é objectivamente mais perto de ordenado porque fixa alguns desses erros. 

Agora o que eu faço agora? I tipo de alcançado o fim da lista. Eu parecia ter fixado todos os erros, mas não. Porque neste caso, alguns números poderia ter borbulhava mais perto para outros números ainda estão fora de ordem. Então, vamos fazê-lo novamente, e eu vou apenas fazê-lo no lugar neste momento. Um e três? Está bem. Três e dois? Claro que não, então vamos mudar isso. Então, dois, três. Três e quatro? E agora vamos ser particularmente pedante aqui. É classificado? Você seres humanos sabe que está classificada. 

Eu deveria tentar novamente. Então, Olivia está propondo que eu tente novamente. Por quê? Porque um computador não tiver o luxo dos nossos olhos humanos de apenas olhando traseira-- OK, eu sou feito. Como o computador determinar que a lista está agora classificado? Mecanicamente. 

Eu deveria passar por mais uma vez, e apenas se I não faça / encontrar algum erro pode I então concluir que o computador, sim, nós somos bons de ir. Assim, um e dois, dois e três, três e quatro. Agora eu posso definitivamente dizer que este é classificadas, porque eu não fez alterações. Agora, seria um erro e apenas tolo se eu, o computador, perguntou essas mesmas perguntas novamente esperando respostas diferentes. não deveria acontecer. 

E então agora a lista é ordenada. Infelizmente, duração de este algoritmo também é N quadrado. Por quê? Porque você tem n números, e na pior caso você tem que mover n números n vezes, porque você tem que continuar de volta para verificar e corrigir potencialmente esses números. E nós podemos fazer a mais análise formal, também. 

Então, tudo isso é para dizer que tomamos três abordagens diferentes, uma deles imediatamente intuitiva fora do bastão de Ben à minha inserção sugerido tipo a este onde tipo de perder de vista a floresta para as árvores inicialmente. Mas, então, se você tomar um passo para trás, voila, temos fixo a noção de classificação. Portanto, este é, ouso dizer, um nível mais baixo talvez do que alguns dos outros algoritmos, mas vamos ver se não podemos visualizar estes por meio deste. 

Então, este é um bom software que alguém escreveu usando barras coloridas que há de vai fazer o seguinte para nós. Cada uma destas barras representa um número. Taller a barra, maior o número, menores do bar, Quanto menor o número. Assim, idealmente, queremos uma boa pirâmide onde começa pequeno e recebe grande, e isso significaria que essas barras são classificadas. Então, eu estou indo para ir em frente e escolher, por exemplo, o algoritmo de Ben tipo selecção first--. 

E observe o que está fazendo. A maneira como eles optou por fazer visualizar este algoritmo é que, assim como eu era andando através da minha lista, este programa está andando através da sua lista de números, destacando em cada rosa número que ele está olhando. E o que está prestes a acontecer agora? 

O menor número de que I ou Ben encontrou de repente é movido para o início da lista. E notem que eles fizeram evict o número que estava lá, e isso é perfeitamente bem. Eu não entrar nesse nível de detalhe. Mas é preciso colocar esse número em algum lugar, por isso, apenas mudou-se para o local aberto que foi criado. Então eu vou para acelerar este -se, porque caso contrário, torna-se rapidamente muito tedioso. Animação speed-- lá vamos nós. Então, agora mesmo princípio Eu estava aplicando, mas você pode começar a sentir o algoritmo, se você vai, ou vê-lo um pouco mais claramente. E este algoritmo tem o efeito de seleccionar o próximo elemento mais pequeno, então você vai começar a vê-lo rampa até à esquerda. E em cada iteração, como eu proposto, que faz um pouco menos de trabalho. Ele não tem que percorrer todo o caminho de volta para a extremidade esquerda da lista, porque já conhece aqueles são classificadas. Então, que tipo de parece que é acelerando, mesmo que cada passo é tendo a mesma quantidade de tempo. Há apenas poucas etapas restantes. E agora você pode tipo de sentir a algoritmo de limpeza do final do mesmo, e na verdade agora está classificada. 

Então ordenação por inserção é tudo feito. Eu necessidade de re-embaralhar a matriz. E observe Eu só pode manter randomização-lo, e vamos ter uma aproximação das a mesma abordagem, ordenação por inserção. Deixe-me retardá-lo para aqui. Vamos começar que mais. Pare. 

Vamos pular quatro. Aqui vamos nós. Randomize eles matriz. E aqui nós vai-- tipo de inserção. Toque. Observe que ele está lidando com cada elemento que encontra imediatamente, mas se ele pertence a o aviso de lugar errado todo o trabalho que tem que acontecer. Temos que continuar mudando mais e mais elementos para abrir espaço para o que queremos colocar no lugar. 

Então, nós estamos focando na extremidade esquerda da lista única. Repare que não temos sequer olhou at-- nós não têm destacado em qualquer coisa rosa para a direita. Nós estamos apenas lidando com os problemas à medida que avançamos, mas nós estamos criando um monte de trabalhar para nós ainda. E assim se acelerar este processo agora a ficar completa, ele tem uma sensação diferente para ele, de fato. É apenas incidindo sobre o fim esquerdo, mas fazendo um pouco mais de trabalho como needed-- tipo de coisas suavização mais, consertar as coisas, mas lidar última instância, com cada elemento de um de cada vez até chegarmos ao as-- bem, nós todos sabemos como isso vai acabar, por isso é um pouco nada assombroso talvez. 

Mas a lista na end-- spoiler-- vai ser resolvido. Então, vamos olhar para um último. Nós não podemos simplesmente ignorar agora. Estamos quase lá. Duas para ir, um para ir. E pronto. Excelente. 

Então agora vamos fazer uma última, re-randomização com bubble sort. E observe aqui, especialmente se eu retardá-lo para baixo, isso manter mergulhando completamente. Mas note que só faz pairwise tipo comparisons-- de soluções locais. Mas assim que chegarmos a o fim da lista na cor rosa, o que vai ter que acontecer de novo? Sim, ele vai ter que começar de novo, porque ele só erros de pares fixos. E que pode ter revelado ainda outros. E então se você acelerar este processo, você vai ver que, assim como o nome indica, o menor elements-- ou melhor, os elements-- maiores estão começando a bolha até o topo, se você quiser. E os elementos são menores começando a bolha para baixo à esquerda. E, de fato, esse é o tipo de o efeito visual bem. E assim isso vai acabar terminando de um modo muito semelhante, também. 

Não temos para habitar em um presente particular. Deixe-me abrir isso agora também. Há alguns outros algoritmos de ordenação em todo o mundo, alguns dos quais são capturados aqui. E, especialmente, para os alunos que não são necessariamente visual ou matemática, como fizemos antes, nós podemos também fazer isso audially se associar um som com isso. E só por diversão, aqui está um alguns algoritmos diferentes, e um deles, em especial, você está vai notar é chamado de "merge sort". 

É realmente uma fundamentalmente melhor algoritmo, de tal forma que merge sort, um dos os que você está prestes a ver, não é ordem de n ao quadrado. É na ordem log de n vezes de n, que é realmente menor e, portanto, mais rápido do que os outros três. E há um par outra bobas que vamos ver. 

Então, vamos lá com algum som. Esta é a ordenação por inserção, por isso novamente é apenas lidar com os elementos como eles vêm. Este é bubble sort, por isso é considerando-os pares de cada vez. E, novamente, os maiores elementos estão borbulhando até o topo. 

Em seguida tipo de seleção. Este é o algoritmo de Ben, onde novamente ele está selecionando de forma iterativa o próximo elemento mais pequeno. E mais uma vez, agora você pode realmente ouvir que está acelerando, mas apenas na medida como ele está fazendo cada vez menos trabalhar em cada iteração. Este é o mais rápido um, merge sort, que é classificar grupos de números em conjunto e, em seguida, combiná-las. Assim look-- esquerda metade já estão classificados. 

Agora ele está classificando a metade direita, e agora ele vai combiná-los em um só. Isso é algo chamado de "Gnome tipo." E você pode tipo de ver que ele vai lá e para cá, que fixa o trabalho um pouco aqui e antes de proceder à nova obra. E é isso. Há um outro tipo, que é realmente apenas para fins académicos, chamado de "tipo estúpido", que leva seus dados, classifica-o de forma aleatória, e verifica se ele está classificada. E se não é, re-ordena-lo aleatoriamente, verifica se ele está classificado, e se não se repete. E, em teoria, probabilisticamente isso vai terminar, mas depois de um pouco de tempo. Não é o mais eficiente de algoritmos. Assim, qualquer perguntas sobre os algoritmos particulares ou nada relacionados lá, também? 

Bem, vamos agora desmembrar o que todos estas linhas são que eu tenho desenhado eo que eu estou supondo que o computador pode fazer debaixo do capô. Eu diria que todos esses números Eu continuo drawing-- eles precisam para obter armazenado em algum lugar na memória. Vamos nos livrar desse cara agora, também. 

Assim, uma parte da memória numa Computador-- tão RAM DIMM é o que procurou ontem, dual memória em linha module-- se parece com isso. E cada uma dessas pequenas fichas pretas é algum número de bytes, normalmente. E então os pinos de ouro são como o fios que ligam ao computador, ea placa de silício verde é apenas o que mantém tudo em conjunto. Então o que isso realmente significa? Se eu tipo de desenhar essa mesma imagem, vamos supor que a simplicidade que este DIMM, dual Inline Memory Module, é um gigabyte de RAM, um gigabyte de memória, que é o número de bytes no total? Um gigabyte é quantos bytes? Mais que isso. 1124 é kilo, 1.000. Mega é milhões. Giga é um bilhão. 

Eu estou mentindo? podemos até ler o rótulo? Isto é, na verdade, 128 gigabytes, por isso é mais. Mas vamos fingir que isso é apenas um gigabyte. Então isso significa que há um bilhão bytes de memória disponíveis para mim ou 8 bilhões de bits, mas vamos para falar em termos de bytes agora, avançar. 

Então, o que isso significa é que isto é um byte, este é mais um byte, este é mais um byte, e se nós realmente queríamos para ser mais específico, teríamos de desenhar um bilhão de pequenos quadrados. Mas o que isso significa? Bem, deixe-me apenas aumentar em nesta imagem. Se eu tenho algo que parece assim agora, isso é quatro bytes. 

E assim eu poderia colocar quatro números aqui. Um dois três quatro. Ou eu poderia colocar quatro letras ou símbolos. "Ei!" poderia ir para a direita lá, porque cada uma das cartas, discutimos anteriormente, Pode ser representado com oito bits ou ASCII ou um byte. Portanto, em outras palavras, você pode colocar 8 mil milhões de coisas dentro de um presente da vara da memória. Agora o que isso significa para colocar as coisas de volta a volta para trás na memória como esta? Isto é o que um programador chamaria de um "array". Em um programa de computador, você não pensa sobre o hardware subjacente, per se. Você só pensa em si mesmo como tendo acesso a um total bilhão de bytes, e você pode o que quiser com ele. Mas por conveniência normalmente é útil para manter o seu direito de memória ao lado do outro como este. Então, se eu aumentar o zoom em isto-- porque certamente não vai desenhar um bilhão de pequenos squares-- vamos supor que este quadro representa essa vara da memória agora. E eu vou apenas chamar a todos quantos o meu marcador acaba me dando aqui. Portanto, agora temos uma vara de memória na placa que tem um, dois, três, quatro, cinco, seis, um, dois, três, quatro, cinco, seis, seven-- assim 42 bytes de memória sobre o total da tela. Obrigado. Sim, fiz a minha aritmética direita. Assim, 42 bytes de memória aqui. Então o que isso realmente significa? Bem, um programador de computador seria realmente geral acha deste como memória endereçável. Em outras palavras, cada uma delas locais na memória, em hardware, tem um endereço exclusivo. 

Não é tão complexo como um Brattle Square, Cambridge, Mass., 02138. Ao contrário, é apenas um número. Este é byte número zero, isto é um, isto é dois, isto é três, e esta é de 41. Espere um minuto. Eu pensei que eu disse 42 um momento atrás. Comecei a contar do zero, de modo que é realmente correto. Agora não temos realmente desenhá-la como uma rede, e se você desenhá-lo como uma grade Acho que as coisas realmente obter um pouco enganador. O que um programador faria, em sua própria mente, geralmente pensam desta memória como é como uma fita, como um pedaço de fita adesiva que só vai sobre e sobre para sempre ou até ficar sem memória. Assim, uma maneira mais comum para desenhar e só pensar sobre a memória seria a de que esta é zero bytes, um, dois, três, e, em seguida, ponto, ponto, ponto. E você tem 42 desses bytes total, o mesmo embora fisicamente ele pode realmente ser algo mais como este. 

Então, se você pensa agora do seu memória como esta, assim como uma fita, isso é o que um programador de novo chamaria de uma matriz de memória. E quando você quer realmente armazenar algo em memória de um computador, você geralmente fazer coisas loja back-to-back to back-to-back. Então, nós estamos falando de números. E quando eu queria para resolver problemas como quatro, um, três, dois, mesmo que eu estava apenas um desenho apenas o número quatro, um, três, dois no bordo, o computador faria realmente tem esta configuração na memória. 

E o que seria ao lado do dois na memória do computador? Bem, não há nenhuma resposta para isso. Nós realmente não sabemos. E desde que a O computador não precisa dele, ele não precisa se preocupar que é o próximo aos números que se preocupa com. E quando eu disse anteriormente que um computador só pode olhar para um endereço de cada vez, este é o tipo de porquê. 

Não ao contrário de um registro jogador e uma cabeça de leitura apenas ser capaz de olhar para um certo sulco em um registro da velha escola física de cada vez, de modo semelhante pode um computador graças a sua CPU e a sua conjunto de instruções Intel, entre cujos instrução é lido a partir da memória ou salvar em memory-- um computador só pode olhar em um local de cada vez-- por vezes, uma combinação dos mesmos, mas realmente apenas um local de cada vez. Então, quando estávamos fazendo estes vários algoritmos, Eu não só estou escrevendo em um vacuum-- quatro, um, três, dois. Esses números, na verdade, pertencem algures na memória física. Portanto, há pequenino transistores ou algum tipo da eletrônica debaixo da hood armazenar esses valores. 

E no total, quantos bits são envolvidos agora, só para ficar claro? Portanto, este é quatro bytes, ou agora é 32 bits total. Então, na verdade existem 32 zeros e aqueles que compõem essas quatro coisas. Há ainda mais aqui, mas mais uma vez, não se preocupam com isso. 

Então agora vamos fazer outra pergunta usando memória, pois que no final do dia está na variância. Não importa o que pode fazer com o computador, no final do dia o hardware ainda o é mesmo debaixo do capô. Como eu poderia armazenar uma palavra aqui? Bem, uma palavra em um computador, como "Ei!" seria armazenado como esta. E se você queria um mais Word, você pode simplesmente substituir esse e dizer algo como "Olá" e loja que aqui. 

E aqui, também, este contiguidade é realmente uma vantagem, porque um computador pode apenas lido da direita para a esquerda. Mas aqui está uma pergunta. No contexto desta palavra, h-e-l-l-o, ponto de exclamação, como pode o computador sabe onde o palavra começa e onde a palavra termina? No contexto de números, Como o computador saber quanto tempo a sequência de números é ou de onde ele começa? Bem, acontece out-- e não vamos entrar muito a este nível de detail-- computadores mover coisas ao redor na memória literalmente, por meio desses endereços. Assim, em um computador, se você estiver escrever código para guardar coisas como palavras, o que você está fazendo realmente está digitando expressões que lembram onde em memória do computador estas palavras são. Então deixe-me fazer uma muito, exemplo muito simples. 

Eu estou indo para ir em frente e abrir um programa de texto simples, e eu estou indo para criar um arquivo chamado hello.c. A maioria desta informação que Não vou entrar em em grande detalhe, mas eu estou indo para escrever um programa nesse mesmo idioma, C. Isto é muito mais intimidante, Eu diria, do que zero, mas é muito semelhante em espírito. Na verdade, estes encaracolado braces-- Você pode tipo de pensar o que eu fiz como esta. 

Vamos fazer isso, na verdade. Quando a bandeira verde clicado, faça o seguinte. Quero imprimir "Olá". Portanto, esta é agora pseudocódigo. Eu sou o tipo de borrar as linhas. Em C, esta língua que eu estou falando sobre, esta linha de impressão Olá torna-se realmente "printf" com alguns parênteses e um ponto e vírgula. 

Mas é exatamente a mesma idéia. E isso muito user-friendly "Quando a bandeira verde clicado" torna-se o muito mais arcano "void main int." E isso realmente não tem mapeamento, então eu só vou ignorar isso. Mas as chaves são como o peças do puzzle curvo como este. 

Assim, você pode tipo de adivinhar. Mesmo se você nunca programou antes, o que é que este programa provavelmente fazer? Provavelmente imprime Olá com um ponto de exclamação. 

Então, vamos tentar isso. Eu estou indo para salvá-lo. E isto é, novamente, uma muito ambiente da velha escola. Eu não posso clicar, não pode arrastar. Eu tenho que digitar comandos. Então, eu quero executar o meu programa, de modo Eu poderia fazer isso, como hello.c. Esse é o arquivo que eu corri. Mas espere, eu estou faltando uma etapa. O que dizemos é uma condição necessária passo para uma linguagem como C? Acabei de fonte escrita código, mas o que eu preciso? Sim, eu preciso de um compilador. Então, no meu Mac aqui, eu tenho um programa chamado GCC, o compilador GNU C, o que me permite fazer isto-- vez meu código-fonte em, vamos chamá-lo, Código da máquina. 

E eu posso ver que, outra vez, como se segue, estes são os zeros e uns EU APENAS criado a partir de meu código-fonte, todos os zeros e uns. E se eu quiser executar meu program-- isso acontece a ser chamado a.out para reasons-- histórico "Olá". Posso executá-lo novamente. Ola Ola Ola. E parece estar funcionando. 

Mas isso significa que em algum lugar na minha memória do computador são as palavras h-e-l-l o, ponto de exclamação. E verifica-se, como um aparte, o que um computador faria normalmente fazer para que ele saiba onde as coisas começam e end-- é vai colocar um símbolo especial aqui. E a convenção é colocar o número zero no final de uma palavra para que você saiba onde realmente termina, de modo que você não manter imprimir mais e mais caracteres que você realmente pretende. 

Mas o takeaway aqui, mesmo embora este é bastante misterioso, é que é, em última análise relativamente simples. Foi-lhe dado uma espécie de fita, um espaço em branco espaço onde pode escrever cartas. Você simplesmente tem que ter um símbolo especial, como arbitrariamente o número zero, para colocar na extremidade da suas palavras para que o computador sabe, oh, eu deveria parar a impressão depois Eu vejo o ponto de exclamação. Porque a próxima coisa lá é um valor ASCII de zero, ou o carácter nulo como alguém iria chamá-lo. Mas há um tipo de um problema aqui, e vamos voltar a números por um momento. Suponha que eu faço, na verdade, têm uma série de números, e supor que o programa que eu estou escrevendo é como um livro de notas para um professor e uma sala de aula professores. E este programa permite que ele ou ela para digitar as notas dos seus alunos em questionários. E suponha que o aluno recebe 100 em seu primeiro teste, talvez como um 80 no próximo, em seguida, um 75, em seguida, um 90 no quarto quiz. 

Portanto, neste ponto da história, a matriz é de tamanho quatro. Não há absolutamente mais memória no computador, mas a matriz, por assim dizer, é de tamanho quatro. Suponha agora que o professor quer para atribuir um quinto teste para a classe. Bem, uma das coisas que ele ou ela vai ter que fazer é agora armazenar um valor adicional aqui. Mas se a matriz o professor tem criado neste programa é de tamanho para, um dos problemas com que é uma matriz você não pode simplesmente continuar a acrescentar a memória. Porque o que se outra parte do programa tem a palavra "hey" ali? 

Em outras palavras, a memória pode ser usado para qualquer coisa em um programa. E se antes eu digitei, hey, Quero entrada quatro pontuações do questionário, eles podem ir aqui e aqui. E se de repente você mudar sua mente mais tarde e dizer que eu quero um quinto teste pontuação, você não pode simplesmente colocá-lo onde quiser, porque o que se esta memória está sendo usada para algo else-- algum outro programa ou alguma outra característica do programa que você está correndo? Então você tem que pensar com antecedência como você deseja armazenar seus dados, porque agora você pintou sozinho em um canto digital. 

Assim, um professor pode, em vez dizer quando se escreve um programa para armazenar a sua notas, você sabe o quê? Vou solicitar, ao escrever o meu programa, que eu quero zero, um, dois, três, quatro, cinco, seis, oito graus no total. Então, um, dois, três, quatro, cinco, seis, sete, oito. O professor pode apenas sobre-alocar memória ao escrever o seu programa e dizer, você sabe o quê? Eu nunca vou atribuir mais de oito testes em um semestre. Isso é uma loucura. Eu nunca vou atribuir isso. Assim que esta maneira que ele ou ela tem a flexibilidade para pontuações loja de estudante, como 75, 90, e talvez um extra, onde o aluno tem crédito extra, 105. 

Mas se o professor nunca utiliza estes três espaços, há um takeaway intuitiva aqui. Ele ou ela é apenas desperdício de espaço. Portanto, em outras palavras, não é isso tradeoff comum na programação onde você pode alocar exatamente tanta memória como você quer, a cabeça do que é que você está super efficient-- você não está sendo um desperdício em todos-- mas a desvantagem dos quais é o que se você mudar sua mente quando usando o programa que você deseja armazenar mais dados do que você inicialmente previsto. 

Então, talvez a solução é, então, escrever seus programas de tal forma que eles usam mais memória do que eles realmente precisam. Desta forma, você não vai a correr para esse problema, mas você está sendo um desperdício. E o mais memória o programa usa, como discutimos ontem, a menos memória que está disponível para outros programas, quanto mais cedo o seu computador pode retardar para baixo por causa da memória virtual. E assim a solução ideal pode ser o que? 

Sub-reparte parece ruim. Over-reparte parece ruim. Então, o que pode ser uma solução melhor? A realocação. Seja mais dinâmico. Não se force a escolher um priori, no início, o que você quer. E, certamente, não o excesso de alocar, para que você não ser um desperdício. 

E assim, para alcançar esse objetivo, precisa jogar esta estrutura de dados, por assim dizer, longe. E então o que um programador tipicamente utilizará é algo que não é uma chamada matriz, mas uma lista ligada. Em outras palavras, ele ou ela vai começar a pensar em sua memória como sendo um tipo de forma que eles pode tirar da seguinte maneira. Se eu quiser armazenar um número na um program-- por isso é de setembro de Eu dei os meus alunos um questionário; eu quero para armazenar primeiro teste dos alunos, e eles tem um 100 sobre ele-- I vou pedir o meu computador, por meio do programa que eu tenho escrito, por um pedaço de memória. E eu estou indo para armazenar o número 100, e é isso. 

Em seguida, algumas semanas mais tarde quando eu chegar em meu segundo questionário, e é hora de digitar em que 90%, eu vou para pedir o computador, hey, computador, Eu posso ter outro pedaço de memória? Vai me dar a este pedaço vazio de memória. Vou colocar o número 90, mas no meu programa de alguma forma ou outro-- e nós não vai se preocupar com a sintaxe para isto-- eu preciso de alguma forma encadear essas coisas juntas. E eu vou acorrentá-los juntamente com o que parece ser uma seta aqui. 

O terceiro questionário que surge, Eu vou dizer, hey, computador, dar-me outro pedaço de memória. E eu vou colocar para baixo que quer que fosse, como 75, e tenho de cadeia presente juntos agora de alguma forma. Quarta questionário vem junto, e talvez isso é para o final do semestre. E por esse ponto o meu programa pode estar usando memória em todo o lugar, em todo fisicamente. E assim, apenas por diversão, eu sou vai tirar essa luz quiz-- eu esquecer o que era; Eu acho que talvez um 80 ou algo-- caminho até aqui. 

Mas isso é bom, porque pictoricamente Eu estou indo para desenhar esta linha. Em outras palavras, na realidade, no hardware do seu computador, a primeira pontuação pode acabar aqui, porque é logo no início do semestre. O próximo pode acabar aqui porque um pouco de tempo já passou eo programa continua a funcionar. A próxima pontuação, que foi a 75, pode ser por aqui. E a última pontuação pode ser um 80, que é por aqui. 

Então, na realidade, fisicamente, isso pode ser o que a memória do seu computador parece. Mas este não é um mentais útil paradigma para um programador de computador. Por que você deveria se preocupar onde o Parreira seus dados estão terminando? Você só quer armazenar dados. 

Este é tipo de como nossa discussão antes de desenhar o cubo. Por que você se importa o que é o ângulo do cubo e como você tem que voltar para desenhá-lo? Você só quer um cubo. Da mesma forma aqui, você só quero livro de notas. Você só quer pensar isto como uma lista de números. Quem se importa como ela é implementadas em hardware? 

Assim, a abstração agora É esta foto aqui. Esta é uma lista ligada, como um programador iria chamá-lo, na medida em que você tem um lista, obviamente, de números. Mas está ligada pictoricamente por meio destas setas, e todas estas setas é-- debaixo o capô, se você estiver curioso, Recordamos que o nosso hardware físico tem endereços zero, um, dois, três, quatro. Todas estas flechas são é como um mapa ou instruções, onde se 90 é-- agora Eu tenho que contar. 

Zero, um, dois, três, quatro, cinco, seis, sete. Parece que o 90 é a memória do número de endereço de sete. Todas estas flechas são é como um pequeno pedaço de papel que está dando instruções para o programa que diz que siga este mapa para chegar ao local de sete. E lá você vai encontrar o segunda pontuação do questionário do estudante. Enquanto isso, o 75-- se eu continuar com este, este é sete, oito, nove, 10, 11, 12, 13, 14, 15. 

Esta outra seta representa apenas um mapa para localização de memória 15. Mas, novamente, o programador geralmente faz não se preocupam com este nível de detalhe. E na maioria cada programação linguagem de hoje, o programador nem vai saber onde na memória esses números realmente são. Tudo o que ele ou ela tem que se preocupam com o que eles são de alguma forma ligada em conjunto numa estrutura de dados como este. 

Mas acontece que não ficar muito técnico. Mas só porque nós podemos, talvez, dar ao luxo de ter essa discussão aqui, suponha que nós revisitar esta questão aqui de uma matriz. Vamos ver se nós lamentamos indo para lá. Esta é de 100, 90, 75, e 80. 

Deixe-me fazer brevemente esta reivindicação. Esta é uma matriz, e de novo, o característica marcante de uma matriz é que todos os seus dados está de volta ao de volta para trás em memory-- literalmente Um byte ou talvez quatro bytes, um número fixo de bytes de distância. Em uma lista ligada, o que poderíamos chamar assim, debaixo do capô que sabe onde esse material é? Ele nem sequer precisam fluir como este. Alguns dos dados pode ser de volta para a esquerda até lá. Você nem sequer sabe. 

E assim, com uma matriz, você tem um recurso conhecido como acesso aleatório. E o que os meios de acesso aleatório é que o computador pode saltar instantaneamente para qualquer local em uma matriz. Por quê? Porque o computador sabe que é a primeira localização zero, um, dois e três. 

E então se você quiser ir de este elemento para o elemento seguinte, você literalmente, na A mente de computador, basta adicionar um. Se você quer ir para o terceiro elemento, basta adicionar um-- próximo elemento, apenas Adicione um. No entanto, nesta versão da história, suponha o computador está visitando ou em lidar com o número 100. Como você chegar ao próximo grau no livro de notas? 

Você tem que tomar sete etapas, que é arbitrária. Para chegar ao próximo, você tem que levar mais oito passos para chegar a 15. Em outras palavras, não é um lacuna constante entre os números, e por isso só leva o computador mais tempo é o ponto. O computador tem de procurar através da memória, a fim para encontrar o que você está procurando. 

Assim, enquanto uma matriz tende a ser um structure-- rápida de dados porque você pode literalmente apenas fazer aritmética simples e chegar onde você quer pela adição de um, para instance-- uma lista ligada, você sacrifica esse recurso. Você não pode simplesmente ir de primeira para a segunda a terceira para a quarta. Você tem que seguir o mapa. Você tem que tomar mais medidas para chegar a esses valores, que parece ser a adição de um custo. Então, nós estamos pagando um preço, mas o que era o recurso que Dan estava procurando aqui? O que faz uma lista ligada aparentemente, nos permitem fazer, qual foi a origem da esta história em particular? 

Exatamente. Um tamanho dinâmico para isso. Podemos acrescentar a esta lista. Podemos até mesmo diminuir a lista, para que só está usando o máximo de memória como nós queremos realmente e assim estamos nunca over-reparte. 

Agora é só para ser realmente nit-exigente, há um custo escondido. Então você não deve me deixar convencer que este é um compromisso convincente. Há um outro custo escondido aqui. O benefício, para ser claro, é que nós começamos dinamismo. Se eu quiser um outro elemento, só pode desenhá-lo e colocar um número lá. E então eu posso ligá-la com uma imagem aqui, enquanto aqui, novamente, se eu tenho pintou-me em um canto, se alguma coisa já está usando a memória aqui, estou fora da sorte. Pintei-me para o canto. 

Mas o que é o oculto custar nesta foto? Não é apenas a quantidade de tempo que leva para ir daqui até aqui, que é de sete passos, em seguida oito etapas, que é mais do que um. O que é um outro custo oculto? Não apenas tempo. Informações adicionais estão necessário para atingir esse quadro. 

Sim, esse mapa, esses pequenos pedaços de papel, como eu manter descrevendo-os como. Estes arrows-- aqueles que não são livres. A Computador-- você sabe o que um computador tem. Ele tem zeros e uns. Se você deseja representar uma flecha ou um mapear ou um número, você precisa de alguma memória. Então, no outro preço que você pagar por uma lista ligada, a ciência da computação comum de recursos, é também espaço. 

E de fato assim, tão comumente, Entre as compensações na concepção de engenharia de software sistemas é o tempo e espaço-- são dois dos seus ingredientes, dois dos seus ingredientes mais caros. Isso está me custando mais tempo porque eu tenho que siga este mapa, mas também está me custando mais espaço porque eu tenho que manter este mapa ao redor. Assim, a esperança, como nós tipo de discutido sobre ontem e hoje, é que os benefícios irá superam os custos. 

Mas não há nenhuma solução óbvia aqui. Talvez seja melhor-- a la rápida e suja, como Kareem proposta earlier-- para jogar memória ao problema. Basta comprar mais memória, pensar menos duro sobre como resolver o problema, e resolvê-lo de uma forma mais fácil. E, de fato antes, quando falamos sobre compensações, não havia espaço em o computador e tempo. Era hora desenvolvedor, que é ainda um outro recurso. 

Então, novamente, é este ato de equilíbrio tentando decidir qual dessas coisas você está disposto a gastar? Qual é o menos caro? Que produz os melhores resultados? Sim? 

De fato. Neste caso, se você estiver representando números na maps-- estes são chamados em muitas línguas "ponteiros" ou "endereços" - que é o dobro do espaço. Isso não precisa ser tão ruim quanto o dobro se agora nós estamos apenas armazenar números. Suponha que estavam armazenando registros de pacientes em um hospital-- assim nomes de Pierson, números de telefone, números de segurança social, médico história. Esta caixa pode ser muito, muito maior, em cujo caso um pouco ponteiro minúsculo, o endereço do a próxima element-- não é um grande negócio. É um tal franja custo, não importa. Mas neste caso, sim, é uma duplicação. Boa pergunta. 

Vamos falar sobre o tempo que um pouco mais concretamente. Qual é o tempo de execução de pesquisar esta lista? Suponha que eu queria para procurar através de todas as notas dos alunos, e há n graus nesta estrutura de dados. Aqui, também, podemos tomar emprestado o vocabulário da anterior. Esta é uma estrutura de dados linear. 

Big O de n é o que é necessário para obter para o fim da presente estrutura de dados, whereas-- e não vimos este antes-- uma matriz dá-lhe o que é chamado de tempo constante, o que significa um passo ou dois passos ou 10 steps-- não importa. É um número fixo. Não tem nada a ver com o tamanho da matriz. E a razão para isso, mais uma vez, é de acesso aleatório. O computador pode apenas imediatamente saltar para outro local, porque eles são todos iguais distância de tudo o resto. Não há nenhum pensamento envolvido. Tudo certo. Então, se eu puder, deixe-me tentar pintar dois quadros finais. Um muito comum conhecida como uma tabela hash. Então, para motivar a discussão, deixe-me pensar sobre como fazer isso. 

Assim como sobre isso? Suponha-se que o problema queremos resolver agora está a implementar em um dictionary-- por isso um monte de palavras em inglês como queiras. E o objectivo é o de ser capaz de responder perguntas do formulário esta é uma palavra? Então você quer implementar um corretor ortográfico, apenas como um dicionário física que você pode olhar as coisas em. Suponha que eu fosse fazer isso com uma matriz. Eu poderia fazer isso. 

E supor que as palavras são de maçã e banana e melão. E eu não posso pensar de frutas que começam com d, então estamos apenas vai ter três frutas. Portanto, este é um array, e estamos armazenar todas estas palavras neste dicionário como uma matriz. A questão, então, é de que outra forma você pode armazenar esta informação? 

Bem, eu sou o tipo de batota aqui, porque cada uma dessas letras da palavra é realmente um byte individual. Então, se eu realmente queria ser nit-exigente, eu realmente deveria ser dividindo este se em muito pequenos pedaços de memória, e poderíamos fazer exatamente isso. Mas nós estamos indo funcionar em o mesmo problema que antes. E se, como Merriam Webster ou Oxford faz cada ano-- que adicionar palavras ao dictionary-- nós não necessariamente quer nos pintar em um canto com uma matriz? 

Então, ao invés, talvez uma abordagem mais inteligente é colocar a maçã no seu próprio nó ou caixa, como diríamos, banana, e então aqui temos melão. E corda que essas coisas juntas. Portanto, esta é a matriz, e esta é a lista ligada. Se você não consegue ver, ele só diz "matriz", e isso diz "lista." 

Portanto, temos a mesma questões exatas como antes, pelo qual agora temos dinamismo na nossa lista ligada. Mas temos um dicionário bastante lento. Suponha que eu queira procurar uma palavra. Pode me levar grande O de n passos, porque a palavra pode ser todo o caminho no final de a lista, como melão. E verifica-se que na programação, sort do santo graal dos dados estruturas, é algo que lhe dá constante tempo como uma matriz mas que ainda lhe dá dinamismo. 

Assim, podemos ter o melhor dos dois mundos? E, de fato, há algo chamada tabela hash que permite que você faça exatamente que, ainda que aproximadamente. Uma tabela é um columbófilo estrutura de dados que nós pode pensar em como a combinação de um array-- e eu vou desenhá-lo como isto-- e listas ligadas que eu vou desenhar como este aqui. 

E a maneira como essa coisa obras é como se segue. Se este agora-- de hash mesa-- é minha estrutura de dados de terceira, e eu quero armazenar palavras neste, eu não faço quero apenas armazenar todas as palavras de volta para trás a volta para trás. Quero aproveitar algumas pedaço de informação sobre as palavras que lhe permitirão me obtê-lo onde é mais rápido. 

Assim, dada a maçã palavras e banana e melão, Eu deliberadamente escolheu essas palavras. Por quê? O que é uma espécie de fundamentalmente diferente sobre os três? Qual é o óbvio? Eles começam com letras diferentes. 

Então você sabe o quê? Em vez de colocar todas as minhas palavras o mesmo balde, por assim dizer, como em uma lista grande, por que não fazer Eu, pelo menos, tentar uma otimização e fazer minhas listas de 1/26 do tempo. A otimização convincente pode ser por que não fazer Eu-- ao inserir uma palavra para essa estrutura de dados, na memória do computador, por isso Não coloquei todas as palavras "a" aqui, tudo 'B' palavras aqui, e todos os "c" palavras aqui? Então isso acaba colocando uma maçã aqui, banana aqui, melão aqui, e assim por diante. 

E se eu tiver um adicional palavra como-- o que é outro? Maçã, banana, pêra. Qualquer um pensa de uma fruta que começa com a, b, ou c? perfeita Blueberry--. Isso vai acabar aqui. E assim parece que temos um marginalmente melhor solução, porque agora se eu quiser para procurar maçã, I first-- Eu não apenas mergulho em minha estrutura de dados. Eu não mergulho na memória do meu computador. I primeiro olhar para a primeira letra. 

E isso é o que um computador cientista diria. Você botar em sua estrutura de dados. Você toma sua entrada, o que, neste caso, é uma palavra como maçã. Você analisá-lo, olhando para a primeira letra neste caso, hashing-o assim. Hashing é um termo geral em que você toma algo como entrada e você produzir alguma saída. E a saída em que caso é a localização você deseja pesquisar, o primeiro local, segundo local, a terceira. Assim, a entrada é de maçã, a saída é em primeiro lugar. A entrada é de banana, o saída deve ser segundo. A entrada é melão, a saída deve ser o terceiro. A entrada é de mirtilo, o saída deve voltar a ser segundo. E é isso que ajuda a tirar atalhos através de sua memória a fim de obter a palavras ou dados de forma mais eficaz. 

Agora, isso reduz nosso tempo potencialmente por tanto como um de 26, porque se você assumir que você ter tantos "a" palavras como "z" palavras como palavras "q", que não é realmente realistic-- você vai ter a inclinação do outro lado certas letras do alphabet-- mas isso seria um incremental abordagem que não permite -lo a obter a palavras muito mais rapidamente. E, na realidade, um sofisticado programa, os Googles do mundo, o Facebooks do mundo-- eles usariam uma tabela hash para uma série de finalidades diferentes. Mas eles não seria tão ingênuo basta olhar para a primeira letra na maçã ou banana ou pêra ou melão, porque como você pode ver esses listas ainda podia começar por muito tempo. 

E por isso este pode ainda ser tipo de linear-- tão espécie de lento, como com o grande O de n que discutimos anteriormente. Então, o que um verdadeiro tabela hash boa vontade fazer-- ele terá uma variedade muito maior. E vai usar um muito mais função de hash sofisticado, de modo que não basta olhar para o "a". Talvez ele olha para "a-p-p-l-e" e de alguma forma, converte essas cinco letras no local onde maçã deve ser armazenado. Estamos apenas ingenuamente usando a letra 'a' sozinho, porque é agradável e simples. 

Mas uma tabela hash, em Ao final, você pode pensar como uma combinação de uma matriz, cada um dos quais tem uma lista vinculada que idealmente deverá ser tão curto quanto possível. E isso não é uma solução óbvia. De facto, grande parte da sintonização fina o que se passa debaixo do capô quando implementar esses tipos de estruturas de dados sofisticados é o que é o direito comprimento da matriz? Qual é a função hash certo? Como você armazenar coisas na memória? 

Mas perceber o quão rapidamente este tipo de discussão escalada, seja tão longe que é uma espécie de sobre a cabeça neste momento, que está bem. Mas nós começamos, recall, com verdadeiramente algo de baixo nível e electrónicos. E assim este novo é este tema da abstração, onde uma vez que você começar a tomar para concedido, OK, eu tenho ele-- há memória física, OK, tem, cada localização física tem um endereço, OK, I got it, I pode representar esses endereços como arrows-- você pode rapidamente começar a ter conversas mais sofisticados que no final parecem estar nos permitindo para resolver problemas como pesquisar e triagem de forma mais eficaz. E com certeza, demasiado-- porque eu acho que isso é o mais profundo nós fomos em algum destes tópicos CS proper-- Nós feito em um dia e uma metade neste apontar o que você pode geralmente fazer mais o curso de oito semanas em um semestre. 

Quaisquer perguntas sobre estes? Não? Tudo certo. Bem, por que não fazemos uma pausa lá, iniciar o almoço alguns minutos mais cedo, retomar em apenas cerca de uma hora? E eu vou durar um pouco com perguntas. Então eu vou ter que ir levar algumas chamadas, se está tudo OK. Vou ligar uma música, entretanto, mas o almoço deve ser ao virar da esquina.