算法简介 peak_finding

Peak Finding

peak(数学里的极大点,不过数组是离散的)

###1.一维情况

peak定义

对一维数组一般元素而言如果当前元素比左右的元素都不小(>=),它就是极点
而起点和终点只要比它旁边的元素大就是极点了
这样的定义下数组至少有一个极点

解法

1.遍历一遍,找到peak
时间复杂度: O(n)

2.分治法
查看n/2元素是否是极点,不是的话,沿着元素较大的方向继续查找
时间复杂度: O(log(n))

###2.二维情况

peak定义

对二维的数组而言,当前元素比上下左右四个元素都不小

####解法
1.贪心算法
按一定顺序比较和四个方向上元素的大小,朝较大的方向移动,直到找到极点
时间复杂度: O(mn)

2.分治法
对于j=m/2 找到该列最大点,按顺序比较左右元素,沿着较大值的方向递归