1 00:00:00,000 --> 00:00:00,990 2 00:00:00,990 --> 00:00:02,970 >> [Música tocando] 3 00:00:02,970 --> 00:00:10,400 4 00:00:10,400 --> 00:00:12,550 >> David J. MALAN: Este é CS50. 5 00:00:12,550 --> 00:00:14,612 E este é o início da semana três. 6 00:00:14,612 --> 00:00:16,820 Então, nós temos um monte de emocionante coisas para cobrir hoje. 7 00:00:16,820 --> 00:00:20,160 Um monte de oportunidades para voluntários em cima do palco. 8 00:00:20,160 --> 00:00:22,780 E, finalmente, é hoje não sobre o código em tudo. 9 00:00:22,780 --> 00:00:24,820 Mas é sobre ideias e trata-se de algoritmos, 10 00:00:24,820 --> 00:00:28,420 e, na verdade, trazendo de volta alguns dos as lições aprendidas a partir da semana zero, 11 00:00:28,420 --> 00:00:31,910 onde recall, nós introduziu esta monstruosidade. 12 00:00:31,910 --> 00:00:33,880 E empréstimos inspiração desde que, para iniciar 13 00:00:33,880 --> 00:00:36,879 para resolver cada vez mais sofisticados problemas através de algoritmos. 14 00:00:36,879 --> 00:00:38,420 Mas, primeiro, um par de anúncios. 15 00:00:38,420 --> 00:00:42,020 Então um, se você gostaria de se juntar Funcionários e colegas de CS50 no almoço 16 00:00:42,020 --> 00:00:44,670 nesta sexta-feira, tanto aqui como no Cambridge, e em New Haven, 17 00:00:44,670 --> 00:00:48,060 visite por favor o curso de site, em que um URL pode ser encontrado. 18 00:00:48,060 --> 00:00:50,390 Palestra esta quarta-feira não estar aqui em Sanders. 19 00:00:50,390 --> 00:00:53,610 Vai ser on-line, de modo sintonizar no site da CS50, 20 00:00:53,610 --> 00:00:55,850 se aqui em Cambridge ou New Haven também. 21 00:00:55,850 --> 00:00:58,110 >> E, em seguida, ajustou dois problema já está em suas mãos. 22 00:00:58,110 --> 00:01:03,067 Se você ainda não mergulhou ainda, permita-me para oferecer a sugestão de palavras fortes 23 00:01:03,067 --> 00:01:05,150 que, especialmente agora, como o problema define antecipadamente, 24 00:01:05,150 --> 00:01:08,669 você realmente quer começar agora, se não borrifar um pouco no fim de semana ou antes 25 00:01:08,669 --> 00:01:10,710 quando pela primeira vez sair em Sextas-feiras, porque você vai 26 00:01:10,710 --> 00:01:14,380 descobrir que eles não são necessariamente ficando mais longos ou mais desafiador por 27 00:01:14,380 --> 00:01:14,950 SE. 28 00:01:14,950 --> 00:01:17,575 Eu acho que você vai descobrir que, em geral, eles tendem a levar mais ou menos 29 00:01:17,575 --> 00:01:18,892 em torno mesma quantidade de tempo. 30 00:01:18,892 --> 00:01:20,850 Mas é certamente depende no aluno, e 31 00:01:20,850 --> 00:01:22,880 depende da mentalidade com o qual você se aproxima dele. 32 00:01:22,880 --> 00:01:24,910 Mas, invariavelmente, você está indo para executar-se contra alguma parede, 33 00:01:24,910 --> 00:01:26,350 e você está indo bater algum bug, e você é apenas 34 00:01:26,350 --> 00:01:27,950 não vai ser capaz de superar isso em algum momento. 35 00:01:27,950 --> 00:01:31,380 E é muito valiosa para ser capaz se afastar, voltar no dia seguinte, 36 00:01:31,380 --> 00:01:35,286 ir para o horário de expediente, no pós CS50 Discutir ou similar, para começar realmente desbloqueado. 37 00:01:35,286 --> 00:01:36,160 Portanto, manter isso em mente. 38 00:01:36,160 --> 00:01:40,830 Começando mais cedo possível é a melhor coisa que você pode fazer. 39 00:01:40,830 --> 00:01:44,160 Então, aqui é onde nós começamos a classe, mais na semana zero. 40 00:01:44,160 --> 00:01:47,441 E podemos obter um voluntário aqui para me ajudar a encontrar microfones? 41 00:01:47,441 --> 00:01:47,940 ESTÁ BEM. 42 00:01:47,940 --> 00:01:48,900 Levantando-se já. 43 00:01:48,900 --> 00:01:50,080 Vamos lá para cima. 44 00:01:50,080 --> 00:01:53,707 Acho que é como ele vai funcionar. 45 00:01:53,707 --> 00:01:54,415 Qual o seu nome? 46 00:01:54,415 --> 00:01:55,570 ALAN ESTRADA: Alan Estrada. 47 00:01:55,570 --> 00:01:56,778 DAVID J. MALAN: Alan Estrada. 48 00:01:56,778 --> 00:01:57,910 Vamos lá para cima. 49 00:01:57,910 --> 00:01:58,619 Bom te conhecer. 50 00:01:58,619 --> 00:01:59,910 ALAN ESTRADA: Prazer em conhecê-lo. 51 00:01:59,910 --> 00:02:02,772 DAVID J. MALAN: E você estava aqui com a gente na semana zero, é claro. 52 00:02:02,772 --> 00:02:03,028 ALAN ESTRADA: eu era. 53 00:02:03,028 --> 00:02:03,160 Eu era. 54 00:02:03,160 --> 00:02:05,868 >> DAVID J. MALAN: Então você poderia ir em frente e encontrar para nós Mike Smith, 55 00:02:05,868 --> 00:02:08,639 tão rápido quanto você pode? 56 00:02:08,639 --> 00:02:10,639 Tão rápido quanto você puder. 57 00:02:10,639 --> 00:02:13,756 Literalmente rasgando o problema em metade do que você precisa. 58 00:02:13,756 --> 00:02:15,130 >> ALAN ESTRADA: Hum. 59 00:02:15,130 --> 00:02:17,380 DAVID J. MALAN: Literalmente rasgando o problema pela metade. 60 00:02:17,380 --> 00:02:20,210 61 00:02:20,210 --> 00:02:22,083 >> ALAN ESTRADA: Oh. 62 00:02:22,083 --> 00:02:22,583 Mm. 63 00:02:22,583 --> 00:02:23,300 Muito bem. 64 00:02:23,300 --> 00:02:23,700 >> DAVID J. MALAN: OK. 65 00:02:23,700 --> 00:02:24,200 Boa. 66 00:02:24,200 --> 00:02:24,701 Obrigado. 67 00:02:24,701 --> 00:02:25,700 ALAN ESTRADA: Muito bom. 68 00:02:25,700 --> 00:02:26,210 ESTÁ BEM. 69 00:02:26,210 --> 00:02:27,610 >> DAVID J. MALAN: E agora, você whittled para baixo 70 00:02:27,610 --> 00:02:29,320 a metade do tamanho do problema. 71 00:02:29,320 --> 00:02:31,267 Agora, estamos reduzidos a um quarto. 72 00:02:31,267 --> 00:02:33,475 Você está pagando a atenção para de que lado estamos mantendo? 73 00:02:33,475 --> 00:02:34,405 >> [RINDO] 74 00:02:34,405 --> 00:02:35,970 >> ALAN ESTRADA: Sim, eu penso-- 75 00:02:35,970 --> 00:02:37,594 >> DAVID J. MALAN: Qual seção estamos? 76 00:02:37,594 --> 00:02:39,150 ALAN ESTRADA: Silenciosos, então. 77 00:02:39,150 --> 00:02:39,941 >> DAVID J. MALAN: OK. 78 00:02:39,941 --> 00:02:42,810 Mas Mike Smith vai para ser depois Silenciosos. 79 00:02:42,810 --> 00:02:44,130 Assim-- 80 00:02:44,130 --> 00:02:48,180 >> [RINDO] 81 00:02:48,180 --> 00:02:48,742 >> Tudo certo. 82 00:02:48,742 --> 00:02:50,200 ALAN ESTRADA: Onde estamos procurando? 83 00:02:50,200 --> 00:02:52,049 DAVID J. MALAN: Mike Smith. 84 00:02:52,049 --> 00:02:53,090 ALAN ESTRADA: Mike Smith. 85 00:02:53,090 --> 00:02:54,760 DAVID J. MALAN: Agora, estamos em cirúrgico. 86 00:02:54,760 --> 00:02:57,840 Agora, os médicos. 87 00:02:57,840 --> 00:02:58,340 Agora-- 88 00:02:58,340 --> 00:02:59,856 >> ALAN ESTRADA: Let's- vamos com real. 89 00:02:59,856 --> 00:03:00,370 Real. 90 00:03:00,370 --> 00:03:00,970 >> DAVID J. MALAN: Real. 91 00:03:00,970 --> 00:03:01,470 ESTÁ BEM. 92 00:03:01,470 --> 00:03:03,700 Se você precisar de Real. 93 00:03:03,700 --> 00:03:05,250 Agora, o caminho que é Mike Smith? 94 00:03:05,250 --> 00:03:06,250 >> ALAN ESTRADA: Desta forma. 95 00:03:06,250 --> 00:03:07,333 >> DAVID J. MALAN: Que maneira? 96 00:03:07,333 --> 00:03:08,240 ALAN ESTRADA: Espere. 97 00:03:08,240 --> 00:03:08,790 M é-- certo? 98 00:03:08,790 --> 00:03:09,110 Começamos com-- 99 00:03:09,110 --> 00:03:10,090 >> DAVID J. MALAN: Yeah. 100 00:03:10,090 --> 00:03:10,650 Eles são deixados. 101 00:03:10,650 --> 00:03:11,430 Seu direito. 102 00:03:11,430 --> 00:03:11,710 >> ALAN ESTRADA: Yeah. 103 00:03:11,710 --> 00:03:13,126 >> DAVID J. MALAN: Então Mike está aqui. 104 00:03:13,126 --> 00:03:13,990 ALAN ESTRADA: O quê? 105 00:03:13,990 --> 00:03:14,665 >> [RINDO] 106 00:03:14,665 --> 00:03:17,365 107 00:03:17,365 --> 00:03:18,330 >> Mau exemplo, rapazes. 108 00:03:18,330 --> 00:03:18,830 Desculpe. 109 00:03:18,830 --> 00:03:21,610 DAVID J. MALAN: Isto vai ensinar você pular para fora de sua cadeira. 110 00:03:21,610 --> 00:03:22,318 >> ALAN ESTRADA: Oh. 111 00:03:22,318 --> 00:03:22,890 Oh. 112 00:03:22,890 --> 00:03:23,390 Entendi. 113 00:03:23,390 --> 00:03:24,670 Entendi. 114 00:03:24,670 --> 00:03:25,170 Oh. 115 00:03:25,170 --> 00:03:25,669 Oh. 116 00:03:25,669 --> 00:03:26,812 Isso é-- OK, eu tenho você. 117 00:03:26,812 --> 00:03:27,520 Smith aqui? 118 00:03:27,520 --> 00:03:28,894 >> DAVID J. MALAN: Smith, obrigado. 119 00:03:28,894 --> 00:03:30,535 Portanto, vou continuar olhando para cima Smith? 120 00:03:30,535 --> 00:03:30,790 >> ALAN ESTRADA: Ah, sim. 121 00:03:30,790 --> 00:03:31,340 Não não não. 122 00:03:31,340 --> 00:03:31,600 Ah não. 123 00:03:31,600 --> 00:03:31,940 Isto é meu. 124 00:03:31,940 --> 00:03:32,580 >> DAVID J. MALAN: Oh, você tem Smith. 125 00:03:32,580 --> 00:03:33,415 ESTÁ BEM. 126 00:03:33,415 --> 00:03:34,040 >> ALAN ESTRADA: Sim, eu Smith tem aqui. 127 00:03:34,040 --> 00:03:34,700 Desculpe, rapazes. 128 00:03:34,700 --> 00:03:35,860 Eu pensei que nós Michael-- Michael estava procurando. 129 00:03:35,860 --> 00:03:36,550 Desculpe. 130 00:03:36,550 --> 00:03:37,550 >> DAVID J. MALAN: É OK. 131 00:03:37,550 --> 00:03:39,950 Tudo bem, agora estamos em Paccini e Sons. 132 00:03:39,950 --> 00:03:41,242 >> ALAN ESTRADA: Paccini e filhos. 133 00:03:41,242 --> 00:03:43,158 DAVID J. MALAN: Só você e eu estamos em sobre este assunto. 134 00:03:43,158 --> 00:03:44,050 ESTÁ BEM. 135 00:03:44,050 --> 00:03:45,130 Encontre-nos Mike Smith. 136 00:03:45,130 --> 00:03:45,830 Smith. 137 00:03:45,830 --> 00:03:46,310 >> ALAN ESTRADA: Smith. 138 00:03:46,310 --> 00:03:46,750 >> DAVID J. MALAN: Smith. 139 00:03:46,750 --> 00:03:47,728 Estamos em R para lixo. 140 00:03:47,728 --> 00:03:48,644 ALAN ESTRADA: Péssima. 141 00:03:48,644 --> 00:03:50,096 Oh. 142 00:03:50,096 --> 00:03:52,480 Isso vai demorar um pouco. 143 00:03:52,480 --> 00:03:54,340 >> [RINDO] 144 00:03:54,340 --> 00:03:55,804 145 00:03:55,804 --> 00:03:56,720 DAVID J. MALAN: Shoes. 146 00:03:56,720 --> 00:03:58,080 Estamos em sapatos. 147 00:03:58,080 --> 00:04:00,210 >> ALAN ESTRADA: Agora estamos gonna-- 148 00:04:00,210 --> 00:04:01,105 >> DAVID J. MALAN: Nice. 149 00:04:01,105 --> 00:04:01,980 ALAN ESTRADA: Which-- 150 00:04:01,980 --> 00:04:03,620 [RINDO] 151 00:04:03,620 --> 00:04:05,440 Oh, isso é ótimo. 152 00:04:05,440 --> 00:04:06,910 [RINDO] 153 00:04:06,910 --> 00:04:08,380 154 00:04:08,380 --> 00:04:09,390 >> DAVID J. MALAN: É OK. 155 00:04:09,390 --> 00:04:11,365 >> ALAN ESTRADA: Oh, isso é bom. 156 00:04:11,365 --> 00:04:14,425 Eu não acho que eu vou ter amigos PSAT após este. 157 00:04:14,425 --> 00:04:15,300 DAVID J. MALAN: Good. 158 00:04:15,300 --> 00:04:16,078 Sporting. 159 00:04:16,078 --> 00:04:17,036 ALAN ESTRADA: Sporting. 160 00:04:17,036 --> 00:04:18,668 Hum, L, M, N, O, P. 161 00:04:18,668 --> 00:04:19,459 DAVID J. MALAN: OK. 162 00:04:19,459 --> 00:04:21,600 Então, vamos destruir o ao meio. 163 00:04:21,600 --> 00:04:22,270 Está certo. 164 00:04:22,270 --> 00:04:25,606 Isso acaba mal de qualquer maneira, porque Mike Smith não será nas páginas amarelas. 165 00:04:25,606 --> 00:04:26,430 >> ALAN ESTRADA: Aw. 166 00:04:26,430 --> 00:04:27,140 >> DAVID J. MALAN: Não, é OK. 167 00:04:27,140 --> 00:04:28,930 Mas vamos fingir que ele está nesta página. 168 00:04:28,930 --> 00:04:33,260 Então, agora, você talhou o problema para baixo a uma página, e encontramos Mike Smith. 169 00:04:33,260 --> 00:04:35,180 >> [CHEERING] 170 00:04:35,180 --> 00:04:35,757 171 00:04:35,757 --> 00:04:36,340 Tudo bem, obrigado. 172 00:04:36,340 --> 00:04:40,700 173 00:04:40,700 --> 00:04:41,200 ESTÁ BEM. 174 00:04:41,200 --> 00:04:43,646 Isso foi extraordinário. 175 00:04:43,646 --> 00:04:45,954 Mas ainda era mais rápido que busca linear, 176 00:04:45,954 --> 00:04:47,870 em que nós começamos no início do livro, 177 00:04:47,870 --> 00:04:51,210 e passamos o nosso caminho da esquerda para a direita, eventualmente, à procura de Mike Smith. 178 00:04:51,210 --> 00:04:53,540 E assim, se o livro de telefone tinha talvez 1.000 páginas, 179 00:04:53,540 --> 00:04:56,300 talvez teria levado nos 10 ou mais lágrimas página. 180 00:04:56,300 --> 00:04:59,380 >> Mas você pode ter alavancado tocou uma suposição 181 00:04:59,380 --> 00:05:03,602 durante toda a isso, o que é dizer que o livro de telefone com antecedência o que era? 182 00:05:03,602 --> 00:05:04,310 AUDIÊNCIA: Ordenado. 183 00:05:04,310 --> 00:05:05,000 DAVID J. MALAN: É classificada. 184 00:05:05,000 --> 00:05:05,160 Certo? 185 00:05:05,160 --> 00:05:07,909 É classificados em ordem alfabética, por isso, que todos esses nomes e números 186 00:05:07,909 --> 00:05:11,230 são classificadas a partir da de um para o Z de, e em ordem alfabética no meio. 187 00:05:11,230 --> 00:05:13,100 Mas hoje, nós agora pedir a questão, bem, 188 00:05:13,100 --> 00:05:16,170 como fez Verizon ou o telefone empresa obtê-lo naquele estado? 189 00:05:16,170 --> 00:05:19,560 >> Porque é uma coisa para alavancar essa suposição, e, portanto, 190 00:05:19,560 --> 00:05:22,570 resolver um problema com um algoritmo de forma mais eficiente. 191 00:05:22,570 --> 00:05:24,900 Mas nós nunca realmente pediu na semana zero, bem, 192 00:05:24,900 --> 00:05:27,790 quanto isso custou Verizon ou outra pessoa 193 00:05:27,790 --> 00:05:29,620 para obter essa lista telefônica na ordem de classificação? 194 00:05:29,620 --> 00:05:29,780 >> Certo? 195 00:05:29,780 --> 00:05:31,529 Não importa se olhando para cima Mike Smith 196 00:05:31,529 --> 00:05:35,190 é super rápido, se você leva um ano para classificar as páginas inicialmente. 197 00:05:35,190 --> 00:05:35,690 Certo? 198 00:05:35,690 --> 00:05:38,620 Você pode muito bem peneirar através de um livro de telefone ao acaso, 199 00:05:38,620 --> 00:05:40,690 se ele vai ser super caro para classificá-lo. 200 00:05:40,690 --> 00:05:42,350 Então, se nós podemos ter outro voluntário. 201 00:05:42,350 --> 00:05:46,350 Vamos dar uma olhada aqui em cima como nós might-- venha up-- como 202 00:05:46,350 --> 00:05:48,100 poderíamos ir sobre a classificação destes. 203 00:05:48,100 --> 00:05:51,990 >> E se, na verdade, poderia Jordan se juntar a nós aqui em cima no palco. 204 00:05:51,990 --> 00:05:55,100 Venha-se apenas por um momento. 205 00:05:55,100 --> 00:05:56,359 Qual o seu nome? 206 00:05:56,359 --> 00:05:57,150 CAROLINE: Caroline. 207 00:05:57,150 --> 00:05:58,691 DAVID J. MALAN: Caroline, vamos lá para cima. 208 00:05:58,691 --> 00:06:02,070 E você vai ser se juntou por mim e Jordão aqui. 209 00:06:02,070 --> 00:06:03,800 Caroline, obrigado. 210 00:06:03,800 --> 00:06:04,300 Tudo certo. 211 00:06:04,300 --> 00:06:08,330 Então o que temos aqui para Caroline tem 26 livros azuis 212 00:06:08,330 --> 00:06:10,747 FAS que utiliza para administrar certos exames finais. 213 00:06:10,747 --> 00:06:13,330 Estes estão ficando difíceis de encontrar, mas o que temos feito com antecedência 214 00:06:13,330 --> 00:06:15,800 é que nós colocamos o nome de alguém na parte da frente de cada uma delas, 215 00:06:15,800 --> 00:06:18,133 mas mantivemos-lo simples, em seguida, colocar para fora os nomes completos. 216 00:06:18,133 --> 00:06:22,720 Por isso, seria colocar a pessoa com o nome G, D, J, B, todo o caminho de A a Z, 217 00:06:22,720 --> 00:06:24,090 mas eles estão em ordem aleatória. 218 00:06:24,090 --> 00:06:26,890 E por isso, se você faria, falando seu caminho através do problema como você 219 00:06:26,890 --> 00:06:31,620 fazê-lo, você pode ir em frente e classificar estes para nós, de A a Z. 220 00:06:31,620 --> 00:06:34,070 >> AUDIÊNCIA: OK, então L é como, no meio. 221 00:06:34,070 --> 00:06:35,050 C está começando. 222 00:06:35,050 --> 00:06:42,410 B. J antes L. B, Q. 223 00:06:42,410 --> 00:06:45,140 >> DAVID J. MALAN: Mantenha essa pensou por um segundo. 224 00:06:45,140 --> 00:06:48,910 Porque de outra forma, esta é apenas interessante para você, eu, e Jordan. 225 00:06:48,910 --> 00:06:49,724 Aí vamos nós. 226 00:06:49,724 --> 00:06:50,640 AUDIÊNCIA: [inaudível]. 227 00:06:50,640 --> 00:06:57,299 R. 228 00:06:57,299 --> 00:06:58,090 DAVID J. MALAN: OK. 229 00:06:58,090 --> 00:06:59,310 O que você está fazendo? 230 00:06:59,310 --> 00:07:01,730 >> CAROLINE: M vem depois O. 231 00:07:01,730 --> 00:07:02,564 >> DAVID J. MALAN: OK. 232 00:07:02,564 --> 00:07:03,064 >> CAROLINE: O. 233 00:07:03,064 --> 00:07:04,120 DAVID J. MALAN: O, Bom. 234 00:07:04,120 --> 00:07:04,970 >> CAROLINE: E. 235 00:07:04,970 --> 00:07:06,730 >> DAVID J. MALAN: E, F. Sim. 236 00:07:06,730 --> 00:07:07,620 >> CAROLINE: T, U, V 237 00:07:07,620 --> 00:07:10,689 >> DAVID J. MALAN: V, T, U, V. Portanto, parece que você está making-- continuar. 238 00:07:10,689 --> 00:07:12,730 Parece que você está fazendo uma grande pilha aqui, 239 00:07:12,730 --> 00:07:13,910 e tipo de uma grande pilha de lá. 240 00:07:13,910 --> 00:07:16,230 Assim, a primeira metade do alfabeto, segunda metade do alfabeto. 241 00:07:16,230 --> 00:07:16,460 ESTÁ BEM. 242 00:07:16,460 --> 00:07:16,960 Boa. 243 00:07:16,960 --> 00:07:19,680 Tipo de dividir o problema em duas partes. 244 00:07:19,680 --> 00:07:21,771 M, N, X. Sim. 245 00:07:21,771 --> 00:07:22,270 CAROLINE: K. 246 00:07:22,270 --> 00:07:22,980 DAVID J. MALAN: OK. 247 00:07:22,980 --> 00:07:25,070 K. Então você está tipo de seleção -los um após o outro, 248 00:07:25,070 --> 00:07:27,620 colocá-lo para a esquerda ou direita, ou Z está acontecendo no chão. 249 00:07:27,620 --> 00:07:28,012 ESTÁ BEM. 250 00:07:28,012 --> 00:07:29,190 >> CAROLINE: Z está acontecendo no chão. 251 00:07:29,190 --> 00:07:29,360 >> DAVID J. MALAN: OK. 252 00:07:29,360 --> 00:07:30,920 Y está acontecendo no chão. 253 00:07:30,920 --> 00:07:31,735 Agora podemos colocar X. 254 00:07:31,735 --> 00:07:32,409 >> CAROLINE: G. 255 00:07:32,409 --> 00:07:33,700 DAVID J. MALAN: G de ir à esquerda. 256 00:07:33,700 --> 00:07:36,017 S está indo bem. 257 00:07:36,017 --> 00:07:37,642 Tudo bem, um está indo todo o caminho à esquerda. 258 00:07:37,642 --> 00:07:38,790 >> Caroline: A, B, C, D. 259 00:07:38,790 --> 00:07:39,873 >> DAVID J. MALAN: Agora, é bom. 260 00:07:39,873 --> 00:07:43,260 Temos A, B, C. W de ir lá em baixo. 261 00:07:43,260 --> 00:07:45,566 Tudo bem, T. 262 00:07:45,566 --> 00:07:46,611 >> CAROLINE: H, I, J. 263 00:07:46,611 --> 00:07:47,860 DAVID J. MALAN: H, I, J. Boa. 264 00:07:47,860 --> 00:07:49,160 CAROLINE: No centro, eu estou gonna-- 265 00:07:49,160 --> 00:07:50,000 DAVID J. MALAN: OK. 266 00:07:50,000 --> 00:07:52,375 Então, agora, vamos tipo de mesclar essas várias pilhas. 267 00:07:52,375 --> 00:08:00,730 Então, de A a C, então eu vejo D, e E, e F, e G, e H, I e agradável. 268 00:08:00,730 --> 00:08:05,540 J, K. E então, essa pilha é de cabeça para baixo, mas isso é OK. 269 00:08:05,540 --> 00:08:06,040 Certo. 270 00:08:06,040 --> 00:08:07,240 Podemos cortar alguns cantos. 271 00:08:07,240 --> 00:08:07,950 ESTÁ BEM. 272 00:08:07,950 --> 00:08:10,530 E então nós precisamos W, X, Y, Z. 273 00:08:10,530 --> 00:08:11,250 >> CAROLINE: Yeah. 274 00:08:11,250 --> 00:08:11,880 >> DAVID J. MALAN: Excelente. 275 00:08:11,880 --> 00:08:14,122 Assim, um grande obrigado a Caroline para classificar estes. 276 00:08:14,122 --> 00:08:15,030 >> [CHEERING] 277 00:08:15,030 --> 00:08:17,287 >> Obrigado. 278 00:08:17,287 --> 00:08:18,120 Muito obrigado. 279 00:08:18,120 --> 00:08:22,910 Então agora vamos considerar por um momento como Caroline passou fazendo o que, 280 00:08:22,910 --> 00:08:26,040 e exatamente o que nós foram capazes a-- como nós 281 00:08:26,040 --> 00:08:28,409 foram capazes de resolver esse problema quando estávamos apenas 282 00:08:28,409 --> 00:08:29,950 dado um monte de entradas aleatórias. 283 00:08:29,950 --> 00:08:31,610 >> Bem, parece que há foi um pouco de um sistema de lá? 284 00:08:31,610 --> 00:08:32,110 Certo. 285 00:08:32,110 --> 00:08:34,495 Assim, as primeiras cartas no alfabeto, ela 286 00:08:34,495 --> 00:08:37,120 era colocar à esquerda, eo cartas posteriores no alfabeto, 287 00:08:37,120 --> 00:08:38,270 ela estava colocando para a direita. 288 00:08:38,270 --> 00:08:40,500 E assim que ela encontrou algumas cartas proximais, queridos 289 00:08:40,500 --> 00:08:43,124 que vá para a direita ao lado do outro, ela iria colocá-los em ordem. 290 00:08:43,124 --> 00:08:46,750 E então nós meio que tinha estes pequenos pilhas de entradas ordenadas ocorrendo. 291 00:08:46,750 --> 00:08:50,540 >> E assim que é bastante parecido com o que a maioria de nós seres humanos faria. 292 00:08:50,540 --> 00:08:53,530 Gostaríamos espécie de peneirar, e nós meio que temos um mecanismo. 293 00:08:53,530 --> 00:08:56,930 Mas pode ser difícil de escrever -o para baixo em uma fórmula de per si. 294 00:08:56,930 --> 00:08:59,010 Ele Senti um pouco mais orgânico do que isso. 295 00:08:59,010 --> 00:09:02,560 Então, vamos ver se podemos agora ligado O problema com o menor número de entradas. 296 00:09:02,560 --> 00:09:05,170 >> Em vez de 26, vamos fazer algo muito menos 297 00:09:05,170 --> 00:09:09,890 com apenas dizer, sete, atrás estas portas, por assim dizer. 298 00:09:09,890 --> 00:09:11,300 Há apenas sete números? 299 00:09:11,300 --> 00:09:15,240 E se o objetivo agora em mão é encontrar um valor, 300 00:09:15,240 --> 00:09:17,850 vamos ver o quão eficiente nós podemos fazer sobre este assunto. 301 00:09:17,850 --> 00:09:22,460 E vamos ver se podemos agora começar a aplicar alguns números, 302 00:09:22,460 --> 00:09:26,310 ou algumas fórmulas com as quais para descrever a eficiência do nosso livro de telefone 303 00:09:26,310 --> 00:09:31,060 algoritmo, nosso algoritmo livro exame, e de modo mais geral, busca de informações. 304 00:09:31,060 --> 00:09:34,770 >> Então, para isso, deixe-me ir em frente, e na tela de toque aqui, 305 00:09:34,770 --> 00:09:41,100 colocar um navegador web que tem exatamente esses sete portas. 306 00:09:41,100 --> 00:09:46,670 E se nós pudéssemos adquirir um outro voluntariar para vir até aqui, 307 00:09:46,670 --> 00:09:48,480 Eu coloquei essas mesmas portas por aqui. 308 00:09:48,480 --> 00:09:49,170 Voluntário rápido. 309 00:09:49,170 --> 00:09:51,130 >> Este um-- demos vão a uma mais rápida e mais rápido agora. 310 00:09:51,130 --> 00:09:51,600 Vamos lá para baixo. 311 00:09:51,600 --> 00:09:52,308 Qual o seu nome? 312 00:09:52,308 --> 00:09:53,040 TREVOR: Trevor. 313 00:09:53,040 --> 00:09:53,998 >> DAVID J. MALAN: Trevor? 314 00:09:53,998 --> 00:09:55,770 Tudo bem, Trevor, vamos lá para baixo. 315 00:09:55,770 --> 00:09:59,212 Então Trevor se ofereceu aqui para fazer um problema semelhante, mas um que é 316 00:09:59,212 --> 00:10:02,170 de âmbito mais restrito, e que está acontecendo para permitir-nos para tentar formalizar agora 317 00:10:02,170 --> 00:10:03,970 o processo de triagem de esses números. 318 00:10:03,970 --> 00:10:05,500 >> Então Trevor, prazer em conhecê-lo. 319 00:10:05,500 --> 00:10:08,720 Então aqui é uma matriz, por assim falar, uma lista de sete portas. 320 00:10:08,720 --> 00:10:10,327 Vá em frente e encontrar-nos no número 50. 321 00:10:10,327 --> 00:10:12,410 E, em seguida, após o fato, diga-nos como você o encontrou. 322 00:10:12,410 --> 00:10:19,124 323 00:10:19,124 --> 00:10:20,040 Deve ser-- tudo bem. 324 00:10:20,040 --> 00:10:21,945 Sim, este é o único aqui? 325 00:10:21,945 --> 00:10:24,680 Uh oh. 326 00:10:24,680 --> 00:10:25,560 ESTÁ BEM. 327 00:10:25,560 --> 00:10:26,680 Você clicou essa. 328 00:10:26,680 --> 00:10:28,690 Boa. 329 00:10:28,690 --> 00:10:29,780 >> E bom. 330 00:10:29,780 --> 00:10:30,970 Agora você clicou essa. 331 00:10:30,970 --> 00:10:34,060 E deixe-me dar-lhe o microfone, de modo que você tê-lo em apenas um momento. 332 00:10:34,060 --> 00:10:37,000 Vá em frente e clique no ao lado que você pretende. 333 00:10:37,000 --> 00:10:39,812 Sim bom. 334 00:10:39,812 --> 00:10:41,020 TREVOR: Posso desmarque a porta? 335 00:10:41,020 --> 00:10:42,620 DAVID J. MALAN: Não, você não pode desmarque. 336 00:10:42,620 --> 00:10:43,119 TREVOR: OK. 337 00:10:43,119 --> 00:10:43,974 Este. 338 00:10:43,974 --> 00:10:45,640 DAVID J. MALAN: Onde você quer ir? 339 00:10:45,640 --> 00:10:46,410 Qual? 340 00:10:46,410 --> 00:10:47,230 >> TREVOR: Que um. 341 00:10:47,230 --> 00:10:48,042 >> DAVID J. MALAN: Não. 342 00:10:48,042 --> 00:10:48,450 >> TREVOR: OK. 343 00:10:48,450 --> 00:10:48,735 Este. 344 00:10:48,735 --> 00:10:49,020 >> DAVID J. MALAN: Sim. 345 00:10:49,020 --> 00:10:49,700 Isso foi bom. 346 00:10:49,700 --> 00:10:50,380 Tudo certo. 347 00:10:50,380 --> 00:10:53,900 Então, qual foi o seu algoritmo ou procedimento para fazer isso, Trevor? 348 00:10:53,900 --> 00:10:56,149 >> TREVOR: Eu só passei portas até que eu encontrei a 50. 349 00:10:56,149 --> 00:10:56,940 DAVID J. MALAN: OK. 350 00:10:56,940 --> 00:10:58,150 Excelente algoritmo. 351 00:10:58,150 --> 00:10:59,540 Então, isso é bom. 352 00:10:59,540 --> 00:11:03,120 Porque, na verdade, se eu revelar o que é por trás dessas duas outras portas, o que 353 00:11:03,120 --> 00:11:06,954 vamos encontrar aqui é que só temos entrada aleatória. 354 00:11:06,954 --> 00:11:08,870 Então isso foi realmente como bem como se poderia obter. 355 00:11:08,870 --> 00:11:12,509 E, na verdade, você tem melhor do que exaustivamente buscando todo o conjunto, 356 00:11:12,509 --> 00:11:15,300 porque ele teria sido realmente azarado se tivesse atingido o número 357 00:11:15,300 --> 00:11:16,604 50 no último porta. 358 00:11:16,604 --> 00:11:18,520 Mas o que se em vez deu-lhe uma hipótese. 359 00:11:18,520 --> 00:11:20,630 Suponha que eu classifico todos estas portas ao redor, 360 00:11:20,630 --> 00:11:23,500 de modo que você tem a números classificados este tempo, 361 00:11:23,500 --> 00:11:29,730 mas desta vez é realmente um diferente-- este tempo, 362 00:11:29,730 --> 00:11:32,640 ele é realmente classificadas para você. 363 00:11:32,640 --> 00:11:35,380 E agora a meta na mão é atingir o número de 50. 364 00:11:35,380 --> 00:11:36,090 >> TREVOR: OK. 365 00:11:36,090 --> 00:11:37,670 >> DAVID J. MALAN: Qual é seu algoritmo vai ser? 366 00:11:37,670 --> 00:11:39,628 >> TREVOR: Bem, se é classificadas, é qualquer um que vai 367 00:11:39,628 --> 00:11:42,710 para ser-- se maior para o maior, descendente, vai ser o primeiro, 368 00:11:42,710 --> 00:11:44,751 ou se é o contrário, será a última. 369 00:11:44,751 --> 00:11:48,897 Então só vou tocar esta porta, e em seguida, basta tocar a última porta. 370 00:11:48,897 --> 00:11:49,980 DAVID J. MALAN: Excelente. 371 00:11:49,980 --> 00:11:50,270 Tudo certo. 372 00:11:50,270 --> 00:11:51,150 Assim, encontramos o número 50. 373 00:11:51,150 --> 00:11:52,970 Assim, logo que você soubesse eles foram ordenados, nós 374 00:11:52,970 --> 00:11:55,040 foram capazes de aproveitar essa suposição. 375 00:11:55,040 --> 00:11:57,040 Então, eles estão muito parecido a exemplo do livro de telefone. 376 00:11:57,040 --> 00:11:59,540 Assim que você tem, mesmo com um pequeno problema como este, 377 00:11:59,540 --> 00:12:02,380 suas entradas pré-classificados, nós podemos realmente encontrar o valor indiscutivelmente 378 00:12:02,380 --> 00:12:03,130 mais eficientemente. 379 00:12:03,130 --> 00:12:05,800 >> E eu não lhe disse se era classificadas pequeno a grande, ou grande a pequeno, 380 00:12:05,800 --> 00:12:08,080 e por isso era muito razoável para começar em uma extremidade ou outro 381 00:12:08,080 --> 00:12:09,750 para realmente encontrar esse valor-alvo. 382 00:12:09,750 --> 00:12:11,400 Por isso, agradeço ao Trevor também. 383 00:12:11,400 --> 00:12:13,260 E eu vou propose-- bem feito. 384 00:12:13,260 --> 00:12:16,960 Temos um pequeno clip, na verdade, que está entre os nossos momentos favoritos em CS50, 385 00:12:16,960 --> 00:12:19,700 pelo que, por vezes, estas demonstrações não chegam a ir de acordo com o plano. 386 00:12:19,700 --> 00:12:22,050 E, de fato agora, eu puxou a interface errada 387 00:12:22,050 --> 00:12:23,508 com que usar a tela sensível ao toque. 388 00:12:23,508 --> 00:12:24,660 Então isso foi culpa minha lá. 389 00:12:24,660 --> 00:12:26,600 >> Então, isso vai fazer para clipe do próximo ano como 390 00:12:26,600 --> 00:12:28,570 a razão pela qual eu estava clicando no meu próprio ecrã. 391 00:12:28,570 --> 00:12:31,390 Mas vamos dar uma olhada rápida para o que aconteceu no ano passado 392 00:12:31,390 --> 00:12:34,770 com Jay, que surgiu, muito como Trevor aqui, ofereceu-se, 393 00:12:34,770 --> 00:12:39,380 e neste clipe curto, você verá como esta mesma demonstração não fez muito 394 00:12:39,380 --> 00:12:41,074 revelar as mesmas lições aprendidas. 395 00:12:41,074 --> 00:12:41,740 [REPRODUÇÃO DE VÍDEO] 396 00:12:41,740 --> 00:12:45,360 -Tudo Que eu quero que você faça agora é para encontrar para mim, e para nós, 397 00:12:45,360 --> 00:12:51,674 realmente, o número 50 um passo de cada vez. 398 00:12:51,674 --> 00:12:52,450 >> -O Número 50? 399 00:12:52,450 --> 00:12:53,190 >> -O Número 50. 400 00:12:53,190 --> 00:12:55,356 E você pode revelar o que é por trás de cada uma destas portas 401 00:12:55,356 --> 00:12:58,540 simplesmente por tocar com um dedo. 402 00:12:58,540 --> 00:13:00,910 Caramba. 403 00:13:00,910 --> 00:13:02,870 >> [RINDO] 404 00:13:02,870 --> 00:13:03,806 >> [FIM DE REPRODUÇÃO] 405 00:13:03,806 --> 00:13:05,430 DAVID J. MALAN: Assim que correu muito bem. 406 00:13:05,430 --> 00:13:06,796 Essas foram as portas não triados. 407 00:13:06,796 --> 00:13:08,670 E Jay, é claro, achei tudo muito rapidamente. 408 00:13:08,670 --> 00:13:12,910 Trevor fez um trabalho muito melhor em termos de um momento de aprendizado, 409 00:13:12,910 --> 00:13:15,850 por assim dizer, este ano, em levando mais tempo para encontrá-lo. 410 00:13:15,850 --> 00:13:17,950 É claro, então nós demos Jay uma segunda chance, 411 00:13:17,950 --> 00:13:20,320 pelo qual nós ordenamos as portas, assim como fizemos para o Trevor, 412 00:13:20,320 --> 00:13:22,300 e Trevor fez super-bem desta vez. 413 00:13:22,300 --> 00:13:26,124 Mas Jay fez metade tão rapidamente. 414 00:13:26,124 --> 00:13:26,790 [REPRODUÇÃO DE VÍDEO] 415 00:13:26,790 --> 00:13:29,650 -O Objetivo agora é também encontrar-nos no número 50, 416 00:13:29,650 --> 00:13:33,030 mas fazê-lo através de algoritmos, e diga-nos como você está indo sobre ele. 417 00:13:33,030 --> 00:13:33,660 >> -ESTÁ BEM. 418 00:13:33,660 --> 00:13:35,604 >> -E Se você encontrá-lo, mantenha o filme. 419 00:13:35,604 --> 00:13:37,228 Se você não encontrá-lo, você dá-lo de volta. 420 00:13:37,228 --> 00:13:38,044 >> -Cara. 421 00:13:38,044 --> 00:13:38,860 >> -Oh! 422 00:13:38,860 --> 00:13:40,800 >> - [Inaudível] OK. 423 00:13:40,800 --> 00:13:46,236 Então, eu estou indo para verificar as extremidades primeiro para determinar se there's-- Oh. 424 00:13:46,236 --> 00:13:48,646 >> [Aplausos] 425 00:13:48,646 --> 00:13:53,948 426 00:13:53,948 --> 00:13:55,729 >> [FIM DE REPRODUÇÃO] 427 00:13:55,729 --> 00:13:56,520 DAVID J. MALAN: OK. 428 00:13:56,520 --> 00:13:59,760 Então triagem portas claramente conduz a uma maior eficiência. 429 00:13:59,760 --> 00:14:01,680 E assim, duas vezes mais rápido é o que eu quis dizer lá. 430 00:14:01,680 --> 00:14:03,270 E assim Jay teve sorte duas vezes. 431 00:14:03,270 --> 00:14:06,685 E ele também teve sorte naquela última ano, eu pedi alguns discos Blu-ray 432 00:14:06,685 --> 00:14:07,560 para realmente dar para fora. 433 00:14:07,560 --> 00:14:09,768 Sinto muito este ano, não têm o mesmo, Trevor. 434 00:14:09,768 --> 00:14:11,540 Mas melhor ainda era alguns anos atrás. 435 00:14:11,540 --> 00:14:14,820 E alguns de vocês podem saber isso companheiro, Sean, que quando ele estava na CS50, 436 00:14:14,820 --> 00:14:17,780 foi desafiado com a exata mesmo problema, embora em SD, 437 00:14:17,780 --> 00:14:19,360 como você verá em breve, de volta ao dia. 438 00:14:19,360 --> 00:14:22,622 E você vai descobrir que não só ele demorar um pouco mais do que Jay, 439 00:14:22,622 --> 00:14:25,580 um pouco mais do que Trevor, foi realmente esta oportunidade maravilhosa 440 00:14:25,580 --> 00:14:29,820 se envolver quase todos no multidão a la Preço Certo, incentivando 441 00:14:29,820 --> 00:14:31,889 -lo a encontrar o número que estávamos procurando. 442 00:14:31,889 --> 00:14:32,930 Vamos. dar uma olhada rápida. 443 00:14:32,930 --> 00:14:33,320 >> [REPRODUÇÃO DE VÍDEO] 444 00:14:33,320 --> 00:14:33,820 >> -ESTÁ BEM. 445 00:14:33,820 --> 00:14:36,680 Portanto, sua tarefa aqui, Sean, é o seguinte. 446 00:14:36,680 --> 00:14:40,860 Eu ter escondido por trás dessas portas o número sete. 447 00:14:40,860 --> 00:14:45,120 Mas afastada, em algumas dessas portas bem como outros são números negativos. 448 00:14:45,120 --> 00:14:47,500 E seu objetivo é pensar desta linha superior de números 449 00:14:47,500 --> 00:14:50,390 como apenas uma matriz, ou apenas sequência de pedaços de papel 450 00:14:50,390 --> 00:14:51,510 com números por trás deles. 451 00:14:51,510 --> 00:14:55,540 E seu objetivo é, usando apenas o topo matriz aqui, encontrar-me o número sete. 452 00:14:55,540 --> 00:14:58,570 E nós estamos indo então para criticar como você vai fazer sobre isso. 453 00:14:58,570 --> 00:14:59,070 -Tudo certo. 454 00:14:59,070 --> 00:15:00,850 -Find-Nos o número sete, por favor. 455 00:15:00,850 --> 00:15:10,500 456 00:15:10,500 --> 00:15:11,000 Não. 457 00:15:11,000 --> 00:15:15,050 458 00:15:15,050 --> 00:15:18,550 Cinco, 19, 13. 459 00:15:18,550 --> 00:15:22,240 460 00:15:22,240 --> 00:15:24,770 >> [RINDO] 461 00:15:24,770 --> 00:15:25,910 >> Não é uma pergunta capciosa. 462 00:15:25,910 --> 00:15:29,410 463 00:15:29,410 --> 00:15:29,910 Uma. 464 00:15:29,910 --> 00:15:33,218 465 00:15:33,218 --> 00:15:34,695 >> [RINDO] 466 00:15:34,695 --> 00:15:37,861 Neste ponto, sua pontuação não é muito bom, então você pode muito bem continuar. 467 00:15:37,861 --> 00:15:40,610 468 00:15:40,610 --> 00:15:41,110 Três. 469 00:15:41,110 --> 00:15:43,890 470 00:15:43,890 --> 00:15:45,378 >> [RINDO] 471 00:15:45,378 --> 00:15:46,370 472 00:15:46,370 --> 00:15:47,774 >> Continue. 473 00:15:47,774 --> 00:15:50,690 Francamente, eu não posso ajudar, mas pergunto o que você está mesmo pensando, assim-- 474 00:15:50,690 --> 00:15:51,959 >> [RINDO] 475 00:15:51,959 --> 00:15:53,229 476 00:15:53,229 --> 00:15:55,020 Apenas a linha superior, de modo você tem três esquerda. 477 00:15:55,020 --> 00:15:56,200 Então, encontrar-me sete. 478 00:15:56,200 --> 00:15:59,700 479 00:15:59,700 --> 00:16:02,167 >> [RINDO] 480 00:16:02,167 --> 00:16:14,870 481 00:16:14,870 --> 00:16:15,370 17. 482 00:16:15,370 --> 00:16:25,675 483 00:16:25,675 --> 00:16:26,946 Sete. 484 00:16:26,946 --> 00:16:28,780 >> [Aplausos] 485 00:16:28,780 --> 00:16:29,426 >> Tudo certo. 486 00:16:29,426 --> 00:16:30,360 >> [FIM DE REPRODUÇÃO] 487 00:16:30,360 --> 00:16:31,840 >> DAVID J. MALAN: para que pudéssemos assistir a esses todo o dia. 488 00:16:31,840 --> 00:16:34,090 E, claro, alguns dos demos deste ano talvez 489 00:16:34,090 --> 00:16:36,330 agora vai acabar no próximo vídeo do ano também. 490 00:16:36,330 --> 00:16:39,040 Então agora vamos realmente focar os algoritmos 491 00:16:39,040 --> 00:16:42,140 aqui, e ver se nós não podemos agora começar a formalizar 492 00:16:42,140 --> 00:16:46,650 como podemos ir sobre a obtenção de nossos dados a este estado que está classificado, 493 00:16:46,650 --> 00:16:50,054 de modo que, em última análise, podemos, na verdade, procurá-la de modo mais eficiente. 494 00:16:50,054 --> 00:16:52,470 E mesmo que nós vamos usar conjuntos de dados relativamente pequeno, 495 00:16:52,470 --> 00:16:54,511 como a que oito números temos aqui no quadro, 496 00:16:54,511 --> 00:16:58,230 em última análise, poderia aplicar essas mesmas idéias 1.000 entradas, um milhão de entradas, 497 00:16:58,230 --> 00:17:02,100 4 bilhões de insumos, porque os algoritmos vão ser fundamentalmente o mesmo. 498 00:17:02,100 --> 00:17:05,359 >> E assim, este é o nosso último oportunidade para os voluntários de hoje, 499 00:17:05,359 --> 00:17:09,790 mas talvez o mais envolvido, para o qual precisamos oito voluntários 500 00:17:09,790 --> 00:17:12,960 para subir e pé-nos através do processo de triagem que será em breve 501 00:17:12,960 --> 00:17:15,212 ser sobre estes stands de música aqui. 502 00:17:15,212 --> 00:17:16,170 Deixe-me começar a voltar aqui. 503 00:17:16,170 --> 00:17:19,692 >> Então, um no verde turquoise-- é? 504 00:17:19,692 --> 00:17:21,130 Você está cometendo? 505 00:17:21,130 --> 00:17:21,630 Dois. 506 00:17:21,630 --> 00:17:23,069 Vamos lá para baixo. 507 00:17:23,069 --> 00:17:23,569 ESTÁ BEM. 508 00:17:23,569 --> 00:17:24,420 Três. 509 00:17:24,420 --> 00:17:25,400 Four. 510 00:17:25,400 --> 00:17:27,247 Vamos me-- OK, cinco. 511 00:17:27,247 --> 00:17:28,830 Você está sendo nomeado por seu amigo. 512 00:17:28,830 --> 00:17:31,340 Seis, sete, e oito. 513 00:17:31,340 --> 00:17:32,130 Vamos lá para cima. 514 00:17:32,130 --> 00:17:32,630 Tudo certo. 515 00:17:32,630 --> 00:17:33,190 Muito obrigada. 516 00:17:33,190 --> 00:17:33,689 Vamos lá para cima. 517 00:17:33,689 --> 00:17:34,790 Vamos lá para cima. 518 00:17:34,790 --> 00:17:35,330 >> Tudo certo. 519 00:17:35,330 --> 00:17:38,890 Então o que temos e isso aqui-- está entre os mais desajeitados, 520 00:17:38,890 --> 00:17:42,390 uma vez que este vai exigir que você humor Minha apenas um pouco de tempo. 521 00:17:42,390 --> 00:17:43,442 Você deve ser o número um. 522 00:17:43,442 --> 00:17:44,150 Qual o seu nome? 523 00:17:44,150 --> 00:17:44,610 >> ANNAN: Annan. 524 00:17:44,610 --> 00:17:45,526 >> DAVID J. MALAN: Annan. 525 00:17:45,526 --> 00:17:46,092 David. 526 00:17:46,092 --> 00:17:46,800 Qual o seu nome? 527 00:17:46,800 --> 00:17:47,140 >> JOSÉ: José. 528 00:17:47,140 --> 00:17:49,190 >> DAVID J. MALAN: Joseph, você é o número dois. 529 00:17:49,190 --> 00:17:52,260 >> SERENA: Serena, número três. 530 00:17:52,260 --> 00:17:53,722 Stefan, o número quatro. 531 00:17:53,722 --> 00:17:54,430 CYNTHIA: Cynthia. 532 00:17:54,430 --> 00:17:57,548 DAVID J. MALAN: Cynthia, número cinco. 533 00:17:57,548 --> 00:17:58,452 [Inaudível] 534 00:17:58,452 --> 00:17:59,618 DAVID J. MALAN: [inaudível]. 535 00:17:59,618 --> 00:18:00,391 David, número seis. 536 00:18:00,391 --> 00:18:00,890 MATT: Matt. 537 00:18:00,890 --> 00:18:02,160 DAVID J. MALAN: número de Matt sete. 538 00:18:02,160 --> 00:18:02,850 E? 539 00:18:02,850 --> 00:18:03,210 >> WAVERLY: Waverly. 540 00:18:03,210 --> 00:18:04,470 >> DAVID J. MALAN: Waverly, número oito. 541 00:18:04,470 --> 00:18:04,970 Tudo certo. 542 00:18:04,970 --> 00:18:06,510 Se você could-- gritos. 543 00:18:06,510 --> 00:18:08,820 Se você tudo, como seu primeiro desafio, há 544 00:18:08,820 --> 00:18:10,820 São oito estantes de música aqui de frente para a platéia. 545 00:18:10,820 --> 00:18:14,200 Se você pudesse colocar seus números no estes suportes de música de tal maneira 546 00:18:14,200 --> 00:18:16,560 que eles se alinham com o mesmos números no quadro. 547 00:18:16,560 --> 00:18:19,560 Então, faça-se olhar como que por colocando os seus números sobre estes música 548 00:18:19,560 --> 00:18:21,960 fica aqui. 549 00:18:21,960 --> 00:18:25,980 Excelente até agora. 550 00:18:25,980 --> 00:18:26,600 >> Excelente. 551 00:18:26,600 --> 00:18:26,890 ESTÁ BEM. 552 00:18:26,890 --> 00:18:29,556 Então, agora, vamos pedir ao questão em algumas maneiras diferentes. 553 00:18:29,556 --> 00:18:31,610 Como podemos ir sobre como classificar essas pessoas aqui em cima? 554 00:18:31,610 --> 00:18:34,500 Porque nós tivemos algumas abordagens anteriormente, em que estávamos 555 00:18:34,500 --> 00:18:36,360 tipo de tomada de dois baldes diferentes. 556 00:18:36,360 --> 00:18:38,842 E então nós geralmente remendar as coisas juntos. 557 00:18:38,842 --> 00:18:41,050 Assim que viu dois números que pertencia juntos, 558 00:18:41,050 --> 00:18:41,975 nós colocá-los juntos. 559 00:18:41,975 --> 00:18:43,350 Duas cartas que pertencem juntos. 560 00:18:43,350 --> 00:18:45,058 >> Mas vamos ver se nós Não é possível formalizar isso, 561 00:18:45,058 --> 00:18:48,044 para que possamos, finalmente, ter alguns pseudo-código que você vai, 562 00:18:48,044 --> 00:18:49,710 com o qual você pode resolver estes problemas. 563 00:18:49,710 --> 00:18:51,870 Então, agora, eu estou olhando para fora esses números aqui. 564 00:18:51,870 --> 00:18:55,030 E eu vejo um monte de erros. 565 00:18:55,030 --> 00:18:57,750 Em última análise, eu quero um no à esquerda e oito à direita. 566 00:18:57,750 --> 00:19:00,650 >> E então eu estou olhando estes dois, quatro e dois. 567 00:19:00,650 --> 00:19:02,930 E qual é o problema, obviamente? 568 00:19:02,930 --> 00:19:04,261 Sim. 569 00:19:04,261 --> 00:19:04,760 Assim. 570 00:19:04,760 --> 00:19:07,160 Dois, obviamente, vem antes quatro, então você sabe o quê? 571 00:19:07,160 --> 00:19:10,210 Deixe-me primeiro dar uma abordagem gulosa, se você, como muito problema 572 00:19:10,210 --> 00:19:13,790 um-- definir se você se lembra do Standard Edition do Conjunto de Problemas One, 573 00:19:13,790 --> 00:19:16,820 onde eu apenas localmente resolver o problema que está bem aqui na minha frente 574 00:19:16,820 --> 00:19:17,690 e ver onde ele me leva. 575 00:19:17,690 --> 00:19:17,870 >> ESTÁ BEM. 576 00:19:17,870 --> 00:19:20,161 Então, dois e quatro, deixe-me ir em frente e apenas trocar vocês dois. 577 00:19:20,161 --> 00:19:22,400 Se você pode mover fisicamente vocês mesmos e seu papel, 578 00:19:22,400 --> 00:19:25,040 Eu pareço ter começado a listar em um estado melhor. 579 00:19:25,040 --> 00:19:26,330 >> Agora, eles são bons. 580 00:19:26,330 --> 00:19:28,480 Eu vou seguir em frente, quatro e seis anos, parece ser bom. 581 00:19:28,480 --> 00:19:29,110 Não é um problema. 582 00:19:29,110 --> 00:19:30,440 Seis e oito, OK. 583 00:19:30,440 --> 00:19:31,860 Oito e um, um outro problema. 584 00:19:31,860 --> 00:19:34,750 Porque o que é verdade sobre oito e um? 585 00:19:34,750 --> 00:19:36,990 Um vem antes das oito, e assim o que devemos fazer? 586 00:19:36,990 --> 00:19:38,090 Vamos trocar esses dois. 587 00:19:38,090 --> 00:19:39,316 Um e oito. 588 00:19:39,316 --> 00:19:40,690 E agora, eu vou continuar. 589 00:19:40,690 --> 00:19:42,030 Eu vou continuar olhando para frente. 590 00:19:42,030 --> 00:19:42,840 E vamos ver o que acontece. 591 00:19:42,840 --> 00:19:44,680 Oito e três, de Claro, fora de ordem. 592 00:19:44,680 --> 00:19:45,815 Vamos swap. 593 00:19:45,815 --> 00:19:46,940 Oito e sete, é claro. 594 00:19:46,940 --> 00:19:47,481 Fora de ordem. 595 00:19:47,481 --> 00:19:48,280 Vamos swap. 596 00:19:48,280 --> 00:19:49,940 Oito e cinco, é claro, vamos swap. 597 00:19:49,940 --> 00:19:50,560 Tudo certo. 598 00:19:50,560 --> 00:19:51,880 Lista é ordenada. 599 00:19:51,880 --> 00:19:53,060 sim? 600 00:19:53,060 --> 00:19:54,280 >> OK, obviamente, não. 601 00:19:54,280 --> 00:19:55,860 Mas é um pouco melhor, certo? 602 00:19:55,860 --> 00:19:57,270 Porque aviso que aconteceu. 603 00:19:57,270 --> 00:20:01,749 Cada vez que realizou um swap, um menor número tipo de percolado que maneira, 604 00:20:01,749 --> 00:20:03,790 e um número maior percolado desta forma, ou nós vamos 605 00:20:03,790 --> 00:20:06,880 começar a dizer ao borbulhar para a esquerda ou para a direita borbulhar. 606 00:20:06,880 --> 00:20:10,080 >> Agora, não é suficiente, porque na melhor das hipóteses um número poderia 607 00:20:10,080 --> 00:20:11,990 ter movido um ponto para a frente, ou na pior das hipóteses, 608 00:20:11,990 --> 00:20:13,880 pode ter um número movido um local mais longe. 609 00:20:13,880 --> 00:20:16,369 Então, você sabe o quê, este tipo de funcionou muito bem até agora. 610 00:20:16,369 --> 00:20:17,410 Deixe-me apenas experimentá-lo novamente. 611 00:20:17,410 --> 00:20:18,880 Dois e quatro, eles estão OK. 612 00:20:18,880 --> 00:20:20,180 Quatro e seis, eles estão OK. 613 00:20:20,180 --> 00:20:21,790 Seis e um, fora de ordem. 614 00:20:21,790 --> 00:20:23,007 Então, vamos trocar vocês dois. 615 00:20:23,007 --> 00:20:25,840 E agora, repare o problema de começando a ficar um pouco melhor novamente. 616 00:20:25,840 --> 00:20:27,006 Seis e três, fora de ordem. 617 00:20:27,006 --> 00:20:28,100 Vamos trocar vocês dois. 618 00:20:28,100 --> 00:20:29,730 Seis e sete, você é bom. 619 00:20:29,730 --> 00:20:32,230 Sete e cinco, é claro, fora de ordem. 620 00:20:32,230 --> 00:20:33,920 Sete e oito, em ordem. 621 00:20:33,920 --> 00:20:36,470 E agora, eu talvez seja necessário fazer isso mais algumas vezes. 622 00:20:36,470 --> 00:20:39,830 E, na verdade, acho que para vós talvez quantas vezes maximamente 623 00:20:39,830 --> 00:20:41,330 pode eu tenho que andar para trás e para frente? 624 00:20:41,330 --> 00:20:42,390 >> Nós vamos voltar a isso. 625 00:20:42,390 --> 00:20:43,700 Então, dois e quatro ainda estão OK. 626 00:20:43,700 --> 00:20:44,940 Quatro e um, Nope. 627 00:20:44,940 --> 00:20:45,747 Então, troca de deixar. 628 00:20:45,747 --> 00:20:47,830 E, novamente, observar visualmente um é uma espécie de borbulhar 629 00:20:47,830 --> 00:20:49,163 para a esquerda, onde deveria estar. 630 00:20:49,163 --> 00:20:50,010 Quatro e três swap. 631 00:20:50,010 --> 00:20:51,330 Quatro e seis. 632 00:20:51,330 --> 00:20:53,100 Seis e cinco swap. 633 00:20:53,100 --> 00:20:53,959 Seis e sete. 634 00:20:53,959 --> 00:20:55,000 Sete e oito são boas. 635 00:20:55,000 --> 00:20:55,500 >> Boa. 636 00:20:55,500 --> 00:20:58,460 Estamos ficando ainda melhor. 637 00:20:58,460 --> 00:20:59,130 Então vamos ver. 638 00:20:59,130 --> 00:21:00,940 Agora, temos dois e um. 639 00:21:00,940 --> 00:21:02,520 Claro, trocar. 640 00:21:02,520 --> 00:21:07,520 Dois e três, três e quatro, quatro e cinco, seis e sete, sete e oito. 641 00:21:07,520 --> 00:21:08,020 Boa. 642 00:21:08,020 --> 00:21:08,730 E você sabe o quê? 643 00:21:08,730 --> 00:21:11,190 Porque eu fiz uma mudança lá, deixe-me fazer uma verificação de sanidade. 644 00:21:11,190 --> 00:21:13,023 Deixe-me ir até o fim voltar para o início. 645 00:21:13,023 --> 00:21:13,680 ESTÁ BEM. 646 00:21:13,680 --> 00:21:14,750 Um, dois-- sim, ver? 647 00:21:14,750 --> 00:21:15,870 Algo estava errado. 648 00:21:15,870 --> 00:21:18,420 Três, quatro, cinco, seis, sete, oito. 649 00:21:18,420 --> 00:21:21,920 E neste último passe, são Você está satisfeito com a minha empresa 650 00:21:21,920 --> 00:21:23,830 alegando que ele é classificado? 651 00:21:23,830 --> 00:21:24,330 ESTÁ BEM. 652 00:21:24,330 --> 00:21:25,880 Visualmente, isso é absolutamente verdadeiro. 653 00:21:25,880 --> 00:21:28,410 Mas funcionalmente, o que que também só acontecerá 654 00:21:28,410 --> 00:21:31,870 nesse último passe que permite que você para confirmar que esta lista é de fato 655 00:21:31,870 --> 00:21:32,660 classificadas? 656 00:21:32,660 --> 00:21:34,477 >> O que eu fiz ou não fazer isso último passe? 657 00:21:34,477 --> 00:21:35,810 AUDIÊNCIA: Não houve alterações. 658 00:21:35,810 --> 00:21:36,120 DAVID J. MALAN: Desculpe? 659 00:21:36,120 --> 00:21:37,070 AUDIÊNCIA: Sem alterações. 660 00:21:37,070 --> 00:21:38,653 DAVID J. MALAN: Não houve alterações. 661 00:21:38,653 --> 00:21:41,947 Portanto, seria estúpido da minha parte fazer isso mesmo algoritmo novamente 662 00:21:41,947 --> 00:21:43,780 se eu não fazer qualquer altera a primeira vez. 663 00:21:43,780 --> 00:21:45,160 E o Estado não mudou. 664 00:21:45,160 --> 00:21:47,576 Certamente, eu não vou fazer qualquer muda pela segunda vez. 665 00:21:47,576 --> 00:21:49,820 E assim, é seguro agora quer dizer, lista é ordenada. 666 00:21:49,820 --> 00:21:52,069 >> E, de fato, este é agora algo que nós vamos geral 667 00:21:52,069 --> 00:21:56,900 chamada bubble sort, em que pares, você corrigir erros novamente, 668 00:21:56,900 --> 00:22:00,210 e de novo, e de novo, e você manter indo e voltando, 669 00:22:00,210 --> 00:22:03,370 e frente e para trás, até que você fazer nenhum desses swaps, em que ponto 670 00:22:03,370 --> 00:22:07,089 você pode ter certeza, sim, eu Terminada a fixação todos os erros. 671 00:22:07,089 --> 00:22:08,630 Vamos redefinir e tentar outra abordagem. 672 00:22:08,630 --> 00:22:11,590 Se vocês poderiam voltar para a ordem que você era um momento atrás, 673 00:22:11,590 --> 00:22:13,780 que olhou como esta. 674 00:22:13,780 --> 00:22:17,640 Agora, vamos ter uma abordagem um pouco mais como o livro exame, 675 00:22:17,640 --> 00:22:21,122 pelo qual estávamos constantemente seleccionando a letra do alfabeto 676 00:22:21,122 --> 00:22:22,830 que nós meio que queria para lidar com o próximo. 677 00:22:22,830 --> 00:22:26,420 Talvez fosse uma carta alta, como A, ou uma baixa letra Z. 678 00:22:26,420 --> 00:22:28,170 >> Então, todo mundo está de volta nesta ordem. 679 00:22:28,170 --> 00:22:29,800 E agora deixe-me fazer isso. 680 00:22:29,800 --> 00:22:34,880 Vamos ver Eu sei que tenho oito números aqui. 681 00:22:34,880 --> 00:22:37,410 Eu estou indo para ir em frente e apenas deliberadamente selecione 682 00:22:37,410 --> 00:22:38,520 os elementos mais pequenos. 683 00:22:38,520 --> 00:22:38,760 Certo? 684 00:22:38,760 --> 00:22:39,801 Isso parece muito intuitivo. 685 00:22:39,801 --> 00:22:42,560 Por que eu não encontrar o menor elemento, colocá-lo onde ele pertence, 686 00:22:42,560 --> 00:22:45,280 em seguida, obter o próximo elemento mais pequeno, coloque -lo onde ele pertence, e basta repetir. 687 00:22:45,280 --> 00:22:46,820 >> Porque intuitivamente, que deve funcionar também. 688 00:22:46,820 --> 00:22:48,441 Então, quatro, que é um número bastante pequeno. 689 00:22:48,441 --> 00:22:49,940 Eu vou lembrar de onde isso é. 690 00:22:49,940 --> 00:22:50,523 Espere um minuto. 691 00:22:50,523 --> 00:22:51,577 Dois é menor. 692 00:22:51,577 --> 00:22:53,910 Deixa-me lembrar onde dois é, e esquecer-se sobre quatro. 693 00:22:53,910 --> 00:22:55,050 Nós vamos lidar com isso mais tarde. 694 00:22:55,050 --> 00:22:56,460 Seis, eu não estou interessado. 695 00:22:56,460 --> 00:22:57,810 Oito, eu não estou interessado. 696 00:22:57,810 --> 00:22:59,780 Um deles é o meu novo número pequeno. 697 00:22:59,780 --> 00:23:01,470 Então, eu vou me lembrar onde você estiver. 698 00:23:01,470 --> 00:23:02,534 Três, não está interessado. 699 00:23:02,534 --> 00:23:03,450 Sete, não está interessado. 700 00:23:03,450 --> 00:23:04,530 Cinco, não está interessado. 701 00:23:04,530 --> 00:23:07,390 >> Então, sem cair o palco este ano, 702 00:23:07,390 --> 00:23:09,890 Vou agarrar número um-- e qual era o seu nome? 703 00:23:09,890 --> 00:23:10,150 >> ANNAN: Annan. 704 00:23:10,150 --> 00:23:11,220 >> DAVID J. MALAN: Annan. 705 00:23:11,220 --> 00:23:13,540 E se você pudesse se juntar a mim no o início da lista, 706 00:23:13,540 --> 00:23:14,870 vamos colocá-lo onde você pertence. 707 00:23:14,870 --> 00:23:16,080 Unfortunately-- qual é o seu nome? 708 00:23:16,080 --> 00:23:16,650 >> STEFAN: Stefan. 709 00:23:16,650 --> 00:23:18,191 >> DAVID J. MALAN: Stefan está no caminho. 710 00:23:18,191 --> 00:23:23,490 Portanto, antes de Stefan resolve este problema, o que devemos fazer? 711 00:23:23,490 --> 00:23:25,412 O que vamos fazer com Stefan? 712 00:23:25,412 --> 00:23:27,269 >> AUDIÊNCIA: [inaudível]. 713 00:23:27,269 --> 00:23:28,060 DAVID J. MALAN: OK. 714 00:23:28,060 --> 00:23:28,850 Assim nós poderíamos fazer isso. 715 00:23:28,850 --> 00:23:31,730 Poderíamos tipo de levar Stefan e sua quatro, e basta colocá-lo em uma variável 716 00:23:31,730 --> 00:23:33,530 e segurá-lo para uma certa quantidade de tempo, 717 00:23:33,530 --> 00:23:35,220 tornando assim espaço para o número um. 718 00:23:35,220 --> 00:23:36,280 E isso não é ruim. 719 00:23:36,280 --> 00:23:39,270 Eu poderia sugerir, por que não fazer nós apenas colocar Stefan aqui? 720 00:23:39,270 --> 00:23:41,610 Por que isso pode violar um das ideias que começaram 721 00:23:41,610 --> 00:23:44,830 falando última vez, na semana passada? 722 00:23:44,830 --> 00:23:45,330 Sim? 723 00:23:45,330 --> 00:23:45,740 >> AUDIÊNCIA: [inaudível]. 724 00:23:45,740 --> 00:23:46,860 >> DAVID J. MALAN: Não há nenhum índice para ele. 725 00:23:46,860 --> 00:23:49,735 Se você acha que isso, de fato, como um array, isto é como um negativo, 726 00:23:49,735 --> 00:23:52,900 por isso não há memória, na verdade, aqui se este é realmente uma matriz, 727 00:23:52,900 --> 00:23:55,090 como se declarou na semana passada na conferência. 728 00:23:55,090 --> 00:23:56,250 Assim, não devemos fazer isso. 729 00:23:56,250 --> 00:23:57,340 Podemos armazená-lo em uma variável. 730 00:23:57,340 --> 00:23:57,820 >> Ou você sabe o quê? 731 00:23:57,820 --> 00:23:59,153 Eu ouvi alguém sugerir isso. 732 00:23:59,153 --> 00:24:01,020 O que mais poderíamos fazer com Stefan? 733 00:24:01,020 --> 00:24:03,770 Por que nós não apenas expulsá-lo e colocá-lo sobre o lugar onde estava o número um. 734 00:24:03,770 --> 00:24:05,170 Então, se você quer ir para lá. 735 00:24:05,170 --> 00:24:07,300 E, de fato, este é um solução muito boa. 736 00:24:07,300 --> 00:24:10,480 Agora, por um lado, eu tenho tipo da piorou o problema. 737 00:24:10,480 --> 00:24:13,650 Quatro é agora mais longe de onde ele deve ser. 738 00:24:13,650 --> 00:24:14,900 Ele deve ser em direção a esse meio. 739 00:24:14,900 --> 00:24:16,100 >> Mas você sabe o quê? 740 00:24:16,100 --> 00:24:17,630 Isso poderia ter sido má sorte. 741 00:24:17,630 --> 00:24:18,822 Talvez o número oito foi aqui. 742 00:24:18,822 --> 00:24:20,530 E assim, talvez faríamos ter tido sorte, 743 00:24:20,530 --> 00:24:22,460 e oito empurrada para mais perto do fim. 744 00:24:22,460 --> 00:24:24,710 Assim, no final do dia, É o tipo de todas as médias para fora. 745 00:24:24,710 --> 00:24:26,085 Nós não precisa se preocupar com quatro. 746 00:24:26,085 --> 00:24:29,400 Tudo que me importa agora é seleccionando o elemento mais pequeno. 747 00:24:29,400 --> 00:24:32,030 >> E agora, o que eu vou fazer é esquecer-se sobre o número um 748 00:24:32,030 --> 00:24:35,160 permanentemente, porque eu sei o lista atrás de mim agora está classificada. 749 00:24:35,160 --> 00:24:36,720 Assim, a minha lista era anteriormente tamanho oito. 750 00:24:36,720 --> 00:24:37,720 Agora, é do tamanho de sete. 751 00:24:37,720 --> 00:24:40,340 Então, meu problema é conseguir menor, embora de forma linear. 752 00:24:40,340 --> 00:24:43,022 Então, agora, eu estou indo para selecionar o atual elemento mais pequeno, dois. 753 00:24:43,022 --> 00:24:46,520 Seis, oito, quatro, três, sete, cinco. 754 00:24:46,520 --> 00:24:47,770 Esse foi o menor elemento. 755 00:24:47,770 --> 00:24:49,416 Então o que é que eu vou fazer com-- o que era o seu nome? 756 00:24:49,416 --> 00:24:49,760 >> JOSÉ: José. 757 00:24:49,760 --> 00:24:50,085 >> DAVID J. MALAN: Joseph? 758 00:24:50,085 --> 00:24:52,000 Nós vamos deixar Joseph no lugar. 759 00:24:52,000 --> 00:24:54,842 Agora, eu vou fingir que esses caras é-- bem, 760 00:24:54,842 --> 00:24:56,550 Eu sei que estes dois já estão classificados. 761 00:24:56,550 --> 00:24:58,424 Vamos agora concentrar-se na restante da lista. 762 00:24:58,424 --> 00:25:00,080 Seis é a menor corrente. 763 00:25:00,080 --> 00:25:01,190 Oito é maior. 764 00:25:01,190 --> 00:25:02,970 Quatro é agora a menor corrente. 765 00:25:02,970 --> 00:25:04,762 Três é agora a menor corrente. 766 00:25:04,762 --> 00:25:07,720 E agora, eu estou indo para selecionar três, que é-- o que é seu nome? 767 00:25:07,720 --> 00:25:08,190 SERENA: Serena. 768 00:25:08,190 --> 00:25:10,620 DAVID J. MALAN: Serena, se pudesse pegue o seu número e swap com-- 769 00:25:10,620 --> 00:25:11,550 Kalsang: Kalsang. 770 00:25:11,550 --> 00:25:12,940 DAVID J. MALAN: Kalsang. 771 00:25:12,940 --> 00:25:15,220 Vamos voltar, e estamos vai trocar os dois. 772 00:25:15,220 --> 00:25:17,360 E agora, vamos colocar isso no piloto automático. 773 00:25:17,360 --> 00:25:21,589 Eu estou indo para ir e deixá-lo para vocês para selecionar os menores elementos próximos. 774 00:25:21,589 --> 00:25:22,380 Dun, dun, dun, dun. 775 00:25:22,380 --> 00:25:24,560 Número quatro, o que você deve fazer? 776 00:25:24,560 --> 00:25:26,261 Excelente. 777 00:25:26,261 --> 00:25:27,760 Agora, eu vou fazer uma outra passagem. 778 00:25:27,760 --> 00:25:28,590 Dun, dun, dun, dun. 779 00:25:28,590 --> 00:25:31,465 Vejo cinco é o próximo menor. 780 00:25:31,465 --> 00:25:32,840 Agora, eu vou tomar outra passagem. 781 00:25:32,840 --> 00:25:33,631 Dun, dun, dun, dun. 782 00:25:33,631 --> 00:25:34,880 Seis é o menor. 783 00:25:34,880 --> 00:25:35,520 Boa. 784 00:25:35,520 --> 00:25:36,585 Sete é o menor. 785 00:25:36,585 --> 00:25:37,085 Sem mudança. 786 00:25:37,085 --> 00:25:38,630 Oito é o menor. 787 00:25:38,630 --> 00:25:39,170 Feito. 788 00:25:39,170 --> 00:25:43,900 >> Então, o que acabou de fazer por forma iterativa seleccionando um elemento após a outra 789 00:25:43,900 --> 00:25:47,230 é implementar algo que nós somos vai formalizar como selecção de classificação. 790 00:25:47,230 --> 00:25:49,120 E é talvez ainda simples de explicar, 791 00:25:49,120 --> 00:25:51,310 em que, literalmente, tudo o que você quero fazer é apenas manter 792 00:25:51,310 --> 00:25:54,700 indo e voltando pela lista seleção, a próxima menor elemento, 793 00:25:54,700 --> 00:25:55,720 até que você esteja feito. 794 00:25:55,720 --> 00:25:58,650 >> Por isso, é ainda mais simples, talvez intuitivamente, que a última. 795 00:25:58,650 --> 00:26:00,020 Vamos tentar um último. 796 00:26:00,020 --> 00:26:03,060 Se vocês poderiam redefinir a si mesmos nas seguintes posições 797 00:26:03,060 --> 00:26:08,600 uma última vez, vamos ver se nós não podemos agora formalizar uma outra abordagem. 798 00:26:08,600 --> 00:26:12,857 Na verdade, seria alguém lá fora, gostaria de propor 799 00:26:12,857 --> 00:26:14,440 de que outra forma poderíamos fazer sobre este assunto? 800 00:26:14,440 --> 00:26:17,439 Sem jogar fora buzzwords ou tipo de respostas que já são conhecidas, 801 00:26:17,439 --> 00:26:19,689 apenas intuitivamente, o que poderíamos fazer? 802 00:26:19,689 --> 00:26:21,635 >> AUDIÊNCIA: [inaudível]. 803 00:26:21,635 --> 00:26:22,510 DAVID J. MALAN: Yeah. 804 00:26:22,510 --> 00:26:24,620 Então, há alguma grande intuição lá. 805 00:26:24,620 --> 00:26:28,020 As coisas boas parecem acontecer até agora em ciência da computação quando dividimos 806 00:26:28,020 --> 00:26:30,832 e conquistar o problema de dividir ao meio e meio a meio. 807 00:26:30,832 --> 00:26:32,540 E assim, de fato, nós poderia começar a fazer isso. 808 00:26:32,540 --> 00:26:35,754 E, de fato, que vai ser, vamos ver, um dos nossos melhores soluções ainda. 809 00:26:35,754 --> 00:26:37,420 Mas vamos voltar a isso em pouco tempo. 810 00:26:37,420 --> 00:26:40,500 Na verdade, nós vamos fazer que um pouco mais tarde esta semana. 811 00:26:40,500 --> 00:26:42,180 O que mais podemos fazer para resolver isso? 812 00:26:42,180 --> 00:26:44,647 Então, todo mundo aqui está em ordem aparentemente aleatória. 813 00:26:44,647 --> 00:26:45,230 Você sabe o que? 814 00:26:45,230 --> 00:26:48,320 Ao invés de ir e voltar, frente e para trás, e para trás 815 00:26:48,320 --> 00:26:50,624 cada vez, este se sente como Eu estou fazendo um monte de pé. 816 00:26:50,624 --> 00:26:52,790 Por que não posso apenas começar em o início da lista, 817 00:26:52,790 --> 00:26:54,960 e basta colocar quatro onde ele pertence? 818 00:26:54,960 --> 00:26:59,680 Então deixe-me assumir para o momento que minha lista é apenas este primeiro elemento. 819 00:26:59,680 --> 00:27:04,937 É quatro classificados neste momento no tempo, se tudo o que me importa é tudo aqui? 820 00:27:04,937 --> 00:27:06,520 Esta é uma espécie de trivialmente verdadeira, certo? 821 00:27:06,520 --> 00:27:10,000 Como a lista contendo um número, e que é, obviamente, o número quatro classificados. 822 00:27:10,000 --> 00:27:13,070 >> Então deixe-me apenas estipular que esta lista é ordenada. 823 00:27:13,070 --> 00:27:15,090 Mas agora eu tenho o resto desta lista. 824 00:27:15,090 --> 00:27:17,240 Então, agora, eu encontro dois. 825 00:27:17,240 --> 00:27:21,690 Onde faz dois, obviamente, pertencem em relação a quatro? 826 00:27:21,690 --> 00:27:22,580 Antes quatro. 827 00:27:22,580 --> 00:27:23,862 Então, o que eu posso fazer aqui? 828 00:27:23,862 --> 00:27:24,820 Qual é o seu nome? 829 00:27:24,820 --> 00:27:25,090 >> JOSÉ: José. 830 00:27:25,090 --> 00:27:26,030 >> DAVID J. MALAN: Joseph, se você pudesse voltar atrás 831 00:27:26,030 --> 00:27:27,790 por apenas um momento com o seu número. 832 00:27:27,790 --> 00:27:31,130 E agora o que deve Stefan fazer aqui? 833 00:27:31,130 --> 00:27:33,720 Vamos mudar Stefan aqui. 834 00:27:33,720 --> 00:27:35,520 E agora, vamos Joseph entrar aqui. 835 00:27:35,520 --> 00:27:39,660 E agora, deixe-me afirmar que tudo aqui está classificada. 836 00:27:39,660 --> 00:27:42,474 Então, resultado semelhante, mas um abordagem fundamentalmente diferente. 837 00:27:42,474 --> 00:27:44,140 Eu nem sequer olhou para o que está lá em baixo. 838 00:27:44,140 --> 00:27:46,310 Eu continuo tendo os elementos como eles são entregue a mim, 839 00:27:46,310 --> 00:27:47,240 e lidar com eles. 840 00:27:47,240 --> 00:27:48,330 >> Então, agora, eu vejo o número seis. 841 00:27:48,330 --> 00:27:51,110 Onde é que o número seis pertencem? 842 00:27:51,110 --> 00:27:53,250 Temos dois, quatro, seis. 843 00:27:53,250 --> 00:27:54,800 Exatamente onde ela está agora. 844 00:27:54,800 --> 00:27:57,750 Então, vamos deixar isso quieto, e agora afirmam que esta parte da lista 845 00:27:57,750 --> 00:27:58,772 agora está classificada. 846 00:27:58,772 --> 00:28:01,230 E assim, este se sente fundamentalmente diferente, já que eu sou apenas 847 00:28:01,230 --> 00:28:05,230 movendo-se através da lista aqui linearmente, e eu nunca estou dobrando para trás. 848 00:28:05,230 --> 00:28:05,730 Sim. 849 00:28:05,730 --> 00:28:06,230 Tudo certo. 850 00:28:06,230 --> 00:28:08,190 Assim, oito, onde você pertence? 851 00:28:08,190 --> 00:28:08,730 Aqui mesmo. 852 00:28:08,730 --> 00:28:09,310 Perfeito. 853 00:28:09,310 --> 00:28:10,210 Então, agora, um. 854 00:28:10,210 --> 00:28:10,900 Uh oh. 855 00:28:10,900 --> 00:28:13,010 Isto parece que é vai ser caro. 856 00:28:13,010 --> 00:28:15,690 Agora, no algoritmo anterior, Eu apenas trocados pessoas. 857 00:28:15,690 --> 00:28:18,648 Para que eu possa colocá-lo todo o caminho no no início, mas depois mudou Joseph. 858 00:28:18,648 --> 00:28:21,450 Mas se eu passar Joseph, agora o que vai ser errado? 859 00:28:21,450 --> 00:28:24,250 >> Agora, eu tenho a sorte de undone-- tenho dado um passo para a frente e, em seguida, 860 00:28:24,250 --> 00:28:26,300 um passo para trás, porque agora Joseph estaria fora de ordem. 861 00:28:26,300 --> 00:28:26,830 Então, vamos fazer isso. 862 00:28:26,830 --> 00:28:29,150 Se você pudesse levar o número um e passo para trás por apenas um momento. 863 00:28:29,150 --> 00:28:30,490 Como podemos put-- o que mesmo o seu nome? 864 00:28:30,490 --> 00:28:31,130 >> ANNAN: Annan. 865 00:28:31,130 --> 00:28:32,610 >> DAVID J. MALAN: Annan no lugar? 866 00:28:32,610 --> 00:28:36,091 O que precisa acontecer com respeito a dois, quatro, seis, oito e? 867 00:28:36,091 --> 00:28:37,570 Tudo que eles precisam mudar. 868 00:28:37,570 --> 00:28:42,590 Portanto, se oito gostaria de deslocar em primeiro lugar, em seguida, seis, depois quatro, depois dois. 869 00:28:42,590 --> 00:28:45,380 E então Annan, se você gostaria de vir aqui, bom. 870 00:28:45,380 --> 00:28:47,760 Mas aqui, nós temos apenas tipo de pago um preço 871 00:28:47,760 --> 00:28:49,510 num ponto diferente no algoritmo. 872 00:28:49,510 --> 00:28:52,550 Considerando última vez com a seleção tipo, e até mesmo bubble sort, 873 00:28:52,550 --> 00:28:54,700 Eu estou andando para trás e frente, para trás e para frente, 874 00:28:54,700 --> 00:28:58,360 que é, certamente, somando tempo-sábio, e, literalmente, passo a passo. 875 00:28:58,360 --> 00:29:00,660 >> Ordenação por inserção, na primeira vista, parece que é 876 00:29:00,660 --> 00:29:05,150 super-inteligente, em que eu sou apenas tornando lento, o progresso incremental, 877 00:29:05,150 --> 00:29:07,120 mas eu não vou esta frente e para trás. 878 00:29:07,120 --> 00:29:09,410 Mas se alguém é de fato fora de ordem, aviso 879 00:29:09,410 --> 00:29:10,840 todo o trabalho que eu apenas tive que fazer. 880 00:29:10,840 --> 00:29:14,750 Eu tive que mudar metade da lista apenas para dar espaço para o número um. 881 00:29:14,750 --> 00:29:16,790 Então é a mesma quantidade de trabalho, até agora, ele 882 00:29:16,790 --> 00:29:18,690 sente, apenas um tipo diferente de trabalho. 883 00:29:18,690 --> 00:29:19,370 >> Vamos continuar. 884 00:29:19,370 --> 00:29:22,657 Portanto, agora sabemos que toda a gente entre um e oito são classificadas. 885 00:29:22,657 --> 00:29:23,740 Aqui, eu tenho o número três. 886 00:29:23,740 --> 00:29:25,864 Se você gosta de pegar número três, passo para trás um. 887 00:29:25,864 --> 00:29:28,260 E o que vocês precisam fazer? 888 00:29:28,260 --> 00:29:28,760 Sim. 889 00:29:28,760 --> 00:29:33,070 Então, isso é um outro, dois, três passos. 890 00:29:33,070 --> 00:29:36,010 Três unidades de tempo que custam apenas me, de modo que os três podem agora encaixar. 891 00:29:36,010 --> 00:29:37,460 Finalmente, sete. 892 00:29:37,460 --> 00:29:39,730 >> Vamos em frente e ter você tomar um passo para trás. 893 00:29:39,730 --> 00:29:42,780 Isso só vai nos custar uma unidade de tempo, mas isso é OK. 894 00:29:42,780 --> 00:29:44,170 E agora, cinco de ir para ser um pouco mais caro. 895 00:29:44,170 --> 00:29:45,340 Se você gostaria de dar um passo atrás. 896 00:29:45,340 --> 00:29:48,380 Precisamos avançar oito, e sete, e seis. 897 00:29:48,380 --> 00:29:50,749 E então todo mundo está agora classificada. 898 00:29:50,749 --> 00:29:52,290 Assim, uma grande mão para os nossos voluntários aqui. 899 00:29:52,290 --> 00:29:53,554 Muito obrigada. 900 00:29:53,554 --> 00:29:56,220 >> [Aplausos] 901 00:29:56,220 --> 00:29:56,860 >> Obrigado a todos. 902 00:29:56,860 --> 00:29:57,520 Obrigado a todos. 903 00:29:57,520 --> 00:30:02,940 Então vamos ver agora o quão caro tudo isso era. 904 00:30:02,940 --> 00:30:06,210 Vamos considerar, talvez, o mais simples delas, uma espécie de bolha. 905 00:30:06,210 --> 00:30:09,950 E digo mais simples, só porque você pode resolvê-lo avidamente por apenas 906 00:30:09,950 --> 00:30:11,660 resolver o problema de pares aqui. 907 00:30:11,660 --> 00:30:13,720 Corrigir o problema de pares aqui, uma e outra vez 908 00:30:13,720 --> 00:30:17,680 e novamente, repetindo como muitos vezes como você realmente precisa. 909 00:30:17,680 --> 00:30:21,050 >> Assim, verifica-se que com uma espécie de bolha, bem, 910 00:30:21,050 --> 00:30:25,820 quantos passos eu tenho que assumir a primeira passagem desse algoritmo? 911 00:30:25,820 --> 00:30:30,850 Eu poderia take-- vamos see-- um, dois, três, quatro, cinco, seis, sete. 912 00:30:30,850 --> 00:30:32,190 E há oito elementos aqui. 913 00:30:32,190 --> 00:30:35,280 Então, é como n menos 1 passos para começa a partir do início da lista 914 00:30:35,280 --> 00:30:36,380 para o fim da lista. 915 00:30:36,380 --> 00:30:41,350 >> Mas com seleção tipo, lembre-se que eu sou selecionar os elementos novo e de novo 916 00:30:41,350 --> 00:30:44,590 e, novamente, que é menor, Estou colocando-o no lugar, 917 00:30:44,590 --> 00:30:46,616 mas então eu não sou olhando atrás de mim novamente. 918 00:30:46,616 --> 00:30:49,490 Então, eu acho que é um pouco mais clara que, em seguida, pela primeira vez, que pode 919 00:30:49,490 --> 00:30:52,680 tem que tomar todos os passos n menos 1 para encontrar o elemento mais pequeno. 920 00:30:52,680 --> 00:30:55,920 Então eu colocá-los no lugar, e eu expulsar quem quer que estivesse aqui anteriormente. 921 00:30:55,920 --> 00:30:57,500 >> Mas então eu não tenho que manter a olhar para este elemento, 922 00:30:57,500 --> 00:30:59,040 porque eu sei que é já a menor. 923 00:30:59,040 --> 00:31:01,581 Então, agora, eu posso olhar para apenas sete elementos, em seguida, seis elementos, 924 00:31:01,581 --> 00:31:03,290 em seguida, cinco elementos, em seguida, quatro elementos. 925 00:31:03,290 --> 00:31:06,900 E assim matematicamente, se n é o número de elementos ou números 926 00:31:06,900 --> 00:31:11,990 que começou com, você pode imaginar que este é o mesmo que n menos 1, 927 00:31:11,990 --> 00:31:14,250 além n menos 2 etapas, n menos mais 3 etapas, 928 00:31:14,250 --> 00:31:16,780 n menos mais 4 passos, tudo o maneira para baixo a apenas um passo. 929 00:31:16,780 --> 00:31:18,160 E eu estou em minha última pessoa. 930 00:31:18,160 --> 00:31:20,650 >> E se você se lembra que um monte Status de livros ou livros de matemática 931 00:31:20,650 --> 00:31:24,730 ter essas fórmulas na capa dura para trás ou frente deles, 932 00:31:24,730 --> 00:31:27,690 verifica-se que esta série pode ser expresso de forma mais simples 933 00:31:27,690 --> 00:31:28,857 como n vezes n menos 1 sobre 2. 934 00:31:28,857 --> 00:31:31,273 E é bom se isso não é na vanguarda da sua mente. 935 00:31:31,273 --> 00:31:32,420 Mas isso é realmente verdade. 936 00:31:32,420 --> 00:31:34,449 Isso é apenas uma maneira mais simples de escrevê-lo. 937 00:31:34,449 --> 00:31:36,240 E então se você acha de volta à escola, 938 00:31:36,240 --> 00:31:38,698 quando você acabou de começar multiplicando coisas, isso, claro, 939 00:31:38,698 --> 00:31:41,820 é apenas n ao quadrado menos n dividido por dois. 940 00:31:41,820 --> 00:31:44,772 Tudo o que eu tenho feito é expandir as expressões lá. 941 00:31:44,772 --> 00:31:46,730 E assim vamos reescrever este um pouco diferente. 942 00:31:46,730 --> 00:31:49,780 Isso n ao quadrado dividido por 2 menos n / 2. 943 00:31:49,780 --> 00:31:53,270 >> Então, novamente, eu sou apenas um tipo de aplicação um pouco de aritmética governa lá. 944 00:31:53,270 --> 00:31:57,140 Mas note-se agora que o maior prazo nesta expressão, por assim dizer, 945 00:31:57,140 --> 00:31:58,540 é que n ao quadrado. 946 00:31:58,540 --> 00:32:02,910 Então, sim, é n ao quadrado dividido por dois, menos n / 2. 947 00:32:02,910 --> 00:32:05,080 >> Mas, geralmente, se n for vai ser um valor grande, 948 00:32:05,080 --> 00:32:08,740 Eu vou alegar que n ao quadrado vai ser o fator dominante. 949 00:32:08,740 --> 00:32:10,490 É só vai ser um contribuinte maior 950 00:32:10,490 --> 00:32:12,877 para o número de passos do que n / 2. 951 00:32:12,877 --> 00:32:13,960 Então, o que quero dizer com isto? 952 00:32:13,960 --> 00:32:16,795 Vamos tentar um exemplo simples, mesmo embora a matemática fica um pouco grande. 953 00:32:16,795 --> 00:32:20,210 >> Então, suponha que tinha 1 milhão de pessoas no palco, ou 1 milhão de coisas 954 00:32:20,210 --> 00:32:21,320 que deseja classificar. 955 00:32:21,320 --> 00:32:23,730 Vamos ligar um milhão em exatamente que fórmula 956 00:32:23,730 --> 00:32:27,230 para ver quantos passos que leva totais para classificar um milhão de elementos usando digamos, 957 00:32:27,230 --> 00:32:28,560 tipo de seleção. 958 00:32:28,560 --> 00:32:30,760 >> Então, nós teríamos a mesma fórmula como antes. 959 00:32:30,760 --> 00:32:34,120 Eu ligar um milhão, para que eu recebo um milhão quadrado dividido por 2, 960 00:32:34,120 --> 00:32:35,990 menos de um milhão dividido por 2. 961 00:32:35,990 --> 00:32:40,180 Se eu fizer isso de matemática com antecedência aqui, temos 500 bilhões 962 00:32:40,180 --> 00:32:47,460 menos 500.000, que nos dá 499999500000, 963 00:32:47,460 --> 00:32:49,270 que é muito danado grande. 964 00:32:49,270 --> 00:32:54,370 >> Na verdade, se você comparar agora 499.000 milhões, 999 milhões, 965 00:32:54,370 --> 00:33:01,210 500000 contra o nosso valor original, 500 bilhões, é tão bem perto. 966 00:33:01,210 --> 00:33:06,850 Certo? n ao quadrado dividido por 2 dá US-- ou melhor, n ao quadrado dividido por 2 967 00:33:06,850 --> 00:33:08,370 nos deu 500 bilhões. 968 00:33:08,370 --> 00:33:13,510 Isso é muito danado perto a 499.999.500.000, 969 00:33:13,510 --> 00:33:17,970 o que quer dizer fora subtraindo 500.000, ou, mais geralmente, subtraindo fora 970 00:33:17,970 --> 00:33:20,010 n ao quadrado, não é realmente um grande negócio. 971 00:33:20,010 --> 00:33:22,490 O n ao quadrado faz com que essas números crescem muito rápido. 972 00:33:22,490 --> 00:33:25,790 >> Agora, isso só é importante na medida em como nós, como cientistas da computação, 973 00:33:25,790 --> 00:33:29,350 são geralmente não vai se importar tanto sobre as nuances dessas fórmulas 974 00:33:29,350 --> 00:33:31,400 e exatamente o que o respostas precisas são. 975 00:33:31,400 --> 00:33:33,390 Nós nos preocupamos só isso, você sabe o quê? 976 00:33:33,390 --> 00:33:37,810 No final do dia, esta fórmula é da ordem de n ao quadrado. 977 00:33:37,810 --> 00:33:39,350 >> Sim, nós estamos dividindo por dois lá dentro. 978 00:33:39,350 --> 00:33:41,360 Sim, nós estamos subtraindo off n menos 2. 979 00:33:41,360 --> 00:33:46,860 Contudo, no final do dia, o termo que realmente nos dói e custa-nos 980 00:33:46,860 --> 00:33:48,995 uma série de etapas é que o termo quadrado. 981 00:33:48,995 --> 00:33:51,370 E então o que um cientista da computação vai geralmente fazem 982 00:33:51,370 --> 00:33:54,160 é ignorar todos aqueles Da ordem menor, 983 00:33:54,160 --> 00:33:56,900 e basta olhar para o que mais contribui para o custo. 984 00:33:56,900 --> 00:34:00,530 >> E isso é bom, porque podemos agora falar com muito mais generalidade 985 00:34:00,530 --> 00:34:02,470 sobre algoritmos, e pode compará-los. 986 00:34:02,470 --> 00:34:04,550 E o fato de que eu sou O utilizando este é deliberada. 987 00:34:04,550 --> 00:34:06,680 Quando eu digo no fim de, estou especificamente 988 00:34:06,680 --> 00:34:09,560 referindo-se a algo chamado grande O. E ó grande 989 00:34:09,560 --> 00:34:14,090 é uma notação que um computador cientista usa para descrever 990 00:34:14,090 --> 00:34:16,710 um limite superior em alguma coisa. 991 00:34:16,710 --> 00:34:21,150 >> Então, se você dizer que um algoritmo é em grande O de n ao quadrado, 992 00:34:21,150 --> 00:34:23,380 como eu propus apenas um há pouco, que os meios 993 00:34:23,380 --> 00:34:27,710 que, em termos da sua execução tempo ou a sua eficiência, 994 00:34:27,710 --> 00:34:30,090 ele assume a ordem quadrado de n passos. 995 00:34:30,090 --> 00:34:31,420 Talvez mais, talvez menos. 996 00:34:31,420 --> 00:34:33,435 Mas é da ordem de n ao quadrado. 997 00:34:33,435 --> 00:34:34,560 E esse é o limite superior. 998 00:34:34,560 --> 00:34:36,530 Não vai ser mais doloroso do que isso. 999 00:34:36,530 --> 00:34:40,800 Não vai ser n cubos, ou 2 ao n, ou algo muito maior. 1000 00:34:40,800 --> 00:34:43,800 Este é um limite superior em tudo o que o custo é. 1001 00:34:43,800 --> 00:34:46,150 Assim, dado que, vamos Considere apenas alguns exemplos. 1002 00:34:46,150 --> 00:34:49,820 E esta é apenas uma lista finita tempos de execução de muito comuns 1003 00:34:49,820 --> 00:34:52,870 para algoritmos que está destinado a ser ilustrativos de alguns coisas que temos 1004 00:34:52,870 --> 00:34:53,600 visto já. 1005 00:34:53,600 --> 00:34:58,060 >> Assim, por exemplo, no caso de seleção tipo, o que eu estou dizendo aqui 1006 00:34:58,060 --> 00:35:02,250 está em execução que a seleção de tipo tempo é da ordem de n ao quadrado. 1007 00:35:02,250 --> 00:35:06,260 No pior caso, eu vou ter um monte de números aleatórios aqui. 1008 00:35:06,260 --> 00:35:08,600 E, como vimos matematicamente, se eu continuar caminhando 1009 00:35:08,600 --> 00:35:11,310 por meio da lista, através do lista, selecionar o próximo menor 1010 00:35:11,310 --> 00:35:14,410 elemento novo e de novo, se eu na verdade, anote todas as etapas 1011 00:35:14,410 --> 00:35:18,750 Estou tomando como eu propus como uma fórmula antes, é da ordem de n ao quadrado 1012 00:35:18,750 --> 00:35:20,370 etapas que eu estou tomando. 1013 00:35:20,370 --> 00:35:24,520 >> E verifica-se que bolha tipo e ordenação por inserção 1014 00:35:24,520 --> 00:35:27,370 são tão lento no pior dos casos. 1015 00:35:27,370 --> 00:35:32,040 Considere, por exemplo, ordenação por inserção, o último algoritmo, tratámos, 1016 00:35:32,040 --> 00:35:35,500 que nos fez olhar para o elemento, e, em seguida, inseri-lo onde ele pertence. 1017 00:35:35,500 --> 00:35:38,720 E então olhamos para o próximo elemento, e inseriu-lo onde ele pertence. 1018 00:35:38,720 --> 00:35:40,990 >> Por isso, considero o melhor cenário possível. 1019 00:35:40,990 --> 00:35:45,590 Suponha que eu tinha meus voluntários alinhar literalmente, como este, de um a oito, 1020 00:35:45,590 --> 00:35:47,440 já ordenados. 1021 00:35:47,440 --> 00:35:51,300 Quantos passos é a ordenação por inserção vai levar para classificar oito pessoas, 1022 00:35:51,300 --> 00:35:55,640 se eles chegam no palco olhando assim? 1023 00:35:55,640 --> 00:35:57,410 >> Oito pessoas já ordenados. 1024 00:35:57,410 --> 00:35:58,760 E eu uso a inserção de tipo. 1025 00:35:58,760 --> 00:36:02,180 Esse último dos algoritmos. 1026 00:36:02,180 --> 00:36:03,640 Bem, vamos reviver rápido real. 1027 00:36:03,640 --> 00:36:05,504 Então, se eu começar aqui, eu vejo um. 1028 00:36:05,504 --> 00:36:06,420 Onde é que se pertencem? 1029 00:36:06,420 --> 00:36:07,730 Ele pertence aqui. 1030 00:36:07,730 --> 00:36:08,330 Eu vejo dois. 1031 00:36:08,330 --> 00:36:09,660 Onde é que dois pertencem? 1032 00:36:09,660 --> 00:36:10,260 Aqui mesmo. 1033 00:36:10,260 --> 00:36:10,900 Eu vejo três. 1034 00:36:10,900 --> 00:36:11,920 Onde é que três pertencem? 1035 00:36:11,920 --> 00:36:12,480 Aqui mesmo. 1036 00:36:12,480 --> 00:36:13,100 >> Eu vejo quatro. 1037 00:36:13,100 --> 00:36:13,600 Aqui mesmo. 1038 00:36:13,600 --> 00:36:15,660 Cinco, seis, sete, oito. 1039 00:36:15,660 --> 00:36:17,320 Não há nenhuma razão para me repetir. 1040 00:36:17,320 --> 00:36:21,260 E assim, como muitos passos é que, em termos de n? 1041 00:36:21,260 --> 00:36:23,870 É da ordem de n passos, certo? n menos 1. 1042 00:36:23,870 --> 00:36:27,567 Mas eu tomou uma série linear de passos, e agora eu sou feito. 1043 00:36:27,567 --> 00:36:28,900 Então esse é o melhor caso, no entanto. 1044 00:36:28,900 --> 00:36:29,983 E sobre o pior caso? 1045 00:36:29,983 --> 00:36:32,730 O que oito estavam lá, e sete estavam lá embaixo, 1046 00:36:32,730 --> 00:36:35,840 e um e dois foram mais aqui, então que a lista foram verdadeiramente revertido? 1047 00:36:35,840 --> 00:36:38,300 >> Bem, o que acontece de fato se este é o número? 1048 00:36:38,300 --> 00:36:41,300 E nós vamos fazer apenas um par de exemplos. 1049 00:36:41,300 --> 00:36:49,300 E se, na verdade, o número oito está aqui, e os gritos number--. 1050 00:36:49,300 --> 00:36:52,660 1051 00:36:52,660 --> 00:36:56,430 Então, o que se, de fato, o número oito é todo o caminho até aqui, 1052 00:36:56,430 --> 00:36:57,790 e eu estou usando ordenação por inserção? 1053 00:36:57,790 --> 00:36:58,290 >> ESTÁ BEM. 1054 00:36:58,290 --> 00:37:00,280 Eu reivindico no momento que está no lugar. 1055 00:37:00,280 --> 00:37:03,152 Mas agora, seven-- onde é que sete ir? 1056 00:37:03,152 --> 00:37:04,360 Claro, ele vai por aqui. 1057 00:37:04,360 --> 00:37:06,760 Então eu tenho que mover oito mais de um lugar. 1058 00:37:06,760 --> 00:37:08,554 Agora seis, onde ela vai? 1059 00:37:08,554 --> 00:37:09,220 Bem, tudo bem. 1060 00:37:09,220 --> 00:37:13,150 Agora, eu tenho que mudar oito mais um lugar, e sete ao longo de um lugar, 1061 00:37:13,150 --> 00:37:14,440 e então eu plop para baixo seis. 1062 00:37:14,440 --> 00:37:16,870 >> Assim, o primeiro tempo, custo me um passo para consertar as coisas, 1063 00:37:16,870 --> 00:37:18,570 então isso me custou dois passos para consertar as coisas. 1064 00:37:18,570 --> 00:37:20,370 Quantos passos é vai demorar para corrigir 1065 00:37:20,370 --> 00:37:22,720 coisas para colocar cinco no lugar certo? 1066 00:37:22,720 --> 00:37:23,340 Três. 1067 00:37:23,340 --> 00:37:29,520 Porque agora eu tenho que mover um, dois, três. 1068 00:37:29,520 --> 00:37:32,430 Quantos passos é que vai tomar para colocar quatro no lugar certo? 1069 00:37:32,430 --> 00:37:36,040 4 plus 5, acrescido de 6, além de sete. 1070 00:37:36,040 --> 00:37:40,260 >> E por isso é matematicamente idêntica à o que descrevemos para a seleção de classificação. 1071 00:37:40,260 --> 00:37:42,130 Nós temos nesta série que está apenas a aumentar. 1072 00:37:42,130 --> 00:37:45,650 1 mais 2 mais 3, mais 4, ou, inversamente, 7 + 6 1073 00:37:45,650 --> 00:37:52,610 mais 5 mais 4 acrescenta-se para hoje para fins da ordem de n ao quadrado. 1074 00:37:52,610 --> 00:37:57,640 >> Então deixe-me também que estipulam bubble sort é também no n ao quadrado. 1075 00:37:57,640 --> 00:38:01,340 Porque com bubble sort, cada vez que eu vá até a lista, 1076 00:38:01,340 --> 00:38:03,100 Estou levando aproximadamente quantos degraus? 1077 00:38:03,100 --> 00:38:06,260 Cada vez que eu literalmente andar de lá para lá? 1078 00:38:06,260 --> 00:38:07,960 Cerca de n passos. 1079 00:38:07,960 --> 00:38:12,650 Mas quantas vezes eu poderia precisa ir através da lista? 1080 00:38:12,650 --> 00:38:13,920 >> Bem, cerca de tempo n. 1081 00:38:13,920 --> 00:38:15,680 Talvez n menos 1, mas cerca de n vezes. 1082 00:38:15,680 --> 00:38:16,430 Bem, por que isso? 1083 00:38:16,430 --> 00:38:19,560 Bem, com bubble sort, se começamos com bubble sort, 1084 00:38:19,560 --> 00:38:23,570 com a lista na pior possível situação, que mais uma vez é completamente 1085 00:38:23,570 --> 00:38:25,550 para trás, o que vai acontecer? 1086 00:38:25,550 --> 00:38:28,830 Eu percorrer a lista, eo número um pertence todo o caminho até lá. 1087 00:38:28,830 --> 00:38:33,280 >> Mas com bubble sort, até que ponto é que um movimentar na minha primeira passagem através da lista? 1088 00:38:33,280 --> 00:38:36,620 Quantos pontos ele consegue mais próximo do local correto? 1089 00:38:36,620 --> 00:38:37,240 Apenas um. 1090 00:38:37,240 --> 00:38:40,281 Então, se você tipo de razão através deste, cada vez através deste algoritmo, 1091 00:38:40,281 --> 00:38:41,880 Tendo cerca de n passos de David. 1092 00:38:41,880 --> 00:38:44,940 Mas quantos passes a lista é 1093 00:38:44,940 --> 00:38:49,060 vai levar para um a bolha à esquerda, onde ele pertence? 1094 00:38:49,060 --> 00:38:51,840 >> Ele tem que se mover como, n espaços desta forma. 1095 00:38:51,840 --> 00:38:57,960 Então, só para fazer a triagem da lista, Eu tenho que andar para trás e n vezes. 1096 00:38:57,960 --> 00:39:01,540 E cada vez, estou olhando para n elementos. 1097 00:39:01,540 --> 00:39:05,410 Então, fazer as coisas n n vezes em da ordem de n ao quadrado. 1098 00:39:05,410 --> 00:39:07,220 >> Agora, vamos ver em alguns dos curtas que 1099 00:39:07,220 --> 00:39:10,440 são incorporados no próximo problema do CS50 definida, uma outra abordagem para estes, 1100 00:39:10,440 --> 00:39:13,490 mas por agora, vamos considerar apenas alguns outros tempos de execução, 1101 00:39:13,490 --> 00:39:16,840 especialmente se os triagem tomar um pouco de tempo para afundar. 1102 00:39:16,840 --> 00:39:21,790 O que é um algoritmo que vimos já que leva na ordem de n passos? 1103 00:39:21,790 --> 00:39:27,560 >> O que deve tomar uma série linear de passos que temos visto até agora? 1104 00:39:27,560 --> 00:39:29,350 O que é isso? 1105 00:39:29,350 --> 00:39:30,480 A pesquisa de diretório de telefone. 1106 00:39:30,480 --> 00:39:31,390 O primeiro algoritmo. 1107 00:39:31,390 --> 00:39:31,560 Certo? 1108 00:39:31,560 --> 00:39:33,650 Onde estamos linearmente à procura de Mike Smith? 1109 00:39:33,650 --> 00:39:34,150 De fato. 1110 00:39:34,150 --> 00:39:37,180 A partir da semana zero, quando eu comecei virando uma página de cada vez, 1111 00:39:37,180 --> 00:39:40,095 e eu mesmo disse que era uma espécie de um algoritmo sensação linear, 1112 00:39:40,095 --> 00:39:42,720 e tivemos que imagem na placa com a linha vermelha reta 1113 00:39:42,720 --> 00:39:44,678 eo amarelo em linha reta linha, aqueles eram de fato 1114 00:39:44,678 --> 00:39:46,810 algoritmos que são em grande ó de n. 1115 00:39:46,810 --> 00:39:50,680 >> Porque para encontrar Mike Smith em um telefone livro de n páginas, no pior caso, 1116 00:39:50,680 --> 00:39:52,422 pode me n passos tomar. 1117 00:39:52,422 --> 00:39:53,630 Que tal pegar atendimento? 1118 00:39:53,630 --> 00:39:55,790 Um dois três quatro cinco seis. 1119 00:39:55,790 --> 00:39:59,420 Qual é o tempo de execução deste algoritmo para fazer a chamada? 1120 00:39:59,420 --> 00:40:03,070 Big O de n, porque, em teoria I tem que apontar todos na sala. 1121 00:40:03,070 --> 00:40:05,861 >> Agora, como um aparte, que sobre o outra otimização de semana de zero? 1122 00:40:05,861 --> 00:40:08,117 Dois, quatro, seis, oito, 10, 12. 1123 00:40:08,117 --> 00:40:10,200 Um cientista da computação seria perceber, espere um minuto, 1124 00:40:10,200 --> 00:40:12,320 que é da ordem de n dividido por dois passos. 1125 00:40:12,320 --> 00:40:12,820 Certo? 1126 00:40:12,820 --> 00:40:14,444 Porque eu estou fazendo duas pessoas de cada vez. 1127 00:40:14,444 --> 00:40:17,015 Mas vamos ignorar esses termos de ordem mais baixa, 1128 00:40:17,015 --> 00:40:19,140 e nós apenas estamos indo para jogue fora a dividir por 2, 1129 00:40:19,140 --> 00:40:21,830 e apenas dizer, grande O de n para esse algoritmo bem. 1130 00:40:21,830 --> 00:40:22,760 >> Que tal este? 1131 00:40:22,760 --> 00:40:26,170 Vamos pular alguns destes, mas o que era um algoritmo que foi log de n? 1132 00:40:26,170 --> 00:40:29,900 Isso levou cerca de log n passos? 1133 00:40:29,900 --> 00:40:30,870 O dividir e conquistar. 1134 00:40:30,870 --> 00:40:31,369 Exatamente. 1135 00:40:31,369 --> 00:40:33,900 Como o exemplo do livro de telefone em semana zero e hoje cedo, 1136 00:40:33,900 --> 00:40:36,191 onde dividimos o problema de novo e de novo e de novo. 1137 00:40:36,191 --> 00:40:39,070 Nós chamou-o sobre a placa na semana zero como uma linha verde curvado, 1138 00:40:39,070 --> 00:40:41,460 e dissemos que dia era um algoritmo logarítmica. 1139 00:40:41,460 --> 00:40:44,970 >> E, de fato, o número de passos leva para realizar dividir e conquistar, 1140 00:40:44,970 --> 00:40:48,610 ou busca binária como nós vamos começar chamando-o, como no livro de telefone, 1141 00:40:48,610 --> 00:40:50,680 é da ordem de registo e etapas. 1142 00:40:50,680 --> 00:40:52,470 E isso é um pouco de um estranho. 1143 00:40:52,470 --> 00:40:54,910 >> O que leva uma única etapa, ou mais especificamente 1144 00:40:54,910 --> 00:40:56,240 um número constante de passos? 1145 00:40:56,240 --> 00:40:58,865 Talvez seja dois, talvez seja três, mas um cientista da computação apenas 1146 00:40:58,865 --> 00:41:01,423 simplifica-lo tão grande O de 1, um número constante de passos. 1147 00:41:01,423 --> 00:41:04,256 O que é algo que você poderia fazer isso tem um número constante de passos? 1148 00:41:04,256 --> 00:41:08,030 1149 00:41:08,030 --> 00:41:10,930 >> Qual é o tempo de execução de bater palmas? 1150 00:41:10,930 --> 00:41:11,920 Tempo constante. 1151 00:41:11,920 --> 00:41:12,420 Certo? 1152 00:41:12,420 --> 00:41:15,490 Como, qual é o tempo de execução de fazer qualquer coisa que leva apenas um 1153 00:41:15,490 --> 00:41:18,570 operação, como imprimir F Olá Mundo. 1154 00:41:18,570 --> 00:41:24,110 Isso pode ser considerado constante de tempo, a menos que menos caso esquina com a impressão F, 1155 00:41:24,110 --> 00:41:28,260 O que o tempo de execução de impressão F realmente ser? 1156 00:41:28,260 --> 00:41:28,790 E porque? 1157 00:41:28,790 --> 00:41:30,550 O que é de medição n nesse caso? 1158 00:41:30,550 --> 00:41:32,251 >> AUDIÊNCIA: [inaudível]. 1159 00:41:32,251 --> 00:41:33,250 DAVID J. MALAN: Exatamente. 1160 00:41:33,250 --> 00:41:34,900 O número de caracteres que pretende imprimir. 1161 00:41:34,900 --> 00:41:36,191 Portanto, é muito sensível ao contexto. 1162 00:41:36,191 --> 00:41:39,910 Hoje, temos vindo a apostar muito em letras e números aqui no conselho. 1163 00:41:39,910 --> 00:41:43,540 Mas também pode ser caracteres em uma seqüência real. 1164 00:41:43,540 --> 00:41:46,420 Assim, verifica-lá fora é outra medida que vai começar a se preocupar, 1165 00:41:46,420 --> 00:41:48,530 e isso é o oposto de grande O, por assim dizer. 1166 00:41:48,530 --> 00:41:50,120 >> Isso é notação omega. 1167 00:41:50,120 --> 00:41:53,380 Considerando que grande O significa o que é, o um limite superior ao seu tempo de execução? 1168 00:41:53,380 --> 00:41:55,580 No máximo, quanto tempo pode tomar alguma coisa? 1169 00:41:55,580 --> 00:41:59,250 Omega-- desculpe este continua vindo up-- é o oposto do que, 1170 00:41:59,250 --> 00:42:02,960 pelo que é um limite inferior na quantidade de tempo algo pode tomar. 1171 00:42:02,960 --> 00:42:10,480 >> Assim. por exemplo, o que é um algoritmo que toma medidas sempre n ao quadrado? 1172 00:42:10,480 --> 00:42:15,600 Bem, um dos algoritmos que temos visto Hoje em dia, na verdade, pode ser que como bem. 1173 00:42:15,600 --> 00:42:16,720 Tipo de seleção. 1174 00:42:16,720 --> 00:42:18,270 Seleção tipo é muito estúpido. 1175 00:42:18,270 --> 00:42:21,760 Mesmo que o algorithm-- desculpe, mesmo se a matriz já está classificado, 1176 00:42:21,760 --> 00:42:24,150 seleção tipo vai manter uma curta caminhada através da lista 1177 00:42:24,150 --> 00:42:28,907 para se certificar de que tem o menor elemento novo e de novo e de novo. 1178 00:42:28,907 --> 00:42:31,740 E mesmo que você os seres humanos no público sabe disso, espere um minuto, 1179 00:42:31,740 --> 00:42:33,948 você já passou o elemento mais pequeno, o computador 1180 00:42:33,948 --> 00:42:37,300 não sabe que até que parece todo o caminho através da lista. 1181 00:42:37,300 --> 00:42:40,240 Do mesmo modo, um limite inferior que também pode ser tida em conta 1182 00:42:40,240 --> 00:42:42,000 talvez seja tempo linear. 1183 00:42:42,000 --> 00:42:48,260 >> Quanto tempo leva para elementos tipo n no melhor 1184 00:42:48,260 --> 00:42:52,420 caso usando algo como bubble sort? 1185 00:42:52,420 --> 00:42:54,280 Suponha que a sua lista já está classificado. 1186 00:42:54,280 --> 00:42:56,696 Dissemos bubble sort assume da ordem de n ao quadrado etapas. 1187 00:42:56,696 --> 00:42:59,640 Mas e se ele já está classificado? 1188 00:42:59,640 --> 00:43:02,310 E se você perceber depois uma passagem através da matriz 1189 00:43:02,310 --> 00:43:03,540 que você fez há swaps? 1190 00:43:03,540 --> 00:43:05,970 Você precisa continuar a fazer mais passes? 1191 00:43:05,970 --> 00:43:06,470 >> Não. 1192 00:43:06,470 --> 00:43:10,340 Assim, um limite inferior na bubble sort pode ser dito para ser linear. 1193 00:43:10,340 --> 00:43:11,830 Omega de n. 1194 00:43:11,830 --> 00:43:14,450 E podemos olhar para outros de estes também. 1195 00:43:14,450 --> 00:43:17,990 Então, vamos dar uma olhada rápida em apenas uma visualização aqui 1196 00:43:17,990 --> 00:43:20,790 para ver como estes se distinguem. 1197 00:43:20,790 --> 00:43:24,592 Eu estou indo para ir para baixo aqui neste A página que está disponível no site do C50, 1198 00:43:24,592 --> 00:43:27,550 mas vai ser uma dor de começar a trabalhar, uma vez que utiliza uma tecnologia chamada 1199 00:43:27,550 --> 00:43:30,560 Applets Java, que é um em grande parte sem apoio nos dias de hoje, 1200 00:43:30,560 --> 00:43:32,730 pelo menos por Chrome e certos outros. 1201 00:43:32,730 --> 00:43:37,070 >> E deixe-me ir em frente e acelerar este e explicar o que está acontecendo. 1202 00:43:37,070 --> 00:43:40,840 Esta é uma demonstração de bolha tipo, o primeiro algoritmo de nós olhamos. 1203 00:43:40,840 --> 00:43:43,950 E é uma visualização em que cada destas barras representa um número. 1204 00:43:43,950 --> 00:43:45,710 Quanto maior for a barra, quanto maior o número. 1205 00:43:45,710 --> 00:43:47,520 Quanto menor o bar, Quanto menor o número. 1206 00:43:47,520 --> 00:43:50,353 E o que você pode ver visualmente, mesmo embora este está indo super rápido, 1207 00:43:50,353 --> 00:43:53,699 é que a barra vermelha é como eu, andando para trás e corrigir problemas. 1208 00:43:53,699 --> 00:43:56,740 Você pode ver que os elementos maiores são, na verdade borbulhando para a direita, 1209 00:43:56,740 --> 00:43:59,650 e os elementos menores está borbulhando para a esquerda. 1210 00:43:59,650 --> 00:44:01,870 E aqui, se nós realmente olhar mais de perto, 1211 00:44:01,870 --> 00:44:04,330 nós podemos realmente contar o número de comparações e swaps 1212 00:44:04,330 --> 00:44:05,350 que estavam sendo feitos. 1213 00:44:05,350 --> 00:44:07,360 >> Mas em vez disso, vamos olhar no segundo algoritmo 1214 00:44:07,360 --> 00:44:11,240 vimos anteriormente com o nosso voluntários, selecção de classificação. 1215 00:44:11,240 --> 00:44:13,500 Visualmente, tem um efeito muito diferente. 1216 00:44:13,500 --> 00:44:16,820 Mas é, de novo, muito intuitivo, em que mantemos selecionar o próximo menor 1217 00:44:16,820 --> 00:44:18,660 elemento, e temos um pouco de sorte. 1218 00:44:18,660 --> 00:44:20,110 Isso foi fundamentalmente mais rápido. 1219 00:44:20,110 --> 00:44:22,840 Mas se nós corremos esse novo e de novo e novamente com muitos insumos, 1220 00:44:22,840 --> 00:44:26,680 veríamos que ele é de fato ainda em grande O de n ao quadrado. 1221 00:44:26,680 --> 00:44:29,920 >> Vamos fazer um último aqui, ordenação por inserção, 1222 00:44:29,920 --> 00:44:33,180 que foi o terceiro algoritmo nós olhamos, ea recordação 1223 00:44:33,180 --> 00:44:36,700 que este lida com a como elementos que ele encontra-los, 1224 00:44:36,700 --> 00:44:39,290 Mas, então, talvez turnos coisas para abrir espaço, 1225 00:44:39,290 --> 00:44:41,660 inserção de elementos a que pertencem. 1226 00:44:41,660 --> 00:44:45,330 >> E isso também acaba dando o resultado final. Agora todos os três daqueles 1227 00:44:45,330 --> 00:44:46,490 senti muito rápido. 1228 00:44:46,490 --> 00:44:48,740 E, de fato, eu corri-los em um bom clip. 1229 00:44:48,740 --> 00:44:52,510 Mas, fundamentalmente, eles são todos bem horrível, para ser honesto. 1230 00:44:52,510 --> 00:44:56,960 Todos estes algoritmos até agora que são executados em grande O de n ao quadrado 1231 00:44:56,960 --> 00:44:59,270 tomar um pouco de tempo para ser executado no final. 1232 00:44:59,270 --> 00:45:01,920 >> E, de fato, podemos ver e sinto que este, por último, 1233 00:45:01,920 --> 00:45:04,090 se eu puxar para cima esta terceira e última demonstração. 1234 00:45:04,090 --> 00:45:05,840 Este é outro visualização que está acontecendo 1235 00:45:05,840 --> 00:45:08,500 para mostrar bubble sort à esquerda, tipo de seleção no meio, 1236 00:45:08,500 --> 00:45:13,410 e alguma coisa, como um de nossos mão levanta mais cedo sugeriu, 1237 00:45:13,410 --> 00:45:15,020 merge sort à direita. 1238 00:45:15,020 --> 00:45:16,937 Um dividir e conquistar estratégia à direita. 1239 00:45:16,937 --> 00:45:19,520 E isso é, na verdade, o que nós somos indo olhar na quarta-feira. 1240 00:45:19,520 --> 00:45:21,990 Mas o tempo estes funcionem em paralelo vamos. 1241 00:45:21,990 --> 00:45:26,765 É mais ou menos o mesmo número de elementos, todos rodando ao mesmo tempo. 1242 00:45:26,765 --> 00:45:30,940 1243 00:45:30,940 --> 00:45:34,440 Bubble sort vs seleção tipo vs merge sort. 1244 00:45:34,440 --> 00:45:36,760 >> Agora, eles estão todos correndo em teoria, ao mesmo tempo. 1245 00:45:36,760 --> 00:45:39,830 A CPU está sendo executado em a mesma velocidade, mas você 1246 00:45:39,830 --> 00:45:44,014 pode sentir-se como chato isso é indo muito rapidamente para se tornar, 1247 00:45:44,014 --> 00:45:45,930 e quão rápido quando nós injetar um pouco de semana 1248 00:45:45,930 --> 00:45:49,330 algoritmos do zero pode que acelerar as coisas. 1249 00:45:49,330 --> 00:45:51,760 >> E agora vamos comparar estes em uma última forma. 1250 00:45:51,760 --> 00:45:55,710 Eu estou indo para ir em frente para o site do CS50, onde 1251 00:45:55,710 --> 00:45:59,020 temos este elo final para hoje, onde alguém na internet 1252 00:45:59,020 --> 00:46:03,960 gentilmente montar um vídeo que capta o que ordenação diferente 1253 00:46:03,960 --> 00:46:07,510 algoritmos soam como. 1254 00:46:07,510 --> 00:46:09,577 Esta é a ordenação por inserção. 1255 00:46:09,577 --> 00:46:12,072 >> [BIPE] 1256 00:46:12,072 --> 00:46:13,070 1257 00:46:13,070 --> 00:46:16,850 >> Através do qual você está aplicando uma frequência com base na altura da barra de barra. 1258 00:46:16,850 --> 00:46:19,826 Esta é bubble sort. 1259 00:46:19,826 --> 00:46:21,822 >> [BIPE Warped] 1260 00:46:21,822 --> 00:46:33,299 1261 00:46:33,299 --> 00:46:45,774 >> Chegando próximo é-- vindo ao lado espécie seleção é--, 1262 00:46:45,774 --> 00:46:48,820 onde mais uma vez, estamos selecionando o próximo elemento mais pequeno, 1263 00:46:48,820 --> 00:46:51,820 e podemos vê-lo crescer da esquerda para a direita. 1264 00:46:51,820 --> 00:47:01,120 1265 00:47:01,120 --> 00:47:04,000 >> Merge sort, o nosso vencedor, até agora, hoje. 1266 00:47:04,000 --> 00:47:09,659 1267 00:47:09,659 --> 00:47:12,450 Observe como ele está dividindo as coisas em [inaudível] a metade e trimestres. 1268 00:47:12,450 --> 00:47:17,510 1269 00:47:17,510 --> 00:47:21,660 Tipo Gnome, que não tem falou, e cria visualmente 1270 00:47:21,660 --> 00:47:24,450 e audally um pouco de forma e som diferente. 1271 00:47:24,450 --> 00:47:27,060 1272 00:47:27,060 --> 00:47:30,160 Indo e voltando, limpar as coisas. 1273 00:47:30,160 --> 00:47:32,230 Também check out heapsort no site do cara. 1274 00:47:32,230 --> 00:47:36,100 1275 00:47:36,100 --> 00:47:36,810 >> E é isso. 1276 00:47:36,810 --> 00:47:38,210 Vamos vê-lo na próxima vez. 1277 00:47:38,210 --> 00:47:42,647 1278 00:47:42,647 --> 00:47:48,334 >> [Whooshing E MÚSICA] 1279 00:47:48,334 --> 00:50:24,839