算法设计与分析 课程期末复习简记 |
您所在的位置：网站首页 › 采用贪心算法的最优装载问题的主要计算量 › 算法设计与分析 课程期末复习简记 |
算法设计与分析 课程期末复习简记
|
目录 网络流 线性规划 回溯算法 分支限界 贪心算法 动态规划 分治算法 算法复杂度分析 相关概念 网络流 下面是本章需要掌握的知识 • 流量⽹络的相关概念 • 最⼤流的概念 • 最⼩割集合的概念 • Dinic有效算法的步骤 • 会⼿推⼀个流量⽹络的最⼤流 下面对此依次进行复习 首先看流量网络的相关概念
上面是课程PPT中的定义，真是抽象
实际上，我们直接将某个流量网络进行建模出来就是上图这样，其中每一条弧上的第一个数字代表该条弧的最大流量，第二个数字代表该条弧的实际通过流量，并且定义一个发点V1、收点V6，其余的就是中间点了 那么上图所说的可行流又是什么？ 实际上可行流即从发点到收点的流量都是合法的 即每一条弧的实际流量f>=0且fp; //求a的b次方 int base=a; int index=b; while(index>0){ if(index%2==1){//指数为奇数 //将奇数变偶数 index--; res=res*base%p;//抽离出多余的一个底数 }else{//指数为偶数 index/=2;//指数缩小一半 //底数变为原来的平方 base=base*base%p; } } printf("%d\n",res); } return 0; }改进分支算法的两个方法
预处理即在算法实验题整数位乘中的补零操作 减小子问题个数即 整数位乘中我们不一定在小规模问题使用分治，即小规模问题使用正常解法即可 算法复杂度分析 相关概念对于相同输入规模的不同实例，算法的基本运算次数也不⼀样，可定义两种时间复杂度 • 最坏情况下的时间复杂度W(n) • 算法求解输入规模为n 的实例所需要的最⻓时间 • 平均情况下的时间复杂度A(n) • 在给定同样规模为n 的输入实例的概率分布下，算法求解这些实例所需要的 平均时间 其中A(n)的计算公式如下
即使用概率论中的均值计算公式 下面是上述两种时间复杂度的计算例子
函数的渐近表示
下面介绍递推方程 首先认识递推方程
下面介绍两种求解递推方程的方法 1、迭代法 步骤如下
补充知识
例题
主定理
观察可知a=9,b=3,因此logba=2，因此 又f(n)=n，即f(n)=o(n^2) 符合上述主定理的第一种情况 因此递推方程 例2
因此递推方程为
|
例题
2、递归树
例1
【本文地址】
今日新闻 |
推荐新闻 |