在實現(xiàn)算法的時候，通常會從兩方面考慮算法的復(fù)雜度，即時間復(fù)雜度和空間復(fù)雜度。顧名思義，時間復(fù)雜度用于度量算法的計算工作量，空間復(fù)雜度用于度量算法占用的內(nèi)存空間。
本文將從時間復(fù)雜度的概念出發(fā)，結(jié)合實際代碼示例分析算法的時間復(fù)雜度。
漸進(jìn)時間復(fù)雜度
時間復(fù)雜度是算法運(yùn)算所消耗的時間，因為不同大小的輸入數(shù)據(jù)，算法處理所要消耗的時間是不同的，因此評估一個算運(yùn)行時間是比較困難的，所以通常關(guān)注的是時間頻度，即算法運(yùn)行計算操作的次數(shù)，記為T(n)，其中n稱為問題的規(guī)模。
同樣，因為n是一個變量，n發(fā)生變化時，時間頻度T(n) 也在發(fā)生變化，我們稱時間復(fù)雜度的極限情形稱為算法的漸近時間復(fù)雜度，記為O(n)，不包含函數(shù)的低階和首項系數(shù)。
我們以如下 例子來解釋一下：
如上例子中，我們根據(jù)代碼上執(zhí)行的平均時間假設(shè)，計算 run_time(n) 函數(shù)的時間復(fù)雜度，如下：
上述時間復(fù)雜度計算公式T(n) ，是我們對函數(shù) run_time(n) 進(jìn)行的時間復(fù)雜度的估算。當(dāng)n 值非常大的時候，T(n)函數(shù)中常數(shù)項 time0 以及n的系數(shù) (time1+time2+time3+time4) 對n的影響也可以忽略不計了，因此這里函數(shù)run_time(n) 的時間復(fù)雜度我們可以表示為 O(n)。
因為我們計算的是極限狀態(tài)下（如，n非常大）的時間復(fù)雜度，因此其中存在以下兩種特性：
- 低階項相對于高階項產(chǎn)生的影響很小，可以忽略不計。
- 最高項系數(shù)對最高項的影響也很小，可以忽略不計。
根據(jù)上述兩種特性，時間復(fù)雜度的計算方法：
1.只取最高階項，去掉低階項。
2.去掉最高項的系數(shù)。
3.針對常數(shù)階，取時間復(fù)雜度為O(1)。
我們通過下面例子理解一下常見的時間復(fù)雜度，如下：
時間復(fù)雜度：常數(shù)階 O(1)
時間復(fù)雜度：線性階 O(n)
時間復(fù)雜度：線性階 O(n)
時間復(fù)雜度：平方階 O(n^2)
時間復(fù)雜度：平方階 O(n^2)
時間復(fù)雜度：平方階 O(n^2)
時間復(fù)雜度：立方階 O(n^3)
時間復(fù)雜度：對數(shù)階 O(logn)
隨著問題規(guī)模n的不斷增大，上述時間復(fù)雜度不斷增大，算法的執(zhí)行效率越低，時間復(fù)雜度排序如下：
練習(xí)一下
如下count_sort 函數(shù)實現(xiàn)了計數(shù)排序，列表中的數(shù)范圍都在0到100之間，列表長度大約為100萬。
如上count_sort 函數(shù)的 空間復(fù)雜度為 O(n)，公式如下：
