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

2
00:00:05,830 --> 00:00:07,910
>> Alle reg, sodat, rekenkundige kompleksiteit.

3
00:00:07,910 --> 00:00:10,430
Net 'n bietjie van 'n waarskuwing
voordat ons duik in te far--

4
00:00:10,430 --> 00:00:13,070
hierdie sal waarskynlik onder
die mees wiskunde-swaar dinge

5
00:00:13,070 --> 00:00:14,200
ons praat oor in CS50.

6
00:00:14,200 --> 00:00:16,950
Hopelik sal dit nie te oorweldigend wees
en ons sal probeer en lei jou

7
00:00:16,950 --> 00:00:19,200
deur die proses nie, maar
net 'n bietjie van 'n billike waarskuwing.

8
00:00:19,200 --> 00:00:21,282
Daar is 'n bietjie
van wiskunde hier betrokke.

9
00:00:21,282 --> 00:00:23,990
Alle reg, sodat in volgorde na maak
gebruik van ons hulpbronne computational

10
00:00:23,990 --> 00:00:28,170
in die werklike world-- dit is regtig
belangrik om te verstaan ​​algoritmes

11
00:00:28,170 --> 00:00:30,750
en hoe hulle verwerk data.

12
00:00:30,750 --> 00:00:32,810
As ons 'n werklik
doeltreffende algoritme, ons

13
00:00:32,810 --> 00:00:36,292
kan die bedrag van die hulpbronne te minimaliseer
ons beskikbaar om dit te hanteer.

14
00:00:36,292 --> 00:00:38,750
As ons 'n algoritme wat
gaan 'n baie werk te neem

15
00:00:38,750 --> 00:00:41,210
om werklik te verwerk 'n
groot versameling van data, dit is

16
00:00:41,210 --> 00:00:44,030
gaan meer nodig
en meer hulpbronne, wat

17
00:00:44,030 --> 00:00:47,980
is geld, geheue, al daardie soort van dinge.

18
00:00:47,980 --> 00:00:52,090
>> So, in staat is om 'n analiseer
algoritme gebruik van hierdie hulpmiddel stel,

19
00:00:52,090 --> 00:00:56,110
basies, vra die question--
hoe werk hierdie algoritme skaal

20
00:00:56,110 --> 00:00:59,020
as ons gooi meer en meer data op dit?

21
00:00:59,020 --> 00:01:02,220
In CS50, die bedrag van die data ons
werk met is redelik klein.

22
00:01:02,220 --> 00:01:05,140
Oor die algemeen, is ons programme gaan
uit te voer in 'n tweede of less--

23
00:01:05,140 --> 00:01:07,830
waarskynlik 'n baie minder
veral vroeg op.

24
00:01:07,830 --> 00:01:12,250
>> Maar dink oor 'n maatskappy wat handel oor
met honderde miljoene kliënte.

25
00:01:12,250 --> 00:01:14,970
En wat hulle nodig het om te verwerk
dat die kliënt data.

26
00:01:14,970 --> 00:01:18,260
As die aantal kliënte wat hulle
het groter en groter,

27
00:01:18,260 --> 00:01:21,230
dit gaan om te vereis
meer en meer hulpbronne.

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

29
00:01:22,926 --> 00:01:25,050
Wel, dit hang af van hoe
ons analiseer die algoritme,

30
00:01:25,050 --> 00:01:28,097
die gebruik van die gereedskap in hierdie toolbox.

31
00:01:28,097 --> 00:01:31,180
Wanneer ons praat oor die kompleksiteit van
'n algorithm-- wat soms jy sal

32
00:01:31,180 --> 00:01:34,040
hoor dit verwys na die tyd
kompleksiteit of ruimte kompleksiteit

33
00:01:34,040 --> 00:01:36,190
maar ons gaan net
om te bel complexity--

34
00:01:36,190 --> 00:01:38,770
ons praat oor die algemeen
die ergste scenario.

35
00:01:38,770 --> 00:01:42,640
Gegewe die absolute ergste hopie
data wat ons kan gooi dit,

36
00:01:42,640 --> 00:01:46,440
hoe word hierdie algoritme gaan
verwerk of hanteer dat die data?

37
00:01:46,440 --> 00:01:51,450
Ons oor die algemeen noem die ergste geval
runtime van 'n algoritme groot-O.

38
00:01:51,450 --> 00:01:56,770
So 'n algoritme kan gesê word dat
hardloop in O van n of O van n vierkant.

39
00:01:56,770 --> 00:01:59,110
En meer oor wat
diegene bedoel in 'n tweede.

40
00:01:59,110 --> 00:02:01,620
>> Soms, al is, sorg ons doen
oor die beste scenario.

41
00:02:01,620 --> 00:02:05,400
As die data is alles wat ons wou
dit moet wees en dit was absoluut perfek

42
00:02:05,400 --> 00:02:09,630
en ons was te stuur hierdie perfekte
stel data deur ons algoritme.

43
00:02:09,630 --> 00:02:11,470
Hoe sou dit te hanteer in daardie situasie?

44
00:02:11,470 --> 00:02:15,050
Ons verwys soms dat
groot-Omega, so in kontras met die groot-O,

45
00:02:15,050 --> 00:02:16,530
ons het groot-Omega.

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

47
00:02:18,880 --> 00:02:21,319
Big-O vir die ergste scenario.

48
00:02:21,319 --> 00:02:23,860
Oor die algemeen, wanneer ons praat oor
die kompleksiteit van 'n algoritme,

49
00:02:23,860 --> 00:02:26,370
ons praat oor die
ergste geval scenario.

50
00:02:26,370 --> 00:02:28,100
So hou dit in gedagte.

51
00:02:28,100 --> 00:02:31,510
>> En in hierdie klas, is ons oor die algemeen gaan
om die akkurate analise opsy te verlaat.

52
00:02:31,510 --> 00:02:35,350
Daar is wetenskap en velde
gewy aan hierdie soort van dinge.

53
00:02:35,350 --> 00:02:37,610
Wanneer ons praat oor redenasie
deur algoritmes,

54
00:02:37,610 --> 00:02:41,822
wat ons stuk-vir-stuk sal doen vir baie
algoritmes ons praat oor in die klas.

55
00:02:41,822 --> 00:02:44,780
Ons is regtig net te praat oor
redeneer deur dit met gesonde verstand,

56
00:02:44,780 --> 00:02:47,070
nie met formules, of bewyse,
of iets soos dit.

57
00:02:47,070 --> 00:02:51,600
So moenie bekommerd wees nie, sal ons nie
draai in 'n groot wiskunde klas.

58
00:02:51,600 --> 00:02:55,920
>> So ek sê ons omgee kompleksiteit
want dit vra die vraag, hoe

59
00:02:55,920 --> 00:03:00,160
doen ons algoritmes te hanteer en groter
groter datastelle op hulle gegooi.

60
00:03:00,160 --> 00:03:01,960
Wel, wat is 'n datastel?

61
00:03:01,960 --> 00:03:03,910
Wat het ek bedoel as ek sê dat?

62
00:03:03,910 --> 00:03:07,600
Dit beteken ook al die meeste maak
sin in konteks, om eerlik te wees.

63
00:03:07,600 --> 00:03:11,160
As ons 'n algoritme, die
Prosesse Strings-- ons is waarskynlik

64
00:03:11,160 --> 00:03:13,440
praat oor die grootte van die string.

65
00:03:13,440 --> 00:03:15,190
Dit is die data set--
die grootte, die aantal

66
00:03:15,190 --> 00:03:17,050
karakters wat die string.

67
00:03:17,050 --> 00:03:20,090
As ons praat oor 'n
algoritme wat lêers prosesse,

68
00:03:20,090 --> 00:03:23,930
Ons kan praat oor hoe
baie kilogrepe bestaan ​​dat 'n lêer.

69
00:03:23,930 --> 00:03:25,710
En dit is die datastel.

70
00:03:25,710 --> 00:03:28,870
As ons praat oor 'n algoritme
wat hanteer skikkings meer algemeen,

71
00:03:28,870 --> 00:03:31,510
soos sorteringsalgoritmes
of soek algoritmes,

72
00:03:31,510 --> 00:03:36,690
ons waarskynlik praat oor die aantal
elemente wat 'n verskeidenheid bestaan.

73
00:03:36,690 --> 00:03:39,272
>> Nou, ons kan 'n meet
algorithm-- in die besonder,

74
00:03:39,272 --> 00:03:40,980
as ek sê ons kan
meet 'n algoritme, ek

75
00:03:40,980 --> 00:03:43,840
beteken dat ons meet hoe
baie hulpbronne dit neem.

76
00:03:43,840 --> 00:03:48,990
Of daardie hulpbronne is, hoeveel
grepe van RAM-- of megagrepe RAM

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

78
00:03:49,790 --> 00:03:52,320
Of hoeveel tyd wat dit neem om te hardloop.

79
00:03:52,320 --> 00:03:56,200
En ons kan dit noem
meet, arbitrêr, f van n.

80
00:03:56,200 --> 00:03:59,420
Waar n die aantal
elemente in die datastel.

81
00:03:59,420 --> 00:04:02,640
En f van N is hoeveel Iets.

82
00:04:02,640 --> 00:04:07,530
Hoeveel eenhede van hulpbronne nie
dit vereis dat die data te verwerk.

83
00:04:07,530 --> 00:04:10,030
>> Nou, ons het eintlik nie omgee
oor wat f van N is presies.

84
00:04:10,030 --> 00:04:13,700
Trouens, ons baie selde will--
sal seker nooit in hierdie class-- ek

85
00:04:13,700 --> 00:04:18,709
duik in enige regtig diep
ontleding van wat f van N is.

86
00:04:18,709 --> 00:04:23,510
Ons is net gaan om te praat oor wat f van
N is ongeveer of wat dit is geneig om.

87
00:04:23,510 --> 00:04:27,600
En die neiging van 'n algoritme is
bepaal deur die hoogste orde termyn.

88
00:04:27,600 --> 00:04:29,440
En ons kan sien wat ek
daarmee deur die neem van

89
00:04:29,440 --> 00:04:31,910
'n blik op 'n meer konkrete voorbeeld.

90
00:04:31,910 --> 00:04:34,620
>> So kom ons sê dat ons
drie verskillende algoritmes.

91
00:04:34,620 --> 00:04:39,350
Waarvan die eerste neem n
blokkies, sommige eenhede van hulpbronne

92
00:04:39,350 --> 00:04:42,880
om 'n datastel van grootte n verwerk.

93
00:04:42,880 --> 00:04:47,000
Ons het 'n tweede algoritme wat neem
N blokkies plus N kwadraat hulpbronne

94
00:04:47,000 --> 00:04:49,350
om 'n datastel van grootte n verwerk.

95
00:04:49,350 --> 00:04:52,030
En ons het 'n derde
algoritme wat in-- wat loop

96
00:04:52,030 --> 00:04:58,300
neem n blokkies minus 8N kwadraat
plus 20 N eenhede van hulpbronne

97
00:04:58,300 --> 00:05:02,370
om 'n algoritme te verwerk
met datastel grootte n.

98
00:05:02,370 --> 00:05:05,594
>> Nou weer, het ons regtig nie gaan
om te kry in hierdie vlak van detail.

99
00:05:05,594 --> 00:05:08,260
Ek is regtig net hierdie up
hier as 'n illustrasie van 'n punt

100
00:05:08,260 --> 00:05:10,176
dat ek gaan wees
maak in 'n tweede, wat

101
00:05:10,176 --> 00:05:12,980
is dat ons net regtig omgee
oor die neiging van dinge

102
00:05:12,980 --> 00:05:14,870
as die data-stelle te kry groter.

103
00:05:14,870 --> 00:05:18,220
So as die datastel is klein, daar is
eintlik 'n mooi groot verskil

104
00:05:18,220 --> 00:05:19,870
in hierdie algoritmes.

105
00:05:19,870 --> 00:05:23,000
Die derde algoritme daar
neem 13 keer langer,

106
00:05:23,000 --> 00:05:27,980
13 keer die bedrag van hulpbronne
om te hardloop met betrekking tot die eerste een.

107
00:05:27,980 --> 00:05:31,659
>> As ons datastel is die grootte 10, wat
is groter, maar nie noodwendig groot,

108
00:05:31,659 --> 00:05:33,950
ons kan sien dat daar
eintlik 'n bietjie van 'n verskil maak.

109
00:05:33,950 --> 00:05:36,620
Die derde algoritme
raak meer doeltreffend te maak.

110
00:05:36,620 --> 00:05:40,120
Dit gaan oor die werklikheid 40% -
of 60% meer doeltreffend te maak.

111
00:05:40,120 --> 00:05:41,580
Dit neem 40% van die bedrag van die tyd.

112
00:05:41,580 --> 00:05:45,250
Dit kan run-- dit kan neem
400 eenhede van hulpbronne

113
00:05:45,250 --> 00:05:47,570
om 'n datastel grootte 10 verwerk.

114
00:05:47,570 --> 00:05:49,410
Terwyl die eerste
algoritme, daarenteen,

115
00:05:49,410 --> 00:05:54,520
neem 1000 eenhede van hulpbronne
om 'n datastel grootte 10 verwerk.

116
00:05:54,520 --> 00:05:57,240
Maar kyk wat gebeur as
ons getalle te kry, selfs groter.

117
00:05:57,240 --> 00:05:59,500
>> Nou, die verskil
tussen hierdie algoritmes

118
00:05:59,500 --> 00:06:01,420
begin om 'n bietjie minder duidelik geword.

119
00:06:01,420 --> 00:06:04,560
En die feit dat daar
laer-orde terms-- of eerder,

120
00:06:04,560 --> 00:06:09,390
terme met laer exponents--
begin om irrelevant te word.

121
00:06:09,390 --> 00:06:12,290
As 'n datastel is die grootte
1000 en die eerste algoritme

122
00:06:12,290 --> 00:06:14,170
loop in 'n miljard stappe.

123
00:06:14,170 --> 00:06:17,880
En die tweede algoritme loop in
'n miljard en 'n miljoen stappe.

124
00:06:17,880 --> 00:06:20,870
En die derde algoritme loop
in net minder as 'n miljard stappe.

125
00:06:20,870 --> 00:06:22,620
Dit is nogals 'n miljard stappe.

126
00:06:22,620 --> 00:06:25,640
Diegene laer-orde terme begin
om werklik irrelevant geword.

127
00:06:25,640 --> 00:06:27,390
En net om werklik
hamer huis die point--

128
00:06:27,390 --> 00:06:31,240
indien die data insette is van grootte van 'n
million-- al drie hierdie pretty much

129
00:06:31,240 --> 00:06:34,960
een neem quintillion-- as
my wiskunde is correct-- stappe

130
00:06:34,960 --> 00:06:37,260
om 'n data insette verwerk
grootte van 'n miljoen.

131
00:06:37,260 --> 00:06:38,250
Dit is 'n baie stappe.

132
00:06:38,250 --> 00:06:42,092
En die feit dat een van hulle dalk
neem 'n paar 100,000, of 'n paar 100

133
00:06:42,092 --> 00:06:44,650
miljoen selfs minder as
ons praat oor 'n aantal

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

135
00:06:46,990 --> 00:06:50,006
Hulle het almal geneig om te neem
ongeveer N blokkies,

136
00:06:50,006 --> 00:06:52,380
en so sal ons eintlik verwys
om al hierdie algoritmes

137
00:06:52,380 --> 00:06:59,520
as op die einde van N
blokkies of groot-O van n blokkies.

138
00:06:59,520 --> 00:07:03,220
>> Hier is 'n lys van sommige van die meer
algemene rekenkundige kompleksiteit klasse

139
00:07:03,220 --> 00:07:05,820
dat ons sal teëkom in
algoritmes, oor die algemeen.

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

141
00:07:07,970 --> 00:07:11,410
Hierdie is bestel
algemeen vinnigste by die top,

142
00:07:11,410 --> 00:07:13,940
algemeen stadigste aan die onderkant.

143
00:07:13,940 --> 00:07:16,920
So konstante time algoritmes is geneig
die vinnigste wees, ongeag

144
00:07:16,920 --> 00:07:19,110
van die grootte van die
data insette wat jy slaag in.

145
00:07:19,110 --> 00:07:23,760
Hulle het altyd een operasie of
een eenheid van hulpbronne te hanteer.

146
00:07:23,760 --> 00:07:25,730
Dit kan wees 2, dit dalk
wees 3, kan dit wees 4.

147
00:07:25,730 --> 00:07:26,910
Maar dit is 'n konstante getal is.

148
00:07:26,910 --> 00:07:28,400
Dit maak nie wissel.

149
00:07:28,400 --> 00:07:31,390
>> Logaritmiese time algoritmes
is effens beter.

150
00:07:31,390 --> 00:07:33,950
En 'n baie goeie voorbeeld van
'n logaritmiese tyd algoritme

151
00:07:33,950 --> 00:07:37,420
sekerlik gesien het deur die nou is die
uitmekaar skeur van die telefoon boek

152
00:07:37,420 --> 00:07:39,480
Mike Smith vind in die telefoon boek.

153
00:07:39,480 --> 00:07:40,980
Ons sny die probleem in die helfte.

154
00:07:40,980 --> 00:07:43,580
En so n groter word
en groter en larger--

155
00:07:43,580 --> 00:07:47,290
in werklikheid, elke keer as jy dubbel
N, dit neem net nog 'n stap.

156
00:07:47,290 --> 00:07:49,770
So dit is 'n baie beter
as, sê, lineêre tyd.

157
00:07:49,770 --> 00:07:53,030
Wat is as jy dubbel N, is dit
neem dubbel die aantal stappe.

158
00:07:53,030 --> 00:07:55,980
As jy verdriedubbel n, dit neem
verdriedubbel die aantal stappe.

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

160
00:07:58,580 --> 00:08:01,790
>> Toe dinge 'n bietjie more--
bietjie minder groot van daar af.

161
00:08:01,790 --> 00:08:06,622
Jy het lineêre ritmiese tyd, soms
genoem log lineêre tyd of net n teken n.

162
00:08:06,622 --> 00:08:08,330
En ons sal 'n voorbeeld
van 'n algoritme wat

163
00:08:08,330 --> 00:08:13,370
lopies in n log n, wat is nog steeds beter
as kwadratiese time-- N kwadraat.

164
00:08:13,370 --> 00:08:17,320
Of polinoom tyd, n twee
enige getal groter as twee.

165
00:08:17,320 --> 00:08:20,810
Of eksponensiële tyd, wat
selfs worse-- C om die n.

166
00:08:20,810 --> 00:08:24,670
So 'n paar konstante aantal opgewek
die krag van die grootte van die insette.

167
00:08:24,670 --> 00:08:28,990
So as daar is 1,000-- indien die
data insette is van die grootte 1000,

168
00:08:28,990 --> 00:08:31,310
dit sou neem om die C 1000 krag.

169
00:08:31,310 --> 00:08:33,559
Dit is 'n baie erger as polinoom tyd.

170
00:08:33,559 --> 00:08:35,030
>> Faktoriaal tyd is nog erger.

171
00:08:35,030 --> 00:08:37,760
En in die feit, daar is regtig nie
bestaan ​​oneindige tyd algoritmes,

172
00:08:37,760 --> 00:08:43,740
soos sogenaamde stupid sort-- wie
werk is om lukraak shuffle 'n skikking

173
00:08:43,740 --> 00:08:45,490
en dan check om te sien
of dit gesorteer.

174
00:08:45,490 --> 00:08:47,589
En as dit is nie, lukraak
shuffle die skikking weer

175
00:08:47,589 --> 00:08:49,130
en kyk om te sien of dit gesorteer.

176
00:08:49,130 --> 00:08:51,671
En as jy kan waarskynlik imagine--
jy kan 'n situasie indink

177
00:08:51,671 --> 00:08:55,200
waar in die ergste geval, dit sal
nooit eintlik begin met die skikking.

178
00:08:55,200 --> 00:08:57,150
Dit algoritme sal vir ewig te hardloop.

179
00:08:57,150 --> 00:08:59,349
En so sou dit 'n wees
oneindige tyd algoritme.

180
00:08:59,349 --> 00:09:01,890
Hopelik sal jy nie skryf
enige faktoriaal of oneindige tyd

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

182
00:09:04,510 --> 00:09:09,150
>> So, laat ons 'n bietjie meer
beton blik op sommige eenvoudiger

183
00:09:09,150 --> 00:09:11,154
rekenkundige kompleksiteit klasse.

184
00:09:11,154 --> 00:09:13,070
So ons het 'n example--
of twee voorbeelde here--

185
00:09:13,070 --> 00:09:15,590
van konstante tyd algoritmes,
wat altyd

186
00:09:15,590 --> 00:09:17,980
'n enkele operasie in die ergste geval.

187
00:09:17,980 --> 00:09:20,050
So die eerste example--
ons het 'n funksie

188
00:09:20,050 --> 00:09:23,952
genoem 4 vir jou, wat
neem 'n verskeidenheid van grootte 1000.

189
00:09:23,952 --> 00:09:25,660
Maar dan blykbaar
nie eintlik kyk

190
00:09:25,660 --> 00:09:29,000
op it-- nie regtig omgee wat is
binnekant van dit, van daardie skikking.

191
00:09:29,000 --> 00:09:30,820
Net altyd terug vier.

192
00:09:30,820 --> 00:09:32,940
So, wat algoritme,
ten spyte van die feit dat dit

193
00:09:32,940 --> 00:09:35,840
neem 1000 elemente nie
enigiets doen met hulle.

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

195
00:09:36,590 --> 00:09:38,240
Dit is altyd 'n enkele stap.

196
00:09:38,240 --> 00:09:41,600
>> In werklikheid, voeg 2 nums-- wat
ons voor as well-- gesien het

197
00:09:41,600 --> 00:09:43,680
net verwerk twee heelgetalle.

198
00:09:43,680 --> 00:09:44,692
Dit is nie 'n enkele stap.

199
00:09:44,692 --> 00:09:45,900
Dit is eintlik 'n paar stappe.

200
00:09:45,900 --> 00:09:50,780
Jy kry 'n, jy b, jy voeg
saam, en jy uitset die resultate.

201
00:09:50,780 --> 00:09:53,270
So dit is 84 stappe.

202
00:09:53,270 --> 00:09:55,510
Maar dit is altyd konstant,
ongeag of 'n b.

203
00:09:55,510 --> 00:09:59,240
Jy moet 'n te kry, kry b, voeg
hulle saam, uitset die resultaat.

204
00:09:59,240 --> 00:10:02,900
So dit is 'n konstante tyd algoritme.

205
00:10:02,900 --> 00:10:05,170
>> Hier is 'n voorbeeld van 'n
lineêre tyd algorithm--

206
00:10:05,170 --> 00:10:08,740
'n algoritme wat gets-- wat neem
een addisionele stap, moontlik,

207
00:10:08,740 --> 00:10:10,740
as jou insette groei deur 1.

208
00:10:10,740 --> 00:10:14,190
So, kom ons sê ons is op soek na
die nommer 5 binnekant van 'n skikking.

209
00:10:14,190 --> 00:10:16,774
Jy kan 'n situasie waar het
jy kan vind dit redelik vroeg.

210
00:10:16,774 --> 00:10:18,606
Maar jy kan ook '
'n situasie waar dit

211
00:10:18,606 --> 00:10:20,450
dalk die laaste element van die skikking wees.

212
00:10:20,450 --> 00:10:23,780
In 'n skikking van grootte 5, indien
Ons is op soek na die nommer 5.

213
00:10:23,780 --> 00:10:25,930
Dit sou 5 stappe te neem.

214
00:10:25,930 --> 00:10:29,180
En in die feit, dink dat daar
nie 5 oral in hierdie reeks.

215
00:10:29,180 --> 00:10:32,820
Ons het nog steeds eintlik moet kyk na
elke enkele element van die skikking

216
00:10:32,820 --> 00:10:35,550
ten einde te bepaal
of 5 is daar.

217
00:10:35,550 --> 00:10:39,840
>> So in die ergste geval, en dit is dat
die element is die laaste in die skikking

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

219
00:10:41,700 --> 00:10:44,690
Ons het nog om te kyk na
al die elemente N.

220
00:10:44,690 --> 00:10:47,120
En so hierdie algoritme
loop in lineêre tyd.

221
00:10:47,120 --> 00:10:50,340
Jy kan bevestig dat deur
ekstrapoleer 'n bietjie deur te sê,

222
00:10:50,340 --> 00:10:53,080
as ons het 'n 6-element skikking en
Ons was op soek na die nommer 5,

223
00:10:53,080 --> 00:10:54,890
dit dalk 6 stappe te neem.

224
00:10:54,890 --> 00:10:57,620
As ons 'n 7-element skikking en
Ons is op soek na die nommer 5.

225
00:10:57,620 --> 00:10:59,160
Dit mag dalk 7 stappe te neem.

226
00:10:59,160 --> 00:11:02,920
As ons by te voeg 'n meer element aan ons
skikking, dit neem 'n stap.

227
00:11:02,920 --> 00:11:06,750
Dit is 'n lineêre algoritme
in die ergste geval.

228
00:11:06,750 --> 00:11:08,270
>> Paar vinnige vrae vir jou.

229
00:11:08,270 --> 00:11:11,170
Wat is die runtime-- wat is
die ergste geval runtime

230
00:11:11,170 --> 00:11:13,700
van hierdie spesifieke brokkie kode?

231
00:11:13,700 --> 00:11:17,420
So ek het 'n 4 lus hier wat loop
van J gelyk 0, al die pad tot m.

232
00:11:17,420 --> 00:11:21,980
En wat ek hier sien, is dat die
liggaam van die lus loop in konstante tyd.

233
00:11:21,980 --> 00:11:24,730
So die gebruik van die terminologie wat
ons het reeds about-- wat gepraat

234
00:11:24,730 --> 00:11:29,390
sou die ergste geval wees
runtime van hierdie algoritme?

235
00:11:29,390 --> 00:11:31,050
Neem 'n tweede.

236
00:11:31,050 --> 00:11:34,270
Die binneste deel van die lus
loop in konstante tyd.

237
00:11:34,270 --> 00:11:37,510
En die buitenste deel van die
lus gaan m keer hardloop.

238
00:11:37,510 --> 00:11:40,260
So, wat is die ergste geval runtime hier?

239
00:11:40,260 --> 00:11:43,210
Het jy 'n groot-O van m raai?

240
00:11:43,210 --> 00:11:44,686
Jy wil reg wees.

241
00:11:44,686 --> 00:11:46,230
>> Hoe oor 'n ander een?

242
00:11:46,230 --> 00:11:48,590
Hierdie keer het ons 'n
lus binnekant van 'n lus.

243
00:11:48,590 --> 00:11:50,905
Ons het 'n buitenste lus
wat loop van nul tot p.

244
00:11:50,905 --> 00:11:54,630
En ons het 'n innerlike lus wat loop
van nul tot p, en binnekant van die,

245
00:11:54,630 --> 00:11:57,890
Ek verklaar dat die liggaam die
lus loop in konstante tyd.

246
00:11:57,890 --> 00:12:02,330
So, wat is die ergste geval runtime
van hierdie spesifieke brokkie kode?

247
00:12:02,330 --> 00:12:06,140
Wel, weer, ons het 'n
buitenste lus wat p keer loop.

248
00:12:06,140 --> 00:12:09,660
En elke time-- iterasie
van daardie lus, eerder.

249
00:12:09,660 --> 00:12:13,170
Ons het 'n innerlike lus
wat ook loop p keer.

250
00:12:13,170 --> 00:12:16,900
En dan binnekant van daardie, is daar die
konstante time-- bietjie brokkie daar.

251
00:12:16,900 --> 00:12:19,890
>> So as ons 'n buitenste lus wat
loop p keer binnekant van wat

252
00:12:19,890 --> 00:12:22,880
'n innerlike lus wat
loop p times-- wat

253
00:12:22,880 --> 00:12:26,480
die ergste geval runtime
van hierdie kode uit?

254
00:12:26,480 --> 00:12:30,730
Het jy 'n groot-O p raai kwadraat?

255
00:12:30,730 --> 00:12:31,690
>> Ek is Doug Lloyd.

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

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