Ermittlung der Worst-Case-Komplexität eines Algorithmus

Question

Kann jemand mir bitte erklären, wie man das Worst-Case-Komplexität eines Algorithmus bestimmen kann. Ich weiß, dass wir die Gleichung W (n) = max {t (I) | I Element von D) verwenden müssen, wobei D die Menge der Eingaben der Größe n ist. Errechne ich die Anzahl der Operationen, die für jedes Element I ausgeführt werden, und nehme dann dessen Maximum an? Welchen einfacheren Weg gibt es, dies zu erreichen?

Answer 1

aus der Gleichung Ab nach hinten ein wenig zu denken. Was Sie wirklich interessieren, ist die Skalierbarkeit, oder was wird es tun, wenn Sie die Größe der Eingabe erhöhen.

Wenn Sie nur eine Schleife haben, zum Beispiel, haben Sie eine O (n) Zeit Komplexität Algorithmus. Wenn Sie jedoch eine Schleife innerhalb einer anderen Schleife haben, wird sie zu O (n^2), weil sie nun viele Dinge für jede Eingabe der Größe n tun muss.

Wenn Sie über schlimmsten Fall zu sprechen, Sie sprechen in der Regel über nicht deterministische Algorithmen, in dem Sie eine Schleife haben könnten, die vorzeitig stoppen kann. Was Sie dafür tun möchten, ist das Schlimmste anzunehmen und vorzugeben, dass die Schleife so spät wie möglich stoppt. Also, wenn wir haben:

for (int i = 0; i < n; i ++) { für (int j = 0; j < n; j ++) { if (rand()> 0,5) j = n; } }

Wir würden sagen, dass das Worst-Case-O (n^2). Obwohl wir wissen, dass es sehr wahrscheinlich ist, dass die mittlere Schleife früh ausbricht, suchen wir nach der schlechtesten Leistung.

Answer 2

Diese Gleichung ist eher eine Definition als ein Algorithmus.

Hat den Algorithmus in Frage kümmert sich um etwas anderes als die Größe seines Eingangs? Wenn nicht, dann ist die Berechnung von W (n) "einfach".

Ist dies der Fall, versuchen Sie mit einem pathologischen Eingang zu kommen. Zum Beispiel kann es bei Quicksort ziemlich offensichtlich sein, dass eine sortierte Eingabe pathologisch ist, und Sie können etwas zählen, um zu sehen, dass es O (n^2) Schritte benötigt. An diesem Punkt können Sie entweder

1. Zeigen Sie, dass Sie Ihre Eingabe ist „maximal“ pathologische
2. Exhibit eine passende obere auf der Laufzeit auf jeden Eingang gebunden

Beispiel # 1:

Bei jedem Durchlauf von Quicksort wird der Drehpunkt an die richtige Stelle gesetzt und dann auf die beiden Teile rekursiv gesetzt. (handwave alert) Der schlimmste Fall ist, den Rest des Arrays auf einer Seite des Pivot zu haben. Eine sortierte Eingabe erreicht dies.

Beispiel # 2:

Jeder Durchlauf von quicksort versetzt den Drehpunkt in der richtigen Stelle, so dass es nicht mehr als O (n) hindurchgeht. Jeder Durchgang erfordert nicht mehr als O (n) Arbeit. Daher kann keine Eingabe dazu führen, dass Quicksort mehr als O (n^2) benötigt.

In diesem Fall ist # 2 viel einfacher.