演算法(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)：每個節點最多只有兩個子節點的樹狀結構。

    • 二元搜尋樹(Binary Search 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-2 重要演算法的概念與應用

(一)演算法簡介

  • 演算法(Algorithm)：將解決問題的方法以系列的步驟與流程表達出，則為演算法，常用有排序(Sort)、搜尋(Search)、遞迴(Recursive)等。

    • 表示法：以流程圖(Flowchart) 簡單的圖案、符號記錄解決問題的步驟，參閱： fChart 程式設計工具。

(二)解題策略

    • 暴力法(Brute Force)：將所有可能情形列出，再從中找出答案，缺點：較沒效率。

    • 貪心法(Greedy Method)：又稱貪婪演算法(Greedy Algorithm)，選當下最有利方式，再決定下一步驟，缺點：有時候並無法達成全局最佳解。 講義範例【參閱：貪婪演算法-維基百科】。

    • 分治法(Divide and Conquer)：又稱各個擊破法，將問題拆成一個個小問題，各個擊破後，再將小問題的解答合併與統整為答案。是很多高效演算法的基礎，如排序演算法中快速排序、合併排序。【參閱：範例圖】

(三)常見的演算法

  • 搜尋：常用方式有循序搜尋及二分搜尋，循序搜尋是依序逐一搜尋，方法簡單但較沒效率，而二分搜尋可提升速度，但搜尋前資料必須先由小至大排序好。 講義範例

  • 遞迴；函數本身呼叫自己的函數即為遞迴，撰寫時函式中必須有結束點否則程式會形成無窮迴圈造成錯誤。 講義範例

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

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

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