python - int ('1010' ,2) 的时间复杂度是多少？

Question

我只想知道 int(<binary string>,2) 的时间复杂度在 python 中，将 base-2 二进制数字字符串转换为 int

Answer 1

根据Python source code ，从基数 2 或任何二次方基数转换而来的字符数复杂度为 O(N)。

/* *str points to the first digit in a string of base `base` digits.  base
 * is a power of 2 (2, 4, 8, 16, or 32).  *str is set to point to the first
 * non-digit (which may be *str!).  A normalized int is returned.
 * The point to this routine is that it takes time linear in the number of
 * string characters.

相比之下，似乎每个非二基幂都是(通常？)O(N^2) .

Binary bases can be converted in time linear in the number of digits, because
Python's representation base is binary.  Other bases (including decimal!) use
the simple quadratic-time algorithm below, complicated by some speed tricks.