leetcode 121 号问题 与<算法导论>

Question

老师，请问下，leetcode 中121 号问题，用O(n) 的时间复杂度就可以搞定，但是<算法导论> 中用的分治策略 的时间复杂度是O(nlogn)的时间？ 这是同一个问题吧？

Answer 1

liuyubobobo 2018-10-03 02:12:13

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

是的，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

加油！：）

• 提问者 triump #1

  谢谢！ 老师 ： leetcode 121  和123 虽然 都可用DP思想， 但感觉好像体会的不是很深刻，能帮忙分析下？

• liuyubobobo 回复 提问者 triump #2

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