鱼C论坛

 找回密码
 立即注册
查看: 3393|回复: 2

[已解决]我对算法时间复杂度的大o阶的推导有些疑问

[复制链接]
发表于 2019-5-6 10:53:47 | 显示全部楼层 |阅读模式
5鱼币
推导大O阶一般是三个步骤:
1、去常数项;
2、保留最高项,去其他低次项;
3、去最高项的系数

一般来说考虑一个算法的时间复杂度,默认的运算次数都在十万、百万次等以上的级别,这样1、2两项挺好理解的,常数项和低次项基本属于零头可以忽略,但是3、去掉系数我就不能理解了,乘1和乘10都不是一个数量级的,很明显乘1的要好于乘10的。
我认为第3个步骤是不合理的,有没有实际开发经验者谈一谈这个
最佳答案
2019-5-6 10:53:48
当n较小时,分析时间复杂度没有太大意义,一般是考虑极限情况,当n足够大的时候,影响整个表达式的值的不是常数,而是n,这就跟保留最高项去掉其他项是一个意思,另外常数确实是会影响算法性能的,在算法竞赛中,有一种情况就叫"卡常",因为算法时间复杂度中常数项导致程序超时。

最佳答案

查看完整内容

当n较小时,分析时间复杂度没有太大意义,一般是考虑极限情况,当n足够大的时候,影响整个表达式的值的不是常数,而是n,这就跟保留最高项去掉其他项是一个意思,另外常数确实是会影响算法性能的,在算法竞赛中,有一种情况就叫"卡常",因为算法时间复杂度中常数项导致程序超时。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2019-5-6 10:53:48 | 显示全部楼层    本楼为最佳答案   
当n较小时,分析时间复杂度没有太大意义,一般是考虑极限情况,当n足够大的时候,影响整个表达式的值的不是常数,而是n,这就跟保留最高项去掉其他项是一个意思,另外常数确实是会影响算法性能的,在算法竞赛中,有一种情况就叫"卡常",因为算法时间复杂度中常数项导致程序超时。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2019-6-1 23:53:56 | 显示全部楼层
当n足够大的时候,系数就可以被忽略了,另外在探讨算法的时候,不会刻意的去考虑乘1和乘10对硬件计算时间的差别
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-12-23 22:42

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表