complexity-theory - 递归函数的复杂度

Question

我已经编写了一个用于反转堆栈内联的函数。这两个是堆栈类的成员函数。

void reverse()
{
    int first=pop();
    if(first!=-1)
    {
        reverse();
        insert(first);
    }
}
private:
void insert(int i)
{
    int temp=pop();

    if(temp==-1)
    {
       push(i);     
    }
    else
    { 
       /* there is already a element in the stack*/
       insert(i);
       push(temp);

    }
}

现在我如何以大 O 的形式分析我的函数来计算复杂度。

Answer 1

您insert()需要O(length of the stack)时间，因为：

T(n) = T(n-1) + O(1)[to push] = O(n)

你reverse()需要O(square of the length of the stack)时间，因为：

T(n) = T(n-1) + O(n)[for insert] = O(n^2)