12 3 / 3 页下一页

论坛徽章:: 0

电梯直达

1楼 [收藏(0)] [报告]

发表于 2007-05-24 09:03 |只看该作者 |倒序浏览

我想请教一个算法，有一无符号32位整数，求其右边第一位数起到第一个位为‘1’的0的个数。
如0x21c534a8，则返回3；0x1b94a4c0，则返回6。
用循环好做，但时间复杂度不是常数。有时间复杂度为常数的算法吗，谢谢大家

文库|博客

疯长的野草

白手起家

论坛徽章:: 0

2楼 [报告]

发表于 2007-05-24 09:39 |只看该作者

时间复杂度不是常数？什么是实践复杂度啊

实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？

cugb_cat

版主

论坛徽章:: 0

3楼 [报告]

发表于 2007-05-24 09:51 |只看该作者

原帖由 疯长的野草 于 2007-5-24 09:39 发表
时间复杂度不是常数？什么是实践复杂度啊

建议你碰到不知道概念先google或看书

实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？

ypxing

家境小康

论坛徽章:: 0

4楼 [报告]

发表于 2007-05-24 09:58 |只看该作者

原帖由 heavyrain44 于 2007-5-24 09:03 发表
我想请教一个算法，有一无符号32位整数，求其右边第一位数起到第一个位为‘1’的0的个数。
如0x21c534a8，则返回3；0x1b94a4c0，则返回6。
用循环好做，但时间复杂度不是常数。有时间复杂度为常数的算法吗，谢谢 ...

不是常数是什么?
你最多需要检查32位
所以是O(1)

楼主是不是说要对n位的整数进行计算?

[ 本帖最后由 ypxing 于 2007-5-24 10:06 编辑 ]

实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？

heavyrain44

白手起家

论坛徽章:: 0

5楼 [报告]

发表于 2007-05-24 10:13 |只看该作者

楼上的那位，您这样说也对，但显然检查0x21c534a8跟检查0x1b94a4c0所需要的时间是不一样的。您所说的时间是常数，只是说最坏的情况下所需要的时间是常数而已。
我希望检查所有数据所需要的时间都是一样的，而且越快越好

[ 本帖最后由 heavyrain44 于 2007-5-24 10:16 编辑 ]