最長迴文序列算法，時間分析

http://ajeetsingh.org/2013/11/12/find-longest-palindrome-sub-sequence-in-a-string/最長迴文序列算法，時間分析

從該網站的代碼：

/** 
* To find longest palindrome sub-sequence 
* It has time complexity O(N^2) 
* 
* @param source 
* @return String 
*/ 
public static String getLongestPalindromicSubSequence(String source){ 
    int n = source.length(); 
    int[][] LP = new int[n][n]; 

    //All sub strings with single character will be a plindrome of size 1 
    for(int i=0; i < n; i++){ 
     LP[i][i] = 1; 
    } 
    //Here gap represents gap between i and j. 
    for(int gap=1;gap<n;gap++){ 
     for(int i=0;i<n-gap;i++){ 
        int j=i+gap; 
        if(source.charAt(i)==source.charAt(j) && gap==1) 
         LP[i][j]=2; 
        else if(source.charAt(i)==source.charAt(j)) 
         LP[i][j]=LP[i+1][j-1]+2; 
        else 
         LP[i][j]= Math.max(LP[i][j-1], LP[i+1][j]);    
     }  
    } 
    //Rebuilding string from LP matrix 
    StringBuffer strBuff = new StringBuffer(); 
    int x = 0; 
    int y = n-1; 
    while(x < y){ 
     if(source.charAt(x) == source.charAt(y)){ 
      strBuff.append(source.charAt(x)); 
      x++; 
      y--; 
     } else if(LP[x][y-1] > LP[x+1][y]){ 
      y--; 
     } else { 
      x++; 
     } 
    } 
    StringBuffer strBuffCopy = new StringBuffer(strBuff); 
    String str = strBuffCopy.reverse().toString(); 
    if(x == y){   
     strBuff.append(source.charAt(x)).append(str); 
    } else { 
     strBuff.append(str); 
    } 
    return strBuff.toString(); 
} 

public static void main(String[] args) { 
    //System.out.println(getLongestPalindromicSubSequenceSize("XAYBZA")); 
    System.out.println(getLongestPalindromicSubSequence("XAYBZBA")); 
}

內for循環從i =執行0到n-間隙倍。這個算法的時間複雜度將如何變爲O（N^2）時間？

來源

2014-03-19 user14864

的執行內環體次數是

enter image description here

來源

2014-03-19 18:40:08

最長迴文序列算法，時間分析

回答

相關問題