算法随机技术

设计模式

算法设计技术

一、分类方法

实现方法
设计方法
其他的分类方法

1.1按照实现方法分类

1.递归或迭代

递归算法指的是算法反复调用自身。
迭代算法则更多的使用在循环结构中，有时采用栈和队列等数据结构。

2.过程式或声明式（非过程式）

声明式变成语言只需指明所需达到的目标，无需给出具体的细节，例如：sql语言。
过程式则需要指明想得到的期望结果的具体步骤，例如：c、php、perl等。

3.串行或并行或分布式

串行：一次执行一条计算机指令。
并行：利用计算机体系结构的特点，一次处理多条指令。
分布式：将并行算法分不到不容的机器上运行。

4.确定性或不确定性

确定性算法：基于预定义的过程来求解问题
不确定性算法：每一步通过某种启发式规则来推测最优解

5.精确或近似

近似算法往往用于求解np难问题。

1.2按设计方法分类

1.贪婪法

选取当前状态的最优决策，而不考虑对后续决策的影响。即由局部最优解获取全局最优解。

2.分支法

将原问题分解为众多子问题，且这些子问题与原问题类型相同但规模更小。

3.动态规划方法

与备忘录方法相结合。与分治法不同的是，分治法子问题之间不存在依赖关系，但是动态规划的子问题存在重叠的问题。通过备忘录的方法可以将许多问题的时间复杂度从指数级降为多项式级。

4.线性规划方法

使用不等式约束条件，最大化（或最小化）输入变量的线性函数。

5.归约（转化和求解）

将一复杂的问题转化和求解为一个一有渐进最优解的已知问题。

1.3其他分类方法

1.按照研究领域分类

每个领域有自己各自的问题并需要有效的算法。例如：查找算法、排序算法、归并算法、数值算法、图算法、字符串算法、集合算法、组合算法、机器算法、加密、并行算法、数据解压缩算法等。

2.按照复杂度分类

线性时间复杂度、指数数级时间、多项式时间

3.随机算法

随机选择、随机操作

4.分支定界、枚举和回溯

常见的几类算法技术

2.1贪婪法

1.贪婪的定义

将问题分为多个阶段。在每个阶段，选取当前状态下的最优决策。

2.贪婪算法的要素

• 贪婪选择性质

全局最优解可以通过寻找局部最优解获得。

• 最优子结构

原问题的最优解包含子问题的最优解。

3.贪婪算法的应用

赫夫曼编码压缩算法

• 问题托管地址 github地址