Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

To find a local minimum in a field

  1. Dec 4, 2005 #1
    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
     
  2. jcsd
  3. Dec 13, 2005 #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.
     
  4. Dec 14, 2005 #3

    DrGreg

    User Avatar
    Science Advisor
    Gold Member

    Hint: does divide-and-conquer mean anything to you?


    (Sorry, franznietzsche's idea doesn't solve the problem because O(n/2) is still O(n).)
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: To find a local minimum in a field
  1. Root Finding (Replies: 5)

  2. Magnetic field contour (Replies: 0)

Loading...