算法復(fù)雜度分為時間復(fù)雜度和空間復(fù)雜度脐雪。
其作用：
時間復(fù)雜度是指執(zhí)行算法所需要的計算工作量恢共；
而空間復(fù)雜度是指執(zhí)行這個算法所需要的內(nèi)存空間。
（算法的復(fù)雜性體現(xiàn)在運行該算法時的計算機(jī)所需資源的多少上脂信，計算機(jī)資源最重要的是時間和空間（即寄存器）資源透硝，因此復(fù)雜度分為時間和空間復(fù)雜度）。
簡單來說濒生，時間復(fù)雜度指的是語句執(zhí)行次數(shù)，空間復(fù)雜度指的是算法所占的存儲空間
時間復(fù)雜度
計算時間復(fù)雜度的方法：
用常數(shù)1代替運行時間中的所有加法常數(shù)
修改后的運行次數(shù)函數(shù)中丽声，只保留最高階項
去除最高階項的系數(shù)
按數(shù)量級遞增排列规阀，常見的時間復(fù)雜度有：
常數(shù)階O(1),對數(shù)階O(log2n),線性階O(n),
線性對數(shù)階O(nlog2n),平方階O(n2)，立方階O(n3),…歧胁，
k次方階O(nk),指數(shù)階O(2n)厉碟。
隨著問題規(guī)模n的不斷增大，上述時間復(fù)雜度不斷增大箍鼓，算法的執(zhí)行效率越低款咖。
舉個栗子:
sum = n*(n+1)/2; //時間復(fù)雜度O(1)
for(int i = 0; i < n; i++){
printf("%d ",i);
}
//時間復(fù)雜度O(n)
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
printf("%d ",i);
}
}
//時間復(fù)雜度O(n^2)
for(int i = 0; i < n; i++){
for(int j = i; j < n; j++){
printf("%d ",i);
}
}
//運行次數(shù)為(1+n)*n/2
//時間復(fù)雜度O(n^2)
int i = 1, n = 100;
while(i < n){
i = i * 2;
}
//設(shè)執(zhí)行次數(shù)為x. 2^x = n 即x = log2n
//時間復(fù)雜度O(log2n)
最壞時間復(fù)雜度和平均時間復(fù)雜度
最壞情況下的時間復(fù)雜度稱最壞時間復(fù)雜度奄喂。一般不特別說明海洼，討論的時間復(fù)雜度均是最壞情況下的時間復(fù)雜度。
這樣做的原因是：最壞情況下的時間復(fù)雜度是算法在任何輸入實例上運行時間的上界域帐，這就保證了算法的運行時間不會比任何更長是整。
平均時間復(fù)雜度是指所有可能的輸入實例均以等概率出現(xiàn)的情況下，算法的期望運行時間龙优。設(shè)每種情況的出現(xiàn)的概率為pi,平均時間復(fù)雜度則為sum(pi*f(n))
常用排序算法的時間復(fù)雜度
最差時間分析 平均時間復(fù)雜度 穩(wěn)定度 空間復(fù)雜度
冒泡排序 O(n2) O(n2) 穩(wěn)定 O(1)
快速排序 O(n2) O(nlog2n) 不穩(wěn)定 O(log2n)~O(n)
選擇排序 O(n2) O(n2) 穩(wěn)定 O(1)
二叉樹排序 O(n2) O(nlog2n) 不穩(wěn)定 O(n)
插入排序 O(n2) O(n2) 穩(wěn)定 O(1)
堆排序 O(nlog2n) O(nlog2n) 不穩(wěn)定 O(1)
希爾排序 O O 不穩(wěn)定 O(1)
空間復(fù)雜度
空間復(fù)雜度(Space Complexity)是對一個算法在運行過程中臨時占用存儲空間大小的量度舵盈，記做S(n)=O(f(n))。
對于一個算法來說瓦糟，空間復(fù)雜度和時間復(fù)雜度往往是相互影響的赴蝇。當(dāng)追求一個較好的時間復(fù)雜度時，可能會使空間復(fù)雜度的性能變差句伶，即可能導(dǎo)致占用較多的存儲空間考余；反之，當(dāng)追求一個較好的空間復(fù)雜度時楚堤，可能會使時間復(fù)雜度的性能變差，即可能導(dǎo)致占用較長的運行時間衅胀。
有時我們可以用空間來換取時間以達(dá)到目的酥筝。
