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
Како се упореде 2 различите алгоритме

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
и нотација се зове "Биг Охнотатион '

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
ради по налогу г (к)

29
00:01:13,390 --> 00:01:15,140
ако постоји неки (к) вредност, к ₀ и

30
00:01:15,140 --> 00:01:17,630
нека константа, Ц, за које

31
00:01:17,630 --> 00:01:19,340
ф (к) је мања или једнака

32
00:01:19,340 --> 00:01:21,230
та стална пута г (к)

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
'Н' у низу.

48
00:02:02,670 --> 00:02:04,910
Укратко, ради у О (н).

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
О (н), само није био довољно брз за тебе?

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
или О (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
Дакле, ради у О (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
ипак је асимптотски цонстант које представљају као О (1).

105
00:04:23,420 --> 00:04:25,120
>> Као што вероватно можете погодити,

106
00:04:25,120 --> 00:04:27,940
постоји много различитих велике О време рада да се измери алгоритме са.

107
00:04:27,940 --> 00:04:32,980
О (н) ² алгоритми су асимптотски спорији од О (н) алгоритма.

108
00:04:32,980 --> 00:04:35,910
То је, као што је број елемената (н) расте,

109
00:04:35,910 --> 00:04:39,280
евентуално О (н) ² алгоритми ће бити потребно више времена

110
00:04:39,280 --> 00:04:41,000
од О (н) алгоритме за приказивање.

111
00:04:41,000 --> 00:04:43,960
То не значи О (н) алгоритми увек трчи брже

112
00:04:43,960 --> 00:04:46,410
од О (н) ² алгоритама, чак у истом окружењу,

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
 је О (н) ² алгоритам може заправо раде брже,

116
00:04:52,900 --> 00:04:55,450
али, на крају, као улазну величину повећава

117
00:04:55,450 --> 00:04:58,760
према бесконачности, О (н) ² алгоритма рунтиме

118
00:04:58,760 --> 00:05:02,000
ће на крају засенити извршни од О (н) алгоритма.

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
алгоритми који раде у О (н) ² време заиста може завршити успорава свој програм,

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
логаритамска време О (лог н).

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
или 3 ових операција,

148
00:06:18,450 --> 00:06:22,260
провере средњи елемент, а затим сече низ у полувремену ће бити потребно,

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

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

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
О (лог н).

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
Дакле, то је О (лог н), али Ω (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
Дакле, ради у О (н) времену

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
Дакле, О (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
>> Ако користите у О (н) ² алгоритма,

215
00:09:12,490 --> 00:09:15,240
или још горе, О (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
>> То је асимптотско сложеност. Хвала.