Komplexität < Komplex. & Berechnb. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) reagiert/warte auf Reaktion  | | Datum: | 17:02 Do 04.10.2007 | | Autor: | Fabian |
| Aufgabe | Welche algorithmische Komplexität bezüglich des Speicherbedarfs und des übergebenen Paramters n besitzt die nachfolgende Funktion? Schätzen Sie diese anhand der Größenordnung O ab.
void funktion7(int n){
int a[10] = {0,1,2,3,4,5,6,7,8,9};
int b = 10;
int j;
for(j=0; j<n; j++) {
int *c = (int *) malloc(sizeof(int) * (n-j)*j);
*c = a[4];
free(c);
}
} |
Hallo,
bei dieser Aufgabe weiß ich leider nicht weiter. Ich würde gerne Lösungsansätze liefern, weiß aber leider keine!
Ich danke euch für eure Antworten!
Viele Grüße
Fabian
|
|
| |
|
Hallo,
> Welche algorithmische Komplexität bezüglich des
> Speicherbedarfs und des übergebenen Paramters n besitzt
> die nachfolgende Funktion? Schätzen Sie diese anhand der
> Größenordnung O ab.
>
> void funktion7(int n){
> int a[10] = {0,1,2,3,4,5,6,7,8,9};
> int b = 10;
> int j;
> for(j=0; j<n; j++) {
> int *c = (int *) malloc(sizeof(int) * (n-j)*j);
> *c = a[4];
> free(c);
> }
> }
> bei dieser Aufgabe weiß ich leider nicht weiter. Ich
> würde gerne Lösungsansätze liefern, weiß aber leider
> keine!
>
> Ich danke euch für eure Antworten!
ich würde einfach mal linear den Programmtext durchgehen.
Für die Speicherkomplexität ist interessant eigentlich nur die Zeile mit malloc, da der Rest einfach konstanten Speicher benötigt. Der Speicher wird zwar danach direkt wieder frei gegeben, allerdings wird er natürlich alloziiert.
Für die Laufzeit ist eigentlich auch nur die Schleife interessant. Ansonsten wird ja nicht viel gemacht. Die Frage dabei ist natürlich, wieviel Zeit man einem malloc/free zuweist. In der Größenordnung des zu reservierenden/freizugebenden Speichers? Oder konstante Laufzeit?
Vielleicht hilft das jetzt, damit Du selber auf eine Lösung kommst, oder zumindest auf einen Lösungsansatz.
Gruß
Matthias Kretschmer
|
|
|
|
