摘要：示例代碼斐波那契數(shù)列復制代碼復制代碼這里，給定規(guī)模，計算所需的時間為計算的時間和計算的時間的和。示例代碼復制代碼復制代碼同樣是斐波那契數(shù)列，我們使用數(shù)組來存儲計算結(jié)果，這樣算法復雜度優(yōu)化為。算法適用于少量數(shù)據(jù)的排序，時間復雜度為。

原文：http://www.cnblogs.com/gaochundong/p/complexity_of_algorithms.html
為什么要進行算法分析？

預測算法所需的資源
計算時間（CPU 消耗）
內(nèi)存空間（RAM 消耗）
通信時間（帶寬消耗）
預測算法的運行時間
在給定輸入規(guī)模時，所執(zhí)行的基本操作數(shù)量。
或者稱為算法復雜度（Algorithm Complexity）
如何衡量算法復雜度？

內(nèi)存（Memory）
時間（Time）
指令的數(shù)量（Number of Steps）
特定操作的數(shù)量
磁盤訪問數(shù)量
網(wǎng)絡包數(shù)量
漸進復雜度（Asymptotic Complexity）
算法的運行時間與什么相關？

取決于輸入的數(shù)據(jù)。（例如：如果數(shù)據(jù)已經(jīng)是排好序的，時間消耗可能會減少。）
取決于輸入數(shù)據(jù)的規(guī)模。（例如：6 和 6 * 109）
取決于運行時間的上限。（因為運行時間的上限是對使用者的承諾。）
算法分析的種類：

最壞情況（Worst Case）：任意輸入規(guī)模的最大運行時間。（Usually）
平均情況（Average Case）：任意輸入規(guī)模的期待運行時間。（Sometimes）
最佳情況（Best Case）：通常最佳情況不會出現(xiàn)。（Bogus）
例如，在一個長度為 n 的列表中順序搜索指定的值，則

最壞情況：n 次比較
平均情況：n/2 次比較
最佳情況：1 次比較
而實際中，我們一般僅考量算法在最壞情況下的運行情況，也就是對于規(guī)模為 n 的任何輸入，算法的最長運行時間。這樣做的理由是：

一個算法的最壞情況運行時間是在任何輸入下運行時間的一個上界（Upper Bound）。
對于某些算法，最壞情況出現(xiàn)的較為頻繁。
大體上看，平均情況通常與最壞情況一樣差。
算法分析要保持大局觀（Big Idea），其基本思路：

忽略掉那些依賴于機器的常量。
關注運行時間的增長趨勢。
比如：T(n) = 73n3 + 29n3 + 8888 的趨勢就相當于 T(n) = Θ(n3)。

漸近記號（Asymptotic Notation）通常有 O、 Θ 和 Ω 記號法。Θ 記號漸進地給出了一個函數(shù)的上界和下界，當只有漸近上界時使用 O 記號，當只有漸近下界時使用 Ω 記號。盡管技術上 Θ 記號較為準確，但通常仍然使用 O 記號表示。

使用 O 記號法（Big O Notation）表示最壞運行情況的上界。例如，

線性復雜度 O(n) 表示每個元素都要被處理一次。
平方復雜度 O(n2) 表示每個元素都要被處理 n 次。

Notation Intuition Informal Definition

f is bounded above by g asymptotically

Two definitions :
Number theory:

f is not dominated by g asymptotically

Complexity theory:

f is bounded below by g asymptotically

f is bounded both above and below by g asymptotically

例如：

T(n) = O(n3) 等同于 T(n) ∈ O(n3)
T(n) = Θ(n3) 等同于 T(n) ∈ Θ(n3).
相當于:

T(n) 的漸近增長不快于 n3。
T(n) 的漸近增長與 n3 一樣快。

復雜度 標記符號 描述
常量（Constant）
O(1)

操作的數(shù)量為常數(shù)，與輸入的數(shù)據(jù)的規(guī)模無關。

n = 1,000,000 -> 1-2 operations

對數(shù)（Logarithmic）
O(log2 n)

操作的數(shù)量與輸入數(shù)據(jù)的規(guī)模 n 的比例是 log2 (n)。

n = 1,000,000 -> 30 operations

線性（Linear） O(n)
操作的數(shù)量與輸入數(shù)據(jù)的規(guī)模 n 成正比。

n = 10,000 -> 5000 operations

平方（Quadratic） O(n2)
操作的數(shù)量與輸入數(shù)據(jù)的規(guī)模 n 的比例為二次平方。

n = 500 -> 250,000 operations

立方（Cubic） O(n3)
操作的數(shù)量與輸入數(shù)據(jù)的規(guī)模 n 的比例為三次方。

n = 200 -> 8,000,000 operations

指數(shù)（Exponential）
O(2n)

O(kn)

O(n!)

指數(shù)級的操作，快速的增長。

n = 20 -> 1048576 operations

注1：快速的數(shù)學回憶，logab = y 其實就是 ay = b。所以，log24 = 2，因為 22 = 4。同樣 log28 = 3，因為 23 = 8。我們說，log2n 的增長速度要慢于 n，因為當 n = 8 時，log2n = 3。

注2：通常將以 10 為底的對數(shù)叫做常用對數(shù)。為了簡便，N 的常用對數(shù) log10 N 簡寫做 lg N，例如 log10 5 記做 lg 5。

注3：通常將以無理數(shù) e 為底的對數(shù)叫做自然對數(shù)。為了方便，N 的自然對數(shù) loge N 簡寫做 ln N，例如 loge 3 記做 ln 3。

注4：在算法導論中，采用記號 lg n = log2 n ，也就是以 2 為底的對數(shù)。改變一個對數(shù)的底只是把對數(shù)的值改變了一個常數(shù)倍，所以當不在意這些常數(shù)因子時，我們將經(jīng)常采用 "lg n"記號，就像使用 O 記號一樣。計算機工作者常常認為對數(shù)的底取 2 最自然，因為很多算法和數(shù)據(jù)結(jié)構(gòu)都涉及到對問題進行二分。

而通常時間復雜度與運行時間有一些常見的比例關系：

復雜度 10 20 50 100 1000 10000 100000
O(1)
<1s

<1s

<1s

<1s

<1s

<1s

<1s

O(log2(n))
<1s

<1s

<1s

<1s

<1s

<1s

<1s

O(n)
<1s

<1s

<1s

<1s

<1s

<1s

<1s

O(n*log2(n))
<1s

<1s

<1s

<1s

<1s

<1s

<1s

O(n2)
<1s

<1s

<1s

<1s

<1s

2s

3-4 min

O(n3)
<1s

<1s

<1s

<1s

20s

5 hours

231 days

O(2n)
<1s

<1s

260 days

hangs

hangs

hangs

hangs

O(n!)
<1s

hangs

hangs

hangs

hangs

hangs

hangs

O(nn)
3-4 min

hangs

hangs

hangs

hangs

hangs

hangs

計算代碼塊的漸進運行時間的方法有如下步驟：

確定決定算法運行時間的組成步驟。
找到執(zhí)行該步驟的代碼，標記為 1。
查看標記為 1 的代碼的下一行代碼。如果下一行代碼是一個循環(huán)，則將標記 1 修改為 1 倍于循環(huán)的次數(shù) 1 n。如果包含多個嵌套的循環(huán)，則將繼續(xù)計算倍數(shù)，例如 1 n * m。
找到標記到的最大的值，就是運行時間的最大值，即算法復雜度描述的上界。
示例代碼（1）：

復制代碼
1 decimal Factorial(int n)
2 {
3 if (n == 0)
4 return 1;
5 else
6 return n * Factorial(n - 1);
7 }
復制代碼
階乘（factorial），給定規(guī)模 n，算法基本步驟執(zhí)行的數(shù)量為 n，所以算法復雜度為 O(n)。

示例代碼（2）：

復制代碼
1 int FindMaxElement(int[] array)
2 {
3 int max = array[0];
4 for (int i = 0; i < array.Length; i++)
5 {
6 if (array[i] > max)
7 {
8 max = array[i];
9 }
10 }
11 return max;
12 }
復制代碼
這里，n 為數(shù)組 array 的大小，則最壞情況下需要比較 n 次以得到最大值，所以算法復雜度為 O(n)。

示例代碼（3）：

復制代碼
1 long FindInversions(int[] array)
2 {
3 long inversions = 0;
4 for (int i = 0; i < array.Length; i++)
5 for (int j = i + 1; j < array.Length; j++)
6 if (array[i] > array[j])
7 inversions++;
8 return inversions;
9 }
復制代碼
這里，n 為數(shù)組 array 的大小，則基本步驟的執(zhí)行數(shù)量約為 n*(n-1)/2，所以算法復雜度為 O(n2)。

示例代碼（4）：

復制代碼
1 long SumMN(int n, int m)
2 {
3 long sum = 0;
4 for (int x = 0; x < n; x++)
5 for (int y = 0; y < m; y++)
6 sum += x * y;
7 return sum;
8 }
復制代碼
給定規(guī)模 n 和 m，則基本步驟的執(zhí)行數(shù)量為 n*m，所以算法復雜度為 O(n2)。

示例代碼（5）：

復制代碼
1 decimal Sum3(int n)
2 {
3 decimal sum = 0;
4 for (int a = 0; a < n; a++)
5 for (int b = 0; b < n; b++)
6 for (int c = 0; c < n; c++)
7 sum += a b c;
8 return sum;
9 }
復制代碼
這里，給定規(guī)模 n，則基本步驟的執(zhí)行數(shù)量約為 nnn ，所以算法復雜度為 O(n3)。

示例代碼（6）：

復制代碼
1 decimal Calculation(int n)
2 {
3 decimal result = 0;
4 for (int i = 0; i < (1 << n); i++)
5 result += i;
6 return result;
7 }
復制代碼
這里，給定規(guī)模 n，則基本步驟的執(zhí)行數(shù)量為 2n，所以算法復雜度為 O(2n)。

示例代碼（7）：

斐波那契數(shù)列：

Fib(0) = 0
Fib(1) = 1
Fib(n) = Fib(n-1) + Fib(n-2)
F() = 0, 1, 1, 2, 3, 5, 8, 13, 21, 34 ...

復制代碼
1 int Fibonacci(int n)
2 {
3 if (n <= 1)
4 return n;
5 else
6 return Fibonacci(n - 1) + Fibonacci(n - 2);
7 }
復制代碼
這里，給定規(guī)模 n，計算 Fib(n) 所需的時間為計算 Fib(n-1) 的時間和計算 Fib(n-2) 的時間的和。

T(n<=1) = O(1)

T(n) = T(n-1) + T(n-2) + O(1)

                 fib(5)   
             /                  
       fib(4)                fib(3)   
     /                      /     
 fib(3)      fib(2)         fib(2)    fib(1)
/             /           /      

通過使用遞歸樹的結(jié)構(gòu)描述可知算法復雜度為 O(2n)。

示例代碼（8）：

復制代碼
1 int Fibonacci(int n)
2 {
3 if (n <= 1)
4 return n;
5 else
6 {
7 int[] f = new int[n + 1];
8 f[0] = 0;
9 f[1] = 1;
10
11 for (int i = 2; i <= n; i++)
12 {
13 f[i] = f[i - 1] + f[i - 2];
14 }
15
16 return f[n];
17 }
18 }
復制代碼
同樣是斐波那契數(shù)列，我們使用數(shù)組 f 來存儲計算結(jié)果，這樣算法復雜度優(yōu)化為 O(n)。

示例代碼（9）：

復制代碼
1 int Fibonacci(int n)
2 {
3 if (n <= 1)
4 return n;
5 else
6 {
7 int iter1 = 0;
8 int iter2 = 1;
9 int f = 0;
10
11 for (int i = 2; i <= n; i++)
12 {
13 f = iter1 + iter2;
14 iter1 = iter2;
15 iter2 = f;
16 }
17
18 return f;
19 }
20 }
復制代碼
同樣是斐波那契數(shù)列，由于實際只有前兩個計算結(jié)果有用，我們可以使用中間變量來存儲，這樣就不用創(chuàng)建數(shù)組以節(jié)省空間。同樣算法復雜度優(yōu)化為 O(n)。

示例代碼（10）：

通過使用矩陣乘方的算法來優(yōu)化斐波那契數(shù)列算法。

復制代碼
1 static int Fibonacci(int n)
2 {
3 if (n <= 1)
4 return n;
5
6 int[,] f = { { 1, 1 }, { 1, 0 } };
7 Power(f, n - 1);
8
9 return f[0, 0];
10 }
11
12 static void Power(int[,] f, int n)
13 {
14 if (n <= 1)
15 return;
16
17 int[,] m = { { 1, 1 }, { 1, 0 } };
18
19 Power(f, n / 2);
20 Multiply(f, f);
21
22 if (n % 2 != 0)
23 Multiply(f, m);
24 }
25
26 static void Multiply(int[,] f, int[,] m)
27 {
28 int x = f[0, 0] m[0, 0] + f[0, 1] m[1, 0];
29 int y = f[0, 0] m[0, 1] + f[0, 1] m[1, 1];
30 int z = f[1, 0] m[0, 0] + f[1, 1] m[1, 0];
31 int w = f[1, 0] m[0, 1] + f[1, 1] m[1, 1];
32
33 f[0, 0] = x;
34 f[0, 1] = y;
35 f[1, 0] = z;
36 f[1, 1] = w;
37 }
復制代碼
優(yōu)化之后算法復雜度為O(log2n)。

示例代碼（11）：

在 C# 中更簡潔的代碼如下。

復制代碼
1 static double Fibonacci(int n)
2 {
3 double sqrt5 = Math.Sqrt(5);
4 double phi = (1 + sqrt5) / 2.0;
5 double fn = (Math.Pow(phi, n) - Math.Pow(1 - phi, n)) / sqrt5;
6 return fn;
7 }
復制代碼
示例代碼（12）：

插入排序的基本操作就是將一個數(shù)據(jù)插入到已經(jīng)排好序的有序數(shù)據(jù)中，從而得到一個新的有序數(shù)據(jù)。算法適用于少量數(shù)據(jù)的排序，時間復雜度為 O(n2)。

復制代碼
1 private static void InsertionSortInPlace(int[] unsorted)
2 {
3 for (int i = 1; i < unsorted.Length; i++)
4 {
5 if (unsorted[i - 1] > unsorted[i])
6 {
7 int key = unsorted[i];
8 int j = i;
9 while (j > 0 && unsorted[j - 1] > key)
10 {
11 unsorted[j] = unsorted[j - 1];
12 j--;
13 }
14 unsorted[j] = key;
15 }
16 }
17 }
復制代碼