Python 的 int.bit_length() 的最坏情况时间复杂度 [英] Worst-case time complexity of Python's int.bit_length()

问题描述

当我们调用函数 int.bit_length 时一个整数 n，是最坏情况下的时间复杂度 O(log(n)) 或者 Python 使用一些技巧来改进它(例如，存储 n 的最高有效位的位置，当它已创建)?

When we call the function int.bit_length passing an integer n, is the worst-case time complexity O(log(n)) or Python uses some trick to improve it (e.g. storing the position of the most significant bit of n when it is created)?

推荐答案

在 CPython 中，对于内部表示数字少于 PY_SSIZE_T_MAX/PyLong_SHIFT 的值 - 即少于 PY_SSIZE_T_MAX 二进制数字 - 它是根据内部位数，是:

In CPython, for values with fewer internal-representation digits than PY_SSIZE_T_MAX/PyLong_SHIFT – i.e. fewer than PY_SSIZE_T_MAX binary digits – it’s calculated from the number of internal digits, yes:

msd = ((PyLongObject *)self)->ob_digit[ndigits-1];
msd_bits = bits_in_digit(msd);

if (ndigits <= PY_SSIZE_T_MAX/PyLong_SHIFT)
    return PyLong_FromSsize_t((ndigits-1)*PyLong_SHIFT + msd_bits);

否则，它会再次通过 bigint，对于 O(log log N) 的整体时间复杂度(这在实践和理论的奇怪组合中也不完全正确，所以......).

Otherwise, it goes through bigints again, for overall time complexity of O(log log N) (which isn’t exactly true either in this strange mix of practice and theory, so…).

/* expression above may overflow; use Python integers instead */
result = (PyLongObject *)PyLong_FromSsize_t(ndigits - 1);
if (result == NULL)
    return NULL;
x = (PyLongObject *)PyLong_FromLong(PyLong_SHIFT);
if (x == NULL)
    goto error;
y = (PyLongObject *)long_mul(result, x);
Py_DECREF(x);
if (y == NULL)
    goto error;
Py_DECREF(result);
result = y;

x = (PyLongObject *)PyLong_FromLong((long)msd_bits);
if (x == NULL)
    goto error;
y = (PyLongObject *)long_add(result, x);
Py_DECREF(x);
if (y == NULL)
    goto error;
Py_DECREF(result);
result = y;

return (PyObject *)result;

tl;dr:它是 O(1)

tl;dr: it’s O(1)

这篇关于Python 的 int.bit_length() 的最坏情况时间复杂度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！