1
00:00:00,000 --> 00:00:05,830

2
00:00:05,830 --> 00:00:07,910
>> 所有的權利，所以，計算複雜度。

3
00:00:07,910 --> 00:00:10,430
只是有點警告
在我們深入太far--

4
00:00:10,430 --> 00:00:13,070
這很可能是其中
最數學重的東西

5
00:00:13,070 --> 00:00:14,200
我們談論的CS50。

6
00:00:14,200 --> 00:00:16,950
希望這將不會過於龐大
我們會盡力引導你

7
00:00:16,950 --> 00:00:19,200
通過的過程中，但
只是有點公平的警告。

8
00:00:19,200 --> 00:00:21,282
有一點點
數學這裡涉及。

9
00:00:21,282 --> 00:00:23,990
好了，所以為了使
利用我們的計算資源

10
00:00:23,990 --> 00:00:28,170
在現實天下 - 這是真的
重要的是要了解算法

11
00:00:28,170 --> 00:00:30,750
以及如何處理數據。

12
00:00:30,750 --> 00:00:32,810
如果我們有一個非常
高效的算法，

13
00:00:32,810 --> 00:00:36,292
可的資源量最小化
我們可用來對付它。

14
00:00:36,292 --> 00:00:38,750
如果我們有一個算法，
是要採取了很多工作，

15
00:00:38,750 --> 00:00:41,210
處理一個真正
大量的數據，這是

16
00:00:41,210 --> 00:00:44,030
將需要更
和更多的資源，這

17
00:00:44,030 --> 00:00:47,980
就是金錢，RAM，所有的那種東西。

18
00:00:47,980 --> 00:00:52,090
>> 所以，能夠分析一個
使用這種算法工具集，

19
00:00:52,090 --> 00:00:56,110
基本上，詢問的問題 - 
如何做到這一點的算法規模

20
00:00:56,110 --> 00:00:59,020
因為我們在它扔越來越多的數據？

21
00:00:59,020 --> 00:01:02,220
在CS50，數據量我們
有工作是非常小的。

22
00:01:02,220 --> 00:01:05,140
一般情況下，我們的節目會
在第二或less--運行

23
00:01:05,140 --> 00:01:07,830
大概少了很多
尤其是早期。

24
00:01:07,830 --> 00:01:12,250
>> 不過想想一個公司的交易
擁有億萬顧客。

25
00:01:12,250 --> 00:01:14,970
他們需要處理
客戶數據。

26
00:01:14,970 --> 00:01:18,260
作為客戶數量它們
有變得越來越大，

27
00:01:18,260 --> 00:01:21,230
這將需要
越來越多的資源。

28
00:01:21,230 --> 00:01:22,926
還有多少資源？

29
00:01:22,926 --> 00:01:25,050
嗯，這取決於如何
我們分析的算法，

30
00:01:25,050 --> 00:01:28,097
使用該工具箱中的工具。

31
00:01:28,097 --> 00:01:31,180
當我們談論的複雜性
一種算法 - 有時你會

32
00:01:31,180 --> 00:01:34,040
聽到它稱為時間
複雜度和空間複雜度

33
00:01:34,040 --> 00:01:36,190
但我們正要
調用complexity--

34
00:01:36,190 --> 00:01:38,770
我們通常講
在最壞的情況。

35
00:01:38,770 --> 00:01:42,640
由於絕對最差樁
數據，我們可以扔吧，

36
00:01:42,640 --> 00:01:46,440
該算法將如何
處理或處理這些數據？

37
00:01:46,440 --> 00:01:51,450
我們一般稱之為最壞情況下的
運行時的算法大O的。

38
00:01:51,450 --> 00:01:56,770
這樣一種算法可能被說
在n或n鄰鄰運行平方。

39
00:01:56,770 --> 00:01:59,110
而更多的是什麼
這意味著在第二。

40
00:01:59,110 --> 00:02:01,620
>> 然而，有時候，我們做護理
關於最好的情況。

41
00:02:01,620 --> 00:02:05,400
如果數據是一切我們想要的
它是，它是絕對完美

42
00:02:05,400 --> 00:02:09,630
和我們發送此完美
設置數據通過我們的算法。

43
00:02:09,630 --> 00:02:11,470
在這種情況下會如何處理？

44
00:02:11,470 --> 00:02:15,050
我們有時指的是作為
大歐米茄，所以在與大O相反，

45
00:02:15,050 --> 00:02:16,530
我們有大歐米茄。

46
00:02:16,530 --> 00:02:18,880
大歐米茄在最好的情況。

47
00:02:18,880 --> 00:02:21,319
大O在最壞的情況。

48
00:02:21,319 --> 00:02:23,860
一般情況下，當我們談論
所述的算法的複雜性，

49
00:02:23,860 --> 00:02:26,370
我們正在談論的
最壞的情況。

50
00:02:26,370 --> 00:02:28,100
所以記住這一點。

51
00:02:28,100 --> 00:02:31,510
>> 而在這個類中，我們通常會
到一邊離開了嚴格的分析。

52
00:02:31,510 --> 00:02:35,350
有科學和領域
專門用於這種東西。

53
00:02:35,350 --> 00:02:37,610
當我們談論的推理
通過算法，

54
00:02:37,610 --> 00:02:41,822
我們會做件逐件進行多
算法，我們談論的類。

55
00:02:41,822 --> 00:02:44,780
我們真的只是在談論
通過它推理常識，

56
00:02:44,780 --> 00:02:47,070
不與公式或證明，
或類似的東西。

57
00:02:47,070 --> 00:02:51,600
所以不要擔心，我們不會
變成一個大的數學課。

58
00:02:51,600 --> 00:02:55,920
>> 所以我說，我們關心的複雜性
因為它要求的問題，怎麼樣

59
00:02:55,920 --> 00:03:00,160
做我們的算法處理大，
被扔在他們更大的數據集。

60
00:03:00,160 --> 00:03:01,960
那麼，什麼是數據集？

61
00:03:01,960 --> 00:03:03,910
什麼我的意思是當我說？

62
00:03:03,910 --> 00:03:07,600
這意味著不管是什麼讓最
在上下文中意義上說，是誠實的。

63
00:03:07,600 --> 00:03:11,160
如果我們有一個算法，該
流程Strings--我們可能

64
00:03:11,160 --> 00:03:13,440
說起字符串的大小。

65
00:03:13,440 --> 00:03:15,190
這是該數據set--
的大小，數量

66
00:03:15,190 --> 00:03:17,050
字符組成的字符串。

67
00:03:17,050 --> 00:03:20,090
如果我們談論的
算法處理的文件，

68
00:03:20,090 --> 00:03:23,930
我們可能會談論如何
千字節包含該文件。

69
00:03:23,930 --> 00:03:25,710
這就是今天的數據集。

70
00:03:25,710 --> 00:03:28,870
如果我們談論的算法
處理數組更普遍，

71
00:03:28,870 --> 00:03:31,510
如排序算法
或搜索算法，

72
00:03:31,510 --> 00:03:36,690
我們可能談論的數
的組成的陣列元素。

73
00:03:36,690 --> 00:03:39,272
>> 現在，我們可以測量
算法 - 特別是

74
00:03:39,272 --> 00:03:40,980
當我說我們可以
測量的算法，我

75
00:03:40,980 --> 00:03:43,840
意味著我們可以衡量
很多資源，它佔用了。

76
00:03:43,840 --> 00:03:48,990
無論這些資源是多少
RAM--字節或兆字節的RAM

77
00:03:48,990 --> 00:03:49,790
它使用。

78
00:03:49,790 --> 00:03:52,320
或多少時間才能運行。

79
00:03:52,320 --> 00:03:56,200
我們可以把這種
測量，隨意，F N的。

80
00:03:56,200 --> 00:03:59,420
其中n是數
在數據集中的元素。

81
00:03:59,420 --> 00:04:02,640
而F N是多少出頭。

82
00:04:02,640 --> 00:04:07,530
有多少資源的單位呢
它要求以處理該數據。

83
00:04:07,530 --> 00:04:10,030
>> 現在，我們其實並不關心
什麼F N的正是。

84
00:04:10,030 --> 00:04:13,700
事實上，我們很少will--
肯定永遠不會在這個分類 - 我

85
00:04:13,700 --> 00:04:18,709
潛入任何非常深
分析什麼樣的F n為。

86
00:04:18,709 --> 00:04:23,510
我們只是要談論什麼的F
n近似或者什麼也容易。

87
00:04:23,510 --> 00:04:27,600
和算法的傾向是
其最高階項決定。

88
00:04:27,600 --> 00:04:29,440
我們可以看到我
意思是，通過採取

89
00:04:29,440 --> 00:04:31,910
一看一個更具體的例子。

90
00:04:31,910 --> 00:04:34,620
>> 所以我們可以說，我們有
三種不同的算法。

91
00:04:34,620 --> 00:04:39,350
其中第一個佔據N
資源立方，一些單位

92
00:04:39,350 --> 00:04:42,880
處理規模為n的數據集。

93
00:04:42,880 --> 00:04:47,000
我們有第二個算法，需要
ñ立方加N的平方資源

94
00:04:47,000 --> 00:04:49,350
處理規模為n的數據集。

95
00:04:49,350 --> 00:04:52,030
而且我們有第三
算法運行in--的

96
00:04:52,030 --> 00:04:58,300
需要n個立方減去8N平方
加上20 N單位的資源

97
00:04:58,300 --> 00:05:02,370
處理的算法
與數據集大小為n的。

98
00:05:02,370 --> 00:05:05,594
>> 現在，再次，我們真的不打算
進入這種詳細程度。

99
00:05:05,594 --> 00:05:08,260
我真的只是這些了
這裡作為一個點的圖示

100
00:05:08,260 --> 00:05:10,176
那我將是
使在第二，這

101
00:05:10,176 --> 00:05:12,980
是我們唯一真正關心
關於物聯網的趨勢

102
00:05:12,980 --> 00:05:14,870
隨著數據集變得越來越大。

103
00:05:14,870 --> 00:05:18,220
因此，如果數據集為小，有
實際上是一個非常大的差異

104
00:05:18,220 --> 00:05:19,870
在這些算法。

105
00:05:19,870 --> 00:05:23,000
第三種算法有
需要13倍以上，

106
00:05:23,000 --> 00:05:27,980
資源的13倍的量
運行相對於第一個。

107
00:05:27,980 --> 00:05:31,659
>> 如果我們的數據集的大小為10，這
是大的，但不一定是巨大的，

108
00:05:31,659 --> 00:05:33,950
我們可以看到，有
其實有點區別。

109
00:05:33,950 --> 00:05:36,620
第三種算法
變得更加有效。

110
00:05:36,620 --> 00:05:40,120
這是關於實際上40％ - 
或60％更有效。

111
00:05:40,120 --> 00:05:41,580
需要40％的時間量。

112
00:05:41,580 --> 00:05:45,250
它可以run--它可以採取
400單位的資源

113
00:05:45,250 --> 00:05:47,570
處理規模10的數據集。

114
00:05:47,570 --> 00:05:49,410
而第一
算法，相比之下，

115
00:05:49,410 --> 00:05:54,520
需要1000單位的資源
處理規模10的數據集。

116
00:05:54,520 --> 00:05:57,240
但是，看看會發生什麼的
我們的數字得到更大。

117
00:05:57,240 --> 00:05:59,500
>> 現在，所不同的
這些算法之間

118
00:05:59,500 --> 00:06:01,420
開始變得有點不那麼明顯。

119
00:06:01,420 --> 00:06:04,560
而事實上，有
低階terms--或者說，

120
00:06:04,560 --> 00:06:09,390
低exponents--條款
開始變得無關緊要。

121
00:06:09,390 --> 00:06:12,290
如果數據集是大小
1000和第一算法

122
00:06:12,290 --> 00:06:14,170
運行在一個十億步驟。

123
00:06:14,170 --> 00:06:17,880
和第二算法在運行
一個十億和一百萬的步驟。

124
00:06:17,880 --> 00:06:20,870
而第三個算法運行
在略低於一十億步驟。

125
00:06:20,870 --> 00:06:22,620
這幾乎是一個十億步驟。

126
00:06:22,620 --> 00:06:25,640
那些低階項啟動
要成為真正無關緊要。

127
00:06:25,640 --> 00:06:27,390
而就真的
錘回家的point--

128
00:06:27,390 --> 00:06:31,240
如果輸入的數據是大小
million--所有這三個幾乎

129
00:06:31,240 --> 00:06:34,960
採取一quintillion--如果
我的數學是correct--步驟

130
00:06:34,960 --> 00:06:37,260
以處理的數據輸入
規模百萬。

131
00:06:37,260 --> 00:06:38,250
這是一個很大的步驟。

132
00:06:38,250 --> 00:06:42,092
而事實上，他們中的一個可能
採取一對夫婦10萬或一對夫婦100

133
00:06:42,092 --> 00:06:44,650
萬元甚至更少的時候
我們談論了許多

134
00:06:44,650 --> 00:06:46,990
這big--它是一種無關緊要的。

135
00:06:46,990 --> 00:06:50,006
他們都傾向於採取
大約ñ立方，

136
00:06:50,006 --> 00:06:52,380
所以我們實際上是指
所有這些算法

137
00:06:52,380 --> 00:06:59,520
作為n的順序上
立方或大，O n立方的。

138
00:06:59,520 --> 00:07:03,220
>> 下面是一些比較列表
常見的計算複雜性類

139
00:07:03,220 --> 00:07:05,820
我們會遇到
算法，一般。

140
00:07:05,820 --> 00:07:07,970
而在CS50還專門。

141
00:07:07,970 --> 00:07:11,410
這些是從訂購
通常最快在頂部，

142
00:07:11,410 --> 00:07:13,940
到通常最慢的下方。

143
00:07:13,940 --> 00:07:16,920
因此，固定的時間算法往往
是最快的，而不管

144
00:07:16,920 --> 00:07:19,110
的大小的
數據輸入你通過研究。

145
00:07:19,110 --> 00:07:23,760
他們總是需要一個操作或
資源的一個單位來處理。

146
00:07:23,760 --> 00:07:25,730
它可能是2，它可能
是3，它可能是4。

147
00:07:25,730 --> 00:07:26,910
但這是一個常數。

148
00:07:26,910 --> 00:07:28,400
它不改變。

149
00:07:28,400 --> 00:07:31,390
>> 對數時間算法
是略勝一籌。

150
00:07:31,390 --> 00:07:33,950
而一個真正的好例子
對數時間算法

151
00:07:33,950 --> 00:07:37,420
你一定已經被看到現在是
撕裂電話簿

152
00:07:37,420 --> 00:07:39,480
找到邁克·史密斯在電話簿。

153
00:07:39,480 --> 00:07:40,980
我們切成兩半的問題。

154
00:07:40,980 --> 00:07:43,580
所以，當n變大
和更大和larger--

155
00:07:43,580 --> 00:07:47,290
其實，每次增加一倍
N，只需要一個步驟。

156
00:07:47,290 --> 00:07:49,770
所以這是好了很多
比說，線性時間。

157
00:07:49,770 --> 00:07:53,030
這是你的兩倍N，它
採取的步驟數量的兩倍。

158
00:07:53,030 --> 00:07:55,980
如果你三倍N，它需要
三倍的步驟的數量。

159
00:07:55,980 --> 00:07:58,580
每單位的一個步驟。

160
00:07:58,580 --> 00:08:01,790
>> 然後，事情變得有點緩慢 - 
從那裡少一點大。

161
00:08:01,790 --> 00:08:06,622
你有線性的節奏，時而
所謂的對數線性時間或只是N日誌ñ。

162
00:08:06,622 --> 00:08:08,330
我們會為例
的算法的那

163
00:08:08,330 --> 00:08:13,370
運行中的n log N，這仍然是更好的
比二次時間 - ñ平方。

164
00:08:13,370 --> 00:08:17,320
或者多項式時間，n兩個
任何數目大於2。

165
00:08:17,320 --> 00:08:20,810
或指數的時間，這
甚至worse-- C到n個。

166
00:08:20,810 --> 00:08:24,670
因此，一些常數提高到
輸入的大小的功率。

167
00:08:24,670 --> 00:08:28,990
所以，如果有1,000--如果
數據輸入是大小1000，

168
00:08:28,990 --> 00:08:31,310
它會採取C到第1,000權力。

169
00:08:31,310 --> 00:08:33,559
這是一個很多比多項式時間差。

170
00:08:33,559 --> 00:08:35,030
>> 階乘時間更是雪上加霜。

171
00:08:35,030 --> 00:08:37,760
而事實上，也確實
有無限的時間算法，

172
00:08:37,760 --> 00:08:43,740
例如，所謂的愚蠢類別 - 其
工作是隨機洗牌數組

173
00:08:43,740 --> 00:08:45,490
然後檢查
無論是排序。

174
00:08:45,490 --> 00:08:47,589
如果它不是，隨機
再次洗牌陣列

175
00:08:47,589 --> 00:08:49,130
並檢查是否它的排序。

176
00:08:49,130 --> 00:08:51,671
正如你可能imagine--
你能想像一個情況

177
00:08:51,671 --> 00:08:55,200
其中在最壞的情況下，這種意願
從來沒有真正開始的數組。

178
00:08:55,200 --> 00:08:57,150
該算法將永遠運行。

179
00:08:57,150 --> 00:08:59,349
因此，這將是一個
無限時間的算法。

180
00:08:59,349 --> 00:09:01,890
希望你會不會寫
任何因子或無限的時間

181
00:09:01,890 --> 00:09:04,510
算法CS50。

182
00:09:04,510 --> 00:09:09,150
>> 那麼，讓我們多了幾分
具體看一些簡單的

183
00:09:09,150 --> 00:09:11,154
計算複雜性類。

184
00:09:11,154 --> 00:09:13,070
因此，我們有一個example--
兩個例子這裡 - 

185
00:09:13,070 --> 00:09:15,590
恆定時間算法，
它始終以

186
00:09:15,590 --> 00:09:17,980
在最壞的情況下，單一的操作。

187
00:09:17,980 --> 00:09:20,050
因此，第一個example--
我們有一個函數

188
00:09:20,050 --> 00:09:23,952
所謂的4對你來說，這
取大小1000的數組。

189
00:09:23,952 --> 00:09:25,660
但後​​來顯然
實際上不看

190
00:09:25,660 --> 00:09:29,000
在它 - 並不真正關心什麼
裡面那個陣吧。

191
00:09:29,000 --> 00:09:30,820
永遠只是返回四個。

192
00:09:30,820 --> 00:09:32,940
所以，這算法，
儘管事實上，它

193
00:09:32,940 --> 00:09:35,840
需要1000元不
做他們什麼。

194
00:09:35,840 --> 00:09:36,590
剛剛返回四個。

195
00:09:36,590 --> 00:09:38,240
它總是一個步驟。

196
00:09:38,240 --> 00:09:41,600
>> 其實，加2 nums--這
我們以前作為well--見過

197
00:09:41,600 --> 00:09:43,680
只是處理兩個整數。

198
00:09:43,680 --> 00:09:44,692
這不是一個單一的步驟。

199
00:09:44,692 --> 00:09:45,900
它實際上是一對夫婦的步驟。

200
00:09:45,900 --> 00:09:50,780
你得到了，你就會得到B，你加他們
在一起，你的輸出結果。

201
00:09:50,780 --> 00:09:53,270
因此，這84步。

202
00:09:53,270 --> 00:09:55,510
但是，它總是不斷的，
不管a或b。

203
00:09:55,510 --> 00:09:59,240
你要得到一個，拿到B，加
在一起，輸出其結果。

204
00:09:59,240 --> 00:10:02,900
所以這是一個恆定的時間算法。

205
00:10:02,900 --> 00:10:05,170
>> 這裡有一個例子
線性時間算法 - 

206
00:10:05,170 --> 00:10:08,740
這gets--接受一個算法
一個附加步驟，可能的話，

207
00:10:08,740 --> 00:10:10,740
作為輸入增長了1。

208
00:10:10,740 --> 00:10:14,190
因此，我們說，我們正在尋找
數5內的陣列。

209
00:10:14,190 --> 00:10:16,774
你可能會遇到這樣的情況
你可以找到它相當早。

210
00:10:16,774 --> 00:10:18,606
但你也可以有
的情況下它

211
00:10:18,606 --> 00:10:20,450
可能是該陣列的最後一個元素。

212
00:10:20,450 --> 00:10:23,780
在大小5，數組，如果
我們正在尋找的數字5。

213
00:10:23,780 --> 00:10:25,930
這將需要5個步驟。

214
00:10:25,930 --> 00:10:29,180
而事實上，想像有
不隨地5此數組中。

215
00:10:29,180 --> 00:10:32,820
我們實際上仍然要看看
該陣列的每一個元素

216
00:10:32,820 --> 00:10:35,550
為了確定
無論是否5是存在的。

217
00:10:35,550 --> 00:10:39,840
>> 因此，在最壞情況下，這是
該元素是最後一個陣列中

218
00:10:39,840 --> 00:10:41,700
或不存在的。

219
00:10:41,700 --> 00:10:44,690
我們還是來看看
所有的n個元素。

220
00:10:44,690 --> 00:10:47,120
因此該算法
以線性時間運行。

221
00:10:47,120 --> 00:10:50,340
您可以確認通過
說外推一點點，

222
00:10:50,340 --> 00:10:53,080
如果我們有一個6-元件陣列和
我們正在尋找5號，

223
00:10:53,080 --> 00:10:54,890
它可能需要6個步驟。

224
00:10:54,890 --> 00:10:57,620
如果我們有一個7-元件陣列和
我們正在尋找的數字5。

225
00:10:57,620 --> 00:10:59,160
這可能需要7個步驟。

226
00:10:59,160 --> 00:11:02,920
當我們增加一個元素，我們的
陣列，它需要一個步驟。

227
00:11:02,920 --> 00:11:06,750
這是一個線性算法
在最壞的情況下。

228
00:11:06,750 --> 00:11:08,270
>> 夫婦簡單的問題給你。

229
00:11:08,270 --> 00:11:11,170
什麼是runtime--什麼
最壞情況下的運行時

230
00:11:11,170 --> 00:11:13,700
的代碼，這個特殊的片段？

231
00:11:13,700 --> 00:11:17,420
所以我有一個4環路這裡運行
從第j等於0，一路為m。

232
00:11:17,420 --> 00:11:21,980
而我所看到這裡，是，
循環體運行在固定的時間。

233
00:11:21,980 --> 00:11:24,730
因此，使用術語
我們已經談過about--什麼

234
00:11:24,730 --> 00:11:29,390
將是最壞的情況
該算法的運行時間？

235
00:11:29,390 --> 00:11:31,050
拿第二。

236
00:11:31,050 --> 00:11:34,270
環路的內側部分
運行在固定的時間。

237
00:11:34,270 --> 00:11:37,510
和的外側部分
迴路將運行的m倍。

238
00:11:37,510 --> 00:11:40,260
那麼什麼是最壞的情況下運行嗎？

239
00:11:40,260 --> 00:11:43,210
你猜大O m的？

240
00:11:43,210 --> 00:11:44,686
你是對的。

241
00:11:44,686 --> 00:11:46,230
>> 要不要再來一個？

242
00:11:46,230 --> 00:11:48,590
這一次，我們有一個
環路的環路的內側。

243
00:11:48,590 --> 00:11:50,905
我們有一個外環
運行從零到第

244
00:11:50,905 --> 00:11:54,630
我們有一個運行內環
從零到p和的裡面，

245
00:11:54,630 --> 00:11:57,890
予指出，人體的
環在固定時間內運行。

246
00:11:57,890 --> 00:12:02,330
那麼，什麼是最壞情況下的運行時間
的代碼，這個特殊的片段？

247
00:12:02,330 --> 00:12:06,140
好了，再次，我們有一個
運行P乘以外環。

248
00:12:06,140 --> 00:12:09,660
而且每個時間 - 迭代
該循環，而。

249
00:12:09,660 --> 00:12:13,170
我們有一個內環
也運行P乘以。

250
00:12:13,170 --> 00:12:16,900
然後那裡面，還有的
恆時間 - 小片段存在。

251
00:12:16,900 --> 00:12:19,890
>> 因此，如果我們有一個外循環
運行P乘以其內部是

252
00:12:19,890 --> 00:12:22,880
內環那
運行p times--是什麼

253
00:12:22,880 --> 00:12:26,480
最壞情況下的運行時
這個代碼片段？

254
00:12:26,480 --> 00:12:30,730
你猜大O的P平方？

255
00:12:30,730 --> 00:12:31,690
>> 我是道格·勞埃德。

256
00:12:31,690 --> 00:12:33,880
這是CS50。

257
00:12:33,880 --> 00:12:35,622