斐波拉契数列的第n项

斐波拉契数列:

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

递归实现

1
2
3
4
5
6
7
8
long fab1(int n)
{
if (n < 3)
{
return 1;
}
return fab1(n - 2) + fab1(n - 1);
}

「遍历数组」实现

1
2
3
4
5
6
7
8
9
10
11
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];
}

「滚动数组」实现

1
2
3
4
5
6
7
8
9
10
11
12
13
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;
}

测试比较

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#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)