算法查找目錄

1. 基礎數據結構

數組與鏈表
- 動態數組
  - 實現與自動擴容機制
  - 均攤分析
  - ArrayList/Vector實現
- 單向鏈表
  - 基本操作(插入、刪除、查找)
  - 鏈表反轉
  - 環檢測(Floyd判圈算法)
- 雙向鏈表
  - 插入刪除操作優化
  - 雙向遍歷優勢
  - 邊界情況處理
- 循環鏈表
  - 約瑟夫環問題
  - 單向循環鏈表
  - 雙向循環鏈表
- 跳表
  - 基本原理與實現
  - 概率分析
  - 與平衡樹的對比
棧與隊列
- 棧的實現與應用
  - 數組實現棧
  - 鏈表實現棧
  - 表達式求值
  - 括號匹配
  - 函數調用棧模擬
- 隊列的實現與應用
  - 數組實現隊列
  - 鏈表實現隊列
  - 循環隊列
  - 廣度優先搜索應用
- 雙端隊列
  - 雙端隊列實現技巧
  - 應用場景
  - 滑動窗口算法
- 優先隊列
  - 基于堆的實現
  - 基于有序數組的實現
  - 事件調度應用
樹結構
- 二叉樹
  - 樹的遍歷(前序、中序、后序、層序)
  - 遞歸與迭代實現
  - Morris遍歷
  - 二叉樹序列化與反序列化
- 二叉搜索樹
  - 插入、查找、刪除操作
  - 高度分析
  - 中序遍歷的有序性
  - 二叉搜索樹重構
- AVL樹
  - 平衡因子
  - 左旋與右旋
  - 插入和刪除的再平衡
  - 與紅黑樹的對比
- 紅黑樹
  - 五條性質
  - 插入操作與調整
  - 刪除操作與調整
  - 應用案例
- B樹/B+樹
  - B樹的定義與性質
  - B+樹的改進
  - 插入與分裂
  - 刪除與合并
  - 數據庫索引應用
- 線段樹
  - 構建線段樹
  - 區間查詢
  - 區間更新
  - 懶惰傳播
  - 區間最值、區間和應用
- 樹狀數組(Binary Indexed Tree/Fenwick Tree)
  - 原理與實現
  - 單點更新與區間查詢
  - 區間更新實現
  - 二維樹狀數組
- Trie樹(前綴樹)
  - 字典實現
  - 字符串檢索
  - 前綴統計
  - 壓縮前綴樹
- 后綴樹
  - 構建方法
  - 字符串匹配應用
  - 與后綴數組關系
- 區間樹(Interval Tree)
  - 區間重疊查詢
  - 與線段樹的區別
- 四叉樹/八叉樹
  - 空間劃分
  - 圖像處理應用
- 自平衡二叉搜索樹變種
  - 伸展樹(Splay Tree)
  - 替罪羊樹(Scapegoat Tree)
  - 樹堆(Treap)
堆
- 二叉堆
  - 最大堆/最小堆
  - 堆化(Heapify)
  - 上浮與下沉操作
  - 堆排序
- 斐波那契堆
  - 可合并堆操作
  - 漸進復雜度分析
  - 與二叉堆對比
- 左偏堆
  - 可合并堆實現
  - 左偏性質維護
- 配對堆
  - 基本操作
  - 復雜度分析
- d-堆
  - 多叉堆實現
  - 應用場景
哈希表
- 哈希函數
  - 除法哈希法
  - 乘法哈希法
  - 全域哈希
  - 密碼學哈希函數
- 沖突解決
  - 開放尋址法
    - 線性探測
    - 二次探測
    - 雙重哈希
  - 鏈地址法
    - 簡單鏈表
    - 平衡樹
  - Robin Hood哈希
  - 布谷鳥哈希
- 動態擴容與縮容
  - 負載因子
  - 漸進式重哈希
- 完美哈希
  - 靜態數據集優化
- 一致性哈希
  - 哈希環
  - 虛擬節點
  - 分布式緩存應用
- 布隆過濾器
  - 空間效率
  - 誤判率分析
  - 計數布隆過濾器
圖
- 圖的表示
  - 鄰接矩陣
    - 稠密圖優勢
    - 空間復雜度
  - 鄰接表
    - 稀疏圖優勢
    - 出邊快速訪問
  - 十字鏈表
    - 有向圖優化
    - 入邊出邊同等訪問
  - 多重鄰接表
    - 無向圖優化
    - 邊的快速刪除
  - 邊集數組
    - 簡單實現
    - Kruskal算法應用
- 特殊圖結構
  - 星形圖
  - 網格圖
  - 完全圖
  - 二部圖
  - DAG(有向無環圖)
緩存結構與替換策略
- 基本緩存策略
  - LRU (最近最少使用)
    - 雙向鏈表+哈希表實現
    - O(1)時間復雜度操作
  - LFU (最不經常使用)
    - 頻率統計實現
    - O(1)時間復雜度優化
  - FIFO (先進先出)
    - 隊列實現
    - 簡單性與局限性
  - Clock算法
    - 二次機會法
    - 循環鏈表實現
- 高級緩存策略
  - ARC (自適應替換緩存)
    - LRU與LFU的結合
    - 自適應調整
  - W-TinyLFU
    - 窗口TinyLFU
    - 頻率估計器
    - 布隆過濾器應用
  - 2Q緩存
    - 多級隊列設計
    - 冷熱數據分離
  - LIRS (低訪問頻率驅逐)
    - 重用距離概念
    - 實現細節
  - CLOCK-Pro
    - Clock改進版
    - 冷熱數據識別
- 分布式緩存
  - 一致性哈希在緩存中的應用
  - 緩存同步策略
  - 緩存穿透/擊穿/雪崩解決方案
- 多級緩存體系
  - 層次化緩存設計
  - CPU緩存、內存、磁盤層次

2. 搜索算法

基本搜索
- 線性搜索
  - 無序數據搜索
  - 最壞時間復雜度
  - 平均時間復雜度
- 二分搜索
  - 有序數據前提
  - 迭代與遞歸實現
  - 邊界條件處理
  - 變種(查找第一個/最后一個等于給定值)
- 插值搜索
  - 均勻分布數據優化
  - 時間復雜度分析
- 跳躍搜索
  - 分塊搜索
  - 最優塊大小
- 斐波那契搜索
  - 黃金分割思想
  - 與二分查找對比
- 指數搜索
  - 無界數組搜索
  - 時間復雜度分析
樹搜索算法
- 深度優先搜索(DFS)
  - 遞歸實現
  - 迭代實現(棧)
  - 回溯與剪枝
  - 空間復雜度分析
- 廣度優先搜索(BFS)
  - 隊列實現
  - 層次遍歷
  - 最短路徑應用
  - 空間復雜度分析
- 雙向搜索
  - 從起點和終點同時搜索
  - 空間優化
  - 應用場景
- 啟發式搜索
  - 最佳優先搜索
  - 貪婪最佳優先搜索
- A*搜索
  - 啟發函數設計
  - 曼哈頓/歐幾里得距離
  - 完備性與最優性證明
  - 改進版本(IDA*, SMA*)
- Alpha-Beta剪枝
  - 極小極大算法優化
  - 博弈樹搜索
  - 剪枝效率分析
- 蒙特卡洛樹搜索
  - 四個階段(選擇、擴展、模擬、回傳)
  - UCB(上置信界)算法
  - 圍棋AI應用
- 迭代深化搜索
  - 深度限制DFS
  - 空間優化
  - IDDFS(迭代加深DFS)
- 模式搜索
  - Bloom過濾器應用
  - 近似字符串匹配
圖搜索算法的應用
- 迷宮求解
- 八數碼/十五數碼問題
- 掃雷游戲AI
- 棋類游戲搜索

3. 排序算法

基本排序
- 冒泡排序
  - 基本實現
  - 優化(提前終止)
  - 穩定性分析
- 選擇排序
  - 基本實現
  - 不穩定性分析
  - 空間復雜度優勢
- 插入排序
  - 基本實現
  - 對小數據量/近乎有序數據的高效性
  - 穩定性分析
  - 二分插入排序優化
- 希爾排序
  - 增量序列選擇
  - 與插入排序關系
  - 不穩定性分析
高效排序
- 歸并排序
  - 分治思想
  - 遞歸實現
  - 迭代實現
  - 原地歸并優化
  - 穩定性分析
- 快速排序
  - 基本實現
  - 主元選擇優化(三數取中法)
  - 尾遞歸優化
  - 三路快排
  - 不穩定性分析
- 堆排序
  - 構建堆過程
  - 時間復雜度分析
  - 不穩定性分析
  - 原地排序特性
- 計數排序
  - 適用條件
  - 穩定性實現
  - 空間復雜度分析
- 桶排序
  - 桶的數量選擇
  - 桶內排序算法
  - 均勻分布效率分析
- 基數排序
  - LSD與MSD方法
  - 適用數據類型
  - 時間復雜度分析
特殊排序
- 外部排序
  - 多路歸并
  - 敗者樹
  - 置換-選擇算法
  - 多階段合并
- TimSort
  - 自然排序段識別
  - minrun選擇
  - galloping模式
  - 歸并優化
- 內省排序(IntroSort)
  - 快排、堆排、插入排序結合
  - 深度限制機制
  - 實際應用(C++標準庫)
- 拓撲排序
  - 基于DFS實現
  - 基于入度的實現(Kahn算法)
  - 環檢測
  - 多解問題
- 偏序關系排序
- 混合排序策略
  - Timsort原理
  - 適應性排序算法設計
排序算法分析與比較
- 時間復雜度對比
- 空間復雜度對比
- 穩定性對比
- 適用場景分析
- 緩存友好性分析

4. 圖論算法

圖的表示與基礎操作
- 鄰接矩陣表示
- 鄰接表表示
- 十字鏈表表示
- 圖的遍歷
  - 深度優先遍歷
  - 廣度優先遍歷
最短路徑
- 單源最短路徑
  - Dijkstra算法
    - 樸素實現
    - 優先隊列優化
    - 適用條件(無負權)
  - Bellman-Ford算法
    - 基本實現
    - 隊列優化(SPFA)
    - 負環檢測
  - 0-1 BFS(雙端隊列BFS)
    - 權值為0或1的圖
    - 時間復雜度優勢
- 全源最短路徑
  - Floyd-Warshall算法
    - 動態規劃思想
    - 路徑重建
    - 時空復雜度分析
  - Johnson算法
    - 結合Bellman-Ford與Dijkstra
    - 適用于稀疏圖
    - 復雜度分析
  - A*算法
    - 啟發函數設計
    - 完備性與最優性
    - 應用場景
最小生成樹
- Prim算法
  - 樸素實現
  - 優先隊列優化
  - 適用于稠密圖
- Kruskal算法
  - 并查集實現
  - 適用于稀疏圖
- Bor?vka算法
  - 并行實現潛力
  - 歷史意義
- 次小生成樹
- 度限制生成樹
網絡流
- 基本概念
  - 流網絡
  - 殘存網絡
  - 割
- 最大流
  - Ford-Fulkerson算法
    - 增廣路徑方法
    - 收斂條件
  - Edmonds-Karp算法
    - BFS尋找增廣路
    - 復雜度改進
  - Dinic算法
    - 層次圖概念
    - 多路增廣
    - 復雜度分析
  - 推送-重標記算法
    - 基本操作
    - 全局重標記優化
    - FIFO實現
  - MPM算法
- 最小費用最大流
  - 費用流概念
  - 消圈算法
  - 結合最短路的SSP算法
- 應用
  - 二分圖最大匹配
  - 項目選擇問題
  - 最大密度子圖
匹配
- 二分圖匹配
  - 匈牙利算法
    - 交替路實現
    - DFS與BFS版本
  - Hopcroft-Karp算法
    - 多路增廣
    - 復雜度優勢
- 一般圖匹配
  - 帶花樹算法(Blossom Algorithm)
  - 帶權匹配
- 穩定婚姻問題
  - Gale-Shapley算法
  - 最優性與公平性
  - 應用(醫院分配問題)
- 最大權二分匹配
  - KM算法(Kuhn-Munkres)
  - 匈牙利算法擴展
強連通分量
- Kosaraju算法
  - 兩次DFS技巧
  - 時間復雜度分析
- Tarjan算法
  - 單次DFS實現
  - 低連接值概念
  - 棧應用
- Gabow算法
- 強連通分量應用
  - 縮點
  - 2-SAT問題
割點與橋
- Tarjan算法識別割點
- Tarjan算法識別割邊(橋)
- 雙連通分量
- 邊雙連通分量
二分圖
- 二分圖判定
- 二分圖最大匹配
- 二分圖最大權匹配
- 二分圖最小點覆蓋
- 二分圖最大獨立集
- K?nig定理
其他圖算法
- 歐拉路徑/回路
  - Fleury算法
  - Hierholzer算法
  - 應用(一筆畫問題)
- 哈密頓路徑/回路
  - 回溯算法
  - 動態規劃方法
  - NP完全性
- 圖著色算法
  - 貪心著色
  - 回溯著色
  - Welsh-Powell算法
  - 應用(寄存器分配)
- 最大團算法
  - Bron–Kerbosch算法
  - 剪枝技術
- 平面圖算法
  - 平面性測試
  - 面提取
- 支配樹
  - Lengauer-Tarjan算法
  - 編譯器優化應用
- 最小樹形圖(最小樹形圖)
  - Chu–Liu/Edmonds算法
  - 有向圖生成樹
- 斯坦納樹問題
  - 近似算法
  - 精確算法

5. 字符串算法

模式匹配
- 樸素字符串匹配
  - 暴力匹配
  - 時間復雜度分析
- KMP算法
  - 部分匹配表(next數組)
  - 失配函數構造
  - 復雜度分析
- Boyer-Moore算法
  - 壞字符規則
  - 好后綴規則
  - 實際效率分析
- Rabin-Karp算法
  - 哈希函數設計
  - 滾動哈希技術
  - 多模式擴展
- Aho-Corasick算法
  - AC自動機構建
  - 失配指針
  - 多模式匹配優勢
- Sunday算法
  - 快速跳轉
  - 實際效率
- Shift-And/Shift-Or算法
  - 位并行技術
  - 近似字符串匹配擴展
字符串距離
- 編輯距離
  - 萊文斯坦距離
    - 動態規劃實現
    - 空間優化
  - 漢明距離
    - 位運算優化
    - 應用場景
  - Damerau-Levenshtein距離
    - 換位操作
  - 最長公共子序列
    - 動態規劃方法
    - 空間優化
    - 多序列擴展
  - 最長公共子串
    - 后綴數組解法
    - 動態規劃解法
- 相似度度量
  - Jaccard相似系數
  - 余弦相似度
  - n-gram距離
  - Jaro-Winkler距離
文本壓縮
- 霍夫曼編碼
  - 霍夫曼樹構建
  - 編碼與解碼
  - 最優性證明
- 算術編碼
  - 區間細分
  - 精度問題
- Lempel-Ziv家族
  - LZ77
  - LZ78
  - Lempel-Ziv-Welch(LZW)
  - LZSS
  - LZMA
- Burrows-Wheeler變換
  - 變換原理
  - 逆變換
  - 與DEFLATE結合
- PPM(預測部分匹配)
  - 上下文模型
  - 逃逸符號
字符串索引
- 后綴數組
  - DC3/SA-IS構建算法
  - 高度數組(LCP)
  - 應用(最長重復子串)
- 后綴樹
  - Ukkonen線性時間構建
  - McCreight算法
  - 應用(最長公共子串)
- 后綴自動機
  - 狀態構建
  - 應用場景
- FM-Index
  - BWT索引
  - 行列采樣
  - 生物信息學應用
- 廣義后綴樹
  - 多字符串索引
正則表達式
- NFA構建
- DFA轉換
- Thompson算法
- 回溯法實現
字符串算法應用
- DNA序列比對
- 拼寫檢查與糾正
- 文本搜索引擎
- 數據壓縮

6. 計算幾何

基本操作
- 點、線、面的表示
  - 點的表示與運算
  - 向量表示
  - 線段表示
  - 多邊形表示
- 向量運算
  - 點積與叉積
  - 三重積
  - 向量投影
- 距離計算
  - 點到點距離
  - 點到線距離
  - 點到面距離
  - 線段間距離
- 基本判定
  - 點在線段上判定
  - 線段相交判定
  - 射線與線段相交
  - 點的方位判斷
凸包算法
- Graham掃描法
  - 排序技巧
  - 復雜度分析
- Andrew算法(單調鏈)
  - 上下凸殼構建
  - 復雜度優勢
- Jarvis步進法(Gift wrapping)
  - 實現簡單性
  - 輸出敏感算法
- 分治法
- 快包算法(QuickHull)
- 隨機增量法
- 剪枝優化
多邊形
- 多邊形面積計算
  - 三角剖分法
  - 鞋帶公式
- 點在多邊形內的判定
  - 射線法
  - 繞數法
  - 三角剖分法
- 多邊形相交判定
  - 分離軸定理
  - 線段相交檢測
- 多邊形剖分
  - 耳切法
  - 單調多邊形剖分
  - 最優三角剖分
- 多邊形核
  - 半平面交
  - 應用
- 多邊形布爾運算
  - 交、并、差操作
  - Weiler-Atherton算法
- 簡化多邊形
  - Douglas-Peucker算法
掃描線算法
- 線段相交
- 矩形面積并
- 多邊形面積并
- 最近點對
Voronoi圖
- Fortune掃描線算法
- 增量法
- 分治法
- 應用場景(最近鄰查找)
Delaunay三角剖分
- 空圓性質
- 翻轉算法
- 增量構造法
- 與Voronoi圖對偶關系
最近點對問題
- 分治算法
- 掃描線方法
- 隨機化算法
線段相交檢測
- 掃描線算法
- Bentley-Ottmann算法
- 分治算法
凸多邊形算法
- 二分查找優化
- 切線計算
- 支撐線
- 凸包合并
計算幾何高級主題
- 幾何搜索
  - 點定位問題
  - 區域查詢
  - 范圍樹
- 安排問題(Arrangement)
  - 線段安排
  - 雙對偶性
- 運動規劃
  - 可見圖
  - 元胞分解
- 幾何圖形近似
- 機器人路徑規劃

7. 動態規劃

基本概念
- 最優子結構
- 重疊子問題
- 備忘錄法(記憶化搜索)
- 自底向上方法
基本動態規劃
- 一維動態規劃
  - 斐波那契序列
    - 遞推實現
    - 矩陣快速冪優化
  - 最長遞增子序列
    - O(n2)解法
    - O(nlogn)解法(二分優化)
    - 最長上升子序列應用
  - 最大子數組和
    - Kadane算法
    - 分治解法比較
- 背包問題系列
  - 0-1背包問題
    - 基本實現
    - 空間優化
    - 路徑重建
  - 完全背包問題
    - 基本實現
    - 與0-1背包區別
  - 多重背包問題
    - 基本實現
    - 二進制優化
    - 單調隊列優化
  - 分組背包問題
  - 混合背包問題
  - 二維費用背包問題
  - 求方案數的背包問題
  - 背包方案的字典序
區間動態規劃
- 矩陣鏈乘法
  - 最優分割點
  - 方案重建
- 最優三角剖分
  - 多邊形剖分
  - 權值定義
- 石子合并問題
  - 環形石子合并
  - 四邊形不等式優化
- 括號匹配
- 最長回文子序列
- 最長回文子串
- 區間DP優化
  - 四邊形不等式優化
  - Knuth優化
狀態壓縮動態規劃
- 狀態表示技巧
  - 位運算基礎
  - 狀態轉移設計
- 旅行商問題的DP解法
  - 狀態設計
  - 時空復雜度分析
- 集合覆蓋問題
  - 狀態設計
  - 子集枚舉技巧
- 子集DP
  - 枚舉子集的方法
  - SOS DP (Sum Over Subsets)
- 狀壓技巧
  - 位操作常用技巧
  - Gosper’s Hack
  - 枚舉子集的所有子集
樹形動態規劃
- 樹的最大獨立集
  - 選與不選狀態
  - 樹上消息傳遞
- 樹的最小支配集
  - 狀態定義
  - 轉移方程設計
- 樹的最小頂點覆蓋
  - 與最大獨立集關系
- 樹上背包問題
  - 樹上合并背包
  - DFS序優化
- 換根DP
  - 一次DFS預處理
  - 重心的求法
- 樹上分治
  - 點分治
  - 路徑計數
  - 動態點分治
- 樹鏈剖分
  - 重鏈剖分
  - 實鏈剖分
  - 樹上路徑查詢

8. 貪心算法

貪心算法基礎
- 貪心選擇性質
- 最優子結構
- 貪心算法證明方法
  - 交換論證
  - 反證法
經典貪心問題
- 活動選擇問題
  - 按結束時間排序
  - 證明正確性
- 赫夫曼編碼
  - 最優前綴碼
  - 構造霍夫曼樹
- 最小生成樹
  - Prim算法貪心性質
  - Kruskal算法貪心性質
- 單源最短路徑
  - Dijkstra算法貪心策略
  - 負權邊的失效
- 集合覆蓋問題的貪心近似
  - 貪心算法近似比
  - 最壞情況分析
- 作業調度問題
  - 單機最優調度
  - 最小化完成時間
  - 最小化延遲
  - 截止時間與懲罰
  - 區間調度問題
貪心算法設計技巧
- 排序預處理
- 雙指針技術
- 事件處理
- 優先隊列應用
貪心算法與動態規劃對比
- 相同點與差異
- 適用場景分析
- 常見混淆案例
貪心算法近似比分析
- 近似算法概念
- 性能保證證明
- 近似比界限

9. 分治算法

分治策略基礎
- 分解、解決、合并三步法
- 遞歸樹分析
- 主定理應用
經典分治算法
- 快速排序
  - 分區策略
  - 隨機化技巧
  - 平均時間復雜度證明
- 歸并排序
  - 合并操作
  - 穩定性分析
  - 外部排序應用
- Strassen矩陣乘法
  - 七次乘法技巧
  - 漸近復雜度改進
  - 實際應用考量
- 最接近點對問題
  - 平面劃分
  - 條帶內點對處理
  - 線性時間合并
- 快速選擇(第k小元素)
  - 分區后直接遞歸
  - 期望線性時間證明
  - 中位數的中位數(BFPRT)算法
- 循環賽日程表問題
  - 遞歸構造
  - 應用場景
- 大整數乘法
  - Karatsuba算法
  - 分治策略減少乘法次數
分治算法設計與優化
- 平衡分割
- 合并步驟優化
- 基本情況優化
- 避免重復計算
分治與動態規劃的結合
- 分治+記憶化
- 區間DP的分治理解

10. 回溯算法

回溯法基礎
- 狀態空間樹
- 顯式與隱式約束
- 解空間構建
- 剪枝策略
經典回溯問題
- N皇后問題
  - 約束傳播
  - 位運算優化
  - 對稱性剪枝
- 圖的著色問題
  - 最小著色數
  - 沖突檢測優化
  - 啟發式選擇策略
- 子集和問題
  - 排序預處理
  - 剪枝條件
  - 與動態規劃對比
- 漢密爾頓路徑問題
  - 可行性剪枝
  - 與TSP關系
- 數獨求解
  - 約束傳播
  - 最小剩余值啟發式
  - 舞蹈鏈算法(DLX)
- 組合問題生成
  - 子集生成
  - 排列生成
  - 組合生成
  - 字典序生成算法
回溯優化技巧
- 順序選擇優化
- 約束傳播
- 對稱性破缺
- 位向量表示狀態
- 預排序
- 預處理
啟發式回溯
- 啟發函數設計
- 剪枝策略
- 結合局部搜索
回溯與分支定界
- 界限函數設計
- 最優解搜索
- 剪枝效率分析

11. 隨機化算法

隨機算法基礎
- 概率空間
- 隨機變量
- 期望與方差
- 隨機算法類型
  - 蒙特卡洛算法
  - 拉斯維加斯算法
  - 舍伍德算法
隨機化技術
- 隨機采樣
- 隨機置換
- 隨機選擇
- 隨機分區
- 隨機行走
經典隨機化算法
- 隨機快速排序
  - 隨機主元選擇
  - 期望時間分析
- 隨機化素性測試
  - Miller-Rabin算法
    - 二次探測
    - 錯誤概率分析
  - Fermat素性測試
    - 小費馬定理
    - Carmichael數的弱點
  - Solovay-Strassen算法
  - AKS確定性素性測試
- 蒙特卡洛算法
  - 隨機近似算法
  - π值估計
  - 面積計算
  - 積分估計
- 拉斯維加斯算法
  - 隨機快速排序
  - 隨機化BST
- 舍伍德算法
  - 完美洗牌
  - Fisher-Yates算法
- 快速隨機選擇算法
  - 期望線性時間分析
  - 與確定性選擇對比
- 最小割算法
  - Karger算法
  - Karger-Stein算法
  - 期望分析
隨機化數據結構
- 跳表
  - 概率層次構建
  - 期望查找時間
- 樹狀隨機化結構
  - Treap(樹堆)
  - 隨機化二叉搜索樹
- 布隆過濾器
  - 錯誤率分析
  - 最優參數選擇
- Count-Min Sketch
- HyperLogLog算法
隨機化在線算法
- 隨機化競爭分析
- 對抗輸入處理
隨機化算法的去隨機化
- 條件期望方法
- 方法德蘭多米化
- 偽隨機函數應用

12. 數論算法

基本數論概念
- 整除性與同余
- 素數與合數
- 算術基本定理
- 模運算性質
整數運算
- 高精度整數計算
  - 大整數加減
  - 大整數乘法
    - 普通乘法
    - Karatsuba算法
    - FFT/NTT優化
  - 大整數除法
- 最大公約數(GCD)
  - 歐幾里得算法
    - 基本算法
    - 時間復雜度分析
    - 二進制優化(Binary GCD)
  - 擴展歐幾里得算法
    - 求解線性丟番圖方程
    - 模逆元計算
  - Stein算法(二進制GCD)
    - 位運算優化
- 最小公倍數(LCM)
  - GCD關系
  - 多個數的LCM計算
素數與因數分解
- 素數生成與判定
  - 試除法
  - 埃拉托斯特尼篩法
    - 基本篩法
    - 優化技巧
  - 線性篩法
    - 歐拉篩
    - 時間復雜度優化
  - 區間篩法
  - 素性測試
    - Miller-Rabin測試
    - Fermat測試
- 整數分解
  - 試除法
  - Pollard’s rho算法
  - Pollard’s p-1算法
  - 二次篩法
  - 數域篩法
模運算
- 模運算基本性質
- 快速冪
  - 二進制快速冪
  - 矩陣快速冪
  - 多項式快速冪
- 模逆元
  - 擴展歐幾里得法
  - 費馬小定理法
  - 線性預處理
- 中國剩余定理
  - 基本定理
  - 擴展中國剩余定理
  - 應用場景
- 離散對數
  - Shanks的Baby-step Giant-step算法
  - Pollard’s rho算法
  - 指標計算法
數論函數
- 歐拉函數
  - 性質
  - 計算方法
  - 歐拉定理
- 莫比烏斯函數
  - 定義與性質
  - 莫比烏斯反演
  - 計算技巧
- 數論函數的卷積
連分數
- 連分數展開
- 有理數逼近
密碼學應用
- RSA算法基礎
  - 公鑰生成
  - 加密解密過程
  - 安全性分析
- Diffie-Hellman密鑰交換
- 離散對數問題
- 素數在密碼學中的應用

13. 計算復雜性理論

復雜度分析基礎
- 漸近記號
  - Big-O, Big-Omega, Big-Theta
  - 小o, 小omega
  - 漸近緊確界
- 時間復雜度分析
  - 最壞情況分析
  - 平均情況分析
  - 攤銷分析
    - 聚集法
    - 核算法
    - 勢能法
- 空間復雜度分析
  - 遞歸棧空間
  - 輔助空間
復雜度類別
- P類
  - 多項式時間可解問題
  - 常見P類問題
- NP類
  - 非確定性多項式時間
  - 驗證與求解的區別
- NP完全
  - Cook-Levin定理
  - 歸約概念
  - NP完全性證明技術
- NP難問題
  - 與NP完全的關系
  - 優化問題與判定問題
- PSPACE
- 可數性與不可數性
- 決定性問題
經典NP完全問題
- 布爾可滿足性問題(SAT)
  - 3-SAT
  - Horn-SAT
- 旅行商問題
  - 判定版本
  - 優化版本
  - 近似算法
- 頂點覆蓋問題
  - 2-近似算法
  - 證明思路
- 集合覆蓋問題
  - 貪心近似算法
  - 近似比
- 子集和問題
  - 偽多項式時間算法
  - NP完全性證明
- 圖著色問題
  - k-著色
  - 近似算法
- 團問題(Clique)
- 獨立集問題
近似算法
- 近似比
- 近似方案(PTAS)
- 完全近似方案(FPTAS)
- 不可近似性
- 經典近似算法
  - 裝箱問題近似
  - TSP近似
  - 頂點覆蓋近似
隨機化與平均復雜度
- 隨機復雜度分析
- 平滑分析
量子計算簡介
- 量子復雜度類BQP
- 量子多項式時間
- 量子算法概覽

14. 調度與負載均衡算法

調度問題基礎
- 任務與資源模型
- 調度目標
- 在線與離線調度
- 搶占式與非搶占式調度
基本輪詢算法
- 簡單輪詢(Round Robin)
  - 基本實現
  - 均衡性分析
  - 適用場景
- 加權輪詢(Weighted Round Robin)
  - 權重分配策略
  - 實現技巧
- 平滑加權輪詢(Smooth Weighted Round Robin)
  - 動態權重調整
  - 平滑性保證
- 交替輪詢(Alternating RR)
高級負載均衡
- 最少連接(Least Connection)
  - 連接計數
  - 新連接分配
- 加權最少連接(Weighted Least Connection)
  - 加權因子設計
- 最短響應時間
  - 響應時間估計
  - 自適應調整
- IP哈希(IP Hash)
  - 一致性考慮
  - 應用場景
- 一致性哈希(Consistent Hashing)
  - 哈希環設計
  - 虛擬節點
  - 平衡性分析
  - 最小化遷移
- 動態負載均衡
  - 服務器狀態監控
  - 負載預測
  - 自適應調整
進程/線程調度
- 操作系統調度
  - 先來先服務(FCFS)
    - 實現方法
    - 優缺點分析
  - 短作業優先(SJF)
    - 非搶占式SJF
    - 搶占式SJF(SRTF)
    - 預估執行時間
  - 優先級調度
    - 靜態優先級
    - 動態優先級
    - 老化技術
  - 輪轉調度(Round Robin)
    - 時間片選擇
    - 上下文切換開銷
  - 多級隊列調度
    - 隊列分配策略
    - 隊列間調度
  - 多級反饋隊列
    - 動態優先級調整
    - 時間片增長策略
  - 完全公平調度(CFS)
    - 虛擬運行時間
    - 紅黑樹實現
    - 調度延遲與粒度
- 實時調度算法
  - 速率單調調度(RMS)
    - 最優性證明
    - 可調度性分析
  - 最早截止時間優先(EDF)
    - 動態優先級
    - 最優性證明
  - 最小松弛時間優先(LLF)
    - 計算方法
    - 實現復雜度
作業調度高級主題
- 隨機工作竊取(Work Stealing)
  - 雙端隊列設計
  - 竊取策略
  - 負載均衡性質
- 分支定界作業調度
  - 界限函數設計
  - 分支策略
- 遺傳算法作業調度
  - 編碼設計
  - 適應度函數
  - 交叉與變異
- 強化學習調度方法
  - 狀態與動作設計
  - 獎勵函數
  - 訓練策略
- 資源受限項目調度(RCPSP)
  - 數學模型
  - 啟發式算法
- 作業車間調度問題
  - 流水作業調度
    - Johnson算法(兩臺機器)
    - NEH算法
  - 開放式作業調度
  - 作業車間調度
    - 關鍵路徑方法
    - 瓶頸機器識別
- 批處理作業調度
  - 批量形成策略
  - 批內調度

15. 機器學習算法

監督學習
- 線性模型
  - 線性回歸
    - 最小二乘法
    - 梯度下降
    - 正則化技術
  - 邏輯回歸
    - 極大似然估計
    - 決策邊界
    - 多分類擴展
  - 感知器
    - 在線學習
    - 收斂性證明
- 決策樹
  - 構建算法
    - ID3算法
    - C4.5算法
    - CART算法
  - 特征選擇
    - 信息增益
    - 增益率
    - 基尼指數
  - 剪枝策略
    - 預剪枝
    - 后剪枝
  - 處理連續特征
- 集成學習
  - Bagging
    - 隨機森林
      - 隨機特征選擇
      - OOB錯誤估計
      - 特征重要性
  - Boosting
    - AdaBoost
      - 樣本權重調整
      - 弱分類器權重
    - Gradient Boosting
      - GBDT
      - XGBoost
      - LightGBM
    - Stacking
  - 投票方法
- 支持向量機(SVM)
  - 線性SVM
    - 最大間隔
    - 對偶問題
    - SMO算法
  - 核方法
    - 多項式核
    - 高斯核(RBF)
    - 字符串核
  - 支持向量回歸
  - 一類SVM
- k-近鄰算法(KNN)
  - 距離度量
    - 歐氏距離
    - 曼哈頓距離
    - 閔可夫斯基距離
  - 加權策略
  - k值選擇
  - 鄰近搜索優化
    - kd樹
    - 球樹
    - 局部敏感哈希
- 神經網絡基礎
  - 多層感知機
    - 前向傳播
    - 反向傳播
    - 激活函數
  - 損失函數
    - 均方誤差
    - 交叉熵
  - 優化算法
    - SGD
    - Adam
    - RMSprop
  - 正則化技術
    - Dropout
    - 批標準化
無監督學習
- 聚類算法
  - k-均值聚類
    - 算法步驟
    - 初始中心選擇
    - k值確定
    - k-means++
    - Mini-batch k-means
  - 層次聚類
    - 凝聚方法
    - 分裂方法
    - 連接策略
      - 單連接
      - 全連接
      - 平均連接
      - Ward方法
  - 密度聚類
    - DBSCAN
      - 核心點、邊界點與噪聲
      - 參數選擇
    - OPTICS
    - Mean Shift
  - 譜聚類
    - 拉普拉斯矩陣
    - 特征向量
  - 高斯混合模型
    - EM算法
    - 模型選擇
- 降維技術
  - 主成分分析(PCA)
    - 協方差矩陣
    - 特征值分解
    - 貢獻率分析
    - 核PCA
  - 線性判別分析(LDA)
    - 類內散度與類間散度
    - 特征抽取
  - 奇異值分解(SVD)
    - 矩陣分解原理
    - 截斷SVD
    - 應用(推薦系統)
  - 流形學習
    - ISOMAP
    - t-SNE
    - UMAP
- 異常檢測
  - 統計方法
  - 基于距離
  - 基于密度
  - 孤立森林
- 關聯規則挖掘
  - Apriori算法
  - FP-Growth算法
強化學習
- 基本概念
  - 馬爾可夫決策過程
  - 狀態、動作、獎勵
  - 值函數與策略
- 經典算法
  - 動態規劃方法
    - 策略迭代
    - 值迭代
  - 蒙特卡洛方法
    - 首次訪問MC
    - 每次訪問MC
  - 時序差分學習
    - SARSA
      - on-policy學習
      - 期望SARSA
    - Q-learning
      - off-policy學習
      - Double Q-learning
  - 策略梯度法
    - REINFORCE算法
    - Actor-Critic方法
  - 深度強化學習
    - DQN
    - A3C
    - PPO
- 探索與利用
  - ε-greedy
  - UCB
  - Thompson采樣
- 多臂賭博機問題
  - 算法對比
  - 上下文賭博機
半監督與遷移學習
- 半監督學習
  - 自訓練
  - 協同訓練
  - 圖方法
- 遷移學習
  - 領域自適應
  - 微調技術
機器學習評估方法
- 交叉驗證
- 數據集劃分
- 評價指標
- 過擬合與欠擬合
- 偏差-方差分解

16. 分布式算法

分布式系統模型
- 同步與異步模型
- 故障模型
- 一致性模型
- CAP定理
分布式共識
- 二階段提交(2PC)
- 三階段提交(3PC)
- Paxos算法
  - Basic Paxos
  - Multi-Paxos
  - 活鎖問題
- Raft算法
  - 領導選舉
  - 日志復制
  - 安全性證明
  - 成員變更
- ZAB協議(Zookeeper)
- 拜占庭將軍問題
  - 拜占庭容錯(BFT)
  - PBFT算法
  - Tendermint
- 區塊鏈共識
  - PoW(工作量證明)
  - PoS(權益證明)
  - DPoS(委托權益證明)
分布式哈希表
- Chord
  - 環形結構
  - 指針表優化
- Pastry
- Kademlia
  - XOR距離
  - k-bucket
- 應用(P2P網絡)
一致性哈希
- 虛擬節點
- 負載均衡
- 最小化遷移
- 應用場景(分布式緩存)
分布式計算
- MapReduce
  - 編程模型
  - 容錯機制
  - 調度策略
- Spark計算模型
  - RDD抽象
  - 轉換與動作
  - DAG執行引擎
  - 內存計算優勢
- 流處理
  - Storm
  - Flink
  - 窗口計算
- 批處理與流處理統一
分布式鎖
- 基于數據庫
- 基于緩存
  - Redis實現
  - 鎖超時問題
- 基于ZooKeeper
- 死鎖檢測與預防
分布式事務
- ACID特性
- BASE理論
- 分布式事務協議
  - 2PC/3PC
  - TCC(Try-Confirm-Cancel)
  - SAGA模式
- 最終一致性
分布式系統設計模式
- 主從復制
- 讀寫分離
- 分區(Sharding)
- 一致性哈希
- 領導選舉
- 背壓機制
- 熔斷器模式
分布式系統理論
- FLP不可能性
- CAP定理
- PACELC定理
- 一致性級別

17. 并行算法

并行計算模型
- PRAM模型
- BSP模型
- LogP模型
- 并行復雜度分析
  - 加速比
  - 效率
  - Amdahl定律
  - Gustafson定律
并行編程范式
- 共享內存
  - OpenMP
  - pthread
- 消息傳遞
  - MPI
- 數據并行
  - SIMD
  - GPU編程模型
    - CUDA
    - OpenCL
并行算法設計技術
- 分解與映射
- 局部性優化
- 負載均衡
- 通信優化
- 同步機制
并行排序
- 并行歸并排序
  - 遞歸并行
  - 工作劃分
- 并行快速排序
  - 劃分策略
  - 任務分配
- 樣本排序
- 基數排序并行化
- 位圖排序并行化
并行圖算法
- 并行廣度優先搜索
  - 前沿擴展
  - 層同步
  - 工作分配
- 并行深度優先搜索
- 并行最短路徑
  - 并行Dijkstra
  - 并行Bellman-Ford
  - Δ-stepping算法
- 并行最小生成樹
- 并行連通分量
  - Shiloach-Vishkin算法
  - 標簽傳播
并行矩陣運算
- 矩陣乘法
  - 塊分割
  - Cannon算法
  - SUMMA算法
  - DNS算法
- 矩陣分解并行化
  - 并行LU分解
  - 并行Cholesky分解
  - 并行QR分解
- 求解線性方程組
  - 并行高斯消元
  - 迭代方法并行化
并行動態規劃
- 依賴圖分析
- 波前并行
- k-D格柵方法
并行前綴和
- Hillis-Steele算法
- Blelloch算法
- 效率分析
工作竊取調度
- 雙端隊列設計
- 竊取策略
- 負載均衡
- 應用(并行遞歸)
并行數值算法
- 并行FFT
- 并行數值積分
- 并行隨機數生成
并行機器學習
- 數據并行
- 模型并行
- 梯度并行化
- 參數服務器架構

18. 壓縮算法

壓縮基礎
- 壓縮比
- 香農信息論
- 熵編碼原理
- 信源模型
無損壓縮
- 基本無損壓縮
  - 游程編碼(RLE)
    - 基本編碼方案
    - 變長RLE
    - 應用場景(圖像)
  - 霍夫曼編碼
    - 前綴碼特性
    - 霍夫曼樹構建
    - 自適應霍夫曼編碼
    - 規范霍夫曼編碼
  - 算術編碼
    - 區間細分
    - 精度問題處理
    - 與霍夫曼編碼比較
  - 預測編碼
    - 差分編碼
    - DPCM(差分脈沖編碼調制)
  - 字典編碼
    - LZ77/LZSS
      - 滑動窗口
      - 前向緩沖區
      - 匹配查找優化
    - LZ78/LZW
      - 字典構建
      - 編碼過程
      - 解碼過程
      - GIF壓縮應用
    - DEFLATE
      - LZ77與霍夫曼結合
      - 靜態與動態霍夫曼樹
      - zlib/gzip實現
    - LZMA
      - 改進的匹配查找
      - 范圍編碼器
      - 7z格式
- 有損壓縮
  - 變換編碼
    - 離散余弦變換(DCT)
      - 二維DCT
      - 能量聚集性
      - JPEG應用
    - 小波變換
      - 多分辨率分析
      - 離散小波變換
      - JPEG2000應用
    - 分形壓縮
      - 迭代函數系統
      - 自相似性利用
  - 量化
    - 標量量化
    - 向量量化
    - 自適應量化
  - 預測編碼
    - 運動補償
    - 視頻編碼應用
  - 感知編碼
    - 人類視覺系統模型
    - 掩蔽效應利用
- 特定領域壓縮
  - 圖像壓縮
    - JPEG
      - 編碼流程
      - 質量控制
    - PNG
      - 無損特性
      - 濾波器優化
    - WebP
    - JPEG-XL
  - 視頻壓縮
    - H.264/AVC
    - H.265/HEVC
    - VP9
    - AV1
  - 音頻壓縮
    - MP3
    - AAC
    - Vorbis
    - Opus
  - 文本壓縮
    - bzip2
    - PPM
    - 上下文模型
- 壓縮算法評估
  - 壓縮率
  - 速度考量
  - 對稱性分析
  - 內存需求
  - 錯誤魯棒性

19. 密碼學算法

密碼學基礎
- 信息安全基本原則
  - 保密性
  - 完整性
  - 可用性
  - 不可否認性
- 攻擊模型
  - 唯密文攻擊
  - 已知明文攻擊
  - 選擇明文攻擊
  - 選擇密文攻擊
- 密碼學原語
  - 偽隨機生成器
  - 單向函數
  - 單向陷門函數
  - 承諾方案
對稱加密
- 流密碼
  - RC4
    - 密鑰調度算法
    - 偽隨機生成算法
    - 已知弱點
  - ChaCha20
    - 四分之一輪函數
    - Salsa20改進
  - 線性反饋移位寄存器(LFSR)
    - 最大長度序列
    - 非線性組合
- 分組密碼
  - DES
    - Feistel網絡
    - S盒設計
    - 密鑰調度
    - 3DES變種
  - AES
    - SPN結構
    - 字節替代
    - 行移位
    - 列混合
    - 輪密鑰加
    - 密鑰擴展
  - 其他主要分組密碼
    - Blowfish
    - Twofish
    - Serpent
    - IDEA
- 操作模式
  - ECB模式
  - CBC模式
  - CFB模式
  - OFB模式
  - CTR模式
  - GCM模式
  - XTS模式
- 認證加密
  - AEAD模式
  - GCM
  - CCM
  - EAX
  - ChaCha20-Poly1305
非對稱加密
- 數學基礎
  - 模運算
  - 離散對數問題
  - 因數分解問題
  - 橢圓曲線離散對數
- RSA
  - 密鑰生成
  - 加密解密過程
  - 簽名驗證
  - 填充方案(PKCS#1)
  - 安全性考量
- ElGamal
  - 基于離散對數
  - 同態性質
- ECC(橢圓曲線加密)
  - 橢圓曲線基本概念
  - 點加法與倍乘
  - ECDH(橢圓曲線Diffie-Hellman)
  - ECDSA(橢圓曲線數字簽名)
  - EdDSA(Edwards曲線數字簽名)
- Diffie-Hellman密鑰交換
  - 原始協議
  - 中間人攻擊防護
  - 有限域實現
  - 橢圓曲線實現
- 格密碼
  - 格基礎知識
  - LWE問題
  - NTRU
  - 后量子密碼學
哈希函數
- 哈希函數性質
  - 單向性
  - 抗碰撞性
  - 雪崩效應
- 構造方法
  - Merkle-Damg?rd結構
  - 海綿結構
- 實際哈希函數
  - MD5
    - 壓縮函數設計
    - 已知攻擊
  - SHA家族
    - SHA-1
    - SHA-2
    - SHA-3(Keccak)
  - BLAKE2
    - BLAKE2b/BLAKE2s
    - 并行化特性
  - RIPEMD
  - Whirlpool
- 密碼學應用
  - 消息認證碼(HMAC)
  - 密鑰派生函數(KDF)
  - 隨機數生成
數字簽名
- 簽名方案
  - RSA簽名
  - DSA
  - ECDSA
  - EdDSA(Ed25519)
  - Schnorr簽名
- 盲簽名
- 群簽名
- 環簽名
- 多重簽名
- 聚合簽名
消息認證碼
- HMAC
- CBC-MAC
- PMAC
- CMAC
- Poly1305
零知識證明
- 基本概念
  - 完備性
  - 可靠性
  - 零知識性
- 交互式證明
  - Schnorr協議
  - Fiat-Shamir變換
- 非交互式零知識證明
  - zk-SNARKs
  - zk-STARKs
  - Bulletproofs
- 應用
  - 身份驗證
  - 匿名憑證
  - 區塊鏈隱私
密鑰管理
- 密鑰生成
- 密鑰分發
- 密鑰存儲
- 公鑰基礎設施(PKI)
  - 證書
  - CA層次結構
  - 吊銷機制
密碼協議
- TLS/SSL
- SSH
- 安全多方計算
- 秘密共享
  - Shamir門限方案
  - Blakley方案
- 同態加密
  - 部分同態
  - 全同態
  - 應用場景

20. 優化算法

優化問題基礎
- 問題形式化
- 可行域與目標函數
- 局部最優與全局最優
- 凸優化基礎
線性規劃
- 標準形式與松弛形式
- 幾何解釋
- 基本解與基本可行解
- 單純形法
  - 初始基可行解
  - 旋轉操作
  - 退化與循環性
  - 兩階段法
  - 大M法
- 內點法
  - 障礙函數方法
  - 原對偶方法
  - 復雜度優勢
- 對偶理論
  - 弱對偶性
  - 強對偶性
  - 互補松弛性
  - 對偶單純形法
- 整數線性規劃
  - 分支定界法
  - 割平面法
  - 列生成法
- 網絡流線性規劃
  - 最小費用流
  - 運輸問題
  - 指派問題
非線性優化
- 無約束優化
  - 梯度下降法
    - 步長選擇
    - 收斂性分析
    - 隨機梯度下降
    - 批量梯度下降
    - mini-batch梯度下降
  - 牛頓法
    - 二階信息利用
    - 收斂速度
    - 計算復雜度
  - 擬牛頓法
    - BFGS
    - L-BFGS
    - DFP
    - SR1
  - 共軛梯度法
    - Fletcher-Reeves公式
    - Polak-Ribière公式
  - 信賴域方法
  - 線搜索方法
    - Armijo準則
    - Wolfe條件
    - 黃金分割法
- 約束優化
  - 拉格朗日乘數法
  - KKT條件
  - 懲罰函數法
  - 障礙函數法
  - 增廣拉格朗日法
  - 序列二次規劃(SQP)
- 全局優化
  - 多起點局部搜索
  - 分支定界
  - 區間分析
組合優化
- 精確算法
  - 分支定界法
    - 下界計算
    - 分支策略
    - 搜索策略
  - 動態規劃
  - 背包問題算法
  - 最短路徑算法
- 近似算法
  - 近似度量
  - 近似方案設計
  - 集合覆蓋近似
  - TSP近似
- 啟發式與元啟發式
  - 局部搜索
    - 爬山法
    - 模擬退火
      - 退火調度
      - 鄰域定義
      - 接受準則
    - 禁忌搜索
      - 禁忌表
      - 短期記憶
      - 長期記憶
  - 進化算法
    - 遺傳算法
      - 編碼方案
      - 選擇操作
      - 交叉操作
      - 變異操作
      - 參數設置
    - 進化策略
    - 差分進化
    - 遺傳編程
  - 群體智能
    - 粒子群優化
      - 粒子更新
      - 鄰域結構
      - 收斂性分析
    - 蟻群算法
      - 信息素更新
      - 狀態轉移規則
      - TSP應用
    - 人工蜂群
    - 螢火蟲算法
    - 和聲搜索
  - 路徑重連
  - 變鄰域搜索
多目標優化
- Pareto最優概念
- 加權求和法
- 約束法
- 非支配排序
- 多目標進化算法
  - NSGA-II
  - MOEA/D
- 指標法
魯棒優化
- 不確定集建模
- 最壞情況優化
- 分布式魯棒優化
在線優化與學習
- 多臂賭博機問題
- 在線凸優化
- 專家建議問題
- 在線學習理論
優化算法應用
- 機器學習中的優化
- 運籌學應用
- 金融優化
- 工程設計優化

21. 數據庫算法

數據庫基礎
- 數據模型
- 關系代數
- 事務特性(ACID)
- 并發控制
- 故障恢復
索引結構
- B+樹索引
  - 結構特性
  - 插入算法
  - 刪除算法
  - 范圍查詢優化
  - 緩沖池管理
- 哈希索引
  - 靜態哈希
  - 動態哈希
    - 可擴展哈希
    - 線性哈希
  - 多級哈希
  - 部分匹配查詢
- 全文索引
  - 倒排索引
    - 詞項管理
    - 倒排列表
    - 壓縮技術
  - n-gram索引
  - 后綴數組索引
  - 詞典樹索引
  - 向量空間模型
  - BM25排序
- 空間索引
  - R樹家族
    - R樹
    - R*樹
    - R+樹
  - 四叉樹/八叉樹
  - 網格文件
  - 空間填充曲線
  - 地理哈希
- 多維索引
  - kd樹
  - UB樹
  - 位圖索引
  - 聯合索引
  - 前綴壓縮
查詢優化
- 查詢處理步驟
  - 解析
  - 重寫
  - 優化
  - 執行
- 基于規則的優化
  - 謂詞下推
  - 投影下推
  - 連接重排序
  - 常量傳播
- 基于成本的優化
  - 統計信息收集
  - 成本模型
  - 選擇率估計
  - 直方圖技術
- 連接算法
  - 嵌套循環連接
    - 簡單嵌套循環
    - 索引嵌套循環
    - 塊嵌套循環
  - 排序合并連接
    - 預排序優化
  - 哈希連接
    - 基本哈希連接
    - Grace哈希連接
    - Hybrid哈希連接
  - 半連接
  - 特殊連接
    - 自然連接
    - 外連接算法
    - 反連接
  - 多表連接優化
    - 連接順序選擇
    - 左深樹與右深樹
    - 動態規劃方法
- 排序算法
  - 外部歸并排序
  - 多路合并
  - 置換選擇算法
  - TOP-N優化
  - 排序回避技術
- 聚合算法
  - 哈希聚合
  - 排序聚合
  - 分組優化
- 查詢執行
  - 火山模型
  - 向量化執行
  - 代碼生成
  - 并行執行
事務處理
- 并發控制協議
  - 鎖機制
    - 兩階段鎖協議
    - 死鎖處理
    - 鎖粒度
    - 意向鎖
  - MVCC
    - 時間戳排序
    - 快照隔離
    - 版本鏈管理
    - 垃圾回收
  - 樂觀并發控制
    - 驗證技術
  - 2PC/3PC
    - 協調者邏輯
    - 參與者邏輯
    - 故障處理
  - 分布式事務
    - XA協議
    - SAGA模式
- 隔離級別
  - 讀未提交
  - 讀已提交
  - 可重復讀
  - 可序列化
  - 異常現象處理
- 故障恢復
  - WAL(預寫式日志)
  - REDO
  - UNDO
  - 檢查點
  - 恢復算法
    - ARIES
數據倉庫算法
- 物化視圖
  - 視圖選擇
  - 增量維護
  - 視圖匹配
- OLAP操作
  - 多維數據模型
  - 上卷與下鉆
  - 切片與切塊
- 數據立方體計算
  - 預計算策略
  - BUC算法
  - Star Cubing
數據壓縮
- 行壓縮
- 列壓縮
  - 字典編碼
  - 游程編碼
  - 差分編碼
  - 位圖編碼
- 索引壓縮
- 壓縮與查詢執行
數據庫中間件算法
- 分庫分表
  - 水平分片
  - 垂直分片
  - 路由算法
- 負載均衡
- 分布式查詢處理
- 連接查詢路由
流數據處理
- 窗口計算
- 近似算法
  - 計數器
  - Bloom過濾器
  - Count-Min Sketch
  - HyperLogLog
- 連續查詢處理
- 流連接算法

22. 區塊鏈算法

區塊鏈基礎
- 分布式賬本
- 哈希鏈結構
- 交易驗證
- 共識機制概念
共識算法
- 工作量證明(PoW)
  - 哈希算法
  - 難度調整
  - 51%攻擊防御
  - 比特幣挖礦
- 權益證明(PoS)
  - 質押機制
  - 驗證者選擇
  - 懲罰機制
  - 以太坊2.0實現
- 委托權益證明(DPoS)
  - 代表選舉
  - 區塊生產
  - EOS實現
- 實用拜占庭容錯(PBFT)
  - 三階段協議
  - 視圖更換
  - 超級賬本實現
- 其他共識機制
  - PoA(權威證明)
  - PoB(燃燒證明)
  - PoC(容量證明)
  - Avalanche
密碼學原語
- 哈希函數應用
  - 區塊鏈中的Merkle樹
  - 工作量證明算法
- 數字簽名
  - ECDSA應用
  - 多重簽名
  - 環簽名
  - 盲簽名
  - 聚合簽名
- 零知識證明
  - Zcash中的zk-SNARKs
  - 零知識應用場景
智能合約
- 執行環境
- 合約語言
- 氣體計費機制
- 合約驗證
- 合約優化
區塊鏈存儲
- Merkle樹
  - 樹構建
  - 簡化支付驗證
- Merkle Patricia樹
  - 以太坊狀態存儲
- IPFS存儲
- DAG結構
  - IOTA Tangle
  - Hashgraph
區塊鏈安全算法
- 防雙花機制
- 防重放攻擊
- 密鑰管理
- 閃電網絡
  - 支付通道
  - 路由算法
- 跨鏈技術
  - 原子交換
  - 哈希時間鎖定合約