一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 1054|回复: 23
收起左侧

[算法题] Amazon GrayCheck 那道题的时间复杂度讨论

[复制链接] |试试Instant~ |关注本帖
sherry900105 发表于 2015-2-22 05:14:55 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
看OA有一道题是判断两个byte是否互为gray code

然后看到了一个帖子有两种答案

一个是while循环那种

另一个就是直接bit运算的

bit运算那种应该是O(1)没错了, while循环那种怎么都觉得不是O(n)啊, 总觉得是logn级别的。。求大牛解释~~

谢谢么么哒~


 楼主| sherry900105 发表于 2015-2-22 05:17:39 | 显示全部楼层
while循环那种情况是这样的:

int x = (byte)(term1 ^ term2);
while(x != 0){                        
            x = (byte)(x & (x - 1));                        
            count++;               
        }               
        return count == 1 ? 1:0;

个人觉得因为while不是完全遍历了x里面的所有位, 只是挑出了x中的1逐位变为0, 所以总觉得是logn级别的。。应该不是O(n)
回复 支持 反对

使用道具 举报

xjwun 发表于 2015-2-22 05:42:03 | 显示全部楼层
sherry900105 发表于 2015-2-22 05:17
while循环那种情况是这样的:

int x = (byte)(term1 ^ term2);

感觉worst还是O(N)吧,
回复 支持 反对

使用道具 举报

 楼主| sherry900105 发表于 2015-2-22 05:44:10 | 显示全部楼层
xjwun 发表于 2015-2-22 05:42
感觉worst还是O(N)吧,

你是指所有位都是1的情况么。。但是不能看worst啊。。二分查找worst还是n呢。。。
回复 支持 反对

使用道具 举报

 楼主| sherry900105 发表于 2015-2-22 05:45:12 | 显示全部楼层
xjwun 发表于 2015-2-22 05:42
感觉worst还是O(N)吧,

不对不对说错了。。。= =有个排序算法的worst是n。。脑子都乱了。。
回复 支持 反对

使用道具 举报

xjwun 发表于 2015-2-22 05:48:24 | 显示全部楼层
sherry900105 发表于 2015-2-22 05:45
不对不对说错了。。。= =有个排序算法的worst是n。。脑子都乱了。。

个人感觉这个code要数所有为1的为,最后判断是不是只有一位为1,所以我觉得不能像二分那样变成logn,因为每次没有什么丢掉一半的情况,我也不知道对不对,期待大牛解答哈
回复 支持 反对

使用道具 举报

xjwun 发表于 2015-2-22 05:49:21 | 显示全部楼层
sherry900105 发表于 2015-2-22 05:45
不对不对说错了。。。= =有个排序算法的worst是n。。脑子都乱了。。

你说的快排吧
回复 支持 反对

使用道具 举报

 楼主| sherry900105 发表于 2015-2-22 06:00:16 | 显示全部楼层

但是实际上位运算这种底层运算应该不是String字符串判断那种一位一位比较啊 我觉得位运算的话应该是直接定位到为1的那个位然后变成0 所以应该是直接忽略了所有的0位 这样的话时间复杂度肯定是小于n大于1的 只有可能是log级的。。不知道这么分析对不对。。
回复 支持 反对

使用道具 举报

zengm321 发表于 2015-2-22 07:06:43 | 显示全部楼层
sherry900105 发表于 2015-2-22 05:17
while循环那种情况是这样的:

int x = (byte)(term1 ^ term2);

不是O(n), 而是O(1), 因为就只有32bit而已
回复 支持 反对

使用道具 举报

 楼主| sherry900105 发表于 2015-2-22 07:22:26 | 显示全部楼层
zengm321 发表于 2015-2-22 07:06
不是O(n), 而是O(1), 因为就只有32bit而已

那那个while循环的复杂度也只有O1?!
回复 支持 反对

使用道具 举报

xiaoxin213 发表于 2015-2-22 08:17:17 | 显示全部楼层
为啥要while循环?(x & (x - 1))不就是在检查是否只有一个1么??

我觉得是这样:
if(x != 0) return (x & (x - 1)) == 0 ? true :false;
else return false;
回复 支持 反对

使用道具 举报

 楼主| sherry900105 发表于 2015-2-22 08:46:04 | 显示全部楼层
xiaoxin213 发表于 2015-2-22 08:17
为啥要while循环?(x & (x - 1))不就是在检查是否只有一个1么??

我觉得是这样:

据说是因为case过不了才要加个while..我也觉得不需要while啊。。= =
回复 支持 反对

使用道具 举报

xiaoxin213 发表于 2015-2-22 11:46:04 | 显示全部楼层
sherry900105 发表于 2015-2-22 08:46
据说是因为case过不了才要加个while..我也觉得不需要while啊。。= =

哪个case??
回复 支持 反对

使用道具 举报

 楼主| sherry900105 发表于 2015-2-23 00:19:13 | 显示全部楼层

不知道啊。。我又没做过oa。。是地里小伙伴说的~
回复 支持 反对

使用道具 举报

Larrylianj 发表于 2015-2-25 13:34:31 | 显示全部楼层
不是text case过不了, x & (x-1) 目的是去除最右边一个1。那个算法的思想是不断去除最右边的1看是否为0,这个算法只有在 答案是正确的时候(是gray code)才会比查遍8位累计1的个数的时间复杂度要少。
回复 支持 反对

使用道具 举报

 楼主| sherry900105 发表于 2015-2-26 01:16:11 | 显示全部楼层
Larrylianj 发表于 2015-2-25 13:34
不是text case过不了, x & (x-1) 目的是去除最右边一个1。那个算法的思想是不断去除最右边的1看是否为0, ...

我看题目的意思是只需要check是不是互为格雷码啊。。要是超过一个1不就不是了么。。还用继续check么。。。
回复 支持 反对

使用道具 举报

LUOLUOLNSH 发表于 2015-3-6 11:43:02 | 显示全部楼层
楼主 想问问在地里哪里看到答案 能share下帖子吗?多谢啦~~
回复 支持 反对

使用道具 举报

xjwun 发表于 2015-3-6 11:45:51 | 显示全部楼层
Larrylianj 发表于 2015-2-25 13:34
不是text case过不了, x & (x-1) 目的是去除最右边一个1。那个算法的思想是不断去除最右边的1看是否为0, ...

但是只有八位,所以还是O(1) ?谢谢!
回复 支持 反对

使用道具 举报

天空的一点 发表于 2015-3-6 13:18:55 | 显示全部楼层
这题不是O(1)么,循环走8次,然后计算bit也是计算八次,怎么是O(n)呢
回复 支持 反对

使用道具 举报

lchen77 发表于 2015-3-6 18:04:50 | 显示全部楼层
话说我怎么觉得用while 循环时, 应该是   
while (res_ox)
36          {
37             if (res_ox & 0x1) count_one++;
38             res_ox = res_ox >> 1;
39          }
这样才是一位一位比较吧?复杂度 O(n), n 是位数,不是数字的太小。
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-5 08:37

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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