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

2
00:00:05,830 --> 00:00:07,910
>> Selvä, joten, laskennallinen vaativuus.

3
00:00:07,910 --> 00:00:10,430
Vain vähän varoitus
ennen kuin sukeltaa liian far--

4
00:00:10,430 --> 00:00:13,070
tämä varmaan joukossa
eniten matematiikka-raskaita asioita

5
00:00:13,070 --> 00:00:14,200
puhumme CS50.

6
00:00:14,200 --> 00:00:16,950
Toivottavasti se ei ole liian suuri
ja me yritämme ja opastaa

7
00:00:16,950 --> 00:00:19,200
prosessin läpi, mutta
vain hieman reilun varoituksen.

8
00:00:19,200 --> 00:00:21,282
Siellä on hieman
matematiikkaa mukana täällä.

9
00:00:21,282 --> 00:00:23,990
Selvä, joten jotta
käyttää meidän laskentaresursseja

10
00:00:23,990 --> 00:00:28,170
todellisessa world-- se on todella
tärkeää ymmärtää algoritmeja

11
00:00:28,170 --> 00:00:30,750
ja miten ne käsittelevät tiedot.

12
00:00:30,750 --> 00:00:32,810
Jos meillä on todella
tehokas algoritmi, me

13
00:00:32,810 --> 00:00:36,292
voi minimoida resurssien
meillä on käytettävissä käsitellä sitä.

14
00:00:36,292 --> 00:00:38,750
Jos meillä on algoritmi, joka
vie paljon työtä

15
00:00:38,750 --> 00:00:41,210
käsitellä todella
suuri joukko tietoja, se on

16
00:00:41,210 --> 00:00:44,030
aikoo vaatia lisää
ja enemmän resursseja, jotka

17
00:00:44,030 --> 00:00:47,980
on rahaa, RAM, kaikki tuollaista.

18
00:00:47,980 --> 00:00:52,090
>> Niin, että voimme analysoida
algoritmi tällä työkalusarja,

19
00:00:52,090 --> 00:00:56,110
pohjimmiltaan, kysyy question--
miten tämä algoritmi asteikko

20
00:00:56,110 --> 00:00:59,020
kuten me heittää enemmän ja enemmän tietoja se?

21
00:00:59,020 --> 00:01:02,220
In CS50, datan määrä olemme
kanssa on melko pieni.

22
00:01:02,220 --> 00:01:05,140
Yleensä meidän ohjelmat ovat menossa
ajaa toisen tai less--

23
00:01:05,140 --> 00:01:07,830
luultavasti paljon vähemmän
erityisesti varhain.

24
00:01:07,830 --> 00:01:12,250
>> Mutta ajattele yritys, joka käsittelee
satoja miljoonia asiakkaita.

25
00:01:12,250 --> 00:01:14,970
Ja he tarvitsevat prosessin
että asiakkaan tiedot.

26
00:01:14,970 --> 00:01:18,260
Koska asiakkaiden määrä he
on saa suurempia ja suurempia,

27
00:01:18,260 --> 00:01:21,230
se tulee vaatia
enemmän ja enemmän resursseja.

28
00:01:21,230 --> 00:01:22,926
Kuinka monta resursseja?

29
00:01:22,926 --> 00:01:25,050
No, se riippuu siitä, miten
analysoimme algoritmi,

30
00:01:25,050 --> 00:01:28,097
työkaluilla tässä työkalupakin.

31
00:01:28,097 --> 00:01:31,180
Kun puhumme monimutkaisuus
algorithm-- joka joskus ll

32
00:01:31,180 --> 00:01:34,040
kuulla sen nimitystä aika
monimutkaisuus tai tilaa monimutkaisuus

33
00:01:34,040 --> 00:01:36,190
mutta me vain menossa
soittaa complexity--

34
00:01:36,190 --> 00:01:38,770
me yleensä puhumme
pahimmassa tapauksessa.

35
00:01:38,770 --> 00:01:42,640
Koska ehdoton pahin kasa
tiedot että voisimme heittää sitä,

36
00:01:42,640 --> 00:01:46,440
miten tämä algoritmi menossa
käsitellä tai käsitellä että tiedot?

37
00:01:46,440 --> 00:01:51,450
Olemme yleensä kutsumme pahin
runtime algoritmin iso-O.

38
00:01:51,450 --> 00:01:56,770
Niin algoritmi voidaan sanoa
ajaa O n tai O n neliö.

39
00:01:56,770 --> 00:01:59,110
Ja enemmän siitä, mitä
ne tarkoittavat toista.

40
00:01:59,110 --> 00:02:01,620
>> Joskus kuitenkin, teemme hoito
noin parhaassa tapauksessa.

41
00:02:01,620 --> 00:02:05,400
Jos tiedot on kaiken mitä halusimme
sen olevan ja se oli aivan täydellinen

42
00:02:05,400 --> 00:02:09,630
ja olimme lähettää tämä täydellinen
tietotaulukoista kautta algoritmi.

43
00:02:09,630 --> 00:02:11,470
Miten se hoitaa tässä tilanteessa?

44
00:02:11,470 --> 00:02:15,050
Joskus viittaavat että
iso-Omega, joten toisin kuin iso-O,

45
00:02:15,050 --> 00:02:16,530
meillä on iso-Omega.

46
00:02:16,530 --> 00:02:18,880
Iso-Omega paras mahdollinen tilanne.

47
00:02:18,880 --> 00:02:21,319
Big-O pahin skenaario.

48
00:02:21,319 --> 00:02:23,860
Yleensä kun puhumme
monimutkaisuus algoritmi,

49
00:02:23,860 --> 00:02:26,370
me puhumme
pahimmassa tapauksessa.

50
00:02:26,370 --> 00:02:28,100
Niin pitää tämä mielessä.

51
00:02:28,100 --> 00:02:31,510
>> Ja tässä luokassa, me yleensä menossa
jättää analysoitava syrjään.

52
00:02:31,510 --> 00:02:35,350
On tieteiden ja kentät
omistettu tällaista kamaa.

53
00:02:35,350 --> 00:02:37,610
Kun puhumme perustelut
kautta algoritmeja,

54
00:02:37,610 --> 00:02:41,822
joka teemme pala-by-osainen monille
algoritmit puhumme luokassa.

55
00:02:41,822 --> 00:02:44,780
Olemme todella vain puhu
päättely läpi järkeä,

56
00:02:44,780 --> 00:02:47,070
ei kaavat, tai todisteita,
tai jotain sellaista.

57
00:02:47,070 --> 00:02:51,600
Joten älä huoli, Emme
muuttumassa iso matematiikka luokka.

58
00:02:51,600 --> 00:02:55,920
>> Joten sanoin välitämme monimutkaisuus
koska se kysyy, miten

59
00:02:55,920 --> 00:03:00,160
teemme algoritmeja käsitellä suurempia ja
Suuremmat tietokokonaisuuksien heitetään niitä.

60
00:03:00,160 --> 00:03:01,960
No, mikä on tietojen joukko?

61
00:03:01,960 --> 00:03:03,910
Mitä minä tarkoitan, kun sanoin, että?

62
00:03:03,910 --> 00:03:07,600
Se tarkoittaa mikä tekee eniten
järkeä yhteydessä, olla rehellinen.

63
00:03:07,600 --> 00:03:11,160
Jos meillä on algoritmi,
Prosessit Strings-- olemme luultavasti

64
00:03:11,160 --> 00:03:13,440
puhumme koko merkkijono.

65
00:03:13,440 --> 00:03:15,190
Se tietojen set--
koko, lukumäärä

66
00:03:15,190 --> 00:03:17,050
merkkien, jotka muodostavat merkkijono.

67
00:03:17,050 --> 00:03:20,090
Jos puhumme
algoritmi, joka käsittelee tiedostoja,

68
00:03:20,090 --> 00:03:23,930
voisimme puhua miten
monet kilotavua käsittävät tiedoston.

69
00:03:23,930 --> 00:03:25,710
Ja se on tietojen käyttöä.

70
00:03:25,710 --> 00:03:28,870
Jos puhumme algoritmi
joka käsittelee paneelit yleisemmin,

71
00:03:28,870 --> 00:03:31,510
kuten lajittelualgoritmeja
tai etsivät algoritmeja,

72
00:03:31,510 --> 00:03:36,690
me luultavasti puhumme numero
elementtejä, jotka käsittävät erilaisia.

73
00:03:36,690 --> 00:03:39,272
>> Nyt voimme mitata
algorithm-- erityisesti,

74
00:03:39,272 --> 00:03:40,980
kun sanon voimme
mitata algoritmi, I

75
00:03:40,980 --> 00:03:43,840
voimme mitata, kuinka
paljon resursseja se vie.

76
00:03:43,840 --> 00:03:48,990
Ovatko nämä resurssit ovat, kuinka monta
tavua RAM-- tai megatavua RAM-muistia

77
00:03:48,990 --> 00:03:49,790
se käyttää.

78
00:03:49,790 --> 00:03:52,320
Tai kuinka paljon aikaa se vie ajaa.

79
00:03:52,320 --> 00:03:56,200
Voimme kutsua tätä
mitata, mielivaltaisesti, f n.

80
00:03:56,200 --> 00:03:59,420
Jossa n on määrä
elementtejä tietokokonaisuutta.

81
00:03:59,420 --> 00:04:02,640
Ja f n on, kuinka monta somethings.

82
00:04:02,640 --> 00:04:07,530
Kuinka monta resurssia ei
se edellyttää käsitellä näitä tietoja.

83
00:04:07,530 --> 00:04:10,030
>> Nyt oikeastaan ​​välitä
mitä f n on täsmälleen.

84
00:04:10,030 --> 00:04:13,700
Itse asiassa olemme hyvin harvoin will--
varmasti koskaan tässä class-- I

85
00:04:13,700 --> 00:04:18,709
sukeltaa mitään todella syvä
analyysi siitä, mitä f n on.

86
00:04:18,709 --> 00:04:23,510
Olemme juuri menossa puhua siitä, mitä f
n on noin tai mitä se pyrkii.

87
00:04:23,510 --> 00:04:27,600
Ja taipumus algoritmi on
sanelee sen huipputasolla aikavälillä.

88
00:04:27,600 --> 00:04:29,440
Ja voimme nähdä, mitä minä
tarkoitamme, että ottamalla

89
00:04:29,440 --> 00:04:31,910
katso enemmän konkreettinen esimerkki.

90
00:04:31,910 --> 00:04:34,620
>> Joten sanoa, että meillä on
kolme eri algoritmeja.

91
00:04:34,620 --> 00:04:39,350
Joista ensimmäinen kestää n
kuutioitu, jotkut resurssia

92
00:04:39,350 --> 00:04:42,880
käsitellä datasarjan koko on n.

93
00:04:42,880 --> 00:04:47,000
Meillä on toinen algoritmi, joka vie
n kuutioitu plus n potenssiin resurssit

94
00:04:47,000 --> 00:04:49,350
käsitellä datasarjan koko on n.

95
00:04:49,350 --> 00:04:52,030
Ja meillä on kolmasosa
algoritmi, joka toimii in--, että

96
00:04:52,030 --> 00:04:58,300
vie n kuutioitu miinus 8n potenssiin
plus 20 n resurssia

97
00:04:58,300 --> 00:05:02,370
käsitellä algoritmi
tietoja asettaa koko on n.

98
00:05:02,370 --> 00:05:05,594
>> Nyt taas, emme todellakaan aio
päästä tämän tason yksityiskohtia.

99
00:05:05,594 --> 00:05:08,260
Olen todella vain on näitä ylös
täällä esimerkki pisteen

100
00:05:08,260 --> 00:05:10,176
että aion olla
jolloin toisessa, joka

101
00:05:10,176 --> 00:05:12,980
on, että me vain todella varovainen
noin taipumus asioita

102
00:05:12,980 --> 00:05:14,870
kuten aineistoja saada isompi.

103
00:05:14,870 --> 00:05:18,220
Joten jos tiedot joukko on pieni, siellä
oikeastaan ​​aika iso ero

104
00:05:18,220 --> 00:05:19,870
näissä algoritmit.

105
00:05:19,870 --> 00:05:23,000
Kolmas algoritmi siellä
kestää 13 kertaa pidempään,

106
00:05:23,000 --> 00:05:27,980
13 kertaa enemmän resursseja
juosta suhteessa ensimmäiseen palloon.

107
00:05:27,980 --> 00:05:31,659
>> Jos meidän tietokokonaisuus on koko 10, joka
on suurempi, mutta ei välttämättä suuria,

108
00:05:31,659 --> 00:05:33,950
voimme nähdä, että on olemassa
itse asiassa hieman eroa.

109
00:05:33,950 --> 00:05:36,620
Kolmas algoritmi
tehostuu.

110
00:05:36,620 --> 00:05:40,120
Se on noin oikeastaan ​​40% -
tai 60% tehokkaampi.

111
00:05:40,120 --> 00:05:41,580
Se kestää 40% aikaa.

112
00:05:41,580 --> 00:05:45,250
Se voi run-- se voi kestää
400 resurssia

113
00:05:45,250 --> 00:05:47,570
käsitellä tietoja joukko koko 10.

114
00:05:47,570 --> 00:05:49,410
Kun taas ensimmäinen
algoritmi, sen sijaan,

115
00:05:49,410 --> 00:05:54,520
ottaa 1000 resurssia
käsitellä tietoja joukko koko 10.

116
00:05:54,520 --> 00:05:57,240
Mutta katsokaa mitä tapahtuu
meidän numerot saada isompi.

117
00:05:57,240 --> 00:05:59,500
>> Nyt ero
näiden algoritmien

118
00:05:59,500 --> 00:06:01,420
alkaa tulla hieman vähemmän ilmeinen.

119
00:06:01,420 --> 00:06:04,560
Ja se, että on olemassa
alemman asteen terms-- tai pikemminkin,

120
00:06:04,560 --> 00:06:09,390
toimeen alempi exponents--
alkaa tulla merkityksettömiä.

121
00:06:09,390 --> 00:06:12,290
Jos datasarja on koko
1000 ja ensimmäinen algoritmi

122
00:06:12,290 --> 00:06:14,170
toimii miljardia vaiheita.

123
00:06:14,170 --> 00:06:17,880
Ja toinen algoritmi toimii
miljardi ja miljoona vaiheita.

124
00:06:17,880 --> 00:06:20,870
Ja kolmas algoritmi toimii
vain ujo miljardin vaiheita.

125
00:06:20,870 --> 00:06:22,620
Se on aika paljon miljardia vaiheita.

126
00:06:22,620 --> 00:06:25,640
Ne alemman asteen termit alkaa
tulla todella merkitystä.

127
00:06:25,640 --> 00:06:27,390
Ja vain todella
hammer koti point--

128
00:06:27,390 --> 00:06:31,240
jos tietojen syöttö on koko
million-- kaikki nämä kolme melko paljon

129
00:06:31,240 --> 00:06:34,960
ottaa yksi quintillion-- jos
minun matematiikka on correct-- vaiheet

130
00:06:34,960 --> 00:06:37,260
käsitellä tietojen syöttö
koosta miljoonaa euroa.

131
00:06:37,260 --> 00:06:38,250
Se on paljon portaita.

132
00:06:38,250 --> 00:06:42,092
Ja se, että yksi heistä voisi
ottaa pari 100000, tai pari 100

133
00:06:42,092 --> 00:06:44,650
milj vielä vähemmän kun
puhumme numero

134
00:06:44,650 --> 00:06:46,990
että big-- se on eräänlainen merkitystä.

135
00:06:46,990 --> 00:06:50,006
Ne kaikki on taipumus ottaa
noin n kuutioitu,

136
00:06:50,006 --> 00:06:52,380
ja niin me todella viitata
kaikki nämä algoritmit

137
00:06:52,380 --> 00:06:59,520
olevan suuruusluokkaa n
kuutioitu tai iso-O n kuutioitu.

138
00:06:59,520 --> 00:07:03,220
>> Tässä luettelo joistakin enemmän
yhteinen laskennallinen vaativuus luokat

139
00:07:03,220 --> 00:07:05,820
että me kohtaamme
algoritmeja, yleensä.

140
00:07:05,820 --> 00:07:07,970
Ja nimenomaan myös CS50.

141
00:07:07,970 --> 00:07:11,410
Nämä tilataan
yleensä nopein huipulla,

142
00:07:11,410 --> 00:07:13,940
yleisesti hitain alareunassa.

143
00:07:13,940 --> 00:07:16,920
Joten jatkuva aika algoritmeja yleensä
olla nopein, riippumatta

144
00:07:16,920 --> 00:07:19,110
koon
Tietojen syöttäminen ohitat.

145
00:07:19,110 --> 00:07:23,760
He aina ottaa yksi toiminnan tai
yhden yksikön resursseja käsitellä.

146
00:07:23,760 --> 00:07:25,730
Se voi olla 2, se saattaa
olla 3, se voi olla 4.

147
00:07:25,730 --> 00:07:26,910
Mutta se on vakiomäärä.

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

149
00:07:28,400 --> 00:07:31,390
>> Logaritminen aika algoritmit
ovat hieman paremmat.

150
00:07:31,390 --> 00:07:33,950
Ja todella hyvä esimerkki
logaritminen aika algoritmi

151
00:07:33,950 --> 00:07:37,420
olet varmasti nähdä nyt on
repimällä puhelinluettelon

152
00:07:37,420 --> 00:07:39,480
löytää Mike Smith puhelinluettelosta.

153
00:07:39,480 --> 00:07:40,980
Leikkaamme ongelma kahtia.

154
00:07:40,980 --> 00:07:43,580
Ja niin n suurenee
ja suurempia ja larger--

155
00:07:43,580 --> 00:07:47,290
Itse asiassa joka kerta kun kaksinkertainen
n, se kestää vain yksi askel.

156
00:07:47,290 --> 00:07:49,770
Niin, että on paljon parempi
kuin vaikkapa lineaarisen ajan.

157
00:07:49,770 --> 00:07:53,030
Joka on jos kaksinkertainen n, se
ottaa kaksinkertainen määrä vaiheita.

158
00:07:53,030 --> 00:07:55,980
Jos kolminkertaistaa n, se kestää
kolminkertaistaa useita vaiheita.

159
00:07:55,980 --> 00:07:58,580
Yksi askel kohti.

160
00:07:58,580 --> 00:08:01,790
>> Sitten asiat saavat hieman more--
hieman vähemmän suuria sieltä.

161
00:08:01,790 --> 00:08:06,622
Sinulla on lineaarinen rytminen aikaa, joskus
nimeltään loki lineaarisen ajan tai vain n log n.

162
00:08:06,622 --> 00:08:08,330
Ja me esimerkki
ja algoritmi, joka

163
00:08:08,330 --> 00:08:13,370
kulkee n log n, joka on vielä parempi
kuin asteen time-- n potenssiin.

164
00:08:13,370 --> 00:08:17,320
Tai polynomiaikainen, n kaksi
mikä tahansa luku suurempi kuin kaksi.

165
00:08:17,320 --> 00:08:20,810
Tai eksponentiaalisesti enemmän aikaa, joka
on jopa worse-- C n.

166
00:08:20,810 --> 00:08:24,670
Joten jotkut vakio numero nostetaan
voima koko panos.

167
00:08:24,670 --> 00:08:28,990
Joten jos on 1,000-- jos
tietojen syöttö on koko 1000,

168
00:08:28,990 --> 00:08:31,310
se veisi C 1000. valtaa.

169
00:08:31,310 --> 00:08:33,559
Se on paljon pahempi kuin polynomiajassa.

170
00:08:33,559 --> 00:08:35,030
>> Kertoma aika on vielä pahempi.

171
00:08:35,030 --> 00:08:37,760
Ja itse asiassa, ei todellakaan tee
olemassa ääretön aika algoritmeja,

172
00:08:37,760 --> 00:08:43,740
kuten ns tyhmä sort-- joiden
työ on satunnaisesti shuffle array

173
00:08:43,740 --> 00:08:45,490
ja sitten tarkistaa,
onko se lajitellaan.

174
00:08:45,490 --> 00:08:47,589
Ja jos se ei ole, satunnaisesti
shuffle array uudelleen

175
00:08:47,589 --> 00:08:49,130
ja tarkista, onko se lajitellaan.

176
00:08:49,130 --> 00:08:51,671
Ja kuten voitte luultavasti imagine--
voit kuvitella tilanne

177
00:08:51,671 --> 00:08:55,200
jossa pahimmassa-tapauksessa, että tahto
koskaan todella alkaa kanssa jono.

178
00:08:55,200 --> 00:08:57,150
Tämä algoritmi kulkisi ikuisesti.

179
00:08:57,150 --> 00:08:59,349
Ja että olisi
ääretön aika algoritmi.

180
00:08:59,349 --> 00:09:01,890
Toivottavasti et kirjallisesti
kaikki kertoma tai ääretön aika

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

182
00:09:04,510 --> 00:09:09,150
>> Niin, sallikaa hieman enemmän
betoni tarkastelemme joitakin yksinkertaisempi

183
00:09:09,150 --> 00:09:11,154
laskennallinen monimutkaisuus luokat.

184
00:09:11,154 --> 00:09:13,070
Meillä on siis example--
tai kaksi esimerkkiä here--

185
00:09:13,070 --> 00:09:15,590
jatkuvasti ajan algoritmeja,
joka aina

186
00:09:15,590 --> 00:09:17,980
yksittäinen operaatio pahimman.

187
00:09:17,980 --> 00:09:20,050
Joten ensimmäinen example--
meillä funktio

188
00:09:20,050 --> 00:09:23,952
kehotti 4 sinulle, joka
ottaa taulukon koko 1000.

189
00:09:23,952 --> 00:09:25,660
Mutta sitten ilmeisesti
ei varsinaisesti katso

190
00:09:25,660 --> 00:09:29,000
klo it-- ei välitä mitä
sen sisällä, ja että jono.

191
00:09:29,000 --> 00:09:30,820
Aina vain palauttaa neljä.

192
00:09:30,820 --> 00:09:32,940
Niin, että algoritmi,
huolimatta siitä, että se

193
00:09:32,940 --> 00:09:35,840
vie 1000 elementtejä ei
niitä mitenkään.

194
00:09:35,840 --> 00:09:36,590
Palaa aivan neljä.

195
00:09:36,590 --> 00:09:38,240
On aina yksi askel.

196
00:09:38,240 --> 00:09:41,600
>> Itse asiassa, lisätään 2 nums-- joka
olemme nähneet ennen kuin well--

197
00:09:41,600 --> 00:09:43,680
vain käsittelee kaksi kokonaislukua.

198
00:09:43,680 --> 00:09:44,692
Se ei askeltakaan.

199
00:09:44,692 --> 00:09:45,900
Se on oikeastaan ​​pari askelta.

200
00:09:45,900 --> 00:09:50,780
Saat, saat b, lisäät ne
yhteen, ja te tuotos tuloksia.

201
00:09:50,780 --> 00:09:53,270
Joten se on 84 vaiheet.

202
00:09:53,270 --> 00:09:55,510
Mutta se on aina vakio,
riippumatta tai b.

203
00:09:55,510 --> 00:09:59,240
Sinun täytyy saada, saada b, lisätä
ne yhteen, tuotos tulos.

204
00:09:59,240 --> 00:10:02,900
Niin, että jatkuva algoritmi.

205
00:10:02,900 --> 00:10:05,170
>> Tässä on esimerkki
lineaarinen aika algorithm--

206
00:10:05,170 --> 00:10:08,740
algoritmi, joka gets--, joka vie
yksi ylimääräinen vaihe, mahdollisesti,

207
00:10:08,740 --> 00:10:10,740
kuin panos kasvaa 1.

208
00:10:10,740 --> 00:10:14,190
Joten sanokaamme etsimme
numero 5 sisällä array.

209
00:10:14,190 --> 00:10:16,774
Saatat olla tilanteessa, jossa
löydät sen melko aikaisin.

210
00:10:16,774 --> 00:10:18,606
Mutta voit myös olla
tilanteessa, jossa se

211
00:10:18,606 --> 00:10:20,450
ehkä viimeinen alkiota.

212
00:10:20,450 --> 00:10:23,780
Riviksi nro 5, jos
etsimme numero 5.

213
00:10:23,780 --> 00:10:25,930
Se veisi 5 askelta.

214
00:10:25,930 --> 00:10:29,180
Ja itse asiassa, kuvitella, että on olemassa
ei 5 missään tässä array.

215
00:10:29,180 --> 00:10:32,820
Meillä on vielä todella on tarkasteltava
jokainen alkio

216
00:10:32,820 --> 00:10:35,550
jotta voidaan määrittää
onko 5 on siellä.

217
00:10:35,550 --> 00:10:39,840
>> Joten pahimmassa tapauksessa, joka on, että
elementti on viimeinen array

218
00:10:39,840 --> 00:10:41,700
tai ei ole olemassa lainkaan.

219
00:10:41,700 --> 00:10:44,690
Meillä on vielä tarkasteltava
kaikki n elementtiä.

220
00:10:44,690 --> 00:10:47,120
Ja niin tämä algoritmi
toimii lineaarisessa ajassa.

221
00:10:47,120 --> 00:10:50,340
Voit vahvistaa, että
ekstrapoloimalla hieman sanomalla,

222
00:10:50,340 --> 00:10:53,080
jos meillä oli 6-elementti array ja
etsimme numero 5,

223
00:10:53,080 --> 00:10:54,890
se saattaa kestää 6 askelmaa.

224
00:10:54,890 --> 00:10:57,620
Jos meillä on 7-elementti array ja
etsimme numero 5.

225
00:10:57,620 --> 00:10:59,160
Se saattaa kestää 7 porrasta.

226
00:10:59,160 --> 00:11:02,920
Kuten me lisätä vielä yhden elementin meidän
array, se vie yksi askel.

227
00:11:02,920 --> 00:11:06,750
Se lineaarinen algoritmi
pahimmassa-tapauksessa.

228
00:11:06,750 --> 00:11:08,270
>> Muutaman nopeaa kysymyksiin sinulle.

229
00:11:08,270 --> 00:11:11,170
Mikä runtime-- mitä
pahin runtime

230
00:11:11,170 --> 00:11:13,700
tämän nimenomaisen koodinpätkä?

231
00:11:13,700 --> 00:11:17,420
Joten minulla on 4 silmukka täällä joka kulkee
vaiheesta j on 0, kaikki tavalla jopa metrin.

232
00:11:17,420 --> 00:11:21,980
Ja mitä näen täällä, on että
elin silmukka kulkee jatkuvasti ajan.

233
00:11:21,980 --> 00:11:24,730
Joten käyttämällä termeistä
olemme jo puhuneet about-- mitä

234
00:11:24,730 --> 00:11:29,390
olisi pahin
runtime Tämän algoritmin?

235
00:11:29,390 --> 00:11:31,050
Ota toinen.

236
00:11:31,050 --> 00:11:34,270
Sisäosan silmukan
toimii jatkuvasti ajan.

237
00:11:34,270 --> 00:11:37,510
Ja ulompi osa
silmukka tulee ajaa m kertaa.

238
00:11:37,510 --> 00:11:40,260
Niin mitä pahin runtime täällä?

239
00:11:40,260 --> 00:11:43,210
Arvasit iso-O, m?

240
00:11:43,210 --> 00:11:44,686
Olisit oikeassa.

241
00:11:44,686 --> 00:11:46,230
>> Entä toinen?

242
00:11:46,230 --> 00:11:48,590
Tällä kertaa meillä
silmukka silmukan sisällä.

243
00:11:48,590 --> 00:11:50,905
Meillä ulomman silmukan
joka kulkee nollasta s.

244
00:11:50,905 --> 00:11:54,630
Ja meillä on sisemmän silmukan, joka toimii
nollasta p, ja sisältä että,

245
00:11:54,630 --> 00:11:57,890
Totean, että elin
silmukka toimii jatkuvasti ajan.

246
00:11:57,890 --> 00:12:02,330
Niin mitä pahin runtime
tämän nimenomaisen koodinpätkä?

247
00:12:02,330 --> 00:12:06,140
No, taas, meillä on
ulompi silmukka, joka kulkee s kertaa.

248
00:12:06,140 --> 00:12:09,660
Ja kukin time-- iteroinnin
Tämän silmukan, melko.

249
00:12:09,660 --> 00:12:13,170
Meillä sisemmän silmukan
että myös toimii s kertaa.

250
00:12:13,170 --> 00:12:16,900
Ja sitten sisällä että siellä
vakio time-- pikku pätkä siellä.

251
00:12:16,900 --> 00:12:19,890
>> Joten jos meillä on ulompi silmukka, joka
kulkee p kertaa jonka sisällä on

252
00:12:19,890 --> 00:12:22,880
sisemmän silmukan, joka
juoksee p times-- mikä on

253
00:12:22,880 --> 00:12:26,480
pahin runtime
Tämän koodinpätkä?

254
00:12:26,480 --> 00:12:30,730
Arvasit iso-O p potenssiin?

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

256
00:12:31,690 --> 00:12:33,880
Tämä on CS50.

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