java - 使用递归的 O(n^2) 的最大递增子序列

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

截至我认为使用递归我们无法实现具有时间复杂度的算法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) 是当时的最大值。在最坏的情况下，您有一个已排序的数组，并且在每次检查中（如果 A[n] < x 则）您必须使用 max 更新第三个参数，这意味着您最多必须检查所有数组。

该算法从索引 n 到 n-1 取一个最大值，并用从 n 到 n-2 的最大值检查它，并用 n 到 n-3 索引中的最大值检查它，它继续用 n 到 1 检查以获得最大项目。

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

对不起图片质量:)