由于簡(jiǎn)書不支持
Latex蝗拿，建議去我的博客看原文：斐波納契數(shù)列實(shí)現(xiàn)及優(yōu)化
求關(guān)注沛膳、求交流、求意見俊鱼、求建議刻像。
前言
LintCode 是專注代碼面試的在線評(píng)測(cè)系統(tǒng)，有很多代碼題并闲，可以用 Java细睡、C++、Python 在線答題帝火，我覺得還不錯(cuò)溜徙，就決定把做一做這些題，然后把題目的實(shí)現(xiàn)犀填、優(yōu)化思路寫下來蠢壹，一來是為了有更深的理解，二來是討論一下還有沒有更好的方法九巡。
題目
LintCode：斐波納契數(shù)列
描述
查找 斐波納契數(shù)列 中第 N 個(gè)數(shù)图贸。
所謂的 斐波納契數(shù)列 是指：
- 前兩個(gè)數(shù)是
0和1。 - 第
i個(gè)數(shù)是第i-1個(gè)數(shù)和第i-2個(gè)數(shù)的和冕广。
斐波納契數(shù)列的前10個(gè)數(shù)字是：
0, 1, 1, 2, 3, 5, 8, 13, 21, 34 ...
樣例
給定 1疏日，返回 0
給定 2，返回 1
給定 10撒汉，返回 34
實(shí)現(xiàn)
遞歸實(shí)現(xiàn)
問題分析
根據(jù) 斐波那契數(shù)列 的定義得：
$$
\begin{aligned}
f(1) & = 0\
f(2) & = 1\
f(n) & = f(n - 1) + f(n - 2)\qquad n\in{3,4,5\ldots}
\end{aligned}
$$
根據(jù)上述表達(dá)式最明顯的實(shí)現(xiàn)方式便是遞歸沟优。
實(shí)現(xiàn) - C++
class Solution{
public:
int fibonacci(int n) {
if (n == 1) {
return 0;
} else if (n == 2) {
return 1;
} else {
return fibonacci(n - 1) + fibonacci(n - 2);
}
}
};
實(shí)現(xiàn) - Java
class Solution {
public int fibonacci(int n) {
if (n == 1) {
return 0;
} else if (n == 2) {
return 1;
} else {
return fibonacci(n - 1) + fibonacci(n - 2);
}
}
}
結(jié)果分析
- 結(jié)果：結(jié)果不盡人意，速度非常慢睬辐，甚至沒有通過 LintCode 的評(píng)測(cè)挠阁。
- 分析：這種遞歸不同于一般的遞歸，在
n較大時(shí)溯饵，兩次遞歸調(diào)用中存在大量的重復(fù)運(yùn)算侵俗，導(dǎo)致速度非常慢。
非遞歸實(shí)現(xiàn)
問題分析
在遞歸實(shí)現(xiàn)中瓣喊，由于大量的重復(fù)運(yùn)算導(dǎo)致速度慢坡慌，所以采用非遞歸形式，思路也非常簡(jiǎn)單：從 f(0) 開始根據(jù)公式疊加至 f(n) 藻三。
實(shí)現(xiàn) - C++
class Solution{
public int fibonacci(int n) {
if (n == 1) {
return 0;
} else if (n == 2) {
return 1;
} else {
int n1 = 0;
int n2 = 1;
int sn = 0;
while (n > 2) {
sn = n1 + n2;
n1 = n2;
n2 = sn;
n--;
}
return sn;
}
}
};
實(shí)現(xiàn) - Java
class Solution{
public:
int fibonacci(int n) {
if (n == 1) {
return 0;
} else if (n == 2) {
return 1;
} else {
int n1 = 0;
int n2 = 1;
int sn = 0;
while (n > 2) {
sn = n1 + n2;
n1 = n2;
n2 = sn;
n--;
}
return sn;
}
}
};
結(jié)果分析
- 結(jié)果：經(jīng)測(cè)試
C++最快可以以10ms輕松通過 LintCode 的評(píng)測(cè)洪橘。 - 分析：時(shí)間復(fù)雜度為
o(n)，空間復(fù)雜度為o(1)棵帽，效果不錯(cuò)熄求。 - 細(xì)節(jié)：使用
while代替for節(jié)省了一個(gè)Int(4Byte)的空間。
遞歸實(shí)現(xiàn)優(yōu)化
問題分析
類似的遞歸重復(fù)計(jì)算問題很多逗概，但未必都可以簡(jiǎn)單的像 斐波那契數(shù)列 問題這么容易化為非遞歸弟晚，那么有沒有辦法遞歸的前提下保證沒有重復(fù)計(jì)算呢？思路也很簡(jiǎn)單：計(jì)算結(jié)果加入緩存。
實(shí)現(xiàn) - C++
class Solution{
public:
vector<int> buffer;
int fibonacci(int n) {
if(n == 1){
return 0;
} else if (n == 2){
return 1;
}
int n1, n2, sn;
if (buffer.size() == 0) {
buffer.push_back(0);
buffer.push_back(1);
}
if (buffer.size() > n - 2) {
n1 = buffer[n - 2];
} else {
n1 = fibonacci(n - 1);
}
if (buffer.size() > n - 3) {
n2 = buffer[n - 3];
} else {
n2 = fibonacci(n - 2);
}
sn = n1 + n2;
if (buffer.size() < n) {
buffer.push_back(sn);
}
return sn;
}
};
實(shí)現(xiàn) - Java
class Solution {
ArrayList<Integer> buffer = new ArrayList<Integer>();
public int fibonacci(int n) {
if(n == 1){
return 0;
} else if (n == 2){
return 1;
}
int n1, n2, sn;
if (buffer.size() == 0) {
buffer.add(0);
buffer.add(1);
}
if (buffer.size() > n - 2) {
n1 = buffer.get(n - 2);
} else {
n1 = fibonacci(n - 1);
}
if (buffer.size() > n - 3) {
n2 = buffer.get(n - 3);
} else {
n2 = fibonacci(n - 2);
}
sn = n1 + n2;
if (buffer.size() < n) {
buffer.add(sn);
}
return sn;
}
}
結(jié)果分析
- 結(jié)果：經(jīng)測(cè)試
C++同樣最快可以以10ms輕松通過 LintCode 的評(píng)測(cè)卿城。Java也跑出了1269ms的成績(jī)枚钓，可喜可賀。 - 分析：雖然空間復(fù)雜度相對(duì)非遞歸提升到了
o(n)瑟押，不過在不改動(dòng)遞歸結(jié)構(gòu)的前提下搀捷，也算達(dá)到了不錯(cuò)的效果。 - 細(xì)節(jié)：
- 在枚舉
f(1)多望、f(2)后再聲明變量嫩舟，以節(jié)約內(nèi)存空間。 -
n是從1開始怀偷，buffer是從0開始家厌。 -
f(1)和f(2)要一開始加進(jìn)來，如果遞歸加入會(huì)順序相反椎工，導(dǎo)致結(jié)果出錯(cuò)饭于。
矩陣快速冪實(shí)現(xiàn)
概述
根據(jù)@iFzzzh的提醒，發(fā)現(xiàn)了大大降低時(shí)間復(fù)雜度的方法维蒙。
原理
先介紹一下什么是快速冪镰绎，如下式：
$$
f(n) = a^n\tag{1}
$$
當(dāng) $n$ 為偶數(shù)時(shí)則有:
$$
f(n) = (a{\frac{n}{2}})2=f(\frac{n}{2})^2\tag{2}
$$
當(dāng) $n$ 為奇數(shù)時(shí)則有:
$$
f(n) = (a{\lfloor\frac{n}{2}\rfloor})2 \times a=f(\lfloor\frac{n}{2}\rfloor)^2\times a\tag{3}
$$
顯然 (1) 式時(shí)間復(fù)雜度為 o(n) ，而 (2) (3) 式復(fù)雜度為 o(log_2 n)木西，這就是快速冪，簡(jiǎn)單的來說就是以二分降冪的方式減少計(jì)算步驟随静。
問題分析
類比上述的快速冪法八千，采用矩陣的方式也可以將 斐波那契數(shù)列 化為 a^n 的格式，達(dá)到降冪的效果：
$$
\begin{aligned}
\begin{bmatrix}
f(n)\
f(n-1)\
\end{bmatrix}&=
\begin{bmatrix}
f(n-1)+f(n-2)\
f(n-1)\
\end{bmatrix}\\
&=\begin{bmatrix}
1 & 1\
1 & 0\
\end{bmatrix}\times
\begin{bmatrix}
f(n-1)\
f(n-2)\
\end{bmatrix}\\
&=\begin{bmatrix}
1 & 1\
1 & 0\
\end{bmatrix}^2\times
\begin{bmatrix}
f(n-2)\
f(n-3)\
\end{bmatrix}\
&\qquad\qquad\quad\vdots\
&=\begin{bmatrix}
1 & 1\
1 & 0\
\end{bmatrix}^{n-2}\times
\begin{bmatrix}
f(2)\
f(1)\
\end{bmatrix}\
\end{aligned}
$$
根據(jù) 斐波那契數(shù)列 的定義燎猛，f(1) f(2) 為常數(shù)恋捆，此時(shí)便可以通過快速冪的方式計(jì)算 f(n) 的值了。
實(shí)現(xiàn) - C++
class Solution{
public:
int fibonacci(int n) {
if(n == 1){
return 0;
}
if(n == 2){
return 1;
}
int s[2][2];
rxn(n - 2, s);
return s[0][0];
}
void rxn(int n, int result[2][2]){
if(n == 0){
result[0][0] = 1;
result[0][1] = 0;
result[1][0] = 0;
result[1][1] = 1;
return;
}
if(n == 1){
result[0][0] = 1;
result[0][1] = 1;
result[1][0] = 1;
result[1][1] = 0;
return;
}
if(n > 1){
int s[2][2] = {1, 1, 1, 0};
int buffer[2][2];
rxn(n / 2, buffer);
int buffer2[2][2];
mul(buffer, buffer, buffer2);
if(n % 2 == 0){
result[0][0] = buffer2[0][0];
result[0][1] = buffer2[0][1];
result[1][0] = buffer2[1][0];
result[1][1] = buffer2[1][1];
}else{
mul(buffer2, s, result);
}
}
}
void mul(int m1[2][2], int m2[2][2], int result[2][2]) {
result[0][0] = m1[0][0] * m2[0][0] + m1[0][1] * m2[1][0];
result[0][1] = m1[0][0] * m2[0][1] + m1[0][1] * m2[1][1];
result[1][0] = m1[1][0] * m2[0][0] + m1[1][1] * m2[1][0];
result[1][1] = m1[1][0] * m2[0][1] + m1[1][1] * m2[1][1];
}
};
實(shí)現(xiàn) - Java
class Solution {
public int fibonacci(int n) {
if(n == 1){
return 0;
} else if (n == 2){
return 1;
}
int s[][] = new int[2][2];
rxn(n - 2, s);
return s[0][0];
}
public void rxn(int n, int[][] result){
if(n == 0){
result[0][0] = 1;
result[0][1] = 0;
result[1][0] = 0;
result[1][1] = 1;
return;
}
if(n == 1){
result[0][0] = 1;
result[0][1] = 1;
result[1][0] = 1;
result[1][1] = 0;
return;
}
if(n > 1){
int s[][] = {{1, 1}, {1, 0}};
int buffer[][] = new int[2][2];
rxn(n / 2, buffer);
int buffer2[][] = new int[2][2];
mul(buffer, buffer, buffer2);
if(n % 2 == 0){
result[0][0] = buffer2[0][0];
result[0][1] = buffer2[0][1];
result[1][0] = buffer2[1][0];
result[1][1] = buffer2[1][1];
}else{
mul(buffer2, s, result);
}
}
}
public void mul(int[][] m1, int[][] m2, int[][] result) {
result[0][0] = m1[0][0] * m2[0][0] + m1[0][1] * m2[1][0];
result[0][1] = m1[0][0] * m2[0][1] + m1[0][1] * m2[1][1];
result[1][0] = m1[1][0] * m2[0][0] + m1[1][1] * m2[1][0];
result[1][1] = m1[1][0] * m2[0][1] + m1[1][1] * m2[1][1];
}
}
結(jié)果分析
- 結(jié)果：
C++最快可以以10ms通過 LintCode 的評(píng)測(cè)重绷。Java最快可以以1200ms通過 LintCode 的評(píng)測(cè)沸停。 - 分析：可能是由于 LintCode 測(cè)試數(shù)據(jù)不夠大的原因，矩陣快速冪并沒有體現(xiàn)出時(shí)間復(fù)雜度為
o(log_2 n)應(yīng)有的優(yōu)勢(shì)昭卓，不過根據(jù)其單步計(jì)算量提升愤钾，時(shí)間卻與非遞歸遞歸優(yōu)化達(dá)到同一水平，可以判斷出其效果還是有的候醒。
總結(jié)
理論上講的通的道理只是理論上能颁，小問題到了手上解決掉才能明白。簡(jiǎn)單的問題弄透也不容易倒淫，我記錄一下這個(gè)思路省得忘了伙菊，能夠有人用得上自然更好。當(dāng)然誰要是能給我個(gè)更好的答案才是極好的。
