문자열 순열을 인쇄하는 알고리즘 - 실행 시간 분석

Question

주어진 문자열의 순열을 인쇄하는 데 다음 코드가 있습니다. 이 코드의 실행 시간을 알아 내려고 노력하고 있어요

public static int count = 0; 

public static void permute(String soFar, String strLeft) { 

    if(strLeft.length() == 1) { 
     soFar += strLeft; 
     System.out.println(++count + " :: " + soFar); 
    } 

    for(int i=0; i<strLeft.length(); i++) { 
     permute(soFar + strLeft.charAt(i), strLeft.substring(0,i) + strLeft.substring(i+1)); 
    } 
} 

/** 
* @param args 
*/ 
public static void main(String[] args) { 
    String input = "abcd"; 
    permute("",input); 
} 

[편의상 아니라 내가 노력하고 무엇에 초점을 풀어 문자열의 문자가 중복되지한다고 가정 할 수 있습니다].

지금까지의 생각을 내 체인 : 재발을 쓰려고 ,

T(n) = n * T(n-1) + O(n) for n > 1 
    = 1     for n = 1 

는 N있다! 순열 (recutive calls)의 수는 n보다 큽니다. 사실 입력 문자열이 "abcd"인 경우 (예 : 4 자), permute 함수 호출 수는 65입니다.

이 코드의 실행 시간을 찾는 방법에 대한 지침은 무엇입니까?

Answer 1

글쎄, 우선, 당신은 여분의 전화를합니다. 한 문자 만 남아 있으면 솔루션을 내 보냅니다. 그러나 여전히 permute을 빈 문자열로 호출하고 호출 횟수를 망칠 것입니다.

첫 번째 개선점은 else을 if 절에 추가하는 것입니다.

public static void permute(String soFar, String strLeft) { 

    if(strLeft.length() == 1) { 
     soFar += strLeft; 
     System.out.println(++count + " :: " + soFar); 
    } 
    else { 
     for(int i=0; i<strLeft.length(); i++) { 
      permute(soFar + strLeft.charAt(i), strLeft.substring(0,i) + strLeft.substring(i+1)); 
     } 
    } 
} 

이것은 통화 수를 41로 줄입니다. 통화 수를 계산하려면 호출 트리를 구성하고 노드 수를 계산하십시오. 각 통화는 문자열에서 하나 개의 문자를 제거함으로써 수행되는 것처럼있다 : 길이 4
1 비디오, 길이 3
4 비디오, 길이 2
12 통화 및 길이 1
24 통화

은

41까지 합계. Voilá.