时间复杂度

算法代表着用系统的方法描述解决问题的策略机制。也就是说,能够对一定规范的输入,在有限时间内获得所要求的输出。

算法复杂度分为时间复杂度空间复杂度
其作用:

  • 时间复杂度是指执行算法所需要的计算工作量
  • 空间复杂度是指执行这个算法所需要的内存空间

常数时间的操作:一个操作如果和数据量没有关系,每次都是固定时间内完成的操作,叫做常数操作

时间复杂度为一个算法流程中,常数操作数量指标。常用O(读作big O)来表示。
具体来说,在常数操作数量的表达式中,\color{red}{只要高阶项,不要低阶项,也不要高阶项的系数,剩下的部分如果记为f(N),那么时间复杂度为O(f(N)。}

举个栗子
一个普通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)
\color{red}{那么根据只要高阶项,不要低阶项,也不要高阶项的系数,剩下的部分如果记为f(N),那么时间复杂度为O(f(N)。}
这次算法时间复杂度应去掉低阶项bN+1和N的系数A
f(N)=N^2, O(f(n))=O(N^2)

评价一个算法流程的好坏时间复杂度的指标,然后再分析不同数据样本下的实际运行时间,也就是常数项时间。

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成,浏览时请结合常识与多方信息审慎甄别。
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

相关阅读更多精彩内容

友情链接更多精彩内容