一种求所有最长增量子序列的算法  

An algorithm for computing the all longest increasing subsequence

作　　者：杨海斌[1] 赵学锋[1] 王秀花[1] 张利香[1] 

机构地区：[1]西北师范大学数学与信息科学学院,甘肃兰州730070

出　　处：《山东大学学报（工学版）》2010年第6期156-158,共3页Journal of Shandong University（Engineering Science）

摘　　要：对计算最长增量子序列(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）.

关 键 词：子序列 CM算法 最长增量子序列 所有最长增量子序列 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]