分析时间复杂度-万能方法论适合循环嵌套、递归、树、图、分治、复杂代码任何代码都可以套用这套流程。大O本质找随着 n 变大开销增长最快的那一项抛弃常数、低阶一、通用五步法固定顺序每次严格照做步骤1定位「代价点」找到最内层、重复执行的核心操作赋值、比较、访问结点if、return、函数声明不算干活语句不计次数。例子cppfor(i0;in;i)for(j0;jn;j)a[i][j]0; // ←代价点步骤2写出代价点最多执行多少次分 3 大类场景① 迭代for‑while循环数清楚外层跑几次内层跑几次内层次数是不是依赖外层变量(i)。cppfor(i1;in;i)for(j1;ji;j)总次数 123\dotsn\dfrac{n(n1)}{2}② 递归代码最难两条路线二选一1计数法优先408首选一共访问多少元素每个元素被处理几次二叉树遍历n个结点每个访问1次 →总次数 n → O(n)2递推公式T(n)写出时间递推式 T(n)然后解出来经典分治T(n)2T(n/2)O(n) → 主定理结果 O(n\log n)③ 图 / 网格结构记住两个变量n顶点、m边邻接表遍历所有顶点所有边各走一遍总开销O(nm)邻接矩阵扫描整张 n×n 表格开销O(n^2)步骤3写出精确求和表达式循环→求和公式递归→T(n)递推式图→顶点边之和。步骤4取最高阶项扔掉所有常数、低阶项规则- 5n^23n7 →最高阶 n^2 → O(n^2)- 2n →扔掉常数 2 → O(n)- nn\log n → n\log n 增长更快O(n\log n)只有最高阶留下步骤5校验防翻车最后一步对照复杂度从小到大梯队判断是否合理O(1)O(\log n)O(n)O(n\log n)O(n^2)O(n^3)O(2^n)二、三大难题工具复杂复杂度专用工具1求和公式 ——对付多层循环只要嵌套循环就把内层循环次数写成求和\sum_{i1}^{n}\sum_{j1}^{i} 1算出结果再取最高阶。常见求和\sum_{i1}^n i\frac{n(n1)}{2}\Rightarrow O(n^2)\sum_{i1}^n \log i\Rightarrow O(n\log n)工具2递归 ——主定理解分治递推式神器形如T(n)a\,T\left(\frac{n}{b}\right)f(n)a子问题数量n/b每个子问题规模f(n)分割合并开销三条判定规则1. 如果 f(n)n^{\log_b a} → T(n)O(n^{\log_b a})2. 如果 f(n)n^{\log_b a} → T(n)O(n^{\log_b a}\log n)3. 如果 f(n)n^{\log_b a} → T(n)O(f(n))408常考例子归并排序T(n)2T(n/2)O(n)a2,b2,\log_2 21,\,f(n)n^1相等→O(n\log n)⚠注意主定理只能用于子问题规模均等平分图DFS、树遍历递归不要用主定理优先「结点计数法」工具3收支法 / 势能分析法摊还复杂度对付vector动态扩容、并查集路径压缩。并查集时间不是简单O(1)是摊还近乎常数 \boldsymbol{\alpha(n)}阿克曼反函数几乎等于1408一般直接写近似 O(1)三、三类高频易错场景「判定口诀」背下来1树递归数结点不要数递归调用次数每个结点处理1次n结点就是 O(n)平衡二叉搜索树查找树高 \log n → O(\log n)普通斜树最坏树高 n → O(n)2图代码你最头疼邻接表遍历顶点边 \boldsymbol{O(nm)}邻接矩阵遍历扫整张表 \boldsymbol{O(n^2)}3循环里面有log每次规模除以 2 →大概率带 \log nwhile(kn) k*2; //循环次数 logn四、避坑检查清单分析完核对一遍✅有没有漏掉内层循环代价✅递归是不是误把递归分支数当成指数复杂度✅图邻接表/邻接矩阵有没有搞混✅是不是把常数系数保留进复杂度了✅最坏/平均复杂度有没有搞混排序题默认最坏五、实战演示一遍完整走流程代码for(int i1;in;i){int ji;while(jn) j i;}步骤1代价点j i步骤2‑3求和i从1~n内层循环次数 n/i总次数\sum_{i1}^{n}\frac{n}{i}n\sum\frac1i调和级数≈n\ln n步骤4最高阶n\log n步骤5校验 →结果 \boldsymbol{O(n\log n)}