在Python中将列表转换为str的时间和空间复杂性 [英] Time and Space Complexity of list to str conversion in Python

问题描述

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

Trying to find out what is the time complexity of casting to string

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

肯定是O(1) 不确定如何验证.

Pretty sure it's O(1) Not sure how to verify.

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

about space complexity, That should not be linear to list size, thinking O(1) because string has max size.

推荐答案

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

It's linear, because bigger lists need more time and memory to convert.

使用 perfplot 生成的图形.代码，以供参考:

Graph generated using perfplot. Code, for reference:

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)

这篇关于在Python中将列表转换为str的时间和空间复杂性的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！