前言
有需要的同學可以訂閱專欄：Swift數(shù)據(jù)結(jié)構(gòu)和算法專題
代碼地址：Swift數(shù)據(jù)結(jié)構(gòu)和算法代碼
復雜度
這個項目以后會擴展嗎尸闸？
這個古老的問題總是在軟件開發(fā)的設計階段被問到元扔，并且有多種形式。從架構(gòu)的角度來看晓锻，可擴展性是指更改應用程序的難易程度盅称。從數(shù)據(jù)庫的角度來看肩祥，可伸縮性是關于在數(shù)據(jù)庫中保存或檢索數(shù)據(jù)所需的時間。
對于算法缩膝，可擴展性是指算法在執(zhí)行時間和內(nèi)存使用方面隨著輸入大小的增加而執(zhí)行的情況混狠。
當我們處理少量數(shù)據(jù)時，低效率的算法可能仍然感覺很快疾层。然而将饺，隨著數(shù)據(jù)量的增加，低效率的算法變得很糟糕。那么它會變得多糟糕呢俯逾？了解如何量化這是我們需要了解的一項重要技能贸桶。
在本章中，我們將了解 Big O 表示法在兩個維度（執(zhí)行時間和內(nèi)存使用）中不同級別的可伸縮性桌肴。
時間復雜度
對于少量數(shù)據(jù)皇筛，由于現(xiàn)代硬件的速度，即使是最爛的算法也可能看起來很快坠七。然而水醋，隨著數(shù)據(jù)的增加，低效率的算法的成本變得越來越明顯彪置。時間復雜度是隨著輸入大小的增加運行算法所需時間的度量拄踪。
恒定時間
恒定時間算法是一種無論輸入大小如何都具有相同運行時間的算法。參考下面的代碼：
func checkFirst(names: [String]) {
if let first = names.first {
print(first)
} else {
print("no names")
}
}
names 數(shù)組的大小對該函數(shù)的運行時間沒有影響拳魁。無論輸入有 10 個項目還是 1000 萬個項目惶桐，此函數(shù)都只檢查數(shù)組的第一個元素。這是時間與數(shù)據(jù)大小之間的時間復雜度的可視化：
[圖片上傳失敗...(image-45f300-1645529361634)]
隨著輸入數(shù)據(jù)的增加潘懊，算法所花費的時間不會改變姚糊。
為簡潔起見，程序員使用一種稱為 Big O 表示法的表示法來表示各種時間復雜度的大小授舟。常數(shù)時間的大 O 表示法是 O(1)救恨。
線性時間
我們看一下下面的代碼：
func printNames(names: [String]) {
for _ in names {
for name in names {
print(name)
}
}
}
這一次，該函數(shù)為數(shù)組中的每個名稱打印出數(shù)組中的所有名稱释树。如果您有一個包含十條數(shù)據(jù)的數(shù)組肠槽，它將十次打印十個名稱的完整列表。那是 100 個打印語句奢啥。
如果將輸入大小增加 1秸仙，它將打印 11 個名稱的完整列表 11 次，產(chǎn)生 121 個打印語句桩盲。與之前以線性時間運行的函數(shù)不同寂纪，算法會隨著數(shù)據(jù)量的增加而迅速失控。
下圖說明了這種行為：
[圖片上傳失敗...(image-f47ac1-1645529361634)]
隨著輸入數(shù)據(jù)大小的增加正驻，算法運行所需的時間會急劇增加弊攘。因此，算法在規(guī)模上表現(xiàn)不佳姑曙。
二次時間的大 O 表示法是 O(n2)襟交。
無論線性時間 O(n) 算法的編寫效率如何（即便你加上各種等待算法），對于足夠大的n伤靠，線性時間算法將比超級優(yōu)化的二次算法執(zhí)行得更快捣域。
對數(shù)時間
到目前為止啼染，我們已經(jīng)了解了線性和二次時間復雜度，其中輸入的每個元素至少檢查一次焕梅。但是迹鹅，在某些情況下，只需要檢查輸入的子集贞言，從而加快運行時間斜棚。
屬于這類時間復雜度的算法是可以通過對輸入數(shù)據(jù)做出一些假設來利用一些捷徑的算法。例如该窗，如果我們有一個排序的整數(shù)數(shù)組弟蚀，那么查找特定值是否存在的最快方法是什么？
一個天真的解決方案是從頭到尾檢查數(shù)組酗失，在得出結(jié)論之前檢查每個元素义钉。由于我們要檢查每個元素一次，這將是一個 O(n) 算法规肴。線性時間相當不錯捶闸，但你可以做得更好。由于輸入數(shù)組已排序拖刃，因此您可以進行優(yōu)化删壮。考慮以下代碼：
let numbers = [1, 3, 56, 66, 68, 80, 99, 105, 450]
func naiveContains(_ value: Int, in array: [Int]) -> Bool {
for element in array {
if element == value {
return true
}
}
return false
}
如果我們要檢查數(shù)組中是否存在數(shù)字 451序调，則樸素算法必須從頭到尾迭代醉锅，對數(shù)組中的九個值進行總共九次檢查兔簇。但是发绢，由于數(shù)組已排序，因此可以可以立即通過檢查中間值刪除一半必要的比較：
func naiveContains(_ value: Int, in array: [Int]) -> Bool {
guard !array.isEmpty else { return false }
let middleIndex = array.count / 2
if value <= array[middleIndex] {
for index in 0...middleIndex {
if array[index] == value {
return true
}
}
} else {
for index in middleIndex..<array.count {
if array[index] == value {
return true
}
}
}
return false
}
上面的函數(shù)做了一個小而有意義的優(yōu)化垄琐，它只檢查數(shù)組的一半來得出結(jié)論边酒。
該算法首先檢查中間值以查看它與所需值的比較情況。如果中間值大于期望值狸窘，則算法不會費心查看數(shù)組右半部分的值墩朦；由于數(shù)組已排序，中間值右側(cè)的值只能變大翻擒。
在另一種情況下氓涣，如果中間值小于所需值，算法將不會查看數(shù)組的左側(cè)陋气。這是一個小而有意義的優(yōu)化劳吠，它將比較次數(shù)減少了一半。
如果我們可以在整個方法中重復進行此優(yōu)化會怎樣巩趁？后面“二分查找”中會有更加詳細的介紹痒玩。
可以重復丟棄一半所需比較的算法將具有對數(shù)時間復雜度。下圖描述了對數(shù)時間算法在輸入數(shù)據(jù)增加時的表現(xiàn)：
[圖片上傳失敗...(image-74aba9-1645529361634)]
隨著輸入數(shù)據(jù)的增加，執(zhí)行算法所需的時間以緩慢的速度增加蠢古。如果我們仔細觀察奴曙，可能會注意到該圖似乎表現(xiàn)出漸近行為。這可以通過考慮將需要進行的比較次數(shù)減半的影響來解釋草讶。
當我們的輸入大小為 100 時洽糟，將比較減半意味著您可以節(jié)省 50 次比較。如果輸入大小為 100,000堕战，則將比較減半意味著您可以節(jié)省 50,000 次比較脊框。你擁有的數(shù)據(jù)越多，減半效應的規(guī)模就越大践啄。因此浇雹，可以看到圖形似乎接近水平。
此類別中的算法很少屿讽，但在允許的情況下非常強大昭灵。對數(shù)時間復雜度的大 O 表示法是 O()。
是以 2 為底的對數(shù)伐谈、以 10 為底的對數(shù)還是自然對數(shù)欲诺？
在上面的例子中扶叉，log以2為底適用。然而，由于大 O 符號只關注性能的形狀抒寂，實際的基數(shù)并不重要。
擬線性時間
我們會遇到的另一個常見時間復雜度是擬線性時間嚣伐。擬線性時間算法的性能比線性時間差哭廉，但比二次時間好得多。它們是我們將要處理的最常見的算法之一距贷。擬線性時間算法的一個例子是 Swift 的排序方法柄冲。
擬線性時間復雜度的 Big-O 表示法是 O(n log n)，它是線性時間和對數(shù)時間的乘積忠蝗。因此现横，對數(shù)時間和線性時間之間的擬線性擬合；它比線性時間差阁最，但仍比我們接下來將看到的許多其他復雜性好戒祠。這是圖表：
[圖片上傳失敗...(image-f01e1a-1645529361634)]
擬線性時間復雜度與二次時間具有相似的曲線，但上升速度沒有那么快速种，因此對大型數(shù)據(jù)集更具彈性姜盈。
其他時間復雜度
到目前為止，我們遇到的五個時間復雜度就是上面遇到的那些哟旗。其他時間復雜度確實存在贩据，但遠不常見栋操。這些時間復雜度包括多項式時間、指數(shù)時間饱亮、階乘時間等矾芙。
需要注意的是，時間復雜度是對性能的高級概述近上，它并不能判斷算法的速度超出一般的排序方案剔宪。這意味著兩種算法可以具有相同的時間復雜度，但一種可能仍然比另一種快得多壹无。對于小型數(shù)據(jù)集葱绒，時間復雜度可能不是實際速度的準確度量。
比較時間復雜度
假設我們編寫了以下代碼來查找從 1 到 n 的數(shù)字之和斗锭。
func sumFromOne(upto n: Int) -> Int {
var result = 0 for i in 1...n {
result += i
}
return result
}
sumFromOne(upto: 10000)
代碼循環(huán) 10000 次并返回 50005000地淀。它是 O(n) 并且需要一點時間才能在操場上運行，因為它會計算循環(huán)并打印結(jié)果岖是。
下面是另一個版本：
func sumFromOne(upto n: Int) -> Int {
(1...n).reduce(0, +)
}
sumFromOne(upto: 10000)
在 Playground 中帮毁，這將運行得更快，因為它從標準庫中調(diào)用已編譯的代碼豺撑。但是烈疚，如果我們查看 reduce 的時間復雜度，您會發(fā)現(xiàn)它也是 O(n)聪轿，因為它調(diào)用了 n 次方法爷肝。它是同一個大 O，但具有更小的常量陆错，因為它是編譯代碼灯抛。
最終我們寫成下面這個樣子：
func sumFromOne(upto n: Int) -> Int {
(n + 1) * n / 2
}
sumFromOne(upto: 10000)
這個版本的函數(shù)使用了 高斯在小學時注意到的一個技巧。也就是說危号，我們可以使用簡單的算術計算總和牧愁。該算法的最終版本是 O(1) 并且很難被擊敗素邪。始終首選恒定時間算法外莲。如果你把這個版本放在一個循環(huán)中，你仍然會得到線性時間兔朦。之前的 O(n) 版本距離緩慢的二次時間只有一個外循環(huán)偷线。
空間復雜度
算法的時間復雜度可以幫助預測可擴展性，但它不是唯一的指標沽甥∩睿空間復雜度是算法運行所需資源的度量。對于計算機來說摆舟，算法的資源就是內(nèi)存亥曹。我們看以下代碼：
func printSorted(_ array: [Int]) {
let sorted = array.sorted()
for element in sorted {
print(element)
}
}
上面的函數(shù)將創(chuàng)建數(shù)組的排序副本并打印數(shù)組邓了。要計算空間復雜度，我們需要分析函數(shù)的內(nèi)存分配媳瞪。
由于array.sorted() 會產(chǎn)生一個與數(shù)組大小相同的全新數(shù)組骗炉，因此printSorted 的空間復雜度為O(n)。盡管此函數(shù)簡單而優(yōu)雅蛇受，但在某些情況下句葵，我們可能希望分配盡可能少的內(nèi)存。
我們可以將上述功能修改為以下內(nèi)容：
func printSorted(_ array: [Int]) {
// 1
guard !array.isEmpty else { return }
// 2
var currentCount = 0
var minValue = Int.min
// 3
for value in array {
if value == minValue {
print(value)
currentCount += 1
}
}
while currentCount < array.count {
// 4
var currentValue = array.max()!
for value in array {
if value < currentValue && value > minValue {
currentValue = value
}
}
// 5
for value in array {
if value == currentValue {
print(value)
currentCount += 1
}
}
// 6
minValue = currentValue
}
}
此實現(xiàn)尊重空間限制兢仰≌д桑總體目標是多次迭代數(shù)組，為每次迭代打印下一個最小值把将。這是這個算法正在做的事情：
檢查數(shù)組是否為空的情況轻专。如果是，則沒有可打印的內(nèi)容察蹲。
currentCount 記錄打印語句的數(shù)量铭若。 minValue 存儲最后打印的值。
算法首先打印出所有匹配 minValue 的值递览，并根據(jù)打印語句的數(shù)量更新 currentCount叼屠。
使用 while 循環(huán)，算法找到大于 minValue 的最小值并將其存儲在 currentValue 中绞铃。
然后算法在更新 currentCount 的同時打印數(shù)組中 currentValue 的所有值镜雨。
minValue 設置為 currentValue，因此下一次迭代將嘗試找到下一個最小值儿捧。
上述算法只分配內(nèi)存來跟蹤少數(shù)變量荚坞，因此空間復雜度為 O(1)。這與前面的函數(shù)相反菲盾，它分配整個數(shù)組來創(chuàng)建源數(shù)組的排序表示颓影。
其他標識
到目前為止，我們已經(jīng)使用大 O 表示法評估了算法懒鉴。這是迄今為止程序員評估時最常用的衡量標準诡挂。但是，也存在其他符號临谱。
Big Omega 表示法用于衡量算法的最佳情況運行時間璃俗。這不如大 O 有用，因為獲得最好的情況通常是站不住腳的悉默。
Big Theta 表示法用于測量具有相同最佳和最壞情況的算法的運行時間城豁。
Playground 基于行的執(zhí)行錯誤
本書廣泛使用Playground。在某些情況下抄课，可能會發(fā)現(xiàn) Xcode 13 錯誤地禁用了基于行的執(zhí)行唱星。在這些情況下雳旅，只需使用 Playground 窗口底部的執(zhí)行控制按鈕即可運行整個 Playground。
關鍵點
? 時間復雜度是隨著輸入大小的增加運行算法所需時間的度量间聊。
? 我們應該了解常數(shù)時間岭辣、對數(shù)時間、線性時間甸饱、擬線性時間和二次時間沦童，并能夠按成本對它們進行排序。
? 空間復雜度是算法運行所需資源的度量叹话。
? 大O 符號用于表示時間和空間復雜度的一般形式偷遗。
? 時間和空間復雜度是可擴展性的高級度量；它們不測量算法本身的實際速度驼壶。
? 對于小型數(shù)據(jù)集氏豌，時間復雜度通常無關緊要。例如热凹，當 n 很小時泵喘，擬線性算法可能比二次算法慢。
| 上一章 | 目錄 | 下一章 |
|---|
