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

为什么要学习算法？
【复习南开大学软件学院2021年秋季学期研究生算法课程】在有限时间和内存下，编写程序正确地或有效地解决问题。
计算数列的第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) 。
算法三：矩阵快速幂算法
数列递推公式的矩阵形式
，数学通项公式的矩阵形式
即使有了通项公式，要计算n-2次幂还是需要O(n)时间
快速幂算法
每次迭代问题规模减半，时间复杂度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)快得更多
为什么学习算法

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

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