演算法複雜度主要包括什麼

演算法複雜度：

《時間複雜度

    在電腦科學中，時間複雜性，又稱時間複雜度，演算法的時間複雜度是一個函數，它定性描述演算法的運行時間。這是一個代表演算法輸入值的字串的長度的函數。時間複雜度常用大O符號表述，不包括這個函數的低階項和首項係數。使用這種方式時，時間複雜度可稱為是漸近的，亦即考察輸入值大小趨近無窮時的情況。

    為了計算時間複雜度，我們通常會估計演算法的操作單元數量，每個單元運作的時間都是相同的。因此，總運行時間和演算法的操作單元數量最多相差一個常數係數。

    相同大小的不同輸入值仍可能造成演算法的運行時間不同，因此我們通常使用演算法的最壞情況複雜度，記為T(n)，定義為任何大小的輸入n所需的最大運轉時間。另一種較少使用的方法是平均情況複雜度，通常有特別指定才會使用。時間複雜度可以用函數T(n) 的自然特性加以分類，舉例來說，有著T(n) =O(n) 的演算法被稱為「線性時間演算法」；而T(n) =O(M ^n) 和M= O(T(n)) ，其中M≥n> 1 的演算法被稱為「指數時間演算法」。

    一個演算法花費的時間與演算法中語句的執行次數成正比例，哪個演算法中語句執行次數多，它花費時間就多。一個演算法中的語句執行次數稱為語句頻度或時間頻度。記為T(n)。
　　一般情況下，演算法中基本運算重複執行的次數是問題規模n的某個函數，用T(n)表示，若有某個輔助函數f(n),使得當n趨近於無窮大時，T（n)/f (n)的極限值為不等於零的常數，則稱f(n)為T(n)的同數量級函數。記作T(n)=O(f(n)),稱O(f(n)) 為演算法的漸進時間複雜度，簡稱時間複雜度。
　　在各種不同演算法中，若演算法中語句執行次數為一個常數，則時間複雜度為O(1),另外，在時間頻度不相同時，時間複雜度有可能相同，如T( n)=n2 3n 4與T(n)=4n2 2n 1它們的頻度不同，但時間複雜度相同，都為O(n2)。

時間頻度

    一個演算法執行所耗費的時間，從理論上是不能算出來的，必須上機運行測試才能知道。但我們不可能也沒有必要對每個演算法都上機測試，只要知道哪個演算法花費的時間多，哪個演算法花費的時間少就可以了。而一個演算法花費的時間與演算法中語句的執行次數成正比例，哪個演算法中語句執行次數多，它花費時間就多。一個演算法中的語句執行次數稱為語句頻度或時間頻度。記為T(n)。

空間複雜度

    與時間複雜度類似，空間複雜度是指演算法在電腦內執行時所需儲存空間的量測。作法:

    S(n)=O(f(n))

    演算法執行期間所需的儲存空間包含3個部分：

• #演算法程式所佔的空間；

• 輸入的初始資料所佔的儲存空間；

• ##演算法執行過程中所需要的額外空間。

    在許多實際問題中，為了減少演算法所佔的儲存空間，通常會採用壓縮儲存技術。

以上是演算法複雜度主要包括什麼的詳細內容。更多資訊請關注PHP中文網其他相關文章！