第一问答网»论坛 › 中问网 › 问答 › 分治法练习题 divide and conquer

分治法练习题 divide and conquer

11 |

1 | 2013-6-5 02:44:43 | 显示全部楼层 |阅读模式

可以用经典的二分法：每次找中间位置。具体地说，初始有端点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...

使用道具举报

返回列表发新帖

千问

主题	0 回帖	4882万积分

论坛元老

Rank: 8 Rank: 8

积分: 48824836

回复楼主返回列表

问答

热门排行

分治法 练习题 divide and conquer

分治法练习题 divide and conquer