算法分析与设计

大家好，欢迎来到IT知识分享网。

算法与程序的区别：程序是算法用某种程序设计语言的具体实现，程序设计的实质就是构造解决问题的算法。算法+数据结构=程序，算法的结构和选择依赖于数据结构，所以数据结构是算法设计的基础。

在设计算法的时候，一定要先搞清楚算法要求处理什么问题、实现哪些功能、预期获得的结果等。

2.数学模型拟制

简单地说，数学模型就是对实际问题的一种数学表达，是数学理论与实际相结合的一门学科。

3.算法详细设计

算法详细设计指的是把算法具体化，即设计出算法的详细规格说明。

4.算法描述

根据前三部分的工作，采用描述工具将算法的具体过程描述下来。

5.算法思路的正确性验证

通过公式定理来验证算法所选择的设计策略及设计思路是否正确。

6.算法分析

算法分析是对算法的效率进行分析，主要是时间效率和空间效率。

7.算法的计算机实现和测试

采用某种程序设计语言来实现算法，并在计算机上进行运行和测试。

8.文档资料的编制

撰写算法的整个设计过程。

1.时间复杂性

时间复杂性是对算法运行时间长短的度量

2.空间复杂性

空间复杂性是对一个算法在运行过程中所占用存储空间大小的度量。

递归算法要分析空间复杂性

递归算法运行的过程分为两个阶段：递推和回归

2.当子程序返回时，才从栈顶 释放 它的 局部变量和形式参数的 存储空间。

3.子程序运行使用的是栈顶的那一份变量和形式参数。

4.全局变量、静态局部变量和动态分配的变量(new 分配的)，分配在”堆”里，不随程序的调用返回而变化。

以全排列问题的为例：

全排列算法的时间=复杂性为：O(n!)

无关系：集合结构

一对一：线性结构，例如：顺序表与链表，栈与队列

一对多：树型结构

多对多：图型结构

顺序表：把线性表的元素按逻辑次序依次存放在一组地址连续的存储单元，用这种方法存储的线性表简称为顺序表。

链表：链表是线性表的另一种存储方式，其特点是用一组任意的存储单元存储线性表的数据元素，它由一系列的节点组成，节点可以在运行时动态生成。主要有单链表、循环链表、双向链表。

队列：和栈相反，队列是一种先进先出的线性表，它只允许在表的一端插入 元素，而在另一端删除元素。队列的性质：允许删除的一端称为队头(Front)，允许插入的一端称为队尾(Rear)。

图：图是一种比线性表和树更为复杂的数据结构，可以用二元组表示，图中的数据元素通常被称为顶点(或节点)，数据元素之间的关系称为边，其形式定义为：G=(V，E)，集合V是顶点集，集合E是边集。

在线性表中，数据元素之间仅存在线性关系，即每个元素只有一个直接前驱和一个直接后继

在树型结构中，元素之间具有明显的层次关系，每个元素只能和上一层的一个元素相关，但也可以和下一层的多个元素相关。

在图型结构中元素之间的关系可以是任意的，一个图中任意两个元素都可以相关，即每个元素可以有多个前驱和多个后继。

当前会议的开始时间 >=(大于等于) 上一个会议结束的时间

(1)贪心选择性质:

贪心选择性质的证明即证明会场安排问题存在一个以贪心选择开始的最优解。

(2)最优子结构性质

进一步，在做了贪心选择买，即选择了会议1后，原问题就简化为对C中所有与会议1相容的会议进行会议安排的子问题。即若A是原问题的一个最优解，则A’=A-{1}是会议安排问题C1={i属于C|bi>=ei}的一个最优解。

证明(反证法)：假设A’不是会场安排问题C1的一个最优解。设A1是会场安排问题C1的一个最优解，那么|A1|>|A’|。令A2=A1U{1}，由于A1中的会议的开始时间均大于等于e1，故A2是会议安排问题C的一个解。又因为|A2=A1U{1}|>|A’U{1}=A|,所以A不是会场安排问题C的最优解。这与A是原问题的最优解矛盾，所以A’是会场安排问题C的一个最优解。

哈夫曼树

哈夫曼编码

最小生成树其实是一种可以看作是树的结构，而最小生成树的结构来源于图，通过这个图我们使用某种算法形成最小生成树的算法就可以叫做最小生成树算法，具体实现上有两种算法，分别为Prim算法和Kruskal算法

按Prim算法对无向连通带权图构造一棵最小生成树

通常分治法的求解过程都要遵循两大步骤：分解和治理

(1)二分查找算法实现的非递归形式

0—1背包问题

2.访问结点v0的第一个邻接点，以这个邻接点vt作为一个新节点，访问vt所有邻接点。直到以vt出发的所有节点都被访问到，回溯到v0的下一个未被访问过的邻接点，以这个邻结点为新节点，重复上述步骤。直到图中所有与v0相通的所有节点都被访问到。

3.若此时图中仍有未被访问的结点，则另选图中的一个未被访问的顶点作为起始点。重复深度优先搜索过程，直到图中的所有节点均被访问过。

给定一个无向图G(V,E)，给出深度优先搜索该图的一个搜索序列

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-YymXWxGn-83)(C:%5CUsers%5C%E6%88%B4%E5%B0%94%5CDesktop%5C%E7%AE%97%E6%B3%95%E8%AE%BE%E8%AE%A1%5C%E6%B7%B1%E5%BA%A6%E4%BC%98%E5%85%88%E6%90%9C%E7%B4%A2.png)]

2.依次访问v0的各个未被访问的邻接点；

3.依次从上述邻接点出发，访问它们的各个未被访问的邻接点。

4.若此时图中仍有未被访问的结点，则另选图中的一个未被访问的顶点作为起始点。重复广度优先搜索过程，直到图中的所有节点均被访问过。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-O66adgfV-85)(C:%5CUsers%5C%E6%88%B4%E5%B0%94%5CDesktop%5C%E7%AE%97%E6%B3%95%E8%AE%BE%E8%AE%A1%5C%E5%B9%BF%E5%BA%A6%E4%BC%98%E5%85%88%E6%90%9C%E7%B4%A2.png)]

数值随机化算法

P类问题是NP问题的子集，NPC(NP完全)问题是NP问题的子集

如果一个问题可以找到一个能在多项式的时间里解决它的算法，那么这个问题就属于P问题。

NP问题是指可以在多项式的时间里验证一个解的问题

分治法(2)：二分查找、快速排序