Du befindest dich hier: FSI Informatik » Prüfungsfragen und Altklausuren » Prüfungen im Bachelor-Studium (1. - 5. Semester) » algoks » Komplexitäten (Übersicht)
Inhaltsverzeichnis
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