常数时间的操作:一个操作如果和数据量没有关系,每次都是固定时间内完成的操作,叫做常数操作。
时间复杂度为一个算法流程中,常数操作数量的指标。常用O(读作big O)来表示。具体来说,在常数操作数量的表达式中,只要高阶项,不要低阶项,也不要高阶项的系数,剩下的部分如果记为f(N),那么时间复杂度为O(f(N))。
评价一个算法流程的好坏,先看时间复杂度的指标,然后再分析不同数据样本下的实际运行时间,也就是常数项时间。
额外空间复杂度:在执行代码过程中申请的额外存储空间,比如变量,有限个变量则O(1),分析额外空间复杂度和时间复杂度类似。
一个简单的理解时间复杂度的例子
一个有序数组A,另一个无序数组B,请打印B中的所有不在A中的数,A数
组长度为N,B数组长度为M。
算法流程1:对于数组B中的每一个数,都在A中通过遍历的方式找一下;
算法流程2:对于数组B中的每一个数,都在A中通过二分的方式找一下;
算法流程3:先把数组B排序,然后用类似外排的方式打印所有在A中出现
的数;
三个流程,三种时间复杂度的表达...
如何分析好坏?
原文:https://www.cnblogs.com/xuechengmeigui/p/13083053.html