同一問題可用不同算法解決杈抢，而一個(gè)算法的質(zhì)量優(yōu)劣將影響到算法乃至程序的效率希痴。算法分析的目的在于選擇合適算法和改進(jìn)算法。一個(gè)算法的評(píng)價(jià)主要從時(shí)間復(fù)雜度和空間復(fù)雜度來考慮春感。
時(shí)間復(fù)雜度
一般情況下砌创，算法中基本操作重復(fù)執(zhí)行的次數(shù)是問題規(guī)模n的某個(gè)函數(shù)，用T(n)表示鲫懒，若有某個(gè)輔助函數(shù)f(n),存在一個(gè)正常數(shù)c使得fn*c>=T(n)恒成立嫩实。記作T(n)=O(f(n)),稱O(f(n)) 為算法的漸進(jìn)時(shí)間復(fù)雜度，簡稱時(shí)間復(fù)雜度窥岩。
推導(dǎo)大O階
推導(dǎo)攻略:
- 用常數(shù)1取代運(yùn)行時(shí)間中的所有加法常數(shù)
- 在修改后的運(yùn)行次數(shù)函數(shù)中,只保留最高階項(xiàng)
- 如果最高階項(xiàng)存在且不是1,則去除與這個(gè)項(xiàng)相乘的常數(shù)
常數(shù)階
常數(shù)階用O(1)表示
線性階
線性階用O(n)表示
示例:如下代碼的時(shí)間復(fù)雜度即為O(n)
int I ,n = 100, sum = 0;
for(I = 0 ; I < n; I++){
sum = sum + I;
}
平方階
平方階用O(n2)表示
示例:如下代碼的時(shí)間復(fù)雜度即為O(n2)
int I , j , n = 100;
for (I = 0; I < n; I++){
for(j = 0; j < n; j ++ ){
printf("666")
}
}
對(duì)數(shù)階
對(duì)數(shù)階用O(logn)表示
示例:如下代碼的時(shí)間復(fù)雜度即為O(logn)
int I = 1, n = 100;
while(I < n){
I = I * 2
}
//由于2^x = n ,所以x = log(2)n
常見時(shí)間復(fù)雜度
| 時(shí)間復(fù)雜度 | 術(shù)語 | 例子 |
|---|---|---|
| O(1) | 常數(shù)階 | 123 |
| O(n) | 線性階 | 2n+3 |
| O(n2) | 平方 | 3n2+4n+5 |
| O(logn) | 對(duì)數(shù)階 | 3log(2)n + 5 |
| O(nlogn) | nlogn階 | 2n + 3nlog(2)n + 10 |
| O(n3) | 立方階 | n3+3n2+4n+5 |
| O(2^n) | 指數(shù)階 | 2^n |
常見時(shí)間復(fù)雜度耗費(fèi)時(shí)間從小到大依次是: O(1)<O(logn)<(O(n))<O(nlogn)<O(n2)<O(n3)<O(2^n)
空間復(fù)雜度
與時(shí)間復(fù)雜度類似甲献，空間復(fù)雜度是指算法在計(jì)算機(jī)內(nèi)執(zhí)行時(shí)所需存儲(chǔ)空間的度量。記作:
S(n)=O(f(n))
