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

目錄一、前導知識
       1.1 演算法評估標準
       1.2 Time complexity
              1.2.1 Constant Time O(1) 
              1.2.2 Logarithmic Time O(log(n)) 
              1.2.3 Linear Time O(n)
              1.2.4 Log Linear Time O(n log (n))
              1.2.5 Exponential Time O(n^2)
              1.2.6 總結
       1.3 Space complexity
       1.4 時間複雜度和空間複雜度的 Trade-off
二、References

一、前導知識

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