1
00:00:07,720 --> 00:00:10,950
[Powered by Google Translate] Vostè probablement ha sentit parlar d'un algoritme ràpid o eficient

2
00:00:10,950 --> 00:00:13,090
per a l'execució de la seva tasca en particular,

3
00:00:13,090 --> 00:00:16,110
però què significa això per a un algorisme per ser ràpid o eficient?

4
00:00:16,110 --> 00:00:18,580
Bé, no està parlant d'un mesurament en temps real,

5
00:00:18,580 --> 00:00:20,500
com segons o minuts.

6
00:00:20,500 --> 00:00:22,220
Això es deu a maquinari informàtic

7
00:00:22,220 --> 00:00:24,260
i pot variar dràsticament.

8
00:00:24,260 --> 00:00:26,020
El meu programa pot córrer més lent que el teu,

9
00:00:26,020 --> 00:00:28,000
perquè ho estic corrent en un ordinador antic,

10
00:00:28,000 --> 00:00:30,110
o perquè se m'acut estar jugant un joc de vídeo en línia

11
00:00:30,110 --> 00:00:32,670
al mateix temps, que està acaparant tot el meu memòria,

12
00:00:32,670 --> 00:00:35,400
o podria estar corrent el meu programa a través de diferents programes

13
00:00:35,400 --> 00:00:37,550
que es comunica amb la màquina de manera diferent en un nivell baix.

14
00:00:37,550 --> 00:00:39,650
És com comparar pomes i taronges.

15
00:00:39,650 --> 00:00:41,940
El fet que el meu equip més lent triga més

16
00:00:41,940 --> 00:00:43,410
que el teu per tornar una resposta

17
00:00:43,410 --> 00:00:45,510
no vol dir que vostè té l'algorisme més eficient.

18
00:00:45,510 --> 00:00:48,830
>> Per tant, ja que no es pot comparar directament els temps d'execució dels programes

19
00:00:48,830 --> 00:00:50,140
en qüestió de segons o minuts,

20
00:00:50,140 --> 00:00:52,310
Com podem comparar dos algorismes diferents

21
00:00:52,310 --> 00:00:55,030
independentment del seu maquinari o l'entorn del programari?

22
00:00:55,030 --> 00:00:58,000
Per crear una forma més uniforme de mesurament de l'eficiència algorísmica,

23
00:00:58,000 --> 00:01:00,360
els informàtics i matemàtics han ideat

24
00:01:00,360 --> 00:01:03,830
conceptes per a la mesura de la complexitat asimptòtica d'un programa

25
00:01:03,830 --> 00:01:06,110
i una notació anomenada "Ohnotation Big '

26
00:01:06,110 --> 00:01:08,320
per descriure això.

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

28
00:01:10,820 --> 00:01:13,390
s'executa en l'ordre de g (x)

29
00:01:13,390 --> 00:01:15,140
si existeix algun valor (x), x ₀ i

30
00:01:15,140 --> 00:01:17,630
alguna constant C, per a això

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

32
00:01:19,340 --> 00:01:21,230
aquesta constant g vegades (x)

33
00:01:21,230 --> 00:01:23,190
per a tot x major que x ₀.

34
00:01:23,190 --> 00:01:25,290
>> Però no s'espanten per la definició formal.

35
00:01:25,290 --> 00:01:28,020
Què significa això en realitat significa en termes menys teòrics?

36
00:01:28,020 --> 00:01:30,580
Bé, és bàsicament una forma d'analitzar

37
00:01:30,580 --> 00:01:33,580
la rapidesa d'execució d'un programa creix asimptòticament.

38
00:01:33,580 --> 00:01:37,170
És a dir, com la mida de les entrades augmenta cap a l'infinit,

39
00:01:37,170 --> 00:01:41,390
Escolta, estàs ordenar una matriu de mida 1000 en comparació amb una matriu de mida 10.

40
00:01:41,390 --> 00:01:44,950
Com afecta el temps d'execució del seu programa de créixer?

41
00:01:44,950 --> 00:01:47,390
Per exemple, imaginar comptant el nombre de caràcters

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

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

44
00:01:51,620 --> 00:01:54,790
lletra per lletra i afegint 1 a un comptador per a cada caràcter.

45
00:01:55,700 --> 00:01:58,420
Aquest algorisme es diu que s'executen en temps lineal

46
00:01:58,420 --> 00:02:00,460
pel que fa al nombre de caràcters,

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

48
00:02:02,670 --> 00:02:04,910
En resum, s'executa en O (n).

49
00:02:05,570 --> 00:02:07,290
Per què és això?

50
00:02:07,290 --> 00:02:09,539
Així, amb aquest mètode, el temps requerit

51
00:02:09,539 --> 00:02:11,300
per travessar la cadena completa

52
00:02:11,300 --> 00:02:13,920
és proporcional al nombre de caràcters.

53
00:02:13,920 --> 00:02:16,480
Comptar el nombre de caràcters d'una cadena de 20 caràcters

54
00:02:16,480 --> 00:02:18,580
es va a prendre el doble de temps que sigui necessari

55
00:02:18,580 --> 00:02:20,330
per comptar els caràcters d'una cadena de 10 caràcters,

56
00:02:20,330 --> 00:02:23,000
perquè cal mirar tots els personatges

57
00:02:23,000 --> 00:02:25,740
i cada personatge té la mateixa quantitat de temps per mirar.

58
00:02:25,740 --> 00:02:28,050
A mesura que augmenta el nombre de caràcters,

59
00:02:28,050 --> 00:02:30,950
el temps d'execució s'incrementarà linealment amb la longitud d'entrada.

60
00:02:30,950 --> 00:02:33,500
>> Ara, imagini si vostè decideix que el temps lineal,

61
00:02:33,500 --> 00:02:36,390
O (n), simplement no era prou ràpid per a tu?

62
00:02:36,390 --> 00:02:38,750
Potser vostè està emmagatzemant enormes cadenes,

63
00:02:38,750 --> 00:02:40,450
i vostè no pot pagar el temps extra que tindria

64
00:02:40,450 --> 00:02:44,000
per recórrer la totalitat dels seus caràcters de comptatge un per un.

65
00:02:44,000 --> 00:02:46,650
Per tant, vostè decideix intentar alguna cosa diferent.

66
00:02:46,650 --> 00:02:49,270
Què passaria si a emmagatzemar i el nombre de caràcters

67
00:02:49,270 --> 00:02:52,690
a la cadena, per exemple, en una variable anomenada 'llengua'

68
00:02:52,690 --> 00:02:54,210
des del principi en el programa,

69
00:02:54,210 --> 00:02:57,800
fins i tot abans d'emmagatzemar el primer caràcter en la cadena?

70
00:02:57,800 --> 00:02:59,980
Llavors, l'únic que hauria de fer ara per esbrinar la longitud de la cadena,

71
00:02:59,980 --> 00:03:02,570
és comprovar quin és el valor de la variable és.

72
00:03:02,570 --> 00:03:05,530
No ha de mirar la mateixa cadena en absolut,

73
00:03:05,530 --> 00:03:08,160
i accedir al valor d'una variable com llengua es considera

74
00:03:08,160 --> 00:03:11,100
un temps asimptòticament constant operació,

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

76
00:03:13,070 --> 00:03:17,110
Per què és això? Bé, recordes el que significa complexitat asimptòtica.

77
00:03:17,110 --> 00:03:19,100
Com canvia el temps d'execució com la mida

78
00:03:19,100 --> 00:03:21,400
de les seves entrades creix?

79
00:03:21,400 --> 00:03:24,630
>> Diguem que es tracta d'aconseguir el nombre de caràcters d'una cadena més gran.

80
00:03:24,630 --> 00:03:26,960
Bé, no importa el gran que fer la cadena,

81
00:03:26,960 --> 00:03:28,690
fins a un milió de caràcters de longitud,

82
00:03:28,690 --> 00:03:31,150
Tot el que has de fer per trobar la longitud de la corda amb aquest enfocament,

83
00:03:31,150 --> 00:03:33,790
és llegir el valor de la llengua variable,

84
00:03:33,790 --> 00:03:35,440
que ja ha fet.

85
00:03:35,440 --> 00:03:38,200
La longitud de l'entrada, és a dir, la longitud de la cadena que s'està tractant de trobar,

86
00:03:38,200 --> 00:03:41,510
no afecta en absolut la velocitat del seu programa s'executa.

87
00:03:41,510 --> 00:03:44,550
Aquesta part del seu programa funcionaria igual de ràpid en una cadena d'un sol caràcter

88
00:03:44,550 --> 00:03:46,170
i una cadena de mil caràcters,

89
00:03:46,170 --> 00:03:49,140
i és per això que aquest programa s'anomena execució en temps constant

90
00:03:49,140 --> 00:03:51,520
pel que fa a la mida de l'entrada.

91
00:03:51,520 --> 00:03:53,920
>> Per descomptat, hi ha un inconvenient.

92
00:03:53,920 --> 00:03:55,710
Et passes l'espai de memòria addicional en el seu ordinador

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

94
00:03:57,380 --> 00:03:59,270
i el temps extra que el porta

95
00:03:59,270 --> 00:04:01,490
per fer l'emmagatzematge real de la variable,

96
00:04:01,490 --> 00:04:03,390
però el punt segueix en peu,

97
00:04:03,390 --> 00:04:05,060
esbrinar quant de temps la cadena

98
00:04:05,060 --> 00:04:07,600
no depèn de la longitud de la cadena en absolut.

99
00:04:07,600 --> 00:04:10,720
Així, s'executa en O (1) o constant de temps.

100
00:04:10,720 --> 00:04:13,070
Això certament no ha de significar

101
00:04:13,070 --> 00:04:15,610
que el codi s'executa en un pas,

102
00:04:15,610 --> 00:04:17,470
però no importa la quantitat de passos que és,

103
00:04:17,470 --> 00:04:20,019
Si no canvia amb la grandària de les entrades,

104
00:04:20,019 --> 00:04:23,420
tot i així és asimptòticament constant que representem com O (1).

105
00:04:23,420 --> 00:04:25,120
>> Com podran imaginar,

106
00:04:25,120 --> 00:04:27,940
hi ha molts diferents temps d'execució Big O per mesurar amb algorismes.

107
00:04:27,940 --> 00:04:32,980
O (n) ² algoritmes són asimptòticament més lent que O (n) algoritmes.

108
00:04:32,980 --> 00:04:35,910
És a dir, com el nombre d'elements (n) creix,

109
00:04:35,910 --> 00:04:39,280
amb el temps O (n) ² algoritmes prendrà més temps

110
00:04:39,280 --> 00:04:41,000
d'O (n) algoritmes per córrer.

111
00:04:41,000 --> 00:04:43,960
Això no vol dir que O (n) algoritmes sempre s'executen més ràpid

112
00:04:43,960 --> 00:04:46,410
d'O (n) ² algoritmes, fins i tot en el mateix entorn,

113
00:04:46,410 --> 00:04:48,080
en el mateix maquinari.

114
00:04:48,080 --> 00:04:50,180
Potser en mides d'entrada,

115
00:04:50,180 --> 00:04:52,900
 l'O (n) ² algorisme podria funcionar més ràpid,

116
00:04:52,900 --> 00:04:55,450
però, amb el temps, ja que la mida d'entrada augmenta

117
00:04:55,450 --> 00:04:58,760
cap a l'infinit, l'O (n) temps d'execució de l'algorisme ²

118
00:04:58,760 --> 00:05:02,000
finalment eclipsarà el temps d'execució de la O (n) algorisme.

119
00:05:02,000 --> 00:05:04,230
Igual que qualsevol funció matemàtica de segon grau

120
00:05:04,230 --> 00:05:06,510
 eventualment superarà qualsevol funció lineal,

121
00:05:06,510 --> 00:05:09,200
no importa la quantitat d'un capçal d'iniciar la funció lineal comença amb.

122
00:05:10,010 --> 00:05:12,000
Si està treballant amb grans quantitats de dades,

123
00:05:12,000 --> 00:05:15,510
algoritmes que s'executen en O (n) ² realment pot arribar a alentir el seu programa,

124
00:05:15,510 --> 00:05:17,770
però per mides petits d'entrada,

125
00:05:17,770 --> 00:05:19,420
probablement ni tan sols es donarà compte.

126
00:05:19,420 --> 00:05:21,280
>> Una altra complexitat asimptòtica és,

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

128
00:05:24,420 --> 00:05:26,340
Un exemple d'un algorisme que s'executa aquest ràpidament

129
00:05:26,340 --> 00:05:29,060
és l'algorisme de recerca binària clàssica,

130
00:05:29,060 --> 00:05:31,850
per buscar un element en una llista ja-ordenats d'elements.

131
00:05:31,850 --> 00:05:33,400
>> Si no sap el que fa la recerca binària,

132
00:05:33,400 --> 00:05:35,170
T'ho explicaré perquè realment ràpid.

133
00:05:35,170 --> 00:05:37,020
Diguem que vostè està buscant el número 3

134
00:05:37,020 --> 00:05:40,200
en aquesta matriu d'enters.

135
00:05:40,200 --> 00:05:42,140
Es veu en l'element mig de la matriu

136
00:05:42,140 --> 00:05:46,830
i pregunta: "Està l'element que vull major, igual o menor que això?"

137
00:05:46,830 --> 00:05:49,150
Si és igual, llavors genial. Vostè va trobar l'element, i ja està.

138
00:05:49,150 --> 00:05:51,300
Si és major, llavors vostè sap que l'element

139
00:05:51,300 --> 00:05:53,440
ha d'estar en la part dreta de la matriu,

140
00:05:53,440 --> 00:05:55,200
i només es pot observar que, en el futur,

141
00:05:55,200 --> 00:05:57,690
i si és menor, llavors vostè sap que ha d'estar a la banda esquerra.

142
00:05:57,690 --> 00:06:00,980
Aquest procés es repeteix llavors amb la matriu més petits

143
00:06:00,980 --> 00:06:02,870
fins que l'element es troba el correcte.

144
00:06:08,080 --> 00:06:11,670
>> Aquesta potent algorisme redueix la mida de la matriu a la meitat amb cada operació.

145
00:06:11,670 --> 00:06:14,080
Per tant, per trobar un element en una matriu ordenada de mida 8,

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

147
00:06:16,170 --> 00:06:18,450
o 3 d'aquestes operacions,

148
00:06:18,450 --> 00:06:22,260
comprovant l'element mitjà, llavors el tall de la matriu en un mitjà es requerirà,

149
00:06:22,260 --> 00:06:25,670
mentre que una matriu de mida 16 té (log ₂ 16),

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

151
00:06:27,480 --> 00:06:30,570
Això és només una operació més per una sèrie duplicat en grandària.

152
00:06:30,570 --> 00:06:32,220
Doblegant la mida de la matriu

153
00:06:32,220 --> 00:06:35,160
augmenta el temps d'execució només en un 1 tros d'aquest codi.

154
00:06:35,160 --> 00:06:37,770
Un cop més, comprovar l'element central de la llista, i després partir.

155
00:06:37,770 --> 00:06:40,440
Així, es diu que opera en temps logarítmic,

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

157
00:06:42,440 --> 00:06:44,270
Espereu-vos, vostè diu,

158
00:06:44,270 --> 00:06:47,510
¿Això no depenen del lloc en la llista l'element que està buscant és?

159
00:06:47,510 --> 00:06:50,090
I si el primer element es miri resulta ser la correcta?

160
00:06:50,090 --> 00:06:52,040
Llavors, només es necessita una operació,

161
00:06:52,040 --> 00:06:54,310
no importa què tan gran és la llista.

162
00:06:54,310 --> 00:06:56,310
>> Bé, és per això que els informàtics tenen termes més

163
00:06:56,310 --> 00:06:58,770
la complexitat asimptòtica que reflecteixen el millor dels casos

164
00:06:58,770 --> 00:07:01,050
i en el pitjor dels casos actuacions d'un algorisme.

165
00:07:01,050 --> 00:07:03,320
Més adequadament, els límits superior i inferior

166
00:07:03,320 --> 00:07:05,090
en el temps d'execució.

167
00:07:05,090 --> 00:07:07,660
En el millor dels casos per a la recerca binària, és el nostre element

168
00:07:07,660 --> 00:07:09,330
bell mig,

169
00:07:09,330 --> 00:07:11,770
i vostè ho aconsegueix en temps constant,

170
00:07:11,770 --> 00:07:14,240
no importa el gran que la resta de la matriu és.

171
00:07:15,360 --> 00:07:17,650
El símbol utilitzat per això és Ω.

172
00:07:17,650 --> 00:07:19,930
Per tant, aquest algorisme es diu d'executar en Ω (1).

173
00:07:19,930 --> 00:07:21,990
En el millor dels casos, es troba l'element ràpidament,

174
00:07:21,990 --> 00:07:24,200
no importa què tan gran és la matriu,

175
00:07:24,200 --> 00:07:26,050
però en el pitjor dels casos,

176
00:07:26,050 --> 00:07:28,690
que ha de realitzar (log n) els controls parcials

177
00:07:28,690 --> 00:07:31,030
de la matriu per trobar l'element correcte.

178
00:07:31,030 --> 00:07:34,270
Límits pitjor dels casos superiors s'anomenen amb la gran "O" que vostè ja sap.

179
00:07:34,270 --> 00:07:38,080
Per tant, és O (log n), però Ω (1).

180
00:07:38,080 --> 00:07:40,680
>> Una recerca lineal, per contra,

181
00:07:40,680 --> 00:07:43,220
en el qual a través de cada element de la matriu

182
00:07:43,220 --> 00:07:45,170
per trobar el que voleu,

183
00:07:45,170 --> 00:07:47,420
és en el millor Ω (1).

184
00:07:47,420 --> 00:07:49,430
Un cop més, el primer element que desitgi.

185
00:07:49,430 --> 00:07:51,930
Per tant, tant i fa tan gran és la matriu.

186
00:07:51,930 --> 00:07:54,840
En el pitjor cas, que és l'últim element de la matriu.

187
00:07:54,840 --> 00:07:58,560
Per tant, has de caminar a través de tots els n elements de la matriu per trobar-lo,

188
00:07:58,560 --> 00:08:02,170
com si estigués buscant un 3.

189
00:08:04,320 --> 00:08:06,030
Per tant, s'executa en O (n) temps

190
00:08:06,030 --> 00:08:09,330
perquè és proporcional al nombre d'elements de la matriu.

191
00:08:10,800 --> 00:08:12,830
>> Un símbol més utilitzat és Θ.

192
00:08:12,830 --> 00:08:15,820
Això pot ser usat per descriure els algorismes on els casos millor i pitjor

193
00:08:15,820 --> 00:08:17,440
són els mateixos.

194
00:08:17,440 --> 00:08:20,390
Aquest és el cas dels algorismes de longitud de cadena que parlem abans.

195
00:08:20,390 --> 00:08:22,780
És a dir, si la emmagatzemem en una variable abans

196
00:08:22,780 --> 00:08:25,160
emmagatzemem la cadena i accedir-hi més tard en temps constant.

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

198
00:08:27,920 --> 00:08:30,130
estem emmagatzemant en aquesta variable, haurem de mirar.

199
00:08:33,110 --> 00:08:35,110
El cas és que miri

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

201
00:08:37,120 --> 00:08:39,799
Així Ω (1) o en el millor dels casos la constant de temps.

202
00:08:39,799 --> 00:08:41,059
El pitjor cas és,

203
00:08:41,059 --> 00:08:43,400
ens fixem en ella i trobar la longitud de la cadena.

204
00:08:43,400 --> 00:08:47,300
Així, O (1) o constant de temps en el pitjor cas.

205
00:08:47,300 --> 00:08:49,180
Així, atès que la millor i el pitjor dels casos són els mateixos,

206
00:08:49,180 --> 00:08:52,520
això es pot dir per funcionar en Θ (1) hora.

207
00:08:54,550 --> 00:08:57,010
>> En resum, tenim una bona manera de raonar sobre els codis d'eficiència

208
00:08:57,010 --> 00:09:00,110
sense saber res sobre el temps real que triga a executar,

209
00:09:00,110 --> 00:09:02,270
que es veu afectada per molts factors externs,

210
00:09:02,270 --> 00:09:04,190
incloent maquinari diferents, programari,

211
00:09:04,190 --> 00:09:06,040
o els detalls del seu codi.

212
00:09:06,040 --> 00:09:08,380
A més, ens permet raonar bé sobre el que succeirà

213
00:09:08,380 --> 00:09:10,180
quan la mida dels increments de les entrades.

214
00:09:10,180 --> 00:09:12,490
>> Si s'executa en O (n) ² algorisme,

215
00:09:12,490 --> 00:09:15,240
o pitjor encara, un O (2 ⁿ) algorisme,

216
00:09:15,240 --> 00:09:17,170
un dels més ràpids tipus de cultiu,

217
00:09:17,170 --> 00:09:19,140
que realment començarà a notar la desacceleració

218
00:09:19,140 --> 00:09:21,220
quan comences a treballar amb grans quantitats de dades.

219
00:09:21,220 --> 00:09:23,590
>> Aquesta és la complexitat asimptòtica. Gràcies.