Zeitkomplexität eines Algorithmus - n oder n * n?

Question

Ich versuche herauszufinden, welche Theta-Komplexität dieser Algorithmus ist. (a ist eine Liste von ganzen Zahlen)

def sttr(a): 
    for i in xrange(0,len(a)): 
     while s!=[] and a[i]>=a[s[-1]]: 
      s.pop() 
     s.append(i) 
    return s 

Auf der einen Seite kann ich sagen, dass appendn ausgeführt wird (Länge eines Array) Zeiten, so pop zu und das letzte, was ich beachten soll, ist die while Zustand, der wahrscheinlich 2n mal höchstens ausgeführt werden konnte.

Daraus kann ich sagen, dass dieser Algorithmus höchstens 4*n ist, so ist es THETA (n).

Aber ist es nicht amortisiert Analyse?

Auf der anderen Seite kann ich sagen:

Es gibt 2 verschachtelten Zyklen. Der for Zyklus wird genau n mal ausgeführt. Der while Zyklus könnte maximal n mal ausgeführt werden, da ich das Element in jeder Iteration entfernen muss. Also ist die Komplexität THETA (n * n).

Ich möchte THETA berechnen, weiß aber nicht, welche dieser beiden Optionen richtig ist. Könnten Sie mir einen Rat geben?

Answer 1

Die Antwort ist THETA(n) und Ihre Argumente sind korrekt.

Dies ist keine amortisierte Analyse.

Um zu einer amortisierten Analyse zu kommen, müssen Sie sich die innere Schleife ansehen. Sie können nicht einfach sagen, wie schnell die while ausgeführt wird, wenn Sie den Rest des Algorithmus ignorieren. Naive Annäherung wäre O (N) und das ist korrekt, da das die maximale Anzahl von Iterationen ist. Da wir jedoch wissen, dass die Gesamtzahl der Ausführungen O (N) ist (Ihr Argument) und dass dies N-mal ausgeführt wird, können wir sagen, dass die Komplexität der inneren Schleife O (1) amortisiert ist.