f*******w
发帖数: 1243 | 1 http://compprog.wordpress.com/2007/11/06/binary-numbers-countin
这个二进制counting bits的问题，里面说的Sparse one algorithm的复杂度是1的个数
可是每次需要对两个n-bits的二进制数做AND或者OR，应该是O(n)吧？ | G*******l
发帖数: 19 | 2 这个帖子还分了sparse和dense。。。厉害了。。。
这个是O(1), 因为那个循环至多执行32次或者64次（常数次）。。 | f*******w
发帖数: 1243 | 3
可是如果是这样的话，那counting bits这个问题本身就永远是常数次了啊……
【在 G*******l 的大作中提到】
: 这个帖子还分了sparse和dense。。。厉害了。。。
: 这个是O(1), 因为那个循环至多执行32次或者64次（常数次）。。
| g*********n
发帖数: 43 | 4 n is an "int", thus "AND" "OR" finishes in one instruction cycle? |
|
