1. 首页
  2. 问答
  3. 排序算法的效率

排序算法的效率

2009-09-13 106 views
4

我正在研究明天的一个非常重要的采访，有一件事情我有很多麻烦：排序算法和BigO效率。排序算法的效率

什么数字很重要？最佳，最差或平均效率？

来源

2009-09-13 MedicineMan

+1

我当然希望你明天的面试官是不是因此定期:) – DVK 2009-09-13 17:18:33

+14

我不知道什么是错的问问题，以提高你的一般知识。特别是在准备面试时，你应该攻击你最擅长的领域，而不考虑面子或者看起来多么笨。根据我的经验，那些最害怕看起来像个傻瓜的人所经历的个人成长最少。 – MedicineMan 2009-09-13 18:02:25

回答

4

最差，其次是平均水平。也要意识到所谓的“隐藏常量”的真实世界影响 - 例如，经典的快速排序算法在最坏的情况下为O（n^2），平均为O（n log n），而mergesort在最坏的情况下是O（n log n），但在实践中快速排序将优于合并排序。

来源

2009-09-13 17:02:51

+0

自然归并可以离开快速排序和quickersort中的灰尘 - CFR http://svn.python.org/projects/python/trunk/Objects/listsort.txt，http://stackoverflow.com/questions/154504/is- timsort-general-purpose-or-python-specific，http://www.hatfulofhollow.com/posts/code/timsort/等等。 – 2009-09-13 17:13:30

+4

虽然这是一个很好的答案，但我必须管理员我会犹豫不决雇佣一些不明白开发者这种基本和显而易见的东西。 – DVK 2009-09-13 17:17:56

+0

DVK，你听起来像是一个象牙塔般的人，那种以最大努力小心翼翼地守卫他知识面不大的人。你是不是在这里分享你的知识，你的努力来支持社区？你担心有人会在这方面获得胜任能力，然后拿到你的工作？ – MedicineMan 2009-09-13 18:05:43

2

当然，所有这些都很重要。你必须明白一种排序算法的好处，在最糟糕的情况下，平均情况下可能会变成可怕的赤字，或者最糟糕的情况并不是那么糟糕，但最好的情况并不是那么好，它只适用于未分类的数据等。

来源

2009-09-13 17:03:56

1

我建议你不要只记住这些事实。了解他们为什么如此。如果我正在采访你，我会确保提出问题，告诉你我理解如何分析算法，而不仅仅是吐出你在网页或书中看到的东西。另外，面试之前的一天并不是进行这项学习的时间。

祝你好运！请在评论中报告它是如何去的！

来源

2009-09-13 17:14:03

+0

谢谢，记忆永远不是最好的路线，但是当面临最后期限时，我需要优先考虑大脑中发生的事情。 – MedicineMan 2009-09-13 18:06:57

2

总之。

排序算法效率会因输入数据和任务而异。

  • 排序最高速度，可以存档就是n *的log（n）
  • 如果数据包含排序的子数据，最高速度可以得到更好的那么n *的log（n）
  • 如果数据包括重复，排序可以在接近线性的时间来完成
  • 大多数排序算法都有其用途

最快速排序的变种有它的平均情况也的n * log（n）的，但你通常快于其他没有严格优化的算法。它不稳定时速度更快，但稳定的变体速度只有一小部分慢。主要问题是最坏的情况。最好的休闲解决方案是Introsort。

大部分合并排序变体的最佳，平均和最坏情况都固定为n * log（n）。它稳定并且相对容易扩展。但它需要一个相对于总项目大小的二叉树（或其仿真）。主要问题是记忆。最好的临时解决方法是timsort。

排序算法也因输入大小而异。我可以做一个新手声称，超过10T大小的数据输入，没有合并排序变种的匹配。

来源

2009-09-13 18:27:45 Margus

+0

答案没有解决发布的中心问题，但它确实提供了基于现实世界经验的各种排序表现的宝贵洞察力。 – MedicineMan 2009-09-13 18:33:47

1

我刚刚在我的大学刚刚结束了一组面试......

每个算法有它的好处，否则不会存在。 因此，它更好地理解您正在研究的算法的优点。它在哪里做得好？如何改进？

我想你需要自动执行此操作时读取各种效率符号。注意最坏的情况，并注意平均情况，最好的情况是罕见的。

一切顺利您的采访。

来源

2009-09-14 16:33:57 Lazer

相关问题

 相关问题