南开大学软件学院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) 。
算法三：矩阵快速幂算法
数列递推公式的矩阵形式
，数学通项公式的矩阵形式
即使有了通项公式，要计算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)快得更多
为什么学习算法
- 根据数据规模 选择恰当时间复杂度的算法 是很重要的
- 本课程会介绍更多的方法和思想来优化 时间复杂度，矩阵快速幂算法就是分治思想 的一个经典应用
- 优化时间复杂度带来的效率提升往往是显著的，但是设计出新的低复杂度算法 是难度非常高的
- 需要澄清的是，程序的实际运行时间不仅仅由算法的时间复杂度决定的
全部评论 (0)
还没有任何评论哟~