Нахождение большой 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 рекурсивных вызова, означает ли это, что я делаю NXN (из-за n / 2 рекурсии) большой 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).