1.) 假设我有下面的函数接受一个大小为 n 的列表:
def foo(lst):
n = len(lst)
for i in range(n):
n.append(i)
return n
在这种情况下,我们如何解释输入空间复杂度?
最初,当然,输入占用的空间与列表的大小(n)成正比:O(n)。然而,由于我们将一个元素附加到输入列表,它的大小将变为 2n。因此,输入占用的空间量与 2n 成正比,使用大 O 表示法仍可简化为 O(n)。这是正确的解释吗?
2.) 假设我有下面的函数,它接收一个长度为 n 和正整数 k 的列表。没有输入验证,尽管假设 k 必须至多等于 n:
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
在这种情况下,我们如何解释辅助空间复杂度?虽然我们只存储一个列表(因为我们不断地覆盖同一个变量),但列表的大小根据 k 的输入而不同。
因此,例如,如果 k = 1(最佳情况),那么我们将为每次迭代存储一个空列表。如果 k = 2,那么我们将为每次迭代存储一个 2 元素列表。但是,如果 k = n(最坏情况),我们将在其单独迭代中存储一个 n 元素列表。因此,如果我们只考虑辅助空间复杂度,那么说它是最坏情况 O(n) 是否公平?