8.1 算法设计与分析的基本概念
8.1.1 算法
算法：对特定问题求解步骤的一种描述，具有有穷性、确定性、可行性、输入和输出
8.1.2 算法设计
算法设计技术：分治法、动态规划法、贪心法、回溯法、分支限界法、概率算法和近似算法
8.1.3 算法分析
算法分析的主要内容：选择解决问题的算法的过程，首先需要考虑算法的正确性、可靠性、简单性和易理解性，同时也考考虑算法的时间复杂度和空间复杂度要低；算法分析指对一个算法所需要的资源进行估算，这些资源包括内存、通信带宽、计算机硬件和时间等，所需要资源越多，该算法的复杂度越高
8.1.4 算法的表示
常用的算法表示方法：自然语言、流程图、程序设计语言和伪代码
8.2 算法分析基础
8.2.1 时间复杂度
算法的时间复杂度分析主要分析算法的运行时间，常用输入规模n为自变量的函数T(n)来表示算法的时间复杂度
时间复杂度分析有三种情况：最佳情况、最坏情况和平均情况
8.2.2 渐进符号
从极限角度看，只关心与运行时间如何随输入规模的无线增长而增长；用以下3种标准方法来简化算法的渐进分析：O记号、Ω记号、φ记号
8.2.3 递归式
递归算法分析方法：展开法、代换法、递归树法、主方法
8.3 分治法
8.3.1 递归的概念
递归：指子程序直接调用自己或通过一些列调用语句间接的调用自己，是一种描述问题和解决问题的常用方法
递归的两个基本要素：边界条件，即确定递归到何时终止；递归模式，即大问题如何分解为小问题
8.3.2 分治法的基本思想
分治法的基本思想：将一个难以解决的大问题分解成一些规模较小的相同问题，以便各个击破，分而治之；
分治法的递归步骤：分解（将原问题分解成一系列子问题）、求解（递归的求解各子问题）、合并（将子问题的解合并成原问题的解）
8.3.3 分治法的典型实例
归并排序：将待排序的元素分成大小大致相同的两个序列，分别对这两个子序列进行排序，最终将排序号的子序列合并为所要求的序列
8.4 动态规划法
8.4.1 动态规划法的基本思想
动态规划的基本思想：将待求解问题分解成若干的子问题，先求解子问题，然后冲这些子问题的解得到原问题的解，被分解得到的子问题往往不是独立的，不同子问题的数据常常只有多项式量级，如果能够保存已解决的子问题的答案，在需要时找出以求得的答案，这样就可以避免大量的重复计算，从而得到多项式时间的算法，为此，可以用一个表来记录已解决问题的答案，无论该子问题以后是否被用到，只要她被计算过，就将其结果填入表中，为可以利用它的问题服务；通常用于求解某种最优性质的问题
动态规划算法的步骤：找出最优解的性质，并刻画其结构特征；递归的定义最优解的值；以自底向上的方式计算出最优解；依据计算最优值时得到的信息，构造一个最优解
8.4.2 动态规划法的典型实例
0-1 背包问题、最长公共子序列
8.5 贪心法
8.5.1 贪心法的基本思想
贪心法：根据当前已有的信息作出选择，一旦选择就不改变，只能做到局部最优。
8.5.2 贪心法的典型实例
活动选择问题：指若干个具有竞争性活动要求互斥使用某一公共资源时如何选择最大的相容集合
背包问题
8.6 回溯法
回溯法：可以系统的搜索一个问题的所有解或任一解，它在包含问题的所有解的解空间树中，按照深度优先的策略，从根节点出发搜索空间树，判断节点是否肯定不包含问题的解，如果不包含则跳过该子树，逐层向其祖先节点回溯，否则进入子树，继续按照深度优先策略搜索，这种深度优先的方式系统的搜索问题的解的方法，适用于解一些组合数较大的问题
8.6.1 回溯法的算法框架
解空间：应用回溯法解问题，首先明确定义问题的解空间，其中至少包含问题的一个最优解；其后将解空间很好的组织起来，使得用回溯法能方便的搜索整个解空间
回溯法的步骤：针对所给的问题，定义问题的解空间；确定易于搜索的解空间结构；以深度优先的方式搜索解空间
限界函数：回溯法中解空间较大，为了有效搜索，需要进行剪枝，用限界函数来判断，限界函数的指导原则是尽可能多和尽可能早的杀掉不可能产生最优解的活结点
8.6.2 回溯法的典型实例
0-1背包问题、n皇后问题
8.7 分支限界法
分支界限法：类似于回溯法，即是一种在解空间上搜索问题解的算法，找出解空间中满足约束条件的一个解，或是在满足约束条件的解汇总找出使某一目标数值达到极大会极小的解，以广度优先或最小消耗优先的方式搜索
8.8 概率算法
概率算法：将随机性的选择加入算法，在算法执行某种步骤时，可以随机的选择下一步该如何进行，同时允许结果以最小的概率出现错误，并以此为代价，获得算法运行时间的大幅减少
特征：输入包括两部分，原问题的输入和一个供算法进行随机选择的随机数序列；运行过程中包括一处或多处随机选择，根据随机值来决定算法的运行路径；不能保证其结果一定正确，但能限定其 出错概率；不同运行过程中，对于相同的而输入可以有不同的输出
分类：数值概率算法、蒙特卡罗算法、拉斯维加斯算法和舍伍德算法
8.9 近似算法
近似算法：其基本思想是放弃求最优解，而用近似最优解代替最优解，以换取算法设计上的的简单和时间复杂度的降低；过程如下：虽然它可能找不到一个最优解，但它总会给待求解的问题提供一个解，为了具有实用性，近似算法必须能够给出算法所产生的解与最优解之间的差别或者比例的一个界限，他保证任意一个实例的近似最优解与最优解之间相差的程度，衡量其性能的指标为，算法的时间复杂度和解的近似程度
8.10 数据挖掘算法
数据挖掘的核心是算法，主要功能包括分类 、回归、关联规则和聚类
分类：一种有监督的学习过程，根据历史数据预测未来数据的模型；学习模型和应用模型；训练数据集、测试数据集合未知数据
决策树归纳：一种自顶向下的递归算法，使用一种属性选择度量为树的每个非叶子节点选择待分裂的属性
朴素贝叶斯算法和贝叶斯理念网络基于后验概率的贝叶斯公式进行分类
后向传播算法是使用梯度下降法的神经网络算法
支持向量机是一种用于线性和非线性数据的分类算法
聚类：一种非监督的学习过程；典型算法有，基于划分的算法，基于层次的算法、基于密度的算法、基于网络的算法和基于统计模型的算法
8.11 智能优化算法
智能优化算法：人工神经网络、混沌、遗传算法、进化规划、模拟退火、禁忌搜索及其混合优化策略
人工神经网络：是一个有向图为拓扑结构的动态系统，它通过对连续或断续的输入作状态响应二进行信息处理，发展了深度学习
遗传算法：在迭代过程中保持已有的结构，同时寻找更好的结构，建立在自然选择和群体遗传学基础上，通过自然选择、杂交和变异实现搜索的方法，基本过程是，首先采用某种编码方式将解空间映射到编码空间，每个编码对应问题的一个解，称为染色体或个体；其次通过随机的额方法产生初始解，在种群中根据适应值或某种竞争机制选择个体，再次使用各种遗传操作算子产生下一代，如此进化下去，知道满足期望的终止条件
模拟退火算法：一种求解全局优化算法，其基本思想来源于物理退火过程（加温过程、等温阶段、冷却阶段）；思想是，先将固体加热至溶化、再将其嘘嘘冷却、凝固成规整晶体
禁忌搜索算法：一种 模拟人类智力过程的全局搜索算法，是对局部邻域搜索的一种扩展；基本思想是，首选确定一个初始可行解x，x可以从一个启发式算法获得或在可行解集合X中任意选择；定义可行解x的邻域移动集S(x)，从邻域移动集中挑选一个能改进当前解x的移动，再从移动开始重新搜索，如果邻域移动集中智能接受比前一个可行解x更好的解，搜索就可能选入循环，为了避免循环和局部最优，构造一个短期循环记忆表来存储刚刚进行过的邻域移动，这些移动称为禁忌移动，对于当前的移动，在以后的移动内是禁止的以避免回到原始解，然后释放该移动
蚁群算法：依据信息正反馈原理和某种启发式算法的有机结合，优化过程包括选择、更新和协调，在选择过程中，信息素浓度越高的路径被选择的概率越大；在更新过程中，路径上的信息素随着蚂蚁的经过而增长，同时也随时间的推移而挥发；在协调过程中，蚂蚁通过信息素进行信息交流相互协作，在选择和更新过程中，较好的解通过路径上的信息素得到加强，从而引导下一代蚂蚁向最优邻域搜索使算法收敛，同时更新过程的信息素挥发又使得算法具有探索能力增加解的多样性，使算法不易陷入局部最优。
粒子群优化算法：将鸟群运动模型中的气息地类比成所求问题的解空间中可能解的位置，通过个体间的信息传递，引导整个群体向可能解的方向移动，增加发现最好解的可能，将鸟抽象为没有质量和形状的而粒子，在搜索空间中以一定的速度飞行，这个速度依据自身的飞行经验和同伴的飞行经验来动态调整，所有粒子都有一个被目标函数决定的适应值，并且知道自己到目前为止发现的最好为止和当前的位置，除此之外，每个粒子根据当前位置、当前速度、当前位置与自己最好位置之间的距离、当前位置与自身群体最好位置之间的距离来改变自己的当前位置。飞行经验是指该粒子本身所找到的最优位置，同伴飞行经验至该粒子周围的粒子目前找到的最优解；一整个种群为伴，算法成为全局粒子群算法，当同伴只取种群中的一部分时，则新城局部粒子群算法。
