1
00:00:07,720 --> 00:00:10,950
[Powered by Google Translate] Ai auzit, probabil, oamenii vorbesc despre un algoritm rapid sau eficiente

2
00:00:10,950 --> 00:00:13,090
pentru executarea sarcina dumneavoastră special,

3
00:00:13,090 --> 00:00:16,110
dar ce anume înseamnă pentru un algoritm pentru a fi rapid sau de eficiente?

4
00:00:16,110 --> 00:00:18,580
Ei bine, nu e vorba de o măsurare în timp real,

5
00:00:18,580 --> 00:00:20,500
cum ar fi secunde sau minute.

6
00:00:20,500 --> 00:00:22,220
Acest lucru se datorează faptului că hardware-ul computerului

7
00:00:22,220 --> 00:00:24,260
și software-ul variază drastic.

8
00:00:24,260 --> 00:00:26,020
Programul meu ar putea rula mai lent decât a ta,

9
00:00:26,020 --> 00:00:28,000
pentru ca eu o rulează pe un calculator mai vechi,

10
00:00:28,000 --> 00:00:30,110
sau pentru că I se întâmplă să joace un joc video online

11
00:00:30,110 --> 00:00:32,670
în același timp, care este hogging toate memoria mea,

12
00:00:32,670 --> 00:00:35,400
sau am putea fi difuzate programul meu prin intermediul unui software diferit

13
00:00:35,400 --> 00:00:37,550
care comunică cu aparatul diferit la un nivel scăzut.

14
00:00:37,550 --> 00:00:39,650
E cum ai compara merele cu portocalele.

15
00:00:39,650 --> 00:00:41,940
Doar pentru ca calculatorul meu lent durează mai mult

16
00:00:41,940 --> 00:00:43,410
decât a ta de a da înapoi un răspuns

17
00:00:43,410 --> 00:00:45,510
nu înseamnă că trebuie algoritm mai eficient.

18
00:00:45,510 --> 00:00:48,830
>> Deci, din moment ce nu se poate compara direct runtime ale programelor

19
00:00:48,830 --> 00:00:50,140
în câteva secunde sau minute,

20
00:00:50,140 --> 00:00:52,310
cum putem compara 2 algoritmi diferite

21
00:00:52,310 --> 00:00:55,030
indiferent de hardware sau software-ul de mediu?

22
00:00:55,030 --> 00:00:58,000
Pentru a crea un mod mai uniform de măsurare a eficienței algoritmică,

23
00:00:58,000 --> 00:01:00,360
oamenii de stiinta de calculator si matematicieni au conceput

24
00:01:00,360 --> 00:01:03,830
concepte pentru măsurarea complexitatea asimptotică a unui program de

25
00:01:03,830 --> 00:01:06,110
și o notație numit "Big Ohnotation"

26
00:01:06,110 --> 00:01:08,320
pentru a descrie acest lucru.

27
00:01:08,320 --> 00:01:10,820
Definiția formală este faptul că o funcție f (x)

28
00:01:10,820 --> 00:01:13,390
ruleaza pe ordinea de g (x)

29
00:01:13,390 --> 00:01:15,140
în cazul în care există o anumită valoare (x), x ₀ și

30
00:01:15,140 --> 00:01:17,630
o constantă, C, pentru care

31
00:01:17,630 --> 00:01:19,340
f (x) este mai mică sau egală cu

32
00:01:19,340 --> 00:01:21,230
care constanta de ori g (x)

33
00:01:21,230 --> 00:01:23,190
pentru orice x mai mare decât x ₀.

34
00:01:23,190 --> 00:01:25,290
>> Dar să nu-ți fie frică de mers cu definiție oficială.

35
00:01:25,290 --> 00:01:28,020
Ce înseamnă, de fapt, în mai puțin termeni teoretici?

36
00:01:28,020 --> 00:01:30,580
Ei bine, e de fapt o modalitate de a analiza

37
00:01:30,580 --> 00:01:33,580
cat de rapid timp de execuție a unui program creste asimptotic.

38
00:01:33,580 --> 00:01:37,170
Asta este, ca mărime de intrare crește spre infinit dvs.,

39
00:01:37,170 --> 00:01:41,390
cuvânt de spus, te sortarea o serie de dimensiuni 1000, comparativ cu o serie de mărimea 10.

40
00:01:41,390 --> 00:01:44,950
Cum rulare a programului ta să crească?

41
00:01:44,950 --> 00:01:47,390
De exemplu, imaginați-vă numărare numărul de caractere

42
00:01:47,390 --> 00:01:49,350
într-un șir mai simplu mod

43
00:01:49,350 --> 00:01:51,620
 de mers pe jos prin întreg șir

44
00:01:51,620 --> 00:01:54,790
scrisoare-de-literă și adăugând 1 la un contor pentru fiecare personaj.

45
00:01:55,700 --> 00:01:58,420
Acest algoritm se spune pentru a rula în timp liniar

46
00:01:58,420 --> 00:02:00,460
în ceea ce privește numărul de caractere,

47
00:02:00,460 --> 00:02:02,670
"N" în șir.

48
00:02:02,670 --> 00:02:04,910
Pe scurt, se execută în O (n).

49
00:02:05,570 --> 00:02:07,290
De ce este acest lucru?

50
00:02:07,290 --> 00:02:09,539
Ei bine, folosind aceasta abordare, timpul necesar

51
00:02:09,539 --> 00:02:11,300
sa traverseze întregul șir

52
00:02:11,300 --> 00:02:13,920
este proporțională cu numărul de caractere.

53
00:02:13,920 --> 00:02:16,480
Numărarea numărul de caractere dintr-un șir de 20 de caractere

54
00:02:16,480 --> 00:02:18,580
este de gând să ia de două ori, atâta timp cât este nevoie

55
00:02:18,580 --> 00:02:20,330
pentru a număra caracterele dintr-un șir de 10 de caractere,

56
00:02:20,330 --> 00:02:23,000
pentru ca trebuie sa te uiti la toate caracterele

57
00:02:23,000 --> 00:02:25,740
și fiecare personaj are aceeași cantitate de timp să se uite la.

58
00:02:25,740 --> 00:02:28,050
Pe măsură ce crește numărul de caractere,

59
00:02:28,050 --> 00:02:30,950
Runtime va crește liniar cu lungimea de intrare.

60
00:02:30,950 --> 00:02:33,500
>> Acum, imaginați-vă dacă vă decideți că timpul linear,

61
00:02:33,500 --> 00:02:36,390
O (n), pur și simplu nu a fost suficient de rapid pentru tine?

62
00:02:36,390 --> 00:02:38,750
Poate te stocarea siruri de caractere uriașe,

63
00:02:38,750 --> 00:02:40,450
și nu vă puteți permite timp suplimentar s-ar lua

64
00:02:40,450 --> 00:02:44,000
pentru a traversa toate personajele lor de numărare unul câte unul.

65
00:02:44,000 --> 00:02:46,650
Deci, vă decideți să încercați ceva diferit.

66
00:02:46,650 --> 00:02:49,270
Ce se întâmplă dacă s-ar întâmpla să stocați deja numărul de caractere

67
00:02:49,270 --> 00:02:52,690
în șir, să zicem, într-o variabilă numită "len,"

68
00:02:52,690 --> 00:02:54,210
încă de la începutul programului,

69
00:02:54,210 --> 00:02:57,800
înainte de a vă memorate chiar caracter foarte primul în șir dvs.?

70
00:02:57,800 --> 00:02:59,980
Apoi, tot ce ar trebui să facem acum pentru a afla lungimea șirului,

71
00:02:59,980 --> 00:03:02,570
verifica ce este valoarea variabilei este.

72
00:03:02,570 --> 00:03:05,530
Tu nu ar trebui să se uite la șirul în sine, la toate,

73
00:03:05,530 --> 00:03:08,160
și accesarea valoarea unei variabile cum ar fi len este considerată

74
00:03:08,160 --> 00:03:11,100
o constantă de timp asimptotic funcționare,

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

76
00:03:13,070 --> 00:03:17,110
De ce este acest lucru? Ei bine, amintiți-vă ce înseamnă complexitate asimptotică.

77
00:03:17,110 --> 00:03:19,100
Cum se schimbă rulare ca dimensiunea

78
00:03:19,100 --> 00:03:21,400
intrări de dvs. crește?

79
00:03:21,400 --> 00:03:24,630
>> Spuneți că ați fost încercarea de a obține numărul de caractere dintr-un șir mai mare.

80
00:03:24,630 --> 00:03:26,960
Ei bine, nu ar conta cât de mare faci șir,

81
00:03:26,960 --> 00:03:28,690
chiar și un milion de caractere,

82
00:03:28,690 --> 00:03:31,150
tot ce ar trebui să facă pentru a găsi lungimea șirului cu această abordare,

83
00:03:31,150 --> 00:03:33,790
este de a citi valoarea variabilei LEN,

84
00:03:33,790 --> 00:03:35,440
care deja făcut.

85
00:03:35,440 --> 00:03:38,200
Durata de intrare, care este, de lungimea șirului sunteți încercarea de a găsi,

86
00:03:38,200 --> 00:03:41,510
nu afectează deloc cât de repede se execută programul.

87
00:03:41,510 --> 00:03:44,550
Această parte a programului dumneavoastră va rula la fel de rapid pe un șir de un caracter

88
00:03:44,550 --> 00:03:46,170
și un șir de o mie de caractere,

89
00:03:46,170 --> 00:03:49,140
si de aceea acest program ar fi mentionat ca rulează în timp constant

90
00:03:49,140 --> 00:03:51,520
cu privire la dimensiunea de intrare.

91
00:03:51,520 --> 00:03:53,920
>> Desigur, există un neajuns.

92
00:03:53,920 --> 00:03:55,710
Iti petreci spațiu de memorie suplimentar pe calculatorul dvs.

93
00:03:55,710 --> 00:03:57,380
stocarea variabila

94
00:03:57,380 --> 00:03:59,270
și timp suplimentar este nevoie de tine

95
00:03:59,270 --> 00:04:01,490
pentru a face de stocare reală a variabilei,

96
00:04:01,490 --> 00:04:03,390
dar punctul de încă stă,

97
00:04:03,390 --> 00:04:05,060
a afla cât de mult timp a fost șirul de

98
00:04:05,060 --> 00:04:07,600
nu depinde de lungimea șirului, la toate.

99
00:04:07,600 --> 00:04:10,720
Deci, se execută în O (1) sau constanta de timp.

100
00:04:10,720 --> 00:04:13,070
Acest lucru cu siguranță nu trebuie să însemne

101
00:04:13,070 --> 00:04:15,610
că codul se execută în 1 pas,

102
00:04:15,610 --> 00:04:17,470
dar nu contează cât de multe etape este,

103
00:04:17,470 --> 00:04:20,019
în cazul în care nu se schimba cu dimensiunea de intrări,

104
00:04:20,019 --> 00:04:23,420
e încă asimptotic constanta pe care le reprezintă ca O (1).

105
00:04:23,420 --> 00:04:25,120
>> După cum puteți ghici, probabil,

106
00:04:25,120 --> 00:04:27,940
există multe diferite runtime mari O să măsoare cu algoritmi.

107
00:04:27,940 --> 00:04:32,980
O (n) ² algoritmi sunt asimptotic mai lent decât O (n) algoritmi.

108
00:04:32,980 --> 00:04:35,910
Asta este, ca numărul de elemente (n) crește,

109
00:04:35,910 --> 00:04:39,280
în cele din urmă O (n) ² algoritmi va dura mai mult timp

110
00:04:39,280 --> 00:04:41,000
mult O (n) pentru a rula algoritmi.

111
00:04:41,000 --> 00:04:43,960
Acest lucru nu înseamnă O (n) algoritmi executați întotdeauna mai repede

112
00:04:43,960 --> 00:04:46,410
mult O (n) ² algoritmi, chiar și în același mediu,

113
00:04:46,410 --> 00:04:48,080
pe același hardware.

114
00:04:48,080 --> 00:04:50,180
Poate pentru dimensiuni mici de intrare,

115
00:04:50,180 --> 00:04:52,900
 O (n) ² algoritm ar putea lucra de fapt mai repede,

116
00:04:52,900 --> 00:04:55,450
dar, în cele din urmă, în calitate de mărimea de intrare crește

117
00:04:55,450 --> 00:04:58,760
spre infinit, O (n) ² algoritmul lui timp de execuție

118
00:04:58,760 --> 00:05:02,000
va eclipsa în cele din urmă de rulare O (n) algoritmul.

119
00:05:02,000 --> 00:05:04,230
La fel ca orice funcție matematică pătratică

120
00:05:04,230 --> 00:05:06,510
 va depăși în cele din urmă orice funcție liniară,

121
00:05:06,510 --> 00:05:09,200
indiferent de cât de mult de un cap de a începe funcția liniară începe off cu.

122
00:05:10,010 --> 00:05:12,000
Dacă lucrați cu cantități mari de date,

123
00:05:12,000 --> 00:05:15,510
algoritmi care rulează în O (n) ² poate ajunge într-adevăr până încetinirea programului,

124
00:05:15,510 --> 00:05:17,770
dar pentru dimensiuni mici de intrare,

125
00:05:17,770 --> 00:05:19,420
probabil nici nu va observa.

126
00:05:19,420 --> 00:05:21,280
>> Un alt complexitatea asimptotică este,

127
00:05:21,280 --> 00:05:24,420
timp logaritmică, O (log n).

128
00:05:24,420 --> 00:05:26,340
Un exemplu de un algoritm care rulează acest lucru rapid

129
00:05:26,340 --> 00:05:29,060
este clasic căutare algoritmul binar,

130
00:05:29,060 --> 00:05:31,850
pentru a găsi un element dintr-o listă deja-sortate de elemente.

131
00:05:31,850 --> 00:05:33,400
>> Dacă nu știi ce face cautare binara,

132
00:05:33,400 --> 00:05:35,170
Voi explica pentru tine foarte repede.

133
00:05:35,170 --> 00:05:37,020
Să presupunem că sunteți în căutarea pentru numărul 3

134
00:05:37,020 --> 00:05:40,200
în această matrice de întregi.

135
00:05:40,200 --> 00:05:42,140
Se uită la elementul din mijloc al matrice

136
00:05:42,140 --> 00:05:46,830
și întreabă, "Este elementul vreau mai mare, egală sau mai mică decât aceasta?"

137
00:05:46,830 --> 00:05:49,150
Dacă e egal, atunci mare. Ai găsit elementul, și ați terminat.

138
00:05:49,150 --> 00:05:51,300
Dacă e mai mare, atunci știi elementul

139
00:05:51,300 --> 00:05:53,440
trebuie să fie în partea dreaptă a matrice,

140
00:05:53,440 --> 00:05:55,200
si poti sa te uiti doar la faptul că, în viitor,

141
00:05:55,200 --> 00:05:57,690
și, dacă este mai mic, atunci știi că trebuie să fie în partea stângă.

142
00:05:57,690 --> 00:06:00,980
Acest proces este apoi repetat cu matrice mici dimensiuni

143
00:06:00,980 --> 00:06:02,870
până când elementul corect este găsit.

144
00:06:08,080 --> 00:06:11,670
>> Acest algoritm puternic taie dimensiunea matrice în jumătate, cu fiecare operațiune.

145
00:06:11,670 --> 00:06:14,080
Deci, pentru a găsi un element într-o gamă de sortat dimensiune 8,

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

147
00:06:16,170 --> 00:06:18,450
sau 3 din aceste operațiuni,

148
00:06:18,450 --> 00:06:22,260
verificarea elementul din mijloc, apoi de tăiere matrice în jumătate va fi necesar,

149
00:06:22,260 --> 00:06:25,670
întrucât o serie de dimensiune 16 ia (log ₂ 16),

150
00:06:25,670 --> 00:06:27,480
sau 4 operațiuni.

151
00:06:27,480 --> 00:06:30,570
Asta e doar 1 operațiunea mai mult de o matrice de dimensiune dublat.

152
00:06:30,570 --> 00:06:32,220
Dublarea dimensiunea matrice

153
00:06:32,220 --> 00:06:35,160
crește durata de funcționare cu doar 1 bucata din prezentul cod.

154
00:06:35,160 --> 00:06:37,770
Din nou, verificarea elementul din mijloc al listei, apoi de despicare.

155
00:06:37,770 --> 00:06:40,440
Deci, se spune să funcționeze în timp logaritmică,

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

157
00:06:42,440 --> 00:06:44,270
Dar stai, spui tu,

158
00:06:44,270 --> 00:06:47,510
nu asta depinde de locul în lista de element pe care îl căutați este?

159
00:06:47,510 --> 00:06:50,090
Ce se întâmplă dacă primul element te uiti la întâmplă să fie corect?

160
00:06:50,090 --> 00:06:52,040
Apoi, este nevoie de doar 1 funcționare,

161
00:06:52,040 --> 00:06:54,310
indiferent de cât de mare este lista.

162
00:06:54,310 --> 00:06:56,310
>> Ei bine, de aceea oamenii de știință de calculator au termeni mai

163
00:06:56,310 --> 00:06:58,770
pentru complexitatea asimptotică care reflectă mai bun caz

164
00:06:58,770 --> 00:07:01,050
și cel mai rău caz performanțelor unui algoritm.

165
00:07:01,050 --> 00:07:03,320
Mai corect, limitele superioare și inferioare

166
00:07:03,320 --> 00:07:05,090
pe timp de execuție.

167
00:07:05,090 --> 00:07:07,660
În cel mai bun caz pentru căutare binară, elementul nostru este

168
00:07:07,660 --> 00:07:09,330
chiar acolo, în mijloc,

169
00:07:09,330 --> 00:07:11,770
si te-ai prins în timp constant,

170
00:07:11,770 --> 00:07:14,240
indiferent de cât de mare restul de matrice este.

171
00:07:15,360 --> 00:07:17,650
Simbolul folosit pentru acest lucru este Ω.

172
00:07:17,650 --> 00:07:19,930
Deci, acest algoritm se spune pentru a rula în Ω (1).

173
00:07:19,930 --> 00:07:21,990
În cel mai bun caz, aceasta constată elementul rapid,

174
00:07:21,990 --> 00:07:24,200
indiferent de cât de mare este matrice,

175
00:07:24,200 --> 00:07:26,050
dar, în cel mai rău caz,

176
00:07:26,050 --> 00:07:28,690
acesta trebuie să efectueze (log n) controale pe părți

177
00:07:28,690 --> 00:07:31,030
de matrice pentru a găsi elementul dreapta.

178
00:07:31,030 --> 00:07:34,270
Limitele cazul cel mai defavorabil superioare sunt descrise cu mare "O" pe care le cunosc deja.

179
00:07:34,270 --> 00:07:38,080
Deci, e O (log n), dar Ω (1).

180
00:07:38,080 --> 00:07:40,680
>> O căutare liniară, prin contrast,

181
00:07:40,680 --> 00:07:43,220
in care te plimbi prin fiecare element al matricei

182
00:07:43,220 --> 00:07:45,170
pentru a găsi cea pe care o doriți,

183
00:07:45,170 --> 00:07:47,420
este cel mai bun Ω (1).

184
00:07:47,420 --> 00:07:49,430
Din nou, primul element pe care doriți.

185
00:07:49,430 --> 00:07:51,930
Deci, nu contează cât de mare este matrice.

186
00:07:51,930 --> 00:07:54,840
În cel mai rău caz, e ultimul element din matrice.

187
00:07:54,840 --> 00:07:58,560
Deci, va trebui să se plimbe prin toate elementele din matrice n să-l găsiți,

188
00:07:58,560 --> 00:08:02,170
ca în cazul în care ați fost în căutarea pentru un 3.

189
00:08:04,320 --> 00:08:06,030
Deci, se execută în O (n)

190
00:08:06,030 --> 00:08:09,330
deoarece este proporțională cu numărul de elemente din matrice.

191
00:08:10,800 --> 00:08:12,830
>> Un simbol mai folosit este Θ.

192
00:08:12,830 --> 00:08:15,820
Acest lucru poate fi folosit pentru a descrie algoritmi în care cazurile cele mai bune și mai rău

193
00:08:15,820 --> 00:08:17,440
sunt aceleași.

194
00:08:17,440 --> 00:08:20,390
Acesta este cazul în algoritmii șir de lungime care am vorbit mai devreme.

195
00:08:20,390 --> 00:08:22,780
Asta este, dacă am depozitați-l într-o variabilă înainte de

196
00:08:22,780 --> 00:08:25,160
am stoca și accesa string-l mai târziu, în timp constant.

197
00:08:25,160 --> 00:08:27,920
Indiferent ce număr

198
00:08:27,920 --> 00:08:30,130
suntem stocarea în această variabilă, va trebui să se uite la ea.

199
00:08:33,110 --> 00:08:35,110
Cel mai bun caz este, ne uităm la ea

200
00:08:35,110 --> 00:08:37,120
și pentru a găsi lungimea șirului.

201
00:08:37,120 --> 00:08:39,799
Deci, Ω (1) sau cel mai bun caz constanta de timp.

202
00:08:39,799 --> 00:08:41,059
Cel mai rău caz este,

203
00:08:41,059 --> 00:08:43,400
ne uităm la ea și pentru a găsi lungimea șirului.

204
00:08:43,400 --> 00:08:47,300
Deci, O (1) sau constanta de timp, în cel mai rău caz.

205
00:08:47,300 --> 00:08:49,180
Deci, din moment cel mai bun caz și cele mai grave cazuri sunt aceleași,

206
00:08:49,180 --> 00:08:52,520
acest lucru poate fi spus pentru a rula în Θ (1) timp.

207
00:08:54,550 --> 00:08:57,010
>> În rezumat, avem bune moduri de a rationa despre eficiența codurilor

208
00:08:57,010 --> 00:09:00,110
fără a ști nimic despre timp real-lume, care le iau pentru a rula,

209
00:09:00,110 --> 00:09:02,270
care este afectată de o mulțime de factori externi,

210
00:09:02,270 --> 00:09:04,190
inclusiv hardware diferite, software-ul,

211
00:09:04,190 --> 00:09:06,040
sau specificul codului.

212
00:09:06,040 --> 00:09:08,380
De asemenea, ne permite să motiv bine despre ceea ce se va întâmpla

213
00:09:08,380 --> 00:09:10,180
atunci când dimensiunea crește intrărilor.

214
00:09:10,180 --> 00:09:12,490
>> Dacă sunteți execută în O (n) ² algoritm,

215
00:09:12,490 --> 00:09:15,240
sau mai rau, un O (2 ⁿ) algoritm,

216
00:09:15,240 --> 00:09:17,170
unul dintre cele mai rapide tipuri de creștere,

217
00:09:17,170 --> 00:09:19,140
veți începe cu adevărat să observați încetinirea

218
00:09:19,140 --> 00:09:21,220
Atunci când începeți să lucrați cu cantități mari de date.

219
00:09:21,220 --> 00:09:23,590
>> Asta e complexitatea asimptotică. Multumesc.