一、概念
1.時間復(fù)雜度
這個與耗時并無直接聯(lián)系。時間復(fù)雜度的計算并不是計算程序具體運(yùn)行的時間财骨，而是算法執(zhí)行語句的次數(shù)。簡而言之，就是計算機(jī)執(zhí)行一個算法快慢的量度體現(xiàn)隆箩。
2.空間復(fù)雜度
Space Complexity
解決一個實際問題可能有多種算法來實現(xiàn)该贾，但是運(yùn)行時候所占用的內(nèi)存可能是不同的，空間復(fù)雜度是對一個算法在運(yùn)行過程中臨時占用存儲空間大小的量度體現(xiàn)摘仅。
二靶庙、表示
1.時間復(fù)雜度
我們一般用“大O符號表示法”來表示時間復(fù)雜度：T(n) = O(f(n))
n是影響復(fù)雜度變化的因子，f(n)是復(fù)雜度具體的算法娃属。
常見的時間復(fù)雜度量級
常數(shù)階O(1)
線性階O(n)
對數(shù)階O(log ?n)
線性對數(shù)階O(nlogN)
平方階O(n2)
立方階O(n3)
K次方階O(n^k)
指數(shù)階(2^n)
常用的時間復(fù)雜度所耗費(fèi)的時間從小到大依次是：
O(1) < O(log ?n) <O (n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)
2.空間復(fù)雜度
空間復(fù)雜度是對一個算法在運(yùn)行過程中臨時占用存儲空間大小的一個量度六荒，同樣反映的是一個趨勢，我們用 S(n) 來定義矾端，一般也作為問題規(guī)模n的函數(shù)掏击，以數(shù)量級形式給出。
空間復(fù)雜度比較常用的有：O(1)秩铆、O(n)砚亭、O(n2)，
三殴玛、復(fù)雜度計算
1.時間復(fù)雜度
求解算法的時間復(fù)雜度的具體步驟是：
⑴ 找出算法中的基本語句捅膘；算法中執(zhí)行次數(shù)最多的那條語句就是基本語句，通常是最內(nèi)層循環(huán)的循環(huán)體滚粟。
⑵ 計算基本語句的執(zhí)行次數(shù)的數(shù)量級寻仗；
只需計算基本語句執(zhí)行次數(shù)的數(shù)量級，這就意味著只要保證基本語句執(zhí)行次數(shù)的函數(shù)中的最高次冪正確即可凡壤，可以忽略所有低次冪和最高次冪的系數(shù)署尤。
⑶ 用大Ο記號表示算法的時間性能。將基本語句執(zhí)行次數(shù)的數(shù)量級放入大Ο記號中亚侠。
如果算法中包含嵌套的循環(huán)曹体，則基本語句通常是最內(nèi)層的循環(huán)。
時間復(fù)雜度為:O(1)
private int getSum(int a) {
int sum = 0;
sum=sum+a;
return sum;
}
時間復(fù)雜度用來表示代碼執(zhí)行時間的增長變化趨勢的硝烂。上面的算法并沒有隨著變量的增長而增長耗費(fèi)時間箕别，那么無論這類代碼有多長，都可以用O(1)來表示它的時間復(fù)雜度钢坦。
時間復(fù)雜度為:O(n)
int i=0;
while (i < n && arr[i]!=1){
i++;
}
這段代碼究孕，for循環(huán)里面的代碼會執(zhí)行n遍，因此它消耗的時間是隨著n的變化而變化的爹凹，因此這類代碼都可以用O(n)來表示它的時間復(fù)雜度厨诸。但是如果arr[i]等于1的話，則循環(huán)執(zhí)行一次判斷跳出禾酱，時間復(fù)雜度是O(1)微酬。
時間復(fù)雜度為:O(log ?n)
int i = 1;
while(i<n){
i = i * 2;
}
從上面代碼可以看到绘趋，在while循環(huán)里面，每次都將 i 乘以 2颗管，乘完之后陷遮，i 距離 n 就越來越近了。我們試著求解一下垦江，假設(shè)循環(huán)x次之后帽馋，i 就大于 2 了，此時這個循環(huán)就退出了比吭，也就是說 2 的 x 次方等于 n绽族，那么 x = log2^n
也就是說當(dāng)循環(huán) log2^n 次以后，這個代碼就結(jié)束了衩藤。因此這個代碼的時間復(fù)雜度為：O(logn)
時間復(fù)雜度為:O(nlogN)
for(m=1; m<n; m++){
i = 1;
while(i<n) {
i = i * 2;
}
}
線性對數(shù)階O(nlogN) 將時間復(fù)雜度為O(logn)的代碼循環(huán)N遍的話吧慢，那么它的時間復(fù)雜度就是 n * O(logN)，也就是了O(nlogN)赏表。
時間復(fù)雜度為:O(n2)
如果把 O(n) 的代碼再嵌套循環(huán)一遍检诗，它的時間復(fù)雜度就是 O(n2) 了。
for(x=1; i<=m; x++){
for(i=1; i<=n; i++) {
//
}
}
它的時間復(fù)雜度為 O(m*n)瓢剿，如果m=n,Tn=O(n2),
時間復(fù)雜度為:O(n3)
O(n3)相當(dāng)于三層n循環(huán)逢慌，其它的類似還有K次方階O(n^k)。
2.空間復(fù)雜度
算法所占用的存儲空間主要包括：
1程序本身所占用的空間
2輸入輸出變量所占用的空間
3動態(tài)分配的臨時空間间狂，通常指輔助變量
輸入數(shù)據(jù)所占空間只取決于問題本身涕癣，和算法無關(guān)。我們所說的空間復(fù)雜度是對一個算法在運(yùn)行過程中臨時占用存儲空間大小的量度前标，即第三項。通常來說距潘，只要算法不涉及到動態(tài)分配的空間以及遞歸炼列、棧所需的空間，空間復(fù)雜度通常為0(1)音比。
舉個??：
private void test1(int n) {
int a = 0, b = 0, c = 0;
int cnt;
for (cnt = 0; cnt < n; cnt++) {
a += cnt;
b += a;
c += b;
}
}
空間復(fù)雜度為O(1)俭尖，因為只有a, b, c, cnt四個臨時變量。且臨時變量個數(shù)和輸入數(shù)據(jù)規(guī)模無關(guān)洞翩。
第二個??：
private int test1(int n) {
int a = 0;
if (n == 0) {
return 1;
}
n -= a;
return test1(n);
}
S(n) = O(n).空間復(fù)雜度為O(n)稽犁，因為每次遞歸都會創(chuàng)建一個新的臨時變量a并且共遞歸執(zhí)行n次。
四骚亿、其他
0.算法復(fù)雜度通常指什么已亥？
算法復(fù)雜度是指算法在編寫成可執(zhí)行程序后，運(yùn)行時所需要的資源来屠，資源包括時間資源和內(nèi)存資源,簡而言之也就是時間復(fù)雜度和空間復(fù)雜度的統(tǒng)稱虑椎，一般求“復(fù)雜度”時震鹉，通常指的是時間復(fù)雜度。
1.為什么需要復(fù)雜度分析捆姜？
數(shù)據(jù)結(jié)構(gòu)和算法本身解決的是“快”和“省”的問題传趾，即如何讓代碼運(yùn)行得更快，如何讓代碼更省存儲空間泥技。所以浆兰，執(zhí)行效率是算法一個非常重要的考量指標(biāo)，那就要進(jìn)行時間珊豹、空間復(fù)雜度分析簸呈。
2.算法復(fù)雜度中的O(logN)底數(shù)是多少？
from: 知乎
若算法的 T(n) = O(log n)平夜，則稱其具有對數(shù)時間蝶棋。由于計算機(jī)使用二進(jìn)制的記數(shù)系統(tǒng)，對數(shù)常常以10為底（即log10 n忽妒，有時寫作 lg n）玩裙。然而，由對數(shù)的換底公式段直，loga n和 logb n只有一個常數(shù)因子不同吃溅，這個因子在大O記法中被丟棄。因此記作O(log n)鸯檬，而不論對數(shù)的底是多少决侈，是對數(shù)時間算法的標(biāo)準(zhǔn)記法。
我的理解是首先要明白的是時間復(fù)雜度是為了表明一種趨勢喧务， 不過無論底數(shù)是什么,log級別的漸進(jìn)意義是一樣的赖歌，log級別的時間復(fù)雜度都是由于使用了分治思想,這個底數(shù)直接由分治的復(fù)雜度決定。如果采用二分法,那么就會以2為底數(shù),三分法就會以3為底數(shù),其他亦然功茴。
3.時間復(fù)雜度和空間復(fù)雜度的關(guān)系庐冯？
沒有直接關(guān)系。首先時間復(fù)雜度并不等效于程序執(zhí)行速度坎穿，其次編程里的大部分空間換時間其實并沒有改善時間復(fù)雜度展父。
