Worst Case Zeitkomplexität für einen Algorithmus

Question

Was ist die Worst Case Zeitkomplexität t (n): - Ich lese dieses Buch über Algorithmen und als Beispiel wie die T (n) zu bekommen .... wie die Auswahl Sortieralgorithmus

---

Wie, wenn ich den Umgang mit dem SelectionSort (A [0..n-1])

//sorts a given array by selection sort
//input: An array A[0..n - 1] of orderable elements.
//output: Array A[0..n-1] sorted in ascending order

Lassen Sie mich eine Pseudo-Code schreiben

for i <----0 to n-2 do
  min<--i
for j<--i+1 to n-1 do
   ifA[j]<A[min] min <--j
swap A[i] and A[min]

-------- Ich schreibe es in C # zu ---------------

private int[] a = new int[100];

// number of elements in array
private int x;

// Selection Sort Algorithm
public void sortArray()
{
  int i, j;
  int min, temp;

  for( i = 0; i < x-1; i++ )
  {
    min = i;

    for( j = i+1; j < x; j++ )
    {
      if( a[j] < a[min] )
      {
        min = j;
      }
    }

    temp = a[i];
    a[i] = a[min];
    a[min] = temp;
  }
}

==================

Nun, wie die t erhalten (n) oder als bekannt schlimmste Fall Zeit Komplexität

Answer 1

sara jons Der Folien-Set, das Sie verwiesen haben - und der Algorithmus darin

Die Komplexität für jede primitive / atomare Operation in der for-Schleife gemessen wird

for(j=0 ; j<n ; j++)
{
    //...    
}

Die Folien diese Schleife als 2n + 2 aus den folgenden Gründen bewerten:

Der Anfangssatz von j = 0 (+1 op)

Der Vergleich von j

Die Zunahme von j ++ (n ops)

Die letzte Bedingung zu prüfen, ob j

Zweitens ist der Vergleich innerhalb der for-Schleife

if(STudID == A[j])      
    return true;

Dies ist als n ops bewertet. Somit ist das Ergebnis, wenn Sie +1 op addieren, n ops, n ops, +1 op, n ops = 3n + 2 Komplexität. So T (n) = 3n + 2

Erkennen, dass T (n) ist nicht die gleiche wie O (n).

Answer 2

Das wäre O (n ^ 2).

Der Grund ist, dass Sie eine einzelne for-Schleife für Schleife in eine andere geschachtelt haben. Die Laufzeit für die inneren for-Schleife, O (n), geschieht für jede Iteration der äußeren for-Schleife, was wiederum O (n). Der Grund, jedes von diesen einzeln steht für O (n) ist, weil sie eine lineare Zeitmenge der Größe des Eingangs gegeben nehmen. Je größer der Eingang desto länger dauert es auf einer linearen Skala, n.

Mathe Um herauszufinden, was in diesem Fall trivial ist, nur mehrere, die Komplexität der inneren Schleife durch die Komplexität der äußeren Schleife. n * n = n ^ 2. Denn denken Sie daran, für jedes n in der äußeren Schleife, müssen Sie wieder n für die innere tun. Zur Klarstellung: n-mal für jeden n.

O (n * n).

O (n ^ 2)

Answer 3

Übrigens, sollten Sie nicht Komplexität mischen (durch Groß-O) und die T-Funktion. Die T-Funktion ist die Anzahl der Schritte der Algorithmus für einen gegebenen Eingang zu durchlaufen hat.

So ist der Wert von T (n) die tatsächliche Anzahl der Schritte, während O (etwas) eine Komplexität bezeichnet. Durch das herkömmliche abuse Notations, T (n) = O (f (n)) bedeutet, dass die Funktion T (n) von höchstens die gleiche Komplexität wie eine andere Funktion f (n), die in der Regel wird die einfachste mögliche Funktion sein, seine Komplexitätsklasse.

Dies ist nützlich, weil es uns auf das große Bild konzentrieren: Wir können jetzt zwei Algorithmen leicht vergleichen, die durch einen Blick auf, wie sie durchführen „auf lange Sicht“ sehr unterschiedlich aussehende T (n) Funktionen haben <. / p>

Answer 4

Eine weitere Doktor-comp Rückblende hier.

Zunächst wird die T-Funktion ist einfach die Zeit (in der Regel in einer Anzahl von Schritte , über die weiter unten noch mehr) ein Algorithmus zur Durchführung einer Aufgabe übernimmt. Was für ein „Schritt“ wird, wird etwas durch die Verwendung definiert; zum Beispiel ist es üblich, die Anzahl der Vergleiche in Sortieralgorithmen, aber die Anzahl der Elemente in Suchalgorithmen gesucht zu zählen.

Wenn wir über die Worst-Case-Zeit einen Algorithmus zu sprechen, drücken wir in der Regel, dass mit „Big-O-Notation“. So wird zum Beispiel, man hört, dass Blase Art nimmt O (n²) Zeit. Wenn wir O-Notation verwenden, sind, was wir wirklich sagen will, ist, dass das Wachstum einer Funktion - in diesem Fall T - nicht schneller ist als das Wachstum einiger anderer Funktion mal eine Konstante. Das ist

T (n) = O (n²)

Legeeinrichtung zum n , egal wie groß, gibt es eine Konstante K , für die T (n) ≤ kn² . Ein Punkt von einiger confustion hier ist, dass wir das Zeichen „=“ in einer überladenen Art und Weise verwenden: es ist nicht die beide sind, bedeutet gleich in dem numerischen Sinne, nur, dass wir sagen < em> T (n) ist begrenzt durch kn² .

Im Beispiel in Ihrer erweiterten Frage, es sieht aus wie sie die Anzahl der Vergleiche in der for-Schleife und im Test sind zählen; es würde helfen, den Kontext und die Frage der Lage sein, sie zu beantworten, um zu sehen. Auf jeden Fall zeigt es allerdings, warum wir Big-O-Notation mögen: W (n) hier O (n) . (Beweis: Es existiert eine Konstante k, nämlich 5, für die W (n) ≤ k (3N) +2 folgt durch die Definition von O (n) . ).

Wenn Sie mehr darüber erfahren möchten, konsultieren jede gute Algorithmen Text, zB Einführung in Algorithmen von Cormen et al.

Answer 5

Schreib Pseudo-Codes suchen, einfügen und Schüler Informationen aus der Hash-Tabelle zu entfernen. berechnen die beste und im schlimmsten Fall Zeit Komplexität

Answer 6

3n + 2 ist die richtige Antwort, so weit wie die Schleife geht. Bei jedem Schritt der Schleife, 3 atomare Operationen werden durchgeführt. j ++ sind eigentlich zwei Operationen, nicht ein. und j