Big O表示法描述的是算法执行时间（或空间）随输入规模n增长的上界趋势。分析时只关注最高阶项，忽略常数系数——O(3n^2 + 5n + 10)简化为O(n^2)，因为当n趋向无穷时n^2主导增长。常见复杂度从优到劣：O(1)常数时间，如哈希表查找、数组下标访问；O(log n)对数时间，如二分查找——每次将搜索范围减半；O(n)线性时间，如遍历数组；O(n log n)线性对数，如归并排序、快排平均情况；O(n^2)平方时间，如冒泡排序、暴力枚举所有数对；O(2^n)指数时间，如不带记忆化的递归斐波那契、枚举所有子集；O(n!)阶乘时间，如全排列。分析方法：看循环——单层循环遍历n个元素是O(n)，两层嵌套循环是O(n^2)，循环变量每次翻倍或减半是O(log n)。递归分析用主定理：T(n) = aT(n/b) + O(n^d)，根据d和log_b(a)的关系确定复杂度。比如归并排序T(n) = 2T(n/2) + O(n)，a=2, b=2, d=1，log_2(2)=1=d，所以O(n log n)。空间复杂度计算额外使用的空间：新建一个长度n的数组是O(n)，递归深度为n是O(n)栈空间（如快排最坏情况），递归深度log n是O(log n)（如归并排序）。常见优化模式：两数之和用哈希表从O(n^2)暴力搜索优化到O(n)；排序后用双指针从O(n^2)优化到O(n)或O(n log n)；动态规划将指数级递归优化为多项式级（如斐波那契从O(2^n)到O(n)）。面试中建议先给出暴力解并分析复杂度，再逐步优化，展示你的思维过程。

快排平均 O(n log n)，空间 O(log n)，其缓存友好的访问模式使其在实践中最快——大多数语言标准库都用它或其混合版本。最坏情况 O(n²)，但随机化选择枢轴使其极不可能发生。归并排序在所有情况下保证 O(n log n) 且是稳定的，适合需要保持顺序的场景或链表排序。它需要 O(n) 额外空间。堆排序原地 O(n log n) 但缓存性能差。对于小数组或近乎有序的数组，插入排序的 O(n) 最优情况和低开销使其比任何分治算法都快——所以 TimSort（Python、Java）在归并中对小段用插入排序。通用内存排序我选快排，需要稳定性或外部排序选归并，小数组或混合策略中用插入排序。

BFS 用队列逐层探索图。从源节点开始，先访问所有邻居再进入下一层。这保证了无权图中的最短路径，适合求最少步数或最少连接数的问题。DFS 沿每条分支尽可能深入后回溯，用递归或显式栈实现。它更适合需要探索所有路径、检测环或生成拓扑排序的问题。两者时间都是 O(V+E)，V 为顶点数，E 为边数。BFS 最坏空间 O(V)（最宽层），DFS 最坏空间 O(V)（最长路径）。我在最短路径和层序问题中选 BFS，在穷举搜索、环检测和拓扑排序中选 DFS。图很深时用迭代 DFS 避免栈溢出；图很宽时 DFS 更省内存。

标准二分搜索在有序数组中通过反复将搜索空间减半，O(log n) 找到目标。关键变体有：下界找值第一次出现或可插入的位置——找到目标后继续向左搜索。上界找最后位置——继续向右搜索。旋转有序数组如 [4,5,6,7,0,1,2]，我通过比较 mid 和 left 判断哪半边有序，再检查目标是否落在有序半边。答案空间二分搜索用于优化问题：如求 d 天内运送包裹的最小载重，对载重值二分，贪心检查可行性。二分搜索的关键是定义清晰的循环不变量：每次迭代中 left 和 right 代表什么。我总是用 left < right 模式，根据 mid 是否可能是答案来决定 right = mid 还是 right = mid - 1。

哈希表通过计算键的哈希值确定数组索引来存储键值对。核心操作是 index = hash(key) % array_size，平均 O(1) 访问。不同键哈希到相同索引时产生冲突。我用链地址法处理——每个桶存一个链表——或开放寻址法，探测下一个空槽。链地址法更简单且退化平缓；开放寻址法缓存性能更好但实现更复杂，尤其是删除操作。我维护负载因子（条目数/桶数），超过0.75时数组翻倍并重新哈希所有条目——这种摊销代价保持操作在 O(1)。好的哈希函数均匀分布键；字符串可用多项式滚动哈希。我的设计会用链地址法的桶数组，跟踪负载因子，0.75时扩容，并实现正确的相等性检查，因为不同对象可能有相同哈希码。