역 추적 알고리즘의 시간 복잡도를 계산하는 방법

Question

이 프로그램을 사용했는지, 역 추적 알고리즘의 시간 복잡도를 계산하는 방법은 무엇입니까?

/* 
    Function to print permutations of string This function takes three parameters: 
    1. String 
    2. Starting index of the string 
    3. Ending index of the string. 
*/ 
void swap (char *x, char *y) 
{ 
    char temp; 
    temp = *x; 
    *x = *y; 
    *y = temp; 
} 

void permute(char *a, int i, int n) 
{ 
    int j; 

    if (i == n) 
    printf("%s\n", a); 
    else 
    { 
    for (j = i; j <= n; j++) 
    { 
     swap((a+i), (a+j)); 
     permute(a, i+1, n); 
     swap((a+i), (a+j)); //backtrack 
    } 
    } 
} 

Answer 1

각 permute(a,i,n)는 i == 1이 n-1 통화 ... i == n-1 한 전화가있다 i == 0가 n 통화가 permute(a,i+1,n)

따라서,에 n-i 호출됩니다.

반복 횟수에 대한 재귀 수식은 다음에서 찾을 수 있습니다.
T(1) = 1 [base]; 및 T(n) = n * T(n-1) [공정]

가 T(n) = n * T(n-1) = n * (n-1) * T(n-2) = .... = n * (n-1) * ... * 1 = n!

EDIT 총 결과 : 소형 보정]를 for 루프의 조건 때문에하는 j <= n [하지 j < n, 각 permute() 실제로 n-i+1 회 permute(a,i+1,n) 호출된다 그 결과 T (n) = (n+1) * T(n-1) [step]이고 T(0) = 1 [base]가되며, 나중에 T(n) = (n+1) * n * ... * 1 = (n+1)!이됩니다.
그러나 구현 버그보다 더 많은 기능이있는 것으로 보입니다. \

Answer 2

간단한 직감이란 n! 순열과 당신은 그들 모두를 생성해야합니다. 따라서 시간 복잡성은 적어도 n! 당신이 모든 것을 거쳐야 할 것처럼! 그들 모두를 생성하기 위해서. 따라서 시간 복잡도는 O (n!)입니다.