作者：nnngu
GitHub：https://github.com/nnngu
博客園：http://www.cnblogs.com/nnngu
簡(jiǎn)書：http://www.reibang.com/users/1df20d76ea5c
知乎：https://www.zhihu.com/people/nnngu/posts

1弥咪、算法的概念：

算法 (Algorithm)疲酌，是對(duì)特定問題求解步驟的一種描述空郊。

解決一個(gè)問題往往有不止一種方法萨醒，算法也是如此衬浑。那么解決特定問題的多個(gè)算法之間如何衡量它們的優(yōu)劣呢？有如下的指標(biāo)：

2、衡量算法的指標(biāo)：

（1）時(shí)間復(fù)雜度： 執(zhí)行這個(gè)算法需要消耗多少時(shí)間。

（2）空間復(fù)雜度： 這個(gè)算法需要占用多少內(nèi)存空間焰望。

同一個(gè)問題可以用不同的算法解決，而一個(gè)算法的優(yōu)劣將影響到算法乃至程序的效率已亥。算法分析的目的在于為特定的問題選擇合適算法熊赖。一個(gè)算法的評(píng)價(jià)主要從時(shí)間復(fù)雜度和空間復(fù)雜度來考慮 。

算法在時(shí)間的高效性和空間的高效性之間通常是矛盾的 陷猫。所以一般只會(huì)取一個(gè)平衡點(diǎn)秫舌。通常我們假設(shè)程序運(yùn)行在足夠大的內(nèi)存空間中，所以研究更多的是算法的時(shí)間復(fù)雜度绣檬。

3、算法的時(shí)間復(fù)雜度

（1）語句頻度T(n)： 一個(gè)算法執(zhí)行所花費(fèi)的時(shí)間嫂粟，從理論上是不能算出來的娇未，必須上機(jī)運(yùn)行測(cè)試才能知道。但我們不可能對(duì)每個(gè)算法都上機(jī)測(cè)試星虹，只需知道哪個(gè)算法花費(fèi)的時(shí)間多零抬，哪個(gè)算法花費(fèi)的時(shí)間少就可以了镊讼。而且一個(gè)算法花費(fèi)的時(shí)間與算法中的基本操作語句的執(zhí)行次數(shù)成正比例，哪個(gè)算法中語句執(zhí)行次數(shù)多平夜，它花費(fèi)時(shí)間就多蝶棋。一個(gè)算法中的語句執(zhí)行次數(shù)稱為語句頻度，記為T(n)忽妒。

（2）時(shí)間復(fù)雜度： 在剛才提到的語句頻度中玩裙，n稱為問題的規(guī)模，當(dāng)n不斷變化時(shí)段直，語句頻度T(n)也會(huì)不斷變化吃溅。但有時(shí)我們想知道它的變化呈現(xiàn)什么規(guī)律。為此鸯檬，我們引入時(shí)間復(fù)雜度概念决侈。 一般情況下，算法中的基本操作語句的重復(fù)執(zhí)行次數(shù)是問題規(guī)模n的某個(gè)函數(shù)喧务，用T(n)表示赖歌，若有某個(gè)輔助函數(shù)f(n)，使得當(dāng)n趨近于無窮大時(shí)功茴，T(n) / f(n) 的極限值為不等于零的常數(shù)庐冯，則稱f(n)是T(n)的同數(shù)量級(jí)函數(shù)。記作 T(n)=Ｏ( f(n) )痊土，稱Ｏ( f(n) ) 為算法的漸進(jìn)時(shí)間復(fù)雜度肄扎，簡(jiǎn)稱時(shí)間復(fù)雜度。 　　T(n) 不同赁酝，但時(shí)間復(fù)雜度可能相同犯祠。 如：T(n)=n2+5n+6 與 T(n)=3n2+3n+2 它們的T(n) 不同，但時(shí)間復(fù)雜度相同酌呆，都為O(n2)衡载。

（3）常見的時(shí)間復(fù)雜度有： 常數(shù)階O(1)，對(duì)數(shù)階O(log₂n)隙袁，線性階O(n)痰娱，線性對(duì)數(shù)階O(nlog₂n)，平方階O(n²)菩收，立方階O(n³)梨睁， k次方階O(n^k)，指數(shù)階O(2ⁿ)娜饵。隨著問題規(guī)模n的不斷增大坡贺，上述時(shí)間復(fù)雜度不斷增大，算法的執(zhí)行效率越低。

（4）平均時(shí)間復(fù)雜度和最壞時(shí)間復(fù)雜度：

平均時(shí)間復(fù)雜度是指所有可能的輸入實(shí)例均以等概率出現(xiàn)的情況下遍坟，該算法的運(yùn)行時(shí)間拳亿。

最壞情況下的時(shí)間復(fù)雜度稱最壞時(shí)間復(fù)雜度。一般討論的時(shí)間復(fù)雜度均是最壞情況下的時(shí)間復(fù)雜度愿伴。 這樣做的原因是：最壞情況下的時(shí)間復(fù)雜度是算法在任何輸入實(shí)例上運(yùn)行時(shí)間的界限肺魁，這就保證了算法的運(yùn)行時(shí)間不會(huì)比最壞情況更長。

（5）如何求時(shí)間復(fù)雜度：

【1】如果算法的執(zhí)行時(shí)間不隨著問題規(guī)模n的增加而增長隔节，即使算法中有上千條語句鹅经，其執(zhí)行時(shí)間也不過是一個(gè)較大的常數(shù)。此類算法的時(shí)間復(fù)雜度是O(1)官帘。

    public static void main(String[] args) {
        int x = 91;
        int y = 100;
        while (y > 0) {
            if (x > 100) {
                x = x - 10;
                y--;
            } else {
                x++;
            }
        }
    }

該算法的時(shí)間復(fù)雜度為：O(1)

這個(gè)程序看起來有點(diǎn)嚇人瞬雹，總共循環(huán)運(yùn)行了1100次，但是我們看到n沒有?

沒刽虹。這段程序的運(yùn)行是和n無關(guān)的酗捌，就算它再循環(huán)一萬年，我們也不管他涌哲，只是一個(gè)常數(shù)階的函數(shù)

【2】當(dāng)有若干個(gè)循環(huán)語句時(shí)胖缤，算法的時(shí)間復(fù)雜度是由嵌套層數(shù)最多的循環(huán)語句中最內(nèi)層語句的頻度f(n)決定的。

1         int x = 1;
2         for (int i = 1; i <= n; i++) {
3             for (int j = 1; j <= i; j++) {
4                 for (int k = 1; k <= j; k++) {
5                     x++;
6                 }
7             }
8         }

該算法的時(shí)間復(fù)雜度為：O(n³) 該程序段中頻度最大的語句是第5行的語句阀圾，內(nèi)循環(huán)的執(zhí)行次數(shù)雖然與問題規(guī)模n沒有直接關(guān)系哪廓，但是卻與外層循環(huán)的變量取值有關(guān)，而最外層循環(huán)的次數(shù)直接與n有關(guān)初烘，因此該程序段的時(shí)間復(fù)雜度為 O(n³)

【3】算法的時(shí)間復(fù)雜度不僅僅依賴于問題的規(guī)模涡真，還與輸入實(shí)例的初始狀態(tài)有關(guān)。 　　在數(shù)值 A[n-1肾筐，n-2 ...0] 中查找給定值k的算法大致如下：

1         int i = n - 1;
2         while (i >= 0 && (A[i] != k)) {
3             i--;
4         }
5         return i;

該算法的時(shí)間復(fù)雜度為：O(n)

此算法中第3行語句的頻度不僅與問題規(guī)模n有關(guān)哆料，還與輸入實(shí)例A中的各元素取值和k的取值有關(guān)：如果A中沒有與k相等的元素，那么第3行語句的頻度為 f(n)=n 吗铐，該程序段的時(shí)間復(fù)雜度為 O(n)

（6）用時(shí)間復(fù)雜度來評(píng)價(jià)算法的性能

用兩個(gè)算法A₁和A₂求解同一問題东亦，時(shí)間復(fù)雜度分別是O(100n²)，O(5n³)

（1） 5n³/100n²=n/20 唬渗，當(dāng)輸入量n＜20時(shí)典阵，100n²> 5n³ ，這時(shí)A₂花費(fèi)的時(shí)間較少镊逝。

（2）隨著問題規(guī)模n的增大壮啊，兩個(gè)算法的時(shí)間開銷之比 5n³/100n²=n/20 也隨著增大。即當(dāng)問題規(guī)模較大時(shí)撑蒜，算法A₁比算法A₂要高效的多他巨。它們的漸近時(shí)間復(fù)雜度O(n²)和O(n³) 評(píng)價(jià)了這兩個(gè)算法在時(shí)間方面的性能充坑。在算法分析時(shí)减江，往往對(duì)算法的時(shí)間復(fù)雜度和漸近時(shí)間復(fù)雜度不予區(qū)分染突，而經(jīng)常是將漸近時(shí)間復(fù)雜度 O(f(n)) 簡(jiǎn)稱為時(shí)間復(fù)雜度，其中的f(n)一般是算法中頻度最大的語句頻度辈灼。

4份企、算法的空間復(fù)雜度

空間復(fù)雜度(Space Complexity) 是對(duì)一個(gè)算法在運(yùn)行過程中臨時(shí)占用存儲(chǔ)空間大小的量度，記做 S(n)=O(f(n)) 巡莹，其中n為問題的規(guī)模司志。利用算法的空間復(fù)雜度，可以對(duì)算法的運(yùn)行所需要的內(nèi)存空間有個(gè)預(yù)先估計(jì)降宅。

一個(gè)算法執(zhí)行時(shí)除了需要存儲(chǔ)本身所使用的指令骂远、常數(shù)、變量和輸入數(shù)據(jù)外腰根，還需要一些對(duì)數(shù)據(jù)進(jìn)行操作的工作單元和存儲(chǔ)一些計(jì)算所需的輔助空間激才。算法執(zhí)行時(shí)所需的存儲(chǔ)空間包括以下兩部分。

（1）固定部分额嘿。這部分空間的大小與輸入/輸出的數(shù)據(jù)的個(gè)數(shù)瘸恼、數(shù)值無關(guān)。主要包括指令空間（即代碼空間）册养、數(shù)據(jù)空間（常量东帅、簡(jiǎn)單變量）等所占的空間。這部分屬于靜態(tài)空間球拦。

（2）可變空間靠闭，這部分空間的主要包括動(dòng)態(tài)分配的空間，以及遞歸棧所需的空間等坎炼。這部分的空間大小與算法有關(guān)愧膀。
舉例分析算法的空間復(fù)雜度：

    public void reserse(int[] a, int[] b) {
        int n = a.length;
        for (int i = 0; i < n; i++) {
            b[i] = a[n - 1 - i];
        }
    }

上方的代碼中，當(dāng)程序調(diào)用 reserse() 方法時(shí)点弯，要分配的內(nèi)存空間包括：引用a扇调、引用b、局部變量n抢肛、局部變量i

因此 f(n)=4 狼钮，4為常量。所以該算法的空間復(fù)雜度 S(n)=O(1)

5捡絮、總結(jié)

算法的時(shí)間復(fù)雜度和兩個(gè)因素有關(guān)：算法中的最大嵌套循環(huán)層數(shù)熬芜；最內(nèi)層循環(huán)結(jié)構(gòu)中循環(huán)的次數(shù)。

一般來說福稳，具有多項(xiàng)式時(shí)間復(fù)雜度的算法是可以接受的涎拉；具有指數(shù)（不是對(duì)數(shù)）時(shí)間復(fù)雜度的算法，只有當(dāng)n足夠小時(shí)才可以使用。一般效率較好的算法要控制在O(log₂n) 或者 O(n)