O(2n log(2n) oder O(n log (n)) Operationen |
28.09.2010, 14:38 | Coolio2066 | Auf diesen Beitrag antworten » |
O(2n log(2n) oder O(n log (n)) Operationen Hallo Ich verstehe den letzten Absatz von http://www.cs.utk.edu/~dongarra/etemplates/node384.html nicht. Da wir eine 2n X 2n Matrix haben, sollten wir doch auch O(2nlog(2n)) Operationen benötigen Meine Ideen: Benötigt man weniger Operationen, wegen der NULL im zweiten abschnitt des ersten vektors oder weil nur T_Nv des zweiten vektots betrachtet wird?! |
||
28.09.2010, 14:57 | Pseudonym | Auf diesen Beitrag antworten » |
Hi. Schau dir mal die Definition der O/Landau-Notation an. Dann wirst du sehen, dass Konstanten in der Regel keine Rolle spielen und es gilt für eine Funktion f: |
||
28.09.2010, 15:19 | Coolio2066 | Auf diesen Beitrag antworten » |
wie schreibt mans dann "die matrix-vektor-multiplikation benötigt O(nlog(n)) Operationen" ist das ok? |
||
28.09.2010, 16:25 | Coolio2066 | Auf diesen Beitrag antworten » |
ist das eine offizielle schreiobweise? ist sie richtig? DANKE |
||
28.09.2010, 18:32 | Pseudonym | Auf diesen Beitrag antworten » |
Die Korrekte Schreibweise wäre , da ja eine Menge von Funktionen ist. Aber eigentlich sollte jeder wissen was gemeint ist, wenn von O(...) die Rede ist. Daher sollte auch "[...] benötigt O(...) Operationen" nicht missverstanden werden. |
|
Verwandte Themen
Die Beliebtesten » |
Die Größten » |
|
Die Neuesten » |
|