014
11.12.2004, 00:51 Uhr
Windalf
Der wo fast so viele Posts wie FloSoft...
(Operator)
|
hab gerade diese frage als postmessage bekommen...
poste das mal hier weils hier dazu gehört...
| Zitat: |
Ich bins nochmal. Bin jetzt auch mit den anderen Aufgaben durch, jetzt muß ich nur noch eine Zusatzaufgabe bei der Matrix machen.
Irgendwie wieder ein Problem, bei der ich wohl mehr die Aufgabenstellung nicht verstehe.
Und zwar geht es um das Matrixproblem, man soll dazu die Ordnung der Laufzeitfunktion T (n) berechnen. Zur Vereinfachung soll man annehmen, daß bei der Ausgangsmatrix Zeile = Spalte = 2*n ist.
Ich tippe das n bezieht sich jetzt auf die Spalten/Zeilen-anzahl der quadratischen Matrix.
Wenn ich eine Schleife habe, deren Durchläufe allgemein angegeben sind habe ich ja O(n) , dann mit der inneren Schleife zusammen O (n^2).
Dann hätte ich jetzt bei der Matrixeingabenschleife O(n^2) aber wo führt das bei der Matrixschleife mit der Untermatrizenschleife hin bei der man die Anzahl der Untermatrizen mit Einsen in der Diagonale berechnen soll?
Wie muß ich das mit der Vereinfachung verstehen?
Ich hoffe du kannst mir nochmal helfen.
Viele Grüße
| C++: |
#include<stdio.h>
int main()
{
int i,j,z=4,s=4,anzahl=0,m,n,o=0,k,l; // O(1) //
float matrix[4][4]; // O(1) //
//10//
// Eingabe der Matrix //
printf("Bitte geben Sie einen Wert für n ein:\n"); // O(1) //
scanf("%d",&n); //O(1) //
printf("Bitte geben Sie die Werte der Matrix ein:\n"); //O(1) //
for(i=0;i<z;i++)
{ for(j=0;j<s;j++)
scanf("%f",&matrix[i][j]);}
}//20//
anzahl=anzahl+(z-n+1)*(s-n+1); // O(1) //
for(i=0;i<=z-n;++i)
for(j=0;j<=s-n;++j,o+=l)
for(k=0,l=1;l&&k<n;++k)
if(matrix[i][j]*matrix[i+k][j+k]!=1)
l=0;
printf("Die Matrix hat %d quadratische Teilmatrizen\n",anzahl); //O(1) //
printf("%d quadratische Teilmatrizen haben nur den Wert 1 in der Hauptdiagonalen",o);
return 0;
}
|
|
so da die "untermatrix" ja maximal so gross sein kann wie die originalmatrix muss die innere schleife maximal n mal durchlaufen werden (das auch nur wenn auch alles einsen auf der diagonale sind sonst wird ja früher abgebrochen...)
also würd ich spontan sagen das ist kleiner O(n^3)
--
...fleißig wie zwei Weißbrote |
