1
00:00:07,720 --> 00:00:10,950
[Powered by Google Translate] Ou te pwobableman tande moun pale sou yon algorithm vit oswa efikas

2
00:00:10,950 --> 00:00:13,090
pou egzekite travay an patikilye ou a,

3
00:00:13,090 --> 00:00:16,110
men ki sa egzakteman sa vle di pou yon algorithm yo dwe vit oswa efikas?

4
00:00:16,110 --> 00:00:18,580
Oke, li pa pale osijè de yon mezi nan tan reyèl,

5
00:00:18,580 --> 00:00:20,500
tankou segonn oubyen minit.

6
00:00:20,500 --> 00:00:22,220
Sa a se paske kenkayri òdinatè

7
00:00:22,220 --> 00:00:24,260
ak lojisyèl varye byen wo.

8
00:00:24,260 --> 00:00:26,020
Pwogram m 'lan ka kouri pi dousman pase pou ou,

9
00:00:26,020 --> 00:00:28,000
paske mwen m 'kouri l' sou yon òdinatè ki pi gran,

10
00:00:28,000 --> 00:00:30,110
oswa paske mwen rive yo dwe jwe yon jwèt videyo sou entènèt

11
00:00:30,110 --> 00:00:32,670
an menm tan an, ki se hogging tout memwa m 'yo,

12
00:00:32,670 --> 00:00:35,400
oswa mwen ta ka ap kouri pwogram mwen an nan lojisyèl diferan

13
00:00:35,400 --> 00:00:37,550
ki kominike avèk machin nan yon fason diferan nan yon nivo ki ba.

14
00:00:37,550 --> 00:00:39,650
Se tankou konpare pòm ak zoranj.

15
00:00:39,650 --> 00:00:41,940
Jis paske òdinatè pi dousman mwen li pran plis

16
00:00:41,940 --> 00:00:43,410
pase ou bay tounen yon repons

17
00:00:43,410 --> 00:00:45,510
sa pa vle di ou gen algorithm nan pi efikas.

18
00:00:45,510 --> 00:00:48,830
>> Se konsa, depi nou pa ka konpare dirèkteman runtimes yo pou pwogram

19
00:00:48,830 --> 00:00:50,140
nan segonn oubyen minit,

20
00:00:50,140 --> 00:00:52,310
ki jan nou konpare 2 algoritm diferan

21
00:00:52,310 --> 00:00:55,030
kèlkeswa nan kenkayri yo oswa anviwònman lojisyèl?

22
00:00:55,030 --> 00:00:58,000
Pou kreye yon fason plis inifòm nan mezire algoritmik efikas,

23
00:00:58,000 --> 00:01:00,360
syantis konpitè ak matematisyèn te envante

24
00:01:00,360 --> 00:01:03,830
konsèp pou mezire konpleksite a asenptotik nan yon pwogram

25
00:01:03,830 --> 00:01:06,110
ak yon notasyon rele 'Big Ohnotation'

26
00:01:06,110 --> 00:01:08,320
pou dekri sa a.

27
00:01:08,320 --> 00:01:10,820
Definisyon nan fòmèl se ke yon fonksyon f (x)

28
00:01:10,820 --> 00:01:13,390
kouri sou lòd la g (x)

29
00:01:13,390 --> 00:01:15,140
si gen egziste kèk valè (x), x ₀ ak

30
00:01:15,140 --> 00:01:17,630
kèk konstan, C, pou ki

31
00:01:17,630 --> 00:01:19,340
f (x) se mwens pase oswa egal a

32
00:01:19,340 --> 00:01:21,230
ki konstan fwa g (x)

33
00:01:21,230 --> 00:01:23,190
pou tout x pi gran pase x ₀.

34
00:01:23,190 --> 00:01:25,290
>> Men, pa dwe pè ale nan definisyon fòmèl la.

35
00:01:25,290 --> 00:01:28,020
Ki sa ki sa sa a aktyèlman vle di nan mwens tèm teyorik?

36
00:01:28,020 --> 00:01:30,580
Oke, bazikman yon fason pou analize

37
00:01:30,580 --> 00:01:33,580
konbyen vit ègzekutabl yon pwogram nan ap grandi asenptotik.

38
00:01:33,580 --> 00:01:37,170
Sa se, kòm gwosè a nan entrain ou ogmante nan direksyon pou debordeman,

39
00:01:37,170 --> 00:01:41,390
di, w ap Fouye yon etalaj de gwosè 1000 konpare ak yon etalaj de gwosè 10.

40
00:01:41,390 --> 00:01:44,950
Ki jan ègzekutabl a nan pwogram ou an grandi?

41
00:01:44,950 --> 00:01:47,390
Pou egzanp, imajine konte kantite karaktè

42
00:01:47,390 --> 00:01:49,350
nan yon fisèl wout la pi senp

43
00:01:49,350 --> 00:01:51,620
 pa mache nan fil la tout antye

44
00:01:51,620 --> 00:01:54,790
lèt-pa-lèt ak ajoute 1 nan yon kontwa pou chak karaktè.

45
00:01:55,700 --> 00:01:58,420
Sa a se algorithm di kouri nan tan lineyè

46
00:01:58,420 --> 00:02:00,460
ki gen rapò ak ki kantite karaktè,

47
00:02:00,460 --> 00:02:02,670
'N' nan fil la.

48
00:02:02,670 --> 00:02:04,910
Nan ti bout tan, li kouri nan O (n).

49
00:02:05,570 --> 00:02:07,290
Poukisa se sa a?

50
00:02:07,290 --> 00:02:09,539
Oke, lè l sèvi avèk apwòch sa a, tan yo mande

51
00:02:09,539 --> 00:02:11,300
Traverse fisèl la tout antye

52
00:02:11,300 --> 00:02:13,920
se pwopòsyonèl ak kantite karaktè.

53
00:02:13,920 --> 00:02:16,480
Konte kantite karaktè nan yon fisèl 20-karaktè

54
00:02:16,480 --> 00:02:18,580
a pral pran de fwa osi lontan ke li pran

55
00:02:18,580 --> 00:02:20,330
ka konte karaktè yo nan yon fisèl 10-karaktè,

56
00:02:20,330 --> 00:02:23,000
paske ou gen fè yon gade nan tout karaktè yo

57
00:02:23,000 --> 00:02:25,740
ak chak karaktè pran menm kantite lajan an nan tan fè yon gade nan.

58
00:02:25,740 --> 00:02:28,050
Kòm ou ogmante kantite karaktè,

59
00:02:28,050 --> 00:02:30,950
ègzekutabl an ap ogmante linear ak longè a D '.

60
00:02:30,950 --> 00:02:33,500
>> Koulye a, imajine si ou deside lè sa a lineyè,

61
00:02:33,500 --> 00:02:36,390
O (n), jis pa t 'vit ase pou ou?

62
00:02:36,390 --> 00:02:38,750
Petèt w ap estoke strings gwo,

63
00:02:38,750 --> 00:02:40,450
epi ou pa kapab peye tan siplemantè a li ta pran

64
00:02:40,450 --> 00:02:44,000
Traverse tout nan karaktè yo konte yon sèl-pa-youn.

65
00:02:44,000 --> 00:02:46,650
Se konsa, ou deside eseye yon bagay diferan.

66
00:02:46,650 --> 00:02:49,270
Ki sa ki si ou ta rive deja estoke ki kantite karaktè

67
00:02:49,270 --> 00:02:52,690
nan fisèl la, di, nan yon varyab rele 'Len,'

68
00:02:52,690 --> 00:02:54,210
byen bonè nan nan pwogram nan,

69
00:02:54,210 --> 00:02:57,800
anvan ou menm ki estoke pèsonaj la trè premye nan fil ou a?

70
00:02:57,800 --> 00:02:59,980
Lè sa a, tout sa ou ta dwe fè kounye a yo chèche konnen longè a fisèl,

71
00:02:59,980 --> 00:03:02,570
se tcheke sa ki valè a nan varyab la se.

72
00:03:02,570 --> 00:03:05,530
Ou pa ta gen fè yon gade nan fisèl la li menm nan tout,

73
00:03:05,530 --> 00:03:08,160
ak gen aksè nan valè a nan yon varyab tankou Len ki konsidere kòm

74
00:03:08,160 --> 00:03:11,100
yon operasyon tan asenptotik konstan,

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

76
00:03:13,070 --> 00:03:17,110
Poukisa se sa a? Oke, sonje sa konpleksite asenptotik vle di.

77
00:03:17,110 --> 00:03:19,100
Kijan chanjman nan ègzekutabl kòm gwosè a

78
00:03:19,100 --> 00:03:21,400
entrées nan ou a ap grandi?

79
00:03:21,400 --> 00:03:24,630
>> Di ou te ap eseye jwenn nimewo a nan karaktè nan yon fisèl pi gran.

80
00:03:24,630 --> 00:03:26,960
Oke, li pa ta gen pwoblèm ki jan gwo ou fè fisèl la,

81
00:03:26,960 --> 00:03:28,690
menm yon milyon dola karaktè long,

82
00:03:28,690 --> 00:03:31,150
tout sa ou ta gen pou fè pou jwenn longè fil la ak apwòch sa a,

83
00:03:31,150 --> 00:03:33,790
a se fè lekti soti valè a nan Len a varyab,

84
00:03:33,790 --> 00:03:35,440
ki ou deja fè fè yo.

85
00:03:35,440 --> 00:03:38,200
D 'longè a, se sa ki, longè a nan fisèl la w ap eseye jwenn,

86
00:03:38,200 --> 00:03:41,510
pa afekte nan tout kouman vit pwogram ou an ap kouri.

87
00:03:41,510 --> 00:03:44,550
Pati sa a nan pwogram ou an ta kouri egalman vit sou yon fisèl yon sèl-karaktè

88
00:03:44,550 --> 00:03:46,170
ak yon fisèl mil-karaktè,

89
00:03:46,170 --> 00:03:49,140
ak sa a, se poukisa ta pwogram sa a dwe refere yo kòm kouri nan tan konstan

90
00:03:49,140 --> 00:03:51,520
ki gen rapò ak gwosè a D '.

91
00:03:51,520 --> 00:03:53,920
>> Natirèlman, gen yon dezavantaj.

92
00:03:53,920 --> 00:03:55,710
Ou depanse plis espas memwa sou òdinatè ou

93
00:03:55,710 --> 00:03:57,380
estoke varyab la

94
00:03:57,380 --> 00:03:59,270
ak tan siplemantè a li pran ou

95
00:03:59,270 --> 00:04:01,490
fè depo aktyèl la nan varyab la,

96
00:04:01,490 --> 00:04:03,390
men pwen an toujou rete,

97
00:04:03,390 --> 00:04:05,060
jwenn deyò konbyen tan fisèl ou te

98
00:04:05,060 --> 00:04:07,600
pa depann de longè nan fisèl la nan tout.

99
00:04:07,600 --> 00:04:10,720
Se konsa, li kouri nan O (1) oswa tan konstan.

100
00:04:10,720 --> 00:04:13,070
Sa a sètènman pa gen vle di

101
00:04:13,070 --> 00:04:15,610
ki kòd ou a kouri nan 1 etap,

102
00:04:15,610 --> 00:04:17,470
men pa gen pwoblèm ki jan anpil etap li ye,

103
00:04:17,470 --> 00:04:20,019
si li pa chanje avèk gwosè a nan entrain yo,

104
00:04:20,019 --> 00:04:23,420
li la toujou asenptotik konstan ki nou reprezante kòm O (1).

105
00:04:23,420 --> 00:04:25,120
>> Kòm ou ka pwobableman devine,

106
00:04:25,120 --> 00:04:27,940
genyen anpil moun ki diferan gwo runtimes O ki mezire algoritm avèk yo.

107
00:04:27,940 --> 00:04:32,980
O (n) ² algoritm yo se asenptotik pi dousman pase O algoritm (n).

108
00:04:32,980 --> 00:04:35,910
Sa se, kòm nimewo a nan eleman (n) ap grandi,

109
00:04:35,910 --> 00:04:39,280
evantyèlman O (n) ² algoritm ap pran plis tan

110
00:04:39,280 --> 00:04:41,000
pase O (n) algoritm nan kouri.

111
00:04:41,000 --> 00:04:43,960
Sa pa vle di O (n) algoritm toujou kouri pi vit

112
00:04:43,960 --> 00:04:46,410
pase O (n) algoritm ², menm nan anviwònman an menm,

113
00:04:46,410 --> 00:04:48,080
nan kenkayri a menm.

114
00:04:48,080 --> 00:04:50,180
Petèt pou gwosè D 'piti,

115
00:04:50,180 --> 00:04:52,900
 O an (n) ² algorithm ta ka aktyèlman ap travay pi vit,

116
00:04:52,900 --> 00:04:55,450
men, evantyèlman, menm jan gwosè a D 'ogmante

117
00:04:55,450 --> 00:04:58,760
nan direksyon pou debordeman, O (n) ègzekutabl la ² algorithm nan

118
00:04:58,760 --> 00:05:02,000
pral evantyèlman eklips ègzekutabl a nan algorithm nan O (n).

119
00:05:02,000 --> 00:05:04,230
Jis tankou nenpòt ki fonksyon kwadratik matematik

120
00:05:04,230 --> 00:05:06,510
 pral evantyèlman rapouswiv nenpòt fonksyon lineyè,

121
00:05:06,510 --> 00:05:09,200
pa gen pwoblèm konbyen nan yon tèt kòmanse fonksyon an lineyè kòmanse koupe ak.

122
00:05:10,010 --> 00:05:12,000
Si w ap travay ak gwo kantite done,

123
00:05:12,000 --> 00:05:15,510
algoritm ki kouri nan O (n) ² tan ka vrèman fini ralanti desann pwogram ou an,

124
00:05:15,510 --> 00:05:17,770
men pou gwosè D 'piti,

125
00:05:17,770 --> 00:05:19,420
pwobableman ou pa pral menm remake.

126
00:05:19,420 --> 00:05:21,280
>> Yon lòt konpleksite asenptotik se,

127
00:05:21,280 --> 00:05:24,420
logaritmik tan, O (boutèy demi lit n).

128
00:05:24,420 --> 00:05:26,340
Yon egzanp yon algorithm ki kouri sa a byen vit

129
00:05:26,340 --> 00:05:29,060
se binè algorithm la klasik rechèch,

130
00:05:29,060 --> 00:05:31,850
pou jwenn yon eleman nan yon lis deja-Ranje nan eleman.

131
00:05:31,850 --> 00:05:33,400
>> Si ou pa konnen ki sa ki rechèch binè fè,

132
00:05:33,400 --> 00:05:35,170
Mwen pral eksplike li pou ou reyèlman byen vit.

133
00:05:35,170 --> 00:05:37,020
Se pou nou di w ap chèche pou yon nimewo pou la 3

134
00:05:37,020 --> 00:05:40,200
nan sa a seri nonm antye relatif.

135
00:05:40,200 --> 00:05:42,140
Li sanble nan eleman nan mitan nan etalaj la

136
00:05:42,140 --> 00:05:46,830
epi mande, "se eleman ki mwen vle pi gran pase, egal a, oswa mwens pase sa a?"

137
00:05:46,830 --> 00:05:49,150
Si li la egal, Lè sa a, gwo. Ou te jwenn eleman a, epi w ap fè.

138
00:05:49,150 --> 00:05:51,300
Si li nan pi gwo a, Lè sa a, ou konnen eleman nan

139
00:05:51,300 --> 00:05:53,440
gen yo dwe nan bò dwat la etalaj la,

140
00:05:53,440 --> 00:05:55,200
epi ou ka sèlman gade nan ki nan tan kap vini an,

141
00:05:55,200 --> 00:05:57,690
epi si li nan pi piti, Lè sa a, ou konnen li te gen nan bò gòch la.

142
00:05:57,690 --> 00:06:00,980
Pwosesis sa a Lè sa a, repete ak etalaj ki pi piti a-gwosè

143
00:06:00,980 --> 00:06:02,870
jiskaske yo eleman ki kòrèk la jwenn.

144
00:06:08,080 --> 00:06:11,670
>> Sa a algorithm pwisan koupe gwosè a etalaj nan mwatye ak chak operasyon.

145
00:06:11,670 --> 00:06:14,080
Se konsa, jwenn yon eleman nan yon etalaj Ranje nan gwosè 8,

146
00:06:14,080 --> 00:06:16,170
nan pifò (ouvri sesyon ₂ 8),

147
00:06:16,170 --> 00:06:18,450
oswa 3 nan operasyon sa yo,

148
00:06:18,450 --> 00:06:22,260
tcheke eleman nan mitan, lè sa a koupe etalaj la nan mwatye yo pral mande,

149
00:06:22,260 --> 00:06:25,670
Lè nou konsidere ke yon etalaj de gwosè 16 pran (ouvri sesyon ₂ 16),

150
00:06:25,670 --> 00:06:27,480
oswa 4 operasyon yo.

151
00:06:27,480 --> 00:06:30,570
Sa a se sèlman 1 operasyon plis pou yon etalaj double-gwosè.

152
00:06:30,570 --> 00:06:32,220
Double pwensip gwosè a nan etalaj la

153
00:06:32,220 --> 00:06:35,160
ogmante ègzekutabl a pa sèlman 1 ti moso nan sa a kòd.

154
00:06:35,160 --> 00:06:37,770
Yon fwa ankò, tcheke eleman nan mitan nan lis la, Lè sa a, divize.

155
00:06:37,770 --> 00:06:40,440
Se konsa, li di l opere nan tan logaritmik,

156
00:06:40,440 --> 00:06:42,440
O (boutèy demi lit n).

157
00:06:42,440 --> 00:06:44,270
Men, tann, ou di,

158
00:06:44,270 --> 00:06:47,510
pa sa a depann sou kote nan lis la eleman nan w ap chèche pou se?

159
00:06:47,510 --> 00:06:50,090
E si eleman nan premye ou gade nan k ap pase yo dwe youn nan dwa?

160
00:06:50,090 --> 00:06:52,040
Lè sa a,, li sèlman pran 1 operasyon,

161
00:06:52,040 --> 00:06:54,310
pa gen pwoblèm ki jan gwo lis la se.

162
00:06:54,310 --> 00:06:56,310
>> Oke, sa a, se poukisa syantis òdinatè gen plis tèm

163
00:06:56,310 --> 00:06:58,770
pou asenptotik konpleksite ki reflete pi byen ki ka a

164
00:06:58,770 --> 00:07:01,050
ak pi move-ka pèfòmans nan yon algorithm.

165
00:07:01,050 --> 00:07:03,320
Plis byen, anwo ak pi ba limit yo

166
00:07:03,320 --> 00:07:05,090
sou ègzekutabl la.

167
00:07:05,090 --> 00:07:07,660
Nan ka a pi bon pou rechèch binè, eleman nou an, se

168
00:07:07,660 --> 00:07:09,330
dwa gen nan mitan an,

169
00:07:09,330 --> 00:07:11,770
epi ou jwenn li nan tan konstan,

170
00:07:11,770 --> 00:07:14,240
pa gen pwoblèm ki jan gwo rès la nan etalaj la se.

171
00:07:15,360 --> 00:07:17,650
Senbòl yo itilize pou sa a se Ω.

172
00:07:17,650 --> 00:07:19,930
Se konsa, sa a algorithm te di se kouri nan Ω (1).

173
00:07:19,930 --> 00:07:21,990
Nan ka ki pi bon, li jwenn eleman ki byen vit,

174
00:07:21,990 --> 00:07:24,200
pa gen pwoblèm ki jan gwo etalaj la se,

175
00:07:24,200 --> 00:07:26,050
men nan ka ki pi mal la,

176
00:07:26,050 --> 00:07:28,690
li gen fè (boutèy demi lit n) chèk separe

177
00:07:28,690 --> 00:07:31,030
nan etalaj la jwenn eleman ki dwat.

178
00:07:31,030 --> 00:07:34,270
Pi move-ka anwo avèk limit yo refere yo bay ak gwo "O la" ke ou deja konnen.

179
00:07:34,270 --> 00:07:38,080
Se konsa, li O (boutèy demi lit n), men Ω (1).

180
00:07:38,080 --> 00:07:40,680
>> Yon rechèch lineyè, pa kontra,

181
00:07:40,680 --> 00:07:43,220
nan kote ou mache nan chak eleman nan etalaj la

182
00:07:43,220 --> 00:07:45,170
jwenn youn nan ou vle,

183
00:07:45,170 --> 00:07:47,420
se nan pi bon Ω (1).

184
00:07:47,420 --> 00:07:49,430
Yon fwa ankò, eleman nan premye ou vle.

185
00:07:49,430 --> 00:07:51,930
Se konsa, li pa gen pwoblèm ki jan gwo etalaj la se.

186
00:07:51,930 --> 00:07:54,840
Nan ka ki pi mal la, li nan eleman an dènye nan etalaj la.

187
00:07:54,840 --> 00:07:58,560
Se konsa, ou gen mache nan tout eleman n nan etalaj la jwenn li,

188
00:07:58,560 --> 00:08:02,170
renmen si w te gen ap chèche pou yon 3.

189
00:08:04,320 --> 00:08:06,030
Se konsa, li kouri nan tan O (n)

190
00:08:06,030 --> 00:08:09,330
paske li nan pwopòsyonèl ak kantite eleman nan etalaj la.

191
00:08:10,800 --> 00:08:12,830
>> Youn nan senbòl plis itilize se Θ.

192
00:08:12,830 --> 00:08:15,820
Sa a ka sèvi ak dekri algoritm kote pi byen ak pi move ka yo

193
00:08:15,820 --> 00:08:17,440
se menm bagay la.

194
00:08:17,440 --> 00:08:20,390
Sa a se ka a nan algoritm yo fisèl-longè nou te pale de pi bonè.

195
00:08:20,390 --> 00:08:22,780
Sa se, si nou mete yo nan yon varyab anvan

196
00:08:22,780 --> 00:08:25,160
nou sere fisèl la ak jwenn aksè nan li pita nan konstan tan.

197
00:08:25,160 --> 00:08:27,920
Pa gen pwoblèm sa nimewo

198
00:08:27,920 --> 00:08:30,130
nou ap estoke nan varyab sa a, nou pral oblije gade nan li.

199
00:08:33,110 --> 00:08:35,110
Ka a se pi bon, nou gade nan li

200
00:08:35,110 --> 00:08:37,120
ak jwenn longè fil la.

201
00:08:37,120 --> 00:08:39,799
Se konsa, Ω (1) oswa pi bon-ka tan konstan.

202
00:08:39,799 --> 00:08:41,059
Ka ki pi mal la se,

203
00:08:41,059 --> 00:08:43,400
nou gade nan li epi li jwenn longè fil la.

204
00:08:43,400 --> 00:08:47,300
Se konsa, O (1) oswa konstan tan nan pi move ka.

205
00:08:47,300 --> 00:08:49,180
Se konsa, depi ka a pi byen ak pi move ka yo se menm bagay la,

206
00:08:49,180 --> 00:08:52,520
sa a kapab di nan kouri nan tan Θ (1).

207
00:08:54,550 --> 00:08:57,010
>> An rezime, nou gen bon fason di rezon sou efikasite kòd

208
00:08:57,010 --> 00:09:00,110
san yo pa konnen anyen sou tan an nan lavi reyèl yo pran kouri,

209
00:09:00,110 --> 00:09:02,270
ki se afekte pa anpil nan faktè deyò a,

210
00:09:02,270 --> 00:09:04,190
ki gen ladan diferan kenkayri, lojisyèl,

211
00:09:04,190 --> 00:09:06,040
oswa kòman sa ap kòd ou a.

212
00:09:06,040 --> 00:09:08,380
Epitou, li pèmèt nou fè lojik byen sou sa ki pral rive

213
00:09:08,380 --> 00:09:10,180
lè gwosè a nan ogmantasyon yo entrain.

214
00:09:10,180 --> 00:09:12,490
>> Si w ap kouri nan O (n) algorithm ²,

215
00:09:12,490 --> 00:09:15,240
oswa pi mal, yon O (2 ⁿ) algorithm,

216
00:09:15,240 --> 00:09:17,170
yonn nan plus ki kalite k ap grandi,

217
00:09:17,170 --> 00:09:19,140
ou pral reyèlman kòmanse avi ralentissement la

218
00:09:19,140 --> 00:09:21,220
lè ou kòmanse ap travay ak pi gwo kantite done.

219
00:09:21,220 --> 00:09:23,590
>> Sa a konpleksite asenptotik. Mèsi.