Function 的時間複雜度

在電腦科學中，演算法的時間複雜度 Time complexity 可以描述該演算法的執行時間

時間複雜度常用大 O (Big O Notation)符號表述，不包括這個函式的低階項和首項係數

時間複雜度是想探討問題，當function 的input 變大，他所需要執行的時間會如何增長

例如，有 f(x)，執行 function，input 是 f(1)時，需要執行的總時間是 k，假設放大 10 倍，變成 f(10)所需要的總時長是多少?

或是，如果一個演算法對於任何大小為 𝑛（必須比 𝑛0 大）的輸入，它需要 5𝑛^3 + 3𝑛 的時間 執行完畢，那麼它的漸近時間複雜度是 O(𝑛^3)

為了計算時間複雜度，我們通常會估計演算法的操作單元數量，每個單元執行的時間都是相同的

所以直觀上來說，時間複雜度就是，在參數逐漸變大的情況下，Function 執行完畢所需要的時間的成長速度

舉例

1. 若調用函數 𝑓(𝑥)，𝑓(10)需要的時間是 5 秒，但 𝑓(50)需要的時間是 125 秒，則參數變大 5 倍，卻導致 𝑓(𝑥)的執行時間成長 25 倍，那麼參數的成長會導致函式執行時間平方倍成長，我們就說，𝑓(𝑥)的時間複雜度是 𝑂(𝑛^2)

2. 若調用函數 g(𝑥)，g(10)需要的時間是 5 秒，但 g(50)需要的時間是 25 秒，則參數變大 5 倍，導致 g(𝑥)的執行時間成長 5 倍，那麼參數的成長會導致函式執行時間成線性成長，我們就說，g(x)的時間複雜度是 𝑂(𝑛)

3. 若調用函數 h(𝑥)， h(10)需要的時間是 5 秒，但 h (50)需要的時間也是 5 秒，則參數變大 5 倍，導致 h(𝑥)的執行時間沒有任何改變，那麼參數的成長與所需完成的時間無關，我們就說，h(x)的時間複雜度是 𝑂(1)

array 中的常見 method 相對應的時間複雜度

基本概念

• push – 𝑂(1)
• pop – 𝑂(1)
• shift – 𝑂(𝑛)
• unshift – 𝑂(𝑛)

例外!!每個瀏覽器的 JavaScript 引擎內部對於陣列的實現方法略有差異。對於不同大小的陣列，可能會採用其他更好的資料結構，例如 double-linked list, binary search tree (BST)等等，來增強表現，因此速度可能比上面列出的速度快

補充 :Big O Notation 正式定義 Formal Definition

(Ǝc ∈ R)s.t.0 ≤ f(x) ≤ cg(x) is true
for all x ≥ n0

直觀上來說，當 x 不斷成長時， f(x)的成長速度不會超過 g(x)的某個常數倍

f(x) = 3x^2 + 7x + 8 = O(x^2) = O(g(x))

下一篇文章來學習物件導向語法。