1 00:00:00,000 --> 00:00:11,100 >> [Música tocando] 2 00:00:11,100 --> 00:00:11,490 >> DAVID J. MALAN: Tudo bem. 3 00:00:11,490 --> 00:00:12,170 Então bem-vindo de volta. 4 00:00:12,170 --> 00:00:15,180 Isto é CS50, e é o o final de semana três. 5 00:00:15,180 --> 00:00:17,770 >> Então, lembro nas últimas semanas, estamos gastando um pouco de 6 00:00:17,770 --> 00:00:20,820 tempo em C, em programação, em sintaxe. 7 00:00:20,820 --> 00:00:24,680 E é muito normal, se você ainda estiver lutando com o Conjunto de Problemas 2, para ser 8 00:00:24,680 --> 00:00:25,950 bater sua cabeça contra a parede. 9 00:00:25,950 --> 00:00:28,310 É mensagens de erro enigmáticas para o futuro e os erros que você 10 00:00:28,310 --> 00:00:29,220 não consegue perseguir. 11 00:00:29,220 --> 00:00:32,310 Porque, pode ter certeza, que em apenas um tempo de algumas semanas você vai olhar para trás 12 00:00:32,310 --> 00:00:35,930 coisas como César, e [? V-genair,?] talvez até de crack, e 13 00:00:35,930 --> 00:00:40,050 perceber o quão longe você chegou num curto período de tempo. 14 00:00:40,050 --> 00:00:43,670 Então, se isso serve de consolo, pendurar lá por enquanto. 15 00:00:43,670 --> 00:00:46,610 >> Hoje, porém, começamos a transição para coisas de mais alto nível. 16 00:00:46,610 --> 00:00:49,820 E começamos a dar como certo que Vocês sabem como programar, ou pelo 17 00:00:49,820 --> 00:00:52,090 menos o início de que o nível de conforto. 18 00:00:52,090 --> 00:00:56,520 E vamos começar a considerar como podemos ir sobre a criação de programas mais 19 00:00:56,520 --> 00:00:57,440 eficazmente. 20 00:00:57,440 --> 00:01:01,090 Como podemos ir sobre como otimizar o eficiência dos algoritmos e 21 00:01:01,090 --> 00:01:03,110 geralmente a solução mais problemas interessantes. 22 00:01:03,110 --> 00:01:06,850 E começando a tomar por certo que, se quiséssemos, poderíamos codificar qualquer 23 00:01:06,850 --> 00:01:08,350 dos exemplos que temos em mente. 24 00:01:08,350 --> 00:01:11,430 Então, hoje, nós não tocar o teclado para qualquer forma de código. 25 00:01:11,430 --> 00:01:15,150 Vai ser nível muito mais elevado, e em última instância, sobre a resolução de problemas. 26 00:01:15,150 --> 00:01:20,490 >> Então, para chegar a esse ponto, deixe-me propor que os seguintes sete 27 00:01:20,490 --> 00:01:24,290 retângulos representam sete portas, atrás que são um monte de 28 00:01:24,290 --> 00:01:26,340 números, entre os quais está o número 50. 29 00:01:26,340 --> 00:01:30,470 Deixe-me projetar esta neste tela aqui também. 30 00:01:30,470 --> 00:01:36,770 E propor que precisamos de um voluntário para me ajudar a encontrar um número na frente 31 00:01:36,770 --> 00:01:38,140 a internet aqui para ver. 32 00:01:38,140 --> 00:01:40,755 Vamos para cima, na cor rosa. 33 00:01:40,755 --> 00:01:43,050 Tudo bem. 34 00:01:43,050 --> 00:01:43,930 Qual é o seu nome? 35 00:01:43,930 --> 00:01:44,850 >> JENNIFER: [inaudível] 36 00:01:44,850 --> 00:01:45,170 >> DAVID J. MALAN: Desculpe? 37 00:01:45,170 --> 00:01:45,860 >> JENNIFER: Jennifer. 38 00:01:45,860 --> 00:01:46,390 >> DAVID J. MALAN: Jennifer. 39 00:01:46,390 --> 00:01:46,980 Tudo bem, Jennifer. 40 00:01:46,980 --> 00:01:47,630 Prazer em conhecê lo. 41 00:01:47,630 --> 00:01:48,370 Vamos para cima. 42 00:01:48,370 --> 00:01:52,430 Então, esses aqui são sete portas, eo que Gostaria de fazer para nós aqui, 43 00:01:52,430 --> 00:01:56,560 na frente de todos os seus colegas, é encontrar-nos o número, 50. 44 00:01:56,560 --> 00:02:00,860 Para encontrar um número, você pode espreitar atrás qualquer destas portas simplesmente tocando 45 00:02:00,860 --> 00:02:03,030 em uma das portas, e irá revelar o seu número. 46 00:02:03,030 --> 00:02:06,080 E vamos ver o quão rápido você pode encontrar-nos o número, 50. 47 00:02:06,080 --> 00:02:09,979 48 00:02:09,979 --> 00:02:11,229 >> 15. 49 00:02:11,229 --> 00:02:13,110 50 00:02:13,110 --> 00:02:14,360 16. 51 00:02:14,360 --> 00:02:16,270 52 00:02:16,270 --> 00:02:16,530 50. 53 00:02:16,530 --> 00:02:17,350 Bem feito. 54 00:02:17,350 --> 00:02:18,040 Tudo bem. 55 00:02:18,040 --> 00:02:19,906 Salva de palmas para Jennifer. 56 00:02:19,906 --> 00:02:21,530 >> [Aplausos] 57 00:02:21,530 --> 00:02:22,320 >> Tudo bem. 58 00:02:22,320 --> 00:02:25,254 Então, qual foi a sua estratégia para encontrar o número, a 50? 59 00:02:25,254 --> 00:02:27,222 >> JENNIFER: Hum, eu pensei que talvez se - 60 00:02:27,222 --> 00:02:27,714 [Inaudível] 61 00:02:27,714 --> 00:02:28,206 >> DAVID J. MALAN: Oh. 62 00:02:28,206 --> 00:02:29,630 Dê-lhe um segundo. 63 00:02:29,630 --> 00:02:32,420 Assim foi a sua estratégia para encontrar o número, a 50? 64 00:02:32,420 --> 00:02:34,760 >> JENNIFER: Então, eu só começar no começando a ver que o primeiro número 65 00:02:34,760 --> 00:02:38,590 era, e então eu pensei, talvez se eles estão classificadas, vou continuar 66 00:02:38,590 --> 00:02:39,970 tocando mais alto? 67 00:02:39,970 --> 00:02:40,140 >> DAVID J. MALAN: OK. 68 00:02:40,140 --> 00:02:42,910 E nós parecem ter encontrado que seja esse o caso. 69 00:02:42,910 --> 00:02:45,670 Embora, vamos descascar as camadas apenas um pouco, e você quer ir 70 00:02:45,670 --> 00:02:47,640 frente e revelar as outras portas você poderia ter escolhido? 71 00:02:47,640 --> 00:02:50,400 72 00:02:50,400 --> 00:02:51,712 >> JENNIFER: Oh, querida. 73 00:02:51,712 --> 00:02:53,128 >> DAVID J. MALAN: Ah. 74 00:02:53,128 --> 00:02:54,280 >> JENNIFER: Então eu só tenho sorte. 75 00:02:54,280 --> 00:02:55,270 >> DAVID J. MALAN: Então você teve sorte. 76 00:02:55,270 --> 00:02:55,710 Tudo bem. 77 00:02:55,710 --> 00:02:56,795 Então, não é mau. 78 00:02:56,795 --> 00:02:58,750 Mas isso é um interessante insight, certo? 79 00:02:58,750 --> 00:03:01,870 Se você assumiu, e você conseguiu, na verdade, um pouco de sorte lá. 80 00:03:01,870 --> 00:03:05,350 Mas se do princípio de que os números eram classificadas, você pode ser mais preciso 81 00:03:05,350 --> 00:03:08,750 de como isso influenciado seu comportamento? 82 00:03:08,750 --> 00:03:11,715 >> JENNIFER: Então, se eles foram ordenados, eu pensei que talvez menor para o maior. 83 00:03:11,715 --> 00:03:11,970 >> DAVID J. MALAN: OK. 84 00:03:11,970 --> 00:03:15,260 >> JENNIFER: Ou se isso acabou sendo realmente grande, então maior para o menor. 85 00:03:15,260 --> 00:03:15,540 >> DAVID J. MALAN: OK. 86 00:03:15,540 --> 00:03:18,170 Então maior para o menor, ou menor para o maior. 87 00:03:18,170 --> 00:03:21,990 Mas deixe-me propor, suponha que você tinha obtido de azar, e supor que eles 88 00:03:21,990 --> 00:03:26,840 não foram, de fato, classificado, quantos aquelas portas que você poderia ter tido para espiar 89 00:03:26,840 --> 00:03:28,590 trás em que o pior caso? 90 00:03:28,590 --> 00:03:29,860 >> JENNIFER: Todos eles. 91 00:03:29,860 --> 00:03:30,420 >> David J. MALAN: Todos eles. 92 00:03:30,420 --> 00:03:31,740 Então vamos generalizar que, como n. 93 00:03:31,740 --> 00:03:34,790 Não passa a ser 7, mas vamos mais geralmente dizem que há n portas no 94 00:03:34,790 --> 00:03:35,650 tela aqui. 95 00:03:35,650 --> 00:03:40,110 Assim, no pior caso, você teria que para olhar para trás sete portas, ou n portas. 96 00:03:40,110 --> 00:03:44,140 E assim, este realmente é, é um pouco de sorte hoje, mas é realmente um linear 97 00:03:44,140 --> 00:03:46,440 algoritmo do tipo, mesmo que você eram uma espécie de pular ao redor. 98 00:03:46,440 --> 00:03:47,080 Isso é justo? 99 00:03:47,080 --> 00:03:47,500 >> JENNIFER: Yeah. 100 00:03:47,500 --> 00:03:50,000 >> DAVID J. MALAN: Bem, deixe-me ver se o seu mudanças de estratégia, se eu nos movem 101 00:03:50,000 --> 00:03:52,190 nosso segundo exemplo aqui com 7 portas diferentes. 102 00:03:52,190 --> 00:03:55,240 Os mesmos números, mas esta vez que eles são classificados. 103 00:03:55,240 --> 00:03:58,350 Qual é a sua estratégia aqui vai ser, tentando apagar de sua mente o que 104 00:03:58,350 --> 00:03:59,310 os outros números foram - 105 00:03:59,310 --> 00:03:59,930 >> JENNIFER: OK. 106 00:03:59,930 --> 00:04:02,290 >> DAVID J. MALAN - mais cedo? 107 00:04:02,290 --> 00:04:03,180 >> JENNIFER: Vamos começar com o primeiro. 108 00:04:03,180 --> 00:04:03,540 >> DAVID J. MALAN: Tudo bem. 109 00:04:03,540 --> 00:04:05,190 Comece com o primeiro. 110 00:04:05,190 --> 00:04:05,960 4. 111 00:04:05,960 --> 00:04:08,810 Agora, onde você vai passar, e por quê? 112 00:04:08,810 --> 00:04:10,040 >> JENNIFER: 4 é muito pequeno. 113 00:04:10,040 --> 00:04:12,500 Então, se eles são uma espécie talvez menor a maior, que deveria 114 00:04:12,500 --> 00:04:13,290 ser o dobro, e -. 115 00:04:13,290 --> 00:04:13,670 >> DAVID J. MALAN: OK. 116 00:04:13,670 --> 00:04:15,990 Vamos ver, o que você acha? 117 00:04:15,990 --> 00:04:19,050 >> JENNIFER: Experimente a última. 118 00:04:19,050 --> 00:04:19,500 Nice. 119 00:04:19,500 --> 00:04:20,880 >> DAVID J. MALAN: Muito bem feito. 120 00:04:20,880 --> 00:04:21,860 Tudo bem. 121 00:04:21,860 --> 00:04:23,010 >> [Aplausos] 122 00:04:23,010 --> 00:04:24,310 >> DAVID J. MALAN: OK. 123 00:04:24,310 --> 00:04:26,790 Então, na verdade você está fazendo isso horrivelmente, porque você é 124 00:04:26,790 --> 00:04:27,700 fazê-lo muito bem. 125 00:04:27,700 --> 00:04:31,150 O que nos deixa incapaz de fazer determinados pontos. 126 00:04:31,150 --> 00:04:32,565 Então, vamos tentar reverter aqui. 127 00:04:32,565 --> 00:04:34,560 >> JENNIFER: OK. 128 00:04:34,560 --> 00:04:35,980 >> DAVID J. MALAN: Muito bem feito, no entanto. 129 00:04:35,980 --> 00:04:39,060 Então você começou no início, você viu que ele tinha 4 anos, então você 130 00:04:39,060 --> 00:04:40,240 deslocada para o final. 131 00:04:40,240 --> 00:04:42,320 Mas suponha que você não tem sorte lá, e suponho que 50 132 00:04:42,320 --> 00:04:42,890 estava em outro lugar. 133 00:04:42,890 --> 00:04:46,190 Qual a sua terceira etapa ter sido? 134 00:04:46,190 --> 00:04:47,680 >> JENNIFER: Volte para o começo. 135 00:04:47,680 --> 00:04:48,320 >> DAVID J. MALAN: Volte para o início. 136 00:04:48,320 --> 00:04:51,320 OK, então você teria tocado esta porta, o qual foi de 8. 137 00:04:51,320 --> 00:04:51,660 Tudo bem. 138 00:04:51,660 --> 00:04:52,650 Então, isso não é 50. 139 00:04:52,650 --> 00:04:55,380 Onde é que você olhou ao lado? 140 00:04:55,380 --> 00:04:56,720 >> JENNIFER: Se eu não fiz sabem que classificados. 141 00:04:56,720 --> 00:04:57,005 >> DAVID J. MALAN: Correto. 142 00:04:57,005 --> 00:04:58,490 Bem, se você soubesse foram classificadas - 143 00:04:58,490 --> 00:04:58,700 >> JENNIFER: Ah, sabia, sim. 144 00:04:58,700 --> 00:05:00,910 >> DAVID J. MALAN: - mas você não fez sabe onde 50 foi ainda? 145 00:05:00,910 --> 00:05:01,785 >> JENNIFER: Apenas continuar. 146 00:05:01,785 --> 00:05:02,130 >> DAVID J. MALAN: Tudo bem. 147 00:05:02,130 --> 00:05:02,520 OK. 148 00:05:02,520 --> 00:05:03,800 Continue indo. 149 00:05:03,800 --> 00:05:05,270 OK, para que eu possa trabalhar. 150 00:05:05,270 --> 00:05:05,610 >> JENNIFER: OK. 151 00:05:05,610 --> 00:05:07,210 >> DAVID J. MALAN: Agora, se você está apenas vai continuar, o que é seu 152 00:05:07,210 --> 00:05:09,680 algoritmo que recaem apoiada em. 153 00:05:09,680 --> 00:05:10,740 >> JENNIFER: o linear -. 154 00:05:10,740 --> 00:05:11,820 >> DAVID J. MALAN: É uma espécie de linear. 155 00:05:11,820 --> 00:05:13,480 Mas deixe-me propor, vamos me colocar no local. 156 00:05:13,480 --> 00:05:14,900 Deixe-me atualizar a página. 157 00:05:14,900 --> 00:05:17,120 mesmo número, o mesmo arranjo, mesmas portas. 158 00:05:17,120 --> 00:05:21,350 Mas acho que voltar para aquele primeiro dia em classe quando rasgou um livro de telefone em 159 00:05:21,350 --> 00:05:25,480 metade, mais ou menos, eo que era nossa estratégia lá? 160 00:05:25,480 --> 00:05:26,450 >> JENNIFER: Comece pelo meio. 161 00:05:26,450 --> 00:05:26,690 >> DAVID J. MALAN: OK. 162 00:05:26,690 --> 00:05:27,610 Portanto, comece no meio. 163 00:05:27,610 --> 00:05:28,790 Então, vamos em frente e simular isso. 164 00:05:28,790 --> 00:05:30,720 Comece pelo meio por revelando que porta. 165 00:05:30,720 --> 00:05:31,660 Portanto, o número 16. 166 00:05:31,660 --> 00:05:35,290 Então, o que o cara forte fizeram, que rasgou o livro de telefone pela metade, 167 00:05:35,290 --> 00:05:38,450 para chegar ao próximo palpite? 168 00:05:38,450 --> 00:05:39,400 >> JENNIFER: Vá no semestre. 169 00:05:39,400 --> 00:05:41,700 >> DAVID J. MALAN: E porque para a direita? 170 00:05:41,700 --> 00:05:43,900 >> JENNIFER: Se eles eram uma espécie de menor para o maior, então deve ser 50 171 00:05:43,900 --> 00:05:44,720 nessa extremidade. 172 00:05:44,720 --> 00:05:44,920 >> DAVID J. MALAN: Ótimo. 173 00:05:44,920 --> 00:05:45,390 Totalmente razoável. 174 00:05:45,390 --> 00:05:48,380 Assim como um livro de telefone, você vai para o direita, por oposição à esquerda, mas aqui 175 00:05:48,380 --> 00:05:49,500 é o principal argumento. 176 00:05:49,500 --> 00:05:53,930 Agora você pode jogar fora, ou arrancar, semestre deste problema, deixando-o não 177 00:05:53,930 --> 00:05:55,970 com 7 portas, mas realmente com apenas 3. 178 00:05:55,970 --> 00:05:57,870 Que é cerca de metade da dimensão do problema. 179 00:05:57,870 --> 00:05:58,350 Tudo bem. 180 00:05:58,350 --> 00:06:01,890 Portanto, agora que você teria feito depois que você vai para a direita? 181 00:06:01,890 --> 00:06:05,870 >> JENNIFER: So 16 ainda é muito pequeno, em relação a 50, talvez por isso eu vou tentar, 182 00:06:05,870 --> 00:06:06,700 como, um presente. 183 00:06:06,700 --> 00:06:07,890 >> DAVID J. MALAN: Tudo bem. 184 00:06:07,890 --> 00:06:08,720 42. 185 00:06:08,720 --> 00:06:10,830 Tudo bem, então agora o que é seu instinto dizendo a você? 186 00:06:10,830 --> 00:06:12,100 >> JENNIFER: Eu posso jogar fora isso e, em seguida, apenas - 187 00:06:12,100 --> 00:06:12,360 >> DAVID J. MALAN: OK. 188 00:06:12,360 --> 00:06:14,212 Bom, você pode jogar fora a metade esquerda lá. 189 00:06:14,212 --> 00:06:14,890 >> JENNIFER: - escolher um. 190 00:06:14,890 --> 00:06:15,530 >> DAVID J. MALAN: E a direita. 191 00:06:15,530 --> 00:06:15,760 >> JENNIFER: Yeah. 192 00:06:15,760 --> 00:06:17,820 >> DAVID J. MALAN: Então, mesmo que seja difícil ver talvez, quando há apenas 193 00:06:17,820 --> 00:06:21,320 Sete portas, pensar, agora, a consistência do 194 00:06:21,320 --> 00:06:22,620 algoritmo que você acabou de aplicar. 195 00:06:22,620 --> 00:06:24,510 No caso anterior, o que fez ter sorte, o que foi ótimo. 196 00:06:24,510 --> 00:06:26,540 Mas você fez usar uma heurística, Eu diria. 197 00:06:26,540 --> 00:06:29,150 Você usou uma espécie de seus instintos, e saber ordenado, se é muito 198 00:06:29,150 --> 00:06:31,600 pequena no início, obviamente, temos tem que ir mais para a direita. 199 00:06:31,600 --> 00:06:34,990 Mas, em certo sentido, você tem sorte, porque talvez este foi o número 100, 200 00:06:34,990 --> 00:06:36,220 e talvez 50 foi mais no meio. 201 00:06:36,220 --> 00:06:37,910 Talvez 50 fosse o mesmo por aqui. 202 00:06:37,910 --> 00:06:40,960 >> Mas o que você fez um pouco diferente desta vez foi, você fez a mesma coisa 203 00:06:40,960 --> 00:06:42,150 uma e outra vez. 204 00:06:42,150 --> 00:06:45,310 E eu diria que o que você acabou se, ainda influenciado pelo telefone 205 00:06:45,310 --> 00:06:48,100 livro exemplo, é algo muito mais algorítmica, e muito 206 00:06:48,100 --> 00:06:49,930 menos especial encaixotado. 207 00:06:49,930 --> 00:06:51,620 Muito menos instintivo. 208 00:06:51,620 --> 00:06:57,160 Assim, no final do dia, como seria que descreve a eficácia do 209 00:06:57,160 --> 00:07:00,530 primeiro algoritmo, onde você foi esquerda para a direita, contra o 210 00:07:00,530 --> 00:07:03,430 segundo algoritmo aqui? 211 00:07:03,430 --> 00:07:06,460 >> JENNIFER: Isso deve-se, como, talvez reduzir pela metade o tempo, ou até mais, sim. 212 00:07:06,460 --> 00:07:07,320 >> DAVID J. MALAN: OK, talvez até mais. 213 00:07:07,320 --> 00:07:10,150 Vamos empurrar um pouco mais sobre isso. 214 00:07:10,150 --> 00:07:13,030 O que realmente, se continuar esta lógica, nós definitivamente reduziu pela metade o 215 00:07:13,030 --> 00:07:15,830 tempo de corrida com este segundo algoritmo jogando fora metade do 216 00:07:15,830 --> 00:07:18,470 números, mas o que vamos fazer no próximo iteração, quando Jennifer revelou 217 00:07:18,470 --> 00:07:20,615 o segundo número? 218 00:07:20,615 --> 00:07:22,830 >> Nós para metade o número de portas novamente. 219 00:07:22,830 --> 00:07:25,270 E então o que fizemos após o que, se havia mais portas para brincar? 220 00:07:25,270 --> 00:07:27,520 Gostaríamos de metade deles, e mais uma vez, e de novo, e de novo. 221 00:07:27,520 --> 00:07:30,420 E isso era exatamente como vocês todos pé na primeira semana de 222 00:07:30,420 --> 00:07:33,000 classe, metade do que você sentar-se, metade de você sentar, metade de vocês 223 00:07:33,000 --> 00:07:35,440 sentar-se, até que um solitário alma estava de pé. 224 00:07:35,440 --> 00:07:39,050 E nós dissemos que o tempo de execução isso, o número de passos Bastou 225 00:07:39,050 --> 00:07:40,430 na ordem de quê? 226 00:07:40,430 --> 00:07:41,230 >> COLUNA 1: [inaudível] 227 00:07:41,230 --> 00:07:43,970 >> DAVID J. MALAN: Então log base 2 de n, ou apenas mais simples, faça o login do n. 228 00:07:43,970 --> 00:07:45,060 Portanto, algo logarítmica. 229 00:07:45,060 --> 00:07:48,380 E o gráfico não é uma linha reta que ficou pior e pior, foi 230 00:07:48,380 --> 00:07:52,490 interessante que esta curva não fez ficar tão ruim ao longo do tempo. 231 00:07:52,490 --> 00:07:53,910 Então, vamos segurar essa idéia. 232 00:07:53,910 --> 00:07:54,690 Vamos agradecer a Jennifer. 233 00:07:54,690 --> 00:07:56,150 Muito obrigado por terem vindo em cima. 234 00:07:56,150 --> 00:07:57,400 E, um segundo. 235 00:07:57,400 --> 00:08:00,170 236 00:08:00,170 --> 00:08:02,925 Não há mesa lâmpadas hoje, mas nós tem CS50 bolas de stress. 237 00:08:02,925 --> 00:08:03,420 >> JENNIFER: Yay. 238 00:08:03,420 --> 00:08:04,410 >> DAVID J. MALAN: Tudo bem, aqui. 239 00:08:04,410 --> 00:08:06,545 Obrigado por incorrer o stress aqui. 240 00:08:06,545 --> 00:08:07,350 Tudo bem. 241 00:08:07,350 --> 00:08:10,620 Então, vamos ver se não podemos agora formalizar esta um pouco mais. 242 00:08:10,620 --> 00:08:14,820 Então, novamente, o que nós fizemos foi essencialmente a mesma coisa que nós fizemos 243 00:08:14,820 --> 00:08:16,660 em que a primeira semana. 244 00:08:16,660 --> 00:08:23,780 Mas ao invés de final com apenas um linear algoritmo, que representado 245 00:08:23,780 --> 00:08:27,210 anteriormente como essa linha reta, pelo que, se colocarmos mais uma porta 246 00:08:27,210 --> 00:08:29,610 tela, em seguida, Jennifer teria tiveram que olhar, potencialmente, 247 00:08:29,610 --> 00:08:30,600 por trás de mais uma porta. 248 00:08:30,600 --> 00:08:33,490 Se colocarmos mais duas portas, ela pode ter para olhar para trás mais duas portas. 249 00:08:33,490 --> 00:08:35,990 >> E assim, houve essa linear relação entre o tamanho da 250 00:08:35,990 --> 00:08:39,059 problema em, por exemplo, o eixo x, e a quantidade de tempo que demora a 251 00:08:39,059 --> 00:08:40,440 resolver na y. 252 00:08:40,440 --> 00:08:43,330 Mas a imagem que eu estava aludindo anterior era esta linha verde. 253 00:08:43,330 --> 00:08:45,970 Verde deliberadamente, porque ele só me senti melhor. 254 00:08:45,970 --> 00:08:49,790 Em teoria, o algoritmo, quando fizemos com o livro de telefone, quando fizemos 255 00:08:49,790 --> 00:08:52,420 com vocês contando uns aos outros, e no segundo caso, quando apenas Jennifer 256 00:08:52,420 --> 00:08:55,250 fiz isso aqui em cima, que era uma espécie de fundamentalmente melhor. 257 00:08:55,250 --> 00:08:57,180 Porque não foi apenas duas vezes mais rápido. 258 00:08:57,180 --> 00:08:58,870 Não era até quatro vezes mais rápido. 259 00:08:58,870 --> 00:09:03,290 Foi totalmente dependente do que a tamanho da entrada foi, de quantas 260 00:09:03,290 --> 00:09:05,220 passos que finalmente levou. 261 00:09:05,220 --> 00:09:08,040 >> E assim esta ideia simples que todos nós tomamos adquirido com o livro de telefone, 262 00:09:08,040 --> 00:09:10,200 semelhante pode ser aplicado para algo como isto. 263 00:09:10,200 --> 00:09:12,380 E isso pode ser mais informal conhecida como, como você pode 264 00:09:12,380 --> 00:09:13,940 imaginar, dividir e conquistar. 265 00:09:13,940 --> 00:09:16,390 Não ao contrário do que fizemos, é claro, com o livro de telefone. 266 00:09:16,390 --> 00:09:18,300 >> Mas o pseudocódigo, aviso, foi isso. 267 00:09:18,300 --> 00:09:21,800 Portanto, não vamos fazer isso de novo, mas recordar essa primeira semana, todos nós se levantou 268 00:09:21,800 --> 00:09:25,140 e, em seguida, metade do que você sentou-se, metade dos você sentou-se, metade do que você sentou-se. 269 00:09:25,140 --> 00:09:29,280 Esse algoritmo foi implementado em um pouco de uma forma de trapaça, em que, ele 270 00:09:29,280 --> 00:09:32,870 Não foi apenas uma das me contando, fundamentalmente, de forma mais eficiente. 271 00:09:32,870 --> 00:09:35,830 Nesse caso, eu estava alavancando um recurso secundário. 272 00:09:35,830 --> 00:09:39,470 Mais ou menos, CPUs múltiplo, cérebros, várias pessoas inteligentes no 273 00:09:39,470 --> 00:09:42,740 sala estavam me ajudando a começar a partir de algo linear para algo 274 00:09:42,740 --> 00:09:45,190 logarítmica, de algo vermelho para algo verde. 275 00:09:45,190 --> 00:09:48,650 >> Mas, neste caso, Jennifer sozinho pode fundamentalmente melhorar a 276 00:09:48,650 --> 00:09:52,370 desempenho de seu primeiro algoritmo, mais uma vez, só de pensar um pouco mais. 277 00:09:52,370 --> 00:09:56,650 E agora, quando chega a hora de implementar essas coisas, descobrir 278 00:09:56,650 --> 00:10:00,670 que as linhas de código que você pode escrever como que você pode repeti-los novamente, e 279 00:10:00,670 --> 00:10:03,350 novamente, e novamente, uma espécie de em uma forma de looping. 280 00:10:03,350 --> 00:10:06,370 Porque você não vai ter a luxo, como Jennifer fez num primeiro momento, a 281 00:10:06,370 --> 00:10:10,460 só tem um monte de ifs e dizer: hmm, se este primeiro número é 4, 282 00:10:10,460 --> 00:10:11,800 deixe-me saltar todo o caminho até o fim. 283 00:10:11,800 --> 00:10:14,180 Ooh, se esse número é muito grande, deixe-me passar para trás de forma arbitrária 284 00:10:14,180 --> 00:10:15,220 ao segundo elemento. 285 00:10:15,220 --> 00:10:18,210 Você verá que ele vai ser muito mais difícil de formalizar o que nós, seres humanos 286 00:10:18,210 --> 00:10:21,270 tomar para concedido como muito razoável heurística, mas um computador é apenas 287 00:10:21,270 --> 00:10:23,260 vai fazer o que você diga a ele para fazer. 288 00:10:23,260 --> 00:10:25,280 >> Agora, isso tem muito interessante implicações. 289 00:10:25,280 --> 00:10:29,950 Este gráfico é uma espécie de significado para classificar de sobrecarregar visualmente, mas o aviso prévio, onde 290 00:10:29,950 --> 00:10:32,230 é a reta neste gráfico? 291 00:10:32,230 --> 00:10:35,330 Onde está o gráfico linear que chamamos de n? 292 00:10:35,330 --> 00:10:37,580 Bem, é uma espécie de para o fundo da imagem, certo? 293 00:10:37,580 --> 00:10:40,500 Então, tudo o que fizemos é que tenho a sorte de zoom out para o eixo x eo 294 00:10:40,500 --> 00:10:44,780 eixo-y para tentar obter uma noção do que outros tipos de curvas parecem. 295 00:10:44,780 --> 00:10:47,760 >> E as especificidades da matemática expressões, hoje, não importa para 296 00:10:47,760 --> 00:10:52,440 muito, mas perceber que há uma grande quantidade de algoritmos que são muito piores do que 297 00:10:52,440 --> 00:10:53,470 algo que é linear. 298 00:10:53,470 --> 00:10:55,410 Na verdade, n cubos parece muito ruim. 299 00:10:55,410 --> 00:10:58,400 2 ao n parece muito ruim. n ao quadrado parece muito ruim. 300 00:10:58,400 --> 00:11:01,630 E vamos ver o que alguns desses pode ser, na realidade de hoje. 301 00:11:01,630 --> 00:11:05,430 E log n não se sente tão ruim, mas melhor do que n é o log de base 2 do n. 302 00:11:05,430 --> 00:11:08,080 Mas você sabe, ele teria sido ainda mais surpreendente se Jennifer, ou se, 303 00:11:08,080 --> 00:11:12,910 essa primeira semana, surgiu com algo que é log de registro de n. 304 00:11:12,910 --> 00:11:15,880 >> Portanto, em outras palavras, não há toda essa gama de possíveis soluções para 305 00:11:15,880 --> 00:11:18,570 problemas, mas, mesmo aqui, o aviso o que vai acontecer. 306 00:11:18,570 --> 00:11:22,910 Quando eu diminuir o zoom, qual destas curvas vai provar ser o absoluto 307 00:11:22,910 --> 00:11:26,630 pior os que estão na tela agora? 308 00:11:26,630 --> 00:11:28,680 Então n cubos parece muito ruim no momento. 309 00:11:28,680 --> 00:11:32,470 Mas se diminuir o zoom e ver mais do x e eixo-y, que vai 310 00:11:32,470 --> 00:11:34,550 dominar em última instância? 311 00:11:34,550 --> 00:11:37,120 Então, ele realmente se que 2 a n, e você pode descobrir isso apenas por 312 00:11:37,120 --> 00:11:39,990 ligar em algum cada vez maior números, e você verá que 2 para o 313 00:11:39,990 --> 00:11:42,070 n, de facto, muito mais rapidamente se torna maior. 314 00:11:42,070 --> 00:11:45,530 Se realmente diminuir o zoom, a 2 para o n algoritmo absolutamente uma merda. 315 00:11:45,530 --> 00:11:48,170 Quero dizer que isso vai levar um pouco de tempo para a 316 00:11:48,170 --> 00:11:49,460 computador para agitar completamente. 317 00:11:49,460 --> 00:11:52,500 >> Mas você vai ver ao longo do tempo, especialmente com conjuntos de problemas futuros e até mesmo 318 00:11:52,500 --> 00:11:55,600 projetos finais, é seus dados conjunto se torna grande, certo? 319 00:11:55,600 --> 00:11:58,300 Mesmo na primeira versão do Facebook, como o número de amigos, eo 320 00:11:58,300 --> 00:12:01,840 número de usuários registrados tem grande você pode classificar de telefone-lo e 321 00:12:01,840 --> 00:12:05,530 implementar algo com busca linear, ou uma classificação muito simples 322 00:12:05,530 --> 00:12:07,030 algoritmo, como veremos hoje. 323 00:12:07,030 --> 00:12:09,280 Você tem que começar a pensar mais e mais sobre estes problemas. 324 00:12:09,280 --> 00:12:12,070 E os tipos de problemas locais como Facebook e Google e Microsoft, 325 00:12:12,070 --> 00:12:16,350 e outros, trabalhar é exatamente esses tipo de dados grande tipo de perguntas 326 00:12:16,350 --> 00:12:18,530 cada vez mais nos dias de hoje. 327 00:12:18,530 --> 00:12:18,900 >> Tudo bem. 328 00:12:18,900 --> 00:12:23,800 Assim, o sucesso de Jennifer, em que a segunda algoritmo, francamente, ela fez incrivelmente 329 00:12:23,800 --> 00:12:26,110 bem o primeiro tempo, mas vamos escrevê-lo como sorte, para que 330 00:12:26,110 --> 00:12:27,000 pode fazer neste momento. 331 00:12:27,000 --> 00:12:30,970 No segundo caso, ela alavancado um algoritmo que repetiu novamente e 332 00:12:30,970 --> 00:12:34,670 novamente, mas ela levou para concedido um certa suposição de que nós permitimos 333 00:12:34,670 --> 00:12:39,370 , mas ela explorado algum detalhe o segunda vez que ela não tem o 334 00:12:39,370 --> 00:12:39,840 primeira vez. 335 00:12:39,840 --> 00:12:41,800 Que era o que? 336 00:12:41,800 --> 00:12:43,050 >> Que a lista foi classificada. 337 00:12:43,050 --> 00:12:46,350 Assim, logo que a lista foi resolvido, nós afirmam que Jennifer era capaz de fazer 338 00:12:46,350 --> 00:12:47,480 fundamentalmente melhor. 339 00:12:47,480 --> 00:12:51,450 Sete portas, sim, não é tão interessante, mas acho que estamos 7.000.000 portas. 340 00:12:51,450 --> 00:12:54,080 Sessão de n está indo definitivamente para realizar muito, muito 341 00:12:54,080 --> 00:12:55,610 mais rápido no longo prazo. 342 00:12:55,610 --> 00:12:58,880 Mas ela tinha que ter a portas classificadas para ela. 343 00:12:58,880 --> 00:13:02,320 Agora, eu tomei a liberdade de fazer o que com antecedência na tela do computador 344 00:13:02,320 --> 00:13:05,160 aqui, mas acho que Jennifer tive que fazer isso sozinha? 345 00:13:05,160 --> 00:13:10,120 Suponha-se que as portas em questão dados representados em um banco de dados, ou 346 00:13:10,120 --> 00:13:14,260 amigos registrados para Facebook, ou todas as páginas web na internet que 347 00:13:14,260 --> 00:13:16,880 vários sites pode precisar ao índice ou pesquisa sobre. 348 00:13:16,880 --> 00:13:20,940 >> Suponha que você acabou de ter um conjunto de dados brutos definir e foi deixado para você, ou para 349 00:13:20,940 --> 00:13:23,010 Jennifer fazer isso de triagem? 350 00:13:23,010 --> 00:13:26,950 Que, ao contrário, exige que nós respondemos a questão, bem como, quanto tempo 351 00:13:26,950 --> 00:13:31,080 teria levado Jennifer, ou até mesmo de mim, para ordenar os números com antecedência para 352 00:13:31,080 --> 00:13:32,680 que ela poderia tirar proveito disso? 353 00:13:32,680 --> 00:13:32,880 Certo? 354 00:13:32,880 --> 00:13:36,620 Porque a implicação, é claro, é se ele me leva muito tempo para classificar 355 00:13:36,620 --> 00:13:40,800 os números, quem diabos se importa que você pode encontrar um número como 50 tão rápido, 356 00:13:40,800 --> 00:13:44,850 como no caso de Jennifer, se mais de esmagada a quantidade de tempo total 357 00:13:44,850 --> 00:13:46,920 demorou, classificando as coisas com antecedência? 358 00:13:46,920 --> 00:13:49,320 >> Então, vamos ver se a gente não pode o pintar a imagem aqui. 359 00:13:49,320 --> 00:13:51,370 Eu tenho um monte mais estresse esferas, se isso ajuda 360 00:13:51,370 --> 00:13:52,270 quebrar o gelo aqui. 361 00:13:52,270 --> 00:13:55,690 E se você não se importar, nós precisa de sete voluntários - 362 00:13:55,690 --> 00:13:57,060 on, OK. 363 00:13:57,060 --> 00:13:57,240 Uau. 364 00:13:57,240 --> 00:13:59,250 Então, não tem que gastar em lâmpadas de mesa, ao que parece. 365 00:13:59,250 --> 00:13:59,690 Tudo bem. 366 00:13:59,690 --> 00:14:01,530 Assim como sobre vocês dois na frente. 367 00:14:01,530 --> 00:14:04,160 Que tal vocês dois nas costas. 368 00:14:04,160 --> 00:14:04,870 Então, isso é quatro. 369 00:14:04,870 --> 00:14:09,890 Como sobre você na frente cinco, seis e sete. 370 00:14:09,890 --> 00:14:10,320 Bem ali. 371 00:14:10,320 --> 00:14:13,260 Seu amigo está apontando para fora, de modo a obter o prêmio. 372 00:14:13,260 --> 00:14:13,700 >> Tudo bem. 373 00:14:13,700 --> 00:14:14,410 Vamos para cima. 374 00:14:14,410 --> 00:14:17,120 E por que não tê-lo caras vem aqui. 375 00:14:17,120 --> 00:14:18,960 Vou dar-lhe cada um número. 376 00:14:18,960 --> 00:14:22,150 E vá em frente e organizar-se de forma idêntica ao que está 377 00:14:22,150 --> 00:14:25,180 representado na tela. 378 00:14:25,180 --> 00:14:26,530 >> [Interpondo VOZES] 379 00:14:26,530 --> 00:14:28,160 >> DAVID J. MALAN: Oop, sorry. 380 00:14:28,160 --> 00:14:30,210 Bug. 381 00:14:30,210 --> 00:14:32,180 Tudo bem. 382 00:14:32,180 --> 00:14:32,750 Bem, aqui vamos nós. 383 00:14:32,750 --> 00:14:34,180 Número cinco. 384 00:14:34,180 --> 00:14:35,136 Número seis. 385 00:14:35,136 --> 00:14:37,770 Um, dois, três, quatro, cinco, seis, sete. 386 00:14:37,770 --> 00:14:39,410 Oh, isso é estranho. 387 00:14:39,410 --> 00:14:41,210 >> COLUNA 2: Vou pegar um -. 388 00:14:41,210 --> 00:14:41,900 >> DAVID J. MALAN: Bom negócio. 389 00:14:41,900 --> 00:14:43,130 Tudo bem. 390 00:14:43,130 --> 00:14:44,611 Obrigado por participar. 391 00:14:44,611 --> 00:14:47,200 >> [Aplausos] 392 00:14:47,200 --> 00:14:48,580 >> OK. 393 00:14:48,580 --> 00:14:48,860 Tudo bem. 394 00:14:48,860 --> 00:14:51,970 Portanto, temos quatro, dois, seis, um, três, sete, cinco. 395 00:14:51,970 --> 00:14:56,010 Aperfeiçoar isso temos sete voluntários aqui que são iguais à largura do 396 00:14:56,010 --> 00:14:57,430 matriz que estamos jogando com o anterior. 397 00:14:57,430 --> 00:14:59,470 E eu escolhi sete por razões que será apenas 398 00:14:59,470 --> 00:15:00,840 conveniente um pouco. 399 00:15:00,840 --> 00:15:04,400 E eu vou propor pela primeira vez que nós classificar estes sete voluntários. 400 00:15:04,400 --> 00:15:06,786 Se você gostaria, em primeiro lugar, para dizer Olá embora. 401 00:15:06,786 --> 00:15:08,970 Uma vez que este vai ser um embaraçosas vários minutos. 402 00:15:08,970 --> 00:15:10,370 Apresente-se. 403 00:15:10,370 --> 00:15:10,980 >> GRACE: Oi, eu sou Grace. 404 00:15:10,980 --> 00:15:14,190 Eu sou um estudante de segundo ano em Leverett House. 405 00:15:14,190 --> 00:15:14,620 >> Branson: Hi. 406 00:15:14,620 --> 00:15:15,620 Estou Branson. 407 00:15:15,620 --> 00:15:16,920 Eu sou um calouro na Weld. 408 00:15:16,920 --> 00:15:19,755 409 00:15:19,755 --> 00:15:20,230 >> GABE: Oi. 410 00:15:20,230 --> 00:15:21,040 Estou Gabe. 411 00:15:21,040 --> 00:15:22,300 Eu sou um júnior na Cabot. 412 00:15:22,300 --> 00:15:24,826 413 00:15:24,826 --> 00:15:25,980 >> NEIL: Eu sou Neil. 414 00:15:25,980 --> 00:15:29,090 Eu sou um calouro na Matthews. 415 00:15:29,090 --> 00:15:29,550 >> JASON: Eu sou Jason. 416 00:15:29,550 --> 00:15:32,816 Eu sou um calouro na Greenough. 417 00:15:32,816 --> 00:15:33,700 >> MIKE: Eu sou Mike. 418 00:15:33,700 --> 00:15:37,360 Eu sou um calouro na Grays. 419 00:15:37,360 --> 00:15:37,990 >> JESS: Eu sou Jess. 420 00:15:37,990 --> 00:15:40,313 Eu sou um estudante de segundo ano em Leverett. 421 00:15:40,313 --> 00:15:41,300 >> DAVID J. MALAN: Excelente. 422 00:15:41,300 --> 00:15:41,850 Tudo bem. 423 00:15:41,850 --> 00:15:44,190 Bem, obrigado a todos os nossos voluntários aqui até agora. 424 00:15:44,190 --> 00:15:47,110 E o desafio na mão agora vai ser a de classificar esses caras, mas, em seguida, 425 00:15:47,110 --> 00:15:50,250 vamos ter que pensar um pouco muito sobre como nós realmente eficiente 426 00:15:50,250 --> 00:15:51,110 classificou. 427 00:15:51,110 --> 00:15:52,580 Então, vamos primeiro tentar isso. 428 00:15:52,580 --> 00:15:55,970 Vocês podem ver os números uns dos outros apenas por colocar em torno dos cantos. 429 00:15:55,970 --> 00:15:59,380 Vá em frente e levar alguns segundos, e tipo-vos do menor na 430 00:15:59,380 --> 00:16:01,240 esquerda para a maior à direita. 431 00:16:01,240 --> 00:16:02,490 Ir. 432 00:16:02,490 --> 00:16:07,010 433 00:16:07,010 --> 00:16:07,530 >> OK. 434 00:16:07,530 --> 00:16:08,030 Bom. 435 00:16:08,030 --> 00:16:09,370 Isso foi muito danado rápido. 436 00:16:09,370 --> 00:16:14,040 Agora, alguém aqui, qual foi o algoritmo que esses caras aplicada? 437 00:16:14,040 --> 00:16:14,900 >> COLUNA 1: Pelo menos a maior. 438 00:16:14,900 --> 00:16:15,000 >> DAVID J. MALAN: OK. 439 00:16:15,000 --> 00:16:18,070 Pelo menos a maior é realmente uma espécie de objetivo, mas eu não tenho certeza que é 440 00:16:18,070 --> 00:16:18,890 realmente um algoritmo. 441 00:16:18,890 --> 00:16:21,810 Pelo menos a maior não diz me passo-a-passo o que fazer. 442 00:16:21,810 --> 00:16:22,833 Sim? 443 00:16:22,833 --> 00:16:24,083 >> COLUNA 1: [inaudível] 444 00:16:24,083 --> 00:16:26,010 445 00:16:26,010 --> 00:16:26,280 >> DAVID J. MALAN: OK. 446 00:16:26,280 --> 00:16:28,920 Então, se você vê uma pessoa menor do que seu número, então mover-se para 447 00:16:28,920 --> 00:16:29,680 o direito deles. 448 00:16:29,680 --> 00:16:32,800 Assim que agora está ficando cada vez mais expressivo, mais como um algoritmo, porque você 449 00:16:32,800 --> 00:16:35,410 pode-se dizer, se isso, então aquilo. 450 00:16:35,410 --> 00:16:37,050 Então nós temos algum tipo de construção condicional. 451 00:16:37,050 --> 00:16:39,700 E esses caras pareciam fazer que alguns vezes, porque alguns de vocês mudaram um pouco 452 00:16:39,700 --> 00:16:40,420 de uma distância. 453 00:16:40,420 --> 00:16:43,410 Então, houve presumivelmente algum tipo de looping acontecendo em suas mentes. 454 00:16:43,410 --> 00:16:44,610 >> Mas vamos tentar formalizar isso. 455 00:16:44,610 --> 00:16:47,540 Se vocês pudessem repostas a este arranjo. 456 00:16:47,540 --> 00:16:50,650 Vamos ver se não podemos formalizar esta uma pouco, e, em seguida, fazer a pergunta, apenas 457 00:16:50,650 --> 00:16:51,580 quão eficiente é essa? 458 00:16:51,580 --> 00:16:54,220 Claro que, quando fazemos isso de forma mais lenta, ele vai se sentir tão bem de 459 00:16:54,220 --> 00:16:57,210 um algoritmo, mas vamos ver se podemos colocar os dedos sobre os passos precisos. 460 00:16:57,210 --> 00:16:58,670 >> Então, vocês dois são quatro e dois. 461 00:16:58,670 --> 00:17:01,020 Ou você ordem correta ou incorreta? 462 00:17:01,020 --> 00:17:01,900 Obviamente incorreta. 463 00:17:01,900 --> 00:17:02,710 Então nós trocamos. 464 00:17:02,710 --> 00:17:05,170 Agora estou indo para mover de lado aqui e dizer: 4-6. 465 00:17:05,170 --> 00:17:06,240 Você está correta ou incorreta? 466 00:17:06,240 --> 00:17:06,599 >> GABE: Correto. 467 00:17:06,599 --> 00:17:07,180 >> DAVID J. MALAN: Correto. 468 00:17:07,180 --> 00:17:08,300 Seis e um? 469 00:17:08,300 --> 00:17:08,609 Não.. 470 00:17:08,609 --> 00:17:09,630 Troque. 471 00:17:09,630 --> 00:17:10,490 Então, isso é dois swaps. 472 00:17:10,490 --> 00:17:11,710 Seis e três anos? 473 00:17:11,710 --> 00:17:11,980 Não.. 474 00:17:11,980 --> 00:17:13,000 Troque. 475 00:17:13,000 --> 00:17:13,930 Seis e sete? 476 00:17:13,930 --> 00:17:14,630 Parece bom. 477 00:17:14,630 --> 00:17:15,396 Sete e cinco? 478 00:17:15,396 --> 00:17:16,150 >> JESS: [inaudível] 479 00:17:16,150 --> 00:17:17,089 >> DAVID J. MALAN: OK, troque. 480 00:17:17,089 --> 00:17:19,770 E classificados. 481 00:17:19,770 --> 00:17:19,980 Tudo bem. 482 00:17:19,980 --> 00:17:21,440 Então, obviamente, não, né? 483 00:17:21,440 --> 00:17:22,470 Então lá estava mais acontecendo. 484 00:17:22,470 --> 00:17:24,920 Mas, na verdade, esses caras, mesmo apenas instintivamente. 485 00:17:24,920 --> 00:17:25,450 continuou se movendo. 486 00:17:25,450 --> 00:17:27,710 Eles não parar, uma vez que eles corrigido um problema. 487 00:17:27,710 --> 00:17:27,839 Assim. 488 00:17:27,839 --> 00:17:29,390 Na verdade, eu vou ter para fazer a mesma coisa. 489 00:17:29,390 --> 00:17:32,720 Eu vou ter a sorte de retroceder para trás para o início deste problema, 490 00:17:32,720 --> 00:17:35,630 ou no início da presente de matriz pessoal, vamos começar a chamá-los. 491 00:17:35,630 --> 00:17:38,366 >> E agora, o que deve o meu algoritmo na segunda passagem será? 492 00:17:38,366 --> 00:17:39,220 >> COLUNA 1: a mesma coisa. 493 00:17:39,220 --> 00:17:39,940 >> DAVID J. MALAN: Mesma coisa. 494 00:17:39,940 --> 00:17:41,460 E isso, eu estou começando a gostar, certo? 495 00:17:41,460 --> 00:17:44,720 Assim que você pode encontrar-se fazendo a mesma coisa uma e outra vez, isso é 496 00:17:44,720 --> 00:17:47,890 tornando-se mais como um algoritmo, instinto e menos humana. 497 00:17:47,890 --> 00:17:48,680 >> Então, agora, aqui vamos nós de novo. 498 00:17:48,680 --> 00:17:49,870 Dois e quatro? 499 00:17:49,870 --> 00:17:50,220 Não. 500 00:17:50,220 --> 00:17:51,050 Quatro e um? 501 00:17:51,050 --> 00:17:53,380 Ah, houve de fato algumas trabalho ainda a ser feito. 502 00:17:53,380 --> 00:17:53,620 Por e três? 503 00:17:53,620 --> 00:17:54,572 Bom. 504 00:17:54,572 --> 00:17:56,000 Quatro e seis? 505 00:17:56,000 --> 00:17:58,380 Seis e cinco? 506 00:17:58,380 --> 00:17:59,470 Seis e sete? 507 00:17:59,470 --> 00:18:00,970 OK, agora, feito. 508 00:18:00,970 --> 00:18:01,550 OK, não. 509 00:18:01,550 --> 00:18:02,710 Eu tenho que voltar. 510 00:18:02,710 --> 00:18:05,130 >> Então, agora, mais uma vez, nós estamos fazendo isso um pouco mais deliberadamente. 511 00:18:05,130 --> 00:18:08,700 E agora, há apenas um cérebro executar este algoritmo. 512 00:18:08,700 --> 00:18:10,290 Uma CPU, se você quiser. 513 00:18:10,290 --> 00:18:13,090 E, francamente, esse é o único recurso vamos ter acesso. 514 00:18:13,090 --> 00:18:16,280 E uma vez que você voltar para um teclado e ter algo como C no nosso 515 00:18:16,280 --> 00:18:19,600 disposição, estamos apenas escrevendo um programa que pode fazer uma coisa de cada vez. 516 00:18:19,600 --> 00:18:22,900 Considerando que, esses caras há um momento, nós alavancado a sua inteligência coletiva 517 00:18:22,900 --> 00:18:24,180 como vocês fizeram na semana zero. 518 00:18:24,180 --> 00:18:24,980 Então, vamos continuar fazendo isso. 519 00:18:24,980 --> 00:18:26,260 >> Dois e um. 520 00:18:26,260 --> 00:18:26,945 Dois e três. 521 00:18:26,945 --> 00:18:27,460 Três e quatro. 522 00:18:27,460 --> 00:18:28,310 Quatro e cinco. 523 00:18:28,310 --> 00:18:28,620 Cinco e seis. 524 00:18:28,620 --> 00:18:30,510 Seis e sete. 525 00:18:30,510 --> 00:18:31,880 Feito? 526 00:18:31,880 --> 00:18:34,560 Então, eu estou, mas deixe-me jogar advogado do diabo. 527 00:18:34,560 --> 00:18:37,950 Eu, o tipo de computador que só fez um passe por esse conjunto de 528 00:18:37,950 --> 00:18:40,225 pessoas, sabe que eu sou feito? 529 00:18:40,225 --> 00:18:40,670 >> COLUNA 1: Não. 530 00:18:40,670 --> 00:18:41,050 >> DAVID J. MALAN: Então por quê? 531 00:18:41,050 --> 00:18:46,900 O que eu tenho que fazer, a fim de concluir decisivamente que estou a fazer? 532 00:18:46,900 --> 00:18:48,230 Provavelmente mais uma passagem. 533 00:18:48,230 --> 00:18:48,430 Certo? 534 00:18:48,430 --> 00:18:51,760 Porque tudo que eu sei de que anterior passe é que eu corrigi um erro. 535 00:18:51,760 --> 00:18:53,920 E isso significa, talvez haja ainda outro erro 536 00:18:53,920 --> 00:18:54,840 que eu preciso corrigir. 537 00:18:54,840 --> 00:18:58,680 Então eu só posso ter certeza de rebobinagem, e em seguida, verificando, 1-2, e dois 538 00:18:58,680 --> 00:19:00,940 três, três e quatro, quatro e cinco, cinco e seis, seis e sete. 539 00:19:00,940 --> 00:19:02,510 OK, agora eu fiz nenhum trabalho. 540 00:19:02,510 --> 00:19:05,990 >> Eu posso certamente me lembro que eu fiz não trabalhar com algo como uma variável, 541 00:19:05,990 --> 00:19:06,975 como um int. 542 00:19:06,975 --> 00:19:12,490 Chamá-lo de swaps, e se swaps é 0 uma vez que eu chegar até aqui, e ele começou a 0, então 543 00:19:12,490 --> 00:19:15,520 Gostaria apenas de ser estúpido para continuar frente e para trás, verificando novamente, e 544 00:19:15,520 --> 00:19:16,450 de novo, e de novo, certo? 545 00:19:16,450 --> 00:19:18,450 Porque você ficar preso em algum espécie de loop infinito. 546 00:19:18,450 --> 00:19:21,250 Assim, logo que há 0 swaps, podemos afirmar que este 547 00:19:21,250 --> 00:19:23,810 algoritmo é realmente completa. 548 00:19:23,810 --> 00:19:25,400 >> Agora, vamos colocar um nome sobre o assunto. 549 00:19:25,400 --> 00:19:28,930 O algoritmo que proponho nós apenas implementado é uma coisa chamada bolha 550 00:19:28,930 --> 00:19:32,800 tipo, conhecida como tal na medida em que os números que são maiores do tipo de 551 00:19:32,800 --> 00:19:37,990 bolha seu caminho até o topo, ou até para o fim da série de números. 552 00:19:37,990 --> 00:19:40,270 Mas quão eficiente foi esse algoritmo? 553 00:19:40,270 --> 00:19:44,600 Quantos passos que eu tenho fisicamente para ter, por exemplo, para classificar estas 554 00:19:44,600 --> 00:19:45,850 sete seres humanos? 555 00:19:45,850 --> 00:19:48,560 556 00:19:48,560 --> 00:19:49,550 >> De quatro a cinco anos? 557 00:19:49,550 --> 00:19:51,420 OK, muitos é em última instância vai ser a resposta. 558 00:19:51,420 --> 00:19:54,960 Mas, mesmo assim, o número específico não é tão interessante. 559 00:19:54,960 --> 00:19:56,670 Vamos generalizar como n. 560 00:19:56,670 --> 00:20:00,520 Então, se eu tivesse n pessoas aqui em cima, e eles foram, de alguma forma, em ordem aleatória no 561 00:20:00,520 --> 00:20:02,180 começando, em que ordem original. 562 00:20:02,180 --> 00:20:04,910 Bem, quantos passos eu tinha para assumir a primeira passagem? 563 00:20:04,910 --> 00:20:09,810 Era um, dois, três, quatro, cinco, seis, e eles são sete pessoas, de modo 564 00:20:09,810 --> 00:20:13,670 que é sete, seis -, de modo que n menos as etapas de uma primeira vez. 565 00:20:13,670 --> 00:20:16,280 >> Agora, quantos passos eu tinha a tomar quando eu rebobinado? 566 00:20:16,280 --> 00:20:19,310 Bem, poderíamos dobrar esse se nós realmente queríamos, mas por agora, estou 567 00:20:19,310 --> 00:20:22,300 só vou dizer, tudo bem, outro n menos 1. 568 00:20:22,300 --> 00:20:25,240 Assim, o n menos um vai ficar irritante para acompanhar, então vamos 569 00:20:25,240 --> 00:20:26,400 apenas arredondar ligeiramente. 570 00:20:26,400 --> 00:20:27,770 Então 2n passos. 571 00:20:27,770 --> 00:20:29,310 Então, 14 etapas, mais ou menos. 572 00:20:29,310 --> 00:20:31,930 >> Quantas vezes eu tomo um passo da próxima vez? 573 00:20:31,930 --> 00:20:33,740 Bem, é 3N. 574 00:20:33,740 --> 00:20:34,510 realmente. 575 00:20:34,510 --> 00:20:37,920 E agora, no pior dos casos, por exemplo, quantas vezes eu teria 576 00:20:37,920 --> 00:20:41,730 ido para trás e para frente, para trás e para frente, executar este algoritmo, trocando 577 00:20:41,730 --> 00:20:44,620 pessoas em cada passagem, mais ou menos? 578 00:20:44,620 --> 00:20:47,720 579 00:20:47,720 --> 00:20:50,010 É realmente n ao quadrado, certo? 580 00:20:50,010 --> 00:20:53,000 >> Porque, na pior das hipóteses, você pode tipo de pensar sobre isso de forma intuitiva, 581 00:20:53,000 --> 00:20:54,800 embora possa demorar um pouco pouco de tempo para afundar-se dentro 582 00:20:54,800 --> 00:20:57,590 No pior dos casos, o que seria isso sete pessoas parecia, em 583 00:20:57,590 --> 00:21:00,230 termos do acordo de seus números? 584 00:21:00,230 --> 00:21:01,460 Completamente para trás, certo? 585 00:21:01,460 --> 00:21:02,815 E só para simular que, qual era o seu nome? 586 00:21:02,815 --> 00:21:03,360 >> MIKE: Mike. 587 00:21:03,360 --> 00:21:03,640 >> DAVID J. MALAN: Mike? 588 00:21:03,640 --> 00:21:08,100 OK, Mike, você pode simplesmente juntar-me ao longo aqui por apenas um segundo? 589 00:21:08,100 --> 00:21:08,880 Na verdade, não. 590 00:21:08,880 --> 00:21:10,150 Desculpe Mike, vamos retroceder. 591 00:21:10,150 --> 00:21:10,910 Qual é o seu nome? 592 00:21:10,910 --> 00:21:11,180 >> NEIL: Neil. 593 00:21:11,180 --> 00:21:11,640 >> DAVID J. MALAN: Neil. 594 00:21:11,640 --> 00:21:13,750 OK, Neil, você vem com me, se você não se importa. 595 00:21:13,750 --> 00:21:17,150 Então eu vou propor, apenas para simplicidade, que Neil está agora no seu 596 00:21:17,150 --> 00:21:18,510 pior caso possível. 597 00:21:18,510 --> 00:21:20,720 Mas lembre-se como eu implementei meu algoritmo. 598 00:21:20,720 --> 00:21:24,530 Eu estou comparando, comparando, comparando, comparando, comparando, oh. 599 00:21:24,530 --> 00:21:26,640 Agora, esses caras estão fora de ordem, assim que eu resolver. 600 00:21:26,640 --> 00:21:27,980 Então vocês trocar. 601 00:21:27,980 --> 00:21:31,630 Mas considere agora, quanto mais distante Neil não tem que ir? 602 00:21:31,630 --> 00:21:32,690 É mais ou menos n. 603 00:21:32,690 --> 00:21:33,570 Você sabe, não é, na verdade, n. 604 00:21:33,570 --> 00:21:36,040 É como se, n menos 1, mas estou ficando irritado manter o controle do pequeno 605 00:21:36,040 --> 00:21:37,550 número, então vamos chamá-lo de n. 606 00:21:37,550 --> 00:21:42,860 >> Então, se Neil move um passo máximo de cada tempo, e para se deslocar Neil um passo, 607 00:21:42,860 --> 00:21:46,580 Eu tenho que fazer esta passagem realmente tedioso e para trás, isto é mais ou menos 608 00:21:46,580 --> 00:21:52,080 Fazendo isto, n passos, um total de n vezes, porque ele vai me levar 609 00:21:52,080 --> 00:21:55,820 que muitos passos para chegar Neil tudo o caminho para onde ele pertence. 610 00:21:55,820 --> 00:21:58,620 Deixai toda a gente se vocês foram todos mis-ordenadas, bem. 611 00:21:58,620 --> 00:22:01,100 >> Então, vamos chamar bubble sort n ao quadrado. 612 00:22:01,100 --> 00:22:04,860 O tempo de execução deste algoritmo, o desempenho deste algoritmo, o 613 00:22:04,860 --> 00:22:07,120 eficiência deste algoritmo, vamos apenas descrever mais 614 00:22:07,120 --> 00:22:08,800 geralmente como n ao quadrado. 615 00:22:08,800 --> 00:22:11,650 Que é bom, porque eu poderia fazer o mesmo exemplo, com oito pessoas, nove 616 00:22:11,650 --> 00:22:15,450 pessoas, um milhão de pessoas, e isso resposta não vai mudar. 617 00:22:15,450 --> 00:22:18,870 >> Então, se vocês não se importaria, vamos redefinir-lo para onde você começou. 618 00:22:18,870 --> 00:22:22,510 E vamos tentar duas outras abordagens e ver se não podemos fazer fundamentalmente 619 00:22:22,510 --> 00:22:23,820 melhor do que este. 620 00:22:23,820 --> 00:22:27,130 Então, desta vez, eu vou propor uma espécie de algoritmo diferente. 621 00:22:27,130 --> 00:22:29,950 Isso foi muito inteligente de nós da última vez, e vocês estavam certos de ter a 622 00:22:29,950 --> 00:22:32,470 instintos certos de apenas uma espécie de troca de pares. 623 00:22:32,470 --> 00:22:36,500 Mas se eu realmente queria abordar esse simplesmente, e meu objetivo é mover-se 624 00:22:36,500 --> 00:22:39,800 todos os números de pequenos desta maneira, e empurrar todos os grandes números que 625 00:22:39,800 --> 00:22:43,030 Assim, por que não posso fazer isso apenas no mais ingênua maneira possível e ver se eu 626 00:22:43,030 --> 00:22:45,730 pode fazer melhor do que aquilo que era um algoritmo bastante complexo? 627 00:22:45,730 --> 00:22:46,620 >> Então vamos ver. 628 00:22:46,620 --> 00:22:48,940 Quatro é um número bastante pequeno, por isso estou vai deixá-lo lá momento. 629 00:22:48,940 --> 00:22:50,610 Ooh, o número dois é ainda melhor. 630 00:22:50,610 --> 00:22:52,230 Então você pode apenas um passo à frente por um momento? 631 00:22:52,230 --> 00:22:55,670 Este é atualmente o meu menor numerado candidato, e eu vou me lembrar 632 00:22:55,670 --> 00:22:57,000 que com, tipo, uma variável. 633 00:22:57,000 --> 00:22:57,930 Mas eu vou manter a verificação. 634 00:22:57,930 --> 00:22:59,890 Existe alguém cuja número é menor? 635 00:22:59,890 --> 00:23:00,460 Seis, não. 636 00:23:00,460 --> 00:23:01,390 Oh, há Neil novamente. 637 00:23:01,390 --> 00:23:04,050 >> Então eu vou empurrá-lo de volta tipo de conceitualmente. 638 00:23:04,050 --> 00:23:05,120 Neil virá para a frente. 639 00:23:05,120 --> 00:23:08,440 E agora, a variável que eu estou usando para acompanhar o que tem o menor 640 00:23:08,440 --> 00:23:11,390 número é atualizado para conter Localização de Neil. 641 00:23:11,390 --> 00:23:12,110 Bem, vamos ver. 642 00:23:12,110 --> 00:23:13,960 Três, sete, cinco. 643 00:23:13,960 --> 00:23:15,590 OK, eu sei que Neil era o menor. 644 00:23:15,590 --> 00:23:18,110 Qual é a coisa mais simples para eu fazer agora? 645 00:23:18,110 --> 00:23:21,410 Eu não vou perder meu tempo por apenas Neil borbulhando um local para a esquerda. 646 00:23:21,410 --> 00:23:25,350 Por que não posso simplesmente colocar Neil onde ele pertence, o que é, naturalmente, onde? 647 00:23:25,350 --> 00:23:26,160 >> Todo o caminho no início. 648 00:23:26,160 --> 00:23:27,720 Então Neil, venha comigo. 649 00:23:27,720 --> 00:23:28,910 E qual era o seu nome? 650 00:23:28,910 --> 00:23:29,310 >> GRACE: Grace. 651 00:23:29,310 --> 00:23:29,710 >> DAVID J. MALAN: Grace. 652 00:23:29,710 --> 00:23:29,920 OK. 653 00:23:29,920 --> 00:23:32,490 Então, Graça, infelizmente, você está tipo de no caminho. 654 00:23:32,490 --> 00:23:34,290 Então, como vamos resolver este problema? 655 00:23:34,290 --> 00:23:34,490 Certo? 656 00:23:34,490 --> 00:23:37,500 Se esta é uma matriz, não há apenas sete localidades. 657 00:23:37,500 --> 00:23:40,830 Lembre-se que, com Rob, nós falamos sobre declarando as idades, e que só tinha um 658 00:23:40,830 --> 00:23:41,740 número finito de idades? 659 00:23:41,740 --> 00:23:42,535 A mesma idéia aqui. 660 00:23:42,535 --> 00:23:44,300 Nós temos apenas um número finito de inteiros. 661 00:23:44,300 --> 00:23:47,590 Graça é uma espécie de em nossa maneira, então como é que vamos resolver? 662 00:23:47,590 --> 00:23:49,555 >> A maneira mais simples é assim, Graça, desculpe. 663 00:23:49,555 --> 00:23:51,870 Você vai ter que passar por cima de lá para que possamos fazer o quarto. 664 00:23:51,870 --> 00:23:55,290 Agora, se você pensar sobre isso, talvez nós apenas piorou o problema. 665 00:23:55,290 --> 00:23:58,510 E talvez nós fizemos, porque o que se Graça estavam no lugar certo? 666 00:23:58,510 --> 00:24:01,730 Mas nós sabemos que ela não é, porque caso contrário, ela teria sido 667 00:24:01,730 --> 00:24:03,980 pé para a frente em vez de Neil neste momento, certo? 668 00:24:03,980 --> 00:24:05,550 Já checou o número para fora. 669 00:24:05,550 --> 00:24:05,770 >> Tudo bem. 670 00:24:05,770 --> 00:24:09,110 Então, agora, Neil está no lugar certo, e Eu posso fazer uma pequena otimização. 671 00:24:09,110 --> 00:24:11,740 Para o próximo minuto, eu vou ignorar Neil todos juntos, de modo a não 672 00:24:11,740 --> 00:24:15,280 desperdice seu tempo, ou acidentalmente trocá-lo para o lugar errado. 673 00:24:15,280 --> 00:24:17,805 Então, agora, como faço para encontrar o próximo elemento que é menor? 674 00:24:17,805 --> 00:24:18,480 Dois. 675 00:24:18,480 --> 00:24:20,225 Isso é um número muito bom, se você quer dar um passo adiante e 676 00:24:20,225 --> 00:24:21,100 Eu vou lembrar de você. 677 00:24:21,100 --> 00:24:21,980 Seis, não é bom. 678 00:24:21,980 --> 00:24:24,820 Quatro, três, sete, cinco, não é bom. 679 00:24:24,820 --> 00:24:26,800 Então deixe-me levá-lo para o seu lugar certo. 680 00:24:26,800 --> 00:24:28,470 E nós só temos sorte desta vez. 681 00:24:28,470 --> 00:24:31,350 >> Agora, eu vou ignorar estes dois caras, e agora fazer mais uma 682 00:24:31,350 --> 00:24:32,260 passar por isso. 683 00:24:32,260 --> 00:24:33,490 Six, que um número muito pequeno. 684 00:24:33,490 --> 00:24:34,300 Vamos em frente. 685 00:24:34,300 --> 00:24:35,220 Oh, desculpe. 686 00:24:35,220 --> 00:24:37,640 Número de Grace é melhor, para pisar para a frente. 687 00:24:37,640 --> 00:24:38,260 Four. 688 00:24:38,260 --> 00:24:39,120 Desculpe, Grace. 689 00:24:39,120 --> 00:24:39,950 Voltar novamente. 690 00:24:39,950 --> 00:24:41,550 O número três é melhor. 691 00:24:41,550 --> 00:24:42,290 Sete. 692 00:24:42,290 --> 00:24:42,720 Cinco. 693 00:24:42,720 --> 00:24:43,550 E agora, qual é o seu nome? 694 00:24:43,550 --> 00:24:44,000 >> JASON: Jason. 695 00:24:44,000 --> 00:24:44,420 >> DAVID J. MALAN: Jason. 696 00:24:44,420 --> 00:24:47,050 Assim Jason é agora o menor elemento eu selecionei. 697 00:24:47,050 --> 00:24:49,160 Onde ele está indo? 698 00:24:49,160 --> 00:24:50,380 Então, onde seis é. 699 00:24:50,380 --> 00:24:51,210 E o seu nome é novo? 700 00:24:51,210 --> 00:24:51,710 >> GABE: Gabe. 701 00:24:51,710 --> 00:24:52,340 >> DAVID J. MALAN: Gabe. 702 00:24:52,340 --> 00:24:53,220 Gabe é o caminho. 703 00:24:53,220 --> 00:24:54,640 Qual é a coisa mais fácil de fazer? 704 00:24:54,640 --> 00:24:58,390 Troque esses dois caras e continuar. 705 00:24:58,390 --> 00:24:59,020 Então, agora vamos ver. 706 00:24:59,020 --> 00:25:00,170 Quem é o menor? 707 00:25:00,170 --> 00:25:01,030 Four. 708 00:25:01,030 --> 00:25:01,990 Deixe-me apenas um tipo de fraude. 709 00:25:01,990 --> 00:25:03,090 Cinco vai ser o menor. 710 00:25:03,090 --> 00:25:05,220 Acho que no próximo, se, você quer pisar para a frente, o que eu tenho a ver com 711 00:25:05,220 --> 00:25:06,820 esses caras, com Gabe? 712 00:25:06,820 --> 00:25:08,450 Troque novamente. 713 00:25:08,450 --> 00:25:10,740 Então, agora, ainda um pouco fora de ordem. 714 00:25:10,740 --> 00:25:14,140 Eu encontrei Gabe para ser o menor, então Eu pop-lo, movê-lo mais caras. 715 00:25:14,140 --> 00:25:15,190 E feito. 716 00:25:15,190 --> 00:25:17,200 >> Assim resposta é a mesma. 717 00:25:17,200 --> 00:25:18,600 O resultado final é o mesmo. 718 00:25:18,600 --> 00:25:22,730 Qual destes dois algoritmos é melhor? 719 00:25:22,730 --> 00:25:23,500 A segunda, eu ouvi. 720 00:25:23,500 --> 00:25:24,252 Por quê? 721 00:25:24,252 --> 00:25:25,900 >> COLUNA 3: é n passos [inaudível]. 722 00:25:25,900 --> 00:25:27,600 >> DAVID J. MALAN: É n passos, no máximo. 723 00:25:27,600 --> 00:25:28,490 Interessante. 724 00:25:28,490 --> 00:25:30,610 Assim é que? 725 00:25:30,610 --> 00:25:33,630 Assim como eu encontrar o menor elemento? 726 00:25:33,630 --> 00:25:37,060 Quantos passos que eu tenho que tomar a encontrar o menor elemento? 727 00:25:37,060 --> 00:25:39,220 Eu tinha um olhar todo o caminho no final, certo? 728 00:25:39,220 --> 00:25:41,530 Porque em que o pior caso, o que Neil se foram por aqui? 729 00:25:41,530 --> 00:25:45,700 Então, basta encontrar o menor elemento me n passos, ou n menos 1 leva. 730 00:25:45,700 --> 00:25:46,100 Mas, OK. 731 00:25:46,100 --> 00:25:46,980 Então corrigir Neil. 732 00:25:46,980 --> 00:25:48,740 Lembre-se que, cerca de um minuto atrás. 733 00:25:48,740 --> 00:25:51,680 >> Mas como é que eu encontrar o próximo menor elemento? 734 00:25:51,680 --> 00:25:54,830 É n menos 1, ou n menos 2 realmente, a partir do número de passos. 735 00:25:54,830 --> 00:25:55,440 Então OK. 736 00:25:55,440 --> 00:25:57,390 Então eu fiz n menos 2. 737 00:25:57,390 --> 00:25:57,600 Tudo bem. 738 00:25:57,600 --> 00:25:59,130 Assim que se sente um pouco melhor. 739 00:25:59,130 --> 00:25:59,730 Tudo bem. 740 00:25:59,730 --> 00:26:03,270 Quantos passos da próxima vez encontrar o número três? 741 00:26:03,270 --> 00:26:04,420 Assim, n menos 4. 742 00:26:04,420 --> 00:26:07,670 Então está diminuindo, uma a menos pisar em cada iteração. 743 00:26:07,670 --> 00:26:08,740 Portanto, este não se sentir melhor, certo? 744 00:26:08,740 --> 00:26:13,450 Se a última vez que foi mais ou menos n vezes n, desta vez é menos n 1, mais n menos 745 00:26:13,450 --> 00:26:16,500 2, além de n menos 3, mais n menos 4, ponto, ponto, ponto. 746 00:26:16,500 --> 00:26:18,750 Mas se você se lembra de sua escola livros didáticos, a pequena fraude 747 00:26:18,750 --> 00:26:24,380 folha na parte de trás que tem fórmulas, se você somar essa série de números, 748 00:26:24,380 --> 00:26:31,280 que é o número total de passos será que eu levo aqui? 749 00:26:31,280 --> 00:26:36,580 >> Este é um daqueles, tipo, n menos 1, n vezes, divididos por 2. 750 00:26:36,580 --> 00:26:39,040 Então deixe-me ver se eu posso puxar isso por apenas um momento. 751 00:26:39,040 --> 00:26:42,230 E novamente, eu sou o tipo de arredondamento alguns números apenas para manter nossa vida simples, 752 00:26:42,230 --> 00:26:47,830 mas se bem me lembro, é algo como se Eu n menos uma coisas, então n menos 753 00:26:47,830 --> 00:26:53,570 2, então n menos 3, é mais ou menos algo parecido com isso mais de 2, e se eu 754 00:26:53,570 --> 00:26:55,510 multiplicar isso, é realmente praça n. 755 00:26:55,510 --> 00:26:58,940 Que não está se sentindo muito bem. n n menos mais dois. 756 00:26:58,940 --> 00:27:00,350 >> Mas aqui está a coisa. 757 00:27:00,350 --> 00:27:03,720 Em ciência da computação, quando os problemas começam a ficar interessantes é quando n 758 00:27:03,720 --> 00:27:04,700 fica muito grande. 759 00:27:04,700 --> 00:27:08,110 E quando n fica muito grande, o que de esses valores vai dominar tudo 760 00:27:08,110 --> 00:27:09,750 dos outros? 761 00:27:09,750 --> 00:27:10,990 Ele é o tipo de n ao quadrado, certo? 762 00:27:10,990 --> 00:27:13,340 Sim, dividindo-se por dois é muito bom. 763 00:27:13,340 --> 00:27:16,740 Mas se você está falando de bilhões de pedaços de dados, ou trilhões de 764 00:27:16,740 --> 00:27:18,700 pedaços de dados, ok, então você está duas vezes mais rápido. 765 00:27:18,700 --> 00:27:22,440 Mas quem realmente se importa se esse grande número, Se esse fator é o que recebe 766 00:27:22,440 --> 00:27:23,040 cada vez maior. 767 00:27:23,040 --> 00:27:25,990 E, certamente, faz mais de uma diferença que esse cara. 768 00:27:25,990 --> 00:27:29,120 Assim, mesmo que vocês estão certos, o segundo algoritmo, vamos chamá-lo 769 00:27:29,120 --> 00:27:32,970 seleção de tipo, é, no mundo real, um pouco mais rápido, potencialmente, porque eu sou 770 00:27:32,970 --> 00:27:35,360 tomando cada vez menos passos de cada vez. 771 00:27:35,360 --> 00:27:37,340 >> Realmente não é fundamentalmente mais rápido. 772 00:27:37,340 --> 00:27:41,430 Porque se nós realmente jogar isso para grandes valores de n, no final do 773 00:27:41,430 --> 00:27:44,750 o dia, grande o suficiente para n, ainda é vai sentir-se bastante lento. 774 00:27:44,750 --> 00:27:46,770 Bem, deixe-me tirar uma última passagem por aí. 775 00:27:46,770 --> 00:27:48,920 Isso é o que eu chamaria seleção espécie. 776 00:27:48,920 --> 00:27:51,040 Vocês podem reiniciar-se uma última vez? 777 00:27:51,040 --> 00:27:53,550 E neste último caso, eu vou propor algo 778 00:27:53,550 --> 00:27:54,970 chamado ordenação por inserção. 779 00:27:54,970 --> 00:27:57,470 Ordenação por inserção ser, conceitualmente, um pouco diferente. 780 00:27:57,470 --> 00:28:00,980 >> Ao invés de ir para trás e para a frente e selecionar o menor elemento, eu sou 781 00:28:00,980 --> 00:28:05,030 apenas indo para lidar com cada uma delas caras como eu encontrá-los, e insira 782 00:28:05,030 --> 00:28:06,850 los em seu lugar correto. 783 00:28:06,850 --> 00:28:10,160 Então, eu só vou começar com Graça, e eu vejo que ela é o número quatro. 784 00:28:10,160 --> 00:28:11,720 Onde é que o número quatro pertence? 785 00:28:11,720 --> 00:28:14,940 Eu não comecei nada de triagem, então Grace começa a ficar ali. 786 00:28:14,940 --> 00:28:18,355 E agora eu vou reclamar, se você pudesse dar um passo para a direita, este 787 00:28:18,355 --> 00:28:21,650 minha lista ordenada, essa é minha lista restante indiferenciados. 788 00:28:21,650 --> 00:28:23,260 Então agora eu vou continuar a seguir, e qual é o seu nome? 789 00:28:23,260 --> 00:28:23,700 >> Branson:. 790 00:28:23,700 --> 00:28:24,150 >> DAVID J. MALAN: Branson. 791 00:28:24,150 --> 00:28:25,375 Então Branson é o número dois. 792 00:28:25,375 --> 00:28:27,490 Então, eu vou levá-lo por um momento. 793 00:28:27,490 --> 00:28:30,940 E agora, onde você pertence neste array? 794 00:28:30,940 --> 00:28:32,360 Assim, para o direito de Grace. 795 00:28:32,360 --> 00:28:35,670 Então, novamente, nós somos o tipo de fazer Graça fazer um monte de trabalho aqui. 796 00:28:35,670 --> 00:28:37,290 Onde é que vamos colocá-lo? 797 00:28:37,290 --> 00:28:40,120 Então, nós estamos indo para deslizar-lo para o à esquerda, e inserir Branson lá. 798 00:28:40,120 --> 00:28:41,680 Mas agora eu afirmo que vocês são feitos. 799 00:28:41,680 --> 00:28:43,240 Mas repare, eu não estou usando o espaço extra. 800 00:28:43,240 --> 00:28:45,130 É ainda dois elementos aqui, cinco ali. 801 00:28:45,130 --> 00:28:47,910 Tamanho total do conjunto é de 7, por isso estou não enganar, tudo bem? 802 00:28:47,910 --> 00:28:51,950 >> Portanto, agora temos, com Gabe aqui, o número seis, onde você pertence? 803 00:28:51,950 --> 00:28:52,650 Você teve sorte novamente. 804 00:28:52,650 --> 00:28:53,820 Então, você começa a ficar ali. 805 00:28:53,820 --> 00:28:57,210 Basta dar um leve passo para a direita só para deixar claro que você está classificado. 806 00:28:57,210 --> 00:29:00,520 E agora temos Neil novamente, o número de um, onde você vai? 807 00:29:00,520 --> 00:29:03,540 E agora é o lugar onde nós vamos começar a ver que este algoritmo, que em primeiro 808 00:29:03,540 --> 00:29:05,950 vista, sente-se muito inteligente, assista que está prestes a acontecer. 809 00:29:05,950 --> 00:29:07,370 Se você pudesse avançar. 810 00:29:07,370 --> 00:29:09,260 >> Aonde queremos colocar Neil? 811 00:29:09,260 --> 00:29:11,830 Então, obviamente, aqui, assim como obtemos Neil lá? 812 00:29:11,830 --> 00:29:12,970 Vamos fazer isso passo-a-passo. 813 00:29:12,970 --> 00:29:15,620 Gabe, onde você precisa ir? 814 00:29:15,620 --> 00:29:19,590 Sim, assim que tomar um grande passo, ou duas meias-medidas para tornar 815 00:29:19,590 --> 00:29:20,820 um passo por lá. 816 00:29:20,820 --> 00:29:21,750 Graça, onde você vai? 817 00:29:21,750 --> 00:29:22,510 Bom. 818 00:29:22,510 --> 00:29:23,500 Assim, uma outra etapa. 819 00:29:23,500 --> 00:29:24,960 E, finalmente, Branson? 820 00:29:24,960 --> 00:29:25,460 Outro passo. 821 00:29:25,460 --> 00:29:27,190 E agora podemos colocar Neil no lugar. 822 00:29:27,190 --> 00:29:28,440 >> Então, agora, continuar essa lógica. 823 00:29:28,440 --> 00:29:32,420 Mesmo que não estão mudando Neil mais, e mais, e mais, para colocá-lo 824 00:29:32,420 --> 00:29:36,420 onde ele passa, no pior caso, o próximo número podemos encontrar poderia 825 00:29:36,420 --> 00:29:42,220 ser o número, por exemplo, houve um número zero, então vamos mudar tudo 826 00:29:42,220 --> 00:29:42,730 esses caras. 827 00:29:42,730 --> 00:29:44,950 Suponha-se que há um número negativo um, então temos que mudar 828 00:29:44,950 --> 00:29:46,080 todos esses caras. 829 00:29:46,080 --> 00:29:48,500 Então, nós estamos realmente apenas uma espécie de inversão o problema ao redor, de modo que estamos 830 00:29:48,500 --> 00:29:52,620 transferir a despesa do de modo que o processo de selecção de inserção 831 00:29:52,620 --> 00:29:56,930 processo, de modo que vocês só tinha para movimentar cerca de n menos algo 832 00:29:56,930 --> 00:29:57,940 número de passos. 833 00:29:57,940 --> 00:30:01,200 E esse número de passos é só ir aumentar à medida que eu escolher mais números, 834 00:30:01,200 --> 00:30:04,730 se eu tiver que ficar empurrando vocês para trás, e volta, e volta. 835 00:30:04,730 --> 00:30:08,320 >> Então, a coisa mais triste agora é tudo isso algoritmos são n ao quadrado. 836 00:30:08,320 --> 00:30:10,570 Vamos em frente e, graças a estes caras, e visualizá-las um pouco 837 00:30:10,570 --> 00:30:11,090 diferente. 838 00:30:11,090 --> 00:30:12,312 Muito bem feito. 839 00:30:12,312 --> 00:30:14,120 >> [Aplausos] 840 00:30:14,120 --> 00:30:15,030 >> Tudo bem. 841 00:30:15,030 --> 00:30:16,280 Lá você vai. 842 00:30:16,280 --> 00:30:18,390 843 00:30:18,390 --> 00:30:18,470 Obrigado por - 844 00:30:18,470 --> 00:30:19,190 >> Branson: [inaudível] manter os números. 845 00:30:19,190 --> 00:30:21,990 >> DAVID J. MALAN: Não, você pode manter os números assim. 846 00:30:21,990 --> 00:30:23,440 Tudo bem. 847 00:30:23,440 --> 00:30:24,100 Bem feito. 848 00:30:24,100 --> 00:30:25,300 Tudo bem. 849 00:30:25,300 --> 00:30:30,510 Então vamos ver se não podemos agora resumir mais rapidamente e mais visualmente 850 00:30:30,510 --> 00:30:33,410 exatamente o que aconteceu aqui como se segue. 851 00:30:33,410 --> 00:30:36,510 852 00:30:36,510 --> 00:30:38,770 Eu estou indo para ir em frente e puxe para cima Firefox. 853 00:30:38,770 --> 00:30:41,310 Vamos ligar essa demonstração no site do curso. 854 00:30:41,310 --> 00:30:43,870 Java é um pouco chato para começar a trabalhar em alguns navegadores estes dias. 855 00:30:43,870 --> 00:30:46,760 Então, se você brincar com isso em casa, perceber que você pode precisar usar Firefox 856 00:30:46,760 --> 00:30:47,990 para fazê-lo funcionar. 857 00:30:47,990 --> 00:30:50,440 E o que eu vou fazer com este demonstração é o seguinte. 858 00:30:50,440 --> 00:30:54,875 >> No fundo, eu tenho um monte de opções de menu, incluindo um começo e uma 859 00:30:54,875 --> 00:30:55,840 botão de parar. 860 00:30:55,840 --> 00:30:59,450 Além disso, como um lado, parece haver um bug nesses programas, em que você 861 00:30:59,450 --> 00:31:03,720 não pode realmente ver a partida ou parada botão, a menos que você mantenha Comando ou Alt 862 00:31:03,720 --> 00:31:06,560 mais e zoom in, que curiosamente mostra mais botões. 863 00:31:06,560 --> 00:31:09,090 Portanto, apenas FYI, se você jogar com isso em casa. 864 00:31:09,090 --> 00:31:12,870 Agora eu vou clicar em Iniciar, em apenas um momento, depois de um atraso de especificar, 865 00:31:12,870 --> 00:31:16,810 como, a 200 milésimos de segundo aqui, apenas para que possamos ver o que acontece. 866 00:31:16,810 --> 00:31:20,180 >> Então, eu afirmo que esta é uma visualização do primeiro algoritmo 867 00:31:20,180 --> 00:31:23,730 esses caras fizeram, bubble sort, em que nós trocamos pessoas por pares. 868 00:31:23,730 --> 00:31:27,490 O insight fundamental para essa visualização é que a altura das barras 869 00:31:27,490 --> 00:31:30,510 representa o tamanho do número. 870 00:31:30,510 --> 00:31:32,210 Assim, o mais alto do bar, o Quanto maior o número. 871 00:31:32,210 --> 00:31:33,680 Mais curto da barra, menor o número. 872 00:31:33,680 --> 00:31:38,630 E se você observar, estamos passando por a primeira iteração do algoritmo, 873 00:31:38,630 --> 00:31:42,620 troca de pequenos e grandes números, de modo que o número pequeno vem em primeiro lugar e 874 00:31:42,620 --> 00:31:44,280 o grande número vai para a direita. 875 00:31:44,280 --> 00:31:48,770 >> E assim que chegamos ao final de um array de muitos mais números do que sete, estamos 876 00:31:48,770 --> 00:31:49,900 vai voltar para o início. 877 00:31:49,900 --> 00:31:51,140 E antecipar isso. 878 00:31:51,140 --> 00:31:54,860 Na extrema esquerda, que o rapaz está acontecendo para trocar para o lado, e isto 879 00:31:54,860 --> 00:31:56,010 processo se repete. 880 00:31:56,010 --> 00:31:59,450 Agora essa visualização fica rapidamente chato, então deixe-me ir em frente e parar 881 00:31:59,450 --> 00:32:04,170 , mude o atraso algo muito mais rápido apenas para começar agora, uma sensação de 882 00:32:04,170 --> 00:32:05,060 este algoritmo. 883 00:32:05,060 --> 00:32:07,840 >> Assim, mesmo que eu acelerava-se, este é como atualizar meu processador, comprando 884 00:32:07,840 --> 00:32:08,580 um novo computador. 885 00:32:08,580 --> 00:32:12,980 Eu não mudaram fundamentalmente o meu algoritmo, mas você pode realmente ver mais 886 00:32:12,980 --> 00:32:16,800 claramente do que com os seres humanos, que a grande números estão borbulhando até o topo, 887 00:32:16,800 --> 00:32:20,900 e os números pequenos estão borbulhando para a parte inferior. 888 00:32:20,900 --> 00:32:22,390 E agora essa coisa aqui classificados. 889 00:32:22,390 --> 00:32:25,260 E, como um aparte, nas praças, há apenas algumas escrituração lá para 890 00:32:25,260 --> 00:32:28,010 ajudá-lo a contar quantas comparações, ou quantos swaps têm 891 00:32:28,010 --> 00:32:28,950 realmente foi feito. 892 00:32:28,950 --> 00:32:30,750 >> Bem, vamos tentar uma das os outros que vimos. 893 00:32:30,750 --> 00:32:37,116 Deixe-me clique no bubble sort aqui, e deixe-me escolher, e esta página inteira 894 00:32:37,116 --> 00:32:38,936 é um pouco buggy. 895 00:32:38,936 --> 00:32:41,155 Vamos aceitar o risco e executá-lo novamente. 896 00:32:41,155 --> 00:32:44,560 897 00:32:44,560 --> 00:32:45,030 Lá vamos nós. 898 00:32:45,030 --> 00:32:47,180 Então vamos fazer a seleção tipo. 899 00:32:47,180 --> 00:32:49,140 Eu não sei por que o menu aparece por lá. 900 00:32:49,140 --> 00:32:54,070 Vamos zoom para corrigir isso bug, mudar isso para 50. 901 00:32:54,070 --> 00:32:56,020 Ah, vamos realmente fazer muito mais rápido. 902 00:32:56,020 --> 00:32:59,160 Cinco milissegundos ou menos, e começar. 903 00:32:59,160 --> 00:33:00,470 >> Portanto, esta é a seleção de tipo. 904 00:33:00,470 --> 00:33:03,070 Então, novamente, pensar sobre o que fez com os seres humanos aqui. 905 00:33:03,070 --> 00:33:08,490 Nós fomos através da matriz e selecionados o elemento mais pequeno, novamente, 906 00:33:08,490 --> 00:33:09,250 e de novo, e de novo. 907 00:33:09,250 --> 00:33:11,110 Agora eu afirmo que ainda era muito ruim. 908 00:33:11,110 --> 00:33:15,010 Foi ainda n ao quadrado, mais ou menos, mas foi, no mundo real, um pouco 909 00:33:15,010 --> 00:33:18,280 mais rápido, porque eu estava realmente tomando ligeiramente menos passos de cada vez. 910 00:33:18,280 --> 00:33:19,800 Mas estamos apenas falando o quê? 911 00:33:19,800 --> 00:33:21,830 Talvez 40 ou mais bares aqui? 912 00:33:21,830 --> 00:33:23,200 Não estamos falando de 40 milhões. 913 00:33:23,200 --> 00:33:27,430 Portanto, não é totalmente claro para mim que era de fato um ganho significativo. 914 00:33:27,430 --> 00:33:32,530 >> Deixe-me agora voltar atrás e mudar a nossa terceiro algoritmo, que foi selecionado 915 00:33:32,530 --> 00:33:33,180 ordenação por inserção. 916 00:33:33,180 --> 00:33:36,380 E agora é realmente de buggy, pois o menu realmente não deveria estar lá. 917 00:33:36,380 --> 00:33:40,840 Então, agora vamos rolar para trás até aqui e iniciar este algoritmo. 918 00:33:40,840 --> 00:33:43,270 Whoop, começar e parar. 919 00:33:43,270 --> 00:33:47,160 Assim, este tipo de tem um padrão bastante a ela, em que estamos mais uma vez 920 00:33:47,160 --> 00:33:50,240 inserindo os seres humanos, ou em Neste caso, as barras em 921 00:33:50,240 --> 00:33:52,620 a sua localização apropriada. 922 00:33:52,620 --> 00:33:55,430 E ele já fez antes Eu me virei. 923 00:33:55,430 --> 00:33:58,940 Mas este, também, em teoria, ainda n ao quadrado. 924 00:33:58,940 --> 00:34:01,430 >> Então vamos ver se não podemos resumir estes como segue. 925 00:34:01,430 --> 00:34:04,750 Eu estou indo para ir em frente e apenas para dar nós tipo de uma maneira comum de falar 926 00:34:04,750 --> 00:34:08,489 sobre essas coisas, deixe-me apresentar apenas um pouco de notação aqui. 927 00:34:08,489 --> 00:34:12,480 Você está prestes a ver uma coisa chamada grande Ó, porque é literalmente uma grande 928 00:34:12,480 --> 00:34:16,320 O. e esta é uma forma que um computador cientista ou um matemático ainda usa 929 00:34:16,320 --> 00:34:19,230 para descrever o tempo de execução de um algoritmo. 930 00:34:19,230 --> 00:34:21,400 Quantos passos ele realmente tomar? 931 00:34:21,400 --> 00:34:25,080 >> Agora eu vou me envergonhar com minha letra aqui em apenas um momento. 932 00:34:25,080 --> 00:34:29,020 Mas deixe-me ir em frente e dizer que isso vai ser grande por aqui ó. 933 00:34:29,020 --> 00:34:33,610 E deixe-me apresentar um outro símbolo, um omega capital. 934 00:34:33,610 --> 00:34:37,080 Omega vai ser o oposto, essencialmente, de grande O. Considerando que a grande O 935 00:34:37,080 --> 00:34:40,790 significa, no pior dos casos, a quantidade de tempo pode levar algum algoritmo, em 936 00:34:40,790 --> 00:34:43,480 termos de n, omega vai ser quanto tempo ela poderia 937 00:34:43,480 --> 00:34:45,409 tomar na melhor das hipóteses. 938 00:34:45,409 --> 00:34:48,090 E vamos ver o que se entende por melhor das hipóteses, em apenas um momento. 939 00:34:48,090 --> 00:34:49,940 >> Então, vamos começar algo simples. 940 00:34:49,940 --> 00:34:54,719 Deixe-me começar com uma busca linear. 941 00:34:54,719 --> 00:34:55,679 Portanto, não a classificação. 942 00:34:55,679 --> 00:34:58,000 Vamos chamar essa busca linear. 943 00:34:58,000 --> 00:35:01,140 E agora, fazer um pouco de mesa de fora dessa. 944 00:35:01,140 --> 00:35:06,600 E agora, no caso da pesquisa linear, no pior caso, quantos passos é 945 00:35:06,600 --> 00:35:11,770 ele vai me levar para encontrar uma número de escolha arbitrária? 946 00:35:11,770 --> 00:35:14,540 E há n portas totais ou n números totais. 947 00:35:14,540 --> 00:35:15,940 Pior caso. 948 00:35:15,940 --> 00:35:18,800 Quantos passos eu vou ter que tomar para encontrar o número 50 em uma matriz 949 00:35:18,800 --> 00:35:20,830 de n portas? 950 00:35:20,830 --> 00:35:21,410 E por quê? 951 00:35:21,410 --> 00:35:23,680 Porque ele pode ser tudo o caminho para o fim. 952 00:35:23,680 --> 00:35:27,120 Tanto como Jennifer encontrado, o número 50 foi todo o caminho, por isso, 953 00:35:27,120 --> 00:35:30,760 o pior busca linear caso é grande O de n, vamos dizer. 954 00:35:30,760 --> 00:35:33,430 >> E quanto melhor das hipóteses, se tiver muita sorte? 955 00:35:33,430 --> 00:35:36,200 Só vai dar um passo, ou um número constante de passos. 956 00:35:36,200 --> 00:35:37,830 Então, vamos descrever isso como um. 957 00:35:37,830 --> 00:35:39,010 Então, isso é muito bom. 958 00:35:39,010 --> 00:35:41,210 Agora, o que se fez alguma coisa como busca binária? 959 00:35:41,210 --> 00:35:43,860 960 00:35:43,860 --> 00:35:47,846 Pesquisa de modo binário, no pior caso, levou quanto tempo? 961 00:35:47,846 --> 00:35:49,250 >> [Interpondo VOZES] 962 00:35:49,250 --> 00:35:51,310 >> DAVID J. MALAN: Então, na verdade, eu ouvi em alguns lugares. 963 00:35:51,310 --> 00:35:56,390 Então, é realmente entrar n, mais ou menos, porque, como nós dividimos a lista ao meio 964 00:35:56,390 --> 00:36:00,730 novamente, e novamente, e novamente, somos capazes para encontrar, finalmente, o valor, 965 00:36:00,730 --> 00:36:04,750 se ele está lá, mas há uma pegadinha. 966 00:36:04,750 --> 00:36:08,590 Qual é a suposição de que nós temos que ter concedido para a busca binária? 967 00:36:08,590 --> 00:36:09,700 Tem que ser resolvido. 968 00:36:09,700 --> 00:36:12,770 Não está resolvido, você pode dividir a coisa ao meio de novo e de novo, e você 969 00:36:12,770 --> 00:36:15,490 pode ir para a esquerda, e você pode ir para a direita, e você pode ir para a esquerda e para a direita, mas você é 970 00:36:15,490 --> 00:36:18,070 não vai encontrar o elemento se a lista não está ordenada, porque 971 00:36:18,070 --> 00:36:18,790 você pode perdê-la. 972 00:36:18,790 --> 00:36:22,120 Porque a sua heurística, para ir à esquerda ou para a direita vai ser falho, se é 973 00:36:22,120 --> 00:36:23,420 na verdade, não classificados. 974 00:36:23,420 --> 00:36:26,110 Portanto, há uma espécie de custo oculto para usar algo assim. 975 00:36:26,110 --> 00:36:29,250 >> Agora, vamos para a nossa classificação algoritmos não busca - 976 00:36:29,250 --> 00:36:31,140 oh, realmente vamos entrar em branco. 977 00:36:31,140 --> 00:36:33,190 Busca binária na melhor das hipóteses? 978 00:36:33,190 --> 00:36:36,290 É também um caso só acontece de ser bem no meio da matriz, ou 979 00:36:36,290 --> 00:36:37,810 no meio da lista telefônica. 980 00:36:37,810 --> 00:36:39,710 Agora vamos fazer o bubble sort. 981 00:36:39,710 --> 00:36:42,570 Então, novamente, agora estamos entrando na tipos, e não as pesquisas. 982 00:36:42,570 --> 00:36:47,220 >> No pior dos casos, quantos passos que fizemos reivindicação bubble sort vai levar? 983 00:36:47,220 --> 00:36:48,410 n ao quadrado. 984 00:36:48,410 --> 00:36:49,200 Então eu vou tirar isso. 985 00:36:49,200 --> 00:36:51,710 Ooh, minha letra parece ainda pior quando está previsto que grande. 986 00:36:51,710 --> 00:36:52,510 Tudo bem. 987 00:36:52,510 --> 00:36:53,570 Então isso n ao quadrado. 988 00:36:53,570 --> 00:36:59,460 E, na melhor das hipóteses de bubble sort, quantos passos é que vai tomar? 989 00:36:59,460 --> 00:37:00,980 1, eu ouvi. 990 00:37:00,980 --> 00:37:01,760 >> COLUNA 1: n. 991 00:37:01,760 --> 00:37:03,286 >> DAVID J. MALAN: n, eu ouvi. 992 00:37:03,286 --> 00:37:04,200 >> COLUNA 1: 2. 993 00:37:04,200 --> 00:37:05,010 >> DAVID J. MALAN: 2, eu ouvi. 994 00:37:05,010 --> 00:37:06,670 Ouço 3? 995 00:37:06,670 --> 00:37:07,080 Tudo bem. 996 00:37:07,080 --> 00:37:11,390 Então eu ouvi 1, n, 2, mas vamos escolher para além de pelo menos a primeira dessas 997 00:37:11,390 --> 00:37:12,330 sugestões, 1. 998 00:37:12,330 --> 00:37:15,370 Não é um mau instinto, porque tipo de segue um padrão aqui. 999 00:37:15,370 --> 00:37:19,670 Mas se ele só tem um passo, como no mundo que eu poderia reclamar que a lista 1000 00:37:19,670 --> 00:37:22,900 é ordenada, porque se eu estou apenas permitida tomar um passo, quantos elementos 1001 00:37:22,900 --> 00:37:25,230 Na verdade, eu poderia verificar para ter certeza? 1002 00:37:25,230 --> 00:37:28,270 Bem, só um, o que significa que há n menos um elementos que poderiam estar fora de 1003 00:37:28,270 --> 00:37:31,310 ordem, e eu só vou na fé depois olhando para um elemento que o 1004 00:37:31,310 --> 00:37:31,850 coisa está classificada. 1005 00:37:31,850 --> 00:37:33,930 Então 1 não é correto aqui. 1006 00:37:33,930 --> 00:37:35,710 Assim, minimamente, quantos que eu tenho que olhar? 1007 00:37:35,710 --> 00:37:36,680 >> [Interpondo VOZES] 1008 00:37:36,680 --> 00:37:40,160 >> DAVID J. MALAN: n menos 1, ou realmente, n, porque eu preciso olhar para cada 1009 00:37:40,160 --> 00:37:42,190 elemento para certificar-se de que não está fora de ordem. 1010 00:37:42,190 --> 00:37:44,750 Mas, novamente, nós vamos resolver de onda nossa mãos em números menores e 1011 00:37:44,750 --> 00:37:47,100 supor que, à medida que n se torna grande, eles são desinteressante qualquer maneira. 1012 00:37:47,100 --> 00:37:48,380 Então, isso é bubble sort. 1013 00:37:48,380 --> 00:37:49,830 E agora, vamos fazer esses dois últimos. 1014 00:37:49,830 --> 00:37:53,520 Tipo de seleção, e depois vamos fazer ordenação por inserção. 1015 00:37:53,520 --> 00:37:57,160 E então vai explodir sua mente com algo muito 1016 00:37:57,160 --> 00:37:58,926 melhor do que todos estes. 1017 00:37:58,926 --> 00:38:00,410 Tudo bem. 1018 00:38:00,410 --> 00:38:04,700 >> Qual é o pior caso em execução momento da seleção tipo? 1019 00:38:04,700 --> 00:38:05,680 >> COLUNA 4: n ao quadrado. 1020 00:38:05,680 --> 00:38:06,710 >> DAVID J. MALAN: n quadrado, estou ouvindo. 1021 00:38:06,710 --> 00:38:09,790 Mas por que n ao quadrado, intuitivamente? 1022 00:38:09,790 --> 00:38:11,170 >> COLUNA 4: Porque nós só fiz isso. 1023 00:38:11,170 --> 00:38:12,260 >> DAVID J. MALAN: Porque nós só fiz isso. 1024 00:38:12,260 --> 00:38:12,550 OK. 1025 00:38:12,550 --> 00:38:13,380 Boa resposta. 1026 00:38:13,380 --> 00:38:16,660 Mas, intuitivamente, por que é a seleção tipo n ao quadrado? 1027 00:38:16,660 --> 00:38:18,980 O que temos que fazer uma e outra vez? 1028 00:38:18,980 --> 00:38:22,570 Tivemos que manter a digitalização através, são você o menor, é o 1029 00:38:22,570 --> 00:38:24,020 menor, é o menor. 1030 00:38:24,020 --> 00:38:27,480 E concedido, fomos capazes de tomar n passos, então n menos 1, então n menos 2. 1031 00:38:27,480 --> 00:38:30,700 Mas se você espécie de adicionar todos aqueles acima, ou levá-la na fé que eu adicionei 1032 00:38:30,700 --> 00:38:34,810 -los com antecedência, temos cerca de n quadrado menos alguns números menores. 1033 00:38:34,810 --> 00:38:36,730 Então, eu vou ligar para este n ao quadrado. 1034 00:38:36,730 --> 00:38:39,530 Mas, com a seleção de tipo no melhor caso, quantos passos é 1035 00:38:39,530 --> 00:38:40,632 vai me levar? 1036 00:38:40,632 --> 00:38:41,840 >> COLUNA 5: [inaudível] 1037 00:38:41,840 --> 00:38:44,350 >> DAVID J. MALAN: É, infelizmente, ainda n ao quadrado, certo? 1038 00:38:44,350 --> 00:38:49,590 Porque se eu estou selecionando o menor elemento, e tivemos sete pessoas aqui, 1039 00:38:49,590 --> 00:38:53,280 Eu só sei que, quando eu chegar ao muito final, que eu encontrei a menor 1040 00:38:53,280 --> 00:38:55,670 número, onde quer ela pode ter sido. 1041 00:38:55,670 --> 00:38:58,820 Mas como faço para encontrar o próximo menor número? 1042 00:38:58,820 --> 00:39:00,160 Eu tenho que fazer outra passagem. 1043 00:39:00,160 --> 00:39:04,810 Assim, no melhor dos casos, o que é o de entrada para a seleção tipo? 1044 00:39:04,810 --> 00:39:07,830 É uma lista já espécie, número um, número dois, número três, número quatro. 1045 00:39:07,830 --> 00:39:08,600 Mas eu sou um computador. 1046 00:39:08,600 --> 00:39:10,190 Eu só posso olhar para um coisa de cada vez. 1047 00:39:10,190 --> 00:39:12,465 Eu não posso classificar de dar um passo de volta como um ser humano e dizer: 1048 00:39:12,465 --> 00:39:14,030 ooh, isso parece correto. 1049 00:39:14,030 --> 00:39:17,580 >> Eu só posso julgar correto em seleção espécie, selecionando o 1050 00:39:17,580 --> 00:39:18,370 menor número. 1051 00:39:18,370 --> 00:39:21,390 Mas mesmo se eu encontrar o número um em primeiro lugar, se eu não sei mais nada sobre 1052 00:39:21,390 --> 00:39:24,460 os outros números, o que eu não faço, tudo o que eu sei que tenho sido entregue uma matriz 1053 00:39:24,460 --> 00:39:27,930 ou um conjunto de portas de trás, que são números, a única maneira que eu sei que um 1054 00:39:27,930 --> 00:39:28,680 foi a menor? 1055 00:39:28,680 --> 00:39:32,440 Se eu chegar até aqui e perceber, caramba, uma era de fato o menor. 1056 00:39:32,440 --> 00:39:34,870 >> Mas como faço para, então, determinar que dois é a próxima menor? 1057 00:39:34,870 --> 00:39:38,350 Ao fazer a mesma ineficiência uma e outra vez. 1058 00:39:38,350 --> 00:39:42,210 Então, finalmente, com a ordenação por inserção, como, na pior das hipóteses, 1059 00:39:42,210 --> 00:39:44,990 se dizemos que ele executa? 1060 00:39:44,990 --> 00:39:49,100 Ele também é n ao quadrado. 1061 00:39:49,100 --> 00:39:53,020 E que tal com o melhor caso? 1062 00:39:53,020 --> 00:39:56,282 Vamos deixar isso como um cliffhanger. 1063 00:39:56,282 --> 00:40:00,090 Vamos preencher esse vazio da próxima vez, mas primeiro deixe-me propor que 1064 00:40:00,090 --> 00:40:02,620 fundamentalmente fazer melhor do que tudo isso, certo? 1065 00:40:02,620 --> 00:40:05,220 >> Então, pense por si mesmo que a inserção tipo vai ser. 1066 00:40:05,220 --> 00:40:06,910 Bem, isso não era muito dramática, porque eu sou o único 1067 00:40:06,910 --> 00:40:08,970 que viu a mudança. 1068 00:40:08,970 --> 00:40:09,620 Uau. 1069 00:40:09,620 --> 00:40:10,420 OK. 1070 00:40:10,420 --> 00:40:12,615 Então aqui nós temos um pouco demonstração diferente. 1071 00:40:12,615 --> 00:40:16,580 Se eu aumentar o zoom aqui, você vai ver que em À esquerda temos bubble sort, no 1072 00:40:16,580 --> 00:40:20,740 meio temos a seleção de classificação, e em a extrema-direita, nós temos algo que 1073 00:40:20,740 --> 00:40:23,380 não olhei ainda chamado merge sort. 1074 00:40:23,380 --> 00:40:26,080 Mas considere o que temos sido fazendo aqui, até agora, hoje. 1075 00:40:26,080 --> 00:40:29,200 Quando Jennifer veio pela primeira vez em cima do palco, passamos a matriz de números 1076 00:40:29,200 --> 00:40:33,750 novamente, e novamente, com busca linear, e temos tempo de execução linear, grande o 1077 00:40:33,750 --> 00:40:35,100 de n, por assim dizer. 1078 00:40:35,100 --> 00:40:41,000 >> Quando consideramos agora a primeira semana de classe, quando tínhamos dividir e conquistar, 1079 00:40:41,000 --> 00:40:43,740 e nós tínhamos o livro de telefone lacrimejamento, e Jennifer, e nós coletivamente 1080 00:40:43,740 --> 00:40:47,500 alavancado esse insight fundamental, que era repetir-se uma e outra vez por 1081 00:40:47,500 --> 00:40:50,930 alguma forma de jogar fora, jogando fora, jogar fora, metade do problema, ou 1082 00:40:50,930 --> 00:40:55,320 Geralmente, dividindo-se um problema no meio, e depois tratando o pedaço menor de 1083 00:40:55,320 --> 00:40:59,630 o problema como conceitualmente equivalente para a outra, que de alguma forma fez 1084 00:40:59,630 --> 00:41:00,910 fundamentalmente melhor. 1085 00:41:00,910 --> 00:41:04,720 Mas com o bubble sort, com a seleção tipo, com ordenação por inserção, temos pode 1086 00:41:04,720 --> 00:41:06,560 nenhum desses insights que Jennifer fez. 1087 00:41:06,560 --> 00:41:10,220 Nós praticamente só andou para trás e diante de um grupo inteiro de vezes, e nós 1088 00:41:10,220 --> 00:41:12,650 coisas mexido um pouco, trocando por esta ordem, talvez 1089 00:41:12,650 --> 00:41:13,730 inserir ou selecionar. 1090 00:41:13,730 --> 00:41:16,950 Mas no final do dia, eu fiz um monte de andar desajeitado e para trás. 1091 00:41:16,950 --> 00:41:21,160 Nós não realmente aproveitar algo inteligente como Jennifer gostou dividindo 1092 00:41:21,160 --> 00:41:22,040 e conquistador. 1093 00:41:22,040 --> 00:41:25,620 >> Assim tipo fundir, pelo contrário, que não vai ver até a próxima semana, ele vai 1094 00:41:25,620 --> 00:41:29,540 para alavancar a idéia chave, dividindo de entrada e, em seguida, reduzir para metade e, em seguida 1095 00:41:29,540 --> 00:41:30,580 reduzir para metade, em seguida, reduzir para metade. 1096 00:41:30,580 --> 00:41:34,590 E, em cada iteração do loop de que, classificando a metade esquerda e à direita 1097 00:41:34,590 --> 00:41:38,200 de metade, em seguida, a metade esquerda da metade esquerda, ea metade direita da esquerda e, em seguida 1098 00:41:38,200 --> 00:41:40,990 a metade esquerda da metade direita, e a metade direita da metade direita. 1099 00:41:40,990 --> 00:41:42,840 E repetindo uma e outra vez. 1100 00:41:42,840 --> 00:41:46,170 >> Então, você vai ver isso visualmente, mas esta é o que nos espera na próxima semana. 1101 00:41:46,170 --> 00:41:49,760 E, em geral, quando pensamos um pouco pouco mais difícil em qualquer problema desse tipo. 1102 00:41:49,760 --> 00:41:52,435 1103 00:41:52,435 --> 00:41:57,970 Nós n ao quadrado do lado esquerdo, n quadrado no meio, e n 1104 00:41:57,970 --> 00:41:59,400 log n à direita. 1105 00:41:59,400 --> 00:42:00,590 Portanto, não há o suspense real. 1106 00:42:00,590 --> 00:42:02,040 Vemo-nos na segunda-feira. 1107 00:42:02,040 --> 00:42:05,163 >> [Aplausos]