1 00:00:00,000 --> 00:00:03,332 >> [Música tocando] 2 00:00:03,332 --> 00:00:06,490 >> ANDI Peng: Bem-vindo à semana 3 da secção. 3 00:00:06,490 --> 00:00:09,550 Obrigado, rapazes, para tudo que vem a esta hora de início mais cedo hoje. 4 00:00:09,550 --> 00:00:11,466 Temos uma nice, pouco grupo íntimo hoje. 5 00:00:11,466 --> 00:00:14,570 Portanto, esperamos que nós vamos chegar a acabamento, talvez, cedo, 6 00:00:14,570 --> 00:00:15,780 um pouco mais cedo hoje. 7 00:00:15,780 --> 00:00:22,057 Então, rapidamente, apenas alguns anúncios para a agenda de hoje. 8 00:00:22,057 --> 00:00:23,890 Antes de começar, estamos indo para ir um pouco mais 9 00:00:23,890 --> 00:00:28,910 algumas breves questões logísticas, pset perguntas, interrogue, coisas assim. 10 00:00:28,910 --> 00:00:30,250 E então nós vamos mergulhar na direita. 11 00:00:30,250 --> 00:00:34,710 Vamos usar um depurador chamado GDB começar a desbancar o nosso código, que David 12 00:00:34,710 --> 00:00:36,550 explicou em conferência no outro dia. 13 00:00:36,550 --> 00:00:39,420 Nós falaremos sobre os quatro tipos de tipos. 14 00:00:39,420 --> 00:00:42,310 Nós vamos passar por cima deles muito rapidamente uma vez que eles são muito intensivos. 15 00:00:42,310 --> 00:00:45,710 Mas sei que todos os slides e código-fonte estão sempre online. 16 00:00:45,710 --> 00:00:50,810 Então, sinta-se livre, na sua leitura, a voltar e dar uma olhada nisso. 17 00:00:50,810 --> 00:00:53,930 >> Nós vamos passar por notação assintótica, que 18 00:00:53,930 --> 00:00:55,944 é apenas uma maneira elegante de dizer "tempos de execução", 19 00:00:55,944 --> 00:00:58,360 onde temos a grande O, que David explicou em conferência. 20 00:00:58,360 --> 00:01:01,550 E também temos Omega, que é o tempo de execução limite inferior. 21 00:01:01,550 --> 00:01:06,450 E vamos falar um pouco mais em profundidade a respeito de como os trabalhos. 22 00:01:06,450 --> 00:01:10,160 E, finalmente, nós vamos passar por cima de busca binária, porque muitos de vocês que já têm 23 00:01:10,160 --> 00:01:15,190 olhou para seus Série de Exercícios provavelmente sabe que que é uma questão que está em seu pset. 24 00:01:15,190 --> 00:01:17,470 Então você vai ser feliz todos que nós cobrimos isso hoje. 25 00:01:17,470 --> 00:01:20,610 >> E, por último, por sua o feedback seção, eu realmente 26 00:01:20,610 --> 00:01:23,000 deixou cerca de 15 minutos a o fim de ir um pouco mais 27 00:01:23,000 --> 00:01:27,730 logística de pset3, dúvidas, talvez um pouco de orientação, se quiser, 28 00:01:27,730 --> 00:01:28,990 antes de iniciar a programação. 29 00:01:28,990 --> 00:01:30,890 Então, vamos tentar passar o material muito rapidamente. 30 00:01:30,890 --> 00:01:33,880 E então podemos passar algum tempo tendo mais perguntas para o pset. 31 00:01:33,880 --> 00:01:35,230 ESTÁ BEM. 32 00:01:35,230 --> 00:01:39,570 >> Rapidamente, assim que apenas alguns anúncios antes de começarmos hoje. 33 00:01:39,570 --> 00:01:45,410 Em primeiro lugar, bem-vindo a fazer -lo através de dois dos seus Série de Exercícios. 34 00:01:45,410 --> 00:01:49,432 Eu dei uma olhada no your-- Sim, vamos obter uma salva de palmas para que um. 35 00:01:49,432 --> 00:01:51,140 Na verdade, eu estava realmente, realmente impressionado. 36 00:01:51,140 --> 00:01:55,800 I classificado o primeiro pset para vocês na semana passada e que vocês fizeram incrível. 37 00:01:55,800 --> 00:01:58,290 >> Estilo estava no ponto além de alguns comentários. 38 00:01:58,290 --> 00:02:00,660 Certifique-se de que você está sempre comentando seu código. 39 00:02:00,660 --> 00:02:03,040 Mas seus Série de Exercícios foram no ponto. 40 00:02:03,040 --> 00:02:05,549 E mantê-lo. 41 00:02:05,549 --> 00:02:08,090 E é bom para o aluno a ver que vocês estão colocando 42 00:02:08,090 --> 00:02:10,704 em tanto esforço em seu estilo e seu projeto em seu código 43 00:02:10,704 --> 00:02:12,120 que gostaríamos para você ver. 44 00:02:12,120 --> 00:02:16,450 Então, eu estou passando ao longo de minha gratidão para o resto dos TAs. 45 00:02:16,450 --> 00:02:19,210 >> No entanto, há um algumas perguntas Debrief 46 00:02:19,210 --> 00:02:22,010 Eu só quero passar por cima desse faria tanto a minha vida 47 00:02:22,010 --> 00:02:24,900 e um monte de outro TAs "vive um pouco mais fácil. 48 00:02:24,900 --> 00:02:28,220 Em primeiro lugar, eu tenho notado isso passado week-- quantos de vocês 49 00:02:28,220 --> 00:02:32,301 já estão a funcionar em check50 seu código antes de enviar? 50 00:02:32,301 --> 00:02:32,800 ESTÁ BEM. 51 00:02:32,800 --> 00:02:36,690 Então, todos devem estar fazendo check50, porque-- um secret-- nós realmente 52 00:02:36,690 --> 00:02:41,540 executar check50 como parte de nossa correção scripts para testar o seu código. 53 00:02:41,540 --> 00:02:45,480 Portanto, se seu código está falhando check50, com toda a probabilidade, 54 00:02:45,480 --> 00:02:47,570 ele provavelmente vai falhar nosso check também. 55 00:02:47,570 --> 00:02:49,320 Às vezes, vocês ter as respostas certas. 56 00:02:49,320 --> 00:02:52,200 Como, em gananciosos, alguns dos você tem os números certos, 57 00:02:52,200 --> 00:02:53,960 você só imprimir algum material extra. 58 00:02:53,960 --> 00:02:55,940 E esse material extra realmente falhar a verificação, 59 00:02:55,940 --> 00:02:58,440 porque o computador não faz realmente sabe o que ele está procurando. 60 00:02:58,440 --> 00:03:00,981 E assim ela só vai percorrer, ver que sua saída não 61 00:03:00,981 --> 00:03:03,810 corresponder ao que esperamos que a resposta para ser, e marcá-lo é errado. 62 00:03:03,810 --> 00:03:06,560 >> E eu sei que aconteceu em alguns de seus casos esta semana. 63 00:03:06,560 --> 00:03:09,870 Então, eu fui para trás e manualmente Reclassificados código de todos. 64 00:03:09,870 --> 00:03:12,780 No futuro, porém, por favor, por favor, certifique- 65 00:03:12,780 --> 00:03:14,570 que você está executando verificar 50 em seu código. 66 00:03:14,570 --> 00:03:17,970 Porque é um tipo de dor para o TA ter que voltar e manualmente regrade 67 00:03:17,970 --> 00:03:21,197 cada pset único para cada instância única, pouco perdida. 68 00:03:21,197 --> 00:03:22,530 Então eu não tirar quaisquer pontos. 69 00:03:22,530 --> 00:03:25,210 Acho que eu tirei talvez um ou dois para o projeto. 70 00:03:25,210 --> 00:03:27,710 No futuro, embora, se você está falhando check50, 71 00:03:27,710 --> 00:03:31,330 Os pontos serão tomadas off para correção. 72 00:03:31,330 --> 00:03:35,020 >> Além disso, são Série de Exercícios devido sextas-feiras ao meio-dia. 73 00:03:35,020 --> 00:03:38,990 Eu acho que há uma de sete minutos período de carência tarde que nós lhe damos. 74 00:03:38,990 --> 00:03:42,434 Por tempo de Harvard, eles estão autorizados a ser de sete minutos de atraso para tudo. 75 00:03:42,434 --> 00:03:44,350 Então, aqui em Yale, vamos aderir a isso também. 76 00:03:44,350 --> 00:03:47,910 Mas praticamente, às 12:07, se o seu não está na pset, 77 00:03:47,910 --> 00:03:49,720 ele vai ser marcado como final. 78 00:03:49,720 --> 00:03:53,160 E assim, enquanto ele é marcado tão tarde, o TA-- eu sou 79 00:03:53,160 --> 00:03:54,870 ainda vai ser grading seus Série de Exercícios. 80 00:03:54,870 --> 00:03:56,760 Então, você ainda verá um grau aparecer. 81 00:03:56,760 --> 00:03:58,820 No entanto, sabemos que a o final do semestre, 82 00:03:58,820 --> 00:04:02,270 todas Série de Exercícios final será apenas zerada automaticamente pelo computador. 83 00:04:02,270 --> 00:04:04,490 >> Fazemos isso por duas razões. 84 00:04:04,490 --> 00:04:09,220 Um deles, às vezes ficamos desculpado, como desculpas de Dean, 85 00:04:09,220 --> 00:04:10,762 mais tarde que eu não sei sobre isso ainda. 86 00:04:10,762 --> 00:04:13,761 Por isso, gostaria de ter certeza que estamos classificação tudo apenas no caso, como, eu sou 87 00:04:13,761 --> 00:04:15,080 faltando a desculpa de um reitor. 88 00:04:15,080 --> 00:04:17,000 E em segundo lugar, lembre- mente, você ainda pode 89 00:04:17,000 --> 00:04:19,370 soltar um pset que tem pontos de escopo completo. 90 00:04:19,370 --> 00:04:21,430 E assim nós gostamos de grau todos os seus Série de Exercícios apenas 91 00:04:21,430 --> 00:04:24,730 para se certificar de que o seu âmbito de lá e você está tentando eles. 92 00:04:24,730 --> 00:04:29,150 Assim, mesmo se é tarde, você ainda obter crédito para pontos de escopo, eu acho. 93 00:04:29,150 --> 00:04:33,730 >> Então moral da história é, torná- se de seus Série de Exercícios estão em dentro do prazo. 94 00:04:33,730 --> 00:04:38,350 E se eles não estão em on-tempo, sei que não é grande. 95 00:04:38,350 --> 00:04:41,678 Sim, antes de eu seguir em frente, alguém tem qualquer dúvida sobre o feedback pset? 96 00:04:41,678 --> 00:04:42,178 Sim. 97 00:04:42,178 --> 00:04:43,630 >> AUDIÊNCIA: Você disse que pode soltar uma das Série de Exercícios? 98 00:04:43,630 --> 00:04:44,296 >> ANDI Peng: Sim. 99 00:04:44,296 --> 00:04:47,050 Portanto, há nove Série de Exercícios geral ao longo do semestre. 100 00:04:47,050 --> 00:04:50,610 E se você tem escopo points-- tão escopo é justo, 101 00:04:50,610 --> 00:04:53,567 muito bonito, que você está tentando a problema, você está colocando no tempo, 102 00:04:53,567 --> 00:04:56,150 você está mostrando que você tem demonstrada você leu o spec. 103 00:04:56,150 --> 00:04:57,191 Isso é muito bonito escopo. 104 00:04:57,191 --> 00:04:59,370 E se você está cumprindo Os pontos de escopo, nós 105 00:04:59,370 --> 00:05:03,360 pode soltar o menor um fora de alcance global. 106 00:05:03,360 --> 00:05:06,790 Então essa é a sua vantagem para preencher e tentar todos os pset. 107 00:05:06,790 --> 00:05:10,320 >> Mesmo se nenhum dos upload-- -los trabalhar, fazer upload de todos eles. 108 00:05:10,320 --> 00:05:13,711 E então nós esperamos ser capazes de dar-lhe alguns desses pontos de volta. 109 00:05:13,711 --> 00:05:14,210 Legal. 110 00:05:14,210 --> 00:05:16,780 Alguma outra pergunta? 111 00:05:16,780 --> 00:05:17,840 Ótimo. 112 00:05:17,840 --> 00:05:21,960 >> Em segundo lugar, escritório horas-- alguns notas rápidas sobre o horário de expediente. 113 00:05:21,960 --> 00:05:24,300 Então, primeiro, entrar no início da semana. 114 00:05:24,300 --> 00:05:26,909 Ninguém está sempre em o horário de expediente às segundas-feiras. 115 00:05:26,909 --> 00:05:28,700 Christabel veio a o horário de expediente na noite passada. 116 00:05:28,700 --> 00:05:29,691 Sim, Christabel. 117 00:05:29,691 --> 00:05:32,190 E o que temos no escritório horas na noite passada, Christabel? 118 00:05:32,190 --> 00:05:33,020 >> AUDIÊNCIA: Nós tivemos sorvete. 119 00:05:33,020 --> 00:05:36,160 >> ANDI Peng: Então, isso é certo, tivemos sorvete no horário de expediente na noite passada. 120 00:05:36,160 --> 00:05:39,390 Enquanto eu não posso prometer-lhe que teremos sorvete no horário de expediente 121 00:05:39,390 --> 00:05:43,230 a cada semana, o que posso prometer-lhe é que haverá um aumento significativamente 122 00:05:43,230 --> 00:05:45,380 melhor relação de alunos por TA. 123 00:05:45,380 --> 00:05:47,650 Como legítimo, é como 3-1. 124 00:05:47,650 --> 00:05:50,350 Considerando que, contrastam com que Quinta-feira, você tem cerca de 150 125 00:05:50,350 --> 00:05:52,830 realmente estressado crianças e não sorvete. 126 00:05:52,830 --> 00:05:55,360 E não é apenas produtivo para ninguém. 127 00:05:55,360 --> 00:05:58,730 Então moral da história é, chegou cedo para as horas de expediente e coisas boas 128 00:05:58,730 --> 00:06:00,310 acontecerá. 129 00:06:00,310 --> 00:06:02,110 >> Além disso, venha preparado para fazer perguntas. 130 00:06:02,110 --> 00:06:03,200 Você sabe? 131 00:06:03,200 --> 00:06:05,420 Independentemente do que TAs, I pensam, têm vindo a dizer, 132 00:06:05,420 --> 00:06:10,710 temos recebido um par de estudantes que entram em na quinta-feira, como, 10:50 133 00:06:10,710 --> 00:06:15,100 não ter lido a especificação sendo como me ajude, me ajude. 134 00:06:15,100 --> 00:06:18,200 Infelizmente, neste ponto, não há Não muito que podemos fazer para ajudá-lo. 135 00:06:18,200 --> 00:06:19,590 Então, por favor, venha no início da semana. 136 00:06:19,590 --> 00:06:22,040 Chegue mais cedo para o horário de expediente. 137 00:06:22,040 --> 00:06:23,350 Venha preparado para fazer perguntas. 138 00:06:23,350 --> 00:06:25,310 Certifique-se de que você, como um estudante, onde são 139 00:06:25,310 --> 00:06:27,620 você precisa ser para que o TAs podem orientá-lo junto, 140 00:06:27,620 --> 00:06:32,850 que é o que o horário de expediente deve ser alocado para. 141 00:06:32,850 --> 00:06:37,380 >> Em segundo lugar, então eu sei professores gostaria de nos surpreender com os testes. 142 00:06:37,380 --> 00:06:39,439 Eu tinha um professor aqueles como, yo, a propósito, 143 00:06:39,439 --> 00:06:41,230 lembre-se que intercalar você tem próxima segunda-feira. 144 00:06:41,230 --> 00:06:42,855 Sim, eu não sei nada sobre isso intercalar. 145 00:06:42,855 --> 00:06:45,630 Então, eu estou indo ser que TA que você lembra tudo o que teste 146 00:06:45,630 --> 00:06:47,270 0-- porque, você sabe, nós somos CS. 147 00:06:47,270 --> 00:06:50,730 Agora que nós temos matrizes feito, você começa por isso que é teste 0, não quiz-1, eh? 148 00:06:50,730 --> 00:06:51,320 ESTÁ BEM. 149 00:06:51,320 --> 00:06:52,490 Oh, eu tenho algumas risadas sobre isso. 150 00:06:52,490 --> 00:06:53,120 ESTÁ BEM. 151 00:06:53,120 --> 00:06:59,710 >> Então questionário 0 será 14 de outubro se você está na seção de segunda a quarta-feira 152 00:06:59,710 --> 00:07:02,920 e 15 de Outubro, se você estiver em a seção de terça a quinta-feira. 153 00:07:02,920 --> 00:07:05,630 Isto não se aplica para aqueles de vocês em Harvard 154 00:07:05,630 --> 00:07:10,350 who-- Eu acho que você vai ser todos tendo seus testes no dia 14. 155 00:07:10,350 --> 00:07:13,560 >> Então, sim, na próxima semana, se David, em palestra, vai, 156 00:07:13,560 --> 00:07:15,747 sim, então com isso teste na próxima semana, todos vocês 157 00:07:15,747 --> 00:07:17,580 não ficará chocado porque você veio para a seção 158 00:07:17,580 --> 00:07:19,664 e você sabe que o seu 0 teste é em duas semanas. 159 00:07:19,664 --> 00:07:21,580 E teremos avaliação sessões e tudo mais. 160 00:07:21,580 --> 00:07:26,360 Assim, não se preocupa com estar com medo por isso. 161 00:07:26,360 --> 00:07:29,890 Todas as perguntas antes-- dúvidas em todas as questões logísticas relativas, 162 00:07:29,890 --> 00:07:32,591 classificação, o horário de expediente, seções? 163 00:07:32,591 --> 00:07:33,090 Sim. 164 00:07:33,090 --> 00:07:35,100 >> AUDIÊNCIA: Então o teste é vai ser durante a palestra? 165 00:07:35,100 --> 00:07:35,766 >> ANDI Peng: Sim. 166 00:07:35,766 --> 00:07:39,460 Então o quiz, eu acho, é 60 minutos atribuídos em que intervalo de tempo 167 00:07:39,460 --> 00:07:42,240 que você só vai tomar na sala de aula. 168 00:07:42,240 --> 00:07:44,810 Então você não tem que vir em em, tipo, um aleatória 19:00. 169 00:07:44,810 --> 00:07:46,140 Está tudo bom. 170 00:07:46,140 --> 00:07:47,100 Sim. 171 00:07:47,100 --> 00:07:50,060 Legal. 172 00:07:50,060 --> 00:07:50,840 >> Tudo certo. 173 00:07:50,840 --> 00:07:54,330 Então, nós estamos indo para introduzir um conceito para você 174 00:07:54,330 --> 00:08:00,760 esta semana que David já tem tipo de abordou em palestra na semana passada. 175 00:08:00,760 --> 00:08:02,010 É chamado de GDB. 176 00:08:02,010 --> 00:08:05,570 E como muitos de vocês, enquanto em o curso de escrever suas Série de Exercícios, 177 00:08:05,570 --> 00:08:09,981 ter notado um grande botão que diz "Debug" na parte superior do seu IDE? 178 00:08:09,981 --> 00:08:10,480 ESTÁ BEM. 179 00:08:10,480 --> 00:08:13,770 Então agora nós vamos realmente começar a desenterrar o mistério do que aquele botão, na verdade, 180 00:08:13,770 --> 00:08:14,270 faz. 181 00:08:14,270 --> 00:08:16,790 E eu garanto que você, é uma bonito, coisa linda. 182 00:08:16,790 --> 00:08:20,740 >> Então, até agora, eu acho houve duas coisas 183 00:08:20,740 --> 00:08:23,320 os alunos têm sido tipicamente fazendo quando depuração Série de Exercícios. 184 00:08:23,320 --> 00:08:27,635 Um deles, eles quer adicionar em printf () - por isso a cada poucas linhas, 185 00:08:27,635 --> 00:08:29,760 eles adicionar em um printf () - oh, o que é essa variável? 186 00:08:29,760 --> 00:08:32,551 Oh, o que é essa variável agora-- e você tipo de ver a progressão 187 00:08:32,551 --> 00:08:33,940 do seu código como ele é executado. 188 00:08:33,940 --> 00:08:37,030 Ou o segundo método é fazer as crianças que eles simplesmente escrever a coisa toda 189 00:08:37,030 --> 00:08:38,610 e depois ir como este no final. 190 00:08:38,610 --> 00:08:39,970 Esperemos que ele funciona. 191 00:08:39,970 --> 00:08:44,851 Eu garanto que você, é melhor GDB de ambos os métodos. 192 00:08:44,851 --> 00:08:45,350 Sim. 193 00:08:45,350 --> 00:08:46,980 Portanto, este será o seu novo melhor amigo. 194 00:08:46,980 --> 00:08:51,780 Porque é uma coisa bonita monitores que tanto visualmente 195 00:08:51,780 --> 00:08:54,850 o que seu código está fazendo em um ponto específico 196 00:08:54,850 --> 00:08:57,486 bem como o que todo o seu variáveis ​​estão levando, 197 00:08:57,486 --> 00:08:59,610 como quais são seus valores, nesse ponto específico. 198 00:08:59,610 --> 00:09:02,670 E, desta forma, você pode realmente definir pontos de interrupção em seu código. 199 00:09:02,670 --> 00:09:04,350 Você pode executar através de linha por linha. 200 00:09:04,350 --> 00:09:07,324 GDB e só vai ter para você, exibido para você, 201 00:09:07,324 --> 00:09:09,490 que todas as suas variáveis estão, o que estão fazendo, 202 00:09:09,490 --> 00:09:10,656 o que está acontecendo no código. 203 00:09:10,656 --> 00:09:13,240 E, de tal maneira, que é muito mais fácil de ver 204 00:09:13,240 --> 00:09:17,120 o que está acontecendo em vez de printf-ing ou escrever para baixo suas declarações. 205 00:09:17,120 --> 00:09:19,160 >> Então, vamos fazer um exemplo disso mais tarde. 206 00:09:19,160 --> 00:09:20,660 Então, isso parece um pouco abstrato. 207 00:09:20,660 --> 00:09:23,490 Não se preocupe, nós vamos fazer exemplos. 208 00:09:23,490 --> 00:09:29,170 E assim, essencialmente, as três maiores, funções mais usadas que você precisa em GDB 209 00:09:29,170 --> 00:09:32,500 são os próximos, Passa, e Entre em botões. 210 00:09:32,500 --> 00:09:34,860 Eu vou de cabeça há, na verdade, no momento. 211 00:09:34,860 --> 00:09:40,930 >> Então vocês todos podem ver que ou eu deveria ampliar um pouco? 212 00:09:40,930 --> 00:09:43,220 213 00:09:43,220 --> 00:09:44,470 Na parte de trás, você pode ver isso? 214 00:09:44,470 --> 00:09:45,730 Devo fazer zoom? 215 00:09:45,730 --> 00:09:46,480 Só um pouco? 216 00:09:46,480 --> 00:09:49,390 OK legal. 217 00:09:49,390 --> 00:09:50,280 Aí vamos nós. 218 00:09:50,280 --> 00:09:50,960 ESTÁ BEM. 219 00:09:50,960 --> 00:09:57,000 >> Então, eu tenho, aqui, a minha implementação para ganancioso. 220 00:09:57,000 --> 00:10:01,430 E enquanto um monte de vocês escreveu ganancioso em loop while que form-- 221 00:10:01,430 --> 00:10:04,890 é uma maneira perfeitamente aceitável para fazer ele-- outra maneira de fazer isso é simplesmente 222 00:10:04,890 --> 00:10:06,280 dividir no módulo. 223 00:10:06,280 --> 00:10:09,290 Porque então você pode ter o seu valor e, em seguida, ter seu restante. 224 00:10:09,290 --> 00:10:11,150 E então você pode apenas adicioná-lo todos juntos. 225 00:10:11,150 --> 00:10:13,390 Será que a lógica do que eu estou fazendo aqui fazer sentido para todos, 226 00:10:13,390 --> 00:10:14,117 antes de começarmos? 227 00:10:14,117 --> 00:10:16,760 228 00:10:16,760 --> 00:10:17,980 Mais ou menos? 229 00:10:17,980 --> 00:10:18,710 Legal. 230 00:10:18,710 --> 00:10:19,210 Ótimo. 231 00:10:19,210 --> 00:10:21,290 É uma peça muito sexy de código, eu diria. 232 00:10:21,290 --> 00:10:23,502 Como eu disse, David, em palestra, depois de um tempo, 233 00:10:23,502 --> 00:10:25,960 tudo que você vai começar a ver código como algo que é bonito. 234 00:10:25,960 --> 00:10:29,950 E às vezes quando você vê bonita código, é uma sensação maravilhosa. 235 00:10:29,950 --> 00:10:35,410 >> Então, no entanto, enquanto este código é muito bonito, ele não funciona corretamente. 236 00:10:35,410 --> 00:10:37,750 Então, vamos correr check50 sobre este assunto. 237 00:10:37,750 --> 00:10:39,440 Confira 50 20-- oop. 238 00:10:39,440 --> 00:10:43,221 239 00:10:43,221 --> 00:10:43,720 2? 240 00:10:43,720 --> 00:10:44,990 É que pset2? 241 00:10:44,990 --> 00:10:46,870 Sim. 242 00:10:46,870 --> 00:10:47,520 Oh, pset1. 243 00:10:47,520 --> 00:10:50,970 244 00:10:50,970 --> 00:10:52,890 ESTÁ BEM. 245 00:10:52,890 --> 00:10:53,900 Então corremos check50. 246 00:10:53,900 --> 00:11:01,550 247 00:11:01,550 --> 00:11:07,170 >> E, como vocês podem ver aqui, ele está falhando um par de casos. 248 00:11:07,170 --> 00:11:10,165 E para alguns de vocês, no curso de fazer os seus conjuntos de problemas, 249 00:11:10,165 --> 00:11:11,110 você é como, ah, por que não está funcionando. 250 00:11:11,110 --> 00:11:13,318 Por que é trabalhar para alguns valores, mas não para outros? 251 00:11:13,318 --> 00:11:17,760 Bem, GDB vai ajudá-lo a figura por que essas entradas não estavam funcionando. 252 00:11:17,760 --> 00:11:18,320 >> ESTÁ BEM. 253 00:11:18,320 --> 00:11:21,640 Então vamos ver, um dos cheques que eu estava falhando em check50 254 00:11:21,640 --> 00:11:24,920 o valor de entrada foi de 0,41. 255 00:11:24,920 --> 00:11:27,830 Portanto, a resposta correta que você deve estar recebendo é um 4. 256 00:11:27,830 --> 00:11:33,090 Mas em vez disso o que estou imprimindo é o 3-N, que está incorrecta. 257 00:11:33,090 --> 00:11:36,190 Então vamos executar isso manualmente, apenas certifique-se de que check50 está funcionando. 258 00:11:36,190 --> 00:11:36,940 Vamos fazer ./greedy. 259 00:11:36,940 --> 00:11:40,130 260 00:11:40,130 --> 00:11:43,340 Opa, eu tenho que fazer ganancioso. 261 00:11:43,340 --> 00:11:43,840 Aí vamos nós. 262 00:11:43,840 --> 00:11:44,381 Agora ./greedy. 263 00:11:44,381 --> 00:11:46,950 264 00:11:46,950 --> 00:11:47,670 >> Quanto é devido? 265 00:11:47,670 --> 00:11:49,550 Vamos fazer 0,41. 266 00:11:49,550 --> 00:11:52,590 E sim, nós vemos aqui que é a saída 3 267 00:11:52,590 --> 00:11:55,160 quando a resposta correta, na verdade, deve ser de 4. 268 00:11:55,160 --> 00:12:01,460 Então, vamos entrar GDB e ver como nós pode ir sobre como corrigir este problema. 269 00:12:01,460 --> 00:12:03,992 >> Assim, o primeiro passo na sempre depuração do código 270 00:12:03,992 --> 00:12:05,950 é definir um ponto de interrupção, ou um ponto no qual você 271 00:12:05,950 --> 00:12:09,079 deseja que o computador ou o depurador para começar a olhar para. 272 00:12:09,079 --> 00:12:11,120 Então, se você realmente não sabe qual é seu problema, 273 00:12:11,120 --> 00:12:14,670 Normalmente, a coisa típica queremos fazer é definir o nosso ponto de interrupção na principal. 274 00:12:14,670 --> 00:12:18,520 Então, se vocês podem ver isso botão vermelho ali mesmo, 275 00:12:18,520 --> 00:12:22,860 Sim, isso foi me estabelecendo um breakpoint para a função principal. 276 00:12:22,860 --> 00:12:24,130 Eu clique isso. 277 00:12:24,130 --> 00:12:26,130 >> E então eu posso ir até meu botão Debug. 278 00:12:26,130 --> 00:12:27,036 Eu bater esse botão. 279 00:12:27,036 --> 00:12:31,710 280 00:12:31,710 --> 00:12:36,555 Deixe-me zoom out se eu puder. 281 00:12:36,555 --> 00:12:38,020 Aí vamos nós. 282 00:12:38,020 --> 00:12:40,730 Portanto, temos, aqui, um painel à direita. 283 00:12:40,730 --> 00:12:43,680 Sinto muito, pessoal na parte de trás, você não pode realmente ver muito bem. 284 00:12:43,680 --> 00:12:49,090 Mas, essencialmente, todos este painel direita está fazendo 285 00:12:49,090 --> 00:12:53,130 é manter o controle de ambos os destaque A linha, que é a linha de código 286 00:12:53,130 --> 00:12:56,640 que o computador está sendo executado, bem como todas as suas variáveis 287 00:12:56,640 --> 00:12:57,600 aqui embaixo. 288 00:12:57,600 --> 00:13:00,487 >> Então você tem centavos, moedas, n, todos declararam a coisas diferentes 289 00:13:00,487 --> 00:13:01,070 neste ponto. 290 00:13:01,070 --> 00:13:04,850 Não se preocupe, porque não temos, na verdade, inicializado-los a quaisquer variáveis ​​ainda. 291 00:13:04,850 --> 00:13:07,200 Assim, no seu computador, o seu computador só está vendo, 292 00:13:07,200 --> 00:13:14,376 oh, 32767 foi a última função utilizada de que o espaço de memória no meu computador. 293 00:13:14,376 --> 00:13:16,000 E assim que é onde atualmente é centavos. 294 00:13:16,000 --> 00:13:19,360 Mas não que uma vez que você executar o código, deve tornar-se inicializado. 295 00:13:19,360 --> 00:13:24,110 >> Então, vamos passar por, linha por linha, o que está acontecendo aqui. 296 00:13:24,110 --> 00:13:25,350 ESTÁ BEM. 297 00:13:25,350 --> 00:13:29,400 Então, aqui estão os três botões que eu só explicada. 298 00:13:29,400 --> 00:13:34,090 Você tem o Play, ou a função Run, botão, você tem a Passo sobre o botão, 299 00:13:34,090 --> 00:13:36,600 e você também tem o botão Step Into. 300 00:13:36,600 --> 00:13:41,260 E essencialmente, todos os três eles apenas passar por seu código 301 00:13:41,260 --> 00:13:42,690 e fazer coisas diferentes. 302 00:13:42,690 --> 00:13:45,680 >> Então, normalmente, quando você está depurando, nós não queremos é só apertar Play, 303 00:13:45,680 --> 00:13:47,930 porque o jogo só vai funcionar seu código para o fim de tudo. 304 00:13:47,930 --> 00:13:49,070 E então você não vai realmente sei qual seu problema 305 00:13:49,070 --> 00:13:51,432 é a menos que você definir vários pontos de interrupção. 306 00:13:51,432 --> 00:13:53,890 Se você definir vários pontos de interrupção, Ela só vai automaticamente 307 00:13:53,890 --> 00:13:56,030 executado a partir de um ponto de interrupção, para o próximo, para o próximo. 308 00:13:56,030 --> 00:13:58,030 Mas neste caso nós temos só que um, porque nós 309 00:13:58,030 --> 00:13:59,970 quer trabalhar nosso caminho de cima para baixo para baixo. 310 00:13:59,970 --> 00:14:04,830 Então, vamos ignorar esse botão agora para os fins deste programa. 311 00:14:04,830 --> 00:14:08,230 >> Assim, o Passo sobre a função apenas etapas, ao longo de cada linha única 312 00:14:08,230 --> 00:14:11,510 e diz-lhe o que o computador está fazendo. 313 00:14:11,510 --> 00:14:14,630 O Passo em função vai para a função real 314 00:14:14,630 --> 00:14:16,000 que está em sua linha de código. 315 00:14:16,000 --> 00:14:19,070 Assim, por exemplo, como printf (), que é uma função, certo? 316 00:14:19,070 --> 00:14:21,980 Se eu quisesse fisicamente passo para a função printf (), 317 00:14:21,980 --> 00:14:25,610 Eu gostaria realmente ir para o pedaço de código onde printf () foi escrito e veja 318 00:14:25,610 --> 00:14:26,730 o que está acontecendo lá. 319 00:14:26,730 --> 00:14:29,924 >> Mas, normalmente, assumimos que o código que nós damos-lhe trabalha. 320 00:14:29,924 --> 00:14:31,340 Assumimos o printf () está funcionando. 321 00:14:31,340 --> 00:14:33,170 Assumimos que GetInt () está funcionando. 322 00:14:33,170 --> 00:14:35,170 Portanto, não há necessidade de passo para essas funções. 323 00:14:35,170 --> 00:14:37,170 Mas se há funções que você escreve-se 324 00:14:37,170 --> 00:14:39,060 que você deseja verificar o que está acontecendo, 325 00:14:39,060 --> 00:14:41,200 você iria querer passo em que a função. 326 00:14:41,200 --> 00:14:43,940 >> Então, agora nós apenas estamos indo de passar por cima este pedaço de código. 327 00:14:43,940 --> 00:14:44,485 Então vamos ver. 328 00:14:44,485 --> 00:14:46,547 Oh, impressão, "Oh hai, como muita mudança é devido? " 329 00:14:46,547 --> 00:14:47,130 Nós não nos importamos. 330 00:14:47,130 --> 00:14:49,830 Sabemos que está trabalhando, por isso, passar por cima dela. 331 00:14:49,830 --> 00:14:53,290 >> Então n, que é o nosso flutuador que temos initialized-- ou declared-- 332 00:14:53,290 --> 00:14:56,810 no topo, estamos agora igualando que a GetFloat (). 333 00:14:56,810 --> 00:14:57,810 Então, vamos passar por cima disso. 334 00:14:57,810 --> 00:14:59,580 E vemos no inferior aqui, o programa 335 00:14:59,580 --> 00:15:03,360 está me levando para introduzir um valor. 336 00:15:03,360 --> 00:15:08,580 Então entrada de deixar o valor que queremos para testar aqui, que é 0,41. 337 00:15:08,580 --> 00:15:09,160 Ótimo. 338 00:15:09,160 --> 00:15:12,780 >> Então agora n-- fazer vocês ver aqui, no bottom-- é 339 00:15:12,780 --> 00:15:15,140 stored-- porque ainda não arredondados, é 340 00:15:15,140 --> 00:15:19,540 armazenados neste gigante como flutuador que é 0,4099999996, 341 00:15:19,540 --> 00:15:22,550 que é perto o suficiente para o nosso propósitos, agora, para 0,41. 342 00:15:22,550 --> 00:15:26,090 E então nós vamos ver mais tarde, como nós continuar pisando sobre o programa, 343 00:15:26,090 --> 00:15:29,850 depois aqui, n se tornou arredondado e centavos tornou-se 41. 344 00:15:29,850 --> 00:15:30,350 Ótimo. 345 00:15:30,350 --> 00:15:32,230 Então, nós sabemos que o trabalho do nosso arredondamento. 346 00:15:32,230 --> 00:15:34,700 Sabemos que temos a número correto de centavos, 347 00:15:34,700 --> 00:15:36,990 por isso sabemos que isso é não é realmente o problema. 348 00:15:36,990 --> 00:15:40,050 >> Então, nós continuamos pisando em neste programa. 349 00:15:40,050 --> 00:15:40,900 Vamos aqui. 350 00:15:40,900 --> 00:15:46,139 E assim, depois desta linha de código, deve saber quantos quartos que temos. 351 00:15:46,139 --> 00:15:46,680 Nós passar por cima. 352 00:15:46,680 --> 00:15:52,040 E você vê o que fazemos, na verdade, tem um trimestre porque temos subtraído 25 353 00:15:52,040 --> 00:15:53,790 do nosso valor inicial de 41. 354 00:15:53,790 --> 00:15:55,890 E nós temos 16 esquerda para nossos centavos. 355 00:15:55,890 --> 00:15:58,830 >> Será que todo mundo entender como o programa está percorrendo 356 00:15:58,830 --> 00:16:02,980 e por centavos, passou a ser 16 e por que, agora, as moedas tornou-se um? 357 00:16:02,980 --> 00:16:04,610 Todos estão seguindo essa lógica? 358 00:16:04,610 --> 00:16:05,110 Legal. 359 00:16:05,110 --> 00:16:07,860 Assim, a partir deste ponto, o de trabalho do programa, certo? 360 00:16:07,860 --> 00:16:09,797 Sabemos que ele está fazendo exatamente o que quer que seja. 361 00:16:09,797 --> 00:16:11,880 E nós não o fez, na verdade, tem que imprimir, oh, o que 362 00:16:11,880 --> 00:16:14,430 é centavos, neste ponto, o que é moedas neste momento. 363 00:16:14,430 --> 00:16:17,170 >> Continuamos a atravessar o programa. 364 00:16:17,170 --> 00:16:18,100 Passar por cima. 365 00:16:18,100 --> 00:16:18,620 Legal. 366 00:16:18,620 --> 00:16:19,700 Nós passar por cima de moedas de dez centavos. 367 00:16:19,700 --> 00:16:20,200 Ótimo. 368 00:16:20,200 --> 00:16:22,367 Nós vemos que ele é tomado fora de $ 0,10 para um centavo. 369 00:16:22,367 --> 00:16:23,450 E agora temos duas moedas. 370 00:16:23,450 --> 00:16:25,260 Está certo. 371 00:16:25,260 --> 00:16:31,555 >> Nós passar por cima de moedas de um centavo e nós vemos que temos de sobra centavos. 372 00:16:31,555 --> 00:16:32,680 Hmm, isso é estranho. 373 00:16:32,680 --> 00:16:37,540 Até aqui no programa, eu deveria ter subtraído meus tostões. 374 00:16:37,540 --> 00:16:39,400 Talvez eu só não foi fazendo esse direito linha. 375 00:16:39,400 --> 00:16:42,190 E, infelizmente, você pode ver aqui, porque nós sabemos 376 00:16:42,190 --> 00:16:44,360 que estamos pisando através das linhas 32 e 33, 377 00:16:44,360 --> 00:16:50,560 que é onde o nosso programa impropriamente teve variáveis ​​executado. 378 00:16:50,560 --> 00:16:55,136 Assim, podemos olhar e ver, oh, Eu estou subtraindo centavos aqui, 379 00:16:55,136 --> 00:16:57,010 mas eu não sou realmente adicionando a minha valor da moeda. 380 00:16:57,010 --> 00:16:57,860 Eu estou adicionando ao centavos. 381 00:16:57,860 --> 00:17:00,234 E eu não quero adicionar centavos, eu quero adicionar a moedas. 382 00:17:00,234 --> 00:17:05,420 Então, se nós mudar isso para moedas, nós temos um programa de trabalho. 383 00:17:05,420 --> 00:17:06,730 Eu posso correr check50. 384 00:17:06,730 --> 00:17:11,063 Você pode simplesmente sair do GDB direita aqui e depois executar check50 novamente. 385 00:17:11,063 --> 00:17:11,938 Eu poderia apenas fazer isso. 386 00:17:11,938 --> 00:17:14,822 387 00:17:14,822 --> 00:17:18,480 Eu tenho que fazer ganancioso. 388 00:17:18,480 --> 00:17:19,940 0.41. 389 00:17:19,940 --> 00:17:22,819 E aqui, é impressão a resposta certa. 390 00:17:22,819 --> 00:17:26,569 >> Então, como vocês podem ver, GDB é uma ferramenta muito poderosa 391 00:17:26,569 --> 00:17:29,940 para quando temos tanto código acontecendo e tantas variáveis 392 00:17:29,940 --> 00:17:32,510 que é difícil para nós, como um ser humano, para acompanhar. 393 00:17:32,510 --> 00:17:35,360 O computador, no GDB depurador, tem a capacidade 394 00:17:35,360 --> 00:17:37,020 manter o controle de tudo. 395 00:17:37,020 --> 00:17:40,480 Eu sei, em Visionaire, vocês provavelmente pode ter atingido algumas falhas de segmentação 396 00:17:40,480 --> 00:17:43,150 porque você estava executando fora dos limites de sua matriz. 397 00:17:43,150 --> 00:17:46,510 No exemplo de César, que é exatamente o que eu tenho implementado aqui. 398 00:17:46,510 --> 00:17:50,060 >> Então, eu esqueci de verificar se há o que aconteceria se eu 399 00:17:50,060 --> 00:17:52,510 não ter dois argumentos de linha de comando. 400 00:17:52,510 --> 00:17:53,880 Eu só não colocar nessa seleção. 401 00:17:53,880 --> 00:17:57,380 E assim se eu executar Debug-- eu definir meu ponto de interrupção para a direita lá. 402 00:17:57,380 --> 00:17:58,055 Eu corro Debug. 403 00:17:58,055 --> 00:18:15,880 404 00:18:15,880 --> 00:18:16,550 >> ESTÁ BEM. 405 00:18:16,550 --> 00:18:17,050 Sim. 406 00:18:17,050 --> 00:18:20,350 Então, na verdade, era suposto GDB ter me disse que não 407 00:18:20,350 --> 00:18:22,300 Foi há uma falha de segmentação. 408 00:18:22,300 --> 00:18:24,883 Eu não sei o que estava acontecendo ali mesmo, mas quando eu corri, 409 00:18:24,883 --> 00:18:25,590 que estava trabalhando. 410 00:18:25,590 --> 00:18:29,410 Quando você executa linhas de código através de e GDB pode de repente parar em você, 411 00:18:29,410 --> 00:18:31,540 ir para cima e veja o que o erro é vermelho. 412 00:18:31,540 --> 00:18:33,930 Ele vai dizer-lhe, hey, você teve uma falha de segmentação, 413 00:18:33,930 --> 00:18:38,550 o que significa que você tentou acessar espaço em uma matriz que não existia. 414 00:18:38,550 --> 00:18:39,050 Sim. 415 00:18:39,050 --> 00:18:43,280 >> Assim, no próximo problema definir esta semana, vocês 416 00:18:43,280 --> 00:18:45,600 provavelmente vai ter um monte de variáveis ​​flutuando. 417 00:18:45,600 --> 00:18:48,560 Você não vai ter a certeza de que todos eles significam em um determinado ponto. 418 00:18:48,560 --> 00:18:53,560 Então GDB vai realmente ajudá-lo em descobrir o que eles estão todos igualando 419 00:18:53,560 --> 00:18:55,940 e ser capaz de ver que visualmente. 420 00:18:55,940 --> 00:19:01,995 Alguém está confuso sobre como qualquer um que estava trabalhando? 421 00:19:01,995 --> 00:19:02,495 Legal. 422 00:19:02,495 --> 00:19:10,121 423 00:19:10,121 --> 00:19:10,620 Tudo certo. 424 00:19:10,620 --> 00:19:14,260 Então, depois disso, estamos vai mergulhar na direita 425 00:19:14,260 --> 00:19:17,562 em são quatro diferentes tipos de tipos para esta semana. 426 00:19:17,562 --> 00:19:19,520 Como muitos de vocês, em primeiro lugar de tudo, antes de começarmos, 427 00:19:19,520 --> 00:19:23,020 li toda a especificação para pset3? 428 00:19:23,020 --> 00:19:23,824 ESTÁ BEM. 429 00:19:23,824 --> 00:19:24,740 Estou orgulhoso de vocês. 430 00:19:24,740 --> 00:19:29,110 Isso é como a metade da classe, que é significativamente mais do que da última vez. 431 00:19:29,110 --> 00:19:33,950 >> Então, isso é ótimo, porque quando falamos sobre o conteúdo 432 00:19:33,950 --> 00:19:36,170 em lecture-- ou desculpe, em section-- eu gosto 433 00:19:36,170 --> 00:19:38,210 para relacionar um monte de que de volta para o que o pset é 434 00:19:38,210 --> 00:19:40,210 e como você deseja implementar isso no seu pset. 435 00:19:40,210 --> 00:19:42,400 Então, se você vem tendo ler a especificação, ele vai 436 00:19:42,400 --> 00:19:45,510 ser muito mais fácil para você entender o que eu estou falando sobre quando eu digo, 437 00:19:45,510 --> 00:19:48,720 oh hey, isso pode ser um realmente bom lugar para implementar este tipo. 438 00:19:48,720 --> 00:19:52,870 Assim, aqueles de vocês que leram o especs saber que, como parte de sua pset, 439 00:19:52,870 --> 00:19:54,900 você vai ter que escrever um tipo de espécie. 440 00:19:54,900 --> 00:19:58,670 Então, isso pode ser muito útil para um monte de você hoje. 441 00:19:58,670 --> 00:20:01,760 >> Então, vamos começar com, Essencialmente, o tipo mais simples 442 00:20:01,760 --> 00:20:04,580 do tipo, o tipo de seleção. 443 00:20:04,580 --> 00:20:06,800 O algoritmo típico para como iríamos fazer isto 444 00:20:06,800 --> 00:20:10,460 é-- David passou por todas de palestra, então eu vou mover-se rapidamente ao longo 445 00:20:10,460 --> 00:20:13,900 aqui-- é essencialmente, você tem uma matriz de valores. 446 00:20:13,900 --> 00:20:17,170 E então você encontrar o menor valor não triados 447 00:20:17,170 --> 00:20:20,200 e você trocar esse valor com o primeiro valor indiferenciados. 448 00:20:20,200 --> 00:20:22,700 E então você simplesmente continuar a repetir com o resto da sua lista. 449 00:20:22,700 --> 00:20:25,740 >> E aqui está uma explicação visual de como isso funciona. 450 00:20:25,740 --> 00:20:30,460 Assim, por exemplo, se tivéssemos de começar com uma série de cinco elementos, índice 451 00:20:30,460 --> 00:20:35,910 0 a 4, com 3, 5, 2, 6 e 4 valores colocado no array-- então agora, 452 00:20:35,910 --> 00:20:38,530 nós apenas estamos indo para assumir que todos eles são indiferenciados 453 00:20:38,530 --> 00:20:41,130 porque nós não testei o contrário. 454 00:20:41,130 --> 00:20:44,130 >> Então, como uma espécie de seleção faria trabalho é que ele iria primeiro 455 00:20:44,130 --> 00:20:46,800 executado através da totalidade da matriz indiferenciados. 456 00:20:46,800 --> 00:20:49,120 Ele escolhia o menor valor. 457 00:20:49,120 --> 00:20:51,750 Neste caso, 3, direita agora, é o menor. 458 00:20:51,750 --> 00:20:52,680 Ele fica a 5. 459 00:20:52,680 --> 00:20:55,620 Não, 5 não é maior than-- ou desculpe, não é menos than-- 3. 460 00:20:55,620 --> 00:20:57,779 Assim, o valor mínimo é ainda 3. 461 00:20:57,779 --> 00:20:58,695 E então você começa a 2. 462 00:20:58,695 --> 00:21:00,990 O computador vê, oh, 2 é inferior a 3. 463 00:21:00,990 --> 00:21:02,750 2 agora deve ser o valor mínimo. 464 00:21:02,750 --> 00:21:06,630 E assim 2 swaps com que o primeiro valor. 465 00:21:06,630 --> 00:21:10,702 >> Então, depois de um passe, nós realmente ver que os 2 e os 3 são trocados. 466 00:21:10,702 --> 00:21:13,910 E nós apenas estamos indo para continuar a fazê- este novamente com o resto da matriz. 467 00:21:13,910 --> 00:21:17,660 Então, nós estamos indo apenas para percorrer os últimos quatro índices da matriz. 468 00:21:17,660 --> 00:21:20,670 Vamos ver o que é 3 o valor mínimo seguinte. 469 00:21:20,670 --> 00:21:23,240 Então vamos trocar isso com 4. 470 00:21:23,240 --> 00:21:26,900 E então nós apenas estamos indo para mantê- que atravessa até que, eventualmente, você 471 00:21:26,900 --> 00:21:33,730 chegar a uma matriz classificada em que 2, 3, 4, 5, e 6 são todos classificados. 472 00:21:33,730 --> 00:21:37,530 Será que todo mundo entender a lógica de como uma espécie de seleção funciona? 473 00:21:37,530 --> 00:21:39,669 >> Você apenas tem algum tipo de um valor mínimo. 474 00:21:39,669 --> 00:21:41,210 Você está mantendo o controle de o que é. 475 00:21:41,210 --> 00:21:45,170 E sempre que você encontrá-lo, você trocá-lo com o primeiro valor na array-- 476 00:21:45,170 --> 00:21:48,740 ou, não o primeiro value-- o próximo valor na matriz. 477 00:21:48,740 --> 00:21:50,150 Legal. 478 00:21:50,150 --> 00:21:55,460 >> Então, como vocês tipo de viu de um breve vislumbre, 479 00:21:55,460 --> 00:21:58,450 vamos Pseudocódigo isso. 480 00:21:58,450 --> 00:22:02,510 Então, se vocês nas costas quiser formar um grupo, todos em uma mesa 481 00:22:02,510 --> 00:22:06,170 pode formar um pequeno parceiro, eu vou para dar a vocês como três minutos 482 00:22:06,170 --> 00:22:08,190 apenas para falar através a lógica, em Inglês, 483 00:22:08,190 --> 00:22:14,161 de como podemos ser capazes de implementar pseudocódigo para escrever uma espécie de seleção. 484 00:22:14,161 --> 00:22:14,910 E há doces. 485 00:22:14,910 --> 00:22:16,118 Por favor, venha para cima e obter doces. 486 00:22:16,118 --> 00:22:19,520 Se você é na parte de trás e você quer doces, eu posso jogava balas em você. 487 00:22:19,520 --> 00:22:22,850 Na verdade, fazer legal vocę--. 488 00:22:22,850 --> 00:22:23,552 Oh, desculpe. 489 00:22:23,552 --> 00:22:26,751 490 00:22:26,751 --> 00:22:27,250 ESTÁ BEM. 491 00:22:27,250 --> 00:25:23,880 492 00:25:23,880 --> 00:25:27,140 >> Então, se nós gostaríamos de, como uma classe, escrita pseudocódigo 493 00:25:27,140 --> 00:25:30,466 por quanto se poderia aproximar este problema, apenas sinta-se livre. 494 00:25:30,466 --> 00:25:32,340 Vou apenas ir ao redor e, a fim, peça aos grupos 495 00:25:32,340 --> 00:25:35,065 para a próxima linha de o que deveríamos estar fazendo. 496 00:25:35,065 --> 00:25:37,840 Então, se vocês querem começar fora, qual é a primeira coisa 497 00:25:37,840 --> 00:25:40,600 que fazer quando você está tentando implementar uma maneira de resolver este programa 498 00:25:40,600 --> 00:25:43,480 seletivamente para classificar uma lista? 499 00:25:43,480 --> 00:25:46,349 Vamos apenas supor que tenho uma matriz, tudo bem? 500 00:25:46,349 --> 00:25:49,088 >> AUDIÊNCIA: Você quer criar alguns tipo de [inaudível] que você é 501 00:25:49,088 --> 00:25:50,420 que atravessa toda a sua matriz. 502 00:25:50,420 --> 00:25:51,128 >> ANDI PENG: Certo. 503 00:25:51,128 --> 00:25:54,100 Então você vai querer fazer uma iteração através de cada espaço, certo? 504 00:25:54,100 --> 00:26:05,490 Muito bom. 505 00:26:05,490 --> 00:26:08,600 Se vocês querem me dar o próximo linha-- sim, na parte de trás. 506 00:26:08,600 --> 00:26:11,414 507 00:26:11,414 --> 00:26:13,290 >> AUDIÊNCIA: Verifique- tudo para o menor. 508 00:26:13,290 --> 00:26:14,248 >> ANDI Peng: Lá vamos nós. 509 00:26:14,248 --> 00:26:17,438 Por isso, queremos passar e verificar a ver o que o valor mínimo é, certo? 510 00:26:17,438 --> 00:26:22,110 511 00:26:22,110 --> 00:26:24,840 Eu estou indo para abreviar que a "min". 512 00:26:24,840 --> 00:26:27,658 O que vocês querem fazer depois você encontrou o valor mínimo? 513 00:26:27,658 --> 00:26:28,533 >> AUDIÊNCIA: [inaudível] 514 00:26:28,533 --> 00:26:29,942 515 00:26:29,942 --> 00:26:33,150 ANDI Peng: Então você vai querer ligá-lo com o primeiro desse array, 516 00:26:33,150 --> 00:26:33,650 certo? 517 00:26:33,650 --> 00:26:45,120 518 00:26:45,120 --> 00:26:46,850 Esse é o começo, eu vou dizer. 519 00:26:46,850 --> 00:26:47,220 Tudo certo. 520 00:26:47,220 --> 00:26:50,386 Portanto, agora que você já trocou o primeiro um, o que você quer fazer depois disso? 521 00:26:50,386 --> 00:26:54,840 Portanto, agora sabemos que este aqui deve ser o menor valor, certo? 522 00:26:54,840 --> 00:26:58,310 Então você tem um descanso adicional da matriz que é indiferenciado. 523 00:26:58,310 --> 00:27:01,569 Então, o que você quer fazer aqui, se você caras querem me dar a próxima linha? 524 00:27:01,569 --> 00:27:04,610 AUDIÊNCIA: Então você quer fazer uma iteração através do restante da matriz. 525 00:27:04,610 --> 00:27:05,276 ANDI Peng: Sim. 526 00:27:05,276 --> 00:27:09,857 E então o que iterar tipo de implicar provavelmente vamos precisar? 527 00:27:09,857 --> 00:27:10,440 Que tipo de-- 528 00:27:10,440 --> 00:27:12,057 >> AUDIÊNCIA: Oh, uma variável adicional? 529 00:27:12,057 --> 00:27:13,890 ANDI Peng: Provavelmente outro loop for, certo? 530 00:27:13,890 --> 00:27:28,914 Então, nós estamos provavelmente vai querer iterar through-- grande. 531 00:27:28,914 --> 00:27:31,830 E então você vai voltar e provavelmente verificar o mínimo de novo, 532 00:27:31,830 --> 00:27:32,100 certo? 533 00:27:32,100 --> 00:27:34,975 E você vai ficar repetindo isso, porque os loops só vai 534 00:27:34,975 --> 00:27:36,010 para manter funcionando, certo? 535 00:27:36,010 --> 00:27:39,190 >> Então, como vocês podem ver, nós basta ter um pseudocódigo geral 536 00:27:39,190 --> 00:27:41,480 de como nós queremos que este programa para olhar. 537 00:27:41,480 --> 00:27:46,646 Este iterate aqui, o que é que nós tipicamente precisa escrever no nosso código 538 00:27:46,646 --> 00:27:49,270 se queremos fazer uma iteração através de um matriz, o tipo de estrutura? 539 00:27:49,270 --> 00:27:51,030 Eu acho que Christabel já disse isso antes. 540 00:27:51,030 --> 00:27:51,500 >> AUDIÊNCIA: Um laço for. 541 00:27:51,500 --> 00:27:52,160 >> ANDI Peng: Um loop for? 542 00:27:52,160 --> 00:27:52,770 Exatamente. 543 00:27:52,770 --> 00:27:56,060 Portanto, este é, provavelmente, vai ser um loop for. 544 00:27:56,060 --> 00:27:59,240 O que é um cheque aqui vai implicar? 545 00:27:59,240 --> 00:28:02,536 Normalmente, se você quiser verificar se algo é algo else-- 546 00:28:02,536 --> 00:28:03,270 >> AUDIÊNCIA: Se. 547 00:28:03,270 --> 00:28:06,790 >> ANDI Peng: Um se, certo? 548 00:28:06,790 --> 00:28:10,790 E então o swap aqui, vamos passar por cima mais tarde, porque David 549 00:28:10,790 --> 00:28:12,770 passei por isso na palestra também. 550 00:28:12,770 --> 00:28:14,580 E, em seguida, a segunda iteração implies-- 551 00:28:14,580 --> 00:28:15,120 >> AUDIÊNCIA: Outra loop for. 552 00:28:15,120 --> 00:28:16,745 >> ANDI Peng: --another para loop, exatamente. 553 00:28:16,745 --> 00:28:19,870 554 00:28:19,870 --> 00:28:22,000 Então, se nós estamos olhando neste corretamente, 555 00:28:22,000 --> 00:28:24,680 pode ver que estamos, provavelmente, vai precisar de um laço for aninhado 556 00:28:24,680 --> 00:28:28,330 com uma declaração condicional lá e, em seguida, uma parte real de código que é 557 00:28:28,330 --> 00:28:31,360 indo para trocar os valores. 558 00:28:31,360 --> 00:28:35,980 Então eu apenas geralmente escrito um código de pseudocódigo aqui. 559 00:28:35,980 --> 00:28:38,910 E então nós estamos indo realmente fisicamente, como uma classe, 560 00:28:38,910 --> 00:28:40,700 tentar implementar isso hoje. 561 00:28:40,700 --> 00:28:42,486 Vamos voltar a este IDE. 562 00:28:42,486 --> 00:28:49,243 563 00:28:49,243 --> 00:28:50,230 >> Uh oh. 564 00:28:50,230 --> 00:28:51,754 Por que é que não-- aí está. 565 00:28:51,754 --> 00:28:52,253 ESTÁ BEM. 566 00:28:52,253 --> 00:28:55,834 567 00:28:55,834 --> 00:28:57,500 Desculpe, deixe-me tentar ampliar um pouco mais. 568 00:28:57,500 --> 00:28:59,310 Aí vamos nós. 569 00:28:59,310 --> 00:29:05,060 Tudo o que eu estou fazendo aqui é que eu criei um programa chamado "seleção / sort.c." 570 00:29:05,060 --> 00:29:10,860 Eu criei uma matriz de nove valores, 4, 8, 2, 1, 6, 9, 7, 5, 3. 571 00:29:10,860 --> 00:29:14,370 Atualmente, como você pode ver, eles são não-ordenada. 572 00:29:14,370 --> 00:29:17,880 n vai ser o número que diz-lhe a quantidade de valores 573 00:29:17,880 --> 00:29:18,920 você tem em sua matriz. 574 00:29:18,920 --> 00:29:20,670 Neste caso, temos nove valores. 575 00:29:20,670 --> 00:29:23,760 E eu só tenho um loop for aqui que imprime a matriz indiferenciados. 576 00:29:23,760 --> 00:29:28,370 >> E no final, eu também tenho um para loop que apenas imprime-lo novamente. 577 00:29:28,370 --> 00:29:32,070 Então, teoricamente, se este programa está funcionando corretamente, no final, 578 00:29:32,070 --> 00:29:35,670 você deve ver um impresso para o laço em que 1, 2, 3, 4, 5, 6, 7, 8, 579 00:29:35,670 --> 00:29:39,310 9 são todos corretamente em ordem. 580 00:29:39,310 --> 00:29:43,410 >> Então, nós temos o nosso pseudocódigo aqui. 581 00:29:43,410 --> 00:29:46,090 Alguém quer para-- Eu sou apenas indo para ir pedir volunteers-- 582 00:29:46,090 --> 00:29:49,540 me diga exatamente o que digitar se nós queremos, em primeiro lugar, apenas uma iteração 583 00:29:49,540 --> 00:29:52,840 até o início deste array? 584 00:29:52,840 --> 00:29:55,204 Qual é a linha de código que eu sou provavelmente vai precisar aqui? 585 00:29:55,204 --> 00:29:56,990 >> AUDIÊNCIA: [inaudível] 586 00:29:56,990 --> 00:29:59,010 >> ANDI Peng: Sim, sinto livre a-- desculpe, você 587 00:29:59,010 --> 00:30:02,318 Não tem que ficar up-- sensação livre para levantar a sua voz um pouco. 588 00:30:02,318 --> 00:30:08,190 >> AUDIÊNCIA: Para int i é igual a 0-- 589 00:30:08,190 --> 00:30:10,690 >> ANDI Peng: Sim, boa. 590 00:30:10,690 --> 00:30:15,220 >> AUDIÊNCIA: i é menor do que o comprimento de matriz. 591 00:30:15,220 --> 00:30:19,630 >> ANDI Peng: Então lembre- importa aqui, porque nós 592 00:30:19,630 --> 00:30:23,060 não tem uma função que nos diz o comprimento de uma matriz, 593 00:30:23,060 --> 00:30:25,790 nós já temos um valor que armazena isso. 594 00:30:25,790 --> 00:30:27,920 Certo? 595 00:30:27,920 --> 00:30:31,010 Outro aspecto a ter em mente-- em uma matriz 596 00:30:31,010 --> 00:30:33,940 de nove valores, quais são os índices? 597 00:30:33,940 --> 00:30:38,720 Vamos apenas dizer que essa matriz era 0-3. 598 00:30:38,720 --> 00:30:41,500 Você vê que a última índice é, na verdade, três. 599 00:30:41,500 --> 00:30:45,530 Não é 4, mesmo que não haja quatro valores na matriz. 600 00:30:45,530 --> 00:30:49,866 >> Então aqui, nós temos que ter muito cuidado do que a nossa condição para o comprimento 601 00:30:49,866 --> 00:30:50,490 Será. 602 00:30:50,490 --> 00:30:51,948 >> AUDIÊNCIA: Não seria n menos 1? 603 00:30:51,948 --> 00:30:54,440 ANDI Peng: Vai n menos 1, exatamente. 604 00:30:54,440 --> 00:30:57,379 Isso faz sentido, porque é n menos 1, todo mundo? 605 00:30:57,379 --> 00:30:58,920 É porque as matrizes são indexados zero. 606 00:30:58,920 --> 00:31:02,010 Eles começam em 0 e correr até n menos 1. 607 00:31:02,010 --> 00:31:03,210 Sim, é um pouco complicado. 608 00:31:03,210 --> 00:31:03,730 ESTÁ BEM. 609 00:31:03,730 --> 00:31:05,929 E depois-- 610 00:31:05,929 --> 00:31:08,054 AUDIÊNCIA: Isnt'1 que já tomado cuidado, porém, 611 00:31:08,054 --> 00:31:11,400 apenas por não dizer "inferior ou igual "e apenas dizer" menos do que? " 612 00:31:11,400 --> 00:31:13,108 >> ANDI Peng: Isso é um pergunta muito boa. 613 00:31:13,108 --> 00:31:13,630 Então sim. 614 00:31:13,630 --> 00:31:17,410 Mas também, a maneira que nós somos implementar o direito de verificar, 615 00:31:17,410 --> 00:31:19,120 você precisa para comparar dois valores. 616 00:31:19,120 --> 00:31:21,009 Então você realmente quer deixar o "para" vazio. 617 00:31:21,009 --> 00:31:23,050 Porque se você comparar este, você não vai 618 00:31:23,050 --> 00:31:25,530 tem alguma coisa depois que ele para comparar, certo? 619 00:31:25,530 --> 00:31:27,460 Sim. 620 00:31:27,460 --> 00:31:29,297 Então i ++. 621 00:31:29,297 --> 00:31:30,380 Vamos adicionar nossos suportes em. 622 00:31:30,380 --> 00:31:30,880 Whoops. 623 00:31:30,880 --> 00:31:33,950 624 00:31:33,950 --> 00:31:34,710 Ótimo. 625 00:31:34,710 --> 00:31:39,117 Portanto, temos o início do nosso circuito externo. 626 00:31:39,117 --> 00:31:41,450 Então, agora nós provavelmente quer criar uma variável para manter 627 00:31:41,450 --> 00:31:43,085 a par de o menor valor, certo? 628 00:31:43,085 --> 00:31:45,751 Alguém quer me dar o linha de código que faria isso? 629 00:31:45,751 --> 00:31:48,700 630 00:31:48,700 --> 00:31:53,570 O que precisamos se vamos querer armazenar algo? 631 00:31:53,570 --> 00:31:55,047 >> Certo. 632 00:31:55,047 --> 00:31:57,630 Talvez um nome melhor para que seria ser-- "temp" totalmente works-- 633 00:31:57,630 --> 00:32:00,655 talvez um mais apropriadamente chamado seria, se queremos que a menor value-- 634 00:32:00,655 --> 00:32:01,624 >> AUDIÊNCIA: Min. 635 00:32:01,624 --> 00:32:02,790 ANDI Peng: min, lá vamos nós. 636 00:32:02,790 --> 00:32:05,230 min seria bom. 637 00:32:05,230 --> 00:32:08,340 E aqui, o que nós quer inicializá-lo para? 638 00:32:08,340 --> 00:32:09,620 Isto é um pouco complicado. 639 00:32:09,620 --> 00:32:13,580 Porque agora no início desta matriz, 640 00:32:13,580 --> 00:32:15,730 você ainda não olhou para nada, certo? 641 00:32:15,730 --> 00:32:19,200 Então, o que, automaticamente, se nós estamos apenas no i é igual a 0, 642 00:32:19,200 --> 00:32:22,302 o que queremos para inicializar nosso primeiro valor mínimo para? 643 00:32:22,302 --> 00:32:22,802 AUDIÊNCIA: i. 644 00:32:22,802 --> 00:32:24,790 ANDI Peng: i, exatamente. 645 00:32:24,790 --> 00:32:27,040 Christabel, por que queremos para inicializar-lo para mim? 646 00:32:27,040 --> 00:32:28,510 >> AUDIÊNCIA: Porque, bem, nós estamos começando com 0. 647 00:32:28,510 --> 00:32:31,660 Então, porque não temos nada para comparar que ele, o mínimo vai acabar sendo 0. 648 00:32:31,660 --> 00:32:32,451 >> ANDI Peng: Exatamente. 649 00:32:32,451 --> 00:32:34,400 Então, ela é exatamente correto. 650 00:32:34,400 --> 00:32:36,780 Porque nós não temos realmente olhou para nada ainda, 651 00:32:36,780 --> 00:32:38,680 não sabemos o que o nosso valor mínimo é. 652 00:32:38,680 --> 00:32:41,960 Queremos apenas inicializar-lo para i, que, atualmente, está bem aqui. 653 00:32:41,960 --> 00:32:44,750 E enquanto continuamos a mover para baixo essa matriz, 654 00:32:44,750 --> 00:32:48,122 vamos ver que, com cada passe adicional, incrementa i. 655 00:32:48,122 --> 00:32:49,830 E assim, nesse ponto, i provavelmente vai 656 00:32:49,830 --> 00:32:52,329 a querer ser o mínimo, porque ele vai ser o que quer 657 00:32:52,329 --> 00:32:54,520 é o início da matriz não triados. 658 00:32:54,520 --> 00:32:55,270 Legal. 659 00:32:55,270 --> 00:32:58,720 >> Então, agora nós queremos adicionar um loop for aqui que é 660 00:32:58,720 --> 00:33:03,225 vai percorrer a não classificado, ou o resto desta matriz. 661 00:33:03,225 --> 00:33:05,808 Alguém quer me dar um linha de código que faria isso? 662 00:33:05,808 --> 00:33:08,870 663 00:33:08,870 --> 00:33:11,330 Hint-- o que precisamos aqui em baixo? 664 00:33:11,330 --> 00:33:17,320 665 00:33:17,320 --> 00:33:18,820 O que vai fazer no presente para loop? 666 00:33:18,820 --> 00:33:19,465 Sim. 667 00:33:19,465 --> 00:33:21,590 AUDIÊNCIA: Então nós quereríamos têm um número inteiro diferente, 668 00:33:21,590 --> 00:33:25,080 porque nós estamos correndo pelo resto da matriz em vez do i, talvez por isso 669 00:33:25,080 --> 00:33:25,760 j. 670 00:33:25,760 --> 00:33:27,301 >> ANDI Peng: Sim, j soa bem para mim. 671 00:33:27,301 --> 00:33:27,850 É igual? 672 00:33:27,850 --> 00:33:33,930 >> AUDIÊNCIA: Então seria eu mais 1, porque você está começando no próximo valor. 673 00:33:33,930 --> 00:33:40,395 E, em seguida, para o end---lo novamente, j é menos de n menos 1, e depois j ++. 674 00:33:40,395 --> 00:33:41,103 ANDI Peng: Grande. 675 00:33:41,103 --> 00:33:48,510 676 00:33:48,510 --> 00:33:52,750 >> E, em seguida, aqui, nós vamos querer verificar para ver se a nossa condição for cumprida, 677 00:33:52,750 --> 00:33:53,250 certo? 678 00:33:53,250 --> 00:33:55,740 Porque você quer alterar o valor mínimo 679 00:33:55,740 --> 00:33:58,700 se é realmente menor do que o que você está comparando-a, certo? 680 00:33:58,700 --> 00:34:01,146 Então, o que vamos querer aqui? 681 00:34:01,146 --> 00:34:04,160 682 00:34:04,160 --> 00:34:04,897 Verifique para ver. 683 00:34:04,897 --> 00:34:06,730 Que tipo de declaração estamos, provavelmente, vai 684 00:34:06,730 --> 00:34:08,389 ti deseja usar, se nós querer verificar alguma coisa? 685 00:34:08,389 --> 00:34:09,360 >> AUDIÊNCIA: Uma instrução if. 686 00:34:09,360 --> 00:34:10,485 >> ANDI Peng: Uma instrução if. 687 00:34:10,485 --> 00:34:13,155 Então se-- eo que vai ser a condição de que nós queremos dentro 688 00:34:13,155 --> 00:34:13,988 do nosso if? 689 00:34:13,988 --> 00:34:18,255 690 00:34:18,255 --> 00:34:22,960 >> AUDIÊNCIA: Se o valor de j é menor do que o valor de i-- 691 00:34:22,960 --> 00:34:24,600 >> ANDI Peng: Exatamente. 692 00:34:24,600 --> 00:34:27,480 Então se-- de modo que este conjunto é chamado de "matriz". 693 00:34:27,480 --> 00:34:27,980 Ótimo. 694 00:34:27,980 --> 00:34:30,465 Então, se array-- que foi isso? 695 00:34:30,465 --> 00:34:31,090 Diga isso de novo. 696 00:34:31,090 --> 00:34:39,590 >> AUDIÊNCIA: Se matriz-j é menor do que matriz-i, então poderíamos mudar o min. 697 00:34:39,590 --> 00:34:41,590 Assim, a min seria j. 698 00:34:41,590 --> 00:34:44,590 699 00:34:44,590 --> 00:34:47,249 >> ANDI Peng: Isso faz sentido? 700 00:34:47,249 --> 00:34:48,670 ESTÁ BEM. 701 00:34:48,670 --> 00:34:52,929 E agora aqui em baixo, nós, na verdade, deseja implementar a troca, certo? 702 00:34:52,929 --> 00:34:58,285 Assim recordar, a palestra, que David, quando ele estava tentando trocar as-- o que era 703 00:34:58,285 --> 00:34:59,996 suco de laranja ele-- e milk-- 704 00:34:59,996 --> 00:35:01,150 >> AUDIÊNCIA: Isso foi gross. 705 00:35:01,150 --> 00:35:02,816 >> ANDI Peng: Sim, isso foi tipo de Gross. 706 00:35:02,816 --> 00:35:05,310 Mas foi uma boa bonita conceito demonstrando tempo. 707 00:35:05,310 --> 00:35:08,430 Então, pense de seus valores aqui. 708 00:35:08,430 --> 00:35:10,794 Você tem uma matriz de minutos, uma série de i, 709 00:35:10,794 --> 00:35:12,460 ou o que nós estávamos tentando trocar aqui. 710 00:35:12,460 --> 00:35:15,310 E você provavelmente não pode derramar-los em uns aos outros, ao mesmo tempo, para a direita? 711 00:35:15,310 --> 00:35:17,180 Então, o que vamos a necessidade de criar aqui 712 00:35:17,180 --> 00:35:19,126 a fim de trocar os valores corretamente? 713 00:35:19,126 --> 00:35:19,820 >> AUDIÊNCIA: Uma variável temporária. 714 00:35:19,820 --> 00:35:21,370 >> ANDI Peng: Uma variável temporária. 715 00:35:21,370 --> 00:35:22,570 Então vamos fazer int temporário. 716 00:35:22,570 --> 00:35:25,681 Veja, isso seria uma melhor tempo a-- Whoa, o que foi isso? 717 00:35:25,681 --> 00:35:26,180 ESTÁ BEM. 718 00:35:26,180 --> 00:35:29,800 Portanto, esta teria sido uma melhor tempo para nomear o "temp." variável 719 00:35:29,800 --> 00:35:30,730 Então vamos fazer int temporário. 720 00:35:30,730 --> 00:35:32,563 O que é que vamos Definir temp igual a aqui? 721 00:35:32,563 --> 00:35:34,752 722 00:35:34,752 --> 00:35:35,335 AUDIÊNCIA: Min? 723 00:35:35,335 --> 00:35:38,508 724 00:35:38,508 --> 00:35:39,716 ANDI Peng: É um pouco complicado. 725 00:35:39,716 --> 00:35:43,110 726 00:35:43,110 --> 00:35:44,880 Ele realmente não importa no final. 727 00:35:44,880 --> 00:35:47,690 Não importa o que ordem que você escolher para trocar em 728 00:35:47,690 --> 00:35:50,862 desde que você está fazendo certo que você é manter o controle do que você está trocando. 729 00:35:50,862 --> 00:35:52,250 >> AUDIÊNCIA: Poderia ser gama-i. 730 00:35:52,250 --> 00:35:53,666 >> ANDI Peng: Sim, vamos fazer matriz-i. 731 00:35:53,666 --> 00:35:55,950 732 00:35:55,950 --> 00:35:59,305 E então, qual é a próxima linha de código que nós queremos ter aqui? 733 00:35:59,305 --> 00:36:00,680 AUDIÊNCIA: array-i é igual a matriz de j. 734 00:36:00,680 --> 00:36:07,154 735 00:36:07,154 --> 00:36:08,070 ANDI Peng: E ​​por último? 736 00:36:08,070 --> 00:36:12,070 AUDIÊNCIA: array-j é igual a matriz-i. 737 00:36:12,070 --> 00:36:14,525 Audiência: Ou matriz j iguais matriz de temp-- ou, temporário. 738 00:36:14,525 --> 00:36:17,135 739 00:36:17,135 --> 00:36:19,430 >> ANDI Peng: OK. 740 00:36:19,430 --> 00:36:21,510 Então, vamos executar este e veja se ele está indo para o trabalho. 741 00:36:21,510 --> 00:36:37,520 742 00:36:37,520 --> 00:36:39,335 Onde é que está acontecendo? 743 00:36:39,335 --> 00:36:40,210 Oh, isso é um problema. 744 00:36:40,210 --> 00:36:44,320 Veja, na linha 40, estamos tentando usar matriz-j? 745 00:36:44,320 --> 00:36:47,022 Mas onde é que j só existem em? 746 00:36:47,022 --> 00:36:48,402 >> AUDIÊNCIA: No loop for. 747 00:36:48,402 --> 00:36:49,110 ANDI PENG: Certo. 748 00:36:49,110 --> 00:36:51,730 Então o que é que vamos fazer? 749 00:36:51,730 --> 00:36:53,170 >> AUDIÊNCIA: Definir fora as-- 750 00:36:53,170 --> 00:36:57,777 751 00:36:57,777 --> 00:37:00,610 AUDIÊNCIA: É, eu acho que você tem para usar outra instrução if, certo? 752 00:37:00,610 --> 00:37:05,230 Assim como, se o minimum-- tudo bem, deixe-me pensar. 753 00:37:05,230 --> 00:37:08,170 754 00:37:08,170 --> 00:37:09,990 >> ANDI Peng: Caras, tente para dar uma olhada Deixe-nos 755 00:37:09,990 --> 00:37:11,270 Veja, o que é algo que podemos fazer aqui? 756 00:37:11,270 --> 00:37:11,811 >> AUDIÊNCIA: OK. 757 00:37:11,811 --> 00:37:15,900 Portanto, se o mínimo não é igual j-- assim ainda se o mínimo é i-- 758 00:37:15,900 --> 00:37:17,570 então não teríamos de trocar. 759 00:37:17,570 --> 00:37:22,450 760 00:37:22,450 --> 00:37:24,712 >> ANDI Peng: Será que a igualdade de i? 761 00:37:24,712 --> 00:37:25,920 O que você quer dizer aqui? 762 00:37:25,920 --> 00:37:30,494 >> AUDIÊNCIA: Ou sim, se o mínimo não é igual a mim, sim. 763 00:37:30,494 --> 00:37:39,627 764 00:37:39,627 --> 00:37:40,210 ANDI Peng: OK. 765 00:37:40,210 --> 00:37:42,040 Bem, isso resolve, tipo, nossos problemas. 766 00:37:42,040 --> 00:37:47,265 Mas isso ainda não resolve o problema do que acontece se j-- desde j 767 00:37:47,265 --> 00:37:49,890 não existe fora dele, o que você que nós queremos fazer com ele? 768 00:37:49,890 --> 00:37:50,698 Declará-la fora? 769 00:37:50,698 --> 00:37:59,410 770 00:37:59,410 --> 00:38:02,730 Vamos tentar executar este. 771 00:38:02,730 --> 00:38:04,435 Uh oh. 772 00:38:04,435 --> 00:38:06,200 Nossa espécie não está funcionando. 773 00:38:06,200 --> 00:38:10,060 >> Como você pode ver, nosso inicial matriz tinha esses valores. 774 00:38:10,060 --> 00:38:14,800 E depois, ele deve ter foi em 1, 2, 3, 4, 5, 6, 7, 8, 9. 775 00:38:14,800 --> 00:38:15,530 Não esta funcionando. 776 00:38:15,530 --> 00:38:16,030 Ahh. 777 00:38:16,030 --> 00:38:17,184 O que nós fazemos? 778 00:38:17,184 --> 00:38:17,850 AUDIÊNCIA: Debug. 779 00:38:17,850 --> 00:38:21,787 780 00:38:21,787 --> 00:38:23,370 ANDI Peng: Tudo bem, podemos tentar isso. 781 00:38:23,370 --> 00:38:25,030 Podemos depurar. 782 00:38:25,030 --> 00:38:26,042 Aumentar um pouco. 783 00:38:26,042 --> 00:38:31,177 784 00:38:31,177 --> 00:38:33,656 Vamos definir o nosso ponto de interrupção. 785 00:38:33,656 --> 00:38:37,280 Vamos OK como--. 786 00:38:37,280 --> 00:38:40,444 >> Então, porque já sabemos que estas linhas, 15 a 22, 787 00:38:40,444 --> 00:38:43,610 são working-- porque tudo que eu estou fazendo é apenas iterar e printing-- 788 00:38:43,610 --> 00:38:45,406 I pode ir em frente e ignorar isso. 789 00:38:45,406 --> 00:38:47,280 Vamos começar na linha 25. 790 00:38:47,280 --> 00:38:48,712 Oop, deixe-me livrar disso. 791 00:38:48,712 --> 00:38:51,598 792 00:38:51,598 --> 00:38:54,057 >> AUDIÊNCIA: Então, do ponto de interrupção onde a depuração começa? 793 00:38:54,057 --> 00:38:54,890 ANDI Peng: ou pára. 794 00:38:54,890 --> 00:38:55,670 AUDIÊNCIA: ou pára. 795 00:38:55,670 --> 00:38:55,930 ANDI Peng: Sim. 796 00:38:55,930 --> 00:38:58,640 Você pode definir vários pontos de interrupção e ele pode simplesmente pular de um para o outro. 797 00:38:58,640 --> 00:39:01,590 Mas neste caso nós não sabemos onde o erro está acontecendo. 798 00:39:01,590 --> 00:39:03,780 Então, nós apenas queremos começar de cima para baixo. 799 00:39:03,780 --> 00:39:05,020 Sim. 800 00:39:05,020 --> 00:39:05,550 ESTÁ BEM. 801 00:39:05,550 --> 00:39:08,460 >> Então esta linha aqui, podemos intervir. 802 00:39:08,460 --> 00:39:11,499 Você pode ver aqui em baixo, nós temos uma matriz. 803 00:39:11,499 --> 00:39:13,290 Esses são os valores que estão na matriz. 804 00:39:13,290 --> 00:39:16,360 Você vê que, como índice de 0, ele corresponde ao value-- oh, 805 00:39:16,360 --> 00:39:17,526 Vou tentar fazer zoom. 806 00:39:17,526 --> 00:39:20,650 Desculpe, é realmente difícil para see-- na matriz índice 0, 807 00:39:20,650 --> 00:39:24,090 que tem um valor de 4 e então assim por diante e assim por diante. 808 00:39:24,090 --> 00:39:25,670 Temos as nossas variáveis ​​locais. 809 00:39:25,670 --> 00:39:28,570 Agora eu é igual a 0, o que nós queremos que ele seja. 810 00:39:28,570 --> 00:39:31,540 811 00:39:31,540 --> 00:39:33,690 >> E assim vamos continuar percorrendo. 812 00:39:33,690 --> 00:39:36,850 O nosso mínima é igual a 0, que nós também queremos que ele seja. 813 00:39:36,850 --> 00:39:39,470 814 00:39:39,470 --> 00:39:45,560 E, então, entrar em nosso segundo para ciclo, se a matriz-j é inferior a matriz-i, 815 00:39:45,560 --> 00:39:46,380 que não era. 816 00:39:46,380 --> 00:39:48,130 Então, se você ver como que pulou isso? 817 00:39:48,130 --> 00:39:52,430 >> AUDIÊNCIA: Então deve ser o caso mínimo, tudo isso-- que não deve 818 00:39:52,430 --> 00:39:55,424 estar dentro do primeiro para o loop? 819 00:39:55,424 --> 00:39:57,340 ANDI Peng: Não, porque você ainda deseja testar. 820 00:39:57,340 --> 00:40:00,329 Você quer fazer uma comparação cada tempo, mesmo depois de passar por ela. 821 00:40:00,329 --> 00:40:02,620 Você não apenas quer fazê-lo na primeira passagem. 822 00:40:02,620 --> 00:40:05,240 Você quer fazê-lo com cada passagem adicional novamente. 823 00:40:05,240 --> 00:40:07,198 Então você quer verificar se há sua condição dentro. 824 00:40:07,198 --> 00:40:11,610 825 00:40:11,610 --> 00:40:13,746 Então, nós apenas estamos indo para continuar correndo por aqui. 826 00:40:13,746 --> 00:40:17,337 827 00:40:17,337 --> 00:40:18,420 Eu vou dar a vocês uma dica. 828 00:40:18,420 --> 00:40:23,910 Tem a ver com o fato de que, quando você está verificando sua condicional, 829 00:40:23,910 --> 00:40:26,600 você não está verificando para o índice correto. 830 00:40:26,600 --> 00:40:32,510 Então, agora você está verificando para índice de matriz de j é inferior a matriz 831 00:40:32,510 --> 00:40:33,970 Índice de i. 832 00:40:33,970 --> 00:40:36,580 Mas o que você está fazendo em cima o início do loop for? 833 00:40:36,580 --> 00:40:38,260 Você não está definindo j igual a mim? 834 00:40:38,260 --> 00:40:41,260 835 00:40:41,260 --> 00:40:45,415 >> Sim, para que possamos realmente sair do depurador aqui. 836 00:40:45,415 --> 00:40:47,040 Então, vamos dar uma olhada no nosso pseudocódigo. 837 00:40:47,040 --> 00:40:50,070 838 00:40:50,070 --> 00:40:52,580 For-- vamos começam em i é igual a 0. 839 00:40:52,580 --> 00:40:54,760 Nós estamos indo para ir até n menos 1. 840 00:40:54,760 --> 00:40:58,040 Vamos verificar, se temos esse direito? 841 00:40:58,040 --> 00:40:59,580 Sim, isso era certo. 842 00:40:59,580 --> 00:41:02,080 >> Assim, pois, aqui dentro, estamos vai criar um valor mínimo 843 00:41:02,080 --> 00:41:03,630 e definir que igual a i. 844 00:41:03,630 --> 00:41:04,950 Será que vamos fazer isso? 845 00:41:04,950 --> 00:41:06,270 Sim, fiz isso. 846 00:41:06,270 --> 00:41:10,430 Agora, em nosso interior loop for, estamos vai fazer j é igual a i n menos 1. 847 00:41:10,430 --> 00:41:11,950 Será que vamos fazer isso? 848 00:41:11,950 --> 00:41:15,540 Na verdade, nós fizemos isso. 849 00:41:15,540 --> 00:41:19,922 >> Então, no entanto, o que estamos comparando aqui? 850 00:41:19,922 --> 00:41:20,925 >> AUDIÊNCIA: j + 1. 851 00:41:20,925 --> 00:41:21,716 ANDI Peng: Exatamente. 852 00:41:21,716 --> 00:41:24,184 853 00:41:24,184 --> 00:41:27,350 E então você vai querer definir o seu mínimo igual a 1 j mais bem. 854 00:41:27,350 --> 00:41:31,057 855 00:41:31,057 --> 00:41:32,640 Então eu passei por isso muito rapidamente. 856 00:41:32,640 --> 00:41:36,190 Vocês entendem por isso que é j + 1? 857 00:41:36,190 --> 00:41:36,890 ESTÁ BEM. 858 00:41:36,890 --> 00:41:40,700 >> Assim, em sua matriz, em sua primeira passagem, 859 00:41:40,700 --> 00:41:44,850 o loop for, por int i é igual a 0, vamos apenas 860 00:41:44,850 --> 00:41:46,740 assumir este não foi alterado ainda. 861 00:41:46,740 --> 00:41:53,180 862 00:41:53,180 --> 00:41:56,760 Nós temos uma matriz de, completamente, apenas quatro elementos não ordenados, certo? 863 00:41:56,760 --> 00:42:00,760 Por isso, queremos inicializar i igual a 0. 864 00:42:00,760 --> 00:42:03,650 E eu vai apenas percorrer este loop. 865 00:42:03,650 --> 00:42:08,560 E assim na primeira passagem, vamos para inicializar uma variável chamada "min" 866 00:42:08,560 --> 00:42:11,245 que também é igual a I, porque não temos um valor mínimo. 867 00:42:11,245 --> 00:42:12,870 Então, isso é actualmente igual a 0 também. 868 00:42:12,870 --> 00:42:16,182 869 00:42:16,182 --> 00:42:17,640 E então nós vamos passar. 870 00:42:17,640 --> 00:42:19,270 E nós queremos fazer uma iteração novamente. 871 00:42:19,270 --> 00:42:22,900 Agora que nós descobrimos o que o nosso mínimo é, nós queremos para percorrer 872 00:42:22,900 --> 00:42:25,190 novamente para ver se ele está comparando, certo? 873 00:42:25,190 --> 00:42:40,440 Então, j, aqui, vai igual a I, o qual é 0. 874 00:42:40,440 --> 00:42:46,320 E, em seguida, se a matriz j mais eu, que é o que é o próximo mais, como menos 875 00:42:46,320 --> 00:42:49,270 do que o seu mínimo atual valor é, você quer trocar. 876 00:42:49,270 --> 00:42:56,850 >> Então, vamos apenas dizer que nós temos tem, como, 2, 5, 1, 8. 877 00:42:56,850 --> 00:43:01,610 Agora, i é igual a 0 e j é igual a 0. 878 00:43:01,610 --> 00:43:05,210 E esse é o nosso valor mínimo. 879 00:43:05,210 --> 00:43:09,950 Se matriz-j mais i-- por isso, se o isso é depois do que nós estamos olhando para 880 00:43:09,950 --> 00:43:13,450 é maior do que o anterior, que vai tornar-se o mínimo. 881 00:43:13,450 --> 00:43:18,120 >> Então aqui nós vemos que 5 não é menos do que isso. 882 00:43:18,120 --> 00:43:19,730 Então, ele vai não ser 5. 883 00:43:19,730 --> 00:43:23,580 Vemos que 1 é inferior a 2, certo? 884 00:43:23,580 --> 00:43:32,970 Portanto, agora sabemos que o nosso mínimo é vai ser o valor de índice 0, 1, 2. 885 00:43:32,970 --> 00:43:34,030 Sim? 886 00:43:34,030 --> 00:43:39,170 E então quando você chegar aqui, você pode trocar os valores corretos. 887 00:43:39,170 --> 00:43:42,610 >> Então, quando vocês estavam apenas tendo o j antes, você não estavam olhando para o 888 00:43:42,610 --> 00:43:43,260 depois disso. 889 00:43:43,260 --> 00:43:44,520 Você estava olhando o mesmo valor, que 890 00:43:44,520 --> 00:43:46,290 É por isso que ele simplesmente não estava fazendo nada. 891 00:43:46,290 --> 00:43:49,721 Isso faz sentido para todos, por isso que precisamos que mais um lá? 892 00:43:49,721 --> 00:43:50,220 ESTÁ BEM. 893 00:43:50,220 --> 00:43:53,345 Agora vamos correr com ele para fazer certeza de que o resto do código está correcto. 894 00:43:53,345 --> 00:44:04,424 895 00:44:04,424 --> 00:44:05,340 Por que é que acontece? 896 00:44:05,340 --> 00:44:14,780 897 00:44:14,780 --> 00:44:16,364 Ah, é o min aqui. 898 00:44:16,364 --> 00:44:17,780 Nós estávamos comparando o valor errado. 899 00:44:17,780 --> 00:44:24,944 900 00:44:24,944 --> 00:44:25,906 Ah não. 901 00:44:25,906 --> 00:44:30,720 902 00:44:30,720 --> 00:44:33,482 >> Ah, sim, aqui nós trocando os valores errados bem. 903 00:44:33,482 --> 00:44:34,940 Porque nós estávamos olhando para i e j. 904 00:44:34,940 --> 00:44:36,440 Esses são os que foram merecem uma visita. 905 00:44:36,440 --> 00:44:39,160 Nós realmente quiser trocar o mínimo, o mínimo atual, 906 00:44:39,160 --> 00:44:40,550 com o que o exterior é. 907 00:44:40,550 --> 00:44:59,510 908 00:44:59,510 --> 00:45:05,402 E, como vocês podem ver abaixo aqui, temos uma matriz classificada. 909 00:45:05,402 --> 00:45:07,110 Ele só tinha a ver com o facto de que quando 910 00:45:07,110 --> 00:45:09,350 estávamos verificando o valores que foram comparando, 911 00:45:09,350 --> 00:45:11,226 nós não estávamos olhando para os valores corretos. 912 00:45:11,226 --> 00:45:13,850 Nós estávamos olhando para a mesma aqui, não, na verdade, trocando-lo. 913 00:45:13,850 --> 00:45:17,135 Você tem que olhar para um lado para ele e, em seguida, você pode trocar. 914 00:45:17,135 --> 00:45:19,260 Então é isso que era uma espécie de incomodando nosso código antes. 915 00:45:19,260 --> 00:45:22,460 E o que eu fiz aqui é tudo o depurador poderia ter feito para você 916 00:45:22,460 --> 00:45:23,810 Eu só fiz isso no placa, porque é mais fácil 917 00:45:23,810 --> 00:45:26,320 para ver em vez de tentar para fazer zoom e depurador. 918 00:45:26,320 --> 00:45:29,391 Isso faz sentido para todo mundo? 919 00:45:29,391 --> 00:45:29,890 Legal. 920 00:45:29,890 --> 00:45:34,800 921 00:45:34,800 --> 00:45:35,410 >> Tudo certo. 922 00:45:35,410 --> 00:45:41,070 Nós podemos passar para falar sobre notação assintótica, que 923 00:45:41,070 --> 00:45:44,580 é apenas uma maneira elegante de dizer o tempos de execução de todos os tipos dessas. 924 00:45:44,580 --> 00:45:47,650 Então eu sei David, em palestra, aflorados tempos de execução. 925 00:45:47,650 --> 00:45:52,124 E ele passou por toda a fórmula de como calcular os tempos de execução. 926 00:45:52,124 --> 00:45:53,040 Não se preocupa com isso. 927 00:45:53,040 --> 00:45:54,660 Se você for realmente curioso sobre como isso funciona, 928 00:45:54,660 --> 00:45:55,810 fique à vontade para falar comigo depois seção. 929 00:45:55,810 --> 00:45:57,560 Podemos caminhar por as fórmulas juntos. 930 00:45:57,560 --> 00:46:00,689 Mas todos vocês tem que realmente sei é que n ao quadrado sobre 2 931 00:46:00,689 --> 00:46:01,980 é a mesma coisa que n ao quadrado. 932 00:46:01,980 --> 00:46:04,710 Devido ao número maior o expoente, mais cresce. 933 00:46:04,710 --> 00:46:06,590 E assim para os nossos propósitos, todos nós nos preocupamos 934 00:46:06,590 --> 00:46:09,470 é que o número gigante que está crescendo. 935 00:46:09,470 --> 00:46:13,340 >> Então, qual é o melhor caso runtime de seleção tipo? 936 00:46:13,340 --> 00:46:15,830 Se você estiver indo para ter para percorrer uma lista 937 00:46:15,830 --> 00:46:18,712 e então percorrer o resto da lista, 938 00:46:18,712 --> 00:46:20,420 quantas vezes são você vai provavelmente, 939 00:46:20,420 --> 00:46:24,612 no pior na case-- melhor caso, sorry-- percorrer? 940 00:46:24,612 --> 00:46:27,070 Talvez a melhor pergunta é para perguntar, o que é o pior caso 941 00:46:27,070 --> 00:46:28,153 runtime de seleção de classificação. 942 00:46:28,153 --> 00:46:29,366 AUDIÊNCIA: n ao quadrado. 943 00:46:29,366 --> 00:46:30,740 ANDI Peng: É n ao quadrado, certo. 944 00:46:30,740 --> 00:46:36,986 Então, uma maneira fácil de pensar nisso é como, qualquer momento você tem duas aninhadas para loops, 945 00:46:36,986 --> 00:46:38,110 ele vai ser n ao quadrado. 946 00:46:38,110 --> 00:46:40,386 Porque não só é você que funciona através de uma vez, 947 00:46:40,386 --> 00:46:42,260 você tem que voltar volta e correr com ele 948 00:46:42,260 --> 00:46:44,980 mais uma vez dentro para cada valor. 949 00:46:44,980 --> 00:46:48,640 Então, nesse caso, você está correndo n vezes n ao quadrado, que é-- sorry, 950 00:46:48,640 --> 00:46:50,505 n vezes n, o que equivale n ao quadrado. 951 00:46:50,505 --> 00:46:53,230 952 00:46:53,230 --> 00:46:56,360 >> E tipo é também um pouco única no sentido 953 00:46:56,360 --> 00:46:59,774 que não importa se estes valores já estão em ordem. 954 00:46:59,774 --> 00:47:01,440 Ele ainda vai correr através de qualquer maneira. 955 00:47:01,440 --> 00:47:03,872 Vamos apenas dizer que este foi de 1, 2, 3, 4. 956 00:47:03,872 --> 00:47:07,080 Independentemente de estarem ou não foi em fim, ele ainda teria percorreu 957 00:47:07,080 --> 00:47:08,620 e ainda verificou o valor mínimo. 958 00:47:08,620 --> 00:47:10,100 Ele teria feito o mesmo número de cheques 959 00:47:10,100 --> 00:47:12,780 a cada momento, mesmo que não chegou a tocar em nada. 960 00:47:12,780 --> 00:47:16,940 >> Assim, em tal caso, o melhor eo pior tempos de execução são realmente equivalentes. 961 00:47:16,940 --> 00:47:19,160 Assim, o tempo de execução esperado seleção de tipo, 962 00:47:19,160 --> 00:47:23,790 que designamos pelo símbolo de teta, teta, neste caso, 963 00:47:23,790 --> 00:47:24,790 também seria n ao quadrado. 964 00:47:24,790 --> 00:47:26,480 Todos os três destes seriam n ao quadrado. 965 00:47:26,480 --> 00:47:29,653 É claro que todos sobre o porquê o tempo de execução é n ao quadrado? 966 00:47:29,653 --> 00:47:33,360 967 00:47:33,360 --> 00:47:33,980 >> Tudo certo. 968 00:47:33,980 --> 00:47:39,120 Então, eu estou indo só para executar rapidamente pelo resto das sortes. 969 00:47:39,120 --> 00:47:41,137 O algoritmo para bolha sort-- lembre-se, 970 00:47:41,137 --> 00:47:43,220 este foi o primeiro Davi, passando em palestra. 971 00:47:43,220 --> 00:47:46,000 Essencialmente, você pisa toda a lista 972 00:47:46,000 --> 00:47:48,950 e você swap-- você só comparar dois de cada vez. 973 00:47:48,950 --> 00:47:51,350 E se um é maior, que você acabou de trocá-los. 974 00:47:51,350 --> 00:47:53,590 Então, se estes são maiores, você trocaria. 975 00:47:53,590 --> 00:47:56,180 Eu tenho oficial aqui. 976 00:47:56,180 --> 00:47:59,100 >> Então, vamos apenas dizer que você tinha 8, 6, 4, 2. 977 00:47:59,100 --> 00:48:00,571 Você iria comparar a 8 e um 6. 978 00:48:00,571 --> 00:48:01,570 Você precisaria trocá-los. 979 00:48:01,570 --> 00:48:02,610 Você poderia comparar a 8 e um 4. 980 00:48:02,610 --> 00:48:03,609 Você precisaria trocá-los. 981 00:48:03,609 --> 00:48:07,000 Se tiver de trocar a 8 e o 2, alterá-los também. 982 00:48:07,000 --> 00:48:10,760 Assim, em tal sentido, você pode ver, jogado fora ao longo de um longo período de tempo, 983 00:48:10,760 --> 00:48:13,730 como o tipo de bolha de valores as extremidades, o que é por isso que chamamos 984 00:48:13,730 --> 00:48:15,320 bubble sort. 985 00:48:15,320 --> 00:48:19,950 >> Nós só iria percorrer novamente em nossa segunda passagem, e nossa terceira passagem, 986 00:48:19,950 --> 00:48:21,150 e nossa quarta passagem. 987 00:48:21,150 --> 00:48:25,820 Essencialmente, bubble sort apenas corre até que você não fazer mais swaps. 988 00:48:25,820 --> 00:48:31,109 Então, nesse sentido, este é apenas o pseudocódigo geral para ele. 989 00:48:31,109 --> 00:48:32,650 Não se preocupe, estes serão todos online. 990 00:48:32,650 --> 00:48:34,990 Não temos que ir realmente sobre isso. 991 00:48:34,990 --> 00:48:38,134 >> Nós apenas inicializar um contador variável que começa em 0. 992 00:48:38,134 --> 00:48:39,800 E nós iterar através de toda a matriz. 993 00:48:39,800 --> 00:48:43,420 E se um valor é-- se este valor é maior do que aquele valor, 994 00:48:43,420 --> 00:48:44,610 você está indo para trocá-los. 995 00:48:44,610 --> 00:48:46,860 E então você é apenas vai continuar. 996 00:48:46,860 --> 00:48:47,970 E você está indo para contar. 997 00:48:47,970 --> 00:48:50,845 E você está indo só para continuar fazendo este enquanto o contador é maior 998 00:48:50,845 --> 00:48:53,345 a 0, o que significa que cada vez que você tem que trocar, 999 00:48:53,345 --> 00:48:55,220 você sabe que você quer ir para trás e verificar novamente. 1000 00:48:55,220 --> 00:48:59,510 Você deseja manter a verificação até que você saiba que você não tem que trocar mais. 1001 00:48:59,510 --> 00:49:05,570 >> Então, quais são os melhores e piores caso tempos de execução para bubble sort? 1002 00:49:05,570 --> 00:49:09,300 E hint-- esta é realmente diferente tipo de seleção no sentido 1003 00:49:09,300 --> 00:49:11,810 que estas duas respostas não são os mesmos. 1004 00:49:11,810 --> 00:49:14,709 Pense sobre o que aconteceria em um caso, se ele já foi resolvido. 1005 00:49:14,709 --> 00:49:16,500 E pensar sobre o que que aconteceria se fosse 1006 00:49:16,500 --> 00:49:18,372 no caso em que não foi resolvido. 1007 00:49:18,372 --> 00:49:20,580 E você pode tipo de correr através de por que isso está acontecendo. 1008 00:49:20,580 --> 00:49:22,954 Eu vou dar a vocês, tipo, 30 segundos para pensar sobre isso. 1009 00:49:22,954 --> 00:49:52,330 1010 00:49:52,330 --> 00:49:53,540 >> ESTÁ BEM. 1011 00:49:53,540 --> 00:49:57,462 Alguém tem um palpite sobre o que o pior caso de tempo de execução de bubble sort é? 1012 00:49:57,462 --> 00:49:57,962 Sim. 1013 00:49:57,962 --> 00:50:07,810 >> AUDIÊNCIA: seria, como, n vezes n menos 1 ou algo assim? 1014 00:50:07,810 --> 00:50:10,650 Como, cada vez que ele é executado, é apenas, como, um swap de menos 1015 00:50:10,650 --> 00:50:10,960 que quer que fosse. 1016 00:50:10,960 --> 00:50:12,668 >> ANDI Peng: Sim, então você está totalmente certo. 1017 00:50:12,668 --> 00:50:15,940 E este é um caso em que a sua resposta foi realmente mais complexo 1018 00:50:15,940 --> 00:50:17,240 do que aquele que precisa dar. 1019 00:50:17,240 --> 00:50:19,772 Então ele vai para run-- eu sou vai apagar tudo isso aqui. 1020 00:50:19,772 --> 00:50:20,480 Está todo mundo bem? 1021 00:50:20,480 --> 00:50:21,869 Posso apagar isso? 1022 00:50:21,869 --> 00:50:22,368 ESTÁ BEM. 1023 00:50:22,368 --> 00:50:27,904 1024 00:50:27,904 --> 00:50:30,320 Você vai percorrer n vezes pela primeira vez, certo? 1025 00:50:30,320 --> 00:50:33,200 E eles estão indo para ser executado através n menos 1 segundo tempo, certo? 1026 00:50:33,200 --> 00:50:37,130 E então você está indo para mantê- indo, n mina 2, et cetera. 1027 00:50:37,130 --> 00:50:40,210 David fez isso em uma palestra, onde, se você adicionou-se todos esses valores, 1028 00:50:40,210 --> 00:50:48,080 você começa algo que é como-- yeah-- mais de 2, que, essencialmente, apenas reduz 1029 00:50:48,080 --> 00:50:49,784 até n ao quadrado. 1030 00:50:49,784 --> 00:50:51,700 Você está indo para obter um fração estranho lá dentro. 1031 00:50:51,700 --> 00:50:53,892 E assim só sei que a n ao quadrado sempre 1032 00:50:53,892 --> 00:50:55,350 tem precedência sobre a fração. 1033 00:50:55,350 --> 00:50:58,450 E assim, neste caso, o pior tempo de execução seria n ao quadrado. 1034 00:50:58,450 --> 00:51:00,210 Se fosse descendente fim, pense, você 1035 00:51:00,210 --> 00:51:02,530 tem que fazer um swap de cada vez. 1036 00:51:02,530 --> 00:51:05,170 >> Qual seria, potencialmente, o melhor caso de tempo de execução? 1037 00:51:05,170 --> 00:51:08,580 Vamos apenas dizer que, se a lista já foi em ordem, o que poderia ser o tempo de execução? 1038 00:51:08,580 --> 00:51:09,565 >> AUDIÊNCIA: n. 1039 00:51:09,565 --> 00:51:10,690 ANDI Peng: É n, exatamente. 1040 00:51:10,690 --> 00:51:11,600 E por que é n? 1041 00:51:11,600 --> 00:51:13,850 AUDIÊNCIA: Porque você apenas tem que verificar em cada vez. 1042 00:51:13,850 --> 00:51:14,770 ANDI Peng: Exatamente. 1043 00:51:14,770 --> 00:51:17,150 Assim, na melhor execução possível, se esta lista já foi 1044 00:51:17,150 --> 00:51:20,270 sorted-- digamos 1, 2, 3, 4-- você seria apenas passar, você iria verificar, 1045 00:51:20,270 --> 00:51:21,720 você iria ver, oh, todos eles pan out. 1046 00:51:21,720 --> 00:51:22,636 Eu não tive que trocar. 1047 00:51:22,636 --> 00:51:23,370 Terminei. 1048 00:51:23,370 --> 00:51:26,500 Então, nesse caso, é apenas n ou o número de passos que você acabou 1049 00:51:26,500 --> 00:51:29,870 tinha que verificar na primeira lista. 1050 00:51:29,870 --> 00:51:33,990 >> E depois, nós já atingiu tipo de inserção, onde 1051 00:51:33,990 --> 00:51:39,260 o algoritmo é essencialmente a dividir -lo em uma parte classificada e indiferenciados. 1052 00:51:39,260 --> 00:51:42,810 E em seguida, um por um, os valores são indiferenciados 1053 00:51:42,810 --> 00:51:46,880 inserido na sua apropriada posições no início da lista. 1054 00:51:46,880 --> 00:51:52,120 >> Assim, por exemplo, temos uma Lista de 3, 5, 2, 6, 4 novamente. 1055 00:51:52,120 --> 00:51:54,750 Sabemos que é actualmente indiferenciados porque nós temos apenas 1056 00:51:54,750 --> 00:51:57,030 comecei a olhar para ele. 1057 00:51:57,030 --> 00:52:00,610 Vamos dar uma olhada e sabemos que o primeiro valor é ordenada, certo? 1058 00:52:00,610 --> 00:52:04,190 Se você está apenas olhando para uma variedade de tamanho um, você sabe que ele está classificada. 1059 00:52:04,190 --> 00:52:08,230 >> Então nós sabemos que o outros quatro são indiferenciados. 1060 00:52:08,230 --> 00:52:10,980 Passamos por e vemos esse valor. 1061 00:52:10,980 --> 00:52:11,730 Vamos voltar. 1062 00:52:11,730 --> 00:52:13,130 Veja que o valor de 5? 1063 00:52:13,130 --> 00:52:14,110 Vamos dar uma olhada nisso. 1064 00:52:14,110 --> 00:52:15,204 Nós compará-lo a 3. 1065 00:52:15,204 --> 00:52:17,870 Sabemos que é maior do que 3, por isso sabemos que isso está classificado. 1066 00:52:17,870 --> 00:52:22,940 Portanto, sabemos agora que os dois primeiros são classificadas e os três últimos não são. 1067 00:52:22,940 --> 00:52:24,270 >> Vamos dar uma olhada em dois. 1068 00:52:24,270 --> 00:52:25,720 Primeiro vamos verificar isso com cinco. 1069 00:52:25,720 --> 00:52:26,700 É menos do que 5? 1070 00:52:26,700 --> 00:52:27,240 Não é. 1071 00:52:27,240 --> 00:52:29,510 Então nós temos que ficar olhando para baixo. 1072 00:52:29,510 --> 00:52:30,940 Em seguida, você verificar 2 off 3. 1073 00:52:30,940 --> 00:52:31,850 É menos do que? 1074 00:52:31,850 --> 00:52:32,350 Não. 1075 00:52:32,350 --> 00:52:35,430 Então, você sabe a 2 tem que ser inserido na parte da frente e 3 e 5 1076 00:52:35,430 --> 00:52:38,200 ambos têm que ser empurrados para fora. 1077 00:52:38,200 --> 00:52:42,190 Faça isso novamente com 6 e 4. 1078 00:52:42,190 --> 00:52:48,962 E nós apenas manter a verificação, essencialmente, onde basta verificar, verificação, verificação. 1079 00:52:48,962 --> 00:52:51,170 E até que seja na direita posição, que tipo de apenas 1080 00:52:51,170 --> 00:52:54,890 insira-o na posição correta, que é onde o nome veio. 1081 00:52:54,890 --> 00:52:59,830 >> Então, isso é apenas o algoritmo, pseudocódigo per se, tipo, 1082 00:52:59,830 --> 00:53:04,990 em como iríamos implementar um tipo de inserção. 1083 00:53:04,990 --> 00:53:05,954 Pseudocódigo é aqui. 1084 00:53:05,954 --> 00:53:06,620 É tudo online. 1085 00:53:06,620 --> 00:53:10,720 Não se preocupe se vocês são tentando copiar este para baixo. 1086 00:53:10,720 --> 00:53:14,500 Então mais uma vez, mesmo que question-- seria a melhor e piores tempos de execução 1087 00:53:14,500 --> 00:53:16,120 para inserção tipo? 1088 00:53:16,120 --> 00:53:17,750 É muito semelhante à última pergunta. 1089 00:53:17,750 --> 00:53:20,479 Eu vou dar a vocês, tipo, 30 segundos para pensar sobre isso também. 1090 00:53:20,479 --> 00:53:47,150 1091 00:53:47,150 --> 00:53:50,071 >> OK Alguém quer dá-me o pior tempo de execução? 1092 00:53:50,071 --> 00:53:50,570 Sim. 1093 00:53:50,570 --> 00:53:51,490 >> AUDIÊNCIA: n ao quadrado. 1094 00:53:51,490 --> 00:53:52,573 >> ANDI Peng: É n ao quadrado. 1095 00:53:52,573 --> 00:53:53,730 E por que é que n ao quadrado? 1096 00:53:53,730 --> 00:53:57,562 >> AUDIÊNCIA: Porque em ordem inversa, você tem 1097 00:53:57,562 --> 00:54:02,619 passar por n vezes n, que é-- 1098 00:54:02,619 --> 00:54:03,660 ANDI Peng: Sim, exatamente. 1099 00:54:03,660 --> 00:54:06,610 Então, mesmo que na bubble sort. 1100 00:54:06,610 --> 00:54:08,720 Se esta lista está em ordem decrescente, você é 1101 00:54:08,720 --> 00:54:11,240 vai ter que verificar primeiro uma vez. 1102 00:54:11,240 --> 00:54:13,470 E, em seguida, com toda valor adicional, você está 1103 00:54:13,470 --> 00:54:16,390 vai ter que verificar se contra cada valor único, certo? 1104 00:54:16,390 --> 00:54:20,290 E assim por completo, você está indo fazer um n vezes passar um outro n aconteceu, e que 1105 00:54:20,290 --> 00:54:21,750 n é quadrado. 1106 00:54:21,750 --> 00:54:22,860 E sobre o melhor caso? 1107 00:54:22,860 --> 00:54:24,360 Sim. 1108 00:54:24,360 --> 00:54:28,840 >> AUDIÊNCIA: n menos 1, porque o primeiro já é elevado ao quadrado. 1109 00:54:28,840 --> 00:54:30,270 >> ANDI Peng: Então, fechar. 1110 00:54:30,270 --> 00:54:31,850 A resposta é, na verdade, n. 1111 00:54:31,850 --> 00:54:37,189 Porque enquanto o primeiro é classificadas, não pode actually---lo 1112 00:54:37,189 --> 00:54:38,980 nós apenas tivemos sorte, em Nesse exemplo, que dois 1113 00:54:38,980 --> 00:54:40,930 passou a ser o menor número. 1114 00:54:40,930 --> 00:54:43,680 Mas isto não será sempre o caso. 1115 00:54:43,680 --> 00:54:48,040 Se 2 já está classificado no início mas você olha e há um um aqui, 1116 00:54:48,040 --> 00:54:49,144 o 1 vai bater-lo. 1117 00:54:49,144 --> 00:54:51,060 E isso vai acabar sendo colidido de qualquer maneira. 1118 00:54:51,060 --> 00:54:56,250 >> Assim, na melhor das hipóteses, ele é realmente só vai ser n. 1119 00:54:56,250 --> 00:54:59,090 Se você tem 1, 2, 3, 4, 5, 6, 7, 8, você está 1120 00:54:59,090 --> 00:55:00,940 vai percorrer que lista inteira uma vez 1121 00:55:00,940 --> 00:55:03,430 para verificar para ver se está tudo bem. 1122 00:55:03,430 --> 00:55:07,390 É claro que todos na corrida tempos de seleção também? 1123 00:55:07,390 --> 00:55:09,960 Eu sei que eu estou passando estes realmente rápido. 1124 00:55:09,960 --> 00:55:13,330 Mas só sei que se você sabe o conceitos gerais, você deve ser bom. 1125 00:55:13,330 --> 00:55:16,070 ESTÁ BEM. 1126 00:55:16,070 --> 00:55:19,790 Então eu vou dar a vocês talvez, como, um minuto para conversar com seus vizinhos 1127 00:55:19,790 --> 00:55:21,890 sobre o que são apenas algumas das principais diferenças 1128 00:55:21,890 --> 00:55:23,540 entre esses tipos de tipos. 1129 00:55:23,540 --> 00:56:24,571 1130 00:56:24,571 --> 00:56:25,570 Nós falaremos sobre isso em breve. 1131 00:56:25,570 --> 00:56:26,444 AUDIÊNCIA: Oh, OK. 1132 00:56:26,444 --> 00:56:27,320 ANDI Peng: Sim. 1133 00:56:27,320 --> 00:56:28,380 ESTÁ BEM. 1134 00:56:28,380 --> 00:56:33,420 Cool, vamos reunir novamente com a classe. 1135 00:56:33,420 --> 00:56:34,330 ESTÁ BEM. 1136 00:56:34,330 --> 00:56:37,579 Portanto, este foi um tipo de pergunta aberta no sentido 1137 00:56:37,579 --> 00:56:39,120 que há muitas respostas para elas. 1138 00:56:39,120 --> 00:56:40,746 E nós vamos passar por cima de alguns deles brevemente. 1139 00:56:40,746 --> 00:56:43,411 Eu só queria que você obtenha caras pensando sobre o que diferenciou 1140 00:56:43,411 --> 00:56:44,530 os três tipos de tipos. 1141 00:56:44,530 --> 00:56:47,440 E ouvi, também, uma grande question-- o que merge sort fazer? 1142 00:56:47,440 --> 00:56:50,110 Ótima pergunta, porque é isso o que estamos cobrindo seguinte. 1143 00:56:50,110 --> 00:56:52,850 >> Assim é o merge sort um tipo que funciona 1144 00:56:52,850 --> 00:56:56,100 muito diferente dos outros tipos. 1145 00:56:56,100 --> 00:56:58,180 Como vocês podem see-- Davi fez aquela demo 1146 00:56:58,180 --> 00:57:01,130 onde ele tinha todo o legal ruídos de ver como mesclar 1147 00:57:01,130 --> 00:57:04,010 tipo correu, como, infinitamente mais rápido do que os outros dois tipos? 1148 00:57:04,010 --> 00:57:04,510 ESTÁ BEM. 1149 00:57:04,510 --> 00:57:07,580 Então, isso é por causa de mesclagem tipo implementa essa divisão 1150 00:57:07,580 --> 00:57:11,020 e conquistar conceito que nós temos falou sobre um monte na palestra. 1151 00:57:11,020 --> 00:57:14,550 Nesse sentido que nós gostamos de trabalhar mais esperto, não mais difícil, quando você divide 1152 00:57:14,550 --> 00:57:18,120 e conquistar problemas, e quebrá-las para baixo, e, em seguida, colocá-los juntos, 1153 00:57:18,120 --> 00:57:19,930 coisas boas sempre acontecem. 1154 00:57:19,930 --> 00:57:21,960 >> Assim, a maneira que se fundem tipo essencialmente funciona 1155 00:57:21,960 --> 00:57:24,660 é que ele divide um matriz não triados pela metade. 1156 00:57:24,660 --> 00:57:26,500 E então ele tem duas metades de matrizes. 1157 00:57:26,500 --> 00:57:28,220 E ele só classifica essas duas metades. 1158 00:57:28,220 --> 00:57:31,750 Ele apenas continua dividindo pela metade, em metade, ao meio até que tudo está classificada 1159 00:57:31,750 --> 00:57:33,680 e, em seguida, de forma recursiva coloca tudo isso junto. 1160 00:57:33,680 --> 00:57:36,550 >> Então isso é muito abstrato. 1161 00:57:36,550 --> 00:57:38,750 Portanto, este é apenas um pouco de pseudocódigo. 1162 00:57:38,750 --> 00:57:41,040 Isso faz sentido em a forma como ele está sendo executado? 1163 00:57:41,040 --> 00:57:43,870 Então, vamos apenas dizer que você tem um matriz de n elementos, certo? 1164 00:57:43,870 --> 00:57:45,450 Se n é inferior a 2, você pode retornar. 1165 00:57:45,450 --> 00:57:49,040 Porque você sabe que, se houver apenas uma coisa, ele deve ser classificado. 1166 00:57:49,040 --> 00:57:52,600 Senão, você classificar a metade esquerda, e então você classificar a metade direita, 1167 00:57:52,600 --> 00:57:54,140 e então você se fundir. 1168 00:57:54,140 --> 00:57:56,979 >> Assim, enquanto que parece realmente fácil, na realidade, pensando que é 1169 00:57:56,979 --> 00:58:00,270 tipo de difícil. Porque você é como, bem, esse é o tipo de execução em si. 1170 00:58:00,270 --> 00:58:00,769 Certo? 1171 00:58:00,769 --> 00:58:02,430 Está funcionando em si. 1172 00:58:02,430 --> 00:58:05,479 Então, nesse sentido, David tocou sobre a recursividade em sala de aula. 1173 00:58:05,479 --> 00:58:07,270 E isso é um conceito vamos falar sobre mais. 1174 00:58:07,270 --> 00:58:11,430 É que este, estas duas linhas aqui, na verdade, é apenas o programa 1175 00:58:11,430 --> 00:58:13,860 dizendo que ele seja executado em si com entrada diferente. 1176 00:58:13,860 --> 00:58:17,230 Então ao invés de executar-se com a totalidade de n elementos, 1177 00:58:17,230 --> 00:58:20,530 você pode quebrá-lo para baixo na metade esquerda e metade direita 1178 00:58:20,530 --> 00:58:22,680 e, em seguida, executá-lo novamente. 1179 00:58:22,680 --> 00:58:26,050 >> E então nós vamos olhá-lo visualmente, porque eu sou um aprendiz visual. 1180 00:58:26,050 --> 00:58:27,270 Ele funciona melhor para mim. 1181 00:58:27,270 --> 00:58:29,890 Então, vamos olhar para um exemplo visual aqui. 1182 00:58:29,890 --> 00:58:36,237 >> Vamos dizer que nós temos uma matriz, seis elementos, 3, 5, 2, 6, 4, 1, não classificados. 1183 00:58:36,237 --> 00:58:37,820 Tudo bem, há muita coisa nesta página. 1184 00:58:37,820 --> 00:58:43,179 Então, se vocês podem olhar para o primeiro passo aqui, 3, 5, 2, 6, 4, 1, 1185 00:58:43,179 --> 00:58:44,220 você pode dividi-lo ao meio. 1186 00:58:44,220 --> 00:58:45,976 Você tem 3, 5, 2, 6, 4, 1. 1187 00:58:45,976 --> 00:58:48,850 Você sabe que estes aren't-- você Não sei se eles estão ou não classificados, 1188 00:58:48,850 --> 00:58:52,517 para que você mantenha quebrando-as, ao meio, no meio, pela metade, até que finalmente, 1189 00:58:52,517 --> 00:58:53,600 você só tem um elemento. 1190 00:58:53,600 --> 00:58:56,790 E um elemento é sempre classificada, certo? 1191 00:58:56,790 --> 00:59:01,560 >> Então, nós sabemos que 3, 5, 2, 4, 6, 1, por si só, são classificadas. 1192 00:59:01,560 --> 00:59:05,870 E agora podemos juntá-los novamente. 1193 00:59:05,870 --> 00:59:07,510 Então, nós sabemos a 3, 5. 1194 00:59:07,510 --> 00:59:08,510 Colocamos esses juntos. 1195 00:59:08,510 --> 00:59:09,617 Sabemos que é classificada. 1196 00:59:09,617 --> 00:59:10,450 Os 2 ainda está lá. 1197 00:59:10,450 --> 00:59:11,830 Podemos colocar o 4 eo 6 juntos. 1198 00:59:11,830 --> 00:59:13,996 Sabemos que isso está classificado, por isso, colocar isso em conjunto. 1199 00:59:13,996 --> 00:59:14,940 E a 1 existe. 1200 00:59:14,940 --> 00:59:18,720 >> E então você simplesmente olhar para estas duas metades direita aqui. 1201 00:59:18,720 --> 00:59:21,300 Tem a 3, 5, 2, 2, 3, 5. 1202 00:59:21,300 --> 00:59:23,465 Você pode simplesmente comparar o começo de tudo. 1203 00:59:23,465 --> 00:59:26,340 Porque você sabe que isto é separado e você sabe que isso está classificado. 1204 00:59:26,340 --> 00:59:29,360 Então você não tem que mesmo comparar a 5, você acabou de comparar a 3. 1205 00:59:29,360 --> 00:59:32,070 E o 2 é inferior a 3, assim você sabe que 2 deve ir no final. 1206 00:59:32,070 --> 00:59:33,120 >> A mesma coisa por lá. 1207 00:59:33,120 --> 00:59:34,740 A 1 deve ir aqui. 1208 00:59:34,740 --> 00:59:37,330 E então, quando você vai para colocar esses dois valores, 1209 00:59:37,330 --> 00:59:39,950 você sabe que isto é separado e você sabe que que está classificada. 1210 00:59:39,950 --> 00:59:43,240 Então a 1 eo 2, o 1 é inferior a 2. 1211 00:59:43,240 --> 00:59:45,570 Isso diz-lhe que o 1 deve percorrer no final desta 1212 00:59:45,570 --> 00:59:47,480 sem sequer olhar para 3 ou 5. 1213 00:59:47,480 --> 00:59:50,100 E então a 4, você pode apenas vá, ele vai para a direita aqui. 1214 00:59:50,100 --> 00:59:51,480 Você não tem que olhar para o 5. 1215 00:59:51,480 --> 00:59:52,570 Mesma coisa com o 6. 1216 00:59:52,570 --> 00:59:55,860 Você sabe que a 6-- apenas não precisa ser olhado. 1217 00:59:55,860 --> 00:59:57,870 >> E assim, dessa forma, você é salvando-se apenas 1218 00:59:57,870 --> 00:59:59,526 um monte de passos quando você está comparando. 1219 00:59:59,526 --> 01:00:02,150 Você não tem que comparar cada elemento contra outros elementos. 1220 01:00:02,150 --> 01:00:05,230 Você só comparar contra os que você precisa para comparar contra. 1221 01:00:05,230 --> 01:00:06,870 Então, esse é o tipo de um conceito abstrato. 1222 01:00:06,870 --> 01:00:10,540 Não se preocupe se não é bastante bater-lhe ainda direita. 1223 01:00:10,540 --> 01:00:14,740 Mas, geralmente, este é como uma espécie de mesclagem funciona. 1224 01:00:14,740 --> 01:00:17,750 Perguntas, perguntas rápidas, antes de eu seguir em frente? 1225 01:00:17,750 --> 01:00:18,550 Sim. 1226 01:00:18,550 --> 01:00:22,230 >> AUDIÊNCIA: Então você disse que você toma a 1, e em seguida a 4, e o 6 1227 01:00:22,230 --> 01:00:23,860 e colocá-los em. 1228 01:00:23,860 --> 01:00:26,800 Portanto, não são não são those-- você olhar para eles 1229 01:00:26,800 --> 01:00:28,544 como elementos separados, e não como o todo? 1230 01:00:28,544 --> 01:00:29,210 ANDI Peng: Sim. 1231 01:00:29,210 --> 01:00:32,020 Então, o que está acontecendo é que você, basicamente, 1232 01:00:32,020 --> 01:00:33,650 está criando uma nova matriz. 1233 01:00:33,650 --> 01:00:36,690 Então você sabe que, aqui, eu tenho duas matrizes de tamanho 3, certo? 1234 01:00:36,690 --> 01:00:39,600 Então, você sabe que a minha matriz classificada precisa de ter seis elementos. 1235 01:00:39,600 --> 01:00:42,270 Então você acabou de criar uma nova quantidade de memória. 1236 01:00:42,270 --> 01:00:44,270 Então você é tipo como de sendo um desperdício de memória, 1237 01:00:44,270 --> 01:00:46,186 mas isso não importa porque é tão pequeno. 1238 01:00:46,186 --> 01:00:48,590 Então você olha para o 1 e você olha para o 2. 1239 01:00:48,590 --> 01:00:50,770 E você sabe que o 1 é inferior a 2. 1240 01:00:50,770 --> 01:00:53,840 Então você sabe que um deve ir o início de tudo isso. 1241 01:00:53,840 --> 01:00:55,850 >> Você não precisa mesmo de olhar para a 3 e 5 a. 1242 01:00:55,850 --> 01:00:57,400 Então você sabe que um vai lá. 1243 01:00:57,400 --> 01:00:59,300 Então você basicamente cortar a 1. 1244 01:00:59,300 --> 01:01:00,370 É, tipo, morto para nós. 1245 01:01:00,370 --> 01:01:03,690 Então só temos 2, 3, 5, e, em seguida, 4 e 6. 1246 01:01:03,690 --> 01:01:06,270 E então você sabe que, você comparar a 4 e a 2, 1247 01:01:06,270 --> 01:01:07,560 oh, o 2 deve ir para lá. 1248 01:01:07,560 --> 01:01:09,685 Então você plop a 2 para baixo, você cortá-lo. 1249 01:01:09,685 --> 01:01:12,060 Então, então você apenas tem a 3 e o 5 no 4 e 6 a. 1250 01:01:12,060 --> 01:01:14,650 E você continua cortando-off até que você colocá-los na matriz. 1251 01:01:14,650 --> 01:01:17,110 >> AUDIÊNCIA: Então você é apenas sempre comparando o [inaudível]? 1252 01:01:17,110 --> 01:01:17,710 >> ANDI Peng: Exatamente. 1253 01:01:17,710 --> 01:01:19,590 Então, nesse sentido, você é apenas comparando, essencialmente, 1254 01:01:19,590 --> 01:01:21,240 um número contra o outro número. 1255 01:01:21,240 --> 01:01:22,990 E porque você sabe que está classificada, você 1256 01:01:22,990 --> 01:01:24,350 não tem que olhar através de todos os números. 1257 01:01:24,350 --> 01:01:25,870 Você apenas tem que olhar para o primeiro. 1258 01:01:25,870 --> 01:01:27,582 E então você pode apenas plop -los para baixo, porque você sabe 1259 01:01:27,582 --> 01:01:29,640 eles pertencem onde eles precisam de pertencer. 1260 01:01:29,640 --> 01:01:31,030 Sim. 1261 01:01:31,030 --> 01:01:32,920 Boa pergunta. 1262 01:01:32,920 --> 01:01:35,290 >> E, em seguida, se algum de vocês são um pouco ambicioso, 1263 01:01:35,290 --> 01:01:38,660 sinta-se livre para olhar para este código. 1264 01:01:38,660 --> 01:01:40,680 Esta é realmente a implementação física 1265 01:01:40,680 --> 01:01:42,150 de como iria escrever merge sort. 1266 01:01:42,150 --> 01:01:44,070 E você pode ver, é muito curto. 1267 01:01:44,070 --> 01:01:46,310 Mas as idéias por trás que são bastante complexas. 1268 01:01:46,310 --> 01:01:50,865 Então, se você sentir vontade de desenhar isso em sua lição de casa esta noite, sinta-se livre para. 1269 01:01:50,865 --> 01:01:54,050 1270 01:01:54,050 --> 01:01:54,740 >> ESTÁ BEM. 1271 01:01:54,740 --> 01:01:58,070 Então David também passou por isso na palestra. 1272 01:01:58,070 --> 01:02:00,660 O que é o melhor caso tempos de execução, piores tempos de execução de caso, 1273 01:02:00,660 --> 01:02:05,680 e os tempos de execução esperadas de merge sort? 1274 01:02:05,680 --> 01:02:07,260 Um par de segundos para pensar. 1275 01:02:07,260 --> 01:02:11,198 Isso é muito difícil, mas o tipo de intuitiva se você pensar sobre isso. 1276 01:02:11,198 --> 01:02:20,090 1277 01:02:20,090 --> 01:02:23,054 Tudo certo. 1278 01:02:23,054 --> 01:02:25,269 >> AUDIÊNCIA: É o pior caso n log n? 1279 01:02:25,269 --> 01:02:26,060 ANDI Peng: Exatamente. 1280 01:02:26,060 --> 01:02:29,380 E por que é n log n. 1281 01:02:29,380 --> 01:02:32,230 >> AUDIÊNCIA: Não é porque torna-se mais rapidamente de forma exponencial, 1282 01:02:32,230 --> 01:02:35,390 por isso é como uma função do que em vez de simplesmente sendo n 1283 01:02:35,390 --> 01:02:37,529 quadrado ou algo assim? 1284 01:02:37,529 --> 01:02:38,320 ANDI Peng: Exatamente. 1285 01:02:38,320 --> 01:02:40,750 Assim, a razão pela qual o runtime sobre isso é log n 1286 01:02:40,750 --> 01:02:44,310 n é porque-- o que é você fazendo em todos estes passos de? 1287 01:02:44,310 --> 01:02:46,190 Você só está cortando-o ao meio, certo? 1288 01:02:46,190 --> 01:02:48,750 E assim, quando estamos fazendo o log, tudo o que ele está fazendo 1289 01:02:48,750 --> 01:02:53,150 está dividindo um problema no meio, ao meio, na metade, em mais metades. 1290 01:02:53,150 --> 01:02:56,430 E, nesse sentido, você pode tipo de eliminar o modelo linear 1291 01:02:56,430 --> 01:02:57,510 que temos vindo a utilizar. 1292 01:02:57,510 --> 01:03:00,254 Porque quando você chop coisas pela metade, é um log. 1293 01:03:00,254 --> 01:03:02,420 Isso é apenas a matemática maneira de representá-lo. 1294 01:03:02,420 --> 01:03:06,310 >> E então, finalmente, no final, você é apenas fazendo uma última passagem 1295 01:03:06,310 --> 01:03:07,930 para colocar todos eles em ordem, certo? 1296 01:03:07,930 --> 01:03:10,330 E por isso, se você só tem que verificar uma coisa, que é n. 1297 01:03:10,330 --> 01:03:13,420 E então você está tipo de multiplicando os dois em conjunto. 1298 01:03:13,420 --> 01:03:17,660 Então, é como você tem que Final vá para n para baixo aqui com um registro de n 1299 01:03:17,660 --> 01:03:18,390 aqui em cima. 1300 01:03:18,390 --> 01:03:21,060 E se você multiplicar eles, que é n log n. 1301 01:03:21,060 --> 01:03:26,100 >> E assim o melhor eo pior caso caso e espera são todos n log n. 1302 01:03:26,100 --> 01:03:27,943 É também como um outro tipo. 1303 01:03:27,943 --> 01:03:30,090 É como espécie seleção no sentido de que ele 1304 01:03:30,090 --> 01:03:32,131 Não importa o que o seu lista é, ele só vai 1305 01:03:32,131 --> 01:03:34,801 para fazer a mesma coisa a cada momento. 1306 01:03:34,801 --> 01:03:35,300 ESTÁ BEM. 1307 01:03:35,300 --> 01:03:39,950 Então, como vocês podem ver, mesmo que os tipos que temos ido through-- n 1308 01:03:39,950 --> 01:03:41,660 quadrado, não é muito eficiente. 1309 01:03:41,660 --> 01:03:47,060 E mesmo esse log n n é não é o mais eficiente. 1310 01:03:47,060 --> 01:03:49,720 Se vocês são curiosos, há mecanismos de ordenação 1311 01:03:49,720 --> 01:03:54,310 que são tão eficientes que eles são quase essencialmente plana em tempo de execução. 1312 01:03:54,310 --> 01:03:55,420 >> Você tem um pouco de log n. 1313 01:03:55,420 --> 01:03:58,190 Você tem alguma log log n de. 1314 01:03:58,190 --> 01:04:00,330 Nós não toque sobre eles nesta classe agora. 1315 01:04:00,330 --> 01:04:02,663 Mas se vocês estão curiosos, sinta-se livre para o Google, o que é 1316 01:04:02,663 --> 01:04:04,392 os mecanismos de triagem mais eficientes. 1317 01:04:04,392 --> 01:04:06,350 Eu não sei, existem alguns realmente engraçado, 1318 01:04:06,350 --> 01:04:09,860 como-- há alguns realmente mais engraçados que as pessoas fazem. 1319 01:04:09,860 --> 01:04:12,210 E você quer saber como eles nunca pensei nisso. 1320 01:04:12,210 --> 01:04:15,730 Então, o Google, se você tem alguma reposição tempo, em, quais são algumas maneiras engraçadas 1321 01:04:15,730 --> 01:04:17,730 que bem como pessoas-- eficientes pessoas ways-- 1322 01:04:17,730 --> 01:04:20,371 têm sido capazes de implementar os tipos. 1323 01:04:20,371 --> 01:04:20,870 ESTÁ BEM. 1324 01:04:20,870 --> 01:04:22,880 E aqui está um pouco gráfico útil. 1325 01:04:22,880 --> 01:04:26,850 Eu sei que todos vocês, antes que teste 0, estará em seu quarto, provavelmente, tentando 1326 01:04:26,850 --> 01:04:27,960 para memorizar que. 1327 01:04:27,960 --> 01:04:30,940 Então, isso é bom lá para vocês. 1328 01:04:30,940 --> 01:04:37,120 Só não se esqueça a lógica que made-- por que esses números estavam ocorrendo. 1329 01:04:37,120 --> 01:04:39,870 Se você está sempre perdido, basta fazer se você sabe o que os tipos são. 1330 01:04:39,870 --> 01:04:40,820 E você pode executar através los em sua mente 1331 01:04:40,820 --> 01:04:42,903 para descobrir por que os respostas são essas respostas. 1332 01:04:42,903 --> 01:04:46,250 1333 01:04:46,250 --> 01:04:47,600 >> Tudo certo. 1334 01:04:47,600 --> 01:04:49,680 Então, nós estamos indo para mover em, finalmente, para a pesquisa. 1335 01:04:49,680 --> 01:04:51,638 Porque, como aqueles de vocês que leram o pset, 1336 01:04:51,638 --> 01:04:55,175 pesquisa também faz parte da problema desta semana define. 1337 01:04:55,175 --> 01:04:57,300 Você será solicitado para implementar dois tipos de pesquisas. 1338 01:04:57,300 --> 01:05:00,070 Um deles é uma pesquisa linear e é uma pesquisa binária. 1339 01:05:00,070 --> 01:05:01,760 >> Assim, a busca linear é bastante fácil. 1340 01:05:01,760 --> 01:05:04,070 Você só quer procurar elemento de uma lista para ver se você obtê-lo. 1341 01:05:04,070 --> 01:05:05,444 Você apenas tem para percorrer. 1342 01:05:05,444 --> 01:05:08,170 E se ele é igual a alguma coisa, você pode simplesmente devolvê-lo, certo? 1343 01:05:08,170 --> 01:05:10,890 Mas o que nós somos mais interessado em falar sobre 1344 01:05:10,890 --> 01:05:14,550 é a busca binária, à direita, que é a dividir e conquistar mecanismo que 1345 01:05:14,550 --> 01:05:18,190 David estava demonstrando em conferência. 1346 01:05:18,190 --> 01:05:20,810 >> Lembre-se o exemplo do livro de telefone que ele continua trazendo à tona, 1347 01:05:20,810 --> 01:05:23,960 o que ele meio que se esforçou um pouco sobre o ano passado, 1348 01:05:23,960 --> 01:05:27,530 onde você dividir o problema pela metade, ao meio, ao meio, uma e outra vez, 1349 01:05:27,530 --> 01:05:30,730 até encontrar o que você está procurando? 1350 01:05:30,730 --> 01:05:33,727 E você tem o runtime do que bem. 1351 01:05:33,727 --> 01:05:35,810 E você pode ver, é significativamente mais eficiente 1352 01:05:35,810 --> 01:05:39,080 do que qualquer outro tipo de pesquisa. 1353 01:05:39,080 --> 01:05:41,880 >> Assim, a maneira que nós iria sobre execução de uma pesquisa binária 1354 01:05:41,880 --> 01:05:46,510 é, se nós tivéssemos uma matriz, índice de 0 a 6, sete elementos, 1355 01:05:46,510 --> 01:05:49,790 podemos olhar no meio, direita-- desculpe, se nossa pergunta first-- 1356 01:05:49,790 --> 01:05:53,840 se queremos fazer a pergunta de, faz a matriz conter o elemento de 7, 1357 01:05:53,840 --> 01:05:56,840 Obviamente, sendo os seres humanos, e tendo tais uma pequena variedade, é fácil para nós 1358 01:05:56,840 --> 01:05:58,210 para dizer sim. 1359 01:05:58,210 --> 01:06:05,750 Mas a maneira de implementar um binário busca seria a de olhar no meio. 1360 01:06:05,750 --> 01:06:08,020 >> Sabemos que o índice 3 é no meio, porque nós 1361 01:06:08,020 --> 01:06:09,270 sei que há sete elementos. 1362 01:06:09,270 --> 01:06:10,670 O 7 dividido por 2? 1363 01:06:10,670 --> 01:06:12,850 Você pode cortar esse extra 1. 1364 01:06:12,850 --> 01:06:14,850 Você tem três no meio. 1365 01:06:14,850 --> 01:06:17,590 Então é matriz de 3 igual a 7? 1366 01:06:17,590 --> 01:06:18,900 Não está certo? 1367 01:06:18,900 --> 01:06:21,050 Mas podemos fazer um par de cheques. 1368 01:06:21,050 --> 01:06:25,380 É gama de 3 a 7 ou menos 3 é de matriz maior do que 7? 1369 01:06:25,380 --> 01:06:27,240 >> E nós sabemos que ele é inferior a 7. 1370 01:06:27,240 --> 01:06:30,259 Então, nós sabemos que, oh, ela deve não estar na metade esquerda. 1371 01:06:30,259 --> 01:06:32,300 Sabemos que ele deve ser na metade direita, certo? 1372 01:06:32,300 --> 01:06:34,662 Assim, podemos apenas cortar metade do array. 1373 01:06:34,662 --> 01:06:36,370 Nós nem sequer têm de mais olhar para ela. 1374 01:06:36,370 --> 01:06:38,711 Porque nós sabemos que metade do nosso problema-- 1375 01:06:38,711 --> 01:06:41,210 nós sabemos que a resposta está em a metade direita do nosso problema. 1376 01:06:41,210 --> 01:06:42,580 Portanto, basta olhar para isso agora. 1377 01:06:42,580 --> 01:06:44,860 >> Então, agora olhamos para o meio do que restou. 1378 01:06:44,860 --> 01:06:46,880 Esse índice 5. 1379 01:06:46,880 --> 01:06:50,200 Nós fazemos a mesma verificação novamente e vemos que ele é menor. 1380 01:06:50,200 --> 01:06:52,050 Então, nós olhamos para a esquerda do que isso. 1381 01:06:52,050 --> 01:06:53,430 E então vemos que cheque. 1382 01:06:53,430 --> 01:06:57,600 É o valor da matriz em índice 4 igual a 7? 1383 01:06:57,600 --> 01:06:58,260 Isto é. 1384 01:06:58,260 --> 01:07:03,580 Assim, podemos retornar verdadeiro, porque encontramos o valor em nossa lista. 1385 01:07:03,580 --> 01:07:06,738 Será que a maneira que eu atravessei que faz sentido para todo mundo? 1386 01:07:06,738 --> 01:07:08,760 ESTÁ BEM. 1387 01:07:08,760 --> 01:07:11,670 Eu vou dar a vocês talvez, como, três, quatro minutos para descobrir 1388 01:07:11,670 --> 01:07:13,270 Pseudocódigo como este no. 1389 01:07:13,270 --> 01:07:18,070 >> Então imagine eu lhe pedi para escrever uma chamado função search () que retornaram 1390 01:07:18,070 --> 01:07:20,640 um valor, um valor booleano, isso era verdade ou false-- como, 1391 01:07:20,640 --> 01:07:22,970 verdadeiro se você encontrou a valor, falso se você não fez. 1392 01:07:22,970 --> 01:07:25,230 E então você estava passou no valor você 1393 01:07:25,230 --> 01:07:28,410 estava procurando em valores, que é o array-- oh, eu definitivamente colocá 1394 01:07:28,410 --> 01:07:29,410 que no lugar errado. 1395 01:07:29,410 --> 01:07:29,580 ESTÁ BEM. 1396 01:07:29,580 --> 01:07:31,829 De qualquer forma, que deve ter foi para a direita de valores. 1397 01:07:31,829 --> 01:07:36,280 E, em seguida, int n é o número de elementos dessa matriz. 1398 01:07:36,280 --> 01:07:39,430 Como você iria sobre a tentativa Pseudocódigo para esse problema em? 1399 01:07:39,430 --> 01:07:41,630 Eu vou dar a vocês como três minutos para fazer isso. 1400 01:07:41,630 --> 01:08:00,137 1401 01:08:00,137 --> 01:08:02,595 Não, eu acho que há only-- sim, há um aqui em cima. 1402 01:08:02,595 --> 01:08:03,261 AUDIÊNCIA: Posso? 1403 01:08:03,261 --> 01:08:04,388 ANDI Peng: Sim, eu tenho você. 1404 01:08:04,388 --> 01:08:09,410 1405 01:08:09,410 --> 01:08:11,050 É que trabalhar? 1406 01:08:11,050 --> 01:08:12,290 OK legal. 1407 01:08:12,290 --> 01:10:43,590 1408 01:10:43,590 --> 01:10:44,720 >> ESTÁ BEM. 1409 01:10:44,720 --> 01:10:47,630 Todos os caras certos, nós somos vai controlá-lo em. 1410 01:10:47,630 --> 01:10:49,730 ESTÁ BEM. 1411 01:10:49,730 --> 01:10:54,020 Então assumir que temos esta linda pouco matriz com valores de n na mesma. 1412 01:10:54,020 --> 01:10:55,170 Eu não desenhar as linhas. 1413 01:10:55,170 --> 01:10:58,649 Mas como é que nós vamos sobre tentando escrever isso? 1414 01:10:58,649 --> 01:11:00,440 Alguém quer dá-me a primeira linha? 1415 01:11:00,440 --> 01:11:02,814 Se você quiser me dar o primeira linha deste pseudocódigo. 1416 01:11:02,814 --> 01:11:06,563 1417 01:11:06,563 --> 01:11:08,430 >> AUDIÊNCIA: [inaudível] 1418 01:11:08,430 --> 01:11:10,138 AUDIÊNCIA: Você iria querer iterar through-- 1419 01:11:10,138 --> 01:11:11,094 AUDIÊNCIA: Só mais um para loop? 1420 01:11:11,094 --> 01:11:11,760 AUDIÊNCIA --para. 1421 01:11:11,760 --> 01:11:15,880 1422 01:11:15,880 --> 01:11:17,780 >> ANDI Peng: Então, este é um pouco complicado. 1423 01:11:17,780 --> 01:11:23,130 Pense about-- você quer para continuar correndo esse loop 1424 01:11:23,130 --> 01:11:27,950 uma e outra vez até quando? 1425 01:11:27,950 --> 01:11:30,819 >> AUDIÊNCIA: Até o [inaudível] valor que é igual ao valor. 1426 01:11:30,819 --> 01:11:31,610 ANDI Peng: Exatamente. 1427 01:11:31,610 --> 01:11:33,900 Então você pode realmente apenas write-- podemos até mesmo simplificá-lo mais. 1428 01:11:33,900 --> 01:11:35,630 Nós podemos apenas fazer um loop while, certo? 1429 01:11:35,630 --> 01:11:39,380 Então você pode apenas ter loop-- sabemos que é um tempo. 1430 01:11:39,380 --> 01:11:42,850 Mas, por agora, eu vou para dizer "laço" - através do que? 1431 01:11:42,850 --> 01:11:46,640 Laço que é until-- nossa condição terminando? 1432 01:11:46,640 --> 01:11:47,510 Acho que ouvi-lo. 1433 01:11:47,510 --> 01:11:48,530 Ouvi alguém dizer isso. 1434 01:11:48,530 --> 01:11:51,255 >> Audiência: Valores iguala meio. 1435 01:11:51,255 --> 01:11:52,255 ANDI Peng: Diga isso de novo. 1436 01:11:52,255 --> 01:11:54,470 AUDIÊNCIA: Ou, até o valor que você está procurando 1437 01:11:54,470 --> 01:11:58,470 para é igual ao valor médio. 1438 01:11:58,470 --> 01:12:00,280 >> ANDI Peng: O que se ele não está lá? 1439 01:12:00,280 --> 01:12:03,113 E se o valor que você está pesquisando para não é realmente nessa matriz? 1440 01:12:03,113 --> 01:12:05,890 AUDIÊNCIA: Você retorna 1. 1441 01:12:05,890 --> 01:12:08,850 >> ANDI Peng: Mas o que queremos loop até que se nós tem uma condição? 1442 01:12:08,850 --> 01:12:09,350 Sim. 1443 01:12:09,350 --> 01:12:11,239 >> AUDIÊNCIA: Até que haja apenas um valor? 1444 01:12:11,239 --> 01:12:13,530 ANDI Peng: Você pode fazer um loop until-- para que você saiba que você é 1445 01:12:13,530 --> 01:12:15,714 vai ter um valor máximo, certo? 1446 01:12:15,714 --> 01:12:18,130 E você sabe que você está indo para ter um valor min, certo? 1447 01:12:18,130 --> 01:12:20,379 Porque também, isso é algo Eu esqueci de dizer antes, 1448 01:12:20,379 --> 01:12:22,640 que algo que é crítica sobre busca binária 1449 01:12:22,640 --> 01:12:24,182 é que sua matriz já está classificado. 1450 01:12:24,182 --> 01:12:26,973 Porque não há nenhuma maneira de fazê- isso se eles são apenas valores aleatórios. 1451 01:12:26,973 --> 01:12:29,190 Você não sabe se é maior que o outro, certo? 1452 01:12:29,190 --> 01:12:32,720 >> Então, você sabe que o seu máximo e seus mins está aqui, certo? 1453 01:12:32,720 --> 01:12:35,590 Se você vai estar se adaptando seu máximo em seus minutos e os mid-- 1454 01:12:35,590 --> 01:12:38,470 vamos assumir o seu valor médio é aqui-- direita 1455 01:12:38,470 --> 01:12:43,910 você está indo para, basicamente, loop até sua mínima é de 1456 01:12:43,910 --> 01:12:47,510 sobre o mesmo como seu máximo, à direita ou se o seu máximo não é o mesmo que o seu min. 1457 01:12:47,510 --> 01:12:48,040 Certo? 1458 01:12:48,040 --> 01:12:51,340 Porque quando isso acontece, você sabe que você, eventualmente, acertar o mesmo valor. 1459 01:12:51,340 --> 01:12:59,135 Então você quer fazer um loop até que o seu min é inferior ou igual a-- oops, 1460 01:12:59,135 --> 01:13:01,510 não menos do que ou igual a, a outra maneira é circundar-- max. 1461 01:13:01,510 --> 01:13:15,110 1462 01:13:15,110 --> 01:13:16,160 >> Será que isso faz sentido? 1463 01:13:16,160 --> 01:13:18,810 I levou algumas tentativas para obter esse direito. 1464 01:13:18,810 --> 01:13:21,869 Mas loop até que o seu valor máximo é essencialmente quase menos 1465 01:13:21,869 --> 01:13:23,410 ou igual a seu mínimo, certo? 1466 01:13:23,410 --> 01:13:25,201 Isso é quando você sabe que você já convergiram. 1467 01:13:25,201 --> 01:13:29,290 AUDIÊNCIA: Quando seria o seu máximo valor pode ser inferior ao mínimo? 1468 01:13:29,290 --> 01:13:31,040 ANDI Peng: Se você mantiver ajustando-o, o que 1469 01:13:31,040 --> 01:13:32,380 é o que nós estamos indo estar fazendo neste. 1470 01:13:32,380 --> 01:13:33,460 Isso faz sentido? 1471 01:13:33,460 --> 01:13:35,750 Mínimo e máximo são apenas inteiros que são, provavelmente, 1472 01:13:35,750 --> 01:13:39,260 vai querer criar para manter o controle de onde nós estamos olhando. 1473 01:13:39,260 --> 01:13:41,790 Como a matriz existe independentemente do que estamos fazendo. 1474 01:13:41,790 --> 01:13:45,030 Como, nós não estamos fisicamente decepar a matriz, certo? 1475 01:13:45,030 --> 01:13:47,261 Estamos apenas ajustando onde nós estamos olhando. 1476 01:13:47,261 --> 01:13:48,136 Isso faz sentido? 1477 01:13:48,136 --> 01:13:48,472 >> AUDIÊNCIA: É. 1478 01:13:48,472 --> 01:13:49,110 >> ANDI Peng: OK. 1479 01:13:49,110 --> 01:13:57,090 Então, se essa é a condição para o nosso loop, o que queremos dentro deste loop? 1480 01:13:57,090 --> 01:13:58,700 O que vamos estar querendo fazer? 1481 01:13:58,700 --> 01:14:02,390 Então, agora, nós temos um máximo e um mínimo, direito, 1482 01:14:02,390 --> 01:14:04,962 Provavelmente criou-se aqui em algum lugar. 1483 01:14:04,962 --> 01:14:07,170 Nós vamos provavelmente quer para encontrar um meio, certo? 1484 01:14:07,170 --> 01:14:08,450 Como é que vai ser capaz de encontrar o meio? 1485 01:14:08,450 --> 01:14:09,491 Qual é a mathematical-- 1486 01:14:09,491 --> 01:14:11,079 AUDIÊNCIA: Max além min divididos por dois. 1487 01:14:11,079 --> 01:14:11,870 ANDI Peng: Exatamente. 1488 01:14:11,870 --> 01:14:20,300 1489 01:14:20,300 --> 01:14:21,620 Isso faz sentido? 1490 01:14:21,620 --> 01:14:25,780 E que vocês ver porque nós não apenas use-- por que fizemos isso 1491 01:14:25,780 --> 01:14:27,850 em vez de fazer apenas n dividido por 2? 1492 01:14:27,850 --> 01:14:30,310 É porque n é um valor que vai ficar na mesma. 1493 01:14:30,310 --> 01:14:30,979 Certo? 1494 01:14:30,979 --> 01:14:34,020 Mas porque nós ajustamos nossa mínimo e valores máximos, eles vão mudar. 1495 01:14:34,020 --> 01:14:36,040 E, como resultado, o nosso meio vai mudar também. 1496 01:14:36,040 --> 01:14:37,873 Então é por isso que queremos para fazer isso aqui mesmo. 1497 01:14:37,873 --> 01:14:38,510 ESTÁ BEM. 1498 01:14:38,510 --> 01:14:41,600 >> E então, agora que nós encontramos our-- sim. 1499 01:14:41,600 --> 01:14:44,270 >> AUDIÊNCIA: Apenas um question-- rápida quando você diz min e max, 1500 01:14:44,270 --> 01:14:46,410 assumindo que estamos ele já está classificado? 1501 01:14:46,410 --> 01:14:48,400 >> ANDI Peng: Sim, isso é realmente uma condição prévia para uma busca binária, 1502 01:14:48,400 --> 01:14:49,816 que você tem que saber que está classificada. 1503 01:14:49,816 --> 01:14:53,660 É por isso que tipo, você escreve no seu conjunto de problemas antes de sua busca binária. 1504 01:14:53,660 --> 01:14:55,910 ESTÁ BEM. 1505 01:14:55,910 --> 01:14:58,876 Portanto, agora que sabemos onde nosso ponto médio é, o que você quer fazer aqui? 1506 01:14:58,876 --> 01:15:01,789 1507 01:15:01,789 --> 01:15:04,319 >> AUDIÊNCIA: Queremos comparar que para o outro. 1508 01:15:04,319 --> 01:15:05,110 ANDI Peng: Exatamente. 1509 01:15:05,110 --> 01:15:12,280 Então você está indo para comparar meados de valor, certo? 1510 01:15:12,280 --> 01:15:14,900 1511 01:15:14,900 --> 01:15:18,670 E o que dizer isso nós quando se comparam? 1512 01:15:18,670 --> 01:15:22,226 O que nós queremos fazer depois? 1513 01:15:22,226 --> 01:15:25,389 >> AUDIÊNCIA: Se o valor for maior de meados dos anos, queremos cortá-lo. 1514 01:15:25,389 --> 01:15:26,180 ANDI Peng: Exatamente. 1515 01:15:26,180 --> 01:15:33,940 Então, se o valor for maior de meados dos anos, estamos 1516 01:15:33,940 --> 01:15:36,550 vai querer alterar essas Maxes mínimo e, certo? 1517 01:15:36,550 --> 01:15:38,980 O que nós queremos mudar? 1518 01:15:38,980 --> 01:15:42,145 Então, se nós sabemos o valor está em algum lugar aqui, o que você que mudar? 1519 01:15:42,145 --> 01:15:44,758 Nós queremos mudar a nossa mínimo a ser mid, certo? 1520 01:15:44,758 --> 01:15:49,420 1521 01:15:49,420 --> 01:15:54,292 E então outra coisa, se é neste metade, o que nós queremos mudar? 1522 01:15:54,292 --> 01:15:55,306 >> AUDIÊNCIA: O seu máximo. 1523 01:15:55,306 --> 01:15:55,972 ANDI Peng: Sim. 1524 01:15:55,972 --> 01:16:02,597 1525 01:16:02,597 --> 01:16:04,680 E então você só vai para manter looping, certo? 1526 01:16:04,680 --> 01:16:08,920 Porque agora, depois de uma iteração através, você tem um máximo aqui. 1527 01:16:08,920 --> 01:16:10,760 E então você pode recalcular um mid. 1528 01:16:10,760 --> 01:16:11,990 E então você pode comparar. 1529 01:16:11,990 --> 01:16:14,766 E você está indo para continuar até os minutos e as Maxes 1530 01:16:14,766 --> 01:16:15,890 ter essencialmente convergentes. 1531 01:16:15,890 --> 01:16:17,890 E isso é quando você sabe que você bateu o fim de tudo. 1532 01:16:17,890 --> 01:16:20,280 E quer você encontrou- ou você não tem nesse momento. 1533 01:16:20,280 --> 01:16:23,170 >> Será que isto faz sentido para todo mundo? 1534 01:16:23,170 --> 01:16:26,020 1535 01:16:26,020 --> 01:16:26,770 ESTÁ BEM. 1536 01:16:26,770 --> 01:16:27,900 Isso é muito importante, porque você vai ter 1537 01:16:27,900 --> 01:16:29,760 para escrever isso em seu código de hoje à noite. 1538 01:16:29,760 --> 01:16:32,660 Mas vocês têm uma boa sensação de que você deveria estar fazendo, 1539 01:16:32,660 --> 01:16:34,051 qual é bom. 1540 01:16:34,051 --> 01:16:34,550 ESTÁ BEM. 1541 01:16:34,550 --> 01:16:38,840 Então, nós temos cerca de sete minutos seção esquerda. 1542 01:16:38,840 --> 01:16:43,170 Então, nós estamos indo falar sobre este pset que nós estaremos fazendo. 1543 01:16:43,170 --> 01:16:46,410 Assim, o pset é dividido em duas metades. 1544 01:16:46,410 --> 01:16:50,230 A primeira metade envolve a implementação de um find 1545 01:16:50,230 --> 01:16:54,210 no qual você escreve uma busca linear, um busca binária, e um algoritmo de ordenação. 1546 01:16:54,210 --> 01:16:56,690 >> Portanto, este é o primeiro tempo num pset onde 1547 01:16:56,690 --> 01:17:00,050 estaremos dando a vocês o que é chamado código de distribuição, que é o código 1548 01:17:00,050 --> 01:17:02,740 que temos pré-escrito, mas apenas deixou algumas peças off 1549 01:17:02,740 --> 01:17:04,635 para que você terminar de escrever. 1550 01:17:04,635 --> 01:17:07,510 Então vocês, quando você olha para esta código, você pode ficar realmente assustado. 1551 01:17:07,510 --> 01:17:08,630 Se você está apenas como, ahh, eu não sei o que está fazendo, 1552 01:17:08,630 --> 01:17:11,670 Eu não sei, como, que parece tão complicado, ahh, relaxar. 1553 01:17:11,670 --> 01:17:12,170 Está certo. 1554 01:17:12,170 --> 01:17:12,930 Leia o spec. 1555 01:17:12,930 --> 01:17:16,920 A especificação irá explicar-lhe exatamente o que todos esses programas estão fazendo. 1556 01:17:16,920 --> 01:17:20,560 >> Por exemplo, é um programa generate.c que virá com sua pset. 1557 01:17:20,560 --> 01:17:24,060 Você realmente não tem que tocá-lo, mas você deve entender o que está fazendo. 1558 01:17:24,060 --> 01:17:28,550 E generate.c, tudo o que está fazendo é quer gerar números aleatórios 1559 01:17:28,550 --> 01:17:32,400 ou você pode dar-lhe uma semente, como um número preestabelecido que leva, 1560 01:17:32,400 --> 01:17:34,140 e gera mais números. 1561 01:17:34,140 --> 01:17:37,170 Portanto, há uma maneira específica para implementar no qual generate.c 1562 01:17:37,170 --> 01:17:42,760 você pode apenas fazer um monte de números para você testar seus outros métodos diante. 1563 01:17:42,760 --> 01:17:45,900 >> Então, se você queria, para exemplo, testar a sua descoberta, 1564 01:17:45,900 --> 01:17:48,970 você iria querer correr generate.c, gerar um monte de números, 1565 01:17:48,970 --> 01:17:50,880 e em seguida, executar a função de ajudantes. 1566 01:17:50,880 --> 01:17:53,930 Sua função ajudantes é o lugar onde você está realmente escrever fisicamente código. 1567 01:17:53,930 --> 01:17:59,330 E pensar ajudantes como um arquivo de biblioteca você está escrevendo que find está chamando. 1568 01:17:59,330 --> 01:18:02,950 E assim dentro helpers.c, você vai fazer pesquisa e classificação. 1569 01:18:02,950 --> 01:18:06,500 >> E então você vai, essencialmente, apenas colocá-los todos juntos. 1570 01:18:06,500 --> 01:18:10,350 A especificação irá dizer-lhe como colocar isso na linha de comando. 1571 01:18:10,350 --> 01:18:14,880 E você vai ser capaz de testar se ou não o seu tipo e de pesquisa estão trabalhando. 1572 01:18:14,880 --> 01:18:15,870 Legal. 1573 01:18:15,870 --> 01:18:18,720 Alguém já começou e problemas encontrados ou perguntas 1574 01:18:18,720 --> 01:18:20,520 eles têm agora com isso? 1575 01:18:20,520 --> 01:18:21,020 ESTÁ BEM. 1576 01:18:21,020 --> 01:18:21,476 >> AUDIÊNCIA: Espere. 1577 01:18:21,476 --> 01:18:21,932 Eu tenho uma pergunta. 1578 01:18:21,932 --> 01:18:22,844 >> ANDI Peng: Sim. 1579 01:18:22,844 --> 01:18:28,390 >> AUDIÊNCIA: Então eu comecei a fazer a busca linear em helpers.c 1580 01:18:28,390 --> 01:18:29,670 e não foi realmente funcionando. 1581 01:18:29,670 --> 01:18:34,590 Mas, em seguida, mais tarde, descobri que acabamos tem que excluí-lo e fazer busca binária. 1582 01:18:34,590 --> 01:18:36,991 Então, não importa se ele não funcionar? 1583 01:18:36,991 --> 01:18:39,700 1584 01:18:39,700 --> 01:18:41,510 >> ANDI Peng: resposta curta é não. 1585 01:18:41,510 --> 01:18:42,642 Mas já que estamos não-- 1586 01:18:42,642 --> 01:18:44,350 AUDIÊNCIA: Mas ninguém de realmente verificar. 1587 01:18:44,350 --> 01:18:46,058 ANDI Peng: Nós nunca somos vai ver isso. 1588 01:18:46,058 --> 01:18:49,590 Mas você provavelmente vai querer fazer Certifique-se a sua pesquisa está funcionando. 1589 01:18:49,590 --> 01:18:51,700 Porque se seu linear Pesquisa não funciona, 1590 01:18:51,700 --> 01:18:54,410 então as chances são o seu binário pesquisa não vai funcionar tão bem. 1591 01:18:54,410 --> 01:18:56,646 Porque você tem semelhante lógica em ambas. 1592 01:18:56,646 --> 01:18:58,020 E não, isso realmente não importa. 1593 01:18:58,020 --> 01:19:01,300 Então, os únicos que você vai virar em são uma espécie e busca binária. 1594 01:19:01,300 --> 01:19:02,490 Sim. 1595 01:19:02,490 --> 01:19:06,610 >> E também, um monte de crianças foram tentar compilar helpers.c. 1596 01:19:06,610 --> 01:19:09,550 Você não está realmente permitido para fazer isso, porque helpers.c 1597 01:19:09,550 --> 01:19:11,200 não tem uma função principal. 1598 01:19:11,200 --> 01:19:13,550 E assim você só deve ser realmente compilando 1599 01:19:13,550 --> 01:19:18,670 gerar e encontrar, porque encontrar chamadas helpers.c e as funções dentro dela. 1600 01:19:18,670 --> 01:19:20,790 Assim que torna a depuração uma dor na bunda. 1601 01:19:20,790 --> 01:19:22,422 Mas isso é o que temos que fazer. 1602 01:19:22,422 --> 01:19:23,880 AUDIÊNCIA: Você acabou de fazer tudo, certo? 1603 01:19:23,880 --> 01:19:27,290 ANDI Peng: você pode apenas fazer tudo bem, sim. 1604 01:19:27,290 --> 01:19:28,060 ESTÁ BEM. 1605 01:19:28,060 --> 01:19:32,570 Então é isso em termos do que o pset está pedindo que todos vocês façam. 1606 01:19:32,570 --> 01:19:35,160 Se você tiver alguma dúvida, sinta- livre para me perguntar depois seção. 1607 01:19:35,160 --> 01:19:37,580 Eu vou estar aqui para, como, 20 minutos. 1608 01:19:37,580 --> 01:19:40,500 >> E sim, os PSet de não é realmente tão ruim assim. 1609 01:19:40,500 --> 01:19:41,680 Vocês devem estar OK. 1610 01:19:41,680 --> 01:19:43,250 Estes, basta seguir as orientações. 1611 01:19:43,250 --> 01:19:47,840 Tipo de ter um senso de, logicamente, o que deveria estar acontecendo e você vai ficar bem. 1612 01:19:47,840 --> 01:19:48,690 Não fique muito assustado. 1613 01:19:48,690 --> 01:19:50,220 Há um monte de código já escrito lá. 1614 01:19:50,220 --> 01:19:53,011 Não tenha muito medo se você não faz entender o que tudo isso significa. 1615 01:19:53,011 --> 01:19:54,749 Se é muito, é totalmente bem. 1616 01:19:54,749 --> 01:19:55,790 E chegar a horas de expediente. 1617 01:19:55,790 --> 01:19:57,520 Nós vamos ajudá-lo a dar uma olhada. 1618 01:19:57,520 --> 01:20:00,810 >> AUDIÊNCIA: Com a adicional funções, parecemos aqueles acima? 1619 01:20:00,810 --> 01:20:03,417 >> ANDI Peng: Sim, essas são no código. 1620 01:20:03,417 --> 01:20:05,750 No jogo de 15, metade dos ele já está escrito para você. 1621 01:20:05,750 --> 01:20:09,310 Assim, estas funções sejam já no código. 1622 01:20:09,310 --> 01:20:12,020 Sim. 1623 01:20:12,020 --> 01:20:12,520 Tudo certo. 1624 01:20:12,520 --> 01:20:14,000 Bem, melhor sorte. 1625 01:20:14,000 --> 01:20:15,180 É um dia nojento. 1626 01:20:15,180 --> 01:20:19,370 Portanto, esperamos que vocês não me sinto muito mal por ficar dentro e codificação. 1627 01:20:19,370 --> 01:20:22,133