1 00:00:00,000 --> 00:00:11,100 2 00:00:11,100 --> 00:00:12,300 >> COLUNA 1: Olá a todos! 3 00:00:12,300 --> 00:00:13,890 Bem-vindo de volta à seção. 4 00:00:13,890 --> 00:00:17,480 Tão feliz de ver tantos de vocês, tanto aqui, e todo mundo que está assistindo online. 5 00:00:17,480 --> 00:00:18,760 6 00:00:18,760 --> 00:00:20,920 Assim, como bem-vindo de volta habitual. 7 00:00:20,920 --> 00:00:24,360 Espero que todos tenham tido um lindo fim de semana, cheio de descanso, relaxamento. 8 00:00:24,360 --> 00:00:26,026 Foi lindo ontem. 9 00:00:26,026 --> 00:00:27,525 Então, espero que tenham gostado do ar livre. 10 00:00:27,525 --> 00:00:28,840 11 00:00:28,840 --> 00:00:30,610 >> Então, primeiro de um par de anúncios. 12 00:00:30,610 --> 00:00:31,920 13 00:00:31,920 --> 00:00:32,700 Grading. 14 00:00:32,700 --> 00:00:37,350 Assim, a maioria de vocês deve ter ficado um enviar e-mail de mim sobre o seu Pset Scratch 15 00:00:37,350 --> 00:00:39,920 bem como classificação para Pset 1. 16 00:00:39,920 --> 00:00:41,000 17 00:00:41,000 --> 00:00:42,220 Assim, apenas um par de coisas. 18 00:00:42,220 --> 00:00:45,150 Certifique-se de usar check50 em style50. 19 00:00:45,150 --> 00:00:47,250 Estas são destinadas a ser recursos para vocês, 20 00:00:47,250 --> 00:00:50,660 para se certificar de que você está recebendo tantos pontos como você pode 21 00:00:50,660 --> 00:00:52,390 sem perdê-los desnecessariamente. 22 00:00:52,390 --> 00:00:54,407 Então, coisas como estilo são muito importantes. 23 00:00:54,407 --> 00:00:55,740 Nós estamos indo para decolar para ele. 24 00:00:55,740 --> 00:00:58,115 Alguns de vocês já podem ter notado que a partir de seu Pset. 25 00:00:58,115 --> 00:00:58,920 26 00:00:58,920 --> 00:01:01,450 E check50 é apenas um maneira muito fácil de se certificar 27 00:01:01,450 --> 00:01:05,050 que na verdade estamos devolvendo o que necessita de ser devolvida para o utilizador, 28 00:01:05,050 --> 00:01:06,690 e que tudo está funcionando corretamente. 29 00:01:06,690 --> 00:01:08,690 30 00:01:08,690 --> 00:01:12,040 >> Na segunda nota, certifique-se o seu upload coisas para a pasta correta. 31 00:01:12,040 --> 00:01:14,470 Faz minha vida apenas um pouco mais difícil 32 00:01:14,470 --> 00:01:18,836 se você carregar Pset 2 em 1 Pset porque quando eu baixar coisas, 33 00:01:18,836 --> 00:01:20,085 eles não baixar corretamente. 34 00:01:20,085 --> 00:01:21,690 35 00:01:21,690 --> 00:01:24,560 E eu sei que é um pouco instável, em um sistema para se acostumar, 36 00:01:24,560 --> 00:01:26,950 mas apenas ser super cuidado, se só para mim, 37 00:01:26,950 --> 00:01:30,080 de modo que quando você está recebendo e-mails em como 2:00 e eu sou de classificação. 38 00:01:30,080 --> 00:01:33,710 Se não causar eu tenho que olhar tudo em torno de sua Pset. 39 00:01:33,710 --> 00:01:34,440 Legal. 40 00:01:34,440 --> 00:01:37,270 >> Eu sei que é cedo, mas eu totalmente fui pego de surpresa 41 00:01:37,270 --> 00:01:40,800 por um ensaio que é devido esta sexta-feira, que meus professores foram apenas como, oh sim. 42 00:01:40,800 --> 00:01:42,550 Lembre-se, você tem um ensaio devido na sexta-feira. 43 00:01:42,550 --> 00:01:45,780 Então, eu sei que ninguém gosta para pensar midterms, 44 00:01:45,780 --> 00:01:50,620 mas seu primeiro teste é em 15 de outubro, que outubro é a partir desta semana. 45 00:01:50,620 --> 00:01:53,290 Assim, pode ser mais cedo do que o esperado é tudo. 46 00:01:53,290 --> 00:01:57,510 Assim que você não está jogado de surpresa quando Menciono seção da próxima semana que oh, 47 00:01:57,510 --> 00:02:00,560 seu teste na próxima semana, eu pensei Eu te daria um pouco mais 48 00:02:00,560 --> 00:02:01,500 de um heads-up agora. 49 00:02:01,500 --> 00:02:02,970 50 00:02:02,970 --> 00:02:04,660 >> Assim, seu conjunto de problemas, o número três. 51 00:02:04,660 --> 00:02:07,070 Como as pessoas leram o especificação por curiosidade? 52 00:02:07,070 --> 00:02:08,560 53 00:02:08,560 --> 00:02:09,199 Está bem. 54 00:02:09,199 --> 00:02:10,229 Temos um casal. 55 00:02:10,229 --> 00:02:12,320 Tipo de baixo da última semana, mas isso é OK. 56 00:02:12,320 --> 00:02:13,650 Eu sei que era belo fora. 57 00:02:13,650 --> 00:02:15,120 58 00:02:15,120 --> 00:02:16,660 Então Break Out. 59 00:02:16,660 --> 00:02:21,010 Definitivamente depois de ter feito ler hoje a sua especificação, pelo menos, 60 00:02:21,010 --> 00:02:25,240 tente como download código de distribuição e execução 61 00:02:25,240 --> 00:02:27,430 como a primeira inicial coisa que pedir para você. 62 00:02:27,430 --> 00:02:28,681 63 00:02:28,681 --> 00:02:32,590 Como estamos usando código de distribuição e uma biblioteca 64 00:02:32,590 --> 00:02:36,790 que só tenho using-- --É só é a segunda vez que fiz isso Pset, 65 00:02:36,790 --> 00:02:38,650 coisas malucas pode acontecer com o seu aparelho, 66 00:02:38,650 --> 00:02:41,370 e você quer descobrir que para fora agora contra mais tarde. 67 00:02:41,370 --> 00:02:45,570 >> Porque se é noite de quinta ou é Quarta-feira e, por algum motivo 68 00:02:45,570 --> 00:02:48,912 o aparelho simplesmente não faz quero correr com a biblioteca 69 00:02:48,912 --> 00:02:50,620 ou com a distribuição código, o que significa 70 00:02:50,620 --> 00:02:52,309 você não pode sequer começar a fazer a codificação. 71 00:02:52,309 --> 00:02:54,100 Porque você não pode verificar para ver se funciona. 72 00:02:54,100 --> 00:02:55,975 O seu não vai ser capaz para ver se ele compila. 73 00:02:55,975 --> 00:03:00,500 Você quer cuidar das pessoas no início semana, quando você ainda pode enviar e-mail me 74 00:03:00,500 --> 00:03:03,100 ou um dos outros FT, e podemos obter os fixados. 75 00:03:03,100 --> 00:03:05,410 Porque essas são questões que vão pará-lo 76 00:03:05,410 --> 00:03:07,120 de fazer qualquer progresso real. 77 00:03:07,120 --> 00:03:10,055 Não é como um bug, que você pode apenas uma espécie de pular. 78 00:03:10,055 --> 00:03:10,712 79 00:03:10,712 --> 00:03:13,420 Se você está tendo problemas com o seu aparelho ou código de distribuição, 80 00:03:13,420 --> 00:03:16,211 você realmente quiser se que tomadas cuidar de, mais cedo ou mais tarde. 81 00:03:16,211 --> 00:03:20,410 Assim, mesmo se você não está indo realmente iniciar a codificação, baixar a distribuição 82 00:03:20,410 --> 00:03:24,040 código, leia a especificação, certifique-se tudo está funcionando lá. 83 00:03:24,040 --> 00:03:25,134 Ok? 84 00:03:25,134 --> 00:03:27,675 Se você só pode fazer isso, eu prometer sua vida será mais fácil. 85 00:03:27,675 --> 00:03:28,800 86 00:03:28,800 --> 00:03:31,410 E assim, você provavelmente vai para fazê-lo agora certo? 87 00:03:31,410 --> 00:03:32,100 Está bem. 88 00:03:32,100 --> 00:03:33,950 Assim, todas as perguntas lá? 89 00:03:33,950 --> 00:03:35,850 Quaisquer coisas de logística? 90 00:03:35,850 --> 00:03:36,910 Todo mundo é bom? 91 00:03:36,910 --> 00:03:38,270 Está bem. 92 00:03:38,270 --> 00:03:41,700 >> Disclaimer para aqueles de você no quarto e online. 93 00:03:41,700 --> 00:03:45,437 Vou estar tentando mudar entre PowerPoint no aparelho 94 00:03:45,437 --> 00:03:47,270 porque nós estamos indo estar fazendo alguma codificação 95 00:03:47,270 --> 00:03:53,630 hoje pela demanda popular do anonymous sugestão enquete eu enviei na semana passada. 96 00:03:53,630 --> 00:03:55,480 Então, vamos fazer alguma codificação. 97 00:03:55,480 --> 00:03:57,800 Então, se vocês também querem ao fogo até seus aparelhos, 98 00:03:57,800 --> 00:04:02,910 e você deve ter conseguido um e-mail de mim, com um arquivo de exemplo. 99 00:04:02,910 --> 00:04:04,310 Por favor, sinta-se livre para fazer isso. 100 00:04:04,310 --> 00:04:07,340 >> Então, vamos falar sobre GDB, que é um depurador. 101 00:04:07,340 --> 00:04:09,970 Ele vai ajudar você tipo de descobrir onde 102 00:04:09,970 --> 00:04:11,860 as coisas vão mal no seu código. 103 00:04:11,860 --> 00:04:15,370 É realmente apenas uma maneira de você para a etapa através de seu código que está acontecendo, 104 00:04:15,370 --> 00:04:19,100 e ser capaz de imprimir variáveis ou ver o que está realmente acontecendo 105 00:04:19,100 --> 00:04:22,980 sob o capô versículos seu programa apenas correr, é como falha, 106 00:04:22,980 --> 00:04:25,030 e você fica tipo, nenhuma idéia o que aconteceu aqui. 107 00:04:25,030 --> 00:04:26,730 Eu não sei o que ele falhou na linha. 108 00:04:26,730 --> 00:04:29,040 Eu não sei onde ele errou. 109 00:04:29,040 --> 00:04:31,280 Então, GDB vai te ajudar com isso. 110 00:04:31,280 --> 00:04:35,240 Além disso, se você decidir continuar sim, e ter 61, 111 00:04:35,240 --> 00:04:38,430 ele vai realmente ser o seu melhor amigo, porque eu posso te dizer 112 00:04:38,430 --> 00:04:40,840 porque eu estou passando por essa classe. 113 00:04:40,840 --> 00:04:43,620 >> Nós vamos olhar para binário pesquisa, que se vocês se lembrar 114 00:04:43,620 --> 00:04:47,540 o grande exemplo de catálogo telefônico espetáculo de classe. 115 00:04:47,540 --> 00:04:50,620 Nós estaremos implementando isso, e caminhando por isso um pouco mais, 116 00:04:50,620 --> 00:04:54,650 e então nós estamos passando por quatro diferentes tipos, que são bolha, 117 00:04:54,650 --> 00:04:56,285 Seleção, Inserção, e mesclar. 118 00:04:56,285 --> 00:04:57,830 119 00:04:57,830 --> 00:04:58,330 Legal. 120 00:04:58,330 --> 00:05:00,390 Então, GDB como mencionei, é um depurador. 121 00:05:00,390 --> 00:05:01,400 122 00:05:01,400 --> 00:05:09,370 E estes são uma espécie de grande coisas, as grandes funções ou comandos 123 00:05:09,370 --> 00:05:13,240 que você usa dentro GDB, e eu andarei você através de uma demonstração de que em um segundo. 124 00:05:13,240 --> 00:05:15,360 >> Portanto, este não é apenas vai ficar abstrato. 125 00:05:15,360 --> 00:05:18,000 Vou tentar fazê-lo como concreto possível para vocês. 126 00:05:18,000 --> 00:05:19,870 Então, quebrar. 127 00:05:19,870 --> 00:05:22,200 Ele quer estará pausa como, um número, que 128 00:05:22,200 --> 00:05:26,900 representa uma linha em seu programa, ou pode nomear uma função. 129 00:05:26,900 --> 00:05:30,150 Então, se você diz quebrar principal, ele vai parar em principal, 130 00:05:30,150 --> 00:05:32,400 e deixá-lo andar por essa função. 131 00:05:32,400 --> 00:05:36,350 >> Da mesma forma, se você tem alguma externo funcionam como Trocar ou Cube, 132 00:05:36,350 --> 00:05:38,450 que olhou para a semana passada. 133 00:05:38,450 --> 00:05:41,780 Se você disser que quebrar um daqueles, sempre que o seu programa de bate que, 134 00:05:41,780 --> 00:05:44,290 ele vai esperar para você diga a ele o que fazer. 135 00:05:44,290 --> 00:05:47,860 Antes ele só vai executar para que você realmente pode pisar dentro da função 136 00:05:47,860 --> 00:05:49,020 e ver o que está acontecendo. 137 00:05:49,020 --> 00:05:50,370 138 00:05:50,370 --> 00:05:53,515 Então, da próxima, apenas ignora o próxima linha, vai mais funções. 139 00:05:53,515 --> 00:05:54,730 140 00:05:54,730 --> 00:05:55,560 Step. 141 00:05:55,560 --> 00:05:56,810 Estas são todas pouco abstrato. 142 00:05:56,810 --> 00:06:00,530 Então, eu estou indo só para passar por eles, mas você vai vê-los em uso em um segundo. 143 00:06:00,530 --> 00:06:01,810 >> Entrar em uma função. 144 00:06:01,810 --> 00:06:04,170 Então, como eu estava dizendo, como com swap, que seria 145 00:06:04,170 --> 00:06:07,110 permitem que você, na verdade, se você estiver como entrar fisicamente no interior, 146 00:06:07,110 --> 00:06:10,990 você pode mexer com essas variáveis, impressão o que eles são, ver o que está acontecendo. 147 00:06:10,990 --> 00:06:12,140 148 00:06:12,140 --> 00:06:14,830 Lista vai literalmente apenas imprimir o código circundante. 149 00:06:14,830 --> 00:06:17,570 Então, se você tipo de esquecer onde você está no seu programa, 150 00:06:17,570 --> 00:06:19,880 ou você está se perguntando o que está acontecendo ao seu redor, 151 00:06:19,880 --> 00:06:23,790 isso só vai imprimir um segmento de como cinco ou seis linhas em torno dele. 152 00:06:23,790 --> 00:06:26,080 Assim, você pode se orientar sobre onde você está. 153 00:06:26,080 --> 00:06:27,230 154 00:06:27,230 --> 00:06:28,650 >> Imprimir alguma variável. 155 00:06:28,650 --> 00:06:34,590 Então, se você tem a chave como em César, que vamos olhar. 156 00:06:34,590 --> 00:06:36,220 Você pode dizer-chave impressão em qualquer ponto. 157 00:06:36,220 --> 00:06:40,070 Ele vai dizer-lhe que o valor é tão que, talvez em algum lugar ao longo do caminho, 158 00:06:40,070 --> 00:06:42,070 você substituiu a sua chave. 159 00:06:42,070 --> 00:06:45,495 Você pode realmente dizer que, por causa você pode realmente observar esse valor. 160 00:06:45,495 --> 00:06:46,500 161 00:06:46,500 --> 00:06:48,780 >> Nos locais, apenas impressões as suas variáveis ​​locais. 162 00:06:48,780 --> 00:06:53,120 Então, quando você está dentro de um loop, e você só quer ver como, oh. 163 00:06:53,120 --> 00:06:54,270 Qual é o meu eu? 164 00:06:54,270 --> 00:06:57,020 O que é este valor de chave que eu inicializar aqui? 165 00:06:57,020 --> 00:06:58,537 Qual é a mensagem neste momento? 166 00:06:58,537 --> 00:07:00,370 Ela só vai imprimir tudo daqueles, de maneira a ficar 167 00:07:00,370 --> 00:07:04,330 não tem que individualmente dizer, I. Imprimir Imprimir mensagem. 168 00:07:04,330 --> 00:07:04,970 Imprimir Key. 169 00:07:04,970 --> 00:07:06,190 170 00:07:06,190 --> 00:07:07,700 E em seguida, exibir. 171 00:07:07,700 --> 00:07:10,370 O que faz é como você passo através do programa, 172 00:07:10,370 --> 00:07:13,980 ele só vai ter certeza de que ele é exibindo alguns determinada variável 173 00:07:13,980 --> 00:07:14,780 em todos os pontos. 174 00:07:14,780 --> 00:07:17,160 Para que você Também-- --é uma espécie de atalho, onde 175 00:07:17,160 --> 00:07:19,530 você não tem que continuar assim, oh. 176 00:07:19,530 --> 00:07:23,150 Chave de impressão ou impressão I. Ele só irá automaticamente fazer isso por você. 177 00:07:23,150 --> 00:07:25,959 >> Então, com isso, vamos para ver como isso vai. 178 00:07:25,959 --> 00:07:28,000 Eu vou tentar e interruptor para o meu aparelho. 179 00:07:28,000 --> 00:07:30,200 180 00:07:30,200 --> 00:07:31,271 Veja se eu posso fazer isso. 181 00:07:31,271 --> 00:07:31,770 All. 182 00:07:31,770 --> 00:07:40,970 183 00:07:40,970 --> 00:07:42,370 Nós apenas estamos indo para espelhar-lo. 184 00:07:42,370 --> 00:07:44,530 Não há nada de louco no meu laptop de qualquer maneira. 185 00:07:44,530 --> 00:07:49,600 186 00:07:49,600 --> 00:07:50,100 Está bem. 187 00:07:50,100 --> 00:07:57,030 188 00:07:57,030 --> 00:08:01,054 Isso precisa ser um presente. 189 00:08:01,054 --> 00:08:01,795 É tão pequena. 190 00:08:01,795 --> 00:08:03,730 191 00:08:03,730 --> 00:08:05,120 Vamos ver se podemos fazer isso. 192 00:08:05,120 --> 00:08:09,970 193 00:08:09,970 --> 00:08:10,940 >> Está bem. 194 00:08:10,940 --> 00:08:15,305 Alice está obviamente lutando aqui só um pouco, 195 00:08:15,305 --> 00:08:17,995 mas nós vamos buscá-la em um momento. 196 00:08:17,995 --> 00:08:20,810 197 00:08:20,810 --> 00:08:22,020 Está bem. 198 00:08:22,020 --> 00:08:25,900 Nós apenas estamos indo para aumentar isso. 199 00:08:25,900 --> 00:08:28,770 200 00:08:28,770 --> 00:08:29,380 Está bem. 201 00:08:29,380 --> 00:08:31,679 Todos podem ver que tipo de? 202 00:08:31,679 --> 00:08:32,470 Talvez um pouco? 203 00:08:32,470 --> 00:08:33,594 Eu sei que é um pouco pequeno. 204 00:08:33,594 --> 00:08:34,570 205 00:08:34,570 --> 00:08:37,530 Você não consegue descobrir como fazer esta maior. 206 00:08:37,530 --> 00:08:38,350 Se alguém souber. 207 00:08:38,350 --> 00:08:40,309 Alguém sabe como fazê-lo maior? 208 00:08:40,309 --> 00:08:40,932 Está bem. 209 00:08:40,932 --> 00:08:42,140 Nós vamos rolar com ele. 210 00:08:42,140 --> 00:08:45,801 Não importa de qualquer maneira, porque é só esse é o código que vocês deveriam 211 00:08:45,801 --> 00:08:46,300 ter. 212 00:08:46,300 --> 00:08:48,310 >> O que é mais importante é o terminal aqui. 213 00:08:48,310 --> 00:08:52,840 214 00:08:52,840 --> 00:08:58,690 E nós temos aqui Por que é tão pequeno? 215 00:08:58,690 --> 00:09:02,325 216 00:09:02,325 --> 00:09:02,825 Configurações. 217 00:09:02,825 --> 00:09:07,920 218 00:09:07,920 --> 00:09:08,420 Oh. 219 00:09:08,420 --> 00:09:09,500 Verdadeiro Ike. 220 00:09:09,500 --> 00:09:10,880 Como é isso? 221 00:09:10,880 --> 00:09:11,770 Fora de lá. 222 00:09:11,770 --> 00:09:19,370 223 00:09:19,370 --> 00:09:21,810 Isso é melhor para todos? 224 00:09:21,810 --> 00:09:22,525 Está bem ,. 225 00:09:22,525 --> 00:09:23,025 Legal. 226 00:09:23,025 --> 00:09:25,830 227 00:09:25,830 --> 00:09:28,220 >> Sabe quando você está em um CS classe dificuldades técnicas 228 00:09:28,220 --> 00:09:32,971 são uma espécie de parte de as-- Então, vamos esclarecer isso. 229 00:09:32,971 --> 00:09:33,470 Está bem. 230 00:09:33,470 --> 00:09:38,060 Então, aqui na seção, que tivemos aqui. 231 00:09:38,060 --> 00:09:40,830 César é um arquivo executável. 232 00:09:40,830 --> 00:09:41,800 Então eu fiz isso. 233 00:09:41,800 --> 00:09:46,370 Então, uma coisa a perceber é com o GDB que ele só funciona em arquivos executáveis. 234 00:09:46,370 --> 00:09:48,040 Então, você não pode executá-lo em um Dotsy. 235 00:09:48,040 --> 00:09:50,532 Você tem que realmente fazer Certifique-se de que o seu código é compilado, 236 00:09:50,532 --> 00:09:51,865 e que, na verdade, pode ser executado. 237 00:09:51,865 --> 00:09:52,970 238 00:09:52,970 --> 00:09:56,186 >> Então, certifique-se de que, se isso não acontecer compilar, obtê-lo para compilar, 239 00:09:56,186 --> 00:09:57,810 de modo que você pode tipo de correr com ele. 240 00:09:57,810 --> 00:10:04,590 Então, para começar GDB, tudo que você faz, Gloria tipo GDB, e então apenas o 241 00:10:04,590 --> 00:10:06,250 arquivo que você deseja. 242 00:10:06,250 --> 00:10:08,240 Eu sempre cometer erros de ortografia César. 243 00:10:08,240 --> 00:10:11,730 Mas você quer ter a certeza já que é um executável, 244 00:10:11,730 --> 00:10:14,210 Flash ponto de ti para que significa que você vai 245 00:10:14,210 --> 00:10:19,240 para executar CSI você está indo para executar este arquivos ou com o depurador. 246 00:10:19,240 --> 00:10:19,910 Está bem. 247 00:10:19,910 --> 00:10:22,885 Então, você que, você começa este tipo de rabiscos. 248 00:10:22,885 --> 00:10:24,250 249 00:10:24,250 --> 00:10:25,750 É apenas sobre todas as coisas depurador. 250 00:10:25,750 --> 00:10:28,200 Você realmente não tem que se preocupe com isso agora. 251 00:10:28,200 --> 00:10:31,460 E como você pode ver, temos esta parênteses em aberto, o PIB, parênteses próximos, 252 00:10:31,460 --> 00:10:34,690 e apenas se parece com nossa linha de comando, certo? 253 00:10:34,690 --> 00:10:37,010 >> Então, o que nós queremos fazer-- --So, A primeira coisa 254 00:10:37,010 --> 00:10:39,570 é que nós queremos escolher um lugar para quebrá-lo. 255 00:10:39,570 --> 00:10:42,332 Então, há um bug neste programa Caesar 256 00:10:42,332 --> 00:10:44,290 que apresento, que vamos descobrir. 257 00:10:44,290 --> 00:10:45,330 258 00:10:45,330 --> 00:10:56,350 É o que faz é que leva a entrada Barfoo em todas as tampas, e por alguma razão 259 00:10:56,350 --> 00:11:01,950 isso não muda A. Ele só deixa sozinho, é tudo mais correta, 260 00:11:01,950 --> 00:11:03,980 mas a segunda letra A permanece inalterado. 261 00:11:03,980 --> 00:11:07,120 Então, nós estamos indo para tentar descobrir por que isso acontece. 262 00:11:07,120 --> 00:11:10,440 Então, a primeira coisa que você normalmente quero fazer sempre que você começar em GDB 263 00:11:10,440 --> 00:11:12,010 é descobrir onde a quebrá-lo. 264 00:11:12,010 --> 00:11:14,956 >> Então, César é um pequena programa. 265 00:11:14,956 --> 00:11:16,330 Nós só temos uma função, certo? 266 00:11:16,330 --> 00:11:18,520 Qual foi a nossa função no Caesar? 267 00:11:18,520 --> 00:11:19,590 268 00:11:19,590 --> 00:11:24,350 Há apenas uma função, certo Main? 269 00:11:24,350 --> 00:11:26,490 Principal é uma função para todos os seus programas. 270 00:11:26,490 --> 00:11:29,230 Se você não tem Main, eu poderia ser um pouco preocupado agora, 271 00:11:29,230 --> 00:11:31,000 mas espero que todos tenham tido principal lá. 272 00:11:31,000 --> 00:11:34,150 Então, o que podemos fazer é que podemos apenas quebrar principal, apenas como aquele. 273 00:11:34,150 --> 00:11:35,190 Assim, ele diz, OK. 274 00:11:35,190 --> 00:11:37,430 Montamos nosso único breakpoint lá. 275 00:11:37,430 --> 00:11:42,870 >> Então, agora a coisa a lembrar é de César leva um argumento de linha de comando para a direita 276 00:11:42,870 --> 00:11:45,150 e nós não temos feito isso em qualquer lugar ainda. 277 00:11:45,150 --> 00:11:47,560 Então, o que você faz é quando você realmente ir a correr 278 00:11:47,560 --> 00:11:51,540 o programa, qualquer programa que você está funcionando em GDB que precisa de linha de comando 279 00:11:51,540 --> 00:11:55,010 argumentos, você está indo para a entrada quando você começar a executá-lo. 280 00:11:55,010 --> 00:11:59,280 Então, neste caso, o que fazemos Corra com uma chave de três. 281 00:11:59,280 --> 00:12:00,770 282 00:12:00,770 --> 00:12:02,040 E ele vai realmente começar. 283 00:12:02,040 --> 00:12:08,480 >> Então, se você vê aqui, temos Se RC não é igual a 2. 284 00:12:08,480 --> 00:12:12,210 Então, se vocês todos têm esse arquivo que eu enviei-se 285 00:12:12,210 --> 00:12:15,100 você vai ver que isso é como o primeira linha a nossa função principal, certo? 286 00:12:15,100 --> 00:12:17,890 Ele está verificando para ver se temos o número correto de argumentos. 287 00:12:17,890 --> 00:12:20,620 Então, se você está se perguntando RC se está correto, 288 00:12:20,620 --> 00:12:23,250 você pode fazer algo como impressão RC. 289 00:12:23,250 --> 00:12:24,380 290 00:12:24,380 --> 00:12:28,640 RC é de dois, que é o que esperávamos, certo? 291 00:12:28,640 --> 00:12:32,010 >> Então, podemos ir Em seguida, e continuam até. 292 00:12:32,010 --> 00:12:33,200 Então, nós temos alguma chave lá. 293 00:12:33,200 --> 00:12:34,260 294 00:12:34,260 --> 00:12:37,090 E podemos imprimir nossa chave para se certificar de que está correto. 295 00:12:37,090 --> 00:12:38,380 296 00:12:38,380 --> 00:12:39,500 Interessante. 297 00:12:39,500 --> 00:12:41,210 Não é bem o que esperávamos. 298 00:12:41,210 --> 00:12:44,810 Então, uma coisa a perceber com o GDB também, é 299 00:12:44,810 --> 00:12:49,000 que não é até que você realmente acertar Em seguida, que a linha que você acabou de ver 300 00:12:49,000 --> 00:12:50,720 é realmente executada. 301 00:12:50,720 --> 00:12:53,870 Assim, neste caso Key não tenha ainda sido atribuído. 302 00:12:53,870 --> 00:12:57,050 Então, Key é algum valor de lixo que você vê na parte inferior lá. 303 00:12:57,050 --> 00:13:03,680 Negativo $ 120-- --é um bilhão e algo que coisas estranhas certo? 304 00:13:03,680 --> 00:13:05,340 Não é a chave que esperávamos. 305 00:13:05,340 --> 00:13:10,720 Mas se nós batemos em Avançar e, em seguida, tentar chave de impressão, é três. 306 00:13:10,720 --> 00:13:11,710 >> Todo mundo vê isso? 307 00:13:11,710 --> 00:13:13,780 Então, se você conseguir alguma coisa que você gosta, espere. 308 00:13:13,780 --> 00:13:15,540 Isto é completamente errado, e eu não sei 309 00:13:15,540 --> 00:13:20,150 como isso iria acontecer, porque tudo que eu quero fazer é atribuir um número, uma variável, 310 00:13:20,150 --> 00:13:22,900 tentar bater seguida, tente imprimir de novo, e ver se isso funciona. 311 00:13:22,900 --> 00:13:27,830 Porque ele só vai executar e na verdade, atribuir alguma coisa depois que você 312 00:13:27,830 --> 00:13:29,340 clique em Next. 313 00:13:29,340 --> 00:13:30,336 Fazer sentido para todos? 314 00:13:30,336 --> 00:13:30,836 Uh huh? 315 00:13:30,836 --> 00:13:33,220 >> COLUNA 2: Quando você aleatório números o que isso significa? 316 00:13:33,220 --> 00:13:34,790 >> COLUNA 1: É apenas aleatória. 317 00:13:34,790 --> 00:13:35,710 É apenas lixo. 318 00:13:35,710 --> 00:13:38,320 É apenas algo que o seu computador irá atribuir ao acaso. 319 00:13:38,320 --> 00:13:39,721 320 00:13:39,721 --> 00:13:40,220 Legal. 321 00:13:40,220 --> 00:13:45,760 Então, agora podemos passar através, e assim por agora temos este GetString texto simples. 322 00:13:45,760 --> 00:13:48,600 Então, deixe-me apresentar o que vai acontecer quando nós batemos seguida aqui. 323 00:13:48,600 --> 00:13:51,320 Nossa GDB tipo de desaparece, certo? 324 00:13:51,320 --> 00:13:55,720 Isso porque GetString agora está em execução, certo? 325 00:13:55,720 --> 00:14:01,460 Então, quando vimos texto simples é igual a GetString, parênteses abertos e parênteses, 326 00:14:01,460 --> 00:14:04,380 e clique em Next, que tem realmente executada agora. 327 00:14:04,380 --> 00:14:06,580 Então, ele está esperando por nos a entrada de algo. 328 00:14:06,580 --> 00:14:13,560 >> Então, nós estamos indo para a entrada a nossa comida que é o que está falhando, como eu disse a você 329 00:14:13,560 --> 00:14:18,020 e que apenas diz que é terminar a execução, que o fechou 330 00:14:18,020 --> 00:14:19,980 suporte significa que é sai fora desse circuito. 331 00:14:19,980 --> 00:14:21,170 332 00:14:21,170 --> 00:14:25,420 Assim, podemos bater seguida, e agora, como eu sou certeza de que está familiarizado de César, 333 00:14:25,420 --> 00:14:27,260 isto é, o que é esta linha vai fazer. 334 00:14:27,260 --> 00:14:32,030 É para Int I é igual a 0, N é igual a Strlen, texto simples e, em seguida, 335 00:14:32,030 --> 00:14:33,960 I é menor que n, I, plus, plus. 336 00:14:33,960 --> 00:14:35,210 O que é este laço vai fazer? 337 00:14:35,210 --> 00:14:37,900 338 00:14:37,900 --> 00:14:39,160 Abra a sua mensagem. 339 00:14:39,160 --> 00:14:39,770 Legal. 340 00:14:39,770 --> 00:14:41,330 Então, vamos começar a fazer isso. 341 00:14:41,330 --> 00:14:47,210 >> Assim, se esta condição corresponder, para o nosso primeiro? 342 00:14:47,210 --> 00:14:52,250 Se é um B, é texto simples I. pode obter informações sobre os nossos moradores. 343 00:14:52,250 --> 00:14:53,610 344 00:14:53,610 --> 00:14:57,970 Assim, I é zero, e se seis, que esperamos, e nossa chave é três. 345 00:14:57,970 --> 00:14:59,227 Tudo o que faz sentido, certo? 346 00:14:59,227 --> 00:15:01,310 Esses números são todos exatamente o que deve ser. 347 00:15:01,310 --> 00:15:02,590 348 00:15:02,590 --> 00:15:03,870 Então, hum? 349 00:15:03,870 --> 00:15:05,620 COLUNA 3: Eu tenho números aleatórios para mim. 350 00:15:05,620 --> 00:15:09,156 351 00:15:09,156 --> 00:15:12,030 COLUNA 1: Bem, podemos check-- --nós pode conversar sobre isso em um segundo. 352 00:15:12,030 --> 00:15:14,110 353 00:15:14,110 --> 00:15:15,750 Mas você deve estar recebendo este. 354 00:15:15,750 --> 00:15:17,700 355 00:15:17,700 --> 00:15:20,130 Então, se temos um capital B para o nosso primeiro, 356 00:15:20,130 --> 00:15:22,080 esta condição deve pegá-lo, certo? 357 00:15:22,080 --> 00:15:27,120 Então, se nós batemos Em seguida, vemos que esta Se realmente executa. 358 00:15:27,120 --> 00:15:29,220 Porque se você está seguindo ao longo de seu código, 359 00:15:29,220 --> 00:15:33,460 essa linha aqui, onde texto simples I é substituído com esta aritmética, 360 00:15:33,460 --> 00:15:35,720 só é executado caso a caso condição é certo correto? 361 00:15:35,720 --> 00:15:36,905 362 00:15:36,905 --> 00:15:40,240 >> GDB só vai mostrar-lhe as coisas que são realmente execução. 363 00:15:40,240 --> 00:15:45,140 Então, se essa condição Se não foi cumprida, é só vai pular para a próxima linha. 364 00:15:45,140 --> 00:15:46,540 Ok? 365 00:15:46,540 --> 00:15:48,510 Então, nós temos que. 366 00:15:48,510 --> 00:15:51,171 Este suporte significa que é fechado fora desse ciclo agora. 367 00:15:51,171 --> 00:15:52,420 Então, ele vai começar de novo. 368 00:15:52,420 --> 00:15:54,760 369 00:15:54,760 --> 00:15:56,280 Apenas isso. 370 00:15:56,280 --> 00:15:59,120 Então, que possamos obter informações sobre nossos moradores aqui, 371 00:15:59,120 --> 00:16:02,575 e vemos que o nosso primeiro letra mudou, certo? 372 00:16:02,575 --> 00:16:05,150 É agora um E, como deveria ser. 373 00:16:05,150 --> 00:16:07,360 Assim, podemos continuar. 374 00:16:07,360 --> 00:16:08,500 >> E nós temos essa verificação. 375 00:16:08,500 --> 00:16:09,916 E essa verificação deve funcionar, certo? 376 00:16:09,916 --> 00:16:12,570 É A. Deve ser mudado três cartas para a frente. 377 00:16:12,570 --> 00:16:14,320 378 00:16:14,320 --> 00:16:16,530 Mas se você observar, nós obter algo diferente. 379 00:16:16,530 --> 00:16:17,580 380 00:16:17,580 --> 00:16:22,860 Portanto, neste caso aqui em cima, ele pegou -lo, e assim que esta linha executada, 381 00:16:22,860 --> 00:16:28,620 que modificou a nossa B. Mas, neste caso aqui, 382 00:16:28,620 --> 00:16:32,860 temos que simplesmente ignorados, e fui para o [? L Siff. ?] 383 00:16:32,860 --> 00:16:34,660 Então, alguma coisa está acontecendo lá. 384 00:16:34,660 --> 00:16:37,780 O que está dizendo é que, sabemos que ele deve pegar aqui, 385 00:16:37,780 --> 00:16:39,200 mas não é. 386 00:16:39,200 --> 00:16:42,210 Qualquer um pode ver o que o nosso problema é nessa linha? 387 00:16:42,210 --> 00:16:45,380 388 00:16:45,380 --> 00:16:46,969 É uma coisa muito minuto. 389 00:16:46,969 --> 00:16:48,510 E você também pode olhar para o seu código. 390 00:16:48,510 --> 00:16:49,980 391 00:16:49,980 --> 00:16:54,940 É também linha-- esquecer que linha é em há-- mas é no [inaudível]. 392 00:16:54,940 --> 00:16:55,480 Sim? 393 00:16:55,480 --> 00:16:58,639 >> COLUNA 4: É no maior do que página, se você lê-lo no livro. 394 00:16:58,639 --> 00:16:59,430 COLUNA 1: Exatamente. 395 00:16:59,430 --> 00:17:02,620 Assim, o depurador não poderia dizer isso, mas o depurador 396 00:17:02,620 --> 00:17:05,880 poderia fazê-lo para baixo a uma linha que você sabe que não está funcionando. 397 00:17:05,880 --> 00:17:09,319 E às vezes, quando especialmente no final do semestre, quando 398 00:17:09,319 --> 00:17:12,910 você está lidando com uma centena, uma centena de algumas linhas de código, e você 399 00:17:12,910 --> 00:17:16,190 Não sei onde ele está falhando, esta é uma ótima maneira de fazê-lo. 400 00:17:16,190 --> 00:17:17,900 401 00:17:17,900 --> 00:17:18,989 Assim, encontramos o nosso erro. 402 00:17:18,989 --> 00:17:21,530 Você pode corrigi-lo em seu arquivo, e, em seguida, você pode executá-lo novamente, 403 00:17:21,530 --> 00:17:23,029 e tudo funcionaria perfeitamente. 404 00:17:23,029 --> 00:17:24,970 405 00:17:24,970 --> 00:17:30,590 E a coisa mais importante é isso pode parecer, OK. 406 00:17:30,590 --> 00:17:31,090 Sim. 407 00:17:31,090 --> 00:17:31,370 Legal. 408 00:17:31,370 --> 00:17:32,744 Você sabia que você está procurando. 409 00:17:32,744 --> 00:17:34,910 Então, você sabia o que fazer. 410 00:17:34,910 --> 00:17:39,021 >> GDB pode ser super útil porque você pode imprimir todas essas coisas que você 411 00:17:39,021 --> 00:17:39,520 não o faria. 412 00:17:39,520 --> 00:17:41,160 É muito mais útil do que printf. 413 00:17:41,160 --> 00:17:43,440 Quantos de vocês usam como declarações printf 414 00:17:43,440 --> 00:17:46,200 para descobrir onde um erro foi, certo? 415 00:17:46,200 --> 00:17:48,450 Então, com isso, você não tem que manter a voltar, 416 00:17:48,450 --> 00:17:51,139 e gosta de comentar em Printf, ou comentar, 417 00:17:51,139 --> 00:17:52,930 e descobrir o que você deve ser a impressão. 418 00:17:52,930 --> 00:17:55,670 Este, na verdade, apenas permite que você percorrer, imprimir coisas 419 00:17:55,670 --> 00:18:00,000 como você está passando, por isso, você pode observar como eles mudam em tempo real, 420 00:18:00,000 --> 00:18:02,190 como o programa está sendo executado. 421 00:18:02,190 --> 00:18:04,390 >> E isso leva um pouco pouco de tempo para se acostumar. 422 00:18:04,390 --> 00:18:07,850 Eu recomendo apenas uma espécie de ser um pouco frustrado com isso 423 00:18:07,850 --> 00:18:08,930 para agora. 424 00:18:08,930 --> 00:18:13,450 Se você passar uma hora sobre o próxima semana aprendendo a usar o GDB, 425 00:18:13,450 --> 00:18:16,140 você vai salvar tanto tempo mais tarde. 426 00:18:16,140 --> 00:18:18,750 E literalmente. dizemos isso para as pessoas a cada ano, 427 00:18:18,750 --> 00:18:23,890 e eu me lembro quando eu tirei o classe, eu era como, eu vou ficar bem. 428 00:18:23,890 --> 00:18:24,700 Não. 429 00:18:24,700 --> 00:18:27,030 Pset 6 chegou e eu estava como, eu vou aprender 430 00:18:27,030 --> 00:18:29,500 como usar o GDB porque eu não saber o que está acontecendo aqui. 431 00:18:29,500 --> 00:18:32,940 >> Então, se você tomar o tempo para usá-lo em programas menores 432 00:18:32,940 --> 00:18:35,697 que você está indo para ser trabalhando, como trabalhar 433 00:18:35,697 --> 00:18:37,530 por algo como Visionare, como este. 434 00:18:37,530 --> 00:18:38,800 435 00:18:38,800 --> 00:18:42,850 Ou se você quiser prática extra, tenho certeza Eu poderia vir acima com programas de buggy, 436 00:18:42,850 --> 00:18:45,300 para que você possa depurar se você gostaria. 437 00:18:45,300 --> 00:18:49,300 >> Mas se você apenas levar algum tempo para chegar acostumar com isso, apenas brincar com ele, 438 00:18:49,300 --> 00:18:50,550 ele realmente vai atendê-lo bem. 439 00:18:50,550 --> 00:18:52,591 E é realmente uma das aquelas coisas que você só 440 00:18:52,591 --> 00:18:57,340 tem que tentar, e sujar as mãos com, antes de realmente entendê-la. 441 00:18:57,340 --> 00:19:02,090 Eu realmente só entendi uma vez Eu tinha de depuração coisas com ele, 442 00:19:02,090 --> 00:19:08,170 e é muito mais agradável para ter uma idéia do como depurar, mais cedo ou mais tarde. 443 00:19:08,170 --> 00:19:08,850 Está bem. 444 00:19:08,850 --> 00:19:09,625 Legal. 445 00:19:09,625 --> 00:19:12,960 Eu sei que é tipo como um curso intensivo de GDB, 446 00:19:12,960 --> 00:19:16,400 e com certeza vou trabalhar para ter estes para parecer maior da próxima vez. 447 00:19:16,400 --> 00:19:17,590 448 00:19:17,590 --> 00:19:18,280 Legal. 449 00:19:18,280 --> 00:19:20,390 >> Assim, se voltarmos para o nosso PowerPoint. 450 00:19:20,390 --> 00:19:27,194 451 00:19:27,194 --> 00:19:28,110 Será que isso vai funcionar? 452 00:19:28,110 --> 00:19:29,711 453 00:19:29,711 --> 00:19:30,210 Awh. 454 00:19:30,210 --> 00:19:31,101 Sim. 455 00:19:31,101 --> 00:19:31,600 Está bem. 456 00:19:31,600 --> 00:19:35,480 Então, se você precisar de qualquer um dos aqueles novamente, há a lista. 457 00:19:35,480 --> 00:19:37,160 458 00:19:37,160 --> 00:19:40,830 Pesquisa Então binário, que todos lembra o grande espetáculo de David 459 00:19:40,830 --> 00:19:42,259 rasgando telefone livros pela metade. 460 00:19:42,259 --> 00:19:44,050 Eu realmente não entendo o livros de telefone mais, 461 00:19:44,050 --> 00:19:46,530 porque, como onde você obter livros de telefone nos dias de hoje? 462 00:19:46,530 --> 00:19:48,220 Eu realmente não sei. 463 00:19:48,220 --> 00:19:49,840 464 00:19:49,840 --> 00:19:50,590 A busca binária. 465 00:19:50,590 --> 00:19:52,464 Alguém se lembra Como Binary trabalhos de pesquisa? 466 00:19:52,464 --> 00:19:54,380 467 00:19:54,380 --> 00:19:55,220 Qualquer um em tudo? 468 00:19:55,220 --> 00:19:56,325 Sim? 469 00:19:56,325 --> 00:19:58,283 COLUNA 5: Você sabe quando você olhar para que metade 470 00:19:58,283 --> 00:20:01,146 seria em, Com base nisso, e livrar-se da outra metade. 471 00:20:01,146 --> 00:20:01,896 >> COLUNA 1 Exatamente. 472 00:20:01,896 --> 00:20:06,290 Então, Pesquisa Binária, é uma espécie de a-- --nós gostamos de chamá-lo de dividir e conquistar. 473 00:20:06,290 --> 00:20:09,170 Então, o que você vai fazer é você vai olhar no meio, 474 00:20:09,170 --> 00:20:11,990 e você vai ver se ele corresponde o que você está procurando. 475 00:20:11,990 --> 00:20:15,420 E se isso não acontecer, então você tenta descobrir, é que vai ser deixado 476 00:20:15,420 --> 00:20:16,450 metade ou a metade direita. 477 00:20:16,450 --> 00:20:19,325 Então, isso pode ser se você está procurando em algo que está em ordem alfabética, 478 00:20:19,325 --> 00:20:20,720 veja você, oh. 479 00:20:20,720 --> 00:20:22,750 Será que Allison vir antes M? 480 00:20:22,750 --> 00:20:23,250 Sim. 481 00:20:23,250 --> 00:20:25,030 Então, nós estamos indo para olhar para o primeiro semestre. 482 00:20:25,030 --> 00:20:26,450 >> Ou pode ser como com os números. 483 00:20:26,450 --> 00:20:28,830 Qualquer coisa que você puder comparar, ele pode ser resolvido. 484 00:20:28,830 --> 00:20:29,920 485 00:20:29,920 --> 00:20:31,260 Você pode usar a pesquisa binária em. 486 00:20:31,260 --> 00:20:32,340 487 00:20:32,340 --> 00:20:37,455 Então, alguém se lembra deste gráfico ou o que é isso? 488 00:20:37,455 --> 00:20:39,520 É Complexidade assintótica. 489 00:20:39,520 --> 00:20:42,830 Assim, este gráfico apenas descreve o tempo que 490 00:20:42,830 --> 00:20:46,230 leva você para resolver um problema como você aumenta o número de coisas 491 00:20:46,230 --> 00:20:47,090 que você está usando. 492 00:20:47,090 --> 00:20:51,260 >> Então, nós temos N, que é o tempo linear. 493 00:20:51,260 --> 00:20:54,560 Se N ao longo de dois, o que é ligeiramente melhor, ainda cresce super rápido. 494 00:20:54,560 --> 00:20:58,360 E então temos de login, que é o que consideramos Binary Search. 495 00:20:58,360 --> 00:21:03,630 Se notarmos, como o seu problema fica muito mais e muito maior, 496 00:21:03,630 --> 00:21:06,600 o tempo que você leva para resolvê-lo não vai aumentar muito. 497 00:21:06,600 --> 00:21:09,010 É como comparável aqui no início. 498 00:21:09,010 --> 00:21:10,060 Você é como, OK. 499 00:21:10,060 --> 00:21:13,000 Qualquer coisa aqui realmente não importa qual nós usamos, 500 00:21:13,000 --> 00:21:16,220 mas você sair de um milhão, um bilhão. 501 00:21:16,220 --> 00:21:20,010 Você está tentando encontrar some-- --you're tentando encontrar uma agulha num palheiro. 502 00:21:20,010 --> 00:21:21,550 >> Eu acho que você quer este problema. 503 00:21:21,550 --> 00:21:25,850 Você quer que esta complexidade, não linear porque para tudo o que você 504 00:21:25,850 --> 00:21:30,049 conhecer o seu vai estar procurando por cada agulha indivíduo, coisa de feno, 505 00:21:30,049 --> 00:21:31,340 tentando olhar para a agulha. 506 00:21:31,340 --> 00:21:34,730 E isso não é muito divertido, na minha opinião. 507 00:21:34,730 --> 00:21:35,500 Gosto rápido. 508 00:21:35,500 --> 00:21:36,620 Eu gosto eficiente. 509 00:21:36,620 --> 00:21:40,450 E estudantes, trabalhadoras você caras são, sabem trabalhar de forma mais inteligente, 510 00:21:40,450 --> 00:21:43,010 não mais difícil tipo de coisa, como você pode tornar-se estes algoritmos. 511 00:21:43,010 --> 00:21:45,110 512 00:21:45,110 --> 00:21:47,910 >> Então, nós estamos indo a pé através de apenas um exemplo rápido. 513 00:21:47,910 --> 00:21:51,090 Eu acho que vocês devem ter uma mão em Pesquisa Binária, 514 00:21:51,090 --> 00:21:54,352 mas no caso de alguém é um pouco difusa, quer reforçá-lo, 515 00:21:54,352 --> 00:21:56,310 vamos apenas ir através de um exemplo aqui. 516 00:21:56,310 --> 00:21:59,490 Então, a gente está procurando se a matriz contém sete. 517 00:21:59,490 --> 00:22:00,540 518 00:22:00,540 --> 00:22:06,010 >> Então, a primeira coisa que fazemos é olhar no meio, certo? 519 00:22:06,010 --> 00:22:09,340 E também você vai ser a codificação Pesquisa Binária em apenas um segundo. 520 00:22:09,340 --> 00:22:11,310 Então, isso vai ser divertido. 521 00:22:11,310 --> 00:22:13,710 Então, nós olhamos no matrizes pequenas médias 3. 522 00:22:13,710 --> 00:22:15,501 Faz três igualar 7? 523 00:22:15,501 --> 00:22:16,000 Não. 524 00:22:16,000 --> 00:22:18,670 525 00:22:18,670 --> 00:22:19,550 É seis. 526 00:22:19,550 --> 00:22:21,480 Então, é menor do que ou maior do que sete? 527 00:22:21,480 --> 00:22:23,080 528 00:22:23,080 --> 00:22:23,960 Menor que. 529 00:22:23,960 --> 00:22:24,570 Sim. 530 00:22:24,570 --> 00:22:25,170 Caras bom trabalho. 531 00:22:25,170 --> 00:22:25,569 532 00:22:25,569 --> 00:22:27,360 Eu sinto que como eu deveria temos doces porque eu 533 00:22:27,360 --> 00:22:29,460 quer jogá-lo fora para os estaleiros. 534 00:22:29,460 --> 00:22:30,270 É o que eu vou fazer na próxima semana. 535 00:22:30,270 --> 00:22:31,436 Ele vai manter vocês afiada. 536 00:22:31,436 --> 00:22:32,560 537 00:22:32,560 --> 00:22:34,690 >> Então, nós jogamos fora que primeiro semestre, certo? 538 00:22:34,690 --> 00:22:35,670 foi menor do que. 539 00:22:35,670 --> 00:22:39,325 sabemos que tudo em que lado esquerdo 540 00:22:39,325 --> 00:22:41,700 vai ser menos do que o que estamos realmente procurando. 541 00:22:41,700 --> 00:22:43,491 Assim, não há necessidade de prestar atenção a ela. 542 00:22:43,491 --> 00:22:45,120 Apenas esqueça sobre isso. 543 00:22:45,120 --> 00:22:48,720 Então, agora olhamos para o nosso lado direito, e olhamos para o meio ali, 544 00:22:48,720 --> 00:22:50,510 e agora são nove. 545 00:22:50,510 --> 00:22:55,510 Então, 9 é-- --Everyone? 546 00:22:55,510 --> 00:22:57,470 Maior do que o que nós somos procurando, certo? 547 00:22:57,470 --> 00:22:59,860 Então, nós estamos indo jogar fora tudo para a direita. 548 00:22:59,860 --> 00:23:00,970 549 00:23:00,970 --> 00:23:01,940 Como aquele. 550 00:23:01,940 --> 00:23:03,700 Agora, todos nós é deixado com um. 551 00:23:03,700 --> 00:23:07,760 Então, vamos verificar, é este o que que estamos procurando? ele é. 552 00:23:07,760 --> 00:23:08,970 Nós encontramos o que queríamos. 553 00:23:08,970 --> 00:23:10,440 554 00:23:10,440 --> 00:23:11,690 Por isso, está feito. 555 00:23:11,690 --> 00:23:12,550 Bilinear Search. 556 00:23:12,550 --> 00:23:15,740 >> E se você observar, nós tinha sete entradas de lá. 557 00:23:15,740 --> 00:23:24,320 Levou apenas nós como três vezes, mas se você está fazendo como um bilhão, 558 00:23:24,320 --> 00:23:28,190 vocês sabem quantos passos que faria ter se tivéssemos quatro bilhões de coisas? 559 00:23:28,190 --> 00:23:29,940 560 00:23:29,940 --> 00:23:30,455 Algum palpite? 561 00:23:30,455 --> 00:23:32,286 562 00:23:32,286 --> 00:23:33,960 É 32. 563 00:23:33,960 --> 00:23:37,110 32 passos para encontrar algo em quatro bilhões 564 00:23:37,110 --> 00:23:39,650 elemento da matriz por causa de potências de dois. 565 00:23:39,650 --> 00:23:43,550 Então, dois é a 32, é de quatro bilhões. 566 00:23:43,550 --> 00:23:50,430 >> Assim como muito louco você ainda está dentro como um relativamente pequeno número de passos 567 00:23:50,430 --> 00:23:52,650 para encontrar algo em quatro bilhões de elementos. 568 00:23:52,650 --> 00:23:55,730 Então, nessa nota, estamos vai codificar isso 569 00:23:55,730 --> 00:23:58,950 para que vocês possam realmente tipo de ver como isso funciona. 570 00:23:58,950 --> 00:24:01,520 Tudo bem, então vocês podem codificar. 571 00:24:01,520 --> 00:24:04,100 Vou deixar vocês conversar um pouco. 572 00:24:04,100 --> 00:24:07,970 Conheça pessoas ao seu redor, o que é o que alguém queria da última seção. 573 00:24:07,970 --> 00:24:10,280 >> Então, para conhecer as pessoas ao seu redor. 574 00:24:10,280 --> 00:24:11,305 Fale um pouco. 575 00:24:11,305 --> 00:24:12,580 576 00:24:12,580 --> 00:24:15,730 E tudo que eu quero de você caras agora é apenas 577 00:24:15,730 --> 00:24:17,575 tentar criar um esboço de pseudocódigo. 578 00:24:17,575 --> 00:24:18,075 Ok? 579 00:24:18,075 --> 00:24:20,825 580 00:24:20,825 --> 00:24:21,325 Whoa. 581 00:24:21,325 --> 00:24:23,320 582 00:24:23,320 --> 00:24:29,520 Tudo que eu quero de vocês é que você está só vai preencher neste caso enquanto. 583 00:24:29,520 --> 00:24:32,170 Então, eu tenho definir essas superior e limites inferiores que 584 00:24:32,170 --> 00:24:35,250 representam o início e no final de nossa matriz. 585 00:24:35,250 --> 00:24:40,440 E você vai, na verdade, loop através de e descobrir 586 00:24:40,440 --> 00:24:42,470 o que estamos fazendo dentro deste loop while. 587 00:24:42,470 --> 00:24:45,810 >> Então, se você pode descobrir out-- tenho uma dica há-- quais são os casos 588 00:24:45,810 --> 00:24:46,640 que temos aqui? 589 00:24:46,640 --> 00:24:48,100 590 00:24:48,100 --> 00:24:51,560 Então, se você quiser descobrir a casos, vamos Pseudocódigo aqueles 591 00:24:51,560 --> 00:24:53,350 e depois vamos realmente codificá-las. 592 00:24:53,350 --> 00:24:55,330 E vai ser, eu acho, espero que ele vai 593 00:24:55,330 --> 00:24:56,788 ser um pouco mais fácil do que você espera. 594 00:24:56,788 --> 00:24:57,554 595 00:24:57,554 --> 00:25:00,220 Porque não é que muito código, na verdade, o que é muito legal. 596 00:25:00,220 --> 00:25:34,110 597 00:25:34,110 --> 00:25:35,018 >> Mm-hm? 598 00:25:35,018 --> 00:25:35,893 >> Estudante: [inaudível]? 599 00:25:35,893 --> 00:25:36,984 600 00:25:36,984 --> 00:25:37,650 INSTRUTOR: Sim. 601 00:25:37,650 --> 00:25:38,595 Havia algo para encontrar no meio. 602 00:25:38,595 --> 00:25:39,552 >> ALUNO: Assim, podemos usar isso. 603 00:25:39,552 --> 00:25:39,770 Está bem. 604 00:25:39,770 --> 00:25:40,603 >> INSTRUTOR: Perfeito. 605 00:25:40,603 --> 00:25:42,950 Então essa é a primeira coisa que precisamos fazer. 606 00:25:42,950 --> 00:25:44,330 Então, encontrar o meio. 607 00:25:44,330 --> 00:25:45,415 608 00:25:45,415 --> 00:25:45,915 Grande. 609 00:25:45,915 --> 00:25:47,770 610 00:25:47,770 --> 00:25:55,010 Então você tem uma idéia de como poderíamos realmente encontrar o meio com código? 611 00:25:55,010 --> 00:25:55,980 >> Estudante: Sim. 612 00:25:55,980 --> 00:25:57,000 n mais de 2? 613 00:25:57,000 --> 00:25:58,500 614 00:25:58,500 --> 00:25:59,500 INSTRUTOR: Então n mais de 2. 615 00:25:59,500 --> 00:26:05,170 Então, uma coisa a lembrar é que seus limites superiores e inferiores mudar. 616 00:26:05,170 --> 00:26:08,110 Continuamos a constrição da parte da matriz nós estamos olhando para. 617 00:26:08,110 --> 00:26:11,970 Então n mais de 2 só vai funcionar para a primeira coisa que fazemos. 618 00:26:11,970 --> 00:26:17,810 Assim, tendo superior e inferior em conta, como podemos obter esse elemento do meio? 619 00:26:17,810 --> 00:26:20,640 Porque queremos que a média entre superior e inferior, certo? 620 00:26:20,640 --> 00:26:21,730 621 00:26:21,730 --> 00:26:22,494 Mm-hm? 622 00:26:22,494 --> 00:26:23,369 >> Estudante: [inaudível]. 623 00:26:23,369 --> 00:26:26,170 624 00:26:26,170 --> 00:26:28,080 >> INSTRUTOR: Então nós temos algum meio. 625 00:26:28,080 --> 00:26:32,730 E vai ser superior mais baixa superior a 2. 626 00:26:32,730 --> 00:26:34,740 627 00:26:34,740 --> 00:26:35,690 Impressionante. 628 00:26:35,690 --> 00:26:36,570 Lá vamos nós. 629 00:26:36,570 --> 00:26:37,280 Um para baixo da linha. 630 00:26:37,280 --> 00:26:38,560 Vocês estão no seu caminho. 631 00:26:38,560 --> 00:26:41,400 Portanto, agora que temos o nosso meio, o que nós queremos fazer? 632 00:26:41,400 --> 00:26:45,050 633 00:26:45,050 --> 00:26:45,900 Só em geral. 634 00:26:45,900 --> 00:26:47,734 Você não tem que codificá-lo. 635 00:26:47,734 --> 00:26:48,335 Sim. 636 00:26:48,335 --> 00:26:49,210 Estudante: [inaudível]? 637 00:26:49,210 --> 00:27:00,310 638 00:27:00,310 --> 00:27:10,310 INSTRUTOR: Então é mais porque você é achando a média entre os dois 639 00:27:10,310 --> 00:27:10,810 deles. 640 00:27:10,810 --> 00:27:11,890 641 00:27:11,890 --> 00:27:17,370 Então, se você pensar neles como tipo de aumentar a partir dos lados, 642 00:27:17,370 --> 00:27:21,640 pensar sobre isso quando você se aproxima no meio, você quer assim. 643 00:27:21,640 --> 00:27:27,150 Então, se você estivesse em ambos os lados da meio, e temos como 5 e 7. 644 00:27:27,150 --> 00:27:31,440 Quando você adiciona-los juntos você obter 12, você divide por 2, é 6. 645 00:27:31,440 --> 00:27:33,726 >> Às vezes é difícil explicar por que funciona, 646 00:27:33,726 --> 00:27:35,600 mas se você trabalha com um exemplo, às vezes, 647 00:27:35,600 --> 00:27:37,962 ele vai ajudar você a descobrir se ele deve ser mais ou menos. 648 00:27:37,962 --> 00:27:38,846 Sim. 649 00:27:38,846 --> 00:27:40,830 >> Estudante: [inaudível] exatamente no meio 650 00:27:40,830 --> 00:27:43,950 se tivessem um caso onde há um monte de números menores 651 00:27:43,950 --> 00:27:45,860 e como um número grande? 652 00:27:45,860 --> 00:27:49,750 >> INSTRUTOR: Então, tudo que você precisa é o meio da matriz. 653 00:27:49,750 --> 00:27:53,010 Então, se você tinha um monte de números pequenos e, em seguida, um número muito grande 654 00:27:53,010 --> 00:27:54,799 no final, não importa. 655 00:27:54,799 --> 00:27:56,840 Tudo o que importa é que eles estão classificadas, você só 656 00:27:56,840 --> 00:27:59,339 quero olhar para o meio do a matriz, porque você ainda está 657 00:27:59,339 --> 00:28:00,700 fatiar o seu problema pela metade. 658 00:28:00,700 --> 00:28:03,020 659 00:28:03,020 --> 00:28:03,680 Legal. 660 00:28:03,680 --> 00:28:06,430 Portanto, agora que temos a meio, o que vamos fazer a seguir? 661 00:28:06,430 --> 00:28:07,150 >> ALUNO: Compare. 662 00:28:07,150 --> 00:28:08,150 INSTRUTOR: The comparar. 663 00:28:08,150 --> 00:28:11,670 Então, comparar a média value_wanted. 664 00:28:11,670 --> 00:28:14,300 665 00:28:14,300 --> 00:28:15,160 Legal. 666 00:28:15,160 --> 00:28:17,950 Então você vê aqui, temos este valor que queremos aqui. 667 00:28:17,950 --> 00:28:22,012 668 00:28:22,012 --> 00:28:23,095 Lembre-se esta é uma matriz. 669 00:28:23,095 --> 00:28:24,100 670 00:28:24,100 --> 00:28:26,970 Assim, refere-se a média do índice. 671 00:28:26,970 --> 00:28:29,785 Por isso, queremos fazer valores de média. 672 00:28:29,785 --> 00:28:32,380 673 00:28:32,380 --> 00:28:35,650 Não se esqueça, se você quiser comparar, de dois iguais. 674 00:28:35,650 --> 00:28:38,250 Você faz única igual a você só vai transferir-lo, 675 00:28:38,250 --> 00:28:41,090 e depois, é claro, é vai ser o valor que você deseja. 676 00:28:41,090 --> 00:28:42,300 Portanto, não faça isso. 677 00:28:42,300 --> 00:28:44,350 >> Então vamos ver se os valores no meio 678 00:28:44,350 --> 00:28:46,460 é igual ao valor que queremos. 679 00:28:46,460 --> 00:28:47,749 680 00:28:47,749 --> 00:28:48,790 Não se esqueça de suas chaves. 681 00:28:48,790 --> 00:28:50,520 682 00:28:50,520 --> 00:28:52,235 Dropbox deve ir embora. 683 00:28:52,235 --> 00:28:54,140 684 00:28:54,140 --> 00:28:56,200 Então, o que vamos fazer neste caso? 685 00:28:56,200 --> 00:28:59,360 Se é o que queremos para voltar? 686 00:28:59,360 --> 00:29:01,510 687 00:29:01,510 --> 00:29:02,626 Nós estamos tentando dizer. 688 00:29:02,626 --> 00:29:03,440 >> ALUNO: Imprima. 689 00:29:03,440 --> 00:29:05,314 >> INSTRUTOR: Bem, nós não quer imprimir. 690 00:29:05,314 --> 00:29:08,220 Portanto, este é um bool aqui, portanto, quer retornar verdadeiro ou falso. 691 00:29:08,220 --> 00:29:12,280 Nós estamos dizendo, é esse número um [? RRA? ?] Então, se é, 692 00:29:12,280 --> 00:29:13,788 nós simplesmente devolvê-lo verdadeiro. 693 00:29:13,788 --> 00:29:16,780 694 00:29:16,780 --> 00:29:17,760 Se eu posso soletrar verdade. 695 00:29:17,760 --> 00:29:18,830 696 00:29:18,830 --> 00:29:20,805 >> ALUNO: Por que você não retornar zero? 697 00:29:20,805 --> 00:29:22,930 INSTRUTOR: Então você poderia retornar zero se você quisesse. 698 00:29:22,930 --> 00:29:26,780 Mas neste caso, porque nossa função retorna um bool, 699 00:29:26,780 --> 00:29:28,962 precisamos voltar verdadeira ou falsa. 700 00:29:28,962 --> 00:29:30,920 ALUNO: Quando você estiver dizendo expressão booleana, 701 00:29:30,920 --> 00:29:33,450 você pode configurá-lo igual a falso? 702 00:29:33,450 --> 00:29:39,860 Como se eu quero dizer, se esta condição não for cumprida, como é superior é igual a falso. 703 00:29:39,860 --> 00:29:42,332 Será que vai entender se você apenas colocar falso do outro lado? 704 00:29:42,332 --> 00:29:43,040 INSTRUTOR: Yeah. 705 00:29:43,040 --> 00:29:44,820 Então, na verdade, se você estiver sempre fazendo alguma coisa 706 00:29:44,820 --> 00:29:49,600 como é superior ou é menor, que retorna verdadeiro ou falso 707 00:29:49,600 --> 00:29:53,850 e é realmente um estilo ruim para digamos igual a igual a true ou iguais 708 00:29:53,850 --> 00:29:54,840 é igual a falso. 709 00:29:54,840 --> 00:30:00,210 Você quer usar esse resultado como o próprio como o seu cheque. 710 00:30:00,210 --> 00:30:04,720 711 00:30:04,720 --> 00:30:05,860 Não é o que eu queria. 712 00:30:05,860 --> 00:30:08,150 713 00:30:08,150 --> 00:30:09,240 Isso é o que eu queria. 714 00:30:09,240 --> 00:30:13,205 Assim, no caso de você está pedindo sobre algo como salvar isso em c. 715 00:30:13,205 --> 00:30:16,320 716 00:30:16,320 --> 00:30:25,150 >> Então, se temos int main (void) e algo como isso. 717 00:30:25,150 --> 00:30:31,922 E você tem, se é superior de alguma entrada e você está 718 00:30:31,922 --> 00:30:33,630 perguntando se você pode fazer algo parecido com isto? 719 00:30:33,630 --> 00:30:35,010 720 00:30:35,010 --> 00:30:35,679 Certo? 721 00:30:35,679 --> 00:30:37,470 ESTUDANTE: Eu estava tentando para fazê-lo [inaudível]. 722 00:30:37,470 --> 00:30:38,450 Porque se it's-- 723 00:30:38,450 --> 00:30:39,200 INSTRUTOR: Certo. 724 00:30:39,200 --> 00:30:41,197 Então você quer que isso seja falso, certo? 725 00:30:41,197 --> 00:30:41,780 Estudante: Sim. 726 00:30:41,780 --> 00:30:45,960 INSTRUTOR: Então, nesse caso você quero que ele execute, se isso não é verdade. 727 00:30:45,960 --> 00:30:50,510 Então, a coisa legal você fazer lá é esta. 728 00:30:50,510 --> 00:30:52,900 729 00:30:52,900 --> 00:30:55,650 Então lembre-se de exclamação ponto nega coisas? 730 00:30:55,650 --> 00:30:58,270 Ele diz que [inaudível] não significa. 731 00:30:58,270 --> 00:31:03,590 Portanto, se olharmos apenas esta parte aqui, você 732 00:31:03,590 --> 00:31:05,740 dizem que avalia a falso como você quer que ele. 733 00:31:05,740 --> 00:31:06,790 734 00:31:06,790 --> 00:31:09,880 Não falsa é verdade que significa que este seria executado. 735 00:31:09,880 --> 00:31:11,037 Será que isso faz sentido? 736 00:31:11,037 --> 00:31:11,620 Estudante: Sim. 737 00:31:11,620 --> 00:31:12,453 INSTRUTOR: Awesome. 738 00:31:12,453 --> 00:31:13,800 739 00:31:13,800 --> 00:31:14,300 Está bem. 740 00:31:14,300 --> 00:31:16,330 Então, nós poderíamos apenas retornar verdade neste caso. 741 00:31:16,330 --> 00:31:20,357 Portanto, agora temos dois outros casos neste caso. 742 00:31:20,357 --> 00:31:21,565 Quais são os nossos outros dois casos? 743 00:31:21,565 --> 00:31:31,610 744 00:31:31,610 --> 00:31:32,900 Vamos apenas fazê-lo desta forma. 745 00:31:32,900 --> 00:31:40,660 Então vamos começar com outra coisa se os valores no meio 746 00:31:40,660 --> 00:31:43,230 é menor do que o valor que queremos. 747 00:31:43,230 --> 00:31:47,200 748 00:31:47,200 --> 00:31:52,020 Assim, o nosso valor no meio é menos que o valor que estamos procurando. 749 00:31:52,020 --> 00:31:53,765 750 00:31:53,765 --> 00:31:56,720 >> Assim que ligado você acho que quer atualizar? 751 00:31:56,720 --> 00:31:57,870 752 00:31:57,870 --> 00:31:58,780 Superior ou inferior? 753 00:31:58,780 --> 00:32:01,440 754 00:32:01,440 --> 00:32:01,940 Superior? 755 00:32:01,940 --> 00:32:03,230 756 00:32:03,230 --> 00:32:06,470 Assim que lado da matriz vamos estar olhando? 757 00:32:06,470 --> 00:32:07,500 >> ALUNO: A mais baixa. 758 00:32:07,500 --> 00:32:09,750 >> INSTRUTOR: Nós estamos indo estar olhando para a esquerda. 759 00:32:09,750 --> 00:32:11,120 Então, outra coisa se pouco valor é menor. 760 00:32:11,120 --> 00:32:14,730 Portanto, o seu valor médio aqui é menor do que o que nós queremos. 761 00:32:14,730 --> 00:32:17,202 Por isso, queremos levar o lado direito da nossa matriz. 762 00:32:17,202 --> 00:32:18,910 Então, nós estamos indo para atualizar nosso limite inferior. 763 00:32:18,910 --> 00:32:20,210 764 00:32:20,210 --> 00:32:23,020 Então, vamos transferir nossa inferior. 765 00:32:23,020 --> 00:32:25,221 E o que você acha que deve ser menor? 766 00:32:25,221 --> 00:32:26,304 ESTUDANTE: O valor médio? 767 00:32:26,304 --> 00:32:27,446 768 00:32:27,446 --> 00:32:28,820 INSTRUTOR: Então o value-- meio 769 00:32:28,820 --> 00:32:30,136 ALUNO: Plus 1. 770 00:32:30,136 --> 00:32:31,010 INSTRUTOR: --plus 1. 771 00:32:31,010 --> 00:32:32,300 772 00:32:32,300 --> 00:32:34,380 Alguém pode me dizer por que temos que mais uma? 773 00:32:34,380 --> 00:32:35,730 >> Estudante: [? Nenhum valor?] é mais igual a ele. 774 00:32:35,730 --> 00:32:36,120 >> INSTRUTOR: Certo. 775 00:32:36,120 --> 00:32:38,661 Porque já sabemos que nosso valor médio não é igual a 776 00:32:38,661 --> 00:32:42,750 isso e queremos excluí-lo a partir de todas as pesquisas subsequentes. 777 00:32:42,750 --> 00:32:46,360 Se você esquecer de que mais 1, esta vai gostar de loop indefinidamente. 778 00:32:46,360 --> 00:32:49,620 E você só vai ser pego em uma loop infinito e então você vai segfault 779 00:32:49,620 --> 00:32:50,370 e as coisas vão mal. 780 00:32:50,370 --> 00:32:54,780 Então, certifique-se sempre que você não está incluindo o valor que você acabou de 781 00:32:54,780 --> 00:32:55,380 olhou. 782 00:32:55,380 --> 00:32:58,530 Então, nós cuidamos do que com um plus 1. 783 00:32:58,530 --> 00:33:04,840 >> Portanto, agora temos nossa última condição que eu sempre por razões de segurança 784 00:33:04,840 --> 00:33:12,664 você pode conferir aqui, mais se o valor em o meio é maior do que o valor 785 00:33:12,664 --> 00:33:13,163 nós queremos. 786 00:33:13,163 --> 00:33:16,260 787 00:33:16,260 --> 00:33:20,230 Isso significa que nós queremos a metade do lado esquerdo. 788 00:33:20,230 --> 00:33:21,350 789 00:33:21,350 --> 00:33:23,260 Então, qual deles é que vamos atualizar? 790 00:33:23,260 --> 00:33:23,760 Superior. 791 00:33:23,760 --> 00:33:25,470 792 00:33:25,470 --> 00:33:26,970 E o que é este vai ser igual? 793 00:33:26,970 --> 00:33:31,630 794 00:33:31,630 --> 00:33:33,690 Médio menos 1 porque, é claro, que queremos 795 00:33:33,690 --> 00:33:38,370 para se certificar de que não estamos olhando para o valor médio novamente. 796 00:33:38,370 --> 00:33:41,830 797 00:33:41,830 --> 00:33:45,110 E então nós temos isso. 798 00:33:45,110 --> 00:33:45,610 É isso aí. 799 00:33:45,610 --> 00:33:46,820 Isso é tudo de busca binária é. 800 00:33:46,820 --> 00:33:48,190 Não é tão ruim, certo? 801 00:33:48,190 --> 00:33:51,590 É como se 10 linhas de código com espaço em branco. 802 00:33:51,590 --> 00:33:57,510 Então, muito poderoso, muito útil, você vai estar a usá-lo em um de seus Série de Exercícios posteriores. 803 00:33:57,510 --> 00:33:59,360 Talvez não este, mas mais tarde. 804 00:33:59,360 --> 00:34:00,670 Assim, aprendê-la. 805 00:34:00,670 --> 00:34:01,510 Adoro. 806 00:34:01,510 --> 00:34:02,980 Ele vai te tratar bem. 807 00:34:02,980 --> 00:34:05,370 Então, alguém tem alguma perguntas sobre busca binária? 808 00:34:05,370 --> 00:34:06,196 Sim. 809 00:34:06,196 --> 00:34:09,840 >> ALUNO: Será que isso importa se o seu n é par ou ímpar? 810 00:34:09,840 --> 00:34:10,750 >> INSTRUTOR: Não. 811 00:34:10,750 --> 00:34:18,150 Porque nós lançá-lo para o meio como um int, ela só vai truncar-lo. 812 00:34:18,150 --> 00:34:21,600 Então, ele vai ficar um inteiro e ele vai eventualmente classificar através de tudo. 813 00:34:21,600 --> 00:34:23,909 Assim você não precisa se preocupar com isso. 814 00:34:23,909 --> 00:34:24,580 Todo mundo bom? 815 00:34:24,580 --> 00:34:25,659 816 00:34:25,659 --> 00:34:26,850 Impressionante. 817 00:34:26,850 --> 00:34:27,919 Legal. 818 00:34:27,919 --> 00:34:30,836 Então, vocês tem isso. 819 00:34:30,836 --> 00:34:33,380 820 00:34:33,380 --> 00:34:33,880 Slideshow. 821 00:34:33,880 --> 00:34:35,719 822 00:34:35,719 --> 00:34:43,270 Assim como nós estávamos falando sobre, eu sei David mencionou tempos de execução de complexidade. 823 00:34:43,270 --> 00:34:44,420 824 00:34:44,420 --> 00:34:50,340 >> Assim, na melhor das hipóteses, é apenas um, o que chamamos de tempo constante. 825 00:34:50,340 --> 00:34:51,909 Alguém pode me dizer por que isso pode ser? 826 00:34:51,909 --> 00:34:52,969 827 00:34:52,969 --> 00:34:55,800 Que tipo de cenário que isso implica? 828 00:34:55,800 --> 00:34:58,260 829 00:34:58,260 --> 00:34:58,760 Mm-hm. 830 00:34:58,760 --> 00:34:59,926 >> Estudante: [inaudível] first-- 831 00:34:59,926 --> 00:35:00,789 832 00:35:00,789 --> 00:35:03,830 INSTRUTOR: Então no meio sendo o primeiro elemento que vem, certo? 833 00:35:03,830 --> 00:35:08,167 Assim, ou um conjunto de um ou tudo o que está procurando apenas 834 00:35:08,167 --> 00:35:09,750 passa a ser bem no meio. 835 00:35:09,750 --> 00:35:11,190 836 00:35:11,190 --> 00:35:13,380 Então, essa é a nossa melhor caso. 837 00:35:13,380 --> 00:35:17,540 Você começa em problemas reais, provavelmente não vai chegar [inaudível] que muitas vezes. 838 00:35:17,540 --> 00:35:18,667 839 00:35:18,667 --> 00:35:19,750 E o nosso pior caso? 840 00:35:19,750 --> 00:35:21,270 Nosso pior caso é log n. 841 00:35:21,270 --> 00:35:25,360 E isso tem a ver com o todo potências de dois coisa que eu falei. 842 00:35:25,360 --> 00:35:30,930 >> Assim, no pior caso, isso significaria que tivemos de cortar a matriz para baixo 843 00:35:30,930 --> 00:35:33,270 até que era um elemento de um. 844 00:35:33,270 --> 00:35:34,810 845 00:35:34,810 --> 00:35:38,930 Então tivemos que cortá-la pela metade tantas vezes quanto nós podia. 846 00:35:38,930 --> 00:35:41,430 É por isso que é log n porque você continua dividindo por dois. 847 00:35:41,430 --> 00:35:42,890 848 00:35:42,890 --> 00:35:45,830 Assim pressupostos, coisas que você Preciso saber se você está sempre 849 00:35:45,830 --> 00:35:48,050 vai usar uma busca binária. 850 00:35:48,050 --> 00:35:50,680 Seus elementos devem ser ordenados. 851 00:35:50,680 --> 00:35:53,890 Eles têm de ser resolvidas, porque essa é a única maneira que você 852 00:35:53,890 --> 00:35:57,060 pode saber se você é capaz para jogar fora metade. 853 00:35:57,060 --> 00:36:00,260 >> Se você tivesse esta bolsa confusa de números e você está dizendo, 854 00:36:00,260 --> 00:36:05,380 OK, eu vou verificar o meio número eo número que eu estou procurando 855 00:36:05,380 --> 00:36:08,510 é menos do que isso, eu só vou para atirar arbitrariamente fora metade. 856 00:36:08,510 --> 00:36:11,130 Você não sabe se o seu os números em que a outra metade. 857 00:36:11,130 --> 00:36:12,655 Sua lista tem de ser resolvida. 858 00:36:12,655 --> 00:36:14,030 859 00:36:14,030 --> 00:36:16,560 Assim, este pode ser indo adiante um pouco, 860 00:36:16,560 --> 00:36:18,360 mas você precisa ter acesso aleatório. 861 00:36:18,360 --> 00:36:21,940 Você precisa ser capaz de apenas ir para aquele elemento do meio. 862 00:36:21,940 --> 00:36:25,110 Se você tiver que atravessar por algo 863 00:36:25,110 --> 00:36:28,630 ou você leva etapas extras para chegar a esse elemento do meio, 864 00:36:28,630 --> 00:36:31,750 não é log n mais porque você está adicionando mais trabalho para ele. 865 00:36:31,750 --> 00:36:34,800 E isso vai fazer um pouco de mais sentido em duas semanas, 866 00:36:34,800 --> 00:36:37,950 mas eu meio que queria prefácio, dar a vocês uma idéia do que é 867 00:36:37,950 --> 00:36:38,999 para vir. 868 00:36:38,999 --> 00:36:40,790 Mas esses são os dois premissas importantes 869 00:36:40,790 --> 00:36:44,804 que você precisa para uma lista de binário. 870 00:36:44,804 --> 00:36:45,720 Certifique-se de que está classificado. 871 00:36:45,720 --> 00:36:47,920 Esse é o grande problema para vocês agora mesmo. 872 00:36:47,920 --> 00:36:52,170 E em que podemos entrar em o resto de nossas sortes. 873 00:36:52,170 --> 00:36:56,444 Então, quatro bolha sorts--, inserção, seleção e merge. 874 00:36:56,444 --> 00:36:57,485 Eles estão todos bem legal. 875 00:36:57,485 --> 00:37:02,860 Se vocês decidem tomar CS 124, você vai aprender sobre todos os tipos de tipos. 876 00:37:02,860 --> 00:37:07,575 E se você é um fã XKCD, não é um sobre quadrinhos muito legal 877 00:37:07,575 --> 00:37:11,530 como os tipos realmente ineficazes, o que eu recomendo que você vai olhar. 878 00:37:11,530 --> 00:37:16,170 Um deles é como espécie de pânico, que é como, oh não, retornar disposição aleatória. 879 00:37:16,170 --> 00:37:16,991 Sistema de desligamento. 880 00:37:16,991 --> 00:37:17,490 Deixar. 881 00:37:17,490 --> 00:37:19,070 882 00:37:19,070 --> 00:37:21,500 Então, humor geeky é sempre bom. 883 00:37:21,500 --> 00:37:22,620 884 00:37:22,620 --> 00:37:25,750 >> Então, alguém se lembra tipo de como apenas uma idéia geral 885 00:37:25,750 --> 00:37:27,810 de como bubble sort funciona. 886 00:37:27,810 --> 00:37:31,130 887 00:37:31,130 --> 00:37:32,155 Você se lembra? 888 00:37:32,155 --> 00:37:32,755 >> Estudante: Sim. 889 00:37:32,755 --> 00:37:33,970 >> INSTRUTOR: Vá em frente. 890 00:37:33,970 --> 00:37:38,980 >> Estudante: Então você está passando e se for maior, então você trocar os dois. 891 00:37:38,980 --> 00:37:39,820 >> INSTRUTOR: Mm-hm. 892 00:37:39,820 --> 00:37:40,564 Exatamente. 893 00:37:40,564 --> 00:37:41,730 Então você só iterar. 894 00:37:41,730 --> 00:37:43,050 Você verifica dois números. 895 00:37:43,050 --> 00:37:46,510 Se o anterior é maior depois do que aquele, 896 00:37:46,510 --> 00:37:50,230 você só trocá-los de forma que em Desta forma, todos os números mais elevados 897 00:37:50,230 --> 00:37:54,990 bolha-se para o fim da lista e todos os números mais baixos bolha para baixo. 898 00:37:54,990 --> 00:37:59,355 >> Será que ele mostrar a vocês o frio efeito sonoro triagem vídeo? 899 00:37:59,355 --> 00:38:00,480 É bem legal. 900 00:38:00,480 --> 00:38:01,510 901 00:38:01,510 --> 00:38:05,200 Assim como Robert disse, o algoritmo que você acabou de percorrer a lista, 902 00:38:05,200 --> 00:38:07,930 trocando os valores adjacentes se eles não estão em ordem. 903 00:38:07,930 --> 00:38:10,975 E depois é só ficar repetindo até que você não faça nenhuma swaps. 904 00:38:10,975 --> 00:38:11,990 905 00:38:11,990 --> 00:38:12,740 Então, não é ruim, certo? 906 00:38:12,740 --> 00:38:14,080 907 00:38:14,080 --> 00:38:16,319 Então, só temos um exemplo rápido aqui. 908 00:38:16,319 --> 00:38:18,360 Então, isso vai classificar los em ordem crescente. 909 00:38:18,360 --> 00:38:19,470 910 00:38:19,470 --> 00:38:23,470 Então, quando nós passamos a primeira tempo, olhamos a oito 911 00:38:23,470 --> 00:38:26,880 e seis não são, obviamente, em ordem, nós trocá-los. 912 00:38:26,880 --> 00:38:27,985 >> Então olhe para a próxima. 913 00:38:27,985 --> 00:38:29,430 Oito e quatro não em ordem. 914 00:38:29,430 --> 00:38:30,450 Trocá-los. 915 00:38:30,450 --> 00:38:32,530 E depois de oito e dois, trocá-los. 916 00:38:32,530 --> 00:38:33,470 Lá vamos nós. 917 00:38:33,470 --> 00:38:39,519 Então, depois de sua primeira passagem, você sabe que seu maior número 918 00:38:39,519 --> 00:38:41,810 vai ser todo o caminho no topo, porque é só 919 00:38:41,810 --> 00:38:44,210 vai ser constantemente maior do que tudo o resto 920 00:38:44,210 --> 00:38:46,810 e ele só vai para bolha até todo o caminho até a final lá. 921 00:38:46,810 --> 00:38:48,226 Será que isso faz sentido para todos? 922 00:38:48,226 --> 00:38:48,560 923 00:38:48,560 --> 00:38:49,060 Legal. 924 00:38:49,060 --> 00:38:51,310 925 00:38:51,310 --> 00:38:53,920 >> Então olhamos para a nossa segunda passagem. 926 00:38:53,920 --> 00:38:54,980 Seis e quatro, interruptor. 927 00:38:54,980 --> 00:38:55,920 Seis e dois, switch. 928 00:38:55,920 --> 00:38:58,700 E agora nós temos algumas coisas em ordem. 929 00:38:58,700 --> 00:39:02,240 Assim, para cada passagem que fazer através de nossa lista inteira, 930 00:39:02,240 --> 00:39:06,320 sabemos que como que muitos números no final terá sido classificados. 931 00:39:06,320 --> 00:39:07,690 932 00:39:07,690 --> 00:39:09,610 Então nós fazemos uma terceira passagem, que é um swap. 933 00:39:09,610 --> 00:39:10,860 934 00:39:10,860 --> 00:39:15,910 E, em seguida, na nossa quarta passar, temos zero slots. 935 00:39:15,910 --> 00:39:18,570 E assim sabemos que a nossa matriz tiver sido resolvido. 936 00:39:18,570 --> 00:39:20,900 >> E essa é a grande coisa com bubble sort. 937 00:39:20,900 --> 00:39:23,720 Nós sabemos que quando nós ter zero swaps, que 938 00:39:23,720 --> 00:39:26,497 significa que tudo está em ordem completa. 939 00:39:26,497 --> 00:39:27,580 É uma espécie de como podemos verificar. 940 00:39:27,580 --> 00:39:28,740 941 00:39:28,740 --> 00:39:36,480 Então, nós também estamos indo para codificar bolha tipo o que também não é tão ruim assim. 942 00:39:36,480 --> 00:39:38,120 Nenhum destes são tão ruins. 943 00:39:38,120 --> 00:39:40,210 Sei que pode parecer um pouco assustador. 944 00:39:40,210 --> 00:39:42,124 Eu sei que quando eu tirei a classe, mesmo quando eu 945 00:39:42,124 --> 00:39:44,290 estava ensinando a classe para Pela primeira vez no ano passado, 946 00:39:44,290 --> 00:39:46,165 Eu estava tipo, como eu faço isso? 947 00:39:46,165 --> 00:39:48,540 Faz sentido na teoria, mas como é que vamos realmente fazer isso? 948 00:39:48,540 --> 00:39:51,420 É por isso que eu também quero andar por meio de código com vocês aqui. 949 00:39:51,420 --> 00:39:54,915 Então, eu tenho um pseudocódigo para vocês neste momento. 950 00:39:54,915 --> 00:39:55,950 951 00:39:55,950 --> 00:39:58,970 Então, basta manter isso em mente como estamos prestes a fazer a transição mais. 952 00:39:58,970 --> 00:40:04,210 Portanto, temos alguns contador que mantém o controle de nossos swaps, 953 00:40:04,210 --> 00:40:08,370 porque precisamos ter certeza de que estamos verificando isso. 954 00:40:08,370 --> 00:40:11,830 E iteramos toda a matriz como acabamos de fazer com este exemplo. 955 00:40:11,830 --> 00:40:12,900 956 00:40:12,900 --> 00:40:17,325 Se o elemento é maior do que antes o elemento depois de onde estamos, 957 00:40:17,325 --> 00:40:20,760 nós trocá-los e incrementamos nossa contador, porque assim que trocar, 958 00:40:20,760 --> 00:40:23,850 queremos deixar o nosso contador de saber disso. 959 00:40:23,850 --> 00:40:26,247 Qualquer dúvida lá? 960 00:40:26,247 --> 00:40:27,580 Algo parece engraçado aqui. 961 00:40:27,580 --> 00:40:29,225 962 00:40:29,225 --> 00:40:32,350 ALUNO: Você colocar o contador a zero cada vez que você passar pelo loop? 963 00:40:32,350 --> 00:40:34,339 Você não vai manter de volta a zero todas as vezes? 964 00:40:34,339 --> 00:40:35,505 INSTRUTOR: Não necessariamente. 965 00:40:35,505 --> 00:40:39,710 Então, o que acontece é que passamos aqui. 966 00:40:39,710 --> 00:40:43,830 Então faça enquanto, lembre-se, este será executado uma vez, sem falhar. 967 00:40:43,830 --> 00:40:46,480 Então ele vai definir o contador igual a zero, 968 00:40:46,480 --> 00:40:48,070 em seguida, ele vai para percorrer. 969 00:40:48,070 --> 00:40:50,590 Como se repete através de, ele irá atualizar balcão. 970 00:40:50,590 --> 00:40:51,870 971 00:40:51,870 --> 00:40:56,900 Como ele atualiza balcão, quando ele é feito, quando é atingido o final da matriz, 972 00:40:56,900 --> 00:41:00,830 se a nossa lista não tenha sido resolvido, contador foram atualizados. 973 00:41:00,830 --> 00:41:01,840 974 00:41:01,840 --> 00:41:07,150 >> Então ele verifica o estado de conservação e diz, OK, é contador maior que zero. 975 00:41:07,150 --> 00:41:09,290 Se for isso, fazê-lo novamente. 976 00:41:09,290 --> 00:41:14,340 Você deseja redefinir para que quando você percorrer, contador é igual a zero. 977 00:41:14,340 --> 00:41:18,240 Se você passar por uma ordenada array, nada muda, 978 00:41:18,240 --> 00:41:21,355 isso falhar, e você voltar a lista ordenada. 979 00:41:21,355 --> 00:41:23,104 980 00:41:23,104 --> 00:41:24,020 Será que isso faz sentido? 981 00:41:24,020 --> 00:41:24,940 982 00:41:24,940 --> 00:41:26,356 Estudante: Poderia nos um pouco. 983 00:41:26,356 --> 00:41:27,147 INSTRUTOR: OK. 984 00:41:27,147 --> 00:41:28,980 Se há qualquer outra questão que vem à tona. 985 00:41:28,980 --> 00:41:30,180 986 00:41:30,180 --> 00:41:30,680 Sim. 987 00:41:30,680 --> 00:41:33,760 >> Estudante: Qual seria a função ser para trocar os elementos? 988 00:41:33,760 --> 00:41:36,900 >> INSTRUTOR: Então podemos realmente escrever que, se nós estamos indo agora. 989 00:41:36,900 --> 00:41:37,801 990 00:41:37,801 --> 00:41:38,300 Legal. 991 00:41:38,300 --> 00:41:42,155 Então, nessa nota, Alison vai para voltar para o aparelho. 992 00:41:42,155 --> 00:41:43,080 Vai ser divertido. 993 00:41:43,080 --> 00:41:45,170 994 00:41:45,170 --> 00:41:47,390 E nós temos o nosso bom bolha coisa tipo aqui. 995 00:41:47,390 --> 00:41:50,800 Então, eu já fiz ciclismo através da matriz. 996 00:41:50,800 --> 00:41:53,030 Nós temos nossos swaps que são iguais a zero. 997 00:41:53,030 --> 00:41:54,480 998 00:41:54,480 --> 00:41:58,440 Por isso, queremos trocar adjacente elementos se eles estão fora de ordem. 999 00:41:58,440 --> 00:42:03,020 Então, a primeira coisa que precisamos não é iterar nossa matriz. 1000 00:42:03,020 --> 00:42:04,500 1001 00:42:04,500 --> 00:42:08,260 >> Então, como você acha que pode iterar nossa matriz? 1002 00:42:08,260 --> 00:42:09,720 1003 00:42:09,720 --> 00:42:13,990 Temos para e i é igual a 0. 1004 00:42:13,990 --> 00:42:16,950 1005 00:42:16,950 --> 00:42:22,454 Queremos i a ser menos que n menos 1 menos k. 1006 00:42:22,454 --> 00:42:23,870 E eu vou explicar isso em um segundo. 1007 00:42:23,870 --> 00:42:26,280 1008 00:42:26,280 --> 00:42:32,830 Portanto, esta é uma otimização aqui, onde, me lembro como eu disse após cada passagem 1009 00:42:32,830 --> 00:42:36,655 através da matriz de nós sei que tudo o que é on-- 1010 00:42:36,655 --> 00:42:43,590 1011 00:42:43,590 --> 00:42:46,295 >> Então, depois de um passe de nós sabemos que este é classificado. 1012 00:42:46,295 --> 00:42:47,370 1013 00:42:47,370 --> 00:42:50,060 Após dois passes sabemos que tudo isso está classificada. 1014 00:42:50,060 --> 00:42:52,750 Depois de três passagens de nós sei que é classificada. 1015 00:42:52,750 --> 00:42:55,620 Assim, a maneira que eu estou interagindo através da matriz aqui, 1016 00:42:55,620 --> 00:43:01,090 se ele está certificando-se de ir apenas através do que sabemos é indiferenciado. 1017 00:43:01,090 --> 00:43:01,644 Ok? 1018 00:43:01,644 --> 00:43:02,810 Isso é apenas uma otimização. 1019 00:43:02,810 --> 00:43:04,430 1020 00:43:04,430 --> 00:43:08,210 Você pode escrevê-lo apenas ingenuamente iteração através de tudo, 1021 00:43:08,210 --> 00:43:09,970 seria apenas levar mais tempo. 1022 00:43:09,970 --> 00:43:12,470 Com este ciclo de quatro é apenas uma boa otimização 1023 00:43:12,470 --> 00:43:18,460 porque sabemos que após cada cheia iteração através da matriz aqui, 1024 00:43:18,460 --> 00:43:24,050 como cada ciclo completo aqui, sabemos que um mais destes elementos 1025 00:43:24,050 --> 00:43:25,760 serão classificados no final. 1026 00:43:25,760 --> 00:43:28,294 >> Portanto, não precisa se preocupar com aqueles. 1027 00:43:28,294 --> 00:43:29,710 Será que isso faz sentido para todos? 1028 00:43:29,710 --> 00:43:30,950 Esse truque pouco fria? 1029 00:43:30,950 --> 00:43:32,060 1030 00:43:32,060 --> 00:43:37,270 Então, nesse caso, se estamos interagindo através, 1031 00:43:37,270 --> 00:43:50,590 sabemos que queremos verificar se matriz n e n + 1 estão em ordem. 1032 00:43:50,590 --> 00:43:52,640 1033 00:43:52,640 --> 00:43:53,559 Está bem. 1034 00:43:53,559 --> 00:43:54,600 Então aqui está o pseudocódigo. 1035 00:43:54,600 --> 00:43:57,540 Queremos verificar se a matriz n e n mais 1 estão em ordem. 1036 00:43:57,540 --> 00:43:59,520 Então, o que podemos ter lá? 1037 00:43:59,520 --> 00:44:01,090 1038 00:44:01,090 --> 00:44:03,120 Vai ser uma condicional. 1039 00:44:03,120 --> 00:44:04,220 Será um caso. 1040 00:44:04,220 --> 00:44:07,066 >> ALUNO: Se array n é inferior a matriz n mais 1. 1041 00:44:07,066 --> 00:44:07,816 INSTRUTOR: Mm-hm. 1042 00:44:07,816 --> 00:44:09,000 1043 00:44:09,000 --> 00:44:10,699 Bem, inferior ou superior. 1044 00:44:10,699 --> 00:44:11,615 ALUNO: Maior que. 1045 00:44:11,615 --> 00:44:15,850 1046 00:44:15,850 --> 00:44:17,620 Então eu quero trocá-los. 1047 00:44:17,620 --> 00:44:18,570 Exatamente. 1048 00:44:18,570 --> 00:44:23,570 Portanto, agora entramos em qual é a mecanismo para troca-los? 1049 00:44:23,570 --> 00:44:24,840 1050 00:44:24,840 --> 00:44:28,137 Então nós passamos por isso brevemente, um tipo de função swap na semana passada. 1051 00:44:28,137 --> 00:44:29,595 Alguém se lembra como funcionava? 1052 00:44:29,595 --> 00:44:32,300 1053 00:44:32,300 --> 00:44:34,950 Portanto, não podemos apenas reenviá-los, certo? 1054 00:44:34,950 --> 00:44:36,640 Porque um deles vai se perder. 1055 00:44:36,640 --> 00:44:41,696 Se disséssemos A é igual a B e depois B é igual a A, toda uma súbita ambos 1056 00:44:41,696 --> 00:44:43,150 são apenas igual a B. 1057 00:44:43,150 --> 00:44:45,720 >> Então o que temos a fazer é que tem uma variável temporária que é 1058 00:44:45,720 --> 00:44:49,055 vai realizar um dos nossos enquanto estamos no processo de troca. 1059 00:44:49,055 --> 00:44:50,200 1060 00:44:50,200 --> 00:44:56,464 Então, o que temos é que vamos ter alguns int temperatura é igual a-- você pode atribuí-lo 1061 00:44:56,464 --> 00:44:59,130 para qualquer um que você quiser, basta certifique-se de manter o controle de ele-- 1062 00:44:59,130 --> 00:45:01,840 portanto, neste caso, eu vou atribuí-la a matriz n + 1. 1063 00:45:01,840 --> 00:45:03,360 1064 00:45:03,360 --> 00:45:07,674 Então, isso vai segurar o que quer valor é nesse segundo bloco 1065 00:45:07,674 --> 00:45:08,590 que nós estamos olhando. 1066 00:45:08,590 --> 00:45:09,700 1067 00:45:09,700 --> 00:45:13,240 >> E então o que podemos fazer é que podemos ir frente e variedade Reassign n + 1, 1068 00:45:13,240 --> 00:45:14,990 porque sabemos que que têm valor armazenado. 1069 00:45:14,990 --> 00:45:16,645 1070 00:45:16,645 --> 00:45:19,270 Este é também um dos grandes coisas- Eu não sei se algum de vocês 1071 00:45:19,270 --> 00:45:23,780 tivemos problemas onde se alternam dois linhas de código, de repente as coisas funcionavam. 1072 00:45:23,780 --> 00:45:25,880 Ordem é muito importante no CS. 1073 00:45:25,880 --> 00:45:29,450 Então, certifique-se de diagrama coisas, se possível 1074 00:45:29,450 --> 00:45:31,230 sobre o que está realmente acontecendo. 1075 00:45:31,230 --> 00:45:34,256 Então agora nós vamos reatribuir array n + 1, 1076 00:45:34,256 --> 00:45:36,005 porque sabemos que que têm valor armazenado. 1077 00:45:36,005 --> 00:45:37,090 1078 00:45:37,090 --> 00:45:41,560 >> E podemos atribuir isso a matriz n ou neste caso variedade i. 1079 00:45:41,560 --> 00:45:50,540 1080 00:45:50,540 --> 00:45:51,465 Muitas variáveis. 1081 00:45:51,465 --> 00:45:54,230 1082 00:45:54,230 --> 00:45:55,470 Está bem. 1083 00:45:55,470 --> 00:46:01,500 Matriz Então agora temos transferido i mais um para igualar o que está na matriz i. 1084 00:46:01,500 --> 00:46:08,240 E agora podemos voltar e atribuir gama i com o quê? 1085 00:46:08,240 --> 00:46:10,680 1086 00:46:10,680 --> 00:46:11,180 Qualquer um? 1087 00:46:11,180 --> 00:46:13,490 1088 00:46:13,490 --> 00:46:14,010 >> Estudante: 10. 1089 00:46:14,010 --> 00:46:14,680 >> INSTRUTOR: 10. 1090 00:46:14,680 --> 00:46:15,180 Exatamente. 1091 00:46:15,180 --> 00:46:16,930 1092 00:46:16,930 --> 00:46:18,640 E uma última coisa. 1093 00:46:18,640 --> 00:46:21,840 Se temos trocado agora, o que precisamos fazer? 1094 00:46:21,840 --> 00:46:23,740 O que é a única coisa que vai nos dizer 1095 00:46:23,740 --> 00:46:27,542 se alguma vez terminar este programa? 1096 00:46:27,542 --> 00:46:29,250 O que nos diz que tem uma lista ordenada? 1097 00:46:29,250 --> 00:46:31,560 1098 00:46:31,560 --> 00:46:33,750 Se não executar quaisquer swaps, certo? 1099 00:46:33,750 --> 00:46:36,900 Se permutas é igual de zero no final desta. 1100 00:46:36,900 --> 00:46:42,975 Assim, sempre que você realizar uma troca, como nós apenas fiz aqui, queremos atualizar swaps. 1101 00:46:42,975 --> 00:46:45,002 1102 00:46:45,002 --> 00:46:47,210 E eu sei que houve uma pergunta anterior sobre você puder 1103 00:46:47,210 --> 00:46:49,689 usar zero ou um, em vez de verdadeiro ou falso. 1104 00:46:49,689 --> 00:46:50,980 E isso é o que isso faz aqui. 1105 00:46:50,980 --> 00:46:52,750 Portanto, este diz que se não swaps. 1106 00:46:52,750 --> 00:47:01,310 Portanto, se permutas é zero, o que eu é-- sempre chegar em minhas verdades e meus falsos misturados. 1107 00:47:01,310 --> 00:47:03,960 Queremos nos avaliar a verdade e não é. 1108 00:47:03,960 --> 00:47:07,680 1109 00:47:07,680 --> 00:47:09,630 Então, se é zero, então é falsa. 1110 00:47:09,630 --> 00:47:12,560 Se negar-o com um [? bater?] torna-se verdade. 1111 00:47:12,560 --> 00:47:13,975 Então esta linha executa. 1112 00:47:13,975 --> 00:47:15,060 1113 00:47:15,060 --> 00:47:17,370 >> Verdades e falsas e zeros e uns ficar louco. 1114 00:47:17,370 --> 00:47:20,690 Assim, se você andar devagar por isso ele vai fazer sentido. 1115 00:47:20,690 --> 00:47:23,320 Mas isso é o que este pequeno pouco de código aqui faz. 1116 00:47:23,320 --> 00:47:26,490 Portanto, este verifica fizemos quaisquer swaps. 1117 00:47:26,490 --> 00:47:30,054 Então, se é nada além zero, que vai ser falsa 1118 00:47:30,054 --> 00:47:31,970 e toda a coisa é indo para executar novamente. 1119 00:47:31,970 --> 00:47:33,150 1120 00:47:33,150 --> 00:47:33,650 Legal? 1121 00:47:33,650 --> 00:47:34,660 1122 00:47:34,660 --> 00:47:36,000 >> Estudante: O que faz pausa fazer? 1123 00:47:36,000 --> 00:47:38,990 >> INSTRUTOR: Quebre apenas quebra-lo para fora do loop. 1124 00:47:38,990 --> 00:47:41,570 Portanto, neste caso, seria assim como acabar com o programa 1125 00:47:41,570 --> 00:47:43,828 e você teria apenas tem sua lista classificada. 1126 00:47:43,828 --> 00:47:44,536 ESTUDANTE: Amazing. 1127 00:47:44,536 --> 00:47:48,094 1128 00:47:48,094 --> 00:47:49,010 INSTRUTOR: Eu sinto muito? 1129 00:47:49,010 --> 00:47:52,110 ESTUDANTE: Como previamente usado por escrito sobre um escrito de zero 1130 00:47:52,110 --> 00:47:54,170 apresentar que, se que vai funcionar ou não. 1131 00:47:54,170 --> 00:47:54,878 >> INSTRUTOR: Yeah. 1132 00:47:54,878 --> 00:47:56,410 Assim, você pode retornar zero ou um. 1133 00:47:56,410 --> 00:47:58,950 Neste caso, porque não estamos realmente fazer qualquer coisa com a função, 1134 00:47:58,950 --> 00:48:00,150 nós só queremos que quebre. 1135 00:48:00,150 --> 00:48:02,680 Nós realmente não se preocupam com isso. 1136 00:48:02,680 --> 00:48:06,960 Brake também é bom se ele é usado para sair 1137 00:48:06,960 --> 00:48:10,710 de quatro lacetes ou condições que você não quer manter a execução. 1138 00:48:10,710 --> 00:48:12,110 Ele só leva você para fora deles. 1139 00:48:12,110 --> 00:48:13,587 1140 00:48:13,587 --> 00:48:14,795 É um pouco de uma coisa nuance. 1141 00:48:14,795 --> 00:48:16,737 1142 00:48:16,737 --> 00:48:18,445 Eu sinto que há uma grande quantidade de mão de ondulação, 1143 00:48:18,445 --> 00:48:19,740 como você vai aprender sobre isso em breve. 1144 00:48:19,740 --> 00:48:20,955 >> Mas você vai aprender sobre isso em breve. 1145 00:48:20,955 --> 00:48:21,500 Eu prometo. 1146 00:48:21,500 --> 00:48:22,670 1147 00:48:22,670 --> 00:48:23,170 Está bem. 1148 00:48:23,170 --> 00:48:24,840 Assim que todos obter bubble sort? 1149 00:48:24,840 --> 00:48:25,550 Não é tão ruim. 1150 00:48:25,550 --> 00:48:31,910 Iterar, coisas de swap, utilizando uma variável temp, e que está tudo pronto lá? 1151 00:48:31,910 --> 00:48:32,960 Legal. 1152 00:48:32,960 --> 00:48:34,080 Impressionante. 1153 00:48:34,080 --> 00:48:34,807 Está bem. 1154 00:48:34,807 --> 00:48:35,765 Voltar para o PowerPoint. 1155 00:48:35,765 --> 00:48:38,140 1156 00:48:38,140 --> 00:48:40,130 Quaisquer dúvidas em geral sobre estes até agora? 1157 00:48:40,130 --> 00:48:41,200 1158 00:48:41,200 --> 00:48:41,700 Legal. 1159 00:48:41,700 --> 00:48:43,110 1160 00:48:43,110 --> 00:48:43,695 Mm-hm. 1161 00:48:43,695 --> 00:48:45,279 >> Estudante: [inaudível] int main normalmente. 1162 00:48:45,279 --> 00:48:46,695 Você tem que ter que para isso? 1163 00:48:46,695 --> 00:48:48,400 1164 00:48:48,400 --> 00:48:53,550 >> INSTRUTOR: Então, nós apenas procurando apenas no algoritmo de ordenação real. 1165 00:48:53,550 --> 00:48:54,559 1166 00:48:54,559 --> 00:48:56,350 Se você tivesse que dentro como um programa maior, 1167 00:48:56,350 --> 00:48:57,891 você teria um lugar principal int. 1168 00:48:57,891 --> 00:49:00,070 1169 00:49:00,070 --> 00:49:02,880 Dependendo de onde você usar este algoritmo, 1170 00:49:02,880 --> 00:49:05,860 seria determinar o que é sendo devolvido por ela. 1171 00:49:05,860 --> 00:49:09,960 Mas, para o nosso caso, estamos estritamente olhando como faz isso, na verdade, 1172 00:49:09,960 --> 00:49:11,300 iterar através de um array. 1173 00:49:11,300 --> 00:49:12,570 Portanto, não se preocupe com isso. 1174 00:49:12,570 --> 00:49:14,150 1175 00:49:14,150 --> 00:49:19,830 >> Então, nós estávamos falando sobre melhor caso e os piores cenários de busca binária. 1176 00:49:19,830 --> 00:49:22,470 Por isso, é também importante fazer que, para cada um dos nossos tipos. 1177 00:49:22,470 --> 00:49:24,200 1178 00:49:24,200 --> 00:49:27,560 Então, o que você acha que é o pior caso de execução de bubble sort? 1179 00:49:27,560 --> 00:49:29,560 1180 00:49:29,560 --> 00:49:30,700 Vocês lembram-se? 1181 00:49:30,700 --> 00:49:31,784 >> ALUNO: N menos 1. 1182 00:49:31,784 --> 00:49:32,700 INSTRUTOR: N menos 1. 1183 00:49:32,700 --> 00:49:35,070 Então isso significa que há n menos 1 comparações. 1184 00:49:35,070 --> 00:49:40,060 Então, uma coisa a perceber é que na primeira iteração, 1185 00:49:40,060 --> 00:49:43,360 que passamos, nós comparamos estes dois-- de modo que é um. 1186 00:49:43,360 --> 00:49:46,685 Estes dois, três, quatro. 1187 00:49:46,685 --> 00:49:48,070 1188 00:49:48,070 --> 00:49:55,050 Então, depois de uma iteração nós já tem quatro comparações. 1189 00:49:55,050 --> 00:49:58,230 Quando eu estou falando de tempo de execução e n. 1190 00:49:58,230 --> 00:50:04,680 N representa o número de comparações como uma função de quantos elementos 1191 00:50:04,680 --> 00:50:05,570 temos. 1192 00:50:05,570 --> 00:50:06,430 Ok? 1193 00:50:06,430 --> 00:50:08,860 >> Assim que passamos, temos quatro. 1194 00:50:08,860 --> 00:50:11,780 A próxima vez que você sabe que não fazer tem que cuidar do presente. 1195 00:50:11,780 --> 00:50:15,140 Nós comparamos os dois, estes dois, estes dois, 1196 00:50:15,140 --> 00:50:20,050 e se não tivéssemos que a otimização com o ciclo de quatro que eu escrevi, 1197 00:50:20,050 --> 00:50:22,750 você estaria comparando aqui de qualquer forma. 1198 00:50:22,750 --> 00:50:26,170 Então você teria que executado através da matriz 1199 00:50:26,170 --> 00:50:34,380 e fazer comparações n n vezes, porque cada vez que 1200 00:50:34,380 --> 00:50:36,670 executar, através dele, tipo uma coisa. 1201 00:50:36,670 --> 00:50:38,300 1202 00:50:38,300 --> 00:50:41,475 >> E cada vez que percorrem a matriz, fazemos n comparações. 1203 00:50:41,475 --> 00:50:42,920 1204 00:50:42,920 --> 00:50:46,330 Assim, o nosso tempo de execução para isso é na verdade, n ao quadrado, que 1205 00:50:46,330 --> 00:50:48,400 é muito pior em nossa log final, porque isso 1206 00:50:48,400 --> 00:50:51,965 significa se tivéssemos quatro bilhão de elementos, é 1207 00:50:51,965 --> 00:50:55,260 vai nos levar de quatro bilhões quadrados em vez de 32. 1208 00:50:55,260 --> 00:51:01,240 Então, não é o melhor tempo de execução, mas para algumas coisas, 1209 00:51:01,240 --> 00:51:04,610 você sabe, se você estiver dentro um certo intervalo de elementos 1210 00:51:04,610 --> 00:51:06,540 bubble sort pode ser bom para usar. 1211 00:51:06,540 --> 00:51:07,530 >> Está bem. 1212 00:51:07,530 --> 00:51:12,290 Então agora o que é o melhor caso de tempo de execução? 1213 00:51:12,290 --> 00:51:14,357 1214 00:51:14,357 --> 00:51:14,940 ALUNO: Zero? 1215 00:51:14,940 --> 00:51:16,420 Ou 1? 1216 00:51:16,420 --> 00:51:18,140 >> INSTRUTOR: Então um faria ser uma comparação. 1217 00:51:18,140 --> 00:51:19,114 Right. 1218 00:51:19,114 --> 00:51:20,002 >> ALUNO: N menos 1? 1219 00:51:20,002 --> 00:51:21,380 1220 00:51:21,380 --> 00:51:22,320 >> INSTRUTOR: Então, sim. 1221 00:51:22,320 --> 00:51:22,990 Então n menos um. 1222 00:51:22,990 --> 00:51:26,510 Sempre que você tem um conceito como n menos 1, temos a tendência de simplesmente deixá-la 1223 00:51:26,510 --> 00:51:31,680 e nós apenas dizer n porque você tem comparar cada um dos these-- cada par. 1224 00:51:31,680 --> 00:51:36,470 Portanto, seria n menos 1, que nós que tinha acabado de dizer é aproximadamente n. 1225 00:51:36,470 --> 00:51:39,280 Quando você está lidando com tempo de execução, tudo está em aproxima. 1226 00:51:39,280 --> 00:51:43,860 Contanto que é o expoente correto, você é muito bom. 1227 00:51:43,860 --> 00:51:45,700 >> Essa é a forma como lidamos com ele. 1228 00:51:45,700 --> 00:51:47,410 1229 00:51:47,410 --> 00:51:51,780 Assim que o melhor caso é n, que significa que a lista já está classificado, 1230 00:51:51,780 --> 00:51:54,320 e tudo o que fazemos é executado através de e verifique se ele está classificada. 1231 00:51:54,320 --> 00:51:56,110 1232 00:51:56,110 --> 00:51:56,855 Legal. 1233 00:51:56,855 --> 00:51:57,355 Tudo certo. 1234 00:51:57,355 --> 00:51:58,980 1235 00:51:58,980 --> 00:52:01,920 Então, como você vê aqui, nós só tem mais alguns gráficos. 1236 00:52:01,920 --> 00:52:02,660 Então n ao quadrado. 1237 00:52:02,660 --> 00:52:03,780 1238 00:52:03,780 --> 00:52:05,120 Fun. 1239 00:52:05,120 --> 00:52:09,730 Muito pior do que n, como vemos, e muito, muito pior do que 2n log. 1240 00:52:09,730 --> 00:52:12,060 E então você começa também em registro registros. 1241 00:52:12,060 --> 00:52:18,020 E você pega 124, você entrar em como a estrela de log, que é como um louco. 1242 00:52:18,020 --> 00:52:20,172 Então, se você estiver interessado, estrela log de pesquisa. 1243 00:52:20,172 --> 00:52:20,880 É uma espécie de diversão. 1244 00:52:20,880 --> 00:52:22,800 1245 00:52:22,800 --> 00:52:24,220 Portanto, temos este grande gráfico. 1246 00:52:24,220 --> 00:52:25,360 1247 00:52:25,360 --> 00:52:28,720 Apenas um heads-up, este um gráfico maravilhoso ter 1248 00:52:28,720 --> 00:52:31,350 para o seu meio-termo, porque nós tempo para perguntar-lhe estas dilui. 1249 00:52:31,350 --> 00:52:36,090 Assim, apenas a cabeça para cima, tem este em seu intercalar sobre a sua folha de fraude bom 1250 00:52:36,090 --> 00:52:36,616 lá. 1251 00:52:36,616 --> 00:52:37,990 Então, nós apenas olhou para bubble sort. 1252 00:52:37,990 --> 00:52:39,510 1253 00:52:39,510 --> 00:52:42,370 Na pior das hipóteses, n ao quadrado, melhor caso, n. 1254 00:52:42,370 --> 00:52:43,367 1255 00:52:43,367 --> 00:52:44,950 E nós vamos olhar para os outros. 1256 00:52:44,950 --> 00:52:47,940 >> E como você pode ver, a única um que realmente faz bem 1257 00:52:47,940 --> 00:52:50,910 é merge sort, que nós vamos entrar em porquê. 1258 00:52:50,910 --> 00:52:52,690 1259 00:52:52,690 --> 00:52:55,215 Então, nós estamos indo para ir para o ao lado um tipo de seleção aqui--. 1260 00:52:55,215 --> 00:52:56,360 1261 00:52:56,360 --> 00:52:58,420 Alguém se lembra como seleção espécie trabalhou? 1262 00:52:58,420 --> 00:53:05,200 1263 00:53:05,200 --> 00:53:05,700 Vá em frente. 1264 00:53:05,700 --> 00:53:08,210 >> ALUNO: Basicamente passar por uma ordem e criar uma nova lista. 1265 00:53:08,210 --> 00:53:11,001 E assim como você está colocando elementos em, colocá-los no lugar certo 1266 00:53:11,001 --> 00:53:11,750 na nova lista. 1267 00:53:11,750 --> 00:53:14,040 >> INSTRUTOR: Assim que os sons mais como ordenação por inserção. 1268 00:53:14,040 --> 00:53:15,040 Mas você está realmente perto. 1269 00:53:15,040 --> 00:53:15,915 Eles são muito semelhantes. 1270 00:53:15,915 --> 00:53:17,440 Mesmo eu pegá-los misturados às vezes. 1271 00:53:17,440 --> 00:53:18,981 Antes desta seção eu era como, esperar. 1272 00:53:18,981 --> 00:53:20,130 1273 00:53:20,130 --> 00:53:20,630 Está bem. 1274 00:53:20,630 --> 00:53:24,141 Então, o que você quer fazer é a seleção de classificação, 1275 00:53:24,141 --> 00:53:25,890 a maneira que você pode pensar sobre o assunto ea forma 1276 00:53:25,890 --> 00:53:30,140 Eu me certificar de que não tentar obter los misturados, é que atravessa 1277 00:53:30,140 --> 00:53:33,280 e seleciona o menor número e ele 1278 00:53:33,280 --> 00:53:36,070 coloca que no início da sua lista. 1279 00:53:36,070 --> 00:53:37,730 Ele troca-lo com a primeira posição. 1280 00:53:37,730 --> 00:53:42,600 1281 00:53:42,600 --> 00:53:45,370 Eles realmente têm um exemplo para mim. 1282 00:53:45,370 --> 00:53:46,540 Impressionante. 1283 00:53:46,540 --> 00:53:50,130 Assim, apenas uma maneira de pensar em seleção ele-- tipo, selecione o menor valor. 1284 00:53:50,130 --> 00:53:51,940 E nós estamos indo executado através de um exemplo 1285 00:53:51,940 --> 00:53:55,320 que eu acho que vai ajudar, porque Acho visuais sempre ajudar. 1286 00:53:55,320 --> 00:53:58,510 Então, vamos começar com algo que é completamente indiferenciados. 1287 00:53:58,510 --> 00:54:00,730 Red será indiferenciados, verde serão classificados. 1288 00:54:00,730 --> 00:54:02,190 Tudo fará sentido em um segundo. 1289 00:54:02,190 --> 00:54:08,950 >> Então nós passamos por e iteramos desde o início até o fim. 1290 00:54:08,950 --> 00:54:12,320 E nós dizemos: OK, 2 é nosso menor número. 1291 00:54:12,320 --> 00:54:15,680 Então, nós vamos tomar dois e vamos para movê-lo para a frente da nossa matriz 1292 00:54:15,680 --> 00:54:17,734 porque é a menor número que temos. 1293 00:54:17,734 --> 00:54:19,150 Então, isso é o que este está fazendo aqui. 1294 00:54:19,150 --> 00:54:20,820 Ele só vai trocar os dois. 1295 00:54:20,820 --> 00:54:21,850 1296 00:54:21,850 --> 00:54:25,450 Então agora temos um classificado parte e uma parte não classificado. 1297 00:54:25,450 --> 00:54:27,810 E o que é bom lembrar sobre a seleção de tipo 1298 00:54:27,810 --> 00:54:30,690 é que estamos selecionando apenas da parte não classificado. 1299 00:54:30,690 --> 00:54:32,220 1300 00:54:32,220 --> 00:54:34,527 >> A parte ordenada você acabou de sair sozinho. 1301 00:54:34,527 --> 00:54:35,660 Mm-hm? 1302 00:54:35,660 --> 00:54:38,452 >> ESTUDANTE: Como ele sabe o que é o menor sem compará-lo 1303 00:54:38,452 --> 00:54:39,868 para todos os outros valores na matriz. 1304 00:54:39,868 --> 00:54:41,250 INSTRUTOR: Ele faz compará-lo. 1305 00:54:41,250 --> 00:54:42,041 Nós gostamos de ignorados. 1306 00:54:42,041 --> 00:54:43,850 Este é apenas geral global. 1307 00:54:43,850 --> 00:54:44,831 Sim. 1308 00:54:44,831 --> 00:54:47,205 Quando escrevemos o código que eu sou certeza que você vai estar mais satisfeito. 1309 00:54:47,205 --> 00:54:48,696 1310 00:54:48,696 --> 00:54:53,030 Mas você guarde este primeiro elemento como a menor. 1311 00:54:53,030 --> 00:54:56,110 Você compara e você dizer, OK, é menor? 1312 00:54:56,110 --> 00:54:56,660 Sim. 1313 00:54:56,660 --> 00:54:57,460 Mantê-lo. 1314 00:54:57,460 --> 00:54:58,640 Aqui é menor? 1315 00:54:58,640 --> 00:54:59,660 Não? 1316 00:54:59,660 --> 00:55:02,510 >> Esta é a sua menor, transferir-lo para o seu valor. 1317 00:55:02,510 --> 00:55:06,340 E você será muito mais feliz quando vamos através do código. 1318 00:55:06,340 --> 00:55:07,510 1319 00:55:07,510 --> 00:55:13,970 Então nós passamos, nós trocá-lo, por isso, em seguida, olharmos para esta parcela não classificado. 1320 00:55:13,970 --> 00:55:15,810 Então, nós estamos indo para selecionar três. 1321 00:55:15,810 --> 00:55:18,890 Nós estamos indo para colocá-lo em pelo o fim da nossa parte ordenada. 1322 00:55:18,890 --> 00:55:20,267 1323 00:55:20,267 --> 00:55:23,100 E nós apenas estamos indo para continuar fazendo que, fazendo isso, e fazendo isso. 1324 00:55:23,100 --> 00:55:24,130 1325 00:55:24,130 --> 00:55:27,420 Portanto, este é o nosso tipo de pseudocódigo aqui. 1326 00:55:27,420 --> 00:55:29,470 1327 00:55:29,470 --> 00:55:31,380 Vamos codificar-lo aqui em um segundo. 1328 00:55:31,380 --> 00:55:34,140 1329 00:55:34,140 --> 00:55:37,270 Mas só uma coisa de andar através de um nível elevado. 1330 00:55:37,270 --> 00:55:40,275 Você está indo para ir de i é igual a 0 para n menos 2. 1331 00:55:40,275 --> 00:55:41,570 1332 00:55:41,570 --> 00:55:43,530 Essa é outra otimização. 1333 00:55:43,530 --> 00:55:45,020 Não se preocupe muito com isso. 1334 00:55:45,020 --> 00:55:46,620 Então, como você estava dizendo. 1335 00:55:46,620 --> 00:55:49,660 1336 00:55:49,660 --> 00:55:54,406 Como Jacob estava dizendo, como nós acompanhar o que o nosso mínimo é? 1337 00:55:54,406 --> 00:55:55,030 Como sabemos? 1338 00:55:55,030 --> 00:55:57,060 Nós temos que comparar tudo em nossa lista. 1339 00:55:57,060 --> 00:55:59,600 >> Então mínimo é igual a i. 1340 00:55:59,600 --> 00:56:03,870 É só dizer, neste caso, o índice do nosso valor mínimo. 1341 00:56:03,870 --> 00:56:07,660 Então ele vai para percorrer e ele vai de j é igual a i + 1. 1342 00:56:07,660 --> 00:56:11,420 Então já sabemos que esse é o nosso primeiro elemento. 1343 00:56:11,420 --> 00:56:13,240 Nós não precisamos de compará-lo a si mesmo. 1344 00:56:13,240 --> 00:56:16,970 Então nós começamos a compará-lo com o próximo aquele que é por isso que é i + 1 para n 1345 00:56:16,970 --> 00:56:20,110 menos 1, que é a final da matriz lá. 1346 00:56:20,110 --> 00:56:25,090 E nós dissemos, se da matriz em j é inferior a matriz min, 1347 00:56:25,090 --> 00:56:29,200 então nós realocar onde nossos índices mínimos é. 1348 00:56:29,200 --> 00:56:37,470 >> E se não min é igual a i, tal como em que estávamos de volta para cá. 1349 00:56:37,470 --> 00:56:38,950 1350 00:56:38,950 --> 00:56:41,790 Assim como quando fizemos primeiro um presente. 1351 00:56:41,790 --> 00:56:49,310 Neste caso, ele iria começar a zero, ele acabaria sendo dois. 1352 00:56:49,310 --> 00:56:53,010 Assim, não seria igual min i na final. 1353 00:56:53,010 --> 00:56:55,720 Isso nos permite saber que precisamos trocá-los. 1354 00:56:55,720 --> 00:56:57,420 1355 00:56:57,420 --> 00:57:00,470 Eu me sinto como um exemplo concreto vai ajudar muito mais do que isso. 1356 00:57:00,470 --> 00:57:04,970 Então, eu vou codificar isso com vocês agora e eu acho que vai ser melhor. 1357 00:57:04,970 --> 00:57:07,380 1358 00:57:07,380 --> 00:57:11,350 >> Tipos tendem a trabalhar dessa forma em que muitas vezes é melhor só para vê-los. 1359 00:57:11,350 --> 00:57:12,780 1360 00:57:12,780 --> 00:57:17,280 Então, o que nós queremos fazer é queremos primeiro a menor 1361 00:57:17,280 --> 00:57:19,890 elemento na sua posição na matriz. 1362 00:57:19,890 --> 00:57:21,280 Exatamente o que Jacob estava dizendo. 1363 00:57:21,280 --> 00:57:23,090 Você precisa armazenar que de alguma forma. 1364 00:57:23,090 --> 00:57:25,900 Então, vamos começar aqui iteração sobre a matriz. 1365 00:57:25,900 --> 00:57:28,970 Nós vamos dizer que é nosso primeiro apenas para começar. 1366 00:57:28,970 --> 00:57:38,308 Então, nós vamos ter int menor é igual ao da matriz em i. 1367 00:57:38,308 --> 00:57:40,500 1368 00:57:40,500 --> 00:57:45,050 >> Então, uma coisa a notar, cada tempo este loop é executado, 1369 00:57:45,050 --> 00:57:48,550 estamos começando um passo mais adiante. 1370 00:57:48,550 --> 00:57:54,780 1371 00:57:54,780 --> 00:57:57,440 Quando começamos olhamos para este. 1372 00:57:57,440 --> 00:58:00,840 A próxima vez que iterar, estamos começando em um presente 1373 00:58:00,840 --> 00:58:02,680 e atribuindo-lhe o nosso menor valor. 1374 00:58:02,680 --> 00:58:10,450 Portanto, é muito semelhante ao bubble sort onde sabemos que depois de uma passagem, 1375 00:58:10,450 --> 00:58:11,700 este último elemento é classificado. 1376 00:58:11,700 --> 00:58:12,810 1377 00:58:12,810 --> 00:58:15,120 Com a seleção de classificação, que é exatamente o oposto. 1378 00:58:15,120 --> 00:58:18,950 >> Em cada passagem, sabemos que a primeira é classificada. 1379 00:58:18,950 --> 00:58:21,360 Após a segunda passagem, o segunda será classificada. 1380 00:58:21,360 --> 00:58:26,470 E como você viu com os exemplos de slides, nossa porção ordenados não para de crescer. 1381 00:58:26,470 --> 00:58:34,020 Assim, definindo o nosso menor um para matrizes i, tudo o que está fazendo 1382 00:58:34,020 --> 00:58:37,340 constrição é o que nós estamos olhando de forma 1383 00:58:37,340 --> 00:58:40,164 para minimizar o número de comparações que fazemos. 1384 00:58:40,164 --> 00:58:41,770 Isso faz sentido para todos? 1385 00:58:41,770 --> 00:58:42,920 1386 00:58:42,920 --> 00:58:46,380 Você precisa de mim para ser executado através de que novamente mais lenta ou com palavras diferentes? 1387 00:58:46,380 --> 00:58:47,180 Estou feliz por. 1388 00:58:47,180 --> 00:58:48,095 1389 00:58:48,095 --> 00:58:48,595 Está bem. 1390 00:58:48,595 --> 00:58:50,060 1391 00:58:50,060 --> 00:58:55,540 >> Então, nós estamos armazenando o valor neste ponto, 1392 00:58:55,540 --> 00:58:57,840 mas também queremos armazenar o índice. 1393 00:58:57,840 --> 00:59:01,010 Então, nós estamos indo para armazenar o posição da menor 1394 00:59:01,010 --> 00:59:02,770 um, que só vai ser eu. 1395 00:59:02,770 --> 00:59:04,357 1396 00:59:04,357 --> 00:59:05,440 Então agora Jacob está satisfeito. 1397 00:59:05,440 --> 00:59:06,870 Nós temos coisas guardadas. 1398 00:59:06,870 --> 00:59:08,240 1399 00:59:08,240 --> 00:59:11,870 E agora temos de olhar através de a parte não separados da matriz. 1400 00:59:11,870 --> 00:59:18,170 Portanto, neste caso esta seria o nosso indiferenciados. 1401 00:59:18,170 --> 00:59:20,980 1402 00:59:20,980 --> 00:59:22,462 Este é i. 1403 00:59:22,462 --> 00:59:25,430 1404 00:59:25,430 --> 00:59:26,210 Está bem. 1405 00:59:26,210 --> 00:59:30,040 >> Então o que nós vamos fazer vai ser para um loop. 1406 00:59:30,040 --> 00:59:32,066 Sempre que você precisar iterar através de um array, 1407 00:59:32,066 --> 00:59:33,440 a sua mente poderia ir para um loop. 1408 00:59:33,440 --> 00:59:34,760 1409 00:59:34,760 --> 00:59:38,090 Assim, para alguns int k equals-- o que pensamos 1410 00:59:38,090 --> 00:59:39,700 k vai ser igual a começar com? 1411 00:59:39,700 --> 00:59:41,580 1412 00:59:41,580 --> 00:59:44,766 Isto é o que definimos como o nosso menor valor e queremos compará-lo. 1413 00:59:44,766 --> 00:59:47,090 O que nós queremos comparar? 1414 00:59:47,090 --> 00:59:48,730 Vai ser este próximo, certo? 1415 00:59:48,730 --> 00:59:53,200 Então, nós queremos k ser inicializado para i + 1 para começar. 1416 00:59:53,200 --> 00:59:55,350 1417 00:59:55,350 --> 01:00:02,800 >> E queremos k neste caso, Já tamanho armazenados aqui, 1418 01:00:02,800 --> 01:00:03,930 para que possamos usar apenas tamanho. 1419 01:00:03,930 --> 01:00:06,240 Tamanho sendo o tamanho da matriz. 1420 01:00:06,240 --> 01:00:09,620 E nós só queremos actualizar k por um de cada vez. 1421 01:00:09,620 --> 01:00:17,410 1422 01:00:17,410 --> 01:00:17,910 Legal. 1423 01:00:17,910 --> 01:00:19,650 1424 01:00:19,650 --> 01:00:23,430 Então, agora precisamos encontrar o elemento mais pequeno aqui. 1425 01:00:23,430 --> 01:00:24,470 1426 01:00:24,470 --> 01:00:31,380 Então, se nós iterar, nós quer dizer, se a matriz em k 1427 01:00:31,380 --> 01:00:37,080 é menor do que a menor value-- este é o lugar onde nós estamos, na verdade, 1428 01:00:37,080 --> 01:00:42,950 manter o controle do que é a menor aqui- 1429 01:00:42,950 --> 01:00:47,740 então queremos transferir o nosso menor valor é. 1430 01:00:47,740 --> 01:00:50,645 >> Isto significa que, oh, nós somos iteração por aqui. 1431 01:00:50,645 --> 01:00:51,699 1432 01:00:51,699 --> 01:00:53,740 Qualquer valor que está aqui é não a nossa mais pequena coisa. 1433 01:00:53,740 --> 01:00:54,448 Nós não queremos isso. 1434 01:00:54,448 --> 01:00:56,100 Queremos transferir-lo. 1435 01:00:56,100 --> 01:01:02,050 Então, se estamos a reatribuição-lo, o que fazer você acha que pode ser neste código aqui? 1436 01:01:02,050 --> 01:01:04,160 Queremos transferir menor e posição. 1437 01:01:04,160 --> 01:01:05,740 1438 01:01:05,740 --> 01:01:07,010 Então, o que é menor agora? 1439 01:01:07,010 --> 01:01:08,422 1440 01:01:08,422 --> 01:01:09,130 ESTUDANTE: Array k. 1441 01:01:09,130 --> 01:01:09,963 INSTRUTOR: Array k. 1442 01:01:09,963 --> 01:01:13,480 1443 01:01:13,480 --> 01:01:15,956 E qual é a posição agora? 1444 01:01:15,956 --> 01:01:20,940 1445 01:01:20,940 --> 01:01:23,000 O que há de os índices de nosso menor valor? 1446 01:01:23,000 --> 01:01:24,030 1447 01:01:24,030 --> 01:01:24,530 É só k. 1448 01:01:24,530 --> 01:01:25,690 1449 01:01:25,690 --> 01:01:27,790 Então matriz k, k, eles combinam. 1450 01:01:27,790 --> 01:01:31,670 1451 01:01:31,670 --> 01:01:33,120 Então, nós queríamos que realocar. 1452 01:01:33,120 --> 01:01:34,390 1453 01:01:34,390 --> 01:01:39,950 E então, depois que encontramos o menor, Assim, no final deste loop 1454 01:01:39,950 --> 01:01:45,100 aqui nós encontramos o nosso menor valor é, por isso, apenas trocá-lo. 1455 01:01:45,100 --> 01:01:47,100 1456 01:01:47,100 --> 01:01:50,816 Neste caso, como dizer que a nossa menor valor é aqui fora. 1457 01:01:50,816 --> 01:01:51,940 Este é o nosso menor valor. 1458 01:01:51,940 --> 01:01:57,690 >> Nós apenas queremos trocá-lo aqui, o que é o que esse função swap na parte inferior 1459 01:01:57,690 --> 01:02:01,270 fez, que acabamos escreveu-se junto a alguns minutos atrás. 1460 01:02:01,270 --> 01:02:02,775 Por isso, deve parecer familiar. 1461 01:02:02,775 --> 01:02:04,320 1462 01:02:04,320 --> 01:02:08,030 E então ele só vai iterar por meio até atingir todo o caminho 1463 01:02:08,030 --> 01:02:13,100 ao final, o que significa que você tem zero elementos que são indiferenciados 1464 01:02:13,100 --> 01:02:14,800 e tudo o mais foi resolvido. 1465 01:02:14,800 --> 01:02:16,216 1466 01:02:16,216 --> 01:02:16,715 Faz sentido? 1467 01:02:16,715 --> 01:02:18,010 1468 01:02:18,010 --> 01:02:19,280 Um pouco mais concretamente? 1469 01:02:19,280 --> 01:02:19,990 O código ajuda? 1470 01:02:19,990 --> 01:02:21,720 1471 01:02:21,720 --> 01:02:26,410 >> ALUNO: Para um tamanho, você nunca realmente defini-la ou alterá-la, 1472 01:02:26,410 --> 01:02:27,340 como ele sabe? 1473 01:02:27,340 --> 01:02:32,380 >> INSTRUTOR: Então uma coisa a notar-se aqui é o tamanho int. 1474 01:02:32,380 --> 01:02:35,680 Então, nós estamos dizendo neste tipo sort-- é uma função neste case-- é 1475 01:02:35,680 --> 01:02:40,770 seleção espécie, é passado na com a função. 1476 01:02:40,770 --> 01:02:43,460 Então, se não foi aprovada em, você faria algo 1477 01:02:43,460 --> 01:02:47,840 como com o comprimento da matriz ou você iterar 1478 01:02:47,840 --> 01:02:49,390 para encontrar o comprimento. 1479 01:02:49,390 --> 01:02:52,680 Mas porque ele é passado em, podemos usá-lo apenas. 1480 01:02:52,680 --> 01:02:55,720 Você simplesmente assumir que o usuário deu-lhe um tamanho válido que 1481 01:02:55,720 --> 01:02:57,698 na verdade representa um tamanho de sua matriz. 1482 01:02:57,698 --> 01:02:59,461 1483 01:02:59,461 --> 01:02:59,960 Legal? 1484 01:02:59,960 --> 01:03:01,610 1485 01:03:01,610 --> 01:03:05,870 >> Se vocês têm algum problema com estes ou quer mais prática de codificação tipos 1486 01:03:05,870 --> 01:03:08,050 em seu próprio país, você deve ir para study.cs50. 1487 01:03:08,050 --> 01:03:11,560 1488 01:03:11,560 --> 01:03:12,670 É uma ferramenta. 1489 01:03:12,670 --> 01:03:15,040 Eles têm um verificador que você pode realmente escrever. 1490 01:03:15,040 --> 01:03:16,180 Eles fazem pseudocódigo. 1491 01:03:16,180 --> 01:03:19,310 Eles têm mais vídeos e slides incluindo os que eu uso aqui. 1492 01:03:19,310 --> 01:03:23,150 Então, se você ainda estiver sentindo um pouco confuso, tente isso. 1493 01:03:23,150 --> 01:03:25,670 Como sempre, venha falar comigo, também. 1494 01:03:25,670 --> 01:03:26,320 Pergunta? 1495 01:03:26,320 --> 01:03:28,611 >> Estudante: Você está dizendo que o tamanho é previamente definido? 1496 01:03:28,611 --> 01:03:29,234 1497 01:03:29,234 --> 01:03:29,900 INSTRUTOR: Sim. 1498 01:03:29,900 --> 01:03:35,570 Tamanho é previamente definido se aqui na declaração da função. 1499 01:03:35,570 --> 01:03:39,060 Então você assume que ele tenha sido aprovada em pelo usuário, e para simplificar, 1500 01:03:39,060 --> 01:03:41,896 vamos supor que o usuário nos deu o tamanho correto. 1501 01:03:41,896 --> 01:03:43,240 Legal. 1502 01:03:43,240 --> 01:03:44,390 Então, isso é a seleção de classificação. 1503 01:03:44,390 --> 01:03:45,590 1504 01:03:45,590 --> 01:03:47,640 Gente, eu sei que nós estamos aprendendo muito hoje. 1505 01:03:47,640 --> 01:03:49,710 É uma densa dados para seção. 1506 01:03:49,710 --> 01:03:51,880 1507 01:03:51,880 --> 01:03:57,340 Então, com isso, vamos ir para a ordenação por inserção. 1508 01:03:57,340 --> 01:04:01,550 1509 01:04:01,550 --> 01:04:02,510 >> Está bem. 1510 01:04:02,510 --> 01:04:06,100 Então, antes que nós temos que fazer nossa análise runtime aqui. 1511 01:04:06,100 --> 01:04:10,190 Assim, no melhor dos casos, concedida desde que eu mostrei 1512 01:04:10,190 --> 01:04:11,960 a mesa que eu já tipo de jogou fora. 1513 01:04:11,960 --> 01:04:15,430 Mas o melhor caso de execução, o que pensamos? 1514 01:04:15,430 --> 01:04:17,310 1515 01:04:17,310 --> 01:04:18,130 Tudo resolvido. 1516 01:04:18,130 --> 01:04:21,040 1517 01:04:21,040 --> 01:04:22,070 N ao quadrado. 1518 01:04:22,070 --> 01:04:24,780 Alguém tem uma explicação por que você acha? 1519 01:04:24,780 --> 01:04:29,060 1520 01:04:29,060 --> 01:04:30,519 >> Estudante: Você está comparando through-- 1521 01:04:30,519 --> 01:04:31,268 INSTRUTOR: Certo. 1522 01:04:31,268 --> 01:04:32,540 Você está comparando através. 1523 01:04:32,540 --> 01:04:35,630 Em cada iteração, apesar de estamos diminuindo este por um, 1524 01:04:35,630 --> 01:04:38,950 você ainda está procurando por tudo para encontrar o menor. 1525 01:04:38,950 --> 01:04:42,390 Assim, mesmo se o seu menor valor É aqui, no início, 1526 01:04:42,390 --> 01:04:44,710 você ainda está comparando-a contra tudo o resto 1527 01:04:44,710 --> 01:04:46,550 para ter certeza que é a mais pequena coisa. 1528 01:04:46,550 --> 01:04:49,820 Então você vai acabar correndo por aproximadamente n vezes ao quadrado. 1529 01:04:49,820 --> 01:04:51,090 1530 01:04:51,090 --> 01:04:51,590 Tudo certo. 1531 01:04:51,590 --> 01:04:52,785 E o que é o pior caso? 1532 01:04:52,785 --> 01:04:54,350 1533 01:04:54,350 --> 01:04:57,980 Também n ao quadrado, porque você está indo estar fazendo esse mesmo procedimento. 1534 01:04:57,980 --> 01:05:01,670 Portanto, neste caso, a seleção tipo tem algo 1535 01:05:01,670 --> 01:05:04,010 que também chamamos de tempo de execução esperado. 1536 01:05:04,010 --> 01:05:07,400 Assim, nos outros, só sei os limites superiores e inferiores. 1537 01:05:07,400 --> 01:05:11,180 Dependendo de como o nosso louco lista é ou como indiferenciados é, 1538 01:05:11,180 --> 01:05:15,350 que variam entre n ou n ao quadrado. 1539 01:05:15,350 --> 01:05:16,550 Nós não sabemos. 1540 01:05:16,550 --> 01:05:22,820 >> Mas porque a seleção espécie tem o mesmo pior eo melhor caso, que nos diz que 1541 01:05:22,820 --> 01:05:25,880 não importa o tipo de entrada que ter, se é completamente 1542 01:05:25,880 --> 01:05:29,130 classificadas ou completamente reversa classificadas, é 1543 01:05:29,130 --> 01:05:30,740 vai levar a mesma quantidade de tempo. 1544 01:05:30,740 --> 01:05:33,760 Então, nesse caso, se você lembre-se da nossa mesa, 1545 01:05:33,760 --> 01:05:38,610 ele realmente tinha um valor que esses dois tipos não têm, 1546 01:05:38,610 --> 01:05:40,390 tempo de execução que é o esperado. 1547 01:05:40,390 --> 01:05:43,350 Então, nós sabemos que sempre que corremos seleção espécie, 1548 01:05:43,350 --> 01:05:45,380 é garantido que executar um tempo n ao quadrado. 1549 01:05:45,380 --> 01:05:46,630 Não há variabilidade lá. 1550 01:05:46,630 --> 01:05:47,630 É só esperar. 1551 01:05:47,630 --> 01:05:48,820 1552 01:05:48,820 --> 01:05:52,140 E, novamente, se você quer aprender mais, tomar CS 124 na primavera. 1553 01:05:52,140 --> 01:05:55,370 1554 01:05:55,370 --> 01:05:56,712 Tudo certo. 1555 01:05:56,712 --> 01:05:57,545 Nós já vimos este. 1556 01:05:57,545 --> 01:05:58,530 1557 01:05:58,530 --> 01:05:59,030 Legal. 1558 01:05:59,030 --> 01:06:00,930 Assim, tipo de inserção. 1559 01:06:00,930 --> 01:06:03,330 E eu estou indo provavelmente para brilhar por isso. 1560 01:06:03,330 --> 01:06:05,440 Eu não vou ter vocês codificá-lo. 1561 01:06:05,440 --> 01:06:06,580 Nós vamos apenas passar por ela. 1562 01:06:06,580 --> 01:06:10,500 Então ordenação por inserção é uma espécie de semelhante à seleção espécie 1563 01:06:10,500 --> 01:06:14,460 em que temos tanto um indiferenciados e ordenados parte da matriz. 1564 01:06:14,460 --> 01:06:20,260 >> Mas o que é diferente é que como se passar por um por um, 1565 01:06:20,260 --> 01:06:24,210 nós apenas tomar qualquer número é o próximo na nossa indiferenciados, 1566 01:06:24,210 --> 01:06:28,507 e classificá-lo corretamente em nossa matriz classificada. 1567 01:06:28,507 --> 01:06:30,090 Ela vai fazer mais sentido com um exemplo. 1568 01:06:30,090 --> 01:06:31,140 1569 01:06:31,140 --> 01:06:35,430 Então, tudo começa como indiferenciados, Assim como com a seleção tipo. 1570 01:06:35,430 --> 01:06:38,740 E nós vamos resolver isso em ordem ascendente como temos sido. 1571 01:06:38,740 --> 01:06:40,360 1572 01:06:40,360 --> 01:06:43,340 Então, na nossa primeira passagem tomamos o primeiro valor 1573 01:06:43,340 --> 01:06:46,700 e dizemos: OK, você está agora em uma lista por si mesmo. 1574 01:06:46,700 --> 01:06:49,150 >> Porque você está em uma lista por si mesmo, você está classificado. 1575 01:06:49,150 --> 01:06:52,460 Parabéns por ser o primeiro elemento desta matriz. 1576 01:06:52,460 --> 01:06:54,800 Você já está resolvido tudo em seu próprio país. 1577 01:06:54,800 --> 01:06:58,900 Então agora temos um classificado e um conjunto indiferenciado. 1578 01:06:58,900 --> 01:07:01,760 Então, agora vamos dar o primeiro. 1579 01:07:01,760 --> 01:07:05,600 O que acontece entre aqui e aqui está o que nós dizemos, 1580 01:07:05,600 --> 01:07:08,890 OK, vamos olhar para o primeiro valor da nossa matriz indiferenciados 1581 01:07:08,890 --> 01:07:13,270 e nós estamos indo para introduzi-lo em seu correto lugar na matriz de classificação. 1582 01:07:13,270 --> 01:07:21,460 >> Então, o que fazemos é tomar 5 e podemos dizer, OK, 5 é maior que 3, 1583 01:07:21,460 --> 01:07:24,630 por isso, só inseri-lo direito para a direita do que isso. 1584 01:07:24,630 --> 01:07:25,130 Nós somos bons. 1585 01:07:25,130 --> 01:07:26,200 1586 01:07:26,200 --> 01:07:28,420 Então vamos para o nosso próximo. 1587 01:07:28,420 --> 01:07:29,720 E tomamos dois. 1588 01:07:29,720 --> 01:07:34,330 Dizemos, OK, 2 é menos de 3, por isso sabemos que 1589 01:07:34,330 --> 01:07:36,220 precisa de estar no frente da nossa lista agora. 1590 01:07:36,220 --> 01:07:41,800 Então, o que fazemos é empurrar 3 e 5 para baixo e passamos 2 em que o primeiro slot. 1591 01:07:41,800 --> 01:07:42,990 1592 01:07:42,990 --> 01:07:45,870 Então, nós estamos apenas inserindo-o o local correto que deveria ser. 1593 01:07:45,870 --> 01:07:46,960 1594 01:07:46,960 --> 01:07:49,470 >> Então, olhamos para o nosso próximo, e nós dizemos seis. 1595 01:07:49,470 --> 01:07:53,620 OK, é maior do que 6 tudo em nossa matriz classificada, 1596 01:07:53,620 --> 01:07:56,000 por isso, só marcá-lo até o fim. 1597 01:07:56,000 --> 01:07:56,960 E então olhamos para quatro. 1598 01:07:56,960 --> 01:07:58,130 1599 01:07:58,130 --> 01:08:03,020 4 é inferior a 6, é menos que 5, mas é maior do que 3. 1600 01:08:03,020 --> 01:08:06,270 Por isso, basta inseri-lo para a direita em a meio entre 3 e 5. 1601 01:08:06,270 --> 01:08:07,380 1602 01:08:07,380 --> 01:08:10,530 Que um pouco de modo a tornar pouco mais concreto, 1603 01:08:10,530 --> 01:08:12,280 aqui é o tipo de idéia do que aconteceu. 1604 01:08:12,280 --> 01:08:16,430 Assim, para cada elemento não classificado, que determinar onde na parcela classificada 1605 01:08:16,430 --> 01:08:17,090 ele é. 1606 01:08:17,090 --> 01:08:20,680 >> Assim, tendo em mente a classificado e não classificado, 1607 01:08:20,680 --> 01:08:26,080 temos que atravessar e figura para onde ele se encaixa na matriz de classificação. 1608 01:08:26,080 --> 01:08:31,460 E nós inseri-lo, deslocando o elementos à direita do que para baixo. 1609 01:08:31,460 --> 01:08:34,910 E então nós apenas manter iterar até que 1610 01:08:34,910 --> 01:08:39,270 tem uma lista completamente resolvido onde indiferenciados agora é zero 1611 01:08:39,270 --> 01:08:41,720 e ordenada retoma a totalidade da nossa lista. 1612 01:08:41,720 --> 01:08:43,146 1613 01:08:43,146 --> 01:08:45,854 Então, novamente, para tornar as coisas ainda mais concreto, temos pseudocódigo. 1614 01:08:45,854 --> 01:08:47,979 1615 01:08:47,979 --> 01:08:52,410 >> Então, basicamente, para i é igual a 0 a n menos 1, 1616 01:08:52,410 --> 01:08:54,790 isso é apenas o comprimento da nossa matriz. 1617 01:08:54,790 --> 01:09:00,979 Temos algum elemento que é igual a a primeira matriz ou os primeiros índices. 1618 01:09:00,979 --> 01:09:03,200 Montamos j igual a isso. 1619 01:09:03,200 --> 01:09:04,649 1620 01:09:04,649 --> 01:09:09,210 Assim, enquanto j é maior do que zero e a matriz, j menos 1 1621 01:09:09,210 --> 01:09:11,660 é maior do que o elemento, por isso tudo o que está fazendo 1622 01:09:11,660 --> 01:09:17,479 é ter certeza de que seu j representa realmente 1623 01:09:17,479 --> 01:09:20,010 a porção não triados da matriz. 1624 01:09:20,010 --> 01:09:30,745 >> Assim, enquanto ainda há coisas para classificar e j menos um é-- que 1625 01:09:30,745 --> 01:09:31,840 é o elemento a ela? 1626 01:09:31,840 --> 01:09:34,760 J nunca foi definido aqui. 1627 01:09:34,760 --> 01:09:35,677 É uma espécie de irritante. 1628 01:09:35,677 --> 01:09:36,176 Está bem. 1629 01:09:36,176 --> 01:09:36,689 De qualquer forma. 1630 01:09:36,689 --> 01:09:39,899 Então j menos 1, você está verificando o elemento antes. 1631 01:09:39,899 --> 01:09:46,460 Você está dizendo, OK, é o elemento antes de onde quer que eu am-- vamos 1632 01:09:46,460 --> 01:09:47,540 realmente tirar isso. 1633 01:09:47,540 --> 01:09:52,580 1634 01:09:52,580 --> 01:09:56,830 Então, digamos que este é como na nossa segunda passagem. 1635 01:09:56,830 --> 01:09:59,525 Então eu vai ser igual para 1, que é aqui. 1636 01:09:59,525 --> 01:10:03,310 1637 01:10:03,310 --> 01:10:06,025 >> Então i vai ser igual a 1. 1638 01:10:06,025 --> 01:10:09,510 1639 01:10:09,510 --> 01:10:13,702 Isto seria de 2, 4, 5, 6, 7. 1640 01:10:13,702 --> 01:10:16,060 1641 01:10:16,060 --> 01:10:16,750 Tudo certo. 1642 01:10:16,750 --> 01:10:20,945 Assim, o nosso elemento, neste caso, vai ser igual a 4. 1643 01:10:20,945 --> 01:10:22,110 1644 01:10:22,110 --> 01:10:24,946 E nós temos alguns j que é vai ser igual a 1. 1645 01:10:24,946 --> 01:10:29,770 1646 01:10:29,770 --> 01:10:30,971 Oh, j está diminuindo. 1647 01:10:30,971 --> 01:10:31,720 Isso é o que é. 1648 01:10:31,720 --> 01:10:35,680 Então, j é igual a i, então o que é isso dizendo é que à medida que avançamos, 1649 01:10:35,680 --> 01:10:37,530 estamos apenas certificando-se que não estamos mais 1650 01:10:37,530 --> 01:10:43,520 indexação dessa maneira quando estamos tentando para inserir as coisas em nossa lista classificada. 1651 01:10:43,520 --> 01:10:49,850 >> Portanto, quando j é igual a 1 e, neste caso matriz j menos um-- tão matriz j menos 1 1652 01:10:49,850 --> 01:10:54,610 é 2 neste case-- se é isso maior do que o elemento, 1653 01:10:54,610 --> 01:10:57,700 então tudo isso está fazendo está mudando as coisas. 1654 01:10:57,700 --> 01:11:04,790 Portanto, neste caso, uma matriz j menos Seria matriz de zero, o que é 2. 1655 01:11:04,790 --> 01:11:08,430 2 não é maior do que 4, de modo que este não é executado. 1656 01:11:08,430 --> 01:11:11,460 Assim, a mudança não se move para baixo. 1657 01:11:11,460 --> 01:11:18,790 O que isto faz aqui é apenas movendo o array ordenado baixo. 1658 01:11:18,790 --> 01:11:22,340 1659 01:11:22,340 --> 01:11:26,400 Neste caso, na verdade, nós poderia fazer-- vamos fazer isso três. 1660 01:11:26,400 --> 01:11:28,080 1661 01:11:28,080 --> 01:11:31,970 Então, se estamos a caminhar através de Neste exemplo, agora estamos aqui. 1662 01:11:31,970 --> 01:11:32,740 Esta é classificada. 1663 01:11:32,740 --> 01:11:34,492 1664 01:11:34,492 --> 01:11:35,200 Este é indiferenciado. 1665 01:11:35,200 --> 01:11:39,090 1666 01:11:39,090 --> 01:11:39,860 Legal? 1667 01:11:39,860 --> 01:11:46,620 Então, i é igual a 2, assim nosso elemento é igual a 3. 1668 01:11:46,620 --> 01:11:47,920 1669 01:11:47,920 --> 01:11:52,270 E o nosso j é igual a 2. 1670 01:11:52,270 --> 01:12:00,620 Então olhamos através e nós dizer, OK, é matriz j menos um 1671 01:12:00,620 --> 01:12:03,470 maior do que o elemento que nós estamos olhando? 1672 01:12:03,470 --> 01:12:05,540 E a resposta é sim, certo? 1673 01:12:05,540 --> 01:12:11,275 4 é maior do que 3 e j é 2, portanto, esse código é executado. 1674 01:12:11,275 --> 01:12:12,510 1675 01:12:12,510 --> 01:12:18,550 >> Então, agora o que nós fazemos uma série de 2, por isso aqui, nós trocá-los. 1676 01:12:18,550 --> 01:12:25,620 Então, nós apenas dizer, OK, array em 2 agora vai ser 3. 1677 01:12:25,620 --> 01:12:28,130 1678 01:12:28,130 --> 01:12:32,340 E j vai ser igual j menos 1, que é 1. 1679 01:12:32,340 --> 01:12:34,590 1680 01:12:34,590 --> 01:12:37,200 Isso é horrível, mas vocês a idéia. 1681 01:12:37,200 --> 01:12:38,360 J é agora igual a 1. 1682 01:12:38,360 --> 01:12:44,360 E matriz j é apenas vai ser igual ao nosso elemento, que foi de 4. 1683 01:12:44,360 --> 01:12:45,950 1684 01:12:45,950 --> 01:12:48,570 Eu apaguei algo que não devia tem ou algo miswrote, 1685 01:12:48,570 --> 01:12:49,910 mas vocês começa a idéia. 1686 01:12:49,910 --> 01:12:50,640 >> É mover-se em n. 1687 01:12:50,640 --> 01:12:51,920 1688 01:12:51,920 --> 01:12:57,960 E então, se isso fosse, seria laço novamente e ele dizia: OK, j é um agora. 1689 01:12:57,960 --> 01:13:00,665 E matriz j menos 1 é agora 2. 1690 01:13:00,665 --> 01:13:01,750 1691 01:13:01,750 --> 01:13:03,760 É de 2 a menos de nosso elemento? 1692 01:13:03,760 --> 01:13:04,540 Não? 1693 01:13:04,540 --> 01:13:07,970 Isso significa que nós temos este elemento inserido 1694 01:13:07,970 --> 01:13:10,110 no ponto correto em nossa matriz classificada. 1695 01:13:10,110 --> 01:13:14,400 Então nós podemos levar isso e dizemos: OK, a nossa matriz classificada está aqui. 1696 01:13:14,400 --> 01:13:19,940 E levaria esse número 6 e ser como, OK, é de 6 inferior a esse número? 1697 01:13:19,940 --> 01:13:20,480 Não? 1698 01:13:20,480 --> 01:13:21,080 Legal. 1699 01:13:21,080 --> 01:13:22,680 Nós estamos bem. 1700 01:13:22,680 --> 01:13:23,530 >> Fazê-lo novamente. 1701 01:13:23,530 --> 01:13:24,740 Dizemos 7. 1702 01:13:24,740 --> 01:13:29,010 É menos do que 7 o final da nossa matriz classificada? 1703 01:13:29,010 --> 01:13:29,520 Não. 1704 01:13:29,520 --> 01:13:30,430 Então, nós estamos bem. 1705 01:13:30,430 --> 01:13:32,760 Então, isso seria resolvido. 1706 01:13:32,760 --> 01:13:38,610 Basicamente tudo isso faz se ele está dizendo take 1707 01:13:38,610 --> 01:13:42,060 o primeiro elemento sua matriz não classificado, 1708 01:13:42,060 --> 01:13:46,010 descobrir para onde vai em sua matriz de classificação. 1709 01:13:46,010 --> 01:13:48,780 E isso só se encarrega de swaps de fazer isso. 1710 01:13:48,780 --> 01:13:51,300 Você está basicamente apenas trocando até que esteja no ponto certo. 1711 01:13:51,300 --> 01:13:53,600 1712 01:13:53,600 --> 01:13:56,990 A imagem visual é que você é movendo tudo para baixo, fazendo isso. 1713 01:13:56,990 --> 01:13:59,420 >> Então, é como metade bubble sort-esque. 1714 01:13:59,420 --> 01:14:02,280 1715 01:14:02,280 --> 01:14:03,420 Confira estudo 50. 1716 01:14:03,420 --> 01:14:06,000 Eu recomendo tentar codificar isso em seu próprio país. 1717 01:14:06,000 --> 01:14:07,220 1718 01:14:07,220 --> 01:14:12,450 Se você tiver quaisquer problemas ou se você quiser ver código de exemplo para um tipo de inserção, 1719 01:14:12,450 --> 01:14:13,750 por favor, me avise. 1720 01:14:13,750 --> 01:14:14,500 Estou sempre por perto. 1721 01:14:14,500 --> 01:14:16,600 1722 01:14:16,600 --> 01:14:20,200 Então, o pior caso de tempo de execução e melhor caso de execução. 1723 01:14:20,200 --> 01:14:30,700 Como você viu cara da mesa eu já mostrei, é tanto n ao quadrado e n. 1724 01:14:30,700 --> 01:14:35,590 >> Assim, tipo de ir fora do que nós falamos sobre com os nossos tipos anteriores, pior 1725 01:14:35,590 --> 01:14:38,760 caso de tempo de execução é que, se é completamente não separados, 1726 01:14:38,760 --> 01:14:42,530 temos que comparar todos esses n vezes. 1727 01:14:42,530 --> 01:14:47,020 Nós fazemos um monte de comparações porque se está em ordem inversa, 1728 01:14:47,020 --> 01:14:50,360 vamos dizer, OK, este é a mesma, isto é boa, 1729 01:14:50,360 --> 01:14:54,650 e este terá que ser comparados contra o primeiro a ser movido para trás. 1730 01:14:54,650 --> 01:14:56,710 E à medida que direção o fim da cauda, ​​temos 1731 01:14:56,710 --> 01:14:59,440 comparar, comparar e comparar contra tudo. 1732 01:14:59,440 --> 01:15:03,030 >> Então, ele acaba sendo cerca de n ao quadrado. 1733 01:15:03,030 --> 01:15:09,510 Se é correto, então você dizer, OK, 2, você é bom. 1734 01:15:09,510 --> 01:15:11,330 3, você está em relação a dois. 1735 01:15:11,330 --> 01:15:12,310 Você é bom. 1736 01:15:12,310 --> 01:15:14,150 4, basta comparar com a cauda. 1737 01:15:14,150 --> 01:15:14,990 Você é bom. 1738 01:15:14,990 --> 01:15:17,140 6, comparar com a cauda, ​​você está bem. 1739 01:15:17,140 --> 01:15:20,870 Assim, para cada ponto, se ele já está classificadas, você está fazendo uma comparação. 1740 01:15:20,870 --> 01:15:22,320 Então é só n. 1741 01:15:22,320 --> 01:15:26,840 E porque nós temos um melhor caso de execução de n e um caso pior tempo de execução de n 1742 01:15:26,840 --> 01:15:28,680 quadrado, não temos tempo de execução esperado. 1743 01:15:28,680 --> 01:15:31,290 1744 01:15:31,290 --> 01:15:34,020 >> Ela só depende do caos da nossa lista lá. 1745 01:15:34,020 --> 01:15:35,860 1746 01:15:35,860 --> 01:15:39,530 E, novamente, outra gráfico e outra tabela. 1747 01:15:39,530 --> 01:15:41,170 Assim, as diferenças entre os tipos. 1748 01:15:41,170 --> 01:15:44,180 Eu estou indo só para brisa através, eu sentir como nós falamos extensivamente 1749 01:15:44,180 --> 01:15:46,570 sobre como eles todo o tipo de variar e link juntos. 1750 01:15:46,570 --> 01:15:50,564 Então, merge sort é o último Vou te aborrecer com caras. 1751 01:15:50,564 --> 01:15:52,105 Nós temos um quadro bastante colorido. 1752 01:15:52,105 --> 01:15:53,860 1753 01:15:53,860 --> 01:15:56,040 Então, merge sort é um algoritmo recursivo. 1754 01:15:56,040 --> 01:15:59,910 Então, vocês sabem o que uma função recursiva é? 1755 01:15:59,910 --> 01:16:01,550 1756 01:16:01,550 --> 01:16:03,320 >> Alguém quer dizer? 1757 01:16:03,320 --> 01:16:04,739 Você quer tentar? 1758 01:16:04,739 --> 01:16:07,280 Assim, uma função recursiva é apenas uma função que chama a si mesmo. 1759 01:16:07,280 --> 01:16:08,570 1760 01:16:08,570 --> 01:16:11,590 Então, se vocês estão familiarizados com a seqüência de Fibonacci, 1761 01:16:11,590 --> 01:16:15,670 que é considerado recursivo porque você levar os dois anteriores 1762 01:16:15,670 --> 01:16:17,530 e adicioná-los juntos para obter o seu próximo. 1763 01:16:17,530 --> 01:16:21,440 Então recursiva, eu sempre penso de recursividade como como uma espiral 1764 01:16:21,440 --> 01:16:24,430 então você é como a espiral para baixo para ele. 1765 01:16:24,430 --> 01:16:27,150 Mas é apenas uma função que chama a si mesmo. 1766 01:16:27,150 --> 01:16:32,660 >> E, na verdade, muito rapidamente eu pode mostrar-lhe o que parece. 1767 01:16:32,660 --> 01:16:34,260 1768 01:16:34,260 --> 01:16:41,840 Então recursiva aqui, se olharmos, este é a forma recursiva para resumir em uma matriz. 1769 01:16:41,840 --> 01:16:45,900 1770 01:16:45,900 --> 01:16:47,880 Então, tudo o que fazemos é temos a função soma 1771 01:16:47,880 --> 01:16:52,210 soma que leva um tamanho e uma matriz. 1772 01:16:52,210 --> 01:16:55,210 E se você observar, o tamanho decréscimos de um em um. 1773 01:16:55,210 --> 01:17:00,365 E tudo que ele faz é se x é igual a zero-- isso, se o tamanho da matriz 1774 01:17:00,365 --> 01:17:02,710 é igual a zero-- ele retorna a zero. 1775 01:17:02,710 --> 01:17:10,440 >> Caso contrário, ele resume este último elemento da matriz, 1776 01:17:10,440 --> 01:17:14,790 e, em seguida, leva uma soma de o resto da matriz. 1777 01:17:14,790 --> 01:17:17,555 Então, é só quebrá-lo para baixo em problemas cada vez menores. 1778 01:17:17,555 --> 01:17:18,990 1779 01:17:18,990 --> 01:17:21,890 Longa história curta, recursão, função que chama a si mesmo. 1780 01:17:21,890 --> 01:17:25,740 Se isso é tudo que você tem fora deste, isso é o que uma função recursiva é. 1781 01:17:25,740 --> 01:17:29,870 Se você tomar 51, você vai ficar muito, muito confortável com recursividade. 1782 01:17:29,870 --> 01:17:31,110 1783 01:17:31,110 --> 01:17:32,370 É muito legal. 1784 01:17:32,370 --> 01:17:34,660 Fazia sentido em como 03:00 uma noite fora. 1785 01:17:34,660 --> 01:17:37,900 E eu era como, por que eu nunca uso isso? 1786 01:17:37,900 --> 01:17:39,170 1787 01:17:39,170 --> 01:17:42,430 >> Assim, para merge sort, basicamente o que ele vai fazer é que é 1788 01:17:42,430 --> 01:17:45,620 vai quebrá-lo e quebrá-lo para baixo até que ele é apenas elementos individuais. 1789 01:17:45,620 --> 01:17:47,570 Os elementos individuais são fáceis de classificar. 1790 01:17:47,570 --> 01:17:48,070 Vemos isso. 1791 01:17:48,070 --> 01:17:50,760 Se você tem um elemento, é já considerada classificada. 1792 01:17:50,760 --> 01:17:53,800 Então, em uma entrada de n elementos, se n é inferior a 2, 1793 01:17:53,800 --> 01:17:58,120 basta retornar porque isso significa é 0 ou 1, como vimos. 1794 01:17:58,120 --> 01:18:00,050 Aqueles são considerados elementos ordenados. 1795 01:18:00,050 --> 01:18:02,170 >> Caso contrário, quebrá-lo ao meio. 1796 01:18:02,170 --> 01:18:06,336 Classificar a primeira metade, classificar o segundo metade, em seguida, fundi-las. 1797 01:18:06,336 --> 01:18:07,460 Por que ele é chamado merge sort. 1798 01:18:07,460 --> 01:18:08,700 1799 01:18:08,700 --> 01:18:12,155 Portanto, temos aqui nós vamos resolver estes. 1800 01:18:12,155 --> 01:18:13,410 1801 01:18:13,410 --> 01:18:17,210 Assim, mantemos tê-los até que o tamanho da matriz é 1. 1802 01:18:17,210 --> 01:18:20,790 Então, quando ele é um, nós apenas voltar porque este é um array ordenado, 1803 01:18:20,790 --> 01:18:23,940 e este é um array ordenado, e isso é um array ordenado, todos nós estamos classificadas. 1804 01:18:23,940 --> 01:18:25,390 1805 01:18:25,390 --> 01:18:29,420 Então, o que fazemos é começar a fundir-los juntos. 1806 01:18:29,420 --> 01:18:31,820 >> Assim, a maneira que puder pensar em fusão é 1807 01:18:31,820 --> 01:18:36,240 você acabou de remover a menor número de cada uma das sub-matrizes 1808 01:18:36,240 --> 01:18:38,330 e apenas anexá-lo para a matriz emergiu. 1809 01:18:38,330 --> 01:18:44,290 Então, se você olhar aqui, quando temos esses conjuntos temos 4, 6 e 1. 1810 01:18:44,290 --> 01:18:47,280 Quando queremos mesclar estes, olharmos para estes dois primeiros 1811 01:18:47,280 --> 01:18:50,730 e dizemos: OK, um é menor, ele vai para a frente. 1812 01:18:50,730 --> 01:18:54,330 4 e 6, não há nada para comparar que ele, só marcá-lo até o fim. 1813 01:18:54,330 --> 01:18:58,020 >> Quando combinamos esses dois, nós apenas levar a uma menor destes dois, 1814 01:18:58,020 --> 01:18:59,310 por isso é um. 1815 01:18:59,310 --> 01:19:01,690 E agora nós tomamos a menor destes dois, então 2. 1816 01:19:01,690 --> 01:19:03,330 Menor destes dois, três. 1817 01:19:03,330 --> 01:19:06,260 Menor destes dois, 4, 5, 6. 1818 01:19:06,260 --> 01:19:08,630 Então, você está apenas tirando estes. 1819 01:19:08,630 --> 01:19:11,210 E porque eles têm foram classificadas anteriormente, 1820 01:19:11,210 --> 01:19:14,300 você só tem uma Comparação de cada vez que há. 1821 01:19:14,300 --> 01:19:19,610 Então, mais código aqui, apenas representação. 1822 01:19:19,610 --> 01:19:24,410 Então você começa no meio e você classificar esquerda e à direita 1823 01:19:24,410 --> 01:19:26,180 e então você só mesclar aqueles. 1824 01:19:26,180 --> 01:19:30,080 >> E não temos código para fundir aqui. 1825 01:19:30,080 --> 01:19:34,110 Mas, novamente, se você vai em estudar 50, ele vai estar lá. 1826 01:19:34,110 --> 01:19:36,860 Caso contrário, vir falar comigo Se você ainda está confuso. 1827 01:19:36,860 --> 01:19:42,340 Então coisa legal aqui é que melhor caso, pior caso, e tempo de execução esperado 1828 01:19:42,340 --> 01:19:46,250 são todos no registo n, que é muito melhor do que nós temos 1829 01:19:46,250 --> 01:19:48,000 visto para o resto de nossas sortes. 1830 01:19:48,000 --> 01:19:51,840 Vimos n ao quadrado eo que realmente 1831 01:19:51,840 --> 01:19:54,380 chegar aqui é n log n, o que é ótimo. 1832 01:19:54,380 --> 01:19:55,830 >> Olha como muito melhor que é. 1833 01:19:55,830 --> 01:19:56,780 Tal curva agradável. 1834 01:19:56,780 --> 01:19:58,130 1835 01:19:58,130 --> 01:20:00,120 Portanto, muito mais eficiente. 1836 01:20:00,120 --> 01:20:03,510 Se você já se puder, uso merge sort. 1837 01:20:03,510 --> 01:20:04,810 Ela vai lhe poupar tempo. 1838 01:20:04,810 --> 01:20:07,670 Então, novamente, como dissemos, se você está para baixo nesta região mais baixa, 1839 01:20:07,670 --> 01:20:09,480 não que fazer muita diferença. 1840 01:20:09,480 --> 01:20:11,360 Você se levanta para milhares e milhares de entradas, 1841 01:20:11,360 --> 01:20:13,318 você definitivamente quer um algoritmo mais eficiente. 1842 01:20:13,318 --> 01:20:14,730 1843 01:20:14,730 --> 01:20:19,400 E, mais uma vez, a nossa mesa linda de todas tipos que vocês aprenderam hoje. 1844 01:20:19,400 --> 01:20:21,157 >> Então, eu sei que tem sido um dia denso. 1845 01:20:21,157 --> 01:20:23,490 Isso não vai necessariamente para ajudá-lo com seu pset. 1846 01:20:23,490 --> 01:20:28,250 Mas eu só quero fazer um disclaimer essa seção não é apenas sobre Série de Exercícios. 1847 01:20:28,250 --> 01:20:31,240 Todo esse material é justo jogo para seus exames semestrais. 1848 01:20:31,240 --> 01:20:35,430 E também se você continuar com CS, estes são os fundamentos realmente importantes 1849 01:20:35,430 --> 01:20:37,870 que você precisa saber. 1850 01:20:37,870 --> 01:20:41,700 Assim, alguns dias serão um pouco mais pset ajuda, 1851 01:20:41,700 --> 01:20:44,600 mas algumas semanas será teor muito mais efectiva 1852 01:20:44,600 --> 01:20:46,600 que pode não parecer super útil para você agora, 1853 01:20:46,600 --> 01:20:51,215 mas eu prometo que se você continuar no vai ser muito, muito útil. 1854 01:20:51,215 --> 01:20:52,560 1855 01:20:52,560 --> 01:20:54,250 >> Então é isso por seção. 1856 01:20:54,250 --> 01:20:55,250 Down to the wire. 1857 01:20:55,250 --> 01:20:56,570 Eu fiz isso em um minuto. 1858 01:20:56,570 --> 01:20:58,262 1859 01:20:58,262 --> 01:20:58,970 Mas lá vai. 1860 01:20:58,970 --> 01:21:01,240 E eu vou ter donuts ou doces. 1861 01:21:01,240 --> 01:21:03,464 Tem alguém alérgico a nada, pelo caminho? 1862 01:21:03,464 --> 01:21:05,307 1863 01:21:05,307 --> 01:21:05,890 Ovos e leite. 1864 01:21:05,890 --> 01:21:08,120 Então, donuts são um não? 1865 01:21:08,120 --> 01:21:09,400 1866 01:21:09,400 --> 01:21:10,160 Está bem. 1867 01:21:10,160 --> 01:21:10,770 Tudo certo. 1868 01:21:10,770 --> 01:21:12,120 Sem chocolate? 1869 01:21:12,120 --> 01:21:12,620 Starburst. 1870 01:21:12,620 --> 01:21:13,837 1871 01:21:13,837 --> 01:21:14,670 Starbursts são boas. 1872 01:21:14,670 --> 01:21:15,170 Está bem. 1873 01:21:15,170 --> 01:21:17,045 Nós vamos ter Starburst próxima semana seguida. 1874 01:21:17,045 --> 01:21:18,240 Isso é o que eu vou chegar. 1875 01:21:18,240 --> 01:21:19,690 Vocês têm uma ótima semana. 1876 01:21:19,690 --> 01:21:20,460 Leia o seu spec. 1877 01:21:20,460 --> 01:21:22,130 >> Deixe-me saber se você tiver quaisquer perguntas. 1878 01:21:22,130 --> 01:21:25,300 PSet duas classes devem ser para você até quinta-feira. 1879 01:21:25,300 --> 01:21:28,320 Se você tiver alguma dúvida sobre como eu graduada algo 1880 01:21:28,320 --> 01:21:32,250 ou porque eu graduada algo do jeito que eu fez, por favor me escreva, venha falar comigo. 1881 01:21:32,250 --> 01:21:34,210 Estou um pouco esse louco semana, mas prometo 1882 01:21:34,210 --> 01:21:36,340 Eu ainda vou responder no prazo de 24 horas. 1883 01:21:36,340 --> 01:21:38,240 Então, tem uma ótima semana a todos. 1884 01:21:38,240 --> 01:21:40,090 Boa sorte em sua pset. 1885 01:21:40,090 --> 01:21:41,248