---
# System prepended metadata

title: '演算法[algorithm]'

---

# 循序搜尋(Sequential Search)
定義：
* 一個一個依序搜尋，效率較差，但資料若未經排 序，僅能使用此方法
* 資料不需事先排序。
* N個資料，則搜尋比對的次數最少1次， 最多N次


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











# 二元搜尋(Binary Search)
* 定義：一種在已排序數列中尋找目標值的搜索算法
* 特性：
1. 資料必需事先排序。
1. N個資料，則搜尋比對的次數： 最少1次，最多Log2N次。
* 流程圖如下
* ![binarysearch](https://hackmd.io/_uploads/ByeTq_Cp6.png)


![image](https://hackmd.io/_uploads/r1HjgWup6.png)
# 比較sequential search v.s. binary search


| Aspect           | Sequential Search                               | Binary Search                                        |
| ---------------- | ----------------------------------------------- | ---------------------------------------------------- |
| Time Complexity  | O(n)                                            | O(log n)                                             |
| Space Complexity | O(1)                                            | O(1)                                                 |
| Efficiency       | Less efficient for large datasets               | Highly efficient for large datasets              |
| Search Method |     Linear search: sequentially checks each element         |Divides search space in half and eliminates one half         |

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

# 氣泡排序(Bubble Sort)
* 定義：氣泡排序是一種簡單的排序算法，它反覆地走訪要排序的數列，依次比較兩個相鄰的元素，若是逆序則交換它們的位置，直到整個數列都是有序的

* 特性：
1. 一種穩定的排序算法，相同元素的相對位置在排序前後不會改變。
2. 在最壞情況下，氣泡排序的時間複雜度為O(n^2)，其中n是要排序的元素數目。

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



# 合併排序(Merge Sort)
* 定義：合併排序是一種分治法的排序算法，它將待排序數列不斷地分成較小的子數列，直到每個子數列只有一個元素，然後將這些子數列合併成較大的有序數列。

* 特性：
1. 無論是最好情況還是最壞情況，時間複雜度為O(n log n) 。這是因為合併排序採取devide and conquer方式排序，故時間複雜度都是線性的。
1. 它在合併操作中保持了相同元素的相對位置，因此是穩定的。 
![image](https://hackmd.io/_uploads/rybTN_q0T.png)

# 比較氣泡排序(Bubble Sort) v.s.合併排序(Merge Sort)


| 特徵 | 氣泡排序 | 合併排序 |
| -------- | -------- | -------- |
| 基本概念         |  反覆比較相鄰元素並交換        |   分治法，將數列分成子問題並合併       |
| 時間複雜度         |  最壞情況：O(n^2)        |    始終為O(n log n)      |
|          |  最好情況：O(n)        |          |
|  穩定性        |  穩定        |   穩定       |
| 效率   | 效率較低，尤其在大型數列中    | 效率較高，特別在大型數列中    |

![image](https://hackmd.io/_uploads/r1_bMV-yC.png)




# 參考資料
1.Dr. Ana Bell , Prof. Eric Grimson, & prof. John Guttag. (2016, August). MIT6_0001F16_Searching and Sorting Algorithms. Introduction To Computer Science And Programming In Python. https://ocw.mit.edu/courses/6-0001-introduction-to-computer-science-and-programming-in-python-fall-2016/resources/mit6_0001f16_lec12/
