复杂度分析是算法面试的基础中的基础。字节、腾讯、阿里等大厂的算法面试，每道编程题都要求你分析解法的时间和空间复杂度。力扣刷题也必须理解复杂度才能判断解法是否最优。这是区分"会写代码"和"会写高效代码"的关键能力。
定义Big O表示法：描述算法运行时间或空间随输入规模增长的上界，关注最高阶项，忽略常数和低阶项。
列举常见复杂度：O(1)常数、O(log n)对数、O(n)线性、O(n log n)线性对数、O(n^2)平方、O(2^n)指数、O(n!)阶乘，并给出典型算法示例。
讲分析方法：循环次数分析（单循环O(n)、嵌套循环O(n^2)、每次减半O(log n)）、递归用主定理或递归树分析。
讲空间复杂度：额外使用的数据结构大小 + 递归栈深度。原地算法O(1)辅助空间。
讲常见优化技巧：哈希表换时间O(n^2)→O(n)、排序+双指针、动态规划避免重复计算。
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)）。面试中建议先给出暴力解并分析复杂度，再逐步优化，展示你的思维过程。
面试写完代码后主动分析复杂度，不要等面试官问——这是专业素养的体现。
记住常见数据结构操作的复杂度：HashMap O(1)、TreeMap O(log n)、排序O(n log n)、堆操作O(log n)。
刷题时养成"能否更优"的思维习惯——从暴力解出发，思考如何利用排序、哈希、双指针等技巧优化。
面试中如果忘了主定理公式，即答侠可以实时提供。
最好情况是最少操作次数（意义不大），最坏情况是最多操作次数（Big O通常描述的），平均情况是所有输入的期望操作次数。快排：最好/平均O(n log n)，最坏O(n^2)。
一系列操作的平均单次开销。ArrayList.add()扩容时是O(n)，但大多数调用是O(1)，均摊下来是O(1)。均摊和平均不同——均摊保证总操作的开销上界。
递归的空间复杂度 = 递归深度 × 每层额外空间。比如二叉树递归遍历：深度O(log n)到O(n)，每层O(1)，空间复杂度O(log n)到O(n)。尾递归优化后可以O(1)。