斐波拉契数列的第n项

斐波拉契数列:

• a(0) = 0
• a(1) = 1
• a(2) = 1
• a(n) = a(n-1) + a(n-2)

递归实现

long fab1(int n)
{
    if (n < 3)
    {
        return 1;
    }
    return fab1(n - 2) + fab1(n - 1);
}

「遍历数组」实现

long fab2(int n)
{
    long nums[n];
    nums[0] = 1;
    nums[1] = 1;
    for (int i = 2; i < n; i++)
    {
        nums[i] = nums[i - 2] + nums[i - 1];
    }
    return nums[n - 1];
}

「滚动数组」实现

long fab3(int n)
{
    long first = 1;
    long second = 1;
    long current = 1;
    for (int i = 3; i <= n; i++)
    {
        current = first + second;
        first = second;
        second = current;
    }
    return current;
}

测试比较

#include <iostream>
#include <ctime>

using namespace std;

void fun_cost(long (*func)(int), int n)
{
    time_t begin, end;
    time(&begin);
    long result = (*func)(n);
    time(&end);
    double difference = difftime(end, begin);

    const char *format = "n: %d result: %ld cost: %f";
    int len = snprintf(NULL, 0, format, n, result, difference);
    char *s = (char *)malloc(len + 1);
    sprintf(s, format, n, result, difference);
    std::cout << s << endl;
}

int main()
{
    fun_cost(fab1, 45);
    fun_cost(fab2, 45);
    fun_cost(fab3, 45);
    return 0;
}

结果:

n	result	耗时
n: 45	result: 1134903170	cost: 4.000000
n: 45	result: 1134903170	cost: 0.000000
n: 45	result: 1134903170	cost: 0.000000

总结

• 递归版: 理解相对简单, 但是递归调用遇到大数时, 将会造成很深的调用栈, 耗费内存和运行时间O(n^2)
• 「遍历数组」: 时间复杂度O(n), 空间复杂度为O(n)
• 「滚动数组」: 方法最优, 时间复杂度为O(n), 空间复杂度为常量(3)

---