InTheBloodHorse

数据结构与算法(6) 你可能不知道的斐波那契数列

字数统计: 255阅读时长: 1 min
2018/09/30 Share

每个程序员对斐波那契数列应该都是知道的,这里就不介绍我们熟知的求斐波那契的方法。
在这里我们用 通项公式法 来解。
TIM截图20180930131051.jpg

知道了公式,问题就简单了。
但是这里的复杂度还是 O(n),因为我们还要算这个 n次方呢。
大多数人都会说,简单!遍历一遍不就行了?
的确可以,假如这么简单,我也就不会来写这个了。
在这里a^n 我们可以用减治的思想。

  1. 当 n 是偶数时,先求出 r = a^(n/2),所以 r * r 就是 a^n
  2. 当 n 是奇数时,n-1为偶数,先求出 r = a ^((n-1)/2),再计算 r r a,就得到了a^n

这样我们的复杂度就降到了 O(log(n))。
代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int cal(int a,int n)
{
if(n==0) return 1;
if(n==1) return a;

int r = 0;
if(n%2){
r = cal(a,(n-1)/2);
return r*r*a;
}else{
r = cal(a,n/2);
return r*r;
}
}

CATALOG