Valutare la complessità media temporale di un dato algoritmo bubble sort.

Question

Considerando questo pseudo-codice di 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

Quali sarebbero le idee di base che avrebbe dovuto tenere a mente per valutare il tempo-media complessità? Ho già compiuto il calcolo dei casi peggiori e migliori, ma sono bloccato deliberare come valutare la complessità media del ciclo interno, a formare l'equazione.

L'equazione caso peggiore è:

$$ \ 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) $$

in cui sigma interno rappresenta il ciclo interno, e sigma esterno rappresenta il ciclo esterno. Penso che ho bisogno di cambiare entrambi i sigma a causa della -clause "if-then-break", che potrebbero influire sul sigma esterno, ma anche a causa della se-clausola nel ciclo interno, che interesserà le azioni fatte nel corso di un ciclo (4 azioni + 1 confronto se è vero, il resto solo 1 di confronto).

Per chiarimenti sul termine medio-tempo: questo algoritmo di ordinamento avrà bisogno di tempi diversi su diverse liste (della stessa lunghezza), come l'algoritmo potrebbe essere necessario più o meno passaggi attraverso / entro i cicli fino a quando la lista è completamente in ordine . Cerco di trovare un (modo non statistica) matematica di valutare la media di quei colpi necessari.

Per questo mi aspetto qualsiasi ordine di essere della stessa possibilità.

Answer 1

Per le liste di lunghezza $ n $, media di solito significa che si deve iniziare con una distribuzione uniforme su tutto il $ n $ permutazioni di [$ 1 $, .., $ n $]: che saranno tutte le liste voi prendere in considerazione.

Il media complessità sarebbe allora la somma del numero di step per tutte le liste divise per $ n! $.

Per una data lista $ (x_i) $ _i, il numero di passi del vostro algoritmo è $ nd $ dove $ d $ è la più grande distanza tra un elemento di $ x_i $ e la sua posizione legittima $ i $ (ma solo se deve spostarsi a sinistra), che è di $ \ MAX_I (\ max (1, i-x_i)) $.

Poi fate i conti: per ogni $ d $ trovare il numero $ C_D $ di liste con questa particolare distanza massima, allora il valore atteso di $ d $ è:

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

E questo è il pensiero di base senza la parte più difficile, che sta trovando $ C_D $. Forse c'è una soluzione più semplice, però.

EDIT: aggiunto `previsto '

Answer 2

Si ricordi che un paio $ (A [i], A [j]) $ (risp. $ (I, j) $) viene invertito se $ i A [j] $.

Supponendo tuoi effettua algoritmo uno swap per ogni inversione, il tempo di esecuzione del vostro algoritmo dipenderà dal numero di inversioni.

Il calcolo del numero atteso di inversioni in una permutazione casuale uniforme è facile:

Sia $ P $ un permutazione, e lasciare che $ R (P) $ sia il contrario di $ P $. Per esempio, se $ P = 2,1,3,4 $ allora $ R (P) = 4,3,1,2 $.

Per ogni coppia di indici $ (i, j) $ è un'inversione esattamente uno tra $ P $ o $ R (P) $.

Poiché il numero totale di coppie è $ n (n-1) / 2 $, e il numero totale e ogni coppia è invertito esattamente la metà delle permutazioni, assumendo tutte le permutazioni sono equiprobabili, il numero atteso di inversioni è :

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

Answer 3

Numero di swap

numero di inversioni = Numero di swap.

Pertanto, Numero di iterazioni> $ \ frac {n (n-1)} {4} $

In questo modo, caso media complessità è $ \ omega (n ^ 2) $. Ma, dal momento che caso medio sopraelevazione supera peggiore dei casi, si ottiene che sia $ O (n ^ 2) $,

Questo ci dà: Tempo medio = $ \ theta (n ^ 2) $

(Tempo complessità = numero di iterazioni n. Di iterazioni> n. Di swap)

Answer 4

in questo documento, la complessità media momento della bolla sorta raggiunto O (nlog (n))! http://algo.inria.fr/flajolet/Publications/ViFl90.pdf