1
00:00:00,000 --> 00:00:05,830

2
00:00:05,830 --> 00:00:07,910
>> Ondo da, beraz, konplexutasun konputazionala.

3
00:00:07,910 --> 00:00:10,430
Just abisu bat pixka bat
murgiltze dugu gehiegi far-- aurretik

4
00:00:10,430 --> 00:00:13,070
hau zihurrenik artean izango
gehien matematika-heavy gauzak

5
00:00:13,070 --> 00:00:14,200
CS50 buruz hitz egin dugu.

6
00:00:14,200 --> 00:00:16,950
Zorionez, ez da gehiegi erabatekoa izan
eta saiatu eta gidatuko zaitugu

7
00:00:16,950 --> 00:00:19,200
prozesuan zehar, baina
azoka abisu bat apur bat besterik ez.

8
00:00:19,200 --> 00:00:21,282
Ez da, pixka bat
matematika inplikatutako hemen.

9
00:00:21,282 --> 00:00:23,990
Ondo da, ordenan hain egiteko
gure baliabide konputazional erabilera

10
00:00:23,990 --> 00:00:28,170
benetako world-- in da benetan
algoritmoak ulertzeko garrantzitsua

11
00:00:28,170 --> 00:00:30,750
eta nola datuak prozesatu dute.

12
00:00:30,750 --> 00:00:32,810
Badugu benetan bat
algoritmo eraginkor, dugu

13
00:00:32,810 --> 00:00:36,292
baliabideen zenbatekoa murriztu dezake
horri aurre egiteko, eskuragarri dugu.

14
00:00:36,292 --> 00:00:38,750
Algoritmo bat dugu bada hori
da lan asko hartzen joan

15
00:00:38,750 --> 00:00:41,210
Benetan prozesatu
Datu multzo handia, da

16
00:00:41,210 --> 00:00:44,030
gehiago behar da
eta baliabide gehiago, eta horrek

17
00:00:44,030 --> 00:00:47,980
dirua, RAM, gauza mota hori guztia.

18
00:00:47,980 --> 00:00:52,090
>> Beraz, gai izatea bat aztertzeko
Algoritmo tresna multzo hau erabiliz,

19
00:00:52,090 --> 00:00:56,110
Funtsean, galdetzen du question-- du
Algoritmo eskala, nola ez du

20
00:00:56,110 --> 00:00:59,020
Gero eta gehiago egiten datuen bota dugu?

21
00:00:59,020 --> 00:01:02,220
CS50, datuen kopurua gaude
lan egitea nahiko txikia da.

22
00:01:02,220 --> 00:01:05,140
Oro har, gure programa joan
bigarren edo less-- ere exekutatu

23
00:01:05,140 --> 00:01:07,830
seguruenik askoz gutxiago
batez ere goiz.

24
00:01:07,830 --> 00:01:12,250
>> Baina hori jorratzen duen enpresa bat pentsatzen
bezeroen milioika ehunka.

25
00:01:12,250 --> 00:01:14,970
Eta prozesatu behar dute
bezeroen datu hori.

26
00:01:14,970 --> 00:01:18,260
Bezeroen kopurua ahala
dute handiagoa eta handiagoa lortzen,

27
00:01:18,260 --> 00:01:21,230
nik eskatzen joan
baliabideak gero eta gehiago.

28
00:01:21,230 --> 00:01:22,926
Zenbat gehiago baliabideak?

29
00:01:22,926 --> 00:01:25,050
Beno, hori nola araberakoa
Algoritmoaren aztertuko ditugu,

30
00:01:25,050 --> 00:01:28,097
honetan laukitik tresna erabiliz.

31
00:01:28,097 --> 00:01:31,180
When konplexutasuna buruz hitz egiten dugu
algoritmo baten zenbaitetan dituzu

32
00:01:31,180 --> 00:01:34,040
entzuteko denbora gisa aipatzen da
konplexutasuna edo espazio konplexutasuna

33
00:01:34,040 --> 00:01:36,190
baina besterik ez gara joan
complexity-- deitzeko

34
00:01:36,190 --> 00:01:38,770
oro har ari gara buruz hitz egiten
Kasurik txarrenean du.

35
00:01:38,770 --> 00:01:42,640
Pila txarrena absolutuaren emanda
Datu ditugula litezke bota,

36
00:01:42,640 --> 00:01:46,440
nola da algoritmo hau joan
prozesatu edo datu horiek aurre egiteko?

37
00:01:46,440 --> 00:01:51,450
Oro har, dei egiten diegu kasurik txarrenaren
Algoritmo big-O baten exekuzio.

38
00:01:51,450 --> 00:01:56,770
Beraz, algoritmo bat esan behar ditzake
n edo n O O abian egongo karratu.

39
00:01:56,770 --> 00:01:59,110
Eta zer gehiago
horiek bigarren bat ere esan nahi.

40
00:01:59,110 --> 00:02:01,620
>> Batzuetan, ordea, arreta egiten dugu
best-kasuan agertokia buruz.

41
00:02:01,620 --> 00:02:05,400
Datuen guztia bada nahi dugu
eta izango da erabat perfektua izan zen

42
00:02:05,400 --> 00:02:09,630
eta hau ezin hobea bidaltzen ari ginen
Datu multzo gure algoritmoaren bidez.

43
00:02:09,630 --> 00:02:11,470
Nola litzateke kudeatuko du egoera horretan?

44
00:02:11,470 --> 00:02:15,050
Batzuetan erreferentzia dugun bezala
big-Omega, big-O alderatuta beraz,

45
00:02:15,050 --> 00:02:16,530
big-Omega ditugu.

46
00:02:16,530 --> 00:02:18,880
Big-Omega best-kasu eszenatokia da.

47
00:02:18,880 --> 00:02:21,319
Kasurik txarrenean du Big-O.

48
00:02:21,319 --> 00:02:23,860
Oro har, buruz hitz egiten dugu
algoritmo bat konplexutasuna,

49
00:02:23,860 --> 00:02:26,370
dugu buruz hitz egiten ari
Kasurik txarrenean.

50
00:02:26,370 --> 00:02:28,100
Beraz, kontuan izan hori.

51
00:02:28,100 --> 00:02:31,510
>> Eta klase honetan, oro har ari gara joan
du azterketa zorrotza alde batera utzi nahi.

52
00:02:31,510 --> 00:02:35,350
Badira zientziak eta eremuak
Gauza mota hau eskainita.

53
00:02:35,350 --> 00:02:37,610
When arrazoibide buruz hitz egiten dugu
algoritmoen bidez,

54
00:02:37,610 --> 00:02:41,822
bertan egin dugu pieza-ek pieza askorentzat
algoritmoak buruz hitz egiten dugu klasea.

55
00:02:41,822 --> 00:02:44,780
Benetan ari gara buruz hitz egiten
Bidez pensatzen sen,

56
00:02:44,780 --> 00:02:47,070
Ez formulak, edo frogak batera,
edo horrelako zerbait.

57
00:02:47,070 --> 00:02:51,600
Beraz, ez kezkatu, ez gara gai izan
matematika klase handi bat bihurtzen da.

58
00:02:51,600 --> 00:02:55,920
>> Beraz konplexutasuna buruz baino ez dugu esan dut
galderari, nola eskatu dio delako

59
00:02:55,920 --> 00:03:00,160
ez gure algoritmoak kudeatzeko handiago eta
ari haiek bota datuak multzo handiago.

60
00:03:00,160 --> 00:03:01,960
Beno, zer datu multzo bat da?

61
00:03:01,960 --> 00:03:03,910
Zer egin zuen hura esan dut esan nahi dut?

62
00:03:03,910 --> 00:03:07,600
Edozein izanda ere egiten gehienak esan nahi du
Testuinguru zentzurik, egia esateko.

63
00:03:07,600 --> 00:03:11,160
Algoritmo bat, daukagu ​​bada
Prozesuak Strings-- ziurrenik gaude

64
00:03:11,160 --> 00:03:13,440
katea tamaina buruz hitz egiten.

65
00:03:13,440 --> 00:03:15,190
Hori datuen da set--
tamaina, kopurua,

66
00:03:15,190 --> 00:03:17,050
egiteko katea osatzen duten pertsonaien.

67
00:03:17,050 --> 00:03:20,090
Dugu bati buruz hitz egiten ari bada
Algoritmo fitxategiak prozesatzen duen,

68
00:03:20,090 --> 00:03:23,930
dugu nola buruz liteke hizketan
kilobyteko fitxategi hori osatzen.

69
00:03:23,930 --> 00:03:25,710
Eta hori datu-sorta da.

70
00:03:25,710 --> 00:03:28,870
Dugu algoritmo bat buruz hitz egiten bada
Hori arrayak maneiatzen orokorrago,

71
00:03:28,870 --> 00:03:31,510
hala nola algoritmoak bezala
algoritmorikerabiltzen bilatuz,

72
00:03:31,510 --> 00:03:36,690
ziurrenik ari gara zenbaki buruz hitz egiten
array bat osatzen duten elementuen.

73
00:03:36,690 --> 00:03:39,272
>> Orain, bat neurtu ahal izango dugu
algoritmo bereziki,

74
00:03:39,272 --> 00:03:40,980
nuenean, esan dezakegu
algoritmo bat neurtzeko, I

75
00:03:40,980 --> 00:03:43,840
Esan nahi neurtu ahal izango dugu nola
baliabide asko hartzen du.

76
00:03:43,840 --> 00:03:48,990
Baliabide horiek diren ala ez, zenbat
RAM byte edo megabyte RAM

77
00:03:48,990 --> 00:03:49,790
Erabiltzen.

78
00:03:49,790 --> 00:03:52,320
Edo zenbat denbora exekutatu hartzen du.

79
00:03:52,320 --> 00:03:56,200
Eta hau esan genezake
neurtzeko, edonola, n f.

80
00:03:56,200 --> 00:03:59,420
Non n kopurua da
Datu multzo elementu.

81
00:03:59,420 --> 00:04:02,640
Eta n f Somethings zenbat da.

82
00:04:02,640 --> 00:04:07,530
Zenbat baliabide unitateak egiten
Datu hori prozesatu behar da.

83
00:04:07,530 --> 00:04:10,030
>> Orain, egia esan, ez zaintzeko
zer n f da, hain zuzen ere.

84
00:04:10,030 --> 00:04:13,700
Izan ere, oso gutxitan Borondate dugu
Zalantzarik gabe, izango klase dut hau sekula ere

85
00:04:13,700 --> 00:04:18,709
Edozein benetan sakon murgiltzea
zer f n da azterketa.

86
00:04:18,709 --> 00:04:23,510
Besterik ez gara zer f buruz hitz egingo
n, gutxi gorabehera, edo zer joera da.

87
00:04:23,510 --> 00:04:27,600
Algoritmo bat joera da
bere ordena epe altuena aginduei.

88
00:04:27,600 --> 00:04:29,440
Eta zer ikusi ahal izango dugu I
esan nahi hartuz

89
00:04:29,440 --> 00:04:31,910
a Zehatzagoak adibide bat begiratu.

90
00:04:31,910 --> 00:04:34,620
>> Beraz, demagun dugun
hiru algoritmo ezberdinak.

91
00:04:34,620 --> 00:04:39,350
Horietatik lehena hartzen n
Baliabide cubed, unitate batzuk

92
00:04:39,350 --> 00:04:42,880
Datu tamaina n multzo bat lantzeko.

93
00:04:42,880 --> 00:04:47,000
Garamatzan bigarren bildu bat daukagu
n cubed plus n karratu baliabideak

94
00:04:47,000 --> 00:04:49,350
Datu tamaina n multzo bat lantzeko.

95
00:04:49,350 --> 00:04:52,030
Eta hirugarren bat dugu
Hori dela in-- exekutatzen algoritmo

96
00:04:52,030 --> 00:04:58,300
hartzen n cubed ken 8n karratu
Baliabide plus 20 n unitateak

97
00:04:58,300 --> 00:05:02,370
algoritmo bat prozesatu
tamaina n ezarri datuekin.

98
00:05:02,370 --> 00:05:05,594
>> Orain, berriz ere, ez dugu benetan ez dira joan
den xehetasun maila honetan sartu.

99
00:05:05,594 --> 00:05:08,260
Ziur nago besterik ez dute horiek eman
Hemen puntu baten adibide gisa

100
00:05:08,260 --> 00:05:10,176
naiz duten I izango da joan
bigarren bat egiten da, eta horrek

101
00:05:10,176 --> 00:05:12,980
da dugun bakarra benetan axola duten
Gauzak joeraren inguruko

102
00:05:12,980 --> 00:05:14,870
Datu multzo handiagoa lortu zuen.

103
00:05:14,870 --> 00:05:18,220
Beraz, datu multzo txikia da, bada, ez dago
benetan aldea nahiko handia

104
00:05:18,220 --> 00:05:19,870
algoritmo horietan.

105
00:05:19,870 --> 00:05:23,000
Hirugarren Algoritmoa ez
hartzen 13 aldiz gehiago,

106
00:05:23,000 --> 00:05:27,980
Baliabideen zenbatekoa 13 aldiz handiagoa
lehenengoa erlatiboa exekutatu.

107
00:05:27,980 --> 00:05:31,659
>> Gure datu-sorta tamaina 10, badago bertan
handiagoa da, baina ez du zertan oso handia da,

108
00:05:31,659 --> 00:05:33,950
ikusi ahal izango dugu, ez dagoela
Egia esan, diferentzia bat pixka bat.

109
00:05:33,950 --> 00:05:36,620
Hirugarren Algoritmoa
eraginkorragoa bihurtzen.

110
00:05:36,620 --> 00:05:40,120
Egia esan, 40% inguru ditu -
edo% 60 eraginkorragoa.

111
00:05:40,120 --> 00:05:41,580
% 40 zenbat denbora behar izaten ditu.

112
00:05:41,580 --> 00:05:45,250
Run daiteke hartu ahal izango du
400 baliabideak unitateak

113
00:05:45,250 --> 00:05:47,570
Datu tamaina 10 multzo bat lantzeko.

114
00:05:47,570 --> 00:05:49,410
Lehenengo Kontuan izanik
bildu, aitzitik,

115
00:05:49,410 --> 00:05:54,520
1.000 baliabideak unitateak hartzen
Datu tamaina 10 multzo bat lantzeko.

116
00:05:54,520 --> 00:05:57,240
Baina begira zer gertatzen
Gure zenbakiak are handiagoa lortzeko.

117
00:05:57,240 --> 00:05:59,500
>> Orain, aldea
Algoritmo horien arteko

118
00:05:59,500 --> 00:06:01,420
hasteko apur bat gutxiago agerian gera dadin.

119
00:06:01,420 --> 00:06:04,560
Eta, hain zuzen, ez direla
behe-ordena terms-- edo, hobeto esanda,

120
00:06:04,560 --> 00:06:09,390
txikiagoa exponents-- termino
hasteko garrantzirik bihurtu.

121
00:06:09,390 --> 00:06:12,290
Datu multzo baten tamaina bera bada
1.000 eta lehen bildu

122
00:06:12,290 --> 00:06:14,170
bilioi bat urrats exekutatzen.

123
00:06:14,170 --> 00:06:17,880
Eta bigarren bildu exekutatzen
milioi eta milioi bat urrats.

124
00:06:17,880 --> 00:06:20,870
Eta hirugarren algoritmoa exekutatzen
besterik mila milioi urrats lotsati ere.

125
00:06:20,870 --> 00:06:22,620
It bat milioi urrats nahiko askoz.

126
00:06:22,620 --> 00:06:25,640
Behe-ordena termino horiek hasteko
benetan garrantzirik bihurtu.

127
00:06:25,640 --> 00:06:27,390
Eta besterik gabe, benetan behar
Mailu etxean point-- du

128
00:06:27,390 --> 00:06:31,240
Datu-sarrerarekin tamaina bat baldin bada
million-- guztiak horiek hiru pretty much

129
00:06:31,240 --> 00:06:34,960
quintillion-- bat bada hartu
Nire math correct-- pausoak da

130
00:06:34,960 --> 00:06:37,260
Sarrera datu bat prozesatu
tamaina milioi bat.

131
00:06:37,260 --> 00:06:38,250
Hori urrats asko da.

132
00:06:38,250 --> 00:06:42,092
Eta hain zuzen, horietako bat gerta daiteke
Pare bat 100.000 edo pare bat hartuko 100

133
00:06:42,092 --> 00:06:44,650
milioi are gutxiago
dugu zenbaki bati buruz hitz egiten ari

134
00:06:44,650 --> 00:06:46,990
Hori big-- motatako inolako garrantzirik.

135
00:06:46,990 --> 00:06:50,006
Hartu ohi dute, guztiak
gutxi gorabehera n cubed,

136
00:06:50,006 --> 00:06:52,380
eta, beraz, benetan genuke erreferentzia
algoritmo horiek guztiak

137
00:06:52,380 --> 00:06:59,520
n ordena izateaz gain
cubed edo n cubed of big-O.

138
00:06:59,520 --> 00:07:03,220
>> Hemen gehiago batzuen zerrenda bat da
komun konplexutasun konputazionala klaseak

139
00:07:03,220 --> 00:07:05,820
dugula topo egingo in
algoritmoak, oro har.

140
00:07:05,820 --> 00:07:07,970
Eta, era berean, zehazki, CS50.

141
00:07:07,970 --> 00:07:11,410
Hauek dira agindu
Oro har, goialdean azkarrena,

142
00:07:11,410 --> 00:07:13,940
Oro har, motelena behealdean.

143
00:07:13,940 --> 00:07:16,920
Beraz, denbora etengabe algoritmoak joera
azkarrena izan da, kontuan hartu gabe

144
00:07:16,920 --> 00:07:19,110
tamaina du
Sarrera datu pasatzen duzu.

145
00:07:19,110 --> 00:07:23,760
Beti eragiketa bat hartzen dute, edo
baliabideak unitate bat landu.

146
00:07:23,760 --> 00:07:25,730
Baliteke 2, izango da, agian
izan 3, agian 4, izango da.

147
00:07:25,730 --> 00:07:26,910
Baina kopurua konstante bat da.

148
00:07:26,910 --> 00:07:28,400
Ez du aldatzen dira.

149
00:07:28,400 --> 00:07:31,390
>> Logaritmikoa denbora algoritmoak
zertxobait hobeak dira.

150
00:07:31,390 --> 00:07:33,950
Eta adibide benetan ona
logaritmikoa denbora algoritmoa

151
00:07:33,950 --> 00:07:37,420
duzun bada, ziur aski, dirudienez, orain da
urraketaren telefono liburuaren aparte

152
00:07:37,420 --> 00:07:39,480
Mike Smith aurkitu telefono-liburuan.

153
00:07:39,480 --> 00:07:40,980
Arazoa moztu dugu erditik.

154
00:07:40,980 --> 00:07:43,580
Eta beraz, n lortzen handiago gisa
eta handiago eta larger--

155
00:07:43,580 --> 00:07:47,290
hain zuzen ere, aldi bakoitzean bi
n, bakarrik urrats bat gehiago hartzen du.

156
00:07:47,290 --> 00:07:49,770
Beraz, asko hobeto
baino, esan, denbora lineala.

157
00:07:49,770 --> 00:07:53,030
Zein da bikoiztu n izanez gero,
urratsen kopuru bikoitza hartzen du.

158
00:07:53,030 --> 00:07:55,980
Hirukoiztu duzun n bada, hartzen
hirukoiztu urrats kopurua.

159
00:07:55,980 --> 00:07:58,580
Urrats bat aleko.

160
00:07:58,580 --> 00:08:01,790
>> Gero gauzak more-- apur bat lortzeko
zertxobait gutxiago handia bertatik.

161
00:08:01,790 --> 00:08:06,622
Lineal denbora erritmikoa daukazu, batzuetan
log denbora lineala deitzen edo besterik nn saioa.

162
00:08:06,622 --> 00:08:08,330
Eta adibide bat egingo dugu
algoritmo bat dagoela

163
00:08:08,330 --> 00:08:13,370
n log n, hau da, oraindik hobea eskailerak
quadratic aldia n baino karratu.

164
00:08:13,370 --> 00:08:17,320
Edo polinomio denbora, n bi
Edozein kopurua bi baino handiagoa.

165
00:08:17,320 --> 00:08:20,810
Denbora esponentzialean edo, bertan
are worse-- C n da.

166
00:08:20,810 --> 00:08:24,670
Beraz kopurua konstante batzuk planteatu
sarrera tamaina du boterea.

167
00:08:24,670 --> 00:08:28,990
Beraz, ez da 1,000-- du galtzen
Datuak sartzea size 1.000 da,

168
00:08:28,990 --> 00:08:31,310
C hartuko luke du 1.000 boterera.

169
00:08:31,310 --> 00:08:33,559
Da polinomio denbora asko baino okerrago.

170
00:08:33,559 --> 00:08:35,030
>> Factorial denbora are okerragoa da.

171
00:08:35,030 --> 00:08:37,760
Eta hain zuzen ere, ez dago benetan ez
existitzen denbora infinitua algoritmoak,

172
00:08:37,760 --> 00:08:43,740
besteak beste, orain arte bezala ergelak deiturikoak, gisa zeinen
lana da array bat ausaz nahastuko

173
00:08:43,740 --> 00:08:45,490
eta, ondoren, aztertu
du horrela antolatu ala ez.

174
00:08:45,490 --> 00:08:47,589
Eta ez da, bada, ausaz
berriro nahastu array

175
00:08:47,589 --> 00:08:49,130
eta egiaztatu du horrela antolatu den ikusteko.

176
00:08:49,130 --> 00:08:51,671
Eta zuk ziurrenik imagine-- ahal bezain
egoera bat imajinatu dezakezu

177
00:08:51,671 --> 00:08:55,200
non txarrena kasuan, borondate horren
inoiz benetan sorta batekin hasi.

178
00:08:55,200 --> 00:08:57,150
Algoritmo betiko exekutatu litzateke.

179
00:08:57,150 --> 00:08:59,349
Eta beraz, hori izango litzateke
infinitua denbora algoritmoa.

180
00:08:59,349 --> 00:09:01,890
Zorionez, ezin izango da idazten duzun
edozein faktore edo infinitua denbora

181
00:09:01,890 --> 00:09:04,510
CS50 algoritmoak.

182
00:09:04,510 --> 00:09:09,150
>> Beraz, dezagun pixka bat gehiago
sinpleagorik begirada hormigoia

183
00:09:09,150 --> 00:09:11,154
konputazional konplexutasunaren klaseak.

184
00:09:11,154 --> 00:09:13,070
Beraz, adibide bat dugu
edo bi adibide hemen

185
00:09:13,070 --> 00:09:15,590
denbora konstante algoritmoak,
horrek beti hartu

186
00:09:15,590 --> 00:09:17,980
kasurik txarrenaren eragiketa bakarrean.

187
00:09:17,980 --> 00:09:20,050
Beraz, lehen adibide
funtzio bat dela

188
00:09:20,050 --> 00:09:23,952
4 deitzen duzu, eta horrek
tamaina 1.000 array bat hartzen du.

189
00:09:23,952 --> 00:09:25,660
Baina gero, itxuraz
Ez du benetan itxura

190
00:09:25,660 --> 00:09:29,000
at it ez du benetan axola zer da
horren barruan, array horren.

191
00:09:29,000 --> 00:09:30,820
Beti bakarrik lau itzultzen.

192
00:09:30,820 --> 00:09:32,940
Beraz, algoritmo hori,
dela nahiz

193
00:09:32,940 --> 00:09:35,840
1.000 elementu hartzen ez badu
haiekin ezer egin.

194
00:09:35,840 --> 00:09:36,590
Just lau itzultzen.

195
00:09:36,590 --> 00:09:38,240
Beti da pauso bakar bat.

196
00:09:38,240 --> 00:09:41,600
>> Izan ere, gehitu 2 nums-- bertan
Nik bezala well-- aurretik dugu

197
00:09:41,600 --> 00:09:43,680
bi zenbaki osoen prozesuak.

198
00:09:43,680 --> 00:09:44,692
Ez da pauso bakar bat.

199
00:09:44,692 --> 00:09:45,900
Egia esan, pare bat urrats.

200
00:09:45,900 --> 00:09:50,780
Bat lortuko duzu, lortu duzu b, horiek gehitzen duzunean
elkarrekin, eta zuk irteera emaitzekin.

201
00:09:50,780 --> 00:09:53,270
Beraz, 84 pausu da.

202
00:09:53,270 --> 00:09:55,510
Baina etengabeko beti da,
edo b kontuan hartu gabe.

203
00:09:55,510 --> 00:09:59,240
Bat eskuratu ahal izango duzu, b, gehitu
Haiekin batera, emaitza irteera.

204
00:09:59,240 --> 00:10:02,900
Beraz, denbora etengabe algoritmo bat da.

205
00:10:02,900 --> 00:10:05,170
>> Hona hemen adibide bat
denbora lineala algoritmo

206
00:10:05,170 --> 00:10:08,740
garamatzan gets-- algoritmo bat
Urrats bat gehiago, seguru asko,

207
00:10:08,740 --> 00:10:10,740
Zure sarrera 1 eta hazi ahala.

208
00:10:10,740 --> 00:10:14,190
Beraz, demagun bilatzen ari gara
5. zenbakian array baten barnealdea.

209
00:10:14,190 --> 00:10:16,774
Baliteke egoera bat non duzu
nahiko goiz da aurkitu dezakezu.

210
00:10:16,774 --> 00:10:18,606
Baina, era berean, ezin duzu
egoera bat non

211
00:10:18,606 --> 00:10:20,450
array azken elementua izan liteke.

212
00:10:20,450 --> 00:10:23,780
Tamaina 5 array bat, bada ere
5 zenbakia bilatzen ari gara.

213
00:10:23,780 --> 00:10:25,930
5 urrats hartuko luke.

214
00:10:25,930 --> 00:10:29,180
Eta hain zuzen ere, imajinatu ez dagoela da
Ez 5 array honen edozein lekutan.

215
00:10:29,180 --> 00:10:32,820
Oraindik ere, benetan dugu begiratzen
array elementu bakar behin

216
00:10:32,820 --> 00:10:35,550
izateko zehazteko ere
ala ez, 5 dago.

217
00:10:35,550 --> 00:10:39,840
>> Beraz, kasurik txarrenaren, hau da, hori ere
elementua array azken da

218
00:10:39,840 --> 00:10:41,700
edo ez da existitzen.

219
00:10:41,700 --> 00:10:44,690
Oraindik ere begiratzen dugu
n elementu guztiak.

220
00:10:44,690 --> 00:10:47,120
Eta, beraz, algoritmo hau
denbora lineal exekutatzen.

221
00:10:47,120 --> 00:10:50,340
Hori baieztatu dezakezu arabera
Pixka bat estrapolatu esanez,

222
00:10:50,340 --> 00:10:53,080
6-elementu array bat izan badugu eta
5 zenbakia bilatzen ari ginen,

223
00:10:53,080 --> 00:10:54,890
6 urrats iraun dezake.

224
00:10:54,890 --> 00:10:57,620
7-elementu array bat bada, eta
5 zenbakia bilatzen ari gara.

225
00:10:57,620 --> 00:10:59,160
7 urratsetan iraun dezake.

226
00:10:59,160 --> 00:11:02,920
Elementu bat gehiago gehitu nahi dugu gure
array, urrats bat gehiago hartzen du.

227
00:11:02,920 --> 00:11:06,750
Hori algoritmo lineal bat da
Txarrena-kasuan.

228
00:11:06,750 --> 00:11:08,270
>> Bikote galdera azkar duzu.

229
00:11:08,270 --> 00:11:11,170
Zer da runtime-- du zer da
kasurik txarrenaren exekuzio

230
00:11:11,170 --> 00:11:13,700
kode hau bereziki?

231
00:11:13,700 --> 00:11:17,420
Beraz, 4 begizta bat hemen doa daukat
tik j funtzioak 0, m gehienez modu guztiak.

232
00:11:17,420 --> 00:11:21,980
Eta hemen zer ikusten dut, hori da
Begizta gorputza denbora etengabe exekutatzen.

233
00:11:21,980 --> 00:11:24,730
Beraz, hori terminologia erabiliz
dugu dagoeneko hitz egin zer naizenean

234
00:11:24,730 --> 00:11:29,390
kasurik txarrenaren litzateke
Algoritmo honen exekuzio?

235
00:11:29,390 --> 00:11:31,050
Hartu segundo bat.

236
00:11:31,050 --> 00:11:34,270
Barneko begizta zatia
denbora etengabe exekutatzen.

237
00:11:34,270 --> 00:11:37,510
Eta kanpoaldeko zatia
begizta da m aldiz exekutatu behar.

238
00:11:37,510 --> 00:11:40,260
Beraz, zein da kasurik txarrenaren exekuzio hemen?

239
00:11:40,260 --> 00:11:43,210
Ba m-big-O asmatzen duzu?

240
00:11:43,210 --> 00:11:44,686
Eskubidea litzaidake.

241
00:11:44,686 --> 00:11:46,230
>> Nola beste bat buruz?

242
00:11:46,230 --> 00:11:48,590
Oraingo honetan bat egin behar dugu
begizta baten barruan amaitzen da.

243
00:11:48,590 --> 00:11:50,905
Kanpoko begizta bat daukagu
hutsetik p doa.

244
00:11:50,905 --> 00:11:54,630
Eta hori exekutatzen barneko begizta bat daukagu
zerotik p, eta horren barruan,

245
00:11:54,630 --> 00:11:57,890
Dut adierazi gorputzean dela
begizta denbora etengabe exekutatzen.

246
00:11:57,890 --> 00:12:02,330
Beraz, zein da kasurik txarrenaren exekuzio
kode hau bereziki?

247
00:12:02,330 --> 00:12:06,140
Beno, berriz, bat dugu
p aldiz exekutatzen duen kanpoko begizta.

248
00:12:06,140 --> 00:12:09,660
Eta, aldi bakoitzean iterazio
begizta hori, baizik.

249
00:12:09,660 --> 00:12:13,170
Barneko begizta bat daukagu
hori ere p aldiz exekutatzen.

250
00:12:13,170 --> 00:12:16,900
Eta gero, horren barruan, ez da etorri
etengabeko aldia gutxi mozkina ez.

251
00:12:16,900 --> 00:12:19,890
>> Beraz, kanpoko begizta bat behar badugu
p aldiz barruan dagoen huraxe exekutatzen

252
00:12:19,890 --> 00:12:22,880
barneko begizta bat dela
exekutatzen p zer da garaietatik

253
00:12:22,880 --> 00:12:26,480
kasurik txarrenaren exekuzio
kode honen?

254
00:12:26,480 --> 00:12:30,730
Ba or big-O asmatzen duzun karratu?

255
00:12:30,730 --> 00:12:31,690
>> Naiz Doug Lloyd.

256
00:12:31,690 --> 00:12:33,880
Hau CS50 da.

257
00:12:33,880 --> 00:12:35,622