算法复杂度意味着最坏情况的复杂度
我们有最好情况、平均情况和最坏情况的时间复杂度。那么有人问我们算法的复杂度他指的是什么？
We have best case, average case and worst case time complexities. So someone asks us about the complexity of an algorithm what is he referring to?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
口语化：通常，一般情况。这就是为什么人们说快速排序是 O(N log N) 时间，而哈希表查找是 O(K) 时间（K = 键大小）。最坏情况分别为 O(N^2) 和 O(K*N)。我建议要明确。
学术上：通常是最坏的情况。然而，在学术界，人们通常感兴趣的是证明给定问题的复杂性类别，而不是检查算法的复杂性。对于院士来说，算法可能只是复杂性上限的方便证明，而不是实际的研究对象。
另一个问题是“平均情况”完全取决于输入分布。大多数人都假设均匀分布，除非他们使用“现实世界”这个短语，此时任何人都可以猜测他们的输入是什么。
Colloquially: Usually, average case. This is why people say that Quicksort is O(N log N) time and a hash table lookup is O(K) time (K = key size). They are worst case O(N^2) and O(K*N), respectively. I recommend being explicit.
Academically: Usually, worst case. However, in academia people are usually interested in proving the complexity class for a given problem, rather than examining the complexity of an algorithm. For academicians, an algorithm might just be a handy proof for an upper bound on complexity rather than the actual object of study.
The other gotcha is that "average case" is entirely dependent on the input distribution. Most people assume uniform distributions, unless they use the phrase "real world" at which point it's anybody's guess what their input is.