簡單輕鬆十分鐘看懂 Time complexity & Space complexity 分析刷 LeetCode

一、前導知識

1.1 演算法評估標準

當同一個問題可以用不同演算法去解決時，需要一個評量的標準去評估哪個演算法比較好，通常會用兩個指標去評量演算法的好壞 :

• Time complexity (時間複雜度)
• Space complexity (空間複雜度)

當然理論上所花費的時間和占用的記憶體是越小越好。

1.2 Time complexity

Time complexity 是電腦執行演算法所需要耗費的時間成本，通常會用 O (Big O notation) 去計算。

Big O notation 是解決一個規模為 n 的問題所花費的時間，或者所需步驟之數目；而演算法多快通常不是以秒而是步驟次數來衡量，因為每個人電腦效能會影響執行速度，若用秒數來衡量會顯得不夠客觀。

1.2.1 Constant Time O(1) 

(念 Big O one)

	function sum(a, b) {
	return a + b; // Return 結果，執行 1 次
	}

view raw Time complexity - O(1) hosted with ❤ by GitHub

這個範例中只有一個步驟，就是計算並回傳 a + b 的值，所以不管 a 或 b 有多大都不影響執行的步驟數目，執行時間不會隨著輸入資料量的增加而增加，故 Time complexity 為 O(1)。

可以稍微簡化成 : 沒用到任何 loop 所以 Time complexity 為 O(1)。

1.2.2 Logarithmic Time O(log(n)) 

(念 Big O log n)

在演算法中，log n 的慣例指的是以 2 為底的意思，也就是 2 的幾次方，如 log n = x 是指 n = 2^x。

通常可以能夠對半處理的都屬於 O(log n) 的演算法，比如 binary search；假設 n 是 8，而 log 8 = 3，所以這個演算法會跑 3 次；假設 n 是 9，則這個演算法會跑 4 次。

	function powerOf2(n) {
	let x = 0; // Assign 數值給變數 ，執行 1 次
	while (n > 1) {
	n = n / 2; // 4，執行 2 次；8，執行 3 次 ... n，執行 log n 次
	x++; // 4，執行 2 次；8，執行 3 次 ... n，執行 log n 次
	}
	return x; // Return 結果，執行 1 次
	}

view raw Time complexity - O(log n) hosted with ❤ by GitHub

總共需要執行：1 + 2*log n + 1 = 2*log n + 2，忽略常數的係數，故這裡的 Time complexity 會是 O(log (n))。

1.2.3 Linear Time O(n)

(念 Big O n)

	function listSum(n) {
	let result = 0; // Assign 數值給變數，執行 1 次
	for (let i = 0; i < n.length; i++) { // Loop array 執行 n 次
	result += n[i];
	}
	return result; // Return 結果，執行 1 次
	}

view raw Time complexity - O(n) hosted with ❤ by GitHub

所以執行次數是 1 + n + 1 = n + 2，但如果在 n 相當大的時候，2 就不是那麼重要了，所以我們在比較的時候可只比較最高次方就好，忽略常數的係數，故這裡的 Time complexity 會是 O(n)。

可以稍微簡化成 : 

若是一個 loop 則是 O(n) 

若是兩個 loop 則是 O(n) + O(n) = O(2n) = O(n) 

...

若是 X 個 loop 則是 O(n) + O(n) …. + O (n) = O(Xn) = O(n)

1.2.4 Log Linear Time O(n log (n))

(念 Big O n log n)

時間複雜度為 O(n log (n)) 的演算法，代表著執行時間會隨著以二為底的 log n 再乘上 n 成長。最常見的例子是 Merge Sort、Quick Sort 和 Heap Sort。

	let x = n; // Assign 數值給變數 ，執行 1 次
	while (x > 0) {
	let y = x; // Assign 數值給變數 ，執行 1 次
	while (y > 0) { // 假設 n = 4，執行 2 次；假設 n = 8，執行 3 次 ... n，執行 logn 次
	y = Math.floor(y / 2);
	} // 整段迴圈會因為 n 的改變而增加次數，是 n log (n)
	x = x - 1; // Assign 數值給變數 ，執行 1 次
	}

view raw Time complexity - O(n log n) hosted with ❤ by GitHub

總共需要執行：1 + 1 + n log (n) + 1，忽略常數的係數，故這裡的 Time complexity 會是 O(n log (n))。

1.2.5 Exponential Time O(n^2)

(念 Big O n square / quadratic)

	function TwoListsSum(m, n) {
	for (let i = 0; i < m.length; i++) { // Loop array 執行 m 次
	for (let j = 0; j < n.length; j++) { // Loop array 執行 n 次
	console.log(m[i] * n[j]); // 執行 loop i 的 m 次 * loop j 的 n 次 = m*n 次
	}
	}
	}

view raw Time complexity - O(n^2) hosted with ❤ by GitHub

若此題假設 m === n，則總共需要執行：m + n + m*n = n + n + n*n = 2n + n^2，一樣忽略常數的係數，故這裡的 Time complexity 會是 O(n^2)。

若此題假設 m !== n，則總共需要執行：m + n + m*n 這裡的 Time complexity 會是 O(m*n)。

可以稍微簡化成 :
一層 loop ⇒ O(n)
兩層 loop ⇒ O(n^2)
…
x 層 loop ⇒ O(n^x) → 念 Big O n to the x

1.2.6 總結

(https://www.youtube.com/watch?v=47GRtdHOKMg&ab_channel=DataDaft)

由圖可看出來 O(n^2)、 O(n^3) … O(n^x)、O(2^n)、O(n!) 的 Time complexity 比其他高很多，尤其是當 input data 增加時，時間更是大幅的增加；所以通常希望演算法的 Time complexity 最佳到最差的排序是 O(1), O(log(n)), O(n), O(n log(n)), O(n^2), O(n^3) … O(n^n), O(2^n), O(n!)

題外話，在刷題時是用 Time complexity 去比較，而實務上要採用哪種方式則是要看需求。

Time complexity 是理論上程式執行的時間，而 Running time 是實務上程式執行的時間。Time complexity 低不代表 Running time 就一定低。

--
前面有說到一些簡單的判斷 Time complexity 的方式，比如說有沒有 for loop，但不是都單靠這些就可以正確的判斷，比如說以下這個範例 :

	for (let i = 0; i < s.length; i++) {
	if (s.indexOf(s[i]) === s.lastIndexOf(s[i])) {
	return i;
	}
	}
	return -1;

view raw Time complexity - example hosted with ❤ by GitHub

他雖然只有用到一個 for loop，但是裡面用到了 indexOf 和 lastIndexOf 會去搜尋整個 input 的數值，所以這個範例的 Time complexity 其實會是 O(n^2) 而不是 O(n)，在使用和計算上還是要小心注意。

1.3 Space complexity

Space complexity 是計算演算法執行時所花費的記憶體空間成本，
計算方式與 Time complexity 相似，也是使用 Big O notation 來表示其複雜度。

	const add = (n) => {
	let total = ;
	for(let i=0; i<n; i++){
	total += i;
	}
	return total;
	}

view raw Space complexity - example 1 hosted with ❤ by GitHub

不管輸入的 n 為多少，都只會建立一個變數 total，因此 Space complexity 為 O(1)。

	const createArray = (n) => {
	const arr = [];
	for (let i = 0; i < n; i++) {
	arr.push(i);
	}
	return arr;
	};

view raw Space complexity - example 2 hosted with ❤ by GitHub

這裡建立的變數 arr 的長度會根據使用者輸入的 n 增長，因此 Space complexity 為 O(n)。

可以稍微簡化成 :
不用任何 array ⇒ O(1)
若是兩個 array 則是 O(n) + O(n) = O(2n) = O(n)
...
若是 X 個 array 則是 O(n) + O(n) …. + O (n) = O(xn) = O(n)

一維 array ⇒ O(n)
二維 array ⇒ O(n^2)
…
X 維 array ⇒ O(n^X)

但一樣要注意的是，不是都單靠有沒有建立空 array 就可以正確的判斷，比如說以下這個範例 : 計算以下 arr 個別數字的總計。

	let arr = [1,2,3,4,5]
	// 常見計算法
	let total = 0;
	for (let i = 0; i < arr.length; i++) {
	total += arr[i];
	}
	// 用 recursion 方式計算
	const recursion = (arr, n) => {
	if (n <= 0) return 0;
	const x = arr[n - 1];
	return recursion(arr, n - 1) + x;
	}

view raw Space complexity - example 3 hosted with ❤ by GitHub

用常見方式計算的 Time complexity 是 O(n)，Space complexity 是 O(1)；

而用 recursion 方式計算的 Time complexity 是 O(n)，Space complexity 是 O(n)。

1.4 時間複雜度和空間複雜度的 Trade-off

在某些情況下，可以用記憶體空間來多存取資訊，省去重複運算來節省時間；如果沒有多餘的記憶體可以使用，則可以把需要靠記憶體空間存取的資訊靠重複運算來取得。

二、References

• How to compute Time Complexity or Order of Growth of any program
• 【演算法】時間複雜度與空間複雜度Time & Space Complexity
• Big O Notation, Time Complexity & Space Complexity
• 初學者學演算法｜談什麼是演算法和時間複雜度

--
相關文章

• Coding Interview 就是刷好刷滿刷爆 LeetCode 就會上?
• 簡單輕鬆十分鐘學會 Hash Map (雜湊表) 刷 LeetCode