遞歸函數的複雜性

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)