何时对数组进行排序？

Question

几年前,在一次求职面试中,我被问到:什么时候排序阵列值得？我记得不能正确回答,最近我做了一个算法课程,我得出结论,提供更"学术化"的反应可能会让我得到那份工作......无论如何,不​​可能修复过去,到目前为止,我正试图正式回答自己,目前,这就是我所在的地方:

给定一个数组,搜索的时间将是

• O(n)如果没有排序
• O(log(n))如果已排序

考虑到O(n*log(n))中的快速排序排序

何时对数组进行排序？它当然取决于我们要搜索数组的次数.

• 在有序数组中搜索x次的成本= O(n*log(n))+ [O(log(n))*x]
• 在未排序的数组中搜索x次的成本= O(n)*x

x的价值是多少？

Answer 1

我个人会回答，如果满足以下任一条件，则值得对数组进行排序：

• 我们计划经常要求数组中的最大值（将成本从 O(n) 降低到 O(1)），
• 我们计划经常要求数组中的最小值（将成本从 O(n) 降低到 O(1)），
• 我们经常会在数组中寻找给定值（将成本从 O(n) 降低到 O(log(n)）。

如果可以在 O(n) 内对数组进行排序（例如，数据满足计数排序的条件），我们将开始从搜索操作中获益（因此总时间，包括排序所需的时间，将小于k 次操作后在未排序数组中搜索所花费的时间，其中k = ConstantOfSortingOperation / (n/log(n))（对数组进行排序所花费的时间除以搜索排序器数组的增益）。

如果我们用 for ex 对数组进行排序，时间复杂度为 O(nlogn)。HeapSort 或 QuickSort（其中隐藏在大 O 表示法中的常数很小）我们将在k = (constant*nlogn)/ (n/logn)之后开始从搜索操作中获得收益。Constant/nlogn 基本上是如果我们不把时间花在排序上而是花在搜索上，我们可以搜索未排序数组多少次。n/logn 是与在未排序数组中搜索相比，在排序器数组中进行单次搜索所获得的收益。因此，如果我们认为常数很小（远小于 n），那么我们开始增益（= x，或多或少）后的时间将约为n*logn * logn / n = (log(n))^2。

如果我们计算获得最大/最小值的收益，我们就可以更快地从数组排序中获得收益。