時間複雜度介紹

簡介

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

相同大小的不同輸入值仍可能造成算法的運作時間不同，是以我們通常使用算法的最壞情況複雜度，記為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)。

常見算法的時間複雜度舉例說明

1.常數階O(1)

無論代碼執行了多少行，隻要是沒有循環等複雜結構，那這個代碼的時間複雜度就都是O(1)如：

int i = 1;
int j = 2;
++i;
j++;
int m = i + j;
           

上述代碼在執行的時候，它消耗的時候并不随着某個變量的增長而增長，那麼無論這類代碼有多長，即使有幾萬幾十萬行，都可以用O(1)來表示它的時間複雜度。

2.對數階O(logN)

int i = 1;
while(i<n)
{
    i = i * 2;
}
           

從上面代碼可以看到，在while循環裡面，每次都将 i 乘以 2，乘完之後，i 距離 n 就越來越近了。我們試着求解一下，假設循環x次之後，i 就大于n了，此時這個循環就退出了，也就是說 2 的 x 次方等于 n，那麼 x = log2^n

也就是說當循環 log2^n 次以後，這個代碼就結束了。是以這個代碼的時間複雜度為：O(logn)

3.線性階O(n)

for(i=1; i<=n; ++i)
{
   j = i;
   j++;
}
           

這段代碼，for循環裡面的代碼會執行n遍，是以它消耗的時間是随着n的變化而變化的，是以這類代碼都可以用O(n)來表示它的時間複雜度。

4.線性對數階O(nlogN)

線性對數階O(nlogN) 其實非常容易了解，将時間複雜度為O(logn)的代碼循環N遍的話，那麼它的時間複雜度就是 n * O(logN)，也就是了O(nlogN)。

就拿上面的代碼加一點修改來舉例：

for(m=1; m<n; m++)
{
    i = 1;
    while(i<n)
    {
        i = i * 2;
    }
}           

5.平方階O(n²)

平方階O(n²) 就更容易了解了，如果把 O(n) 的代碼再嵌套循環一遍，它的時間複雜度就是 O(n²) 了。

舉例：

for(x=1; i<=n; x++)
{
   for(i=1; i<=n; i++)
    {
       j = i;
       j++;
    }
}           

小結:O(1) < O(logn) < O(n) < O(nlogn) < O(n^2)