导图社区 算法设计与分析
这是一篇关于算法设计与分析的思维导图，主要内容包括：绪论，分治法，动态规划法，贪心算法，回溯法，分支限界法，分治法与动态规划法的异同，回溯法和分支限界法异同。
社区模板帮助中心，点此进入>>
互联网9大思维
组织架构-单商户商城webAPP 思维导图。
域控上线
python思维导图
css
CSS
计算机操作系统思维导图
计算机组成原理
IMX6UL(A7)
考试学情分析系统
算法设计与分析
绪论
算法基本概念
算法特性
输入
输出
有穷性
确定性
可行性
时间复杂度
C=F（N,I,A）
问题规模，输入，算法本身
渐进复杂性
T*(n)
子主题
渐进记号
渐进上界O
升阶
若lim n趋向于无穷时，f(n)/g(n)=0
渐进下界Ω
减阶
……=♾️
渐进精确界θ
时间复杂度排行 与O的计算性质
分治法
主方法递归方程求T(n)
基本思想
要背！
将一个问题规模为n的原问题分解为k个规模较小的子问题 这些子问题相互独立且与原问题相同，递归的求解这些子问题的解， 然后合并构造出原问题的解
分治法解决问题的特征
问题的规模缩小到一定程度就很容易解决
可以分解为若干个规模较小的相同问题
子问题的解可以合并为原问题的解
简记
易解决、可分解、可合并
步骤
分解
递归
合并
例子
大整数乘法
T(n)=log(n²)
二分查找
O(logn)
快速排序
最好&平均
O(nlogn)
最坏
O(n²)
代码要背！！
循环赛日程表
Strassen矩阵乘法
归并排序
动态规划法
介绍
将一个复杂的问题分解为一系列相互关联的子问题 各个子问题往往不是相互独立，记录子问题的解， 避免重复，然后利用这些记录的解构建原问题的解
基本要素
最优子结构性质
子问题重叠性质
自底向上求解方式
解题步骤
背！！
分析最优解性质，刻画最优解的结构特征 考察是否适合用动态规划法
分析适合
递归定义最优值(建立递归式方程)
递归方程
以自底向上的方式计算出最优值， 并记录相关信息
自底向上
构造最优解
动态规划法为什么需要 最优子结构性质
动态规划法是通过将原问题分解为子问题， 求解子问题的最优解来构造原问题的最优解 最优子结构性质保证了原问题的最优解可以 由子问题的最优解组合而成
最长公共子序列问题
列表法
时间复杂度O(mn)
矩阵连乘
贪心算法
记一下
贪心选择性质
特点
了解
解决
合并
证明
背包问题
会场安排问题
哈夫曼树和哈夫曼编码
最小生成树
普里姆算法
找顶点
克鲁斯卡尔算法
找权最小边
O(mlogm)
最短路径问题
最优装载问题
注意
贪心算法不能解决0-1背包问题和n皇后问题
回溯法
n皇后问题
分支限界法
分类
队列式分支限界法
优先队列式分支限界法
选取扩展结点的原则
结点的优先级
任务分配问题
最大团问题
分治法与动态规划法的异同
同
都需要对问题进行分解
都通过子问题求解原问题
异
子问题关联性
分治法子问题相互独立
动态规划法子问题可能重叠
解决问题方式
分治法递归求解子问题 然后合并
动态规划法记录子问题的解 然后构建原问题的解
回溯法和分支限界法异同
都用于搜索问题的解空间
都可以用树结构表示解空间
搜索方式
回溯法
深度优先
广度优先或最佳优先
目的和应用场景
用于找到问题的所有解或一个解
用于找到问题的最优解
自由主题
