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

2
00:00:05,830 --> 00:00:07,910
>> Dobre, takže, výpočtová zložitosť.

3
00:00:07,910 --> 00:00:10,430
Len trochu varovanie
Než sa ponoríme príliš far--

4
00:00:10,430 --> 00:00:13,070
to bude pravdepodobne medzi
najviac Math-heavy veci

5
00:00:13,070 --> 00:00:14,200
hovoríme o v CS50.

6
00:00:14,200 --> 00:00:16,950
Dúfajme, že to nebude príliš ohromujúce
a my sa pokúsime a sprievodca vás

7
00:00:16,950 --> 00:00:19,200
prostredníctvom procesu, ale
len trochu varovať.

8
00:00:19,200 --> 00:00:21,282
Je tu trochu
matematiky tu jedná.

9
00:00:21,282 --> 00:00:23,990
Dobre, tak, aby ste mohli vykonať
využitia našich výpočtových zdrojov

10
00:00:23,990 --> 00:00:28,170
v reálnom world-- je to naozaj
dôležité pochopiť, algoritmy

11
00:00:28,170 --> 00:00:30,750
a ako sa spracovávajú dáta.

12
00:00:30,750 --> 00:00:32,810
Ak máme naozaj
efektívny algoritmus, máme

13
00:00:32,810 --> 00:00:36,292
môže minimalizovať množstvo zdrojov
máme k dispozícii, aby sa s tým vyrovnať.

14
00:00:36,292 --> 00:00:38,750
Ak máme algoritmus, ktorý
bude trvať veľa práce

15
00:00:38,750 --> 00:00:41,210
spracovať naozaj
veľký súbor dát, je to

16
00:00:41,210 --> 00:00:44,030
bude vyžadovať viac
a ďalšie zdroje, ktoré

17
00:00:44,030 --> 00:00:47,980
sú peniaze, RAM, všetko, čo druh vecí.

18
00:00:47,980 --> 00:00:52,090
>> Takže, je schopný analyzovať
algoritmus pomocou tohto sada nástrojov,

19
00:00:52,090 --> 00:00:56,110
v podstate žiada question--
ako sa tento algoritmus mierka

20
00:00:56,110 --> 00:00:59,020
ako sme hodiť viac a viac dát na to?

21
00:00:59,020 --> 00:01:02,220
V CS50, množstvo dát sme
práca s je celkom malý.

22
00:01:02,220 --> 00:01:05,140
Všeobecne platí, že naše programy idú
spustiť v druhej alebo less--

23
00:01:05,140 --> 00:01:07,830
pravdepodobne oveľa menej
najmä čoskoro.

24
00:01:07,830 --> 00:01:12,250
>> Ale premýšľať o firme, ktorá sa zaoberá
so stovkami miliónov zákazníkov.

25
00:01:12,250 --> 00:01:14,970
A oni potrebujú spracovať
že údaje o zákazníkoch.

26
00:01:14,970 --> 00:01:18,260
Ako sa počet zákazníkov, ktoré
majú dostane väčšie a väčšie,

27
00:01:18,260 --> 00:01:21,230
že to bude vyžadovať
viac a viac prostriedkov.

28
00:01:21,230 --> 00:01:22,926
Koľko ďalších zdrojov?

29
00:01:22,926 --> 00:01:25,050
No, to záleží na tom, ako
analyzujeme algoritmus,

30
00:01:25,050 --> 00:01:28,097
s využitím nástrojov v tomto paneli nástrojov.

31
00:01:28,097 --> 00:01:31,180
Keď hovoríme o zložitosti
algorithm-- ktoré niekedy budete

32
00:01:31,180 --> 00:01:34,040
počuť len čas
zložitosť alebo priestor zložitosť

33
00:01:34,040 --> 00:01:36,190
ale my sme len tak
volať complexity--

34
00:01:36,190 --> 00:01:38,770
my všeobecne hovorí o
najhorší scenár.

35
00:01:38,770 --> 00:01:42,640
Vzhľadom k tomu, absolútne najhoršie hromada
údaje, ktoré by sme mohli hádzať na to,

36
00:01:42,640 --> 00:01:46,440
ako sa tento algoritmus bude
spracovávajú alebo vysporiadať s týmito dátami?

37
00:01:46,440 --> 00:01:51,450
Všeobecne Hovoríme najhoršom prípade
runtime algoritmu big-O.

38
00:01:51,450 --> 00:01:56,770
Takže algoritmus môže byť povedal, aby
spustiť v O. N alebo O n na druhú.

39
00:01:56,770 --> 00:01:59,110
A viac o tom, čo
tie, ktoré znamenajú v druhom.

40
00:01:59,110 --> 00:02:01,620
>> Niekedy, keď robíme starostlivosť
o najlepšom prípade.

41
00:02:01,620 --> 00:02:05,400
Ak dáta je všetko, čo sme chceli
aby to bolo a bolo to úplne perfektný

42
00:02:05,400 --> 00:02:09,630
a my sme boli posielanie to perfektné
sada dát prostredníctvom nášho algoritmu.

43
00:02:09,630 --> 00:02:11,470
Ako by sa to zvládnuť v tejto situácii?

44
00:02:11,470 --> 00:02:15,050
Niekedy sme odkazujú na, že keď
big-Omega, takže na rozdiel od veľkých-O,

45
00:02:15,050 --> 00:02:16,530
máme veľkú-Omega.

46
00:02:16,530 --> 00:02:18,880
Big-Omega pre najlepší možný scenár.

47
00:02:18,880 --> 00:02:21,319
Big-O pre najhorší možný scenár.

48
00:02:21,319 --> 00:02:23,860
Všeobecne platí, že keď hovoríme o
zložitosť algoritmu,

49
00:02:23,860 --> 00:02:26,370
hovoríme o
najhorší scenár.

50
00:02:26,370 --> 00:02:28,100
Takže majte na pamäti, že.

51
00:02:28,100 --> 00:02:31,510
>> A v tejto triede, budeme všeobecne deje
opustiť hĺbkovej analýzy stranou.

52
00:02:31,510 --> 00:02:35,350
Tam sú vedy a polia
venovaný tento druh vecí.

53
00:02:35,350 --> 00:02:37,610
Keď hovoríme o zdôvodnenie
pomocou algoritmov,

54
00:02:37,610 --> 00:02:41,822
čo urobíme kus od kusu pre mnoho
algoritmy hovoríme o v triede.

55
00:02:41,822 --> 00:02:44,780
Sme naozaj len hovorí o
úvaha cez to so zdravým rozumom,

56
00:02:44,780 --> 00:02:47,070
nie s formulou, alebo dôkazy,
alebo niečo také.

57
00:02:47,070 --> 00:02:51,600
Takže sa nemusíte báť, Nebudeme
sústruženie do veľkého matiku.

58
00:02:51,600 --> 00:02:55,920
>> Tak som povedal: staráme sa o zložitosti
pretože kladie otázku, ako

59
00:02:55,920 --> 00:03:00,160
sa naše algoritmy spracovávať väčšie a
väčšie súbory údajov bol hodený na ne.

60
00:03:00,160 --> 00:03:01,960
No, a čo je súbor dát?

61
00:03:01,960 --> 00:03:03,910
Čo mám na mysli, keď som povedal, že?

62
00:03:03,910 --> 00:03:07,600
To znamená, že bez ohľadu je dosiahnuté maximálneho
zmysel v súvislostiach, aby som bol úprimný.

63
00:03:07,600 --> 00:03:11,160
Ak máme algoritmus, na
Procesy Strings-- sme nejspíš

64
00:03:11,160 --> 00:03:13,440
hovorí o veľkosti reťazca.

65
00:03:13,440 --> 00:03:15,190
To sú údaje set--
veľkosť, počet

66
00:03:15,190 --> 00:03:17,050
znakov, ktoré tvoria reťazec.

67
00:03:17,050 --> 00:03:20,090
Keď už sa bavíme o
algoritmus, ktorý spracováva súbory,

68
00:03:20,090 --> 00:03:23,930
môžeme hovoriť o tom, ako
mnoho kilobajtov obsahujú tento súbor.

69
00:03:23,930 --> 00:03:25,710
A to je súbor dát.

70
00:03:25,710 --> 00:03:28,870
Keď už sa bavíme o algoritme
, Ktorý spracováva pole všeobecnejšie

71
00:03:28,870 --> 00:03:31,510
ako je triedenie algoritmy
alebo vyhľadávanie algoritmy,

72
00:03:31,510 --> 00:03:36,690
budeme pravdepodobne hovoríme o počte
prvkov, ktoré tvoria pole.

73
00:03:36,690 --> 00:03:39,272
>> Teraz môžeme zmerať
algorithm-- najmä

74
00:03:39,272 --> 00:03:40,980
keď hovorím, že môžeme
merať algoritmus, ja

75
00:03:40,980 --> 00:03:43,840
znamenať môžeme merať, ako
veľa zdrojov, to zaberá.

76
00:03:43,840 --> 00:03:48,990
Či už sú tieto zdroje, koľko
bajtov RAM-- alebo megabajtov pamäte RAM

77
00:03:48,990 --> 00:03:49,790
používa.

78
00:03:49,790 --> 00:03:52,320
Alebo ako dlho to trvá spustiť.

79
00:03:52,320 --> 00:03:56,200
A môžeme volať toto
zmerať, svojvoľne, f n.

80
00:03:56,200 --> 00:03:59,420
Kde n je počet
Prvky v sade dát.

81
00:03:59,420 --> 00:04:02,640
A f n je, koľko niečo cez.

82
00:04:02,640 --> 00:04:07,530
Koľko jednotiek zdrojov robí
vyžadovať spracovanie týchto dát.

83
00:04:07,530 --> 00:04:10,030
>> Teraz sme v skutočnosti nezaujíma
o tom, čo f n je presne.

84
00:04:10,030 --> 00:04:13,700
V skutočnosti sme veľmi zriedka will--
Rozhodne sa nikdy v tomto class-- I

85
00:04:13,700 --> 00:04:18,709
Ponorte sa do žiadnej naozaj hlbokej
analýza toho, čo f o n je.

86
00:04:18,709 --> 00:04:23,510
Sme jednoducho hovoriť o tom, čo f
n je približne alebo čo má tendenciu.

87
00:04:23,510 --> 00:04:27,600
A tendencia algoritmu je
diktoval jeho najvyššieho rádu termíne.

88
00:04:27,600 --> 00:04:29,440
A my môžeme vidieť, čo mám
na mysli, že tým, že

89
00:04:29,440 --> 00:04:31,910
Pozrite sa na viac konkrétny príklad.

90
00:04:31,910 --> 00:04:34,620
>> Takže povedzme, že máme
tri rôzne algoritmy.

91
00:04:34,620 --> 00:04:39,350
Prvý z nich je uvedené n
Cubed, niektoré jednotky zdrojov

92
00:04:39,350 --> 00:04:42,880
pre spracovanie dát sadu veľkosti n.

93
00:04:42,880 --> 00:04:47,000
Máme druhý algoritmu, ktorý berie
n kocky a n štvorcový zdroje

94
00:04:47,000 --> 00:04:49,350
pre spracovanie dát sadu veľkosti n.

95
00:04:49,350 --> 00:04:52,030
A máme tretina
algoritmus, ktorý beží in-- že

96
00:04:52,030 --> 00:04:58,300
zaberá n kocky mínus 8N na druhú
plus 20 n jednotiek zdrojov

97
00:04:58,300 --> 00:05:02,370
spracovať algoritmus
s údajmi uvedenými veľkosti n.

98
00:05:02,370 --> 00:05:05,594
>> Teraz znovu, naozaj nebudeme
sa dostať do tejto úrovni detailu.

99
00:05:05,594 --> 00:05:08,260
Som naozaj sa len týchto hore
tu ako ilustráciu bodu

100
00:05:08,260 --> 00:05:10,176
že ja budem
čo v druhom, ktorý

101
00:05:10,176 --> 00:05:12,980
je, že sme len naozaj záleží
o tendenciu vecí

102
00:05:12,980 --> 00:05:14,870
ako dátové súbory získať väčšie.

103
00:05:14,870 --> 00:05:18,220
Takže v prípade, že dátová sada je malý, je tu
vlastne celkom veľký rozdiel

104
00:05:18,220 --> 00:05:19,870
V týchto algoritmov.

105
00:05:19,870 --> 00:05:23,000
Tretí algoritmus tam
trvá 13 krát dlhšie,

106
00:05:23,000 --> 00:05:27,980
13 krát množstvo zdrojov
bežať vo vzťahu k prvej.

107
00:05:27,980 --> 00:05:31,659
>> Ak sa náš súbor dát je veľkosť 10, ktorý
je väčší, ale nie nevyhnutne veľké,

108
00:05:31,659 --> 00:05:33,950
môžeme vidieť, že je tu
vlastne trochu rozdiel.

109
00:05:33,950 --> 00:05:36,620
Tretí algoritmus
sa stáva účinnejšia.

110
00:05:36,620 --> 00:05:40,120
Je to o vlastne o 40% -
alebo 60% efektívnejšia.

111
00:05:40,120 --> 00:05:41,580
To trvá 40% množstvo času.

112
00:05:41,580 --> 00:05:45,250
To môže run-- to môže trvať
400 jednotiek zdrojov

113
00:05:45,250 --> 00:05:47,570
pre spracovanie dát sadu veľkosti 10.

114
00:05:47,570 --> 00:05:49,410
Kým prvý
algoritmus, naopak

115
00:05:49,410 --> 00:05:54,520
berie 1.000 jednotiek zdrojov
pre spracovanie dát sadu veľkosti 10.

116
00:05:54,520 --> 00:05:57,240
Ale pozrite sa, čo sa deje, keď
náš počet sa ešte väčší.

117
00:05:57,240 --> 00:05:59,500
>> Teraz je rozdiel
Medzi tieto algoritmy

118
00:05:59,500 --> 00:06:01,420
začnú byť o niečo menej viditeľné.

119
00:06:01,420 --> 00:06:04,560
A skutočnosť, že existujú
nižšia-objednávať terms-- alebo skôr,

120
00:06:04,560 --> 00:06:09,390
termíny s nižším exponents--
začnú byť irelevantné.

121
00:06:09,390 --> 00:06:12,290
Ak je súbor dát o veľkosti
1000 a prvý algoritmus

122
00:06:12,290 --> 00:06:14,170
prebieha v miliardy krokoch.

123
00:06:14,170 --> 00:06:17,880
A druhý algoritmus beží v
miliarda a milión krokov.

124
00:06:17,880 --> 00:06:20,870
A tretí algoritmus beží
V tesne pred miliardy krokov.

125
00:06:20,870 --> 00:06:22,620
Je to celkom veľa miliardu krokov.

126
00:06:22,620 --> 00:06:25,640
Tí menej náročné podmienky spustení
aby sa stal naozaj irelevantné.

127
00:06:25,640 --> 00:06:27,390
A len preto, aby naozaj
kladivo domov point--

128
00:06:27,390 --> 00:06:31,240
v prípade, že vstupné dáta je veľkosť A
million-- všetci traja z nich celkom veľa

129
00:06:31,240 --> 00:06:34,960
mať jednu quintillion-- if
moja matematika je correct-- kroky

130
00:06:34,960 --> 00:06:37,260
spracovať vstup dát
veľkosti milióna.

131
00:06:37,260 --> 00:06:38,250
To je veľa schodov.

132
00:06:38,250 --> 00:06:42,092
A skutočnosť, že jeden z nich by mohol
trvať niekoľko 100.000, alebo pár 100

133
00:06:42,092 --> 00:06:44,650
miliónov, aj keď menej
hovoríme o počte

134
00:06:44,650 --> 00:06:46,990
že big-- je to trochu irelevantné.

135
00:06:46,990 --> 00:06:50,006
Tí všetci majú tendenciu brať
približne n kocky,

136
00:06:50,006 --> 00:06:52,380
a tak by sme vlastne odkazovať
pre všetky z týchto algoritmov

137
00:06:52,380 --> 00:06:59,520
ako na poradie n
kubický alebo big-O n kubický.

138
00:06:59,520 --> 00:07:03,220
>> Tu je zoznam niektorých z viacerých
spoločné výpočtovej triedy zložitosti

139
00:07:03,220 --> 00:07:05,820
že s ktorými sa stretnete v
algoritmy, všeobecne.

140
00:07:05,820 --> 00:07:07,970
A tiež konkrétne v CS50.

141
00:07:07,970 --> 00:07:11,410
Títo sú organizovaní od
všeobecne najrýchlejší v hornej časti,

142
00:07:11,410 --> 00:07:13,940
všeobecne najpomalší v dolnej časti.

143
00:07:13,940 --> 00:07:16,920
Takže konštantnom čase algoritmy majú tendenciu
byť najrýchlejší, bez ohľadu

144
00:07:16,920 --> 00:07:19,110
o veľkosti
Vstupné dáta odovzdáte.

145
00:07:19,110 --> 00:07:23,760
Oni vždy jednu operáciu, alebo
jeden celok zdrojov riešiť.

146
00:07:23,760 --> 00:07:25,730
To by mohlo byť 2, by to mohlo
byť 3, môže to byť 4.

147
00:07:25,730 --> 00:07:26,910
Ale to je konštantná číslo.

148
00:07:26,910 --> 00:07:28,400
To sa nemení.

149
00:07:28,400 --> 00:07:31,390
>> Logaritmickej algoritmy času
sú o niečo lepšie.

150
00:07:31,390 --> 00:07:33,950
A naozaj dobrý príklad
logaritmickou algoritmus

151
00:07:33,950 --> 00:07:37,420
ste iste videli už je
odtrhnutie telefónneho zoznamu

152
00:07:37,420 --> 00:07:39,480
nájsť Mike Smith v telefónnom zozname.

153
00:07:39,480 --> 00:07:40,980
Režeme problém na polovicu.

154
00:07:40,980 --> 00:07:43,580
A tak ako n sa zväčší
a väčšie a larger--

155
00:07:43,580 --> 00:07:47,290
V skutočnosti, zakaždým, keď sa zdvojnásobí
n, len to trvá ešte jeden krok.

156
00:07:47,290 --> 00:07:49,770
Tak to je oveľa lepšie,
než, povedzme, lineárny čas.

157
00:07:49,770 --> 00:07:53,030
Čo je, pokiaľ zdvojnásobiť n, to
berie dvojnásobný počet krokov.

158
00:07:53,030 --> 00:07:55,980
Ak strojnásobiť n, trvá
strojnásobiť počet krokov.

159
00:07:55,980 --> 00:07:58,580
Jeden krok za jednotku.

160
00:07:58,580 --> 00:08:01,790
>> Potom sa veci trochu more--
trochu menej skvelé odtiaľ.

161
00:08:01,790 --> 00:08:06,622
Máš lineárny rytmické čas, niekedy
volal log lineárny čas, alebo len n log n.

162
00:08:06,622 --> 00:08:08,330
A Budeme príklad
of algoritmus, ktorý

163
00:08:08,330 --> 00:08:13,370
prebieha v n log n, čo je ešte lepšie
než kvadratická time-- n na druhú.

164
00:08:13,370 --> 00:08:17,320
Alebo polynóm čas, n dvoch
ľubovoľné číslo väčšie než dve.

165
00:08:17,320 --> 00:08:20,810
Alebo exponenciálny čas, ktorý
je dokonca worse-- C až n.

166
00:08:20,810 --> 00:08:24,670
Takže nejaká konštanta číslo zvýši na
sila veľkosť vstupu.

167
00:08:24,670 --> 00:08:28,990
Takže či je 1,000-- keď signál
Vstupné dáta o veľkosti 1000,

168
00:08:28,990 --> 00:08:31,310
to bude trvať C do 1000. moci.

169
00:08:31,310 --> 00:08:33,559
Je to oveľa horšie, než polynomiálním čase.

170
00:08:33,559 --> 00:08:35,030
>> Faktoriál čas je ešte horšia.

171
00:08:35,030 --> 00:08:37,760
A v skutočnosti, tam naozaj
Existujú nekonečného času algoritmy,

172
00:08:37,760 --> 00:08:43,740
ako je napríklad tzv hlúpy sort-- ktorých
úlohou je náhodne zamiešať pole

173
00:08:43,740 --> 00:08:45,490
a potom skontrolovať,
či už je to triediť.

174
00:08:45,490 --> 00:08:47,589
A ak to nie je, náhodne
Znovu zamiešajte pole

175
00:08:47,589 --> 00:08:49,130
a skontrolujte, či je to triediť.

176
00:08:49,130 --> 00:08:51,671
A ako môžete pravdepodobne imagine--
môžete si predstaviť situáciu,

177
00:08:51,671 --> 00:08:55,200
kde sa v najhoršom prípade, že bude
vlastne nikdy začať s poľa.

178
00:08:55,200 --> 00:08:57,150
To algoritmus pobeží navždy.

179
00:08:57,150 --> 00:08:59,349
A tak to by bolo
nekonečný čas algoritmus.

180
00:08:59,349 --> 00:09:01,890
Dúfajme, že nebudete písať
akýkoľvek faktoriál alebo nekonečný čas

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

182
00:09:04,510 --> 00:09:09,150
>> Takže, poďme sa trochu viac
betón pozrieť na niektoré jednoduchšie

183
00:09:09,150 --> 00:09:11,154
výpočtovej zložitosť triedy.

184
00:09:11,154 --> 00:09:13,070
Takže máme example--
alebo dva príklady here--

185
00:09:13,070 --> 00:09:15,590
konštantných časových algoritmov,
ktorý vždy brať

186
00:09:15,590 --> 00:09:17,980
jedna operácia v najhoršom prípade.

187
00:09:17,980 --> 00:09:20,050
Takže prvý example--
my máme funkciu

188
00:09:20,050 --> 00:09:23,952
volal 4 pre vás, ktorý
berie poľa veľkosti 1000.

189
00:09:23,952 --> 00:09:25,660
Ale potom zrejme
nie je v skutočnosti vyzerať

190
00:09:25,660 --> 00:09:29,000
na to-- nie je naozaj jedno, čo je
vnútri nej, z tejto matice.

191
00:09:29,000 --> 00:09:30,820
Vždy iba vráti štyri.

192
00:09:30,820 --> 00:09:32,940
Tak, že algoritmus,
a to napriek skutočnosti, že

193
00:09:32,940 --> 00:09:35,840
trvá 1000 prvky nemusia
robiť niečo s nimi.

194
00:09:35,840 --> 00:09:36,590
Len vráti štyri.

195
00:09:36,590 --> 00:09:38,240
Je to vždy jeden krok.

196
00:09:38,240 --> 00:09:41,600
>> V skutočnosti, sa pridajú 2 nums--, ktoré
sme nevideli za well--

197
00:09:41,600 --> 00:09:43,680
práve spracováva dve celé čísla.

198
00:09:43,680 --> 00:09:44,692
Nie je to jediný krok.

199
00:09:44,692 --> 00:09:45,900
V skutočnosti je to pár krokov.

200
00:09:45,900 --> 00:09:50,780
Získate, dostanete b, je pridáte
dohromady, a vy výstupné výsledky.

201
00:09:50,780 --> 00:09:53,270
Takže je to 84 krokov.

202
00:09:53,270 --> 00:09:55,510
Ale je to vždy konštantný,
ohľadu na to, a alebo b.

203
00:09:55,510 --> 00:09:59,240
Musíte sa dostať, dostať b, pridajte
je dohromady, výstup výsledok.

204
00:09:59,240 --> 00:10:02,900
Takže to je konštantná algoritmus.

205
00:10:02,900 --> 00:10:05,170
>> Tu je príklad
lineárny čas algorithm--

206
00:10:05,170 --> 00:10:08,740
algoritmus, ktorý gets--, ktorý berie
jeden ďalší krok, prípadne

207
00:10:08,740 --> 00:10:10,740
ako vaše vstupné rastie o 1.

208
00:10:10,740 --> 00:10:14,190
Takže, povedzme, že hľadáme
počet 5 vnútri poľa.

209
00:10:14,190 --> 00:10:16,774
Možno budete v situácii, keď
môžete nájsť to celkom skoro.

210
00:10:16,774 --> 00:10:18,606
Ale môžete tiež mať
situácie, kedy ju

211
00:10:18,606 --> 00:10:20,450
môže byť posledný prvok poľa.

212
00:10:20,450 --> 00:10:23,780
V poli o veľkosti 5, pokiaľ
hľadáme číslo 5.

213
00:10:23,780 --> 00:10:25,930
Chcelo by to 5 krokov.

214
00:10:25,930 --> 00:10:29,180
A v skutočnosti, predstavte si, že je tu
Nie je 5 kdekoľvek v tomto poli.

215
00:10:29,180 --> 00:10:32,820
Stále v skutočnosti sa pozrieť na
každý prvok poľa

216
00:10:32,820 --> 00:10:35,550
za účelom zistenia,
či 5 je tam.

217
00:10:35,550 --> 00:10:39,840
>> Takže v najhoršom prípade, čo je to, že
prvok je posledný v poli

218
00:10:39,840 --> 00:10:41,700
alebo neexistuje vôbec.

219
00:10:41,700 --> 00:10:44,690
Stále sa pozrieť na
všetky z n prvkov.

220
00:10:44,690 --> 00:10:47,120
A tak tento algoritmus
beží v lineárnom čase.

221
00:10:47,120 --> 00:10:50,340
Môžete potvrdiť, že by
extrapolácie trochu tým, že hovorí,

222
00:10:50,340 --> 00:10:53,080
keby sme mali 6-prvok poľa a
sme hľadali na číslo 5,

223
00:10:53,080 --> 00:10:54,890
to môže trvať 6 krokov.

224
00:10:54,890 --> 00:10:57,620
Ak máme 7-prvok poľa a
hľadáme číslo 5.

225
00:10:57,620 --> 00:10:59,160
To by mohlo trvať 7 krokov.

226
00:10:59,160 --> 00:11:02,920
Ako sme pridať ešte jeden prvok do nášho
poľa, trvá ešte jeden krok.

227
00:11:02,920 --> 00:11:06,750
To je lineárny algoritmus
v najhoršom prípade.

228
00:11:06,750 --> 00:11:08,270
>> Pár rýchlych otázok pre vás.

229
00:11:08,270 --> 00:11:11,170
Čo je to, čo je runtime--
najhorší prípad runtime

230
00:11:11,170 --> 00:11:13,700
z tohto konkrétneho fragmentu kódu?

231
00:11:13,700 --> 00:11:17,420
Takže mám 4 slučku tu, ktorý beží
od j rovná 0, celú cestu až do m.

232
00:11:17,420 --> 00:11:21,980
A to, čo som videl tu, je to, že
telo slučky prebieha v konštantnom čase.

233
00:11:21,980 --> 00:11:24,730
Takže používať terminológiu
sme už hovorili, čo about--

234
00:11:24,730 --> 00:11:29,390
by bol najhorší
runtime tohto algoritmu?

235
00:11:29,390 --> 00:11:31,050
Vezmite chvíľku.

236
00:11:31,050 --> 00:11:34,270
Vnútorná časť slučky
beží v konštantnom čase.

237
00:11:34,270 --> 00:11:37,510
A vonkajšiu časť
slučka bude bežať m-krát.

238
00:11:37,510 --> 00:11:40,260
Takže to, čo je tu najhorší prípad runtime?

239
00:11:40,260 --> 00:11:43,210
Vedeli ste asi veľký-O M?

240
00:11:43,210 --> 00:11:44,686
Vy by ste mať pravdu.

241
00:11:44,686 --> 00:11:46,230
>> Ako sa asi iný?

242
00:11:46,230 --> 00:11:48,590
Tentoraz máme
slučka vnútri slučky.

243
00:11:48,590 --> 00:11:50,905
Máme vonkajšej slučky
ktorá beží od nuly do str.

244
00:11:50,905 --> 00:11:54,630
A máme vnútorný slučku, ktorá sa spúšťa
od nuly do p, a vnútorné časti, ktoré,

245
00:11:54,630 --> 00:11:57,890
Vyhlasujem, že orgán pre
slučka beží v konštantnom čase.

246
00:11:57,890 --> 00:12:02,330
Takže čo je najhoršie runtime
z tohto konkrétneho fragmentu kódu?

247
00:12:02,330 --> 00:12:06,140
No, zase máme
Vonkajšie slučka, ktorá sa spúšťa p krát.

248
00:12:06,140 --> 00:12:09,660
A každý time-- iterácie
tejto slučky, skôr.

249
00:12:09,660 --> 00:12:13,170
Máme vnútorný slučky
že tiež beží p krát.

250
00:12:13,170 --> 00:12:16,900
A potom vnútri to, že je tu
konštantný time-- malý úryvok tam.

251
00:12:16,900 --> 00:12:19,890
>> Takže ak máme vonkajšej slučka, ktorá
beží p časy vnútri ktorej je

252
00:12:19,890 --> 00:12:22,880
vnútorné slučky, ktorá
beží p times-- to, čo je

253
00:12:22,880 --> 00:12:26,480
najhorší prípad runtime
tento fragment kódu?

254
00:12:26,480 --> 00:12:30,730
Vedeli ste asi veľký-O P na druhú?

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

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

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