30 個重要數據結構和算法完整介紹(建議收藏保存)

數據結構和算法 (DSA)

通常被認為是一個令人生畏的話題——一種常見的誤解。它們是技術領域最具創新性概念的基礎，對于工作/實習申請者和有經驗的程序員的職業發展都至關重要。掌握DSA意味著你能夠使用你的計算和算法思維來解決前所未見的問題，并為任何科技公司的價值做出貢獻（包括你自己的！）。通過了解它們，您可以提高代碼的可維護性、可擴展性和效率。

話雖如此，我決定在CSDN新星計劃挑戰期間將我所了解的數據結構和算法集中起來。本文旨在使 DSA 看起來不像人們認為的那樣令人生畏。它包括 15 個最有用的數據結構和 15 個最重要的算法，可以幫助您在學習中和面試中取得好成績并提高您的編程競爭力。后面等我還會繼續對這些數據結構和算法進行進一步詳細地研究講解。

@TOC

一、數據結構

1. 數組（Arrays）

數組是最簡單也是最常見的數據結構。它們的特點是可以通過索引（位置）輕松訪問元素。

它們是做什么用的？

想象一下有一排劇院椅。每把椅子都分配了一個位置（從左到右），因此每個觀眾都會從他將要坐的椅子上分配一個號碼。這是一個數組。將問題擴展到整個劇院（椅子的行和列），您將擁有一個二維數組（矩陣）！

特性

元素的值按順序放置，并通過從 0 到數組長度的索引訪問；

數組是連續的內存塊；

它們通常由相同類型的元素組成（這取決于編程語言）；

元素的訪問和添加速度很快；搜索和刪除不是在 O(1) 中完成的。

2. 鏈表（Linked Lists）

鏈表是線性數據結構，就像數組一樣。鏈表和數組的主要區別在于鏈表的元素不存儲在連續的內存位置。它由節點組成——實體存儲當前元素的值和下一個元素的地址引用。這樣，元素通過指針鏈接。

它們是做什么用的？

鏈表的一個相關應用是瀏覽器的上一頁和下一頁的實現。雙鏈表是存儲用戶搜索顯示的頁面的完美數據結構。

特性

它們分為三種類型：單獨的、雙重的和圓形的；

元素不存儲在連續的內存塊中；

完美的優秀內存管理（使用指針意味著動態內存使用）；

插入和刪除都很快；訪問和搜索元素是在線性時間內完成的。

3. 堆棧（Stacks）

堆棧是一種抽象數據類型，它形式化了受限訪問集合的概念。該限制遵循 LIFO（后進先出）規則。因此，添加到堆棧中的最后一個元素是您從中刪除的第一個元素。

堆棧可以使用數組或鏈表來實現。

它們是做什么用的？

現實生活中最常見的例子是在食堂中將盤子疊放在一起。位于頂部的板首先被移除。放置在最底部的盤子是在堆棧中保留時間最長的盤子。

堆棧最有用的一種情況是您需要獲取給定元素的相反順序。只需將它們全部推入堆棧，然后彈出它們。

另一個有趣的應用是有效括號問題。給定一串括號，您可以使用堆棧檢查它們是否匹配。

特性

您一次只能訪問最后一個元素（頂部的元素）；

一個缺點是，一旦您從頂部彈出元素以訪問其他元素，它們的值將從堆棧的內存中丟失；

其他元素的訪問是在線性時間內完成的；任何其他操作都在 O(1) 中。

4. 隊列（Queues）

隊列是受限訪問集合中的另一種數據類型，就像前面討論的堆棧一樣。主要區別在于隊列是按照FIFO（先進先出）模型組織的：隊列中第一個插入的元素是第一個被移除的元素。隊列可以使用固定長度的數組、循環數組或鏈表來實現。

它們是做什么用的？

這種抽象數據類型 (ADT) 的最佳用途當然是模擬現實生活中的隊列。例如，在呼叫中心應用程序中，隊列用于保存等待從顧問那里獲得幫助的客戶——這些客戶應該按照他們呼叫的順序獲得幫助。

一種特殊且非常重要的隊列類型是優先級隊列。元素根據與它們關聯的“優先級”被引入隊列：具有最高優先級的元素首先被引入隊列。這個 ADT 在許多圖算法（Dijkstra 算法、BFS、Prim 算法、霍夫曼編碼 - 更多關于它們的信息）中是必不可少的。它是使用堆實現的。

另一種特殊類型的隊列是deque 隊列（雙關語它的發音是“deck”）?？梢詮年犃械膬啥瞬迦?刪除元素。

特性

我們只能直接訪問引入的“最舊”元素；

搜索元素將從隊列的內存中刪除所有訪問過的元素；

彈出/推送元素或獲取隊列的前端是在恒定時間內完成的。搜索是線性的。

5. Map 和 哈希表（Hash Table）

Maps （dictionaries）是包含鍵集合和值集合的抽象數據類型。每個鍵都有一個與之關聯的值。

哈希表是一種特殊類型的映射。它使用散列函數生成一個散列碼，放入一個桶或槽數組：鍵被散列，結果散列指示值的存儲位置。

最常見的散列函數（在眾多散列函數中）是模常數函數。例如，如果常量是 6，則鍵 x 的值是x%6。

理想情況下，散列函數會將每個鍵分配給一個唯一的桶，但他們的大多數設計都采用了不完善的函數，這可能會導致具有相同生成值的鍵之間發生沖突。這種碰撞總是以某種方式適應的。

它們是做什么用的？

Maps 最著名的應用是語言詞典。語言中的每個詞都為其指定了定義。它是使用有序映射實現的（其鍵按字母順序排列）。

通訊錄也是一張Map。每個名字都有一個分配給它的電話號碼。

另一個有用的應用是值的標準化。假設我們要為一天中的每一分鐘（24 小時 = 1440 分鐘）分配一個從 0 到 1439 的索引。哈希函數將為h(x) = x.小時*60+x.分鐘。

特性

鍵是唯一的（沒有重復）；

抗碰撞性：應該很難找到具有相同鍵的兩個不同輸入；

原像阻力：給定值 H，應該很難找到鍵 x，使得h(x)=H；

第二個原像阻力：給定一個鍵和它的值，應該很難找到另一個具有相同值的鍵；

術語：

“map”：Java、C++；

“dictionary”：Python、JavaScript、.NET；

“associative array"：PHP。

因為maps 是使用自平衡紅黑樹實現的（文章后面會解釋），所以所有操作都在 O(log n) 內完成；所有哈希表操作都是常量。

6. 圖表（Graphs）

圖是表示一對兩個集合的非線性數據結構：G={V, E}，其中 V 是頂點（節點）的集合，而 E 是邊（箭頭）的集合。節點是由邊互連的值 - 描述兩個節點之間的依賴關系（有時與成本/距離相關聯）的線。

圖有兩種主要類型：有向圖和無向圖。在無向圖中，邊(x, y)在兩個方向上都可用：(x, y)和(y, x)。在有向圖中，邊(x, y)稱為箭頭，方向由其名稱中頂點的順序給出：箭頭(x, y)與箭頭(y, x) 不同。

它們是做什么用的？

圖是各種類型網絡的基礎：社交網絡（如 weixin、csdn、weibo），甚至是城市街道網絡。社交媒體平臺的每個用戶都是一個包含他/她的所有個人數據的結構——它代表網絡的一個節點。weixin 上的好友關系是無向圖中的邊（因為它是互惠的），而在 CSDN 或 weibo上，帳戶與其關注者/關注帳戶之間的關系是有向圖中的箭頭（非互惠）。

特性

圖論是一個廣闊的領域，但我們將重點介紹一些最知名的概念：

無向圖中節點的度數是它的關聯邊數；

有向圖中節點的內部/外部度數是指向/來自該節點的箭頭的數量；

從節點 x 到節點 y 的鏈是相鄰邊的連續，x 是它的左端，y 是它的右邊；

一個循環是一個鏈，其中 x=y；圖可以是循環/非循環的；如果 V 的任意兩個節點之間存在鏈，則圖是連通的；

可以使用廣度優先搜索 (BFS) 或深度優先搜索 (DFS) 遍歷和處理圖，兩者都在 O(|V|+|E|) 中完成，其中 |S| 是集合S 的基數；查看下面的鏈接，了解圖論中的其他基本信息。

7. 樹（Trees）

一棵樹是一個無向圖，在連通性方面最?。ㄈ绻覀兿粭l邊，圖將不再連接）和在無環方面最大（如果我們添加一條邊，圖將不再是無環的） . 所以任何無環連通無向圖都是一棵樹，但為了簡單起見，我們將有根樹稱為樹。

根是一個固定節點，它確定樹中邊的方向，所以這就是一切“開始”的地方。葉子是樹的終端節點——這就是一切“結束”的地方。

一個頂點的孩子是它下面的事件頂點。一個頂點可以有多個子節點。一個頂點的父節點是它上面的事件頂點——它是唯一的。

它們是做什么用的？

我們在任何需要描繪層次結構的時候都使用樹。我們自己的家譜樹就是一個完美的例子。你最古老的祖先是樹的根。最年輕的一代代表葉子的集合。

樹也可以代表你工作的公司中的上下級關系。這樣您就可以找出誰是您的上級以及您應該管理誰。

特性

根沒有父級；

葉子沒有孩子；

根和節點 x 之間的鏈的長度表示 x 所在的級別；

一棵樹的高度是它的最高層（在我們的例子中是 3）；

最常用的遍歷樹的方法是 O(|V|+|E|) 中的 DFS，但我們也可以使用 BFS；使用 DFS 在任何圖中遍歷的節點的順序形成 DFS 樹，指示我們訪問節點的時間。

8. 二叉樹（Binary Trees）和二叉搜索樹（Binary Search Trees）

二叉樹是一種特殊類型的樹：每個頂點最多可以有兩個子節點。在嚴格二叉樹中，除了葉子之外，每個節點都有兩個孩子。具有 n 層的完整二叉樹具有所有2?-1 個可能的節點。

二叉搜索樹是一棵二叉樹，其中節點的值屬于一個完全有序的集合——任何任意選擇的節點的值都大于左子樹中的所有值，而小于右子樹中的所有值。

它們是做什么用的？

BT 的一項重要應用是邏輯表達式的表示和評估。每個表達式都可以分解為變量/常量和運算符。這種表達式書寫方法稱為逆波蘭表示法 (RPN)。這樣，它們就可以形成一個二叉樹，其中內部節點是運算符，葉子是變量/常量——它被稱為抽象語法樹（AST）。

BST 經常使用，因為它們可以快速搜索鍵屬性。AVL 樹、紅黑樹、有序集和映射是使用 BST 實現的。

特性

BST 有三種類型的 DFS 遍歷：

先序（根、左、右）；

中序（左、根、右）；

后序（左、右、根）；全部在 O(n) 時間內完成；

中序遍歷以升序為我們提供了樹中的所有節點；

最左邊的節點是 BST 中的最小值，最右邊的節點是最大值；

注意 RPN 是 AST 的中序遍歷；

BST 具有排序數組的優點，但有對數插入的缺點——它的所有操作都在 O(log n) 時間內完成。

9. AVL樹（Adelson-Velsky and Landis Trees ）

所有這些類型的樹都是自平衡二叉搜索樹。不同之處在于它們以對數時間平衡高度的方式。

AVL 樹在每次插入/刪除后都是自平衡的，因為節點的左子樹和右子樹的高度之間的模塊差異最大為 1。 AVL 以其發明者的名字命名：Adelson-Velsky 和 Landis。

在紅黑樹中，每個節點存儲一個額外的代表顏色的位，用于確保每次插入/刪除操作后的平衡。

在 Splay 樹中，最近訪問的節點可以快速再次訪問，因此任何操作的攤銷時間復雜度仍然是 O(log n)。

它們是做什么用的？

AVL 似乎是數據庫理論中最好的數據結構。

RBT（紅黑樹） 用于組織可比較的數據片段，例如文本片段或數字。在 Java 8 版本中，HashMap 是使用 RBT 實現的。計算幾何和函數式編程中的數據結構也是用 RBT 構建的。

在 Windows NT 中（在虛擬內存、網絡和文件系統代碼中），Splay 樹用于緩存、內存分配器、垃圾收集器、數據壓縮、繩索（替換用于長文本字符串的字符串）。

特性

ANY自平衡BST中ANY操作的攤銷時間復雜度為O(log n)；

在最壞的情況下，AVL 的最大高度是 1.44 * log2n（為什么？==提示==：考慮所有級別都已滿的 AVL 的情況，除了最后一個只有一個元素）；

AVLs 在實踐中搜索元素是最快的，但是為了自平衡而旋轉子樹的成本很高；

同時，由于沒有旋轉，RBT 提供了更快的插入和刪除；

展開樹不需要存儲任何簿記數據。

10.堆（Heaps）

最小堆是一棵二叉樹，其中每個節點的值都大于或等于其父節點的值：val[par[x]] <= val[x]，具有堆的 xa 節點，其中val[ x]是它的值，par[x] 是它的父級。

還有一個實現相反關系的最大堆。

二叉堆是一棵完整的二叉樹（它的所有層都被填充，除了最后一層）。

它們是做什么用的？

正如我們幾天前討論過的，優先隊列可以使用二叉堆有效地實現，因為它支持 O(log n) 時間內的 insert()、delete()、extractMax() 和 reduceKey() 操作。這樣，堆在圖算法中也是必不可少的（因為優先級隊列）。

任何時候您需要快速訪問最大/最小項目，堆都是最好的選擇。

堆也是堆排序算法的基礎。

特性

它總是平衡的：無論何時我們在結構中刪除/插入一個元素，我們只需要“篩選”/“滲透”它直到它處于正確的位置；

節點k > 1的父節點是[k/2]（其中 [x] 是 x 的整數部分），其子節點是2k和2k+1；

設置優先級隊列的替代方案，ordered_map（在 C++ 中）或任何其他可以輕松允許訪問最小/最大元素的有序結構；

根優先，因此其訪問的時間復雜度為O(1)，插入/刪除在O(log n)中完成；創建一個堆是在 O(n) 中完成的；O(n*log n)中的堆排序。

11.字典樹（Tries）

trie 是一種高效的信息檢索數據結構。也稱為前綴樹，它是一種搜索樹，允許以 O(L) 時間復雜度插入和搜索，其中 L 是鍵的長度。

如果我們將密鑰存儲在一個平衡良好的 BST 中，它將需要與 L * log n 成正比的時間，其中 n 是樹中的密鑰數量。這樣，與 BST 相比，trie 是一種更快的數據結構（使用 O(L)），但代價是 trie 存儲要求。

它們是做什么用的？

樹主要用于存儲字符串及其值。它最酷的應用程序之一是在 Google 搜索欄中鍵入自動完成和自動建議。特里是最好的選擇，因為它是最快的選擇：如果我們不使用特里，更快的搜索比節省的存儲更有價值。

通過在字典中查找單詞或在同一文本中查找該單詞的其他實例，也可以使用 trie 來完成鍵入單詞的正字法自動更正。

特性

它有一個鍵值關聯；鍵通常是一個單詞或它的前綴，但它可以是任何有序列表；

根有一個空字符串作為鍵；

節點值與其子節點值之間的長度差為 1；這樣，根的子節點將存儲長度 為 1 的值；作為結論，我們可以說來自第 k 層的節點 x 具有長度k 的值；

正如我們所說，插入/搜索操作的時間復雜度是 O(L)，其中 L 是鍵的長度，這比 BST 的 O(log n) 快得多，但與哈希表相當；

空間復雜度實際上是一個缺點：O(ALPHABET_SIZE*L*n)。

12. 段樹（Segment Trees）

段樹是一個完整的二叉樹，可以有效地回答查詢，同時仍然可以輕松修改其元素。

給定數組中索引 i 上的每個元素代表一個用[i, i]間隔標記的葉子。將其子節點分別標記為[x, y]或[y, z]的節點將具有[x, z]區間作為標簽。因此，給定 n 個元素（0-indexed），線段樹的根將被標記為[0, n-1]。

它們是做什么用的？

它們在可以使用分而治之（我們將要討論的第一個算法概念）解決的任務中非常有用，并且還可能需要更新其元素。這樣，在更新元素時 ，包含它的任何區間也會被修改，因此復雜度是對數的。例如，n 個給定元素的總和/最大值/最小值是線段樹最常見的應用。如果元素更新正在發生，二分搜索也可以使用段樹。

特性

作為二叉樹，節點 x 將2x和2x+1作為子節點，[x/2]作為父節點，其中[x]是x的整數部分；

更新段樹中整個范圍的一種有效方法稱為“延遲傳播”，它也是在 O(log n) 中完成的（有關操作的實現，請參見下面的鏈接）；

它們可以是 k 維的：例如，有 q 個查詢來查找一個矩陣的給定子矩陣的總和，我們可以使用二維線段樹；

更新元素/范圍需要 O(log n) 時間；對查詢的回答是恒定的(O(1))；

空間復雜度是線性的，這是一個很大的優勢：O(4*n)。

13. 樹狀數組（Fenwick Trees）

fenwick 樹，也稱為二叉索引樹 (BIT)，是一種也用于高效更新和查詢的數據結構。與 Segment Trees 相比，BITs 需要更少的空間并且更容易實現。

它們是做什么用的？

BIT 用于計算前綴和——第 i 個位置的元素的前綴和是從第一個位置到第 i 個元素的總和。它們使用數組表示，其中每個索引都以二進制系統表示。例如，索引 10 相當于十進制系統中的索引 2。

特性

樹的構建是最有趣的部分：首先，數組應該是 1-indexed 要找到節點 x 的父節點，您應該將其索引 x 轉換為二進制系統并翻轉最右邊的有效位；ex.節點 6 的父節點是 4；

6 = 1*22+1*21+0*2? => 1"1"0 (flip) => 100 = 1*22+0*21+0*2? = 4;

最后，ANDing 元素，每個節點都應該包含一個可以添加到前綴和的間隔；

更新的時間復雜度仍然是 O(log n)，查詢的時間復雜度仍然是 O(1)，但空間復雜度與線段樹的 O(4*n) 相比是一個更大的優勢：O(n)。

14. 并查集（Disjoint Set Union）

我們有 n 個元素，每個元素代表一個單獨的集合。并查集 (DSU) 允許我們做兩個操作：

1.UNION — 組合任意兩個集合（或者統一兩個不同元素的集合，如果它們不是來自同一個集合）；

2.FIND — 查找元素來自的集合。

它們是做什么用的？

并查集（DSU） 在圖論中非常重要。您可以檢查兩個頂點是否來自同一個連接組件，或者甚至可以統一兩個連接組件。

讓我們以城市和城鎮為例。由于人口和經濟增長的鄰近城市正在擴張，它們可以輕松創建大都市。因此，兩個城市合并在一起，他們的居民住在同一個大都市。我們還可以通過調用 FIND 函數來檢查一個人居住在哪個城市。

特性

它們用樹表示；一旦兩組組合在一起，兩個根中的一個成為主根，另一個根的父代是另一棵樹的葉子之一；

一種實用的優化是通過高度壓縮樹木；這樣，聯合由最大的樹組成，以輕松更新它們的兩個數據（參見下面的實現）；

所有操作都在 O(1) 時間內完成。

15. 最小生成樹（Minimum Spanning Trees）

給定一個連通圖和無向圖，該圖的生成樹是一個子圖，它是一棵樹并將所有節點連接在一起。單個圖可以有許多不同的生成樹。加權、連通和無向圖的最小生成樹 (MST) 是權重（成本）小于或等于其他所有生成樹權重的生成樹。生成樹的權重是賦予生成樹每條邊的權重之和。

它們是做什么用的？

最小生成樹（MST ）問題是一個優化問題，一個最小成本問題。有了路線網，我們可以認為影響n個城市之間建立國道的因素之一是相鄰兩個城市之間的最小距離。

國家路線就是這樣，由道路網絡圖的 MST 表示。

特性

作為一棵樹，具有 n 個頂點的圖的 MST 具有 n-1 條邊；可以使用以下方法解決：

Prim 算法 — 密集圖的最佳選擇（具有 n 個節點且邊數接近n(n-1)/2)的圖）；

Kruskal 算法——主要使用；它是一種基于不相交集聯合的貪心算法（我們后面也將討論它）；

構建它的時間復雜度對于 Kruskal 來說是 O(n log n) 或 O(n log m)（這取決于圖），對于 Prim 來說是 O(n2)。

二、算法

1.分治算法（Divide and Conquer）

分而治之（DAC）本身并不是一個特定的算法，而是在深入研究其他主題之前需要了解的重要算法類別。它用于解決可以劃分為與原始問題相似但規模較小的子問題的問題。然后 DAC 遞歸地求解它們，最后合并結果以找到問題的解決方案。

它分為三個階段：

劃分——將問題分解為子問題；

用遞歸解決子問題；

合并——子問題的結果到最終解決方案中。

它是干什么用的？

分治算法（DAC） 的一種實際應用是使用多個處理器進行并行編程，因此子問題在不同的機器上執行。

DAC 是許多算法的基礎，例如快速排序、合并排序、二分搜索或快速乘法算法。

特性

每個 DAC 問題都可以寫成一個遞推關系；因此，必須找到停止遞歸的基本情況；

它的復雜度是T(n)=D(n)+C(n)+M(n)，這意味著每個階段都有不同的復雜度，具體取決于問題。

2. 排序算法（Sorting Algorithms）

排序算法用于根據元素上的比較運算符重新排列給定元素（來自數組或列表）。當我們提到一個排序數組時，我們通常會想到升序（比較運算符是“<”）。排序有多種類型，具有不同的時間和空間復雜度。其中一些是基于比較的，有些則不是。以下是最流行/最有效的排序方法：

冒泡排序（Bubble Sort）

冒泡排序是最簡單的排序算法之一。它基于相鄰元素之間的重復交換（如果它們的順序錯誤）。它是穩定的，它的時間復雜度是 O(n2) 并且它需要 O(1) 輔助空間。

計數排序（Counting Sort）

計數排序不是基于比較的排序。它基本上是使用每個元素的頻率（一種散列），確定最小值和最大值，然后在它們之間迭代以根據其頻率放置每個元素。它在 O(n) 中完成，空間與數據范圍成正比。如果輸入范圍不明顯大于元素數量，則它是有效的。

快速排序（Quick Sort）

快速排序是分而治之的一個應用。它基于選擇一個元素作為樞軸（第一個、最后一個或中間值），然后交換元素以將樞軸放置在所有小于它的元素和所有大于它的元素之間。它沒有額外的空間和 O(n*log n) 時間復雜度——基于比較的方法的最佳復雜度。

歸并排序（Merge Sort）

歸并排序也是一個分而治之的應用程序。它將數組分成兩半，對每一半進行排序，然后合并它們。它的時間復雜度也是 O(n*log n)，所以它也像 Quick Sort 一樣超快，但不幸的是它需要 O(n) 額外空間來同時存儲兩個子數組，最后合并它們。

基數排序（Radix Sort）

基數排序使用計數排序作為子程序，因此它不是基于比較的算法。我們怎么知道CS是不夠的？假設我們必須對[1, n2] 中的元素進行排序。使用 CS，我們需要 O(n2)。我們需要一個線性算法——O(n+k)，其中元素在[1, k]范圍內。它從最不重要的一個（單位）開始，到最重要的（十、百等）對元素進行逐位排序。額外空間（來自 CS）：O(n)。

3. 搜索算法（Searching Algorithms）

搜索算法旨在檢查數據結構中元素的存在，甚至返回它。有幾種搜索方法，但這里是最受歡迎的兩種：

線性搜索（Linear Search）

該算法的方法非常簡單：您從數據結構的第一個索引開始搜索您的值。您將它們一一比較，直到您的值和當前元素相等。如果該特定值不在 DS 中，則返回 -1。

時間復雜度：O(n)

二分查找（Binary Search）

BS 是一種基于分而治之的高效搜索算法。不幸的是，它只適用于排序的數據結構。作為一種 DAC 方法，您連續將 DS 分成兩半，并將搜索中的值與中間元素的值進行比較。如果它們相等，則搜索結束。無論哪種方式，如果您的值大于/小于它，搜索應該繼續在右/左半部分。

時間復雜度：O(log n)

4. 埃氏篩法（Sieve of Eratosthenes）

給定一個整數 n，打印所有小于或等于 n 的素數。

Eratosthenes 篩法是解決這個問題的最有效的算法之一，它完美地適用于小于10.000.000 的n 。

該方法使用頻率列表/映射來標記[0, n]范圍內每個數字的素數：如果 x 是素數，則ok[x]=0，否則ok[x]=1。

我們開始從列表中選擇每個素數，并用 1 標記列表中的倍數——這樣，我們選擇未標記的 (0) 數。最后，我們可以在 O(1) 中輕松回答任意數量的查詢。

經典算法在許多應用中都是必不可少的，但我們可以進行一些優化。首先，我們很容易注意到 2 是唯一的偶素數，因此我們可以單獨檢查它的倍數，然后在范圍內迭代以找到從 2 到 2 的素數。其次，很明顯，對于數字 x，我們之前在迭代 2、3 等時已經檢查了 2x、3x、4x 等。這樣，我們的乘數檢查 for 循環每次都可以從 x2 開始。最后，即使這些倍數中有一半是偶數，而且我們也在迭代奇素數，因此我們可以在倍數檢查循環中輕松地從 2x 迭代到 2x。

空間復雜度：O(n)

時間復雜度：O(n*log(log n)) 用于經典算法，O(n) 用于優化算法。

5. 字符串匹配算法（Knuth-Morris-Pratt）

給定長度為 n 的文本和長度為 m 的模式，找出文本中所有出現的模式。

Knuth-Morris-Pratt 算法 (KMP) 是解決模式匹配問題的有效方法。

天真的解決方案基于使用“滑動窗口”，每次設置新的起始索引時，我們都會比較字符與字符，從文本的索引 0 開始到索引 nm。這樣，時間復雜度是 O(m*(n-m+1))~O(n*m)。

KMP 是對樸素解決方案的優化：它在 O(n) 中完成，并且當模式具有許多重復的子模式時效果最佳。因此，它也使用滑動窗口，但不是將所有字符與子字符串進行比較，而是不斷尋找當前子模式的最長后綴，這也是它的前綴。換句話說，每當我們在某些匹配后檢測到不匹配時，我們就已經知道下一個窗口文本中的某些字符。因此，再次匹配它們是沒有用的，因此我們重新開始匹配文本中具有該前綴后的字符的相同字符。我們怎么知道我們應該跳過多少個字符？好吧，我們應該構建一個預處理數組，告訴我們應該跳過多少個字符。

6.貪婪算法（Greedy）

Greedy 方法多用于需要優化且局部最優解導致全局最優解的問題。

也就是說，當使用 Greedy 時，每一步的最優解都會導致整體最優解。然而，在大多數情況下，我們在一個步驟中做出的決定會影響下一步的決定列表。在這種情況下，必須用數學方法證明算法。Greedy 也會在一些數學問題上產生很好的解決方案，但不是全部（可能無法保證最佳解決方案）！

貪心算法通常有五個組成部分：

候選集——從中創建解決方案；

選擇函數——選擇最佳候選人；

可行性函數——可以確定候選人是否能夠為解決方案做出貢獻；

一個目標函數——將候選人分配給（部分）解決方案；

一個解決方案函數——從部分解決方案構建解決方案。

分數背包問題

給定n個物品的重量和價值，我們需要將這些物品放入容量為W的背包中，以獲得背包中的最大總價值（允許取件物品：一件物品的價值與其重量成正比）。

貪心方法的基本思想是根據它們的價值/重量比對所有項目進行排序。然后，我們可以添加盡可能多的整個項目。當我們發現一件比背包中剩余重量 (w1) 重 (w2) 的物品時，我們將對其進行分割：僅取出w2-w1以最大化我們的利潤。保證這個貪心的解決方案是正確的。

7. 動態規劃（Dynamic Programming）

動態規劃 (DP) 是一種類似于分而治之的方法。它還將問題分解為類似的子問題，但它們實際上是重疊和相互依賴的——它們不是獨立解決的。

每個子問題的結果都可以在以后隨時使用，它是使用記憶（預先計算）構建的。DP 主要用于（時間和空間）優化，它基于尋找循環。

DP 應用包括斐波那契數列、河內塔、Roy-Floyd-Warshall、Dijkstra 等。 下面我們將討論 0-1 背包問題的 DP 解決方案。

0–1 背包問題

給定n個物品的重量和價值，我們需要將這些物品放入容量為W的背包中，以獲得背包中的最大總值（不允許像貪婪解決方案中的那樣分割物品）。

0-1 屬性是由我們應該選擇整個項目或根本不選擇它的事實給出的。

我們構建了一個 DP 結構作為矩陣dp[i][cw]存儲我們通過選擇總權重為 cw 的 i 個對象可以獲得的最大利潤。很容易注意到我們應該首先用v[i]初始化dp[1][w[i] ]，其中w[i]是第 i 個對象的權重，v[i] 是它的值。

復現如下：

dp[i][cw] = max(dp[i-1][cw], dp[i-1][cw-w[i]]+v[i])

我們稍微分析一下。

dp[i-1][cw]描述了我們沒有在背包中添加當前物品的情況。dp[i-1][cw-w[i]]+v[i]就是我們添加item的情況。話雖如此，dp[i-1][cw-w[i]]是采用 i-1 個元素的最大利潤：所以它們的重量是當前重量，沒有我們的物品重量。最后，我們將項目的值添加到它。

答案存入dp[n][W]. 通過一個簡單的觀察進行優化：在循環中，當前行僅受前一行的影響。因此，將DP結構存儲到矩陣中是不必要的，因此我們應該選擇一個空間復雜度更好的數組：O(n)。時間復雜度：O(n*W)。

8. 最長公共子序列（Longest Common Subsequence）

給定兩個序列，找出它們中存在的最長子序列的長度。子序列是以相同的相對順序出現的序列，但不一定是連續的。例如，“bcd”、“abdg”、“c”都是“abcdefg”的子序列。

這是動態規劃的另一個應用。LCS 算法使用 DP 來解決上述問題。

實際的子問題是要分別從序列 A 中的索引 i 開始，分別從序列 B 中的索引 j 中找到最長公共子序列。

接下來，我們將構建 DP 結構lcs[ ][ ]（矩陣），其中lcs[i][j]是從 A 中的索引 i 開始，分別是 B 中的索引 j 的公共子序列的最大長度。我們將以自頂向下的方式構建它。顯然，解決方案存儲在lcs[n][m] 中，其中 n 是 A 的長度，m 是 B 的長度。

遞推關系非常簡單直觀。為簡單起見，我們將考慮兩個序列都是 1 索引的。首先，我們將初始化lcs[i][0] , 1<=i<=n和lcs[0][j] , 1<=j<=m , 0, 作為基本情況（沒有從 0 開始的子序列）。然后，我們將考慮兩種主要情況：如果A[i]等于B[j]，則lcs[i][j] = lcs[i-1][j-1]+1（比之前的 LCS 多一個相同的字符）。否則，它將是lcs[i-1][j]（如果不考慮A[i]）和lcs[i][j-1]（如果不考慮B[j]）之間的最大值）。

時間復雜度：O(n*m)

附加空間：O(n*m)

9. 最長遞增子序列（Longest Increasing Subsequence）

給定一個包含 n 個元素的序列 A，找到最長子序列的長度，使其所有元素按遞增順序排序。子序列是以相同的相對順序出現的序列，但不一定是連續的。例如，“bcd”、“abdg”、“c”是“abcdefg”的子序列。

LIS 是另一個可以使用動態規劃解決的經典問題。

使用數組l[ ]作為 DP 結構來尋找遞增子序列的最大長度，其中l[i]是包含A[i]的遞增子序列的最大長度，其元素來自[A[i] ], ..., A[n]] 子序列。l[i]為 1，如果A[i]之后的所有元素比它小。否則，在 A[i] 之后大于它的所有元素之間的最大值為 1+。顯然，l[n]=1，其中 n 是 A 的長度。 實現是自底向上的（從末尾開始）。

在搜索當前元素之后的所有元素之間的最大值時出現了一個優化問題。我們能做的最好的事情是二分搜索最大元素。

為了找到現在已知的最大長度的子序列，我們只需要使用一個額外的數組ind[]，它存儲每個最大值的索引。

時間復雜度：O(n*log n)

附加空間：O(n)

10.凸包算法（Convex Hull）

給定同一平面中的一組 n 個點，找到包含所有給定點（位于多邊形內部或其邊上）的最小面積凸多邊形。這種多邊形稱為凸包。凸包問題是一個經典的幾何，在現實生活中有很多應用。例如，碰撞避免：如果汽車的凸包避免碰撞，那么汽車也能避免碰撞。路徑的計算是使用汽車的凸表示完成的。形狀分析也是在凸包的幫助下完成的。這樣，圖像處理很容易通過匹配模型的凸缺陷樹來完成。

有一些算法用于尋找凸包，如 Jarvis 算法、Graham 掃描等。今天我們將討論 Graham 掃描和一些有用的優化。

格雷厄姆掃描按極角對點進行排序——由某個點和其他選定點確定的線的斜率。然后用一個棧來存儲當前時刻的凸包。當一個點 x 被壓入堆棧時，其他點會被彈出堆棧，直到 x 與最后兩個點所確定的線形成小于 180° 的角度。最后，引入堆棧的最后一個點關閉多邊形。由于排序，這種方法的時間復雜度為 O(n*log n)。但是，這種方法在計算斜率時會產生精度誤差。

一種改進的解決方案具有相同的時間復雜度，但誤差較小，按坐標（x，然后是 y）對點進行排序。然后我們考慮由最左邊和最右邊的點形成的線，并將問題分為兩個子問題。最后，我們在這條線的每一邊找到了凸包。所有給定點的凸包是兩個包的重聚。

11. 圖遍歷（Graph Traversals）

遍歷圖的問題是指以特定順序訪問所有節點，通常沿途計算其他有用信息。

廣度優先搜索（Breadth-First Search）

廣度優先搜索 (BFS) 算法是確定圖是否連通的最常用方法之一——或者換句話說，查找 BFS 源節點的連通分量。

BFS 還用于計算源節點和所有其他節點之間的最短距離。BFS 的另一個版本是 Lee 算法，用于計算網格中兩個單元格之間的最短路徑。

該算法首先訪問源節點，然后訪問將被推入隊列的鄰居。隊列中的第一個元素被彈出。我們將訪問它的所有鄰居，并將之前未訪問的鄰居推入隊列。重復該過程直到隊列為空。當隊列為空時，表示所有可達頂點都已訪問完畢，算法結束。

深度優先搜索（Depth-First Search）

深度優先搜索 (DFS) 算法是另一種常見的遍歷方法。在檢查圖形的連通性時，它實際上是最好的選擇。

首先，我們訪問根節點并將其壓入堆棧。雖然堆棧不為空，但我們檢查頂部的節點。如果該節點有未訪問的鄰居，則選擇其中一個并將其壓入堆棧。否則，如果它的所有鄰居都被訪問過，我們就會彈出這個節點。當堆棧變空時，算法結束。

經過這樣的遍歷，就形成了一個DFS樹。DFS 樹有很多應用；最常見的一種是存儲每個節點的“開始”和“結束”時間——它進入堆棧的時刻，分別是它從堆棧中彈出的時刻。

12. 弗洛依德算法（Floyd-Warshall）

Floyd-Warshall / Roy-Floyd 算法解決了所有對最短路徑問題：找到給定邊加權有向圖中每對頂點之間的最短距離。

FW 是一個動態規劃應用程序。DP 結構（矩陣）dist[ ][ ]用輸入圖矩陣初始化。然后我們將每個頂點視為其他兩個節點之間的中間體。最短路徑在每兩對節點之間更新，任何節點 k 作為中間頂點。如果 k 是 i 和 j 之間排序路徑中的中間值，則dist[i][j]成為dist[i][k]+dist[k][j]和dist[i][j]之間的最大值。

時間復雜度：O(n3)

空間復雜度：O(n2)

13. Dijkstra 算法和 Bellman-Ford 算法

迪杰斯特拉（Dijkstra） 算法

給定一個圖和圖中的一個源頂點，找出從源到給定圖中所有頂點的最短路徑。

Dijkstra 算法用于在加權圖中找到這樣的路徑，其中所有的權重都是正的。

Dijkstra 是一種貪心算法，它使用以源節點為根的最短路徑樹（SPT）。SPT 是一種自平衡二叉樹，但該算法可以使用堆（或優先級隊列）來實現。我們將討論堆解決方案，因為它的時間復雜度是 O(|E|*log |V|)。這個想法是使用圖形的鄰接列表表示。這樣，節點將使用 BFS （廣度優先搜索）在 O(|V|+|E|) 時間內遍歷。

所有頂點都用 BFS 遍歷，那些最短距離尚未最終確定的頂點被存儲到最小堆（優先隊列）中。

創建最小堆并將每個節點連同它們的距離值一起推入其中。然后，源成為距離為 0 的堆的根。其他節點將無限分配為距離。當堆不為空時，我們提取最小距離值節點 x。對于與 x 相鄰的每個頂點 y，我們檢查 y 是否在最小堆中。在這種情況下，如果距離值大于 (x, y) 的權重加上 x 的距離值，那么我們更新 y 的距離值。

貝爾曼-福特（Bellman-Ford）算法

正如我們之前所說，Dijkstra 僅適用于正加權圖。貝爾曼解決了這個問題。給定一個加權圖，我們可以檢查它是否包含負循環。如果沒有，那么我們還可以找到從我們的源到其他源的最小距離（可能為負權重）。

Bellman-Ford 非常適合分布式系統，盡管它的時間復雜度是 O(|V| |E|)。

我們初始化一個 dist[] 就像在 Dijkstra 中一樣。對于 *|V|-1次，對于每個(x, y)邊，如果dist[y] > dist[x] + (x, y) 的權重，那么我們用它更新dist[y]。

我們重復最后一步以可能找到負循環。這個想法是，如果沒有負循環，最后一步保證最小距離。如果有任何節點在當前步驟中的距離比上一步中的距離短，則檢測到負循環。

14.克魯斯卡爾算法（Kruskal’s Algorithm）

我們之前已經討論過什么是最小生成樹。

有兩種算法可以找到圖的 MST：Prim（適用于密集圖）和 Kruskal（適用于大多數圖）。現在我們將討論 Kruskal 算法。

Kruskal 開發了一種貪心算法來尋找 MST。它在稀有圖上很有效，因為它的時間復雜度是 O(|E|*log |V|)。

該算法的方法如下：我們按權重的遞增順序對所有邊進行排序。然后，選取最小的邊。如果它不與當前 MST 形成循環，我們將其包括在內。否則，丟棄它。重復最后一步，直到 MST 中有 |V|-1 條邊。

將邊包含到 MST 中是使用 Disjoint-Set-Union 完成的，這也在前面討論過。

15. 拓撲排序（Topological Sorting）

有向無環圖 (DAG) 只是一個不包含循環的有向圖。

DAG 中的拓撲排序是頂點的線性排序，使得對于每個拱形(x, y)，節點 x 出現在節點 y 之前。

顯然，拓撲排序中的第一個頂點是一個入度為 0 的頂點（沒有拱形指向它）。

另一個特殊屬性是 DAG 沒有唯一的拓撲排序。

BFS （廣度優先搜索）實現遵循此例程：找到一個入度為 0 的節點并將第一個推入排序。該頂點已從圖中刪除。由于新圖也是一個 DAG，我們可以重復這個過程。

在 DFS 期間的任何時候，節點都可以屬于以下三個類別之一：

我們完成訪問的節點（從堆棧中彈出）；

當前在堆棧上的節點；

尚未發現的節點。

如果在 DAG 中的 DFS 期間，節點 x 具有到節點 y 的輸出邊，則 y 屬于第一類或第三類。如果 y 在堆棧上，則(x, y)將結束一個循環，這與 DAG 定義相矛盾。

這個屬性實際上告訴我們一個頂點在它的所有傳出鄰居都被彈出后從堆棧中彈出。因此，要對圖進行拓撲排序，我們需要跟蹤彈出頂點的逆序列表。

哇，你已經到讀了文章的結尾。感謝您的閱覽！文章篇幅較長，如果有些出錯的地方還請大家批評指正，可在評論區留言或者私信我。

數據結構

版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。

版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。