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
>> 這是漸進複雜度。謝謝。