*时间复杂度**：统计**基本操作执行次数**关于输入规模n的渐进上界（大O），关注最坏/平均情况

一、线性数据结构对比数组、链表、栈、队列结构优点缺点典型适用场景数组随机访问 O(1)内存连续缓存友好实现简单插入/删除 O(n)需移动元素大小固定静态数组或扩容开销大动态数组频繁随机读取、已知规模的数据集合如矩阵、缓存块链表单/双动态大小插入/删除 O(1)给定位置指针时无需预分配空间顺序访问 O(n)额外指针开销空间浪费缓存不友好频繁增删、未知数据量如LRU缓存链表、浏览器历史记录栈LIFO操作统一仅栈顶天然支持回溯、嵌套结构解析仅支持后进先出访问受限函数调用栈、括号匹配、表达式求值、DFS递归模拟队列FIFO公平调度、先进先服务不支持随机访问双端操作需dequeBFS遍历、任务调度、缓冲区管理、滑动窗口✅ 衍生结构Deque双端队列支持两端O(1)插删是栈队列的超集循环队列通过取模优化空间利用率。二、二叉树遍历递归 vs 非递归遍历方式访问顺序递归思路非递归核心栈模拟关键性质先序DLR根 → 左 → 右visit(root); preorder(root.left); preorder(root.right);栈中压入右子树→左子树保证左先弹出可唯一确定二叉树配合中序中序LDR左 → 根 → 右inorder(left); visit(root); inorder(right);持续向左走到底再弹栈访问转向右子树BST中序 严格升序序列后序LRD左 → 右 → 根postorder(left); postorder(right); visit(root);两种主流法① 双栈法先序变体根→右→左结果逆序② 标记法栈存(node, visited)适合释放内存子树先于根销毁# 中序非递归示例最常用definorder_iterative(root):stack,res[],[]currootwhilestackorcur:whilecur:# 一路向左stack.append(cur)curcur.left curstack.pop()# 访问栈顶res.append(cur.val)curcur.right# 转向右子树returnres三、平衡树原理与旋转AVL 红黑树平衡目标避免退化为链表O(n)查找维持 O(log n) 查找/插入/删除。AVL树平衡定义任意节点左右子树高度差 ≤ 1平衡因子 ∈ {-1,0,1}。旋转类型4种由失衡路径方向决定LL左左→ 右旋RR右右→ 左旋LR左右→ 先左旋再右旋RL右左→ 先右旋再左旋特点高度严格平衡查询最优但插入/删除频繁旋转O(log n)次。红黑树更实用5大性质① 节点红/黑② 根黑③ 叶NIL黑④ 红节点子必黑⑤ 任一节点到其叶路径黑节点数相同黑高平衡。旋转同AVL左/右旋但重着色recoloring更频繁旋转次数更少。优势平均性能优STLmap/set、JavaTreeMap、Linux CFS调度均采用。四、哈夫曼树与数据压缩构建过程贪心将各字符按频率权值建成叶子节点重复取权值最小的两节点合并为新内部节点权和加入集合直至只剩一棵树。编码规则左分支0右分支1 → 叶子节点路径即哈夫曼码。压缩原理高频字符短码低频长码 →总码长最小化WPL最小。局限需预知频率静态压缩需传输编码表可用自适应哈夫曼改进。五、哈希表地址计算与冲突处理哈希函数设计原则高效、均匀、确定性如h(k) (a*k b) % mm为质数。冲突处理方法原理优缺点适用场景开放定址法冲突时按探测序列线性/二次/双重哈希找空位空间紧凑但聚集严重负载因子需 0.7内存敏感、小规模数据如CPU缓存链地址法拉链法数组链表/红黑树Java 8当链长≥8转树无容量限制缓存不友好最常用通用场景Python dict、C unordered_map六、排序算法复杂度分析算法时间复杂度平均/最坏空间复杂度稳定性关键特性冒泡排序O(n²)/O(n²)O(1)✅交换相邻元素可加标志提前终止快速排序O(n log n)/O(n²)O(log n)递归栈❌分治基准划分实际最快pivot选差则退化归并排序O(n log n)/O(n log n)O(n)辅助数组✅分治合并稳定适合外排序关键洞察快排原地、cache友好但不稳定归并稳定、可并行但需O(n)空间。七、二分查找Binary Search原理在有序数组中每次比较中间元素排除一半区间。适用条件数据有序 支持随机访问数组/ArrayList。时间复杂度O(log n)空间复杂度O(1)迭代或 O(log n)递归。变体查找左/右边界、旋转数组查找、实数精度二分。八、动态规划DP——以0-1背包为例基本思想将问题分解为重叠子问题用状态转移方程边界求解避免重复计算。0-1背包建模dp[i][w] 前i个物品在容量w下的最大价值状态转移dp[i][w] max(dp[i-1][w], dp[i-1][w-weight[i]] value[i])选或不选第i个空间优化滚动数组 →dp[w] max(dp[w], dp[w-weight[i]] value[i])倒序更新九、贪心算法 vs 动态规划贪心每步选当前最优局部最优无后效性贪心选择性质成立时得全局最优如哈夫曼、活动选择、最小生成树。DP考虑所有可能决策通过状态转移保证全局最优。核心区别贪心无“回退”不试探DP有“记忆化”存子问题解。十、图的存储与遍历存储方式空间复杂度查询边增删边适用场景邻接矩阵O(V²)O(1)O(1)稠密图、需频繁查边、Floyd算法邻接表O(VE)O(degree(v))O(1)稀疏图、BFS/DFS、网络流BFS队列实现层序遍历求无权图最短路径。DFS栈/递归深度优先适合连通性、拓扑排序、强连通分量。十一、最短路径算法算法原理时间复杂度适用场景限制Dijkstra贪心优先队列每次选未确定最短距的最近点松弛O((VE) log V)单源、非负权权重为负则失效改用Bellman-FordFloyd-WarshallDPdist[i][j] min(dist[i][j], dist[i][k]dist[k][j])O(V³)多源、稠密图、含负权无负环V≤500内存O(V²)十二、算法复杂度分析方法时间复杂度统计基本操作执行次数关于输入规模n的渐进上界大O关注最坏/平均情况。空间复杂度算法运行所需额外存储空间不含输入本身包括变量、递归栈、辅助结构。技巧递归用主定理循环看嵌套层数注意隐式开销如Python切片O(n)。十三、分治法Divide Conquer三步① 分Divide分解为子问题② 治Conquer递归解决③ 合Combine合并子解。归并排序实例分mid (lr)//2拆为两半治merge_sort(left), merge_sort(right)合merge(left_arr, right_arr)—— 双指针O(n)合并。十四、回溯算法Backtracking——八皇后原理DFS剪枝在解空间树中试错式搜索失败则退回上层回溯。八皇后步骤每行放1皇后减少搜索空间列、主对角线r-c、副对角线rc用集合标记占用若某行无法放置回溯至上一行换列关键约束传播提前剪枝决定效率。十五、KMP字符串匹配核心思想利用模式串自身前缀与后缀重合信息避免主串指针回退。next数组部分匹配表next[j]P[0..j-1]的最长真前后缀长度。构造类DPj0时next[0]0i从1开始jnext[i-1]若P[i]P[j]则next[i]j1否则jnext[j-1]跳转。匹配主串i、模式串j失配时jnext[j-1]i不回退。