Zeitkomplexität eines Algorithmus

[mihe7]

Wie komme ich hier in der zweiten for-Schleife auf (n-1)*(n+1) und warum (n-1)*n für die if-Bedingung?

Ich weiß nicht genau, was hier gezählt wird, aber ich vermute mal die Initialisierung und das Inkrement.

for(int i=1; i<a.length; i++) { // n

Die Schleife hat (n-1) Iterationen, d. h. es wird (n-1)-mal inkrementiert und 1-mal initialisiert, so dass sich in der Zeile n Schritte ergeben.

for(int j=0; j<a.length; j++) { // (n-1)*(n+1)

Die Schleife hat n Iterationen, d. h. es wird n-mal inkrementiert und 1-mal initialisiert, so dass sich in der Zeile n+1 Schritte ergeben. Allerdings wird diese Zeile durch die äußere Schleife (n-1)-mal wiederholt, so dass sich insgesamt (n-1)*(n+1) Schritte ergeben.

 

[jono]

Okay, das verstehe ich, aber wenn man sich ganz oben mal den Code anschaut von #1 , steht neben der while-Schleife n+1, aber warum? JustNoBody sagt :
" Die Überprüfung wird n+1 mal gemacht, denn er prüft 0<n, 1<n, ... n<n
Die Schritte in der while Schleife werden aber bei n<n aber nicht mehr ausgeführt. Der Check wird also 1 Mal mehr gemacht als die Schritte in der Schleife. "
Müsste es dann nicht, wie in deiner letzten Erklärung auch nur n-mal gemacht werden. Verstehe nicht was er damit meint, wenn er sagt der check wird 1 mal mehr gemacht als die Schritte in der Schleife, klingt irgendwie komisch.

 

[jono]

@mihe7
"Ich weiß nicht genau, was hier gezählt wird, aber ich vermute mal die Initialisierung und das Inkrement. " <- Meinst du damit das"(n-1)*n" der if-Schleife? Wenn ja, verstehe nicht genau wie du darauf kommst, wäre sehr gut wenn du das evtl. nochmal näher beschreiben kannst.

 

[mihe7]

if-Schleife?

if-schleife.de

Meinst du damit das"(n-1)*n" der if-Schleife?

Nein, ich meinte, welche Operationen genau von der for-Schleife als Schritte gezählt werden. Ich vermutete, dass die Bedingung nicht mitgezählt wird, d. h. nur die Initialisierung (int i=1) und das Hochzählen (i++) relevant wären.

Aber

JustNoBody sagt :
" Die Überprüfung wird n+1 mal gemacht, denn er prüft 0<n, 1<n, ... n<n

würde auch Sinn ergeben. Ergebnis ist aber für #48 das gleiche.

Verstehe nicht was er damit meint, wenn er sagt der check wird 1 mal mehr gemacht als die Schritte in der Schleife, klingt irgendwie komisch.

Das ist schon richtig. Die Schleife endet, wenn die Schleifenbedingung nicht mehr gilt. Dieser Fall tritt nur einmal ein, nämlich wenn die Schleife endet. In diesem Fall wird aber der Schleifenrumpf nicht mehr ausgeführt.

for (int i = 0; i < 2; i++)

i = 0: Check #1: i < 2 wahr -> also Schleifenrumpf ausführen, i hochzählen
i = 1: Check #2: i < 2 wahr -> also Schleifenrumpf ausführen, i hochzählen
i = 2: Check #3: i < 2 falsch -> also terminiert die Schleife

Check ist 3-mal ausgeführt worden, der Schleifenrumpf nur zweimal

 

[jono]

for(int j=0; j<a.length; j++) { // (n-1)*(n+1)

Dann verstehe ich nicht wieso diese for-Schleife nicht (n-1)*(n+2) ist ?

 

[jono]

Das müsste dann hier ja auch einmal mehr ausgeführt werden, so wie bei der while-Schleife, weil

for(int j=0; j<a.length; j++)

meiner Auffasung nach dann dasselbe ist, so wie du es mir auch als letztes beschrieben hast
oder verstehe ich etwas falsch ^^

 

[mihe7]

Lies nochmal, was ich in #51 geschrieben habe. Das kann doch nicht so schwer sein.

In der Zeile(!!!) der äußeren for-Schleife befinden sich Operationen, die insgesamt n-mal ausgeführt werden. Darum der Kommentar "// n".

In der Zeile(!!!) der inneren for-Schleife befinden sich Operationen, die - für sich genommen - (n+1)-mal ausgeführt werden.

Der Schleifenrumpf der äußeren for-Schleife wird (n-1)-mal durchlaufen, so dass die Zeile der inneren for-Schleife (n-1)-mal wiederholt ausgeführt wird. Macht (n-1)*(n+1)

 

[jono]

Ja das ist mir klar , ich glaube du weißt nicht worauf ich hinaus will.
Wenn du sagst, dass bei "while (i<n) | n+1" korrekt ist, dann müsstest
du doch auch bei

for(int j=0; j<a.length; j++)

zustimmen, dass "j<a.length" für sich genommen auch schon n+1 betragen müsste , weil j <a.length = n ja nichts anderes ist als i<n.
Also würde sich aufgrund der Initialisierung und dem gerade Genannten n+2 ergeben alleine nur für die zweite innere Schleife unabhängig davon , dass sie sowieso mit der äußeren n-1 mal wiederholt wird.

 

[jono]

Weil,

i = 0;
while(i < n) und j < n(a.length)

dasselbe sind was die Wiederholungen angeht.

 

[jono]

Und oben bei der while-Schleife ist es ja so, dass die Initialisierung als 0 gewertet wird, gehen wir davon aus sie wird als 1 gewertet. Dann hätten wir schonmal die 1 für die for-Schleife, dann kommt wie bei der while-Schleife j < n welches n+1 betragen müsste laut #1 und dann noch das Inkrement was mit einem n zu bewerten ist. Demnach müsste ich doch davon ausgehen, dass es dann 2n + 2 sein müsste ^^

for(int j=0; j<a.length; j++)

 

[mihe7]

Ich weiß nicht, was Du hier veranstaltest. Ich habe anders gezählt als in #1 gezählt wurde, nämlich die Zahl der Zuweisungen und nicht die Zahl der Vergleiche. Bei der for-Schleife kommst Du dabei aufs gleiche raus: 1 Initialisierung + x-Inkremente <=> x+1-Vergleiche. Mischen, so wie Du es gemacht hast, darfst Du die beiden Zählmethoden aber natürlich nicht.

Du kannst gerne bei den Vergleichen bleiben, denn

Wenn du sagst, dass bei "while (i<n) | n+1" korrekt ist, dann müsstest
du doch auch bei

for(int j=0; j<a.length; j++)

zustimmen, dass "j<a.length" für sich genommen auch schon n+1 betragen müsste

ist auch richtig. Die Zeile wird aber (n-1)-mal wiederholt, daher (n-1)*(n+1)

 

[jono]

for (int i = 0; i < 2; i++)
   
i = 0: Check #1: i < 2 wahr -> also Schleifenrumpf ausführen, i hochzählen
i = 1: Check #2: i < 2 wahr -> also Schleifenrumpf ausführen, i hochzählen
i = 2: Check #3: i < 2 falsch -> also terminiert die Schleife

Check ist 3-mal ausgeführt worden, der Schleifenrumpf nur zweimal

Analog zu der while-Schleife hast du mir die Sinnhaftigkeit für n+1 hinter der while-Schleife versucht näher zu bringen anhand dessen was ich eingefügt habe. Dann frage ich mich halt(ich glaube auch zurecht) warum das dann nicht bei der for-Schleife auch so ist?

 

[jono]

Hat sich erledigt

 

[jono]

Aber warum berücksichtigt man dieses n+1 wie bei der while-Schleife nicht auch bei der for Schleife, weil die wird ja auch wie du es erklärt hast n+1 mal durchlaufen

 

[jono]

Eine 1 für die Initialisierung bei der for-Schleife, dann n-mal inkrementieren, sodass sich (n+1) ergibt,
bei der while-Schleife wird auch n-mal inkrementiert und, und die Iteration ist dann "//n+1" bei der while
Schleife. Aber warum darf man die Methoden denn nicht mischen, weil es doch eigentlich das Gleiche ist,
bei der for-Schleife müsste ich dann doch auch die Wiederholungen zählen mit n+1 wieso wird das dort nicht
gemacht?

 

[mihe7]

Aber warum darf man die Methoden denn nicht mischen, weil es doch eigentlich das Gleiche ist,
bei der for-Schleife müsste ich dann doch auch die Wiederholungen zählen mit n+1 wieso wird das dort nicht
gemacht?

Du kannst ja nicht einfach Iteration + Vergleiche rechnen.

 

[jono]

Also unterscheidet sich die while- von der for-Schleife? Denn bei der while-Schleife werden die Vergleiche gezählt und bei der for-Schleife nur die Inkremente.

 

[mihe7]

Also unterscheidet sich die while- von der for-Schleife?

Nein, aber es unterscheidet sich, was man zählt. In einem Punkt hast Du allerdings recht: in #1 wurden Vergleiche + Inkrement gezählt. Während in #48 z. B. nur Vergleiche (oder eben Zuweisungen) gezählt wurden.

 

[jono]

In #48 wurden nur Inkrement und Initialisierung gezählt meinst du oder?

 

[mihe7]

In #48 wurden nur Inkrement und Initialisierung gezählt meinst du oder?

Ja, oder eben die Vergleiche.

 

[jono]

Ok, die Vergleiche wurden ja in #48 nicht gezählt, das ist ja z. B. der Fall bei der while-Schleife.

 

[jono]

Aber woher soll ich jetzt wissen ob ich Inkremente oder doch Vergleiche zähle oder eben beides

 

[mihe7]

Vom Aufgabensteller bzw. dem "Zählmodell". Du musst Dir überlegen, dass man beim Zählen sowieso von CPU-Instruktionen abstrahiert. Also zählt man schon mal keine CPU-Instruktionen, sondern z. B. Anweisungen der Programmiersprache. Nur: ist ein Math.sin(x) wirklich mit einfachen Vergleich oder einem i++ vergleichbar? Taugt also auch nicht viel. Bedingungen sind da schon besser.

Normalerweise interessiert die exakte Schrittzahl nicht, da man an der Laufzeit-Komplexität interessiert ist. D. h. man sieht: aha, äußere Schleife läuft knapp n-mal, innere Schleife läuft n-mal, macht O(n²). Gemein wird es, wenn die innere Zählvariable von der äußeren abhängt. Da muss man dann etwas überlegen (und ggf. zählen).

 

[jono]

Was meinst du jetzt mot exakter Schrittzahl genau?

 

[mihe7]

Was meinst du jetzt mot exakter Schrittzahl genau?

Das Programm läuft ja Schritt für Schritt ab. Jeder Schritt erhöht die Schrittzahl.

 

[jono]

1.

    public static int[] bubblesort(int[] a) {     // n = a.length
int temp; // 1
for(int i=1; i<a.length; i++) { // n
for(int j=0; j<a.length; j++) { // (n-1)*(n+1)
if(a[j]>a[j+1]) { // (n-1)*n
temp=a[j]; // (n-1)*n
a[j]=a[j+1]; // (n-1)*n
a[j+1]=temp; // (n-1)*n
}
}
}
return a; // 1
}

/* 1 + n + (n-1)(n+1) + 4(n-1)n + 1
* = 2 + n + n^2 - 1 + 4n^2 -4n + 1
* = 5n^2 - 3n + 2
* => O(n^2)
     */

Wie kommt man hier von 5n^2 - 3n + 2 auf => O(n^2)?
2.

public static int[] bubblesort2(int[] a) {     // n = a.length
int temp; // 1
for(int i=1; i<a.length; i++) { // n
for(int j=0; j<a.length-i; j++) { // n*(n+1)/2 - 1
if(a[j]>a[j+1]) { // (n-1)*n/2
temp=a[j]; // (n-1)*n/2
a[j]=a[j+1]; // (n-1)*n/2
a[j+1]=temp; // (n-1)*n/2
}
}
}
return a; // 1

Wie kommt man auf geteilt durch 2 bei der zweiten for-Schleife??
3.

public static int beispiel(int[] a) {  // n = a.length
            int result = 0;                               // 1
            int x = 5;                                    // 1
            int y = 2;                                    // 1
            int z = 1;                                    // 1   
            for (int i = 0; i < x; i++) {                 // 6
                System.out.println("i: " + i);           // 5
                for (int j = 1; j < a.length; j*=y) {   // 5 (log(n)+1)
                    System.out.println("j: " + j);      // 5 log(n)
                    for (int k = a.length-x; k >= 0; k--) {   // 5 log(n) (n-3)
                        System.out.println("k: " + k);        // 5 log(n) (n-4)
                        for (int l = 0; l < a.length; l+=z) { // 5 log(n) (n-4) (n+1)
                            System.out.println("l: " + l);    // 5 log(n) (n-4) n
                            for (int m = 0; m < Math.pow(2, a.length); m++) {  // 5 log(n) (n-4) n (2^n+1)
                                System.out.println("m: " + m);     // 5 log(n) (n-4) n 2^n
                                result += i - a[j] + a[k] - a[l];  // 5 log(n) (n-4) n 2^n
                            }
                        }
                    }
                }
            }
            return result; // 1 
        }

Wie kommt man in der 3. for-Schleife auf (n-3), Rest verstehe ich nur das halt nicht.

 

[mihe7]

Wie kommt man hier von 5n^2 - 3n + 2 auf => O(n^2)?

Indem alle Konstanten und konstanten Faktoren weggelassen werden: n^2-n und dann nur das n mit dem größten Exponenten (n^2) genommen wird.

Wie kommt man auf geteilt durch 2 bei der zweiten for-Schleife??

j ist abhängig von i. Ist i = 1, gilt für j: 0 <= j < n-1, ist i=2, gilt für j: 0 <= j < n-2

i	0 <= j <
1	n-1
2	n-2
3	n-3
...	...
n-2	2
n-1	1

Da die Zahl der Vergleiche bekanntermaßen um 1 höher liegt, ergibt dies: 2+3+4+...+n. Ergänzt man die Summe um +1-1, erhält man (1+2+3+...+n)-1. Für den geklammerten Ausdruck liefert der kleine Gauß n*(n+1)/2, so dass man insgesamt n*(n+1)/2 - 1 erhält.

Wie kommt man in der 3. for-Schleife auf (n-3),

Nicht anders wie sonst auch: k zählt wegen x=5 von n-5 bis 0, das sind n-4 verschiedene Werte. Da die Zahl der Vergleiche bekanntermaßen um 1 höher liegt, sind es n-3 Vergleiche.

 

[jono]

War es nicht so, dass es die Initialisierung war die für +1 sorgt und nicht die Zahl der Vergleiche?

 

[jono]

War es nicht so, dass es die Initialisierung war die für +1 sorgt und nicht die Zahl der Vergleiche?

 

[mihe7]

Scroll rauf und lies nach.

 

[jono]

Ja, du hast gesagt, dass man daran interessiert ist, die exakte Schrittzahl zu erfassen sprich die Inkremente lassen wir außer Acht, weil es ja auch hieß ganz oben wird sich auf die Iterationen plus Inkremente konzentriert, dementsprechend jetzt nir dir Vergleiche.
Du hast aber in #61 gesagt, dass initialisieren auch eine 1 darstellt, die hast du dann aber als letztes nicht berücksichtigt, hast zwar die richtige lösung gesagt aber warum keine Initialisierung erwähnt

 

[mihe7]

Zum gefühlt 300-ten Mal: entweder Vergleiche zählen oder Zuweisungen, dann kommst Du auf die Ergebnisse.

 

[abc66]

Wie kann man über 80(!) Beiträge mit dieser Aufgabe "verschwenden"?

 

[Meniskusschaden]

Wie kann man über 80(!) Beiträge mit dieser Aufgabe "verschwenden"?

Vermutlich hat @jono noch nie das Glücksgefühl einer durch eigenständiges Nachdenken erarbeiteten Erkenntnis erlebt. Aus den zeitlichen Abständen zwischen seinen Nachfragen zu den Beiträgen von @mihe7 lässt sich folgern, dass er wohl auch noch nie die Idee hatte, das mal zu versuchen.

 

[jono]

Doch hatte ich schon dank eurer Hilfe, und mit dem was ich hier gelernt habe auchschon einige Aufgaben alleine gemacht.
@Meniskusschaden , Wohlgemerkt ich bin erst beim 30. Kommentar dazu gekommen und es geht hier um 4 Aufgaben und nicht um eine Aufgabe. Ich will einfach auf Nummer sicher gehen, du könntest ja lieber schauen woran es liegt, dass ich gewisse Sachen Frage und effiziente Beiräge leisten, und daraus lässt sich wohl nicht folgern, dass ich noch die Idee hatte, da ich sonst nicht so explizit gewisse Dinge nachfragen würde.
Ist doch super, wenn du alles kannst. Aber ich weiß dass ich auch für mehrere Leute frage,
@mihe7 Dein Beitrag #73 war mir nicht ganz so einleuchtend , deshalb frage ich auch nach. Ist irgendwie meiner Ansicht nach nicht wirklich verständich, dass du irgendwie da mit Math.sin(x) ankommst.
Also mihe, da du die vielleicht Begriffe benutzt , die du vielleicht vorher definieren solltest, frage ich nochmal: Setzt du Zuweisung mit Initialisierung gleich ?
Du bringst mich halt durcheinander, wenn du mal in #51 schaust in der letzten Einfügung, da sagst du Initialisierung = 1; und Inkremente = 1;
"Zum gefühlt 300-ten Mal: entweder Vergleiche zählen oder Zuweisungen, dann kommst Du auf die Ergebnisse."
Wie lässt sich das jetzt damit in Einklang bringen? Vielleicht kann es auch mal daran liegen dass ihr das nicht besonders verständnisvoll formuliert

 

[jono]

Sag doch einfach mal ganz normal, wie ich die Komplexität der for-Schleife allgemein bewerte, rede doch nicht so um den heißen Brei. Das ist auch ein Problem.
In #51 wären die Vergleiche ja (n+1), was wären denn da die Zuweisungen?

for(int j=0; j<a.length; j++) { // (n-1)*(n+1)

Weiteres Beispiel, hier sagt man für die 2. for-Schleife aus #76(1.), es gibt n Inkrementierungen und eine Initialisierung, sodass sich n+1 ergibt.
Oder eben man zählt nur die Vergleiche, sodass sich n+1 ergibt, so korrekt? Wenn ja bitte explizit die Frage hier beantworten.

 

[mihe7]

Ist irgendwie meiner Ansicht nach nicht wirklich verständich, dass du irgendwie da mit Math.sin(x) ankommst.

Überleg mal, wie viele CPU-Zyklen man braucht, um den Sinus zu berechnen und dann überlegst Du mal, wie viele CPU-Zyklen man braucht, um eine Variable zu inkrementieren. Du wirst ja nicht behaupten wollen, dass die Zahl der Zyklen hierfür gleich sind, oder? Trotzdem wird das jeweils mit 1 bewertet. Man abstrahiert also von bestimmten Dingen, die streng genommen höchst unterschiedlich sind. Warum? Weil Größenordnungen interessieren und nicht Einzelschritte.

Setzt du Zuweisung mit Initialisierung gleich ?

Nein, Initialisierung ist die erstmalige Zuweisung eines Wertes an eine Variable.

Du bringst mich halt durcheinandeer, wenn du mal in #51 schaust in der letzten Einfügung, da sagst du Initialisierung = 1; und Inkremente = 1;

Ja, und? Ich habe auch zig-mal erklärt, dass ich eben anders gezählt habe. Genauso wie in #1 anders gezählt und in #48 anders gezählt wurde.

Wie lässt sich das jetzt damit in Einklang bringen?

s. o. (Initialisierung)

Sag doch einfach mal ganz normal, wie ich die Komplexität der for-Schleife allgemein bewerte, rede doch nicht so um den heißen Brei. Das ist auch ein Problem.

Das Problem ist, dass Du seit 50 Kommentaren nach dem Zustandekommen gegebener Schrittzahlen fragst, obwohl es Dir anscheinend nur um die Komplexität geht. Die Frage hat @httpdigest bereits in #28 beantwortet und in #73 habe ich das an Deinem Beispiel verdeutlicht und in #77 für einen komplizierteren Fall gezeigt.

 

[jono]

for(int j=0; j<a.length; j++) { // (n-1)*(n+1)

Weiteres Beispiel, hier sagt man für die 2. for-Schleife aus #76(1.), es gibt n Inkrementierungen und eine Initialisierung, sodass sich n+1 ergibt.
Oder eben man zählt nur die Vergleiche, sodass sich n+1 ergibt, so korrekt? Wenn ja bitte explizit die Frage hier beantworten.

 

[jono]

Das ist auch das, was mich so verwirrt, will einfach nur in mein Kopf einstanzen, wie das jetzt mit der unterschiedlichen Zählmethode ist, weil wenn man einmal das verwendet und einmal das und du dann irgendwas mit Zuweisungen sagst. Ich denke jetzt mal, dass du mit Zuweisungen, die erstmalige (+1) bei der Initialiserung meinst, und die weitern darauf n-mal folgenden Inkremente(bzw. Neuzuweisungen) ?
Und dann dem entsprechend entweder Vergleiche(wie bei der while-Schleife in #1) oder Zuweisungen, wie gerade von mir beschrieben.

 

[mihe7]

Weiteres Beispiel, hier sagt man für die 2. for-Schleife aus #76(1.), es gibt n Inkrementierungen und eine Initialisierung, sodass sich n+1 ergibt.
Oder eben man zählt nur die Vergleiche, sodass sich n+1 ergibt, so korrekt? Wenn ja bitte explizit die Frage hier beantworten.

Das sind die zwei Möglichkeiten, um auf die n+1 zu kommen. Für die Komplexität spielt es aber keine Rolle, was Du zählst.

dass du mit Zuweisungen, die erstmalige (+1) bei der Initialiserung meinst, und die weitern darauf n-mal folgenden Inkremente(bzw. Neuzuweisungen) ?

Klar.

Und dann dem entsprechend entweder Vergleiche(wie bei der while-Schleife in #1) oder Zuweisungen, wie gerade von mir beschrieben.

Richtig. Wie willst Du anders auf die n+1 kommen?

Wie oben schon geschrieben: für die Komplexität spielt die genaue Zahl keine Rolle. Du kannst auch Vergleiche und Zuweisungen zählen. Dann Verdoppelt sich die Anzahl der Schritte halt und der konstante Faktor 2 (Verdoppelung) fliegt am Ende raus.

1 Initialisierung + n-Inkremente + (n+1)-Vergleiche = 2*(n+1) => O(n)
1 Initialisierung + n-Inkremente => O(n)
(n+1)-Vergleiche => O(n)
n-Iterationen => O(n)

 

[jono]

public static int[] bubblesort2(int[] a) {     // n = a.length
int temp; // 1
for(int i=1; i<a.length; i++) { // n
for(int j=0; j<a.length-i; j++) { // n*(n+1)/2 - 1
if(a[j]>a[j+1]) { // (n-1)*n/2
temp=a[j]; // (n-1)*n/2
a[j]=a[j+1]; // (n-1)*n/2
a[j+1]=temp; // (n-1)*n/2
}
}
} return a; // 1

Warum ist es denn hier so, dass die äußere for-Schleife nicht mit der inneren * genommen wird, weil
"Da die Zahl der Vergleiche bekanntermaßen um 1 höher liegt, ergibt dies: 2+3+4+...+n. Ergänzt man die Summe um +1-1, erhält man (1+2+3+...+n)-1. Für den geklammerten Ausdruck liefert der kleine Gauß n*(n+1)/2, so dass man insgesamt n*(n+1)/2 - 1 erhält."
du das gesagt hast, also das "n*" ist ja nicht das von der ersten Schleife.

 

[Meniskusschaden]

also das "n*" ist ja nicht das von der ersten Schleife.

Doch, es stammt aus der äußeren Schleife..

 

[mihe7]

Warum ist es denn hier so, dass die äußere for-Schleife nicht mit der inneren * genommen wird, weil

Weil die Tabelle aus #77 die Schritte (rechte Spalte) für jede Iteration (linke Spalte) der äußeren Schleife zeigt. Schritte aufsummiert ergibt Gesamtzahl der Schritte. Multiplikation funktioniert hier nicht, weil die Anzahl der Schritte je Iteration nicht konstant ist, sondern von i abhängt.

EDIT: damit es nicht wieder zu Verwirrungen kommt: die Schritte sind in der Tabelle nur indirekt über das j gezeigt.