회문 분해 알고리즘의 시간 복잡도

Question

문자열 s가 주어지면 파티션의 모든 부분 문자열이 회문이되도록 파티션을 만듭니다. s의 모든 palindrome 파티셔닝을 반환합니다.

나는 회문의 회문 분해를 되돌리기위한 논리를 썼다. 나는이 시간 복잡성을 몰아 가는데 어려움을 겪고있다. 루프 내에서 재귀 호출

논리는 첫 번째 문자부터 시작하여 각 부분 문자열을 반복하고, 회귀선을 찾으면 나머지 부분부터 시작하여 다음 하위 문자열을 검사합니다. 우리는 중독이 반복적으로

사람이

public class Solution { 
public List<List<String>> partition(String s) { 
    List<List<String>> result = new ArrayList<List<String>>(); 
    List<String> palindromePartition = new ArrayList<String>(); 
    int start=0; 

    decompose(s,0,palindromePartition,result); 
    return result; 

} 

private void decompose(String input,int startIndex,List<String> palindromePartition,List<List<String>> result) { 
    if(startIndex==input.length()) 
     { 
      ArrayList<String> partitionResult = new ArrayList<String>(palindromePartition); 
      result.add(partitionResult); 
      return; 
     } 

    for(int i=startIndex+1;i<=input.length();i++){ 
      if(isPalindrome(input.substring(startIndex,i))){ 
       palindromePartition.add(input.substring(startIndex,i)); 
       decompose(input,i,palindromePartition,result); 
       palindromePartition.remove(palindromePartition.size()-1); 

      } 

    } 

} 

private boolean isPalindrome(String input){ 
    int left=0; 
    int right=input.length()-1; 
    while(right>left){ 
      if(input.charAt(left)!=input.charAt(right)) 
       return false; 
      left++; 
      right--; 
    } 
    return true; 
} 

Answer 1

이 isPalindrome() 방법을보고, 시작하려면 이러한 경우에이 운전하는 최상의 방법 제안 할 수 있습니다 :이 방법은 본다

private boolean isPalindrome(String input){ 
    int left=0; 
    int right=input.length()-1; 
    while(right>left){ 
      if(input.charAt(left)!=input.charAt(right)) 
       return false; 
      left++; 
      right--; 
    } 
    return true; 
} 

을 문자열의 처음 문자와 마지막 문자를 비교하여 비교합니다. O (n/2)의 시간 복잡성은 입력의 길이의 절반을 반복해야하므로 수행해야 할 작업을 수행해야하기 때문에 복잡합니다. 이것은 Big-O 표기법에 대한 상수 항을 무시하기 때문에 점근 적으로 O (n)이됩니다.

다음으로 decompose() 방법을 살펴보십시오. 이 선들은 시간 복잡성을 유도하는 데 중요한 역할을합니다.

for(int i=startIndex+1;i<=input.length();i++){ 
     if(isPalindrome(input.substring(startIndex,i))){ 
      palindromePartition.add(input.substring(startIndex,i)); 
      decompose(input,i,palindromePartition,result); 
      palindromePartition.remove(palindromePartition.size()-1); 
     } 
} 

루프를 포함하기 전에 루프와 if-condition이 수행하는 작업을 살펴보십시오. 문자로 입력 문자열을 반복하고 각각의 연속 된 하위 문자열에서 isPalendrome() 함수를 호출하십시오. 하위 문자열 내에서 재귀 호출이 없으면 isPalendrome() 메서드 (시간 복잡성 O (n))를 n 번 호출 할 때 시간 복잡성 O (n^2)가 발생합니다. 따라서, decompose()의 각각의 비 재귀 호출은 시간 복잡성 O (n^2)를 갖는다.

재귀를 추가하면 최악의 상황이 상당히 나빠집니다. 매번 스스로를 호출하면 복잡성은 n*(n-1)*(n-2)*.....이되며 O (n!)는 단순화됩니다. 나는 if-condition이 매번 true 일 때 일어날 일을 살펴봄으로써 최악의 경우 인 n*(n-1)*(n-2)*.....을 도출했습니다. 즉, for 루프를 반복 할 때마다 함수를 호출하고 매번 호출 할 때마다 매번 함수를 다시 호출해야하며 기본 사례에 도달 할 때까지 아래로 이동합니다. 이것은 수학적으로 O (n!)로 단순화되는 시퀀스이며, 그러면 n^2로 곱해야합니다. 그러나 이것은 O (n!)에 점근 적으로 단순화됩니다. 가장 좋은 경우는 O (n^2)이며, 이는 문장이없고, 평균 경우가 O (n^n)에 더 가깝습니다. 단어 내에서 문장을 자주 사용하기 때문에 가능합니다.