1

以下代码遍历列表一次并找到 LIS。我不明白为什么 DP 算法应该采用 O(n2)。

//C
int lis(int *a, int l){
  if(l == 0) return 1;
  else if(a[l] > a[l - 1])  return  1 + lis(a, l - 1);
  else  return lis(a, l - 1);
}

int main(){
  int a[] =  { 10, 22, 9, 33, 21, 50, 41, 60 };
  cout << lis(a, sizeof(a)/sizeof(a[0]) - 1);
}

% erlang
lis([_H]) -> 1;
lis([H1, H2 |T]) when H1 > H2 ->  1 + lis([H2|T]);
lis([_H|T]) -> lis(T).

main() ->  lis(lists:reverse([ 10, 22, 9, 33, 21, 50, 41, 60 ])).
4

2 回答 2

2

您当前的lis/1函数实现是 O(n)，我看不出有任何怀疑的理由。但是有一些问题。您的实现实际上并没有计算有效的 LIS。尝试

lis(lists:reverse([1,2,3,4,1,2]))

错误示例。最长的递增序列是[1,2,3,4]，对吧？但是您的算法返回 6 作为结果。

  • 你的算法中的第一个错误是你result每次都增加，当你遇到比以前更大的元素时。但result只有当当前元素大于当前 LIS 的最大元素时，才应增加。所以（根据上面的例子）你应该记住4而不是result在你检测到之后增加 then2大于1。

  • 但这不仅仅是你必须做的事情。考虑序列1 2 3 6 4 5。对于 5 个第一个元素，LIS 的长度为 4。但那里有两个可能的选项 - 要么1 2 3 4要么1 2 3 6。您应该将哪个作为实际的 LIS？

  • 等等等等...

另一个例子直接来自维基页面。

序列[0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15]有 LIS [0, 2, 6, 9, 13, 15]（例如6元素），但你的算法说9.

而且，（纠正我，如果我错了），LIS 实现必须返回子序列本身，而不仅仅是它的长度。

于 2014-11-21T11:04:13.013 回答
2

好消息：上述实现不是二次的。

坏消息：上述函数不计算递增元素的最长子序列（定义为LIS）。

为了回答您的问题，实际的 LIS 问题具有二次复杂性，而不是 DP 算法本身，这只是迈向最终解决方案的一步。事实上，DP算法对列表的所有元素都是重复的（你需要计算所有的DP[i]），这就是为什么完整的算法被归类为O(n^2)的原因。

于 2014-11-21T11:07:42.737 回答