如何分析、統計算法的執行效率和資源消耗：
一個概念：複雜度分析
兩個名額：時間複雜度，空間複雜度
一個表示法：大O複雜度表示法
三大實用法則
一：大O複雜度舉例說明
第一步：概念解釋
1 int cal(int n) {
2 int sum = 0;
3 int i = 1;
4 for (; i <= n; ++i) {
5 sum = sum + i;
6 }
7 return sum;
8}
如何計算該該處代碼的運作時間，假設每一行執行的時間為time
則 第二行1time，第三行1time，四五行都執行了n遍則2n*time,一共執行時間為(2n+2)*time.
結論：所有代碼的執行時間 T(n) 與每行代碼的執行次數成正比
再來看一個例子：
1 int cal(int n) {
2 int sum = 0;
3 int i = 1;
4 int j = 1;
5 for (; i <= n; ++i) {
6 j = 1;
7 for (; j <= n; ++j) {
8 sum = sum + i * j;
9 }
10 }
11}
結論：同上理可得整段代碼的執行時間：T(n) = (2n2+2n+3)*time；
通過以上兩個例子我們可以得出：所有代碼的執行時間 T(n) 與每行代碼的執行次數 n 成正比。
總結出來一個公式就是：
T(n) 表示代碼執行的時間；n 表示資料規模的大小；f(n) 表示每行代碼執行的次數總和。因為這是一個公式，是以用 f(n) 來表示。公式中的 O，表示代碼的執行時間 T(n) 與 f(n) 表達式成正比。
最後，這就是大 O 時間複雜度表示法。大 O 時間複雜度實際上并不具體表示代碼真正的執行時間，而是表示代碼執行時間随資料規模增長的變化趨勢，是以，也叫作漸進時間複雜度（asymptotic time complexity），簡稱時間複雜度。
注：當 n 很大時，你可以把它想象成 10000、100000。而公式中的低階、常量、系數三部分并不左右增長趨勢，是以都可以忽略。我們隻需要記錄一個最大量級就可以了，如果用大 O 表示法表示剛講的那兩段代碼的時間複雜度，就可以記為：T(n) = O(n)； T(n) = O(n2)。
二：三大法則
一：隻關注循環執行次數最多的一段代碼
由于大 O 這種複雜度表示方法隻是表示一種變化趨勢。我們通常會忽略掉公式中的常量、低階、系數，隻需要記錄一個最大階的量級就可以了。我們在分析一個算法、一段代碼的時間複雜度的時候，也隻關注循環執行次數最多的那一段代碼就可以了
例如我們上面的例子1：
int cal(int n) {
int sum = 0;
int i = 1;
for (; i <= n; ++i) {
sum = sum + i;
}
return sum;
}
可以忽略2，3行代碼，隻考慮執行次數最多的4，5行，複雜度為O(n)
二：加法法則：總複雜度等于量級最大的那段代碼的複雜度
int cal(int n) {
int sum_1 = 0;
int p = 1;
for (; p < 100; ++p) {
sum_1 = sum_1 + p;
}
int sum_2 = 0;
int q = 1;
for (; q < n; ++q) {
sum_2 = sum_2 + q;
}
int sum_3 = 0;
int i = 1;
int j = 1;
for (; i <= n; ++i) {
j = 1;
for (; j <= n; ++j) {
sum_3 = sum_3 + i * j;
}
}
return sum_1 + sum_2 + sum_3;
}
可以看出三個地方的主要複雜度為：sum_1由于是常量級的計算，與n無關，是以複雜度為O(1)，sum_2顯而易見的為O(n)，sum_3為O(n的平方)。
最終複雜度計算為總的時間複雜度就等于量級最大的那段代碼的時間複雜，即O(n的平方)
法則三：乘法法則：嵌套代碼的複雜度等于嵌套内外代碼複雜度的乘積
int cal(int n) {
int ret = 0;
int i = 1;
for (; i < n; ++i) {
ret = ret + f(i);
}
}
int f(int n) {
int sum = 0;
int i = 1;
for (; i < n; ++i) {
sum = sum + i;
}
return sum;
}
可以看出分别的cal()和f()的複雜度為O(n)，但是由于在實際應用中cal()函數中調用了f()，是以整個cal()的時間複雜度為O(n*n)即O(n的平方)。
補充：
常見的幾種時間複雜度執行個體分析：
對于剛羅列的複雜度量級，我們可以粗略地分為兩類，多項式量級和非多項式量級。其中，非多項式量級隻有兩個：O(2n) 和 O(n!)。
我們把時間複雜度為非多項式量級的算法問題叫作 NP（Non-Deterministic Polynomial，非确定多項式）問題。
主要的多項式時間複雜度的分析：
1：O(1)
int i = 8;
int j = 6;
int sum = i + j;
一般情況下，隻要算法中不存在循環語句、遞歸語句，即使有成千上萬行的代碼，其時間複雜度也是Ο(1)。
2:O(logn)、O(nlogn)
i=1;
while (i <= n) {
i = i * 2;
}
從代碼中可以看出，變量 i 的值從 1 開始取，每循環一次就乘以 2。當大于 n 時，循環結束,實際上，變量 i 的取值就是一個等比數列。如果我把它一個一個列出來，就應該是這個樣子的：
是以，我們隻要知道 x 值是多少，就知道這行代碼執行的次數了。通過 2x=n 求解 x 這個問題我們想高中應該就學過了，我就不多說了。x=log2n，是以，這段代碼的時間複
雜度就是 O(log2n)。
如果把代碼稍微改成這樣
i=1;
while (i <= n) {
i = i * 3;
}
這段代碼的時間複雜度為 O(log3n)。
實際上，不管是以 2 為底、以 3 為底，還是以 10 為底，我們可以把所有對數階的時間複雜度都記為 O(logn)。為什麼呢？我們知道，對數之間是可以互相轉換的，log3n 就等于 log32 * log2n，是以 O(log3n) = O(C * log2n)，其中 C=log32 是一個常量。基于我們前面的一個理論：在采用大 O 标記複雜度的時候，可以忽略系數，即 O(Cf(n)) = O(f(n))。是以，O(log2n) 就等于 O(log3n)。是以，在對數階時間複雜度的表示方法裡，我們忽略對數的“底”，統一表示為 O(logn)。
如果一段代碼的時間複雜度是 O(logn)，我們循環執行 n 遍，時間複雜度就是 O(nlogn) 了。而且，O(nlogn) 也是一種非常常見的算法時間複雜度。比如，歸并排序、快速排序的時間複雜度都是 O(nlogn)。
3：O(m+n)、O(m*n)
int cal(int m, int n) {
int sum_1 = 0;
int i = 1;
for (; i < m; ++i) {
sum_1 = sum_1 + i;
}
int sum_2 = 0;
int j = 1;
for (; j < n; ++j) {
sum_2 = sum_2 + j;
}
return sum_1 + sum_2;
}
從代碼中看出，m和n的量級無法判斷量級，就不能簡單地利用加法法則，省略掉其中一個。是以，上面代碼的時間複雜度就是 O(m+n)。
空間複雜度分析：
空間複雜度全稱就是漸進空間複雜度（asymptotic space complexity），表示算法的存儲空間與資料規模之間的增長關系。