Could a nested loop be replaced with a counter variable to reduce the time complexity?-CodePudding

This might be a beginner question, but I have a method that is using a nested loop to look for a value inside a 2D array, let's say the body looks something like this: (assuming there is always a match for 1 in the 2D array)


        // example array ==> int arr = new int[5][5]
        int length = arr.length;
        int index1 = -1;
        int index2 = -1;

        loop:
        for (int i = 0; i < length; i  ) {
            for (int j = 0; j < length; j  ) {
                if (arr[i][j] == 1) {
                    index1 = i;
                    index2 = j;
                    break loop;
                }
            }
        }

I've replaced the second loop with an extra variable (counter) in this way:

        // example array ==> int arr = new int[5][5]
        int length = arr.length;
        int index1 = -1;
        int index2 = -1;
        int counter = 0;

        for (int i = 0; i < length; i  ) {
            if (arr[counter][i] == 1) {
                index1 = counter;
                index2 = i;
                break;
            }

            if (i == length - 1) {
                counter  ;
                i = 0;
            }
        }

Is this still considered a nested loop with the same time complexity? And please if there is a good link to understand how to analyze my code complexity in general, attach it!

This is a sample code, I know that some enhancements could be done, but I'm just asking about the time complexity (just ignore the edge cases and error handling)

CodePudding user response：

You should add this condition to the for loop, or you will have the ArrayOutOfBoundException:

 for (int i = 0; i < length && counter < length-1; i  ) //if the array is something like new int[5][5]

Try to measure the execution time of both with currentTimeMillis(), with different arrays and iterations :)

CodePudding user response：

You can use Test App to check the performance for each approach like below code snippet

package test;

public class TestLoops {

    static int numOfItrr = 30000;
    static int[][] arr = new int[numOfItrr][numOfItrr];

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        initArr();

        System.out.println("=====================Start======================");
        System.out.println("numOfItrr :"   numOfItrr);
        initArr();
        testWithForLoops();
        testWithCounter();
        System.out.println("=====================Finish=====================");
    }

    public static void initArr() {
        for (int i = 0; i < numOfItrr; i  ) {
            for (int j = 0; j < numOfItrr; j  ) {
                arr[i][j] = (int) (Math.random() * 1000);
            }
        }
    }

    public static void testWithForLoops() {
        long start = System.nanoTime();
        int max = arr[0][0];

        for (int i = 0; i < numOfItrr; i  ) {
            for (int j = 0; j < numOfItrr; j  ) {
                if (arr[i][j] > max) {
                    max = arr[i][j];
                }
            }
        }

        long end = System.nanoTime();
        System.out.println("time With loops    = "   (end - start));

    }

    public static void testWithCounter() {
        long start = System.nanoTime();

        int counter = 0;
        int max = arr[0][0];

        for (int i = 0; i < numOfItrr; i  ) {
            if (arr[counter][i] > max) {
                max = arr[counter][i];
            }
            if (i == numOfItrr - 1 && counter < numOfItrr - 1) {
                counter  ;
                i = 0;
            }
        }

        long end = System.nanoTime();
        System.out.println("time With Counter  = "   (end - start));
    }

}

Here are sample results

====================Start=====================

numOfItrr :10000

time With loops = 86591300

time With Counter = 110362600

====================Finish=====================

====================Start=====================

numOfItrr :30000

time With loops = 754436400

time With Counter = 978285600

====================Finish=====================

====================Start=====================

numOfItrr :30000

time With loops = 754230300

time With Counter = 970180300

====================Finish=====================

CodePudding user response：

It considers the content of O() as the maximum number of operations required for execution and 'n' the parameter to identify the size of the input.

The for loop generally iterates over a certain size, which in this case is the size of your array.

A for loop therefore performs at most 'n' operations, which is why it is called linear time or O(n).

In the first case you show two nested for-cycles, in which case a simple multiplication has to be made, because the cycle of complexity O(n) is done at most 'n' times, so it is called quadratic time or O(n^2).

The more the value of O(n) increases, the greater the complexity.

For simplicity:

For loop is O(n) and It's ok
2 For non-nested loops is O(n n), but it still says O(n) and It's ok
2 For nested loops is O(n*n) and is Not good
3 For nested loops is O(nnn) and is Really bad

That is why the second code you sent, assuming there are no errors, is certainly faster than the first.