# Lecture 4
###### tags: `Data Structure` `NYCU`

## Reference
[Lec04 資料結構 第三週課程](https://youtu.be/x72xBomc-XE)

## Note
### Array
用array表達一個多項式 $\to\$ e.g.:
$$
A(X)=3X^{20}+2X^{5}+4\\
B(X)=X^{4}+10X^{3}+1
$$

#### Type 1
多項式的係數就是Array中存放的element，而指數代表Array的index
* 缺點：
如下圖的$A(X)$，如果有一個sparse的array，這樣開的空間就只會有兩個index有存放數值，其他就會被浪費掉

#### Type 2
> 老師表示回家自己看書

#### Type 3
用一個global array存放所有的多項式，以上圖為例，global array存放$A(X)$和$B(X)$，存放index和相對應的coefficient
:::info
How to implement? Refer to original video at timestamp `5:30`
:::
:::danger
如果Global Array滿了怎麼辦?最簡單的作法是看前面有無可回收的多項式(寫在Descrutor)
:::

---
### Matrix
最簡單的就是直接declare一個2-dim的陣列，存放矩陣的element，缺點也和上面提到的sparse array一樣會有sparse matrix，如果太多index沒有存放東西，就會很浪費

#### Sparse Matrix Solution
直接紀錄該位置不是零的那些index的row和column就結束了(我也有想到)，排序是先看row再看column(1-dim的array)
e.g. 
:::info
如何implement transportation?最簡單的做法就是row和column互換，再做排序(一樣是先依照row再看column)
:::