软件设计师（八）算法设计与分析

算法被公认为是计算机科学的基石算法理论研究的是算法的设计技术和分析技术。一、算法设计和分析的基本概念1、算法 Algorithm算法是对特定问题求解步骤的一种描述它是指令的有限序列其中每一条指令表示一个或多个操作。一个算法有5 个重要特性有穷性、确定性、可行性、输入、输出。2、算法设计算法设计技术也称算法设计策略。经常采用的算法设计技术主要有分治法、动态规划法、贪心法、回溯法、分支限界法、概率算法、近似算法。3、算法分析求解一个问题可能会有多种算法可以选择选择的主要标准首先是算法的正确性、可靠性、简单性和易理解性其次是算法的时间复杂度和空间复杂度要低这是算法分析技术的主要内容。算法分析是指对一个算法所需要的资源进行估算这些资源包括内存、通信带宽、计算机硬件和时间等所需要的资源越多该算法的复杂度就越高。复杂度分析主要包括时间复杂度和空间复杂度分析。4、算法的表示常用的表示算法的方法有自然语言、流程图、程序设计语言和伪代码等二、算法分析基础1、时间复杂度算法的时间复杂度分析主要是分析算法的运行时间 即算法执行所需要的基本操作数。将算法的时间复杂度分析分为 3 种情况。最佳情况使算法执行时间最少的输入。最坏情况使算法执行时间最多的输入。平均情况算法的平均运行时间下式给出了一般算法在平均情况下的复杂度分析。T ( n ) ∑ i 1 m p i ∗ t i T(n) \displaystyle\sum_{i1}^{m} p_i* t_iT(n)i1∑m​pi​∗ti​其中p i p_ipi​表示第i ii类输入发生的概率t i t_iti​表示第i ii类输入的执行时间输入分为m mm类.2、渐进符号a n 2 b n c an^2 bncan2bnc仅考虑n 2 n^2n2当输入规模大到只有与运行时间的增长量级有关时就是在研究算法的渐进效率。也就是说从极限角度看只关心算法运行时间如何随着输入规模的无限增长而增长。下面简单介绍 3 种常用的标准方法来简化算法的渐进分析:O OO记号用该记号给出一个算法运行时间的渐进上界。Ω \OmegaΩ记号用该记号给出一个算法运行时间的渐进下界。Θ \ThetaΘ记号用该记号给出一个算法运行时间的渐进上界和渐进下界即渐进紧致界10 n 2 4 n 2 10n^2 4n210n24n2仅考虑n 2 n^2n2O OO是算法运行时间的渐进上界比n 2 n^2n2大的满足Ω \OmegaΩ是算法运行时间的渐进下界比n 2 n^2n2小的满足Θ \ThetaΘ是算法运行时间的渐进紧致界n 2 n^2n2满足3、递归式从算法的结构上看算法可以分为非递归形式和递归形式。递归形式的方法1展开法将递归式中等式右边的项根据递归式进行替换称为展开。展开后的项被再次展开如此下去直到得到一个求和表达式得到结果2代换法这一名称来源于当归纳假设用较小值时用所猜测的值代替函数的解。在用代换法解递归式时需要 3 个步骤猜测解的形式用数学归纳法证明猜测的正确性求出使解真正有效的常数。3递归树法在递归树中每一个结点都代表递归函数调用集合中一个子问题的代价。将树中每一层内结点的代价相加得到一个每层代价的集合再将每层的代价相加得到递归式所有层的总代价。当用递归式表示分治算法的时间复杂度时递归树方法尤其有用。4主方法主方法也称为主定理给出了求解以下形式的递归式的快速方法三、分治法1、递归的概念递归是指子程序 (或函数)直接调用自己或通过一系列调用语句间接调用自己是一种描述问题和解决问题的常用方法。递归就是在运行的过程中调用自己递归有两个基本要素边界条件即确定递归到何时终止也称为递归出口递归模式即大问题是如何分解为小问题的也称为递归体。2、分治法的基本思想分治法的设计思想是将一个难以直接解决的大问题分解成一些规模较小的相同问题以便各个击破分而治之。分治法产生的子问题往往是原问题的较小模式这就为递归技术提供了方便。一般来说分治算法在每一层递归上都有 3 个步骤。分解。将原问题分解成一系列子问题。求解。递归地求解各子问题。若子问题足够小则直接求解.合并。将子问题的解合并成原问题的解。使用场景该问题的规模缩小到一定的程度就可以容易地解决该问题可以分解为若干个规模较小的相同问题利用该问题分解出的子问题的解可以合并为该问题的解该问题所分解出的各个子问题是相互独立的3、分治法的典型实例归并排序算法是成功应用分治法的一个完美的例子其基本思想是将待排序元素分成大小大致相同的两个子序列分别对这两个子序列进行排序最终将排好序的子序列合并为所要求的序列。归并排序算法完全依照上述分治算法的 3 个步骤进行。四、动态规划法1、动态规划法的基本思想基本思想也是将待求解问题分解成若干个子问题先求解子问题然后从这些子问题的解得到原问题的解。与分治法不同的是适合用动态规划法求解的问题经分解得到的子问题往往不是独立的。如果能够保存已解决的子问题的答案在需要时再找出已求得的答案这样就可以避免大量的重复计算。可以用一个表来记录所有已解决的子问题的答案。不管该子问题以后是否被用到只要它被计算过就将其结果填入表中。这就是动态规划法的基本思路。动态规划算法通常用于求解具有某种最优性质的问题。设计动态规划算法按照以下几个步骤进行找出最优解的性质并刻画其结构特征递归地定义最优解的值。以自底向上的方式计算出最优值根据计算最优值时得到的信息构造一个最优解对于一个给定的问题若其具有以下两个性质可以考虑用动态规划法来求解。最优子结构重叠子问题2、动态规划法的典型实例0-1背包问题最长公共子序列LCS五、贪心法1、贪心法的基本思想贪心法也经常用于解决最优化问题。贪心法并不是从整体最优考虑它所做出的选择只是在某种意义上的局部最优。举一个简单的贪心法例子平时购物找钱时为使找回的零钱的硬币数最少从最大面值的币种开始先尽量用大面值的币种当不足大面值币种的金额时才去考虑下一种较小面值的币种这就是在采用贪心法。如果只有面值分别为 1、5 和 11 单位的硬币而希望找回总额为 15 单位的硬币按贪心算法应找 1 个 11 单位面值的硬币和 4 个1 单位面值的硬币共找回5个硬币。但最优的解答应是 3 个 5 单位面值的硬币。采用贪心法的两个性质最优子结构贪心选择性质2、贪心法的典型实例多个活动占用教室资源[定理 8.3] 对于任意非空子问题S i j S_ijSi​j设a m a_mam​是S i j S_ijSi​j中具有最早结束时间的活动。那么(1) 活动a m a_mam​在S i j S_ijSi​j的某个最大兼容活动子集中。(2)子问题S i j S_ijSi​j为空所以选择a m a_mam​将使S m j S_mjSm​j为唯一可能非空的子问题六、回溯法回溯法是一种选优搜索法按选优条件向前搜索以达到目标。但当搜索到某步时发现原先选择并不优或达不到目标就退回一步重新选择。这种走不通就退回再走的技术就是回溯法。回溯法有“通用的解题法”之称可以系统地搜索一个问题的所有解或任一解是一个既带有系统性又带有跳跃性的搜索算法。过程它在包含问题的所有解的解空间树中按照深度优先的策略从根结点出发搜索解空间树。算法搜索至解空间树的任一结点时总是先判断该结点是否肯定不包含问题的解。如果肯定不包含则跳过对以该结点为根的子树的系统搜索逐层向其祖先结点回溯否则进入该子树继续按深度优先的策略进行搜索。回溯法在用来求问题的所有解时要回溯到根且根结点的所有子树都已被搜索遍才结束。而用来求问题的任一解时只要搜索到问题的一个解就可以结束。这种以深度优先的方式系统地搜索问题的解的方法称为回溯法它适用于解一些组合数较大的问题。1、回溯法的算法框架1问题的解空间在应用回溯法解问题时首先应明确定义问题的解空间。问题的解空间应至少包含问题的一个(最优) 解。定义了问题的解空间后还应将解空间很好地组织起来使得用回溯法能方便地搜索整个解空间。通常将解空间表示为树或图的形式。例如对于 m3 时的 0-1 背包问题其解空间用一棵完全二又树表示2回溯法的基本思想在确定了解空间的组织结构后回溯法从开始结点(根结点)出发以深度优先的方式搜索整个解空间。这个开始结点就成为一个活结点同时也成为当前的扩展结点。在当前的扩展结点处搜索向纵深方向移至一个新结点。这个新结点就成为一个新的活结点并成为当前扩展结点。如果在当前扩展结点处不能再向纵深方向移动则当前的扩展结点就成为死结点。此时应往回移动(回溯) 至最近的一个活结点处并使这个活结点成为当前的扩展结点。回溯法即以这种工作方式递归地在解空间中搜索直到找到所要求的解或解空间中已无活结点时为止。综上所述运用回溯法解题通常包含以下 3 个步骤针对所给问题定义问题的解空间。确定易于搜索的解空间结构。以深度优先的方式搜索解空间3回溯法的算法框架回溯法的算法框架有非递归和递归两种方式。4回溯法的限界函数问题的解空间往往很大为了有效地进行搜索需要在搜索的过程中对某些结点进行剪枝而对哪些结点进行剪枝需要设计限界函数来判断。因此限界函数的设计是回溯法的一个核心问题也是一个很难的问题。设计限界函数的通用的指导原则是尽可能多和尽可能早地“杀掉”不可能产生最优解的活结点。2、回溯法的典型实例七、分支限界法分支限界法类似于回溯法也是一种在问题的解空间树T TT上搜索问题解的算法。活节点队列当向下查询后本身从活节点队列中去除。回溯法分支限界法求解目标找出T中满足约束条件的所有解找出满足约束条件的最优解搜索方式深度优先广度优先或最小耗费优先搜索策略可以回溯每一个活结点只有一次机会成为扩展结点核心问题相同限界函数的设计限界函数的设计根据从活结点表中选择下一扩展结点的不同方式将分支限界法分为两种队列式FIFO先进先出分支限界法优先队列式分支限界法结点优先级优先队列是一种常用的数据结构通常用堆实现。对应于大顶堆和小顶堆存在最大优先队列和最小优先队列。以最大优先队列为例优先队列除了具有堆上的一些操作,如调整堆、构建堆之外还有获得优先队列的最大元素抽取出优先队列的最大元素向优先队列插入一个元素和增大优先队列中某个元素的值其中,除了获得优先队列的最大元素的时间复杂度为 O(1)之外,其他几个操作的时间复杂度均为二又树的高度,即O(lgn)。八、概率算法一般情况下概率算法具有以下基本特征。概率算法的输入包括两部分一部分是原问题的输入另一部分是一个供算法进行随机选择的随机数序列。概率算法在运行过程中包括一处或多处随机选择根据随机值来决定算法的运行路径。概率算法的结果不能保证一定是正确的但能限制其出错概率。概率算法在不同的运行过程中对于相同的输入实例可以有不同的结果因此对于相同的输入实例概率算法的执行时间可能不同。概率算法大致分为 4类数值概率算法数值概率算法常用于数值问题的求解。这类算法得到的往往是近似解且近似解的精度随计算时间的增加不断提高。蒙特卡罗 (Monte Carlo) 算法蒙特卡罗算法用于求问题的精确解。拉斯维加斯(LasVegas) 算法拉斯维加斯算法不会得到不正确的解。舍伍德 (Sherwood) 算法舍伍德算法总能求得问题的一个解且所求得的解总是正确的九、近似算法1、基本思想放弃求最优解而用近似最优解代替最优解以换取算法设计上的简化和时间复杂度的降低。2、过程虽然它可能找不到一个最优解但它总会给待求解的问题提供一个解。为了具有实用性近似算法必须能够给出算法所产生的解与最优解之间的差别或者比例的一个界限它保证任意一个实例的近似最优解与最优解之间相差的程度。显然这个差别越小近似算法越具有实用性。3、衡量近似算法性能的标准算法的时间复杂度近似算法的时间复杂度必须是多项式阶的这是近似算法的基本目标解的近似程度近似最优解的近似程度也是设计近似算法的重要目标。近似程度与近似算法本身、问题规模乃至不同的输入实例有关。十、数据挖掘算法1、数据挖掘概述数据挖掘利用机器学习方法对多种数据包括数据库数据、数据仓库数据、Web 数据等进行分析和挖掘。数据挖掘的核心是算法其主要功能包括分类、回归、关联规则和聚类等。2、分类分类是一种有监督的学习过程根据历史数据预测未来数据的模型。分类的数据对象属性分为两类一般属性和分类属性或者目标属性。对数据分类有两个步骤学习模型和应用模型在分类过程中涉及到的数据包括训练数据集、测试数据集和未知数据。学习模型是指基于训练数据集采用分类算法建立学习模型。应用模型是指应用测试数据集的数据到学习模型中根据输出来评估模型的好坏以及将未知数据输入到学习模型中预测数据的类型。存有多种分类算法决策树归纳朴素贝叶斯算法和贝叶斯信念网络后向传播BP支持向量机SVM可以用混淆矩阵来评估分类模型的质量.3、频繁模式和关联规则挖掘挖掘海量数据中的频繁模式和关联规则可以有效地指导企业发现交叉销售机会、进行决策分析和商务管理等。4、聚类聚类是一种无监督学习过程。根据数据的特征将相似的数据对象归为一类不相似的数据对象归到不同的类中这就是聚类每个聚类也称为簇。“物以类聚人以群分”就是聚类的典型描述。聚类的典型算法有基于划分的方法、基于层次的方法、基于密度的方法、基于网格的方法和基于统计模型的方法。说明算法基于划分的方法基于划分的方法将 n 个数据对象划分为 k 个不相交的集合每个集合称为一个簇典型的算法有 k-均值、k-中心点算法等基于层次的方法将数据对象集进行层次的分解。根据其是自底向上还是自顶向下分解可以分为凝聚的方法和分裂的方法。AGNES、DIANA基于密度的方法基于数据对象的邻域来进行聚类分析因此可以识别各种形状的簇以及一个数据对象可以属于多个不同的簇DBSCAN、OPTICS 和 DENCLUE基于网格的方法把对象空间量化为有限个单元形成一个网格结构。STING、CLIQUE基于统计模型的方法将数据对象集看作多个服从不同分布的数据集构成聚类的目的是识别出这些不同的分布的数据对象EM十一、智能优化算法优化技术是一种以数学为基础用于求解各种工程问题优化解的应用技术。包括人工神经网络、混沌、遗传算法、进化规划、模拟退火、禁忌搜索及其混合优化策略等。人工神经网络(ANN)是一个以有向图为拓扑结构的动态系统它通过对连续或断续的输入作状态响应而进行信息处理。模拟退火算法(SA)是一种求解全局优化算法。模拟退火算法的基本思想来源于物理退火过程、所谓物理退火过程包括 3 个阶段加温阶段、等温阶段、冷却阶段。禁忌搜索算法(TS)是模拟人类智力过程的一种全局搜索算法是对局部邻域搜索的一种扩展。