如果想要分析一個(gè)程序的性能巢音，你可以嘗試將程序運(yùn)行，然后收集它的運(yùn)行數(shù)據(jù)尽超，就可以得到程序運(yùn)行所需要的時(shí)間和內(nèi)存官撼。我們將這種分析方法稱為事后統(tǒng)計(jì)法。
事后統(tǒng)計(jì)法是非常樸素的分析方法似谁，但是也兩點(diǎn)問題：
- 程序的運(yùn)行需要依賴硬件環(huán)境傲绣，比如同一個(gè)程序在兩臺(tái)性能不一的電腦上的表現(xiàn)是不同的。
- 程序運(yùn)行時(shí)間往往收到數(shù)據(jù)規(guī)模的影響秃诵，例如在排序算法中菠净，快排是最優(yōu)秀的算法，如果只使用幾個(gè)數(shù)據(jù)進(jìn)行排序攀唯，可能它的表現(xiàn)還不如冒泡排序革答，但是當(dāng)使用上萬個(gè)數(shù)據(jù)進(jìn)行排序的時(shí)候，他們的性能差異就會(huì)顯現(xiàn)碟嘴。（這種差異可能不是十倍娜扇，而是百倍千倍）
由于這些問題雀瓢，我們一般使用復(fù)雜度分析的方法分析一個(gè)算法的性能，這就是大O復(fù)雜度表示法
大O復(fù)雜度表示法：
大O時(shí)間復(fù)雜度表示法：
拋去計(jì)算機(jī)底層的影響泊业，我們可以使用大O時(shí)間復(fù)雜度表示法來表示代碼執(zhí)行時(shí)間隨數(shù)據(jù)規(guī)模增長的變化趨勢(shì)吁伺，簡(jiǎn)稱時(shí)間復(fù)雜度捆愁。
分析時(shí)間復(fù)雜度有三個(gè)比較使用的方法：
1.只關(guān)注循環(huán)執(zhí)行次數(shù)最多的一段代碼：
敲黑板：循環(huán) 和 最多
下面有一段代碼：
int cal(int n) {
int sum = 0;
int i = 1;
for (; i <= n; ++i) {
sum = sum + i;
}
return sum;
}
上面的代碼中牙瓢，2憔足、3行代碼都是常量級(jí)的執(zhí)行時(shí)間，和n無關(guān)弓候，在復(fù)雜度分析中可以忽略邦蜜。循環(huán)執(zhí)行次數(shù)最多代碼是 for 循環(huán)中的代碼贱迟，它被執(zhí)行了 n 次，所以總的時(shí)間復(fù)雜度是O（n）
2.加法法則：總復(fù)雜度等于量級(jí)最大的那段代碼的復(fù)雜度：
看下面的代碼：
int cal(int n) {
int sum_1 = 0;
int p = 1;
for (; p < 100; ++p) {
sum_1 = sum_1 + p;
}
int sum_2 = 0;
int q = 1;
for (; q < n; ++q) {
sum_2 = sum_2 + q;
}
int sum_3 = 0;
int i = 1;
int j = 1;
for (; i <= n; ++i) {
j = 1;
for (; j <= n; ++j) {
sum_3 = sum_3 + i * j;
}
}
return sum_1 + sum_2 + sum_3;
}
上面的代碼中缚俏，sum_2部分的代碼的復(fù)雜度為O(n)胀屿，sum_3代碼的復(fù)雜度為O(n2）宿崭，根據(jù)加法法則，cal函數(shù)的復(fù)雜度為O(n2)
3.乘法法則：嵌套代碼的復(fù)雜度等于嵌套內(nèi)外代碼的復(fù)雜度的乘積：
看下面的代碼：
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;
}
可以看到讹堤，在 cal 的 for 循環(huán)中嵌套了 f 函數(shù)。第一部分的 for 循環(huán)貢獻(xiàn)了 n 的復(fù)雜度梗醇，而 f 函數(shù)也貢獻(xiàn)了 n 的復(fù)雜度，根據(jù)乘法法則手负，cal的復(fù)雜度為 O(n2)竟终。
大O空間復(fù)雜度表示法：
空間復(fù)雜度的定義和時(shí)間復(fù)雜度類似：表示算法需要的存儲(chǔ)空間與數(shù)據(jù)規(guī)模之間的增長關(guān)系。
你只需要分析在算法中申請(qǐng)的存儲(chǔ)空間即可，常見的空間復(fù)雜度有：O(1),O(n),O(n2)
最好镰惦、最壞、平均茵瘾、均攤 時(shí)間復(fù)雜度
同一個(gè)算法在給定不同數(shù)據(jù)的情況下性能可能會(huì)出現(xiàn)很大的差異圣絮，例如：如果一個(gè)數(shù)組已經(jīng)基本有序，那么使用快速排序則有O(n2)的時(shí)間復(fù)雜度棒搜，而最好的情況下復(fù)雜度為O(nlogn)。
基于上面的情況末盔，我們引入了各種復(fù)雜度的度量：
- 最好情況時(shí)間復(fù)雜度：在最理想的情況下，執(zhí)行這段代碼的時(shí)間復(fù)雜度
- 最壞情況時(shí)間復(fù)雜度：在最糟糕的情況下游盲，執(zhí)行這段代碼的時(shí)間復(fù)雜度
- 平均時(shí)間復(fù)雜度：根據(jù)概率論的理論，平均時(shí)間復(fù)雜度的值為代碼執(zhí)行的加權(quán)平均值莺奔，也就是它的期望值。所以你也可以將之稱為加權(quán)平均時(shí)間復(fù)雜度屏富。
- 均攤時(shí)間復(fù)雜度：你可以將其理解為一種特殊的平均時(shí)間復(fù)雜度：
先來看下面一段代碼：
// array表示一個(gè)長度為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;
}
你會(huì)發(fā)現(xiàn)，如果我們一直使用insert函數(shù)向數(shù)組array中添加數(shù)據(jù)已维，在沒有到達(dá)n垛耳，只需要O(1)的時(shí)間復(fù)雜度，但是如果放入第n個(gè)數(shù)據(jù)泡嘴，復(fù)雜度就會(huì)變?yōu)镺(n)，這就出現(xiàn)了在執(zhí)行過程中操作的復(fù)雜度不同的情況，針對(duì)這種情況建椰，我摘取了下面一段話：
對(duì)一個(gè)數(shù)據(jù)結(jié)構(gòu)進(jìn)行一組連續(xù)操作中棉姐，大部分情況下時(shí)間復(fù)雜度都很低夏志，只有個(gè)別情況下時(shí)間復(fù)雜度比較高湿诊，而且這些操作之間存在前后連貫的時(shí)序關(guān)系，這個(gè)時(shí)候，我們就可以將這一組操作放在一塊兒分析宣蠕，看是否能將較高時(shí)間復(fù)雜度那次操作的耗時(shí)，平攤到其他那些時(shí)間復(fù)雜度比較低的操作上唱逢。而且，在能夠應(yīng)用均攤時(shí)間復(fù)雜度分析的場(chǎng)合，一般均攤時(shí)間復(fù)雜度就等于最好情況時(shí)間復(fù)雜度叠艳。
注意：只有在最好、最壞徐勃、平均時(shí)間復(fù)雜度在量級(jí)上存在差異的時(shí)候扎酷，區(qū)分它們才有意義谁榜。
以上就是對(duì)算法的復(fù)雜度分析的全部內(nèi)容。
