计算时间复杂度在这个函数

Question

鉴于这种功能（用伪代码）有什么时间复杂度？尝试它，我会说，时间复杂度是θ（N ^ 3），因为我们需要遍历树第一θ（N），然后乘以祖先的贡献是θ（n）和ADDTOQUEUEθ（n）的贡献。这个对吗？

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

ANCESTOR不相称的节点的深度多项业务

ADDTOHEAD不操作的人数不变

添加到队列会进行大量操作的比例到列表的长度

`函数（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（也不受你的伪代码proveable）和ADDHEAD是相反面 - 这意味着在第一次运行L短，v高为此ANCESTOR将是漫长而ADDHEAD短，经过一番步骤他们将得到平等的，从这一点来说v较低，L是更大，所以ANCESTOR将是快，但ADDHEAD将是漫长的。

如果我的假设是正确的，ADDHEAD的“速度”和ANCESTOR在不同的方向相同的复杂，那么你是复杂O(n^2)（如在每一个节点，你将获得：1 + N +，2 +（N-1）， 3+（N-2）...，其在结束N + 1）的每个步骤。