Я пытаюсь выяснить, какова сложность Theta этого алгоритма. (a — список целых чисел)
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, так что это ТЕТА (n).
Но разве это не амортизированный анализ?
С другой стороны могу сказать следующее:
Есть 2 вложенных цикла. Цикл for выполняется ровно n раз. Цикл while может выполняться не более n раз, так как мне приходится удалять элемент на каждой итерации. Таким образом, сложность равна ТЕТА (n*n).
Я хочу вычислить ТЭТА, но не знаю, какой из этих двух вариантов правильный. Не могли бы вы дать мне совет?
