关于覆盖输入、无值存储及返回变量的空间复杂度三类问题咨询

给定函数：

def remove_duplicates(my_list):
    return list(set(my_list))

提问：该函数将输入列表转换为集合后再转回列表并返回，未将新创建的列表赋值给变量。请问此操作是否仍会占用辅助空间？其辅助空间复杂度是O(N)还是O(1)？本人认为是O(N)，因为最坏情况下新列表与原列表长度相等，创建该列表会消耗辅助空间。

解答 #

• 会占用辅助空间。不管是否显式赋值给变量，list(set(my_list))都会在内存中创建新的集合和列表对象，这部分空间属于额外开销。
• 辅助空间复杂度为O(N)。最坏场景下原列表无重复元素，集合和新列表的元素数量都等于原列表长度N，需要分配O(N)级别的空间存储这些元素，你的判断是正确的。

给定函数：

def foo(my_list):
    my_list = list(range(len(my_list)))

提问：该函数创建包含输入列表所有索引的新列表，并覆盖输入变量my_list存储该新列表。请问如何评估此操作的空间复杂度？其辅助空间复杂度是否为O(N)？是否会影响原本为O(N)的输入空间复杂度？

解答 #

• 辅助空间复杂度是O(N)。list(range(len(my_list)))创建了一个长度为N（原列表长度）的新列表，这部分属于函数额外分配的辅助空间。
• 输入空间复杂度不受影响。输入的原列表属于函数的参数空间，新列表是独立创建的辅助空间，覆盖变量名只是改变了局部变量的引用指向，不会改变输入空间的占用情况。输入空间复杂度依然为O(N)，辅助空间复杂度额外加O(N)，整体空间复杂度仍为O(N)（O(N)+O(N)=O(N)）。

现有两个接收正整数n的函数：

1. 第一个返回[odds, evens]形式的列表（其中odds是0到n的所有奇数组成的列表，evens是0到n的所有偶数组成的列表）；
2. 第二个返回包含0到n所有整数的列表。

提问：请问如何评估二者的辅助空间复杂度？仅看返回列表外层元素数易认为第一个是O(1)、第二个是O(N)，但第一个返回的嵌套列表总元素数约为n，那第一个的辅助空间复杂度到底是O(N)还是O(1)？

解答 #

• 两个函数的辅助空间复杂度都是O(N)。
• 空间复杂度的计算核心是看所有额外分配的元素总数量，而非外层容器的数量。第一个函数返回的嵌套列表中，odds和evens的元素总数为n+1（0到n共n+1个数），和第二个函数返回的列表元素数量完全一致，都需要O(N)级别的辅助空间存储这些元素。外层的列表只是一个包含两个引用的容器，空间开销为常数级O(1)，不影响整体的O(N)复杂度判定。

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