【算法】20180905算法笔记整理

1、时间复杂度
O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)

沃思公式：数据结构+算法=程序

2、穷举与回溯
回溯法：向前走，碰壁回头
回溯算法的优化问题：从约束条件入手，可利用对称性裁减子树、划分成子问题等
- 分支设计优先策略
- 调整取值点与回溯点
- 调整约束条件

影响回溯算法效率的因素：
- 搜索树的结构
- 分支是否均匀
- 树的深度
- 对称程度
- 解的分布
- 分布深度
- 约束条件的判断：计算是否简单

3、递归与分治
问题的分解、子集解的合并，Hanoi问题
步骤：
- 描述递归关系
- 确定递归边界
- 递归函数译码
- 程序完善

数据的查找与排序、矩阵乘法、马的周游路线、计数逆序排名问题、消除信号的噪声和棋盘覆盖等

4、递推
数列、数阵求解与解计数应用题方面的应用
某种现象的变化结果与紧靠它前面变化的一个或一些结果紧密关联
关键是得到相邻的数据项的递推关系、归纳规律→抽象为数学模型

5、贪心算法
删数字、背包、覆盖、图的着色、遍历、哈夫曼编码、最小代价生成树等问题的求解
最优子结构性质→动态规划
贪心算法比动态规划效率高，且不存在空间限制的影响，可解决NP完全问题或大规模优化问题，得到很好近似解

6、动态规划
多阶段决策问题的最优化目标是获取导致问题最优值的最优决策序列
条件：
- 问题中的状态必须满足最优性原理
- 问题中的状态必须满足无后效性

步骤：
- 所求优化问题分成若干阶段，刻画其结构特效
- 各个阶段的状态表示及递推关系，确定初始（边界）条件
- 应用递推求解最优值
- 计算最优值，构造最优解

7、运筹学
- 规划论
- 图论与网络分析
- 排队论
- 决策论
- 存储论
- 博弈论
- 随机运筹模型

8、线性规划
一般地，在连续、可控的决策变量前提下，求一个线性函数在一组线性约束条件下的最大化、最小化问题
- 非线性规划数学模型（^2及更高）
- 动态规划数学模型（时间序列等变化）
- 随机规划数学模型（随即规划）
- 整数规划模型
- 多目标线性规划问题数学模型

决策变量、资源限量、消耗（功效、技术）系数、价值系数

灵敏度分析：
当参数发生变化时，原最优解将如何变化，或参数在什么范围内发生变化时，不会影响原最优解
当变量或条件发生变化时，将对原最优解产生怎样的影响，基于【最优解】的这种分析称为灵敏度分析

• 目标函数中价值系数C的变化
• 右端项资源约束常熟b的变化
• 约束条件中技术系数A的变化
• 增加新的决策变量和新的约束条件的变化
• 目标系数或右端项含有参数的变化

9、动态规划

• 阶段：k
• 状态：Sk
• 决策：Uk
• 策略：P1n(S1)=(U1(S1)，U2(S2)，…,Un(Sn)，)
• 状态转移方程：Sk+1=Tk(Sk,Uk)
• 指标函数和最优指标值：

分类：
- 决策过程：确定性、随机性
- 时间参量：离散、连续

最优化原理：如果整个策略最优，那么其任意子策略也必是最优的

10、欧拉回路的判定规则：

• 如果连接奇数桥的顶点多于两个，则不存在欧拉回路
• 如果只有两个点连接奇数桥，可以从这两个地方之一出发，找到欧拉回路
• 如果没有一个点连接奇数桥，则无论从哪里出发，都能找到欧拉回路

11、网络计划：
用网络分析的方法编制的计划，技术有：
- 关键路线法CPM
- 计划评审技术PERT

步骤：
- 绘制网络图
- 计算时间参数
- 确定关键路线及网络优化

12、存储论
相关模型：

• 不允许缺货，补充时间很短
• 不允许缺货，补充需一定时间
• 允许缺货，补充需一定时间
• 允许缺货，补充时间很短
• 价格有折扣的存储问题
• 需求是离散的随机变量
• 需求是连续的随机变量
• （s，S）型存储策略（连续型）
• （s，S）型存储策略（离散型）

13、排队论
三部分研究内容：

• 性态问题：排队系统概率规律性
• 最优化问题：静态最优和动态最优
• 排队系统的统计推断：

排队模型的符号表示：X/Y/Z/A/B/C

 - X：相继到达间隔时间的分布
 - Y：服务时间的分布
 - Z：并列的服务台数目
 - A：系统容量限制N
 - B：顾客源数目m
 - C：服务规则

常见分布：

• M：负指数分布