算法時間複雜度的計算【整理】

基本的計算步驟

時間複雜度的定義

一般情況下，算法中基本操作重複執行的次數是問題規模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) 
基本操作即算法中的每條語句（以;号作為分割），語句的執行次數也叫做語句的頻度。
           

在做算法分析時，一般預設為考慮最壞的情況。

2. 計算出T(n)的數量級 
求T(n)的數量級，隻要将T(n)進行如下一些操作：
忽略常量、低次幂和最高次幂的系數 令f(n)=T(n)的數量級。

3. 用大O來表示時間複雜度 
當n趨近于無窮大時，如果lim(T(n)/f(n))的值為不等于0的常數，則稱f(n)是T(n)的同數量級函數。記作T(n)=O(f(n))。
           

一個示例：

int num1, num2;
 for(int i=; i<n; i++){ 
     num1 += ;
     for(int j=; j<=n; j*=){ 
         num2 += num1;
     }
 } 
/*
分析：
.
語句int num1, num2;的頻度為；
語句i=;的頻度為；
語句i<n; i++; num1+=; j=; 的頻度為n；
語句j<=n; j*=; num2+=num1;的頻度為n*log2n；
T(n) =  + n + n*log2n

.
忽略掉T(n)中的常量、低次幂和最高次幂的系數
f(n) = n*log2n

.
lim(T(n)/f(n)) = (+n+n*log2n) / (n*log2n)
                     = *(/n)*(/log2n) + *(/log2n) + 

當n趨向于無窮大，/n趨向于，/log2n趨向于
是以極限等于。

T(n) = O(n*log2n)
*/
           

簡化的計算步驟

再來分析一下，可以看出，決定算法複雜度的是執行次數最多的語句，這裡是

num2 += num1

，一般也是最内循環的語句。

并且，通常将求解極限是否為常量也省略掉？

于是，以上步驟可以簡化為：

1. 找到執行次數最多的語句 
2. 計算語句執行次數的數量級
3. 用大O來表示結果 
           

繼續以上述算法為例，進行分析：

1.
執行次數最多的語句為num2 += num1

2.
T(n) = n*log2n
f(n) = n*log2n

3.
// lim(T(n)/f(n)) = 1
T(n) = O(n*log2n)
           

一些補充說明【重要】

最壞時間複雜度

算法的時間複雜度不僅與語句頻度有關，還與問題規模及輸入執行個體中各元素的取值有關。一般不特别說明，讨論的時間複雜度均是最壞情況下的時間複雜度。這就保證了算法的運作時間不會比任何更長。
           

求數量級

即求對數值(log)，預設底數為10，簡單來說就是“一個數用标準科學計數法表示後，10的指數”。例如，5000=5x10 3 (log5000=3) ，數量級為3。另外，一個未知數的數量級為其最接近的數量級，即最大可能的數量級。
           

求極限的技巧

要利用好1/n。當n趨于無窮大時，1/n趨向于0 
           

一些規則(引自：時間複雜度計算 )

1) 加法規則

T(n,m) = T1(n) + T2(n) = O (max ( f(n), g(m) )
           

2) 乘法規則

T(n,m) = T1(n) * T2(m) = O (f(n) * g(m))
           

3) 一個特例（問題規模為常量的時間複雜度）

在大O表示法裡面有一個特例，如果T1(n) ＝ O(c)， c是一個與n無關的任意常數，T2(n) = O ( f(n) ) 則有
T(n) = T1(n) * T2(n) = O ( c*f(n) ) = O( f(n) )

也就是說，在大O表示法中，任何非0正常數都屬于同一數量級，記為O(1)。
           

4) 一個經驗規則

複雜度與時間效率的關系：
c < log2n < n < n*log2n < n2 < n3 < 2n < 3n < n! （c是一個常量）
           

對比：

>　其中c是一個常量  

>　如果一個算法的複雜度為c 、 log2n 、n 、 n*log2n,那麼這個算法時間效率比較高 

> 如果是 2n , 3n ,n!,那麼稍微大一些的n就會令這個算法不能動了 

> 居于中間的幾個則差強人意。
           

複雜情況的分析

以上都是對于單個嵌套循環的情況進行分析，但實際上還可能有其他的情況，下面将例舉說明。

1.并列循環的複雜度分析

将各個嵌套循環的時間複雜度相加。

例如：

　　for (i=; i<=n; i++)
　　    x++;

　　for (i=; i<=n; i++)
　　    for (j=; j<=n; j++)
　　        x++;
/*
解：
第一個for循環
T(n) = n
f(n) = n
時間複雜度為Ο(n)

第二個for循環
T(n) = n2
f(n) = n2
時間複雜度為Ο(n2)

整個算法的時間複雜度為Ο(n+n2) = Ο(n2)。
*/
           

2.函數調用的複雜度分析

例如：

public void printsum(int count){
    int sum = ;
    for(int i= ; i<n; i++){
       sum += i;
    }   
    System.out.print(sum);
}

/*
分析：
記住，隻有可運作的語句才會增加時間複雜度，是以，上面方法裡的内容除了循環之外，其餘的可運作語句的複雜度都是O(1)。
是以printsum的時間複雜度 = for的O(n)+O(1) = 忽略常量 = O(n)

*這裡其實可以運用公式 num = n*(n+1)/2，對算法進行優化，改為：*/
public void printsum(int count){
    int sum = ;
    sum = count * (count+)/;   
    System.out.print(sum);
}
//這樣算法的時間複雜度将由原來的O(n)降為O(1)，大大地提高了算法的性能。 
           

3.混合情況（多個方法調用與循環）的複雜度分析

例如：

public void suixiangMethod(int n){
    printsum(n);//1.1
    for(int i= ; i<n; i++){
       printsum(n); //1.2
    }
    for(int i= ; i<n; i++){
       for(int k=; k
        System.out.print(i,k); //1.3
      }
  }
//suixiangMethod 方法的時間複雜度需要計算方法體的各個成員的複雜度。
//也就是1.1+1.2+1.3 = O(1)+O(n)+O(n2) ----> 忽略常數 和 非主要項 == O(n2)
           

更多的例子

O(1)

交換i和j的内容

temp=i;
i=j;
j=temp;   

/*
以上三條單個語句的頻度為1，該程式段的執行時間是一個與問題規模n無關的常數。算法的時間複雜度為常數階，記作T(n)=O(1)。如果算法的執行時間不随着問題規模n的增加而增長，即使算法中有上千條語句，其執行時間也不過是一個較大的常數。此類算法的時間複雜度是O(1)。
*/
           

O(n2)

sum=；                /* 執行次數1 */
    for(i=;i<=n;i++)      
       for(j=;j<=n;j++) 
         sum++；       /* 執行次數n2 */
//解：T(n) = 1 + n2 = O(n2)

   for (i=;i<n;i++)
   { 
       y=y+;        ①   
       for (j=;j<=(*n);j++)    
          x++;        ②      
   }         
   /*
解：  語句1的頻度是n-1
         語句2的頻度是(n-1)*(2n+1) = 2n2-n-1
         T(n) = 2n2-n-1+(n-1) = 2n2-2
         f(n) = n2
         lim(T(n)/f(n)) = 2 + 2*(1/n2) = 2
         T(n) = O(n2).
         */
           

O(n)

a=0;
   b=1;               ①
   for (i=1;i<=n;i++) ②
   {  
      s=a+b;　　　　③
      b=a;　　　　　④  
      a=s;　　　　　⑤
   }
   /*
解：  語句1的頻度：2,        
         語句2的頻度：n,        
         語句3的頻度：n,        
         語句4的頻度：n,    
         語句5的頻度：n,                                  
         T(n) = 2+4n
         f(n) = n
         lim(T(n)/f(n)) = 2*(1/n) + 4 = 4
         T(n) = O(n).     
         */
           

O(log2n)

i=1;       ①
   while (i<=n)
      i=i*2; ②
      /*
解： 語句1的頻度是1,  
       設語句2的頻度是t,  則：nt<=n;  t<=log2n
       考慮最壞情況，取最大值t=log2n,
        T(n) = 1 + log2n
        f(n) = log2n
        lim(T(n)/f(n)) = 1/log2n + 1 = 1
        T(n) = O(log2n)
        */
           

O(n3)

for(i=;i<n;i++)
   {  
      for(j=;j<i;j++)  
      {
         for(k=;k<j;k++)
            x=x+;  
      }
/*
解：當i=m, j=k的時候,内層循環的次數為k當i=m時, j 可以取 ,,...,m- ,  是以這裡最内循環共進行了++...+m-=(m-)m/次是以,i從取到n, 則循環共進行了: +(-)*/+...+(n-)n/=n(n+)(n-)/次
T(n) = n(n+)(n-)/ = (n3-n)/
f(n) = n3
是以時間複雜度為O(n3)。
 */
           

個人感覺這個還是挺适合了解時間複雜度計算的标準，便于了解。原文轉自：算法時間複雜度的計算【整理】