1.為什麼需要複雜度分析
雖然将代碼執行⼀遍，通過統計、監控等手段就能得到算法執行時間和占用記憶體大小（有些書上将這種方法稱為事後統計法），但是這種方法有2個局限性。
- 測試結果非常依賴測試環境。
- 測試結果受資料規模影響很大。
是以一般不采用這種方法，而是采用時間複雜度和空間複雜度兩方面來表示算法複雜度。
2.大O時間複雜度的由來與表示方法
eg1.
int cal(int n){
int sum = 0;
int i = 1;
for (;i <= n;i++){
sum = sum + i;
}
return sum;
}
假設執行每行代碼的時間是n，則總時間T(n) = 2n + 3（一個循環條件n次，循環結果n次，共2n次）
eg2.
int cal(int n) {
int sum = 0;
int i = 1;
int j = 1;
for (; i <= n; ++i){
j = 1;
for (; j <= n; ++j) {
sum = sum + i * j;
}
}
}
外部for循環執行了2n次，内部for循環執行了2n^2, 是以T(n) = 3+2n+2n^2
至此，我們可以總結出一個規律：所有代碼的執行時間 T(n) 與每行代碼的執行次數 n 成正比，可以寫成一個公式：T(n) = O(f(n))。T(n)表示代碼執行的總時間，n表示資料規模的大小，f(n)表示每段代碼執行的次數之和，O表示T(n)與f(n)成正比。這就是大O時間複雜度表示法。
注：大O時間複雜度實際并不是代碼時間執行時間，隻是表示一種資料代碼執行時間，随資料規模增長的變化趨勢。是以也叫做漸進時間複雜度，簡稱：時間複雜度
3.時間複雜度如何分析
1.隻關注循環次數最多的那一段代碼
2.加法法則：總複雜度等于量級最大的那一段代碼的複雜度
時間複雜度表示的是一種趨勢，是以可以忽略掉低階、常量、系數，隻用關心最高階即可。
是以eg1的時間複雜度為O(n)，eg2為O(n^2)
3.乘法法則：嵌套代碼的複雜度等于嵌套内外代碼複雜的乘積
eg3.
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;
}
for(int i = 0;i < n;i++){
for(int j = 0; j < i;j++){}
}
這兩種時間複雜度為O(n^2)
4.常見的的時間複雜度：
1.多項式時間複雜度：
除O(1),O(n),O(n^2)外常見的還有O(logn)、O(nlogn)、O(m + n)、O(m * n)
1.1 O(1):
隻要代碼不随n的增長而變化，即為這O(1)。
1.2 O(logn):
eg4.
int i = 1;
while(i <= n) {
i = i * 2;
}
i每循環一次就乘2，是以循環m次之後，2^m > n，則m = log ( n ) \log(n) log(n)次。
根據換底公式，所有對數形式的都可以換為以2為底的對數.
1.3 O(nlogn):
eg5.
int i = 1;
for(int i = 0;i < n;i++){
while(i <= n) {
i = i * 2;
}
}
1.4 O(m + n)
eg6.
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的量級大小，是以無法直接省略掉一個，是以為(m + n)。
O(m * n) 同理。
2.非多項式時間複雜度：（這種情況較少，當n越來越大時，非多項式的時間複雜度急劇增加，是以非多項式的算法基本不用）
O(2^n)
O(n!)
5.最好，最壞，平均時間複雜度
eg7.
int find(int[] array, int n, int x) {
int i = 0;
int pos = -1;
for (; i < n; ++i) {
if (array[i] == x) {
pos = i;
break;
}
}
return pos;
}
最好情況：O(1)
最壞情況：O(n)
平均：共有（n + 1）種情況，n種在數組中，一種不在數組中，權重平均之後，時間複雜度還是為O(n)
也可以這樣了解：最平均的話就是在最中間的那個位置，當n逐漸變大的時候，中間的次數也會變化，是以也是O(n)
6.空間複雜度分析
空間複雜度是對一個算法在運作臨時占用存儲空間大小的度量。
eg8.
public static int sum(int n) {
int count = 0;
for (int i = 1; i <= n; i++) {
count += i;
}
return count;
}
算法執行所需要的臨時空間不随着某個變量n的大小而變化，即此算法空間複雜度為一個常量，可表示為S(n) = O(1)。
eg9.
int[] m = new int[n]
for(i=1; i<=n; ++i)
{
j = i;
j++;
}
這段代碼中，第一行new出來一個數組之後占用的空間大小為n，，此後幾行雖然有循環，但是沒有再配置設定新的空間，是以這段代碼的複雜度隻用看第一行即可，S(n) = O(n)
附：
