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
Просто немного предупреждение
Прежде чем мы углубимся в слишком far--

4
00:00:10,430 --> 00:00:13,070
это, вероятно, будет среди
наиболее математике тяжелых вещей

5
00:00:13,070 --> 00:00:14,200
мы говорим о в CS50.

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
в реальном world-- это действительно
Важно понимать алгоритмы

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
в основном, спрашивает question--
как делает эту шкалу алгоритм

20
00:00:56,110 --> 00:00:59,020
как мы бросить все больше и больше данных на нем?

21
00:00:59,020 --> 00:01:02,220
В CS50, количество данных, мы
работать с довольно небольшой.

22
00:01:02,220 --> 00:01:05,140
Как правило, наши программы собираются
для запуска в секунду или less--

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
Когда мы говорим о сложности
algorithm-- иногда вы будете

32
00:01:31,180 --> 00:01:34,040
услышать его называют время
Сложность или пространство сложности

33
00:01:34,040 --> 00:01:36,190
но мы только собираемся
позвонить complexity--

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
Мы обычно называем наихудшее
время выполнения алгоритма большой-O.

38
00:01:51,450 --> 00:01:56,770
Так алгоритм, можно сказать,
работать в O п O или п квадрате.

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
Мы иногда называем, что в
большой Омега, поэтому в отличие от биг-O,

45
00:02:15,050 --> 00:02:16,530
у нас есть большой-Omega.

46
00:02:16,530 --> 00:02:18,880
Большие Омега для лучшем случае.

47
00:02:18,880 --> 00:02:21,319
Большой-O для худшем случае.

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
Если у нас есть алгоритм, в
Процессы Strings-- мы, вероятно,

64
00:03:11,160 --> 00:03:13,440
говорить о размере строки.

65
00:03:13,440 --> 00:03:15,190
Вот данные set--
размер, количество

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
>> Теперь мы можем измерить
algorithm-- в частности,

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
Являются ли эти ресурсы, сколько
байт RAM-- или мегабайт оперативной памяти

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
Где N есть число
элементы в наборе данных.

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
На самом деле, мы очень редко will--
конечно, никогда не будет в этом class-- I

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
для обработки набора данных размера N.

93
00:04:42,880 --> 00:04:47,000
У нас есть второй алгоритм, который принимает
п кубе плюс п квадрате ресурсы

94
00:04:47,000 --> 00:04:49,350
для обработки набора данных размера N.

95
00:04:49,350 --> 00:04:52,030
И у нас есть третий
алгоритм, который работает in--, что

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
Это может run-- это может занять
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
занимает 1000 единиц ресурсов
для обработки набора данных размером 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
И тот факт, что есть
низшего порядка terms-- или, скорее,

120
00:06:04,560 --> 00:06:09,390
члены с более низкой exponents--
начать, чтобы стать не имеет значения.

121
00:06:09,390 --> 00:06:12,290
Если набор данных имеет размер
1000 и первый алгоритм

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
И только по-настоящему
молоток домой point--

128
00:06:27,390 --> 00:06:31,240
Если входные данные размера A
million-- все три из них в значительной степени

129
00:06:31,240 --> 00:06:34,960
взять один quintillion-- если
моя математика correct-- шаги

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
что big-- это вроде не имеет значения.

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
как порядка п
в кубе или большой-O н кубе.

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
А также специально в CS50.

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
найти Mike Smith в телефонной книге.

153
00:07:39,480 --> 00:07:40,980
Режем проблему в два раза.

154
00:07:40,980 --> 00:07:43,580
И так, как н становится больше
и больше и larger--

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
>> Тогда все становится немного more--
немного меньше большая оттуда.

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
работает в н п журнала, который еще лучше
чем квадратичная time-- н квадрате.

164
00:08:13,370 --> 00:08:17,320
Или за полиномиальное время, п двух
любое число, большее двух.

165
00:08:17,320 --> 00:08:20,810
Или экспоненциальный время, которое
даже worse-- С к п.

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
это займет C 1000-власти.

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
таких, как, так называемые глупо sort-- которого
работа, чтобы случайно перемешать массив

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
И, как вы, вероятно, может imagine--
Вы можете представить себе ситуацию,

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
алгоритмы CS50.

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
Поэтому у нас есть example--
или два примера here--

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
Таким образом, первый example--
у нас есть функция

188
00:09:20,050 --> 00:09:23,952
называется 4 для вас, которые
принимает массив размера 1000.

189
00:09:23,952 --> 00:09:25,660
Но то, видимо,
на самом деле не выглядят

190
00:09:25,660 --> 00:09:29,000
в it-- не волнует то, что
внутри него, из этого массива.

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
занимает 1000 элементов не
сделать что-нибудь с ними.

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 nums-- которые
мы видели раньше, как well--

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
>> Вот пример
линейное время algorithm--

206
00:10:05,170 --> 00:10:08,740
алгоритм, который gets--, который принимает
один дополнительный шаг, вероятно,

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
Что runtime--, что это
в худшем случае выполнения

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

231
00:11:13,700 --> 00:11:17,420
Так что у меня 4 петли здесь, который работает
от J равен 0, все, вплоть до м.

232
00:11:17,420 --> 00:11:21,980
И то, что я вижу здесь, является то, что
Тело цикла выполняется за константное время.

233
00:11:21,980 --> 00:11:24,730
Таким образом, используя терминологию, что
мы уже говорили about-- что

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
И каждый time-- итерации
из этой петли, а.

249
00:12:09,660 --> 00:12:13,170
У нас есть внутренний цикл
который также работает р раз.

250
00:12:13,170 --> 00:12:16,900
А потом внутри что, есть
постоянная time-- немного фрагмент там.

251
00:12:16,900 --> 00:12:19,890
>> Так что, если у нас есть внешний контур, что
работает р раз, внутри которого является

252
00:12:19,890 --> 00:12:22,880
внутренний цикл, который
работает стр times-- что

253
00:12:22,880 --> 00:12:26,480
в худшем случае выполнения
из этого фрагмента кода?

254
00:12:26,480 --> 00:12:30,730
Вы догадались большая-O р квадрат?

255
00:12:30,730 --> 00:12:31,690
>> Я Дуг Ллойд.

256
00:12:31,690 --> 00:12:33,880
Это CS50.

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