南开大学软件学院2021年秋季学期研究生算法课程（复习）

本文主要是介绍南开大学软件学院2021年秋季学期研究生算法课程（复习），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

为什么要学习算法？

在有限时间和内存下，编写程序正确地或有效地解决问题。

计算Fibonacci数列的第n项

算法一：递归函数

int F(int n){if(n<=2) return 1;return F(n-1)+F(n-2);
}

算法二：递推循环

int F(int n){if(n<=2) return 1;int f1=1, f2=1;for(int i=3;i<=n;i++){int temp = f1+f2;f1=f2;f2=temp;}return f2;
}

递归函数计算100项时，会无法完成计算，递推可以很快计算出100项。

递归算法的时间复杂度为O(1.618^n)，递推函数的时间复杂度为O(n)。

算法三：矩阵快速幂算法

数列递推公式的矩阵形式 $\bigl(\begin{smallmatrix} F_n\\ F_{n-1} \end{smallmatrix}\bigr) = \begin{pmatrix} 1 & 1\\ 1 & 0 \end{pmatrix} \bigl(\begin{smallmatrix} F_{n-1}\\ F_{n-2} \end{smallmatrix}\bigr)$ ，数学通项公式的矩阵形式 $\bigl(\begin{smallmatrix} F_n\\ F_{n-1} \end{smallmatrix}\bigr) = \begin{pmatrix} 1 & 1\\ 1 & 0 \end{pmatrix}^{n-2} \bigl(\begin{smallmatrix} 1\\ 1 \end{smallmatrix}\bigr)$

即使有了通项公式，要计算n-2次幂还是需要O(n)时间

快速幂算法

$A^n=\left\{\begin{matrix} (A^{\frac{n}{2}})^2,\ n=2k\\ A\times(A^\frac{n-1}{2})^2,\ n=2k+1 \end{matrix}\right.$

每次迭代问题规模减半，时间复杂度O(log n)

class Matrix{Matrix operator*(const Matrix &);// ...
};Matrix Quickpow(Matrix A, int n){if(n==1) return A;Matrix half = Quickpow(A, n/2);if(n%2==1){return A*half*half;}else{return half*half;}
}int F(int n){if(n<=2) return 1;Matric A(1,1,1,0);A = Quickpow(A,n-2);return A[0][0] + A[0][1];
}

当数据规模更大时，O(log n)能比O(n)快得更多