斐波那契数的计算方式是:
$$
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
类型的存储限制,数据再大会溢出。