Pour le tri d'inversion insertion!

Question

une question que je trouve dans le Wikipedia (je veux apprendre genre des algorithmes très bien). Quoi qu'il en soit, c'est une question - me pourriez-vous expliquer comment je peux le montrer

Exercice:. Montrer que l'algorithme d'insertion Trier (A) fonctionne en temps O (n + I) étant donné que j'est le nombre d'inversions dans le tableau A

Answer 1

Regardez les sections de Implementation et Analysis de cette .

Considérons l'algorithme présenté il y a:

private static void insertionsort()
{
    int i, j, t;
    for (i=1; i<n; i++)
    {
        j=i;
        t=a[j];
        while (j>0 && a[j-1]>t)
        {
            a[j]=a[j-1];
            j--;
        }
        a[j]=t;
    }
}

Notez que la boucle while se poursuit pour les itérations de v[i], où v[i] est le nombre de renversements causés par l'élément i. Cela devrait faire la preuve, il très facile à comprendre.