# Komplexität eines Algorithmus bestimmen



## kulturfenster (20. Aug 2007)

Hallo allerseits,
Ich habe die Aufgabe, die Komplexität des folgenden Algos zu bestimmen:

```
// Input: An array A of n integers
// Output: An array B of n integers
// Let B be a new empty array of n integers
// Let S be a new empty stack
j = 0;
for(int i = 1; i < n; i++) {
   if(A[i-1] < S.top())
      S.push(A[i-1]);
   else {
      while( A[i-1] < S.top()) {
         B[j] = S.pop();
         j++;
      }
   }
}
return B;
```

Seh ich das richtig, dass "A[i-1] < S.top()" stehts eine Exception liefert, da S ja empty ist!? Falls das stimmt, wird weder die if-Bedinungn noch die while-Schlaufe je ausgeführt. So wird lediglich die for-SChlaufe durchlaufen, was zu einer Komplexität von O(n) führt. 
Stimmt das so?

Vielen Dank für Antworten + Tipps!


----------



## SlaterB (20. Aug 2007)

warum sollte ein empty Stack zu einer Exception führen?

was stellst du dir denn unter diesem Algorithmus vor, ein Exception-Generator?
das geht auch einfacher

-------

und angenommen, es gäbe diese Exception,
wieso sollte dann die Schleife n-mal durchlaufen werden,
ist bei einer Exception nicht normalerweise Schluss?


----------



## kulturfenster (20. Aug 2007)

hmm, wenn ich mich nicht irre, sind API und mein Buch über Algos auf meiner Seite:

API:





> java.util
> Class EmptyStackException
> 
> java.lang.Object
> ...



und das BUch:


> Methods of a stack ADT:
> Top(): Return the top object on the stack, without removing it; an error occurs if the stack is empty





> und angenommen, es gäbe diese Exception,
> wieso sollte dann die Schleife n-mal durchlaufen werden,
> ist bei einer Exception nicht normalerweise Schluss?


stimmt. Also wäre die Laufzeit O(1)? Oder liege ich mit dem empty Stack falsch?  ???:L


----------



## SlaterB (20. Aug 2007)

ja, sieht so aus, falls der von dir beschriebene Stack gemeint ist,
wahrscheinlich muss der Stack mit einem Anfangssymbol gefüllt werden, das kleiner/ größer als alle A_ ist, 
eine Begrenzung/ eine Startmarkierung, gibts oft bei sowas


auch komisch:
if(A[i-1] < S.top()) 
  ..
else { 
      while( A[i-1] < S.top()) { 
..

in der Schleife im else-Fall wird die gleiche Bedingung geprüft, das ist im allgemeinen sinnlos,
eines der beiden < soll wohl ein > sein_


----------

