1
00:00:07,720 --> 00:00:10,950
[Powered by Google Translate] Ve pengine habari watu kuzungumza kuhusu algorithm kufunga au ufanisi

2
00:00:10,950 --> 00:00:13,090
kwa ajili ya utekelezaji kazi yako maalum,

3
00:00:13,090 --> 00:00:16,110
lakini nini hasa nini maana ya algorithm kuwa haraka au ufanisi?

4
00:00:16,110 --> 00:00:18,580
Naam, ni si kuzungumza juu ya kipimo katika muda halisi,

5
00:00:18,580 --> 00:00:20,500
kama sekunde au dakika.

6
00:00:20,500 --> 00:00:22,220
Hii ni kwa sababu vifaa vya kompyuta

7
00:00:22,220 --> 00:00:24,260
na programu kutofautiana kwa kasi.

8
00:00:24,260 --> 00:00:26,020
Mpango wangu ili kukimbia polepole kuliko yako,

9
00:00:26,020 --> 00:00:28,000
kwa sababu mimi nina mbio kwenye kompyuta wakubwa,

10
00:00:28,000 --> 00:00:30,110
au kwa sababu mimi kutokea kwa kuwa kucheza mchezo video online

11
00:00:30,110 --> 00:00:32,670
wakati huo huo, ambayo ni hogging yangu kumbukumbu zote,

12
00:00:32,670 --> 00:00:35,400
au nipate kuwa mbio mpango wangu kupitia programu mbalimbali

13
00:00:35,400 --> 00:00:37,550
ambayo mawasiliano na mashine tofauti katika ngazi ya chini.

14
00:00:37,550 --> 00:00:39,650
Ni kama kulinganisha apples na machungwa.

15
00:00:39,650 --> 00:00:41,940
Kwa sababu tu kompyuta yangu polepole inachukua muda mrefu

16
00:00:41,940 --> 00:00:43,410
kuliko yako kutoa nyuma jibu

17
00:00:43,410 --> 00:00:45,510
haina maana una algorithm ufanisi zaidi.

18
00:00:45,510 --> 00:00:48,830
>> Hivyo, tangu hatuwezi moja kwa moja kulinganisha runtimes ya mipango

19
00:00:48,830 --> 00:00:50,140
katika sekunde au dakika,

20
00:00:50,140 --> 00:00:52,310
jinsi gani sisi kulinganisha 2 algorithms tofauti

21
00:00:52,310 --> 00:00:55,030
bila kujali vifaa zao au mazingira software?

22
00:00:55,030 --> 00:00:58,000
Kwa kujenga njia zaidi ya sare ya kupima ufanisi algorithmic,

23
00:00:58,000 --> 00:01:00,360
kompyuta wanasayansi na wanahisabati wameazimia

24
00:01:00,360 --> 00:01:03,830
dhana kwa ajili ya kupima utata asymptotic wa mpango

25
00:01:03,830 --> 00:01:06,110
na nukuu iitwayo 'Big Ohnotation'

26
00:01:06,110 --> 00:01:08,320
kwa kuelezea hili.

27
00:01:08,320 --> 00:01:10,820
ufafanuzi rasmi ni kwamba kazi f (x)

28
00:01:10,820 --> 00:01:13,390
anaendesha juu ya utaratibu wa g (x)

29
00:01:13,390 --> 00:01:15,140
kama kuna baadhi ya thamani (x), x ₀ na

30
00:01:15,140 --> 00:01:17,630
baadhi ya mara kwa mara, C, ambayo

31
00:01:17,630 --> 00:01:19,340
f (x) ni chini ya au sawa na

32
00:01:19,340 --> 00:01:21,230
kwamba mara kwa mara mara g (x)

33
00:01:21,230 --> 00:01:23,190
kwa ajili ya wote x mkubwa kuliko x ₀.

34
00:01:23,190 --> 00:01:25,290
>> Lakini si kuwa na hofu mbali kwa ufafanuzi rasmi.

35
00:01:25,290 --> 00:01:28,020
Je, hii kwa kweli maana katika suala chini ya kinadharia?

36
00:01:28,020 --> 00:01:30,580
Naam, ni kimsingi njia ya kuchambua

37
00:01:30,580 --> 00:01:33,580
jinsi ya kufunga Runtime mpango wa kukua asymptotically.

38
00:01:33,580 --> 00:01:37,170
Hiyo ni, kama kawaida ya pembejeo yako huongezeka kuelekea infinity,

39
00:01:37,170 --> 00:01:41,390
kusema, wewe ni kuchagua safu ya ukubwa 1000 ikilinganishwa na safu ya kawaida 10.

40
00:01:41,390 --> 00:01:44,950
Jinsi gani Runtime ya programu yako kukua?

41
00:01:44,950 --> 00:01:47,390
Kwa mfano, fikiria kuhesabu idadi ya wahusika

42
00:01:47,390 --> 00:01:49,350
katika string njia rahisi

43
00:01:49,350 --> 00:01:51,620
 kutembea kupitia string nzima

44
00:01:51,620 --> 00:01:54,790
barua-na-barua na kuongeza 1 kwa counter kwa tabia ya kila.

45
00:01:55,700 --> 00:01:58,420
Algorithm Hii inasemekana kukimbia katika wakati linear

46
00:01:58,420 --> 00:02:00,460
kwa heshima na idadi ya wahusika,

47
00:02:00,460 --> 00:02:02,670
'N' katika kamba.

48
00:02:02,670 --> 00:02:04,910
Kwa kifupi, ni anaendesha katika O (n).

49
00:02:05,570 --> 00:02:07,290
Kwa nini hii ni?

50
00:02:07,290 --> 00:02:09,539
Naam, kwa kutumia mbinu hii, muda unaotakiwa

51
00:02:09,539 --> 00:02:11,300
kwa traverse string nzima

52
00:02:11,300 --> 00:02:13,920
ni sawia na idadi ya wahusika.

53
00:02:13,920 --> 00:02:16,480
Kuhesabu idadi ya herufi katika string 20-tabia

54
00:02:16,480 --> 00:02:18,580
ni kwenda kuchukua mara mbili kama muda mrefu kama inachukua

55
00:02:18,580 --> 00:02:20,330
kuhesabu wahusika katika string 10-tabia,

56
00:02:20,330 --> 00:02:23,000
kwa sababu una kuangalia wahusika wote

57
00:02:23,000 --> 00:02:25,740
na tabia ya kila inachukua kiasi hicho cha muda wa kuangalia katika.

58
00:02:25,740 --> 00:02:28,050
Kama wewe kuongeza idadi ya wahusika,

59
00:02:28,050 --> 00:02:30,950
Runtime itaongeza linearly na urefu wa pembejeo.

60
00:02:30,950 --> 00:02:33,500
>> Sasa, hebu fikiria kama wewe kuamua kuwa wakati linear,

61
00:02:33,500 --> 00:02:36,390
O (n), tu si kwa kasi ya kutosha kwa ajili yenu?

62
00:02:36,390 --> 00:02:38,750
Labda wewe ni hifadhi ya masharti makubwa,

63
00:02:38,750 --> 00:02:40,450
na huwezi kununua muda wa ziada itachukua

64
00:02:40,450 --> 00:02:44,000
kwa traverse yote ya wahusika yao ya kuhesabu moja-na-moja.

65
00:02:44,000 --> 00:02:46,650
Hivyo, wewe kuamua kujaribu kitu tofauti.

66
00:02:46,650 --> 00:02:49,270
Nini kama kingetokea tayari kuhifadhi idadi ya herufi

67
00:02:49,270 --> 00:02:52,690
katika kamba, kusema, katika variable iitwayo 'len,'

68
00:02:52,690 --> 00:02:54,210
mapema katika mpango,

69
00:02:54,210 --> 00:02:57,800
kabla hata kuhifadhiwa tabia sana kwanza katika kamba yako?

70
00:02:57,800 --> 00:02:59,980
Kisha, wote wewe d kufanya sasa ili kujua urefu wa kamba,

71
00:02:59,980 --> 00:03:02,570
ni kuangalia nini thamani ya kutofautiana ni.

72
00:03:02,570 --> 00:03:05,530
Ungependa kuwa kuangalia string yenyewe wakati wote,

73
00:03:05,530 --> 00:03:08,160
na kupata thamani ya kutofautiana kama len ni kuchukuliwa

74
00:03:08,160 --> 00:03:11,100
asymptotically mara kwa mara wakati wa operesheni,

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

76
00:03:13,070 --> 00:03:17,110
Kwa nini hii ni? Naam, kumbukeni yale utata asymptotic maana yake.

77
00:03:17,110 --> 00:03:19,100
Jinsi gani mabadiliko Runtime kama kawaida

78
00:03:19,100 --> 00:03:21,400
wa pembejeo yako kukua?

79
00:03:21,400 --> 00:03:24,630
>> Sema ungekuwa kujaribu kupata idadi ya herufi katika kamba kubwa.

80
00:03:24,630 --> 00:03:26,960
Naam, ingekuwa si jambo jinsi kubwa ya kufanya kamba,

81
00:03:26,960 --> 00:03:28,690
hata milioni wahusika muda mrefu,

82
00:03:28,690 --> 00:03:31,150
wote wewe d kufanya kupata urefu wa kamba pamoja na mfumo huu,

83
00:03:31,150 --> 00:03:33,790
ni kusoma nje thamani ya len variable,

84
00:03:33,790 --> 00:03:35,440
ambayo tayari alifanya.

85
00:03:35,440 --> 00:03:38,200
urefu wa pembejeo, kwamba ni, urefu wa kamba wewe ni kujaribu kupata,

86
00:03:38,200 --> 00:03:41,510
haiathiri wakati wote jinsi ya kufunga programu yako anaendesha.

87
00:03:41,510 --> 00:03:44,550
Hii sehemu ya mpango wako ingekuwa kukimbia sawa haraka juu ya kamba moja-tabia

88
00:03:44,550 --> 00:03:46,170
na kamba elfu-tabia,

89
00:03:46,170 --> 00:03:49,140
na kwamba ni kwa nini mpango huu itakuwa inajulikana kama mbio katika muda wa mara kwa mara

90
00:03:49,140 --> 00:03:51,520
kwa heshima na ukubwa wa pembejeo.

91
00:03:51,520 --> 00:03:53,920
>> Bila shaka, kuna drawback.

92
00:03:53,920 --> 00:03:55,710
Kutumia ziada kumbukumbu nafasi kwenye kompyuta yako

93
00:03:55,710 --> 00:03:57,380
hifadhi ya kutofautiana

94
00:03:57,380 --> 00:03:59,270
na muda wa ziada inachukua wewe

95
00:03:59,270 --> 00:04:01,490
kufanya hifadhi ya halisi ya kutofautiana,

96
00:04:01,490 --> 00:04:03,390
lakini uhakika bado anasimama,

97
00:04:03,390 --> 00:04:05,060
kutafuta namna ya muda mrefu string yako ilikuwa

98
00:04:05,060 --> 00:04:07,600
Haitegemei urefu wa kamba wakati wote.

99
00:04:07,600 --> 00:04:10,720
Hivyo, ni anaendesha katika O (1) au wakati mara kwa mara.

100
00:04:10,720 --> 00:04:13,070
Bila ya shaka hii haina maana

101
00:04:13,070 --> 00:04:15,610
kwamba code yako anaendesha katika hatua 1,

102
00:04:15,610 --> 00:04:17,470
lakini hakuna jambo jinsi hatua nyingi ni,

103
00:04:17,470 --> 00:04:20,019
ikiwa haina mabadiliko na ukubwa wa pembejeo,

104
00:04:20,019 --> 00:04:23,420
bado asymptotically mara kwa mara ambayo sisi kuwakilisha kama O (1).

105
00:04:23,420 --> 00:04:25,120
>> Kama unaweza pengine guess,

106
00:04:25,120 --> 00:04:27,940
kuna tofauti kubwa O runtimes kupima algorithms na.

107
00:04:27,940 --> 00:04:32,980
O (n) ² algorithms ni asymptotically polepole zaidi kuliko O algorithms (n).

108
00:04:32,980 --> 00:04:35,910
Hiyo ni, kama idadi ya vipengele (n) kukua,

109
00:04:35,910 --> 00:04:39,280
hatimaye O (n) ² algorithms itachukua muda zaidi

110
00:04:39,280 --> 00:04:41,000
kuliko O (n) algorithms kukimbia.

111
00:04:41,000 --> 00:04:43,960
Hii haina maana O (n) algorithms daima kukimbia kwa kasi

112
00:04:43,960 --> 00:04:46,410
kuliko O (n) ² algorithms, hata katika mazingira sawa,

113
00:04:46,410 --> 00:04:48,080
juu ya vifaa hivyo.

114
00:04:48,080 --> 00:04:50,180
Labda kwa wadogo pembejeo ukubwa,

115
00:04:50,180 --> 00:04:52,900
 O (n) ² algorithm ili kweli kazi kwa kasi,

116
00:04:52,900 --> 00:04:55,450
lakini hatimaye, kama kawaida huongeza pembejeo

117
00:04:55,450 --> 00:04:58,760
kuelekea infinity, O (n) ² algorithm ya Runtime

118
00:04:58,760 --> 00:05:02,000
hatimaye kupatwa Runtime ya algorithm O (n).

119
00:05:02,000 --> 00:05:04,230
Tu kama kazi yoyote ya hisabati quadratic

120
00:05:04,230 --> 00:05:06,510
 hatimaye iwafikie kazi yoyote linear,

121
00:05:06,510 --> 00:05:09,200
haijalishi ni kiasi gani ya kichwa kuanza kazi linear kuanza mbali na.

122
00:05:10,010 --> 00:05:12,000
Kama wewe ni kufanya kazi kwa kiasi kikubwa cha data,

123
00:05:12,000 --> 00:05:15,510
algorithms kwamba kukimbia katika O (n) ² wakati kweli unaweza kuishia kupunguza chini ya mpango wako,

124
00:05:15,510 --> 00:05:17,770
lakini kwa ajili ya wadogo pembejeo ukubwa,

125
00:05:17,770 --> 00:05:19,420
pengine hata taarifa.

126
00:05:19,420 --> 00:05:21,280
>> Mwingine ni utata asymptotic,

127
00:05:21,280 --> 00:05:24,420
logarithmic muda, O (logi n).

128
00:05:24,420 --> 00:05:26,340
mfano wa algorithm kwamba anaendesha hii haraka

129
00:05:26,340 --> 00:05:29,060
ni classic binary tafuta algorithm,

130
00:05:29,060 --> 00:05:31,850
kwa ajili ya kutafuta kipengele katika orodha tayari-sorted ya vipengele.

131
00:05:31,850 --> 00:05:33,400
>> Kama hawajui nini binary tafuta gani,

132
00:05:33,400 --> 00:05:35,170
Mimi itabidi kueleza ni kwa wewe kweli haraka.

133
00:05:35,170 --> 00:05:37,020
Hebu sema wewe ni kuangalia kwa namba 3

134
00:05:37,020 --> 00:05:40,200
katika hii safu ya integers.

135
00:05:40,200 --> 00:05:42,140
Inaangalia kipengele katikati ya safu

136
00:05:42,140 --> 00:05:46,830
na anauliza, "Je, kipengele nataka zaidi kuliko, sawa na, au chini zaidi kuliko haya?"

137
00:05:46,830 --> 00:05:49,150
Kama ni sawa, basi kubwa. Wewe kupatikana kipengele, na wewe ni kosa.

138
00:05:49,150 --> 00:05:51,300
Kama ni kubwa, basi, unajua kipengele

139
00:05:51,300 --> 00:05:53,440
ina kuwa katika upande wa kulia wa safu,

140
00:05:53,440 --> 00:05:55,200
na unaweza tu kuangalia kwamba katika siku zijazo,

141
00:05:55,200 --> 00:05:57,690
na kama ni ndogo, basi, unajua ina kuwa katika upande wa kushoto.

142
00:05:57,690 --> 00:06:00,980
Utaratibu huu ni kisha alirudia na safu ndogo ya kawaida

143
00:06:00,980 --> 00:06:02,870
mpaka kipengele sahihi ni kupatikana.

144
00:06:08,080 --> 00:06:11,670
>> Hii algorithm nguvu kupunguzwa ukubwa safu katika nusu na operesheni ya kila.

145
00:06:11,670 --> 00:06:14,080
Hivyo, ili kupata kipengele katika safu ya ukubwa sorted 8,

146
00:06:14,080 --> 00:06:16,170
saa zaidi (kuingia ₂ 8),

147
00:06:16,170 --> 00:06:18,450
au 3 ya shughuli hizo,

148
00:06:18,450 --> 00:06:22,260
kuangalia kipengele katikati, kukata kisha safu katika nusu watatakiwa,

149
00:06:22,260 --> 00:06:25,670
ambapo safu ya ukubwa 16 inachukua (kuingia ₂ 16),

150
00:06:25,670 --> 00:06:27,480
au 4 shughuli.

151
00:06:27,480 --> 00:06:30,570
Hiyo tu 1 zaidi operesheni kwa safu mbili-size.

152
00:06:30,570 --> 00:06:32,220
Maradufu ukubwa wa safu

153
00:06:32,220 --> 00:06:35,160
huongeza Runtime na tu 1 chunk ya kanuni hii.

154
00:06:35,160 --> 00:06:37,770
Tena, kuangalia kipengele katikati ya orodha, basi splitting.

155
00:06:37,770 --> 00:06:40,440
Hivyo, ni alisema kufanya kazi katika muda logarithmic,

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

157
00:06:42,440 --> 00:06:44,270
Lakini kusubiri, unaweza kusema,

158
00:06:44,270 --> 00:06:47,510
haina hii wanategemea ambapo katika orodha ya kipengele wewe ni kuangalia kwa ni?

159
00:06:47,510 --> 00:06:50,090
Nini kama kipengele kwanza ukiangalia kinachotokea kwa kuwa moja ya haki?

160
00:06:50,090 --> 00:06:52,040
Kisha, tu inachukua 1 operesheni,

161
00:06:52,040 --> 00:06:54,310
hakuna jambo gani kubwa orodha ni.

162
00:06:54,310 --> 00:06:56,310
>> Naam, hiyo ndiyo sababu ya kompyuta wanasayansi suala zaidi

163
00:06:56,310 --> 00:06:58,770
kwa utata asymptotic ambayo kutafakari bora kesi

164
00:06:58,770 --> 00:07:01,050
na mbaya zaidi kesi maonyesho ya algorithm.

165
00:07:01,050 --> 00:07:03,320
Zaidi vizuri, mipaka ya juu na chini

166
00:07:03,320 --> 00:07:05,090
juu ya Runtime.

167
00:07:05,090 --> 00:07:07,660
Katika kesi bora kwa ajili ya kutafuta binary, kipengele yetu ni

168
00:07:07,660 --> 00:07:09,330
haki pale katikati,

169
00:07:09,330 --> 00:07:11,770
na wewe kupata katika muda mara kwa mara,

170
00:07:11,770 --> 00:07:14,240
hakuna jambo gani kubwa ya mapumziko ya safu ni.

171
00:07:15,360 --> 00:07:17,650
ishara kutumika kwa ajili ya hii ni Ω.

172
00:07:17,650 --> 00:07:19,930
Hivyo, algorithm hii ni alisema kukimbia katika Ω (1).

173
00:07:19,930 --> 00:07:21,990
Katika kesi bora, huikuta kipengele haraka,

174
00:07:21,990 --> 00:07:24,200
hakuna jambo gani kubwa safu ni,

175
00:07:24,200 --> 00:07:26,050
lakini katika hali mbaya,

176
00:07:26,050 --> 00:07:28,690
ina kufanya (logi n) hundi kupasuliwa

177
00:07:28,690 --> 00:07:31,030
wa safu wa kupata haki ya kipengele.

178
00:07:31,030 --> 00:07:34,270
Mipaka Mbaya-herufi ni inajulikana na kubwa "O" kwamba tayari kujua.

179
00:07:34,270 --> 00:07:38,080
Hivyo, ni O (logi n), lakini Ω (1).

180
00:07:38,080 --> 00:07:40,680
>> tafuta linear, kwa kulinganisha,

181
00:07:40,680 --> 00:07:43,220
ambayo wewe kutembea kwa njia ya kila kipengele cha safu

182
00:07:43,220 --> 00:07:45,170
kupata moja unataka,

183
00:07:45,170 --> 00:07:47,420
ni saa Ω bora (1).

184
00:07:47,420 --> 00:07:49,430
Tena, kipengele kwanza unataka.

185
00:07:49,430 --> 00:07:51,930
Hivyo, haijalishi jinsi kubwa ni safu.

186
00:07:51,930 --> 00:07:54,840
Katika kesi mbaya, ni kipengele mwisho katika safu.

187
00:07:54,840 --> 00:07:58,560
Hivyo, wewe kuwa na kutembea kwa njia ya mambo yote n katika safu ya kupata hiyo,

188
00:07:58,560 --> 00:08:02,170
kama kama walikuwa wanatafuta 3.

189
00:08:04,320 --> 00:08:06,030
Hivyo, ni anaendesha katika O muda (n)

190
00:08:06,030 --> 00:08:09,330
sababu ni sawia na idadi ya vipengele katika safu.

191
00:08:10,800 --> 00:08:12,830
>> Moja zaidi ishara kutumika ni Θ.

192
00:08:12,830 --> 00:08:15,820
Hii inaweza kutumika kuelezea algorithms ambapo kesi mzuri na mbaya zaidi

193
00:08:15,820 --> 00:08:17,440
ni sawa.

194
00:08:17,440 --> 00:08:20,390
Hii ni kesi katika algorithms string-urefu kuongelea mapema.

195
00:08:20,390 --> 00:08:22,780
Hiyo ni, kama sisi kuhifadhi katika variable kabla

196
00:08:22,780 --> 00:08:25,160
sisi kuhifadhi kamba na kupata hiyo baadaye katika wakati mara kwa mara.

197
00:08:25,160 --> 00:08:27,920
Hakuna jambo gani idadi

198
00:08:27,920 --> 00:08:30,130
sisi ni hifadhi katika variable kwamba, tutaweza kuwa na kuangalia saa yake.

199
00:08:33,110 --> 00:08:35,110
kesi bora ni, sisi kuangalia ni

200
00:08:35,110 --> 00:08:37,120
na kupata urefu wa kamba.

201
00:08:37,120 --> 00:08:39,799
Hivyo Ω (1) au bora-kesi ya mara kwa mara wakati.

202
00:08:39,799 --> 00:08:41,059
kesi mbaya zaidi ni,

203
00:08:41,059 --> 00:08:43,400
sisi kuangalia ni kupata na urefu wa kamba.

204
00:08:43,400 --> 00:08:47,300
Hivyo, O (1) au wakati mara kwa mara katika hali mbaya.

205
00:08:47,300 --> 00:08:49,180
Hivyo, tangu kesi bora na hali mbaya ni sawa,

206
00:08:49,180 --> 00:08:52,520
hii inaweza kuwa alisema kukimbia katika Θ wakati (1).

207
00:08:54,550 --> 00:08:57,010
>> Kwa muhtasari, tuna njia nzuri ya sababu kuhusu ufanisi codes

208
00:08:57,010 --> 00:09:00,110
bila kujua chochote kuhusu wakati halisi ya dunia wao kuchukua kukimbia,

209
00:09:00,110 --> 00:09:02,270
ambayo ni walioathirika na kura ya mambo ya nje,

210
00:09:02,270 --> 00:09:04,190
ikiwa ni pamoja na vifaa mbalimbali ya programu,,

211
00:09:04,190 --> 00:09:06,040
au specifics ya maadili yako.

212
00:09:06,040 --> 00:09:08,380
Pia, ni inaruhusu sisi kufikiri vyema kuhusu nini kitatokea

213
00:09:08,380 --> 00:09:10,180
wakati ukubwa wa ongezeko pembejeo.

214
00:09:10,180 --> 00:09:12,490
>> Kama wewe ni mbio katika algorithm O (n) ²,

215
00:09:12,490 --> 00:09:15,240
au mbaya zaidi, O (2 ⁿ) algorithm,

216
00:09:15,240 --> 00:09:17,170
moja ya aina ya kukua haraka sana,

217
00:09:17,170 --> 00:09:19,140
utasikia kweli kuanza kwa taarifa kushuka

218
00:09:19,140 --> 00:09:21,220
wakati wa kuanza kufanya kazi na kiasi kubwa ya data.

219
00:09:21,220 --> 00:09:23,590
>> Hiyo asymptotic utata. Shukrani.