###### tags: `實習`
# 資料結構
https://ocw.nctu.edu.tw/course_detail.php?bgid=9&gid=0&nid=412
## Life Cycle
1. Analysis
2. Design (base your requirements)
3. Refinement (optimization code)
4. verification (Test Case)
## Abstract Data Type(ADT) (抽象資料型別)
1. 資料的一般特性(general characteristics)與操作方式(operations)** 進行討論，而這種資料的抽象化就是**抽象資料型別(Abstract Data Type)

## Algorithm
1. input
2. output
3. definiteness(清楚定義)
4. finiteness(有限性)
5. effectivenss(有效率的)
## Selection Sort
find smallest number in unsort array
put to sort array next place
O(n^2)

    int * Selection_Sort(int * data){
        for(int i=0;i<sizeof(data)/sizeof(int);i++){
        int min = i;
        for(int k=i;k<sizeof(data)/sizeof(int);k++)
            min = (data[i]<data[min])?i:min;
        swap(data[i],data[min]);
        }
        return data
    }
    

## Binary Search
再已排序陣列(單調性)，可利用中間分隔去快速尋找目標
O(Log2(n))

int binary_serarch(int first,int end,int find){
    
    while(data[mid]!=find&&first!=end){
        int mid = (first+end);
        if(data[mid]>find)
            end = mid-1;
        else
           first= mid+1;
    }
    if(first!=end)
        return mid; 
    else
        return -1;
}
    

## Selection Problem
find kth data in array
暴力方法: 排序->data[k]
優化1: 拉K個元素先排序->若比K大丟掉，比K小加入
優化2: PQ

int Selection_K(int * data,int k){
    priority_queue<int,vector<int>,less<int> > less;
    priority_queue<int,vector<int>,greater<int> > greater;
    for(int i=0;i<sizeof(data)/sizeof(int);i++){
        if(less.size()<k)
            less.push(data[i]);
        else if(data[i]>less.top()){
            greater.push(data[i]);
        }else{
            greater.push(less.top());
            less.pop();
        }
    }
    return less.top();
}

## Recursive Algorithms
### 遞迴C計算
C(m,n) = m!(c!(m-n)!)
ex: c(m,n) = c(m-1,n)+c(m-1,n-1)

int c(int m,int n){
    if(n==1)
        return m;
    return c(m-1,n)+c(m-1,n-1)
}

### 遞迴乘法
a*b = a * (b-1) + a
a*1 = a

int mul(int a,int b){
    if(b==1)
        return a;
    return mult(a,b-1)+a;
}

### 遞迴加法
1+2+3+4......n

int sum(n){
    if(n==1)
        return 1;
    return n+sum(n-1);
}

### Recursive Binary Serarch

int binary_serarch(int first,int end,int find){
    int mid = (first+end);
    if(data[mid]==find)
        return mid;
    if(first==end)
        return -1;
    if(data[mid]>find)
        return binary_serarch(first,mid-1);
    else
        return binary_serarch(mid+1,end);
}

### Recursive Permutaions
生成所有可能性
#### 暴力生成

    char * Permutaions(char * ans,char * data,char * temp,int position,bool * check,int * index){
        if (position==sizeof(data)/sizeof(char)){
            char * copy = (char *)malloc(sizeof(data)/sizeof(char));
            strcpy(copy,temp);
            ans[index++]=copy;
        }
        for(int i=0;i<sizeof(data)/sizeof(char);i++){
            if(check[i]==0){
                temp[position]=data[i];
                check[i]=true;
                Permutaions(ans,data,temp,position+1,check,index);
                check[i]=false;
            }
        }
    }

#### 交換生成

    void Permutaions(char * data,int i,int n){
        if (i==n)
            printf("%s\n",ans);
        for(k=i;k<sizeof(data)/sizeof(char);k++){ 
                swap(data[i],data[k]);
                Permutaions(data,i+1, n);
                swap(data[i],data[k]);
        }
    }

## Space Complexity
S(P) = c + Sp(n)
## Time Complexity
O(P) = c + T(n)
### Tabular Method
ex:

    float sum(float list[],int n){
        float tempsum = 0;# O(1)
        int i;
        for (int i=0;i<n;++)# O(N+1)
            rempsum+=list[i];# O(N)
        retrun tempsum;# O(1)
    }

O(2*n+3) => O(n)

## Complexity
### Big-Theta