??1個算法是由控制結(jié)構(gòu)（順序，分支，循環(huán)）和原操作（指固有數(shù)據(jù)類型的操作）構(gòu)成。為了便于比較同1問題的不同算法，通常的做法是，從算法當選取1種對所研究的問題來講是基本操作的原操作,以該基本原操作重復履行的次數(shù)作為算法的時間度量。多數(shù)情況下，基本原操作是它最深層循環(huán)中的原操作，對算法的時間度量最經(jīng)常使用的是斟酌在最壞的情況下時間復雜度。
??算法中基本操作重復履行的次數(shù)是問題范圍n的某個函數(shù)，用T(n)表示，若有某個輔助函數(shù)f(n)，使得當n趨近于無窮大時，T(n)/f(n)的極限值為不等于零的常數(shù)，則稱f(n)是T(n)的同數(shù)量級函數(shù)。記作T(n)=O(f(n))，稱O(f(n))為算法的漸進時間復雜度(O是數(shù)量級的符號 )，簡稱時間復雜度。
1. 計算出基本操作的履行次數(shù)T(n)
??基本操作即算法中的每條語句（以;號作為分割），語句的履行次數(shù)也叫做語句的頻度。在做算法分析時，1般默許為斟酌最壞的情況。
2. 計算出T(n)的數(shù)量級
??求T(n)的數(shù)量級，只要將T(n)進行以下1些操作：疏忽常量、低次冪和最高次冪的系數(shù)。令f(n)=T(n)的數(shù)量級。
3. 用大O來表示時間復雜度
??當n趨近于無窮大時，如果lim(T(n)/f(n))的值為不等于0的常數(shù)，則稱f(n)是T(n)的同數(shù)量級函數(shù)。記作T(n)=O(f(n))。
1. 找到履行次數(shù)最多的語句
2. 計算語句履行次數(shù)的數(shù)量級
3. 用大O來表示結(jié)果
例1(O(n))
public void printsum(int count){
int sum = 1;
for(int i= 0; i<n; i++){
sum += i;
}
System.out.print(sum);
}記住，只有可運行的語句才會增加時間復雜度，因此，上面方法里的內(nèi)容除循環(huán)以外，其余的可運行語句的復雜度都是O(1)。
所以printsum的時間復雜度 = for的O(n)+O(1) = 疏忽常量 = O(n)
這里其實可以應用公式 num = n(n+1)/2，對算法進行優(yōu)化，改成*
public void printsum(int count){
int sum = 0;
sum = count*(count+1)/2;
System.out.print(sum);
}這樣算法的時間復雜度將由原來的O(n)降為O(1)，大大地提高了算法的性能。
例2（O(log2n)）
int i= 1;
while(i<n){
i = i*2;
}設(i=i*2)的頻度是t, 則：2t(2的t次方)<=n; 兩邊去對數(shù)t<=log2n，斟酌最壞情況，取最大值t=log2n。T(n) = O(log2n)。
例3（O(n2)）
int num=0;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
num++;
}
}時間復雜度為O(n2)。
http://univasity.iteye.com/blog/1164707
http://www.cnblogs.com/songQQ/archive/2009/10/20/1587122.html
程序員人生，我編程，我富裕，記住wfuyu網(wǎng)，php教程，php學習，php手冊，CMS模版制作
聲明：本站大部分內(nèi)容是作者原創(chuàng)，少部分收集于互聯(lián)網(wǎng)供大家一起學習，原版權(quán)很多不明，如有侵權(quán)請聯(lián)系本站，謝謝！
粵ICP備14040726號-1?? 2015-2020 程序員人生 版權(quán)所有
