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

Question

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

Answer 1

根据Python源代码，从基数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.