1
00:00:07,720 --> 00:00:10,950
[Powered by Google Translate] Вероятно сте чували хората да говорят за бързо или ефективен алгоритъм

2
00:00:10,950 --> 00:00:13,090
за изпълнение на конкретна задача,

3
00:00:13,090 --> 00:00:16,110
но какво точно означава това за алгоритъм протече бързо и ефективно?

4
00:00:16,110 --> 00:00:18,580
Е, това не говори за измерване в реално време,

5
00:00:18,580 --> 00:00:20,500
като секунди или минути.

6
00:00:20,500 --> 00:00:22,220
Това е така, защото компютърен хардуер

7
00:00:22,220 --> 00:00:24,260
и софтуер се различават драстично.

8
00:00:24,260 --> 00:00:26,020
Моята програма може да работи по-бавно от твоя,

9
00:00:26,020 --> 00:00:28,000
защото аз съм я изпълняват на по-стар компютър,

10
00:00:28,000 --> 00:00:30,110
или защото се случи да се играе онлайн видео игра

11
00:00:30,110 --> 00:00:32,670
в същото време, което е свински паметта ми,

12
00:00:32,670 --> 00:00:35,400
или може да бъде моята програма чрез различен софтуер

13
00:00:35,400 --> 00:00:37,550
, която комуникира с устройството по различен начин на ниско ниво.

14
00:00:37,550 --> 00:00:39,650
Това е все едно да сравняваме ябълки и портокали.

15
00:00:39,650 --> 00:00:41,940
Само защото моя бавен компютър отнема повече време

16
00:00:41,940 --> 00:00:43,410
от вашия да върне отговор

17
00:00:43,410 --> 00:00:45,510
не означава, че имат по-ефективен алгоритъм.

18
00:00:45,510 --> 00:00:48,830
>> Така че, тъй като ние не може директно да се сравнят автономна работа на програмите

19
00:00:48,830 --> 00:00:50,140
в секунди или минути,

20
00:00:50,140 --> 00:00:52,310
как да сравним две различни алгоритми

21
00:00:52,310 --> 00:00:55,030
независимо от техния хардуер или софтуерна среда?

22
00:00:55,030 --> 00:00:58,000
За да се създаде по-еднообразна начин за измерване на алгоритмични ефективност,

23
00:00:58,000 --> 00:01:00,360
компютърни учени и математици са разработили

24
00:01:00,360 --> 00:01:03,830
концепции за измерване на асимптотичната сложността на програмата

25
00:01:03,830 --> 00:01:06,110
и нотация, наречена "Биг Ohnotation"

26
00:01:06,110 --> 00:01:08,320
за описване на това.

27
00:01:08,320 --> 00:01:10,820
Формалната дефиниция е, че една функция е (х)

28
00:01:10,820 --> 00:01:13,390
работи по реда на грам (X)

29
00:01:13,390 --> 00:01:15,140
ако съществува (х) стойност х ₀ и

30
00:01:15,140 --> 00:01:17,630
някои постоянно, C, за които

31
00:01:17,630 --> 00:01:19,340
е (х) е по-малка или равна на

32
00:01:19,340 --> 00:01:21,230
че постоянно пъти грама (X)

33
00:01:21,230 --> 00:01:23,190
за всички Х по-голямо от х ₀.

34
00:01:23,190 --> 00:01:25,290
>> Но не се плаши от формалната дефиниция.

35
00:01:25,290 --> 00:01:28,020
Какво означава това всъщност означава в по-теоретичен план?

36
00:01:28,020 --> 00:01:30,580
Е, това е в основата на начина, по който анализира

37
00:01:30,580 --> 00:01:33,580
колко бързо време на изпълнение на програмата расте асимптотично.

38
00:01:33,580 --> 00:01:37,170
Това е, като размера на вашите входа се увеличава към безкрайност,

39
00:01:37,170 --> 00:01:41,390
да речем, вие сте сортиране на масив с размер 1000, в сравнение с масив с размер 10.

40
00:01:41,390 --> 00:01:44,950
Как растат по време на изпълнение на вашата програма?

41
00:01:44,950 --> 00:01:47,390
Например, представете си брои броя на символите

42
00:01:47,390 --> 00:01:49,350
в низ най-простият начин

43
00:01:49,350 --> 00:01:51,620
 пеша през целия низ

44
00:01:51,620 --> 00:01:54,790
писмо от писмо и добавяне на 1 брояч за всеки знак.

45
00:01:55,700 --> 00:01:58,420
Този алгоритъм се казва, да се движи в линейното време

46
00:01:58,420 --> 00:02:00,460
по отношение на броя на символите,

47
00:02:00,460 --> 00:02:02,670
"N" в низа.

48
00:02:02,670 --> 00:02:04,910
С една дума, тя работи в O (N).

49
00:02:05,570 --> 00:02:07,290
Защо е това?

50
00:02:07,290 --> 00:02:09,539
Е, използването на този подход, времето, необходимо

51
00:02:09,539 --> 00:02:11,300
да прекосяват целия низ

52
00:02:11,300 --> 00:02:13,920
е пропорционален на броя на символите.

53
00:02:13,920 --> 00:02:16,480
Преброяване на знаците в 20-символен низ

54
00:02:16,480 --> 00:02:18,580
ще се вземат два пъти по-дълго, колкото е нужно

55
00:02:18,580 --> 00:02:20,330
да разчита знаците в 10-символен низ

56
00:02:20,330 --> 00:02:23,000
защото трябва да разгледаме всички герои

57
00:02:23,000 --> 00:02:25,740
и всеки герой е на същия период от време да погледнете.

58
00:02:25,740 --> 00:02:28,050
Както може да увеличи броя на символите,

59
00:02:28,050 --> 00:02:30,950
по време на изпълнение ще се повишават линейно с дължината на входа.

60
00:02:30,950 --> 00:02:33,500
>> Сега си представете, ако решите, че линейното време,

61
00:02:33,500 --> 00:02:36,390
O (N), просто не е достатъчно бърз за вас?

62
00:02:36,390 --> 00:02:38,750
Може би сте съхраняване на огромни струни,

63
00:02:38,750 --> 00:02:40,450
и не могат да си позволят допълнително време би отнело

64
00:02:40,450 --> 00:02:44,000
да преминават на героите си броим едно по едно.

65
00:02:44,000 --> 00:02:46,650
Така че, можете да решите да опитате нещо различно.

66
00:02:46,650 --> 00:02:49,270
Какво ще стане, ако ще се случи с вече съхранява броя на символите

67
00:02:49,270 --> 00:02:52,690
в низа, да речем, в променлива наречена "дъл"

68
00:02:52,690 --> 00:02:54,210
в началото на програмата,

69
00:02:54,210 --> 00:02:57,800
, преди да можете дори ако тя се съхранява на първия знак в низ си?

70
00:02:57,800 --> 00:02:59,980
След това всичко, което ще трябва да направя сега, за да разберете дължината на низ,

71
00:02:59,980 --> 00:03:02,570
е да проверите каква е стойността на променливата е.

72
00:03:02,570 --> 00:03:05,530
Може би не трябва да погледнем в себе си низ на всички,

73
00:03:05,530 --> 00:03:08,160
и достъп до стойността на дадена променлива като дъл се счита за

74
00:03:08,160 --> 00:03:11,100
асимптотично константно време на работа,

75
00:03:11,100 --> 00:03:13,070
или O (1).

76
00:03:13,070 --> 00:03:17,110
Защо е това? Е, не забравяйте, какво означава асимптотичната сложност.

77
00:03:17,110 --> 00:03:19,100
Как по време на работа промяна, тъй като размерът

78
00:03:19,100 --> 00:03:21,400
на вашите входове расте?

79
00:03:21,400 --> 00:03:24,630
>> Да речем, че се опитвате да получите броя на знаците в по-голям низ.

80
00:03:24,630 --> 00:03:26,960
Е, това не е от значение колко голям низ,

81
00:03:26,960 --> 00:03:28,690
даже милион знака,

82
00:03:28,690 --> 00:03:31,150
всичко, което ще трябва да направите, за да се намери дължината на низ с този подход,

83
00:03:31,150 --> 00:03:33,790
е да се чете стойността на променливата дъл,

84
00:03:33,790 --> 00:03:35,440
което вече.

85
00:03:35,440 --> 00:03:38,200
Въвеждане на дължина, което означава, че дължината на низа, който се опитвате да намерите,

86
00:03:38,200 --> 00:03:41,510
не оказва влияние върху всичко, колко бързо вашата програма работи.

87
00:03:41,510 --> 00:03:44,550
Тази част от вашата програма ще тече еднакво бързо на един символен низ

88
00:03:44,550 --> 00:03:46,170
и хиляди символен низ,

89
00:03:46,170 --> 00:03:49,140
и затова тази програма ще бъде по-нататък за константно време

90
00:03:49,140 --> 00:03:51,520
по отношение на размера на входа.

91
00:03:51,520 --> 00:03:53,920
>> Разбира се, има един недостатък.

92
00:03:53,920 --> 00:03:55,710
Харчат допълнително пространство в паметта на вашия компютър

93
00:03:55,710 --> 00:03:57,380
съхраняване на променливата

94
00:03:57,380 --> 00:03:59,270
и допълнително време, тя ще ви отведе

95
00:03:59,270 --> 00:04:01,490
да направят действително съхранение на променливата,

96
00:04:01,490 --> 00:04:03,390
но въпросът все още стои,

97
00:04:03,390 --> 00:04:05,060
как дългия низ

98
00:04:05,060 --> 00:04:07,600
не зависи от дължината на низа на всички.

99
00:04:07,600 --> 00:04:10,720
Така че, тя работи в O (1) или константно време.

100
00:04:10,720 --> 00:04:13,070
Това със сигурност не трябва да означава

101
00:04:13,070 --> 00:04:15,610
че кодът работи в 1 стъпка,

102
00:04:15,610 --> 00:04:17,470
но без значение колко стъпки е

103
00:04:17,470 --> 00:04:20,019
ако тя не се променя с размера на входовете,

104
00:04:20,019 --> 00:04:23,420
тя все още е асимптотично константа, която ние представляваме като O (1).

105
00:04:23,420 --> 00:04:25,120
>> Както вероятно можете да се досетите,

106
00:04:25,120 --> 00:04:27,940
има много различни Big O автономна работа за измерване на алгоритми с.

107
00:04:27,940 --> 00:04:32,980
O (N) ² алгоритми са асимптотично по-бавно, отколкото O (N) алгоритми.

108
00:04:32,980 --> 00:04:35,910
Това е, тъй като броят на елементите (н) расте,

109
00:04:35,910 --> 00:04:39,280
в крайна сметка O (N) ² алгоритми ще отнеме повече време

110
00:04:39,280 --> 00:04:41,000
от O (N) алгоритми да се изпълнява.

111
00:04:41,000 --> 00:04:43,960
Това не означава, O (N) алгоритми винаги работи по-бързо

112
00:04:43,960 --> 00:04:46,410
от O (N) ² алгоритми, дори и в една и съща среда,

113
00:04:46,410 --> 00:04:48,080
на същия хардуер.

114
00:04:48,080 --> 00:04:50,180
Може би за малки размери за въвеждане,

115
00:04:50,180 --> 00:04:52,900
 O (N) ² алгоритъм може действително да работят по-бързо,

116
00:04:52,900 --> 00:04:55,450
, но в крайна сметка, като размера на входа се увеличава

117
00:04:55,450 --> 00:04:58,760
към безкрайност, O (N) ² алгоритъм, по време на работа

118
00:04:58,760 --> 00:05:02,000
в крайна сметка ще затъмни време на работа на алгоритъм O (N).

119
00:05:02,000 --> 00:05:04,230
Просто като всяка квадратичен математическа функция

120
00:05:04,230 --> 00:05:06,510
 в крайна сметка ще изпревари която и да е линейна функция,

121
00:05:06,510 --> 00:05:09,200
без значение колко на главата започне линейна функция започва.

122
00:05:10,010 --> 00:05:12,000
Ако работите с големи обеми от данни,

123
00:05:12,000 --> 00:05:15,510
алгоритми, които се движат в O (N) ² време наистина може да се окажете забавя вашата програма,

124
00:05:15,510 --> 00:05:17,770
но за малки размери за въвеждане,

125
00:05:17,770 --> 00:05:19,420
най-вероятно дори няма да забележите.

126
00:05:19,420 --> 00:05:21,280
>> Друг асимптотичната сложност,

127
00:05:21,280 --> 00:05:24,420
логаритмична време, O (дневник н).

128
00:05:24,420 --> 00:05:26,340
Пример за алгоритъм, който работи бързо

129
00:05:26,340 --> 00:05:29,060
е класически алгоритъм двоично търсене,

130
00:05:29,060 --> 00:05:31,850
за намиране на елемент от вече сортиран списък на елементите.

131
00:05:31,850 --> 00:05:33,400
>> Ако не знаете какво двоично търсене,

132
00:05:33,400 --> 00:05:35,170
Ще ти обясня за вас наистина бързо.

133
00:05:35,170 --> 00:05:37,020
Да речем, че търсите за номер 3

134
00:05:37,020 --> 00:05:40,200
в този масив от цели числа.

135
00:05:40,200 --> 00:05:42,140
Тя изглежда в средата елемент на масива

136
00:05:42,140 --> 00:05:46,830
и пита: "е елемент, искам по-голямо от, равно или по-малко от това?"

137
00:05:46,830 --> 00:05:49,150
Ако е еднакъв, то голяма. Намери елемент, и сте готови.

138
00:05:49,150 --> 00:05:51,300
Ако е по-голям, тогава знаете елемент

139
00:05:51,300 --> 00:05:53,440
трябва да бъде в дясната част на масива,

140
00:05:53,440 --> 00:05:55,200
и можете да погледнете, че в бъдеще,

141
00:05:55,200 --> 00:05:57,690
и ако тя е по-малък, тогава знаете, тя трябва да е в лявата страна.

142
00:05:57,690 --> 00:06:00,980
Този процес се повтаря с по-малък размер масив

143
00:06:00,980 --> 00:06:02,870
до правилния елемент е намерен.

144
00:06:08,080 --> 00:06:11,670
>> Този мощен алгоритъм пресича размер на масива наполовина с всяка операция.

145
00:06:11,670 --> 00:06:14,080
Така че, за да намерите елемент в сортиран масив с размер 8,

146
00:06:14,080 --> 00:06:16,170
най-много (влезете ₂ 8),

147
00:06:16,170 --> 00:06:18,450
или три от тези операции,

148
00:06:18,450 --> 00:06:22,260
проверка на средата елемент, а след това рязане на масив в 1/2 ще се изисква,

149
00:06:22,260 --> 00:06:25,670
като има предвид, че масив с размер 16 отнема (влезете ₂ 16),

150
00:06:25,670 --> 00:06:27,480
или четири операции.

151
00:06:27,480 --> 00:06:30,570
Това е само 1 операция за масив двоен размер.

152
00:06:30,570 --> 00:06:32,220
Удвояването на размера на масива

153
00:06:32,220 --> 00:06:35,160
увеличава по време на работа само с 1 парче на този кодекс.

154
00:06:35,160 --> 00:06:37,770
Отново, проверка на средата елемент от списъка, след това разделяне.

155
00:06:37,770 --> 00:06:40,440
Така че, да работят в логаритмична време,

156
00:06:40,440 --> 00:06:42,440
O (Вход н).

157
00:06:42,440 --> 00:06:44,270
Но чакайте, вие казвате,

158
00:06:44,270 --> 00:06:47,510
не това зависи от това къде в списъка елемент, което търсите, е?

159
00:06:47,510 --> 00:06:50,090
Какво става, ако първият елемент, погледнете се случва да бъде най-подходящия?

160
00:06:50,090 --> 00:06:52,040
След това, тя отнема само 1 операция,

161
00:06:52,040 --> 00:06:54,310
без значение колко голям е списъка.

162
00:06:54,310 --> 00:06:56,310
>> Е, това е защо компютърни специалисти имат повече условия

163
00:06:56,310 --> 00:06:58,770
за асимптотичната сложност, които отразяват най-добрия случай

164
00:06:58,770 --> 00:07:01,050
и най-лошия случай изпълнения на алгоритъм.

165
00:07:01,050 --> 00:07:03,320
По-правилно, горни и долни граници

166
00:07:03,320 --> 00:07:05,090
по време на работа.

167
00:07:05,090 --> 00:07:07,660
В най-добрия случай за двоично търсене, нашият елемент е

168
00:07:07,660 --> 00:07:09,330
точно там в средата,

169
00:07:09,330 --> 00:07:11,770
и да го получите за константно време,

170
00:07:11,770 --> 00:07:14,240
без значение колко голяма е останалата част от масива.

171
00:07:15,360 --> 00:07:17,650
Символът, използван за това е Ω.

172
00:07:17,650 --> 00:07:19,930
Така че, този алгоритъм се казва, да се движи в Ω (1).

173
00:07:19,930 --> 00:07:21,990
В най-добрия случай, той бързо намира елемент,

174
00:07:21,990 --> 00:07:24,200
без значение колко голям масив,

175
00:07:24,200 --> 00:07:26,050
но в най-лошия случай,

176
00:07:26,050 --> 00:07:28,690
тя трябва да изпълнява (Вход н) сплит проверки

177
00:07:28,690 --> 00:07:31,030
на масива, за да намерят най-подходящия елемент.

178
00:07:31,030 --> 00:07:34,270
В най-лошия случай горните граници се обозначават с голямото "О", че вече знаете.

179
00:07:34,270 --> 00:07:38,080
Значи, това е O (дневник н), но Ω (1).

180
00:07:38,080 --> 00:07:40,680
>> Линейна търсене, от друга страна,

181
00:07:40,680 --> 00:07:43,220
, в които ви преведе през всеки елемент на масива

182
00:07:43,220 --> 00:07:45,170
да намерите тази, която искате,

183
00:07:45,170 --> 00:07:47,420
е в най-добрия случай Ω (1).

184
00:07:47,420 --> 00:07:49,430
Отново, първият елемент, който искате.

185
00:07:49,430 --> 00:07:51,930
Така, че няма значение колко голям масив.

186
00:07:51,930 --> 00:07:54,840
В най-лошия случай, това е последният елемент в масива.

187
00:07:54,840 --> 00:07:58,560
Така че, вие трябва да преминете през всички н елементите в масива, за да го намери,

188
00:07:58,560 --> 00:08:02,170
искал, ако търсите за 3.

189
00:08:04,320 --> 00:08:06,030
Така че, тя работи в O (N) време

190
00:08:06,030 --> 00:08:09,330
защото това е пропорционална на броя на елементите в масива.

191
00:08:10,800 --> 00:08:12,830
>> Още един символ е Θ.

192
00:08:12,830 --> 00:08:15,820
Това може да се използва за описание на алгоритми, където най-добрите и най-лошите случаи

193
00:08:15,820 --> 00:08:17,440
са едни и същи.

194
00:08:17,440 --> 00:08:20,390
Такъв е случаят в низ дължина алгоритми, за които говорихме по-рано.

195
00:08:20,390 --> 00:08:22,780
Това е, ако го съхранява в променлива преди

196
00:08:22,780 --> 00:08:25,160
ние съхраняваме низ и достъп до него по-късно за константно време.

197
00:08:25,160 --> 00:08:27,920
Без значение какъв номер

198
00:08:27,920 --> 00:08:30,130
сме съхраняване в тази променлива, ще трябва да го погледнете.

199
00:08:33,110 --> 00:08:35,110
В най-добрия случай, ние гледаме на него

200
00:08:35,110 --> 00:08:37,120
и да намерят дължината на низа.

201
00:08:37,120 --> 00:08:39,799
Така Ω (1) или най-добрия случай константно време.

202
00:08:39,799 --> 00:08:41,059
Най-лошия случай е,

203
00:08:41,059 --> 00:08:43,400
ние гледаме на него и да намерят дължината на низа.

204
00:08:43,400 --> 00:08:47,300
Така че, O (1) или постоянна път в най-лошия случай.

205
00:08:47,300 --> 00:08:49,180
Така че, тъй като най-добрия случай и най-тежките случаи са едни и същи,

206
00:08:49,180 --> 00:08:52,520
това може да се каже, да се движи в Θ (1) време.

207
00:08:54,550 --> 00:08:57,010
>> В обобщение, ние имаме добри начини за причина за ефективност кодове

208
00:08:57,010 --> 00:09:00,110
без да знаят нищо за реалния свят време, те да тече,

209
00:09:00,110 --> 00:09:02,270
която е засегната от много външни фактори,

210
00:09:02,270 --> 00:09:04,190
включително различни хардуер, софтуер,

211
00:09:04,190 --> 00:09:06,040
или спецификата на кода си.

212
00:09:06,040 --> 00:09:08,380
Също така, тя ни позволява да разсъждава и за това какво ще се случи

213
00:09:08,380 --> 00:09:10,180
когато размерът на входа се увеличава.

214
00:09:10,180 --> 00:09:12,490
>> Ако сте в O (N) ² алгоритъм,

215
00:09:12,490 --> 00:09:15,240
или по-лошо, O (2 ⁿ) алгоритъм,

216
00:09:15,240 --> 00:09:17,170
един от най-бързо развиващите се видове,

217
00:09:17,170 --> 00:09:19,140
вие наистина ще започнете да забележите забавяне

218
00:09:19,140 --> 00:09:21,220
когато започнете да работите с по-големи обеми от данни.

219
00:09:21,220 --> 00:09:23,590
>> Това е асимптотичната сложност. Благодаря.