mirror of
https://github.com/ShusenTang/LeetCode.git
synced 2024-09-02 14:20:01 +00:00
49 lines
1.3 KiB
Markdown
49 lines
1.3 KiB
Markdown
# [509. Fibonacci Number](https://leetcode.com/problems/fibonacci-number/)
|
||
|
||
# 思路
|
||
求斐波那契数列。
|
||
|
||
## 思路一
|
||
常用思路就是按照定义迭代计算，很简单，见代码。
|
||
|
||
时间复杂度O(N)，空间复杂度O(1)。
|
||
|
||
## 思路二
|
||
除了基本的思路，还有个O(logN)复杂度求斐波那契数列的思路。
|
||
|
||
根据定义，我们有
|
||
```
|
||
| F(N) F(N-1)| | 1 1 |(N-1)
|
||
| | = | |
|
||
| F(N-1) F(N-2)| | 1 0 |
|
||
```
|
||
以上公式不难用归纳法证明。所以要想得到F(N)，只需要求得矩阵
|
||
```
|
||
|1 1|
|
||
|1 0|
|
||
```
|
||
的N-1次方。如何求这个矩阵的乘方呢，如果简单地循环N-1次那么复杂度还是O(N)。而我们知道求乘方有一个O(logN)的二分算法：
|
||
* n为偶数：A^n = A^(n/2) * A^(n/2)
|
||
* n为奇数：A^n = A^(n/2) * A^(n/2) * A
|
||
|
||
以上求乘方的方法可以很方便地用递归实现。
|
||
|
||
这种思路虽然时间复杂度为O(logN)，但是隐含的时间常数比较大，所以不是很常用，这里代码略。但是这种用O(logN)的二分求乘方的思路是值得我们学习的。
|
||
|
||
# C++
|
||
## 思路一
|
||
``` C++
|
||
class Solution {
|
||
public:
|
||
int fib(int N) {
|
||
if(N <= 1) return N;
|
||
int pre = 1, prepre = 0, tmp;
|
||
for(int i = 2; i <= N; i++){
|
||
tmp = pre + prepre;
|
||
prepre = pre;
|
||
pre = tmp;
|
||
}
|
||
return pre;
|
||
}
|
||
};
|
||
``` |