1
00:00:00,000 --> 00:00:05,830

2
00:00:05,830 --> 00:00:07,910
>> Tudo bem, então, a complexidade computacional.

3
00:00:07,910 --> 00:00:10,430
Basta um pouco de um aviso
antes de mergulhar em muito far--

4
00:00:10,430 --> 00:00:13,070
este provavelmente estará entre
as coisas mais matemática-pesados

5
00:00:13,070 --> 00:00:14,200
falamos em CS50.

6
00:00:14,200 --> 00:00:16,950
Esperemos que isso não vai ser muito esmagadora
e vamos tentar e guiá-lo

7
00:00:16,950 --> 00:00:19,200
através do processo, mas
apenas um pouco de um aviso justo.

8
00:00:19,200 --> 00:00:21,282
Há um pouco
de matemática envolvida aqui.

9
00:00:21,282 --> 00:00:23,990
Tudo bem, então, a fim de torná-
uso de nossos recursos computacionais

10
00:00:23,990 --> 00:00:28,170
no real mundo-- é realmente
importante compreender algoritmos

11
00:00:28,170 --> 00:00:30,750
e como eles processam dados.

12
00:00:30,750 --> 00:00:32,810
Se temos uma realmente
algoritmo eficiente, nós

13
00:00:32,810 --> 00:00:36,292
pode minimizar a quantidade de recursos
que temos disponíveis para lidar com ele.

14
00:00:36,292 --> 00:00:38,750
Se tivermos um algoritmo que
vai levar um monte de trabalho

15
00:00:38,750 --> 00:00:41,210
para processar um realmente
grande conjunto de dados, é

16
00:00:41,210 --> 00:00:44,030
vai exigir mais
e mais recursos, que

17
00:00:44,030 --> 00:00:47,980
é dinheiro, RAM, todo esse tipo de coisa.

18
00:00:47,980 --> 00:00:52,090
>> Assim, ser capaz de analisar uma
algoritmo usando este conjunto de ferramentas,

19
00:00:52,090 --> 00:00:56,110
basicamente, pede ao question--
como é que este algoritmo de escala

20
00:00:56,110 --> 00:00:59,020
como nós jogamos mais e mais dados a ele?

21
00:00:59,020 --> 00:01:02,220
Em CS50, a quantidade de dados que estamos
trabalhando com é muito pequena.

22
00:01:02,220 --> 00:01:05,140
Geralmente, nossos programas estão indo
para executar em um segundo ou less--

23
00:01:05,140 --> 00:01:07,830
provavelmente muito menos
particularmente desde o início.

24
00:01:07,830 --> 00:01:12,250
>> Mas pense sobre uma empresa que lida
com centenas de milhões de clientes.

25
00:01:12,250 --> 00:01:14,970
E eles precisam para processar
que os dados do cliente.

26
00:01:14,970 --> 00:01:18,260
À medida que o número de clientes que eles
tem se torna maior e maior,

27
00:01:18,260 --> 00:01:21,230
que vai exigir
mais e mais recursos.

28
00:01:21,230 --> 00:01:22,926
Quantas mais recursos?

29
00:01:22,926 --> 00:01:25,050
Bem, isso depende de como
analisamos o algoritmo,

30
00:01:25,050 --> 00:01:28,097
usando as ferramentas nesta caixa de ferramentas.

31
00:01:28,097 --> 00:01:31,180
Quando falamos sobre a complexidade da
um algorithm-- que às vezes você vai

32
00:01:31,180 --> 00:01:34,040
ouvi-lo referido como tempo
complexidade ou espaço complexidade

33
00:01:34,040 --> 00:01:36,190
mas nós apenas estamos indo
para chamar complexity--

34
00:01:36,190 --> 00:01:38,770
nós estamos geralmente falando
o pior cenário.

35
00:01:38,770 --> 00:01:42,640
Dada a pior absoluta de pilha
dados que poderia estar jogando para ele,

36
00:01:42,640 --> 00:01:46,440
como é que isto vai algoritmo
processar ou lidar com esses dados?

37
00:01:46,440 --> 00:01:51,450
Nós geralmente chamar o pior caso
tempo de execução de um algoritmo big-O.

38
00:01:51,450 --> 00:01:56,770
Assim, um algoritmo pode ser dito
executado em O de n ou o de n ao quadrado.

39
00:01:56,770 --> 00:01:59,110
E mais sobre o que
aqueles dizer em um segundo.

40
00:01:59,110 --> 00:02:01,620
>> Às vezes, porém, nós nos importamos
sobre o melhor cenário.

41
00:02:01,620 --> 00:02:05,400
Se os dados forem tudo o que queríamos
que seja e foi absolutamente perfeito

42
00:02:05,400 --> 00:02:09,630
e nós estávamos enviando este perfeito
conjunto de dados através do nosso algoritmo.

43
00:02:09,630 --> 00:02:11,470
Como ele iria lidar nessa situação?

44
00:02:11,470 --> 00:02:15,050
Nós às vezes se referem a isso como
big-Omega, portanto, em contraste com o big-O,

45
00:02:15,050 --> 00:02:16,530
temos big-Omega.

46
00:02:16,530 --> 00:02:18,880
Big-Omega para o melhor cenário.

47
00:02:18,880 --> 00:02:21,319
Big-O para o pior cenário.

48
00:02:21,319 --> 00:02:23,860
Geralmente, quando falamos de
a complexidade de um algoritmo,

49
00:02:23,860 --> 00:02:26,370
nós estamos falando sobre o
pior cenário.

50
00:02:26,370 --> 00:02:28,100
Portanto, manter isso em mente.

51
00:02:28,100 --> 00:02:31,510
>> E nesta classe, vamos geral
para deixar a análise rigorosa de lado.

52
00:02:31,510 --> 00:02:35,350
Há ciências e campos
dedicada a este tipo de coisa.

53
00:02:35,350 --> 00:02:37,610
Quando falamos de raciocínio
por meio de algoritmos,

54
00:02:37,610 --> 00:02:41,822
que nós vamos fazer peça por peça para muitos
algoritmos falamos na classe.

55
00:02:41,822 --> 00:02:44,780
Nós realmente estamos falando apenas de
raciocinando através dele com o senso comum,

56
00:02:44,780 --> 00:02:47,070
não com fórmulas, ou provas,
ou qualquer coisa assim.

57
00:02:47,070 --> 00:02:51,600
Então não se preocupe, nós não será
transformando-se em uma classe grande de matemática.

58
00:02:51,600 --> 00:02:55,920
>> Então eu disse: nós nos preocupamos com a complexidade
porque ele faz a pergunta, como

59
00:02:55,920 --> 00:03:00,160
que nossos algoritmos lidar com maior e
maiores conjuntos de dados que está sendo jogado neles.

60
00:03:00,160 --> 00:03:01,960
Bem, o que é um conjunto de dados?

61
00:03:01,960 --> 00:03:03,910
O que eu quero dizer quando eu disse isso?

62
00:03:03,910 --> 00:03:07,600
Isso significa que tudo o que faz mais
sentido no contexto, para ser honesto.

63
00:03:07,600 --> 00:03:11,160
Se tivermos um algoritmo, o
Processos Strings-- estamos provavelmente

64
00:03:11,160 --> 00:03:13,440
falando sobre o tamanho da cadeia.

65
00:03:13,440 --> 00:03:15,190
Isso é os dados set--
o tamanho, o número

66
00:03:15,190 --> 00:03:17,050
de personagens que compõem a cadeia.

67
00:03:17,050 --> 00:03:20,090
Se estamos falando de um
algoritmo que processa arquivos,

68
00:03:20,090 --> 00:03:23,930
poderíamos estar falando sobre como
muitos kilobytes compreendem esse arquivo.

69
00:03:23,930 --> 00:03:25,710
E esse é o conjunto de dados.

70
00:03:25,710 --> 00:03:28,870
Se estamos falando de um algoritmo
que lida com matrizes de uma forma mais geral,

71
00:03:28,870 --> 00:03:31,510
tais como algoritmos de classificação
ou pesquisar algoritmos,

72
00:03:31,510 --> 00:03:36,690
nós provavelmente estamos falando sobre o número
de elementos que compreendem uma matriz.

73
00:03:36,690 --> 00:03:39,272
>> Agora, podemos medir um
algorithm-- em particular,

74
00:03:39,272 --> 00:03:40,980
quando eu digo que pudermos
medir um algoritmo, I

75
00:03:40,980 --> 00:03:43,840
significa que podemos medir o quão
muitos recursos que ele ocupa.

76
00:03:43,840 --> 00:03:48,990
Se esses recursos são, quantos
bytes de RAM-- ou megabytes de memória RAM

77
00:03:48,990 --> 00:03:49,790
ele usa.

78
00:03:49,790 --> 00:03:52,320
Ou quanto tempo leva para executar.

79
00:03:52,320 --> 00:03:56,200
E nós podemos chamar isso de
medir, de forma arbitrária, de f n.

80
00:03:56,200 --> 00:03:59,420
Onde n é o número de
elementos do conjunto de dados.

81
00:03:59,420 --> 00:04:02,640
E f de n é o número de qualquer coisa.

82
00:04:02,640 --> 00:04:07,530
Quantas unidades de recursos faz
que exigem a processar esses dados.

83
00:04:07,530 --> 00:04:10,030
>> Agora, nós realmente não me importo
sobre o que f de n é exatamente.

84
00:04:10,030 --> 00:04:13,700
Na verdade, nós muito raramente will--
certamente nunca vai neste I class--

85
00:04:13,700 --> 00:04:18,709
mergulhar em qualquer realmente profundo
análise do que f de n é.

86
00:04:18,709 --> 00:04:23,510
Nós só vamos falar sobre o que f de
n é aproximadamente ou o que tende a.

87
00:04:23,510 --> 00:04:27,600
E a tendência de um algoritmo é
ditada pela sua mais alta expressão fim.

88
00:04:27,600 --> 00:04:29,440
E podemos ver o que eu
entendemos por que, ao tomar

89
00:04:29,440 --> 00:04:31,910
uma olhada em um exemplo mais concreto.

90
00:04:31,910 --> 00:04:34,620
>> Então, vamos dizer que temos
três algoritmos diferentes.

91
00:04:34,620 --> 00:04:39,350
O primeiro dos quais tem N
cubos, algumas unidades de recursos

92
00:04:39,350 --> 00:04:42,880
para processar um conjunto de tamanho n dados.

93
00:04:42,880 --> 00:04:47,000
Temos um segundo algoritmo que leva
n cubos mais recursos n ao quadrado

94
00:04:47,000 --> 00:04:49,350
para processar um conjunto de tamanho n dados.

95
00:04:49,350 --> 00:04:52,030
E nós temos uma terceira
algoritmo que corre que em--

96
00:04:52,030 --> 00:04:58,300
ocupa n cubos menos 8N quadrado
n mais de 20 unidades de recursos

97
00:04:58,300 --> 00:05:02,370
para processar um algoritmo
com o conjunto de tamanho n dados.

98
00:05:02,370 --> 00:05:05,594
>> Agora, novamente, nós realmente não estão indo
para chegar a este nível de detalhe.

99
00:05:05,594 --> 00:05:08,260
Estou realmente só tem estes acima
aqui como uma ilustração de um ponto

100
00:05:08,260 --> 00:05:10,176
que eu vou ser
tornando num segundo, o que

101
00:05:10,176 --> 00:05:12,980
é que só realmente se importa
sobre a tendência das coisas

102
00:05:12,980 --> 00:05:14,870
como os conjuntos de dados ficar maior.

103
00:05:14,870 --> 00:05:18,220
Portanto, se o conjunto de dados é pequeno, não há
na verdade, uma diferença muito grande

104
00:05:18,220 --> 00:05:19,870
nestes algoritmos.

105
00:05:19,870 --> 00:05:23,000
O terceiro algoritmo lá
leva 13 vezes mais tempo,

106
00:05:23,000 --> 00:05:27,980
13 vezes a quantidade de recursos
para rodar em relação à primeira.

107
00:05:27,980 --> 00:05:31,659
>> Se o nosso conjunto de dados é o tamanho 10, que
é maior, mas não necessariamente grande,

108
00:05:31,659 --> 00:05:33,950
podemos ver que não há
na verdade, um pouco de diferença.

109
00:05:33,950 --> 00:05:36,620
O terceiro algoritmo
torna-se mais eficiente.

110
00:05:36,620 --> 00:05:40,120
Trata-se de, na verdade, 40% -
ou 60% mais eficiente.

111
00:05:40,120 --> 00:05:41,580
Leva 40% a quantidade de tempo.

112
00:05:41,580 --> 00:05:45,250
Pode run-- pode demorar
400 unidades de recursos

113
00:05:45,250 --> 00:05:47,570
para processar um conjunto de tamanho 10 dados.

114
00:05:47,570 --> 00:05:49,410
Considerando que o primeiro
algoritmo, por contraste,

115
00:05:49,410 --> 00:05:54,520
leva 1.000 unidades de recursos
para processar um conjunto de tamanho 10 dados.

116
00:05:54,520 --> 00:05:57,240
Mas veja o que acontece como
nossos números ficar ainda maior.

117
00:05:57,240 --> 00:05:59,500
>> Agora, a diferença
entre estes algoritmos

118
00:05:59,500 --> 00:06:01,420
começam a se tornar um pouco menos aparente.

119
00:06:01,420 --> 00:06:04,560
E o facto de que existem
de ordem inferior terms-- ou melhor,

120
00:06:04,560 --> 00:06:09,390
termos de menor exponents--
começam a se tornar irrelevante.

121
00:06:09,390 --> 00:06:12,290
Se um conjunto de dados é de tamanho
1000 e o primeiro algoritmo

122
00:06:12,290 --> 00:06:14,170
é executado em um bilhão de passos.

123
00:06:14,170 --> 00:06:17,880
E o segundo algoritmo roda em
um bilhão e um milhão de passos.

124
00:06:17,880 --> 00:06:20,870
E o terceiro algoritmo roda
em pouco menos de um bilhão de passos.

125
00:06:20,870 --> 00:06:22,620
É praticamente um bilhão de passos.

126
00:06:22,620 --> 00:06:25,640
Esses termos de ordem mais baixa começar
para se tornar realmente irrelevante.

127
00:06:25,640 --> 00:06:27,390
E só para realmente
martelo casa o ponto--

128
00:06:27,390 --> 00:06:31,240
se a entrada de dados é de tamanho um
milhões-- todos os três destes praticamente

129
00:06:31,240 --> 00:06:34,960
tomar um quintillion-- se
minha matemática é passos correct--

130
00:06:34,960 --> 00:06:37,260
para processar uma entrada de dados
tamanho de um milhão.

131
00:06:37,260 --> 00:06:38,250
Isso é um monte de etapas.

132
00:06:38,250 --> 00:06:42,092
E o fato de que um deles poderia
levar um par 100.000, ou um casal 100

133
00:06:42,092 --> 00:06:44,650
milhões ainda menos quando
estamos falando de um número

134
00:06:44,650 --> 00:06:46,990
big-- que é uma espécie de irrelevante.

135
00:06:46,990 --> 00:06:50,006
Todos eles tendem a tomar
aproximadamente n cubado,

136
00:06:50,006 --> 00:06:52,380
e por isso seria verdade se referem
para todos estes algoritmos

137
00:06:52,380 --> 00:06:59,520
como sendo da ordem de n
cubos ou big-O de n em cubos.

138
00:06:59,520 --> 00:07:03,220
>> Aqui está uma lista de alguns dos mais
classes de complexidade computacional comuns

139
00:07:03,220 --> 00:07:05,820
que vamos encontrar em
algoritmos, geralmente.

140
00:07:05,820 --> 00:07:07,970
E também, especificamente, no CS50.

141
00:07:07,970 --> 00:07:11,410
Estes são ordenados a partir de
geralmente mais rápido na parte superior,

142
00:07:11,410 --> 00:07:13,940
de forma geral, mais lento na parte inferior.

143
00:07:13,940 --> 00:07:16,920
Então, algoritmos de tempo constante tendem
ser o mais rápido, independentemente

144
00:07:16,920 --> 00:07:19,110
do tamanho do
entrada de dados que você passar em.

145
00:07:19,110 --> 00:07:23,760
Eles sempre têm uma operação ou
uma unidade de recursos para lidar com eles.

146
00:07:23,760 --> 00:07:25,730
Pode ser 2, que poderia
ser 3, pode ser 4.

147
00:07:25,730 --> 00:07:26,910
Mas é um número constante.

148
00:07:26,910 --> 00:07:28,400
Ele não varia.

149
00:07:28,400 --> 00:07:31,390
>> Algoritmos de tempo logarítmicas
são ligeiramente melhores.

150
00:07:31,390 --> 00:07:33,950
E realmente um bom exemplo de
um algoritmo de tempo logarítmica

151
00:07:33,950 --> 00:07:37,420
você certamente visto até agora é o
dilacerando do livro de telefone

152
00:07:37,420 --> 00:07:39,480
para encontrar Mike Smith no livro de telefone.

153
00:07:39,480 --> 00:07:40,980
Nós cortar o problema pela metade.

154
00:07:40,980 --> 00:07:43,580
E assim como n fica maior
e maior e larger--

155
00:07:43,580 --> 00:07:47,290
na verdade, cada vez que você dobrar
n, ele só tem mais um passo.

156
00:07:47,290 --> 00:07:49,770
Então, isso é muito melhor
do que, digamos, o tempo linear.

157
00:07:49,770 --> 00:07:53,030
Que é se você dobrar n, ele
leva o dobro do número de etapas.

158
00:07:53,030 --> 00:07:55,980
Se você triplicar n, é preciso
triplicar o número de passos.

159
00:07:55,980 --> 00:07:58,580
Um passo por unidade.

160
00:07:58,580 --> 00:08:01,790
>> Em seguida, as coisas ficam um pouco more--
pouco menos grande de lá.

161
00:08:01,790 --> 00:08:06,622
Você tem tempo rítmica linear, por vezes,
chamado registro de tempo linear ou apenas n log n.

162
00:08:06,622 --> 00:08:08,330
E nós vamos um exemplo
de um algoritmo que

163
00:08:08,330 --> 00:08:13,370
é executado em n log n, que é ainda melhor
do que quadrática tempo-- n ao quadrado.

164
00:08:13,370 --> 00:08:17,320
Ou tempo polinomial, n dois
qualquer número maior do que dois.

165
00:08:17,320 --> 00:08:20,810
Ou tempo exponencial, o que
é ainda worse-- C ao n.

166
00:08:20,810 --> 00:08:24,670
Assim, um número constante e elevada a
a potência do tamanho da entrada.

167
00:08:24,670 --> 00:08:28,990
Portanto, se há 1,000-- se o
entrada de dados é de tamanho 1.000,

168
00:08:28,990 --> 00:08:31,310
demoraria C ao poder 1000.

169
00:08:31,310 --> 00:08:33,559
É muito pior do que tempo polinomial.

170
00:08:33,559 --> 00:08:35,030
>> Tempo fatorial é ainda pior.

171
00:08:35,030 --> 00:08:37,760
E, de fato, não há realmente fazer
existem algoritmos de tempo infinito,

172
00:08:37,760 --> 00:08:43,740
tais como, assim chamada sort-- burro cuja
trabalho é para embaralhar aleatoriamente um array

173
00:08:43,740 --> 00:08:45,490
e, em seguida, verificar para ver
se ele está classificado.

174
00:08:45,490 --> 00:08:47,589
E se não é, de forma aleatória
embaralhar a matriz novamente

175
00:08:47,589 --> 00:08:49,130
e verificar para ver se ele está classificado.

176
00:08:49,130 --> 00:08:51,671
E como você provavelmente pode imagine--
você pode imaginar uma situação

177
00:08:51,671 --> 00:08:55,200
onde, no pior caso, que a vontade
nunca realmente começar com a matriz.

178
00:08:55,200 --> 00:08:57,150
Algoritmo que iria correr para sempre.

179
00:08:57,150 --> 00:08:59,349
E para que seria um
algoritmo de tempo infinito.

180
00:08:59,349 --> 00:09:01,890
Espero que você não vai ser escrito
qualquer momento factorial ou infinito

181
00:09:01,890 --> 00:09:04,510
algoritmos em CS50.

182
00:09:04,510 --> 00:09:09,150
>> Então, vamos ter um pouco mais
olhar em algum concreto simples

183
00:09:09,150 --> 00:09:11,154
classes de complexidade computacional.

184
00:09:11,154 --> 00:09:13,070
Portanto, temos um example--
ou dois exemplos aqui--

185
00:09:13,070 --> 00:09:15,590
algoritmos de tempo constantes,
que sempre tomar

186
00:09:15,590 --> 00:09:17,980
uma única operação no pior caso.

187
00:09:17,980 --> 00:09:20,050
Assim, o primeiro example--
nós temos uma função

188
00:09:20,050 --> 00:09:23,952
4 chamado para você, que
recebe um array de tamanho 1.000.

189
00:09:23,952 --> 00:09:25,660
Mas então, aparentemente,
não realmente olhar

190
00:09:25,660 --> 00:09:29,000
a ele-- não se importa realmente o que é
dentro dele, desse array.

191
00:09:29,000 --> 00:09:30,820
Sempre retorna apenas quatro.

192
00:09:30,820 --> 00:09:32,940
Então, esse algoritmo,
apesar do facto de que ele

193
00:09:32,940 --> 00:09:35,840
leva 1.000 elementos não
fazer nada com eles.

194
00:09:35,840 --> 00:09:36,590
Retorna apenas quatro.

195
00:09:36,590 --> 00:09:38,240
É sempre uma única etapa.

196
00:09:38,240 --> 00:09:41,600
>> Na verdade, adicionar 2 nums-- que
que já vimos antes como bom--

197
00:09:41,600 --> 00:09:43,680
apenas processa dois inteiros.

198
00:09:43,680 --> 00:09:44,692
Não é uma única etapa.

199
00:09:44,692 --> 00:09:45,900
É realmente um par etapas.

200
00:09:45,900 --> 00:09:50,780
Você ganha um, você começa b, você adicioná-los
juntos, e você saída dos resultados.

201
00:09:50,780 --> 00:09:53,270
Então é 84 passos.

202
00:09:53,270 --> 00:09:55,510
Mas é sempre constante,
independentemente de a ou b.

203
00:09:55,510 --> 00:09:59,240
Você tem que chegar a, b começar, adicione
-los em conjunto, o resultado de saída.

204
00:09:59,240 --> 00:10:02,900
Então isso é um algoritmo de tempo constante.

205
00:10:02,900 --> 00:10:05,170
>> Aqui está um exemplo de um
algorithm-- tempo linear

206
00:10:05,170 --> 00:10:08,740
que um algoritmo que leva gets--
um passo adicional, possivelmente,

207
00:10:08,740 --> 00:10:10,740
como sua entrada cresce 1.

208
00:10:10,740 --> 00:10:14,190
Então, vamos dizer que estamos procurando
o número 5 para dentro de uma matriz.

209
00:10:14,190 --> 00:10:16,774
Você pode ter uma situação em que
você pode encontrá-lo bastante cedo.

210
00:10:16,774 --> 00:10:18,606
Mas você também pode ter
uma situação onde

211
00:10:18,606 --> 00:10:20,450
pode ser o último elemento da matriz.

212
00:10:20,450 --> 00:10:23,780
Em uma matriz de tamanho 5, se
nós estamos olhando para o número 5.

213
00:10:23,780 --> 00:10:25,930
Levaria 5 passos.

214
00:10:25,930 --> 00:10:29,180
E, de fato, imaginar que há
5 não em qualquer lugar nessa matriz.

215
00:10:29,180 --> 00:10:32,820
Nós ainda realmente tem que olhar para
cada elemento da matriz

216
00:10:32,820 --> 00:10:35,550
a fim de determinar
5 ou não existe.

217
00:10:35,550 --> 00:10:39,840
>> Assim, no pior caso, que é que
o elemento é o último na matriz

218
00:10:39,840 --> 00:10:41,700
ou não existe de todo.

219
00:10:41,700 --> 00:10:44,690
Nós ainda temos de olhar para
todos os n elementos.

220
00:10:44,690 --> 00:10:47,120
E assim este algoritmo
executa em tempo linear.

221
00:10:47,120 --> 00:10:50,340
Você pode confirmar que,
extrapolando um pouco, dizendo:

222
00:10:50,340 --> 00:10:53,080
se tivéssemos uma matriz de 6 elementos e
estávamos procurando o número 5,

223
00:10:53,080 --> 00:10:54,890
isso pode levar 6 etapas.

224
00:10:54,890 --> 00:10:57,620
Se nós temos uma matriz de 7-elemento e
nós estamos olhando para o número 5.

225
00:10:57,620 --> 00:10:59,160
Pode levar 7 passos.

226
00:10:59,160 --> 00:11:02,920
À medida que adicionamos mais um elemento para a nossa
matriz, ele dá mais um passo.

227
00:11:02,920 --> 00:11:06,750
Isso é um algoritmo linear
no pior caso.

228
00:11:06,750 --> 00:11:08,270
>> Casal perguntas rápidas para você.

229
00:11:08,270 --> 00:11:11,170
Qual é a runtime-- o que é
o pior caso de tempo de execução

230
00:11:11,170 --> 00:11:13,700
deste trecho de código específico?

231
00:11:13,700 --> 00:11:17,420
Então, eu tenho um loop de 4 aqui que é executado
de j é igual a 0, todo o caminho até m.

232
00:11:17,420 --> 00:11:21,980
E o que eu estou vendo aqui, é que o
corpo do laço é executado em tempo constante.

233
00:11:21,980 --> 00:11:24,730
Então, usando a terminologia que
nós já falamos o que about--

234
00:11:24,730 --> 00:11:29,390
seria o pior caso
tempo de execução deste algoritmo?

235
00:11:29,390 --> 00:11:31,050
Tome um segundo.

236
00:11:31,050 --> 00:11:34,270
A parte interna do lacete
é executado em tempo constante.

237
00:11:34,270 --> 00:11:37,510
E a parte externa do
loop está indo para executar m vezes.

238
00:11:37,510 --> 00:11:40,260
Então, qual é o pior caso de tempo de execução aqui?

239
00:11:40,260 --> 00:11:43,210
Será que você adivinha big-O de m?

240
00:11:43,210 --> 00:11:44,686
Você estaria certo.

241
00:11:44,686 --> 00:11:46,230
>> Como cerca de um outro?

242
00:11:46,230 --> 00:11:48,590
Desta vez temos um
loop dentro de um loop.

243
00:11:48,590 --> 00:11:50,905
Nós temos um laço externo
que vai de zero a p.

244
00:11:50,905 --> 00:11:54,630
E nós temos um loop interno que é executado
de zero a P, e dentro de que,

245
00:11:54,630 --> 00:11:57,890
Afirmo que o corpo do
loop é executado em tempo constante.

246
00:11:57,890 --> 00:12:02,330
Então, qual é o pior caso de tempo de execução
deste trecho de código específico?

247
00:12:02,330 --> 00:12:06,140
Bem, mais uma vez, temos um
loop externo que corre p vezes.

248
00:12:06,140 --> 00:12:09,660
E cada iteração tempo--
de malha que, em vez.

249
00:12:09,660 --> 00:12:13,170
Nós temos um laço interno
que também executa p vezes.

250
00:12:13,170 --> 00:12:16,900
E, em seguida, dentro disso, há o
constante pequeno trecho tempo-- lá.

251
00:12:16,900 --> 00:12:19,890
>> Então, se temos um circuito externo que
p é executado vezes dentro dos quais é

252
00:12:19,890 --> 00:12:22,880
um loop interno que
p é executado o que é vezes--

253
00:12:22,880 --> 00:12:26,480
o pior caso de tempo de execução
de esse trecho de código?

254
00:12:26,480 --> 00:12:30,730
Será que você adivinha big-O de p quadrado?

255
00:12:30,730 --> 00:12:31,690
>> Eu sou Doug Lloyd.

256
00:12:31,690 --> 00:12:33,880
Este é CS50.

257
00:12:33,880 --> 00:12:35,622