In der Informatik ist die Analyse von Algorithmen der Entschluss vom Betrag von Mitteln (wie Zeit und Lagerung) notwendig, um sie durchzuführen. Die meisten Algorithmen werden entworfen, um mit Eingängen der willkürlichen Länge zu arbeiten. Gewöhnlich werden die Leistungsfähigkeit oder Laufzeit eines Algorithmus als eine Funktion festgesetzt, die die Eingangslänge mit der Zahl von Schritten (Zeitkompliziertheit) oder Speicherelemente (Raumkompliziertheit) verbindet.

Algorithmus-Analyse ist ein wichtiger Teil einer breiteren rechenbetonten Kompliziertheitstheorie, die theoretische Schätzungen für die Mittel zur Verfügung stellt, die durch jeden Algorithmus erforderlich sind, der ein gegebenes rechenbetontes Problem behebt. Diese Schätzungen gewähren einen Einblick in angemessene Richtungen der Suche nach effizienten Algorithmen.

In der theoretischen Analyse von Algorithmen ist es üblich, ihre Kompliziertheit im asymptotischen Sinn zu schätzen, d. h., die Kompliziertheitsfunktion für den willkürlich großen Eingang zu schätzen. Große O Notation, Omega-Notation und theta Notation sind an dieses Ende gewöhnt. Zum Beispiel, wie man sagt, läuft binäre Suche in mehreren Schritten, die zum Logarithmus der Länge der Liste proportional sind, die, oder in O (Klotz (n)), umgangssprachlich "in der logarithmischen Zeit" wird sucht. Gewöhnlich asymptotische Schätzungen werden verwendet, weil sich verschiedene Durchführungen desselben Algorithmus in der Leistungsfähigkeit unterscheiden können. Jedoch ist die Wirksamkeit irgendwelcher zwei "angemessenen" Durchführungen eines gegebenen Algorithmus durch einen unveränderlichen multiplicative Faktor genannt eine verborgene Konstante verbunden.

Genau (nicht asymptotisch) können Maßnahmen der Leistungsfähigkeit manchmal geschätzt werden, aber sie verlangen gewöhnlich bestimmte Annahmen bezüglich der besonderen Durchführung des Algorithmus, genannt Modell der Berechnung. Ein Modell der Berechnung kann in Bezug auf einen abstrakten Computer, z.B, Maschine von Turing, und/oder durch das Verlangen definiert werden, dass bestimmte Operationen in der Einheitszeit durchgeführt werden.

Zum Beispiel, wenn die sortierte Liste, auf die wir binäre Suche anwenden, n Elemente hat, und wir versichern können, dass jeder lookup eines Elements in der Liste in der Einheitszeit, dann am grössten Teil des Klotzes n + 1mal getan werden kann, wenn Einheiten erforderlich sind, um eine Antwort zurückzugeben.

Kostenmodelle

Zeitleistungsfähigkeitsschätzungen hängen davon ab, was wir definieren, um ein Schritt zu sein. Für die Analyse, um nützlich zur wirklichen Ausführungszeit zu entsprechen, wie man versichern muss, wird die Zeit, die erforderlich ist, einen Schritt durchzuführen, oben durch eine Konstante begrenzt. Man muss hier sorgfältig sein; zum Beispiel zählen einige Analysen eine Hinzufügung von zwei Zahlen als ein Schritt auf. Diese Annahme darf in bestimmten Zusammenhängen nicht bevollmächtigt werden. Zum Beispiel, wenn die an einer Berechnung beteiligten Zahlen willkürlich groß sein können, wie man nicht mehr annehmen kann, ist die durch eine einzelne Hinzufügung erforderliche Zeit unveränderlich.

Zwei Kostenmodelle werden allgemein verwendet:

• das gleichförmige Kostenmodell, auch genannt Maß des Uniform-gekosteten (und ähnliche Schwankungen), teilt unveränderliche Kosten zu jeder Maschinenoperation unabhängig von der Größe beteiligten der Zahlen zu
• das logarithmische Kostenmodell, auch genannt Maß der logarithmischen Kosten (und Schwankungen davon), teilt Kosten zu jeder zur Zahl von beteiligtem von Bit proportionalen Maschinenoperation zu

Der Letztere ist beschwerlicher, um zu verwenden, so wird es nur, wenn notwendig, zum Beispiel in der Analyse von Arithmetik-Algorithmen der willkürlichen Präzision, wie diejenigen verwendet, die in der Geheimschrift verwendet sind.

Ein Stichpunkt, der häufig überblickt wird, ist das veröffentlichte niedrigere Grenzen für Probleme werden häufig für ein Modell der Berechnung gegeben, die mehr eingeschränkt wird als der Satz von Operationen, die Sie in der Praxis verwenden konnten und deshalb es Algorithmen gibt, die schneller sind als, was möglich naiv gedacht würde.

Laufzeitanalyse

Laufzeitanalyse ist eine theoretische Klassifikation, die schätzt und die Zunahme in der Laufzeit (oder Durchlaufzeit) von einem Algorithmus als seine Eingangsgröße (gewöhnlich angezeigt als n) Zunahmen voraussieht. Laufzeitleistungsfähigkeit ist ein Thema vom großen Interesse an der Informatik: Ein Programm kann Sekunden, Stunden oder sogar Jahre nehmen, um zu beenden, durchzuführen, abhängig von dem Algorithmus es durchführt (sieh auch Leistungsanalyse, die die Analyse einer Durchlaufzeit eines Algorithmus in der Praxis ist).

Mängel der empirischen Metrik

Da Algorithmen mit der Plattform unabhängig sind (d. h. ein gegebener Algorithmus auf einer willkürlichen Programmiersprache auf einem willkürlichen Computer durchgeführt werden kann, der ein willkürliches Betriebssystem führt), gibt es bedeutende Nachteile zum Verwenden einer empirischen Annäherung, um die vergleichende Leistung eines gegebenen Satzes von Algorithmen zu messen.

Nehmen Sie als ein Beispiel ein Programm, das einen spezifischen Zugang in einer sortierten Liste der Größe n nachschlägt. Nehmen Sie an, dass dieses Programm auf dem Computer A, eine modernste Maschine, mit einem geradlinigen Suchalgorithmus, und auf dem Computer B, einer viel langsameren Maschine mit einem binären Suchalgorithmus durchgeführt wurde. Die Abrisspunkt-Prüfung in den zwei Computern, die ihre jeweiligen Programme führen, könnte etwas wie der folgende schauen:

Gestützt auf diesen Metrik würde es leicht sein, zum Beschluss zu springen, dass Computer A einen Algorithmus führt, der weit in der Leistungsfähigkeit als dieser von Computer B. However höher ist, wenn die Größe der Eingangsliste zu einer ausreichenden Anzahl vergrößert wird, wird dieser Beschluss drastisch demonstriert, um irrtümlicherweise zu sein:

Computer A, das geradlinige Suchprogramm führend, stellt eine geradlinige Wachstumsrate aus. Die Durchlaufzeit des Programms ist zu seiner Eingangsgröße direkt proportional. Die Verdoppelung der Eingangsgröße verdoppelt die Durchlaufzeit, die Eingangsgröße-Vierfachen die Durchlaufzeit und so weiter vervierfachend. Andererseits stellt Computer B, das binäre Suchprogramm führend, eine logarithmische Wachstumsrate aus. Die Verdoppelung der Eingangsgröße vergrößert nur die Durchlaufzeit durch einen Betrag (in diesem Beispiel, 25,000 ns). Wenn auch Computer A scheinbar eine schnellere Maschine ist, wird Computer B Computer an der Durchlaufzeit unvermeidlich übertreffen, weil es einen Algorithmus mit einer viel langsameren Wachstumsrate führt.

Ordnungen des Wachstums

Informell, wie man sagen kann, stellt ein Algorithmus eine Wachstumsrate auf der Ordnung einer mathematischen Funktion aus, wenn außer einer bestimmten Eingangsgröße n die Funktion f (n) Zeiten eine positive Konstante einen oberen gebunden oder Grenze für die Durchlaufzeit dieses Algorithmus zur Verfügung stellt. Mit anderen Worten, für eine gegebene Eingangsgröße n größer als ein n und ein unveränderlicher c, wird die Laufzeit dieses Algorithmus nie größer sein als c × f (n). Dieses Konzept wird oft mit der Großen O Notation ausgedrückt. Zum Beispiel, da die Durchlaufzeit der Einfügungssorte quadratisch wächst, als seine Eingangsgröße zunimmt, wie man sagen kann, ist Einfügungssorte des Auftrags O (n ²).

Große O Notation ist eine günstige Weise, den größten anzunehmenden Unfall für einen gegebenen Algorithmus auszudrücken, obwohl es auch verwendet werden kann, um den durchschnittlichen Fall - zum Beispiel auszudrücken, ist der größte anzunehmende Unfall für die Schnellsortierung O (n ²), aber die Durchlaufzeit des durchschnittlichen Falls ist O (n loggen n).

Empirische Ordnungen des Wachstums

Das Annehmen, das die Ordnung des Wachstums Macht-Regel, der Koeffizient eine Dose folgt, durch die Einnahme empirischer Maße gefunden werden (der Durchlaufzeit, sagen), an einigen Punkten der Problem-Größe und dem Rechnen so dass. Wenn die Ordnung des Wachstums tatsächlich der Macht-Regel folgt, der empirische Wert eines Willens bleiben unveränderlich an verschiedenen Reihen, und wenn nicht, es wird sich ändern - aber konnte noch zum Vergleich irgendwelcher zwei gegebenen Algorithmen betreffs ihrer empirischen lokalen Ordnungen des Wachstumsverhaltens dienen. Angewandt auf den obengenannten Tisch:

Es wird klar gesehen, dass der erste Algorithmus eine geradlinige Ordnung des Wachstums tatsächlich im Anschluss an die Macht-Regel ausstellt. Die empirischen Werte für den zweiten vermindern sich schnell, darauf hinweisend, dass er einer anderen Regel des Wachstums folgt und jedenfalls viel niedrigere lokale Ordnung des Wachstums (und Besserung weiter noch) empirisch hat als die erste.

Das Auswerten der Laufzeitkompliziertheit

Die Laufzeitkompliziertheit für den größten anzunehmenden Unfall eines gegebenen Algorithmus kann manchmal durch das Überprüfen der Struktur des Algorithmus und das Bilden einiger Vereinfachungsannahmen bewertet werden. Denken Sie den folgenden Pseudocode:

1 bekommen eine positive ganze Zahl vom Eingang

2 wenn n> 10

3 Druck "Könnte das eine Weile..." nehmen

4 weil ich = 1 zu n

5 für j = 1 zu mir

6 Druck i * j

7 Druck "Getan!"

Ein gegebener Computer wird eine getrennte Zeitdauer nehmen, um jede der mit dem Ausführen dieses Algorithmus beteiligten Instruktionen durchzuführen. Die spezifische Zeitdauer, um eine gegebene Instruktion auszuführen, wird sich ändern, abhängig von dem Instruktion durchgeführt wird, und welcher Computer es durchführt, aber auf einem herkömmlichen Computer wird dieser Betrag deterministisch sein. Sagen Sie, dass, wie man betrachtet, die im Schritt 1 ausgeführten Handlungen Zeit T verbrauchen, verwendet Schritt 2 Zeit T und so weiter.

Im Algorithmus oben werden Schritte 1, 2 und 7 nur einmal geführt. Für eine Grenzfall-Einschätzung sollte es angenommen werden, dass Schritt 3 ebenso geführt wird. So ist die Summe der Zeit, um Schritte 1-3 und Schritt 7 zu führen:

:

Die Schleifen in Schritten 4, 5 und 6 sind heikler, um zu bewerten. Der Außenschleife-Test im Schritt 4 wird (n + 1) durchführen

Zeiten (bemerken, dass ein Extraschritt erforderlich ist, für die Schleife, folglich n + 1 und nicht n Ausführungen zu enden), der T (n + 1) Zeit verbrauchen wird. Die innere Schleife wird andererseits durch den Wert von mir geregelt, der von 1 bis n wiederhole. Auf dem ersten führen die Außenschleife durch, j wiederholt von 1 bis 1: Die innere Schleife macht einen Pass, so das Laufen des inneren Schleife-Körpers (Schritt 6) verbraucht T Zeit, und der innere Schleife-Test (Schritt 5) verzehrt sich 2T Zeit. Während des folgenden führen die Außenschleife durch, j wiederholt von 1 bis 2: Die innere Schleife macht zwei Pässe, so das Laufen des inneren Schleife-Körpers (Schritt 6) verzehrt sich 2T Zeit, und der innere Schleife-Test (Schritt 5) verzehrt sich 3T Zeit.

Zusammen kann die Gesamtzeit, die erforderlich ist, den inneren Schleife-Körper zu führen, als ein arithmetischer Fortschritt ausgedrückt werden:

:

der factored als sein kann

:

Die Gesamtzeit, die erforderlich ist, den inneren Schleife-Test durchzuführen, kann ähnlich bewertet werden:

::der factored als sein kann:

Deshalb ist die Gesamtlaufzeit für diesen Algorithmus:

:

der zu abnimmt

:</Mathematik>

Als Faustregel kann man annehmen, dass der höchst wertige Begriff in jeder gegebenen Funktion seine Rate des Wachstums beherrscht und so seine Laufzeitordnung definiert. In diesem Beispiel n ist ² der höchst wertige Begriff, so kann man dass f (n) = O (n ²) beschließen. Formell kann das wie folgt bewiesen werden:

(für n  0)

Lassen Sie k eine Konstante größer oder gleich [T. sein. T]

(für n  1)

Deshalb für

Eine elegantere Annäherung an das Analysieren dieses Algorithmus würde das [T. erklären sollen. T] sind alle einer Einheit der Zeit größer oder gleich [T. gleich. T]. Das würde bedeuten, dass die Laufzeit des Algorithmus wie folgt zusammenbricht:

Wachstumsrate-Analyse anderer Mittel

Die Methodik der Laufzeitanalyse kann auch verwertet werden, um andere Wachstumsraten wie Verbrauch des Speicherraums vorauszusagen. Als ein Beispiel, denken Sie den folgenden Pseudocode, der führt und Speichergebrauch durch ein Programm neu zuteilt, das auf der Größe einer Datei gestützt ist, die dieses Programm führt:

während (Datei öffnen sich noch)

,

lassen Sie n = Größe der Datei

für alle 100,000 Kilobytes der Zunahme in der Dateigröße

verdoppeln Sie sich der Betrag des Gedächtnisses hat vorbestellt

In diesem Beispiel, als die Dateigröße n Zunahmen wird Gedächtnis an einer Exponentialwachstumsrate verbraucht, die Auftrag O (2) ist.

Relevanz

Algorithmus-Analyse ist in der Praxis wichtig, weil der zufällige oder unbeabsichtigte Gebrauch eines ineffizienten Algorithmus Systemleistung bedeutsam zusammenpressen kann. In zeitempfindlichen Anwendungen kann ein Algorithmus, der zu lange nimmt, um zu laufen, seine Ergebnisse überholt oder nutzlos machen. Ein ineffizienter Algorithmus kann auch damit enden, einen unwirtschaftlichen Betrag der Rechenmacht oder Lagerung zu verlangen, um zu laufen, wieder es praktisch nutzlos machend.

Siehe auch

• Amortisierte Analyse
• Asymptotische Analyse
• Asymptotische rechenbetonte Kompliziertheit
• Bester, schlechtester und durchschnittlicher Fall
• Große O Notation
• Rechenbetonte Kompliziertheitstheorie
• Master-Lehrsatz
• NP-Complete
• Numerische Analyse
• Polynomische Zeit
• Programm-Optimierung
• (Computerprogrammierung) im Profil darstellend
• Geglättete Analyse
• Zeitkompliziertheit — schließt Tisch von Ordnungen des Wachstums für allgemeine Algorithmen ein

Referenzen