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

2
00:00:05,830 --> 00:00:07,910
>> Oké, dus, computationele complexiteit.

3
00:00:07,910 --> 00:00:10,430
Gewoon een beetje een waarschuwing
voordat we duiken in te far--

4
00:00:10,430 --> 00:00:13,070
Dit zal waarschijnlijk worden onder
de meeste wiskunde-zware dingen

5
00:00:13,070 --> 00:00:14,200
we praten over in CS50.

6
00:00:14,200 --> 00:00:16,950
Hopelijk zal het niet al te overweldigend
en we zullen proberen en begeleiden u

7
00:00:16,950 --> 00:00:19,200
door het proces, maar
gewoon een beetje een eerlijke waarschuwing.

8
00:00:19,200 --> 00:00:21,282
Er is een beetje
van de wiskunde hier betrokken.

9
00:00:21,282 --> 00:00:23,990
Oké, dus om te maken
gebruik van onze computationele middelen

10
00:00:23,990 --> 00:00:28,170
in de echte wereld-- het is echt
belangrijk om algoritmes te begrijpen

11
00:00:28,170 --> 00:00:30,750
en hoe zij verwerken data.

12
00:00:30,750 --> 00:00:32,810
Als we een echt
efficiënte algoritme, we

13
00:00:32,810 --> 00:00:36,292
kan de hoeveelheid middelen te minimaliseren
we beschikbaar hebben om te gaan.

14
00:00:36,292 --> 00:00:38,750
Als we een algoritme dat
gaat een hoop werk te nemen

15
00:00:38,750 --> 00:00:41,210
om echt te verwerken een
grote set van gegevens, het is

16
00:00:41,210 --> 00:00:44,030
gaan meer nodig
en meer middelen, die

17
00:00:44,030 --> 00:00:47,980
is geld, RAM, al dat soort dingen.

18
00:00:47,980 --> 00:00:52,090
>> Dus, in staat om een ​​analyse
algoritme met behulp van deze tool set,

19
00:00:52,090 --> 00:00:56,110
eigenlijk, vraagt ​​de question--
hoe werkt dit algoritme schaal

20
00:00:56,110 --> 00:00:59,020
zoals we gooien meer en meer gegevens op het?

21
00:00:59,020 --> 00:01:02,220
In CS50, de hoeveelheid gegevens die we
werken met is vrij klein.

22
00:01:02,220 --> 00:01:05,140
In het algemeen zijn onze programma's gaan
om te draaien in een tweede of less--

23
00:01:05,140 --> 00:01:07,830
waarschijnlijk een minder
bijzonder vroeg.

24
00:01:07,830 --> 00:01:12,250
>> Maar na te denken over een bedrijf dat zich bezighoudt
met honderden miljoenen klanten.

25
00:01:12,250 --> 00:01:14,970
En ze moeten verwerken
dat klantgegevens.

26
00:01:14,970 --> 00:01:18,260
Aangezien het aantal klanten dat ze
hebben groter en groter,

27
00:01:18,260 --> 00:01:21,230
het gaat om eisen
meer en meer middelen.

28
00:01:21,230 --> 00:01:22,926
Hoeveel middelen?

29
00:01:22,926 --> 00:01:25,050
Nou, dat hangt af van hoe
we analyseren het algoritme,

30
00:01:25,050 --> 00:01:28,097
met behulp van de gereedschappen in deze gereedschapskist.

31
00:01:28,097 --> 00:01:31,180
Als we praten over de complexiteit van
een algorithm-- die soms je zult

32
00:01:31,180 --> 00:01:34,040
hoor het wel aangeduid als de tijd
complexiteit of ruimte complexiteit

33
00:01:34,040 --> 00:01:36,190
maar we gaan gewoon
te bellen complexity--

34
00:01:36,190 --> 00:01:38,770
we het over het algemeen
het worst-case scenario.

35
00:01:38,770 --> 00:01:42,640
Gezien de absolute slechtste stapel
gegevens die we konden worden gooien op het,

36
00:01:42,640 --> 00:01:46,440
hoe wordt dit algoritme gaat
verwerken of omgaan met die gegevens?

37
00:01:46,440 --> 00:01:51,450
We over het algemeen noemen het worst-case
runtime van een algoritme big-O.

38
00:01:51,450 --> 00:01:56,770
Dus een algoritme kan worden gezegd
draaien in O n of O n kwadraat.

39
00:01:56,770 --> 00:01:59,110
En meer over wat
die betekenen in een tweede.

40
00:01:59,110 --> 00:02:01,620
>> Soms, hoewel, zorg wij
over de best-case scenario.

41
00:02:01,620 --> 00:02:05,400
Als de gegevens is alles wat we wilden
het aan en het was absoluut perfect

42
00:02:05,400 --> 00:02:09,630
en we stuurden deze perfecte
set van gegevens via ons algoritme.

43
00:02:09,630 --> 00:02:11,470
Hoe zou het behandelen in die situatie?

44
00:02:11,470 --> 00:02:15,050
Wij verwijzen soms dat als
big-Omega, dus in tegenstelling big-O,

45
00:02:15,050 --> 00:02:16,530
we hebben grote-Omega.

46
00:02:16,530 --> 00:02:18,880
Big-Omega voor het beste scenario.

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

48
00:02:21,319 --> 00:02:23,860
Over het algemeen, als we praten over
de complexiteit van een algoritme,

49
00:02:23,860 --> 00:02:26,370
we praten over de
in het ergste geval.

50
00:02:26,370 --> 00:02:28,100
Dus hou dat in gedachten.

51
00:02:28,100 --> 00:02:31,510
>> En in deze klasse, we meestal gaan
aan de strenge analyse buiten beschouwing laten.

52
00:02:31,510 --> 00:02:35,350
Er zijn wetenschappen en velden
gewijd aan dit soort dingen.

53
00:02:35,350 --> 00:02:37,610
Wanneer we praten over redeneren
door middel van algoritmes,

54
00:02:37,610 --> 00:02:41,822
die wij stuk-voor-stuk zal doen voor velen
algoritmes we praten over in de klas.

55
00:02:41,822 --> 00:02:44,780
We zijn echt alleen over
redeneren doorheen met gezond verstand,

56
00:02:44,780 --> 00:02:47,070
niet met formules, of bewijzen,
of iets dergelijks.

57
00:02:47,070 --> 00:02:51,600
Dus maak je geen zorgen, zullen wij niet
verandert in een grote wiskunde klasse.

58
00:02:51,600 --> 00:02:55,920
>> Dus ik zei dat we de zorg over de complexiteit
want het stelt de vraag, hoe

59
00:02:55,920 --> 00:03:00,160
weet onze algoritmes verwerken groter en
grotere datasets naar hen gegooid.

60
00:03:00,160 --> 00:03:01,960
Nou, wat is een data set?

61
00:03:01,960 --> 00:03:03,910
Wat heb ik bedoel als ik zei dat?

62
00:03:03,910 --> 00:03:07,600
Het betekent dat wat de meeste maakt
zin in context, om eerlijk te zijn.

63
00:03:07,600 --> 00:03:11,160
Als we een algoritme, het
Processen Strings-- we waarschijnlijk

64
00:03:11,160 --> 00:03:13,440
over de grootte van de string.

65
00:03:13,440 --> 00:03:15,190
Dat is de data set--
de grootte, het aantal

66
00:03:15,190 --> 00:03:17,050
tekens die deel uitmaken van de string.

67
00:03:17,050 --> 00:03:20,090
Als we praten over een
algoritme dat bestanden verwerkt,

68
00:03:20,090 --> 00:03:23,930
we zouden kunnen praten over hoe
vele kilobytes bestaan ​​dat bestand.

69
00:03:23,930 --> 00:03:25,710
En dat is de dataset.

70
00:03:25,710 --> 00:03:28,870
Als we praten over een algoritme
die verwerkt arrays algemeen,

71
00:03:28,870 --> 00:03:31,510
zoals sorteeralgoritmen
of zoeken algoritmen,

72
00:03:31,510 --> 00:03:36,690
we waarschijnlijk over het aantal
elementen die een array omvatten.

73
00:03:36,690 --> 00:03:39,272
>> Nu, we kunnen een meten
algorithm-- in het bijzonder,

74
00:03:39,272 --> 00:03:40,980
als ik zeg dat we kunnen
meten van een algoritme, I

75
00:03:40,980 --> 00:03:43,840
bedoelen we kunnen meten hoe
veel middelen het neemt.

76
00:03:43,840 --> 00:03:48,990
Of deze middelen zijn, hoeveel
bytes van RAM-- of megabyte RAM-geheugen

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

78
00:03:49,790 --> 00:03:52,320
Of hoeveel tijd het kost om te draaien.

79
00:03:52,320 --> 00:03:56,200
En we kunnen dit noemen
meten, willekeurig, f n.

80
00:03:56,200 --> 00:03:59,420
Waarbij n het aantal
elementen in de dataset.

81
00:03:59,420 --> 00:04:02,640
En f n is hoeveel plussers.

82
00:04:02,640 --> 00:04:07,530
Hoeveel eenheden van de middelen doet
zij eisen dat die gegevens te verwerken.

83
00:04:07,530 --> 00:04:10,030
>> Nu, we hebben eigenlijk niet schelen
over wat f van n is precies.

84
00:04:10,030 --> 00:04:13,700
In feite hebben we zeer zelden will--
zeker zal nooit in deze class-- I

85
00:04:13,700 --> 00:04:18,709
Duik in een echt diepe
analyse van wat f n.

86
00:04:18,709 --> 00:04:23,510
We gaan gewoon praten over wat f van
n is ongeveer of wat neigt.

87
00:04:23,510 --> 00:04:27,600
De neiging van een algoritme
gedicteerd door de hoogste orde termijn.

88
00:04:27,600 --> 00:04:29,440
En we kunnen zien wat ik
bedoel dat door het nemen

89
00:04:29,440 --> 00:04:31,910
Een blik op een concreet voorbeeld.

90
00:04:31,910 --> 00:04:34,620
>> Dus laten we zeggen dat we
drie verschillende algoritmen.

91
00:04:34,620 --> 00:04:39,350
De eerste daarvan is nu n
blokjes, sommige eenheden van de middelen

92
00:04:39,350 --> 00:04:42,880
een dataset van grootte n verwerken.

93
00:04:42,880 --> 00:04:47,000
We hebben een tweede algoritme dat neemt
n blokjes plus n kwadraat middelen

94
00:04:47,000 --> 00:04:49,350
een dataset van grootte n verwerken.

95
00:04:49,350 --> 00:04:52,030
En we hebben een derde
algoritme dat in-- die loopt

96
00:04:52,030 --> 00:04:58,300
neemt n blokjes minus 8n kwadraat
plus 20 n eenheden van de middelen

97
00:04:58,300 --> 00:05:02,370
een algoritme te verwerken
met data set van grootte n.

98
00:05:02,370 --> 00:05:05,594
>> Nu weer, we zijn echt niet van plan
om in dit niveau van detail.

99
00:05:05,594 --> 00:05:08,260
Ik ben echt gewoon deze omhoog
hier ter illustratie van een punt

100
00:05:08,260 --> 00:05:10,176
dat ik ga worden
die in een tweede, die

101
00:05:10,176 --> 00:05:12,980
is dat we alleen echt zorg
over de tendens van de dingen

102
00:05:12,980 --> 00:05:14,870
als de datasets groter.

103
00:05:14,870 --> 00:05:18,220
Dus als de dataset is klein, er is
eigenlijk een vrij groot verschil

104
00:05:18,220 --> 00:05:19,870
in deze algoritmen.

105
00:05:19,870 --> 00:05:23,000
De derde algoritme is er
duurt 13 keer langer,

106
00:05:23,000 --> 00:05:27,980
13 keer de hoeveelheid middelen
te lopen ten opzichte van de eerste.

107
00:05:27,980 --> 00:05:31,659
>> Als onze dataset is maat 10, die
groter, maar niet noodzakelijkerwijs groot,

108
00:05:31,659 --> 00:05:33,950
kunnen we zien dat er
eigenlijk een beetje een verschil.

109
00:05:33,950 --> 00:05:36,620
De derde algoritme
efficiënter.

110
00:05:36,620 --> 00:05:40,120
Het is over het daadwerkelijk 40% -
of 60% efficiënter.

111
00:05:40,120 --> 00:05:41,580
Het neemt 40% van de tijd.

112
00:05:41,580 --> 00:05:45,250
Het kan run-- kan nemen
400 eenheden van de middelen

113
00:05:45,250 --> 00:05:47,570
een dataset van maat 10 te verwerken.

114
00:05:47,570 --> 00:05:49,410
Overwegende dat de eerste
algoritme daarentegen

115
00:05:49,410 --> 00:05:54,520
neemt 1.000 eenheden van de middelen
een dataset van maat 10 te verwerken.

116
00:05:54,520 --> 00:05:57,240
Maar kijk eens wat er gebeurt als
onze nummers krijgen nog groter.

117
00:05:57,240 --> 00:05:59,500
>> Nu het verschil
tussen deze algoritmen

118
00:05:59,500 --> 00:06:01,420
beginnen iets minder duidelijk worden.

119
00:06:01,420 --> 00:06:04,560
En het feit dat er
lagere orde terms-- of liever,

120
00:06:04,560 --> 00:06:09,390
termen met lagere exponents--
beginnen te irrelevant geworden.

121
00:06:09,390 --> 00:06:12,290
Als een dataset is van de grootte
1000 en het eerste algoritme

122
00:06:12,290 --> 00:06:14,170
draait in een miljard stappen.

123
00:06:14,170 --> 00:06:17,880
En de tweede algoritme draait in
een miljard en een miljoen stappen.

124
00:06:17,880 --> 00:06:20,870
En de derde algoritme loopt
in gewoon verlegen van een miljard stappen.

125
00:06:20,870 --> 00:06:22,620
Het is vrij veel een miljard stappen.

126
00:06:22,620 --> 00:06:25,640
Die lagere orde termen beginnen
om echt irrelevant geworden.

127
00:06:25,640 --> 00:06:27,390
En gewoon om echt
hamer huis van de point--

128
00:06:27,390 --> 00:06:31,240
Als de data ingang van een groot
million-- alle drie van deze vrij veel

129
00:06:31,240 --> 00:06:34,960
neem een ​​quintillion-- als
mijn wiskunde is correct-- stappen

130
00:06:34,960 --> 00:06:37,260
een data-input te verwerken
van de grootte van een miljoen.

131
00:06:37,260 --> 00:06:38,250
Dat is veel trappen.

132
00:06:38,250 --> 00:06:42,092
En het feit dat een van hen zou
neem een ​​paar 100.000, of een paar 100

133
00:06:42,092 --> 00:06:44,650
miljoen nog minder wanneer
we praten over een aantal

134
00:06:44,650 --> 00:06:46,990
dat big-- het is een soort van irrelevant.

135
00:06:46,990 --> 00:06:50,006
Ze hebben allemaal de neiging om te nemen
ongeveer n blokjes,

136
00:06:50,006 --> 00:06:52,380
en dus zouden we eigenlijk verwijzen
al deze algoritmen

137
00:06:52,380 --> 00:06:59,520
als de orde van n
blokjes of big-O n blokjes.

138
00:06:59,520 --> 00:07:03,220
>> Hier is een lijst van enkele van de meer
gemeenschappelijke computationele complexiteit klassen

139
00:07:03,220 --> 00:07:05,820
dat we tegenkomen in
algoritmen, algemeen.

140
00:07:05,820 --> 00:07:07,970
En ook specifiek in CS50.

141
00:07:07,970 --> 00:07:11,410
Deze worden besteld
algemeen snelste bovenaan,

142
00:07:11,410 --> 00:07:13,940
algemeen langzaamste onderaan.

143
00:07:13,940 --> 00:07:16,920
Dus constante tijd algoritmen neiging
de snelste, ongeacht

144
00:07:16,920 --> 00:07:19,110
de grootte van de
gegevensinvoer u passeren.

145
00:07:19,110 --> 00:07:23,760
Ze nemen altijd een operatie of
een eenheid van de middelen om te gaan met.

146
00:07:23,760 --> 00:07:25,730
Het zou kunnen zijn 2, is het misschien
3 zijn, is het misschien 4.

147
00:07:25,730 --> 00:07:26,910
Maar het is een constant aantal.

148
00:07:26,910 --> 00:07:28,400
Het niet varieert.

149
00:07:28,400 --> 00:07:31,390
>> Logaritmische tijd algoritmen
zijn iets beter.

150
00:07:31,390 --> 00:07:33,950
En een heel goed voorbeeld van
een logaritmische tijd algoritme

151
00:07:33,950 --> 00:07:37,420
je zeker hebben gezien nu is het
openscheuren van het telefoonboek

152
00:07:37,420 --> 00:07:39,480
Mike Smith vinden in het telefoonboek.

153
00:07:39,480 --> 00:07:40,980
We snijden het probleem in de helft.

154
00:07:40,980 --> 00:07:43,580
Dus als n groter wordt
en grotere en larger--

155
00:07:43,580 --> 00:07:47,290
In feite, elke keer als je het dubbele
n, het duurt maar een stap.

156
00:07:47,290 --> 00:07:49,770
Dus dat is een stuk beter
dan, zeg, lineaire tijd.

157
00:07:49,770 --> 00:07:53,030
Dat is als je Double N, is het
neemt het dubbele van het aantal stappen.

158
00:07:53,030 --> 00:07:55,980
Als je verdrievoudigen n, het duurt
verdrievoudigen het aantal stappen.

159
00:07:55,980 --> 00:07:58,580
Een stap per eenheid.

160
00:07:58,580 --> 00:08:01,790
>> Dan dingen een beetje more--
iets minder grote vanaf daar.

161
00:08:01,790 --> 00:08:06,622
Je hebt lineaire ritmische tijd, soms
genaamd log lineaire tijd of gewoon n log n.

162
00:08:06,622 --> 00:08:08,330
En we zullen een voorbeeld
een algoritme dat

163
00:08:08,330 --> 00:08:13,370
runs in n log n, die nog beter
dan kwadratisch tijd-- n kwadraat.

164
00:08:13,370 --> 00:08:17,320
Of polynomiale tijd, n twee
elk getal groter dan twee.

165
00:08:17,320 --> 00:08:20,810
Of exponentiële tijd, die
zelfs worse-- C n.

166
00:08:20,810 --> 00:08:24,670
Dus sommige constant aantal verhoogd tot
de kracht van de grootte van de ingang.

167
00:08:24,670 --> 00:08:28,990
Dus als er 1,000-- als de
gegevensinvoer is van grootte 1000,

168
00:08:28,990 --> 00:08:31,310
het zou C nemen om de 1000 de macht.

169
00:08:31,310 --> 00:08:33,559
Het is veel erger dan polynomiale tijd.

170
00:08:33,559 --> 00:08:35,030
>> Faculteit tijd is nog erger.

171
00:08:35,030 --> 00:08:37,760
En in feite is er echt
Er bestaan ​​oneindige tijd algoritmen,

172
00:08:37,760 --> 00:08:43,740
zoals zogenaamde dom sort-- waarvan
taak is om willekeurig shuffle een array

173
00:08:43,740 --> 00:08:45,490
en controleer om te zien
of het nu opgelost.

174
00:08:45,490 --> 00:08:47,589
En als het niet, willekeurig
shuffle de array weer

175
00:08:47,589 --> 00:08:49,130
en controleren om te zien of het nu opgelost.

176
00:08:49,130 --> 00:08:51,671
En zoals je kunt waarschijnlijk imagine--
kunt u een situatie voor te stellen

177
00:08:51,671 --> 00:08:55,200
waar in het slechtste geval, dat wil
nooit echt beginnen met de array.

178
00:08:55,200 --> 00:08:57,150
Dat algoritme zou voor altijd uit te voeren.

179
00:08:57,150 --> 00:08:59,349
En dus dat zou een te zijn
oneindige tijd algoritme.

180
00:08:59,349 --> 00:09:01,890
Hopelijk zult u niet schrijven
elke faculteit of oneindige tijd

181
00:09:01,890 --> 00:09:04,510
algoritmen in CS50.

182
00:09:04,510 --> 00:09:09,150
>> Dus, laten we eens een beetje meer
betonnen kijkje bij enkele eenvoudiger

183
00:09:09,150 --> 00:09:11,154
computationele complexiteit klassen.

184
00:09:11,154 --> 00:09:13,070
Dus we hebben een example--
of twee voorbeelden hier--

185
00:09:13,070 --> 00:09:15,590
van constante tijd algoritmen,
die altijd nemen

186
00:09:15,590 --> 00:09:17,980
één operatie in het slechtste geval.

187
00:09:17,980 --> 00:09:20,050
Dus de eerste example--
we hebben een functie

188
00:09:20,050 --> 00:09:23,952
riep 4 voor u, die
neemt een reeks van afmetingen 1.000.

189
00:09:23,952 --> 00:09:25,660
Maar dan blijkbaar
eigenlijk niet kijken

190
00:09:25,660 --> 00:09:29,000
bij het-- niet echt schelen wat is
erin, van genoemde matrix.

191
00:09:29,000 --> 00:09:30,820
Altijd net terug van vier.

192
00:09:30,820 --> 00:09:32,940
Dus, dat algoritme,
ondanks het feit dat het

193
00:09:32,940 --> 00:09:35,840
neemt 1000 elementen niet
alles doen met hen.

194
00:09:35,840 --> 00:09:36,590
Net terug van vier.

195
00:09:36,590 --> 00:09:38,240
Het is altijd een enkele stap.

196
00:09:38,240 --> 00:09:41,600
>> In feite, voeg 2 nums-- die
we eerder als goed-- hebt gezien

197
00:09:41,600 --> 00:09:43,680
slechts verwerkt twee getallen.

198
00:09:43,680 --> 00:09:44,692
Het is niet een enkele stap.

199
00:09:44,692 --> 00:09:45,900
Het is eigenlijk een paar stappen.

200
00:09:45,900 --> 00:09:50,780
Je krijgt een, krijg je b, u ze toevoegen
samen, en u de output van de resultaten.

201
00:09:50,780 --> 00:09:53,270
Dus het is 84 stappen.

202
00:09:53,270 --> 00:09:55,510
Maar het is altijd constant,
ongeacht a of b.

203
00:09:55,510 --> 00:09:59,240
Je moet een te krijgen, krijgen b, voeg
ze samen output het resultaat.

204
00:09:59,240 --> 00:10:02,900
Dus dat is een constante tijd algoritme.

205
00:10:02,900 --> 00:10:05,170
>> Hier is een voorbeeld van een
lineaire tijd algorithm--

206
00:10:05,170 --> 00:10:08,740
een algoritme dat gets-- dat neemt
één additionele stap, eventueel,

207
00:10:08,740 --> 00:10:10,740
als uw inbreng groeit door 1.

208
00:10:10,740 --> 00:10:14,190
Dus, laten we zeggen dat we op zoek naar
het aantal 5 binnenkant van een array.

209
00:10:14,190 --> 00:10:16,774
Je zou een situatie waar hebben
U vindt het vrij vroeg.

210
00:10:16,774 --> 00:10:18,606
Maar je kon ook
een situatie waarin

211
00:10:18,606 --> 00:10:20,450
zou het laatste element van de array.

212
00:10:20,450 --> 00:10:23,780
In een array van grootte 5, indien
we op zoek naar het nummer 5.

213
00:10:23,780 --> 00:10:25,930
Het zou 5 stappen.

214
00:10:25,930 --> 00:10:29,180
En in feite, stel dat er
5 niet overal in deze array.

215
00:10:29,180 --> 00:10:32,820
We hebben nog steeds eigenlijk moeten kijken naar
elk element van de array

216
00:10:32,820 --> 00:10:35,550
om te bepalen
of 5 is daar.

217
00:10:35,550 --> 00:10:39,840
>> Dus in het slechtste geval, namelijk dat
het element is de laatste in de reeks

218
00:10:39,840 --> 00:10:41,700
of niet bestaan.

219
00:10:41,700 --> 00:10:44,690
We hebben nog steeds te kijken naar
alle n elementen.

220
00:10:44,690 --> 00:10:47,120
En dus dit algoritme
draait in lineaire tijd.

221
00:10:47,120 --> 00:10:50,340
U kan bevestigen dat door
extrapoleren een beetje door te zeggen:

222
00:10:50,340 --> 00:10:53,080
als we een 6-element array en
we waren op zoek naar het nummer 5,

223
00:10:53,080 --> 00:10:54,890
het zou 6 stappen.

224
00:10:54,890 --> 00:10:57,620
Als we een 7-element array en
we op zoek naar het nummer 5.

225
00:10:57,620 --> 00:10:59,160
Het zou 7 stappen.

226
00:10:59,160 --> 00:11:02,920
Als we voegen nog een element aan onze
array, duurt het nog een stap.

227
00:11:02,920 --> 00:11:06,750
Dat is een lineair algoritme
in het slechtste geval.

228
00:11:06,750 --> 00:11:08,270
>> Paar korte vragen voor u.

229
00:11:08,270 --> 00:11:11,170
Wat is het runtime-- wat
het slechtste geval runtime

230
00:11:11,170 --> 00:11:13,700
van dit bijzondere stukje code?

231
00:11:13,700 --> 00:11:17,420
Dus ik heb een 4 loop hier die loopt
van j gelijk is aan 0, helemaal tot m.

232
00:11:17,420 --> 00:11:21,980
En wat ik hier zien, is dat de
body van de lus wordt uitgevoerd in constante tijd.

233
00:11:21,980 --> 00:11:24,730
Dus met behulp van de terminologie die
we hebben al about-- wat gepraat

234
00:11:24,730 --> 00:11:29,390
zou het slechtste geval
looptijd van dit algoritme?

235
00:11:29,390 --> 00:11:31,050
Neem een ​​tweede.

236
00:11:31,050 --> 00:11:34,270
Het binnenste deel van de lus
draait in constante tijd.

237
00:11:34,270 --> 00:11:37,510
En het buitenste deel van de
lus gaat m keer draaien.

238
00:11:37,510 --> 00:11:40,260
Dus wat is het slechtste geval runtime hier?

239
00:11:40,260 --> 00:11:43,210
Heb je big-O van m raden?

240
00:11:43,210 --> 00:11:44,686
Je zou gelijk hebben.

241
00:11:44,686 --> 00:11:46,230
>> Wat dacht je van een ander?

242
00:11:46,230 --> 00:11:48,590
Deze keer hebben we een
lus binnen een lus.

243
00:11:48,590 --> 00:11:50,905
We hebben een buitenlus
die loopt van nul tot p.

244
00:11:50,905 --> 00:11:54,630
En we hebben een innerlijke lus die loopt
van nul tot p, en de binnenkant van dat

245
00:11:54,630 --> 00:11:57,890
Ik zeggen dat het lichaam de
lus loopt constant in de tijd.

246
00:11:57,890 --> 00:12:02,330
Dus wat is het worst-case runtime
van dit bijzondere stukje code?

247
00:12:02,330 --> 00:12:06,140
Nou, nogmaals, we hebben een
buitenlus dat p maal uitgevoerd.

248
00:12:06,140 --> 00:12:09,660
En elke tijd-- iteratie
van die lus, in plaats van.

249
00:12:09,660 --> 00:12:13,170
We hebben een innerlijke lus
die ook loopt p maal.

250
00:12:13,170 --> 00:12:16,900
En dan de binnenkant van dat, is er de
constante tijd-- klein fragment daar.

251
00:12:16,900 --> 00:12:19,890
>> Dus als we een buitenste lus die
rijdt p maal binnen luidt

252
00:12:19,890 --> 00:12:22,880
een innerlijke lus die
loopt p times-- wat

253
00:12:22,880 --> 00:12:26,480
het slechtste geval runtime
van dit stukje code?

254
00:12:26,480 --> 00:12:30,730
Heb je big-O p denk kwadraat?

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

256
00:12:31,690 --> 00:12:33,880
Dit is CS50.

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