的http://ajeetsingh.org/2013/11/12/find-longest-palindrome-sub-sequence-in-a-string/

从本网站的code：

/**
* 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"));
}

内部循环执行从i = 0到n-差距倍。怎么会没有这个算法的时间复杂度变成为O（N ^ 2）的时间？

The inner for loop executes from i=0 to n-gap times. How would does the time complexity of this algorithm turn out to be O(N^2) time?

推荐答案

的被执行的内循环体的次数是

The number of times the inner loop body is executed is