推荐学习书目
› Learn Python the Hard Way
Python Sites
› PyPI - Python Package Index
› http://diveintopython.org/toc/index.html
› Pocoo
值得关注的项目
› PyPy
› Celery
› Jinja2
› Read the Docs
› gevent
› pyenv
› virtualenv
› Stackless Python
› Beautiful Soup
› 结巴中文分词
› Green Unicorn
› Sentry
› Shovel
› Pyflakes
› pytest
Python 编程
› pep8 Checker
Styles
› PEP 8
› Google Python Style Guide
› Code Style from The Hitchhiker's Guide
Python 的 int.bit_length() 函数的时间复杂度是多少呢？
littleMaple · MapleCCC · 2021-02-12 20:02:47 +08:00 · 2015 次点击这是一个创建于 1381 天前的主题，其中的信息可能已经有所发展或是发生改变。
假设某整数 x 的二进制最高有效位位数为 n，那么 x.bit_length() 的时间复杂度是 O(n) 还是 O(1) 呢？
 |
1
mogg 2021-02-12 20:08:40 +08:00
log n 啊……
|
|
2
mogg 2021-02-12 20:13:54 +08:00  1
对不起看错了，常规算法是 O(log x ) or O(n)
固定位数有优化到 O(log 32/64……)的算法（记得 csapp 上有） Python 的具体实现得看看源码（ |
 |
3
lxy42 2021-02-12 20:34:54 +08:00 1
正好在看 Python 源码, [int_bit_length_impl]( https://github.com/python/cpython/blob/master/Objects/longobject.c#L5256).
从源码来看是 O(1). |
 |
4
littleMaple OP @lxy42 #3 感谢解惑！
|
|
5
littleMaple OP @mogg #2 感谢回复！我这就去看 CSAPP，之前一直放着.
|
 |
6
msg7086 2021-02-13 04:22:19 +08:00 via Android 1
本质上应该是 lzcnt 吧，让 CPU 算的话是常数时间。
徒手算的话应该也能优化到常数时间。 |
Select Language