Сложность времени алгоритма - n или n * n?

Question

Я пытаюсь выяснить, что такое сложность Theta этого алгоритма. (а это список целых чисел)

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 

С одной стороны, я могу сказать, что append это выполняется n (длина массива) раз, так pop тоже, и последнее, что я должен рассмотреть это while состояние который мог быть выполнен вероятно 2n раз максимум.

Из этого можно сказать, что этот алгоритм не более 4*n, так что это THETA (n).

Но разве это не амортизированный анализ?

С другой стороны, я могу сказать так:

Есть 2 вложенные циклы. Цикл for выполняется точно n раз. Цикл while может быть выполнен не более n раз, так как я должен удалить элемент на каждой итерации. Таким образом, сложность THETA (n * n).

Я хочу вычислить THETA, но не знаю, какой из этих двух вариантов правильный. Не могли бы вы дать мне совет?

Answer 1

Ответ THETA(n), и ваши аргументы верны.

Это не амортизированный анализ.

Чтобы получить анализ амортизации, вы должны посмотреть на внутренний цикл. Вы не можете легко сказать, как быстро будет выполняться while, если вы игнорируете остальную часть алгоритма. Наивный подход будет O (N), и это правильно, так как это максимальное количество итераций. Однако, поскольку мы знаем, что общее число исполнений - O (N) (ваш аргумент) и что это будет выполнено N раз, мы можем сказать, что сложность внутреннего цикла O (1) амортизирована.