贪婪算法的最佳复杂度是什么？
看起来最好的复杂度应该是线性O(n)。
无关紧要，我说的是贪婪的算法。
有时贪婪是值得的？
在我感兴趣的具体情况下，我感兴趣的是计算变化。
假设你需要找35美分的零钱。你有1，5，10，25的硬币。贪心算法，编码简单，可以快速、轻松地解决这个问题。首先抓取25美分，最高值在35，然后是10美分，以完成总数。这将是最好的情况。当然，在一些糟糕的情况下，这种贪婪算法也会有问题。我说的是确定这类问题的最佳案例复杂性。
回答 4
Stack Overflow用户
发布于 2011-10-10 12:01:29
任何具有必须单独获取的n项的输出的算法都具有最好的O(n)时间复杂度；贪婪算法也不例外。例如，更自然的贪婪版本的背包问题将NP完全的东西转换为O(n^2)的东西--您尝试所有项目，选择剩余的空闲空间最少的项目；然后尝试所有剩余项目，再次选择最好的项目；依此类推。每一步都是O(n)。但复杂性可以是任何东西--这取决于贪婪的难易程度。(例如，像分层聚集聚类这样的贪婪聚类算法具有单独的步骤，这些步骤是O(n^2)评估的(至少是幼稚的)，并且需要这些步骤的O(n)。)
Stack Overflow用户
发布于 2011-10-10 09:11:00
当你谈论贪婪算法时，通常你谈论的是算法的正确性，而不是时间复杂度，特别是对于像改变这样的问题。
使用贪婪启发式是因为它们很简单。这意味着对简单的问题采用简单的实现，对困难的问题采用合理的近似。在后一种情况下，你会发现时间复杂度比保证正确的算法要好。在前一种情况下，您不能期望比最佳时间复杂度更好。
Stack Overflow用户
发布于 2013-07-07 17:17:46
贪婪的方法
- problem...sort给定元素使用合并排序..(Nlogn)
- 查找将需要O(N)的最大截止日期使用线性搜索select one by one element....O(n²)
nlogn +n+ n²= n²在最坏的情况下...
现在我们可以应用二进制搜索而不是线性搜索.？
https://stackoverflow.com/questions/7707586
复制相似问题
腾讯云开发者
