演算法(A)
2019/07/26 謝碧景(c)編製更新
二元搜尋樹(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 交友應用。
(一)演算法簡介
演算法(Algorithm):將解決問題的方法以系列的步驟與流程表達出,則為演算法,常用有排序(Sort)、搜尋(Search)、遞迴(Recursive)等。
表示法:以流程圖(Flowchart) 簡單的圖案、符號記錄解決問題的步驟,參閱: fChart 程式設計工具。
(二)解題策略
暴力法(Brute Force):將所有可能情形列出,再從中找出答案,缺點:較沒效率。
貪心法(Greedy Method):又稱貪婪演算法(Greedy Algorithm),選當下最有利方式,再決定下一步驟,缺點:有時候並無法達成全局最佳解。 講義範例【參閱:貪婪演算法-維基百科】。
分治法(Divide and Conquer):又稱各個擊破法,將問題拆成一個個小問題,各個擊破後,再將小問題的解答合併與統整為答案。是很多高效演算法的基礎,如排序演算法中快速排序、合併排序。【參閱:範例圖】
(三)常見的演算法
資 A-V-3 演算法效能分析
演算法效能分析:使用『複雜度』(Complexity)評估演算法的效能。【參閱:排序演算法-維基百科】
分為時間和空間兩種評估方式:『時間複雜度』採運算次數,『空間複雜度』即執行過程中需多少儲存空間。