는 하나의 루프

Question

와 재귀 함수의 시간 복잡도를 찾을 수 없습니다이

T (n)은 같은 재발 방정식을 만들었습니다 .I 간단한 재귀 함수 (N-1) +1 캐럿 =되어 다음

int i에 +1을 사용했습니다. 나는 이것을 이렇게 풀었습니다.

T (n) = kT (n-1) +1. . . T (N) = K^(MT ㎚) + T (1)로 설정하려면 m

-> 내지 = 1 -> m이 N-1

그것이된다 =를 (K^N-1) (N -1)

이제 내 질문은 괜찮습니까. 나는 n^2를 기대했지만 이것은 다항식으로 보이지 않습니다.

void permute(int k,int size) 
{ 
    int i; 
    for (i=k-1;i>=0;i--) 
    permute(k-1,size); 
    return; 
} 

친절이 짧은 문제

Answer 1

하자 N = 크기를 해결하는 방법을 도와주세요. 그러면

T(n,k)=k*T(n,k-1) + O(1) 
    =k*[(k-1)*T(n,k-2) + O(1)] + O(1) 
    =k*(k-1)*T(n,k-2) + k*O(1) + O(1) 
    =k*(k-1)*[(k-2)*T(n,k-3) + O(1)] + k*O(1) + O(1) 
    =k*(k-1)*(k-2)*T(n,k-3) + k*(k-1)*O(1) + k*O(1) + O(1) 
    =... 
    =O(k!)*T(n,0) + O(1) * [P(k,k-1)+P(k,k-2)+...+P(k,1)] 
    =O(k!)*T(n,0) + O(1) * e * O(k!) 
    =O(k!)*T(n,0)     

그래서 permute (0, size)의 복잡성에 따라 다릅니다.