---
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
上圖的符號↔就是交換的意思
我絕對不是偷懶，總之就是每次固定一個位置，傳給下一個Perm
其中第二個參數 INT，應該就是指要固定的位置
如果要固定的位置跟總長度一樣，就直接印出來
---
# Performance Evaluation
分為兩個層次
# Performance Analysis：
這是跟機器無關的，也就是一些對程式碼的分析
也就是複雜度理論Complexity theorem，分為空間跟時間
# 空間複雜度Space Complexity：
也就是你花的空間，分成兩個部分
常數部分，跟你程式碼在運行時使用的部分
# 時間複雜度Time Complexity：
跟空間一樣，有個常數部分，以及程式碼執行的時間
## 方法一：計算步驟
賦值 assignment 才會算一步，宣告declare不算一步，這可以算出精準的步數
更直接的方式就是畫表格
迴圈要注意因為最後會讓i=n，所以是n+1步
## 方法二：尋找跟 n 的關係
精確的步數用意不大，比較需要的是跟 n 的關係，以下介紹三個計算用的函式
這三個函式，都是代表我可以用「某個g(n)」，去把我原本算的步數，也就是 f(n) 給表示出來
而 g(n) 到底是多少，就跟函示要符合的定義有關
## Big O
最常聽到的就是他，也就是找出最糟的情形
## Omega
這是找出最下界，也就是最好的情況
## Theta
這是找出夾起來的邊界，也就是說 g(n) 要同時符合最上界跟最下界
---
:::info
但如果程式碼太龐大很複雜，這時候就如同四則運算的精神，也來找一些規則
:::
# 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 |
Sign in with Wallet
Connect another wallet