---
# System prepended metadata

title: Data Structure
tags: [MyNTUST]

---

# Data Structure

###### tags: `MyNTUST`

{%hackmd  @CA-Lee/MyNTUST_banner %}

[TOC]

Program, Algorithm & Recursion
===

Datatype
---

- char
    - store in ASCII code
- int
- float
- double

Program
---

- a good program is
    - correct
    - easy to read
    - easy to debug
    - easy to modify

Algorithm
---

- definition
    - 解決問題的步驟
    - input
    - output
        - at least one
    - clear and unambiguous
    - finite
        - 有限步驟內可以解決問題
        - program don't need
    - effective
        - anyone can understand by pencil and paper
- algorithm vs program
    - algorithm is just paperwork
- often devide into modules (modularization)
    - easy to maintain

Function
---

- why seperate into functions
    - easy to test
    - easy to update
    - 更好分工
- recursion

Recursive
---

- Direct recursion
    - A call A in A
- indirect recursion
    - A call B, B call A
- tail recursion
    - A call A in the last line
- (often) easy to read
- but more time-comsuming
- Ackerman's function
    $$
    A(m,n) =
    \begin{cases}
        n+1, & \text{if } m=0 \\
        A(m-1,1), & \text{if } n=0 \\
        A(m-1,A(m,n-1)), & \text{otherwise}
    \end{cases}
    $$
    eg.
    $$
    \begin{align}
    A(1,2)=A(0,A(1,1))=A(0,3)=4\\
    A(1,1)=A(0,A(1,0))=A(0,2)=3\\
    A(1,0)=A(0,1)=2 \\
    A(0,1)=2
    \end{align}
    $$
    
Performance Analysis
===

Space Complexity
---

> $S(P) = c + S_p$

- fixed part
    - instructions (指令、程式碼)
    - constants (常數)
    - simple variable (一些基本的變數)
- variable part
    - recursion stack space (遞迴時佔的空間)
        - 因為要先儲存還沒執行完的資料(程式)
    - referenced variables
- 一般都針對 $S_p$ 討論

Time Complexity
---

> $T(P) = c + T_p$

- 分成 compile time 和 run (execution) time，一般討論 run time
- compile time
    - 編譯的時間，基本上是 constant
- run time
    - 程式執行所耗的時間，可能會因輸入而改變
    - measuement
        - 實際測量程式執行所耗的時間
    - analysis
        - 計算程式走了幾步 (有幾行指令)

Expressing Complexity
---

- we usually use some terminoloies, which is meaningful but inexact 

### Big-oh

> $f(n) = O(g(n))$
> (f of n is big oh of g of n)

- 程式複雜度上界
- 程式 f 輸入 n 之後執行的時間為 $f(n)$
- 找到數學式 $g(n)$ 使得 $f(n)$ 在 $n \ge n_0$ 時永遠小於等於 $g(n) \times c$ 倍
    - $f(n) \le cg(n) \text{ for all } n, n \ge n_0$
    - eg. $3n + 2 = O(n)$
        - $3n +2 \le 4n \text{ for all } n \ge 2$
        - $3n + 2 = O(n^2)$ is also correct, but not informative
- $g(n)$ should be as small as possible
- Fantastic names (~~潮爆的~~讀法)
    |          |             |
    | -------- | ----------- |
    | $O(1)$   | constant    |
    | $O(n)$   | linear      |
    | $O(n^2)$ | quadratic   |
    | $O(n^3)$ | cubic       |
    | $O(2^n)$ | exponential | 
- $O(1) < O(\log n) < O(n) < O(n \log n)$
    $< O(n^2) < O(2^n) < O(n^3) < O(n^c)$
    $< O(2^n) < O(3^n) < O(c^n) < O(n!)$
    $< O(n^n) < O(n^{c^n})$

### Omega

> $f(n) = \Omega(g(n))$
> (f of n is omega of g of n)

- 程式複雜度下界
- $n \ge n_0$ 後 $f(n)$ 必大於 $cg(n)$
    - $f(n) \ge cg(n) \text{ for all } n, n \ge n_0$
- $g(n)$ also should be as large as possible

### Theta

> $f(n) = \Theta(g(n))$
> (f of n is theta of g of n)

- $g(n)$ 同時是 $O()$ 同時也是 $\Omega()$
- 比 $O()$ 和 $\Omega()$ 更精確
- $\Theta(g(n)) = O(g(n)) = \Omega(g(n))$ 

### Little-Oh

> $f(n) = o(g(n)),\space 0 \le f(n) \lt cg(n)$

- for **all** positive constant $c$, exist some $n_0$ such $f(n) < cg(n)$ for all $n > n_0$
- e.g.
    - $2n = o(n^2)$
    - $2n^2 \neq o(n^2)$

### Little-omega

> $f(n) = \omega(g(n)),\space 0 \le cg(n) \lt f(n)$

- for **all** positive constant $c$, exist some $n_0$ such $cg(n) < f(n)$ for all $n > n_0$
- e.g.
    - $\frac{1}{2}n^2 = \omega(n)$
    - $\frac{1}{2}n^2 \neq \omega(n^2)$


### Implications

- $f(n) = \Theta(g(n)) \iff g(n)=\Theta(f(n))$
- $f(n) = O(g(n)) \iff g(n) = \Omega(f(n))$
- $f(n) = o(g(n)) \iff g(n) = \omega(f(n))$


Master Method
---

> a "cookbook" for solving complexity of some recursive functions

### Theorem

- $T(n) = aT(\frac{n}{b}) + f(n)$
- $a \ge 1, b \gt 1, f(n) \text{ is a positive function}$

1. $f(n) = O(n^{\log_b a-\epsilon})$ for some constant $\epsilon > 0$
    - $T(n) = \Theta(n^{\log_b a})$
2. $f(n) = \Theta(n^{\log_b a})$
    - $T(n) = \Theta(n^{\log_b a} \log_2 n)$
3. $f(n) = \Omega(n^{\log_b a+\epsilon})$ for some constant $\epsilon > 0$, and $af(\frac{n}{b}) \le cf(n)$ for some constant $c < 1$ and $n > n_0$
    - $T(n) = \Theta(f(n))$


### examples

- e.g. $T(n) = 9T(\frac{n}{3}) + n$
    - $a=9,b=3,f(n)=n,n^{\log_ba}=n^{\log_3 9}=n^2$
    - $f(n) = n = O(n^{\log_b a-\epsilon}) = O(n^{\log_3 9-1})$
    - by case 1, $T(n) = \Theta(n^{\log_b a}) = \Theta(n^2)$
- e.g. $T(n) = T(\frac{2n}{3}) + 1$
- e.g. $T(n) = 3T(\frac{n}{4}) + n \log_2 n$

Array
===

- array is a set of pair of <index, value>
- in C/C++, index start from 0
- 通常儲存在連續的記憶體中
    - a[3] 的位址等於 a[0] 的位址 + 3 單位
- 在初始化時可以設 default value

2D array
---

- 二維，可以和數學的 matrix 對應
    - $A_{i,j} = A[i-1][j-1]$
- Row-major
    - Store in sequence $A_{1,1},A_{1,2},...,A_{1,n},A_{2,1},...,A_{2,n},...,A_{m,n}$
    - a[i][j]的位址 = A[0][0]的位址 + i*n 個單位 + j 個單位
- Column-major
    - Store in sequence $A_{1,1},A_{2,1},...,A_{m,1},A_{1,2},...,A_{m,2},...,A_{m,n}$
    - a[i][j]的位址 = A[0][0]的位址 + j*m 個單位 + i 個單位

Triangular Matrix
---

> 有約一半的值是 0，存起來很浪費空間，所以不存

- lower-triangular
    - row-major
        - $L(A_{i,j}) = l_s + [\frac{(1+(i-1)) \times (i-1)}{2} + (j-1)] \times d$
    - column-major
        - 全部減後面
        - $L(A_{i,j}) = l_s + [\frac{(1+m)\times m}{2} - \frac{(1+(m-j))(m-j)}{2} - (m-i+1)] \times d$
- upper-triangular
    - 概念同上

Stack
===

Concept
---

- ordered
    - 插入或刪除要依照規定的順序
        - 只能插入/刪除 top 的資料
- 桶子
    - stack 可以說是一個桶子
    - 插入資料
        - 往桶子裡丟，最後丟的會在最上面
    - 取出/移除資料
        - 從桶子裡拿，只能從最上面的開始拿
- LIFO
    - last in first out

Implementation
---

- push(data)
    - 放東西進去
    - 放之前程式要檢查 stack 是否已經放滿
        - else `stack overflow`
- pop()
    - 取出資料
    - 程式要檢查 stack 還有沒有資料
        - else `stack underflow`
- peek()
    - 偷看
    - 看一下 top 的資料
- use array
    - 宣告一個空間
    - 從 0 開始放，一個指標紀錄 top 位置

Stack Permutation
---

- 給一組 elements 和一個 stack
- 將 elements 依序放入 stack，但中途可以 pop
- 所以會得到新的順序
- 該順序稱為 stack-sortable permutation
- e.g. ABC
    - ACB: push (A), pop (A), push (B), push (C), pop (C), pop (B)
- Catalan number ([wiki](https://en.wikipedia.org/wiki/Catalan_number))
    - how many stack-sortable permutations
    - $$\frac{1}{n+1}C^{2n}_{n}$$

Prefix, Infix & Postfix
===

- Infix (中序表示法)
    - `運算元1` + `運算子` + `運算元2`
    - e.g. `A + B`
- Postfix (後序表示法)
    - e.g. `AB X`
    - infix to postfix
        1. 將所有括號寫出來
        2. 用運算子取代對應的右括號
        3. 移除左括號
- Prefix (前序表示法)
    - e.g. `* AB`
    - infix to prefix
        1. 將所有括號寫出來
        2. 用運算子取代對應的左括號
        3. 移除右括號

Red-Black Tree
===

> 紅黑樹

- definition
    - nodes have color red or black
    - leaf nodes doesn't store data
    - root is always black
    - leaves are always black
    - red nodes always have two black children
    - from any node to its leaf must pass same amount of black nodes
- self balanced
    - longest path $\le$ 2 $\times$ shortest path
        - 因為紅色都有兩個小孩
        - 不會連續太多黑色，因為走過的黑色要一樣多

Insertion
---

1. if one black has two children, change its color
2. if needed, do rotation
3. insert node as red
4. if needed, do rotation
5. check root is black

Red-Black Tree VS AVL Tree
---

- $O(\log n)$ for searching, insertion, deletion
- AVL tree is more rigidly balanced
- AVL tree is slower when insertion & deletion, bus faster in searching

Contributors
===

- [calee](https://calee.tw)
- [alston](https://github.com/Alston-Jan)
- [issues](https://github.com/jp05451)