the snake II
Erfahrenes Mitglied
Ich brauche Hilfe bei folgender Übungsaufgabe:
Bestimmen Sie die Laufzeitkomplexität der folgenden Funktion bar nur in Abhängigkeit von der Eingabegröße n in Form der O-Notation, wenn die Funktion foo(i,j,n) bei jedem aufruf 2j Schritte braucht. Betrachten Sie m als Konstante.
Tipp:
![latex2png.png latex2png.png](https://www.tutorials.de/data/attachments/45/45180-56c52128e0994675829bc47474ac7b2d.jpg?hash=VsUhKOCZRn)
Die Anzahl der Durchläufe der äußeren for-Schleife ist unabhängig von der Eingabegröße. Also O(1)...?
Die Anzahl der Durchläufe der inneren Schleife ist proportional zu n. Also O
...?
Das Ergebnis ist dann: O(1) * O
* ?
Was zeigt mir der Tipp? Und wie rechne ich alles zusammen?
Mit vielem Dank im Vorraus,
André
Bestimmen Sie die Laufzeitkomplexität der folgenden Funktion bar nur in Abhängigkeit von der Eingabegröße n in Form der O-Notation, wenn die Funktion foo(i,j,n) bei jedem aufruf 2j Schritte braucht. Betrachten Sie m als Konstante.
Tipp:
![latex2png.png latex2png.png](https://www.tutorials.de/data/attachments/45/45180-56c52128e0994675829bc47474ac7b2d.jpg?hash=VsUhKOCZRn)
Code:
int bar (int m, int n) {
int i, j;
for (i=0;i<m;i++)
{
for(j=0;j<n;j++)
{
foo(i,j,n);
}
}
}
Die Anzahl der Durchläufe der äußeren for-Schleife ist unabhängig von der Eingabegröße. Also O(1)...?
Die Anzahl der Durchläufe der inneren Schleife ist proportional zu n. Also O
![Thumbs down (n) (n)](https://cdn.jsdelivr.net/joypixels/assets/8.0/png/unicode/64/1f44e.png)
Das Ergebnis ist dann: O(1) * O
![Thumbs down (n) (n)](https://cdn.jsdelivr.net/joypixels/assets/8.0/png/unicode/64/1f44e.png)
Was zeigt mir der Tipp? Und wie rechne ich alles zusammen?
Mit vielem Dank im Vorraus,
André