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

山东大学学报(工学版) ›› 2010, Vol. 40 ›› Issue (6): 156-158.

• 其它 • 上一篇

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

杨海斌,赵学锋,王秀花,张利香

西北师范大学数学与信息科学学院, 甘肃兰州 730070

收稿日期:2009-10-20 出版日期:2010-12-16 发布日期:2009-10-20
作者简介:杨海斌(1985-),男,甘肃渭源人,硕士研究生,主要研究方向为算法设计与分析.E-mail: yanghaibin2008@126.com

An algorithm for computing the all longest increasing subsequence

YANG Hai-bin, ZHAO Xue-feng, WANG Xiu-hua, ZHANG Li-xiang

College of Mathematics and Information Science, Northwest Normal University, Lanzhou 730070, China

Received:2009-10-20 Online:2010-12-16 Published:2009-10-20

摘要/Abstract

摘要：

对计算最长增量子序列(longest increasing subsequence, LIS)的CM (Cover-Making) 算法进行详细地分析,提出一个基于CM算法的新算法,可以求出一个序列的所有最长增量子序列。它的时间复杂度是O((m+1)k+(n-k)log k), 空间复杂度是O(n+km)。

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

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).

Key words: subsequence, CM algorithm, longest increasing subsequence, all longest increasing subsequence

杨海斌,赵学锋,王秀花,张利香. 一种求所有最长增量子序列的算法[J]. 山东大学学报(工学版), 2010, 40(6): 156-158.

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 (ENGINEERING SCIENCE), 2010, 40(6): 156-158.

参考文献

多维度评价

Viewed

Full text

Abstract

Cited

Shared

Discussed

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

An algorithm for computing the all longest increasing subsequence

PDF (PC)

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 0

多维度评价

本文评价

推荐阅读 0