时间复杂度

常见的常数时间的操作

• 常见算术运算(+ - * / %)
• 常见位运算(>> >>> << | & ^)
• 赋值 比较 自增 自减
• 数组寻址操作

总之:

时间固定的操作就是常数时间的操作
时间不固定的操作就不是常数时间的操作

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

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

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

当完成了表达式的建立,只要把最高阶项留下即可.低阶项都去掉,高阶项的系数也都去掉.

记为: O (忽略掉系数的高阶项)

时间复杂度的意义

只留下最高阶项

样本量大的时候,发现低阶项是什么不是最重要的;没意向的系数是什么不是最重要的.真正重要的就是最高阶项是什么.

额外空间复杂度

在实现一个算法流程中,需要开辟一些空间来支持你的算法流程

作为输入参数的空间,不算额外空间

作为输出参数的空间,不算额外空间

如果你的流程只需要开辟有限几个变量,额外空间复杂度就是O(1)

对数器

1. 你想要测得方法a
2. 实现复杂度不好但是容易实现的方法b
3. 实现一个随机样本产生器
4. 把方法a和方法b跑相同的随机样本,看看得到的结果是否一样
5. 如果有一个随机样本使得比对结果不一致,打印样本进行人工干预,改对方法a和方法b
6. 当样本数量很多时对比测试依然正确,可以确定方法a已经正确.