Оценка средней временной сложности данного алгоритма сортировки пузырьков.

Question

Рассматривая этот псевдокод bubblesort:

FOR i := 0 TO arraylength(list) STEP 1  
    switched := false
    FOR j := 0 TO arraylength(list)-(i+1) STEP 1
        IF list[j] > list[j + 1] THEN
            switch(list,j,j+1)
            switched := true
        ENDIF
    NEXT
    IF switched = false THEN
        break
    ENDIF
NEXT

Каковы были бы основные идеи, которые я должен был бы иметь в виду, чтобы оценить среднюю временную сложность?Я уже выполнил вычисление наихудшего и наилучшего случаев, но я застрял, размышляя о том, как оценить среднюю сложность внутреннего цикла, чтобы сформировать уравнение.

Уравнение в наихудшем случае выглядит следующим образом:

$$ \sum_{i=0}^n \слева(\sum_{j=0}^{n -(i+1)}O(1) + O(1)\справа) = O(\frac{n^ 2}{2} + \frac{n}{2}) = O(n ^2) $$

в котором внутренняя сигма представляет внутренний цикл, а внешняя сигма представляет внешний цикл.Я думаю, что мне нужно изменить обе сигмы из-за предложения "if-then-break", которое может повлиять на внешнюю сигму, но также из-за предложения if во внутреннем цикле, которое повлияет на действия, выполняемые во время цикла (4 действия + 1 сравнение, если true, иначе только 1 сравнение).

Для уточнения термина "среднее время":Этому алгоритму сортировки потребуется разное время для разных списков (одинаковой длины), поскольку алгоритму может потребоваться больше или меньше шагов по циклам до тех пор, пока список не будет полностью приведен в порядок.Я пытаюсь найти математический (нестатистический способ) оценки среднего значения этих необходимых раундов.

Для этого я ожидаю, что любой заказ будет иметь такую же возможность.

Answer 1

Для списков длиной $ n $ среднее значение обычно означает, что вы должны начать с равномерного распределения по всем $n! $ перестановкам [$ 1 $, .., $ n $]:это будут все списки, которые вы должны рассмотреть.

Тогда ваша средняя сложность была бы равна сумме количества шагов для всех списков, деленной на $ n! $.

Для данного списка $(x_i)_i $ количество шагов вашего алгоритма равно $ nd $, где $ d $ - наибольшее расстояние между элементом $ x_i $ и его законным местоположением $ i $ (но только если он должен переместиться влево), то есть $ \max_i(\max(1,i-x_i)) $.

Затем вы производите расчеты:для каждого $d $ найдите число $ c_d $ списков с этим конкретным максимальным расстоянием, тогда ожидаемое значение $ d $ равно:

$$\frac1{n!}\ \sum_{d=0}^n{\ dc_d}$$

И это основные мысли без самой сложной части, которая заключается в поиске $ c_d $.Хотя, может быть, есть более простое решение.

Редактировать:добавлено `ожидаемое"

Answer 2

Напомним, что пара $(A[i], A[j])$ (соответственно.$(i,j)$) инвертируется, если $i < j$ и $A[i] > A[j]$.

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

Вычислить ожидаемое количество инверсий при равномерной случайной перестановке несложно:

Пусть $ P $ будет перестановкой, и пусть $ R (P) $ будет обратным значению $ P $.Например, если $P = 2,1,3,4$, то $R(P) = 4,3,1,2$.

Для каждой пары индексов $(i,j) $ имеет место инверсия ровно в одном из $P$ или $R(P)$.

Поскольку общее количество пар равно $ n (n-1) / 2 $, а общее количество и каждая пара инвертируются ровно в половине перестановок, предполагая, что все перестановки одинаково вероятны, ожидаемое количество инверсий равно:

$$\frac{n(n-1)}{4}$$

Answer 3

Количество свопов < Количество итераций (как в оптимизированном, так и в простом пузырьковом сценарии)

Количество инверсий = Количество свопов.

Следовательно, Количество итераций > $\frac{n(n-1)}{4}$

Таким образом, средняя сложность случая равна $\omega(n ^2) $.Но, поскольку средний случай не может превышать наихудший, мы получаем, что это $ O (n ^ 2) $,

Это дает нам :Среднее время = $\ тета(n^2)$

(Временная сложность = Количество итераций №количество итераций > нет.о свопах)

Answer 4

в этом документе средняя временная сложность пузырьковой сортировки достигла O(nlog(n))!http://algo.inria.fr/flajolet/Publications/ViFl90.pdf