Nicht angemeldet. · Kennwort vergessen · Registrieren

nebelwerfer
troll-tank
Avatar
Mitglied seit 04/2009
320 Beiträge
Betreff: 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---
Dieser Beitrag wurde 2 mal verändert, zuletzt am 30.01.2011, 13:43 von nebelwerfer.
BastiW
Mitglied seit 09/2008
572 Beiträge
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
Mitglied seit 02/2009
385 Beiträge
Lösen von Gleichungssystemen mit tridiagonalen Matrizen: O(n)
Eumel
Mitglied seit 04/2009
518 Beiträge
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³)
Dieser Beitrag wurde am 02.02.2011, 02:11 von Eumel verändert.
BastiW
Mitglied seit 09/2008
572 Beiträge
Zitat von 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²).


Zitat von 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
Mitglied seit 04/2009
518 Beiträge
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
Mitglied seit 02/2009
385 Beiträge
Zitat von 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
Mitglied seit 04/2009
518 Beiträge
Zitat von decyfeR:
Zitat von 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
Mitglied seit 09/2008
572 Beiträge
Zitat von 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.
Schließen Kleiner – Größer + Auf diesen Beitrag antworten:
Prüfcode: VeriCode Gib bitte das Wort aus dem Bild ins folgende Textfeld ein. (Nur die Buchstaben eingeben, Kleinschreibung ist in Ordnung.)
Smileys: :-) ;-) :-D :-p :blush: :cool: :rolleyes: :huh: :-/ <_< :-( :'( :#: :scared: 8-( :nuts: :-O
Weitere Zeichen:
Gehe zu Forum
Datenschutz | Kontakt
Powered by the Unclassified NewsBoard software, 20150713-dev, © 2003-2011 by Yves Goergen