递归函数的复杂性

Question

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

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)