---
# System prepended metadata

title: NTCU資料結構第一張考前複習
tags: [學業共筆]

---

## CH1 時間複雜度

### 時間複雜度
時間複雜度是用來描述一個演算法在輸入 n 個東西時，總執行時間與 n 的關係。

**時間複雜度大小順序**
```
θ(log n) < θ(n) < θ(n*log(n)) < θ(n^2) < θ(n^3) < θ(2^n) < θ(n!)
```
**時間複雜度種類**
* O (Upper Bound) 複雜度最高的情況
* Ω (Lower Bound) 複雜度最低的情況
* θ (“theta”) 同時滿足O和Ω的情況

#### **O (Upper Bound)**

可以找到一個非負的常數C，並滿足 **f(n) <= C*g(n)**

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


#### **Ω (Lower Bound)**

可以找到一個非負的常數C，並滿足 **f(n) >= C*g(n)**

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

#### **θ (“theta”)**

可以找到兩個非負的常數C1,C2，並滿足 **C1g(n) <= f(n) <= C2g(n)**
> *θ為同時滿足O和Ω的情況*

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


#### 課本例題1

判斷以下敘述是否屬實

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


#### 課本例題3

### 試證明

![](https://hackmd.io/_uploads/rkEvQ-bGT.png)

### 解答  
![](https://hackmd.io/_uploads/BJ1TmWbza.png)



---

### recursive(遞迴) && iterative(疊代)

**recursive(遞迴)**

* 指一段程式(通常為一個function)呼叫自己
 

**iterative(疊代)**

* 指一段程式擁有迴圈的結構

#### 課本例題 7

The factorial function n! has value 1 when n < 1 and value n*(n-1)! when n > 1.
Write both a recursive and an iterative C function to compute n!.

**iterative(疊代)**

```c=
double iterFact(int n) {
    if (n <= 1) return 1.0;

    double answer = 1.0;
    for (int i = 2; i <= n; i++)
        answer *= i;

    return answer;
}

```
> 時間複雜度: O(n)

**recursive(遞迴)**

```c=
double recurFact(int n) {
    if (n <= 1) return 1.0;
    return n * recurFact(n - 1);
}
```
> 時間複雜度: O(n)

#### 課本例題 8

The Fibonacci numbers are defined as: f(0) = 0, f(1) = 1, and f(i) = f(i-1)+f(i-2) for i > 1.
Write both a recursive and an iterative C function to compute f(i)

**iterative(疊代)**

```c=
int iterFib(int n) {
    if (n <= 1) return n;

    int fib1 = 0, fib2 = 1, fib;

    for (int i = 2; i <= n; i++) { // 廢波那契從 2 開始算
        fib = fib1 + fib2;
        fib1 = fib2;
        fib2 = fib;
    }

    return fib2;
}
```
> 時間複雜度: O(n)

**recursive(遞迴)**

```c=
int fibonacci(int n) {
    if (n <= 1) {
        return n;
    }
    return fibonacci(n - 1) + fibonacci(n - 2);
}
```
> 時間複雜度: O(2^n)

#### 課本例題9

Write an iterative function to compute a binomial coefficient, then transform it into an equivalent recursive function.

binomial coefficient(二項式係數)

**iterative(疊代)**

```c=
// 計算二項式係數 C(n, m)
double iterBinom(int n, int m) {
    // 特殊情況
    if (m == 0 || n == m) return 1;

    double result = 1.0;

    // 基於二項式係數的展開式直接計算每一項的乘除
    for (int i = 1; i <= m; i++) {
        result *= (n - i + 1);  // 分子部分
        result /= i;            // 分母部分
    }

    return result; // 返回計算結果
}

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

> 時間複雜度: O(n)

**recursive(遞迴)**

```c=
double recurFact(int n){ /*recursive version */
    if ((n==0) || (n==1)) return 1.0;
    return n*recurFact(n-1);
}

double recurBinom(int n, int m){ /*recursive version */
    return recurFact(n)/(recurFact(m)*recurFact(n-m));
}
```
```C=
double recurBinom(int n, int m) {
    if (m == 0 || n == m) return 1;
    return recurBinom(n - 1, m - 1) + recurBinom(n - 1, m);
}

```
> 時間複雜度: O(n)


