algorithm - O(n) 中的最长公共子序列

Question

是否有任何可能的算法可以在 O(n) 时间内找到最长子序列的长度？我知道 O(nlogn)。

Answer 1

不，没有 LCS 算法可以为您提供 O(n) 复杂度的结果。O(nlgn) 是这个问题的最高性能。