時間複雜度 (Time Complexity)#

用來表示程式執行的時間與速度表現。通常與程式內的演算法有關,

例如,當我們再加入一個 input 到某程式時,執行時的時間會變久嗎?多了多久?等等...

這通常會在您面試時的上機考,題目會限制您的程式執行時間,

或是在白板題,面試官會要您描述為什麼兩支程式速度不同?或者某程式該如何改進...

範例說明#

這邊用前面幾篇的題目來說明時間複雜度,體會一下:

回顧字串反轉來說明一種時間複雜度#

在我們之前的章節,字串反轉

function reverseString(str){
let result = '';
for(let i = str.length; i>=1; i--){
result += str[i-1]
}
return result
}

上面程式,我們的 str 字串,假如再多加一個字元,就會讓回圈多跑一次,

這個時間複雜度我們稱為 線性時間(Linear Run Time),也稱為 N

回顧樓梯測驗來說明另一種時間複雜度#

再看一下我們前幾章的樓梯測驗:

function steps(n) {
for (let row = 0; row < n; row++) {
let aStep = '';
for (let col = 0; col < n; col++) {
if (col <= row) {
aStep += '@';
} else {
aStep += ' ';
}
}
console.log(aStep);
}
}

在樓梯測驗中 n 每增加一次,都會多跑好幾次(n * n 次):

n = 2 時,會跑 2 * 2 = 4 次
n = 3 時,會跑 3 * 3 = 9 次
n = 4 時,會跑 4 * 4 = 16 次

這時我們稱這種時間複雜度為 平方時間(Quadratic Time Complexity)。也稱為 N^2

其他常見時間複雜度#

這邊稍微說明一下常見的時間複雜度,在面試或上機考時,可能會遇見其中一種,或是兩種的結合:

常數時間(Constant Time)#

表示法:1

輸入到程式的資料量增加,但執行時間不變:

比如有個神奇的演算法可以把樓梯測驗寫成 n 增加但時間不變,那這種時間複雜度就是常數時間。

對數時間(Logarithmic Time)#

表示法:log(n)

輸入到程式的資料量增加,但執行時間一開始增加,到一定程度後無明顯增加。

這種情況會發生在做二元搜尋的時候,後面章節我們會介紹。

線性對數時間 (Quasilinear Time)#

表示法:n * log(n)

通常在比較排列時會用到,比如以下所需的時間:

新的班級座號都是隨機的,這時要用姓名的筆畫多少來排列,修正座號順序,然後在新的座號表上寫上新的座號。

指數時間(Exponential Time)#

表示法:2 ^ N

隨著輸入資料變多,需要執行的時間以指數增加。

通常我們會避免這種演算法,因為這是時間效率最不好的。因此面試時要盡量避免。

此文同時發佈於鐵人賽