1. 算法復(fù)雜度初認(rèn)

1. 你循環(huán)的次數(shù)寫成 n 的表達(dá)式，就是時(shí)間復(fù)雜度
2. 你申請(qǐng)的變量數(shù)量寫成 n 的表達(dá)式，就是空間復(fù)雜度
3. 例如計(jì)算 1 到 n 的和，輸入為 n

• 如果你用循環(huán)來(lái)計(jì)算，那么循環(huán)次數(shù)是 n 次，于是時(shí)間復(fù)雜度為 O (n )。 不管 n 是多大，變量最多也就不超過(guò) 5 個(gè)，于是空間復(fù)雜度為 O (5 )，也就是 O (1 )，常數(shù)全變成 1 就對(duì)了
• 如果你用前 n 項(xiàng)和的公式來(lái)計(jì)算，只要一次計(jì)算即可： n(n+1 )/2 ，并沒(méi)有循環(huán)，于是時(shí)間復(fù)雜度為 O (3 )[此處進(jìn)行了三次計(jì)算：+，，/]，常數(shù)變?yōu)?1 就是 O (1 )，變量數(shù)量這里可能只需要兩個(gè)，于是空間復(fù)雜度也為 O (1 )

2. 時(shí)間復(fù)雜度

1. 時(shí)間復(fù)雜度

1. 同一問(wèn)題可用不同算法解決，而一個(gè)算法的質(zhì)量?jī)?yōu)劣將影響到算法乃至程序的效率。算法分析的目的在于選擇合適算法和改進(jìn)算法。
2. 計(jì)算機(jī)科學(xué)中，算法的時(shí)間復(fù)雜度是一個(gè)函數(shù)，它定量描述了該算法的運(yùn)行時(shí)間。這是一個(gè)關(guān)于代表算法輸入值的字符串的長(zhǎng)度的函數(shù)。時(shí)間復(fù)雜度常用大O符號(hào)表述，不包括這個(gè)函數(shù)的低階項(xiàng)和首項(xiàng)系數(shù)。使用這種方式時(shí)，時(shí)間復(fù)雜度可被稱為是漸近的，它考察當(dāng)輸入值大小趨近無(wú)窮時(shí)的情況。
3. 算法復(fù)雜度分為時(shí)間復(fù)雜度和空間復(fù)雜度。其作用：時(shí)間復(fù)雜度是指執(zhí)行算法所需要的計(jì)算工作量；而空間復(fù)雜度是指執(zhí)行這個(gè)算法所需要的內(nèi)存空間。（算法的復(fù)雜性體現(xiàn)在運(yùn)行該算法時(shí)的計(jì)算機(jī)所需資源的多少上，計(jì)算機(jī)資源最重要的是時(shí)間和空間（即寄存器）資源，因此復(fù)雜度分為時(shí)間和空間復(fù)雜度）。

2. 計(jì)算方法

1. 1.一般情況下，算法中基本操作重復(fù)執(zhí)行的次數(shù)是問(wèn)題規(guī)模n的某個(gè)函數(shù)，用T(n)表示，若有某個(gè)輔助函數(shù)f(n),使得當(dāng)n趨近于無(wú)窮大時(shí)，T(n)/f(n)的極限值為不等于零的常數(shù)，則稱f(n)是T(n)的同數(shù)量級(jí)函數(shù)。記作T(n)=O(f(n))，稱O(f(n)) 為算法的漸進(jìn)時(shí)間復(fù)雜度，簡(jiǎn)稱時(shí)間復(fù)雜度。
2. 2. 在計(jì)算時(shí)間復(fù)雜度的時(shí)候，先找出算法的基本操作，然后根據(jù)相應(yīng)的各語(yǔ)句確定它的執(zhí)行次數(shù)，再找出 T(n) 的同數(shù)量級(jí)（它的同數(shù)量級(jí)有以下：1，log2n，n，n log2n ，n的平方，n的三次方，2的n次方，n!），找出后，f(n) = 該數(shù)量級(jí)，若 T(n)/f(n) 求極限可得到一常數(shù)c，則時(shí)間復(fù)雜度T(n) = O(f(n))

3. demo

for(i=1; i<=n; ++i) { 
    for(j=1; j<=n; ++j) { 
        c[i][j] = 0;//該步驟屬于基本操作執(zhí)行次數(shù)：n的平方次 
        for(k=1; k<=n; ++k){ 
            c[i][j] += a[i][k] * b[k][j];//該步驟屬于基本操作執(zhí)行次數(shù)：n的三次方次
        }
    } 
}

1. 則有 T(n) = n 的平方+n的三次方，根據(jù)上面括號(hào)里的同數(shù)量級(jí)，我們可以確定 n的三次方 為T（n）的同數(shù)量級(jí)
2. 則有 f(n) = n的三次方，然后根據(jù) T(n)/f(n) 求極限可得到常數(shù)c
3. 則該算法的時(shí)間復(fù)雜度：T(n) = O(n^3)

4. 總結(jié)

1. 時(shí)間復(fù)雜度比較簡(jiǎn)單的計(jì)算方法是：看看有幾重for循環(huán)，只有一重則時(shí)間復(fù)雜度為O(n)，二重則為O(n^2)，依此類推，如果有二分則為O(logn)，二分例如快速冪、二分查找，如果一個(gè)for循環(huán)套一個(gè)二分，那么時(shí)間復(fù)雜度則為O(nlogn)。

3. 空間復(fù)雜度

1. 一個(gè)算法的空間復(fù)雜度S(n)定義為該算法所耗費(fèi)的存儲(chǔ)空間，它也是問(wèn)題規(guī)模n的函數(shù)?？臻g復(fù)雜度是對(duì)一個(gè)算法在運(yùn)行過(guò)程中臨時(shí)占用存儲(chǔ)空間大小的量度。
2. 一個(gè)算法在計(jì)算機(jī)存儲(chǔ)器上所占用的存儲(chǔ)空間，包括存儲(chǔ)算法本身所占用的存儲(chǔ)空間，算法的輸入輸出數(shù)據(jù)所占用的存儲(chǔ)空間和算法在運(yùn)行過(guò)程中臨時(shí)占用的存儲(chǔ)空間這三個(gè)方面
3. 一個(gè)算法的空間復(fù)雜度只考慮在運(yùn)行過(guò)程中為局部變量分配的存儲(chǔ)空間的大小，它包括為參數(shù)表中形參變量分配的存儲(chǔ)空間和為在函數(shù)體中定義的局部變量分配的存儲(chǔ)空間兩個(gè)部分。
4. 算法的空間復(fù)雜度一般也以數(shù)量級(jí)的形式給出。如當(dāng)一個(gè)算法的空間復(fù)雜度為一個(gè)常量，即不隨被處理數(shù)據(jù)量n的大小而改變時(shí)，可表示為O(1)；當(dāng)一個(gè)算法的空間復(fù)雜度與以2為底的n的對(duì)數(shù)成正比時(shí)，可表示為O(log2n)；當(dāng)一個(gè)算法的空間復(fù)雜度與n成線性比例關(guān)系時(shí)，可表示為O(n)。若形參為數(shù)組，則只需要為它分配一個(gè)存儲(chǔ)由實(shí)參傳送來(lái)的一個(gè)地址指針的空間，即一個(gè)機(jī)器字長(zhǎng)空間；若形參為引用方式，則也只需要為其分配存儲(chǔ)一個(gè)地址的空間，用它來(lái)存儲(chǔ)對(duì)應(yīng)實(shí)參變量的地址，以便由系統(tǒng)自動(dòng)引用實(shí)參變量。

4. 時(shí)間與空間復(fù)雜度比較

1. 對(duì)于一個(gè)算法，其時(shí)間復(fù)雜度和空間復(fù)雜度往往是相互影響的。當(dāng)追求一個(gè)較好的時(shí)間復(fù)雜度時(shí)，可能會(huì)使空間復(fù)雜度的性能變差，即可能導(dǎo)致占用較多的存儲(chǔ)空間；反之，當(dāng)追求一個(gè)較好的空間復(fù)雜度時(shí)，可能會(huì)使時(shí)間復(fù)雜度的性能變差，即可能導(dǎo)致占用較長(zhǎng)的運(yùn)行時(shí)間。
2. 另外，算法的所有性能之間都存在著或多或少的相互影響。因此，當(dāng)設(shè)計(jì)一個(gè)算法（特別是大型算法）時(shí)，要綜合考慮算法的各項(xiàng)性能，算法的使用頻率，算法處理的數(shù)據(jù)量的大小，算法描述語(yǔ)言的特性，算法運(yùn)行的機(jī)器系統(tǒng)環(huán)境等各方面因素，才能夠設(shè)計(jì)出比較好的算法。算法的時(shí)間復(fù)雜度和空間復(fù)雜度合稱為算法的復(fù)雜度。
3. 有兩個(gè)算法A1和A2求解同一問(wèn)題，時(shí)間復(fù)雜度分別是T1(n)=100n2，T2(n)=5n3。（1）當(dāng)輸入量n＜20時(shí)，有T1(n)＞T2(n)，后者花費(fèi)的時(shí)間較少。（2）隨著問(wèn)題規(guī)模n的增大，兩個(gè)算法的時(shí)間開銷之比5n3/100n2=n/20亦隨著增大。即當(dāng)問(wèn)題規(guī)模較大時(shí)，算法A1比算法A2要有效地多。它們的漸近時(shí)間復(fù)雜度O(n2)和O(n3)從宏觀上評(píng)價(jià)了這兩個(gè)算法在時(shí)間方面的質(zhì)量。在算法分析時(shí)，往往對(duì)算法的時(shí)間復(fù)雜度和漸近時(shí)間復(fù)雜度不予區(qū)分，而經(jīng)常是將漸近時(shí)間復(fù)雜度T(n)=O(f(n))簡(jiǎn)稱為時(shí)間復(fù)雜度，其中的f(n)一般是算法中頻度最大的語(yǔ)句頻度。

5. 案例

1. 如果算法的執(zhí)行時(shí)間不隨著問(wèn)題規(guī)模n的增加而增長(zhǎng)，即使算法中有上千條語(yǔ)句，其執(zhí)行時(shí)間也不過(guò)是一個(gè)較大的常數(shù)。此類算法的時(shí)間復(fù)雜度是O(1)。

x=91;
y=100;
while(y>0) {
    if(x>100) {
        x=x-10;
        y--;
    } else{
         x++;
    }
}

解答： T(n)=O(1)，
這個(gè)程序看起來(lái)有點(diǎn)嚇人，總共循環(huán)運(yùn)行了1100次，但是我們看到n沒(méi)有?
沒(méi)。這段程序的運(yùn)行是和n無(wú)關(guān)的，
就算它再循環(huán)一萬(wàn)年，我們也不管他，只是一個(gè)常數(shù)階的函數(shù)

2. 當(dāng)有若干個(gè)循環(huán)語(yǔ)句時(shí)，算法的時(shí)間復(fù)雜度是由嵌套層數(shù)最多的循環(huán)語(yǔ)句中最內(nèi)層語(yǔ)句的頻度f(wàn)(n)決定的。

 x=1; 
for(i=1;i<=n;i++){
    for(j=1;j<=i;j++){
        for(k=1;k<=j;k++){
            x++; 　
        }
    }
} 

該程序段中頻度最大的語(yǔ)句是(x++)，內(nèi)循環(huán)的執(zhí)行次數(shù)雖然與問(wèn)題規(guī)模n沒(méi)有直接關(guān)系，但是卻與外層循環(huán)的變量取值有關(guān)，而最外層循環(huán)的次數(shù)直接與n有關(guān)，因此可以從內(nèi)層循環(huán)向外層分析語(yǔ)句(x++)的執(zhí)行次數(shù)： 則該程序段的時(shí)間復(fù)雜度為T(n)=O(n3/6+低次項(xiàng))=O(n3)

參考
http://blog.csdn.net/booirror/article/details/7707551/
http://www.cnblogs.com/xiaxianfei/p/5385081.html