1.何为常数时间的操作?
如果一个操作的执行时间不以具体样本量为转移,每次执行时间都是固定时间。称这样的操作为常数时间的操作。
2.常见的常数时间的操作
•常见的算术运算(+、-、*、/、%等)
•常见的位运算(>>、>>>、<<、|、&、^等)
•赋值、比较、自增、自减操作等
•数组寻址操作
总之,执行时间固定的操作都是常数时间的操作;反之,执行时间不固定的操作,都不是常数时间的操作。
3.如何确定算法流程的总操作数量与样本数量之间的表达式关系?
1)想象该算法流程所处理的数据状况,要按照最差情况来。
2)把整个流程彻底拆分为一个个基本动作,保证每个动作都是常数时间的操作。
3)如果数据量为N,看看基本动作的数量和N是什么关系。
4.如何确定算法流程的时间复杂度?
当完成了表达式的建立,只要把最高阶项留 下即可。低阶项都去掉,高阶项的系数也去掉。
记为:O(忽略掉系数的高阶项)
5.时间复杂度的意义
抹掉了好多东西,只剩下了一个最高阶项啊…
那这个东西有什么意义呢?
时间复杂度的意义在于:
当我们要处理的样本量很大很大时,我们会发现低阶项是什么不是最重要的;每一项的系数是什么,不
是最重要的。真正重要的就是最高阶项是什么。
这就是时间复杂度的意义,它是衡量算法流程的复杂程度的一种指标,该指标只与数据量有关,与过程
之外的优化无关。
注意
1.算法的过程,和具体的语言是无关的。
2.想分析一个算法流程的时问复杂度的前提,是对该流程非常熟悉
3.一 定要确保在拆分算法流程时,拆分出来的所有行为都是常数时间的操作。这意味着你写算法时,对自己的用过的每一个系统api,都非常的熟悉。否则会影响你对时间复杂度的估算。
评估算法优劣的核心指标是什么?
时间复杂度(流程决定)
额外空间复杂度(流程决定)
常数项时间(实现细节决定)
算法和数据结构学习的大脉络
1)知道怎么算的算法 2) 知道怎么试的算法