finding local minimum of a NxN matrix with algorithm of order N as worst case

Question

3.00/5 (2 votes)

See more:

How do I find the local minimum of a NxN matrix without and O N^2 algorithm as below. The time takes for ever when N grows large. I need the algorithm to b order N as its worst case.

C#

int row = 0;
           int column = 0;
           Random random = new Random();


           int[,] matrix = new int[10, 10];
           for (int r = 0; r < 10; r++)
           {
                for (int c = 0; c < 10; c++)
                {
                     int randomNumber = random.Next(0, 100);
                     matrix[r, c] = randomNumber;
                }
           }


           int min = 100;
           Stopwatch timer = new Stopwatch();
           timer.Start();

           for (int i = 0; i < matrix.GetLongLength(0); i++)
           {
                for (int j = 0; j < matrix.GetLongLength(1); j++)
                {
                     if (matrix[i, j] < min)
                     {
                          min = matrix[i, j];
                     }

                }
           }
           timer.Stop();
          double time = timer.ElapsedMilliseconds;
          Console.WriteLine(time);

Posted 27-Jan-12 19:14pm

shekarchee

Updated 24-Jul-19 6:09am

Amir Mahfoozi

v2

Add a Solution

Comments

Sergey Alexandrovich Kryukov 28-Jan-12 2:01am

What is "local minimum"? Do you think there is "global" and "local" minimum? :-)
--SA

Andreas Gieriet 28-Jan-12 16:47pm

If speed really matters, you might consider programming this in some better suited language. Maybe C/C++? The complexity is still NxN, but there might be less overhead.

3 solutions

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Sergey Alexandrovich Kryukov · Answer 1 · 2012-01-27T20:30:00

Short answer is: there is no such thing as miracle.

The answer is already contained in the question. 1) The algorithm you show is really of the O(N²) complexity; 2) It can be improved but the complexity cannot grow lower then O(N²).

First, let's see why the complexity is O(N²). If you test all N² elements of the matrix, it gives you the said complexity. If you test not all of them, there is a chance of incorrect answer (false minimum) because any of the untested values can be less then the found value.

The real speed depends on the test set of values. That said, there is some probability that there is no less values, because you could sooner find the value of int.MinValue. In my solution below, this is taken into account. This line commented "questionable check" slightly reduce the complexity, but increase absolute time of the algorithm. Overall, it is useful only if the probability of int.MinValue in data is high enough. Generally, the real performance of any algorithm depends on the method of generation of data set.

Now, performance of your code could be improved by one mysterious trick: ++j makes better performance then j++. I avoided for loops by using foreach, please see below. Believe or not, it works correctly for multidimensional arrays.

Also, you need to fix a bug. You 100 is a bug, not even a bug, just foolishness. Real solution is using int.MaxValue. For floating point types, you should have used +Inf which correctly compares with other floating point values.

So, here is the fixed solution:

C#

internal static int Minimum(int[,] matrix) {
    int result = int.MaxValue; //sic!
    foreach(int value in matrix) {
        if (value == int.MinValue) return value; // questionable check
        if (value < result)
            result = value;
    } //loop
    return result;
} //Minumum

—SA

Andreas Gieriet · Answer 2 · 2012-01-28T10:45:00

As SAKryukov said, the problem is of complexity O(N²).

Sometimes it helps to view the problem from a different angle:

It might help if you determine that min property while constructing the matrix and cache it somehow... assuming the matrices are constant once they are constructed.
Or even more weird: store all the values in a sorted structure and only refer from the matrix to these values (maybe with some reference counting mechanism)... assuming you have huge matrices with not many differing values).
...

jkool_ · Answer 3 · 2019-07-24T06:09:00

I think that problem has the next focus:
find a local minimum:
a pair of indices i and j such that m[i][j] < m[i+1][j], m[i][j] < m[i][j+1],
m[i][j] < m[i-1][j], and m[i][j] < m[i][j-1]. Therefore, it's possible reach O(n).
Below there is an example in Java, I hope it is useful.

Java

public static void main(String[] args) {
        int[][] m = {{4, 5, 20, 31, 1}
                    ,{7, 31, 11, 8, 7}
                    ,{20, 29, 13, 19, 33}
                    ,{6, 16, 17, 27, 39}
                    ,{32, 37, 24, 26, 41}};
        
        int value = findLocalMinimum(m);
        System.out.println("value: "+value);
    }
    
    private static int findLocalMinimum(int m[][]){ 
        return find(m, m.length/2, m.length/2); //O(n)
    }
    
    private static int find(int m[][], int a, int b){
        if( (b == 0 || m[a][b-1] > m[a][b]) && (b == m.length-1 || m[a][b+1] > m[a][b]) && 
            (a == 0 || m[a-1][b] > m[a][b]) && (a == m.length-1 || m[a+1][b] > m[a][b]))
            return m[a][b];
        else if(b > 0 && m[a][b-1] < m[a][b])
            return find(m, a, b-1);
        else if(b < m.length-1 && m[a][b+1] < m[a][b])
            return find(m, a, b+1);
        else if(a > 0 && m[a-1][b] < m[a][b])
            return find(m, a-1, b);
        else 
            return find(m, a+1, b);
    }

Regards!

finding local minimum of a NxN matrix with algorithm of order N as worst case

3 solutions

Solution 1

Solution 2

Solution 4

Add your solution here

Preview 0