JavaScript-淺談BigO的運作

    AllenLi
    Coding

    運用JavaScript來模擬時間複雜度(Time Complexity)與空間複雜度(Space Complexity)：
    通常我們衡量演算法的執行速度，會透過程式的執行步驟次數來進行比較，而比較的類型分別有時間、空間的複雜。

    - 時間複雜度 (Time Complexity)： 
(1.) 計算每一行(輪)程式將會執行的次數。
(2.) 將所有執行的次數進行加總。
(3.) 以BigO來代表時間的複雜度。
ex.
+------------------+
| Time Complexity  |
+------------------+
| 1. BigO(1)       |
| 2. BigO(log n)   |
| 3. BigO(n)       |
| 4. BigO(n log n) |
| 5. BigO(n^2)     |
| 6. BigO(2n)      |
| 7. BigO(2!)      |
+------------------+

- 空間複雜度 (Space Complexity)： 
(1.) 計算演算法執行時所佔用的記憶體空間，以下兩者的差異分別為「每次執行都會產生一樣的空間」
     、「會根據使用者輸入的input來決定記憶體的空間」。
ex.
+------------------+
| Space Complexity |
+------------------+
| 1. BigO(1)       |
| 2. BigO(n)       |
+------------------+

    運用JavaScript來模擬BigO(1)：
    此演算法代表花費的時間與資料數量沒有關係，且最有效率。

    let bigO_1 = function(a, b) {
    return a * b
}
console.log(bigO_1(1, 2)) //2

    運用JavaScript來模擬BigO(log n)：
    此演算法代表花費的時間與資料數量有弱相關性，且仍保持不錯的效率。

    let bigO_logn = function(array, key) {
  let min = 0, max = array.length - 1
  
  while (min <= max) {
    let middle = Math.floor((min + max) / 2)

    if (array[middle] > key) {
      max = array[middle - 1]
    } else if(array[middle] < key) {
      min = array[middle + 1] 
    } else {
      return middle;
    }
  }
}
console.log(bigO_logn([1,3,5,7,9,11], 5)) //index = 2

    運用JavaScript來模擬BigO(n)：
    此演算法執行所花費的時間開始受到資料數量的多寡影響。

    let bigO_n = function(n) {
  let sum = 0
  for (let i = 0; i <= n; i++) {
    sum += i
  }
  return sum;
}
console.log(bigO_n(3)) //6

    運用JavaScript來模擬BigO(n log n)：
    此演算法執行所花費的時間開始受到資料數量的多寡影響。

    function bigO_nlogn(n) {
  for (let i = 0; i < n; i++) {
    for (let j = 1; j < n; j = j * 2) {
      console.log("Hello world!")
    }
  }
}
console.log(bigO_nlogn(2)) //Hello world!
                           //Hello world!

    運用JavaScript來模擬BigO(n^2)：
    此演算法執行所花費的時間開始受到資料數量的多寡產生了劇烈的影響。

    let bigO_square = function(n) {
  let sum = 0
  for (let i = 0; i <= n; i++) {
    for (let j = 1; j <= n; j++) {
      sum += i * j
    }
  }
  return sum;
}
console.log(bigO_square(2)) //9

    運用JavaScript來模擬BigO(2n)：
    此演算法執行所花費的時間開始受到資料數量呈倍數成長，效率不佳。

    let bigO_2n = function(n) {
  let sum = 0
  for (let i = 0; i <= n; i++) {
    sum += i
  }
  for (let j = 0; j <= n; j++) {
    sum += j
  }
  return sum;
}
console.log(bigO_2n(2)) //6

    運用JavaScript來模擬BigO(n!)：
    此演算法執行所花費的時間會依照資料數量成階層式成長。

    let bigO_n_ex = function(n) {
  if (n === 1) return 1;
  return n * bigO_n_ex(n - 1);
}
console.log(bigO_n_ex(5)) //120

    Related Posts