3 算法分析【荐】.ppt

3.1概率分析 每个实例都有同样的机会作为算法的输入而被算法计算 均匀分布(Uniform distribution) 线性有哪些信誉好的足球投注网站问题 给定一个具有n个数的数组，问题就是要回答数组里是否存在一个指定的数x，如果存在，给出该数在数组中的位置，如果不存在，则回答说不能找到 LinearSearch(A, x) 1 k ← 1 2 while (k ≤ n) and (x≠A[k]) do 3 k ← k+1 4 if k n then return 0 5 else return k 假定数组A中的元素为1到n之间的整数，而且两两互不相同 考虑数组中含有元素x，即能成功有哪些信誉好的足球投注网站到的情形: 在任意一个位置k ，元素x被找到的概率为 1/n 如果x=A[k], 则比较次数为k 算法找到元素的平均比较次数为 整个算法的平均时间复杂度由比较的次数决定，因此算法的平均情形时间复杂度为 插入排序InsertSort(A): 假定数组A中的元素为1到n之间的整数，而且两两互不相同。任意给定一个数组A ，其排列的数目为n!。 n!种排列中的任意一种排列具有同样的概率作为算法的输入。 . 考虑当前迭代要插入key=A[j] 到 A[1..j]共j个位置中的任何一个位置,插入到j个位置中的任何一个位置的概率为1/j .假设插入到k，现在我们分析为了插入到k，算法需要比较的次数。如果k=1，则算法需要比较的次数为j-k ，如果2≤k≤j ，则算法需要比较的次数为j-k+1 ，因此将key插入到A[1]到A[j]任何一个位置，平均比较的次数为 由于InsertSort(A)算法共迭代次n-1，因此，整个算法需要的平均比较次数为 聘用问题 假设你要聘用一个秘书。你对目前聘用的秘书不满意，你一直在试图寻找更合适的人选。因此，对当前的求职者面试之后，你决定，如果求职者的能力比当前秘书强，则解雇现在的秘书，并聘用该求职者。当然，面试的费用很低，而聘用的费用是昂贵的。你愿意支付这种策略所需要的费用，但是想预计整个费用是多大。 HireAssistant(n) 1 best ← 0 2 for i ← 1 to n do 3 interview candidate i 4 if candidate i is better than candidate best then 5 best ← i 6 hire candidate i. 令ci表示面试的费用， ch表示聘用的费用， m表示被聘用的人数，则HireAssistant(n)算法的总费用为O(nci + mch) 最坏情形 当第一个求职者就是最好的秘书时 最好情形 当应聘的求职者一个比一个好时，即后面来的求职者比前面的求职者好 概率分析 假定求职者以随机的顺序来应聘，并且能够比较两个求职者以确定哪一个更合格。对于当前的求职者，如果能够求得该求职者被聘用概率，则我们可以估计出整个的费用。事实上，对于第i个求职者，前面i个人，每一个人都有同样的机会被聘用，因此第i个求职者被聘用的概率为1/i, 因此平均聘用的费用为 对于这个聘任问题，算法平均情形复杂度为 3.2 分摊分析 通过研究执行一系列数据结构运算所需要的费用，来研究各个运算之间的关系。分摊分析能够用来证明，如果一系列运算的总费用是小的，则其中一个运算的分摊费用也是小的，即使一系列运算中某个运算的费用很大 分摊分析与平均情形分析的不同之处在于它不涉及复杂的概率分析，分摊分析保证了在最坏情形下每个运算具有的平均性能 一系列数据结构的运算，运算之间是相互关联的 3.2.1 合计方法 分析出由n个运算构成的序列在最坏情形下的运行时间总和T(n) ，因而在最坏情形下，每个运算的平均费用，或者分摊费用可定义为 T(n)/n 注意该分摊费用的计算方法对每个运算都是成立的，即使当序列中存在几种类型的运算时也一样 栈运算 PUSH(S, x) :将元素x压入S POP(S) :弹出并返回的顶端元素 因为这两个运算的运行时间都为O(1) ，故我们可以把每个运算的费用当作1。这样的话，一个包含个Push和Pop运算的序列的总费用就为n，因而这n个运算的实际运行时间就为O(n) 增加一个栈运算MultiPop(S,k)，它弹出栈S顶部的k个元素，但如果栈中元素的个数小于k ，则此运算将把栈清空，其伪代码如下 MULTIPOP(S, k) 1 while not STACK-EMPTY(S) and k ≠ 0 do 2 PO