Fibonacci序列的时间和空间复杂度

Question

这不是获取Fibonacci序列号的最有效方法，但我正在学习Big，并希望确认和解释下面代码的空间和时间效率。代码是用Python编写的，因此我使用一个列表并将其附加到其中，然后返回最后一个值。

追加方法需要O(1)时间，如图中所示的这里，但是我做了几乎n次的操作，所以我会得到时间复杂度的O(n)吗？

关于空间复杂性，我是否应该考虑作为算术级数使用的空间，因为如果输入的数字大于函数堆栈开始时的大小，列表就必须移到别处？

此问题中的代码用于递归方法。

def getFib(position):
  if position == 0:
    return 0
  if position == 1:
    return 1

  list_ = [0, 1]
  previous = 1

  for pos in range(2, position+1):
    list_.append(list_[pos-1] + list_[pos-2])

  return list_[position]

if __name__ == "__main__":
  print(getFib(0))
  print(getFib(1))
  print(getFib(2))
  print(getFib(3))
  print(getFib(4))
  print(getFib(5))
  print(getFib(6))
  print(getFib(7))
  print(getFib(8))
  print(getFib(9))

Answer 1

时间复杂性：O(n)，因为您正在执行n乘以具有恒定时间复杂度的循环。

空间复杂性：O(n)，因为您要在列表中存储n数字。

当然，您不需要存储所有的数字，而只需要存储最后两个值。这样就可以将空间复杂度降低到O(1)。