時間複雜度 (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

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

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

此文同時發佈於好讀版