asymptotische Aufwandsabschätz < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 13:43 Di 23.11.2004 | | Autor: | mausi |
hat jemand ne ahnung wie man das berechnet für diesen programmausschnitte?
static int unwichtig(int n){
int ergebnis=0;
for(int i=0; i < n; i++){
for(int j=i; j<n; j++){
ergebnis=ergebnis+1;
} // end for
for(int k=0; k<n; k++){
ergebnis=2*ergebnis;
} //end for
} // end for
return ergebnis;
}// end proc
//Annahme: Gehen Sie davon aus, dass a und b quadratische Matrizen
//der Dimension (n,n) sind.
static int[][] maMult (int[][] a, int[][] b){
int[][] c=new int[a.length][b[0].length];
for (int i=0; i<a.length; i++){
for (int j=0; j<b[0].length; j++){
c[i][j]=0;
for (int k=0; k<b.length; k++){
c[i][j]=c[i][j]+(a[i][k]*b[k][j]);
} // end for
} // end for
} // end for
return c;
}// end proc
|
|
| |
|
Hallo oder Guten Tag oder Guten Morgen oder wie auch immer ;)
Also wenn du den Quelltext besser formatierst, ist er viel einfacher zu lesen.
Danke, Thomas ;)
|
|
|
| |
|
Hallo.
Bei der Aufwandsabschätzung musst du eigentlich nur zählen. Da eine Multiplikation bzw Division mehr Zeit in Anspruch nimmt, wird eine Addition und eine Multiplikation in einer "Punktoperation" zusammengefasst (warum auch immer). Du musst also ermitteln, wie viele Punktoperationen im ungünstigsten Fall ("worst case") durchgeführt werden. Für deinen ersten Algorithmus wären das:
Prozedur unwichtig(int n) {
for(int i=0; i < n; i++){ //SCHLEIFE 1
for(int j=i; j<n; j++){ //SCHLEIFE 2
ergebnis=ergebnis+1;
} // end for (2)
for(int k=0; k<n; k++){ //SCHLEIFE 3
ergebnis=2*ergebnis;
} //end for (2)
} // end for (1)
return ergebnis;
}// end proc
Zur SCHLEIFE 2:
n + (n-1) + (n-2) + ... + (1) = [mm] \bruch{n(n+1)}{2} [/mm] Durchläufe. Aber nur Additionen
Zur SCHLEIFE 3:
n + n + ... + n = [mm] n^{2} [/mm] Durchläufe. Hier Multiplikationen.
SCHLEIFE 2 und SCHLEIFE 3 zusammen:
Da es mehr Additionen als Multiplikationen sind, kann die SCHLEIFE 2 außen vorgelassen werden. Es zählt der Aufwand der SCHLEIFE 3. Somit gilt:
Obere Aufwandsabschätzung: [mm] O(n^{2})
[/mm]
Die zweite Abschätzung solltest du selber mal probieren und deine Ansätze posten...
Thomas :)
|
|
|
| |
|
| Status: |
(Frage) für Interessierte  | | Datum: | 18:26 Sa 27.11.2004 | | Autor: | mausi |
keine ahnung es geht um matrizen hmm ich verstehe jetzt wie du bei der ersten funktion vorgegangen bist aber hier bin ich ratlos es sind ja 3 schleifen is klar und es geht um ein 2dimensionales array hmm aber weiter weiss ich auch nicht,bitte nochmal helfen
|
|
|
|
