在数组中查找局部最小值

Question

给定一个整数数组,找到局部最小值.如果A [i-1]> A [i]和A [i] <A [i + 1],则元素A [i]被定义为局部最小值,其中i = 1 ... n-2.在边界元素的情况下,数量必须小于其相邻数字.

我知道如果只有一个局部最小值,那么我们可以用修改后的二进制搜索来解决.但是如果知道阵列中存在多个局部最小值,它能否及时解决O(log n)？

Answer 1

如果不保证数组元素是不同的,那么在O(log n)时间内不可能这样做.原因如下:假设您有一个数组,其中所有n> 1的值都相同.在这种情况下,没有元素可以是局部最小值,因为没有元素小于其邻居.但是,为了确定所有值都相同,您必须查看所有数组元素,这需要花费O(n)时间.如果使用的时间少于O(n),则无法查看所有数组元素.

另一方面,如果数组元素保证不同,您可以使用以下观察在O(log n)时间内解决此问题:

1. 如果只有一个元素,则保证是局部最小值.
2. 如果有多个元素,请查看中间元素.如果它是当地的最低要求,那么你已经完成了.否则,它旁边的至少一个元素必须小于它.现在,想象如果你从一个较小的元素开始并逐渐向远离中间元素的方向移动到阵列的一端,会发生什么.在每一步,要么下一个元素小于前一个元素,要么它更大.最终,您将以这种方式命中阵列的末尾,或者您将达到局部最小值.请注意,这意味着您可以执行此操作以查找本地最小值.但是,我们实际上并没有这样做.相反,我们将使用这样一个事实,即在数组的这一半中存在局部最小值作为丢弃数组的一半的理由.在剩下的情况下,我们保证找到当地的最低要求.

因此,您可以构建以下递归算法:

1. 如果只有一个数组元素,那么它是局部最小值.
2. 如果有两个数组元素,请检查每个元素.一个必须是当地的最低要求.
3. 否则,请查看数组的中间元素.如果是当地最低要求,请将其退回.否则,至少一个相邻值必须小于此值.递归包含较小元素(但不是中间)的数组的一半.

请注意,这具有递归关系

T(1)≤1

T(2)≤1

T(n)≤T(n/2)+ 1

使用主定理,您可以根据需要显示此算法在时间O(log n)中运行.

希望这可以帮助!

另请注意,只有当数组边缘小于相邻元素时,此算法的边数才算作局部最小值,此算法才有效.

Answer 2

局部最小值的数量可以是n/2; 你无法及时列举它们O(log n).

Answer 3

使用分而治之算法.设m = n/2,并检查值A [m](即数组中间的元素).

案例1:A [m-1] <A [m].然后数组的左半部分必须包含局部最小值,因此在左半部分递归.我们可以通过矛盾来证明这一点:假设A [i]不是每个0≤i<m的局部最小值.那么A [m-1]不是局部最小值,这意味着A [m-2] <A [m-1].类似地,A [m -3] <A [m -2].以这种方式继续,我们得到A [0] <A [1].但是A [0]是局部最小值,与我们最初的假设相反.

情况2:A [m + 1]> A [m].然后数组的右半部分必须包含局部最小值,因此在右半部分递归.这与案例1对称.

情况3:A [m-1]> A [m]和A [m + 1] <A [m].然后A [m]是局部最小值,所以返回它.运行时间重现是T(n)= T(n/2)+Θ(1),其产生T(n)=Θ(log n).