---
tags: 讀書會
---
# 資料結構與演算法搭配 leetcode 1 - Day3

## 前情提要

本節講的東西以讀書會分享為主，用詞可能會有錯誤，如果有錯誤都歡迎大聲提出，我會大聲的感謝你。

今天為了課程完整度所以省略了 leetcode 的部分 >< ，先說一下。

## 摘要

演算法超簡介

為啥以及如何判別演算法好壞？

Complexity(複雜度) 介紹

時間複雜度與空間複雜度？

Big O Notation 介紹

Big O Notation 的三個規則

怎麼以 Big O Notation 的值來判斷演算法的好壞

Big O Notation 的規則由來

---

今天不會探討數學原理，這只是分享我對於演算法跟 big O 的理解，如果有講錯的地方請跟我說拜託。

---

## 什麼是演算法？
我們很常聽到：演算法帶我來的之類的

- 冗長的定義：
由有限步驟所構成的集合，可以用於解決某一個特定的問題。

- 簡單來說
演算法就是一步一步用來解決問題的程序。
輸入 + 演算法 = 輸出
橘子 打成汁 = 橘子汁
其中打成汁的過程就是演算法，要罵用手榨汁、要罵用果汁機榨汁。
這兩種方式用手榨汁、要罵用果汁機榨汁都是演算法，都可以將橘子變成橘子汁。

- 生活中用到的演算法
- google map 找到最短的路徑，如此多的排列組合，找出最短的路徑
- Youtube 的推薦影片，在數十億之影片中找到符合你喜好的影片
- Excel 排列報表之類的，數字很多時，如何排列
- FB IG 的各種操作，推薦好友或是推文給你

## 比較演算法
Comparing Algorithms 演算法分析

為什麼我們要比較演算法呢？

如果現在有相同的演算法可以完成同一個任務，那位什麼要比較呢？結果不是都一樣嗎？

//1 + 2 + 3 + ... + n = sum

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
}

現在你看的出來哪一個演算法比較好嗎？

可以比較優劣的標準 => 速度、記憶體資源

我們來印出他們的執行時間，可以知道:

在參數等於 `(100)` 的時候，兩者執行速度差不多，因瀏覽器而異

---
但是在參數等於 `(10000000)` 的時候，很明顯的 `fun2()` 的速度是快於 `fun1()`

---

所以這個例子我們可以知道 `fun2()` 是比`fun1()` 還好的演算法
但是比較演算法都要這樣用瀏覽器跑、計算時間比較嗎？ NO！
接下來要說說比較演算法的方法

### 比較演算法 - 比較的方法 => 比較演算法的複雜度 Complexity

比較演算法無非就是在比較時間或是空間，時間複雜度跟空間複雜度

更少的時空間占用 === 更好的演算法

- BUT 在執行環境上面計時不是一個好比較方式，
- 每次的執行結果都不一樣
- 每一個執行環境 (runtime) 執行結果不一定一樣
- 同上，不同人的執行環境結果會有差，像在 Mia 的電腦跟 安潔 的 M1 上執行，速度一定是天差地別

比較好的比較方式 => 比較演算法的複雜度 Complexity

那接下來我們就來講複雜度是什麼？

## 複雜度 Complexity

1. 複雜度分成兩種：時間複雜度，空間複雜度(我們買的課程以時間複雜度為主)

2. 每一個加減乘除，比大小等等都可以算做一個 operation (操作)，多少 operation 複雜度就有多少
- `+` `-` `*` `/` `>` `<` `=`
3. 在所寫的演算法裡面，operations 越多那不管用甚麼機器時間都會比較多，相對來說 operations 少的話，不管甚麼機器去執行，花的時間會比較少。簡單的說就是用 operations 來看複雜度的話就不會受到執行環境的影響。

4. 通常我們會用一個 `f(n)` 去表示 Complexity 跟 input sizes 的關係
`f(n)` 表示 Complexity 裡面的 n 表示 input size

以下這個演算法，請問會輸出幾個 `Hi`

function example(n) {
  for (let i = 0; i < 2 * n; i++) {
    console.log("Hi");
  }

  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
    console.log("Hi");
    }
  }

  console.log("Hi");
  console.log("Hi");
  console.log("Hi");
}

example(2);

這邊可以知道當參數為 `2` 的時候會輸出 11 個 `Hi`

這邊我們可以說 example(n) 他的 Complexity(複雜度) = `n² + 2n + 3`
依照上面第 `4.` 點的話可以這樣表示 `f(n) = n² + 2n + 3`

以上這個就是 複雜度的大致算法

那下面我們就來看兩個演算法的複雜度如何比較

## 來比較複雜度吧

以最初的兩個演算法為範例

//1 + 2 + 3 + ... + n = sum

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
}

以這個例子， fun1 在執行時，裡面有個 for loop，裡面有很多 operations (操作)：
- 每次跑一圈判斷 `i <= n` 算一個 operations
- 跑一個`i++` 算一個 operations
- 執行`sum += i` 算一個 operations

每跑一次 for loop 就要跑三個 operations
那總共要跑幾次呢？ n 次
所以它的複雜度就是 `f(n) = 3n`
這個就是 `fun1()` 的 Complexity 公式

fun2 的話，每跑一次就執行三步，operations 就是 3，所以複雜度就是` f(n) = 3`
Complexity 公式就是 `f(n) = 3`

fun1 f(n) = 3n
是線性關係

fun2 f(n) = 3
是常數關係

畫圖時間
n 越大 複雜度越大

這邊可以知道在 n 很小的時候， 他們之間的複雜度不會差太多，但是只要值一大，複雜度也會大很多

fun1 的複雜度為
f(n) = 3n

fun2 的複雜度為
f(n) = 3

---
這邊是不是對如何比較複雜度有點概念了，但是該不會每比較一次都要話一次圖吧？

當然不會，接下來我們就來看看 Big O Notation 跟複雜度之間的關係

## Big O Notation 你是山曉 🌄

不管學甚麼演算法、資料結構都會使用到 big O 這個概念

Big O Notation 是做為一個「工具」用來當作衡量演算法

(聽說面試會問，轉 senior 可能比較常碰到？

>我的解釋是「用來轉換、衡量複雜度的一個工具，演算法的優劣都是以 Big O Notation 的值為比較對象」 (僅供參考，不太準確)

### 定義

[WIKI 大O符號](https://zh.wikipedia.org/wiki/%E5%A4%A7O%E7%AC%A6%E5%8F%B7)
>WIKI 解釋：大 O 符號是用來描述一個演算法在輸入 n 個東西時，總執行時間與 n 的關係。

1. 當 input 的值不斷往上時， `f(n)` 的數字會走向哪裡。 可能會往上可能會往下，但主要是會往上，這就是 big O Notation 主要在描述的事情

2. 總是考慮最壞情況 (記我就好)
big O Notation 會考慮最壞的情況，如果 input size 超大的話， big O Notation 的工作就是顯示複雜度的趨勢是什麼

簡單來說：考慮最壞情況，也就是 input size 如果超大的話成長趨勢為何

那接下來來學習如何計算 big O 的值吧～

### Big O Notation 的三個規則

要計算 big O 的值的話，有三個規則是要先知道的：

- 1. constant doesn't matter
- 2. small terms don't matter
- 3. logarithm base doesn't matter

下面來一一解釋：

#### 1. constant doesn't matter

const 常數 < = > variable 變數

常數就是 `f(n) = 3n` 的 `3`
變數就是 `f(n) = 3n` 的 `n`

意思就是常數並不重要

所以 `f(n) = 3n` 的 big O Notation 就是 `O(n)`，其中 `3n` 的 `3` 被拿走了

#### 2. small terms don't matter

以下為例

有一個演算法的複雜度 `f(n) = 3n² + 6n + 4`

`3n²` 最大，比後面的 `6n + 4` 還大，所以可以不去考慮後面

只考慮 `3n²`，`f(n) = 3n²`

再搭配第規則 `1.` 常數並不重要， `3`也可以拿掉

所以複雜度 `f(n) = 3n² + 6n + 4` 的 big O Notation 就是 `O(n²)`

>只考慮最大的值

#### 3. logarithm base doesn't matter

(logarithm 對數，就是數學中的 log)

意思就是 log 的底數不重要，可以省略

例如：
`f(n) = log₂n` ，那2 可以被忽略
`f(n) = log₂n` 的 big O Notation 就是 `O(logn)`

>就是 log 的底數可以去掉

這邊不詳述 log 呦！

那以下是個小測驗，考考你對 big O 的掌握度：

練習：

有個演算法的 complexity(複雜度)
1. 
f(n) = 2n
求 big O 的值
big O => 

2. 
f(n) = 13n^3 + 6n + 5
求 big O 的值
big O =>

3.
f(n) = 4log₂n
求 big O 的值
big O =>

4.
有個演算法的 complexity(複雜度)
f(n) = 5
求 big O 的值
big O =>


// 答案


1. big O => O(n)

2. big O => O(n^3)

3. big O => O(logn)

4. 不是 O(5) 哦，big O => O(1)

關於第四題，因為規則 1. 上有說常數並不重要，但其實意思並不是把常數直接拿走，而是「將常數當作 1」

所以關於規則 1. 比較準確的結論應該是：

>意思其實就是不管常數多大，都把常數當作 1 ！

接下來大家都學會怎麼將複雜度轉換成 big O 了，下面來介紹各式 big O 的值孰優孰劣。

### 來比較常見的 big O 的值
順序由好排到差

好

1. O(1)	極好
2. O(logn)	極好
3. O(n)	常見的 case
4. O(nlogn)	sorting 演算法常見，這裡先知道
5. O(n^2)	極差 要想辦法變成 3. or 4.
6. O(n^3)	極差 要想辦法變成 3. or 4.

差

>總之這邊的重點就是不要有 O(n^2) 以下的 big O 出現，出現就是拉基扣


下面來帶大家稍稍微了解 big O 的規則為甚麼要這樣定
大略知道原因就好

## Understanding Big O

剛剛學過 big O Notation 的運算方式但是沒有學到為甚麼？

這裡稍微解釋為甚麼以及更了解運算概念

請轉換成 big O 並且比較以下 Complexity(複雜度)

f1(n) = 1000
f2(n) = n
f3(n) = n +1500
f4(n) = n^2


big O：

O(1)
O(n)
O(n)
O(n^2)

在這裡可以發現 `f2(n)` 跟 `f3(n)` 的 big O 都是 `O(n)`
那你可能會想，為什麼 `f3(n)` 的 1500 可以被刪掉？感覺執行 1500 次也不是個小數目ㄋ一ㄝ？

>因為 big O 所考慮的是最糟糕的情況！

用表格解釋，在 n 非常大時，1500 只是不足一提的一根毛
在途中也會看見 n^2 的時間複雜度已經是逆天的高

回到 big O 的定義
big O 考慮的是 input size 極大，或是要執行很多次的時候
所以可以把常數丟掉

## 今日分享小結

不會探討到數學原理，這只是分享我對於演算法跟 big O 的理解

知道什麼是演算法

知道演算法優劣為何重要

知道比較演算法比較有時間複雜度跟空間複雜度可以比

知道用時間複雜度來比較演算法並不是用「秒」 來比，而是比較 operations (操作)次數

知道 Complexity(複雜度) 跟 Big O Notation 之間的關係

知道 Big O Notation 的三個規則

知道怎麼以 Big O Notation 的值來判斷演算法的好壞

大概知道 Big O Notation 的規則由來

再說一次這次是讀書會的分享，關於 big O 的解釋請在到處參考ㄛ(怕誤人子弟。

## 謝謝大家

恭喜各位接受灌輸


## 除了課程的參考資料

延伸閱讀關鍵字：Big Omega and Big Theta (我看不懂

#### 影片：

你各位的課程：
[CS101] 初心者的計概與 coding 火球術 7-2：怎麼衡量演算法的好壞
可以回去聽青春年華的 Huli

裡面也有提到
有關於時間複雜度，空間複雜度 的 空間換取時間、時間換取空間 的基本概念。

可以看演算法在業界的哪會用到：
[學習資料結構、演算法在工作上真的有用嗎? 實際工作經歷不藏私! | 二元樹 | 雜湊 | 計算機概論 | 工程師 Nic](https://www.youtube.com/watch?v=-Y_4rOXeqHQ&ab_channel=%E5%9C%A8%E5%9C%B0%E4%B8%8A%E6%BB%BE%E7%9A%84%E5%B7%A5%E7%A8%8B%E5%B8%ABNic)

演算法簡介：
[【圖解演算法教學】一次搞懂「資料結構」與「演算法」到底是什麼？ 入門|介紹|教學|LeetCode|資料結構](https://www.youtube.com/watch?v=WNN2-jw1EVU&ab_channel=%E5%9C%96%E8%A7%A3%E7%A8%8B%E5%BC%8F%E6%95%99%E5%AD%B8SamTsai)

#### 文章：

演算法簡介：
[初學者學演算法｜談什麼是演算法和時間複雜度](https://medium.com/appworks-school/%E5%88%9D%E5%AD%B8%E8%80%85%E5%AD%B8%E6%BC%94%E7%AE%97%E6%B3%95-%E8%AB%87%E4%BB%80%E9%BA%BC%E6%98%AF%E6%BC%94%E7%AE%97%E6%B3%95%E5%92%8C%E6%99%82%E9%96%93%E8%A4%87%E9%9B%9C%E5%BA%A6-b1f6908e4b80)

[評量演算法好壞的 Big O](https://ithelp.ithome.com.tw/articles/10213615)