資料結構-堆疊&佇列
考研相關文章參考資料為 wjungle 大神提供的筆記
Stack
具有 LIFO 性質之有序串列,插入元素之操作為 push,刪除元素之操作為 push,且兩者發生於同一端,稱為頂端 (top)
Stack Permutation
給予 nnn 個資料依序 push 進入 stack,並且在過程中可以進行任意合法的 pop 將資料輸出,在此模式下所產生的所有輸出之排列組合
ex: a,b,ca,b,ca,b,c 之 Stack Permutation:
abc, acb, bac, bca, cab, cba
共 5 種
nnn 個資料之 Stack Permutation 個數:
1n+1Cn2n\frac{1}{n + 1}C_{n}^{2n}n+11Cn2n
與下列問題之個數相同 (卡塔蘭數):
nnn 個 nodes 可以形成的不同二元樹個數
nnn 組 “(” 及 “)” 之合法配對個數
(n+1)(n + 1)(n+1) 個 matrix 相乘之所有乘法組合個數
Infix, Postfix, Prefix 轉換
計算題型作法
括 ...
資料結構-時間複雜度
考研相關文章參考資料為 wjungle 大神提供的筆記
漸進式符號
Asymptotic Notations
表示時間函數的成長速率 (growth rate) 等級
符號
OOO
f(n)=O(g(n))f(n) = O(g(n))f(n)=O(g(n)) iff exist two positive constants ccc and n0n_0n0 such that f(n)≤c∗g(n)f(n) \leq c*g(n)f(n)≤c∗g(n), for all n≥n0n \geq n_0n≥n0
視為理論的 Upper-Bound
Ω\OmegaΩ
f(n)=Ω(g(n))f(n) = \Omega(g(n))f(n)=Ω(g(n)) iff exist two positive constants ccc and n0n_0n0 such that f(n)≥c∗g(n)f(n) \geq c*g(n)f(n)≥c∗g(n), for all n≥n0n \geq n_0n≥n0
視為理論的 Lower-Bound
Θ\ThetaΘ
f(n ...
資料結構-陣列&鏈結串列
考研相關文章參考資料為 wjungle 大神提供的筆記
Array 元素之位置
一維陣列
A:array[l...u]A: array[l...u]A:array[l...u] of items
共有 u−l+1u - l + 1u−l+1 格
起始位置: l0l_0l0
元素大小: ddd
A[i]A[i]A[i] 的位置: l0+(i−l)∗dl_0 + (i - l) * dl0+(i−l)∗d
二維陣列
A:array[l1...u1,l2...u2]A: array[l_1...u_1, l_2...u_2]A:array[l1...u1,l2...u2] of items
有 u1−l1+1u_1 - l_1 + 1u1−l1+1 列,u2−l2+1u_2 - l_2 + 1u2−l2+1 行
Row-major
A[i,j]=l0+[(i−l1)∗(u2−l2+1)+(j−l2)]∗dA[i, j] = l_0 + [(i - l_1) * (u_2 - l_2 + 1) + (j - l_2)] * dA[i,j]=l0+[( ...
資料結構-圖
考研相關文章參考資料為 wjungle 大神提供的筆記
Graph
令 G=<V,E>G = <V, E>G=<V,E> 代表圖形是由兩個非空集合組成:
VVV: 代表頂點 (Vertex)
EEE: 代表邊 (Edge)
根據邊的類型,可分為兩類:
Undirected Graph (無向圖)
邊不具有方向性
(i,j)=(j,i)(i,j) = (j,i)(i,j)=(j,i) 代表同一邊
Directed Graph (有向圖)
邊具有方向性
(i,j)≠(j,i)(i,j) \neq (j,i)(i,j)=(j,i)
相關術語
Eulerian cycle (尤拉 cycle)
從某點出發,經過每個邊各一次,又回到原點
充分必要條件: 每個頂點之 degree 為偶數
Eulerian chain
從某點出發,經過每個邊各一次,不一定要回到原點
充分必要條件: 有兩個頂點之 degree 為奇數,剩餘頂點之 degree 為偶數
Hamiltonian Path (漢米爾頓路徑)
從某點出發, ...
資料結構-雜湊
考研相關文章參考資料為 wjungle 大神提供的筆記
Hashing
一種資料儲存與搜尋的機制,當想要存入或取出資料時,先經過 Hashing Function 求出 Hashing Address,接著到 Hash Table 中對應的 Bucket 存入或取出資料 xxx
Hash Table 由 BBB 個 Bucket 組成
每個 Bucket 則由 SSS 個 Slots 組成
每個 Slot 可儲存一筆資料
優點:
資料搜尋前不用經過排序
在沒有 Collision 的情況下,資料搜尋時間為 O(n)O(n)O(n)
Worst case: O(n)O(n)O(n): Hashing Function 為定值
保密性、安全性高
不知道 Hashing Function 則無法存取資料
不可回推
常用於密碼學、資料壓縮
相關術語
Collision 碰撞
不同資料經過 Hashing Function 後得到相同 Hashing Address
Overflow 溢位
Collision 發生後對應的 Bucket 沒有多餘空間 ...
正規語言-L7
正規語言相關文章參考資料為陳穎平教授上課講義
L7 Time Complexity
Measuring Complexity
Definition
Let MMM be a deterministic Turing machine that halts on all inputs. The running time or time complexity of MMM is the function f:N→Nf : N → Nf:N→N , where f(n)f (n)f(n) is the maximum number of steps that MMM uses on any input of length nnn. If f(n)f (n)f(n) is the running time of MMM , we say that MMM runs in time f(n)f (n)f(n) and that MMM is an f(n)f (n)f(n) time Turing machine. Customarily we use nnn to represent the ...
正規語言-L5
正規語言相關文章參考資料為陳穎平教授上課講義
L5 Reducibility
If problem A reduces to problem B, we can use a solution to B to solve A.
When A is reducible to B, solving A cannot be harder than solving B because a solution to B gives a solution to A. Therefore, if A is reducible to B,
B is decidable ⇒ A is decidable;
A is undecidable ⇒ B is undecidable.
Undecidable Problems from Language Theory
定義 HALTTM={⟨M,w⟩ ∣ M is a TM and M halts on input w}HALT_{TM} = \{ ⟨M, w⟩~|~M~is~a~TM~and~M~halts~on~input~w \}HALTTM={⟨ ...
正規語言-L4
正規語言相關文章參考資料為陳穎平教授上課講義
L4 Decidability
Decidable Languages
Decidable Problems Concerning Regular Languages
定義 ADFA={⟨B,w⟩ ∣ B is a DFA that accepts input string w}A_{DFA} = \{ ⟨B, w⟩~|~B~is~a~DFA~that~accepts~input~string~w \}ADFA={⟨B,w⟩ ∣ B is a DFA that accepts input string w}
Theorem
ADFAA_{DFA}ADFA is a decidable language.
證明: 建立一個 TM MMM 模擬 www 在 BBB 上的行為,如果停在 accept states 則 ADFAA_{DFA}ADFA appect,否則會 reject,只有這兩種可能,因此是 Decidable 的
定義 ANFA={⟨B,w⟩ ∣ B is a NFA that accepts input st ...
正規語言-L3
正規語言相關文章參考資料為陳穎平教授上課講義
L3 The Church-Turing Thesis
Turing Machines
圖靈機的想法: Finite control + unlimited and unrestricted memory.
在磁帶上面讀 & 寫
可以將讀取頭向左/右移動
磁帶是無限長的
可以立刻決定拒絕 (Reject) 或接受 (Accept)
Formal Definition of A Turing Machine
Definition
A Turing machine is a 7-tuple (Q,Σ,Γ,δ,q0,qaccept,qreject)(Q, Σ, Γ, δ, q_0, q_{accept}, q_{reject})(Q,Σ,Γ,δ,q0,qaccept,qreject), where Q,Σ,ΓQ, Σ, ΓQ,Σ,Γ are all finite sets and
QQQ is the set of states;
ΣΣΣ is the input alphabet not containing the b ...
正規語言-L2
正規語言相關文章參考資料為陳穎平教授上課講義
L2 Context-Free Languages
Context-Free Grammars
CFGs: 上下文無關文法,指的是字元在進行替換時不需要考慮上下文,其擁有足夠的表現力來表示大多數程式設計語言的語法
Formal Definition of CFGs
Definition
A context-free grammar is a 4-tuple (V,Σ,R,S)(V, Σ, R, S)(V,Σ,R,S), where
VVV is a finite set called the variables;
ΣΣΣ is a finite set, disjoint from VVV ,called the terminals;
RRR is a finite set of rules (or productions), with each rule being a variable and a string of variables and terminals;
S∈VS ∈ VS∈V is the start varia ...









