Berechnen Big Theta Notation Bubble Sortieren

Question

Ich versuche, die Theta-Notation für Bubble-Art zu berechnen, aber ich bleibe stecken. In Anbetracht dieses Verfahren (Pseudocode):

procedure BUBBLE_SORT(A,n) { 
    array A(1 to n) 
    for (int i = 1; i <= n; i++) { 
     for(int j = 1; j <= n-1; j++) { 
      if(A[j] > A[j+1] { 
       //swap(A(j), A(j+1)) 
      } 
     } 
    } 
} 

konnte ich den schlimmsten Fall bekommen mit Sigma-Notation Laufzeit zu sein:

(n^2 - n)/2

Für die besten Falllaufzeit, folgte ich meinem Buch und tat dies:

Gegeben p (n) = (n^2 - n)/2, wir behaupten, dass p (n) = Θ (n^2). Um dies zu beweisen wir zeigen, dass für einige Konstanten c1, c2 und n0:

C1n^2 < = (n^2/2) + (n/2) < = C2n^2

Division beiden Seiten durch n^2, erhalten wir:

C1 < = (1/2) + (1/2n) < = C2

Dies ist, wo ich verloren habe. In dem Buch wählte der Autor einige Zahlen aus, stöpselte sie ein und sagte: "Daraus folgt, dass p (n) = Θ (n^2)"

Woher weiß ich, welche Nummern angeschlossen werden sollen? Kann ich einfach irgendwelche Nummern anschliessen? Und wenn diese Zahlen zur Ungleichung passen, bedeutet das, dass ich sofort sagen kann, dass der Algorithmus Θ (n^2) ist?

Vielen Dank!

Answer 1

Ein allgemeiner Ansatz, dem ich folge, ist die Überprüfung der Standardkomplexitätswerte. wie 2^(2^n) > n! > 4^n > 2^n > n^2 > nlogn > log(n!) > n > sqrt(n) > (logn)^2 > logn > loglogn > 1

Auf diese Weise nur Plugin n^2 Jetzt, wenn es erfüllt dann betrachten Sie Werte weniger als das. Auf diese Weise können Sie die enge Bindung bekommen. Wenn es nicht genügt, geh für höhere Werte. Dies hilft in vielen Fällen.

Answer 2

Denken Sie daran, dass es sich um asymptotisches Verhalten handelt.

Wir können darüber nachdenken, ein Spiel zu spielen: Ihr Ziel ist es zu beweisen, dass eine bestimmte Grenze gilt. Das Spiel läuft so ab: Zunächst wählt man die Konstanten C1 und C2. Dann wähle ich einen beliebigen n. Wenn ich das so machen kann, dass es die Ungleichheit verletzt, verlierst du (die Grenze hält nicht). Wenn es keinen Weg gibt, kann ich das tun, auch wenn Sie nicht mehr die C1 und C2 ändern können, die Sie ausgewählt haben, gewinnen Sie (die Grenze ist korrekt).

ES bei der Gleichung in Frage ist nun sehen lassen:

C1 < = (1/2) + (1/2n) < = C2

Da n eine ganze Zahl ist (am Ende ist, sie repräsentiert die Anzahl der Elemente in Ihrem Array), gibt es einen bestimmten kleinsten Wert: n = 1. Lassen Sie uns ersetzen, dass in:

(1/2) + (1/2) = 1

Okay, jetzt, dass ein Anfang. Mal sehen, was passiert, wenn ich n größer mache ... Beachten Sie, dass die n nur im Nenner erscheint.Also kann ich deine Grenze nicht durcheinander bringen, indem ich sie willkürlich groß mache. Der schlechteste Fall für Sie ist eigentlich für kleine Werte von n. Bei größeren Werten von n wird der zweite Teil des Produkts kleiner und verschwindet schließlich. Für die Begrenzung n->inf erhalten wir:

lim n-> inf (1/2) + (1/2n)

(1/2) + lim n-> inf (1/2n) = (1 2 /) + 0 = 1/2

Also, was das sagt uns, je nachdem, was Wert von n ich wähle, der resultierende Wert wird immer im Bereich 1/2 bis 1 (da die Gleichung linear ist in n Diese beiden Stichproben reichen aus, um das zu zeigen, bei komplexeren Gleichungen erfordert die Festlegung der Grenzen normalerweise etwas mehr Arbeit.

Mit diesem Wissen können Sie C1 und C2 in einer Weise auswählen, dass ich das Spiel nie gewinnen kann?

Answer 3

Wir interessieren uns für C1 und C2 solche zu finden, daß für jeden n >= 1 gilt:

C1 <= (1/2) + (1/2n) <= C2

Eine gute Wahl für C1 = 1/2 (aber jeder streng positiven Wert kleiner als das ist auch gültig, zB C1 = 0.1).

Eine gute Wahl für C2 = 1 (aber jeder Wert größer als das ist auch gültig). Der Wert C2 = 1 ist in Ordnung, weil der Ausdruck 1/2 + 1/2n abnimmt, wenn n größer wird, daher ist der maximale Wert für n = 1.

---

Eine letzte Bemerkung: Es wurde oben gezeigt, dass es einige Konstanten C1 und C2, für welche die Ungleichheiten immer, wenn n >= 1 halten. Wenn es bequemer wäre, hätten wir uns auf Werte von n konzentrieren können, beginnend mit einem anderen konstanten Wert (anstelle von 1, beispielsweise). Wichtig ist, dass es einige Konstanten C1 und C2 gibt, so dass beide Ungleichungen gelten, wenn n groß genug ist.