概述
一個算法是由控制結(jié)構(gòu)（順序，分支昂利，循環(huán)）和原操作（指固有數(shù)據(jù)類型的操作）構(gòu)成疫稿。為了便于比較同一問題的不同算法张弛，通常的做法是，從算法中選取一種對所研究的問題來說是基本操作的原操作,以該基本原操作重復(fù)執(zhí)行的次數(shù)作為算法的時間度量意推。多數(shù)情況下豆瘫，基本原操作是它最深層循環(huán)中的原操作，對算法的時間度量最常用的是考慮在最壞的情況下時間復(fù)雜度菊值。
時間復(fù)雜度的定義
算法中基本操作重復(fù)執(zhí)行的次數(shù)是問題規(guī)模n的某個函數(shù)外驱，用T(n)表示，若有某個輔助函數(shù)f(n)腻窒，使得當(dāng)n趨近于無窮大時昵宇，T(n)/f(n)的極限值為不等于零的常數(shù)，則稱f(n)是T(n)的同數(shù)量級函數(shù)儿子。記作T(n)=O(f(n))瓦哎，稱O(f(n))為算法的漸進(jìn)時間復(fù)雜度(O是數(shù)量級的符號 )，簡稱時間復(fù)雜度。
根據(jù)定義蒋譬，可以歸納出基本的計(jì)算步驟
1. 計(jì)算出基本操作的執(zhí)行次數(shù)T(n)
基本操作即算法中的每條語句（以;號作為分割）割岛，語句的執(zhí)行次數(shù)也叫做語句的頻度。在做算法分析時犯助，一般默認(rèn)為考慮最壞的情況癣漆。
2. 計(jì)算出T(n)的數(shù)量級
??求T(n)的數(shù)量級，只要將T(n)進(jìn)行如下一些操作：忽略常量剂买、低次冪和最高次冪的系數(shù)惠爽。令f(n)=T(n)的數(shù)量級。
3. 用大O來表示時間復(fù)雜度
當(dāng)n趨近于無窮大時雷恃，如果lim(T(n)/f(n))的值為不等于0的常數(shù)疆股，則稱f(n)是T(n)的同數(shù)量級函數(shù)费坊。記作T(n)=O(f(n))倒槐。
以上步驟可以簡化
- 找到執(zhí)行次數(shù)最多的語句
- 計(jì)算語句執(zhí)行次數(shù)的數(shù)量級
- 用大O來表示結(jié)果
舉例
例一(O(n))
public void printsum(int count){
int sum = 1;
for(int i= 0; i<n; i++){
sum += i;
}
System.out.print(sum);
}
記住，只有可運(yùn)行的語句才會增加時間復(fù)雜度附井，因此讨越，上面方法里的內(nèi)容除了循環(huán)之外，其余的可運(yùn)行語句的復(fù)雜度都是O(1)永毅。
所以printsum的時間復(fù)雜度 = for的O(n)+O(1) = 忽略常量 = O(n)
這里其實(shí)可以運(yùn)用公式 num = n(n+1)/2把跨，對算法進(jìn)行優(yōu)化，改為*
public void printsum(int count){
int sum = 0;
sum = count*(count+1)/2;
System.out.print(sum);
}
*這樣算法的時間復(fù)雜度將由原來的O(n)降為O(1)沼死，大大地提高了算法的性能着逐。 *
例二（O(log2n)）
int i= 1;
while(i<n){
i = i*2;
}
設(shè)(i=i*2)的頻度是t, 則：2t(2的t次方)<=n; 兩邊去對數(shù)t<=log2n，考慮最壞情況意蛀，取最大值t=log2n耸别。T(n) = O(log2n)。
例三（O(n2)）
int num=0;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
num++;
}
}
時間復(fù)雜度為O(n2)县钥。
常用算法的時間復(fù)雜度
參考
http://univasity.iteye.com/blog/1164707
http://www.cnblogs.com/songQQ/archive/2009/10/20/1587122.html
