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

2
00:00:05,830 --> 00:00:07,910
>> Greit, så, beregningsorientert kompleksitet.

3
00:00:07,910 --> 00:00:10,430
Bare litt av en advarsel
før vi dykker i for far--

4
00:00:10,430 --> 00:00:13,070
Dette vil trolig være blant
de matematiske-tunge ting

5
00:00:13,070 --> 00:00:14,200
vi snakker om i CS50.

6
00:00:14,200 --> 00:00:16,950
Forhåpentligvis vil det ikke bli for overveldende
og vi skal prøve å veilede deg

7
00:00:16,950 --> 00:00:19,200
gjennom prosessen, men
bare en bit av en rettferdig advarsel.

8
00:00:19,200 --> 00:00:21,282
Det er litt
matematikk involvert her.

9
00:00:21,282 --> 00:00:23,990
Greit, så for å gjøre
bruk av våre beregningsressurser

10
00:00:23,990 --> 00:00:28,170
i den virkelige world-- er det virkelig
viktig å forstå algoritmer

11
00:00:28,170 --> 00:00:30,750
og hvordan de behandler data.

12
00:00:30,750 --> 00:00:32,810
Hvis vi har en virkelig
effektiv algoritme, vi

13
00:00:32,810 --> 00:00:36,292
kan minimere mengden av ressurser
vi har tilgjengelig for å håndtere det.

14
00:00:36,292 --> 00:00:38,750
Hvis vi har en algoritme som
kommer til å ta mye arbeid

15
00:00:38,750 --> 00:00:41,210
å behandle en virkelig
stort sett av data, er det

16
00:00:41,210 --> 00:00:44,030
kommer til å kreve mer
og mer ressurser, som

17
00:00:44,030 --> 00:00:47,980
er penger, RAM, all den slags ting.

18
00:00:47,980 --> 00:00:52,090
>> Så, for å være i stand til å analysere en
Algoritmen bruker dette verktøyet sett,

19
00:00:52,090 --> 00:00:56,110
utgangspunktet, spør question--
hvordan fungerer denne algoritmen skala

20
00:00:56,110 --> 00:00:59,020
som vi kaster mer og mer data på det?

21
00:00:59,020 --> 00:01:02,220
I CS50, mengden data vi er
arbeider med er ganske liten.

22
00:01:02,220 --> 00:01:05,140
Vanligvis er våre programmer kommer
å kjøre i et sekund eller less--

23
00:01:05,140 --> 00:01:07,830
sannsynligvis mye mindre
spesielt tidlig.

24
00:01:07,830 --> 00:01:12,250
>> Men tenk om et selskap som avtaler
med hundrevis av millioner av kunder.

25
00:01:12,250 --> 00:01:14,970
Og de trenger for å behandle
at kundedata.

26
00:01:14,970 --> 00:01:18,260
Ettersom antallet kunder de
har blir større og større,

27
00:01:18,260 --> 00:01:21,230
det kommer til å kreve
flere og flere ressurser.

28
00:01:21,230 --> 00:01:22,926
Hvor mange flere ressurser?

29
00:01:22,926 --> 00:01:25,050
Vel, det avhenger av hvordan
vi analysere algoritmen,

30
00:01:25,050 --> 00:01:28,097
ved hjelp av verktøyene i denne kassen.

31
00:01:28,097 --> 00:01:31,180
Når vi snakker om kompleksiteten
en algorithm-- som noen ganger du vil

32
00:01:31,180 --> 00:01:34,040
hører det referert til som tids
kompleksitet eller plass kompleksitet

33
00:01:34,040 --> 00:01:36,190
men vi skal bare
å ringe complexity--

34
00:01:36,190 --> 00:01:38,770
vi vanligvis snakker om
worst-case scenario.

35
00:01:38,770 --> 00:01:42,640
Gitt den absolutt verste haug av
data som vi kan kaste på det,

36
00:01:42,640 --> 00:01:46,440
hvordan er denne algoritmen skal
behandle eller håndtere disse dataene?

37
00:01:46,440 --> 00:01:51,450
Vi vanligvis kaller worst-case
runtime av en algoritme big-O.

38
00:01:51,450 --> 00:01:56,770
Slik at en algoritme kan sies å
kjøre i O n eller O n squared.

39
00:01:56,770 --> 00:01:59,110
Og mer om hva
de betyr i en andre.

40
00:01:59,110 --> 00:02:01,620
>> Noen ganger, skjønt, vi bryr oss
om best-case scenario.

41
00:02:01,620 --> 00:02:05,400
Hvis dataene er alt vi ønsket
det skal være, og det var helt perfekt

42
00:02:05,400 --> 00:02:09,630
og vi skulle sende dette perfekt
sett av data gjennom algoritme.

43
00:02:09,630 --> 00:02:11,470
Hvordan ville det håndtere i denne situasjonen?

44
00:02:11,470 --> 00:02:15,050
Vi noen ganger refererer til at så
big-Omega, slik at i motsetning til stor-O,

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

46
00:02:16,530 --> 00:02:18,880
Big-Omega for best-case scenario.

47
00:02:18,880 --> 00:02:21,319
Big-O for worst-case scenario.

48
00:02:21,319 --> 00:02:23,860
Vanligvis, når vi snakker om
kompleksiteten av en algoritme,

49
00:02:23,860 --> 00:02:26,370
vi snakker om
worst-case scenario.

50
00:02:26,370 --> 00:02:28,100
Så hold det i tankene.

51
00:02:28,100 --> 00:02:31,510
>> Og i denne klassen, vi vanligvis går
å forlate grundig analyse til side.

52
00:02:31,510 --> 00:02:35,350
Det er fag og felt
viet til denne typen ting.

53
00:02:35,350 --> 00:02:37,610
Når vi snakker om resonnement
gjennom algoritmer,

54
00:02:37,610 --> 00:02:41,822
som vi vil gjøre bit-for-bit for mange
algoritmer vi snakke om i klassen.

55
00:02:41,822 --> 00:02:44,780
Vi er egentlig bare snakker om
resonnement gjennom den med sunn fornuft,

56
00:02:44,780 --> 00:02:47,070
ikke med formler, eller bevis,
eller noe sånt.

57
00:02:47,070 --> 00:02:51,600
Så ikke bekymre deg, vil vi ikke være
snu til en stor matte klasse.

58
00:02:51,600 --> 00:02:55,920
>> Så jeg sa at vi bryr oss om kompleksitet
fordi det stiller spørsmålet, hvordan

59
00:02:55,920 --> 00:03:00,160
gjør våre algoritmer håndtere større og
større datasett blir kastet på dem.

60
00:03:00,160 --> 00:03:01,960
Vel, hva er et datasett?

61
00:03:01,960 --> 00:03:03,910
Hva var det jeg mener når jeg sier det?

62
00:03:03,910 --> 00:03:07,600
Det betyr at uansett gjør det meste
fornuft i sammenheng, for å være ærlig.

63
00:03:07,600 --> 00:03:11,160
Hvis vi har en algoritme, er
Prosesser Strings-- vi er trolig

64
00:03:11,160 --> 00:03:13,440
snakker om størrelsen av strengen.

65
00:03:13,440 --> 00:03:15,190
Det er data set--
størrelsen, antallet

66
00:03:15,190 --> 00:03:17,050
tegn som utgjør strengen.

67
00:03:17,050 --> 00:03:20,090
Hvis vi snakker om en
algoritme som behandler filer,

68
00:03:20,090 --> 00:03:23,930
Vi snakker kanskje om hvordan
mange kilobyte omfatter denne filen.

69
00:03:23,930 --> 00:03:25,710
Og det er datasettet.

70
00:03:25,710 --> 00:03:28,870
Hvis vi snakker om en algoritme
som håndterer arrays mer generelt,

71
00:03:28,870 --> 00:03:31,510
slik som sortering algoritmer
eller søker algoritmer,

72
00:03:31,510 --> 00:03:36,690
vi trolig snakker om antall
av elementer som utgjør en oppstilling.

73
00:03:36,690 --> 00:03:39,272
>> Nå kan vi måle en
algorithm-- særlig

74
00:03:39,272 --> 00:03:40,980
når jeg sier vi kan
måle en algoritme, I

75
00:03:40,980 --> 00:03:43,840
mener vi kan måle hvor
mange ressurser det tar opp.

76
00:03:43,840 --> 00:03:48,990
Enten disse ressursene er, hvor mange
byte av RAM-- eller megabyte RAM

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

78
00:03:49,790 --> 00:03:52,320
Eller hvor mye tid det tar å kjøre.

79
00:03:52,320 --> 00:03:56,200
Og vi kan kalle dette
måle, vilkårlig, f n.

80
00:03:56,200 --> 00:03:59,420
Hvor n er antall
elementer i datasettet.

81
00:03:59,420 --> 00:04:02,640
Og f n er hvor mange somethings.

82
00:04:02,640 --> 00:04:07,530
Hvor mange enheter av ressurser gjør
det trenger for å behandle dataene.

83
00:04:07,530 --> 00:04:10,030
>> Nå har vi faktisk ikke bryr seg
om hva f n er nøyaktig.

84
00:04:10,030 --> 00:04:13,700
Faktisk er vi svært sjelden will--
sikkert vil aldri i denne class-- jeg

85
00:04:13,700 --> 00:04:18,709
dykke inn i noen virkelig dype
analyse av hva f n er.

86
00:04:18,709 --> 00:04:23,510
Vi er bare nødt til å snakke om hva f av
n er ca eller hva det pleier å.

87
00:04:23,510 --> 00:04:27,600
Og tendensen til en algoritme er
diktert av sin høyeste orden sikt.

88
00:04:27,600 --> 00:04:29,440
Og vi kan se hva jeg
mener med at ved å ta

89
00:04:29,440 --> 00:04:31,910
en se på en mer konkret eksempel.

90
00:04:31,910 --> 00:04:34,620
>> Så la oss si at vi har
tre forskjellige algoritmer.

91
00:04:34,620 --> 00:04:39,350
Den første av disse tar n
cubed, noen enheter av ressurser

92
00:04:39,350 --> 00:04:42,880
å behandle et datasett av størrelse n.

93
00:04:42,880 --> 00:04:47,000
Vi har en annen algoritme som tar
n terninger pluss n squared ressurser

94
00:04:47,000 --> 00:04:49,350
å behandle et datasett av størrelse n.

95
00:04:49,350 --> 00:04:52,030
Og vi har en tredje
algoritme som kjører in-- som

96
00:04:52,030 --> 00:04:58,300
tar opp n cubed minus 8n squared
pluss 20 n enheter av ressurser

97
00:04:58,300 --> 00:05:02,370
å behandle en algoritme
med datasett av størrelse n.

98
00:05:02,370 --> 00:05:05,594
>> Nå igjen, vi egentlig ikke kommer
å komme inn i denne detaljnivå.

99
00:05:05,594 --> 00:05:08,260
Jeg er egentlig bare ha disse opp
her som en illustrasjon av en punkt

100
00:05:08,260 --> 00:05:10,176
at jeg kommer til å være
gjør i et sekund, noe som

101
00:05:10,176 --> 00:05:12,980
er at vi bare virkelig bryr seg
om tendensen ting

102
00:05:12,980 --> 00:05:14,870
som datasettene blir større.

103
00:05:14,870 --> 00:05:18,220
Slik at hvis datasettet er liten, er det
faktisk en ganske stor forskjell

104
00:05:18,220 --> 00:05:19,870
i disse algoritmene.

105
00:05:19,870 --> 00:05:23,000
Den tredje algoritme der
tar 13 ganger lengre,

106
00:05:23,000 --> 00:05:27,980
13 ganger så mye ressurser
å løpe i forhold til den første.

107
00:05:27,980 --> 00:05:31,659
>> Hvis vår datasettet er størrelse 10, som
er større, men ikke nødvendigvis stor,

108
00:05:31,659 --> 00:05:33,950
Vi kan se at det er
faktisk litt av en forskjell.

109
00:05:33,950 --> 00:05:36,620
Den tredje algoritme
blir mer effektiv.

110
00:05:36,620 --> 00:05:40,120
Det handler om å faktisk 40% -
eller 60% mer effektiv.

111
00:05:40,120 --> 00:05:41,580
Det tar 40% av mengden av tid.

112
00:05:41,580 --> 00:05:45,250
Det kan run-- det kan ta
400 enheter av ressurser

113
00:05:45,250 --> 00:05:47,570
å behandle et datasett av størrelse 10.

114
00:05:47,570 --> 00:05:49,410
Mens den første
algoritmen, derimot,

115
00:05:49,410 --> 00:05:54,520
tar 1.000 enheter av ressurser
å behandle et datasett av størrelse 10.

116
00:05:54,520 --> 00:05:57,240
Men se hva som skjer når
våre tall blir enda større.

117
00:05:57,240 --> 00:05:59,500
>> Nå, forskjellen
mellom disse algoritmene

118
00:05:59,500 --> 00:06:01,420
begynner å bli litt mindre tydelig.

119
00:06:01,420 --> 00:06:04,560
Og det faktum at det finnes
lavere ordens terms-- eller rettere sagt,

120
00:06:04,560 --> 00:06:09,390
vilkår med lavere exponents--
begynner å bli irrelevant.

121
00:06:09,390 --> 00:06:12,290
Hvis et datasett er av størrelse
1000 og den første algoritme

122
00:06:12,290 --> 00:06:14,170
kjører i en milliard trinn.

123
00:06:14,170 --> 00:06:17,880
Og den andre algoritmen kjører i
en milliard og en million skritt.

124
00:06:17,880 --> 00:06:20,870
Og den tredje algoritmen kjører
i bare sjenert av en milliard trinn.

125
00:06:20,870 --> 00:06:22,620
Det er ganske mye en milliard trinn.

126
00:06:22,620 --> 00:06:25,640
De lavere-ordens termer starte
å bli virkelig irrelevant.

127
00:06:25,640 --> 00:06:27,390
Og bare for å virkelig
hammer hjem point--

128
00:06:27,390 --> 00:06:31,240
hvis dataene inngangen er av størrelse en
million-- alle tre av disse ganske mye

129
00:06:31,240 --> 00:06:34,960
ta ett quintillion-- hvis
min matte er correct-- trinn

130
00:06:34,960 --> 00:06:37,260
å behandle en data input
av størrelse en million.

131
00:06:37,260 --> 00:06:38,250
Det er mange av trinnene.

132
00:06:38,250 --> 00:06:42,092
Og det faktum at en av dem kan
ta et par 100 000, eller et par 100

133
00:06:42,092 --> 00:06:44,650
million enda mindre når
vi snakker om en rekke

134
00:06:44,650 --> 00:06:46,990
at big-- det er litt irrelevant.

135
00:06:46,990 --> 00:06:50,006
De har alle en tendens til å ta
ca n terninger,

136
00:06:50,006 --> 00:06:52,380
og så ville vi faktisk henviser
til alle disse algoritmene

137
00:06:52,380 --> 00:06:59,520
som å være av størrelsesorden n
isbiter eller big-O n terninger.

138
00:06:59,520 --> 00:07:03,220
>> Her er en liste over noen av de mer
vanligste beregningsorientert kompleksitet klasser

139
00:07:03,220 --> 00:07:05,820
at vi vil møte i
algoritmer, generelt.

140
00:07:05,820 --> 00:07:07,970
Og også spesielt i CS50.

141
00:07:07,970 --> 00:07:11,410
Disse er bestilt fra
generelt raskest på toppen,

142
00:07:11,410 --> 00:07:13,940
generelt langsomste nederst.

143
00:07:13,940 --> 00:07:16,920
Så konstant tids algoritmer pleier
å være den raskeste, uavhengig

144
00:07:16,920 --> 00:07:19,110
av størrelsen av
data input du passerer i.

145
00:07:19,110 --> 00:07:23,760
De alltid ta en operasjon eller
en enhet av ressurser til å håndtere.

146
00:07:23,760 --> 00:07:25,730
Det kan være to, det kan
være 3, kan det være fire.

147
00:07:25,730 --> 00:07:26,910
Men det er et konstant tall.

148
00:07:26,910 --> 00:07:28,400
Det varierer ikke.

149
00:07:28,400 --> 00:07:31,390
>> Logaritmiske tids algoritmer
er litt bedre.

150
00:07:31,390 --> 00:07:33,950
Og et veldig godt eksempel på
en logaritmisk tid algoritme

151
00:07:33,950 --> 00:07:37,420
du har sikkert sett nå er den
rive fra hverandre av telefonboken

152
00:07:37,420 --> 00:07:39,480
å finne Mike Smith i telefonboken.

153
00:07:39,480 --> 00:07:40,980
Vi kuttet problemet i to.

154
00:07:40,980 --> 00:07:43,580
Og slik som n blir større
og større og larger--

155
00:07:43,580 --> 00:07:47,290
faktisk, hver gang du dobler
n, tar det bare ett trinn.

156
00:07:47,290 --> 00:07:49,770
Så det er mye bedre
enn for eksempel lineær tid.

157
00:07:49,770 --> 00:07:53,030
Som er hvis du dobler n, det
tar dobbelt antall skritt.

158
00:07:53,030 --> 00:07:55,980
Hvis du tredoble n, tar det
tredoble antall skritt.

159
00:07:55,980 --> 00:07:58,580
Ett skritt per enhet.

160
00:07:58,580 --> 00:08:01,790
>> Så det blir litt mer--
litt mindre bra derfra.

161
00:08:01,790 --> 00:08:06,622
Du har lineær rytmisk tid, noen ganger
kalt log lineær tid eller bare n log n.

162
00:08:06,622 --> 00:08:08,330
Og vi vil et eksempel
av en algoritme som

163
00:08:08,330 --> 00:08:13,370
kjører i n log n, som fortsatt er bedre
enn kvadratisk tid-- n squared.

164
00:08:13,370 --> 00:08:17,320
Eller polynomisk tid, n to-
hvilket som helst tall større enn to.

165
00:08:17,320 --> 00:08:20,810
Eller eksponentiell tid, som
er enda C til worse-- n.

166
00:08:20,810 --> 00:08:24,670
Så hevet til noen konstant antall
kraften av størrelsen på inngangen.

167
00:08:24,670 --> 00:08:28,990
Så hvis det er 1,000-- hvis
data input er av størrelse 1000,

168
00:08:28,990 --> 00:08:31,310
det ville ta C til 1000 th strøm.

169
00:08:31,310 --> 00:08:33,559
Det er mye verre enn polynomisk tid.

170
00:08:33,559 --> 00:08:35,030
>> Fakultet tid er enda verre.

171
00:08:35,030 --> 00:08:37,760
Og faktisk er det egentlig gjøre
eksisterer uendelig tid algoritmer,

172
00:08:37,760 --> 00:08:43,740
for eksempel, såkalte dum sort-- som
jobb er å tilfeldig shuffle en matrise

173
00:08:43,740 --> 00:08:45,490
og deretter sjekke for å se
enten det er sortert.

174
00:08:45,490 --> 00:08:47,589
Og hvis det ikke er, tilfeldig
shuffle rekken igjen

175
00:08:47,589 --> 00:08:49,130
og sjekk for å se om det er sortert.

176
00:08:49,130 --> 00:08:51,671
Og så kan du sannsynligvis imagine--
du kan forestille seg en situasjon

177
00:08:51,671 --> 00:08:55,200
hvor i verste fall, at viljen
aldri faktisk begynne med array.

178
00:08:55,200 --> 00:08:57,150
At algoritmen ville kjøre for alltid.

179
00:08:57,150 --> 00:08:59,349
Og så det ville være en
uendelig tid algoritme.

180
00:08:59,349 --> 00:09:01,890
Forhåpentligvis vil du ikke være å skrive
alle fakultet eller uendelig tid

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

182
00:09:04,510 --> 00:09:09,150
>> Så, la oss ta en litt mer
betong titt på noen enklere

183
00:09:09,150 --> 00:09:11,154
beregningsorientert kompleksitet klasser.

184
00:09:11,154 --> 00:09:13,070
Så vi har en example--
eller to eksempler her--

185
00:09:13,070 --> 00:09:15,590
av konstante tids algoritmer,
som alltid tar

186
00:09:15,590 --> 00:09:17,980
en enkelt operasjon i verste tilfelle.

187
00:09:17,980 --> 00:09:20,050
Så det første example--
vi har en funksjon

188
00:09:20,050 --> 00:09:23,952
kalt 4 for deg som
tar en rekke størrelse 1000.

189
00:09:23,952 --> 00:09:25,660
Men så tilsynelatende
faktisk ikke ser

190
00:09:25,660 --> 00:09:29,000
på it egentlig ikke bryr seg hva som er
innsiden av den, i den oppstillingen.

191
00:09:29,000 --> 00:09:30,820
Alltid bare returnerer fire.

192
00:09:30,820 --> 00:09:32,940
Så, at algoritmen,
til tross for det faktum at den

193
00:09:32,940 --> 00:09:35,840
tar 1.000 elementene ikke frem
gjøre noe med dem.

194
00:09:35,840 --> 00:09:36,590
Bare returnerer fire.

195
00:09:36,590 --> 00:09:38,240
Det er alltid et enkelt trinn.

196
00:09:38,240 --> 00:09:41,600
>> Faktisk, tilsett 2 nums-- som
vi har sett før samt--

197
00:09:41,600 --> 00:09:43,680
bare behandler to heltall.

198
00:09:43,680 --> 00:09:44,692
Det er ikke et enkelt trinn.

199
00:09:44,692 --> 00:09:45,900
Det er faktisk et par skritt.

200
00:09:45,900 --> 00:09:50,780
Du får en, får du b, legger du dem
sammen, og du sende resultatene.

201
00:09:50,780 --> 00:09:53,270
Så det er 84 trinn.

202
00:09:53,270 --> 00:09:55,510
Men det er alltid konstant,
uavhengig av a eller b.

203
00:09:55,510 --> 00:09:59,240
Du må få en, får b, legg
dem sammen, utgang resultatet.

204
00:09:59,240 --> 00:10:02,900
Så det er en konstant tid algoritme.

205
00:10:02,900 --> 00:10:05,170
>> Her er et eksempel på en
lineær tid algorithm--

206
00:10:05,170 --> 00:10:08,740
en algoritme som gets-- som tar
en ytterligere trinn, eventuelt

207
00:10:08,740 --> 00:10:10,740
som input vokser etter en.

208
00:10:10,740 --> 00:10:14,190
Så, la oss si at vi leter etter
antall 5 inne i en matrise.

209
00:10:14,190 --> 00:10:16,774
Du kan ha en situasjon der
du kan finne det ganske tidlig.

210
00:10:16,774 --> 00:10:18,606
Men du kan også ha
en situasjon hvor det

211
00:10:18,606 --> 00:10:20,450
kan være det siste element i matrisen.

212
00:10:20,450 --> 00:10:23,780
I en rekke av størrelse 5, hvis
Vi leter etter nummer 5.

213
00:10:23,780 --> 00:10:25,930
Det ville ta 5 trinn.

214
00:10:25,930 --> 00:10:29,180
Og faktisk, forestille seg at det er
ikke 5 hvor som helst i denne matrisen.

215
00:10:29,180 --> 00:10:32,820
Vi har fortsatt faktisk nødt til å se på
hvert enkelt element i matrisen

216
00:10:32,820 --> 00:10:35,550
for å bestemme
hvorvidt 5 er der.

217
00:10:35,550 --> 00:10:39,840
>> Så i verste fall, som er at
elementet er sist i rekken

218
00:10:39,840 --> 00:10:41,700
eller ikke eksisterer i det hele tatt.

219
00:10:41,700 --> 00:10:44,690
Vi har fortsatt å se på
alle de n elementene.

220
00:10:44,690 --> 00:10:47,120
Og så denne algoritmen
kjører i lineær tid.

221
00:10:47,120 --> 00:10:50,340
Du kan bekrefte at ved
ekstrapolere litt ved å si:

222
00:10:50,340 --> 00:10:53,080
hvis vi hadde en 6-element array og
vi var ute etter nummer 5,

223
00:10:53,080 --> 00:10:54,890
det kan ta 6 trinn.

224
00:10:54,890 --> 00:10:57,620
Hvis vi har en 7-element array og
Vi leter etter nummer 5.

225
00:10:57,620 --> 00:10:59,160
Det kan ta 7 trinn.

226
00:10:59,160 --> 00:11:02,920
Som vi legge til en mer element i vår
array, tar det enda et steg.

227
00:11:02,920 --> 00:11:06,750
Det er en lineær algoritme
i verste fall.

228
00:11:06,750 --> 00:11:08,270
>> Par raske spørsmål for deg.

229
00:11:08,270 --> 00:11:11,170
Hva er runtime-- hva som er
worst-case runtime

230
00:11:11,170 --> 00:11:13,700
av denne spesielle kodebit?

231
00:11:13,700 --> 00:11:17,420
Så jeg har en 4 sløyfe her som kjører
fra j er lik 0, hele veien opp til m.

232
00:11:17,420 --> 00:11:21,980
Og det jeg ser her, er at
legeme av sløyfen kjører i konstant tid.

233
00:11:21,980 --> 00:11:24,730
Så bruker terminologien
Vi har allerede snakket om-- hva

234
00:11:24,730 --> 00:11:29,390
ville være det verste-fall
runtime av denne algoritmen?

235
00:11:29,390 --> 00:11:31,050
Ta et sekund.

236
00:11:31,050 --> 00:11:34,270
Den indre delen av sløyfen
kjører i konstant tid.

237
00:11:34,270 --> 00:11:37,510
Og den ytre delen av
sløyfe kommer til å kjøre m ganger.

238
00:11:37,510 --> 00:11:40,260
Så hva er worst-case runtime her?

239
00:11:40,260 --> 00:11:43,210
Visste du gjette big-O av m?

240
00:11:43,210 --> 00:11:44,686
Du ville være riktig.

241
00:11:44,686 --> 00:11:46,230
>> Hva med en annen?

242
00:11:46,230 --> 00:11:48,590
Denne gangen har vi en
løkke inne i en løkke.

243
00:11:48,590 --> 00:11:50,905
Vi har en ytre sløyfe
som går fra null til p.

244
00:11:50,905 --> 00:11:54,630
Og vi har en indre løkke som går
fra null til p, og på innsiden av denne,

245
00:11:54,630 --> 00:11:57,890
Jeg sier at kroppen
sløyfe går i konstant tid.

246
00:11:57,890 --> 00:12:02,330
Så hva er worst-case runtime
av denne spesielle kodebit?

247
00:12:02,330 --> 00:12:06,140
Vel, igjen, har vi en
ytre sløyfe som går p ganger.

248
00:12:06,140 --> 00:12:09,660
Og hver tid-- køyring
av at loop, heller.

249
00:12:09,660 --> 00:12:13,170
Vi har en indre sløyfe
som også kjører p ganger.

250
00:12:13,170 --> 00:12:16,900
Og så innsiden av det, det er den
konstant tid-- liten bit der.

251
00:12:16,900 --> 00:12:19,890
>> Så hvis vi har en ytre løkke som
løper p ganger innsiden av disse er

252
00:12:19,890 --> 00:12:22,880
en indre løkke som
kjører p times-- hva er

253
00:12:22,880 --> 00:12:26,480
worst-case runtime
av denne kodebit?

254
00:12:26,480 --> 00:12:30,730
Visste du gjette big-O p squared?

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

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

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