java - 最长回文子序列算法，时间分析

Question

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-gap 次。这个算法的时间复杂度怎么会变成 O(N^2) 时间？

Answer 1

内层循环体执行的次数为