评估算法优劣的核心指标

  • 时间复杂度（流程决定）

时间复杂度就是算法流程中发生了多少次常数操作。
复杂度与具体的常系数无关
多项式级的复杂度相加的时候，选择高者作为结果。

  • 额外空间复杂度（流程决定）

  • 常数项时间（实现细节决定）

    何为常数时间的操作？

    如果一个操作的执行时间不以 具体样本量为转移，每次执行时间都是固定的。

    常见的常数时间的操作

  • 常见的算术运算（+、-、*、/、% 等）

  • 常见的位运算（>>、>>>、<<、|、&、^等）
  • 赋值、比较、自增、自减等操作
  • 数组寻址操作

总之，执行时间固定的操作都是常数时间的操作。
反之，执行时间不固定的操作，都不是常数时间的操作。（例如LinkedList）

如何确定算法流程的总操作数量与样本数量之间的表达式关系？

  • 想象该算法流程所处理的数据状况，要按照最差情况来。
  • 把整个流程彻底拆分为一个个基本动作，保证每个动作都是常数时间的操作。
  • 如果数据量为N，看看基本动作的数量和N是什么关系。

    如何确定算法流程的时间复杂度？

    当完成了表达式的建立，只要把最高阶项留下即可。低阶项都去掉，高阶项的系数也去掉。
    记为：O(忽略掉系数的高阶项)

    时间复杂度的意义

    抹掉了好多东西，只剩下了一个最高阶项啊…
    那这个东西有什么意义呢？
    时间复杂度的意义在于：
    当我们要处理的样本量很大很大时，我们会发现低阶项是什么不是最重要的；每一项的系数是什么，不是最重要的。真正重要的就是最高阶项是什么。
    这就是时间复杂度的意义，它是衡量算法流程的复杂程度的一种指标，该指标只与数据量有关，与过程之外的优化无关。