迴文分解算法的時間複雜度

Question

給定一個字符串s，分區s使分區的每個子字符串都是迴文。 返回s的所有可能的迴文分區。

我寫了一個邏輯來返回一個字符串的迴文分解，我很難駕駛這個時間複雜度。它的循環內遞歸調用

使用的邏輯是迭代每個子字符串從第一個字符開始，然後一旦我們找到迴文，我們檢查從剩餘的端口開始的下一個子字符串。我們OD這個遞歸

任何人都可以建議最好的方式在這種情況下，以推動這一

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）的時間複雜度，因爲它必須循環輸入的一半長度來執行它需要做的事情。這漸近地變成O（n），因爲你忽略了Big-O符號的常數項。

接下來，看看你的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); 
     } 
} 

之前，我們包括遞歸，看看循環和如果條件做。它們逐字符地循環輸入字符串，並在每個連續的子字符串上調用isPalendrome()函數。如果沒有子字符串中的遞歸調用，那麼您的時間複雜度爲O（n^2），因爲您正在調用isPalendrome()方法（時間複雜度爲O（n））n次。因此，每個非遞歸調用decompose()具有時間複雜度O（n^2）。

在遞歸中添加最糟糕的情況變得非常糟糕。如果每次都自行調用，複雜度將爲n*(n-1)*(n-2)*.....，簡化爲O（n！）。我通過查看if條件每次都是真的會發生什麼，我推導出n*(n-1)*(n-2)*.....作爲最壞的情況。這意味着對於for循環的每次迭代，您都可以調用該函數，並且每次在該調用時，都會每次再次調用該函數，並且該函數會一直下降，直到達到基本情況。這在數學上表示爲簡化爲O（n！）的序列，然後您必須乘以n^2。然而，這漸近地簡化爲O（n！）。最好的情況是O（n^2），這是沒有迴文的時候，平均情況會更接近於O（n^n），因爲你很可能經常在單詞內處理迴文。