斐波那契的几种思路,你都会吗
文章目录
- 递归
- 数组
- 迭代
- 矩阵快速幂
- 对角化(通项)
茴字的四种写法,你都会么?
递归
- 时间
>O(n) - 空间
O(1)
int fibo(int n){
if(1==n || 2==n) return 1;
return fibo(n-1) + fibo(n-2);
}
数组
- 时间
O(n) - 空间
O(n)
#define MAXN 100
int fibo(int n){
int dp[MAXN];
dp[0] = 0; dp[1] = 1;
for(int i=2; i<=n; i++){
dp[i] = dp[i-1] + dp[i-2];
}
return dp[n];
}
迭代
- 时间
O(n) - 空间
O(1)
int fibo(int n){
int f1=1, f2=1, f;
while(n>=3){
n--;
f = f1+f2;
f1 = f2;
f2 = f;
}
return f;
}
矩阵快速幂
- 时间
O(logn) - 空间
O(1)
已知
x
t
+
1
=
x
t
+
x
t
−
1
\Large x_{t+1} = x_t + x_{t-1}
xt+1=xt+xt−1, 令
X
t
=
[
x
t
−
1
,
x
t
]
T
\Large X_t=[x_{t-1}, x_t]^T
Xt=[xt−1,xt]T, 则有
X
t
=
[
0
1
1
1
]
X
t
−
1
=
[
0
1
1
1
]
t
−
1
X
1
=
[
0
1
1
1
]
t
−
1
[
0
1
]
\Large X_{t} = \begin{bmatrix} 0 & 1 \\ 1 & 1 \end{bmatrix}X_{t-1} =\begin{bmatrix} 0 & 1 \\ 1 & 1 \end{bmatrix}^{t-1}X_1 = \begin{bmatrix} 0 & 1 \\ 1 & 1 \end{bmatrix}^{t-1}\begin{bmatrix} 0 \\ 1 \end{bmatrix}
Xt=
0111
Xt−1=
0111
t−1X1=
0111
t−1
01
Eigen::Matrtix2f fast_power(Eigen::Matrix2f& mat, int n){
if(0 == n) return Eigen::Matrix2x::Identity();
if(1 == n) return mat;
if(n&2) return mat*fast_power(mat, n-1);
Eigen::Matrix2f tmp = fast_power(mat, n>>1);
return tmp*tmp;
}
int fibo(int n){
Eigen::Matrix2f base;
base << 0, 1, 1, 1;
Eigen::Matrix2f X1;
X1 << 0, 1;
return (int)(fast_power(base, n-1)*X1)[1];
}
对角化(通项)
- 时间
O(1) - 空间
O(1)
在上式中, 令
A
=
[
0
1
1
1
]
\Large A=\begin{bmatrix} 0 & 1 \\ 1 & 1 \end{bmatrix}
A=
0111
, 得到两个特征值
λ
1
=
1
+
5
2
,
λ
2
=
1
−
5
2
\Large \lambda_1=\frac{1+\sqrt{5}}{2}, \lambda_2=\frac{1-\sqrt{5}}{2}
λ1=21+5,λ2=21−5, 以及对应的特征向量
η
1
=
[
1
1
+
5
2
]
,
η
2
=
[
1
1
−
5
2
]
\Large \eta_1=\begin{bmatrix} 1 \\ \frac{1+\sqrt{5}}{2} \end{bmatrix}, \eta_2=\begin{bmatrix} 1 \\ \frac{1-\sqrt{5}}{2} \end{bmatrix}
η1=
121+5
,η2=
121−5
. 那么很容易将
A
\Large A
A对角化:
A
=
P
−
1
Σ
P
\Large A = P^{-1} \Sigma P
A=P−1ΣP
其中
β
1
=
η
1
∣
η
1
∣
,
β
2
=
η
2
∣
η
2
∣
,
P
=
[
β
1
,
β
2
]
,
Σ
=
d
i
a
g
(
λ
1
,
λ
2
)
\Large \beta_1 = \frac{\eta_1}{|\eta_1|}, \beta_2 = \frac{\eta_2}{|\eta_2|}, P = [\beta_1, \beta_2], \Sigma=diag(\lambda_1, \lambda_2)
β1=∣η1∣η1,β2=∣η2∣η2,P=[β1,β2],Σ=diag(λ1,λ2). 这里由于
η
1
,
η
2
\Large \eta_1, \eta_2
η1,η2属于不同的特征值,已经能够保证正交,因此不需要额外的正交化.
那么有
A
t
=
(
P
−
1
Σ
P
)
t
=
P
−
1
Σ
t
P
\Large A^{t} = (P^{-1}\Sigma P)^t = P^{-1}\Sigma^t P
At=(P−1ΣP)t=P−1ΣtP
那么前面求
X
t
\Large X_t
Xt也变得简单了
X
t
=
[
0
1
1
1
]
t
−
1
[
0
1
]
=
A
t
−
1
[
0
1
]
=
P
−
1
Σ
t
−
1
P
[
0
1
]
\Large X_{t} = \begin{bmatrix} 0 & 1 \\ 1 & 1 \end{bmatrix}^{t-1}\begin{bmatrix} 0 \\ 1 \end{bmatrix} = A^{t-1}\begin{bmatrix} 0 \\ 1 \end{bmatrix} = P^{-1}\Sigma^{t-1} P \begin{bmatrix} 0 \\ 1 \end{bmatrix}
Xt=
0111
t−1
01
=At−1
01
=P−1Σt−1P
01
上式中,
P
\large P
P是一个二阶方阵,求逆计算量并不大.
Σ
\Large \Sigma
Σ是一个二阶对角阵, 幂方也只需要给对角线元素幂方即可. 上式的计算量其实并不大.
这里最大的问题是精度损失, 有可能在计算过程中会因为float精度的问题,导致结果转换为int时存在一定的误差.