Python 中列表到字符串转换的时间和 Space 复杂度

Question

试图找出转换为字符串的时间复杂度是多少

str([1,2,6,...,3,6])

很确定是 O(1) 不确定如何验证。

编辑： 关于 space 的复杂性，这不应该与列表大小成线性关系， 考虑 O(1) 因为字符串具有最大大小。

Answer 1

它是线性的，因为更大的列表需要更多的时间和内存来转换。

使用 perfplot 生成的图表。代码，供参考：

import numpy as np
import perfplot 

perfplot.show(
    setup=lambda n: np.random.choice(100, n).tolist(),
    kernels=[
        lambda lst: [str(x) for x in lst],
        lambda lst: list(map(str, lst)),
    ],
    labels=['[str(x) for x in lst]', 'list(map(str, lst))'],
    n_range=[2**k for k in range(0, 20)],
    xlabel='N',
    logx=True,
    logy=True,
    equality_check=None)