关于空间复杂度的两个疑难技术问题

问题1：输入空间复杂度分析 #

给出的函数代码如下：

def foo(lst):
  n = len(lst)
  for i in range(n):
    lst.append(i)
  return n

你的解读是正确的。输入空间复杂度衡量的是存储输入数据所占用的空间规模。初始输入列表的大小为n，占用O(n)空间；后续向列表追加n个元素后，列表总大小变为2n，但大O记法会忽略常数系数，2n的渐近增长量级仍然是线性的，因此输入空间复杂度依然是O(n)。

问题2：辅助空间复杂度分析 #

给出的函数代码如下：

def foo(lst, k):
  n = len(lst)
  for i in range(n - k + 1):
    cool = lst[i: i + k]
    if sum(cool) == 15:
      return cool

你的结论是对的，该函数的最坏情况辅助空间复杂度为O(n)。

辅助空间复杂度指的是除了输入数据、输出数据之外，算法运行过程中额外占用的空间。这里每次循环会创建切片cool，虽然每次迭代会覆盖同一个变量，但我们需要看运行过程中占用的最大额外空间：当k=n时，切片lst[0:n]会生成一个与原列表等长的新列表，占用O(n)空间，这就是最坏情况的空间开销，因此辅助空间复杂度的最坏情况为O(n)。

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