算法设计与分析

1 算法概述

算法三要素

操作、控制结构、数据结构

算法的基本特征

有穷性、确定性、可行性、算法有零个或多个输入、算法有一个或多个输出

设计算法考虑的指标

正确性、可读性、健壮性、高效率与低存储需求

2 算法分析基础

与算法执行时间相关的因素

1. 问题中数据存储的数据结构
2. 算法采用的数学模型
3. 算法设计的策略
4. 问题的规模
5. 实现算法的程序设计语言
6. 编译算法产生的机器代码质量
7. 计算机执行指令的速度

算法的空间复杂性

1. 输入数据所占空间
2. 算法本身所占空间
3. 辅助变量所占空间

算法的空间复杂度是指算法在执行过程中所占辅助存储空间的大小

3 算法基本工具和优化技巧

递归算法解题步骤

1. 分析问题、寻找递归关系
2. 设置边界、控制递归
3. 设计函数、确定参数

4 基本的算法策略

迭代算法求解问题

1. 确定迭代模型
2. 建立迭代关系式
3. 对迭代过程进行控制

适用分治法策略的问题

1. 能将这 \(n\) 个数据分解成 \(k\) 个不同子集合，且得到 \(k\) 个子集合是可以独立求解的子问题，其中 \(1 \le k\le n\)
2. 分解所得到的子问题与原问题具有相似的结构，便于利用递归或循环机制
3. 在求出这些子问题的解之后，就可以推解出原问题的解

动态规划算法求解具有的三个性质

1. 最优化原理：也是最优子结构，指一个问题的最优解包含其子问题的最优解，或一个最优化策略的子策略总是最优的
2. 无后向性：即某一阶段的状态一旦确定，就不受这个状态以后决策的影响
3. 子问题重叠：即子问题之间是不独立的，一个子问题在下一阶段决策中可能被多次使用到

设计动态规划算法步骤

1. 通常步骤：划分阶段、选择状态、确定决策并写出状态转移方程
2. 实际应用简化步骤：分析最优解的性质并刻画其结构特征、递推定义最优值、以自底向上的方式或自顶向下的记忆化方法计算最优值、根据计算最优值时得到的信息构造问题的最优解

5 图搜索算法

隐式图

隐式图是由问题的初始结点，为了求解或求证问题，根据题目的规则（一般是由题目的意思隐含给出的），也就是生成子结点的约束条件，逐步扩展结点，直到得到目标点为止的一个隐式的图

隐式图术语

1. 子集树：要求解的问题需要在 \(n\) 个元素的子集中进行搜索，其搜索空间树称作子集树
2. 排列树：要求解的问题需要在 \(n\) 个元素的排列中进行搜索时，解空间树称作排列树

割点

在一个无向连通图 \(G\) 中，当且仅当删去 \(G\) 中的顶点 \(v\) 及所有依附于 \(v\) 的边后，可将图分割成两个以上的连通分量，则称 \(v\) 为图 \(G\) 的割点

连通图 \(G\) 的割点判别

1. 从图的某一个顶点开始深度优先遍历图，得到深度优先生成树
2. 用开始遍历的顶点作为生成树的根
   1. 根顶点是图的割点的充要条件是，根至少有两个相邻结点
   2. 其余顶点 \(u\) 是图的割点的充要条件是：该顶点 \(u\) 至少有一个相邻结点 \(w\)，从该相邻结点出发不可能通过该相邻结点顶点 \(w\) 和该相邻结点 \(w\) 的子孙顶点，以及一条回边所组成的路径到达 \(u\) 的祖先（图中非生成树的边成为回边）
   3. 特别的，叶结点不是割点

回溯法和分支限界法的比较

方法	对解空间树的搜索方式	存储结点的常用数据结构	结点存储特性	主要应用
回溯法	深度优先搜索	堆栈	活结点的所有可行子结点被遍历后才被从栈中弹出	找出满足约束条件的所有解
分支限界法	广度优先或最小消耗优先搜索	队列、优先队列、堆	每个结点只有一次成为活结点的机会	找出满足约束条件的一个解或特定定义下的最优解