作业帮分治法 练习题 divide and conquer一组数字A1到An 有一个位置p A1到Ap是递增 Ap到An是递减设计分治法算法找位置p；用你的算法建立递归关系对于键值比较并解释；（set up a recurrence relation for the num
来源：学生作业帮助网 编辑：作业帮 时间：2024/05/02 13:52:23
分治法 练习题 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}的时候用归纳,需要一些详尽的精准的陈述,不推荐.