数据结构与算法

数组（Array）和链表（Linked List）是最基础的数据结构——数组在内存中连续存储，支持随机访问；链表通过指针串联，支持灵活插入删除

栈（Stack）是后进先出（LIFO），队列（Queue）是先进先出（FIFO）——它们是两种最基础的操作受限线性表

哈希表通过哈希函数把键映射到数组下标——查找、插入、删除平均 O(1)，是最实用的数据结构之一

二叉树（Binary Tree）每个节点最多有两个子节点——前序、中序、后序、层序遍历是树操作的基础

二叉搜索树（Binary Search Tree, BST）对每个节点，左子树所有值 < 节点值 < 右子树所有值——查找、插入、删除平均 O(log n)

堆是完全二叉树——最大堆的父节点 >= 子节点，最小堆相反。插入和删除堆顶 O(log n)，常用于优先队列和堆排序

平衡树在插入/删除后通过旋转保持左右子树高度差在允许范围内——保证所有操作 O(log n)，不会退化为链表

图（Graph）由顶点和边组成——邻接矩阵用二维数组存边，邻接表用链表存每个顶点的邻居，各有优劣

DFS（深度优先搜索）用栈/递归深入到底再回溯，BFS（广度优先搜索）用队列逐层扩散——是最基本的两种图/树搜索算法

Dijkstra 算法从单源点出发找最短路径——贪心思想，每次选当前最近的点扩展。Floyd 算法用动态规划求所有点对的最短路径

最小生成树（MST）是连通无向图中边权和最小的生成树——Kruskal 排序选边（并查集），Prim 从点出发扩展（类似 Dijkstra）

插入排序、选择排序、冒泡排序是最简单的三种排序算法——时间复杂度 O(n²)，实现简单，适合小规模数据

归并排序稳定 O(n log n) 但需额外空间，快速排序平均 O(n log n) 且原地排序，堆排序 O(n log n) 无额外空间——各有优劣

二分搜索（Binary Search）每次把搜索范围缩小一半——在有序数组中查找目标值，时间复杂度 O(log n)

分治（Divide and Conquer）把大问题分解成小问题分别解决再合并——递归是实现分治的自然方式。归并排序、快速排序都是分治思想的应用

动态规划（Dynamic Programming, DP）把问题分解为重叠子问题，通过"记忆化"避免重复计算——最优子结构 + 状态转移方程是 DP 的核心

贪心算法（Greedy Algorithm）每步选当前最优——不保证全局最优，但对某些问题（如 Dijkstra、哈夫曼编码）贪心就是最优解

回溯（Backtracking）是暴力搜索的"剪枝"版本——尝试所有可能，发现此路不通就退回上一步。剪枝越早，效率越高

大 O 表示法（Big O Notation）描述算法效率随输入规模增长的"趋势"——它忽略常数和低阶项，只关注增长最快的部分

P 问题能在多项式时间内解决，NP 问题的解能在多项式时间内验证——P = NP？这是计算机科学最大的未解之谜（千禧年难题之一）