演算法(A)

2019/07/26 謝碧景(c)編製更新

資 A-V-1 重要資料結構的概念與應用

(一)常見的資料結構 (Data Structure)

1.陣列 (Array) 結構的概念及問題解決的應用。

陣列講義 (C++)

2.堆疊(Stack)：後進先出(LIFO)特性的資料結構。佇列(Queue)：先進先出(FIFO)原則的資料結構。

3.鏈結串列(Linked List)：將物件串接在一起，以利增加或移除物件。

4.樹(Tree)：類似樹木枝幹結構，由節點(Node)與分支(Branch)組成。例：電腦的資料夾結構。

• • 二元樹(Binary Tree)：每個節點最多只有兩個子節點的樹狀結構。

• • 走訪：拜訪樹上的每一個節點

    • 前序走訪 (Pre-order)：根→左→右，例：20→15→4→17→30→32

    • 中序走訪 (in-order)：左→根→右，例：4→15→17→20→30→32

    • 後序走訪 (Post-order)：左→右→根，例：4→17→15→32→30→20

5.圖(Graph)：由數個節點，及連接節點的邊(Edge)組成的資料結構。節點間有邊連接，可構成相鄰矩陣(Adjacency Matrix)，屬於二維陣列中對應的元素就是1，反之為0。

• • • 無向圖 (Undirected Graph)：邊沒有方向性。例：Facebook 交友應用。

    • 有向圖 (Directed Graph)：邊有方向性。例：Instagram 交友應用。

資 A-V-3 演算法效能分析

• • 演算法效能分析：使用『複雜度』(Complexity)評估演算法的效能。【參閱：排序演算法-維基百科】

  • 分為時間和空間兩種評估方式：『時間複雜度』採運算次數，『空間複雜度』即執行過程中需多少儲存空間。