Algorithmen und Datenstrukturen

Praktische Einführung und Programmierung

Stefan Bosse

Universität Koblenz - Praktische Informatik

1 / 33

Stefan Bosse - Algorithmen und Datenstrukturen - Modul C Komplexität und Effizienz ::

Komplexität und Effizienz

Was ist Effizienz, was ist Komplexität, wie sind sie definiert?

2 / 33

Stefan Bosse - Algorithmen und Datenstrukturen - Modul C Komplexität und Effizienz ::

Komplexität und Effizienz

Was ist Effizienz, was ist Komplexität, wie sind sie definiert?

Wie wird Komplexität/Effizienz berechnet?

3 / 33

Stefan Bosse - Algorithmen und Datenstrukturen - Modul C Komplexität und Effizienz ::

Komplexität und Effizienz

Was ist Effizienz, was ist Komplexität, wie sind sie definiert?

Wie wird Komplexität/Effizienz berechnet?

Wie wird Komplexität/Effizienz gemessen?

4 / 33

Stefan Bosse - Algorithmen und Datenstrukturen - Modul C Komplexität und Effizienz ::

Komplexität und Effizienz

Was ist Effizienz, was ist Komplexität, wie sind sie definiert?

Wie wird Komplexität/Effizienz berechnet?

Wie wird Komplexität/Effizienz gemessen?

Was ist praktisch relevant?

5 / 33

Stefan Bosse - Algorithmen und Datenstrukturen - Modul C Komplexität und Effizienz :: Einstieg

Einstieg

Für die algorithmische Lösung eines gegebenen Problems ist es unerlässlich, dass der gefundene Algorithmus das Problem korrekt löst. Darüber hinaus ist es natürlich wünschenswert, dass er dies mit möglichst geringem Aufwand tut. Manchmal ist dies auch unerlässlich – etwa beim automatischen Abschalten eines Kernkraftwerks im Falle einer Havarie.

  • Die Theorie der Komplexität von Algorithmen beschäftigt sich damit, gegebene Algorithmen hinsichtlich ihres Aufwands abzuschätzen und – darüber hinaus – für gegebene Problemklassen zu bestimmen, mit welchem Mindestaufwand Probleme dieser Klasse gelöst werden können.
6 / 33

Stefan Bosse - Algorithmen und Datenstrukturen - Modul C Komplexität und Effizienz :: Einstieg

Einstieg

Für die algorithmische Lösung eines gegebenen Problems ist es unerlässlich, dass der gefundene Algorithmus das Problem korrekt löst. Darüber hinaus ist es natürlich wünschenswert, dass er dies mit möglichst geringem Aufwand tut. Manchmal ist dies auch unerlässlich – etwa beim automatischen Abschalten eines Kernkraftwerks im Falle einer Havarie.

  • Die Theorie der Komplexität von Algorithmen beschäftigt sich damit, gegebene Algorithmen hinsichtlich ihres Aufwands abzuschätzen und – darüber hinaus – für gegebene Problemklassen zu bestimmen, mit welchem Mindestaufwand Probleme dieser Klasse gelöst werden können.

Wir haben bereits Beispiele aus der Numerik kennen gelernt, wo unterschiedliche Algorithmen das gleiche Problem mit unterschiedlicher Effizienz lösen. Das Ergebnis war (fast) immer gleich (aber in der Numerik nicht selbstverständlich).

AuD dpunkt 7.3 Komplexität

7 / 33

Stefan Bosse - Algorithmen und Datenstrukturen - Modul C Komplexität und Effizienz :: Ein Beispiel: Suche in linearen Arrays

Ein Beispiel: Suche in linearen Arrays

Die Bestimmung des Aufwands wollen wir zunächst an einem einfachen Beispiel verdeutlichen: der sequenziellen Suche in Folgen. Gegeben seien hierzu

i=IndexOf(b ∈ {a1,..., an})

  • eine Zahl n ≥ 0,
  • n Zahlen A=a1,..., an, die alle verschieden sind,
  • eine Zahl b.

Gesucht wird der Index i = 1, 2,..., n, so dass b = ai ist, sofern ein solcher Index existiert. Sonst soll i = -1 ausgegeben werden.

8 / 33

Stefan Bosse - Algorithmen und Datenstrukturen - Modul C Komplexität und Effizienz :: Ein Beispiel: Suche in linearen Listen

Ein Beispiel: Suche in linearen Listen

Eine sehr einfache Lösung (Implementierung) dieses Suchproblems ist die folgende (wobei standardmäßig an+1 = 0 gesetzt sei) und mit i=0 als programmatischen Startindex:

a=[1,2,5,6,7]
b=5
i=0
n=length(a)
while (i<n && b != a[i]) {
  i=i+1 
}
if (i==n) i=-1; // nicht gefunden

Suche in linearer Array Liste

Am Ende hat i den gesuchten Ausgabewert (oder -1 wenn nicht gefunden).

9 / 33

Stefan Bosse - Algorithmen und Datenstrukturen - Modul C Komplexität und Effizienz :: Ein Beispiel: Suche in linearen Listen

Analyse

Der Aufwand der Suche, d.h. die Anzahl der Schritte, hängt von der Eingabe ab, d.h. von n, A=a1,..., an und b. Es gilt:

  1. Bei erfolgreicher Suche, wenn b = ai ist, werden S = i Schritte benötigt.
  2. Bei erfolgloser Suche werden S = n + 1 Schritte benötigt.

Die erste Aussage hängt noch von zu vielen Parametern ab, um aufschlussreich zu sein. Man ist bemüht, globalere Aussagen zu finden, die nur von einer einfachen Größe abhängen. Hier bietet sich die Länge n der Eingabeliste an und man beschränkt sich auf Fragen der Art:

  1. Wie groß ist S für ein gegebenes n im schlechtesten Fall?
  2. Wie groß ist S für ein gegebenes n im Mittel?

Wir analysieren nun den Fall der erfolgreichen Suche:

10 / 33

Stefan Bosse - Algorithmen und Datenstrukturen - Modul C Komplexität und Effizienz :: Ein Beispiel: Suche in linearen Listen

Analyse

  1. Im schlechtesten Fall wird b erst im letzten Schritt gefunden, d.h. b = an. Also gilt: S = n im schlechtesten Fall.
  2. Um eine mittlere Anzahl von Schritten zu berechnen, muss man Annahmen über die Häufigkeit machen, mit der – bei wiederholter Verwendung des Algorithmus mit verschiedenen Eingaben – b an erster, zweiter, …, letzter Stelle gefunden wird. Also N Experimente mit verschiedenen Eingaben!
    • Wird b häufiger am Anfang der Liste gefunden, so ist die mittlere Anzahl von Suchschritten sicherlich kleiner, als wenn b häufiger am Ende der Liste gefunden wird.
    • Als einfaches Beispiel nehmen wir die Gleichverteilung an. Läuft der Algorithmus N-mal, N ≫ 1, so wird b gleich häufig an erster, zweiter,.., letzter Stelle gefunden, also jeweils N/n-mal.

Dann werden für alle N Suchvorgänge (Experimente) insgesamt M Schritte benötigt, im Mittel S=M/N:

M=Nn1+Nn2+..+Nnn=Nn(1+2+..+n)=N(n+12)

11 / 33

Stefan Bosse - Algorithmen und Datenstrukturen - Modul C Komplexität und Effizienz :: Ein Beispiel: Suche in linearen Listen

Analyse

Also im Mittel bei Gleichverteilung:

S=n+12

Unser Algorithmus ist für das gestellte Problem keineswegs der schnellste, sondern eher einer der langsameren. Es gibt Algorithmen, die die Suche in Listen (oder Tabellen) mit n Einträgen unter speziellen Voraussetzungen i.W. mit einer konstanten, nicht von n abhängigen Anzahl von Schritten lösen!

  • Die besten Suchverfahren für direkten Zugriff, die auch Ordnung der Schlüssel zulassen, benötigen eine logarithmische Anzahl von Schritten, d.h. S = a · log2(b · n) + c, wobei a, b, c Konstanten sind.
12 / 33

Stefan Bosse - Algorithmen und Datenstrukturen - Modul C Komplexität und Effizienz :: Asymptotische Analyse

Asymptotische Analyse

Meist geht es bei der Analyse der Komplexität von Algorithmen bzw. Problemklassen darum, als Maß für den Aufwand eine Funktion F(n) zu finden.

F(n) = a bedeutet: Bei einem Problem der Größe n ist der Aufwand a.

  • Die Problemgröße n bezeichnet dabei in der Regel ein Maß für den Umfang einer Eingabe, z.B. die Anzahl der Elemente in einer Eingabeliste oder die Größe eines bestimmten Eingabewertes.
  • Der Aufwand a ist in der Regel ein grobes Maß für die Rechenzeit, jedoch ist auch der benötigte Speicherplatz zuweilen Gegenstand der Analyse.
  • Die Rechenzeit wird meist dadurch abgeschätzt, dass man zählt, wie häufig eine bestimmte Art von Operation ausgeführt wird, z.B. Speicherzugriffe, arithmetische Operationen.
    • Auf diese Weise erhält man ein maschinenunabhängiges Maß für die Rechenzeit, die mit einer abstrakten Maschine maschinenunabhängig bestimmt werden kann ⇒ Profilieren mit μJ VM!
13 / 33

Stefan Bosse - Algorithmen und Datenstrukturen - Modul C Komplexität und Effizienz :: Asymptotische Analyse

Asymptotische Analyse

Die Aufwandsfunktion F lässt sich in den wenigsten Fällen exakt bestimmen. Vorherrschende Analysemethoden sind wie bereits eingeführt:

  • Abschätzungen des Aufwands im schlechtesten Fall
  • Abschätzungen des Aufwands im Mittel
  • Abschätzungen des Aufwands im besten Fall (Business best hope)

Selbst hierfür lassen sich im Allgemeinen keine exakten Angaben machen. Man beschränkt sich dann auf approximiertes Rechnen in Größenordnungen.

Rechnen in Größenordnungen

Das folgende Beispiel illustriert die Schwierigkeit von exakten Analysen, insbesondere bei Abschätzungen im Mittel, bereits in recht einfachen Fällen.

14 / 33

Stefan Bosse - Algorithmen und Datenstrukturen - Modul C Komplexität und Effizienz :: Asymptotische Analyse

Rechnen in Größenordnungen

  • Gegeben: n ≥ 0, A={a1,.., an, ai ∊ ℕ}
  • Gesucht: Der Index i der (ersten) größten Zahl
a=[5,2,1,7,6]
n=length(a)
amax=a[0],imax=0
for (i=1;i<n;i++) {
  if (amax<a[i]) { amax=a[i]; imax=i }  // relevante Operation 
}

Maximumssuche in linearer Array Liste

15 / 33

Stefan Bosse - Algorithmen und Datenstrukturen - Modul C Komplexität und Effizienz :: Asymptotische Analyse

Rechnen in Größenordnungen

Neben übergeordneten Schleifeniterationen müssen Teilausdrücke und Funktionen betrachtet werden.

Analyse: Wie oft wird die Anweisung {*} von if (also die max Berechnung) als relevante Operation ausgeführt?

  1. Best case: 1 Durchlauf
  2. Worst case: n-1 Durchläufe
  3. Mean case: ? Statistische Betrachtung ist erforderlich...
16 / 33

Stefan Bosse - Algorithmen und Datenstrukturen - Modul C Komplexität und Effizienz :: Asymptotische Analyse

Rechnen in Größenordnungen

Analyse: Wie oft wird die Anweisung {*} (von if) !!, also die max Berechnung) im Mittel ausgeführt, abhängig von n (Größe der Folge)?

  • Diese gesuchte mittlere Anzahl sei Tn. Offenbar gilt: 1 ≤ Tn ≤ n.
  • Beobachtung: {*}(if) wird genau dann ausgeführt, wenn ai das größte der Elemente {a1,.., ai} ist.
  • Annahme (Gleichverteilung): Für jedes i = 1,.., n hat jedes der Elemente a1,..,an die gleiche Chance, das größte zu sein.
    • Das heißt, dass bei N Durchläufen (Experimente mit unterschiedlichen Eingaben) und n Elementen (pro Eingabe) durch den Algorithmus, N ≫ 1, insgesamt N/n-mal die Anweisung {*}(if) ausgeführt wird für i = 1,..,n. Das heißt:
    • imax := 1 wird N-mal, d.h. immer, ausgeführt
    • imax := 2 wird N/2-mal ausgeführt
    • etc.
17 / 33

Stefan Bosse - Algorithmen und Datenstrukturen - Modul C Komplexität und Effizienz :: Asymptotische Analyse

Rechnen in Größenordnungen

Die gesamte Ausführungszeit M für alle N Experimente ist dann N*Tn:

M=NTn=N+N2+N3+..+Nn=N(1+12+..+1n)=NHn

Hn ist die harmonische Zahl mit der Näherung Hn≈ln(n)+γ

Da der Aufwand schon vom Ansatz her ohnehin nur grob abgeschätzt werden kann, macht eine Feinheit wie +γ im obigen Beispiel nicht viel Sinn. Interessant ist lediglich, dass Tn logarithmisch von n abhängt, nicht so sehr, wie dieser Zusammenhang im Detail aussieht.

  • Man schreibt dafür die O-Notation mit der weiteren Approximation ln(n)≈log(n) (und M/N):

Tn=O(logn)

D.h. Tn ist von der Ordnung log(n), wobei multiplikative und additive Konstanten sowie die Basis des Logarithmus unspezifiziert bleiben.

18 / 33

Stefan Bosse - Algorithmen und Datenstrukturen - Modul C Komplexität und Effizienz :: Messen

Messen

Die Komplexität kann nicht wirklich gemessen werden.

  1. Die Zeitmessung ist ungenau (statistische Schwankung)
  2. Die Messung der ausgeführten Instruktionen (Prozessorinstruktionen, VM) ist präzise, aber enthält einen Überhang.
  3. Bei zu kleinen N gibt es Verfälschung, und die Größenordnung n ist ähnlich n2 oder n3, vielleicht nicht einmal unterscheidbar von log n
  4. Große N können u.U. nicht gerechnet werden da die Kapazitäten des Rechners nicht ausreichen (Speicher, Laufzeit)
19 / 33

Stefan Bosse - Algorithmen und Datenstrukturen - Modul C Komplexität und Effizienz :: Messen

Messen

Ein Beispiel ...

+

20 / 33

Stefan Bosse - Algorithmen und Datenstrukturen - Modul C Komplexität und Effizienz :: Die O-Notation

Die O-Notation

Die O-Notation lässt sich mathematisch exakt definieren. Seien f, g : ℕ → ℕ Funktionen, dann gilt:

f(n)=O(g(n))⇔∃c,n0∀n≥n0:0≤f(n)≤c⋅g(n)

Was bedeutet diese Relation?

Das heißt, dass f(n)/g(n) für genügend große n > n0 durch eine Konstante c beschränkt ist. Anschaulich bedeutet dies, dass f nicht stärker wächst als g.

  • Diese Begriffsbildung wendet man bei der Analyse von Algorithmen an, um Aufwandsfunktionen f durch Angabe einer einfachen Vergleichsfunktion g abzuschätzen, so dass f(n) = O(g(n)) gilt, also das Wachstum von f durch das von g beschränkt ist (Oberschranke).
21 / 33

Stefan Bosse - Algorithmen und Datenstrukturen - Modul C Komplexität und Effizienz :: Die O-Notation

Die O-Notation

Eigentlich ist die Angabe f = O(g) im mathematischen Sinn nicht exakt. Vielmehr müsste man f ∊ O(g) schreiben, um auszudrücken, dass f zur Klasse der Funktionen gehört, deren Wachstum asymptotisch durch das Wachstum von g beschränkt ist. Die Schreibweise mit dem »=« hat sich allerdings allgemein eingebürgert, so dass wir sie auch verwenden.

addp Asymptotische obere Schranke: O-Notation

22 / 33

Stefan Bosse - Algorithmen und Datenstrukturen - Modul C Komplexität und Effizienz :: Die O-Notation

Die O-Notation

Da die O(g)-Notation eine obere Grenze für eine Klasse von Funktionen definiert, kann die Funktion g jeweils vereinfacht werden, indem konstante Faktoren weggelassen werden sowie nur der höchste Exponent berücksichtigt wird.

Beispiele:

Tn=n2+3n−3<O(n2)=c⋅n2Tn=lnn+γ<O(logn)=c⋅log(n)

  • Diese Ungleichung wird für n ≥ n0 erfüllt, wenn man beispielsweise c = 2 und n0 = 1 einsetzt (erster Fall).

  • Für kleine n kann es aber signifikante Abweichungen geben (siehe Übungsaufgaben) von der tatsächlichen Rechenzeit geben!

Warum?

23 / 33

Stefan Bosse - Algorithmen und Datenstrukturen - Modul C Komplexität und Effizienz :: Die O-Notation

Die O-Notation

Komplexitätsklassen

Aufwand Klasse
O(1) Konstanter Aufwand (unabhängig von n)
O(log n) Logarithmischer Aufwand
O(n) Linearer Aufwand
O(n log n) Linearer Aufwand
O(n2) Quadratischer Aufwand
O(n3) Kubischer Aufwand
O(nk) Polynomieller Aufwand für k ≥ 0
O(kn) Exponentieller Aufwand

Typische Komplexitätsklassen aufsteigend sortiert

24 / 33

Stefan Bosse - Algorithmen und Datenstrukturen - Modul C Komplexität und Effizienz :: Die O-Notation

Komplexitätsklassen

addp Wachstum für ausgewählte Komplexitätsklassen

Die Polynomiellen Klassen sind auch noch für großes n mit "schnelleren" Rechnern (z.B. durch Parallelisierung) in akzeptabler Zeit lösbar, wo hingegen exponentielle Laufzeit auch nicht mehr durch schnellere Rechner oder Parallelisierung lösbar sind.

25 / 33

Stefan Bosse - Algorithmen und Datenstrukturen - Modul C Komplexität und Effizienz :: Die O-Notation

Komplexitätsklassen

Recht illustrativ ist es auch, sich vor Augen zu führen, welche Größenordnung ein Problem haben kann, wenn man die Zeit durch eine maximale Dauer T begrenzt. Wir nehmen dazu an, dass ein Schritt des Aufwandes genau eine Mikrosekunde (1 µs) dauert. G sei dabei das größte lösbare Problem in der Zeit T. Den Aufwand g(n) = log n lassen wir weg, da man hier praktisch unbegrenzt große Probleme in vernünftiger Zeit bearbeiten kann.

addp Zeitaufwand für einige Problemgrößen

26 / 33

Stefan Bosse - Algorithmen und Datenstrukturen - Modul C Komplexität und Effizienz :: Die O-Notation

Problemklassen

Aufwand Problem
O(1) Einfache Suchverfahren mit Hash Tabellen
O(log n) Allgemeine Suchverfahren für Tabellen (Baum-Suchverfahren)
O(n) sequenzielle Suche, Suche in Texten, syntaktische Analyse von Programmen, einfache Vektoroperationen
O(n log n) Sortieren, Suche
O(n2) einige dynamische Optimierungsverfahren (z.B. optimale Suchbäume), Multiplikation Matrix-Vektor (einfach)
O(n3) Matrizen-Multiplikation (einfach)
O(2n) viele Optimierungsprobleme (z.B. optimale Schaltwerke), automatisches Beweisen (im Prädikatenkalkül 1. Stufe)

Typische Problemklassen

27 / 33

Stefan Bosse - Algorithmen und Datenstrukturen - Modul C Komplexität und Effizienz :: NP versa P-vollständig

NP versa P-vollständig

P-vollständig Gruppe
Der Algorithmus löst maximal in polynomieller Laufzeit (aber beliebiger Polynomgrad)
NP
Der Algorithmus löst maximal in exponentieller Laufzeit (aber beliebige Basis), eventuell auch in P Laufzeit.
  • Offensichtlich gehört jedes Problem aus P auch NP an, d.h., es gilt P ⊆ NP.
  • Es gibt eine Reihe von Problemen, von denen man weiß, dass sie NP angehören, aber nicht, ob sie auch P angehören.
    • Das bedeutet, dass sie mithilfe eines nichtdeterministischen Algorithmus gelöst werden können, aber es noch nicht gelungen ist, einen effizienten deterministischen Algorithmus zu finden.

Es ist – streng genommen – ein offenes Problem, ob sich die exponentiellen Probleme nicht doch mit polynomialem Aufwand lösen lassen, d.h., ob P=NP gilt. Es wäre jedoch eine große Überraschung, wenn sich dies herausstellen sollte. Man kann allerdings beweisen, dass es eine Klasse von verwandten Problemen aus NP gibt, die folgende Eigenschaft aufweisen: Falls eines dieser Probleme in polynomialer Zeit mit einem deterministischen Algorithmus gelöst werden könnte, so ist dies für alle Probleme aus NP möglich (demzufolge wäre P=NP). Man bezeichnet Probleme mit dieser Eigenschaft als NP-vollständig. Ein bekanntes Problem aus dieser Klasse ist das Problem des Handlungsreisenden.

28 / 33

Stefan Bosse - Algorithmen und Datenstrukturen - Modul C Komplexität und Effizienz :: NP versa P-vollständig

NP versa P-vollständig

Aber:

Diese Annahmen und Aussagen gelten nur für "handelsübliche" Rechnermodelle, also der Turing- oder Registermaschine (von-Neumann Rechner). Wie sich das bei völlig andersartigen Rechnermodellen (z.B. Quantencomputer) entwickelt ist noch unklar.

29 / 33

Stefan Bosse - Algorithmen und Datenstrukturen - Modul C Komplexität und Effizienz :: Analyse von Algorithmen

Analyse von Algorithmen

Wie kann nun die Laufzeitkomplexität eines Algorithmus bestimmt werden? Die Probleme einer exakten Analyse haben wir bereits diskutiert. Die Bestimmung der Größenordnung ist dagegen wesentlich einfacher, da sich hierfür einige einfache Regeln angeben lassen:

  1. Zählschleifen
for(i=a;i<b;i=i+c) { * }

Laufzeit := max. Laufzeit der inneren Anweisung · Anzahl der Iterationen (b-a)/c

  1. Geschachtelte Zählschleifen
for(i=a1;i<b1;i=i+c1) for(j=a2;j<b2;j=j+c2) { * }

Laufzeit := max. Laufzeit der inneren Anweisung · Produkt der Durchläufe aller Schleifen, d.h. Πi(bi-ai)/ci

30 / 33

Stefan Bosse - Algorithmen und Datenstrukturen - Modul C Komplexität und Effizienz :: Analyse von Algorithmen

Analyse von Algorithmen

  1. Nacheinanderausführung
for(i=a;i<b;i=i+c) { * } ; for(j=a2;j<b2;j=j+c2) { * }

Bei einer Sequenz von Anweisungen werden die Laufzeiten zunächst addiert. Da konstante Faktoren weggelassen werden können und nur die jeweils höchsten Exponenten berücksichtigt werden, wird für die Gesamtlaufzeit nur die maximale Laufzeitkomponente verwendet.

  1. Bedingte Verzweigungen
if (cond) { A1 } else { A2 }

Laufzeit := Aufwand für Test + max(Aufwand für A1, Aufwand für A2)

  1. Funktionsaufrufe (Rekursion)
function foo(x) { return terminatecond(x)?C:F(foo(G(x))) }

Laufzeit := max. Laufzeit der inneren Anweisung · Anzahl der Iterationen

31 / 33

Stefan Bosse - Algorithmen und Datenstrukturen - Modul C Komplexität und Effizienz :: Landau Symbole

Landau Symbole

But wait, there is more...

Wikipedia Es gibt neben der O-Notation noch weitere Funktionen die unterschiedliche Schranken definieren

32 / 33

Stefan Bosse - Algorithmen und Datenstrukturen - Modul C Komplexität und Effizienz :: Little versa Big O

Little versa Big O

Big-O- und Little-O-Notationen haben sehr ähnliche Definitionen, und ihr Unterschied liegt darin, wie streng sie in Bezug auf die von ihnen dargestellte Obergrenze sind.

Big O
Engerer Abstand zwischen f und g

f(n)=O(g(n))⇔∃c,n0∀n≥n0:0≤f(n)≤c⋅g(n)

Little o
Großzügigerer Abstand zwischen f und g

f(n)=O(g(n))⇔∃c,n0∀n≥n0:0≤f(n)<c⋅g(n)

33 / 33