python函数的空间复杂度

Question

有人能帮我计算一下这个python函数的空间复杂度吗？

input: nums = [1, 2, 3, 4, 5, 6, 7, 8....]
       m = integer 

for i in range(len(nums)):
    temp = nums[i:i+m]

这个空间复杂度应该是o(m)，还是o(n*m)，为什么？谢谢!

Answer 1

不包括输入，对于这段代码，因为m看起来不是一个常量，它应该是O(m)，因为在任何给定的时间点，我们只存储了nums[i:i+m]的1个块，因为temp只是为每个循环重新分配了一个新的子列表，从而使得前一个子列表已经成为garbage collection的主题。

• 所以不管是否有100万个nums并且m只有5个，那么我们现在将只存储5个项目，然后下一次迭代将保留前5个项目并存储新的5个项目的集合(取决于python实现，这甚至可能只是使用相同的内存并覆盖前一个)，依此类推。

但是如果你存储每个子列表，比如：

temp_list = []
for i in range(len(nums)):
    temp = nums[i:i+m]
    temp_list.append(temp)

那么它应该是O(m * len(nums))，因为我们将在nums中存储每个元素的m项。

Answer 2

忽略Python的垃圾收集，你会得到O(mn)的空间复杂性，其中n = len(nums)。这是因为您首先分配一个n元素列表，然后再分配每个m元素的n列表(请注意，对列表进行切片会创建一个新的分配)。这给出了总的n + mn单元分配，这是渐近的O(mn)。

但是在for循环中创建的列表都被temp引用。这意味着一旦创建了新的列表，前一个列表就没有引用，它就有资格进行垃圾收集。这实际上给我们留下了两个列表:长度为n的nums和长度为m的最后一个temp，这相当于O(m + n)的空间复杂度。