戀上數據結構演算法圖解

『壹』 <演算法圖解>

二分查找、大O分析法；數組和鏈表；遞歸、快速排序；分治、動態規劃、貪婪演算法；散列表（鍵值對組成的數據結構）；圖演算法（模擬網路的方法）：廣度優先搜索、迪傑斯特拉演算法（計算網路中兩點之間最短距離）；K近鄰（KNN，用於創建推薦系統、OCR引擎、預測股價、物件分類）。

二分查找的時間復雜度為log2n，多少個2相乘等於n。

有序數組，定義low和high，非一個元素，猜中，大了，小了。

選擇排序：o(n方)，快速排序：o(nlogn)，存儲最小的值，存儲最小元素的索引，找出最小的值，加到新數組中。

循環，程序的性能更好，遞歸，程序更容易理解。棧有兩種操作：壓入和彈出。

每個遞歸函數都有兩部分：基線條件和遞歸條件，遞歸條件指的是函數調用自己，基線條件指的是函數不再調用自己，避免無限循環。

編程概念，調用棧，計算機在內部使用被稱為調用棧的棧，遞歸是調用自己的函數。

調用棧可能佔用大量內存，解決方案是編寫循環代碼，或者使用尾遞歸，但並非所有的語言都支持尾遞歸。

分治-遞歸式問題解決辦法：步驟：找出基線條件，確定如何縮小問題的規模，使其符合基線條件。

涉及數組的遞歸函數，基線條件通常是數組為空或只包含一個元素。

快速排序-D&C演算法：步驟：設置基線條件，數組小於2，選擇基準值，將數組分成兩個子數組：小於和大於基準值的元素，對這兩個子數組進行快速排序，遞歸調用。

合並排序：o(nlogn)，快速排序：o(nlogn)：層數o(logn)乘每層需要的時間o(n)，但最差情況為o(n方)。

散列表-基本數據結構之一：內部機制：實現、沖突、散列函數。

散列表無序，數據結構：數組、列表、（棧、不能用於查找）、散列表（包含額外邏輯）。

數組和鏈表都直接映射到內存，但散列表使用散列函數來確定元素存儲位置。

散列函數：不同的輸入映射到不同的索引，輸出不同的數字，散列表是散列函數和數組的結合，也稱散列映射、映射、字典、關聯數組。

緩存的數據存儲在散列表中，訪問頁面時，先檢查散列表是否存儲了頁面。

如果兩個鍵映射到了同一個位置引發沖突，可以在這個位置存儲一個鏈表，好的散列函數可以減少沖突。

填裝因子為散列表元素/位置總數，因子越低，發生沖突的可能性越小，性能越高。

廣度優先搜索（BFS）的含義：解決最短路徑問題的演算法。

步驟：使用圖來建立問題模型，使用廣度優先搜索演算法（是否有路徑，哪個路徑最短）。

所有演算法中，圖演算法是最有用的。

隊列（數據結構）：類似於棧，不能隨機訪問隊列中元素，只支持入隊和出隊（壓入和彈出），先加入的先出隊，即先進先出（FIFO），而棧是後進先出（LIFO）。

有向圖：關系是單向的，無向圖：沒有箭頭，直接相連的節點互為鄰居。

拓撲排序：根據圖創建一個有序列表。

迪傑斯特拉演算法：適用於加權圖（提高或降低某些邊的權重），找出加權圖中的最短路徑。

只適用於有向無環圖，如果有負權邊，不能使用迪傑斯特拉演算法，因為演算法假設處理過的節點，沒有前往終點的最短路徑，故，有負權邊的可用貝爾曼-福特演算法。

在未處理的節點找到開銷最小的節點，遍歷當前節點的所有鄰居，如果經當前節點前往該鄰居更近，就更新鄰居開銷，同時將該鄰居的父節點設置為當前節點，將當前節點標記為處理過，找出接下來要處理的節點，並循環。

貪婪演算法：每步都選擇局部最優解，最終就是全局最優解，易於實現，運行快，是個不錯的近似演算法。

集合類似於列表，但是不包含重復的元素。

貪婪演算法：o(n方)，NP完全問題：需要計算所有的解，從中選出最小距離，計算量大，最佳做法是使用近似演算法。

動態規劃：約定條件下找到最優解，在問題可分解為彼此獨立且離散的子問題時，就可使用動態規劃來解決。

動態規劃解決方案涉及網路，每個單元格都是子問題，需考慮如何將問題分解為子問題。

最長公共序列。

K最近鄰演算法（KNN）：電影推薦系統。

特徵抽取：指標打分，計算距離（相似程度），N維。

KNN的基本工作：分類和回歸。

應用：OCR光學字元識別（optical character recognition），提取線段、點、曲線特徵，找出與新圖像最近的鄰居；語音識別，人臉識別。

垃圾郵件過濾器：樸素貝葉斯分類器。

二叉查找樹（binary search tree）：有序樹狀數據結構。

二叉查找樹插入和刪除操作快於有序數組，但不能隨機訪問（沒有索引）。

紅黑樹是處於平衡狀態的特殊二叉樹，不平衡時，如向右傾斜時性能不佳。

B樹是一種特殊的二叉樹。

反向索引：一個散列表，將單詞映射到包含他的頁面，常用於創建搜索引擎。

並行演算法：速度的提升非線性，因為並行性管理開銷和負載均衡。

分布式演算法：特殊的並行演算法，maprece（映射和歸並函數），映射：任務多時自動分配多台計算機完成，將一個數組轉換成另一個數組，歸並是將一個數組轉換成一個元素。

線性規劃：在給定約束條件下最大限度的改善指定指標，使用simplex演算法，圖演算法為線性規劃子集。

『貳』 【圖解】數據結構代碼領背-折半插入排序

【視覺解讀】深入剖析：折半插入排序的代碼實踐與理解</

折半插入排序，巧妙地將數組劃分為有序與無序兩部分，其核心思想是利用折半查找的高效性，尋找待插入元素的精確位置。相較於直接插入排序，它在比較次數上有所優化，但移動元素的次數並未減少，整體時間復雜度依然保持在O(n^2)。讓我們通過一個生動示例來揭秘這一演算法的運作機制。