尧图网站建设 
最核心真相大部分人不是不会公式而是分不清循环次数、递归分支、访问几条边、有没有重复计算。图论、树、双重循环、递归最容易混淆。一、最常见的6个出错原因1、把代码“实际执行次数”和循环上限混在一起cppfor(int i0;in;i)for(int ji;jn;j)很多人直接写成 O(n^2)这个结论没错但有人误以为循环跑了 n\times n 次实际次数n(n‑1)…1\frac{n(n1)}{2}。时间复杂度看最高阶项常数、低阶全部扔掉所以还是 O(n^2)。坑不要被“少跑几次”迷惑大O是增长趋势不是精确次数。2、递归只看一层循环忽略分支数量树、DFS图遍历重灾区比如二叉树递归遍历void dfs(TreeNode *p){if(!p) return;dfs(p-left);dfs(p-right);}错误分析一层调用两次以为 O(2^n)。正确一共只访问n个结点每个结点一次O(n)。递归分析口诀看一共处理多少个元素而不是看调用了几个递归式子。3、图论顶点数 n边数 m经常搞混你写图论代码最容易踩- DFS / BFS遍历整张图每个顶点访问1次每条边访问1次时间 O(nm)超级高频错误写成 O(n^2)。只有邻接矩阵遍历才是 O(n^2)邻接表遍历是 O(nm)再举朴素Dijkstra邻接矩阵每次扫描全部n个点找最小值循环n次 → O(n^2)Dijkstra邻接表堆优化O(m\log n)408最容易错的一对邻接表遍历O(nm)邻接矩阵遍历O(n^2)4、循环里套了一个时间不为O(1)的函数漏掉内层代价for(int i0;in;i){vector.push_back(x);}push_back均摊O(1)总O(n)没问题。但如果循环里面又嵌套了一次遍历数组就要叠加代价。很多人只看外层循环n次忽略内层。5、分不清最好、最坏、平均时间复杂度以快排举例- 最坏 O(n^2)- 平均 O(n\log n)408题目如果没特别说明排序算法默认写最坏时间复杂度。6、对数复杂度什么时候出现很多人凭感觉乱写logn出现 O(\log n) 典型场景1. 每次问题规模 /2二分查找2. 平衡二叉搜索树查找3. 堆操作树高 \log n普通二叉树最坏树高n查找最坏 O(n)不是 \log n二、万能分析步骤以后每次严格照着4步走正确率暴涨步骤1找出代码中最内层重复执行的核心语句只看被反复跑的那条干活代码跳过if判断、return。步骤2求这条语句最多会被执行多少次分三类场景1. 循环代码数循环执行多少次2. 树递归一共访问多少结点每个结点访问几次3. 图代码n顶点、m边邻接表还是邻接矩阵步骤3写出精确表达式扔掉常数、低阶项3n^25n100 →最高阶 n^2 →O(n^2)O(2n) 和 O(n) 等价常数直接丢掉。步骤4对照常见复杂度清单检验从小到大顺序O(1)O(\log n)O(n)O(n\log n)O(n^2)O(n^3)O(2^n)三、图论专属速查表背下来杜绝分析错误n顶点数m边数1. DFS/BFS邻接表O(nm)2. DFS/BFS邻接矩阵O(n^2)3. 朴素Dijkstra邻接矩阵O(n^2)4. Floyd‑Warshall三重循环 O(n^3)5. Prim朴素邻接矩阵O(n^2)6. Kruskal排序边 O(m\log m)7. 拓扑排序 Kahn(邻接表)O(nm)四、最容易混淆的一组对比高频错题1. 遍历二叉树n结点 → O(n)2. 遍历图邻接表 → O(nm)3. 遍历图邻接矩阵 → O(n^2)千万不要看到递归DFS就直接写指数复杂度五、训练方法快速把时间复杂度练稳1. 写完一段代码强制自己用上面4步口头分析一遍2. 专门刷「判断时间复杂度」的选择题做完对比答案3. 错题一定要标注错因- 是把邻接表写成n²- 递归误以为指数- 丢了内层循环代价 【方法论】时间复杂度易错点
最核心真相大部分人不是不会公式而是分不清循环次数、递归分支、访问几条边、有没有重复计算。图论、树、双重循环、递归最容易混淆。一、最常见的6个出错原因1、把代码“实际执行次数”和循环上限混在一起cppfor(int i0;in;i)for(int ji;jn;j)很多人直接写成 O(n^2)这个结论没错但有人误以为循环跑了 n\times n 次实际次数n(n‑1)…1\frac{n(n1)}{2}。时间复杂度看最高阶项常数、低阶全部扔掉所以还是 O(n^2)。坑不要被“少跑几次”迷惑大O是增长趋势不是精确次数。2、递归只看一层循环忽略分支数量树、DFS图遍历重灾区比如二叉树递归遍历void dfs(TreeNode *p){if(!p) return;dfs(p-left);dfs(p-right);}错误分析一层调用两次以为 O(2^n)。正确一共只访问n个结点每个结点一次O(n)。递归分析口诀看一共处理多少个元素而不是看调用了几个递归式子。3、图论顶点数 n边数 m经常搞混你写图论代码最容易踩- DFS / BFS遍历整张图每个顶点访问1次每条边访问1次时间 O(nm)超级高频错误写成 O(n^2)。只有邻接矩阵遍历才是 O(n^2)邻接表遍历是 O(nm)再举朴素Dijkstra邻接矩阵每次扫描全部n个点找最小值循环n次 → O(n^2)Dijkstra邻接表堆优化O(m\log n)408最容易错的一对邻接表遍历O(nm)邻接矩阵遍历O(n^2)4、循环里套了一个时间不为O(1)的函数漏掉内层代价for(int i0;in;i){vector.push_back(x);}push_back均摊O(1)总O(n)没问题。但如果循环里面又嵌套了一次遍历数组就要叠加代价。很多人只看外层循环n次忽略内层。5、分不清最好、最坏、平均时间复杂度以快排举例- 最坏 O(n^2)- 平均 O(n\log n)408题目如果没特别说明排序算法默认写最坏时间复杂度。6、对数复杂度什么时候出现很多人凭感觉乱写logn出现 O(\log n) 典型场景1. 每次问题规模 /2二分查找2. 平衡二叉搜索树查找3. 堆操作树高 \log n普通二叉树最坏树高n查找最坏 O(n)不是 \log n二、万能分析步骤以后每次严格照着4步走正确率暴涨步骤1找出代码中最内层重复执行的核心语句只看被反复跑的那条干活代码跳过if判断、return。步骤2求这条语句最多会被执行多少次分三类场景1. 循环代码数循环执行多少次2. 树递归一共访问多少结点每个结点访问几次3. 图代码n顶点、m边邻接表还是邻接矩阵步骤3写出精确表达式扔掉常数、低阶项3n^25n100 →最高阶 n^2 →O(n^2)O(2n) 和 O(n) 等价常数直接丢掉。步骤4对照常见复杂度清单检验从小到大顺序O(1)O(\log n)O(n)O(n\log n)O(n^2)O(n^3)O(2^n)三、图论专属速查表背下来杜绝分析错误n顶点数m边数1. DFS/BFS邻接表O(nm)2. DFS/BFS邻接矩阵O(n^2)3. 朴素Dijkstra邻接矩阵O(n^2)4. Floyd‑Warshall三重循环 O(n^3)5. Prim朴素邻接矩阵O(n^2)6. Kruskal排序边 O(m\log m)7. 拓扑排序 Kahn(邻接表)O(nm)四、最容易混淆的一组对比高频错题1. 遍历二叉树n结点 → O(n)2. 遍历图邻接表 → O(nm)3. 遍历图邻接矩阵 → O(n^2)千万不要看到递归DFS就直接写指数复杂度五、训练方法快速把时间复杂度练稳1. 写完一段代码强制自己用上面4步口头分析一遍2. 专门刷「判断时间复杂度」的选择题做完对比答案3. 错题一定要标注错因- 是把邻接表写成n²- 递归误以为指数- 丢了内层循环代价