To find a local minimum in a field

In summary, the conversation discusses the concept of a local minimum in a field of integers and the search for an algorithm that can find a local minimum in a more efficient time than O(n). The suggested algorithm uses a loop and a conditional control statement, but it is not efficient enough. The conversation hints at using a divide-and-conquer algorithm to improve the efficiency.
  • #1
alejandrito
7
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
  • #2
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.
 
  • #3
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:

FAQ: To find a local minimum in a field

What is a local minimum in a field?

A local minimum in a field refers to the lowest point on the surface of a function in a particular region. It is the point with the smallest value in that specific area, but not necessarily the overall lowest point in the entire function.

How can I determine the location of a local minimum in a field?

To determine the location of a local minimum in a field, you can graph the function and look for the lowest point within a specific region. Alternatively, you can use calculus to find the minimum point by taking the derivative of the function and setting it equal to zero.

Why is finding a local minimum important in scientific research?

Finding a local minimum is important in scientific research because it helps identify the optimal point or solution within a specific region. This can be applied to various fields such as optimizing experimental conditions, finding the most efficient route, or determining the best parameters for a model.

Can there be multiple local minima in a field?

Yes, there can be multiple local minima in a field. This means that there can be more than one lowest point within a specific region of a function. It is important to carefully analyze the function and its surroundings to accurately identify all local minima.

How does the concept of a local minimum apply to real-life situations?

In real-life situations, the concept of a local minimum can be applied to various scenarios such as finding the most cost-effective solution, minimizing energy consumption, or optimizing resource allocation. It can also be used to analyze data and identify patterns or trends in a given system.

Similar threads

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

Hot Threads

Recent Insights

Back
Top