| 一种求所有最长增量子序列的算法 |
| |
| 引用本文： | 杨海斌,赵学锋,王秀花,张利香.一种求所有最长增量子序列的算法[J].山东大学学报(工学版),2010,40(6):156-158. |
| |
| 作者姓名： | 杨海斌 赵学锋 王秀花 张利香 |
| |
| 作者单位： | 西北师范大学数学与信息科学学院, 甘肃 兰州 730070 |
| |
| 摘 要： | 对计算最长增量子序列(longest increasing subsequence, LIS)的CM (Cover-Making) 算法进行详细地分析,提出一个基于CM算法的新算法,可以求出一个序列的所有最长增量子序列。 它的时间复杂度是O((m+1)k+(n-k)log k), 空间复杂度是O(n+km)。
|
| 关 键 词： | 子序列 CM 算法 最长增量子序列 所有最长增量子序列 |
| 收稿时间： | 2009-10-20 |
An algorithm for computing the all longest increasing subsequence |
| |
| YANG Hai-bin,ZHAO Xue-feng,WANG Xiu-hua,ZHANG Li-xiang.An algorithm for computing the all longest increasing subsequence[J].Journal of Shandong University of Technology,2010,40(6):156-158. |
| |
| Authors: | YANG Hai-bin ZHAO Xue-feng WANG Xiu-hua ZHANG Li-xiang |
| |
| Affiliation: | College of Mathematics and Information Science, Northwest Normal University, Lanzhou 730070, China |
| |
| Abstract: | 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 isO((m+1)k+(n-k)log k), and the complexity of the space is O(n+km). |
| |
| Keywords: | subsequence CM algorithm longest increasing subsequence all longest increasing subsequence |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
| 点击此处可从《山东大学学报(工学版)》浏览原始摘要信息 |
|
点击此处可从《山东大学学报(工学版)》下载全文 |
