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

2
00:00:05,830 --> 00:00:07,910
>> U redu, pa, računalna složenost.

3
00:00:07,910 --> 00:00:10,430
Samo malo upozorenje
Prije nego što zaronite u previše far--

4
00:00:10,430 --> 00:00:13,070
to vjerojatno će biti među
Najviše math-teških stvari

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

6
00:00:14,200 --> 00:00:16,950
Nadam se da neće biti previše neodoljiv
a mi ćemo pokušati vas

7
00:00:16,950 --> 00:00:19,200
kroz proces, ali
Samo malo fer upozorenje.

8
00:00:19,200 --> 00:00:21,282
Tu je malo
matematike koji su uključeni ovdje.

9
00:00:21,282 --> 00:00:23,990
U redu, tako da bi se napraviti
korištenje naših računalnih resursa

10
00:00:23,990 --> 00:00:28,170
u stvarnom svijet-to je stvarno
važno razumjeti algoritme

11
00:00:28,170 --> 00:00:30,750
i kako su obradu podataka.

12
00:00:30,750 --> 00:00:32,810
Ako smo doista
učinkovit algoritam, mi

13
00:00:32,810 --> 00:00:36,292
može smanjiti količinu resursa
imamo na raspolaganju kako bi se bavio s njom.

14
00:00:36,292 --> 00:00:38,750
Ako imamo algoritam koji
će potrajati puno posla

15
00:00:38,750 --> 00:00:41,210
obraditi stvarno
veliki skup podataka, to je

16
00:00:41,210 --> 00:00:44,030
će zahtijevati više
i više sredstava,

17
00:00:44,030 --> 00:00:47,980
je novac, RAM, sve to vrsta stvari.

18
00:00:47,980 --> 00:00:52,090
>> Dakle, biti u mogućnosti analizirati
Algoritam koristeći ovaj alat set,

19
00:00:52,090 --> 00:00:56,110
osnovi, pita question--
Kako ovo algoritam razmjera

20
00:00:56,110 --> 00:00:59,020
kao što smo baciti sve više i više podataka na njemu?

21
00:00:59,020 --> 00:01:02,220
U CS50, količinu podataka smo
rad s prilično mala.

22
00:01:02,220 --> 00:01:05,140
Općenito, naši programi idu
prikazivati ​​u drugi ili less--

23
00:01:05,140 --> 00:01:07,830
Vjerojatno puno manje
Posebno rano.

24
00:01:07,830 --> 00:01:12,250
>> Ali razmišljam o tvrtka koja se bavi
sa stotinama milijuna kupaca.

25
00:01:12,250 --> 00:01:14,970
I oni moraju obraditi
da kupac podataka.

26
00:01:14,970 --> 00:01:18,260
Kako je broj kupaca se
imaju dobiva veći i veći,

27
00:01:18,260 --> 00:01:21,230
to će zahtijevati
sve više i više resursa.

28
00:01:21,230 --> 00:01:22,926
Koliko više resursa?

29
00:01:22,926 --> 00:01:25,050
Pa, to ovisi o tome kako
analiziramo algoritam,

30
00:01:25,050 --> 00:01:28,097
pomoću alata u ovom alata.

31
00:01:28,097 --> 00:01:31,180
Kada govorimo o složenosti
algorithm-- koji Ponekad ćete

32
00:01:31,180 --> 00:01:34,040
čuti što se naziva vrijeme
složenosti ili prostora složenost

33
00:01:34,040 --> 00:01:36,190
ali mi jednostavno ide
nazvati complexity--

34
00:01:36,190 --> 00:01:38,770
mi općenito govorimo o
najgori scenarij.

35
00:01:38,770 --> 00:01:42,640
S obzirom na apsolutno najgore hrpa
Podaci koje smo mogli biti bacanje na to,

36
00:01:42,640 --> 00:01:46,440
kako je to algoritam će
obraditi ili se bave s tim podacima?

37
00:01:46,440 --> 00:01:51,450
Mi obično nazivamo najgorem slučaju
Runtime algoritma big-O.

38
00:01:51,450 --> 00:01:56,770
Dakle, algoritam se može reći da
izvoditi u O n ili O n na kvadrat.

39
00:01:56,770 --> 00:01:59,110
A više o tome što
one znače u sekundi.

40
00:01:59,110 --> 00:02:01,620
>> Ponekad, međutim, mi njegu
o najboljem scenariju.

41
00:02:01,620 --> 00:02:05,400
Ako podaci sve što smo htjeli
da se i to je apsolutno savršena

42
00:02:05,400 --> 00:02:09,630
i bili smo slanje ovo savršena
skup podataka putem našeg algoritma.

43
00:02:09,630 --> 00:02:11,470
Kako bi se nositi u toj situaciji?

44
00:02:11,470 --> 00:02:15,050
Ponekad se odnosi na to što je
velika Omega, tako da je u suprotnosti s velikom-O,

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

46
00:02:16,530 --> 00:02:18,880
Big-Omega za najboljem scenariju.

47
00:02:18,880 --> 00:02:21,319
Big-O za najgorem slučaju.

48
00:02:21,319 --> 00:02:23,860
Općenito, kada govorimo o
složenost algoritma,

49
00:02:23,860 --> 00:02:26,370
govorimo o
najgorem slučaju.

50
00:02:26,370 --> 00:02:28,100
Pa imajte to na umu.

51
00:02:28,100 --> 00:02:31,510
>> A u ovoj klasi, mi općenito ide
napustiti strogu analizu stranu.

52
00:02:31,510 --> 00:02:35,350
Postoje znanosti i polja
posvećen ove vrste stvari.

53
00:02:35,350 --> 00:02:37,610
Kada govorimo o zaključivanju
kroz algoritme,

54
00:02:37,610 --> 00:02:41,822
što ćemo činiti dio-po-dio za mnoge
Algoritmi govorimo o u klasi.

55
00:02:41,822 --> 00:02:44,780
Mi smo zapravo samo govori o
razmišljanje kroz njega sa zdravim razumom,

56
00:02:44,780 --> 00:02:47,070
ne s formulama, ili dokaze,
ili bilo što slično.

57
00:02:47,070 --> 00:02:51,600
Dakle, ne brinite, nećemo biti
pretvara u velikom satu matematike.

58
00:02:51,600 --> 00:02:55,920
>> Zato sam rekao da je stalo složenosti
jer postavlja pitanje, kako

59
00:02:55,920 --> 00:03:00,160
ne naši algoritmi nositi veći i
veće setovi podataka koji se baca na njih.

60
00:03:00,160 --> 00:03:01,960
Pa, što je skup podataka?

61
00:03:01,960 --> 00:03:03,910
Što mislim kada sam rekao da je?

62
00:03:03,910 --> 00:03:07,600
To znači da sve što čini većinu
smisla u kontekstu, da budem iskren.

63
00:03:07,600 --> 00:03:11,160
Ako imamo algoritam, na
Procesi Strings-- smo vjerojatno

64
00:03:11,160 --> 00:03:13,440
govori o veličini niza.

65
00:03:13,440 --> 00:03:15,190
To su podaci set--
veličina, broj

66
00:03:15,190 --> 00:03:17,050
znakova koji čine niz.

67
00:03:17,050 --> 00:03:20,090
Ako govorimo o
algoritam koji obrađuje datoteke,

68
00:03:20,090 --> 00:03:23,930
bismo mogli razgovarati o tome kako
mnogi kilobajta sadrže tu datoteku.

69
00:03:23,930 --> 00:03:25,710
I to je skup podataka.

70
00:03:25,710 --> 00:03:28,870
Ako govorimo o algoritmu
koje obrađuje polja općenito,

71
00:03:28,870 --> 00:03:31,510
kao što su sortiranje algoritama
ili u potrazi algoritama,

72
00:03:31,510 --> 00:03:36,690
vjerojatno govorimo o broju
elemenata koji čine niz.

73
00:03:36,690 --> 00:03:39,272
>> Sada, možemo mjeriti
algorithm-- posebno,

74
00:03:39,272 --> 00:03:40,980
kad kažem možemo
mjerenje algoritam, ja

75
00:03:40,980 --> 00:03:43,840
znači možemo mjeriti koliko
mnogo resursa zauzima.

76
00:03:43,840 --> 00:03:48,990
Jesu li ti resursi su, koliko
bajtova RAM-- ili megabajta RAM

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

78
00:03:49,790 --> 00:03:52,320
Ili koliko vremena je potrebno za pokretanje.

79
00:03:52,320 --> 00:03:56,200
I možemo zvati
mjerenje, samovoljno, f n.

80
00:03:56,200 --> 00:03:59,420
Pri čemu je n broj
elementi u skupu podataka.

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

82
00:04:02,640 --> 00:04:07,530
Koliko jedinica resursa radi
to zahtijevaju obraditi te podatke.

83
00:04:07,530 --> 00:04:10,030
>> Sada, mi zapravo nije briga
što f n je točno.

84
00:04:10,030 --> 00:04:13,700
U stvari, mi smo vrlo rijetko will--
sigurno nikada neće u ovoj class-- I.

85
00:04:13,700 --> 00:04:18,709
zaroniti u bilo stvarno duboko
Analiza ono f n.

86
00:04:18,709 --> 00:04:23,510
Samo ćemo razgovarati o tome što f
nje otprilike i što je sklon.

87
00:04:23,510 --> 00:04:27,600
A tendencija algoritam je
diktiraju najvišoj narudžbe pojam.

88
00:04:27,600 --> 00:04:29,440
I možemo vidjeti što sam
znači po tome uzimajući

89
00:04:29,440 --> 00:04:31,910
Pogled na konkretniji primjer.

90
00:04:31,910 --> 00:04:34,620
>> Dakle, recimo da imamo
tri različite algoritme.

91
00:04:34,620 --> 00:04:39,350
Od kojih je prvi uklanja n
kubu, neke jedinice resursa

92
00:04:39,350 --> 00:04:42,880
obraditi skup podataka veličine n.

93
00:04:42,880 --> 00:04:47,000
Imamo drugi algoritam koji uzima
n kubu plus n kvadratna resursi

94
00:04:47,000 --> 00:04:49,350
obraditi skup podataka veličine n.

95
00:04:49,350 --> 00:04:52,030
I mi smo treća
algoritam koji radi in-- da

96
00:04:52,030 --> 00:04:58,300
zauzima n kubu minus 8N kvadrat
plus 20 n jedinica resursa

97
00:04:58,300 --> 00:05:02,370
obraditi algoritam
s podacima skupa veličine n.

98
00:05:02,370 --> 00:05:05,594
>> Sada opet, mi stvarno ne ide
da se u ovoj razini detalja.

99
00:05:05,594 --> 00:05:08,260
Ja sam stvarno samo ove gore
ovdje kao ilustracija točke

100
00:05:08,260 --> 00:05:10,176
da ću biti
što u sekundi, što

101
00:05:10,176 --> 00:05:12,980
je da mi je samo stalo
o tendencijom stvari

102
00:05:12,980 --> 00:05:14,870
kao setovi podataka dobiti veći.

103
00:05:14,870 --> 00:05:18,220
Dakle, ako skup podataka je mala, ima
zapravo prilično velika razlika

104
00:05:18,220 --> 00:05:19,870
u tim algoritmima.

105
00:05:19,870 --> 00:05:23,000
Treći algoritam tamo
traje 13 puta duže,

106
00:05:23,000 --> 00:05:27,980
13 puta iznos sredstava
za pokretanje u odnosu na prvi.

107
00:05:27,980 --> 00:05:31,659
>> Ako je naš skup podataka je veličina 10, koji
je veća, ali ne nužno velika,

108
00:05:31,659 --> 00:05:33,950
možemo vidjeti da postoji
zapravo malo razlika.

109
00:05:33,950 --> 00:05:36,620
Treći algoritam
postaje učinkovitija.

110
00:05:36,620 --> 00:05:40,120
To je oko 40% zapravo -
ili 60% učinkovitiji.

111
00:05:40,120 --> 00:05:41,580
Potrebno 40% u iznosu od vremena.

112
00:05:41,580 --> 00:05:45,250
To može run-- to može potrajati
400 jedinica resursa

113
00:05:45,250 --> 00:05:47,570
obraditi skup podataka veličine 10.

114
00:05:47,570 --> 00:05:49,410
A prvi
Algoritam, za razliku od,

115
00:05:49,410 --> 00:05:54,520
Potrebno 1.000 jedinica resursa
obraditi skup podataka veličine 10.

116
00:05:54,520 --> 00:05:57,240
Ali pogledajte što se događa dok
naši brojevi dobili još veći.

117
00:05:57,240 --> 00:05:59,500
>> Sad, razlika
između tih algoritama

118
00:05:59,500 --> 00:06:01,420
početi postati malo manje očiti.

119
00:06:01,420 --> 00:06:04,560
A činjenica da postoje
nižeg reda terms-- odnosno,

120
00:06:04,560 --> 00:06:09,390
Pojmovi s nižim exponents--
početi postati irelevantna.

121
00:06:09,390 --> 00:06:12,290
Ako je skup podaci o veličini
1000 i prvi algoritam

122
00:06:12,290 --> 00:06:14,170
radi u milijardu koraka.

123
00:06:14,170 --> 00:06:17,880
I drugi algoritam radi u
milijardu i milijun koraka.

124
00:06:17,880 --> 00:06:20,870
A treći algoritam radi
u samo sramiti milijardu koraka.

125
00:06:20,870 --> 00:06:22,620
To je prilično puno milijardu koraka.

126
00:06:22,620 --> 00:06:25,640
Ti pojmovi nižeg reda početak
postati doista nevažno.

127
00:06:25,640 --> 00:06:27,390
I samo da se stvarno
čekić kući point--

128
00:06:27,390 --> 00:06:31,240
ako su ulazni podaci o veličini a
million-- sve tri od njih prilično

129
00:06:31,240 --> 00:06:34,960
uzeti jedan quintillion-- ako
moja matematika correct-- koraka

130
00:06:34,960 --> 00:06:37,260
obraditi unos podataka
veličine milijuna.

131
00:06:37,260 --> 00:06:38,250
To je mnogo koraka.

132
00:06:38,250 --> 00:06:42,092
A činjenica da je jedan od njih možda
potrajati nekoliko 100,000 ili par 100

133
00:06:42,092 --> 00:06:44,650
milijuna još manje kada
govorimo o broju

134
00:06:44,650 --> 00:06:46,990
da big-- to je vrsta nevažno.

135
00:06:46,990 --> 00:06:50,006
Svi oni imaju tendenciju da se
oko nje kubu,

136
00:06:50,006 --> 00:06:52,380
pa bismo se zapravo odnosi
svim tim algoritama

137
00:06:52,380 --> 00:06:59,520
kao na red n
kubu ili velika-O n kubu.

138
00:06:59,520 --> 00:07:03,220
>> Ovdje je popis nekih od više
zajedničke računalne složenosti klasa

139
00:07:03,220 --> 00:07:05,820
da ćemo se susresti u
algoritmi općenito.

140
00:07:05,820 --> 00:07:07,970
I također posebno u CS50.

141
00:07:07,970 --> 00:07:11,410
Oni su naručili od
obično najbrži na vrhu,

142
00:07:11,410 --> 00:07:13,940
općenito najsporije na dnu.

143
00:07:13,940 --> 00:07:16,920
Dakle, konstantna vremena algoritmi često
biti najbrži, bez obzira na

144
00:07:16,920 --> 00:07:19,110
veličine od
unos podataka prođe u.

145
00:07:19,110 --> 00:07:23,760
Oni uvijek uzeti jednu operaciju ili
jedna jedinica resursa da se bave.

146
00:07:23,760 --> 00:07:25,730
To bi moglo biti 2, to bi moglo
biti 3, to bi moglo biti 4.

147
00:07:25,730 --> 00:07:26,910
No, to je konstantni broj.

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

149
00:07:28,400 --> 00:07:31,390
>> Logaritamska vrijeme algoritmi
su nešto bolje.

150
00:07:31,390 --> 00:07:33,950
I stvarno dobar primjer
logaritamska vrijeme algoritam

151
00:07:33,950 --> 00:07:37,420
sigurno ste vidjeli do sada je
razdire od telefonskog imenika

152
00:07:37,420 --> 00:07:39,480
naći Mike Smith u telefonskom imeniku.

153
00:07:39,480 --> 00:07:40,980
Snizili smo problema na pola.

154
00:07:40,980 --> 00:07:43,580
I tako je n dobiva veći
i veći i larger--

155
00:07:43,580 --> 00:07:47,290
Zapravo, svaki put kada se udvostručiti
nje, to traje samo još jedan korak.

156
00:07:47,290 --> 00:07:49,770
Dakle, to je puno bolje
nego, recimo, linearno vrijeme.

157
00:07:49,770 --> 00:07:53,030
Koji je ako udvostručite nje, ona
vodi dvostruki broj koraka.

158
00:07:53,030 --> 00:07:55,980
Ako utrostručiti nje, to traje
utrostručiti broj koraka.

159
00:07:55,980 --> 00:07:58,580
Jedan korak po jedinici.

160
00:07:58,580 --> 00:08:01,790
>> Tada se stvari malo more--
malo manje sjajno od tamo.

161
00:08:01,790 --> 00:08:06,622
Imate linearno ritmičke vremena, ponekad
zove dnevnik linearno vrijeme ili samo n prijavite n.

162
00:08:06,622 --> 00:08:08,330
A mi ćemo kao primjer
algoritma koji

163
00:08:08,330 --> 00:08:13,370
radi u n log n, što je još bolje
od kvadratnog time-- n na kvadrat.

164
00:08:13,370 --> 00:08:17,320
Ili polinom vrijeme, n dva
bilo koji broj veći od dva.

165
00:08:17,320 --> 00:08:20,810
Ili eksponencijalna vrijeme, koje
još worse-- C u n.

166
00:08:20,810 --> 00:08:24,670
Tako su neki konstantni broj povećan na
moć veličine ulaza.

167
00:08:24,670 --> 00:08:28,990
Dakle, ako postoji 1,000-- ako mu je
ulazni podaci veličine 1000,

168
00:08:28,990 --> 00:08:31,310
to bi se C do 1,000th vlast.

169
00:08:31,310 --> 00:08:33,559
To je puno gore nego polinomnom vrijeme.

170
00:08:33,559 --> 00:08:35,030
>> Faktorijalni vrijeme je još gore.

171
00:08:35,030 --> 00:08:37,760
A u stvari, ima zaista
Postoje beskonačni put algoritama,

172
00:08:37,760 --> 00:08:43,740
kao što je tzv glupo sort-- čija
posao je slučajno shuffle niz

173
00:08:43,740 --> 00:08:45,490
a zatim provjerite je li
je li to riješeno.

174
00:08:45,490 --> 00:08:47,589
A ako to nije, slučajno
opet vrpoljiti niz

175
00:08:47,589 --> 00:08:49,130
i provjerite da li je to riješeno.

176
00:08:49,130 --> 00:08:51,671
I kao što vjerojatno možete imagine--
možete zamisliti situaciju

177
00:08:51,671 --> 00:08:55,200
gdje je u najgorem slučaju, da će
Nikad zapravo početi s nizom.

178
00:08:55,200 --> 00:08:57,150
To algoritam će se izvoditi zauvijek.

179
00:08:57,150 --> 00:08:59,349
A kako bi bilo
beskonačan put algoritam.

180
00:08:59,349 --> 00:09:01,890
Nadam se da se neće pisati
bilo faktorijalni ili beskonačan vrijeme

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

182
00:09:04,510 --> 00:09:09,150
>> Dakle, neka je uzeti malo više
beton pogled na neke jednostavnije

183
00:09:09,150 --> 00:09:11,154
računske složenosti klasa.

184
00:09:11,154 --> 00:09:13,070
Dakle, imamo example--
ili dva primjera here--

185
00:09:13,070 --> 00:09:15,590
stalnih vremenskih algoritama,
koji uvijek uzeti

186
00:09:15,590 --> 00:09:17,980
jedan rad u najgorem slučaju.

187
00:09:17,980 --> 00:09:20,050
Dakle, prvi example--
imamo funkciju

188
00:09:20,050 --> 00:09:23,952
pozvao 4 za vas, koji
traje niz veličine 1.000.

189
00:09:23,952 --> 00:09:25,660
Ali onda očito
ne zapravo izgleda

190
00:09:25,660 --> 00:09:29,000
na it-- zapravo ne briga što je
unutar nje, te niz.

191
00:09:29,000 --> 00:09:30,820
Uvijek samo vraća četiri.

192
00:09:30,820 --> 00:09:32,940
Dakle, da je algoritam,
unatoč činjenici da se

193
00:09:32,940 --> 00:09:35,840
Potrebno 1.000 elemenata ne
ništa s njima.

194
00:09:35,840 --> 00:09:36,590
Samo vraća četiri.

195
00:09:36,590 --> 00:09:38,240
To je uvijek jedan korak.

196
00:09:38,240 --> 00:09:41,600
>> U stvari, dodati 2 nums-- koji
smo vidjeli kako je well--

197
00:09:41,600 --> 00:09:43,680
Samo obrađuje dva prirodna broja.

198
00:09:43,680 --> 00:09:44,692
To nije jedan korak.

199
00:09:44,692 --> 00:09:45,900
To je zapravo par koraka.

200
00:09:45,900 --> 00:09:50,780
Možete dobiti, dobivate B, možete ih dodati
zajedno, a vi izlazni rezultati.

201
00:09:50,780 --> 00:09:53,270
Tako da je 84 koraka.

202
00:09:53,270 --> 00:09:55,510
Ali to je uvijek konstantna,
Bez obzira na, ili b.

203
00:09:55,510 --> 00:09:59,240
Morate dobiti, dobiti b, dodajte
ih zajedno, izlazni rezultat.

204
00:09:59,240 --> 00:10:02,900
Dakle, to je konstanta vrijeme algoritam.

205
00:10:02,900 --> 00:10:05,170
>> Evo primjera od a
linearno vrijeme algorithm--

206
00:10:05,170 --> 00:10:08,740
algoritam koji gets-- da traje
jedan dodatni korak, eventualno,

207
00:10:08,740 --> 00:10:10,740
kao svoj ulaz raste za 1.

208
00:10:10,740 --> 00:10:14,190
Dakle, recimo da smo u potrazi za
broj 5 unutar niza.

209
00:10:14,190 --> 00:10:16,774
Možda ćete imati situaciju u kojoj
možete smatraju da je prilično rano.

210
00:10:16,774 --> 00:10:18,606
Ali, također mogu imati
situacija u kojoj je

211
00:10:18,606 --> 00:10:20,450
možda posljednji element niza.

212
00:10:20,450 --> 00:10:23,780
U nizu veličine 5, ako
mi smo u potrazi za broj 5.

213
00:10:23,780 --> 00:10:25,930
Bilo bi 5 koraka.

214
00:10:25,930 --> 00:10:29,180
A u stvari, zamislite da postoji
Nije 5 bilo gdje u tom nizu.

215
00:10:29,180 --> 00:10:32,820
Još uvijek zapravo pogledati
svaki element polja

216
00:10:32,820 --> 00:10:35,550
kako bi se utvrdilo
da li ili ne 5 je tu.

217
00:10:35,550 --> 00:10:39,840
>> Dakle, u najgorem slučaju, što je to
element je posljednja u nizu

218
00:10:39,840 --> 00:10:41,700
ili ne postoji uopće.

219
00:10:41,700 --> 00:10:44,690
Mi i dalje morati gledati na
sve n elemenata.

220
00:10:44,690 --> 00:10:47,120
I tako ovaj algoritam
radi u linearnom vremenu.

221
00:10:47,120 --> 00:10:50,340
Možete potvrditi da je
ekstrapoliranja malo govoreći,

222
00:10:50,340 --> 00:10:53,080
ako smo imali 6-element matrice A i
bili smo u potrazi za broj 5,

223
00:10:53,080 --> 00:10:54,890
to bi moglo potrajati 6 koraka.

224
00:10:54,890 --> 00:10:57,620
Ako imamo 7-element matrice A i
mi smo u potrazi za broj 5.

225
00:10:57,620 --> 00:10:59,160
To bi moglo potrajati 7 koraka.

226
00:10:59,160 --> 00:11:02,920
Kao što smo dodali još jedan element na naš
polje, potrebno je još jedan korak.

227
00:11:02,920 --> 00:11:06,750
To je linearni algoritam
u najgorem slučaju.

228
00:11:06,750 --> 00:11:08,270
>> Par brzih pitanja za vas.

229
00:11:08,270 --> 00:11:11,170
Što je runtime-- što je
najgorem slučaju izvođenja

230
00:11:11,170 --> 00:11:13,700
ovog posebnog isječak koda?

231
00:11:13,700 --> 00:11:17,420
Dakle, imam 4 petlje ovdje koji radi
od j = 0, pa sve do m.

232
00:11:17,420 --> 00:11:21,980
A ono što sam vidio ovdje, je da je
Tijelo petlje radi u stalnom vremenu.

233
00:11:21,980 --> 00:11:24,730
Dakle, koristite terminologiju koja
već smo razgovarali about-- što

234
00:11:24,730 --> 00:11:29,390
bi bio najgori slučaj
Runtime ovog algoritma?

235
00:11:29,390 --> 00:11:31,050
Uzmite trenutak.

236
00:11:31,050 --> 00:11:34,270
Unutarnji dio petlje
radi u stalnom vremenu.

237
00:11:34,270 --> 00:11:37,510
A vanjski dio od
Petlja će se izvoditi m puta.

238
00:11:37,510 --> 00:11:40,260
Dakle, što je najgori slučaj runtime ovdje?

239
00:11:40,260 --> 00:11:43,210
Jeste li pogoditi veliki-o m?

240
00:11:43,210 --> 00:11:44,686
Ti bi biti u pravu.

241
00:11:44,686 --> 00:11:46,230
>> Kako o drugom?

242
00:11:46,230 --> 00:11:48,590
Ovaj put imamo
petlje unutar petlje.

243
00:11:48,590 --> 00:11:50,905
Imamo vanjski petlju
koji traje od nula do str.

244
00:11:50,905 --> 00:11:54,630
I mi imamo unutarnji petlju koja teče
od nule do p, a unutar toga,

245
00:11:54,630 --> 00:11:57,890
Tvrdim da je tijelo
petlje radi u stalnom vremenu.

246
00:11:57,890 --> 00:12:02,330
Dakle, što je najgori slučaj izvođenja
ovog posebnog isječak koda?

247
00:12:02,330 --> 00:12:06,140
Pa, opet, imamo
Vanjska petlja koja teče str puta.

248
00:12:06,140 --> 00:12:09,660
I svaki time-- iteracija
tog procesa, a.

249
00:12:09,660 --> 00:12:13,170
Imamo unutarnju petlju
koje također vodi p puta.

250
00:12:13,170 --> 00:12:16,900
I onda unutar toga, tu je i
stalna time-- mali isječak postoji.

251
00:12:16,900 --> 00:12:19,890
>> Dakle, ako imamo vanjski petlje da
radi se p puta unutar kojih je

252
00:12:19,890 --> 00:12:22,880
unutarnja petlja koja
radi p times-- ono što je

253
00:12:22,880 --> 00:12:26,480
najgorem slučaju izvođenja
ove isječak koda?

254
00:12:26,480 --> 00:12:30,730
Jeste li pogoditi velika O p kvadrat?

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

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

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