***************************************************

更多精彩，歡迎進入：http://shop115376623.taobao.com

***************************************************

求解算法的時間復雜度的具體步驟是：

　　⑴ 找出算法中的基本語句；

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

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

　　只需計算基本語句執行次數的數量級，這就意味著只要保證基本語句執行次數的函數中的最高次冪正確即可，可以忽略所有低次冪和最高次冪的系數。這樣能夠簡化算法分析，并且使注意力集中在最重要的一點上：增長率。

　　⑶ 用大Ο記號表示算法的時間性能。

　　將基本語句執行次數的數量級放入大Ο記號中。

　　如果算法中包含嵌套的循環，則基本語句通常是最內層的循環體，如果算法中包含并列的循環，則將并列循環的時間復雜度相加。例如：

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

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

　　第一個for循環的時間復雜度為Ο(n)，第二個for循環的時間復雜度為Ο(n2)，則整個算法的時間復雜度為Ο(n+n2)=Ο(n2)。

　　常見的算法時間復雜度由小到大依次為：

　　Ο(1)＜Ο(log2n)＜Ο(n)＜Ο(nlog2n)＜Ο(n2)＜Ο(n3)＜…＜Ο(2n)＜Ο(n!)

Ο(1)表示基本語句的執行次數是一個常數，一般來說，只要算法中不存在循環語句，其時間復雜度就是Ο(1)。Ο(log2n)、Ο(n)、Ο(nlog2n)、Ο(n2)和Ο(n3)稱為多項式時間，而Ο(2n)和Ο(n!)稱為指數時間。計算機科學家普遍認為前者是有效算法，把這類問題稱為P類問題，而把后者稱為NP問題。

這只能基本的計算時間復雜度，具體的運行還會與硬件有關。

上面的這部分內容是比較可靠的，理解的時候，可以參看著下面的這部分內容。

在計算算法時間復雜度時有以下幾個簡單的程序分析法則:

1.對于一些簡單的輸入輸出語句或賦值語句,近似認為需要O(1)時間

2.對于順序結構,需要依次執行一系列語句所用的時間可采用大O下"求和法則"

求和法則:是指若算法的2個部分時間復雜度分別為 T1(n)=O(f(n))和 T2(n)=O(g(n)),則 T1(n)+T2(n)=O(max(f(n), g(n)))

特別地,若T1(m)=O(f(m)), T2(n)=O(g(n)),則 T1(m)+T2(n)=O(f(m) + g(n))

3.對于選擇結構,如if語句,它的主要時間耗費是在執行then字句或else字句所用的時間,需注意的是檢驗條件也需要O(1)時間

4.對于循環結構,循環語句的運行時間主要體現在多次迭代中執行循環體以及檢驗循環條件的時間耗費,一般可用大O下"乘法法則"

乘法法則: 是指若算法的2個部分時間復雜度分別為 T1(n)=O(f(n))和 T2(n)=O(g(n)),則 T1*T2=O(f(n)*g(n))

5.對于復雜的算法,可以將它分成幾個容易估算的部分,然后利用求和法則和乘法法則技術整個算法的時間復雜度

另外還有以下2個運算法則:

(1) 若g(n)=O(f(n)),則O(f(n))+ O(g(n))= O(f(n))

(2) O(Cf(n)) = O(f(n)),其中C是一個正常數

可以用以上法則對下面程序段進行簡單分析

①for (i=0; i<n; i++)

② for (j=0; j<n; j++)

{

③ c[i][j] = 0;

④ for (k=0; k<n; k++)

⑤ c[i][j]= c[i][j]+ a[i][k]* b[k][j];/ * T5(n) = O(1) */

}

第①條與②③④⑤是循環嵌套T1(n)*T2(n)* (T3(n)+ T4(n)* T5(n))= O(n*n*n)即為整個算法的時間復雜度

O(1)<O(log2n)<O(n)<O(n log2 n)<O(n^2)<O(n^3)<O(2^n)

?

轉自http://blog.sina.com.cn/s/blog_50ce2abb0100vhem.html

表示時間復雜度的階有：

O(1)?：常量時間階??????????O (n)：線性時間階

O(㏒n)?：對數時間階????O(n㏒n)?：線性對數時間階

O (n^k)：?k≥2?，k次方時間階

例１??兩個n階方陣的乘法

??????????????for(i=1，i<=n; ++i)

??????????????????for(j=1; j<=n; ++j)

?????????????????????{???c[i][j]=0 ;

??????????????????????????for(k=1; k<=n; ++k)

?????????????????????????c[i][j]+=a[i][k]*b[k][j] ;?

}

由于是一個三重循環，每個循環從1到n，則總次數為：?n×n×n=n³　時間復雜度為T(n)=O(n³)【立方階】

例２??{++x; s=0 ;}

將x自增看成是基本操作，則語句頻度為１，即時間復雜度為Ｏ(1)?。【常量階】

如果將s=0也看成是基本操作，則語句頻度為２，其時間復雜度仍為Ｏ(1)，即常量階。

例３???for(i=1; i<=n; ++i)

???????????????{ ++x; s+=x ; }?

語句頻度為：2n，其時間復雜度為：O(n)?，即為【線性階】。

例４???for(i=1; i<=n; ++i)

　　　　for(j=1; j<=n; ++j)

???????????????????{ ++x; s+=x ; }

???語句頻度為：n*n*2=2n²?，其時間復雜度為：O(n²)?，即為【平方階】。

定理：若A(n)=a_mn^m?+a_m-1n^m-1+…+a₁n+a₀是一個m次多項式，則A(n)=O(n^m)

例５???for(i=2;i<=n;++i)

??????????????for(j=2;j<=i-1;++j)

????????????????????{++x; a[i,j]=x; }

語句頻度為：???1+2+3+…+n-2=(1+n-2) ×(n-2)/2

=(n-1)(n-2)/2 =n²-3n+2

?∴時間復雜度為O(n²)，即此算法的時間復雜度為【平方階】。

一個算法時間為O(1)的算法，它的基本運算執行的次數是固定的。因此，總的時間由一個常數（即零次多項式）來限界。而一個時間為O(n²)的算法則由一個二次多項式來限界。

以下六種計算算法時間的多項式是最常用的。其關系為：

?????O(1) < O(㏒n) < O(n) < O(n㏒n) < O(n²) < O(n³)

??指數時間的關系為：

????O(2ⁿ) < O(n!) < O(nⁿ)

當n取得很大時，指數時間算法和多項式時間算法在所需時間上非常懸殊。

例1：素數的判斷算法。

void prime( int n)

?

{??

int i=2 ;

while ( (n%i)!=0 && i*1.0< sqrt(n) )??

?????i++ ;

if (i*1.0>sqrt(n) )

??????printf(“&d?是一個素數\n” , n) ;

else

??????printf(“&d?不是一個素數\n” , n) ;

}

嵌套的最深層語句是i++；其頻度由條件( (n% i)!=0 && i*1.0< sqrt(n) )決定，顯然i*1.0< sqrt(n)?，時間復雜度O(n^1/2)。

或者說是O(sqrt(n))；

?

例2：冒泡排序法。

Void bubble_sort(int a[]，int n)

{??

change=false;

for (i=n-1; change=TURE; i>1 && change; --i)

for (j=0; j<i; ++j)

if (a[j]>a[j+1])

????{?????a[j] ←→a[j+1] ;???change=TURE ; }

}

最好情況：0次

最壞情況：1+2+3+?+n-1=n(n-1)/2

平均時間復雜度為：?O(n²)??【平方階】