这不是获得斐波那契序列号的最有效的方法,但我正在学习大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))
时间复杂度:
O(n)
因为您正在执行n
倍于具有恒定时间复杂度的循环。在空间复杂度:
O(n)
,因为您正在列表中存储n
个数字。在当然,不需要存储所有的数字,只需要存储最后两个值。这样可以将空间复杂性降低到
O(1)
。在相关问题 更多 >
编程相关推荐