Vertragstheorie Eine Einführung mit finanzökonomischen Beispielen und Anwendungen 2005, XVI, 218 S. Basler, Herbert Grundbegriffe der Wahrscheinlichkeitsrechnung und Statistischen Methodenlehre

2.1.2 Komplexit¨

at

W¨

ahrend im Zusammenhang mit der Berechenbarkeitstheorie Existenzaussa-

gen im Mittelpunkt stehen, untersucht die Algorithmen- und Komplexit¨

ats-

theorie Fragestellungen hinsichtlich des Aufwandes, der zur Berechnung eines

Problems anf¨

allt.

7

Dabei stehen Aussagen bez¨

uglich der Rechenzeit (Rechen-

aufwand, Laufzeit) im Mittelpunkt – weitere Ressourcen sind z. B. Speicher-

platz oder Kommunikationsaufwand –, wobei in der Regel die Anzahl aus-

gef¨

uhrter Elementaroperationen als Berechnungs- bzw. Messgr¨

oße zu Grunde

gelegt wird (wie z. B. Addition oder Vergleich zweier Zahlen mit begrenzter

Stellenzahl).

Zur Quantifizierung der Laufzeit von Algorithmen verwendet man in der

Regel die asymptotische Laufzeitkomplexit¨

at. Dabei begn¨

ugt man sich unter

Verwendung der so genannten O-Notation mit

”

groben“ Aussagen zum Lauf-

zeitverhalten

”

f¨

ur große n“, wobei n die Problemgr¨oße beschreibt. Oftmals

erscheint die Angabe der Problemgr¨

oße offensichtlich. So mag sich die Be-

schreibung der Problemgr¨

oße f¨

ur die Sortierung von n Zahlen durch n sofort

aufdr¨

angen; allerdings bleibt dabei unber¨

ucksichtigt, dass sich f¨

ur jede ein-

zelne Zahl in Abh¨

angigkeit von der Gr¨

oße oder der Genauigkeit eventuell

ein nicht konstanter Speicheraufwand ergibt. Als weiteres Beispiel diene die

Addition zweier n × n Matrizen: Obwohl die Eingabel¨ange hierf¨ur eigentlich

2

· n · n · d betr¨agt, wobei d die ben¨otigte Speicherl¨ange f¨ur ein Matrixele-

ment ist, gibt man den Berechnungsaufwand in der Regel f¨

ur den prim¨

ar

kennzeichnenden Parameter n an.

Eine asymptotische Laufzeitkomplexit¨

at von T (n) = O(n

2

) bedeutet, dass

die Laufzeit eines Algorithmus f¨

ur gen¨

ugend große Werte von n durch eine

Funktion c · n

2

, c konstant, nach oben beschr¨ankt ist. Formal l¨asst sich dies

folgendermaßen spezifizieren: T (n) = O(f (n)) ⇔ ∃c > 0 ∃n




> 0 ∀n > n

:

T (n) ≤ c · f (n). Einige typische Laufzeitklassen seien im Folgenden kurz

charakterisiert:

7

Vgl. hierzu z. B. Bachem (1980), Engesser (1993), Garey und Johnson (1979),

Papadimitriou (1994), Rechenberg (2000) und Wegener (1999).

---

18

2. Informatik und Informations- und Kommunikationstechnik

• O(1), konstanter Aufwand: Die Laufzeit ist konstant bzw. von der Prob-

lemgr¨

oße unabh¨

angig.

• O(log n), logarithmische Komplexit¨at: Eine Verdopplung der Eingabegr¨oße

des Problems f¨

uhrt hier nur zu einem Anstieg der Laufzeit um eine Kon-

stante. Ein Beispiel f¨

ur einen solchen Algorithmus ist die bin¨

are Suche

eines Elementes in einer geordneten Sequenz von Zahlen (sukzessive ver-

gleichend mit einem mittleren Element der verbliebenen Sequenz werden

die zu betrachtenden Zahlen in jedem Schritt in etwa halbiert).

• O(n), lineare Komplexit¨at: Die Laufzeit ist proportional zur Problemgr¨oße.

Beispiel: Suche eines Elementes in einer ungeordneten Menge von Zahlen.

• O(n log n): Diese Laufzeitkomplexit¨at ist typisch f¨ur Algorithmen zur Sor-

tierung von n Objekten.

• O(n

k

), k konstant, polynomiale Komplexit¨at: Solche Laufzeitkomple-

xit¨

aten sind typisch f¨

ur Algorithmen mit k geschachtelten Schleifen, die

jeweils mit einer von n abh¨angigen H¨aufigkeit durchlaufen werden.

• O(2

n

), exponentielle Komplexit¨

at: Die Laufzeit solcher Algorithmen

w¨

achst so stark an, dass sie f¨

ur

”

große n“ nicht mehr brauchbar sind.

Die asymptotische Laufzeitkomplexit¨

at charakterisiert das Laufzeitver-

halten eines Algorithmus nur grob. Weiterhin wird bei solchen Aussagen in

der Regel der Worst Case angenommen; d. h. es wird eine obere Absch¨

atzung

f¨

ur den schlimmstm¨

oglichen Fall getroffen. Im praktischen Einsatz kann da-

mit ein Verfahren mit einer Komplexit¨

at von O(n

2

) im Durchschnitt besser

abschneiden als eines mit O(n log n). Dies sei an folgendem Beispiel verdeut-

licht: Als Sortieralgorithmus wird h¨

aufig der Quicksort-Algorithmus einge-

setzt; vgl. z. B. Cormen et al. (2004). Es gibt einige Eingaben, f¨

ur die der

Quicksort-Algorithmus zur Sortierung von n Zahlen eine Laufzeit von O(n

2

)

ben¨

otigt; zumeist liegt die Laufzeit aber bei O(n log n). Da der Quicksort-

Algorithmus relativ einfach zu implementieren und die im großen O

”

versteck-

te“ Konstante relativ klein ist, wird dieser Algorithmus in der praktischen

Anwendung oft anderen Sortieralgorithmen vorgezogen, die eine Worst-Case-

Komplexit¨

at von O(n log n) besitzen.

Die Vorteilhaftigkeit eines Verfahrens ist damit eigentlich eher ¨

uber die

durchschnittliche Laufzeit zu bewerten (Average Case). Allerdings ergeben

sich hierbei im Allgemeinen zwei Probleme: Zum einen ist die Kenntnis der

Wahrscheinlichkeitsverteilung der Eingaben notwendig, zum anderen ergeben

sich in der Regel bei nichttrivialen Algorithmen erhebliche Schwierigkeiten bei

der Bestimmung des durchschnittlichen Berechnungsaufwandes.

Eine weitere relevante M¨

oglichkeit der Quantifizierung des Berechnungs-

aufwandes besteht in der amortisierten Laufzeitanalyse, bei der der Aufwand

einer wiederholten Ausf¨

uhrung gewisser Operationen berechnet wird. Dies sei

durch ein Beispiel erl¨

autert: Obwohl der Aufwand einer einzelnen Operation

im Worst Case linear sein mag (z. B. die Erweiterung eines Vektors um ein

Element ¨

uber den bereits reservierten Speicherbereich hinaus), k¨

onnen nach-

folgende Operationen oftmals mit konstantem Aufwand ausgef¨

uhrt werden

---

2.1 Theoretische Grundlagen

19

(z. B. indem eine n¨

otige Erweiterung eines Vektors ¨

uber eine Verdopplung

des reservierten Speicherbereiches durchgef¨

uhrt wird), so dass sich amorti-

siert ein konstanter Aufwand f¨

ur die Operationsausf¨

uhrung ergeben kann.

Zur Verdeutlichung der Auswirkungen verschiedener Laufzeitkomplexi-

t¨

aten kann Tabelle 2.1 dienen, die f¨

ur gewisse Laufzeitkomplexit¨

aten und

Rechenzeiten die maximal l¨

osbare Problemgr¨

oße n angibt. Dabei sei davon

ausgegangen, dass in einer Millisekunde eine Elementaroperation ausgef¨

uhrt

wird. Man erkennt, dass insbesondere bei der exponentiellen Laufzeitkomple-

xit¨

at eine Erh¨

ohung der Rechenzeit nur relativ geringe Auswirkungen auf die

l¨

osbare Problemgr¨

oße nach sich zieht.

Rechenzeit

Komplexit¨

at 1 Sekunde

1 Minute

1 Stunde

n

n = 1.000 n = 60.000 n = 3.600.000

n

2

n = 31,6

n = 244,9

n = 1.897,4

2

n

n = 10,0

n = 15,9

n = 21,8