# 資料結構&演算法 1. 時間複雜度 (上篇)

###### tags: `資料結構&演算法` `TimeComplexity`

## 關於時間複雜度本篇將討論以下幾個項目
:::info
### 1. 什麼是時間複雜度？
### 2. 什麼是大 O 符號(Big O notation)表示法？
### 3. O(1)
### 4. O(log n)
### 5. O(n)
### 6. O(n*log n)
### 7. O(n²)
### 8. 時間複雜度排序
:::

---
## 測試環境：
> OS：Windows 10
> IDE：Visual Studio 2019

---
## 1. 什麼是時間複雜度？
以下是 [Wikipedia](https://zh.wikipedia.org/zh-tw/%E6%97%B6%E9%97%B4%E5%A4%8D%E6%9D%82%E5%BA%A6) 對於「時間複雜度(Time complexity)」的介紹：
>在電腦科學中，演算法的時間複雜度（Time complexity）是一個函式，它定性描述該演算法的執行時間。 這是一個代表演算法輸入值的字串的長度的函式。 時間複雜度常用大 O 符號表述，不包括這個函式的低階項和首項係數。 使用這種方式時，時間複雜度可被稱為是漸近的，亦即考察輸入值大小趨近無窮時的情況。

### 簡單來說，就是提供一個能快速判斷程式執行所需單位時間的依據

---
## 2. 什麼是大 O 符號(Big O notation)表示法？
### 關於 大 O 符號可參考 [Wikipedia](https://zh.wikipedia.org/wiki/%E5%A4%A7O%E7%AC%A6%E5%8F%B7) 的介紹，又稱作「漸進時間複雜度(asymptotic time complexity)」，表示方式如下

// 程式執行的時間 = O (程式執行次數的總和)
// n：數據規模大小
// O：表示程式執行時間 T(n) 與 f(n) 成正比

T(n) = O(f(n))

### 判斷重點：
> ### 1. 僅關注執行次數最多的部分
> ### 2. 以量級最大的為主
> ### 3. 若有嵌套(巢狀迴圈)則為內層複雜度*外層複雜度
> ### 4. 常數係數可省略
#### 範例 1：


僅關注執行次數最多的部分→只看第二段，故時間複雜度為：

O(100)

#### 範例 2：


以量級最大的為主，第一段次數為已知常數→只看第二段，故時間複雜度為：

O(n)

#### 範例 3：


內層複雜度*外層複雜度，f(m)*f(n)，故時間複雜度為：

O(m*n)

#### 範例 4：


常數係數可省略，故第一段 (O(2*n)) & 第二段 (O(f(2)*f(n))) 時間複雜度皆為：

O(n)

---
## 3. O(1)
### 常數時間(Constant time)
### O(1) 並不是指執行 1 行程式碼而是執行次數，就算上萬行的程式，只執行一次，時間複雜度就是 O(1)

#### 範例：


上圖時間複雜度：

O(1)

---
## 4. O(log n)
### 對數時間(Sub-linear time)
#### 範例：


上圖中的 while 迴圈執行次數並非 n，而是在迴圈執行第 x 次時 i ≥ n

// 將迴圈執行第一次至第 x 次的 i 列出來：

2⁰, 2¹, 2², 2³, 2⁴, … , 2^x

i = 2^x 時 i > n

// 2^x > n，表示在執行第 (x + 1) 次時 i 值大於變數 n 迴圈結束

執行次數 x = log(2, n)

在轉換 log 的底時變量為常數，前面說過「常數係數可省略」，故在時間複雜度不論 log 的底是多少此時的時間複雜度皆為：

O(log n)

---
## 5. O(n)
### 線性時間(Linear time)
#### 範例：


上圖第一段 & 第二段時間複雜度分別為：

1. O(n)
2. O(m)

同時看第一段&第二段呢？

依據準則「僅關注執行次數最多的部分」，但在此我們無法評估出 m & n 哪個循環次數較多，故時間複雜度應表示為：

O(f(m) + g(n))

---
## 6. O(n*log n)
### 線性乘對數時間
#### 範例：


依據準則「若有嵌套(巢狀迴圈)則為內層複雜度 * 外層複雜度」，得到時間複雜度：

// 內部 while 迴圈執行次數 log n * 外部 for 迴圈執行次數 n

O(n*log n)

---
## 7. O(n²)
### 平方時間(Quadratic time)
#### 範例：


依據準則「若有嵌套(巢狀迴圈)則為內層複雜度*外層複雜度」，得到時間複雜度：

// 內部 for 迴圈執行次數 n * 外部 for 迴圈執行次數 n

O(n²)

---
## 8. 時間複雜度排序
### 時間複雜度(高→低)依序為：

O(2^n) > O(n²) > O(n*log n) > O(n) > O(log n) > O(1)

> Y 軸：程式執行時間 T(n)
> X 軸：數據規模大小 n


---
## 總結
### 本篇介紹了大 O 表示法與 5 種常遇到的時間複雜度情況，分析時間複雜度大多時候並不困難，相信就算是新手在看完本篇後在多數情況下也能分析出自己程式的時間複雜度了。

### 儘管本篇介紹並不完整，但目的在於讓新手快速理解時間複雜度的概念，若後續有更進一步的需求，也能以此作為基礎來探索更深入的知識。

---
### 參考資料
1. [Wikipedia](https://zh.wikipedia.org/zh-tw/%E6%97%B6%E9%97%B4%E5%A4%8D%E6%9D%82%E5%BA%A6)
---

## 新手上路，若有錯誤還請告知，謝謝