Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
Aufwand Bandmatrix mal Vektor
In den Folien steht, dass der Aufwand das Produkt einer Bandmatrix, mit Bandbreite m, und einem Vektor zu berechnen in O(m^2 * n) liegt. Müsste es aber nicht O(n) sein, da m konstant ist?
Es ist doch immer die Frage, mit welchen Parametern du deine Laufzeit ausdrücken möchtest 
Wenn du n konstant lässt, aber die Bandbreite variierst, erhälst du O(m^2).
Aber wie kommt man dort eigentlich auf m^2? Pro Ergebniszeile muss ich maximal 2m Elemente jeweils multiplizieren und diese m Produkte dann aufaddieren. Mit n Zeilen ergibt das doch O(mn).
Hast Recht, außerdem hab ich Matrix mal Vektor mit LR-Zerlegung verwechselt (Also Aufwand LR = O(m^2 * n)).
@Jonas wenn du für ein spezifisches Problem die Komplexität angibst, z.B. die Multiplikation eines n-Vektors mit einer nxn Matrix mit Bandbreite 5, dann ist die Komplexität 2*m * n = n im O-Kalkül (Du hast pro Zeile 5-1 Additionen und und 5 Multiplikationen und das ganze n mal). Wenn du aber für allgemeine Matrizen die Komplexität angibst, ist m eine Unbekannt, die die Komplexität des Algorithmus diktiert, damit darf m nicht wie ein übliches Skalar im O Kalkül einfach fallen gelassen werden sondern muss mit angegeben werden.
Das m^2n ist übrigens für die LR Zerlegung und nicht für die Multiplikation, siehe “Direkte Verfahren LGS 3”, S. 5.
Wo in den Folien steht, dass die Matrix-Vektor Multiplikation die Komplexität m^2n hat, kann ich grad net finden und es stimmt auch net soweit ich das grad beurteilen kann, hab allerdings etz auch net sonderlich intensiv darüber nachgedacht.
Wenn man aber fragt “Gegeben Bandmatrix mit Bandbreite m, was ist der Aufwand der LR-Zerlegung”, ist m ja fest gewählt und müsste somit wegfallen.
Es fällt weg wenn da steht : Gegeben eine Bandmatrix mit Bandbreite 5, was ist die Komplexität der LR Zerlegung. Zumindest nach den Regeln des O Kalküls. Ich würd dann trotzdem hinschreiben: O(25n) = O(n). Wenn da steht es ist eine M-Bandbreite Matrix gegeben, ist die eben NICHT näher bestimmt, sonst stünde ja ne Zahl da. Ganz unabhängig was jetzt O Kalkül konform wäre, wenns in den Folien so und so steht macht mans eben so und so und im späteren Arbeitsleben interessierts eh keinen mehr weil Rechenleistung billig ist und alles naiv implementiert werden solle (mal sehen wie viele sich davon triggern lassen jetzt) 
Es steht aber aber eine konkrete Zahl da. m steht ja für genau eine festgelegte Zahl.
„Gegeben eine Bandmatrix mit Bandbreite m …“ ist mMn. nur kurz für:
„Gegeben eine Bandmatrix mit Bandbreite 1 …“
„Gegeben eine Bandmatrix mit Bandbreite 2 …“
„Gegeben eine Bandmatrix mit Bandbreite 3 …“ etc.
Ich denke, wenn dort keine explizite Zahl steht, ist vom Aufgabensteller intendiert, die Komplexität in Abhängigkeit dieser Parameter anzugeben.
Im Folgenden bitte die Komplexitäten nicht blind übernehmen. Lieber nicht lesen, wenn es nur verwirrt. 
[sub]Wenn man wie in BFS über die Eingabenlänge argumentiert: Die LR-Zerlegung, wenn man eine quadratische Matrix als Eingabe betrachtet und die Länge der Eingabe mit n bezeichnet, ist in O(n^(3/2)) berechenbar. Insbesondere wären dann die Vorwärts- und Rückwärtssubstitutionen bei einer gegebenen Matrix in O(n) berechenbar.[/sub]