В худшем случае сложность времени для этой глупой сортировки?

Question

Код выглядит так:

for (int i = 1; i < N; i++) {
    if (a[i] < a[i-1]) {
        swap(i, i-1);
        i = 0;
    }
}

Попробовав несколько вещей, я понял, что наихудший случай - когда входной массив находится в порядке убывания. Тогда выглядит так, что сравнение будет максимальным и, следовательно, мы будем рассматривать только сравнение. Тогда кажется, что это будет сумма сумм, то есть сумма... {1+2+3+...+(n-1)}+{1+2+3+...+(n-2))}+{1+2+3+...+(n-3)}+ .... + 1, если так, что будет O(n)?

Если я не на правильном пути, может кто-то указать, что O (n) будет и как его можно получить? ура!

Answer 1

Для начала, суммирование

(1 + 2 + 3 + ... + n) + (1 + 2 + 3 + ... + n - 1) + ... + 1

на самом деле не O(N). Вместо этого это O(n³). Вы можете видеть это, потому что сумма 1 + 2 +... + n = O(n², и есть n копий каждого из них. Вы можете более правильно показать, что это суммирование Θ(n³), посмотрев на сначала n / 2 из этих терминов. Каждый из этих терминов по крайней мере 1 + 2 + 3 +... + n / 2 = Θ(n²), поэтому существует n / 2 копии чего-то, что Θ(n²), давая точную оценку Θ(n³).

Мы можем ограничить общее время выполнения этого алгоритма в O(n³), отметив, что каждый своп уменьшает число инверсий в массиве на единицу (инверсия - это пара элементов не на своем месте). В массиве может быть не более O(n²) инверсий, а в отсортированном массиве инверсий нет (понимаете почему?), Поэтому не более O(n²) проходов по массиву, и каждое занимает не более На работе. Это в совокупности дает оценку O(n³).

Следовательно, identified (n³) наихудшего времени выполнения, которое вы определили, асимптотически ограничено, поэтому алгоритм выполняется за время O(n³) и имеет время выполнения наихудшего случая Θ(n³).

Надеюсь это поможет!

Answer 2

Это делает одну итерацию списка за своп. Максимальное количество необходимых свопов O(n * n) для обратного списка. Выполнение каждой итерации O(n),

Поэтому алгоритм O(n * n * n),

Answer 3

Это половина печально известной пузырьковой сортировки, которая имеет O(N^2). Эта частичная сортировка имеет O(N), потому что цикл For переходит от 1 к N. После одной итерации вы получите самый большой элемент в конце списка, а остальную часть списка - в некотором измененном порядке. Для правильной Bubble Sort необходим еще один цикл внутри этого цикла, чтобы перебрать j от 1 до Ni и сделать то же самое. If идет внутри внутреннего цикла.

Теперь у вас есть две петли, одна внутри другой, и они обе идут от 1 до N (вроде). У вас будет N * N или N ^ 2 итераций. Таким образом, O (N ^ 2) для Bubble Sort.

Теперь вы должны сделать следующий шаг как программист: закончите писать Bubble Sort и сделайте так, чтобы он работал правильно. Попробуйте использовать разные длины списка a и посмотрите, сколько времени это займет. Тогда никогда не используйте это снова.;-)