# 資料結構與演算法 Using Python

## 目錄
> :::spoiler 清單
> [TOC]
> :::
---

## About Data Structure
> 在資料結構中，常以抽象概念定義名詞，不依賴某種程式語言已有的結構特性，如array是個有序容器，起始index為0，同個array中只存放相同type的item，然而每個程式語言實作array後的特性未必相同

## Analysis of Algorithm

### Running Time
> 執行時間增長幅度通常取決於輸入大小，由於平均執行時間難以估計，所以通常**以最壞的情況評估**
### Experimental Studies
> 以程式實現演算法，以不同的輸入規模測試並記錄時間(如下)，最後畫成圖表

from time import time
start_time = time()
'''
# run algorithm
'''
end_time = time()
elapsed = end_time - start_time

> 若採實驗的方式，需要確保硬體跟執行環境的統一，以及精準不受其他效能干擾因素的環境

> Big-O (O) 代表worst case
> Theta (θ) 代表average case
> Omega (Ω) 代表best case
### Theoretical Analysis
- 使用高階的描述取代實驗
- 輸入測資的大小定義為 n
- 考慮所有可能的測資
- 使用獨立的硬體跟軟體環境，來評估一個演算法的速度
### Pseudocode (虛擬碼、偽代碼)
- 演算法的高階描述
- 比英文敘述更有條理
- 不如程式碼詳細
- 可能會有被忽略的程式設計問題
### Pseudocode Details
#### Control flow
- if...then...[else...]
- while...do...
- repeat...until...
- for...do...
- Indentation replaces braces (以縮排取代大括號)
- Method declaration
- Method call
- Returnn value
- Expressions
### Important Functions
| Name | Time Complexity |
|:---:|:---:|
| Constant | 1 |
| Logarithmic | log(n) |
| Linear | n |
| N-Log-N | nlog(n) |
| Quadratic | n^2 |
| Cubic | n^3 |
| Exponential | 2^n |
| Factorial | n! |


### Primitive Operations (演算法的基本操作)
- 基本計算執行
- 可在虛擬碼中辨別
- 不依賴程式語言
- 不需要過於詳細的定義
- 假設某個操作需要的時間是固定的
> e.g, 評估表達式(即計算值)、將變數賦予值(即assignment)、取得陣列中的某個索引值、呼叫function/method、回傳值(return)

### Counting Primitive Operatioins
> 透過檢視pseudocode，計算原始操作的最大值作為輸入大小的函數

> op：operation，即1個操作時間
> n ops：n operations，即n個操作時間
>
> Line 1：2 ops (定義+取值)
> Line 3：2 ops (取值+賦值)
> Line 4：2n ops ((向data取值+賦值給val)*迴圈n次)
> Line 5：2n ops (取biggest值，判斷val>biggest狀態)
> Line 6：0~n ops (受Line 5判斷，有可能完全跑不到(0)，或n次迴圈都跑到(n))
> Line 7：1 ops (回傳)
>
> 將以上加總：
> best case：4n+5 = 4n+c ≈ 4n
> worst case：5n+5 = 5n+c ≈ 5n
> 由於n很大，所以較少的+1、+2...是可以忽略的
### Growth Rate of Running Time (執行時間增長率)
- 改變軟體環境或硬體設備
- T(n)的線性時間增長率是find_max的固有屬性
### Constant Factors
- 增長率不受常數或低階項影響
> 例如 $10^{2}n + 10^5$ 為linear，而 $10^5n^2 + 10^8n$為$n^2$
### Big-Oh Notation
> 給定一個函數f(n)跟g(n)，我們稱作f(n)是O(g(n)) (讀作Big-O g(n))

> e.g,
> 2n + 10 is O(n)
> 2n + 10 <= cn
> (c-2)n >= 10
> n >= 10/(c-2)
> 得到c = 3, n0 = 10
### Big-Oh Example
- $7n-2$
> c = 7, n0 = 1
- $3n^3+20n^2+5$
> c = 28, n0 = 1
- $3 log n + 5$
> c = 8, n0 = 2
### Big-Oh and Grow Rate
- Big-O符號界定了function的增長率上限
- 「f(n) is O(g(n))」表示f(n) <= g(n)的增長率
<img src="https://i.imgur.com/VCjQ5n0.png" width="50%">
### Big-Oh Rules
- 去掉低階項與常數
> 若f(n)是d次多項式，則f(n)是O($n^d$)
- 使用盡可能小的函數
> 2n 為O(n)，而不是O($n^2$)
- 使用最簡單的表達式
> 3n+5 為O(n)，而不是O(3n)
### Asymptotic Algorithm Analysis (漸進演算法分析)
- worst case由輸入大小

### Computing Prefix Averages

### Prefix Averages

### Review Math Define & Big-Oh

## Maps/Dictionaries

## Array

> Using python (少用)
> arr1 = array((Data Type), list)

<img src="https://i.imgur.com/mWLUfZY.png" width="75%">

### 特性
- 有序，連續
- 起始為0
- 儲存的內容型別一致，稱作element或item
### Insertion (插入元素)
> 從中間插入element時，worst case為O(n)


### Removeal (移除元素)
> 刪除任意位置item時，worst case為O(n)


### Add/Append (添加元素)
> 與Insert的差別在於，添加的位置在array的最後，因此不會需要搬移其他items位置
> worst case為O(1)

### Comparison of the Strategies (策略比較)

#### Incremental Strategy Analysis (增量策略分析)
>

#### Doubling Strategy Analysis

### Python Sample

## Queues
> FIFO
### 主要函數
- enqueue()
>
- dequeue()
### 輔助函數
- first()
>
- len()
>
- is_empty()
>

> example

<img src="https://i.imgur.com/SLxTOfO.png" width="80%">

## Queue的應用
### 直接
- Waiting lists, bureaucracy
- Access to shared resources (e.g., printer)
- Multiprogramming
### 間接
- Auxiliary data structure for algorithms
- Component of other data structures

### 以Array實作Queue
> f為front
> r為end

> 當不斷dequeue時，前面閒置的空間過多，當r已經用完後面空間時，會將指標指到前面的空間形成環狀

## Stacks
> LIFO

### 主要函數
- push()
>
- pop()
### 輔助函數
- top()
>
- len()
>
- is_empty()
>

> example

<img src="https://i.imgur.com/ZZW33kz.png" width="80%">

## Stack的應用
### 直接
- Page-visited history in a Web browser
- Undo sequence in a text editor
- Chain of method calls in a language that
supports recursion
### 間接
- Auxiliary data structure for algorithms
- Component of other data structures

### 以Array實作Stack
> t為top


### 配對檢測
#### Parentheses Matching (括號檢測)
- Algorithm
- Python
- HTML Tag

### 計算邏輯
#### Evaluating Arithmetic Expressions (算術表達式)
> `+` `-` `*` `/`等運算規則的優先順序判斷
> e.g, 14 – 3 * 2 + 7 = (14 – (3 * 2) ) + 7

## Linked Lists (鏈結串列)

### Singly Linked List (單向鏈結串列)

## Recursion

## Trees

## Graphs

## Searching

## Sorting

## Text Processing

## Dynamic Programming

## Artificial Intelligence Algorithms

---
###### tags: `Data Structure and Algorithms` `Python`