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
上运行的顺序的g（x）

29
00:01:13,390 --> 00:01:15,140
如果存在一些（x）的值中，x 0和

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
该常数乘以克（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
说，你大小为10的数组排序数组的大小为1000。

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
的字符串，例如，在一个变量称为“LEN”，

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
即使是100万个字符长，

82
00:03:28,690 --> 00:03:31,150
你就必须这样做，这种方法找到字符串的长度，

83
00:03:31,150 --> 00:03:33,790
是读出的值的变量的len，

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）2比O（n）的算法，算法是渐近慢。

108
00:04:32,980 --> 00:04:35,910
那就是，作为元素的数目（n）的增长，

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）2的算法，即使是在同样的环境下，

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（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
或这些操作，

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
这只是更多的一倍大小的数组操作。

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（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
最坏情况下的上界被称为大“O”你已经知道了。

179
00:07:34,270 --> 00:07:38,080
因此，它是O（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
因此，它运行在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
>> 这是渐进复杂度。谢谢。