算法設計基礎匯報人：AA2024-01-14算法概述基本算法思想數據結構與算法排序算法查找算法圖論算法算法設計與分析實例目錄01算法概述算法是一組有窮的規則，它們規定了解決某一特定類型問題的一系列運算步驟。確定性、可行性、有窮性、輸入項、輸出項。算法的定義與特性算法特性算法定義基本算法包括排序、查找、數值計算等基礎算法。數據結構相關算法如鏈表、樹、圖等數據結構相關的算法。圖論算法最短路徑、最小生成樹、網絡流等圖論相關算法。動態規劃用于解決最優化問題的一種算法思想。貪心算法每一步都采取當前狀態下最好或最優的選擇，從而希望導致結果是最好或最優的算法。回溯算法一種通過探索所有可能的候選解來找出所有解的算法。算法的分類算法的評價指標空間復雜度可讀性評估算法所需存儲空間隨問題規模增長的變化情況。算法是否易于理解和實現。時間復雜度正確性健壯性評估算法執行時間隨問題規模增長的變化情況。算法是否能正確地解決指定的問題。算法對于異常情況的處理能力和穩定性。02基本算法思想貪心算法是一種在每一步選擇中都采取在當前狀態下最好或最優（即最有利）的選擇，從而希望導致結果是最好或最優的算法。定義活動選擇問題、背包問題、最小生成樹問題等。典型問題局部最優解并不一定能推導出全局最優解，但貪心算法在有最優子結構的問題中尤為有效。特點貪心算法典型問題歸并排序、快速排序、二分搜索等。定義分治算法是一種解決問題的策略，它將一個問題分解成兩個或更多的相同或相似的子問題，再把子問題的解組合起來，以達到解決原問題的目的。特點通過分解問題，降低問題的規模，使問題更容易解決。同時，分治算法通常利用遞歸來實現。分治算法動態規劃是一種在數學、計算機科學和經濟學中使用的，通過把原問題分解為相對簡單的子問題的方式來求解復雜問題的方法。定義背包問題、最長公共子序列、最短路徑問題等。典型問題動態規劃通常用于優化重疊子問題的計算，通過存儲子問題的解，避免重復計算，從而提高算法效率。特點動態規劃定義回溯算法是一種通過探索所有可能的候選解來找出所有解的算法。如果候選解被確認不是一個解的話（或者至少不是最后一個解），回溯算法會通過在上一步進行一些變化來丟棄該解，即“回溯”并嘗試其他可能的解。典型問題八皇后問題、圖的著色問題、旅行商問題等。特點回溯算法是一種基于試錯的搜索算法，它通過逐步構建解決方案，并在不滿足條件時進行回溯，以尋找所有可能的解決方案。回溯算法03數據結構與算法數組鏈表棧隊列線性數據結構與算法連續內存空間，隨機訪問元素，插入和刪除操作需要移動元素。后進先出（LIFO）的數據結構，支持壓棧和彈棧操作。非連續內存空間，通過指針連接元素，插入和刪除操作只需修改指針。先進先出（FIFO）的數據結構，支持入隊和出隊操作。每個節點最多有兩個子節點的樹，通常用于實現二叉搜索樹等。二叉樹堆AVL樹紅黑樹完全二叉樹，滿足堆屬性（父節點值大于或等于/小于或等于子節點值），常用于實現優先隊列。自平衡二叉搜索樹，任何節點的兩個子樹的高度最大差別為1，保證查詢、插入和刪除操作的平衡性。自平衡二叉搜索樹，通過顏色和旋轉規則保證平衡，廣泛應用于各種場景。樹形數據結構與算法最短路徑算法Dijkstra算法和Floyd算法是兩種常用的求解圖中兩點間最短路徑的算法。圖的遍歷深度優先搜索（DFS）和廣度優先搜索（BFS）是兩種常用的圖遍歷算法。鄰接表用鏈表或數組表示圖，每個節點包含與之相連的節點信息。圖由節點（頂點）和邊組成的數據結構，可分為有向圖和無向圖。鄰接矩陣用二維數組表示圖，數組元素表示節點之間的連接關系。圖形數據結構與算法04排序算法將待排序的元素插入到已排序的序列中，從而達到排序的目的。從第一個元素開始，認為該元素已經被排序；取出下一個元素，在已經排序的元素序列中從后向前掃描；如果該元素（已排序）大于新元素，將該元素移到下一位置；重復步驟3，直到找到已排序的元素小于或者等于新元素的位置；將新元素插入到該位置后；重復步驟2~5。最壞情況下是O(n^2)，最好情況下是O(n)，平均時間復雜度是O(n^2)。基本思想實現過程時間復雜度插入排序010203基本思想在未排序序列中找到最小（或最大）元素，存放到排序序列的起始位置，然后再從剩余未排序元素中繼續尋找最小（或最大）元素，然后放到已排序序列的末尾。以此類推，直到所有元素均排序完畢。實現過程首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再從剩余未排序元素中繼續尋找最小（大）元素，然后放到已排序序列的末尾。以此類推，直到所有元素均排序完畢。時間復雜度無論最好最壞情況，時間復雜度均為O(n^2)，空間復雜度為O(1)。選擇排序對相鄰的元素進行兩兩比較，順序相反則進行交換，這樣每一輪過后最小（或最大）的元素就會“浮”到序列的一端。比較相鄰的元素。如果第一個比第二個大，就交換他們兩個；對每一對相鄰元素做同樣的工作，從開始第一對到結尾的最后一對。這步做完后，最后的元素會是最大的數；針對所有的元素重復以上的步驟，除了最后一個；持續每次對越來越少的元素重復上面的步驟，直到沒有任何一對數字需要比較。最好情況為O(n)，最壞和平均情況為O(n^2)。基本思想實現過程時間復雜度冒泡排序通過一趟排序將待排記錄分隔成獨立的兩部分，其中一部分記錄的關鍵字均比另一部分的關鍵字小，則可分別對這兩部分記錄繼續進行排序，以達到整個序列有序。選擇一個基準元素；重新排列數組，所有元素比基準值小的擺放在基準前面，所有元素比基準值大的擺在基準的后面（相同的數可以到任一邊）。在這個分區退出之后，該基準就處于數組的中間位置。這個稱為分區操作；遞歸地（recursive）把小于基準值元素的子數組和大于基準值元素的子數組排序。最好情況為O(nlogn)，最壞情況為O(n^2)，平均情況為O(nlogn)。基本思想實現過程時間復雜度快速排序05查找算法從數據結構的一端開始，順序掃描，直到找到所查元素為止。基本思想適用場景時間復雜度適用于線性表等數據結構，尤其是當數據規模較小或數據無序時。平均時間復雜度和最壞情況下的時間復雜度均為O(n)，其中n為數據結構中元素的個數。030201順序查找基本思想在有序表中，取中間元素作為比較對象，若給定值與中間元素相等，則查找成功；若給定值小于中間元素，則在左半部分繼續查找；若給定值大于中間元素，則在右半部分繼續查找。不斷重復上述過程，直到查找成功或查找區間為空為止。適用場景適用于有序表等數據結構，且要求數據必須采用順序存儲結構。時間復雜度平均時間復雜度和最壞情況下的時間復雜度均為O(logn)，其中n為數據結構中元素的個數。二分查找要點三基本思想通過計算元素的哈希值，將元素映射到哈希表的某個位置進行存儲和查找。哈希查找的核心是設計一個好的哈希函數，使得元素能夠盡可能均勻地分布在哈希表中，以減少沖突和提高查找效率。要點一要點二適用場景適用于需要快速查找和插入的場景，如緩存系統、數據庫索引等。時間復雜度在理想情況下，哈希查找的時間復雜度為O(1)。但在存在哈希沖突的情況下，需要進行沖突處理，此時時間復雜度會上升。常見的沖突處理方法有開放地址法和鏈地址法。要點三哈希查找06圖論算法03Bellman-Ford算法適用于帶負權邊的有向圖，通過對所有邊進行松弛操作求解單源最短路徑問題。01Dijkstra算法適用于沒有負權邊的有向圖，通過貪心策略逐步確定起點到各個頂點的最短路徑。02Floyd算法適用于帶負權邊的有向圖和無向圖，通過動態規劃思想求解任意兩點間的最短路徑。最短路徑算法Kruskal算法按照邊權值從小到大的順序選擇邊，每次選擇一條連接兩個不連通分量的邊加入生成樹，直至生成樹包含所有頂點。Boruvka算法每次選擇當前生成樹中所有頂點與外界頂點中權值最小的邊加入生成樹，直至生成樹包含所有頂點。Prim算法從某一頂點出發，每次選擇當前生成樹與外界頂點中權值最小的邊加入生成樹，直至生成樹包含所有頂點。最小生成樹算法Kahn算法從入度為0的頂點開始，不斷刪除該頂點和以它為起點的有向邊，直至所有頂點都被刪除或發現環。DFS算法通過深度優先搜索遍歷圖中的所有頂點，記錄每個頂點的訪問狀態，根據訪問順序得到拓撲排序結果。拓撲排序算法07算法設計與分析實例問題描述01給定一組物品，每種物品都有自己的重量和價值，背包的總容量有限。如何選擇物品放入背包，使得背包內物品的總價值最大。解決方法02使用動態規劃算法，根據物品的重量和價值，以及背包的容量，構建狀態轉移方程，求解最優解。復雜度分析03時間復雜度為O(NW)，其中N為物品數量，W為背包容量。空間復雜度為O(W)。背包問題問題描述在8x8的國際象棋棋盤上放置8個皇后，使得它們不能互相攻擊。即任何兩個皇后都不能處于同一行、同一列或同一斜線上。解決方法使用回溯算法，從第一行開始逐行放置皇后，每次放置時檢查當前位置是否與已放置的皇后沖突。如果沖突，則回溯到上一行重新放置。復雜度分析時間復雜度為O(N!)，其中N為棋盤大小。空間復