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 для вас, які
приймає масив розміру 1 000.

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