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
Это не означает, что О (п) алгоритмы всегда работать быстрее

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
>> Вот асимптотической сложности. Спасибо.