Installation Guide 官方網站：PaddleOCR、CUDA Doucument 1.安裝 CUDA 10.2 需要 Visual Studio C++套件 2.下載(需要註冊)安裝 CUDNN 7.6+(GPU) 覆蓋 CUDA 資料夾並將路徑加入環境變數 Path (參考網頁中範例)，並重新開機

Reference : Fundamentals of Data Structures in C, 2/e Tree Tree Tree Transformation M-way Search Tree Splay Tree Red-Black Tree AVL Tree

[TOC] Heap Tree - 堆積樹 $Heap$ 是一顆 $Complete\ Binay\ Tree$ 最適合當作 $Piority\ Queue$ 所有 $Parent$ 皆 $\geq$ 或 $\leq$ $Child$

--- title: 'M-way Search Tree' disqus: hackmd --- [TOC] ## M-way Search Tree * **Def：** Degree $>$ 2，每個 Node 有 m 個 Degree 、 m-1 個 Data * 在實際應用上，二元搜尋樹因為每個 Node 只能儲存一筆 Data 所以只要資料量一多就會使高度過大 * 為解決高度問題我們要增加每個 Node 裡面的資料，相對的 Links 數量也會增加 * 在 BT 中大的放左、小的放右，而在 M-way ST 中同樣依照 Node 裡 Data 的值域來做區分，如圖所示 (4-Way)  --- ### 性質 * 設高度 k 起始點為 1，根據 BT 該 Level 最大 Nodes = $2^{k-1}$ 在 M-way Tree 裡 設 Degree = m ，該 Level 最大 Nodes 則為 $m^{k-1}$ * 整顆 Tree 最大 Nodes =

--- title: 'Symmetric Min-Max Heap' disqus: hackmd --- [TOC] ## Symmetric Min-Max Heap (SMMH) > [color=#34d2db] **Def：(此為新版的SMMH)** > 1. 本身是 Complete Binary Tree > 2. Root 無 Data > 3. 任意 Node 之 Left Child Data $\leq$ Right Child Data > 4. 任意 Node 之 > * Left Subtree (左子樹) 為 Min - Heap > * Right Subtree (右子樹) 為 Max - Heap > 5. 任意兄弟關係中 Left sibling (左兄弟) $\leq$ Right sibling (右兄弟) > ```graphviz graph graphname{ 1 [label=""] 2 [label="4"] 3 [label="80"]

--- title: 'Min-Max Heap' disqus: hackmd --- [TOC] ## Min-Max Heap > [color=#34d2db] **Def：** > 1. 是 Complete Binary Tree > 2. Level 依序由 Min/Max Heap 交互出現 > 3. Root 在 Min Level > 4. 某 Node x 在 Min Level，代表以 x 為 Root 的 Tree 中，x 是最小值 > (同理 Max Level)  * 此樹就是由 Min Heap 與 Max Heap 互相交疊形成 * 再次提醒，定義 3 有提到 Root 必須為 Min Level 的值 --- ### Insertion - 插入 * 依照 Complete Binary Tree 性質，插入 Node 2  * 此時 Node 2 你不知道他

--- title: 'Thread Binary Tree' disqus: hackmd --- [TOC] # Threaded Binary Tree - 引線二元樹 * 根據 [Binary Tree - Linked List](https://hackmd.io/jALze7TIS6a9A_LYNoVidA#Linked-List) 有 $n+1$ 條 Link 未使用 而在該缺點提到的：對於Leaf Link 的作法，**引線二元樹** 就是其中一個 * 我們將利用這 $n+1$ 條 Link 指向同一棵樹裡的其它 Node * 規則將依照 [Binary Tree Traversal](https://hackmd.io/jALze7TIS6a9A_LYNoVidA#Binary-Tree-Traversal) 的 **Inorder (中序)** 性質來規定 ![](https://upload.wikimedia.org/wikipedia/commons/thumb/7/7a/Threaded_tree.svg/1200px-Threaded_tr

--- title: 'Search - 搜尋' disqus: hackmd --- [TOC] ## Search - 搜尋 * 搜尋方式 * Internal Searching (內部搜尋)：可將資料一次置於 RAM * External Searching (外部搜尋)：需透過 Disk 協助存取資料 * 資料狀態 * Static (靜態)：資料固定 * Dynamic (動態)：更動頻繁、無法預知 --- ### Linear Search - 線性搜尋 * 不須事先排序 :::warning **Time Complexity：** 設有 n 筆資料，平均次數為：第 1 次搜尋成功 + 第 2 次搜尋成功 + ... 第 n 次搜尋成功 ＝ $\dfrac{(1+n)n}{2}*\dfrac{1}{n}=O(n)$ ::: --- ### Binary Search - 二分搜尋 * 須事先排序 * 資料必須可以 Direct Access、Random File :::warning **Time Complexit

--- title: 'Fibonacci Heap - 費式堆積' disqus: hackmd --- [TOC] ## Fibonacci Heap - 費式堆積 (DS.) * 先備知識：[Binomial Heap - 二項式堆積](https://hackmd.io/tCv57gtkQJGQxGM3TMo5aA?both#Binomial-Heap---%E4%BA%8C%E9%A0%85%E5%BC%8F%E5%A0%86%E7%A9%8D-Algo)，若以下操作手法相同將不重複解釋 * `Merge - 合併` * `Pointer：min` :::danger 費式堆積只要 Height 相同即可合併 ::: * **Def：** * 是 Extended Binomial Heap * 與 Binomial Heap 操作相似，但結構並不嚴謹 * | | Binomial Heap | Fibonacci Heap | | -------- | -------- | ----

--- title: 'Binomial Heap - 二項式堆積' disqus: hackmd --- [TOC] ## Binomial Heap - 二項式堆積 (Algo.) * **Def：** 1. 此堆積是由 Degree 0 的樹依序堆積下去 2. Degree 為 0 的二項樹只有一個 Root 3. Root 下有 $k$ 個 Child，每個 Child ==Degree==分別為 $k-1,k-2,...,2,1,0$ 4. 可將二項樹視為 Height 從 0 開始的樹，其 $Nodes = 2^k$ (即為前一棵的 $2$ 倍) 5. 高度或 Degree 為 $k$ 的二項樹，它在 Height 為 h 層 Max Nodes 為 $\left(\begin{array}{ccc}k\\h\end{array}\right)$ 6. Degree 為 $k$ 的二項樹可從兩顆 Degree 為 $k-1$ 的二項樹合併：把其中一棵作為另一顆的 Leftmost Child (合併的基礎

--- title: 'Splay Tree' disqus: hackmd --- [TOC] ## Splay Tree - 伸展樹 * **Def** * 是一種能夠自我平衡的二元搜尋樹，它能在均攤 $O(log_n)$ 的時間內完成基於伸展（Splay）操作 假設想對一個 BST 執行一系列的尋找操作，為了使整個尋找時間更小， 被查頻率高的那些 $Node$ 就應該在靠近樹根的位置。 因此 $Splay\ Tree$ 被發明出來，它會沿著從某個節點到樹根之間的路徑，通過一系列的旋轉把這個節點搬移到樹根去。 它的優勢在於不需要記錄用於平衡樹的冗餘資訊。 * 與 Binary Tree 差異：最差時間下的操作都能保持在 $O(log_n)$ * 唯一導致 Splay Tree 產生最差時間 $O(n)$ 的是以 `非遞減順序` 操作資料 :::success 非遞減順序：1,2,3,4,4,5... :::  ---

--- title: 'Red-Black Tree' disqus: hackmd --- [TOC] ## Red-Black Tree * **Def** 1. 本身是一顆 Balanced Binary Search Tree 2. Node 的顏色非紅及黑 3. Root、Null 為黑色 4. 每個紅色 Node 都有兩個黑色 Nodes 5. 任意 Node 到每個 Leaf 經過的黑 Nodes 皆一樣多 (RBT 的 Balanced 定義)  <br><br> * 用紅黑樹的原因：在 BST 中最佳的搜尋時間為 $O(log_2n)$，最差為 $O(n)$， 假設 n = 128 最佳時間為：7 ，相差了數十倍之遠 * 而在紅黑樹中利用 **紅色** 及 **黑色**

--- title: 'AVL Tree' disqus: hackmd --- [TOC] ## AVL Tree * 在 BST 裡最佳時間為 $O(log_2n)$ 最差時間為 $O(n)$ 相距甚遠， 此章所探討正是為了使 $BST$ 能夠穩定的成長方法 使用高度平衡 $(Height\ Balanced)$： 使得最差情況下仍然是 $O(log_2n)$ * $BST\ +\ Heighted\ Balanced\ = AVL\ Tree$ **Def：** 1. 是一顆 $Height\ Balanced\ Binary\ Search\ Tree$ ( 高度平衡二元搜尋樹 ) 2. 任意 $Node$ 之 $Left\ Subtree$ 與 $Right\ Subtree$ 高度差：左子樹高度 $-$ 右子樹高度為 $-1,0,1$，也就是說 $|H_L-H_R|\leq 1$ 3. 因為是 $BST$ 所以記得以 $Root$ 為基準的值，大小會在不同邊  --- ### Un

--- title: 'Extended Binary Tree' disqus: hackmd --- [TOC] ## Extended Binary Tree - 延伸二元樹 * 在一般的 Binary Tree 中 Leaf 的 Link 為 Null，而我們將指向 Null 改成指向一種 Node 稱做： 1. 紅色 Node：External Node ( Failure Node ) 外部節點 (失敗節點) 3. 藍色 Node：內部節點 (Internal Node) * 另一版本定義 External Node = Leaf，Internal Node = Non-Leaf ```graphviz graph graphname{ 1 [label="1" color=blue] 2 [label="2" color=blue] 3 [label="3" color=blue] 4 [label="4" shape=s style=dashed color=red] 5

--- title: 'Binary Tree' disqus: hackmd --- [TOC] Binary Tree === * 又稱為 Knuth Tree , Ordered Tree * 有限集合，**可以為空** * 若非空則由 左子樹、右子樹 構成 * 每個 Node 之 Degree：0~2 * 子樹 有**次序**之分 #### 次序 1. 子樹 B,C 在 Tree 中視為相同 2. 在 Binary Tree 中視為不同  --- ## Difference with Tree | | Tree | Binary Tree | |:------:|:-----------:|:------:| | 可否為空 | $No$ , 至少一樹根 | $Yes$ | | $Node Degree$ (存在 $Root$ 時) | $\geq 0$ | $0,1,2$ | --- ## Three Theories of Binary Tr

--- title: 'Tree' disqus: hackmd --- --- 索引 [TOC] --- Tree === * 由至少 1 個 Node 構成之集合，**不可為空** * 其餘 Nodes 分成 T~1~ ~ T~m~ **互斥集合** (各自也是一棵樹A,B,C) * Binary Tree 是 Tree 的一種，請不要搞混 ```graphviz digraph graphname{ 1 [label="Root"]; 2 [label="A"]; 3 [label="B"]; 4 [label="D"]; 5 [label="E"]; 6 [label="F"]; 7 [label="G"]; 8 [label="H"]; 9 [label="C"]; 1 -> 2 [label=" T1", fontcolor=red] 1 -> 3 [label=" T2", fontcolor=red] 1 -> 9 [label=" T3", fon

--- title: '6-1 圖的種類及術語' disqus: hackmd --- [TOC] ## 連通圖 Connected Graph **Def：** 設 $G=(V,E)$ 為一個無向圖 **(Undirected Graph)** $∀x,y∈V，x≠y$，點集 $V$ 中任兩相異點之間==皆有一條 $walk$== 可以到達==彼此== 否則稱 $G$ 為 不連通圖 **(Disconnected Graph)**  右圖中.$(5,4)$ $(0,1,2,3)$ 不存在無向 $walk$ 可到達彼此 --- ### 強連通圖 Strongly Connected Graph **Def：** 設 $G=(V,E)$ 為一個有向圖 **(Directed Graph)** $∀x,y∈V，x≠y$，點集 $V$ 中任兩相異點之間==皆有一條有向 $walk$== 可以到達==彼此==  右圖中 $2$ 不存在有向 $

--- title: 'Tree Transformation' disqus: hackmd --- [TOC] --- # Tree Transformation * 此章節的內容是將以下三種樹做彼此之間的轉換，並無任何程式相關的東西，不需要的可略過此節 * **Tree** * **LC-RS Binary Tree** * **Forest** --- ## Tree to LC-RS Binary Tree * LC-RS 為 Left-child Right-sibling 的縮寫，是將 K-ary(K元) Tree 轉換成 Binary Tree 的一種方法，轉換的過程又稱作 [Knuth](https://en.wikipedia.org/wiki/Donald_Knuth) Transform * 依照中文的字面意思就是，**左兒子、右兄弟** 此也是我們轉換的核心所在 ![](https://upload.wikimedia.org/wikipedia/commons/thumb/c/cd/N-ary_to_binar

--- title: 'OCW CH8 - Memory Management' disqus: hackmd --- [TOC] # Memory Management ## Address Binding * 位址定位 (Address Binding) 決定程式的起始位置： 在程式編譯 (Compile) 後，符號化的地址(參數、函數)因為存取的記憶體位置可能不是連續的。 * 所以之後的鏈結器 (Linker) 或載入器 (Loder) 可能會將他們重行定址，把地址連結(bind) 至絕對地址(absoulte address)、即實際上在 Memory 的位置。 * 與記憶體位置的連結(bind)至絕對地址的時間點，可以在以下任何步驟完成。 --- ### 編譯時期 (Compile time) * 若編譯期間知道 process 會在記憶體何處，則產生==絕對碼(Absolute object code)==。 * 在 Linkage Editor 時將程式所用的函數，鏈結到程式碼區段。 * 而之後的 Loader 我們稱作他為 Absolute Loader，