obere Grenze untere Schranke

Question

Was bedeutet es eine obere Grenze zu beweisen oder zu einem Algorithmus untere Grenze?

Answer 1

Proving eine obere Schranke bedeutet, dass Sie haben bewiesen, dass der Algorithmus verwenden nicht mehr als einige Begrenzung auf eine Ressource.

Proving eine untere Schranke bedeutet, dass Sie haben bewiesen, dass der Algorithmus verwenden nicht weniger als einige Begrenzung auf eine Ressource.

"Ressource" in diesem Zusammenhang könnte Zeit, Speicher, Bandbreite, oder etwas anderes sein.

Answer 2

Obere und untere Grenzen haben mit dem minimalen und maximalen „Komplexität“ eines Algorithmus zu tun (ich verwende dieses Wort bewusst, da sie eine sehr spezifische Bedeutung in Komplexitätsanalyse hat).

Nehmen wir zum Beispiel unser alter Freund, der Blase sortieren. In einem idealen Fall, in dem alle Daten, die bereits sortiert sind, wurde die Zeit, ist f (n) eine Funktion abhängig von n, die Anzahl der Elemente in der Liste. Das ist, weil Sie nur einen Durchlauf des Datensatz zu machen (mit Null-Swaps) Ihre Liste, um sicherzustellen, sortiert.

In einem besonders schlimmen Fall, wo die Daten in der entgegengesetzt zu der Reihenfolge sortiert werden Sie wollen, die Zeit, wird f (n ² ). Dies liegt daran, dass jeder Durchgang ein Element in die richtige Position bewegt, und Sie müssen n übergibt alle Elemente zu tun.

In diesem Fall sind die oberen und unteren Grenzen sind unterschiedlich, auch wenn die Groß-O Komplexität bleibt gleich.

Als Nebenwirkung, die Blase Art viel geschmähte ist (in der Regel aus guten Gründen), aber es kann sinnvoll unter bestimmten Umständen machen. Ich benutze es tatsächlich in einer Anwendung, wo der Großteil der Daten bereits sortiert ist und nur ein oder zwei Elemente neigen dazu, zu einem Zeitpunkt, zu dem Ende der Liste hinzugefügt werden. Für ein Element hinzufügen, und mit einer rückwärtig gerichteter Blase sortieren, können Sie die neue Liste garantieren in einem Durchgang sortiert werden. Das zeigt das untere Grenze Konzept.

In der Tat könnte man eine Optimierung der Blase Art machen, die die untere Schranke f setzt (1), indem Sie einfach ein zusätzliches Datum bereitstellt, das anzeigt, ob die Liste sortiert ist. Sie würden diesen Satz nach dem Sortieren und es löschen, wenn bis zum Ende ein Element hinzugefügt wird.

Answer 3

Was auch immer verpflichtet, die (obere oder untere) sind wir immer reden über den Worst-Case-Eingang, die wir in Betracht ziehen. Zum Beispiel bei der Sortierung, gehen wir davon aus, dass die Worst-Case ist eine unsortierte Eingabeliste.

Mein Verständnis ist, dass Probleme eine untere Grenze haben. Zum Beispiel, sagen wir, daß der von vergleichsbasierten gebunden unteren Sortierung wird Omega \ (n log n); wir machen keine Annahmen darüber, was insbesondere vergleichsbasierten Sortier Algorithmus die wir verwenden. Was auch immer der Algorithmus (Mergesort, schnelle Art, etc.), können wir nicht besser tun dies als Schranke von \ Omega (n log n). Untere Schranken sagen uns, intuitiv, wie schwer ein bestimmtes Problem ist.

Wenn wir über einen bestimmten sprechen Algorithmus , dann reden wir über obere Schranken. Zum Beispiel, sagen wir, daß die obere Grenze der Blasensortierung ist O (n ^ 2) und die obere Grenze des Verschmelzungssortier ist O (n log n). Obere Schranken, intuitiv, erzählen Sie uns, wie gut ein bestimmtes Algorithmus ist, das Problem zu lösen.