Zeitkomplexität eines Algorithmus

mihe7

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

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

Java:
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

Top Contributor
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

Top Contributor
@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

Top Contributor

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.

Java:
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

Top Contributor
Java:
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

Top Contributor
Das müsste dann hier ja auch einmal mehr ausgeführt werden, so wie bei der while-Schleife, weil
Java:
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

Top Contributor
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

Top Contributor
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
Java:
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

Top Contributor
Weil,
Java:
i = 0;
while(i < n) und j < n(a.length)
dasselbe sind was die Wiederholungen angeht.
 

jono

Top Contributor
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 ^^
Java:
for(int j=0; j<a.length; j++)
 

mihe7

Top Contributor
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
Java:
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

Top Contributor
Java:
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

Top Contributor
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

Top Contributor
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?
 

jono

Top Contributor
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

Top Contributor
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

Top Contributor
1.
Java:
    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.
Java:
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.
Java:
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

Top Contributor
Java:
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

i0 <= j <
1n-1
2n-2
3n-3
......
n-22
n-11

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

Top Contributor
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
 

Meniskusschaden

Top Contributor
Wie kann man über 80(!) Beiträge mit dieser Aufgabe "verschwenden"? :confused:
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.:rolleyes:;)
 

jono

Top Contributor
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 :)
 
Zuletzt bearbeitet:

jono

Top Contributor
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?
Java:
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.
 
Zuletzt bearbeitet:

mihe7

Top Contributor
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

Top Contributor
Java:
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

Top Contributor
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

Top Contributor
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

Top Contributor
Java:
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.
 

mihe7

Top Contributor
Java:
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.
 

Neue Themen


Oben