1.评估算法优劣的核心指标:

时间复杂度(流程决定)、额外空间复杂度(流程决定)、常数项时间(实现细节决定)

2.常数时间的操作:

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

2.1常见的常数时间的操作:

常见的算术运算(+,-,*,/,%等)
常见的位运算(>>,>>>,<<,|,&,^等)
赋值、比较、自增、自减操作等
数组寻址操作。
总之,执行时间固定的操作都是常数时间的操作。反之,执行时间不固定的操作都不是常数时间的操作。

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

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

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

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

3. 额外空间复杂度

实现一个算法流程,在实现算法流程的过程中,需要开辟一些空间来支持算法流程。
作为输入参数的空间,不算额外空间。作为输出结果的空间,不算额外空间。因为这些都是必要的 和实现目标有关的,所以都不算。但除此之外,你的流程还需要开辟空间才能让流程继续下去,这部分空间就是额外空间。
如果流程只需要开辟几个有限变量,额外空间复杂度就是O(1)。

4.算法流程的常数项

时间复杂度只是一个很重要的指标,如果两个时间复杂度一样的算法,还要去时间上拼优劣,就进入到拼常数时间的阶段,简称拼常数项。