Python 中 bin() 的时间复杂度

Question

bin(n)Python中的时间复杂度n是多少，十进制数（整数）在哪里？

例如：

如果n = 10，那么bin(n) = 0b1010，那么幕后发生了什么？十进制转二进制需要多长时间？这是什么Big O符号？

Answer 1

python中bin(n)的时间复杂度是多少，其中n是十进制数（整数）？

十进制转二进制需要多长时间？

没有n从十进制到二进制的数字转换，因为内部表示已经是二进制的。整数值表示为一组64-bit值（例如，如果该值小于2^64 - 1则该数组包含一个元素）。因此，要以二进制形式显示它，需要从最高位打印到最低位。

如果您查看此处的源代码bin()或更具体的宏#define WRITE_DIGITS(p) 链接，您将看到以下循环：

for (i = 0; i < size_a; ++i) {
    ...
}

size_aa代表必须找到二进制表示的数字大小（64 位整数数组的大小）。

然后，在for循环中有一个while其中i第 -th 位的位a被提取并保存到字符串表示中p：

...
do {
    ...
    cdigit = (char)(accum & (base - 1));
    cdigit += (cdigit < 10) ? '0': 'a' - 10;
    *--p = cdigit;
    ...
} while (...);
...

执行内循环，直到提取出当前数字的所有位。在此之后，外循环移动到下一位，因此所有位再次从内循环中提取。等等。

但是迭代次数等于给定数字的二进制表示中的位数n，即log(n)。因此，bin()一个数的时间复杂度n为O(log(n))