時間複雜度、空間複雜度以及分析方法
在學習資料結構與演算法的時候，總不擴音到時間複雜度以及空間複雜度這兩個概念，以及每次對所寫程式碼進行的複雜度分析等，最近這段時間學習資料結構與演算法時對這兩個概念的理解比之前好些了，這篇文章記錄下最基礎的概念以及常見的時間/空間複雜度。
時間複雜度
先說下時間複雜度：描述一個演算法執行時間與資料規模的增長關係 ，通常用 T(n) = O(f(n)) 來表示，這裡的 n 表示資料的規模，f(n) 每行程式碼執行的次數總和。這裡重點在於增長關係 這幾個字，一個演算法的時間複雜度，通常只需要考慮 n 的增長規模，這裡的 n 指的是每段程式碼的執行次數，所以時間複雜度大多都只看迴圈、遞迴來分析，而與那些常數、係數等無關。舉個例子：
function calc(n){
var sum = 0;
var i = 1;
for (; i < n; i++ ){
sum += i;
}
return sum;
}
這段程式碼可以累加從 0 到 n 的和，我們這樣對它進行分析：第 2、3 行程式碼需要執行一次，第 4、5 行需要執行 n 次，總的就是 2n 次，所以它的時間複雜度為 O(2n + 2)，但是因為係數、常數這些對 n 的增長規模沒有影響，不需要考慮，可以忽略，如果是 n² 那就有影響了，都已經到平方階了。所以這樣看其時間複雜度為 O(n) 。
類似於這樣的程式碼不用分析，時間複雜度都是常量級的 O(1)，因為它並沒有體現出 n 的增長規模關係，就算程式碼在多時間複雜度也是一樣的，換句話說，一段程式碼裡沒有迴圈啊、遞迴等語句，通常時間複雜度都是 O(1) 。再下面在看下這段程式碼：
function(n){
var sum = 0;
for(var i = 1; i <= n; i++){
for(var j = 1; j <= n; j++){
sum += i*j;
}
}
return sum;
}
像這種嵌套了兩層 for 迴圈的程式碼，兩行程式碼分別執行了 n 遍，並且是巢狀，時間複雜度就是 O(n²)。
分析小技巧
- 如果沒有迴圈或遞迴，都是常量級的程式碼，時間複雜度就是 O(1)
- 只關注迴圈次數最多的一段程式碼，它的量級就可作為整段程式碼的時間複雜度
- 如果是 for 迴圈巢狀的程式碼，採用乘法計算其內外複雜度；如果是一個函式裡有多段程式碼，則分析出每一段程式碼的時間複雜度，在將它們相加，最後去掉係數以及常數，取最大量級的作為整段程式碼的時間複雜度。例如，O(2n²+n+2) 則簡化為 O(n²)
空間複雜度
類比時間複雜度，空間複雜度的概念在幾個字上不一樣，完整表述為:描述一個算法佔用空間與資料規模的增長關係 。如下程式碼：
function print(n){
var i = 0;
var arr = new Array(n);
for(i;i<n;i++){
arr[i] = i * i;
}
}
同樣的，第二行程式碼申請了儲存空間 i，但它是常量階的，跟資料的增長規模沒有關係，所以不用理；第三行程式碼申請了一個容量為 n 的陣列，剩下的程式碼都沒有涉及到佔用空間了，所以整段程式碼的空間複雜度為 O(n) 。常見的空間複雜度不多，就 O(1)、O(n)、O(n²) 這幾個，其餘對數階的那些一般很少應用到。
常見的複雜度
常見的複雜度從低階到高階有：O(1)、O(logn)、O(n)、O(nlogn)、O(n²)