演算法分析

怎麼定義演算法比較好 ? 1. 執行速度快(time) 2. 占用電腦記憶體空間少(space)

ex

// 1 + 2 + ...+ n
function fun1(n) {
  let sum = 0
  for (let i=1; i<=n; i++) {
    sum += i
  }
  return sum
}

function fun2(n) {
  return (1 + n) * n /2
}

console.log(fun1(10)) // 55
console.log(fun2(10)) // 55

在 index.html 引入 <script src="./test.js"></script>

test.js 檔案，在幫兩個演算法做計時

let time1 = window.performance.now()
fun1(100000)
let time2 = window.performance.now()
console.log('fun1 takes time', (time2 - time1)/1000)
let time3 = window.performance.now()
fun2(100000)
let time4 = window.performance.now()
console.log('fun2 takes time', (time4 - time3)/1000)

• 重新整理頁面，每次計時結果都不同
• 絕大多數情況， fun2 執行時間小於 fun1
• 小結：time and space are the concerns。可以利用計時知道花多久時間，但不實際。原因：(1)不穩定：同一台電腦不同次執行得到結果不同、(2) 不同電腦的硬體設備等級不同。

What's Complexity

• when analyzing the complexity of an algorithm, we calculate the (time or space) complexity.
  如何計算時間複雜度 ?

1. Generally, every addition, subtraction, multiplication, division comparison counts as one operation. (加減乘除與比較每一個都被算做一個 operation)
2. Complexity means given an input size, how many operations do we need to perform in an algorithm ?(在寫的演算法裡，總共用到多少 operation。如果用到的 operation 越多，不論使用甚麼機器我所花費的時間就越多)
3. We use function f(n) to show the equation of complexity and input sizes.f(n) 表示它的複雜度，其中 n 表示他的 input size，這表示複雜度與 input size 是呈一個函數的關係。

ex1：幾個 Hello

A：14 個

function example(n) {
  // 迴圈從 0 跑到 5 執行 6 次，所以得到 6 個 Hello
  for (let i = 0; i < 3*n; i++) {
    console.log('Hello')
  }
  // nested for loop 外圈兩次，內圈兩次，所以總共有 4 個 Hello
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      console.log('Hello')
    }
  }
  // 最後執行 4 次 Hello
  console.log('Hello')
  console.log('Hello')
  console.log('Hello')
  console.log('Hello')
}

example(2)

如果 example(n) 最後會印出幾個 Hellos ?
答：f(n) = n^2 + 3n + 4 (次)

1. 第一個迴圈會執行 3n 次，每次都會引出一個 Hello，所以總共會印出 3n 個 Hellos
2. 第二個巢狀迴圈會執行 n^2 次，每次都會引出一個 Hello，所以總共會印出 n^2 個 Hellos
3. 最後還會再印出 4 次 Hellos

這個 f(n) = n^2 + 3n + 4 代表甚麼 ?
數學上 f(n) 與 n have quadratic relation. => 他們是呈平方關係，也就意味 n 成長一點點，f(n) 會爆炸性成長

function example(n) {
  // 迴圈從 0 跑到 5 執行 6 次，所以得到 6 個 Hello
  let counter = 0
  for (let i = 0; i < 3*n; i++) {
    counter ++
  }
  // nested for loop 外圈兩次，內圈兩次，所以總共有 4 個 Hello
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      counter++
    }
  }
  // 最後執行 4 次 Hello
  counter += 4
  return counter
}

for (let i = 2; i < 10; i++) {
  console.log(`example(${i}) will print out : ` + example(i) + ' Hellos')
}

Analysis of fun 1 and fun 2

要判斷複雜度低的第一件事，就是計算有多少 operation。

1. fun1() 的 f(n) = 3n (因為 i <= n 、 i++ 、sum += i 也要算入，所以每執行一圈，就要執行 3 次 operation，又總共要執行 n 次 forloop，故 3 * n)；數學關係為 linear
2. fun1() 的 f(n) = 3 (因為)；數學關係為 constant
3. 當 n 很小時，兩者的差異不大，然而當 n 很大時，兩者的差異很大。

Big O Notation (超重要)

為甚麼很重要 ?

1. 他是一個衡量演算法重要的工具，如果不知道他會不知道如何對演算法進行優化。
2. 面試會被問到這個演算法 Big O 的值是甚麼

甚麼是 大 O

• Big O notation is a tool that describe the limiting behavior of a function when the argument (程式裡是指 input 的意思) towards a particular value or infinity. 當 input n 的值不斷擴大/逼近無窮，f(n) 的值會走去哪裡
• Big O notation has a worst case scenario, which means it shows the general trends of complexity when the size of inputs is extremely large. 大 O 表最壞的情況打算，當 input size 趨近無窮，他會展示演算法複雜度的成長趨勢

如何計算大 O

1. constant doesn't matter => 將 constant 化成 1
2. small terms don't matter
3. logarithm base doesn't matter => 底數不重要

ｆ(n) = 3n => O(n)

f(n) = 3n^2 + 4n + 4 => O(n^2)

f(n) = log 以 2 為底 指數為 n => O(logn)

f(n) = 5 => O(1) 因為將 5 化成 1

asympotic

1. Understanding Big O in math

1. def：The function f(n) = O(g(n)) iff ∃ c, n0 st 0 <= f(n) <= c * g(n) ∀n >= n0 (c * g(n) 定義了 upper bound，所以 big O notataion defined 了一個函數他的 upper bound behavior 是甚麼)
2. big O 的值原則上會以最小的 O 值表示，這樣才能反映他的特性。儘管我們知道 O(n) = O(n^2)
3. ex：

2. Understanding Big Ω in math

1. def：The function f(n) = Ω(g(n)) iff ∃ real number c, n0 st f(n) >= c * g(n) >= 0 ∀n >= n0 (c * g(n) 定義了 lower bound，所以 big Ω notataion defined 了一個函數他的 lower bound behavior 是甚麼)
2. Big Ω 表示演算法最低限度的複雜度是甚麼，會介意 Big Ω 是因為演算法無論怎麼改進，總會有最低限度的臨界值，使的這個函數沒辦法變得更好
3. Big Ω 的值原則上會以最大的 Ω 值表示，這樣才能反映他的特性。儘管我們知道 Ω(n) = Ω(log(n))
4. ex1：insertion sort，O(n^2) and Ω(n)，無論如何讓他變得更好，他最少時間複雜度就是 Ω(n)
5. ex2：

3. Understanding Big Θ in math

1. def：The function f(n) = Θ(g(n)) iff ∃ positive real number c1, c2, n0 st 0 <= c1 g(n) <= f(n) <= c2 g(n) ( Big Θ 定義 average boung )
2. ex

小結

Big O in Arrays and Objects

1. analysis of arrays and objects：處理資料方式包含 insertion / removal / searching / access
2. js 原生 function 被寫成時就有自己的 Big O，我們要先認識他們的 Big O 才會避免之後學習演算法、資料結構發生一些常犯的錯誤

Object

• insertion : O(1) => 不管物件多麼龐大，幫他加入新的資料所需的時間都一樣
• removal : O(1)
• searching : O(n) => 要找尋物件裡面有沒有某個 property，他會從第一個 property 一路往下找到最後一個，如果沒有找到就會告知沒有，若有找到就會馬上通知並停止尋找
• accessing : O(1) => 因為 hash table (快速一次性地找到資料且占用記憶體也不大)，所以 hugeObj.age 的時間與 tinyObj.age 相同

Array

• insertion : push O(1) / unshift O(n)

1. push (加在 array 的最後面)：因為只要在 array 最後面再加一格，所以是 O(1)
2. unshift (加在 array 的最前面)：unshift 後不僅 array 的總長度改變，新增加的那格的 index number 是 0，舊 array index number 是 0 的變成 1，對於陣列每個元素都要改變 index number，所以他的時間複雜度會是 O(n)

• removal : pop O(1) / shift O(n)
• searching : O(n) => 要找尋陣列裡面有沒有某個 element，他會從第一個 element 一路往下找到最後一個，如果沒有找到就會告知沒有，若有找到就會馬上通知並停止尋找
• accessing : O(1) => 因為 hash table (快速一次性地找到資料且占用記憶體也不大)，所以 hugeArr[999] 的時間與 tinyArr[9] 相同

ex1

他的 big O 是多少 ?

let n = 5
let arr = [1, 3, 5, 7, 9]
for (let i=0 ; i<n; i++) {
  arr.push(10)
}

console.log(arr) // [   1,  3,  5,  7,  9,  10, 10, 10, 10, 10 ]

答 = O(n)

ex2

他的 big O 是多少 ?

let n = 5
let arr = [1, 3, 5, 7, 9]
for (let i=0 ; i<n; i++) { // addition opertion n times 
  arr.unshift(10) // O(n)
}

console.log(arr) // [10, 10, 10, 10, 10 1, 3, 5, 7, 9]

答 = O(n^2)

小結

js Array 與 Object 都使用 hash table 所以 accessing 資料所花的時間是一樣的，不論物件或陣列多麼龐大。