摘要
对计算最长增量子序列(longest increasing subsequence,LIS)的CM(Cover-Making)算法进行详细地分析,提出一个基于CM算法的新算法,可以求出一个序列的所有最长增量子序列。它的时间复杂度是O((m+1)k+(n-k)logk),空间复杂度是O(n+km)。
The Cover-Making（CM） algorithm of the longest increasing subsequence was analyzed, and a new algorithm that can compute a sequence＇ s all longest increasing subsequences was presented, based on the CM algorithm. The complexity of the time is O（ （m ＋ 1 ）k ＋ （n- k）log k） and the complexity of the space is O（ n ＋ km）.
出处
《山东大学学报（工学版）》
CAS
北大核心
2010年第6期156-158,共3页
Journal of Shandong University（Engineering Science）
关键词
子序列
CM算法
最长增量子序列
所有最长增量子序列
subsequence
CM algorithm
longest increasing subsequence
all longest increasing subsequence
