---
# System prepended metadata

title: Lecture 2
tags: [NYCU, Data Structure]

---

# 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
![](https://i.imgur.com/5fDAGfc.png)
:::

---
#### Application of Recursive Function
* Permutation
    Detailed description can browse the [original video](https://youtu.be/0J2eLvkuF8k)
    如果不用Recursive解決Permutation的問題，可以考慮用For-Loop但是要考慮重複出現的問題
    :::spoiler Example
    ![](https://i.imgur.com/hGNBo0t.png)
    
    ![](https://i.imgur.com/oU1sF0H.png)
    在這個例子中boundary condition就是只剩下一個字元需要做排列的時候 
    :::
* Binary Search
    :::spoiler Example
    ![](https://i.imgur.com/vtd69dw.png)
    :::
### 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
    ![](https://i.imgur.com/XZJxX4E.png)
    :::
2. Use Tabular Method
    :::spoiler Example
    ![](https://i.imgur.com/CTnZCeI.png)
    :::
:::warning
![](https://i.imgur.com/1aDQmYq.png)

![](https://i.imgur.com/hfugetm.png)

![](https://i.imgur.com/BsBQPtj.png)

:::