寻找大 O 递归

Question

我试图从下面的代码中找出什么是 Big O 和 big Omega。

此代码输入一个整数数组，并按升序对它们进行排序。最坏的情况是全部按降序排列 {5,4,3,2,1} ，最好的情况是升序 {1,2,3,4,5}。

static int counter = 0;
static int counter1 = 0;
static int counter2 = 0;

public static int[] MyAlgorithm(int[]a) {
    int n = a.length;
    boolean done = true;
    int j = 0;
    while(j<=n-2) {
        counter++;
        if(a[j]>a[j+1]) {
            int temp = a[j];
            a[j] = a[j+1];
            a[j+1] = temp;
            done = false;
        }
        j = j+1;
    }
    j = n-1;
    while(j>=1) {
        counter1++;
        if(a[j]<a[j-1]) {
            int temp = a[j-1];
            a[j-1] = a[j];
            a[j] = temp;
            done = false;
        }
        j = j-1;
    }
    if(!done) {
        counter2++;
        MyAlgorithm(a);
    }
    return a;

}

我得到的每个 while 循环的最坏情况是 n-1，对于递归它是 n/2。

最好的情况是 n-1 个 while 循环和零递归

所以我的大 Omega 是 (n)（没有递归）但是对于 Big O，这是让我感到困惑的部分，因为有 n/2 次递归调用，这是否意味着我执行 N X N（因为 n/2 递归）big O (n^2)？还是保持大 O(n)？？？

Answer 1

正如你所说，Omega 是 Omega(n)。如果数组 a 中的所有数字都已按排序顺序排列，代码将遍历数组两次，每个 while 循环一次。这是 n 步 O(1) 次。

在最坏的情况下，您假设 O(n^2) 是正确的。如您所见，以相反顺序排序的数组会产生这种最坏的情况。我们还可以通过按递增顺序排列数组然后仅交换第一个和最后一个数字来产生最坏的情况。然后 MyAlgorithm 中的每个运行移动 last/first 第二个位置。在 n/2 步（运行步，共 MyAlgorithm 步）之后，数字到达了它们的最终位置。因此，O(n/2 * n) = O(n^2).

小提示，一般排序在 O(n log n) 中，所以你只能在某些情况下在 O(n) 中排序。

寻找大 O 递归

Finding big O recursion

java

time-complexity

space-complexity