演算法的時間複雜度與空間複雜度

演算法複雜度是指演算法在編寫成可執行程式後，執行時所需的資源，資源包括時間資源和記憶體資源。應用於數學和計算機導論。

演算法時間複雜度的定義：（推薦學習：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中文網其他相關文章！