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

2
00:00:05,830 --> 00:00:07,910
>> Muy bien, así, la complejidad computacional.

3
00:00:07,910 --> 00:00:10,430
Sólo un poco de una advertencia
Antes de profundizar en demasiados far--

4
00:00:10,430 --> 00:00:13,070
esto probablemente va a ser entre
las cosas más pesado de matemáticas

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

6
00:00:14,200 --> 00:00:16,950
Esperemos que no sea demasiado abrumador
y vamos a tratar de guiar

7
00:00:16,950 --> 00:00:19,200
a través del proceso, pero
sólo un poco de una advertencia justa.

8
00:00:19,200 --> 00:00:21,282
Hay un poco
de matemáticas involucradas aquí.

9
00:00:21,282 --> 00:00:23,990
De acuerdo, con el fin de hacer
uso de nuestros recursos computacionales

10
00:00:23,990 --> 00:00:28,170
en lo real mundo-- es realmente
importante entender algoritmos

11
00:00:28,170 --> 00:00:30,750
y cómo se procesan los datos.

12
00:00:30,750 --> 00:00:32,810
Si tenemos una realidad
algoritmo eficiente, nos

13
00:00:32,810 --> 00:00:36,292
puede reducir al mínimo la cantidad de recursos
que tenemos disponible para tratar con él.

14
00:00:36,292 --> 00:00:38,750
Si tenemos un algoritmo que
se va a tomar un montón de trabajo

15
00:00:38,750 --> 00:00:41,210
para procesar una realidad
gran conjunto de datos, es

16
00:00:41,210 --> 00:00:44,030
va a requerir más
y más recursos, que

17
00:00:44,030 --> 00:00:47,980
es el dinero, la memoria RAM, todo ese tipo de cosas.

18
00:00:47,980 --> 00:00:52,090
>> Por lo tanto, ser capaz de analizar una
algoritmo que utiliza este conjunto de herramientas,

19
00:00:52,090 --> 00:00:56,110
básicamente, se pregunta el pregunta--
¿cómo funciona esta escala algoritmo

20
00:00:56,110 --> 00:00:59,020
como tiramos más y más datos en él?

21
00:00:59,020 --> 00:01:02,220
En CS50, la cantidad de datos que estamos
trabajar con es bastante pequeña.

22
00:01:02,220 --> 00:01:05,140
En general, nuestros programas van
para ejecutarse en un segundo o less--

23
00:01:05,140 --> 00:01:07,830
probablemente mucho menos
sobre todo desde el principio.

24
00:01:07,830 --> 00:01:12,250
>> Pero piensa en una empresa que ofertas
con cientos de millones de clientes.

25
00:01:12,250 --> 00:01:14,970
Y necesitan para procesar
que los datos del cliente.

26
00:01:14,970 --> 00:01:18,260
A medida que el número de clientes a los que
tienen hace más grande y más grande,

27
00:01:18,260 --> 00:01:21,230
que va a requerir
más y más recursos.

28
00:01:21,230 --> 00:01:22,926
¿Cuántos más recursos?

29
00:01:22,926 --> 00:01:25,050
Bueno, eso depende de cómo
analizamos el algoritmo,

30
00:01:25,050 --> 00:01:28,097
utilizando las herramientas de esta caja de herramientas.

31
00:01:28,097 --> 00:01:31,180
Cuando hablamos de la complejidad de
un algorithm-- que a veces tendrás

32
00:01:31,180 --> 00:01:34,040
escuchar su pronunciación conoce como tiempo
complejidad o espacio complejidad

33
00:01:34,040 --> 00:01:36,190
pero sólo vamos
llamar complexity--

34
00:01:36,190 --> 00:01:38,770
estamos hablando en general,
el peor de los casos.

35
00:01:38,770 --> 00:01:42,640
Teniendo en cuenta el peor pila absoluta de
datos que podríamos estar lanzando en él,

36
00:01:42,640 --> 00:01:46,440
cómo se va a este algoritmo
procesar o tratar con esos datos?

37
00:01:46,440 --> 00:01:51,450
Por lo general, llamamos el peor de los casos
tiempo de ejecución de un algoritmo grande-O.

38
00:01:51,450 --> 00:01:56,770
Así que un algoritmo podría decirse que
ejecutar en O de n u O de n al cuadrado.

39
00:01:56,770 --> 00:01:59,110
Y más de lo
aquellos quiere decir en un segundo.

40
00:01:59,110 --> 00:02:01,620
>> A veces, sin embargo, nos importa
sobre el mejor de los casos.

41
00:02:01,620 --> 00:02:05,400
Si los datos son todo lo que queríamos
que sea y que era absolutamente perfecto

42
00:02:05,400 --> 00:02:09,630
y estábamos enviando esta perfecta
un conjunto de datos a través de nuestro algoritmo.

43
00:02:09,630 --> 00:02:11,470
¿Cómo sería manejar en esa situación?

44
00:02:11,470 --> 00:02:15,050
A veces nos referimos a que a medida
big-Omega, por lo que en contraste con la gran-O,

45
00:02:15,050 --> 00:02:16,530
tenemos grandes Omega.

46
00:02:16,530 --> 00:02:18,880
Big-Omega para el mejor de los casos.

47
00:02:18,880 --> 00:02:21,319
Big-O para el peor de los casos.

48
00:02:21,319 --> 00:02:23,860
Generalmente, cuando se habla de
la complejidad de un algoritmo,

49
00:02:23,860 --> 00:02:26,370
estamos hablando de la
en el peor escenario.

50
00:02:26,370 --> 00:02:28,100
Así que tenlo en mente.

51
00:02:28,100 --> 00:02:31,510
>> Y en esta clase, estamos generalmente va
para dejar el análisis riguroso de lado.

52
00:02:31,510 --> 00:02:35,350
Hay ciencias y campos
dedicado a este tipo de cosas.

53
00:02:35,350 --> 00:02:37,610
Cuando hablamos de razonamiento
a través de algoritmos,

54
00:02:37,610 --> 00:02:41,822
que haremos pieza por pieza para muchos
algoritmos que nos hablan de la clase.

55
00:02:41,822 --> 00:02:44,780
Realmente estamos hablando sólo de
razonamiento a través de él con el sentido común,

56
00:02:44,780 --> 00:02:47,070
no con fórmulas, o pruebas,
ni nada de eso.

57
00:02:47,070 --> 00:02:51,600
Así que no se preocupe, nosotros no vamos a ser
convirtiéndose en una clase de matemáticas grande.

58
00:02:51,600 --> 00:02:55,920
>> Así que le dije que nos preocupamos por la complejidad
porque hace la pregunta, ¿cómo

59
00:02:55,920 --> 00:03:00,160
no manejan nuestros algoritmos más grande y
grandes conjuntos de datos que son lanzados contra ellos.

60
00:03:00,160 --> 00:03:01,960
Bueno, lo que es un conjunto de datos?

61
00:03:01,960 --> 00:03:03,910
¿Qué quise decir cuando dije eso?

62
00:03:03,910 --> 00:03:07,600
Significa lo aprovecha al máximo
sentido en el contexto, para ser honesto.

63
00:03:07,600 --> 00:03:11,160
Si tenemos un algoritmo, el
Procesos Strings-- estamos probablemente

64
00:03:11,160 --> 00:03:13,440
hablando sobre el tamaño de la cadena.

65
00:03:13,440 --> 00:03:15,190
Eso es los datos definido--
el tamaño, el número

66
00:03:15,190 --> 00:03:17,050
de caracteres que componen la cadena.

67
00:03:17,050 --> 00:03:20,090
Si estamos hablando de un
algoritmo que procesa los archivos,

68
00:03:20,090 --> 00:03:23,930
podríamos estar hablando de cómo
muchos kilobytes comprenden ese archivo.

69
00:03:23,930 --> 00:03:25,710
Y ese es el conjunto de datos.

70
00:03:25,710 --> 00:03:28,870
Si estamos hablando de un algoritmo
que maneja arrays de manera más general,

71
00:03:28,870 --> 00:03:31,510
tales como algoritmos de ordenación
o la búsqueda de algoritmos,

72
00:03:31,510 --> 00:03:36,690
probablemente estamos hablando de la serie
de los elementos que conforman una matriz.

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

74
00:03:39,272 --> 00:03:40,980
cuando digo que podemos
mido un algoritmo, que

75
00:03:40,980 --> 00:03:43,840
significa que podemos medir la
muchos recursos que ocupa.

76
00:03:43,840 --> 00:03:48,990
Ya sea que esos recursos son, cuántos
bytes de RAM-- o megabytes de RAM

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

78
00:03:49,790 --> 00:03:52,320
¿O cuánto tiempo se tarda en ejecutar.

79
00:03:52,320 --> 00:03:56,200
Y podemos llamar a esto
medir, de manera arbitraria, f de n.

80
00:03:56,200 --> 00:03:59,420
Donde n es el número de
elementos en el conjunto de datos.

81
00:03:59,420 --> 00:04:02,640
Y f de n es el número de tantos.

82
00:04:02,640 --> 00:04:07,530
¿Cuántas unidades de recursos hace
se requiere para procesar esos datos.

83
00:04:07,530 --> 00:04:10,030
>> Ahora, en realidad no nos importa
acerca de lo que f de n es exactamente.

84
00:04:10,030 --> 00:04:13,700
De hecho, muy raramente Voluntad--
sin duda nunca se en este class-- I

85
00:04:13,700 --> 00:04:18,709
bucear en cualquier realmente profundo
análisis de lo que f de n es.

86
00:04:18,709 --> 00:04:23,510
Sólo vamos a hablar de lo f de
n es de aproximadamente o lo que tiende a.

87
00:04:23,510 --> 00:04:27,600
Y la tendencia de un algoritmo es
dictado por su término más alto orden.

88
00:04:27,600 --> 00:04:29,440
Y podemos ver lo que
decir con que al tomar

89
00:04:29,440 --> 00:04:31,910
Una mirada a un ejemplo más concreto.

90
00:04:31,910 --> 00:04:34,620
>> Así que vamos a decir que tenemos
tres algoritmos diferentes.

91
00:04:34,620 --> 00:04:39,350
El primero de los cuales tiene n
cubos, algunas unidades de recursos

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

93
00:04:42,880 --> 00:04:47,000
Tenemos un segundo algoritmo que toma
n cubos más recursos n al cuadrado

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

95
00:04:49,350 --> 00:04:52,030
Y tenemos una tercera
algoritmo que se ejecuta en-- que

96
00:04:52,030 --> 00:04:58,300
ocupa n 8n menos al cubo cuadrado
más 20 n unidades de recursos

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

98
00:05:02,370 --> 00:05:05,594
>> Ahora, de nuevo, que realmente no vamos
para entrar en este nivel de detalle.

99
00:05:05,594 --> 00:05:08,260
Estoy realmente sólo tengo estas arriba
aquí como una ilustración de un punto

100
00:05:08,260 --> 00:05:10,176
que yo voy a ser
decisiones en un segundo, lo que

101
00:05:10,176 --> 00:05:12,980
es que sólo nos importa
acerca de la tendencia de las cosas

102
00:05:12,980 --> 00:05:14,870
como los conjuntos de datos se hacen más grandes.

103
00:05:14,870 --> 00:05:18,220
Así que si el conjunto de datos es pequeño, hay
en realidad una diferencia bastante grande

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

105
00:05:19,870 --> 00:05:23,000
El tercer algoritmo allí
toma 13 veces más,

106
00:05:23,000 --> 00:05:27,980
13 veces la cantidad de recursos
para funcionar en relación con la primera.

107
00:05:27,980 --> 00:05:31,659
>> Si nuestro conjunto de datos es de tamaño 10, que
es más grande, pero no necesariamente enorme,

108
00:05:31,659 --> 00:05:33,950
podemos ver que hay
en realidad un poco de diferencia.

109
00:05:33,950 --> 00:05:36,620
El tercer algoritmo
se vuelve más eficiente.

110
00:05:36,620 --> 00:05:40,120
Se trata en realidad del 40% -
o 60% más eficiente.

111
00:05:40,120 --> 00:05:41,580
Se tarda 40% la cantidad de tiempo.

112
00:05:41,580 --> 00:05:45,250
Puede run-- puede tomar
400 unidades de recursos

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

114
00:05:47,570 --> 00:05:49,410
Mientras que la primera
algoritmo, por el contrario,

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

116
00:05:54,520 --> 00:05:57,240
Pero mira lo que pasa como
nuestros números se ponen aún más grande.

117
00:05:57,240 --> 00:05:59,500
>> Ahora, la diferencia
entre estos algoritmos

118
00:05:59,500 --> 00:06:01,420
empezar a ser un poco menos aparente.

119
00:06:01,420 --> 00:06:04,560
Y el hecho de que hay
de orden inferior terms-- o más bien,

120
00:06:04,560 --> 00:06:09,390
términos con menor exponents--
empezar a ser irrelevante.

121
00:06:09,390 --> 00:06:12,290
Si un conjunto de datos es de tamaño
1000 y el primer algoritmo

122
00:06:12,290 --> 00:06:14,170
corre en unos mil millones de pasos.

123
00:06:14,170 --> 00:06:17,880
Y el segundo algoritmo se ejecuta en
mil millones y un millón de pasos.

124
00:06:17,880 --> 00:06:20,870
Y la tercera algoritmo se ejecuta
en poco menos de mil millones de pasos.

125
00:06:20,870 --> 00:06:22,620
Es más o menos mil millones de pasos.

126
00:06:22,620 --> 00:06:25,640
Esos términos de orden inferior comienzan
para llegar a ser realmente irrelevante.

127
00:06:25,640 --> 00:06:27,390
Y sólo para realmente
martillo casa el point--

128
00:06:27,390 --> 00:06:31,240
si la entrada de datos es de tamaño a
millones-- estos tres o menos

129
00:06:31,240 --> 00:06:34,960
tomar uno quintillion-- si
mis matemáticas es pasos correct--

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

131
00:06:37,260 --> 00:06:38,250
Eso es un montón de pasos.

132
00:06:38,250 --> 00:06:42,092
Y el hecho de que uno de ellos podría
tomar un par de 100.000, o una pareja 100

133
00:06:42,092 --> 00:06:44,650
millones menos aún cuando
estamos hablando de un número

134
00:06:44,650 --> 00:06:46,990
que big-- es algo irrelevante.

135
00:06:46,990 --> 00:06:50,006
Todos ellos tienden a tomar
aproximadamente n en cubos,

136
00:06:50,006 --> 00:06:52,380
y así podríamos realmente referirse
a todos estos algoritmos

137
00:06:52,380 --> 00:06:59,520
como estando en el orden de n
en cubos o grande-O de n cubos.

138
00:06:59,520 --> 00:07:03,220
>> Aquí está una lista de algunos de los más
clases comunes complejidad computacional

139
00:07:03,220 --> 00:07:05,820
que vamos encontramos en
algoritmos, por lo general.

140
00:07:05,820 --> 00:07:07,970
Y también específicamente en CS50.

141
00:07:07,970 --> 00:07:11,410
Estos están ordenados de
generalmente más rápida en la parte superior,

142
00:07:11,410 --> 00:07:13,940
a generalmente más lento en la parte inferior.

143
00:07:13,940 --> 00:07:16,920
Así algoritmos de tiempo constante tienden
ser el más rápido, sin tener en cuenta

144
00:07:16,920 --> 00:07:19,110
del tamaño de la
entrada de datos se pasa en.

145
00:07:19,110 --> 00:07:23,760
Ellos siempre tienen una sola operación o
una unidad de recursos para hacer frente a.

146
00:07:23,760 --> 00:07:25,730
Podría ser 2, podría
ser de 3, podría ser 4.

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

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

149
00:07:28,400 --> 00:07:31,390
>> Algoritmos tiempo logarítmicas
son ligeramente mejor.

150
00:07:31,390 --> 00:07:33,950
Y un buen ejemplo de
un algoritmo de tiempo logarítmica

151
00:07:33,950 --> 00:07:37,420
seguramente has visto por ahora es el
desgarrando de la guía telefónica

152
00:07:37,420 --> 00:07:39,480
encontrar Mike Smith en la guía telefónica.

153
00:07:39,480 --> 00:07:40,980
Cortamos el problema a la mitad.

154
00:07:40,980 --> 00:07:43,580
Y así, a medida que n se hace más grande
y más grande y larger--

155
00:07:43,580 --> 00:07:47,290
de hecho, cada vez que el doble
n, sólo se necesita un paso más.

156
00:07:47,290 --> 00:07:49,770
Así que eso es mucho mejor
que, por ejemplo, el tiempo lineal.

157
00:07:49,770 --> 00:07:53,030
¿Qué es si se duplica n, que
toma el doble del número de pasos.

158
00:07:53,030 --> 00:07:55,980
Si Triple N, se necesita
triplicar el número de pasos.

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

160
00:07:58,580 --> 00:08:01,790
>> Luego las cosas se ponen un poco más--
poco menos grande de allí.

161
00:08:01,790 --> 00:08:06,622
Tienes tiempo rítmico lineal, a veces
llamado registro de tiempo lineal o simplemente n log n.

162
00:08:06,622 --> 00:08:08,330
Y vamos a un ejemplo
de un algoritmo que

163
00:08:08,330 --> 00:08:13,370
carreras en n log n, lo que es aún mejor
que cuadrática tiempo-- n al cuadrado.

164
00:08:13,370 --> 00:08:17,320
O el tiempo polinomio, n de dos
cualquier número mayor que dos.

165
00:08:17,320 --> 00:08:20,810
O tiempo exponencial, lo que
es aún worse-- C para el n.

166
00:08:20,810 --> 00:08:24,670
Así que algunos número constante elevó hasta
el poder del tamaño de la entrada.

167
00:08:24,670 --> 00:08:28,990
Así que si hay 1,000-- si el
la entrada de datos es de tamaño 1000,

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

169
00:08:31,310 --> 00:08:33,559
Es mucho peor que tiempo polinomial.

170
00:08:33,559 --> 00:08:35,030
>> Tiempo factorial es aún peor.

171
00:08:35,030 --> 00:08:37,760
Y de hecho, en realidad lo hacen
Existen algoritmos de tiempo infinito,

172
00:08:37,760 --> 00:08:43,740
tales como, los llamados sort-- estúpida cuya
trabajo consiste en mezclar aleatoriamente un conjunto

173
00:08:43,740 --> 00:08:45,490
y luego compruebe
ya sea ordenadas.

174
00:08:45,490 --> 00:08:47,589
Y si no es así, al azar
mezclar la matriz de nuevo

175
00:08:47,589 --> 00:08:49,130
y comprobar para ver si se trata de resolver el problema.

176
00:08:49,130 --> 00:08:51,671
Y como usted probablemente puede imagine--
se puede imaginar una situación

177
00:08:51,671 --> 00:08:55,200
donde en el peor de los casos, que la voluntad
En realidad nunca comenzar con la matriz.

178
00:08:55,200 --> 00:08:57,150
Ese algoritmo iría para siempre.

179
00:08:57,150 --> 00:08:59,349
Y por lo que sería un
algoritmo de tiempo infinito.

180
00:08:59,349 --> 00:09:01,890
Esperemos que no va a escribir
cualquier momento factorial o infinito

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

182
00:09:04,510 --> 00:09:09,150
>> Por lo tanto, vamos a echar un poco más
aspecto concreto en algún simple

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

184
00:09:11,154 --> 00:09:13,070
Así que tenemos un ejemplo--
o dos ejemplos aquí--

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

186
00:09:15,590 --> 00:09:17,980
una sola operación en el peor de los casos.

187
00:09:17,980 --> 00:09:20,050
Así que la primera ejemplo--
tenemos una función

188
00:09:20,050 --> 00:09:23,952
llamada 4 para usted, que
toma una matriz de tamaño 1000.

189
00:09:23,952 --> 00:09:25,660
Pero entonces, aparentemente
en realidad no mirar

190
00:09:25,660 --> 00:09:29,000
en it-- no le importa realmente lo que es
dentro de ella, de esa matriz.

191
00:09:29,000 --> 00:09:30,820
Siempre simplemente devuelve cuatro.

192
00:09:30,820 --> 00:09:32,940
Por lo tanto, ese algoritmo,
a pesar del hecho de que

193
00:09:32,940 --> 00:09:35,840
tiene 1.000 elementos no
hacer nada con ellos.

194
00:09:35,840 --> 00:09:36,590
Sólo devuelve cuatro.

195
00:09:36,590 --> 00:09:38,240
Es siempre un solo paso.

196
00:09:38,240 --> 00:09:41,600
>> De hecho, añadir 2 nums-- que
que hemos visto antes como bien--

197
00:09:41,600 --> 00:09:43,680
simplemente procesa dos enteros.

198
00:09:43,680 --> 00:09:44,692
No es un solo paso.

199
00:09:44,692 --> 00:09:45,900
En realidad es un par de pasos.

200
00:09:45,900 --> 00:09:50,780
Usted recibe una, se obtiene b, se agregan
juntos, y ustedes, los resultados de salida.

201
00:09:50,780 --> 00:09:53,270
Así que es 84 pasos.

202
00:09:53,270 --> 00:09:55,510
Pero siempre es constante,
independientemente de a o b.

203
00:09:55,510 --> 00:09:59,240
Tienes que conseguir una, obtener b, agregue
juntos, el resultado de salida.

204
00:09:59,240 --> 00:10:02,900
Así que eso es un algoritmo de tiempo constante.

205
00:10:02,900 --> 00:10:05,170
>> He aquí un ejemplo de un
algorithm-- tiempo lineal

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

207
00:10:08,740 --> 00:10:10,740
como su entrada crece un 1.

208
00:10:10,740 --> 00:10:14,190
Así que, digamos que estamos buscando
el número 5 en el interior de una matriz.

209
00:10:14,190 --> 00:10:16,774
Es posible que tenga una situación en la
usted lo puede encontrar bastante temprano.

210
00:10:16,774 --> 00:10:18,606
Pero también podría tener
una situación donde

211
00:10:18,606 --> 00:10:20,450
podría ser el último elemento de la matriz.

212
00:10:20,450 --> 00:10:23,780
En una matriz de tamaño 5, si
estamos buscando el número 5.

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

214
00:10:25,930 --> 00:10:29,180
Y de hecho, imagino que hay
No 5 en cualquier parte de esta matriz.

215
00:10:29,180 --> 00:10:32,820
Todavía en realidad tenemos que mirar
cada elemento de la matriz

216
00:10:32,820 --> 00:10:35,550
Para determinar
si 5 es allí.

217
00:10:35,550 --> 00:10:39,840
>> Así que en el peor de los casos, y es que
el elemento es la última en la matriz

218
00:10:39,840 --> 00:10:41,700
o no existe en absoluto.

219
00:10:41,700 --> 00:10:44,690
Todavía tenemos que mirar
todos los n elementos.

220
00:10:44,690 --> 00:10:47,120
Y así, este algoritmo
se ejecuta en tiempo lineal.

221
00:10:47,120 --> 00:10:50,340
Puede confirmar que por
extrapolar un poco al decir:

222
00:10:50,340 --> 00:10:53,080
si tuviéramos una matriz de 6 elementos y
que estábamos buscando para el número 5,

223
00:10:53,080 --> 00:10:54,890
puede ser que tome 6 pasos.

224
00:10:54,890 --> 00:10:57,620
Si tenemos un conjunto de 7 elementos y
estamos buscando el número 5.

225
00:10:57,620 --> 00:10:59,160
Puede ser que tome 7 pasos.

226
00:10:59,160 --> 00:11:02,920
A medida que agregamos un elemento más a nuestro
matriz, que se necesita un paso más.

227
00:11:02,920 --> 00:11:06,750
Eso es un algoritmo lineal
En el peor de los casos.

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

229
00:11:08,270 --> 00:11:11,170
¿Cuál es la runtime-- lo que es
el peor de los casos-runtime

230
00:11:11,170 --> 00:11:13,700
de este fragmento de código en particular?

231
00:11:13,700 --> 00:11:17,420
Así que tengo un bucle de 4 aquí que corre
desde j es igual a 0, todo el camino hasta m.

232
00:11:17,420 --> 00:11:21,980
Y lo que estoy viendo aquí, es que el
cuerpo del bucle se ejecuta en tiempo constante.

233
00:11:21,980 --> 00:11:24,730
Así, utilizando la terminología que
ya hemos hablado sobre-- lo

234
00:11:24,730 --> 00:11:29,390
sería el peor de los casos
tiempo de ejecución de este algoritmo?

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

236
00:11:31,050 --> 00:11:34,270
La parte interna del bucle
corre en tiempo constante.

237
00:11:34,270 --> 00:11:37,510
Y la parte exterior de la
bucle se va a ejecutar m veces.

238
00:11:37,510 --> 00:11:40,260
¿Cuál es el peor de los casos el tiempo de ejecución en esta lista?

239
00:11:40,260 --> 00:11:43,210
¿Sabía usted adivina grande-O de m?

240
00:11:43,210 --> 00:11:44,686
Usted tendría razón.

241
00:11:44,686 --> 00:11:46,230
>> ¿Qué hay de otra?

242
00:11:46,230 --> 00:11:48,590
Esta vez tenemos una
bucle dentro de un bucle.

243
00:11:48,590 --> 00:11:50,905
Tenemos un bucle exterior
que va desde cero a p.

244
00:11:50,905 --> 00:11:54,630
Y tenemos un bucle interno que se ejecuta
de cero a p, y en el interior de eso,

245
00:11:54,630 --> 00:11:57,890
Declaro que el cuerpo de la
bucle se ejecuta en tiempo constante.

246
00:11:57,890 --> 00:12:02,330
¿Cuál es el peor de los casos el tiempo de ejecución
de este fragmento de código en particular?

247
00:12:02,330 --> 00:12:06,140
Bueno, de nuevo, tenemos una
lazo externo que se ejecuta p veces.

248
00:12:06,140 --> 00:12:09,660
Y cada iteración tiempo--
de ese bucle, más bien.

249
00:12:09,660 --> 00:12:13,170
Tenemos un bucle interno
que también corre p veces.

250
00:12:13,170 --> 00:12:16,900
Y luego dentro de eso, está el
constante pequeño fragmento tiempo-- allí.

251
00:12:16,900 --> 00:12:19,890
>> Así que si tenemos un bucle exterior que
corre p veces dentro de los cuales es

252
00:12:19,890 --> 00:12:22,880
un bucle interior que
corre p veces-- lo que es

253
00:12:22,880 --> 00:12:26,480
el peor de los casos-runtime
de este fragmento de código?

254
00:12:26,480 --> 00:12:30,730
¿Sabía usted adivina grande-O de p al cuadrado?

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

256
00:12:31,690 --> 00:12:33,880
Esto es CS50.

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