什么是時間復雜度？時間復雜度有哪幾種？

在計算機科學中，時間復雜性，又稱時間復雜度，算法的時間復雜度是一個函數，它定性描述該算法的運行時間。這是一個代表算法輸入值的字符串的長度的函數。時間復雜度常用大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)。

時間復雜度有哪幾種?常見的七種時間復雜度：

O(1)：Constant Compxity 常數復雜度。

O(log n)：Logarithmic Complexity 對數復雜度。

O(n)：Linear Complexity 線性時間復雜度。

O(n^2)：N square Complexity 平方。

O(n^3)：N cubic Complexity 立方。

O(2^n)：Exponential Grwth 指數。

O(n!)：Factorial階乘。