算法的復(fù)雜度分為兩大類： 時(shí)間復(fù)雜度、空間復(fù)雜度谚鄙。時(shí)間復(fù)雜度指的是該算法完成需要執(zhí)行運(yùn)算的次數(shù)各拷；空間復(fù)雜度指執(zhí)行算法需要消耗的內(nèi)存空間大小。
對(duì)一個(gè)算法而言闷营，時(shí)間復(fù)雜度 和 空間復(fù)雜度 都是越小越好撤逢。因?yàn)閮?yōu)秀算法的核心是通過最短的時(shí)間和最小的空間完成指定的目標(biāo)運(yùn)算。
這篇文章粮坞，將介紹算法的時(shí)間復(fù)雜度和空間復(fù)雜度的計(jì)算方式蚊荣，內(nèi)容很基礎(chǔ)，大神繞了吧莫杈。
時(shí)間復(fù)雜度的計(jì)算
通常互例，我們不會(huì)直接將算法執(zhí)行的總次數(shù)作為它的時(shí)間復(fù)雜度，因?yàn)轶菽郑⒉皇敲恳粋€(gè)算法都能算出一個(gè)確切的總執(zhí)行次數(shù)媳叨，根據(jù)不同的計(jì)算對(duì)象腥光，相同的算法的總執(zhí)行次數(shù)是不固定的，那么計(jì)算執(zhí)行的總次數(shù)意義不大糊秆。相反武福，定性的分析同一個(gè)算法對(duì)規(guī)模增加的影響更有意義：我們只想知道，隨著規(guī)模 N 的增長(zhǎng)痘番，算法的執(zhí)行次數(shù)的增長(zhǎng)曲線（對(duì)數(shù)增長(zhǎng)捉片？ 常數(shù)增長(zhǎng)或者是指數(shù)增長(zhǎng)？）是怎樣的汞舱，這個(gè)增長(zhǎng)能夠給算法的性能做一個(gè)定性的分析伍纫，從而判斷一個(gè)算法的優(yōu)劣。一般我們會(huì)使用大 O 記錄昂芜。下面介紹幾種常見的大 O 記錄時(shí)間復(fù)雜度的例子莹规。
常見的幾個(gè)時(shí)間復(fù)雜度算法
O(1)：表示的是該算法的執(zhí)行次數(shù)和規(guī)模 N 無(wú)關(guān)，永遠(yuǎn)都會(huì)執(zhí)行某個(gè)常數(shù)次的元素泌神。
比如高斯函數(shù)：
// 計(jì)算 1 + 2 + 3 + 4 + ...... + 100 + ... + N
// 規(guī)模為 N
func addTo(_ n: Int) {
sum = (1 + n) * n/2; /* 執(zhí)行1次 */
printf("%d", sum); /* 執(zhí)行1次 */
}
這個(gè)高斯函數(shù)永遠(yuǎn)都只會(huì)執(zhí)行2次良漱，不管N有多大。也即是欢际，算法永遠(yuǎn)執(zhí)行一個(gè)常數(shù)次數(shù)债热，這種時(shí)間復(fù)雜度，用大O表示為O(1)幼苛。
O(LogN)：對(duì)數(shù)遞增，表示隨著規(guī)模的增大焕刮，執(zhí)行次數(shù)按照規(guī)模N的對(duì)數(shù)函數(shù)遞增舶沿。
比如： 常見的對(duì)分查找。
// 給定一個(gè)有序的整型數(shù)組 Arr, 從中隨機(jī)挑選出一個(gè)元素 X配并，在數(shù)組中找到 X 的元素的下標(biāo)值
func findElmentIndex(_ arr: [Int], _ x: Int ) -> Int {
var low = 0, hight = arr.count, index = (low + hight)/2
while x != arr[index] {
if x > arr[index] {
low = index
}else if x < arr[index]{
hight = index
}else{
return index
}
index = (low + hight)/2
}
return index
}
這里并不好算出算法的實(shí)際次數(shù)（根據(jù)X數(shù)字的位置會(huì)不斷改變總執(zhí)行次數(shù)）括荡。但是我們可以給出一個(gè)大致的范圍，假如 X 剛好在數(shù)組的中間溉旋，那么一次就可以找到X的位置畸冲。如果X在最前面，也就是index = 0的位置,那么需要次數(shù)最多观腊，為 logN邑闲。這里使用大 O 記錄就是 O（logN）。
O(N)：表示算法的執(zhí)行次數(shù)以 N 線性增長(zhǎng)梧油。
比如苫耸，累加函數(shù)。
// 計(jì)算 1 + 2 + 3 + 4 + ...... + 100 + ... + N
// 除了使用高斯函數(shù)計(jì)算儡陨，我們也可以使用逐個(gè)相加的方法
func addTo(_ n: Int) -> {
var sum = 0
for i in 0..<n+1{
sum += i
}
return sum
}
這個(gè)算法的執(zhí)行次數(shù)很明朗褪子，就是N次量淌。因?yàn)殡S著規(guī)模 N 線性增長(zhǎng)，因此計(jì)作 O（N）嫌褪。
其余常見的還有 O（N^2）呀枢、 O（N^3）。以及 O（2^n）笼痛、O（N!）裙秋、 O（N^N）這些不常用到的，因?yàn)樵脚旁诤竺鏁r(shí)間復(fù)雜度越大晃痴，我們一般很少用到残吩。
計(jì)算時(shí)間復(fù)雜度的大 O 的方法
如何給一個(gè)算法定義大 O 呢？其實(shí)很簡(jiǎn)單倘核，只需要遵循一個(gè)規(guī)律就行泣侮。
假若給定一個(gè)函數(shù)，內(nèi)部是一個(gè)累加算法紧唱，我們來(lái)想計(jì)算它的時(shí)間復(fù)雜度活尊，可以通過下面的順序來(lái)操作：
- 計(jì)算算法執(zhí)行的總時(shí)間
- 用常數(shù)1取代運(yùn)行時(shí)間中的所有加法常數(shù)。
- 在修改后的運(yùn)行次數(shù)函數(shù)中漏益，只保留最髙階項(xiàng)蛹锰。
- 如果最高階項(xiàng)存在且不是1,則去除與這個(gè)項(xiàng)相乘的常數(shù)。
首先看函數(shù)原型：
func addTo(_ n: Int) -> Int {
var sum = 0
for i in 0..<n {
sum += i // 執(zhí)行n次
}
return sum
}
- 很容易計(jì)算得出绰疤，總次數(shù)為 n
- 沒有常數(shù)
- 本身只有一項(xiàng)铜犬，最高階即為本身
- 最高階存在為1， 不需要做其他的處理
這個(gè)算法的大 O 記做： O（n）轻庆，也就是線性執(zhí)行癣猾。這個(gè)例子還不夠體現(xiàn)上面四個(gè)步驟的所有流程。
再來(lái)看一個(gè)經(jīng)常用到的：
// 冒泡排序
func sortByBubble<T: Comparable>(_ arr: [T]) -> [T] {
var mutArr = arr; // 1次
for i in 0..<mutArr.count {
// n 次
for j in (i+1)..<mutArr.count {
if mutArr[i] > mutArr[j] {
(mutArr[i],mutArr[j]) = (mutArr[j],mutArr[i]) // n-1 余爆、 n -2 .... 1
}
}
}
return mutArr
}
最快的時(shí)間： 在數(shù)組本身已經(jīng)排好序的情況纷宇，為n次。
最慢的時(shí)間： 完全倒序的情況下蛾方，執(zhí)行 n-1 + n-2 + .... + 1 = n^2/2 + n/2 （注意這里是交換兩個(gè)元素的值像捶，很多編程語(yǔ)言中應(yīng)該為3次，也就是這里的值應(yīng)該乘以3）
我們以最壞的情況計(jì)算大 O：
1 + n^2/2 + n/2 ---- > n^2/2 + n/2 + 1
首先去除常數(shù)項(xiàng)： ----> n^2/2 + n/2
只保留最高次冪項(xiàng)： ----> n^2/2
去除最高次冪的常數(shù)： ----> n^2
所以桩砰，冒泡排序的大 O 為：O（n^2）
空間復(fù)雜度的計(jì)算
一個(gè)程序的空間復(fù)雜度是指運(yùn)行完一個(gè)程序所需內(nèi)存的大小拓春。利用程序的空間復(fù)雜度，可以對(duì)程序的運(yùn)行所需要的內(nèi)存多少有個(gè)預(yù)先估計(jì)亚隅。一個(gè)程序執(zhí)行時(shí)除了需要存儲(chǔ)空間和存儲(chǔ)本身所使用的指令邮利、常數(shù)淘衙、變量和輸入數(shù)據(jù)外丘薛，還需要一些對(duì)數(shù)據(jù)進(jìn)行操作的工作單元和存儲(chǔ)一些為現(xiàn)實(shí)計(jì)算所需信息的輔助空間。程序執(zhí)行時(shí)所需存儲(chǔ)空間包括以下兩部分渐尿。
所以，相對(duì)來(lái)說(shuō)矾瑰，空間復(fù)雜度經(jīng)常不會(huì)太大砖茸，如果太大，很可能算法會(huì)執(zhí)行不下去殴穴。一般的空間復(fù)雜度為 O （1）凉夯，O（n）也很常見，另外像涉及到遞歸算法中采幌，空間復(fù)雜度可能達(dá)到O（n^2)劲够。
空間復(fù)雜的大 O 計(jì)算其實(shí)和時(shí)間復(fù)雜度類似。但是還需要根據(jù)實(shí)際情況來(lái)算休傍，任何脫離實(shí)際的算法都毫無(wú)意義征绎。
排序算法的穩(wěn)定性
排序算法的穩(wěn)定性指的是同一個(gè)算法，相同大小的結(jié)果在每一次的算法中的順序都是一樣的磨取。我們前面舉例的冒泡排序就是如此人柿，就算其中有大小相同的值，但是排序在前面的值忙厌，排序后還是在前凫岖。
對(duì)于不穩(wěn)定的排序算法，只要舉出一個(gè)實(shí)例逢净，即可說(shuō)明它的不穩(wěn)定性哥放；而對(duì)于穩(wěn)定的排序算法，必須對(duì)算法進(jìn)行分析從而得到穩(wěn)定的特性爹土。需要注意的是甥雕，排序算法是否為穩(wěn)定的是由具體算法決定的，不穩(wěn)定的算法在某種條件下可以變?yōu)榉€(wěn)定的算法着饥，而穩(wěn)定的算法在某種條件下也可以變?yōu)椴环€(wěn)定的算法。
比如還是之前的冒泡排序惰赋，改成下面這樣就變成了不穩(wěn)定的排序算法：
// 冒泡排序
func sortByBubble<T: Comparable>(_ arr: [T]) -> [T] {
var mutArr = arr;
for i in 0..<mutArr.count {
for j in (i+1)..<mutArr.count {
if mutArr[i] >= mutArr[j] { // 這里的條件進(jìn)行了更改
(mutArr[i],mutArr[j]) = (mutArr[j],mutArr[i])
}
}
}
print(mutArr)
return mutArr
}
這個(gè)算法最終變成了不穩(wěn)定的排序算法宰掉。
