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

2
00:00:05,830 --> 00:00:07,910
>> Rendben, szóval, számítási komplexitás.

3
00:00:07,910 --> 00:00:10,430
Csak egy kis figyelmeztetés
mielőtt belevetik túl far--

4
00:00:10,430 --> 00:00:13,070
ez akkor valószínűleg körében
A legtöbb matematikai nehéz dolog

5
00:00:13,070 --> 00:00:14,200
beszélünk a CS50.

6
00:00:14,200 --> 00:00:16,950
Remélhetőleg nem lesz túl nyomasztó
és megpróbáljuk, és végigvezeti Önt

7
00:00:16,950 --> 00:00:19,200
keresztül a folyamat, de
Csak egy kicsit tisztességes figyelmeztetést.

8
00:00:19,200 --> 00:00:21,282
Van egy kicsit
A matematikai részt itt.

9
00:00:21,282 --> 00:00:23,990
Rendben, így annak érdekében, hogy
felhasználása a számítási erőforrások

10
00:00:23,990 --> 00:00:28,170
A valós world-- ez tényleg
Fontos megérteni algoritmusok

11
00:00:28,170 --> 00:00:30,750
és hogyan dolgozzák fel az adatokat.

12
00:00:30,750 --> 00:00:32,810
Ha van egy igazán
hatékony algoritmust, mi

13
00:00:32,810 --> 00:00:36,292
csökkenti a források összege
a rendelkezésünkre álló foglalkozni vele.

14
00:00:36,292 --> 00:00:38,750
Ha van egy algoritmus, amely
fog tartani a sok munka

15
00:00:38,750 --> 00:00:41,210
feldolgozni egy igazán
nagy adathalmazt, ez

16
00:00:41,210 --> 00:00:44,030
lesz szükség több
és több erőforrást, amely

17
00:00:44,030 --> 00:00:47,980
pénz, RAM, minden ilyesmi.

18
00:00:47,980 --> 00:00:52,090
>> Tehát, hogy képes elemezni a
algoritmust használja ezt az eszközt sor,

19
00:00:52,090 --> 00:00:56,110
Alapvetően arra kéri a question--
hogyan működik ez az algoritmus skálán

20
00:00:56,110 --> 00:00:59,020
ahogy dobja egyre több adat kerül ez?

21
00:00:59,020 --> 00:01:02,220
Ebben CS50, az adatok mennyisége vagyunk
dolgozik elég kicsi.

22
00:01:02,220 --> 00:01:05,140
Általában a programok folynak
futtatni egy második vagy less--

23
00:01:05,140 --> 00:01:07,830
Valószínűleg sokkal kevesebb
Különösen az elején.

24
00:01:07,830 --> 00:01:12,250
>> De gondolj olyan cég, amely foglalkozik
több száz millió ügyfél.

25
00:01:12,250 --> 00:01:14,970
És kell feldolgozniuk
hogy az ügyfelek adatait.

26
00:01:14,970 --> 00:01:18,260
Mivel az ügyfelek száma általuk
van egyre nagyobb és nagyobb,

27
00:01:18,260 --> 00:01:21,230
ez fog igényelni
több és több erőforrást.

28
00:01:21,230 --> 00:01:22,926
Hány több forrást?

29
00:01:22,926 --> 00:01:25,050
Nos, ez attól függ, hogy
elemezzük az algoritmust,

30
00:01:25,050 --> 00:01:28,097
eszközeivel eszköztár.

31
00:01:28,097 --> 00:01:31,180
Amikor arról beszélünk, összetettsége
Egy algorithm-- amely néha akkor

32
00:01:31,180 --> 00:01:34,040
hallani nevezik idő
bonyolultsága vagy térben összetettsége

33
00:01:34,040 --> 00:01:36,190
de mi csak megy
hívni complexity--

34
00:01:36,190 --> 00:01:38,770
mi általában beszélünk
A legrosszabb forgatókönyv.

35
00:01:38,770 --> 00:01:42,640
Mivel az abszolút legrosszabb halom
adatok, hogy mi lehetne dobott rajta,

36
00:01:42,640 --> 00:01:46,440
hogyan van ez algoritmust fog
feldolgozni és kezelni az adatokat?

37
00:01:46,440 --> 00:01:51,450
Általánosságban az a legrosszabb
futásidejű algoritmus nagy O.

38
00:01:51,450 --> 00:01:56,770
Tehát egy algoritmus lehet mondani,
futnak O n vagy O n négyzeten.

39
00:01:56,770 --> 00:01:59,110
És még mit
azokat jelenti a második.

40
00:01:59,110 --> 00:02:01,620
>> Néha azonban, mi ellátás
a legjobb esetben.

41
00:02:01,620 --> 00:02:05,400
Ha az adatok mindent, amit akartunk
hogy legyen, és ez abszolút tökéletes volt

42
00:02:05,400 --> 00:02:09,630
és mi volt küldése tökéletes
adathalmazt keresztül algoritmus.

43
00:02:09,630 --> 00:02:11,470
Milyen lenne kezelni ebben a helyzetben?

44
00:02:11,470 --> 00:02:15,050
Néha arra utalnak, hogy a
nagy-Omega, így szemben a nagy-O,

45
00:02:15,050 --> 00:02:16,530
már nagy-Omega.

46
00:02:16,530 --> 00:02:18,880
Nagy-Omega a legjobb eset.

47
00:02:18,880 --> 00:02:21,319
Big-O a legrosszabb forgatókönyv.

48
00:02:21,319 --> 00:02:23,860
Általában, ha beszélünk
összetettsége egy algoritmus,

49
00:02:23,860 --> 00:02:26,370
beszélünk a
a legrosszabb esetben.

50
00:02:26,370 --> 00:02:28,100
Tehát hogy tartsa szem előtt.

51
00:02:28,100 --> 00:02:31,510
>> És ebben az osztályban, mi általában lesz
elhagyni a szigorú elemzés félre.

52
00:02:31,510 --> 00:02:35,350
Vannak tudományok és mezők
szentelt ilyen cucc.

53
00:02:35,350 --> 00:02:37,610
Amikor arról beszélünk, indokolás
algoritmusok segítségével,

54
00:02:37,610 --> 00:02:41,822
amit megteszek darab-by-darab a sok
algoritmusok beszélünk az osztályban.

55
00:02:41,822 --> 00:02:44,780
Mi tényleg csak beszél
érvelés rajta a józan ész,

56
00:02:44,780 --> 00:02:47,070
Nem képletek, vagy bizonyítékokat,
vagy ilyesmi.

57
00:02:47,070 --> 00:02:51,600
Szóval ne aggódj, nem lesz
fordult egy nagy matekórán.

58
00:02:51,600 --> 00:02:55,920
>> Szóval azt mondtam törődünk összetettsége
mert azt a kérdést, hogy hogyan

59
00:02:55,920 --> 00:03:00,160
nem az algoritmusok kezelni a nagyobb és
Nagy adathalmazok dobálnak rájuk.

60
00:03:00,160 --> 00:03:01,960
Nos, mi egy adathalmaz?

61
00:03:01,960 --> 00:03:03,910
Mit gondolok, amikor azt mondta, hogy?

62
00:03:03,910 --> 00:03:07,600
Ez azt jelenti, bármi is okozza a legtöbb
értelme az összefüggésben, hogy őszinte legyek.

63
00:03:07,600 --> 00:03:11,160
Ha van egy algoritmus, a
Folyamatok Strings-- akkor alighanem

64
00:03:11,160 --> 00:03:13,440
beszél a méret a húr.

65
00:03:13,440 --> 00:03:15,190
Ez az adat set--
a méret, a szám

66
00:03:15,190 --> 00:03:17,050
karakterek alkotják a húr.

67
00:03:17,050 --> 00:03:20,090
Ha beszélünk egy
algoritmust, amely feldolgozza a fájlokat,

68
00:03:20,090 --> 00:03:23,930
mi lehet beszélni, hogyan
Sok kilobyte tartalmaznak, hogy a fájl.

69
00:03:23,930 --> 00:03:25,710
És ez az adathalmaz.

70
00:03:25,710 --> 00:03:28,870
Ha beszélünk egy algoritmus
amely kezeli tömbök általában

71
00:03:28,870 --> 00:03:31,510
mint például a rendezési algoritmusok
vagy keresőalgoritmust,

72
00:03:31,510 --> 00:03:36,690
akkor alighanem beszélünk száma
Az alkotó elemek egy tömbben.

73
00:03:36,690 --> 00:03:39,272
>> Most tudjuk mérni egy
algorithm-- különösen,

74
00:03:39,272 --> 00:03:40,980
amikor azt mondom, amit lehet
mérésére egy algoritmus, azt

75
00:03:40,980 --> 00:03:43,840
jelenti azt, hogy mennyire
sok erőforrást vesz fel.

76
00:03:43,840 --> 00:03:48,990
Hogy ezek a források, hogy hány
byte RAM-- vagy megabájt RAM-mal

77
00:03:48,990 --> 00:03:49,790
használ.

78
00:03:49,790 --> 00:03:52,320
Vagy mennyi idő kell ahhoz, hogy fusson.

79
00:03:52,320 --> 00:03:56,200
És nevezhetjük ezt
mérésére, önkényesen, f n.

80
00:03:56,200 --> 00:03:59,420
Ahol N a száma
elemek a adathalmaz.

81
00:03:59,420 --> 00:04:02,640
És f n hány asok.

82
00:04:02,640 --> 00:04:07,530
Hány egységnyi nyersanyagot nem
követeli, hogy feldolgozza az adatokat.

83
00:04:07,530 --> 00:04:10,030
>> Most, hogy igazából nem érdekel
mit f n pontosan.

84
00:04:10,030 --> 00:04:13,700
Sőt, mi nagyon ritkán will--
biztosan nem ebben a class-- I

85
00:04:13,700 --> 00:04:18,709
belevetik magukat a valóban mély
elemzést, amit f n van.

86
00:04:18,709 --> 00:04:23,510
Mi csak beszélgetünk, milyen f
n kb vagy mit is hajlamos.

87
00:04:23,510 --> 00:04:27,600
És az a tendencia, az algoritmus
diktálta a legmagasabb rendű távon.

88
00:04:27,600 --> 00:04:29,440
És azt látjuk, amit én
ez alatt azáltal, hogy

89
00:04:29,440 --> 00:04:31,910
Egy pillantás egy konkrét példát.

90
00:04:31,910 --> 00:04:34,620
>> Tehát mondjuk, hogy van
Három különböző algoritmusok.

91
00:04:34,620 --> 00:04:39,350
Az első, amely úgy n
kockára vágott, néhány egység erőforrások

92
00:04:39,350 --> 00:04:42,880
feldolgozni egy adathalmaz n méretű.

93
00:04:42,880 --> 00:04:47,000
Van egy másik algoritmust tartalmaz,
n kockára vágott + n faragva erőforrások

94
00:04:47,000 --> 00:04:49,350
feldolgozni egy adathalmaz n méretű.

95
00:04:49,350 --> 00:04:52,030
És van egy harmadik
algoritmus fut in--, hogy

96
00:04:52,030 --> 00:04:58,300
felveszi n kockára vágott mínusz 8 n faragva
plusz 20 n egységnyi nyersanyagot

97
00:04:58,300 --> 00:05:02,370
feldolgozni egy algoritmus
A adatállomány n méretű.

98
00:05:02,370 --> 00:05:05,594
>> Most újra, igazán nem megy
bejutni ilyen szintű részletesség.

99
00:05:05,594 --> 00:05:08,260
Én tényleg csak e fel
Itt az illusztráció egy pont

100
00:05:08,260 --> 00:05:10,176
hogy én leszek
így egy második, amely

101
00:05:10,176 --> 00:05:12,980
hogy mi csak igazán érdekel
a tendencia a dolgokat

102
00:05:12,980 --> 00:05:14,870
mint az adatsorok kap nagyobb.

103
00:05:14,870 --> 00:05:18,220
Tehát, ha az adathalmaz kicsi, van
valójában egy elég nagy különbség

104
00:05:18,220 --> 00:05:19,870
Ezekben algoritmusok.

105
00:05:19,870 --> 00:05:23,000
A harmadik algoritmus létezik
úgy 13-szer hosszabb,

106
00:05:23,000 --> 00:05:27,980
13-szer annyi erőforrások
futtatni képest az első.

107
00:05:27,980 --> 00:05:31,659
>> Ha mi adathalmaz mérete 10, amely
nagyobb, de nem szükségszerűen hatalmas,

108
00:05:31,659 --> 00:05:33,950
azt látjuk, hogy van
valójában egy kicsit a különbség.

109
00:05:33,950 --> 00:05:36,620
A harmadik algoritmus
hatékonyabbá válik.

110
00:05:36,620 --> 00:05:40,120
Arról van szó, valójában 40% -
vagy 60% -kal hatékonyabb.

111
00:05:40,120 --> 00:05:41,580
Tart 40% az az idő.

112
00:05:41,580 --> 00:05:45,250
Ez run-- is eltarthat
400 egység erőforrások

113
00:05:45,250 --> 00:05:47,570
feldolgozni egy adathalmaz mérete 10.

114
00:05:47,570 --> 00:05:49,410
Míg az első
algoritmus, ezzel szemben,

115
00:05:49,410 --> 00:05:54,520
úgy 1000 egységnyi nyersanyagot
feldolgozni egy adathalmaz mérete 10.

116
00:05:54,520 --> 00:05:57,240
De nézd mi történik, amint
a számok, hogy még nagyobb.

117
00:05:57,240 --> 00:05:59,500
>> Most, a különbség
ezek között algoritmusok

118
00:05:59,500 --> 00:06:01,420
kezd válni egy kicsit kevésbé nyilvánvaló.

119
00:06:01,420 --> 00:06:04,560
És az a tény, hogy vannak
alacsonyabb rendű terms-- vagy inkább,

120
00:06:04,560 --> 00:06:09,390
szempontjából alacsonyabb exponents--
kezd válni.

121
00:06:09,390 --> 00:06:12,290
Ha egy adathalmaz mérete
1,000 és az első algoritmus

122
00:06:12,290 --> 00:06:14,170
fut egy milliárd lépéseket.

123
00:06:14,170 --> 00:06:17,880
És a második algoritmus fut
Egy milliárd millió lépés.

124
00:06:17,880 --> 00:06:20,870
És a harmadik algoritmus fut
A Röpke egy milliárd lépéseket.

125
00:06:20,870 --> 00:06:22,620
Ez nagyjából egymilliárd lépéseket.

126
00:06:22,620 --> 00:06:25,640
Ezeket az alsó-rendű tagokat indul
válni igazán releváns.

127
00:06:25,640 --> 00:06:27,390
És csak azért, hogy valóban
kalapács haza a point--

128
00:06:27,390 --> 00:06:31,240
ha az adatbevitel a méret a
million-- mindhárom elég sok

129
00:06:31,240 --> 00:06:34,960
hogy egy quintillion-- ha
én matek correct-- lépések

130
00:06:34,960 --> 00:06:37,260
feldolgozni egy adatbeviteli
A méret egy millió.

131
00:06:37,260 --> 00:06:38,250
Ez egy csomó lépést.

132
00:06:38,250 --> 00:06:42,092
És az a tény, hogy egyikük talán
hogy pár 100.000, vagy egy pár 100

133
00:06:42,092 --> 00:06:44,650
millió még kevésbé, ha
beszélünk több

134
00:06:44,650 --> 00:06:46,990
hogy big-- ez a fajta lényegtelen.

135
00:06:46,990 --> 00:06:50,006
Mindannyian hajlamosak arra, hogy
mintegy n kockára vágott,

136
00:06:50,006 --> 00:06:52,380
alatt, ezért ténylegesen hivatkozni
hogy az összes ilyen algoritmusok

137
00:06:52,380 --> 00:06:59,520
mint a sorrendben a N
kockára vágott, vagy a nagy O-n a köbön.

138
00:06:59,520 --> 00:07:03,220
>> Itt van egy lista néhány a több
közös számítási komplexitás osztályok

139
00:07:03,220 --> 00:07:05,820
hogy mi lesz találkozás
algoritmusok, általában.

140
00:07:05,820 --> 00:07:07,970
És azt is, konkrétan a CS50.

141
00:07:07,970 --> 00:07:11,410
Ezek megrendelt
általában leggyorsabb a tetején,

142
00:07:11,410 --> 00:07:13,940
hogy általában leglassabb az alján.

143
00:07:13,940 --> 00:07:16,920
Tehát állandó idejű algoritmusok hajlamosak
hogy a leggyorsabb, függetlenül attól,

144
00:07:16,920 --> 00:07:19,110
A méret a
adatbevitel elmész.

145
00:07:19,110 --> 00:07:23,760
Ők mindig egy művelet vagy
egységnyi erőforrás áll rendelkezésére.

146
00:07:23,760 --> 00:07:25,730
Lehet, hogy a 2., talán
legyen 3, lehet, hogy 4.

147
00:07:25,730 --> 00:07:26,910
De ez egy állandó számot.

148
00:07:26,910 --> 00:07:28,400
Ez nem változik.

149
00:07:28,400 --> 00:07:31,390
>> Logaritmikus időben algoritmusok
valamivel jobb.

150
00:07:31,390 --> 00:07:33,950
És egy igazán jó példa
logaritmikus algoritmust

151
00:07:33,950 --> 00:07:37,420
amit biztosan látott már a
tépte szét a telefonkönyv

152
00:07:37,420 --> 00:07:39,480
találni Mike Smith a telefonkönyvben.

153
00:07:39,480 --> 00:07:40,980
Vágjuk a probléma felét.

154
00:07:40,980 --> 00:07:43,580
És így n nagyobb lesz
és nagyobb és larger--

155
00:07:43,580 --> 00:07:47,290
sőt, minden alkalommal, ha kétszer
n, csak úgy egy lépést.

156
00:07:47,290 --> 00:07:49,770
Szóval ez egy sokkal jobb
mint mondjuk a lineáris idő.

157
00:07:49,770 --> 00:07:53,030
Amely, ha kétszeresére n, akkor
veszi kettős a lépések számát.

158
00:07:53,030 --> 00:07:55,980
Ha megháromszorozódik n, tart
megháromszorozza a lépések számát.

159
00:07:55,980 --> 00:07:58,580
Egy lépés egységenként.

160
00:07:58,580 --> 00:08:01,790
>> Aztán a dolgok egy kicsit more--
kicsit kevésbé jó onnan.

161
00:08:01,790 --> 00:08:06,622
Van lineáris ritmikus, néha
úgynevezett log lineáris idő, vagy csak n log n.

162
00:08:06,622 --> 00:08:08,330
És mi egy példa
Az egy algoritmus, hogy

163
00:08:08,330 --> 00:08:13,370
fut n log n, ami még mindig jobb,
mint másodfokú time-- n faragva.

164
00:08:13,370 --> 00:08:17,320
Vagy polinomiális n két
meghaladó tetszőleges kettő.

165
00:08:17,320 --> 00:08:20,810
Vagy exponenciális időt, amely
még worse-- C és az N.

166
00:08:20,810 --> 00:08:24,670
Szóval néhány állandó számú emelt
A hatalom a bemenet mérete.

167
00:08:24,670 --> 00:08:28,990
Szóval, ha van 1,000-- ha a
adatbevitel mérete 1000,

168
00:08:28,990 --> 00:08:31,310
telne C a 1000. hatalom.

169
00:08:31,310 --> 00:08:33,559
Ez sokkal rosszabb, mint polinomiális időben.

170
00:08:33,559 --> 00:08:35,030
>> Factorial idő még rosszabb.

171
00:08:35,030 --> 00:08:37,760
És valóban, ott tényleg
létezik végtelen idő algoritmusok,

172
00:08:37,760 --> 00:08:43,740
mint például, az úgynevezett buta sort-- akinek
feladata, hogy véletlenszerűen összekeveri a tömb elemeit

173
00:08:43,740 --> 00:08:45,490
és nézze meg, hogy
legyen szó válogatni.

174
00:08:45,490 --> 00:08:47,589
És ha ez nem, véletlenszerűen
shuffle a tömb újra

175
00:08:47,589 --> 00:08:49,130
és nézze meg, hogy ez válogatni.

176
00:08:49,130 --> 00:08:51,671
És ahogy tudod talán imagine--
el lehet képzelni olyan helyzetet

177
00:08:51,671 --> 00:08:55,200
ahol a legrosszabb eset, hogy akarata
sosem kezdeni a tömbben.

178
00:08:55,200 --> 00:08:57,150
Ez az algoritmus állna örökké.

179
00:08:57,150 --> 00:08:59,349
És így, hogy lenne
végtelen idejű algoritmus.

180
00:08:59,349 --> 00:09:01,890
Remélhetőleg nem lesz írás
minden faktoros vagy végtelen idő

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

182
00:09:04,510 --> 00:09:09,150
>> Tehát, vessünk egy kicsit
beton pillantást néhány egyszerűbb

183
00:09:09,150 --> 00:09:11,154
számítási komplexitás osztályok.

184
00:09:11,154 --> 00:09:13,070
Tehát van egy example--
-két példát here--

185
00:09:13,070 --> 00:09:15,590
Az állandó idejű algoritmusok,
amely mindig

186
00:09:15,590 --> 00:09:17,980
egyetlen művelettel a legrosszabb eset.

187
00:09:17,980 --> 00:09:20,050
Tehát az első example--
van egy funkció

188
00:09:20,050 --> 00:09:23,952
az úgynevezett 4 az Ön számára, amely
vesz egy sor mérete 1000.

189
00:09:23,952 --> 00:09:25,660
De akkor nyilván
valójában nem néz ki

190
00:09:25,660 --> 00:09:29,000
A it-- nem nagyon érdekli, mi van
belsejében is, a tömb.

191
00:09:29,000 --> 00:09:30,820
Mindig csak visszatér a négy.

192
00:09:30,820 --> 00:09:32,940
Szóval, ez az algoritmus,
annak ellenére, hogy ez

193
00:09:32,940 --> 00:09:35,840
úgy 1000 elemeket nem
mit kezdeni velük.

194
00:09:35,840 --> 00:09:36,590
Csak visszatér a négy.

195
00:09:36,590 --> 00:09:38,240
Ez mindig egy lépéssel.

196
00:09:38,240 --> 00:09:41,600
>> Tény, adjunk hozzá 2 nums-- amely
amit látott, mint well--

197
00:09:41,600 --> 00:09:43,680
Csak feldolgozza két egész szám.

198
00:09:43,680 --> 00:09:44,692
Ez nem egy lépésben.

199
00:09:44,692 --> 00:09:45,900
Ez valójában egy pár lépésre.

200
00:09:45,900 --> 00:09:50,780
Kapsz egy, kapsz b, felveszi őket
együtt, és akkor az eredmény kimentése.

201
00:09:50,780 --> 00:09:53,270
Tehát ez a 84 lépést.

202
00:09:53,270 --> 00:09:55,510
De ez mindig állandó,
függetlenül attól, hogy egy vagy b.

203
00:09:55,510 --> 00:09:59,240
Van, hogy egy, kap b, add
őket, kimeneti eredményét.

204
00:09:59,240 --> 00:10:02,900
Szóval ez egy állandó algoritmust.

205
00:10:02,900 --> 00:10:05,170
>> Íme egy példa egy
lineáris idő algorithm--

206
00:10:05,170 --> 00:10:08,740
egy algoritmus, hogy gets-- vevő
egy további lépés, esetleg,

207
00:10:08,740 --> 00:10:10,740
a bemenet növekszik 1.

208
00:10:10,740 --> 00:10:14,190
Tehát, mondjuk keresünk
Az 5-ös szám belsejében egy tömbben.

209
00:10:14,190 --> 00:10:16,774
Lehet, hogy olyan helyzetben, amikor
akkor ez egy nagyon jó korán.

210
00:10:16,774 --> 00:10:18,606
De akkor is van
olyan helyzetben, hogy

211
00:10:18,606 --> 00:10:20,450
Lehet, hogy az utolsó elem a tömbben.

212
00:10:20,450 --> 00:10:23,780
Az egy tömbben méretű 5, ha
keresünk száma 5.

213
00:10:23,780 --> 00:10:25,930
Telne 5 lépésben.

214
00:10:25,930 --> 00:10:29,180
És valóban, képzeljük el, hogy van
Nem 5 sehova ebben a tömbben.

215
00:10:29,180 --> 00:10:32,820
Még mindig ténylegesen meg kell nézni
minden egyes eleme a tömb

216
00:10:32,820 --> 00:10:35,550
annak érdekében, hogy meghatározzák
e vagy sem 5 ott van.

217
00:10:35,550 --> 00:10:39,840
>> Tehát a legrosszabb eset, ami az, hogy
Az elem utolsó a tömbben

218
00:10:39,840 --> 00:10:41,700
vagy nem is létezik.

219
00:10:41,700 --> 00:10:44,690
Még mindig meg kell nézni
mind az n elemekkel.

220
00:10:44,690 --> 00:10:47,120
És így ez az algoritmus
fut a lineáris időben.

221
00:10:47,120 --> 00:10:50,340
Te is megerősíti, hogy a
extrapolációjára egy kicsit, mondván,

222
00:10:50,340 --> 00:10:53,080
ha lenne egy 6-elem tömb és
kerestünk száma 5,

223
00:10:53,080 --> 00:10:54,890
ez eltart 6 lépésben.

224
00:10:54,890 --> 00:10:57,620
Ha van egy 7 tömböt és
keresünk száma 5.

225
00:10:57,620 --> 00:10:59,160
Ez eltarthat 7 lépéseket.

226
00:10:59,160 --> 00:11:02,920
Ahogy hozzá még egy eleme, hogy a
tömb, tart még egy lépést.

227
00:11:02,920 --> 00:11:06,750
Ez egy lineáris algoritmus
a legrosszabb esetben.

228
00:11:06,750 --> 00:11:08,270
>> Pár gyors kérdés az Ön számára.

229
00:11:08,270 --> 00:11:11,170
Mi a runtime-- mi
A legrosszabb futási

230
00:11:11,170 --> 00:11:13,700
Ezen adott kódrészletet?

231
00:11:13,700 --> 00:11:17,420
Szóval van egy 4 hurok van, hogy fut
a j értéke 0, egészen a m.

232
00:11:17,420 --> 00:11:21,980
És mit látok itt, hogy a
hurok teste fut állandóan időben.

233
00:11:21,980 --> 00:11:24,730
Tehát terminológiát használva, hogy
Már beszéltünk about-- mi

234
00:11:24,730 --> 00:11:29,390
lenne a legrosszabb
futási az algoritmus?

235
00:11:29,390 --> 00:11:31,050
Vegyünk egy pillanatra.

236
00:11:31,050 --> 00:11:34,270
A belső része a hurok
fut állandóan időben.

237
00:11:34,270 --> 00:11:37,510
És a külső része a
hurok fog futni m alkalommal.

238
00:11:37,510 --> 00:11:40,260
Szóval mi a legrosszabb eset runtime itt?

239
00:11:40,260 --> 00:11:43,210
Találta ki a nagy O-m?

240
00:11:43,210 --> 00:11:44,686
Igazad van.

241
00:11:44,686 --> 00:11:46,230
>> Mit szólnál egy másikat?

242
00:11:46,230 --> 00:11:48,590
Ezúttal egy
hurok belsejében egy hurok.

243
00:11:48,590 --> 00:11:50,905
Van egy külső hurok
futó nulláról p.

244
00:11:50,905 --> 00:11:54,630
És van egy belső kör, amely fut
nulláról p, és aztán az,

245
00:11:54,630 --> 00:11:57,890
Megállapítom, hogy a testület a
hurok fut állandóan időben.

246
00:11:57,890 --> 00:12:02,330
Szóval mi a legrosszabb eset runtime
Ezen adott kódrészletet?

247
00:12:02,330 --> 00:12:06,140
Nos, megint van egy
külső hurok fut p-szer.

248
00:12:06,140 --> 00:12:09,660
És minden time-- ismétlés
Az, hogy a hurok, inkább.

249
00:12:09,660 --> 00:12:13,170
Van egy belső hurok
futtatására is képes p-szer.

250
00:12:13,170 --> 00:12:16,900
És akkor aztán az, ott van a
állandó time-- kis részlet van.

251
00:12:16,900 --> 00:12:19,890
>> Tehát ha van egy külső hurok, amely
fut p-szer belsejében, amely

252
00:12:19,890 --> 00:12:22,880
egy belső hurok
fut p times-- mi

253
00:12:22,880 --> 00:12:26,480
A legrosszabb futási
E kódrészletet?

254
00:12:26,480 --> 00:12:30,730
Találta ki a nagy O-p faragva?

255
00:12:30,730 --> 00:12:31,690
>> Én Doug Lloyd.

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

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