02第二章 算法分析.pptVIP

大学本科计算机专业应用型规划教材 数据结构（C++版） 第二章 算法分析 2.1 什么是算法分析 2.2 算法运行时间举例 2.3 最大连续子序列之和问题 2.4 通用Big-Oh规则 2.5 对数 2.6 静态有哪些信誉好的足球投注网站问题 2.7 检验一个算法分析 2.8 Big-Oh分析法的限制 2.1 什么是算法分析 任何算法花费的运行时间取决于它所要处理的数据输入量。例如，排序一万个元素比排序10个元素花费更多时间。算法的运行时间是数据输入量的一个函数，确切的函数值依赖于许多因素。例如，主机的运行速度，编译程序的质量，还有程序本身的质量。对于一个给定计算机上的给定程序，可以描绘出运行时间的函数。图2-1给出了四个程序的运行时间图，这些曲线代表了在算法分析中相遇的四个函数：线性函数、O（nlogn）、二次方函数、立方函数，输入规模n从1至100，运行时间为0至10毫秒。从图2-1和它的对比图2-2可知，线性函数，O（nlogn），平方函数，立方函数曲线所代表的函数呈有规律的递减趋向。 - - 2.2 算法运行时间举例 数组中的最小元素： 给出一个具有n项的数组，找出其最小元素。 最小元素问题是计算机科学中的基本问题，可用下列方法解决： 定义一个变量min存储最小元素； 初始化min为第一个元素； 顺序扫描整个数组，将min更改为合适的元素。 这个算法运行时间为O（n），是线性的，因为对数组中的元素重复做定量的工作，一个线性算法正是所期望的，需要测试数组中的每一个元素，这一过程需要线性的时间。 - 平面中距离最近的两点： 在平面（直角坐标系）中提供n个点，找出一对距离最近的点。 寻找距离最近点问题是图形中的基本问题，可用下列方法解决： 计算每对点间的距离。 保留最短距离。 计算比较花费时间，存在n（n-1）/2对点，大约为n2对点，测试所有对点，并找出它们中的最短距离将花费平方次的时间，一个好的算法运行O（nlogn）的时间，并避免计算所有的点。也存在一个算法只花费O（n）的时间。后两个算法通过细微的观察可快速得到一个结果。 2.3 最大连续子序列之和问题 给出n个整数（可为负）A1，A2，…，An，找出的最大值（与队列次序相同），如果所有整数为负，最大值为0。 2.3.1 简单易懂的O(n3)算法 2.3.2 一个改进的O(n2)算法 2.3.3 一个线性算法 2.3.1 简单易懂的O(n3)算法 最简单的算法就是直接穷举有哪些信誉好的足球投注网站或蛮力算法。 直接穷举有哪些信誉好的足球投注网站法的优点是非常简单。减少一个算法的复杂性，比较可能的方法就是编写程序要正确。然而，穷举有哪些信誉好的足球投注网站法的效率不可能太高。 这算法的运行时间由内部循环16和17行决定，四个表达式被重复： 初始化 k = i 测试 k = i 增长 ThisSum += a[ k ] 调整 k++ 2.3.2 一个改进的O(n2)算法 从这个算法中移走一个嵌套循环后，就降低了运行时间。怎样移走一个循环呢？显然，不能经常这样做，但是，先前的算法中有许多不必要的运算。这个需要改进的算法的低效率性就是算法2.1中的内部循环中的过度计算。改进后的算法利用了这样一个事实：，换句话说，假设已经要计算了从i到j-1子序列的值，则计算从i到j子序列的值就不会花费太长的时间，因为只需要额外加一个项，但是，立方算法抛弃了这个信息。利用这个观察到的信息得到了改进后的算法2.2，有两个而不是三个嵌套循环，运行时间为O（n2）。 2.3.3 一个线性算法 定理2.2： Ai，j为任意序列，且Si，j0，如果qj,则Ai，q不是值最大的连续子序列。 证明： 从i到q的序列的元素之和为从i到j的序列的元素之和加上从j+1到q的子序列的元素之和，则Si，q=Si，j+Sj+1，q因为Si，j0，所以Si，qSj+1，q，Ai，q不是一个最大的连续子序列。 - 定理2.3： 对于任意i，Ai，j为Si，j0的第一个序列，则对于任意i=p=j，且p=q，则 Ap，q也不是和最大的连续子序列或者只是一个与一个已经存在的和最大的连续子序列的和相等。 证明： 如果p=i，则适用于定理2.2。否则，如定理2.3，使Si,q=Si,q-1+Sp,q，j是使Si,j0的最小的下标，如果Si，p-1=0，则有Sp，q=Si，q，如果qj（如图2-5上图所示），则定理2.2表明：Ai，q不是和最大的连续子序列，Ap，q也不是，否则如图2-5下图所示，Ap，q至多与一个已经存在的子序列Ai，q的和相等。 - 定理2.3说明：当检测到一个和为负的子序列时，不仅能跳跃出内循环，而且可以将i提前到j+1，如算法2.3所示，只用一个循环就可以重写这个算法。很明显，这个算法的运行时间是线性的，在循环中的每一步，递增j，至多重复n次。 2.4 通用B