Um diese Webseite uneingeschränkt betrachen zu können, aktivieren Sie bitte Javascript

2020-11-01

Von: Lukas Reipert (gepr. Osmers)





Laufzeitanalyse, Komplexität von Algorithmen


In Bezug auf Algorithmen möchte jeder am liebsten genau wissen, wie komplex diese arbeiten, wie lange sie ungefähr brauchen, um ein Problem zu lösen und wie viel Speicher sie benötigen. Ein Programm kann aus mehreren Algorithmen bestehen. Um die Effizienz eines Programms beurteilen zu können, braucht es ein Verfahren, das diese einheitlich ausdrücken kann. Wichtig ist hierbei auch der Aspekt der Vergleichbarkeit, gerade in Bezug auf andere Algorithmen.

 

Die Durchlaufzeit eines Algorithmus ist abhängig vom Input. Wenn ein Programm eine Liste sortieren kann, dann ist es schließlich für die Durchlaufzeit von Bedeutung, wie lang die Liste ist, bzw. wie viele Elemente sie enthält. Jedoch hängt das wiederum davon ab, wie viel Rechenleistung das Gerät hat, auf dem es ausgeführt wird. Das heißt es ergibt auch keinen Sinn anzugeben, wie schnell der Algorithmus durchläuft. Viel mehr ist interessant, wie „tief“ der Algorithmus ist und wie stark sich die Ausführung in Abhängigkeit zur Größe des Inputs verlängert.

 

Als Teil der Landau Schreibweise hat sich die O-Notation etabliert. Mithilfe dieser werden verschiedene Komplexitätsklassen aufgestellt, die eine Einordnung der Komplexität erlauben. Die O-Notation gibt den Algorithmus als Teil einer Menge an, der maximal so komplex ist, wie es die Definition der Komplexitätsklasse zulässt. Das heißt, dass die Komplexität in der O-Notation (Schreibweise) immer eine obere Komplexitätsgrenze angibt. Daneben gibt es dann einige weitere Komplexitätsklassen, die andere Komplexitätsklassen dominieren, d.h. komplexer sind.
Ein Algorithmus ist immer der (für ihn) niedrigstmöglichen Komplexitätsklasse zugeordnet. Dabei werden laut Definition konstante Vorfaktoren, Koeffizienten oder z.B. k addierte Durchläufe von n nicht berücksichtigt, weil sie niedrigwertiger sind als beispielsweise die Komplexität O(n²).

 

Beispiel:

Ein Algorithmus hat die Komplexität O(n²). Eine Funktion f(n) mit f(n)=5*n²+15 könnte dann diesen Algorithmus beschreiben. Weitere Beispiele sollen später im Text folgen. Als nächstes die Reihenfolge der Komplexitätsklassen in aufsteigender Komplexität.

 

O (log(n))

Logarithmisch

O (n)

Linear

O (n*log(n))

Logarithmisch

O (n²)

Quadratisch

O (n³)

Kubisch

O (n4)

Polynomial

O (2^n)

Exponentiell

O (3^n)

Exponentiell

O (n!)

Fakultätisch

 

Je weiter unten eine Komplexitätsklasse in dieser Darstellung ist, desto mehr Komplexitätsklassen dominiert sie. Die praktischen Unterschiede in der Durchlaufzeit machen sich mit zunehmender Komplexität relativ schnell bemerkbar.

 

Zum Beispiel kann ein Algorithmus, der aus einer Linearen Suche besteht der Komplexitätsklasse O(n) zugeordnet werden. Die Lineare Suche muss im „Worst Case“ so oft durchlaufen, wie die Liste Elemente hat. Eine lineare Suche kann ein Array oder eine Liste von vorne nach hinten durchsuchen und die Position eines Elements herausfinden. Zwei ineinander geschachtelte Schleifen haben zum Beispiel eine quadratische Komplexität.

 


Vorgehen zur Laufzeitanalyse von Algorithmen

 

Theorie

 

Es soll angemerkt sein, dass unter dem Aspekt der Komplexität eines Algorithmus nicht nur die Zeitkomplexität, sondern auch die Platzkomplexität angegeben werden kann. Diese gibt den minimalen Speicherbedarf des Algorithmus an. Hier soll es aber vorrangig um die Zeitkomplexität gehen.

 

In zwei Schritten kann man die Zeitkomplexität eines Algorithmus analysieren. Zunächst sollte man herausfinden, welcher Term in dem zu findenden Element der höchstwertigste ist. Wenn wir für die zwei ineinander geschachtelten Klammern also eine Algorithmus-Analyse aufstellen wird die im Bereich n² landen. Wenn noch eine weitere Funktion enthalten ist mit n+50 Durchläufen, dann ergibt sich n²+(n+50). Dieser Term ist der Komplexitätsklasse O (n²) zuzuordnen, weil die Konstanten dahinter [O (n) und O (50)] als einzelne Terme betrachtet von O (n²) dominiert werden, also weniger komplex sind. Dementsprechend wird die Funktion zuerst von Konstanten und irrelevanten Faktoren abstrahiert, dann wird der entscheidende Term gesucht und dieser nach der Tabelle eingeordnet.
Ab einer bestimmten Komplexitätsklasse kombiniert mit einer etwas höheren Eingabemenge, kann die Komplexität in der Praxis aber schon so hoch sein, dass eine Ausführung längere Zeit in Anspruch nehmen würde. Ein Algorithmus mit der Komplexität O (n³) ist in der Praxis oft schon sehr zeitintensiv zu berechnen.

 

 

Praxis

 

Wenn einem ein Algorithmus mit einer bestimmbaren Eingabemenge vorliegt, dann kann auch praktisch herausgefunden werden, welche Komplexität dieser besitzt. Ähnlich einer Wertetabelle, schreiben wir uns für einige ausgesuchte Werte ein Paar aus Eingabemenge und Dauer der Ausführung auf. Das sollten wir mit ein paar Werten tun, die in einem konstanten Abstand zueinander sind, da man an ihnen oft sehen kann, ob Werte gegen eine bestimmte Grenze korrelieren.

 

Ein fiktiver Beispielalgorithmus:

Eingabe n

100

150

200

250

300

350

400

Dauer in s

3

8

19

32

55

86

126

n²/t

3.333

2.813

2.105

1.953

1.636

1.424

1.270

n³/t

333.333

421.875

421.052

488.281

490.909

498.547

507.936

 


Wenn wir bei diesem Ergebnis eine leichte Unschärfe voraussetzen, dann können wir nach der Streichung einiger Wertepaare (im Sinn) sehen, dass n³/t gegen ungefähr 520.000 korreliert, also annähernd konstant ist. Bei n²/t ist deutlich zu sehen, dass die Werte nicht korrelieren. Somit können wir auf eine ungefähre Komplexität von O (n³) schließen. Für eine genauere Überprüfung sollten nun weitere Werte wie Eingabe n = 1.000 oder 10.000 angeschaut werden.

 

 

Praktisch nicht lösbare Probleme

 

Es existieren Probleme, die ab einer bestimmten Eingabemenge nicht in absehbarer Zeit lösbar sind, wobei mit „absehbar“ nicht der Ablauf eines Tages gemeint ist. Vielmehr ist die Komplexität so hoch, dass bei einer Grenze der Eingabemenge kein Algorithmus besteht, der das Problem „schnell“ oder annehmbar schnell löst.

 

Traveling Salesman Problem

 

Das Traveling Salesman Problem gehört zu der Kategorie der Probleme, die sich ab einer bestimmten Eingangsmenge praktisch nicht mehr lösen lassen. Außerdem wird das Traveling Salesman Problem als „NP-vollständig“ bezeichnet. Alle NP-vollständigen Probleme sind quasi nicht lösbar, weil für sie kein Algorithmus existiert, der berechnen kann, was der beste nächste Schritt wäre um das Problem in polynomialer Zeit zu lösen. Alle NP-vollständigen haben das Problem, dass sie ab einer bestimmten Zahl von Eingangsvariablen nicht mehr in absehbarer Zeit berechnet werden können. NP bedeutet „Nichtdeterministisch-polynomial“. Fachlich ausgedrückt heißt das, dass alle NP-vollständigen Probleme nur von einem nicht-deterministischen Algorithmus gelöst werden könnten, der vollständig berechnen kann, welcher Schritt im Optimalfall als nächstes kommen müsste und dieses Problem trotzdem in polynomialer Zeit löst.

 

Was ist das Traveling Salesman Problem (TSP)?

 

Bei dem TSP handelt es sich um das Problem die kürzest mögliche Route zu finden, während man eine bestimmte Anzahl gegebener Punkte abgeschritten werden muss. Wie ein Handelsreisender, der einige Städte in seiner Region nacheinander bereisen muss. Er benötigt also einen Algorithmus, der ihm im Optimalfall den kürzesten Weg berechnen kann. Voraussetzung ist, dass kein Punkt zweimal „bereist“ werden darf, bis auf den Anfangspunkt, an dem er am Ende wieder ankommen muss.
Das Problem ist Folgendes: Sobald ein Startpunkt ausgewählt ist, muss die Entscheidung getroffen werden, welcher Punkt als nächstes besucht werden soll. Den optimalen Punkt zu finden ist von da aus aber schwierig, da bei der Entscheidung eigentlich alle Entfernungen die danach infrage kämen mit einberechnet werden müssten. Dafür müssten aber immer wieder alle möglichen Wege berechnet werden, mit deren aktueller Ausgangslage.

 

Schon bei einer Eingabemenge von 16 Orten und einer Zeit von 1s, die vergeht, wenn die Strecke einer der möglichen Wege berechnet wird, dauert die Berechnung länger als 20 Jahre. Es gibt einige Algorithmen, mit denen sich ein gutes Ergebnis annähern lässt, wie dem Nearest-Neighbor-Verfahren, das grob gesagt immer die Stadt bereist, die dem aktuellen Ort am nächsten liegt. Natürlich sind die tatsächlich verwendeten Algorithmen weiter optimiert.

 



Zusammenfassung

 

Die Komplexität eines Algorithmus teilt sich in Zeitkomplexität und Platzkomplexität. Die Komplexität kann in der O-Notation angegeben werden. Diese gibt die obere Komplexitätsgrenze für den höchstwertigsten Term an, der in der „Funktion“, die den Algorithmus beschreibt, vorkommt. Ein Algorithmus kann auch praktisch, mit einer Art Wertetabelle, auf die ungefähre Komplexität überprüft werden. Dafür kann der Quotient aus der vermuteten Zeitkomplexität und Dauer der Ausführung des Algorithmus für verschiedene Eingabemengen verglichen werden. Wenn eine Konstanz festgestellt werden kann, dann ist möglicherweise eine Komplexitätsklasse gefunden. Es gibt auch Probleme, die praktisch nicht lösbar sind. Zum Beispiel die der Kategorie „NP-vollständig“. Zu ihnen gehört das Traveling Salesman Problem. Es beschreibt eine Reise an verschiedene Orte mit dem kürzest möglichen Weg, ohne einen Ort doppelt zu besuchen. Bereits bei einer niedrigen zweistelligen Zahl an Städten ist der kürzeste Weg durch ausprobieren nicht in absehbarer Zeit zu berechnen. Ausprobieren, die „Brute Force Methode“ ist die einzig mögliche Methode zum Finden der Lösung, weil noch kein Algorithmus existiert, der die Lösung exakt berechnen kann. Es gibt jedoch einige Annäherungen, mit denen sich ein relativ kurzer Weg finden lässt (allerdings ohne zu wissen, ob es tatsächlich der kürzeste ist).