時間複雜度和空間複雜度

02-19

　　時間複雜度和空間複雜度是衡量一個演算法的兩個重要指標,用於表示演算法的最差狀態所需的時間增長量和所需輔助空間.

　　接下來用我之前所寫的冒泡排序作為例子來討論：

def bubble_sort(arr): length = len(arr) # 第一級遍歷 for index in range(length): # 第二級遍歷 for j in range(1, length - index): if arr[j - 1] > arr[j]: # 交換兩者數據，這裡沒用temp是因為python 特性元組。 arr[j - 1], arr[j] = arr[j], arr[j - 1] return arr

　　冒泡演算法最壞情況(逆序)的運行時間和長度有2次線性關係,具體算式如下：

T(n) = a * (n*(n-1)+(n-1)*(n-2)+...+2*1)+C = 4n * ( n/2 ) + C

　　其中 C 為常數運算次數 ,比如調用函數,設置長度, a 為循環體中進行的操作數.

　　衡量一個演算法的運行時間主要是看其在長時間運行中的表現情況,所以在計算時間複雜度的時候,只需考慮最高次冪的項.

　　在冒泡演算法中時間開銷最大的項為 an^2 從這裡我們就可已得出冒泡演算法的排序長度和運行時間成二次曲線.

　　而在表達時間複雜度時,為了只關注代碼運算時間的增長率,還忽略掉最高項的係數,由此可得時間複雜度為 O(n^2).

　　那麼冒泡演算法的空間複雜度呢？

　　是 O(1) ,在這個Python範例中由於使用了元組,所以我們利用到的額外空間只有 length,也就是說不管如何進行運算,這個演算法佔用的空間永遠是常數空間.

　　空間複雜度又被稱作輔助空間,與時間複雜度一樣,空間複雜度同樣只考慮所佔空間的增長率.

　　在基礎演算法中,我們常常會使用輔助空間來節約演算法的運行時間,比如歸併排序:

# 遞歸法def merge_sort(list): # 認為長度不大於1的數列是有序的 if len(list) <= 1: return list # 二分列表 middle = len(list) // 2 left = merge_sort(list[:middle]) right = merge_sort(list[middle:]) # 最後一次合併 return merge(left, right)# 合併def merge(left, right): l,r=0,0 result=[] while l<len(left) and r<len(right): if left[l] <right[r]: result.append(left[l]) l+=1 else: result.append(right[r]) r +=1 reslut +=left[l:] result+=right[r:] return result

　　就利用了 O(n) 的輔助空間來進行排序.

　　對著兩種排序演算法有疑問可以看我之前的文章.

　　有人認為基本演算法並沒有什麼意義,其實不然,這些基礎的演算法和數據結構將會是減少用戶等待時間的磨刀石.