优化算法以查找所有局部最大值 [英] Optimized algorithm to find all the local maximum

问题描述

我目前正在研究查找所有局部最大值的算法的时间复杂度。根据此，时间复杂度为O（log N）一维阵列是否仅找出一个最大值？

如果我想找到所有最大值，该怎么办？有没有办法找到所有复杂度小于暴力法O（N）的东西？

谢谢。

[1,2,1,2，...] 有 O（n）个局部最大值，因此输出大小本身就是 O（n）。

另一种证明发现所有局部最大值是Omega（n）问题的方法也是如此。

第一个请注意，找到全局最大值是Omega（n）问题。

现在，我们将代表以下算法来求解数组 A 中的全局最大值：

1. 在 A


2. 中查找所有局部最大值将（1）中的元素视为新元素数组 A 。


3. 如果size（A）> 1-返回1


4. 否则：A中唯一的元素是全局最大值。

算法的正确性是微不足道的，我们迭代地丢弃元素，然后全局

复杂度：

• 请注意，在每个步骤中，至少删除了 size（A）/ 2 个元素
  （为什么？）


• 这使我们 O（d（n））+ O（d（n / 2））+ O（d（n / 4））+ ... + O（d（1））


• 在上面的 O（d（n））中，是最优查找所有局部最大值算法的复杂性（步骤1）。


• 现在，鉴于此事实，并假设（朝着矛盾的方向） d（n）在 o（n） [小o表示法， d（n）渐​​近于 n ）]-我们得到 d（n）+ d（n / 2）+ ... + d（1）在 o（n + n / 2 + ... + 1）= o（2n）= o（n）





因此，我们在 o（n）算法中求解了全局最大值，但它是 Omega（n ）问题-矛盾。

因此，第1步中的算法必须为 Omega（n）。




I am currently looking into the time complexity of the algorithm for finding all the local maxima. According to this, the time complexity is O(log N) for 1D array. Is it for finding out only one maxima?

What if I want to find all the maxima? Is there any way to find all of them with complexity smaller than O(N) of brute force method?

Thank you.

解决方案

As I stated in comments, for the counter example of [1,2,1,2,...] there are O(n) local maxima, and the output size itself is thus O(n).

Another approach to prove that finding all local maxima is Omega(n) problem, goes as folloes.

First, note that finding global maximum is Omega(n) problem.
Now, we will represent the following algorithm to solve global maximum in an array A:

1. Find all local maxima in A
2. Regard the elements found in (1) as the new array A.
3. if size(A) > 1 - return to 1
4. else: the only element in A is the global maxima.

Correctness of the algorithm is pretty trivial, we iteratively discard elements, and the global maximum is never discarded.

Complexity:

• Note that in each step, at least size(A)/2 elements are removed (why?)
• This gives us the complexity of O(d(n)) + O(d(n/2)) + O(d(n/4)) + ... + O(d(1))
• In the above O(d(n)) is the complexity of the optimal 'find all local maxima' algorithm (step 1).
• Now, given this fact, and assuming (towards contradiction) d(n) is in o(n) [small o notation, d(n) is asymptotically 'weaker' than n)] - we get that d(n) + d(n/2) + ... + d(1) is in o(n + n/2 + ... + 1) = o(2n) = o(n)

So, we solved global maximum in o(n) algorithm, but it is Omega(n) problem - contradiction.
Thus, the algorithm in step 1 MUST be Omega(n).

这篇关于优化算法以查找所有局部最大值的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！