引導(dǎo)
通常，在編程過程中比較常遇見的問題就是性能瓶頸。很多時(shí)候我們是去考慮怎么橫向擴(kuò)展，我們聽到最多的就是aop（面向切面編程），但在這之前往往我們忽略掉了最基本的問題系統(tǒng)性能是否真的達(dá)到了瓶頸?
這時(shí)候就要用到算法知識了，首先分析在數(shù)學(xué)角度上你的算法證明是正確的基礎(chǔ)上，其次就是分析算法時(shí)間復(fù)雜度。算法的時(shí)間復(fù)雜度反映了程序執(zhí)行時(shí)間隨輸入規(guī)模增長而增長的量級，在很大程度上能很好反映出算法的優(yōu)劣與否。
算法的效率
雖然計(jì)算機(jī)能快速的完成運(yùn)算處理，但實(shí)際上，它也需要根據(jù)輸入數(shù)據(jù)的大小和算法效率來消耗一定的處理器資源。要想編寫出能高效運(yùn)行的程序，我們就需要考慮到算法的效率。
算法的效率主要由以下兩個(gè)復(fù)雜度來評估：
時(shí)間復(fù)雜度：評估執(zhí)行程序所需的時(shí)間。可以估算出程序?qū)μ幚砥鞯氖褂贸潭取?br>
空間復(fù)雜度：評估執(zhí)行程序所需的存儲(chǔ)空間?？梢怨浪愠龀绦?qū)τ?jì)算機(jī)內(nèi)存的使用程度。
設(shè)計(jì)算法時(shí)，一般是要先考慮系統(tǒng)環(huán)境，然后權(quán)衡時(shí)間復(fù)雜度和空間復(fù)雜度，選取一個(gè)平衡點(diǎn)。不過，時(shí)間復(fù)雜度要比空間復(fù)雜度更容易產(chǎn)生問題，因此算法研究的主要也是時(shí)間復(fù)雜度，不特別說明的情況下，復(fù)雜度就是指時(shí)間復(fù)雜度。本章也主要來講述時(shí)間復(fù)雜度。
時(shí)間復(fù)雜度
-
時(shí)間頻度
一個(gè)算法執(zhí)行所耗費(fèi)的時(shí)間，從理論上是不能算出來的，必須上機(jī)運(yùn)行測試才能知道。但我們不可能也沒有必要對每個(gè)算法都上機(jī)測試，只需知道哪個(gè)算法花費(fèi)的時(shí)間多，哪個(gè)算法花費(fèi)的時(shí)間少就可以了。并且一個(gè)算法花費(fèi)的時(shí)間與算法中語句的執(zhí)行次數(shù)成正比例，哪個(gè)算法中語句執(zhí)行次數(shù)多，它花費(fèi)時(shí)間就多。一個(gè)算法中的語句執(zhí)行次數(shù)稱為語句頻度或時(shí)間頻度。記為T(n)。 -
時(shí)間復(fù)雜度
前面提到的時(shí)間頻度T(n)中，n稱為問題的規(guī)模，當(dāng)n不斷變化時(shí)，時(shí)間頻度T(n)也會(huì)不斷變化。但有時(shí)我們想知道它變化時(shí)呈現(xiàn)什么規(guī)律，為此我們引入時(shí)間復(fù)雜度的概念。一般情況下，算法中基本操作重復(fù)執(zhí)行的次數(shù)是問題規(guī)模n的某個(gè)函數(shù)，用T(n)表示，若有某個(gè)輔助函數(shù)f(n)，使得當(dāng)n趨近于無窮大時(shí)，T（n)/f(n)的極限值為不等于零的常數(shù)，則稱f(n)是T(n)的同數(shù)量級函數(shù)，記作T(n)=O(f(n))，它稱為算法的漸進(jìn)時(shí)間復(fù)雜度，簡稱時(shí)間復(fù)雜度。
推導(dǎo)大O階
推導(dǎo)大O階，我們可以按照如下的規(guī)則來進(jìn)行推導(dǎo)，得到的結(jié)果就是大O表示法：
1.用常數(shù)1來取代運(yùn)行時(shí)間中所有加法常數(shù)。
2.修改后的運(yùn)行次數(shù)函數(shù)中，只保留最高階項(xiàng)
3.如果最高階項(xiàng)存在且不是1，則去除與這個(gè)項(xiàng)相乘的常數(shù)。
常數(shù)階
int sum = 0,n = 100; //執(zhí)行一次
sum = (1+n)*n/2; //執(zhí)行一次
System.out.println (sum); //執(zhí)行一次
上面算法的運(yùn)行的次數(shù)的函數(shù)為f(n)=3，根據(jù)推導(dǎo)大O階的規(guī)則1，我們需要將常數(shù)3改為1，則這個(gè)算法的時(shí)間復(fù)雜度為O(1)。如果sum = （1+n）*n/2這條語句再執(zhí)行10遍，因?yàn)檫@與問題大小n的值并沒有關(guān)系，所以這個(gè)算法的時(shí)間復(fù)雜度仍舊是O(1)，我們可以稱之為常數(shù)階。
線性階
int number=1;
while(number<n){
number=number*2;
//時(shí)間復(fù)雜度為O(1)的算法
...
}
對數(shù)階
int number=1;
while(number<n){
number=number*2;
//時(shí)間復(fù)雜度為O(1)的算法
...
}
其他常見復(fù)雜度
除了常數(shù)階、線性階、平方階、對數(shù)階，還有如下時(shí)間復(fù)雜度：
f(n)=nlogn時(shí)，時(shí)間復(fù)雜度為O(nlogn)，可以稱為nlogn階。
f(n)=n3時(shí)，時(shí)間復(fù)雜度為O(n3)，可以稱為立方階。
f(n)=2?時(shí)，時(shí)間復(fù)雜度為O(2?)，可以稱為指數(shù)階。
f(n)=n!時(shí)，時(shí)間復(fù)雜度為O(n!)，可以稱為階乘階。
f(n)=(√n時(shí)，時(shí)間復(fù)雜度為O(√n)，可以稱為平方根階。
