Bewertung der durchschnittlichen Zeitkomplexität eines gegebenen Bubblesort -Algorithmus.

Question

In Anbetracht dieses Pseudo-Code eines Bubblesorts:

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

Was wären die grundlegenden Ideen, die ich beachten müsste, um die durchschnittliche Zeitkomplexität zu bewerten? Ich habe bereits die Berechnung der schlimmsten und besten Fälle erreicht, aber ich bin festgedacht, wie ich die durchschnittliche Komplexität der inneren Schleife bewerten kann, um die Gleichung zu bilden.

Die schlimmste Fallgleichung ist:

$$ sum_ {i = 0}^n links ( sum_ {j = 0}^{n -(i + 1)} o (1) + o (1) rechts) = o ( frac {n ^2} {2} + frac {n} {2}) = o (n^2) $$

in dem das innere Sigma die innere Schleife darstellt und das äußere Sigma die äußere Schleife darstellt. Ich denke, dass ich beide Sigmas aufgrund des "If-Then-Break" -Clauses ändern muss, was das äußere Sigma beeinflusst, aber auch aufgrund der If-Klausel in der inneren Schleife, die die während einer Schleife durchgeführten Maßnahmen beeinflusst (4 Aktionen + 1 Vergleich, wenn wahr, sonst nur 1 Vergleich).

Zur Klarstellung zum Begriff Durchschnittszeit: Dieser Sortieralgorithmus erfordert unterschiedliche Zeit in verschiedenen Listen (derselben Länge), da der Algorithmus möglicherweise mehr oder weniger Schritte durch/innerhalb der Schleifen benötigt, bis die Liste vollständig in Ordnung ist. Ich versuche, einen mathematischen (nicht statistischen Weg) der Bewertung des Durchschnitts der erforderlichen Runden zu finden.

Dafür erwarte ich, dass jede Ordnung die gleiche Möglichkeit hat.

Answer 1

Für Länge von Länge $ N $ bedeutet der Durchschnitt normalerweise, dass Sie mit einer einheitlichen Verteilung auf alle $ n! $ Permutationen von [$ 1 $, .., $ n $] beginnen müssen .

Ihre durchschnittliche Komplexität wäre dann die Summe der Anzahl der Schritt für alle Listen geteilt durch $ n! $.

Für eine bestimmte Liste $ $ (x_i) _i $ ist die Anzahl der Schritte Ihres Algorithmus $ nd $, wobei $ d $ die größte Entfernung zwischen einem Element $ x_i $ und seinem rechtmäßigen Standort $ i $ ist (aber nur, wenn es muss Nach links bewegen), das ist $ max_i ( max (1, i-x_i)) $.

Dann machen Sie die Mathematik: Für jede $ d $ Finden Sie die Nummer $ C_D $ von Listen mit dieser speziellen maximalen Entfernung, dann lautet der erwartete Wert von $ d $:

$$ frac1 {n!} sum_ {d = 0}^n { dc_d} $$

Und das sind die grundlegenden Gedanken ohne den schwierigsten Teil, der $ C_D $ findet. Vielleicht gibt es jedoch eine einfachere Lösung.

Bearbeiten: "erwartet" hinzugefügt "

Answer 2

Denken Sie daran, dass ein Paar $ (a [i], a [j]) $ (resp. $ (I, j) $) invertiert ist, wenn $ i <j $ und $ a [i]> A [j] $.

Unter der Annahme, dass Ihr Algorithmus für jede Inversion einen Swap durchführt, hängt die Laufzeit Ihres Algorithmus von der Anzahl der Inversionen ab.

Die Berechnung der erwarteten Anzahl von Inversionen in einer einheitlichen zufälligen Permutation ist einfach:

Sei $ p $ eine Permutation und sei $ r (p) $ umgekehrt von $ p $. Zum Beispiel, wenn $ p = 2,1,3,4 $ dann $ R (P) = 4,3,1,2 $.

Für jedes Paar von Indizes $ (i, j) $ gibt es eine Inversion in genau einem von entweder $ P $ oder $ R (P) $.

Da die Gesamtzahl der Paare $ n (n-1)/2 $ beträgt und die Gesamtzahl und jedes Paar genau die Hälfte der Permutationen invertiert, sofern alle Permutationen gleich wahrscheinlich sind, ist die erwartete Anzahl der Inversionen:

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

Answer 3

Anzahl der Swaps <Anzahl der Iterationen (sowohl in optimiertem als auch im einfachen Bubble Case -Szenario)

Anzahl der Inversionen = Anzahl der Swaps.

Daher Anzahl der Iterationen> $ frac {n (n-1)} {4} $

Somit beträgt die durchschnittliche Fallkomplexität $ Omega (n^2) $. Da der Durchschnittsfall jedoch den schlimmsten Fall nicht überschreiten kann, erhalten wir, dass es $ o (n^2) $ ist,

Dies gibt uns: Durchschnittszeit = $ theta (n^2) $

(Zeitkomplexität = Anzahl der Iteration Nr. Iterationen> Nein. Von Swaps)

Answer 4

In diesem Dokument erreichte die durchschnittliche Zeitkomplexität der Blasensorte O (NLog (n))!http://algo.inria.fr/flajolet/publications/vifl90.pdf