L'évaluation de la complexité du temps moyen d'un algorithme de tri à bulles donné.

Question

Compte tenu de cette pseudo-code d'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

Quelles seraient les idées de base, je dois garder à l'esprit pour évaluer la moyenne du temps complexité? Je l'ai déjà accompli le calcul des pires et les meilleurs cas, mais je suis délibérante bloqué comment évaluer la complexité moyenne de la boucle interne, pour former l'équation.

Le pire cas, l'équation est:

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

dans lequel le modulateur sigma interne représente la boucle intérieure, et le sigma extérieur représente la boucle externe. Je pense que je dois changer les deux sigmas en raison du -clause « if-then-break », ce qui pourrait affecter le sigma externe mais aussi en raison de la clause si dans la boucle intérieure, ce qui aura une incidence sur les actions effectuées au cours d'une boucle (4 actions + 1 comparaison si elle est vraie, sinon seulement 1 comparaison).

Pour plus de précisions sur la durée du temps moyen: Cet algorithme de tri aura besoin différent du temps sur les différentes listes (de la même longueur), que l'algorithme peut-être besoin plus ou moins d'étapes par / dans les boucles jusqu'à ce que la liste est tout à fait dans l'ordre . J'essaie de trouver un (de façon non statistique) mathématique d'évaluer la moyenne de ces tours nécessaires.

Pour cela, j'attends un ordre d'être de la même possibilité.

Answer 1

Pour les listes de longueur $ n $, en moyenne généralement signifie que vous devez commencer par une distribution uniforme sur toutes les permutations $ n $ de [$ 1 $, .., $ n $]: qui seront toutes les listes que vous doivent prendre en considération.

Votre complexité moyenne serait alors la somme du nombre d'étapes pour toutes les listes divisées par $ n! $.

Pour une liste $ donnée (x_i) $ _i, le nombre d'étapes de votre algorithme est $ nd $ où $ d $ est la plus grande distance entre un élément $ x_i $ et sa juste position $ i $ (mais seulement si il doit se déplacer vers la gauche), qui est $ \ MAX_I (\ max (1, i-x_i)) $.

Ensuite, vous faites le calcul: pour chaque $ d $ trouver le numéro $ C_D $ de liste avec cette distance particulière maximale, la valeur prévue de $ d $ est:

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

Ce sont les pensées de base sans la partie la plus difficile qui est de trouver $ C_D $. Peut-être il y a une solution plus simple cependant.

EDIT: ajout `devrait '

Answer 2

Rappelons que une paire $ (A [i], A [j]) $ (resp. $ (I, j) $) est inversé si $ i A [j] $.

En supposant que votre algorithme effectue un échange pour chaque inversion, la durée de fonctionnement de votre algorithme dépendra du nombre d'inversions.

Calcul du nombre prévu d'inversions dans une permutation aléatoire uniforme est facile:

Soit $ P $ une permutation, et que $ R (P) $ soit l'inverse de $ P $. Par exemple, si $ P = 2,1,3,4 $, alors $ R (P) = 4,3,1,2 $.

Pour chaque paire d'indices $ (i, j) $ il y a une inversion dans exactement un des deux $ P $ ou R (P) $.

Etant donné que le nombre total de paires est $ n (n-1) / 2 $, et le nombre total et chaque paire est inversé dans exactement la moitié des permutations, en supposant que toutes les permutations sont également probables, le nombre attendu d'inversions est :

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

Answer 3

Nombre de swaps

Nombre de Inversions = Nombre de swaps.

Par conséquent, Nombre de Iterations> $ \ frac {n (n-1)} {4} $

Ainsi, la complexité des cas moyenne est $ \ omega (n ^ 2) $.  Mais, étant donné que le cas moyen ne peut pas dépasser le pire des cas, nous obtenons qu'il est O $ (n ^ 2) $,

Cela nous donne: Temps moyen = $ \ theta (n ^ 2) $

(complexité Temps = Nombre d'itération pas. D'itérations> non. Des swaps)

Answer 4

dans ce document, la complexité du temps moyen de bulles sorte atteint O (nlog (n))! http://algo.inria.fr/flajolet/Publications/ViFl90.pdf