用递归法最大增加O(n^2)的SubSequence

Question

LIS :最长的增长子序列问题是找到一个给定序列的子序列，其中子序列的元素是排序的，从低到高。

例：

0、8、4、12、2、10、6、14、1、9、5、13、3、11、7、15 最长的增长子序列是0，2，6，9，13，15。

我可以使用不同的方法来开发LIS，比如动态编程和记忆技术，但是，对于特定的情况，我喜欢使用具有O(N^2)时间复杂性的递归来实现LIS。

到目前为止，我认为使用递归不能实现时间复杂度为O(N^2)的算法。(请纠正我)

不过，我从谷歌那里得到了这个算法

Algorithm  LIS(A,n,x)
1: if n = 0 then
2:   return 0
3: m   LIS(A; n -1; x)
4: if A[n] < x then
5:   m =max(m; 1 + LIS(A; n-1;A[n]))
6: print(m)

这个算法是O(N^2)吗？

你能解释一下吗？

Answer 1

该算法在数组中输出最大值，第一个参数(A)是数组，第二个参数(n)是现在检查最大的项的索引，第三个参数(x)在那个时候是最大的。在最坏的情况下，您有一个排序数组，并且在每次检查中(如果是

该算法从索引n到n-1取最大值，从n到n-2用max检验，在n~ n-3索引中用max检验，然后继续用n到1检验得到最大项。

这意味着它是O(n+(n-1)+(n-2)+...+2+1) = O(n^2)

​

​

对Pic的质量感到抱歉:)