使用join()的方法的空间复杂性

Question

请考虑以下方法:

def fun(lst) : 
    concat = "".join(lst) 
    return hash(concat) 

这段代码的地方复杂性是多少？
谢谢!

Answer 1

给定列表或元组时,join仅分配一定量的空间,超出保持连接字符串所需的空间.(如果没有给出列表或元组,它会将输入转换为元组,这需要O(N)空间.)由于连接的字符串需要O(N)空间,其中n是输入的大小,join有O( N)空间复杂性.

详细说明:join将要连接的所有字符串的长度相加,分配足够大的字符串来保存结果,然后将输入字符串复制到结果中.它需要能够迭代输入两次来执行此操作,因此如果输入不是列表或元组,则它会生成元组.假设存在n总大小的输入字符串N,则元组占用空间n,并使输出字符串占空比N.如果输入字符串仅在创建元组时存在,可能是因为join传递了一个生成器,实现输入字符串的空间成比例N.因此,所需的总空间是O(N).