---
# System prepended metadata

title: Lecture 3

---

# Lecture 3

## Reference

[Lec03 資料結構 第二週課程](https://youtu.be/hPIBv0kO-Zc)

## Notes

### Time complexity analysis (cont.) (05:25)

- Some rules
    1. 程式中有兩個部分，複雜度分別是$f(N), g(N)$
        1. 若是循序的程式$T_1(N) + T_2(N)$，則複雜度取最大值
        2. 若是$T_1(N)$會呼叫$T_2(N)$，則複雜度相乘
    2. 如果$T_1(N)$是$k$次的多項式，則$T(N)=\Theta(N^k)$
    3. $(log(N))^k = O(N)$
        
        $$
        \because log(m) < m, \forall m > 0
        \\
        \therefore log(N^{1/k}) < N^{1/k}
        \\
        \rightarrow \frac{1}{k} log(N) < N^{1/k}
        \\
        \rightarrow log(N) < kN^{1/k}
        \\
        \Rightarrow log^k(N) < k^kN
        $$
        

![](https://hackmd.io/_uploads/rJ2EIerV3.png)

### Running time calculations (09:17)

- Examples

![](https://hackmd.io/_uploads/HkVHLeSV2.png)

![](https://hackmd.io/_uploads/rJASLxrV2.png)

![](https://hackmd.io/_uploads/SkGIUlrV2.png)

- If-else判斷一樣找最大值 (bottleneck)

![](https://hackmd.io/_uploads/HyaP8lB43.png)

- Recursive function
    - 可參考離散數學中怎麼解決這個問題

![](https://hackmd.io/_uploads/B1x_IxrEh.png)

- Recursive function (Fibonocci series)

![](https://hackmd.io/_uploads/S1XdUxS4h.png)

- 常見的時間複雜度
    - 常數
    - 對數
    - 線性
    - 線性乘以對數
    - 多項式
    - 指數

![](https://hackmd.io/_uploads/r1wFUgH4h.png)

### Summary of introduction (21:18)

- What’s data structure & algorithm
- Space / Time complexity

### Arrays (22:54)

- Definition :
    - A set of index and value
- 在記憶體中是連續存放的
- index像是門牌號碼一樣，array[index]代表的是取值

![](https://hackmd.io/_uploads/ryt1veSEn.png)

- 存放不同資料型態的array
    - 第一個存的是int
    - 第二個存的是int pointer

![](https://hackmd.io/_uploads/HJ6kDeSVh.png)

- 比較 int* list1 跟 int list2[5]
    - 相同點：list1 跟 list2都是pointer，注意list2這個pointer是list2這個陣列的第一個位置，list2[0]才是取這個陣列的第一個值
    - 相異點：list2預先保留了五個位置給陣列用，list1只有保留一個
    - 若list2代表這個陣列的第一個位置，可以用星號(*)來取值
    - list2 + i代表第 i 個位置，等同於&list2[i]，(&)是取位置的意思
    - 因此，*(list2 + i)的功能就等同於list2[i]

### Structure (41:12)

- 自訂義data type

```c
sturct {
	char name[10];
	int age;
	float salary;
} person;

strcpy(person.name, "James");
person.age = 10;
person.salary = 35000;

// Declaration by type define, which also determines the alias of the structure
typedef struct human_being{
	char name[10];
	int age;
	float salary;
}

typedef struct{
	char name[10];
	int age;
	float salary;
} human_being;

human_being person1, person2
```

- Unions被跳過了
- Self-Referential Structures : 有指向自己的pointer的structure

```c
typedef struct list {
	char data;
	list* link;
}
```

### Polynomial (48:41)

- 多項式可以用array來存degree及係數，array的index代表的是多項式的次方，index裡對應的值就是那個次方的係數。
    - E.g., poly[0] = 3, poly[5] = 2 → $2x^5 + 3$

- 多項式加法
    - while : 判斷a和b兩個多項式裡面還有沒有元素
        - switch compare : 比較兩個多項式的領導係數的次方
            - case -1 : b比較大，複製值跟次方到d裡面，然後從b裡面刪除這個元素
            - case 0 : 兩者一樣大，先加起來再複製，但如果係數總和剛好是0就不用複製了
            - case 1 : a比較大，複製值跟次方到d裡面，然後從a裡面刪除這個元素
    - 其中一個多項式沒有值之後，把另外一個多項式的元素複製到d裡面

![](https://hackmd.io/_uploads/rJFbDlH4n.png)

- 其他表示方法 : 用一個array表示數個多項式
    - coef存多項式的係數
    - exp存對應的次方
    - A, B只存他們在global array中的index起迄點

![](https://hackmd.io/_uploads/S1n-DxHVn.png)

- 實作
    - friend表示這個class可以存取自己的private member
    - static表示每個Polynomial物件都會共用同一組termArray和free
    - 空間需求 : 在多項式是稀疏的情況下，大約是第一種方法的兩倍，因為要同時存放多項式的次方及係數，第一種方法只要存係數就好

![](https://hackmd.io/_uploads/rkgzDlSNh.png)

- 方法與前者差不多，一樣要traverse兩個多項式
    - 時間複雜度 : $O(n+m)$ where $n, m$ is the number of nonzeros in polynomial $A, B$

![](https://hackmd.io/_uploads/rkEMveBV3.png)