Python下述遍历切片函数的空间复杂度是O(m)还是O(n*m)？

问题复现 #

给定输入参数：

• nums：任意长度的整数列表，长度记为n
• m：整数参数
  代码实现如下：

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

问该代码的空间复杂度是O(m)还是O(n*m)？ #

结论 #

该代码的空间复杂度为O(m)，不是O(n*m)。 #

具体原因 #

• 空间复杂度的统计标准是程序运行周期内峰值占用的额外内存大小，不是运行全程累计分配的内存总和。
• Python的列表切片nums[i:i+m]会生成一个新的列表对象，该对象的长度最大为m，所以单次切片占用的额外空间为O(m)。
• 每次进入下一轮循环时，上一轮生成的temp列表就没有任何活跃变量引用，会被Python的垃圾回收机制自动释放内存。任意时刻程序只会持有当前循环生成的1个切片对象，额外内存占用始终和m成正比。
• 只有当代码中将每次生成的temp全部存储到另外的全局容器中时（比如每次循环都执行res.append(temp)），才会累计占用O(n*m)的空间，当前代码没有类似操作，因此不会达到这个量级。

内容的提问来源于stack exchange，提问作者m4gg