时间复杂度O(log(n))空间复杂度O(1)求斐波那契数列第n项

斐波那契数的计算方式是: \[ fib(n)=\left\{\begin{matrix} 0 & n=0\\ 1 & n=1\\ fib(n-1)+fib(n-2) & n\geq 2 \\ \end{matrix}\right. \] 之前用这个计算公式写出了时间复杂度O(n)空间复杂度O(1)的动态规划迭代算法。而这篇文章主要是讲讲时间复杂度O(log(n))空间复杂度O(1)算法的思路。本文代码都已反复测试过,确保可以正常运行。

前两个代码可以求得: \[ fib(n) \quad \forall n \in \{x|0 \leq x \leq 93\} \]

  • 最后的迭代思路代码不可以计算fib(0)​;
  • 最大只可以求得fib(93)​,这是因为unsigned long long类型的存储限制,数据再大会溢出。

⚡️算法核心

如果要将算法的时间复杂度降下来,那么就要改改上面的斐波那契数列递推公式。

当n足够大时,做如下推理: \[ \begin{equation} \begin{aligned} fib(n) &= fib(n-1)+fib(n-2)\\ &= [fib(n-2)+fib(n-3)]+fib(n-2)\\ &= 2fib(n-2)+fib(n-3)\\ &= 2[fib(n-3)+fib(n-4)] + fib(n-3)\\ &= 3fib(n-3)+2fib(n-4)\\ &= 3[fib(n-4)+fib(n-5)]+2fib(n-4)\\ &= 5fib(n-4)+3fib(n-5)\\ &= 8fib(n-5)+5fib(n-6)\\ &= 13fib(n-6)+8fib(n-7)\\ &= 21fib(n-7)+13fib(n-8)\\ &= ···\\ \end{aligned} \end{equation} \] 看多项式的系数,不正是斐波那契数列的项吗?

即: \[ \begin{equation} \begin{aligned} fib(n) &= fib(2)fib(n-1)+fib(1)fib(n-2)\\ &= fib(3)fib(n-2)+fib(2)fib(n-3)\\ &= fib(4)fib(n-3)+fib(3)fib(n-4)\\ &= fib(5)fib(n-4)+fib(4)fib(n-5)\\ &= ···\\ \end{aligned} \end{equation} \]

通过上述推理,发现了一个规律,其中i可以是1到n中任意一个数: \[ fib(n)=fib(i)fib(n+1-i)+fib(i-1)fib(n-i) \quad \forall i \in \{x|1\leq x \leq n\} \] 而当\(i\)\(n\)的一半时,这个公式就发生了一些奇妙的变化。

取一半这个操作需要考虑n是奇数还是偶数:

n为奇数

此时\(i\)\((n+1)/2\),代入公式可得: \[ \begin{equation} \begin{aligned} fib(n) &= fib(\frac{n+1}{2})fib(\frac{n+1}{2})+fib(\frac{n-1}{2})fib(\frac{n-1}{2})\\ &= [fib(\frac{n+1}{2})]^2 + [fib(\frac{n-1}{2})]^2\\ \end{aligned} \end{equation} \]

n为偶数

此时\(i\)\(n/2\),代入公式可得: \[ \begin{equation} \begin{aligned} fib(n)&=fib(\frac{n}{2})fib(\frac{n}{2}+1)+fib(\frac{n}{2}-1)fib(\frac{n}{2})\\ &=fib(\frac{n}{2})[fib(\frac{n}{2})+fib(\frac{n}{2}-1)]+fib(\frac{n}{2}-1)fib(\frac{n}{2})\\ &=[fib(\frac{n}{2})]^2+2fib(\frac{n}{2})fib(\frac{n}{2}-1)\\ \end{aligned} \end{equation} \]

合并一下公式

\[ fib(n)=\left\{\begin{matrix} 0 & n=0\\ 1 & n=1\\ [fib(\frac{n+1}{2})]^2 + [fib(\frac{n-1}{2})]^2 & \text{n >1 and n is odd} \\ [fib(\frac{n}{2})]^2+2fib(\frac{n}{2})fib(\frac{n}{2}-1)& \text{n > 1 and n is even}\\ \end{matrix}\right. \]

这样n就不直接和自己的后两项发生关系,而是和自己的一半那个数扯上关系了。

🚄递归代码

思路

使用上述递推式可以很容易写出的递归代码,虽然是个效率很低的递归思路,但是也比最朴素的递归求斐波那契数的算法效率高不少。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
using namespace std;

unsigned long long fib(int n) {
if (n == 0) return 0;

if (n == 1) return 1;

if (n & 1) {
return fib((n + 1) / 2) * fib((n + 1) / 2) + fib((n - 1) / 2) * fib((n - 1) / 2); // a为奇数
} else {
return fib(n / 2) * fib(n / 2) + 2 * fib(n / 2) * fib(n / 2 - 1); // a为偶数
}
}

int main() {
int n;
cin >> n;
cout << fib(n) << endl;
return 0;
}

🛩使用记忆法进行优化

思路

记忆法是动态规划的一个变种,和上面的差不多,同样也是自顶向下的递归算法,区别在于算过的值都被记录下来,避免重复计算,提升了不少效率,这就是时间复杂度O(log(n))空间复杂度O(n)的算法:

代码

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
28
29
30
31
32
33
34
35
36
37
#include <iostream>
#include <vector>
using namespace std;

// memory数组用于记录是否计算过这个值,默认都是0
// 如果memory中此值是0,表示需要计算,计算完将结果填入memory数组中
// 如果此值已经计算过,直接从memory中取出即可
vector<unsigned long long> memory;

unsigned long long fib(int n) {
if (n == 0) {
memory[0] = 0;
return memory[0];
}
else if (n == 1) {
memory[1] = 1;
return memory[1];
}

if (memory[n] != 0)
return memory[n];

if (n & 1) {
memory[n] = fib((n + 1) / 2) * fib((n + 1) / 2) + fib((n - 1) / 2) * fib((n - 1) / 2); // a为奇数
} else {
memory[n] = fib(n / 2) * fib(n / 2) + 2 * fib(n / 2) * fib(n / 2 - 1); // a为偶数
}
return memory[n];
}

int main() {
int n;
cin >> n;
memory.resize(n + 1);
cout << fib(n) << endl;
return 0;
}

🚀使用迭代法进一步优化

这是真正自底向上的算法了,迭代法算法可以在时间复杂度O(log(n))空间复杂度O(1)下计算第n个斐波那契数。

思路

迭代规则

首先这样思考:

1、如果我使用\(fib(n)=fib(n-1)+fib(n-2)\)的递推思路,那么当我要求得\(fib(n)\)的值时,必须把\(fib(0) - fib(n-1)\)的值全部算出来;

2、现在改为折半的递推思路,那么当我要求得\(fib(n)\)的值时,需要计算哪些值呢?

举个栗子,当我要计算\(fib(2729)\)时:

1、2729是奇数,需要先求得\(fib(1365)\)\(fib(1364)\)(因为奇数公式),而\(fib(1365)\)是可以通过\(fib(1363)+fib(1364)\)求得的,这里只需要求出\(fib(1363)\)\(fib(1364)\)

为什么是求这两个数而不是求\(fib(1365)\)\(fib(1364)\),这是我踩的一个大坑。

我可以算\(fib(1365)\)\(fib(1364)\),也可以算\(fib(1364)\)\(fib(1363)\)

而我自己规定,遇到以下两种情况:

  1. 所需要求的fib(n)​中,n是奇数时(比如这里2729是奇数);
  2. 一个要求先求得fib(x+1)和fib(x),另一个需要先求得fib(x)和fib(x-1)时。比如下面求fib(341)和fib(340)的部分。

都算后面两个数。而且整个计算图都需要保持计算规则的一致性,都计算后面两个数。

2、计算\(fib(1364)\),1364是偶数,需要先求得\(fib(682)\)\(fib(681)\)

3、计算\(fib(1363)\),1363是奇数,需要先求得\(fib(682)\)\(fib(681)\)

发现要计算的数是一样的,都是\(fib(682)\)\(fib(681)\)

4、计算\(fib(682)\),682是偶数,需要先求得\(fib(341)\)\(fib(340)\)

计算\(fib(681)\),681是奇数,需要先求得\(fib(341)\)\(fib(340)\)

5、计算\(fib(341)\),341是奇数,需要先求得\(fib(171)\)\(fib(170)\)

计算\(fib(340)\),341是偶数,需要先求得\(fib(170)\)\(fib(169)\)

这时要计算的数就不一样了,但是\(fib(171)\)可以通过\(fib(170)\)\(fib(169)\)很轻易算出——\(fib(171)=fib(170)+fib(169)\),所以只需要计算\(fib(170)\)\(fib(169)\)就好了。

However,计算\(fib(171)\)\(fib(170)\)也是可以的。但是计算规则要一致,要么就都算后两个,要么就都算前两个。

而我选择计算后两个,因为可以更快收敛到\(fib(1)\)\(fib(0)\)。(其实差别不大)

6、如此递推下去,直到\(fib(1)=1\)\(fib(0)=0\)为止……

可以画出一张计算图,若需要计算相同的斐波那契数,在右边标记为0;若需要计算不同的斐波那契数,但通过后两项相加得前一项,在右边标记为1(红色的标记暂时不管,这是代码中考虑的部分):

迭代规则总结

每次迭代都需要计算两个斐波那契数,记为\(fib(a)\)\(fib(b)\)最终要求得的值是\(fib(a)\)

1、当a为偶数时,计算\(fib(a)\)\(fib(b)\)需要相同的数;

2、当a为奇数时,计算\(fib(a)\)\(fib(b)\)需要的数不同,我的计算规则是只算后两个;

每次计算都会因为a的奇偶性不同而采取不同的运算策略,也就是只根据a的奇偶性,就可以知道该如何运算了。

如果到这里为止都看懂了再继续往下看。

获取计算图

每次二分操作都要分a是奇数还是偶数,可以通过不断的将a进行模2运算得出结果。这个操作有没有觉得似曾相识,当初十进制转二进制不就是这么算的吗,也就是说最顶端的数,即要求的数\(fib(n)\)的二进制表示方法就是一张现成的计算规则。

还是比如\(fib(2729)\),2729的二进制表示是1010 1010 1001,而上面计算图右边的数从下往上看,就是他的二进制表示。

或者换个思路想,上面迭代规则总结中,是按a奇偶性分情况处理的,那么a的奇偶性会导致不同的模2结果,也就是n的二进制表示计算方式。

在代码中,我使用了一个ruler的变量来读取n二进制的每一个bit位的值。具体操作如下:

1、n是一个int型的变量,共有32个bit位;

2、ruler是用于读取n的指定bit位的值的工具,初始化时ruler的第一个bit位是1,其他都是0,将rulern进行按位与运算,结果为0表示n这一个bit位是0;结果非0表示n这一个bit位是1;

3、读取次数使用count变量来记录,count初始值为32,表示需要统计32次;

4、跳过n前面的0bit位,计算机存储一个正数的时候,前面会补0,要先把这些0跳掉,一个while循环搞定:

1
2
3
4
while ((n & ruler) == 0) {
ruler >>= 1;
count--;
}

5、跳过第一个为1的bit位,所有的数第一个有效bit位都是1,上面的计算图也可以看出跳过这个bit位,从第2个bit位开始;

1
2
ruler >>= 1;
count--;

6、此时ab两个数就是\(fib(1)\)\(fib(0)\)。设置tmp变量,用于奇数运算时,存储\(fib(a)+fib(b)\)的值。设置cd变量,用于接收运算结果;

7、处理完后c的值赋予ad的值赋予b,进入下一轮迭代;

8、最后取a的值作为所要求的结果。为什么取a不取b,因为我的计算规则里就是始终把a作为要求得的值。

代码

我没有兼容求\(fib(0)\),感觉不跳第一个有效位可以兼容,但我这里没有深入思考。

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <iostream>
using namespace std;

unsigned long long even_calculate (unsigned long long a, unsigned long long b) {
return a * a + 2 * a * b;
}

unsigned long long odd_calculate (unsigned long long a, unsigned long long b) {
return a * a + b * b;
}

int main() {
int n, count;
cin >> n;
count = 32;
unsigned int ruler = 0x80000000;
// 跳过n前面的0bit位
while ((n & ruler) == 0) {
ruler >>= 1;
count--;
}
ruler >>= 1;
count--;
unsigned long long a = 1, b = 0, tmp = a + b, c = 2, d = 1;
for (int i = 0; i < count; i++) {
if (n & ruler) {
tmp = a + b;
c = odd_calculate(tmp, a);
d = even_calculate(a, b);
} else {
c = even_calculate(a, b);
d = odd_calculate(a, b);
}
a = c;
b = d;
ruler >>= 1;
}

cout << a << endl;

return 0;
}
Image