arrays - 多峰的一维寻峰算法

Question

目前，我指的是 MIT OpenCourseWare 在下面的视频教程中给出的关于在一维数组中查找峰值的解释。

https://www.youtube.com/watch?v=HtSuA80QTyo

递归关系:T(n)=T(n/2) + O(1) 只强调数组的一半加上它会导致一个峰值作为输出。说多峰确实存在的递归关系可能是什么。

请有人解释一下这个查询。

提前致谢!

Answer 1

视频中的问题是:在一维数组 A[0...N-1] 中找到一个峰，其中 A[i] 是一个当 A[i] >= A[i-1] 且 A[i] >= A[i+1] 或 i = 0 且 A[i] >= A[ 时达到峰值i+1] 或 i = N-1 and A[i] >= A[i-1]。一个数组可能有很多峰，注意你只需要给出任何一个。这个问题可以用分而治之的算法来解决。我用 C 实现了它。

// it return the index of the peak.
//it can contain many peak, you can return Any One.

int find_a_peak(int a[], int low, int hi) {
   if (low == hi) return low;
   if (low == hi - 1) return a[low] > a[hi] ? low : hi;
   int mid = (low + hi) / 2;
   if (a[mid] >= a[mid+1]) {
     //At least one peak can be found in the subarray A[low,low+1,...,mid]
     return find_a_peak(a, low, mid);
   } else {
     //At least one peak can be found in the subarray A[mid+1,...,hi]
     return find_a_peak(a, mid+1, hi); 
   } 
}

其实这个算法和二分查找是一样的。您可以在每一步中将数组的大小减半。即 T(N) = T(N/2) + O(1)，这样 T(N) = O(lnN)。