1
00:00:07,720 --> 00:00:10,950
[Powered by Google Translate] Ju ndoshta keni dëgjuar njerëzit flasin rreth një algoritmi të shpejtë apo të efektshme

2
00:00:10,950 --> 00:00:13,090
për ekzekutimin detyrën tuaj të veçantë,

3
00:00:13,090 --> 00:00:16,110
Por çfarë saktësisht do të thotë kjo për një algoritmi të jetë i shpejtë apo të efektshme?

4
00:00:16,110 --> 00:00:18,580
E pra, kjo nuk është duke folur për një matje në kohë reale,

5
00:00:18,580 --> 00:00:20,500
si sekonda ose minuta.

6
00:00:20,500 --> 00:00:22,220
Kjo është për shkak hardware kompjuteri

7
00:00:22,220 --> 00:00:24,260
dhe software të ndryshojnë në mënyrë drastike.

8
00:00:24,260 --> 00:00:26,020
Programi im mund të kandidojë ngadalshëm se sa tuajat,

9
00:00:26,020 --> 00:00:28,000
sepse unë jam running atë në një kompjuter të vjetër,

10
00:00:28,000 --> 00:00:30,110
ose sepse Unë të ndodhë për të luajtur një lojë online video

11
00:00:30,110 --> 00:00:32,670
në të njëjtën kohë, e cila është e hogging gjitha memorie time,

12
00:00:32,670 --> 00:00:35,400
ose unë mund të konkurrojnë programin tim nëpërmjet programeve të ndryshme

13
00:00:35,400 --> 00:00:37,550
e cila komunikon me makinë ndryshe në një nivel të ulët.

14
00:00:37,550 --> 00:00:39,650
Është si krahasuar mollë dhe portokall.

15
00:00:39,650 --> 00:00:41,940
Vetëm për shkak se kompjuteri im merr më e ngadalshme

16
00:00:41,940 --> 00:00:43,410
se juaja për t'i kthyer një përgjigje

17
00:00:43,410 --> 00:00:45,510
nuk do të thotë që ju keni algorithm më efikas.

18
00:00:45,510 --> 00:00:48,830
>> Pra, pasi ne nuk mund të drejtpërdrejt të krahasojnë runtimes e programeve

19
00:00:48,830 --> 00:00:50,140
në sekonda ose minuta,

20
00:00:50,140 --> 00:00:52,310
si nuk kemi krahasojnë 2 algoritme të ndryshme

21
00:00:52,310 --> 00:00:55,030
pavarësisht nga hardware e tyre apo mjedisi software?

22
00:00:55,030 --> 00:00:58,000
Për të krijuar një mënyrë më uniforme për të matur efikasitetin algorithmic,

23
00:00:58,000 --> 00:01:00,360
shkencëtarët kompjuterike dhe matematicienë kanë shpikur

24
00:01:00,360 --> 00:01:03,830
Konceptet për matjen kompleksitetin asymptotic e një programi

25
00:01:03,830 --> 00:01:06,110
dhe një simbol i quajtur 'Ohnotation Big'

26
00:01:06,110 --> 00:01:08,320
për përshkrimin këtë.

27
00:01:08,320 --> 00:01:10,820
Përkufizimi formal është se një funksioni f (x)

28
00:01:10,820 --> 00:01:13,390
shkon në mënyrë të g (x)

29
00:01:13,390 --> 00:01:15,140
nëse ekziston ndonjë vlerë (x), x ₀ dhe

30
00:01:15,140 --> 00:01:17,630
disa konstante, C, për të cilat

31
00:01:17,630 --> 00:01:19,340
f (x) është më pak se ose e barabartë me

32
00:01:19,340 --> 00:01:21,230
që herë konstante g (x)

33
00:01:21,230 --> 00:01:23,190
për të gjitha x madhe se x ₀.

34
00:01:23,190 --> 00:01:25,290
>> Por nuk do të jetë i frikësuar larg nga përkufizimi formal.

35
00:01:25,290 --> 00:01:28,020
Çfarë e bën këtë të vërtetë do të thotë më pak në aspektin teorik?

36
00:01:28,020 --> 00:01:30,580
E pra, kjo është në thelb një mënyrë për të analizuar

37
00:01:30,580 --> 00:01:33,580
sa shpejt Runtime të një programi rritet asymptotically.

38
00:01:33,580 --> 00:01:37,170
Kjo është, si madhësia e inputeve tuaj rritet drejt pafundësi,

39
00:01:37,170 --> 00:01:41,390
Thuaj, ju jeni zgjidhja një rrjet të madhësisë 1000 në krahasim me një grup të madhësisë 10.

40
00:01:41,390 --> 00:01:44,950
Si e runtime e programit tuaj të rriten?

41
00:01:44,950 --> 00:01:47,390
Për shembull, imagjinoni numëruar numrin e karaktereve

42
00:01:47,390 --> 00:01:49,350
në një varg Mënyra më e thjeshtë

43
00:01:49,350 --> 00:01:51,620
 duke ecur nëpër varg të tërë

44
00:01:51,620 --> 00:01:54,790
letër-nga-letër dhe duke shtuar 1 në një sportel për çdo karakter.

45
00:01:55,700 --> 00:01:58,420
Ky algoritëm është thënë për të kandiduar në kohë lineare

46
00:01:58,420 --> 00:02:00,460
në lidhje me numrin e karaktereve,

47
00:02:00,460 --> 00:02:02,670
'N' në vargun.

48
00:02:02,670 --> 00:02:04,910
Me pak fjalë, ajo shkon në O (n).

49
00:02:05,570 --> 00:02:07,290
Pse është kjo?

50
00:02:07,290 --> 00:02:09,539
E pra, duke përdorur këtë qasje, koha e nevojshme

51
00:02:09,539 --> 00:02:11,300
të kaloj nëpër të gjithë tekstin

52
00:02:11,300 --> 00:02:13,920
është proporcionale me numrin e karaktereve.

53
00:02:13,920 --> 00:02:16,480
Numëruar numrin e karaktereve në një varg 20-karakter

54
00:02:16,480 --> 00:02:18,580
do të marrë dy herë për aq kohë sa ajo merr

55
00:02:18,580 --> 00:02:20,330
për të numëruar personazhet në një varg 10-karakter,

56
00:02:20,330 --> 00:02:23,000
sepse ju duhet të shikoni në të gjitha personazhet

57
00:02:23,000 --> 00:02:25,740
dhe çdo karakter merr të njëjtën sasi e kohës për të parë në.

58
00:02:25,740 --> 00:02:28,050
Si ju rritet numri i karaktereve,

59
00:02:28,050 --> 00:02:30,950
runtime e do të rritet linearisht me gjatësi input.

60
00:02:30,950 --> 00:02:33,500
>> Tani, imagjinoni nëse ju vendosni atë kohë lineare,

61
00:02:33,500 --> 00:02:36,390
O (n), thjesht nuk ishte e shpejtë të mjaftueshme për ju?

62
00:02:36,390 --> 00:02:38,750
Ndoshta ju jeni ruajtjen vargje të mëdha,

63
00:02:38,750 --> 00:02:40,450
dhe ju nuk mund të përballojë kohën shtesë që do të marrë

64
00:02:40,450 --> 00:02:44,000
të kaloj nëpër të gjitha karakteret e tyre të numërimit një-nga-një.

65
00:02:44,000 --> 00:02:46,650
Pra, ju vendosni të provoni diçka të ndryshme.

66
00:02:46,650 --> 00:02:49,270
Çfarë ndodh nëse ju do të ndodhte me tashmë të ruajtur numrin e shkronjave

67
00:02:49,270 --> 00:02:52,690
në vargun, të themi, në një ndryshore të quajtur 'len,'

68
00:02:52,690 --> 00:02:54,210
në fillim të programit,

69
00:02:54,210 --> 00:02:57,800
para se të ruajtur edhe karakterin e parë në vargun tuaj?

70
00:02:57,800 --> 00:02:59,980
Pastaj, të gjithë ju do të duhet të bëni tani për të gjetur gjatësinë string,

71
00:02:59,980 --> 00:03:02,570
shikoni se çfarë është vlera e variablit është.

72
00:03:02,570 --> 00:03:05,530
Ju nuk do të duhet të shikoni në vargun e vetë në të gjitha,

73
00:03:05,530 --> 00:03:08,160
dhe qasjen vlerën e një ndryshore si len konsiderohet

74
00:03:08,160 --> 00:03:11,100
një operacion asymptotically konstante kohë,

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

76
00:03:13,070 --> 00:03:17,110
Pse është kjo? E pra, mbani mend se çfarë do të thotë kompleksiteti asymptotic.

77
00:03:17,110 --> 00:03:19,100
Si funksionon ndryshimi runtime si madhësia

78
00:03:19,100 --> 00:03:21,400
Inputet e juaj rritet?

79
00:03:21,400 --> 00:03:24,630
>> Thonë se ju ishin duke u përpjekur për të marrë numrin e karaktereve në një varg të madh.

80
00:03:24,630 --> 00:03:26,960
E pra, kjo nuk do të marrë parasysh sa i madh ju bëni string,

81
00:03:26,960 --> 00:03:28,690
edhe një milion karaktere të gjatë,

82
00:03:28,690 --> 00:03:31,150
të gjithë ju do të duhet të bëni për të gjetur gjatësinë e vargut me këtë qasje,

83
00:03:31,150 --> 00:03:33,790
është për të lexuar vlerën e len ndryshueshme,

84
00:03:33,790 --> 00:03:35,440
që keni bërë tashmë.

85
00:03:35,440 --> 00:03:38,200
Gjatësia input, që është, gjatësia e vargut që ju jeni duke u përpjekur për të gjetur,

86
00:03:38,200 --> 00:03:41,510
nuk ndikon fare se sa shpejt programi juaj shkon.

87
00:03:41,510 --> 00:03:44,550
Kjo pjesë e programit tuaj do të kandidojë në mënyrë të barabartë të shpejtë në një varg një karakter

88
00:03:44,550 --> 00:03:46,170
dhe një mijë karakter string,

89
00:03:46,170 --> 00:03:49,140
dhe kjo është arsyeja pse ky program do t'i referohemi si drejtimin në kohë konstante

90
00:03:49,140 --> 00:03:51,520
në lidhje me madhësinë e input.

91
00:03:51,520 --> 00:03:53,920
>> Sigurisht, ka një pengesë.

92
00:03:53,920 --> 00:03:55,710
Ju shpenzojnë hapësirë ​​shtesë kujtesës në kompjuterin tuaj

93
00:03:55,710 --> 00:03:57,380
ruajtjen e ndryshueshme

94
00:03:57,380 --> 00:03:59,270
dhe koha shtesë ajo ju merr

95
00:03:59,270 --> 00:04:01,490
të bëjë ruajtjen aktuale të ndryshueshme,

96
00:04:01,490 --> 00:04:03,390
por pika ende qëndron,

97
00:04:03,390 --> 00:04:05,060
gjetur se sa kohë string juaj ishte

98
00:04:05,060 --> 00:04:07,600
nuk varet nga gjatësia e vargut në të gjitha.

99
00:04:07,600 --> 00:04:10,720
Kështu, ajo shkon në O (1) ose kohë të vazhdueshëm.

100
00:04:10,720 --> 00:04:13,070
Kjo sigurisht nuk do të duhet të thotë

101
00:04:13,070 --> 00:04:15,610
se kodi juaj shkon në 1 hap,

102
00:04:15,610 --> 00:04:17,470
por pa marrë parasysh se sa hapa është,

103
00:04:17,470 --> 00:04:20,019
në qoftë se ajo nuk ndryshon me madhësinë e inputeve,

104
00:04:20,019 --> 00:04:23,420
ajo është ende asymptotically konstante e cila ne përfaqësojnë si O (1).

105
00:04:23,420 --> 00:04:25,120
>> Si ju mund ndoshta me mend,

106
00:04:25,120 --> 00:04:27,940
ka shumë runtimes ndryshme Big O për të matur me algoritme.

107
00:04:27,940 --> 00:04:32,980
O (n) ² algoritme janë asymptotically ngadalshme se O (n) algoritme.

108
00:04:32,980 --> 00:04:35,910
Kjo është, si numri i elementeve (n) rritet,

109
00:04:35,910 --> 00:04:39,280
përfundimisht O (n) ² algoritme do të marrë më shumë kohë

110
00:04:39,280 --> 00:04:41,000
se O (n) algoritme për të kandiduar.

111
00:04:41,000 --> 00:04:43,960
Kjo nuk do të thotë O (n) algoritme gjithmonë kandidojë më të shpejtë

112
00:04:43,960 --> 00:04:46,410
se O (n) ² algoritme, madje edhe në të njëjtin mjedis,

113
00:04:46,410 --> 00:04:48,080
në të njëjtën hardware.

114
00:04:48,080 --> 00:04:50,180
Ndoshta për të madhësive të vogla të dhëna,

115
00:04:50,180 --> 00:04:52,900
 O (n) ² algorithm mund të vërtetë punojnë më shpejt,

116
00:04:52,900 --> 00:04:55,450
por, përfundimisht, si madhësia input rrit

117
00:04:55,450 --> 00:04:58,760
drejt pafundësisë, të (n) Kohezgjatja O ² algoritmin e

118
00:04:58,760 --> 00:05:02,000
përfundimisht do të eklipsonte Runtime të algorithm (n) O.

119
00:05:02,000 --> 00:05:04,230
Ashtu si çdo funksion kuadratik matematikore

120
00:05:04,230 --> 00:05:06,510
 përfundimisht do të arrij ndonjë funksion linear,

121
00:05:06,510 --> 00:05:09,200
pa marrë parasysh se sa e një kokë të fillojë funksionin linear fillon me.

122
00:05:10,010 --> 00:05:12,000
Nëse ju jeni duke punuar me sasi të mëdha të të dhënave,

123
00:05:12,000 --> 00:05:15,510
algoritme që të kandidojë në O (n) ² kohë mund të vërtetë të përfundojë ngadalësuar programin tuaj,

124
00:05:15,510 --> 00:05:17,770
por për të madhësive të vogla të dhëna,

125
00:05:17,770 --> 00:05:19,420
ju ndoshta nuk do të vini re.

126
00:05:19,420 --> 00:05:21,280
>> Një tjetër kompleksiteti asymptotic është,

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

128
00:05:24,420 --> 00:05:26,340
Një shembull i një algoritmi që drejton këtë shpejt

129
00:05:26,340 --> 00:05:29,060
është klasik kërkimit binar algorithm,

130
00:05:29,060 --> 00:05:31,850
për të gjetur një element në një listë të renditura tashmë të elementeve.

131
00:05:31,850 --> 00:05:33,400
>> Nëse ju nuk e dini se çfarë kërkoni binar bën,

132
00:05:33,400 --> 00:05:35,170
Unë do të shpjegojë atë për ju me të vërtetë shpejt.

133
00:05:35,170 --> 00:05:37,020
Le të thonë se ju jeni duke kërkuar për numrin 3

134
00:05:37,020 --> 00:05:40,200
në këtë grup e integers.

135
00:05:40,200 --> 00:05:42,140
Ajo duket në elementin e mesme e grup

136
00:05:42,140 --> 00:05:46,830
dhe pyet, "A është elementi më i madh se unë dua, e barabartë me ose më pak se kjo?"

137
00:05:46,830 --> 00:05:49,150
Nëse është e barabartë, atëherë e madhe. Keni gjetur elementin, dhe ju jeni bërë.

138
00:05:49,150 --> 00:05:51,300
Në qoftë se kjo është më e madhe, atëherë ju e dini elementin

139
00:05:51,300 --> 00:05:53,440
ka të jetë në anën e duhur e vektorit,

140
00:05:53,440 --> 00:05:55,200
dhe ju mund të shikoni në atë në të ardhmen,

141
00:05:55,200 --> 00:05:57,690
dhe në qoftë se është e vogël, atëherë ju e dini se ajo duhet të jetë në anën e majtë.

142
00:05:57,690 --> 00:06:00,980
Ky proces është përsëritur më pas me grup të vogël të madhësisë

143
00:06:00,980 --> 00:06:02,870
derisa elementi saktë është gjetur.

144
00:06:08,080 --> 00:06:11,670
>> Kjo algorithm fuqishme shkurtime madhësinë e vektorit në gjysmën e me çdo operacion.

145
00:06:11,670 --> 00:06:14,080
Pra, për të gjetur një element në një grup të renditura të madhësisë 8,

146
00:06:14,080 --> 00:06:16,170
më së shumti (hyni ₂ 8),

147
00:06:16,170 --> 00:06:18,450
ose 3 prej këtyre operacioneve,

148
00:06:18,450 --> 00:06:22,260
kontrolluar elementin e mesme, pastaj prerja array në gjysmën do të jetë e nevojshme,

149
00:06:22,260 --> 00:06:25,670
ndërsa një grup i madhësisë 16 merr (hyni ₂ 16),

150
00:06:25,670 --> 00:06:27,480
ose 4 operacione.

151
00:06:27,480 --> 00:06:30,570
Kjo është vetëm 1 operacion më shumë për një grup të dyfishuar në madhësi.

152
00:06:30,570 --> 00:06:32,220
Dyfishuar madhësinë e vektorit

153
00:06:32,220 --> 00:06:35,160
rrit Runtime vetëm nga 1 copë të këtij kodi.

154
00:06:35,160 --> 00:06:37,770
Përsëri, duke kontrolluar elementin e mesme të listës, atëherë ndarjen.

155
00:06:37,770 --> 00:06:40,440
Pra, ai tha se për të vepruar në kohë logaritmike,

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

157
00:06:42,440 --> 00:06:44,270
Por prisni, ju thoni,

158
00:06:44,270 --> 00:06:47,510
kjo nuk varet nga ku në listë elementi që ju jeni duke kërkuar për të është?

159
00:06:47,510 --> 00:06:50,090
Çfarë ndodh nëse elementi i parë që ju shikoni në ndodh të jetë një e drejtë?

160
00:06:50,090 --> 00:06:52,040
Pastaj, ajo merr vetëm 1 operacion,

161
00:06:52,040 --> 00:06:54,310
pa marrë parasysh sa e madhe është lista.

162
00:06:54,310 --> 00:06:56,310
>> E pra, kjo është arsyeja pse shkencëtarët kompjuter kanë kushtet më të

163
00:06:56,310 --> 00:06:58,770
për kompleksitetin asymptotic që reflektojnë më të mirë rast

164
00:06:58,770 --> 00:07:01,050
dhe më të keq rasti shfaqje të një algoritmi.

165
00:07:01,050 --> 00:07:03,320
Më siç duhet, kufijtë e sipërme dhe të poshtme

166
00:07:03,320 --> 00:07:05,090
në runtime.

167
00:07:05,090 --> 00:07:07,660
Në rastin më të mirë për kërkimin binar, elementi ynë është

168
00:07:07,660 --> 00:07:09,330
ka të drejtë në mes,

169
00:07:09,330 --> 00:07:11,770
dhe ju të merrni atë në kohë të vazhdueshme,

170
00:07:11,770 --> 00:07:14,240
pa marrë parasysh sa i madh pjesa tjetër e array është.

171
00:07:15,360 --> 00:07:17,650
Simboli i përdorur për këtë është Ω.

172
00:07:17,650 --> 00:07:19,930
Kështu, kjo algoritmi është thënë të drejtuar në Ω (1).

173
00:07:19,930 --> 00:07:21,990
Në rastin më të mirë, ai e gjen elementin shpejt,

174
00:07:21,990 --> 00:07:24,200
pa marrë parasysh sa i madh array është,

175
00:07:24,200 --> 00:07:26,050
por në rastin më të keq,

176
00:07:26,050 --> 00:07:28,690
ajo ka për të kryer (log n) kontrolle ndarë

177
00:07:28,690 --> 00:07:31,030
e array për të gjetur elementin e duhur.

178
00:07:31,030 --> 00:07:34,270
Kufijtë më të keq rastin e sipërme janë të referuara me "O" e madhe që ju tashmë e dini.

179
00:07:34,270 --> 00:07:38,080
Kështu, ajo është O (log n), por Ω (1).

180
00:07:38,080 --> 00:07:40,680
>> Një kërkim linear, nga ana tjetër,

181
00:07:40,680 --> 00:07:43,220
në të cilën ju ecni nëpër çdo element i vektorit

182
00:07:43,220 --> 00:07:45,170
për të gjetur një që ju dëshironi,

183
00:07:45,170 --> 00:07:47,420
është në Ω mirë (1).

184
00:07:47,420 --> 00:07:49,430
Përsëri, elementi i parë që ju dëshironi.

185
00:07:49,430 --> 00:07:51,930
Pra, kjo nuk ka rëndësi se sa i madh është array.

186
00:07:51,930 --> 00:07:54,840
Në rastin më të keq, kjo është elementi i fundit në grup.

187
00:07:54,840 --> 00:07:58,560
Pra, ju duhet të ecin nëpër të gjitha elementet n në rrjet për të gjetur atë,

188
00:07:58,560 --> 00:08:02,170
si në qoftë se ju jeni duke kërkuar për një 3.

189
00:08:04,320 --> 00:08:06,030
Pra, ajo shkon në kohë O (n)

190
00:08:06,030 --> 00:08:09,330
sepse kjo është në proporcion me numrin e elementeve në array.

191
00:08:10,800 --> 00:08:12,830
>> Një simbol më të përdorur është Θ.

192
00:08:12,830 --> 00:08:15,820
Kjo mund të përdoret për të përshkruar algoritme ku rastet më të mira dhe më të keq

193
00:08:15,820 --> 00:08:17,440
janë të njëjta.

194
00:08:17,440 --> 00:08:20,390
Ky është rasti në string-gjatësi algoritme kemi folur më herët.

195
00:08:20,390 --> 00:08:22,780
Kjo është, në qoftë se ne të ruajtur atë në një variabël para

196
00:08:22,780 --> 00:08:25,160
ne dyqan të vargut dhe të hyni në atë më vonë në kohë konstante.

197
00:08:25,160 --> 00:08:27,920
Pa marrë parasysh se çfarë numri

198
00:08:27,920 --> 00:08:30,130
ne jemi ruajtjen në atë variabël, ne do të duhet të shikojmë në të.

199
00:08:33,110 --> 00:08:35,110
Rasti më i mirë është, ne e shohim atë

200
00:08:35,110 --> 00:08:37,120
dhe për të gjetur gjatësinë e vargut.

201
00:08:37,120 --> 00:08:39,799
Kështu Ω (1) ose më të mirë-rast koha konstante.

202
00:08:39,799 --> 00:08:41,059
Rasti më i keq është,

203
00:08:41,059 --> 00:08:43,400
ne shikojmë në atë dhe për të gjetur gjatësinë e vargut.

204
00:08:43,400 --> 00:08:47,300
Kështu, O (1) ose koha konstante në rastin keq.

205
00:08:47,300 --> 00:08:49,180
Pra, pasi rastin më të mirë dhe rastet më të këqija janë të njëjta,

206
00:08:49,180 --> 00:08:52,520
kjo mund të tha te drejtuar në Θ kohë (1).

207
00:08:54,550 --> 00:08:57,010
>> Në përmbledhje, ne kemi mënyra të mira për të arsyes rreth efikasitetit kodet

208
00:08:57,010 --> 00:09:00,110
pa e ditur asgjë në lidhje me kohën reale botë që ata marrin për të kandiduar,

209
00:09:00,110 --> 00:09:02,270
e cila është prekur nga shumë faktorë jashtë,

210
00:09:02,270 --> 00:09:04,190
përfshirë hardware të ndryshme, software,

211
00:09:04,190 --> 00:09:06,040
ose specifikat e kodit tuaj.

212
00:09:06,040 --> 00:09:08,380
Gjithashtu, ajo na lejon për arsye të mirë për atë që do të ndodhë

213
00:09:08,380 --> 00:09:10,180
kur madhësia e rrit inputeve.

214
00:09:10,180 --> 00:09:12,490
>> Nëse ju jeni drejtimin në O (n) algorithm ²,

215
00:09:12,490 --> 00:09:15,240
ose më keq, një O (2 ⁿ) algoritmi,

216
00:09:15,240 --> 00:09:17,170
një nga llojet më të shpejtë në rritje,

217
00:09:17,170 --> 00:09:19,140
ju do të vërtetë të fillojë të vërehet ngadalësim

218
00:09:19,140 --> 00:09:21,220
kur ju filloni duke punuar me sasi të mëdha të të dhënave.

219
00:09:21,220 --> 00:09:23,590
>> Kjo është kompleksiteti asymptotic. Faleminderit.