目錄：
1.如何評價(jià)算法性能恬叹？
2.大O表示法
3.常見時(shí)間復(fù)雜度大小及其比較
4.一些較為復(fù)雜的實(shí)例
如何評價(jià)算法性能勺疼？
數(shù)據(jù)結(jié)構(gòu)和算法李请，本質(zhì)上是解決現(xiàn)實(shí)存在的問題，即如何讓解決指定問題的代碼運(yùn)行得更快蛙酪？一個(gè)算法如果能在所要求的資源限制(resource constraint)內(nèi)將問題解決好，則稱這個(gè)算法是有效率的(effient)助币。
限制可分為空間限制和時(shí)間限制猴蹂。
而算法的速度，算法需求多少空間如何衡量呢窒所？
你可能會(huì)說鹉勒，我可以通過如下代碼來測試代碼的運(yùn)行時(shí)間：
//JAVA CODE
void calcDuration(){
long begin = System.currentTimeMillis();
function(n);
long end = System.currentTimeMillis();
}
我們可以通過end-begin來計(jì)算出function()的執(zhí)行時(shí)間。這類“事后統(tǒng)計(jì)”的方法用來評估算法執(zhí)行效率是正確的吵取，但是它也有它的局限性：
受不同機(jī)器配置的影響禽额，結(jié)果差異不同，甚至同一段算法皮官，在不同機(jī)器上跑出來的結(jié)果差異很大脯倒。
算法的測試結(jié)果受輸入的規(guī)模影響很大，也就是說捺氢，輸入不同規(guī)模的數(shù)據(jù)藻丢，結(jié)果差別非常大。
能不能事先“算”出算法的執(zhí)行效率呢摄乒？這就引出了以下兩個(gè)概念：時(shí)間復(fù)雜度悠反，空間復(fù)雜度。
大O表示法
首先看一個(gè)簡單的例子：
void foo(){
for(int i =0;i<n;i++){//執(zhí)行了n次
System.out.println("Hello world");//執(zhí)行了n次
}
System.out.println("function over");//執(zhí)行了1次
}
在上述例子中馍佑，第1行的代碼總共執(zhí)行了n次斋否，第2行的代碼總共執(zhí)行n次，第4行代碼會(huì)執(zhí)行1次拭荤。
這里假設(shè)計(jì)算機(jī)處理語句代價(jià)(如：賦值如叼，自增，輸出等)都為c穷劈；(當(dāng)然笼恰，可以擬定一個(gè)最小單位踊沸，讓所有語句的代價(jià)與c成正比)。
假設(shè)算法總執(zhí)行時(shí)間為T(n)社证，其中n為問題的規(guī)模逼龟；
那么上述代碼的總執(zhí)行時(shí)間：T(n) = (2n +1)c
可以看出，T(n)與代碼的總執(zhí)行次數(shù)總是成正比的追葡，即與(2*n+1)成正比腺律；
我們將代碼執(zhí)行次數(shù)用f(n)來表示，即f(n) = 2*n+1宜肉。
我們算出了代碼的執(zhí)行次數(shù)后匀钧，如何表示算法的復(fù)雜度呢？
在計(jì)算機(jī)中谬返，我們一般采用大O漸進(jìn)表示法來表示算法的復(fù)雜度之斯。即
T(n) = O(f(n))
將上述f(n)帶入，我們得出T(n) = O(n),因此遣铝，上述算法的時(shí)間復(fù)雜度為O(n),細(xì)心的同學(xué)發(fā)現(xiàn)了佑刷，f(n)不是等于2*n+1嗎？酿炸，為什么到里面就沒有了呢瘫絮？
其實(shí)大O并不是表示代碼真正的執(zhí)行時(shí)間，而是代碼執(zhí)行時(shí)間隨著數(shù)據(jù)規(guī)模增長的變化趨勢填硕。具有以下特點(diǎn)：
1.不保留系數(shù)麦萤；
2.且只保留最高階的項(xiàng)。
這里稍微解釋下第二條扁眯，低階項(xiàng)在問題規(guī)模n慢慢增大的時(shí)候壮莹，對結(jié)果影響慢慢變小，所以在計(jì)算時(shí)間復(fù)雜度的時(shí)候恋拍，可以省去垛孔。可以把大O符號想象成一個(gè)過濾形的一個(gè)漏斗施敢，過濾那些系數(shù)以及低階的項(xiàng)周荐。
比如:f(n) = 2n^2+5n+1; 則時(shí)間復(fù)雜度記為O（n^2）
常見算法復(fù)雜度大小及其比較
O(1)<O(logn)<O(n)<O(nlogn)<O(n)<O(n^2) <O(2^n)<O(n!)
log函數(shù)統(tǒng)一以2為底。
以上是算法復(fù)雜度大小與比較僵娃，需要注意的是除開O(2^n)與O（n!）外其他的被稱為多項(xiàng)式時(shí)間概作，這個(gè)概念后續(xù)會(huì)再次提及（NP問題）現(xiàn)在你只需要知道多項(xiàng)式是什么概念就行了。
另外我在初學(xué)的時(shí)候經(jīng)常分不清2^n與n!的大小比較
其實(shí)你把他展開來看就好了默怨。
2 *2 *2 *2.....(n個(gè)2)
1 *2 *3 *4.....(n個(gè)數(shù))
這樣是不是就清楚了呢讯榕？
一些較為復(fù)雜的實(shí)例
實(shí)例1
for(int i =0;i<n;i++){
for(int j = 0;j<m;j++){
System.out.println("sth");/*運(yùn)行m*n次*/
}
}
在做時(shí)間復(fù)雜度題目的時(shí)候，我們往往只需要注意哪些語句頻度最高的語句，比如上例中的第三行愚屁，總計(jì)會(huì)運(yùn)行m*n次济竹，所以上例的時(shí)間復(fù)雜度為O(mn)。注意：一般問題規(guī)模我們會(huì)用n來表示霎槐，但是經(jīng)常會(huì)有多個(gè)影響問題規(guī)模的參數(shù)出現(xiàn)送浊，比如上例。
實(shí)例2
int i =1;
while(i<=n){
i = i*2;
}
很多初學(xué)者看到上面的代碼就頭大丘跌，不知道分析袭景，實(shí)際上這道題就是問:
i = i*2會(huì)運(yùn)行多少次? 等價(jià)于
1 * 2 * 2 * 2.....*2 = n，有多少個(gè)乘2? 等價(jià)于
2^k = n闭树，求k
所以k = logn 耸棒，所以，時(shí)間復(fù)雜度為O(logn)
稍微變形下报辱，如果替換成語句i = i*3或者其他的呢与殃？？
我們可以根據(jù)上述公式捏肢，把任意不以2為低的log函數(shù)奈籽，換成以2為低饥侵，而大O符號又是省略系數(shù)的鸵赫，所以不管是i = i*3，i = i * 4躏升，i = i * 5辩棒，...都統(tǒng)一記為O(logn)。
實(shí)例3
void foo(int m){
for(int i = 0;i<m;i++)
System.out.println("sth");
}
void koo(int n){
for(int i =0;i<n;i++)
foo(n);//第7行
}
我們要求koo函數(shù)的時(shí)間復(fù)雜度膨疏，由于koo函數(shù)的內(nèi)部又調(diào)用了foo一睁，所以將koo的內(nèi)部看成一個(gè)雙層for循環(huán)，所以koo的時(shí)間復(fù)雜度為O(n^2)佃却。
思考：如果將第7行的調(diào)用改成foo(i)呢者吁？
實(shí)例4
int Fib(int n){//斐波那契數(shù)列
if(n<3) return 1;
else return Fib(n-1)+Fib(n-2);
}
上述實(shí)例是求斐波那契數(shù)列的遞歸形式，遞歸算法的時(shí)間復(fù)雜度往往更難求得饲帅，畫出調(diào)用過程為下圖：
遞歸算法的復(fù)雜度复凳，為這顆二叉樹的節(jié)點(diǎn)數(shù)。
我們知道滿二叉樹的節(jié)點(diǎn)數(shù)為2^h -1,其中h為樹的高度灶泵，那樹的高度怎么求呢育八？
我們可以看紅線部分表示這棵樹每一層最左邊的節(jié)點(diǎn)，它的特征很明顯赦邻，等于n-1（n是輸入規(guī)模）髓棋。所以這個(gè)算法的最終復(fù)雜度為O(2^n)。
值得一提的是，這是一種非常不好的寫法按声。有很多求斐波那契數(shù)列好的算法膳犹，暫時(shí)就不再贅述了。
