算法设计与分析_04算法分析举例

2019/12/18算法设计与分析演示稿纪玉波制作(C)1算法设计与分析——算法分析举例2019/12/18算法设计与分析演示稿纪玉波制作(C)2算法分析举例•本节举几个对具体算法进行分析的例子，可以由此学习分析的方法，举一反三再分析其它的算法。2019/12/18算法设计与分析演示稿纪玉波制作(C)3例1.堆阵排序1．堆阵堆阵排序（Heapsort,1964年RobertW.Floyd和J.Williams共同设计，1978年RobertW.Floyd获图灵奖）是利用二叉树的一种排序方法。堆(Heap)也译为堆或堆垒,是与二叉排序树不同的一种二叉树，它的定义为：一个完全二叉树(完全二叉树：各层都是满的，只是最下面一层从右边起连续缺几个结点)，它的每个结点对应于原始数据的一个元素，且规定：如果一个结点有子结点，此结点数据必须大于或等于其子结点的数据。由此可见，堆是完全二叉树，且规定了父结点和子结点数据之间必须满足的条件。2019/12/18算法设计与分析演示稿纪玉波制作(C)4由于堆阵是完全二叉树，采用将结点顺序编号存于一维数组中的表示法较链接表示法节省存储也便于运算。设某堆的结点数共有n个，顺序将它们存人一维数组K中，下标从1到n。根据顺序表示二叉树的特点，除下标为1的结点是整个树的根结点而没有父结点以外，其余下标为j的结点（2≤j≤n）都有父结点，父结点的下标为i=。故堆阵的条件可以表示成:K[i]≥K[j]当2≤j≤n和i=由堆的定义可知，其根结点（即在数组中下标为1的结点）具有最大的数值，堆阵排序就是利用这一特点进行的。堆阵排序过程分为构成堆和利用它来排序两个阶段，下面分别进行介绍。2019/12/18算法设计与分析演示稿纪玉波制作(C)52．构成堆阵的过程可以采用两种方法构成堆阵。第一种方法是从根结点起逐个插入结点，在插入结点过程中进行父子结点数据比较和必要的互换调整，使之总满足堆的条件；第二种方法则是先把所有数据按任意次序置入完全二叉树的各结点中，然后由下而上逐层进行父子结点数据比较，进行必要的互换调整，直至使其最后完全满足堆的条件，数据的比较调整可以使用“筛”运算进行。筛运算从最末尾结点（下标为n）的父结点（下标为）开始，向前逐结点进行，直至筛完根结点即形成此堆阵。筛每个结点时，将其数值与其两个子结点中数值较大者进行比较，如小于子结点数值，则与之进行互换，互换后又将它看成父结点，再与下一层的子结点进行比较，如此做下去，直至不小于其子结点的数值或已筛到端结点而不再有子结点了，此数据的筛运算即完成。2019/12/18算法设计与分析演示稿纪玉波制作(C)63．利用堆阵排序由于在一个堆中根结点数据总是所有数据中之最大者，利用堆阵排序的方法是从根结点逐个取出数据，每次将新的元素再提到根结点，如此反复进行。为了节约存储，要求排序得到的有序数据序列仍存放于原数组中，故将从根结点取出的数据由数组的末端起逐单元存放。每存放一个数据，同时将原在该单元的数据换到根结点，但这样互换后一般会破坏堆的条件，为此，需对根结点再做一次筛运算，就又可形成新的满足条件的堆。随着数组末端存放的由堆中取出的数据越来越多，堆的结点数逐渐减少，当到取出了(n-1)个数据，堆阵只剩下一个根结点，此最后一个数据一定是全部数据中的最小者，堆阵排序过程即全部结束。2019/12/18算法设计与分析演示稿纪玉波制作(C)74．时间复杂性分析堆阵排序分为建立堆阵和利用堆阵排序两大步骤。设堆阵有r个满层，元素个数n=2r-1。最坏的情况假设每个元素都需要从原来位置筛到堆阵的最底层，仅原来在最底层的不必筛，这样一来最上层的一个元素要下降r-1层；第二层的两个元素要下降r-2层；……；中间第i层2(i-1)个元素要下降r-I层；……；下面倒数第一层，也即第r-1层的2(r-2)个元素下降一层。每筛下一层要进行两次比较（先左右两子节点相比，然后此元素与其中较大者比）。因此在最坏的情况下，为了建立堆阵所需要的比较次数为：2019/12/18算法设计与分析演示稿纪玉波制作(C)82019/12/18算法设计与分析演示稿纪玉波制作(C)9下面看利用堆阵排序所需要的比较次数。排序时由后向前顺次将元素与根结点对换，并将换到根结点的元素筛到合适的位置处，如果逐个进行，堆阵越来越小，直至排序完毕。设在某一步堆阵有i个元素，其深度为，最坏情况将根元素筛到堆阵最下层需要比较次为，故最坏情况排序过程的总比较次数为：2019/12/18算法设计与分析演示稿纪玉波制作(C)102019/12/18算法设计与分析演示稿纪玉波制作(C)11因此堆阵排序总的比较次数当n较大时最坏情况为2nlogn(其复杂性为O(nlogn))，为排序问题下界的两倍。虽然此排序算法时间上不是最优，但它是“就地”进行运算，也不需要指示字分量，故所占空间比较节省。2019/12/18算法设计与分析演示稿纪玉波制作(C)12例2.快速排序快速排序(Quicksort)是1962年由霍尔（Hoare）提出的，故也称为霍尔快速排序。这是一种基于分部分进行互换的排序方法，其基本思想是将所有数据逐步划分成越来越多的许多小部分，每划分一次，以后的互换只在划分成的各小部分中进行，再将各小部分划分成更小的部分。此算法是把一个大问题划分成一些子问题，对这些子问题再用同样的算法递归地进行处理，最后将所有子问题的解答合在一起即得到原来大问题的解，这种处理问题的算法叫做分治法（Divideandconquer）。2019/12/18算法设计与分析演示稿纪玉波制作(C)13进行快速排序运算，首先任选其中一个数据（例如选第一个数据）作为标准，经过一定的互换运算，令它将其余的数据划分为两部分，它本身处于这两部分数据之间，并且它前面的所有的数据均小于或等于它，它后面的所有的数据均大于或等于它。由此可看出两点：第一，此数据的位置就是它最终的合适位置，进一步的运算过程中此数据即不必再动；第二，以后的排序运算只需在划分成的每部分里进行，两部分之间不会再有数据互换。第一次划分以后，再用相同的算法对划成的部分进行类似的运算，即从每部分中任选一个数据将其划分成更小的两部分，依此递归地做下去，直至每个小部分中的数据个数均不超过一个为止，排序过程即结束。2019/12/18算法设计与分析演示稿纪玉波制作(C)14如原始数据已存于一维数组K中，设进行比较的两个数据所在单元下标分别为i和j。初始时i指向数组中第一个数据，j指向第末个数据。i先不动使j逐步前移，每次对二者的数据进行比较，当遇到K[i]大于K[j]的情况时，即将二者对调位置；然后令j固定使i逐步后移做数据比较，再遇到K[i]大于K[j]时又进行位置对调；以后又是i不动使j前移做数据比较；……；如此反复进行，直至i与j两者相遇为止。下面是一实例：2019/12/18算法设计与分析演示稿纪玉波制作(C)152019/12/18算法设计与分析演示稿纪玉波制作(C)16其中括号中的数据表示正进行比较的两个数据，左面一个的下标为i，右面一个的下标为j。最后一行只有一个括号，说明i与j相等了，此单元即是作为标准的数据（13）之最终位置。从图中可以看出，作为标准的数据（13）要多次与别的数据进行比较和互换。为了节约运算时间，可先将其取出给一局部工作变量赋值，以后只移动别的数据，它不真正参加“互换”，一直到i=j时才将其置入最终合适的位置处。2019/12/18算法设计与分析演示稿纪玉波制作(C)172019/12/18算法设计与分析演示稿纪玉波制作(C)182019/12/18算法设计与分析演示稿纪玉波制作(C)19平均情况分析：此处除了为了具体推导出平均情况复杂性外还有两个目的：一是可以看出平均情况复杂性分析较最坏情况复杂性分析要困难得多；二是举例说明递归方程的解法。设选作标准的元素将数据分成两组，一组有k个元素，另一组有（n-k-1）元素。由于要考虑各种可能的情况，k值可能为0～（n-1），相应的另一组的个数则为（n-1）～0。令对n个元素进行快速排序所需要的平均比较次数为C（n），并设k的各种取值出现的概率相等，则C（n）为各种k的取值的平均值2019/12/18算法设计与分析演示稿纪玉波制作(C)20式中括号中第一项为第一趟所需的比较次数，后面两项分别为左右两部分数据继续进行快速排序所需的平均总比较次数，。这是一个递归方程，常可用两种解法：第一种是试猜法，即假设一个带有若干待定常数的函数，代入方程中导出这些常数，但这种方法假设这个函数要有一定经验；另一种方法是直接利用递归方程的特点求解。我们现介绍后一种方法。2019/12/18算法设计与分析演示稿纪玉波制作(C)212019/12/18算法设计与分析演示稿纪玉波制作(C)222019/12/18算法设计与分析演示稿纪玉波制作(C)232019/12/18算法设计与分析演示稿纪玉波制作(C)242019/12/18算法设计与分析演示稿纪玉波制作(C)25