復(fù)雜度分析包括：
- 時(shí)間復(fù)雜度分析
- 空間復(fù)雜度分析
事后統(tǒng)計(jì)法
我們常用事后統(tǒng)計(jì)法來(lái)統(tǒng)計(jì)效率帘腹，這種方法也存在一些問(wèn)題例如：
1陈症，測(cè)試結(jié)果依賴測(cè)試環(huán)境
2盐固，測(cè)試結(jié)果受數(shù)據(jù)規(guī)模的影響很大
大O復(fù)雜度表示法
代碼執(zhí)行時(shí)間隨著數(shù)據(jù)規(guī)模增長(zhǎng)的變化趨勢(shì)看疗，也叫漸進(jìn)時(shí)間復(fù)雜度唆阿，簡(jiǎn)稱時(shí)間復(fù)雜度燥筷。
T(n)=O(logn)
T(n)=O(n)
T(n)=O(n*logn)
T(n)=O(n^2)
一般有這幾種復(fù)雜度
時(shí)間復(fù)雜度分析
在cpu的角度看箩祥，每行代碼都在執(zhí)行類似的操作：讀數(shù)據(jù)-運(yùn)算-寫數(shù)據(jù)，每行簡(jiǎn)單看成一次操作
例如：
int cal(int n) {
int sum = 0;
int i = 1;
int j = 1;
for (; i <= n; ++i) {
j = 1;
for (; j <= n; ++j) {
sum = sum + i * j;
}
}
}
上面代碼可以看成執(zhí)行了（2n^2 + 2n + 3）*unit_time
1肆氓，只關(guān)注循環(huán)執(zhí)行次數(shù)最多的一段代碼
我們?cè)诜治鲆欢未a的時(shí)間復(fù)雜度的時(shí)候袍祖，也只是關(guān)注循環(huán)執(zhí)行次數(shù)最多的那一次代碼。其他的相對(duì)可以忽略不計(jì)
2谢揪，加法法則：總復(fù)雜度等于量級(jí)最大的那段代碼的復(fù)雜度蕉陋。
一段代碼有幾段循環(huán)，例如單次循環(huán)和嵌套循環(huán)拨扶，嵌套循環(huán)的復(fù)雜度是量級(jí)更大的凳鬓。
3，乘法法則：嵌套代碼的復(fù)雜度等于嵌套內(nèi)外代碼的復(fù)雜度的成績(jī)
例如：
int cal(int n) {
int ret = 0;
int i = 1;
for (; i < n; ++i) {
ret = ret + f(i);
}
}
int f(int n) {
int sum = 0;
int i = 1;
for (; i < n; ++i) {
sum = sum + i;
}
return sum;
}
兩個(gè)方法嵌套屈雄，并且是循環(huán)嵌套就等于兩個(gè)復(fù)雜度的積
復(fù)雜度的量級(jí)
- 多項(xiàng)式量級(jí)
常量階O(1)
對(duì)數(shù)階O(logn)
線性階O(n)
線性對(duì)數(shù)階O(nlogn)
平方階O(n^2)
立方階O(n^3)
K次方階O(n^k) -
非多項(xiàng)式量級(jí)
指數(shù)階O(2^n)
階乘階O(n!)
一般非多項(xiàng)式量級(jí)的稱為NP(Non-Deterministic Polynomial)非確定多項(xiàng)式問(wèn)題村视。當(dāng)n越大，執(zhí)行時(shí)間會(huì)急劇增大酒奶，這種算法的時(shí)間復(fù)雜度是非常低效的蚁孔。
復(fù)雜度.jpeg
復(fù)雜度分析有幾種情況
- 最好情況的時(shí)間復(fù)雜度
- 最壞情況的時(shí)間復(fù)雜度
- 平均情況的時(shí)間復(fù)雜度
- 均攤時(shí)間復(fù)雜度
前面三個(gè)都好理解，下面說(shuō)說(shuō)這個(gè)復(fù)雜度分析
/ array表示一個(gè)長(zhǎng)度為n的數(shù)組
// 代碼中的array.length就等于n
int[] array = new int[n];
int count = 0;
void insert(int val) {
if (count == array.length) {
int sum = 0;
for (int i = 0; i < array.length; ++i) {
sum = sum + array[i];
}
array[0] = sum;
count = 1;
}
array[count] = val;
++count;
}
例如上面的例子惋嚎，當(dāng)沒(méi)達(dá)到數(shù)組的長(zhǎng)度的時(shí)候復(fù)雜度是是O(1),在達(dá)到length的時(shí)候復(fù)雜度O(n),想這樣規(guī)律的多個(gè)低階復(fù)雜度+一個(gè)高階復(fù)雜度的情況杠氢，這個(gè)高階復(fù)雜度可以分?jǐn)偟角懊鎛個(gè)低階的復(fù)雜度上。他最終的復(fù)雜度是O(1)另伍，像這種多個(gè)低階可以把一個(gè)高階的給分?jǐn)偟艟褪蔷鶖倧?fù)雜度鼻百。比如ArrayList的insert導(dǎo)致的擴(kuò)容也是一個(gè)道理。
均攤復(fù)雜度也算是一種特殊的平均復(fù)雜度摆尝。
空間復(fù)雜度
時(shí)間復(fù)雜度的全稱是漸進(jìn)時(shí)間復(fù)雜度温艇，標(biāo)識(shí)算法的執(zhí)行時(shí)間與數(shù)據(jù)之間的增長(zhǎng)關(guān)系，類比空間就是漸進(jìn)空間復(fù)雜度堕汞，標(biāo)識(shí)算法的存儲(chǔ)于存儲(chǔ)空間規(guī)模之間的增長(zhǎng)關(guān)系勺爱。
主要的空間復(fù)雜度O(1)、O(n)讯检、O(n^2)琐鲁，而O(logn)卫旱、O(nlogn)基本用不到。
