The King's College (New York) - >> >> PROFESSOR: Tudo bem. Este é CS50 e este é o final de semana três. Então, nós estamos aqui hoje, não em Sanders Theater, em vez de Weidner Library. Dentro dos quais é um estúdio conhecido como Hauser Studio, ou digamos Estúdio H, ou deve nós dizer-- se você gostou que piada, é, na verdade, a partir de colega, Mark, em linha, que sugeriu tanto via Twitter. Agora, o que é legal sobre estar aqui em um estúdio é que eu estou cercado por estes do verde paredes, uma tela verde ou chromakey, por assim dizer, o que significa que de CS50 equipe de produção, sem saber para mim agora, poderia estar colocando me mais em qualquer lugar do mundo, por bem ou por mal. >> Agora, o que temos pela frente, conjunto de problemas dois está em suas mãos para esta semana, mas com conjunto de problemas três da próxima semana, você será desafiado com a chamada de jogo 15, um favor de partido antiga que você pode se lembrar de receber como uma criança que tem um grupo inteiro de números que pode deslizar para cima, para baixo, esquerda e direita, e há um gap dentro do quebra-cabeça, no qual você pode realmente deslizar as peças de quebra-cabeça. Em última análise, você receber essa quebra-cabeça em alguma ordem semi aleatório, e o objectivo é a classificá-lo de cima para baixo, esquerda para a direita, a partir de um todo o caminho até a 15. >> Infelizmente, a aplicação você terá em mãos vai ser software base, não fisicamente. Você está realmente vai ter que escrever código com o qual um estudante ou usuário pode jogar o jogo de 15. E, de fato, em que o hacker edição do jogo de 15, você vai ser um desafio para implementar, não apenas o jogo desta velha escola jogo, mas sim a solução disso, a implementação de modo deus, por assim dizer, que realmente resolve o enigma para o ser humano, fornecendo-lhes dica, depois dica, depois dica. Então, mais sobre isso na próxima semana. Mas isso é o que está por vir. >> Por agora lembrar que no início desta semana tivemos este momento de angústia, se quiserem, pelo que o melhor que estávamos fazendo triagem wise foi um limite superior de grande o de n quadrado. Em outras palavras, bubble sort, tipo de seleção, ordenação por inserção, todos eles, enquanto diferente na sua implementação, transformou em um n ao quadrado que funciona tempo no pior caso. E nós geralmente assumem que o pior caso para classificar é aquele que seus inputs são completamente para trás. E, de fato, levou bastante a poucos passos para implementar cada um desses algoritmos. >> Agora no final da aula recall, nós comparamos bubble sort contra a espécie de selecção contra uma outra que chamamos de merge sort na época, e proponho que ele está tomando vantagem de uma lição de semana zero, dividir e conquistar. E de alguma forma alcançar algum tipo de logarítmica tempo de funcionamento, em última análise, em vez de algo isso é puramente quadrática. E não é bastante logarítmica, é um pouco mais do que isso. Mas se você se lembra de classe, foi muito, muito mais rápido. Vamos dar uma olhada onde paramos. >> Bubble sort contra seleção tipo contra merge sort. Agora eles estão todos correndo, em teoria, ao mesmo tempo. A CPU está sendo executado na mesma velocidade. Mas você pode sentir como chato isso está indo muito rapidamente para se tornar, e quão rápido, quando injetamos um pouco de algoritmos de semana de zero, podemos acelerar as coisas. >> Assim, tipo marca parece incrível. Como podemos aproveitá-lo, a fim para ordenar os números mais rapidamente. Bem, vamos pensar de volta para um ingrediente que nós teve de volta na semana zero, que de procurando por alguém em uma lista telefônica, e lembrar que a pseudocódigo que nos propusemos, através do qual podemos encontrar alguém como Mike Smith, parecia um pouco algo como isto. >> Agora, dê uma olhada em particular na linha 7 e 8, e 10 e 11, que induzem a esse ciclo, pelo que mantivemos voltar para a linha 3 novamente, e novamente, e de novo. Mas acontece que podemos ver esse algoritmo, aqui em pseudocódigo, um pouco mais de forma holística. Na verdade, o que estou procurando a aqui na tela, é um algoritmo para a busca de Mike Smith entre alguns conjunto de páginas. E, de fato, podemos simplificar esta algoritmo nessas linhas 7 e 8, e 10 e 11 a apenas dizer isto, que eu tenho apresentado aqui em amarelo. Em outras palavras, se o Mike Smith é no início do livro, nós não precisa especificar passo a passo agora como ir encontrá-lo. Não temos para especificar voltar para a linha 3, por quê nós não apenas em vez disso, digamos, mais geralmente, procurar Mike no metade esquerda do livro. >> Por outro lado, se o Mike é na verdade, no final do livro, por que não podemos apenas citar pesquisa unquote para Mike na metade direita do livro. Em outras palavras, por que não acabamos tipo de punt para nós mesmos dizendo: procurar Mike neste subconjunto do livro, e deixá-lo para a nossa existente algoritmo para nos dizer como a busca de Mike em que a metade esquerda do livro. Em outras palavras, o nosso algoritmo funciona se é um livro de telefone desta espessura, desta espessura, ou qualquer espessura que seja. Assim, podemos de forma recursiva definir este algoritmo. Em outras palavras, no tela aqui, é um algoritmo para a busca de Mike Smith entre as páginas de um livro de telefone. Assim, na linha 7 e 10, vamos apenas dizer exatamente isso. E eu uso este termo num momento atrás, e de fato, recursão é a palavra de ordem, por enquanto, e é este processo de fazer algo por alguma forma cíclica usando o código que você já tem, e chamando-o de novo, e mais uma vez, e novamente. Agora ele vai ser importante que de alguma forma inferior para fora, e não fazer isso infinitamente longo. Caso contrário, vamos têm, na verdade um loop infinito. Mas vamos ver se podemos emprestar essa idéia de uma recursão, fazendo algo de novo e de novo e de novo, para resolver o problema de ordenação através de mesclagem tipo, tanto mais eficiente. >> Então, eu dar-lhe-merge sort. Vamos dar uma olhada. Então aqui é pseudocódigo, com que poderíamos implementar a triagem, usando este algoritmo chamado merge sort. E é simplesmente isso. Sobre a entrada de n elementos, em outras palavras, se você estiver dado n elementos e números e cartas ou qualquer que seja a entrada é, se você está dado n elementos, se n é inferior a 2, apenas voltar. Certo? Porque se n é inferior a 2, que significa que a minha lista de elementos ou é de tamanho 0 ou 1, e em ambos desses casos triviais, a lista já está classificado. Se não existe uma lista, está classificado. E se há uma lista de comprimento 1, é obviamente classificadas. Assim, o algoritmo precisa apenas realmente fazer algo interessante, se temos dois ou mais elementos que nos foi dado. Então, vamos olhar para a magia então. Logo classificar a metade esquerda dos elementos, em seguida, classificar a metade direita de elementos, em seguida, mesclar as metades classificados. E o que é tipo de mente dobra aqui, é que eu realmente não parecem ter-lhe dito nada ainda, certo? Tudo o que eu disse é, dada uma lista de n elementos, ordenar a metade esquerda, em seguida, a metade direita, em seguida, mesclar as metades ordenados, mas onde está o segredo real? Onde está o algoritmo? Bem, acontece que essas duas linhas primeiro, metade deixou tipo de elementos, e tipo certo de metade dos elementos, são chamadas recursivas, por assim dizer. >> Apesar de tudo, neste ponto no tempo, eu tenho um algoritmo com a qual a classificar um monte de elementos? Sim. Está bem aqui. É aqui mesmo na tela, e para que eu possa usar o mesmo conjunto de passos para classificar a metade esquerda, como eu posso a metade direita. E, de fato, mais uma vez, e outra vez. Então, de alguma forma ou de outra, e nós vamos em breve ver isso, a magia de merge sort é incorporado em que muito definitiva linha, a fusão das metades ordenados. E isso parece bastante intuitivo. Você pega duas metades, e você, de alguma forma, fundi-las, e vamos ver isso concretamente em um momento. >> Mas este é um algoritmo completo. E vamos ver exatamente o porquê. Bem supor que nós estamos dando esses mesmos oito elementos aqui na tela, um através de oito, mas eles são em ordem aleatória. E o objetivo em questão é para classificar estes elementos. Bem, como eu posso ir sobre fazê-lo usando, novamente, merge sort, de acordo com este pseudo-código? E, novamente, incutir isso em sua mente, apenas por um momento. O primeiro caso é bastante trivial, se for inferior a 2, basta retornar, não há trabalho a ser feito. Então, realmente há apenas três passos para realmente manter em mente. Mais uma vez, e de novo, eu sou vai querer ter para classificar a metade esquerda, ordenar a metade direita, e, em seguida, uma vez que sua duas metades são classificadas, Eu quero fundi-las em uma lista ordenada. Portanto, manter isso em mente. >> Então aqui está a lista original. Vamos tratar isso como uma array, como nós começamos a na semana dois, que é um bloco contíguo de memória. Neste caso, contendo oito números, back to back to back. E vamos agora aplicar merge sort. Então, primeiro eu quero classificar a metade esquerda da lista, e vamos, portanto, concentrar em 4, 8, 6, e 2. >> Agora, como eu vou sobre ordenar uma lista de tamanho 4? Bem eu tenho que considerar agora triagem esquerda da metade esquerda. Mais uma vez, vamos retroceder por um momento. Se o pseudocódigo é isso, e eu estou determinado oito elementos, 8 é obviamente maior que ou igual a 2. Assim, com o primeiro caso não se aplica. Assim, para classificar oito elementos, eu primeiro ordenar a metade esquerda de elementos, então eu ordenar a metade direita, então eu mesclar as duas metades, cada uma das ordenadas tamanho 4. ESTÁ BEM. >> Mas se você acabou de me dizer, ordenar a metade esquerda, que agora é de tamanho 4, como faço para classificar a metade esquerda? Bem, se eu tenho uma entrada de quatro elementos, I primeiro classificar à esquerda dois, então os dois direita, e então eu fundi-las. Então, novamente, torna-se um pouco de uma mente dobra jogo aqui, porque você, tipo, tem que lembre-se onde você está na história, mas no final do dia, dada qualquer número de elementos, primeiro você deseja classificar a metade esquerda, em seguida, a metade direita, em seguida, fundi-las. Vamos começar a fazer exatamente isso. Aqui é a entrada de oito elementos. Agora nós estamos olhando para a metade esquerda aqui. Como faço para classificar quatro elementos? Bem, eu primeiro classificar a metade esquerda. Agora como faço para classificar a metade esquerda? Bem, eu tenho dado dois elementos. Então, vamos resolver estes dois elementos. 2 é maior do que ou igual a 2, é claro. Assim que o primeiro caso não se aplica. >> Então, eu agora tenho que classificar a esquerda metade destes dois elementos. A metade esquerda, é claro, está apenas a 4. Então, como faço para classificar uma lista de um elemento? Bem, agora, que caso base especial em cima, por assim dizer, se aplica. 1 é inferior a 2, e o meu lista é realmente de tamanho 1. Então, eu só retornar. Eu não faço nada. E, de fato, olha o que eu tenho feito, quatro já estão classificados. Como eu já estou parcialmente bem sucedido aqui. >> Agora que parece uma espécie de idiota para reclamar, mas é verdade. 4 é uma lista de tamanho 1. Ele já está classificado. Isso é a metade esquerda. Agora eu ordenar a metade direita. Minha entrada é um elemento, 8 Da mesma forma, já classificados. Estúpido, também, mas, novamente, este princípio básico vai permitir-nos construir agora em cima deste com sucesso. 4 classificado, 8 é classificado, agora Qual foi a última etapa? Assim, o terceiro e último passo, qualquer vez que você está classificando uma lista, recall, era fundir as duas metades, à esquerda e à direita. Então, vamos fazer exatamente isso. Meu metade esquerda é, naturalmente, 4. Meu metade direita é 8. >> Então, vamos fazer isso. Primeiro eu vou para alocar alguma memória adicional, que eu vou representar aqui, como apenas uma matriz secundária, que é grande o suficiente para caber isso. Mas você pode imaginar que se estende retângulo que todo o comprimento, se precisarmos de mais tarde. Como faço para fazer 4 e 8, e mesclar essas duas listas de tamanho 1 juntos? Aqui, também, bastante simples. 4 vem primeiro, depois vem 8. Porque se eu quiser classificar a metade esquerda, em seguida, a metade direita, e, em seguida, mesclar essas duas metades juntos, na ordem de classificação, 4 vem primeiro, depois vem 8. >> Então, parece que estamos a fazer progressos, mesmo embora eu não tenha feito qualquer trabalho real. Mas lembre-se onde estamos na história. Nós originalmente levou oito elementos. Separamos a metade esquerda, que é 4. Então nós ordenamos a metade esquerda da metade esquerda, que era de 2. E aqui vamos nós. Nós somos feitos com esse passo. >> Então, se temos classificados o à esquerda metade 2, agora nós tem que classificar a metade direita de 2. Assim, a metade direita 2 está estes dois valores aqui, 6 e 2. Então, vamos agora dar uma entrada de tamanho 2, e ordenar a metade esquerda e, em seguida a metade direita, e, em seguida, fundi-las. Bem como faço para classificar uma lista de tamanho 1, que contém apenas o número 6? Eu já estou feito. Essa lista de tamanho 1 é ordenada. >> Como faço para classificar uma outra lista de tamanho 1, o assim chamado metade direita. Bem, também, já está classificado. O número 2 está sozinho. Então agora eu tenho duas metades, esquerda e certo, eu preciso fundi-las. Deixe-me dar-me um pouco de espaço extra. E colocá-2 em lá, em seguida, 6 de lá, assim classificando essa lista, esquerda e direita, e fundindo-lo juntos, em última instância. Então, eu estou em um pouco melhor forma. Eu não sou feito, porque claramente 4, 8, 2, 6 não é a ordenação final que eu quero. Mas agora tenho duas listas de tamanho 2, que ambos têm, respectivamente, foram classificadas. Portanto, agora se você retroceder em sua mente de olho, onde é que isso nos deixa? Comecei com oito elementos, então eu talhou-lo para baixo para a metade esquerda do 4, em seguida, a metade esquerda 2, e em seguida, a metade direita da 2, Eu terminei, portanto, a triagem esquerda metade de 2, e a metade direita de 2, então qual é o terceiro e último passo aqui? Eu tenho que fundir-se duas listas de tamanho 2. Então, vamos em frente. E na tela aqui, dar- me alguma memória adicional, embora tecnicamente, repare que eu tenho tem um monte de espaço em branco em cima há. Se eu quiser ser especialmente espaço eficiente sábio, Eu poderia simplesmente começar a mover os elementos e para trás, superior e inferior. Mas apenas para maior clareza visual, Vou colocá-lo lá em baixo, para manter as coisas agradável e limpo. >> Então eu tenho duas listas de tamanho 2. A primeira lista tem 4 e 8. A segunda lista tem 2 e 6. Vamos mesclar aqueles juntos na ordem de classificação. 2, é claro, vem em primeiro lugar, em seguida, 4, 6, em seguida, em seguida, 8. E agora parece que estamos recebendo em algum lugar interessante. Agora eu tenho metade classificadas da lista, e coincidentemente, é Todos os números pares, mas isso é, na verdade, apenas uma coincidência. E eu agora ter resolvido a esquerda metade, de modo que é 2, 4, 6, e 8. Nada está fora de ordem. Que se sente como progresso. >> Agora parece que eu tenho falado para sempre agora, Então, o que continua a ser visto se isso algoritmo é, na verdade, mais eficiente. Mas estamos passando por super metodicamente. Um computador, é claro, iria fazê-lo assim. Então, onde estamos? Começamos com oito elementos. Separei a metade esquerda da 4. Eu pareço ser feito com isso. Portanto, agora o próximo passo é ordenar a metade direita 4. E esta parte podemos ir através de um pouco mais rapidamente, embora você é bem-vindo para retroceder ou pausar, apenas acho que por ele em seu próprio ritmo, mas o que que temos agora é uma oportunidade para fazer o mesmo algoritmo exato em quatro números diferentes. >> Então vamos em frente, e se concentrar em a metade direita, que estamos aqui. A metade esquerda do referido metade direita, e agora o metade esquerda da esquerda metade do que a metade direita, e como faço para classificar uma lista de tamanho 1 contendo apenas o número 1? Está feito. Como eu faço o mesmo para uma lista de tamanho 1 contendo apenas 7? Está feito. Passo três para metade, em seguida, esta é para mesclar esses dois elementos em uma nova lista de tamanho 2, 1 e 7. Não parecem ter feito tudo que muito trabalho interessante. Vamos ver o que acontece em seguida. Eu só ordenados a metade esquerda do metade direita da minha entrada original. Agora vamos classificar a direita meio, que contém 3 e 5. Vamos de novo olhar para a esquerda metade, classificado, metade direita, classificado, e mesclar os dois juntos, em algum espaço adicional, 3 vem primeiro, depois vem 5. E agora, temos classificados o metade esquerda da metade direita do problema original, e a metade direita da metade direita do problema original. O que é a terceira e última etapa? Bem, para mesclar essas duas metades juntas. Então me deixe ter algum espaço extra, mas, novamente, eu poderia estar usando aquele espaço em cima de reposição. Mas nós estamos indo para mantê- o simples visualmente. Deixe-me agora fundem-se em um, e em seguida, 3, 5 e, em seguida, e em seguida 7. Assim, me deixando agora com a metade direita do problema original Isso é perfeitamente ordenadas. >> Então o que resta? Eu sinto que eu continuo dizendo a mesmas coisas de novo, e de novo, mas isso é um reflexo do fato de que estamos usando recursão. O processo de utilização de um algoritmo de novo, e de novo, em subconjuntos mais pequenos de o problema original. Então, agora tenho uma esquerda classificadas metade do problema original. Eu tenho uma meia ordenada direita do problema original. Qual é a terceira e última etapa? Oh, ele está fundindo. Então, vamos fazer isso. Vamos alocar algum adicional memória, mas meu deus, nós poderia colocá-lo em qualquer lugar agora. Temos muito espaço disponível para nós, mas vamos mantê-lo simples. Em vez de ir para trás e adiante com nossa memória original, vamos fazê-lo visualmente aqui abaixo, para terminar a fusão metade esquerda e metade direita. >> Assim, através da fusão, o que eu preciso fazer? Eu quero ter os elementos em ordem. Então, olhando para o lado esquerdo, Eu vejo o primeiro número é 2. Eu olho para a metade direita, Eu vejo o primeiro número é 1, então obviamente que número que eu quero arrancar, e colocar em primeiro lugar na minha lista final? Naturalmente, 1. Agora eu quero fazer a mesma pergunta. Na metade esquerda, eu tenho ainda tem o número 2. Na metade direita, Eu tenho o número 3. Qual deles eu quero escolher? Claro, número 2 E Agora observe os candidatos 4 estão à esquerda, à direita 3. Vamos, naturalmente, escolher três. Agora, os candidatos são 4 na a esquerda, 5, à direita. Nós, é claro, escolher quatro. 6, à esquerda, à direita 5. Nós, é claro, escolher 5. 6 do lado esquerdo, do lado direito 7. Nós escolhemos seis, e então nós escolher 7, e, em seguida, nós escolhemos 8. Voila. >> Assim, um grande número de palavras mais tarde, ter resolvido esta lista de oito elementos em uma lista de um a oito, que está aumentando a cada passo, mas quanto tempo fez leva-nos a fazer isso. Bem, eu tenho deliberadamente coisas estabelecidas pictorially aqui, para que possamos tipo de ver ou apreciar a divisão na conquista que está acontecendo. >> Na verdade, se você olhar para trás na esteira, Eu deixei todas essas linhas pontilhadas em suportes do lugar, você pode, tipo de, veja, em ordem inversa, se você tipo de olhar para trás em história agora, meu lista original é, é claro, de tamanho 8. E, em seguida, anteriormente, eu estava lidando com duas listas de tamanho 4, e, em seguida, quatro listas de tamanho 2, e, em seguida, oito listas de tamanho 1. >> Então, o que faz isso, tipo de, lembra? Bem, na verdade, qualquer de os algoritmos Nós olhou, até agora, onde nós dividir e dividir, e se dividem, continuo a ter as coisas novamente, e novamente, resulta nessa idéia geral. E então há algo logarítmica acontecendo aqui. E não é muito de log n, mas há um componente logarítmica com o que acabou de fazer. >> Agora vamos considerar como isso realmente é. Então log de n, novamente foi um grande tempo de execução, quando fizemos algo como busca binária, como agora chamá-lo, a estratégia de dividir para conquistar via que encontramos Mike Smith. Agora tecnicamente. Isso é log base dois de n, mesmo embora na maioria das classes de matemática, 10 é geralmente a base que você assume. Mas cientistas da computação quase sempre pensar e falar em termos de base 2, assim que nós geralmente apenas dizer log de N, em vez de log de base 2 de N, mas eles são exatamente um eo mesmo no mundo do computador ciência, e como um aparte, há um fator constante diferença entre os dois, de modo que é moot de qualquer maneira, por razões mais formais. >> Mas, por agora, o que nós nos importamos é sobre este exemplo. Então não vamos provar por exemplo, mas em menos usar um exemplo dos números na mão como uma verificação de sanidade, se você quiser. Assim, a fórmula anteriormente foi log de base 2 de N, mas o que é n neste caso. Eu tinha números de n originais, ou 8 do número original especificamente. Agora ele tem sido um pouco enquanto, mas estou bastante Certifique-se que a base de log 2 do valor 8 é 3, e, na verdade, o que é bom sobre o que é 3 que é exactamente o número de vezes que você pode dividir uma lista comprimento de 8, e novamente, e outra vez, até que você é deixado com listas de apenas um tamanho. Certo? 8 vai para 4, vai para 2, vai para 1, e isso é reflexivo do que exatamente imagem, tivemos apenas um momento atrás. Então, um pouco de sanidade verificar de onde o logaritmo é realmente envolvidos. >> Então, agora, o que mais está envolvido aqui? n. Então, observe que cada vez que dividir a lista, embora na ordem inversa na história aqui, eu ainda estava fazendo as coisas n. Isso exige que a fusão etapa Eu toco a cada um dos números, a fim de deslize- a sua localização adequada. Assim, mesmo que a altura desta diagrama é de tamanho de log n de n ou 3, Especificamente, em outras palavras, Eu fiz três divisões aqui. Quanto trabalho que eu fiz na horizontal ao longo desta carta de cada vez? >> Bem, eu fiz n passos de trabalhar, porque se eu tenho tem quatro elementos e quatro elementos, e eu preciso fundi-las. Eu preciso passar por estes quatro e estes quatro, finalmente, para fundi-los de volta em oito elementos. Se por outro lado eu tenho oito dedos aqui, o que eu não faço, e oito fingers-- sorry-- Se eu tenho tem quatro dedos aqui, que eu faço, quatro dedos aqui, o que eu faço, então isso é o mesmo exemplo como antes, se eu fizer tem oito dedos embora em total, o que eu posso, tipo, fazer. Eu posso exatamente fazer aqui, então eu posso certamente mesclar todas estas listas de tamanho 1, em conjunto. Mas eu certamente tem que olhar em cada elemento de uma única vez. Então, a altura deste processo é o log N, a largura do presente processo, por assim dizer, é n, então o que nós parecemos ter, em última instância, é uma duração de tamanho n vezes log n. >> Em outras palavras, dividimos lista, log n vezes o, mas cada vez que fizemos isso, tivemos para tocar a cada um dos elementos a fim de fundi-los todos juntos, o que n para etapa foi, por isso temos n vezes log n, ou como um cientista da computação diria, assintoticamente, que seria a grande palavra para descrever o superior vinculado em um tempo de execução, estamos executando em um grande o de log n tempo, por assim dizer. >> Agora, isso é significativo, porque recordar que os tempos de execução foram com bubble sort, e seleção tipo e ordenação por inserção, e até mesmo alguns outros que existem, n ao quadrado era onde estávamos. E você pode, tipo, ver este aqui. Se n ao quadrado é, obviamente, n vezes n, mas aqui temos n vezes log n, e já sabemos a partir da semana zero, que log n, a logarítmica, é melhor do que algo linear. Afinal, recordar a imagem com o vermelho eo amarelo e as linhas verdes que tirou, a logarítmica linha verde era muito menor. E, portanto, muito melhor e mais rápido que as linhas amarelas e vermelhas em linha reta, n vezes log n é, de fato, melhor que n vezes n, ou n ao quadrado. >> Então, parece que temos identificou um algoritmo merge tipo que é executado em muito tempo mais rápido, e na verdade, é por isso que, no início desta semana, quando vimos que disputa entre bolha tipo, espécie de seleção, e mesclar sort, merge sort realmente, realmente ganhou. E, de fato, nós não mesmo esperar para bubble sort e seleção espécie terminar. >> Agora vamos dar uma outra passagem para isso, a partir de um pouco mais perspectiva formal, apenas em caso, isso ressoa melhor que maior do que o nível de discussão. Então aqui está o algoritmo novamente. Vamos nos perguntar: o que o tempo de execução é deste algoritmos várias etapas? Vamos dividi-lo em primeiro caso e no segundo caso. A SE ea outra pessoa no caso IF, Se n for inferior a 2, apenas voltar. Se sente como tempo constante. É, tipo, como dois passos, Se n for inferior a 2, em seguida, voltar. Mas, como dissemos na segunda-feira, constante de tempo, ou grande o de 1, pode ser dois, três passos passos, até 1.000 passos. O que importa é que é um número constante de passos. Assim, o amarelo destaque pseudocódigo aqui é executado em, vamos chamá-lo, constante de tempo. Então, mais formalmente, e vamos a-- este será a extensão em que nós formalizar este direito agora-- T de n, o tempo de execução de um problema que leva n qualquer coisa como entrada, igualam o o de um, Se n for menor do que 2. Portanto, é condicionada a isso. Então, para ser claro, se n for inferior a 2, temos uma lista muito curta, então o tempo de execução, de t n, em que n é 0 ou 1, neste caso muito específico, ele só vai ser de tempo constante. Vai levar um passo, dois passos, que seja. É um número fixo de etapas. >> Assim, a parte suculenta certamente deve estar em no outro caso no pseudocódigo. O caso MAIS. Ordenar metade esquerda de elementos, tipo certo metade dos elementos, fundir metades ordenados. Quanto tempo dura cada uma dessas etapas tomar? Bem, se a corrida tempo para resolver n elementos é, vamos chamá-lo muito genericamente, T de N, em seguida, a triagem esquerda metade dos elementos é, tipo, como dizer, T de n dividido por 2, e da mesma forma classificando a metade direita de elementos é, tipo, como dizer, T de N 2 dividido e, em seguida fundindo as metades classificados. Bem, se eu tenho algum número de elementos aqui, como quatro, e algum número de elementos aqui, como quatro, e eu tenho que fundir cada um destes quatro em, e cada um destes quatro, um depois o outro, de modo que em última análise, eu tenho oito elementos. Ela se sente como que é grande o de n passos? Se eu tenho n dedos e cada um eles tem que ser incorporada lugar, que é como mais n passos. >> Então, na verdade, como uma fórmula, podemos expressar isso, embora um pouco assustadoramente em primeiro vista, mas é algo que capta exatamente essa lógica. O tempo de execução, T de n, n IF é maior do que ou igual a 2. Neste caso, o caso MAIS, é T de n dividido por dois, além de T n dividido por 2, mais grande o de n, alguns linear número de passos, talvez exatamente n, talvez 2 vezes n, mas é mais ou menos, a ordem de n. De modo que, também, é como podemos expressar isso como uma fórmula. Agora você não saberia isso a menos você gravou em sua mente, ou procurá-lo no traseira de um livro, que poderia ter um pouco cábula no final, mas este é, de fato, vai dá-nos um grande o de n log n, porque a recorrência que você está vendo aqui na tela, se você realmente fez isso para fora, com um número infinito de exemplos, ou você fez isso como uma fórmula, você faria ver que esta, porque esta fórmula em si é recursivo, com t de n sobre algo à direita, e t de N ao longo do lado esquerdo, isto pode na verdade, ser expresso, em última análise, tão grande para ir de log n n. Se não está convencido, isso é bem por agora, apenas assumir a fé, que é, de fato, o que leva a que a recorrência, mas este é apenas um pouco mais de um abordagem matemática para olhar no tempo de execução de merge sort com base apenas na sua pseudocódigo. >> Agora vamos dar um pouco de respiradouro de tudo isso, e dar uma olhada em um certo ex-senador, que pode parecer um pouco familiarizado, que sentou-se com Eric do Google Schmidt, há algum tempo, para uma entrevista no palco, na frente de um grupo inteiro de pessoas, falando em última análise, sobre um tópico, que é bastante agora familiar. Vamos dar uma olhada. >> Eric Schmidt: Agora o senador, você está aqui no Google, e eu gosto de pensar no Presidência como uma entrevista de emprego. Agora é difícil conseguir um emprego como presidente. PRESIDENTE OBAMA: Certo. Eric Schmidt: E você é vai fazer agora. Também é difícil conseguir um emprego no Google. PRESIDENTE OBAMA: Certo. >> Eric Schmidt: Temos perguntas, e pedimos nossas perguntas candidatos, e este é de Larry Schwimmer. >> PRESIDENTE OBAMA: OK. >> Eric Schmidt: O quê? Vocês pensam que estou brincando? Está bem aqui. Qual é a maneira mais eficiente de classificar um milhão de 32 bits inteiros? >> PRESIDENTE OBAMA: bom-- Eric Schmidt: Às vezes, talvez eu sinto muito, maybe-- PRESIDENTE OBAMA: Não, não, não, não, não, eu penso-- Eric Schmidt: Isso não é ele-- PRESIDENTE OBAMA: I acho, eu acho que a bolha tipo seria o caminho errado a seguir. Eric Schmidt: Vamos lá. Quem lhe disse isso? ESTÁ BEM. Eu não fiz a ciência da computação on-- >> PRESIDENTE OBAMA: Nós temos temos os nossos espiões lá dentro. PROFESSOR: Tudo bem. Vamos deixar atrás de nós agora o mundo teórica de algoritmos na análise assintótica da mesma, e retornar para alguns tópicos a partir da semana zero e um, e de início para remover algumas rodinhas, Se você for. Para que você realmente entender em última análise, a partir do zero, o que é acontecendo debaixo do capô, quando você escrever, compilar e executar programas. Lembre-se, em particular, que este era o primeiro programa C nós olhamos, um programa canônica, simples das sortes, relativamente falando, em que, imprime, Olá Mundo. E lembro que eu disse, o processo que o código fonte atravessa é exatamente isso. Você pega o seu código-fonte, passar -lo através de um compilador, como Clang, e sai código objeto, que pode parecer como este, zeros e uns que a CPU do computador central unidade de processamento ou cérebro, em última análise, entende. >> Acontece que isso é uma pouco de uma simplificação, que estamos agora em um posição de provocar uma separação para entender o que está realmente sido acontecendo debaixo do capô cada vez que você executa Tinido, ou, mais geralmente, cada vez que você faz um programa, Faça uso e CF 50 IDE. Em particular, o material como este é gerado primeiro, quando você compilar seu programa. Em outras palavras, quando levar o seu código-fonte e compilá-lo, o que é primeiro sendo emitido por Clang é algo conhecido como código de montagem. E, de fato, ele parece exatamente como este. >> Corri um comando no linha de comando anterior. Hello.c Clang de capital traço s, e isso criou um arquivo para mim chamados hello.s, no interior dos quais foram exactamente estes conteúdos, e um pouco mais acima e um pouco mais abaixo, mas eu coloquei o juiciest informações aqui na tela. E se você olhar de perto, você verá pelo menos algumas palavras-chave familiares. Temos principal na parte superior. Temos printf para baixo no meio. E também temos Olá mundo barra invertida n entre aspas abaixo. >> E tudo o mais aqui é instruções de nível muito baixo que a CPU do computador entende. Instruções da CPU que se movem de memória ao redor, que seqüências de carga de memória, e, finalmente, imprimir as coisas na tela. Agora o que acontece embora depois este código assembly é gerado? Em última instância, você faz, de fato, ainda gerar código objeto. Mas os passos que têm realmente vem acontecendo debaixo do capô olhar um pouco mais como este. O código fonte torna-se o código de montagem, que então se torna código objeto, e as palavras-chave aqui são de que, quando você compilar o código fonte, vem para fora do código de montagem, e, em seguida, quando você montar o seu código de montagem, fora vem código objeto. >> Agora Clang é super sofisticado, como um monte de compiladores, e ele faz todas essas etapas juntos, e ele faz não necessariamente saída de qualquer intermediário arquivos que você mesmo pode ver. Ele só compila as coisas, que é o termo geral que descreve todo este processo. Mas se você realmente quer para ser determinado, não há muito mais acontecendo lá também. >> Mas vamos também considerar agora que mesmo esse programa super simples, hello.c, chamado de uma função. Apelou printf. Mas eu não queria escrever printf, de fato, que vem com c, por assim dizer. É um recall função que é declarou em io.h padrão, que é um arquivo de cabeçalho, que é um tema que vamos realmente mergulhar em mais profundidade antes de tempo. Mas um arquivo de cabeçalho é tipicamente acompanhada por um arquivo de código, arquivo de código fonte, de modo muito parecido existe io.h. padrão >> Há algum tempo atrás, alguém, ou de alguém, também escreveu um arquivo chamado io.c padrão, em que as definições efectivas, ou implementações de printf, e cachos de outras funções, são realmente escrito. Assim, dado que, se considerar ter aqui à esquerda, ola.c, que quando compilado, nos dá hello.s, mesmo se Clang não se incomode de poupança em um lugar podemos vê-lo, e que o código de montagem fica montada em hello.o, que é, na verdade, o nome padrão dado sempre que você compilar fonte código em código objeto, mas não são completamente pronto para executá-lo ainda, porque mais um passo tem que acontecer, e tem vem acontecendo durante os últimos semanas, talvez sem o seu conhecimento. >> Especificamente em algum lugar CS50 em IDE, e este, também, vai ser um pouco de um simplificação excessiva por um momento, não é, ou foi em cima de um tempo, um arquivo chamado io.c padrão, que alguém compilados em io.s padrão ou o equivalente, alguém que, em seguida, montado em io.o padrão, ou se vê em um arquivo ligeiramente diferente formato que pode ter um diferente extensão de arquivo completo, mas, em teoria e conceitualmente, exatamente esses passos tinha que acontecer de alguma forma. O que significa dizer, que agora quando estou escrevendo um programa, hello.c, que apenas diz: Olá mundo, e eu estou usando o código de outra pessoa como printf, que foi uma vez em cima de um tempo, em um arquivo chamado io.c padrão, em seguida, de alguma forma eu tenho que tomar minha código objeto, meus zeros e uns, e objeto dessa pessoa código, ou zeros e uns, e de alguma forma vincular-los juntos em um arquivo final, chamado Olá, que tem todos os zeros e os de minha função principal, e todos os zeros e aqueles para printf. >> E, de fato, esse último processo é chamada, ligar o seu código objeto. A saída dos quais é um arquivo executável. Então, na justiça, na final do dia, nada mudou desde uma semana, quando nós primeiro começou a compilar programas. Com efeito, tudo isto tem sido acontecendo debaixo do capô, mas agora estamos em uma posição onde podemos realmente desmembrar essas várias etapas. E, de fato, no final do dia, nós ainda somos à esquerda com zeros e uns, que é realmente uma ótima segue agora a outra capacidade de C, que nós não tivemos a alavancar mais provável até à data, conhecida como operadores bit a bit. Em outras palavras, até o momento, a qualquer hora nós temos tratadas com dados variáveis em C ou em C, nós tivemos coisas como caracteres e carros alegóricos e ins e anseia e duplas e similares, mas todos esses são, pelo menos, oito bits. Temos ainda nunca foi capaz de manipular bits individuais, mesmo que um bit individual, nós sabe, pode representar um 0 e um 1. Agora verifica-se que em C, você pode ter acesso a bits individuais, se você souber a sintaxe, com o qual se chegar a eles. >> Então, vamos dar uma olhada em operadores bit a bit. Então, retratado aqui estão alguns símbolos que nós temos, tipo de, mais ou menos, visto antes. Eu vejo um e comercial, vertical bar, e alguns outros também, e lembrar que ampersand ampersand é algo que temos visto antes. O operador lógico AND, onde você tem dois deles em conjunto, ou o OU lógico operador, onde você tem duas barras verticais. Operadores bit a bit, o que nós vamos veja operar em pedaços individualmente, basta usar um único e comercial, um única barra vertical, o símbolo de acento circunflexo vem em seguida, a pequena til, e depois à esquerda colchete esquerdo suporte, ou suporte direito colchete direito. Cada um deles têm significados diferentes. >> Na verdade, vamos dar uma olhada. Vamos velha escola hoje, e uso uma tela de toque de outrora, conhecido como um quadro branco. E este quadro branco vai nos permitir para expressar alguns símbolos bastante simples, ou melhor, alguns fórmulas bastante simples, que, em seguida, em última análise, nós podemos alavancagem, a fim para acessar indivíduo bits dentro de um programa C. Em outras palavras, vamos fazer isso. Vamos primeiro falar para um momento sobre ampersand, que é o bit a bit operador AND. Em outras palavras, esta é um operador que permite me para ter uma variável do lado esquerdo normalmente, e uma variável da mão direita, ou um valor individual, que se nós E los juntos, me dá um resultado final. Então o que eu quero dizer? Se em um programa, você tem uma variável que armazena um desses valores, ou vamos mantê-lo simples, e apenas escreva zeros e uns individualmente, aqui está como o operador E comercial funciona. 0 0 comercial está indo igual a 0. Agora, por que é isso? >> É muito semelhante ao As expressões booleanas, que temos discutido até agora. Se você acha que depois de tudo, o 0 é false, 0 é falso, falso e falso é, como já discutimos logicamente, também falsa. Então, nós temos 0 aqui também. Se você tomar 0 e comercial 1, bem que, também, vai ser 0, porque para isso expressão à esquerda para ser verdade ou 1, seria necessário para ser verdade e verdade. Mas aqui temos false e verdadeira, ou 0 e 1. Agora, novamente, se temos um E comercial 0, que, também, vai ser 0, e se tivermos um e comercial 1, finalmente temos um bit 1. Portanto, em outras palavras, nós não estamos fazendo nada de interessante com este operador ainda, este operador comercial. É o bit a bit operador AND. Mas estes são os ingredientes através do qual nós podemos fazer coisas interessantes, como veremos em breve. >> Agora vamos olhar apenas o único barra vertical até aqui, à direita. Se eu tiver um bit 0 e I OR-o com, o bit a bit OR operador, outro bit 0, que vai me dar 0. Se eu tomar um bit 0 e OR-lo com um bit 1, então eu estou indo para obter um. E, de fato, apenas para clareza, deixe-me voltar, de modo que minhas barras verticais não são confundidos com 1s. Deixe-me reescrever todos meu 1 é um pouco mais claramente, para que possamos ver ao lado, se eu ter um 1 ou 0, que vai ser um 1, e se eu tiver um 1 ou 1 que, também, vai ser um 1. Assim você pode ver que a lógica OR operador se comporta de maneira muito diferente. Isto dá-me OU 0 0 0 me dá, mas cada outra combinação dá-me uma. Então, enquanto eu tiver um 1 no fórmula, o resultado será uma. >> Em contraste com a E operador, o comercial, só se eu tenho dois números 1 no equação, eu realmente obter um 1. Agora há alguns outros operadores também. Um deles é um pouco mais complicado. Então deixe-me ir em frente e apagar esta para libertar algum espaço. E vamos dar uma olhada no símbolo de acento circunflexo, por apenas um momento. Este é tipicamente um personagem que você pode digitar em seu teclado e segurando Shift em seguida, um dos números em cima de seu EUA teclado. >> Então este é o exclusivo Operador OU, OU exclusivo. Então, nós apenas viu o operador OR. Este é o OR exclusivo do operador. O que é realmente a diferença? Bem, vamos apenas olhar para a fórmula, e usar isto como ingredientes em última instância. 0 XOR 0. Eu vou dizer é sempre 0. Essa é a definição de XOR. XOR 0 1 vai ser 1. 1 XOR 0 vai ser 1, e um XOR 1 vai ser? Errado? Ou não é? Eu não sei. 0. Agora, o que está acontecendo aqui? Bem, pense sobre o nome deste operador. OU exclusivo, de modo a nome, tipo, sugere, a resposta só vai ser 1 se as entradas são exclusivas, exclusivamente diferente. Então, aqui estão as entradas do mesma, de modo que a saída é 0. Aqui as entradas são o mesma, de modo que a saída é 0. Aqui estão as saídas são diferentes, eles são exclusivos, e então a saída é 1. Portanto, é muito semelhante ao E, é muito semelhante, ou melhor, é muito semelhante ao OU, mas apenas de uma forma exclusiva. Este não é um 1, porque temos dois de 1, e não exclusivamente, apenas um deles. Tudo certo. E os outros? Bem o til, entretanto, é realmente agradável e simples, felizmente. E esta é uma unary operador, o que significa é aplicado a apenas uma entrada, um operando, por assim dizer. Não a um esquerdo e um direito. Em outras palavras, se você tomar til de 0, a resposta será o oposto. E se você tomar til de 1, o resposta haverá o oposto. Assim, o operador til é uma forma de negar um pouco, ou virar um pouco de 0 a 1, ou de 1 a 0. >> E isso deixa-nos, finalmente, com apenas dois operadores finais, o chamado deslocamento para a esquerda, e o o chamado operador de deslocamento para a direita. Vamos dar uma olhada em como os trabalhos. O operador de deslocamento para a esquerda, por escrito com dois colchetes como essa, opera como se segue. Se a minha entrada, ou a minha operando, à esquerda operador de deslocamento é simplesmente um 1. E eu, em seguida, dizer ao computador para desvio à esquerda que uma, digamos sete lugares, o resultado é como se eu tomar essa 1, e movê-lo sete lugares mais à esquerda e, por padrão, vamos supor que o espaço à direita vai ser preenchido com zeros. Em outras palavras, uma mudança deixou 7 vai para me dar que 1, seguido por 1, 2, 3, 4, 5, 6, 7 zeros. Então, de certa forma, ele permite que você ter um número pequeno como 1, e torná-lo muito claramente muito, muito maior, desta forma, mas nós estamos indo realmente para ver abordagens mais inteligentes para ele Em vez disso, como bem, >> Tudo certo. É isso por três semanas. Vamos vê-lo na próxima vez. Este foi CS50. >> >> COLUNA 1: Ele estava no snack- bar comendo um sundae de chocolate. Ele tinha tudo sobre o seu rosto. Ele está vestindo que o chocolate como uma barba COLUNA 2: O que você está fazendo? COLUNA 3: Hmmm? O quê? >> COLUNA 2: Você acabou de duplo mergulho? Você dupla mergulhou o chip. COLUNA 3: Desculpe-me. COLUNA 2: Você mergulhou o chip, você deu uma mordida, e você mergulhou novamente. COLUNA 3: COLUNA 2: Assim que é como colocar todo o seu direito boca no mergulho. Da próxima vez que você tomar um chip, apenas mergulhá-lo uma vez, e terminá-la. >> COLUNA 3: Você sabe o que, Dan? Você mergulha a maneira que você quiser mergulhar. Vou mergulhar a maneira que eu quero mergulhar..
Curso de ar condicionado automotivo ms disciplinas do curso de engenharia sanitaria e ambiental Itabira reporter do tempo bom dia brasil. Parnamirim xvi exame de ordem fgv agravo em execucao Declaração Pessoal, bec vantage exam papers download Dissertação, curse mods for wot Apresentação de Power Point, exame cariotipo serve para que Tese. Apresentacao em powerpoint sobre gestao financeira exames de glicemia na gestacao curso de ar condicionado automotivo ms Bacabal art 3 inciso iii cc. Unesp cursos menos concorridos Textos criativos Caieiras abnt de um artigo cientifico, curso de especializacao em seguranca do trabalho em fortaleza.
Pinhais:
Sophia Bell, Schoharie: Union Theological Seminary, Morningside Heights (Columbia University area). Várzea Grande: NYS College of Human Ecology; 2010.
Carol Hoggarth, Oneida County. São Paulo: SUNY Learning Network; 2013.
Alanna Mora, E 11th Street zip 10003. João Pessoa: Orange County Community College; 2007.