Komplexität (O-Notation) < Komplex. & Berechnb. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Aufgabe | 1.a) Geben Sie für die Methoden m1 bis m4 an, was sie in Bezug auf den Parameter n berechnen (Bsp.: „Das Doppelte von n“).
b) Welche Laufzeit haben die einzelnen Methoden, ausgedrückt in der O-Notation, in Abhängigkeit von n? Begründen Sie Ihre Antworten!
public static int m1(int n) {
int z = 0;
while (n > 1) {
n = n / 2;
z++;
}
return z;
}
public static int m3(int n) {
int t = 1, z = 0;
while (n > 0) {
n = n - t;
t = t + 2;
z++;
}
return z;
}
public static int m4(int n) {
return m3(m1(n));
} |
Hallo,
ich versuche gerade herauszufinden, wie man die Laufzeit von einem Code "ablesen" kann. Wie finde ich heraus, was die Funktion, die Anzahl der Schritte und die Komplexitätsklasse (O-Notation) von so einem Code ist? Muss ich bei so einem Code drauf achten, was übergeben wurde (hier: n) oder was zurückgeliefert (hier: z) wird, um die oben genannten Sachen herauszufinden?
Ich habe keine Ahnung, wie man an so eine Aufgabe rangeht. Deswegen habe ich jetzt erstmal die Werte 1-5 und 10 für n eingesetzt und handschriftlich den Code selber "ausgeführt". Bei m1 komme ich auch auf log2(n). Aber bei den anderen Aufgaben habe ich keine Ahnung. Kann mir jemand erklären, wie ihr bei solchen Aufgaben vorgeht?
Habe auch die folgenden Ergebnisse erhalten:
m1)
n: 1 2 3 4 5 ... 10
z: 0 1 1 2 2 ... 3
Laufzeit: log2(n)
Anzahl der Schritte: ?
Funktion: ?
m3)
n: 1 2 3 4 5 ... 10
z: 1 2 2 2 3 ... 4
Laufzeit: ?
Anzahl der Schritte: ?
Funktion: ?
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 16:18 Sa 16.08.2014 | | Autor: | felixf |
Moin!
> 1.a) Geben Sie für die Methoden m1 bis m4 an, was sie in
> Bezug auf den Parameter n berechnen (Bsp.: „Das Doppelte
> von n“).
> b) Welche Laufzeit haben die einzelnen Methoden,
> ausgedrückt in der O-Notation, in Abhängigkeit von n?
> Begründen Sie Ihre Antworten!
>
> public static int m1(int n) {
> int z = 0;
>
> while (n > 1) {
> n = n / 2;
> z++;
> }
>
> return z;
> }
>
> public static int m3(int n) {
> int t = 1, z = 0;
>
> while (n > 0) {
> n = n - t;
> t = t + 2;
> z++;
> }
>
> return z;
> }
>
> public static int m4(int n) {
> return m3(m1(n));
> }
>
> Hallo,
> ich versuche gerade herauszufinden, wie man die Laufzeit
> von einem Code "ablesen" kann. Wie finde ich heraus, was
> die Funktion, die Anzahl der Schritte und die
> Komplexitätsklasse (O-Notation) von so einem Code ist?
> Muss ich bei so einem Code drauf achten, was übergeben
> wurde (hier: n) oder was zurückgeliefert (hier: z) wird,
> um die oben genannten Sachen herauszufinden?
Ja.
> Ich habe keine Ahnung, wie man an so eine Aufgabe rangeht.
> Deswegen habe ich jetzt erstmal die Werte 1-5 und 10 für n
> eingesetzt und handschriftlich den Code selber
> "ausgeführt".
Das ist ein sehr guter Ansatz. Daraus kann man oft schon erkennen, in welche Richtung das Ergebnis geht.
Bei diesen beiden Code-Stuecken siehst du uebrigens, dass das Ergebnis (z) in der Schleife je um genau 1 erhoeht wird. Damit ist die Anzahl der Schleifendurchlaeufe gleich dem Ergebnis. Wenn du also weisst, was die Funktion berechnet, kannst du recht einfach die Komplexitaet bestimmen.
> Bei m1 komme ich auch auf log2(n). Aber bei
> den anderen Aufgaben habe ich keine Ahnung. Kann mir jemand
> erklären, wie ihr bei solchen Aufgaben vorgeht?
>
> Habe auch die folgenden Ergebnisse erhalten:
> m1)
> n: 1 2 3 4 5 ... 10
> z: 0 1 1 2 2 ... 3
>
> Laufzeit: log2(n)
Wenn du [mm] $O(\log_2 [/mm] n)$ meinst: ja.
> Anzahl der Schritte: ?
Haengt davon ab, was du unter "Schritt" verstehst. Wenn du bei der Schleife jede Iteration einmal zaehlst (da ist ja der Vergleich) und dazu noch zwei weitere Befehle pro Iteration, hast du $3 z$ Schritte fuer die Schleife. Und wenn du die Initialisierung der Variablen $z$ ebenfalls zaehlst, kommst du auf $3 z + 1$ Schritte. Wenn du also den Wert von $z$ kennst -- das ist der naechste Teil -- kannst du die Anzahl der Schritte direkt hinschreiben.
> Funktion: ?
Tipp: die Funktion hat etwas mit [mm] $\log_2 [/mm] n$ zu tun.
> m3)
> n: 1 2 3 4 5 ... 10
> z: 1 2 2 2 3 ... 4
>
> Laufzeit: ?
> Anzahl der Schritte: ?
> Funktion: ?
Tipp hierzu: die Summe der ersten $n$ ungeraden Zahlen $1, 3, 5, [mm] \dots, [/mm] 2n+1$ ist genau [mm] $n^2$.
[/mm]
Und noch ein Tipp: $t$ geht der Reihe nach alle ungeraden Zahlen durch.
LG Felix
|
|
|
| |
|
> Bei diesen beiden Code-Stuecken siehst du uebrigens, dass
> das Ergebnis (z) in der Schleife je um genau 1 erhoeht
> wird. Damit ist die Anzahl der Schleifendurchlaeufe gleich
> dem Ergebnis. Wenn du also weisst, was die Funktion
> berechnet, kannst du recht einfach die Komplexitaet
> bestimmen.
Was würde passieren, wenn z innerhalb/außerhalb der Schleife und z.B. z = t/2, z = z*5 oder z = z-5 wäre?
> > Bei m1 komme ich auch auf log2(n). Aber bei
> > den anderen Aufgaben habe ich keine Ahnung. Kann mir jemand
> > erklären, wie ihr bei solchen Aufgaben vorgeht?
> >
> > Habe auch die folgenden Ergebnisse erhalten:
> > m1)
> > n: 1 2 3 4 5 ... 10
> > z: 0 1 1 2 2 ... 3
> >
> > Laufzeit: log2(n)
>
> Wenn du [mm]O(\log_2 n)[/mm] meinst: ja.
Ja, genau das meinte ich.
> > Anzahl der Schritte: ?
>
> Haengt davon ab, was du unter "Schritt" verstehst. Wenn du
> bei der Schleife jede Iteration einmal zaehlst (da ist ja
> der Vergleich) und dazu noch zwei weitere Befehle pro
> Iteration, hast du [mm]3 z[/mm] Schritte fuer die Schleife. Und wenn
> du die Initialisierung der Variablen [mm]z[/mm] ebenfalls zaehlst,
> kommst du auf [mm]3 z + 1[/mm] Schritte. Wenn du also den Wert von [mm]z[/mm]
> kennst -- das ist der naechste Teil -- kannst du die Anzahl
> der Schritte direkt hinschreiben.
Wäre das dann nicht [mm]2 z+1[/mm] bei der m1? Und dieses z+1 ist für die z++ oder?
> > m3)
> > n: 1 2 3 4 5 ... 10
> > z: 1 2 2 2 3 ... 4
> >
> > Laufzeit: ?
> > Anzahl der Schritte: ?
> > Funktion: ?
>
> Tipp hierzu: die Summe der ersten [mm]n[/mm] ungeraden Zahlen [mm]1, 3, 5, \dots, 2n+1[/mm]
> ist genau [mm]n^2[/mm].
>
> Und noch ein Tipp: [mm]t[/mm] geht der Reihe nach alle ungeraden
> Zahlen durch.
Ich weiß nicht genau, was ich damit anfangen soll. Das die genau [mm] n^2 [/mm] sind habe ich jetzt auch gesehen, aber was heißt das dann für die anderen Zahlen?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 14:55 So 17.08.2014 | | Autor: | felixf |
Moin!
> > Bei diesen beiden Code-Stuecken siehst du uebrigens, dass
> > das Ergebnis (z) in der Schleife je um genau 1 erhoeht
> > wird. Damit ist die Anzahl der Schleifendurchlaeufe gleich
> > dem Ergebnis. Wenn du also weisst, was die Funktion
> > berechnet, kannst du recht einfach die Komplexitaet
> > bestimmen.
>
> Was würde passieren, wenn z innerhalb/außerhalb der
> Schleife und z.B. z = t/2, z = z*5 oder z = z-5 wäre?
Dann geht es nicht ganz so einfach 
> > > Anzahl der Schritte: ?
> >
> > Haengt davon ab, was du unter "Schritt" verstehst. Wenn du
> > bei der Schleife jede Iteration einmal zaehlst (da ist ja
> > der Vergleich) und dazu noch zwei weitere Befehle pro
> > Iteration, hast du [mm]3 z[/mm] Schritte fuer die Schleife. Und wenn
> > du die Initialisierung der Variablen [mm]z[/mm] ebenfalls zaehlst,
> > kommst du auf [mm]3 z + 1[/mm] Schritte. Wenn du also den Wert von [mm]z[/mm]
> > kennst -- das ist der naechste Teil -- kannst du die Anzahl
> > der Schritte direkt hinschreiben.
>
> Wäre das dann nicht [mm]2 z+1[/mm] bei der m1? Und dieses z+1 ist
> für die z++ oder?
Du hast in der Schleife zwei Anweisungen:
* $n = n/2$
* $z++$ (ist hier gleichbedeutend mit $z = z + 1$)
Und du hast den Vergleich $n > 1$, der in jedem Durchlauf druchgefuehrt sind. Also hast du drei Operationen pro Schleifendurchlauf. Weiterhin hast du eine Operation davor, naemlich $z = 0$. Insgesamt hast du also, da $z$ gleich der Anzahl der Schleifendurchlaeufe sind, $3 z + 1$ Operationen.
> > > m3)
> > > n: 1 2 3 4 5 ... 10
> > > z: 1 2 2 2 3 ... 4
> > >
> > > Laufzeit: ?
> > > Anzahl der Schritte: ?
> > > Funktion: ?
> >
> > Tipp hierzu: die Summe der ersten [mm]n[/mm] ungeraden Zahlen [mm]1, 3, 5, \dots, 2n+1[/mm]
> > ist genau [mm]n^2[/mm].
> >
> > Und noch ein Tipp: [mm]t[/mm] geht der Reihe nach alle ungeraden
> > Zahlen durch.
> Ich weiß nicht genau, was ich damit anfangen soll. Das
> die genau [mm]n^2[/mm] sind habe ich jetzt auch gesehen, aber was
> heißt das dann für die anderen Zahlen?
Nun, du ziehst doch solange ungerade Zahlen ab, bis das Ergebnis [mm] $\le [/mm] 0$ ist. Du suchst also das kleinste natuerliche $z$, so dass $n - 1 - 3 - 5 - ... - (2 z - 1) [mm] \le [/mm] 0$ ist. Wegen $1 + 3 + 5 + ... + (2 z - 1) = (z - [mm] 1)^2$ [/mm] suchst du also das kleinste $z$ mit $n [mm] \le [/mm] (z - [mm] 1)^2$. [/mm] Damit kannst du jetzt eine explizite Formel fuer $z$ in Abhaengigkeit von $n$ angeben.
LG Felix
|
|
|
|
