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
е пари, RAM, всички такива неща.

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
Ние понякога се позовават на нея като
голям Omega, така че за разлика от големите O,

45
00:02:15,050 --> 00:02:16,530
ние имаме голям Omega.

46
00:02:16,530 --> 00:02:18,880
Big-Omega за в най-добрия случай.

47
00:02:18,880 --> 00:02:21,319
Big-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
когато казвам, ние можем
измерване на алгоритъм, I

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

76
00:03:43,840 --> 00:03:48,990
Дали тези ресурси са, колко
байта RAM-- или мегабайта 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
Където п е броят на
елементи в масива от данни.

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
да обработи набор данни от размера п.

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
И ние имаме една трета
алгоритъм, който работи 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
ако въведените данни е с размер на
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
да се намери Майк Смит в телефонния указател.

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-- C до п.

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
Ние все още трябва да разгледаме
Всички N елементи.

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 линия тук, която работи
от к е равна на 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
Знаете ли, предполагам голям O на м?

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
Знаете ли, предполагам, че голяма-О р квадрат?

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