1
00:00:07,720 --> 00:00:10,950
[Powered by Google Translate] Jy het waarskynlik gehoor mense praat oor 'n vinnige of doeltreffende algoritme

2
00:00:10,950 --> 00:00:13,090
vir die uitvoering van jou spesifieke taak,

3
00:00:13,090 --> 00:00:16,110
maar wat presies beteken dit vir 'n algoritme om vinnig of doeltreffende te wees?

4
00:00:16,110 --> 00:00:18,580
Wel, dit is nie praat oor 'n meting in real-time,

5
00:00:18,580 --> 00:00:20,500
soos sekondes of minute.

6
00:00:20,500 --> 00:00:22,220
Dit is omdat die rekenaar hardeware

7
00:00:22,220 --> 00:00:24,260
en sagteware wissel drasties.

8
00:00:24,260 --> 00:00:26,020
My program kan loop stadiger as joune,

9
00:00:26,020 --> 00:00:28,000
want ek loop dit op 'n ouer rekenaar,

10
00:00:28,000 --> 00:00:30,110
of omdat ek toevallig op 'n aanlyn video spel speel

11
00:00:30,110 --> 00:00:32,670
op dieselfde tyd, wat al my geheue verslindende,

12
00:00:32,670 --> 00:00:35,400
of ek my program kan hardloop deur middel van verskillende sagteware

13
00:00:35,400 --> 00:00:37,550
wat kommunikeer met die masjien anders op 'n lae vlak.

14
00:00:37,550 --> 00:00:39,650
Dit is soos appels en lemoene te vergelyk.

15
00:00:39,650 --> 00:00:41,940
Net omdat my stadiger rekenaar langer neem

16
00:00:41,940 --> 00:00:43,410
as joune terug te gee 'n antwoord

17
00:00:43,410 --> 00:00:45,510
beteken nie jy het die meer doeltreffende algoritme.

18
00:00:45,510 --> 00:00:48,830
>> So, want ons kan nie direk vergelyk die Runtimes van programme

19
00:00:48,830 --> 00:00:50,140
in sekondes of minute,

20
00:00:50,140 --> 00:00:52,310
Hoe vergelyk ons ​​2 verskillende algoritmes

21
00:00:52,310 --> 00:00:55,030
ongeag van hul hardeware of sagteware-omgewing?

22
00:00:55,030 --> 00:00:58,000
'N meer eenvormige manier van die meet van algoritmiese doeltreffendheid te skep,

23
00:00:58,000 --> 00:01:00,360
rekenaar wetenskaplikes en wiskundiges uitgedink het

24
00:01:00,360 --> 00:01:03,830
konsepte vir die meet van die asimptotiese kompleksiteit van 'n program

25
00:01:03,830 --> 00:01:06,110
en 'n notasie genoem "Big Ohnotation"

26
00:01:06,110 --> 00:01:08,320
vir die beskrywing van hierdie.

27
00:01:08,320 --> 00:01:10,820
Die formele definisie is dat 'n funksie f (x)

28
00:01:10,820 --> 00:01:13,390
loop op die orde van g (x)

29
00:01:13,390 --> 00:01:15,140
indien daar 'n paar (x) waarde, x ₀ en

30
00:01:15,140 --> 00:01:17,630
n konstante, C, waarvoor

31
00:01:17,630 --> 00:01:19,340
f (x) is minder as of gelyk aan

32
00:01:19,340 --> 00:01:21,230
dat konstante keer g (x)

33
00:01:21,230 --> 00:01:23,190
vir alle x groter as x ₀.

34
00:01:23,190 --> 00:01:25,290
>> Maar moenie bang wees nie weg deur die formele definisie.

35
00:01:25,290 --> 00:01:28,020
Wat dit eintlik beteken in minder teoretiese terme?

36
00:01:28,020 --> 00:01:30,580
Wel, dit is basies 'n manier van die ontleding van

37
00:01:30,580 --> 00:01:33,580
hoe vinnig 'n program se runtime asimptoties groei.

38
00:01:33,580 --> 00:01:37,170
Dit is, na gelang van die grootte van jou insette verhoog na oneindigheid,

39
00:01:37,170 --> 00:01:41,390
Sê jy sorteer 'n verskeidenheid van grootte 1000 in vergelyking met 'n verskeidenheid van grootte 10.

40
00:01:41,390 --> 00:01:44,950
Hoe die looptyd van jou program groei?

41
00:01:44,950 --> 00:01:47,390
Byvoorbeeld, verbeel die tel van die aantal van karakters

42
00:01:47,390 --> 00:01:49,350
in 'n tou die eenvoudigste manier

43
00:01:49,350 --> 00:01:51,620
 deur die loop deur die hele string

44
00:01:51,620 --> 00:01:54,790
letter-vir-letter en die toevoeging van 1 tot 'n toonbank vir elke karakter.

45
00:01:55,700 --> 00:01:58,420
Hierdie algoritme is gesê om uit te voer in 'n lineêre tyd

46
00:01:58,420 --> 00:02:00,460
met betrekking tot die aantal karakters,

47
00:02:00,460 --> 00:02:02,670
'N' in die tou.

48
00:02:02,670 --> 00:02:04,910
In kort, dit loop in O (n).

49
00:02:05,570 --> 00:02:07,290
Hoekom is dit?

50
00:02:07,290 --> 00:02:09,539
Wel, die gebruik van hierdie benadering, die tyd wat nodig

51
00:02:09,539 --> 00:02:11,300
die hele string te verken

52
00:02:11,300 --> 00:02:13,920
is proporsioneel tot die aantal karakters.

53
00:02:13,920 --> 00:02:16,480
Die tel van die aantal van karakters in 'n 20-karakterstring

54
00:02:16,480 --> 00:02:18,580
gaan twee keer so lank as wat dit neem

55
00:02:18,580 --> 00:02:20,330
die karakters te tel in 'n 10-karakterstring,

56
00:02:20,330 --> 00:02:23,000
want jy het om te kyk na al die karakters

57
00:02:23,000 --> 00:02:25,740
en elke karakter neem die dieselfde hoeveelheid tyd om na te kyk.

58
00:02:25,740 --> 00:02:28,050
Soos jy toename in die aantal van karakters,

59
00:02:28,050 --> 00:02:30,950
sal die runtime lineêr toeneem met die inset lengte.

60
00:02:30,950 --> 00:02:33,500
>> Nou, verbeel as jy besluit dat lineêre tyd,

61
00:02:33,500 --> 00:02:36,390
O (n), was net nie vinnig genoeg vir jou?

62
00:02:36,390 --> 00:02:38,750
Miskien is jy die stoor van groot snare,

63
00:02:38,750 --> 00:02:40,450
en jy kan nie bekostig om die ekstra tyd wat dit sou neem

64
00:02:40,450 --> 00:02:44,000
al van hul karakters tel een-vir-een te deurkruis.

65
00:02:44,000 --> 00:02:46,650
So, jy besluit om iets anders te probeer.

66
00:02:46,650 --> 00:02:49,270
Wat gebeur as jy sou gebeur reeds die aantal karakters te stoor

67
00:02:49,270 --> 00:02:52,690
in die tou, sê in 'n veranderlike genaamd "len,

68
00:02:52,690 --> 00:02:54,210
vroeg in die program,

69
00:02:54,210 --> 00:02:57,800
voordat jy selfs die heel eerste karakter in die string gestoor?

70
00:02:57,800 --> 00:02:59,980
Dan al wat jy nou moet doen om uit te vind die string lengte,

71
00:02:59,980 --> 00:03:02,570
word bepaal wat die waarde van die veranderlike is.

72
00:03:02,570 --> 00:03:05,530
Jy wil nie hê om te kyk na die tou self op alle,

73
00:03:05,530 --> 00:03:08,160
en toegang tot die waarde van 'n veranderlike soos len word beskou as

74
00:03:08,160 --> 00:03:11,100
'n asimptoties konstante operasie,

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

76
00:03:13,070 --> 00:03:17,110
Hoekom is dit? Wel, onthou wat asimptotiese kompleksiteit beteken.

77
00:03:17,110 --> 00:03:19,100
Hoe werk die runtime verandering as die grootte

78
00:03:19,100 --> 00:03:21,400
van jou insette groei?

79
00:03:21,400 --> 00:03:24,630
>> Sê jy probeer om die aantal karakters wat in 'n groter string te kry.

80
00:03:24,630 --> 00:03:26,960
Wel, sou dit nie saak hoe groot jy die tou,

81
00:03:26,960 --> 00:03:28,690
selfs 'n miljoen karakters lank,

82
00:03:28,690 --> 00:03:31,150
al wat jy hoef te doen, die tou se lengte met hierdie benadering te vind,

83
00:03:31,150 --> 00:03:33,790
is om te lees uit die waarde van die veranderlike len,

84
00:03:33,790 --> 00:03:35,440
wat jy reeds gemaak.

85
00:03:35,440 --> 00:03:38,200
Die inset lengte, dit is die lengte van die string wat jy probeer om te vind,

86
00:03:38,200 --> 00:03:41,510
raak nie al hoe vinnig jou program loop.

87
00:03:41,510 --> 00:03:44,550
Hierdie deel van jou program sou ewe vinnig hardloop op 'n een-karakterstring

88
00:03:44,550 --> 00:03:46,170
en 'n duisend-karakterstring,

89
00:03:46,170 --> 00:03:49,140
en dit is hoekom hierdie program sal na verwys word as hardloop in konstante tyd

90
00:03:49,140 --> 00:03:51,520
met betrekking tot die invoer grootte.

91
00:03:51,520 --> 00:03:53,920
>> Natuurlik, daar is 'n nadeel.

92
00:03:53,920 --> 00:03:55,710
Jy spandeer 'n ekstra geheue ruimte op jou rekenaar

93
00:03:55,710 --> 00:03:57,380
die stoor van die veranderlike

94
00:03:57,380 --> 00:03:59,270
en die ekstra tyd wat dit neem om jou

95
00:03:59,270 --> 00:04:01,490
die werklike stoor van die veranderlike te doen,

96
00:04:01,490 --> 00:04:03,390
maar die punt staan ​​nog steeds,

97
00:04:03,390 --> 00:04:05,060
om uit te vind hoe lank jou string was

98
00:04:05,060 --> 00:04:07,600
nie afhang van die lengte van die string at all.

99
00:04:07,600 --> 00:04:10,720
So, dit loop in O (1) of konstante tyd.

100
00:04:10,720 --> 00:04:13,070
Dit beteken beslis nie te beteken dat

101
00:04:13,070 --> 00:04:15,610
dat jou kode in 1 stap loop,

102
00:04:15,610 --> 00:04:17,470
maar maak nie saak hoeveel stappe dit is,

103
00:04:17,470 --> 00:04:20,019
as dit nie verander met die grootte van die insette,

104
00:04:20,019 --> 00:04:23,420
dit is nog steeds asimptoties konstante wat ons verteenwoordig as O (1).

105
00:04:23,420 --> 00:04:25,120
>> Soos jy kan dink,

106
00:04:25,120 --> 00:04:27,940
daar is baie verskillende groot O Runtimes algoritmes te meet.

107
00:04:27,940 --> 00:04:32,980
O (n) ² algoritmes is asimptoties stadiger as O (n) algoritmes.

108
00:04:32,980 --> 00:04:35,910
Dit is, as die aantal elemente (n) groei,

109
00:04:35,910 --> 00:04:39,280
O (n) ² algoritmes sal uiteindelik meer tyd neem

110
00:04:39,280 --> 00:04:41,000
as O (n) algoritmes uit te voer.

111
00:04:41,000 --> 00:04:43,960
Dit beteken nie O (n) algoritmes altyd hardloop vinniger

112
00:04:43,960 --> 00:04:46,410
as O (n) ² algoritmes, selfs in dieselfde omgewing,

113
00:04:46,410 --> 00:04:48,080
op dieselfde hardeware.

114
00:04:48,080 --> 00:04:50,180
Miskien is dit vir klein inset-groottes,

115
00:04:50,180 --> 00:04:52,900
 die O (n) ² algoritme kan eintlik vinniger werk,

116
00:04:52,900 --> 00:04:55,450
maar uiteindelik, as die inset grootte verhoog

117
00:04:55,450 --> 00:04:58,760
na die oneindigheid, die O (n) ² algoritme runtime

118
00:04:58,760 --> 00:05:02,000
sal uiteindelik oorskadu die looptyd van die algoritme O (n).

119
00:05:02,000 --> 00:05:04,230
Net soos enige kwadratiese wiskundige funksie

120
00:05:04,230 --> 00:05:06,510
 enige lineêre funksie sal uiteindelik inhaal,

121
00:05:06,510 --> 00:05:09,200
maak nie saak hoeveel van 'n kop begin die lineêre funksie begin met.

122
00:05:10,010 --> 00:05:12,000
As jy werk met groot hoeveelhede data,

123
00:05:12,000 --> 00:05:15,510
algoritmes wat loop in O (n) ² tyd kan regtig beland stadiger jou program,

124
00:05:15,510 --> 00:05:17,770
maar vir klein inset groottes,

125
00:05:17,770 --> 00:05:19,420
jy sal waarskynlik nie eens agterkom nie.

126
00:05:19,420 --> 00:05:21,280
>> Nog 'n asimptotiese kompleksiteit is,

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

128
00:05:24,420 --> 00:05:26,340
'N voorbeeld van 'n algoritme wat loop hierdie vinnig

129
00:05:26,340 --> 00:05:29,060
is die klassieke binêre soek algoritme,

130
00:05:29,060 --> 00:05:31,850
vir die vind van 'n element in 'n reeds-gesorteerde lys van elemente.

131
00:05:31,850 --> 00:05:33,400
>> As jy nie weet wat binêre soek doen,

132
00:05:33,400 --> 00:05:35,170
Ek sal dit vir jou verduidelik regtig vinnig.

133
00:05:35,170 --> 00:05:37,020
Kom ons sê jy is op soek vir die nommer 3

134
00:05:37,020 --> 00:05:40,200
in die skikking van heelgetalle.

135
00:05:40,200 --> 00:05:42,140
Dit lyk op die middelste element van die skikking

136
00:05:42,140 --> 00:05:46,830
en vra, "Is die element wat ek wil groter as, gelyk aan of minder as dit?"

137
00:05:46,830 --> 00:05:49,150
As dit gelyk is, dan groot. Jy die element, en jy klaar is.

138
00:05:49,150 --> 00:05:51,300
As dit is groter, dan weet jy die element

139
00:05:51,300 --> 00:05:53,440
te wees in die regterkant van die skikking,

140
00:05:53,440 --> 00:05:55,200
en jy kan net kyk na wat in die toekoms,

141
00:05:55,200 --> 00:05:57,690
en as dit is kleiner, dan weet jy dit moet in die linkerkant.

142
00:05:57,690 --> 00:06:00,980
Hierdie proses word dan herhaal met die kleiner-grootte skikking

143
00:06:00,980 --> 00:06:02,870
totdat die korrekte element gevind word.

144
00:06:08,080 --> 00:06:11,670
>> Hierdie kragtige algoritme sny die skikking grootte in die helfte met elke operasie.

145
00:06:11,670 --> 00:06:14,080
So, 'n element te vind in 'n gesorteerde skikking van grootte 8,

146
00:06:14,080 --> 00:06:16,170
by die meeste (teken ₂ 8),

147
00:06:16,170 --> 00:06:18,450
of 3 van hierdie bedrywighede,

148
00:06:18,450 --> 00:06:22,260
die beheer van die middelste element, dan die skikking te sny in die helfte sal vereis word,

149
00:06:22,260 --> 00:06:25,670
terwyl 'n verskeidenheid van grootte 16 neem (teken ₂ 16),

150
00:06:25,670 --> 00:06:27,480
of 4 bedrywighede.

151
00:06:27,480 --> 00:06:30,570
Dit is net 1 meer operasie vir 'n verdubbel-grootte skikking.

152
00:06:30,570 --> 00:06:32,220
Verdubbeling van die grootte van die skikking

153
00:06:32,220 --> 00:06:35,160
verhoog die runtime deur slegs 1 stuk van hierdie kode.

154
00:06:35,160 --> 00:06:37,770
Weer, kontrole die middelste element van die lys, dan verdeel.

155
00:06:37,770 --> 00:06:40,440
So, is dit gesê om te werk in 'n logaritmiese tyd,

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

157
00:06:42,440 --> 00:06:44,270
Maar wag, sê jy,

158
00:06:44,270 --> 00:06:47,510
dit nie afhang van waar die element wat jy soek is in die lys?

159
00:06:47,510 --> 00:06:50,090
Wat as die eerste element wat jy kyk na gebeur om die regte een te wees?

160
00:06:50,090 --> 00:06:52,040
Dan, dit neem net 1 werking,

161
00:06:52,040 --> 00:06:54,310
maak nie saak hoe groot die lys is.

162
00:06:54,310 --> 00:06:56,310
>> Wel, dit is waarom die rekenaar wetenskaplikes het meer terme

163
00:06:56,310 --> 00:06:58,770
vir asimptotiese kompleksiteit wat weerspieël die beste-geval

164
00:06:58,770 --> 00:07:01,050
en die ergste-geval optredes van 'n algoritme.

165
00:07:01,050 --> 00:07:03,320
Meer gewoon, die boonste en onderste grense

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

167
00:07:05,090 --> 00:07:07,660
In die beste geval vir binêre soek, ons element is

168
00:07:07,660 --> 00:07:09,330
reg daar in die middel,

169
00:07:09,330 --> 00:07:11,770
en jy kry dit in konstante tyd,

170
00:07:11,770 --> 00:07:14,240
maak nie saak hoe groot die res van die skikking is.

171
00:07:15,360 --> 00:07:17,650
Die simbool wat gebruik word vir hierdie Ω.

172
00:07:17,650 --> 00:07:19,930
So, hierdie algoritme het gesê in Ω (1) uit te voer.

173
00:07:19,930 --> 00:07:21,990
In die beste geval, is dit bevind dat die element vinnig,

174
00:07:21,990 --> 00:07:24,200
maak nie saak hoe groot die skikking is,

175
00:07:24,200 --> 00:07:26,050
maar in die ergste geval,

176
00:07:26,050 --> 00:07:28,690
dit het uit te voer (log n) verdeel tjeks

177
00:07:28,690 --> 00:07:31,030
die regte element van die skikking te vind.

178
00:07:31,030 --> 00:07:34,270
Ergste geval bogrense word bedoel met die groot "O" wat jy reeds ken.

179
00:07:34,270 --> 00:07:38,080
So, dit is O (log n), maar Ω (1).

180
00:07:38,080 --> 00:07:40,680
>> 'N lineêre soek, in teenstelling,

181
00:07:40,680 --> 00:07:43,220
wat jy loop deur elke element van die skikking

182
00:07:43,220 --> 00:07:45,170
die een wat jy wil om te vind,

183
00:07:45,170 --> 00:07:47,420
is aan die beste Ω (1).

184
00:07:47,420 --> 00:07:49,430
Weereens, die eerste element wat jy wil.

185
00:07:49,430 --> 00:07:51,930
So, dit maak nie saak hoe groot die skikking is.

186
00:07:51,930 --> 00:07:54,840
In die ergste geval, dit is die laaste element in die skikking.

187
00:07:54,840 --> 00:07:58,560
Dus, jy het om te loop deur al die N-elemente in die skikking om dit te vind,

188
00:07:58,560 --> 00:08:02,170
graag as jy op soek vir 'n 3.

189
00:08:04,320 --> 00:08:06,030
So, dit loop in O (n) tyd

190
00:08:06,030 --> 00:08:09,330
want dit is eweredig aan die aantal elemente in die skikking.

191
00:08:10,800 --> 00:08:12,830
>> Een meer simbool wat gebruik word, is Θ.

192
00:08:12,830 --> 00:08:15,820
Dit kan gebruik word om algoritmes te beskryf waar die beste en die ergste gevalle

193
00:08:15,820 --> 00:08:17,440
is dieselfde.

194
00:08:17,440 --> 00:08:20,390
Dit is die geval in die string lengte algoritmes het ons gepraat oor vroeër.

195
00:08:20,390 --> 00:08:22,780
Dit is, as ons bêre dit in 'n veranderlike voor

196
00:08:22,780 --> 00:08:25,160
ons die stoor van die string en toegang tot dit later in konstante tyd.

197
00:08:25,160 --> 00:08:27,920
Maak nie saak watter getal

198
00:08:27,920 --> 00:08:30,130
ons stoor in daardie veranderlike, sal ons om te kyk na dit.

199
00:08:33,110 --> 00:08:35,110
Die beste geval is, ons kyk na dit

200
00:08:35,110 --> 00:08:37,120
en vind die lengte van die string.

201
00:08:37,120 --> 00:08:39,799
So Ω (1) of die beste geval konstante tyd.

202
00:08:39,799 --> 00:08:41,059
Die ergste geval is,

203
00:08:41,059 --> 00:08:43,400
ons kyk na dit en vind die lengte van die string.

204
00:08:43,400 --> 00:08:47,300
So, O (1) of konstante tyd in die ergste geval.

205
00:08:47,300 --> 00:08:49,180
Dus, sedert die beste geval en die ergste gevalle is die dieselfde,

206
00:08:49,180 --> 00:08:52,520
hierdie kan gesê word om uit te voer in Θ (1) tyd.

207
00:08:54,550 --> 00:08:57,010
>> In die opsomming, ons het goeie maniere om te redeneer oor kodes doeltreffendheid

208
00:08:57,010 --> 00:09:00,110
sonder om te weet enigiets oor die werklike wêreld tyd wat hulle neem om te hardloop,

209
00:09:00,110 --> 00:09:02,270
wat geraak word deur baie van die buite faktore,

210
00:09:02,270 --> 00:09:04,190
insluitende verskillende hardeware, sagteware,

211
00:09:04,190 --> 00:09:06,040
of die besonderhede van u kode.

212
00:09:06,040 --> 00:09:08,380
Ook, dit stel ons in staat om goed te redeneer oor wat sal gebeur

213
00:09:08,380 --> 00:09:10,180
wanneer die grootte van die insette toeneem.

214
00:09:10,180 --> 00:09:12,490
>> As jy loop in O (n) ² algoritme,

215
00:09:12,490 --> 00:09:15,240
of nog erger, 'n O (2 ⁿ) algoritme,

216
00:09:15,240 --> 00:09:17,170
een van die vinnigste groeiende tipes,

217
00:09:17,170 --> 00:09:19,140
jy regtig begin om die verlangsaming om op te let

218
00:09:19,140 --> 00:09:21,220
wanneer jy begin werk met groter hoeveelhede data.

219
00:09:21,220 --> 00:09:23,590
>> Dis asimptotiese kompleksiteit. Dankie.