时间复杂度入门：一次讲清 O(n) 与常见量级

时间复杂度是用来估算程序“数据变大时变慢多少”的标尺，不看具体跑了几毫秒，只看增长趋势。记作 O(…) 时，括号里只留增长最快的那一项，常数和低阶项都省掉，因为数据足够大时它们说了不算。

最常见的量级按从快到慢排：O(1)、O(log n)、O(n)、O(n log n)、O(n²)、O(2ⁿ)。O(1) 是不管数据多大都只做固定几步，比如按下标取数组元素；O(log n) 是每步砍掉一半，比如有序数组的二分查找，数据翻一倍只多一步；O(n) 是每个元素看一遍，比如求和、找最大值。O(n log n) 常见于高效排序；O(n²) 是两层循环互相套，比如冒泡排序和朴素的两两比较，数据翻一倍耗时约变四倍，数据一上规模就扛不住；O(2ⁿ) 是每多一个元素耗时翻倍，只适合很小的数据，基本是“写出来就知道不能用”的信号。

新手最容易踩的坑有三个：第一，只看循环层数不看循环次数，内层循环提前 break 或步长减半时量级会变；第二，把平均情况当成保证，二分查找要求有序、哈希查找最坏情况会退化，前提条件要先说清；第三，拿小数据测速度下结论，几百条数据上 O(n²) 可能比 O(n log n) 还快，量级只有在数据变大时才见分晓。

一句话总结：先看数据规模会不会涨，再看每步是不是在砍半、扫一遍还是套循环，量级定下来，选算法和估算耗时心里就有数了。