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

2
00:00:05,830 --> 00:00:07,910
>> Todo ben, entón, a complexidade computacional.

3
00:00:07,910 --> 00:00:10,430
Tan só un pouco de un aviso
antes de mergullo moito far--

4
00:00:10,430 --> 00:00:13,070
este probablemente estará entre
as cousas máis matemática pesados

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

6
00:00:14,200 --> 00:00:16,950
Esperemos que isto non vai ser moi esmagadora
e imos tratar e guía-lo

7
00:00:16,950 --> 00:00:19,200
a través do proceso, pero
só un pouco de un aviso xusto.

8
00:00:19,200 --> 00:00:21,282
Hai un pouco
de matemática aquí.

9
00:00:21,282 --> 00:00:23,990
Todo ben, entón, a fin de torná-
uso dos nosos recursos computacionais

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

11
00:00:28,170 --> 00:00:30,750
e como procesan datos.

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

13
00:00:32,810 --> 00:00:36,292
pode minimizar a cantidade de recursos
que temos dispoñibles para tratar con el.

14
00:00:36,292 --> 00:00:38,750
Se temos un algoritmo que
vai levar unha chea de traballo

15
00:00:38,750 --> 00:00:41,210
para procesar un realmente
gran conxunto de datos, é

16
00:00:41,210 --> 00:00:44,030
vai esixir máis
e máis recursos, que

17
00:00:44,030 --> 00:00:47,980
é diñeiro, RAM, todo este tipo de cousas.

18
00:00:47,980 --> 00:00:52,090
>> Así, ser capaz de analizar unha
algoritmo usando este conxunto de ferramentas,

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

20
00:00:56,110 --> 00:00:59,020
como xogamos máis e máis datos a el?

21
00:00:59,020 --> 00:01:02,220
En CS50, a cantidade de datos que estamos
traballando con é moi pequena.

22
00:01:02,220 --> 00:01:05,140
Xeralmente, os nosos programas van
para realizar un segundo ou less--

23
00:01:05,140 --> 00:01:07,830
probablemente moito menos
particularmente desde o principio.

24
00:01:07,830 --> 00:01:12,250
>> Pero pense sobre unha empresa que trata
con centos de millóns de clientes.

25
00:01:12,250 --> 00:01:14,970
E precisan para procesar
que os datos do cliente.

26
00:01:14,970 --> 00:01:18,260
A medida que o número de clientes que
ten se fai maior e máis grande,

27
00:01:18,260 --> 00:01:21,230
que vai esixir
máis e máis recursos.

28
00:01:21,230 --> 00:01:22,926
Cantas máis recursos?

29
00:01:22,926 --> 00:01:25,050
Ben, iso depende de como
analizamos o algoritmo,

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

31
00:01:28,097 --> 00:01:31,180
Cando falamos sobre a complexidade da
un algorithm-- que ás veces vai

32
00:01:31,180 --> 00:01:34,040
ouvídelo chamada tempo
complexidade ou espazo complexidade

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

34
00:01:36,190 --> 00:01:38,770
estamos xeralmente falando
o peor escenario.

35
00:01:38,770 --> 00:01:42,640
Dada a peor absoluta de pila
datos que podería estar xogando para el,

36
00:01:42,640 --> 00:01:46,440
como é que isto vai algoritmo
procesar ou tratar con estes datos?

37
00:01:46,440 --> 00:01:51,450
Nós xeralmente chamar o peor caso
tempo de execución dun algoritmo big-O.

38
00:01:51,450 --> 00:01:56,770
Así, un algoritmo pode ser dito
executado en O n ou o de n ao cadrado.

39
00:01:56,770 --> 00:01:59,110
E máis sobre o que
aqueles dicir nun segundo.

40
00:01:59,110 --> 00:02:01,620
>> Ás veces, porén, nos importa
sobre o mellor escenario.

41
00:02:01,620 --> 00:02:05,400
Se os datos son todo o que queriamos
que sexa e foi absolutamente perfecto

42
00:02:05,400 --> 00:02:09,630
e que estaban enviando este perfecto
conxunto de datos a través do noso algoritmo.

43
00:02:09,630 --> 00:02:11,470
Como ía tratar nesta situación?

44
00:02:11,470 --> 00:02:15,050
Nós ás veces se refiren a iso como
big-Omega, polo tanto, en contraste co 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 mellor escenario.

47
00:02:18,880 --> 00:02:21,319
Big-O para o peor escenario.

48
00:02:21,319 --> 00:02:23,860
Xeralmente, cando falamos de
a complexidade dun algoritmo,

49
00:02:23,860 --> 00:02:26,370
estamos a falar sobre o
peor escenario.

50
00:02:26,370 --> 00:02:28,100
Polo tanto, manter isto presente.

51
00:02:28,100 --> 00:02:31,510
>> E nesta clase, imos xeral
para deixar a análise rigorosa de lado.

52
00:02:31,510 --> 00:02:35,350
Hai ciencias e campos
dedicada a este tipo de cousas.

53
00:02:35,350 --> 00:02:37,610
Cando falamos de razoamento
por medio de algoritmos,

54
00:02:37,610 --> 00:02:41,822
que nós imos facer peza por peza para moitos
algoritmos falamos na clase.

55
00:02:41,822 --> 00:02:44,780
Nós realmente estamos falando só de
raciocinando través del co sentido común,

56
00:02:44,780 --> 00:02:47,070
non con fórmulas, ou probas,
ou algo así.

57
00:02:47,070 --> 00:02:51,600
Non te preocupes, non será
transformando-se nunha clase grande de matemáticas.

58
00:02:51,600 --> 00:02:55,920
>> Entón eu dixen: nós nos preocupa coa complexidade
porque fai a pregunta, como

59
00:02:55,920 --> 00:03:00,160
que os nosos algoritmos xestionar maior e
maiores conxuntos de datos que está a ser xogado neles.

60
00:03:00,160 --> 00:03:01,960
Ben, o que é un conxunto de datos?

61
00:03:01,960 --> 00:03:03,910
O que quero dicir cando dixo iso?

62
00:03:03,910 --> 00:03:07,600
Isto significa que todo o que fai máis
sentido no contexto, para ser honesto.

63
00:03:07,600 --> 00:03:11,160
Se temos un algoritmo, o
Procesos Strings-- estamos probablemente

64
00:03:11,160 --> 00:03:13,440
falando sobre o tamaño da cadea.

65
00:03:13,440 --> 00:03:15,190
Iso é os datos set--
o tamaño, o número

66
00:03:15,190 --> 00:03:17,050
de personaxes que compoñen a cadea.

67
00:03:17,050 --> 00:03:20,090
Se estamos a falar dun
algoritmo que procesa arquivos,

68
00:03:20,090 --> 00:03:23,930
poderiamos estar falando como
moitos kilobytes comprenden o ficheiro.

69
00:03:23,930 --> 00:03:25,710
E ese é o conxunto de datos.

70
00:03:25,710 --> 00:03:28,870
Se estamos a falar dun algoritmo
que trata sobre matrices de forma máis xeral,

71
00:03:28,870 --> 00:03:31,510
como algoritmos de clasificación
ou buscar algoritmos,

72
00:03:31,510 --> 00:03:36,690
nós probablemente estamos falando do número
de elementos que comprenden unha matriz.

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

74
00:03:39,272 --> 00:03:40,980
cando digo que pudermos
medir un algoritmo, I

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

76
00:03:43,840 --> 00:03:48,990
Se estes recursos son, cantos
bytes de RAM-- ou megabytes de memoria RAM

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

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

79
00:03:52,320 --> 00:03:56,200
E podemos chamar iso de
medir, de forma arbitraria, f n.

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

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

82
00:04:02,640 --> 00:04:07,530
Cantas unidades de recursos fai
que esixen a procesar eses datos.

83
00:04:07,530 --> 00:04:10,030
>> Agora, nós realmente non me importa
sobre o que f n é exactamente.

84
00:04:10,030 --> 00:04:13,700
En realidade, nós moi raramente will--
certamente non vai neste I class--

85
00:04:13,700 --> 00:04:18,709
mergullo en calquera realmente profundo
análise do que f n é.

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

87
00:04:23,510 --> 00:04:27,600
E a tendencia dun algoritmo é
ditada pola súa máis alta expresión fin.

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

89
00:04:29,440 --> 00:04:31,910
un ollo a un exemplo máis concreto.

90
00:04:31,910 --> 00:04:34,620
>> Entón, imos dicir que temos
tres algoritmos diferentes.

91
00:04:34,620 --> 00:04:39,350
O primeiro dos cales ten N
cubos, algunhas unidades de recursos

92
00:04:39,350 --> 00:04:42,880
para procesar un conxunto de tamaño n datos.

93
00:04:42,880 --> 00:04:47,000
Temos un segundo algoritmo que leva
n cubos máis recursos n ao cadrado

94
00:04:47,000 --> 00:04:49,350
para procesar un conxunto de tamaño n datos.

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

96
00:04:52,030 --> 00:04:58,300
ocupa n cubos menos 8N cadrado
n máis de 20 unidades de recursos

97
00:04:58,300 --> 00:05:02,370
para procesar un algoritmo
co conxunto de tamaño n datos.

98
00:05:02,370 --> 00:05:05,594
>> Agora, de novo, nós realmente non están indo
para chegar a este nivel de detalle.

99
00:05:05,594 --> 00:05:08,260
Estou realmente só ten estes arriba
aquí como unha ilustración dun punto

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

101
00:05:10,176 --> 00:05:12,980
é que só realmente importa
sobre a tendencia das cousas

102
00:05:12,980 --> 00:05:14,870
como os conxuntos de datos queda maior.

103
00:05:14,870 --> 00:05:18,220
Polo tanto, se o conxunto de datos é pequeno, non hai
de feito, unha diferenza moi grande

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

105
00:05:19,870 --> 00:05:23,000
O terceiro algoritmo alí
leva 13 veces máis tempo,

106
00:05:23,000 --> 00:05:27,980
13 veces a cantidade de recursos
para rodar en relación á primeira.

107
00:05:27,980 --> 00:05:31,659
>> O noso conxunto de datos é o tamaño 10, que
é maior, pero non necesariamente grande,

108
00:05:31,659 --> 00:05:33,950
vemos que non hai
en realidade, un pouco de diferenza.

109
00:05:33,950 --> 00:05:36,620
O terceiro algoritmo
faise máis eficiente.

110
00:05:36,620 --> 00:05:40,120
Trátase de, en realidade, o 40% -
ou 60% máis eficiente.

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

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

113
00:05:45,250 --> 00:05:47,570
para procesar un conxunto de tamaño 10 datos.

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

115
00:05:49,410 --> 00:05:54,520
leva 1.000 unidades de recursos
para procesar un conxunto de tamaño 10 datos.

116
00:05:54,520 --> 00:05:57,240
Pero mira o que acontece como
nosos números estar aínda maior.

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

118
00:05:59,500 --> 00:06:01,420
comezan a facer un pouco menos aparente.

119
00:06:01,420 --> 00:06:04,560
E o feito de que hai
de orde inferior terms-- ou mellor,

120
00:06:04,560 --> 00:06:09,390
termos de menor exponents--
comezan a facer irrelevante.

121
00:06:09,390 --> 00:06:12,290
Un conxunto de datos é de tamaño
1000 eo primeiro algoritmo

122
00:06:12,290 --> 00:06:14,170
é executado en mil millóns de pasos.

123
00:06:14,170 --> 00:06:17,880
E o segundo algoritmo roda en
mil millóns e un millón de pasos.

124
00:06:17,880 --> 00:06:20,870
E o terceiro algoritmo roda
en pouco menos de mil millóns de pasos.

125
00:06:20,870 --> 00:06:22,620
É practicamente mil millóns de pasos.

126
00:06:22,620 --> 00:06:25,640
Estes termos de orde máis baixa comezar
para facer 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
a entrada de datos é de tamaño un
milhões-- os tres destes practicamente

129
00:06:31,240 --> 00:06:34,960
tomar un quintillion-- se
miña matemática é pasos correct--

130
00:06:34,960 --> 00:06:37,260
para procesar unha entrada de datos
tamaño dun millón.

131
00:06:37,260 --> 00:06:38,250
Iso é unha chea de pasos.

132
00:06:38,250 --> 00:06:42,092
E o feito de que un deles podería
levar un par 100.000 ou unha parella 100

133
00:06:42,092 --> 00:06:44,650
millóns aínda menos cando
estamos a falar dun número

134
00:06:44,650 --> 00:06:46,990
big-- que é unha especie de irrelevante.

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

136
00:06:50,006 --> 00:06:52,380
e por iso sería verdade se refiren
para todos estes algoritmos

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

138
00:06:59,520 --> 00:07:03,220
>> Aquí está a lista de algúns dos máis
clases de complexidade computacional comúns

139
00:07:03,220 --> 00:07:05,820
que imos atopar en
algoritmos, xeralmente.

140
00:07:05,820 --> 00:07:07,970
E tamén, en concreto, no CS50.

141
00:07:07,970 --> 00:07:11,410
Estes son ordenados a partir de
xeralmente máis rápido na parte superior,

142
00:07:11,410 --> 00:07:13,940
de forma xeral, máis lento na parte inferior.

143
00:07:13,940 --> 00:07:16,920
Entón, algoritmos de tempo constante tenden
ser o máis rápido, independentemente

144
00:07:16,920 --> 00:07:19,110
do tamaño do
entrada de datos que pasar.

145
00:07:19,110 --> 00:07:23,760
Eles sempre teñen unha operación ou
unha unidade de recursos para tratar con eles.

146
00:07:23,760 --> 00:07:25,730
Pode ser 2, que podería
ser 3, pódese 4.

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

148
00:07:26,910 --> 00:07:28,400
El non varía.

149
00:07:28,400 --> 00:07:31,390
>> Algoritmos de tempo logarítmicas
son lixeiramente mellores.

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

151
00:07:33,950 --> 00:07:37,420
certamente visto ata agora é o
dilacerando do libro de teléfono

152
00:07:37,420 --> 00:07:39,480
para atopar Mike Smith no libro de teléfono.

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

154
00:07:40,980 --> 00:07:43,580
E así como n queda maior
e máis grande e larger--

155
00:07:43,580 --> 00:07:47,290
de feito, cada vez que dobrar
n, el só ten un paso.

156
00:07:47,290 --> 00:07:49,770
Entón, iso é moito mellor
que, digamos, o tempo lineal.

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

158
00:07:53,030 --> 00:07:55,980
Se triplicar n, hai que
triplicar o número de pasos.

159
00:07:55,980 --> 00:07:58,580
Un paso por unidade.

160
00:07:58,580 --> 00:08:01,790
>> A continuación, as cousas están un pouco more--
pouco menos grande de alí.

161
00:08:01,790 --> 00:08:06,622
Ten tempo rítmica lineal, ás veces,
chamado rexistro de tempo lineal ou só n log n.

162
00:08:06,622 --> 00:08:08,330
E nós imos un exemplo
dun algoritmo que

163
00:08:08,330 --> 00:08:13,370
é executado en n log n, que é aínda mellor
que cuadrática tempo-- n ao cadrado.

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

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

166
00:08:20,810 --> 00:08:24,670
Así, un número constante e elevada a
a potencia do tamaño da entrada.

167
00:08:24,670 --> 00:08:28,990
Polo tanto, se hai 1,000-- o
entrada de datos é de tamaño 1.000,

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

169
00:08:31,310 --> 00:08:33,559
É moito peor que tempo polinomial.

170
00:08:33,559 --> 00:08:35,030
>> Tempo factorial é aínda peor.

171
00:08:35,030 --> 00:08:37,760
E, de feito, non hai realmente facer
hai algoritmos de tempo infinito,

172
00:08:37,760 --> 00:08:43,740
tales como, así chamada sort-- burro cuxa
traballo é para embaralhar aleatoriamente un array

173
00:08:43,740 --> 00:08:45,490
e, a continuación, comprobar a ver
se está clasificado.

174
00:08:45,490 --> 00:08:47,589
E se non é, de forma aleatoria
embaralhar a matriz de novo

175
00:08:47,589 --> 00:08:49,130
e comprobar a ver se está clasificado.

176
00:08:49,130 --> 00:08:51,671
E como probablemente pode imagine--
podes imaxinar unha situación

177
00:08:51,671 --> 00:08:55,200
onde, no peor caso, que as ganas
nunca realmente comezar coa matriz.

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

179
00:08:57,150 --> 00:08:59,349
E para que sería un
algoritmo de tempo infinito.

180
00:08:59,349 --> 00:09:01,890
Espero que non vai ser escrito
calquera momento factorial ou infinito

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

182
00:09:04,510 --> 00:09:09,150
>> Entón, imos ter un pouco máis
mirar nalgún concreto simple

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

184
00:09:11,154 --> 00:09:13,070
Polo tanto, temos un example--
ou dous 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
unha única operación no peor caso.

187
00:09:17,980 --> 00:09:20,050
Así, o primeiro example--
temos unha función

188
00:09:20,050 --> 00:09:23,952
4 chamado para ti, que
recibe un array de tamaño 1.000.

189
00:09:23,952 --> 00:09:25,660
Pero entón, ao parecer,
non realmente ollar

190
00:09:25,660 --> 00:09:29,000
a ele-- non lle importa realmente o que é
dentro del, dese array.

191
00:09:29,000 --> 00:09:30,820
Sempre retorna só catro.

192
00:09:30,820 --> 00:09:32,940
Entón, ese algoritmo,
a pesar do feito de que

193
00:09:32,940 --> 00:09:35,840
leva 1.000 elementos non
facer nada con eles.

194
00:09:35,840 --> 00:09:36,590
Volve só catro.

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

196
00:09:38,240 --> 00:09:41,600
>> De feito, engadir 2 nums-- que
que xa vimos antes como bom--

197
00:09:41,600 --> 00:09:43,680
só procesa dous enteiros.

198
00:09:43,680 --> 00:09:44,692
Non é unha única etapa.

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

200
00:09:45,900 --> 00:09:50,780
Gañou un, comeza b, vostede engadila los
xuntos, e saída dos resultados.

201
00:09:50,780 --> 00:09:53,270
Entón é 84 pasos.

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

203
00:09:55,510 --> 00:09:59,240
Ten que chegar a, b comezar, engade
Los en conxunto, o resultado de saída.

204
00:09:59,240 --> 00:10:02,900
Entón iso é un algoritmo de tempo constante.

205
00:10:02,900 --> 00:10:05,170
>> Aquí está un exemplo dun
algorithm-- tempo lineal

206
00:10:05,170 --> 00:10:08,740
que un algoritmo que leva gets--
un paso adicional, posiblemente,

207
00:10:08,740 --> 00:10:10,740
como a súa entrada crece 1.

208
00:10:10,740 --> 00:10:14,190
Entón, imos dicir que estamos a buscar
o número 5 para dentro dunha matriz.

209
00:10:14,190 --> 00:10:16,774
Pode que unha situación na que
pode atopalo moi cedo.

210
00:10:16,774 --> 00:10:18,606
Pero tamén pode ter
unha situación 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
Nunha matriz de tamaño 5, se
nós estamos mirando para o número 5.

213
00:10:23,780 --> 00:10:25,930
Levaría 5 pasos.

214
00:10:25,930 --> 00:10:29,180
E, de feito, imaxinar que hai
5 non en calquera lugar nesa matriz.

215
00:10:29,180 --> 00:10:32,820
Aínda realmente ten que ollar para
cada elemento da matriz

216
00:10:32,820 --> 00:10:35,550
a fin de determinar
5 ou non existe.

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

218
00:10:39,840 --> 00:10:41,700
ou non existe en absoluto.

219
00:10:41,700 --> 00:10:44,690
Aínda temos que mirar para
todo n elementos.

220
00:10:44,690 --> 00:10:47,120
E así este algoritmo
executa en tempo lineal.

221
00:10:47,120 --> 00:10:50,340
Pode confirmar que,
extrapolando algo, dicindo:

222
00:10:50,340 --> 00:10:53,080
se tivésemos unha matriz de 6 elementos e
estabamos a buscar o número 5,

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

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

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

226
00:10:59,160 --> 00:11:02,920
A medida que engadimos un elemento para a nosa
matriz, dá un paso máis.

227
00:11:02,920 --> 00:11:06,750
Isto é un algoritmo lineal
no peor caso.

228
00:11:06,750 --> 00:11:08,270
>> Parella preguntas rápidas para ti.

229
00:11:08,270 --> 00:11:11,170
Cal é a runtime-- o que é
o peor caso de tempo de execución

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

231
00:11:13,700 --> 00:11:17,420
Entón, eu teño un loop de 4 aquí que se executa
de j é igual a 0, todo o camiño ata m.

232
00:11:17,420 --> 00:11:21,980
E o que eu estou a ver aquí, é que o
corpo do lazo execútase en tempo constante.

233
00:11:21,980 --> 00:11:24,730
Entón, usando a terminoloxía que
xa falamos o que about--

234
00:11:24,730 --> 00:11:29,390
sería o peor caso
tempo de execución deste algoritmo?

235
00:11:29,390 --> 00:11:31,050
Tomé un segundo.

236
00:11:31,050 --> 00:11:34,270
A parte interna do lacete
execútase en tempo constante.

237
00:11:34,270 --> 00:11:37,510
E a parte exterior do
loop está indo para realizar m veces.

238
00:11:37,510 --> 00:11:40,260
Entón, cal é o peor caso de tempo de execución aquí?

239
00:11:40,260 --> 00:11:43,210
Será que adiviña big-O m?

240
00:11:43,210 --> 00:11:44,686
Estaría ben.

241
00:11:44,686 --> 00:11:46,230
>> Como case outro?

242
00:11:46,230 --> 00:11:48,590
Esta vez temos un
loop dentro dun loop.

243
00:11:48,590 --> 00:11:50,905
Temos un lazo externo
que vai de cero a p.

244
00:11:50,905 --> 00:11:54,630
E nós temos un loop interno que se executa
de cero a P, e dentro de que,

245
00:11:54,630 --> 00:11:57,890
Afirmo que o corpo do
loop execútase en tempo constante.

246
00:11:57,890 --> 00:12:02,330
Entón, cal é o peor caso de tempo de execución
deste fragmento de código específico?

247
00:12:02,330 --> 00:12:06,140
Ben, unha vez máis, temos un
loop externo que corre p veces.

248
00:12:06,140 --> 00:12:09,660
E cada iteración tempo--
de punto que, en vez.

249
00:12:09,660 --> 00:12:13,170
Temos un lazo interno
que tamén executa p veces.

250
00:12:13,170 --> 00:12:16,900
E, a continuación, dentro diso, hai o
constante pequeno fragmento tempo-- alí.

251
00:12:16,900 --> 00:12:19,890
>> Entón, se temos un circuíto externo que
p corre veces dentro dos cales é

252
00:12:19,890 --> 00:12:22,880
un loop interno que
p execútase o que é vezes--

253
00:12:22,880 --> 00:12:26,480
o peor caso de tempo de execución
de este fragmento de código?

254
00:12:26,480 --> 00:12:30,730
Será que adiviña big-O p cadrado?

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

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

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