《算法设计与问题求解》PPT第一章 算法基础.pptx

1、算法概念算法描述算法主要类别及典型问题算法复杂性分析目录标准模板库（STL）1 1算法概念算法概念 什么是算法什么是算法 算法的特征算法的特征算法（算法（AlgorithmAlgorithm）是指解题方案的准确而完整的描述，通过一系列解决问题的清晰指令来描述问题的程序化解决方案。对于符合一定规范的输入，能够在有限时间内获得所要求的输出。算法中的指令描述的是一个计算，当其运行时能从一个初始状态和（可能为空的）初始输入开始，经过一系列有限而清晰定义的状态，最终产生输出并停止于一个终态。一个状态到另一个状态的转移不一定是确定的。1 算法概念算法的有穷性是指算法必须能在执行有限个步骤之后终止1 算法概

2、念有穷性有穷性算法的每一步骤必须有确切的定义确切性确切性有0个或多个输入，0个输入是指算法本身定出了初始条件输入项输入项有一个或多个输出，以反映对输入数据加工后的结果输出项输出项算法中执行的任何计算步骤都是可以被分解为基本的可执行的操作步骤，即每个计算步骤都可以在有限时间内完成（也称之为有效性）可行性可行性2 2算法描述算法描述 伪代码伪代码算法描述算法描述是指对算法用一种方式进行详细的描述，可以使用自然语言、伪代码（Pseudocode），也可使用程序流程图，但描述的结果必须满足算法的五个特征。伪代码伪代码是一种类似于英语结构的语言，用于描述模块功能，可以将整个算法运行过程的结构用接近自然语

3、言的形式进行描述。由于伪代码结构清晰、代码简单、可读性好，并且类似自然语言，在算法设计中得到了广泛使用。2 算法描述2 算法描述例1.1 使用伪代码描述冒泡排序算法。/算法 BubbleSort(A,n)/输入：数组A、元素个数n/输出：排序后的数组for i 1 to n-1 do /将1赋值给i，执行1n-1轮循环 for j i to n-i-1 do /将i赋值给j，执行循环 if Aj Aj+1 then /判断交换Aj与Aj+1的值 end if end forend forreturn A3 3算法主要类别及典算法主要类别及典型问题型问题 递归法递归法&递推法递推法 穷举法穷举法

4、 贪心算法贪心算法 分治法分治法 动态规划法动态规划法 分支界限法分支界限法 回溯法回溯法3 算法主要类别及经典问题程序调用自身的编程技巧称为递归（递归（RecursionRecursion）。一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解。问题来求解。例1.2 用递归法求解Fibonacci数列中第n个数。3 算法主要类别及经典问题递推法的思想是把一个复杂的庞大的计算过程转化为简单过程的多次重复。把一个复杂的庞大的计算过程转化为简单过程的多次重复。3

5、算法主要类别及经典问题 穷举法（又称蛮力法）通过列举出问题的所有可能的情况，逐个判断是符合问题约束穷举法（又称蛮力法）通过列举出问题的所有可能的情况，逐个判断是符合问题约束，如果符合则得到问题的一个解。例1.4百钱买百鸡问题 我国古代数学家张丘建在算经一书中曾提出过著名的“百钱买百鸡”问题，该问题叙述如下：鸡翁一，值钱五；鸡母一，值钱三；鸡雏三，值钱一；百钱买百鸡，则翁、母、雏各几何？for x 1 to 20 do for y 1 to 33 do z 100-x-y if 5*x+3*y+z/3=100 and z mod 3=0 then 输出公鸡 x 只，母鸡 y 只，小鸡 z 只en

6、d if end for end for3 算法主要类别及经典问题 贪心算法（又称贪婪算法）在求解问题的过程中总是做出在当前格局下最好的决策，并不贪心算法（又称贪婪算法）在求解问题的过程中总是做出在当前格局下最好的决策，并不从整体最优上加以考虑，从整体最优上加以考虑，因此，贪心法得到的是在往往是问题的局部最优解。贪心算法是一种对某些求最优解问题的更简单、更迅速的设计技术。求最短路径的Dijkstra算法实际上是一个贪婪算法，因为该算法总是试图优先访问每一步循环中距离起始点最近的下一个顶点。例1.5 最短路径Dijkstra算法伪代码3 算法主要类别及经典问题 分治法主要包括将原问题分为相同获相

7、似的子问题、对子问题进行求解、合并子问题的解这分治法主要包括将原问题分为相同获相似的子问题、对子问题进行求解、合并子问题的解这几个主要的步骤。几个主要的步骤。其中对子问题进行求解可能会进一步分成更小的问题，这是一个递归求解的过程，直到更小的问题能够直接求解。折半查找即利用分治法的思想进行问题求解，通过将搜索范围折半，将原问题分解为两个两个相同的问题，持续分解子问题直到找到所查找元素的位置或者确定不存在该元素。例1.6 折半查找算法伪代码3 算法主要类别及经典问题 动态规划是一种在数学和计算机科学中求解包含重叠子问题的最优化问题的方法。动态规划是一种在数学和计算机科学中求解包含重叠子问题的最优化

8、问题的方法。其基本思想是，将原问题分解为相似的子问题，在求解的过程中通过子问题的解求出原问题的解。动态规划法适用于具有重叠子问题的问题，通过表格技术存储子问题的求解结果，并通过查表避免重复计算，实现“以空间换时间”的算法设计目标。利用递归求解Fibonacci数列第n项问题时，存在大量的重复计算，消耗过多的CPU资源，导致算法运行时间变长，如图所示。3 算法主要类别及经典问题例1.7 Fibonacci数列动态规划伪代码3 算法主要类别及经典问题 分支限界法是对有约束条件分支限界法是对有约束条件的最优化问题的所有可行解（数的最优化问题的所有可行解（数目有限）空间进行搜索目有限）空间进行搜索。搜

9、索策略是基于广度优先原则（主要利用优先队列），优先扩展当前搜索结点的所有子节点，并利用限界函数剪切不符合问题约束的分支，减少搜索空间、提高算法性能。分支限界法本质上是穷举法，但因为有限界函数剪枝的作用可以减少部分搜索空间，因此，其效率一般要高于穷举法。例1.8 分支限界法通用模板伪代码3 算法主要类别及经典问题 回溯法（探索与回溯法）是一种选优搜回溯法（探索与回溯法）是一种选优搜索法，按选优条件向前搜索，以达到目标。索法，按选优条件向前搜索，以达到目标。选优策略是采用深度优先原则进行，并结合剪枝函数来减少搜索范围，提高算法执行效率。剪枝函数主要是两类：当前选择不符合问题约束或者不能达到最优的部

10、分解。迷宫问题是求一条从指定起点到达指定终点的搜索问题，搜索过程从起点出发，按照上、下、左、右四个方向按深度优先原则（递归调用）进行搜索，如果相邻点是不可通过（不符合问题约束），则放弃当前搜索方向（剪枝），转而搜索其他方向，直到到达终点。例1.9 迷宫问题求解伪代码4 4算法复杂性分析算法复杂性分析 算法输入规模度量算法输入规模度量 算法运行时间的度量算法运行时间的度量 渐进符号渐进符号 算法复杂性分析算法复杂性分析4 算法复杂性分析算法输入规模度量算法输入规模度量4 算法复杂性分析算法运行时间的度量算法运行时间的度量4 算法复杂性分析渐进符号渐进符号4 算法复杂性分析大大O O符号的含义如图

11、所示：符号的含义如图所示：4 算法复杂性分析4 算法复杂性分析4 算法复杂性分析4 算法复杂性分析4 算法复杂性分析4 算法复杂性分析算法复杂性分析算法复杂性分析 算法复杂性指的是算法运行所需要的计算机资源的量，需要时间资源的量称为时间复杂性，需要的空间资源量称为空间复杂性。算法效率的度量，是评价算法优劣的重要依据。一个算法的复杂性的高低体现在运行该算法所需要的计算机资源的多少，所需的资源越多说明算法的复杂性越高；反之，所需的资源越低，则算法的复杂性越低。4 算法复杂性分析非递归非递归算法复杂性分析算法复杂性分析例1.20顺序查找算法复杂度分析。4 算法复杂性分析非递归非递归算法复杂性分析算法

12、复杂性分析例1.21选择排序算法复杂度分析。4 算法复杂性分析非递归非递归算法复杂性分析算法复杂性分析例1.22图的全源点最短路径Floyd算法复杂度分析。/算法：Floydfor k 0 to n do for i 0 to n do for j 0 to n do if disi,k!=and disk,j!=and disi,k+disk,j disi,j then disi,j disi,k+disk,j end if end for end forend for4 算法复杂性分析递归递归算法复杂性分析算法复杂性分析4 算法复杂性分析递归递归算法复杂性分析算法复杂性分析例1.24二分查找算法复杂度分析每次折半的搜索过程形成一棵二叉树，如图所示：4 算法复杂性分析递归递归算法复杂性分析算法复杂性分析4 算法复杂性分析递归递归算法复杂性分析算法复杂性分析例1.25求解汉诺塔问题算法复杂度分析4 算法复杂性分析递归递归算法复杂性分析算法复杂性分析