贪心算法的最佳复杂度是多少？
看起来最好的复杂度是线性 O(n)。
实际情况并不重要，我所说的是一般的贪婪算法。
有时候贪心也有好处？
在我感兴趣的具体情况下，是计算变化。
假设您需要找 35 美分的零钱。你有 1、5、10、25 枚硬币。贪心算法，编码简单，可以快速轻松地解决这个问题。首先抓取 35 中最高值的 25 美分，然后再抓取 10 美分以完成总数。这将是最好的情况。当然，也有不好的情况和这种贪心算法会出现问题的情况。我说的是确定此类问题的最佳情况复杂性。
It seems like the best complexity would be linear O(n).
Doesn't matter the case really, I'm speaking of greedy algorithms in general.
Sometimes it pays off to be greedy?
In the specific case that I am interested would be computing change.
Say you need to give 35 cents in change. You have coins of 1, 5, 10, 25. The greedy algorithm, coded simply, would solve this problem quickly and easily. First grabbing 25 cents the highest value going in 35 and then next 10 cents to complete the total. This would be best case. Of course there are bad cases and cases where this greedy algorithm would have issues. I'm talking best case complexity for determining this type of problem.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
任何具有必须单独获取的
n项输出的算法最多具有O(n)时间复杂度；贪心算法也不例外。例如，背包问题的更自然的贪婪版本将 NP 完全问题转换为O(n^2)的问题 - 您尝试所有项目，选择留下最少可用空间的项目其余的;然后尝试所有剩余的，再次选择最好的；等等。每一步都是O(n)。但复杂性可以是任何东西——这取决于贪婪的难度。 （例如，像层次凝聚聚类这样的贪婪聚类算法具有O(n^2)的单独步骤来评估（至少天真地），并且需要O(n)这些步骤。）Any algorithm that has an output of
nitems that must be taken individually has at bestO(n)time complexity; greedy algorithms are no exception. A more natural greedy version of e.g. a knapsack problem converts something that is NP-complete into something that isO(n^2)--you try all items, pick the one that leaves the least free space remaining; then try all the remaining ones, pick the best again; and so on. Each step isO(n). But the complexity can be anything--it depends on how hard it is to be greedy. (For example, a greedy clustering algorithm like hierarchical agglomerative clustering has individual steps that areO(n^2)to evaluate (at least naively) and requiresO(n)of these steps.)当您谈论贪婪算法时，通常您谈论的是算法的正确性而不是时间复杂度，尤其是对于诸如更改之类的问题。
使用贪心启发法是因为它们很简单。这意味着简单问题可以轻松实现，困难问题可以合理近似。在后一种情况下，您会发现时间复杂度优于保证正确的算法。在前一种情况下，您不能指望比最佳时间复杂度更好。
When you're talking about greedy algorithms, typically you're talking about the correctness of the algorithm rather than the time complexity, especially for problems such as change making.
Greedy heuristics are used because they're simple. This means easy implementations for easy problems, and reasonable approximations for hard problems. In the latter case you'll find time complexities that are better than guaranteed correct algorithms. In the former case, you can't hope for better than optimal time complexity.
贪婪方法
nlogn + n + n² = n² 在最坏的情况下......
现在我们可以应用二分搜索而不是线性搜索......？
GREEDY APPROACH
nlogn + n + n² = n² in worst case....
now can we apply binary search instead of linear search.....?
贪婪与否本质上与计算复杂性无关，除了贪婪算法在解决相同问题时往往比其他算法更简单，因此它们往往具有较低的复杂性。
Greedy or not has essentially nothing to do with computational complexity, other than the fact that greedy algorithms tend to be simpler than other algorithms to solve the same problem, and hence they tend to have lower complexity.