文章目录

• 递归
• 数组
• 迭代
• 矩阵快速幂
• 对角化(通项)

茴字的四种写法,你都会么?

递归

• 时间>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)

已知xt+1=xt+xt−1\Large x_{t+1} = x_t + x_{t-1}xt+1​=xt​+xt−1​, 令Xt=[xt−1,xt]T\Large X_t=[x_{t-1}, x_t]^TXt​=[xt−1​,xt​]T, 则有
Xt=[0111]Xt−1=[0111]t−1X1=[0111]t−1[01]\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​=​01​11​​Xt−1​=​01​11​​t−1X1​=​01​11​​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=[0111]\Large A=\begin{bmatrix} 0 & 1 \\ 1 & 1 \end{bmatrix}A=​01​11​​, 得到两个特征值λ1=1+52,λ2=1−52\Large \lambda_1=\frac{1+\sqrt{5}}{2}, \lambda_2=\frac{1-\sqrt{5}}{2}λ1​=21+5​​,λ2​=21−5​​, 以及对应的特征向量η1=[11+52],η2=[11−52]\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 AA对角化:
A=P−1ΣP\Large A = P^{-1} \Sigma P A=P−1ΣP
其中β1=η1∣η1∣,β2=η2∣η2∣,P=[β1,β2],Σ=diag(λ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​属于不同的特征值,已经能够保证正交,因此不需要额外的正交化.

那么有
At=(P−1ΣP)t=P−1ΣtP\Large A^{t} = (P^{-1}\Sigma P)^t = P^{-1}\Sigma^t P At=(P−1ΣP)t=P−1ΣtP
那么前面求Xt\Large X_tXt​也变得简单了
Xt=[0111]t−1[01]=At−1[01]=P−1Σt−1P[01]\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​=​01​11​​t−1​01​​=At−1​01​​=P−1Σt−1P​01​​
上式中, P\large PP是一个二阶方阵,求逆计算量并不大. Σ\Large \SigmaΣ是一个二阶对角阵, 幂方也只需要给对角线元素幂方即可. 上式的计算量其实并不大.

这里最大的问题是精度损失, 有可能在计算过程中会因为float精度的问题,导致结果转换为int时存在一定的误差.