Not logged in. · Lost password · Register

nebelwerfer
troll-tank
Avatar
Member since Apr 2009
320 posts
Subject: Komplexitaeten von den Verfahren ( in O notation)
mach grad paar aufgaben, und schreibe meine loesungen zu den kompl. in o schreibweise hier rein,

lest sie euch durch, ueberprueft sie, korrigiert wenn falsch , added eigene, und am ende haben wir ne schoene sammlung zum auswendig reinknueppeln...

Anfangen ich jetzt ;-):

Komplexitaet LR Zerlegung: O(n^3)
   quelle: https://lp.uni-goettingen.de/get/text/1018

Komplexitaet Vor bzw Rueck einsetzen nach LR zerlegung: O(n^2 + (n^2)/2 - n) = O(n^2)
   quelle: rechnung wieviel schritte man brauch,umformen zu summenformel, und nutzen von wolframalpha

Komplexitaet von loesen von gleichung it LR und vor,rueckwaertseinsetzun: O ( n^3 + n^2 + n^2) = O(n^3)

QR-Zerlegung (beide Verfahren): O(n^3)

Matrix-Matrix Multiplikation: O(n^3)

Matrix-Vektor Multiplikation: O(n^2)

Polynom-Auswertung mit Horner-Schema: O(n)

cg-Verfahren: O(n^3)

Lösen von Gleichungssystemen mit tridiagonalen Matrizen: O(n)
---Haters gonna hate---
This post was edited 2 times, last on 2011-01-30, 13:43 by nebelwerfer.
BastiW
Member since Sep 2008
572 posts
QR-Zerlegung (beide Verfahren): O(n^3)
Matrix-Matrix Multiplikation: O(n^3)
Matrix-Vektor Multiplikation: O(n^2)
Polynom-Auswertung mit Horner-Schema: O(n)
cg-Verfahren: O(n^3)
decyfeR
Member since Feb 2009
385 posts
Lösen von Gleichungssystemen mit tridiagonalen Matrizen: O(n)
Eumel
Member since Apr 2009
518 posts
Seid ihr euch bei den Komplexitäten sicher?
Hab hier in ner Zusammenfassung auch a paar gefunden:

Algorithmus von Aitken-Neville O(n²)
Algorithmus von DeCasteljau O(n²)
Algorithmus von Gauss O(n³)
Thomas-Algorithmus O(n)
Ax=b bei vollbesetztem A O(n³)
Rx=b (Dreieck) O(n²)
Vandermonde O(n³)
Cattmull-Rom-Spline O(n³)
Jacobi, Gseidel O(n²)
Householder O(n³)
This post was edited on 2011-02-02, 02:11 by Eumel.
BastiW
Member since Sep 2008
572 posts
Quote by Eumel:
LR - Zerlegung O(n²)

LR-Zerlegung selber hat O(n³). Das ist ja praktisch das Gauss'sche Eliminationsverfahren bei dem man sich zusätzlich die Koeffizienten "merkt". Das anschließende Vorwärts- / Rückwärtseinsetzen hat dann O(n²).


Quote by Eumel:
cg-Verfahren O(n)

Verwendet man das cg-Verfahren zur Optimierung quadratischer Funktionale (und damit als Anwendung dessen Lösen von LGS), so liefert das cg-Verfahren (wenn man exakt d.h. mit unbegrenzter Genauigkeit rechnet) in n Schritten die Lösung. Da ein solcher Schritt allerdings Matrix-Vektor Multiplikationen enthält ( O(n²) ), ergibt sich eine Gesamtkomplexität von O(n³).
Eumel
Member since Apr 2009
518 posts
Diskrete Faltung zweier Vektoren (periodischer Fall): O(n)
FFT (Fast-Fourier-Transformation) eines Vektors: O(n*log n)
Ein Iterationsschritt des SOR-Verfahrens (vollbesetzte Matrizen): O(??)
Bestimmen der Maximums-Norm eines Vektors: O(n)
Filterung eines m x m Pixel großen Bildes mit einer (nicht separierbaren) Maske der Größe n x n: O(??)
decyfeR
Member since Feb 2009
385 posts
Quote by Eumel:
Diskrete Faltung zweier Vektoren (periodischer Fall): O(n)
FFT (Fast-Fourier-Transformation) eines Vektors: O(n*log n)
...
Filterung eines m x m Pixel großen Bildes mit einer (nicht separierbaren) Maske der Größe n x n: O(??)

Soweit ich mich erinnern kann, kam das im SS SoSe 2010 gar nicht dran und duerfte somit auch nicht Teil des Klausurstoffs sein.
Eumel
Member since Apr 2009
518 posts
Quote by decyfeR:
Quote by Eumel:
Diskrete Faltung zweier Vektoren (periodischer Fall): O(n)
FFT (Fast-Fourier-Transformation) eines Vektors: O(n*log n)
...
Filterung eines m x m Pixel großen Bildes mit einer (nicht separierbaren) Maske der Größe n x n: O(??)

Soweit ich mich erinnern kann, kam das im SS SoSe 2010 gar nicht dran und duerfte somit auch nicht Teil des Klausurstoffs sein.

überragend ;)
BastiW
Member since Sep 2008
572 posts
Quote by Eumel:
Ein Iterationsschritt des SOR-Verfahrens (vollbesetzte Matrizen): O(??)

Das SOR Verfahren ist einfach das Gauss-Seidel Verfahren mit Relaxation nach jedem Iterationsschritt. Am Aufwand für einen Iterationsschritt ändert das (in Landau Notation) nichts. Es bleibt also bei O(n²). Bei guter Wahl des Relaxationsparameters lässt sich damit allerdings die Konvergenzgeschwindigkeit beträchtlich steigern. Ich halte das in Hinblick auf die Klausur aber für eher unwichtig.
Close Smaller – Larger + Reply to this post:
Verification code: VeriCode Please enter the word from the image into the text field below. (Type the letters only, lower case is okay.)
Smileys: :-) ;-) :-D :-p :blush: :cool: :rolleyes: :huh: :-/ <_< :-( :'( :#: :scared: 8-( :nuts: :-O
Special characters:
Go to forum
Datenschutz | Kontakt
Powered by the Unclassified NewsBoard software, 20150713-dev, © 2003-2011 by Yves Goergen