上篇算法（1）
一煮嫌、函數(shù)的漸近增長
- 函數(shù)的漸近增長：給定兩個函數(shù)f(n)和g(n)笛谦，如果存在一個整數(shù)N, 使得對于所有的 n > N， f(n)總是比g(n)大昌阿，那么饥脑，我們說f(n)的增長漸近快于g(n)。
有兩個算法 A 和 B 懦冰，假設(shè)兩個算法的輸入規(guī)模都是 n好啰，算法 A 要做 2n+3 次操作，算法 B 要做 3n+1 次操作儿奶。覺得誰快框往？看下圖：
算法的漸近增長.png
當(dāng) n = 1 時，算法 A 效率不如算法 B（次數(shù)比算法 B 要多一次）闯捎。而當(dāng) n = 2 時椰弊，兩者效率相同；當(dāng) n > 2時瓤鼻，算法 A 就開始優(yōu)于算法 B 了秉版，隨著 n 的增加， 算法 A 比算法 B 越來越好了茬祷，得出結(jié)論清焕，算法 A 好過 算法 B
- 判斷一個算法的效率時，函數(shù)中的常數(shù)和其他次要項(xiàng)常臣婪福可以忽略秸妥，而更應(yīng)該關(guān)注主項(xiàng)（最高階項(xiàng)）的階數(shù)。
二沃粗、算法時間復(fù)雜度
1粥惧、算法時間復(fù)雜度定義
- 進(jìn)行算法分析時，語句總的執(zhí)行次數(shù) T(n)是關(guān)于問題規(guī)模n的函數(shù)最盅，進(jìn)而分析 T(n)隨n的變化情況并確定T(n)的數(shù)量級突雪。算法的時間復(fù)雜度，也就是算法的時間量度涡贱，記作：T(n) = O(f(n)咏删。它表示隨問題規(guī)模n的增大，算法執(zhí)行時間的增長率和f(n)的增長率相同问词，稱作算法的漸近時間復(fù)雜度督函，簡稱為時間復(fù)雜度。其中f(n)是問題規(guī)模n的某個函數(shù)。
用大寫O()來體現(xiàn)算法時間復(fù)雜度的記法侨核，稱之為大O記法草穆。
一般情況下，隨著n的增大搓译，T(n)增長最慢的算法為最優(yōu)算法悲柱。
三個求和算法的時間復(fù)雜度分別是O(n)，O(1)些己，O(n2)豌鸡。我們分別給它們?nèi)チ朔枪俜降拿Q，O(1)叫常數(shù)項(xiàng)段标、O(n)叫線性階涯冠、O(n2)叫平方階
2、推導(dǎo)大O階方法
- 推導(dǎo)大O階：
1逼庞、用常數(shù)1取代運(yùn)行時間中的所有加法常數(shù)蛇更。
2、在修改后的運(yùn)行次數(shù)函數(shù)中赛糟，只保留最高階項(xiàng)派任。
3、如果最高階項(xiàng)存在且不是1璧南，則去除與這個項(xiàng)相乘的常數(shù)掌逛，得到的結(jié)果就是大O階
3、常數(shù)階
高斯算法司倚，時間復(fù)雜度不是O(3)豆混，而是O(1)。
//第二種算法
int sum = 0, n = 100; /*執(zhí)行1次*/
sum = (1 + n) * n/2; /*執(zhí)行1次*/
printf("%d", sum); /*執(zhí)行1次*/
這個算法的運(yùn)行次數(shù)函數(shù)是f(n)=3.根據(jù)我們推導(dǎo)大O階的方法动知，第一步就是把常數(shù)項(xiàng)3改為1皿伺。在保留最高階項(xiàng)時發(fā)現(xiàn)，它根本么有最高階項(xiàng)拍柒，所以這個算法的時間復(fù)雜度為O(1)心傀。
另外，我們試想一下拆讯，如果這個算法當(dāng)中的語句 sum=(1+n)*n/2有8句，即：
int sum = 0, n = 100; /*執(zhí)行1次*/
sum = (1 + n) * n/2; /*執(zhí)行2次*/
sum = (1 + n) * n/2; /*執(zhí)行3次*/
sum = (1 + n) * n/2; /*執(zhí)行4次*/
sum = (1 + n) * n/2; /*執(zhí)行5次*/
sum = (1 + n) * n/2; /*執(zhí)行6次*/
sum = (1 + n) * n/2; /*執(zhí)行7次*/
sum = (1 + n) * n/2; /*執(zhí)行8次*/
printf("%d", sum); /*執(zhí)行1次*/
事實(shí)上無論n為多少养叛，上面的兩段代碼就是3和10次執(zhí)行的差異种呐。這種與問題的大小無關(guān)（n的多少）,執(zhí)行時間恒定的算法，我們稱之具有O(1)的時間復(fù)雜度弃甥，又叫常數(shù)階爽室。
注意：不管這個常數(shù)是多少，我們都記作O(1)淆攻，而不能是O(3)阔墩、O(10)等其他任何數(shù)字嘿架，這是初學(xué)者常常犯的錯誤。
對于分支結(jié)構(gòu)而言啸箫，無論是真耸彪，還是假，執(zhí)行的次數(shù)都是恒定的忘苛，不會隨著n的變大而發(fā)生變化蝉娜，所以單純的分支結(jié)構(gòu)（不包含在循環(huán)結(jié)構(gòu)中），其時間復(fù)雜度也是O(1)扎唾。
4召川、線性階
- 分析算法的復(fù)雜度，關(guān)鍵就是要分析循環(huán)結(jié)構(gòu)的運(yùn)行情況胸遇。
// 線性階
int i;
for (i = 0; i < n; i++) {
/* 時間復(fù)雜度為O(1)的程序步驟序列 */
}
```
5荧呐、對數(shù)階
>下面的這段代碼，時間復(fù)雜度又是多少呢纸镊？
int count = 1;
while (count < n) {
count = count * 2;
/* 時間復(fù)雜度為O(1)的程序步驟序列 */
}
由于每次count乘以2之后坛增，就距離n更近了一分。也就是說薄腻，有多少個2相乘后大于n,則會退出循環(huán)收捣。由2× = n ，得到 x = ㏒2n (2縮小)庵楷。所以這個循環(huán)的時間復(fù)雜度為O(㏒n)罢艾。
6、平方階
下面例子是一個循環(huán)嵌套尽纽，它的內(nèi)循環(huán)剛才我們已經(jīng)分析過咐蚯，時間復(fù)雜度為O(n)。
int i, j;
for(i = 0, i < n; i++)
{
for (j = 0; j < n; j++)
{
/* 時間復(fù)雜度為O(1)的程序步驟序列 */
}
}
而對于外層的循環(huán)弄贿，不過是內(nèi)部這個時間復(fù)雜度為O(n)的語句春锋，再循環(huán)n次。所以這段代碼的時間復(fù)雜度為O(n2)差凹。
如果外循環(huán)的循環(huán)次數(shù)改為了m期奔，時間復(fù)雜度就變?yōu)镺(m x n)。
int i, j;
for(i = 0, i < m; i++)
{
for (j = 0; j < n; j++)
{
/* 時間復(fù)雜度為O(1)的程序步驟序列 */
}
}
所以我們可以總結(jié)得出危尿，**循環(huán)的時間復(fù)雜度等于循環(huán)體的復(fù)雜度乘以該循環(huán)運(yùn)行的次數(shù)**
那么下面這個循環(huán)嵌套呐萌，它的時間復(fù)雜度是多少呢？
int i, j;
for(i = 0, i < m; i++)
{
for (j = i; j < n; j++) /* 注意j = i 而不是 0/
{
/ 時間復(fù)雜度為O(1)的程序步驟序列 */
}
}
由于當(dāng)i=0時谊娇，內(nèi)循環(huán)執(zhí)行了n次肺孤，當(dāng)i = 1時，執(zhí)行了n-1次，······當(dāng)i = n-1時赠堵，執(zhí)行了1次小渊，所以總的執(zhí)行次數(shù)為：
n+(n-1)+(n-2)+···+1=n(n+1)/2 = (n2+n)/2
用推導(dǎo)大O階的方法，第一條茫叭，沒有加法常數(shù)不予考慮酬屉；第二條，只保留最高階項(xiàng)杂靶，因此保留n2/2;第三條梆惯，去除這個項(xiàng)相乘的常數(shù)，也就是取出1/2,最終這段代碼的時間復(fù)雜度為O(n2）吗垮。
從這個例子垛吗，我們也可以得到一個經(jīng)驗(yàn)，其實(shí)理解大O推導(dǎo)不算難烁登，難的是對數(shù)列的一些相關(guān)運(yùn)算怯屉，這更多的是考察數(shù)學(xué)知識和能力。