时间复杂度与空间复杂度

时间复杂度
image.png

image.png

斐波那契的三种解法

  1. #include <iostream>
  2. using namespace std;
  4. // 递归形式
  5. long double fb1(int n)
  6. {
  7.     if(n<1)
  8.     {
  9.         return -1;
  10.     }
  11.     if(n==1||n==2)
  12.     {
  13.         return 1;
  14.     }
  16.     return fb1(n-1)+fb1(n-2);
  17. }
  18. //数组形式存储，动态规划 时间复杂度O(n),空间复杂度O(n)
  19. long double fb2(int n )
  20. {
  21.     if(n<1)
  22.         return -1;
  23.     int *p =new int[n+1];
  24.     p[1] = p[2] =1;
  25.     for(int i=3;i<=n;i++)
  26.     {
  27.         p[i]=p[i-1]+p[i-2];
  28.     }
  29.     long double res = p[n];
  30.     delete []p;
  31.     return res;
  33. }
  35. //时间复杂度O(n),空间复杂度O(1)
  36. long double fb3(int n)
  37. {
  38.     if(n<1)
  39.         return -1;
  40.     long double s1,s2;
  41.     s1 = s2 =1;
  42.     for(int i=3;i<=n;i++)
  43.     {
  44.         s2 = s1 + s2;
  45.         s1 = s2 -s1;
  46.     }
  47.     return s2;
  48. }
  49. int main() {
  51.     long double result = fb1(20);
  52.     cout << result << endl;
  54.     long double result2 = fb2(20);
  55.     cout << result2 << endl;
  57.     long double result3 = fb2(20);
  58.     cout << result3 << endl;
  60.     std::cout << "Hello, World!" << std::endl;
  61.     return 0;
  62. }
/home/er/dsa/p1/cmake-build-debug/p1
6765
6765
6765
Hello, World!

斐波那契 、复杂度 - 图3 My Github