재귀 함수의 복잡함

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 형태의 함수를 분석 할 수 있습니까? 때문에 귀하의 insert()

Answer 1

는 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)