演算法筆記（八）：複雜度分析（二）

#感興趣的可以去訂閱極客時間前谷歌工程師的專欄：數據結構與演算法之美，個人覺得寫的很不錯。這裡只是我自己做的一個簡單的筆記

（一） 對數階時間複雜度

1 def tset(n):
2     i = 1
3     while i <= n:
4         i = i*2

    上面這段代碼，i 從1開始，迴圈一次乘於2，當大於n時，迴圈結束，我們可以得到2^x = n。要計算上面這段代碼的時間複雜度，求解x的值就行了，根據數學基礎中和對數相關的計算，可以得到x = log₂n = logn,所以這段代碼的時間複雜度就是O（logn）。

        將代碼修改成下麵這樣，很容易計算出，代碼的時間複雜度是O（log₃n）。

1 def tset(n):
2     i = 1
3     while i <= n:
4         i = i*3

        在對數中log₃n = log₃2*log₂n,所以O（log₃n） = O（log₃2*log₂n） = O（C*log₂n），其中C是常量，根據漸進符號的定義，計算時間複雜度時，我們可以忽略常量，所以上面這段代碼的時間複雜度也是O（logn），同理，所有對數階時間複雜度的表示中，可以統一表示為O（logn）。

   如果一段代碼的時間複雜度是O（logn），如果迴圈運行n次，那麼時間複雜度就是O（nlogn）。

（二） 空間複雜度

  下麵這段代碼，和分析時間複雜度一樣，因為只有第三行代碼創建了一個大小為n的數組，其他不是常量就是不占用記憶體空間，所以這段代碼的空間複雜度是O（n）

1 def test1(n):
2     a = 0
3     arr = numpy.arange(n)
4     for i in range(n):
5         arr[i] = i*i
6     return arr

（三）  最好、最壞、平均時間複雜度

 這裡我們用之前線性查找的例子：

1 import numpy as np
2 
3 #找到結果，返回索引，否則返回None
4 def search(array,key):
5     for j in range(len(array)):
6         if array[j] == key:
7             return j
8     return None

最好時間複雜度： 如果第一個元素就是我們要查找的元素，那麼代碼的時間複雜度就是O（1）

最壞時間複雜度：如果最後一個元素才是我們要查找的元素，或者數組中根本就沒有我們要查找的元素，那麼代碼的時間複雜度就是O（n）

平均時間複雜度：查找元素在是否在數組中有2種情況，在數組中（0...n-1）和不在數組中，那麼總共就有 n+1種情況，我們將需要查找的元素（可能運行的次數，第n個元素和不在數組中運行次數都是n次）相加除以n+1就可以得到代碼的時間複雜度。

（1+2+3...+n+n）/ （n+1） = （n*(n+2)）/2（n+1），那麼平均時間複雜度為O（n）。

1+2+3...+n  可以推導出公式 n(n+1)/2，詳細推導過程不明白的可以自己網上查查資料。