1 00:00:00,000 --> 00:00:00,488 2 00:00:00,488 --> 00:00:10,800 >> [Música tocando] 3 00:00:10,800 --> 00:00:13,500 DAVID MALAN: Tudo bem. 4 00:00:13,500 --> 00:00:14,670 Tudo bem, bem-vindo de volta. 5 00:00:14,670 --> 00:00:18,120 Portanto, esta é a Semana 4, o início º, já. 6 00:00:18,120 --> 00:00:21,320 E você vai lembrar que, na semana passada, colocamos código de lado por um pouco 7 00:00:21,320 --> 00:00:24,240 e começamos a conversar um pouco mais de alto nível, sobre coisas como 8 00:00:24,240 --> 00:00:28,130 pesquisa e classificação, que embora ideias são simples, pouco 9 00:00:28,130 --> 00:00:31,840 representativo de uma classe de problemas você vai começar a resolver particularmente 10 00:00:31,840 --> 00:00:34,820 como você começar a pensar em último projetos e soluções interessantes que você 11 00:00:34,820 --> 00:00:36,760 pode ter de problemas do mundo real. 12 00:00:36,760 --> 00:00:39,490 Agora bubble sort é um dos mais simples tais algoritmos, e 13 00:00:39,490 --> 00:00:42,900 Trabalhou por ter estes pequenos números em uma lista ou em um tipo conjunto de 14 00:00:42,900 --> 00:00:46,530 bolha seu caminho até o topo, eo grandes números mover seu caminho até 15 00:00:46,530 --> 00:00:47,930 o fim da lista. 16 00:00:47,930 --> 00:00:50,650 >> E lembrar que pudéssemos visualizar bubble sort um pouco 17 00:00:50,650 --> 00:00:52,310 algo como isto. 18 00:00:52,310 --> 00:00:53,640 Então deixe-me ir em frente e clique em Iniciar. 19 00:00:53,640 --> 00:00:55,350 Eu já pré-selecionado bubble sort. 20 00:00:55,350 --> 00:00:58,920 E se você lembrar que o azul mais alto linhas representam números grandes, pequenas 21 00:00:58,920 --> 00:01:03,300 linhas azuis representam pequenos números, como passamos por isso de novo e de novo e 22 00:01:03,300 --> 00:01:07,680 mais uma vez, comparando duas barras de lado a lado outra em vermelho, vamos trocar o 23 00:01:07,680 --> 00:01:11,010 maior eo menor se eles estão fora de ordem. 24 00:01:11,010 --> 00:01:14,150 >> Então, isso vai continuar e continuar e ir , e você verá que a maior 25 00:01:14,150 --> 00:01:16,700 elementos estão fazendo seu caminho para o direito, e os elementos menores são 26 00:01:16,700 --> 00:01:17,900 fazendo o seu caminho para a esquerda. 27 00:01:17,900 --> 00:01:21,380 Mas começamos a quantificar a eficiência, a 28 00:01:21,380 --> 00:01:22,970 qualidade deste algoritmo. 29 00:01:22,970 --> 00:01:25,200 E nós dissemos que, no pior caso, este algoritmo levou 30 00:01:25,200 --> 00:01:27,940 aproximadamente quantos passos? 31 00:01:27,940 --> 00:01:28,980 >> Então n ao quadrado. 32 00:01:28,980 --> 00:01:30,402 E o que era n? 33 00:01:30,402 --> 00:01:31,650 >> AUDIÊNCIA: Número de elementos. 34 00:01:31,650 --> 00:01:32,790 >> DAVID MALAN: Então n foi o número de elementos. 35 00:01:32,790 --> 00:01:33,730 E assim nós vamos fazer isso muitas vezes. 36 00:01:33,730 --> 00:01:36,650 Toda vez que quero falar sobre o tamanho de um problema ou o tamanho de um 37 00:01:36,650 --> 00:01:39,140 entrada, ou a quantidade de tempo que leva para produzir uma saída, vamos 38 00:01:39,140 --> 00:01:41,610 generalizada o que a entrada é como n. 39 00:01:41,610 --> 00:01:45,970 Então, de volta na Semana 0, o número de páginas na lista telefônica foi n. 40 00:01:45,970 --> 00:01:47,550 O número de estudantes na sala foi n. 41 00:01:47,550 --> 00:01:49,630 Então, aqui, também, que estamos seguindo esse padrão. 42 00:01:49,630 --> 00:01:52,800 >> Agora n ao quadrado não é particularmente rápido, então nós tentamos fazer melhor. 43 00:01:52,800 --> 00:01:55,970 E assim, nós olhamos um par de outros algoritmos, entre os quais 44 00:01:55,970 --> 00:01:57,690 foram seleção espécie. 45 00:01:57,690 --> 00:01:59,180 Assim, a seleção espécie foi um pouco diferente. 46 00:01:59,180 --> 00:02:03,130 Era quase mais simples, ouso dizer, qual I iniciada no começo do 47 00:02:03,130 --> 00:02:06,740 Lista dos nossos voluntários e eu novamente e outra vez passou por 48 00:02:06,740 --> 00:02:10,060 Na lista, arrancar a menor elemento de cada vez e colocá-lo ou 49 00:02:10,060 --> 00:02:13,040 ela no início da lista. 50 00:02:13,040 --> 00:02:16,410 >> Mas isso, também, uma vez que começamos a pensar através da matemática e maior 51 00:02:16,410 --> 00:02:19,860 imagem, pensou em quantas vezes Eu estava indo para trás e para frente e para trás 52 00:02:19,860 --> 00:02:24,090 e para trás, nós dissemos, no pior caso, seleção espécie, também, era o quê? 53 00:02:24,090 --> 00:02:24,960 n ao quadrado. 54 00:02:24,960 --> 00:02:27,490 Agora, no mundo real, ele pode na verdade, ser ligeiramente mais rápido. 55 00:02:27,490 --> 00:02:30,620 Porque mais uma vez, eu não tenho que manter retrocesso, uma vez que eu tinha ordenado a 56 00:02:30,620 --> 00:02:31,880 menores elementos. 57 00:02:31,880 --> 00:02:35,090 Mas se pensarmos muito grande n, e se você tipo de fazer a matemática como 58 00:02:35,090 --> 00:02:39,170 Eu fiz no tabuleiro, com o n ao quadrado menos alguma coisa, tudo o resto 59 00:02:39,170 --> 00:02:41,850 além do n ao quadrado, uma vez que n fica muito grande, não 60 00:02:41,850 --> 00:02:42,850 realmente importa tanto. 61 00:02:42,850 --> 00:02:45,470 Assim como os cientistas da computação, que espécie de fechar os olhos para o menor 62 00:02:45,470 --> 00:02:49,220 fatores e se concentrar apenas no fator de uma expressão que vai fazer 63 00:02:49,220 --> 00:02:50,330 a maior diferença. 64 00:02:50,330 --> 00:02:52,840 >> Bem, finalmente, nós olhamos a ordenação por inserção. 65 00:02:52,840 --> 00:02:56,620 E este foi semelhante em espírito, mas ao invés de passar por iterativa e 66 00:02:56,620 --> 00:03:01,250 selecionar o menor elemento de um tempo, em vez tomou a mão que eu 67 00:03:01,250 --> 00:03:04,070 foi tratado, e eu decidi, tudo certo, você pertence aqui. 68 00:03:04,070 --> 00:03:06,160 Em seguida, mudei-me para o próximo elemento e decidiu que ele ou 69 00:03:06,160 --> 00:03:07,470 ela pertencia aqui. 70 00:03:07,470 --> 00:03:08,810 E então eu segui em frente e continuar. 71 00:03:08,810 --> 00:03:11,780 E eu poderia para, ao longo do caminho, mudar esses caras, a fim de 72 00:03:11,780 --> 00:03:13,030 dar espaço para eles. 73 00:03:13,030 --> 00:03:16,880 Então isso foi uma espécie de inversão mentais de seleção tipo que 74 00:03:16,880 --> 00:03:18,630 chamado ordenação por inserção. 75 00:03:18,630 --> 00:03:20,810 >> Então, esses temas para ocorrer no mundo real. 76 00:03:20,810 --> 00:03:23,640 Apenas alguns anos atrás, quando um determinado senador estava concorrendo à presidência, 77 00:03:23,640 --> 00:03:27,160 Eric Schmidt, no momento em que o CEO da Google, na verdade, tive a oportunidade 78 00:03:27,160 --> 00:03:28,040 entrevistá-lo. 79 00:03:28,040 --> 00:03:32,010 E nós pensamos em compartilhar esse YouTube clipe para você aqui, se pudéssemos transformar-se 80 00:03:32,010 --> 00:03:32,950 o volume. 81 00:03:32,950 --> 00:03:39,360 >> [REPRODUÇÃO] 82 00:03:39,360 --> 00:03:44,620 >> -Agora, o senador, você está aqui no Google, e eu gosto de pensar na presidência 83 00:03:44,620 --> 00:03:46,042 como uma entrevista de emprego. 84 00:03:46,042 --> 00:03:47,770 >> [Risos] 85 00:03:47,770 --> 00:03:50,800 >> -Agora é difícil conseguir um emprego como presidente. 86 00:03:50,800 --> 00:03:52,480 E você está passando os rigores agora. 87 00:03:52,480 --> 00:03:54,330 Também é difícil conseguir um emprego no Google. 88 00:03:54,330 --> 00:03:59,610 Temos perguntas e pedimos Nossos candidatos perguntas. 89 00:03:59,610 --> 00:04:02,250 E este é de Larry Schwimmer. 90 00:04:02,250 --> 00:04:05,325 >> [Risos] 91 00:04:05,325 --> 00:04:06,400 -Vocês pensam que eu estou brincando? 92 00:04:06,400 --> 00:04:08,750 É aqui mesmo. 93 00:04:08,750 --> 00:04:12,110 Qual é a maneira mais eficiente para ordenar um milhão de números inteiros de dois bits? 94 00:04:12,110 --> 00:04:15,810 >> [Risos] 95 00:04:15,810 --> 00:04:18,260 >> -Bem, uh - 96 00:04:18,260 --> 00:04:19,029 >> -Sinto muito. 97 00:04:19,029 --> 00:04:19,745 Talvez devêssemos - 98 00:04:19,745 --> 00:04:21,000 >> -Não, não, não, não, não. 99 00:04:21,000 --> 00:04:21,470 >> -Isso não é uma - 100 00:04:21,470 --> 00:04:22,185 OK. 101 00:04:22,185 --> 00:04:25,328 >> -Eu acho que o bubble sort seria ser o caminho errado. 102 00:04:25,328 --> 00:04:26,792 >> [Risos] 103 00:04:26,792 --> 00:04:28,510 >> [Aclamações e aplausos] 104 00:04:28,510 --> 00:04:31,211 >> -Vamos, que lhe disse isso? 105 00:04:31,211 --> 00:04:32,155 OK. 106 00:04:32,155 --> 00:04:33,350 >> [FIM REPRODUÇÃO DE VÍDEO] 107 00:04:33,350 --> 00:04:35,070 >> DAVID MALAN: Então você tem isso. 108 00:04:35,070 --> 00:04:39,600 Então começamos a quantificar estes execução vezes, por assim dizer, com algo 109 00:04:39,600 --> 00:04:43,480 chamado notação assintótica, que é apenas referindo-se a nossa espécie de transformar 110 00:04:43,480 --> 00:04:47,420 os olhos para esses fatores menores e apenas olhando para o tempo de execução, 111 00:04:47,420 --> 00:04:51,250 o desempenho destes algoritmos, como n fica muito grande ao longo do tempo. 112 00:04:51,250 --> 00:04:55,110 E assim, nós introduzimos grande O. e Big O representava algo que pensávamos 113 00:04:55,110 --> 00:04:57,000 como um limite superior. 114 00:04:57,000 --> 00:04:59,570 E, na verdade, Barry, podemos diminuir que o microfone um pouco? 115 00:04:59,570 --> 00:05:01,040 >> Nós pensamos que isso é um limite superior. 116 00:05:01,040 --> 00:05:04,710 Tão grande S de n significa que, em quadrado pior das hipóteses, algo como 117 00:05:04,710 --> 00:05:07,780 seleção tipo levaria n passos quadrado. 118 00:05:07,780 --> 00:05:10,310 Ou algo parecido com a ordenação por inserção seria n passos quadrado. 119 00:05:10,310 --> 00:05:15,150 Agora, para algo como a inserção tipo, qual foi o pior caso? 120 00:05:15,150 --> 00:05:18,200 Dado um array, que é o pior cenário possível, que você pode encontrar 121 00:05:18,200 --> 00:05:20,650 se depara com? 122 00:05:20,650 --> 00:05:21,860 >> É completamente para trás, certo? 123 00:05:21,860 --> 00:05:24,530 Porque se é completamente para trás, você tem que fazer um monte de trabalho. 124 00:05:24,530 --> 00:05:26,420 Porque se você está completamente para trás, você vai encontrar o 125 00:05:26,420 --> 00:05:28,840 maior elemento aqui, embora pertence lá. 126 00:05:28,840 --> 00:05:31,140 Então você vai dizer, tudo bem, a Neste momento, você pertence aqui, 127 00:05:31,140 --> 00:05:32,310 assim que você deixá-lo sozinho. 128 00:05:32,310 --> 00:05:35,425 >> Então você percebe, oh, droga, eu tenho que mover este elemento ligeiramente menor para 129 00:05:35,425 --> 00:05:36,470 à esquerda de você. 130 00:05:36,470 --> 00:05:38,770 Então eu tenho que fazer isso de novo e de novo e de novo. 131 00:05:38,770 --> 00:05:41,410 E se eu andei para trás e para a frente, você se classificar de sentir o desempenho dos 132 00:05:41,410 --> 00:05:45,540 que o algoritmo, pois constantemente eu sou baralhar todos os outros para baixo na 133 00:05:45,540 --> 00:05:46,510 matriz para fazer o quarto para ele. 134 00:05:46,510 --> 00:05:47,750 Então esse é o pior caso. 135 00:05:47,750 --> 00:05:48,570 >> Por outro lado - 136 00:05:48,570 --> 00:05:50,320 e isso foi um cliffhanger última vez - 137 00:05:50,320 --> 00:05:54,065 dissemos que a ordenação por inserção era um omega de quê? 138 00:05:54,065 --> 00:05:57,530 Qual é o melhor caso running momento da inserção do tipo? 139 00:05:57,530 --> 00:05:58,520 Então, é realmente n. 140 00:05:58,520 --> 00:06:00,980 Esse era o vazio que deixou no quadro da última vez. 141 00:06:00,980 --> 00:06:03,160 >> E é omega de n porque porquê? 142 00:06:03,160 --> 00:06:06,630 Bem, no melhor caso, o que é ordenação por inserção vai ser entregue? 143 00:06:06,630 --> 00:06:09,830 Bem, a lista que está completamente resolvido já, o mínimo de trabalho para fazer. 144 00:06:09,830 --> 00:06:12,460 Mas o que é interessante sobre a ordenação por inserção é que, porque começa aqui e 145 00:06:12,460 --> 00:06:15,340 decide, oh, você é o número um, você pertence aqui. 146 00:06:15,340 --> 00:06:16,970 Oh, o que uma boa fortuna. 147 00:06:16,970 --> 00:06:17,740 >> Você é o número dois. 148 00:06:17,740 --> 00:06:19,030 Você também pertenço aqui. 149 00:06:19,030 --> 00:06:21,010 Número três, melhor ainda, você pertence aqui. 150 00:06:21,010 --> 00:06:25,210 Assim que se chega ao fim da pseudocódigo lista, por inserção de tipo 151 00:06:25,210 --> 00:06:28,010 que atravessou verbalmente última vez, ele é feito. 152 00:06:28,010 --> 00:06:32,790 Mas a seleção tipo, pelo contrário, continuei a fazer o quê? 153 00:06:32,790 --> 00:06:35,260 >> Continuei a lista novo e de novo e de novo. 154 00:06:35,260 --> 00:06:39,160 Porque o conhecimento chave que só havia uma vez que você olhou para todo o caminho para a 155 00:06:39,160 --> 00:06:42,500 final da lista você pode estar certo que o elemento que foi selecionado 156 00:06:42,500 --> 00:06:45,560 de fato o menor elemento atualmente. 157 00:06:45,560 --> 00:06:48,920 Então, esses diferentes modelos mentais final cedendo alguns muito real-world 158 00:06:48,920 --> 00:06:53,130 diferenças para nós, assim como esses diferenças assintóticas teóricas. 159 00:06:53,130 --> 00:06:56,910 >> Então, só para recapitular, então, grande O de n quadrado, temos visto alguns como 160 00:06:56,910 --> 00:06:58,350 algoritmos até agora. 161 00:06:58,350 --> 00:06:59,580 Big O de n? 162 00:06:59,580 --> 00:07:02,870 O que é um algoritmo que poderia ser dito para ser grande O de n? 163 00:07:02,870 --> 00:07:06,930 No pior dos casos, leva uma série linear de passos. 164 00:07:06,930 --> 00:07:07,810 >> OK, pesquisa linear. 165 00:07:07,810 --> 00:07:10,470 E no pior caso, onde está o elemento que você está procurando quando 166 00:07:10,470 --> 00:07:12,950 aplicação de pesquisa linear? 167 00:07:12,950 --> 00:07:14,680 >> OK, no pior caso, não é mesmo lá. 168 00:07:14,680 --> 00:07:17,000 Ou o segundo pior caso, é todo o caminho no final, o que é 169 00:07:17,000 --> 00:07:18,880 mais-ou-menos uma diferença de uma etapa. 170 00:07:18,880 --> 00:07:21,180 Assim, no final do dia, podemos dizer que é linear. 171 00:07:21,180 --> 00:07:23,910 Big O de n seria de busca linear, porque, no pior caso, o 172 00:07:23,910 --> 00:07:26,610 elemento não está lá ou é todo o caminho no final. 173 00:07:26,610 --> 00:07:29,370 >> Bem, O grande de log de n. 174 00:07:29,370 --> 00:07:32,760 Nós não falamos em detalhes sobre isso, mas já vi isso antes. 175 00:07:32,760 --> 00:07:36,840 O que é executado no chamado logarítmica tempo, no pior dos casos? 176 00:07:36,840 --> 00:07:38,500 >> Sim, pesquisa de modo binário. 177 00:07:38,500 --> 00:07:42,930 E busca binária no pior caso pode ter o elemento em algum lugar 178 00:07:42,930 --> 00:07:45,640 no meio, ou em algum lugar no interior da matriz. 179 00:07:45,640 --> 00:07:48,040 Mas você só encontrá-lo uma vez que você dividir a lista pela metade, em 180 00:07:48,040 --> 00:07:48,940 metade, pela metade, pela metade. 181 00:07:48,940 --> 00:07:50,200 E, em seguida, voila, ele está lá. 182 00:07:50,200 --> 00:07:52,500 Ou ainda, pior caso, não é mesmo lá. 183 00:07:52,500 --> 00:07:56,770 Mas você não sabe que ele não está lá até que você espécie de chegar a esse último 184 00:07:56,770 --> 00:08:00,470 baixo para a maioria dos elementos de reduzir para metade e reduzir para metade e reduzir para metade. 185 00:08:00,470 --> 00:08:01,400 >> Big O de 1. 186 00:08:01,400 --> 00:08:03,540 Para que pudéssemos grande O de 2, O grande de 3. 187 00:08:03,540 --> 00:08:06,260 Sempre que você quiser apenas um número constante, nós apenas uma espécie de apenas simplificar 188 00:08:06,260 --> 00:08:07,280 que ó tão grande de uma. 189 00:08:07,280 --> 00:08:10,440 Mesmo que se realisticamente, é preciso 2 ou até 100 passos, se é um 190 00:08:10,440 --> 00:08:13,680 número constante de passos, que acabamos de dizer grande O de 1. 191 00:08:13,680 --> 00:08:15,930 O que é um algoritmo que é em grande O de 1? 192 00:08:15,930 --> 00:08:18,350 >> AUDIÊNCIA: Encontrar o comprimento de uma variável. 193 00:08:18,350 --> 00:08:21,090 >> DAVID MALAN: Encontrar o comprimento de uma variável? 194 00:08:21,090 --> 00:08:23,870 >> AUDIÊNCIA: Não, o comprimento se ele já está classificada. 195 00:08:23,870 --> 00:08:24,160 >> DAVID MALAN: Ótimo. 196 00:08:24,160 --> 00:08:27,850 OK, assim que encontrar o comprimento de algo Se o comprimento de que alguma coisa, como 197 00:08:27,850 --> 00:08:30,020 uma matriz, é armazenada em alguma variável. 198 00:08:30,020 --> 00:08:33,380 Porque você pode apenas ler a variável, ou imprimir a variável, ou 199 00:08:33,380 --> 00:08:34,960 geralmente só acessar essa variável. 200 00:08:34,960 --> 00:08:37,299 E voila, que leva tempo constante. 201 00:08:37,299 --> 00:08:38,909 >> Por outro lado, acho que volta a zero. 202 00:08:38,909 --> 00:08:42,460 Pense na primeira semana de C, chamando apenas printf e impressão 203 00:08:42,460 --> 00:08:46,240 algo na tela é sem dúvida constante de tempo, porque ele só leva 204 00:08:46,240 --> 00:08:50,880 um certo número de ciclos de CPU para mostrar que o texto no ecrã. 205 00:08:50,880 --> 00:08:52,720 Ou esperar - não é? 206 00:08:52,720 --> 00:08:56,430 De que outra forma poderíamos modelar o desempenho do printf? 207 00:08:56,430 --> 00:09:00,420 Será que alguém gostaria de discordar, que talvez não seja o tempo realmente constante? 208 00:09:00,420 --> 00:09:03,600 Em que sentido pode printf está funcionando tempo, na verdade, a impressão de uma corda em 209 00:09:03,600 --> 00:09:05,580 tela, ser algo excepto constante. 210 00:09:05,580 --> 00:09:07,860 >> AUDIÊNCIA: [inaudível]. 211 00:09:07,860 --> 00:09:08,230 >> DAVID MALAN: Yeah. 212 00:09:08,230 --> 00:09:09,300 Por isso, depende da nossa perspectiva. 213 00:09:09,300 --> 00:09:13,390 Se nós realmente acho que a entrada para printf como sendo a string, e 214 00:09:13,390 --> 00:09:16,380 portanto, podemos medir o tamanho desse entrada pelo seu comprimento - então vamos chamá 215 00:09:16,380 --> 00:09:17,780 que o comprimento n, bem como - 216 00:09:17,780 --> 00:09:21,990 sem dúvida, printf é a própria grande O de n porque ele vai levá-lo n passos 217 00:09:21,990 --> 00:09:24,750 para imprimir cada um dos n caracteres, provavelmente. 218 00:09:24,750 --> 00:09:27,730 Pelo menos na medida em que assumimos que, talvez, ele está usando um laço for 219 00:09:27,730 --> 00:09:28,560 debaixo do capô. 220 00:09:28,560 --> 00:09:30,860 >> Mas teríamos de olhar para isso Código para entender melhor. 221 00:09:30,860 --> 00:09:33,650 E, de fato, uma vez que vocês começarem analisar seus próprios algoritmos, você vai 222 00:09:33,650 --> 00:09:34,900 literalmente fazer exatamente isso. 223 00:09:34,900 --> 00:09:37,765 Espécie de globo ocular seu código e pensar sobre - tudo bem, eu tenho esse laço 224 00:09:37,765 --> 00:09:41,870 aqui ou eu tenho laços aninhados aqui, que vai fazer n coisas n vezes, 225 00:09:41,870 --> 00:09:46,050 e você pode classificar de razão o seu caminho através do código, mesmo que seja 226 00:09:46,050 --> 00:09:47,980 pseudocódigo e não o código real. 227 00:09:47,980 --> 00:09:49,730 >> Assim que sobre omega de n ao quadrado? 228 00:09:49,730 --> 00:09:53,582 O que era um algoritmo que na melhor caso, ainda levou n passos quadrados? 229 00:09:53,582 --> 00:09:54,014 Sim? 230 00:09:54,014 --> 00:09:54,880 >> AUDIÊNCIA: [inaudível]. 231 00:09:54,880 --> 00:09:55,900 >> DAVID MALAN: Então seleção espécie. 232 00:09:55,900 --> 00:09:59,150 Devido a este problema muito reduzida ao fato de que mais uma vez, eu não sei 233 00:09:59,150 --> 00:10:02,600 Eu encontrei o atual menor até Eu chequei todos os elementos danado. 234 00:10:02,600 --> 00:10:08,050 Assim omega de, digamos, n, só veio com um. 235 00:10:08,050 --> 00:10:09,300 Ordenação por inserção. 236 00:10:09,300 --> 00:10:12,370 Se a lista passa a ser classificada já, na melhor das hipóteses, só temos 237 00:10:12,370 --> 00:10:15,090 para fazer uma passagem através dela, no ponto em que temos a certeza. 238 00:10:15,090 --> 00:10:17,890 E, em seguida, que pode ser dito ser linear, com certeza. 239 00:10:17,890 --> 00:10:20,570 >> Que tal omega de 1? 240 00:10:20,570 --> 00:10:23,790 O que, na melhor das hipóteses, pode demorar um número constante de etapas? 241 00:10:23,790 --> 00:10:27,220 Pesquisa de modo linear, se você apenas ter sorte eo elemento que você está procurando 242 00:10:27,220 --> 00:10:31,000 é logo no início da lista, se esse é o lugar onde você está começando seu 243 00:10:31,000 --> 00:10:33,070 linear transversal dessa lista. 244 00:10:33,070 --> 00:10:35,180 >> E isso é verdade de um série de coisas. 245 00:10:35,180 --> 00:10:37,660 Por exemplo, mesmo binário pesquisa é omega de 1. 246 00:10:37,660 --> 00:10:40,310 Porque se você ficar muito danado sorte e smack-dab no meio de 247 00:10:40,310 --> 00:10:42,950 sua matriz é o número você está procurando? 248 00:10:42,950 --> 00:10:45,730 Assim, você pode ter sorte lá, também. 249 00:10:45,730 --> 00:10:49,190 >> Este, por último, omega de n log n. 250 00:10:49,190 --> 00:10:52,573 Então n log n, nós realmente não falar ainda, mas - 251 00:10:52,573 --> 00:10:53,300 >> AUDIÊNCIA: merge sort? 252 00:10:53,300 --> 00:10:53,960 >> DAVID MALAN: merge sort. 253 00:10:53,960 --> 00:10:56,920 Esse foi o gancho da última vez, onde propusemos, e nós mostramos 254 00:10:56,920 --> 00:10:58,600 visualmente, que existem algoritmos. 255 00:10:58,600 --> 00:11:02,470 E uma espécie de apenas um desses fundir algoritmo que é fundamentalmente mais rápido 256 00:11:02,470 --> 00:11:03,450 que alguns desses outros caras. 257 00:11:03,450 --> 00:11:07,800 Na verdade, fundir curto é não só no melhor caso n log n, no pior 258 00:11:07,800 --> 00:11:09,460 caso n log n. 259 00:11:09,460 --> 00:11:14,540 E quando você tem essa coincidência de omega e grandes O ser a mesma coisa? 260 00:11:14,540 --> 00:11:17,310 Na verdade, podemos descrever isso como o que é chamada theta, embora seja um 261 00:11:17,310 --> 00:11:18,220 pouco menos comum. 262 00:11:18,220 --> 00:11:21,730 Mas isso significa apenas que os dois limites, neste caso, são as mesmas. 263 00:11:21,730 --> 00:11:25,770 >> Então, merge sort, o que isso realmente se resumem a para nós? 264 00:11:25,770 --> 00:11:27,000 Bem, lembre-se a motivação. 265 00:11:27,000 --> 00:11:30,340 Deixa-me tirar-se outra animação que nós não olhar pela última vez. 266 00:11:30,340 --> 00:11:33,390 Este, mesma idéia, mas é um pouco maior. 267 00:11:33,390 --> 00:11:36,160 E eu estou indo para ir em frente e apontar primeiro - temos ordenação por inserção em 268 00:11:36,160 --> 00:11:39,410 canto superior esquerdo, em seguida, a seleção de classificação, bubble sort, a par de outros tipos - 269 00:11:39,410 --> 00:11:42,670 shell e rápidos - que não falamos aproximadamente, e heap e merge sort. 270 00:11:42,670 --> 00:11:47,090 >> Assim, pelo menos, tentar focar seus olhos em os três principais da esquerda e depois 271 00:11:47,090 --> 00:11:49,120 merge sort quando eu clico esta seta verde. 272 00:11:49,120 --> 00:11:51,900 Mas eu vou deixar todos eles executados, apenas para dar-lhe um sentido da diversidade de 273 00:11:51,900 --> 00:11:53,980 algoritmos que existem no mundo. 274 00:11:53,980 --> 00:11:56,180 Eu vou deixar esta corrida por apenas alguns segundos. 275 00:11:56,180 --> 00:11:59,640 E se você concentrar seus olhos - escolha um algoritmo, focar-lo por apenas um 276 00:11:59,640 --> 00:12:02,970 segundo - você vai começar a ver o padrão que é de execução. 277 00:12:02,970 --> 00:12:04,530 >> Merge sort, aviso prévio, está feito. 278 00:12:04,530 --> 00:12:06,430 Heap espécie, tipo rápida, shell - 279 00:12:06,430 --> 00:12:09,480 assim parece que introduziu a três piores algoritmos na semana passada. 280 00:12:09,480 --> 00:12:12,960 Mas isso é bom que estamos aqui hoje para olhar para merge sort, que é um dos 281 00:12:12,960 --> 00:12:16,500 o mais fácil é olhar, mesmo embora ele provavelmente irá dobrar sua mente 282 00:12:16,500 --> 00:12:17,490 só um pouquinho. 283 00:12:17,490 --> 00:12:21,130 Aqui podemos ver o quanto seleção espécie é uma merda. 284 00:12:21,130 --> 00:12:24,600 >> Mas, por outro lado, é muito fácil de implementar. 285 00:12:24,600 --> 00:12:28,160 E talvez para P Set 3, que é um dos algoritmos que você escolheu para implementar 286 00:12:28,160 --> 00:12:28,960 para a edição standard. 287 00:12:28,960 --> 00:12:30,970 Perfeitamente bem, perfeitamente correto. 288 00:12:30,970 --> 00:12:35,210 >> Mas, novamente, como n se torna grande, se você optar por implementar um algoritmo mais rápido 289 00:12:35,210 --> 00:12:39,020 como merge sort, as probabilidades são em maior e insumos maiores, o código é apenas 290 00:12:39,020 --> 00:12:39,800 vai correr mais rápido. 291 00:12:39,800 --> 00:12:41,090 Seu site vai funcionar melhor. 292 00:12:41,090 --> 00:12:42,650 Seus usuários estão indo para ser feliz. 293 00:12:42,650 --> 00:12:45,280 E por isso há esses efeitos de realmente dar 294 00:12:45,280 --> 00:12:47,350 nos algum pensamento mais profundo. 295 00:12:47,350 --> 00:12:49,990 >> Então, vamos dar uma olhada no que fundem espécie é realmente tudo. 296 00:12:49,990 --> 00:12:52,992 O legal é que a fusão tipo é só isso. 297 00:12:52,992 --> 00:12:56,300 Isto é, mais uma vez, o que nós chamamos pseudocódigo, ser pseudocódigo 298 00:12:56,300 --> 00:12:57,720 Inglês-como sintaxe. 299 00:12:57,720 --> 00:12:59,890 E a simplicidade é espécie de fascinante. 300 00:12:59,890 --> 00:13:02,840 >> Então, na entrada de n elementos - para que significa apenas que, aqui está um array. 301 00:13:02,840 --> 00:13:04,000 Tem coisas n nele. 302 00:13:04,000 --> 00:13:05,370 Isso é tudo o que estamos dizendo aqui. 303 00:13:05,370 --> 00:13:07,560 >> Se n for menor do que 2, o retorno. 304 00:13:07,560 --> 00:13:08,640 Então, isso é apenas o caso trivial. 305 00:13:08,640 --> 00:13:12,580 Se n for menor do que 2, em seguida, é obviamente 1 ou 0, caso em que a coisa 306 00:13:12,580 --> 00:13:14,780 já está classificado ou inexistente, por isso só voltar. 307 00:13:14,780 --> 00:13:15,900 Não há nada a fazer. 308 00:13:15,900 --> 00:13:18,360 Então, isso é um caso simples de arrancar fora. 309 00:13:18,360 --> 00:13:20,110 >> Caso contrário, nós temos três etapas. 310 00:13:20,110 --> 00:13:23,650 Classificar a metade esquerda dos elementos, tipo a metade direita dos elementos, 311 00:13:23,650 --> 00:13:26,650 e em seguida, mesclar as duas metades ordenadas. 312 00:13:26,650 --> 00:13:29,400 O que é interessante aqui é que Eu sou o tipo de punting, certo? 313 00:13:29,400 --> 00:13:32,300 Há uma espécie de definição circular para esse algoritmo. 314 00:13:32,300 --> 00:13:35,986 Em que sentido é este algoritmo de circular definição? 315 00:13:35,986 --> 00:13:37,850 >> AUDIÊNCIA: [inaudível]. 316 00:13:37,850 --> 00:13:41,670 >> DAVID MALAN: Sim, o meu algoritmo de ordenação, dois de seus passos são "espécie 317 00:13:41,670 --> 00:13:44,640 alguma coisa. "E assim que levanta a questão, bem, o que eu vou usar 318 00:13:44,640 --> 00:13:46,460 para classificar a metade esquerda ea metade direita? 319 00:13:46,460 --> 00:13:49,600 E a beleza aqui é que, apesar de mais uma vez, este é o alucinante 320 00:13:49,600 --> 00:13:54,030 parte potencialmente, você pode usar mesmo algoritmo para classificar a metade esquerda. 321 00:13:54,030 --> 00:13:54,700 >> Mas espere um minuto. 322 00:13:54,700 --> 00:13:57,070 Quando você disse para classificar a metade esquerda, quais são os dois 323 00:13:57,070 --> 00:13:58,240 etapas vai ser o próximo? 324 00:13:58,240 --> 00:14:00,550 Vamos resolver a metade esquerda da meia esquerda e à direita 325 00:14:00,550 --> 00:14:01,420 a metade da metade esquerda. 326 00:14:01,420 --> 00:14:04,430 Caramba, como faço para classificar os dois metades, ou em quartos, agora? 327 00:14:04,430 --> 00:14:05,260 >> Mas isso é OK. 328 00:14:05,260 --> 00:14:07,830 Temos um algoritmo de classificação aqui. 329 00:14:07,830 --> 00:14:10,660 E mesmo que você pode se preocupar em pela primeira vez esta é uma espécie de infinito 330 00:14:10,660 --> 00:14:12,780 loop, é um ciclo que nunca vai acabar - ele vai 331 00:14:12,780 --> 00:14:15,770 acabar de uma vez o que acontece? 332 00:14:15,770 --> 00:14:16,970 Uma vez que n é inferior a 2. 333 00:14:16,970 --> 00:14:19,180 Que eventualmente vai acontecer, porque se você continuar e reduzir para metade 334 00:14:19,180 --> 00:14:23,020 reduzir para metade em reduzir para metade dessas metades, com certeza eventualmente, você vai acabar 335 00:14:23,020 --> 00:14:25,350 com apenas 1 ou 0 elementos. 336 00:14:25,350 --> 00:14:28,500 Em que ponto, este algoritmo diz que você está feito. 337 00:14:28,500 --> 00:14:31,020 >> Portanto, a verdadeira magia neste algoritmo parece estar em 338 00:14:31,020 --> 00:14:33,470 esse passo final, a fusão. 339 00:14:33,470 --> 00:14:37,190 Essa idéia simples, apenas fusão de dois coisas, que é o que finalmente vai 340 00:14:37,190 --> 00:14:40,920 que nos permitem classificar uma matriz de, digamos, oito elementos. 341 00:14:40,920 --> 00:14:44,410 Então, eu tenho mais oito bolas de stress up aqui, oito pedaços de papel, e uma 342 00:14:44,410 --> 00:14:45,500 Google Glass - 343 00:14:45,500 --> 00:14:46,140 que eu tenho que manter. 344 00:14:46,140 --> 00:14:46,960 >> [Risos] 345 00:14:46,960 --> 00:14:48,970 >> DAVID MALAN: Se pudéssemos ter oito voluntários, e vamos ver se podemos 346 00:14:48,970 --> 00:14:51,430 jogar isso, então. 347 00:14:51,430 --> 00:14:52,500 Uau, OK. 348 00:14:52,500 --> 00:14:53,565 Ciência da computação está ficando divertido. 349 00:14:53,565 --> 00:14:54,320 Tudo bem. 350 00:14:54,320 --> 00:14:57,770 Então, que tal você três, maior mão lá em cima. 351 00:14:57,770 --> 00:14:58,580 Quatro na parte de trás. 352 00:14:58,580 --> 00:15:02,220 E quanto a nós vamos fazer você três nessa linha? 353 00:15:02,220 --> 00:15:03,390 E quatro na frente. 354 00:15:03,390 --> 00:15:04,920 Então você oito, vamos para cima. 355 00:15:04,920 --> 00:15:12,060 >> [Risos] 356 00:15:12,060 --> 00:15:13,450 >> DAVID MALAN: Na verdade eu sou não sei o que é. 357 00:15:13,450 --> 00:15:14,810 São as bolas de stress? 358 00:15:14,810 --> 00:15:16,510 As lâmpadas de mesa? 359 00:15:16,510 --> 00:15:18,650 O material? 360 00:15:18,650 --> 00:15:19,680 A internet? 361 00:15:19,680 --> 00:15:20,160 >> OK. 362 00:15:20,160 --> 00:15:21,310 Então vamos lá para cima. 363 00:15:21,310 --> 00:15:22,310 Quem gostaria - 364 00:15:22,310 --> 00:15:23,570 continuam aparecendo. 365 00:15:23,570 --> 00:15:24,240 Vamos ver. 366 00:15:24,240 --> 00:15:26,460 E isso coloca você no local - 367 00:15:26,460 --> 00:15:27,940 você está em uma localização. 368 00:15:27,940 --> 00:15:28,670 Uh-oh, espere um minuto. 369 00:15:28,670 --> 00:15:30,760 1, 2, 3, 4, 5, 6, 7 - oh, bom. 370 00:15:30,760 --> 00:15:31,310 Tudo bem, estamos bem. 371 00:15:31,310 --> 00:15:35,130 Tudo bem, então todos têm assento, mas não no vidro do Google. 372 00:15:35,130 --> 00:15:36,475 Deixe-me fazer fila estes acima. 373 00:15:36,475 --> 00:15:37,115 Qual é o seu nome? 374 00:15:37,115 --> 00:15:37,440 >> MICHELLE: Michelle. 375 00:15:37,440 --> 00:15:38,090 >> DAVID MALAN: Michelle? 376 00:15:38,090 --> 00:15:42,000 Tudo bem, você começa a olhar como o geek, se está tudo OK. 377 00:15:42,000 --> 00:15:44,625 Bem, eu também, eu suponho, apenas por um momento. 378 00:15:44,625 --> 00:15:45,875 Tudo bem, espera. 379 00:15:45,875 --> 00:15:48,510 380 00:15:48,510 --> 00:15:50,950 Estamos tentando chegar a um caso de uso para o Google de vidro, e nós 381 00:15:50,950 --> 00:15:53,750 pensei que seria divertido fazer apenas isso quando as pessoas estão no palco. 382 00:15:53,750 --> 00:15:57,120 Vamos gravar o mundo a partir de sua perspectiva. 383 00:15:57,120 --> 00:15:58,410 Tudo bem. 384 00:15:58,410 --> 00:15:59,830 Não provavelmente o Google pretendia. 385 00:15:59,830 --> 00:16:02,260 Tudo bem, se você não me importo de usar isso para os próximos minutos difíceis, 386 00:16:02,260 --> 00:16:03,150 que seria maravilhoso. 387 00:16:03,150 --> 00:16:08,620 >> Tudo bem, então temos aqui um conjunto de elementos, e que a matriz, de acordo com a 388 00:16:08,620 --> 00:16:11,480 pedaços de papel nessas pessoas ' mãos, está atualmente sem classificação. 389 00:16:11,480 --> 00:16:12,050 >> MICHELLE: Oh, isso é tão estranho. 390 00:16:12,050 --> 00:16:12,810 >> DAVID MALAN: É praticamente aleatória. 391 00:16:12,810 --> 00:16:15,760 E, em apenas um momento, vamos tentar para implementar espécie se fundem 392 00:16:15,760 --> 00:16:17,950 e ver onde esse insight chave. 393 00:16:17,950 --> 00:16:21,970 E o truque aqui com merge sort é algo que não assumiram ainda. 394 00:16:21,970 --> 00:16:24,030 Nós realmente precisa de algum espaço adicional. 395 00:16:24,030 --> 00:16:26,650 Então, o que vai ser particularmente interessante sobre isso é que estes 396 00:16:26,650 --> 00:16:29,270 caras vão se movimentar um pouco pouco, porque eu estou indo supor que 397 00:16:29,270 --> 00:16:31,880 há um conjunto extra de espaço, dizer, logo atrás deles. 398 00:16:31,880 --> 00:16:34,570 >> Então, se eles estão por trás de sua cadeira, que é a matriz secundária. 399 00:16:34,570 --> 00:16:36,960 Se eles estão sentados aqui, isso é a matriz primária. 400 00:16:36,960 --> 00:16:40,170 Mas este é um recurso que nós temos não aproveitados, até agora, com bolha 401 00:16:40,170 --> 00:16:42,040 tipo, com a seleção de tipo, com a ordenação por inserção. 402 00:16:42,040 --> 00:16:44,600 Lembre-se, na semana passada, todo mundo tipo de embaralhadas no lugar. 403 00:16:44,600 --> 00:16:46,840 Eles não usam qualquer memória adicional. 404 00:16:46,840 --> 00:16:49,310 Fizemos espaço para as pessoas por movimentação de pessoas ao redor. 405 00:16:49,310 --> 00:16:50,580 >> Portanto, esta é uma visão de chave, também. 406 00:16:50,580 --> 00:16:53,410 Há esse trade-off, em geral, em informática, de recursos. 407 00:16:53,410 --> 00:16:55,800 Se você quiser acelerar algo como o tempo, você vai 408 00:16:55,800 --> 00:16:56,900 tem que pagar um preço. 409 00:16:56,900 --> 00:17:00,750 E um desses preços é muitas vezes espaço, a quantidade de memória ou disco 410 00:17:00,750 --> 00:17:01,700 espaço em disco que você está usando. 411 00:17:01,700 --> 00:17:03,640 Ou, francamente, a quantidade programador de tempo. 412 00:17:03,640 --> 00:17:06,700 Quanto tempo você leva, o ser humano, para realmente implementar um pouco mais 413 00:17:06,700 --> 00:17:07,829 algoritmo complicado. 414 00:17:07,829 --> 00:17:09,760 Mas, por hoje, o trade-off é tempo e espaço. 415 00:17:09,760 --> 00:17:11,930 >> Então, se vocês pudessem apenas segurar o seu números para que possamos ver que você é 416 00:17:11,930 --> 00:17:15,839 de facto correspondente 4, 2, 6, 1, 3, 7, 8. 417 00:17:15,839 --> 00:17:16,599 Excelente. 418 00:17:16,599 --> 00:17:19,520 Então eu vou tentar orquestrar coisas, se vocês podem apenas 419 00:17:19,520 --> 00:17:21,800 seguir minha liderança aqui. 420 00:17:21,800 --> 00:17:26,650 >> Então, eu estou indo para implementar, em primeiro lugar, o primeiro passo do pseudocódigo, que é 421 00:17:26,650 --> 00:17:29,440 na entrada de n elementos, se n for inferior a 2, depois de voltar. 422 00:17:29,440 --> 00:17:31,370 Obviamente, que não faz aplicam-se, por isso, seguir em frente. 423 00:17:31,370 --> 00:17:33,340 Assim classificar a metade esquerda dos elementos. 424 00:17:33,340 --> 00:17:36,220 Então isso significa que eu vou focar a minha atenção por um momento sobre estes 425 00:17:36,220 --> 00:17:37,310 quatro caras aqui. 426 00:17:37,310 --> 00:17:39,774 Tudo bem, o que posso fazer na próxima? 427 00:17:39,774 --> 00:17:40,570 >> AUDIÊNCIA: classificar a metade esquerda. 428 00:17:40,570 --> 00:17:42,780 >> DAVID MALAN: Então agora eu tenho que classificar a metade esquerda desses caras. 429 00:17:42,780 --> 00:17:45,580 Porque mais uma vez, assumir para si a objetivo é classificar a metade esquerda. 430 00:17:45,580 --> 00:17:46,440 Como você faz isso? 431 00:17:46,440 --> 00:17:49,140 Basta seguir as instruções, mesmo que nós estamos fazendo isso de novo. 432 00:17:49,140 --> 00:17:50,160 Assim classificar a metade esquerda. 433 00:17:50,160 --> 00:17:52,030 Agora estou classificando esses dois caras. 434 00:17:52,030 --> 00:17:53,563 O que vem a seguir? 435 00:17:53,563 --> 00:17:54,510 >> AUDIÊNCIA: classificar a metade esquerda. 436 00:17:54,510 --> 00:17:55,460 >> DAVID MALAN: classificar a metade esquerda. 437 00:17:55,460 --> 00:18:00,680 Então, agora estes, este lugar aqui, é uma lista de tamanho 1. 438 00:18:00,680 --> 00:18:01,365 E qual é o seu nome? 439 00:18:01,365 --> 00:18:02,390 >> PRINCESA DAISY: Princesa Daisy. 440 00:18:02,390 --> 00:18:03,690 >> DAVID MALAN: Princesa Daisy está aqui. 441 00:18:03,690 --> 00:18:07,470 E assim ela já está classificado, porque a lista é de tamanho 1. 442 00:18:07,470 --> 00:18:09,490 O que posso fazer na próxima? 443 00:18:09,490 --> 00:18:13,680 OK, voltar, porque essa lista é de tamanho 1, que é inferior a 2. 444 00:18:13,680 --> 00:18:14,320 Então qual é o próximo passo? 445 00:18:14,320 --> 00:18:17,490 E agora você tem que tipo de voltar atrás em sua mente. 446 00:18:17,490 --> 00:18:19,340 >> Classificar a metade direita, o que é - 447 00:18:19,340 --> 00:18:19,570 qual é o seu nome? 448 00:18:19,570 --> 00:18:20,220 >> LINDA: Linda. 449 00:18:20,220 --> 00:18:20,980 >> DAVID MALAN: Linda. 450 00:18:20,980 --> 00:18:23,210 E então, o que fazemos agora que temos uma lista de tamanho 1? 451 00:18:23,210 --> 00:18:24,440 >> AUDIÊNCIA: Return. 452 00:18:24,440 --> 00:18:24,760 >> DAVID MALAN: Cuidado. 453 00:18:24,760 --> 00:18:29,540 Voltamos primeiro, e agora o terceiro etapa - e se eu tipo de representá-lo por 454 00:18:29,540 --> 00:18:33,490 abraçando os dois assentos agora, agora eu tem que juntar estes dois elementos. 455 00:18:33,490 --> 00:18:35,530 Então, agora, infelizmente, os elementos estão fora de ordem. 456 00:18:35,530 --> 00:18:39,920 Mas é aí que o processo de fusão começa a ficar atraente. 457 00:18:39,920 --> 00:18:42,410 >> Então, se vocês poderiam levantar-se para apenas um momento, eu vou precisar de você, em um 458 00:18:42,410 --> 00:18:44,170 momento, para o passo atrás de sua cadeira. 459 00:18:44,170 --> 00:18:46,480 E se Linda, porque é 2 menor do que 4, por que não 460 00:18:46,480 --> 00:18:48,130 você chega perto em primeiro lugar? 461 00:18:48,130 --> 00:18:48,690 Fique aí. 462 00:18:48,690 --> 00:18:50,520 Então, Linda, que você chega perto pela primeira vez. 463 00:18:50,520 --> 00:18:53,820 >> Agora, na realidade, se é apenas uma matriz pudéssemos levá-la em tempo real 464 00:18:53,820 --> 00:18:55,360 a partir desta cadeira a este ponto. 465 00:18:55,360 --> 00:18:57,770 Então, imagine que tomou alguma constante um número de passos. 466 00:18:57,770 --> 00:18:58,480 E agora - 467 00:18:58,480 --> 00:19:01,490 mas precisamos colocá-lo em o primeiro local aqui. 468 00:19:01,490 --> 00:19:03,930 >> E agora, se você pudesse vir por aí, bem, vamos 469 00:19:03,930 --> 00:19:06,300 estar no local dois. 470 00:19:06,300 --> 00:19:09,120 E mesmo que este se sente como se fosse tomando um tempo, o que é bom agora é 471 00:19:09,120 --> 00:19:14,710 que a metade esquerda da metade esquerda agora está classificada. 472 00:19:14,710 --> 00:19:18,010 Então, qual foi o próximo passo, se agora retroceder ainda mais na história? 473 00:19:18,010 --> 00:19:18,980 >> AUDIÊNCIA: A metade direita. 474 00:19:18,980 --> 00:19:19,900 >> DAVID MALAN: classificar a metade direita. 475 00:19:19,900 --> 00:19:21,320 Então, vocês tem que fazer isso, também. 476 00:19:21,320 --> 00:19:23,510 Então, se você pode levantar-se apenas por um momento? 477 00:19:23,510 --> 00:19:25,192 E qual é o seu nome? 478 00:19:25,192 --> 00:19:25,540 >> JESS: Jess. 479 00:19:25,540 --> 00:19:25,870 >> DAVID MALAN: Jess. 480 00:19:25,870 --> 00:19:29,720 OK, então Jess é agora a esquerda metade da metade direita. 481 00:19:29,720 --> 00:19:31,400 E assim ela é uma lista de tamanho 1. 482 00:19:31,400 --> 00:19:32,380 Ela está obviamente classificados. 483 00:19:32,380 --> 00:19:33,070 E o seu nome? 484 00:19:33,070 --> 00:19:33,630 >> MICHELLE: Michelle. 485 00:19:33,630 --> 00:19:35,340 >> DAVID MALAN: Michelle é, obviamente, uma lista de tamanho 1. 486 00:19:35,340 --> 00:19:36,050 Ela já está classificada. 487 00:19:36,050 --> 00:19:38,690 Então, agora a mágica acontece, o processo de fusão. 488 00:19:38,690 --> 00:19:39,790 Então, quem vai vir em primeiro lugar? 489 00:19:39,790 --> 00:19:41,560 Obviamente, a Michelle. 490 00:19:41,560 --> 00:19:43,280 Então, se você poderia vir em torno de volta. 491 00:19:43,280 --> 00:19:47,090 O espaço que temos disponível para ela agora está bem atrás nesta cadeira aqui. 492 00:19:47,090 --> 00:19:51,580 E agora, se você pudesse voltar, bem como, temos agora, para ser claro, dois 493 00:19:51,580 --> 00:19:53,810 metades, cada uma de tamanho 2 - 494 00:19:53,810 --> 00:19:57,090 e apenas por causa da representação, se poderia fazer um pouco de espaço - 495 00:19:57,090 --> 00:19:59,780 um deixou metade aqui, um metade aqui. 496 00:19:59,780 --> 00:20:01,160 >> Retroceder ainda mais na história. 497 00:20:01,160 --> 00:20:02,270 Qual é o próximo passo? 498 00:20:02,270 --> 00:20:03,030 >> AUDIÊNCIA: Mesclar. 499 00:20:03,030 --> 00:20:04,160 >> DAVID MALAN: Portanto, agora temos de mesclar. 500 00:20:04,160 --> 00:20:07,490 Então, OK, então agora, felizmente, nós só liberou quatro cadeiras. 501 00:20:07,490 --> 00:20:11,480 Então, usei o dobro da memória, mas podemos dar flip-flop entre 502 00:20:11,480 --> 00:20:12,330 duas matrizes. 503 00:20:12,330 --> 00:20:14,190 Então, qual é o número que vir primeiro? 504 00:20:14,190 --> 00:20:14,850 Então, Michelle, obviamente. 505 00:20:14,850 --> 00:20:16,680 Então, volta e pegue o seu lugar aqui. 506 00:20:16,680 --> 00:20:19,120 E, em seguida, o número 2 é obviamente Em seguida, assim que você vir aqui. 507 00:20:19,120 --> 00:20:21,520 Número 4, número 6. 508 00:20:21,520 --> 00:20:23,390 E mais uma vez, mesmo que não haja uma pouco de andar envolvido, 509 00:20:23,390 --> 00:20:26,010 realmente, estas poderiam acontecer imediatamente, , movendo uma - 510 00:20:26,010 --> 00:20:26,880 OK, bem jogado. 511 00:20:26,880 --> 00:20:28,350 >> [Risos] 512 00:20:28,350 --> 00:20:29,680 >> DAVID MALAN: E agora estamos em muito boa forma. 513 00:20:29,680 --> 00:20:34,910 A metade esquerda da totalidade entrada já foi resolvido. 514 00:20:34,910 --> 00:20:37,370 Tudo bem, então esses caras tinham a vantagem de a minha - 515 00:20:37,370 --> 00:20:40,340 como foi terminar todas as meninas na à esquerda e todos os meninos do lado direito? 516 00:20:40,340 --> 00:20:42,450 >> OK, então caras "virar agora. 517 00:20:42,450 --> 00:20:44,680 Então eu não vou levá-lo através estes passos. 518 00:20:44,680 --> 00:20:46,550 Vamos ver se podemos reaplicar o mesmo pseudocódigo. 519 00:20:46,550 --> 00:20:50,050 Se você quiser ir em frente e levantar-se, e vocês, deixe-me dar-lhe o microfone. 520 00:20:50,050 --> 00:20:52,990 Veja se você não pode replicar o que que fizemos aqui no 521 00:20:52,990 --> 00:20:53,880 outra extremidade da lista. 522 00:20:53,880 --> 00:20:59,530 Quem precisa falar primeiro, baseado no algoritmo? 523 00:20:59,530 --> 00:21:03,210 Então explique o que você está fazendo antes de de fazer quaisquer movimentos do pé. 524 00:21:03,210 --> 00:21:05,930 >> COLUNA 1: Tudo bem, então desde Eu sou a metade esquerda da 525 00:21:05,930 --> 00:21:07,790 metade esquerda, eu volto. 526 00:21:07,790 --> 00:21:08,730 Certo? 527 00:21:08,730 --> 00:21:09,250 >> DAVID MALAN: Ótimo. 528 00:21:09,250 --> 00:21:10,350 >> COLUNA 1: E então - 529 00:21:10,350 --> 00:21:11,800 >> DAVID MALAN: Quem faz o microfone ir para o próximo? 530 00:21:11,800 --> 00:21:12,920 >> COLUNA 1: número seguinte. 531 00:21:12,920 --> 00:21:14,720 >> COLUNA 2: Então, eu sou a metade direita da metade esquerda do 532 00:21:14,720 --> 00:21:17,830 metade esquerda, e eu voltar. 533 00:21:17,830 --> 00:21:18,050 >> DAVID MALAN: Ótimo. 534 00:21:18,050 --> 00:21:18,550 Você voltar. 535 00:21:18,550 --> 00:21:21,855 Então, agora, qual é a próxima para vocês dois? 536 00:21:21,855 --> 00:21:23,740 >> COLUNA 2: Queremos ver quem é menor. 537 00:21:23,740 --> 00:21:24,200 >> DAVID MALAN: Exatamente. 538 00:21:24,200 --> 00:21:24,940 Queremos fundir. 539 00:21:24,940 --> 00:21:27,590 O espaço que vamos usar para fundir você em, mesmo que sejam 540 00:21:27,590 --> 00:21:30,250 obviamente, já classificado, vamos a seguir o mesmo algoritmo. 541 00:21:30,250 --> 00:21:31,560 Então, quem vai em primeiro? 542 00:21:31,560 --> 00:21:35,720 Então, 3, e, em seguida, 7. 543 00:21:35,720 --> 00:21:38,570 E agora o microfone vai para esses caras, OK? 544 00:21:38,570 --> 00:21:43,590 >> COLUNA 3: Então, eu sou a metade direita do metade esquerda e meu n é inferior a 545 00:21:43,590 --> 00:21:45,048 1, então eu só vou passar - 546 00:21:45,048 --> 00:21:46,380 >> DAVID MALAN: Ótimo. 547 00:21:46,380 --> 00:21:49,450 >> COLUNA 4: Eu sou a metade direita do metade direita do lado direito, e eu sou 548 00:21:49,450 --> 00:21:51,740 também uma pessoa, por isso estou vai voltar. 549 00:21:51,740 --> 00:21:52,990 Então, agora que se fundem. 550 00:21:52,990 --> 00:21:55,140 551 00:21:55,140 --> 00:21:56,150 >> COLUNA 3: Então vamos voltar. 552 00:21:56,150 --> 00:21:57,160 >> DAVID MALAN: Então você vai para a parte de trás. 553 00:21:57,160 --> 00:21:59,200 Então, 5 vai em primeiro lugar, em seguida, 8. 554 00:21:59,200 --> 00:22:01,240 E agora público, que é o passo temos que voltar agora 555 00:22:01,240 --> 00:22:02,200 voltar para em nossas mentes? 556 00:22:02,200 --> 00:22:02,940 >> AUDIÊNCIA: Mesclar. 557 00:22:02,940 --> 00:22:07,270 >> DAVID MALAN: Fusão meia esquerda e direita a metade da metade esquerda inicial. 558 00:22:07,270 --> 00:22:08,840 Então, agora - 559 00:22:08,840 --> 00:22:10,520 e só para deixar isso claro, fazer um pouco de espaço 560 00:22:10,520 --> 00:22:11,690 entre vocês dois. 561 00:22:11,690 --> 00:22:13,800 Portanto, agora que é as duas listas, esquerda e direita. 562 00:22:13,800 --> 00:22:18,320 Então, como vamos agora unir a vocês em a primeira fila de assentos de novo? 563 00:22:18,320 --> 00:22:19,600 >> 3 vai pela primeira vez. 564 00:22:19,600 --> 00:22:20,850 Então, 5, obviamente. 565 00:22:20,850 --> 00:22:23,110 566 00:22:23,110 --> 00:22:27,330 Em seguida, 7, e agora 8. 567 00:22:27,330 --> 00:22:28,710 OK, e agora nós estamos? 568 00:22:28,710 --> 00:22:29,650 >> AUDIÊNCIA: Não feito. 569 00:22:29,650 --> 00:22:32,440 >> DAVID MALAN: Não feito, porque Obviamente, há uma única etapa restante. 570 00:22:32,440 --> 00:22:35,720 Mas, novamente, a razão que eu estou usando esta jargão como "retroceder em sua mente" 571 00:22:35,720 --> 00:22:37,160 é porque isso é realmente o que está acontecendo. 572 00:22:37,160 --> 00:22:39,610 Estamos passando por todas essas etapas, mas nós somos uma espécie de pausa para um 573 00:22:39,610 --> 00:22:42,480 momento, o mergulho mais profundo na algoritmo, parando por um momento, 574 00:22:42,480 --> 00:22:45,840 mergulho mais fundo no algoritmo, e agora temos a sorte de retrocesso em nossa 575 00:22:45,840 --> 00:22:49,430 mentes e desfazer todas essas camadas que temos uma espécie de colocar em espera. 576 00:22:49,430 --> 00:22:51,790 >> Portanto, agora temos duas listas de tamanho 4. 577 00:22:51,790 --> 00:22:54,790 Se vocês pudessem levantar-se uma última vez e fazer um pouco de espaço aqui para 578 00:22:54,790 --> 00:22:57,230 tornar claro que esta é a esquerda metade do original, o 579 00:22:57,230 --> 00:22:58,620 metade direita do original. 580 00:22:58,620 --> 00:23:01,060 Quem é o primeiro número que precisa puxar na parte de trás? 581 00:23:01,060 --> 00:23:01,870 Michelle, é claro. 582 00:23:01,870 --> 00:23:03,230 >> Então nós colocamos Michelle aqui. 583 00:23:03,230 --> 00:23:05,080 E quem tem o número 2? 584 00:23:05,080 --> 00:23:06,440 Número 2 vem na parte de trás também. 585 00:23:06,440 --> 00:23:07,800 Número 3? 586 00:23:07,800 --> 00:23:08,510 Excelente. 587 00:23:08,510 --> 00:23:16,570 Número 4, número 5, número 6, o número 7, e o número 8. 588 00:23:16,570 --> 00:23:18,850 >> OK, por isso parecia muito de passos, com certeza. 589 00:23:18,850 --> 00:23:22,390 Mas agora vamos ver se não podemos confirmar tipo de intuitivamente que este 590 00:23:22,390 --> 00:23:26,190 algoritmo fundamental, especialmente no que n fica muito grande, como já vimos 591 00:23:26,190 --> 00:23:29,170 com as animações, é fundamentalmente mais rápido. 592 00:23:29,170 --> 00:23:33,400 Então, eu reivindico este algoritmo, no pior caso, e mesmo no melhor dos casos, 593 00:23:33,400 --> 00:23:36,160 é grande O de n log n vezes. 594 00:23:36,160 --> 00:23:39,160 Ou seja, há algum aspecto deste algoritmo que leva n passos, mas 595 00:23:39,160 --> 00:23:43,110 há um outro aspecto em algum lugar iteração, que looping, que 596 00:23:43,110 --> 00:23:44,410 leva log n passos. 597 00:23:44,410 --> 00:23:49,154 Podemos colocar o dedo sobre o que os dois números estão se referindo? 598 00:23:49,154 --> 00:23:51,320 Bem, onde - 599 00:23:51,320 --> 00:23:54,160 o microfone pra onde ir? 600 00:23:54,160 --> 00:23:58,660 >> COLUNA 1: Será que o log n ser quebrando-nos em dois - 601 00:23:58,660 --> 00:23:59,630 dividindo por dois, essencialmente. 602 00:23:59,630 --> 00:24:00,120 >> DAVID MALAN: Exatamente. 603 00:24:00,120 --> 00:24:03,000 Toda vez que vemos em qualquer algoritmo, portanto, agora, não tem sido esse padrão de 604 00:24:03,000 --> 00:24:04,200 divisória, dividindo, dividindo. 605 00:24:04,200 --> 00:24:05,700 E é normalmente reduzida a algo que é 606 00:24:05,700 --> 00:24:07,100 logarítmica, base 2 log. 607 00:24:07,100 --> 00:24:10,180 Mas pode realmente ser qualquer coisa, mas log base 2. 608 00:24:10,180 --> 00:24:11,330 >> Agora, o que dizer do n? 609 00:24:11,330 --> 00:24:14,550 Eu posso ver que tipo de dividido você homens - divididos você, divididos você, 610 00:24:14,550 --> 00:24:15,910 divididos você, divididos você. 611 00:24:15,910 --> 00:24:18,760 Onde é que o fim vem? 612 00:24:18,760 --> 00:24:19,810 >> Portanto, é a fusão. 613 00:24:19,810 --> 00:24:20,610 Porque pensar nisso. 614 00:24:20,610 --> 00:24:25,420 Quando você mescla oito pessoas em conjunto, em que metade deles são um conjunto de quatro 615 00:24:25,420 --> 00:24:27,770 e a outra metade é outra conjunto de quatro, como você vai 616 00:24:27,770 --> 00:24:28,820 sobre como fazer a fusão? 617 00:24:28,820 --> 00:24:30,830 Bem, vocês fizeram isso bastante intuitiva. 618 00:24:30,830 --> 00:24:34,140 >> Mas, se em vez fiz um pouco mais metodicamente, eu poderia ter apontado para 619 00:24:34,140 --> 00:24:38,090 a pessoa mais à esquerda pela primeira vez com a minha esquerda mão, apontou para a pessoa mais à esquerda 620 00:24:38,090 --> 00:24:42,080 de que a metade com a minha mão direita, e só posteriormente passou pela 621 00:24:42,080 --> 00:24:46,990 lista, apontando para o menor elemento cada vez, movendo o dedo sobre e 622 00:24:46,990 --> 00:24:48,970 sobre quando necessário ao longo da lista. 623 00:24:48,970 --> 00:24:51,890 Mas o que é importante sobre esta fusão processo é que eu estou comparando esses pares 624 00:24:51,890 --> 00:24:53,460 de elementos. 625 00:24:53,460 --> 00:24:57,270 A partir da metade da direita e da esquerda metade, estou nunca uma vez retrocesso. 626 00:24:57,270 --> 00:25:00,570 >> Assim, o próprio merge está tomando não mais do que n passos. 627 00:25:00,570 --> 00:25:03,250 E quantas vezes eu tive para fazer que a fusão? 628 00:25:03,250 --> 00:25:07,150 Bem, não mais do que n, e nós apenas viu que, com a fusão final. 629 00:25:07,150 --> 00:25:13,120 E por isso, se você faz algo que leva log vezes n passos n, ou vice-versa, 630 00:25:13,120 --> 00:25:15,210 ele vai nos n log n vezes dar. 631 00:25:15,210 --> 00:25:16,310 >> E por que isso é melhor? 632 00:25:16,310 --> 00:25:19,600 Bem, se já sabemos que log n é melhor do que n - certo? 633 00:25:19,600 --> 00:25:22,590 Vimos em busca binária, o livro de telefone exemplo, log n foi definitivamente 634 00:25:22,590 --> 00:25:23,760 melhor do que o linear. 635 00:25:23,760 --> 00:25:28,420 Então isso significa que n log n vezes é definitivamente melhor do que n vezes outro 636 00:25:28,420 --> 00:25:30,390 n, AKA n ao quadrado. 637 00:25:30,390 --> 00:25:32,400 E isso é o que finalmente se sente. 638 00:25:32,400 --> 00:25:34,928 >> Tão grande salva de palmas, se pudéssemos, para esses caras. 639 00:25:34,928 --> 00:25:38,920 >> [Aplausos] 640 00:25:38,920 --> 00:25:41,550 >> DAVID MALAN: E os seus presentes de despedida - você pode manter os números, 641 00:25:41,550 --> 00:25:44,010 se você gostaria. 642 00:25:44,010 --> 00:25:45,620 E o seu presente de despedida, como de costume. 643 00:25:45,620 --> 00:25:47,290 Oh, e nós lhe enviaremos a metragem, Michelle. 644 00:25:47,290 --> 00:25:48,343 Obrigado. 645 00:25:48,343 --> 00:25:49,250 Tudo bem. 646 00:25:49,250 --> 00:25:50,400 Sirva-se de uma bola de stress. 647 00:25:50,400 --> 00:25:54,110 >> E deixe-me puxar para cima, entretanto, nosso amigo Rob Bowden para oferecer 648 00:25:54,110 --> 00:25:59,520 perspectiva um pouco diferente deste, desde que você pode pensar sobre estes 649 00:25:59,520 --> 00:26:01,280 etapas que acontecem em um pouco maneira diferente. 650 00:26:01,280 --> 00:26:04,750 Na verdade, o set-up para o que Rob está prestes para nos mostrar assume que nós temos 651 00:26:04,750 --> 00:26:09,030 feito a divisão do grande lista em oito pequenas listas, 652 00:26:09,030 --> 00:26:10,570 cada um de tamanho 1. 653 00:26:10,570 --> 00:26:13,350 >> Então, nós estamos mudando o pseudocódigo a pouco apenas a sorte de chegar ao 654 00:26:13,350 --> 00:26:15,320 ideia central de como a fusão obras. 655 00:26:15,320 --> 00:26:17,600 Mas o tempo de funcionamento do que ele está prestes a fazer ainda é 656 00:26:17,600 --> 00:26:19,110 vai ser o mesmo. 657 00:26:19,110 --> 00:26:23,540 E, novamente, o set-up aqui é que ele é iniciado com oito listas de tamanho 1. 658 00:26:23,540 --> 00:26:27,730 Então você perdeu a parte onde ele é realmente fez o log n, n log, log n 659 00:26:27,730 --> 00:26:31,205 divisão da entrada. 660 00:26:31,205 --> 00:26:32,120 >> [REPRODUÇÃO] 661 00:26:32,120 --> 00:26:33,615 >> -Isso é tudo por um passo. 662 00:26:33,615 --> 00:26:38,270 Para a segunda etapa, repetidamente pares de listas de mala direta. 663 00:26:38,270 --> 00:26:39,210 >> DAVID MALAN: Hm. 664 00:26:39,210 --> 00:26:41,270 Só áudio está chegando fora do meu computador. 665 00:26:41,270 --> 00:26:42,520 Vamos tentar isso novamente. 666 00:26:42,520 --> 00:26:45,330 667 00:26:45,330 --> 00:26:48,310 >> -Just arbitrariamente escolher qual - agora temos quatro listas. 668 00:26:48,310 --> 00:26:51,590 669 00:26:51,590 --> 00:26:52,120 Saiba antes. 670 00:26:52,120 --> 00:26:53,040 >> DAVID MALAN: Lá vamos nós. 671 00:26:53,040 --> 00:27:00,510 >> Mesclando-108 e 15, terminamos com a lista de 15, 108. 672 00:27:00,510 --> 00:27:07,170 Fundir 50 e 4, temos acabar com 4, 50. 673 00:27:07,170 --> 00:27:12,990 Mesclando 8 e 42, que acabar com 8, 42. 674 00:27:12,990 --> 00:27:19,970 E fusão 23 e 16, nós acabar com 16, 23. 675 00:27:19,970 --> 00:27:23,270 >> Agora todas as nossas listas são de tamanho 2. 676 00:27:23,270 --> 00:27:26,690 Note-se que cada um dos quatro listas é classificado. 677 00:27:26,690 --> 00:27:29,450 Assim, podemos começar a fundir pares de listas novamente. 678 00:27:29,450 --> 00:27:38,420 Mesclando 15 e 108 e 4 e 50, que tire primeiro a 4, depois a 15, em seguida, 679 00:27:38,420 --> 00:27:41,500 a 50, depois a 108. 680 00:27:41,500 --> 00:27:50,610 Mesclando 8, 42 e 16, 23, primeiro tomar a 8, em seguida, a 16, depois a 23, 681 00:27:50,610 --> 00:27:52,700 em seguida, a 42. 682 00:27:52,700 --> 00:27:57,600 >> Portanto, agora temos apenas duas listas de tamanho 4, cada um dos quais é classificado. 683 00:27:57,600 --> 00:28:01,170 Então, agora nós mesclar essas duas listas. 684 00:28:01,170 --> 00:28:11,835 Primeiro, tomamos a 4, depois tomamos o 8, então tomamos o 15, então com 16 anos, em seguida, 685 00:28:11,835 --> 00:28:19,456 23, depois 42, depois 50, depois 108. 686 00:28:19,456 --> 00:28:19,872 >> [FIM REPRODUÇÃO DE VÍDEO] 687 00:28:19,872 --> 00:28:23,430 >> DAVID MALAN: Mais uma vez, o aviso prévio, ele nunca tocado um determinado copo mais do que uma vez 688 00:28:23,430 --> 00:28:24,860 depois de avançar além dela. 689 00:28:24,860 --> 00:28:26,200 Assim, ele nunca repetir. 690 00:28:26,200 --> 00:28:29,850 Então ele está sempre se movendo para o lado, e é aí que temos o nosso n. 691 00:28:29,850 --> 00:28:33,290 >> Por que não deixar me puxar para cima uma animação que vimos anteriormente, mas desta vez 692 00:28:33,290 --> 00:28:35,110 incidindo apenas sobre merge sort. 693 00:28:35,110 --> 00:28:38,030 Deixe-me ir em frente e fazer zoom na nesta aqui. 694 00:28:38,030 --> 00:28:42,530 Primeiro deixe-me escolher uma entrada aleatória, ampliar isso, e você pode classificar de ver 695 00:28:42,530 --> 00:28:46,600 o que nós tomamos para concedido, anteriormente, merge sort está realmente fazendo. 696 00:28:46,600 --> 00:28:50,330 >> Então, observe que você obter essas metades ou estes quartos ou estes oitavos da 697 00:28:50,330 --> 00:28:53,140 problema que, de repente, começar a tomar boa forma. 698 00:28:53,140 --> 00:28:57,070 E então, finalmente, você vê a o fim que bam, 699 00:28:57,070 --> 00:28:58,860 tudo é mesclado juntos. 700 00:28:58,860 --> 00:29:01,690 >> Então, essas são apenas três diferentes assume a mesma ideia. 701 00:29:01,690 --> 00:29:05,980 Mas o insight chave, assim como dividir e conquistar na primeira classe, 702 00:29:05,980 --> 00:29:10,640 foi que decidimos dividir de alguma forma o problema em algo grande, em 703 00:29:10,640 --> 00:29:14,760 algo tipo de idêntico em espírito, mas menores e menores 704 00:29:14,760 --> 00:29:15,660 e menores. 705 00:29:15,660 --> 00:29:18,420 >> Agora uma outra forma divertida de classificar de pensar sobre estes, apesar de que não é 706 00:29:18,420 --> 00:29:20,520 vai dar-lhe o mesmo intuitivo entendimento, é 707 00:29:20,520 --> 00:29:21,640 o seguinte animação. 708 00:29:21,640 --> 00:29:25,400 Portanto, este é um vídeo de alguém juntos que associado diferente 709 00:29:25,400 --> 00:29:29,970 sons com as várias operações para ordenação por inserção, por merge sort, e 710 00:29:29,970 --> 00:29:31,150 por um par de outros. 711 00:29:31,150 --> 00:29:32,330 Então, em um momento, eu vou bater Play. 712 00:29:32,330 --> 00:29:33,600 Trata-se de um minuto de duração. 713 00:29:33,600 --> 00:29:37,410 E mesmo que você ainda pode ver a padrões acontecendo, neste momento você pode 714 00:29:37,410 --> 00:29:41,420 também ouvir como esses algoritmos são realizar de maneira diferente e com 715 00:29:41,420 --> 00:29:43,950 um pouco diferentes padrões. 716 00:29:43,950 --> 00:29:45,830 >> Esta é a ordenação por inserção. 717 00:29:45,830 --> 00:29:50,400 >> [TONS JOGO] 718 00:29:50,400 --> 00:29:52,400 >> DAVID MALAN: Ele novamente está tentando para inserir cada elemento 719 00:29:52,400 --> 00:29:52,900 para onde ela pertence. 720 00:29:52,900 --> 00:29:54,628 Este é bubble sort. 721 00:29:54,628 --> 00:30:10,097 >> [TONS JOGO] 722 00:30:10,097 --> 00:30:13,630 >> DAVID MALAN: E você pode classificar de sensação como relativamente pouco trabalho que está fazendo 723 00:30:13,630 --> 00:30:15,834 em cada passo. 724 00:30:15,834 --> 00:30:20,470 Isto é o tédio parece. 725 00:30:20,470 --> 00:30:21,472 >> [TONS JOGO] 726 00:30:21,472 --> 00:30:25,222 >> DAVID MALAN: Esta é a seleção de tipo, onde se selecionar o elemento que queremos por 727 00:30:25,222 --> 00:30:28,845 passando por uma e outra vez e outra vez e colocá-lo no início. 728 00:30:28,845 --> 00:30:37,674 >> [TONS JOGO] 729 00:30:37,674 --> 00:30:43,970 >> DAVID MALAN: Este é o merge sort, que você pode realmente começar a sentir-se. 730 00:30:43,970 --> 00:30:51,810 >> [TONS JOGO] 731 00:30:51,810 --> 00:30:54,770 >> [Risos] 732 00:30:54,770 --> 00:30:58,395 >> DAVID MALAN: Algo chamado gnome tipo, que não olhei. 733 00:30:58,395 --> 00:31:13,630 >> [TONS JOGO] 734 00:31:13,630 --> 00:31:17,910 >> DAVID MALAN: Então deixe-me ver, agora, distraído como você espera, segundo a 735 00:31:17,910 --> 00:31:21,110 música, se eu posso escorregar um pouco pouco de matemática aqui. 736 00:31:21,110 --> 00:31:24,850 Portanto, há uma quarta forma que pudermos pensar sobre o que significa que estes 737 00:31:24,850 --> 00:31:29,210 funções para ser mais rápido do que os que já vimos antes. 738 00:31:29,210 --> 00:31:32,470 E se você está vindo para o curso de um fundo de matemática, você 739 00:31:32,470 --> 00:31:36,030 realmente sabe, talvez, já que você pode bater um termo sobre esta técnica - 740 00:31:36,030 --> 00:31:40,400 ou seja, a recursividade, uma função que de alguma forma se autodenomina. 741 00:31:40,400 --> 00:31:44,780 >> E mais uma vez, lembrar que merge sort pseudocódigo foi recursivo no sentido 742 00:31:44,780 --> 00:31:48,460 que uma das etapas do merge sort foi chamar espécie - 743 00:31:48,460 --> 00:31:49,740 que é, em si. 744 00:31:49,740 --> 00:31:52,480 Mas, felizmente, porque mantivemos chamando tipo, ou merge sort, 745 00:31:52,480 --> 00:31:55,880 especificamente, numa menor e menor e uma lista menor, eventualmente 746 00:31:55,880 --> 00:32:00,005 ao fundo do poço graças ao que chamaremos um caso base, no caso hard-coded que 747 00:32:00,005 --> 00:32:04,270 disse que se a lista é pequena, menos de 2 Nesse caso, basta retornar imediatamente. 748 00:32:04,270 --> 00:32:07,550 Se não tivéssemos esse caso especial, a algoritmo seria nunca inferior para fora, 749 00:32:07,550 --> 00:32:11,010 e você realmente entrar em um loop infinito verdadeiramente para sempre. 750 00:32:11,010 --> 00:32:14,330 >> Mas suponha que queremos agora colocar alguns números no presente, de novo, utilizando n 751 00:32:14,330 --> 00:32:15,660 medida que o tamanho da entrada. 752 00:32:15,660 --> 00:32:18,680 E eu queria te perguntar, o que é o tempo total envolvido 753 00:32:18,680 --> 00:32:19,800 execução merge sort? 754 00:32:19,800 --> 00:32:22,960 Ou, mais geralmente, o que é o custo do mesmo no tempo? 755 00:32:22,960 --> 00:32:24,730 >> Bem, é muito fácil de medir isso. 756 00:32:24,730 --> 00:32:29,010 Se n for menor do que 2, o tempo envolvido na classificação de n elementos, 757 00:32:29,010 --> 00:32:30,480 onde n é 2, é 0. 758 00:32:30,480 --> 00:32:31,410 Porque nós só retornar. 759 00:32:31,410 --> 00:32:32,510 Não há trabalho a ser feito. 760 00:32:32,510 --> 00:32:35,660 Agora, sem dúvida, talvez seja um passo ou dois passos para descobrir a quantidade de 761 00:32:35,660 --> 00:32:38,420 trabalhar, mas é perto o suficiente para que 0 Eu só vou dizer que não trabalho é 762 00:32:38,420 --> 00:32:40,940 necessário se a lista é tão pequena para ser desinteressante. 763 00:32:40,940 --> 00:32:42,580 >> Mas, neste caso, é interessante. 764 00:32:42,580 --> 00:32:47,320 O caso recursivo foi o ramo de o pseudocódigo que disse outra coisa, tipo 765 00:32:47,320 --> 00:32:52,000 a metade esquerda, classificar o direito metade, unir as duas metades. 766 00:32:52,000 --> 00:32:55,530 Agora, por que esta expressão representar essa despesa? 767 00:32:55,530 --> 00:32:58,690 Bem, T de n significa apenas que o tempo para ordenar n elementos. 768 00:32:58,690 --> 00:33:03,070 E, em seguida, no lado direito da sinal de igual lá, o T de n dividido 769 00:33:03,070 --> 00:33:06,600 por 2 refere-se ao custo de quê? 770 00:33:06,600 --> 00:33:07,570 Classificando a metade esquerda. 771 00:33:07,570 --> 00:33:10,990 O outro T de n dividido por 2 é presumivelmente, referindo-se ao custo de 772 00:33:10,990 --> 00:33:12,390 classificar a metade direita. 773 00:33:12,390 --> 00:33:14,590 >> E então o mais n? 774 00:33:14,590 --> 00:33:15,420 É a fusão. 775 00:33:15,420 --> 00:33:19,120 Porque se você tem duas listas, uma de tamanho n superior a 2 e outra de tamanho n 776 00:33:19,120 --> 00:33:22,580 mais de 2, você tem que tocar essencialmente cada um desses elementos, assim como Rob 777 00:33:22,580 --> 00:33:24,990 tocou cada um dos copos, e apenas como se apontou para cada um dos 778 00:33:24,990 --> 00:33:26,310 voluntários no palco. 779 00:33:26,310 --> 00:33:28,790 Assim, n é à custa de fusão. 780 00:33:28,790 --> 00:33:31,780 >> Agora, infelizmente, esta fórmula é também próprio recursiva. 781 00:33:31,780 --> 00:33:36,390 Assim se fez a pergunta, se n é, digamos, 16, se há 16 pessoas no palco 782 00:33:36,390 --> 00:33:40,670 ou 16 xícaras no vídeo, quantos total de passos que é necessário para classificá-los 783 00:33:40,670 --> 00:33:41,550 com merge sort? 784 00:33:41,550 --> 00:33:45,790 Na verdade não é uma resposta óbvia, porque agora você tem a sorte de 785 00:33:45,790 --> 00:33:48,500 recursivamente responder a esta fórmula. 786 00:33:48,500 --> 00:33:51,190 >> Mas tudo bem, porque deixe-me propor que faça o seguinte. 787 00:33:51,190 --> 00:33:56,670 O tempo envolvido para classificar ou 16 pessoas 16 xícaras vai ser representado 788 00:33:56,670 --> 00:33:58,020 geralmente como T de 16. 789 00:33:58,020 --> 00:34:01,400 Mas o que é igual a, de acordo com o nosso fórmula anterior, duas vezes a quantidade 790 00:34:01,400 --> 00:34:04,780 de tempo que leva para classificar 8 copos mais 16. 791 00:34:04,780 --> 00:34:08,590 E, novamente, mais 16 é o momento de fusão, E as duas vezes T de 8 é o 792 00:34:08,590 --> 00:34:10,790 tempo para resolver metade esquerda e metade direita. 793 00:34:10,790 --> 00:34:11,989 >> Mas, novamente, isso não é suficiente. 794 00:34:11,989 --> 00:34:13,210 Temos que mergulhar mais fundo. 795 00:34:13,210 --> 00:34:16,409 Isso significa que temos de responder à pergunta, o que é T de 8? 796 00:34:16,409 --> 00:34:19,610 Bem T de 8 está apenas a 2 t de 4 vezes mais de 8. 797 00:34:19,610 --> 00:34:20,520 Bem, o que é T de 4? 798 00:34:20,520 --> 00:34:23,780 T de 4 está a apenas 2 vezes T de 2 + 4. 799 00:34:23,780 --> 00:34:25,489 Bem, o que é T de 2? 800 00:34:25,489 --> 00:34:29,030 T de 2 é apenas 2 vezes T de 1 mais 2. 801 00:34:29,030 --> 00:34:31,940 >> E, novamente, nós somos o tipo de conseguir preso neste ciclo. 802 00:34:31,940 --> 00:34:34,790 Mas isso está prestes a bater esse o chamado caso base. 803 00:34:34,790 --> 00:34:37,310 Porque o que é T de 1, não podemos reclamar? 804 00:34:37,310 --> 00:34:37,810 0. 805 00:34:37,810 --> 00:34:39,730 Então, agora, finalmente, podemos trabalhar para trás. 806 00:34:39,730 --> 00:34:44,290 >> Se T 1 é 0, agora posso voltar a subir um alinhar com esse cara aqui, e eu posso 807 00:34:44,290 --> 00:34:46,330 conecte 0 para T de 1. 808 00:34:46,330 --> 00:34:51,770 Então, isso significa que ele é igual a 2 vezes a zero, também conhecido como 0, acrescido de 2. 809 00:34:51,770 --> 00:34:53,739 E, de modo que toda a expressão é 2. 810 00:34:53,739 --> 00:34:58,740 >> Agora, se eu pegar o T de 2, cuja resposta é 2, ligá-lo na linha do meio, T 811 00:34:58,740 --> 00:35:02,740 de 4, que me dá duas vezes 2 + 4, de modo 8. 812 00:35:02,740 --> 00:35:07,080 Ora, se eu ligar 8 a anterior linha, que me dá duas vezes 8, 16. 813 00:35:07,080 --> 00:35:12,470 E se, em seguida, continuar com o que 24, acrescentando em 16 de finalmente obter um 814 00:35:12,470 --> 00:35:13,820 valor de 64. 815 00:35:13,820 --> 00:35:18,480 >> Agora que em si mesmo tipo de fala nada para a notação n, o 816 00:35:18,480 --> 00:35:20,700 O grande, o omega que temos falando. 817 00:35:20,700 --> 00:35:24,890 Mas verifica-se que 64 é de fato 16, o tamanho da entrada, 818 00:35:24,890 --> 00:35:27,110 log base 2, de 16. 819 00:35:27,110 --> 00:35:30,200 E se isso é um pouco estranho, apenas acho que volta, e ele vai voltar 820 00:35:30,200 --> 00:35:30,700 para que você eventualmente. 821 00:35:30,700 --> 00:35:33,775 Se este é o log base 2, é como 2 elevado para o que lhe dá 16? 822 00:35:33,775 --> 00:35:36,380 Oh, isso é 4, por isso é 16 vezes 4. 823 00:35:36,380 --> 00:35:39,380 >> E mais uma vez, não é um grande negócio se este é uma espécie de memória nebulosa agora. 824 00:35:39,380 --> 00:35:43,720 Mas, por enquanto, assumir a fé que 16 log 16 é 64. 825 00:35:43,720 --> 00:35:46,590 E assim, de fato, com esta simples sanidade verificar, temos confirmada - 826 00:35:46,590 --> 00:35:48,250 mas não provou formalmente - 827 00:35:48,250 --> 00:35:52,800 que o tempo de execução de fusão espécie é realmente n log n. 828 00:35:52,800 --> 00:35:53,790 >> Então, não é mau. 829 00:35:53,790 --> 00:35:57,260 É definitivamente melhor do que o algoritmos que temos visto até agora, e 830 00:35:57,260 --> 00:36:00,710 é porque temos alavancado, um, uma técnica chamada de recursão. 831 00:36:00,710 --> 00:36:03,880 Mas o mais interessante do que isso, que noção de dividir e conquistar. 832 00:36:03,880 --> 00:36:07,460 Mais uma vez, verdadeiramente semana 0 coisas que até agora é recorrente em 833 00:36:07,460 --> 00:36:08,740 forma mais convincente. 834 00:36:08,740 --> 00:36:11,750 >> Agora, um pouco de exercício divertido, se você tem nunca fiz isso - e você provavelmente 835 00:36:11,750 --> 00:36:14,660 não teria, porque tipo do normal as pessoas não pensam para fazer isso. 836 00:36:14,660 --> 00:36:20,650 Mas se eu for para google.com e se Eu quero aprender algo sobre 837 00:36:20,650 --> 00:36:22,356 recursão, Enter. 838 00:36:22,356 --> 00:36:25,106 839 00:36:25,106 --> 00:36:29,058 >> [Risos] 840 00:36:29,058 --> 00:36:32,030 [Mais risos] 841 00:36:32,030 --> 00:36:33,385 DAVID MALAN: Bad piada espalhando lentamente. 842 00:36:33,385 --> 00:36:34,450 [Risos] 843 00:36:34,450 --> 00:36:36,970 DAVID MALAN: Apenas no caso, ele está lá. 844 00:36:36,970 --> 00:36:38,710 Eu não soletrar errado, e há a piada. 845 00:36:38,710 --> 00:36:40,810 Tudo bem. 846 00:36:40,810 --> 00:36:42,950 Explique-os pessoas próximas a você se ele não tem muito clicado ainda. 847 00:36:42,950 --> 00:36:47,650 Mas recursão, de modo mais geral, refere-se para o processo de uma função de chamada 848 00:36:47,650 --> 00:36:51,430 si só, ou, mais geralmente, a divisão de um problema em algo que pode ser 849 00:36:51,430 --> 00:36:56,220 resolvidos aos poucos, resolvendo idêntico problemas de representação. 850 00:36:56,220 --> 00:36:58,400 >> Bem, vamos engrenagens de mudança apenas por um momento. 851 00:36:58,400 --> 00:37:00,840 Gostamos de terminar em certos cliffhangers, então vamos começar a definir 852 00:37:00,840 --> 00:37:05,870 a fase, durante vários minutos, em uma idéia muito simples - 853 00:37:05,870 --> 00:37:07,620 que a troca de dois elementos, certo? 854 00:37:07,620 --> 00:37:10,040 Todos esses algoritmos que estivemos falando sobre o último par de 855 00:37:10,040 --> 00:37:12,420 palestras envolvem algum tipo de troca. 856 00:37:12,420 --> 00:37:14,630 Hoje foi visualizado por eles recebendo -se de suas cadeiras e 857 00:37:14,630 --> 00:37:18,570 andando por aí, mas no código, faríamos basta ter um elemento de uma matriz 858 00:37:18,570 --> 00:37:20,370 e plop-lo em outro. 859 00:37:20,370 --> 00:37:21,880 >> Então, como vamos fazer isso? 860 00:37:21,880 --> 00:37:24,850 Bem, deixe-me ir em frente e escrever um programa rápido aqui. 861 00:37:24,850 --> 00:37:31,600 Eu estou indo para ir em frente e fazer isto como a seguir. 862 00:37:31,600 --> 00:37:33,910 Vamos chamar isso - 863 00:37:33,910 --> 00:37:38,070 o que queremos chamar esse? 864 00:37:38,070 --> 00:37:38,650 >> Na verdade, não. 865 00:37:38,650 --> 00:37:39,420 Deixe-me voltar atrás. 866 00:37:39,420 --> 00:37:41,220 Eu não quero fazer isso suspense ainda. 867 00:37:41,220 --> 00:37:42,270 Vai estragar a diversão. 868 00:37:42,270 --> 00:37:43,600 Vamos fazer isso em seu lugar. 869 00:37:43,600 --> 00:37:47,430 >> Suponha que eu quero escrever um pouco programa e que agora abraça este 870 00:37:47,430 --> 00:37:48,700 idéia de recursão. 871 00:37:48,700 --> 00:37:50,370 Eu meio que tenho à frente de mim lá. 872 00:37:50,370 --> 00:37:51,420 Eu vou fazer o seguinte. 873 00:37:51,420 --> 00:38:00,220 >> Primeiro, um rápido incluem padrão de io.h, , bem como uma inclusão de cs50.h. 874 00:38:00,220 --> 00:38:03,200 E então eu estou indo para ir em frente e declarar int void main 875 00:38:03,200 --> 00:38:04,360 da maneira usual. 876 00:38:04,360 --> 00:38:07,920 Eu percebi que eu tenho chamado erroneamente o arquivo, assim deixe-me adicionar uma extensão c. aqui para 877 00:38:07,920 --> 00:38:09,510 que podemos compilá-lo corretamente. 878 00:38:09,510 --> 00:38:10,970 Comece esta função. 879 00:38:10,970 --> 00:38:13,290 >> E a função que eu quero escrever, muito simplesmente, é aquele que faz a 880 00:38:13,290 --> 00:38:16,210 usuário para um número e, em seguida, acrescenta-se todos os números entre esse 881 00:38:16,210 --> 00:38:19,920 número e, por exemplo, 0. 882 00:38:19,920 --> 00:38:22,510 Então, primeiro eu vou seguir em frente e declarar int n. 883 00:38:22,510 --> 00:38:24,760 Então eu copiar um código que nós usamos por um tempo. 884 00:38:24,760 --> 00:38:26,660 Enquanto algo é verdadeiro. 885 00:38:26,660 --> 00:38:28,000 Eu vou voltar a isso em um momento. 886 00:38:28,000 --> 00:38:29,010 >> O que eu quero fazer? 887 00:38:29,010 --> 00:38:33,460 Eu quero dizer printf positivo inteiro por favor. 888 00:38:33,460 --> 00:38:36,130 E então eu vou dizem que n recebe obter int. 889 00:38:36,130 --> 00:38:38,800 Então, novamente, algum código clichê que usei antes. 890 00:38:38,800 --> 00:38:40,810 E eu vou fazer isso enquanto n for menor do que 1. 891 00:38:40,810 --> 00:38:44,120 Assim, isto irá assegurar que o utilizador me dá um número inteiro positivo. 892 00:38:44,120 --> 00:38:45,490 >> E agora eu vou fazer o seguinte. 893 00:38:45,490 --> 00:38:51,020 Quero somar todos os números e entre 1 e n, ou 0 e n, 894 00:38:51,020 --> 00:38:52,570 equivalentemente, para obter a soma total. 895 00:38:52,570 --> 00:38:55,100 Assim, o símbolo grande sigma que você pode se lembrar. 896 00:38:55,100 --> 00:38:59,050 Então, eu vou fazer isso pela primeira convocação uma função chamada sigma, 897 00:38:59,050 --> 00:39:06,030 passá-lo em n, e então eu vou printf dizer, a resposta está logo ali. 898 00:39:06,030 --> 00:39:08,180 >> Assim, em breve, eu recebo e int do usuário. 899 00:39:08,180 --> 00:39:09,280 I garantir que ele é positivo. 900 00:39:09,280 --> 00:39:12,700 Eu declaro uma variável chamada resposta de tipo int e armazenar em que o retorno 901 00:39:12,700 --> 00:39:15,610 valor de sigma, passando n como entrada. 902 00:39:15,610 --> 00:39:17,060 E então eu imprimir essa resposta. 903 00:39:17,060 --> 00:39:19,550 >> Infelizmente, embora sigma soa como algo que pode estar em 904 00:39:19,550 --> 00:39:24,040 o arquivo math.h, sua declaração, isso não é verdade. 905 00:39:24,040 --> 00:39:24,690 Então, isso é OK. 906 00:39:24,690 --> 00:39:26,170 Eu posso implementar isso mesmo. 907 00:39:26,170 --> 00:39:29,160 Vou implementar uma função chamada sigma, e isso vai levar um 908 00:39:29,160 --> 00:39:29,900 parâmetro - 909 00:39:29,900 --> 00:39:32,100 vamos chamá-lo m, apenas por isso é diferente. 910 00:39:32,100 --> 00:39:35,910 E, em seguida, até aqui, eu vou dizer, assim, se m for menor do que 1 - Este é um 911 00:39:35,910 --> 00:39:38,180 programa muito desinteressante. 912 00:39:38,180 --> 00:39:41,700 Então, eu estou indo para ir em frente e imediatamente retornar 0. 913 00:39:41,700 --> 00:39:45,920 Ele simplesmente não faz sentido somar todos os números entre 1 e m se m 914 00:39:45,920 --> 00:39:48,470 0 é ele próprio ou negativo. 915 00:39:48,470 --> 00:39:50,900 >> E então eu estou indo para ir em frente e fazer isso muito iterativa. 916 00:39:50,900 --> 00:39:53,090 Eu vou fazer esse tipo de old-school, e eu estou indo para ir em frente 917 00:39:53,090 --> 00:39:57,150 e dizer que eu vou declarar uma quantia a ser 0. 918 00:39:57,150 --> 00:39:59,630 Então eu vou ter um loop de int - 919 00:39:59,630 --> 00:40:02,820 e deixe-me fazê-lo para coincidir com o nosso Código de distribuição, para que você tenha uma cópia 920 00:40:02,820 --> 00:40:07,500 em casa. int i recebe 1 em até i é inferior ou igual a m. 921 00:40:07,500 --> 00:40:09,430 i plus plus. 922 00:40:09,430 --> 00:40:11,430 E, em seguida, dentro deste loop - 923 00:40:11,430 --> 00:40:12,440 estamos quase lá - 924 00:40:12,440 --> 00:40:15,810 soma fica soma mais 1. 925 00:40:15,810 --> 00:40:17,670 E então eu vou retornar a soma. 926 00:40:17,670 --> 00:40:19,420 >> Então eu fiz isso rapidamente, reconhecidamente bastante. 927 00:40:19,420 --> 00:40:22,775 Mas, novamente, a principal função é muito simples, com base no código temos 928 00:40:22,775 --> 00:40:23,190 escrito até agora. 929 00:40:23,190 --> 00:40:25,610 Utiliza o loop duplo para obter uma positiva int do usuário. 930 00:40:25,610 --> 00:40:29,870 Eu, então, passar essa int para uma nova função chamado sigma, chamando-o, mais uma vez, n. 931 00:40:29,870 --> 00:40:33,100 E eu armazenar o valor de retorno, a resposta da caixa preta atualmente 932 00:40:33,100 --> 00:40:35,460 conhecido como sigma, em uma variável chamada de resposta. 933 00:40:35,460 --> 00:40:36,580 Então eu imprimi-lo. 934 00:40:36,580 --> 00:40:39,090 >> Se agora continuar a história, como é sigma implementado? 935 00:40:39,090 --> 00:40:40,840 Proponho para implementar o seguinte. 936 00:40:40,840 --> 00:40:43,560 Primeiro, um pouco de verificação de erros para se certificar de que o usuário não é 937 00:40:43,560 --> 00:40:46,480 brincando comigo e passando algum valor negativo ou 0. 938 00:40:46,480 --> 00:40:49,710 Então eu declarar uma variável chamada Resumindo e configurá-lo para 0. 939 00:40:49,710 --> 00:40:55,910 >> E agora eu começo a passar de i é igual a 1 todo o caminho até e incluindo m, 940 00:40:55,910 --> 00:41:00,130 porque eu quero incluir todas as números de um a m, inclusive. 941 00:41:00,130 --> 00:41:04,350 E dentro deste loop for, eu só faço soma recebe o que é agora, mais do 942 00:41:04,350 --> 00:41:08,900 valor de i. 943 00:41:08,900 --> 00:41:10,370 Além disso, o valor de i. 944 00:41:10,370 --> 00:41:14,090 >> Como um aparte, se você não vi isso antes, há um pouco de açúcar sintático 945 00:41:14,090 --> 00:41:14,870 para esta linha. 946 00:41:14,870 --> 00:41:21,120 Eu posso reescrever isso como mais iguais i, só para me salvar algumas teclas 947 00:41:21,120 --> 00:41:22,570 e olhar um pouco mais frio. 948 00:41:22,570 --> 00:41:23,140 Mas isso é tudo. 949 00:41:23,140 --> 00:41:24,660 É funcionalmente a mesma coisa. 950 00:41:24,660 --> 00:41:26,710 >> Infelizmente, este código de não vai compilar ainda. 951 00:41:26,710 --> 00:41:31,600 Se eu executar o make sigma 0, como sou I vai ser gritado? 952 00:41:31,600 --> 00:41:33,473 O que ele está indo para não gostar? 953 00:41:33,473 --> 00:41:35,740 >> AUDIÊNCIA: [inaudível]. 954 00:41:35,740 --> 00:41:37,800 >> DAVID MALAN: Sim, eu não declarar a função em cima, certo? 955 00:41:37,800 --> 00:41:40,590 C é uma espécie de estúpida, só na medida em que faz o que você diga a ele para fazer, e você 956 00:41:40,590 --> 00:41:41,880 tem que fazer isso nessa ordem. 957 00:41:41,880 --> 00:41:45,910 E então se eu pressione Enter aqui, eu vou receber um aviso sobre sigma implícita 958 00:41:45,910 --> 00:41:46,860 declaração. 959 00:41:46,860 --> 00:41:48,120 >> Oh, não é um problema. 960 00:41:48,120 --> 00:41:50,370 Eu posso ir até o topo, e eu posso dizer, tudo bem, espere um minuto. 961 00:41:50,370 --> 00:41:54,240 Sigma é uma função que retorna um int e espera um 962 00:41:54,240 --> 00:41:56,620 int como entrada, ponto e vírgula. 963 00:41:56,620 --> 00:41:59,550 Ou eu poderia colocar toda a função acima principal, mas em geral, eu 964 00:41:59,550 --> 00:42:02,260 recomendo contra isso, porque é bom ter sempre principal no topo de modo 965 00:42:02,260 --> 00:42:06,310 você pode mergulhar na direita e sabe o que é um programa está fazendo lendo principal pela primeira vez. 966 00:42:06,310 --> 00:42:07,930 >> Então, agora deixe-me limpar a tela. 967 00:42:07,930 --> 00:42:09,330 Remake sigma 0. 968 00:42:09,330 --> 00:42:10,340 Tudo parece check-out. 969 00:42:10,340 --> 00:42:11,970 Deixe-me correr sigma 0. 970 00:42:11,970 --> 00:42:12,770 Entre positiva. 971 00:42:12,770 --> 00:42:15,580 Eu vou dar-lhe o número 3 para mantê-lo simples. 972 00:42:15,580 --> 00:42:18,710 De modo que deve me dar 3 mais 2 mais 1, então 6. 973 00:42:18,710 --> 00:42:20,750 Enter, e na verdade eu fico 6. 974 00:42:20,750 --> 00:42:21,820 >> Eu posso fazer algo maior - 975 00:42:21,820 --> 00:42:24,080 50, 12, 75. 976 00:42:24,080 --> 00:42:27,690 Assim como a tangente, eu vou fazer algo ridículo como realmente um grande 977 00:42:27,690 --> 00:42:30,375 número, Oh, que realmente funcionou - 978 00:42:30,375 --> 00:42:31,600 eh, eu não acho que isso é certo. 979 00:42:31,600 --> 00:42:32,810 Vamos ver. 980 00:42:32,810 --> 00:42:34,060 Vamos realmente mexer com ele. 981 00:42:34,060 --> 00:42:37,150 982 00:42:37,150 --> 00:42:38,400 >> Isso é um problema. 983 00:42:38,400 --> 00:42:43,180 984 00:42:43,180 --> 00:42:44,970 O que está acontecendo? 985 00:42:44,970 --> 00:42:46,050 O código não é tão ruim assim. 986 00:42:46,050 --> 00:42:48,470 Ainda é linear. 987 00:42:48,470 --> 00:42:50,810 Assobiar é um bom efeito, apesar de tudo. 988 00:42:50,810 --> 00:42:52,060 O que está acontecendo? 989 00:42:52,060 --> 00:42:54,700 990 00:42:54,700 --> 00:42:55,620 >> Não tenho certeza se ouvi-lo. 991 00:42:55,620 --> 00:42:57,620 Assim, verifica-se - e isto é como um aparte. 992 00:42:57,620 --> 00:42:59,400 Isto não é essencial para o idéia de recursão. 993 00:42:59,400 --> 00:43:02,480 Acontece que, porque eu estou tentando representam um número tão grande, a maioria 994 00:43:02,480 --> 00:43:06,980 provavelmente ele está sendo mal interpretado por C, tal como um número não positivo, 995 00:43:06,980 --> 00:43:09,980 mas número negativo. 996 00:43:09,980 --> 00:43:12,690 >> Nós não falamos sobre isso, mas Acontece que existem números negativos 997 00:43:12,690 --> 00:43:14,210 no mundo para além a números positivos. 998 00:43:14,210 --> 00:43:16,290 E os meios pelos quais você pode representar um número negativo 999 00:43:16,290 --> 00:43:19,530 essencialmente é, você pode usar um bit especial para indicar 1000 00:43:19,530 --> 00:43:20,400 positivo sobre negativo. 1001 00:43:20,400 --> 00:43:22,950 É um pouco mais complexo do que isso, mas essa é a idéia básica. 1002 00:43:22,950 --> 00:43:26,740 >> Então, infelizmente, se C é confuso uma desses bits como de fato o que significa, 1003 00:43:26,740 --> 00:43:30,790 oh, este é um número negativo, o meu laço aqui, por exemplo, é, na verdade nunca 1004 00:43:30,790 --> 00:43:31,740 vai terminar. 1005 00:43:31,740 --> 00:43:33,850 Então, se eu fosse realmente a impressão de algo novo e de novo, faríamos 1006 00:43:33,850 --> 00:43:34,650 ver muita coisa. 1007 00:43:34,650 --> 00:43:36,220 Mas, novamente, isso é além do ponto. 1008 00:43:36,220 --> 00:43:38,590 Isto é realmente apenas uma espécie de curiosidade intelectual que nós viremos 1009 00:43:38,590 --> 00:43:39,550 voltar para eventualmente. 1010 00:43:39,550 --> 00:43:43,400 Mas, por agora, esta é a correta implementação se assumirmos que o 1011 00:43:43,400 --> 00:43:45,970 usuário irá fornecer ints que se encaixam dentro de ints. 1012 00:43:45,970 --> 00:43:49,370 >> Mas eu afirmo que este código, francamente, poderia ser feito muito mais simples. 1013 00:43:49,370 --> 00:43:54,060 Se o objetivo em questão é ter um número como m e somar todas as 1014 00:43:54,060 --> 00:43:59,510 números entre ele e 1, ou, inversamente entre 1 e ele, eu afirmo 1015 00:43:59,510 --> 00:44:03,380 que eu posso pedir essa idéia de que fundem espécie tinha, que estava tomando um problema 1016 00:44:03,380 --> 00:44:05,660 deste tamanho e dividindo-o em algo menor. 1017 00:44:05,660 --> 00:44:09,875 Talvez nem a metade, mas menor, mas representativamente a mesma. 1018 00:44:09,875 --> 00:44:12,130 A mesma idéia, mas um problema menor. 1019 00:44:12,130 --> 00:44:15,470 >> Então, eu estou na verdade - deixe-me salve este arquivo com um número de versão diferente. 1020 00:44:15,470 --> 00:44:17,670 Vamos chamar esta versão 1 em vez de 0. 1021 00:44:17,670 --> 00:44:20,790 E eu afirmo que eu possa realmente reimplementar esta neste tipo de 1022 00:44:20,790 --> 00:44:22,160 alucinante caminho. 1023 00:44:22,160 --> 00:44:23,710 >> Vou deixar parte dela sozinho. 1024 00:44:23,710 --> 00:44:27,710 Eu vou dizer se m é menor que ou mesmo igual a 0 - 1025 00:44:27,710 --> 00:44:29,280 Eu só vou ser um pouco desta vez mais anal 1026 00:44:29,280 --> 00:44:30,520 com a minha verificação de erros - 1027 00:44:30,520 --> 00:44:33,190 Eu estou indo para ir em frente e retornar 0. 1028 00:44:33,190 --> 00:44:34,490 Este é arbitrária. 1029 00:44:34,490 --> 00:44:37,500 Estou simplesmente decidir se o usuário me dá um número negativo, eu sou 1030 00:44:37,500 --> 00:44:41,490 retornando 0, e eles devem ter lido a documentação mais de perto. 1031 00:44:41,490 --> 00:44:42,170 >> Else - 1032 00:44:42,170 --> 00:44:44,070 perceber o que eu vou fazer. 1033 00:44:44,070 --> 00:44:49,260 Mais eu vou voltar m plus - 1034 00:44:49,260 --> 00:44:51,010 o que é de sigma m? 1035 00:44:51,010 --> 00:44:56,710 Bem, sigma de m mais m menos 1, m menos mais dois, além de menos 3 m. 1036 00:44:56,710 --> 00:44:58,030 Eu não quero escrever tudo isso para fora. 1037 00:44:58,030 --> 00:44:59,120 Por que eu não apenas punt? 1038 00:44:59,120 --> 00:45:05,080 Recursively me chamar com um pouco problema menor, ponto e vírgula, 1039 00:45:05,080 --> 00:45:06,840 e chamá-lo um dia? 1040 00:45:06,840 --> 00:45:07,040 >> Certo? 1041 00:45:07,040 --> 00:45:10,980 Agora, aqui, também, que você pode sentir ou se preocupar que este é um loop infinito que eu sou 1042 00:45:10,980 --> 00:45:15,450 induzindo, pelo qual estou implementando sigma chamando sigma. 1043 00:45:15,450 --> 00:45:20,342 Mas isso é perfeitamente normal, porque eu pensou em frente uma acrescentou que falas? 1044 00:45:20,342 --> 00:45:22,600 >> AUDIÊNCIA: [inaudível]. 1045 00:45:22,600 --> 00:45:25,430 >> DAVID MALAN: 23 a 26, que é o meu caso condição. 1046 00:45:25,430 --> 00:45:28,390 Porque o que é bom sobre o subtração aqui, porque eu mantenho 1047 00:45:28,390 --> 00:45:31,180 entregando sigma problemas menores, menor problemas menores - não é 1048 00:45:31,180 --> 00:45:31,870 a metade do tamanho. 1049 00:45:31,870 --> 00:45:34,380 É apenas um pequeno passo menor, mas isso é OK. 1050 00:45:34,380 --> 00:45:38,050 Porque, eventualmente, vamos trabalhar nosso caminho até a 1 ou 0. 1051 00:45:38,050 --> 00:45:41,630 E uma vez que nós batemos 0, sigma não é vai chamar-se mais. 1052 00:45:41,630 --> 00:45:43,590 Vai retornar imediatamente 0. 1053 00:45:43,590 --> 00:45:47,960 >> Assim, o efeito, se este tipo de vento em sua mente, é adicionar mais m 1054 00:45:47,960 --> 00:45:52,740 menos 1 m, mais M menos 2, mais M menos 3, além de ponto, ponto, ponto, m menos 1055 00:45:52,740 --> 00:45:57,820 m, acabou dando-lhe 0, eo efeito é em última análise, para adicionar todos 1056 00:45:57,820 --> 00:45:59,070 essas coisas juntas. 1057 00:45:59,070 --> 00:46:02,380 Então, nós não temos, com recursão, resolveu o problema que 1058 00:46:02,380 --> 00:46:03,470 não poderia resolver antes. 1059 00:46:03,470 --> 00:46:06,840 Com efeito, esta versão de 0, e todo problema até à data, tem sido resolvidas 1060 00:46:06,840 --> 00:46:09,980 com apenas usando loops ou enquanto loops ou construções semelhantes. 1061 00:46:09,980 --> 00:46:13,150 >> Mas recursão, ouso dizer, dá-nos uma maneira diferente de pensar sobre 1062 00:46:13,150 --> 00:46:17,010 problemas, em que se pode tomar um problema, dividi-lo de alguma coisa 1063 00:46:17,010 --> 00:46:22,340 um tanto grande para algo um tanto menor, eu afirmo que nós podemos resolvê-lo 1064 00:46:22,340 --> 00:46:26,040 talvez um pouco mais elegante em termos do design, com menos código, 1065 00:46:26,040 --> 00:46:30,980 e talvez até mesmo resolver problemas que ser mais difícil, à medida que vai finalmente 1066 00:46:30,980 --> 00:46:33,280 ver, a solução puramente iterativa. 1067 00:46:33,280 --> 00:46:35,980 >> Mas o suspense que eu fiz quero deixar-nos no foi isso. 1068 00:46:35,980 --> 00:46:40,720 Deixe-me ir em frente e abrir um arquivo a partir de - 1069 00:46:40,720 --> 00:46:44,300 Na verdade, deixe-me ir e fazer isso muito rápido. 1070 00:46:44,300 --> 00:46:46,875 Deixe-me ir em frente e propor a seguir. 1071 00:46:46,875 --> 00:46:51,160 1072 00:46:51,160 --> 00:46:54,785 Entre o código de hoje é este arquivo aqui. 1073 00:46:54,785 --> 00:47:01,090 1074 00:47:01,090 --> 00:47:03,050 Este aqui, noswap. 1075 00:47:03,050 --> 00:47:06,260 >> Portanto, este é um pequeno programa estúpido que Eu chicoteado até que as reivindicações a fazer 1076 00:47:06,260 --> 00:47:06,940 a seguir. 1077 00:47:06,940 --> 00:47:10,140 Na principal, declara pela primeira vez um int chamado x e atribui a ele 1078 00:47:10,140 --> 00:47:11,100 o valor de 1. 1079 00:47:11,100 --> 00:47:13,520 Em seguida, ele declara um int y e atribui o valor 2. 1080 00:47:13,520 --> 00:47:15,310 Em seguida, ele imprime o que x e y é. 1081 00:47:15,310 --> 00:47:17,781 Em seguida, ele diz, troca, dot dot dot. 1082 00:47:17,781 --> 00:47:21,670 >> Em seguida, ele afirma ser chamada de uma função chamado swap, passando em x e 1083 00:47:21,670 --> 00:47:24,290 y, a idéia de que é que esperamos x e y voltará 1084 00:47:24,290 --> 00:47:25,620 diferente, o oposto. 1085 00:47:25,620 --> 00:47:27,110 Em seguida, ele trocou reclamar! 1086 00:47:27,110 --> 00:47:28,420 com um ponto de exclamação. 1087 00:47:28,420 --> 00:47:30,190 Em seguida, ele imprime x e y. 1088 00:47:30,190 --> 00:47:33,480 >> Mas acontece que essa mesma demonstração simples para baixo 1089 00:47:33,480 --> 00:47:35,570 aqui é realmente buggy. 1090 00:47:35,570 --> 00:47:38,870 Mesmo que eu estou declarando uma temporária variável e, temporariamente, colocando um em 1091 00:47:38,870 --> 00:47:42,010 , então eu estou reafectação um o valor de b - 1092 00:47:42,010 --> 00:47:45,080 que se sente razoável, porque eu tenho salva uma cópia de um de temperatura. 1093 00:47:45,080 --> 00:47:48,410 Então eu atualizar b para igual o que estava na temperatura. 1094 00:47:48,410 --> 00:47:51,610 Este tipo de jogo shell de mover um em b e b em um usando esta 1095 00:47:51,610 --> 00:47:54,360 meio-homem chamado temperatura sente perfeitamente razoável. 1096 00:47:54,360 --> 00:47:57,270 >> Mas eu afirmo que quando eu executar este código, como eu vou fazer agora - 1097 00:47:57,270 --> 00:47:59,490 deixe-me ir em frente e colá-lo aqui. 1098 00:47:59,490 --> 00:48:01,995 Vou chamar esta noswap.c. 1099 00:48:01,995 --> 00:48:05,630 E, como o nome sugere, este não é Vai ser um programa correto. 1100 00:48:05,630 --> 00:48:09,460 Faça noswap. / No swap. 1101 00:48:09,460 --> 00:48:12,110 x é 1, y é 2, troca, trocados. 1102 00:48:12,110 --> 00:48:14,220 x é 1, y é 2. 1103 00:48:14,220 --> 00:48:16,920 Isto é fundamentalmente errado, mesmo embora isto parece perfeitamente 1104 00:48:16,920 --> 00:48:17,730 razoável para mim. 1105 00:48:17,730 --> 00:48:21,330 E há uma razão, mas não estamos vai revelar o motivo ainda. 1106 00:48:21,330 --> 00:48:24,610 >> Por agora, a segunda suspense que eu queria para deixá-lo com isso é, um 1107 00:48:24,610 --> 00:48:27,120 anúncio das sortes sobre os códigos de cupom. 1108 00:48:27,120 --> 00:48:31,590 Nossa inovação com dias de atraso este ano tem provocado um número não-trivial 1109 00:48:31,590 --> 00:48:33,830 de perguntas, o que foi não a nossa intenção. 1110 00:48:33,830 --> 00:48:36,590 A intenção destes códigos de cupom, em que, se você fizer parte do problema 1111 00:48:36,590 --> 00:48:39,850 definir cedo, obtendo assim um dia extra, Foi realmente para ajudar vocês ajudam 1112 00:48:39,850 --> 00:48:42,420 se começar cedo, tipo de por incentivar você. 1113 00:48:42,420 --> 00:48:44,880 Nos ajuda a distribuir a carga em toda o horário de expediente, para que melhor 1114 00:48:44,880 --> 00:48:45,740 é uma espécie de ganha-ganha. 1115 00:48:45,740 --> 00:48:48,860 >> Infelizmente, acho que as minhas instruções não ter sido, até à data, muito clara, de modo 1116 00:48:48,860 --> 00:48:52,230 Voltei esta semana e atualizada a especificação no maior, mais ousado texto para 1117 00:48:52,230 --> 00:48:53,600 explicar balas como estas. 1118 00:48:53,600 --> 00:48:56,900 E só para dizer isso mais publicamente, por padrão, conjuntos de problemas são devidos quinta-feira 1119 00:48:56,900 --> 00:48:58,400 ao meio-dia, conforme o programa. 1120 00:48:58,400 --> 00:49:02,030 Se você começar cedo, terminando em parte de o problema de definir até quarta-feira às 12:00 1121 00:49:02,030 --> 00:49:05,170 PM, a parte que se relaciona com um cupão código, a idéia é que você pode estender 1122 00:49:05,170 --> 00:49:07,710 o prazo para a P definido até sexta-feira. 1123 00:49:07,710 --> 00:49:10,890 Ou seja, pouco fora uma pequena parte do P definido em relação ao que normalmente é o 1124 00:49:10,890 --> 00:49:13,200 maior problema, e você compra se um dia extra. 1125 00:49:13,200 --> 00:49:15,190 Mais uma vez, você fica pensando o conjunto de problemas, faz com que você 1126 00:49:15,190 --> 00:49:16,380 o expediente mais cedo. 1127 00:49:16,380 --> 00:49:20,670 Mas o problema ainda é o código de cupom obrigados, mesmo se você não enviá-lo. 1128 00:49:20,670 --> 00:49:23,340 >> Mas o mais convincente é este. 1129 00:49:23,340 --> 00:49:26,520 (Sussurro) E essas pessoas deixando cedo vão se arrepender. 1130 00:49:26,520 --> 00:49:28,620 Como são as pessoas na varanda. 1131 00:49:28,620 --> 00:49:32,510 Peço desculpas antecipadamente para as pessoas em a varanda, por razões que serão 1132 00:49:32,510 --> 00:49:33,920 claro em apenas um momento. 1133 00:49:33,920 --> 00:49:37,050 >> Então, temos a sorte de ter um dos Ex-chefe companheiros de ensino do CS50 em 1134 00:49:37,050 --> 00:49:39,302 uma empresa chamada dropbox.com. 1135 00:49:39,302 --> 00:49:45,500 Eles têm muito generosamente doou um código de cupom aqui para isso muito espaço, 1136 00:49:45,500 --> 00:49:48,180 que é a partir do usuais 2 gigabytes. 1137 00:49:48,180 --> 00:49:51,740 Então o que eu pensei que iria fazer nesta nota final é fazer um pouco de uma oferta, 1138 00:49:51,740 --> 00:49:55,380 pelo qual, em apenas um momento, vamos revelar o vencedor e que tem um cupão 1139 00:49:55,380 --> 00:49:57,980 código que você pode, então, ir ao seu site, digite-a, e voila, obter um 1140 00:49:57,980 --> 00:50:01,370 muito mais espaço para o seu Dropbox aparelho e para seus arquivos pessoais. 1141 00:50:01,370 --> 00:50:05,690 >> E em primeiro lugar, que gostaria de participar neste desenho? 1142 00:50:05,690 --> 00:50:09,630 OK, agora que o torna ainda mais divertido. 1143 00:50:09,630 --> 00:50:14,010 A pessoa que recebe este 25 gigabytes código do cupom - o que está longe 1144 00:50:14,010 --> 00:50:16,150 mais atraente do que o falecido dias de hoje, talvez - 1145 00:50:16,150 --> 00:50:20,620 é aquele que está sentado em cima de um assento do banco sob a qual existe 1146 00:50:20,620 --> 00:50:21,620 que o código do cupom. 1147 00:50:21,620 --> 00:50:23,480 Agora você pode olhar por baixo seu assento. 1148 00:50:23,480 --> 00:50:28,710 1149 00:50:28,710 --> 00:50:29,680 >> [REPRODUÇÃO] 1150 00:50:29,680 --> 00:50:31,620 >> -Um, dois, três. 1151 00:50:31,620 --> 00:50:35,015 >> [GRITANDO] 1152 00:50:35,015 --> 00:50:35,985 >> -Você ganha um carro! 1153 00:50:35,985 --> 00:50:36,670 Você ganha um carro! 1154 00:50:36,670 --> 00:50:37,970 >> DAVID MALAN: Veremos você na quarta-feira. 1155 00:50:37,970 --> 00:50:38,904 >> -Você ganha um carro! 1156 00:50:38,904 --> 00:50:39,371 Você ganha um carro! 1157 00:50:39,371 --> 00:50:40,305 Você ganha um carro! 1158 00:50:40,305 --> 00:50:41,706 Você ganha um carro! 1159 00:50:41,706 --> 00:50:43,107 Você ganha um carro! 1160 00:50:43,107 --> 00:50:45,530 >> DAVID MALAN: pessoas Varanda, vêm aqui em baixo para a frente, 1161 00:50:45,530 --> 00:50:46,866 onde temos extras. 1162 00:50:46,866 --> 00:50:50,282 >> -Todo mundo tem um carro! 1163 00:50:50,282 --> 00:50:52,234 Todo mundo fica um carro! 1164 00:50:52,234 --> 00:50:52,722 >> [FIM REPRODUÇÃO DE VÍDEO] 1165 00:50:52,722 --> 00:50:54,590 >> Narrador: Na próxima CS50 - 1166 00:50:54,590 --> 00:51:00,374 >> COLUNA 5: Oh meu Deus caramba caramba caramba caramba caramba caramba caramba caramba caramba - 1167 00:51:00,374 --> 00:51:02,106 >> [JOGOS ukelele]