Laufzeitberechnung

[Blackdamian]

Hallo,

ich steck zur Zeit bei folgenden Problem fest

gegeben sind folgende Funktionen:

int f(int n){

int erg=1;

for (int i=1; i<= g(3*n); i++){

erg = erg * ;

}

return erg;

}

und

int g(int n){

return 2 *n + 42;

}

Und zwar muss ich jetzt die genaue Laufzeit angeben

Nur mein Problem ist, wie beginne ich? Hab kein Plan wie ich hier anfangen soll

Kann mir jemand nen schups in die richtige Richtung geben?^^

lg Susi

[flashpixx]

Komplexität (Informatik)

Zeitkomplexität

Berechnen bzw. beweisen kann man das mit Hilfe einer Vollständige Induktion

[Blackdamian]

hey,

hm.. natürlich hab ich mir die Theorie durchgelesen, aber mein Problem ist wie ich das jetzt auf die obigen Funktionen anwenden soll?

[Blackdamian]

ok,

hier mal meine ersten Überlegungen wäre nett, wenn jmd sagen würde ob das so stimmt oder ob ich komplett in die falsche Richtung gehe.

hab es jetz mal zeilenweise betrachtet:

1.Zeile ist ja ne einfache Anweisung, also müsste es hier ja O(1) sein

2.Zeile das gleiche, also O(1)

3. Zeile: Beginn der Schleife, hier auch noch O(1)

4.Zeile: in der Schleife wird ja nur immer wieder ne Multiplikation ausgeführt, also O(1), aber ich muss hier ja auch die Länge der Schleife beachten,

so das liegt jetzt mein Problem, wie oft wird die ausgeführt, sie wird ja nur solange ausgeführt wie i kleiner gleich g(3n) ist oder?

also müsste es ja O(Anzahl der schleifendurchgänge)* O(1) sein??

der Rest müsste ja auch wieder O(1) sein

wenn ich jetzt die gesamte Laufzeit bestimmen soll, hieße das ja:

O(max{von allen Laufzeiten}) oder?

Stimmen meinen Überlegungen soweit? und wie ist das nun mit der Schleife?

[carstenj]

Hi,

so würde ich das auch sehen. Du hast ja quasi nur eine Schleife, die Konstante 3 kann man vernachlässigen. Daher würde ich sagen, dass du eine lineare Laufzeit O(n) hast, d.h. die Laufzeit wächst einfach mit der Größe von n. Mit Zuweisungen: O(1) + O(1) + O(n) = O(n).

Bei Laufzeiten ist man i.d.R. am worst case interessiert, d.h. geh einfach mal davon aus dass die Funktion für ein sehr großes n ausgeführt wird.

[Blackdamian]

super da lag ich ja nicht ganz verkehrt,

hm.. muss ich eigentlich den zweiten Teil, also:

int g(int n){

return 2 *n + 42;

}

noch genauer betrachten?

weil ich soll ja die genaue Laufzeit angeben, aber wenn ich jetzt davon ausgehe, das n sehr groß wird kann ich ja, dass 2*n+42 eigentlich auch vernachlässigen oder?

danke euch beiden schonmal für eure Hilfe

[carstenj]

Hi,

genau. Die 42 sowieso, weil wenn n = 10000000000000000 wäre, würde die 42 ja nicht mehr auffallen. Man muss immer im Hinterkopf behalten, dass die O-Notation keine genau Angabe ist, aber auch nicht zu sein braucht. Dabei geht es nur darum, in etwa die Effizienz des Algorithmus zu bestimmen. Wächst er linear? Quadratisch? Oder gar exponentiell?

[Blackdamian]

okay dank dir, hab das mit der Laufzeit jetzt kapiert (glaub ich)^^

wenn ich jetzt aber die genaue Laufzeit bestimmen soll, welche mit T(n) bezeichnet ist,also Tf(n) der Funktion f in Abhängigkeit von n, wie mach ich das?

oder ist dann T(n)=O(n)? hm.. denk schon oder?

weil wie du ja auch gesagt hast ist O(n) ja eigentlich nur ne Art Abschätzung, wie groß die Laufzeit max sein kann oder ist, oder?

ich weiß ich stell höchst wahrscheinlich dumme Fragen

lg Susi

[carstenj]

Hi,

das hängt immer davon ab, wie die Funktion aussieht. Wie schon geschrieben, hast mehrere Zuweisungen, das sind dann konstante Kosten: T(1). Dann hast du die Schleife, T(n). Bei Addition gilt: O(max(T(1),T(n)). Da ist es dann auch egal ob du eine Zuweisung hast oder 10.

Wenn du jetzt noch eine weitere Schleife innerhalb hättest, gilt T(n) * T(n), was zur einer quadratischen Laufzeit führen würde, also O(n^2). Ich hoffe das war, was du meintest?

Eine wirkliche Laufzeit, also in Sekunden oder Millisekunden oder sowas hängt von vielen Faktoren ab, wie Prozessor, Speicher, konkreten Werten etc. Dafür ist die O-Notation aber nicht gedacht.

Bearbeitet 3. November 2011 von carstenj

[Blackdamian]

hey,

jepp genau das hatte ich gemeint^^

supi danke dir nochmal

[Blackdamian]

so nach nochmaligen durchlesen bzw bearbeiten der aufgabe, hab ich ein problem festgestellt

und zwar haben wir an einem anderen beispiel ebenfalls die genaue laufzeit berechnet und dies auf andere weise, als wie oben

also gegeben ist folgendes:

int maxSubSum( int[] a) {

int maxSum = 0;

for( i=0; i<a.length; i++)

for( j=i; j<a.length; j++) {

int thisSum =0;

for (int k = i; k<=j; k++)

thisSum += a[k];

if(thisSum>maxSum) maxSum=thisSum;

}

return maxSum;

}

n =a.length

Innere Schleife for( j=0; j<n; j++)

j - i + 1 mal durchlaufen fuer jedes i , j .

Mittlere Schleife for( j=i; j<n; j++)

jeweils j - i + 1 Aktionen

> 1 + 2 + 3 + : : : n - i = (n - i)(n - i + 1)=2 Aktionen

äußere Schleife for( i=0; i<n; i++)

aufsummieren ueber den Aufwand des Durchlaufes für jedes i

Beispiel n = 32. Dann 5984 Additionen

gesamtzahl der durchläufe:

T(n) = (1\6)n³ + (1/2)n² * (1/3) n

wie kommt man dahin?^^

und wie müsste ich das jetzt auf das Erstproblem anwenden?

[flashpixx]

Verwende bitte Code-Tags, das macht das einfach leserlicher

[Blackdamian]

 int maxSubSum( int[] a) {

        int maxSum = 0;

        for( i=0; i<a.length; i++)

              for( j=i; j<a.length; j++) {

                 int thisSum =0;

                 for (int k = i; k<=j; k++)

                     thisSum += a[k];

                 if(thisSum>maxSum) maxSum=thisSum;

              }

        return maxSum;

   } 

so mal probiert, hoffe ist jetzt besser zu lesen

[flashpixx]

ein kleiner praktischer Tip: Schreib Dir an jede Zeile in Deinem Code die Laufzeit dran, also für die ersten zwei Zeilen:

O(1) + O(a.length * <bis vorletzte Zeile>)

somit bekommst Du eine Funktion aus O-Notationen, die Du dann nur vereinfachen musst und dann per Induktion entsprechend für die Aufwandsklasse beweisen kannst

[carstenj]

Hi,

sicher dass der Code das tut was du denkst das er tut? Ich denke da fehlen ein paar Klammern. Ist die o.a. Lösung die Musterlösung? Weil nachvollziehen kann ich die auch nicht.

[Blackdamian]

n =a.length

Innere Schleife for( j=0; j<n; j++)

j - i + 1 mal durchlaufen fuer jedes i , j .

Mittlere Schleife for( j=i; j<n; j++)

jeweils j - i + 1 Aktionen

> 1 + 2 + 3 + : : : n - i = (n - i)(n - i + 1)=2 Aktionen

äußere Schleife for( i=0; i<n; i++)

aufsummieren ueber den Aufwand des Durchlaufes für jedes i

Beispiel n = 32. Dann 5984 Additionen

gesamtzahl der durchläufe:

T(n) = (1\6)n³ + (1/2)n² * (1/3) n

das ist die Orginallösung, am Ende soll eine Formel mit drei summenzeichen herauskommen, um auf die Gleichung

T(n) = (1\6)n³ + (1/2)n² * (1/3) n

zu kommen.

Meine Überlegung ist halt wie ich im obigen Beispiel, also das eigentliche Problem, wie ich da auf ne Summenformel komme.

[flashpixx]

Meine Überlegung ist halt wie ich im obigen Beispiel, also das eigentliche Problem, wie ich da auf ne Summenformel komme.

Das ist nur das Übersetzen des Codes in Operationen, mehr ist das nicht. Zu Deiner Info in Deiner Formel kommen keine "drei Summenzeichen" vor. Du musst für den Code einfach die Summenfunktion in Abhängigkeit von n aufstellen und ggf algebraisch umformen / vereinfachen

[Blackdamian]

hey, das mit den 3 Summenzeichen war in der Beispielaufgabe.

irgendwie komm ich jetzt blos mit meinem code nicht weiter.

find keinen anfang für die Summenformel.

die Grenzen müssten ja von 1 bis n sein, oder? Die schleife wird ja n-mal ausgeführt

aber wie setz ich die schleife um? und muss ich das g in dem unteren code mit einbeziehen für die Summenfunktion, also das :

int g(int n){

return 2*n+42;

}

oder kann ich das komplett weglassen?

kann das grad irgendwie net umsetzen

lg Black

thx das ihr zwei euch so ne mühe macht und mir versucht das zu erklären

[flashpixx]

Als Bsp:

i=1;

for(n=0; n < k; n++)

    i += n;

Die Zuweisung i=1 ist welcher Aufwand?

Welcher Aufwand ist "for(n=0; n < k; n++)" beachte, die For Schleife besteht aus 3 Teilen, welcher Aufwand ist i += n, vor allem beachte wie oft jeder Teil in der Schleife ausgeführt wird.

[Blackdamian]

ok, ich probier mal...

also Zuweisung i=1; : ist ja konstanter Aufwand O(1) bzw konstante Zeit, also c0

for(n=0; n < k; n++) : ok, die bedingung sagt ja n<k, also müssten es ja k-1 Durchläufe sein für die for schleife,

und was den Aufwand angeht, da es ja k-1 durchläufe sind müsste es ja c1*(k-1) sein, also O(n)

i+=n : da irritiert mich grad die schreibweise, änderst du hier nicht die Schleifenlaufvaribale?

aber müsste doch eigentlich auch konstant sein oder?

ok insgesamt wäre, dass ein Aufwand von O(n) bzw c0+c1(k-1)+c2 ?^^

[flashpixx]

also Zuweisung i=1; : ist ja konstanter Aufwand O(1) bzw konstante Zeit, also c0

ja, mach es Dir einfacher und lass das O(1) stehen.

for(n=0; n < k; n++) : ok, die bedingung sagt ja n<k, also müssten es ja k-1 Durchläufe sein für die for schleife,

und was den Aufwand angeht, da es ja k-1 durchläufe sind müsste es ja c1*(k-1) sein, also O(n)

nicht so schnell, Du hast das n=0 vergessen und überleg' mal ob das wirklich k-1 sind..... (schau Dir die Indizierung genau (!) an)

und Du hast das n++ vergessen

i+=n : da irritiert mich grad die schreibweise, änderst du hier nicht die Schleifenlaufvaribale?

Nein mache ich nicht, überleg' Dir was += bedeutet, Du musst das ganze nur umschreiben.

Du musst genau (!) arbeiten, lass vor allem mal die konstanten Faktoren in der Summe stehen, damit Du es wirklich einmal siehst. Als Variablen gibt es hier kein c0 o.ä. Du hast konstante Faktoren und ein k, mehr nicht.

[Blackdamian]

ok, n=0 ist ja auch O(1)

n++ bedeutet ja, dass n in Einer-Schritten wächst, also n=n+1 (?) das heißt O(1)

i+=n bedeutet dann ja i=n+i oder n=i+n verwechsel die reihenfolge immer ;-), aber das müsste ja auch O(1) sein

ok zu den Schleifendurchläufen, da hab ich grad noch meine Probleme

für n gilt ja 0<=n<k oder? sollten es da doch n-Durchläufe sein?

[flashpixx]

ok, n=0 ist ja auch O(1)

Ja

n++ bedeutet ja, dass n in Einer-Schritten wächst, also n=n+1 (?) das heißt O(1)

Ja

i+=n bedeutet dann ja i=n+i oder n=i+n verwechsel die reihenfolge immer ;-), aber das müsste ja auch O(1) sein

Ja, es ist im Grunde unerheblich ob n+i oder i+n ist, denn die Addition ist kommutativ

für n gilt ja 0<=n<k oder? sollten es da doch n-Durchläufe sein?

Es sind n Durchläufte, denn ich beginne bei n=0 und laufe so lange n < k ist und das ist bis n-1 der Fall, d.h. die Indizes laufen von 0 bis n-1 und das sind genau n Durchläufe.

Stell jetzt mal die Summe im Detail auf....

[Blackdamian]

und da liegt jetzt mein Problem, wie mache ich das jetzt

zusammengefasst haben wir ja:

die Zuweisung O(1) ; innerhalb der for-schleife 4*O(1) und für die for-schleife selbst O(n)

aber die For-Schleife hat ja im eigentlichen Sinne O(n), da die For-Schleife ja insgesamt gesehen werden muss oder?

Naja aber wie baue ich das jetzt in ne Summenformel?

Die Grenzen wären ja i=0 bis n-1 (?)

[flashpixx]

Naja aber wie baue ich das jetzt in ne Summenformel?

Du hast für jede Zeile einen Aufwand angegeben und der gesamte Aufwand ist die "Summe über alle einzelnen" ggf. musst Du eben bei Schleifen noch die Anzahl der Iterationen berücksichtigen. Du musst nur eine gesamte Summe bilden !

aber die For-Schleife hat ja im eigentlichen Sinne O(n), da die For-Schleife ja insgesamt gesehen werden muss oder?

Die Schleife hat in diesem Beispiel kein O(n), denn Du hast den konstanten Faktor nicht angegeben und in diesem Beispiel kannst Du ihn sogar explizit angeben.

Bearbeitet 7. November 2011 von flashpixx