1
00:00:07,720 --> 00:00:10,950
[Powered by Google Translate] Þú hefur sennilega heyrt fólk tala um hratt eða duglegur reiknirit

2
00:00:10,950 --> 00:00:13,090
fyrir framkvæmd tiltekna verkefni þínu,

3
00:00:13,090 --> 00:00:16,110
En hvað nákvæmlega þýðir það fyrir reiknirit til að vera fljótur eða duglegur?

4
00:00:16,110 --> 00:00:18,580
Jæja, það er ekki að tala um mælingu í rauntíma,

5
00:00:18,580 --> 00:00:20,500
eins og sekúndur eða mínútur.

6
00:00:20,500 --> 00:00:22,220
Þetta er vegna þess að tölva vélbúnaður

7
00:00:22,220 --> 00:00:24,260
og hugbúnaður mismunandi harkalegur.

8
00:00:24,260 --> 00:00:26,020
Program minn gæti keyrt hægar en þitt,

9
00:00:26,020 --> 00:00:28,000
vegna þess að ég er að keyra það á eldri tölvu,

10
00:00:28,000 --> 00:00:30,110
eða vegna þess að ég koma að spila online vídeó leikur

11
00:00:30,110 --> 00:00:32,670
á sama tíma, sem er svínslegur allt minni mitt,

12
00:00:32,670 --> 00:00:35,400
eða ég gæti verið að keyra forritið mitt í gegnum mismunandi hugbúnaði

13
00:00:35,400 --> 00:00:37,550
sem hefur samband við vélina öðruvísi á lágu stigi.

14
00:00:37,550 --> 00:00:39,650
Það er eins og að bera saman epli og appelsínur.

15
00:00:39,650 --> 00:00:41,940
Bara vegna þess að hægari tölvan mín tekur lengri

16
00:00:41,940 --> 00:00:43,410
en ykkur að gefa til baka svar

17
00:00:43,410 --> 00:00:45,510
þýðir ekki að þú hefur skilvirkari reiknirit.

18
00:00:45,510 --> 00:00:48,830
>> Svo, þar sem við getum ekki beint bera runtimes af forritum

19
00:00:48,830 --> 00:00:50,140
í sekúndum eða mínútum,

20
00:00:50,140 --> 00:00:52,310
hvernig bera saman við 2 mismunandi reiknirit

21
00:00:52,310 --> 00:00:55,030
óháð vélbúnaði eða hugbúnaði umhverfi?

22
00:00:55,030 --> 00:00:58,000
Til að búa til fleiri samræmda leið til að mæla lausnarleiðar skilvirkni,

23
00:00:58,000 --> 00:01:00,360
tölva vísindamenn og stærðfræðingar hafa hugsað

24
00:01:00,360 --> 00:01:03,830
hugtök til að mæla asymptotic flókið forrit

25
00:01:03,830 --> 00:01:06,110
og tákn sem kallast "Big Ohnotation '

26
00:01:06,110 --> 00:01:08,320
til að lýsa þessu.

27
00:01:08,320 --> 00:01:10,820
Formlega skilgreiningin er að fall f (x)

28
00:01:10,820 --> 00:01:13,390
keyrir á röð g (x)

29
00:01:13,390 --> 00:01:15,140
ef það er nokkur (x) gildi, x ₀ og

30
00:01:15,140 --> 00:01:17,630
sumir stöðug, C, sem

31
00:01:17,630 --> 00:01:19,340
f (x) er minna en eða jafnt og

32
00:01:19,340 --> 00:01:21,230
að fasti sinnum g (x)

33
00:01:21,230 --> 00:01:23,190
fyrir öll x meiri en x ₀.

34
00:01:23,190 --> 00:01:25,290
>> En ekki vera hrædd í burtu með formlega skilgreiningu.

35
00:01:25,290 --> 00:01:28,020
Hvað þýðir þetta í raun í minni fræðilegum skilmála?

36
00:01:28,020 --> 00:01:30,580
Jæja, það er í grundvallaratriðum leið til að greina

37
00:01:30,580 --> 00:01:33,580
hversu hratt afturkreistingur forrit vex aðfellu.

38
00:01:33,580 --> 00:01:37,170
Það er, eins og stærð aðföngum þinn eykst til óendanleika,

39
00:01:37,170 --> 00:01:41,390
segja, þú ert að flokka fjölda stærð 1000 samanborið við fjölda stærð 10.

40
00:01:41,390 --> 00:01:44,950
Hvernig virkar afturkreistingur af forritinu vaxa?

41
00:01:44,950 --> 00:01:47,390
Til dæmis ímynda sér að telja fjölda stafa

42
00:01:47,390 --> 00:01:49,350
í streng einfaldasta leiðin

43
00:01:49,350 --> 00:01:51,620
 með því að ganga í gegnum allt band

44
00:01:51,620 --> 00:01:54,790
bréf-við-bréf og bæta 1 við teljarann ​​fyrir hvern staf.

45
00:01:55,700 --> 00:01:58,420
Þetta reiknirit er sagt að keyra í línulegum tíma

46
00:01:58,420 --> 00:02:00,460
með tilliti til fjölda þeirra stafa,

47
00:02:00,460 --> 00:02:02,670
'N' í streng.

48
00:02:02,670 --> 00:02:04,910
Í stuttu máli, keyrir það á O (n).

49
00:02:05,570 --> 00:02:07,290
Hvers vegna er þetta?

50
00:02:07,290 --> 00:02:09,539
Jæja, með því að nota þessa aðferð, tíma þarf

51
00:02:09,539 --> 00:02:11,300
að fara yfir allt band

52
00:02:11,300 --> 00:02:13,920
er í réttu hlutfalli við fjölda þeirra stafa.

53
00:02:13,920 --> 00:02:16,480
Telja fjölda stafa í 20-stafa streng

54
00:02:16,480 --> 00:02:18,580
er að fara að taka tvisvar svo lengi sem það tekur

55
00:02:18,580 --> 00:02:20,330
til að telja stafi í 10-stafa streng,

56
00:02:20,330 --> 00:02:23,000
vegna þess að þú þarft að líta á alla stafi

57
00:02:23,000 --> 00:02:25,740
og hver persóna tekur sama magn af tíma til að líta á.

58
00:02:25,740 --> 00:02:28,050
Eins og þú auka fjölda þeirra stafa,

59
00:02:28,050 --> 00:02:30,950
afturkreistingur eykst línulega með inntak lengd.

60
00:02:30,950 --> 00:02:33,500
>> Nú ímynda sér ef þú ákveður að línulegum tíma,

61
00:02:33,500 --> 00:02:36,390
O (n), var bara ekki nógu hratt fyrir þig?

62
00:02:36,390 --> 00:02:38,750
Kannski þú ert að geyma mikla strengi,

63
00:02:38,750 --> 00:02:40,450
og þú getur ekki efni á auka tíma það myndi taka

64
00:02:40,450 --> 00:02:44,000
að fara yfir allar persónur þeirra telja einn-við-mann.

65
00:02:44,000 --> 00:02:46,650
Svo þú ákveður að prófa eitthvað nýtt.

66
00:02:46,650 --> 00:02:49,270
Hvað ef þú myndir koma þegar geyma fjölda stafa

67
00:02:49,270 --> 00:02:52,690
á band, segja, í breytu sem heitir "Len, '

68
00:02:52,690 --> 00:02:54,210
snemma á í áætluninni,

69
00:02:54,210 --> 00:02:57,800
áður en þú settir jafnvel mjög fyrsta staf í streng þinn?

70
00:02:57,800 --> 00:02:59,980
Þá, allt sem þú vilt þurfa að gera núna til að finna út the band lengd,

71
00:02:59,980 --> 00:03:02,570
er að athuga hvað gildi breytunnar er.

72
00:03:02,570 --> 00:03:05,530
Þú vilt ekki að líta á band sig á öllu,

73
00:03:05,530 --> 00:03:08,160
og aðgang að gildi breytu eins og Len er talið

74
00:03:08,160 --> 00:03:11,100
að aðfellu stöðug skipti aðgerð,

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

76
00:03:13,070 --> 00:03:17,110
Hvers vegna er þetta? Jæja, muna hvað asymptotic flókið þýðir.

77
00:03:17,110 --> 00:03:19,100
Hvernig virkar afturkreistingur breyting sem stærð

78
00:03:19,100 --> 00:03:21,400
inntak þitt vex?

79
00:03:21,400 --> 00:03:24,630
>> Segjum að þú varst að reyna að fá fjölda stafa í stærri band.

80
00:03:24,630 --> 00:03:26,960
Jæja, myndi það ekki máli hversu stór þú gera band,

81
00:03:26,960 --> 00:03:28,690
jafnvel milljón stafir að lengd,

82
00:03:28,690 --> 00:03:31,150
allt sem þú vilt þurfa að gera er að finna lengd strengur er með þessari aðferð,

83
00:03:31,150 --> 00:03:33,790
er að lesa út gildi breytu Len,

84
00:03:33,790 --> 00:03:35,440
sem þú gerðir þegar.

85
00:03:35,440 --> 00:03:38,200
Inntak lengd, sem er lengd strengsins sem þú ert að reyna að finna,

86
00:03:38,200 --> 00:03:41,510
hefur ekki áhrif á öll hversu hratt program keyrir.

87
00:03:41,510 --> 00:03:44,550
Þessi hluti program myndi hlaupa jafn hratt á einn staf band

88
00:03:44,550 --> 00:03:46,170
og þúsund-eðli band,

89
00:03:46,170 --> 00:03:49,140
og það er hvers vegna þetta forrit væri vísað til eins og að keyra á stöðugum tíma

90
00:03:49,140 --> 00:03:51,520
varðar inntak stærð.

91
00:03:51,520 --> 00:03:53,920
>> Auðvitað, það er galli.

92
00:03:53,920 --> 00:03:55,710
Þú eyðir auka minni í tölvunni þinni

93
00:03:55,710 --> 00:03:57,380
geyma breytu

94
00:03:57,380 --> 00:03:59,270
og auka tíma sem það tekur

95
00:03:59,270 --> 00:04:01,490
að gera í raun geymsla breytu,

96
00:04:01,490 --> 00:04:03,390
en punkturinn stendur enn,

97
00:04:03,390 --> 00:04:05,060
finna út hversu lengi strengurinn þinn var

98
00:04:05,060 --> 00:04:07,600
ekki treysta á lengd strengsins yfirleitt.

99
00:04:07,600 --> 00:04:10,720
Svo keyrir það á O (1) eða stöðugum tíma.

100
00:04:10,720 --> 00:04:13,070
Þetta vissulega er ekki að meina

101
00:04:13,070 --> 00:04:15,610
að kóðinn keyrir í 1 skrefi,

102
00:04:15,610 --> 00:04:17,470
en það er sama hversu mörg skref það er,

103
00:04:17,470 --> 00:04:20,019
Ef það breytist ekki með stærð á aðföngum,

104
00:04:20,019 --> 00:04:23,420
það er samt aðfellu fasti sem við tákna sem O (1).

105
00:04:23,420 --> 00:04:25,120
>> Eins og þú geta sennilega giska,

106
00:04:25,120 --> 00:04:27,940
það eru margar mismunandi stór O runtimes að mæla reiknirit með.

107
00:04:27,940 --> 00:04:32,980
O (n) ² reiknirit eru aðfellu hægari en O (n) reiknirit.

108
00:04:32,980 --> 00:04:35,910
Það er, eins og fjölda staka (N) vex,

109
00:04:35,910 --> 00:04:39,280
loksins O (n) ² reiknirit mun taka lengri tíma

110
00:04:39,280 --> 00:04:41,000
en O (n) reiknirit til að keyra.

111
00:04:41,000 --> 00:04:43,960
Þetta þýðir ekki O (n) reiknirit alltaf hlaupa hraðar

112
00:04:43,960 --> 00:04:46,410
en O (n) ² reiknirit, jafnvel í sama umhverfi,

113
00:04:46,410 --> 00:04:48,080
á sama vélbúnaði.

114
00:04:48,080 --> 00:04:50,180
Kannski fyrir litlum stærðum inntak,

115
00:04:50,180 --> 00:04:52,900
 O (n) ² reiknirit gæti raunverulega vinna hraðar,

116
00:04:52,900 --> 00:04:55,450
En að lokum, eins og inntak stærð eykst

117
00:04:55,450 --> 00:04:58,760
að óendanlegu er O (n) ² Reiknirit á afturkreistingur

118
00:04:58,760 --> 00:05:02,000
mun að lokum myrkvi afturkreistingur á O (n) reiknirit.

119
00:05:02,000 --> 00:05:04,230
Rétt eins og allir stigs stærðfræðilega aðgerð

120
00:05:04,230 --> 00:05:06,510
 mun að lokum ná öllum línulegt fall,

121
00:05:06,510 --> 00:05:09,200
sama hversu mikið forskot á línulegt fall byrjar með.

122
00:05:10,010 --> 00:05:12,000
Ef þú ert að vinna með miklu magni af gögnum,

123
00:05:12,000 --> 00:05:15,510
reiknirit sem keyra á O (n) ² tími getur raunverulega endað hægja niður program,

124
00:05:15,510 --> 00:05:17,770
en litlum stærðum inntak,

125
00:05:17,770 --> 00:05:19,420
þú verður að öllum líkindum ekki einu sinni eftir.

126
00:05:19,420 --> 00:05:21,280
>> Annar asymptotic flókið er,

127
00:05:21,280 --> 00:05:24,420
lógaritmískum tíma, O (log n).

128
00:05:24,420 --> 00:05:26,340
Dæmi um reiknirit sem keyrir þetta fljótt

129
00:05:26,340 --> 00:05:29,060
er klassískt tvöfaldur leit reiknirit,

130
00:05:29,060 --> 00:05:31,850
að finna stak í þegar-raðaða lista af þáttum.

131
00:05:31,850 --> 00:05:33,400
>> Ef þú veist ekki hvað tvöfaldur leit hefur,

132
00:05:33,400 --> 00:05:35,170
Ég skal útskýra það fyrir þér mjög fljótt.

133
00:05:35,170 --> 00:05:37,020
Segjum að þú ert að leita að númer 3

134
00:05:37,020 --> 00:05:40,200
í þessum fjölda heiltalna.

135
00:05:40,200 --> 00:05:42,140
Það lítur á miðju þáttur í fylkinu

136
00:05:42,140 --> 00:05:46,830
og spyr, "Er þáttur sem ég vil meira en, jafnt eða minna en þetta?"

137
00:05:46,830 --> 00:05:49,150
Ef það er jafnt, þá frábært. Þú fannst þáttur, og þú ert búinn.

138
00:05:49,150 --> 00:05:51,300
Ef það er meiri, þá þú veist þáttur

139
00:05:51,300 --> 00:05:53,440
þarf að vera í hægra megin í fylkinu,

140
00:05:53,440 --> 00:05:55,200
og þú getur aðeins að líta á það í framtíðinni,

141
00:05:55,200 --> 00:05:57,690
og ef það er minna, þá þú veist það er að vera í vinstri hlið.

142
00:05:57,690 --> 00:06:00,980
Þetta ferli er síðan endurtekið með minni-stærð fylkisins

143
00:06:00,980 --> 00:06:02,870
þar til rétt frumefni er að finna.

144
00:06:08,080 --> 00:06:11,670
>> Þetta öflugur reiknirit sker array stærð í helming með hverri aðgerð.

145
00:06:11,670 --> 00:06:14,080
Svo, til að finna stak í raðaða fjölbreytta stærð 8,

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

147
00:06:16,170 --> 00:06:18,450
eða 3 af þessum aðgerðum,

148
00:06:18,450 --> 00:06:22,260
stöðva miðju frumefni, þá skera í array í tvennt verður krafist,

149
00:06:22,260 --> 00:06:25,670
en fylki af stærð 16 fer (log ₂ 16),

150
00:06:25,670 --> 00:06:27,480
eða 4 aðgerðir.

151
00:06:27,480 --> 00:06:30,570
Það er bara 1 fleiri rekstur fyrir tvöfaldast-stærð fylkisins.

152
00:06:30,570 --> 00:06:32,220
Tvöföldun á stærð fylkisins

153
00:06:32,220 --> 00:06:35,160
eykur afturkreistingur aðeins 1 klumpur af þessum kóða.

154
00:06:35,160 --> 00:06:37,770
Aftur, að haka við miðju þáttur í listanum, þá skipta.

155
00:06:37,770 --> 00:06:40,440
Svo er sagt, að starfa í lógaritmískum tíma,

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

157
00:06:42,440 --> 00:06:44,270
En bíddu, þú segir,

158
00:06:44,270 --> 00:06:47,510
er þetta ekki háð því hvar á listanum þátturinn sem þú ert að leita að er?

159
00:06:47,510 --> 00:06:50,090
Hvað ef fyrsta þáttur sem þú horfir á verður að vera réttur?

160
00:06:50,090 --> 00:06:52,040
Þá tekur það aðeins 1 aðgerð,

161
00:06:52,040 --> 00:06:54,310
sama hversu stór listinn er.

162
00:06:54,310 --> 00:06:56,310
>> Jæja, það er hvers vegna tölva vísindamenn hafa fleiri orð

163
00:06:56,310 --> 00:06:58,770
fyrir asymptotic flókið sem endurspegla bestu-málið

164
00:06:58,770 --> 00:07:01,050
og versta sýningar um reiknirit.

165
00:07:01,050 --> 00:07:03,320
Fleiri almennilega, efri og neðri mörk

166
00:07:03,320 --> 00:07:05,090
á afturkreistingur.

167
00:07:05,090 --> 00:07:07,660
Í besta tilfelli fyrir leit tvöfaldur, þáttur okkar er

168
00:07:07,660 --> 00:07:09,330
rétt þar í miðju,

169
00:07:09,330 --> 00:07:11,770
og þú færð það í föstu tíma,

170
00:07:11,770 --> 00:07:14,240
sama hversu stór restin af fylki.

171
00:07:15,360 --> 00:07:17,650
Táknið er notað fyrir þetta er Ω.

172
00:07:17,650 --> 00:07:19,930
Svo, þetta reiknirit er sagt að hlaupa í Ω (1).

173
00:07:19,930 --> 00:07:21,990
Í besta falli, finnur það hluti fljótt,

174
00:07:21,990 --> 00:07:24,200
sama hversu stór fylki er,

175
00:07:24,200 --> 00:07:26,050
en í versta tilfelli,

176
00:07:26,050 --> 00:07:28,690
það hefur til að framkvæma (log n) Split eftirlit

177
00:07:28,690 --> 00:07:31,030
í fylki til að finna rétta hluti.

178
00:07:31,030 --> 00:07:34,270
Versta efri mörk eru nefnd með stóru "O" sem þú veist nú þegar.

179
00:07:34,270 --> 00:07:38,080
Svo er það O (log n), en Ω (1).

180
00:07:38,080 --> 00:07:40,680
>> A línuleg leita hins,

181
00:07:40,680 --> 00:07:43,220
þar sem þú gengur í gegnum hvert frumefni í fylkinu

182
00:07:43,220 --> 00:07:45,170
til að finna það sem þú vilt,

183
00:07:45,170 --> 00:07:47,420
er í besta Ω (1).

184
00:07:47,420 --> 00:07:49,430
Again, the fyrstur þáttur sem þú vilt.

185
00:07:49,430 --> 00:07:51,930
Svo það skiptir ekki máli hversu stór fylki er.

186
00:07:51,930 --> 00:07:54,840
Í versta tilfelli, það síðasta þáttur í fylki.

187
00:07:54,840 --> 00:07:58,560
Svo, þú ert að ganga í gegnum allar n þætti í fylki til að finna það,

188
00:07:58,560 --> 00:08:02,170
eins og ef þú varst að leita að 3.

189
00:08:04,320 --> 00:08:06,030
Svo keyrir það á O (n) tíma

190
00:08:06,030 --> 00:08:09,330
því það er í réttu hlutfalli við fjölda staka í fylki.

191
00:08:10,800 --> 00:08:12,830
>> Einn fleiri tákn sem notuð er Θ.

192
00:08:12,830 --> 00:08:15,820
Þetta má nota til að lýsa reiknirit þar sem bestu og verstu tilfellum

193
00:08:15,820 --> 00:08:17,440
eru þau sömu.

194
00:08:17,440 --> 00:08:20,390
Þetta er raunin í band lengd reiknirit við ræddum um áðan.

195
00:08:20,390 --> 00:08:22,780
Það er, ef við geyma það í breytu fyrir

196
00:08:22,780 --> 00:08:25,160
geymum strenginn og opna það seinna í stöðugri tíma.

197
00:08:25,160 --> 00:08:27,920
Sama hvaða tala

198
00:08:27,920 --> 00:08:30,130
við erum að geyma í því breyta, verðum við að líta á það.

199
00:08:33,110 --> 00:08:35,110
Besta tilfelli er, horfum við á það

200
00:08:35,110 --> 00:08:37,120
og finna lengd strengsins.

201
00:08:37,120 --> 00:08:39,799
Svo Ω (1) eða best ef stöðug skipti.

202
00:08:39,799 --> 00:08:41,059
Versta tilfelli er

203
00:08:41,059 --> 00:08:43,400
við lítum á það og finna lengd strengsins.

204
00:08:43,400 --> 00:08:47,300
Svo, O (1) eða stöðugum tíma í versta tilfelli.

205
00:08:47,300 --> 00:08:49,180
Svo er þar sem besta tilfelli og verstu tilvikum sama,

206
00:08:49,180 --> 00:08:52,520
það er hægt að segja að keyra í Θ (1) tíma.

207
00:08:54,550 --> 00:08:57,010
>> Í stuttu máli, höfum við góðar leiðir til að ástæðu um númerum skilvirkni

208
00:08:57,010 --> 00:09:00,110
án þess að vita neitt um alvöru-heiminum þegar þeir taka til að hlaupa,

209
00:09:00,110 --> 00:09:02,270
sem hefur áhrif á fullt af utanaðkomandi þáttum,

210
00:09:02,270 --> 00:09:04,190
meðal mismunar vélbúnaður, hugbúnaður,

211
00:09:04,190 --> 00:09:06,040
eða sérkenni kóðann þinn.

212
00:09:06,040 --> 00:09:08,380
Einnig gerir það okkur að ástæðu vel um hvað mun gerast

213
00:09:08,380 --> 00:09:10,180
þegar stærð inntak eykst.

214
00:09:10,180 --> 00:09:12,490
>> Ef þú ert að keyra í O (n) ² reiknirit,

215
00:09:12,490 --> 00:09:15,240
eða verr, a O (2 ⁿ) reiknirit,

216
00:09:15,240 --> 00:09:17,170
einn af the festa vaxa tegundir,

217
00:09:17,170 --> 00:09:19,140
þú munt í raun að byrja að taka eftir hægagangur

218
00:09:19,140 --> 00:09:21,220
þegar þú byrjar að vinna með stærri magni af gögnum.

219
00:09:21,220 --> 00:09:23,590
>> Það er asymptotic flókið. Takk.