Рассчитать сложность времени в этой функции

Question

Учитывая эту функцию (написанную в псевдокоде), какова сложность времени?Пробуя это, я бы сказал, что временная сложность равна θ (n ^ 3) , поскольку нам нужно сначала пройти по дереву θ (n), а затем умножить вклад ANCESTOR, который равен θ (n) и вклад ADDTOQUEUE θ (n).Это правильно?

=========================================================================

ANCESTOR выполняет ряд операций, пропорциональных глубине узла

ADDTOHEAD выполняет постоянное количество операций

ADDTOQUEUE выполняет ряд операций, пропорциональных длине списка

`FUNCTION (T) / * T - дерево, заполненное целыми числами */

L.head = NULL /* L is a new empty linked list (of integers) */
RIC_FUNC(T.root,L)
return L

REC_FUNC(v,L)
if(v==NULL)return
if(ANCESTOR(v))
    ADDTOQUEUE(L,v.info)
else
    ADDHEAD(L,v.info)
 REC_FUNC(v.left,L)
 REC_FUNC(v.right,L)

``

Answer 1

В принципе, вы правы: O(n^3).

Но , у меня есть чувство (также не доказываемое вами псевдокодом), что ANCESTOR и ADDHEADс другой стороны - это означает, что на первом проходе L является коротким, а v является высоким, поэтому ANCESTOR будет длинным и ADDHEAD коротким, и после некоторых шагов они будут равны, и с этой точки v будетниже и L больше, поэтому ANCESTOR будет быстрым, но ADDHEAD будет длинным.

Если мое предположение верно, и "скорость" ADDHEAD и ANCESTOR являются одинаковая сложность в другом направлении, тогда ваша сложность равна O(n^2) (как и в каждом узле, вы получите: 1 + n, 2+ (n-1), 3+ (n-2) ...которые завершают каждый шаг в n + 1).