LR Zerlegung mit zeilenweise Berechnung Laufzeitabschätzung? |
05.10.2017, 17:21 | JessicaDownunder | Auf diesen Beitrag antworten » |
LR Zerlegung mit zeilenweise Berechnung Laufzeitabschätzung? (ich bekomme das Spacing leider nicht gut hin. Die obere for-Schleife umfasst die beiden unteren. Die unteren Schleifen laufen unabhängig voeinander, sind also nicht verschachtelt.) Mein Ansatz ist: i-1 Subtraktionen und Divisionen und (i-1)*(j-1) Multiplikationen und Additionen in der ersten Schleife. i-n Subtraktionen und (i-n)*(i-1) Multiplikationen und Additionen in der zweiten Schleife Insgesamt: für die erste Schleife und für die zweite Schleife. Ich bin mir jetzt leider nicht sicher, ob ich da richtig gerechnet habe. Die normale LR Zerlegung liegt ja in , also wäre dieser Algorithmus nach meiner Berechnung eine Verbesserung, oder? |
||
12.10.2017, 21:11 | sibelius84 | Auf diesen Beitrag antworten » |
Hallo JessicaDownunder, dein Ergebnis finde ich merkwürdig, da ja in der dritten Schleife viel mehr Rechenoperationen stattfinden. Müsstest du nicht über j noch von 1 bis i summieren? Generell würde ich mir erst für jede Zeile innerhalb einer Schleife überlegen, wie viele Rechen-OPs da stattfinden (in Abhängigkeit von i und j), und dann entsprechend über den Schleifenindex summieren. LG sibelius84 |
||
20.10.2017, 07:53 | RomanGa | Auf diesen Beitrag antworten » |
Aufwandabschätzung Hallo Jessica, der Aufwand der normalen LR-Zerlegung ist, wie du schreibst, O(n^3). Dies ist auch hierfür plausibel. Denn: Die äußere Schleife läuft n-mal. Die beiden „mittleren“ Schleifen kann man zusammenfassen. Wir haben insgesamt auch n Durchläufe. Die Summe kann man als innere Schleife programmieren. Sie wird, grob gesprochen, von 1 bis i durchlaufen. Die mittlere und die innere Schleife zusammen ergeben 1 + 2 + 3 + … + n = O(n^2). Damit erhalten wir O(n^3). |
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
|
Die Neuesten » |
|