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
>> Значи, бидејќи ние не може директно да се споредат runtimes на програми

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
и нотација наречена "Биг Ohnotation"

26
00:01:06,110 --> 00:01:08,320
за опишување ова.

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

28
00:01:10,820 --> 00:01:13,390
работи на редоследот на g (x)

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

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

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

32
00:01:19,340 --> 00:01:21,230
тоа постојано пати g (x)

33
00:01:21,230 --> 00:01:23,190
за сите x поголема од X ₀.

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
На кратко, таа работи во О (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
О (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
или О (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
постојат многу различни големи О runtimes за мерење на алгоритми со.

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

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

109
00:04:35,910 --> 00:04:39,280
на крајот О (n) ² алгоритми ќе биде потребно повеќе време

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

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

112
00:04:43,960 --> 00:04:46,410
од О (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
 О (n) ² алгоритам всушност би можеле да работат побрзо,

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

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

118
00:04:58,760 --> 00:05:02,000
на крајот ќе затемнувањето на траење на О (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
алгоритми кои работат во О (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
логаритамска време, О (log n).

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
О (log n).

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
тоа треба да се изврши (log n) Сплит проверки

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
Значи, тоа е О (log n), но Ω (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
Значи, вие мора да одат низ сите n елементи во низа да го најдете,

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

189
00:08:04,320 --> 00:08:06,030
Значи, таа работи во О (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
Значи, О (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
>> Ако сте водење на О (n) ² алгоритам,

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
>> Тоа е асимптотска комплексност. Благодарам.