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

2
00:00:05,830 --> 00:00:07,910
>> Olgu, nii, arvutuslik keerukus.

3
00:00:07,910 --> 00:00:10,430
Veidi hoiatuse
enne kui me sukelduda liiga far--

4
00:00:10,430 --> 00:00:13,070
see ilmselt seas
Kõige matemaatika-rasked asjad

5
00:00:13,070 --> 00:00:14,200
me räägime in CS50.

6
00:00:14,200 --> 00:00:16,950
Loodetavasti see ei tohi olla liiga suur
ja püüame ja juhendab teid

7
00:00:16,950 --> 00:00:19,200
protsessi kaudu, kuid
lihtsalt natuke õiglane hoiatus.

8
00:00:19,200 --> 00:00:21,282
Seal on natuke
matemaatika seotud siin.

9
00:00:21,282 --> 00:00:23,990
Olgu, nii et muuta
kasutada meie arvutiressursse

10
00:00:23,990 --> 00:00:28,170
reaalses world-- see on tõesti
oluline mõista, algoritmid

11
00:00:28,170 --> 00:00:30,750
ja kuidas nad andmeid töödelda.

12
00:00:30,750 --> 00:00:32,810
Kui meil on tõesti
tõhus algoritm, me

13
00:00:32,810 --> 00:00:36,292
võib vähendada ressursside hulga
meil saadaval, et sellega tegeleda.

14
00:00:36,292 --> 00:00:38,750
Kui meil on algoritm, mis
see aega võtab palju tööd

15
00:00:38,750 --> 00:00:41,210
töödelda tõesti
suure hulga andmeid, siis on

16
00:00:41,210 --> 00:00:44,030
läheb vaja rohkem
ja rohkem ressursse, mis

17
00:00:44,030 --> 00:00:47,980
on raha, RAM, kõik muu selline.

18
00:00:47,980 --> 00:00:52,090
>> Niisiis, olles võimeline analüüsima
algoritmi kasutades seda tööriista komplekti,

19
00:00:52,090 --> 00:00:56,110
Põhimõtteliselt palub question--
Kuidas see algoritm skaala

20
00:00:56,110 --> 00:00:59,020
kui me visata rohkem ja rohkem andmeid ta?

21
00:00:59,020 --> 00:01:02,220
In CS50 kogus andmeid me oleme
töötades on üsna väike.

22
00:01:02,220 --> 00:01:05,140
Üldiselt meie programmid lähevad
sõidetud teise või less--

23
00:01:05,140 --> 00:01:07,830
ilmselt palju vähem
eriti varakult.

24
00:01:07,830 --> 00:01:12,250
>> Aga mõtle ettevõte, mis tegeleb
sadu miljoneid kliente.

25
00:01:12,250 --> 00:01:14,970
Ja neil on vaja töödelda
et kliendi andmed.

26
00:01:14,970 --> 00:01:18,260
Nagu mitmed kliendid nad
on muutub suuremaks ja suuremaks,

27
00:01:18,260 --> 00:01:21,230
see läheb vaja
rohkem ja rohkem ressursse.

28
00:01:21,230 --> 00:01:22,926
Mitu rohkem ressursse?

29
00:01:22,926 --> 00:01:25,050
Noh, see sõltub sellest, kuidas
Analüüsides algoritm,

30
00:01:25,050 --> 00:01:28,097
kasutades vahendeid selle tööriistakasti.

31
00:01:28,097 --> 00:01:31,180
Kui me räägime keerukust
algorithm-- mis mõnikord saate

32
00:01:31,180 --> 00:01:34,040
kuule seda nimetatakse aega
keerukuse või ruumi keerukus

33
00:01:34,040 --> 00:01:36,190
aga me lihtsalt läheb
helistada complexity--

34
00:01:36,190 --> 00:01:38,770
me tavaliselt räägime
halvima stsenaariumi.

35
00:01:38,770 --> 00:01:42,640
Arvestades absoluutne halvim kuhja
andmed, et saaksime viskamine seda,

36
00:01:42,640 --> 00:01:46,440
kuidas see algoritm läheb
töödelda või tegeleda, et andmed?

37
00:01:46,440 --> 00:01:51,450
Me üldiselt helistada halvima
Runtime algoritmi big-O.

38
00:01:51,450 --> 00:01:56,770
Nii algoritm võib öelda, et
sõidetud O n või O n ruudus.

39
00:01:56,770 --> 00:01:59,110
Ja veel sellest, mis
need tähendavad teine.

40
00:01:59,110 --> 00:02:01,620
>> Mõnikord, kuigi me hoolime
umbes parimal juhul.

41
00:02:01,620 --> 00:02:05,400
Kui andmed on kõik, mida me tahtsime
seda ja see oli täiusliku

42
00:02:05,400 --> 00:02:09,630
ja me saadame selle täiuslik
andmekogum meie algoritm.

43
00:02:09,630 --> 00:02:11,470
Kuidas see hakkama selles olukorras?

44
00:02:11,470 --> 00:02:15,050
Me mõnikord räägivad, et kui
big-Omega, nii erinevalt big-O,

45
00:02:15,050 --> 00:02:16,530
meil big-Omega.

46
00:02:16,530 --> 00:02:18,880
Big-Omega parima stsenaariumi.

47
00:02:18,880 --> 00:02:21,319
Big-O jaoks halvima stsenaariumi.

48
00:02:21,319 --> 00:02:23,860
Üldiselt, kui me räägime
keerukust algoritmi,

49
00:02:23,860 --> 00:02:26,370
me räägime
Halvimal juhul.

50
00:02:26,370 --> 00:02:28,100
Nii et hoidke seda silmas pidades.

51
00:02:28,100 --> 00:02:31,510
>> Ja selles klassis, me tavaliselt läheb
lahkuda põhjalik analüüs kõrvale.

52
00:02:31,510 --> 00:02:35,350
On teadused ja väljad
pühendatud sellist kraami.

53
00:02:35,350 --> 00:02:37,610
Kui me räägime põhjendusi
läbi algoritmide

54
00:02:37,610 --> 00:02:41,822
mis me teeme tükk-by-piece palju
algoritme me räägime klassis.

55
00:02:41,822 --> 00:02:44,780
Me tõesti räägi
põhjendades seda läbi terve mõistus,

56
00:02:44,780 --> 00:02:47,070
mitte valemeid, või tõendid,
või midagi sellist.

57
00:02:47,070 --> 00:02:51,600
Nii et ärge muretsege, me ei ole
muutumas suur matemaatika klassi.

58
00:02:51,600 --> 00:02:55,920
>> Ma ütlesin me hoolime keerukus
sest see esitab küsimuse, kuidas

59
00:02:55,920 --> 00:03:00,160
ei meie algoritmid hakkama suuremate ja
suurem andmekogud visatakse neid.

60
00:03:00,160 --> 00:03:01,960
Noh, mis on andmete kogum?

61
00:03:01,960 --> 00:03:03,910
Mida ma mõtlen, kui ma ütlesin, et?

62
00:03:03,910 --> 00:03:07,600
See tähendab iganes teeb kõige
mõtet kontekstis, kui aus olla.

63
00:03:07,600 --> 00:03:11,160
Kui meil algoritm
Protsessid Strings-- me ilmselt

64
00:03:11,160 --> 00:03:13,440
Rääkides suurus string.

65
00:03:13,440 --> 00:03:15,190
See on andmeid set--
suurus, arv

66
00:03:15,190 --> 00:03:17,050
märke, mis moodustavad string.

67
00:03:17,050 --> 00:03:20,090
Kui me räägime
algoritm, mis töötleb faile,

68
00:03:20,090 --> 00:03:23,930
me võiks rääkida, kuidas
palju kilobaiti koosnevad et fail.

69
00:03:23,930 --> 00:03:25,710
Ja see andmete hulk.

70
00:03:25,710 --> 00:03:28,870
Kui me räägime algoritmi
mis tegeleb massiivid üldisemalt

71
00:03:28,870 --> 00:03:31,510
näiteks sorteerimine algoritme
või otsides algoritme,

72
00:03:31,510 --> 00:03:36,690
me ilmselt räägime number
elemente, mis sisaldavad hulgaliselt.

73
00:03:36,690 --> 00:03:39,272
>> Nüüd saame mõõtmisel
algorithm-- eelkõige

74
00:03:39,272 --> 00:03:40,980
kui ma ütlen, saame
mõõta algoritmi, ma

75
00:03:40,980 --> 00:03:43,840
keskmine saame mõõta, kui
palju ressursse kulub.

76
00:03:43,840 --> 00:03:48,990
Kas need ressursid on, kui palju
baiti RAM-- või MB RAM

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

78
00:03:49,790 --> 00:03:52,320
Või kui palju aega kulub, et käivitada.

79
00:03:52,320 --> 00:03:56,200
Ja me nimetame seda
mõõta, omavoliliselt, f n.

80
00:03:56,200 --> 00:03:59,420
Kui n on arv
elemendid andmekogumi.

81
00:03:59,420 --> 00:04:02,640
Ja f n on mitu midagid.

82
00:04:02,640 --> 00:04:07,530
Mitu ühikut ressursse ei
see nõuab töödelda, et andmeid.

83
00:04:07,530 --> 00:04:10,030
>> Nüüd, me tegelikult ei hooli
mida f n on täpselt.

84
00:04:10,030 --> 00:04:13,700
Tegelikult me ​​väga harva will--
Kindlasti ei kasuta kunagi selles class-- ma

85
00:04:13,700 --> 00:04:18,709
sukelduda ühtegi tõeliselt sügav
analüüsi, mida f n on.

86
00:04:18,709 --> 00:04:23,510
Me lihtsalt ei kavatse rääkida, milline f
n on umbes või mis see kipub.

87
00:04:23,510 --> 00:04:27,600
Ja tendents algoritm on
määrab selle kõrgeima järjekorras perspektiivis.

88
00:04:27,600 --> 00:04:29,440
Ja me saame aru, mida ma
mõtlen, et võttes

89
00:04:29,440 --> 00:04:31,910
pilk rohkem konkreetse näite.

90
00:04:31,910 --> 00:04:34,620
>> Ütleme, et meil on
kolmes erinevas algoritme.

91
00:04:34,620 --> 00:04:39,350
Esimene mis võtab n
kuubis, mõned üksused ressursside

92
00:04:39,350 --> 00:04:42,880
töödelda andmeid komplekt suurus n.

93
00:04:42,880 --> 00:04:47,000
Meil on teise algoritmi, mis leiab
n kuubis pluss n ruudus ressursid

94
00:04:47,000 --> 00:04:49,350
töödelda andmeid komplekt suurus n.

95
00:04:49,350 --> 00:04:52,030
Ja meil on kolmanda
algoritm, mis töötab in-- et

96
00:04:52,030 --> 00:04:58,300
võtab n kuubis miinus 8n ruuduline
pluss 20 n ühikut ressursse

97
00:04:58,300 --> 00:05:02,370
töödelda algoritmi
andmekogumi mõõtmetega n.

98
00:05:02,370 --> 00:05:05,594
>> Nüüd jälle, me tõesti ei kavatse
sattuda detailsuse tase.

99
00:05:05,594 --> 00:05:08,260
Ma tõesti lihtsalt need üles
siin näitena punkti

100
00:05:08,260 --> 00:05:10,176
et ma lähen
tegemist teise, mis

101
00:05:10,176 --> 00:05:12,980
on see, et me ainult tõesti hoolivad
umbes kalduvus asju

102
00:05:12,980 --> 00:05:14,870
kui andmekogud saada suurem.

103
00:05:14,870 --> 00:05:18,220
Nii, kui andmekogum on väike, ei
tegelikult päris suur erinevus

104
00:05:18,220 --> 00:05:19,870
Nende algoritme.

105
00:05:19,870 --> 00:05:23,000
Kolmas algoritm seal
võtab 13 korda pikem,

106
00:05:23,000 --> 00:05:27,980
13 korda rohkem ressursse
joosta võrreldes esimesega.

107
00:05:27,980 --> 00:05:31,659
>> Kui meie andmed ei size 10, mis
on suurem, kuid mitte tingimata suur,

108
00:05:31,659 --> 00:05:33,950
näeme, et seal on
tegelikult natuke erinev.

109
00:05:33,950 --> 00:05:36,620
Kolmas algoritm
muutub tõhusamaks.

110
00:05:36,620 --> 00:05:40,120
See on umbes tegelikult 40% -
või 60% tõhusam.

111
00:05:40,120 --> 00:05:41,580
See võtab 40%, kui palju aega.

112
00:05:41,580 --> 00:05:45,250
See võib run-- see võib võtta
400 ühikut ressursse

113
00:05:45,250 --> 00:05:47,570
töödelda andmeid komplekt suurus 10.

114
00:05:47,570 --> 00:05:49,410
Kui esimene
algoritmi, seevastu

115
00:05:49,410 --> 00:05:54,520
võtab 1000 ühikut ressursse
töödelda andmeid komplekt suurus 10.

116
00:05:54,520 --> 00:05:57,240
Aga vaata, mis juhtub, kui
Meie numbrid saada isegi suurem.

117
00:05:57,240 --> 00:05:59,500
>> Nüüd, vahe
vahel nende algoritmide

118
00:05:59,500 --> 00:06:01,420
puhul hakkavad veidi vähem ilmne.

119
00:06:01,420 --> 00:06:04,560
Ja asjaolu, et seal on
madalama et terms-- või mitte,

120
00:06:04,560 --> 00:06:09,390
poolest madalama exponents--
alustab olla tõsiseltvõetav.

121
00:06:09,390 --> 00:06:12,290
Kui andmed ei suurusega
1000 ja esimene algoritmi

122
00:06:12,290 --> 00:06:14,170
jookseb miljardit samme.

123
00:06:14,170 --> 00:06:17,880
Ja teine ​​algoritm töötab
miljardi ja miljoni samme.

124
00:06:17,880 --> 00:06:20,870
Ja kolmas algoritm töötab
vaid häbelik miljardi samme.

125
00:06:20,870 --> 00:06:22,620
See on päris palju miljardit samme.

126
00:06:22,620 --> 00:06:25,640
Need madalama järku alustada
saada tõesti ebaoluline.

127
00:06:25,640 --> 00:06:27,390
Ja just tõesti
haamer koju point--

128
00:06:27,390 --> 00:06:31,240
Kui sisestatud andmed on Suurus A
million-- kõik need kolm päris palju

129
00:06:31,240 --> 00:06:34,960
võta üks quintillion-- kui
minu matemaatika on correct-- samme

130
00:06:34,960 --> 00:06:37,260
töödelda andmeid sisestada
suurus miljon.

131
00:06:37,260 --> 00:06:38,250
See on palju samme.

132
00:06:38,250 --> 00:06:42,092
Ja asjaolu, et üks neist võivad
võtta paar 100.000 või paar 100

133
00:06:42,092 --> 00:06:44,650
miljonit isegi vähem kui
me räägime number

134
00:06:44,650 --> 00:06:46,990
et big-- see on selline ebaoluline.

135
00:06:46,990 --> 00:06:50,006
Nad kõik kipuvad võtma
umbes n kuubis,

136
00:06:50,006 --> 00:06:52,380
ja nii me tegelikult viidata
Kõigi nende algoritmide

137
00:06:52,380 --> 00:06:59,520
nagu oleks tellimusel n
kuubis või big-O n kuubis.

138
00:06:59,520 --> 00:07:03,220
>> Siin on nimekiri mõned rohkem
ühise arvutuslik keerukus klassi

139
00:07:03,220 --> 00:07:05,820
et me kohata
algoritme, üldiselt.

140
00:07:05,820 --> 00:07:07,970
Ja ka konkreetselt CS50.

141
00:07:07,970 --> 00:07:11,410
Need tellitakse
üldiselt kiiremini tipus,

142
00:07:11,410 --> 00:07:13,940
üldiselt aeglasem allosas.

143
00:07:13,940 --> 00:07:16,920
Nii konstantset aega algoritme kipuvad
kiireim, sõltumata

144
00:07:16,920 --> 00:07:19,110
suuruse kohta
andmesisestuse sa läbima.

145
00:07:19,110 --> 00:07:23,760
Nad alati üks operatsioon või
üks ühik ressursse tegeleda.

146
00:07:23,760 --> 00:07:25,730
See võib olla 2, see võib
olla 3, siis võib olla 4.

147
00:07:25,730 --> 00:07:26,910
Aga see on pidev number.

148
00:07:26,910 --> 00:07:28,400
See ei muutu.

149
00:07:28,400 --> 00:07:31,390
>> Logarithmic aega algoritme
on veidi parem.

150
00:07:31,390 --> 00:07:33,950
Ja tõesti hea näide
logaritmiline algoritm

151
00:07:33,950 --> 00:07:37,420
olete kindlasti näinud nüüd on
rebides telefoniraamatust

152
00:07:37,420 --> 00:07:39,480
leida Mike Smith telefoniraamatus.

153
00:07:39,480 --> 00:07:40,980
Me lõigatud probleemi poole.

154
00:07:40,980 --> 00:07:43,580
Ja nii nagu n muutub suuremaks
ja suuremate ja larger--

155
00:07:43,580 --> 00:07:47,290
Tegelikult iga kord, kui kahekordistada
n, see võtab vaid üks samm.

156
00:07:47,290 --> 00:07:49,770
Nii et see on palju parem
kui näiteks lineaarset aega.

157
00:07:49,770 --> 00:07:53,030
Milline on siis, kui sa topelt n, siis
võtab kaks korda rohkem samme.

158
00:07:53,030 --> 00:07:55,980
Kui te kolmekordistub n, mis kulub
kolmekordistab mitmeid samme.

159
00:07:55,980 --> 00:07:58,580
Üks samm ühiku kohta.

160
00:07:58,580 --> 00:08:01,790
>> Siis asjad natuke more--
Veidi vähem suuri sealt.

161
00:08:01,790 --> 00:08:06,622
Sul on lineaarne rütmiline aega, mõnikord
nimetatakse Logi lineaarne ajal või lihtsalt n log n.

162
00:08:06,622 --> 00:08:08,330
Ja me näide
algoritmi, mis

163
00:08:08,330 --> 00:08:13,370
jookseb n log n, mis on ikka parem
kui quadratic AEG_ n ruudus.

164
00:08:13,370 --> 00:08:17,320
Või polünomiaalset, n kaks
suvaline arv suurem kui kaks.

165
00:08:17,320 --> 00:08:20,810
Või eksponentsiaalne aeg, mis
on isegi worse-- C kuni n.

166
00:08:20,810 --> 00:08:24,670
Nii mõned pidev arv tõuseb
võimu suurusest sisend.

167
00:08:24,670 --> 00:08:28,990
Nii et kui seal on 1,000-- kui
andmesisestuse on suurus 1000,

168
00:08:28,990 --> 00:08:31,310
see võtaks C kuni 1000. võim.

169
00:08:31,310 --> 00:08:33,559
See on palju hullem kui polünomiaalset.

170
00:08:33,559 --> 00:08:35,030
>> Factorial aega on veel hullem.

171
00:08:35,030 --> 00:08:37,760
Ja tegelikult, seal tõesti
olemas lõpmatu aeg algoritme,

172
00:08:37,760 --> 00:08:43,740
nagu nn loll sort-- kelle
töö on juhuslikult shuffle massiivi

173
00:08:43,740 --> 00:08:45,490
ja siis vaadata,
kas see on järjestatud.

174
00:08:45,490 --> 00:08:47,589
Ja kui see ei ole juhuslikult
shuffle massiiv uuesti

175
00:08:47,589 --> 00:08:49,130
ja vaadake, kas see on järjestatud.

176
00:08:49,130 --> 00:08:51,671
Ja kui saab ilmselt imagine--
võite ette kujutada olukorda

177
00:08:51,671 --> 00:08:55,200
kus halvima, mis
tegelikult kunagi alustada massiivi.

178
00:08:55,200 --> 00:08:57,150
See algoritm läheks igaveseks.

179
00:08:57,150 --> 00:08:59,349
Ja nii, et oleks
lõpmatu aeg algoritm.

180
00:08:59,349 --> 00:09:01,890
Loodetavasti sa ei saa kirjutada
mis tahes faktoriaali või lõpmatu aeg

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

182
00:09:04,510 --> 00:09:09,150
>> Niisiis, võtame natuke rohkem
betooni mõningaid lihtsamaid

183
00:09:09,150 --> 00:09:11,154
arvutuslik keerukus klassid.

184
00:09:11,154 --> 00:09:13,070
Nii on meil example--
või kaks näidet siin--

185
00:09:13,070 --> 00:09:15,590
Pideva aja algoritme,
mis alati

186
00:09:15,590 --> 00:09:17,980
ühe operatsiooni halvima.

187
00:09:17,980 --> 00:09:20,050
Nii et esimene example--
meil on funktsioon

188
00:09:20,050 --> 00:09:23,952
nimetatakse 4 teid, mis
võtab massiivi suurus 1000.

189
00:09:23,952 --> 00:09:25,660
Aga siis ilmselt
tegelikult ei vaata

190
00:09:25,660 --> 00:09:29,000
kell see-- ei huvita, mida on
sees on, selle massiivi.

191
00:09:29,000 --> 00:09:30,820
Alati lihtsalt tagasi neli.

192
00:09:30,820 --> 00:09:32,940
Nii, et algoritm,
vaatamata asjaolule, et see

193
00:09:32,940 --> 00:09:35,840
võtab 1,000 elemendid ei
midagi teha nendega.

194
00:09:35,840 --> 00:09:36,590
Just naaseb neli.

195
00:09:36,590 --> 00:09:38,240
See on alati ühe sammu.

196
00:09:38,240 --> 00:09:41,600
>> Tegelikult lisada 2 nums-- mis
oleme näinud nii well--

197
00:09:41,600 --> 00:09:43,680
lihtsalt töötleb kaks täisarvu.

198
00:09:43,680 --> 00:09:44,692
See ei ole ühe sammu.

199
00:09:44,692 --> 00:09:45,900
See on tegelikult paar sammu.

200
00:09:45,900 --> 00:09:50,780
Sa saad, saad b, kui lisate neid
koos, ja sa väljund tulemusi.

201
00:09:50,780 --> 00:09:53,270
Nii et see on 84 astet.

202
00:09:53,270 --> 00:09:55,510
Aga see on alati konstantne,
sõltumata a või b.

203
00:09:55,510 --> 00:09:59,240
Sa pead saada, saada b, lisada
need kokku, saadab tulemuse.

204
00:09:59,240 --> 00:10:02,900
Nii et pidev algoritm.

205
00:10:02,900 --> 00:10:05,170
>> Siin on näide
lineaarne aeg algorithm--

206
00:10:05,170 --> 00:10:08,740
algoritmi, mis gets-- mis võtab
täiendav aste võimalusel

207
00:10:08,740 --> 00:10:10,740
oma panus kasvab 1..

208
00:10:10,740 --> 00:10:14,190
Niisiis, oletame, et me otsime
arvu 5 sees massiivi.

209
00:10:14,190 --> 00:10:16,774
Sul võib olla olukord, kus
leiad selle üsna varakult.

210
00:10:16,774 --> 00:10:18,606
Aga sa võid ka
olukorrast, kus ta

211
00:10:18,606 --> 00:10:20,450
võib olla viimane element massiivi.

212
00:10:20,450 --> 00:10:23,780
In massiivi suurus 5, kui
me otsime arv 5.

213
00:10:23,780 --> 00:10:25,930
See võtaks 5 sammu.

214
00:10:25,930 --> 00:10:29,180
Ja tegelikult ette kujutada, et seal on
ei 5 kõikjal selle massiivi.

215
00:10:29,180 --> 00:10:32,820
Meil on ikka tegelikult on vaadata
iga element massiivi

216
00:10:32,820 --> 00:10:35,550
et teha kindlaks
kas 5 on olemas.

217
00:10:35,550 --> 00:10:39,840
>> Nii et halvimal juhul, mis on selle
element on viimase massiivi

218
00:10:39,840 --> 00:10:41,700
või ei ole üldse.

219
00:10:41,700 --> 00:10:44,690
Meil on veel vaadata
kõik n elemente.

220
00:10:44,690 --> 00:10:47,120
Ja nii see algoritm
jookseb lineaarne aeg.

221
00:10:47,120 --> 00:10:50,340
Võite kinnitada, et
ekstrapoleerimise natuke juurde,

222
00:10:50,340 --> 00:10:53,080
kui meil oleks 6-element massiivi ja
otsisime arv 5,

223
00:10:53,080 --> 00:10:54,890
see võib võtta 6 samme.

224
00:10:54,890 --> 00:10:57,620
Kui meil on 7-element massiivi ja
me otsime arv 5.

225
00:10:57,620 --> 00:10:59,160
See võib võtta 7 astet.

226
00:10:59,160 --> 00:11:02,920
Nagu me lisada veel üks element meie
massiiv, mis kulub ühe sammu.

227
00:11:02,920 --> 00:11:06,750
See on lineaarne algoritm
aasta halvima.

228
00:11:06,750 --> 00:11:08,270
>> Paar kiiret küsimust sinu jaoks.

229
00:11:08,270 --> 00:11:11,170
Mis runtime-- mis on
halvima runtime

230
00:11:11,170 --> 00:11:13,700
Selle konkreetse koodilõige?

231
00:11:13,700 --> 00:11:17,420
Nii et mul on 4 loop siin, mis töötab
alates j võrdub 0, kõik viis kuni m.

232
00:11:17,420 --> 00:11:21,980
Ja mida ma näen siin, on see, et
keha silmus jookseb pidevalt aega.

233
00:11:21,980 --> 00:11:24,730
Nii kasutades terminoloogiat
me oleme juba rääkinud about-- mida

234
00:11:24,730 --> 00:11:29,390
oleks halvima
Runtime selle algoritmi?

235
00:11:29,390 --> 00:11:31,050
Võtke teine.

236
00:11:31,050 --> 00:11:34,270
Sisemine osa loop
töötab pidevas aega.

237
00:11:34,270 --> 00:11:37,510
Ja välisosas
loop läheb jooksma m korda.

238
00:11:37,510 --> 00:11:40,260
Mis siis halvima runtime siin?

239
00:11:40,260 --> 00:11:43,210
Kas sa vist suur-O m?

240
00:11:43,210 --> 00:11:44,686
Sa oleks õige.

241
00:11:44,686 --> 00:11:46,230
>> Kuidas teine?

242
00:11:46,230 --> 00:11:48,590
Seekord on meil
loop sees silmus.

243
00:11:48,590 --> 00:11:50,905
Meil on välimine loop
mis jookseb nullist p.

244
00:11:50,905 --> 00:11:54,630
Ja meil on sisemine loop, mis töötab
nullist p ja sees, et

245
00:11:54,630 --> 00:11:57,890
Ma väita, et keha
loop töötab konstantse ajaga.

246
00:11:57,890 --> 00:12:02,330
Mis siis halvima runtime
Selle konkreetse koodilõige?

247
00:12:02,330 --> 00:12:06,140
Noh, jälle oleme
välimine mis kulgeb p korda.

248
00:12:06,140 --> 00:12:09,660
Ja iga AEG_ iteratsiooni
Selle loop, pigem.

249
00:12:09,660 --> 00:12:13,170
Meil on sisemine loop
mis töötab ka p korda.

250
00:12:13,170 --> 00:12:16,900
Ja siis sees, et seal on
pidev AEG_ vähe koodijupi seal.

251
00:12:16,900 --> 00:12:19,890
>> Nii et kui meil on välimine loop et
jookseb lk korda, mille sees on

252
00:12:19,890 --> 00:12:22,880
sisemine loop et
jookseb p korda-- mis on

253
00:12:22,880 --> 00:12:26,480
halvima runtime
Selle koodilõige?

254
00:12:26,480 --> 00:12:30,730
Kas sa vist suur-O p ruudus?

255
00:12:30,730 --> 00:12:31,690
>> Ma olen Doug Lloyd.

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

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