Komplexität eines Algorithmus bestimmen

[kulturfenster]

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]

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]

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

API:

java.util
Class EmptyStackException

java.lang.Object
extended by java.lang.Throwable
extended by java.lang.Exception
extended by java.lang.RuntimeException
extended by java.util.EmptyStackException

All Implemented Interfaces:
Serializable

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]

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