我为这个程序是O(n)运行时而疯狂吗?我的助教说是O(n ^ 2) [英] Am I crazy for thinking this program is O(n) runtime? My TA says it's O(n^2)

问题描述

以下代码，应为O(n). 我知道有两个循环.但这并不一定意味着它是O(n ^ 2).函数循环的运行时间不会超过n + 1次(至少据我所知！).那应该是O(n).我错了吗?有人可以帮我吗?谢谢！

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!

程序将奇数放在数组的前面，偶数放在数组的后面！！！

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;

    }

}

}

推荐答案

作为其他问题是该问题的重复部分，让我在此处发布答案.

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

当您增加i或减少end时，代码为O(n).无论如何，您将其余工作(n)减少了一个.

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.

对于即将到来的作业:您可以通过尝试轻松地测试关于big-O的想法.大多数时候，测试的数量不需要很大.这不是证明，但可以为您提供一个很好的提示，无论您的想法正确与否.

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.

这是我针对100个测试所遇到问题的代码.它产生100对数字:数组的长度和循环数.您将这个列表带到图表中.

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;
    }
}

图形看起来像一条直线.因此，您的证明应为O(n)，对吧?

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

这篇关于我为这个程序是O(n)运行时而疯狂吗?我的助教说是O(n ^ 2)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！