推荐学习书目 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 2366 次点击这是一个创建于 1703 天前的主题，其中的信息可能已经有所发展或是发生改变。
假设某整数 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