Komplexität bestimmen < Komplex. & Berechnb. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 09:52 Mo 08.09.2008 | | Autor: | uecki |
| Aufgabe | a und b seinen n-dimensionale Vektoren, A eine reelle n x n Matrix. Bestimmen Sie die Komplexität der Berechnung der reellen Zahl r = [mm] a^T [/mm] * A * b.
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt. |
Hallo,
ich habe hier eine Lösung zu und zwar: [mm] n^2 [/mm] + n = [mm] O(n^2). [/mm] Aber warum ist das [mm] n^2 [/mm] +n ?
Ich dachte, da es drei Variablen sind die miteinander multipliziert werden, würde die Komplexität [mm] O(n^3) [/mm] sein...???
Danke schon mal 
|
|
| |
|
Wenn du über die Matrizen und Vektoren nichts weiteres weißt musst du die Formeln, die du aus der linearen Algebra kennst verwenden:
[mm]a^T * A * b = a^T * (A * b) = a^T * t[/mm]
wobei [mm]t[/mm] ein n-dimensionaler Vektor ist, der definiert wird als [mm]t_i = \sum_{j=1}^n A_{ij} * b_j[/mm]. Also musst du für diesen Teil der Rechnung n mal (alle [mm]t_i[/mm]) n Rechenoperationen (jeweils eine Addition und eine Multiplikation) ausführen, kommst also auf [mm]n^2[/mm]. Übrig bleibt noch die Berechnung von [mm]a^T*t[/mm] was zur Berechnung von [mm]\sum_{i=1}^n a_i * t_i[/mm] führt. Also n Operationen. Insgesamt also [mm]n^2 + n = O(n^2)[/mm] Operationen.
Als Pseudocode:
double[] t = new double[n]
for (int j = 0; j < n; j++) {
double sum = 0;
for (int i = 0; i < n; i++) {
sum += A[i][j] * b[j];
}
t[i] = sum;
}
result = 0;
for (int i = 0; i < n; i++)
result += a[i] * t[i];
Die tiefste Verschachtelung sind die oberen zwei For-Schleifen, also ist die Komplexität [mm]O(n^2)[/mm]. Wenn man die temporäre Variable weglässt und das Ergebnis direkt als [mm]\sum_{i=1}^n\sum_{j=1}^n a_i * A_{ij} * b_j[/mm] berechnet wird die quadratische Abhängigkeit noch deutlicher. Als Pseudocode wäre das dann:
result = 0;
for (int j = 0; j < n; j++) {
double sum = 0;
for (int i = 0; i < n; i++) {
sum += A[i][j] * b[j];
}
result += a[i] * sum;
}
Die Anzahl der multiplizierten Variablen hat mit der Komplexität nichts zu tun, wir nehmen ja an, dass Zahlen in konstanter Zeit multipliziert werden können, a * b * c mit a, b, c Skalar hätte also die Komplexität [mm]O(1)[/mm]
|
|
|
|
