數(shù)據(jù)復雜度分析
數(shù)據(jù)結(jié)構(gòu)和算法本身解決的快和省的問題史汗；
如何衡量的代碼的執(zhí)行效率琼掠；時間、空間復雜度分析停撞。
1. 測試結(jié)果非常依賴測試環(huán)境
2.測試結(jié)果受數(shù)據(jù)規(guī)模的影響很大
大O復雜度表示法
所有代碼的執(zhí)行時間T(n)與每行代碼的執(zhí)行次數(shù)成正比瓷蛙。
大O時間復雜度表示法。大O時間復雜度實際上并不具體表示代碼真正的執(zhí)行時間怜森，而是表示代碼執(zhí)行時間隨數(shù)據(jù)規(guī)模增長的變化趨勢速挑，所以，也叫作漸進時間復雜度（asymptotic time complexity）副硅，簡稱時間復雜度姥宝。
時間復雜度分析
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行代碼都是常量級的執(zhí)行時間恐疲，與n的大小無關(guān)腊满，所以對于復雜度并沒有影響。循環(huán)執(zhí)行次數(shù)最多的是第4培己、5行代碼碳蛋，所以這塊代碼要重點分析。前面我們也講過省咨，這兩行代碼被執(zhí)行了n次肃弟，所以總的時間復雜度就是O(n)。
2.加法法則：總復雜度等于量級最大的那段代碼的復雜度
3.乘法法則：嵌套代碼的復雜度等于嵌套內(nèi)外代碼復雜度的乘積
幾種常見時間復雜度實例分析
1. O(1)
一般情況下零蓉，只要算法中不存在循環(huán)語句笤受、遞歸語句，即使有成千上萬行的代碼敌蜂，其時間復雜度也是Ο(1)箩兽。
2. O(logn)、O(nlogn)
i=1;
while (i <= n)? {
? i = i * 2;
}
從代碼中可以看出章喉，變量i的值從1開始取汗贫，每循環(huán)一次就乘以2。當大于n時秸脱，循環(huán)結(jié)束落包。還記得我們高中學過的等比數(shù)列嗎？實際上摊唇，變量i的取值就是一個等比數(shù)列妥色。如果我把它一個一個列出來，就應該是這個樣子的：
現(xiàn)在遏片，把代碼稍微改下嘹害，這段代碼的時間復雜度是多少撮竿？
i=1;
while (i <= n)? {
? i = i * 3;
}
根據(jù)我剛剛講的思路，很簡單就能看出來笔呀，這段代碼的時間復雜度為O(log3n)幢踏。
實際上，不管是以2為底许师、以3為底房蝉，還是以10為底，我們可以把所有對數(shù)階的時間復雜度都記為O(logn)微渠。為什么呢搭幻？
空間復雜度分析
時間復雜度的全稱是漸進時間復雜度，表示算法的執(zhí)行時間與數(shù)據(jù)規(guī)模之間的增長關(guān)系逞盆。類比一下檀蹋，空間復雜度全稱就是漸進空間復雜度（asymptotic space complexity），表示算法的存儲空間與數(shù)據(jù)規(guī)模之間的增長關(guān)系云芦。
我們常見的空間復雜度就是O(1)俯逾、O(n)、O(n2 )舅逸，像O(logn)桌肴、O(nlogn)這樣的對數(shù)階復雜度平時都用不到。而且琉历，空間復雜度分析比時間復雜度分析要簡單很多坠七。
