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

2
00:00:05,830 --> 00:00:07,910
>> Vse je v redu, tako, računska zahtevnost.

3
00:00:07,910 --> 00:00:10,430
Samo malo opozorilo
preden se potopite v preveč far--

4
00:00:10,430 --> 00:00:13,070
To bo verjetno med
Najbolj math-težkih stvari

5
00:00:13,070 --> 00:00:14,200
govorimo o v CS50.

6
00:00:14,200 --> 00:00:16,950
Upajmo, da ne bo preveč prepričljivo
in bomo poskušali, in vas vodi

7
00:00:16,950 --> 00:00:19,200
skozi proces, vendar
samo malo poštenega opozorila.

8
00:00:19,200 --> 00:00:21,282
Tam je malo
matematike vključeni tukaj.

9
00:00:21,282 --> 00:00:23,990
Vse je v redu, tako da se bo
Uporaba naših računalniških virov

10
00:00:23,990 --> 00:00:28,170
v resničnem world-- to je res
pomembno razumeti algoritme

11
00:00:28,170 --> 00:00:30,750
in kako se obdelujejo podatke.

12
00:00:30,750 --> 00:00:32,810
Če imamo res
učinkovit algoritem smo

13
00:00:32,810 --> 00:00:36,292
lahko zmanjša znesek sredstev,
imamo na voljo za spopadanje z njo.

14
00:00:36,292 --> 00:00:38,750
Če imamo algoritem, ki
se dogaja, da se veliko dela

15
00:00:38,750 --> 00:00:41,210
obdelati res
Velik nabor podatkov, je

16
00:00:41,210 --> 00:00:44,030
dogaja, da zahtevajo več
in več virov, ki

17
00:00:44,030 --> 00:00:47,980
je denar, RAM, vse te vrste stvari.

18
00:00:47,980 --> 00:00:52,090
>> Torej, da lahko analiziramo
algoritem z uporabo tega orodja set,

19
00:00:52,090 --> 00:00:56,110
v bistvu prosi question--
kako se ta algoritem lestvice

20
00:00:56,110 --> 00:00:59,020
kot smo metati vse več podatkov na njej?

21
00:00:59,020 --> 00:01:02,220
V CS50, količino podatkov smo
delo s je precej majhen.

22
00:01:02,220 --> 00:01:05,140
Na splošno, naši programi bodo
teči v drugo ali less--

23
00:01:05,140 --> 00:01:07,830
verjetno veliko manj
predvsem že na začetku.

24
00:01:07,830 --> 00:01:12,250
>> Ampak pomislite podjetje, ki se ukvarja
z več sto milijonov kupcev.

25
00:01:12,250 --> 00:01:14,970
In ki jih potrebujejo za obdelavo
da podatki strank.

26
00:01:14,970 --> 00:01:18,260
Ker je število strank, ki jih
imajo postane večji in večji,

27
00:01:18,260 --> 00:01:21,230
to se dogaja, da zahtevajo
več in več sredstev.

28
00:01:21,230 --> 00:01:22,926
Koliko več sredstev?

29
00:01:22,926 --> 00:01:25,050
No, to je odvisno od tega, kako
smo analizirali algoritem,

30
00:01:25,050 --> 00:01:28,097
uporabo orodij v tej orodjarni.

31
00:01:28,097 --> 00:01:31,180
Ko govorimo o kompleksnosti
algorithm-- ki včasih boste

32
00:01:31,180 --> 00:01:34,040
slišite, da se imenuje čas
kompleksnost ali prostorska zahtevnost

33
00:01:34,040 --> 00:01:36,190
vendar smo šele tekoč
poklicati complexity--

34
00:01:36,190 --> 00:01:38,770
smo na splošno govorimo o
najslabšem primeru.

35
00:01:38,770 --> 00:01:42,640
Glede na absolutno najslabše kup
podatke, ki bi lahko smo metali na to,

36
00:01:42,640 --> 00:01:46,440
kako je ta algoritem bo
obdelavo ali se ukvarjajo s temi podatki?

37
00:01:46,440 --> 00:01:51,450
Smo na splošno imenujemo najslabšim
teka algoritma big-O.

38
00:01:51,450 --> 00:01:56,770
Torej bi lahko algoritem je dejal, da
teči O N ali O n kvadrat.

39
00:01:56,770 --> 00:01:59,110
In še o tem, kaj
tiste pomeni v sekundi.

40
00:01:59,110 --> 00:02:01,620
>> Včasih, čeprav nam ni vseeno
o najboljšem primeru.

41
00:02:01,620 --> 00:02:05,400
Če podatki, je vse, kar smo želeli
da bi bilo in da je absolutno popolna

42
00:02:05,400 --> 00:02:09,630
in smo bili pošiljanje to odlično
niz podatkov preko našega algoritma.

43
00:02:09,630 --> 00:02:11,470
Kako bi bilo ravnati v tem primeru?

44
00:02:11,470 --> 00:02:15,050
Včasih se nanašajo na to kot
big-Omega, tako da v nasprotju z big-O,

45
00:02:15,050 --> 00:02:16,530
imamo velik-Omega.

46
00:02:16,530 --> 00:02:18,880
Big-Omega za najboljšem primeru.

47
00:02:18,880 --> 00:02:21,319
Big-O za najslabšem primeru.

48
00:02:21,319 --> 00:02:23,860
Na splošno, ko govorimo o
kompleksnost algoritmom,

49
00:02:23,860 --> 00:02:26,370
govorimo približno
najslabši scenarij.

50
00:02:26,370 --> 00:02:28,100
Tako da se vodijo v mislih.

51
00:02:28,100 --> 00:02:31,510
>> In v tem razredu, smo na splošno dogaja
zapustiti natančno analizo stran.

52
00:02:31,510 --> 00:02:35,350
Obstajajo vede in polja
namenjenih za tovrstne stvari.

53
00:02:35,350 --> 00:02:37,610
Ko govorimo o obrazložitvi
pomočjo algoritmov,

54
00:02:37,610 --> 00:02:41,822
katero bomo naredili kos-by-kos za mnoge
algoritmi govorimo o v razredu.

55
00:02:41,822 --> 00:02:44,780
Mi smo res samo govoriš
razmišljanjem skozi to z razumom,

56
00:02:44,780 --> 00:02:47,070
ne s formulami, ali dokazila,
ali kaj podobnega.

57
00:02:47,070 --> 00:02:51,600
Torej, ne skrbite, ne bomo
preobrat v velikem matematičnem razredu.

58
00:02:51,600 --> 00:02:55,920
>> Zato sem rekel, da je mar kompleksnosti
ker se zastavlja vprašanje, kako

59
00:02:55,920 --> 00:03:00,160
pa naši algoritmi ročaj večji in
Večje podatkovni nizi, ki se vrže na njih.

60
00:03:00,160 --> 00:03:01,960
No, kaj je niz podatkov?

61
00:03:01,960 --> 00:03:03,910
Kaj sem mislil, ko sem rekel, da je?

62
00:03:03,910 --> 00:03:07,600
To pomeni karkoli kar najbolje
Občutek v kontekstu, če sem iskren.

63
00:03:07,600 --> 00:03:11,160
Če imamo algoritem, na
Procesi Strings-- smo verjetno

64
00:03:11,160 --> 00:03:13,440
govorimo o velikosti niza.

65
00:03:13,440 --> 00:03:15,190
To so podatki set--
velikost, števila

66
00:03:15,190 --> 00:03:17,050
znakov, ki sestavljajo niz.

67
00:03:17,050 --> 00:03:20,090
Če govorimo o
algoritem, ki obdeluje datotek

68
00:03:20,090 --> 00:03:23,930
bomo lahko govorili o tem, kako
veliko kilobajtov sestavljajo to datoteko.

69
00:03:23,930 --> 00:03:25,710
In to je nabor podatkov.

70
00:03:25,710 --> 00:03:28,870
Če govorimo o algoritmu
ki se ukvarja nizi bolj na splošno,

71
00:03:28,870 --> 00:03:31,510
kot so algoritmi za sortiranje
ali iskanje algoritmov,

72
00:03:31,510 --> 00:03:36,690
bomo verjetno govorimo o številu
elementov, ki sestavljajo niz.

73
00:03:36,690 --> 00:03:39,272
>> Sedaj lahko ukrep
algorithm-- zlasti

74
00:03:39,272 --> 00:03:40,980
ko sem rekel, smo lahko
merjenje algoritem, I

75
00:03:40,980 --> 00:03:43,840
pomeni, da lahko merimo, kako
veliko virov, da prevzame.

76
00:03:43,840 --> 00:03:48,990
Ali so ti viri, koliko
bajtov RAM-- ali MB RAM

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

78
00:03:49,790 --> 00:03:52,320
Ali pa, koliko časa je potrebno za vodenje.

79
00:03:52,320 --> 00:03:56,200
In lahko rečemo to
izmerimo, poljubno, f n.

80
00:03:56,200 --> 00:03:59,420
Kjer je n število
elementi v podatkovnem nizu.

81
00:03:59,420 --> 00:04:02,640
In f n je, koliko somethings.

82
00:04:02,640 --> 00:04:07,530
Koliko enot sredstev ne
zahteva za obdelavo teh podatkov.

83
00:04:07,530 --> 00:04:10,030
>> Zdaj smo pravzaprav ne zanima
o tem, kaj f n je točno.

84
00:04:10,030 --> 00:04:13,700
V bistvu smo zelo redko will--
zagotovo ne bo nikoli v tej class-- I

85
00:04:13,700 --> 00:04:18,709
potopite v nobeno res globok
Analiza kaj f n.

86
00:04:18,709 --> 00:04:23,510
Mi smo le, da bo govoril o tem, kaj f
n je približno ali kaj se nagiba k.

87
00:04:23,510 --> 00:04:27,600
In težnja algoritmu je
narekuje najvišji izraz naročila.

88
00:04:27,600 --> 00:04:29,440
In smo lahko videli, kaj sem
mislim s tem, ki ga ob

89
00:04:29,440 --> 00:04:31,910
poglej na bolj konkreten primer.

90
00:04:31,910 --> 00:04:34,620
>> Torej, recimo, da imamo
trije različni algoritmi.

91
00:04:34,620 --> 00:04:39,350
Prvi od katerih je n
kubikov, nekatere enote virov

92
00:04:39,350 --> 00:04:42,880
obdelati podatkovnega niza velikosti n.

93
00:04:42,880 --> 00:04:47,000
Imamo drugo algoritem, ki bo
n kubikov plus n kvadrati viri

94
00:04:47,000 --> 00:04:49,350
obdelati podatkovnega niza velikosti n.

95
00:04:49,350 --> 00:04:52,030
In imamo tretja
Algoritem, ki teče in-- da

96
00:04:52,030 --> 00:04:58,300
zavzema n kubikov minus 8N na kvadrat
plus 20 n enot sredstev

97
00:04:58,300 --> 00:05:02,370
obdelati algoritem
s podatki iz velikosti n.

98
00:05:02,370 --> 00:05:05,594
>> Zdaj spet, res se ne bo
priti v tej ravni podrobnosti.

99
00:05:05,594 --> 00:05:08,260
Res sem samo še ti gor
Tukaj kot ilustracija točke

100
00:05:08,260 --> 00:05:10,176
da bom lahko
izdelavo sekundo, kar

101
00:05:10,176 --> 00:05:12,980
je, da smo samo res skrbi
o tendenci stvari

102
00:05:12,980 --> 00:05:14,870
kot podatkovni nizi dobili večji.

103
00:05:14,870 --> 00:05:18,220
Torej, če je podatkovni niz je majhna, obstaja
pravzaprav zelo velika razlika

104
00:05:18,220 --> 00:05:19,870
V teh algoritmov.

105
00:05:19,870 --> 00:05:23,000
Tretji algoritem tam
traja 13-krat dlje,

106
00:05:23,000 --> 00:05:27,980
13-kratni znesek sredstev
teči glede na prvega.

107
00:05:27,980 --> 00:05:31,659
>> Če je naš nabor podatkov je velikost 10, ki
je večja, vendar ne nujno velika,

108
00:05:31,659 --> 00:05:33,950
lahko vidimo, da obstaja
pravzaprav malo razlike.

109
00:05:33,950 --> 00:05:36,620
Tretji algoritem
postane bolj učinkovita.

110
00:05:36,620 --> 00:05:40,120
Gre za dejansko 40% -
ali 60% večjo učinkovitost.

111
00:05:40,120 --> 00:05:41,580
To traja 40%, se znesek časa.

112
00:05:41,580 --> 00:05:45,250
To lahko run-- lahko traja
400 enot sredstev

113
00:05:45,250 --> 00:05:47,570
obdelati podatkovnega niza velikosti 10.

114
00:05:47,570 --> 00:05:49,410
Ker prva
algoritem, nasprotno,

115
00:05:49,410 --> 00:05:54,520
je 1.000 enot virov
obdelati podatkovnega niza velikosti 10.

116
00:05:54,520 --> 00:05:57,240
Ampak poglej kaj se zgodi,
naše številke dobil še večji.

117
00:05:57,240 --> 00:05:59,500
>> Sedaj pa razlika
med temi algoritmov

118
00:05:59,500 --> 00:06:01,420
začeli, da postanejo malo manj očitna.

119
00:06:01,420 --> 00:06:04,560
In dejstvo, da obstajajo
nižji-order terms-- ali bolje,

120
00:06:04,560 --> 00:06:09,390
izrazi z nižjo exponents--
začeli, da postanejo nepomembni.

121
00:06:09,390 --> 00:06:12,290
Če je podatkovni niz z velikostjo
1000 in prvi algoritem

122
00:06:12,290 --> 00:06:14,170
teče čez milijardo korakih.

123
00:06:14,170 --> 00:06:17,880
In drugi algoritem teče v
milijarda in milijon korakov.

124
00:06:17,880 --> 00:06:20,870
In tretji algoritem teče
v samo sramežljiv milijarde korakov.

125
00:06:20,870 --> 00:06:22,620
To je precej milijarde korakov.

126
00:06:22,620 --> 00:06:25,640
Ti pogoji nižje naročilo začetek
resnično postala nepomembna.

127
00:06:25,640 --> 00:06:27,390
In samo, da bo res
kladivo domov Point--

128
00:06:27,390 --> 00:06:31,240
če vhodni podatki dimenzionirati
million-- vse tri od teh precej

129
00:06:31,240 --> 00:06:34,960
vzemite eno quintillion-- če
Moja matematika correct-- koraki

130
00:06:34,960 --> 00:06:37,260
obdelati vnos podatkov
velikosti milijona.

131
00:06:37,260 --> 00:06:38,250
To je veliko korakov.

132
00:06:38,250 --> 00:06:42,092
In dejstvo, da je eden od njih lahko
traja nekaj 100.000 ali nekaj 100

133
00:06:42,092 --> 00:06:44,650
milijonov še manj, kadar
govorimo o številnih

134
00:06:44,650 --> 00:06:46,990
da big-- je nekako nepomembno.

135
00:06:46,990 --> 00:06:50,006
Vsi težijo, da sprejmejo
približno n kubikov,

136
00:06:50,006 --> 00:06:52,380
in zato bi se dejansko nanašajo
vseh teh algoritmov

137
00:06:52,380 --> 00:06:59,520
kot velikostnega reda n
kubikov ali big-O n kubični.

138
00:06:59,520 --> 00:07:03,220
>> Tukaj je seznam nekaterih bolj
skupna računska kompleksnost razredi

139
00:07:03,220 --> 00:07:05,820
da bomo naleteli na
algoritmi, na splošno.

140
00:07:05,820 --> 00:07:07,970
In prav posebej v CS50.

141
00:07:07,970 --> 00:07:11,410
Te so razvrščene od
splošno najhitrejši na vrhu,

142
00:07:11,410 --> 00:07:13,940
na splošno najpočasnejša na dnu.

143
00:07:13,940 --> 00:07:16,920
Torej konstanten čas algoritmov nagibajo
biti najhitrejši, ne glede

144
00:07:16,920 --> 00:07:19,110
velikosti od
vhodni podatki se boste peljali v.

145
00:07:19,110 --> 00:07:23,760
Vedno vzemite eno operacijo ali
ena enota sredstev za reševanje.

146
00:07:23,760 --> 00:07:25,730
Morda bi bilo 2, bi bilo
lahko 3, morda 4.

147
00:07:25,730 --> 00:07:26,910
Vendar je konstantno število.

148
00:07:26,910 --> 00:07:28,400
To se ne spreminja.

149
00:07:28,400 --> 00:07:31,390
>> Logaritemski čas algoritmov
so nekoliko boljši.

150
00:07:31,390 --> 00:07:33,950
In res dober primer
logaritemski čas algoritem

151
00:07:33,950 --> 00:07:37,420
da ste zagotovo videli do sedaj, je
odtrgate telefonskega imenika

152
00:07:37,420 --> 00:07:39,480
najti Mike Smith v telefonskem imeniku.

153
00:07:39,480 --> 00:07:40,980
Cut smo problem na pol.

154
00:07:40,980 --> 00:07:43,580
In tako, kot n dobi večji
in večje in larger--

155
00:07:43,580 --> 00:07:47,290
v resnici, vsakič, ko podvojilo
n, je samo še en korak.

156
00:07:47,290 --> 00:07:49,770
Tako, da je veliko bolje,
kot, recimo, linearni čas.

157
00:07:49,770 --> 00:07:53,030
Ki je, če ste dvakrat n je
je dvojno število korakov.

158
00:07:53,030 --> 00:07:55,980
Če potrojiti n, je potrebno
potrojiti število korakov.

159
00:07:55,980 --> 00:07:58,580
En korak na enoto.

160
00:07:58,580 --> 00:08:01,790
>> Potem pa se stvari malo more--
Malo manj super od tam.

161
00:08:01,790 --> 00:08:06,622
Imate linearno ritmično časa, včasih
imenovani dnevnik linearni čas ali pa samo n log n.

162
00:08:06,622 --> 00:08:08,330
In bomo zgled
od algoritma, ki

163
00:08:08,330 --> 00:08:13,370
teče v n log n, ki je še vedno bolje
kot kvadratna time-- n kvadrat.

164
00:08:13,370 --> 00:08:17,320
Ali polinom čas, n dva
poljubno število večje od dve.

165
00:08:17,320 --> 00:08:20,810
Ali eksponentna čas, ki
Še worse-- C do n.

166
00:08:20,810 --> 00:08:24,670
Tako nekateri konstantno število dvigne na
Moč velikosti vhoda.

167
00:08:24,670 --> 00:08:28,990
Torej, če je 1,000-- Če
vhodni podatki velikosti 1000,

168
00:08:28,990 --> 00:08:31,310
da bi potrebovali C do 1,000th moči.

169
00:08:31,310 --> 00:08:33,559
To je veliko slabše, kot polinomskem casu.

170
00:08:33,559 --> 00:08:35,030
>> Faktorski čas je še slabše.

171
00:08:35,030 --> 00:08:37,760
In v resnici, je res
obstajajo neskončne čas algoritmov,

172
00:08:37,760 --> 00:08:43,740
kot so ti neumen sort-- katerih
naloga je, da naključno shuffle array

173
00:08:43,740 --> 00:08:45,490
in nato preverite,
ali je to urejeno.

174
00:08:45,490 --> 00:08:47,589
In če to ni naključno
ponovno shuffle array

175
00:08:47,589 --> 00:08:49,130
in preverite, ali je to urejeno.

176
00:08:49,130 --> 00:08:51,671
In kot si verjetno lahko imagine--
si lahko predstavljate situacijo

177
00:08:51,671 --> 00:08:55,200
kjer je v najslabšem primeru, da bo
Nikoli dejansko začeli s paleto.

178
00:08:55,200 --> 00:08:57,150
Ta algoritem bi teči večno.

179
00:08:57,150 --> 00:08:59,349
In tako, da bi bila
neskončno časa algoritem.

180
00:08:59,349 --> 00:09:01,890
Upajmo, da ne bo pisal
vsaka faktorsko ali neskončna čas

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

182
00:09:04,510 --> 00:09:09,150
>> Torej, vzemimo malo več
beton pogled na nekatere enostavnejše

183
00:09:09,150 --> 00:09:11,154
računski kompleksnost razredi.

184
00:09:11,154 --> 00:09:13,070
Torej imamo example--
ali dva primera here--

185
00:09:13,070 --> 00:09:15,590
konstantnih časovnih algoritmov,
ki vedno

186
00:09:15,590 --> 00:09:17,980
ena operacija v najslabšem primeru.

187
00:09:17,980 --> 00:09:20,050
Torej, prvi example--
imamo funkcijo

188
00:09:20,050 --> 00:09:23,952
pozval 4 za vas, ki
prevzame paleto velikosti 1.000.

189
00:09:23,952 --> 00:09:25,660
Ampak potem očitno
dejansko ne videti

190
00:09:25,660 --> 00:09:29,000
na ne it-- res ne zanima, kaj je
znotraj njega, od tega niza.

191
00:09:29,000 --> 00:09:30,820
Vedno vrne ravno štiri.

192
00:09:30,820 --> 00:09:32,940
Torej, da je algoritem,
kljub dejstvu, da je

193
00:09:32,940 --> 00:09:35,840
je 1.000 elementov ne
storiti ničesar z njimi.

194
00:09:35,840 --> 00:09:36,590
Samo vrne štiri.

195
00:09:36,590 --> 00:09:38,240
To je vedno en sam korak.

196
00:09:38,240 --> 00:09:41,600
>> V bistvu, dodamo 2 nums-- ki
smo videli prej kot well--

197
00:09:41,600 --> 00:09:43,680
samo obdeluje dve celi števili.

198
00:09:43,680 --> 00:09:44,692
To ni en sam korak.

199
00:09:44,692 --> 00:09:45,900
To je pravzaprav nekaj korakov.

200
00:09:45,900 --> 00:09:50,780
Dobiš, dobiš b, jih dodate
skupaj, in ti izhodne rezultate.

201
00:09:50,780 --> 00:09:53,270
Torej, to je 84 korakov.

202
00:09:53,270 --> 00:09:55,510
Ampak to je vedno konstantna,
glede na to, a ali b.

203
00:09:55,510 --> 00:09:59,240
Imate, da bi dobili, dobili b, dodajte
jih skupaj, izhodni rezultat.

204
00:09:59,240 --> 00:10:02,900
Torej, to je stalnica, ko algoritem.

205
00:10:02,900 --> 00:10:05,170
>> Tukaj je primer
linearni čas algorithm--

206
00:10:05,170 --> 00:10:08,740
algoritem, ki gets--, ki traja
en dodaten korak, morebiti

207
00:10:08,740 --> 00:10:10,740
kot je vaš vnos raste s 1.

208
00:10:10,740 --> 00:10:14,190
Torej, recimo, da iščemo
število 5 znotraj matrike.

209
00:10:14,190 --> 00:10:16,774
Morda imate situacijo, v kateri
lahko zdi dokaj zgodaj.

210
00:10:16,774 --> 00:10:18,606
Vendar bi lahko imeli tudi
razmere, v katerih je

211
00:10:18,606 --> 00:10:20,450
lahko zadnji element matrike.

212
00:10:20,450 --> 00:10:23,780
V paleto velikosti 5, če
iščemo za številko 5.

213
00:10:23,780 --> 00:10:25,930
To bi trajalo 5 korakov.

214
00:10:25,930 --> 00:10:29,180
In v resnici, si predstavljajte, da obstaja
Ne 5 kjerkoli v tem polju.

215
00:10:29,180 --> 00:10:32,820
Še vedno dejansko morali pogledati
vsak element matrike

216
00:10:32,820 --> 00:10:35,550
da bi določili
ali 5 obstaja.

217
00:10:35,550 --> 00:10:39,840
>> Torej v najslabšem primeru, to je, da
element je zadnji v matriki

218
00:10:39,840 --> 00:10:41,700
ali ne obstaja sploh.

219
00:10:41,700 --> 00:10:44,690
Še vedno moramo gledati
vse n elementov.

220
00:10:44,690 --> 00:10:47,120
In tako je ta algoritem
teče v linearnem času.

221
00:10:47,120 --> 00:10:50,340
Lahko potrdite, da jo
ekstrapolacijo malo z besedami,

222
00:10:50,340 --> 00:10:53,080
če bi imeli niz 6-element in
smo iskali številko 5,

223
00:10:53,080 --> 00:10:54,890
to lahko traja 6 korakov.

224
00:10:54,890 --> 00:10:57,620
Če imamo niz 7-element in
iščemo za številko 5.

225
00:10:57,620 --> 00:10:59,160
To lahko traja 7 korakov.

226
00:10:59,160 --> 00:11:02,920
Kot smo dodali še en element za naše
matrika, ki je potreben še en korak.

227
00:11:02,920 --> 00:11:06,750
To je linearni algoritem
v najslabšem primeru.

228
00:11:06,750 --> 00:11:08,270
>> Par hitrih vprašanj za vas.

229
00:11:08,270 --> 00:11:11,170
Kaj je runtime-- kaj je
najslabšim runtime

230
00:11:11,170 --> 00:11:13,700
tega posebnega odrezka kode?

231
00:11:13,700 --> 00:11:17,420
Torej imam 4 zanke tukaj, da teče
od j enak 0, vso pot do m.

232
00:11:17,420 --> 00:11:21,980
In tisto, kar sem tukaj vidim, je, da je
Telo zanke deluje v stalnem času.

233
00:11:21,980 --> 00:11:24,730
Torej, z uporabo terminologije
smo že govorili about-- kaj

234
00:11:24,730 --> 00:11:29,390
bi bilo v najslabšem primeru
runtime tega algoritma?

235
00:11:29,390 --> 00:11:31,050
Vzemite si trenutek.

236
00:11:31,050 --> 00:11:34,270
Notranji del zanke
teče v stalnem času.

237
00:11:34,270 --> 00:11:37,510
In zunanji del
zanka se bo teči m-krat.

238
00:11:37,510 --> 00:11:40,260
Torej, kaj je runtime najslabšem primeru tukaj?

239
00:11:40,260 --> 00:11:43,210
Ali uganete, Big-O za m?

240
00:11:43,210 --> 00:11:44,686
Ti bi bilo prav.

241
00:11:44,686 --> 00:11:46,230
>> Kaj pa drugo?

242
00:11:46,230 --> 00:11:48,590
Tokrat imamo
zanka znotraj zanke.

243
00:11:48,590 --> 00:11:50,905
Imamo zunanjo zanko
ki teče od nič do str.

244
00:11:50,905 --> 00:11:54,630
In imamo notranjo zanko, ki teče
od nič do p, in znotraj tega,

245
00:11:54,630 --> 00:11:57,890
Izjavljam, da je telo
zanka teče v stalnem času.

246
00:11:57,890 --> 00:12:02,330
Torej, kaj je runtime najslabšem primeru
tega posebnega odrezka kode?

247
00:12:02,330 --> 00:12:06,140
No, še enkrat, imamo
zunanjo zanko, ki teče p-krat.

248
00:12:06,140 --> 00:12:09,660
In vsaka time-- ponovitev
navedene zanke, ne.

249
00:12:09,660 --> 00:12:13,170
Imamo notranjo zanko
ki teče tudi p-krat.

250
00:12:13,170 --> 00:12:16,900
In potem znotraj tega, tam je
stalna time-- mali košček tam.

251
00:12:16,900 --> 00:12:19,890
>> Torej, če imamo zunanja zanka, ki
teče p-krat znotraj katerega je

252
00:12:19,890 --> 00:12:22,880
notranjo zanko, da
teče p times-- kaj je

253
00:12:22,880 --> 00:12:26,480
najslabšim runtime
tega odrezka kode?

254
00:12:26,480 --> 00:12:30,730
Ali uganete, big-O p na kvadrat?

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

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

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