<font color="#8A2BE2">[面試筆記]</font> 資料結構與演算法整理
===

總表
---
| | 陣列 | 鏈結串列 |
|:---|:---:|---:|
|元素的存放|一個接一個連續排列|分散在各處|
|存取方式|隨機存取|循序存取|
| 讀取 | O(1) | O(n) |
| 插入 | 需要搬移插入點之後的所有元素，沒有空間會發生錯誤 O(n) | 只要更改元素的指向位置 O(1) |
| 刪除 | 刪除完元素後，後續元素往前移動 O(n) | 只要更改元素的指向位置 O(1) |

備註：鏈結串列 雖然刪除是O(1)但是查訪需要O(n)

一 鏈結串列 Linked list
---
#### 解釋：
元素可以存在記憶體中任何一個空位，會紀錄下存放位置，透過存放位置找到鏈結串列的每一個元素

#### 應用：

1. 鏈結串列可能用在某些網站為了賺瀏覽量，一頁只顯示一個項目，例如10大電影，使用者必須一頁一頁的點擊『下一頁』去瀏覽整個資訊
2. 服務生將新訂單寫入，廚師只要取出最前端的訂單
2. 紀錄每天花費記帳程式，月底才需要檢視

#### 缺點：
當沒有需要依序讀取整個元素的話，使用鏈結串列就比較浪費時間了

#### 優點：
插入的資料多，讀取的資料少的資料適合使用

二 選擇排序 Selection sort
---
#### 解釋：
每次頭到尾走過一遍，找出該值方入。n個項目每次花費n次。不錯的演算法，但速度不快

#### 應用：
1. 紀錄每位歌手播放次數的記錄表，依播放次數高到低來排序
2. 排序電話簿裡面的姓名
4. 依照日期排序電子郵件

舉例
| | 播放次數 | |
|:---|:---:|---:|
| RADIOHEAD | 156 |
| SHAKIRA | 30 |
| John Legend | 94 | |
| Bruno Mars | 88 | |
| Taylor Swift | 61 | |
| Ladygaga | 111 | |

<br>

Step1 從頭到尾找出播放次數最多，是RADIOHEAD 花費O(n)
Step2 建立新的表格，把RADIOHEAD放入
| | 播放次數 | |
|:---|:---:|---:|
| RADIOHEAD | 156 |

<br>

Step1 從頭到尾找出播放次數最多，是Ladygaga 花費O(n)
Step2 新的表格，把Ladygaga放入
| | 播放次數 | |
|:---|:---:|---:|
| RADIOHEAD | 156 |
| Ladygaga | 111 | |

一直重複

#### 缺點：
時間複雜度O(n^2)
#### 優點：
簡單

三 遞迴 Recursion
---
#### 解釋：


#### 應用：
在後續資料結構與算法中的應用
#### 缺點：
效率可能不一定比較快，for/while迴圈可能更快
#### 優點：
優美

四 堆疊 Stack 使用遞回
---
#### 解釋：
基本情況Base Case + 遞迴情況Recursive Case

call Stack

function fact(x) {
    if (x === 1){
        return 1
    }
    else {
        return x * fact(x-1)
    }
}

fact(3)    //6

/*
參數3帶入
if    不成立 3!=1
else    成立 3*fact(2)  3*(2)=6

參數2帶入
if    不成立 2!=1       
else    成立 2*fact(1)  2*(1)=2

參數1帶入
if     成立 1==1        1
else  不成立 

*/

1. 範例

2. 範例

fact(1)
fact(2) -> fact(2)
fact(3) -> fact(3) -> fact(3)

#### 應用：

#### 缺點：

#### 優點：

五 分治法 Divide and Conquer
---
#### 解釋：
限縮問題，逐步拆解
#### 應用：

#### 缺點：
#### 優點：

六 快速排序法 Quick sort
---
#### 解釋：
如果能處理1個元素的陣列，就能夠處理2個元素陣列
如果能夠處理2個元素陣列，就能夠處理3個元素陣列
以此類推
#### 應用：

#### 缺點：
#### 優點：
最差情況 O(n^2)
平均情況 O(nlogn)

七 合併排序法 Merge sort
---

#### 解釋：
#### 優點：
#### 應用：
#### 缺點：
#### 優點：
最差情況 O(nlogn)
平均情況 O(nlogn)

[參考大神Sean Chou medium連結：](https://medium.com/技術筆記/基礎演算法系列-你只會用-built-in-function-來排序嗎-4a196d37f9f5)

###### tags: `[面試]`