Algorithmen und Komplexität Flashcards
Erläutern Sie die Definition von Sortierverfahren.
Ein Sortierverfahren ist ein Algorithmus der dazu dient ein Liste von Elemente in eine Ordnung zu bringen. Hierfür
muss den Elementen eine Totalordnung zu Grunde liegen.
Erläutern Sie den Begriff der Totalordnung.
Eine Totalordnung für eine Menge 𝑀 ist eine Relation ≤, bei der für Elemente 𝑥, 𝑦, 𝑧 ∈ 𝑀 die folgende
Eigenschaften gelten müssen:
* Reflexivität 𝑥 ≤ 𝑥 (bezeihung zu sich selber, trivial)
* Antisymmetrie x ≤ 𝑦 ∧ 𝑦 ≤ 𝑥 ⇒ 𝑥 = 𝑦
* Transitivität x ≤ 𝑦 ∧ 𝑦 ≤ 𝑧 ⇒ 𝑥 ≤ 𝑧
* Totalität x ≤ 𝑦 ∨ 𝑦 ≤ 𝑥 (Alle elemente sind vergleichbar)
Beispiele: natürliche Zahlen nach Größe geordnet,
Lexikon alphabetisch geordnet.
Unterschiede zwischen iterativen und rekursiven Algorithmen
Rekursiv:
- Ruft sich selber auf (zerlegung in Teilprobleme)
-“eleganter” jedoch ineffizenter und verbraucht viel speicher
- Beispiele: Fibonacci
Iterativ:
- Verwenden Schleifen (while, for) bis eine Endbedingung erfüllt ist
- Zeit- und Speichereffizenter
- Beispiel: Bubble Sort, lineare Suche
Erklären Sie den iterativen Bubble-Sort-Algorithmus.
Bei bubble-Sort werden jeweils zwei Nachbarn verglichen, wenn sie nicht der Ordnung entsprechen werden sie getauscht. Nach jedem Tausch startet der Algorthmus beim ersten Element.
Erklären Sie die lexikographische Sortierung.
Totalorfnung für Zeichenketten. Es gilt:
APfel < Apfel < aPfel < apfel
ASCII-Tabelle kann genutzt werden
Erklären Sie die Sinn und Zweck der Komplexitätstheorie.
Komplexitätstheorie ermöglicht die Analyse von Speicherbedarf und Laufzeit vin Algorithmen. Sie erlaubt die Klassifizierung und Bewertung selbiger -> Optimierung, Planung
Erläutern Sie die Definition der O-Notation.
Die o-Notation wird verwendet um das Wachstumsverhalten von Funktionen.
Die O-Notation beschreibt das asymptotische Wachstum, d.h., wie sich die Funktionen für sehr große Eingabegrößen verhalten. Muss im bezug auf Algorithmen nicht das durschnitlliche Verhalten beschreiben.
Erläutern Sie den Unterschied zwischen Worst-Case- und Best-Case-Abschätzung
Sei f(n),g(n): N→R+ und c∈R, Komplexitätabschätzung ergibt:
1. Worst Case (Symbol 𝒪):
- ungünstige Eingabe für Algorithmus
- f(n) ∈ 𝒪(g(n)) c>0 und n0≥1, sodass f≤cg(n), für n≥n0
2. Best Case (Symbol Ω)
-ungünstige Eingabe
- f(n) ∈ Ω(g(n)) c>0 und n0≥1, sodass f≥cg(n), für n≥n0
3. Identität (Symbol Θ)
-eher bei Speivheraufwand der Fall
- f(n) ∈ Θ(g(n), für f(n)∈ Ω(g(n), 𝒪(g(n))
=> Symbole heißen Landau Synmbole, math. O-Notation
O-Notation Rechenergeln
Für Funktionen gilt:
-O(1)<O(log(n))<O(n)<O(nlog(n))<O(n^2)<O(n^2)<O(n!) =>O(f(n))+O(g(n))=O(max(f(n),g(n)))
=>Terme niedriger Ordnung werden nicht berücksichtigt -> wichtig für if-Bed. (höhere Ordnung “dominiert”)
- O(f(n))⋅O(g(n))=O(f(n)⋅g(n)) -> Wichitg für for-Schleifen -> Bsp.: for (0-n) { for(0-n){x}}
=> O(n)O(n)=O(n^2)
- f(n)=O(g(n)) und g(n)=O(h(n))g(n)=O(h(n)), dann gilt f(n)=O(h(n))f(n)=O(h(n)) (Transitivität -> Wenn f durch g und g durch h beschränkt, dann auch f durch h)
