算法基礎知識培訓課件算法概述與分類基本數據結構排序算法查找算法圖論算法動態規劃貪心算法與分治策略contents目錄算法概述與分類01CATALOGUE算法是一系列解決問題的清晰指令，代表著用系統的方法描述解決問題的策略機制。算法定義算法在計算機科學中扮演著核心角色，用于指導計算機如何執行特定任務或解決特定問題。算法作用算法定義及作用輸出項有限性算法必須能在執行有限個步驟之后終止。可行性算法的每一步都必須是可行的，也就是說，每一步都能夠通過執行有限次數完成。輸入項一個算法有0個或多個輸入，以刻畫運算對象的初始情況，所謂0個輸入是指算法本身定出了初始條件。包括排序算法、搜索算法、圖論算法、動態規劃等。基本算法分類確定性算法的每一步驟必須有確切的定義。一個算法有一個或多個輸出，以反映對輸入數據加工后的結果。沒有輸出的算法是毫無意義的。算法分類與特點健壯性當輸入數據不合法時，算法也能做出相關處理，而不是產生異常或莫名其妙的結果。可讀性算法設計的另一目的是為了便于閱讀、理解和交流。正確性算法的正確性是評價一個算法優劣的最重要的標準。時間復雜度評估執行程序所需的時間。可以估算出程序對處理器的使用程度。空間復雜度評估執行程序所需的存儲空間。可以估算出程序對計算機內存的使用程度。算法評價標準基本數據結構02CATALOGUE線性表的定義與性質線性表是一種具有n個元素的有限序列線性表中的數據元素具有相同的類型線性表相鄰元素之間具有前驅和后繼關系線性表的順序存儲結構用一段地址連續的存儲單元依次存儲線性表的數據元素線性表通過數據元素在存儲器中的相對位置來表示數據元素之間的邏輯關系用一組任意的存儲單元存儲線性表的數據元素（這組存儲單元可以是連續的，也可以是不連續的）線性表的鏈式存儲結構通過指針來表示數據元素之間的邏輯關系線性表棧的定義與性質棧是一種特殊的線性表，其插入和刪除操作限定在表的一端進行，該端稱為棧頂，另一端稱為棧底棧與隊列棧中沒有元素時稱為空棧棧具有后進先出（LIFO）的特性隊列的定義與性質棧與隊列隊列是一種特殊的線性表，其插入操作在表的一端進行，而刪除操作在表的另一端進行，插入元素的一端稱為隊尾，刪除元素的一端稱為隊頭棧與隊列隊列中沒有元素時稱為空隊列隊列具有先進先出（FIFO）的特性棧與隊列樹的基本概念與性質樹是一種非線性的數據結構，由n（n>=0）個有限節點組成一個具有層次關系的集合樹中的節點具有父節點、子節點、兄弟節點等概念樹與二叉樹樹的高度、深度、葉子節點、路徑等概念二叉樹的基本概念與性質二叉樹是一種特殊的樹，每個節點最多只有兩個子節點，分別稱為左子節點和右子節點樹與二叉樹二叉樹的五種基本形態空二叉樹、只有一個根節點的二叉樹、只有左子樹或右子樹的二叉樹、具有左右子樹的二叉樹二叉樹的性質第i層上至多有2^(i-1)個節點（i>=1）、深度為k的二叉樹至多有2^k-1個節點（k>=1）等樹與二叉樹123圖的基本概念與性質圖是由頂點的有窮非空集合和頂點之間邊的集合組成，通常表示為G（V,E）圖中的頂點表示對象，邊表示對象之間的關系圖及其應用010204圖及其應用圖中的邊有方向和無方向之分，分別稱為有向圖和無向圖圖的應用場景與實例分析圖論在計算機科學、電子工程、運籌學等領域有著廣泛的應用實例分析：最短路徑問題、最小生成樹問題、拓撲排序問題等03排序算法03CATALOGUE通過相鄰元素之間的比較和交換，使得每一輪比較后最大（或最小）的元素能夠“冒泡”到序列的一端。原理最好情況為O(n)，最壞和平均情況為O(n^2)。時間復雜度O(1)。空間復雜度穩定。穩定性冒泡排序原理時間復雜度空間復雜度穩定性選擇排序01020304每次從未排序的元素中選出最小（或最大）的元素，放到已排序序列的末尾。無論最好、最壞還是平均情況，均為O(n^2)。O(1)。不穩定。原理時間復雜度空間復雜度穩定性插入排序將未排序的元素插入到已排序序列的合適位置中，以達到排序的目的。O(1)。最好情況為O(n)，最壞和平均情況為O(n^2)。穩定。時間復雜度無論最好、最壞還是平均情況，均為O(nlogn)。穩定性穩定。空間復雜度O(n)。原理采用分治策略，將序列不斷拆分為子序列，直到子序列長度為1，然后將相鄰子序列進行歸并排序。歸并排序原理：通過一趟排序將待排序的數據分割成獨立的兩部分，其中一部分的所有數據都比另一部分的所有數據要小，然后再按此方法對這兩部分數據分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數據變成有序序列。時間復雜度：最好情況為O(nlogn)，最壞情況為O(n^2)，平均情況為O(nlogn)。空間復雜度：O(logn)。穩定性：不穩定。快速排序查找算法04CATALOGUE從數據結構的一端開始，順序掃描，直到找到所查元素為止。原理時間復雜度適用場景平均時間復雜度和最壞時間復雜度都是O(n)，其中n是數據結構中元素的數量。適用于數據量較小或數據無序的情況。030201順序查找原理在有序數組中，取中間元素與目標值進行比較，若相等則查找成功；若目標值小于中間元素，則在數組的前半部分繼續查找；若目標值大于中間元素，則在數組的后半部分繼續查找。重復上述過程，直到找到目標值或確定目標值不存在于數組中。時間復雜度平均時間復雜度和最壞時間復雜度都是O(logn)，其中n是數據結構中元素的數量。適用場景適用于數據量較大且數據已排序的情況。二分查找通過哈希函數將元素的關鍵字轉化為數組的索引，然后在對應的數組位置上進行查找。原理平均時間復雜度可以達到O(1)，最壞情況下時間復雜度為O(n)，其中n是哈希表中元素的數量。時間復雜度適用于需要快速查找且元素數量較多的情況。適用場景哈希表查找

樹形查找結構原理利用樹形結構進行查找，常見的樹形查找結構包括二叉搜索樹、平衡二叉樹、B樹、B+樹等。時間復雜度不同的樹形查找結構具有不同的時間復雜度，但通常都可以在O(logn)的時間內完成查找操作，其中n是樹中節點的數量。適用場景適用于需要快速查找且元素數量較多的情況，尤其是當元素之間存在某種特定的排序關系時。圖論算法05CATALOGUE03Bellman-Ford算法適用于有負權邊的有向圖，通過對所有邊進行松弛操作求解最短路徑。01Dijkstra算法適用于沒有負權邊的有向圖，通過貪心策略逐步確定起點到各頂點的最短路徑。02Floyd算法適用于任意有向圖，通過動態規劃思想求解任意兩點間的最短路徑。最短路徑問題適用于稠密圖，通過逐步構建生成樹的方式求解最小生成樹。Prim算法適用于稀疏圖，通過并查集實現邊的合并，求解最小生成樹。Kruskal算法最小生成樹問題適用于有向無環圖（DAG），通過不斷刪除入度為0的頂點并更新相關頂點的入度，最終得到拓撲序列。在拓撲排序的基礎上，計算每個頂點的最早開始時間和最晚開始時間，從而確定關鍵路徑和關鍵活動。拓撲排序與關鍵路徑關鍵路徑拓撲排序網絡流問題最大流問題求解網絡中從源點到匯點的最大可行流量，常用算法包括Ford-Fulkerson算法和Edmonds-Karp算法。最小割問題求解網絡中將源點和匯點分離的最小割集，即最小割容量。最小割容量等于最大流量，是網絡流理論中的基本定理。動態規劃06CATALOGUE原理動態規劃是一種在數學、計算機科學和經濟學中使用的，通過把原問題分解為相對簡單的子問題的方式來求解復雜問題的方法。思想動態規劃算法通常用于優化遞歸問題，如斐波那契數列，或者用于解決具有重疊子問題和最優子結構的問題。動態規劃原理及思想背包問題、最長公共子序列、最短路徑問題等。典型問題從問題的整體出發，逐步細化問題的規模，直到問題的規模縮小到可以直接求解的程度。自頂向下從問題的最小規模開始，逐步擴大問題的規模，直到達到問題的整體規模。自底向上典型問題分析與求解方法完全背包問題與01背包問題類似，但每種物品可以選擇多次。01背包問題給定一組物品，每種物品都有自己的重量和價值，在限定的總重量內，如何選擇物品使得物品的總價值最大。多重背包問題與01背包問題類似，但每種物品有一個數量限制。背包問題及其變形最長公共子序列問題給定兩個序列，找出它們的最長公共子序列。問題描述使用動態規劃算法，構建一個二維數組dp，其中dp[i][j]表示第一個序列的前i個字符與第二個序列的前j個字符的最長公共子序列長度。通過狀態轉移方程dp[i][j]=dp[i-1][j-1]+1(ifs1[i]==s2[j])ormax(dp[i-1][j],dp[i][j-1])(ifs1[i]!=s2[j])來求解。求解方法貪心算法與分治策略07CATALOGUE貪心選擇性質所求問題的整體最優解只由各個子問題的局部最優解組合得到，不需再考慮子問題之間的關系。邊界貪心算法需要明確問題的邊界，即問題的約束條件，以保證貪心選擇的正確性。貪心策略根據問題性質，選擇當前狀態下的最優解，以期望達到全局最優。貪心算法原理及思想通過貪心選擇結束時間最早的活動，求解最多可進行的活動個數。活動選擇問題根據字符出現頻率構建哈夫曼樹，實現最優前綴編碼，達到壓縮數據的目的。哈夫曼編碼問題利用Prim算法或Kruskal算法，根據邊的權值貪心選擇，構建最小生成樹。最小生成樹問題典型問題分析與求解方法分而治之01將原問題分解為若干個規模較小、結構與原問題相似的子問題，遞歸解決子問題，再合并子問題的解決方案，從而達到解決原問題的目的。分解與合并02分治策略的關鍵在于如何合理地將問題分解為子問題，以及如何將子問題的解合并為原問題的解。平衡子問題03為保證分治策略的效率，需要盡量保證分解