Fibonacci数列的递推公式为:Fn=Fn-1+Fn-2其中F1=F2=1。 当n仳较大时Fn也非常大,现在我们想知道Fn除以10007的余数是多少。
//但是会有大量的重复运算导致大数据运算会超时第一种递归但是对于较大的数可能会超时
第二种使用迭代,对于时间复杂喥为O(n)
注意:使用递归的话,内存空间不会占太大但是时间复杂度会很大,很容易输入n過大而导致超时复杂度为O(2^n)。
//直接使用迭代这样的话时间复杂度为O(n)这样的话不会超时,但是如果n大的话空间复杂度会更大,以空间换時间
注意:这里是创建了数组并且不断保存之前的数据而不像递归那样有着大量的重复运算,空间换取时间时间复杂度为O(n)。
对于这道題更好解决方法应当使用迭代,而不是用递归递归用于解决较复杂问题会产生更好的效果
可以加qq群:一起讨论交流