《從入門到放棄》數據結構和演算法 1- 演算法的引入和演算法時間複雜度

• 2020 年 2 月 11 日
• 筆記

1. 簡介　

　　最近由於快過年了，不是很忙碌了，人心浮動，很多都請假了，現在終於有時間來系統學習下和惡補一下常見數據結構和演算法的知識，所以，還是通過記錄筆記放在部落格的方式來督促自己學習。同時和小夥伴們分享一下學習心得與體會。演算法對於很多程式設計師都接觸不到的，何況是一個測試人員。但是面試過程中，多多少少都有演算法題的面試。所以，學習演算法，短期來看是為了跳槽準備，長期來看，是鍛煉一個人解決問題的思路的提升的一個途徑。

2. 演算法的引入

　　來看一個問題：如果 a+b+c = 1000, 且 a^2 + b^2 = c^2（勾股定理），如何求出所有a b c的組合。

2.1 問題分析：

　　上面告訴兩個條件，從數學角度來說，上面有3個未知數，只有兩個表達式條件，我們第一反應是轉換成二元二次方程來解答。這裡我們是電腦通過程式碼來解決問題。字面意思就是 a的取值範圍是0到1000， b的取值範圍是0到1000， c的取值範圍是0到1000, 然後加上題目的兩個表達式條件，利用for嵌套循環，電腦肯定能幫我們找出a b c的取值。

2.2 程式碼實現：

　　根據上面的分析，python程式碼實現如下：

2.3 參考程式碼：

# coding=utf-8  # 1.先設置編碼，utf-8可支援中英文，如上，一般放在第一行    # 2.注釋：包括記錄創建時間，創建人，項目名稱。  '''  Created on 2020-1-02  @author: 北京-宏哥  Project:《從入門到放棄》數據結構和演算法 1- 演算法的引入和演算法時間複雜度  '''  # 3.導入模組    import time    start_time = time.time()  for a in range(0, 1001):      for b in range(0, 1001):          for c in range(0, 1001):              if a + b + c == 1000 and a**2 + b**2 == c**2:                  print("a, b, c: %d, %d, %d" % (a, b, c))  end_time = time.time()  print(end_time - start_time)

2.4 運行結果：

　　其實上面程式碼思路也是用到了一個方法，叫枚舉法，就是一個一個列出來去嘗試，不行，換下一個值繼續去匹配。

　　運行程式碼後，控制台列印如下圖的結果：

　　也就是差不多花費三分鐘（117秒多），找出了符合條件的a b c的四種取值組合。如果沒有電腦，人也是可以根據這個思路，一步一步去算，只不過時間更是不知道有多慢。這個時間開銷，我們很不滿意，對用戶來說，還是太慢了。有沒有什麼辦法提升以下計算效率。

2.5 優化上面程式碼：

　　根據數學知識，我們用程式碼實現二元二次方程的思路，c = 1000 – a – b; 來減少第三層嵌套for循環。

2.5.1 程式碼實現：

2.5.2 參考程式碼：

# coding=utf-8  # 1.先設置編碼，utf-8可支援中英文，如上，一般放在第一行    # 2.注釋：包括記錄創建時間，創建人，項目名稱。  '''  Created on 2020-1-02  @author: 北京-宏哥  Project:《從入門到放棄》數據結構和演算法 1- 演算法的引入和演算法時間複雜度  '''  # 3.導入模組    import time    start_time = time.time()  for a in range(0, 1001):      for b in range(0, 1001):          c = 1000-a-b          if a**2 + b**2 == c**2:              print("a, b, c: %d, %d, %d" % (a, b, c))  end_time = time.time()  print(end_time - start_time)

2.5.3 運行結果：

　　運行程式碼後，控制台列印如下圖的結果

　　這麼一看，發現時間縮短了不到2秒，這個計算效率大大提升。同樣解決一個問題，由於我們第二種方法減少了一次for循環嵌套，導致計算效率提高了很多倍，這個就是演算法的重要性。

3. 什麼是演算法

演算法是電腦處理資訊的本質，因為電腦程式本質上是一個演算法來告訴電腦確切的步驟來執行一個指定的任務。一般地，當演算法在處理資訊時，會從輸入設備或數據的存儲地址讀取數據，把結果寫入輸出設備或者某個存儲地址供以後再調用。演算法是獨立存在的一種解決問題的方法和思想。對於演算法而言，實現的程式語言並不重要，重要的是思想。

演算法的五大特性： 1：輸入：演算法具有0個或多個輸入 2：輸出：演算法至少有一個或多個輸出 3：有窮性：演算法在有限的步驟之後會自動結束而不會無限循環，並且每一個步驟可以在可接受的時間內完成 4：確定性：演算法內的每一步都有確定的含義，不會出現二義性。 5：可行性：演算法的每一步都是可行的，也就是說每一步都能執行有限的次數完成。

4. 時間複雜度和大O表示法

　　上面我們通過兩個方法來求出a b c的取值組合，第二個方法比第一個方法，從時間效果來看，快很多，所以我們很容易得出結論，第二個演算法比第一個演算法效率要高。那麼演算法是通過時間來衡量，確實最直觀地，我們從時間上來看到演算法和演算法之間的效率不同。但是，單靠時間是不可靠的，例如，同一個演算法，在一個I7的CPU上運行和拿到一個1995年之前的個人PC電腦上運行，這種時間來比較就有點不合適了。所以，我們一般從演算法的執行計算數量這個維度去考察演算法的效率。執行數量可以這麼理解，上面3個for循環嵌套的程式碼，每一行程式碼都有確定的執行步驟數量，所有程式碼行的執行步驟數量相加，就得到了這個演算法的執行步驟數量。因為每台機器要執行這麼多步驟數量大體相同，所以這個執行步驟數量就拿來衡量演算法的效率。

　　我們假定電腦執行演算法每一個基本操作的時間是固定的一個時間單位，那麼有多少個基本操作就代表會花費多少時間單位。對於不同機器而言，確切的單位時間是不同的，但是對於演算法進行多少個基本操作，在規模數量級上說卻是相同的。由此可以忽略機器環境影響而客觀的反應演算法的時間效率。

對於演算法的時間效率，我們可以用「大O記法」來表示。 「大O記法」：對於單調的整數函數f，如果存在一個整數函數g和實常數c>0,使得對於充分大得n，總有 f(n)<=c*g(n),就說函數g是f得一個漸進函數（忽略常數），記作為f(n)=O(g(n)),也就是說在趨向無窮得 極限意義下，函數f的增長速度收到函數g的約束，亦函數f與函數g的特徵相似。

時間複雜度：假設存在函數g，使得演算法A處理規模為n的問題實例所用時間為T(n)=O(g(n))，則稱O(g(n))為演算法A 的漸進時間複雜度，簡稱時間複雜度，記為T(n)

5. 如何理解「大O記法」

　　我們通過「大O記法」的定義，我們來計算下上面 a b c這題的第一種程式碼實現方式的時間複雜度的計算過程。

　　我們根據上面這個圖程式碼對應行來分析（第4到8行程式碼），先分析每行程式碼執行步驟數目。

　　分析過程：

　　第4行：a的取值範圍是0到1000，所以這個for循環要執行1000次

　　第5行：b的取值範圍是0到1000，所以這個for循環要執行1000次

　　第6行：c的取值範圍是0到1000，所以這個for循環要執行1000次

　　第7行：如果不細分步驟，第7和第八兩行當作2個步驟，如果細分，a + b + c是一個步驟， 判斷a + b + c ==1000是一個步驟，a**2是一個步驟，所以細分，第七行存在需要執行 8個步驟數目。

　　這樣，我們把每一行程式碼需要執行步驟次數計算出來是

　　T = 1000 * 1000 * 1000 * 8 　　簡寫成 T = 8*1000^3 　　如果，這裡把1000改成n, 把這個問題規模擴大，這個演算法的時間複雜度可以寫成

　　T（n）= 8*n^3 　　我們在計算時間複雜度的時候，只關注大頭部分，會去掉旁支末節部分，一般我們可以這樣認為 n^3和1000*n^3是等價，所以我們上面文章開頭寫的第一種枚舉法的時間複雜度是 O(n^3)。

　　根據這個時間複雜度計算原則，我們計算第二種演算法的時間複雜度為O(n^2)，這個比第一個效率要高，當然如果時間複雜度為n^1，那麼這個演算法效率就更高。

6.小結

　　好了，今天的分享就到這裡吧！！！謝謝各位的耐心閱讀。有問題加群交流討論！！！

您的肯定就是我進步的動力。如果你感覺還不錯，就請鼓勵一下吧！記得隨手點波 推薦 不要忘記哦！！！

別忘了點 推薦 留下您來過的痕迹