一、前導知識

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)

這個範例中只有一個步驟，就是計算並回傳 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 次。

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

1.2.3 Linear Time O(n)

(念 Big O n)

所以執行次數是 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。

總共需要執行：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)

若此題假設 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 loop，但是裡面用到了 indexOf 和 lastIndexOf 會去搜尋整個 input 的數值，所以這個範例的 Time complexity 其實會是 O(n^2) 而不是 O(n)，在使用和計算上還是要小心注意。

1.3 Space complexity

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

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

這裡建立的變數 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 個別數字的總計。

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

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

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

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

二、References

--
相關文章

工程師英國找工作紀錄 :: 抓住那個工程師

2022/03/22

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