To find a local minimum in a field

Click For Summary
SUMMARY

The discussion centers on finding a local minimum in a field of N integers, where A[0] and A[N+1] are defined as infinity. A local minimum A[i] satisfies the condition A[i-1] >= A[i] <= A[i+1]. The proposed algorithm in Pascal iterates through the array but only achieves O(n) complexity. Participants suggest utilizing a divide-and-conquer approach to improve the algorithm's efficiency beyond O(n), hinting at testing every other value to reduce the number of comparisons.

PREREQUISITES
  • Understanding of local minima in arrays
  • Familiarity with algorithm complexity analysis
  • Basic knowledge of Pascal programming language
  • Concept of divide-and-conquer algorithms
NEXT STEPS
  • Research divide-and-conquer algorithms for optimization techniques
  • Learn about binary search methods applicable to local minima
  • Explore advanced data structures that can assist in finding local minima
  • Study algorithmic complexity and its implications on performance
USEFUL FOR

Computer scientists, algorithm developers, and programmers interested in optimizing search algorithms for local minima in arrays.

alejandrito
Messages
7
Reaction score
0
Let A be a field of N integers and A[0] = A[N+1] = infinity. Element A is called a local minimum if A[I-1] >= A <= A[I+1]. Find an alogrithm that will find some local minimum in a time asymptotically better then O(n). Hint: Consider that in each field deffined as before there must exist at least one local minimum.
The best algorithm (or programme in Pascal) I´ve found is the following:
...
while (A[I+1] > A[I+2] and I<N-1) do I:=I+1;
LOCMIN:=A[I+1];
...
which needs maximally N-1 steps to find a local minimum, but this is not enough if we want the asymptotical difficulty better then O(n). Could anybody help me with improving the algorithm? Thanks
 
Technology news on Phys.org
I haven't tried working this out in detail, but with a clever conditional control statement for the loop you should be able to find a local min testing only every other value, rather than every value(using I=I+2). I think. I might be wrong, but it may be worth a try.
 
Hint: does http://en.wikipedia.org/wiki/Divide-and-conquer_algorithm" mean anything to you?


(Sorry, franznietzsche's idea doesn't solve the problem because O(n/2) is still O(n).)
 
Last edited by a moderator:

Similar threads

Challenge: Find the minimum amount of draws possible for a list of integers
  • · Replies 9 ·
Replies
9
Views
3K
MHB Find path to minimum cost from start to finish
  • · Replies 19 ·
Replies
19
Views
2K
Python Finding a local max/min of a function in Python
  • · Replies 7 ·
Replies
7
Views
6K
MHB Finding a Local Minimum of $G$: Algorithm & Analysis
  • · Replies 22 ·
Replies
22
Views
5K
MHB Finding Min. Element in Sequence: Algo & Steps
  • · Replies 2 ·
Replies
2
Views
1K
MHB How to Sort Elements of a Matrix in O(n) Time Complexity?
  • · Replies 1 ·
Replies
1
Views
2K
To find a local minimum in a field
  • · Replies 2 ·
Replies
2
Views
3K
MHB A' should be asymptotically faster than A
  • · Replies 1 ·
Replies
1
Views
2K
MHB Minimum Degree of a Random Graph (Probabilistic Method)
  • · Replies 1 ·
Replies
1
Views
2K
Finding a Local Minimum in a Complete Binary Tree with Log(N) Probes
  • · Replies 1 ·
Replies
1
Views
2K