1
00:00:00,000 --> 00:00:02,570
[Powered by Google Translate] [Seção 3 - Mais Confortável]

2
00:00:02,570 --> 00:00:05,070
[Rob Bowden - Harvard University]

3
00:00:05,070 --> 00:00:07,310
>> [Esta é CS50. - CS50.TV]

4
00:00:07,310 --> 00:00:12,700
>> Então, a primeira pergunta é estranhamente formulada.

5
00:00:12,700 --> 00:00:17,480
GDB permite "depurar" um programa, mas, mais especificamente, o que é que vamos fazer?

6
00:00:17,480 --> 00:00:22,590
Eu vou responder essa, e eu não sei o que é exatamente o esperado,

7
00:00:22,590 --> 00:00:27,910
então eu estou supondo que é algo ao longo das linhas de ele permite que você passo a passo

8
00:00:27,910 --> 00:00:31,540
andar através do programa, interagir com ele, as variáveis ​​de mudança, fazer todas essas coisas -

9
00:00:31,540 --> 00:00:34,270
basicamente controlar completamente a execução de um programa

10
00:00:34,270 --> 00:00:38,410
e inspeccionar qualquer determinada parte da execução do programa.

11
00:00:38,410 --> 00:00:43,030
Então, esses recursos permitem que você depurar as coisas.

12
00:00:43,030 --> 00:00:44,830
Okay.

13
00:00:44,830 --> 00:00:50,520
Por que a busca binária requer que uma matriz ser classificados?

14
00:00:50,520 --> 00:00:53,360
Quem quer responder a isso?

15
00:00:56,120 --> 00:01:00,070
[Aluno] Porque ele não funciona se não for classificado. Sim >>. [Risos]

16
00:01:00,070 --> 00:01:04,910
Se não for resolvido, então é impossível para dividi-lo ao meio

17
00:01:04,910 --> 00:01:07,850
e saber que tudo para a esquerda é menos e tudo à direita

18
00:01:07,850 --> 00:01:10,490
é maior do que o valor médio.

19
00:01:10,490 --> 00:01:12,790
Por isso, precisa ser ordenada.

20
00:01:12,790 --> 00:01:14,170
Okay.

21
00:01:14,170 --> 00:01:17,570
Por que é uma espécie de bolha em O de n ao quadrado?

22
00:01:17,570 --> 00:01:23,230
Alguém primeiro quero dar uma muito rápida visão geral de alto nível de que tipo bolha é?

23
00:01:25,950 --> 00:01:33,020
[Aluno] Você basicamente passar por cada elemento e você verificar os elementos primeiros.

24
00:01:33,020 --> 00:01:37,150
Se eles estão fora de onde você trocá-los, depois de verificar os elementos seguintes, e assim por diante.

25
00:01:37,150 --> 00:01:40,770
Quando você chegar ao fim, então você sabe que o maior elemento é colocado no final,

26
00:01:40,770 --> 00:01:42,750
assim você ignorar que um, então você continuar passando,

27
00:01:42,750 --> 00:01:48,490
e cada vez que você tem que verificar um elemento menos até que você não fazer alterações. Sim >>.

28
00:01:48,490 --> 00:01:58,470
É chamado espécie de bolha, porque se você virar a matriz de lado assim que é de cima para baixo, vertical,

29
00:01:58,470 --> 00:02:03,100
em seguida, os grandes valores que vão para o fundo e os pequenos valores vai borbulhar até o topo.

30
00:02:03,100 --> 00:02:05,210
É assim que tem o seu nome.

31
00:02:05,210 --> 00:02:08,220
E sim, você acabou de passar.

32
00:02:08,220 --> 00:02:11,190
Você continua passando pela matriz, trocando o valor maior

33
00:02:11,190 --> 00:02:14,040
para obter os maiores valores para o fundo.

34
00:02:14,040 --> 00:02:17,500
>> Por que é O de n ao quadrado?

35
00:02:18,690 --> 00:02:24,620
Primeiro, alguém quer dizer por isso que é O de n ao quadrado?

36
00:02:24,620 --> 00:02:28,760
[Aluno] Porque para cada corrida ele vai n vezes.

37
00:02:28,760 --> 00:02:32,100
Você só pode ter certeza de que você tenha tido o maior elemento de todo o caminho,

38
00:02:32,100 --> 00:02:35,230
então você tem que repetir que para tantos elementos. Sim >>.

39
00:02:35,230 --> 00:02:41,800
Portanto, tenha em mente o que significa e grande O que significa Omega grandes.

40
00:02:41,800 --> 00:02:50,560
O O grande é como o limite superior sobre o quão lento ele pode realmente ser executado.

41
00:02:50,560 --> 00:02:58,990
Então, dizendo que é O de n ao quadrado, não é O de n ou então ele seria capaz de executar

42
00:02:58,990 --> 00:03:02,640
no tempo linear, mas é de O n cubed

43
00:03:02,640 --> 00:03:06,390
porque é delimitada por O de n em cubos.

44
00:03:06,390 --> 00:03:12,300
Se ele é limitado por O de n ao quadrado, então é limitada também pelo n cubos.

45
00:03:12,300 --> 00:03:20,280
Por isso, é n ao quadrado e, no pior caso absoluta que não pode fazer melhor do que n ao quadrado,

46
00:03:20,280 --> 00:03:22,830
é por isso que é O de n ao quadrado.

47
00:03:22,830 --> 00:03:31,200
Então, para ver de matemática discreta em como ele vem a ser n ao quadrado,

48
00:03:31,200 --> 00:03:40,530
se temos cinco coisas em nossa lista, a primeira vez que o número de swaps poderíamos potencialmente precisa fazer

49
00:03:40,530 --> 00:03:47,170
a fim de obter isso? Vamos realmente apenas -

50
00:03:47,170 --> 00:03:52,040
Quantos swaps que vamos ter que fazer na primeira corrida da espécie de bolha através da matriz?

51
00:03:52,040 --> 00:03:53,540
[Aluno] n - 1. Sim >>.

52
00:03:53,540 --> 00:03:58,340
>> Se existem 5 elementos, vamos precisar fazer n - 1.

53
00:03:58,340 --> 00:04:01,100
Em seguida, no segundo quantas swaps que vamos ter que fazer?

54
00:04:01,100 --> 00:04:03,440
[Estudante] n - 2. Sim >>.

55
00:04:03,440 --> 00:04:11,640
E o terceiro vai ser n - 3, e em seguida para a conveniência vou escrever os dois últimos

56
00:04:11,640 --> 00:04:15,270
como então vamos precisar fazer dois swaps e um de swap.

57
00:04:15,270 --> 00:04:19,899
Eu acho que o último pode ou não pode realmente precisam acontecer.

58
00:04:19,899 --> 00:04:22,820
É uma troca? Eu não sei.

59
00:04:22,820 --> 00:04:26,490
Portanto, estas são as quantidades totais de swaps ou pelo menos comparações que você tem que fazer.

60
00:04:26,490 --> 00:04:29,910
Mesmo se você não trocar, você ainda precisa comparar os valores.

61
00:04:29,910 --> 00:04:33,910
Então, existem n - 1 comparações na primeira corrida através da matriz.

62
00:04:33,910 --> 00:04:42,050
Se você reorganizar essas coisas, vamos realmente fazer seis coisas assim que as coisas se comportam bem,

63
00:04:42,050 --> 00:04:44,790
e então eu vou fazer 3, 2, 1.

64
00:04:44,790 --> 00:04:49,910
Então, basta reorganizar estes montantes, que queremos ver quantas comparações fazemos

65
00:04:49,910 --> 00:04:52,700
no algoritmo inteiro.

66
00:04:52,700 --> 00:04:56,550
Então, se nós trazemos esses caras aqui em baixo,

67
00:04:56,550 --> 00:05:07,470
então ainda estamos apenas somando comparações no entanto eram.

68
00:05:07,470 --> 00:05:13,280
Mas se resumir estes e somamos estes e somamos estes,

69
00:05:13,280 --> 00:05:18,130
ainda é o mesmo problema. Nós apenas somar esses grupos particulares.

70
00:05:18,130 --> 00:05:22,400
>> Então agora estamos somando 3 n da. Não é apenas de 3 n.

71
00:05:22,400 --> 00:05:27,650
É sempre vai ser n / 2 n é.

72
00:05:27,650 --> 00:05:29,430
Então, aqui acontece que temos 6.

73
00:05:29,430 --> 00:05:34,830
Se tivéssemos 10 coisas, então nós poderíamos fazer isso de agrupamento para 5 pares diferentes de coisas

74
00:05:34,830 --> 00:05:37,180
e acabar com n + n + n + n + n.

75
00:05:37,180 --> 00:05:45,840
Então, você está sempre indo para obter n / 2 n, e assim por isso, vamos anotar-lo para n ao quadrado / 2.

76
00:05:45,840 --> 00:05:48,890
E por isso mesmo que é o fator de metade, o que acontece a entrar em

77
00:05:48,890 --> 00:05:54,190
devido ao fato de que em cada iteração sobre a matriz compararmos um a menos

78
00:05:54,190 --> 00:05:58,040
então é assim que temos a mais de 2, mas ainda é n ao quadrado.

79
00:05:58,040 --> 00:06:01,650
Nós não nos importamos com o fator constante de um meia.

80
00:06:01,650 --> 00:06:07,760
Então, um monte de coisas O grande como este se baseia em apenas um tipo de fazer esse tipo de matemática,

81
00:06:07,760 --> 00:06:12,260
fazer contas de aritmética e outras coisas série geométrica,

82
00:06:12,260 --> 00:06:17,750
mas a maioria deles neste curso são bastante simples.

83
00:06:17,750 --> 00:06:19,290
Okay.

84
00:06:19,290 --> 00:06:24,430
Por que é tipo de inserção no Omega de n? O que o ômega significa?

85
00:06:24,430 --> 00:06:27,730
[Dois alunos falam ao mesmo tempo - ininteligíveis] sim. >>

86
00:06:27,730 --> 00:06:30,630
Omega você pode pensar como o limite inferior.

87
00:06:30,630 --> 00:06:36,550
>> Portanto, não importa o quão eficiente o seu algoritmo de ordenação por inserção é,

88
00:06:36,550 --> 00:06:41,810
independentemente da lista que é transmitido, ele sempre tem que comparar pelo menos n coisas

89
00:06:41,810 --> 00:06:44,620
ou tem que iterar n coisas.

90
00:06:44,620 --> 00:06:47,280
Por que isso?

91
00:06:47,280 --> 00:06:51,190
[Aluno] Porque se a lista já está classificado, em seguida, através iteração o primeiro

92
00:06:51,190 --> 00:06:54,080
você só pode garantir que o primeiro elemento é o mínimo,

93
00:06:54,080 --> 00:06:56,490
ea segunda iteração você só pode garantir os dois primeiros são

94
00:06:56,490 --> 00:07:00,010
porque você não sabe o que o resto da lista é ordenada. Sim >>.

95
00:07:00,010 --> 00:07:08,910
Se você passar em uma lista completamente classificados, no mínimo você tem que passar por cima de todos os elementos

96
00:07:08,910 --> 00:07:12,180
para ver que nada precisa ser movimentados.

97
00:07:12,180 --> 00:07:14,720
Então, passando por cima da lista e dizer oh, isso já está classificado,

98
00:07:14,720 --> 00:07:18,240
é impossível para você saber que está classificada até que você verifique cada elemento

99
00:07:18,240 --> 00:07:20,660
para ver que eles estão em ordem de classificação.

100
00:07:20,660 --> 00:07:25,290
Assim, o limite inferior é Omega tipo de inserção de n.

101
00:07:25,290 --> 00:07:28,210
Qual é o pior caso de tempo de funcionamento merge sort,

102
00:07:28,210 --> 00:07:31,390
O pior caso de ser grande de novo?

103
00:07:31,390 --> 00:07:37,660
Assim, no pior caso, como é que merge sort correr?

104
00:07:42,170 --> 00:07:43,690
[Estudante] N log n. Sim >>.

105
00:07:43,690 --> 00:07:49,990
Os mais rápidos algoritmos de classificação geral são n log n. Você não pode fazer melhor.

106
00:07:51,930 --> 00:07:55,130
>> Há casos especiais, e se tivermos tempo de hoje - mas provavelmente won't -

107
00:07:55,130 --> 00:07:59,330
podemos ver um que faz melhor do que n log n.

108
00:07:59,330 --> 00:08:04,050
Mas, no caso geral, você não pode fazer melhor do que n log n.

109
00:08:04,050 --> 00:08:09,680
E merge sort acontece a ser o que você deve saber para este curso que é n log n.

110
00:08:09,680 --> 00:08:13,260
E assim nós vamos realmente ser de execução que hoje.

111
00:08:13,260 --> 00:08:18,070
E, finalmente, em não mais que três frases, como funciona o tipo de seleção?

112
00:08:18,070 --> 00:08:20,370
Alguém quer responder, e eu vou contar suas frases

113
00:08:20,370 --> 00:08:22,390
porque se você passar por cima de 3 -

114
00:08:25,530 --> 00:08:28,330
Alguém se lembra tipo de seleção?

115
00:08:31,280 --> 00:08:37,809
Tipo de seleção é geralmente bastante fácil de lembrar apenas do nome.

116
00:08:37,809 --> 00:08:45,350
Você só iterar sobre a matriz, encontrar o que o maior valor é o menor ou -

117
00:08:45,350 --> 00:08:47,290
ordem que está classificando dentro

118
00:08:47,290 --> 00:08:50,750
Então, vamos dizer que estamos classificação da menor para a maior.

119
00:08:50,750 --> 00:08:55,250
Você iterar sobre a matriz, olhando para o que o elemento mínimo é,

120
00:08:55,250 --> 00:08:59,750
selecioná-lo, e depois é só trocá-lo o que está em primeiro lugar.

121
00:08:59,750 --> 00:09:04,090
E então, na segunda passagem sobre a matriz, procure o elemento mínimo de novo,

122
00:09:04,090 --> 00:09:07,490
selecioná-lo, e depois trocá-lo com o que está na segunda posição.

123
00:09:07,490 --> 00:09:10,650
Então, estamos apenas escolhendo os valores mínimos

124
00:09:10,650 --> 00:09:16,050
e inserindo-os na frente da matriz até que seja ordenada.

125
00:09:19,210 --> 00:09:21,560
Perguntas sobre isso?

126
00:09:21,560 --> 00:09:25,710
>> Isto inevitavelmente aparecem nas formas que você tem que preencher quando você está enviando o pset.

127
00:09:29,010 --> 00:09:32,360
Esses são, basicamente, as respostas a esses.

128
00:09:32,360 --> 00:09:34,230
Ok, então agora codificação problemas.

129
00:09:34,230 --> 00:09:40,140
Eu já enviado através de e-mail - Será que ninguém obter esse e-mail? Okay.

130
00:09:40,140 --> 00:09:46,630
Eu já enviou por e-mail o espaço que vamos utilizar,

131
00:09:46,630 --> 00:09:52,120
e se você clicar no meu nome - então eu acho que vou estar no fundo

132
00:09:52,120 --> 00:09:57,170
por causa do r para trás - mas se você clicar no meu nome que você vai ver duas revisões.

133
00:09:57,170 --> 00:10:02,650
Revisão 1 vai ser eu já copiou e colou o código em espaços

134
00:10:02,650 --> 00:10:06,900
para a coisa de pesquisa você vai ter que implementar.

135
00:10:06,900 --> 00:10:10,540
Revisão 2 e será a coisa tipo que vamos implementar depois disso.

136
00:10:10,540 --> 00:10:15,770
Assim, você pode clicar no meu Revisão 1 e trabalhar a partir daí.

137
00:10:17,350 --> 00:10:22,060
E agora queremos implementar busca binária.

138
00:10:22,060 --> 00:10:26,470
>> Alguém quer apenas dar uma explicação de alto nível pseudocódigo

139
00:10:26,470 --> 00:10:31,440
de que nós vamos ter que fazer para pesquisas? Sim.

140
00:10:31,440 --> 00:10:36,170
[Estudante] Você acabou de tomar a meio da matriz e ver se o que você está procurando

141
00:10:36,170 --> 00:10:38,650
é menor do que ou maior do que isso.

142
00:10:38,650 --> 00:10:41,080
E se for menos, você vai para a metade que é menos,

143
00:10:41,080 --> 00:10:44,750
e se é mais, você vai para a metade que é mais e você repetir isso até você, é só pegar uma coisa.

144
00:10:44,750 --> 00:10:46,570
[Bowden] Yeah.

145
00:10:46,570 --> 00:10:51,320
Observe que a nossa matriz de números já está classificado,

146
00:10:51,320 --> 00:10:57,190
e assim que significa que podemos tirar proveito disso e podemos verificar primeiro,

147
00:10:57,190 --> 00:11:00,390
bem, eu estou olhando para o número 50.

148
00:11:00,390 --> 00:11:03,720
Então eu posso ir para o meio.

149
00:11:03,720 --> 00:11:07,380
Médio é difícil de definir quando é um número par de coisas,

150
00:11:07,380 --> 00:11:10,820
mas vamos apenas dizer que nós sempre truncar para o meio.

151
00:11:10,820 --> 00:11:14,420
Portanto, temos aqui oito coisas, de modo que o meio seria 16.

152
00:11:14,420 --> 00:11:17,330
Estou à procura de 50, de modo que 50 é maior que 16.

153
00:11:17,330 --> 00:11:21,310
Então agora eu posso tratar a minha matriz basicamente como estes elementos.

154
00:11:21,310 --> 00:11:23,450
Eu posso jogar fora tudo de mais 16.

155
00:11:23,450 --> 00:11:27,440
Agora a minha matriz é apenas estes quatro elementos, e repito.

156
00:11:27,440 --> 00:11:31,910
Então eu quero encontrar o meio novamente, o que vai ser 42.

157
00:11:31,910 --> 00:11:34,730
42 é menor que 50, então eu posso jogar fora esses dois elementos.

158
00:11:34,730 --> 00:11:36,890
Esta é a minha matriz restante.

159
00:11:36,890 --> 00:11:38,430
Eu vou encontrar o meio novamente.

160
00:11:38,430 --> 00:11:42,100
Eu acho que 50 foi um mau exemplo, porque eu estava sempre jogando fora as coisas para a esquerda,

161
00:11:42,100 --> 00:11:48,280
mas pela mesma medida, se eu estou procurando algo

162
00:11:48,280 --> 00:11:52,100
e é menos do que o elemento Atualmente estou olhando,

163
00:11:52,100 --> 00:11:55,080
então eu vou jogar fora tudo para a direita.

164
00:11:55,080 --> 00:11:58,150
Então agora precisamos implementar isso.

165
00:11:58,150 --> 00:12:02,310
Observe que temos de passar de tamanho.

166
00:12:02,310 --> 00:12:06,730
Não podemos também precisa duro código de tamanho.

167
00:12:06,730 --> 00:12:11,640
Então, se livrar desse # define -

168
00:12:19,630 --> 00:12:21,430
Okay.

169
00:12:21,430 --> 00:12:27,180
Como posso muito bem imaginar o que o tamanho da matriz de números, atualmente, é?

170
00:12:27,180 --> 00:12:30,950
>> Quantos elementos estão na matriz de números?

171
00:12:30,950 --> 00:12:33,630
[Aluno] Números, suportes. Comprimento?

172
00:12:33,630 --> 00:12:36,600
[Bowden] Isso não existe em C.

173
00:12:36,600 --> 00:12:38,580
Precisa. Comprimento.

174
00:12:38,580 --> 00:12:42,010
Matrizes não têm propriedades, por isso não há propriedade de comprimento de matrizes

175
00:12:42,010 --> 00:12:45,650
que só vai dar-lhe o tempo que passa a ser.

176
00:12:48,180 --> 00:12:51,620
[Estudante] Ver a quantidade de memória que tem e dividir por quanto - Sim. >>

177
00:12:51,620 --> 00:12:55,810
Então, como podemos ver quanta memória ele tem? >> [Aluno] Sizeof. >> Sim, sizeof.

178
00:12:55,810 --> 00:13:01,680
Sizeof é o operador que vai retornar o tamanho da matriz de números.

179
00:13:01,680 --> 00:13:10,060
E isso vai ser inteiros no entanto, existem muitas vezes o tamanho de um inteiro

180
00:13:10,060 --> 00:13:14,050
já que é a quantidade de memória que está realmente tomando-se.

181
00:13:14,050 --> 00:13:17,630
Então, se eu quiser que o número de coisas na matriz,

182
00:13:17,630 --> 00:13:20,560
então eu vou querer dividir com o tamanho de um inteiro.

183
00:13:22,820 --> 00:13:26,010
Okay. Assim que me permite passar em tamanho aqui.

184
00:13:26,010 --> 00:13:29,430
Por que eu preciso passar em tamanho a todos?

185
00:13:29,430 --> 00:13:38,570
Por que eu não posso simplesmente fazer aqui int tamanho = sizeof (palheiro) / sizeof (int)?

186
00:13:38,570 --> 00:13:41,490
Por que isso não funciona?

187
00:13:41,490 --> 00:13:44,470
[Aluno] Não é uma variável global.

188
00:13:44,470 --> 00:13:51,540
[Bowden] Haystack existe e estamos passando em números como palheiro,

189
00:13:51,540 --> 00:13:54,700
e esta é uma espécie de prenúncio do que está por vir. Sim.

190
00:13:54,700 --> 00:14:00,170
[Aluno] Haystack é apenas a referência a ele, por isso seria voltar como grande referência que é.

191
00:14:00,170 --> 00:14:02,150
Sim.

192
00:14:02,150 --> 00:14:09,000
Eu duvido que na palestra que você já viu a pilha ainda muito, certo?

193
00:14:09,000 --> 00:14:11,270
Acabamos de falar sobre isso.

194
00:14:11,270 --> 00:14:16,090
Assim, a pilha é onde todas as suas variáveis ​​vão ser armazenados.

195
00:14:16,090 --> 00:14:19,960
>> Qualquer memória que está alocado para as variáveis ​​locais vai na pilha,

196
00:14:19,960 --> 00:14:24,790
e cada função recebe o seu próprio espaço na pilha, seu quadro de pilha própria é o que é chamado.

197
00:14:24,790 --> 00:14:31,590
Então principal tem seu quadro de pilha, e dentro dele vai existir essa matriz de números,

198
00:14:31,590 --> 00:14:34,270
e que vai ser de tamanho sizeof (números).

199
00:14:34,270 --> 00:14:38,180
Vai ter o tamanho de números separados por tamanho dos elementos,

200
00:14:38,180 --> 00:14:42,010
mas que todas as vidas dentro do quadro principal de pilha.

201
00:14:42,010 --> 00:14:45,190
Quando chamamos de busca, pesquisa recebe o seu quadro de pilha própria,

202
00:14:45,190 --> 00:14:48,840
seu próprio espaço para armazenar todas as suas variáveis ​​locais.

203
00:14:48,840 --> 00:14:56,420
Mas esses argumentos - assim palheiro não é uma cópia desta matriz inteira.

204
00:14:56,420 --> 00:15:00,990
Nós não passamos em toda a matriz como uma cópia em pesquisa.

205
00:15:00,990 --> 00:15:04,030
Ele só passa uma referência para essa matriz.

206
00:15:04,030 --> 00:15:11,470
Então pesquisa pode acessar estes números através desta referência.

207
00:15:11,470 --> 00:15:17,100
Ainda está acessando as coisas que vivem dentro da estrutura principal da pilha,

208
00:15:17,100 --> 00:15:22,990
mas, basicamente, quando chegarmos aos ponteiros, que deve ser em breve,

209
00:15:22,990 --> 00:15:24,980
isto é o que os ponteiros estão.

210
00:15:24,980 --> 00:15:29,400
Os ponteiros são apenas referências a coisas, e você pode usar ponteiros para acessar as coisas

211
00:15:29,400 --> 00:15:32,030
que estão em quadros de outras coisas "pilha.

212
00:15:32,030 --> 00:15:37,660
Assim, mesmo que os números é local para o principal, que ainda pode acessá-lo através deste ponteiro.

213
00:15:37,660 --> 00:15:41,770
Mas já que é apenas um ponteiro e é apenas uma referência,

214
00:15:41,770 --> 00:15:45,040
sizeof (palheiro) retorna apenas o tamanho da própria referência.

215
00:15:45,040 --> 00:15:47,950
Ele não retorna o tamanho da coisa que está apontando.

216
00:15:47,950 --> 00:15:51,110
Ele não retorna o tamanho real dos números.

217
00:15:51,110 --> 00:15:55,660
E isso não vai funcionar como queremos que ele.

218
00:15:55,660 --> 00:15:57,320
>> Perguntas sobre isso?

219
00:15:57,320 --> 00:16:03,250
Ponteiros será ido em em detalhes significativamente mais sangrento na semana que vem.

220
00:16:06,750 --> 00:16:13,740
E é por isso que um monte de coisas que você vê, coisas de busca mais ou coisas de classificação,

221
00:16:13,740 --> 00:16:16,990
eles estão quase todos indo a necessidade de ter o tamanho real da matriz,

222
00:16:16,990 --> 00:16:20,440
porque em C, não temos idéia do que o tamanho da matriz é.

223
00:16:20,440 --> 00:16:22,720
Você precisa manualmente passá-lo dentro

224
00:16:22,720 --> 00:16:27,190
E você não pode manualmente passar em toda a matriz, porque você está só de passagem na referência

225
00:16:27,190 --> 00:16:30,390
e não pode obter o tamanho da referência.

226
00:16:30,390 --> 00:16:32,300
Okay.

227
00:16:32,300 --> 00:16:38,160
Então, agora queremos implementar o que foi explicado antes.

228
00:16:38,160 --> 00:16:41,530
Você pode trabalhar com ele por um minuto,

229
00:16:41,530 --> 00:16:45,250
e você não tem que se preocupar em obter tudo perfeitamente 100% funcionando.

230
00:16:45,250 --> 00:16:51,410
Basta escrever o pseudocódigo metade para como você acha que ele deve funcionar.

231
00:16:52,000 --> 00:16:53,630
Okay.

232
00:16:53,630 --> 00:16:56,350
Não há necessidade de ser feito completamente com isso ainda.

233
00:16:56,350 --> 00:17:02,380
Mas será que alguém se sinta confortável com o que têm, até agora,

234
00:17:02,380 --> 00:17:05,599
como algo que pode trabalhar em conjunto?

235
00:17:05,599 --> 00:17:09,690
Alguém quer ser voluntário? Ou eu vou escolher aleatoriamente.

236
00:17:12,680 --> 00:17:18,599
Ele não tem de estar certo por qualquer medida, mas algo que pode modificar em um estado de trabalho.

237
00:17:18,599 --> 00:17:20,720
[Aluno] Claro. Ok >>.

238
00:17:20,720 --> 00:17:27,220
Então você pode salvar a revisão clicando no ícone Salvar pouco.

239
00:17:27,220 --> 00:17:29,950
Você é Ramya, certo? >> [Estudante] Yeah. >> [Bowden] Okay.

240
00:17:29,950 --> 00:17:35,140
Então agora eu posso ver a sua revisão e todos podem puxar para cima a revisão.

241
00:17:35,140 --> 00:17:38,600
E aqui nós temos - Certo.

242
00:17:38,600 --> 00:17:43,160
Então Ramya foi com a solução recursiva, que é definitivamente uma solução válida.

243
00:17:43,160 --> 00:17:44,970
Há duas maneiras que você pode fazer este problema.

244
00:17:44,970 --> 00:17:48,060
Você pode fazê-lo de forma iterativa ou recursivamente.

245
00:17:48,060 --> 00:17:53,860
A maioria dos problemas que você encontrar o que pode ser feito recursivamente também pode ser feito de forma iterativa.

246
00:17:53,860 --> 00:17:58,510
Então aqui nós temos feito isso de forma recursiva.

247
00:17:58,510 --> 00:18:03,730
>> Será que alguém quer definir o que significa fazer uma função recursiva?

248
00:18:07,210 --> 00:18:08,920
[Estudante] Quando você tem uma função chamar a si mesma

249
00:18:08,920 --> 00:18:13,470
e depois chamar-se até que ele sai com verdade e verdade. Sim >>.

250
00:18:13,470 --> 00:18:17,680
Uma função recursiva é apenas uma função que chama a si mesmo.

251
00:18:17,680 --> 00:18:24,140
Há três coisas grandes que uma função recursiva deve ter.

252
00:18:24,140 --> 00:18:27,310
O primeiro é, obviamente, ele chama a si mesmo.

253
00:18:27,310 --> 00:18:29,650
O segundo é o caso base.

254
00:18:29,650 --> 00:18:33,390
Então, em algum ponto, a função precisa parar de chamar-se,

255
00:18:33,390 --> 00:18:35,610
e é isso que o caso base é para.

256
00:18:35,610 --> 00:18:43,860
Então aqui nós sabemos que devemos parar, devemos dar-se em nossa busca

257
00:18:43,860 --> 00:18:48,150
quando começo iguala final - e nós falaremos sobre o que isso significa.

258
00:18:48,150 --> 00:18:52,130
Mas, finalmente, a última coisa que é importante para funções recursivas:

259
00:18:52,130 --> 00:18:59,250
as funções de alguma forma abordar o caso base.

260
00:18:59,250 --> 00:19:04,140
Como se você não está realmente atualizar qualquer coisa quando você faz a segunda chamada recursiva,

261
00:19:04,140 --> 00:19:07,880
se você está literalmente apenas chamando a função novamente com os mesmos argumentos

262
00:19:07,880 --> 00:19:10,130
e não variáveis ​​globais mudaram ou qualquer coisa,

263
00:19:10,130 --> 00:19:14,430
você nunca vai chegar ao caso base, caso em que isso é ruim.

264
00:19:14,430 --> 00:19:17,950
Será uma recursão infinita e um estouro de pilha.

265
00:19:17,950 --> 00:19:24,330
Mas aqui vemos que a atualização está acontecendo desde o início, estamos atualizando + final / 2,

266
00:19:24,330 --> 00:19:28,180
estamos atualizando o argumento final aqui, estamos atualizando o argumento start aqui.

267
00:19:28,180 --> 00:19:32,860
Assim, em todas as chamadas recursivas estamos atualizando algo. Okay.

268
00:19:32,860 --> 00:19:38,110
Você quer andar conosco através de sua solução? >> Claro.

269
00:19:38,110 --> 00:19:44,270
Estou usando SearchHelp de modo que cada vez que faço esta chamada de função

270
00:19:44,270 --> 00:19:47,910
Eu tenho o início de onde eu estou procurando na matriz e no final

271
00:19:47,910 --> 00:19:49,380
de onde eu estou olhando a matriz.

272
00:19:49,380 --> 00:19:55,330
>> A cada passo onde ele está dizendo que é o elemento do meio, que é de início + final / 2,

273
00:19:55,330 --> 00:19:58,850
é que igual ao que nós estamos procurando?

274
00:19:58,850 --> 00:20:04,650
E se é, então, que encontramos, e eu acho que é passado até os níveis de recursão.

275
00:20:04,650 --> 00:20:12,540
E se isso não for verdade, então vamos verificar se esse valor médio da matriz é muito grande,

276
00:20:12,540 --> 00:20:19,320
caso em que se olha para a parte esquerda da matriz, indo desde o início até o índice médio.

277
00:20:19,320 --> 00:20:22,710
E caso contrário, fazer a meia final.

278
00:20:22,710 --> 00:20:24,740
[Bowden] Okay.

279
00:20:24,740 --> 00:20:27,730
É uma boa idéia.

280
00:20:27,730 --> 00:20:36,640
Ok, então um par de coisas, e na verdade, isso é uma coisa muito alto nível

281
00:20:36,640 --> 00:20:41,270
que você nunca vai precisar saber para este curso, mas é verdade.

282
00:20:41,270 --> 00:20:46,080
Funções recursivas, você sempre ouve que eles são um mau negócio

283
00:20:46,080 --> 00:20:51,160
porque se você recursivamente chamar-se muitas vezes, você tem de estouro de pilha

284
00:20:51,160 --> 00:20:54,990
uma vez que, como eu disse antes, cada função recebe o seu quadro de pilha própria.

285
00:20:54,990 --> 00:20:59,500
Então, cada chamada da função recursiva obtém sua estrutura própria pilha.

286
00:20:59,500 --> 00:21:04,140
Então, se você fizer mil chamadas recursivas, você recebe 1.000 quadros de pilha,

287
00:21:04,140 --> 00:21:08,390
e rapidamente você levar a ter quadros de pilha demais e as coisas simplesmente quebrar.

288
00:21:08,390 --> 00:21:13,480
É por isso que funções recursivas são geralmente ruim.

289
00:21:13,480 --> 00:21:19,370
Mas há um subconjunto agradável de funções recursivas chamado rabo-recursivas funções,

290
00:21:19,370 --> 00:21:26,120
e este passa a ser um exemplo de um que se o compilador percebe isso

291
00:21:26,120 --> 00:21:29,920
e que deveria, penso eu - em Clang se você passar a O2-bandeira

292
00:21:29,920 --> 00:21:33,250
em seguida, ele vai perceber isso é rabo recursiva e fazer as coisas bem.

293
00:21:33,250 --> 00:21:40,050
>> Ele vai reutilizar o quadro de pilha, uma e outra vez para cada chamada recursiva.

294
00:21:40,050 --> 00:21:47,010
E assim desde que você está usando o quadro de pilha mesmo, você não precisa se preocupar com

295
00:21:47,010 --> 00:21:51,690
nunca empilhe transbordando, e, ao mesmo tempo, como você disse antes,

296
00:21:51,690 --> 00:21:56,380
onde uma vez você retornar verdadeiro, então ele tem que voltar-se todos estes quadros de pilha

297
00:21:56,380 --> 00:22:01,740
ea chamada 10 a SearchHelp tem que voltar para o 9, tem que voltar para o 8.

298
00:22:01,740 --> 00:22:05,360
De modo que não precisa acontecer quando funções são cauda recursiva.

299
00:22:05,360 --> 00:22:13,740
E então o que torna esta cauda função recursiva é aviso de que, para um dado convite para searchHelp

300
00:22:13,740 --> 00:22:18,470
a chamada recursiva que ele está fazendo é o que ele está retornando.

301
00:22:18,470 --> 00:22:25,290
Assim, em primeira chamada para SearchHelp, que quer retornar imediatamente falso,

302
00:22:25,290 --> 00:22:29,590
retornar imediatamente verdadeira, ou fazemos uma chamada recursiva para SearchHelp

303
00:22:29,590 --> 00:22:33,810
onde o que está retornando é o que essa chamada está retornando.

304
00:22:33,810 --> 00:22:51,560
E não poderia fazer isso se fizemos algo como int x = SearchHelp retorno, x * 2,

305
00:22:51,560 --> 00:22:55,440
apenas alguma alteração aleatória.

306
00:22:55,440 --> 00:23:01,470
>> Então, agora chamada esta recursiva, esta int x = SearchHelp chamada recursiva,

307
00:23:01,470 --> 00:23:05,740
já não é cauda recursiva porque na verdade não tem que devolver

308
00:23:05,740 --> 00:23:10,400
de volta para um quadro de pilha anterior de modo a que a chamada anterior para a função

309
00:23:10,400 --> 00:23:13,040
pode, então, fazer algo com o valor de retorno.

310
00:23:13,040 --> 00:23:22,190
Então isso não é cauda recursiva, mas o que tinha antes, é bem cauda recursiva. Sim.

311
00:23:22,190 --> 00:23:27,000
[Aluno] não deve o caso base segundo ser verificada primeiro

312
00:23:27,000 --> 00:23:30,640
porque pode haver uma situação em que, quando você passar o argumento

313
00:23:30,640 --> 00:23:35,770
você começar = fim, mas eles são o valor da agulha.

314
00:23:35,770 --> 00:23:47,310
A questão foi que não podemos correr para o caso em que o valor final é de agulha

315
00:23:47,310 --> 00:23:52,000
ou iniciar = fim, apropriadamente, começar final =

316
00:23:52,000 --> 00:23:59,480
e você realmente não tenho verificado que um valor particular, no entanto,

317
00:23:59,480 --> 00:24:03,910
em seguida, iniciar + final / 2 é apenas vai ser o mesmo valor.

318
00:24:03,910 --> 00:24:07,890
Mas nós já retornou falso e nós nunca realmente verificado o valor.

319
00:24:07,890 --> 00:24:14,240
Então, no mínimo, em primeira convocação, se o tamanho é 0, então queremos voltar falso.

320
00:24:14,240 --> 00:24:17,710
Mas se o tamanho é 1, então de início não vai acabar igual,

321
00:24:17,710 --> 00:24:19,820
e nós vamos pelo menos verificar a um elemento.

322
00:24:19,820 --> 00:24:26,750
Mas eu acho que você está certo em que pode acabar em um caso onde começar + final / 2,

323
00:24:26,750 --> 00:24:31,190
início acaba sendo o mesmo que de início + final / 2,

324
00:24:31,190 --> 00:24:35,350
mas nós nunca realmente verificado esse elemento.

325
00:24:35,350 --> 00:24:44,740
>> Então, se nós primeiro verificar se o elemento do meio o valor que está procurando,

326
00:24:44,740 --> 00:24:47,110
então podemos retornar imediatamente verdadeiro.

327
00:24:47,110 --> 00:24:50,740
Mais se eles são iguais, então não há sentido em continuar

328
00:24:50,740 --> 00:24:58,440
já que estamos indo só para atualizar a um caso em que estamos em uma matriz de elemento único.

329
00:24:58,440 --> 00:25:01,110
Se esse elemento único não é o que estamos procurando,

330
00:25:01,110 --> 00:25:03,530
então está tudo errado. Sim.

331
00:25:03,530 --> 00:25:08,900
[Estudante] O problema é que uma vez que o tamanho é realmente maior do que o número de elementos na matriz,

332
00:25:08,900 --> 00:25:13,070
já existe um deslocamento - >> Então vai tamanho -

333
00:25:13,070 --> 00:25:19,380
[Aluno] Dizer se a matriz foi tamanho 0, então o SearchHelp vai realmente verificar palheiro de 0

334
00:25:19,380 --> 00:25:21,490
na primeira chamada.

335
00:25:21,490 --> 00:25:25,300
A matriz tem tamanho 0, de modo que o 0 é - >> Yeah.

336
00:25:25,300 --> 00:25:30,750
Há outra coisa que - que poderia ser bom. Vamos pensar.

337
00:25:30,750 --> 00:25:40,120
Então, se a matriz tinha 10 elementos e um meio que vamos verificar é o índice de 5,

338
00:25:40,120 --> 00:25:45,700
por isso estamos verificando 5, e vamos dizer que o valor é menor.

339
00:25:45,700 --> 00:25:50,720
Então, nós estamos jogando tudo fora de 5 em diante.

340
00:25:50,720 --> 00:25:54,030
Então comece a + final / 2 vai ser o nosso novo fim,

341
00:25:54,030 --> 00:25:57,450
Então, sim, ele sempre vai ficar para além do fim da matriz.

342
00:25:57,450 --> 00:26:03,570
Se é um caso se era par ou ímpar, então poderíamos verificar, por exemplo, 4,

343
00:26:03,570 --> 00:26:05,770
mas ainda estamos jogando fora -

344
00:26:05,770 --> 00:26:13,500
Então, sim, o fim é sempre vai ser além do fim real da matriz.

345
00:26:13,500 --> 00:26:18,350
Assim, os elementos que estamos focando, final é sempre vai ser o um depois.

346
00:26:18,350 --> 00:26:24,270
E assim se faz sempre começo final igual, estamos em uma matriz de tamanho 0.

347
00:26:24,270 --> 00:26:35,600
>> A outra coisa que eu estava pensando é que estamos atualizando início para começar a ser + final / 2,

348
00:26:35,600 --> 00:26:44,020
por isso este é o caso que eu estou tendo problemas com onde começar + final / 2

349
00:26:44,020 --> 00:26:46,820
é o elemento que estamos verificando.

350
00:26:46,820 --> 00:26:58,150
Vamos dizer que nós tivemos essa matriz de 10 elementos. Qualquer que seja.

351
00:26:58,150 --> 00:27:03,250
Então comece a + final / 2 vai ser algo como este,

352
00:27:03,250 --> 00:27:07,060
e se isso não é o valor, digamos que deseja atualizar.

353
00:27:07,060 --> 00:27:10,060
O valor é maior, por isso queremos olhar para esta metade da matriz.

354
00:27:10,060 --> 00:27:15,910
Então, como estamos atualizando início, estamos atualizando início para agora ser esse elemento.

355
00:27:15,910 --> 00:27:23,790
Mas isso ainda pode trabalhar, ou pelo menos, você pode fazer start + final / 2 + 1.

356
00:27:23,790 --> 00:27:27,850
[Aluno] Você não precisa ser começar final + [inaudível] >> Yeah.

357
00:27:27,850 --> 00:27:33,240
Nós já verificada este elemento e sei que não é o que estamos procurando.

358
00:27:33,240 --> 00:27:36,800
Portanto, não é necessário atualizar início para ser esse elemento.

359
00:27:36,800 --> 00:27:39,560
Nós podemos simplesmente ignorá-lo e atualizar começar a ser este elemento.

360
00:27:39,560 --> 00:27:46,060
E há sempre um caso, vamos dizer, que este fosse final,

361
00:27:46,060 --> 00:27:53,140
assim, então começar seria isso, inicie + final / 2 seria este,

362
00:27:53,140 --> 00:28:00,580
começar a final + - Sim, eu acho que ele pode acabar em recursão infinita.

363
00:28:00,580 --> 00:28:12,690
Vamos dizer que é apenas uma matriz de tamanho 2 ou uma matriz de tamanho 1. Eu acho que isso vai funcionar.

364
00:28:12,690 --> 00:28:19,490
Assim, atualmente, é que início e fim elemento é um além.

365
00:28:19,490 --> 00:28:24,110
Assim, o elemento que vamos verificar é este,

366
00:28:24,110 --> 00:28:29,400
e então, quando nós atualizamos início, estamos atualizando início para ser 0 + 1/2,

367
00:28:29,400 --> 00:28:33,160
que vai acabar nos de volta com partida sendo este elemento.

368
00:28:33,160 --> 00:28:36,210
>> Então, nós estamos verificando o mesmo elemento e outra vez.

369
00:28:36,210 --> 00:28:43,310
Portanto, este é o caso em que cada chamada recursiva deve realmente atualizar alguma coisa.

370
00:28:43,310 --> 00:28:48,370
Então, nós precisamos fazer start + final / 2 + 1, ou então há um caso

371
00:28:48,370 --> 00:28:50,710
onde não estamos realmente atualizar início.

372
00:28:50,710 --> 00:28:53,820
Todo mundo vê isso?

373
00:28:53,820 --> 00:28:56,310
Okay.

374
00:28:56,310 --> 00:29:03,860
Alguém tem perguntas sobre esta solução ou comentários mais?

375
00:29:05,220 --> 00:29:10,280
Okay. Alguém tem uma solução iterativa que todos nós podemos olhar?

376
00:29:17,400 --> 00:29:20,940
Será que todos nós fazemos isso recursivamente?

377
00:29:20,940 --> 00:29:25,950
Ou eu também acho que se você abrir o seu, então você pode ter substituído o seu anterior.

378
00:29:25,950 --> 00:29:28,810
Será que salvar automaticamente? Eu não sou positivo.

379
00:29:35,090 --> 00:29:39,130
Alguém tem iterativo?

380
00:29:39,130 --> 00:29:42,430
Podemos caminhar com ele junto, se não.

381
00:29:46,080 --> 00:29:48,100
A ideia de que vai ser o mesmo.

382
00:30:00,260 --> 00:30:02,830
Solução iterativa.

383
00:30:02,830 --> 00:30:07,140
Nós vamos querer fazer basicamente a mesma idéia

384
00:30:07,140 --> 00:30:16,530
onde queremos acompanhar o novo fim da matriz e do novo começo da matriz

385
00:30:16,530 --> 00:30:18,510
e fazer isso mais e mais.

386
00:30:18,510 --> 00:30:22,430
E se o que estamos mantendo o controle de como o início eo fim nunca se cruzam,

387
00:30:22,430 --> 00:30:29,020
então nós não encontrá-lo e podemos retornar falso.

388
00:30:29,020 --> 00:30:37,540
Então, como posso fazer isso? Alguém tem sugestões ou código para me puxar para cima?

389
00:30:42,190 --> 00:30:47,450
[Aluno] Faça um loop while. Sim >>.

390
00:30:47,450 --> 00:30:49,450
Você vai querer fazer um loop.

391
00:30:49,450 --> 00:30:51,830
>> Será que você tem o código que eu poderia puxar para cima, ou o que você estava indo para sugerir?

392
00:30:51,830 --> 00:30:56,340
[Aluno] Eu acho que sim. >> Tudo bem. Isso torna as coisas mais fáceis. Qual era o seu nome?

393
00:30:56,340 --> 00:30:57,890
[Aluno] Lucas.

394
00:31:00,140 --> 00:31:04,190
Revisão 1. Okay.

395
00:31:04,190 --> 00:31:13,200
Baixo é o que chamamos de começar antes.

396
00:31:13,200 --> 00:31:17,080
Se não é o que nós chamamos final antes.

397
00:31:17,080 --> 00:31:22,750
Na verdade, o fim está agora dentro da matriz. É um elemento que devemos considerar.

398
00:31:22,750 --> 00:31:26,890
Tão baixa é 0, se for o tamanho da matriz - 1,

399
00:31:26,890 --> 00:31:34,780
e agora estamos looping, e estamos verificando -

400
00:31:34,780 --> 00:31:37,340
Eu acho que você pode andar por ela.

401
00:31:37,340 --> 00:31:41,420
Qual foi o seu pensamento por isso? Ande nos através do seu código.

402
00:31:41,420 --> 00:31:49,940
[Aluno] Claro. Veja o valor palheiro no meio e compará-lo com agulha.

403
00:31:49,940 --> 00:31:58,520
Então, se é maior do que a agulha, então você quer - oh, na verdade, que deve ser para trás.

404
00:31:58,520 --> 00:32:05,180
Você vai querer jogar fora a metade direita, e então sim, que deve ser o caminho.

405
00:32:05,180 --> 00:32:08,830
[Bowden] Portanto, este deve ser menos? É isso que você disse? >> [Estudante] Yeah.

406
00:32:08,830 --> 00:32:10,390
[Bowden] Okay. Menos.

407
00:32:10,390 --> 00:32:15,700
Então, se o que estamos vendo é menor do que o que nós queremos,

408
00:32:15,700 --> 00:32:19,410
então sim, nós queremos jogar fora a metade esquerda,

409
00:32:19,410 --> 00:32:22,210
o que significa que estamos atualizando tudo o que estamos considerando

410
00:32:22,210 --> 00:32:26,610
movendo baixo à direita da matriz.

411
00:32:26,610 --> 00:32:30,130
Este parece ser bom.

412
00:32:30,130 --> 00:32:34,550
Eu acho que tem o mesmo problema que nós dissemos que o anterior,

413
00:32:34,550 --> 00:32:49,760
onde se baixa é 0 e se for 1, então baixa-se + / 2 vai definir até ser a mesma coisa de novo.

414
00:32:49,760 --> 00:32:53,860
>> E mesmo se esse não é o caso, é ainda mais eficiente no mínimo

415
00:32:53,860 --> 00:32:57,630
apenas para jogar fora o elemento que apenas olhou para que sabemos que é errado.

416
00:32:57,630 --> 00:33:03,240
Então baixo + cima / 2 + 1 - >> [aluno], que deveria ser o contrário.

417
00:33:03,240 --> 00:33:05,900
[Bowden] Ou este deve ser - 1 e o outro deve ser + 1.

418
00:33:05,900 --> 00:33:09,580
[Aluno] E não deve ser um duplo sinal de igual. >> [Bowden] Yeah.

419
00:33:09,580 --> 00:33:11,340
[Estudante] Yeah.

420
00:33:14,540 --> 00:33:15,910
Okay.

421
00:33:15,910 --> 00:33:21,280
E, finalmente, agora que temos este 1 + - 1 coisa,

422
00:33:21,280 --> 00:33:31,520
é - não pode ser - é sempre possível para baixo para acabar com um valor maior do que para cima?

423
00:33:35,710 --> 00:33:40,320
Eu acho que a única maneira que pode acontecer - É possível? >> [Aluno] não sei.

424
00:33:40,320 --> 00:33:45,220
Mas se ele fica truncado e em seguida, recebe menos que 1 e depois - >> Yeah.

425
00:33:45,220 --> 00:33:47,480
[Aluno] Seria possivelmente ficar confuso.

426
00:33:49,700 --> 00:33:53,940
Eu acho que deve ser bom só porque

427
00:33:53,940 --> 00:33:58,800
para que ele acabe menor que teria que ser igual, eu acho.

428
00:33:58,800 --> 00:34:03,070
Mas se eles são iguais, então não teria feito o loop while para começar

429
00:34:03,070 --> 00:34:06,670
e nós só teria devolvido o valor. Então, eu acho que estamos bem agora.

430
00:34:06,670 --> 00:34:11,530
Note-se que, embora este problema já não é recursivo,

431
00:34:11,530 --> 00:34:17,400
o mesmo tipo de ideias aplicar onde podemos ver como isso tão facilmente se presta

432
00:34:17,400 --> 00:34:23,659
a uma solução recursiva pelo fato de que nós estamos apenas atualização dos índices e outra vez,

433
00:34:23,659 --> 00:34:29,960
estamos tornando o problema cada vez menor, estamos nos concentrando em um subconjunto da matriz.

434
00:34:29,960 --> 00:34:40,860
[Estudante] Se baixo é 0 e se for 1, ambos estariam 0 + 1/2, que iria para 0,

435
00:34:40,860 --> 00:34:44,429
e, em seguida, um seria + 1, pode-se ser - 1.

436
00:34:47,000 --> 00:34:50,870
[Aluno] Onde estamos verificando a igualdade?

437
00:34:50,870 --> 00:34:55,100
Como se o meio é realmente agulha?

438
00:34:55,100 --> 00:34:58,590
Nós não estamos fazendo atualmente isso? Oh!

439
00:35:00,610 --> 00:35:02,460
Se isto é -

440
00:35:05,340 --> 00:35:13,740
Sim. Não podemos simplesmente fazer o teste aqui porque vamos dizer que a primeira metade -

441
00:35:13,740 --> 00:35:16,430
[Aluno] É realmente como não jogar fora o limite.

442
00:35:16,430 --> 00:35:20,220
Então, se você jogar fora o salto, você tem que verificar primeiro ou o que quer.

443
00:35:20,220 --> 00:35:23,350
Ah. Sim. >> [Estudante] Yeah.

444
00:35:23,350 --> 00:35:29,650
Portanto, agora temos jogado fora o que nós atualmente olhou,

445
00:35:29,650 --> 00:35:33,260
o que significa que nós agora precisamos também ter

446
00:35:33,260 --> 00:35:44,810
if (palheiro [(+ baixo para cima) / 2] == agulha), então podemos retornar true.

447
00:35:44,810 --> 00:35:52,070
E se eu colocar mais ou apenas se, significa literalmente a mesma coisa

448
00:35:52,070 --> 00:35:57,110
porque este teria retornado verdade.

449
00:35:57,110 --> 00:36:01,450
Então, eu vou colocar mais se, mas isso não importa.

450
00:36:01,450 --> 00:36:10,440
>> Então, mais se isso, mais isso, e isso é uma coisa comum que eu faço

451
00:36:10,440 --> 00:36:14,340
onde até mesmo se for o caso, onde tudo é bom aqui,

452
00:36:14,340 --> 00:36:22,780
como baixo nunca pode ser maior do que se, não é o raciocínio que vale a pena saber se isso é verdade.

453
00:36:22,780 --> 00:36:28,010
Assim, pode também dizer enquanto baixo é menor do que ou igual a

454
00:36:28,010 --> 00:36:30,720
ou enquanto baixo é inferior a

455
00:36:30,720 --> 00:36:35,300
por isso, se eles são sempre iguais ou baixa acontece a passar-se,

456
00:36:35,300 --> 00:36:40,130
então podemos quebrar este ciclo.

457
00:36:41,410 --> 00:36:44,630
Perguntas, preocupações, comentários?

458
00:36:47,080 --> 00:36:49,270
Okay. Este parece ser bom.

459
00:36:49,270 --> 00:36:52,230
Agora nós queremos fazer tipo.

460
00:36:52,230 --> 00:37:04,030
Se formos a minha segunda revisão, vemos esses mesmos números,

461
00:37:04,030 --> 00:37:07,550
mas agora eles não estão mais em ordem de classificação.

462
00:37:07,550 --> 00:37:12,840
E nós queremos implementar ordenação usando qualquer algoritmo em O de n log n.

463
00:37:12,840 --> 00:37:17,240
Assim que o algoritmo que você acha que deve implementar aqui? >> [Aluno] tipo Merge.

464
00:37:17,240 --> 00:37:23,810
[Bowden] Yeah. Merge sort é O (n log n), de modo que é o que vamos fazer.

465
00:37:23,810 --> 00:37:26,680
E o problema vai ser bastante semelhante,

466
00:37:26,680 --> 00:37:31,920
onde se presta facilmente a uma solução recursiva.

467
00:37:31,920 --> 00:37:35,580
Nós também podemos chegar a uma solução iterativa, se quisermos,

468
00:37:35,580 --> 00:37:42,540
mas recursão será mais fácil aqui e nós devemos fazer a recursividade.

469
00:37:45,120 --> 00:37:49,530
Acho que vamos caminhar por merge sort primeiro,

470
00:37:49,530 --> 00:37:54,280
embora haja um vídeo bonito em merge sort já. [Risos]

471
00:37:54,280 --> 00:37:59,780
Então, merge sort existem - Eu estou perdendo muito deste trabalho.

472
00:37:59,780 --> 00:38:02,080
Oh, há apenas uma esquerda.

473
00:38:02,080 --> 00:38:03,630
Então, se fundem.

474
00:38:08,190 --> 00:38:12,470
Oh, 1, 3, 5.

475
00:38:26,090 --> 00:38:27,440
Okay.

476
00:38:29,910 --> 00:38:33,460
Merge leva duas matrizes distintas.

477
00:38:33,460 --> 00:38:36,780
Individualmente as duas matrizes são ambos classificadas.

478
00:38:36,780 --> 00:38:40,970
Então, essa matriz, 1, 3, 5, classificados. Esta matriz, 0, 2, 4, classificados.

479
00:38:40,970 --> 00:38:46,710
Agora, o que deve fazer é mesclar combiná-los em uma única matriz que é em si classificados.

480
00:38:46,710 --> 00:38:57,130
Então, nós queremos uma matriz de tamanho 6, que vai ter esses elementos dentro dele

481
00:38:57,130 --> 00:38:59,390
em ordem de classificação.

482
00:38:59,390 --> 00:39:03,390
>> E assim podemos tirar vantagem do fato de que essas duas matrizes são classificadas

483
00:39:03,390 --> 00:39:06,800
fazer isso em tempo linear,

484
00:39:06,800 --> 00:39:13,510
significado de tempo linear se essa matriz é x tamanho e este é y tamanho,

485
00:39:13,510 --> 00:39:20,970
então o algoritmo total deve ser O (x + y). Okay.

486
00:39:20,970 --> 00:39:23,150
Assim sugestões.

487
00:39:23,150 --> 00:39:26,030
[Aluno] Poderíamos começar a partir da esquerda?

488
00:39:26,030 --> 00:39:30,150
Então você vai colocar a 0 para baixo primeiro e depois a 1 e, em seguida, aqui você está no 2.

489
00:39:30,150 --> 00:39:33,320
Então é tipo de como você tem um guia que está se movendo para a direita. >> [Bowden] Yeah.

490
00:39:33,320 --> 00:39:41,070
Para ambas as matrizes se concentrar apenas no elemento mais à esquerda.

491
00:39:41,070 --> 00:39:43,530
Porque ambas as matrizes são classificadas, sabemos que esses dois elementos

492
00:39:43,530 --> 00:39:46,920
são os mais pequenos elementos em um array.

493
00:39:46,920 --> 00:39:53,500
Então isso significa que um desses dois elementos deve ser o menor elemento em nossa matriz resultante da fusão.

494
00:39:53,500 --> 00:39:58,190
O que acontece é que o menor é o do tempo este direito.

495
00:39:58,190 --> 00:40:02,580
Então, tomamos 0, insira-o à esquerda porque 0 é menor que 1,

496
00:40:02,580 --> 00:40:08,210
assim que tomar 0, inseri-lo em nossa primeira posição, e depois atualizar esta

497
00:40:08,210 --> 00:40:12,070
para se concentrar em primeiro elemento.

498
00:40:12,070 --> 00:40:14,570
E agora vamos repetir.

499
00:40:14,570 --> 00:40:20,670
Então agora nós comparar 2 e 1. 1 é menor, por isso vamos inserir uma.

500
00:40:20,670 --> 00:40:25,300
Nós atualizar este ponteiro para apontar para esse cara.

501
00:40:25,300 --> 00:40:33,160
Agora vamos fazer isso de novo, então 2. Isto irá atualizar, comparar estes 2, 3.

502
00:40:33,160 --> 00:40:37,770
Isso atualiza, depois 4 e 5.

503
00:40:37,770 --> 00:40:42,110
De modo que é de mesclagem.

504
00:40:42,110 --> 00:40:49,010
>> Que deve ser bastante óbvio que é o tempo linear, uma vez que basta ir em cada elemento de uma vez.

505
00:40:49,010 --> 00:40:55,980
E esse é o maior passo para a implementação de merge sort está fazendo isso.

506
00:40:55,980 --> 00:40:59,330
E não é tão difícil.

507
00:40:59,330 --> 00:41:15,020
Algumas coisas para se preocupar é vamos dizer que foram fusão 1, 2, 3, 4, 5, 6.

508
00:41:15,020 --> 00:41:30,930
Neste caso, vamos acabar no cenário onde este vai ser menor,

509
00:41:30,930 --> 00:41:36,160
então nós atualizamos este ponteiro, este vai ser menor, atualizar esta,

510
00:41:36,160 --> 00:41:41,280
este é menor, e agora você tem que reconhecer

511
00:41:41,280 --> 00:41:44,220
quando você realmente ficar sem elementos para comparar com.

512
00:41:44,220 --> 00:41:49,400
Uma vez que já utilizaram este matriz inteira,

513
00:41:49,400 --> 00:41:55,190
tudo nesta matriz é agora apenas inserido aqui.

514
00:41:55,190 --> 00:42:02,040
Então, se nós nunca correr para o ponto onde uma de nossas matrizes é completamente fundidas já,

515
00:42:02,040 --> 00:42:06,510
então simplesmente tomar todos os elementos da matriz que não e inseri-las no fim do array.

516
00:42:06,510 --> 00:42:13,630
Assim, podemos apenas inserir 4, 5, 6. Okay.

517
00:42:13,630 --> 00:42:18,070
Isso é uma coisa a observar.

518
00:42:22,080 --> 00:42:26,120
De aplicação que deve ser o passo 1.

519
00:42:26,120 --> 00:42:32,600
Mesclar classificar, então com base nisso, que é duas etapas, duas etapas de bobos.

520
00:42:38,800 --> 00:42:42,090
Vamos dar essa matriz.

521
00:42:57,920 --> 00:43:05,680
Então, merge sort, etapa 1 é recursivamente quebrar a matriz em metades.

522
00:43:05,680 --> 00:43:09,350
Então, dividir essa matriz em metades.

523
00:43:09,350 --> 00:43:22,920
Temos, agora, 4, 15, 16, 50 e 8, 23, 42, 108.

524
00:43:22,920 --> 00:43:25,800
E agora nós fazê-lo novamente e nós dividimos estas em metades.

525
00:43:25,800 --> 00:43:27,530
Eu só vou fazer isso deste lado.

526
00:43:27,530 --> 00:43:34,790
Então, 4, 15 e 16, 50.

527
00:43:34,790 --> 00:43:37,440
Gostaríamos de fazer a mesma coisa aqui.

528
00:43:37,440 --> 00:43:40,340
E agora nós dividi-lo em duas metades novamente.

529
00:43:40,340 --> 00:43:51,080
E nós temos 4, 15, 16, 50.

530
00:43:51,080 --> 00:43:53,170
Então, esse é o nosso caso base.

531
00:43:53,170 --> 00:44:00,540
Uma vez que as matrizes são de tamanho 1, então vamos parar com a divisão em duas metades.

532
00:44:00,540 --> 00:44:03,190
>> Agora o que vamos fazer com isso?

533
00:44:03,190 --> 00:44:15,730
Vamos acabar isto também se dividem em 8, 23, 42 e 108.

534
00:44:15,730 --> 00:44:24,000
Então, agora que estamos neste momento, agora o segundo passo de merge sort é apenas fusão pares para as listas.

535
00:44:24,000 --> 00:44:27,610
Então, nós queremos unir estes. Nós apenas chamar fundir.

536
00:44:27,610 --> 00:44:31,410
Sabemos fusão voltará estes em ordem de classificação.

537
00:44:31,410 --> 00:44:33,920
4, 15.

538
00:44:33,920 --> 00:44:41,440
Agora, queremos juntar essas, e que vai retornar uma lista com aqueles em ordem de classificação,

539
00:44:41,440 --> 00:44:44,160
16, 50.

540
00:44:44,160 --> 00:44:57,380
Combinamos aqueles - Eu não posso escrever - 8, 23 e 42, 108.

541
00:44:57,380 --> 00:45:02,890
Portanto, temos pares incorporadas uma vez.

542
00:45:02,890 --> 00:45:05,140
Agora só fundir novamente.

543
00:45:05,140 --> 00:45:10,130
Observe que cada uma dessas listas é classificada em si,

544
00:45:10,130 --> 00:45:15,220
e então nós podemos apenas mesclar essas listas para obter uma lista de tamanho 4, que é classificada

545
00:45:15,220 --> 00:45:19,990
e mesclar essas duas listas para obter uma lista de tamanho 4, que está classificada.

546
00:45:19,990 --> 00:45:25,710
E, finalmente, podemos mesclar essas duas listas de tamanho 4 para obter uma lista de tamanho 8, que está classificada.

547
00:45:25,710 --> 00:45:34,030
Então, para ver que este é global n log n, já vimos que mesclagem é linear,

548
00:45:34,030 --> 00:45:40,390
Então, quando estamos lidando com a junção destes, assim como o custo global de fusão

549
00:45:40,390 --> 00:45:43,410
para estas duas listas é apenas 2 porque -

550
00:45:43,410 --> 00:45:49,610
Ou bem, é O de n, mas n aqui é apenas esses dois elementos, por isso é 2.

551
00:45:49,610 --> 00:45:52,850
E estes dois será 2 e estes dois será 2 e estes 2 vai ser 2,

552
00:45:52,850 --> 00:45:58,820
assim em todas as fusões que temos de fazer, acabamos fazendo n.

553
00:45:58,820 --> 00:46:03,210
Como 2 + 2 + 2 + 2 é de 8, que é n,

554
00:46:03,210 --> 00:46:08,060
de modo que o custo de fusão neste conjunto é n.

555
00:46:08,060 --> 00:46:10,810
E então a mesma coisa aqui.

556
00:46:10,810 --> 00:46:16,980
Vamos juntar essas duas, então estes dois e, individualmente, esta fusão terá quatro operações,

557
00:46:16,980 --> 00:46:23,610
esta fusão terá quatro operações, mas, mais uma vez, entre todos eles,

558
00:46:23,610 --> 00:46:29,030
acabamos fusão n coisas totais, e por isso este passo leva n.

559
00:46:29,030 --> 00:46:33,670
E assim cada nível tem n elementos a serem reunidos.

560
00:46:33,670 --> 00:46:36,110
>> E quantos são os níveis?

561
00:46:36,110 --> 00:46:40,160
Em cada nível, a nossa matriz cresce tamanho 2.

562
00:46:40,160 --> 00:46:44,590
Aqui nossas matrizes são de tamanho 1, aqui eles são de tamanho 2, aqui eles são de tamanho 4,

563
00:46:44,590 --> 00:46:46,470
e, finalmente, eles são de tamanho 8.

564
00:46:46,470 --> 00:46:56,450
Então, uma vez que está dobrando, não vão ser um total de log n desses níveis.

565
00:46:56,450 --> 00:47:02,090
Assim, com o registro de n níveis, cada nível individual, tendo n total de operações,

566
00:47:02,090 --> 00:47:05,720
temos um log n n algoritmo.

567
00:47:05,720 --> 00:47:07,790
Perguntas?

568
00:47:08,940 --> 00:47:13,320
Já as pessoas já fizeram progressos sobre como implementar isso?

569
00:47:13,320 --> 00:47:18,260
Será que alguém já em um estado onde eu só posso puxar para cima o seu código?

570
00:47:20,320 --> 00:47:22,260
Eu posso dar um minuto.

571
00:47:24,770 --> 00:47:27,470
Este vai ser mais longo.

572
00:47:27,470 --> 00:47:28,730
Eu recomendo se repetem -

573
00:47:28,730 --> 00:47:30,510
Você não tem que fazer recursão para fusão

574
00:47:30,510 --> 00:47:33,750
porque para fazer recursão para mesclagem, você vai ter que passar por um monte de diferentes tamanhos.

575
00:47:33,750 --> 00:47:37,150
Você pode, mas é irritante.

576
00:47:37,150 --> 00:47:43,720
Mas recursão para classificar-se é muito fácil.

577
00:47:43,720 --> 00:47:49,190
Você só literalmente chamar espécie na metade esquerda, tipo na metade direita. Okay.

578
00:47:51,770 --> 00:47:54,860
Alguém tem alguma coisa que eu posso puxar para cima ainda?

579
00:47:54,860 --> 00:47:57,540
Ou então eu vou dar um minuto.

580
00:47:58,210 --> 00:47:59,900
Okay.

581
00:47:59,900 --> 00:48:02,970
Alguém tem algo que podemos trabalhar?

582
00:48:05,450 --> 00:48:09,680
Ou então nós vamos trabalhar com isso e, em seguida, expandir a partir daí.

583
00:48:09,680 --> 00:48:14,050
>> Alguém tem mais do que isso que eu posso puxar para cima?

584
00:48:14,050 --> 00:48:17,770
[Estudante] Yeah. Você pode puxar a minha. >> Tudo bem.

585
00:48:17,770 --> 00:48:19,730
Sim!

586
00:48:22,170 --> 00:48:25,280
[Aluno] Havia uma série de condições. >> Oh, atirar. Você pode -

587
00:48:25,280 --> 00:48:28,110
[Estudante] Eu tenho que salvá-lo. Sim >>.

588
00:48:32,420 --> 00:48:35,730
Então nós fizemos a fusão separadamente.

589
00:48:35,730 --> 00:48:38,570
Ah, mas não é tão ruim assim.

590
00:48:39,790 --> 00:48:41,650
Okay.

591
00:48:41,650 --> 00:48:47,080
Então tipo é em si apenas chamando mergeSortHelp.

592
00:48:47,080 --> 00:48:49,530
Explique-nos o que mergeSortHelp faz.

593
00:48:49,530 --> 00:48:55,700
[Aluno] MergeSortHelp praticamente faz as duas etapas principais,

594
00:48:55,700 --> 00:49:01,270
que é o de classificar cada metade da matriz e, em seguida, para fundir os dois.

595
00:49:04,960 --> 00:49:08,050
[Bowden] Ok, então me dê um segundo.

596
00:49:10,850 --> 00:49:13,210
Eu acho que isso - >> [aluno] eu preciso -

597
00:49:17,100 --> 00:49:19,400
Sim. Eu estou sentindo falta de alguma coisa.

598
00:49:19,400 --> 00:49:23,100
Na fusão, eu percebo que eu preciso para criar uma nova matriz

599
00:49:23,100 --> 00:49:26,530
porque eu não poderia fazê-lo no lugar. Sim >>. Você não pode. Corrigir.

600
00:49:26,530 --> 00:49:28,170
[Estudante] Então eu criar uma nova matriz.

601
00:49:28,170 --> 00:49:31,510
Esqueci-me no final de fundir a re-mudar.

602
00:49:31,510 --> 00:49:34,490
Okay. Precisamos de uma nova matriz.

603
00:49:34,490 --> 00:49:41,000
Em merge sort, isso é quase sempre verdadeiro.

604
00:49:41,000 --> 00:49:44,340
Parte do custo de um algoritmo de melhor em termos de tempo

605
00:49:44,340 --> 00:49:47,310
é quase sempre a necessidade de usar a memória um pouco mais.

606
00:49:47,310 --> 00:49:51,570
Então, aqui, não importa como você fazer merge sort,

607
00:49:51,570 --> 00:49:54,780
você inevitavelmente precisa usar um pouco de memória extra.

608
00:49:54,780 --> 00:49:58,240
Ele ou ela criou uma nova matriz.

609
00:49:58,240 --> 00:50:03,400
E então você diz, no final, só precisa copiar nova matriz para a matriz original.

610
00:50:03,400 --> 00:50:04,830
[Estudante] Eu acho que sim.

611
00:50:04,830 --> 00:50:08,210
Eu não sei se isso funciona em termos de contagem de referência ou o que for -

612
00:50:08,210 --> 00:50:11,650
Sim, ele vai funcionar. >> [Aluno] Okay.

613
00:50:20,620 --> 00:50:24,480
Será que você tente executar isso? >> [Aluno] Não, ainda não. Ok >>.

614
00:50:24,480 --> 00:50:28,880
Tente executá-lo, e então eu vou falar sobre isso por um segundo.

615
00:50:28,880 --> 00:50:35,200
[Aluno] Eu preciso ter todos os protótipos de função e tudo, certo?

616
00:50:37,640 --> 00:50:40,840
Os protótipos de função. Ah, você quer dizer como - Sim.

617
00:50:40,840 --> 00:50:43,040
Ordenar está chamando mergeSortHelp.

618
00:50:43,040 --> 00:50:47,390
>> Então, para que tipo de chamar mergeSortHelp, mergeSortHelp deve ter sido definido

619
00:50:47,390 --> 00:50:56,370
antes tipo ou só precisamos do protótipo. Basta copiar e colar isso.

620
00:50:56,370 --> 00:50:59,490
E da mesma forma, mergeSortHelp está chamando fundir,

621
00:50:59,490 --> 00:51:03,830
mas mesclagem não foi definido ainda, então nós podemos apenas deixar mergeSortHelp saber

622
00:51:03,830 --> 00:51:08,700
que é isso que vai fundir a aparência, e que é isso.

623
00:51:09,950 --> 00:51:15,730
Então mergeSortHelp.

624
00:51:22,770 --> 00:51:32,660
Nós temos um problema aqui, onde temos nenhum caso base.

625
00:51:32,660 --> 00:51:38,110
MergeSortHelp é recursiva, então qualquer função recursiva

626
00:51:38,110 --> 00:51:42,610
vai precisar de algum tipo de caso base para saber quando parar de chamar recursivamente si.

627
00:51:42,610 --> 00:51:45,590
O que é o nosso caso base vai ser aqui? Sim.

628
00:51:45,590 --> 00:51:49,110
[Estudante] Se o tamanho for 1? >> [Bowden] Sim.

629
00:51:49,110 --> 00:51:56,220
Então, como se viu ali, paramos matrizes de divisão

630
00:51:56,220 --> 00:52:01,850
uma vez que temos em matrizes de tamanho 1, que inevitavelmente são classificados si.

631
00:52:01,850 --> 00:52:09,530
Então, se o tamanho é igual a 1, sabemos que a matriz já está classificado,

632
00:52:09,530 --> 00:52:12,970
para que possamos retornar apenas.

633
00:52:12,970 --> 00:52:16,880
>> Observe que é vazio, de modo que não retornar nada especial, apenas retornar.

634
00:52:16,880 --> 00:52:19,580
Okay. Então, esse é o nosso caso base.

635
00:52:19,580 --> 00:52:27,440
Eu acho que o nosso caso base também poderia ser se acontecer de ser fusão de uma matriz de tamanho 0,

636
00:52:27,440 --> 00:52:30,030
nós provavelmente quer parar em algum ponto,

637
00:52:30,030 --> 00:52:33,610
assim, podemos dizer tamanho inferior a 2 ou inferior ou igual a 1

638
00:52:33,610 --> 00:52:37,150
de modo que isso vai funcionar para qualquer matriz agora.

639
00:52:37,150 --> 00:52:38,870
Okay.

640
00:52:38,870 --> 00:52:42,740
Então, esse é o nosso caso base.

641
00:52:42,740 --> 00:52:45,950
Agora se você quer andar conosco através fusão?

642
00:52:45,950 --> 00:52:49,140
O que todos esses casos significa?

643
00:52:49,140 --> 00:52:54,480
Até aqui, nós estamos apenas fazendo a mesma idéia, o -

644
00:52:56,970 --> 00:53:02,470
[Estudante] Eu preciso estar passando tamanho, com todas as chamadas mergeSortHelp.

645
00:53:02,470 --> 00:53:10,080
Eu adicionei tamanho como uma primária adicional e que não está lá, como o tamanho / 2.

646
00:53:10,080 --> 00:53:16,210
[Bowden] Oh, tamanho / 2, tamanho / 2. >> [Estudante] É, e também na função acima, bem.

647
00:53:16,210 --> 00:53:21,320
[Bowden] Aqui? >> [Aluno] Apenas o tamanho. >> [Bowden] Oh. Tamanho, tamanho? >> [Estudante] Yeah.

648
00:53:21,320 --> 00:53:23,010
[Bowden] Okay.

649
00:53:23,010 --> 00:53:26,580
Deixe-me pensar por um segundo.

650
00:53:26,580 --> 00:53:28,780
Não nos deparamos com um problema?

651
00:53:28,780 --> 00:53:33,690
Estamos sempre tratar a esquerda como 0. >> [Aluno] Não.

652
00:53:33,690 --> 00:53:36,340
Isso é errado também. Desculpe. Deve ser partida. Sim.

653
00:53:36,340 --> 00:53:39,230
[Bowden] Okay. Eu gosto que melhor.

654
00:53:39,230 --> 00:53:43,880
E fim. Okay.

655
00:53:43,880 --> 00:53:47,200
Então agora você quer andar conosco através fusão? >> [Aluno] Okay.

656
00:53:47,200 --> 00:53:52,150
Eu só estou passando esta nova matriz que eu criei.

657
00:53:52,150 --> 00:53:57,420
O seu tamanho é o tamanho da parte da matriz que queremos ser classificados

658
00:53:57,420 --> 00:54:03,460
e tentando encontrar o elemento que eu deveria colocar na etapa nova matriz.

659
00:54:03,460 --> 00:54:10,140
Então, para fazer isso, primeiro eu estou verificando se a metade esquerda da matriz continua a ter mais elementos,

660
00:54:10,140 --> 00:54:14,260
e se isso não acontecer, então você vai para baixo para que a condição mais, que apenas diz

661
00:54:14,260 --> 00:54:20,180
Tudo bem, ele deve estar no direito de matriz, e vamos colocar isso no índice atual de newArray.

662
00:54:20,180 --> 00:54:27,620
>> E então, de outra forma, eu estou verificando se o lado direito da matriz também está terminado,

663
00:54:27,620 --> 00:54:30,630
caso em que eu só colocar na esquerda.

664
00:54:30,630 --> 00:54:34,180
Isso pode não ser realmente necessário. Não tenho a certeza.

665
00:54:34,180 --> 00:54:40,970
Mas de qualquer forma, a verificação de outros dois qual dos dois são menores na esquerda ou na direita.

666
00:54:40,970 --> 00:54:49,770
E também, em cada caso, estou incrementando o que eu incrementar espaço reservado.

667
00:54:49,770 --> 00:54:52,040
[Bowden] Okay.

668
00:54:52,040 --> 00:54:53,840
Isso parece bom.

669
00:54:53,840 --> 00:54:58,800
Alguém tem comentários ou questões ou perguntas?

670
00:55:00,660 --> 00:55:07,720
Assim, os quatro casos que temos de trazer as coisas em apenas sendo - ou parece que cinco -

671
00:55:07,720 --> 00:55:13,100
mas temos que considerar se a matriz de esquerda não tem mais coisas que precisamos fundir,

672
00:55:13,100 --> 00:55:16,390
se o direito de matriz não tem mais coisas que precisamos unir -

673
00:55:16,390 --> 00:55:18,400
Estou apontando para o nada.

674
00:55:18,400 --> 00:55:21,730
Então, se a matriz de esquerda não tem mais coisas ou o direito de matriz não tem mais coisas.

675
00:55:21,730 --> 00:55:24,320
Esses são dois casos.

676
00:55:24,320 --> 00:55:30,920
Precisamos também de um caso trivial de se a coisa esquerdo é menor que a coisa certa.

677
00:55:30,920 --> 00:55:33,910
Então, nós queremos escolher a coisa esquerdo.

678
00:55:33,910 --> 00:55:37,630
Esses são os casos.

679
00:55:37,630 --> 00:55:40,990
Então isso era certo, então é isso.

680
00:55:40,990 --> 00:55:46,760
Matriz esquerda. É 1, 2, 3. Okay. Então, sim, essas são as quatro coisas que pode querer fazer.

681
00:55:50,350 --> 00:55:54,510
E nós não vamos passar por cima de uma solução iterativa.

682
00:55:54,510 --> 00:55:55,980
Eu não recomendaria -

683
00:55:55,980 --> 00:56:03,070
Fundir tipo é um exemplo de uma função que é ao mesmo tempo não a cauda recursiva,

684
00:56:03,070 --> 00:56:07,040
não é fácil fazer com que a cauda recursiva,

685
00:56:07,040 --> 00:56:13,450
mas também não é muito fácil fazê-lo interativo.

686
00:56:13,450 --> 00:56:16,910
Isto é muito fácil.

687
00:56:16,910 --> 00:56:19,170
Esta implementação do merge sort,

688
00:56:19,170 --> 00:56:22,140
fundem, não importa o que você faça, você está indo para a construção de mesclagem.

689
00:56:22,140 --> 00:56:29,170
>> Então, merge sort construída em cima de mesclar recursivamente é apenas essas três linhas.

690
00:56:29,170 --> 00:56:34,700
Iterativamente, é mais chato e mais difícil de se pensar.

691
00:56:34,700 --> 00:56:41,860
Mas note que não é cauda recursiva desde mergeSortHelp - quando se chama a si mesma -

692
00:56:41,860 --> 00:56:46,590
ele ainda precisa fazer as coisas após esta chamada retorna recursivas.

693
00:56:46,590 --> 00:56:50,830
Portanto, este quadro de pilha deve continuar a existir mesmo depois de chamar isso.

694
00:56:50,830 --> 00:56:54,170
E então, quando você chama isso, o quadro de pilha deve continuar a existir

695
00:56:54,170 --> 00:56:57,780
porque, mesmo depois que a chamada, ainda precisamos mesclar.

696
00:56:57,780 --> 00:57:01,920
E isso não é trivial para fazer este rabo recursiva.

697
00:57:04,070 --> 00:57:06,270
Perguntas?

698
00:57:08,300 --> 00:57:09,860
Tudo bem.

699
00:57:09,860 --> 00:57:13,400
Então, voltando a classificar - oh, há duas coisas que eu quero mostrar. Okay.

700
00:57:13,400 --> 00:57:17,840
Voltando ao tipo, vamos fazer isso rapidamente.

701
00:57:17,840 --> 00:57:21,030
Ou pesquisa. Tipo? Ordenar. Sim.

702
00:57:21,030 --> 00:57:22,730
Voltando aos primórdios da espécie.

703
00:57:22,730 --> 00:57:29,870
Queremos criar um algoritmo que ordena a matriz usando qualquer algoritmo

704
00:57:29,870 --> 00:57:33,660
em O de n.

705
00:57:33,660 --> 00:57:40,860
Então, como isso é possível? Alguém tem qualquer tipo de -

706
00:57:40,860 --> 00:57:44,300
Sugeri antes em -

707
00:57:44,300 --> 00:57:48,300
Se estamos prestes a melhorar a partir de n log n a O de n,

708
00:57:48,300 --> 00:57:51,450
temos melhorado o nosso algoritmo em termos de tempo,

709
00:57:51,450 --> 00:57:55,250
o que significa que vamos precisar fazer para compensar isso?

710
00:57:55,250 --> 00:57:59,520
[Aluno] Espaço. Sim >>. Nós vamos estar usando mais espaço.

711
00:57:59,520 --> 00:58:04,490
E nem mesmo apenas mais espaço, é exponencialmente mais espaço.

712
00:58:04,490 --> 00:58:14,320
Então eu acho que esse tipo de algoritmo é algo pseudo, pseudo polynom -

713
00:58:14,320 --> 00:58:18,980
pseudo - Eu não me lembro. Pseudo algo.

714
00:58:18,980 --> 00:58:22,210
Mas é porque precisamos usar tanto espaço

715
00:58:22,210 --> 00:58:28,610
que isso pode ser conseguido, mas não realista.

716
00:58:28,610 --> 00:58:31,220
>> E como vamos conseguir isso?

717
00:58:31,220 --> 00:58:36,810
Podemos alcançar isso se garantir que algum determinado elemento da matriz

718
00:58:36,810 --> 00:58:39,600
é inferior a um determinado tamanho.

719
00:58:42,070 --> 00:58:44,500
Então vamos apenas dizer que o tamanho é de 200,

720
00:58:44,500 --> 00:58:48,130
qualquer elemento de uma matriz é abaixo do tamanho 200.

721
00:58:48,130 --> 00:58:51,080
E isso é realmente muito realista.

722
00:58:51,080 --> 00:58:58,660
Você pode muito facilmente ter uma matriz que você sabe tudo na mesma

723
00:58:58,660 --> 00:59:00,570
vai ser menor do que um número.

724
00:59:00,570 --> 00:59:07,400
Como se você tiver algum vetor absolutamente enorme ou algo

725
00:59:07,400 --> 00:59:11,810
mas você sabe que tudo vai ser entre 0 e 5,

726
00:59:11,810 --> 00:59:14,790
em seguida, ele vai ser muito mais rápido para fazer isso.

727
00:59:14,790 --> 00:59:17,930
E o limite de qualquer um dos elementos é de 5,

728
00:59:17,930 --> 00:59:21,980
assim que este limite, que é a quantidade de memória que você vai estar usando.

729
00:59:21,980 --> 00:59:26,300
Assim, o limite é de 200.

730
00:59:26,300 --> 00:59:32,960
Em teoria, há sempre um limite desde um inteiro só pode ser de até 4 bilhões,

731
00:59:32,960 --> 00:59:40,600
mas isso é irreal, desde então, estaria usando o espaço

732
00:59:40,600 --> 00:59:44,400
da ordem de 4000 milhões. Então, isso é irreal.

733
00:59:44,400 --> 00:59:47,060
Mas aqui vamos dizer que nosso limite é 200.

734
00:59:47,060 --> 00:59:59,570
O truque para fazê-lo em O de n é que fazer uma outra matriz chamada conta de tamanho VINCULADO.

735
00:59:59,570 --> 01:00:10,470
Então, na verdade, este é um atalho para - Eu realmente não sei se Clang faz isso.

736
01:00:11,150 --> 01:00:15,330
Mas no GCC, no mínimo - Clang assumindo estou faz isso também -

737
01:00:15,330 --> 01:00:18,180
isso só vai inicializar a matriz inteira para ser 0s.

738
01:00:18,180 --> 01:00:25,320
Então, se eu não quiser fazer isso, então eu poderia fazer separadamente for (int i = 0;

739
01:00:25,320 --> 01:00:31,500
i <BOUND, i + +) e conta [i] = 0;

740
01:00:31,500 --> 01:00:35,260
Então, agora tudo é inicializado com 0.

741
01:00:35,260 --> 01:00:39,570
Eu iterar sobre minha matriz,

742
01:00:39,570 --> 01:00:51,920
eo que eu estou fazendo é que eu estou contando o número de cada um - Vamos descer aqui.

743
01:00:51,920 --> 01:00:55,480
Temos 4, 15, 16, 50, 8, 23, 42, 108.

744
01:00:55,480 --> 01:01:00,010
O que eu estou contando é o número de ocorrências de cada um desses elementos.

745
01:01:00,010 --> 01:01:03,470
Vamos realmente adicionar mais um par aqui com algumas repetições.

746
01:01:03,470 --> 01:01:11,070
Assim, o valor que temos aqui, o valor do que vai ser array [i].

747
01:01:11,070 --> 01:01:14,850
Então val poderia ser 4 ou 8 ou o que seja.

748
01:01:14,850 --> 01:01:18,870
E agora eu estou contando quantos de que o valor que eu vi,

749
01:01:18,870 --> 01:01:21,230
para a contagem [val] + +;

750
01:01:21,230 --> 01:01:29,430
Depois de feito isso, conta vai para algo parecido com 0001.

751
01:01:29,430 --> 01:01:42,190
Vamos fazer a contagem [val] - VINCULADO + 1.

752
01:01:42,190 --> 01:01:48,230
>> Agora isso é só para explicar o fato de que estamos começando do 0.

753
01:01:48,230 --> 01:01:50,850
Então, se 200 vai ser a nossa maior número,

754
01:01:50,850 --> 01:01:54,720
então 0-200 é 201 coisas.

755
01:01:54,720 --> 01:02:01,540
Então, conta, ele vai olhar como 00001 porque temos um 4.

756
01:02:01,540 --> 01:02:10,210
Então nós vamos ter 0001, onde vamos ter um 1 no índice de 8 de contagem.

757
01:02:10,210 --> 01:02:14,560
Nós vamos ter a 2 no índice 23 da contagem.

758
01:02:14,560 --> 01:02:17,630
Nós vamos ter a 2 no índice 42 da contagem.

759
01:02:17,630 --> 01:02:21,670
Assim, podemos usar contagem.

760
01:02:34,270 --> 01:02:44,920
Então num_of_item = contagem [i].

761
01:02:44,920 --> 01:02:52,540
E assim se num_of_item é 2, isso significa que nós queremos inserir o número 2 de i

762
01:02:52,540 --> 01:02:55,290
em nossa matriz de classificação.

763
01:02:55,290 --> 01:03:02,000
Portanto, temos de manter o controle de quanto estamos longe na matriz.

764
01:03:02,000 --> 01:03:05,470
Então index = 0.

765
01:03:05,470 --> 01:03:09,910
Array - Eu só vou escrever.

766
01:03:16,660 --> 01:03:18,020
Conta -

767
01:03:19,990 --> 01:03:28,580
array [index + +] = i;

768
01:03:28,580 --> 01:03:32,490
É isso o que eu quero? Eu acho que é o que eu quero.

769
01:03:35,100 --> 01:03:38,290
Sim, isso parece bom. Okay.

770
01:03:38,290 --> 01:03:43,050
Assim que todo mundo entende o que o propósito da minha conta é a matriz?

771
01:03:43,050 --> 01:03:48,140
É contando o número de ocorrências de cada um desses números.

772
01:03:48,140 --> 01:03:51,780
Então eu estou interagindo sobre essa matriz conta,

773
01:03:51,780 --> 01:03:57,190
e a posição ith na matriz contagens

774
01:03:57,190 --> 01:04:01,930
é o número de i é que deve aparecer na minha matriz de classificação.

775
01:04:01,930 --> 01:04:06,840
É por isso que a contagem de 4 vai ser um

776
01:04:06,840 --> 01:04:11,840
e contagem de 8 vai ser 1, as contagens de 23, vai ser 2.

777
01:04:11,840 --> 01:04:16,900
Então é assim que muitos deles eu quero inserir no meu array ordenado.

778
01:04:16,900 --> 01:04:19,200
Então eu só fazer isso.

779
01:04:19,200 --> 01:04:28,960
Estou inserindo num_of_item i é a minha matriz de classificação.

780
01:04:28,960 --> 01:04:31,670
>> Perguntas?

781
01:04:32,460 --> 01:04:43,100
E assim mais uma vez, este é o tempo linear uma vez que estamos apenas interagindo sobre isso uma vez,

782
01:04:43,100 --> 01:04:47,470
mas também é linear em que este número se encontrar,

783
01:04:47,470 --> 01:04:50,730
e por isso depende muito do que o seu limite é.

784
01:04:50,730 --> 01:04:53,290
Com um limite de 200, que não é tão ruim.

785
01:04:53,290 --> 01:04:58,330
Se o seu limite vai ser de 10.000, então isso é um pouco pior,

786
01:04:58,330 --> 01:05:01,360
mas se o seu limite vai ser 4 bilhões, que é completamente irrealista

787
01:05:01,360 --> 01:05:07,720
e essa matriz vai ter que ser de tamanho 4 bilhões, o que é irreal.

788
01:05:07,720 --> 01:05:10,860
Então é isso. Perguntas?

789
01:05:10,860 --> 01:05:13,270
[Resposta do aluno inaudível] >> Okay.

790
01:05:13,270 --> 01:05:15,710
Eu percebi uma coisa, quando estávamos passando.

791
01:05:17,980 --> 01:05:23,720
Acho que o problema estava em Lucas e, provavelmente, cada um que já vimos.

792
01:05:23,720 --> 01:05:26,330
Eu esqueci completamente.

793
01:05:26,330 --> 01:05:31,040
A única coisa que eu queria comentar é que quando você está lidando com coisas como índices,

794
01:05:31,040 --> 01:05:38,320
você nunca realmente ver isso quando você está escrevendo um loop,

795
01:05:38,320 --> 01:05:41,120
mas, tecnicamente, sempre que você está lidando com esses índices,

796
01:05:41,120 --> 01:05:45,950
você deve quase sempre lidar com números inteiros sem sinal.

797
01:05:45,950 --> 01:05:53,850
A razão para isso é quando você está lidando com números inteiros assinados,

798
01:05:53,850 --> 01:05:56,090
por isso, se você tem dois inteiros assinados e adicioná-los juntos

799
01:05:56,090 --> 01:06:00,640
e eles acabam muito grande, então você acaba com um número negativo.

800
01:06:00,640 --> 01:06:03,410
Então é isso que é estouro de inteiro.

801
01:06:03,410 --> 01:06:10,500
>> Se eu adicionar 2 bilhões e 1 bilhão, eu acabar com negativo 1 bilhão.

802
01:06:10,500 --> 01:06:15,480
É assim que funciona em computadores inteiros.

803
01:06:15,480 --> 01:06:17,510
Assim, o problema com o uso -

804
01:06:17,510 --> 01:06:23,500
Isso é bom, exceto se baixo passa a ser 2 bilhões e se passa a ser 1 bilhão,

805
01:06:23,500 --> 01:06:27,120
então isso vai ser negativo 1 bilhão e, em seguida, vamos dividir esse por dois

806
01:06:27,120 --> 01:06:29,730
e acabar com negativo de 500 milhões.

807
01:06:29,730 --> 01:06:33,760
Portanto, este é apenas um problema se acontecer de você estar procurando por uma matriz

808
01:06:33,760 --> 01:06:38,070
de bilhões de coisas.

809
01:06:38,070 --> 01:06:44,050
Mas se + baixo para cima acontece a transbordar, então isso é um problema.

810
01:06:44,050 --> 01:06:47,750
Assim que torná-los sem sinal, então 2 bilhões, mais 1 bilhão é 3 bilhões.

811
01:06:47,750 --> 01:06:51,960
3.000 milhões dividido por dois é de 1,5 bilhões.

812
01:06:51,960 --> 01:06:55,670
Assim, logo que eles estão sem sinal, tudo é perfeito.

813
01:06:55,670 --> 01:06:59,900
E por isso é também um problema quando você está escrevendo o seu loops,

814
01:06:59,900 --> 01:07:03,940
e realmente, ele provavelmente faz isso automaticamente.

815
01:07:09,130 --> 01:07:12,330
Será realmente apenas gritar com você.

816
01:07:12,330 --> 01:07:21,610
Portanto, se esse número é muito grande para ser em apenas um inteiro, mas que caberia em um inteiro não assinado,

817
01:07:21,610 --> 01:07:24,970
ela vai gritar com você, é por isso que você nunca correr para a questão.

818
01:07:29,150 --> 01:07:34,820
Você pode ver que um índice nunca vai ser negativo,

819
01:07:34,820 --> 01:07:39,220
e assim, quando você está interagindo sobre uma matriz,

820
01:07:39,220 --> 01:07:43,970
você quase sempre pode dizer unsigned int i, mas você realmente não precisa.

821
01:07:43,970 --> 01:07:47,110
As coisas estão indo para o trabalho praticamente tão bem.

822
01:07:48,740 --> 01:07:50,090
Okay. [Sussurra] Que horas são?

823
01:07:50,090 --> 01:07:54,020
A última coisa que eu queria mostrar - e eu vou fazê-lo muito rápido.

824
01:07:54,020 --> 01:08:03,190
Você sabe como nós # define para que possamos # define MAX como 5 ou algo assim?

825
01:08:03,190 --> 01:08:05,940
Não vamos fazer MAX. # Define limite como 200. Isso é o que fizemos antes.

826
01:08:05,940 --> 01:08:10,380
Que define uma constante, que só vai ser copiado e colado

827
01:08:10,380 --> 01:08:13,010
onde quer que aconteça para escrever VINCULADO.

828
01:08:13,010 --> 01:08:18,189
>> Assim, podemos realmente fazer mais com # define.

829
01:08:18,189 --> 01:08:21,170
Podemos # define funções.

830
01:08:21,170 --> 01:08:23,410
Eles não são realmente funções, mas vamos chamá-los de funções.

831
01:08:23,410 --> 01:08:36,000
Um exemplo seria algo como MAX (x, y) é definida como (x <y y:? X). Okay.

832
01:08:36,000 --> 01:08:40,660
Portanto, você deve se acostumar a sintaxe do operador ternário,

833
01:08:40,660 --> 01:08:49,029
mas é menor que x y? Retornar y, outro retorno x.

834
01:08:49,029 --> 01:08:54,390
Assim você pode ver que você pode fazer esta função um separado,

835
01:08:54,390 --> 01:09:01,399
ea função poderia ser como bool MAX leva 2 argumentos, devolva este.

836
01:09:01,399 --> 01:09:08,340
Este é um dos mais comuns que eu vejo feito como este. Nós os chamamos de macros.

837
01:09:08,340 --> 01:09:11,790
Esta é uma macro.

838
01:09:11,790 --> 01:09:15,859
Esta é apenas a sintaxe para isso.

839
01:09:15,859 --> 01:09:18,740
Você pode escrever uma macro para fazer o que quiser.

840
01:09:18,740 --> 01:09:22,649
Você freqüentemente ver macros para depurar printfs e outras coisas.

841
01:09:22,649 --> 01:09:29,410
Assim, um tipo de printf, existem constantes especiais em C, como sublinhado LINHA sublinhado,

842
01:09:29,410 --> 01:09:31,710
2 underscores LINHA sublinhado,

843
01:09:31,710 --> 01:09:37,550
e há também acho que 2 underscores FUNC. Isso pode ser isso. Algo assim.

844
01:09:37,550 --> 01:09:40,880
Estas coisas será substituído com o nome da função

845
01:09:40,880 --> 01:09:42,930
ou o número da linha que você está.

846
01:09:42,930 --> 01:09:48,630
Freqüentemente, você escreve printfs depuração que aqui eu poderia então apenas escrever

847
01:09:48,630 --> 01:09:54,260
DEBUG e ele será impresso o número da linha e função que acontecer de eu estar no

848
01:09:54,260 --> 01:09:57,020
que encontrou que a declaração DEBUG.

849
01:09:57,020 --> 01:09:59,550
E você também pode imprimir outras coisas.

850
01:09:59,550 --> 01:10:05,990
Então, uma coisa que você deve observar é se acontecer de eu # define DOUBLE_MAX

851
01:10:05,990 --> 01:10:11,380
como algo como 2 * y e 2 * x.

852
01:10:11,380 --> 01:10:14,310
Assim, por razão alguma, acontecer de você fazer isso muito.

853
01:10:14,310 --> 01:10:16,650
Então faça uma macro.

854
01:10:16,650 --> 01:10:18,680
Esta é realmente quebrado.

855
01:10:18,680 --> 01:10:23,050
Eu diria que é, fazendo algo como DOUBLE_MAX (3, 6).

856
01:10:23,050 --> 01:10:27,530
Então, o que deve ser devolvido?

857
01:10:28,840 --> 01:10:30,580
[Estudante] 12.

858
01:10:30,580 --> 01:10:34,800
Sim, 12 devem ser devolvidos, e 12 é devolvido.

859
01:10:34,800 --> 01:10:43,350
3 é substituído por x, 6 é substituído por y, e voltamos 2 * 6, que é 12.

860
01:10:43,350 --> 01:10:47,710
Agora, o que sobre isso? O que deve ser devolvido?

861
01:10:47,710 --> 01:10:50,330
[Estudante] 14. >> Idealmente, 14.

862
01:10:50,330 --> 01:10:55,290
A questão é que, como define o trabalho de hash, lembre-se que é uma cópia literal e colar

863
01:10:55,290 --> 01:11:00,160
de praticamente tudo, então o que é que isto vai ser interpretado como

864
01:11:00,160 --> 01:11:11,270
3 é inferior a 1, mais 6, 2 vezes 1 mais 6, 2 vezes 3.

865
01:11:11,270 --> 01:11:19,780
>> Assim, por esta razão, você quase sempre embrulhar tudo entre parênteses.

866
01:11:22,180 --> 01:11:25,050
Qualquer variável que quase sempre embrulhe em parênteses.

867
01:11:25,050 --> 01:11:29,570
Há casos em que você não tem que, como eu sei que eu não preciso fazer isso aqui

868
01:11:29,570 --> 01:11:32,110
porque menos do que é praticamente sempre vai funcionar,

869
01:11:32,110 --> 01:11:34,330
apesar de que pode até não ser verdade.

870
01:11:34,330 --> 01:11:41,870
Se há algo ridículo como DOUBLE_MAX (1 == 2),

871
01:11:41,870 --> 01:11:49,760
então que vai ficar substituído por 3 é igual a menos de 1 é igual a 2,

872
01:11:49,760 --> 01:11:53,460
E então ele vai fazer 3 menor que 1, isso igual a 2,

873
01:11:53,460 --> 01:11:55,620
o que não é o que queremos.

874
01:11:55,620 --> 01:12:00,730
Portanto, a fim de evitar quaisquer problemas de precedência de operadores,

875
01:12:00,730 --> 01:12:02,870
sempre embrulhe em parênteses.

876
01:12:03,290 --> 01:12:07,700
Okay. E é isso, 5:30.

877
01:12:08,140 --> 01:12:12,470
Se você tem alguma dúvida sobre o pset, avise-nos.

878
01:12:12,470 --> 01:12:18,010
Deve ser divertido, ea edição hacker também é muito mais realista

879
01:12:18,010 --> 01:12:22,980
do que a edição hacker do ano passado, por isso esperamos que um monte de você tentar.

880
01:12:22,980 --> 01:12:26,460
No ano passado, foi muito grande.

881
01:12:28,370 --> 01:12:30,000
>> [CS50.TV]