分治法 练习题 divide and conquer一组数字A1到An 有一个位置p A1到Ap是递增 Ap到An是递减设计分治法算法找位置p;用你的算法建立递归关系对于键值比较并解释;(set up a recurrence relation for the num
来源:学生作业帮助网 编辑:作业帮 时间:2024/06/22 03:41:38
![分治法 练习题 divide and conquer一组数字A1到An 有一个位置p A1到Ap是递增 Ap到An是递减设计分治法算法找位置p;用你的算法建立递归关系对于键值比较并解释;(set up a recurrence relation for the num](/uploads/image/z/14483316-12-6.jpg?t=%E5%88%86%E6%B2%BB%E6%B3%95+%E7%BB%83%E4%B9%A0%E9%A2%98+divide+and+conquer%E4%B8%80%E7%BB%84%E6%95%B0%E5%AD%97A1%E5%88%B0An+%E6%9C%89%E4%B8%80%E4%B8%AA%E4%BD%8D%E7%BD%AEp++A1%E5%88%B0Ap%E6%98%AF%E9%80%92%E5%A2%9E++Ap%E5%88%B0An%E6%98%AF%E9%80%92%E5%87%8F%E8%AE%BE%E8%AE%A1%E5%88%86%E6%B2%BB%E6%B3%95%E7%AE%97%E6%B3%95%E6%89%BE%E4%BD%8D%E7%BD%AEp%EF%BC%9B%E7%94%A8%E4%BD%A0%E7%9A%84%E7%AE%97%E6%B3%95%E5%BB%BA%E7%AB%8B%E9%80%92%E5%BD%92%E5%85%B3%E7%B3%BB%E5%AF%B9%E4%BA%8E%E9%94%AE%E5%80%BC%E6%AF%94%E8%BE%83%E5%B9%B6%E8%A7%A3%E9%87%8A%EF%BC%9B%EF%BC%88set+up+a+recurrence+relation+for+the+num)
分治法 练习题 divide and conquer一组数字A1到An 有一个位置p A1到Ap是递增 Ap到An是递减设计分治法算法找位置p;用你的算法建立递归关系对于键值比较并解释;(set up a recurrence relation for the num
分治法 练习题 divide and conquer
一组数字A1到An 有一个位置p A1到Ap是递增 Ap到An是递减
设计分治法算法找位置p;
用你的算法建立递归关系对于键值比较并解释;
(set up a recurrence relation for the number of key comparisons made by your algorithm and explain it)
根据递归关系,用BIG-O 符号写出复杂度 并用数学归纳法证明(为了简单,可以设n=2k)
急用 最后一问可以不答 只要设计好算法 并写出递推关系式比如T(n)=T(n-2)+1
分治法 练习题 divide and conquer一组数字A1到An 有一个位置p A1到Ap是递增 Ap到An是递减设计分治法算法找位置p;用你的算法建立递归关系对于键值比较并解释;(set up a recurrence relation for the num
可以用经典的二分法:每次找中间位置.具体地说,
初始有端点1和n,故取中点p=[(n+1)/2],这里中括号表示取整.考察连续的三个点p-1,p,p+1处的数的大小关系.由于已知序列是单峰的(为容易说明算法思想,假设没有相等的数),故A_{p-1},A_{p},A_{p+1}只有三种可能:要么递增,要么递减,要么先增后减.
如果先增后减,则此p即为所求.
如果递增,则说明欲求的峰值点比这个p点大,那么考虑端点p和n,重复上面的算法.
如果递减,则说明欲求的峰值点比这个p点小,那么考虑端点1和p,重复上面的算法.
这就建立了递归算法.
复杂度是O(log_2{n}).因为每次考虑都把欲求的峰值点的可能位置从全部可能中缩小一半(加减1,在大O符号中可忽略不及).具体地说,当序列长度是2^m的时候,第一次取中点,排除掉一半可能,剩下2^{m-1}个可能的峰值点;第二次取中点,排除掉一半可能,剩下2^{m-2}个可能的峰值点;一次类推.最终经过至多多m+1次就能找到峰值点.反过来看,设n=2^m,那么m=log_2{n}.用大O符号,数值+1可以忽略.当序列长度不是2^m的时候,一定有一个m使得序列长度介于2^{m}和2^{m+1},按照上述证明,复杂度介于O(log_2{n})和O(log_2{n}-1),这俩O符号的意思的一样的,所以复杂度是O(log_2{n}).
用归纳法证明的思想本质是一样的,不过严格的陈述需要自己设定很多额外的约定才能说清楚,比如n的值从介于2^{m-1}和2^m变化到介于2^m和2^{m+1}的时候用归纳,需要一些详尽的精准的陈述,不推荐.