In der Informatik drücken beste, schlechteste und durchschnittliche Fälle eines gegebenen Algorithmus aus, was der Quellengebrauch mindestens höchstens und durchschnittlich beziehungsweise ist. Gewöhnlich ist die Quelle, die wird betrachtet, Laufzeit, aber es konnte auch Gedächtnis oder andere Mittel sein.

In Realtime rechnend, ist die Grenzfall-Ausführungszeit häufig der besonderen Sorge, da es wichtig ist zu wissen, wie viel Zeit im Grenzfall erforderlich sein könnte, um zu versichern, dass der Algorithmus immer rechtzeitig fertig sein wird.

Durchschnittliche Leistung und Grenzfall-Leistung sind in der Algorithmus-Analyse am meisten verwendet. Weniger weit gefunden ist Leistung des besten Falls, aber sie hat wirklich Nutzen: Zum Beispiel, wo die besten Fälle von individuellen Aufgaben bekannt sind, können sie verwendet werden, um die Genauigkeit einer gesamten Grenzfall-Analyse zu verbessern. Computerwissenschaftler verwenden probabilistic Analyse-Techniken, besonders erwarteten Wert, um erwartete Laufzeiten zu bestimmen.

Die Begriffe werden in anderen Zusammenhängen gebraucht; zum Beispiel das schlechteste - und Ergebnis des besten Falls eines geplanten - für die Epidemie, Grenzfall-Temperatur, zu der ein elektronisches Stromkreis-Element usw. ausgestellt wird. Wo Bestandteile der angegebenen Toleranz verwendet werden, müssen Geräte entworfen werden, um richtig mit der Grenzfall-Kombination der Toleranz und Außenbedingungen zu arbeiten.

Leistung des besten Falls für den Algorithmus

Die Begriff-Leistung des besten Falls wird in der Informatik verwendet, um den Weg eines Algorithmus zu beschreiben, benimmt sich unter optimalen Bedingungen. Zum Beispiel kommt der beste Fall für eine einfache geradlinige Suche auf einer Liste vor, wenn das gewünschte Element das erste Element der Liste ist.

Entwicklung und Wahl von Algorithmen basieren selten auf der Leistung des besten Falls: Die meisten akademischen und kommerziellen Unternehmen interessieren sich mehr für die Besserung durchschnittlicher Leistung und Grenzfall-Leistung. Algorithmen können auch trivial modifiziert werden, um gute Laufzeit des besten Falls durch hart codierende Lösungen eines begrenzten Satzes von Eingängen zu haben, das Maß fast sinnlos machend.

Grenzfall gegen die Leistung des durchschnittlichen Falls

Grenzfall-Leistungsanalyse und durchschnittliche Fall-Leistungsanalyse haben einige Ähnlichkeiten, aber verlangen in der Praxis gewöhnlich verschiedene Werkzeuge und Annäherungen.

Die Bestimmung, was durchschnittlicher Eingang bedeutet, ist und häufig schwierig, dass durchschnittlicher Eingang Eigenschaften hat, die es schwierig machen, mathematisch zu charakterisieren (denken Sie zum Beispiel, Algorithmen, die entworfen werden, um auf Schnuren des Textes zu funktionieren). Ähnlich, selbst wenn eine vernünftige Beschreibung eines besonderen "durchschnittlichen Falls" (der wahrscheinlich nur für etwas Gebrauch des Algorithmus anwendbar sein wird) möglich ist, neigen sie dazu, schwieriger hinauszulaufen, Gleichungen zu analysieren.

Grenzfall-Analyse hat ähnliche Probleme: Es ist normalerweise unmöglich, den genauen größten anzunehmenden Unfall zu bestimmen. Statt dessen wird ein Drehbuch solch betrachtet, dass es mindestens so schlecht ist wie der Grenzfall. Zum Beispiel, wenn man einen Algorithmus analysiert, kann es möglich sein, den längstmöglichen Pfad durch den Algorithmus zu finden (durch das Betrachten der maximalen Zahl von Schleifen, zum Beispiel), selbst wenn es nicht möglich ist, den genauen Eingang zu bestimmen, der diesen Pfad erzeugen würde (tatsächlich, kann solch ein Eingang nicht bestehen). Das gibt eine sichere Analyse (der Grenzfall wird nie unterschätzt), aber derjenige, der, da pessimistisch ist, kann es keinen Eingang geben, der diesen Pfad verlangen würde.

Wechselweise kann ein Drehbuch, das, wie man denkt, in der Nähe von (aber nicht notwendigerweise schlechter ist als) der echte Grenzfall, betrachtet werden. Das kann zu einem optimistischen Ergebnis führen, bedeutend, dass die Analyse wirklich den wahren Grenzfall unterschätzen kann.

In einigen Situationen kann es notwendig sein, eine pessimistische Analyse zu verwenden, um Sicherheit zu versichern. Häufig jedoch kann eine pessimistische Analyse zu pessimistisch sein, so kann eine Analyse, die näher am echten Wert wird, aber optimistisch sein kann (vielleicht mit etwas bekannter niedriger Wahrscheinlichkeit des Misserfolgs) eine viel praktischere Annäherung sein.

man Algorithmen analysiert, die häufig eine kleine Zeit nehmen, um zu vollenden, aber eine viel größere Zeit regelmäßig zu verlangen, kann amortisierte Analyse verwendet werden, um die Grenzfall-Laufzeit über (vielleicht unendlich) Reihe von Operationen zu bestimmen. Diese amortisierten Grenzfall-Kosten können an den durchschnittlichen Fall-Kosten viel näher sein, während sie noch eine versicherte obere Grenze auf der Laufzeit zur Verfügung stellen.

Die Grenzfall-Analyse ist mit der Grenzfall-Kompliziertheit verbunden.

Praktische Folgen

Viele Probleme mit der schlechten Grenzfall-Leistung haben gute Leistung des durchschnittlichen Falls. Für Probleme wollen wir lösen, das ist ein gutes Ding: Wir können hoffen, dass die besonderen Beispiele, über die wir uns sorgen, durchschnittlich sind. Für die Geheimschrift ist das sehr schlecht: Wir wollen typische Beispiele eines kryptografischen Problems, hart zu sein. Hier können Methoden wie zufälliger self-reducibility für einige spezifische Probleme verwendet werden zu zeigen, dass der Grenzfall nicht härter ist als der durchschnittliche Fall, oder gleichwertig, dass der durchschnittliche Fall nicht leichter ist als der Grenzfall.

Andererseits haben einige Algorithmen wie Hash-Tabellen sehr schlechte Grenzfall-Handlungsweisen, aber eine gut schriftliche Hash-Tabelle der genügend Größe wird den Grenzfall statistisch nie geben; die durchschnittliche Zahl von durchgeführten Operationen folgt einer Exponentialzerfall-Kurve, und so wird die Durchlaufzeit einer Operation statistisch begrenzt.

Beispiele

• Geradlinige Suche auf einer Liste von n Elementen. Im Grenzfall muss die Suche jedes Element einmal besuchen. Das geschieht, wenn der Wert, der wird sucht, entweder das letzte Element in der Liste ist, oder nicht in der Liste ist. Jedoch, durchschnittlich, ist das Annehmen des gesuchten Werts in der Liste, und jedes Listenelement wird ebenso wahrscheinlich der gesuchte Wert sein, die Suche besucht nur n/2 Elemente.
• Einfügungssorte hat für eine Liste von n Elementen, angenommen gegolten, alles verschieden zu sein, und am Anfang in der zufälligen Ordnung. Durchschnittlich, Hälfte der Elemente in einer Liste A... A sind weniger als Element A, und Hälfte ist größer. Deshalb vergleicht sich der Algorithmus j+1-st Element, das im Durchschnitt mit der Hälfte der bereits sortierten Subliste, so t = j/2 einzufügen ist. Die resultierende Laufzeit des durchschnittlichen Falls gut zu laufen, gibt eine quadratische Funktion der Eingangsgröße gerade wie die Grenzfall-Laufzeit nach.
• Schnellsortierung hat für eine Liste von n Elementen, wieder angenommen gegolten, alles verschieden zu sein, und am Anfang in der zufälligen Ordnung. Dieser populäre Sortieren-Algorithmus hat eine Leistung des durchschnittlichen Falls von O (n loggen n), der zum Bilden davon ein sehr schneller Algorithmus in der Praxis beiträgt. Aber in Anbetracht eines Grenzfall-Eingangs baut sich seine Leistung zu O (n) ab.

Siehe auch

• Das Sortieren des Algorithmus - ein Gebiet, wo es sehr viel Leistungsanalyse von verschiedenen Algorithmen gibt.
• Grenzfall-Stromkreis-Analyse
• Geglättete Analyse
• Zwischenraum begrenztes Element