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

Question

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

Answer 1

liuyubobobo 2018-01-23 16:34:54

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

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

• 提问者 noone19 #1

  嗯嗯，我明白了，谢谢老师。
  转眼间老师的课程都快学完了。 可我碰到了一个问题：刷题的时候看问题确实比以前清楚了很多，知道题目大概是使用什么方法。可是真让我实打实地编码却又写不出来，看别人的代码后又恍然大悟（就比如动态规划的状态式）。这应该是题目刷的不够吧，多刷题应该能解决了吧？
  另外还有个问题想请教老师，leetcode怎么刷才能最快时间提升自己，提高自己的能力以适应开春后的实习求职呢？

• liuyubobobo 回复 提问者 noone19 #2

  看了别人的代码恍然大悟以后，一定不要照着别人的代码敲。把别人的代码关掉，用自己恍然大悟的思路自己写。如果写不出来就打开别人的代码再恍然大悟一下。别忘了总结一下为什么上次觉得自己恍然大悟了可还写不出。当然如果写出来了，可是运行发现逻辑有错误，一定要自己调试。调试是计算机专业的看家本领！在这样做的基础上，做的题目越多越好。对于大多数企业，leetcode把非hard的题目过一遍水平就绰绰有余了。如果你的时间不够，整体经历有200-300道题也差不多了。质量优先；数量其次。另外不要忘记基础。很多互联网公司的面试题是经典数据结构的实现，比如快排或者堆。提前祝offer多多！

• 提问者 noone19 回复 liuyubobobo #3

  嗯嗯，谢谢老师！