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

2
00:00:05,830 --> 00:00:07,910
>> Labi, tāpēc, skaitļošanas sarežģītība.

3
00:00:07,910 --> 00:00:10,430
Tikai mazliet brīdinājums
pirms mēs nirt pārāk far--

4
00:00:10,430 --> 00:00:13,070
Tas droši vien būtu starp
Visvairāk math smago lietas

5
00:00:13,070 --> 00:00:14,200
mēs runājam par in CS50.

6
00:00:14,200 --> 00:00:16,950
Cerams, ka tas nebūs pārāk milzīgs
un mēs cenšamies, un palīdzēs jums

7
00:00:16,950 --> 00:00:19,200
izmantojot procesu, bet
tikai mazliet taisnīgu brīdinājuma.

8
00:00:19,200 --> 00:00:21,282
Tur ir mazliet
math iesaistīti šeit.

9
00:00:21,282 --> 00:00:23,990
Labi, tāpēc, lai veiktu
izmantošana mūsu skaitļošanas resursu

10
00:00:23,990 --> 00:00:28,170
reālajā world-- tas ir patiešām
svarīgi saprast algoritmus

11
00:00:28,170 --> 00:00:30,750
un kā tās apstrādā datus.

12
00:00:30,750 --> 00:00:32,810
Ja mums ir patiešām
efektīvs algoritms, mēs

13
00:00:32,810 --> 00:00:36,292
var samazināt resursu apjomu
mums ir pieejami, lai risinātu ar to.

14
00:00:36,292 --> 00:00:38,750
Ja mums ir algoritmu, kas
gatavojas veikt daudz darba

15
00:00:38,750 --> 00:00:41,210
apstrādāt patiešām
liels datu kopums, tas ir

16
00:00:41,210 --> 00:00:44,030
gatavojas pieprasīt vairāk
un vairāk resursu, kas

17
00:00:44,030 --> 00:00:47,980
ir nauda, ​​RAM, viss, kas veida sīkumi.

18
00:00:47,980 --> 00:00:52,090
>> Tātad, to var analizēt
algoritms, izmantojot šo rīku komplektu,

19
00:00:52,090 --> 00:00:56,110
būtībā lūdz question--
Kā tas algoritms skalu

20
00:00:56,110 --> 00:00:59,020
kā mēs mest vairāk un vairāk datu pie tā?

21
00:00:59,020 --> 00:01:02,220
In CS50, datu apjomu, mēs esam
strādājot ar ir diezgan maza.

22
00:01:02,220 --> 00:01:05,140
Parasti mūsu programmas dodas
palaist otrā vai less--

23
00:01:05,140 --> 00:01:07,830
iespējams, daudz mazāk
īpaši sākumā.

24
00:01:07,830 --> 00:01:12,250
>> Bet domāju par uzņēmumu, kas nodarbojas
ar simtiem miljoniem klientu.

25
00:01:12,250 --> 00:01:14,970
Un viņiem ir nepieciešams, lai apstrādātu
ka klientu dati.

26
00:01:14,970 --> 00:01:18,260
Kā uz klientu skaitu tie
ir kļūst lielāka un lielāka,

27
00:01:18,260 --> 00:01:21,230
tas prasīs
vairāk un vairāk resursu.

28
00:01:21,230 --> 00:01:22,926
Cik daudz vairāk resursu?

29
00:01:22,926 --> 00:01:25,050
Nu, tas ir atkarīgs no tā, cik
mēs analizējam algoritmu,

30
00:01:25,050 --> 00:01:28,097
izmantojot instrumentus šajā instrumentu kopumu.

31
00:01:28,097 --> 00:01:31,180
Kad mēs runājam par sarežģīto
algorithm-- kas dažreiz jūs

32
00:01:31,180 --> 00:01:34,040
dzirdēt tekstā laiks
sarežģītība vai telpas sarežģītība

33
00:01:34,040 --> 00:01:36,190
bet mēs esam tikai gatavojas
zvanīt complexity--

34
00:01:36,190 --> 00:01:38,770
mēs parasti runājam par
sliktākais scenārijs.

35
00:01:38,770 --> 00:01:42,640
Ņemot absolūtais sliktākais kaudzi
dati, ka mēs varētu tikt throwing pie tā,

36
00:01:42,640 --> 00:01:46,440
kā tas ir algoritms gatavojas
apstrādāt vai nodarbojas ar šiem datiem?

37
00:01:46,440 --> 00:01:51,450
Mēs parasti saucam par sliktāko
runtime no algoritma big-O.

38
00:01:51,450 --> 00:01:56,770
Tātad algoritms varētu teikt,
ieskriet O N vai O n brusas.

39
00:01:56,770 --> 00:01:59,110
Un vēl par to,
tie nozīmē sekundē.

40
00:01:59,110 --> 00:02:01,620
>> Dažreiz, lai gan, mēs aprūpe
par labāko scenāriju.

41
00:02:01,620 --> 00:02:05,400
Ja dati ir viss, ko mēs vēlējāmies
ka tas ir, un tas bija absolūti perfekta

42
00:02:05,400 --> 00:02:09,630
un mēs bijām nosūtot šo perfekts
datu kopums caur mūsu algoritmu.

43
00:02:09,630 --> 00:02:11,470
Kā tas rīkoties šajā situācijā?

44
00:02:11,470 --> 00:02:15,050
Mēs dažreiz atsaucas uz, ka
big-Omega, tāpēc atšķirībā no big-O,

45
00:02:15,050 --> 00:02:16,530
mums ir liels-Omega.

46
00:02:16,530 --> 00:02:18,880
Big-Omega par labāko scenāriju.

47
00:02:18,880 --> 00:02:21,319
Big-O, lai sliktākajā gadījumā.

48
00:02:21,319 --> 00:02:23,860
Parasti, kad mēs runājam par
sarežģītība algoritmu,

49
00:02:23,860 --> 00:02:26,370
mēs runājam par
sliktāko scenāriju.

50
00:02:26,370 --> 00:02:28,100
Lai saglabātu, ka prātā.

51
00:02:28,100 --> 00:02:31,510
>> Un šajā klasē, mēs parasti dodas
atstāt nopietnu analīzi malā.

52
00:02:31,510 --> 00:02:35,350
Ir zinātnes un lauki
veltīta šāda veida sīkumi.

53
00:02:35,350 --> 00:02:37,610
Kad mēs runājam par argumentācijas
izmantojot algoritmus,

54
00:02:37,610 --> 00:02:41,822
ko mēs darīsim gabalu pa gabalu daudzi
algoritmi mēs runājam par šajā klasē.

55
00:02:41,822 --> 00:02:44,780
Mēs esam tiešām tikai runā par
argumentācija caur to ar veselo saprātu,

56
00:02:44,780 --> 00:02:47,070
ne ar formulām, vai pierādījumus,
vai kaut kā tā.

57
00:02:47,070 --> 00:02:51,600
Tāpēc neuztraucieties, mēs nebūs
pārvēršas lielā matemātikas klasē.

58
00:02:51,600 --> 00:02:55,920
>> Tāpēc es teicu, mēs rūpējamies par sarežģīto
jo tā uzdod jautājumu, cik

59
00:02:55,920 --> 00:03:00,160
Vai mūsu algoritmi rīkoties lielāks un
Lielāki datu kopas izkrišanas pie viņiem.

60
00:03:00,160 --> 00:03:01,960
Nu, kas ir datu kopa?

61
00:03:01,960 --> 00:03:03,910
Ko es domāju, kad es teicu, ka?

62
00:03:03,910 --> 00:03:07,600
Tas nozīmē, kāds padara visvairāk
jēgas kontekstā, lai būtu godīgi.

63
00:03:07,600 --> 00:03:11,160
Ja mums ir algoritms, ar
Procesi Strings-- mēs esam droši

64
00:03:11,160 --> 00:03:13,440
runājot par lielumu virknes.

65
00:03:13,440 --> 00:03:15,190
Tas ir dati set--
lielums, skaits

66
00:03:15,190 --> 00:03:17,050
rakstzīmju kas veido virkni.

67
00:03:17,050 --> 00:03:20,090
Ja mēs runājam par
algoritms, kas apstrādā failus

68
00:03:20,090 --> 00:03:23,930
mēs varētu runāt par to, kā
daudzi kilobaiti veido šo failu.

69
00:03:23,930 --> 00:03:25,710
Un tas ir datu kopa.

70
00:03:25,710 --> 00:03:28,870
Ja mēs runājam par algoritmu
kas strādā bloki vispārīgāk,

71
00:03:28,870 --> 00:03:31,510
piemēram, šķirošanas algoritmi
vai meklē algoritmus,

72
00:03:31,510 --> 00:03:36,690
mēs, iespējams, runājam par numuru
no faktoriem, kas ietilpst masīvu.

73
00:03:36,690 --> 00:03:39,272
>> Tagad mēs varam izmērīt
algorithm-- it īpaši,

74
00:03:39,272 --> 00:03:40,980
kad es saku, ka mēs varam
pasākums algoritmu, es

75
00:03:40,980 --> 00:03:43,840
nozīmē, ka mēs varam izmērīt, cik
daudz resursu, tas aizņem.

76
00:03:43,840 --> 00:03:48,990
Vai šie resursi ir, cik daudz
no RAM-- baiti vai megabaiti RAM

77
00:03:48,990 --> 00:03:49,790
tā izmanto.

78
00:03:49,790 --> 00:03:52,320
Vai, cik daudz laika nepieciešams, lai palaistu.

79
00:03:52,320 --> 00:03:56,200
Un mēs varam zvanīt šis
pasākums, patvaļīgi, f n.

80
00:03:56,200 --> 00:03:59,420
Kur n ir skaitlis no
elementi datu kopas.

81
00:03:59,420 --> 00:04:02,640
Un f n ir, cik daudz somethings.

82
00:04:02,640 --> 00:04:07,530
Cik daudz resursu vienības dara
tā ir nepieciešama, lai apstrādātu šo informāciju.

83
00:04:07,530 --> 00:04:10,030
>> Tagad mēs patiesībā ir vienalga
par to f n ir tieši.

84
00:04:10,030 --> 00:04:13,700
Patiesībā, mēs ļoti reti will--
protams nekad šajā class-- I

85
00:04:13,700 --> 00:04:18,709
nodoties jebkurš tiešām dziļi
analīze par to f n ir.

86
00:04:18,709 --> 00:04:23,510
Mēs esam tikai gatavojas runāt par to, ko no f
n ir aptuveni vai ko tai ir tendence.

87
00:04:23,510 --> 00:04:27,600
Un tendence algoritms ir
diktē savu augstāko pasūtījuma termiņā.

88
00:04:27,600 --> 00:04:29,440
Un mēs varam redzēt, ko es
domāju ar, ka, ņemot

89
00:04:29,440 --> 00:04:31,910
apskatīt daudz konkrētu piemēru.

90
00:04:31,910 --> 00:04:34,620
>> Tātad pieņemsim, ka mums ir
trīs dažādi algoritmi.

91
00:04:34,620 --> 00:04:39,350
Pirmais no tiem aizņem n
kubā, daži resursu vienības

92
00:04:39,350 --> 00:04:42,880
apstrādāt datu kopu lieluma n.

93
00:04:42,880 --> 00:04:47,000
Mums ir otrais algoritmu, kas notiek
n kubā plus n Kvadrātveida resursi

94
00:04:47,000 --> 00:04:49,350
apstrādāt datu kopu lieluma n.

95
00:04:49,350 --> 00:04:52,030
Un mums ir trešā
algoritms, kas darbojas in-- ka

96
00:04:52,030 --> 00:04:58,300
aizņem n kubā mīnus 8N brusas
plus 20 n vienības resursu

97
00:04:58,300 --> 00:05:02,370
apstrādāt algoritmu
ar datiem, kas no lieluma n.

98
00:05:02,370 --> 00:05:05,594
>> Tagad atkal, mēs tiešām neesam gatavojas
nokļūt šajā detalizācijas pakāpē.

99
00:05:05,594 --> 00:05:08,260
Es esmu patiešām vienkārši ir šie up
šeit kā ilustrācija punkta

100
00:05:08,260 --> 00:05:10,176
ka es esmu būs
padarot sekundē, kas

101
00:05:10,176 --> 00:05:12,980
ir tā, ka mēs tikai patiešām rūp
par tendenci lietām

102
00:05:12,980 --> 00:05:14,870
kā datu kopas iegūt lielākas.

103
00:05:14,870 --> 00:05:18,220
Tātad, ja datu kopa ir mazs, tur ir
patiesībā ir diezgan liela atšķirība

104
00:05:18,220 --> 00:05:19,870
Šajās algoritmiem.

105
00:05:19,870 --> 00:05:23,000
Trešais algoritms tur
aizņem 13 reizes ilgāk,

106
00:05:23,000 --> 00:05:27,980
13 reizes resursu apjoms
palaist, salīdzinot ar pirmo.

107
00:05:27,980 --> 00:05:31,659
>> Ja mūsu datu kopa ir izmērs 10, kas
ir lielāks, taču ne vienmēr milzīgs,

108
00:05:31,659 --> 00:05:33,950
mēs varam redzēt, ka tur ir
faktiski mazliet starpību.

109
00:05:33,950 --> 00:05:36,620
Trešais algoritms
kļūst efektīvāka.

110
00:05:36,620 --> 00:05:40,120
Tas ir par faktiski 40% -
jeb 60% efektīvāk.

111
00:05:40,120 --> 00:05:41,580
Tas aizņem 40% laika daudzums.

112
00:05:41,580 --> 00:05:45,250
Tas var run-- tas var aizņemt
400 resursu vienības

113
00:05:45,250 --> 00:05:47,570
apstrādāt datu kopumu izmēru 10.

114
00:05:47,570 --> 00:05:49,410
Tā kā pirmais
algoritmu, gluži pretēji,

115
00:05:49,410 --> 00:05:54,520
aizņem 1000 resursu vienības
apstrādāt datu kopumu izmēru 10.

116
00:05:54,520 --> 00:05:57,240
Bet izskatās, kas notiek, kā
Mūsu numuri iegūtu vēl lielāku.

117
00:05:57,240 --> 00:05:59,500
>> Tagad, atšķirība
starp šiem algoritmiem

118
00:05:59,500 --> 00:06:01,420
sāk kļūt mazliet mazāk acīmredzama.

119
00:06:01,420 --> 00:06:04,560
Un fakts, ka pastāv
zemākas kārtas terms-- vai drīzāk,

120
00:06:04,560 --> 00:06:09,390
noteikumi, ar zemāku exponents--
sāk kļūt nozīmes.

121
00:06:09,390 --> 00:06:12,290
Ja datu kopa ir lielums
1000 un pirmais algoritms

122
00:06:12,290 --> 00:06:14,170
trašu miljarda soļiem.

123
00:06:14,170 --> 00:06:17,880
Un otrs algoritms darbojas
viens miljards un miljons soļi.

124
00:06:17,880 --> 00:06:20,870
Un trešais algoritms darbojas
tikai kautrīgam miljards soļiem.

125
00:06:20,870 --> 00:06:22,620
Tas ir diezgan daudz miljards soļi.

126
00:06:22,620 --> 00:06:25,640
Šie zemākas pakāpes termini sākt
kļūt tiešām nav nozīmes.

127
00:06:25,640 --> 00:06:27,390
Un tikai, lai patiešām
āmurs mājās tajā point--

128
00:06:27,390 --> 00:06:31,240
ja datu ievades ir no A izmēra
million-- visi trīs šie diezgan daudz

129
00:06:31,240 --> 00:06:34,960
veikt vienu quintillion-- ja
mana matemātika ir correct-- soļi

130
00:06:34,960 --> 00:06:37,260
apstrādāt datu ievadi
no to lieluma miljons.

131
00:06:37,260 --> 00:06:38,250
Tas ir daudz soļiem.

132
00:06:38,250 --> 00:06:42,092
Un fakts, ka viens no viņiem varētu
veikt pāris 100000, vai pāris 100

133
00:06:42,092 --> 00:06:44,650
miljoni vēl mazāk, ja
mēs runājam par vairākiem

134
00:06:44,650 --> 00:06:46,990
ka big-- tas ir sava veida nozīmes.

135
00:06:46,990 --> 00:06:50,006
Viņi visi mēdz veikt
aptuveni n kubā,

136
00:06:50,006 --> 00:06:52,380
un tāpēc mēs faktiski atsaukties
uz visiem šiem algoritmiem

137
00:06:52,380 --> 00:06:59,520
kā par n secībā
kubā vai big-O n kubā.

138
00:06:59,520 --> 00:07:03,220
>> Šeit ir saraksts ar dažiem no vairāk
kopēji skaitļošanas sarežģītība nodarbības

139
00:07:03,220 --> 00:07:05,820
ka mēs sastopas
algoritmi, parasti.

140
00:07:05,820 --> 00:07:07,970
Un arī īpaši CS50.

141
00:07:07,970 --> 00:07:11,410
Tie ir pasūtīts no
parasti ātrāk augšpusē,

142
00:07:11,410 --> 00:07:13,940
līdz parasti vislēnākais apakšā.

143
00:07:13,940 --> 00:07:16,920
Tātad nemainīgs laika algoritmi mēdz
būt ātrākais, neskatoties

144
00:07:16,920 --> 00:07:19,110
no no lieluma
datu ievade jums pāriet.

145
00:07:19,110 --> 00:07:23,760
Viņi vienmēr veikt vienu operāciju vai
viena vienība no resursiem, lai risinātu ar.

146
00:07:23,760 --> 00:07:25,730
Tas varētu būt 2, tas varētu
būt 3, tas varētu būt 4.

147
00:07:25,730 --> 00:07:26,910
Bet tas ir konstante.

148
00:07:26,910 --> 00:07:28,400
Tas nemainās.

149
00:07:28,400 --> 00:07:31,390
>> Logaritmiska laika algoritmi
ir nedaudz labāk.

150
00:07:31,390 --> 00:07:33,950
Un ļoti labs piemērs
logaritms laiks algoritms

151
00:07:33,950 --> 00:07:37,420
Jūs esat droši redzējis līdz šim ir
noplēšot no tālruņu kataloga

152
00:07:37,420 --> 00:07:39,480
atrast Mike Smith tālruņu grāmatā.

153
00:07:39,480 --> 00:07:40,980
Mēs samazināt problēmu pusi.

154
00:07:40,980 --> 00:07:43,580
Un tā kā n izpaužas lielāks
un lielāki un larger--

155
00:07:43,580 --> 00:07:47,290
Patiesībā, katru reizi, kad jūs divreiz
n, tas aizņem tikai vēl vienu soli.

156
00:07:47,290 --> 00:07:49,770
Tātad tas ir daudz labāk
nekā, teiksim, lineārais laiks.

157
00:07:49,770 --> 00:07:53,030
Kas ir, ja jūs dubultā n, tas
ņem dubultu skaitu soļus.

158
00:07:53,030 --> 00:07:55,980
Ja jums triple n, tas aizņem
trīskāršot vairākus pasākumus.

159
00:07:55,980 --> 00:07:58,580
Viens solis uz vienu vienību.

160
00:07:58,580 --> 00:08:01,790
>> Tad lietas iegūt nedaudz more--
nedaudz mazāk lieliski no turienes.

161
00:08:01,790 --> 00:08:06,622
Jums ir lineārs ritmisku laiks, dažreiz
sauc log lineārā laika vai vienkārši n log n.

162
00:08:06,622 --> 00:08:08,330
Un mēs piemērs
par algoritmu, kas

163
00:08:08,330 --> 00:08:13,370
Darbojas n log n, kas ir vēl labāk
nekā kvadrāta LAIKU_ n brusas.

164
00:08:13,370 --> 00:08:17,320
Vai polinoma laiks, n divi
jebkurš skaitlis ir lielāks par diviem.

165
00:08:17,320 --> 00:08:20,810
Vai eksponenciālā laiks, kas
ir pat worse-- C līdz n.

166
00:08:20,810 --> 00:08:24,670
Tātad daži konstante skaits jāpalielina līdz
spēks lieluma ievadi.

167
00:08:24,670 --> 00:08:28,990
Tātad, ja tur ir 1,000-- ja
datu ievade ir izmērs 1000,

168
00:08:28,990 --> 00:08:31,310
tas būtu nepieciešams C līdz 1,000th varas.

169
00:08:31,310 --> 00:08:33,559
Tas ir daudz sliktāk, nekā polinomu laika.

170
00:08:33,559 --> 00:08:35,030
>> Faktoriāls laiks ir vēl sliktāk.

171
00:08:35,030 --> 00:08:37,760
Un patiesībā, tur tiešām
pastāv bezgalīgs laika algoritmi,

172
00:08:37,760 --> 00:08:43,740
piemēram, tā saukto stulba sort-- kuru
uzdevums ir nejauši shuffle masīvs

173
00:08:43,740 --> 00:08:45,490
un pēc tam pārbaudiet,
vai tas ir sakārtoti.

174
00:08:45,490 --> 00:08:47,589
Un, ja tas tā nav, nejauši
shuffle masīvs atkal

175
00:08:47,589 --> 00:08:49,130
un pārbaudiet, vai tas ir sakārtoti.

176
00:08:49,130 --> 00:08:51,671
Un kā jūs varat droši imagine--
Jūs varat iedomāties situāciju

177
00:08:51,671 --> 00:08:55,200
kur sliktākajā gadījumā, ka griba
nekad faktiski sākt ar masīvu.

178
00:08:55,200 --> 00:08:57,150
Tas algoritms varētu palaist uz visiem laikiem.

179
00:08:57,150 --> 00:08:59,349
Un lai būtu
bezgalīgs laiks algoritms.

180
00:08:59,349 --> 00:09:01,890
Cerams, ka jums nebūs rakstiski
jebkurš factorial vai bezgalīgs laiks

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

182
00:09:04,510 --> 00:09:09,150
>> Tātad, pieņemsim nedaudz vairāk
betona apskatīt dažus vienkāršāku

183
00:09:09,150 --> 00:09:11,154
skaitļošanas sarežģītība nodarbības.

184
00:09:11,154 --> 00:09:13,070
Tātad mums ir example--
vai divi piemēri here--

185
00:09:13,070 --> 00:09:15,590
pastāvīga laika algoritmu,
kas vienmēr

186
00:09:15,590 --> 00:09:17,980
viena operācija sliktākajā-lietas.

187
00:09:17,980 --> 00:09:20,050
Tātad pirmajā example--
mums ir funkcija

188
00:09:20,050 --> 00:09:23,952
aicināja 4 jums, kas
aizņem masīva izmēru 1000.

189
00:09:23,952 --> 00:09:25,660
Bet tad acīmredzot
tas tiešām neizskatās

190
00:09:25,660 --> 00:09:29,000
at it-- nav īsti aprūpi, kas ir
iekšpusē tā, šī masīva.

191
00:09:29,000 --> 00:09:30,820
Vienmēr tikai atgriežas četri.

192
00:09:30,820 --> 00:09:32,940
Tātad, ka algoritms,
neskatoties uz to, ka tas

193
00:09:32,940 --> 00:09:35,840
aizņem 1000 elementi nav
darīt kaut ko ar viņiem.

194
00:09:35,840 --> 00:09:36,590
Vienkārši atgriežas četri.

195
00:09:36,590 --> 00:09:38,240
Tas vienmēr ir viens solis.

196
00:09:38,240 --> 00:09:41,600
>> Patiesībā, pievieno 2 nums-- kas
mēs esam redzējuši agrāk kā well--

197
00:09:41,600 --> 00:09:43,680
vienkārši apstrādā divus veselus skaitļus.

198
00:09:43,680 --> 00:09:44,692
Tas nav viens solis.

199
00:09:44,692 --> 00:09:45,900
Tas ir faktiski pāris soļi.

200
00:09:45,900 --> 00:09:50,780
Jūs saņemsiet, jums b, jūs pievienojat tos
kopā, un izvadīt rezultātu.

201
00:09:50,780 --> 00:09:53,270
Tātad, tas ir 84 soļus.

202
00:09:53,270 --> 00:09:55,510
Bet tas vienmēr ir nemainīgs,
neatkarīgi no tā, a vai b.

203
00:09:55,510 --> 00:09:59,240
Jums ir, lai saņemtu, iegūtu B, pievieno
tos kopā, izejas rezultāts.

204
00:09:59,240 --> 00:10:02,900
Tātad tas ir pastāvīgs laiks algoritmu.

205
00:10:02,900 --> 00:10:05,170
>> Lūk piemērs
lineārais laiks algorithm--

206
00:10:05,170 --> 00:10:08,740
algoritms, kas gets-- kas notiek
viens papildu solis, iespējams,

207
00:10:08,740 --> 00:10:10,740
jo jūsu ieguldījums palielinās par 1.

208
00:10:10,740 --> 00:10:14,190
Tātad, pieņemsim, ka mēs meklējam
skaits 5 iekšpusē masīva.

209
00:10:14,190 --> 00:10:16,774
Jums varētu būt situācija, kad
Jūs varat atrast to diezgan agri.

210
00:10:16,774 --> 00:10:18,606
Bet jūs varētu arī būt
situācija, kad to

211
00:10:18,606 --> 00:10:20,450
varētu būt pēdējais elements masīva.

212
00:10:20,450 --> 00:10:23,780
Masīva izmēru 5, ja
mēs meklējam numuru 5.

213
00:10:23,780 --> 00:10:25,930
Tas būtu jāņem 5 soļi.

214
00:10:25,930 --> 00:10:29,180
Un patiesībā, iedomāties, ka tur ir
nevis 5 jebkur šajā masīvā.

215
00:10:29,180 --> 00:10:32,820
Mums vēl tiešām ir jāskatās
katru elementu masīva

216
00:10:32,820 --> 00:10:35,550
lai noteiktu
vai vai nav 5 ir tur.

217
00:10:35,550 --> 00:10:39,840
>> Tātad sliktākajā gadījumā, proti, ka
elements ir pēdējais masīva

218
00:10:39,840 --> 00:10:41,700
vai neeksistē vispār.

219
00:10:41,700 --> 00:10:44,690
Mums vēl ir jāskatās
visi no n elementiem.

220
00:10:44,690 --> 00:10:47,120
Un tā šis algoritms
trašu lineārā laika.

221
00:10:47,120 --> 00:10:50,340
Jūs varat apstiprināt, ka,
ekstrapolējot mazliet, sakot,

222
00:10:50,340 --> 00:10:53,080
ja mums bija 6-elementu masīvu un
mēs meklējām skaitu 5,

223
00:10:53,080 --> 00:10:54,890
tas var aizņemt 6 soļus.

224
00:10:54,890 --> 00:10:57,620
Ja mums ir 7-elementu masīvu un
mēs meklējam numuru 5.

225
00:10:57,620 --> 00:10:59,160
Tas var aizņemt 7 soļi.

226
00:10:59,160 --> 00:11:02,920
Kā mēs pievienot vēl vienu elementu, lai mūsu
masīvs, tas aizņem vēl vienu soli.

227
00:11:02,920 --> 00:11:06,750
Tas ir lineārs algoritms
sliktākajā-lietas.

228
00:11:06,750 --> 00:11:08,270
>> Pāris ātri jautājumi jums.

229
00:11:08,270 --> 00:11:11,170
Kas ir runtime-- kas ir
sliktākajā gadījuma runtime

230
00:11:11,170 --> 00:11:13,700
Šī konkrētā fragmentu kodu?

231
00:11:13,700 --> 00:11:17,420
Tāpēc man ir 4 cilpu šeit, kas darbojas
no j ir vienāds ar 0, visu ceļu līdz pat m.

232
00:11:17,420 --> 00:11:21,980
Un ko es esmu redzēt šeit, ir tas, ka
ķermenis cilpas trašu pastāvīgu laiku.

233
00:11:21,980 --> 00:11:24,730
Tātad, izmantojot terminoloģiju, kas
mēs jau esam runājuši about-- ko

234
00:11:24,730 --> 00:11:29,390
būtu sliktākajā gadījumā
runtime šo algoritmu?

235
00:11:29,390 --> 00:11:31,050
Veikt sekundi.

236
00:11:31,050 --> 00:11:34,270
Iekšējā daļā cilpas
trašu pastāvīgu laiku.

237
00:11:34,270 --> 00:11:37,510
Un ārējā daļa no
cilpa ir gatavojas palaist m reizes.

238
00:11:37,510 --> 00:11:40,260
Tātad, kas ir sliktākais runtime šeit?

239
00:11:40,260 --> 00:11:43,210
Vai jūs uzminēt liels-O m?

240
00:11:43,210 --> 00:11:44,686
Tu būsi taisnība.

241
00:11:44,686 --> 00:11:46,230
>> Kā par otru?

242
00:11:46,230 --> 00:11:48,590
Šoreiz mums ir
cilpa iekšpusē cilpas.

243
00:11:48,590 --> 00:11:50,905
Mums ir ārējo cilpu
kas iet no nulles līdz p.

244
00:11:50,905 --> 00:11:54,630
Un mums ir iekšējais cilpa, kas darbojas
no nulles līdz p, un iekšpusē, kas,

245
00:11:54,630 --> 00:11:57,890
Man jānorāda, ka iestādi par
cilpa trašu pastāvīgu laiku.

246
00:11:57,890 --> 00:12:02,330
Tātad, kas ir sliktākais runtime
Šī konkrētā fragmentu kodu?

247
00:12:02,330 --> 00:12:06,140
Nu, atkal, mums ir
ārējā kontūra, kas darbojas p reizes.

248
00:12:06,140 --> 00:12:09,660
Un katrs LAIKU_ atkārtojuma
Šīs cilpas, drīzāk.

249
00:12:09,660 --> 00:12:13,170
Mums ir iekšējās cilpa
kas arī vada p reizes.

250
00:12:13,170 --> 00:12:16,900
Un tad iekšpusē, ka tur ir
konstante LAIKU_ maz fragments tur.

251
00:12:16,900 --> 00:12:19,890
>> Tātad, ja mums ir ārējā kontūra, kas
iet p reizes iekšpusē, kas ir

252
00:12:19,890 --> 00:12:22,880
iekšējo cilpa, kas
iet p times-- to, kas ir

253
00:12:22,880 --> 00:12:26,480
sliktākajā gadījuma runtime
par šo koda fragmentu?

254
00:12:26,480 --> 00:12:30,730
Vai jūs uzminēt big-O P brusas?

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

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

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