演算法複雜度是指演算法在編寫成可執行程式後,執行時所需的資源,資源包括時間資源和記憶體資源。應用於數學和計算機導論。
演算法時間複雜度的定義:(推薦學習:PHP影片教學)
在進行演算法分析時,語句總的執行次數T(n)是關於問題規模n的函數,進而分析T(n)隨n的變化情況並確定T(n)的數量級。演算法的時間複雜度,也就是演算法的時間量度,記作:T(n)= O(f(n))。它表示隨問題規模n的增大,演算法執行時間的成長率和f(n)的成長率相同,稱作演算法的漸近時間複雜度,簡稱時間複雜度。其中f(n)是問題規模n的某個函數。
用大寫O()來體現演算法時間複雜度的記法,我們稱之為大O記法。
在各種不同演算法中,若演算法中語句執行次數為一個常數,則時間複雜度為O(1),另外,在時間頻度不相同時,時間複雜度有可能相同,如T(n)=n^2 3n 4與T(n)=4n^2 2n 1它們的頻度不同,但時間複雜度相同,都為O(n^2)。
依數量級遞增排列,常見的時間複雜度有:
常數階O(1),對數階O(log2n)(以2為底n的對數,下同),線性階O(n),
線性對數階O(nlog2n),平方階O(n^2),立方階O(n^3),...,
k次方階O(n^k),指數階O(2^n)。隨著問題規模n的不斷增大,上述時間複雜度不斷增大,演算法的執行效率越低。
演算法空間複雜度
與時間複雜度類似,空間複雜度是指演算法在電腦內執行時所需儲存空間的量測。
記作:
S(n)=O(f(n))
演算法執行期間所需要的儲存空間包含3個部分:
演算法程式所佔的空間;
輸入的初始資料所佔的儲存空間;
演算法執行過程中所需的額外空間。
在許多實際問題中,為了減少演算法所佔的儲存空間,通常採用壓縮儲存技術。
更多PHP相關技術文章,請造訪PHP圖文教學欄位進行學習
以上是演算法的時間複雜度與空間複雜度的詳細內容。更多資訊請關注PHP中文網其他相關文章!