Python中bin（）的时间复杂度

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