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