返回全部文章

刷题之前,我更想先建立复杂度直觉

很多人刷题时最难受的瞬间,不是“不会写”,而是:

很多人刷题时最难受的瞬间,不是“不会写”,而是:

不知道自己的思路到底算不算合理。

一个方案摆在眼前,你可能能写出来,但你心里没底:

  • 这样会不会超时
  • 这样是不是太慢
  • 这一步到底该不该优化

这类问题本质上都不是语法问题,而是复杂度直觉不够。

为什么复杂度直觉比刷题数量更重要

如果没有复杂度直觉,你做题时会反复遇到两个问题:

  1. 明明思路不对,却花很多时间把它实现完
  2. 明明思路已经够好了,却因为不自信继续乱改

这会让学习效率非常低。

复杂度直觉到底是什么

不是背 O(n)O(log n) 这些符号,而是看到一个过程时,脑子里能迅速判断:

  • 这大概会扫几遍数据
  • 有没有嵌套循环
  • 有没有重复计算
  • 数据规模一变大,哪里会先炸

一个最实用的起点

先不要追求特别复杂的方法,先把这几类判断练熟:

  • 一次遍历:通常是 O(n)
  • 双层遍历:通常是 O(n^2)
  • 每次规模减半:通常是 O(log n)
  • 排序后再扫:常见是 O(n log n)

很多题一开始只要先判断出这一级别,就已经能筛掉很多错误方向。

怎样训练这种直觉

看题时先不急着写

先问自己:

  • 数据规模是多少
  • 暴力做法大概是什么复杂度
  • 如果数据规模是 10^5,当前思路还能不能撑住

复盘时别只记答案

还要记:

  • 我一开始为什么没意识到这个复杂度太高
  • 这题真正被优化的是哪一层
  • 我以后遇到什么信号应该立刻警觉

复杂度直觉的真正价值

它不只是帮你刷题,更是在训练你做技术判断的能力。

因为很多工程问题本质上也是一样的:

  • 数据规模变大后哪里先出问题
  • 某种方案短期可用,长期为什么不稳
  • 哪一层才是真正的性能瓶颈

结论

刷题之前,如果你愿意先把复杂度直觉练起来,后面的很多方法学习都会更顺。

因为你不再只是“会不会写”,而是开始知道:

什么方向值得继续走,什么方向从一开始就该停下。