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

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-VektorO(n²)
Matrix-MatrixO(n³)
Matrix-Vektor, wenn Matrix Rang 1 hat und A = uv^T geg.O(n)
LR-ZerlegungO(n³)
QR-ZerlegungO(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 DeterminanteO(n)
A = P L U, Determinante:O(n³)vllt. O(n²)
Siehe unten.
A = QR, DeterminanteO(n³)
A = QR, Betrag der DeterminanteO(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-RomO(h³)
Newton (Aitken-Neville Pyramide):O(n²)
De Casteljau:O(n²)
Midpoint Subdivision Fehler:O(1/(levelZahl^4))
Ein Iterationsschritt Jacobi / GS / SORO(n²)
Anzahl Iterschritte bei JacobiO(n)(Schätzwert)
Anzahl Iterschritte bei SORO(sqrt(n))(Schätzwert)
Konvergenzordnung Jacobi / GS / SORrho = 1Lineare 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