斐波纳契序列的时空复杂度

2024-03-28 12:11:13 发布

您现在位置:Python中文网/ 问答频道 /正文

这不是获得斐波那契序列号的最有效的方法,但我正在学习大O,希望确认和解释以下代码的空间和时间效率。代码是用Python编写的,因此我使用一个列表并附加到它,然后返回最后一个值。在

append方法需要O(1)时间,如here所示,但是我几乎做了n次操作,所以我会得到O(n)的时间复杂性吗?在

关于空间复杂性,我是否应该考虑使用arithmetic series的空间,因为如果输入的数字大于开始时给函数堆栈的值,那么列表将不得不移到其他地方?在

question中的代码用于递归方法。在

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))

Tags: 方法代码pos列表returnif时间空间
1条回答
网友
1楼 · 发布于 2024-03-28 12:11:13

时间复杂度:O(n)因为您正在执行n倍于具有恒定时间复杂度的循环。在

空间复杂度:O(n),因为您正在列表中存储n个数字。在

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

相关问题 更多 >