利用 Python 淺嘗算法分析

引言

學習編程的人或許都聽說過,程序 = 數據結構 + 算法 .數據是程序的中心,算法是解決問題的步驟,數據結構和算法兩個概念間的邏輯關系貫穿了整個程序世界，首先二者表現為不可分割的關系.沒有數據間的有機關系，程序根本無法設計。數據結構是底層，算法是上層。數據結構為算法提供服務,算法圍繞數據結構進行操作

這些概念較為抽象,我們淺嘗辄止,本文只介紹一些簡單的理論,我們平時練習的程序可能運算規模和數據規模都很小每次運行都能很快得出結果,可以說是秒出.因為現在計算機技術的快速發展,就算是個人計算機一樣有這非常可觀的算力.但是這並不能改變運行程序時消耗資源的事實.

在實際的開發中,無論是設計還是應用一種算法,我們都要了解這種算法的性能如何,通常我們在衡量一個算法的性能時關心的是對 CPU 和內存的使用率,但是 CPU 是計算機中最為珍貴的資源,我們還是以 CPU 的使用率為主,它體現在算法上就是算法的運算速度,用一個專業的描述就是算法的時間復雜度.相應,如果要計算的是程序運行需要的空間需要考慮的就是空間復雜度.作為上層的使用者我們更關心是時間復雜度,時間越快越好,但是資源開銷的成本來看,我們會平衡時間和空間進行取捨.

什麼是時間復雜度

不同機器運算速度不一樣，我們如何統一衡量一個算法的執行時間呢？計算機科學家們想到，可以用計算步驟來稱量。我們所說的算法時間復雜度一般就是指解決問題所執行的語句頻數.即算法從開始執行到執行完畢所需要的步驟數量。說通俗點,就是計算程序運行步驟次數的最高階.由於並不是每個算法都能上機測試,而且現實中也沒有太大的必要,我們一般需要分析得出大致計算所需要的資源,才會上機,而不是盲目上機測試.說白了.我們使用算法中語句的執行次數對算法進行估算,哪個算法中語句執行次數多,它花費的時間就多,同時我們通常將算法中的語句執行次數稱為時間頻度,記為 T(n),n 表示的是語句的規模

什麼是大 O 表示法

有了 T(n)之後,還有一個問題就是我們不知道隨著處理數據的的增長他的變化會呈現出什麼規律,因此引入輔助函數 f(n)的概念,他和 T(n)是同一個量級的,使用符號 O(f(n))來替代 T(n).O(f(n))這種形式也稱為大 O 表示法.這樣我們可以使用函數分析的手段較為准確地分析時間頻度 T(n),並以此來計算時間復雜度

大 O 表示法的規則

有些運行處理對於當前的算法來說影響很小,幾乎可以忽略不計.

大 O 表示法的簡單規則如下:

1. 常數項使用 O(1)表示

2. 高階因子和低階因子並存,只保留高階因子

3. 如果高階因子項存在並且不是常數項,則去除系數

對與上面的描述你可能還有一點一知半解,那我們就通過例子來唠一唠

算法分析的簡單小實例:

常數階:比如我們平時一些簡單的賦值.簡單的四則運行

a = 2b = 5c = 0.5*a*bprint(c)

上面的例子所有語句最高階是 1,是常數級的.所以他們整體就是常數級的,所以他的時間復雜度就是常數階用 O(1)表示;不管這樣的語句有多少條,時間復雜度也不會變,在算法中常數階也是運行速度最快的

線性階:簡單理解就是可能涉及到單層循環

for i in range(n): print('hello!') 

因為循環體中的時間復雜度為 O(1)常數階的代碼執行了 n 次,這段代碼的規模就是由 n 的大小決定的.所以它的時間復雜度為 O(n)

平方階:簡單理解是在線性階的基礎上由多加了一層循環

for i in range(n): for j in range(m): print('你好')

在這段代碼中最裡層代碼依然是常數階,常數階外面為兩層循環,內層循環的頻數是由外層決定的,所以,它的時間復雜度不能簡單地設為 n^2.但是我們可以對其進行推導,代碼中輸出語句執行的次數為:n+(n-1)+(n-2)+······+1 這是一個等差數列,由等差數列公式可得該式為 n^2+n/2.根據上文中大 O 表示法的第 2 和 3 條規則可得出最高階為 n^2,所以上面代碼的時間復雜度為 O(n^2)

常見時間復雜度的比較

下面分別從簡單的例子列舉中了解常用的算法復雜度:

O(1): 從一個數據集中獲取第一個元素

l = [1,2,3,4]first = l[0]print(first)

O(log n): 將數據集分為兩堆,然後將分好的部分再分半,以此類推(二分法)

def binary_search(list, item): low = 0 high = len(list)-1  n = 0 while low <= high: mid = int((low + high)/2) 
 guess = list[mid] n += 1
 if list[mid]==item: print(n) return mid
 if list[mid]<item:  low = mid + 1 else: high = (mid-1) return None l=[1,2,3,4,8,9,11,12,14,18,19,20,28]print(binary_search(l,12))

O(n): 遍歷一個數據集

l = [1,2,3,4]for i in l: print(i)

O(n log n) :給數據生成所有的排列組合同時遍歷分出來的每一半數據

O(n^2)平方級: 遍歷一個數據集中的每個元素的同時遍歷另一個同數量級的數據集

O(2^n)指數級: 為一個數據集生成其可能的所有子集

O(n!)階乘級: 給數據集生成所有的排列組合

唠一唠:你那些常用的算法都分別對應著上面的哪種時間復雜度呢?