Sie befinden sich hier: Termine » Prüfungsfragen und Altklausuren » Prüfungen im Bachelor-Studium (1. - 5. Semester) » algoks » Komplexitäten   (Übersicht)

Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen gezeigt.

Link zu dieser Vergleichsansicht

pruefungen:bachelor:algoks:komplexitaeten [03.08.2017 12:19] (aktuell)
Marcel[Inf] angelegt (leichter editierbar als bereits bestehene, tlw. falsche PDF)
Zeile 1: Zeile 1:
 +===== Komplexitäten =====
  
 +Editierhinweise:​ Zum Escapen zwei Prozentzeichen am Anfang und am Ende nutzen. Zwei Backslashes und Leerzeichen für eine Newline in der Tabelle.
 +
 +^ Problem ^ Aufwand ^ Weitere Anmkerungen ^
 +| Matrix-Vektor|O(n²)|
 +| Matrix-Matrix|O(n³)|
 +| Matrix-Vektor,​ wenn Matrix Rang 1 hat und %%A = uv^T%% geg.|O(n)|
 +| LR-Zerlegung|O(n³)|
 +| QR-Zerlegung|O(n³)|
 +| QR mit Householder:​|~doppelt so viel wie LR|
 +| QR mit Givens-Rotation:​|~vier mal so viel wie LR|
 +| Cholesky: SPD Matrizen|~halb so groß wie LR|
 +| Rückwärts- & Vorwärtssubst. bei geg. LR:|O(n²)|
 +| Lösen bei geg. LR:​|O(n²)||
 +| Lösen bei geg. QR:|O(n²)|
 +| A = LU, Determinante:​|O(n)||
 +| A = P L U, Betrag der Determinante|O(n)|
 +| A = P L U, Determinante:​|O(n³)|vllt. O(n²)\\ Siehe unten.|
 +| A = QR, Determinante|O(n³)|
 +| A = QR, Betrag der Determinante|O(n³)|
 +| LR m-diagonale Matrix:​|O(m² * n)|
 +| Rückwärts- & Vorwärtssubst. bei geg. LR von m-diagonaler Matrix:​|O(n*m)|
 +|||
 +| Interpolation Nearest Neighbor:​|O(h)|
 +| Interpolation Linear:​|O(h²)|
 +| Interpolation Catmull-Rom|O(h³)|
 +|||
 +| Newton (Aitken-Neville Pyramide):​|O(n²)|
 +| De Casteljau:​|O(n²)|
 +| Midpoint Subdivision Fehler:​|%%O(1/​(levelZahl^4))%%|
 +|||
 +| Ein Iterationsschritt Jacobi / GS / SOR|O(n²)|
 +| Anzahl Iterschritte bei Jacobi|O(n)|(Schätzwert)|
 +| Anzahl Iterschritte bei SOR|O(sqrt(n))|(Schätzwert)|
 +| Konvergenzordnung Jacobi / GS / SOR|rho = 1|Lineare Konvergenz, d. h. feste Anzahl an Iterationen nimmt der Fehler um einen __Faktor__ ab.|
 +|||
 +| Filter NxN Bildausschnitt (Rand vernachlässigbar),​ nicht sep. MxM Filter, insgesamte Anz. arithmetischer Ops:|2 N² M²|
 +| Filter NxN Bildausschnitt (Rand vernachlässigbar),​ sep. MxM Filter, insgesamte Anz. arithmetischer Ops:|4 N² M|
 +
 +===== Algorithmen Details =====
 +
 +==== A = PLU, det(A) bestimmen. ====
 +
 +Beachte, dass nur |det(P)| = 1 gilt (mit Betrag!). Da P reell, kann also det(P) nur + 1 oder -1 sein.
 +
 +P ist eine Permutationsmatrix,​ d. h. die Spalten sind e_1, e_2, e_3, ... nur umsortiert. Finde zuerst die erste 1 in der ersten Zeile (dies ist e_1), dann dies '​gedanklich'​ vortauschen. Pro Tauschschritt ändert sich die Determinante um den Faktor (-1). Dann finde die erste 1 in der zweiten Zeile usw. Das sind n^2 Schritte. Die finale Determinante ergibt sich zu: %%det(P) = (-1)^#​Vertauschungen%%