La evaluación de la complejidad del tiempo promedio de un algoritmo de ordenamiento de burbuja dado.

Question

Teniendo en cuenta este pseudo-código de un 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

¿Cuáles serían las ideas básicas que tendría que tener en cuenta para evaluar el tiempo de complejidad media? Yo ya realizado el cálculo de los peores y mejores casos, pero estoy atascado deliberar cómo evaluar la complejidad media del bucle interior, para formar la ecuación.

La ecuación del peor caso es:

$$ \ Sum_ {i = 0} ^ n \ left (\ sum_ {j = 0} ^ {n - (i + 1)} O (1) + O (1) \ right) = O (\ frac {n ^ 2 } {2} + \ frac {n} {2}) = O (n ^ 2) $$

en el que la sigma interior representa el bucle interior, y la sigma exterior representa el bucle exterior. Creo que tengo que cambiar los dos sigmas debido a la -clause "si-entonces-break", lo que podría afectar a la sigma exterior, sino también debido a la cláusula si en el bucle interno, lo que afectará a las acciones realizadas durante un bucle (4 + 1 acciones de comparación si es cierto, los demás sólo 1 de comparación).

Para la clarificación en el término-tiempo promedio: Este algoritmo de ordenación necesitará tiempo diferente en diferentes listas (de la misma longitud), como el algoritmo podría necesitar más o menos pasos a través de / dentro de los bucles hasta que la lista está completamente en orden . Trato de encontrar un (forma no estadística) matemático de la evaluación de la media de las rondas necesarias.

Para este espero cualquier orden que sea de la misma posibilidad.

Answer 1

!

Para las listas de longitud $ n $, la media por lo general significa que usted tiene que comenzar con una distribución uniforme en todo $ n $ permutaciones de [$ 1 $, .., $ n $]: Eso es todo las listas que tener en cuenta.

Su complejidad media a continuación, sería la suma del número de paso en todas las listas divididas por $ n! $.

Para obtener una lista dada $ (x_i) $ _i, el número de pasos de su algoritmo es $ ND $ donde $ d $ es la mayor distancia entre un elemento de $ x_i $ y su lugar que le corresponde $ i $ (pero sólo si tiene que moverse hacia la izquierda), que es $ \ MAX_I (\ max (1, i-x_i)) $.

A continuación, se hacen las cuentas: por cada $ D $ encontrar el número c_d $ $ de listas con esta distancia máxima en particular, entonces el valor esperado de $ d $ es:

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

Y es que los pensamientos básicos sin los cuales la parte más difícil es encontrar $ c_d $. Tal vez hay una solución más simple sin embargo.

EDIT: añadido `espera '

Answer 2

Recordemos que un par $ (A [i], A [j]) $ (resp. $ (I, j) $) se invierte si $ i A [j] $.

Asumiendo que su algoritmo realiza una permuta para cada inversión, el tiempo de ejecución del algoritmo dependerá del número de inversiones.

Cálculo del número esperado de inversiones en una permutación aleatoria uniforme es fácil:

Let $ P $ sea una permutación, y dejó $ R (P) $ sea el reverso de $ P $. Por ejemplo, si $ P = 2,1,3,4 $ entonces $ R (P) = 4,3,1,2 $.

Para cada par de índices $ (i, j) $ hay una inversión en exactamente una de cualquiera de $ P $ o $ R (P) $.

Dado que el número total de pares es $ n (n-1) / 2 $, y el número total y cada par se invierte en exactamente la mitad de las permutaciones, suponiendo todas las permutaciones son igualmente probables, el número esperado de inversiones es :

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

Answer 3

Número de permutas

número de inversiones = Número de permutas.

Por lo tanto, Número de iteraciones> $ \ frac {n (n-1)} {4} $

Por lo tanto, la caja media de la complejidad es $ \ omega (n ^ 2) $. Pero, puesto que no puede caso promedio exceda peor de los casos, obtenemos que es $ O (n ^ 2) $,

Esto nos da: Promedio de tiempo = $ \ theta (n ^ 2) $

(Tiempo complejidad = Número de iteración no. De iteraciones> no. De permutas)

Answer 4

en este documento, la complejidad del tiempo promedio de la burbuja alcanzó tipo O (n log (n))! http://algo.inria.fr/flajolet/Publications/ViFl90.pdf