15
Institut für Wirtschaftsinformatik – Software Engineering, JKU Linz 1 Algorithmen und Datenstrukturen Übungsmodul 10 Dr. W.Narzt u. Dr. A.Stritzinger Institut für Wirtschaftsinformatik- Software Engineering JKU Linz

Institut für Wirtschaftsinformatik – Software Engineering, JKU Linz 1 Algorithmen und Datenstrukturen Übungsmodul 10 Dr. W.Narzt u. Dr. A.Stritzinger Institut

Embed Size (px)

Citation preview

Page 1: Institut für Wirtschaftsinformatik – Software Engineering, JKU Linz 1 Algorithmen und Datenstrukturen Übungsmodul 10 Dr. W.Narzt u. Dr. A.Stritzinger Institut

Institut für Wirtschaftsinformatik – Software Engineering, JKU Linz 1

Algorithmen und Datenstrukturen Übungsmodul 10

Dr. W.Narzt u. Dr. A.StritzingerInstitut für Wirtschaftsinformatik-

Software EngineeringJKU Linz

Page 2: Institut für Wirtschaftsinformatik – Software Engineering, JKU Linz 1 Algorithmen und Datenstrukturen Übungsmodul 10 Dr. W.Narzt u. Dr. A.Stritzinger Institut

Institut für Wirtschaftsinformatik – Software Engineering, JKU Linz 2

Komplexität - Allgemeines

• Speicherkomplexität

• Laufzeitkomplexität

• Laufzeit = f(Problemgröße) typ. Größe der Datenmenge

• O-Notation gibt Obergrenze für Laufzeit an.

• Konstanten werden weggelassen (zb. f(2,43N+1) = O(N))

Page 3: Institut für Wirtschaftsinformatik – Software Engineering, JKU Linz 1 Algorithmen und Datenstrukturen Übungsmodul 10 Dr. W.Narzt u. Dr. A.Stritzinger Institut

Institut für Wirtschaftsinformatik – Software Engineering, JKU Linz 3

Laufzeitkomplexitäts-Klassen

Bezeichnung O Wertung Beispiel

konstante Komp. O(1) optimal, selten

Hashing, Prepend

Logarithmische K. O( log n ) Sehr günstig Binäres Suchen

Lineare Komp. O( n ) Günstig Lineares Suchen

Leicht überlinear O(n log n) Noch gut Gutes Sortierverfahren

Quadratische K. O( n2 ) Ungünstig Schlechtes Sortierverfahren

Kubische K. O( n3 ) Ungünstig Matrizenmultiplikation

Exponentielle K. O( an ) Katastrophal Rundreiseproblem

Page 4: Institut für Wirtschaftsinformatik – Software Engineering, JKU Linz 1 Algorithmen und Datenstrukturen Übungsmodul 10 Dr. W.Narzt u. Dr. A.Stritzinger Institut

Institut für Wirtschaftsinformatik – Software Engineering, JKU Linz 4

Mathem. Aussagen

wenn P(n) ein Polynom m-ten Grades ist, so gilt: P(n) = O(nm)

an wächst stärker als jedes Polynom -> kein polynomialer Algorithmus

log n wächst schwächer als n, egal welche Basis

Page 5: Institut für Wirtschaftsinformatik – Software Engineering, JKU Linz 1 Algorithmen und Datenstrukturen Übungsmodul 10 Dr. W.Narzt u. Dr. A.Stritzinger Institut

Institut für Wirtschaftsinformatik – Software Engineering, JKU Linz 5

Laufzeitkomplexität

n O(n) O(n2) O(2^n)

1 1 sec 1 sec 1 sec

10 10 sec 100 sec ca. 1 msec

100 100 sec 10 msec 4*106 Jahre

1000 1 msec 1 sec 3,4*10286 Jahre

Page 6: Institut für Wirtschaftsinformatik – Software Engineering, JKU Linz 1 Algorithmen und Datenstrukturen Übungsmodul 10 Dr. W.Narzt u. Dr. A.Stritzinger Institut

Institut für Wirtschaftsinformatik – Software Engineering, JKU Linz 6

Laufzeitkomplexität (relativ kleine Werte)

Page 7: Institut für Wirtschaftsinformatik – Software Engineering, JKU Linz 1 Algorithmen und Datenstrukturen Übungsmodul 10 Dr. W.Narzt u. Dr. A.Stritzinger Institut

Institut für Wirtschaftsinformatik – Software Engineering, JKU Linz 7

Laufzeitkomplexität (relativ große Werte)

Page 8: Institut für Wirtschaftsinformatik – Software Engineering, JKU Linz 1 Algorithmen und Datenstrukturen Übungsmodul 10 Dr. W.Narzt u. Dr. A.Stritzinger Institut

Institut für Wirtschaftsinformatik – Software Engineering, JKU Linz 8

Laufzeit für einfache FOR-Schleifen

for (i=1; i<n; i++) {A

}

Unter der Annahme, dass A konstante Laufzeit aufweist, ist die Laufzeitkomplexität O(n), also linear.

Page 9: Institut für Wirtschaftsinformatik – Software Engineering, JKU Linz 1 Algorithmen und Datenstrukturen Übungsmodul 10 Dr. W.Narzt u. Dr. A.Stritzinger Institut

Institut für Wirtschaftsinformatik – Software Engineering, JKU Linz 9

Laufzeitkomplexität für geschachtelte For-Schleifen

for (int i = 1..n) {for (int j = 1..n) {

A}

}

Laufzeitkomplexität O(n*n), also quadratisch

Page 10: Institut für Wirtschaftsinformatik – Software Engineering, JKU Linz 1 Algorithmen und Datenstrukturen Übungsmodul 10 Dr. W.Narzt u. Dr. A.Stritzinger Institut

Institut für Wirtschaftsinformatik – Software Engineering, JKU Linz 10

Geschachtelte FOR-Schleife mit variabler Obergrenze

for (int i = 1..n) {for (int j = 1..i) {

A}

}

Laufzeitkomplexität O(n*n/2), also quadratisch

Page 11: Institut für Wirtschaftsinformatik – Software Engineering, JKU Linz 1 Algorithmen und Datenstrukturen Übungsmodul 10 Dr. W.Narzt u. Dr. A.Stritzinger Institut

Institut für Wirtschaftsinformatik – Software Engineering, JKU Linz 11

Geschachtelte Schleifen 2

Achtung: nicht jede geschachtelte Schleifenkonstruktion führt zu überlinearer Komplexität!

i = n while (i > 0) { j = 1 while (j <= i) { j = j + 1 } i = i / 2 }

ist O(n)

macht folgendes: 1. Durchlauf: x x x x x x x x x x x x x x x x (n = 16) 2. Durchlauf: x x x x x x x x (8 mal) 3. Durchlauf: x x x x (4 mal) 4. Durchlauf: x x (2 mal) 5. Durchlauf: x (1 mal)

Page 12: Institut für Wirtschaftsinformatik – Software Engineering, JKU Linz 1 Algorithmen und Datenstrukturen Übungsmodul 10 Dr. W.Narzt u. Dr. A.Stritzinger Institut

Institut für Wirtschaftsinformatik – Software Engineering, JKU Linz 12

Schleife mit Teilung der Laufweite

while (i < n) {n = n/2i = i + 1;

}

Laufzeitkomplexität O(log2n), also logarithmisch

Page 13: Institut für Wirtschaftsinformatik – Software Engineering, JKU Linz 1 Algorithmen und Datenstrukturen Übungsmodul 10 Dr. W.Narzt u. Dr. A.Stritzinger Institut

Institut für Wirtschaftsinformatik – Software Engineering, JKU Linz 13

Rekursiver Algorithmus

int fact(int n) {if (n == 0) return 1else return n * fact(n-1)

}

Anzahl der Aufrufe n * Aufwand jeder Aktivierung k

Page 14: Institut für Wirtschaftsinformatik – Software Engineering, JKU Linz 1 Algorithmen und Datenstrukturen Übungsmodul 10 Dr. W.Narzt u. Dr. A.Stritzinger Institut

Institut für Wirtschaftsinformatik – Software Engineering, JKU Linz 14

Rekursion 2

int doSomething(int a, int b) { // a < bif (a == b) return 0;else return

(doSomething (a+1, b) – doSomething(a, b-1))

}

• Durch den zweifachen rekursiven Abstieg ergibt sich ein binärer Aufrufbaum !

• Die Laufzeitkomplexität kann dabei exponentiell werden (2N).• Dies hängt jedoch immer vom Ausmaß der

Problemverkleinerung mit jedem zusätzlichen Rekursionsschritt ab.

• Für doSomething(0,3) ergeben sich (23+1 – 1) Aufrufe, da ein Binärbaum mit Höhe 4 entsteht.

• Laufzeitkomplexität O(2N)

Page 15: Institut für Wirtschaftsinformatik – Software Engineering, JKU Linz 1 Algorithmen und Datenstrukturen Übungsmodul 10 Dr. W.Narzt u. Dr. A.Stritzinger Institut

Institut für Wirtschaftsinformatik – Software Engineering, JKU Linz 15

Konkrete Laufzeitabschätzung

Durch moderne Prozessortechnologien• L1 und L2 Caches• Pipelining, Branchprediction• Multi-core

Und Compiler- sowie VM-Optimierungen• inLining• common subexpression elimination• uam.

lässt sich kaum noch eine brauchbare konkrete Laufzeitabschätzung erzielen!!