1回答

liuyubobobo

2018-10-03

具体你是指《算法导论》中哪里介绍的这个问题？

是的，121问题用dp思想可以直接O(n)搞定。

对于一个算法问题，尤其是在面试中，面试官希望你能从不同角度分析问题是很常见的，主要考察的还是思维。最典型的，在Leetcode的209号问题中，你还将看到follow up是要求你，如果你想的算法是O(n)，能不能提供一个O(nlogn)的算法，就是这个道理：）传送门：https://leetcode.com/problems/minimum-size-subarray-sum/description/

即使在实际中，也并非O(n)永远优于O(nlogn)，因为大O描述的是上界，但实际应用，很有可能所谓的高复杂度的算法更切合应用场景。最典型的就是在排序中，我们会用插入排序来优化归并排序或者快速排序。具体可以参见这里：https://coding.imooc.com/learn/questiondetail/76289.html

加油！：）

0

2

liuyubobobo

回复

triump

开个新帖，先把你的理解理一理，写出来，看看你能不能写明白，哪里理解的不深刻？

2018-10-05

共2条回复