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
і позначень називається "Великий 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
працює на порядок д (х)

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
F (X) менше або дорівнює

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
'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
О (п), просто не був достатньо швидкий для Вас?

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
Є багато різних великих O виміряти час автономної роботи алгоритмів.

107
00:04:27,940 --> 00:04:32,980
О (п) ² алгоритми асимптотично повільніше, ніж O (N) алгоритмів.

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

109
00:04:35,910 --> 00:04:39,280
в кінцевому підсумку O (п) ² алгоритмів займе більше часу

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

111
00:04:41,000 --> 00:04:43,960
Це не означає, O (п) алгоритми завжди працювати швидше

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

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
в кінцевому підсумку затьмарити час роботи O (п) алгоритм.

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 (п) ² Час дійсно може в кінцевому підсумку уповільнює роботу програми,

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 (журнал 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
O (журнал 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
він повинен виконати (§ п) розкол перевірки

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 (журнал 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
Таким чином, ви повинні йти через все п елементів у масиві, щоб знайти його,

188
00:07:58,560 --> 00:08:02,170
Наприклад, якщо ви шукали 3.

189
00:08:04,320 --> 00:08:06,030
Таким чином, він працює в O (п)

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 (п) ² алгоритм,

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
>> Ось асимптотичної складності. Спасибі.