Анализ алгоритма сортировки пузырьков

Question

Обычно сложность рабочего времени buublesort равна O (n^2), но приведенный ниже алгоритм имеет цикл while и цикл for, цикл for зависит от n, но цикл while просто проверитель для логического значения. Может ли кто-нибудь сказать мне, как бы я вычислил время работы этого алгоритма?

bool done; 
done = false; 
while (! done) 
{ 
done = true; 
for (i = 0 ; i < a.length-1 ; i ++) 
    { 
    if (a[i] > a[i+1]) 
    { 

// Swap a[i] and a[i+1] 

    temp = a[i]; 
    a[i] = a[i+1]; 
    a[i+1] = temp; 

    done = false; 
    } 
} 
} 

Answer 1

Этот случай намного сложнее, чем алгоритм с двумя циклами, поскольку точное число итераций внешнего цикла не зависит только от N, но и от конкретной компоновки данных.

Если массив изначально отсортирован, не будет никаких свопов, а внешний цикл будет выполняться только один раз, для сложности O(N).

Если массив первоначально отсортирован в обратном порядке, каждое сравнение индуцирует swap, а внешний цикл выполняется N раз для полной сложности O(N²).

Общий случай намного сложнее оценить, так как он зависит от количества выведенных из строя элементов. Можно показать (по нетривиальному математическому аргументу), что для массива в случайном беспорядке средняя сложность остается O(N²).

Answer 2

Сложность алгоритма является время его работы в худший случай (по «случай» Я имею в виду всю бесконечную последовательность входных данных с увеличением длины). Понятно, что bubblesort нуждается только в операциях O (n) для сортировки массивов, которые уже отсортированы. Но это не считается. Есть некоторые массивы (последовательности массивов, фактически), которым нужны операции O (n^2).

P.S. Иногда более интересно, является ли алгоритм обычно работает в O (n) или таком. Но для пузырьковой системы даже «среднее ожидаемое время» равно O (0,5 * n^2), которое все равно совпадает с O (n^2).

Answer 3

Существует несколько способов подсчета сложности алгоритма. Самый простой и не строгий - найти наихудший случай и подсчитать количество циклов/итераций для него.

Если исходный массив устроен наоборот, ваш код должен будет выполнять точно n^2 сравнения.

Все лучшие способы требуют некоторого серьезного знания математики: вы должны сделать строгие доказательства. Например, чтобы доказать, что выбранный случай действительно худший.