What is the time complexity of the following algor

问题:

This question already has an answer here:

• How to find time complexity of an algorithm 9 answers

can someone tell me what is the time complexity of this algorithm? keep in mind: the second method (findMax) - run on the array based on the index that it gets, means that the method (findMax) doesn't run on all the array every time. I think that the time complexity of this algorithm is O(n) but maybe I'm wrong.

public class Q2 {


public static int[] replace(int []a)
{
    for(int i = 0; i < a.length; i++ ){
        if(i == a.length-1){
            a[i] = 0; 
       }

        int maxSubArry = findMax(a,i); 

          swap (a, i, maxSubArry);
    }
    return a; 

}


public static int findMax (int[]a, int i)
{
  //  i = i +1; 
    int tmp = 0; 
    for(i = i +1; i<a.length; i++)
    {
        if(a[i] > tmp)
            tmp = a[i];
    }
    return tmp; 
    }


public static void swap(int[]a, int i, int maxSubArry)
{
    int temp = a[i]; 
    a[i] = maxSubArry; 
    a[i+1] = temp; 
}

}

回答1:

your replace method is more like bubble sort algorithm and the algorithm complexity is O(n*n).

AND the initial value of findMax should be Integer.MIN_VALUE. and the if statement is unnecessary in replace.

public static int[] replace(int[] a) {
    for (int i = 0; i < a.length-1; i++) {
        swap(a, i, findMax(a, i));
    }
    return a;
}


public static int findMax(int[] a, int i) {
    int tmp = Integer.MIN_VALUE;
    for (i = i + 1; i < a.length; i++) {
        if (a[i] > tmp)
            tmp = a[i];
    }
    return tmp;
}

回答2:

You can do the calculation based on an example. Suppose your array passed to replace() has 10 elements (n = 10). So, the loop inside of replace() runs 10 times, and will call findMax 10 times. Because the loop inside findMax will only start running from i+1, the exact number of times it will run, based on the ten method calls, is (9-i) times:

 outer i | inner loop  | number of loops
=======================================
   0    | from 1 to 9 |     9
   1    | from 2 to 9 |     8
  ...   |  ...        |    ...
   8    | from 9 to 9 |     1
   9    | no loop     |     0

So your formula for the number of inner loops is 9 + 8 + 7 + ... + 1 = 45. That is roughly 1/2 n², and cleary more than n (which we assumed to be 10 in this example). As the big-o notation will disregard constant values, we can leave the 1/2 away, and simply say that the complexity is O(n²).

回答3:

Total complexity is O(n*n).For method findMax (int[]a, int i) in worst case it will take complexity of O(n) ,because in worst case it will search for 0 to last element as Max element present in last.

回答4:

The easiest way the figure out the running time of algorithms like this is to notice that findMax runs over at least half of the array, for at least half of its elements (the first half).

To say the same thing in math: let T(N) be the total number of times that findMax inner loop runs:

T(N) >= 0.5N * 0.5N

⇒ T(N) >= 0.25N²

The running time of this algorithm is therefore at least O(N²).

Then notice that findMax runs over at most the entire array for all of its elements, and that implies that the running time is at most O(N²).