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

2
00:00:05,830 --> 00:00:07,910
>> Allt í lagi, svo computational flókið.

3
00:00:07,910 --> 00:00:10,430
Bara smá viðvörun
áður en við kafa í of far--

4
00:00:10,430 --> 00:00:13,070
þetta verður sennilega að vera meðal
mest stærðfræði-þungur hlutur

5
00:00:13,070 --> 00:00:14,200
við tölum um í CS50.

6
00:00:14,200 --> 00:00:16,950
Vonandi mun það ekki vera of yfirþyrmandi
og við munum reyna að leiða þig

7
00:00:16,950 --> 00:00:19,200
gegnum ferlið, en
bara hluti af Fair Warning.

8
00:00:19,200 --> 00:00:21,282
Það er svolítið
af stærðfræði þátt hér.

9
00:00:21,282 --> 00:00:23,990
Allt í lagi, svo í því skyni að gera
Notkun computational auðlindir okkar

10
00:00:23,990 --> 00:00:28,170
í alvöru world-- það er í raun
mikilvægt að skilja reiknirit

11
00:00:28,170 --> 00:00:30,750
og hvernig þeir vinna úr gögnum.

12
00:00:30,750 --> 00:00:32,810
Ef við höfum mjög
duglegur reiknirit, við

13
00:00:32,810 --> 00:00:36,292
getur lágmarka magn af fjármagni
við höfum í boði til að takast á við það.

14
00:00:36,292 --> 00:00:38,750
Ef við höfum reiknirit sem
er að fara að taka a einhver fjöldi af vinna

15
00:00:38,750 --> 00:00:41,210
að vinna mjög
stór sett af gögnum, það er

16
00:00:41,210 --> 00:00:44,030
að fara að krefjast meira
og fleiri úrræði, sem

17
00:00:44,030 --> 00:00:47,980
er peningar, RAM, allt að hvers konar efni.

18
00:00:47,980 --> 00:00:52,090
>> Svo, að vera fær um að greina að
reiknirit nota þetta tól setja,

19
00:00:52,090 --> 00:00:56,110
grundvallaratriðum, spyr question--
hvernig virkar þetta reiknirit mælikvarða

20
00:00:56,110 --> 00:00:59,020
eins og við kasta fleiri og fleiri gögn á það?

21
00:00:59,020 --> 00:01:02,220
Í CS50, hversu mikið af gögnum sem við erum
vinna með er nokkuð lítið.

22
00:01:02,220 --> 00:01:05,140
Almennt eru forrit okkar fara
að keyra í annað eða less--

23
00:01:05,140 --> 00:01:07,830
sennilega mikið minni
sérstaklega snemma.

24
00:01:07,830 --> 00:01:12,250
>> En hugsa um fyrirtæki sem fæst
með hundruð milljóna viðskiptavina.

25
00:01:12,250 --> 00:01:14,970
Og þeir þurfa að vinna
sem viðskiptavinur gögn.

26
00:01:14,970 --> 00:01:18,260
Sem fjöldi viðskiptavina sem þeir
hafa fær stærri og stærri,

27
00:01:18,260 --> 00:01:21,230
það er að fara að krefjast
fleiri og fleiri úrræði.

28
00:01:21,230 --> 00:01:22,926
Hversu margir fleiri auðlindir?

29
00:01:22,926 --> 00:01:25,050
Jæja, það fer eftir því hvernig
við greina reiknirit,

30
00:01:25,050 --> 00:01:28,097
nota verkfæri í þessari kistu.

31
00:01:28,097 --> 00:01:31,180
Þegar við tölum um flókið
An algorithm-- sem stundum þú munt

32
00:01:31,180 --> 00:01:34,040
heyra það nefnt tíma
flókið eða rúm flókið

33
00:01:34,040 --> 00:01:36,190
en við erum bara að fara
að hringja complexity--

34
00:01:36,190 --> 00:01:38,770
við erum yfirleitt að tala um
versta falli.

35
00:01:38,770 --> 00:01:42,640
Í ljósi alger versta stafli af
gögn sem við gætum verið að henda á það,

36
00:01:42,640 --> 00:01:46,440
hvernig er þetta reiknirit fara að
vinna eða takast á við þessi gögn?

37
00:01:46,440 --> 00:01:51,450
Við köllum yfirleitt versta
afturkreistingur af reiknirit stór-O.

38
00:01:51,450 --> 00:01:56,770
Svo reiknirit mætti ​​segja að
hlaupa í O á n eða O í n veldi.

39
00:01:56,770 --> 00:01:59,110
Og meira um hvað
þá meina í annað.

40
00:01:59,110 --> 00:02:01,620
>> Stundum, þó, gera við umönnun
um besta falli atburðarás.

41
00:02:01,620 --> 00:02:05,400
Ef gögn er allt sem við vildum
það að vera og það var fullkomið

42
00:02:05,400 --> 00:02:09,630
og við vorum að senda þetta fullkomið
setja af gögnum í gegnum reiknirit okkar.

43
00:02:09,630 --> 00:02:11,470
Hvernig væri það höndla í því ástandi?

44
00:02:11,470 --> 00:02:15,050
Við vísa stundum til að sem
stór-Omega, svo ólíkt stór-O,

45
00:02:15,050 --> 00:02:16,530
við höfum stóra-Omega.

46
00:02:16,530 --> 00:02:18,880
Big-Omega fyrir besta falli atburðarás.

47
00:02:18,880 --> 00:02:21,319
Big-O fyrir versta.

48
00:02:21,319 --> 00:02:23,860
Almennt, þegar við tölum um
flókið reiknirit,

49
00:02:23,860 --> 00:02:26,370
við erum að tala um
versta.

50
00:02:26,370 --> 00:02:28,100
Svo halda að í huga.

51
00:02:28,100 --> 00:02:31,510
>> Og í þessum flokki, við erum almennt að fara
að yfirgefa strangt greiningu hliðar.

52
00:02:31,510 --> 00:02:35,350
Það eru vísindi og sviðum
helgaður þessu tagi efni.

53
00:02:35,350 --> 00:02:37,610
Þegar við tölum um rökhugsun
gegnum reiknirit,

54
00:02:37,610 --> 00:02:41,822
sem við munum gera stykki-við-stykki fyrir marga
reiknirit við tölum um í bekknum.

55
00:02:41,822 --> 00:02:44,780
Við erum í raun bara að tala um
reasoning gegnum það með skynsemi,

56
00:02:44,780 --> 00:02:47,070
ekki með formúlur eða fylgigögn,
eða eitthvað svoleiðis.

57
00:02:47,070 --> 00:02:51,600
Svo ekki hafa áhyggjur, Við munum ekki vera
beygja inn í a stór stærðfræði bekknum.

58
00:02:51,600 --> 00:02:55,920
>> Svo ég sagði við vænt um flókið
vegna þess að það spyr spurningu, hvernig

59
00:02:55,920 --> 00:03:00,160
ekki reiknirit okkar höndla stærri og
stærri gagnagrunna verið kastað á þá.

60
00:03:00,160 --> 00:03:01,960
Jæja, hvað er gögnum?

61
00:03:01,960 --> 00:03:03,910
Hvað gerði ég meina þegar ég sagði það?

62
00:03:03,910 --> 00:03:07,600
Það þýðir hvað gerir mest
vit í samhengi, til að vera heiðarlegur.

63
00:03:07,600 --> 00:03:11,160
Ef við höfum reiknirit, á
Processes Strings-- erum við líklega

64
00:03:11,160 --> 00:03:13,440
að tala um stærð af the band.

65
00:03:13,440 --> 00:03:15,190
Það er gögn set--
stærð, fjölda

66
00:03:15,190 --> 00:03:17,050
stafi sem mynda band.

67
00:03:17,050 --> 00:03:20,090
Ef við erum að tala um að
reiknirit sem vinnur skrár,

68
00:03:20,090 --> 00:03:23,930
við gætum verið að tala um hvernig
margir kílóbæti samanstanda að skrá.

69
00:03:23,930 --> 00:03:25,710
Og það er gögnum.

70
00:03:25,710 --> 00:03:28,870
Ef við erum að tala um reiknirit
sem annast fylki almennt,

71
00:03:28,870 --> 00:03:31,510
svo sem flokkun reiknirit
eða leita reiknirit,

72
00:03:31,510 --> 00:03:36,690
við erum líklega að tala um fjölda
þætti sem samanstanda fylki.

73
00:03:36,690 --> 00:03:39,272
>> Nú getum við mæla sem
algorithm-- einkum,

74
00:03:39,272 --> 00:03:40,980
þegar ég segi við getum
mæla algrím, ég

75
00:03:40,980 --> 00:03:43,840
meina við getum mælt hversu
margar auðlindir sem það tekur upp.

76
00:03:43,840 --> 00:03:48,990
Hvort þessar auðlindir eru, hversu margir
bytes RAM-- eða megabæti af RAM

77
00:03:48,990 --> 00:03:49,790
það notar.

78
00:03:49,790 --> 00:03:52,320
Eða hversu mikinn tíma það tekur að keyra.

79
00:03:52,320 --> 00:03:56,200
Og við getum kallað þetta
mæla, geðþótta, f á n.

80
00:03:56,200 --> 00:03:59,420
Þar sem n er fjöldi
þættir í gögnum.

81
00:03:59,420 --> 00:04:02,640
Og f n er hversu margir somethings.

82
00:04:02,640 --> 00:04:07,530
Hversu margar einingar af auðlindum er
það þurfa að vinna þessi gögn.

83
00:04:07,530 --> 00:04:10,030
>> Nú, reyndar við ekki sama
um hvað f n er nákvæmlega.

84
00:04:10,030 --> 00:04:13,700
Í raun erum við will-- mjög sjaldan
vissulega mun aldrei í þessu class-- I

85
00:04:13,700 --> 00:04:18,709
kafa í hvaða raunverulega djúpt
greining á því hvaða f-n er.

86
00:04:18,709 --> 00:04:23,510
Við erum bara að fara að tala um hvað f
n er um eða hvað það hefur tilhneigingu til að.

87
00:04:23,510 --> 00:04:27,600
Og tilhneigingu reiknirit er
ráðist af hæsta röð þess tíma.

88
00:04:27,600 --> 00:04:29,440
Og við getum séð hvað ég
meina með því með því að taka

89
00:04:29,440 --> 00:04:31,910
a líta á áþreifanlegri dæmi.

90
00:04:31,910 --> 00:04:34,620
>> Svo skulum segja að við höfum
þrjár mismunandi reiknirit.

91
00:04:34,620 --> 00:04:39,350
Fyrsta sem tekur N
cubed, sumum einingum auðlindir

92
00:04:39,350 --> 00:04:42,880
að vinna úr gögnum sett af stærð n.

93
00:04:42,880 --> 00:04:47,000
Við höfum annað reiknirit sem tekur
n cubed plús n veldi auðlindir

94
00:04:47,000 --> 00:04:49,350
að vinna úr gögnum sett af stærð n.

95
00:04:49,350 --> 00:04:52,030
Og við höfum þriðja
reiknirit sem keyrir in-- að

96
00:04:52,030 --> 00:04:58,300
tekur upp n cubed mínus 8n veldi
auk 20 n einingar af auðlindum

97
00:04:58,300 --> 00:05:02,370
að vinna reikniriti
með gögn sem sett eru af stærð n.

98
00:05:02,370 --> 00:05:05,594
>> Nú aftur, við í raun ekki að fara
að komast inn í þennan nákvæmnina.

99
00:05:05,594 --> 00:05:08,260
Ég er í raun bara hafa þetta upp
hér til skýringar punkti

100
00:05:08,260 --> 00:05:10,176
sem ég ætla að vera
gera í annað, sem

101
00:05:10,176 --> 00:05:12,980
er að við sama bara virkilega
um tilhneigingu hlutum

102
00:05:12,980 --> 00:05:14,870
sem gagnagrunnar fá stærri.

103
00:05:14,870 --> 00:05:18,220
Þannig að ef gögnum er lítill, það er
reyndar mjög mikill munur

104
00:05:18,220 --> 00:05:19,870
í þessum reiknirit.

105
00:05:19,870 --> 00:05:23,000
Þriðja reiknirit það
tekur 13 sinnum lengur,

106
00:05:23,000 --> 00:05:27,980
13 sinnum the magn af fjármagni
að keyra miðað við það fyrsta.

107
00:05:27,980 --> 00:05:31,659
>> Ef gögnum okkar er stærð 10, sem
er stærri en ekki endilega mikið,

108
00:05:31,659 --> 00:05:33,950
getum við séð að það er
reyndar svolítið af a mismunur.

109
00:05:33,950 --> 00:05:36,620
Þriðja reiknirit
verður skilvirkari.

110
00:05:36,620 --> 00:05:40,120
Það er um raunverulega að 40% -
eða 60% skilvirkari.

111
00:05:40,120 --> 00:05:41,580
Það tekur 40% af því magni af tíma.

112
00:05:41,580 --> 00:05:45,250
Það getur run-- það getur tekið
400 einingar af auðlindum

113
00:05:45,250 --> 00:05:47,570
að vinna úr gögnum sett af stærð 10.

114
00:05:47,570 --> 00:05:49,410
En fyrsta
reiknirit, hins vegar

115
00:05:49,410 --> 00:05:54,520
tekur 1.000 einingar af auðlindum
að vinna úr gögnum sett af stærð 10.

116
00:05:54,520 --> 00:05:57,240
En líta hvað gerist þegar
númer okkar fá jafnvel stærri.

117
00:05:57,240 --> 00:05:59,500
>> Nú er munurinn
milli þessara reiknirit

118
00:05:59,500 --> 00:06:01,420
byrja að verða svolítið minna áberandi.

119
00:06:01,420 --> 00:06:04,560
Og sú staðreynd að það eru
minni röð terms-- eða öllu heldur,

120
00:06:04,560 --> 00:06:09,390
Skilmálar með lægri exponents--
byrja að verða óviðkomandi.

121
00:06:09,390 --> 00:06:12,290
Ef gögnum er stærð
1000 og fyrsta reiknirit

122
00:06:12,290 --> 00:06:14,170
keyrir í milljarð skrefum.

123
00:06:14,170 --> 00:06:17,880
Og seinni reiknirit keyrir í
milljarð og milljón skref.

124
00:06:17,880 --> 00:06:20,870
Og þriðja reiknirit keyrir
í bara feiminn af milljarð skrefum.

125
00:06:20,870 --> 00:06:22,620
Það er ansi mikið milljarð skref.

126
00:06:22,620 --> 00:06:25,640
Þeir minni pöntun skilmálar byrja
að verða mjög óviðkomandi.

127
00:06:25,640 --> 00:06:27,390
Og bara til að virkilega
hamar heim í point--

128
00:06:27,390 --> 00:06:31,240
ef gögn inntak er stærðar
million-- öll þrjú af þessum ansi mikið

129
00:06:31,240 --> 00:06:34,960
taka einn quintillion-- ef
stærðfræði minn er correct-- skref

130
00:06:34,960 --> 00:06:37,260
að vinna gögn inntak
stærð milljón.

131
00:06:37,260 --> 00:06:38,250
Það er mikið af skrefum.

132
00:06:38,250 --> 00:06:42,092
Og sú staðreynd að einn af þeim gæti
taka nokkra 100.000 eða nokkra 100

133
00:06:42,092 --> 00:06:44,650
milljónir jafnvel minna þegar
við erum að tala um fjölda

134
00:06:44,650 --> 00:06:46,990
að big-- það er góður af óviðkomandi.

135
00:06:46,990 --> 00:06:50,006
Þeir allir tilhneigingu til að taka
um n cubed,

136
00:06:50,006 --> 00:06:52,380
og svo við myndum í raun átt
að allar þessar reiknirit

137
00:06:52,380 --> 00:06:59,520
eins og að vera á röð n
cubed eða stór-O n cubed.

138
00:06:59,520 --> 00:07:03,220
>> Hér er listi af sumir af the fleiri
algengar computational bekkjum flókið

139
00:07:03,220 --> 00:07:05,820
að við munum lenda í
reiknirit, almennt.

140
00:07:05,820 --> 00:07:07,970
Og einnig sérstaklega í CS50.

141
00:07:07,970 --> 00:07:11,410
Þetta er raðað frá
almennt festa efst,

142
00:07:11,410 --> 00:07:13,940
almennt hægur neðst.

143
00:07:13,940 --> 00:07:16,920
Svo föstu reiknirit hafa
að vera the festa, óháð

144
00:07:16,920 --> 00:07:19,110
til stærðar á
gögn inntak þú fara í.

145
00:07:19,110 --> 00:07:23,760
Þeir taka alltaf eina aðgerð eða
ein eining af auðlindum til að takast á við.

146
00:07:23,760 --> 00:07:25,730
Það gæti verið 2, gæti það
vera 3, gæti það verið 4.

147
00:07:25,730 --> 00:07:26,910
En það er stöðug tala.

148
00:07:26,910 --> 00:07:28,400
Það breytist ekki.

149
00:07:28,400 --> 00:07:31,390
>> Lógaritmískum tíma reiknirit
eru örlítið betri.

150
00:07:31,390 --> 00:07:33,950
Og mjög gott dæmi um
Logarythmiskur tími reiknirit

151
00:07:33,950 --> 00:07:37,420
þú hefur örugglega séð nú er
rífa í sundur af símaskránni

152
00:07:37,420 --> 00:07:39,480
að finna Mike Smith í símaskránni.

153
00:07:39,480 --> 00:07:40,980
Við skera vandamál í tvennt.

154
00:07:40,980 --> 00:07:43,580
Og svo eins og n fær stærri
og stærri og larger--

155
00:07:43,580 --> 00:07:47,290
í raun í hvert skipti sem þú tvöfaldur
n, það tekur aðeins eitt skref.

156
00:07:47,290 --> 00:07:49,770
Svo það er mikið betra
en, segjum, línuleg tími.

157
00:07:49,770 --> 00:07:53,030
Sem er ef þú tvöfaldur n, það
tekur tvöfalda fjölda af skrefum.

158
00:07:53,030 --> 00:07:55,980
Ef þú þrefaldur n, það tekur
þrefalda fjölda skrefum.

159
00:07:55,980 --> 00:07:58,580
Eitt skref á hverja einingu.

160
00:07:58,580 --> 00:08:01,790
>> Þá það fá smá more--
aðeins minna mikill þaðan.

161
00:08:01,790 --> 00:08:06,622
Þú hefur línulega takt tíma, stundum
kallaði þig línuleg tími eða bara n log n.

162
00:08:06,622 --> 00:08:08,330
Og við munum dæmi
af reiknirit sem

163
00:08:08,330 --> 00:08:13,370
keyrir í n log n, sem er enn betra
en annars stigs time-- n veldi.

164
00:08:13,370 --> 00:08:17,320
Eða margliða tíma, n tveir
allir tala meiri en tveir.

165
00:08:17,320 --> 00:08:20,810
Eða veldisvísis tíma, sem
er jafnvel worse-- C í n.

166
00:08:20,810 --> 00:08:24,670
Svo sumir stöðug tala hækkuð í
kraftur stærð inntak.

167
00:08:24,670 --> 00:08:28,990
Þannig að ef það er 1,000-- standi
gögn inntak af stærð 1.000,

168
00:08:28,990 --> 00:08:31,310
það myndi taka C til 1.000 th völd.

169
00:08:31,310 --> 00:08:33,559
Það er mikið verra en margliðunnar tíma.

170
00:08:33,559 --> 00:08:35,030
>> Factorial tími er jafnvel enn verra.

171
00:08:35,030 --> 00:08:37,760
Og í raun, það er í raun að gera
eru óendanlega tíma reiknirit,

172
00:08:37,760 --> 00:08:43,740
svo sem, svokölluð heimskur sort-- sem
starf er að handahófi uppstokkun fylki

173
00:08:43,740 --> 00:08:45,490
og þá athuga
hvort sem það er flokkað.

174
00:08:45,490 --> 00:08:47,589
Og ef það er ekki, af handahófi
uppstokkun array aftur

175
00:08:47,589 --> 00:08:49,130
og athuga til að sjá hvort það er flokkað.

176
00:08:49,130 --> 00:08:51,671
Og eins og þú geta sennilega imagine--
þú getur ímyndað sér aðstæður

177
00:08:51,671 --> 00:08:55,200
hvar í versta falli, að vilji
aldrei að byrja með array.

178
00:08:55,200 --> 00:08:57,150
Að reiknirit myndi hlaupa að eilífu.

179
00:08:57,150 --> 00:08:59,349
Og svo að væri
óendanlegur tími reiknirit.

180
00:08:59,349 --> 00:09:01,890
Vonandi verður þú ekki vera að skrifa
allir þáttatilraun eða óendanlega tíma

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

182
00:09:04,510 --> 00:09:09,150
>> Svo, við skulum taka a lítill fleiri
steypu líta á sumir einfaldara

183
00:09:09,150 --> 00:09:11,154
computational flókið bekkjum.

184
00:09:11,154 --> 00:09:13,070
Þannig að við höfum example--
eða tvö dæmi here--

185
00:09:13,070 --> 00:09:15,590
föstu tíma reiknirit,
sem alltaf taka

186
00:09:15,590 --> 00:09:17,980
einn gangur í versta falli.

187
00:09:17,980 --> 00:09:20,050
Svo fyrsta example--
við höfum virka

188
00:09:20,050 --> 00:09:23,952
kallað 4 fyrir þig, sem
tekur á fjölbreytta stærð 1.000.

189
00:09:23,952 --> 00:09:25,660
En þá virðist
er í raun ekki líta

190
00:09:25,660 --> 00:09:29,000
á it-- er eiginlega alveg sama hvað er
inni af því, að þessi fylking.

191
00:09:29,000 --> 00:09:30,820
Alltaf bara skilar fjórum.

192
00:09:30,820 --> 00:09:32,940
Svo, að reiknirit,
Þrátt fyrir að það

193
00:09:32,940 --> 00:09:35,840
tekur 1.000 þætti ekki
gera neitt með þeim.

194
00:09:35,840 --> 00:09:36,590
Bara skilar fjórir.

195
00:09:36,590 --> 00:09:38,240
Það er alltaf einu skrefi.

196
00:09:38,240 --> 00:09:41,600
>> Í raun, bæta við 2 nums-- sem
við höfum séð áður og well--

197
00:09:41,600 --> 00:09:43,680
bara ferli tvær heiltölur.

198
00:09:43,680 --> 00:09:44,692
Það er ekki einu skrefi.

199
00:09:44,692 --> 00:09:45,900
Það er í raun nokkur skref.

200
00:09:45,900 --> 00:09:50,780
Þú færð, þú færð b, þú bætir við þeim
saman, og þú framleiðsla niðurstöður.

201
00:09:50,780 --> 00:09:53,270
Svo það er 84 skrefum.

202
00:09:53,270 --> 00:09:55,510
En það er alltaf stöðug,
óháð a eða b.

203
00:09:55,510 --> 00:09:59,240
Þú þarft að fá, fá b, bæta
þá saman, framleiðsla niðurstaðan.

204
00:09:59,240 --> 00:10:02,900
Svo er það stöðug tími reiknirit.

205
00:10:02,900 --> 00:10:05,170
>> Hér er dæmi um a
línuleg tími algorithm--

206
00:10:05,170 --> 00:10:08,740
reiknirit sem gets-- sem tekur
einu viðbótar skref, hugsanlega,

207
00:10:08,740 --> 00:10:10,740
eins inntak vex um 1.

208
00:10:10,740 --> 00:10:14,190
Svo, við skulum segja að við erum að leita að
fjöldi 5 inni fylki.

209
00:10:14,190 --> 00:10:16,774
Þú gætir hafa aðstæður þar
þú getur fundið það nokkuð snemma.

210
00:10:16,774 --> 00:10:18,606
En þú getur líka hafa
ástand þar sem það

211
00:10:18,606 --> 00:10:20,450
gæti verið síðasta þáttur í array.

212
00:10:20,450 --> 00:10:23,780
Í fjölda af stærð 5, ef
við erum að leita að númer 5.

213
00:10:23,780 --> 00:10:25,930
Það myndi taka 5 skref.

214
00:10:25,930 --> 00:10:29,180
Og í raun, ímynda sér að það er
ekki 5 hvar sem er í þessu fylki.

215
00:10:29,180 --> 00:10:32,820
Við enn í raun að líta á
hvert einasta þáttur í fylkinu

216
00:10:32,820 --> 00:10:35,550
í því skyni að ákvarða
hvort 5 er þar.

217
00:10:35,550 --> 00:10:39,840
>> Svo í versta tilfelli, sem er að
þáttur er síðasta í array

218
00:10:39,840 --> 00:10:41,700
eða er ekki til á öllum.

219
00:10:41,700 --> 00:10:44,690
Við höfum enn að horfa á
öllu af N þáttum.

220
00:10:44,690 --> 00:10:47,120
Og svo þetta reiknirit
keyrir í línulegum tíma.

221
00:10:47,120 --> 00:10:50,340
Þú getur staðfest það með því að
framreikna svolítið með því að segja,

222
00:10:50,340 --> 00:10:53,080
ef við hefðum 6 þátturinn array og
við vorum að leita að númer 5,

223
00:10:53,080 --> 00:10:54,890
það gæti tekið 6 skrefum.

224
00:10:54,890 --> 00:10:57,620
Ef við höfum 7 þátturinn array og
við erum að leita að númer 5.

225
00:10:57,620 --> 00:10:59,160
Það gæti tekið 7 skrefum.

226
00:10:59,160 --> 00:11:02,920
Eins og við bæta við einum stak okkar
array, það tekur eitt skref.

227
00:11:02,920 --> 00:11:06,750
Það er línulegt reiknirit
í versta falli.

228
00:11:06,750 --> 00:11:08,270
>> Par fljótur spurningar fyrir þig.

229
00:11:08,270 --> 00:11:11,170
Hvað er runtime-- hvað er
versta afturkreistingur

230
00:11:11,170 --> 00:11:13,700
af þessu tiltekna runu af kóða?

231
00:11:13,700 --> 00:11:17,420
Þannig að ég hef 4 lykkju hér sem keyrir
frá J jafngildir 0, alla leið upp að m.

232
00:11:17,420 --> 00:11:21,980
Og það sem ég er að sjá hér, er að
Lík lykkju keyrir á föstu tíma.

233
00:11:21,980 --> 00:11:24,730
Svo nota hugtök sem
við höfum þegar talað about-- hvað

234
00:11:24,730 --> 00:11:29,390
væri versta
afturkreistingur þessa reiknirit?

235
00:11:29,390 --> 00:11:31,050
Taktu annað.

236
00:11:31,050 --> 00:11:34,270
Innri hluta lykkju
keyrir í föstu tíma.

237
00:11:34,270 --> 00:11:37,510
Og ytri hluti af
lykkja er að fara að keyra m sinnum.

238
00:11:37,510 --> 00:11:40,260
Svo er það versta afturkreistingur hér?

239
00:11:40,260 --> 00:11:43,210
Vissir þú giska stór-O á m?

240
00:11:43,210 --> 00:11:44,686
Þú vilt vera rétt.

241
00:11:44,686 --> 00:11:46,230
>> Hvernig væri annað?

242
00:11:46,230 --> 00:11:48,590
Í þetta sinn höfum við
lykkja inni í lykkju.

243
00:11:48,590 --> 00:11:50,905
Við höfum ytri lykkju
sem liggur frá núll til bls.

244
00:11:50,905 --> 00:11:54,630
Og við höfum innra lykkja sem keyrir
frá núll til p, og inni í því,

245
00:11:54,630 --> 00:11:57,890
Ég fullyrði að líkaminn er
lykkja keyrir á föstu tíma.

246
00:11:57,890 --> 00:12:02,330
Svo er það versta afturkreistingur
af þessu tiltekna runu af kóða?

247
00:12:02,330 --> 00:12:06,140
Jæja, aftur, við höfum
ytri lykkja sem keyrir bls sinnum.

248
00:12:06,140 --> 00:12:09,660
Og hver time-- endurtekning
þeirrar lykkju, frekar.

249
00:12:09,660 --> 00:12:13,170
Við höfum innra lykkja
sem einnig rekur bls sinnum.

250
00:12:13,170 --> 00:12:16,900
Og þá inni að það er
stöðug time-- lítið runu þar.

251
00:12:16,900 --> 00:12:19,890
>> Svo ef við höfum ytri lykkja sem
rekur p sinnum inni sem er

252
00:12:19,890 --> 00:12:22,880
innri lykkja sem
rekur bls times-- hvað er

253
00:12:22,880 --> 00:12:26,480
versta afturkreistingur
þessarar runu af kóða?

254
00:12:26,480 --> 00:12:30,730
Vissir þú giska stór-O p veldi?

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

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

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