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

2
00:00:05,830 --> 00:00:07,910
>> Gerai, taip, skaičiavimo sudėtingumas.

3
00:00:07,910 --> 00:00:10,430
Tiesiog įspėjimas tiek
kol mes pasinerti per far--

4
00:00:10,430 --> 00:00:13,070
tai tikriausiai bus tarp
Labiausiai matematikos sunkiųjų dalykai

5
00:00:13,070 --> 00:00:14,200
mes kalbame apie į CS50.

6
00:00:14,200 --> 00:00:16,950
Tikimės, kad tai nebus per didele
ir mes pasistengsime ir padės jums

7
00:00:16,950 --> 00:00:19,200
per procesą, bet
tik iš sąžiningai perspėta tiek.

8
00:00:19,200 --> 00:00:21,282
Yra šiek tiek
matematikos dalyvauja čia.

9
00:00:21,282 --> 00:00:23,990
Visos teisės, todėl, siekiant, kad
naudojimas mūsų skaičiavimo išteklių

10
00:00:23,990 --> 00:00:28,170
realiame world-- tai tikrai
Svarbu suprasti algoritmai

11
00:00:28,170 --> 00:00:30,750
ir kaip jie apdoroti duomenis.

12
00:00:30,750 --> 00:00:32,810
Jei mes turime tikrai
efektyvus algoritmas, mes

13
00:00:32,810 --> 00:00:36,292
gali sumažinti išteklių suma
mes turime rasti kovoti su ja.

14
00:00:36,292 --> 00:00:38,750
Jei mes turime algoritmą, kuris
ketina imtis daug darbo

15
00:00:38,750 --> 00:00:41,210
apdoroti tikrai
didelis duomenų rinkinys, tai

16
00:00:41,210 --> 00:00:44,030
ketina reikalauti daugiau
ir daugiau išteklių, kurie

17
00:00:44,030 --> 00:00:47,980
yra pinigai, RAM, visa tai stuff natūra.

18
00:00:47,980 --> 00:00:52,090
>> Taigi, kad galėtų panagrinėti
algoritmas naudojant šią priemonę rinkinį,

19
00:00:52,090 --> 00:00:56,110
iš esmės, prašo question--
Kaip tai algoritmas skalę

20
00:00:56,110 --> 00:00:59,020
kaip mes išmetame daugiau ir daugiau duomenų iš jo?

21
00:00:59,020 --> 00:01:02,220
Be CS50, duomenų kiekį mes
dirba su gana maža.

22
00:01:02,220 --> 00:01:05,140
Apskritai, mūsų programos vyksta
paleisti antrą ar less--

23
00:01:05,140 --> 00:01:07,830
tikriausiai daug mažiau
ypač anksti.

24
00:01:07,830 --> 00:01:12,250
>> Bet pagalvokite apie kompanija, kuri užsiima
su šimtais milijonų klientų.

25
00:01:12,250 --> 00:01:14,970
Ir jiems reikia apdoroti
kad klientų duomenų.

26
00:01:14,970 --> 00:01:18,260
Kaip klientų skaičiaus jie
turi gauna didesni ir didesni,

27
00:01:18,260 --> 00:01:21,230
jis ketina reikalauti
vis daugiau ir daugiau išteklių.

28
00:01:21,230 --> 00:01:22,926
Kiek daugiau išteklių?

29
00:01:22,926 --> 00:01:25,050
Na, tai priklauso nuo to, kaip
mes analizuoti algoritmus,

30
00:01:25,050 --> 00:01:28,097
naudojant įrankius šiame rinkinį.

31
00:01:28,097 --> 00:01:31,180
Kai kalbame apie sudėtingumo
algorithm-- kurie kartais jums

32
00:01:31,180 --> 00:01:34,040
išgirsti tai vadinama metu
sudėtingumas ar kosmoso sudėtingumas

33
00:01:34,040 --> 00:01:36,190
bet mes tik ketina
skambinti complexity--

34
00:01:36,190 --> 00:01:38,770
mes paprastai kalbame apie
blogiausias scenarijus.

35
00:01:38,770 --> 00:01:42,640
Kadangi absoliutus blogiausias krūva
duomenų, kad galėtume būti mesti į jį,

36
00:01:42,640 --> 00:01:46,440
kaip tai algoritmas ketina
apdoroti arba kovoti su tais duomenimis?

37
00:01:46,440 --> 00:01:51,450
Mes paprastai vadiname blogiausio atvejo
Trukmė algoritmą Big-O.

38
00:01:51,450 --> 00:01:56,770
Taigi algoritmas gali būti sakė
paleisti O N arba O n kvadratu.

39
00:01:56,770 --> 00:01:59,110
Ir daugiau apie tai, ką
tie reiškia per sekundę.

40
00:01:59,110 --> 00:02:01,620
>> Kartais, nors mes darome priežiūros
apie geriausią scenarijų.

41
00:02:01,620 --> 00:02:05,400
Jeigu duomenys yra viskas, ką norėjau
ji būtų, ir tai buvo visiškai tobula

42
00:02:05,400 --> 00:02:09,630
ir mes siunčiant tai puikus
nustatyti duomenų per mūsų algoritmas.

43
00:02:09,630 --> 00:02:11,470
Kaip tai dirbti tokioje situacijoje?

44
00:02:11,470 --> 00:02:15,050
Mes kartais skaitykite, kad
didelis omega, todėl priešingai Big-O,

45
00:02:15,050 --> 00:02:16,530
mes turime didelis Omega.

46
00:02:16,530 --> 00:02:18,880
Big-omega už geriausią scenarijų.

47
00:02:18,880 --> 00:02:21,319
Big-O už blogiausią scenarijų.

48
00:02:21,319 --> 00:02:23,860
Paprastai, kai mes kalbame apie
algoritmą sudėtingumą,

49
00:02:23,860 --> 00:02:26,370
mes kalbame apie
blogiausio atvejo scenarijus.

50
00:02:26,370 --> 00:02:28,100
Taigi keep that in mind.

51
00:02:28,100 --> 00:02:31,510
>> Ir šioje klasėje, mes paprastai vyksta
palikti griežtą analizę nuošalyje.

52
00:02:31,510 --> 00:02:35,350
Yra mokslai ir laukai
Orientacinis šios stuff natūra.

53
00:02:35,350 --> 00:02:37,610
Kai kalbame apie samprotavimo
per algoritmų,

54
00:02:37,610 --> 00:02:41,822
kuri mes padarysime gabalas po gabalo, nes daugelis
algoritmai mes kalbame apie klasėje.

55
00:02:41,822 --> 00:02:44,780
Mes tikrai tik kalbame apie
aiškinosi per jį su sveiku protu,

56
00:02:44,780 --> 00:02:47,070
ne formules, arba įrodymų,
ar kas nors panašaus.

57
00:02:47,070 --> 00:02:51,600
Taigi nesijaudinkite, mes negali būti
virsta dideliu matematikos klasės.

58
00:02:51,600 --> 00:02:55,920
>> Taigi sakiau, mes rūpinamės sudėtingumo
nes ji klausia, kaip

59
00:02:55,920 --> 00:03:00,160
darome algoritmai tvarkyti didesnis ir
didesni duomenų rinkiniai buvo išmesti į juos.

60
00:03:00,160 --> 00:03:01,960
Na, kas yra duomenų rinkinys?

61
00:03:01,960 --> 00:03:03,910
Ką aš turiu galvoje, kai sakiau, kad?

62
00:03:03,910 --> 00:03:07,600
Tai reiškia, ką daro pats
jausmas kontekste, turi būti sąžiningas.

63
00:03:07,600 --> 00:03:11,160
Jei mes turime algoritmą, kad
Procesai Strings-- mes tikriausiai

64
00:03:11,160 --> 00:03:13,440
kalbame apie eilutę dydžio.

65
00:03:13,440 --> 00:03:15,190
Štai duomenys set--
dydis, numeris,

66
00:03:15,190 --> 00:03:17,050
simbolių, kurie sudaro eilutę.

67
00:03:17,050 --> 00:03:20,090
Jei mes kalbame apie
algoritmas, kuris apdoroja failus,

68
00:03:20,090 --> 00:03:23,930
mes galime kalbėti apie tai, kaip
daug kilobaitų sudaro tą failą.

69
00:03:23,930 --> 00:03:25,710
Ir tai duomenų rinkinys.

70
00:03:25,710 --> 00:03:28,870
Jei mes kalbame apie algoritmą
kad rankenos masyvus apskritai,

71
00:03:28,870 --> 00:03:31,510
pvz rūšiavimo algoritmai
ar ieškoti algoritmus,

72
00:03:31,510 --> 00:03:36,690
mes tikriausiai kalbame apie skaičius
elementų, sudarančių masyvo.

73
00:03:36,690 --> 00:03:39,272
>> Dabar mes galime išmatuoti
algorithm-- ypač

74
00:03:39,272 --> 00:03:40,980
kai aš sakau, mes galime
matuoti algoritmą, aš

75
00:03:40,980 --> 00:03:43,840
reiškia, kad mes galime įvertinti, kaip
daug išteklių ji užima.

76
00:03:43,840 --> 00:03:48,990
Nesvarbu, ar tie ištekliai, kiek
baitų RAM-- ar megabaitų RAM

77
00:03:48,990 --> 00:03:49,790
ji naudoja.

78
00:03:49,790 --> 00:03:52,320
Arba, kiek laiko užtrunka paleisti.

79
00:03:52,320 --> 00:03:56,200
Ir mes galime tai vadiname
matuoti, savavališkai, f n.

80
00:03:56,200 --> 00:03:59,420
Kur n yra skaičius
elementai duomenų rinkinį.

81
00:03:59,420 --> 00:04:02,640
Ir f n yra kiek septyniasdešimties.

82
00:04:02,640 --> 00:04:07,530
Kiek resursų vienetų daro
ji reikalauja, kad procesas, duomenis.

83
00:04:07,530 --> 00:04:10,030
>> Dabar mes iš tikrųjų nerūpi
apie tai, ką f n yra tiksliai.

84
00:04:10,030 --> 00:04:13,700
Tiesą sakant, mes labai retai will--
tikrai niekada šiame class-- I

85
00:04:13,700 --> 00:04:18,709
pasinerti į bet tikrai giliai
analizė, ką f n yra.

86
00:04:18,709 --> 00:04:23,510
Užtenka tik ketiname kalbėti apie tai, ką f
n yra maždaug ar ką jis linkęs.

87
00:04:23,510 --> 00:04:27,600
Ir algoritmą tendencija
diktuoja savo aukščiausią užsakymo laikotarpiu.

88
00:04:27,600 --> 00:04:29,440
Ir mes galime pamatyti, ką aš
reiškia, kad atsižvelgiant

89
00:04:29,440 --> 00:04:31,910
pažvelgti labiau konkretus pavyzdys.

90
00:04:31,910 --> 00:04:34,620
>> Taigi tarkime, kad mes turime
trys skirtingi algoritmai.

91
00:04:34,620 --> 00:04:39,350
Iš kurių pirmasis trunka n
kubeliais, kai išteklių vienetai

92
00:04:39,350 --> 00:04:42,880
apdoroti duomenis rinkinį dydžio n.

93
00:04:42,880 --> 00:04:47,000
Mes turime antrą algoritmą, kuris turėjo
N kubeliais plius n kvadrato ištekliai

94
00:04:47,000 --> 00:04:49,350
apdoroti duomenis rinkinį dydžio n.

95
00:04:49,350 --> 00:04:52,030
Ir mes turime trečioji
algoritmas, kuris veikia in-- kad

96
00:04:52,030 --> 00:04:58,300
užima n kubeliais atėmus 8N kvadrato
plius 20 N resursų vienetų

97
00:04:58,300 --> 00:05:02,370
apdoroti algoritmą
su rinkiniu dydžio n duomenis.

98
00:05:02,370 --> 00:05:05,594
>> Dabar vėl, mes tikrai neketiname
patekti į šį detalumo lygiu.

99
00:05:05,594 --> 00:05:08,260
Aš tikrai tereikia juos iki
čia kaip taško iliustracijoje

100
00:05:08,260 --> 00:05:10,176
kad aš ruošiuosi būti
priėmimo per sekundę, kuris

101
00:05:10,176 --> 00:05:12,980
yra tai, kad mes tik tikrai rūpi
apie dalykus tendencija

102
00:05:12,980 --> 00:05:14,870
kaip duomenų rinkinių gauti didesnį.

103
00:05:14,870 --> 00:05:18,220
Taigi, jei duomenų rinkinys yra mažas, ten
iš tikrųjų gana didelis skirtumas

104
00:05:18,220 --> 00:05:19,870
Šiose algoritmo.

105
00:05:19,870 --> 00:05:23,000
Trečiasis algoritmas yra
trunka 13 kartų ilgiau,

106
00:05:23,000 --> 00:05:27,980
13 kartų išteklių suma
paleisti, lyginant su pirmojo.

107
00:05:27,980 --> 00:05:31,659
>> Jei mūsų duomenų rinkinys yra 10 dydžio, kuris
yra didesnis, bet nebūtinai didžiulis,

108
00:05:31,659 --> 00:05:33,950
matome, kad ten
faktiškai skirtumo tiek.

109
00:05:33,950 --> 00:05:36,620
Trečiasis algoritmas
tampa efektyvesnis.

110
00:05:36,620 --> 00:05:40,120
Tai apie faktiškai 40% -
arba 60% efektyvesnis.

111
00:05:40,120 --> 00:05:41,580
Tai užtrunka 40%, kiek laiko.

112
00:05:41,580 --> 00:05:45,250
Jis gali run-- tai gali užtrukti
400 resursų vienetų

113
00:05:45,250 --> 00:05:47,570
apdoroti duomenis rinkinį 10 dydžio.

114
00:05:47,570 --> 00:05:49,410
Kadangi pirmasis
algoritmas, priešingai,

115
00:05:49,410 --> 00:05:54,520
užima 1000 resursų vienetų
apdoroti duomenis rinkinį 10 dydžio.

116
00:05:54,520 --> 00:05:57,240
Bet pažiūrėkite, kas atsitinka, kaip
Mūsų numeriai gauti dar didesni.

117
00:05:57,240 --> 00:05:59,500
>> Dabar, skirtumas
tarp šių algoritmo

118
00:05:59,500 --> 00:06:01,420
pradėti tapti šiek tiek mažiau akivaizdus.

119
00:06:01,420 --> 00:06:04,560
Ir tai, kad yra
žemesnės eilės terms-- arba, tiksliau,

120
00:06:04,560 --> 00:06:09,390
terminai su mažesne exponents--
pradėti tapo nereikšmingi.

121
00:06:09,390 --> 00:06:12,290
Jeigu duomenų rinkinys yra dydžio
1000 ir pirmasis algoritmas

122
00:06:12,290 --> 00:06:14,170
veikia milijardą žingsnius.

123
00:06:14,170 --> 00:06:17,880
Ir antra algoritmas veikia
milijardas ir milijonas žingsniai.

124
00:06:17,880 --> 00:06:20,870
Ir trečia algoritmas veikia
į tiesiog drovus milijardą žingsnius.

125
00:06:20,870 --> 00:06:22,620
Tai gana daug milijardų žingsnių.

126
00:06:22,620 --> 00:06:25,640
Tos mažesnės pavedimo sąlygas pradėti
tapti tikrai nesvarbus.

127
00:06:25,640 --> 00:06:27,390
Ir tik tikrai
kartojami point--

128
00:06:27,390 --> 00:06:31,240
jei duomenų įvesties yra Dydis A
million-- visi šie trys gana daug

129
00:06:31,240 --> 00:06:34,960
išgerkite vieną quintillion-- jei
mano matematika yra correct-- žingsniai

130
00:06:34,960 --> 00:06:37,260
apdoroti įvesties duomenų
dydžio milijono.

131
00:06:37,260 --> 00:06:38,250
Štai keletas žingsnių daug.

132
00:06:38,250 --> 00:06:42,092
Ir faktas, kad vienas iš jų gali
per porą 100.000 ar pora 100

133
00:06:42,092 --> 00:06:44,650
milijonų net mažiau, kai
mes kalbame apie skaičius

134
00:06:44,650 --> 00:06:46,990
kad big-- tai tipo nesvarbus.

135
00:06:46,990 --> 00:06:50,006
Jie visi linkę imtis
maždaug n kubeliais,

136
00:06:50,006 --> 00:06:52,380
ir todėl mes iš tikrųjų kreiptis
visų šių algoritmo

137
00:06:52,380 --> 00:06:59,520
kaip ant n tam
kubeliais arba didelis O n cubed.

138
00:06:59,520 --> 00:07:03,220
>> Štai keletas iš daugiau Sąrašas
bendrieji skaičiavimo sudėtingumas klasės

139
00:07:03,220 --> 00:07:05,820
kad mes susiduriame
algoritmai, dažniausiai.

140
00:07:05,820 --> 00:07:07,970
Ir taip pat konkrečiai CS50.

141
00:07:07,970 --> 00:07:11,410
Tai yra užsakomi iš
paprastai greičiausiai viršuje,

142
00:07:11,410 --> 00:07:13,940
apskritai lėčiausiai apačioje.

143
00:07:13,940 --> 00:07:16,920
Taigi nuolatinis laiko algoritmai linkę
greičiausias, nepriklausomai

144
00:07:16,920 --> 00:07:19,110
nuo dydžio
duomenų įvedimo pereisite į.

145
00:07:19,110 --> 00:07:23,760
Jie visada vieną operaciją ar
vienas vienetas išteklių spręsti.

146
00:07:23,760 --> 00:07:25,730
Tai gali būti 2, tai gali
būti 3, tai gali būti 4.

147
00:07:25,730 --> 00:07:26,910
Bet tai pastovus skaičius.

148
00:07:26,910 --> 00:07:28,400
Ji neturi skirtis.

149
00:07:28,400 --> 00:07:31,390
>> Logaritminė laiko algoritmai
yra šiek tiek geriau.

150
00:07:31,390 --> 00:07:33,950
Ir tikrai geras pavyzdys
logaritminis laikas algoritmas

151
00:07:33,950 --> 00:07:37,420
Jūs tikrai pamatėte dabar yra
Patempimai iš telefonų knygos

152
00:07:37,420 --> 00:07:39,480
rasti Mike Smith telefonų knygoje.

153
00:07:39,480 --> 00:07:40,980
Pjauname problemą per pusę.

154
00:07:40,980 --> 00:07:43,580
Ir taip n gauna didesni
ir didesni ir larger--

155
00:07:43,580 --> 00:07:47,290
Tiesą sakant, kiekvieną kartą jums dvigubai
n, tai trunka tik dar vieną žingsnį.

156
00:07:47,290 --> 00:07:49,770
Taigi, kad daug geriau
nei, tarkim, linijinis laikas.

157
00:07:49,770 --> 00:07:53,030
Kuris yra, jei jūs dvigubai n, tai
trunka dvigubai žingsnių skaičių.

158
00:07:53,030 --> 00:07:55,980
Jei trigubai N, ji užima
patrigubės žingsnių skaičių.

159
00:07:55,980 --> 00:07:58,580
Vienas žingsnis vienetui.

160
00:07:58,580 --> 00:08:01,790
>> Tada viskas pasidaro šiek tiek more--
šiek tiek mažiau puikus iš ten.

161
00:08:01,790 --> 00:08:06,622
Turite linijinis ritmišką laiką, kartais
vadinamas žurnalas linijinis laikas arba tiesiog n log n.

162
00:08:06,622 --> 00:08:08,330
Ir mes pavyzdį
algoritmą, kad

163
00:08:08,330 --> 00:08:13,370
eina n log n, kuris yra dar geriau
nei kvadratinė LAIKĄ_ n kvadratu.

164
00:08:13,370 --> 00:08:17,320
Arba daugianario laikas, N du
bet koks skaičius didesnis negu du.

165
00:08:17,320 --> 00:08:20,810
Arba eksponentinis laikas, kuris
net worse-- C n.

166
00:08:20,810 --> 00:08:24,670
Taigi kai pastovus skaičius padidintas iki
iš įvesties dydžio jėga.

167
00:08:24,670 --> 00:08:28,990
Taigi, jei ten 1,000-- jei
duomenų įvedimas yra dydis 1,000,

168
00:08:28,990 --> 00:08:31,310
tai užtruktų C į 1,000th galia.

169
00:08:31,310 --> 00:08:33,559
Tai daug blogiau nei polinomo metu.

170
00:08:33,559 --> 00:08:35,030
>> Faktorinė laikas yra dar blogiau.

171
00:08:35,030 --> 00:08:37,760
Ir iš tiesų, ten tikrai
egzistuoja begalinis laiko algoritmai,

172
00:08:37,760 --> 00:08:43,740
pvz, vadinamasis kvaila sort-- kurio
darbas yra atsitiktinai shuffle masyvą

173
00:08:43,740 --> 00:08:45,490
ir tada patikrinkite,
ar tai rūšiuojamos.

174
00:08:45,490 --> 00:08:47,589
Ir jei taip nėra, atsitiktinai
shuffle masyvo vėl

175
00:08:47,589 --> 00:08:49,130
ir patikrinkite, ar jis rūšiuojami.

176
00:08:49,130 --> 00:08:51,671
Ir kaip jūs galite galbūt imagine--
galite įsivaizduoti situaciją

177
00:08:51,671 --> 00:08:55,200
kur blogiausiu atveju, kad valia
niekada iš tikrųjų pradėti su masyvo.

178
00:08:55,200 --> 00:08:57,150
Tai algoritmas būtų paleisti amžinai.

179
00:08:57,150 --> 00:08:59,349
Ir taip, kad būtų
begalinis laikas algoritmas.

180
00:08:59,349 --> 00:09:01,890
Tikimės, kad jums nebus raštu
bet faktorialas arba begalinis laikas

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

182
00:09:04,510 --> 00:09:09,150
>> Taigi, galime imtis šiek tiek daugiau
betono pažvelgti į kai paprastesnis

183
00:09:09,150 --> 00:09:11,154
skaičiavimo sudėtingumas klasės.

184
00:09:11,154 --> 00:09:13,070
Taigi, mes turime example--
arba du pavyzdžiai here--

185
00:09:13,070 --> 00:09:15,590
pastovaus laiko algoritmai,
kuri visada

186
00:09:15,590 --> 00:09:17,980
viena operacija blogiausiu atveju.

187
00:09:17,980 --> 00:09:20,050
Taigi pirmą example--
turime funkciją

188
00:09:20,050 --> 00:09:23,952
vadinamas 4 už jus, kurie
trunka dydis 1,000 masyvo.

189
00:09:23,952 --> 00:09:25,660
Bet tada matyt
iš tikrųjų nėra surasti

190
00:09:25,660 --> 00:09:29,000
ne it-- tikrai ne rūpintis, kas
viduje ji, tos masyvo.

191
00:09:29,000 --> 00:09:30,820
Visada tik grįžta keturi.

192
00:09:30,820 --> 00:09:32,940
Taigi, tai algoritmas,
Nepaisant to, kad jį

193
00:09:32,940 --> 00:09:35,840
užima 1000 elementus nėra
nieko su jais daryti.

194
00:09:35,840 --> 00:09:36,590
Tiesiog grįžta keturi.

195
00:09:36,590 --> 00:09:38,240
Jis visada vienas žingsnis.

196
00:09:38,240 --> 00:09:41,600
>> Tiesą sakant, pridėti 2 nums-- kuris
mes matėme prieš pat well--

197
00:09:41,600 --> 00:09:43,680
tik perdirba du sveikieji skaičiai.

198
00:09:43,680 --> 00:09:44,692
Tai ne vienas žingsnis.

199
00:09:44,692 --> 00:09:45,900
Tai tikrai pora žingsnių.

200
00:09:45,900 --> 00:09:50,780
Gauni, gausite B, pridėsite juos
kartu, ir jūs išvesties rezultatus.

201
00:09:50,780 --> 00:09:53,270
Taigi, tai 84 žingsnių.

202
00:09:53,270 --> 00:09:55,510
Bet ji visada pastovus,
nepriklausomai nuo to, A arba B.

203
00:09:55,510 --> 00:09:59,240
Turite gauti, gauti B, įlašinama
juos kartu, išvesties rezultatas.

204
00:09:59,240 --> 00:10:02,900
Taigi, kad pastovus laikas algoritmas.

205
00:10:02,900 --> 00:10:05,170
>> Štai Kurių pavyzdys
linijinis laikas algorithm--

206
00:10:05,170 --> 00:10:08,740
algoritmas, kuris gets--, kad mano
vienas papildomas etapas, galbūt,

207
00:10:08,740 --> 00:10:10,740
kaip jūsų indėlis auga 1 d.

208
00:10:10,740 --> 00:10:14,190
Taigi, tarkime, mes ieškome
numeris 5 viduje masyvą.

209
00:10:14,190 --> 00:10:16,774
Jūs galite turėti padėtį, kai
Jūs galite rasti jį gana anksti.

210
00:10:16,774 --> 00:10:18,606
Bet jūs taip pat gali turėti
situacija, kai ją

211
00:10:18,606 --> 00:10:20,450
gali būti paskutinis elementas masyvo.

212
00:10:20,450 --> 00:10:23,780
Be dydžio 5 masyvas, jei
mes ieškome skaičius 5.

213
00:10:23,780 --> 00:10:25,930
Tai būtų 5 žingsnius.

214
00:10:25,930 --> 00:10:29,180
Ir iš tiesų, įsivaizduokite, kad ten
ne 5 bet šiame masyve.

215
00:10:29,180 --> 00:10:32,820
Mes vis dar realiai pažvelgti į
kiekvienas elementas masyve

216
00:10:32,820 --> 00:10:35,550
siekiant nustatyti,
ar 5 yra.

217
00:10:35,550 --> 00:10:39,840
>> Taigi blogiausiu atveju, kuri yra tai, kad
elementas yra paskutinis masyvo

218
00:10:39,840 --> 00:10:41,700
arba neegzistuoja ne visiems.

219
00:10:41,700 --> 00:10:44,690
Mes vis dar turime pažvelgti į
visi n elementų.

220
00:10:44,690 --> 00:10:47,120
Ir todėl šis algoritmas
veikia linijinio laiko.

221
00:10:47,120 --> 00:10:50,340
Jūs galite patvirtinti, kad
ekstrapoliuojant truputį, sakydamas,

222
00:10:50,340 --> 00:10:53,080
jei mes turėjome 6 elementų masyvą ir
Mes ieškojome skaičiumi 5,

223
00:10:53,080 --> 00:10:54,890
tai gali užtrukti 6 žingsnius.

224
00:10:54,890 --> 00:10:57,620
Jei mes turime 7-elementų masyvas ir
mes ieškome skaičius 5.

225
00:10:57,620 --> 00:10:59,160
Tai gali užtrukti 7 veiksmus.

226
00:10:59,160 --> 00:11:02,920
Kaip mes pridėti dar vieną elementą į mūsų
masyvas, ji užima dar vieną žingsnį.

227
00:11:02,920 --> 00:11:06,750
Štai linijinis algoritmas
blogiausiu atveju-.

228
00:11:06,750 --> 00:11:08,270
>> Pora greitai klausimai jums.

229
00:11:08,270 --> 00:11:11,170
Koks runtime-- kas
blogiausiu atveju Runtime

230
00:11:11,170 --> 00:11:13,700
būtent šio kodo fragmentą?

231
00:11:13,700 --> 00:11:17,420
Taigi turiu 4 kilpa čia, kad veikia
iš j yra lygus 0, visą kelią iki m.

232
00:11:17,420 --> 00:11:21,980
Ir ką aš matau čia yra tas, kad
kūno kilpos veikia pastoviu laiku.

233
00:11:21,980 --> 00:11:24,730
Taigi, naudojant terminologijos,
mes jau kalbėjome about-- ką

234
00:11:24,730 --> 00:11:29,390
būtų pats blogiausias atvejis
Trukmė šio algoritmo?

235
00:11:29,390 --> 00:11:31,050
Paimkite sekundę.

236
00:11:31,050 --> 00:11:34,270
Vidinis dalis kilpą
veikia nuolat laiko.

237
00:11:34,270 --> 00:11:37,510
Ir išorinė dalis iš
kilpa ketina paleisti m kartus.

238
00:11:37,510 --> 00:11:40,260
Taigi, kas yra blogiausio atvejo Runtime čia?

239
00:11:40,260 --> 00:11:43,210
Ar galite atspėti, BIG-O m?

240
00:11:43,210 --> 00:11:44,686
Jūs norite būti teisus.

241
00:11:44,686 --> 00:11:46,230
>> Kaip apie vienas kitą?

242
00:11:46,230 --> 00:11:48,590
Šį kartą mes turime
kilpa viduje kilpa.

243
00:11:48,590 --> 00:11:50,905
Mes turime išorinį kontūrą
, kuri veikia nuo nulio iki p.

244
00:11:50,905 --> 00:11:54,630
Ir mes turime vidinį kontūrą, kuris veikia
nuo nulio iki p, ir viduje, kad,

245
00:11:54,630 --> 00:11:57,890
Aš pareiškiu, kad įstaiga
kilpa veikia nuolat laiko.

246
00:11:57,890 --> 00:12:02,330
Taigi, kas yra blogiausio atvejo Runtime
būtent šio kodo fragmentą?

247
00:12:02,330 --> 00:12:06,140
Na, vėlgi, mes turime
išorinis kontūras, kuris veikia p kartus.

248
00:12:06,140 --> 00:12:09,660
Ir kiekvienas LAIKĄ_ iteracijos
tos kilpos, o.

249
00:12:09,660 --> 00:12:13,170
Mes turime vidinį kontūrą
kad taip pat veikia p kartus.

250
00:12:13,170 --> 00:12:16,900
Ir tada viduje, kad ten-aisiais
pastovus LAIKĄ_ mažai fragmentą ten.

251
00:12:16,900 --> 00:12:19,890
>> Taigi, jei mes turime išorinis kontūras, kad
veikia p kartus viduje, kuri yra

252
00:12:19,890 --> 00:12:22,880
vidinis kilpa, kad
veikia p times-- kas

253
00:12:22,880 --> 00:12:26,480
blogiausiu atveju Runtime
Šio kodo fragmentą?

254
00:12:26,480 --> 00:12:30,730
Ar galite atspėti, didelis O p kvadrato?

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

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

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