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

2
00:00:05,830 --> 00:00:07,910
>> Okay, så, beregningsmæssige kompleksitet.

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

4
00:00:10,430 --> 00:00:13,070
dette vil sandsynligvis være blandt
de mest matematiske-tunge ting

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

6
00:00:14,200 --> 00:00:16,950
Forhåbentlig vil det ikke være for overvældende
og vi vil forsøge at guide dig

7
00:00:16,950 --> 00:00:19,200
gennem processen, men
bare lidt af en retfærdig advarsel.

8
00:00:19,200 --> 00:00:21,282
Der er en lille smule
af matematik involveret her.

9
00:00:21,282 --> 00:00:23,990
Okay, så for at gøre
brug af vores it-ressourcer

10
00:00:23,990 --> 00:00:28,170
i den virkelige verden-det er virkelig
vigtigt at forstå algoritmer

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

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

13
00:00:32,810 --> 00:00:36,292
kan minimere mængden af ​​ressourcer
vi har til rådighed til at behandle den.

14
00:00:36,292 --> 00:00:38,750
Hvis vi har en algoritme,
kommer til at tage en masse arbejde

15
00:00:38,750 --> 00:00:41,210
at behandle en virkelig
store datasæt, er det

16
00:00:41,210 --> 00:00:44,030
vil kræve mere
og flere ressourcer, som

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

18
00:00:47,980 --> 00:00:52,090
>> Så at kunne analysere et
algoritme, der anvender dette værktøj sæt,

19
00:00:52,090 --> 00:00:56,110
dybest set, spørger question--
hvordan gør denne algoritme skala

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

21
00:00:59,020 --> 00:01:02,220
I CS50, mængden af ​​data er vi
arbejder med er temmelig lille.

22
00:01:02,220 --> 00:01:05,140
Generelt er vores programmer går
at køre i en anden eller less--

23
00:01:05,140 --> 00:01:07,830
sikkert en masse mindre
især tidligt.

24
00:01:07,830 --> 00:01:12,250
>> Men tænk på et firma, der handler
med hundredvis af millioner af kunder.

25
00:01:12,250 --> 00:01:14,970
Og de har brug for at behandle
at kundernes data.

26
00:01:14,970 --> 00:01:18,260
Da antallet af kunder, de
har bliver større og større,

27
00:01:18,260 --> 00:01:21,230
det kommer til at kræve
flere og flere ressourcer.

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

29
00:01:22,926 --> 00:01:25,050
Tja, det afhænger af, hvordan
vi analysere algoritme,

30
00:01:25,050 --> 00:01:28,097
ved hjælp af de værktøjer i denne værktøjskasse.

31
00:01:28,097 --> 00:01:31,180
Når vi taler om kompleksitet
en algorithm-- som undertiden vil du

32
00:01:31,180 --> 00:01:34,040
høre det omtalt som tiden
kompleksitet eller rum kompleksitet

33
00:01:34,040 --> 00:01:36,190
men vi bare
at kalde complexity--

34
00:01:36,190 --> 00:01:38,770
vi generelt taler om
det værst tænkelige scenarie.

35
00:01:38,770 --> 00:01:42,640
I betragtning af den absolutte værste bunke
data, som vi kunne smide på det,

36
00:01:42,640 --> 00:01:46,440
hvordan denne algoritme vil
forarbejde eller beskæftige sig med disse data?

37
00:01:46,440 --> 00:01:51,450
Vi generelt kalder det værst tænkelige
runtime af en algoritme big-O.

38
00:01:51,450 --> 00:01:56,770
Så en algoritme kan siges at
køre i O n eller O n potens.

39
00:01:56,770 --> 00:01:59,110
Og mere om, hvad
dem betyde i et sekund.

40
00:01:59,110 --> 00:02:01,620
>> Nogle gange, selv om, vi gør pleje
om det bedste tænkelige scenario.

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

42
00:02:05,400 --> 00:02:09,630
og vi var at sende denne perfekte
sæt af data gennem vores algoritme.

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

44
00:02:11,470 --> 00:02:15,050
Vi nogle gange henviser til, at så
big-Omega, så i modsætning til store-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 bedste fald.

47
00:02:18,880 --> 00:02:21,319
Big-O for det værst tænkelige scenarie.

48
00:02:21,319 --> 00:02:23,860
Generelt, når vi taler om
kompleksiteten af ​​en algoritme,

49
00:02:23,860 --> 00:02:26,370
vi taler om den
værst tænkelige scenario.

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

51
00:02:28,100 --> 00:02:31,510
>> Og i denne klasse, er vi generelt går
at forlade grundig analyse til side.

52
00:02:31,510 --> 00:02:35,350
Der er videnskaber og felter
viet til den slags ting.

53
00:02:35,350 --> 00:02:37,610
Når vi taler om ræsonnement
via algoritmer,

54
00:02:37,610 --> 00:02:41,822
som vi vil gøre stykke-for-stykke for mange
algoritmer vi taler om i klassen.

55
00:02:41,822 --> 00:02:44,780
Vi er virkelig bare taler om
ræsonnement gennem det med sund fornuft,

56
00:02:44,780 --> 00:02:47,070
ikke med formler, eller beviser,
eller sådan noget.

57
00:02:47,070 --> 00:02:51,600
Så du skal ikke bekymre dig, vil vi ikke være
ved at blive en stor matematik klasse.

58
00:02:51,600 --> 00:02:55,920
>> Så jeg sagde, at vi interesserer os for kompleksitet
fordi det stiller spørgsmålet, hvordan

59
00:02:55,920 --> 00:03:00,160
gør vores algoritmer håndtere større og
større datasæt kastes på dem.

60
00:03:00,160 --> 00:03:01,960
Nå, hvad er et datasæt?

61
00:03:01,960 --> 00:03:03,910
Hvad gjorde jeg mener, når jeg sagde det?

62
00:03:03,910 --> 00:03:07,600
Det betyder, hvad gør mest
mening i sammenhæng, at være ærlig.

63
00:03:07,600 --> 00:03:11,160
Hvis vi har en algoritme, den
Processer Strings-- vi er nok

64
00:03:11,160 --> 00:03:13,440
tale om størrelsen af ​​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, der udgør strengen.

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

68
00:03:20,090 --> 00:03:23,930
vi måske tale om, hvordan
mange kilobyte omfatter denne fil.

69
00:03:23,930 --> 00:03:25,710
Og det er datasættet.

70
00:03:25,710 --> 00:03:28,870
Hvis vi taler om en algoritme
der håndterer arrays mere generelt,

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

72
00:03:31,510 --> 00:03:36,690
vi nok taler om antallet
elementer, der omfatter et array.

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

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

75
00:03:40,980 --> 00:03:43,840
mener, vi kan måle, hvor
mange ressourcer, det tager op.

76
00:03:43,840 --> 00:03:48,990
Hvorvidt disse ressourcer er, hvor mange
bytes RAM-- eller megabyte RAM

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

78
00:03:49,790 --> 00:03:52,320
Eller hvor meget tid det tager at køre.

79
00:03:52,320 --> 00:03:56,200
Og vi kan kalde denne
måle, vilkårligt, f af n.

80
00:03:56,200 --> 00:03:59,420
Hvor n er antallet af
elementer i datasættet.

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

82
00:04:02,640 --> 00:04:07,530
Hvor mange enheder af ressourcer gør
det kræve at behandle disse data.

83
00:04:07,530 --> 00:04:10,030
>> Nu, vi faktisk ligeglad
hvad f n er præcis.

84
00:04:10,030 --> 00:04:13,700
Faktisk vi meget sjældent will--
helt sikkert vil aldrig i denne class-- I

85
00:04:13,700 --> 00:04:18,709
dykke ned i enhver virkelig dyb
analyse af, hvad f n er.

86
00:04:18,709 --> 00:04:23,510
Vi er lige kommer til at snakke om, hvad f af
n er ca. eller hvad det har tendens til.

87
00:04:23,510 --> 00:04:27,600
Og tendensen af ​​en algoritme er
dikteret af dets højeste orden sigt.

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

89
00:04:29,440 --> 00:04:31,910
et kig på et mere konkret eksempel.

90
00:04:31,910 --> 00:04:34,620
>> Så lad os sige, at vi har
tre forskellige algoritmer.

91
00:04:34,620 --> 00:04:39,350
Hvoraf den første tager n
kubik, nogle enheder af ressourcer

92
00:04:39,350 --> 00:04:42,880
at behandle et datasæt størrelse n.

93
00:04:42,880 --> 00:04:47,000
Vi har en anden algoritme, der tager
n kubik plus n firkantede ressourcer

94
00:04:47,000 --> 00:04:49,350
at behandle et datasæt størrelse n.

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

96
00:04:52,030 --> 00:04:58,300
fylder n kubik minus 8n kvadreret
plus 20 n enheder af ressourcer

97
00:04:58,300 --> 00:05:02,370
at behandle en algoritme
med datasæt størrelse n.

98
00:05:02,370 --> 00:05:05,594
>> Nu igen, vi virkelig ikke vil
at komme ind i dette niveau af detaljer.

99
00:05:05,594 --> 00:05:08,260
Jeg er virkelig bare har disse op
her som en illustration af et punkt

100
00:05:08,260 --> 00:05:10,176
at jeg har tænkt mig at være
gør i en anden, hvilket

101
00:05:10,176 --> 00:05:12,980
er, at vi kun virkelig pleje
om tendensen ting

102
00:05:12,980 --> 00:05:14,870
som datasættene bliver større.

103
00:05:14,870 --> 00:05:18,220
Så hvis datasættet er lille, er der
faktisk en temmelig stor forskel

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

105
00:05:19,870 --> 00:05:23,000
Den tredje algoritme der
tager 13 gange længere tid,

106
00:05:23,000 --> 00:05:27,980
13 gange den mængde ressourcer
at køre i forhold til den første.

107
00:05:27,980 --> 00:05:31,659
>> Hvis vores datasæt er størrelse 10, som
er større, men ikke nødvendigvis store,

108
00:05:31,659 --> 00:05:33,950
Vi kan se, at der er
faktisk lidt af en forskel.

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

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

111
00:05:40,120 --> 00:05:41,580
Det tager 40% mængden af ​​tid.

112
00:05:41,580 --> 00:05:45,250
Det kan run-- det kan tage
400 enheder af ressourcer

113
00:05:45,250 --> 00:05:47,570
at behandle et datasæt af størrelse 10.

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

115
00:05:49,410 --> 00:05:54,520
tager 1.000 enheder af ressourcer
at behandle et datasæt af størrelse 10.

116
00:05:54,520 --> 00:05:57,240
Men se, hvad der sker som
vores tal bliver endnu større.

117
00:05:57,240 --> 00:05:59,500
>> Nu forskellen
mellem disse algoritmer

118
00:05:59,500 --> 00:06:01,420
begynder at blive lidt mindre synlige.

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

120
00:06:04,560 --> 00:06:09,390
vilkår med lavere exponents--
begynder at blive irrelevant.

121
00:06:09,390 --> 00:06:12,290
Hvis et datasæt størrelse
1.000 og den første algoritme

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

123
00:06:14,170 --> 00:06:17,880
Og anden algoritme kører i
en milliard og en million trin.

124
00:06:17,880 --> 00:06:20,870
Og den tredje algoritme kører
på bare genert af en milliard trin.

125
00:06:20,870 --> 00:06:22,620
Det er temmelig meget en milliard trin.

126
00:06:22,620 --> 00:06:25,640
Disse lavere ordens led starter
til at blive virkelig irrelevant.

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

128
00:06:27,390 --> 00:06:31,240
hvis input data er størrelse en
million-- alle tre af disse temmelig meget

129
00:06:31,240 --> 00:06:34,960
tage en quintillion-- hvis
min matematik er correct-- skridt

130
00:06:34,960 --> 00:06:37,260
at behandle en dataindgang
størrelse million.

131
00:06:37,260 --> 00:06:38,250
Det er en masse trin.

132
00:06:38,250 --> 00:06:42,092
Og det faktum, at en af ​​dem kan
tage et par 100.000, eller et par 100

133
00:06:42,092 --> 00:06:44,650
million endnu mindre, når
vi taler om et nummer

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

135
00:06:46,990 --> 00:06:50,006
De har alle en tendens til at tage
ca n kubik,

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

137
00:06:52,380 --> 00:06:59,520
som værende af størrelsesordenen n
kubik eller store-O n kubik.

138
00:06:59,520 --> 00:07:03,220
>> Her er en liste over nogle af de mere
fælles beregningsmæssige kompleksitet klasser

139
00:07:03,220 --> 00:07:05,820
at vi vil støde på
algoritmer generelt.

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

141
00:07:07,970 --> 00:07:11,410
Disse er bestilt fra
generelt hurtigste foroven,

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

143
00:07:13,940 --> 00:07:16,920
Så konstant tid algoritmer tendens
at være den hurtigste, uanset

144
00:07:16,920 --> 00:07:19,110
af størrelsen af ​​den
datainput du passerer i.

145
00:07:19,110 --> 00:07:23,760
De har altid tage en operation eller
en enhed af ressourcer at beskæftige sig med.

146
00:07:23,760 --> 00:07:25,730
Det kunne være 2, det måske
være 3, kan det være 4.

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

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

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

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

151
00:07:33,950 --> 00:07:37,420
du har sikkert set af nu er det
oprivning af telefonbogen

152
00:07:37,420 --> 00:07:39,480
at finde Mike Smith i telefonbogen.

153
00:07:39,480 --> 00:07:40,980
Vi sender problemet i halve.

154
00:07:40,980 --> 00:07:43,580
Og så n bliver større
og større og larger--

155
00:07:43,580 --> 00:07:47,290
i virkeligheden, hver gang du fordobler
n, det tager kun et skridt.

156
00:07:47,290 --> 00:07:49,770
Så det er meget bedre
end fx lineær tid.

157
00:07:49,770 --> 00:07:53,030
Hvilket er, hvis du dobbelt n, det
tager fordoble antallet af trin.

158
00:07:53,030 --> 00:07:55,980
Hvis du tredoble n, det tager
tredoble antallet af skridt.

159
00:07:55,980 --> 00:07:58,580
Et skridt pr.

160
00:07:58,580 --> 00:08:01,790
>> Så tingene bliver lidt more--
lidt mindre fantastisk derfra.

161
00:08:01,790 --> 00:08:06,622
Du har lineær rytmisk tid, nogle gange
kaldet log lineær tid eller bare n log n.

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

163
00:08:08,330 --> 00:08:13,370
kører i n log n, som stadig bedre
end kvadratisk time-- n potens.

164
00:08:13,370 --> 00:08:17,320
Eller polynomiel tid, n to
hvilket som helst antal større end to.

165
00:08:17,320 --> 00:08:20,810
Eller eksponentiel tid, hvilket
er endda worse-- C til n.

166
00:08:20,810 --> 00:08:24,670
Så nogle konstant antal hævet til
magt størrelsen af ​​input.

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

168
00:08:28,990 --> 00:08:31,310
det ville tage C til 1000. magt.

169
00:08:31,310 --> 00:08:33,559
Det er meget værre end polynomiel tid.

170
00:08:33,559 --> 00:08:35,030
>> Faktorielt tid er endnu værre.

171
00:08:35,030 --> 00:08:37,760
Og i virkeligheden, virkelig gøre der
Der findes uendelig tid algoritmer,

172
00:08:37,760 --> 00:08:43,740
såsom såkaldte dum sort-- hvis
job er at tilfældigt shuffle et array

173
00:08:43,740 --> 00:08:45,490
og derefter kontrollere, at se
uanset om det er sorteret.

174
00:08:45,490 --> 00:08:47,589
Og hvis det ikke er, tilfældigt
shuffle array igen

175
00:08:47,589 --> 00:08:49,130
og kontrollere, om det er sorteret.

176
00:08:49,130 --> 00:08:51,671
Og som kan du sikkert imagine--
du kan forestille dig en situation,

177
00:08:51,671 --> 00:08:55,200
hvor i det værst tænkelige, der vil
faktisk aldrig begynde med arrayet.

178
00:08:55,200 --> 00:08:57,150
Denne algoritme ville køre for evigt.

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

180
00:08:59,349 --> 00:09:01,890
Forhåbentlig vil du ikke skrive
enhver 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å lad os tage lidt mere
beton kig på nogle enklere

183
00:09:09,150 --> 00:09:11,154
beregningsmæssige 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
af konstant tid algoritmer,
som altid tager

186
00:09:15,590 --> 00:09:17,980
en enkelt operation i det værst tænkelige.

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

188
00:09:20,050 --> 00:09:23,952
kaldte 4 for dig, som
tager en bred vifte af størrelse 1000.

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

190
00:09:25,660 --> 00:09:29,000
på det-- ikke rigtig ligeglad, hvad der er
inde i den, for den opstilling.

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

192
00:09:30,820 --> 00:09:32,940
Så denne algoritme,
på trods af, at det

193
00:09:32,940 --> 00:09:35,840
tager 1.000 elementer ikke
gøre noget 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 altid et enkelt trin.

196
00:09:38,240 --> 00:09:41,600
>> Faktisk, tilsættes 2 nums-- som
vi har set før, som well--

197
00:09:41,600 --> 00:09:43,680
lige processer to heltal.

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

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

200
00:09:45,900 --> 00:09:50,780
Du får en, får du b, du tilføje dem
sammen, og du output resultaterne.

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

202
00:09:53,270 --> 00:09:55,510
Men det er altid konstant,
uanset a eller b.

203
00:09:55,510 --> 00:09:59,240
Du er nødt til at få en, få b, tilføj
dem sammen, output 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, der tager gets--
et yderligere skridt, muligvis,

207
00:10:08,740 --> 00:10:10,740
som dit input vokser med 1.

208
00:10:10,740 --> 00:10:14,190
Så lad os sige, at vi leder efter
nummer 5 indersiden af ​​et array.

209
00:10:14,190 --> 00:10:16,774
Du har måske en situation, hvor
du kan finde det forholdsvis tidligt.

210
00:10:16,774 --> 00:10:18,606
Men man kunne også have
en situation, hvor det

211
00:10:18,606 --> 00:10:20,450
kan være den sidste element i array.

212
00:10:20,450 --> 00:10:23,780
I en vifte af størrelse 5, hvis
Vi leder efter nummer 5.

213
00:10:23,780 --> 00:10:25,930
Det ville tage 5 trin.

214
00:10:25,930 --> 00:10:29,180
Og i virkeligheden, forestille sig, at der er
ikke 5 overalt i dette array.

215
00:10:29,180 --> 00:10:32,820
Vi har faktisk stadig nødt til at se på
hvert enkelt element af arrayet

216
00:10:32,820 --> 00:10:35,550
med henblik på at bestemme
hvorvidt 5 er der.

217
00:10:35,550 --> 00:10:39,840
>> Så i det værst tænkelige, nemlig at
elementet er sidst i arrayet

218
00:10:39,840 --> 00:10:41,700
eller findes ikke på alle.

219
00:10:41,700 --> 00:10:44,690
Vi har stadig til at se på
alle de n elementer.

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

221
00:10:47,120 --> 00:10:50,340
Du kan bekræfte, at ved
ekstrapolere en lille smule ved at sige,

222
00:10:50,340 --> 00:10:53,080
hvis vi havde en 6-element array og
vi ledte efter nummer 5,

223
00:10:53,080 --> 00:10:54,890
det kan tage 6 trin.

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

225
00:10:57,620 --> 00:10:59,160
Det kan tage 7 trin.

226
00:10:59,160 --> 00:11:02,920
Som vi tilføje endnu en element til vores
array, det tager endnu et skridt.

227
00:11:02,920 --> 00:11:06,750
Det er en lineær algoritme
i det værst tænkelige.

228
00:11:06,750 --> 00:11:08,270
>> Par hurtige spørgsmål til dig.

229
00:11:08,270 --> 00:11:11,170
Hvad er runtime--, hvad der er
det værst tænkelige runtime

230
00:11:11,170 --> 00:11:13,700
af denne særlige stykke kode?

231
00:11:13,700 --> 00:11:17,420
Så jeg har en 4 løkke her, der kører
fra j lig 0, hele vejen op til m.

232
00:11:17,420 --> 00:11:21,980
Og hvad jeg ser her, er, at
organ af løkken kører i konstant tid.

233
00:11:21,980 --> 00:11:24,730
Så ved hjælp af terminologi,
Vi har allerede talt om-- hvad

234
00:11:24,730 --> 00:11:29,390
ville være det værst tænkelige
runtime af denne algoritme?

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

236
00:11:31,050 --> 00:11:34,270
Den indre del af sløjfen
kører i konstant tid.

237
00:11:34,270 --> 00:11:37,510
Og den ydre del af
loop kommer til at køre m gange.

238
00:11:37,510 --> 00:11:40,260
Så hvad er den værst tænkelige runtime her?

239
00:11:40,260 --> 00:11:43,210
Vidste du gætte big-O m?

240
00:11:43,210 --> 00:11:44,686
Du ville have ret.

241
00:11:44,686 --> 00:11:46,230
>> Hvad med en anden?

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

243
00:11:48,590 --> 00:11:50,905
Vi har en ydre sløjfe
der løber fra nul til s.

244
00:11:50,905 --> 00:11:54,630
Og vi har en indre sløjfe, der kører
fra nul til p, og inde i det,

245
00:11:54,630 --> 00:11:57,890
Jeg anfører, at kroppen
loop kører i konstant tid.

246
00:11:57,890 --> 00:12:02,330
Så hvad er den værst tænkelige runtime
af denne særlige stykke kode?

247
00:12:02,330 --> 00:12:06,140
Nå, igen, har vi en
ydre loop, der kører p gange.

248
00:12:06,140 --> 00:12:09,660
Og hver time-- iteration
af denne løkke, snarere.

249
00:12:09,660 --> 00:12:13,170
Vi har en indre sløjfe
, der også kører p gange.

250
00:12:13,170 --> 00:12:16,900
Og så inde i det, der er den
konstant time-- lille uddrag der.

251
00:12:16,900 --> 00:12:19,890
>> Så hvis vi har en ydre løkke, der
kører p gange, inden i hvilken er

252
00:12:19,890 --> 00:12:22,880
en indre løkke,
kører p gange-- hvad der er

253
00:12:22,880 --> 00:12:26,480
det værst tænkelige runtime
af denne stump kode?

254
00:12:26,480 --> 00:12:30,730
Vidste du gætte big-O af p potens?

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

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

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