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

2
00:00:05,830 --> 00:00:07,910
>> Okej, så, beräkningskomplexitet.

3
00:00:07,910 --> 00:00:10,430
Bara en bit av en varning
innan vi dyker i för far--

4
00:00:10,430 --> 00:00:13,070
Detta kommer förmodligen att vara bland
de matematiktunga saker

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

6
00:00:14,200 --> 00:00:16,950
Förhoppningsvis kommer det inte vara alltför överväldigande
och vi ska försöka guida dig

7
00:00:16,950 --> 00:00:19,200
genom processen, men
bara en bit av en rättvis varning.

8
00:00:19,200 --> 00:00:21,282
Det finns en liten bit
matematik inblandade här.

9
00:00:21,282 --> 00:00:23,990
Okej, så för att göra
användning av våra beräkningsresurser

10
00:00:23,990 --> 00:00:28,170
i den verkliga world-- det verkligen
viktigt att förstå algoritmer

11
00:00:28,170 --> 00:00:30,750
och hur de behandlar uppgifter.

12
00:00:30,750 --> 00:00:32,810
Om vi ​​har en riktigt
effektiv algoritm, vi

13
00:00:32,810 --> 00:00:36,292
kan minimera mängden resurser
vi har till förfogande för att ta itu med det.

14
00:00:36,292 --> 00:00:38,750
Om vi ​​har en algoritm som
kommer att ta en hel del arbete

15
00:00:38,750 --> 00:00:41,210
att bearbeta en riktigt
stor uppsättning av data, är det

16
00:00:41,210 --> 00:00:44,030
kommer att kräva mer
och mer resurser, vilket

17
00:00:44,030 --> 00:00:47,980
är pengar, RAM, alla den typen av saker.

18
00:00:47,980 --> 00:00:52,090
>> Så, att kunna analysera en
algoritm att använda detta verktyg set,

19
00:00:52,090 --> 00:00:56,110
princip frågar question--
hur fungerar denna algoritm skala

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

21
00:00:59,020 --> 00:01:02,220
I CS50, mängden data som vi är
arbetar med är ganska liten.

22
00:01:02,220 --> 00:01:05,140
Generellt är våra program går
att köra i en andra eller less--

23
00:01:05,140 --> 00:01:07,830
förmodligen mycket mindre
särskilt tidigt.

24
00:01:07,830 --> 00:01:12,250
>> Men tänk om ett företag som behandlar
med hundratals miljoner kunder.

25
00:01:12,250 --> 00:01:14,970
Och de behöver för att bearbeta
kunden uppgifter.

26
00:01:14,970 --> 00:01:18,260
Eftersom antalet kunder som de
har blir större och större,

27
00:01:18,260 --> 00:01:21,230
det kommer att kräva
mer och mer resurser.

28
00:01:21,230 --> 00:01:22,926
Hur många fler resurser?

29
00:01:22,926 --> 00:01:25,050
Tja, det beror på hur
vi analyserar algoritmen,

30
00:01:25,050 --> 00:01:28,097
med hjälp av verktygen i verktygslådan.

31
00:01:28,097 --> 00:01:31,180
När vi talar om komplexiteten i
en algorithm-- som ibland du kommer

32
00:01:31,180 --> 00:01:34,040
höra det kallas tid
komplexitet eller utrymme komplexitet

33
00:01:34,040 --> 00:01:36,190
men vi ska bara
ringa complexity--

34
00:01:36,190 --> 00:01:38,770
vi generellt talar om
det värsta scenariot.

35
00:01:38,770 --> 00:01:42,640
Med tanke på den absolut värsta högen av
data som vi kan kasta på det,

36
00:01:42,640 --> 00:01:46,440
Hur är denna algoritm kommer att
bearbeta eller ta itu med dessa uppgifter?

37
00:01:46,440 --> 00:01:51,450
Vi kallar allmänhet värsta fall
runtime av en algoritm big-O.

38
00:01:51,450 --> 00:01:56,770
Så en algoritm kan sägas
köra i O n eller O av n kvadrat.

39
00:01:56,770 --> 00:01:59,110
Och mer om vad
de innebär i en sekund.

40
00:01:59,110 --> 00:02:01,620
>> Men ibland gör vi vård
om det bästa scenariot.

41
00:02:01,620 --> 00:02:05,400
Om uppgifterna är allt vi ville
det ska vara och det var absolut perfekt

42
00:02:05,400 --> 00:02:09,630
och vi skickar denna perfekt
datauppsättning genom vår algoritm.

43
00:02:09,630 --> 00:02:11,470
Hur skulle det handtag i en sådan situation?

44
00:02:11,470 --> 00:02:15,050
Vi hänvisar ibland till det som
big-Omega, så till skillnad från big-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 för bästa scenariot.

47
00:02:18,880 --> 00:02:21,319
Big-O för det värsta scenariot.

48
00:02:21,319 --> 00:02:23,860
Generellt när vi talar om
komplexiteten av en algoritm,

49
00:02:23,860 --> 00:02:26,370
vi pratar om
i värsta fall.

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

51
00:02:28,100 --> 00:02:31,510
>> Och i denna klass, vi generellt gå
att lämna noggrann analys åt sidan.

52
00:02:31,510 --> 00:02:35,350
Det finns vetenskaper och fält
ägnas åt den här typen av grejer.

53
00:02:35,350 --> 00:02:37,610
När vi talar om resonemang
genom algoritmer,

54
00:02:37,610 --> 00:02:41,822
som vi kommer att göra bit-för-bit för många
algoritmer vi talar om i klassen.

55
00:02:41,822 --> 00:02:44,780
Vi egentligen bara talar om
resonemang igenom det med sunt förnuft,

56
00:02:44,780 --> 00:02:47,070
inte med formler, eller bevis,
eller nåt sånt.

57
00:02:47,070 --> 00:02:51,600
Så oroa dig inte, vi kommer inte att
förvandlas till en stor matte klass.

58
00:02:51,600 --> 00:02:55,920
>> Så jag sa att vi bryr oss om komplexitet
eftersom det ställer frågan, hur

59
00:02:55,920 --> 00:03:00,160
gör våra algoritmer hanterar större och
större datamängder som kastas på dem.

60
00:03:00,160 --> 00:03:01,960
Nå, vad är en datamängd?

61
00:03:01,960 --> 00:03:03,910
Vad jag menar när jag sa det?

62
00:03:03,910 --> 00:03:07,600
Det betyder vad gör mest
mening i sitt sammanhang, för att vara ärlig.

63
00:03:07,600 --> 00:03:11,160
Om vi ​​har en algoritm, den
Processer Strings-- vi förmodligen

64
00:03:11,160 --> 00:03:13,440
talar om storleken på strängen.

65
00:03:13,440 --> 00:03:15,190
Det är data set--
storleken, antalet

66
00:03:15,190 --> 00:03:17,050
tecken som utgör strängen.

67
00:03:17,050 --> 00:03:20,090
Om vi ​​pratar om en
algoritm som behandlar filer,

68
00:03:20,090 --> 00:03:23,930
vi kan tala om hur
många kilobyte omfattar den filen.

69
00:03:23,930 --> 00:03:25,710
Och det är datamängden.

70
00:03:25,710 --> 00:03:28,870
Om vi ​​pratar om en algoritm
som hanterar arrayer mer generellt,

71
00:03:28,870 --> 00:03:31,510
såsom sorteringsalgoritmer
eller sökalgoritmer,

72
00:03:31,510 --> 00:03:36,690
vi förmodligen pratar om antalet
element som utgör en array.

73
00:03:36,690 --> 00:03:39,272
>> Nu kan vi mäta en
algorithm-- särskilt

74
00:03:39,272 --> 00:03:40,980
när jag säger att vi kan
mäta en algoritm, jag

75
00:03:40,980 --> 00:03:43,840
menar vi kan mäta hur
många resurser det tar upp.

76
00:03:43,840 --> 00:03:48,990
Huruvida dessa resurser är, hur många
bytes RAM-- eller megabyte RAM-minne

77
00:03:48,990 --> 00:03:49,790
den använder.

78
00:03:49,790 --> 00:03:52,320
Eller hur mycket tid det tar att köra.

79
00:03:52,320 --> 00:03:56,200
Och vi kan kalla detta
mäta, godtyckligt, f n.

80
00:03:56,200 --> 00:03:59,420
Där n är antalet
element i datamängden.

81
00:03:59,420 --> 00:04:02,640
Och f n är hur många things.

82
00:04:02,640 --> 00:04:07,530
Hur många enheter av resurser gör
det behöver för att behandla dessa uppgifter.

83
00:04:07,530 --> 00:04:10,030
>> Nu, vi faktiskt inte bryr
vad f n är exakt.

84
00:04:10,030 --> 00:04:13,700
I själva verket mycket sällan will-- vi
säkert kommer aldrig i denna class-- jag

85
00:04:13,700 --> 00:04:18,709
dyka in i någon riktigt djup
analys av vad f hos n är.

86
00:04:18,709 --> 00:04:23,510
Vi ska bara tala om vad f från
n är ungefär eller vad det tenderar att.

87
00:04:23,510 --> 00:04:27,600
Och tendensen av en algoritm är
dikteras av sin högsta ordningens term.

88
00:04:27,600 --> 00:04:29,440
Och vi kan se vad jag
menar med detta genom att ta

89
00:04:29,440 --> 00:04:31,910
En titt på en mer konkret exempel.

90
00:04:31,910 --> 00:04:34,620
>> Så låt oss säga att vi har
tre olika algoritmer.

91
00:04:34,620 --> 00:04:39,350
Den första som tar n
kubik, vissa enheter av resurser

92
00:04:39,350 --> 00:04:42,880
att behandla en datauppsättning av storlek n.

93
00:04:42,880 --> 00:04:47,000
Vi har en andra algoritm som tar
n kubik plus n kvadrerade resurser

94
00:04:47,000 --> 00:04:49,350
att behandla en datauppsättning av storlek n.

95
00:04:49,350 --> 00:04:52,030
Och vi har en tredje
algoritm som körs in-- att

96
00:04:52,030 --> 00:04:58,300
tar upp n kubik minus 8n kvadrat
plus 20 n enheter av resurser

97
00:04:58,300 --> 00:05:02,370
att behandla en algoritm
med uppgifter som storlek n.

98
00:05:02,370 --> 00:05:05,594
>> Nu igen, vi verkligen inte kommer
att komma in i denna detaljnivå.

99
00:05:05,594 --> 00:05:08,260
Jag är verkligen bara har dessa upp
här som en illustration av en punkt

100
00:05:08,260 --> 00:05:10,176
att jag kommer att vara
vilket i ett andra, som

101
00:05:10,176 --> 00:05:12,980
är att vi bara verkligen bryr
om tendensen hos saker

102
00:05:12,980 --> 00:05:14,870
som datamängderna blir större.

103
00:05:14,870 --> 00:05:18,220
Så om datamängden är liten, det finns
faktiskt en ganska stor skillnad

104
00:05:18,220 --> 00:05:19,870
i dessa algoritmer.

105
00:05:19,870 --> 00:05:23,000
Den tredje algoritmen där
tar 13 gånger längre,

106
00:05:23,000 --> 00:05:27,980
13 gånger så mycket resurser
att köra i förhållande till den första.

107
00:05:27,980 --> 00:05:31,659
>> Om vår datamängden är storlek 10, som
är större, men inte nödvändigtvis stora,

108
00:05:31,659 --> 00:05:33,950
Vi kan se att det finns
faktiskt lite av en skillnad.

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

110
00:05:36,620 --> 00:05:40,120
Det handlar om faktiskt 40% -
eller 60% effektivare.

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

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

113
00:05:45,250 --> 00:05:47,570
att behandla en datauppsättning av storlek 10.

114
00:05:47,570 --> 00:05:49,410
Medan den första
algoritm, däremot,

115
00:05:49,410 --> 00:05:54,520
tar 1.000 enheter av resurser
att behandla en datauppsättning av storlek 10.

116
00:05:54,520 --> 00:05:57,240
Men titta vad som händer när
våra siffror bli ännu större.

117
00:05:57,240 --> 00:05:59,500
>> Nu, skillnaden
mellan dessa algoritmer

118
00:05:59,500 --> 00:06:01,420
börjar bli lite mindre uppenbar.

119
00:06:01,420 --> 00:06:04,560
Och det faktum att det finns
lägre ordningens terms-- eller snarare,

120
00:06:04,560 --> 00:06:09,390
termer med lägre exponents--
börjar bli irrelevant.

121
00:06:09,390 --> 00:06:12,290
Om en datauppsättning är av storlek
1000 och den första algoritmen

122
00:06:12,290 --> 00:06:14,170
körs i en miljard steg.

123
00:06:14,170 --> 00:06:17,880
Och den andra algoritmen körs i
en miljard och en miljon steg.

124
00:06:17,880 --> 00:06:20,870
Och den tredje algoritmen körs
på bara blyg av en miljard steg.

125
00:06:20,870 --> 00:06:22,620
Det är ganska mycket en miljard steg.

126
00:06:22,620 --> 00:06:25,640
De lägre ordningens termer börjar
att bli riktigt irrelevant.

127
00:06:25,640 --> 00:06:27,390
Och bara för att verkligen
hammare hem point--

128
00:06:27,390 --> 00:06:31,240
om dataingången är av storlek en
million-- alla tre av dessa ganska mycket

129
00:06:31,240 --> 00:06:34,960
ta en quintillion-- om
min matte är correct-- steg

130
00:06:34,960 --> 00:06:37,260
att bearbeta en dataingång
storlek en miljon.

131
00:06:37,260 --> 00:06:38,250
Det är en mängd åtgärder.

132
00:06:38,250 --> 00:06:42,092
Och det faktum att en av dem kanske
ta ett par 100000, eller ett par 100

133
00:06:42,092 --> 00:06:44,650
miljoner ännu mindre när
Vi pratar om ett antal

134
00:06:44,650 --> 00:06:46,990
som big-- det är ganska irrelevant.

135
00:06:46,990 --> 00:06:50,006
De tenderar alla att ta
approximativt n kubik,

136
00:06:50,006 --> 00:06:52,380
och så skulle vi faktiskt hänvisar
till alla dessa algoritmer

137
00:06:52,380 --> 00:06:59,520
som i storleksordningen n
kubik eller big-O n i kubik.

138
00:06:59,520 --> 00:07:03,220
>> Här är en lista över några av de mer
gemensamma beräkningskomplexitetsklasser

139
00:07:03,220 --> 00:07:05,820
att vi kommer att stöta in
algoritmer, i allmänhet.

140
00:07:05,820 --> 00:07:07,970
Och även specifikt i CS50.

141
00:07:07,970 --> 00:07:11,410
Dessa beställs från
allmänhet snabbast på toppen,

142
00:07:11,410 --> 00:07:13,940
allmänt långsammaste i botten.

143
00:07:13,940 --> 00:07:16,920
Så konstant tids algoritmer tenderar
att vara den snabbaste, oavsett

144
00:07:16,920 --> 00:07:19,110
av storleken på den
inmatning av data du skickar in.

145
00:07:19,110 --> 00:07:23,760
De tar alltid en operation eller
en enhet av resurser för att ta itu med.

146
00:07:23,760 --> 00:07:25,730
Det kan vara två, kanske det
vara 3, kan det vara 4.

147
00:07:25,730 --> 00:07:26,910
Men det är ett konstant antal.

148
00:07:26,910 --> 00:07:28,400
Det varierar inte.

149
00:07:28,400 --> 00:07:31,390
>> Logaritmisk tidsalgoritmer
är något bättre.

150
00:07:31,390 --> 00:07:33,950
Och en riktigt bra exempel på
en logaritmisk tidsalgoritm

151
00:07:33,950 --> 00:07:37,420
Du har säkert sett vid det här laget är det
isärrivning av telefonboken

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

153
00:07:39,480 --> 00:07:40,980
Vi skär problemet i hälften.

154
00:07:40,980 --> 00:07:43,580
Och så n blir större
och större och larger--

155
00:07:43,580 --> 00:07:47,290
i själva verket varje gång du dubbla
n tar det bara ett steg.

156
00:07:47,290 --> 00:07:49,770
Så det är en mycket bättre
än, säg, linjär tid.

157
00:07:49,770 --> 00:07:53,030
Vilket är om du dubbla n, det
tar dubbelt så många steg.

158
00:07:53,030 --> 00:07:55,980
Om du tredubbla n tar det
tredubbla antalet steg.

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

160
00:07:58,580 --> 00:08:01,790
>> Då det blir lite more--
lite mindre bra därifrån.

161
00:08:01,790 --> 00:08:06,622
Du har linjär rytmisk tid, ibland
kallas log linjär tid eller bara n log n.

162
00:08:06,622 --> 00:08:08,330
Och vi ska ett exempel
av en algoritm som

163
00:08:08,330 --> 00:08:13,370
körningar i n log n, som fortfarande är bättre
än kvadratisk time-- n kvadrat.

164
00:08:13,370 --> 00:08:17,320
Eller polynomtid, n två
valfritt antal större än två.

165
00:08:17,320 --> 00:08:20,810
Eller exponentiell tid, vilket
är även worse-- C till n.

166
00:08:20,810 --> 00:08:24,670
Så några konstant antal höjas till
kraften i storleken av insignalen.

167
00:08:24,670 --> 00:08:28,990
Så om det finns 1,000-- om
dataingång är av storlek 1000,

168
00:08:28,990 --> 00:08:31,310
det skulle ta C till åter 1000:e kraften.

169
00:08:31,310 --> 00:08:33,559
Det är mycket värre än polynomisk tid.

170
00:08:33,559 --> 00:08:35,030
>> Faktoriell tid är ännu värre.

171
00:08:35,030 --> 00:08:37,760
Och faktiskt, det verkligen gör
Det finns oändliga tids algoritmer,

172
00:08:37,760 --> 00:08:43,740
såsom, s.k. dum sort-- vars
jobb är att slumpmässigt blanda en array

173
00:08:43,740 --> 00:08:45,490
och sedan kontrollera
oavsett om det är för sortering.

174
00:08:45,490 --> 00:08:47,589
Och om det inte är slumpmässigt
shuffle arrayen igen

175
00:08:47,589 --> 00:08:49,130
och kontrollera om det sorteras.

176
00:08:49,130 --> 00:08:51,671
Och som ni kan nog imagine--
du kan föreställa sig en situation

177
00:08:51,671 --> 00:08:55,200
var i värsta fall kommer att
aldrig faktiskt börjar med matrisen.

178
00:08:55,200 --> 00:08:57,150
Denna algoritm skulle köra alltid.

179
00:08:57,150 --> 00:08:59,349
Och så det skulle vara en
oändlig tid algoritm.

180
00:08:59,349 --> 00:09:01,890
Förhoppningsvis kommer du inte att skriva
varje fakultet eller oändlig tid

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

182
00:09:04,510 --> 00:09:09,150
>> Så, låt oss ta en lite mer
betong titt på några enklare

183
00:09:09,150 --> 00:09:11,154
beräkningskomplexitetsklasser.

184
00:09:11,154 --> 00:09:13,070
Så vi har en example--
eller två exempel här--

185
00:09:13,070 --> 00:09:15,590
av konstanta tidsalgoritmer,
som alltid tar

186
00:09:15,590 --> 00:09:17,980
en enda operation i värsta fall.

187
00:09:17,980 --> 00:09:20,050
Så den första example--
vi har en funktion

188
00:09:20,050 --> 00:09:23,952
kallade 4 för dig, som
tar en rad storlek 1000.

189
00:09:23,952 --> 00:09:25,660
Men sedan tydligen
inte faktiskt ser

190
00:09:25,660 --> 00:09:29,000
på det-- egentligen inte bryr sig vad som är
insidan av det, i nämnda matris.

191
00:09:29,000 --> 00:09:30,820
Alltid bara returnerar fyra.

192
00:09:30,820 --> 00:09:32,940
Så att algoritmen,
trots det faktum att det

193
00:09:32,940 --> 00:09:35,840
tar 1000 element inte
göra något med dem.

194
00:09:35,840 --> 00:09:36,590
Bara tillbaka fyra.

195
00:09:36,590 --> 00:09:38,240
Det är alltid ett enda steg.

196
00:09:38,240 --> 00:09:41,600
>> I själva verket, tillsätt 2 nums-- som
vi har sett tidigare som well--

197
00:09:41,600 --> 00:09:43,680
bara behandlar två heltal.

198
00:09:43,680 --> 00:09:44,692
Det är inte ett enda steg.

199
00:09:44,692 --> 00:09:45,900
Det är faktiskt ett par steg.

200
00:09:45,900 --> 00:09:50,780
Du får en får du b, du lägga till dem
tillsammans, och du matar ut resultaten.

201
00:09:50,780 --> 00:09:53,270
Så det är 84 steg.

202
00:09:53,270 --> 00:09:55,510
Men det är alltid konstant,
oavsett a eller b.

203
00:09:55,510 --> 00:09:59,240
Du måste få en, få b, lägg
ihop dem, mata ut resultatet.

204
00:09:59,240 --> 00:10:02,900
Så det är en konstant tidsalgoritm.

205
00:10:02,900 --> 00:10:05,170
>> Här är ett exempel på en
linjär tids algorithm--

206
00:10:05,170 --> 00:10:08,740
en algoritm som gets-- som tar
ett ytterligare steg, eventuellt,

207
00:10:08,740 --> 00:10:10,740
som din input växer med 1.

208
00:10:10,740 --> 00:10:14,190
Så, låt oss säga att vi letar efter
antalet 5 insidan av en matris.

209
00:10:14,190 --> 00:10:16,774
Du kanske har en situation där
du kan finna det ganska tidigt.

210
00:10:16,774 --> 00:10:18,606
Men du kan också ha
en situation där det

211
00:10:18,606 --> 00:10:20,450
kan vara det sista elementet i uppsättningen.

212
00:10:20,450 --> 00:10:23,780
I en matris med storleken 5, om
Vi letar efter nummer 5.

213
00:10:23,780 --> 00:10:25,930
Det skulle ta 5 steg.

214
00:10:25,930 --> 00:10:29,180
Och faktiskt, föreställa sig att det finns
inte 5 någonstans i denna uppsättning.

215
00:10:29,180 --> 00:10:32,820
Vi har fortfarande faktiskt måste titta på
varje enskilt element i matrisen

216
00:10:32,820 --> 00:10:35,550
i syfte att fastställa
huruvida 5 är där.

217
00:10:35,550 --> 00:10:39,840
>> Så i värsta fall, vilket är att
elementet är sist i gruppen

218
00:10:39,840 --> 00:10:41,700
eller inte existerar alls.

219
00:10:41,700 --> 00:10:44,690
Vi måste fortfarande titta på
alla av n element.

220
00:10:44,690 --> 00:10:47,120
Och så denna algoritm
körs i linjär tid.

221
00:10:47,120 --> 00:10:50,340
Du kan bekräfta detta genom att
extrapolera lite genom att säga,

222
00:10:50,340 --> 00:10:53,080
om vi hade en 6-elementgrupp och
Vi letade efter nummer 5,

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

224
00:10:54,890 --> 00:10:57,620
Om vi ​​har en 7-elementgrupp och
Vi letar efter nummer 5.

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

226
00:10:59,160 --> 00:11:02,920
Som vi lägga till ytterligare en faktor till vår
array, tar det ett steg.

227
00:11:02,920 --> 00:11:06,750
Det är en linjär algoritm
i värsta fall.

228
00:11:06,750 --> 00:11:08,270
>> Par snabba frågor till dig.

229
00:11:08,270 --> 00:11:11,170
Vad är runtime-- vad
värsta fall runtime

230
00:11:11,170 --> 00:11:13,700
av denna speciella kodsträng?

231
00:11:13,700 --> 00:11:17,420
Så jag har en 4 slinga här som körs
från j är lika med 0, hela vägen upp till m.

232
00:11:17,420 --> 00:11:21,980
Och vad jag ser här, är att
kropp av slingan körs i konstant tid.

233
00:11:21,980 --> 00:11:24,730
Så använder den terminologi som
Vi har redan talat about-- vad

234
00:11:24,730 --> 00:11:29,390
skulle vara det värsta
runtime av denna algoritm?

235
00:11:29,390 --> 00:11:31,050
Ta en andra.

236
00:11:31,050 --> 00:11:34,270
Den inre delen av slingan
körs i konstant tid.

237
00:11:34,270 --> 00:11:37,510
Och den yttre delen av den
slinga kommer att köra m gånger.

238
00:11:37,510 --> 00:11:40,260
Så vad är det värsta fall runtime här?

239
00:11:40,260 --> 00:11:43,210
Har du gissa big-O m?

240
00:11:43,210 --> 00:11:44,686
Du skulle bli rätt.

241
00:11:44,686 --> 00:11:46,230
>> Vad sägs om en annan?

242
00:11:46,230 --> 00:11:48,590
Den här gången har vi en
slinga i en slinga.

243
00:11:48,590 --> 00:11:50,905
Vi har en yttre slinga
som går från noll till sid.

244
00:11:50,905 --> 00:11:54,630
Och vi har en inre slinga som löper
från noll till p, och insidan av det,

245
00:11:54,630 --> 00:11:57,890
Jag konstatera att kroppen
slinga körs i konstant tid.

246
00:11:57,890 --> 00:12:02,330
Så vad är det värsta fall runtime
av denna speciella kodsträng?

247
00:12:02,330 --> 00:12:06,140
Tja, återigen, har vi en
yttre slinga som löper p gånger.

248
00:12:06,140 --> 00:12:09,660
Och varje time-- iteration
av denna slinga, snarare.

249
00:12:09,660 --> 00:12:13,170
Vi har en inre slinga
som körs också p gånger.

250
00:12:13,170 --> 00:12:16,900
Och sedan inne i det, det är
konstant time-- lilla utdrag där.

251
00:12:16,900 --> 00:12:19,890
>> Så om vi har en yttre slinga som
körs p tider inuti vilket är

252
00:12:19,890 --> 00:12:22,880
en inre ögla som
löper p times-- vad som är

253
00:12:22,880 --> 00:12:26,480
värsta fall runtime
av detta utdrag av koden?

254
00:12:26,480 --> 00:12:30,730
Har du gissa big-O p kvadrat?

255
00:12:30,730 --> 00:12:31,690
>> Jag är Doug Lloyd.

256
00:12:31,690 --> 00:12:33,880
Detta är CS50.

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