Nicholas Blogger
0%

發表於 Disqus：
文章字數： 1.2k 所需閱讀時間 ≈ 2 分鐘

通常在針對某一問題開發程式時，都會經過下列步驟：

  1. 明確定義問題
  2. 設計演算法，並評估其執行效率
  3. 撰寫程式，並加以測試
    閱讀全文 »

發表於 Disqus：
文章字數： 2.3k 所需閱讀時間 ≈ 4 分鐘
  • 若要在系統中表示一個圖形，需要儲存兩個集合：
    • 圖形的頂點 ( Vertices )
    • 圖形的邊 （ Edges or arcs )
  • 常用的表示方式：
    • Adjacency Matrix ( 相鄰矩陣 )
    • Adjacency List ( 相鄰串列 )
    • Multiple Adjacency List ( 相鄰多元串列 )
    • Index Array ( 索引陣列 )
      閱讀全文 »

發表於 Disqus：
文章字數： 2.8k 所需閱讀時間 ≈ 5 分鐘

前言

m-way Search Tree 雖利用增大 Tree 的 Degree 來降低 Search Tree 的高度，以減少 Disk I/O 的次數，但若此 Tree 不平衡，也可能會變相地增加 Disk I/O 的次數

  • 因此發展出 B-tree of order m

定義

是一個 Balanced m-way search tree。可以為空，若不為空，則滿足：

  • Root 至少有 2 個 Childs ( Root: 2 ≤ degree ≤ m)
  • 除了 Root 及 Failure Node 之外，其餘 Node 的分支度介於 ⎡m/2⎤ 及 m 之間 (⎡m/2⎤ ≤ degree ≤ m)
  • 所有的 Failure Node 皆位於同一 Level。(即：所有葉子節點位於同一 Level)
    閱讀全文 »

發表於 Disqus：
文章字數： 1k 所需閱讀時間 ≈ 2 分鐘

前言： 外部搜尋 (External Search)

m-way Search Tree 主要用於外部搜尋 (External Search)

  • 先前的樹状搜尋方法皆為內部搜尋 (Internal Search)( B.S.T.和 AVL )
  • Internal Search:
    • 資料量少 ，可以一次全部置於 Memory 中進行 search 之工作
  • External Search:
    • 資料量大 ，無法一次全置於 Memory 中，須藉助輔助儲存體( E.g. Disk )，進行分段 search 之工作
閱讀全文 »

發表於 Disqus：
文章字數： 1.3k 所需閱讀時間 ≈ 2 分鐘

前言 ： Binary Search Tree 的效益

  • 當 B.S.T. 建立之後，可以用來搜尋資料。因此，由平均比較次數來決定其效益
    • 若平均比較次數愈低，則效益愈高
  • 例：
    • 成功搜尋的平均比較次數：
  • 結論： 不考慮加權値或加權値皆相同的情形下
    • 愈平衡的 Binary Search Tree，其平均比較次數愈小，Big-O ≈ O (log n)
    • 愈偏斜的 Binary Search Tree，其平均比較次數愈大，Big-O ≈ O (n)
  • 在靜態的環境下，一般 Binary Search Tree 的建構方法可以有較充裕的時間將欲搜尋的所有資料建構成較平衡的 Binary Search Tree，以提升後續資料搜尋時的效率
  • 然而，若是在動態的環境下，資料可以隨時 Insert / Delete。此時，一般 Binary Search Tree 的建構方法會産生 Skewed Binary Tree，導致資料搜尋的效率變差 (即：O (n))
  • ∴ 面對動態資料，需要 AVL Tree 讓 Tree 的高度均維持在高度平衡的情況
    閱讀全文 »

發表於 Disqus：
文章字數： 2k 所需閱讀時間 ≈ 4 分鐘

具有 External Node 的 B.T. 稱之

  • 一個二元樹具有 n 個節點，若以 Link List 表示，則會有 n+1 條空 Link，在這些空 Link 上加上特定節點，稱為 External Node (或 Failure Node)，其餘 Nodes 稱 Internal Nodes
  • 外部節點數 = 內部節點數 + 1 ( 2n – (n - 1) = n + 1 )
  • 為何外部節點又被稱為失敗節點？
    • 以二元搜尋樹的角度來説，若搜尋到外部節點時，代表在原本的二元樹中找不到想要的資料，也就是搜尋失敗
閱讀全文 »

發表於 Disqus：
文章字數： 2.3k 所需閱讀時間 ≈ 4 分鐘
  • 目的：
    • 圖形中的所有頂點都被拜訪到，且僅被拜訪到一次
  • 拜訪方式有兩種：
    • Depth First Search (DFS；深先搜尋，需利用 Stack)
    • Breadth First Search (BFS；廣先搜尋，需利用 Queue)
  • 應用：

發表於 Disqus：
文章字數： 1.7k 所需閱讀時間 ≈ 3 分鐘

一個圖形(Graph) 是由頂點集合 V 與邊集合 E 所組成，表示如下： G (V, E)

閱讀全文 »

發表於 Disqus：
文章字數： 6.6k 所需閱讀時間 ≈ 12 分鐘
  • Binary Tree 為具有 ≥ 0 個 nodes 所構成的有限集合
    • Binary Tree可以為空的樹
    • 若不為空的樹，則具有 Root 及左, 右子樹，且左, 右子樹亦是 Binary Tree
      閱讀全文 »