Laufzeitanalyse von Algorithmen - Problem und Frage -

[tsluga]

Hey,

ich beschäftige mich grad mit der Laufzeit Analyse von Algorithmen die man so in Java schreiben kann und würde gerne wissen ob das was ich jetzt weiss, richtig ist.

int[] a = new int[n];
		int[] b = new int[n];
		int   i = 0;
		while( i != n){
			a[i] = 0;
			i    = i+1;
		}
		i = 0;
		while( i != n){
			b[i] = 0;
			i    = i + 1;
		}

Dieses hat eine Laufzeit von :

f(n) = (2n+1)(2n+1)
f(n) = 4n+2
f(n) = O(n)

Stimmt es, dasss die Schleifen eine Laufzeit von n haben, es sind aber 2, ist die Laufzeit dann n oder 2n, wegen den 2 Schleifen. Wieso lautet es eigentlich 2n, meiner Meinung nach hätte es so aussehen müssen :

( n + 1 + 1 ) " n für die Schleife und zweimal das + 1 wegen dem Vergleich und der Inkrementierung " + 1 " Die 1 wegen der Zuweisung von i + 1 " + ( n + 1 + 1) "Wieder n für die Schleifen und zweimal +1 wegen dem Verlgleich und der Inkrementierung "

Also :

f(n) = (n+1+1+1)+1+(n+1+1)
f(n) = 2n + 5
f(n) = 2n

int i = 0, j = 0;

while (i != n - 1)
{
   while (j != n - 1)
   {  
      if (b[j] > b[j + 1])
      {
	  swap(b[j],b[j+1]);
      }
      j++;
   }
   j = 0;
   i++;
}

Das müsste eine Laufzeit von O(n²) haben, da ja beide Schleifen das n-1 mal durchlaufen werden und geschachtelt sind, daher (n-1)*(n-1) = O(n²)

 

[Bleiglanz]

im Prinzip schon richtig gedacht, wo ist dein Problem?

zur ersten Frage kann ich nur sagen, dass es meistens eh völlig wurscht ist ob du n oder n+1 oder n+2 hinschreibst; und dass es keinen Konsens darüber gibt, was man überhaupt zählt

oft werden nur die "Multiplikationen und Divisionen" gezählt, manchmal auch jeder stinkige Inkrementoperator i++

wenn O(n) dasteht, dann ist nicht klar, WAS die gezählte Elementaroperation überhaupt ist...