算法分析
維基百科,自由的 encyclopedia
在計算機科學中,算法分析(英語:Analysis of algorithm)是分析執行一個給定算法需要消耗的計算資源數量(例如計算時間,存儲器使用等)的過程。算法的效率或複雜度在理論上表示為一個函數。其定義域是輸入數據的長度(通常考慮任意大的輸入,沒有上界),值域通常是執行步驟數量(時間複雜度)或者存儲器位置數量(空間複雜度)。算法分析是計算複雜度理論的重要組成部分。
理論分析常常利用漸近分析估計一個算法的複雜度,並使用大O符號、大Ω符號和大Θ符號作為標記。舉例,二分查找所需的執行步驟數量與查找列表的長度之對數成正比,記為 ,簡稱為「對數時間」。通常使用漸近分析的原因是,同一算法的不同具體實現的效率可能有差別。但是,對於任何給定的算法,所有符合其設計者意圖的實現,它們之間的性能差異應當僅僅是一個係數。
精確分析算法的效率有時也是可行的,但這樣的分析通常需要一些與具體實現相關的假設,稱為計算模型。計算模型可以用抽象機器來定義,比如圖靈機。或者可以假設某些基本操作在單位時間內可完成。
假設二分查找的目標列表總共有 n 個元素。如果我們假設單次查找可以在一個時間單位內完成,那麼至多只需要 單位的時間就可以得到結果。這樣的分析在有些場合非常重要。
算法分析在實際工作中是非常重要的,因為使用低效率的算法會顯著降低系統性能。在對運行時間要求極高的場合,耗時太長的算法得到的結果可能是過期或者無用的。低效率算法也會大量消耗計算資源。