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 (?)

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?

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 ?^^

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

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.

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

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?

hey, jepp genau das hatte ich gemeint^^ supi danke dir nochmal

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

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

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?

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

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