分析公式

image.png

T(n) 表示代码执行的时间；n 表示数据规模的大小；

f(n) 表示每行代码执行的次数总和。因为这是一个公式，所以用 f(n) 来表示。

公式中的 O，表示代码的执行时间 T(n) 与 f(n) 表达式成正比。

image.png

当 n 很大时，你可以把它想象成 10000、100000。而公式中的低阶、常量、系数三部分并不左右增长趋势，所以都可以忽略。我们只需要记录一个最大量级就可以了，如果用大 O 表示法表示刚讲的那两段代码的时间复杂度，就可以记为：

image.png

总结

  1. 只关注循环执行次数最多的一段代码
  2. 加法法则：总复杂度等于量级最大的那段代码的复杂度
  3. 乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积

image.png