時(shí)間、空間復(fù)雜度：衡量算法執(zhí)行小路的指標(biāo)，數(shù)據(jù)結(jié)構(gòu)與算法離不開(kāi)時(shí)間儒洛、空間復(fù)雜度分析，復(fù)雜度分析是算法的精髓狼速。
為什么需要分析復(fù)雜度
為什么不直接去運(yùn)行代碼然后測(cè)試運(yùn)行速度琅锻？
1、環(huán)境影響大
不同的硬件條件下處理器的處理速度不一樣導(dǎo)致的性能差
2向胡、數(shù)據(jù)集對(duì)結(jié)果的影響
如果數(shù)據(jù)規(guī)模較小恼蓬，測(cè)試結(jié)果就無(wú)法真實(shí)反映算法效率
復(fù)雜度分析是一個(gè)不需要具體測(cè)試數(shù)據(jù)來(lái)測(cè)試，粗略計(jì)算出執(zhí)行效率的一種方法僵芹。
大O復(fù)雜度表示法
算法復(fù)雜度其實(shí)就是算法代碼執(zhí)行的時(shí)間处硬。
如何不運(yùn)行代碼粗略估算時(shí)間：
int sum(int n){
int i=0;
int sum=0;
for(;i<n;i++){
sum+=i;
}
return sum;
}
用上面這個(gè)累加算法為例子說(shuō)明，因?yàn)槭谴致杂?jì)算拇派，現(xiàn)在假定CPU執(zhí)行一行代碼的時(shí)間為t荷辕，然后整個(gè)sum方法的執(zhí)行時(shí)間為：1+1+n+n+1=(2n+3)*t;可以看出代碼總的執(zhí)行時(shí)間和n成正比，總結(jié)出大O表示公式為：
其中件豌，T（n）表示代碼執(zhí)行的時(shí)間疮方，n為數(shù)據(jù)集規(guī)模，f(n)是一個(gè)公式茧彤，以上述例子說(shuō)明就是2n+3骡显，所以T(n)=O(2n+3),
大O表示法只是代表代碼執(zhí)行的時(shí)間的變化趨勢(shì)，并不能得出真正執(zhí)行時(shí)間曾掂，所以也叫漸進(jìn)時(shí)間復(fù)雜度惫谤，簡(jiǎn)稱(chēng)時(shí)間復(fù)雜度。當(dāng)n趨向于很大時(shí)珠洗，常數(shù)項(xiàng)的影響微乎其微溜歪，所以我們常常將常公式中公式中的低階、常量许蓖、系數(shù)三部分去掉蝴猪。所以富岳，上述例子就可以表示為：
常用時(shí)間復(fù)雜度分析方法：
1、只關(guān)注循環(huán)最多的一段代碼
由于大O復(fù)雜度表示方法只是表示一種變化趨勢(shì)拯腮，常量窖式、低階和系數(shù)這些并不會(huì)對(duì)變化趨勢(shì)造成很大影響，所以我們一般選擇忽略动壤。
2萝喘、加法法則
如下代碼：
int cal(int n) {
int sum_1 = 0;
int p = 1;
//T1
for (; p < 100; ++p) {
sum_1 = sum_1 + p;
}
int sum_2 = 0;
int q = 1;
//T2
for (; q < n; ++q) {
sum_2 = sum_2 + q;
}
int sum_3 = 0;
int i = 1;
int j = 1;
//T3
for (; i <= n; ++i) {
j = 1;
for (; j <= n; ++j) {
sum_3 = sum_3 + i * j;
}
}
return sum_1 + sum_2 + sum_3;
}
我們只關(guān)注循環(huán)部分，T1琼懊、T2阁簸、T3，由于T1只循環(huán)100此哼丈，跟n無(wú)關(guān)启妹，可以忽略，T2=O(n),T3=O(n^2),有這么一個(gè)結(jié)論：代碼總的時(shí)間復(fù)雜度等于量級(jí)最大的那段代碼的時(shí)間復(fù)雜度：
所以上面這個(gè)例子的時(shí)間復(fù)雜度為O(n^2)
3醉旦、乘法法則
例子：
//Tn
int fun1(int n) {
int sum1 = 0;
int i = 1;
//T1
for (; i < n; ++i) {
sum = ret + f(i);
}
}
int fun2(int n) {
int sum2 = 0;
int i = 1;
//T2
for (; i < n; ++i) {
sum2 = sum2 + i;
}
return sum2;
}
由于T1里循環(huán)執(zhí)行了fun2方法饶米，fun2里T2=O(n),T1也是O(n)，所以總的時(shí)間復(fù)雜度就是：
總結(jié)乘法公式：
若:T1(n)=O(f(n))车胡，T2(n)=O(g(n)),則Tn=T1(n)T2(n)=O(f(n))O(g(n))=O(f(n)*g(n))
常見(jiàn)復(fù)雜度量級(jí)
| 多項(xiàng)式量級(jí) | 非多項(xiàng)式量級(jí) |
|---|---|
| 常量階O(1) | 指數(shù)階O(2^n) |
| 對(duì)數(shù)階O(logn) | 階乘階O(n!) |
| 線性階O(n) | |
| 線性對(duì)數(shù)階O(nlogn) | |
| N次方臺(tái)階O(n^N) |
差別：非多項(xiàng)式階在數(shù)據(jù)隨著n增大檬输，時(shí)間會(huì)爆炸式增加，這類(lèi)是非常低效的算法匈棘，不推薦使用丧慈。
1、O(1)
常量級(jí)復(fù)雜度主卫，比如代碼只有5行10行或者1000行這些逃默，只要代碼的執(zhí)行時(shí)間不隨n增大而增大，有限數(shù)量級(jí)的都?xì)w為O(1)復(fù)雜度簇搅；我們平時(shí)在分析時(shí)完域，只要代碼不存在循環(huán)、遞歸語(yǔ)句馍资，代碼再多筒主，也可以算是O(1)復(fù)雜度。
2鸟蟹、O(logn)、O(nlogn)
對(duì)數(shù)階復(fù)雜度使兔，比如下面這樣的代碼：
int i=1;
while(i<=n){
i=i*2;
}
循環(huán)終結(jié)條件是i<=n,
n=2^x,求出x就能得出代碼建钥，其中
舉個(gè)栗子：我們上面的2換成3熊经，會(huì)有復(fù)雜度為:
上面說(shuō)過(guò)分析復(fù)雜度時(shí)常數(shù)可以去掉不算泽艘，推導(dǎo)下來(lái)還是會(huì)算回以2為底時(shí)一樣的復(fù)雜度，因此镐依，我們可以將對(duì)數(shù)的底忽略掉匹涮，統(tǒng)一用O(logn)表示。
3槐壳、O(m+n)
m然低、n為兩個(gè)不同數(shù)量級(jí)的數(shù)據(jù)，且無(wú)法確定誰(shuí)大誰(shuí)小务唐，也就不能根據(jù)前面的加法法則來(lái)說(shuō)勝率掉某一個(gè)雳攘，這個(gè)時(shí)候算法復(fù)雜度就得改為：
T(n)=T1(m)+T2(n)=O(f(m))+O(f(n))=O(m+n)
空間復(fù)雜度
算法復(fù)雜度分時(shí)間復(fù)雜度和空間復(fù)雜度，上面分析了時(shí)間復(fù)雜度枫笛，空間復(fù)雜度分析原理是一樣的吨灭，時(shí)間復(fù)雜度算的是代碼運(yùn)行的時(shí)間，而空間復(fù)雜度則算代碼所占用的內(nèi)存大小刑巧，舉個(gè)栗子：
void fun(int n){
int i=1;
int[] arr=new int[n];
for(;i<n;i++){
arr[i]=i;
}
}
跟時(shí)間復(fù)雜度一樣喧兄，i常量聲明所占用的空間為1，可以忽略啊楚，我們著重看循環(huán)部分繁莹，沒(méi)循環(huán)一次就要申請(qǐng)一次內(nèi)存，所以整個(gè)代碼的空間復(fù)雜度為O(n)特幔。
最好咨演、最壞時(shí)間復(fù)雜度
例子：
int findItem(int[] array,int x){
int n=array.lenth;
int item=-1;
for(int i=0;i<n;i++){
if(array[i]==x){
return i;
}
}
return item;
}
上面這段代碼是在一個(gè)數(shù)組中找到某個(gè)值的下標(biāo)，這段代碼的復(fù)雜度如果用上面介紹的幾種方法是沒(méi)辦法準(zhǔn)確得出復(fù)雜度的蚯斯，分析它需要用到新的復(fù)雜度概念：最好薄风、最壞時(shí)間復(fù)雜度；加入我們要找的元素在第一個(gè)位置拍嵌，那么只要運(yùn)行一次的循環(huán)就可以結(jié)束代碼遭赂，那么復(fù)雜度就是O(1),如果很不幸，我們要找的元素根本不在數(shù)組中横辆，那么就會(huì)出現(xiàn)需要循環(huán)n次才能結(jié)束代碼撇他，那么此時(shí)的復(fù)雜度就變?yōu)镺(n)了，這兩個(gè)就是分別對(duì)應(yīng)最好狈蚤、最壞時(shí)間復(fù)雜度困肩。
平均時(shí)間復(fù)雜度
前面的最好最壞時(shí)間復(fù)雜度對(duì)應(yīng)的都是極端情況下的復(fù)雜度，沒(méi)辦法作為衡量算法好壞的標(biāo)準(zhǔn)脆侮，所以就引入了平均時(shí)間復(fù)雜度锌畸。我們繼續(xù)分析上面的代碼例子，首先列出所有的可能靖避，一共會(huì)有n+1中情況潭枣，當(dāng)我們要找的元素在數(shù)組n到n-1中某一個(gè)時(shí)有n中可能比默，此時(shí)需要遍歷的次數(shù)分別為1到n次，再加上一種就是元素不在數(shù)組中盆犁，此時(shí)也需要遍歷n次命咐，所以一共需要遍歷的次數(shù)加起來(lái)就是1+2+3+...+n+n，然后算一下每一項(xiàng)的概率谐岁，由于存在在或者不在數(shù)組的情況醋奠，假定概率都為1/2，然后在的情況下每項(xiàng)的概率又為1/n翰铡，所以組合起來(lái)就是1/2n,然后開(kāi)始求和钝域，公式為：
N=1*1/2n+2*1/2n+3*1/2n+...+n*1/2n+n*1/2
最后這個(gè)n為要找的元素不在數(shù)組里，所以乘上的概率是1/2.
所以平均時(shí)間復(fù)雜度O(n)為：
均攤時(shí)間復(fù)雜度
均攤時(shí)間復(fù)雜度分析的情況是锭魔，比如一個(gè)算法例证，在大多數(shù)情況下復(fù)雜度都為O(1),但當(dāng)符合某個(gè)條件時(shí)會(huì)變?yōu)镺(n)，然后這個(gè)時(shí)候均攤時(shí)間復(fù)雜度就能有所用處了迷捧。比如java中ArrayList的自動(dòng)擴(kuò)容：
add()方法的源碼如下：
public boolean add(E e) {
ensureCapacityInternal(size + 1);
elementData[size++] = e;//添加對(duì)象時(shí)织咧，自增size
return true;
}
private void ensureCapacityInternal(int minCapacity) {
modCount++;//定義于ArrayList的父類(lèi)AbstractList，用于存儲(chǔ)結(jié)構(gòu)修改次數(shù)
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);//新容量擴(kuò)大到原容量的1.5倍漠秋，右移一位相關(guān)于原數(shù)值除以2笙蒙。
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;//MAX_ARRAY_SIZE和Integer.MAX_VALUE為常量，詳細(xì)請(qǐng)參閱下面的注解
}
在容量充足的情況下庆锦，只需要執(zhí)行插入操作捅位，此時(shí)復(fù)雜度為O(1),但是當(dāng)容量滿(mǎn)了的時(shí)候，就需要擴(kuò)容搂抒，此時(shí)的復(fù)雜度變?yōu)镺(n)艇搀，然后算均攤時(shí)間復(fù)雜度，假設(shè)在到達(dá)剛好擴(kuò)容的數(shù)據(jù)一共有n個(gè)求晶，那么前n種復(fù)雜度都為O(1),第n此為O(n)焰雕，每種情況的概率都為1/n+1,最后：
總結(jié)
基本復(fù)雜度分析到這就學(xué)完了，這些方法都會(huì)貫穿整個(gè)算法學(xué)習(xí)的全部芳杏，所以要牢固掌握矩屁。
