Komplexiät bestimmen (2)

[kulturfenster]

Es gilt die Laufzeit eines Algos zu bestimmen:

// INPUT: An array A of n integers.
// OUTPUT: An array B of n integers.
// Let B be an 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++;
          }
     }
}

Also, die for-Schlaufe wird ja in jedem Fall komplett durchlaufen, also hat der Algo schon mindestens eine Laufzeit von O(n).
Was ich aber leider nicht verstehe, ist die if-Anweisung. S.top() soll doch das oberete Element des Stacks wiedergeben. Führt dies nicht zu einer EmptyStackException, da der Stack ja am Anfang leer ist? So wie ich das verstehe, würde erst bei einem true in der if-Anweisung das erste Element auf den Stack geladen werden.

Vielen Dank für Tipps!

 

[Guest]

Führt dies nicht zu einer EmptyStackException, da der Stack ja am Anfang leer ist?

ja

 

[Beni]

Der Code macht für mich nicht viel Sinn, aber darum geht es in der Aufgabe ja wohl auch nicht.

Pro Durchlauf der for-Schleife wird höchstens ein Element auf den Stack gepusht, d.h. es können auch höchstens n Elemente gepoppt werden -> Laufzeit ist O( n ) (hoffe ich )