• 大O复杂度表示法
  
  T(n)表示代码执行的时间; n表示数据规模的大小; f(n) 表示每行代码执行的次数总和。因为这是一个公式， 所以用f(n)来表示。公式中的O,表示代码的执行时间T(n)与f(n)表达式成正比。
  大O时间复杂度实际上并不具体表示代码真正的执行时间，而是表示代码执行时间随数据规模增长的变化趋势，所以，也叫作渐进时间复杂度(asymptotic time complexity)，简称时间复杂度。
  • 复杂度分析原则
    1）单段代码看高频：比如循环。
    2）多段代码取最大：比如一段代码中有单循环和多重循环，那么取多重循环的复杂度。
    3）嵌套代码求乘积：比如递归、多重循环等
    4）多个规模求加法：比如方法有两个参数控制两个循环的次数，那么这时就取二者复杂度相加。
  • 时间复杂度分析
    只关注循环执行次数最多的一段代码
    加法法则：总复杂度等于量级最大的那段代码的复杂度
    乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积
  • 常见时间复杂度实例分析
  • 
  • 
    多项式阶：随着数据规模的增长，算法的执行时间和空间占用，按照多项式的比例增长。包括，
    O(1)（常数阶）、O(logn)（对数阶）、O(n)（线性阶）、O(nlogn)（线性对数阶）、O(n2)（平方阶）、O(n3)（立方阶）
    非多项式阶：随着数据规模的增长，算法的执行时间和空间占用暴增，这类算法性能极差。包括，
    O(2^n)（指数阶）、O(n!)（阶乘阶）
  • 空间复杂度分析
    表示算法的存储空间与数据规模之间的增长关系
  • 复杂度增长趋势图
  • 复杂度分析的4个概念
    • 最坏情况时间复杂度
      代码在最坏情况下执行的时间复杂度
    • 最好情况时间复杂度
      代码在最理想情况下执行的时间复杂度
    • 平均时间复杂度
      代码在所有情况下执行的次数的加权平均值
    • 均摊时间复杂度
      在代码执行的所有复杂度情况中绝大部分是低级别的复杂度，个别情况是高级别复杂度且发生具有时序关系时，可以将个别高级别复杂度均摊到低级别复杂度上。基本上均摊结果就等于低级别复杂度。
    • 背景
      1.同一段代码在不同情况下时间复杂度会出现量级差异，为了更全面，更准确的描述代码的时间复杂度，所以引入这4个概念。
      2.代码复杂度在不同情况下出现量级差别时才需要区别这四种复杂度。大多数情况下，是不需要区别分析它们的。