请问动态规划里的最长递增子系列问题
为什么时间复杂度是 nlog2 的呀
1条回答 默认 最新
关注 1、暴力解法
- 所谓暴力解法,就是穷举所有情况。因为对于长度为 $n$ 的原序列,它的子序列总共有 $2^n$ 种情况,所以利用深度优先搜索枚举所有情况,然后取 "满足相邻两元素递增并且长度最长" 的子序列就是答案,当然这种方法肯定是不可取的,因为随着 $n$ 的不断变大,整个求解时间复杂度呈指数级增长。
2、朴素解法
- 朴素解法采用的是动态规划的思想。首先当然是设计状态。
1)设计状态
- 对于数组序列 $a_i(1 \le i \le n)$,令 $f[i]$ 表示以第 $i$ 个数 $a_i$ 结尾的最长递增子序列的长度。
- 那么,我们考虑以第 $i$ 个数 $a_i$ 结尾的最长递增子序列,它在这个序列中的前一个数一定是 $a_j(1 \le j < i)$ 中的一个,所以,如果我们已经知道了 $f[j]$,那么就有 $f[i] = f[j] + 1$。显然,我们还需要满足 $a_j < a_i$ 这个递增的限制条件。
2)状态转移方程
- 那么就可以得出状态转移方程:$$f[i] = \max_{j=1}^{i-1} (f[j] \ | \ a_j < a_i) + 1$$
- 这里 $f[j]$ 是 $f[i]$ 的子结构,而 $max(f[j])$ 是 $f[i]$ 的最优子结构,当然我们需要考虑一种情况,就是没有找到最优子结构的时候,例如:$i=1$ 或者 不存在 $a_j < a_i$ 的 $j$,此时 $f[i] = 1$,表示 $a_i$ 本身是一个长度为 $1$ 的最长递增子序列。
- $f[i]$ 数组可以通过两层循环来求解,如下图表所示:
-|-|-|-|-|-|-|- $a[i]$|1|2|4|6|3|5|9 $f[i]$|1|2|3|4|3|4|5
3)时间复杂度分析
- 状态数 $f[...]$ 总共 $O(n)$ 个,状态转移的消耗为 $O(n)$,所以总的时间复杂度为 $O(n^2)$,所以对于这类问题,一般能够接受的 $n$ 的范围在千级别,也就是 $1000, 2000, 3000 ...$。如果是 $n=10000, 100000$ 的情况,就需要考虑优化了。
- 那么,下文将介绍最长单调子序列的优化算法,基于的是 贪心 的思想,为了方便理解,将 "单调" 一词替换为 "递增"。均以 最长递增子序列 为例进行讲解。
本回答被题主选为最佳回答 , 对您是否有帮助呢?解决 无用评论 打赏 举报
悬赏问题
- ¥15 c语言怎么用printf(“\b \b”)与getch()实现黑框里写入与删除?
- ¥20 怎么用dlib库的算法识别小麦病虫害
- ¥15 华为ensp模拟器中S5700交换机在配置过程中老是反复重启
- ¥15 java写代码遇到问题,求帮助
- ¥15 uniapp uview http 如何实现统一的请求异常信息提示?
- ¥15 有了解d3和topogram.js库的吗?有偿请教
- ¥100 任意维数的K均值聚类
- ¥15 stamps做sbas-insar,时序沉降图怎么画
- ¥15 买了个传感器,根据商家发的代码和步骤使用但是代码报错了不会改,有没有人可以看看
- ¥15 关于#Java#的问题,如何解决?