algorithm - 排序算法的效率

Question

我正在为明天的一次非常重要的面试做准备，但有一件事我遇到了很多麻烦：排序算法和 BigO 效率。

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

score 4 · Accepted Answer

最差，其次是平均。也要注意所谓的“隐藏常量”对现实世界的影响——例如，经典的快速排序算法在最坏的情况下是 O(n^2)，平均是 O(n log n)，而归并排序在最坏的情况下是 O(n log n)，但在实践中快速排序将优于归并排序。

score 2 · Accepted Answer

当然，所有这些都很重要。您必须了解一种算法在平均情况下的好处可能会在最坏的情况下变成可怕的缺陷，或者最坏的情况并没有那么糟糕，但最好的情况也没有那么好，它只适用于未排序的数据等

score 2 · Accepted Answer

简而言之。

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

大多数快速排序变体的平均情况也是 n*log(n)，但通常比其他未高度优化的算法更快。当它不稳定时它会更快，但稳定的变体只会慢一点。主要问题是最坏的情况。最好的休闲解决方法是 Introsort。

大多数归并排序变体的最佳、平均和最差情况都固定为 n*log(n)。它稳定且相对容易扩大规模。但它需要一个相对于总项目大小的二叉树（或其仿真）。主要问题是内存。最好的休闲修复是timsort。

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

score 1 · Accepted Answer

我刚刚在我的大学完成了一组面试......

每个算法都有它的好处，否则它就不会存在。因此，最好了解您正在研究的算法有什么好处。哪里做的好？如何改进？

我想当你这样做时，你会自动需要阅读各种效率符号。注意最坏的情况，注意一般的情况，最好的情况很少见。

祝你面试顺利。

score 1 · Accepted Answer

我建议你不要仅仅记住这些事实。了解它们为何如此。如果我在采访你，我会确保问一些问题，表明你了解如何分析算法，而不仅仅是把你在网页或书中看到的东西吐出来。此外，面试前一天不是做这个学习的时间。

祝你好运！！请在评论中报告情况如何！

score 0 · Accepted Answer

您可能还想研究在某些条件存在时可以使用的其他类型的排序。例如，考虑基数排序。http://en.wikipedia.org/wiki/Radix_sort

6 回答 6