算法代表着用系统的方法描述解决问题的策略机制。也就是说,能够对一定规范的输入,在有限时间内获得所要求的输出。
算法复杂度分为时间复杂度和空间复杂度。
其作用:
- 时间复杂度是指执行算法所需要的计算工作量;
- 空间复杂度是指执行这个算法所需要的内存空间。
常数时间的操作:一个操作如果和数据量没有关系,每次都是固定时间内完成的操作,叫做常数操作。
时间复杂度为一个算法流程中,常数操作数量的指标。常用O(读作big O)来表示。
具体来说,在常数操作数量的表达式中,
举个栗子
一个普通N个数字的从小到大排序
a1,a2,a3,a4,a5,a6,a7
每次排序找到最小值放在前面
第一次需要遍历N-1遍取比较得到最小值放在首位
第二次遍历除了第一位的剩下值,需要遍历N-2遍取比较得到最小值放在第二位,
第三次遍历除了前两位的剩下值,需要遍历N-3遍取比较得到最小值放在第三位,
以此大概需要(N-1+N-2+N-3+N-4....+3+2+1)次,每次操作是一个常数时间操作记为O(1)(读作bigO(1))
所以整个时间化简复杂度应该是(N^2 /2+N+1)*O(1),也就是(aN^2+bN+1)*O(1)
这次算法时间复杂度应去掉低阶项bN+1和N的系数A
f(N)=N^2, O(f(n))=O(N^2)
评价一个算法流程的好坏,先看时间复杂度的指标,然后再分析不同数据样本下的实际运行时间,也就是常数项时间。