Fibonacci C语言实现

 1 long long int Fibonacci(int n)
 2 {
 3     int i;
 4     long long int *dp, ret;
 5     dp = malloc(sizeof(long long int ) * (n+1));
 6     
 7     dp[0]=0; dp[1] = 1; 
 8     for (i=2; i<= n; i++) {
 9         dp[i] = dp[i-1] + dp[i-2];
10     }
11     ret = dp[n];
12     free(dp);
13     return ret;
14 }

上面就是之前写的代码,看上去能够解决问题,但是今天看了https://www.cnblogs.com/MonsterJ/p/13154306.html 的分析,感觉自己弱爆了,连时间复杂度都没分析.

直接上时间更优化的代码:

 1  int fib(int N) {
 2         if (N == 0) {
 3             return 0;
 4         }
 5         if (N== 1) {
 6             return 1;
 7         }
 8         int *notes = malloc(sizeof(int) * (N+1));
 9         if (notes == NULL) 
10             return -1;
11         
12         notes[0] = 0;
13         notes[1] = 1;
14        int i;
15         for( i = 2; i <= N; i++) {
16             notes[i] = notes[i-1] + notes[i-2];
17         }
18         int res = notes[N];
19         free(notes);
20         return  res;
21     }

再上空间上更简化的代码:

 int fib(int N) {
        int a = 0;
        int b = 1;
        if(N == 0) {
            return a;
        }
        if(N == 1) {
            return b;
        }
        for(int i = 2; i <= N; i++) {
            int tmp = a + b;
            a = b;
            b = tmp;
        }
        return b;
    }

Fibonacci C语言实现

相关推荐