数据结构与算法基本概念

介绍了数据结构与算法两大方面。数据结构主要包括了线性结构和非线性结构。线性结构有线性表、栈、队列、串、数组、矩阵、广义表等。非线性结构有树、二叉树、森林、图等。数据结构的运算主要有查找和排序两大块。算法方面主要介绍了常规算法如分治法、动态规划法等，以及数据挖掘算法、智能优化算法等。

数据结构

• 数据结构
  • 概念
    • 定义
      • 是 数据元素的集合 及 元素间的相互关系 和 构造方法
      • 元素之间的 相互关系 是数据的 逻辑结构
      • 数据元素及元素之间 关系的存储 称为 存储结构(/物理结构)
    • 三要素
      • 逻辑结构
      • 存储结构
      • 运算
    • 根据逻辑结构分类
      • 线性结构
      • 非线性结构
        • 树结构
        • 图结构
  • 关于“线性结构”
    • 定义
      • 用于对客观世界中具有 单一前驱 和 后继 的数据关系进行描述
    • 特点
      • 数据元素之间呈现一种线性关系，即元素“一个接一个排列”
    • 分类
      • 线性表
        • 定义
          • 是 n(n≥0) 个元素(结构上不可分)的有限序列，通常表示为 (a1,a2,...,an)
        • 基本运算
          • 插入
          • 删除
          • 查找
        • 存储结构
          • 顺序存储
            • 用一组地址连续的存储单元依次存储线性表中的数据元素
            • 第 i 个元素 ai 的存储位置
              • LOC(ai) = LOC(a1) + (i-1) x L
                • LOC(a1) 表示第一个元素的存储位置。 L 表示每个数据元素所占空间的字节数。
          • 链式存储
            • 用通过指针链接起来的结点来存储数据元素
            • 结点结构
              • 数据域
                • 用于存储数据元素的值
              • 指针域
                • 用于存储当前元素的直接前驱或直接后继的位置信息
            • 分类
              • 线性链表（或单(向)链表）
                • 关于“有头链表”：实际应用中，为简化使用，还可以引入一个不存储数据元素的结点，称为头结点。
                • 结点中只有1个指针域
              • 双向链表
                • 每个结点有2个在指针
                  • 例： typedef struct node { dataType data; //数据域 struct node *prev, *next; //指针域 }Node, *LinkList;
              • 循环链表
                • 表尾结点的指针 指向 表头结点
              • 静态链表
                • 借助数组来描述线性表的链式存储结构
      • 栈
        • 定义
          • 只能通过一端来实现数据存储和检索（先进后出，Last In First Out，LIFO）
            • 操作的一端称为栈顶（Top）；另一端称为栈底（Bottom）。
        • 基本运算
          • 初始化栈 InitStack(S)
          • 判栈空 IsEmpty(S)
          • 入栈 Push(S, x)
          • 出栈 Pop(S)
          • 读栈顶元素 Top(S)
        • 存储结构
          • 顺序存储
          • 链式存储
        • 应用
          • 表达式求值
          • 括号匹配
          • 将递归过程转变为非递归过程的处理中
      • 队列
        • 定义
          • 只能在表的一端插入元素，在表的另一端删除元素（先进先出，First In First Out，FIFO）
            • 插入的一端称为队尾（Rear）； 删除的一端称为队头（Front）；
        • 基本运算
          • 初始化队列 InitQueue(Q)
          • 判队空 IsEmpty(Q)
          • 入队 EnQueue(Q, x)
          • 出队 DelQueue(Q)
          • 读队头元素 FrontQue(Q)
        • 存储结构
          • 顺序存储
            • 顺序队列
            • 循环队列
          • 链式存储
            • 链队列
      • 串
        • 定义
          • 仅由字符构成的有限序列。一般记为 S='a1a2...an'，S是串名，=后面的串是串值
        • 基本概念
          • 空串；空格串；串比较；串相等；子串；
        • 基本运算
          • 赋值操作 StrAssign(s, t)
          • 连接操作 Concat(s, t)
          • 串长 StrLength(s)
          • 串比较 StrCompare(s, t)
          • 求子串 SubString(s, start, len)
        • 存储结构
          • 顺序存储
          • 链式存储
        • 模式匹配
          • 定义
            • 子串的定位操作称为 串的模式匹配
            • 子串也称为 模式串
          • 匹配算法
            • 朴素的模式匹配算法
              • 布鲁特-福斯算法
            • 改进的模式匹配算法
              • KMP算法
      • 推广
        • 数组
          • 定义
            • 数组是定长线性表在维数上的扩展，即线性表中的元素又是一个线性表
            • N 维数组是一种“同构”的数据结构，其每个数据元素类型相同、结构一致
          • 特点
            • 数据元素数目固定
            • 数据元素具有相同的类型
            • 数据元素的下标关系具有上下界的约束，且下标有序
          • 基本运算
            • 给定一组下标，存取数据元素
            • 给定一组下标，修改数据元素
          • 存储结构
            • 顺序存储
        • 矩阵
          • 定义
            • 矩阵是一种数学对象，这里主要研究如何在节省存储空间的情况下 使矩阵的各种运算能高效地运行
          • 分类
            • 特殊矩阵
              • 值相同的元素或0元素在矩阵中的分布有一定的规律
              • 分类
                • 对称矩阵
                • 对角矩阵
                • 三角矩阵
            • 稀疏矩阵
              • 值相同的元素或0元素在矩阵中的分布没有规律
              • 存储
                • 使用三元组 (i, j, aij) 存储1个元素的 行号、列号、值
              • 存储结构
                • 顺序存储
                  • 三元组顺序表
                • 链式存储
                  • 十字链表
        • 广义表
          • 定义
            • 是由0个或多个 单元素或子表 组成的有限序列
            • 长度
              • 元素的个数
            • 深度
              • 广义表展开后所含的括号的最大层数
          • 基本运算
            • 插入
            • 删除
            • 查找
          • 存储结构
            • 链式存储
  • 关于“非线性结构”
    • 树
      • 定义
        • 一个数据元素可以有零到一个直接前驱元素，及两个或两个以上的直接后继元素
        • 树是 n(n≥0) 个结点的有限集合
        • 树的定义是递归的，有且只有1个称为“根”的结点，其余结点称为根结点的“子树”
      • 逻辑结构
        • 元素间有层次关系
          • 
      • 基本概念
        • 双亲
          • 孩子结点的根结点
        • 孩子
          • 结点的子树的根 称为该结点的孩子
        • 兄弟
          • 具有相同双亲的结点互为兄弟
        • 叶子结点
          • 终端结点，度为0
        • 内部结点
          • 非终端结点或分支结点，度不为0
        • 结点的度
          • 一个结点的子树的个数
        • 结点的层次
          • 根为第1层，根的孩子为第2层，以此类推
        • 树的高度
          • 一棵树的最大层数记为树的高度（或深度）
            • 高度：从下往上数 ↑； 深度：从上往下数 ↓；
        • 有序、无序树
          • 若树中结点的各子树是有序的，则为有序树，否则为无序数
      • 存储结构
        • 双亲表示法
        • 孩子表示法
        • 孩子兄弟表示法
          • 为实现 树、二叉树、森林 之间的转换提供了可能
      • 基本运算
        • 遍历
          • 方式
            • 先根遍历
              • 先访问树的根结点，然后依次先根遍历根的各棵子树
                • 等同于 对转换所得的二叉树进行先序遍历。
            • 后根遍历
              • 先依次后根遍历树根的各课子树，然后访问树根结点
                • 等同于 对转换所得的二叉树进行中序遍历。
      • 其他细分
        • 二叉树
          • 定义
            • 二叉树是 n(n≥0) 个结点的有限集合
            • 二叉树的定义是递归的。由 1个根结点 及 2棵不相交的且分别称为左、右子树的二叉树 所组成
              • 
          • 主要性质
            • 二叉树第 i 层(i≥1)上最多有 2的(i-1)次方 个结点
            • 高度为 k(k≥1) 的二叉树最多有 2的k次方-1 个结点
          • 分类
            • 满二叉树
              • 
              • 各层没有空结点
            • 完全二叉树
              • 
              • 除了最后1层，其余各层都是满的
              • 最后1层的结点序从左到右放置，不能留空
            • 非完全二叉树
              • 
          • 存储结构
            • 顺序存储
              • 按适当顺序 在一组地址连续的存储单元中 存储二叉树中的结点
                • 
              • 设一棵完全二叉树，根结点序号为1，若有编号为 i 的结点，则
                • 若 i=1，则该结点为根结点，无双亲
                • 若 i>1，则该结点的双亲结点为 ⌊ i/2 ⌋
                • 若 2i≤n，则该结点的左孩子为 2i，否则无左孩子
                • 若 2i+1≤n，则该结点的右孩子为 2i+1，否则无右孩子
            • 链式存储
              • 存储
                • 结点中包含数据元素、双亲、左子树的根、右子树的根
                • 可用 二叉链表 或 三叉链表 存储
                  • 
          • 基本运算
            • 遍历
              • 定义
                • 按某种策略访问树中的每个结点，且仅访问一次的过程
                • 遍历二叉树的过程实质是按一定的规则将树中的结点排成一个线性序列的过程
              • 方式
                • （1）按先遍历左子树后遍历右子树的约定，根据访问根结点位置的不同
                  • 借助 栈。
                  • 可得到3种方式
                    • 先序遍历
                      • 遍历路线从根结点出发，逆时针沿着二叉树的外缘移动，对每个结点均途径三次。 若第1次经过结点时访问，则为先序遍历。
                    • 中序遍历
                      • 若第2次经过结点时访问，则为中序遍历。
                    • 后序遍历
                      • 若第3次经过结点时访问，则为后序遍历。
                • （2）层序遍历（自上而下、自左至右 逐层访问）
                  • 借助 队列。
          • 其他细分
            • 线索二叉树
              • 定义
                • 在二叉树结点的存储信息中，增加直接前驱和直接后续信息
                  • typedef struct tbtnode { dataType data; //数据域 struct tbtnode *lchild, *rchild; //指针域 char ltag, rtag; //标志域 0:指针指向孩子结点 1:指针指向前驱/后继结点 }TBTNode;
            • 最优二叉树
              • 定义
                • 又称为哈夫曼树，是一类带权路径长度 最短的树
              • 基本概念
                • 路径
                  • 从树中一个结点到另一个结点之间的通路
                • 路径长度
                  • 路径上的分支数目
                • 结点的带权路径长度
                  • 从该结点到树根之间的路径长度 与 该结点权值的 乘积
                • 树的路径长度
                  • 从树根到每一个叶子之间的路径长度之和
                • 树的带权路径长度
                  • 树中所有叶子结点的带权路径长度之和
              • 构造算法
                • （1）在二叉树集合中，选取 两棵权值最小的树 作为 左、右子树(两者中权值较小的放左子树) 构造一棵新的二叉树，左、右子树根结点的权值之和 作为 新的二叉树的根结点的权值； （2）从集合中删除这两棵树，加入新构造的树； 重复上述步骤；
              • 应用
                • 哈夫曼编码
                  • 说明
                    • 等长编码：每个字符的二进制码长度相同； 不等长编码（也称前缀码）：每个字符的二进制码长度不相同； 若要设计不等长编码，需满足条件：任一字符的编码都不是另一个字符的编码的前缀。 哈夫曼编码就是一种不等长编码。
        • 森林
          • 定义
            • 树和森林相互递归定义
          • 基本运算
            • 遍历
              • 方式
                • 先序遍历
                  • 先访问森林中第1棵树的根结点，然后先序遍历第1棵树根结点的子树森林。最后先序遍历剩余树所构成的森林
                • 中序遍历
                  • 先中序遍历森林中第1棵树的子树森林，然后访问第1棵树的根结点。最后中序遍历剩余树所构成的森林
          • 树、二叉树、森林之间的相互转换
            • 树 转换为 二叉树
              • 步骤
                • 
                • （1）加线：兄弟结点间加连线
                • （2）去线：结点只保留与第1个结点的连线
                • （3）层次调整(旋转)：以树根结点为轴心，旋转使第1个孩子结点位于左孩子位置，兄弟结点位于右孩子位置
            • 森林 转换为 二叉树
              • 步骤
                • 
                • （1）森林的每棵树分别转为二叉树
                • （2）第1棵二叉树不动，依次把后一棵二叉树的根结点作为前一棵二叉树的根结点的右孩子并连线
            • 二叉树 转换为 树
              • 步骤
                • （1）加线：某结点左孩子的n个右孩子结点，都作为此结点的孩子结点并连线
                • （2）去线：删去原二叉树中所有结点与其右孩子结点的连线
                • （3）层次调整（旋转）
            • 二叉树 转换为 森林
              • 步骤
                • 
                • （1）分离出二叉树
                  • 从根结点开始，删除所有右孩子连线
                • （2）二叉树转为树
    • 图
      • 定义
        • 一个结点的前驱结点和后继结点数目没有限制
        • 图 G(Graph) 是由集合 V(Vertex) 和 E(Edge) 构成的二元组，记作 G=(V, E)
          • 例： G1 = (V1, E1); V1 = {a, b, c, d}; E1 = {(a,b), (a,c), (a,d), (b,d), (c,d)}; 
          • V是 顶点(数据元素) 的非空有限集合
          • E是 边(数据元素之间的关系) 的有限集合
      • 基本概念
        • 顶点的度
          • 度
            • 关联于该顶点的 边的数目，是入度和出度之和，记作 D(v)
          • 入度
            • 是以该顶点为终点的 有向边的数目，记作ID(v)
          • 出度
            • 是以该顶点为起点的 有向边的数目，记作OD(v)
        • 路径
          • 从顶点 vp 到顶点 vq 的顶点序列
          • 路径长度
            • 路径上边的数目
          • 回路 或 环
            • 第1个顶点和最后1个顶点相同的路径
              • 若该路径其余顶点均不相同，则称其为 简单路径
        • 子图
        • 连通图 与 连通分量
          • 连通图
            • 任意两个顶点都是连通的无向图
          • 连通分量
            • 该图的极大连通子图
              • 图中不被其他子图包含的连通子图。一般就是图本身。
        • 强连通图 与 强连通分量
          • 强连通图
            • 任意两个顶点都是连通的有向图
          • 强连通分量
            • 该图的极大连通子图
              • 图中不被其他子图包含的连通子图。一般就是图本身。
        • 网
          • 边带权值的图
        • 有向树
          • 有1个顶点的入度为0，其余顶点的入度均为1的有向图
        • 生成树
          • 
          • 该图的极小连通子图（，没有回路的）
          • 图的生成树是不唯一的
            • 从不同的顶点出发，选择不同的存储方式，用不同的求解方法，可以得到不同的生成树。 对于非连通图而言，每个连通分量中的顶点集和遍历时走过的边集一起构成若干棵生成树，把它们称为非连通图的生成树森林。 按深度和广度优先搜索进行遍历将得到不同的生成树，分别称为深度优先生成树和广度优先生成树。 
        • 单源点最短路径
      • 分类
        • 有向图
          • 每条边都有方向
          • 顶点间的关系用 <vi, vj> 表示
            • 它表示 vi 到 vj 有一条有向边（也称为 弧）
            • vi 是有向边的起点，称为弧尾
            • vj 是有向边的终点，称为弧头
          • 其他细分
            • 有向无环图
              • Directed Acycline Graph，DAG
              • 不存在回路的有向图
        • 无向图
          • 每条边都没有方向
          • 顶点间的关系用 (vi, vj) 表示
        • 完全图
          • 每个顶点与其他顶点间都有边
          • 分类
            • 有向完全图
            • 无向完全图
      • 存储结构
        • 邻接矩阵表示法
        • 邻接链表表示法
      • 基本运算
        • 遍历
          • 定义
            • 图的遍历是指从某个顶点出发，沿着某条搜索路径对图中的所有顶点进行访问且只访问一次的过程
          • 方式
            • 为了避免对顶点的重复访问，在图的遍历过程中必须记下每个已访问过的顶点。
            • 深度优先搜索（Depth First Search，DFS）
              • 借助 栈。
              • 尽可能先对纵深方向搜索访问
            • 广度优先搜索（Breadth First Search，BFS）
              • 借助 队列。
              • 尽可能先对横向方向搜索访问
      • 关于“最小生成树”
        • 定义
          • 对连通网来说，边是带权值的，生成树的各边也带权值
          • 最小生成树 即 权值最小的生成树
            • 求解最小生成树有许多实际的应用。
        • 基本概念
          • 生成树的权
            • 生成树各边的权值总和
        • 常用最小生成树求解算法
          • 普里姆（Prim）算法
          • 克鲁斯卡尔（Kruskal）算法
      • 关于“单源点最短路径”
        • 定义
          • 是指给定 带权有向图G 和 源点 v0，求从 v0 到 G 中其余各顶点的 最短路径
        • 常用求解算法
          • 迪杰斯特拉（Dijkstra）算法
          • 弗洛伊德（Floyd）算法
      • 应用
        • AOV网（Activity On Vertex network）
          • 定义
            • 以顶点表示活动，用有向边表示活动之间的优先关系 的有向图
            • AOV网中不应出现 有向环
          • 检查 AOV网 是否存在回路
            • 方法
              • 对有向图构造其顶点的 拓扑有序序列，若图中所有的顶点都在它的拓扑有序序列中，则不存在回路
              • 步骤
                • 
                • （1）在网中选一个入度为0的顶点，并输出它
                • （2）从网中删除该顶点及关联的所有弧
                • （3）重复上述两步，直到网中不存在入度为0的顶点
                • （4）结果
                  • 若所有顶点已输出，此时整个拓扑排序完成，说明不存在回路
                  • 若尚有未输出的顶点，剩余顶点均有前驱顶点，此时拓扑排序无法继续进行，说明存在回路
        • AOE网（Activity On Edge network）
          • 定义
            • 以顶点表示事件，用有向边表示活动，以边上的权值表示该活动持续的时间 的有向图
            • 整个工程所需的时间 是从开始顶点到结束顶点的 最长路径的长度
          • 基本概念
            • 顶点表示的事件 是某些活动已完成、某些活动可以动工的标志
            • 源点
              • 入度为0的开始顶点
            • 汇点
              • 出度为0的结束顶点
            • 关键路径
              • 从源点到汇点的最长的路径
                • 关键路径上的所有活动均是 关键活动
            • 顶点事件的时间
              • 顶点事件的最早发生时间 ve(j)
              • 顶点事件的最晚发生时间 vl(i)
• 数据结构的运算
  • 查找
    • 基本概念
      • 说明
        • 查找是一种常用的基本运算
      • 查找表
        • 是指由同一类型的数据元素（或记录）构成的集合
      • 关键字
        • 是数据元素（或记录）的 某个数据项的值
          • 用来识别（标识）这个数据元素
      • 主关键字
        • 是指能唯一标识一个数据元素的关键字
      • 次关键字
        • 是指能标识多个数据元素的关键字
      • 查找的结果
        • 查找成功
        • 查找失败
      • 平均查找长度
        • 查找过程需和给定关键字值进行比较的次数的 期望值
    • 查找表的基本操作
      • 静态查找表
        • 查询 某个数据元素是否在查找表中
        • 检索 某个数据元素的各种属性
      • 动态查找表
        • 插入 一个数据元素
        • 删除 一个数据元素
    • 关于“静态查找表”
      • 查找方法
        • 分类
          • 顺序查找
          • 折半查找
            • 过程分析
              • 查找的过程可以用一棵二叉树描述
              • 折半查找判定(二叉)树的构造方法
                • （1）以当前查找区间的中间位置序号作为根
                • （2）左半个子表和右半个子表中的记录序号分别作为 根的左子树和右子树上的结点
          • 分块查找
    • 关于“动态查找表”
      • 特点
        • 表结构本身是在查找过程中动态生成的
      • 表结构分类
        • 二叉排序树
          • 定义
            • 又称二叉查找树
              • 它或是一棵空树
              • 或是具有以下性质的二叉树
                • 若左子树非空，则左子树所有结点的值均小于根结点的值
                • 若右子树非空，则右子树所有结点的值均大于根结点的值
                • 左、右子树本身是二叉排序树
        • 平衡二叉树
          • 定义
            • 又称 AVL 树
              • 它或是一棵空树
              • 或是具有以下性质的二叉树
                • 左、右子树的高度之差的绝对值不超过1
                • 左、右子树本身是平衡二叉树
          • 操作
            • 插入
              • LL 型单向右旋平衡处理
              • RR 型单向左旋平衡处理
              • LR 型先左后右双向旋转平衡处理
              • RL 型先右后左双向旋转平衡处理
        • m 阶 的 B_树
          • 定义
            • 它或是一棵空树
            • 或是具有以下性质的 m 树
              • 树中每个结点最多有 m 棵子树
              • ...
        • 红黑树
    • 哈希表（或 散列表）
      • 定义
        • 通过计算 一个以记录的关键字 为自变量的函数（称为哈希函数） 来得到该记录的 存储地址
        • 即 根据设定的哈希函数 H(key) 和处理冲突的方法，将一组关键字映射到一个有限的连续的地址集（区间）上，并以关键字在地址集中的“像”作为记录在表中的存储位置
          • 这一映射过程称为 哈希造表 或 散列
          • 所得的存储位置称为 哈希地址 或 散列地址
      • 基本概念
        • 关于哈希冲突
          • 对于某个哈希函数 H 和这两个关键字 K1 和 K2，如果 K1≠K2，而 H(K1)=H(K2)，则称为冲突
            • 具有相同哈希函数值的关键字对该哈希函数来说称为 同义词
          • 一般来说
            • 冲突只能尽可能减少而不能完全避免，因为哈希函数是从关键字集合到地址集合的映像
            • 哈希函数是一个压缩映像，冲突是不可避免的
      • 主要考虑的问题
        • 如何构造哈希函数
          • 常用方法
            • 直接定址法
            • 数字分析法
            • 平方取中法
            • 折叠法
            • 随机数法
            • 除留余数法
          • 应解决好的问题
            • 哈希函数应是一个压缩映像函数，它应具有较大的压缩性，以节省存储空间
            • 哈希函数应具有较好的散列性，尽可能均匀地把关键字映射到存储区的各个存储单元
        • 如何解决冲突
          • 常用方法
            • 开放定址法
            • 链地址法
            • 再哈希法
            • 建立一个公共溢出区
      • 基本运算
        • 查找
          • 概念
            • 用存入元素时相同的哈希函数和冲突处理方法计算得到待查记录的存储地址
            • 平均查找长度
              • 取决于
                • 哈希函数
                • 处理冲突的方法
                • 哈希表的装填因子
            • 关于“哈希表的装填因子”
              • 定义
                • α= 表中装入的记录数 / 哈希表的长度
  • 排序
    • 基本概念
      • 定义
        • 假设含n个记录的文件内容为{R1,R2,…,R}，相应的关键字为{k1,k2,…,kn}。经过排序确定一种排列{Rj1,Rj2,…,Rjn}， 使得它们的关键字满足以下递增（或递减）关系：kj1≤kj2≤…≤kjn(或kj1≥kj2≥…≥kjn）。
      • 排序方法的稳定性
        • 稳定的排序方法
          • 关键字相同的记录Ri、Rj，Ri 领先于 Rj。排序后，Ri、Rj 的次序仍不变
        • 不稳定的排序方法
          • 关键字相同的记录Ri、Rj，Ri 领先于 Rj。排序后，Ri、Rj 的次序可能改变
    • 基本操作
      • （1）比较关键字的大小；
      • （2）根据存储方式的不同，可能需要移动记录的位置；
    • 分类
      • 内部排序
        • 待排序记录全部存放在内存中进行排序的过程。
        • 简单排序
          • 直接插入排序
          • 冒泡排序
          • 简单选择排序
        • 希尔排序
        • 堆排序
        • 快速排序
        • 归并排序
          • 两路归并排序
            • 所谓“归并”，是将两个或两个以上的有序文件合并成为一个新的有序文件。 归并排序的一种实现方法是把一个有n个记录的无序文件看成是由n个长度为1的有序子文件组成的文件，然后进行两两归并，得到 ⌈n/2⌉ 个长度为2或1的有序文件，再两两归并。如此重复，直到最后形成包含n个记录的有序文件为止。 这种反复将两个有序文件归并成一个有序文件的排序方法称为两路归并排序。
        • 基数排序
      • 外部排序
        • 指待排序记录的数量很大，以至于内存不能容纳全部记录，在排序过程中尚需对外存进行访问的排序过程。 外部排序就是对大型文件的排序，待排序的记录存放在外存。在排序的过程中，内存只存储文件的一部分记录，整个排序过程需要进行多次内外存间的数据交换。
        • 基本方法
          • 外部排序就是对大型文件的排序，待排序的记录存放在外存。在排序的过程中，内存只存储文件的一部分记录，整个排序过程需要进行多次内外存间的数据交换。 常用的外部排序方法是归并排序，一般分为两个阶段： 在第一阶段，把文件中的记录分段读入内存，利用某种内部排序方法对记录段进行排序并输出到外存的另一个文件中，在新文件中形成许多有序的记录段，称为归并段： 在第二阶段，对第一阶段形成的归并段用某种归并方法进行一趟趟地归并，使文件的有序段逐渐加长，直到将整个文件归并为一个有序段时为止。
        • 方法分类
          • k 路平衡归并

算法

• 基本概念
  • 算法理论研究
    • 算法的设计技术(/策略)
      • 回答问题：“对特定的问题，如何提出一个算法来求解？”
    • 算法的分析技术
      • 回答问题：“该算法是否足够好？”
  • 定义
    • 算法（Algorithm）是对特定问题求解步骤的一种描述，它是指令的有限序列。其中每一条指令表示一个或多个操作。
  • 算法的5个重要特性
    • 有穷性
    • 确定性
    • 可行性
    • 输入
    • 输出
  • 关于“算法设计”
    • 主要技术
      • 分治法、动态规划法、贪心法、回溯法、分支限界法、概率算法、近似算法
  • 关于“算法分析”
    • 一些分析标准
      • 算法的正确性、可靠性、简单性、易理解性
      • 算法的时间复杂度 和 空间复杂度
  • 算法的表示
    • 自然语言
    • 流程图
    • 程序设计语言
    • 伪代码
  • 关于“时间复杂度”
    • 分析
      • 定义
        • 主要是分析算法的运行时间，即算法执行所需要的基本操作数
      • 方法
        • 建立以输入规模n为自变量的函数T(n)来表示算法的时间复杂度
          • 根据不同的输入，有3种情况
            • 最佳情况
            • 最坏情况
            • 平均情况
        • 渐进符号
          • 是对上述T(n)方法的进一步抽象，仅考虑运行时间的增长率（或称为 增长量级）
            • 当输入规模大到只有与运行时间的增长量级有关时，就是在研究算法的渐进效率。也就是说，从极限角度看，只关心算法运行时间如何随着输入规模的无限增长而增长。
            • 分析方法
              • O记号
                • 渐进上界 分析
                  • 例：
                    • 多项式级复杂度：O(1)、O(log(n))、O(n2次方)等； 非多项式级复杂度：O(an次方)、O(n!)等（非常耗时）；
              • Ω记号
                • 渐进下届 分析
              • Θ记号
                • 渐进上界和渐进下界 分析，即 渐进紧致界 分析
  • 算法结构
    • 一般可分为
      • 非递归形式
      • 递归形式
        • 主要的时间复杂度分析方法
          • 展开法
          • 代换法
          • 递归树法
          • 主方法
• 常规算法
  • 分治法
    • 基本思想
      • 将一个难以直接解决的大问题分解成一些规模较小的相同问题，以便各个击破，分而治之
      • 递归
        • 分治与递归就像一对孪生兄弟。
        • 是指子程序直接调用自己 或 通过一系列调用语句间接调用自己
        • 基本要素
          • 边界条件
            • 即确定递归到何时终止，也称为递归出口；
          • 递归模式
            • 即大问题是如何分解为小问题的，也称为递归体；
    • 主要步骤
      • 分治算法在每一层递归上的步骤
        • （1）分解
        • （2）求解
        • （3）合并
    • 应用
      • 归并排序
      • 最大字段和问题
  • 动态规划法
    • 基本思想
      • 将一个难以直接解决的大问题分解成一些规模较小的相同问题，各个击破。与分治法不同的是，子问题往往不是独立的
      • 在表中保存已解决子问题的答案，在需要时再找出
    • 主要步骤
      • （1）找出最优解的性质
      • （2）递归定义最优解的值
      • （3）以自底向上的方式计算出最优值
      • （4）根据计算最优值时得到的信息，构造一个最优解
    • 应用
      • 0-1 背包问题
      • 最长公共子序列（LCS）
  • 贪心法
    • 基本思想
      • 策略上是仅根据当前已有的信息做出选择，获取局部(/近似)最优解
    • 算法形式
      • 递归贪心算法
      • 迭代贪心算法
    • 应用
      • 活动选择问题
      • 背包问题
  • 回溯法
    • 基本思想
      • 在确定了解空间的组织结构后，回溯法从开始结点（根结点）出发，以深度优先的方式搜索整个解空间。直到找到所要求的解或解空间中已无活动结点时为止
      • 求解目标是找出满足约束条件的所有解
      • 解空间
        • 至少应包含问题的一个（最优）解
        • 一般表示为树或图的形式
      • 限界函数
        • 由于解空间往往很大，为了有效地进行搜索，需要在搜索的过程中对某些结点进行剪枝。设计限界函数用于剪枝判断（尽可能早、多地剪枝）
    • 主要步骤
      • （1）定义问题的解空间
      • （2）确定易于搜索的解空间结构
      • （3）以深度优先的方式搜索解空间
    • 算分框架
      • 递归方式
      • 非递归方式
    • 应用
      • 0-1背包问题
      • n 皇后问题
  • 分支限界法
    • 基本思想
      • 类似回溯法，也是一种在问题的解空间树 T 上搜索问题解的算法
      • 以广度优先 或 以最小耗费优先的方式搜索解空间
      • 求解目标是找出满足约束条件的一个(最优)解
      • 限界函数
    • 根据从活动点表中选择下一扩展结点的不同方式分类
      • 队列式（FIFO，先进先出）分支限界法
      • 优先队列式分支限界法
  • 概率算法
    • 基本思想
      • 在算法执行某些步骤时，可以随机地选择下一步该如何进行，同时允许结果以较小的概率出现错误，并以此为代价，获得算法运行时间的大幅度减少
    • 分类
      • 数值概率算法
      • 蒙特卡罗（Monte Carlo）算法
      • 拉斯维加斯（Las Vegas）算法
      • 舍伍德（Sherwood）算法
  • 近似算法
    • 基本思想
      • 放弃求最优解，而用近似最优解代替最优解，以换取算法设计上的简化和时间复杂度的降低
    • 衡量性能的标准
      • 算法的时间复杂度
      • 解的近似程度
• 数据挖掘算法
  • 数据挖掘
    • 基本概念
      • 是一门交叉学科，利用机器学习方法对多种数据（数据库数据、数据仓库数据、Web数据等）进行分析和挖掘
    • 核心
      • 是算法
    • 主要功能
      • 分类
      • 回归
      • 关联规则
      • 聚类
• 智能优化算法
  • 概述
    • 优化技术
      • 是一种以数学为基础，用于求解各种工程问题优化解的应用技术
      • 在优化领域，由于这些算法构造的直观性与自然机理，常称为“智能优化算法”或“现代启发式算法”
  • 已有的优化算法
    • 人工神经网络（ANN）
      • 原理
        • 一个以有向图为拓扑结构的动态系统，它通过对连续或断续的输入状态响应而进行信息处理
      • 分类
        • 前馈网络和反馈网络
          • 分类
            • 基于 BP 算法的多层前向神经网络
        • 深度机器学习
          • 深度置信网（DBNs）
            • 无监督机器学习模型
          • 卷积神经网络（CNNs）
            • 有监督机器学习模型
    • 遗传算法
    • 模拟退火算法（SA）
    • 禁忌搜索算法（TS）
    • 蚁群算法
    • 粒子群优化算法（PSO）