資料結構筆記
Slowly move to chengr4/my-data-structures: My data structures (github.com)
Content:
+ Notation O, 𝛺, 𝛩 (Theta)
+ Running time calculations
+ Array
+ Queue
+ Stack
+ A mazing problem
+ Linked list
+ Tree
+ Priority queue (== Heap)
+ Hoffman code
+ Graph
+ Sorting
+ Hash
+ Reference
Notation O, 𝛺, 𝛩 (Theta)
找最小的 upper bound 和最大的 lower bound 才有意義
Big-O (upper bound)
E.g.
Condition: T(n) = 3n+2, F(n) = nif T(n) = 3n+2 = O(n)
=> 3n+2 < cn
當 c = 4 => 存在
Properties of Notation O, 𝛺, 𝛩 (Theta)
- Transitivity
- Rule of sums
使用時機：在算一個演算法需要花的時間時，不用計算所有步驟的加總，計算最花時間的步驟即可
- Rule of products
使用時機：For loop, while loop
- Transpose symmetry
- Reflexivity
- Symmetry
Running time calculations
Nested for loops
for(i=0; i<N; i++)
for(j=0; j<N; j++)
k++;=> 1*N*N
Consecutive statements
for(i=0; i<N; i++)
A[i]=0;
for(i=0; i<N; i++)
for(j=0; j<N; j++)
A[i]+=A[j]+i+j;T(前) + T(後) =max(1*N, 1*N*N) = 1*N*N (Rule of sum)
Array
- 固定空間
- Implemented by consecutive memory (連續的記憶體空間)
int list[5];
list[0] // base address = a
list[1] // a + sizeof(int)- one dimension, two dimension…..
用法
+ 宣告多項式
+ 宣告 matrix
+ 宣告 String
- 宣告多項式 e.g.
x⁴+10x³+3x²+1
方法1: key:指數, value:係數
方法2: use one global array to store all polynomials
// written by C++
class term {
friend Polynomial; // 可以取用 term 的 private
private:
private coef; // coefficient
private exp; // exponent
}class Polynomial {
private:
static term termArray[MaxTerm]; // 靜態，所有 Polynomial 共用
static int free; // TermArray 的最後 column
int Start, Finish;}
- 宣告 matrix
E.g. 宣告Spare matrix (其元素大部分為零的矩陣)
- 宣告 String
Usually String is represented as a character array
KMP Algorithm
- 一個比較有效率的找字串演算法
- 一次可以 shift 多個位元
Queue
- FIFO (first in first out)
- 兩端開口，因此需要指標 front(頭) and rear(尾)
- 進階: priority queue
- 有限
- 實現：Linked list (自己覺得), circular queue
Circular queue
If (front == rear)=> queue 是空值- Problem: one space is left when queue is full
- 用mod Max_size 判斷 queue是否已滿
用法
- 排隊
- Job scheduling in OS system
Stack
- A finite ordered list
- LIFO (last in first out)
- top and bottom
- ㄧ端開口，因此只需要 top 指標
- 可以用 Array, Linked list implement
用法
- 四則運算 input with Postfix
A mazing problem
- 走迷宮問題
- 可以用一個 stack 紀錄曾經走的每個位置
Linked list
- 組成: node, pointer
- 其他種 linked list: Double linked list (可以前後一起搜索)
- 被刪除的 node 可以選擇從記憶體刪除或者再開一個 free list 存放 (省去要再 call memory 的麻煩)
優點
- 能節省儲存空間
缺點
- 要找到需要的 node 需要從第一個開始一個一個檢查
用法
- 宣告多項式
優點：加減法快
缺點：?????
- 宣告 matrix
E.g. 宣告Spare matrix (其元素大部分為零的矩陣)
Example via JS
Doubly linked list
left link+data+right link
Tree
- A collection of nodes
- degree == 樹枝
- 可以用於表示
Set
Content:
+ Binary tree
+ Full BT and Complete BT
+ Threaded Binary Trees
+ Binary search tree
+ Selection tree
Binary tree
- The max number of nodes
on level iof a binary tree is2^(i-1),i>=1 - The max number of nodes in a binary tree of
depth kis2^k-1,k>=1 - 性質:
n0(無樹枝的 node) =n2(有兩根樹枝的node) +1 - 用
Array表示: 易找查位置，花較多空間，刪減不易 - 用
Linked list表示：不易找查位置，花費較少空間，易刪減
Full BT and Complete BT
- Full BT: 滿節點的樹
- Complete BT: 由上至下，有左至右編號的樹
Binary Tree Traversals
L(moving left),V(visiting the node),R(moving right)- inorder (LVR), preorder (VLR), postorder (LRV)
- 可以結合 Stack
Threaded Binary Trees
- 讓空指標有意義
- 理論存在，但實際上非常少用
Binary search tree
- == ordered/sorted binary tree
- 必左邊 subtree 小，右邊 subtree 大
用 leftSize 可以找第 k 大的值
AVL Tree
- Balanced binary search tree => 每個 node 都儘量 height-balanced
- Balance factor
BF(T) = hL- hR=> For any node T in an AVL Tree,BF(T) = -1, 0 or 1 - 每一次 insert 都必許符合上述條件 => 一旦不符合會做 LL, LR, RL, RR 調整
Optimal Binary Search Tree (未理解)
- Check the worst case
- 計算 cost 找最小值
- static set: 固定機率
weight= probability 相加
Selection tree
- winner tree, loser tree
- 快速排序用
Priority queue (== Heap)
- Each element has a priority (key)
- Has max (min) priority queue
max heap: key[parent] >= key[children]
min heap: key[parent] <= key[children]- 概念用 tree 表示 (Complete BT) => 實際用 array
- 屬 Complete BT
- delete 從 root 開始 => 刪除從根開始雖然很快，但是要調整其他 node 的位置，所以時間複雜度為 O(log(n))
Max Heapify
- 從 Complete BT 最後的 leaf 的 parent 開始向前修正 (index 直接向前修正)
- Time complexity: O(nlg(n)) =>這裡沒搞懂
Hoffman code
- 字母使用頻率越高，給的編碼愈少 (加速傳遞)
- 用 Tree 儲存
- 使用 priority queue
Graph
請到這篇
Sorting
- Internal Method: The entire sort list can be carried out in the memory
- External Method: 資料太大，記憶體不用夠時使用
Insert sort
- 將第 n 個數字插入 sorted n-1 的隊伍中
Selection sort
- 從 unsorted 的數字中選最小的出來，放進隊伍
Bubble sort
Merge sort
- Recursive algorithm
優點：快、在 external merge sort 可以減少 memory 使用
Quick sort
Heap sort
Algorithm (Increasing order)
Step1: Build min heap
Step2: for(i=0;i<N;i++) deleteMin;缺點：可能需要額外空間 (決定於如何排序)、tree 要花 O(log(n)) 時間被調整
Bucket sort (Radix sort)
- Radix Exchange Sort: 以數字的第 n 個 bit 作為籃子，將 Array 中的數區分大小
- Straight-Radix Sort: 從個位數的 bit 開始，不斷分類
Hash
Hash function
- Simple to compute
- Minimize the number of collisions
- 讓 identifiers 平均的分布進 bucket => uniform hash function
- Mid-square function =>
- Division => 算餘數
- Folding
x = 12320324111220
=>
partition: P1 = 123, P2 = 203, P3 = 241, P4 = 112, P5 = 20
=>
Shift folding: P1 + P2 + P3 + P4 + P5 = 699 == 落在第 699 個 bucket0r Folding at the boundaries
Overflow handling
There are two ways to handle overflow:
- Open addressing (使用新空間)
=> Linear Probing, Quadratic Probing (平方)
- Chaining (不開空間，把資料在同空間串接起來)
=> linked list
Reference
[1] 彭文志教授。資料結構 (2013)