我正在准备明天一场相当重要的面试，但有一件事让我十分困扰：排序算法和BigO效率。
哪个数字是需要了解的？最好的、最坏的还是平均效率？
排序算法的效率
4
- MedicineMan
2
1我真希望你明天的面试官不是 Stack Overflow 的常客 :) - DVK
15我不知道询问问题以提高你的常识有什么问题。特别是在为面试做准备时，你应该攻击自己最薄弱的领域，不必考虑面子或者看起来多傻。根据我的经验，那些最害怕像傻瓜一样被人看待的人，个人成长的程度也最少。 - MedicineMan
6个回答
4
最差的情况是最糟糕的，其次是平均情况。还要注意所谓的“隐藏常数”对现实世界的影响 - 例如，经典的快速排序算法在最坏情况下是O(n^2)，平均情况下是O(n log n)，而归并排序在最坏情况下是O(n log n)，但实际上快速排序比归并排序更高效。
- Martin DeMello
5
自然合并排序可以让快速排序和快速选择排序望尘莫及——参见http://svn.python.org/projects/python/trunk/Objects/listsort.txt，https://dev59.com/XXVC5IYBdhLWcg3w4Vb6，http://www.hatfulofhollow.com/posts/code/timsort/等等。 - Alex Martelli
4虽然这是一个很好的回答，但我必须承认，我会犹豫雇用一个连开发者这么基本和明显的东西都不理解的人。 - DVK
DVK，你听起来像是一个象牙塔式的人，这种人会非常努力地保护自己所拥有的小知识领域。难道你不是来分享你的知识，并用你的努力支持社区的吗？你是不是害怕别人会在这个领域变得能力更强，然后夺走你的工作？ - MedicineMan
Alex: 这真的很棒。我以前并不知道timsort有这么好。 - Martin DeMello
2@MedicineMan。你对@DVK的回应有点过于防御了。有一些好公司完全同意DVK的观点——这是“刷围墙”的事情。 - jamesh
2
当然，了解它们全部都很重要。你必须理解一种排序算法在平均情况下的优点可能会在最坏情况下变得非常糟糕，或者最坏情况并不那么糟糕，但最好情况并不太好，并且仅适用于未排序的数据等。
- Ed Marty
2
简而言之。
排序算法的效率会因输入数据和任务而异。
- 最快的排序速度是n*log(n)
- 如果数据包含已排序的子数据，则最快的速度可能比n*log(n)更好
- 如果数据包含重复项，则可以在接近线性时间内进行排序
- 大多数排序算法都有它们的用途
大多数快速排序变体的平均情况也是n*log(n)，但它们通常比其他未经过重度优化的算法更快。当它不稳定时，它更快，但稳定的变体只稍微慢一点。主要问题是最坏情况。最好的临时解决方案是Introsort。
大多数归并排序变体的最佳、平均和最坏情况都固定为n*log(n)。它是稳定的，相对容易扩展。但它需要一个二叉树（或其仿真），与总项目的大小相关。主要问题是内存。最好的临时解决方案是timsort。
排序算法也因输入大小而异。我可以说一个新手的观点，在10T大小的数据输入中，没有任何匹配归并排序变体。
- Margus
1
答案并没有回答中心问题，但它确实提供了基于实际经验的各种排序性能的有价值的见解。 - MedicineMan
1
我建议你不要仅仅死记硬背这些琐碎的知识点，而是要了解它们的原因。如果我在面试你，我会问你一些问题，以展示你如何分析算法，而不仅仅是能够复述网页或书本上的内容。此外，在面试前一天进行学习也不是明智之举。
祝你好运！请在评论中回报面试情况！
祝你好运！请在评论中回报面试情况！
- San Jacinto
1
谢谢，记忆并不总是最好的方法，但当面临截止日期时，我需要优先考虑哪些内容首先进入大脑。 - MedicineMan
1
我刚刚结束了大学的一轮面试...
每个算法都有其优点，否则就不会存在。因此，最好理解你正在学习的算法的好处。它在哪里表现良好？如何改进它？
我猜当你这样做时，你自然需要阅读各种效率符号。要考虑最坏情况，并注意平均情况，最佳情况很少出现。
祝你面试顺利。
- Lazer
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接