【剑指offer】10A--求裴波那切数列的第n项，C++实现

#本文是牛客网《剑指offer》刷题笔记

1.题目

      写入一个函数，输入n，输出裴波那切数列的第n项

     

2.思路

• 递归--时间和空间复杂度高
•  循环--时间和空间复杂度低，通过循环迭代计算第n项，首先根据f(0)和f(1)计算f(2)，在根据f(1)和f(2)计算f(3)，依次类推计算出第n项。

3.code

1 class Solution { 2 public: 3 int Fibonacci(int n) { 4 // n==0 5 if(n<=0) 6 return 0; 7 8 // n==1 9 if(n==1) 10 return 1; 11 12 // n>1 13 int one=0; 14 int two=1; 15 int three=0; 16 17 for(int i = 2;i<=n;i++){ 18 three = one + two; 19 one =two; 20 two = three; 21 } 22 return three; 23 } 24 };

 4.复杂度

      时间复杂度O(n)

转载于:https://www.cnblogs.com/wanglei5205/p/8522931.html

总结

以上是生活随笔为你收集整理的【剑指offer】10A--求裴波那切数列的第n项，C++实现的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。