iT邦幫忙

第 12 屆 iThome 鐵人賽

DAY 10
0
Software Development

One Punch 一拳搞定前後端面試系列 第 10

[One Punch 一拳搞定前後端面試] DAY-10 - 時間複雜度

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

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

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

此文同時發佈於好讀版


上一篇
[One Punch 一拳搞定前後端面試] DAY-09 - 字串搜尋
下一篇
[One Punch 一拳搞定前後端面試] DAY-11 - 費氏數列
系列文
One Punch 一拳搞定前後端面試30

尚未有邦友留言

立即登入留言