导图社区 算法分析与设计
- 432
- 35
- 5
- 举报
算法分析与设计
包含常见的递归分治算法,动态规划,贪心算法常见的算法，典型的算法配有代码.
编辑于2020-06-30 21:10:29- 计算机网络
内带考研408专业课考纲 计算机网络全书,适合考研期末考试等复习 参考的是比较流行的课本--谢希仁版 历时一个月精心制作如有错误或不当之处请谅解 包含原书中的所有研究生考试的知识点 感谢你的使用考研加油
- 运输层
计算机网络运输层对应课本谢希仁 包含运输层的所有知识点。OSI七层模型中的物理层、数据链路层和网络层，它们是面向网络通信的低三层协议。运输层负责端到端的通信，既是七层模型中负责数据通信的最高层，又是面向网络通信的低三层和面向信息处理的最高三层之间的中间层。干货满满，赶快收藏学起来吧！
- 算法分析与设计
包含常见的递归分治算法,动态规划,贪心算法常见的算法，典型的算法配有代码.
算法分析与设计
社区模板帮助中心，点此进入>>
- 计算机网络
内带考研408专业课考纲 计算机网络全书,适合考研期末考试等复习 参考的是比较流行的课本--谢希仁版 历时一个月精心制作如有错误或不当之处请谅解 包含原书中的所有研究生考试的知识点 感谢你的使用考研加油
- 运输层
计算机网络运输层对应课本谢希仁 包含运输层的所有知识点。OSI七层模型中的物理层、数据链路层和网络层，它们是面向网络通信的低三层协议。运输层负责端到端的通信，既是七层模型中负责数据通信的最高层，又是面向网络通信的低三层和面向信息处理的最高三层之间的中间层。干货满满，赶快收藏学起来吧！
- 算法分析与设计
包含常见的递归分治算法,动态规划,贪心算法常见的算法，典型的算法配有代码.
- 相似推荐
- 大纲
算法分析与设计复习
概述
什么是的算法
算法是解决问题的一种方法或一个过程
程序与算法的区别
程序是算法用某种程序设计语言的具体实现
程序不满足算法的性质
算法往往只是程序的一部分
说的高端一些
算法是解决问题的步骤;程序是算法的代码实现,算法依靠程序完成功能;程序需要算法作为灵魂
程序是结果,算法是手段
程序=算法+数据结构
算法的性质
输入
输出
至少有一个量作为输出
确定性
组成的每条指令是清晰,无歧义的
有限性
每条指令的执行次数是有限的,执行每条指令的时间也是有限的
算法评价的标准
时间复杂度
空间复杂度
好算法的特性
正确性
可读性
健壮性
高效性
低存储要求
算法复杂度概念
算法复杂度=算法所需要的计算机资源
算法复杂度的依赖
时间复杂性T(n)
最好
最坏
平均
空间复杂性S(n)
算法渐进复杂度的数学表述
t(n)是T(n)略去低阶项留下的主项

渐近分析符号
上界记为O
下界记为Ω
复杂度计算
递归与分治
递归
概念
直接或间接的调用自身的算法称为递归算法
用函数自身给出定义的函数称为递归函数
二要素
函数表达式
终止条件
分治
概念
将一个难以解决的大问题,分割成一些规模较小的相同问题,各个击破,分而治之
可行性
原问题可以划分
子问题都可解
利用子问题的解求出原问题的解
与递归的关系
前提
规模缩小到一定程度后就可以/容易解决
问题可以分割成若干规模较小的相同问题
具有最优子结构
子问题可以合并为该问题的解
各个子问题是相互独立的
子问题之间不包含公共子问题
基本思想
分析问题本身的特征
如何设计有效的分治策略
形式化写出分治法的基本步骤
解决小规模问题
分割大问题
递归计算各子问题
将子问题的解合并成原问题的解
理想状态
子问题能均分
子问题容易合并
相关算法
常考
二分搜索
代码
C++递归&非递归
 
java递归&非递归
public class 二分搜索 { static int Bsearch(int target,int[] data){//递归实现 return Bsearch(target, data, 0, data.length-1); } private static int Bsearch(int target,int[] data,int start,int end){//递归实现 if (start>end) return -1; int middle=start+(end-start)/2; if (data[middle]==target) return middle; if (data[middle]<target){ return Bsearch(target, data, middle+1, end); } return Bsearch(target, data, start, middle-1); } static int BsearchCycle(int target,int[] data) {//非递归实现 int start=0,end=data.length-1; while (start<=end){ int middle=start+(end-start)/2; if (data[middle]>target){ end=middle-1; continue; } else if (data[middle]<target){ start=middle+1; continue; } return middle; } return -1; } public static void main(String arg[]){//main--来自高金磊 int[] ints=new int[]{1,3,9,100,103,104,105}; for (int i = 0; i < ints.length; i++) { System.out.println("递归二分查询"+ints[i]+"索引是"+Bsearch(ints[i], ints)); System.err.println("非递归查询"+ints[i]+"索引是"+BsearchCycle(ints[i], ints)); } System.out.println("递归二分查询"+0+"索引是"+Bsearch(0, ints)); System.err.println("非递归查询"+0+"索引是"+BsearchCycle(0, ints)); }
合并排序
将待排的数组分成两个部分对每一部分继续分割,直到不可分
将所有集合两两合并
合并的时候使用归并
示意图
代码
C++

不建议用非递归
java
递归
public class 合并排序递归 { static void sort(int[] data,int start,int end){ if (start>=end){ return; } int middle=start+(end-start)/2; sort(data, start, middle); sort(data, middle+1, end); merge(data, start, middle,end); } static void merge(int[] data,int start,int middle,int end){ int ss=start; int ss2=middle+1; int da[]=new int[end-start+1]; for (int i = 0; i < da.length; i++) { if (ss>middle) { da[i]=data[ss2++]; continue; } if (ss2>end){ da[i]=data[ss++]; continue; } if (data[ss]>data[ss2]){ da[i]=data[ss2]; ss2++; } else { da[i]=data[ss]; ss++; } } for (int i = 0; i < da.length; i++) { data[start+i]=da[i]; } } public static void main(String arg[]){//main--来自高金磊 int[] data={1,4,2,1,21,231,34,5,675,5}; sort(data, 0, data.length-1); } }
快排
挖坑填萝卜
注意基准值的选择
每次都使基准值放到正确位置,其他元素正确的位于基准值的两侧
步骤
代码
java
数组递归实现
public class 快速排序的数组实现 { private void quick_sort(int[] arr){ quick_sort(arr, 0, arr.length-1); } private void quick_sort(int[] arr,int start,int end){ if (start>=end) return; int s=start; int e=end; // int base=arr[s]; while (s<e){ while (arr[s]<arr[e]&&s<e){ e--; } int middle=arr[s]; arr[s]=arr[e]; arr[e]=middle; s++; while (arr[s]<arr[e]&&s<e){ s++; } middle=arr[s]; arr[s]=arr[e]; arr[e]=middle; e--; } quick_sort(arr, start, s-1); quick_sort(arr, s+1, end); } public static void main(String arg[]){//main--来自高金磊 int[] nums={5,4,8,6,2,1,47,7,3,2,5,8,9,4}; new 快速排序的数组实现().quick_sort(nums); for (int num : nums) { System.out.print(num+"\t"); } } }
掌握
汉诺塔
问题
解决方案
奇次移动移动
将最小的圆盘移动到顺时针方向上的下一个塔座上
偶次移动
保持最小的不动,在其他两个塔座之间将较小的移动到另一个塔座上去
代码示例(一个小小的过程演示)
import java.util.LinkedList; import java.util.Scanner; public class 汉诺塔模拟器 { LinkedList<Integer> pallar1=new LinkedList<>(); LinkedList<Integer> pallar2=new LinkedList<>(); LinkedList<Integer> pallar3=new LinkedList<>(); private void init(int size){ for (int i = size; i >0; i--) { pallar1.push(i); } print(); } private void next() throws Exception { if (!pallar1.isEmpty()&&pallar1.peek()==1){ pallar2.push(pallar1.poll()); move2(pallar1, pallar3); }else if (!pallar2.isEmpty()&&pallar2.peek()==1){ pallar3.push(pallar2.poll()); move2(pallar1, pallar2); }else { pallar1.push(pallar3.poll()); move2(pallar2, pallar3); } } private void move2(LinkedList<Integer> A,LinkedList<Integer> B) throws Exception { if (A.isEmpty()&&B.isEmpty()){ print(); throw new Exception("游戏已结束"); } if (A.isEmpty()){ A.push(B.poll()); return; } if (B.isEmpty()){ B.push(A.poll()); return; } if (A.peek()<B.peek()) { B.push(A.poll()); return; } A.push(B.poll()); } private void print(){ System.out.print("柱子1:"); for (Integer integer : pallar1) { System.out.print("---"+integer); } System.out.println(); System.out.print("柱子2:"); for (Integer integer : pallar2) { System.out.print("---"+integer); } System.out.println(); System.out.print("柱子3:"); for (Integer integer : pallar3) { System.out.print("---"+integer); } System.out.println(); } public static void main(String arg[]){//main--来自高金磊 汉诺塔模拟器 hnt=new 汉诺塔模拟器(); System.out.println("输入游戏规模:"); Scanner scanner=new Scanner(System.in); hnt.init(scanner.nextInt()); try { while (true){ System.out.println("输入n显示下一步,输入all显示全部"); String target=scanner.next(); if (target.equals("n")){ hnt.next(); hnt.print(); } else if (target.equals("all")){ System.out.println("输入显示时间间隔(ms)--建议300"); int t=scanner.nextInt(); while (true){ try { Thread.sleep(t); } catch (InterruptedException e) { e.printStackTrace(); } hnt.next(); hnt.print(); } } } } catch (Exception e){ System.err.println(e.getMessage()); } } }
全排列
了解
大整数乘法
master定理后的表达式
棋盘覆盖
线性时间选择
循环赛日程表
动态规划
概念
类似分治算法
基本思想也是将待求解问题分解成若干子问题
总体思想
经过分解的子问题往往不是相互独立的
有些子问题被重复计算了许多次
可以保存子问题的答案以后优先使用计算过的值
使用场景
通常用于求解具有最优性质的问题
这类问题中,可能会有很多可行解,每一个解都对应一个值,我们希望找到具有最优值的解
适用条件
两个重要性质
最优子结构
概念
问题的最优解包含子问题的最优解
这样才能从子问题的最优解中找到问题的最优解
分析问题的最优子结构时所用的方法具有普遍性
利用最优子结构的性质,以自底向上的方式递归地从子问题的最优解逐步构造整个问题的最优解
是DP能够使用的前提
重叠子问题
子问题的空间非常小
个数是多项式函数
特点
DP具有多种形式,算法多种多样,但是他们都具有相同的填表格式
与分治算法的关系
DP=分治算法+解决冗余
基本要素
最优子结构
重叠子问题
理解多阶段决策问题
设计技巧
阶段的划分
状态的表示
设计DP算法步骤
找到最优解的性质,并刻画其结构特征
递归的定义最优值---写出DP方程
自底向上的方式计算最优值
根据最优值信息构造最优解
备忘录方法的概念
采用自顶向下的计算方式
每一个子问题只在第一次被调用的时候计算
相关算法
01背包
算法
斐波那契(备忘录)
java
int[] data; private int fbnq_DP(int num){ if (num<2) return 1; data=new int[num]; data[0]=1; data[1]=1; for (int i = 2; i < data.length; i++) { data[i]=data[i-1]+data[i-2]; } return data[data.length-1]; }
矩阵连乘
最优子结构证明
设(A1…Ak)(Ak+1…An) 具有最少乘法次数，则(A1…Ak)中加括号的方法使A1..Ak乘法次数最少。否则设存在另一种加括号方法(A1…Ak)'更优，则(A1…Ak)'(Ak+1…An) 比 (A1…Ak)(Ak+1…An) 更优，矛盾。同理， (Ak+1…An) 内的连乘方法也是最优的。 来自 <https://www.cnblogs.com/chuaner/p/11757520.html>
就是矩阵乘法加括号(集合率)的问题
最优子结构
A[i,j]是最优的则A[i,k]A[k,j]是最优的
算法思路

整数划分
将n划分成不同整数之和的划分数
（1）当 n = 1 时，不论m的值为多少（m > 0 )，只有一种划分即 { 1 }; (2) 当 m = 1 时，不论n的值为多少，只有一种划分即 n 个 1，{ 1, 1, 1, ..., 1 }; (3) 当 n = m 时，根据划分中是否包含 n，可以分为两种情况： (a). 划分中包含n的情况，只有一个即 { n }； (b). 划分中不包含n的情况，这时划分中最大的数字也一定比 n 小，即 n 的所有 ( n - 1 ) 划分。 因此 f(n, n) = 1 + f(n, n-1); (4) 当 n < m 时，由于划分中不可能出现负数，因此就相当于 f(n, n); (5) 但 n > m 时，根据划分中是否包含最大值 m，可以分为两种情况： (a). 划分中包含 m 的情况，即 { m, { x1, x2, ..., xi } }, 其中 { x1, x2, ..., xi } 的和为 n - m，可能再次出现 m，因此是（n - m）的 m 划分，因此这种划分个数为 f(n-m, m); (b). 划分中不包含 m 的情况，则划分中所有值都比 m 小，即 n 的 ( m - 1 ) 划分，个数为 f(n, m - 1); 因此 f(n, m) = f(n - m, m) + f(n, m - 1);
公式
f(n, m) = 1; ( n = 1 or m = 1 )
f(n, n); ( n < m )
1+ f(n, m - 1); ( n = m )
f(n - m, m) + f(n, m - 1); ( n > m )
存在的问题
空间溢出
需要存储中间结果
贪心算法
概念
总是做出当前看来最好的选择
不从整体最优考虑
局部最优
其结果往往是最优的但不一定是最优的--只是近似
基本思想
将求解过程看作一系列选择,每次选择一个输入,每次选择都是当前状态下的最好选择
之后问题规模变小重复上述过程
基本要素
最优子结构
同DP
贪心选择性
所求问题的整体最优解可以通过一系列局部最优的选择即贪心选择来达到
这是与DP的最核心的区别
通常使用自顶向下的方式解子问题
必须证明每一步所做出的贪心选择最终能导致问题的整体最优解
局限性
不能保证解是最佳的
不能用来求最大最小解问题
只能求满足某些约束条件的可行解的范围
与DP的差异
略
算法
必考
活动安排
描述
活动集合中选出最大相容活动子集合
属于高效安排一系列争用某一公共资源的活动
贪心选择性
为未安排的活动留下尽可能多的时间
使剩余的可安排时间段极大化,以便安排尽可能的相容活动
解决方案
将活动时间的结束时间按照递增排序
尽可能选择结束时间早的
算法
java
public static int Issue(int s[],int e[]){ //sort by end time for (int i = 0; i < s.length; i++) { for (int j = i+1; j < s.length; j++) { if (e[i]>e[j]){ int middle=e[i]; e[i]=e[j]; e[j]=middle; middle=s[i]; s[i]=s[j]; s[j]=middle; } } } //use Algorithm to select int last_time=0;//record the early end time int count=0; for (int i = 0; i < s.length; i++) { if (s[i]>=last_time) { count++; last_time=e[i]; } } return count; }
单源最短路径
计算从一点出发到达其他点的最短路径
算法
Dijkstra算法
贪心策略
每次都从V-S种找出具有最短特殊路长的顶点u加入S
算法思想
初始时S只有源
每次从未连接的节点中添加具有最短特殊路长度的顶点u,将u加入S种,并对dist数组进行修改
说明
u来自未添加到S组,且将他添加到S种代价最低的结点
dist的更新仅仅需要更新未被添加的结点而u来自那些未被添加且最小的一个
算法

常考
一般背包
与01的区别
01只有装和不装
不能贪心,其贪心结果不能保证使正确的
一般背包可以只选择物品的一部分
贪心选择性
选择剩余物品中性价比最大的物品
步骤
计算单位重量的价值(V/W)
依据贪心选择策略将尽可能多的单位重量价值最高的物品装入背包
直到背包满为止
算法
java
略
最小生成树
prim算法
G=(V,E)是连通带权图
S={1},S只要是V的真子集就做以下贪心算法
贪心选择
取i∈S,j∈V-S,且c[i][j]最小
将顶点j添加到S
每次将未添加的点以最小价值添加到构成的树中
Kruskal算法
贪心选择策略
每次都选择最小的可以连通两个不同连通分支的边
多机调度
问题
n个作业m台机器如何尽可能短的时间完成
贪心选择
采用最长处理时间作业优先
哈夫曼编码
贪心准则
合并具有最小频率的两棵树
用于压缩数据
将频率高的字符用较短的编码
是一种前缀码
使用01串作为其代码
任何一个字符的代码都不能是其他字符代码的前缀
算法