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

2
00:00:05,830 --> 00:00:07,910
>> Bone, do, komputa komplikeco.

3
00:00:07,910 --> 00:00:10,430
Nur iom de averto
antaŭ ni plonĝi en tro far--

4
00:00:10,430 --> 00:00:13,070
tiu verŝajne estos inter
la plej math-multepezaj

5
00:00:13,070 --> 00:00:14,200
ni raportas en CS50.

6
00:00:14,200 --> 00:00:16,950
Espereble ne estos tro superforta
kaj ni provos gvidi vin

7
00:00:16,950 --> 00:00:19,200
tra la procezo, sed
nur iom de justa averto.

8
00:00:19,200 --> 00:00:21,282
Ekzistas iomete
de matematiko implikita tie.

9
00:00:21,282 --> 00:00:23,990
Bone, do por fari
uzo de nia komputa rimedoj

10
00:00:23,990 --> 00:00:28,170
en la reala world-- estas vere
Gravas kompreni algoritmoj

11
00:00:28,170 --> 00:00:30,750
kaj kiel ili procesi datumojn.

12
00:00:30,750 --> 00:00:32,810
Se ni havas vere
kompetenta algoritmo, ni

13
00:00:32,810 --> 00:00:36,292
povas minimumigi la kvanton de resursoj
ni havas disponebla por trakti ĝin.

14
00:00:36,292 --> 00:00:38,750
Se ni havas algoritmon kiu
tuj prenos multan laboron

15
00:00:38,750 --> 00:00:41,210
procesi vere
granda aro de datumoj, ĝi estas

16
00:00:41,210 --> 00:00:44,030
tuj postulos pli
kaj pli da rimedoj, kiuj

17
00:00:44,030 --> 00:00:47,980
estas mono, RAM, ĉiuj tian materialon.

18
00:00:47,980 --> 00:00:52,090
>> Do, povante analizi
algoritmo uzanta tiun ilon aro,

19
00:00:52,090 --> 00:00:56,110
esence, demandas la question--
kiel faras ĉi tiu algoritmo skalo

20
00:00:56,110 --> 00:00:59,020
kiel ni ĵeti pli kaj pli datumoj en ĝi?

21
00:00:59,020 --> 00:01:02,220
En CS50, la kvanto de datumoj ni estas
laborante kun estas belaj malgrandaj.

22
00:01:02,220 --> 00:01:05,140
Ĝenerale, niaj programoj estas irantaj
kuri en dua aŭ less--

23
00:01:05,140 --> 00:01:07,830
probable multe malpli
aparte frue sur.

24
00:01:07,830 --> 00:01:12,250
>> Sed pensu pri kompanio kiu traktas
kun centoj da milionoj de klientoj.

25
00:01:12,250 --> 00:01:14,970
Ili devas prilabori
ke klienta datumo.

26
00:01:14,970 --> 00:01:18,260
Kiel la nombro de klientoj ili
havi ricevas pli kaj pli grandaj,

27
00:01:18,260 --> 00:01:21,230
ĝi tuj postulas
pli kaj pli rimedoj.

28
00:01:21,230 --> 00:01:22,926
Kiel multaj pli rimedoj?

29
00:01:22,926 --> 00:01:25,050
Nu, tio dependas de kiel
ni analizos la algoritmo,

30
00:01:25,050 --> 00:01:28,097
uzante la ilojn en tiu toolbox.

31
00:01:28,097 --> 00:01:31,180
Kiam ni parolas pri la komplekseco de
an algorithm-- kiuj foje vi instruos vin

32
00:01:31,180 --> 00:01:34,040
aŭskultos referita kiel tempo
komplekseco aŭ spaca komplikeco

33
00:01:34,040 --> 00:01:36,190
sed ni ĵus tuj
voki complexity--

34
00:01:36,190 --> 00:01:38,770
ni ĝenerale parolas pri
la plej malbona-kazo scenaro.

35
00:01:38,770 --> 00:01:42,640
Donita la absoluta plej malbona stako de
datumoj kiuj ni povus ĵeti ĝin,

36
00:01:42,640 --> 00:01:46,440
kiele tiu algoritmo tuj
procesi aŭ trakti ke datumoj?

37
00:01:46,440 --> 00:01:51,450
Ni ĝenerale nomas la plej malbona-kazo
ekzekuto de algoritmo granda-O.

38
00:01:51,450 --> 00:01:56,770
Do algoritmo povus esti dirita
kuri en O de n aŭ O de n kvadratoj.

39
00:01:56,770 --> 00:01:59,110
Kaj pli pri kio
tiuj signifas en sekundo.

40
00:01:59,110 --> 00:02:01,620
>> Kelkfoje, tamen, ni faru prizorgo
pri la plej kazo scenaro.

41
00:02:01,620 --> 00:02:05,400
Se la datumoj estas ĉio ni volis
ĝin esti kaj estis absolute perfekta

42
00:02:05,400 --> 00:02:09,630
Kaj ni estis sendanta tiun perfekta
aro de datumoj per nia algoritmo.

43
00:02:09,630 --> 00:02:11,470
Kial ne pritrakti en tiu situacio?

44
00:02:11,470 --> 00:02:15,050
Ni foje rilati al tio kiel
big-Omega, do en kontrasto kun granda-O,

45
00:02:15,050 --> 00:02:16,530
ni havas granda-Omega.

46
00:02:16,530 --> 00:02:18,880
Big-Omega por la plej kazo scenaro.

47
00:02:18,880 --> 00:02:21,319
Big-O por la plej malbona-kazo scenaro.

48
00:02:21,319 --> 00:02:23,860
Ĝenerale, kiam oni parolas pri
la komplikeco de algoritmo,

49
00:02:23,860 --> 00:02:26,370
ni parolas pri la
plej malbona-kazo scenaro.

50
00:02:26,370 --> 00:02:28,100
Observu do, ke en menso.

51
00:02:28,100 --> 00:02:31,510
>> Kaj en ĉi tiu klaso, ni ĝenerale irante
forlasi la strikta analizo flanken.

52
00:02:31,510 --> 00:02:35,350
Ekzistas sciencoj kaj kampoj
dediĉita al tiu klaso de aĵoj.

53
00:02:35,350 --> 00:02:37,610
Kiam ni parolas pri rezonado
tra algoritmoj,

54
00:02:37,610 --> 00:02:41,822
kion ni faros pecon-post-peco por multaj
algoritmoj ni raportas en la klaso.

55
00:02:41,822 --> 00:02:44,780
Ni vere nur parolas pri
diskutis tra ĝi kun komuna senso,

56
00:02:44,780 --> 00:02:47,070
Ne kun formuloj, aŭ pruvoj,
aŭ io simila.

57
00:02:47,070 --> 00:02:51,600
Do ne zorgu, ni ne estos
igante granda math klaso.

58
00:02:51,600 --> 00:02:55,920
>> Do mi diris, ke ni zorgas pri komplekseco
ĉar ĝi petas la demandon, kiamaniere

59
00:02:55,920 --> 00:03:00,160
ĉu nia algoritmoj manipuli pli grandajn kaj
grandaj datenaroj estanta ĵetita ĉe ili.

60
00:03:00,160 --> 00:03:01,960
Nu, kio estas datumoj aro?

61
00:03:01,960 --> 00:03:03,910
Kion mi volas diri kiam mi diras ke?

62
00:03:03,910 --> 00:03:07,600
Ĝi signifas ajn faras la plej
senco en kunteksto, por esti honesta.

63
00:03:07,600 --> 00:03:11,160
Se ni havas algoritmon, la
Procezoj Strings-- ni probable

64
00:03:11,160 --> 00:03:13,440
parolante pri la grandeco de la kordo.

65
00:03:13,440 --> 00:03:15,190
Jen la datumoj set--
la grandeco, la nombro

66
00:03:15,190 --> 00:03:17,050
de karakteroj kiuj konsistigas la kordo.

67
00:03:17,050 --> 00:03:20,090
Se ni parolas pri
algoritmo kiu procesas dosierojn,

68
00:03:20,090 --> 00:03:23,930
Ni povus esti parolante pri kiom
multaj kilobajtoj konsistas ke dosiero.

69
00:03:23,930 --> 00:03:25,710
Kaj tio estas la datuma aro.

70
00:03:25,710 --> 00:03:28,870
Se ni parolas pri algoritmo
kiu manipulas arrays pli ĝenerale,

71
00:03:28,870 --> 00:03:31,510
kiel ordigado algoritmoj
aŭ serĉanta algoritmoj,

72
00:03:31,510 --> 00:03:36,690
ni probable parolas pri la nombro
de elementoj kiuj formas parton tabelo.

73
00:03:36,690 --> 00:03:39,272
>> Nun, ni povas mezuri la
algorithm-- precipe,

74
00:03:39,272 --> 00:03:40,980
kiam mi diras ni povas
mezuri algoritmo, mi

75
00:03:40,980 --> 00:03:43,840
signifas ni povas mezuri kiom
multaj rimedoj prenas supren.

76
00:03:43,840 --> 00:03:48,990
Cxu tiuj rimedoj estas, kiom da
bajtoj de RAM-- aŭ megabajtoj de RAM

77
00:03:48,990 --> 00:03:49,790
ĝi uzas.

78
00:03:49,790 --> 00:03:52,320
Aŭ kiom tempo prenas kuri.

79
00:03:52,320 --> 00:03:56,200
Kaj ni povas nomi ĉi
mezuri, arbitre, f de n.

80
00:03:56,200 --> 00:03:59,420
Kie n estas la nombro de
elementoj en la datuma aro.

81
00:03:59,420 --> 00:04:02,640
Kaj f de n estas kiom multaj somethings.

82
00:04:02,640 --> 00:04:07,530
Kiom da unuoj de rimedoj faras
ĝi postulas procesi ke datumoj.

83
00:04:07,530 --> 00:04:10,030
>> Nun, ni efektive ne gravas
pri kio f de n estas ĝuste.

84
00:04:10,030 --> 00:04:13,700
Fakte, ni tre malofte will--
certe neniam en ĉi class-- mi

85
00:04:13,700 --> 00:04:18,709
plonĝi en ajnan vere profunda
analizo de kion f de n estas.

86
00:04:18,709 --> 00:04:23,510
Ni nur tuj paroli pri kion f de
n estas proksimume kia ĝi emas.

87
00:04:23,510 --> 00:04:27,600
Kaj la tendenco de algoritmo estas
diktita de ĝia plej alta ordo terminon.

88
00:04:27,600 --> 00:04:29,440
Kaj ni povas vidi kion mi
signifas ke prenante

89
00:04:29,440 --> 00:04:31,910
Rigardu pli konkretan ekzemplon.

90
00:04:31,910 --> 00:04:34,620
>> Do diru ke ni havas
tri malsamaj algoritmoj.

91
00:04:34,620 --> 00:04:39,350
La unua el kiuj prenas n
Cubed, iuj unuecoj de rimedoj

92
00:04:39,350 --> 00:04:42,880
procesi datuma aro de amplekso n.

93
00:04:42,880 --> 00:04:47,000
Ni havas dua algoritmo kiu prenas
n Cubed plus n kvadratoj rimedoj

94
00:04:47,000 --> 00:04:49,350
procesi datuma aro de amplekso n.

95
00:04:49,350 --> 00:04:52,030
Kaj ni havas trian
algoritmo kiu kuras in-- ke

96
00:04:52,030 --> 00:04:58,300
dissxutas n Cubed minus 8n kvadrato
plus 20 n unuoj de rimedoj

97
00:04:58,300 --> 00:05:02,370
procesi algoritmo
kun datuma aro de amplekso n.

98
00:05:02,370 --> 00:05:05,594
>> Nun denove, ni vere ne tuj
enir tiu nivelo de detalo.

99
00:05:05,594 --> 00:05:08,260
Fakte, mi nur havas tiujn supren
tie kiel ilustraĵo de punkto

100
00:05:08,260 --> 00:05:10,176
ke mi tuj estos
farante en sekundo, kio

101
00:05:10,176 --> 00:05:12,980
estas ke ni nur vere zorgas
pri la tendenco de aferoj

102
00:05:12,980 --> 00:05:14,870
kiel la datenaroj pligrandiĝi.

103
00:05:14,870 --> 00:05:18,220
Do se la datuma aro estas malgrandaj, ekzistas
fakte iom granda diferenco

104
00:05:18,220 --> 00:05:19,870
en tiuj algoritmoj.

105
00:05:19,870 --> 00:05:23,000
La tria algoritmo tie
prenas 13 fojojn pli longaj,

106
00:05:23,000 --> 00:05:27,980
13 fojojn la kvanto de rimedoj
kuri relativa al la unua unu.

107
00:05:27,980 --> 00:05:31,659
>> Se niaj datumoj aro estas grandeco 10, kiu
estas pli granda, sed ne nepre grandega,

108
00:05:31,659 --> 00:05:33,950
ni povas vidi ke ekzistas
efektive iom de diferenco.

109
00:05:33,950 --> 00:05:36,620
La tria algoritmo
iĝas pli efika.

110
00:05:36,620 --> 00:05:40,120
Temas pri vere 40% -
aŭ 60% pli eficientes.

111
00:05:40,120 --> 00:05:41,580
Ĝi prenas 40% la kvanto de tempo.

112
00:05:41,580 --> 00:05:45,250
Ĝi povas run-- povas preni
400 ekzemplerojn de rimedoj

113
00:05:45,250 --> 00:05:47,570
prilabori datumojn pri grandeco 10.

114
00:05:47,570 --> 00:05:49,410
Dum la unua
algoritmo, kontraste,

115
00:05:49,410 --> 00:05:54,520
prenas 1.000 rimedoj
prilabori datumojn pri grandeco 10.

116
00:05:54,520 --> 00:05:57,240
Sed vidu kio okazas kiam
niaj nombroj akiri eĉ pli granda.

117
00:05:57,240 --> 00:05:59,500
>> Nun, la diferenco
inter tiuj algoritmoj

118
00:05:59,500 --> 00:06:01,420
komencas fariĝi iom malpli evidenta.

119
00:06:01,420 --> 00:06:04,560
Kaj la fakto ke ekzistas
malsupra ordo terms-- aŭ prefere,

120
00:06:04,560 --> 00:06:09,390
terminoj kun suba exponents--
komenci fariĝi pala.

121
00:06:09,390 --> 00:06:12,290
Se datuma aro estas de grandeco
1.000 kaj la unua algoritmo

122
00:06:12,290 --> 00:06:14,170
kuras en miliardo paŝoj.

123
00:06:14,170 --> 00:06:17,880
Kaj la dua algoritmo kuras en
miliardo kaj miliono paŝoj.

124
00:06:17,880 --> 00:06:20,870
Kaj la tria algoritmo kuras
en ĵus timema de miliardo paŝoj.

125
00:06:20,870 --> 00:06:22,620
Estas preskaux miliardo paŝoj.

126
00:06:22,620 --> 00:06:25,640
Tiuj malsupra ordo esprimoj komenci
fariĝi vere pala.

127
00:06:25,640 --> 00:06:27,390
Kaj ĝuste por vere
martelo domo la point--

128
00:06:27,390 --> 00:06:31,240
se la datumoj enigo estas de grandeco a
million-- ĉiuj tri de ĉi tiuj preskaux

129
00:06:31,240 --> 00:06:34,960
preni unu quintillion-- se
mia math estas correct-- paŝoj

130
00:06:34,960 --> 00:06:37,260
prilabori datumojn enigo
de grandeco miliono.

131
00:06:37,260 --> 00:06:38,250
Tio estas multe da ŝtupoj.

132
00:06:38,250 --> 00:06:42,092
Kaj la fakto ke unu el ili povus
preni paron 100.000, aŭ paro 100

133
00:06:42,092 --> 00:06:44,650
milionoj eĉ malpli kiam
ni parolas pri kelkaj

134
00:06:44,650 --> 00:06:46,990
ke big-- estas afable pala.

135
00:06:46,990 --> 00:06:50,006
Ili ĉiuj emas preni
proksimume n Cubed,

136
00:06:50,006 --> 00:06:52,380
kaj tiaj ni estus reale rilati
al ĉiuj tiuj algoritmoj

137
00:06:52,380 --> 00:06:59,520
kiel estante sur la ordo de n
Cubed aŭ granda-O de n potenco de.

138
00:06:59,520 --> 00:07:03,220
>> Jen listo de iuj el la pli
komuna komputa komplikeco klasoj

139
00:07:03,220 --> 00:07:05,820
ke ni renkontas en
algoritmoj, ĝenerale.

140
00:07:05,820 --> 00:07:07,970
Kaj ankaŭ specife en CS50.

141
00:07:07,970 --> 00:07:11,410
Tiuj estas ordonitaj de
ĝenerale plej rapida ĉe la supro,

142
00:07:11,410 --> 00:07:13,940
al ĝenerale malrapida ĉe la fundo.

143
00:07:13,940 --> 00:07:16,920
Do konstanta tempo algoritmoj tendencas
esti la plej rapida, sendepende

144
00:07:16,920 --> 00:07:19,110
de la grandeco de la
datumoj enigo sekvinberoj en.

145
00:07:19,110 --> 00:07:23,760
Ili ĉiam preni unu operacion aŭ
unu unuo de rimedoj por trakti.

146
00:07:23,760 --> 00:07:25,730
Ĝi povus esti 2, oni eble
esti 3, eble 4.

147
00:07:25,730 --> 00:07:26,910
Sed estas konstanta nombro.

148
00:07:26,910 --> 00:07:28,400
Ĝi ne varias.

149
00:07:28,400 --> 00:07:31,390
>> Logaritma tempo algoritmoj
estas iomete pli bone.

150
00:07:31,390 --> 00:07:33,950
Kaj vere bona ekzemplo de
logaritma tempo algoritmo

151
00:07:33,950 --> 00:07:37,420
Vi certe vidis nun estas la
ŝirante dise de la telefono libro

152
00:07:37,420 --> 00:07:39,480
trovi Mike Smith en telefono libro.

153
00:07:39,480 --> 00:07:40,980
Ni tranĉas la problemo en duono.

154
00:07:40,980 --> 00:07:43,580
Kaj tiel kiel n prenas pli granda
kaj pli granda kaj larger--

155
00:07:43,580 --> 00:07:47,290
fakte, ĉiufoje vi duobligi
n, ĝi nur prenas pli paŝo.

156
00:07:47,290 --> 00:07:49,770
Do jen multa bona
ol, ni diru, lineara tempo.

157
00:07:49,770 --> 00:07:53,030
Kio estas se vi duobligos n, ĝi
prenas duobla la nombro de paŝoj.

158
00:07:53,030 --> 00:07:55,980
Se vi triobligi n, prenas
triobligi la nombron de paŝoj.

159
00:07:55,980 --> 00:07:58,580
Unu paŝo por unueco.

160
00:07:58,580 --> 00:08:01,790
>> Tiam aĵoj iom more--
iom malpli granda de tie.

161
00:08:01,790 --> 00:08:06,622
Vi havas lineara ritmaj tempo, kelkfoje
nomata log lineara tempo aŭ simple n log n.

162
00:08:06,622 --> 00:08:08,330
Kaj ni vidos ekzemplon
de algoritmo ke

163
00:08:08,330 --> 00:08:13,370
kurojn en n log n, kio estas ankoraŭ pli bona
ol kvadrata time-- n kvadratoj.

164
00:08:13,370 --> 00:08:17,320
Aŭ polinoma tempo, n du
ajna nombro pli granda ol du.

165
00:08:17,320 --> 00:08:20,810
Aŭ eksponenta tempo, kio
estas eĉ worse-- C al la n.

166
00:08:20,810 --> 00:08:24,670
Do iu konstanto nombro altigita al
la potenco de la grandeco de la enigaĵo.

167
00:08:24,670 --> 00:08:28,990
Do, se estas 1,000-- se la
datumoj enigo estas de grandeco 1.000,

168
00:08:28,990 --> 00:08:31,310
necesus C al la 1,000 potenco.

169
00:08:31,310 --> 00:08:33,559
Estas multe pli malbone ol polinoma tempo.

170
00:08:33,559 --> 00:08:35,030
>> Faktorialo tempo estas eĉ pli malbona.

171
00:08:35,030 --> 00:08:37,760
Kaj fakte, tie vere fari
ekzistas senfina tempo algoritmoj,

172
00:08:37,760 --> 00:08:43,740
kiel, tiel nomata stulta sort-- kies
laborposteno estas hazarde barajar tabelo

173
00:08:43,740 --> 00:08:45,490
kaj tiam kontrolu vidi
ĉu ĝi estas ordo.

174
00:08:45,490 --> 00:08:47,589
Kaj se ĝi ne estas, hazarde
barajar la tabelo denove

175
00:08:47,589 --> 00:08:49,130
kaj kontrolu ĉu ĝi estas ordo.

176
00:08:49,130 --> 00:08:51,671
Kaj kiel vi povas verŝajne imagine--
vi povas imagi situacion

177
00:08:51,671 --> 00:08:55,200
kie en la plej malbona kazo, ke volo
neniam efektive komenci kun la tabelo.

178
00:08:55,200 --> 00:08:57,150
Ke algoritmo estus kuri eterne.

179
00:08:57,150 --> 00:08:59,349
Kaj tial estus
malfinia tempa algoritmo.

180
00:08:59,349 --> 00:09:01,890
Espereble vi ne skribos
ajna faktorialo aŭ senfina tempo

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

182
00:09:04,510 --> 00:09:09,150
>> Do, ni prenu iom pli
konkreta rigardi kelkaj simplaj

183
00:09:09,150 --> 00:09:11,154
komputa komplekseca klaso.

184
00:09:11,154 --> 00:09:13,070
Do ni havas example--
aŭ du ekzemplojn here--

185
00:09:13,070 --> 00:09:15,590
de konstanta tempo algoritmoj,
kiu ĉiam preni

186
00:09:15,590 --> 00:09:17,980
sola operacio en la plej malbona kazo.

187
00:09:17,980 --> 00:09:20,050
Do la unua example--
ni havas funkcion

188
00:09:20,050 --> 00:09:23,952
nomita 4 por vi, kiuj
prenas tabelo de amplekso 1.000.

189
00:09:23,952 --> 00:09:25,660
Sed tiam ŝajne
fakte ne aspektas

190
00:09:25,660 --> 00:09:29,000
ĉe it-- ne vere zorgas kio estas
interne de ĝi, de tiu tabelo.

191
00:09:29,000 --> 00:09:30,820
Ĉiam ĵus revenas kvar.

192
00:09:30,820 --> 00:09:32,940
Do, tiu algoritmo,
spite la fakton ke ĝi

193
00:09:32,940 --> 00:09:35,840
prenas 1.000 elementoj ne
fari nenion kun ili.

194
00:09:35,840 --> 00:09:36,590
Nur revenas kvar.

195
00:09:36,590 --> 00:09:38,240
Ĝi ĉiam estas sola paŝo.

196
00:09:38,240 --> 00:09:41,600
>> Fakte, aldonu 2 nums-- kiu
ni vidis antaŭe kiel well--

197
00:09:41,600 --> 00:09:43,680
nur procesas du entjeroj.

198
00:09:43,680 --> 00:09:44,692
Ĝi ne estas sola paŝo.

199
00:09:44,692 --> 00:09:45,900
Ĝi estas fakte paro paŝoj.

200
00:09:45,900 --> 00:09:50,780
Vi ricevas, vi ricevas b, vi aldonas ilin
kune, kaj ci elirigos la rezultoj.

201
00:09:50,780 --> 00:09:53,270
Do estas 84 paŝoj.

202
00:09:53,270 --> 00:09:55,510
Sed estas ĉiam konstanto,
nekonsiderante a aŭ b.

203
00:09:55,510 --> 00:09:59,240
Vi devas akiri, atingi b, aldonu
ili kune, eligo la rezulto.

204
00:09:59,240 --> 00:10:02,900
Do tio estas konstanta tempo algoritmo.

205
00:10:02,900 --> 00:10:05,170
>> Jen ekzemplo de
lineara tempo algorithm--

206
00:10:05,170 --> 00:10:08,740
algoritmo kiu gets-- kiu prenas
unu plian paŝon, eble,

207
00:10:08,740 --> 00:10:10,740
kiel via enigo kreskas per 1.

208
00:10:10,740 --> 00:10:14,190
Do, diru ni serĉas
la nombro 5 ene de tabelo.

209
00:10:14,190 --> 00:10:16,774
Vi povus havi situacion kie
vi povas trovi ĝin sufiĉe frue.

210
00:10:16,774 --> 00:10:18,606
Sed vi povus ankaŭ havi
situacio kie

211
00:10:18,606 --> 00:10:20,450
eble estos la lasta elemento de la tabelo.

212
00:10:20,450 --> 00:10:23,780
En tabelo de amplekso 5, se
ni serĉas la numero 5.

213
00:10:23,780 --> 00:10:25,930
Ĝi prenus 5 paŝoj.

214
00:10:25,930 --> 00:10:29,180
Kaj fakte, imagu ke ekzistas
Ne 5 ie en tiu tabelo.

215
00:10:29,180 --> 00:10:32,820
Ni ankoraŭ vere devas rigardi
ĉiu unuopa elemento de la tabelo

216
00:10:32,820 --> 00:10:35,550
por determini
ĉu 5 estas tie.

217
00:10:35,550 --> 00:10:39,840
>> Do en la plej malbona kazo, kio estas ke
la elemento estas lasta en la tabelo

218
00:10:39,840 --> 00:10:41,700
aŭ ne ekzistas entute.

219
00:10:41,700 --> 00:10:44,690
Ni ankoraŭ devas rigardi
ĉiuj de la n elementoj.

220
00:10:44,690 --> 00:10:47,120
Kaj tial tiu algoritmo
kuras en lineara tempo.

221
00:10:47,120 --> 00:10:50,340
Vi povas konfirmi ke
extrapolar iomete dirante,

222
00:10:50,340 --> 00:10:53,080
se ni havis 6-era tabelo kaj
ni serĉis la numero 5,

223
00:10:53,080 --> 00:10:54,890
ĝi povus preni 6 paŝoj.

224
00:10:54,890 --> 00:10:57,620
Se ni havas 7-era tabelo kaj
ni serĉas la numero 5.

225
00:10:57,620 --> 00:10:59,160
Ĝi povus preni 7 paŝoj.

226
00:10:59,160 --> 00:11:02,920
Kiel ni aldonos unu pli elementon al nia
tabelo, ĝi prenas pli paŝo.

227
00:11:02,920 --> 00:11:06,750
Tio lineara algoritmo
en la plej malbona kazo.

228
00:11:06,750 --> 00:11:08,270
>> Paro rapide demandoj por vi.

229
00:11:08,270 --> 00:11:11,170
Kio estas la runtime-- kio estas
la plej malbona-kazo tempo de ekzekuto

230
00:11:11,170 --> 00:11:13,700
de tiu aparta fragmento de kodo?

231
00:11:13,700 --> 00:11:17,420
Do mi havas 4 buklo tie ke kuroj
el j egalas 0, tuta vojo supren al m.

232
00:11:17,420 --> 00:11:21,980
Kaj kion mi vidas ĉi tie, estas ke la
korpo de la banto kuras en konstanta tempo.

233
00:11:21,980 --> 00:11:24,730
Do uzante la terminologion ke
ni jam parolis about-- kio

234
00:11:24,730 --> 00:11:29,390
estus la plej malbona-kazo
ekzekuto de ĉi tiu algoritmo?

235
00:11:29,390 --> 00:11:31,050
Prenu duan.

236
00:11:31,050 --> 00:11:34,270
La ena parto de la buklo
kuras en konstanta tempo.

237
00:11:34,270 --> 00:11:37,510
Kaj la ekstera parto de la
buklo tuj kuri m fojojn.

238
00:11:37,510 --> 00:11:40,260
Do kio estas la plej malbona-kazo tempo de ekzekuto tie?

239
00:11:40,260 --> 00:11:43,210
Ĉu vi divenas grand-O de m?

240
00:11:43,210 --> 00:11:44,686
Vi estus prava.

241
00:11:44,686 --> 00:11:46,230
>> Kion pri alia?

242
00:11:46,230 --> 00:11:48,590
Ĉi tiu fojo ni havas
buklo ene de banto.

243
00:11:48,590 --> 00:11:50,905
Ni havas eksteran banton
kiu kuras de nulo al p.

244
00:11:50,905 --> 00:11:54,630
Kaj ni havas internan banton kiu kuras
de nulo al p, kaj ene de tiu,

245
00:11:54,630 --> 00:11:57,890
Mi deklaras ke la korpo la
buklo kuras en konstanta tempo.

246
00:11:57,890 --> 00:12:02,330
Do kio estas la plej malbona-kazo tempo de ekzekuto
de tiu aparta fragmento de kodo?

247
00:12:02,330 --> 00:12:06,140
Nu, denove, ni havas
ekstera buklo kiu kuras p fojojn.

248
00:12:06,140 --> 00:12:09,660
Kaj ĉiu time-- ripeto
de tiu buklo, prefere.

249
00:12:09,660 --> 00:12:13,170
Ni havas internan banton
kiu ankaŭ kuras p fojojn.

250
00:12:13,170 --> 00:12:16,900
Kaj tiam ene de tiu, estas la
konstanta time-- iom fragmento tie.

251
00:12:16,900 --> 00:12:19,890
>> Do se ni havas eksteran banton ke
kuras p fojojn ene de kiuj estas

252
00:12:19,890 --> 00:12:22,880
ena buklo ke
kuras p times-- kio estas

253
00:12:22,880 --> 00:12:26,480
la plej malbona-kazo tempo de ekzekuto
de tiu fragmento de kodo?

254
00:12:26,480 --> 00:12:30,730
Ĉu vi divenas grand-O de p kvadrato?

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

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

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