1，算法：
1.1 所謂算法，是指基于特定的計算模型，旨在解決某一信息處理問題而設計的一個指令序列。
1.2 一般地，算法還應必須具備以下要素：
輸入與輸出；基本操作、確定性與可行性；有窮性與正確性；退化與魯棒性；重用性
對退化與魯棒性說明：
比如其中之一就是，除一般性情況外，實用的算法還應能夠處理各種極端的輸入實例。以排序問題為例，極端情況下待排序序列的長度可能不是正數（參數n = 0甚至n < 0），或者反過來長度達到或者超過系統支持的最大值（n = INT_MAX），或者A[]中的元素不見得互異甚至全體相等，以上種種都屬于所謂的退化（degeneracy）情況。算法所謂的魯棒性（robustness），就是要求能夠盡可能充分地應對此類情況。
1.3 算法效率
可計算性；難解性；計算效率；數據結構
對數據結構說明：
無論是算法的初始輸入、中間結果還是最終輸出，在計算機中都可以數據的形式表示。對于數據的存儲、組織、轉移及變換等操作，不同計算模型和平臺環境所支持的具體形式不盡相同，其執行效率將直接影響和決定算法的整體效率。數據結構這一學科正是以“數據”這一信息的表現形式為研究對象，旨在建立支持高效算法的數據信息處理策略、技巧與方法。要做到根據實際應用需求自如地設計、實現和選用適當的數據結構，必須首先對算法設計的技巧以及相應數據結構的特性了然于心。
2，復雜度度量
2.1 時間復雜度：
從保守估計的角度出發，在規模為n的所有輸入中選擇執行時間最長者作為T(n)，并以T(n)度量該算法的時間復雜度。
2.2 漸進復雜度：
小規模問題所需的處理時間本來就相對更少，故此時不同算法的實際效率差異并不明顯；而在處理更大規模的問題時，效率的些許差異都將對實際執行效果產生巨大的影響。這種著眼長遠、更為注重時間復雜度的總體變化趨勢和增長速度的策略與方法，即所謂的漸進分析（asymptotic analysis）。
大O記號：在大O記號的意義下，函數各項正的常系數可以忽略并等同于1。多項式中的低次項均可忽略，只需保留最高次項。可以看出，大O記號的這些性質的確體現了對函數總體漸進增長趨勢的關注和刻畫。
最壞、最好與平均情況：“最壞情況復雜度”是人們最為關注且使用最多的，在一些特殊的場合甚至成為唯一的指標。比如控制核電站運轉、管理神經外科手術室現場的系統而言，從最好或平均角度評判算法的響應速度都不具有任何意義，在最壞情況下的響應速度才是唯一的指標。

以上主要的這三種漸進復雜度記號之間的聯系與區別。
2.3 空間復雜度
除了執行時間的長短，算法所需存儲空間的多少也是衡量其性能的一個重要方面，此即所謂的空間復雜度（space complexity）。實際上，以上針對時間復雜度所引入的幾種漸進記號，也適用于對空間復雜度的度量，其原理及方法基本相同。

需要注意的是，為了更為客觀地評價算法性能的優劣，除非特別申明，空間復雜度通常并不計入原始輸入本身所占用的空間，對于同一問題，這一指標對任何算法都是相同的。反之，其它（如轉儲、中轉、索引、映射、緩沖等）各個方面所消耗的空間，則都應計入。

另外，很多時候我們都是更多地甚至僅僅關注于算法的時間復雜度，而不必對空間復雜度做專門的考查。這種因為就漸進復雜度的意義而言，在任一算法的任何一次運行過程中所消耗的存儲空間，都不會多于其間所執行基本操作的累計次數。

實際上根據定義，每次基本操作所涉及的存儲空間，都不會超過常數規模；縱然每次基本操作所占用或訪問的存儲空間都是新開辟的，整個算法所需的空間總量，也不過與基本操作的次數同階。從這個意義上說，時間復雜度本身就是空間復雜度的一個天然的上界。當然，對空間復雜度的分析也有其自身的意義，尤其在對空間效率非常在乎的應用場合中，或當問題的輸入規模極為龐大時，由時間復雜度所確立的平凡上界已經難以令人滿意。這類情況下，人們將更為精細地考查不同算法的空間效率，并盡力在此方面不斷優化。

總結

以上是生活随笔為你收集整理的算法及其复杂度度量简介的全部內容，希望文章能夠幫你解決所遇到的問題。

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