子序列的动态规划时间复杂度分析

时间复杂度分析 利用D[]，我们可以得到另外一种计算最长上升子序列长度的方法。设当前已经求出的最长上升子序列长度为len。先判断a[t]与D[len]。若a[t] > D[len]，则将a[t]接在D[len]后将得到一个更长的上升子序列，len = len + 1， D[len] = a[t]；否则，在D[1]..D[len]中，找到最大的j，满足D[j] < a[t]。令k = j + 1，则有D[j] < a[t] <= D[k]，将a[t]接在D[j]后将得到一个更长的上升子序列，同时更新D[k] = a[t]。最后，len即为所要求的最长上升子序列的长度。 这样总的时间复杂度为O(nlog(n));