---
# System prepended metadata

title: 'Introduction (Concepts, Recursion, Algorithm Analysis)[第一週、第二週]'
tags: [資料結構(交大OCW)]

---

---
title: Introduction (Concepts, Recursion, Algorithm Analysis)[第一週、第二週]
tags: 資料結構(交大OCW)
---

# 一個「系統System」

1. 為了達成「系統」所需要的事情，也就是所要的要求
2. 分析想要達成時，是由最外層到內層(Top-Down)還是由內到外(Bottom-up)
	>老師建議用外到內
3. 有了何種方式後，就是去設計，有哪些資料物件、函式
4. 都有了之後才是真的去寫程式和修改程式
5. 要去做驗證 Verification
	1. 跑各種測試都沒問題，會去看正確性跟效能性
	2. 為了方便後人理解，要照著一個流程寫出很好的文件 Document
	    也就是使用方法，英文又叫 Command
    
# 如何評價你的System
1. 有沒有符合你原本的要求
2. 正常運作
3. 文件
4. 函式正常運作
5. 可讀性
6. 儲存空間使用的效率性
7. 執行時間是否可接受Acceptable
	老師說很主觀，會跟你用的設備有關，但總之越小越好

# Data Abstraction

跟已定義(predifined)的資料相對
Abstract Data Type (ADT) 必須要實作後才能知道是哪種資料型態、需要的空間
但是我可以先定義他的一些屬性、功能，目的是為了達到 Implementation Independent

# Algorithm Specification

演算法，就是解決問題的方法
>當然每個人的定義都不一樣

## Criteria：

1. 輸入，也就是你的問題
2. 輸出，也就是你的答案
3. 精確的
4. 能夠在有線步驟內解決，會停止的
5. 有效的

## 演算法舉例：SORT

只要符合，你的輸入是一堆數字，然後你要輸出由小到大，或是由大到小，就是排序問題

### Selection sort

跑一次陣列的迴圈
然後去找到第 i 個到最後一個中的最小值，找到後就跟第 i 個交換位置
當然如果最小的是自己就不用交換

### Quick sort 最快的排序

但是是 Comparison based
時間複雜度可以到 nlogn
如果不是 Comparison based ，可以更快
老師舉的例子沒聽清楚名字，但是有說到是用 hash table

## 演算法舉例：Binary search

基於二分法，陣列中的內容必須要先排好序
每次都從中間值去比較你要找的值，沒找到就依照大小改變區間

當然 Search 還有很多很多種方法，你可以建一棵二元樹，或是建一個 hash table

:::success
Pseudo Code 就是寫出意思的程式碼，虛擬的程式碼
:::

## 演算法舉例：Selection Problem

選出第 K 大的數字

### 方法一：

就是先排序，再去選取
但若是陣列太大，排序會爆掉

### 方法二：

1. 從數字堆中讀取 k 個數字到一個陣列，並降序排列(decreasing)
2. 將數字堆中剩餘的數字一個一個，跟排序好的陣列中第 k 個比較(也就是最小的)
3. 如果比較小，就無視，如果比較大，就從排序好的陣列中，挑選「正確的」位置，把原數字捨棄換成他
>對，講義是寫 correct place

所以最後比較完，該陣列就會有前 K 大的數字
總之應該就是差在，如果陣列數很龐大，然後 K 也沒有很大
那我就只要排序少少部分的陣列，再用O(n)的時間就可以得到第 K 大
但是沒有說明如何插入「正確的」位置，我猜應該是用二元搜尋等方法

:::warning
1. 蘋果的APP是 Object C 寫出來的 (2013年) Android 是 Java (2013年)
2. 想寫東西出來？先給我把 Pseudo code 寫出來
:::

## 演算法舉例：Recursive Algorithm

有分直接(呼叫自己)跟間接(呼叫外部呼叫他自己的函數)
必須要能夠停止，所以要設置邊界

### 例子：總和

```cpp=
// 想法：
// sum(n) = sum(n-1) + n 
// sum(1) = 1
int sum(int n){
    if (n==1){
        return 1;
    }else{
        return sum(n-1)+n;
    }
}

```

### 例子：Binary search

```cpp=
// 想法：
// sum(n) = sum(n-1) + n 
// sum(1) = 1
int binsearch(int list[],int searchnum, int left, int right){
    if (left<right){
        middle = (left+right)/2;
    }
    switch(COMPARE(list[middle],searchnum)){
        case -1: return binsearch(list,searchnum,middle+1,right);
        case 0: return middle;
        case 1: return binsearch(list,searchnum,left,middle-1);
    }
    return -1;
}

```

### 例子：Permutation

![](https://drive.google.com/uc?id=1hJf5xwDWkcF7hbEFI_tZNWnNjSf3tVGO&export=download)

上圖的符號↔就是交換的意思

我絕對不是偷懶，總之就是每次固定一個位置，傳給下一個Perm
其中第二個參數 INT，應該就是指要固定的位置
如果要固定的位置跟總長度一樣，就直接印出來


---

# Performance Evaluation

分為兩個層次

# Performance Analysis：

這是跟機器無關的，也就是一些對程式碼的分析
也就是複雜度理論Complexity theorem，分為空間跟時間

# 空間複雜度Space Complexity：

![](https://drive.google.com/uc?id=124uuT9VsEja22ORiOFCf8skWfvjKuN8F&export=download)


也就是你花的空間，分成兩個部分
常數部分，跟你程式碼在運行時使用的部分

# 時間複雜度Time Complexity：

![](https://drive.google.com/uc?id=1pK_qE0Wue1EkzJzaFHNnrl24qyNks71i&export=download)

跟空間一樣，有個常數部分，以及程式碼執行的時間

![](https://drive.google.com/uc?id=1mN4dk-FuTg-dppz5q2C-9_jPGrfDd1MG&export=download)

## 方法一：計算步驟

![](https://drive.google.com/uc?id=1ZXulQi3hWFyylLajP88Aq1yx-cWkM7WP&export=download)

賦值 assignment 才會算一步，宣告declare不算一步，這可以算出精準的步數
更直接的方式就是畫表格

![](https://drive.google.com/uc?id=1tlx2ZXJr45DZSJaKlW_Nt4rp67x7Z4we&export=download)

迴圈要注意因為最後會讓i=n，所以是n+1步

![](https://drive.google.com/uc?id=1-6eUtqnAfxm3OW_vXNetoH4KhsjDRw8j&export=download)

## 方法二：尋找跟 n 的關係

精確的步數用意不大，比較需要的是跟 n 的關係，以下介紹三個計算用的函式
這三個函式，都是代表我可以用「某個g(n)」，去把我原本算的步數，也就是 f(n) 給表示出來
而 g(n) 到底是多少，就跟函示要符合的定義有關

## Big O

最常聽到的就是他，也就是找出最糟的情形

![](https://drive.google.com/uc?id=1FqP1TZ7fhDOIsZMRb1MllFsBcpGTHfwV&export=download)

## Omega

這是找出最下界，也就是最好的情況

![](https://drive.google.com/uc?id=1JBVBHWNcQqhd5Mksg7sO_YrGiP_wDENT&export=download)

## Theta

這是找出夾起來的邊界，也就是說 g(n) 要同時符合最上界跟最下界

![](https://drive.google.com/uc?id=1QD7e7RI7dmaRdFklXkJAvmR53Nvnwae9&export=download)



---

:::info
但如果程式碼太龐大很複雜，這時候就如同四則運算的精神，也來找一些規則
:::

![](https://drive.google.com/uc?id=1iUBlFEVD1NUYIyuKWUFUmI7PCkzhtBbQ&export=download)

# Performance measurement：

就是計算執行時間，不同語言會有不同的函式提供你計算，這是跟機器有關的

---

# 練習題?

## 迴圈

理論上仔細計算是 4n+1，O(n)，但是不知為何答案給 3*n
可能答案不是要找 Big O ?
```cpp=
for(int i = 0; i<n;i++){
    x++;
    y++;
    z++;
}
```
答案給  1\*n\*n*
```cpp=
for(int i = 0; i<n;i++){
    for(int j = 0; j<n;j++){
        k++;
    }
}
```
這裡要利用上面的規則，所以是 max(3\*n,1\*n\*n*) = 1\*n\*n*
```cpp=
for(int i = 0; i<n;i++){
    x++;
    y++;
    z++;
}
for(int i = 0; i<n;i++){
    for(int j = 0; j<n;j++){
        k++;
    }
}
```
## 判斷

max(2,1\*n) = 1\*n
```cpp=
if(i>0){
    i++;
    j++;
}else{
    for(j = 0; j<n;j++){
        k++;
    }
}
```

# 常見的複雜度

| Name    | meaning     |
| ------- | ----------- |
| c       | constant    |
| logN    | logarithmic |
| logN^2^ | log-squared |
| N       | Linear      |
| NlogN   |             |
| N^2^    | Quadratic   |
| N^3^    | Cubic       |
| 2^N^    | Exponential |






