Am I crazy for thinking this program is O(n) runti

问题:

Code below, it should be O(n). There are two loops, I know this. But that doesn't necessarily mean it's O(n^2). The function loops won't run more than n + 1 times (at least as far as I can tell!). That should be O(n). Am I wrong? Can someone help me out? Thanks!

EDIT: The program puts odd integers at the front and even integers at the back of an array!!!

public class Main {

public static void main(String[] args) {


    int[] array = new int[]{5, 4, 3, 2, 1, 0};

    organizeArray(array);

    for (int j = 0; j < array.length; j++) {
        System.out.println(array[j]);
    }

}

public static void organizeArray(int[] array) {

    int end = array.length - 1;

    for (int i = 0; i < array.length; i++) {

        int temp = 0;

        while (true) {

            if (i == end)
                break;

            if (array[i] % 2 == 0) {

                temp = array[i];
                array[i] = array[end];
                array[end] = temp;
                end = end - 1;
            }

            if (array[i] % 2 != 0)
                break;

        }

        if (i == end)
            break;

    }

}

}

回答1:

Interesting code. The inner for loop will break when the i'th element is odd. If its not odd then it will swap elements from the end until an odd one is found. Since end is decremented upon each swap and the program completes when i reaches end, it follows that i or end can get incremented/decremented, respectively at most O(n) times. Because of this, and because all other operations in the loops are O(1), the program indeed runs in time O(n) despite there being nested loops.

回答2:

As the other question was a duplicate of this one, let me post my answer here.

The code is O(n) as you either increase i or reduce end. In any case, you decrease the rest of work (n) by one.

For your upcoming homework: You can test your thoughts about big-O easily just by trying out. Most of the time the number of tests doesn't need to be very big. It will not be a proof but it gives you a good hint if your thoughts are correct or not.

Here's is my code for your problem with 100 tests. It produces 100 pairs of numbers: The length of the array and the number of loops. You take this list and bring it to a graph.

public class Main {
    public static void main(String[] args) {
        Main main = new Main();
        Random random = new Random();

        for (int i = 0; i < 100; i++) {
            int[] array = new int[random.nextInt(10000 - 10) + 10]; // between 10 and 9999 numbers long
            for (int j = 0; j < array.length; j++) array[j] = random.nextInt();

            main.organize(array);
        }
    }

    private int[] organize(int[] array) {
        long loops = 0;
        int end = array.length-1;

        // I've shorten your code here. This does the same with less breaks
        for (int i = 0; i < end; i++) {
            while(i < end && array[i] % 2 == 0) {
                swap(array, i, end--);
                loops++;
            }
        }

        System.out.printf("%d\t%d\n", array.length, loops);
        return array;
    }

    private void swap(int[] array, int a, int b) {
        int t = array[a];
        array[a] = array[b];
        array[b] = t;
    }
}

And the graph looks like a straight line. So your proof should result in O(n), right?