算法時間復(fù)雜度
函數(shù)漸近增長
算法中執(zhí)行次數(shù)最多的那條語句就是基本語句倦炒，測定運(yùn)行時間就是計(jì)算基本語句的==執(zhí)行次數(shù)==
- 可以忽略加法常數(shù)
- 與最高此項(xiàng)相乘的常數(shù)并不重要
- 最高次項(xiàng)的指數(shù)越大，增長越快
- 判斷一個算法執(zhí)行效率時，函數(shù)中的常數(shù)和其他次要項(xiàng)常成液唬可以忽略，更應(yīng)該關(guān)注主項(xiàng)（最高階項(xiàng)）的階數(shù)
- 某個算法，隨著n增大惊暴，它會越來越優(yōu)于另一算法，或者越來越差與另一算法趁桃。
大O表示法
我們一般使用O(f(n))來體現(xiàn)算法的復(fù)雜度辽话。
推導(dǎo)大O階的方法
- 用常數(shù)1取代運(yùn)行時間中的所有加法常數(shù)
- 在修改后的運(yùn)行次數(shù)函數(shù)中，只保留最高階項(xiàng)
- 如果最高階項(xiàng)存在并且不是1卫病，則去除與這個項(xiàng)相乘的常數(shù)油啤。
得到的結(jié)果就是大O階
常數(shù)階
int sum = 0,n = 100; //執(zhí)行一次
sum = (1+n)*n/2; //執(zhí)行一次
printf（"%d",sum）; //執(zhí)行一次
上面算法的運(yùn)行的次數(shù)的函數(shù)為f(n)=3，根據(jù)推導(dǎo)大O階的規(guī)則1忽肛，我們需要將常數(shù)3改為1村砂，則這個算法的時間復(fù)雜度為O(1)。如果sum = （1+n）*n/2這條語句再執(zhí)行10遍屹逛，因?yàn)檫@與問題大小n的值并沒有關(guān)系础废，所以這個算法的時間復(fù)雜度仍舊是O(1)，我們可以稱之為常數(shù)階罕模。
線性階
線性階主要分析循環(huán)結(jié)構(gòu)的運(yùn)行情況
for(int i=0;i<n;i++){
//時間復(fù)雜度為O(1)的算法...}
上面算法循環(huán)體中的代碼執(zhí)行了n次评腺，因此時間復(fù)雜度為O(n)。
對數(shù)階
int number=1;
while(number<n)
{number=number*2}
可以看出上面的代碼淑掌，隨著number每次乘以2后蒿讥，都會越來越接近n，當(dāng)number不小于n時就會退出循環(huán)抛腕。假設(shè)循環(huán)的次數(shù)為X芋绸，則由2^x=n得出x=log?n，因此得出這個算法的時間復(fù)雜度為O(logn)担敌。
平方階
//嵌套循環(huán)
for(int i=0;i<n;i++){
for(int j=0;j<n;i++){
//復(fù)雜度為O(1)的算法 ...
}
}
內(nèi)層循環(huán)的時間復(fù)雜度在講到線性階時就已經(jīng)得知是O(n)摔敛，現(xiàn)在經(jīng)過外層循環(huán)n次，那么這段算法的時間復(fù)雜度則為O(n2)全封。
常用的時間復(fù)雜度按照耗費(fèi)的時間從小到大依次是：
O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(n3)<O(2?)<O(n!)
像O(n3)马昙，過大的n都會使得結(jié)果變得不現(xiàn)實(shí)。同樣指數(shù)階O(2?)和階乘階O(n!)的等刹悴，除非是很小的n值行楞，否則哪怕n只是100，都是噩夢般的運(yùn)行時間土匀。這種不切實(shí)際的算法復(fù)雜度子房，一般我們都不會去討論它。
——《大話數(shù)據(jù)結(jié)構(gòu)》
最壞情況和平均情況
- 舉個例子恒削，在查找遍歷的時候池颈，有可能在位置1就找到了尾序，這是最好的情況；也有可能到n才能找到躯砰，這是最壞情況每币。
- 平均運(yùn)行時間是以上例子的n/2，平均運(yùn)行時間是最有意義的琢歇，因?yàn)樗?strong>期望的運(yùn)行時間兰怠。
- 一般在沒有特殊說明的情況下，計(jì)算算法時間復(fù)雜度都是指最壞時間復(fù)雜度
算法空間復(fù)雜度
類似于時間復(fù)雜度的討論李茫，一個算法的空間復(fù)雜度(Space Complexity)S(n)定義為該算法所耗費(fèi)的存儲空間揭保，它也是問題規(guī)模n的函數(shù)。漸近空間復(fù)雜度也常常簡稱為空間復(fù)雜度魄宏。
空間復(fù)雜度(Space Complexity)是對一個算法在運(yùn)行過程中臨時占用存儲空間大小的量度秸侣。
一個算法在計(jì)算機(jī)存儲器上所占用的存儲空間，包括存儲算法本身所占用的存儲空間宠互，算法的輸入輸出數(shù)據(jù)所占用的存儲空間和算法在運(yùn)行過程中臨時占用的存儲空間這三個方面味榛。算法的輸入輸出數(shù)據(jù)所占用的存儲空間是由要解決的問題決定的，是通過參數(shù)表由調(diào)用函數(shù)傳遞而來的予跌，它不隨本算法的不同而改變搏色。
存儲算法本身所占用的存儲空間與算法書寫的長短成正比，要壓縮這方面的存儲空間券册，就必須編寫出較短的算法频轿。
如當(dāng)一個算法的空間復(fù)雜度為一個常量，即不隨被處理數(shù)據(jù)量n的大小而改變時烁焙，可表示為O(1)航邢；當(dāng)一個算法的空間復(fù)雜度與以2為底的n的對數(shù)成正比時，可表示為0(10g2n)骄蝇；當(dāng)一個算法的空I司復(fù)雜度與n成線性比例關(guān)系時翠忠，可表示為0(n).若形參為數(shù)組，則只需要為它分配一個存儲由實(shí)參傳送來的一個地址指針的空間乞榨，即一個機(jī)器字長空間；若形參為引用方式当娱，則也只需要為其分配存儲一個地址的空間吃既，用它來存儲對應(yīng)實(shí)參變量的地址，以便由系統(tǒng)自動引用實(shí)參變量跨细。
