# Laufzeitanalyse Bubblesort



## MOEP_BIBER (23. Jun 2011)

Hey Leute,


```
for(int i = 0; i<x.length; i++){           
         for (int j=0; j < x.length-1; j++) 
            if (x[j] > x[j+1]) {                      
               temp       = x[j+1];
               x[j+1]       = x[j];
               x[j]     = temp;
            }          
      }
```

Zeile 1: 2+2n
Zeile 2: 2n+2n(n-1) (n mal Initialisierung + Vergleich, dann n*(n-1) mal Vergleich + Inkrementierung)
Zeile 3ff: 4n(n-1)

=> T(n) = 2+4n+6n(n-1)
=> T(n) = 6n²-2n+2

MfG Moep


----------



## SlaterB (23. Jun 2011)

puh, kühne Annahmen,
so genau rechnet man das nicht, du addierst jede einzelne Aktion auf, 
dabei kann eine Variablenzuweisung 10x so lange dauern wie ein Vergleich oder andersrum wer weiß das schon?

letztlich sind konstante Faktoren für Komplexität eh ziemlich egal, nur Ergebnis n^2 zählt,
und das ist hier recht schnell zu erkennen: doppelte Schleife über n macht n^2, 
wenn da drin noch ne Schleife oder ähnliches wäre, dann vielleicht noch höher, aber es ist nur konstanter Aufwand, bleibt bei n^2


----------



## MOEP_BIBER (23. Jun 2011)

Das Problem ist, dass morgen in der Prüfung schon so genau gefragt wird 
Angenommen wird, dass jede Anweisung gleich lange dauert, deshalb kann man auch dieses T(n) aufstellen.


----------



## SlaterB (23. Jun 2011)

nun, dann kann ich es dir mit Sicherheit nicht sagen weil ich so eine Rechnung noch nie gesehen (oder zumindest gemerkt) habe,
deine Aufstellung klingt mir aber schlüssig

wobei die innere Schleife ja nur bis x.length-1 läuft, also bisschen was abziehen?


----------



## MOEP_BIBER (23. Jun 2011)

achja hab ich übersehen.
Vielen Dank fürs Feedback.


----------



## SlaterB (23. Jun 2011)

anderseits ist x.lengt-1 statt x.length jedes Mal eine zusätzliche Berechnung?
das kann man beliebig kompliziert untersuchen, dann ja auch die ganzen j+1 bei den Indexen,
j++ in der Schleife ist jedenfalls auch nicht aufwendiger als [j+1] für sich


----------



## MOEP_BIBER (23. Jun 2011)

So etwas wird bei uns nicht extra als Berechnung angesehen.
Also weder das mit dem length, noch das mit dem j+1.
Ich find das auch etwas wischi waschi^^


----------



## MOEP_BIBER (23. Jun 2011)

richtige lösung: siehe 1. post


----------

