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

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

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

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

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

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

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

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

忽略掉那些依賴于機(jī)器的常量。
關(guān)注運(yùn)行時(shí)間的增長(zhǎng)趨勢(shì)。
比如：T(n) = 73n3 + 29n3 + 8888 的趨勢(shì)就相當(dāng)于 T(n) = Θ(n3)。

漸近記號(hào)（Asymptotic Notation）通常有 O、 Θ 和 Ω 記號(hào)法。Θ 記號(hào)漸進(jìn)地給出了一個(gè)函數(shù)的上界和下界，當(dāng)只有漸近上界時(shí)使用 O 記號(hào)，當(dāng)只有漸近下界時(shí)使用 Ω 記號(hào)。盡管技術(shù)上 Θ 記號(hào)較為準(zhǔn)確，但通常仍然使用 O 記號(hào)表示。

使用 O 記號(hào)法（Big O Notation）表示最壞運(yùn)行情況的上界。例如，

線性復(fù)雜度 O(n) 表示每個(gè)元素都要被處理一次。
平方復(fù)雜度 O(n2) 表示每個(gè)元素都要被處理 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).
相當(dāng)于:

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

復(fù)雜度 標(biāo)記符號(hào) 描述
常量（Constant）
O(1)

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

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

對(duì)數(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ù)級(jí)的操作，快速的增長(zhǎng)。

n = 20 -> 1048576 operations

注1：快速的數(shù)學(xué)回憶，logab = y 其實(shí)就是 ay = b。所以，log24 = 2，因?yàn)?22 = 4。同樣 log28 = 3，因?yàn)?23 = 8。我們說(shuō)，log2n 的增長(zhǎng)速度要慢于 n，因?yàn)楫?dāng) n = 8 時(shí)，log2n = 3。

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

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

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

而通常時(shí)間復(fù)雜度與運(yùn)行時(shí)間有一些常見(jiàn)的比例關(guān)系：

復(fù)雜度 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

計(jì)算代碼塊的漸進(jìn)運(yùn)行時(shí)間的方法有如下步驟：

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

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

示例代碼（2）：

復(fù)制代碼
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 }
復(fù)制代碼
這里，n 為數(shù)組 array 的大小，則最壞情況下需要比較 n 次以得到最大值，所以算法復(fù)雜度為 O(n)。

示例代碼（3）：

復(fù)制代碼
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 }
復(fù)制代碼
這里，n 為數(shù)組 array 的大小，則基本步驟的執(zhí)行數(shù)量約為 n*(n-1)/2，所以算法復(fù)雜度為 O(n2)。

示例代碼（4）：

復(fù)制代碼
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 }
復(fù)制代碼
給定規(guī)模 n 和 m，則基本步驟的執(zhí)行數(shù)量為 n*m，所以算法復(fù)雜度為 O(n2)。

示例代碼（5）：

復(fù)制代碼
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 }
復(fù)制代碼
這里，給定規(guī)模 n，則基本步驟的執(zhí)行數(shù)量約為 nnn ，所以算法復(fù)雜度為 O(n3)。

示例代碼（6）：

復(fù)制代碼
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 }
復(fù)制代碼
這里，給定規(guī)模 n，則基本步驟的執(zhí)行數(shù)量為 2n，所以算法復(fù)雜度為 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 ...

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

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)
/             /           /      

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

示例代碼（8）：

復(fù)制代碼
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 }
復(fù)制代碼
同樣是斐波那契數(shù)列，我們使用數(shù)組 f 來(lái)存儲(chǔ)計(jì)算結(jié)果，這樣算法復(fù)雜度優(yōu)化為 O(n)。

示例代碼（9）：

復(fù)制代碼
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 }
復(fù)制代碼
同樣是斐波那契數(shù)列，由于實(shí)際只有前兩個(gè)計(jì)算結(jié)果有用，我們可以使用中間變量來(lái)存儲(chǔ)，這樣就不用創(chuàng)建數(shù)組以節(jié)省空間。同樣算法復(fù)雜度優(yōu)化為 O(n)。

示例代碼（10）：

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

復(fù)制代碼
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 }
復(fù)制代碼
優(yōu)化之后算法復(fù)雜度為O(log2n)。

示例代碼（11）：

在 C# 中更簡(jiǎn)潔的代碼如下。

復(fù)制代碼
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 }
復(fù)制代碼
示例代碼（12）：

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

復(fù)制代碼
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 }
復(fù)制代碼