-
算法複雜性
鎖定
算法複雜性的度量主要是針對運行該算法所需要的計算機資源的多少。當算法所需要的資源越多,該算法的複雜性越高;反之,當算法所需要的資源越少,算法的複雜性越低。對於任意給定的一個問題,設計出複雜性儘可能低的算法是在設計算法時追求的重要目標之一;而當給定的問題存在多種算法時,選擇其中複雜性最低的算法是選用算法時遵循的重要準則。因此,算法的複雜性分析對算法的設計或選用具有重要的指導意義和實用價值。
- 中文名
- 算法複雜性
- 意 義
- 估算某個算法所消耗的資源
- 種 類
- 時間複雜度、空間複雜度
算法複雜性時間複雜度
一般情況下,對於一個算法的複雜性分析主要是對算法效率的分析,包括衡量其運行速度的時間效率及衡量其運行時所需要佔用空間大小的空間效率。
對於早期的計算機來説,時間與空間都是極其珍貴的資源。由於硬件技術的發展大大提高了計算機的存儲容量,使得存儲容量的侷限性對於算法的影響大大降低。但是時間效率並沒有得到相應程度的提高。因此,算法的時間效率或算法時間複雜度是算法分析中的關鍵所在。
對於算法的時間效率的計算,通常是拋開與計算機硬件、軟件有關的因素,僅考慮實現該算法的高級語言程序。一般而言,對程序執行的時間複雜度的分析是分塊進行的,先分析程序中的語句,再分析各程序段,最後分析整個程序的執行復雜度。通常以漸進式的大O(希臘字母Omicron,奧米克戎)形式來表示算法的時間複雜度。漸進式的大O形式表示時間複雜度的主要運算規則有如下2種。
1、求和規則
2、乘法規則
假設T(n)是問題規模n(n為整數)的函數,算法的時間複雜度可以定義為O(f(n)),
記作:T(n)=O(f(n))
由於隨着問題規模n的增長,算法執行時間的增長率和f(n)的增長率相同,因此T(n)也被稱為算法的時間複雜度。
算法複雜性空間複雜度
一般情況下,一個算法所佔用的存儲空間包括算法自身、算法的輸入、算法的輸出及實現算法的程序在運行時所佔用空間的總和。
由於算法的輸入和輸出所佔用的空間基本上是一個確定的值,它們不會隨着算法的不同而不同。而算法自身所佔用的空間與實現算法的語言和所使用的語句密切相關,例如程序越短,它所佔用的空間就越少。一個算法在運行過程中所佔用的空間,特別是算法臨時開闢的存儲空間單元則是由算法策略及該算法所處理的數據量決定的。因此,對於一個算法的空間複雜度的衡量主要考慮的是算法在運行過程中所需要的存儲空間的大小。
假設S(n)是問題規模n(n為整數)的函數,可以定義算法的空間複雜度為O(f(n)),
記作:S(n)=O(f(n))