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

2
00:00:05,830 --> 00:00:07,910
>> У реду, тако, рачунарска комплексност.

3
00:00:07,910 --> 00:00:10,430
Само мало упозорење
пре него што зароните превише фар--

4
00:00:10,430 --> 00:00:13,070
ово ће вероватно бити међу
највише матх-тешких ствари

5
00:00:13,070 --> 00:00:14,200
говоримо о у ЦС50.

6
00:00:14,200 --> 00:00:16,950
Надам се да неће бити превише неодољив
а ми ћемо покушати и водити вас

7
00:00:16,950 --> 00:00:19,200
кроз процес, али
само мало фер упозорење.

8
00:00:19,200 --> 00:00:21,282
Има мало
од математике укључени овде.

9
00:00:21,282 --> 00:00:23,990
У реду, тако да би се
коришћење наших ресурса рачунарске

10
00:00:23,990 --> 00:00:28,170
у стварном ворлд-- је стварно
важно разумети алгоритме

11
00:00:28,170 --> 00:00:30,750
и како они обрађују податке.

12
00:00:30,750 --> 00:00:32,810
Ако имамо заиста
ефикасан алгоритам, ми

13
00:00:32,810 --> 00:00:36,292
може да смањи количину ресурса
имамо на располагању да се носи са тим.

14
00:00:36,292 --> 00:00:38,750
Ако имамо алгоритам који
ће потребно много рада

15
00:00:38,750 --> 00:00:41,210
за обраду стварно
велики скуп података, то је

16
00:00:41,210 --> 00:00:44,030
ће захтевати више
и више средстава, која

17
00:00:44,030 --> 00:00:47,980
је новац, РАМ-а, сви такве ствари.

18
00:00:47,980 --> 00:00:52,090
>> Дакле, бити у стању да анализира
алгоритам користећи овај сет алата,

19
00:00:52,090 --> 00:00:56,110
у суштини, пита куестион--
како се овај алгоритам скалу

20
00:00:56,110 --> 00:00:59,020
као што бацају све више и више података на њега?

21
00:00:59,020 --> 00:01:02,220
У ЦС50, количину података смо
рад са је прилично мали.

22
00:01:02,220 --> 00:01:05,140
Генерално, наши програми иду
да ради у други или лесс--

23
00:01:05,140 --> 00:01:07,830
вероватно много мање
посебно рано.

24
00:01:07,830 --> 00:01:12,250
>> Али размислите фирма која се бави
са стотинама милиона купаца.

25
00:01:12,250 --> 00:01:14,970
И они треба да обради
да купац података.

26
00:01:14,970 --> 00:01:18,260
Како се број купаца су
Имам постаје све већа и већа,

27
00:01:18,260 --> 00:01:21,230
то ће захтевати
све више и више ресурса.

28
00:01:21,230 --> 00:01:22,926
Колико још ресурси?

29
00:01:22,926 --> 00:01:25,050
Па, то зависи од тога како
анализирамо алгоритам,

30
00:01:25,050 --> 00:01:28,097
користећи алате у овој кутији за алат.

31
00:01:28,097 --> 00:01:31,180
Када говоримо о сложености
алгоритхм-- који Понекад ћете

32
00:01:31,180 --> 00:01:34,040
Чуо сам да се назива време
Сложеност или простор комплексност

33
00:01:34,040 --> 00:01:36,190
али ми ћемо само
звати цомплекити--

34
00:01:36,190 --> 00:01:38,770
ми углавном говоримо о
најгори сценарио.

35
00:01:38,770 --> 00:01:42,640
С обзиром на апсолутно најгори гомила
подаци које смо могли да бацају на њега,

36
00:01:42,640 --> 00:01:46,440
како је овај алгоритам ће
обрадити или се баве тим подацима?

37
00:01:46,440 --> 00:01:51,450
Ми углавном зову у најгорем случају
Рунтиме алгоритма биг-О.

38
00:01:51,450 --> 00:01:56,770
Дакле, алгоритам може се рећи да
изводити у Ø Н или О од н на квадрат.

39
00:01:56,770 --> 00:01:59,110
И више о томе шта
оне значе у секунди.

40
00:01:59,110 --> 00:02:01,620
>> Понекад, међутим, ми стало
о најбољем сценарију.

41
00:02:01,620 --> 00:02:05,400
Ако су подаци све смо хтели
да буде и било је апсолутно савршен

42
00:02:05,400 --> 00:02:09,630
и ми слали ово савршено
сет података путем нашег алгоритма.

43
00:02:09,630 --> 00:02:11,470
Како би се носити у тој ситуацији?

44
00:02:11,470 --> 00:02:15,050
Понекад се односе на то како
велики омега, тако да је у супротности са великом-О,

45
00:02:15,050 --> 00:02:16,530
имамо велику-Омега.

46
00:02:16,530 --> 00:02:18,880
Биг омега за најбољем сценарију.

47
00:02:18,880 --> 00:02:21,319
Биг О за најгори могући сценарио.

48
00:02:21,319 --> 00:02:23,860
Генерално, када говоримо о
сложеност алгоритма,

49
00:02:23,860 --> 00:02:26,370
говоримо о
најгори сценарио.

50
00:02:26,370 --> 00:02:28,100
Дакле, имајте то на уму.

51
00:02:28,100 --> 00:02:31,510
>> И у овој класи, ми углавном идемо
да оставимо по страни ригорозну анализу.

52
00:02:31,510 --> 00:02:35,350
Постоје науке и поља
посвећен овим стварима.

53
00:02:35,350 --> 00:02:37,610
Када говоримо о резоновања
кроз алгоритама,

54
00:02:37,610 --> 00:02:41,822
што ћемо урадити комад-по-комад за многе
алгоритми говоримо о у класи.

55
00:02:41,822 --> 00:02:44,780
Ми заправо само говори о
образложење кроз њу са здравим разумом,

56
00:02:44,780 --> 00:02:47,070
не са формулама, или доказа,
или нешто слично.

57
00:02:47,070 --> 00:02:51,600
Зато не брини, нећемо бити
претвара у велику цасу математике.

58
00:02:51,600 --> 00:02:55,920
>> Зато сам рекао да је стало сложености
јер се поставља питање, како

59
00:02:55,920 --> 00:03:00,160
наши алгоритми носити већи и
већи скупови података који се баца на њих.

60
00:03:00,160 --> 00:03:01,960
Па, шта је скуп података?

61
00:03:01,960 --> 00:03:03,910
Шта сам мислио када сам то рекао?

62
00:03:03,910 --> 00:03:07,600
То значи да било шта што највише
смисла у контексту, да будем искрен.

63
00:03:07,600 --> 00:03:11,160
Ако имамо алгоритам, на
Процеси Стрингс-- смо вероватно

64
00:03:11,160 --> 00:03:13,440
говоримо о величини низа.

65
00:03:13,440 --> 00:03:15,190
То су подаци договорен--
величина, број

66
00:03:15,190 --> 00:03:17,050
знакова који чине низ.

67
00:03:17,050 --> 00:03:20,090
Ако говоримо о једној
алгоритам који обрађује фајлове,

68
00:03:20,090 --> 00:03:23,930
можемо да причамо о томе како
многи килобајта чине тај фајл.

69
00:03:23,930 --> 00:03:25,710
И то је скуп података.

70
00:03:25,710 --> 00:03:28,870
Ако говоримо о алгоритму
да рукује низова генерално,

71
00:03:28,870 --> 00:03:31,510
као што су алгоритама сортирања
или тражи алгоритме,

72
00:03:31,510 --> 00:03:36,690
вероватно говоримо о броју
елемената који чине низ.

73
00:03:36,690 --> 00:03:39,272
>> Сада можемо да измерите
алгоритхм-- посебно,

74
00:03:39,272 --> 00:03:40,980
кад кажем да можемо
мерење алгоритам, ја

75
00:03:40,980 --> 00:03:43,840
значи можемо да измеримо колико
многи извори заузима.

76
00:03:43,840 --> 00:03:48,990
Да ли ти ресурси су, колико
бајтова РАМ-- или мегабајта РАМ-а

77
00:03:48,990 --> 00:03:49,790
користи.

78
00:03:49,790 --> 00:03:52,320
Или колико времена је потребно за покретање.

79
00:03:52,320 --> 00:03:56,200
И можемо назвати
мерење, произвољно ф н.

80
00:03:56,200 --> 00:03:59,420
Где је Н број
елементи у скупу података.

81
00:03:59,420 --> 00:04:02,640
И Ф н је колико Сометхингс.

82
00:04:02,640 --> 00:04:07,530
Колико јединица ресурса ради
је потребно за обраду тих података.

83
00:04:07,530 --> 00:04:10,030
>> Сада, ми заправо не занима
шта Ф од н је тачно.

84
00:04:10,030 --> 00:04:13,700
У ствари, ми смо веома ретко вилл--
сигурно никада неће у овом цласс-- И

85
00:04:13,700 --> 00:04:18,709
зарони у било заиста дубоко
анализа онога м од н.

86
00:04:18,709 --> 00:04:23,510
Ми ћемо да причамо о томе шта Ф од
н отприлике или шта тежи да.

87
00:04:23,510 --> 00:04:27,600
А тенденција алгоритма је
диктирао свом највишем реда мандата.

88
00:04:27,600 --> 00:04:29,440
И можемо да видимо шта
мислили да је узимање

89
00:04:29,440 --> 00:04:31,910
Поглед на много конкретан пример.

90
00:04:31,910 --> 00:04:34,620
>> Рецимо да имамо
три различита алгоритми.

91
00:04:34,620 --> 00:04:39,350
Први од који узима Н
кубикована, неке јединице ресурса

92
00:04:39,350 --> 00:04:42,880
обрадити скуп података величине н.

93
00:04:42,880 --> 00:04:47,000
Имамо другу алгоритам који траје
Н коцки Плус Н квадрат ресурси

94
00:04:47,000 --> 00:04:49,350
обрадити скуп података величине н.

95
00:04:49,350 --> 00:04:52,030
И ми имамо трећи
алгоритам који ради у-- да

96
00:04:52,030 --> 00:04:58,300
заузима Н куб минус 8Н квадрат
плус 20 Н јединице ресурса

97
00:04:58,300 --> 00:05:02,370
да обради алгоритам
са подацима наведеним у величине н.

98
00:05:02,370 --> 00:05:05,594
>> Сада опет, стварно не иде
да се у овом нивоу детаља.

99
00:05:05,594 --> 00:05:08,260
Ја стварно само ово горе
овде као илустрацију тачке

100
00:05:08,260 --> 00:05:10,176
да ћу бити
одлука у секунди, што

101
00:05:10,176 --> 00:05:12,980
је да ми је стало само
о тенденцији ствари

102
00:05:12,980 --> 00:05:14,870
јер су скупови података постају већи.

103
00:05:14,870 --> 00:05:18,220
Дакле, ако је скуп података је мала, нема
заправо прилично велика разлика

104
00:05:18,220 --> 00:05:19,870
у ових алгоритама.

105
00:05:19,870 --> 00:05:23,000
Трећи алгоритам тамо
узима 13 пута дуже,

106
00:05:23,000 --> 00:05:27,980
13 пута износ средстава
покренути у односу на први један.

107
00:05:27,980 --> 00:05:31,659
>> Ако је наш сет података је величина 10, која
је већа, али не нужно огромна,

108
00:05:31,659 --> 00:05:33,950
видимо да постоји
заправо помало разлике.

109
00:05:33,950 --> 00:05:36,620
Трећи алгоритам
постаје ефикаснији.

110
00:05:36,620 --> 00:05:40,120
Ради се о заправо 40% -
или 60% ефикаснији.

111
00:05:40,120 --> 00:05:41,580
Потребно је 40%, количина времена.

112
00:05:41,580 --> 00:05:45,250
То може рун-- може да потраје
400 јединица ресурса

113
00:05:45,250 --> 00:05:47,570
обрадити скуп података величине 10.

114
00:05:47,570 --> 00:05:49,410
Док је прва
алгоритам, с друге стране,

115
00:05:49,410 --> 00:05:54,520
узима 1.000 јединица ресурса
обрадити скуп података величине 10.

116
00:05:54,520 --> 00:05:57,240
Али погледајте шта се дешава као
наш број бити још већи.

117
00:05:57,240 --> 00:05:59,500
>> Сада, разлика
између ових алгоритама

118
00:05:59,500 --> 00:06:01,420
почну да постане мало мање очигледна.

119
00:06:01,420 --> 00:06:04,560
И чињеница да постоје
нижа реда термс-- односно,

120
00:06:04,560 --> 00:06:09,390
термини са нижим екпонентс--
почињу да постају небитне.

121
00:06:09,390 --> 00:06:12,290
Ако скуп података величине
1.000 и први алгоритам

122
00:06:12,290 --> 00:06:14,170
ради у милијарду корака.

123
00:06:14,170 --> 00:06:17,880
И други алгоритам ради у
а милијарду и милион корака.

124
00:06:17,880 --> 00:06:20,870
И трећи алгоритам ради
у само мање од милијарду корака.

125
00:06:20,870 --> 00:06:22,620
То је прилично милијарду корака.

126
00:06:22,620 --> 00:06:25,640
Ови термини нижег реда старт
да постане заиста небитно.

127
00:06:25,640 --> 00:06:27,390
И само да стварно
чекић кући поента

128
00:06:27,390 --> 00:06:31,240
ако је унос података је величине А
миллион-- све три од њих прилично

129
00:06:31,240 --> 00:06:34,960
узме један куинтиллион-- ако
моја математика је цоррецт-- корака

130
00:06:34,960 --> 00:06:37,260
да процесуира унос података
величине милиона.

131
00:06:37,260 --> 00:06:38,250
То је много корака.

132
00:06:38,250 --> 00:06:42,092
И чињеница да је један од њих могао
потрајати неколико 100.000, или пар 100

133
00:06:42,092 --> 00:06:44,650
милиона чак и мање када
говоримо о броју

134
00:06:44,650 --> 00:06:46,990
да биг-- некако је небитно.

135
00:06:46,990 --> 00:06:50,006
Сви они имају тенденцију да
око Н Цубед,

136
00:06:50,006 --> 00:06:52,380
па ми заправо би се односио
на све ове алгоритама

137
00:06:52,380 --> 00:06:59,520
као по налогу н
коцки или велики О на н куб.

138
00:06:59,520 --> 00:07:03,220
>> Ево листе неких више
заједничке рачунарске класе сложености

139
00:07:03,220 --> 00:07:05,820
да ћемо наићи у
алгоритми, генерално.

140
00:07:05,820 --> 00:07:07,970
Такође конкретно у ЦС50.

141
00:07:07,970 --> 00:07:11,410
То су наручени од
генерално најбржи на врху,

142
00:07:11,410 --> 00:07:13,940
да се генерално Најспорији на дну.

143
00:07:13,940 --> 00:07:16,920
Дакле, константа време алгоритми имају тенденцију
да буде најбржи, без обзира

144
00:07:16,920 --> 00:07:19,110
од величине
унос података прођете у.

145
00:07:19,110 --> 00:07:23,760
Увек узети једну операцију или
једна јединица ресурса да се бави.

146
00:07:23,760 --> 00:07:25,730
То би могло бити 2, могло би
бити 3, могло би бити 4.

147
00:07:25,730 --> 00:07:26,910
Али то је исти број.

148
00:07:26,910 --> 00:07:28,400
Не варира.

149
00:07:28,400 --> 00:07:31,390
>> Логаритхмиц време алгоритми
су нешто боље.

150
00:07:31,390 --> 00:07:33,950
И стварно добар пример
логаритамска време алгоритам

151
00:07:33,950 --> 00:07:37,420
ви сте сигурно видели до сада је
цепање именика

152
00:07:37,420 --> 00:07:39,480
да пронађе Мике Смитх у телефонском именику.

153
00:07:39,480 --> 00:07:40,980
Цут смо проблем на пола.

154
00:07:40,980 --> 00:07:43,580
И тако добија већи н
и већи и ларгер--

155
00:07:43,580 --> 00:07:47,290
У ствари, сваки пут кад удвостручити
н потребно је само још један корак.

156
00:07:47,290 --> 00:07:49,770
Дакле, то је много боље
него, рецимо, линеарно време.

157
00:07:49,770 --> 00:07:53,030
Који је ако Доубле Н, она
узима двоструко број корака.

158
00:07:53,030 --> 00:07:55,980
Ако троструко н је потребно
утростручити броја корака.

159
00:07:55,980 --> 00:07:58,580
Један корак по јединици.

160
00:07:58,580 --> 00:08:01,790
>> Онда су се ствари се мало море--
мало мање сјајно одатле.

161
00:08:01,790 --> 00:08:06,622
Имате линеарно ритмички времена, понекад
зове дневник линеарно време или само н лог н.

162
00:08:06,622 --> 00:08:08,330
А ми ћемо један пример
алгоритма која

163
00:08:08,330 --> 00:08:13,370
Ради у н лог н, што је још боље
од квадратна времена-- готово Н квадрат.

164
00:08:13,370 --> 00:08:17,320
Или полином време, два н
било који број већи од два.

165
00:08:17,320 --> 00:08:20,810
Или експоненцијално време, које
је чак ворсе-- Ц на Н.

166
00:08:20,810 --> 00:08:24,670
Дакле, нека исти број подигнута на
моћ величине улаза.

167
00:08:24,670 --> 00:08:28,990
Дакле, ако постоји 1,000-- ако је
унос података је величине 1000,

168
00:08:28,990 --> 00:08:31,310
било би потребно Ц до 1,000тх власт.

169
00:08:31,310 --> 00:08:33,559
То је много горе него полинома време.

170
00:08:33,559 --> 00:08:35,030
>> Факторијел време је још горе.

171
00:08:35,030 --> 00:08:37,760
И, у ствари, ту стварно
постоји бескрајно време алгоритми,

172
00:08:37,760 --> 00:08:43,740
као што су, такозвана глупа сорт-- чија
посао је да насумично схуффле низ

173
00:08:43,740 --> 00:08:45,490
а затим проверите да ли
да ли је то решено.

174
00:08:45,490 --> 00:08:47,589
А ако није, случајно
поново промешати низ

175
00:08:47,589 --> 00:08:49,130
и проверите да ли је то решено.

176
00:08:49,130 --> 00:08:51,671
И као што вероватно можете имагине--
можете да замислите ситуацију

177
00:08:51,671 --> 00:08:55,200
где је у најгорем случају, то ће
никада није почети са низом.

178
00:08:55,200 --> 00:08:57,150
То алгоритам ће покренути заувек.

179
00:08:57,150 --> 00:08:59,349
И тако то би био
бесконачно време алгоритам.

180
00:08:59,349 --> 00:09:01,890
Надам се да нећу писати
било факторијални или бесконачно време

181
00:09:01,890 --> 00:09:04,510
алгоритми у ЦС50.

182
00:09:04,510 --> 00:09:09,150
>> Дакле, узмимо мало
бетон поглед на неке једноставније

183
00:09:09,150 --> 00:09:11,154
рачунарска комплексност класе.

184
00:09:11,154 --> 00:09:13,070
Дакле, имамо екампле--
или два примера овде-

185
00:09:13,070 --> 00:09:15,590
сталних временских алгоритама,
који увек узимају

186
00:09:15,590 --> 00:09:17,980
једна операција у најгорем слуцају.

187
00:09:17,980 --> 00:09:20,050
Дакле, први екампле--
имамо функцију

188
00:09:20,050 --> 00:09:23,952
позвао 4 за вас, који
заузима низ величине 1.000.

189
00:09:23,952 --> 00:09:25,660
Али онда очигледно
уствари не изгледају

190
00:09:25,660 --> 00:09:29,000
у то-- не стварно брига шта је
унутар ње, те низа.

191
00:09:29,000 --> 00:09:30,820
Увек само враћа четири.

192
00:09:30,820 --> 00:09:32,940
Дакле, то алгоритам,
упркос чињеници да је

193
00:09:32,940 --> 00:09:35,840
узима 1.000 елементе не
ништа са њима.

194
00:09:35,840 --> 00:09:36,590
Само се враћа четири.

195
00:09:36,590 --> 00:09:38,240
Увек је један корак.

196
00:09:38,240 --> 00:09:41,600
>> У ствари, дода се 2 нумс-- која
Видели смо раније као па--

197
00:09:41,600 --> 00:09:43,680
Само обрађује два броја.

198
00:09:43,680 --> 00:09:44,692
То није један корак.

199
00:09:44,692 --> 00:09:45,900
То је заправо пар корака.

200
00:09:45,900 --> 00:09:50,780
Добијате добијате б, да их додате
заједно, а ви излазних резултата.

201
00:09:50,780 --> 00:09:53,270
Тако да је 84 корака.

202
00:09:53,270 --> 00:09:55,510
Али увек је константна,
без обзира на А или Б.

203
00:09:55,510 --> 00:09:59,240
Мораш да добијем, да б, додајте
их заједно, излаз резултат.

204
00:09:59,240 --> 00:10:02,900
Дакле, то је константа време алгоритам.

205
00:10:02,900 --> 00:10:05,170
>> Ево пример
линеарно време алгоритхм--

206
00:10:05,170 --> 00:10:08,740
алгоритам који гетс-- који траје
један додатни корак, евентуално,

207
00:10:08,740 --> 00:10:10,740
као ваш унос расте 1.

208
00:10:10,740 --> 00:10:14,190
Тако, рецимо тражимо
број 5 унутар низа.

209
00:10:14,190 --> 00:10:16,774
Можда ћете морати ситуацији у којој
можете да пронађу је прилично рано.

210
00:10:16,774 --> 00:10:18,606
Али такође може имати
ситуација у којој је

211
00:10:18,606 --> 00:10:20,450
можда последњи елемент низа.

212
00:10:20,450 --> 00:10:23,780
У низу величине 5, ако
тражимо број 5.

213
00:10:23,780 --> 00:10:25,930
Било би потребно 5 корака.

214
00:10:25,930 --> 00:10:29,180
И у ствари, замислите да постоји
Не 5 нигде у овом низу.

215
00:10:29,180 --> 00:10:32,820
Ми још увек у ствари да погледам
сваки елемент низа

216
00:10:32,820 --> 00:10:35,550
у циљу одређивања
ли или не 5 постоји.

217
00:10:35,550 --> 00:10:39,840
>> Дакле, у најгорем случају,-а то је да
елемент је последња у низу

218
00:10:39,840 --> 00:10:41,700
или не постоји уопште.

219
00:10:41,700 --> 00:10:44,690
Ми још увек морамо да погледамо
све н елемената.

220
00:10:44,690 --> 00:10:47,120
И тако овај алгоритам
ради у линеарном времену.

221
00:10:47,120 --> 00:10:50,340
Можете потврдити да је
екстраполирањем мало говорећи,

222
00:10:50,340 --> 00:10:53,080
ако смо имали низ 6-елемент и
ми смо у потрази за број 5,

223
00:10:53,080 --> 00:10:54,890
то би могло потрајати 6 корака.

224
00:10:54,890 --> 00:10:57,620
Ако имамо низ од 7-елемент и
тражимо број 5.

225
00:10:57,620 --> 00:10:59,160
То може трајати 7 корака.

226
00:10:59,160 --> 00:11:02,920
Као што смо додати још један елемент на нашу
Арраи, потребно је још један корак.

227
00:11:02,920 --> 00:11:06,750
То је линеарна алгоритам
у најгорем слуцају.

228
00:11:06,750 --> 00:11:08,270
>> Пар брзих питања за вас.

229
00:11:08,270 --> 00:11:11,170
Шта је оно што је рунтиме--
у најгорем случају рунтиме

230
00:11:11,170 --> 00:11:13,700
овог посебног фрагмент кода?

231
00:11:13,700 --> 00:11:17,420
Дакле, ја имам 4 петљу овде који ради
од Ј једнако 0, па све до м.

232
00:11:17,420 --> 00:11:21,980
И шта ја видим овдје, јесте да
тело петље тече у сталном времену.

233
00:11:21,980 --> 00:11:24,730
Дакле, користећи терминологију која
већ смо причали шта о--

234
00:11:24,730 --> 00:11:29,390
био би у најгорем случају
Рунтиме овог алгоритма?

235
00:11:29,390 --> 00:11:31,050
Узмите мало.

236
00:11:31,050 --> 00:11:34,270
Унутрашњи део петље
ради у сталном време.

237
00:11:34,270 --> 00:11:37,510
И спољни део од
петља ће се покренути м пута.

238
00:11:37,510 --> 00:11:40,260
Дакле, шта је овде у најгорем случају рунтиме?

239
00:11:40,260 --> 00:11:43,210
Да ли сте погодили велики Ø м?

240
00:11:43,210 --> 00:11:44,686
Био би у праву.

241
00:11:44,686 --> 00:11:46,230
>> Како другом?

242
00:11:46,230 --> 00:11:48,590
Овај пут имамо
петље унутар петље.

243
00:11:48,590 --> 00:11:50,905
Ми имамо спољашње петљу
који ради од нуле до п.

244
00:11:50,905 --> 00:11:54,630
И имамо унутрашње петље који ради
од нуле до п, и унутар тога,

245
00:11:54,630 --> 00:11:57,890
Тврдим да је орган којем
петља ради у сталном време.

246
00:11:57,890 --> 00:12:02,330
Дакле, шта је у најгорем случају рунтиме
овог посебног фрагмент кода?

247
00:12:02,330 --> 00:12:06,140
Па, опет, имамо
Спољни петља која води стр пута.

248
00:12:06,140 --> 00:12:09,660
И сваки времена-- готово итерација
те петље, а.

249
00:12:09,660 --> 00:12:13,170
Имамо унутрашњу петљу
који такође води стр пута.

250
00:12:13,170 --> 00:12:16,900
И онда унутар тога, ту је и
константа времена-- готово мало Преглед тамо.

251
00:12:16,900 --> 00:12:19,890
>> Дакле, ако имамо спољашње петље да
ради стр пута унутар којих је

252
00:12:19,890 --> 00:12:22,880
унутрашња петља која
ради п тимес-- шта је

253
00:12:22,880 --> 00:12:26,480
у најгорем случају рунтиме
овог фрагмент кода?

254
00:12:26,480 --> 00:12:30,730
Да ли сте погодили велики о од п квадрат?

255
00:12:30,730 --> 00:12:31,690
>> Ја сам Доуг Лојд.

256
00:12:31,690 --> 00:12:33,880
Ово је ЦС50.

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