1
00:00:07,720 --> 00:00:10,950
[Powered by Google Translate] Probabilmente avete sentito parlare di un algoritmo veloce o efficace

2
00:00:10,950 --> 00:00:13,090
per l'esecuzione di vostro compito particolare,

3
00:00:13,090 --> 00:00:16,110
ma che cosa significa per un algoritmo di essere veloce o efficiente?

4
00:00:16,110 --> 00:00:18,580
Beh, non si sta parlando di una misura in tempo reale,

5
00:00:18,580 --> 00:00:20,500
come secondi o minuti.

6
00:00:20,500 --> 00:00:22,220
Questo perché hardware

7
00:00:22,220 --> 00:00:24,260
e software variano drasticamente.

8
00:00:24,260 --> 00:00:26,020
Il mio programma potrebbe funzionare più lento del tuo,

9
00:00:26,020 --> 00:00:28,000
perché io sono in esecuzione su un vecchio computer,

10
00:00:28,000 --> 00:00:30,110
o perché mi capita di giocare un gioco online video

11
00:00:30,110 --> 00:00:32,670
allo stesso tempo, che è hogging tutta la memoria,

12
00:00:32,670 --> 00:00:35,400
o potrei essere in esecuzione il mio programma attraverso diversi software

13
00:00:35,400 --> 00:00:37,550
che comunica con la macchina in modo diverso a un livello basso.

14
00:00:37,550 --> 00:00:39,650
E 'come paragonare mele e arance.

15
00:00:39,650 --> 00:00:41,940
Solo perché il mio computer più lento impiega più tempo

16
00:00:41,940 --> 00:00:43,410
della tua di restituire una risposta

17
00:00:43,410 --> 00:00:45,510
non significa che si ha l'algoritmo più efficiente.

18
00:00:45,510 --> 00:00:48,830
>> Quindi, dal momento che non è possibile confrontare direttamente i tempi di esecuzione dei programmi

19
00:00:48,830 --> 00:00:50,140
in pochi secondi o minuti,

20
00:00:50,140 --> 00:00:52,310
come si fa a confrontare due diversi algoritmi

21
00:00:52,310 --> 00:00:55,030
indipendentemente dal loro ambiente hardware o software?

22
00:00:55,030 --> 00:00:58,000
Per creare un modo più uniforme di misurazione dell'efficienza algoritmica,

23
00:00:58,000 --> 00:01:00,360
gli informatici e matematici hanno inventato

24
00:01:00,360 --> 00:01:03,830
concetti per misurare la complessità asintotica di un programma

25
00:01:03,830 --> 00:01:06,110
e una notazione chiamata 'Ohnotation Big'

26
00:01:06,110 --> 00:01:08,320
per descrivere questo.

27
00:01:08,320 --> 00:01:10,820
La definizione formale è che una funzione f (x)

28
00:01:10,820 --> 00:01:13,390
corre dell'ordine di g (x)

29
00:01:13,390 --> 00:01:15,140
se esiste un po 'di (x) il valore, x ₀ e

30
00:01:15,140 --> 00:01:17,630
una costante, C, per cui

31
00:01:17,630 --> 00:01:19,340
f (x) è minore o uguale a

32
00:01:19,340 --> 00:01:21,230
che costante volte g (x)

33
00:01:21,230 --> 00:01:23,190
per ogni x maggiore di x ₀.

34
00:01:23,190 --> 00:01:25,290
>> Ma non abbiate paura di distanza dalla definizione formale.

35
00:01:25,290 --> 00:01:28,020
Che cosa significa questo in realtà significa in termini meno teorici?

36
00:01:28,020 --> 00:01:30,580
Be ', è fondamentalmente un modo di analizzare

37
00:01:30,580 --> 00:01:33,580
la velocità di esecuzione di un programma cresce asintoticamente.

38
00:01:33,580 --> 00:01:37,170
Cioè, come la dimensione dei fattori aumenta verso l'infinito,

39
00:01:37,170 --> 00:01:41,390
dire, si sta ordinamento di un array di dimensioni 1000 rispetto ad un array di dimensione 10.

40
00:01:41,390 --> 00:01:44,950
In che modo il tempo di esecuzione del programma di crescere?

41
00:01:44,950 --> 00:01:47,390
Per esempio, immaginate contando il numero di caratteri

42
00:01:47,390 --> 00:01:49,350
in una stringa il modo più semplice

43
00:01:49,350 --> 00:01:51,620
 a piedi attraverso l'intera stringa

44
00:01:51,620 --> 00:01:54,790
lettera per lettera e l'aggiunta di 1 a un contatore per ogni personaggio.

45
00:01:55,700 --> 00:01:58,420
Questo algoritmo è detto per l'esecuzione in tempo lineare

46
00:01:58,420 --> 00:02:00,460
rispetto al numero di caratteri,

47
00:02:00,460 --> 00:02:02,670
'N' nella stringa.

48
00:02:02,670 --> 00:02:04,910
In breve, viene eseguito in O (n).

49
00:02:05,570 --> 00:02:07,290
Perché questo?

50
00:02:07,290 --> 00:02:09,539
Ebbene, utilizzando questo approccio, il tempo richiesto

51
00:02:09,539 --> 00:02:11,300
per attraversare l'intera stringa

52
00:02:11,300 --> 00:02:13,920
è proporzionale al numero di caratteri.

53
00:02:13,920 --> 00:02:16,480
Contare il numero di caratteri di una stringa di 20 caratteri

54
00:02:16,480 --> 00:02:18,580
sta per il doppio del tempo necessario

55
00:02:18,580 --> 00:02:20,330
per contare i caratteri di una stringa di 10 caratteri,

56
00:02:20,330 --> 00:02:23,000
perché si deve guardare a tutti i personaggi

57
00:02:23,000 --> 00:02:25,740
e ogni personaggio ha la stessa quantità di tempo per guardare.

58
00:02:25,740 --> 00:02:28,050
Come si aumenta il numero di caratteri,

59
00:02:28,050 --> 00:02:30,950
il runtime aumenta linearmente con la lunghezza dell'input.

60
00:02:30,950 --> 00:02:33,500
>> Ora, immaginate se si decide che il tempo lineare,

61
00:02:33,500 --> 00:02:36,390
O (n), non era abbastanza veloce per te?

62
00:02:36,390 --> 00:02:38,750
Forse stai memorizzare stringhe enormi,

63
00:02:38,750 --> 00:02:40,450
e non può permettersi il tempo in più ci sarebbe voluto

64
00:02:40,450 --> 00:02:44,000
attraversare tutti i loro conteggio caratteri uno ad uno.

65
00:02:44,000 --> 00:02:46,650
Così, si decide di provare qualcosa di diverso.

66
00:02:46,650 --> 00:02:49,270
E se ne sarebbe già memorizzare il numero di caratteri

67
00:02:49,270 --> 00:02:52,690
nella stringa, ad esempio, in una variabile chiamata 'len,'

68
00:02:52,690 --> 00:02:54,210
nelle prime fasi del programma,

69
00:02:54,210 --> 00:02:57,800
prima ancora memorizzato il primo carattere nella stringa?

70
00:02:57,800 --> 00:02:59,980
Quindi, tutto ciò che avrebbe dovuto fare ora per trovare la lunghezza della stringa,

71
00:02:59,980 --> 00:03:02,570
è verificare quale sia il valore della variabile è.

72
00:03:02,570 --> 00:03:05,530
Lei non avrebbe dovuto guardare la stringa stessa a tutti,

73
00:03:05,530 --> 00:03:08,160
e accedere al valore di una variabile come len è considerata

74
00:03:08,160 --> 00:03:11,100
un'operazione di tempo asintoticamente costante,

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

76
00:03:13,070 --> 00:03:17,110
Perché questo? Bene, ricordate che cosa significa complessità asintotica.

77
00:03:17,110 --> 00:03:19,100
Come cambia il runtime come la dimensione

78
00:03:19,100 --> 00:03:21,400
degli input cresce?

79
00:03:21,400 --> 00:03:24,630
>> Diciamo che stavano cercando di ottenere il numero di caratteri di una stringa più grande.

80
00:03:24,630 --> 00:03:26,960
Beh, non importa quanto grande a fare la stringa,

81
00:03:26,960 --> 00:03:28,690
anche un milione di caratteri,

82
00:03:28,690 --> 00:03:31,150
tutto quello che avrei dovuto fare per trovare la lunghezza della corda con questo approccio,

83
00:03:31,150 --> 00:03:33,790
è leggere il valore della variabile len,

84
00:03:33,790 --> 00:03:35,440
che hai già fatto.

85
00:03:35,440 --> 00:03:38,200
La lunghezza di input, cioè la lunghezza della stringa che si sta cercando di trovare,

86
00:03:38,200 --> 00:03:41,510
non influisce affatto quanto velocemente il vostro programma viene eseguito.

87
00:03:41,510 --> 00:03:44,550
Questa parte del programma sarebbe altrettanto veloce su una stringa di un carattere

88
00:03:44,550 --> 00:03:46,170
e mille-stringa di caratteri,

89
00:03:46,170 --> 00:03:49,140
ed è per questo che questo programma dovrebbe essere indicato come l'esecuzione in tempo costante

90
00:03:49,140 --> 00:03:51,520
rispetto alla dimensione dell'input.

91
00:03:51,520 --> 00:03:53,920
>> Naturalmente, c'è un inconveniente.

92
00:03:53,920 --> 00:03:55,710
Si spende più spazio di memoria sul vostro computer

93
00:03:55,710 --> 00:03:57,380
memorizzare la variabile

94
00:03:57,380 --> 00:03:59,270
e il tempo in più che ti porta

95
00:03:59,270 --> 00:04:01,490
per fare il deposito effettivo della variabile,

96
00:04:01,490 --> 00:04:03,390
ma il punto si ferma,

97
00:04:03,390 --> 00:04:05,060
scoprire quanto tempo la stringa è stata

98
00:04:05,060 --> 00:04:07,600
non dipende dalla lunghezza della stringa a tutti.

99
00:04:07,600 --> 00:04:10,720
Quindi, viene eseguito in O (1) o costante di tempo.

100
00:04:10,720 --> 00:04:13,070
Questo certamente non significa necessariamente

101
00:04:13,070 --> 00:04:15,610
che il codice viene eseguito in 1 passo,

102
00:04:15,610 --> 00:04:17,470
ma non importa quanti passi è,

103
00:04:17,470 --> 00:04:20,019
se non cambia con le dimensioni degli ingressi,

104
00:04:20,019 --> 00:04:23,420
è ancora asintoticamente costante che noi rappresentiamo come O (1).

105
00:04:23,420 --> 00:04:25,120
>> Come si può intuire,

106
00:04:25,120 --> 00:04:27,940
ci sono molti diversi tempi di esecuzione O grandi per misurare con gli algoritmi.

107
00:04:27,940 --> 00:04:32,980
O (n) ² algoritmi sono asintoticamente più lento di O (n) algoritmi.

108
00:04:32,980 --> 00:04:35,910
Cioè, il numero di elementi (n) cresce,

109
00:04:35,910 --> 00:04:39,280
alla fine O (n) ² algoritmi ci vorrà più tempo

110
00:04:39,280 --> 00:04:41,000
di O (n) gli algoritmi per l'esecuzione.

111
00:04:41,000 --> 00:04:43,960
Questo non significa che O (n) algoritmi sempre più veloci

112
00:04:43,960 --> 00:04:46,410
di O (n) ² algoritmi, anche nello stesso ambiente,

113
00:04:46,410 --> 00:04:48,080
sullo stesso hardware.

114
00:04:48,080 --> 00:04:50,180
Forse per le dimensioni di ingresso di piccole dimensioni,

115
00:04:50,180 --> 00:04:52,900
 O (n) ² algoritmo potrebbe effettivamente lavorare più velocemente,

116
00:04:52,900 --> 00:04:55,450
ma, alla fine, come la dimensione ingresso aumenta

117
00:04:55,450 --> 00:04:58,760
verso l'infinito, la O (n) algoritmo ² di runtime

118
00:04:58,760 --> 00:05:02,000
finirà per eclissare il runtime del (n) algoritmo O.

119
00:05:02,000 --> 00:05:04,230
Proprio come qualsiasi funzione quadratica matematica

120
00:05:04,230 --> 00:05:06,510
 finirà per superare qualsiasi funzione lineare,

121
00:05:06,510 --> 00:05:09,200
non importa quanto di una testa di avviare la funzione lineare inizia con.

122
00:05:10,010 --> 00:05:12,000
Se si lavora con grandi quantità di dati,

123
00:05:12,000 --> 00:05:15,510
algoritmi che vengono eseguiti in O (n) ² può davvero finire per rallentare il programma,

124
00:05:15,510 --> 00:05:17,770
ma per piccole dimensioni di ingresso,

125
00:05:17,770 --> 00:05:19,420
probabilmente non si accorgono neppure.

126
00:05:19,420 --> 00:05:21,280
>> Un altro è la complessità asintotica,

127
00:05:21,280 --> 00:05:24,420
tempo logaritmico, O (log n).

128
00:05:24,420 --> 00:05:26,340
Un esempio di un algoritmo che esegue questo rapidamente

129
00:05:26,340 --> 00:05:29,060
è il classico algoritmo di ricerca binaria,

130
00:05:29,060 --> 00:05:31,850
per trovare un elemento in un elenco già ordinato di elementi.

131
00:05:31,850 --> 00:05:33,400
>> Se non sai cosa fa la ricerca binaria,

132
00:05:33,400 --> 00:05:35,170
Te lo spiego per voi molto velocemente.

133
00:05:35,170 --> 00:05:37,020
Diciamo che stai cercando il numero 3

134
00:05:37,020 --> 00:05:40,200
in questo array di interi.

135
00:05:40,200 --> 00:05:42,140
Si guarda l'elemento centrale della matrice

136
00:05:42,140 --> 00:05:46,830
e chiede, "è l'elemento che voglio maggiore, uguale o inferiore a questo?"

137
00:05:46,830 --> 00:05:49,150
Se è uguale, allora grande. Hai trovato l'elemento, e il gioco è fatto.

138
00:05:49,150 --> 00:05:51,300
Se è maggiore, poi si sa l'elemento

139
00:05:51,300 --> 00:05:53,440
deve essere nel lato destro della matrice,

140
00:05:53,440 --> 00:05:55,200
e si può solo osservare che, in futuro,

141
00:05:55,200 --> 00:05:57,690
e se è più piccolo, poi si sa che deve essere sul lato sinistro.

142
00:05:57,690 --> 00:06:00,980
Questo processo viene ripetuto con la minore dimensione della matrice

143
00:06:00,980 --> 00:06:02,870
finché l'elemento esatto.

144
00:06:08,080 --> 00:06:11,670
>> Questo potente algoritmo riduce la dimensione della matrice a metà con ogni operazione.

145
00:06:11,670 --> 00:06:14,080
Così, per trovare un elemento in un array ordinato di dimensione 8,

146
00:06:14,080 --> 00:06:16,170
al massimo (log ₂ 8),

147
00:06:16,170 --> 00:06:18,450
o tre di queste operazioni,

148
00:06:18,450 --> 00:06:22,260
controllando l'elemento centrale, poi tagliando la matrice in mezzo sarà richiesto,

149
00:06:22,260 --> 00:06:25,670
considerando che un array di dimensione 16 si (log ₂ 16),

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

151
00:06:27,480 --> 00:06:30,570
Questo è solo 1 operazione di più per un doppio-dimensione dell'array.

152
00:06:30,570 --> 00:06:32,220
Raddoppiando la dimensione della matrice

153
00:06:32,220 --> 00:06:35,160
aumenta il tempo di esecuzione di solo 1 pezzo di questo codice.

154
00:06:35,160 --> 00:06:37,770
Nuovo, controllando l'elemento centrale dell'elenco, quindi splitting.

155
00:06:37,770 --> 00:06:40,440
Così, si dice di operare in tempo logaritmico,

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

157
00:06:42,440 --> 00:06:44,270
Ma aspetta, tu dici,

158
00:06:44,270 --> 00:06:47,510
questo non dipende il punto in cui l'elemento che stai cercando è?

159
00:06:47,510 --> 00:06:50,090
Che cosa succede se il primo elemento si guarda sembra essere quella giusta?

160
00:06:50,090 --> 00:06:52,040
Poi, ci vuole solo 1 operazione,

161
00:06:52,040 --> 00:06:54,310
non importa quanto grande è la lista.

162
00:06:54,310 --> 00:06:56,310
>> Beh, è ​​per questo che gli informatici hanno termini più

163
00:06:56,310 --> 00:06:58,770
per la complessità asintotica che riflettono il caso migliore

164
00:06:58,770 --> 00:07:01,050
e nel caso peggiore performance di un algoritmo.

165
00:07:01,050 --> 00:07:03,320
Più propriamente, i limiti superiore e inferiore

166
00:07:03,320 --> 00:07:05,090
sul runtime.

167
00:07:05,090 --> 00:07:07,660
Nel migliore dei casi per la ricerca binaria, è il nostro elemento

168
00:07:07,660 --> 00:07:09,330
proprio lì in mezzo,

169
00:07:09,330 --> 00:07:11,770
e si ottiene in tempo costante,

170
00:07:11,770 --> 00:07:14,240
non importa quanto grande il resto della matrice è.

171
00:07:15,360 --> 00:07:17,650
Il simbolo utilizzato per questo è Ω.

172
00:07:17,650 --> 00:07:19,930
Quindi, questo algoritmo è detto per l'esecuzione in Ω (1).

173
00:07:19,930 --> 00:07:21,990
Nel migliore dei casi, si trova l'elemento in modo rapido,

174
00:07:21,990 --> 00:07:24,200
non importa quanto grande sia la matrice,

175
00:07:24,200 --> 00:07:26,050
ma nel caso peggiore,

176
00:07:26,050 --> 00:07:28,690
che deve eseguire (log n) controlli parziali

177
00:07:28,690 --> 00:07:31,030
della matrice per trovare l'elemento giusto.

178
00:07:31,030 --> 00:07:34,270
Limiti del caso peggiore superiori sono indicati con la grande "O" che già conoscete.

179
00:07:34,270 --> 00:07:38,080
Quindi, è O (log n), ma Ω (1).

180
00:07:38,080 --> 00:07:40,680
>> Una ricerca lineare, per contrasto,

181
00:07:40,680 --> 00:07:43,220
in cui si cammina attraverso ogni elemento della matrice

182
00:07:43,220 --> 00:07:45,170
per trovare quello che si desidera,

183
00:07:45,170 --> 00:07:47,420
è al meglio Ω (1).

184
00:07:47,420 --> 00:07:49,430
Anche in questo caso, il primo elemento che si desidera.

185
00:07:49,430 --> 00:07:51,930
Quindi, non importa quanto grande sia la matrice è.

186
00:07:51,930 --> 00:07:54,840
Nel peggiore dei casi, è l'ultimo elemento dell'array.

187
00:07:54,840 --> 00:07:58,560
Quindi, bisogna camminare attraverso tutti gli elementi della matrice n per trovarlo,

188
00:07:58,560 --> 00:08:02,170
come se si stesse cercando un 3.

189
00:08:04,320 --> 00:08:06,030
Quindi, viene eseguito in O (n)

190
00:08:06,030 --> 00:08:09,330
perché è proporzionale al numero di elementi nella matrice.

191
00:08:10,800 --> 00:08:12,830
>> Un simbolo più utilizzato è Θ.

192
00:08:12,830 --> 00:08:15,820
Questo può essere usato per descrivere algoritmi Qualora i casi migliori e peggiori

193
00:08:15,820 --> 00:08:17,440
sono uguali.

194
00:08:17,440 --> 00:08:20,390
Questo è il caso nella stringa di lunghezza algoritmi di cui abbiamo parlato in precedenza.

195
00:08:20,390 --> 00:08:22,780
Cioè, se lo memorizzare in una variabile prima

196
00:08:22,780 --> 00:08:25,160
abbiamo memorizzare la stringa e accedervi in ​​seguito in tempo costante.

197
00:08:25,160 --> 00:08:27,920
Non importa quale sia il numero

198
00:08:27,920 --> 00:08:30,130
stiamo memorizzare in quella variabile, dovremo guardare.

199
00:08:33,110 --> 00:08:35,110
Il caso migliore è, lo guardiamo

200
00:08:35,110 --> 00:08:37,120
e trovare la lunghezza della stringa.

201
00:08:37,120 --> 00:08:39,799
Quindi Ω (1) o nel caso migliore costante di tempo.

202
00:08:39,799 --> 00:08:41,059
Il caso peggiore è,

203
00:08:41,059 --> 00:08:43,400
lo guardiamo e trovare la lunghezza della stringa.

204
00:08:43,400 --> 00:08:47,300
Quindi, O (1) o costante di tempo nel caso peggiore.

205
00:08:47,300 --> 00:08:49,180
Quindi, poiché il caso migliore e peggiore dei casi sono gli stessi,

206
00:08:49,180 --> 00:08:52,520
questo può essere detto per funzionare in Θ (1) tempo.

207
00:08:54,550 --> 00:08:57,010
>> In sintesi, ci sono buoni modi per ragionare su efficienza codici

208
00:08:57,010 --> 00:09:00,110
senza sapere nulla del mondo reale tempo che impiegano per l'esecuzione,

209
00:09:00,110 --> 00:09:02,270
che è influenzata da molti fattori esterni,

210
00:09:02,270 --> 00:09:04,190
incluso l'hardware differenti, il software,

211
00:09:04,190 --> 00:09:06,040
o le specifiche del codice.

212
00:09:06,040 --> 00:09:08,380
Inoltre, ci permette di ragionare bene su cosa accadrà

213
00:09:08,380 --> 00:09:10,180
quando la dimensione degli aumenti ingressi.

214
00:09:10,180 --> 00:09:12,490
>> Se si esegue in O (n) ² algoritmo,

215
00:09:12,490 --> 00:09:15,240
o peggio, una O (2 ⁿ) algoritmo,

216
00:09:15,240 --> 00:09:17,170
uno dei più rapida crescita tipi,

217
00:09:17,170 --> 00:09:19,140
si davvero iniziare a notare il rallentamento

218
00:09:19,140 --> 00:09:21,220
quando si inizia a lavorare con grandi quantità di dati.

219
00:09:21,220 --> 00:09:23,590
>> E 'la complessità asintotica. Grazie.