1. 算法的定義

算法是解決特定問(wèn)題求解步驟的描述，在計(jì)算機(jī)中表現(xiàn)為指令的有限序列，并且每條指令表示一個(gè)或多個(gè)操作

2. 算法的特性

1. 輸入：
   可以具有零個(gè)或多個(gè)輸入
2. 輸出：
   至少有一個(gè)或多個(gè)輸出
3. 可窮性：
   指在執(zhí)行有限的步驟之后，自動(dòng)結(jié)束而不會(huì)出現(xiàn)無(wú)限循環(huán)，并且每一個(gè)步驟在可接受的時(shí)間內(nèi)完成。
4. 確定性：

• 算法的每一步驟都具有確定的含義，不會(huì)出現(xiàn)二義性；
• 算法在一定條件，只有一條執(zhí)行路徑，即相同的輸入只能有唯一的輸出結(jié)果。

5. 可行性：
   算法的每一步驟都必須是可行的。

3. 算法設(shè)計(jì)的要求

3.1. 正確性
指算法至少應(yīng)該具有輸入、輸出和技工處理無(wú)歧義性、能正確反映問(wèn)題的需求、能夠得到問(wèn)題的真確答案。
大體分為四個(gè)層次：

• 算法程序沒(méi)有語(yǔ)法錯(cuò)誤；
• 算法程序?qū)τ诤戏ㄝ斎肽軌虍a(chǎn)生滿(mǎn)足要求的輸出；
• 算法程序?qū)τ诜欠ㄝ斎肽軌虍a(chǎn)生滿(mǎn)足規(guī)格的說(shuō)明；
• 算法程序?qū)τ诠室獾箅y的測(cè)試輸入都有滿(mǎn)足要求的輸出結(jié)果。

3.2. 可讀性
便于（他人）閱讀（和日后自己閱讀和修改）、理解和交流。
3.3. 健壯性
當(dāng)輸入數(shù)據(jù)不合法時(shí)，算法也能做出相關(guān)處理，而不是產(chǎn)生異常，崩潰或莫名其妙的結(jié)果。
3.4. 時(shí)間效率高和存儲(chǔ)量低

4. 算法效率的度量方法

• 事后統(tǒng)計(jì)方法：通過(guò)設(shè)計(jì)好的測(cè)試程序和數(shù)據(jù)，利用計(jì)算機(jī)計(jì)時(shí)器對(duì)不同算法編制的程序的云刑事案件進(jìn)行比較，從而確定算法效率的高低。
  缺陷：必須依據(jù)算法事先編制好測(cè)試程序，通常需要花費(fèi)大量時(shí)間和精力，完了發(fā)覺(jué)測(cè)試的是糟糕的算法，功虧一簣；
  不同測(cè)試環(huán)境差別大。
• 事前分析估算方法：在計(jì)算機(jī)程序編寫(xiě)前，依據(jù)統(tǒng)計(jì)方法對(duì)算法進(jìn)行估算。

經(jīng)過(guò)總結(jié)，我們發(fā)現(xiàn)一個(gè)高級(jí)語(yǔ)言編寫(xiě)的程序在計(jì)算機(jī)上運(yùn)行時(shí)所消耗的時(shí)間取決于下列因素：

1. 算法采用的策略、方案
2. 編譯產(chǎn)生的代碼質(zhì)量
3. 問(wèn)題的輸入規(guī)模
4. 機(jī)器執(zhí)行指令的速度

我們舉例說(shuō)明：
第一種算法（求和1）：

int i, sum = 0, n = 100; //執(zhí)行 1次
for(i = 1; i <= n; i++){ //循環(huán)判斷語(yǔ)句，執(zhí)行了n+1次，
    sum = sum + i; //執(zhí)行 n次
}

第二種算法(高斯算法)（求和2）：

int sum = 0, n = 100; //執(zhí)行 1次
sum = ( 1 + n ) * n / 2; //執(zhí)行 1次

分析可得：
第一種算法執(zhí)行了1+(n+1)+n = 2n+2次；
第二種算法，執(zhí)行了1+1 = 2次，
如果我們把循環(huán)看做一個(gè)整體，忽略頭尾判斷的開(kāi)銷(xiāo)，那么這兩個(gè)算法其實(shí)是n和1的差距？
為什么這么說(shuō)？
第三個(gè)例子（求和3）：

int i, i, x = 0; sum = 0, n = 100;
for(i = 1; i <= n; i++){
    for(j = 1; j<= n; j++){
         x++;
         sum= sum + x;
    }
}

上面這個(gè)例子中，循環(huán)條件i從1到100，每次都要讓j循環(huán)100次，如果非常較真的研究總共精確執(zhí)行次數(shù)，那是非常累的。所以這個(gè)例子的算法，需要執(zhí)行100^2次。

我們研究算法的復(fù)雜度，側(cè)重的是研究算法隨著輸入規(guī)模擴(kuò)大增長(zhǎng)量的一個(gè)抽象，而不是精確的定位需要執(zhí)行多少次， 因?yàn)槿绻@樣，我們得考慮編譯器的優(yōu)化問(wèn)題。

• 我們不關(guān)心編寫(xiě)程序所用的語(yǔ)言是什么，也不關(guān)心這些程序?qū)⑴菰谑裁礃拥挠?jì)算機(jī)上，我們只關(guān)心它所實(shí)現(xiàn)的算法。
• 不計(jì)那些循環(huán)索引的遞增和循環(huán)終止條件、變量聲明、打印結(jié)果等操作。最終，在分析程序的運(yùn)行時(shí)間時(shí)，最重要的是把程序看成是獨(dú)立于程序設(shè)計(jì)語(yǔ)言的算法或一系列步驟。
• 我們?cè)诜治鲆粋€(gè)算法的運(yùn)行時(shí)間時(shí)，重要的是把基本操作的數(shù)量和輸入模式關(guān)聯(lián)起來(lái)。

5. 函數(shù)的漸近增長(zhǎng)

給定兩個(gè)函數(shù)f(n) 和 g(n),如果存在一個(gè)整數(shù)N，使得對(duì)于所有的n>N,f(n)總是比g(n)大，那么，我們說(shuō)f(n)的增長(zhǎng)漸近快于g(n)。

示例1：比較算法:
A1=2n+3;
B1=3n+1;

算法的比較一

當(dāng)n= 1時(shí)，A1=5,B1=4，算法A1效率不如算法B1；
當(dāng)n=2時(shí)，A1=7,B1=7，兩者效率相同；
當(dāng)n=3時(shí)，A1=9,B1=10，算法A1就開(kāi)始優(yōu)于算法B1，隨著n的繼續(xù)增加，算法A1比算法B1逐步拉大差距。所以總體上算法A1比B1優(yōu)秀。

算法的曲線圖對(duì)比

經(jīng)對(duì)比中發(fā)現(xiàn)，隨著n的增大，A2和B2，在曲線表中是被覆蓋的，說(shuō)明后面的+3和+1其實(shí)不影響最終的算法變化曲線的。所以我們可以忽略這些加法常數(shù)

示例2
算法C是4n+8；算法D是2n^2+1.

算法對(duì)比表

算法曲線圖

我們觀察曲線圖發(fā)現(xiàn)，去掉與n相乘的常數(shù)，即C2與D2，C2與C1重合，D2與D1重合，說(shuō)明與最高次項(xiàng)相乘的常數(shù)也是可以忽略的

示例3
算法G是2n^2 ，算法H是3n+1，算法I是2n^2+3n+1。

算法對(duì)比表

算法曲線圖

數(shù)據(jù)很大（即輸入規(guī)模變得很大）的時(shí)候各算法的曲線圖如下：

各算法的曲線圖

這組數(shù)據(jù)可以發(fā)現(xiàn)，當(dāng)n的值變得非常大的時(shí)候，3n+1已經(jīng)沒(méi)法和2n^2的結(jié)果相比較，最終可以忽略不計(jì)，而算法G跟算法I基本已經(jīng)重合。

總結(jié)
判斷一個(gè)算法的效率時(shí)，函數(shù)中的常數(shù)和其他次要項(xiàng)常?？梢院雎?，而更應(yīng)該關(guān)注主項(xiàng)（最高項(xiàng)）的階數(shù)。

6. 算法時(shí)間復(fù)雜度

定義：在進(jìn)行算法分析時(shí)，語(yǔ)句總的執(zhí)行次數(shù)T(n) 是關(guān)于問(wèn)題規(guī)模n的函數(shù)，進(jìn)而分析T(n) 隨n的變化情況并確定T(n)的數(shù)量級(jí)。

公式：T(n) = O(f(n))
表示隨問(wèn)題規(guī)模n的增大，算法執(zhí)行時(shí)間的增長(zhǎng)率和f(n)的增長(zhǎng)率相同，稱(chēng)作算法的漸近時(shí)間復(fù)雜度，簡(jiǎn)稱(chēng)時(shí)間復(fù)雜度。其中f(n)是問(wèn)題規(guī)模n的某個(gè)函數(shù)。
一般情況下，隨著輸入規(guī)模n的增大，T(n)增長(zhǎng)最慢的算法為最優(yōu)算法。
顯然，三個(gè)求和算法的時(shí)間復(fù)雜度分別可表示為：
O(1),O(n),O(n^2)

分析算法時(shí)間復(fù)雜度
分析一個(gè)算法的時(shí)間復(fù)雜度（又稱(chēng)推導(dǎo)大O階）方法：

• 用常數(shù)1取代運(yùn)行時(shí)間中的所有加法常數(shù)
• 在修改后的運(yùn)行次數(shù)函數(shù)中，只保留最高階項(xiàng)；
• 如果最高階項(xiàng)存在且不是1，則去除與這個(gè)項(xiàng)相乘的常數(shù)
• 得到的最后結(jié)果就是大O階。

6.1. 常數(shù)階
舉例：
以下這段代碼的大O是多少？

int sum = 0, n = 100;
printf("hello world\n");
printf("hello world\n");
printf("hello world\n");
printf("hello world\n");
printf("hello world\n");
printf("hello world\n");
sum = (1 + n) * n / 2;

分析：雖然這段代碼雖然有8條語(yǔ)句，但是與問(wèn)題規(guī)模有關(guān)系的只有sum = (1 + n) * n / 2;這一句，所以我們記為O(1).

6.2. 線性階
一般含有非嵌套循環(huán)涉及線性階，線性階就是隨著問(wèn)題規(guī)模n的擴(kuò)大，對(duì)應(yīng)計(jì)算次數(shù)成直線增長(zhǎng)。

int i, n = 100, sum = 0; //執(zhí)行 1次
for(i = 1; i <= n; i++){ //循環(huán)判斷語(yǔ)句，執(zhí)行了n+1次，
    sum = sum + i; //執(zhí)行 n次
}

這段代碼，它的循環(huán)的時(shí)間復(fù)雜度為O(n),因?yàn)檠h(huán)體重的代碼需要執(zhí)行n次。
6.3. 平方階
嵌套循環(huán)：

int i, i,  n = 100;
for(i = 1; i <= n; i++){
    for(j = 1; j<= n; j++){
         printf("hello world\n");
    }
}

n等于100時(shí)，外層循環(huán)每執(zhí)行一次，內(nèi)層循環(huán)就執(zhí)行100次，那總共程序想要從這兩個(gè)循環(huán)出來(lái)，需要執(zhí)行100100次，即n的平方。所以這段代碼的時(shí)間復(fù)雜度為O(n^2).
如果有三個(gè)嵌套循環(huán)，則是n^3.
即：循環(huán)的時(shí)間復(fù)雜度=循環(huán)體的復(fù)雜度 * 該循環(huán)運(yùn)行的次數(shù)

以上的是每個(gè)循環(huán)的次數(shù)都是一樣的，如果循環(huán)的次數(shù)不一樣呢？如以下代碼：

int i, i,  n = 100;
for(i = 0; i < n; i++){
    for(j = i; j< n; j++){
         printf("hello world\n");
    }
}

分析：
當(dāng)i= 0時(shí)，內(nèi)循環(huán)執(zhí)行了n次，當(dāng)i=1時(shí)，內(nèi)循環(huán)執(zhí)行n-1次……當(dāng)i = n-1時(shí)，內(nèi)循環(huán)執(zhí)行1次，所以總的執(zhí)行次數(shù)則為：
n+(n-1)+(n-2)+...+1=n(n+1)/2
拆分后：n^2/2+n/2;
用推導(dǎo)大O的攻略：
第一條忽略，因?yàn)闆](méi)有常數(shù)；第二條只保留最高項(xiàng)，所以n/2這項(xiàng)去掉；第三條，去除與最高項(xiàng)相乘的常數(shù)，最終得O(n^2)。

6.4. 對(duì)數(shù)階
我們看下這個(gè)程序：

int i = 1, n = 100;
while(i < n){
    i = i * 2;
}

分析：
循環(huán)1次時(shí)：i = 1 * 2 = 2;
循環(huán)2次時(shí)：i = 2 * 2 = 4;
循環(huán)3次時(shí)：i = 4 * 2 = 8;
循環(huán)4次時(shí)：i = 8 * 2 = 16;
循環(huán)5次時(shí)：i = 16 * 2 = 32;
循環(huán)6次時(shí)：i = 32 * 2 = 64;
循環(huán)7次時(shí)：i = 64 * 2 = 128;
因?yàn)?28>100,退出循環(huán)。
由上面的分析得n=i=2^x(循環(huán)次數(shù))，得到x = log(2)n,所以這個(gè)循環(huán)的時(shí)間復(fù)雜度為O(logn).

7. 函數(shù)調(diào)用的時(shí)間復(fù)雜度分析

我們把問(wèn)題再實(shí)際化一點(diǎn)，看下邊的例子：
7.1

int i, j, n;
for(i = 0; i < n; i++){
    fun(i);
}
void fun(int count){
    printf("%d", count);
}

分析：函數(shù)體是打印這個(gè)參數(shù)，fun函數(shù)的時(shí)間復(fù)雜度為O(1),所以整體的時(shí)間復(fù)雜度是循環(huán)的次數(shù)O(n).

如果改成這樣呢？
7.2

int i, j, n;
for(i = 0; i < n; i++){
    fun(i);
}
void fun(int count){
    int j;
    for(j = count; j < n; j++){
        printf("%d", j);
    }
}

事實(shí)上，這和我們講解平方階時(shí)舉的第二個(gè)例子一樣：fun內(nèi)部的循環(huán)次數(shù)隨count的增加（接近n）而減少，所以fun函數(shù)的時(shí)間復(fù)雜度為O(n),所以整體的時(shí)間復(fù)雜度為O(n^2).

7.3

n++;
fun(n);
//第一個(gè)for循環(huán)
for(i = 0; i < n; i++){
    fun(i);
}
//第二個(gè)for循環(huán)
for(i = 0; i < n; i++){
    for(j = i; j < n; j++){
        printf("%d", j);
    }
}
//fun方法
void fun(int count){
    int j;
    for(j = count; j < n; j++){
        printf("%d", j);
    }
}

分析：

• n++,為O(1);
• fun(n),為O(n);
• 第一個(gè)for循環(huán)，為O(n^2);
• 第二個(gè)for循環(huán)，為O(n^2);
  所以整體的時(shí)間復(fù)雜度：3n^2 +1,根據(jù)前面的推導(dǎo)方法，最終的時(shí)間復(fù)雜度為：O(n^2).
  7.4 常見(jiàn)的時(shí)間復(fù)雜度

常見(jiàn)的時(shí)間復(fù)雜度.png

常見(jiàn)的時(shí)間復(fù)雜度的曲線圖1.png

常見(jiàn)的時(shí)間復(fù)雜度的曲線圖2.png