关于空间复杂度的两个模糊问题

问题描述 投票:0回答:0

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) 是否公平?

python algorithm big-o space-complexity
© www.soinside.com 2019 - 2024. All rights reserved.