java - 寻找大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 循环，零递归

所以我的大欧米茄是 (n) (无递归) 但对于 Big O 来说，这是令我困惑的部分，因为有 n/2 个递归调用，这是否意味着我执行 N X N (因为 n/2 递归)big O (n^2)？或者它仍然很大 O(n)???

Answer 1

正如您所说，欧米茄是Omega(n)。如果数组 a 中的所有数字都已按排序顺序排列，则代码会在数组上迭代两次，每个 while 循环一次。这是 n 步 O(1) 次。

在最坏的情况下，您的假设是正确的O(n^2)。正如您所看到的，按相反顺序排序的数组会产生最坏的情况。我们还可以通过按升序排列排序数组，然后仅交换第一个和最后一个数字来产生最坏的情况。然后，每次运行 MyAlgorithm 都会移动最后一个/第一个第二个位置。经过 n/2 步(运行 MyAlgorithm)后，数字到达最终位置。因此，O(n/2 * n) = O(n^2)。

<小时/>

小注，排序的时间复杂度一般为O(n log n)，因此只有在某些情况下才能在O(n)中对某些内容进行排序。