2.1 算法定義

算法是解決待定問題求解步驟的描述，在計算機中表現為指令的有限序列，并且每條指令表示一個或多個操作。

2.2 算法的特性

算法有五個基本特性：輸入、輸出、有窮性、確定性和可行性。

• 輸入輸出
  輸入和輸出特性比較容易理解，算法具有零個或多個輸入。絕大多數算法需要輸入參數，但有的是不需要的，不如“hello world”這樣的代碼，不需要任何參數，因此算法的輸入可以是零個。算法至少有一個或多個輸出，算法是一定要輸出的，不需要輸出，那用這個算法干嘛？輸出的形式可以使打印輸出，也可以是返回一個或多個值。

• 有窮性
  有窮性：指算法在執行有限的步驟之后，自動結束而不會出現無限循環，并且每一個步驟在可接受的時間內完成。

• 確定性：
  算法的每一步驟都具有確定的含義，不會出現二義性。

算法在一定條件下，只有一條執行路徑，相同的輸入只能有唯一的輸出結果，算法的每個步驟被精確定義而無歧義。

• 可行性：
  算法的每一步都必須是可行的，也就是說，每一步都能夠通過執行有限次數完成。

2.3 算法設計的要求

算法不是唯一的，同一個問題，可以有很多種解決問題的算法。好的算法應該具有以下幾點要求：

• 正確性：
  正確性：算法的正確性是指算法至少應該具有輸入、輸出和加工處理無歧義性、能正確反映問題的需求、能夠得到問題的正確答案。

算法的“正確”通常在語法上有很大的差別，大體分為以下四個層次。

算法程序沒有語法錯誤；

算法程序對于合法的輸入數據能夠產生滿足要求的輸出結果；

算法程序對于非法的輸入數據能夠得出滿足規格說明的結果；

算法程序對于精心選擇的，甚至刁難的測試數據都有滿足要求的輸出結果。

一般情況下，我們把層次 3 作為算法是否正確的標準。

• 可讀性：
  可讀性：算法設計的另一目的是為了便于閱讀、理解和交流。

我們寫代碼的目的，一方面是為了讓計算機執行，另一方面是為了便于他人閱讀，讓人理解和交流，自己將來也可能閱讀，如果可讀性不好，時間長了自己都不知道寫了什么，可讀性是算法好壞的一個很重要的標志。

• 健壯性
  健壯性：當輸入數據不合法時，算法也能做出相關處理，而不是產生異常或莫名其妙的結果。

• 時間效率高和存儲量低
  時間效率指的是算法的執行時間，對于同一個問題，如果有多個算法可以解決，執行時間短的算法效率高，執行時間長的效率低。存儲量需求指的是算法在執行過程中需要的最大存儲空間，主要指算法程序運行時所占用的內存或外部硬盤存儲空間。設計算法應該盡量滿足時間效率高和存儲量低的需求。

綜上，好的算法，應該具有正確性、可讀性、健壯性、高效性和低存儲量的特點。

2.4 函數的漸進增長

• 函數的漸進增長：給定兩個函數f(n)與g(n)，如果存在一個整數N，使得對于所有n>N，f(n)總是比g(n)大，那么，我們說f(n)的增長漸進快于g(n)。

例子 1：
A 算法與 B 算法，A 算法要做 2n+3 次操作；B 算法要做 3n+1 次操作。問哪個執行的更快？

?

由上圖可知，當 n = 1，算法 A 效率不如算法 B；當 n = 2 時，兩者效率相同；當 n > 2 時，算法A開始優于算法 B了。得出結論，加法常數可以忽略。

例子 2：

C 算法與 D 算法，C 算法要做 4n+8 次操作；D 算法要做 2 n*n +1 次操作。問哪個執行的更快？

由上圖可知，當 n <= 3 時，算法 C 差于算法 D；當 n > 3 時，算法 C 的優勢開始越來越優于算法 D 了。得出結論：與最高次項相乘的常數并不重要。

2.5 算法時間復雜度

• 算法時間復雜度定義
  算法時間復雜度：在進行算法分析時，語句總的執行次數 T(n) 是關于問題規模n的函數，進而分析 T(n) 隨 n 的變化情況并確定 T(n) 的數量級。算法的時間復雜度，也就是算法的時間量度，記作：T(n) = O(f(n))。它表示隨問題規模 n 的增大，算法執行時間的增長率和 f(n) 的增長率相同，稱作算法的漸進時間復雜度，簡稱為時間復雜度。其中 f(n) 是問題規模 n 的某個函數。

這樣用大寫 O() 來體系那算法時間復雜度的記法，我們稱之為大 O 記法。

一般情況下，隨著n的增大，T(n) 增長最慢的算法為最優算法。

• 常用的算法時間復雜度

  
  

• 推導大 O 階方法
  • 用常數 1 取代運行時間中的所有加法常數
  • 在修改后的運行次數函數中，只保留最高階項
  • 如果最高階項存在且不是 1，則去除與這個項相乘的常數。

得到的結果就是大 O 階。

2.6 算法空間復雜度

• 算法的空間復雜度通過計算算法所需的存儲空間實現，算法空間復雜度的計算公式記作：S(n) = O(f(n))，其中，n 為問題的規模，f(n) 為語句關于 n 所占存儲空間的函數。

一般情況下，一個程序在機器上執行時，除了需要存儲程序本身的指令、常數、變量和輸入數據外，還需要存儲對數據操作的存儲單元。若輸入數據所占空間只取決于問題本身，和算法無關，這樣只需要分析該算法在實現時所需的輔助單元即可。若算法執行時所需的輔助空間相對于輸入的數據量而言是個常數，則稱此算法為原地工作，空間復雜度為 O(n)。

通常，我們都使用“時間復雜度”來指運行時間的需求，使用“空間復雜度”指空間需求。當不用限定詞地使用“復雜度”時，通常都是指時間復雜度。

?

轉載于:https://www.cnblogs.com/xinmomoyan/p/10713293.html

總結

以上是生活随笔為你收集整理的02数据结构——算法概念的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。