```
112考資工研究所時寫的筆記，有錯歡迎留言指正
內文有引用他人筆記/教材/文章的地方
若有侵權十分抱歉，告知後將立刻撤除
```
[TOC]
# Basic concept
- 太基本了，幾乎都是algo的東西，skip
# Array
- 算幾題array和位址的轉換(2d array很多陷阱)就差不多了
- row major 和 column major 算出來結果可能都可以，答案就會不只一個
# Stack & Queue
- queue & stack的實作應該可以跳過 (算都會了吧?)
- 考過不只一次，不看根本不會
- [infix to prefix using stack](https://www.youtube.com/watch?v=8QxlrRws9OI)
- [infix to postfix using stack](https://www.youtube.com/watch?v=PAceaOSnxQs)
- postfix 用stack運算結果
- 歷屆16, 19
# Linked list
- Sparse matrix (p141)有點常考
- Generalized list (p149)
- 挺煩人的，很容易忘
# Tree & Binary Tree
- Define:
- $n:$全部node個數
- $n_0:$ deg(v)=0的node個數
- $n_1:$ deg(v)=1的node個數
- $n_2:$ deg(v)=2的node個數
- 重要定理$: n_0=n_2+1$
- proof: $n=n_0+n_1+n_2=1+n1+2n_2$
- 三種node合=從deg記算的node數，+1為沒被算入的root(沒人存他)
- ==Complete== Binary tree
- 簡單來說就是，由上到下由左到右長
- 
- ==Full== Binary tree
- 定義一:
- 剛好把leaf那層長滿，每片數葉深度都一樣
- 深度為h的full binary tree，node必為$2^h-1$
- 
- 定義二:
- 除了葉子以外的節點 (internal node) degree皆為n (n在binary tree中為2)
- 
- 兩個定義的tree會長得很不一樣，需看題目怎麼定義
- 把BST用inorder輸出，即為排序好的結果
- Thread Binary Tree (p182)
- 看一下線怎麼連，code先skip
- Leftmost child next right sibling (p187)
- 留左邊child的link，其他砍掉，同層連起來，旋轉45度 (很抽象)
- 森林轉成樹 (p188)
- root連在一起，旋轉一下
- Inorder, preorder, postorder熟到爛掉，skip
- 記得一定要有Inorder才能決定唯一tree (preorder, postorder無法唯一決定)
- n個node的binary tree有$\displaystyle \frac{1}{n+1} {2n \choose n}$種 (catalan number)
- 計算某條件下(ex. deg=i的node有幾個)的internal node/leaf數量，把branch數量也拿來列式 (歷屆5,6)
- Heapify整棵是亂的樹 (歷屆38)
- 從root開始，廣度優先檢查node是否符合heap規則(可能是min or max當parent)
- ==Heap可以在O(n)時間內建好==
- 
- from [mega ch5 tree](https://drive.google.com/file/d/1zoJAlbWOsHr7ZewSVKT7dPgKSDSd0ako/view?usp=share_link)
- [stackoverflow說明](https://stackoverflow.com/questions/9755721/how-can-building-a-heap-be-on-time-complexity#:~:text=In%20summary%2C%20the%20work%20for,O(n%20log%20n).)
- 但是把每個node刪除/提取出，還是需要$O(n\lg n)$
# Graph
- edge種類(DFS後，把edge分成4種)
1. Tree: Edges in the DFS forest
2. Back: From descendant to ancestor when explored (include self loop)
3. Forward: From ancestor to descendant when explored (exclude tree edge)
4. Cross: Others (no ancestor-descendant relation)
- ==無向圖只有tree edge, back edge而已!==
- 
- [articulation point](https://www.geeksforgeeks.org/articulation-points-or-cut-vertices-in-a-graph/) (cut vertex)
- 移出該vertex後，會導致圖變為disconnected，稱作articulation point
- 尋找articulation point的演算法
- Remove v from graph
- See if the graph remains connected (BFS or DFS)
- Add v back to the graph
- ### adjacency matrix vs transitive closure
- adjacency matrix對角線是0，transitive closure對角線是1
- adjacency matrix紀錄點之間的距離
- transitive closure紀錄的是"能到達為1，不能到達為0"
- [AOE network](https://garychang.gitbook.io/data-structure/4-graph/4.5-aoe-network) (activity on edge network)
- 以p297 試題50為例
- 先算出每個node最早發生時間，反推可得最晚發生時間，兩個時間可以註記在node上
- critial path length即為最後一個node(event)的數字
- 用看的找出critical path (看一下length是不是跟上面一樣!)
- event最早完成時間就是activity的earlist start time
- event最晚完成時間減去活動長度即為activity的latest start time
- 我還是拍影片好了
# Sorting
- 證明用comparison為基礎的排序至少都要nlgn的時間:
- 說明decision tree高度為$\lceil \log_2 n! \rceil+1$
穩定排序: **插入、泡泡、融合、基數** (insertion, bubble, merge, radix)
不穩定排序(也可記排除上面那些): **選擇、快速、堆積** (selection, quick, heap)
## Insertion sort
不斷把尚未sort的item插入前面已經sort好的部分
- Stable
- Space complexity: $O(1)$
- Time complexity:
- Worst: $O(n^2)$
- Avg: $O(n^2)$
```cpp=
void InsertionSort(int *arr, int size){
for (int i = 1; i < size; i++) {
int key = arr[i];
int j = i - 1;
while (key < arr[j] && j >= 0) {
arr[j+1] = arr[j];
j--;
}
arr[j+1] = key;
}
}
```
參考
[Comparison Sort: Insertion Sort(插入排序法)](http://alrightchiu.github.io/SecondRound/comparison-sort-insertion-sortcha-ru-pai-xu-fa.html)
[Rust Algorithm Club](https://rust-algo.club/sorting/insertion_sort/index.html)
## Selection sort
一直把最小的抓下來放
- Unstable
- Space complexity: $O(1)$
- Time complexity:
- Worst: $O(n^2)$
- Avg: $O(n^2)$
```cpp=
void selection_sort(int array[], int n) {
for (int i=0; i<n-1; i++) {
int min_idx = i;
for (int j=i+1; j<n; j++)
if (array[j] < array[min_idx])
min_idx = j;
swap(array, min_idx, i);
}
}
```
參考
[Rust Algorithm Club](https://rust-algo.club/sorting/selection_sort/index.html)
[C/C++ selection sort 選擇排序法](https://shengyu7697.github.io/cpp-selection-sort/)
## Bubble sort(sinking sort)
比較兩個相鄰元素，若首個元素比次個元素大，置換兩者的位置。
依序對相鄰元素執行步驟一，直到抵達序列頂端，此時頂端元素排序完成。
重複步驟 1 - 2 的整個序列疊代，==直到任何一次疊代沒有執行元素置換。==
當然也可以如下程式，直接疊代n次後停止
- stable
- Space complexity: $O(1)$
- Time complexity:
- Worst: $O(n^2)$
- Avg: $O(n^2)$
```cpp=
for(i = n-1; i > 0; i--)
for(j = 0; j <= i-1; j++)
if( A[j] > A[j+1])
swap(A, j, j+1);
```
參考
[[C++] 氣泡排序法(Bubble sort)](https://medium.com/@oturngo/study-note-01-%E6%B0%A3%E6%B3%A1%E6%8E%92%E5%BA%8F%E6%B3%95-bubble-sort-ee534b6f91eb)
## Quick sort
畫sort過程必考，看講義316說明和範例很容易懂
- Unstable
- Space complexity: $O(n)$
- Time complexity:
- Worst: $O(n^2)$
- Avg: $O(n \log n)$
```cpp=
int Partition(int *arr, int front, int end){
int pivot = arr[end];
int i = front -1;
for (int j = front; j < end; j++) {
if (arr[j] < pivot) {
i++;
swap(&arr[i], &arr[j]);
}
}
i++;
swap(&arr[i], &arr[end]);
return i;
}
void QuickSort(int *arr, int front, int end){
if (front < end) {
int pivot = Partition(arr, front, end);
QuickSort(arr, front, pivot - 1);
QuickSort(arr, pivot + 1, end);
}
}
```
參考
[Comparison Sort: Quick Sort(快速排序法)](http://alrightchiu.github.io/SecondRound/comparison-sort-quick-sortkuai-su-pai-xu-fa.html)
## Merge sort
合併過程必考，講義322,324分別為兩種(Iterative/Recursive)合併方法
- stable
- Space complexity: $O(n)$
- Time complexity:
- Worst: $O(n \log n)$
- Avg: $O(n \log n)$
```cpp=
void Merge(std::vector<int> &Array, int front, int mid, int end){
// 利用 std::vector 的constructor,
// 把array[front]~array[mid]放進 LeftSub[]
// 把array[mid+1]~array[end]放進 RightSub[]
std::vector<int> LeftSub(Array.begin()+front, Array.begin()+mid+1),
RightSub(Array.begin()+mid+1, Array.begin()+end+1);
LeftSub.insert(LeftSub.end(), Max); // 在LeftSub尾端加入Max元素(sentinel)
RightSub.insert(RightSub.end(), Max);// 在RightSub尾端加入Max元素(sentinel)
int idxLeft = 0, idxRight = 0;
for (int i = front; i <= end; i++) {
if (LeftSub[idxLeft] <= RightSub[idxRight] ) {
Array[i] = LeftSub[idxLeft];
idxLeft++;
}
else{
Array[i] = RightSub[idxRight];
idxRight++;
}
}
}
void MergeSort(std::vector<int> &array, int front, int end){
// front與end為矩陣範圍
if (front < end) { // 表示目前的矩陣範圍是有效的
int mid = (front+end)/2; // mid即是將矩陣對半分的index
MergeSort(array, front, mid); // 繼續divide矩陣的前半段subarray
MergeSort(array, mid+1, end); // 繼續divide矩陣的後半段subarray
Merge(array, front, mid, end); // 將兩個subarray做比較, 並合併出排序後的矩陣
}
}
```
參考
[Comparison Sort: Merge Sort(合併排序法)](http://alrightchiu.github.io/SecondRound/comparison-sort-merge-sorthe-bing-pai-xu-fa.html)
## Heap sort
最重要的是了解抽走max/min後怎麼把樹重新Heapify，下面連結講的很清楚
尚未建成max-heap前，到建成第一個max-heap的過程也要會(參考講義)
==特別注意==：在同一個subtree裡，leftchild(index(2i))與rightchild(index(2i+1))的「數值」大小順序不重要，只要和root(index(i))比較即可。
- Unstable
- Space complexity: $O(1)$
- Time complexity:
- Worst: $O(n\log n)$
- Avg: $O(n\log n)$
```cpp=
// Code超複雜 跳過 ^_^
```
參考
[Comparison Sort: Heap Sort(堆積排序法)](http://alrightchiu.github.io/SecondRound/comparison-sort-heap-sortdui-ji-pai-xu-fa.html)
## Bucket sort
- [mega筆記 ch5.Tree](https://drive.google.com/file/d/1DvDNPXXK8ZkiprnQvvR9xdRqYb2nYQzr/view?usp=share_link)說bucket sort為Radix sort的MSD版
- [Rusk algorithm club](https://rust-algo.club/sorting/bucket_sort/index.html)說bucket sort是先裝入桶子在用insertion sort排序
- ex: 1~100, 101~200...901\~1000 假設共r=10桶
- 數字如果平均分散在這個範圍內，每個桶只會有n/10筆資料
- 每個桶用insertion sort，**這邊需假設資料小到能$O(n/r)$時間完成**
- 把資料串回來，需要
- Space complexity: $O(n\times r)$
- Time complexity:
- Worst: $O(n^2)$ 當所有人擠同一個桶子
- Avg: $O(n+r)$
- d: max number digit / r: buckets
## Radix sort
- 主要有MSD/LSD兩種，差別在從最大or最小的digit開始分類
- 講義p.330有分類過程，務必看過
==桶子是FIFO==
- MSD: unstable, LSD: stable
- Space complexity: $O(n\times r)$
- Time complexity:
- Worst: $O(d\times(n+r))$
- Avg: $O(d\times(n+r))$
- d: max number digit / r: buckets
```cpp=
// 我賭不會考 考了應該也憑感覺寫得出來吧(記得桶子用Queue做!!!)
```
參考
- [線性排序比較 Radix sort / bucket sort / counting sort](https://iq.opengenus.org/counting-sort-vs-radix-sort-vs-bucket-sort/#:~:text=Radix%20sort%20uses%20counting%20sort,a%20stable%20linear%20sorting%20algorithm.)
# Hashing
- ### 名詞解釋
- bucket
- 分成幾個單位(ex. mod 5就是5個bucket)
- slot
- 每單位可放幾個record
- load density (factor)
- n=放入hash的變數各數
- sb=hash table的容量大小
- $\displaystyle \alpha=\frac{n}{sb}$，可以視為平均一個bucket中有幾個人
- collision
- 兩個不同字進到同個桶中
- overflow
- collision且桶子滿了(no more slots)
- perfect hashing
- 保證不會有collision發生的hashing function
- ### overflow handing
- Linear probing
- 一個bucket滿了，去下一個bucket放
- Quadratic probing
- 如果經過h(x)算出的位置滿了，重算公式如下
- $h(x)\pm i^2$，如果還是滿的，i++
- double hashing
- 如果經過h(x)算出的位置滿了，重算公式如下
- $h(x)+i*f(i)$，如果還是滿的，把$i+1$再算一次
- ex. f(i)=(7-x%7)
- h(41)+1\*f(1)=h(41)+1*(7-41%7) --->滿的話繼續往下算
- h(41)+2\*f(2)=h(41)+2*(7-41%7)
- 以此類推
# 高等樹
[Mega大筆記](https://drive.google.com/drive/folders/1t9mKiqrLc_d9CaVLNtK8Jj8FKcAA3t-C)
## Double-Ended priority queue
- Time complexity
- Insertion: $O(\lg n)$
- Delete min/max: $O(\lg n)$
- find min/max: $O(\lg n)$
- 皆為Complete (binary) tree
- 以下三種都是這種queue
- Min-max heap
- Deap (Double-Ended-Heap)
- Symmetric min-max heap (SMMH)
## Min-Max heap
- 一種Double-Ended priority queue
- 定義
- Complete Binary Tree
- Tree level被分為min level和max level
- 若某節點位於min(max) level，則以該點為根的子樹中，他的權重為最小(大)值。
- 第一層(root)必須為min level
- [完整介紹 & Insert & Delete](https://medium.com/%E7%8B%97%E5%A5%B4%E5%B7%A5%E7%A8%8B%E5%B8%AB/%E5%9C%96%E8%A7%A3-double-ended-priority-queue-%E9%80%B2%E9%9A%8E%E6%A8%B9-1ae18d2ca402)
- 看圖弄懂流程就好，文章廢話太多了
- delete 有分delete min和delete max，略有不同
- [Mega大筆記](https://drive.google.com/drive/folders/1t9mKiqrLc_d9CaVLNtK8Jj8FKcAA3t-C)中，insert的圖示有誤，正確請參考文章
## Deap (Double-Ended-Heap)
- 定義
- 一棵Complete Binary Tree
- root不儲存任何資料
- root的左子樹是min-heap ; 右子樹則為max-heap
- 在root左子上的任一點 i，令 j 為他在右子樹中對應的節點，i 點的權重必須小於 j 點的權重。(p.s 若無對應點則取其父點)
- [完整介紹 & Insert & Delete (Deap在比較下面，文章中很多廢話自行跳過)](https://medium.com/%E7%8B%97%E5%A5%B4%E5%B7%A5%E7%A8%8B%E5%B8%AB/%E5%9C%96%E8%A7%A3-double-ended-priority-queue-%E9%80%B2%E9%9A%8E%E6%A8%B9-1ae18d2ca402)
- insert的"對應點"概念，看書很容易理解
- 其他說明都看這篇文章
## SMMH (Symmetric min-max heap)
- 定義
- 是一個Complete Binary Tree，Root不存Data，滿足:
1. 左兄弟 ≤ 右兄弟 (近兄弟)
2. 節點x的祖父的左子點必須 ≤ x
3. 節點x的祖父的右子點必須 ≥ x
對於節點i來說，i的左子點是i的子樹中的最小值(不含i)。
對於節點i來說，i的右子點是i的子樹中的最大值(不含i)。
- [刪除插入文字敘述](https://garychang.gitbook.io/data-structure/lecture2-tree-and-binary-tree/lecture-2.8-advanced-trees/2.8.3-symmetric-min-max-heap)
- [刪除](https://publish.get.com.tw/BookPre_pdf/51MM045102-2.pdf)
<!-- - [Insert & delete自錄影片](https://www.youtube.com/watch?v=f_wTGAPEqAo) -->
## Extended Binary Tree
- **External Node = Failure Node, 數量為internal node+1**
- E: External path length
- I: Internal path length
- N: Internal Node
- $E=I+2N$
- [完整介紹](https://hackmd.io/@vRN1CwEsTLyHOsG4mC0d4Q/SJJ6ofDn4)
## Minimal Weighted External path length
- 三種求法
- 最常見: Huffman algo $O(n \lg n)$
- 暴力
- DP
- [完整介紹](https://hackmd.io/@vRN1CwEsTLyHOsG4mC0d4Q/SJJ6ofDn4)
## Optimal Binary search tree (OBST)
略，見algo筆記
## AVL tree
- 高度平衡樹，$|h_L - h_R| \leq 1$
- AVL定理
- [證明在連結最下面](https://garychang.gitbook.io/data-structure/lecture2-tree-and-binary-tree/lecture-2.8-advanced-trees/2.8.5-avl-tree)
- Let 形成高度h的AVL Tree所需最少的節點數為$a_h$
- $a_h = a_{h-1}+a_{h-2}+1$
- $a_h = F_{h+2}-1$，其中$F$為費式數列，這裡令h=0為root height
- insert & 完整介紹: 見陳宜欣Slides
- [delete](https://www.youtube.com/watch?v=g4y2h70D6Nk)
## B tree
- B tree is a **balanced** m-way search tree
- 令$t=\lceil\frac{m}{2}\rceil$
- 2 $\leq$ deg(root) $\leq$ m
- $\displaystyle t \leq$ deg(node) $\leq m$
- 1 $\leq$ root's key $\leq$ 2t-1
- t $\leq$ node's key $\leq$ 2t-1
- 一個m階的B樹具有如下幾個特徵：
1. 根結點至少有兩個子女。
2. 每個中間節點都包含k-1個元素和k個孩子，其中 m/2 <= k <= m
3. 每一個葉子節點都包含k-1個元素，其中 m/2 <= k <= m
4. 所有的葉子結點都位於同一層。
5. 每個節點中的元素從小到大排列，節點當中k-1個元素正好是k個孩子包含的元素的值域分劃
- Insert & delete: 陳宜欣Slides session 10
<!-- - [5-way B tree插入與刪除 自錄影片](https://youtu.be/AM3XRJ17Bos) -->
## 2-3 tree
- B tree of order 3 = 3 way B tree
- 內部結點degree為2 or 3
- degree=child數目，一個key的node有兩個child，兩個key的node有三個child
- 所有外部結點位於同階層
- 令2-3 tree height = h，internal node = n
- $\log_3 (n-1) \leq h \leq \log_2 (n-1)$
- [Insertion](https://www.youtube.com/watch?v=bhKixY-cZHE)
- Delete: 看課本(也有[影片](https://www.youtube.com/watch?v=b0naM_7ofYo)，但課本講得比較好)
## 2-3-4 tree
- B tree of order 4 = 4 way B tree
- 有時簡稱2-4 tree
- 內部結點degree為2, 3 or 4
- insert還是會從最上面開始，比較大小決定往左or右放
- [Insert & Delete](https://www.youtube.com/watch?v=0tg6sj3SsN4)
- [TOP-Down & Bottom up 解法 (包含insert, delete)](http://u.camdemy.com/media/510)
- 刪除非常混亂，別的[影片](https://www.youtube.com/watch?v=94e-uBYK5nk)這樣講但我沒懂
## B+ tree
- 很類似B tree，差在B+ tree leaf層才有完整資料，上面都是index，為的是降低IO次數
- 不是每次insert都需在non-leaf node留下自己的index，只有split後，才需要留
- split可以想成依照B tree規則先把資料弄上去，再把資料往下放到右子樹的最小值
以下為交大104資演:
ans:
參考[mega ch9 advance tree](https://drive.google.com/file/d/11jcHDxHtX9mexSxrrG-cDBV3rQt2KsX4/view?usp=share_link)筆記
其他參考: [hackmd](https://hackmd.io/@w8qbx0fdRK2ETRnEzcLK2A/SyjKs-mxg?type=view)
[B+ tree visualization](https://www.cs.usfca.edu/~galles/visualization/BPlusTree.html)
## red-black tree
- 五條規則
- 樹上的每個節點 (node) 只能是紅色或黑色
- 根節點 (root) 一定要是黑色
- 葉節點 (leaf) 一定要是黑色的空值 (NULL)
- 紅色節點的兩個子節點 (child) 一定要是黑色 (亦即不能有兩個紅色節點相連，注意：黑色節點的子節點顏色沒有限制)
- 從任何節點出發，其下至葉節點所有路徑的黑色節點數目要相同
- [2-3-4 tree to red-black tree](https://azrael.digipen.edu/~mmead/www/Courses/CS280/Trees-Mapping2-3-4IntoRB.html)
- [insert](http://alrightchiu.github.io/SecondRound/red-black-tree-insertxin-zeng-zi-liao-yu-fixupxiu-zheng.html)
- [delete](http://alrightchiu.github.io/SecondRound/red-black-tree-deleteshan-chu-zi-liao-yu-fixupxiu-zheng.html)
- [看印度人講比較快](https://tigercosmos.xyz/post/2019/11/algorithm/red-black-tree/)
- 其他資源
- [Red-Black Tree / 紅黑樹 (插入刪除都講得不錯)](https://medium.com/@imprld01/red-black-tree-%E7%B4%85%E9%BB%91%E6%A8%B9-8d793e692d70)
- [Red-Black Trees | Deletion](https://www.codesdope.com/course/data-structures-red-black-trees-deletion/)
- [Red-Black tree visualization](https://www.cs.usfca.edu/~galles/visualization/RedBlack.html)
## Union set
以下code使用union by rank with path compression
```python=
def Make_set(x):
x.parent=x
x.rank=0
def Find_set(x):
if x==x.parent:
return x
return find_set(x.parent)
def Union(x,y):
Link(Find_set(x), Find_set(y))
def Link(x,y):
if x.rank > y.rank:
y.parent=x
else:
x.parent=y
if x.rank == y.rank:
y.rank++
```
- [說明](https://haogroot.com/2021/01/29/union_find-leetcode/)
- 複雜度:
- Union: $O(1)$
- Find (with union by rank): $O(\alpha (n)) \approx O(1)$
- 另外有union by height , union by size，兩者導致union & find會有$O(\lg n)$
- [ref](http://web.eecs.utk.edu/~jplank/plank/classes/cs302/Notes/Disjoint/#:~:text=Union%20by%20height%3A%20The%20height,node%20whose%20height%20is%20bigger.), [ref2比較詳細](https://www.cs.princeton.edu/courses/archive/spring13/cos423/lectures/UnionFind.pdf), [ref3](https://hackmd.io/@CLKO/rkRVS_o-4?type=view), [ref4](https://yuihuang.com/union-find-algorithm/)
- 參考台大102資演題目，當作練習
## leftist tree
左傾樹
[說明](https://tmt514.gitbooks.io/2016-09/content/tree-ds/leftist-tree.html)
- 建議自己畫左傾樹插入1~10，用下面工具比對步驟是否正確，才算完全懂
[visualization](https://www.cs.usfca.edu/~galles/visualization/LeftistHeap.html)
## Binomial queue
[影片講得不錯](https://www.youtube.com/watch?v=9G-5jUqQAVc)
[圖解](https://gtl.csa.iisc.ac.in/dsa/node141.html)
## Binomial heap, Fibonacci heap
[別人的筆記](https://hackmd.io/@Zero871015/DSNote-19)
- 
- [圖片來源:高等樹筆記](https://drive.google.com/drive/folders/1t9mKiqrLc_d9CaVLNtK8Jj8FKcAA3t-C)
# 補充
- [In-place algorithm (重要)](https://zh.m.wikipedia.org/zh-tw/%E5%8E%9F%E5%9C%B0%E7%AE%97%E6%B3%95)
- Build heap只需要$O(n)$就能完成，而非 $O(n\lg n)$ !!!
- 
- 複雜度O(n)證明: 最後一個父點所在的layer最多有n/4 nodes，他們最多會往下移動1；再上一層最多有n/8 nodes，他們最多往下移動2；... Top node最多往下移動h ([ref](https://stackoverflow.com/questions/9755721/how-can-building-a-heap-be-on-time-complexity))
- 
- merge two heap: $O(n)$
- insert, delete都是$O(\lg n)$
- merge two leftist tree: $O(\lg n)$
- 
- Binary search tree如果不平衡，每次插入/查詢可達$O(n)$
- [Fibonacci search](https://www.youtube.com/watch?v=q_AVjuzBxoc), [ref2](https://hackmd.io/@Aquamay/H1nxBOLcO/https%3A%2F%2Fhackmd.io%2F%40Aquamay%2FSynpeGbiu) (還沒看，但感覺很厲害)
- 
- 以108清大計科為例: 對1,2,3...16的sequence分別搜尋2, 10, 15所需次數
```
before search, construct Fn and searched sequence A[]
Fibonacci
k : 0 1 2 3 4 5 6 7 8
Fk: 0 1 1 2 3 5 8 13 21
A[]
i : 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
A[i]: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
n = last index of A[] = 15
k=8 (the kth Fibonacci number >= A[n])
offset = -1
search 2:
i = min(-1+F(8-2), 15) = min(-1+8, 15) = 7
2<A[7] --> k = 8-2 = 6
i = min(-1+F(6-2), 15) = min(-1+3, 15) = 2
2<A[2] --> k = 6-2 = 4
i = min(-1+F(4-2), 15) = min(-1+1, 15) = 0
A[0]<2 --> k = 4-1 = 3, offset = i = 0
i = min(0+F(3-2), 15) = min(0+1, 15) = 1
A[1]=2 , Find!
search 10:
i = min(-1+8, 15) = 7
A[7]<10 --> k = 8-1 = 7, offset = 7
i = min(7+5, 15) = 12
10<A[12] --> k =7-2 = 5
i = min(7+2,15) = 9
A[9]=10, Find!
search 15:
i = min(-1+8, 15) = 7
A[7]<15 --> k = 8-1 = 7, offset = 7
i = min(7+5, 15) = 12
A[12]<15 --> k = 7-1=6, offset = 12
i = min(12+3, 15) = 15
15<A[15] --> k = 6-2 =4
i = min(12+1, 15) = 13
A[13]<15 --> k = 4-1 = 3, offset = 13
i = min(13+1, 15) = 14
A[14] = 15, Find!
```
Sign in with Wallet
Connect another wallet