# 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
$$


### Running time calculations (09:17)

- Examples




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


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


- Recursive function (Fibonocci series)


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


### 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]代表的是取值


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


- 比較 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

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

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裡面


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


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


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