Komplexitätsanalyse < Komplex. & Berechnb. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 12:15 Mo 18.02.2008 | | Autor: | svenchen |
Hallo, sind gerade dabei, für eine Klausur zu lernen, haben aber noch ein paar Schwierigkeiten.
Die Aufgabe lautet:
Bestimmen Sie die Zeitkomplexität in Abhängigkeit der Eingabe n (einer positiven ganzen Zahl) der folgenden Algorithmen, wobei die Grundrechenarten, Speicherzugriffe und Vergleiche die Komplexität O(1) haben.
Man kann jeweils ankreuzen:
O(1), O (log n), O(n), o(n log n), [mm] O(n^2), O(n^3), O(2^n)
[/mm]
a)
int max = a[0];
for (int i = 1; i <n, i++)
if (a[i] > max)
max = a[i];
b)
int k = 0;
for (int i = 0, i<n, i++)
for (int j = 1; j <4*i, j++)
k += j;
c)
int t = 1
while (t <=n)
t = 2*t;
d)
Aufruf der folgnden Methode mit calc (n)
static int calc (int i) {
if (i ==0)
return 1
return calc (i-1) + calc(i-1);
}
e)
Aufruf der folgnden Methode mit isEven(n)
static boolean isEven(int i) {
switch (i) {
case 0: return true;
case 1: return false;
default: return isEven(i-2);
}
}
Sind folgende Überlegungen ok?
a)
Die For Schleife wird n-1 mal durchlaufen also O(n).
b) Die erste for Schleife hat die Komplexität O(n). Was bedeutet bei der zweiten k+=j? Bekommt nur k einen neuen Wert, dann hat diese Zeile ja keinen Einfluss und die zweite Schleife hat auch O(n) also insgesamt [mm] O(n^2).
[/mm]
c) log(n). Denn mit zunehmendem n erreicht man dieses zwar immer länger, aber da verdoppelt wird auch relativ schnell ?! Oder wie kommt man auf das Ergebnis, es ist zwar klar irgendwoher, aber wie kann man es exakt bestimmen?
d)
Andere Frage: wie oft wird die Methode calc (i-1) aufgerufen?
Und zwar O(n + n) = O(2n) = O(n)
e)
Andere Frage: wie oft wird die Methode aufgerufen?
zwar immer i-2, aber je größer die Zahl, desto mehr aufrufe
also O(n).
Also fast immer nur O(n) angekreuzt ?!?
Dankeschön ;)
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 14:48 Mo 18.02.2008 | | Autor: | Zneques |
Hallo,
Wie du es schon getan hast, musst du die Anzahl der Rechenschritte des Programms schätzen.
a)
1.Zeile (1)
2.Zeile (2 o.ä. muss nicht ganz genau sein, wird n-1-mal wiederholt)
3.Zeile (1 wird n-1-mal wiederholt)
4.Zeile (1 wird n-1-mal wiederholt)
[mm] Laufzeit=1+4*(n-1)=-3+4n\in [/mm] O(n)
Die -3 hat also keinen Einfluss auf das Ergebnis. Es zähl also nur der Abschnitt mit der größten Komplexität.
b)
4.Zeile (1*n*(4i-1))
da [mm] i\le [/mm] n gilt [mm] n*(4i-1)\le 4n^2-n\in O(n^2)
[/mm]
genauer : [mm] Laufzeit=\summe_{i=0}^{n}\summe_{j=1}^{4i-1}1=\summe_{i=0}^{n}4i-1=4*(\bruch{n(n-1)}{2})-n
[/mm]
c)
nach i schritten ist [mm] t=2^i
[/mm]
also [mm] i=log_2(t)
d)
Dies ist ein rekursives Programm.
Deine Lösung muss genauso ansetzen.
[mm] Laufzeit_n=2*Laufzeit_{n-1}+4=2*(2*Laufzeit_{n-2}+4)+4=...=c+2^{n-1}*2\in O(2^n) [/mm] , (wobei [mm] c\in O(2^n) [/mm] der Rest mit den Vieren)
e)
[mm] Laufzeit(n)=2+Laufzeit(n-2)=2+2+Laufzeit(n-4)=...=\bruch{n}{2}*2+2\in [/mm] O(n)
> Also fast immer nur O(n) angekreuzt ?!?
Jetzt nur noch zweimal. Besser ?
Ciao.
|
|
|
| |
|
Du kannst dir garnicht vorstellen, wieviel das geholfen hat 
DANKE !
Wenn jemandem noch eine Seite einfällt, wo es Übungsaufgaben dieser Art (mit Lösungen gibt) wäre ich sehr froh.
Denn das ist das einzige, was wir bekommen haben, und ich kann garnicht mehr üben ;(
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 18:23 Mi 20.02.2008 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
