壹｜为什么需要复杂度分析

我们需要拥有直接估计算法执行效率的方法。
如果没有复杂度分析，我们需要通过统计、监控来得到执行时间和占用内存大小。
事后统计法具有两个局限性。一个是测试环境，一个是数据规模。

贰｜什么是时间复杂度

时间复杂度表示代码执行时间随数据规模增长的变化趋势。
我们用大O来表示时间复杂度。

叁｜什么是空间复杂度

空间复杂度表示算法的存储空间随数据规模增长的变化趋势。
我们依然用大O来表示空间复杂度。
空间复杂度考虑的是程序运行时占用的内存大小，不是可执行文件的大小

肆｜时间复杂度分析

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

    伍｜时间复杂度问题拓展

    Q1：O(logn) 以什么为底？

    O(login) = O(logij * logjn)，logij是一个常数系数，可以忽略，所以O(login) = O(logjn)。
    时间复杂度O(login)无论未知数i是什么，时间复杂度都可以表示为logjn，而j也是未知数。
    所以，对数阶时间复杂度可以忽略对数的底，统一表示为O(logn)。

    Q2：递归的时间复杂度？

    递归的时间复杂度计算需要看递归的次数。