Inversion zum Einsetzen Art!

Question

Dies ist eine Frage fand ich in der Wikipedia Website (Ich möchte sehr Sortieralgorithmen lernen Gut). Wie auch immer, dies ist eine Frage - könnten Sie mir erklären, wie ich es zeigen kann,

. Übung: Zeigen Sie, dass Algorithmus Insertion Sort (A) läuft in der Zeit O (n + I) gegeben, dass ich die Anzahl der Inversionen in der Anordnung A

Answer 1

Schauen Sie sich die Implementation und Analysis Abschnitte von diese .

Betrachten der Algorithmus präsentiert es:

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;
    }
}

Beachten Sie, dass die while-Schleife läuft für v[i] Iterationen, wo v[i] ist die Anzahl der Inversionen verursacht durch das Element i. Dies sollte den Beweis es sehr leicht verständlich machen.