Space-Efficient Algorithms for Longest Increasing Subsequence
Space-Efficient Algorithms for Longest Increasing Subsequence
复制标题
DOI：
10.1007/s00224-018-09908-6
复制
发表时间：
2017-12
影响因子：
0.5
通讯作者：
Masashi Kiyomi;H. Ono;Y. Otachi;Pascal Schweitzer;J. Tarui
中科院分区：
文献类型：
--
作者：
Masashi Kiyomi;H. Ono;Y. Otachi;Pascal Schweitzer;J. Tarui
给定一个整数序列，我们想要找到该序列的最长递增子序列。众所周知，这个问题可以在时间和空间上解决。我们本文的目标是减少空间消耗，同时保持较小的时间复杂度。为此，我们提出了使用比特和时间来计算最长递增子序列的长度以及查找实际子序列的时间的算法。我们还表明，在具有规定空间量的顺序访问算法框架中，我们的算法的时间复杂度在多对数因子下是最佳的。
Given a sequence of integers, we want to find a longest increasing subsequence of the sequence. It is known that this problem can be solved intime and space. Our goal in this paper is to reduce the space consumption while keeping the time complexity small. For, we present algorithms that usebits andtime for computing the length of a longest increasing subsequence, andtime for finding an actual subsequence. We also show that the time complexity of our algorithms is optimal up to polylogarithmic factors in the framework of sequential access algorithms with the prescribed amount of space.