Python3 中 str() 函数的复杂度是多少？

Question

我必须创建一个复杂度为 O(n) 的函数，为此我想使用 str() 函数。

有人可以解释一下吗 :

str(1000)

这个代码是 O(1) 还是 O(4) 因为 1+0+0+0 ？

Answer 1

O(n) 在数据结构的上下文中仅意味着如果有 n 项，则对该结构的操作将需要（按顺序）n 迭代或遍历以达到预期的效果。如果你从一个整数构造一个字符串，那么我猜复杂度是 O(log10(n))

编辑：来自 Python docs：

If neither encoding nor errors is given, str(object) returns object.str(), which is the “informal” or nicely printable string representation of object.

Python 检测到该对象是一个 int，因此它将根据该 int 创建一个字符串。实现此转换的一种方法是：

if n == 0:
    return "0"
negative = n < 0
if negative:
    n = -n
out = ""
while n > 0:
    digit = n % 10
    n /= 10
    out = chr(48 + digit) + out
if negative:
    out = "-" + out

while 循环中的迭代次数取决于 n 包含的十进制位数，即 log10(n)。

Answer 2

函数用于字符串转换。这意味着将每个值转换为一个字符串。复杂程度取决于长度。如果全长为 n，那么复杂度将为 O(n)。如果大小是一个固定的数字，在这种情况下它将执行一个恒定的大小。我们将常数表示为 O(1).

Answer 3

从source code, the implementation of int.__str__ has runtime complexity of O(m*n) where m is the number of binary digits and n is the number of decimal digits. Since for an integer i the number of digits in an arbitrary base b is given by log(i, base=b) and logarithms in different bases可以看出，只相差一个常数，运行时复杂度是O(log(i)**2)，即位数的二次方。

这可以通过运行 a performance test:

来验证

import perfplot

perfplot.show(
    setup=lambda n: 10**n,
    kernels=[str],
    n_range=range(1, 1001, 10),
    xlabel='number of digits',
)

Python3 中 str() 函数的复杂度是多少？

What is the complexity of str() function in Python3?

python

string

algorithm

time-complexity