# Laufzeitanalyse von Algorithmen - Problem und Frage -



## tsluga (15. Mai 2005)

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 (17. Mai 2005)

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


----------

