最长上升子序列暴力解法的复杂度

来源：10-2 贪心算法与动态规划的关系 Non-overlapping Intervals

noone19

2018-01-23

老师，2^N代表子序列的个数总共有2^n情况，这个知道。那n是指啥呢，指的是子序列中求最长上升子序列的复杂度为O（n）吗

写回答

1回答

liuyubobobo

2018-01-23

已采纳

对于每一个子序列，我们还需要判断一下他是否是上升子序列，需要O(n)的复杂度：）

不过，实际使用暴力解法，也可以优化，这个判断上升子序列的过程可以在暴力枚举的时候一并完成，这样做还能进行剪枝。此时复杂度是O(2^n)的：）

noone19

liuyubobobo

嗯嗯，谢谢老师！

2018-01-23

共3条回复

玩转算法面试-- Leetcode真题分门别类讲解

课程配套大量BAT面试真题，高频算法题解析，强化训练

7410 学习 · 1150 问题

相似问题

回答 1

回答 1

回答 1

回答 1

回答 2