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

2
00:00:05,830 --> 00:00:07,910
>> Dobře, takže, výpočetní složitost.

3
00:00:07,910 --> 00:00:10,430
Jen trochu varování
Než se ponoříme příliš far--

4
00:00:10,430 --> 00:00:13,070
to bude pravděpodobně mezi
nejvíce Math-heavy věci

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

6
00:00:14,200 --> 00:00:16,950
Doufejme, že to nebude příliš ohromující
a my se pokusíme a průvodce vás

7
00:00:16,950 --> 00:00:19,200
prostřednictvím procesu, ale
jen trochu varovat.

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

9
00:00:21,282 --> 00:00:23,990
Dobře, tak, abyste mohli provést
využití našich výpočetních zdrojů

10
00:00:23,990 --> 00:00:28,170
v reálném world-- je to opravdu
důležité pochopit, algoritmy

11
00:00:28,170 --> 00:00:30,750
a jak se zpracovávají data.

12
00:00:30,750 --> 00:00:32,810
Máme-li opravdu
efektivní algoritmus, máme

13
00:00:32,810 --> 00:00:36,292
může minimalizovat množství zdrojů
máme k dispozici, aby se s tím vyrovnat.

14
00:00:36,292 --> 00:00:38,750
Máme-li algoritmus, který
bude trvat hodně práce

15
00:00:38,750 --> 00:00:41,210
zpracovat opravdu
velký soubor dat, je to

16
00:00:41,210 --> 00:00:44,030
bude vyžadovat více
a další zdroje, které

17
00:00:44,030 --> 00:00:47,980
jsou peníze, RAM, vše, co druh věcí.

18
00:00:47,980 --> 00:00:52,090
>> Takže, je schopen analyzovat
algoritmus pomocí tohoto sada nástrojů,

19
00:00:52,090 --> 00:00:56,110
v podstatě žádá question--
jak se tento algoritmus měřítko

20
00:00:56,110 --> 00:00:59,020
jak jsme hodit více a více dat na to?

21
00:00:59,020 --> 00:01:02,220
V CS50, množství dat jsme
práce s je docela malý.

22
00:01:02,220 --> 00:01:05,140
Obecně platí, že naše programy jdou
spustit v druhé nebo less--

23
00:01:05,140 --> 00:01:07,830
pravděpodobně mnohem méně
zejména brzy.

24
00:01:07,830 --> 00:01:12,250
>> Ale přemýšlet o firmě, která se zabývá
se stovkami milionů zákazníků.

25
00:01:12,250 --> 00:01:14,970
A oni potřebují zpracovat
že údaje o zákaznících.

26
00:01:14,970 --> 00:01:18,260
Jak se počet zákazníků, které
mají dostane větší a větší,

27
00:01:18,260 --> 00:01:21,230
že to bude vyžadovat
více a více prostředků.

28
00:01:21,230 --> 00:01:22,926
Kolik dalších zdrojů?

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

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

31
00:01:28,097 --> 00:01:31,180
Když mluvíme o složitosti
algorithm-- které někdy budete

32
00:01:31,180 --> 00:01:34,040
slyšet jen čas
složitost nebo prostor složitost

33
00:01:34,040 --> 00:01:36,190
ale my jsme jen tak
volat complexity--

34
00:01:36,190 --> 00:01:38,770
my obecně mluví o
nejhorší scénář.

35
00:01:38,770 --> 00:01:42,640
Vzhledem k tomu, absolutně nejhorší hromada
údaje, které bychom mohli házet na to,

36
00:01:42,640 --> 00:01:46,440
jak se tento algoritmus bude
zpracovávají nebo vypořádat s těmito daty?

37
00:01:46,440 --> 00:01:51,450
Obecně Říkáme nejhorším případě
runtime algoritmu big-O.

38
00:01:51,450 --> 00:01:56,770
Takže algoritmus může být řekl, aby
spustit v O. N nebo O n na druhou.

39
00:01:56,770 --> 00:01:59,110
A více o tom, co
ty, které znamenají v druhém.

40
00:01:59,110 --> 00:02:01,620
>> Někdy, když děláme péči
o nejlepším případě.

41
00:02:01,620 --> 00:02:05,400
Pokud data je vše, co jsme chtěli
aby to bylo a bylo to naprosto perfektní

42
00:02:05,400 --> 00:02:09,630
a my jsme byli posílání to perfektní
sada dat prostřednictvím našeho algoritmu.

43
00:02:09,630 --> 00:02:11,470
Jak by se to zvládnout v této situaci?

44
00:02:11,470 --> 00:02:15,050
Někdy jsme odkazují na, že když
big-Omega, takže na rozdíl od velkých-O,

45
00:02:15,050 --> 00:02:16,530
máme velkou-Omega.

46
00:02:16,530 --> 00:02:18,880
Big-Omega pro nejlepší možný scénář.

47
00:02:18,880 --> 00:02:21,319
Big-O pro nejhorší možný scénář.

48
00:02:21,319 --> 00:02:23,860
Obecně platí, že když hovoříme o
složitost algoritmu,

49
00:02:23,860 --> 00:02:26,370
mluvíme o
nejhorší scénář.

50
00:02:26,370 --> 00:02:28,100
Takže mějte na paměti, že.

51
00:02:28,100 --> 00:02:31,510
>> A v této třídě, budeme obecně děje
opustit hloubkové analýzy stranou.

52
00:02:31,510 --> 00:02:35,350
Tam jsou vědy a pole
věnován tento druh věcí.

53
00:02:35,350 --> 00:02:37,610
Když mluvíme o zdůvodnění
pomocí algoritmů,

54
00:02:37,610 --> 00:02:41,822
což uděláme kus od kusu pro mnoho
algoritmy hovoříme o ve třídě.

55
00:02:41,822 --> 00:02:44,780
Jsme opravdu jen mluví o
úvaha přes to se zdravým rozumem,

56
00:02:44,780 --> 00:02:47,070
ne s formulí, nebo důkazy,
nebo něco takového.

57
00:02:47,070 --> 00:02:51,600
Takže se nemusíte bát, Nebudeme
soustružení do velkého matiku.

58
00:02:51,600 --> 00:02:55,920
>> Tak jsem řekl: staráme se o složitosti
protože klade otázku, jak

59
00:02:55,920 --> 00:03:00,160
se naše algoritmy zpracovávat větší a
větší soubory údajů byl hozen na ně.

60
00:03:00,160 --> 00:03:01,960
No, a co je soubor dat?

61
00:03:01,960 --> 00:03:03,910
Co mám na mysli, když jsem řekl, že?

62
00:03:03,910 --> 00:03:07,600
To znamená, že bez ohledu je dosaženo maximálního
smysl v souvislostech, abych byl upřímný.

63
00:03:07,600 --> 00:03:11,160
Máme-li algoritmus, na
Procesy Strings-- jsme nejspíš

64
00:03:11,160 --> 00:03:13,440
mluví o velikosti řetězce.

65
00:03:13,440 --> 00:03:15,190
To jsou údaje set--
velikost, počet

66
00:03:15,190 --> 00:03:17,050
znaků, které tvoří řetězec.

67
00:03:17,050 --> 00:03:20,090
Když už se bavíme o
algoritmus, který zpracovává soubory,

68
00:03:20,090 --> 00:03:23,930
můžeme mluvit o tom, jak
mnoho kilobajtů obsahují tento soubor.

69
00:03:23,930 --> 00:03:25,710
A to je soubor dat.

70
00:03:25,710 --> 00:03:28,870
Když už se bavíme o algoritmu
, který zpracovává pole obecněji

71
00:03:28,870 --> 00:03:31,510
jako je třídění algoritmy
nebo vyhledávání algoritmy,

72
00:03:31,510 --> 00:03:36,690
budeme pravděpodobně mluvíme o počtu
prvků, které tvoří pole.

73
00:03:36,690 --> 00:03:39,272
>> Nyní můžeme změřit
algorithm-- zejména

74
00:03:39,272 --> 00:03:40,980
když říkám, že můžeme
měřit algoritmus, já

75
00:03:40,980 --> 00:03:43,840
znamenat můžeme měřit, jak
mnoho zdrojů, to zabírá.

76
00:03:43,840 --> 00:03:48,990
Ať už jsou tyto zdroje, kolik
bajtů RAM-- nebo megabajtů paměti RAM

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

78
00:03:49,790 --> 00:03:52,320
Nebo jak dlouho to trvá spustit.

79
00:03:52,320 --> 00:03:56,200
A můžeme volat toto
změřit, svévolně, f n.

80
00:03:56,200 --> 00:03:59,420
Kde n je počet
Prvky v sadě dat.

81
00:03:59,420 --> 00:04:02,640
A f n je, kolik něco přes.

82
00:04:02,640 --> 00:04:07,530
Kolik jednotek zdrojů dělá
vyžadovat zpracování těchto dat.

83
00:04:07,530 --> 00:04:10,030
>> Nyní jsme ve skutečnosti nezajímá
o tom, co f n je přesně.

84
00:04:10,030 --> 00:04:13,700
Ve skutečnosti jsme velmi zřídka will--
Rozhodně se nikdy v tomto class-- I

85
00:04:13,700 --> 00:04:18,709
Ponořte se do žádné opravdu hluboké
analýza toho, co f o n je.

86
00:04:18,709 --> 00:04:23,510
Jsme prostě mluvit o tom, co f
n je přibližně nebo co má tendenci.

87
00:04:23,510 --> 00:04:27,600
A tendence algoritmu je
diktoval jeho nejvyššího řádu termínu.

88
00:04:27,600 --> 00:04:29,440
A my můžeme vidět, co mám
na mysli, že tím, že

89
00:04:29,440 --> 00:04:31,910
Podívejte se na více konkrétní příklad.

90
00:04:31,910 --> 00:04:34,620
>> Takže řekněme, že máme
tři různé algoritmy.

91
00:04:34,620 --> 00:04:39,350
První z nich je uvedeno n
cubed, některé jednotky zdrojů

92
00:04:39,350 --> 00:04:42,880
pro zpracování dat sadu velikosti n.

93
00:04:42,880 --> 00:04:47,000
Máme druhý algoritmu, který bere
n kostičky a n čtvereční zdroje

94
00:04:47,000 --> 00:04:49,350
pro zpracování dat sadu velikosti n.

95
00:04:49,350 --> 00:04:52,030
A máme třetina
algoritmus, který běží in-- že

96
00:04:52,030 --> 00:04:58,300
zabírá n kostičky minus 8N na druhou
plus 20 n jednotek zdrojů

97
00:04:58,300 --> 00:05:02,370
zpracovat algoritmus
s údaji uvedenými velikosti n.

98
00:05:02,370 --> 00:05:05,594
>> Teď znovu, opravdu nebudeme
se dostat do této úrovni detailu.

99
00:05:05,594 --> 00:05:08,260
Jsem opravdu se jen těchto nahoru
zde jako ilustraci bodu

100
00:05:08,260 --> 00:05:10,176
že já budu
což v druhém, který

101
00:05:10,176 --> 00:05:12,980
je, že jsme jen opravdu záleží
o tendenci věcí

102
00:05:12,980 --> 00:05:14,870
jako datové soubory získat větší.

103
00:05:14,870 --> 00:05:18,220
Takže v případě, že datová sada je malý, je tu
vlastně docela velký rozdíl

104
00:05:18,220 --> 00:05:19,870
V těchto algoritmů.

105
00:05:19,870 --> 00:05:23,000
Třetí algoritmus tam
trvá 13 krát déle,

106
00:05:23,000 --> 00:05:27,980
13 krát množství zdrojů
běžet ve vztahu k první.

107
00:05:27,980 --> 00:05:31,659
>> Pokud se náš soubor dat je velikost 10, který
je větší, ale ne nutně velké,

108
00:05:31,659 --> 00:05:33,950
můžeme vidět, že je tu
vlastně trochu rozdíl.

109
00:05:33,950 --> 00:05:36,620
Třetí algoritmus
se stává účinnější.

110
00:05:36,620 --> 00:05:40,120
Je to o vlastně o 40% -
nebo 60% efektivnější.

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

112
00:05:41,580 --> 00:05:45,250
To může run-- to může trvat
400 jednotek zdrojů

113
00:05:45,250 --> 00:05:47,570
pro zpracování dat sadu velikosti 10.

114
00:05:47,570 --> 00:05:49,410
Zatímco první
algoritmus, naopak

115
00:05:49,410 --> 00:05:54,520
bere 1.000 jednotek zdrojů
pro zpracování dat sadu velikosti 10.

116
00:05:54,520 --> 00:05:57,240
Ale podívejte se, co se děje, když
náš počet se ještě větší.

117
00:05:57,240 --> 00:05:59,500
>> Nyní je rozdíl
Mezi tyto algoritmy

118
00:05:59,500 --> 00:06:01,420
začnou být o něco méně patrné.

119
00:06:01,420 --> 00:06:04,560
A skutečnost, že existují
nižší-objednávat terms-- nebo spíše,

120
00:06:04,560 --> 00:06:09,390
termíny s nižším exponents--
začnou být irelevantní.

121
00:06:09,390 --> 00:06:12,290
Pokud je soubor dat o velikosti
1000 a první algoritmus

122
00:06:12,290 --> 00:06:14,170
probíhá v miliardy krocích.

123
00:06:14,170 --> 00:06:17,880
A druhý algoritmus běží v
miliarda a milion kroků.

124
00:06:17,880 --> 00:06:20,870
A třetí algoritmus běží
V těsně před miliardy kroků.

125
00:06:20,870 --> 00:06:22,620
Je to docela hodně miliardu kroků.

126
00:06:22,620 --> 00:06:25,640
Ti méně náročné podmínky spuštění
aby se stal opravdu irelevantní.

127
00:06:25,640 --> 00:06:27,390
A jen proto, aby opravdu
kladivo domů point--

128
00:06:27,390 --> 00:06:31,240
v případě, že vstupní data je velikost A
million-- všichni tři z nich docela hodně

129
00:06:31,240 --> 00:06:34,960
mít jednu quintillion-- if
moje matematika je correct-- kroky

130
00:06:34,960 --> 00:06:37,260
zpracovat vstup dat
velikosti milionu.

131
00:06:37,260 --> 00:06:38,250
To je hodně schodů.

132
00:06:38,250 --> 00:06:42,092
A skutečnost, že jeden z nich by mohl
trvat několik 100.000, nebo pár 100

133
00:06:42,092 --> 00:06:44,650
milionů, i když méně
mluvíme o počtu

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

135
00:06:46,990 --> 00:06:50,006
Ti všichni mají tendenci brát
přibližně n kostičky,

136
00:06:50,006 --> 00:06:52,380
a tak bychom vlastně odkazovat
pro všechny z těchto algoritmů

137
00:06:52,380 --> 00:06:59,520
jako na pořadí n
krychlový nebo big-O n krychlový.

138
00:06:59,520 --> 00:07:03,220
>> Zde je seznam některých z více
společné výpočetní třídy složitosti

139
00:07:03,220 --> 00:07:05,820
že se kterými se setkáte v
algoritmy, obecně.

140
00:07:05,820 --> 00:07:07,970
A také konkrétně v CS50.

141
00:07:07,970 --> 00:07:11,410
Tito jsou organizováni od
obecně nejrychlejší v horní části,

142
00:07:11,410 --> 00:07:13,940
obecně nejpomalejší v dolní části.

143
00:07:13,940 --> 00:07:16,920
Takže konstantním čase algoritmy mají tendenci
být nejrychlejší, bez ohledu

144
00:07:16,920 --> 00:07:19,110
o velikosti
Vstupní data předáte.

145
00:07:19,110 --> 00:07:23,760
Oni vždy jednu operaci, nebo
jedna jednotka zdrojů řešit.

146
00:07:23,760 --> 00:07:25,730
To by mohlo být 2, by to mohlo
být 3, může to být 4.

147
00:07:25,730 --> 00:07:26,910
Ale to je konstantní číslo.

148
00:07:26,910 --> 00:07:28,400
To se nemění.

149
00:07:28,400 --> 00:07:31,390
>> Logaritmické algoritmy času
jsou o něco lepší.

150
00:07:31,390 --> 00:07:33,950
A opravdu dobrý příklad
logaritmickou algoritmus

151
00:07:33,950 --> 00:07:37,420
jste jistě viděli už je
odtržení telefonního seznamu

152
00:07:37,420 --> 00:07:39,480
najít Mike Smith v telefonním seznamu.

153
00:07:39,480 --> 00:07:40,980
Řežeme problém na polovinu.

154
00:07:40,980 --> 00:07:43,580
A tak jak n se zvětší
a větší a larger--

155
00:07:43,580 --> 00:07:47,290
Ve skutečnosti, pokaždé, když se zdvojnásobí
n, jen to trvá ještě jeden krok.

156
00:07:47,290 --> 00:07:49,770
Tak to je mnohem lepší,
než, řekněme, lineární čas.

157
00:07:49,770 --> 00:07:53,030
Což je, pokud zdvojnásobit n, to
bere dvojnásobný počet kroků.

158
00:07:53,030 --> 00:07:55,980
Pokud ztrojnásobit n, trvá
ztrojnásobit počet kroků.

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

160
00:07:58,580 --> 00:08:01,790
>> Pak se věci trochu more--
trochu méně skvělé odtamtud.

161
00:08:01,790 --> 00:08:06,622
Máš lineární rytmické čas, někdy
volal log lineární čas, nebo jen n log n.

162
00:08:06,622 --> 00:08:08,330
A Budeme příklad
of algoritmus, který

163
00:08:08,330 --> 00:08:13,370
probíhá v n log n, což je ještě lepší
než kvadratická time-- n na druhou.

164
00:08:13,370 --> 00:08:17,320
Nebo polynom čas, n dvou
libovolné číslo větší než dvě.

165
00:08:17,320 --> 00:08:20,810
Nebo exponenciální čas, který
je dokonce worse-- C až n.

166
00:08:20,810 --> 00:08:24,670
Takže nějaká konstanta číslo zvýší na
síla velikost vstupu.

167
00:08:24,670 --> 00:08:28,990
Takže jestli je 1,000-- když signál
Vstupní data o velikosti 1000,

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

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

170
00:08:33,559 --> 00:08:35,030
>> Faktoriál čas je ještě horší.

171
00:08:35,030 --> 00:08:37,760
A ve skutečnosti, tam opravdu
Existují nekonečného času algoritmy,

172
00:08:37,760 --> 00:08:43,740
jako je například tzv hloupý sort-- jejichž
úkolem je náhodně zamíchat pole

173
00:08:43,740 --> 00:08:45,490
a pak zkontrolovat,
ať už je to třídit.

174
00:08:45,490 --> 00:08:47,589
A pokud to není, náhodně
Znovu zamíchejte pole

175
00:08:47,589 --> 00:08:49,130
a zkontrolujte, zda je to třídit.

176
00:08:49,130 --> 00:08:51,671
A jak můžete pravděpodobně imagine--
můžete si představit situaci,

177
00:08:51,671 --> 00:08:55,200
kde se v nejhorším případě, že bude
vlastně nikdy začít s pole.

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

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

180
00:08:59,349 --> 00:09:01,890
Doufejme, že nebudete psát
jakýkoli faktoriál nebo 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, pojďme se trochu více
beton podívat na některé jednodušší

183
00:09:09,150 --> 00:09:11,154
výpočetní složitost třídy.

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

185
00:09:13,070 --> 00:09:15,590
konstantních časových algoritmů,
který vždy brát

186
00:09:15,590 --> 00:09:17,980
jedna operace v nejhorším případě.

187
00:09:17,980 --> 00:09:20,050
Takže první example--
my máme funkci

188
00:09:20,050 --> 00:09:23,952
volal 4 pro vás, který
bere pole o velikosti 1000.

189
00:09:23,952 --> 00:09:25,660
Ale pak zřejmě
není ve skutečnosti vypadat

190
00:09:25,660 --> 00:09:29,000
na to-- není opravdu jedno, co je
uvnitř ní, z této matice.

191
00:09:29,000 --> 00:09:30,820
Vždy jen vrátí čtyři.

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

193
00:09:32,940 --> 00:09:35,840
trvá 1000 prvky nemusí
dělat něco s nimi.

194
00:09:35,840 --> 00:09:36,590
Jen vrátí čtyři.

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

196
00:09:38,240 --> 00:09:41,600
>> Ve skutečnosti, se přidají 2 nums--, které
jsme neviděli za well--

197
00:09:41,600 --> 00:09:43,680
právě zpracovává dvě celá čísla.

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

199
00:09:44,692 --> 00:09:45,900
Ve skutečnosti je to pár kroků.

200
00:09:45,900 --> 00:09:50,780
Získáte, dostanete b, je přidáte
dohromady, a vy výstupní výsledky.

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

202
00:09:53,270 --> 00:09:55,510
Ale je to vždy konstantní,
ohledu na to, a nebo b.

203
00:09:55,510 --> 00:09:59,240
Musíte se dostat, dostat b, přidejte
je dohromady, výstup výsledek.

204
00:09:59,240 --> 00:10:02,900
Takže to je konstantní algoritmus.

205
00:10:02,900 --> 00:10:05,170
>> Zde je příklad
lineární čas algorithm--

206
00:10:05,170 --> 00:10:08,740
algoritmus, který gets--, který bere
jeden další krok, případně

207
00:10:08,740 --> 00:10:10,740
jako vaše vstupní roste o 1.

208
00:10:10,740 --> 00:10:14,190
Takže, řekněme, že hledáme
počet 5 uvnitř pole.

209
00:10:14,190 --> 00:10:16,774
Možná budete v situaci, kdy
můžete najít to docela brzy.

210
00:10:16,774 --> 00:10:18,606
Ale můžete také mít
situace, kdy ji

211
00:10:18,606 --> 00:10:20,450
může být poslední prvek pole.

212
00:10:20,450 --> 00:10:23,780
V poli o velikosti 5, pokud
hledáme číslo 5.

213
00:10:23,780 --> 00:10:25,930
Chtělo by to 5 kroků.

214
00:10:25,930 --> 00:10:29,180
A ve skutečnosti, představte si, že je tu
Není 5 kdekoli v tomto poli.

215
00:10:29,180 --> 00:10:32,820
Stále ve skutečnosti se podívat na
každý prvek pole

216
00:10:32,820 --> 00:10:35,550
za účelem zjištění,
zda 5 je tam.

217
00:10:35,550 --> 00:10:39,840
>> Takže v nejhorším případě, což je to, že
prvek je poslední v poli

218
00:10:39,840 --> 00:10:41,700
nebo neexistuje vůbec.

219
00:10:41,700 --> 00:10:44,690
Stále se podívat na
všechny z n prvků.

220
00:10:44,690 --> 00:10:47,120
A tak tento algoritmus
běží v lineárním čase.

221
00:10:47,120 --> 00:10:50,340
Můžete potvrdit, že by
extrapolace trochu tím, že říká,

222
00:10:50,340 --> 00:10:53,080
kdybychom měli 6-prvek pole a
jsme hledali na číslo 5,

223
00:10:53,080 --> 00:10:54,890
to může trvat 6 kroků.

224
00:10:54,890 --> 00:10:57,620
Pokud máme 7-prvek pole a
hledáme číslo 5.

225
00:10:57,620 --> 00:10:59,160
To by mohlo trvat 7 kroků.

226
00:10:59,160 --> 00:11:02,920
Jak jsme přidat ještě jeden prvek do našeho
pole, trvá ještě jeden krok.

227
00:11:02,920 --> 00:11:06,750
To je lineární algoritmus
v nejhorším případu.

228
00:11:06,750 --> 00:11:08,270
>> Pár rychlých otázek pro vás.

229
00:11:08,270 --> 00:11:11,170
Co je to, co je runtime--
nejhorší případ runtime

230
00:11:11,170 --> 00:11:13,700
z tohoto konkrétního fragmentu kódu?

231
00:11:13,700 --> 00:11:17,420
Takže mám 4 smyčku zde, který běží
od j rovná 0, celou cestu až do m.

232
00:11:17,420 --> 00:11:21,980
A to, co jsem viděl tady, je to, že
tělo smyčky probíhá v konstantním čase.

233
00:11:21,980 --> 00:11:24,730
Takže používat terminologii
jsme již mluvili, co about--

234
00:11:24,730 --> 00:11:29,390
by byl nejhorší
runtime tohoto algoritmu?

235
00:11:29,390 --> 00:11:31,050
Vezměte chvilku.

236
00:11:31,050 --> 00:11:34,270
Vnitřní část smyčky
běží v konstantním čase.

237
00:11:34,270 --> 00:11:37,510
A vnější část
smyčka bude běžet m-krát.

238
00:11:37,510 --> 00:11:40,260
Takže to, co je tady nejhorší případ runtime?

239
00:11:40,260 --> 00:11:43,210
Věděli jste asi velký-O M?

240
00:11:43,210 --> 00:11:44,686
Vy byste mít pravdu.

241
00:11:44,686 --> 00:11:46,230
>> Jak se asi jiný?

242
00:11:46,230 --> 00:11:48,590
Tentokrát máme
smyčka uvnitř smyčky.

243
00:11:48,590 --> 00:11:50,905
Máme vnější smyčky
která běží od nuly do str.

244
00:11:50,905 --> 00:11:54,630
A máme vnitřní smyčku, která se spouští
od nuly do p, a vnitřní části, které,

245
00:11:54,630 --> 00:11:57,890
Prohlašuji, že orgán pro
smyčka běží v konstantním čase.

246
00:11:57,890 --> 00:12:02,330
Takže co je nejhorší runtime
z tohoto konkrétního fragmentu kódu?

247
00:12:02,330 --> 00:12:06,140
No, zase máme
Vnější smyčka, která se spouští p krát.

248
00:12:06,140 --> 00:12:09,660
A každý time-- iterace
této smyčky, spíše.

249
00:12:09,660 --> 00:12:13,170
Máme vnitřní smyčky
že také běží p krát.

250
00:12:13,170 --> 00:12:16,900
A pak uvnitř to, že je tu
konstantní time-- malý úryvek tam.

251
00:12:16,900 --> 00:12:19,890
>> Takže pokud máme vnější smyčka, která
běží p časy uvnitř které je

252
00:12:19,890 --> 00:12:22,880
vnitřní smyčky, která
běží p times-- to, co je

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

254
00:12:26,480 --> 00:12:30,730
Věděli jste asi velký-O P na druhou?

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

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

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