# Lecture 2
###### tags: `Data Structure` `NYCU`
[TOC]

## Reference
[Lec02 資料結構 第二週課程](https://youtu.be/0J2eLvkuF8k)
## Note
### Recursive Algorithms
#### Type
* Direct Recursion: 簡單來說就是自己呼叫自己
* Indirect Recursion: A calls B $\to$ B calls itself

---
#### Boundary Condition
Recursive algorithm是會停止的，如果他能夠寫出一個完整的通式或過程，就代表有上限，當達到這個上限時就會停止
:::spoiler Example
:::

---
#### Application of Recursive Function
* Permutation
Detailed description can browse the [original video](https://youtu.be/0J2eLvkuF8k)
如果不用Recursive解決Permutation的問題，可以考慮用For-Loop但是要考慮重複出現的問題
:::spoiler Example

在這個例子中boundary condition就是只剩下一個字元需要做排列的時候
:::
* Binary Search
:::spoiler Example
:::
### Performance Analysis
如何判斷一個演算法的好壞

#### Complexity Theory
1. <font color="FF0000">Space Complexity</font>font>: amount of memory $\to$ $S(P)=c+S_p(I)$ where $c$ is a constant(有多少固定的空間被用掉了，e.g. instruction, simple variables, constants) and $S_p$ is depends on characteristics of instance $I$
2. <font color="FF0000">Time Complexity</font>font>: amount of computer time $\to$ $T(P)=c+T_p(I)$ where $c$ is a constant(有多少固定的時間被用掉了，e.g. compile time) and $S_p$ is program execution depends on characteristics of instance $I$
:::info
Run(Execution) Time $T_p(n)=c_aADD(n)+c_sSUB(n)+c_lLDA(n)+c_{st}STA(n)$ where $LDA$ is the time by loading something and $STA$ is the time by storing something
:::

#### How to know how many step in one program? - Purpose: Compute Time Complexity
1. Use Count Variable
:::spoiler Example
:::
2. Use Tabular Method
:::spoiler Example
:::
:::warning



:::