資料結構-算法-時間複雜度

時間複雜度

   顧名思義就是該算法運作的時間，什麼樣的算法算是高效的算法，無外乎是用最少的記憶體空間，花最短的時間解決問題的算法就是。是以我們考慮用時間和空間來衡量一個算法的效率，我們來看看定義：在進行算法分析時，語句總的執行次數T（n）是關于問題規模n的函數，進而分析T（n）随n的變化情況并确定T（n）的數量級。記做T（n）=O（f（n））

   根據定義，求解算法的時間複雜度的具體步驟是：

   1、找出算法中的基本語句；

      算法中執行次數最多的那條語句就是基本語句，通常是最内層循環的循環體

   2、計算基本語句的執行次數的數量級；

      隻需計算基本語句執行次數的數量級，這就意味着隻要保證基本語句執行次數的函數中的最高次幂正确即可，可以忽略所有低次幂和最高次幂的系數

   3、用大O記号表示算法的時間性能

   将基本語句執行次數的數量級放到大O記号中

在這裡說一下常遇見的幾個時間複雜度：

O（1）：常數階      O（n）：線性階    O（n^2）:平方階

推導大O階的方法

   推導規則：

   1、用常數1取代運作時間中所有加法常數。

   2、其次，隻保留最高階項。

   3、如果階項系數存在且不為1，則去掉這個系數。

   最終得到的就是大O階，簡單說就是保留求出數的最高次幂，并且把系數去掉，如：(T)=2n^2+n+1=O(n^2)

常數階

<span style="font-family:KaiTi_GB2312;font-size:24px;">int main()  
{  
    int sum = 0, n = 100;   /* 執行1次 */  
    sum = (1 + n) * n/2;    /* 執行1次 */  
  
    printf("%d", sum);      /* 執行1次 */  
} </span>           

   分析：算法運作次數的函數f(n)=3,根據上面的推導規則，第一步将3改為1，再保留最高階項，它沒有最高階項，是以算法時間複雜度應該是O（1），注意：隻是用執行次數來衡量時間複雜度，但執行次數并不等于時間複雜度，無論輸入規模n為多少，執行時間總是恒定的，時間複雜度總是O（1）

再來看一段代碼：

<span style="font-family:KaiTi_GB2312;font-size:24px;">int sum = 0 ; n = 100;        /*執行1次*/
sum = (1+n)*n/2;             /*執行1次*/
sum = (1+n)*n/2;             /*執行1次*/
sum = (1+n)*n/2;             /*執行1次*/
sum = (1+n)*n/2;             /*執行1次*/
sum = (1+n)*n/2;             /*執行1次*/
sum = (1+n)*n/2;             /*執行1次*/
sum = (1+n)*n/2;             /*執行1次*/
sum = (1+n)*n/2;             /*執行1次*/
sum = (1+n)*n/2;             /*執行1次*/
sum = (1+n)*n/2;             /*執行1次*/
printf("%d",sum);            /*執行1次*/</span>           

   分析：上面的兩端代碼中，無論n有多少個，本質隻是3和12次的執行差異，這種與問題的大小無關，執行時間恒定的算法，成為具有O(1)的時間複雜度，又叫做常數階。

   此外，對于分支結構而言，無論真假執行的次數都是恒定不變的，不會随着n的變大而發生變化，是以單純的分支結構（不在循環結構中），其時間複雜度也是O(1)。

線性階

<span style="font-family:KaiTi_GB2312;font-size:24px;">int main()  
{  
    int i, sum = 0, n = 100;    /* 執行1次 */  
    for( i = 1; i <= n; i++) /* 執行 n+1 次 */  
    {  
        sum = sum + i;          /* 執行n次 */  
        //printf("%d \n", sum);  
    }  
    printf("%d", sum);          /* 執行1次 */  
}  
</span>           

   分析：該算法所用的時間為：1+（n+1）+n=2n+3，但是雖然n不斷增大，n是一個特别特别大的數，那麼上述算法的執行時間會随着n的增大而增加，但是第一行和最後一行，也就是for循環以外的語句并不受n的規模影響，永遠就執行一次，那麼我們可以将上述算法的執行執行總數簡單記做：2n或者n，這樣我們就得到了這個算法的時間複雜度：O（n）

平方階

<span style="font-family:KaiTi_GB2312;font-size:24px;">int i;                  /* 執行1次 */ 
for(i = 0 ; i < n ; i++){            /* 執行n+1次 */  
   for(j = 0 ; j < n ; j++){         /* 執行n*（n+1）次 */ 
    /*時間複雜度為O(1)的程式*/       /* 執行1次 */ 
    }    
}</span>           

   分析：該算法的所有語句的頻度之和為：T（n）=n^2+2n+3.利用推導規則該算法的時間複雜度應該為O（n^2）；或者可以這麼了解：對于内層，時間複雜度為O（n），但是它是包含在外層循環中，再循環n次，是以這段代碼的時間複雜度為O(n^2)

常見的時間複雜度

時間複雜度所耗費的時間

O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) <O(2n) < O(n!) <O(n^n)