從架構(gòu)的角度來(lái)看，可擴(kuò)展性是指更改 app 的難易程度。從數(shù)據(jù)庫(kù)的角度來(lái)看，可伸縮性是指在數(shù)據(jù)庫(kù)中保存或檢索數(shù)據(jù)所需的時(shí)間快慢程度。

對(duì)于算法，可擴(kuò)展性是指隨著輸入大小的增加，算法在執(zhí)行時(shí)間和內(nèi)存使用方面的表現(xiàn)情況。

當(dāng)處理少量數(shù)據(jù)時(shí)，不好的算法（時(shí)間、空間代價(jià)昂貴）可能仍然讓人感覺(jué)執(zhí)行速度很快。然而，隨著數(shù)據(jù)量的增加，昂貴的算法將會(huì)變得很糟糕。只是它會(huì)變得多糟糕呢？如何量化這個(gè)糟糕程度是我們需要了解的一項(xiàng)重要技能。

時(shí)間復(fù)雜度

對(duì)于少量數(shù)據(jù)，由于現(xiàn)代硬件的速度，即使是最昂貴的算法也可能看起來(lái)執(zhí)行速度很快。然而，隨著數(shù)據(jù)的增加，昂貴算法的成本將變得越來(lái)越明顯。時(shí)間復(fù)雜度是隨著輸入大小的增加運(yùn)行算法所需時(shí)間的度量。

恒定時(shí)間

恒定時(shí)間算法是指無(wú)論輸入大小怎樣，都具有相同運(yùn)行時(shí)間的算法。

我們來(lái)看以下代碼：

func checkFirst(names: [String]) {
  if let first = names.first {
    print(first)
  } else {
    print("no names")
  }
}

names 數(shù)組的大小對(duì)該函數(shù)的運(yùn)行時(shí)間沒(méi)有影響。無(wú)論數(shù)組輸入是 10條數(shù)據(jù)還是 1000 萬(wàn)條數(shù)據(jù)，此函數(shù)都只檢查數(shù)組的第一個(gè)元素。 這是一個(gè)簡(jiǎn)單的時(shí)間復(fù)雜度示例：

隨著輸入數(shù)據(jù)的增加，算法所花費(fèi)的時(shí)間不會(huì)改變。

為簡(jiǎn)潔起見(jiàn)，程序員使用一種稱為 Big O 表示法來(lái)表示各種時(shí)間復(fù)雜度的大小。常數(shù)時(shí)間的大 O 表示法是 O(1)。

Linear time

再看以下代碼段：

func printNames(names: [String]) {
  for name in names {
    print(name)
  }
}

此函數(shù)打印出字符串?dāng)?shù)組中的所有名稱。隨著輸入數(shù)組大小的增加，for 循環(huán)的迭代次數(shù)也會(huì)增加相同的數(shù)量。

這種行為稱為線性時(shí)間復(fù)雜度：

線性時(shí)間復(fù)雜度通常是最容易理解的。隨著數(shù)據(jù)量的增加，運(yùn)行時(shí)間也會(huì)增加相同的量。線性時(shí)間的大 O 表示法是 O(n)。

如果一個(gè)函數(shù)有兩個(gè)循環(huán)外加調(diào)用六次 O(1) 方法，時(shí)間復(fù)雜度是 O(2n + 6) 嗎？
時(shí)間復(fù)雜度僅給出了性能的高級(jí)形式，因此發(fā)生一定次數(shù)的循環(huán)并不是時(shí)間復(fù)雜度的一部分。也即是說(shuō)，上面的時(shí)間復(fù)雜度是 O(n) 而非 O(2n + 6) 。
當(dāng)然，優(yōu)化絕對(duì)效率也很重要。比如，算法的 GPU 優(yōu)化版本的運(yùn)行速度可能比原始 CPU 版本快 100 倍，同時(shí)保持時(shí)間復(fù)雜度為 O(n)。雖然在計(jì)算時(shí)間復(fù)雜度時(shí)我們會(huì)忽略這種優(yōu)化，但像這樣的加速其實(shí)也是很重要的。

二次方時(shí)間（Quadratic time ）

這種時(shí)間復(fù)雜度算法，其時(shí)間與輸入大小的平方成正比。 考慮以下代碼：

func printNames(names: [String]) {
  for _ in names {
    for name in names {
      print(name)
    }
  }
}

該函數(shù)打印出數(shù)組中的所有名稱。 如果有一個(gè)包含十條數(shù)據(jù)的數(shù)組，它將十次打印十個(gè)名稱的完整列表，即打印 100 個(gè)語(yǔ)句。

如果將輸入大小增加 1，它將打印 11 * 11 = 121 個(gè)語(yǔ)句。這種增速與之前線性時(shí)間運(yùn)行的函數(shù)不同，n squared 算法會(huì)隨著數(shù)據(jù)量 n 的增加而呈指數(shù)增長(zhǎng)。

下圖說(shuō)明了這種行為：

當(dāng) n 足夠大時(shí)，線性增長(zhǎng)執(zhí)行速度遠(yuǎn)快于指數(shù)增長(zhǎng)執(zhí)行速度。

隨著輸入數(shù)據(jù)大小的增加，算法運(yùn)行所需的時(shí)間會(huì)急劇增加。 因此，n 平方算法在規(guī)模上表現(xiàn)不佳。

二次時(shí)間的大 O 表示法是 O(n2)。

對(duì)數(shù)時(shí)間（Logarithmic time）

到目前為止，我們已經(jīng)了解了線性和二次時(shí)間復(fù)雜度，其中輸入的每個(gè)元素至少檢查一次。 但是，在某些情況下，只需要檢查輸入的子集，從而加快運(yùn)行時(shí)間。

比如，如果有一個(gè)已排序的整數(shù)數(shù)組，那么查找特定值是否存在捷徑呢？

一個(gè)笨法是從頭到尾逐個(gè)檢查數(shù)組，直到找到要找的值。因?yàn)樾枰獧z查每個(gè)元素一次，時(shí)間復(fù)雜度為 O(n) 。

線性搜索雖然表現(xiàn)不錯(cuò)，但我們還可以做得更好。由于輸入數(shù)組已排序，因此我們可以進(jìn)行如下優(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，樸素算法從頭到尾迭代，對(duì)數(shù)組中的九個(gè)值進(jìn)行總共九次檢查。 但是，由于數(shù)組已排序，其實(shí)我們可以通過(guò)檢查中間值立即刪除一半沒(méi)必要的比較：

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ù)做了一個(gè)小優(yōu)化，它只需檢查數(shù)組的一半就能得出結(jié)論。

該算法首先檢查中間值，如果中間值大于期望值，則直接舍棄中間值以后的部分，因?yàn)閿?shù)組是升序的，期望值只能在中間值之前的那一部分。

同樣，如果中間值小于期望值，算法將不會(huì)再查看數(shù)組的左側(cè)了。

這種二分查找方式，具有對(duì)數(shù)時(shí)間復(fù)雜度。下圖描述了對(duì)數(shù)時(shí)間算法隨輸入數(shù)據(jù)增加時(shí)的表現(xiàn)：

隨著輸入數(shù)據(jù)的增加，執(zhí)行算法所需的時(shí)間以緩慢的速度增加。

當(dāng)輸入大小為 100 時(shí)，將比較減半意味著可以節(jié)省 50 次比較。如果輸入大小為 100000，則將比較減半意味著您可以節(jié)省 50000 次比較。要比較的的數(shù)據(jù)越多，減半效應(yīng)效果越明顯。

對(duì)數(shù)時(shí)間復(fù)雜度的大 O 表示法是 O(log n)。

擬線性時(shí)間（Quasilinear time）

另一個(gè)常見(jiàn)時(shí)間復(fù)雜度是擬線性時(shí)間。擬線性時(shí)間算法的性能比線性時(shí)間差，但比二次時(shí)間好得多。它是我們今后將要處理的最常見(jiàn)的算法之一。擬線性時(shí)間算法的一個(gè)例子是 Swift 的排序方法。

擬線性時(shí)間復(fù)雜度的 Big-O 表示法是 O(n log n)，它是線性時(shí)間和對(duì)數(shù)時(shí)間的乘積。它比線性時(shí)間差，但仍比許多其它算法的復(fù)雜性好，圖表：

擬線性時(shí)間復(fù)雜度與二次時(shí)間復(fù)雜度具有相似的曲線，但上升速度沒(méi)有那么快，因此對(duì)大型數(shù)據(jù)集更具彈性。

其它時(shí)間復(fù)雜度

除了上面幾種時(shí)間復(fù)雜度，其它不常見(jiàn)的時(shí)間復(fù)雜度也存在，比如多項(xiàng)式時(shí)間、指數(shù)時(shí)間、階乘時(shí)間等。

需要注意的是，時(shí)間復(fù)雜度是對(duì)性能的高級(jí)概述，它并不能判斷算法的速度超出一般的排序方案。這意味著兩種算法可以具有相同的時(shí)間復(fù)雜度，但一種可能仍然比另一種快得多。對(duì)于小型數(shù)據(jù)集，時(shí)間復(fù)雜度可能不是實(shí)際速度的準(zhǔn)確度量。

例如，如果數(shù)據(jù)集很小，則插入排序等二次算法可以比合并排序等擬線性算法更快。這是因?yàn)椴迦肱判虿恍枰峙漕~外的內(nèi)存來(lái)執(zhí)行算法，而歸并排序需要分配多個(gè)數(shù)組。對(duì)于小型數(shù)據(jù)集，內(nèi)存分配相對(duì)于算法需要接觸的元素?cái)?shù)量而言可能是更昂貴的。

比較時(shí)間復(fù)雜度

看以下代碼，來(lái)查找從 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) 并且需要一點(diǎn)時(shí)間才能在 playground 上運(yùn)行，因?yàn)樗鼤?huì)計(jì)算循環(huán)并打印結(jié)果。

再看另一個(gè)版本：

func sumFromOne(upto n: Int) -> Int {
  (1...n).reduce(0, +)
}
sumFromOne(upto: 10000)

在 Playground 中，這將運(yùn)行得更快，因?yàn)樗鼜臉?biāo)準(zhǔn)庫(kù)中調(diào)用已編譯的代碼。 但是，如果查看 reduce 的時(shí)間復(fù)雜度，您會(huì)發(fā)現(xiàn)它也是 O(n)，因?yàn)樗{(diào)用了 + 方法 n 次。它是同一個(gè)大 O，但具有更小的常量，因?yàn)樗且丫幾g代碼（compiled code）。

最后，還可以這樣寫(xiě)：

func sumFromOne(upto n: Int) -> Int {
  (n + 1) * n / 2
}
sumFromOne(upto: 10000)

可以使用簡(jiǎn)單的算術(shù)計(jì)算總和。該算法的最終版本是 O(1) 并且執(zhí)行速度很難被擊敗。

空間復(fù)雜度（Space complexity）

算法的時(shí)間復(fù)雜度可以幫助預(yù)測(cè)其可擴(kuò)展性，但它不是唯一的指標(biāo)?？臻g復(fù)雜度是算法運(yùn)行所需資源的度量。對(duì)于計(jì)算機(jī)來(lái)說(shuō)，算法的資源就是內(nèi)存。

我們來(lái)看以下代碼：

func printSorted(_ array: [Int]) {
  let sorted = array.sorted()
  for element in sorted {
    print(element)
  }
}

上面的 printSorted 方法將創(chuàng)建 array 的排序副本，然后遍歷打印該排序數(shù)組的值。要計(jì)算空間復(fù)雜度，需要分析函數(shù)的內(nèi)存分配。

由于 array.sorted() 會(huì)產(chǎn)生一個(gè)與數(shù)組大小相同的全新數(shù)組，因此 printSorted 的空間復(fù)雜度為 O(n)。盡管此函數(shù)簡(jiǎn)單而優(yōu)雅，但在某些情況下，我們可能希望分配盡可能少的內(nèi)存。

因?yàn)榭梢詫⑸鲜龇椒▋?yōu)化如下：

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
  }
}

逐行解釋：

1. 檢查數(shù)組是否為空的情況。如果是，則沒(méi)有可打印的內(nèi)容。
2. currentCount 記錄打印語(yǔ)句的數(shù)量。minValue 存儲(chǔ)最后打印的值。
3. 算法首先打印出所有匹配 minValue 的值，并根據(jù)打印語(yǔ)句的數(shù)量更新 currentCount。
4. 使用 while 循環(huán)，算法找到大于 minValue 的最小值并將其存儲(chǔ)在 currentValue 中。
5. 然后算法在更新 currentCount 的同時(shí)打印數(shù)組中 currentValue 的所有值。
6. minValue 設(shè)置為 currentValue，下一次迭代將嘗試找到下一個(gè)最小值。

上述算法只分配內(nèi)存來(lái)跟蹤少數(shù)變量，因此空間復(fù)雜度為 O(1)。這與前面的函數(shù)相反，它分配整個(gè)數(shù)組來(lái)創(chuàng)建源數(shù)組的排序表示。

其它符號(hào)（Other notations）

目前為止，我們已經(jīng)使用大 O 表示法評(píng)估了算法。這是迄今為止程序員評(píng)估時(shí)最常用的衡量標(biāo)準(zhǔn)。但是，除此還存在其它表示符號(hào)。

Big Omega 表示法用于衡量算法的最佳情況運(yùn)行時(shí)間。

Big Theta 表示法用于測(cè)量具有相同最佳和最壞情況的算法的運(yùn)行時(shí)間。

本節(jié)關(guān)鍵點(diǎn)

時(shí)間復(fù)雜度是隨著輸入大小的增加運(yùn)行算法所需時(shí)間的度量。

• 應(yīng)該了解常數(shù)時(shí)間、對(duì)數(shù)時(shí)間、線性時(shí)間、擬線性時(shí)間和二次時(shí)間，并能夠按成本對(duì)其進(jìn)行排序。
• 空間復(fù)雜度是算法運(yùn)行所需資源的度量。
• 大 O 表示法用于表示時(shí)間和空間復(fù)雜度的一般形式。
• 時(shí)間和空間復(fù)雜度是可擴(kuò)展性的高級(jí)度量，他們不測(cè)量算法本身的實(shí)際速度。
• 對(duì)于小型數(shù)據(jù)集，時(shí)間復(fù)雜度通常無(wú)關(guān)緊要。 例如，當(dāng) n 很小時(shí)，擬線性算法可能比二次算法慢。