1
00:00:07,720 --> 00:00:10,950
[Powered by Google Translate] Seguruenik duzu entzun azkar edo eraginkorra algoritmoa buruz hitz

2
00:00:10,950 --> 00:00:13,090
zure ataza jakin exekutatzean,

3
00:00:13,090 --> 00:00:16,110
baina zer esan nahi du algoritmo bat azkar edo eraginkorra izango da?

4
00:00:16,110 --> 00:00:18,580
Beno, ez da denbora errealean neurtzeko bati buruz hitz egiten,

5
00:00:18,580 --> 00:00:20,500
segundotan edo minututan bezala.

6
00:00:20,500 --> 00:00:22,220
Hau da, ordenagailuan hardware delako

7
00:00:22,220 --> 00:00:24,260
eta software erabat aldatu egiten da.

8
00:00:24,260 --> 00:00:26,020
Nire programa zurea baino motelagoa exekutatu dezake,

9
00:00:26,020 --> 00:00:28,000
dut delako exekutatzen zaharrago bat ordenagailuan,

10
00:00:28,000 --> 00:00:30,110
edo gertatuko dudalako online bideo-joko bat jolasten

11
00:00:30,110 --> 00:00:32,670
aldi berean, nire memoria hogging

12
00:00:32,670 --> 00:00:35,400
edo izan liteke nire programa exekutatzen ari dira I software ezberdinen bidez

13
00:00:35,400 --> 00:00:37,550
makina komunikatzen desberdinak maila baxua.

14
00:00:37,550 --> 00:00:39,650
Sagarrak eta laranjak alderatzea bezalakoa da.

15
00:00:39,650 --> 00:00:41,940
Just delako nire motelagoa ordenagailua denbora gehiago behar izaten

16
00:00:41,940 --> 00:00:43,410
atzera baino zurea erantzun bat emateko

17
00:00:43,410 --> 00:00:45,510
ez du esan nahi algoritmoa eraginkorragoa duzu.

18
00:00:45,510 --> 00:00:48,830
>> Beraz, ezin dugu, ez baita zuzenean alderatu programak runtimes

19
00:00:48,830 --> 00:00:50,140
segundo edo minutu

20
00:00:50,140 --> 00:00:52,310
nola egin 2 algoritmo ezberdinak konparatzeko

21
00:00:52,310 --> 00:00:55,030
edozein izanik ere beren hardware edo software ingurumena?

22
00:00:55,030 --> 00:00:58,000
Algoritmikoak eraginkortasuna neurtzeko modu uniforme bat sortzeko,

23
00:00:58,000 --> 00:01:00,360
ordenagailu zientzialari eta matematikariek asmatu dute

24
00:01:00,360 --> 00:01:03,830
programa bat konplexutasuna asymptotic neurtzeko kontzeptuak

25
00:01:03,830 --> 00:01:06,110
eta notazio izeneko 'Big Ohnotation'

26
00:01:06,110 --> 00:01:08,320
hau deskribatzeko.

27
00:01:08,320 --> 00:01:10,820
Formal definizioa da funtzioa f (x)

28
00:01:10,820 --> 00:01:13,390
g (x) ordena exekutatzen

29
00:01:13,390 --> 00:01:15,140
(x) balioa batzuk baldin badago, x ₀ eta

30
00:01:15,140 --> 00:01:17,630
batzuk etengabe, C, eta horrek

31
00:01:17,630 --> 00:01:19,340
f (x) baino txikiagoa edo berdina

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

33
00:01:21,230 --> 00:01:23,190
x guztietan x ₀ baino handiagoa.

34
00:01:23,190 --> 00:01:25,290
>> Baina ez dira beldur urruntzen definizio formala.

35
00:01:25,290 --> 00:01:28,020
Zer esan nahi du benetan gutxiago termino teoriko esan nahi du?

36
00:01:28,020 --> 00:01:30,580
Beno, batez ere da aztertzeko modu bat

37
00:01:30,580 --> 00:01:33,580
programa baten exekuzio nola azkar hazten asymptotically.

38
00:01:33,580 --> 00:01:37,170
Hau da, zure sarrera-tamaina infinitua bidean handitzen

39
00:01:37,170 --> 00:01:41,390
hitza, tamaina 1000 array bat ari zaren ordenatzeko tamaina array bat 10 aldean.

40
00:01:41,390 --> 00:01:44,950
Nola zure programaren exekuzio du hazteko?

41
00:01:44,950 --> 00:01:47,390
Esate baterako, pentsa karaktere kopurua kontatuta

42
00:01:47,390 --> 00:01:49,350
kate batean modurik errazena

43
00:01:49,350 --> 00:01:51,620
 Kate osoa paseoan

44
00:01:51,620 --> 00:01:54,790
gutun-letra eta 1 pertsonaia bakoitzak zenbatzaile bat gehituz.

45
00:01:55,700 --> 00:01:58,420
Algoritmo hori esan denbora lineal

46
00:01:58,420 --> 00:02:00,460
karaktere kopurua dagokionez,

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

48
00:02:02,670 --> 00:02:04,910
Azken finean, bidez O (n).

49
00:02:05,570 --> 00:02:07,290
Zergatik da hau?

50
00:02:07,290 --> 00:02:09,539
Beno, planteamendu hau erabiliz, denbora eskatzen

51
00:02:09,539 --> 00:02:11,300
kate osoa zeharkatuko

52
00:02:11,300 --> 00:02:13,920
karaktere kopurua proportzionala da.

53
00:02:13,920 --> 00:02:16,480
20 karaktereko katea batean karaktere kopurua zenbatzea

54
00:02:16,480 --> 00:02:18,580
birritan denbora hartzen joan

55
00:02:18,580 --> 00:02:20,330
zenbatzeko pertsonaien 10-karaktereko katea batean,

56
00:02:20,330 --> 00:02:23,000
, pertsonaia guztiek begiratu behar duzu duelako

57
00:02:23,000 --> 00:02:25,740
eta pertsonaia bakoitzak denbora kopuru bera begiratzen du.

58
00:02:25,740 --> 00:02:28,050
Karaktere kopurua handitzen den bezala,

59
00:02:28,050 --> 00:02:30,950
exekuzio sarrerako luzera linealki handitu egingo.

60
00:02:30,950 --> 00:02:33,500
>> Orain, pentsa garai hartan lineala erabakitzen bada,

61
00:02:33,500 --> 00:02:36,390
O (n), besterik gabe, ez zen azkar duzu nahikoa?

62
00:02:36,390 --> 00:02:38,750
Agian ari zaren handi kateak gordetzeko,

63
00:02:38,750 --> 00:02:40,450
eta ezin duzu ordaindu aparteko denbora behar luke

64
00:02:40,450 --> 00:02:44,000
bere pertsonaiak bat-banan kontatuta guztiak zeharkatzeko.

65
00:02:44,000 --> 00:02:46,650
Beraz, zerbait desberdinak saiatzeko erabakitzen duzu.

66
00:02:46,650 --> 00:02:49,270
Zer dagoeneko karaktere kopurua gorde gertatuko balitz

67
00:02:49,270 --> 00:02:52,690
katea, esan, 'Len izeneko aldagai batean,'

68
00:02:52,690 --> 00:02:54,210
Programaren hasieran,

69
00:02:54,210 --> 00:02:57,800
nahiz eta zure katea oso pertsonaia lehen gorde aurretik?

70
00:02:57,800 --> 00:02:59,980
Ondoren, denek dute orain, kate-luzera jakiteko nahi duzuna,

71
00:02:59,980 --> 00:03:02,570
zer da aldagaiaren balioa egiaztatu da.

72
00:03:02,570 --> 00:03:05,530
Ez litzateke duzu katea bera guztietan begiratu,

73
00:03:05,530 --> 00:03:08,160
eta aldagai baten balioa sartzeko Len bezala jotzen da

74
00:03:08,160 --> 00:03:11,100
asymptotically konstante bat dute,

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

76
00:03:13,070 --> 00:03:17,110
Zergatik da hau? Beno, gogoratu konplexutasuna asymptotic zer esan nahi du.

77
00:03:17,110 --> 00:03:19,100
Nola tamaina aldaketa exekuzio du

78
00:03:19,100 --> 00:03:21,400
zure input hazten?

79
00:03:21,400 --> 00:03:24,630
>> Esan karaktere kopurua handiagoa katea izan saiatzen ari zaren.

80
00:03:24,630 --> 00:03:26,960
Beno, ez du axola nola handi katea egin duzu,

81
00:03:26,960 --> 00:03:28,690
are gehiago, milioi bat karaktere luze,

82
00:03:28,690 --> 00:03:31,150
Planteamendu honekin katea luzera aurkituko egin nahi duzuna,

83
00:03:31,150 --> 00:03:33,790
aldakorra Len balioa irakurri

84
00:03:33,790 --> 00:03:35,440
horrek dagoeneko.

85
00:03:35,440 --> 00:03:38,200
Sarrerako luzera, hau da, katea luzera aurkitzeko saiatzen ari zaren,

86
00:03:38,200 --> 00:03:41,510
ez nola azkar zure programa exekutatzen eragina.

87
00:03:41,510 --> 00:03:44,550
Programaren zati hau berdin azkar exekutatu litzateke pertsonaia bat-kate bat

88
00:03:44,550 --> 00:03:46,170
eta mila karaktere kate bat,

89
00:03:46,170 --> 00:03:49,140
eta horregatik programa hau izango litzateke, denbora etengabe exekutatzen gisa aipatzen

90
00:03:49,140 --> 00:03:51,520
sarrerako tamaina aldean.

91
00:03:51,520 --> 00:03:53,920
>> Noski, eragozpen bat da.

92
00:03:53,920 --> 00:03:55,710
Aparteko memoria gastatzen duzu zure ordenagailuan

93
00:03:55,710 --> 00:03:57,380
aldagaia gordetzeko

94
00:03:57,380 --> 00:03:59,270
eta denbora gehigarria hartzen du

95
00:03:59,270 --> 00:04:01,490
aldagaiaren benetako biltegiratze egin ahal izateko,

96
00:04:01,490 --> 00:04:03,390
baina puntua dago,

97
00:04:03,390 --> 00:04:05,060
jakiteko zenbat denboraz zure katea izan zen

98
00:04:05,060 --> 00:04:07,600
ez da kate guztietan luzera araberakoa izango da.

99
00:04:07,600 --> 00:04:10,720
Beraz, O (1) edo etengabeko denbora exekutatzen.

100
00:04:10,720 --> 00:04:13,070
Honek, zalantzarik gabe, ez du esan nahi

101
00:04:13,070 --> 00:04:15,610
zure kodea duten 1 urratsean bidez,

102
00:04:15,610 --> 00:04:17,470
baina ez du axola zenbat urrats da,

103
00:04:17,470 --> 00:04:20,019
input tamaina ez bada aldatzen,

104
00:04:20,019 --> 00:04:23,420
oraindik da asymptotically etengabeko O (1).

105
00:04:23,420 --> 00:04:25,120
>> Dezakezu ziurrenik bezala asmatzen,

106
00:04:25,120 --> 00:04:27,940
daude hainbat big O runtimes algoritmoak neurtu ahal izateko.

107
00:04:27,940 --> 00:04:32,980
O (n) ² algoritmoak asymptotically algoritmoak O (n) baino motelagoa.

108
00:04:32,980 --> 00:04:35,910
Hau da, elementu-kopurua (n) hazten da,

109
00:04:35,910 --> 00:04:39,280
O (n) ² algoritmoak azkenean denbora gehiago behar da

110
00:04:39,280 --> 00:04:41,000
O (n) algoritmoak baino exekutatu.

111
00:04:41,000 --> 00:04:43,960
Horrek ez du esan nahi algoritmoak O (n) beti azkarragoa

112
00:04:43,960 --> 00:04:46,410
O (n) ² algoritmoak baino, nahiz eta ingurune berean,

113
00:04:46,410 --> 00:04:48,080
hardware berean.

114
00:04:48,080 --> 00:04:50,180
Agian sarrera txiki tamainak,

115
00:04:50,180 --> 00:04:52,900
 O (n) ² algoritmoa agian benetan lan azkarrago,

116
00:04:52,900 --> 00:04:55,450
baina, azkenean, sarrerako tamaina handitzen

117
00:04:55,450 --> 00:04:58,760
infinitura bidean, O (n) ² algoritmoaren exekuzio

118
00:04:58,760 --> 00:05:02,000
joango Eclipse O (n) algoritmoaren exekuzio.

119
00:05:02,000 --> 00:05:04,230
Just edozein funtzio matematiko quadratic

120
00:05:04,230 --> 00:05:06,510
 joango overtake funtzio lineala,

121
00:05:06,510 --> 00:05:09,200
ez du axola zenbat buru bat hasteko funtzioa lineala hasten.

122
00:05:10,010 --> 00:05:12,000
Ari zaren datu kopuru handiak lan egiten badu,

123
00:05:12,000 --> 00:05:15,510
algoritmoak O en (n) ² denbora benetan, azkenean, zure programa motelduz,

124
00:05:15,510 --> 00:05:17,770
baina sarrera txiki tamainak,

125
00:05:17,770 --> 00:05:19,420
Ziurrenik ere ez konturatu.

126
00:05:19,420 --> 00:05:21,280
>> Asymptotic konplexutasuna Another da,

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

128
00:05:24,420 --> 00:05:26,340
Algoritmo bat doan hau azkar baten adibidea

129
00:05:26,340 --> 00:05:29,060
binary bilaketa algoritmoa klasikoa da,

130
00:05:29,060 --> 00:05:31,850
elementuen zerrenda bat dagoeneko horrela antolatu elementu bat aurkitzeko.

131
00:05:31,850 --> 00:05:33,400
>> Ezagutzen ez baduzu binary bilaketa duenaren,

132
00:05:33,400 --> 00:05:35,170
Azaldu dut benetan azkar.

133
00:05:35,170 --> 00:05:37,020
Demagun kopurua 3 bilatzen ari zaren

134
00:05:37,020 --> 00:05:40,200
zenbaki osoen array honetan.

135
00:05:40,200 --> 00:05:42,140
Array-erdiko elementu itxura

136
00:05:42,140 --> 00:05:46,830
eta galdetzen du, "elementu baino handiagoa nahi dut, eta, berdin, edo hori baino gutxiago?"

137
00:05:46,830 --> 00:05:49,150
Da berdin, ondoren, handia bada. Elementu aurkitu duzu, eta zu egin.

138
00:05:49,150 --> 00:05:51,300
Da handiagoa bada, elementu badakizu

139
00:05:51,300 --> 00:05:53,440
array eskuinaldean,

140
00:05:53,440 --> 00:05:55,200
eta bakarrik dezakezu begiratu etorkizunean,

141
00:05:55,200 --> 00:05:57,690
da eta txikiagoa bada, badakizu ezkerraldean izango du.

142
00:05:57,690 --> 00:06:00,980
Ondoren, prozesu hori txikiagoa-tamaina array errepikatzen

143
00:06:00,980 --> 00:06:02,870
elementu egokia aurkitu arte.

144
00:06:08,080 --> 00:06:11,670
>> Algoritmo horrek indartsu array tamaina moztu eta eragiketa bakoitzaren erdia.

145
00:06:11,670 --> 00:06:14,080
Beraz, tamaina 8 array bat ordenatuko elementu bat aurkitzeko,

146
00:06:14,080 --> 00:06:16,170
gehienez (saioa ₂ 8),

147
00:06:16,170 --> 00:06:18,450
edo 3, eragiketa horiek

148
00:06:18,450 --> 00:06:22,260
erdiko elementua markatuz, ondoren array ebaketa erdi beharko da,

149
00:06:22,260 --> 00:06:25,670
tamaina 16 array bat hartzen du (saioa ₂ 16), berriz,

150
00:06:25,670 --> 00:06:27,480
edo 4 eragiketa.

151
00:06:27,480 --> 00:06:30,570
Hori da 1 baino gehiago bikoiztu-tamaina array eragiketa.

152
00:06:30,570 --> 00:06:32,220
Array-tamaina bikoiztuz

153
00:06:32,220 --> 00:06:35,160
exekuzio-1 bakarrik zatia kode hau handitzen du.

154
00:06:35,160 --> 00:06:37,770
Berriz ere, zerrendako elementu erdiko markatuta, gero splitting.

155
00:06:37,770 --> 00:06:40,440
Beraz, esan duenez, denbora logaritmikoa jarduteko,

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

157
00:06:42,440 --> 00:06:44,270
Baina itxaron, esan duzu,

158
00:06:44,270 --> 00:06:47,510
ez mendekoak dira, non zerrendako elementu bilatzen ari zaren?

159
00:06:47,510 --> 00:06:50,090
Zer gertatzen bada begiratzen duzun lehen elementu eskuineko bat izango?

160
00:06:50,090 --> 00:06:52,040
Ondoren, eragiketa 1 soilik hartzen,

161
00:06:52,040 --> 00:06:54,310
Gaia ez nola big zerrendan.

162
00:06:54,310 --> 00:06:56,310
>> Beno, horregatik, ordenagailu zientzialari termino gehiago dituzte

163
00:06:56,310 --> 00:06:58,770
best-kasuan islatzen konplexutasuna asymptotic

164
00:06:58,770 --> 00:07:01,050
eta txarrena-algoritmo bat kasu emanaldiak ere.

165
00:07:01,050 --> 00:07:03,320
Funtzionatzeko, goiko eta beheko mugetatik

166
00:07:03,320 --> 00:07:05,090
exekuzio gainean.

167
00:07:05,090 --> 00:07:07,660
Binary bilaketa kasuan onena, gure elementu

168
00:07:07,660 --> 00:07:09,330
erdian dago,

169
00:07:09,330 --> 00:07:11,770
eta denbora konstante

170
00:07:11,770 --> 00:07:14,240
ez du axola nola big gainerako array da.

171
00:07:15,360 --> 00:07:17,650
Hau erabiltzen den ikurra Ω da.

172
00:07:17,650 --> 00:07:19,930
Beraz, algoritmo hau esan Ω (1) exekutatu.

173
00:07:19,930 --> 00:07:21,990
Kasu honetan onena, elementu aurkitzen da azkar,

174
00:07:21,990 --> 00:07:24,200
ez du axola nola handi array da,

175
00:07:24,200 --> 00:07:26,050
baina kasu horretan, txarrena,

176
00:07:26,050 --> 00:07:28,690
(log n) egiteko split txekeak du

177
00:07:28,690 --> 00:07:31,030
array eskuineko elementu aurkitu.

178
00:07:31,030 --> 00:07:34,270
Kasurik txarrenaren goiko mugetatik big "O" dagoeneko badakizu aipatzen.

179
00:07:34,270 --> 00:07:38,080
Beraz, O (log n), baina Ω (1) da.

180
00:07:38,080 --> 00:07:40,680
>> Lineal bilaketa bat, aitzitik,

181
00:07:40,680 --> 00:07:43,220
oinez array elementu guztietan bidez

182
00:07:43,220 --> 00:07:45,170
nahi duzun bat aurkitzeko,

183
00:07:45,170 --> 00:07:47,420
Ω onena (1) da.

184
00:07:47,420 --> 00:07:49,430
Berriz ere, lehen elementu nahi duzun.

185
00:07:49,430 --> 00:07:51,930
Beraz, ez du axola nola big array da.

186
00:07:51,930 --> 00:07:54,840
Kasurik okerrenean, array azken elementua da.

187
00:07:54,840 --> 00:07:58,560
Beraz, array elementu guztiak n ibiltzeko aurkituko duzu,

188
00:07:58,560 --> 00:08:02,170
nahi ziren 3 bat bila bazabiltza.

189
00:08:04,320 --> 00:08:06,030
Beraz, O (n) denbora exekutatzen

190
00:08:06,030 --> 00:08:09,330
da array elementu kopuru proportzionala delako.

191
00:08:10,800 --> 00:08:12,830
>> Θ One sinbolo gehiago erabiltzen da.

192
00:08:12,830 --> 00:08:15,820
Algoritmoak non onena eta txarrena kasu deskribatzeko erabil daiteke

193
00:08:15,820 --> 00:08:17,440
berdinak dira.

194
00:08:17,440 --> 00:08:20,390
Kate-luzera algoritmoak buruz hitz egiten dugun kasua da.

195
00:08:20,390 --> 00:08:22,780
Hau da, gorde badugu aldagai batean baino lehen

196
00:08:22,780 --> 00:08:25,160
katea gordetzen dugu, eta sartzeko beranduago, denbora etengabe.

197
00:08:25,160 --> 00:08:27,920
Ez dio axola zer zenbaki

198
00:08:27,920 --> 00:08:30,130
aldagai horretan ari gara gordetzeko, begiratu dugu.

199
00:08:33,110 --> 00:08:35,110
Onena gertatzen da, itxura

200
00:08:35,110 --> 00:08:37,120
eta katearen luzera aurkitu.

201
00:08:37,120 --> 00:08:39,799
Ω (1) edo best-kasuan denbora etengabe, beraz.

202
00:08:39,799 --> 00:08:41,059
Txarrena kasua da,

203
00:08:41,059 --> 00:08:43,400
begiratzen dugu, eta katearen luzera aurkitu.

204
00:08:43,400 --> 00:08:47,300
Beraz, O (1) edo kasu txarrenean etengabeko denbora.

205
00:08:47,300 --> 00:08:49,180
Beraz, kasu onena eta txarrena kasu zenetik berberak dira,

206
00:08:49,180 --> 00:08:52,520
hau esan daiteke Θ (1) denbora exekutatu.

207
00:08:54,550 --> 00:08:57,010
>> Laburbilduz, modu ona daukagu ​​arrazoia buruz kodeak eraginkortasuna

208
00:08:57,010 --> 00:09:00,110
mundu real-time exekutatu dute buruz ezer ezagutu gabe,

209
00:09:00,110 --> 00:09:02,270
den faktore kanpoko asko eragin

210
00:09:02,270 --> 00:09:04,190
desberdinak hardware, software,

211
00:09:04,190 --> 00:09:06,040
edo zure kodea berezitasunak.

212
00:09:06,040 --> 00:09:08,380
Era berean, ondo Arrazoia gurekin zer gertatuko da aukera ematen du

213
00:09:08,380 --> 00:09:10,180
denean input gehikuntza tamaina.

214
00:09:10,180 --> 00:09:12,490
>> O (n) ² algoritmoa exekutatzen ari bada,

215
00:09:12,490 --> 00:09:15,240
edo okerrago, O (2 ⁿ) bildu,

216
00:09:15,240 --> 00:09:17,170
bat geroz azkarrena mota,

217
00:09:17,170 --> 00:09:19,140
benetan, moteltzea nabarituko duzu

218
00:09:19,140 --> 00:09:21,220
datu-kantitate handiagoa duten lanean hasteko.

219
00:09:21,220 --> 00:09:23,590
>> Asymptotic konplexutasuna. Eskerrik asko.