復雜度分析是估算算法執行效率的方法，公式O(f(n))表示算法的復雜度，此方法即為大O復雜度表示法O(f(n))中n表示數據規模，f(n)表示運行算法所需要執行的指令數。

大O復雜度表示法

下面的代碼非常簡單,求 1,2,3…n 的累加和，我們要做的是估算它的執行效率。

def?calc(n):????sum_?=?0????for?i?in?range(1，n+1):????????sum_?=?sum_?+?i????return?sum_

假設每行代碼執行的時間都一樣為t，執行第2行代碼需要時間t，第3,4行代碼運行了n遍，需要的時間為2n*t，這段代碼總執行時間為(2n+1)* t

結論：代碼執行的總時間T(n)與每行代碼的執行次數成正比

看下面的代碼，估算該段代碼的執行時間:

def?calc(n):????sum_?=?0????for?i?in?range(n):????????for?j?in?range(n):????????????sum_?=?sum_?+?i*j????return?sum_

同樣假設每行代碼執行的時間都一樣為t：執行第2行代碼需要時間t，第3行代碼運行了n遍，需要時間為n*t，第4、5行代碼運行了n2次，需要時間為2n2 * t，執行所有代碼的總時間為 (2n2 + n + 1)* t。

結論：代碼執行的總時間T(n)與每行代碼的執行次數成正比。

用O(f(n))來表示算法復雜度：

def?calc(n):????sum_?=?0????for?i?in?range(1，n+1):????????sum_?=?sum_?+?i????return?sum_

def?calc(n):????sum_?=?0????for?i?in?range(n):????????for?j?in?range(n):????????????sum_?=?sum_?+?i*j????return?sum_

T(n) = O(f(n)) , O表示代碼的執行時間T(n) 與 f(n)表達式成比例。

大O復雜度表示法：上面例子中的T(n) = O(2n+1), 另一個 T(n) = O(2n2 + n + 1)。大O時間復雜度并不表示代碼真正的執行時間，而是表示代碼執行時間隨數據規模增長的變化趨勢，也叫作漸進時間復雜度(asymptotic time complexity)，簡稱時間復雜度。

當數據量特別大， 也就是n的取值很大的時候，大O表示法中低階、常量、系數三部分并不會左右增長趨勢，可以忽略。

def?calc(n):????sum_?=?0????for?i?in?range(1，n+1):????????sum_?=?sum_?+?i????return?sum_

def?calc(n):????sum_?=?0????for?i?in?range(n):????????for?j?in?range(n):????????????sum_?=?sum_?+?i*j????return?sum_

上面例子中的T(n) = O(2n+1), 另一個 T(n) = O(2n2 + n + 1)，用大O表示法表示上面兩段代碼的時間復雜度，可以記為O(n)，O(n2)。

算法A： O(n) 執行指令，10000*n

def?calc(n):????sum_?=?0????for?i?in?range(1，n+1):????????sum_?=?sum_?+?I??"""??此處省略n行...?...??"""????return?sum_

算法B： O(n2) 執行指令數，10*n2

對比上面兩個算法，當 n = 10, n=100 時， 算法B執行的速度更快，n = 1000 時兩者速度相當

n = 104 , n = 105, n = 106 ，算法A執行的速度更快的

隨著數據規模的進一步增大， 這個差距會越來越大

時間復雜度分析

如何分析一段代碼的時間復雜度?

在分析一個算法、一段代碼的時間復雜度時，只關注循環執行次數最多的那一段代碼就可以了。

def?calc(n):????sum_?=?0????for?i?in?range(n):????????for?j?in?range(n):????????????sum_?=?sum_?+?i*j????return?sum_

上面的代碼中，我們只需要關注內層for循環的時間復雜度就可以了，內層for循環的兩行代碼被執行了n2次，所以總的時間復雜度就是O(n2)

總復雜度等于量級最大的那段代碼的復雜度

def?calc(n):sum_?=?0????for?i?in?range(1，n+1):????????sum_?=?sum_?+?i????sum_1?=?0????for?i?in?range(1,n+1):????????for?j?in?range(n):????????????sum_1?=?sum_1?+?i*j????return?sum_+sum_1

上面的代碼分為兩部分，分別是求 sum_、sum_1，計算sum_部分的代碼段時間復雜度O(n)，計算sum_1部分的代碼段時間復雜度為O(n2) ，總的時間復雜度由復雜度最大的部分決定, 所以上面代碼復雜度為O(n2)。

嵌套代碼的復雜度等于嵌套內外代碼復雜度的乘積

def?fn(n):????sum_?=?0????for?i?in?range(n+1):????????sum_?=?sum_?+?i????return?sum_def?calc(n):????sum_?=?0????for?i?in?range(n+1):????????sum_?=?sum_?+?fn(i)????return?sum_

上面的代碼中第二個函數調用了第一個函數, 如果把fn函數調用當作一個普通操作, 那么第二個函數的時間復雜度為O(n) Fn函數的時間復雜度為O(n)，那么函數整體的時間復雜度為O(n*n) = O(n2)。

當兩段代碼的數據規模不同時，不能省略復雜度低的部分

def?calc(n):sum_?=?0????for?i?in?range(1，n+1):????????sum_?=?sum_?+?i????sum_1?=?0????for?i?in?range(1,m+1):????????for?j?in?range(m):????????????sum_1?=?sum_1?+?i*j????return?sum_+sum_1

上面的代碼分為兩部分，分別是求 sum_、sum_1，計算sum_部分的代碼段時間復雜度O(n)，計算sum_1部分的代碼段時間復雜度為O(m2) ，總的時間復雜度由復雜度最大的部分決定, 所以上面代碼復雜度為O(m2+n)