Complexité du tri par insertion binaire pour les swaps et comparaison dans le meilleur des cas

Question

Quelle pourrait être la complexité du tri par insertion binaire? Et combien de swaps et de comparaisons sont effectués?

Ce sont peut-être des O(n(LG n))comparaisons, mais je ne suis pas sûr. Dans le pire des cas, il s'agit bien de N^2swaps. Et le meilleur?

Answer 1

Vous pouvez écrire facilement un tri par insertion binaire en utilisant des fonctions intégrées telles que bisect_leftet list.pop(..)et list.insert(..):

def bininssort(L):
    n = len(L)
    i,j=0,0
    for i in range(1,n):
        j=i-1
        x=L.pop(i)
        i1=bisect_left(L,x,0,j+1)
        L.insert(i1,x)
    return L

À propos du pire des cas, car à l' i-thitération de la boucle, nous effectuons une recherche binaire à l'intérieur du sous-tableau A[0..i], avec 0<=i<n, cela devrait prendre des log(i)opérations, donc nous savons maintenant que nous devons insérer un élément à l'emplacement i1et nous l'insérons, mais l'insertion signifie qu'il faut pousser tous les éléments qui le suivent d'une position vers la droite, et c'est au moins des n-iopérations (cela peut être plus que des n-iopérations selon l'emplacement d'insertion). Si nous résumons juste ces deux, nous obtenons\sum_{i=1}^n log(i) + (n-i) = log(n!) + (n*(n+1))/2 ~ n*log(n) + (n*(n+1))/2

(dans l' approximation de Stirling ci-dessus log(n!)est utilisée)

Maintenant, la page wiki dit

En règle générale, on peut supposer que le terme d'ordre le plus élevé dans une fonction donnée domine son taux de croissance et définit ainsi son ordre d'exécution

Je pense donc que la conclusion serait que dans le pire des cas, le tri par insertion binaire est O(n^2)complexe.

Voir également:

• tri par insertion à l'aide de la recherche binaire
• tri par insertion avec recherche binaire
• analyse du tri par insertion binaire
• tri d'insertion binaire et complexité

Ensuite, j'ai essayé de vérifier ses performances sur les listes inversées ( n,n-1,n-2,..,1) et alternées ( 0,n-1,1,n-2,2,n-3,...). Et je les ai adaptés (en utilisant le module matchgrowth ) à différents taux de croissance, cette partie n'est qu'une approximation. L'ordre inversé a été ajusté au temps polynomial, et l'ordre alterné a été ajusté au temps quasilinéaire

Le meilleur des cas est expliqué ici . Si la liste est déjà triée, alors même si nous ne faisons aucun échange, toutes les recherches binaires sont toujours en cours, ce qui conduit à O(n*log(n)).

Le code utilisé ici est disponible dans ce référentiel.