# Zeitkomplexität eines Algorithmus



## TheP3aceguy (25. Jan 2020)

Hallo zusammen,

wir sind momentan dabei die Komplexität eines Algorithmus in Abhängigkeit von n zu berechnen. Dazu haben wir folgende Beispielfolie bekommen: 

Leider ist das ganze nicht tiefergehend erklärt, weshalb ich absolut keine Ahnung habe, was n+1 sowie n oder auch einfach 0 oder 1 zu bedeuten haben. Ich hoffe, dass mir da jemand weiterhelfen kann.


----------



## kneitzel (25. Jan 2020)

Du hast da einen Algorithmus. Spiel den doch einfach einmal durch mit n=1, 2, 3, 4, ...
Da kannst Du dann die Schritte zählen. Wobei ich im Augenblick nicht verstehe, wieso da bei den ersten beiden Befehlen 0 angenommen wird. Aus meiner Sicht müsste das auch als 1 zu zählen sein ... Aber evtl. zählt eine Zuweisung nicht als Operation. Das muss halt einmal definiert worden sein.

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.

Und dann wird am Ende einfach aufsummiert.


----------



## TheP3aceguy (25. Jan 2020)

Okay, vielen Dank schonmal. Wir sollen nun für folgenden Code das ganze durchexerzieren.

```
public class Complexity {
    
    //K-Klasse
    
    public static int calculate(int n) {
        int k = n + 5;                                //1
        int l = 7;
        int m = -2;
        int s = 0;
        for (int i = n; i > l; i/=2) {                //n+1
            s += i;
            for (int j = 0; j < k; j++) {            //markierung
                int t = 2;
                for (int j2 = n; j2 > 0; j2--) {    //markierung
                    t++;
                    s--;
                }
                t+=t;
                while(t>0) {                        //markierung
                    for (int o = n; o < n+k+l+m; o++) {    //markierung
                        s += o*j;
                    }
                    t--;
                }
            }
        }
        return s;
    }
}
```

Jeweils dort, wo die Markierungen angebracht sind, sollen wir die Komplexität eintragen. Für die ersten beiden Markierungen hab ich das auch schonmal versucht, weiß da jedoch nicht, ob das so richtig ist. Bei den weiteren Markierungen habe ich noch keine Ahnung, was ich dort einfüllen soll.


----------



## kneitzel (25. Jan 2020)

Hmm, Du hast eine Schleife, die bei n anfängt, den Wert immer halbiert und so lange läuft, bis der wert nicht mehr größer als 1 ist...
==> Ich denke nicht, dass dies n+1 mal durchlaufen wird...
Spiel es doch mal mit n=8 durch ....
8>1, 4>1, 2>1, 1>1 .... Da komme ich nicht auf 9 Vergleiche ... Oder habe ich übersehen, dass i in der Schleife verändert wird?


----------



## TheP3aceguy (25. Jan 2020)

Stimmt, ich habs mal versucht zu korrigieren:


```
public class Complexity {
    
    //K-Klasse
    
    public static int calculate(int n) {
        int k = n + 5;                                //1
        int l = 7;
        int m = -2;
        int s = 0;
        for (int i = n; i > l; i/=2) {                //(n/2)+1
            s += i;
            for (int j = 0; j < k; j++) {            //markierung
                int t = 2;
                for (int j2 = n; j2 > 0; j2--) {    //n+1
                    t++;
                    s--;
                }
                t+=t;
                while(t>0) {                        //markierung
                    for (int o = n; o < n+k+l+m; o++) {    //markierung
                        s += o*j;
                    }
                    t--;
                }
            }
        }
        return s;
    }
}
```


----------



## httpdigest (25. Jan 2020)

`(n/2)+1` ist doch ziemlich offensichtlich auch falsch, bzw. generell `(n/k)+c` wird falsch sein für jedes `k` und jedes `c`. Für `n` = 100 sind es nur 4 Schritte (100, 50, 25, 12) und nicht (100/2)+1 also 51... Spiele es doch selber einfach immer durch.
Du benötigst eine Funktion, die in der Komplexitätstheorie sehr häufig verwendet wird, z.B. für die Zeitkomplexität von Suchen und Sortieren...


----------



## TheP3aceguy (25. Jan 2020)

httpdigest hat gesagt.:


> `(n/2)+1` ist doch ziemlich offensichtlich auch falsch, bzw. generell `(n/k)+c` wird falsch sein für jedes `k` und jedes `c`. Für `n` = 100 sind es nur 4 Schritte (100, 50, 25, 12) und nicht (100/2)+1 also 51... Spiele es doch selber einfach immer durch.
> Du benötigst eine Funktion, die in der Komplexitätstheorie sehr häufig verwendet wird, z.B. für die Zeitkomplexität von Suchen und Sortieren...



Ich bin jetzt einmal den Foliensatz sowie den Wikipedia Artikel zu Sortierverfahren durchgegangen und habe keine Funktion gefunden, die mir für n=100 4 ausspuckt. Ich hab wirklich keine Ahnung, wie man auf die Funktion kommen soll


----------



## httpdigest (25. Jan 2020)

Du benötigst den Logarithmus zur Basis 2. Und ganz konkret ist die Anzahl der Schritte in dieser Schleife `log2(n) - log2(7)`. Da aber `log2(7)` eine additive Konstante ist, wird diese bei der asymptotischen Laufzeit weggelassen. Also: `log2(n)`.
Desweiteren verwendet man ja meist nicht den Logarithmus zur Basis 2, sondern zur Basis `e` (Eulersche Zahl), geschrieben `ln(n)`, auch "natürlicher Logarithmus" genannt.
Das kann man hier auch machen, denn: `ln(n) = log2(n) * 1/log2(e)`. Hier ist `1/log2(e)` ein konstanter Faktor und kann ebenfalls entfallen.
Es ergibt sich also: `ln(n)`


----------



## TheP3aceguy (25. Jan 2020)

httpdigest hat gesagt.:


> Du benötigst den Logarithmus zur Basis 2. Und ganz konkret ist die Anzahl der Schritte in dieser Schleife `log2(n) - log2(7)`. Da aber `log2(7)` eine additive Konstante ist, wird diese bei der asymptotischen Laufzeit weggelassen. Also: `log2(n)`.
> Desweiteren verwendet man ja meist nicht den Logarithmus zur Basis 2, sondern zur Basis `e` (Eulersche Zahl), geschrieben `ln(n)`, auch "natürlicher Logarithmus" genannt.
> Das kann man hier auch machen, denn: `ln(n) = log2(n) * 1/log2(e)`. Hier ist `1/log2(e)` ein konstanter Faktor und kann ebenfalls entfallen.
> Es ergibt sich also: `ln(n)`



Okay, alles klar, dankeschön. Und wie kommt man als "Laie" auf sowas?


----------



## httpdigest (25. Jan 2020)

Ich nehme mal stark an, dass die Logarithmusfunktion bereits in einer Komplexitätslehren-Vorlesung erwähnt wurde. Sonst wird's schwer, von selbst darauf zu kommen. Aber im Allgemeinen beantwortet dir der Logarithmus von `n` zur Basis `k` quasi die Frage: "Wie oft muss ich `k` mit sich selbst multiplizieren, um `n` zu erhalten.". Es ist also quasi die Umkehrfunktion zur Exponentiation.
Das sollte man auch schon in der Schule gehabt haben.


----------



## kneitzel (25. Jan 2020)

Ohh ... ich habe mich gerade total gewundert.... das ist >l und nicht >1 ... das nur als kleine Anmerkung zu meinem Beitrag #4. Denn das ist da natürlich falsch.... und ich wundere mich, dass @httpdigest bei 12 aufhört. 

Wobei sich da auch ein kleiner Fehler eingeschlichen hat, denn die Prüfung wird doch auch noch für die 6 durchgeführt und da die nicht größer 7 ist, bricht die Schleife ab. Aber das muss er ja noch prüfen....


----------



## httpdigest (25. Jan 2020)

JustNobody hat gesagt.:


> Aber das muss er ja noch prüfen....


Die Prüfung der Schleifenbedingung selbst zählt hier nicht zur Komplexität, sondern die tatsächliche Iteration, also was in dem Schleifen-Body getan wird. Denn das multiplizieren wir ja dann mit der Komplexität der Schleife. Spielt aber sowieso alles keine Rolle, da das eben nur ein konstanter Faktor sein wird.


----------



## TheP3aceguy (25. Jan 2020)

JustNobody hat gesagt.:


> Ohh ... ich habe mich gerade total gewundert.... das ist >l und nicht >1 ... das nur als kleine Anmerkung zu meinem Beitrag #4. Denn das ist da natürlich falsch.... und ich wundere mich, dass @httpdigest bei 12 aufhört.
> 
> Wobei sich da auch ein kleiner Fehler eingeschlichen hat, denn die Prüfung wird doch auch noch für die 6 durchgeführt und da die nicht größer 7 ist, bricht die Schleife ab. Aber das muss er ja noch prüfen....



Jap, ist mir auch erst aufgrund von @httpdigest aufgefallen.

Nun Folgendes bei der nächsten Markierung: 
	
	
	
	





```
for (int j = 0; j < k; j++) {            //markierung
```

n hat doch mit der Zeile augenscheinlich ja erstmal nichts zu tun. Hab ich dann dort eine Null oder wie ist das aufzulösen?


----------



## httpdigest (25. Jan 2020)

_Augenscheinlich _ist richtig. Da aber `k = n + 5` ist (siehe oben), gilt quasi:

```
for (int j = 0; j < n + 5; j++) {...}
```


----------



## kneitzel (25. Jan 2020)

Ok, dann bin ich da jetzt irgendwie zu lange aus dieser Thematik raus. Ich hatte in #1 den Punkt 3 so verstanden, dass die letzte Prüfung auch mitgezählt wird, denn da ist es ja auch n+1 und nicht n ... Aber evtl. ist es dann einfach das Beste, wenn ich dies nur noch lesend verfolge, um hier niemanden zu verwirren, denn ich bezweifle, dass ich groß mehr beitragen kann als Du


----------



## Xyz1 (25. Jan 2020)

Ich glaub @httpdigest ist Mathematikprofessor oder Ähnliches, er beharrt immer so darauf, irgendetwas zu wissen...

Ganz pragmatisch gesehen musst du einfach nur für jede for und jede while ausbaldowern wie oft diese durchlaufen wird.


----------



## httpdigest (25. Jan 2020)

Tobias-nrw hat gesagt.:


> Ich glaub @httpdigest ist Mathematikprofessor oder Ähnliches, er beharrt immer so darauf, irgendetwas zu wissen...


Ich beharre nicht darauf, etwas zu wissen... Ich sage nur, wie es ist.



Tobias-nrw hat gesagt.:


> musst du einfach nur für jede for und jede while ausbaldowern *wie oft diese durchlaufen wird*.


Genau meine Rede. Aber wie gesagt, ist es irrelevant, ob man nun die Prüfung der letzten Iteration mit reinrechnet oder nicht. Es ist dann nur eine Konstante die noch hinzukommt, also egal.


----------



## TheP3aceguy (25. Jan 2020)

httpdigest hat gesagt.:


> _Augenscheinlich _ist richtig. Da aber `k = n + 5` ist (siehe oben), gilt quasi:
> 
> ```
> for (int j = 0; j < n + 5; j++) {...}
> ```



Ich schätze mal _n+4_ wäre zu einfach, oder?


----------



## httpdigest (25. Jan 2020)

TheP3aceguy hat gesagt.:


> Ich schätze mal _n+4_ wäre zu einfach, oder?


Nein, wieso? Wäre exakt richtig. Und _asymptotisch _dann halt O(n).

EDIT: Also ganz exakt korrekt wäre `n + *5*`, weil die Schleife ja bei 0 anfängt.


----------



## TheP3aceguy (25. Jan 2020)

Gut, dann schätze ich einfach mal: 
	
	
	
	





```
for (int j2 = n; j2 > 0; j2--) {    //n-1 EDIT: Müsste eigentlich nur n sein oder?
```


Für die letzten beiden bräuchte ich dann aber auch nochmal Unterstützung:

```
while(t>0) {                        //markierung
                    for (int o = n; o < n+k+l+m; o++) {    //markierung
                        s += o*j;
                    }
                    t--;
```

und wenn ich _o <_ _n+k+l+m_ mal auflöse, bekomme ich ja  n < 2n+10 raus, richtig?


----------



## misterx09 (26. Jan 2020)

TheP3aceguy hat gesagt.:


> Gut, dann schätze ich einfach mal:
> 
> 
> 
> ...



Hallo,

habe bei den 2 unteren, habe ich das selbe Problem.

TheP3aceguy hast du vllt. ne Lösung oder jemand anders?


----------



## Plauzi92 (26. Jan 2020)

Hänge auch an der gleichen Aufgabe 



> Gut, dann schätze ich einfach mal:
> Java:
> for (int j2 = n; j2 > 0; j2--) {    //n-1 EDIT: Müsste eigentlich nur n sein oder?



n-1 wäre es doch so oder so nicht. Wenn n = 1, wird die Schleife einmal durchlaufen also n.

Für die Komplexität der While Schleife musst du ja wissen wie groß t in Abhängigkeit von n ist. Das bekomme ich aber auch nicht wirklich hin weil sich n ja nach jedem Aufruf um 1 erhöht und dann verdoppelt. Ich kenne keinen mathematischen Ausdruck dafür.

Meine Idee wäre ( n * (n+1) + n) * 2

Das stimmt zumindest annähernd.


Hast du es mittlerweile gelöst?


----------



## httpdigest (26. Jan 2020)

```
int k = n + 5;
int l = 7;
int m = -2;
int s = 0;
for (int i = n; i > l; i /= 2) { // log2(n) - log2(7)
  s += i;
  for (int j = 0; j < k; j++) { // n + 5, da k = n + 5
    int t = 2; // <- Achtung, t wird hier immer auf 2 gesetzt!
    for (int j2 = n; j2 > 0; j2--) { // n
      t++;
      s--;
    }
    // hier ist t immer n + 2, da t in der oberen Schleife n Mal um 1 inkrementiert wird
    t += t;
    // hier ist t immer 2n + 4, da t einfach verdoppelt wird
    while (t > 0) { // 2n + 4, da t ganz unten immer um 1 dekrementiert wird
      for (int o = n; o < n + k + l + m; o++) {
        /*
         * Für die Betrachtung der Anzahl der Iterationen,
         * ist diese Schleife quasi dasselbe wie:
         * for (int o = 0; o < k + l + m; o++) {
         *
         * wenn wir jetzt noch Variablenwerte einsetzen
         * und vereinfachen, erhalten wir:
         * for (int o = 0; o < n + 10; o++) {
         *
         * Somit läuft die ganze Schleife für: n + 10
         */
        s += o * j;
      }
      t--;
    }
  }
}
```


----------



## misterx09 (26. Jan 2020)

httpdigest hat gesagt.:


> ```
> int k = n + 5;
> int l = 7;
> int m = -2;
> ...



Danke für die schnelle Antwort.

Habe noch eine Frage, wir müssen jetzt noch die Komplexitätsklasse berechnen.

Die Formel habe ich auf gestellt aber ich komme nicht auf das Ergebnis. 

// 1 + log2 (n) – log2 (7) + n+5 + n+ 2n+4 + n+10
// 5n + 19 + ?? hier weis ich nicht wie ich es auflösen soll, kann mir jemand vllt. einen Hinweis geben?


----------



## httpdigest (26. Jan 2020)

Du musst doch einfach nur die Laufzeiten für verschachtelte Schleifen miteinander multiplizieren und für Schleifen auf derselben Ebene addieren...
So schwer ist das doch nun wirklich nicht.
Wenn:

```
for (int i = 0; i < n; i++) { // n
  for (int j = 0; j < n + 5; j++) { // n + 5
    ...
  }
}
```
dann: n * (n + 5)


----------



## misterx09 (26. Jan 2020)

httpdigest hat gesagt.:


> Du musst doch einfach nur die Laufzeiten für verschachtelte Schleifen miteinander multiplizieren und für Schleifen auf derselben Ebene addieren...
> So schwer ist das doch nun wirklich nicht.
> Wenn:
> 
> ...



das ist mir klar, ich habe mich eher auf der 1+log2(n)-log2(7) teil bezogen.


----------



## httpdigest (26. Jan 2020)

misterx09 hat gesagt.:


> das ist mir klar, ich habe mich eher auf der 1+log2(n)-log2(7) teil bezogen.


Wenn dir das klar ist, dann sollte dir auch klar sein, dass `...+n+5+n+2n+4+n+10` und `...+5n+19` komplett falsch ist.
Darauf bezog ich mich eher.


----------



## httpdigest (26. Jan 2020)

Irgendwie will ich das ganze hier mal abkürzen. Hier erstmal der Ausdruck, der die Anzahl an Operationen beschreibt und den man erhält, wenn man nach dem genannten Schema vorgeht (Laufzeiten von verschachtelten Schleifen multiplizieren und von Schleifen auf selber Ebene addieren):

(log₂(n) - log₂(7)) * (n + 5) * (n + (2n + 4) * (n + 10))

Ganz genau: ceil(log₂(n) - log₂(7)) * (n + 5) * (n + (2n + 4) * (n + 10))
wobei ceil() die "Aufrunden"-Funktion ist, aber das vernachlässigen wir hier mal.

Den hinteren Teil noch in eine schöne polynomielle Form ausmultiplizieren, um den größten Exponenten von n zu erkennen:
(log₂(n) - log₂(7)) * (2n³ + 35n² + 165n + 200)

Um davon die Komplexitätsklasse zu ermitteln, einfach erstmal alle Faktoren von jeder Potenz von n (auch 0, also Konstanten) entfernen:

log₂(n) * (n³ + n² + n)

Dann bei Polynomen einfach den größten Exponenten von n verwenden, hier 3:

log₂(n) * n³

Wenn man will, kann man jetzt auch zu dem natürlichen Logarithmus wechseln, da (wie in einem anderen Beitrag erklärt) log₂(n) dasselbe ist wie ln(n)/ln(2), also der konstante Faktor 1/ln(2) entsteht und konstante Faktoren können vernachlässigt werden:

ln(n) * n³

Schieben wir noch den Faktor nach ganz vorne, der sich am schnellsten erhöht, erreichen wir das Ergebnis:

O(n³ln(n))


----------



## misterx09 (26. Jan 2020)

.


----------



## jono (22. Feb 2020)

```
public class Complexity { 
// O(nˆ3 log (n))
 public static int calculate ( int n) {
 int k = n + 5; // 1
 int l = 7;
 int m = −2; 
int s = 0;
 for ( int i = n; i > l ; i /=2) { // log (n) − 3 
s += i ; for ( int j = 0; j < k ; j++) { //( log (n) − 4) (n + 6) 
int t = 2; 
for ( int j2 = n; j2 > 0; j2−−) { //( log (n) − 4) (n + 5)
 (n + 1)
 t++; 
s−−; 
} t+=t ; // t = (n + 2) 2 = 2n + 4
 while(t>0) //( log (n) − 4) (n + 5)
5) (2n + 5)
 for ( int o = n; o < n+k+l+m; o++) //( log (n) − 4) (n + 5)
 (2n + 4) (n + 11)
 s += o∗j ;
t −−; 
} 
} return s ; 
}
 }
```
Kann mir jemand erklären wie ich hier z.B bei der ersten for-Schleife auf log(n)-3 komme? Habe es nicht wirklich verstanden , weil das hier ja nicht genannt worden ist in der Lösung, die ich hier poste


----------



## httpdigest (22. Feb 2020)

jono hat gesagt.:


> Kann mir jemand erklären wie ich hier z.B bei der ersten for-Schleife auf log(n)-3 komme?


Also log₂(n) deswegen, weil hier `i` immer halbiert wird. Und wir wollen wissen, wie häufig halbiert werden muss. Und die Subtraktion von log₂(7) (was aufgerundet gleich 3 ergibt), weil `i` ja nur bis größer als 7 gehen soll (das ist ein kleines "L" und keine Eins in der Schleifenbedingung).
Alternativ kann man auch log₂(n/7) schreiben.


----------



## jono (22. Feb 2020)

Okay, das habe ich verstanden, wie wäre das denn dann bei der 2. und 3. for Schleife


----------



## httpdigest (22. Feb 2020)

Zeitkomplexität eines Algorithmus
					

Hallo zusammen,  wir sind momentan dabei die Komplexität eines Algorithmus in Abhängigkeit von n zu berechnen. Dazu haben wir folgende Beispielfolie bekommen:   Leider ist das ganze nicht tiefergehend erklärt, weshalb ich absolut keine Ahnung habe, was n+1 sowie n oder auch einfach 0 oder 1 zu...



					www.java-forum.org


----------



## jono (22. Feb 2020)

Du hast da aber nur n+5 stehen


----------



## jono (22. Feb 2020)

Hier steht ja (log(n) -4) (n+6)


----------



## httpdigest (22. Feb 2020)

jono hat gesagt.:


> Du hast da aber nur n+5 stehen


Nein, da steht: "n + 5, da k = n + 5".
Und dann sollte es eigentlich sehr verständlich sein, warum n + 5.
n + 5 bezieht sich bei mir nur darauf, wie viele Iterationen diese eine Schleife für sich gesehen hat, nicht, wie häufig sie insgesamt ausgeführt wird.


----------



## jono (22. Feb 2020)

In der Lösung steht ja (log(n) -4) (n+6)


----------



## httpdigest (22. Feb 2020)

Die von dir präsentierte Lösung nicht nicht 100%ig korrekt. Es gibt keinen Grund, warum aus `log₂(n)-3` der äußeren Schleife plötzlich `log₂(n)-4` bei der inneren Schleife wird.
Die ganz exakte Lösung für die Anzahl an Operationen (Ausführungen der inneren Schleifen) ist:
`ceil(log₂(n/7)) * (n + 5) * (n + (2n + 4) * (n + 10))`


----------



## jono (22. Feb 2020)

Das hilft mir jetzt nicht wirklich weiter


----------



## jono (22. Feb 2020)

Geringe Abweichungen sind ja erlaubt, wäre es dann mit (log(n) -3) (n+5) richtig  bei der 2. for schleife?


----------



## httpdigest (22. Feb 2020)

jono hat gesagt.:


> Das hilft mir jetzt nicht wirklich weiter


Mehr als, dass deine Lösung falsch ist, kann ich halt auch nicht dazu sagen. Und wie man auf `(log(n) - 4) (n+6)` für die zweite innere Schleife kommt, kann ich dir auch nicht sagen, weil das ebenfalls falsch ist.


jono hat gesagt.:


> Geringe Abweichungen sind ja erlaubt


Die "Abweichungen", wie du sie bezeichnest, kommen erst dann zum Tragen, wenn du für die Anzahl der Operationen eine Komplexitätsklasse bestimmen willst. Dort und nur dort kannst du dann Konstanten und lineare Faktoren eliminieren.


jono hat gesagt.:


> wäre es dann mit (log(n) -3) (n+5) richtig bei der 2. for schleife


Ja.


----------



## jono (23. Feb 2020)

Ja, dann haben die ja eine super Lösung hochgeladen. Liegt nicht an mir ^^
Du meintest ja "Also log₂(n) deswegen, weil hier `i` immer halbiert wird."
Wo besteht denn ein Zusammenhang zwischen der Halbierung und dem log₂?
Und warum kommt bei den nächsten Schleifen dann auch das log(n)-3 hin ?
Wird das weiterhin übernommen, weil das die inneren Schleifen sind ?
Wäre dann bei 

```
while(t > 0)
for(int o = n; o < n+k+l+m; o++)  // (n+10)
```
korrekt?


----------



## mihe7 (23. Feb 2020)

jono hat gesagt.:


> Wo besteht denn ein Zusammenhang zwischen der Halbierung und dem log₂?


log₂(2^x) = x


----------



## jono (24. Feb 2020)

Ja, das weiß ich ja auch, verstehe gerade nur nicht warum das dann mit der Halbierung zu tun hat..


----------



## mihe7 (24. Feb 2020)

jono hat gesagt.:


> Ja, das weiß ich ja auch, verstehe gerade nur nicht warum das dann mit der Halbierung zu tun hat..


Was ist denn 2^x?


----------



## abc66 (24. Feb 2020)

(y^2)^(1/2) = y


----------



## jono (24. Feb 2020)

@mihe7 , Gut ist verstanden.


----------



## jono (24. Feb 2020)

```
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
```
Wie komme ich hier in der zweiten for-Schleife auf (n-1)*(n+1) und warum (n-1)*n für die if-Bedingung?


----------



## jono (24. Feb 2020)

Ich habe schon einiges verstanden, diese Aufgabe auch versucht nachvollziehen zu können hinsichtlich meiner Fragen, jedoch keine Idee.
Bitte um verständnisvolle Weiterhilfe


----------



## jono (24. Feb 2020)

@JustNobody Kannst du mir bitte eventuell weiterhelfen?


----------



## mihe7 (24. Feb 2020)

jono hat gesagt.:


> 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 (25. Feb 2020)

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 (25. Feb 2020)

@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 (25. Feb 2020)

jono hat gesagt.:


> if-Schleife?





			if-schleife.de
		




jono hat gesagt.:


> 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


jono hat gesagt.:


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



jono hat gesagt.:


> 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 (25. Feb 2020)

```
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 (25. Feb 2020)

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 (25. Feb 2020)

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 (25. Feb 2020)

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 (25. Feb 2020)

Weil,

```
i = 0;
while(i < n) und j < n(a.length)
```
dasselbe sind was die Wiederholungen angeht.


----------



## jono (25. Feb 2020)

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 (25. Feb 2020)

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


jono hat gesagt.:


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


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


----------



## jono (25. Feb 2020)

```
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 (25. Feb 2020)

Hat sich erledigt


----------



## jono (25. Feb 2020)

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 (25. Feb 2020)

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 (25. Feb 2020)

jono hat gesagt.:


> 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 (25. Feb 2020)

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 (25. Feb 2020)

jono hat gesagt.:


> 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 (25. Feb 2020)

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


----------



## mihe7 (25. Feb 2020)

jono hat gesagt.:


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


Ja, oder eben die Vergleiche.


----------



## jono (25. Feb 2020)

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


----------



## jono (25. Feb 2020)

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


----------



## mihe7 (25. Feb 2020)

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 (25. Feb 2020)

Was meinst du jetzt mot exakter Schrittzahl genau?


----------



## mihe7 (25. Feb 2020)

jono hat gesagt.:


> 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 (26. Feb 2020)

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 (26. Feb 2020)

jono hat gesagt.:


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



jono hat gesagt.:


> 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-12n-23n-3......n-22n-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.



jono hat gesagt.:


> 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 (26. Feb 2020)

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


----------



## jono (26. Feb 2020)

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


----------



## mihe7 (26. Feb 2020)

Scroll rauf und lies nach.


----------



## jono (26. Feb 2020)

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 (26. Feb 2020)

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


----------



## abc66 (26. Feb 2020)

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


----------



## Meniskusschaden (26. Feb 2020)

abc66 hat gesagt.:


> 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 (27. Feb 2020)

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 (27. Feb 2020)

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 (27. Feb 2020)

jono hat gesagt.:


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



jono hat gesagt.:


> Setzt du Zuweisung mit Initialisierung gleich ?


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



jono hat gesagt.:


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



jono hat gesagt.:


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


s. o. (Initialisierung)



jono hat gesagt.:


> 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 (27. Feb 2020)

```
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 (27. Feb 2020)

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 (27. Feb 2020)

jono hat gesagt.:


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



jono hat gesagt.:


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


Klar.



jono hat gesagt.:


> 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 (28. Feb 2020)

```
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 (28. Feb 2020)

jono hat gesagt.:


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


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


----------



## mihe7 (28. Feb 2020)

jono hat gesagt.:


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


----------

