1
00:00:07,720 --> 00:00:10,950
[Powered by Google Translate] Usted probablemente ha oído hablar de un algoritmo rápido o eficiente

2
00:00:10,950 --> 00:00:13,090
para la ejecución de su tarea en particular,

3
00:00:13,090 --> 00:00:16,110
pero ¿qué significa esto para un algoritmo para ser rápido o eficiente?

4
00:00:16,110 --> 00:00:18,580
Bueno, no está hablando de una medición en tiempo real,

5
00:00:18,580 --> 00:00:20,500
como segundos o minutos.

6
00:00:20,500 --> 00:00:22,220
Esto se debe a hardware informático

7
00:00:22,220 --> 00:00:24,260
y puede variar drásticamente.

8
00:00:24,260 --> 00:00:26,020
Mi programa puede correr más lento que el tuyo,

9
00:00:26,020 --> 00:00:28,000
porque lo estoy corriendo en un ordenador antiguo,

10
00:00:28,000 --> 00:00:30,110
o porque se me ocurre estar jugando un juego de video en línea

11
00:00:30,110 --> 00:00:32,670
al mismo tiempo, que está acaparando todo mi memoria,

12
00:00:32,670 --> 00:00:35,400
o podría estar corriendo mi programa a través de diferentes programas

13
00:00:35,400 --> 00:00:37,550
que se comunica con la máquina de manera diferente en un nivel bajo.

14
00:00:37,550 --> 00:00:39,650
Es como comparar manzanas y naranjas.

15
00:00:39,650 --> 00:00:41,940
El hecho de que mi equipo más lento tarda más

16
00:00:41,940 --> 00:00:43,410
que el tuyo para devolver una respuesta

17
00:00:43,410 --> 00:00:45,510
no significa que usted tiene el algoritmo más eficiente.

18
00:00:45,510 --> 00:00:48,830
>> Por lo tanto, ya que no se puede comparar directamente los tiempos de ejecución de los programas

19
00:00:48,830 --> 00:00:50,140
en cuestión de segundos o minutos,

20
00:00:50,140 --> 00:00:52,310
¿Cómo podemos comparar dos algoritmos diferentes

21
00:00:52,310 --> 00:00:55,030
independientemente de su hardware o el entorno del software?

22
00:00:55,030 --> 00:00:58,000
Para crear una forma más uniforme de medición de la eficiencia algorítmica,

23
00:00:58,000 --> 00:01:00,360
los informáticos y matemáticos han ideado

24
00:01:00,360 --> 00:01:03,830
conceptos para la medición de la complejidad asintótica de un programa

25
00:01:03,830 --> 00:01:06,110
y una notación llamada "Ohnotation Big '

26
00:01:06,110 --> 00:01:08,320
para describir esto.

27
00:01:08,320 --> 00:01:10,820
La definición formal es que una función f (x)

28
00:01:10,820 --> 00:01:13,390
se ejecuta en el orden de g (x)

29
00:01:13,390 --> 00:01:15,140
si existe algún valor (x), x ₀ y

30
00:01:15,140 --> 00:01:17,630
alguna constante C, para lo cual

31
00:01:17,630 --> 00:01:19,340
f (x) es menor que o igual a

32
00:01:19,340 --> 00:01:21,230
esa constante g veces (x)

33
00:01:21,230 --> 00:01:23,190
para todo x mayor que x ₀.

34
00:01:23,190 --> 00:01:25,290
>> Pero no se asustan por la definición formal.

35
00:01:25,290 --> 00:01:28,020
¿Qué significa esto en realidad significa en términos menos teóricos?

36
00:01:28,020 --> 00:01:30,580
Bueno, es básicamente una forma de analizar

37
00:01:30,580 --> 00:01:33,580
la rapidez de ejecución de un programa crece asintóticamente.

38
00:01:33,580 --> 00:01:37,170
Es decir, como el tamaño de los insumos aumenta hacia el infinito,

39
00:01:37,170 --> 00:01:41,390
Oye, estás ordenar una matriz de tamaño 1000 en comparación con una matriz de tamaño 10.

40
00:01:41,390 --> 00:01:44,950
¿Cómo afecta el tiempo de ejecución de su programa de crecer?

41
00:01:44,950 --> 00:01:47,390
Por ejemplo, imaginar contando el número de caracteres

42
00:01:47,390 --> 00:01:49,350
en una cadena de la forma más sencilla

43
00:01:49,350 --> 00:01:51,620
 caminando a través de toda la cadena

44
00:01:51,620 --> 00:01:54,790
letra por letra y añadiendo 1 a un contador para cada carácter.

45
00:01:55,700 --> 00:01:58,420
Este algoritmo se dice que se ejecutan en tiempo lineal

46
00:01:58,420 --> 00:02:00,460
con respecto al número de caracteres,

47
00:02:00,460 --> 00:02:02,670
'N' en la cadena.

48
00:02:02,670 --> 00:02:04,910
En resumen, se ejecuta en O (n).

49
00:02:05,570 --> 00:02:07,290
¿Por qué es esto?

50
00:02:07,290 --> 00:02:09,539
Así, con este método, el tiempo requerido

51
00:02:09,539 --> 00:02:11,300
para atravesar la cadena completa

52
00:02:11,300 --> 00:02:13,920
es proporcional al número de caracteres.

53
00:02:13,920 --> 00:02:16,480
Contar el número de caracteres de una cadena de 20 caracteres

54
00:02:16,480 --> 00:02:18,580
se va a tomar el doble de tiempo que sea necesario

55
00:02:18,580 --> 00:02:20,330
para contar los caracteres de una cadena de 10 caracteres,

56
00:02:20,330 --> 00:02:23,000
porque hay que mirar a todos los personajes

57
00:02:23,000 --> 00:02:25,740
y cada personaje tiene la misma cantidad de tiempo para mirar.

58
00:02:25,740 --> 00:02:28,050
A medida que aumenta el número de caracteres,

59
00:02:28,050 --> 00:02:30,950
el tiempo de ejecución se incrementará linealmente con la longitud de entrada.

60
00:02:30,950 --> 00:02:33,500
>> Ahora, imagínese si usted decide que el tiempo lineal,

61
00:02:33,500 --> 00:02:36,390
O (n), simplemente no era lo suficientemente rápido para ti?

62
00:02:36,390 --> 00:02:38,750
Tal vez usted está almacenando enormes cadenas,

63
00:02:38,750 --> 00:02:40,450
y usted no puede pagar el tiempo extra que tendría

64
00:02:40,450 --> 00:02:44,000
para recorrer la totalidad de sus caracteres de conteo uno por uno.

65
00:02:44,000 --> 00:02:46,650
Por lo tanto, usted decide intentar algo diferente.

66
00:02:46,650 --> 00:02:49,270
¿Qué pasaría si a almacenar ya el número de caracteres

67
00:02:49,270 --> 00:02:52,690
en la cadena, por ejemplo, en una variable llamada 'len'

68
00:02:52,690 --> 00:02:54,210
desde el principio en el programa,

69
00:02:54,210 --> 00:02:57,800
incluso antes de almacenar el primer carácter en la cadena?

70
00:02:57,800 --> 00:02:59,980
Entonces, lo único que tendría que hacer ahora para averiguar la longitud de la cadena,

71
00:02:59,980 --> 00:03:02,570
es comprobar cuál es el valor de la variable es.

72
00:03:02,570 --> 00:03:05,530
Usted no tiene que mirar la propia cadena en absoluto,

73
00:03:05,530 --> 00:03:08,160
y acceder al valor de una variable como len se considera

74
00:03:08,160 --> 00:03:11,100
un tiempo asintóticamente constante operación,

75
00:03:11,100 --> 00:03:13,070
o O (1).

76
00:03:13,070 --> 00:03:17,110
¿Por qué es esto? Bueno, ¿recuerdas lo que significa complejidad asintótica.

77
00:03:17,110 --> 00:03:19,100
¿Cómo cambia el tiempo de ejecución como el tamaño

78
00:03:19,100 --> 00:03:21,400
de sus entradas crece?

79
00:03:21,400 --> 00:03:24,630
>> Digamos que se trata de conseguir el número de caracteres de una cadena más grande.

80
00:03:24,630 --> 00:03:26,960
Bueno, no importa lo grande que hacer la cadena,

81
00:03:26,960 --> 00:03:28,690
hasta un millón de caracteres de longitud,

82
00:03:28,690 --> 00:03:31,150
Todo lo que tienes que hacer para encontrar la longitud de la cuerda con este enfoque,

83
00:03:31,150 --> 00:03:33,790
es leer el valor de la len variable,

84
00:03:33,790 --> 00:03:35,440
que ya ha hecho.

85
00:03:35,440 --> 00:03:38,200
La longitud de la entrada, es decir, la longitud de la cadena que se está tratando de encontrar,

86
00:03:38,200 --> 00:03:41,510
no afecta en absoluto la velocidad de su programa se ejecuta.

87
00:03:41,510 --> 00:03:44,550
Esta parte de su programa funcionaría igual de rápido en una cadena de un solo carácter

88
00:03:44,550 --> 00:03:46,170
y una cadena de mil caracteres,

89
00:03:46,170 --> 00:03:49,140
y es por eso que este programa se denomina ejecución en tiempo constante

90
00:03:49,140 --> 00:03:51,520
con respecto al tamaño de la entrada.

91
00:03:51,520 --> 00:03:53,920
>> Por supuesto, hay un inconveniente.

92
00:03:53,920 --> 00:03:55,710
Te pasas el espacio de memoria adicional en su ordenador

93
00:03:55,710 --> 00:03:57,380
almacenar la variable

94
00:03:57,380 --> 00:03:59,270
y el tiempo extra que le lleva

95
00:03:59,270 --> 00:04:01,490
para hacer el almacenamiento real de la variable,

96
00:04:01,490 --> 00:04:03,390
pero el punto sigue en pie,

97
00:04:03,390 --> 00:04:05,060
averiguar cuánto tiempo la cadena se

98
00:04:05,060 --> 00:04:07,600
no depende de la longitud de la cadena en absoluto.

99
00:04:07,600 --> 00:04:10,720
Así, se ejecuta en O (1) o constante de tiempo.

100
00:04:10,720 --> 00:04:13,070
Esto ciertamente no tiene por qué significar

101
00:04:13,070 --> 00:04:15,610
que el código se ejecuta en un paso,

102
00:04:15,610 --> 00:04:17,470
pero no importa la cantidad de pasos que es,

103
00:04:17,470 --> 00:04:20,019
Si no cambia con el tamaño de las entradas,

104
00:04:20,019 --> 00:04:23,420
aún así es asintóticamente constante que representamos como O (1).

105
00:04:23,420 --> 00:04:25,120
>> Como podrán imaginar,

106
00:04:25,120 --> 00:04:27,940
hay muchos diferentes tiempos de ejecución Big O para medir con algoritmos.

107
00:04:27,940 --> 00:04:32,980
O (n) ² algoritmos son asintóticamente más lento que O (n) algoritmos.

108
00:04:32,980 --> 00:04:35,910
Es decir, como el número de elementos (n) crece,

109
00:04:35,910 --> 00:04:39,280
con el tiempo O (n) ² algoritmos tomará más tiempo

110
00:04:39,280 --> 00:04:41,000
de O (n) algoritmos para correr.

111
00:04:41,000 --> 00:04:43,960
Esto no significa que O (n) algoritmos siempre se ejecutan más rápido

112
00:04:43,960 --> 00:04:46,410
de O (n) ² algoritmos, incluso en el mismo entorno,

113
00:04:46,410 --> 00:04:48,080
en el mismo hardware.

114
00:04:48,080 --> 00:04:50,180
Tal vez para pequeños tamaños de entrada,

115
00:04:50,180 --> 00:04:52,900
 el O (n) ² algoritmo podría funcionar más rápido,

116
00:04:52,900 --> 00:04:55,450
pero, con el tiempo, ya que el tamaño de entrada aumenta

117
00:04:55,450 --> 00:04:58,760
hacia el infinito, el O (n) tiempo de ejecución del algoritmo ²

118
00:04:58,760 --> 00:05:02,000
finalmente eclipsará el tiempo de ejecución de la O (n) algoritmo.

119
00:05:02,000 --> 00:05:04,230
Al igual que cualquier función matemática de segundo grado

120
00:05:04,230 --> 00:05:06,510
 eventualmente superará a cualquier función lineal,

121
00:05:06,510 --> 00:05:09,200
no importa la cantidad de un cabezal de iniciar la función lineal comienza con.

122
00:05:10,010 --> 00:05:12,000
Si está trabajando con grandes cantidades de datos,

123
00:05:12,000 --> 00:05:15,510
algoritmos que se ejecutan en O (n) ² realmente puede llegar a ralentizar su programa,

124
00:05:15,510 --> 00:05:17,770
pero para tamaños pequeños de entrada,

125
00:05:17,770 --> 00:05:19,420
probablemente ni siquiera se dará cuenta.

126
00:05:19,420 --> 00:05:21,280
>> Otra complejidad asintótica es,

127
00:05:21,280 --> 00:05:24,420
tiempo logarítmica, O (log n).

128
00:05:24,420 --> 00:05:26,340
Un ejemplo de un algoritmo que se ejecuta este rápidamente

129
00:05:26,340 --> 00:05:29,060
es el algoritmo de búsqueda binaria clásica,

130
00:05:29,060 --> 00:05:31,850
para buscar un elemento en una lista ya-ordenados de elementos.

131
00:05:31,850 --> 00:05:33,400
>> Si usted no sabe lo que hace la búsqueda binaria,

132
00:05:33,400 --> 00:05:35,170
Te lo explicaré para que usted realmente rápido.

133
00:05:35,170 --> 00:05:37,020
Digamos que usted está buscando el número 3

134
00:05:37,020 --> 00:05:40,200
en esta matriz de enteros.

135
00:05:40,200 --> 00:05:42,140
Se ve en el elemento central de la matriz

136
00:05:42,140 --> 00:05:46,830
y pregunta: "¿Está el elemento que quiero mayor, igual o menor que esto?"

137
00:05:46,830 --> 00:05:49,150
Si es igual, entonces genial. Usted encontró el elemento, y ya está.

138
00:05:49,150 --> 00:05:51,300
Si es mayor, entonces usted sabe que el elemento

139
00:05:51,300 --> 00:05:53,440
tiene que estar en el lado derecho de la matriz,

140
00:05:53,440 --> 00:05:55,200
y sólo se puede observar que, en el futuro,

141
00:05:55,200 --> 00:05:57,690
y si es menor, entonces usted sabe que tiene que estar en el lado izquierdo.

142
00:05:57,690 --> 00:06:00,980
Este proceso se repite entonces con la matriz de menor tamaño

143
00:06:00,980 --> 00:06:02,870
hasta que el elemento se encuentra el correcto.

144
00:06:08,080 --> 00:06:11,670
>> Esta potente algoritmo reduce el tamaño de la matriz a la mitad con cada operación.

145
00:06:11,670 --> 00:06:14,080
Por lo tanto, para encontrar un elemento en una matriz ordenada de tamaño 8,

146
00:06:14,080 --> 00:06:16,170
en la mayoría (log ₂ 8),

147
00:06:16,170 --> 00:06:18,450
o 3 de estas operaciones,

148
00:06:18,450 --> 00:06:22,260
comprobando el elemento medio, entonces el corte de la matriz en un medio se requerirá,

149
00:06:22,260 --> 00:06:25,670
mientras que una matriz de tamaño 16 tiene (log ₂ 16),

150
00:06:25,670 --> 00:06:27,480
o 4 operaciones.

151
00:06:27,480 --> 00:06:30,570
Eso es sólo una operación más por una serie duplicado en tamaño.

152
00:06:30,570 --> 00:06:32,220
Doblando el tamaño de la matriz

153
00:06:32,220 --> 00:06:35,160
aumenta el tiempo de ejecución sólo en un 1 trozo de este código.

154
00:06:35,160 --> 00:06:37,770
Una vez más, comprobar el elemento central de la lista, y luego partir.

155
00:06:37,770 --> 00:06:40,440
Así, se dice que opera en tiempo logarítmico,

156
00:06:40,440 --> 00:06:42,440
O (log n).

157
00:06:42,440 --> 00:06:44,270
Pero espere, usted dice,

158
00:06:44,270 --> 00:06:47,510
¿esto no dependen del lugar en la lista el elemento que está buscando es?

159
00:06:47,510 --> 00:06:50,090
¿Y si el primer elemento se mire resulta ser la correcta?

160
00:06:50,090 --> 00:06:52,040
Entonces, sólo se necesita una operación,

161
00:06:52,040 --> 00:06:54,310
no importa qué tan grande es la lista.

162
00:06:54,310 --> 00:06:56,310
>> Bueno, es por eso que los informáticos tienen términos más

163
00:06:56,310 --> 00:06:58,770
la complejidad asintótica que reflejan el mejor de los casos

164
00:06:58,770 --> 00:07:01,050
y en el peor de los casos actuaciones de un algoritmo.

165
00:07:01,050 --> 00:07:03,320
Más adecuadamente, los límites superior e inferior

166
00:07:03,320 --> 00:07:05,090
en el tiempo de ejecución.

167
00:07:05,090 --> 00:07:07,660
En el mejor de los casos para la búsqueda binaria, es nuestro elemento

168
00:07:07,660 --> 00:07:09,330
justo en el medio,

169
00:07:09,330 --> 00:07:11,770
y usted lo consigue en tiempo constante,

170
00:07:11,770 --> 00:07:14,240
no importa lo grande que el resto de la matriz es.

171
00:07:15,360 --> 00:07:17,650
El símbolo utilizado para esto es Ω.

172
00:07:17,650 --> 00:07:19,930
Por lo tanto, este algoritmo se dice que ejecutar en Ω (1).

173
00:07:19,930 --> 00:07:21,990
En el mejor de los casos, se encuentra el elemento rápidamente,

174
00:07:21,990 --> 00:07:24,200
no importa qué tan grande es la matriz,

175
00:07:24,200 --> 00:07:26,050
pero en el peor de los casos,

176
00:07:26,050 --> 00:07:28,690
que tiene que realizar (log n) los controles parciales

177
00:07:28,690 --> 00:07:31,030
de la matriz para encontrar el elemento correcto.

178
00:07:31,030 --> 00:07:34,270
Límites peor de los casos superiores se denominan con la gran "O" que usted ya sabe.

179
00:07:34,270 --> 00:07:38,080
Por lo tanto, es O (log n), pero Ω (1).

180
00:07:38,080 --> 00:07:40,680
>> Una búsqueda lineal, por el contrario,

181
00:07:40,680 --> 00:07:43,220
en el que a través de cada elemento de la matriz

182
00:07:43,220 --> 00:07:45,170
para encontrar el que usted desea,

183
00:07:45,170 --> 00:07:47,420
es en el mejor de Ω (1).

184
00:07:47,420 --> 00:07:49,430
Una vez más, el primer elemento que desee.

185
00:07:49,430 --> 00:07:51,930
Por lo tanto, no importa qué tan grande es la matriz.

186
00:07:51,930 --> 00:07:54,840
En el peor caso, que es el último elemento de la matriz.

187
00:07:54,840 --> 00:07:58,560
Por lo tanto, tienes que caminar a través de todos los n elementos de la matriz para encontrarlo,

188
00:07:58,560 --> 00:08:02,170
como si estuviera buscando un 3.

189
00:08:04,320 --> 00:08:06,030
Por lo tanto, se ejecuta en O (n) tiempo

190
00:08:06,030 --> 00:08:09,330
porque es proporcional al número de elementos de la matriz.

191
00:08:10,800 --> 00:08:12,830
>> Un símbolo más utilizado es Θ.

192
00:08:12,830 --> 00:08:15,820
Esto puede ser usado para describir los algoritmos donde los casos mejor y peor

193
00:08:15,820 --> 00:08:17,440
son los mismos.

194
00:08:17,440 --> 00:08:20,390
Este es el caso de los algoritmos de longitud de cadena que hablamos antes.

195
00:08:20,390 --> 00:08:22,780
Es decir, si la almacenamos en una variable antes

196
00:08:22,780 --> 00:08:25,160
almacenamos la cadena y acceder a ella más tarde en tiempo constante.

197
00:08:25,160 --> 00:08:27,920
No importa qué número

198
00:08:27,920 --> 00:08:30,130
estamos almacenando en esa variable, vamos a tener que mirarlo.

199
00:08:33,110 --> 00:08:35,110
El caso es que mire

200
00:08:35,110 --> 00:08:37,120
y encontrar la longitud de la cadena.

201
00:08:37,120 --> 00:08:39,799
Así Ω (1) o en el mejor de los casos la constante de tiempo.

202
00:08:39,799 --> 00:08:41,059
El peor caso es,

203
00:08:41,059 --> 00:08:43,400
nos fijamos en ella y encontrar la longitud de la cadena.

204
00:08:43,400 --> 00:08:47,300
Así, O (1) o constante de tiempo en el peor caso.

205
00:08:47,300 --> 00:08:49,180
Así, dado que la mejor y el peor de los casos son los mismos,

206
00:08:49,180 --> 00:08:52,520
esto se puede decir para funcionar en Θ (1) hora.

207
00:08:54,550 --> 00:08:57,010
>> En resumen, tenemos una buena manera de razonar acerca de los códigos de eficiencia

208
00:08:57,010 --> 00:09:00,110
sin saber nada sobre el tiempo real que tarda en ejecutarse,

209
00:09:00,110 --> 00:09:02,270
que se ve afectada por muchos factores externos,

210
00:09:02,270 --> 00:09:04,190
incluyendo hardware diferentes, software,

211
00:09:04,190 --> 00:09:06,040
o los detalles de su código.

212
00:09:06,040 --> 00:09:08,380
Además, nos permite razonar bien sobre lo que sucederá

213
00:09:08,380 --> 00:09:10,180
cuando el tamaño de los incrementos de los insumos.

214
00:09:10,180 --> 00:09:12,490
>> Si ejecuta en O (n) ² algoritmo,

215
00:09:12,490 --> 00:09:15,240
o peor aún, un O (2 ⁿ) algoritmo,

216
00:09:15,240 --> 00:09:17,170
uno de los más rápidos tipos de cultivo,

217
00:09:17,170 --> 00:09:19,140
que realmente va a empezar a notar la desaceleración

218
00:09:19,140 --> 00:09:21,220
cuando empiezas a trabajar con grandes cantidades de datos.

219
00:09:21,220 --> 00:09:23,590
>> Esa es la complejidad asintótica. Gracias.