斐波那契数列 O(logN) 算法

欢迎来访

介绍求斐波那契数列时间复杂度为O(\log N)的做法之前，我们先看一下快速幂。

快速幂

题目链接

快速幂算法在数论领域中属于基础性的计算方法。

在处理a^b mod p, (1 \le a, b, p \le 10^9)这类问题时，若采用常规的计算方式，其时间复杂度为O(N)，显然无法满足实际需求，容易导致程序运行超时。而快速幂算法则能够将这一复杂度有效降低至O(\log b)，从而显著提升运算效率。

做法

首先对以下序列进行预处理：a^{2^0}, a^{2^1}, a^{2^2}, a^{2^3}, ..., a^{2^{\log b}}。

将上述各项依次相乘，可得出结果：a^{2^0+2^1+2^2+2^3+...+2^{\log b}}。

根据已知知识，表达式2^0+2^1+2^2+2^3+...+2^{\log b}能够转换为二进制形式表示为：1111...111，其中包含\log b + 1个连续的1。

通过选择或不选择每一个项2^i, 0 \le i \le \log b