數(shù)據(jù)復(fù)雜度分析
數(shù)據(jù)結(jié)構(gòu)和算法本身解決的快和省的問題；
如何衡量的代碼的執(zhí)行效率；時(shí)間、空間復(fù)雜度分析。
1. 測(cè)試結(jié)果非常依賴測(cè)試環(huán)境
2.測(cè)試結(jié)果受數(shù)據(jù)規(guī)模的影響很大
大O復(fù)雜度表示法
所有代碼的執(zhí)行時(shí)間T(n)與每行代碼的執(zhí)行次數(shù)成正比。
大O時(shí)間復(fù)雜度表示法。大O時(shí)間復(fù)雜度實(shí)際上并不具體表示代碼真正的執(zhí)行時(shí)間，而是表示代碼執(zhí)行時(shí)間隨數(shù)據(jù)規(guī)模增長(zhǎng)的變化趨勢(shì)，所以，也叫作漸進(jìn)時(shí)間復(fù)雜度（asymptotic time complexity），簡(jiǎn)稱時(shí)間復(fù)雜度。
時(shí)間復(fù)雜度分析
1.只關(guān)注循環(huán)執(zhí)行次數(shù)最多的一段代碼
int cal(int n) {
? int sum = 0;
? int i = 1;
? for (; i <= n; ++i) {
? ? sum = sum + i;
? }
? return sum;
}
其中第2、3行代碼都是常量級(jí)的執(zhí)行時(shí)間，與n的大小無關(guān)，所以對(duì)于復(fù)雜度并沒有影響。循環(huán)執(zhí)行次數(shù)最多的是第4、5行代碼，所以這塊代碼要重點(diǎn)分析。前面我們也講過，這兩行代碼被執(zhí)行了n次，所以總的時(shí)間復(fù)雜度就是O(n)。
2.加法法則：總復(fù)雜度等于量級(jí)最大的那段代碼的復(fù)雜度
3.乘法法則：嵌套代碼的復(fù)雜度等于嵌套內(nèi)外代碼復(fù)雜度的乘積
幾種常見時(shí)間復(fù)雜度實(shí)例分析
1. O(1)
一般情況下，只要算法中不存在循環(huán)語句、遞歸語句，即使有成千上萬行的代碼，其時(shí)間復(fù)雜度也是Ο(1)。
2. O(logn)、O(nlogn)
i=1;
while (i <= n)? {
? i = i * 2;
}
從代碼中可以看出，變量i的值從1開始取，每循環(huán)一次就乘以2。當(dāng)大于n時(shí)，循環(huán)結(jié)束。還記得我們高中學(xué)過的等比數(shù)列嗎？實(shí)際上，變量i的取值就是一個(gè)等比數(shù)列。如果我把它一個(gè)一個(gè)列出來，就應(yīng)該是這個(gè)樣子的：
現(xiàn)在，把代碼稍微改下，這段代碼的時(shí)間復(fù)雜度是多少？
i=1;
while (i <= n)? {
? i = i * 3;
}
根據(jù)我剛剛講的思路，很簡(jiǎn)單就能看出來，這段代碼的時(shí)間復(fù)雜度為O(log3n)。
實(shí)際上，不管是以2為底、以3為底，還是以10為底，我們可以把所有對(duì)數(shù)階的時(shí)間復(fù)雜度都記為O(logn)。為什么呢？
空間復(fù)雜度分析
時(shí)間復(fù)雜度的全稱是漸進(jìn)時(shí)間復(fù)雜度，表示算法的執(zhí)行時(shí)間與數(shù)據(jù)規(guī)模之間的增長(zhǎng)關(guān)系。類比一下，空間復(fù)雜度全稱就是漸進(jìn)空間復(fù)雜度（asymptotic space complexity），表示算法的存儲(chǔ)空間與數(shù)據(jù)規(guī)模之間的增長(zhǎng)關(guān)系。
我們常見的空間復(fù)雜度就是O(1)、O(n)、O(n2 )，像O(logn)、O(nlogn)這樣的對(duì)數(shù)階復(fù)雜度平時(shí)都用不到。而且，空間復(fù)雜度分析比時(shí)間復(fù)雜度分析要簡(jiǎn)單很多。
