В худшем случае сложность времени в Python int.bit_length () - PullRequest
Новая
       0

В худшем случае сложность времени в Python int.bit_length ()

0 голосов
/ 19 октября 2019

Когда мы вызываем функцию int.bit_length , передающую целое число n, это сложность времени наихудшего случая O(log(n)) или Python использует какой-то трюк для ее улучшения (например, сохранение позиции наиболеезначительный бит n при его создании)?

1 Ответ

2 голосов
/ 19 октября 2019

В CPython , для значений с меньшим количеством цифр внутреннего представления, чем PY_SSIZE_T_MAX/PyLong_SHIFT - т. Е. Меньше чем PY_SSIZE_T_MAX двоичных цифр - он рассчитывается из числа внутренних цифр, да: 

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);

В противном случае он снова проходит через bigints для общей сложности времени O (log log N) (что не совсем верно в этом странном сочетании практики и теории, так что ...). 

/* 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)

...