Looking for algorithm Keywords? Try Ask4Keywords

algorithmAlgorithmus-Komplexität


Bemerkungen

Alle Algorithmen sind eine Liste von Schritten, um ein Problem zu lösen. Jeder Schritt hat Abhängigkeiten von einigen vorherigen Schritten oder vom Start des Algorithmus. Ein kleines Problem könnte wie folgt aussehen:

Geben Sie hier die Bildbeschreibung ein

Diese Struktur wird gerichteter azyklischer Graph oder kurz DAG genannt. Die Verknüpfungen zwischen den einzelnen Knoten in der Grafik stellen Abhängigkeiten in der Reihenfolge der Operationen dar und es gibt keine Zyklen in der Grafik.

Wie passieren Abhängigkeiten? Nehmen Sie zum Beispiel den folgenden Code:

total = 0
for(i = 1; i < 10; i++)
    total = total + i

In diesem Pseudocode hängt jede Iteration der for-Schleife vom Ergebnis der vorherigen Iteration ab, da in dieser nächsten Iteration der in der vorherigen Iteration berechnete Wert verwendet wird. Die DAG für diesen Code könnte folgendermaßen aussehen:

Geben Sie hier die Bildbeschreibung ein

Wenn Sie diese Darstellung von Algorithmen verstehen, können Sie sie verwenden, um die Komplexität der Algorithmen in Bezug auf Arbeit und Spannweite zu verstehen.

Arbeit

Arbeit ist die tatsächliche Anzahl von Operationen, die ausgeführt werden müssen, um das Ziel des Algorithmus für eine gegebene Eingabegröße n .

Spanne

Span wird manchmal als kritischer Pfad bezeichnet und ist die geringste Anzahl von Schritten, die ein Algorithmus ausführen muss, um das Ziel des Algorithmus zu erreichen.

Das folgende Bild hebt die Grafik hervor, um die Unterschiede zwischen Arbeit und Spanne unserer Beispiel-DAG zu zeigen.

Geben Sie hier die Bildbeschreibung ein

Die Arbeit ist die Anzahl der Knoten im Graphen insgesamt. Dies wird durch die Grafik oben links dargestellt. Die Spanne ist der kritische Pfad oder der längste Pfad vom Anfang bis zum Ende. Wenn parallel gearbeitet werden kann, repräsentieren die gelb hervorgehobenen Knoten auf der rechten Seite die Spannweite, die geringste Anzahl von Schritten. Wenn seriell gearbeitet werden muss, ist die Spannweite der Arbeit gleich.

Sowohl Arbeit als auch Spannweite können unabhängig von der Analyse ausgewertet werden. Die Geschwindigkeit eines Algorithmus wird durch die Spanne bestimmt. Die benötigte Rechenleistung wird von der Arbeit bestimmt.

Algorithmus-Komplexität Verwandte Beispiele