Zitat von 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.

Zitat von Blackdamian

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

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

Als Bsp:

Code:

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.

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

Zitat von Blackdamian

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.

Zitat von Blackdamian

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

Zitat von Blackdamian

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.

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?

Zitat von Blackdamian

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

Ja

Zitat von Blackdamian

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

Ja

Zitat von Blackdamian

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

Zitat von Blackdamian

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....

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

Zitat von Blackdamian

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 !

Zitat von Blackdamian

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.

Bei der Laufzeitbetrachtung stellt sich immer die Frage , benutzt mein Algorithmus Schleifen/ Rekursion oder keines der beiden.
Zuweisungen etc. sind Konstant d.h. sie Kosten O(1). Schleifen muessen genauer betrachtet werden, wenn sie verschachtelt sind multipliziert man die innere mit der aeusseren. Wichtig hierbei ist wie oft werden sie durchlaufen. Wenn Rekursion vorliegt ist das ganze ein bisschen schwieriger. Man muss mit einer Rekursionsgleichung arbeiten. T(n)= a*T(n/b) bei (divide und conquer algorithmen kommt hinzu + aufteilen und kombinieren)
wichtig bei Divide und Conquer Algorithmen ist die Betrachtung fuer aufteilen und Kombinieren. Wenn man zu der Erkenntnis kommt das Aufteilen und Kombinieren O(n) ist , kann man es anhand von 3 Faellen bestimmen
a<b O(n) a=b O(n*log(n)) a>b n^log_b(a) wenn es nicht n ist braucht man die Summenformel. a ist die Anzahl der Rekursionsprobleme. b ist hierbei die groesse des Problems.