Laufzeitanalyse Bubblesort

[MOEP_BIBER]

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]

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]

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]

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]

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

 

[SlaterB]

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]

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]

richtige lösung: siehe 1. post